Static Single Assignment (SSA) Form

A program is in Static Single Assignment form if every variable in it is assigned a value at exactly one program point — statically, meaning textually in the code, not dynamically across loop iterations. If the original program assigns `x` three times (perhaps once before a loop, once in each branch of an `if`), SSA renames these into three distinct variables `x1`, `x2`, `x3`, each with a unique definition. Uses of the original `x` are then rewritten to refer to whichever renamed variable is actually reachable at that use. The one wrinkle is control-flow merging. Suppose a branch assigns `x2` on the true side and `x3` on the false side, and both paths rejoin at a block `B`. A use of `x` inside `B` cannot be statically resolved to `x2` or `x3` alone — the correct value depends on which branch was taken at runtime. SSA resolves this with a phi-function: ``` x4 = φ(x2, x3) ``` placed at the top of `B`. Semantically, `φ` returns `x2` if control arrived from the predecessor that defines `x2`, and `x3` if control arrived from the other predecessor. A phi-function's operands are implicitly tagged by predecessor block — the i-th operand corresponds to the i-th predecessor in some fixed order of `B`'s incoming edges. Crucially, φ is not a runtime instruction that "chooses" anything at execution time in the usual sense; it is a compile-time fiction capturing the join, later lowered into ordinary copy instructions placed on the incoming edges. The key structural fact that makes SSA well-defined and useful is the dominance relationship. Block `A` dominates block `B` if every path from the entry block to `B` passes through `A` (every block dominates itself). A variable's single static definition dominates every use of it except uses inside phi-functions, where the relevant predecessor block must merely reach the phi through that edge. This dominance property is what gives SSA its power: to find the definition reaching a use, you walk up the dominator tree — a tree encoding the dominance relation — rather than searching arbitrary paths in the CFG.

Constructing SSA has two conceptually separate jobs: (1) decide where phi-functions must be inserted, and (2) rename variables consistently, threading the correct SSA name into every use. The classical algorithm (Cytron, Ferrante, Rosen, Wegman, Zadeck, 1991) does both efficiently using dominance frontiers.

Dominance frontier. The dominance frontier of a block `A`, written `DF(A)`, is the set of blocks `B` such that `A` dominates a predecessor of `B`, but `A` does not strictly dominate `B` itself. Intuitively, `DF(A)` is exactly the set of merge points where `A`'s influence "runs out" — the first blocks after `A` where a path not through `A` could also arrive. This is precisely where a phi-function is needed for any variable defined in `A`.

Why this is the right place for phi. If a variable `x` is defined in block `A` and there exists a block `B` in `DF(A)`, then `B` has at least two predecessors, one reachable from `A` without repassing through `A`'s dominance, and another arrived at differently. A use of `x` at `B` cannot be resolved to a single definition without a merge — hence φ is required there. Conversely, if `B` is strictly dominated by `A`, no merge is needed at `B` itself; the single definition in `A` suffices, deferring any needed phi to `A`'s dominance frontier further downstream. Because inserting a phi-function at `B` is itself a new "definition" of `x` at `B`, phi-insertion must be applied iteratively — a phi at `B` can force another phi at some block in `DF(B)`. This iterative closure is exactly what makes the dominance-frontier approach both correct and terminating (the CFG is finite, so the process reaches a fixpoint).

Step 1 — Compute dominators and dominance frontiers

``` function COMPUTE_DOMINATORS(CFG):

# Lengauer–Tarjan or simple iterative dataflow both work;

# iterative version shown for clarity. Dom(entry) = {entry} for each node n != entry: Dom(n) = ALL_NODES # start optimistic (too big) changed = true while changed: changed = false for each node n != entry, in reverse-postorder: new_Dom = {n} ∪ ( ⋂ over predecessors p of n of Dom(p) ) if new_Dom != Dom(n): Dom(n) = new_Dom changed = true return Dom ``` ``` function COMPUTE_DOMINANCE_FRONTIER(CFG, IDom):

# IDom(n) = immediate dominator of n (closest strict dominator) for each node n: DF(n) = {} for each node n with ≥ 2 predecessors: for each predecessor p of n: runner = p while runner != IDom(n): DF(runner) = DF(runner) ∪ {n} runner = IDom(runner) return DF ``` This second routine is the standard Cytron et al. formulation: it walks up from each predecessor `p` of a join node `n` toward `n`'s immediate dominator, marking `n` in the dominance frontier of every block visited along the way (stopping once `IDom(n)` is reached, since that block does dominate `n` and needs no phi there for this join).

Step 2 — Place phi-functions

``` function INSERT_PHI_FUNCTIONS(CFG, DF): for each variable v in the program: WorkList = { blocks that assign v } HasPhi = {} # blocks that already got a phi for v while WorkList is not empty: B = remove any block from WorkList for each block D in DF(B): if D not in HasPhi: insert "v = φ(v, v, ..., v)" at top of D

# one operand per predecessor of D HasPhi = HasPhi ∪ {D} WorkList = WorkList ∪ {D} # the phi is itself a def of v ``` This is a worklist closure over dominance frontiers: every block that defines `v` propagates the need for a phi to its dominance frontier, and since a phi is itself a definition, the process repeats until no new phi insertions occur. Because dominance frontiers are finite and each block gets at most one phi per variable, the worklist terminates.

Step 3 — Rename variables

``` function RENAME_VARIABLES(CFG, DomTree): for each variable v: Stack[v] = empty stack # holds current SSA name for v Counter[v] = 0 function NEW_NAME(v): Counter[v] += 1 name = v + "_" + Counter[v] push name onto Stack[v] return name function RENAME_BLOCK(B): for each phi-function "v = φ(...)" at top of B: replace v (the LHS) with NEW_NAME(v) for each ordinary statement s in B, in order: replace each operand use of some variable v in s with the name on top of Stack[v] if s assigns to some variable v: replace the LHS with NEW_NAME(v) for each successor S of B: j = index of B among S's predecessors for each phi-function "v = φ(a1, ..., ak)" at top of S: set the j-th operand to top of Stack[v] for each child C of B in the dominator tree: RENAME_BLOCK(C)

# pop names defined in this block before returning to caller for each name pushed in this block: pop the corresponding Stack[v] RENAME_BLOCK(entry) ``` Renaming is a preorder traversal of the dominator tree, not of the CFG directly. This is the crux of why the algorithm is correct: because a definition dominates all its (non-phi) uses, walking the dominator tree in preorder guarantees that by the time you rename a use, the correct current definition is already on top of the stack — pushed either in the same block earlier, or in some ancestor in the dominator tree. Popping on exit from a block restores the enclosing scope's view, exactly like block-scoped variable shadowing.

Full pipeline

``` function BUILD_SSA(function F): CFG = build_control_flow_graph(F) IDom = compute_immediate_dominators(CFG) DF = compute_dominance_frontier(CFG, IDom) insert_phi_functions(CFG, DF) rename_variables(CFG, dominator_tree(IDom)) return CFG # now in SSA form ```

Dominator computation. The simple iterative algorithm above is a dataflow fixpoint over reverse postorder; it converges in at worst `O(N)` passes over `O(E)` edges each in pathological cases, but in practice — and provably for reducible CFGs traversed in reverse postorder — it converges in a small constant number of passes, giving effectively `O(N + E)` behavior. The Lengauer–Tarjan algorithm computes dominators in `O(E · α(E, N))` (near-linear, with `α` the inverse Ackermann function), and is the version used in production compilers when dominator computation is a hot path.

Dominance frontier computation. Each block `n` with `k` predecessors triggers a walk up the dominator tree from each predecessor toward `IDom(n)`. A classical amortized argument bounds the total work: each step of the inner `while` loop marks one block's dominance frontier with `n` and advances toward the root of the dominator tree, and it can be shown that across all join nodes this totals `O(N + E)` in practice for real CFGs (the size of all dominance frontiers combined is bounded by structural properties of the CFG, not by a naive `N²` bound).

Phi placement. For each variable, the worklist algorithm inserts at most one phi per block (`HasPhi` guards against duplicates), and each insertion adds the block to the worklist at most once. So phi placement for one variable costs `O(N)` set operations bounded by the size of `DF`, and across all `V` variables the total cost is `O(V · N)` in the worst case — acceptable because `V` and `N` are both bounded by program size and this pass runs once per compilation.

Renaming. The renaming pass is a single preorder walk of the dominator tree, visiting each statement exactly once, with `O(1)` amortized stack push/pop per definition (a definition is pushed once and popped once). Total cost is `O(N + U)` where `U` is the number of variable uses — linear in program size.

Overall, building SSA for a function is near-linear in the size of its CFG: `O(N + E)` for dominance structures, plus a modest per-variable phi-placement cost, plus a linear renaming pass. This is why SSA is affordable even in Just-In-Time Compilation settings where compile time itself is a runtime cost users can feel.

Correctness argument. The central invariant to prove is: > At every point in the renamed program, a use of an SSA name `x_k` is dominated by the unique definition of `x_k` (except operand `i` of a phi in block `B`, which need only be reachable through predecessor `i` of `B`, not dominate `B` itself). This holds by induction on the preorder traversal of the dominator tree. The base case is the entry block: any definition there dominates everything reachable from it. For the inductive step, when `RENAME_BLOCK(C)` is called for a dominator-tree child `C` of `B`, every name currently on top of each stack was pushed either in `B` or in some dominator-tree ancestor of `B` — and since `C`'s dominator-tree ancestors are exactly `B` and `B`'s own ancestors, every such definition dominates `C` by the dominator-tree structure itself (child blocks in the dominator tree are, by definition, dominated by their parent). Popping stacks on exit from a block restores exactly the set of definitions visible to blocks not dominated by it, preventing a name from "leaking" into a sibling subtree where it does not dominate uses. The phi-insertion correctness (that every merge requiring disambiguation gets a phi, and no unnecessary phis are inserted for single-reaching-definition blocks) follows directly from the definition of the dominance frontier given earlier: `DF(A)` is precisely the minimal set of blocks where `A`'s reach as a sole dominating definition ends.

Tradeoffs. SSA is not free. Phi-functions inflate program size, especially inside loops with many live variables, and they complicate control-flow-sensitive transformations like tail duplication. SSA must eventually be destroyed (phi-functions lowered to copies on CFG edges) before instruction selection on most architectures, and naive destruction can introduce the lost-copy and swap problems when multiple phis' source values need simultaneous, order-sensitive updates — solved by careful sequentialization algorithms (e.g., via a parallel-copy semantics and cycle detection). SSA also does not model memory locations (arrays, heap, aliasing) directly; extensions like memory SSA or the use of a synthetic "heap" variable are needed to extend the same reasoning to loads and stores.

Consider this small function with a loop, deliberately non-trivial because the loop-carried variable creates a back-edge phi, not just a simple if/else merge: ``` i = 0 s = 0 while (i < n): s = s + i i = i + 1 return s ``` Basic blocks: `Entry` (i=0, s=0) → `Head` (loop test) → `Body` (s=s+i; i=i+1) → back to `Head`; `Head` also exits to `Exit` (return s).

After dominance-frontier computation, `DF(Body) = {Head}` (Body's definitions of `i` and `s` reach Head both directly and via the loop back-edge, and Head is not strictly dominated by Body). `DF(Entry) = {}` since Entry dominates everything. So phis for `i` and `s` are placed only at `Head`. Renamed SSA: ``` Entry: i1 = 0 s1 = 0 goto Head Head: i2 = φ(i1, i3) ; i1 from Entry, i3 from Body s2 = φ(s1, s3) ; s1 from Entry, s3 from Body if (i2 < n) goto Body else goto Exit Body: s3 = s2 + i2 i3 = i2 + 1 goto Head Exit: return s2 ``` Trace the invariant: the use of `i2` and `s2` inside `Head` and `Body` is dominated by `Head`'s own phi definitions (Head dominates itself and Body). The phi operands `i1, s1` are not dominated by `Head` — they come from `Entry`, which only reaches `Head` along one edge — exactly the exception the invariant allows for phi operands. This is why the loop-carried dependency, which a naive "definition must dominate every use" rule would seem to forbit, is handled correctly: the phi operand rule only requires reachability along the matching predecessor edge, not full dominance. Now a downstream optimization becomes trivial: Constant Folding and Constant Propagation can immediately see that `i1 = 0` is a constant, but because `i2` is defined by a phi with a non-constant second operand `i3`, propagation correctly refuses to fold `i2` to `0` — a conclusion that required only inspecting `i2`'s single definition site, not scanning the whole CFG for every path into `Head`.

Every mainstream optimizing compiler infrastructure — LLVM, GCC's GIMPLE-SSA, the JVM's C2 and Graal compilers, V8's TurboFan, and Swift's SIL — represents code in SSA form during optimization. Register allocators use SSA-based liveness information (building directly on Dead-Code Elimination and Liveness Analysis) because SSA's single-definition property makes live ranges easier to compute and coalesce. Sparse conditional constant propagation, global value numbering, loop-invariant code motion, and partial redundancy elimination are all classically formulated as SSA-based algorithms because they reduce to simple graph problems on the SSA def-use graph rather than iterative dataflow over the raw CFG. In Just-In-Time Compilation systems, where compile time competes directly with program run time, SSA's near-linear construction cost and the sparsity of its dataflow facts make it the practical choice for performing meaningful optimization within a tight time budget, and tiered JITs frequently rebuild or incrementally update SSA as they promote hot functions to higher optimization levels.

Ask the tutor: Can you walk through how SSA destruction handles a cycle of phi-functions, like `a2=φ(b1,b3)` and `b2=φ(a1,a3)`, without corrupting values?