Graph coloring with precolored nodes

Supplement to the books,

This page explains register allocation using Iterated Register Coalescing in the presence of precolored nodes (temporary variables already assigned to machine registers).

The instruction-selection phase of a compiler may generate arbitrarily many temporary variables, which must then be assigned to a finite set of machine registers.

But some of the variables produced by instruction selection must be assigned to specific machine registers, because of standard parameter-passing conventions, or the use of special registers such as stack pointer or frame pointer. These variables are precolored before register allocation. For each machine register, there may be at most one node precolored with that color.

Precolored nodes should be considered to have infinite degree. Therefore, simplify, freeze, and spill cannot be performed on them. However, an ordinary (non-precolored) node may be coalesced with a precolored node.

Example

enter:
  c := 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]

The register allocation proceeds as follows (with K=3):

1. In this graph, there is no opportunity for simplify or freeze (because all the non-precolored nodes have degree greater than K). Any attempt to coalesce will produce a coalesced node adjacent to K or more high-degree nodes. Therefore we must spill some node. We calculate spill priorities as follows:

   Node		uses+defs outside loop		uses+defs within loop		degree		spill priority
   a:	(	2	+10*	0	) /	4	=	0.50
   b:	(	1	+10*	1	) /	4	=	2.75
   c:	(	2	+10*	0	) /	6	=	0.33
   d:	(	2	+10*	2	) /	4	=	5.50
   e:	(	1	+10*	3	) /	3	=	10.3

   Node c has the lowest priority--it inteferes with many other temporaries but is rarely used--so it should be spilled first.

   Spilling c, we obtain the graph,

   

2. We can now coalesce a and e, since the resulting node will be adjacent to fewer than K high-degree nodes (after coalescing, node d will be low-degree, though it is high-degree right now). No other simplify or coalesce is possible now. Coalescing a+e gives,

   

3. Now we could coalesce ae+r1 or coalesce b+r2. Let us do the latter:

   

4. We can now coalesce either ae+r1 or coalesce d+r1. Let us do the former:

   

5. We cannot now coalesce r1ae+d because the move is constrained: the nodes r1ae and d interfere. We must simplify d:

   

6. Now we have reached a graph with only precolored nodes, so we pop nodes from the stack and assign colors to them. First we pick d, which can be assigned color r3. Nodes a, b, e have already been assigned colors by coalescing. But node c, which was a potential spill, turns into an actual spill when it is popped from the stack, since no color can be found for it.
7. Since there was spilling in this round, we must rewrite the program to include spill instructions. For each use (or definition) of c, we make up a new temporary, and fetch (or store) it immediately afterward (or beforehand):

   enter:
     c1 := r3
     M[c_loc] := c1
     a := r1
     b := r2
     d := 0
     e := a
   loop:
     d := d+b
     e := e-1
     if e>0 goto loop
     r1 := d
     c2 := M[c_loc]
     r3 := c2
     return
       [ r1,r3 live out]
   

8. Now we build a new inteference graph:

   

9. Graph coloring proceeds as follows. We can immediately coalesce c1+r3 and then c2+r3:

   

10. Then, as before, we can coalesce a+e and then b+r2:

    

11. As before, we can coalesce ae+r1 and then simplify d:

    

12. Now we start popping from the stack: we select color r3 for d, and this was the only node on the stack--all other nodes were coalesced or precolored. So the coloring is:

    Node	Color
    a	r1
    b	r2
    c	r3
    d	r3
    e	r1

13. Now we can rewrite the program with this register assignment:

    enter:
      r3 := r3
      M[c_loc] := r3
      r1 := r1
      r2 := r2
      r3 := 0
      r1 := r1
    loop:
      r2 := r3+r2
      r1 := r1-1
      if r1>0 goto loop
      r1 := r3
      r3 := M[c_loc]
      r3 := r3
      return
        [ r1,r3 live out]
    

14. Finally, we can delete any move instruction whose source and destination are the same; these are the result of coalescing:

    enter:
      M[c_loc] := r3
      r3 := 0
    loop:
      r2 := r3+r2
      r1 := r1-1
      if r1>0 goto loop
      r1 := r3
      r3 := M[c_loc]
      return
        [ r1,r3 live out]
    

    The final program has only one uncoalesced move instruction.