SSA Construction and the Cost of Phi Placement

Static single assignment form requires every variable to be assigned exactly once, and every use to name the assignment that produced the value it reads. Ordinary code violates this constantly: a loop counter is written on every iteration, and a variable assigned in both arms of an if is written twice on the path through either arm. The transformation that repairs the violation introduces a new kind of instruction, the phi node, which selects among the values arriving on different incoming edges.

The engineering question is not whether phi nodes are needed but how many. A naive placement puts a phi at every join for every variable, which for a procedure with many blocks and many variables produces a form larger than the original program and slower to analyze. The standard construction computes a precise answer, and the variants that followed compute a smaller one at the same asymptotic cost.

The invariant, stated precisely

In SSA form, each definition is given a distinct name — conventionally x.1, x.2, and so on — and each use refers to exactly one of those names. Two properties follow and are worth separating because they are checked differently:

Every use is dominated by its definition. If a definition reaches a use, that definition’s block dominates the use’s block, or the use is inside a phi node on an edge where the definition is the incoming value. This is what makes the def-use chain a tree-like structure rather than a general graph, and it is the property most optimizations rely on.

Every path from entry to a use passes through exactly one definition of the name being used. This follows from the first property plus the single-assignment rule, and it is what makes a use’s value unambiguous without any dataflow analysis at the point of use.

A phi node x.3 = φ(x.1, x.2) sits at the head of a block and takes one operand per predecessor edge, in the order the edges appear in the block’s predecessor list. The operands are simultaneous: all are read before the phi’s result is written, which is why a swap of two variables can be expressed as two phi nodes whose operands cross. That simultaneity is a real semantic constraint, not a convention, and naive destruction of SSA by inserting copies gets it wrong when the copies are placed naively — the lost-copy and swap problems documented by Briggs and colleagues.

Dominance frontiers, and why they are the answer

Block A dominates block B if every path from entry to B passes through A. The dominance frontier of A, written DF(A), is the set of blocks B such that A dominates some predecessor of B but does not strictly dominate B itself. In plain terms: B is a place where control flow from A meets control flow from somewhere A does not dominate, so a value defined in A is one of several possible values at B.

That is exactly the condition under which a definition needs a phi. If a variable is defined in block A and used in a block B that A does not dominate, then some path reaches B without passing through A, so B must merge at least two reaching definitions. The iterated dominance frontier DF⁺(A) closes this over chains of joins.

Cytron’s construction therefore works in two passes:

1. Compute DF for every block. The standard algorithm walks each join node B and, for each predecessor P, walks up the dominator tree from P to the immediate dominator of B, adding B to DF of each block passed. The total cost is O(n²) in the worst case but near-linear on real control flow, and the dominator tree it needs comes from Lengauer-Tarjan or the simpler iterative algorithm.
2. For each variable, place a phi at every block in the iterated dominance frontier of the set of blocks that define it, then rename uses by walking the dominator tree and maintaining a stack per variable.

/* Minimal SSA: place a phi for var at each block in DF+ of its def sites.
   dom_frontier[] is a per-block sorted list of frontier members. */
static void place_phis(proc *p) {
    for (size_t v = 0; v < p->nvars; v++) {
        size_t work[MAX_BLOCKS], nwork = 0;
        bool has_phi[MAX_BLOCKS] = {false};

        for (size_t k = 0; k < p->ndefs[v]; k++)
            work[nwork++] = p->defs[v][k];        /* seed with the def blocks */

        while (nwork > 0) {
            size_t b = work[--nwork];
            for (size_t j = 0; j < p->df_len[b]; j++) {
                size_t f = p->df[b][j];
                if (has_phi[f]) continue;
                insert_phi(p, f, v);              /* one phi per variable per block */
                has_phi[f] = true;
                if (!is_def_block(p, f, v)) work[nwork++] = f;
            }
        }
    }
}

The has_phi set is what prevents the iteration from looping forever, and the test is_def_block prevents pushing a block that was already a source of the propagation. Without both, the worklist algorithm re-adds blocks and the placement does not terminate on loops.

Why minimal is not small enough

The construction above is called minimal SSA: it places the fewest phi nodes such that every use has a unique definition. It is minimal with respect to that criterion and still places phi nodes that are never used. A variable defined in a block and used only before a loop will get a phi at the loop header because the header is in the iterated dominance frontier, even though nothing after the loop reads the merged value.

Pruned SSA adds a liveness test: place a phi at block B for variable v only if v is live on entry to B. Since liveness is already computed for other passes, the test is cheap, and it removes the phis at joins where no path reads the merged value before overwriting it. The pruning is sound because a phi whose result is never live cannot affect any use, and removing it does not change the def-use relation of any name that is used. This is why practical SSA constructions run Live-Variable Analysis and the Backward Direction of Dataflow before construction rather than after.

Semi-pruned SSA replaces the global test with a local one: a variable that is live in only one block can never need a live phi, so phis are inserted only for variables that are live across more than one block. That test needs no global liveness pass, at the cost of keeping phis that full pruning would remove. The difference between the two matters mostly for compile time, not for the size of the result.

The cost of the classical algorithm

The two-pass approach is simple and has a hard property that matters: it does not depend on the order in which variables are processed, so the result is deterministic and reproducible. Its costs are the dominator tree computation and the DF sets, which for a procedure with n blocks can total O(n²) entries in adversarial control flow — deeply nested conditionals with many joins.

The alternative, Braun and colleagues’ construction, abandons the precomputed frontier entirely and fills in phi operands on demand as it walks the CFG in reverse postorder from the entry. When a use is found whose definition has not been seen, the algorithm either reads the value from a local predecessor or, if the block has multiple predecessors, creates a phi and recursively asks each predecessor for its value. On reducible control flow this runs in near-linear time and needs no dominator tree, which is why it is the construction used in several production compilers that build SSA directly from the AST or from bytecode. On irreducible control flow it degenerates and needs a fallback.

The trade is explicit: the classical algorithm is uniform and predictable but pays for a dominator tree and frontier sets; the on-demand algorithm is fast and local but has a worst case on irreducible graphs. Both produce SSA that satisfies the same invariant, and both need the same repair pass for the degenerate cases where a phi ends up with a single operand or with all operands equal — trivial phis that later passes remove.

Destruction and the copy problem

Leaving SSA form for register allocation or machine code requires replacing phi nodes with moves on the incoming edges. The obvious translation — for each phi x = φ(a, b), emit x = a on the edge from the first predecessor and x = b on the edge from the second — is wrong when several phis in one block swap values, because the copies overwrite sources before they are read. Two phis x = φ(y, ...) and y = φ(x, ...) need either a temporary or a parallel copy semantics.

The standard fix is to treat the set of phis at a block as a single parallel copy and sequentialize it with a topological order, inserting a temporary only for cycles. On machine code the cost is one move per phi operand in the common case, and the moves often disappear during coalescing. Compilers that allocate registers while still in SSA form avoid the issue by making the phi a first-class constraint rather than a set of moves.

Where the form leaks

SSA assumes that a definition is a single syntactic write. Memory does not obey that. A store through a pointer defines an unknown set of locations, and the usual resolution is to keep memory out of SSA and re-run the memory analyses separately, or to promote address-taken scalars into SSA names first. The latter is what makes SSA useful for local variables in languages with heavy address-taking, and it depends on knowing which variables never escape, the question examined in Escape Analysis and Scalar Replacement of Aggregates.

The second leak is that SSA makes some analyses cheaper and others more awkward. Constant propagation becomes a simple sparse propagation over def-use edges instead of a dense fixpoint, which is the subject of Constant Propagation over a Flat Lattice. But liveness on SSA still requires care around phi operands, because a phi’s operands are live on the edges into the block, not at the block’s entry — a distinction that produces wrong interference edges if the analysis treats a phi as an ordinary instruction.