Phi Functions
At a merge point no single definition reaches the use, so SSA writes `x3 = phi(x1, x2)` — "the value depends on which edge you arrived by". It is a notation, not an instruction, and nothing ever executes one. That is precisely why `[[out-of-ssa]]` has to exist.
What is a phi node actually doing, and how can an instruction that cannot be executed be part of the IR?
SSA IR in which each merge block begins with a phi per variable that had different definitions on the incoming paths. A phi is a mapping from incoming CFG edges to values — one operand per predecessor, in a fixed correspondence with the predecessor list. The question it exists to answer is the only one plain SSA cannot: *which of several definitions reaches this use*, when the answer depends on control flow rather than on data.
A phi is well-formed only if it has exactly one operand per predecessor of its block, its block's predecessor list is accurate, and every operand's definition dominates the end of the corresponding predecessor block — not the phi's own block. That last condition is the one people get wrong, and it is what makes a phi different from an ordinary instruction: its operands are evaluated on the edges, so they need only be available where the edge starts. All phis at the top of a block execute conceptually *simultaneously and before* everything else in the block, which is a semantics no ordinary instruction has.
Key points
- A phi is required exactly where several definitions of the same variable reach one use because control flow merged.
- It maps incoming edges to values: one operand per predecessor, and the pairing is the meaning.
- It is a notation, not an executable instruction. Nothing runs a phi; it is compiled away when SSA is destroyed.
- All phis at the top of a block are conceptually simultaneous, which is what makes a swap expressible and makes sequential emission wrong.
- A phi operand must dominate the end of its own predecessor, not the phi's block — otherwise loop-header phis could not exist.
- Loop headers get one phi per loop-carried variable, which is how a loop-carried dependence becomes a data dependence.
Where the rule runs out
The single-definition rule survives straight-line code without effort and survives branching right up to the point where the branches come back together. Assign x in the then-arm and again in the else-arm and you have two definitions, x1 and x2, which is fine. The problem is the statement after the if, which reads x — and there is no single name for it to read.
Both definitions reach it. Neither dominates it, because either arm can be skipped. Renaming the use to x1 would be wrong on the else path and renaming it to x2 would be wrong on the then path. The form needs a way to say "whichever one you arrived with", and that is all a phi is.
- b0entryentry
%1 = bool 7 > 3 branch %1 ? b1 : b2
Two successors. Nothing about `x` yet. - b1if.then
; x is 1 on this path
Definition one. - b2if.else
; x is 2 on this path
Definition two. - b3if.join
%3 = phi x [1 from b1, 2 from b2] print %3
Two predecessors. Neither definition dominates this block.
- b0→b1
- b0→b2
- b1→b3
- b2→b3
- b0idomb0(entry)
- b1idomb0
- b2idomb0
- b3idomb0
Read it asRead the idom map: b3 is dominated by b0, not by either arm. That is exactly the condition under which a phi is required — a block whose immediate dominator is not its only predecessor. The dominance frontier machinery in [[ssa-construction]] is a way of finding every such block without checking them one at a time.
The notation, on real output
Here is the same program through the real engine. %3 = phi x [1 from b1, 2 from b2] reads: the value of %3 is 1 if control arrived from b1, and 2 if it arrived from b2. The x is a label carried over from the source variable, kept only so the dump is readable; it plays no part in the semantics.
The operand order is not free. Each operand is paired with a predecessor block id, and the pairing is the meaning. Our test suite asserts that every phi's operand blocks are exactly the block's predecessor list, sorted — a phi that has lost track of which operand belongs to which edge is not a slightly-wrong phi, it is a miscompilation waiting for the branch to go the other way.
toSSA — one phi insertedb0: ; entry store @c, 7 store @x, 0 %0 = load @c %1 = bool %0 > 3 branch %1 ? b1 : b2 b1: ; if.then preds=b0 store @x, 1 jump b3 b2: ; if.else preds=b0 store @x, 2 jump b3 b3: ; if.join preds=b1,b2 %2 = load @x print %2 ret
▸b0: ; entry▸ %1 = bool 7 > 3▸ branch %1 ? b1 : b2▸b1: ; if.then preds=b0▸ jump b3▸b2: ; if.else preds=b0▸ jump b3▸b3: ; if.join preds=b1,b2▸ %3 = phi x [1 from b1, 2 from b2]▸ print %3▸ ret
Read it asThe store @x, 0 in the entry block vanished without a trace, because no path from it reaches a load of x — both arms overwrite it. That deletion was not dead-code elimination; it is a side effect of renaming, and it is the first hint of why [[why-ssa-helps]] claims that several analyses become free.
1let c = 7;2let x = 0;3if (c > 3) { x = 1; } else { x = 2; }4print(x);Not an instruction
x label inside our phi is an AtlasLang debugging aid and is not part of the phi's meaning. LLVM's syntax is %3 = phi i32 [ 1, %b1 ], [ 2, %b2 ] and carries a type instead of a name; GCC's GIMPLE dumps write x_3 = PHI <1(2), 2(3)> with block numbers. All three encode the same edge-to-value mapping.A phi cannot be executed, and this is worth stating flatly because every other line in an IR can be. There is no machine instruction that means "copy whichever operand corresponds to the edge we came in on" — by the time the merge block is running, the branch has already retired and the edge is not available to inspect. Some machines have a conditional move, but a conditional move evaluates a condition, and a phi has no condition. It has a *provenance*.
So the phi is a claim about the past made in the present. It says "on the edge from b1, this value was 1". The natural place to put that claim into effect is on the edge itself — that is, at the end of b1 — and that is exactly what [[out-of-ssa]] does. Every phi becomes a set of copies in its predecessors, and the phi disappears before code generation.
The second thing that follows from "not an instruction" is the parallel semantics. Phis at the top of a block all read the values as they were at the end of the predecessor, not as they are after some earlier phi in the same block has run. A block whose first two phis are %11 = phi [%12 ...] and %12 = phi [%11 ...] is describing a swap, and emitting those two lines as sequential copies produces two registers holding the same value. That is the swap problem, and it is a bug about semantics rather than about ordering.
b1: jump b3 b2: jump b3 b3: %3 = phi x [1 from b1, 2 from b2] print %3
b1: %3 = copy 1 jump b3 b2: %3 = copy 2 jump b3 b3: print %3
Only if the copies are placed on the edge the operand belongs to, and only if every phi at the top of the block is translated as one simultaneous parallel copy per edge rather than as independent copies emitted in listing order. When the predecessor has a single successor, "on the edge" and "at the end of the predecessor" are the same place, which is the case here.
The predecessor has several successors — a critical edge — so a copy at its end also executes on paths that never enter the merge block. And when two phis in the same block reference each other's destinations, sequential emission changes the meaning: %11 = copy %12 followed by %12 = copy %11 leaves both registers holding the original %12, so the swap the source asked for does not happen. Both cases are [[out-of-ssa]]'s problem, and both silently produce wrong values rather than errors.
Why they cluster at loop headers
The other place merges happen is the top of a loop, where the entry edge and the back edge come together. Every variable the loop modifies needs a phi at the header — one operand for the value coming in from outside, one for the value coming round again — and those phis are how a loop-carried dependence becomes visible as data rather than as control.
This is also why the phi has to be a fixed point rather than something computable in one pass: the operand coming from the back edge names a value the loop body has not been renamed to produce yet. Construction handles it by placing the phis before renaming and filling in the operands as each predecessor is walked, which is [[ssa-construction]]'s third step.
▸b0: ; entry▸ jump b1▸b1: ; while.cond preds=b0,b2▸ %8 = phi s [0 from b0, %4 from b2]▸ %9 = phi n [0 from b0, %6 from b2]▸ %1 = bool %9 < 3▸ branch %1 ? b2 : b3▸b2: ; while.body preds=b1▸ %4 = int %8 + %9▸ %6 = int %9 + 1▸ jump b1▸b3: ; while.exit preds=b1▸ print %8▸ ret
Read it asThe header phis are *defined before* the values they reference: %8 names %4, which is defined two blocks later in the listing. This is legal SSA — the requirement is that the operand dominates the end of b2, and it does. It is also exactly why a naive "every use comes after its definition" verifier check is wrong, and why phi operands are checked against predecessors instead.
How it works
The steps, in the order the compiler takes them.
- At a block with several predecessors, ask which variables have different definitions reaching along different incoming edges.
- For each such variable, prepend a phi to the block with a slot per predecessor.
- During renaming, give the phi a fresh destination register and push it as the current definition for the rest of the dominated region.
- When walking each predecessor, fill in that predecessor's slot with whatever the current definition of the variable is at the end of that block.
- Verify afterwards that the set of operand blocks equals the block's predecessor set — this is the one invariant that catches most construction bugs.
- At destruction, replace each phi with copies placed on the incoming edges, sequenced as a parallel copy.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- An operand is paired with the wrong predecessor. The program computes the correct answer for one branch direction and a wrong one for the other, so it passes any test that only exercises the common path.
- A predecessor is added to a block — by a later transformation splitting a path, say — and the existing phis are not extended. On the new edge the phi reads uninitialized memory or an arbitrary register, and the failure is intermittent and target-dependent.
- A phi is emitted somewhere other than the very top of its block. Anything before it observes the pre-merge state, and values come out one iteration stale in a loop.
- An engineer single-steps a debugger expecting to land on a phi and never does, then concludes the optimizer deleted their code. The phi was never going to execute; the copies that replaced it are attributed to the branch, not to the merge.
When it helps
- Making loop-carried dependencies explicit, which is the precondition for almost every loop optimization —
[[loop-invariant-code-motion]]cannot decide what is invariant without knowing what the header phis are. - Sparse analyses. Because a phi is the only place values merge, a propagation pass can push facts along def-use edges and only reconsider a value when one of its phi operands changes.
- Reading control-flow-sensitive code. A phi lists the possibilities at a merge, which is often faster to read than reconstructing them from the branches.
When it hurts
- Backends. Every phi is a debt that must be paid in copies, and paying it badly is the source of the three hazards in
[[out-of-ssa]]. - Code with very many merge points and very many live variables, where the phi count grows fast enough that construction and every subsequent pass slow measurably. This is what pruned SSA in
[[ssa-variants]]exists to reduce. - Debug information. A source variable that is a phi at a merge has no single location, and the debugger has to describe it as a piecewise location expression or give up.
What it costs
Every one of these is paid by something.
- Making merges explicit buys an IR where every use has one reaching definition; it pays a phi node per variable per merge, and each of those costs memory during compilation and copies at destruction.
- The parallel semantics buys the ability to express a simultaneous swap without a temporary; it pays a sequencing algorithm in the backend, plus the temporary registers that algorithm allocates when it finds a genuine cycle.
- Keeping a source name on the phi buys readable dumps and better debug info; it pays memory on every phi and a maintenance burden — the name has to be updated or dropped by every pass that rewrites the phi, and passes that forget produce dumps that lie.
What else you could do
What a different compiler or language does instead, and when that is better.
- Continuation-passing style replaces the phi with a parameter of the join continuation, and the incoming values with arguments at the call sites. The information is identical; the advantage is that scoping is explicit and there is no special "simultaneous" rule, and the cost is a representation less familiar to most compiler engineers.
- Block arguments, as in MLIR, Swift's SIL and Cranelift: the merge block takes parameters and each branch supplies arguments. This is CPS's idea in an SSA-shaped IR, and it removes the parallel-copy special case by making the values arrive at the branch, where they already have to be. The cost is that every branch instruction grows an argument list.
- Do not merge at all — duplicate the join block into each arm (tail duplication). This removes the phi and can expose more optimization on each path, at a direct cost in code size and instruction-cache pressure.
See it for yourself
The flag, dump or tool that shows you this directly.
clang -S -emit-llvm -O1 -o - t.con any function with anifthat assigns the same variable in both arms. Thephilines appear at the top of the join block, with the predecessor labels visible.gcc -fdump-tree-ssa -c t.cwritest.c.*.ssa, whosePHI <...>nodes name source variables with version suffixes, which is easier to follow than numbered registers when you are learning.- Compiler Explorer with the LLVM IR output pane: change a branch into a
?:and watch the phi turn into aselect, which is the same merge expressed as data rather than control. - Our CFG viewer and SSA converter at
/compilers/ssashow the phi and highlight which predecessor each operand came from.
Plausible wrong readings
Stated the way a confident engineer states them.
- "The phi picks whichever operand is not undefined." It has no way to test that. It selects by *edge*, and both operands are perfectly defined values on their own paths.
- "A phi is a conditional move." A conditional move evaluates a condition at the point it runs. A phi refers to how control arrived, which is information the machine has already thrown away.
- "Phis cost instructions at run time." They cost copies, and often not even that — a good allocator coalesces the phi destination with its operands so that the copies disappear entirely.
- "If a phi's operands are all the same value, construction made a mistake." Construction deliberately does not check. Placement is decided by dominance frontiers alone, and removing the trivial ones is copy propagation's job — see
[[ssa-construction]].
Misconceptions
The claim, and what is actually true.
if statements.Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
When two paths that assigned the same variable come back together, SSA cannot name a single definition for the code after the merge. A phi node is the notation for "whichever value came in on the edge we took". It is written at the top of the merge block with one operand per incoming edge.
practical
In a dump, a phi tells you two useful things at a glance: this block is a merge, and this value differs by path. At a loop header the phi's second operand names the value computed by the body, which is how you find the loop-carried variable without reading the loop. If you are writing a pass that changes the CFG, the rule to remember is that adding or removing an edge means adding or removing an operand from every phi in the target block — forgetting is the most common way to corrupt SSA.
advanced
The parallel semantics is not a convenience, it is forced. Consider a loop that swaps two variables each iteration: the header holds %11 = phi [%12 from latch] and %12 = phi [%11 from latch]. Under sequential semantics that pair is unsatisfiable — no ordering of two copies produces a swap — so if phis were ordinary instructions, SSA could not represent a program that any programmer can write in one line. Making them simultaneous makes the representation total, and pushes the difficulty into destruction, where a parallel-copy sequencer resolves it with one temporary per cycle. AtlasLang's sequenceParallelCopies is that sequencer, and it is verified by simulating the moves rather than by comparing them to an expected list, because a wrong expectation would pass.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
phi x [...] syntax are AtlasLang's, from toSSA in src/compilers/sim/ir.ts. LLVM writes phi i32 [ v, %pred ] with a type and no source name; GCC's GIMPLE dumps write x_3 = PHI <1(2), 2(3)>. The mapping from edges to values is the same in all three.mov instructions.If you were asked this in an interview
- Write the SSA form of an
if/elsethat assigns the same variable in both arms, and say what the phi means. - Why can a phi not be implemented as a machine instruction?
- Two phis at the top of a block reference each other's destinations. What does that program do, and what goes wrong if you emit the copies in order?
Connections
- Programming Languages & Runtime Internals — How a debugger reconstructs a variable that has no single storage locationA source variable that becomes a phi is spread across registers and edges. Presenting it back to a human at a breakpoint is a runtime and debug-format problem, and the format's location-expression machinery is owned there.