Table of contents for Compilers : principles, techniques, and tools / Al Aho ... [et al.].

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.


Counter
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).