Minimal SSA Construction from Dominance Frontiers

Static single assignment form is a discipline, not a data structure. Its rule is that each name is defined exactly once, and every use refers to exactly one definition. The rule is trivial to state and expensive to satisfy, because a variable assigned in two branches reaches a later use with two possible definitions. SSA resolves this by introducing a merge instruction, the phi function, which selects among incoming values according to which predecessor the control flow arrived from.

Where to put those merge instructions is the whole problem. Placing a phi in every block with multiple predecessors is correct and wasteful: most of them would be trivial, copying one of the inputs unconditionally, and each one enlarges the IR and gives every later pass more work. Placing too few is unsound. The minimal placement is defined by a graph property called the dominance frontier, and the algorithm that computes it is one of the few pieces of compiler theory that is both exactly characterised and cheap to implement.

The SSA Property Restated

Before the placement question can be answered, the form needs a precise statement. A program is in SSA form when each variable has a single definition site that dominates all its uses, and each use refers to that definition. Dominance is what makes the reference unambiguous: if the definition dominates the use, then every path to the use passes through the definition, so at the point of use the value is defined no matter which branch was taken.

For straight-line code this is easy. For a variable assigned inside a conditional and read after the merge, no single definition dominates the use. The phi function at the merge block repairs this by being a definition that does dominate the use, and by naming one input per predecessor edge. A phi is not an ordinary instruction: its inputs are associated with edges, not with positions in the predecessor’s instruction list, and all inputs are conceptually read simultaneously when control enters the block.

Two variables with the same name in the source become distinct SSA names. A source-level loop counter i becomes a chain of names, one per iteration, connected by a phi at the loop header. Renaming is the mechanical part of the translation, and it is driven by a stack per source variable during a depth-first walk of the dominator tree whose shape comes from the control-flow graph. When the walk enters a block that assigns i, a fresh name is pushed; when it leaves, the name is popped, so uses in sibling subtrees see the definition from the nearest enclosing scope that actually dominates them.

The Dominance Frontier

The dominance frontier of a block b, written DF(b), is the set of blocks y such that b dominates some predecessor of y, but b does not strictly dominate y itself. In plainer terms: b is on a path into y from one side, but not from all sides, so a definition in b reaches y along some paths and not others.

That is precisely the condition under which a definition needs a merge. If a definition in b is live at y, and b does not dominate y, then some path to y bypasses b and carries a different definition. The phi at y is where the two are reconciled.

The classic construction of the frontier uses the dominator tree and two clauses. The local clause looks at each successor y of a block b: if b is not the immediate dominator of y, then y is in DF(b), because b is a predecessor of y that dominates itself, and the fact that it is not y’s immediate dominator means it cannot strictly dominate y. The upward clause propagates through the tree: if y is in the frontier of a child of b and b does not strictly dominate y, then y is in DF(b) as well. That is why the algorithm walks the dominator tree in postorder, unioning the frontier sets of children before computing the parent’s own contribution.

def dominance_frontiers(cfg, idom, children):
    df = {b: set() for b in cfg.blocks}
    for b in postorder(children[idom.root]):   # children first
        for y in cfg.successors(b):
            if idom[y] is not b:
                df[b].add(y)                    # local clause
        for c in children[b]:
            for y in df[c]:
                if y is not b and not dominates(b, y):
                    df[b].add(y)                # upward clause
    return df

The strict-dominance test in the upward clause is what prevents a block from claiming its own frontier entry when it does dominate the target. Without it, every block on the path to a merge would add the merge to its own frontier, and phi placement would become non-minimal.

Placing Phis by Worklist

Given the frontier, minimal placement for a variable v is a reachability computation over the def-use graph. Let A(v) be the set of blocks that assign v in the source. A block y needs a phi for v if it is in the frontier of some block in A(v), or in the frontier of some block that already has a phi for v. The second clause is what makes the algorithm iterate: a phi is itself a definition, so it can create demand for further phis downstream.

The worklist formulation processes each block in A(v) once, pushing its frontier members onto a worklist. When a block is popped and does not yet have a phi, one is inserted and its own frontier members are pushed. Insertion is marked so that each block is processed at most once per variable, which bounds the work by the size of the frontier relation rather than by the number of paths.

The cost is what makes this practical. For a variable assigned in k blocks with a total frontier size f, the worklist visits at most k + f blocks, and each visit is a set operation. Across all variables the total is proportional to the sum of the frontier sizes, which is small in practice: most blocks have small frontiers, and structured code tends to have frontiers of size one or two. The pathological case is a dense graph where many blocks can reach many merge points, which is why the algorithm is usually described as near-linear rather than linear.

The result is minimal in a precise sense: no phi is placed that is not required by the def-use relation, given that every definition must dominate its uses. It is not minimal in the stronger sense of “no phi is placed whose result is unused or whose inputs are all the same value”. Those are removed by a subsequent pass, and the distinction matters because the two criteria give different answers on code with dead definitions.

Pruned and Semi-Pruned Variants

Minimal placement ignores liveness. A phi is inserted at a merge even if the variable is dead there, which is correct but wasteful. Pruned SSA adds a liveness test: a phi is inserted at y only if v is live at the entry of y. The test is cheap once liveness has been computed, and it removes phis for variables whose definitions never reach a use.

The problem is circularity: computing liveness for a variable needs the def-use chains that the phis are being inserted to create. Semi-pruned SSA breaks the cycle by using a weaker test that does not require SSA liveness. A variable is considered globally live if it is used in a block other than its definition block, or if it is passed to a call, or if its address is taken; the test is applied to the source program before any renaming, where uses and definitions are block-local facts and no phis exist yet. Variables that are only used within the block that defines them are handled entirely by local renaming and never need phis. The semi-pruned variant is what most production compilers implement, because the test can be answered before any SSA name exists, and it removes most of the waste without the circularity.

The distinction is not academic for compile time. Every phi is an instruction that the register allocator must colour, and every phi edge is a move that out-of-SSA translation must schedule. Removing a phi that would have been dead saves both.

Renaming and the Semantics of the Merge

After placement, the translation walk renames definitions and uses. The walk follows the dominator tree, maintaining a stack per source variable. At a block that assigns v, the block’s instructions are rewritten in order, each assignment pushing a fresh name, and the rename for a phi’s destination is pushed on entry to its block so that uses after the phi see it; when the walk leaves the block, the stack is popped back to its previous depth, so uses in sibling subtrees see the definition from the nearest node on the dominator-tree path that redefines v.

The edge association is the subtle part. A phi’s input for predecessor p must name the value of v at the end of p. The renaming walk visits blocks in the dominator tree, so a predecessor p of the merge may be visited before the merge, after it, or in a different subtree entirely, and the name on top of the stack when the merge is visited is the one defined along the dominator-tree path into the merge, not the one that reaches it from p. Implementations therefore fill the phi’s input for p after the recursive call that processes p returns, or keep an explicit table from an edge to the name current at its source and consult it when the edge is finally reached. Getting this wrong produces a phi that references a value defined on a different path, which is the first thing a verifier checks.

The verifier’s other invariants follow from the definition: every definition dominates every use, each phi has exactly one input per predecessor edge, and no phi input is defined by the phi itself in a way that would create an uninitialised cycle. A loop header phi whose back-edge input is the phi’s own result is legal and expected; a phi whose entry-edge input is its own result is not, because the value would be read before any definition on the entry path.

Where the Guarantee Pays Off

Once the form holds, analyses become sparse. A def-use chain is an explicit list rather than something reconstructed by searching, so a pass that wants to know all users of a value walks a short list. Constant propagation no longer needs to iterate over a lattice at every program point: it evaluates each definition once when it becomes known and propagates the result along the def-use chains.

The property that makes this sound is that the def-use relation is complete. Every use is reachable from its definition by a chain of references, so a pass that updates a definition can find every affected use by following links. That is what allows the algorithm in Sparse Conditional Constant Propagation Across the SSA Graph to re-evaluate only the uses of values that actually changed, rather than every program point on every round of a fixed-point iteration.

The cost is that the form must be maintained. Every transformation that introduces a definition or moves code across a merge must repair the phi inputs, and the repair is where most SSA bugs live. Destruction back to a conventional form is a separate problem, treated in Phi Functions: Parallel Semantics and the Out-of-SSA Problem, and it is harder than construction because the parallel semantics of phi inputs conflict with sequential moves.