A Simple Code Generator
We have carved the program into
basic blocks.
Now comes the moment the whole front end was building toward: turning a block of three-address code
into actual machine instructions. The naïve way — load both operands, do the op, store the
result, for every single statement — works, but it is embarrassingly slow: memory traffic
everywhere, registers touched and immediately abandoned. The simple code generator
of the Dragon Book does far better with one modest ambition: keep values in registers as
long as they are useful, and touch memory only when you must.
To pull that off, the generator maintains a running picture of where every value currently
lives. It answers two questions at every step — "which registers hold a copy of variable
x?" and "where can I find an up-to-date value of
x?" — and it uses next-use information to decide which
registers it is safe to reuse. Get those bookkeeping structures right and good code almost falls
out.
Two descriptors track reality
- a register descriptor records, for each register, the set of variables whose
current value is held there (a register may hold several at once, e.g. right after a copy);
- an address descriptor records, for each variable, all the locations where its
current value can be found — some register, its memory home, or both.
These two are inverse views of the same fact and must be kept consistent: if the
register descriptor says R1 holds x, then
x's address descriptor must list R1, and vice versa. Every
instruction the generator emits is immediately followed by a small descriptor update. The
discipline of updating both, correctly, after every instruction is the skill of writing a
code generator — most bugs are a descriptor that quietly drifted out of sync with the code actually
emitted.
Next-use: when is a value dead?
Before generating code, we scan the block backward and annotate each use of each
variable with its next use — the location of the next instruction in the block that
reads it — or the tag dead if no later instruction in the block reads it. A value
that is dead (and not live on exit from the block, i.e. not needed by a successor block)
does not need to be preserved: its register can be scavenged freely, and it never needs storing back
to memory.
This single piece of information is what turns a memory-thrashing translator into a decent one. If
t is a compiler-generated temporary computed into a register and dead
immediately after, we simply leave the result in that register and reuse it — no load, no store, no
wasted instruction. The backward scan is why we work one block at a time: within a block,
next-use is a purely local, single-pass computation.
The getReg heuristic and the code-gen rule
To emit code for x = y \;\text{op}\; z, the generator calls
getReg to choose a register R to hold the
result, then arranges for y and z to be in
registers, emits OP R, Ry, Rz, and updates the descriptors. getReg picks a
register by a small priority list:
- if y is already in a register R_y that
holds only y, and y is
dead after this instruction — reuse R_y (the result
lands right on top of the operand);
- otherwise, if there is an empty register, take it;
- otherwise spill: pick an occupied register, store its variables to memory if
those values are not already safe, and steal it.
The full statement rule then reads: get registers for the operands (loading from memory if needed),
emit the operation, mark the result as living only in R
(its memory copy is now stale), and — if any operand was a variable that is now dead — free its
register in the descriptors. At the end of the block, any variable that is live on exit but
currently only in a register must be stored back to its memory home.
Worked example: d = (a-b) + (a-c) + (a-c)
This is the Dragon Book's set piece. The block compiles to four TAC statements; assume
a, b, c live in memory on entry and only d is
live on exit, with two registers R1, R2 available. Here
t, u, v are temporaries, each dead right after its last use:
t = a - b, \quad u = a - c, \quad v = t + u, \quad d = v + u.
Following the descriptors instruction by instruction gives this trace — watch how
a stays cached in R2 and gets reused, and how
R1 is recycled the moment a temporary dies:
| TAC | Emitted code | R1 holds | R2 holds | Note |
|---|
| t = a - b | LD R1,a; LD R2,b; SUB R1,R1,R2 | t | b | result in R1 |
| u = a - c | LD R2,a; SUB R2,R2,c* | t | u | reload a into R2, subtract c |
| v = t + u | ADD R1,R1,R2 | v | u | t dead → reuse R1; u still live |
| d = v + u | ADD R1,R1,R2 | d | u | v dead → reuse R1 |
| block exit | ST d,R1 | d | — | d live on exit → store |
No load appears unless a value is genuinely needed from memory, and the only store is the single
one demanded by d's liveness. That is the whole game: registers held as
long as they pay, memory touched as little as the semantics allow.
A generator you can run
The code below is a compact but honest version: two descriptor maps, a getReg that
prefers a dead operand's register then an empty one then spills, and the per-statement rule that
emits loads, the operation, and the final live-on-exit stores. It compiles the block above and
prints the emitted pseudo-assembly.
type Reg = "R1" | "R2";
const REGS: Reg[] = ["R1", "R2"];
// regHolds[R] = variables currently in R. addr[v] = places holding v ("mem" or a register).
const regHolds: Record<Reg, Set<string>> = { R1: new Set(), R2: new Set() };
const addr: Record<string, Set<string>> = {};
const code: string[] = [];
const isTemp = (v: string) => /^[tuv]$/.test(v); // temporaries are dead after last use
function place(v: string): Set<string> {
if (!(v in addr)) addr[v] = new Set([isTemp(v) ? "" : "mem"]);
return addr[v];
}
function emit(line: string) { code.push(line); }
// Ensure variable v is in some register; return that register.
function intoReg(v: string): Reg {
for (const R of REGS) if (regHolds[R].has(v)) return R; // already resident
const R = getReg(v);
emit(`LD ${R}, ${v}`);
regHolds[R] = new Set([v]);
place(v).add(R);
return R;
}
// Choose a register to define `target`.
function getReg(target: string): Reg {
for (const R of REGS) if (regHolds[R].size === 0) return R; // empty register
// Spill the register whose variable has a safe memory copy (or store it first).
for (const R of REGS) {
for (const held of regHolds[R]) {
if (!place(held).has("mem") && held !== target) { emit(`ST ${held}, ${R} (spill)`); place(held).add("mem"); }
}
regHolds[R] = new Set();
place(target); // ensure record exists
return R;
}
return "R1";
}
// x = y op z
function gen(x: string, y: string, op: string, z: string, deadAfter: string[]) {
const Ry = intoReg(y);
const Rz = intoReg(z);
const Rx = Ry; // define result on top of the (assumed dead) left operand's register
emit(`${op} ${Rx}, ${Ry}, ${Rz}`);
// Result x now lives ONLY in Rx; its memory copy is stale.
for (const R of REGS) regHolds[R].delete(x);
regHolds[Rx] = new Set([x]);
addr[x] = new Set([Rx]);
// Free registers of operands that are now dead.
for (const d of deadAfter) {
for (const R of REGS) if (regHolds[R].has(d) && d !== x) regHolds[R].delete(d);
}
}
// d = (a-b)+(a-c)+(a-c) as t=a-b; u=a-c; v=t+u; d=v+u
gen("t", "a", "SUB", "b", ["a", "b"]);
gen("u", "a", "SUB", "c", ["a", "c"]);
gen("v", "t", "ADD", "u", ["t"]);
gen("d", "v", "ADD", "u", ["v", "u"]);
// d is live on exit: store it back.
for (const R of REGS) if (regHolds[R].has("d")) emit(`ST d, ${R}`);
console.log(code.join("\n"));
The exact instructions differ a little from the hand trace (a real generator's getReg
is smarter about which operand to reuse), but the shape is identical: a handful of loads, the
arithmetic, and one closing store. Tinker with the deadAfter lists and watch the store
traffic change — that is next-use information steering the whole thing.
Inside a single block, next-use tells you when a temporary dies. But at the edge of the
block, control leaves for a successor — and any variable a successor might read is
live on exit, so its latest value must actually exist in memory when the block
ends. That is why the generator issues closing ST instructions only for live-on-exit
variables currently stranded in registers. Compute liveness too conservatively (mark everything
live) and you drown the block in needless stores; compute it wrong (mark a needed value dead) and a
successor reads stale memory. Correct
liveness
is what makes register-resident code both fast and correct.
When getReg finds no free register it must spill — but you cannot just
overwrite a register. First check the victim's address descriptor: if its value is only in
that register (no memory copy), you must emit a ST to save it, then update the
descriptor to record that memory now holds it. Skip the store and you have silently destroyed a live
value.
The subtler, more common bug is descriptor drift. After emitting
OP R, Ry, Rz you must do all of: remove the old occupant(s) of
R, record that R now holds only the result,
set the result's address descriptor to just R (its memory copy is now
stale!), and drop any dead operand from its register. Forget the "memory copy is now stale" step and
a later spill will "helpfully" skip storing a value that memory no longer actually has — a classic,
maddening miscompile. Update both descriptors, fully, after every instruction.