Compilers
SSA Form
Every LLVM-based compiler (Clang, rustc, swiftc) implicitly uses SSA. All their optimisations (constant propagation, dead code elimination, loop-invariant code motion) work because LLVM IR is in SSA form. SSA was invented at IBM in 1988 and has since become the de facto standard for optimising compilers.
- **GCC** switched to SSA (GIMPLE SSA) in version 4.0 (2005). Before that, optimisations ran on RTL and were noticeably weaker. The transition took years of work.
- **V8** (the JavaScript engine) builds SSA in Turbofan to JIT-optimise hot code. V8's Sea of Nodes representation is a variation of SSA in which both control flow and data flow live in a single graph.
- **WASM compilers** (Cranelift in Wasmtime/Firefox, LLVM in Emscripten) build SSA before generating machine code from WebAssembly, even though WASM itself is stack-based bytecode.
Phi-Functions
A phi function (phi node) in SSA is a special instruction at the entry of a basic block that selects a value from one of several predecessors. `x2 = phi(x0: BB_if, x1: BB_else)` reads: x2 equals x0 if control came from BB_if, and x1 if it came from BB_else.
Parallel semantics of phi functions matter. If one block has `a = phi(b, ...)` and `b = phi(a, ...)`, both read the old values, not the new ones. During SSA destruction (before codegen), phi functions expand into moves, and order matters. You must avoid the 'lost copy' and 'swap' problems. GCC solves this by emitting parallel copies first.
Where in a basic block can phi functions appear?
Dominance
Block A dominates block B if every path from entry to B goes through A. Dominance is a key concept for building SSA. Phi functions are needed exactly where different definitions of a variable meet, on the dominance frontier.
The dominator tree is built by Lengauer-Tarjan in O(N * alpha(N)), nearly linear time. LLVM uses exactly this algorithm in `DominatorTree`. GCC uses an equivalent. Knowing the dominator tree matters far beyond SSA: loop analysis (back edges in the CFG mark loops), inlining, and many other optimisations rely on dominance.
Why is dominance important when building SSA?
SSA Construction
SSA construction converts a regular IR into SSA form. The Cytron et al. algorithm (1991) does it in two passes: first insert phi functions in the right places (using dominance frontiers), then rename variables.
A simple alternative to the full algorithm is LLVM's `mem2reg`: allocate every variable through `alloca` (on the stack), then run the `mem2reg` pass to promote them into SSA registers. Clang follows exactly this approach: emit naive code with alloca first, then run mem2reg. That keeps codegen simple and pushes the complexity of SSA construction into an optimisation pass.
What does the LLVM pass `mem2reg` do?
SSA Destruction
SSA destruction is the reverse transformation: from SSA form back to regular IR before machine code generation. Phi functions do not exist in real hardware. They must be replaced with copies (moves) in the predecessor blocks.
LLVM has no explicit SSA destruction phase. The register allocator understands phi functions and inserts the needed move instructions itself. GCC takes the opposite path and explicitly destructs SSA before register allocation. Both approaches are correct. It is a question of where the responsibility sits between SSA destruction and register allocation.
Why can't we naively replace `phi(a, b)` with just `a` (take the first argument)?
Key ideas
- **Phi functions** at the entry of a basic block select a value from one of several predecessors. Parallel semantics: all phis read the old values.
- **Dominance** and dominance frontiers decide where phi functions are needed. The Cytron algorithm runs in O(N alpha(N)), nearly linear.
- **SSA construction** is phi insertion + renaming. LLVM simplifies the work via alloca + mem2reg.
- **SSA destruction** replaces phi with moves before codegen. Watch out for circular dependencies (the swap problem).
Related topics
SSA is the basis for most optimisations in modern compilers:
- Intermediate representation — SSA is a specialised form of IR. Understanding TAC and CFG is a prerequisite
- Local optimisations — Constant propagation and dead code elimination work directly on SSA form
- Global optimisations — Dataflow analysis and global optimisation rely on SSA form and the dominator tree
Вопросы для размышления
- In LLVM phi functions can only appear at the start of a block, and in GCC GIMPLE the same rule applies. Why not allow phi anywhere in a block? What would break in the optimisations?
- V8 uses Sea of Nodes, a single graph for control flow and data flow without explicit basic blocks. Which optimisations are easier in Sea of Nodes than in classical SSA?
- SSA requires O(N) phi functions in the worst case. Are there real programs where the number of phi functions vastly exceeds the number of variables?