1CS553 Lecture Register Allocation III 2Register Allocation IIIAnnouncements– Recommend have interference graph construction working by MondayLast lecture– Register allocation across function calls Today– Register allocation optionsCS553 Lecture Register Allocation III 3Interference Graph AllocatorsChaitinBriggsCS553 Lecture Register Allocation III 4Granularity of Allocation (Renumber step in Briggs) What is allocated to registers?– Variables/Temporaries– Live ranges/Webs (i.e., du-chains with common uses)– Values (i.e., definitions; same as variables with SSA)t1: x := 5t2: y := xt3: x := y+1t4: ... x ...t5: x := 3t6: ... x ...Variables: 2 (x & y)Live Ranges/Web: 3 (t1→t2,t4; t2 → t3; t3,t5 → t6)Values: 4 (t1, t2, t3, t5, φ (t3,t5))Each allocation unit is given a symbolic register name (e.g., s1, s2, etc.)b1b4b2b3What are the tradeoffs?CS553 Lecture Register Allocation III 5Computing the Interference Graph (in MiniJava compiler) Use results of live variable analysisfor each flow graph node n dofor each def in def(n) dofor each temp in liveout(n) doif ( not stmt(n) isa MOVE or def != temp ) thenE ← E ∪ (def, temp)2CS553 Lecture Register Allocation III 6Coalescing Move instructions– Code generation can produce unnecessary move instructions mov t1, t2– If we can assign t1 and t2 to the same register, we can eliminate the move Idea– If t1 and t2 are not connected in the interference graph, coalesce them intoa single variable Problem– Coalescing can increase the number of edges and make a graph uncolorable– Limit coalescing to avoid uncolorable graphst1 t2 t1t2coalesceCS553 Lecture Register Allocation III 7Coalescing Logistics Rule– When building the interference graph, do NOT make virtual registersinterfere due to copies.– If the virtual registers s1 and s2 do not interfere and there is a copystatement s1 = s2 then s1 and s2 can be coalesced.– ExampleCS553 Lecture Register Allocation III 8Coalescing in MiniJava compiler Currently the InterferenceGraph only has one Temp.Temp associatedwith each node– represent each merged node with just one of the temps– keep a separate map of representatives mapped to sets of temps– also keep a map of temps mapped to their representative– when rewriting the code use the representative instead of the original tempCS553 Lecture Register Allocation III 9Register Allocation: Spilling If we can’t find a k-coloring of the interference graph– Spill variables (nodes) until the graph is colorable Choosing variables to spill– Choose least frequently accessed variables– Break ties by choosing nodes with the most conflicts in the interferencegraph– Yes, these are heuristics!3CS553 Lecture Register Allocation III 10Weighted Interference Graph Goal– Weight(s) = f(r) is execution frequency of r Static approximation– Use some reasonable scheme to rank variables– One possibility– Weight(s) = 1– Nodes after branch: ½ weight of branch– Nodes in loop: 10 × weight of nodes outside loop!" srrf of references )(CS553 Lecture Register Allocation III 11Improvement #1: Simplification Phase [Chaitin 81] Idea– Nodes with < k neighbors are guaranteed colorable– Improvement over simple greedy coloring algorithm Remove them from the graph first– Reduces the degree of the remaining nodes Must spill only when all remaining nodes have degree ≥ kReferred to as pessimistic spillingCS553 Lecture Register Allocation III 12 Clearly 2-colorable− But Chaitin’s algorithm leads to an immediate block and spill− The algorithm assumes the worst case, namely, that all neighbors willbe assigned a different colorThe Problem: Worst Case Assumptions Is the following graph 2-colorable?s1s2s4s3CS553 Lecture Register Allocation III 13DeferdecisionImprovement #2: Optimistic Spilling [Briggs 89] Idea– Some neighbors might get the same color– Nodes with k neighbors might be colorable– Blocking does not imply that spilling is necessary– Push blocked nodes on stack (rather than place inspill set)– Check colorability upon popping the stack, whenmore information is availables1s2s4s34CS553 Lecture Register Allocation III 14Algorithm [Briggs et al. 89]while interference graph not empty dowhile ∃ a node n with < k neighbors doRemove n from the graphPush n on a stackif any nodes remain in the graph then { blocked with >= k edges }Pick a node n to spill { lowest spill-cost/highest degree}Push n on stackRemove n from the graphwhile stack not empty doPop node n from stackif n is colorable thenAllocate n to a registerelseInsert spill code for n { Store after def; load before use }Reconstruct interference graph & start oversimplifydefer decisionmake decisionCS553 Lecture Register Allocation III 15Stack:dcb*f*a*e*ExamplebadcfeWeighted order: e a f b c dAttempt to 2-color this graph ( , )* blocked nodeCS553 Lecture Register Allocation III 16Possible Register Allocation Design Overall algorithm: graph coloring with simplification Interference graph: two temps interfere if– one is defined in a stmt and the other is live out of the same stmt– exception is a MOVE statement where the temps are the source and dest Coalesce: Briggs strategy– coalesce if new node will have fewer than K neighbors of significantdegree (>= K) Spill heuristic:– spill the node with the lowest weight and break ties by spilling the nodewith the most adjacent edges Simplification: optimistic Select:– pop everything off the stack before generating spill codeCS553 Lecture Register Allocation III 18Improvement #3: Live Range Splitting [Chow & Hennessy 84] Idea– Start with variables as our allocation unit– When a variable can’t be allocated, split it into multiple subranges forseparate allocation– Selective spilling: put some subranges in registers, some in memory– Insert memory operations at boundaries Why is this a good idea?5CS553 Lecture Register Allocation III 19Improvement #4: Rematerialization [Chaitin 82]&[Briggs 84] Idea– Selectively re-compute values rather than loading from memory– “Reverse CSE” Easy case– Value can be computed in single instruction, and– All operands are available Examples– Constants– Addresses of global variables– Addresses of local variables (on stack)CS553 Lecture Register Allocation III 20Next Time Lecture– Instruction