rustc, Go and the JavaScript JITs really do this, and where the awkward ISA constraints (like idiv demanding rax:rdx) come from.Learn Zig Series):Last episode we built a real code generator -- an AST went in, and honest x86-64 machine code came out, bytes we jumped into and called like any other function. But I ended on a confession: our strategy was a stack machine, and stack-machine code is correct but slow. It shoves every intermediate value onto the hardware stack and pops it right back, touching memory constantly, where a good compiler would keep those values sitting in registers where the CPU can reach them in a single cycle. I said the one thing standing between our output and code a real compiler would be proud of is where the values live. Today we untie exactly that knot. This is register allocation -- and it is one of the most beautiful problems in all of compilers, because it is really a graph problem in disguise. Here we go!
Three exercises closed the code-generation episode, and all three extend that episode's generate, parser and CodeBuf, so paste them alongside episode 144's file.
Exercise 1 -- add a modulo operator %. The trick is that x86's idiv already computes both quotient and remainder in one shot: after cqo; idiv rcx the quotient is in rax and the remainder is in rdx. So % is nearly free -- run the exact same division sequence, then take rdx instead of rax. I give BinOp a mod tag, wire % into parseTerm at the same precedence as * and /, and in generate emit one extra mov rax, rdx:
// parseTerm's loop now also accepts '%':
while (self.peek()) |c| {
if (c != '*' and c != '/' and c != '%') break;
self.pos += 1;
const rhs = try self.parseFactor();
const op: BinOp = switch (c) { '*' => .mul, '/' => .div, else => .mod };
lhs = try self.make(.{ .bin = .{ .op = op, .lhs = lhs, .rhs = rhs } });
}
// In generate's per-operator switch, right next to .div:
.mod => {
try cb.emit(&.{ 0x48, 0x99, 0x48, 0xF7, 0xF9 }); // cqo ; idiv rcx
try cb.emit(&.{ 0x48, 0x89, 0xD0 }); // mov rax, rdx (remainder)
},
Because x86 idiv truncates toward zero, its remainder matches Zig's @rem, so the differential test lines up exactly:
test "modulo matches Zig @rem across many inputs" {
const gpa = std.testing.allocator;
var f = try compile(gpa, "x % 7");
defer f.deinit();
var x: i64 = -50;
while (x <= 50) : (x += 1) {
try std.testing.expectEqual(@rem(x, 7), f.call(x));
}
}
mov rax, rdx is 0x48 0x89 0xD0 -- the REX.W prefix for 64-bit, the 0x89 move opcode, and a ModRM byte of 0xD0 that names rdx as source and rax as destination. One instruction is the whole difference between division and modulo.
Exercise 2 -- comparisons that yield 0 or 1. This one is proper instruction selection, because a comparison is a little dance of three instructions: cmp to set the CPU flags, a setcc that writes a single 0-or-1 byte into al based on those flags, then a movzx to zero-extend that byte into the full rax. The elegant part is that the only thing that changes between >, <, == and != is one opcode byte in the setcc:
const CmpOp = enum { gt, lt, eq, ne };
fn genCmp(cb: *CodeBuf, op: CmpOp) !void {
try cb.emit(&.{ 0x59, 0x58 }); // pop rcx ; pop rax (rhs, then lhs)
try cb.emit(&.{ 0x48, 0x39, 0xC8 }); // cmp rax, rcx
switch (op) { // setCC al
.gt => try cb.emit(&.{ 0x0F, 0x9F, 0xC0 }),
.lt => try cb.emit(&.{ 0x0F, 0x9C, 0xC0 }),
.eq => try cb.emit(&.{ 0x0F, 0x94, 0xC0 }),
.ne => try cb.emit(&.{ 0x0F, 0x95, 0xC0 }),
}
try cb.emit(&.{ 0x48, 0x0F, 0xB6, 0xC0 }); // movzx rax, al
try cb.emit(&.{0x50}); // push rax (0 or 1)
}
Notice I did NOT try to pass the setcc opcode as a runtime variable -- episode 144's emit takes a comptime byte slice, so I branch in a switch where each arm is a compile-time literal. That is Zig gently steering you: the encoding is fixed at compile time, so the type system wants it fixed at compile time. The result is still an integer sitting on the stack, so the stack-machine convention survives untouched -- an x > 5 expression composes with + and * exactly like a number does.
Exercise 3 -- a peephole optimizer. Our stack discipline emits obvious waste: a push rax (0x50) immediately followed by a pop rax (0x58) pushes a value and instantly pops the same value back into the same register -- a no-op we can just delete. A first pass over the byte buffer catches it:
fn peephole(gpa: std.mem.Allocator, code: []const u8) !std.ArrayList(u8) {
var out = std.ArrayList(u8).empty;
errdefer out.deinit(gpa);
var i: usize = 0;
while (i < code.len) {
if (i + 1 < code.len and code[i] == 0x50 and code[i + 1] == 0x58) {
i += 2; // push rax ; pop rax -> nothing
continue;
}
try out.append(gpa, code[i]);
i += 1;
}
return out;
}
Nota bene: a byte-level peephole like this is subtly dangerous -- the bytes 0x50 0x58 could appear inside a movabs immediate, not as real instructions, and we would corrupt the program by deleting them. The robust version, as the exercise hinted, runs over the list of emitted instructions before flattening to bytes, where "push then pop of the same register" is unambiguous. I show the byte version because it makes the idea concrete, but the lesson is the real one: optimize the representation where the meaning is clear, not the one where it is accidental. And notice why this waste exists at all -- it is the stack machine spilling to memory when it did not need to. Which is precisely the disease we cure today. ;-)
Here is the core tension, stated plainly. When you walk an expression tree, every subexpression produces a value, and a big expression produces many live values at once. In (a + b) * (c + d), the moment you compute c + d you still need a + b sitting around to multiply against it. Our stack machine "solved" this by giving every value its own slot on an effectively infinite stack -- correct, but every access is a memory access. A real CPU has a tiny fixed set of fast registers (x86-64 gives you about 14 usable general-purpose ones), and the whole game of register allocation is: assign each of the program's many values to one of those few registers, reusing a register the instant its previous occupant is no longer needed, and falling back to memory only when you genuinely run out. That fallback-to-memory is called spilling, and a good allocator spills as little as possible.
The reason this is a hard problem and not a bookkeeping chore is that "no longer needed" is a global property. Whether register r3 is free at instruction 40 depends on whether the value it holds is ever read again after 40 -- which you can only know by analyzing the whole program. That analysis has a name, liveness, and it is where we start. Having said that, the payoff is enormous: register allocation is routinely the difference between code that is 2x slower and code that flies, which is why every production compiler pours serious engineering into it.
You cannot allocate registers on a tree -- allocation is inherently about order and time ("this value dies before that one is born"), and a tree has no linear order. So the first move, universal across real compilers, is to lower the AST into a flat list of simple instructions, each one computing a value into a fresh virtual register. Virtual registers are unlimited: we pretend the machine has as many as we like, and worry about the real count later. This three-address form is the canonical input to every allocator on earth:
const VReg = usize;
const Instr = union(enum) {
imm: struct { dst: VReg, val: i64 },
load_x: struct { dst: VReg },
neg: struct { dst: VReg, src: VReg },
bin: struct { dst: VReg, op: BinOp, lhs: VReg, rhs: VReg },
fn dst(self: Instr) VReg {
return switch (self) {
.imm => |i| i.dst,
.load_x => |i| i.dst,
.neg => |i| i.dst,
.bin => |i| i.dst,
};
}
};
const Program = struct {
code: std.ArrayList(Instr),
nvregs: usize = 0,
root: VReg = 0,
gpa: std.mem.Allocator,
fn init(gpa: std.mem.Allocator) Program {
return .{ .code = .empty, .gpa = gpa };
}
fn deinit(self: *Program) void {
self.code.deinit(self.gpa);
}
fn fresh(self: *Program) VReg {
const v = self.nvregs;
self.nvregs += 1;
return v;
}
fn push(self: *Program, ins: Instr) !void {
try self.code.append(self.gpa, ins);
}
};
The tagged union is the same tool we have leaned on since episode 6, and the little dst helper exists because every instruction defines exactly one virtual register -- a property that makes liveness trivial in a moment. Lowering is then just the tree walk you already know, except instead of emitting bytes it emits Instrs and hands back the virtual register holding each subresult:
fn lower(p: *Program, e: *const Expr) !VReg {
switch (e.*) {
.num => |v| {
const d = p.fresh();
try p.push(.{ .imm = .{ .dst = d, .val = v } });
return d;
},
.var_x => {
const d = p.fresh();
try p.push(.{ .load_x = .{ .dst = d } });
return d;
},
.neg => |inner| {
const s = try lower(p, inner);
const d = p.fresh();
try p.push(.{ .neg = .{ .dst = d, .src = s } });
return d;
},
.bin => |b| {
const l = try lower(p, b.lhs);
const r = try lower(p, b.rhs);
const d = p.fresh();
try p.push(.{ .bin = .{ .dst = d, .op = b.op, .lhs = l, .rhs = r } });
return d;
},
}
}
fn buildProgram(gpa: std.mem.Allocator, e: *const Expr) !Program {
var p = Program.init(gpa);
p.root = try lower(&p, e);
return p;
}
Feed it x*x + 1 and you get a straight-line program: "v0 = load x; v1 = load x; v2 = v0 * v1; v3 = 1; v4 = v2 + v3", with root = v4. Notice a lovely accident of building it this way -- each virtual register is written once and, for a pure expression tree, read once (by its parent). That single-definition, single-use shape is exactly the structure that will make our liveness analysis a five-line function.
A value's live interval is the span from the instruction that defines it to the last instruction that reads it. Two values can share a physical register if and only if their intervals do NOT overlap -- if one is already dead by the time the other is born, they never need to coexist. Because every one of our virtual registers is defined at exactly one point, computing intervals is just a matter of recording each vreg's definition index and its latest use:
const Interval = struct { vreg: VReg, start: usize, end: usize };
fn computeIntervals(gpa: std.mem.Allocator, p: *const Program) ![]Interval {
const def = try gpa.alloc(usize, p.nvregs);
defer gpa.free(def);
const last = try gpa.alloc(usize, p.nvregs);
defer gpa.free(last);
for (0..p.nvregs) |v| {
def[v] = 0;
last[v] = 0;
}
for (p.code.items, 0..) |ins, idx| {
def[ins.dst()] = idx;
last[ins.dst()] = idx;
switch (ins) {
.imm, .load_x => {},
.neg => |i| last[i.src] = idx,
.bin => |i| {
last[i.lhs] = idx;
last[i.rhs] = idx;
},
}
}
// The final result is live all the way to the end -- someone returns it.
last[p.root] = p.code.items.len;
const intervals = try gpa.alloc(Interval, p.nvregs);
for (0..p.nvregs) |v| {
intervals[v] = .{ .vreg = v, .start = def[v], .end = last[v] };
}
return intervals;
}
The one subtlety worth the comment is the root: it is the value the whole program hands back, so it stays live past the last instruction (I mark its end one step beyond the code). Everything else dies at its parent. On real, non-tree programs (with ifs and loops) liveness is a proper fixpoint computation over a control-flow graph -- values can be live across many blocks -- but the concept is identical: an interval where a value matters. Get the intervals right and the allocation almost falls out.
Now the payoff. Linear scan (Poletto and Sarkar, 1999) is the algorithm that made register allocation fast enough for just-in-time compilers, and it is disarmingly simple: sort every interval by its start point, sweep through them left to right keeping a set of "currently active" intervals, and hand out registers from a free pool. When an active interval's end passes, its register goes back to the pool. When you need a register and the pool is empty, you spill -- and the clever heuristic is to spill whichever active value lives longest, because that frees a register for the greatest stretch of future code:
const Location = union(enum) { reg: usize, spill: usize };
const Allocation = struct {
loc: []Location, // indexed by vreg
num_spills: usize = 0,
gpa: std.mem.Allocator,
fn deinit(self: *Allocation) void {
self.gpa.free(self.loc);
}
};
fn startLess(_: void, a: Interval, b: Interval) bool {
return a.start < b.start;
}
fn linearScan(gpa: std.mem.Allocator, p: *const Program, num_regs: usize) !Allocation {
const intervals = try computeIntervals(gpa, p);
defer gpa.free(intervals);
std.sort.pdq(Interval, intervals, {}, startLess);
const loc = try gpa.alloc(Location, p.nvregs);
errdefer gpa.free(loc);
var free_regs = try gpa.alloc(usize, num_regs);
defer gpa.free(free_regs);
var free_top: usize = num_regs;
for (0..num_regs) |i| free_regs[i] = num_regs - 1 - i;
var active = std.ArrayList(Interval).empty;
defer active.deinit(gpa);
var active_reg = std.ArrayList(usize).empty; // register held by each active interval
defer active_reg.deinit(gpa);
var next_spill_slot: usize = 0;
var spills: usize = 0;
for (intervals) |cur| {
// Expire intervals that have ended before this one begins.
var i: usize = 0;
while (i < active.items.len) {
if (active.items[i].end < cur.start) {
free_regs[free_top] = active_reg.items[i];
free_top += 1;
_ = active.orderedRemove(i);
_ = active_reg.orderedRemove(i);
} else i += 1;
}
if (free_top > 0) {
free_top -= 1;
const r = free_regs[free_top];
loc[cur.vreg] = .{ .reg = r };
try insertActive(gpa, &active, &active_reg, cur, r);
} else {
// Out of registers: spill the active interval that ends latest.
var last_idx: usize = 0;
for (active.items, 0..) |a, k| {
if (a.end > active.items[last_idx].end) last_idx = k;
}
const victim = active.items[last_idx];
if (victim.end > cur.end) {
// The victim outlives cur -- steal its register, send it to memory.
const r = active_reg.items[last_idx];
loc[cur.vreg] = .{ .reg = r };
loc[victim.vreg] = .{ .spill = next_spill_slot };
next_spill_slot += 1;
spills += 1;
_ = active.orderedRemove(last_idx);
_ = active_reg.orderedRemove(last_idx);
try insertActive(gpa, &active, &active_reg, cur, r);
} else {
// cur itself dies soonest -- spill it directly.
loc[cur.vreg] = .{ .spill = next_spill_slot };
next_spill_slot += 1;
spills += 1;
}
}
}
return .{ .loc = loc, .num_spills = spills, .gpa = gpa };
}
fn insertActive(
gpa: std.mem.Allocator,
active: *std.ArrayList(Interval),
active_reg: *std.ArrayList(usize),
iv: Interval,
reg: usize,
) !void {
var pos: usize = 0;
while (pos < active.items.len and active.items[pos].end < iv.end) pos += 1;
try active.insert(gpa, pos, iv);
try active_reg.insert(gpa, pos, reg);
}
The result for each virtual register is a Location -- either a physical reg index or a spill slot in memory. That union(enum) is doing real work: it makes "lives in a register" and "lives on the stack" two states the type system forces every later stage to handle, so we can never forget that a value might be spilled. The errdefer on loc means a mid-allocation failure frees the partial result and leaks nothing -- the same ownership discipline we have practised all series. And the whole thing is parameterized on num_regs, which lets us do something illuminating in a minute: dial the register count up and down and watch the spills appear and vanish.
To prove the allocation preserves meaning, I execute it on a tiny register machine -- physical registers modelled as an array, spill slots as a second array -- and compare against evaluating the original tree. Reading and writing a value just dispatches on its Location:
fn run(gpa: std.mem.Allocator, p: *const Program, alloc: *const Allocation, num_regs: usize, x: i64) !i64 {
const regs = try gpa.alloc(i64, num_regs);
defer gpa.free(regs);
const slots = try gpa.alloc(i64, alloc.num_spills + 1);
defer gpa.free(slots);
@memset(regs, 0);
@memset(slots, 0);
const read = struct {
fn f(v: VReg, a: *const Allocation, rg: []i64, sl: []i64) i64 {
return switch (a.loc[v]) {
.reg => |r| rg[r],
.spill => |s| sl[s],
};
}
}.f;
const write = struct {
fn f(v: VReg, val: i64, a: *const Allocation, rg: []i64, sl: []i64) void {
switch (a.loc[v]) {
.reg => |r| rg[r] = val,
.spill => |s| sl[s] = val,
}
}
}.f;
for (p.code.items) |ins| {
switch (ins) {
.imm => |i| write(i.dst, i.val, alloc, regs, slots),
.load_x => |i| write(i.dst, x, alloc, regs, slots),
.neg => |i| write(i.dst, -read(i.src, alloc, regs, slots), alloc, regs, slots),
.bin => |i| {
const l = read(i.lhs, alloc, regs, slots);
const r = read(i.rhs, alloc, regs, slots);
const v = switch (i.op) {
.add => l + r,
.sub => l - r,
.mul => l * r,
.div => @divTrunc(l, r),
};
write(i.dst, v, alloc, regs, slots);
},
}
}
return read(p.root, alloc, regs, slots);
}
This interpreter stands in for a real backend: where it reads a spilled value directly, a machine-code emitter would reload it into a scratch register first, and where it reads a register value it would just name that register in the instruction. The allocation decisions are identical either way -- that is the whole point of keeping the allocator target-independent, and it is exactly why LLVM's allocator is a separate pass from its x86 emitter. The oracle we check against is a plain tree-walking evaluator over the original AST -- the simplest thing that is obviously correct:
fn evalAst(e: *const Expr, x: i64) i64 {
return switch (e.*) {
.num => |v| v,
.var_x => x,
.neg => |inner| -evalAst(inner, x),
.bin => |b| switch (b.op) {
.add => evalAst(b.lhs, x) + evalAst(b.rhs, x),
.sub => evalAst(b.lhs, x) - evalAst(b.rhs, x),
.mul => evalAst(b.lhs, x) * evalAst(b.rhs, x),
.div => @divTrunc(evalAst(b.lhs, x), evalAst(b.rhs, x)),
},
};
}
Now the proof, and it is the test I trust most in this whole episode: compile one bushy expression, allocate it under 2, 3, 4 and 8 registers, and check every version against that oracle across a hundred-odd inputs:
test "allocated program matches the AST across many inputs and register counts" {
const gpa = std.testing.allocator;
// ((x*x) + (2*x + 1)) - ((x - 4) * (x + 4)), built by hand.
const xv = Expr{ .var_x = {} };
const two = Expr{ .num = 2 };
const one = Expr{ .num = 1 };
const four = Expr{ .num = 4 };
const xx = Expr{ .bin = .{ .op = .mul, .lhs = &xv, .rhs = &xv } };
const twox = Expr{ .bin = .{ .op = .mul, .lhs = &two, .rhs = &xv } };
const twox1 = Expr{ .bin = .{ .op = .add, .lhs = &twox, .rhs = &one } };
const left = Expr{ .bin = .{ .op = .add, .lhs = &xx, .rhs = &twox1 } };
const xm4 = Expr{ .bin = .{ .op = .sub, .lhs = &xv, .rhs = &four } };
const xp4 = Expr{ .bin = .{ .op = .add, .lhs = &xv, .rhs = &four } };
const right = Expr{ .bin = .{ .op = .mul, .lhs = &xm4, .rhs = &xp4 } };
const root = Expr{ .bin = .{ .op = .sub, .lhs = &left, .rhs = &right } };
for ([_]usize{ 2, 3, 4, 8 }) |k| {
var prog = try buildProgram(gpa, &root);
defer prog.deinit();
var alloc = try linearScan(gpa, &prog, k);
defer alloc.deinit();
var x: i64 = -30;
while (x <= 30) : (x += 1) {
try std.testing.expectEqual(evalAst(&root, x), try run(gpa, &prog, &alloc, k, x));
}
}
}
With only 2 registers the allocator spills hard and the interpreter leans on memory slots; with 8 it never spills at all -- and every single result is identical. That is the guarantee you want from an allocator: it may make the code faster or slower, but it must never change what the code computes.
The parameter num_regs lets us measure the thing register allocation exists to fight -- register pressure. Squeeze the machine and spills climb; give it room and they disappear. This little test pins that behaviour down as a fact, not a feeling:
test "fewer registers spill more, more registers spill less, results identical" {
const gpa = std.testing.allocator;
const xv = Expr{ .var_x = {} };
const a = Expr{ .bin = .{ .op = .mul, .lhs = &xv, .rhs = &xv } };
const b = Expr{ .bin = .{ .op = .add, .lhs = &xv, .rhs = &a } };
const c = Expr{ .bin = .{ .op = .sub, .lhs = &b, .rhs = &a } };
const d = Expr{ .bin = .{ .op = .mul, .lhs = &c, .rhs = &b } };
const root = Expr{ .bin = .{ .op = .add, .lhs = &d, .rhs = &c } };
var prog = try buildProgram(gpa, &root);
defer prog.deinit();
var a2 = try linearScan(gpa, &prog, 2);
defer a2.deinit();
var a8 = try linearScan(gpa, &prog, 8);
defer a8.deinit();
try std.testing.expect(a2.num_spills >= a8.num_spills);
try std.testing.expectEqual(@as(usize, 0), a8.num_spills);
try std.testing.expectEqual(evalAst(&root, 5), try run(gpa, &prog, &a2, 2, 5));
try std.testing.expectEqual(evalAst(&root, 5), try run(gpa, &prog, &a8, 8, 5));
}
This is the exact tradeoff a real compiler navigates. Values that stay live across a lot of code -- a here gets reused three times -- are the ones that fight over the scarce registers, and when there are not enough, something has to visit memory. It is also why hand-writing tight assembly is so fiddly: a human is doing this bookkeeping in their head, and the compiler does it perfectly every time.
Linear scan is the pragmatic favourite, but there is a second, deeper way to see the very same problem -- and it is the one that reveals why register allocation is genuinely hard. Build a graph with one node per value and an edge between any two values whose live intervals overlap (they "interfere" -- they cannot share a register). Now assigning registers is exactly graph coloring: give each node a color (a register) such that no two connected nodes share one. The minimum number of colors you need is the graph's chromatic number, and the number of physical registers is how many colors you are allowed -- if the graph needs more colors than you have registers, you must spill. A greedy coloring makes the idea concrete:
fn overlaps(a: Interval, b: Interval) bool {
return a.start <= b.end and b.start <= a.end;
}
fn colorGraph(gpa: std.mem.Allocator, p: *const Program) ![]usize {
const intervals = try computeIntervals(gpa, p);
defer gpa.free(intervals);
const n = p.nvregs;
const color = try gpa.alloc(usize, n);
for (0..n) |v| color[v] = std.math.maxInt(usize);
const used = try gpa.alloc(bool, n);
defer gpa.free(used);
for (0..n) |v| {
@memset(used, false);
for (0..n) |u| {
if (u == v) continue;
if (color[u] != std.math.maxInt(usize) and overlaps(intervals[v], intervals[u])) {
used[color[u]] = true; // a neighbour already took this color
}
}
var col: usize = 0;
while (used[col]) col += 1; // smallest color no neighbour uses
color[v] = col;
}
return color;
}
And the property that makes a coloring valid is precisely the one we test -- no two interfering values ever land on the same color:
test "greedy coloring is valid: no two interfering vregs share a color" {
const gpa = std.testing.allocator;
const xv = Expr{ .var_x = {} };
const three = Expr{ .num = 3 };
const t1 = Expr{ .bin = .{ .op = .mul, .lhs = &xv, .rhs = &xv } };
const t2 = Expr{ .bin = .{ .op = .add, .lhs = &t1, .rhs = &three } };
const root = Expr{ .bin = .{ .op = .sub, .lhs = &t2, .rhs = &xv } };
var prog = try buildProgram(gpa, &root);
defer prog.deinit();
const color = try colorGraph(gpa, &prog);
defer gpa.free(color);
const intervals = try computeIntervals(gpa, &prog);
defer gpa.free(intervals);
for (0..prog.nvregs) |u| {
for (u + 1..prog.nvregs) |v| {
if (overlaps(intervals[u], intervals[v]))
try std.testing.expect(color[u] != color[v]);
}
}
}
Here is the punchline that connects the two lenses: general graph coloring is NP-complete, so the optimal allocation is, in the worst case, genuinely intractable -- and that is why linear scan (a fast, greedy approximation) exists at all. The two views are the same coin: an interval sweep and a graph coloring are two ways of asking "which of these values can share a home?". Real compilers pick their algorithm based on how much time they can spend, which brings us neatly to how the grown-ups do it.
Everything here is the real architecture in miniature. LLVM -- the backend behind Clang and Rust's rustc -- ran a classic linear scan for years and today uses a more sophisticated greedy allocator that splits live ranges and re-tries, but the bones are exactly what you just built: intervals, a priority for who gets a register, and spill code when it runs dry. Classic graph-coloring allocation (the Chaitin-Briggs algorithm) is the other giant of the field, used in GCC and many others, and it is the interference-graph view taken all the way, with clever "coalescing" to erase needless moves. The JavaScript engines -- V8, and the JVM's HotSpot -- lean on linear scan precisely because it is fast, and a JIT compiling on the hot path cannot afford to solve an NP-complete problem for every function. Go's compiler does its own register allocation over an SSA form, tuned, like the rest of Go's toolchain, for compile speed over squeezing out the last cycle.
The honest gap between our allocator and a production one is not the algorithm -- it is the constraints. Real machines are not the clean "any value in any register" world we modelled. Remember episode 144's division? x86's idiv demands its dividend in rax and clobbers rdx, whether the allocator likes it or not. Some instructions are two-address (the destination must be one of the sources). Calling conventions pin arguments to specific registers and mark some registers caller-saved, some callee-saved. A real allocator threads all of these "pre-colored" and "clobbered" constraints through the same interval-and-interference machinery you just wrote -- which is why the field has been an active research area for forty years and shows no sign of being "done". But the mental model in your hands right now -- values have intervals, overlapping intervals interfere, allocation is coloring, and you spill when you cannot color -- is the model. Everything else is engineering on top of it.
A naive "spill everything" allocator. Write an allocator that puts every virtual register in its own spill slot and uses zero registers, then run it through the same interpreter and confirm it still computes correct results. Now compare its spill count against linearScan on the bushy expression from the tests. You will have measured, concretely, exactly how much work register allocation saves -- and you will appreciate why "correct but slow" (our stack machine) and "correct and fast" are separated by precisely this pass.
Register coalescing. When the IR contains a pure move (imagine adding a mov: struct { dst: VReg, src: VReg } instruction), the destination and source can often share the same register, making the move vanish entirely. Extend the interference-graph view: if two move-related values do not interfere, give them the same color and delete the move. Measure how many instructions disappear. This is one of the biggest real-world wins in production allocators, and you now have the machinery to see why.
Model a hardware constraint. Give your IR a div that, like x86, must produce its result in physical register 0 and destroys register 1. Teach linearScan to honour a "pre-colored" result and to treat register 1 as clobbered across each division (spill whatever lived there). Prove with a differential test that the constrained allocation still matches the AST. When it passes, you will have felt the exact wrinkle that separates a textbook allocator from one that can actually target a real chip.
That is register allocation, from the tension that motivates it -- infinitely many values, a handful of registers -- all the way to a working linear-scan allocator with spilling, a second view through graph coloring, and a differential test that proves the allocated program means exactly what the tree meant. We now have every piece of a real compiler laid out on the bench: a lexer, a parser, an AST, a type checker, bytecode and a VM, a JIT, a code generator, and now the allocator that makes generated code fast. Next time we start putting these pieces to work on something you can actually run and play with. Thanks for reading -- and happy allocating! ;-)
@scipio