A chef can have a beautiful recipe, but the kitchen decides how the cooking actually goes: only a few burners, a fridge across the room, and every trip to the fridge costs time. A good cook keeps the ingredients they will need again right on the counter and puts away the ones they are finished with.
The code generator is the compiler's cook. Its recipe is the optimized intermediate code from the previous chapters. Its kitchen is the target machine: a handful of fast registers (the burners and counter) and a large but slow memory (the fridge). Its job is to turn three-address code into real machine instructions, choosing good instructions and keeping the right values in registers.
Code generation is the final phase of a compiler. It maps the intermediate representation to an equivalent target program (machine or assembly code), selecting instructions, deciding which values live in registers (register allocation) and in which registers (register assignment), and fixing the order of evaluation. The output must be correct, and should make good use of the target machine's resources.
We will look at the design issues, define a simple target machine with a cost model, follow a simple register-aware code generator through a basic block with full descriptor tables, generate optimal code for expression trees using Ershov numbers (with and without enough registers), and finally allocate registers for a whole fragment by graph colouring. Every piece of generated code in this chapter was executed in a small simulator and checked against the source computation on hundreds of random inputs.
Issues in the Design of a Code Generator
1. Input to the code generator
The input is the intermediate representation (three-address code, quadruples, syntax trees, DAGs) together with the symbol table, which gives the type, size and run-time address (for example, offset in the activation record) of every name. We assume the front end has already done type checking and inserted conversions, so the input is free of errors.
2. The target program
Output form | Advantage | Disadvantage |
|---|---|---|
Absolute machine code | Can be loaded at a fixed address and run immediately | Not relocatable; no separate compilation |
Relocatable machine code (object files) | Modules compiled separately and combined by the linker | Needs linking and relocation |
Assembly language | Easiest to generate and read; the assembler handles encoding | An extra assembly step |
Real compilers like GCC emit assembly and let the assembler (as) produce object files, as described in Language Processors: Interpreter, Assembler, Linker & Loader.
3. Instruction selection
There are usually many instruction sequences that do the same job, with different costs. Translating each three-address statement with a fixed template is easy but wasteful:
x = y + z LD R0, y
ADD R0, R0, z
ST x, R0
w = x - 1 LD R0, x // redundant: R0 already holds x
SUB R0, R0, #1
ST w, R0Also, a statement like a = a + 1 could be a single INC a on a machine that has it. Good selection needs to know the instruction set and its costs. Modern compilers treat it as tree pattern matching: cover the IR tree with tiles, each tile being one machine instruction, at minimum total cost.
4. Register allocation and assignment
Registers are the fastest storage but few in number. Two separate questions arise:
Register allocation: which values should be kept in registers at each point?
Register assignment: which specific register should each of those values use?
Finding an optimal assignment is NP-complete in general (it contains graph colouring), so compilers use good heuristics. Some machines add constraints, such as an instruction that needs its operands in an even/odd register pair, or a multiply that always writes to fixed registers.
5. Evaluation order
The order in which computations are done affects how many registers are needed. Some orders need fewer registers and fewer stores to memory. Picking the best order is also hard in general, but for expression trees there is an optimal algorithm (Ershov numbers, below).
A Simple Target Machine
We use a load/store register machine with registers R0, R1, R2, ... and these instructions:
Instruction | Meaning |
|---|---|
| Load the value at addr into register dst |
| Store register src into location x |
| OP is ADD, SUB, MUL ...; dst = src1 OP src2 |
| Unconditional jump; conditional jump on register r (e.g. BLTZ: jump if r < 0) |
Addressing modes
Mode | Form | Value or location referred to | Extra cost |
|---|---|---|---|
Register |
| The register itself | 0 |
Direct (variable) |
| Memory location of x | 1 |
Indexed |
| Location a + contents(R2) (array element a[i] with byte offset in R2; or a field at offset 8 from a pointer in R2) | 1 |
Indirect |
| Location whose address is in R2 (like *p) | 0 |
Indirect indexed |
| Location whose address is stored at 8 + contents(R2) | 1 |
Immediate |
| The constant 5 itself | 1 |
Cost model
The cost of an instruction is 1 (for the instruction word) plus 1 for each operand that uses a memory address or a constant, because that address or constant occupies an extra word that must be fetched. Register and plain indirect-register operands add nothing.
Instruction | Cost | Why |
|---|---|---|
| 1 | All registers |
| 2 | Address of x is an extra word |
| 2 | Same |
| 2 | Constant 1 is an extra word |
| 1 | Indirect through a register: no extra word |
| 2 | The offset 8 is an extra word |
The cost roughly measures both code size and time (instruction fetches). Minimising it means keeping values in registers and avoiding loads and stores, which is exactly what the rest of this chapter is about. For the template code shown earlier: 6 instructions, cost 2+2+2+2+2+2 = 12. Just deleting the redundant load gives 5 instructions with cost 10.
A Simple Code Generator for a Basic Block
This generator works one basic block at a time and keeps values in registers as long as possible. It relies on two tables and one piece of liveness information.
Register descriptor: for each register, the variables whose current value it holds. Initially all registers are empty.
Address descriptor: for each variable, all the places where its current value can be found: its memory location, one or more registers, or both.
Next-use information: for each statement, whether each variable it touches will be used again later in the block (or is live on exit). This is computed by one backward scan of the block, just like liveness in Data-Flow Analysis.
The algorithm
For each statement x = y op z :
1. Choose registers with getReg: Ry for y, Rz for z, Rx for x.
2. If y is not already in Ry: emit LD Ry, y' (y' = a current location of y)
If z is not already in Rz: emit LD Rz, z'
3. Emit OP Rx, Ry, Rz
4. Update descriptors: Rx now holds only x; x's address descriptor
becomes {Rx} (the memory copy of x is now stale);
remove Rx from every other variable's address descriptor.
For a copy x = y :
If y is not in a register, LD it into some Ry.
Add x to Ry's register descriptor; x's address descriptor becomes {Ry}.
(No instruction is needed when y is already in a register.)
At the end of the block:
For every variable x that is live on exit and whose memory copy is stale,
emit ST x, R for a register R holding x.The getReg function
Choosing Ry (for an operand y):
If y is already in a register, use it.
Otherwise, if some register is empty, use it.
Otherwise pick a register R that can be overwritten safely. R is safe if, for every variable v it holds: v also lives somewhere else (memory or another register), or v is x (the result, about to be overwritten anyway) and not the other operand, or v is dead (no next use). If no register is safe, pick the one needing the fewest stores, emit
ST v, Rfor each v it holds (this is a spill), and use it.
Choosing Rx (for the result): any register holding only x works; and if y has no next use and Ry holds only y, then Ry can be reused for x (similarly for z). Otherwise use the same rules as above.
Worked Example: Generating Code with Descriptors
Generate code for this block with three registers R1, R2, R3. Variables w, x, y, z are live on exit; t1 and t2 are temporaries (dead on exit).
(1) t1 = x - y
(2) t2 = x + z
(3) w = t1 * t2
(4) x = y
(5) z = w - t2Next-use facts (from a backward scan):
After statement | Still needed later | No longer needed (dead) |
|---|---|---|
(1) | x (in 2), y (in 4), t1 (in 3) | - |
(2) | t1 (3), t2 (3, 5) | x (overwritten by 4 before any use), z (overwritten by 5) |
(3) | w (5, and on exit), t2 (5) | t1 |
(4) | x, y (on exit) | - |
(5) | w, x, y, z (on exit) | t2 |
Trace:
Stmt | Code emitted | R1 | R2 | R3 | Address descriptors (changed) |
|---|---|---|---|---|---|
(1) t1 = x - y | LD R1, x | x | y | t1 | x: x, R1 |
(2) t2 = x + z | LD R2, z | t2 | z | t1 | x: x |
(3) w = t1 * t2 | MUL R3, R3, R1 | t2 | z | w | t1: (none) |
(4) x = y | LD R2, y | t2 | y, x | w | y: y, R2 |
(5) z = w - t2 | SUB R1, R3, R1 | z | y, x | w | z: R1 |
end | ST w, R3 | z | y, x | w | w: w, R3 |
The reasoning at each step:
(1) x and y are not in registers, and R1, R2 are free: load them. For t1, neither R1 nor R2 can be reused, because x and y are both needed later. R3 is free, so t1 goes there.
(2) x is in R1. z needs a register but none is free. R1 holds x, which is the other operand (cannot touch). R3 holds t1, which exists nowhere else and is still needed (would need a store). R2 holds y, which also has an up-to-date copy in memory: safe. So
LD R2, z. For t2: x has no next use and R1 holds only x, so reuse R1. The memory copy of x is still correct, so nothing is lost.(3) t1 has no next use and R3 holds only t1, so w reuses R3.
(4) A copy. y is not in a register any more (R2 was reused in step 2), so we load it. R2 is the safe choice: it holds z, which is dead and also in memory. Then x simply joins R2. No instruction is needed for the copy itself. Note that x's memory location is now stale.
(5) w is in R3 and t2 in R1. t2 has no next use, so z reuses R1. (We cannot reuse R3: w is still live.)
End: w, x and z are live on exit and exist only in registers, so they are stored. y's memory copy is current, so no store is needed for y.
The final code has 11 instructions: 4 loads (cost 2 each), 4 register operations (cost 1 each) and 3 stores (cost 2 each), for a total cost of 8 + 4 + 6 = 18. A naive translation that loads every operand and stores every result (including t1 and t2) would need 18 instructions with cost 32. The simulator confirmed that the generated code leaves w, x, y and z with exactly the values the source block computes.
Optimal Code for Expression Trees: Ershov Numbers
For a single expression (a tree, no shared subexpressions), we can compute the exact minimum number of registers needed and generate code that achieves it. The idea: evaluate the subtree that needs more registers first, while all registers are free; then it only occupies one register (its result) while the other subtree is evaluated.
Labelling the tree
Ershov number (label) of a node: every leaf gets 1 (it must be loaded into a register). An interior node whose two children have labels l1 and l2 gets max(l1, l2) if l1 ≠ l2, and l1 + 1 if l1 = l2. The label of the root is the minimum number of registers needed to evaluate the tree without storing intermediate results.
Why +1 only when the labels are equal? Suppose the left subtree needs 3 registers and the right needs 2. Evaluate the left first using 3 registers; afterwards its result occupies just one register, and the right subtree needs 2 more: 1 + 2 = 3, so 3 registers are enough. Now suppose both need 3. Whichever goes first, its result occupies one register while the other subtree needs 3 more, so 4 are required.
(Older textbooks, in the Sethi-Ullman algorithm, label a right leaf 0 because their machines allow an operation with one operand in memory, like ADD R1, x. On a load/store machine like ours every leaf needs a register, so every leaf gets 1. Check which convention a question uses.)
Example: (a * b) - ((c + d) * (e - f))
- [3]
/ \
* [2] * [3]
/ \ / \
a [1] b [1] + [2] - [2]
/ \ / \
c [1] d [1] e [1] f [1]
a*b: children 1,1 equal → 2
c+d, e-f: children 1,1 equal → 2
(c+d)*(e-f): children 2,2 → 3
root: children 2,3 differ → max = 3So 3 registers suffice, and no order can do it with fewer without storing to memory.
Generating the code (enough registers)
gencode(n, base b): uses registers Rb, Rb+1, ..., result in R(b+k-1), k = label(n)
leaf x: LD Rb, x
children with equal labels: gencode(right, b+1); gencode(left, b);
OP R(b+k-1), R(b+k-2), R(b+k-1)
unequal labels: gencode(bigger child, b); gencode(smaller child, b);
OP R(b+k-1), (left result), (right result)Running this (with base 1) on our tree produced:
LD R3, f
LD R2, e
SUB R3, R2, R3 // R3 = e - f
LD R2, d
LD R1, c
ADD R2, R1, R2 // R2 = c + d
MUL R3, R2, R3 // R3 = (c + d) * (e - f)
LD R2, b
LD R1, a
MUL R2, R1, R2 // R2 = a * b
SUB R3, R2, R3 // R3 = a*b - (c+d)*(e-f) result in R311 instructions: 6 loads (one per leaf) and 5 operations (one per operator), with no stores at all. That is the least possible, and only R1, R2 and R3 are used. The right subtree (label 3) was evaluated first because it is "bigger"; doing a * b first would have tied up a register and forced a fourth.
When there are not enough registers
With only r registers, a node whose two children both have labels ≥ r cannot be done without memory. The rule: evaluate the right (or bigger) child using all r registers, store its result to a temporary in memory, evaluate the other child, then load the temporary back and combine. With r = 2 on the same tree, the generator produced (and the simulator verified):
LD R2, f
LD R1, e
SUB R2, R1, R2 // e - f
ST T1, R2 // spill: both children of * have label 2 = r
LD R2, d
LD R1, c
ADD R2, R1, R2 // c + d
LD R1, T1
MUL R2, R2, R1 // (c + d) * (e - f)
ST T2, R2 // spill: root's children have labels 2 and 3, both >= r
LD R2, b
LD R1, a
MUL R2, R1, R2 // a * b
LD R1, T2
SUB R2, R2, R1 // result in R215 instructions instead of 11: two stores and two extra loads. This label-driven strategy (due to Sethi and Ullman) is known to give optimal code for expression trees without shared subexpressions on this kind of register machine.
Global Register Allocation by Graph Colouring
The simple generator above works one block at a time and stores everything at block ends. To keep variables in registers across a whole function, compilers use graph colouring, introduced by Chaitin.
Compute liveness at every point (see Data-Flow Analysis).
Build the interference graph: one node per variable (or live range); an edge between two variables if one is live at a point where the other is defined. Interfering variables cannot share a register.
Colour the graph with k colours, where k is the number of registers, so that neighbours get different colours. Each colour is a register.
If colouring fails, spill some variable: keep it in memory, load it before each use and store it after each definition, rebuild the graph and try again.
Colouring with k colours is NP-complete for k ≥ 3, so Chaitin's heuristic is used:
Simplify: a node with fewer than k neighbours can always be coloured, whatever colours its neighbours get. Remove it and push it on a stack. Repeat.
Spill: if every remaining node has k or more neighbours, choose one as a spill candidate (cheap to spill, many neighbours), remove it and continue.
Select: pop the nodes one by one and give each the lowest colour not used by its already-coloured neighbours. A spill candidate may still get a colour (optimistic colouring, Briggs); if it does not, it is actually spilled.
Worked example
live before live after
(1) a = p + q {p, q} {a, p}
(2) b = a * 2 {a, p} {a, b, p}
(3) c = p - b {a, b, p} {a, b, c}
(4) d = a + c {a, b, c} {b, c, d}
(5) e = d * b {b, c, d} {c, e}
(6) f = e + c {c, e} {f}
(7) return f {f} { }Interference edges (a defined variable versus everything else live right after its definition, plus p–q which are live together on entry):
p–q a–p a–b b–p a–c b–c b–d c–d c–e (9 edges)
Degrees: a 3 b 4 c 4 d 2 e 1 f 0 p 3 q 1
q ---- p
| \
a -- b -- d
\ | /
\ | /
c ---- e f (isolated)Note that f does not interfere with e or c: both die in statement (6) exactly where f is born, so f can reuse one of their registers.
Colouring with k = 3. Our implementation of the heuristic removed nodes in this order, each having fewer than 3 neighbours at the time of removal: f (0), e (1), q (1), d (2), c (2), a (2), b (1), p (0). No spill was needed. Popping in reverse order and choosing the lowest free register:
Pop | Already-coloured neighbours | Register |
|---|---|---|
p | - | R1 |
b | p (R1) | R2 |
a | b (R2), p (R1) | R3 |
c | a (R3), b (R2) | R1 |
d | b (R2), c (R1) | R3 |
q | p (R1) | R2 |
e | c (R1) | R2 |
f | - | R1 |
Rewriting the fragment with these registers (p arrives in R1, q in R2):
ADD R3, R1, R2 // a = p + q
MUL R2, R3, #2 // b = a * 2
SUB R1, R1, R2 // c = p - b
ADD R3, R3, R1 // d = a + c
MUL R2, R3, R2 // e = d * b
ADD R1, R2, R1 // f = e + c result in R1Eight variables share three registers with no loads or stores, and the simulator confirmed the result equals the original computation. Three is also the minimum: a, b and c form a triangle (all three are live together after statement 3), so no 2-colouring exists.
With k = 2, simplification gets stuck after removing f, e and q: every remaining node has at least 2 neighbours. The heuristic picks b (the highest degree, 4) as the spill candidate, and when the stack is popped b finds no free colour, so b is really spilled. The compiler inserts ST after b's definition and LD before its uses, recomputes liveness and tries again, spilling more if needed.
Other allocators
Approach | Idea | Where used |
|---|---|---|
Local (per block) with descriptors | Keep values in registers inside a block; store live values at block end | Simple or fast compilers |
Usage counts | Give registers to the variables used most in a loop | Classic loop-based allocation |
Graph colouring (Chaitin, Briggs) | Interference graph + simplify/spill/select | GCC's integrated register allocator (IRA) and many other optimizing compilers |
Linear scan | Sort live intervals by start; walk once, spilling the interval that ends furthest away when out of registers | JIT compilers (fast allocation) |
Solved Problems
Problem 1: Minimum registers for straight-line code
Assume each result may be placed in a register freed by one of its operands in the same instruction. What is the minimum number of registers needed, without spilling, for:
x = a + b
y = x * c
z = y - a
w = z + x
return wSolution. Compute liveness backwards:
Statement | Live before | Live after |
|---|---|---|
x = a + b | {a, b, c} | {a, c, x} |
y = x * c | {a, c, x} | {a, x, y} |
z = y - a | {a, x, y} | {x, z} |
w = z + x | {x, z} | {w} |
At most 3 values are live at any point, so 3 registers are needed and enough (for straight-line code the interference graph is an interval graph, whose colouring number equals its maximum clique).
Problem 2: Ershov number
How many registers are needed to evaluate a + b * (c - d) without storing intermediate values?
Solution. c - d: 2. b * (c - d): children 1 and 2, unequal → 2. Root: children 1 (a) and 2 → 2. Two registers. The generated code evaluates the bigger subtree first: LD R2, d; LD R1, c; SUB R2, R1, R2; LD R1, b; MUL R2, R1, R2; LD R1, a; ADD R2, R1, R2.
Problem 3: Instruction cost
Find the cost of: LD R1, a; LD R2, b; ADD R1, R1, R2; SUB R1, R1, #4; ST c, R1.
Solution. 2 + 2 + 1 + 2 + 2 = 9. The loads and store each have a memory address word; the SUB has a constant word.
Problem 4: Why evaluation order matters
For (a + b) - (c + (d + e)), compare evaluating the left subtree first versus the right subtree first.
Solution. Labels: a + b = 2; d + e = 2; c + (d + e) = 2 (children 1 and 2); root: children 2 and 2 → 3. With equal labels, either order needs 3 registers, so here the order does not matter. Contrast a - (b * (c + d)): labels 1 and 2 at the root, giving 2. Evaluating the right side first needs 2 registers; evaluating the leaf a first would hold a in a register while the right side needs 2 more, using 3. The rule "bigger label first" is what saves the register.
Common Mistakes
Confusing allocation with assignment. Allocation decides which values get registers; assignment decides which register each one gets.
Forgetting the end-of-block stores. Values that are live on exit and only in registers must be written back. Temporaries that are dead need not be.
Overwriting a register whose value exists nowhere else. getReg must check the address descriptor before reusing a register, or spill first.
Mixing up Ershov conventions. On a load/store machine every leaf has label 1; in the older Sethi-Ullman version a right leaf has label 0. The answers differ by one in some questions.
Adding 1 when child labels differ. Only equal labels increase the count.
Drawing interference edges between variables that are merely used in the same statement. In
f = e + c, if e and c die there, f does not interfere with them.Counting only instructions as cost. In the standard model, memory addresses and constants add to the cost.
Interview and Exam Questions
What are the main issues in code generator design?
The input IR and symbol table, the form of the target program, instruction selection, register allocation and assignment, and the order of evaluation. The overriding requirement is correctness.
What are register and address descriptors?
A register descriptor records which variables' current values each register holds. An address descriptor records, for each variable, all locations (memory, registers) where its current value can be found. The simple code generator uses them to avoid redundant loads and stores.
Why is register allocation hard?
Optimal allocation is NP-complete because it includes graph colouring. Machine constraints (register pairs, fixed registers for some instructions) make it harder still, so compilers use heuristics.
What is an interference graph?
A graph with one node per variable or live range, and an edge between two nodes that are live at the same time (one is live where the other is defined). A k-colouring gives a valid assignment to k registers.
What is spilling?
Keeping a variable in memory instead of a register when there are not enough registers: storing it after definitions and loading it before uses. Spill code costs time, so the allocator spills values that are cheap to spill and used rarely.
What does the Ershov number of an expression tell you?
The minimum number of registers needed to evaluate the tree without storing intermediate results. Evaluating the child with the larger label first achieves it.
How does linear scan differ from graph colouring?
Linear scan sorts live intervals and allocates in one pass, which is fast and suits JIT compilers, but usually gives somewhat worse code than graph colouring, which considers the whole interference structure.
How is instruction cost measured in the textbook model?
1 per instruction plus 1 for each memory address or constant operand, since those take an extra word. LD R1, x costs 2; ADD R1, R2, R3 costs 1.
Summary
The code generator turns IR into target code; its main tasks are instruction selection, register allocation and assignment, and choosing the evaluation order.
In the standard cost model, an instruction costs 1 plus 1 per memory address or constant operand, so loads and stores are what to avoid.
The simple code generator uses register and address descriptors, next-use information and getReg; our 5-statement block became 11 instructions of total cost 18.
Ershov numbers give the minimum registers for an expression tree; evaluating the bigger child first achieves it. With too few registers, the algorithm stores one subtree's result and reloads it (15 instead of 11 instructions in our 2-register example).
Graph colouring allocates registers globally: liveness gives the interference graph, Chaitin's simplify/spill/select colours it. Our 8-variable fragment fit in 3 registers with no memory traffic.
After code generation, Peephole Optimization cleans up the remaining local inefficiencies, and the output goes to the assembler and linker. That completes the journey from source text to machine code.