Register Allocation

Every program you run has been transformed by a compiler into machine code. One of the most critical steps in that transformation is register allocation: deciding which variables get to live in the CPU's tiny set of blazing-fast registers, and which ones get exiled to much slower memory.

A modern CPU might have 16 or 32 general-purpose registers. A typical function, however, may juggle dozens or hundreds of variables. Two variables that are alive at the same time cannot share a register — they would overwrite each other. Variables that are never alive simultaneously, on the other hand, can safely share one.

The compiler's job is to color the interference graph: build a graph where each node is a variable and each edge connects two variables that are alive at the same time, then assign a color (register) to each node so that no two neighbors share a color. If $k$ colors (registers) are enough, every variable stays fast. If not, some variables must be spilled — written to and read from memory, which costs precious cycles.

This coloring problem is the engine of every optimizing compiler you have ever used.

Below is an interference graph: each node is a variable, and an edge means those two variables are alive at the same time — they cannot share a register. Click a node and then pick a register color to assign it. Use only 3 registers (R1, R2, R3).

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="toolbar">
  <span class="reg-label">{{pick_register}}</span>
  <button class="reg-btn" id="reg1" data-reg="R1" style="background:#e63946;border-color:#c92f3c">R1</button>
  <button class="reg-btn" id="reg2" data-reg="R2" style="background:#2a9d8f;border-color:#1d7268">R2</button>
  <button class="reg-btn" id="reg3" data-reg="R3" style="background:#e9c46a;border-color:#c9a84c;color:#333">R3</button>
  <button class="reg-btn" id="regSpill" data-reg="SPILL" style="background:#888;border-color:#666">{{btn_spill}}</button>
</div>
<div class="canvas-wrap">
  <canvas id="igraph" width="420" height="300"></canvas>
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="btnAuto" type="button">{{btn_auto}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.toolbar { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; }
.reg-label { font-size: .85rem; font-weight: 600; color: #555; }
.reg-btn { font: 700 13px ui-monospace, monospace; padding: .3rem .7rem;
           border-radius: 6px; border: 2px solid; cursor: pointer; color: #fff;
           transition: opacity .1s; }
.reg-btn.active { outline: 3px solid #1d3557; outline-offset: 2px; }
.canvas-wrap { border: 1px solid #cdd9e3; border-radius: 8px; overflow: hidden;
               background: #f5f8fa; display: inline-block; }
canvas { display: block; cursor: pointer; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice what happens when a variable has too many conflicting neighbors: no color is available. That variable must be spilled to memory. The demo will detect when coloring is impossible with 3 registers and show you which variable needs to spill. Spilling eliminates the variable from the graph (by splitting its live range), letting the remaining graph be colored — but at a runtime cost.

Register allocation is NP-complete. The proof is a reduction from graph coloring: any instance of $k$-coloring can be turned into a register allocation problem with exactly $k$ registers. Since $k$-coloring is NP-complete for $k \ge 3$ (proved by Karp in 1972), optimal register allocation is too.

Gregory Chaitin made this explicit in 1981, showing that the register allocation problem in its general form is equivalent to graph coloring. His paper is one of the most cited in compiler theory.

In practice, compilers cannot afford to solve NP-complete problems optimally for every function they compile. They use polynomial-time heuristics:

• Chaitin-Briggs coloring: repeatedly remove the lowest-degree node (a node with fewer than $k$ neighbors can always be colored), push it onto a stack, and color on the way back. If a node has $k$ or more neighbors, it is a spill candidate.
• Live-range splitting: instead of spilling a whole variable, split its live range into shorter pieces that might each fit in a register.
• Coalescing: if two variables are connected by a copy instruction and do not interfere, merge them into one node to eliminate the copy.
• Linear scan: a faster, less optimal algorithm used in JIT compilers — scan variables in order of their live intervals and greedily assign registers.

The gap between the optimal solution and what heuristics find is the invisible tax you pay every time you run a program: a few percent slower than theoretically possible, because the compiler gave up on NP-complete exactness in exchange for finishing in seconds.

Register allocation sits at the heart of every optimizing compiler:

• C and C++ compilers (GCC, Clang/LLVM): the register allocator is one of the most tuned components. A better allocator means faster loops, fewer memory round-trips, and lower energy use — critical on battery-powered devices.
• JIT compilers (Java HotSpot, V8, .NET CLR): JIT compilation happens at runtime, so the allocator must be fast itself. Linear scan is the usual compromise: less optimal than Chaitin-Briggs but runs in linear time.
• GPU compilers: GPUs have hundreds of registers per thread, but run thousands of threads simultaneously. Spilling in a GPU shader kills occupancy and can slash throughput by 10×.
• Embedded and real-time systems: microcontrollers may have only 8 registers. Register pressure here directly determines whether code fits in cache.

Every time a tight inner loop shaves a nanosecond off a hot path, a good register allocator probably deserves some of the credit. And every time you wonder why the compiler took so long — it was wrestling with a problem related to graph coloring and P vs NP.

Register allocation is a beautiful example of a hard problem that must be solved anyway — millions of times a day, inside every compiler on every machine. The theory says it is NP-complete, and the theory is right: no polynomial algorithm is known that always finds the optimal assignment.

Yet programs run fast. The secret is that compilers do not solve register allocation exactly — they use carefully engineered heuristics that find good-enough solutions quickly. Chaitin-Briggs, linear scan, live-range splitting: each is a pragmatic truce with intractability.

The interference graph is a microcosm of the whole field. Color it optimally and every variable stays in a fast register. Fail, and variables spill to memory, burning cycles. The boundary between "fits in registers" and "must spill" is the same boundary that graph coloring draws, and it is as hard as P vs NP predicts.