Chapter 11
Register Allocation

Drawings used with permission from:

David MacQueen
Computer Science Department
University of Chicago
1100 E. 58th Street
Chicago, IL 60637
USA

Email: dbm@cs.uchicago.edu

REVIEW

Chapter 10

• Have not yet targeted an architecture.
• Have generated TEMP as needed.
• Goal is to determine fewest TEMPs necessary by eliminating and reusing where possible.
• live - a variable that holds a value that may be needed in the future.
• Discovering live variables is liveness analysis
• Control-flow graph used in analysis, such graphs consist of nodes and directed edges
  • nodes - statements of program
  • edges - if statement x can be followed by statement y there is an edge from x to y.
• Produce interference-graph of TEMP nodes and edges between TEMPs that cannot be assigned to same register.

OVERVIEW

Chapter 11

• Interference-graph from Chapter 10 contains nodes representing a TEMP; edges (t1,t2) represent TEMP pair that cannot be assigned to same register.
• Coloring the interference-graph, where a color corresponds to a real register and no connected TEMPs share the same color, produces a valid register assignment.
• Spilling occurs when too few colors (registers) exist and additional colors are assigned from memory.

Coloring a Graph
 

Interference graph (nodes are temps)	three colors three registers
	adjacent nodes should have different colors

 

11.1 COLORING BY SIMPLIFICATION

NP-complete - Polynomial time algorithms are O(n^k) for n inputs and fixed k. No polynomial time algorithms are known for any NP-complete problem.

Linear-time approximation algorithm - Key phases

• Build - interference-graph of TEMP nodes and edges between TEMPs that cannot be assigned to same register.

• Simplify - use simple heuristic.

  For graph G and K colors

  1. find node m with less than K neighbors, out degree(m) < K
  2. G' = G - {m} obtained by removing m node from G
  3. If G' can be colored so can G; since m has at most K-1 neighbors at least one color remains
  4. Removing m reduces the degree of each neighbor of m, leading to more possible simplifications
  5. Push m onto stack for later coloring
  6. Continue until G' is empty or only insignificant nodes (i.e. out degree(m) < K) remain

1. Remove nodes of insignificant degree (degree < 3 for 3 colors)	2. Remove nodes of low degree (insignificant nodes)	3. Remaining nodes all insignificant and can therefore be colored
4. Add 2nd phase insignificants and color them	5. Add 1st phase insignificants and color them

• Spill - when only nodes of significant degree (i.e. nodes of degree ³ K) remain, simplification heuristic fails and must mark some node for assignment to memory, not a register.

Optimistically, spilling the node will not interfere with other nodes remaining in graph and can be pushed onto stack, continuing simplification.

1. No insignificant nodes after first phase	2. Choose this node as a candidate for spilling and remove it.
3. After coloring remainder, try to color spill candidate. If not possible, then spill it to memory.

• Select - starting with empty graph, assign of colors to nodes in the graph.
  • pop node and assign color not already assigned to a neighbor; a color must exist given that degree < K during simplification
  • may not be able to assign a color for a spilled node when popped
    • cannot if neighbors use K colors, must assign to memory (an actual spill)
    • can if some neighbors use same color so that less than K colors used by neighbors
       
• Start over - rewrite program and rerun simplification until it succeeds
  • actual spills during Select phase require that a TEMP be fetched from memory to a register for a time
  • creates a new interference with TEMP assigned that register (color).
  • rewrite program to remove interference by creating new TEMPs with small live ranges.
  • repeat simplification

Example - 4-color

Live-in interval g h f e m b c d k j live-in: k j                 | | g=mem[j+12] |               | | h=k-1 | |               | f=g*h     |             | e=mem[j+8]     | |           | m=mem[j+16]     | | |           b=mem[f]       | | |         c=e+8         | | |       d=c         | |   |     k=m+4           |   | |   j=b               | | | live-out: d k j
k h g ____ Stack

Exercise - Color the following map of Australia using 3 colors, red, green and blue.

Exercise - Try coloring the following with 4, then 3, then 2 colors.

IR MOVE(a,CONST(1)) MOVE(b,CONST(2)) MOVE(c,CONST(3)) MOVE(c,BINOP(BINOP.PLUS,a,BINOP(BINOP.PLUS,b,c)))	Interference Graph        t2 ___ t3       /   \     /      /     \   /  t35____t1             /  \  t36   t37  t34  t33
Assem 0. OPER[li `d0 1][t33 ][][] 1. MOVE[ move `d0 `s0][t1][t33] 2. OPER[li `d0 2][t34 ][][] 3. MOVE[ move `d0 `s0][t2][t34] 4. OPER[li `d0 3][t35 ][][] 5. MOVE[ move `d0 `s0][t3][t35] 6. OPER[add `d0 `s0 `s1][t37 ][t2 t3 ][] 7. OPER[add `d0 `s0 `s1][t36 ][t1 t37 ][] 8. MOVE[ move `d0 `s0][t3][t36]	Flowgraph                   0: t33 <- ; goto 1         1: t1 <= t33 ; goto 2 2: t34 <- ; goto 3 3: t2 <= t34 ; goto 4 4: t35 <- ; goto 5 5: t3 <= t35 ; goto 6 6: t37 <- t2 t3 ; goto 7 7: t36 <- t1 t37 ; goto 8 8: t3 <= t36 ; goto
Live Interval t35 [4,4] t33 [0,0] t36 [7,7] t1 [1,6] t2 [3,5] t3 [5,5] t37 [6,6] t34 [2,2]	Interference Graph t33: t33 t1: t37 t3 t35 t2 t34 t1 t34: t34 t1 t2: t3 t35 t2 t1 t35: t2 t1 t35 t3: t3 t2 t1 t37: t37 t1 t36: t36

Example - Spill and Start Over

Spilling

If we need to spill temp t:

1. rewrite the code to incorporate the spilling of t:
   1. at each node defining t, replace t with a new temp t’ and follow that node with a store: M[fp+n] := t’ (where n is a new frame slot offset)
   2. at each node using t, replace t with a new temp t’’ and precede that node with a load: t’’ := M[fp+n]

      Note that t’ and t’’ will be live-out for only one instruction.

2. redo liveness analysis, construction of interference graph, and coloring using the rewritten code.

Repeat until no nodes are spilled; all have been rewritten with live-out intervals of length one.

Example - Spill and Rewrite

Spill c=3 a=1 M[0]=a+c d=4 b=2 M[1]=c M[2]=d+b M[3]=a M[4]=b	Rewrite c=3 a1=1                      ; t' M[fp+n]=a1 a2=M[fp+n]            ; t" M[0]=a2+c d=4 b=2 M[1]=c M[2]=d+b a3=M[fp+n]            ;t" M[3]=a3 M[4]=b
Spill with Multiple Uses - 4 colors required	Spill and Rewrite - 3 colors used

Which Temp to Spill?

• Spill the least used temp: minimizes runtime cost of spills (number of loads and stores)
  • statically least used (fewest occurrences in the code)
  • dynamically least used (weight occurrences in loops higher)
• Spill the temp with the most interferences (largest number of adjacent nodes in interference graph)
  • this removes the most edges, decreasing likelihood of further spills
• Spill a temp that hasn’t been spilled before (?)
  • but rewriting replaces spilled temps with new ones!?
     

11.2 COALESCING

Coalescing - combining nodes (registers) that do not interfere into one node (register), forming the union of the edges of the nodes being combined.

MOVEs - can be eliminated and nodes combined when there is no interference edge between source and destination. Dotted edge (r3, c) is a MOVE and may be possible to coalesce as single color (register) since implies r3=c.

Others - can be combined when not connected by an interference edge - however, combining nodes in a K-colorable graph may result in a graph that is not K-colorable. Combined nodes result in a union of interference nodes. r3 and d may be coalesced but r3d node would interfere with the union of the interference nodes for d and r3, making r3d more difficult to color.

Safe strategies - coalescing strategies that do not render a graph uncolorable; the following are safe:

• Briggs - nodes a and b can be coalesced if the resulting node ab will have fewer than K neighbors of significant degree (i.e. having ³ K edges). A K-colorable graph cannot then be turned into a non-K-colorable.
   
• George - nodes a and b can be coalesced if, for every neighbor t of a, either t already interferes with b or t is of insignificant degree. Coalescing is safe by:
  • Let S be the set of insignificant-degree neighbors of a in original graph.
  • If coalescing is not done, simplify could remove all nodes in S leaving a reduced graph G₁.
  • If coalescing is done, simplify could remove all nodes in S leaving a reduced graph G₂.
  • G₂ is a sub-graph of G₁ (the node ab in G₂ corresponds to the node b in G₁) and is at least as colorable.

Conservative strategies - some safe situations may not be coalesced leaving unnecessary MOVEs between registers but better than spilling to memory.

FREEZING - If neither simplify or coalesce possible, freeze the MOVEs in which a low degree node is involved (e.g. freeze MOVE (a,e)) making it an interference edge. Hope that allows further simplification to be performed.

 

Linear-time approximation algorithm with Coalescing - Key phases

• Build - interference-graph of TEMP nodes and edges between TEMPs that cannot be assigned to same register.

• Simplify - use simple heuristic.

  For graph G and K colors

  1. find node m with less than K neighbors, out degree(m) < K
  2. G' = G - {m} obtained by removing m node from G
  3. If G' can be colored so can G; since m has at most K-1 neighbors at least one color remains
  4. Removing m reduces the degree of each neighbor of m, leading to more possible simplifications
  5. Push m onto stack for later coloring
  6. Continue until G' is empty or only insignificant nodes (i.e. out degree(m) < K) remain
      
• Coalesce - perform conservative coalescing on nodes remaining after simplify. After coalescing repeat simplification.
   
• Freeze - If neither simplify or coalesce possible, freeze the MOVEs in which a low degree node is involved making it an interference edge. Resume simplify.

• Spill - when only nodes of significant degree (i.e. nodes of degree ³ K) remain, simplification heuristic fails and must mark some node for assignment to memory, not a register.

Optimistically, spilling the node will not interfere with other nodes remaining in graph and can be pushed onto stack, continuing simplification.

• Select - starting with empty graph, assign of colors to nodes in the graph.
  • pop node and assign color not already assigned to a neighbor; a color must exist given that degree < K during simplification
  • may not be able to assign a color for a spilled node when popped
    • cannot if neighbors use K colors, must assign to memory (an actual spill)
    • can if some neighbors use same color so that less than K colors used by neighbors
       
• Start over - rewrite program and rerun simplification until it succeeds
  • actual spills during Select phase require that a TEMP be fetched from memory to a register for a time
  • creates a new interference with TEMP assigned that register (color).
  • rewrite program to remove interference by creating new TEMPs with small live ranges.
  • repeat simplification

Example

Coalescing Moves with 4 colors

Example - 4 colors j, b, c, d are MOVE-related nodes. Initial work-list in simplify phase must contain only non-MOVE nodes. GRAPH 11.5 after removal of h, g, k GRAPH 11.5(a) coalesce c and d GRAPH 11.5(b) coalesce b and j simplify GRAPH 11.5(b) by removing f, m, e FIGURE 11.6 after coloring Note coalesced nodes are same color (register)
Constrained - MOVEs that are not considered for coalescing when separate interference edge between the source and destination. Example Before coalescing After coalescing xy MOVE y, z not considered for coalescing due to edge (xy,z)

11.3 PRECOLORED NODES

• Nodes that are preassigned colors (registers)
  • frame pointer
  • standard procedure arguments
  • procedure return results
  • zero
• Cannot simplify since must be a register (i.e. register r3 must be register r3)
• Cannot spill
• K-register machine has K precolored interfering nodes.
• A register used explicitly has a live range that interferes with any other variables simultaneously live

TEMPORARY COPIES OF MACHINE REGISTERS

• Coloring algorithm - stops simplify, coalesce, spill when only precolored registers remain
• Short ranges - precolored nodes do not spill, ranges must be short for use by TEMPs

  Example Callee save - create short live range of callee save/restore register by copying to temporary on entry, back from temporary on exit. Note that the  MOVE between temporary below may be coalesced.

  enter: def r7     :     : exit:   use r7

  enter: def r7    t231¬r7       :     :    r7¬t231 exit:   use r7

CALLER-SAVE AND CALLEE-SAVE REGISTERS

1. allocate to caller-save register local variables or temporaries not live across procedures since no saving or restoring necessary
2. allocate to callee-save register local variables or temporaries live across procedures since one save/restore on entry/exit of calling procedure

Graph-coloring with caller/callee-save register using above example and strategy

• callee-save registers live on procedure entry; used at procedure return
• CALL of Assem defined to interfere with all caller-save registers
• variable not live across procedure call tends to be allocated to caller-save register
• variable live across procedure call interferes with all caller-save registers and all new temporaries guaranteeing a spill will occur
• callee saves callee-save register by spilling
• heuristic of spilling high-degree but low uses ensures callee-save/restore temporary (e.g. t₂₃₁ above) spilled
• spilling t₂₃₁ frees  r₇ for coloring some variable of lower degree and higher uses

Example

r1	r2	r3	c	d	a	b	e	Interference intervals
|	|	|						enter:   c¬r3               (TEMP c for callee-save r3)
|	|		|					a¬r1
	|		|		|			b¬r2
			|		|	|		d¬0
			|	|	|	|		e¬a
			|	|		|	|	loop:     d¬d+b
			|	|		|	|	e¬e-1
			|	|		|	|	if e > 0 goto loop
			|	|				r1¬d
|			|					r3¬c
|		|					|	return              (r1, r3 live-out)

Interference graph Correction: should have (c,r1) edge. Does not change the coloring result.

George: c1&r3 - every node c1 interferes with so does r3

Safe strategies - coalescing strategies that do not render a graph uncolorable; the following are safe:

• Briggs - nodes a and b can be coalesced if the resulting node ab will have fewer than K neighbors of significant degree (i.e. having ³ K edges). A K-colorable graph cannot then be turned into a non-K-colorable.
   
• George - nodes a and b can be coalesced if, for every neighbor t of a, either t already interferes with b or t is of insignificant degree. Coalescing is safe by:
  • Let S be the set of insignificant-degree neighbors of a in original graph.
  • If coalescing is not done, simplify could remove all nodes in S leaving a reduced graph G₁.
  • If coalescing is done, simplify could remove all nodes in S leaving a reduced graph G₂.
  • G₂ is a sub-graph of G₁ (the node ab in G₂ corresponds to the node b in G₁) and is at least as colorable.

11.5 REGISTER ALLOCATION FOR TREES

Expression trees - can allocate registers directly from IR Simpler - no need for dataflow or interference graph IR tree at right has two trivial register assignments - rfp and ri Each tile requires 1 register for result. Assignment (side-effects or memory) only at root, not at internal nodes. SimpleAlloc allocates registers to tiles (n is number of register allocated, initially 0):              9¬r1               /        \      6¬r1           8¬r2      /      \ 2¬r1    5¬r2                |             4¬r2 Not optimal - recall stack size calculation from Homework 8, optimal solution performs maximum need first. Tiling left child need < right child need first will require more registers Should first tile and allocate registers to child with greatest need (a) needs 3 while (b) needs 4 registers         (a)                      (b)        /   \                      /  \       3    2                    2   3

ALGORITHM 11.10 labels each tile with number of registers needed to evaluate subtree does not assign registers can be combined with MaximalMunch 2 passes now required identify tile and label with need of each tile emit subtrees in decreasing need when more than 1 child ALGORITHM 11.11 assigns registers and handles spills pre-pass using ALGORITHM 11.10 handles internal nodes of expression trees - does not handle nodes with side-effects explicit TEMPs must be handled some other way such as stack frame

NOTE OPER(instruction, reg[t], [reg[uleft],reg[uright]])

Example

+      /  \     a    *             /  \         b    -             /  \            c    d

t1¬ M[a]    t2¬ M[b]    t3¬ M[c]    t4¬ M[d]    t5¬ t3-t4    t6¬ t2*t5    t7¬ t1+t6

ALGORITHM 11.9 SimpleAlloc (requires 4 registers)

r1¬ M[a]    r2¬ M[b]    r3¬ M[c]    r4¬ M[d]    r3¬ r3-r4    r2¬ r2*r3    t1¬ r1+r2

 

ALGORITHM 11.10 and 11.11 (requires 2 registers) Need   2    +        /  \   1  a    *  2            /  \      1  b    -  2               /  \          1  c    d  1   Allocation    r1¬ M[c]    r2¬ M[d]    r1¬ r1-r2    r2¬ M[b]    r1¬ r2*r1    r2¬ M[a]    r1¬ r1+r2 Evaluation        + r1       /  \   r2 a  * r1          /   \      r2 b    - r1               /  \            r1 c  r2 d

 

Another labeling algorithm

Example - an allocation algorithm given an tree labeled with register need, does not handle spills. Start at root node of tree with gencode( t4 ). The code is for: a+b-(e-(c+d))

REG = current register number (initialized to 1) void gencode(n)  if n is leaf "name"    /* case 0 - just load it */    emit(load, REG, name);  else    if n is interior node "op n1 n2"      if label(n1) >= label(n2) {       /* case 1 - generate left child first */      gencode(n1); REG = REG+1;      gencode(n2); REG = REG-1;      emit(op, REG, REG, REG+1);     }     else label(n1) < label(n2) {       /* case 2 - generate right child first */      gencode(n2); REG = REG+1;      gencode(n1); REG = REG-1;      emit(op, REG, REG+1, REG);    }