10.5 SSA Form and Phi Nodes

Static single assignment (SSA) imposes one rule: every variable is assigned exactly once. Reassignments become new versions, so x = x + 1 turns into x2 = x1 + 1.

That single-definition property makes def-use chains explicit, which is why most modern optimizers work in SSA.

The Merge Problem

Versioning breaks down at merges. If two predecessors define x1 and x2, which version flows out? SSA answers with a phi node:

x3 = phi(x1, x2)

A phi selects the right version based on which predecessor control came from. It is needed only where multiple paths bring different versions together.

Placement and Payoff

Phi nodes belong at the dominance frontier of each definition: the precise points where independent paths reconverge. Place them anywhere else and you waste them or break the form.

With clean def-use chains, constant propagation, dead-code elimination, and value numbering get simpler and stronger. SSA is the reason those passes feel almost trivial on a good IR.

Minimal vs Pruned SSA

Naively placing phi at every frontier produces too many. Minimal SSA inserts phi only where needed; pruned SSA goes further and drops phi for values that are dead at the merge. Fewer phi means cheaper analysis, so the placement algorithm pays for itself.

Leaving SSA

Hardware has no phi instruction, so before code generation the compiler destructs SSA: each phi becomes copies in the predecessor blocks. Done carelessly this hits the lost-copy and swap problems, where parallel phi semantics get serialized wrong. Correct destruction inserts temporaries to preserve the simultaneous nature of phi.

Why It Wins

Consider constant propagation. In plain code, x reassigned three times forces the analysis to track which definition reaches each use. In SSA each x_i has exactly one definition, so a constant flows trivially to every use. Most major optimizations get this same discount, which is why SSA is the default mid-IR in LLVM, GCC, V8, and HotSpot.