Introduction to Code GenerationStructure of a CompilerSlide 3DefinitionsThe Big PictureSlide 6Code ShapeIntroduction to Code GenerationCopyright 2003, Keith D. Cooper, Ken Kennedy & Linda Torczon, all rights reserved.Structure of a CompilerA compiler is a lot of fast stuff followed by some hard problemsThe hard stuff is mostly in optimization and code generationFor superscalars, its allocation & scheduling that countInstructionSelectionRegisterAllocationInstructionSchedulingScanner ParserAnalysis&OptimizationO(n log n)O(n)O(n)NP-CompleteNP-CompleteEither fast orNP-CompletewordsIRIRasmasmasm∞regs∞regskregsStructure of a CompilerFor the rest of CISC672, we assume the following model•Selection is fairly simple (problem of the 1980s)•Allocation & scheduling are complex•Operation placement is not yet critical (unified register set)What about the IR ?•Low-level, RISC-like IR called ILOC •Has “enough” registers•ILOC was designed for this stuff{Branches, compares, & labelsMemory tagsHierarchy of loads & storesProvision for multiple ops/cycleInstructionSelectionInstructionSchedulingRegisterAllocationAnalysis&OptimizationIRasm asmregsregsregsregskregsasmIRDefinitionsInstruction selection•Mapping IR into assembly code•Assumes a fixed storage mapping & code shape•Combining operations, using address modesInstruction scheduling•Reordering operations to hide latencies•Assumes a fixed program (set of operations)•Changes demand for registersRegister allocation•Deciding which values will reside in registers•Changes the storage mapping, may add false sharing•Concerns about placement of data & memory operationsThese 3 problems are tightly coupled.The Big PictureHow hard are these problems?Instruction selection•Can make locally optimal choices, with automated tool•Global optimality is (undoubtedly) NP-CompleteInstruction scheduling•Single basic block heuristics work well•General problem, with control flow NP-CompleteRegister allocation•Single basic block, no spilling, & 1 register size linear time•Whole procedure is NP-CompleteThe Big PictureConventional wisdom says that we lose little by solving these problems independentlyInstruction selection•Use some form of pattern matching •Assume enough registers or target “important” values Instruction scheduling•Within a block, list scheduling is “close” to optimal •Across blocks, build framework to apply list schedulingRegister allocation•Start from virtual registers & map “enough” into k•With targeting, focus on good priority heuristicThis slide is full of “fuzzy” termsOptimal for > 85% of blocksCode ShapeDefinition•All those nebulous properties of the code that impact performance & code “quality”•Includes code, approach for different constructs, cost, storage requirements & mapping, & choice of operations•Code shape is the end product of many decisions (big & small)Impact•Code shape influences algorithm choice & results•Code shape can encode important facts, or hide themRule of thumb: expose as much derived information as possible•Example: explicit branch targets in ILOC simplify analysis•Example: hierarchy of memory operations in ILOC (in
View Full Document
Unlocking...