MIT 33 Register Allocation (slides)

CS412/CS413Introduction to CompilersTim TeitelbaumLecture 33: Register Allocation14 Apr 08CS 412/413 Spring 2008Introduction to Compilers1Variables vs. Registers/Memory• Difference between IR and assembly code:– IR (and abstract assembly) manipulate data in localand temporary variables– Assembly code manipulates data in memory/registers• During code generation, compiler must accountfor this difference• Compiler backend must allocate variables tomemory or registers in the generated assemblycodeCS 412/413 Spring 2008Introduction to Compilers2Simple Approach• Straightforward solution:– Allocate each variable in activation record– At each instruction, bring values needed intoregisters, perform operation, then store result tomemoryxx == yy ++ zzmovmov 16(%ebp),16(%ebp), %eax%eaxmovmov 20(%ebp),20(%ebp), %ebx%ebxaddadd %ebx,%ebx, %eax%eaxmovmov %eax,%eax, 24(%ebx)24(%ebx)• Problem: program execution very inefficient– moving data back and forth between memory andregistersCS 412/413 Spring 2008Introduction to Compilers3Register Allocation• Better approach = register allocation: keep variablevalues in registers as long as possible• Best case: keep a variable’s value in a registerthroughout the lifetime of that variable––––In that case, we don’t need to ever store it in memoryWe say that the variable has been allocated in a registerOtherwise allocate variable in activation recordWe say that variable is spilled to memory• Which variables can we allocate in registers?– Depends on the number of registers in the machine– Depends on how variables are being used• Main Idea: cannot allocate two variables to the sameregister if they are both live at some program pointCS 412/413 Spring 2008Introduction to Compilers4Register Allocation AlgorithmHence, basic algorithm for register allocation is:1.

Perform live variable analysis (over abstractassembly code!)2. Inspect live variables at each program point3. If two variables are ever in same live set, theycan’t be allocated to the same register – theyinterfere with each other4. Conversely, if two variables do not interferewith each other, they can be assigned thesame register. We say they have disjoint liveranges.CS 412/413 Spring 2008Introduction to Compilers5Interference Graph• Nodes = program variables• Edges = connect variables thatinterfere with each other{a}b = a + 2;{a,b}c = b*b;{a,c}b = c + 1;{a,b}return b*a;• Register allocation = graph coloringaeaxebxCS 412/413 Spring 2008bIntroduction to Compilersc6Graph Coloring• Questions:– Can we efficiently find a coloring of the graphwhenever possible?– Can we efficiently find the optimum coloringof the graph?– Can we assign registers to avoid moveinstructions?– What do we do when there aren’t enoughcolors (registers) to color the graph?CS 412/413 Spring 2008Introduction to Compilers7Coloring a Graph• Let K = number of registers (e.g., take K=3)• Try to color graph with K colors• Key operation = Simplify: find some node with at mostK-1 edges and cut it out of the graphCS 412/413 Spring 2008Introduction to Compilers8Coloring a Graph• Idea: once coloring is found for simplified graph,removed node can be colored using free color• Algorithm: simplify until graph contain no nodes• Add nodes back & assign colorsCS 412/413 Spring 2008Introduction to Compilers9Stack Algorithm• Phase 1: Simplification– Repeatedly simplify graph– When a variable (i.e., graphnode) is removed, push it on astacksimplifysimplify• Phase 2: Coloring– Unwind stack and reconstructthe graph as follows:– Pop variable from the stack– Add it back to the graph– Color the node for that variablewith a color that it doesn’tinterfere withCS 412/413 Spring 2008Introduction to Compilerscolorcolor10Stack Algorithma• Example:bcda• …how about:cbdefCS 412/413 Spring 2008Introduction to Compilers11Failure of Heuristic• If graph cannot be colored, it will reduce to a graph inwhich every node has at least K neighbors?• May happen even if graph is colorable in K!• Finding K-coloring is NP-hard problem (requires search)CS 412/413 Spring 2008Introduction to Compilers12Spilling• Once all nodes have K or more neighbors, pick a nodeand mark it for possible spilling (storage in activationrecord).• Remove it from graph, push it on stack• Try to pick node not used much, not in inner loopxCS 412/413 Spring 2008Introduction to Compilers13Optimistic Coloring• Spilled node may be K-colorable• Try to color it when popping the stackx• If not colorable, actual spill: assign it a location in theactivation recordCS 412/413 Spring 2008Introduction to Compilers14Accessing Spilled Variables• Need to generate additional instructions to getspilled variables out of activation record andback in again• Simple approach: always reserve extra registershandy for shuttling data in and out• Better approach: rewrite code introducing anew temporary, rerun liveness analysis andregister allocationCS 412/413 Spring 2008Introduction to Compilers15Rewriting Code• Example: add v1, v2• Suppose that v2 is selected for spilling and assigned toactivation record location [ebp-24]• Add new variable (say t35) for just this instruction,rewrite:mov –24(%ebp), t35add v1, t35Advantage: t35 has short lifetime and doesn’t interferewith other variables as much as v2 did.• Now rerun algorithm; fewer or no variables will spill.CS 412/413 Spring 2008Introduction to Compilers16Putting Pieces TogetherSimplifySimplifySimplificationPotential SpillSpillPotentialOptimistic coloringcoloringOptimisticColoringActual SpillSpillActualCS 412/413 Spring 2008Introduction to Compilers17Precolored Nodes• Some variables are pre-assigned to registers– mul instruction hasuse[I] = eax, def[I] = { eax, edx }– result of function call returned in eax• To properly allocate registers, treat these register usesas special temporary variables and enter intointerference graph as precolored nodesCS 412/413 Spring 2008Introduction to Compilers18Precolored Nodes• Simplify.

Never remove a pre-colored node --it already has a color, i.e., it is a givenregister• Coloring. Once simplified graph is all colorednodes, add other nodes back in and colorthem using precolored nodes as starting pointCS 412/413 Spring 2008Introduction to Compilers19Optimizing Move Instructions• Code generation produces a lot of extra movinstructionsmov t5, t9• If we can assign t5 and t9 to same register, we can getrid of the mov --- effectively, copy elimination at theregister allocation level.• Idea: if t5 and t9 are not connected in inference graph,coalesce them into a single variable; the move will beredundant.CS 412/413 Spring 2008Introduction to Compilers20Coalescing• When coalescing nodes, take union of edges• Hence, coalescing results in high-degree nodes• Problem: coalescing nodes can make a graph uncolorablet5CS 412/413 Spring 2008t9t5/t9Introduction to Compilers21Conservative Coalescing• Conservative = ensure that coalescing doesn’t make thegraph non-colorable (if it was colorable before)• Coalesce a and b only if resulting node a/b has fewerthan K neighbors of significant degree ( )– Safe because we can simplify graph by removing neighbors withinsignificant degree ( ), then remove coalesced node and getthe same graph as beforeaCS 412/413 Spring 2008ba/bIntroduction to Compilers22Conservative Coalescing• Conservative = ensure that coalescing doesn’t make thegraph non-colorable (if it was colorable before)• Coalesce a and b if resulting node a/b has fewer than Kneighbors of significant degree()– Safe because we can simplify graph by removing neighbors withinsignificant degree ( ), then remove coalesced node and getthe same graph as beforeaCS 412/413 Spring 2008ba/bIntroduction to Compilers23Conservative Coalescing• Conservative = ensure that coalescing doesn’t make thegraph non-colorable (if it was colorable before)• Coalesce a and b if resulting node a/b has fewer than Kneighbors of significant degree()– Safe because we can simplify graph by removing neighbors withinsignificant degree ( ), then remove coalesced node and getthe same graph as beforeCS 412/413 Spring 2008Introduction to Compilers24Conservative Coalescing• Conservative = ensure that coalescing doesn’t make thegraph non-colorable (if it was colorable before)• Alternative approach: coalesce a and b if for everyneighbor t of a: either t already interferes with b; or thas insignificant degree– Safe because removing insignificant neighbors with coalescingyields a subgraph of the graph obtained by removing thoseneighbors without coalescingaCS 412/413 Spring 2008ba/bIntroduction to Compilers25Conservative Coalescing• Conservative = ensure that coalescing doesn’t make thegraph non-colorable (if it was colorable before)• Alternative approach: coalesce a and b if for everyneighbor t of a: either t already interferes with b; or thas insignificant degree– Safe because removing insignificant neighbors with coalescingyields a subgraph of the graph obtained by removing thoseneighbors without coalescingaCS 412/413 Spring 2008ba/bIntroduction to Compilers26Simplification + Coalescing• Consider M = set of move-related nodes (which appear inthe source or destination of a move instruction) and N = allother variables• Start by simplifying as many nodes as possible from N• Coalesce some pairs of move-related nodes usingconservative coalescing; delete corresponding movinstruction(s)• Coalescing gives more opportunities for simplification:coalesced nodes may be simplified• If can neither simplify nor coalesce, take a node f in M andfreeze all the move instructions involving that variable; i.e.,change all f-related nodes from M to N; go back to simplify.• If all nodes frozen, no simplify possible, spill a variableCS 412/413 Spring 2008Introduction to Compilers27Full AlgorithmSimplifySimplifyCoalesceCoalesceSimplificationFreezeFreezePotential SpillSpillPotentialOptimistic coloringcoloringOptimisticColoringActual SpillSpillActualCS 412/413 Spring 2008Introduction to Compilers28Overall Code Generation Process• Start with low-level IR code• Build DAG of the computation– Access global variables using static addresses– Access function arguments using frame pointer– Assume all local variables and temporaries are in registers(assume unbounded number of registers)• Generate abstract assembly code– Perform tiling of DAG• Register allocation– Live variable analysis over abstract assembly code– Assign registers and generate assembly codeCS 412/413 Spring 2008Introduction to Compilers29ExampleLow IRProgramt1t1 == x+ix+it1t1 == t1*4t1*4t1t1 == $a+t1$a+t1t2t2 == *t1*t1t2t2 == t2+1t2+1t3t3 == x+ix+it3t3 == t3*4t3*4t3t3 == $a+t3$a+t3*t3*t3 == t2t2array[int]array[int] aafunctionfunction f:(intf:(int x)x) {{intint i;i;……a[x+i]a[x+i] == a[x+i]a[x+i] ++ 1;1;……}}CS 412/413 Spring 2008Introduction to Compilers30Accesses to Function Argumentst4t4==ebp+8ebp+8t5t5==*t4*t4t1t1==t5+it5+it1t1==t1*4t1*4t1t1==$a+t1$a+t1t2t2==*t1*t1t2t2==t2+1t2+1t6=ebp+8t6=ebp+8t7t7==*t6*t6t3t3==t7+it7+it3t3==t3*4t3*4t3t3==$a+t3$a+t3*t3*t3==t2t2t1t1 == x+ix+it1t1 == t1*4t1*4t1t1 == $a+t1$a+t1t2t2 == *t1*t1t2t2 == t2+1t2+1t3t3 == x+ix+it3t3 == t3*4t3*4t3t3 == $a+t3$a+t3*t3*t3 == t2t2CS 412/413 Spring 2008Introduction to Compilers31DAG Constructiont4t4==ebp+8ebp+8t5t5==*t4*t4t1t1==t5+it5+it1t1==t1*4t1*4t1t1==$a+t1$a+t1t2t2==*t1*t1t2t2==t2+1t2+1t6=ebp+8t6=ebp+8t7t7==*t6*t6t3t3==t7+it7+it3t3==t3*4t3*4t3t3==$a+t3$a+t3*t3*t3==t2t2CS 412/413 Spring 2008store+load 1++i$a*4load+ebpIntroduction to Compilers832Tilingstore• Find tiles– Maximal Munch– Dynamic programming• Temporaries to transfervalues between tiles• No temporaries inside anyof the tiles+load 1+ r1r2 *$a+ r3 4i load+ebpCS 412/413 Spring 2008Introduction to Compilers833Abstract Assembly Generationstore+Abstract Assemblyload 1+ r1r2 *$a+ r3 4i loadmov $a, r1mov 8(%ebp), r3mov i, r2add r3, r2add $1, (r1,r2,4)+ebp8CS 412/413 Spring 2008Introduction to Compilers34Register AllocationAbstract AssemblyLive Variablesmovmov $a,$a, r1r1mov $a, r1mov 8(%ebp), r3mov i, r2add r3, r2add $1, (r1,r2,4){%ebp,{%ebp,i}i}{%ebp,r1,i}{%ebp,r1,i}movmov 8(%ebp),8(%ebp), r3r3movmov i,i, r2r2addadd r3,r3, r2r2{r1,{r1,r3,r3,i}i}{r1,r2,r3}{r1,r2,r3}{r1,r2}{r1,r2}addadd $1,$1, (r1,r2,4)(r1,r2,4){}{}CS 412/413 Spring 2008Introduction to Compilers35Register AllocationLive Variablesmovmov $a,$a, r1r1addadd r3,r3, r2r2{r1,{r1,r3,r3,i}i}{r1,r2,r3}{r1,r2,r3}{r1,r2}{r1,r2}addadd $1,$1, (r1,r2,4)(r1,r2,4)r3i{%ebp,r1,i}{%ebp,r1,i}movmov 8(%ebp),8(%ebp), r3r3movmov i,i, r2r2• Build interference graph{%ebp,{%ebp,i}i}%ebpr1r2• Allocate registers:eax: r1, ebx: r3i, r2 spilled to memory{}{}CS 412/413 Spring 2008Introduction to Compilers36Assembly Code GenerationAbstract Assemblymovmov $a,$a, r1r1movmov 8(%ebp),8(%ebp), r3r3movmov i,i, r2r2addadd r3,r3, r2r2addadd $1,$1, (r1,r2,4)(r1,r2,4)Assembly Codemovmov $a,$a, %eax%eaxmovmov 8(%ebp),8(%ebp), %ebx%ebxmovmov –12(%ebp),–12(%ebp), %ecx%ecxmovmov %ecx,%ecx, -16(%ebp)-16(%ebp)addadd %ebx,%ebx, -16(%ebp)-16(%ebp)movmov –16(%ebp),–16(%ebp), %ecx%ecxaddadd $1,$1, (%eax,%ecx,4)(%eax,%ecx,4)Register allocation results:eax: r1; ebx: r3; i, r2 spilled to memoryCS 412/413 Spring 2008Introduction to Compilers37Where We AreSource Program9OptimizedAssembly CodeCS 412/413 Spring 2008Introduction to Compilers38.