The interference graph is used for assigning registers to temporary variables. If two variables do not interfere (ie, there is no edge between these two variables in the interference graph) then we can use the same register for both of them, thus reducing the number of registers needed. On the other hand, if there is a graph edge between two variables, then we should not assign the same register to them since this register needs to hold the values of both variable at one point of time (because the lives of these variables overlap at one point of time - this is what interference means).

Suppose that we have *n* available registers:
*r*_{1}, *r*_{2},..., *r*_{n}. If
we view each register as a different color, then the register
allocation problem for the interference graph is equivalent to the
graph coloring problem where we try to assign one of the *n* different
colors to graph nodes so that no two adjacent nodes have the same
color. This algorithm is used in map drawing where we have countries
or states on the map and we want to color them using a small fixed
number of colors so that states that have a common border are not
painted with the same color. The graph in this case has one node for
each state and an edge between two states if they have common borders.

The register allocation algorithm uses a stack of graph nodes to
insert all nodes of the interference graph one at a time. Each time
it selects a node that has fewer than *n* neighbors (adjacent nodes).
The idea is that if we can color the graph after we remove this node,
then of course we can color the original graph (with the node
included) because the neighbors of this node can have *n* - 1 different
colors in the worst case; so we can just assign the available *n*th
color to the node. This is called *simplification* of the
graph. Each selected node is pushed in the stack. Sometimes though we
cannot simplify any further because all nodes have *n* or more
neighbors. In that case we select one node (ie. variable) to be
spilled into memory instead of assigning a register to it. This is
called *spilling* and the spilled victim can be selected based on
priorities (eg. which variable is used less frequently, is it outside
a loop, etc). The spilled node is also pushed on the stack. When the
graph is completely reduced (and all nodes have been pushed in the
stack), we pop the stack one node at a time, we rebuild the
interference graph and at the same time we assign a color to the
popped-out node so that its color is different from the colors of its
neighbors. This is called the *selection* phase. If we can't
assign a color to a node, we spill out the node into memory (a node
selected to be spilled out during the spill phase does not necessarily
mean that it will actually spilled into memory at the end). If there
are spilled nodes, we use a memory access for each spilled variable
(eg. we use the frame location $fp-24 to store the spilled temporary
variable and we replace all occurrences of this variable in the
program with M[$fp-24]). Then we restart the whole process (the
building of the interference graph, simplification, etc) from the
beginning. Figures 11.1-11.3 on page 237 give an example of this
method.

Consider the following interference graph from the previous section:

The nodes are pushed in the stack in the order of xvuzyw.
Then, at the selection phase, xyzwuv variables
are assigned the registers
*R*_{0}*R*_{2}*R*_{1}*R*_{0}*R*_{1}*R*_{0}.

If there is a move instruction in a program (ie. an assignment of the
form `a:=b`

) and there is no conflict between `a`

and
`b`

, then it is a good idea to use the same register for both
`a`

and `b`

so that you can remove the move instruction
entirely from the program. In fact you can just merge the graph nodes
for `a`

and `b`

in the graph into one node. That way nodes
are now labeled by sets of variables, instead of just one variable.
This is called *coalescing*. This is a good thing to do since it
reduces the number of registers needed and it removes the move
instructions, but it may be bad since it increases the number of
neighbors of the merged nodes, which may lead to an irreducible graph
and a potential spilling. To do this, we add another phase to the
register allocation algorithm, called *coalescing*, that coalesces
move related nodes. If we derive an irreducible graph at some point
of time, there is another phase, called *freezing*, that
de-coalesces one node (into two nodes) and continues the
simplification.

A common criterion for coalescing is that we coalesce two nodes if the
merged node has fewer than *n* neighbors of degree greater than or
equal to *n* (where *n* is the number of available registers). This is
called the Briggs criterion. A slight variation of this is the George
criterion where we coalesce nodes if all the neighbors of one of the
nodes with degree greater than or equal to *n* already interfere with
the other node.

Coalescing is very useful when handling callee-save registers in a
program. Recall that callee-save registers need to be saved by the
callee procedure to maintain their values upon the exit of the
procedure. Suppose that `r3`

is a callee-save register. The
procedure needs to save this register into a temporary variable at the
beginning of the procedure (eg. `a := r3`

) and to restore it at
the end of the procedure (ie. `r3 := a`

). That way, if `r3`

is not used at all during the procedure body, it will be coalesced
with `a`

and the move instructions will be removed. But
coalescing can happen in many other different situations as long as
there is no interference, which makes this technique very general. Note
that registers in a program are handled as temporary variables with a
preassigned color (precolored nodes). This means that precolored nodes
can only be coalesced with other nodes (they cannot be simplified or
spilled). See the example on page 245 in the textbook for a program with precolored
nodes.

2002-08-26