Intermediate Representation (IR)

Definition: A language-independent and machine-independent data structure used by compilers for analysis and optimization, sitting between the source AST and target machine code.

How It Works

Control Flow Graph (CFG): IR instructions are grouped into Basic Blocks (straight-line code with a single entry and single exit) connected by edges representing branches, loops, and fallthrough
SSA Form (Static Single Assignment): every variable is assigned exactly once; when control-flow paths merge, a synthetic phi (Φ) function selects the correct value based on which predecessor block executed (%3 = phi i32 [%1, %bb1], [%2, %bb2]), making def-use chains trivial to compute and simplifying data-flow analyses like constant propagation and dead-code elimination
Three-Address Code / Quadruples: a common textual form where each instruction has at most one operator and two operands (x = y op z), unlike stack-based bytecode (JVM, CPython) where operations implicitly push/pop an operand stack, or graph-based “sea of nodes” IR (V8’s TurboFan, HotSpot’s C2) where control and data dependencies are both explicit graph edges
IR is typically typed: LLVM IR carries explicit types like i32, float, ptr, so optimization passes can reason about size, aliasing, and overflow safely
Optimizers run a pipeline of passes over IR (constant folding, CSE, LICM, inlining, see Compiler Optimizations) before handing off to the backend’s instruction selector and register allocator
Building SSA requires computing dominance frontiers to know exactly where to insert phi nodes; leaving SSA form before code generation (“SSA deconstruction”) reinserts explicit copy instructions where phi nodes were
Dominance: block A dominates block B if every path from the function’s entry to B must pass through A; this relationship is what defines where a phi node is needed (at the “dominance frontier,” where two different definitions of a variable can reach the same block)
Memory SSA: plain SSA only versions scalar variables cleanly; memory (loads and stores through pointers) is harder to version because aliasing makes it unclear which store a given load reads. LLVM’s MemorySSA models memory state itself with its own def/use chain so passes like dead-store elimination can reason about memory the same way they reason about registers
Modern IR verifiers (LLVM’s verify pass) walk the IR after every transformation in debug builds and reject malformed IR immediately, catching optimizer bugs before they silently miscompile a program
IR is also the natural unit of caching and reuse: incremental compilers and build systems can cache a translation unit’s IR and skip re-running the frontend if the source hasn’t changed, only re-running optimization and codegen
Some IRs are high-level and close to the AST (GCC’s GENERIC), some are mid-level (LLVM IR, GIMPLE), and some are low-level and close to real instructions (LLVM MachineIR, GCC’s RTL); a compiler often lowers through several IRs in sequence, each one closer to the target than the last

Under the Hood

Given: f(a) sets x to 1 if a > 0, else 2, and returns x. Step 1: the AST captures the if/else structure as nested nodes. Step 2: lowering to IR splits the function into basic blocks: a condition block, a then-block, an else-block, and a merge block. Step 3: since x is assigned differently on each path into the merge block, SSA construction inserts x3 = phi(x1, x2) to pick the right value based on which predecessor block actually ran. Answer: the branching, mutable-variable source becomes a CFG of single-assignment blocks joined by one phi node, which is what the optimizer and register allocator actually operate on.

Given: LLVM IR for %3 = phi i32 [%1, %bb1], [%2, %bb2] inside block merge. Step: at runtime, execution reaches merge from exactly one predecessor per call; the phi node reads which block control came from and selects that operand. Answer: %3 equals %1 if control arrived from %bb1, or %2 if it arrived from %bb2, with no actual “select” instruction needed in the final machine code since register allocation typically resolves this to a plain move in the predecessor block.

Given: a loop for (int i = 0; i < n; i++) sum += i; needs SSA for both i and sum, each mutated every iteration. Step 1: the loop header block gets a phi for each: i2 = phi(i0, i3) and sum2 = phi(sum0, sum3), where i0/sum0 come from before the loop and i3/sum3 come from the loop body’s end. Step 2: the loop body computes sum3 = sum2 + i2 and i3 = i2 + 1, then branches back to the header. Answer: SSA turns the mutable loop counter and accumulator into an explicit cycle of phi nodes threading values from “before the loop” and “end of this iteration” back into the header, which is exactly the structure LICM and induction-variable analysis operate on.

Why It Matters

Enables reusable, machine-independent optimizations written once against the IR and reused across every source language and every target architecture, instead of duplicating optimization logic per frontend/backend pair
A stable, well-typed IR is what makes tools like LLVM usable as a shared backend for Clang, Rust, Swift, and Julia simultaneously
SSA form specifically is why modern optimizers can be fast and correct at the same time: many classic data-flow problems (constant propagation, dead code elimination) become near-linear-time on SSA instead of requiring iterative fixpoint analysis over a mutable-variable CFG
IR is the natural place to build cross-language, cross-target tools: static analyzers, sanitizers (AddressSanitizer, UndefinedBehaviorSanitizer), and coverage instrumentation are typically implemented as IR passes so they work for every frontend and every target automatically

Common Pitfalls

Losing high-level source type information (signedness, array bounds, source-level generics) during aggressive lowering, which can block optimizations that need that context or produce confusing debug info
Naively computing dominance frontiers and phi placement is quadratic on large functions; production compilers use the Cytron et al. algorithm to keep SSA construction near-linear
IR that’s too low-level too early, lowering to near-machine-code before running high-level optimizations, forecloses transformations that need source-level structure, like vectorization or inlining decisions
Forgetting that SSA is a compile-time-only fiction: real hardware doesn’t have infinite registers or “assign once” semantics, so SSA deconstruction has to reintroduce real copies, and doing that carelessly reintroduces the redundant moves SSA was meant to help eliminate
Assuming one IR fits all purposes: a single flat IR that tries to serve both high-level source-aware optimization and low-level instruction scheduling tends to do both jobs poorly, which is why compilers commonly use several IRs in sequence
Confusing IR with bytecode: bytecode (JVM, CPython) is designed to be shipped, versioned, and interpreted or JIT-compiled at runtime; compiler IR (LLVM IR, GIMPLE) is an internal implementation detail with no stability guarantee between compiler versions
Underestimating how much of a compiler’s total complexity lives in analyses (alias analysis, dominance, liveness) rather than the transformations themselves; a transformation pass is often a few hundred lines, while the analysis it depends on can be thousands
Hand-writing IR and expecting it to behave like source: IR lacks the safety checks a frontend enforces (type checking, borrow checking), so malformed or unverified IR can silently miscompile instead of producing a clear error
Reading SSA form and assuming variables with the same base name (x1, x2, x3) are related at runtime the way loop iterations are; they are compile-time names for what may become entirely different physical registers or stack slots after register allocation
Assuming IR is portable across compiler versions: LLVM IR is versioned and can change between major releases, so IR generated by one Clang version isn’t guaranteed to load in a different LLVM version’s tools

Comparison

IR style	Example	Operand model	Best suited for
Three-address / SSA	LLVM IR	Named virtual registers, phi nodes	General-purpose optimization
Stack-based bytecode	JVM bytecode, CPython bytecode	Implicit operand stack	Compact, portable, simple interpreters
Sea of nodes	V8 TurboFan, HotSpot C2	Graph, both control and data as edges	Aggressive JIT optimization
Tree IR	GCC GENERIC	AST-shaped	Early, high-level lowering close to source
Register Transfer Language	GCC RTL	Explicit target registers	Late-stage, close to real machine instructions

Example

LLVM IR represents code in SSA form. A branch that merges two paths assigning x needs a phi node:

bb1:
  %1 = add i32 %a, %b
  br label %merge
bb2:
  %2 = mul i32 %a, %b
  br label %merge
merge:
  %3 = phi i32 [%1, %bb1], [%2, %bb2]  ; %3 = %1 if from bb1, %2 if from bb2
  ret i32 %3

clang -S -emit-llvm -O0 file.c prints this IR directly, which is how compiler engineers inspect what a given piece of C actually lowers to before any optimization runs.

Java takes the opposite design: javac emits stack-based JVM bytecode instead of SSA, trading optimization-friendliness for a compact, simple format that’s cheap to interpret and easy to verify for safety before it ever runs, since the JVM verifier has to check every bytecode program before execution. HotSpot’s C2 JIT then converts that bytecode into its own internal sea-of-nodes IR at runtime, so the SSA-style optimization still happens, just later and inside the JVM rather than in javac itself.

WebAssembly sits between these two worlds: it’s a stack-based bytecode like JVM bytecode, chosen specifically for compactness and fast validation, but it’s typically the output of an LLVM backend, meaning the SSA-based optimization already happened in LLVM IR before final lowering to the Wasm stack format.

Given: an optimizer wants to know whether it’s safe to hoist y = *p out of a loop, when p might alias the loop’s own loop-control variable stored elsewhere in memory. Step 1: without alias information, the optimizer must conservatively assume *p could change on any iteration, and cannot hoist the load. Step 2: with a points-to/alias analysis pass over the IR establishing that p cannot point at the loop-control variable’s address, the load becomes provably loop-invariant. Answer: the optimization itself (LICM) is trivial once the IR carries enough type and aliasing information to prove it’s legal; most of the real engineering effort in a production optimizer goes into these enabling analyses, not the transformations they unlock.

Referenced by

Dig deeper

Spot an error in this note?