IR, Optimization, and Code Generation

Going straight from AST to machine code sounds attractive but is a dead end. An AST is too high-level: it has no notion of registers, instruction latency, or memory layout. Raw assembly is too low-level: optimizations written against x86 opcodes have to be rewritten for ARM.

An intermediate representation (IR) sits in the middle. It's:

• Low enough that optimizations are machine-agnostic (no registers yet, but no tree structure either).
• High enough that analysis is still easy (explicit data flow, no aliasing ambiguity in SSA).
• Retargetable: write one set of optimizations, compile to any target by swapping the back-end.

LLVM IR is the canonical example: one optimizer, dozens of targets (x86, ARM, WASM, RISC-V). GCC uses GIMPLE then RTL. The IR phase is what makes the $M \times N$ compiler problem into $M + N$.

The simplest IR style is three-address code (TAC): each instruction has at most two operands and one result. Every complex expression is broken into a sequence of instructions with temporary variables.

For z = (a + b) * (a + b) - c:

t1 = a + b
t2 = a + b
t3 = t1 * t2
t4 = t3 - c
z  = t4

Properties: each instruction is trivial to analyze (one operation, explicit operands). Temporaries (t1, t2, ...) are unlimited — the register allocator sorts out physical registers later. Notice t1 and t2 compute the same thing — common subexpression elimination (CSE) will spot this. TAC makes the redundancy obvious in a way the AST does not.

Static Single Assignment (SSA) adds one rule: every variable is assigned exactly once. Reuse a variable? Give it a new version.

; Plain TAC                   ; SSA form
x = 1                         x_1 = 1
x = x + 1      -->            x_2 = x_1 + 1
y = x * 2                     y_1 = x_2 * 2

Where control flow merges (after an if/else), SSA inserts a $\phi$ (phi) node that picks the right version:

if (cond)  x_2 = 5
else       x_3 = 7
           x_4 = phi(x_2, x_3)   ; x_4 is whichever ran

SSA makes use-def chains trivial: the single definition of x_2 is right there — no data-flow analysis needed to find it. This unlocks fast implementations of constant propagation, dead-code elimination, and dozens of other passes. LLVM, GCC (GIMPLE), and Cranelift all use SSA internally.

These passes are typically run to a fixed point (repeat until the IR stops changing). SSA makes many of them $O(n)$ where non-SSA implementations are $O(n^2)$ or require iterated dataflow.

A concrete before/after to make the savings tangible:

; Before optimization
t1 = 2
t2 = 3
t3 = t1 * t2      ; 2 * 3
t4 = t3 + x
t5 = t4 * 0       ; anything * 0 = 0
return t5

; After constant folding + algebraic simplification + DCE
return 0

Steps taken:

1. Constant fold t1 * t2 → 6, then t3 + x stays (x not constant).
2. Algebraic identity _ * 0 = 0 replaces t4 * 0 with 0.
3. DCE removes t1, t2, t3, t4, t5 — none of their values are used in the final return 0.

The entire body collapses to a single constant. This is why -O2 code is often unrecognizable to a human inspecting the assembly — aggressive folding, inlining, and DCE can eliminate whole functions.

From typed AST to machine code through the IR pipeline:

SSA IR instructions (add, mul, load, store) don't map 1:1 to ISA instructions. Instruction selection tiles the IR with patterns that map to real instructions, minimizing the tile count (cost).

A classic technique is tree pattern matching (IBURG, LLVM's SelectionDAG): the IR is turned into a tree, and a dynamic-programming pass finds the minimum-cost tiling of that tree into ISA instruction patterns.

For example, on x86-64:

• add r0, r1 can implement TAC t = a + b directly.
• lea rax, [rcx + rcx*2] can implement t = x + x*2 (i.e., 3*x) in one instruction — a multiply-by-constant optimization invisible at the IR level.
• Vector instructions (vmulps) can replace four scalar mul operations if the auto-vectorizer recognizes the pattern.

Instruction selection is where ISA quirks (addressing modes, fused multiply-add, SIMD) are exploited.

SSA uses unlimited virtual registers; a real CPU has ~16 (x86-64) or ~32 (ARM64). Register allocation assigns virtual registers to physical ones, inserting spill code (load/store to the stack) when demand exceeds supply.

The standard algorithm: graph coloring.

1. Build an interference graph: nodes are virtual registers, edges connect registers that are live simultaneously.
2. Try to k-color the graph ($k$ = number of physical registers). Two interfering registers can't share a color (= physical reg).
3. If a node can't be colored, spill it: assign it a stack slot, insert loads before each use and stores after each def, and retry.

Coloring is NP-complete in general, but the Chaitin-Briggs heuristic works well in practice. LLVM uses a different approach — linear scan allocation — for faster compile times at the cost of some code quality. Both are crucial: bad allocation means excessive stack traffic, which kills performance on memory-bound code.

Code generation emits object files (.o), not the final executable. Each object file contains:

• Text section: machine instructions, with placeholder addresses for external symbols.
• Data/BSS sections: initialized and zero-initialized globals.
• Relocation records: instructions to the linker: "patch address at offset 0x42 with the address of printf".
• Symbol table: exported names and their offsets within this file.

The linker resolves relocations across all object files, assigns final virtual addresses, and produces the executable. Static linking bakes everything in; dynamic linking leaves some relocations unresolved until the loader runs.

For JIT compilers (JVM HotSpot, V8, LLVM MCJIT), all of this happens at runtime — IR lowering, instruction selection, register allocation, and linking occur while the user waits. The trade-off: faster startup than AOT, but shorter optimization budgets per function.