Introduction

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 kk 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.

Color the Interference Graph

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).

<!-- HTML layout for the interference graph coloring demo -->
<p class="hint">Each node is a variable; each edge means those two variables are alive at the same time and cannot share a register. Click a node to assign the selected register color. Use only 3 registers (R1, R2, R3). If a node has too many conflicts, mark it as Spill — it goes to memory instead.</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">Spill</button>
</div>
<div class="canvas-wrap">
  <canvas id="igraph" width="420" height="300"></canvas>
</div>
<div class="status" id="status">Click a node, then assign a register or spill it.</div>
<div class="btns">
  <button id="btnAuto" type="button">Auto-color (greedy)</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>

/* Styles for the interference graph demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Register allocation demo: color an interference graph with k=3 registers.
// Nodes represent variables; edges = interference (both alive at the same time).
const NODES = [
  { id: 'a', label: 'a', x: 210, y: 50 },
  { id: 'b', label: 'b', x: 340, y: 130 },
  { id: 'c', label: 'c', x: 290, y: 255 },
  { id: 'd', label: 'd', x: 130, y: 255 },
  { id: 'e', label: 'e', x:  80, y: 130 },
  { id: 'f', label: 'f', x: 210, y: 165 }
];
// Interference edges — this graph is NOT 3-colorable without spilling (it contains K4).
const EDGES = [
  ['a','b'],['a','e'],['a','f'],
  ['b','c'],['b','f'],
  ['c','d'],['c','f'],
  ['d','e'],['d','f'],
  ['e','f']
];
// Register color map (hex fill and text color per register)
const REG_COLORS = { R1: '#e63946', R2: '#2a9d8f', R3: '#e9c46a', SPILL: '#888' };
const REG_TEXT   = { R1: '#fff',    R2: '#fff',    R3: '#333',    SPILL: '#fff' };
const K = 3; // number of available physical registers

const canvas = document.getElementById('igraph');
const ctx = canvas.getContext('2d');
const assignment = {}; // map nodeId -> register string ('R1'|'R2'|'R3')
let spilled = new Set(); // set of node ids that have been spilled to memory
let selectedReg = 'R1';
let hoveredNode = null;

// initialize R1 as the selected register button
document.getElementById('reg1').classList.add('active');

document.querySelectorAll('.reg-btn').forEach(btn => {
  btn.addEventListener('click', () => {
    selectedReg = btn.dataset.reg;
    document.querySelectorAll('.reg-btn').forEach(b => b.classList.remove('active'));
    btn.classList.add('active');
  });
});

function nodeAt(mx, my) {
  // return the node within 22px of (mx,my), or null
  for (const n of NODES) {
    const dx = mx - n.x, dy = my - n.y;
    if (Math.sqrt(dx*dx + dy*dy) <= 22) return n;
  }
  return null;
}

function getNeighborRegs(nodeId) {
  // collect register assignments of all neighbors of nodeId
  const regs = new Set();
  for (const [u, v] of EDGES) {
    if (u === nodeId && assignment[v]) regs.add(assignment[v]);
    if (v === nodeId && assignment[u]) regs.add(assignment[u]);
  }
  return regs;
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  // draw interference edges first (behind nodes)
  ctx.strokeStyle = '#adb5bd';
  ctx.lineWidth = 1.8;
  for (const [u, v] of EDGES) {
    const A = NODES.find(n => n.id === u);
    const B = NODES.find(n => n.id === v);
    ctx.beginPath(); ctx.moveTo(A.x, A.y); ctx.lineTo(B.x, B.y); ctx.stroke();
  }
  // draw each node circle with fill color based on assignment
  for (const n of NODES) {
    const reg = assignment[n.id];
    const isSpilled = spilled.has(n.id);
    const isHovered = n === hoveredNode;
    const fill = isSpilled ? '#888' : (reg ? REG_COLORS[reg] : (isHovered ? '#b0bec5' : '#c9ccd1'));
    const textCol = isSpilled ? '#fff' : (reg ? REG_TEXT[reg] : '#333');
    ctx.beginPath();
    ctx.arc(n.x, n.y, 22, 0, 2*Math.PI);
    ctx.fillStyle = fill;
    ctx.fill();
    ctx.strokeStyle = isHovered ? '#1d3557' : '#8897a5';
    ctx.lineWidth = isHovered ? 2.5 : 1.5;
    ctx.stroke();
    ctx.fillStyle = textCol;
    ctx.font = 'bold 14px ui-monospace, monospace';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(n.label, n.x, n.y);
    if (reg && !isSpilled) {
      // small register label below variable name
      ctx.fillStyle = textCol;
      ctx.font = '10px system-ui, sans-serif';
      ctx.fillText(reg, n.x, n.y + 13);
    }
    if (isSpilled) {
      ctx.fillStyle = '#fff';
      ctx.font = '10px system-ui, sans-serif';
      ctx.fillText('MEM', n.x, n.y + 13);
    }
  }
}

function setStatus(msg, cls) {
  const s = document.getElementById('status');
  s.textContent = msg;
  s.className = 'status ' + cls;
}

function checkColoring() {
  // validate the current partial or complete coloring
  const activeNodes = NODES.filter(n => !spilled.has(n.id));
  const allAssigned = activeNodes.every(n => assignment[n.id]);
  if (!allAssigned) { setStatus('Click a node, then assign a register or spill it.', 'info'); return; }
  for (const [u, v] of EDGES) {
    if (spilled.has(u) || spilled.has(v)) continue;
    if (assignment[u] && assignment[v] && assignment[u] === assignment[v]) {
      setStatus(i18nFmt('Conflict: %u% and %v% share a register!', { u, v }), 'bad');
      return;
    }
  }
  if (spilled.size > 0) {
    setStatus(i18nFmt('Valid coloring with %n% spill(s). Spilled variables go to memory.', { n: spilled.size }), 'ok');
  } else {
    setStatus('Perfect! All variables fit in 3 registers — no spills needed.', 'ok');
  }
}

canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const mx = (e.clientX - rect.left) * (canvas.width / rect.width);
  const my = (e.clientY - rect.top)  * (canvas.height / rect.height);
  const node = nodeAt(mx, my);
  if (!node) return;
  if (selectedReg === 'SPILL') {
    // mark this node as spilled to memory
    spilled.add(node.id);
    delete assignment[node.id];
  } else {
    const neighborRegs = getNeighborRegs(node.id);
    if (neighborRegs.has(selectedReg) && !spilled.has(node.id)) {
      setStatus(i18nFmt('%reg% is already used by a neighbor of %node%. Choose another register.', { reg: selectedReg, node: node.label }), 'bad');
      draw();
      return;
    }
    spilled.delete(node.id);
    assignment[node.id] = selectedReg;
  }
  draw();
  checkColoring();
});

canvas.addEventListener('mousemove', e => {
  const rect = canvas.getBoundingClientRect();
  const mx = (e.clientX - rect.left) * (canvas.width / rect.width);
  const my = (e.clientY - rect.top)  * (canvas.height / rect.height);
  hoveredNode = nodeAt(mx, my);
  canvas.style.cursor = hoveredNode ? 'pointer' : 'default';
  draw();
});

canvas.addEventListener('mouseleave', () => { hoveredNode = null; draw(); });

function autoColor() {
  // greedy coloring — assign the first available register; spill if none
  // greedy pass over nodes in definition order
  Object.keys(assignment).forEach(k => delete assignment[k]);
  spilled.clear();
  const REGS = ['R1', 'R2', 'R3'];
  for (const n of NODES) {
    const used = getNeighborRegs(n.id);
    const avail = REGS.filter(r => !used.has(r));
    if (avail.length > 0) {
      assignment[n.id] = avail[0];
    } else {
      spilled.add(n.id);
      // no register available — this node must spill
    }
  }
  draw();
  checkColoring();
}

document.getElementById('btnAuto').addEventListener('click', autoColor);
document.getElementById('btnReset').addEventListener('click', () => {
  Object.keys(assignment).forEach(k => delete assignment[k]);
  spilled.clear();
  draw();
  setStatus('Click a node, then assign a register or spill it.', 'info');
});

draw();
setStatus('Click a node, then assign a register or spill it.', 'info');
Result
Console

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.

The Real Complexity

Register allocation is NP-complete. The proof is a reduction from graph coloring: any instance of kk-coloring can be turned into a register allocation problem with exactly kk registers. Since kk-coloring is NP-complete for k≥3k \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 kk neighbors can always be colored), push it onto a stack, and color on the way back. If a node has kk 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/register-allocation/Content licensed under CC BY-NC 4.0.