Static Single Assignment (SSA) Form

Ask an optimiser a simple question — "does the value in x here come from this assignment or that one?" — and in ordinary three-address code the answer is a research project. A variable is assigned over and over; to know which definition reaches a use, you must run a data-flow analysis. Static single assignment form (SSA) makes the question vanish by a single, almost impudent rule: every variable is assigned exactly once. If each name has one and only one definition in the whole program text, then "which definition reaches this use?" has a one-word answer — the definition — readable straight off the name.

"Assigned once" sounds impossible for real code (loops! reassignments!), and the trick that rescues it is beautiful: whenever the source would reassign a variable, SSA instead invents a fresh version — x_1, x_2, x_3, \dots — so each assignment writes a brand-new name. The only real difficulty is what to do where control-flow paths merge and two different versions arrive at the same point. SSA's celebrated answer to that is the φ-function.

Versioning a straight-line block

In straight-line code, converting to SSA is pure renaming. Each assignment to a variable bumps its subscript; each use takes the most recent subscript. Watch a = b + c; b = a - d; a = a * b become single-assignment:

original	SSA	note
`a = b + c`	`a1 = b0 + c0`	first def of a → a1
`b = a - d`	`b1 = a1 - d0`	uses newest a (a1); new b → b1
`a = a * b`	`a2 = a1 * b1`	uses a1 and b1; redef a → a2

Now every name on the left is unique, and every name on the right names exactly one definition. There is no ambiguity to analyse away — the dependency structure is written directly into the subscripts. Constant propagation, dead-code elimination and value numbering all become nearly trivial on this form, because "the value of a1" is a single, immutable fact.

The φ-function at a merge

Straight-line renaming breaks the moment two paths meet. Consider an if that assigns x on one branch and differently on the other; after the join, which version is "current"? Both are, depending on the path taken at run time. SSA reconciles them with a φ-function placed at the top of the merge block:

Read x_3 = \phi(x_1, x_2) as: "x_3 takes the value x_1 if we arrived along the first predecessor edge, or x_2 if along the second." The φ has one argument per incoming edge, matched positionally to the predecessors. It restores the single-assignment invariant at merges: instead of two live definitions of x flowing in, one fresh name x_3 is defined, and every later use reads that one name.

Where do φ-functions go? Dominance frontiers

You could drop a φ for every variable at every join — that is maximal SSA, correct but wildly wasteful. Minimal SSA (Cytron, Ferrante, Rosen, Wegman & Zadeck, 1991) places a φ for a variable only where it is genuinely needed, and the precise criterion is the dominance frontier.

A node d dominates node n if every path from entry to n passes through d. The dominance frontier of d is, informally, the set of nodes that are "just beyond" d's dominion — the first join points where d's influence stops being exclusive.

if a block d contains a definition of variable v, then a φ for v is needed at every node in the dominance frontier of d;
those inserted φ-functions are themselves definitions, so the rule is iterated to a fixed point (the iterated dominance frontier);
the result is minimal SSA: the fewest φ-functions such that every use still has a single reaching definition.

This is the deep pay-off of dominance theory: the abstract "who dominates whom" structure of the CFG tells you exactly where merges of a variable's versions can occur, and hence exactly where a φ must sit — no more, no fewer.

The dominance property, and why optimisation loves SSA

in valid SSA, the single definition of a variable dominates every use of that variable (for a φ argument, the relevant use sits at the end of the corresponding predecessor edge);
consequently each use has exactly one reaching definition — use-def information is explicit, not computed;
def-use chains become direct links, so analyses traverse them in constant time per edge instead of solving a data-flow system.

That single property is why SSA underpins essentially every modern optimiser (LLVM, GCC's GIMPLE, HotSpot). Constant propagation becomes a sparse walk of def-use links; dead-code elimination is "a definition nobody uses is dead — delete it"; global value numbering can prove two computations equal by comparing their unique names. Problems that were global data-flow fixpoints collapse into local, name-based reasoning.

Renaming a block, in code

Here is the straight-line renamer: keep a per-variable counter, bump it on each definition, and rewrite every use with the current version. We also print the φ that the following merge would need, conceptually.

type Stmt = { def: string; uses: string[]; op: string }; // def = op(uses...) // Straight-line block: a = b + c ; b = a - d ; a = a * b const block: Stmt[] = [ { def: "a", uses: ["b", "c"], op: "+" }, { def: "b", uses: ["a", "d"], op: "-" }, { def: "a", uses: ["a", "b"], op: "*" }, ]; // Current version number for each name; 0 means the "incoming" version. const version: Record<string, number> = {}; const cur = (name: string) => `${name}${version[name] ?? 0}`; const ssa: string[] = []; for (const s of block) { const rhs = s.uses.map(cur).join(` ${s.op} `); // uses take the CURRENT version version[s.def] = (version[s.def] ?? 0) + 1; // definition bumps to a fresh version ssa.push(`${cur(s.def)} = ${rhs}`); } ssa.forEach((line) => console.log(line)); // Conceptual φ at a merge where a=a2 came from one path and a=a1 from another: console.log("--- at a control-flow join ---"); console.log("a3 = phi(a2, a1) // pick the version from whichever predecessor we came through");

The output is a1 = b0 + c0, b1 = a1 - d0, a2 = a1 * b1 — each left side unique — followed by the illustrative a3 = phi(a2, a1). That φ is not something the CPU executes; it is a piece of bookkeeping that must be resolved before code generation, which is the next point.

Leaving SSA: φ becomes copies

No processor has a φ instruction. Before final code generation the compiler must translate out of SSA, and the standard method is to realise each φ as ordinary copy instructions placed on the incoming edges. For x_3 = \phi(x_1, x_2) with predecessors P_1 and P_2, insert x3 = x1 at the end of P_1 and x3 = x2 at the end of P_2. Each path deposits its own version into the merged name, and the φ disappears.

Naïve copy insertion is subtly wrong in two famous cases. In the lost-copy problem, a copy inserted on an edge overwrites a value that is still live along a critical edge; in the swap problem, two φ-functions at a loop header effectively want to exchange two values (x3=φ(x1,y1); y3=φ(y1,x1)), and inserting the copies in sequence clobbers one before it is read. Both are fixed by care about ordering — splitting critical edges, and using a temporary or a parallel-copy (all φ-copies of a block happen "simultaneously"). Getting out of SSA correctly is as much a part of the story as getting in.

Nothing mnemonic, charmingly — it is just the next available Greek letter. The SSA paper's authors needed a symbol for the merge operator and reached for φ ("phi") much as mathematicians reach for \varepsilon or \delta. It is sometimes rationalised as "phi for the phony function", because it is not a real computation — it makes no arithmetic, it only selects — and indeed the most important thing to remember about φ is exactly that it is not executable. Some newer IRs rename it merge or use block-argument notation (Swift's SIL, MLIR, Cranelift) that avoids the mystique altogether, passing the incoming values as arguments to the block, which is provably equivalent to φ-functions.

The commonest conceptual error is to imagine the machine "running" x3 = phi(x1, x2). It does not — a φ has no operational meaning at a single point in time; its "choice" depends on the edge control arrived on, which is information a straight-line machine has already thrown away. That is precisely why φ must be lowered to copies on the predecessor edges before code generation. And when you do lower it, remember the lost-copy and swap problems: inserting the copies carelessly (wrong order, or onto a critical edge shared by another path) will clobber a still-live value. Split critical edges and treat a block's φ-copies as a single parallel copy, and both problems disappear.