Bibliographic record and links to related information available from the Library of Congress catalog.
Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.
Table ofContents 1Introduction 1 1.1LanguageProcessors......................... 1 1.1.1ExercisesforSection1.1................... 3 1.2TheStructureofaCompiler..................... 4 1.2.1LexicalAnalysis....................... 5 1.2.2SyntaxAnalysis....................... 8 1.2.3SemanticAnalysis...................... 8 1.2.4IntermediateCodeGeneration............... 9 1.2.5CodeOptimization......................10 1.2.6CodeGeneration.......................10 1.2.7Symbol-TableManagement.................11 1.2.8TheGroupingofPhasesintoPasses............11 1.2.9Compiler-ConstructionTools................12 1.3TheEvolutionofProgrammingLanguages.............12 1.3.1TheMovetoHigher-levelLanguages............13 1.3.2ImpactsonCompilers....................14 1.3.3ExercisesforSection1.3...................14 1.4TheScienceofBuildingaCompiler.................15 1.4.1ModelinginCompilerDesignandImplementation....15 1.4.2TheScienceofCodeOptimization.............15 1.5ApplicationsofCompilerTechnology................17 1.5.1ImplementationofHigh-LevelProgrammingLanguages.17 1.5.2OptimizationsforComputerArchitectures.........19 1.5.3DesignofNewComputerArchitectures..........21 1.5.4ProgramTranslations....................22 1.5.5SoftwareProductivityTools.................23 1.6ProgrammingLanguageBasics...................25 1.6.1TheStatic.DynamicDistinction..............25 1.6.2EnvironmentsandStates..................26 1.6.3StaticScopeandBlockStructure..............28 1.6.4ExplicitAccessControl...................31 1.6.5DynamicScope........................31 1.6.6ParameterPassingMechanisms...............33 vii 1.6.7Aliasing............................35 1.6.8ExercisesforSection1.6...................35 1.7SummaryofChapter1........................36 1.8ReferencesforChapter1.......................38 2ASimpleSyntax-DirectedTranslator 39 2.1Introduction..............................40 2.2SyntaxDe.nition...........................42 2.2.1De.nitionofGrammars...................42 2.2.2Derivations..........................44 2.2.3ParseTrees..........................45 2.2.4Ambiguity...........................47 2.2.5AssociativityofOperators..................48 2.2.6PrecedenceofOperators...................48 2.2.7ExercisesforSection2.2...................51 2.3Syntax-DirectedTranslation.....................52 2.3.1Post.xNotation.......................53 2.3.2SynthesizedAttributes....................54 2.3.3SimpleSyntax-DirectedDe.nitions.............56 2.3.4TreeTraversals........................56 2.3.5TranslationSchemes.....................57 2.3.6ExercisesforSection2.3...................60 2.4Parsing................................60 2.4.1Top-DownParsing......................61 2.4.2PredictiveParsing......................64 2.4.3WhentoUse.-Productions.................65 2.4.4DesigningaPredictiveParser................66 2.4.5Left-Recursion........................67 2.4.6ExercisesforSection2.4...................68 2.5ATranslatorforSimpleExpressions................68 2.5.1AbstractandConcreteSyntax...............69 2.5.2AdaptingtheTranslationScheme..............70 2.5.3ProceduresfortheNonterminals..............72 2.5.4SimplifyingtheTranslator..................73 2.5.5TheCompleteProgram...................74 2.6LexicalAnalysis...........................76 2.6.1RemovalofWhiteSpaceandComments..........77 2.6.2ReadingAhead........................78 2.6.3Constants...........................78 2.6.4RecognizingKeywordsandIdenti.ers...........79 2.6.5ALexicalAnalyzer......................81 2.6.6ExercisesforSection2.6...................84 2.7SymbolTables............................85 2.7.1SymbolTablePerScope...................86 2.7.2TheUseofSymbolTables..................89 2.8IntermediateCodeGeneration...................91 2.8.1TwoKindsofIntermediateRepresentations........91 2.8.2ConstructionofSyntaxTrees................92 2.8.3StaticChecking........................97 2.8.4Three-AddressCode.....................99 2.8.5ExercisesforSection2.8...................105 2.9SummaryofChapter2........................105 3LexicalAnalysis 109 3.1TheRoleoftheLexicalAnalyzer..................109 3.1.1LexicalAnalysisVersusParsing...............110 3.1.2Tokens,Patterns,andLexemes...............111 3.1.3AttributesforTokens....................112 3.1.4LexicalErrors.........................113 3.1.5ExercisesforSection3.1...................114 3.2InputBu.ering............................115 3.2.1Bu.erPairs..........................115 3.2.2Sentinels............................116 3.3Speci.cationofTokens........................116 3.3.1StringsandLanguages....................117 3.3.2OperationsonLanguages..................119 3.3.3RegularExpressions.....................120 3.3.4RegularDe.nitions......................123 3.3.5ExtensionsofRegularExpressions.............124 3.3.6ExercisesforSection3.3...................125 3.4RecognitionofTokens........................128 3.4.1TransitionDiagrams.....................130 3.4.2RecognitionofReservedWordsandIdenti.ers......132 3.4.3CompletionoftheRunningExample............133 3.4.4ArchitectureofaTransition-Diagram-BasedLexicalAn alyzer.............................134 3.4.5ExercisesforSection3.4...................136 3.5TheLexical-AnalyzerGeneratorLex................140 3.5.1UseofLex...........................140 3.5.2StructureofLexPrograms.................141 3.5.3Con.ictResolutioninLex..................144 3.5.4TheLookaheadOperator..................144 3.5.5ExercisesforSection3.5...................146 3.6FiniteAutomata...........................147 3.6.1NondeterministicFiniteAutomata.............147 3.6.2TransitionTables.......................148 3.6.3AcceptanceofInputStringsbyAutomata.........149 3.6.4DeterministicFiniteAutomata...............149 3.6.5ExercisesforSection3.6...................151 3.7FromRegularExpressionstoAutomata..............152 3.7.1ConversionofanNFAtoaDFA..............152 3.7.2SimulationofanNFA....................156 3.7.3E.ciencyofNFASimulation................157 3.7.4ConstructionofanNFAfromaRegularExpression...159 3.7.5E.ciencyofString-ProcessingAlgorithms.........163 3.7.6ExercisesforSection3.7...................166 3.8DesignofaLexical-AnalyzerGenerator..............166 3.8.1TheStructureoftheGeneratedAnalyzer.........167 3.8.2PatternMatchingBasedonNFA's.............168 3.8.3DFA'sforLexicalAnalyzers.................170 3.8.4ImplementingtheLookaheadOperator...........171 3.8.5ExercisesforSection3.8...................172 3.9OptimizationofDFA-BasedPatternMatchers...........173 3.9.1ImportantStatesofanNFA.................173 3.9.2FunctionsComputedFromtheSyntaxTree........175 3.9.3Computingnullable,.rstpos,andlastpos..........176 3.9.4Computingfollowpos.....................177 3.9.5ConvertingaRegularExpressionDirectlytoaDFA...179 3.9.6MinimizingtheNumberofStatesofaDFA........180 3.9.7StateMinimizationinLexicalAnalyzers..........184 3.9.8TradingTimeforSpaceinDFASimulation........185 3.9.9ExercisesforSection3.9...................186 3.10SummaryofChapter3........................187 3.11ReferencesforChapter3.......................189 4SyntaxAnalysis 191 4.1Introduction..............................192 4.1.1TheRoleoftheParser....................192 4.1.2RepresentativeGrammars..................193 4.1.3SyntaxErrorHandling....................194 4.1.4Error-RecoveryStrategies..................195 4.2Context-FreeGrammars.......................197 4.2.1TheFormalDe.nitionofaContext-FreeGrammar....197 4.2.2NotationalConventions...................198 4.2.3Derivations..........................199 4.2.4ParseTreesandDerivations.................201 4.2.5Ambiguity...........................203 4.2.6VerifyingtheLanguageGeneratedbyaGrammar....204 4.2.7Context-FreeGrammarsVersusRegularExpressions...205 4.2.8ExercisesforSection4.2...................206 4.3WritingaGrammar.........................209 4.3.1LexicalVersusSyntacticAnalysis..............209 4.3.2EliminatingAmbiguity....................210 4.3.3EliminationofLeftRecursion................212 4.3.4LeftFactoring........................214 4.3.6ExercisesforSection4.3...................216 4.4Top-DownParsing..........................217 4.4.1Recursive-DescentParsing..................219 4.4.2FIRSTandFOLLOW....................220 4.4.3LL.1.Grammars.......................222 4.4.4NonrecursivePredictiveParsing...............226 4.4.5ErrorRecoveryinPredictiveParsing............228 4.4.6ExercisesforSection4.4...................231 4.5Bottom-UpParsing..........................233 4.5.1Reductions..........................234 4.5.2HandlePruning........................235 4.5.3Shift-ReduceParsing.....................236 4.5.4Con.ictsDuringShift-ReduceParsing...........238 4.5.5ExercisesforSection4.5...................240 4.6IntroductiontoLRParsing:SimpleLR..............241 4.6.1WhyLRParsers........................241 4.6.2ItemsandtheLR.0.Automaton..............242 4.6.3TheLR-ParsingAlgorithm.................248 4.6.4ConstructingSLR-ParsingTables..............252 4.6.5ViablePre.xes........................256 4.6.6ExercisesforSection4.6...................257 4.7MorePowerfulLRParsers......................259 4.7.1CanonicalLR.1.Items....................260 4.7.2ConstructingLR.1.SetsofItems..............261 4.7.3CanonicalLR.1.ParsingTables..............265 4.7.4ConstructingLALRParsingTables.............266 4.7.5E.cientConstructionofLALRParsingTables......270 4.7.6CompactionofLRParsingTables.............275 4.7.7ExercisesforSection4.7...................277 4.8UsingAmbiguousGrammars....................278 4.8.1PrecedenceandAssociativitytoResolveCon.icts....279 4.8.2The.Dangling-Else"Ambiguity..............281 4.8.3ErrorRecoveryinLRParsing................283 4.8.4ExercisesforSection4.8...................285 4.9ParserGenerators..........................287 4.9.1TheParserGeneratorYacc.................287 4.9.2UsingYaccwithAmbiguousGrammars..........291 4.9.3CreatingYaccLexicalAnalyzerswithLex.........294 4.9.4ErrorRecoveryinYacc...................295 4.9.5ExercisesforSection4.9...................297 4.10SummaryofChapter4........................297 4.11ReferencesforChapter4.......................300 5Syntax-DirectedTranslation 303 5.1Syntax-DirectedDe.nitions.....................304 5.1.1InheritedandSynthesizedAttributes............304 5.1.2EvaluatinganSDDattheNodesofaParseTree.....306 5.1.3ExercisesforSection5.1...................309 5.2EvaluationOrdersforSDD's....................310 5.2.1DependencyGraphs.....................310 5.2.2OrderingtheEvaluationofAttributes...........312 5.2.3S-AttributedDe.nitions...................312 5.2.4L-AttributedDe.nitions...................313 5.2.5SemanticRuleswithControlledSideE.ects........314 5.2.6ExercisesforSection5.2...................317 5.3ApplicationsofSyntax-DirectedTranslation............318 5.3.1ConstructionofSyntaxTrees................318 5.3.2TheStructureofaType...................321 5.3.3ExercisesforSection5.3...................323 5.4Syntax-DirectedTranslationSchemes................324 5.4.1Post.xTranslationSchemes.................324 5.4.2Parser-StackImplementationofPost.xSDT's......325 5.4.3SDT'sWithActionsInsideProductions..........327 5.4.4EliminatingLeftRecursionFromSDT's..........328 5.4.5SDT'sforL-AttributedDe.nitions.............331 5.4.6ExercisesforSection5.4...................336 5.5ImplementingL-AttributedSDD's.................337 5.5.1TranslationDuringRecursive-DescentParsing......338 5.5.2On-The-FlyCodeGeneration................340 5.5.3L-AttributedSDD'sandLLParsing............343 5.5.4Bottom-UpParsingofL-AttributedSDD's........348 5.5.5ExercisesforSection5.5...................352 5.6SummaryofChapter5........................353 5.7ReferencesforChapter5.......................354 6Intermediate-CodeGeneration357 6.1VariantsofSyntaxTrees.......................358 6.1.1DirectedAcyclicGraphsforExpressions..........359 6.1.2TheValue-NumberMethodforConstructingDAG's...360 6.1.3ExercisesforSection6.1...................362 6.2Three-AddressCode.........................363 6.2.1AddressesandInstructions.................364 6.2.2Quadruples..........................366 6.2.3Triples.............................367 6.2.4StaticSingle-AssignmentForm...............369 6.2.5ExercisesforSection6.2...................370 6.3TypesandDeclarations.......................370 6.3.1TypeExpressions.......................371 6.3.2TypeEquivalence.......................372 6.3.3Declarations..........................373 6.3.4StorageLayoutforLocalNames..............373 6.3.5SequencesofDeclarations..................376 6.3.6FieldsinRecordsandClasses................376 6.3.7ExercisesforSection6.3...................378 6.4TranslationofExpressions......................378 6.4.1OperationsWithinExpressions...............378 6.4.2IncrementalTranslation...................380 6.4.3AddressingArrayElements.................381 6.4.4TranslationofArrayReferences...............383 6.4.5ExercisesforSection6.4...................384 6.5TypeChecking............................386 6.5.1RulesforTypeChecking...................387 6.5.2TypeConversions......................388 6.5.3OverloadingofFunctionsandOperators..........390 6.5.4TypeInferenceandPolymorphicFunctions........391 6.5.5AnAlgorithmforUni.cation................395 6.5.6ExercisesforSection6.5...................398 6.6ControlFlow.............................399 6.6.1BooleanExpressions.....................399 6.6.2Short-CircuitCode......................400 6.6.3Flow-of-ControlStatements.................401 6.6.4Control-FlowTranslationofBooleanExpressions.....403 6.6.5AvoidingRedundantGotos.................405 6.6.6BooleanValuesandJumpingCode.............408 6.6.7ExercisesforSection6.6...................408 6.7Backpatching.............................410 6.7.1One-PassCodeGenerationUsingBackpatching......410 6.7.2BackpatchingforBooleanExpressions...........411 6.7.3Flow-of-ControlStatements.................413 6.7.4Break-,Continue-,andGoto-Statements..........416 6.7.5ExercisesforSection6.7...................417 6.8Switch-Statements..........................418 6.8.1TranslationofSwitch-Statements..............419 6.8.2Syntax-DirectedTranslationofSwitch-Statements....420 6.8.3ExercisesforSection6.8...................421 6.9IntermediateCodeforProcedures..................422 6.10SummaryofChapter6........................424 6.11ReferencesforChapter6.......................425 7Run-TimeEnvironments 427 7.1StorageOrganization.........................427 7.1.1StaticVersusDynamicStorageAllocation.........429 7.2StackAllocationofSpace......................430 7.2.1ActivationTrees.......................430 7.2.2ActivationRecords......................433 7.2.3CallingSequences......................436 7.2.4Variable-LengthDataontheStack.............438 7.2.5ExercisesforSection7.2...................440 7.3AccesstoNonlocalDataontheStack...............441 7.3.1DataAccessWithoutNestedProcedures..........442 7.3.2IssuesWithNestedProcedures...............442 7.3.3ALanguageWithNestedProcedureDeclarations.....443 7.3.4NestingDepth........................443 7.3.5AccessLinks.........................445 7.3.6ManipulatingAccessLinks.................447 7.3.7AccessLinksforProcedureParameters..........448 7.3.8Displays............................449 7.3.9ExercisesforSection7.3...................451 7.4HeapManagement..........................452 7.4.1TheMemoryManager....................453 7.4.2TheMemoryHierarchyofaComputer...........454 7.4.3LocalityinPrograms.....................455 7.4.4ReducingFragmentation...................457 7.4.5ManualDeallocationRequests...............460 7.4.6ExercisesforSection7.4...................463 7.5IntroductiontoGarbageCollection.................463 7.5.1DesignGoalsforGarbageCollectors............464 7.5.2Reachability..........................466 7.5.3ReferenceCountingGarbageCollectors..........468 7.5.4ExercisesforSection7.5...................470 7.6IntroductiontoTrace-BasedCollection...............470 7.6.1ABasicMark-and-SweepCollector.............471 7.6.2BasicAbstraction......................473 7.6.3OptimizingMark-and-Sweep................475 7.6.4Mark-and-CompactGarbageCollectors..........476 7.6.5Copyingcollectors......................478 7.6.6ComparingCosts.......................482 7.6.7ExercisesforSection7.6...................482 7.7Short-PauseGarbageCollection...................483 7.7.1IncrementalGarbageCollection...............483 7.7.2IncrementalReachabilityAnalysis.............485 7.7.3Partial-CollectionBasics...................487 7.7.4GenerationalGarbageCollection..............488 7.7.5TheTrainAlgorithm.....................490 7.7.6ExercisesforSection7.7...................493 7.8AdvancedTopicsinGarbageCollection..............494 7.8.1ParallelandConcurrentGarbageCollection........495 7.8.2PartialObjectRelocation..................497 7.8.3ConservativeCollectionforUnsafeLanguages.......498 7.8.4WeakReferences.......................498 7.8.5ExercisesforSection7.8...................499 7.9SummaryofChapter7........................500 7.10ReferencesforChapter7.......................502 8CodeGeneration 505 8.1IssuesintheDesignofaCodeGenerator.............506 8.1.1InputtotheCodeGenerator................507 8.1.2TheTargetProgram.....................507 8.1.3InstructionSelection.....................508 8.1.4RegisterAllocation......................510 8.1.5EvaluationOrder.......................511 8.2TheTargetLanguage........................512 8.2.1ASimpleTargetMachineModel..............512 8.2.2ProgramandInstructionCosts...............515 8.2.3ExercisesforSection8.2...................516 8.3AddressesintheTargetCode....................518 8.3.1StaticAllocation.......................518 8.3.2StackAllocation.......................520 8.3.3Run-TimeAddressesforNames...............522 8.3.4ExercisesforSection8.3...................524 8.4BasicBlocksandFlowGraphs...................525 8.4.1BasicBlocks.........................526 8.4.2Next-UseInformation....................528 8.4.3FlowGraphs.........................529 8.4.4RepresentationofFlowGraphs...............530 8.4.5Loops.............................531 8.4.6ExercisesforSection8.4...................531 8.5OptimizationofBasicBlocks....................533 8.5.1TheDAGRepresentationofBasicBlocks.........533 8.5.2FindingLocalCommonSubexpressions..........534 8.5.3DeadCodeElimination...................535 8.5.4TheUseofAlgebraicIdentities...............536 8.5.5RepresentationofArrayReferences.............537 8.5.6PointerAssignmentsandProcedureCalls.........539 8.5.7ReassemblingBasicBlocksFromDAG's..........539 8.5.8ExercisesforSection8.5...................541 8.6ASimpleCodeGenerator......................542 8.6.1RegisterandAddressDescriptors..............543 8.6.2TheCode-GenerationAlgorithm..............544 8.6.3DesignoftheFunctiongetReg................547 8.6.4ExercisesforSection8.6...................548 8.7PeepholeOptimization........................549 8.7.1EliminatingRedundantLoadsandStores.........550 8.7.2EliminatingUnreachableCode...............550 8.7.3Flow-of-ControlOptimizations...............551 8.7.4AlgebraicSimpli.cationandReductioninStrength....552 8.7.5UseofMachineIdioms....................552 8.7.6ExercisesforSection8.7...................553 8.8RegisterAllocationandAssignment................553 8.8.1GlobalRegisterAllocation..................553 8.8.2UsageCounts.........................554 8.8.3RegisterAssignmentforOuterLoops...........556 8.8.4RegisterAllocationbyGraphColoring...........556 8.8.5ExercisesforSection8.8...................557 8.9InstructionSelectionbyTreeRewriting..............558 8.9.1Tree-TranslationSchemes..................558 8.9.2CodeGenerationbyTilinganInputTree.........560 8.9.3PatternMatchingbyParsing................563 8.9.4RoutinesforSemanticChecking..............565 8.9.5GeneralTreeMatching....................565 8.9.6ExercisesforSection8.9...................567 8.10OptimalCodeGenerationforExpressions.............567 8.10.1ErshovNumbers.......................567 8.10.2GeneratingCodeFromLabeledExpressionTrees.....568 8.10.3EvaluatingExpressionswithanInsu.cientSupplyofReg isters..............................570 8.10.4ExercisesforSection8.10..................572 8.11DynamicProgrammingCode-Generation..............573 8.11.1ContiguousEvaluation....................574 8.11.2TheDynamicProgrammingAlgorithm...........575 8.11.3ExercisesforSection8.11..................577 8.12SummaryofChapter8........................578 8.13ReferencesforChapter8.......................579 9Machine-IndependentOptimizations583 9.1ThePrincipalSourcesofOptimization...............584 9.1.1CausesofRedundancy....................584 9.1.2ARunningExample:Quicksort...............585 9.1.3Semantics-PreservingTransformations...........586 9.1.4GlobalCommonSubexpressions..............588 9.1.5CopyPropagation......................590 9.1.6Dead-CodeElimination...................591 9.1.7CodeMotion.........................592 9.1.8InductionVariablesandReductioninStrength......592 9.1.9ExercisesforSection9.1...................596 9.2IntroductiontoData-FlowAnalysis................597 9.2.1TheData-FlowAbstraction.................597 9.2.2TheData-FlowAnalysisSchema..............599 9.2.3Data-FlowSchemasonBasicBlocks............600 9.2.4ReachingDe.nitions.....................601 9.2.5Live-VariableAnalysis....................608 9.2.6AvailableExpressions....................610 9.2.7Summary...........................614 9.2.8ExercisesforSection9.2...................615 9.3FoundationsofData-FlowAnalysis.................618 9.3.1Semilattices..........................618 9.3.2TransferFunctions......................623 9.3.3TheIterativeAlgorithmforGeneralFrameworks.....626 9.3.4MeaningofaData-FlowSolution..............628 9.3.5ExercisesforSection9.3...................631 9.4ConstantPropagation........................632 9.4.1Data-FlowValuesfortheConstant-PropagationFrame work..............................633 9.4.2TheMeetfortheConstant-PropagationFramework...633 9.4.3TransferFunctionsfortheConstant-PropagationFrame work..............................634 9.4.4MonotonicityoftheConstant-PropagationFramework..635 9.4.5NondistributivityoftheConstant-PropagationFramework635 9.4.6InterpretationoftheResults................637 9.4.7ExercisesforSection9.4...................637 9.5Partial-RedundancyElimination..................639 9.5.1TheSourcesofRedundancy.................639 9.5.2CanAllRedundancyBeEliminated.............642 9.5.3TheLazy-Code-MotionProblem..............644 9.5.4AnticipationofExpressions.................645 9.5.5TheLazy-Code-MotionAlgorithm.............646 9.5.6ExercisesforSection9.5...................655 9.6LoopsinFlowGraphs........................655 9.6.1Dominators..........................656 9.6.2Depth-FirstOrdering....................660 9.6.3EdgesinaDepth-FirstSpanningTree...........661 9.6.4BackEdgesandReducibility................662 9.6.5DepthofaFlowGraph...................665 9.6.6NaturalLoops........................665 9.6.7SpeedofConvergenceofIterativeData-FlowAlgorithms.667 9.6.8ExercisesforSection9.6...................669 9.7Region-BasedAnalysis........................672 9.7.1Regions............................672 9.7.2RegionHierarchiesforReducibleFlowGraphs......673 9.7.3OverviewofaRegion-BasedAnalysis...........676 9.7.4NecessaryAssumptionsAboutTransferFunctions....678 9.7.5AnAlgorithmforRegion-BasedAnalysis.........680 9.7.6HandlingNonreducibleFlowGraphs............684 9.7.7ExercisesforSection9.7...................686 9.8SymbolicAnalysis..........................686 9.8.1A.neExpressionsofReferenceVariables.........687 9.8.2Data-FlowProblemFormulation..............689 9.8.3Region-BasedSymbolicAnalysis..............694 9.8.4ExercisesforSection9.8...................699 9.9SummaryofChapter9........................700 9.10ReferencesforChapter9.......................703 10Instruction-LevelParallelism 707 10.1ProcessorArchitectures.......................708 10.1.1InstructionPipelinesandBranchDelays..........708 10.1.2PipelinedExecution.....................709 10.1.3MultipleInstructionIssue..................710 10.2Code-SchedulingConstraints....................710 10.2.1DataDependence.......................711 10.2.2FindingDependencesAmongMemoryAccesses......712 10.2.3Tradeo.BetweenRegisterUsageandParallelism.....713 10.2.4PhaseOrderingBetweenRegisterAllocationandCode Scheduling..........................716 10.2.5ControlDependence.....................716 10.2.6SpeculativeExecutionSupport...............717 10.2.7ABasicMachineModel...................719 10.2.8ExercisesforSection10.2..................720 10.3Basic-BlockScheduling........................721 10.3.1Data-DependenceGraphs..................722 10.3.2ListSchedulingofBasicBlocks...............723 10.3.3PrioritizedTopologicalOrders...............725 10.3.4ExercisesforSection10.3..................726 10.4GlobalCodeScheduling.......................727 10.4.1PrimitiveCodeMotion...................728 10.4.2UpwardCodeMotion....................730 10.4.3DownwardCodeMotion...................731 10.4.4UpdatingDataDependences................732 10.4.5GlobalSchedulingAlgorithms................732 10.4.6AdvancedCodeMotionTechniques.............736 10.4.7InteractionwithDynamicSchedulers............737 10.4.8ExercisesforSection10.4..................737 10.5SoftwarePipelining..........................738 10.5.1Introduction.........................738 10.5.2SoftwarePipeliningofLoops................740 10.5.3RegisterAllocationandCodeGeneration.........743 10.5.4Do-AcrossLoops.......................743 10.5.5GoalsandConstraintsofSoftwarePipelining.......745 10.5.6ASoftware-PipeliningAlgorithm..............749 10.5.7SchedulingAcyclicData-DependenceGraphs.......749 10.5.8SchedulingCyclicDependenceGraphs...........751 10.5.9ImprovementstothePipeliningAlgorithms........758 10.5.10ModularVariableExpansion................758 10.5.11ConditionalStatements...................761 10.5.12HardwareSupportforSoftwarePipelining.........762 10.5.13ExercisesforSection10.5..................763 10.6SummaryofChapter10.......................765 10.7ReferencesforChapter10......................766 11OptimizingforParallelismandLocality 769 11.1BasicConcepts............................771 11.1.1Multiprocessors........................772 11.1.2ParallelisminApplications.................773 11.1.3Loop-LevelParallelism....................775 11.1.4DataLocality.........................777 11.1.5IntroductiontoA.neTransformTheory.........778 11.2MatrixMultiply:AnIn-DepthExample..............782 11.2.1TheMatrix-MultiplicationAlgorithm...........782 11.2.2Optimizations.........................785 11.2.3CacheInterference......................788 11.2.4ExercisesforSection11.2..................788 11.3IterationSpaces............................788 11.3.1ConstructingIterationSpacesfromLoopNests......788 11.3.2ExecutionOrderforLoopNests..............791 11.3.3MatrixFormulationofInequalities.............791 11.3.4IncorporatingSymbolicConstants.............793 11.3.5ControllingtheOrderofExecution.............793 11.3.6ChangingAxes........................798 11.3.7ExercisesforSection11.3..................799 11.4A.neArrayIndexes.........................801 11.4.1A.neAccesses........................802 11.4.2A.neandNona.neAccessesinPractice.........803 11.4.3ExercisesforSection11.4..................804 11.5DataReuse..............................804 11.5.1TypesofReuse........................805 11.5.2SelfReuse...........................806 11.5.3Self-SpatialReuse......................809 11.5.4GroupReuse.........................811 11.5.5ExercisesforSection11.5..................814 11.6ArrayData-DependenceAnalysis..................815 11.6.1De.nitionofDataDependenceofArrayAccesses.....816 11.6.2IntegerLinearProgramming................817 11.6.3TheGCDTest........................818 11.6.4HeuristicsforSolvingIntegerLinearPrograms......820 11.6.5SolvingGeneralIntegerLinearPrograms.........823 11.6.6Summary...........................825 11.6.7ExercisesforSection11.6..................826 11.7FindingSynchronization-FreeParallelism.............828 11.7.1AnIntroductoryExample..................828 11.7.2A.neSpacePartitions....................830 11.7.3Space-PartitionConstraints.................831 11.7.4SolvingSpace-PartitionConstraints............835 11.7.5ASimpleCode-GenerationAlgorithm...........838 11.7.6EliminatingEmptyIterations................841 11.7.7EliminatingTestsfromInnermostLoops..........844 11.7.8Source-CodeTransforms...................846 11.7.9ExercisesforSection11.7..................851 11.8SynchronizationBetweenParallelLoops..............853 11.8.1AConstantNumberofSynchronizations..........853 11.8.2Program-DependenceGraphs................854 11.8.3HierarchicalTime......................857 11.8.4TheParallelizationAlgorithm................859 11.8.5ExercisesforSection11.8..................860 11.9Pipelining...............................861 11.9.1WhatisPipelining......................861 11.9.2SuccessiveOver-Relaxation.SOR.:AnExample.....863 11.9.3FullyPermutableLoops...................864 11.9.4PipeliningFullyPermutableLoops.............864 11.9.5GeneralTheory........................867 11.9.6Time-PartitionConstraints.................868 11.9.7SolvingTime-PartitionConstraintsbyFarkas'Lemma..872 11.9.8CodeTransformations....................875 11.9.9ParallelismWithMinimumSynchronization........880 11.9.10ExercisesforSection11.9..................882 11.10LocalityOptimizations.......................884 11.10.1TemporalLocalityofComputedData...........885 11.10.2ArrayContraction......................885 11.10.3PartitionInterleaving....................887 11.10.4PuttingitAllTogether...................890 11.10.5ExercisesforSection11.10..................892 11.11OtherUsesofA.neTransforms..................893 11.11.1Distributedmemorymachines................894 11.11.2Multi-Instruction-IssueProcessors.............895 11.11.3VectorandSIMDInstructions...............895 11.11.4Prefetching..........................896 11.12SummaryofChapter11.......................897 11.13ReferencesforChapter11......................899 12InterproceduralAnalysis 903 12.1BasicConcepts............................904 12.1.1CallGraphs..........................904 12.1.2ContextSensitivity......................906 12.1.3CallStrings..........................908 12.1.4Cloning-BasedContext-SensitiveAnalysis.........910 12.1.5Summary-BasedContext-SensitiveAnalysis........911 12.1.6ExercisesforSection12.1..................914 12.2WhyInterproceduralAnalysis....................916 12.2.1VirtualMethodInvocation.................916 12.2.2PointerAliasAnalysis....................917 12.2.3Parallelization........................917 12.2.4DetectionofSoftwareErrorsandVulnerabilities.....917 12.2.5SQLInjection.........................918 12.2.6Bu.erOver.ow........................920 12.3ALogicalRepresentationofDataFlow...............921 12.3.1IntroductiontoDatalog...................921 12.3.2DatalogRules.........................922 12.3.3IntensionalandExtensionalPredicates...........924 12.3.4ExecutionofDatalogPrograms...............927 12.3.5IncrementalEvaluationofDatalogPrograms.......928 12.3.6ProblematicDatalogRules.................930 12.3.7ExercisesforSection12.3..................932 12.4ASimplePointer-AnalysisAlgorithm................933 12.4.1WhyisPointerAnalysisDi.cult..............934 12.4.2AModelforPointersandReferences............935 12.4.3FlowInsensitivity......................936 12.4.4TheFormulationinDatalog.................937 12.4.5UsingTypeInformation...................938 12.4.6ExercisesforSection12.4..................939 12.5Context-InsensitiveInterproceduralAnalysis............941 12.5.1E.ectsofaMethodInvocation...............941 12.5.2CallGraphDiscoveryinDatalog..............943 12.5.3DynamicLoadingandRe.ection..............944 12.5.4ExercisesforSection12.5..................945 12.6Context-SensitivePointerAnalysis.................945 12.6.1ContextsandCallStrings..................946 12.6.2AddingContexttoDatalogRules..............949 12.6.3AdditionalObservationsAboutSensitivity.........949 12.6.4ExercisesforSection12.6..................950 12.7DatalogImplementationbyBDD's.................951 12.7.1BinaryDecisionDiagrams..................951 12.7.2TransformationsonBDD's.................953 12.7.3RepresentingRelationsbyBDD's..............954 12.7.4RelationalOperationsasBDDOperations.........954 12.7.5UsingBDD'sforPoints-toAnalysis............957 12.7.6ExercisesforSection12.7..................958 12.8SummaryofChapter12.......................958 12.9ReferencesforChapter12......................961 AACompleteFrontEnd 965 A.1TheSourceLanguage........................965 A.2Main..................................966 A.3LexicalAnalyzer...........................967 A.4SymbolTablesandTypes......................970 A.5IntermediateCodeforExpressions.................971 A.6JumpingCodeforBooleanExpressions..............974 A.7IntermediateCodeforStatements.................978 A.8Parser.................................981 A.9CreatingtheFrontEnd.......................986 BFindingLinearlyIndependentSolutions989 Index 993
Library of Congress Subject Headings for this publication:
Compilers (Computer programs).