Instruction Selection IIThe Back EndInstruction SelectionArchitecture DifferencesAddressing ModesMinimizing CostTree RepresentationTilesTilingSlide 10Slide 11AlgorithmsAd-Hoc AlgorithmIncluding CostDynamic ProgrammingRecursive AlgorithmPseudocodeSlide 18Code Generator GeneratorsTree NotationRewrite RulesSlide 22ExampleRewriting ProcessModern ProcessorsInstruction Selection IICS 671February 26, 20082CS 671 – Spring 2008The Back EndEssential tasks:Instruction selection•Map low-level IR to actual machine instructions•Not necessarily 1-1 mapping•CISC architectures, addressing modesRegister allocation•Low-level IR assumes unlimited registers•Map to actual resources of machines•Goal: maximize use of registers3CS 671 – Spring 2008Instruction SelectionInstruction sets•ISA often has many ways to do the same thing•Idiom: A single instruction that represents a common pattern or sequence of operationsConsider a machine with the following instructions:add r2, r1 r1 ← r1 + r2muli c, r1 r1 ← r1 * cload r2, r1 r1 ← *r2store r2, r1 *r1 ← r2movem r2, r1 *r1 ← *r2movex r3, r2, r1 *r1 ← *(r2 + r3)Sometimes [r2]4CS 671 – Spring 2008Architecture DifferencesRISC (PowerPC, MIPS)•Arithmetic operations require registers•Explicit loads and storesCISC (x86)•Complex instructions (e.g., MMX and SSE)•Arithmetic operations may refer to memory•BUT, only one memory operation per instructionld 8(r0), r1add $12, r1add 8(%esp), %eax5CS 671 – Spring 2008Addressing ModesProblem:•Some architectures (x86) allow different addressing modes in instructions other than load and storeadd $1, 0xaf0080add $1, (%eax)add $1, -8(%eax)add $1, -8(%eax, %ebx, 2)Addr = 0xaf0080Addr = contents of %eaxAddr = %eax - 8Addr = (%eax + %ebx * 2) - 86CS 671 – Spring 2008Minimizing CostGoal:•Find instructions with low overall costDifficulty•How to find these patterns?•Machine idioms may subsume IR operations that are not adjacentIdea: back to tree representation•Convert computation into a tree•Match parts of the treeIRt1 = j*4t2 = b+t1t3 = *t2t4 = i+1t5 = t4*4t6 = a+t5*t6 = t4movem rb, ra7CS 671 – Spring 2008Tree RepresentationBuild a tree:Goal: find parts of the tree that correspond to machine instructionsa[i+1] = b[j]+a+1i4storeload+bj 4IRt1 = j*4t2 = b+t1t3 = *t2t4 = i+1t5 = t4*4t6 = a+t5*t6 = t38CS 671 – Spring 2008TilesIdea: a tile is contiguous piece of the tree that correponds to a machine instruction+a+1i4storeload+bj 4IRt1 = j*4t2 = b+t1t3 = *t2t4 = i+1t5 = t4*4t6 = a+t5*t6 = t3movem rb, ra9CS 671 – Spring 2008TilingTiling: cover the tree with tiles+a+1i4storeload+bj 4Assemblymuli 4, rjadd rj, rbaddi 1, rimuli 4, riadd ri, ramovem rb, ra10CS 671 – Spring 2008Tiling+a+1i4storeload+bj 4+a+1i4storeload+bj 4load rb, r1store r1, ramovex rj, rb, ra11CS 671 – Spring 2008TilingWhat’s hard about this?•Define system of tiles in the compiler•Finding a tiling that implements the tree (Covers all nodes in the tree)•Finding a “good” tilingDifferent approaches•Ad-hoc pattern matching•Automated toolsTo guarantee every tree can be tiled, provide a tile for each individual kind of node+t1t2mov t1, t3add t2, t312CS 671 – Spring 2008AlgorithmsGoal: find a tiling with the fewest tilesAd-hoc top-down algorithm•Start at top of the tree•Find largest tile matches top node•Tile remaining subtrees recursivelyTile(n) { if ((op(n) == PLUS) && (left(n).isConst())) { Code c = Tile(right(n)); c.append(ADDI left(n) right(n)) }}13CS 671 – Spring 2008Ad-Hoc AlgorithmProblem: what does tile size mean?•Not necessarily the best fastest code (Example: multiply vs add)•How to include cost?Idea:•Total cost of a tiling is sum of costs of each tileGoal: find a minimum cost tiling14CS 671 – Spring 2008Including CostAlgorithm:•For each node, find minimum total cost tiling for that node and the subtrees belowKey:•Once we have a minimum cost for subtree, can find minimum cost tiling for a node by trying out all possible tiles matching the nodeUse dynamic programming15CS 671 – Spring 2008Dynamic ProgrammingIdea•For problems with optimal substructure•Compute optimal solutions to sub-problems•Combine into an optimal overall solutionHow does this help?•Use memoization: Save previously computed solutions to sub-problems•Sub-problems recur many times•Can work top-down or bottom-up16CS 671 – Spring 2008Recursive AlgorithmMemoization•For each subtree, record best tiling in a table•(Note: need a quick way to find out if we’ve seen a subtree before – some systems use DAGs instead of trees)At each node•First check table for optimal tiling for this node•If none, try all possible tiles, remember lowest cost•Record lowest cost tile in table•Greedy, top-down algorithmWe can emit code from table17CS 671 – Spring 2008PseudocodeTile(n) { if (best(n)) return best(n) // -- Check all tiles if ((op(n) == STORE) && (op(right(n)) == LOAD) && (op(child(right(n)) == PLUS)) { Code c = Tile(left(n)) c.add(Tile(left(child(right(n))) c.add(Tile(right(child(right(n))) c.append(MOVEX . . .) if (cost(c) < cost(best(n)) best(n) = c } // . . . and all other tiles . . . return best(n)}+a+1i4storeload+bj 418CS 671 – Spring 2008Ad-Hoc AlgorithmProblem:•Hard-codes the tiles in the code generatorAlternative:•Define tiles in a separate specification•Use a generic tree pattern matching algorithm to compute tiling•Tools: code generator generators19CS 671 – Spring 2008Code Generator GeneratorsTree description language•Represent IR tree as textSpecification•IR tree patterns•Code generation actionsGenerator•Takes the specification•Produces a code generatorProvides linear time optimal code generation•BURS (bottom-up rewrite system)•burg, Twig, BEG20CS 671 – Spring 2008Tree NotationUse prefix notation to avoid confusion+a+1i4storeload+bj 4(j, 4)+(b, (j, 4))load(+(b, (j, 4)))+(i,1)(+(i,1),4)+(a,(+(i,1),4))store(+(a,(+(i,1),4)),load(+(b, (j, 4))))21CS 671 – Spring 2008Rewrite RulesRule•Pattern to match and replacement•Cost•Code generation template•May include actions – e.g., generate register namePattern, replacement Cost Template+(reg1,reg2) → reg21 add r1, r2store(reg1, load(reg2)) → done5 movem r2, r122CS 671 – Spring 2008Rewrite RulesExample rules:# Pattern, replacement Cost Template1 +(reg1,reg2) → reg21add r1, r22