STATIC SINGLE ASSIGNMENT one name, one definition; a phi at every join
Rename every variable so it is assigned exactly once. Where control-flow paths merge, a φ-function picks the definition that actually reached the join. Suddenly every use points at exactly one def — the form that makes constant-propagation, value-numbering and dead-code elimination almost trivial. I-13’s value-semantic update v[i] <- e is already single-assignment in spirit; SSA just names the versions.
THE TECHNIQUE rename to versions; phi selects at the merge
Straight-line reassignment becomes numbered versions; a branch that redefines a variable forces a φ at the merge. Toggle the branch and watch the φ resolve — every name is still defined once. live demo
HISTORY & CREDIT IBM, coined 1988; efficient form 1991
“SSA was invented for LLVM.” — no. LLVM (2003) adopted SSA; the form and the name are from IBM Research, 1988–1991, more than a decade earlier. cited
1988 · Rosen, Wegman & Zadeck — “Global value numbers and redundant computations” (POPL): the paper that introduces the term static single assignment. 1989 / 1991 · Cytron, Ferrante, Rosen, Wegman & Zadeck — “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph” (TOPLAS 1991): places φ-functions at dominance frontiers (builds directly on the dominator tree, dart 150’s predecessor). 1998 · Briggs, Cooper, Harvey & Simpson — “Practical Improvements to the Construction and Destruction of SSA Form” (SPE 28(8)): construction/destruction and the copy-placement subtleties.
φ is not executable code — it is a notation for “the value that reached here”, and it is removed (SSA destruction) by inserting copies on the incoming edges before code generation. Rosen-Wegman-Zadeck, 1988
RECOMMEND FOR I-13 i13 is nearly SSA already
I-13’s v[i] <- e rebinds a value; a φ at a join is just a select on the branch condition — both run natively:
$ i13 run phi.i13 # phi(c,a,b) selects the reaching definition at a merge
x_then = 10 x_else = 20
taken = 10 -- phi(1, 10, 20): the then-definition reached
nott = 20 -- phi(0, 10, 20): the else-definition reached
Recommend: SSA is LIT and near-native — a φ is def phi(I c,I a,I b){ if c>0 {->a} ->b }, verified phi(1,10,20)=10 and phi(0,10,20)=20 on the canonical compiler. Because I-13 already updates by value, a lowering pass need only version each name and drop a φ at merges — the destruction step (copies on the edges) is the same value-copy the machine already does. It is the substrate the rest of this batch stands on: SCCP (151), GVN (152) and copy-propagation (153) all read the def-use edges SSA makes explicit.