Register Allocation - Introduction to Compiler Construction in a Java World - page 272

Algorithm 7.9 Graph Coloring Register Allocation
Input: The control-flow graph g for a method with LIR that makes use of virtual registers
Output: The same g but with virtual registers replaced by physical registers
registersAssignedSuccessfully false
repeat
repeat
buildIntervals()
buildInterferenceGraph()
until coalesceRegistersSuccessful()
buildAdjacencyLists()
computeSpillCosts()
pruneGraph()
registersAssignedSuccessfully assignRegistersSuccessful()
if registersAssignedSuccessfully then
generateSpillCode()
end if
until registersAssignedSuccessfully
This algorithm looks like it could go on for a long time, but it usually terminates after
at most two or three iterations.
Register Coalescing
Coalescing registers reduces both the number of virtual registers and the number of moves.
The method coalesceRegistersSuccessful() returns true if it is able to coalesce two registers
and false otherwise; this Boolean result insures that any register coalescing is followed by
a rebuilding of the intervals and the interference graph.
Register coalescing also makes for longer intervals and could render the graph uncol-
orable. [Briggs et al., 1994] and [George and Appel, 1996] propose more conservative condi-
tions under which we may safely coalesce registers, without making the graph uncolorable.
Briggs proposes that two nodes in the graph may be coalesced if the resulting node will
have fewer than R neighbors of significant degree (having R or more edges). George and
Appel propose that two nodes may be coalesced if for every neighbor t of one of those nodes,
either t already interferes with the other node (so no additional edges are added) or t is of
insignificant degree. Appel [Appel, 2002] points out that these rules may prevent the safe
removal of certain moves but that extra moves are less costly than spills.
Representing the Interference Graph
The representation of the interference graph is driven by the kind of queries one wants to
make of it. Our algorithm wants to ask two things:
1. Whether or not one node is adjacent to another. We want to know this when we
coalesce registers and when we want to assign registers.
2. How many nodes, and which nodes, are adjacent to a given node.
The first is best answered by a Boolean adjacency matrix: a matrix with a row and column
for each register; adj[i;j] is true if nodes i and j are adjacent and false otherwise. A lower-
triangular matrix is sucient because there is an ordering on the nodes. For example, our
interference graph in Figure 7.8 might be captured using the following lower-triangular
matrix, where T is true and F is false.