Wrapping UpHigh-level ViewSlide 3Front EndMiddle (Optimizer)Back EndSlide 7Slide 8Slide 9PerspectiveSlide 11Slide 12Wrapping Up Copyright 2003, Keith D. Cooper, Ken Kennedy & Linda Torczon, all rights reserved.The Last Lecture High-level ViewDefinitions•Compiler consumes code & produces code•Interpreter consumes executable & produces resultsSourcecodeMachinecodeCompilerErrorsThe Last Lecture High-level View•Front end consumes source code & produces IRDetermines code shape for rest of compiler •Middle reads & writes IRAnalyzes & transforms IR to “improve” itMyriad techniques at several distinct scopes•Back end consumes optimizes IR & produces target codeMaps code to target ISA & handles resource issuesErrors SourceCodeMiddleFrontEndMachinecodeBackEndIRIRThe Last Lecture Front EndScanner•Applies DFA technology to classify words•Use RE-based tools to generate fast scannersParser•Takes stream of classified words & computes structure•Many techniques (TDRD, LL(1), LR(1) + others)Context-sensitive Analysis•Type-checking & IR generation (AGs & Ad-hoc SDT)•Problems are harder & tools not as well developedErrors SourceCodeMiddleFrontEndMachinecodeBackEndIRIRSolved ProblemsThe Last Lecture Middle (Optimizer)•Typically structured as a series of passesAllows for separation of concernsSimplifies development & debugging•Rewrites IR to improve running time, code space, …•We studied redundancy eliminationOther optimizations include code motion, dead-code elimination, constant propagation, strength reduction, … (see Ch 10)Errors SourceCodeMiddleFrontEndMachinecodeBackEndIRIRMost compilers need better optimization …The Last Lecture Back EndErrors SourceCodeMiddleFrontEndMachinecodeBackEndIRIRThree Problems•Instruction SelectionMapping optimized IR to target machine’s ISA•Instruction SchedulingReordering operations to hide latencies & speed execution•Register AllocationMapping name space of optimized IR to target’s register setThe Last Lecture Back EndErrors SourceCodeMiddleFrontEndMachinecodeBackEndIRIRInstruction Selection•This is a pattern-matching problemWe looked at tree pattern matching, peephole optimizationOther ideas: string matching, ad-hoc matching, parsing, …•Criterion is “local optimality”Map immediate context to ISA in an efficient wayLeave “global optimality” to optimizer•My algorithm of choice: peephole matchingThe Last Lecture Back EndErrors SourceCodeMiddleFrontEndMachinecodeBackEndIRIRInstruction Scheduling•Fixed set of operations, can vary the orderMust preserve inter-operation dependencesMay change demand for registers•List scheduling is dominant paradigmApplied to blocks, extended blocks, regions in code•My algorithm of choice: Schielke’s RBF algorithm on EBBsThe Last Lecture Back EndErrors SourceCodeMiddleFrontEndMachinecodeBackEndIRIRRegister Allocation•Handle disconnect between optimizer’s assumption of unlimited registers and chip’s limited setInsert loads and stores to reconcile the two models (spills)Minimize the slowdown•Global allocation via graph coloring is the dominant paradigmBuild interference graph and color itMany minor variations, but one strong themeThe Last Lecture PerspectiveDifferent concerns in each phase•Front end worries about shaping code for optimizationExpose facts that can be improved & tailored•Middle worries about global issues that affect speed, spaceRedundancy, constants, code motion, locality, ...•Back end worries about using the target’s resourcesAddress modes, functional units, registers, issue slots, …Errors SourceCodeMiddleFrontEndMachinecodeBackEndIRIRThese concerns “bleed” from one phase to anotherThe Last Lecture PerspectiveDifferent complexities in each phase•Front end is mostly linear timeDFAs, parsers take time proportional to size of input stream•Middle is low-order polynomial timeAnalysis & optimization are O(n) to O(n2 ), in general•Back end solves hard problems with approximationsHeuristics that typically take O(n) to (n2) Underlying problems are seriously hardErrors SourceCodeMiddleFrontEndMachinecodeBackEndIRIRThe Last Lecture PerspectiveRemaining work•Front end is solvedNo more theses on parsing•Middle has some room for work (not a wide open frontier) New machines, new languages present new problems•Back end has room for workComplications from new machines Longer latencies, wider processorsErrors
View Full Document
Unlocking...