Phi Functions: Parallel Semantics and the Out-of-SSA Problem

A phi function looks like an assignment list and behaves like a multiplexer. When control enters a block, exactly one incoming edge is taken, and the phi takes the value associated with that edge. All phis in the block take their values from the same edge, simultaneously. That simultaneity is not a stylistic choice; it is a semantic requirement without which the form would be ambiguous whenever a block has phis whose inputs refer to each other.

The requirement is invisible while the program stays in SSA form, because a phi is a definition and definitions are not ordered relative to each other. It becomes visible the moment the form is destroyed and phis must be replaced with real moves. A naive replacement that emits moves in the order the phis appear can read a register after another move has overwritten it, and the resulting code computes the wrong value. This is the out-of-SSA problem, and it is the main reason SSA construction is considered the easy half of the transformation.

Why the Inputs Are Read in Parallel

Consider a two-way swap at a merge. On the left path, x holds a and y holds b; on the right path the roles are reversed, and after the merge the program wants x to hold the other path’s y and vice versa. In SSA this is two phis:

x3 = phi(x1 from L, y1 from R)
y3 = phi(y1 from L, x1 from R)

On edge L the phis read x1 and y1 and produce x3 and y3. If the implementation places the two moves on the edge in the order written and the register allocator has assigned x3 to the same register as x1 and y3 to the same register as y1, the first move overwrites the source of the second. Reading the phis sequentially rather than simultaneously gives the wrong answer, and no reordering of the two moves alone fixes it: a temporary is required.

This is the swap problem. Its sibling is the lost-copy problem, which arises when a value that must still be read by a later move is overwritten first. If the destination of one move is the source of another, emitting the moves in the wrong order destroys the source before it is read, and again a temporary or a different coalescing decision is needed.

Both problems are consequences of the same fact: a set of moves that must be performed in parallel is not a set of moves that can be performed in sequence without extra storage. The general problem is exactly the parallel copy problem from register transfer languages, and it is solved by the same technique: break the copy set into chains and cycles, and use one temporary per cycle.

Where the Moves Go

The straightforward translation places one move per phi input on the corresponding predecessor edge. If the predecessor has a single successor, the moves can be appended to the end of the predecessor block. If the predecessor has multiple successors, the moves must go on the edge specifically, which means either splitting the edge into a new block or predicating the moves on the branch condition.

Critical edges — edges from a block with multiple successors to a block with multiple predecessors — are the case that forces splitting. Putting the moves in the predecessor would make them execute on the other outgoing edge too; putting them in the successor would make them execute for the other incoming edges. Splitting the edge into a block with one predecessor and one successor gives the moves a home with exactly the right execution condition. The cost is a new block, a new unconditional branch, and a lost fall-through, which is why splitting is often restricted to critical edges only.

An alternative that avoids splitting is to place the moves at the top of the successor block and guard them. This requires a predicate that identifies the incoming edge, which is only available if the branch condition is still live or if the architecture offers a conditional move. When it is available, the guarded form is cheaper than a split because it preserves fall-through, but it adds instructions to the hot block rather than to a cold edge block.

Coalescing Decides How Many Moves Survive

A move that assigns a value to a name the register allocator will place in the same register is a no-op, and eliminating it is coalescing. The unrestricted version merges the live ranges of the source and destination whenever the merge does not create a conflict in the interference graph, which removes the move entirely. A restricted version merges only when the destination has a single predecessor, which is safe because there is no other definition competing for the same register on another path.

Coalescing is where out-of-SSA translation and register allocation interact most strongly, and the interaction is a genuine trade-off. Coalescing aggressively removes moves but can create live ranges that span a merge, which raises register pressure and can force a spill. Spilling is far more expensive than a move: a move costs one instruction that many architectures execute without occupying an execution unit, while a spill costs a store and a reload, each occupying a load/store unit and adding a memory access. The usual resolution is a merge test that preserves colourability. The Briggs criterion merges two nodes only when the combined node still has fewer than k neighbours of significant degree, where significant means degree at least k; it is cheap to check and rarely produces an uncolourable graph. The George criterion is more permissive in one direction: it allows a merge when every neighbour of one node either already interferes with the other node or has degree below k. Both are conservative with respect to the true condition, and both are preferred to a biased colouring that merely encourages the same register.

The ordering also matters. If phis are eliminated before allocation, the moves become ordinary instructions and the allocator sees them. If allocation runs on the SSA form directly, the allocator must reason about phi inputs as constraints on colouring rather than as instructions. Both approaches are used, and the second depends on the chordal structure of the SSA interference graph: two values interfere only where a single definition cannot separate them, and this structure admits polynomial-time colouring before the phi constraints are added.

Sequentialising a Parallel Copy

Whatever survives coalescing must be emitted as a correct sequence. The standard algorithm builds a directed graph whose nodes are the locations involved and whose edges are the copies to perform, then decomposes it.

The direction of the edges matters exactly once, because it decides which end of a copy may be written first. Draw an edge from s to d for each copy that must leave d holding the value s holds now; equivalently, s must be read before d is overwritten. A node with out-degree zero is read by no remaining copy, so its current value can be overwritten with no loss: emit the copy that writes it, delete that edge, and repeat. What remains once every such node has been consumed is a set of components in which every node is read by some copy, so no write can go first; one value must be saved into a temporary, the component broken at that point, and the saved value written last.

def emit_parallel_copy(copies, fresh_temp, emit):
    # copies: dict destination -> source; emit(d, s) makes d hold s's old value
    pending = dict(copies)
    # drop self-copies first; they are no-ops, not cycles
    for d in [d for d, s in pending.items() if d == s]:
        del pending[d]
    while pending:
        read_by = set(pending.values())
        ready = [d for d in pending if d not in read_by]
        if ready:
            d = ready[0]
            emit(d, pending.pop(d))       # nobody reads d, so overwrite it now
            continue
        start = next(iter(pending))       # every node is read: all cycles
        tmp = fresh_temp()
        cur = start
        while True:
            s = pending.pop(cur)
            emit(cur, tmp if s == start else s)
            if s == start:
                break
            cur = s
        emit(tmp, start)                  # saved value lands last

Each pass of the outer loop either removes a node from the copy graph or breaks one cycle, so the work is bounded by the number of copies. The emitted move count is the number of distinct copies plus one save and one restore per cycle, which is the fewest moves possible without a richer set of temporaries.

One subtlety: the “nobody reads it” test must be recomputed from the current copy set rather than from the original one, and a node whose only reader was itself must be dropped before the test. Handling it the other way round is how an implementation ends up correct on simple swaps and wrong on merges where one phi input feeds two different destinations.

Degenerate and Adversarial Cases

An unreachable block can have a phi whose incoming values are all undefined. The block is never entered, so no move for that phi ever runs, and the phi and its block can be deleted outright. Most compilers delete unreachable blocks before elimination for exactly this reason, which also removes the case where a phi’s edge values have no definition.

A phi with a single distinct input is a copy with extra steps. If all inputs are the same value, the phi is redundant and can be replaced by that value; this happens constantly after other transformations have folded branches. If the phi has only one predecessor because the other edge was proven dead, the phi collapses to a move. Both cases are handled by a simplification pass that runs before elimination, and both are worth doing because they reduce the parallel copy sets to nothing.

Self-referential phis in loop headers are the case that most often trips a naive implementation. The header phi’s back-edge input is the phi’s own result, so the copy graph contains a self-loop. A self-loop is not a cycle that needs a temporary; it is a no-op, and emitting a temporary for it adds a move per iteration in the hottest block of the loop. The condition to check is whether the source and destination are the same location, not whether the edge exists.

The last case is the phi whose inputs come from different register classes. A floating-point value and an integer value cannot share a register on most architectures, so the coalescing decision is forced and the move must go through a temporary of the correct class or through memory. Some IRs forbid such phis outright by requiring type consistency, which converts a hard problem into a front-end obligation.

What Remains After Elimination

Once phis are gone, the IR is conventional: assignments to named storage, with explicit moves. Everything that follows — scheduling, allocation, and the final emission described in Instruction Scheduling and Its Dependence on the Graph — sees a form in which every value is written and read in a definite order.

The information lost is the def-use precision. After elimination, a variable can be written in several places, and a use may refer to whichever definition reaches it along the path taken, which is exactly the situation SSA form was introduced to remove. That is why most compilers keep the SSA form as long as possible and destroy it late, and why some keep a mapping from the eliminated names back to their SSA definitions so that diagnostics and debug information can still describe values precisely. The alternative, translating to a conventional form early and reconstructing SSA for each analysis, pays the construction cost repeatedly and is only attractive when the analyses are few.