Code Generation and Register Allocation With easy examples.

Code generation is the compiler phase that translates the program's intermediate representation (IR) into real machine code for the target processor. Register allocation decides which variables live in the CPU's registers — the handful of ultra-fast storage slots inside the processor — and which spill to slower memory. Together they turn abstract code into the instructions a chip actually executes.

They matter because they largely decide how fast compiled programs run. A clever allocator keeps hot variables in registers and avoids slow memory traffic; poor code generation wastes the processor's capabilities. Every C, C++, Rust or Java program you run passed through these phases.

Key Concepts

• Intermediate representation (IR): the compiler's machine-independent form of the program (like LLVM IR), lowered to target instructions by code generation.
• Instruction selection: choosing which machine instructions implement each IR operation, often by pattern-matching over the IR.
• Register: fast on-chip storage; a CPU has only a small fixed number (e.g. 16 general-purpose registers on x86-64), so they must be shared.
• Live range: the instruction span over which a variable's value is needed. Overlapping live ranges cannot share a register.
• Interference graph: one node per variable, edges between overlapping live ranges — colouring it with k colours assigns k registers.
• Spilling: when variables outnumber registers, some are stored to the stack and reloaded when needed, costing extra instructions.

How It Works

Graph-colouring register allocation runs in four steps. First, liveness analysis computes which variables are live at every point. Second, the compiler builds the interference graph, connecting variables live at the same time. Third, it colours the graph with as many colours as registers, using a simplify-and-select heuristic: repeatedly remove a node with fewer neighbours than registers, then assign colours in reverse. Fourth, if a node cannot be coloured, a variable is spilled — loads and stores are inserted around its uses, the graph is rebuilt, and colouring retries. Optimal colouring is NP-complete, so compilers use fast heuristics plus coalescing to remove redundant moves.

Worked Example

Generate code for a = b + c × d on a machine with 2 registers, R1 and R2.

1. LOAD c → R1; LOAD d → R2.
2. MUL R1, R2 → R1 (R1 holds c × d; R2 is free).
3. LOAD b → R2; ADD R2, R1 → R2 (R2 holds b + c × d).
4. STORE R2 → a.

Six instructions, two registers, no spilling — because at most two values are live at once. A deeper expression would exhaust the registers and force a spill to the stack.

Common Misconceptions

• "The compiler keeps everything in registers." There are never enough; the real job is choosing which variables deserve them — usually the most frequently used.
• "More registers always mean faster code." Gains flatten beyond a point, and wide register files cost area and power.
• "Register allocation is trivial." Optimal allocation is NP-complete; compilers rely on heuristics whose small differences measurably change performance.

Real-World Applications

• Ahead-of-time compilers (GCC, Clang/LLVM) allocate registers for every function they compile.
• Just-in-time compilers in JVMs and JavaScript engines allocate in milliseconds while the program runs.
• Embedded systems with tiny register files depend on good allocation to meet real-time deadlines.

Code generation lowers the IR to machine instructions, and register allocation packs variables into scarce registers via liveness analysis, interference graphs and graph colouring — spilling only when it must. These two phases are a big part of why optimised builds run so much faster.