Page ‹#›School of Computer ScienceInstruction Selection15-745 Optimizing CompilersSpring 20071School of Computer Science2School of Computer ScienceIRTempMapinstructionselectorregisterallocatorAssemAsseminstructionschedulerCompiler Backend3School of Computer ScienceIntermediate RepresentationsFront end - produces an intermediate representation (IR)Middle end - transforms the IR into an equivalent IR that runs moreefficientlyBack end - transforms the IR into native codeIR encodes the compiler’s knowledge of the programMiddle end usually consists of several passesFrontEndMiddleEndBackEndIR IRSourceCodeTargetCodePage ‹#›4School of Computer ScienceIntermediate RepresentationsDecisions in IR design affect the speed and efficiency ofthe compilerSome important IR properties– Ease of generation– Ease of manipulation– Procedure size– Freedom of expression– Level of abstractionThe importance of different properties varies betweencompilers– Selecting an appropriate IR for a compiler is critical5School of Computer ScienceExamples:Trees, DAGs Examples:3 address codeStack machine code Example:Control-flow graph Types of IntermediateRepresentationsStructural– Graphically oriented– Heavily used in source-to-source translators– Tend to be largeLinear– Pseudo-code for an abstract machine– Level of abstraction varies– Simple, compact data structures– Easier to rearrangeHybrid– Combination of graphs and linear code6School of Computer ScienceLevel of AbstractionThe level of detail exposed in an IR influences theprofitability and feasibility of different optimizations.Two different representations of an array reference:subscriptA ijloadI 1 => r1sub rj, r1 => r2loadI 10 => r3mult r2, r3 => r4sub ri, r1 => r5add r4, r5 => r6loadI @A => r7add r7, r6 => r8load r8 => rAijHigh level AST:Good for memory disambiguationLow level linear code:Good for address calculation7School of Computer ScienceLevel of AbstractionStructural IRs are usually considered high-levelLinear IRs are usually considered low-levelNot necessarily true:+*10j1- j1-+@AloadLow level ASTloadArray A,i,jHigh level linear codePage ‹#›8School of Computer ScienceAbstract Syntax TreeAn abstract syntax tree is the procedure’s parsetree with the nodes for most non-terminal nodesremoved -x2y*x - 2 * yWhen is an AST a good IR?Structural IR9School of Computer ScienceDirected Acyclic GraphA directed acyclic graph (DAG) is an AST with a uniquenode for each valueMakes sharing explicitEncodes redundancyx2y*-←z/←wz ← x - 2 * yw ← x / 2Same expression twice meansthat the compiler might arrangeto evaluate it just once!Structural IR10School of Computer SciencePegasus IRPredicated ExplicitGAted SimpleUniform SSAStructural IR used inCASH (Compiler forApplication SpecificHardware)Structural IR11School of Computer ScienceStack Machine CodeOriginally used for stack-based computers, now JavaExample:x - 2 * y becomesAdvantages– Compact form– Introduced names are implicit, not explicit– Simple to generate and execute codeUseful where code is transmittedover slow communication links (the net )push xpush 2push ymultiplysubtractImplicit names take upno space, where explicitones do!Linear IRPage ‹#›12School of Computer ScienceThree Address CodeThree address code has statements of the form:x ← y op zWith 1 operator (op ) and, at most, 3 names (x, y, & z)Example:z ← x - 2 * y becomesAdvantages:– Resembles many machines (RISC)– Compact formt ← 2 * yz ← x - tLinear IR13School of Computer ScienceTwo Address CodeAllows statements of the formx ← x op yHas 1 operator (op ) and, at most, 2 names (x and y)Example:z ← x - 2 * y becomes– Can be very compact– Destructive operations make reuse hard– Good model for machines with destructive ops (x86)t1 ← 2t2 ← load yt2 ← t2 * t1z ← load xz ← z - t2Linear IR14School of Computer ScienceControl-flow GraphModels the transfer of control in the procedureNodes in the graph are basic blocks– Straight-line code– Either linear or structural representationEdges in the graph represent control flowExampleif (x = y)a ← 2b ← 5a ← 3b ← 4c ← a * bBasic blocks —Maximal lengthsequences ofstraight-line codeHybrid IR15School of Computer ScienceUsing Multiple RepresentationsRepeatedly lower the level of the intermediate representation– Each intermediate representation is suited towards certain optimizationsExample: the Open64 compiler– WHIRL intermediate format• Consists of 5 different IRs that are progressively more detailed– gcc• but not explicit about it :-(FrontEndMiddleEndBackEndIR 1 IR 3SourceCodeTargetCodeMiddleEndIR 2Page ‹#›16School of Computer ScienceInstruction SelectionIRinstructionselectorAssemIR -> Assemtemplates17School of Computer ScienceInstruction selection exampleSuppose we haveWe can generate the x86 code……if c = 1, 2, or 4; otherwise…MOVE(TEMP r, MEM(BINOP(TIMES,TEMP s,CONST c)))movl %(,s,c), %rimull $c, %s, %rmovl (%r), %r18School of Computer ScienceMOVE(TEMP r, MEM(BINOP(TIMES,TEMP s,CONST c)))MOVE(TEMP r, MEM(BINOP(TIMES,TEMP s,CONST c)))Selection dependenciesWe can see that the selection of instructions candepend on the constantsThe context of an IR expression can also affect thechoice of instructionConsider19School of Computer ScienceForwe might sometimes want to generateWhat context might cause us to do this?testl $0,(,%s,c)je LMEM(BINOP(TIMES,TEMP s,CONST c))Example, cont’dPage ‹#›20School of Computer ScienceInstruction selection as tree matchingIn order to take context into account, instructionselectors often use pattern-matching on IR trees– each pattern specifies what instructions to select21School of Computer ScienceIf c is 1, 2, or 4Sample tree-matching rulesIR pattern code costBINOP(PLUS,i,j) leal (i,j),r 1BINOP(TIMES,i,j) movl j,r 2 imull i,rBINOP(PLUS,i,CONST c) leal c(i),r 1MEM(BINOP(PLUS,i,CONST c)) movl c(i),r 1MOVE(MEM(BINOP(PLUS,i,j)),k) movl k,(i,j) 1BINOP(TIMES,i,CONST c) leal (,i,c),r 1BINOP(TIMES,i,CONST c) movl c,r 2 imull i,rMEM(i) movl (i),r 1MOVE(MEM(i),j) movl j,(i) 1MOVE(MEM(i),MEM(j)) movl (j),t 2 movl t,(i)…22School of Computer Sciencea[x] = *y;MOVEMEMMEMy+MEM+EBP CONST aleal $a(%ebp),r1movl (r1),r2leal (,x,$4),r3leal (r2,r3),r4movl (y),r5movl r5,(r4)CONST 4*x(assume a is aformal parameterpassed on the stack)r1r2 r3r4Tiling an IR tree, v.123School of Computer ScienceTiling an IR tree, v.2a[x] =
View Full Document
Unlocking...