Part 4 · 1 chapters · ~8 min

IR and SSA

Why compilers use intermediate representations, three-address code, basic blocks and control-flow graphs, static single assignment and phi functions, dominance in outline, LLVM IR as a real example, stack bytecode as the BYO compiler's IR, and multi-level IRs (MLIR, Rust's HIR and MIR).

Three-address code and SSA

code

; LLVM IR for: int sq_plus(int a, int b) { return a * a + b; }   (clang -O1 -S -emit-llvm)
define i32 @sq_plus(i32 %a, i32 %b) {
  %1 = mul nsw i32 %a, %a          ; every value is assigned exactly once (SSA)
  %2 = add nsw i32 %1, %b
  ret i32 %2
}

; with a branch, values merge through phi
define i32 @pick(i1 %c) {
entry:  br i1 %c, label %then, label %else
then:   br label %join
else:   br label %join
join:   %x = phi i32 [ 1, %then ], [ 2, %else ]
        %y = mul i32 %x, 2
        ret i32 %y
}

The BYO compiler skips SSA and goes straight from AST to stack bytecode, the same choice as CPython and V8's Ignition interpreter for their first tier. Optimising tiers (V8's TurboFan and Maglev, the JVM's C2) build SSA graphs from the bytecode.

FROM AST TO SSA

x = x + 1 written so each variable is assigned once

swipe the figure sideways, or tap expand for full screen

1/4

basic blocks

An IR splits code into basic blocks (no jumps in or out except at the ends) joined into a control-flow graph.

blocks + a CFGthe shape optimisers need