## 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

Consider the following program, produced by the instruction-selection phase of a compiler:
```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 target machine has three registers, r1, r2, r3. Registers r1 and r2 are caller-save, and r3 is callee-save. The code generator has therefore made arrangements to preserve the value of r3 explicitly, by copying it into the temporary c and back again. The interference graph for this function is:

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.