Static single assignment form

In three-address code a variable such as i may be assigned in several places, so to know which value a use of i sees, an analysis must consider every path that reaches it. Static single assignment form, SSA, removes that question by construction: every variable is assigned exactly once in the program text, and every use refers to exactly one definition. Where control flow merges values from different paths, SSA inserts a special φ (phi) function that selects the right one. Introduced by Ron Cytron, Jeanne Ferrante, Barry Rosen, Mark Wegman and Kenneth Zadeck at IBM in a series of papers culminating in 1991, SSA is now the standard IR form in optimizing compilers: LLVM IR, GCC's GIMPLE, the HotSpot and V8 JIT compilers, Go's compiler and Swift's SIL all use it. This lesson explains what SSA is, why it helps, and how compilers construct it using dominance, and how they leave it again before generating code.

The idea

Converting straight-line code to SSA is simple renaming: each assignment to x creates a new version, x1, x2 and so on, and each use refers to the latest version. The difficulty is at join points. After if c { x = 1; } else { x = 2; } use(x), the use could see either assignment. SSA writes this as x3 = φ(x1, x2) at the start of the join block: the φ takes the value of x1 if control arrived from the then-branch and x2 if it arrived from the else-branch. A φ is not a real instruction; it is a notation that records the merging of values, and it has one argument per predecessor of its block. Loops need φ functions at their headers, merging the value from before the loop with the value from the previous iteration.

Why is this worth the trouble? Because many analyses become simpler and faster. In SSA each name has one definition, so the definition reaching any use is known immediately, without data-flow analysis; the def-use information that classical optimizers computed iteratively is explicit in the program. Optimizations such as constant propagation, dead code elimination, value numbering and code motion are much easier to implement on SSA, and they run in time roughly linear in the program's size. SSA also separates the different values that happen to share a source variable name, so unrelated uses of a variable like i in two loops do not interfere. The price is the work of building SSA and of translating out of it.

Dominance

Constructing SSA efficiently, with no more φ functions than needed, rests on a property of control-flow graphs called dominance. A block D dominates block N if every path from the entry to N passes through D. Every block dominates itself; D strictly dominates N if it dominates N and is a different block. The immediate dominator of N is the strict dominator closest to N, and every block except the entry has exactly one, so the immediate dominators form a tree, the dominator tree, rooted at the entry. Dominance captures what is guaranteed to have executed: if D dominates N, then by the time N runs, D has run. We already used this idea: a back edge, which closes a loop, is an edge whose target dominates its source.

Dominator sets satisfy a simple equation: the dominators of N are N itself plus the blocks that dominate all of N's predecessors. That makes them computable by iteration, starting from the assumption that every block dominates everything and refining until nothing changes, another fixed-point computation like FIRST and FOLLOW in lesson 3. Practical compilers use either the iterative algorithm of Keith Cooper, Timothy Harvey and Ken Kennedy (2001), which processes blocks in reverse postorder and represents dominators by the tree directly, or the near-linear algorithm of Thomas Lengauer and Robert Tarjan (1979); for the CFGs of real functions the simple iterative method is usually as fast.

Dominance frontiers

Where are φ functions needed? Suppose x is assigned in block D. The new value flows unchallenged into every block that D dominates, because any path into such a block passes through D. It reaches a contested point only where D's dominance ends: a block Y that has a predecessor dominated by D but that D does not strictly dominate itself. That set of blocks is the dominance frontier of D, written DF(D). A φ for x is needed at each block in the dominance frontier of each definition of x. Because the φ is itself a new definition of x, the process repeats: φ functions go at the iterated dominance frontier of the definition sites. Cytron and colleagues showed this produces minimal SSA, with φ functions only where two different definitions genuinely meet.

# Dominators by iterative data-flow, the dominator tree, and dominance
# frontiers (Cooper, Harvey and Kennedy's formulation), for a loop with an if.
SUCC = {"B0": ["B1"], "B1": ["B2", "B5"], "B2": ["B3", "B4"], "B3": ["B4"],
        "B4": ["B1"], "B5": []}
NODES = list(SUCC); ENTRY = "B0"
PRED = {n: [m for m in NODES if n in SUCC[m]] for n in NODES}
dom = {n: set(NODES) for n in NODES}; dom[ENTRY] = {ENTRY}
changed, rounds = True, 0
while changed:                                      # Dom(n) = {n} ∪ ∩ Dom(p) over preds p
    changed, rounds = False, rounds + 1
    for n in NODES[1:]:
        new = {n} | set.intersection(*(dom[p] for p in PRED[n]))
        if new != dom[n]: dom[n] = new; changed = True
print(f"dominator sets (fixed point after {rounds} rounds):")
for n in NODES: print(f"  Dom({n}) = {{{', '.join(sorted(dom[n]))}}}")
idom = {}
for n in NODES[1:]:                                 # immediate dominator: the closest strict one
    strict = dom[n] - {n}
    idom[n] = max(strict, key=lambda d: len(dom[d]))
print("dominator tree:", ", ".join(f"{idom[n]} -> {n}" for n in NODES[1:]))
DF = {n: set() for n in NODES}
for y in NODES:                                     # walk up from each predecessor of a join
    if len(PRED[y]) >= 2:
        for p in PRED[y]:
            r = p
            while r != idom[y]:
                DF[r].add(y); r = idom[r]
for n in NODES: print(f"  DF({n}) = {{{', '.join(sorted(DF[n]))}}}")

dominator sets (fixed point after 2 rounds):
  Dom(B0) = {B0}
  Dom(B1) = {B0, B1}
  Dom(B2) = {B0, B1, B2}
  Dom(B3) = {B0, B1, B2, B3}
  Dom(B4) = {B0, B1, B2, B4}
  Dom(B5) = {B0, B1, B5}
dominator tree: B0 -> B1, B1 -> B2, B2 -> B3, B2 -> B4, B1 -> B5
  DF(B0) = {}
  DF(B1) = {B1}
  DF(B2) = {B1}
  DF(B3) = {B4}
  DF(B4) = {B1}
  DF(B5) = {}

The results match intuition. B4 is not dominated by B3, since control can reach B4 directly from B2, so B4 is in the frontier of B3: a value assigned in B3 must be merged at B4 with whatever arrived the other way. The loop header B1 is in the frontier of every block in the loop body, and even in its own frontier, because a value defined in the loop meets the value from before the loop at the header. The frontier algorithm in the program walks up the dominator tree from each predecessor of a join block until it reaches the join's immediate dominator, adding the join to the frontier of every block it passes; this is Cooper, Harvey and Kennedy's method.

Constructing SSA: placing φ functions and renaming

SSA construction has two phases. The first places φ functions: for each variable, start a worklist with the blocks that assign it, and for each block on the worklist add a φ to every block in its dominance frontier that does not yet have one, adding that block to the worklist because the φ is a new definition. The second renames. It walks the dominator tree depth first, keeping for each variable a stack of its current SSA names. In each block, a φ or ordinary assignment to x pushes a fresh name x1, x2 and so on; each use of x is replaced by the name on top of x's stack. At the end of a block, the walk fills in the argument of each φ in each CFG successor that corresponds to this predecessor. After visiting a block's dominator-tree children, it pops the names that block pushed. The dominator tree is the right order because a definition in a block is visible exactly in the blocks it dominates.

# Converting a CFG to SSA form: place phi functions at the iterated dominance
# frontier of each variable's definitions, then rename variables by a
# depth-first walk of the dominator tree, keeping a stack of names per variable.
CODE = {   # block -> list of instructions (dest, op, args...) ; jumps implicit in SUCC
    "B0": [("s", "=", "0"), ("i", "=", "0")],
    "B1": [(None, "br", "i", "<", "n")],
    "B2": [("t", "load", "a", "i"), (None, "br", "t", ">", "0")],
    "B3": [("s", "+", "s", "t")],
    "B4": [("i", "+", "i", "1")],
    "B5": [(None, "ret", "s")]}
SUCC = {"B0": ["B1"], "B1": ["B2", "B5"], "B2": ["B3", "B4"], "B3": ["B4"], "B4": ["B1"], "B5": []}
PRED = {b: [a for a in SUCC if b in SUCC[a]] for b in SUCC}
IDOM = {"B1": "B0", "B2": "B1", "B3": "B2", "B4": "B2", "B5": "B1"}   # from the previous program
DF = {"B0": set(), "B1": {"B1"}, "B2": {"B1"}, "B3": {"B4"}, "B4": {"B1"}, "B5": set()}
CHILDREN = {b: [c for c in IDOM if IDOM[c] == b] for b in SUCC}
variables = {ins[0] for body in CODE.values() for ins in body if ins[0]}
phis = {b: {} for b in SUCC}                            # block -> var -> list of args
for v in sorted(variables):
    work = [b for b in CODE if any(ins[0] == v for ins in CODE[b])]
    placed = set()
    while work:
        b = work.pop()
        for y in DF[b]:
            if y not in placed:
                placed.add(y); phis[y][v] = [None] * len(PRED[y])
                if not any(ins[0] == v for ins in CODE[y]): work.append(y)
    print(f"phi for {v} placed in: {sorted(placed) or 'none'}")
count = {v: 0 for v in variables}; stack = {v: [v + "0"] for v in variables}   # v0 = undefined/entry
out = {b: [] for b in SUCC}
def newname(v):
    count[v] += 1; n = f"{v}{count[v]}"; stack[v].append(n); return n
def use(x): return stack[x][-1] if x in stack else x
def rename(b):
    pushed = []
    for v in sorted(phis[b]):
        phis[b][v + "#"] = newname(v); pushed.append(v)
    for dest, op, *args in CODE[b]:
        args = [use(a) for a in args]
        if dest:
            d = newname(dest); pushed.append(dest)
            rhs = {"=": f"{args[0]}", "load": f"{args[0]}[{args[-1]}]"}.get(op, f"{args[0]} {op} {args[-1]}")
            out[b].append(f"{d} = {rhs}")
        else: out[b].append(f"{op} {' '.join(args)}")
    for s in SUCC[b]:                                   # fill phi arguments in successors
        k = PRED[s].index(b)
        for v in phis[s]:
            if not v.endswith("#"): phis[s][v][k] = use(v)
    for c in CHILDREN[b]: rename(c)
    for v in pushed: stack[v].pop()
rename("B0")
for b in SUCC:
    print(f"{b}:  (preds {', '.join(PRED[b]) or 'entry'})")
    for v in sorted(k for k in phis[b] if not k.endswith("#")):
        args = ", ".join(f"{a} from {p}" for a, p in zip(phis[b][v], PRED[b]))
        print(f"    {phis[b][v + '#']} = phi({args})")
    for line in out[b]: print("    " + line)

phi for i placed in: ['B1']
phi for s placed in: ['B1', 'B4']
phi for t placed in: ['B1']
B0:  (preds entry)
    s1 = 0
    i1 = 0
B1:  (preds B0, B4)
    i2 = phi(i1 from B0, i3 from B4)
    s2 = phi(s1 from B0, s4 from B4)
    t1 = phi(t0 from B0, t2 from B4)
    br i2 < n
B2:  (preds B1)
    t2 = a[i2]
    br t2 > 0
B3:  (preds B2)
    s3 = s2 + t2
B4:  (preds B2, B3)
    s4 = phi(s2 from B2, s3 from B3)
    i3 = i2 + 1
B5:  (preds B1)
    ret s2

Every variable now has a single assignment. The φ for s in B4 merges the sum from the path that skipped the addition, s2 from B2, with the updated sum s3 from B3; the φ functions in the loop header B1 merge the initial values with those computed in the previous iteration. The variable t is assigned only in B2 and used only in blocks that B2 dominates, so it needs no φ for correctness. The program nevertheless placed t1 = φ(t0, t2) in the loop header, because B1 is in the dominance frontier of B2; t0 is the undefined initial version and the φ's result is never used. Minimal SSA places such dead φ functions for any variable defined inside a loop, and pruned SSA, which places a φ only where the variable is live (lesson 11), removes such dead φ functions. LLVM's mem2reg pass performs exactly this construction to promote the stack variables of Clang's -O0 IR (lesson 7) into SSA registers.

An alternative construction, by Matthias Braun and colleagues (2013), builds SSA directly while generating IR from the AST, without computing dominance frontiers, by looking up a variable's definition recursively through predecessors and inserting φ functions on demand. It is used by several modern compilers, including libFirm and the Cranelift code generator, because it fits naturally into a single translation pass.

What SSA makes easy

With SSA in hand, several classic optimizations become short programs. Dead code elimination removes any instruction whose result has no uses, repeating as removals create new dead instructions; in SSA, uses are explicit, so this is a simple worklist. Constant propagation replaces a name by its value if its single definition is a constant, and sparse conditional constant propagation (SCCP), due to Mark Wegman and Kenneth Zadeck (1991), also discovers branches that can never be taken and the values that are therefore constant. Global value numbering finds expressions that compute the same value even in different blocks, because equal operands mean equal names. Lesson 11 implements constant propagation and dead code elimination. LLVM's instcombine, GVN, SCCP and loop passes all operate on SSA.

Leaving SSA

Machines have no φ instructions, so before final code generation the compiler translates out of SSA. The basic method replaces each φ x3 = φ(x1, x2) with copies x3 = x1 at the end of the first predecessor and x3 = x2 at the end of the second. Two subtleties make naive copy insertion wrong after optimization. The lost-copy problem arises when a copy placed at the end of a predecessor overwrites a value still needed on another edge, and the swap problem arises when φ functions in the same block exchange values, so copies inserted one at a time clobber each other. Both are solved by treating the φ functions of a block as parallel copies and sequentializing them carefully, and by splitting critical edges, edges from a block with several successors to a block with several predecessors, by inserting an empty block where the copies can go. Most of the inserted copies are then removed by register coalescing (lesson 10), which assigns both sides of a copy to the same register.

A notable result connects SSA and register allocation. Sebastian Hack and Gerhard Goos showed in 2006 that the interference graph of a program in strict SSA form is chordal, which means it can be optimally colored in polynomial time, so register allocation can be done before leaving SSA. Several research and production allocators exploit this.

Variants and extensions

Minimal SSA places φ functions only at iterated dominance frontiers, but some of them may define values that are never used. Pruned SSA uses liveness to place only φ functions whose results are live, and semi-pruned SSA uses a cheaper approximation. Memory needs special handling, because loads and stores through pointers are not variables that can be renamed; LLVM leaves memory out of SSA but builds MemorySSA, a separate SSA-like structure for memory operations, to support memory optimizations. Gated SSA and the static single information form extend φ with predicates that record why control merged. Functional programmers will recognize SSA as another notation for a program in continuation-passing style: Andrew Appel observed in 1998 that SSA is functional programming, with φ functions corresponding to the parameters of local functions, and MLIR and Swift's SIL in fact write block arguments instead of φ functions.

Worked examples