Register allocation is the phase of the compiler that determines which values will be placed in registers. It is often combined with register assignment. If we treat variables as nodes, interferences as edges, and registers as colors, then we can reduce the problem of register allocation to one of combinatorial graph coloring. Consequently, register allocation will succeed without spilling if the chromatic number of any interference graph is less than or equal to the number of usable machine registers. Andrew Appel provides sample graph coloring problems generated by the Standard ML of New Jersey, compiling itself. Thus, we assume that liveness analysis and its corresponding interface graph have already been completed.

Register allocation is tricky enough as it is without extra optimizations, so we examine a vanilla implementation, ignoring spilling, coalescing, and move-move operations. At least for now. It also turns out that true k-coloring is an NP-complete problem, but don’t let that stop you. Thus, we’ll use a heuristic approach, which often colors well, but fails to color optimally.

With these assumptions, the algorithm itself is actually quite simple:

• Let k be the number of registers available.
• Simplify the graph. Whenever a node has less than k neighbors, drop it from the graph, since we know we can color it with some color. Put the node on the stack so that we remember to color it later.
• Once the graph is empty, select colors to assign to the nodes by popping them off the stack and assigning colors as we go.