1981 United States NP-complete

Register Allocation via Graph Coloring

Gregory Chaitin, 1981 — optimal register allocation reduces to graph coloring, which is NP-complete. Even the compiler is solving an NP-hard problem on every build.

Gregory Chaitin, at IBM Research Yorktown Heights, formulated register allocation as a graph coloring problem and built a compiler that used the reduction. Each variable in a program becomes a node in an interference graph; two nodes are connected if their variables are alive at the same time and therefore cannot share a register. Coloring the graph with k colors corresponds to assigning each variable to one of k registers. Graph k-coloring is NP-complete for k ≥ 3 (Karp 1972), so register allocation is NP-complete. Modern compilers use heuristics — Chaitin's graph coloring approach, linear scan, or SSA-based variants — none of which is guaranteed optimal. Every time gcc, clang, or rustc compiles your code, it is approximating an NP-complete problem. The hardness is invisible because we have lived with the heuristic for forty years.

In plain terms

Most programmers never think about register allocation. The compiler does it. Variables go in. Machine code comes out. Somewhere in the middle the compiler decides which variables get to live in CPU registers — fast, scarce — and which get spilled to memory — slow, abundant. Chaitin's contribution was to notice that this decision is exactly graph coloring. Build a graph where every variable is a node. Connect two nodes if the variables are alive at the same time — meaning both might be needed before either is overwritten. Now ask: can I color this graph using at most k colors, where two connected nodes never share a color? If yes, you can assign each variable to one of k registers. If no, you have to spill something. Graph coloring with three or more colors is NP-complete. Karp proved it in 1972. Chaitin's reduction made register allocation NP-complete. And every compiler in the world has been approximating the answer ever since. GCC uses a refined Chaitin-Briggs algorithm. LLVM uses a variant called greedy register allocation. V8's JIT for JavaScript uses linear scan. None of them is optimal. All of them are heuristics that give you a good answer most of the time. The point of putting this page in the book is the invisibility of the hardness. Every time you run npm install or cargo build or make, your computer is solving an NP-complete problem in the compiler — and doing it well enough that you do not notice. The reason it works is forty years of heuristic engineering, not a breakthrough in complexity theory. The same lesson will repeat in chapter eight (package managers running SAT solvers), chapter eleven (search-based refactoring), and chapter eighteen (CompCert paying the proof tax to get optimal correctness). The hardness is in the problem. The compiler is the heuristic. The heuristic has been good for forty years. That is not the same as solved.