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.

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,

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

- 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 **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, - 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, - Now we could coalesce
**ae+r1**or coalesce**b+r2**. Let us do the latter: - We can now coalesce either
**ae+r1**or coalesce**d+r1**. Let us do the former: - We cannot now coalesce
**r1ae+d**because the move is*constrained:*the nodes**r1ae**and**d**interfere. We must**simplify****d**: - 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. - 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]

- Now we build a new inteference graph:
- Graph coloring proceeds as follows. We can immediately coalesce
**c1+r3**and then**c2+r3**: - Then, as before, we can coalesce
**a+e**and then**b+r2**: - As before, we can coalesce
**ae+r1**and then simplify**d**: - 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 - 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]

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