How Does Graph Coloring Model Register Allocation?

Compilers translate high-level programs that use an unlimited number of virtual variables into machine code that must run on a processor with a small, fixed number of physical registers. To bridge this gap, compilers model register allocation as a graph coloring problem. In this model, variables are represented as vertices, conflicts between variables that are needed at the same time are represented as edges, and physical registers are represented as colors. Finding a valid assignment of variables to registers without exceeding the hardware limit is equivalent to coloring the graph with at most k colors, a classic problem known to be NP-complete.

Liveness Analysis and Interference Graphs

Before building the graph, the compiler performs liveness analysis on the intermediate representation of the program. A variable is considered live at a given program point if its current value will be read by a future instruction before it is overwritten.

Two variables interfere if they are both live at the same program point. Because they must hold distinct values simultaneously, they cannot share the same physical register. The compiler encodes these constraints in an undirected interference graph \(G = (V, E)\), where:

  • Each vertex \(v \in V\) corresponds to a virtual register or temporary variable.
  • An edge \((u, v) \in E\) exists if and only if variables \(u\) and \(v\) are simultaneously live at some point in the program.

If the target CPU has \(k\) general-purpose registers, the register allocation problem reduces to finding a proper \(k\)-coloring of \(G\): a function \(c: V \to \{1, 2, \dots, k\}\) such that for every edge \((u, v) \in E\), \(c(u) \neq c(v)\).

Why the Problem Is NP-Complete

In classical complexity theory, deciding whether an arbitrary graph \(G\) is \(k\)-colorable is NP-complete for any \(k \ge 3\). Gregory Chaitin and his colleagues proved in 1981 that register allocation via graph coloring is also NP-complete by showing that any arbitrary graph can be realized as the interference graph of some valid program.

Because no polynomial-time algorithm is known to solve NP-complete problems optimally in the general case, production compilers rely on heuristics to find good colorings quickly rather than searching for a guaranteed optimal solution.

Chaitin-Briggs Heuristic Algorithm

Most classical graph-coloring allocators follow the Chaitin-Briggs algorithm, which alternates between simplifying the graph and assigning colors:

  1. Simplify: If there is a vertex \(v\) with degree \(\deg(v) < k\), it can always be colored regardless of how its neighbors are colored. The compiler removes \(v\) from the graph and pushes it onto a stack.
  2. Spill (Potential): If every remaining vertex has degree \(\ge k\), the graph cannot be simplified further with certainty. The compiler selects a vertex \(v\) as a potential spill candidate—typically choosing one with high degree and low estimated execution frequency—and pushes it onto the stack anyway, hoping its neighbors will end up using fewer than \(k\) distinct colors.
  3. Select: Once the graph is empty, the compiler pops vertices from the stack one by one, reinserts them into the graph, and assigns each a color not used by any of its already-colored neighbors.
  4. Actual Spill: If a popped vertex has neighbors using all \(k\) colors, it cannot be assigned a register. The compiler inserts load and store instructions to keep that variable in memory (spilling it), updates the interference graph, and repeats the process.

Coalescing and Rematerialization

To improve performance further, compilers often combine graph coloring with copy coalescing. If a move instruction copies variable \(u\) to variable \(v\) and there is no edge \((u, v) \in E\), the compiler can merge \(u\) and \(v\) into a single vertex, eliminating the move instruction entirely. However, aggressive coalescing increases vertex degrees and can introduce spills, so modern allocators use conservative strategies—such as Briggs' or George's criteria—to merge nodes only when doing so is guaranteed not to make the graph uncolorable.