Register allocation is an NP-complete problem (except in special cases, such as expression trees); graph coloring is also AfP-complete. Fortunately there is a linear-time approximation algorithm that gives good results; its principal phases are Build, Simplify, Spill, and Select.

Build: Construct the interference graph. We use dataflow analysis to compute the set of temporaries that are simultaneously live at each program point, and we add an edge to the graph for each pair of temporaries in the set. We repeat this for all program points.

Simplify: we repeatedly remove (and push on a stack) nodes of degree less than K. Each such simplification will decrease the degrees of other nodes, leading to more opportunity for simplification.

Spill: Suppose at some point during simplification the graph G has nodes only of significant degree, that is, nodes of degree >= K. we mark some node for spilling. That is, we choose some node in the graph (standing for a temporary variable in the program) and decide to represent it in memory, not registers, during program execution. An optimistic approximation to the effect of spilling is that the spilled node does not interfere with any of the other nodes remaining in the graph. It can therefore be removed and pushed on the stack, and the simplify process continued

Select: We assign colors to nodes in the graph. Starting with the empty graph, we rebuild the original graph by repeatedly adding a node from the top of the stack. When we add a node to the graph, there must be a color for it, as the premise for removing it in the simplify phase was that it could always be assigned a color provided the remaining nodes in the graph could be successfully colored.

When potential spill node n that was pushed using the Spill heuristic is popped, there is no guarantee that it will be colorable: its neighbors in the graph may be colored with K different colors already. In this case, we have an actual spill. We do not assign any color, but we continue the Select phase to identify other actual spills. But perhaps some of the neighbors are the same color, so that among them there are fewer than K colors. Then we can color n, and it does not become an actual spill. This technique is known as optimistic coloring.

Start over: If the Select phase is unable to find a color for some node(s), then the program must be rewritten to fetch them from memory just before each use, and store them back after each definition. Thus, a spilled temporary will turn into several new temporaries with tiny live ranges. These will interfere with other temporaries in the graph. So the algorithm is repeated on this rewritten program. This process iterates until simplify succeeds with no spills; in practice, one or two iterations almost always suffice.

It is easy to eliminate redundant move instructions with an interference graph. If there is no edge in the interference graph between the source and destination of a move instruction, then the move can be eliminated.

The source and destination nodes are coalesced into a new node whose edges are the union of those of the nodes being replaced.

Some temporaries are precolored - they represent machine registers.

For each actual register that is used for some specific purpose, such as the frame pointer, standard-argument- 1-register, standard-argument-2-register,