SSA Form

The cornerstone of modern compiler optimization: each variable is assigned exactly once, reducing data flow analysis from iterative fixed-point computation to a single-pass scan on a sparse graph. Dominator trees, dominance frontiers, and φ functions are the three tools that enforce this constraint across all control flow graphs.

Overview

In conventional IR (three-address code), the same variable may be assigned multiple times. During data flow analysis, to determine which assignment a reference to variable x corresponds to, one must trace back to find "which assignment produced this value." In large functions, this is not only a performance issue but also a correctness issue (multiple assignment points reaching the same use point via different paths).

The core constraint of SSA (Static Single Assignment) is extremely concise: each variable is defined exactly once in the program body. This may seem restrictive, but with the introduction of φ functions (phi functions), any reducible control flow can be converted into SSA. Once in SSA, many problems in data flow analysis change from "iterative solving" to "single-pass scanning"—because each value has only one definition point, the use-def chain is deterministic, resulting in O(n) complexity instead of O(n²).

Why SSA Simplifies Analysis: A Comparison

Conventional IR:

x = 1           ← def1
if (cond)
    x = 2       ← def2 (overwrites def1)
y = x + 1       ← Does this x come from def1 or def2? Depends on cond

To determine which assignment y = x + 1 uses, one must perform reaching definition analysis (iterative data flow, worst-case O(n²)).

SSA equivalent form:

x1 = 1          ← unique def
if (cond)
    x2 = 2      ← unique def
x3 = φ(x1, x2)  ← selects x1 or x2 based on control flow
y = x3 + 1      ← deterministically uses x3; x3's definition point is the φ function—no iterative analysis required

Each use point directly points to a unique definition point—a sparse representation. Data flow information no longer needs to propagate across the entire CFG; it only requires a single scan over the def-use graph. This is why SSA has become the foundation of modern optimization infrastructure.

Three Key Concepts for Constructing SSA

Dominator Tree

Node A dominates node B if and only if every path from the entry to B passes through A. The dominance relationship forms a tree (with the entry block as the root):

• entry dominates all blocks
• block1 dominates block2, block3, and block4
• block2 and block3 do not dominate each other (reaching block2 from entry does not necessarily pass through block3)

The dominator tree is computed from the CFG using Cooper's engineering algorithm (O(n·|V|), performs well on small CFGs) or Lengauer-Tarjan (O(n log n), for large CFGs). Dominator trees are the foundation of SSA construction—the definition point of each variable "covers" its subsequent reachable use points in the dominator tree.

Dominance Frontier

However, variables are not only used at points that are dominated. When control flow merges (e.g., at the end of an if-else), two different definitions "meet." The dominance frontier precisely defines these merge points:

DF(X) = {Y | X dominates some predecessor of Y, but X does not strictly dominate Y}

Literally: Y is the first node that is "no longer dominated by X"—Y has an edge from X's dominated region, but Y itself is outside X's dominance area. These Y nodes are where φ functions need to be inserted.

φ Functions: Selectors at Control Flow Merges

A φ function is not a real instruction—it is a notation meaning: "I select the corresponding source value based on the actual control flow edge entered."

x3 = φ(block2→x1, block3→x2)
    ↑ If entering from block2 → x3 = x1; if entering from block3 → x3 = x2

During code generation, φ functions are eliminated into actual moves on registers/memory—sharing the same physical location or merging from multiple source registers (deconstructing SSA).

Cytron Algorithm: Efficient SSA Construction

The Cytron (1991) algorithm remains the standard today—used by both LLVM and GCC. Two steps:

Step 1: Determine φ Insertion Points

Using dominance frontiers:

For each block D that defines variable v:
  For each block F in the dominance frontier of D:    ← F is a merge point
    Insert φ(v) at the entry of F
    Then treat F as a block that "defines v" (since φ itself is a definition)
    Recursively process the dominance frontier of F

In practice, this is done simultaneously for all variables—one traversal of dominance frontiers, remembering for each variable which blocks require φ functions.

Step 2: Rename Variables

Perform a preorder traversal on the dominator tree, maintaining a stack of version numbers for each variable name:

rename(block):
    for each φ in block:
        Assign a new variable version to the φ result (e.g., x3)
        Push x → x3 onto x's version stack
    for each instruction in block:
        For each use in each instruction:
            Look up the variable version stack: replace with the current top version
        For each definition in each instruction:
            Assign a new version number (e.g., x2)
            Push variable → new version onto the stack
    for each successor of block:
        Fill the successor's φ arguments: use the current top versions of each variable
    for each dominator tree child of block:
        rename(child)          ← recursive call
    Pop all version numbers pushed for the current block ← exit scope

This renaming process completes version numbering for all variables in a single O(N) traversal on the dominator tree—significantly faster than "performing reaching definition analysis on the CFG for each variable's definition point."

Deconstructing SSA: From φ to Executable Code

SSA's φ functions are not real instructions and must be deconstructed before code generation:

Before deconstruction:              After deconstruction (via copies):
  L1: x1 = 1                        L1: x = 1
      goto L3                           goto L3
  L2: x2 = 2                        L2: x = 2
      goto L3                           goto L3
  L3: x3 = φ(x1, x2)                L3:           ← x already has the correct value
      use(x3)                           use(x)

The idea: if the sources of a φ can share the same register, no extra instructions are needed—just place the value into the same register at the end of the predecessor control flow blocks. The key is that multiple sources of a φ cannot be simultaneously active (they come from mutually exclusive paths), so sharing the same physical location is safe.

Complex cases: multiple φs referencing each other, or φs having dependency cycles with regular instructions (e.g., x = φ(y, z); y = x + 1 in a loop)—this is the "lost copy" and "swap" problem, requiring temporary variables to break cycles. The classic out-of-SSA algorithm by Cooper et al. (1998). For more efficient implementations, refer to subsequent research such as Pereira & Palsberg (2004).

SSA's Role in LLVM

LLVM IR is fully SSA: each virtual register (%1, %2, ...) is assigned exactly once. alloca/load/store bypass SSA (via memory aliasing); LLVM's mem2reg pass promotes allocatable alloca-store-load sequences into SSA virtual registers—this is the first gate before entering the optimization pipeline.

Once in SSA, most LLVM passes (inlining, GVN, LICM, DCE, loop unrolling) perform sparse analysis based on SSA—this is the fundamental reason for LLVM's fast and precise optimization.

Trade-offs and Failure Modes

• Excessive φ insertion: Conservative computation of dominance frontiers may insert unnecessary φs on unreachable paths → these will be handled by dead code elimination after SSA deconstruction, not affecting correctness, but consuming more virtual registers in the intermediate stage.
• Irreducible CFG: CFGs caused by goto or tail calls may lack a "single-entry loop header" in the dominator tree sense—standard algorithms first require CFG reducibility (node splitting).
• Extra copies introduced during SSA deconstruction: φ deconstruction may insert many copy instructions → during subsequent register allocation, coalescing eliminates copies that can be merged (SSA deconstruction and register allocation are a pair, see Register Allocation).

References

• Cytron et al. (1991): "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" — the original algorithm for SSA construction
• Cooper/Torczon: "Engineering a Compiler", Chapters 8–9 (comprehensive explanation of SSA, including dominator tree computation)
• LLVM: lib/Transforms/Utils/Mem2Reg.cpp, lib/Transforms/Utils/SSAUpdater.cpp — industrial-grade SSA implementation

Keywords: SSA, static single assignment, φ-function, phi node, dominator, dominance frontier, Cytron algorithm, renaming, out-of-SSA, SSA destruction, sparse analysis, mem2reg, irreducible CFG, use-def chain, virtual register