SSAimplementation

Constructing SSA

The real algorithm, in two halves: place a phi for each variable at the iterated dominance frontier of its definitions, then rename by walking the dominator tree with a stack per variable. That is Cytron et al., that is LLVM's mem2reg, and that is exactly what `toSSA` does.

The question

How does a compiler decide where phi nodes go, without checking every block for every variable?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

Input: three-address IR where locals are load/store against named slots, plus a dominator tree and a dominance frontier computed over the CFG. Output: SSA IR with no slots at all. The intermediate representation that makes the algorithm work is the dominance frontier — for a block n, the set of blocks that n reaches but does not dominate, which is precisely the set of places where a definition in n stops being the only one that could have reached.

What this phase may assume or do

Construction preserves observable behavior if three conditions hold. The promoted slot's address never escapes, so nothing outside these instructions can read or write it. Every load is replaced by the definition that actually reached it on every path — guaranteed by walking the dominator tree, since the current top of a variable's stack is by construction the nearest dominating definition. And every phi ends with exactly one operand per predecessor. The pass is entitled to assume the CFG is reducible enough for the dominator computation to converge, and that the frontend rejected use-before-declaration; when a variable is genuinely only assigned on some paths, AtlasLang substitutes a documented zero rather than leaving an undefined operand.

Key points

Phis go at the iterated dominance frontier of a variable's definition sites — a decision made from graph shape alone.
The iteration is needed because a placed phi is itself a definition, which may force further phis.
Renaming walks the dominator tree with a stack per variable, so the stack top is always the nearest dominating definition.
Two traversals do two jobs: the dominator tree decides scope, and CFG successor edges decide which phi operand slot gets filled.
Placement never inspects values, so trivially-identical phis are expected output, not a bug; copy propagation removes them.
Placement never consults liveness either, so dead phis are also expected — removing those is what pruned SSA is.
Loads are deleted rather than renamed, which is why SSA output has gaps in its register numbering.

The lazy answer, and why nobody uses it

You could put a phi for every variable at the top of every block with more than one predecessor. It would be correct. It would also be enormous — every merge would carry a phi for every variable in the function, most of them merging a value with itself — and every later pass would then spend its time walking phis that say nothing. This is *maximal* SSA, and it is only ever used as a proof device.

What we want is a phi exactly where a variable's value genuinely depends on the path taken. The insight, from Cytron, Ferrante, Rosen, Wegman and Zadeck in 1991, is that this set can be computed from dominance alone, without looking at values: a definition in block n needs a phi at exactly those blocks where n's influence stops, and that is the *dominance frontier* of n.

Step one: the iterated dominance frontier

simplifiedAtlasLang runs this loop per variable over all slots, which is the textbook presentation. LLVM's PromoteMemToReg adds several fast paths first — a slot with a single store, or one used only within one block, is promoted without computing a frontier at all — because those cases dominate real code and the general algorithm is wasted on them.

The dominance frontier of n is the set of blocks m such that n dominates a predecessor of m but does not strictly dominate m itself. Informally: the first places where control coming through n can meet control that did not. A definition in n is the only definition anywhere it dominates — so the first place it stops being the only one is precisely the frontier, and that is where a phi is needed.

One pass is not enough, because a phi is itself a definition. Placing a phi at m means m now defines the variable, so m's own frontier may need phis too. Iterating this to a fixed point gives the *iterated* dominance frontier, and the loop below — straight out of toSSA — is that fixed point: each newly placed phi is pushed back onto the worklist as a new definition site.

The dominance frontier in AtlasLang is computed by the Cooper-Harvey-Kennedy method: for every block with several predecessors, walk up the dominator tree from each predecessor to the block's immediate dominator, adding the block to the frontier of everything passed on the way. [[dominance-frontier]] covers why that walk is correct; here it is a subroutine.

Phi placement, transcribed from `toSSA` in src/compilers/sim/ir.ts

1for each variable v:
2  sites    = blocks containing a store to v
3  worklist = copy of sites
4  placed   = {}
5  while worklist not empty:
6    n = worklist.pop()
7    for each df in frontier[n]:
8      if df in placed: continue
9      placed.add(df)
10      prepend an empty phi for v to block df
11      if df not in sites: worklist.push(df)   // the phi is itself a definition

Note what is absent: nothing looks at the values being stored, and nothing checks whether the arriving values differ. Placement is a question about the shape of the graph, decided before renaming has produced any values to compare.

Step two: renaming down the dominator tree

With the phis in place but empty, the second half rewrites every load and store. It walks the *dominator tree*, not the CFG, and keeps a stack per variable holding the current definition. The reason the dominator tree is the right traversal is the whole trick: when you enter a block, the top of each stack is the nearest definition that dominates you, and a definition that dominates you is by definition the one that reaches you on every path.

A store pushes its value onto the variable's stack and disappears — it is no longer an instruction, it is a name binding. A load does not become a copy; it is deleted, and every later use of its destination register is rewritten to the stack top. That is why the SSA output has no load instructions at all and why the register numbering comes out with gaps.

Before recursing into the dominator-tree children, the walk visits each *CFG successor* and fills in that successor's phi operand for this block from the current stack top. Two different traversals, in the same function, doing two different jobs: the dominator tree decides what is in scope, and the CFG edges decide which phi slot gets filled. Getting these two confused is the classic implementation bug, and the symptom is a phi whose operand blocks do not match its predecessors.

On the way out, the walk pops everything it pushed. That restores the stacks for the sibling subtree, which is what makes the scoping correct.

Renaming, transcribed from the same function

1rename(block):
2  pushed = []
3  for each instruction i in block:
4    if i is a phi:      i.dest = fresh(); push(i.name, i.dest); keep i
5    if i is load  v:    replace all uses of i.dest with top(v); delete i
6    if i is store v, s: push(v, s); delete i
7  for each CFG successor s of block:          // CFG edges
8    for each phi p in s:
9      p.sources.add({ from: block, value: top(p.name) })
10  for each dominator-tree child c of block:   // dominator tree
11    rename(c)
12  pop everything in pushed

A store pushes the value it stores, not a new register — so a chain of x = y produces no copies at all, and copy propagation over the result has nothing left to do for that case.

Placement does not look at values — and that is on purpose

Because placement is decided by graph shape alone, construction will happily insert a phi whose operands turn out to be identical. The function below assigns the same value in both arms of an if; b3 is still on the dominance frontier of both arms, so a phi is still placed, and the result is %7 = phi v [%1 from b1, %1 from b2] — a phi that merges a value with itself.

This is not a defect to be fixed in construction. Checking whether the arriving values agree would mean renaming first, and renaming needs the phis to already be there; the dependency runs the wrong way. So the placement pass is deliberately blind, and the cleanup is left to [[copy-propagation]], which sees a phi with one distinct operand, replaces its uses with that operand, and deletes it. Our pass manager relies on this: the "both arms assign the same thing" example is the case that makes the copy-propagation toggle demonstrably do something.

The same reasoning explains the other surprise in real dumps — a phi for a variable that is dead after the merge. Placement does not consult liveness either. Consulting it is what pruned SSA does, and it costs a liveness analysis up front; see [[ssa-variants]].

A trivially-identical phi, produced by real construction

SSA — note the operands

▸b0: ; entry
▸  %0 = param 0 ; c: int
▸  %1 = param 1 ; a: int
▸  %3 = bool %0 > 0
▸  branch %3 ? b1 : b2
▸b1: ; if.then preds=b0
▸  jump b3
▸b2: ; if.else preds=b0
▸  jump b3
▸b3: ; if.join preds=b1,b2
▸  %7 = phi v [%1 from b1, %1 from b2]
▸  ret %7

Read it asBoth operands are %1. The phi merges nothing. It exists because b3 is on the dominance frontier of both arms, which is a fact about the graph and not about the values — and it is removed one pass later, not by construction.

Both arms assign the same value

1fn g(c: int, a: int): int {
2  let v = 0;
3  if (c > 0) { v = a; } else { v = a; }
4  return v;
5}

What it costs

The dominance computation is the iterative Cooper-Harvey-Kennedy algorithm, which converges in a small number of passes over reverse post-order for the shapes real code produces. Phi placement is linear in the size of the dominance frontiers, and renaming is one walk of the dominator tree. In practice the whole thing is close to linear in program size, which is why compilers run it unconditionally above -O0.

The number of phis Cytron's algorithm places is minimal *for the placement criterion it uses* — no phi is placed at a block that is not on an iterated dominance frontier. It is not minimal in the sense of "the fewest phis a correct SSA form could have", because it ignores both value equality and liveness. Those two omissions are what the variants in [[ssa-variants]] address, and each buys fewer phis at the price of an extra analysis.

Where the work goesimplementation

Step	What it computes	Roughly costs	Failure if omitted
Dominators	Immediate dominator per block	A few passes over reverse post-order	No frontier, so no way to decide placement
Dominance frontier	Where each block's influence ends	One walk up the tree per merge predecessor	You fall back to a phi at every merge
Iterated frontier	Fixed point, since phis are definitions too	Worklist over newly placed phis	Missing phis in loops and nested merges; uses read stale values
Renaming	One definition per use	One dominator-tree walk with a stack per variable	Phis with no operands and loads with no definition
Operand fill-in	Which value arrives on which edge	One pass over CFG successors per block	Phi operands mismatched to predecessors — wrong value on one branch only

How it works

The steps, in the order the compiler takes them.

Compute reverse post-order, then immediate dominators by iterative intersection (Cooper-Harvey-Kennedy).
Derive the dominance frontier: for every block with several predecessors, walk from each predecessor up to that block's immediate dominator, adding the block to the frontier of every block on the way.
Collect the set of blocks containing a store for each promotable variable.
Worklist over those sites; for each, place an empty phi at every frontier block not yet handled, and push newly-phi'd blocks back on because a phi is a definition.
Walk the dominator tree from the entry, maintaining a stack of the current value per variable.
In each block: a phi gets a fresh register and is pushed; a store pushes its value and is deleted; a load is deleted and its uses rewritten to the stack top.
Fill each CFG successor's phi operand for this block from the stack top, then recurse into dominator-tree children, then pop everything pushed in this block.
Drop the slot list. The function no longer has local variables, only values.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

The iteration is skipped and only the first-order frontier is used. Nested merges and loops end up missing phis, and a use reads a value from the wrong iteration — output is off by one and only in the loop.
Renaming walks the CFG instead of the dominator tree. Values leak between sibling branches, so a variable assigned only in the then-arm is visible in the else-arm, and the program computes with a value from a path it did not take.
The stack is not popped on the way out of a block. Later siblings see definitions from an earlier subtree, and the symptom is a value that is correct on the first branch executed and wrong afterwards.
Phi operands are filled from dominator-tree children rather than CFG successors. Phis end up with operands attributed to blocks that are not predecessors, and the verifier — if there is one — reports an arity mismatch; if there is not, one branch direction miscompiles.
A slot whose address escaped is promoted. Writes through the pointer are invisible to the promoted value, and the function reads stale data with no diagnostic anywhere.

When it helps

Every optimization downstream. Construction is the price of admission to an SSA middle-end, and the passes that follow are collectively worth far more than it costs.
Removing memory traffic that the frontend emitted for convenience. A frontend that lowers every local to alloca/load/store is much simpler to write, and mem2reg is what makes that simplicity free.
Exposing loop-carried dependencies as header phis, which is the input every loop transformation needs.

When it hurts

At -O0 or in a baseline JIT tier, where the dominance computation and renaming walk are pure overhead because nothing downstream will use the result.
On functions with pathological control flow — very many merges and very many live variables — where the phi count and the frontier computation are the compile-time bottleneck. Irreducible control flow from computed goto or from decompiled code is the usual source.
When most locals cannot be promoted because their addresses escape. You pay for the analysis and promote almost nothing, and the real win would have come from alias analysis instead.

What it costs

Every one of these is paid by something.

Frontier-based placement buys near-minimal phi counts; it pays for a dominator tree and a frontier computation before a single instruction is rewritten, and those are not free on large functions.
Deleting loads rather than turning them into copies buys a smaller IR and fewer instructions for later passes to walk; it pays in traceability — the register numbers no longer correspond to anything, and a dump is harder to match against the source.
Deliberately ignoring values during placement buys a construction pass that is a pure function of the CFG and therefore easy to test; it pays a population of trivial phis that a later pass has to clean up, and a reader who does not know this thinks the compiler is confused.
Ignoring liveness during placement buys one fewer analysis in the pipeline; it pays phis for variables that are dead after the merge, which cost memory in every pass that follows and copies at destruction unless something removes them.

What else you could do

What a different compiler or language does instead, and when that is better.

Braun et al.'s "Simple and Efficient Construction of SSA Form" (2013) builds SSA directly from the AST with no dominance computation at all, creating phis lazily when a block is sealed and removing trivial ones on the spot. It is what Cranelift-style and several JIT frontends use, because it skips a whole analysis and naturally produces pruned SSA. The cost is that it is harder to reason about for irreducible graphs and interleaves construction with simplification.
Aycock and Horspool's minimal-phi construction places phis everywhere and then removes the ones that turn out to be unnecessary. Conceptually simpler, and much more expensive on large functions.
Skip promotion entirely and let a memory-SSA layer reason about loads and stores in place. This is what LLVM does for the slots it cannot promote, and it is strictly more general and strictly more expensive.
For a language whose locals are already immutable bindings, the frontend can emit SSA directly and skip construction. The parser has the scope information, so the stack discipline is already there — this is what several functional-language compilers do.

See it for yourself

The flag, dump or tool that shows you this directly.

opt -passes=mem2reg -S t.ll on unoptimized IR shows exactly this algorithm and nothing else, which is the single clearest way to watch construction happen.
opt -passes='print<domfrontier>' -disable-output t.ll prints the dominance frontier LLVM computed, so you can check by hand that the phis landed where the frontier said.
gcc -fdump-tree-ssa-details includes the phi placement decisions in the dump, with the variable versions attached.
Our dominator-tree and SSA-converter interactives at /compilers/ssa show the frontier and the placed phis for the same program side by side; phisInserted in the pipeline output is the count this algorithm produced.

Plausible wrong readings

Stated the way a confident engineer states them.

"A phi goes wherever two paths merge." Wherever two paths merge *and* the variable has definitions on more than one of them, reachable through the frontier. Plenty of merges need no phi for a given variable.
"The algorithm figures out which values differ." It never looks at a value. That is why identical-operand phis come out of it and why the pass is a pure function of the CFG.
"Renaming is just walking the blocks in order." Block order is not the dominance order. Walking the block list works by accident on straight-line code and produces wrong scoping the moment there is a branch.
"mem2reg is an optimization pass." It is a representation change. It happens to delete memory traffic, but its purpose is to make everything after it possible.

Misconceptions

The claim, and what is actually true.

Construction puts a phi wherever it might be needed and then checks.

It puts a phi wherever the iterated dominance frontier says, and never checks. The checking that does happen — removing phis whose operands agree — is a later, separate pass.

The dominance frontier is an optimization detail you can skip.

Without it you are placing phis at every merge for every variable, which is correct but produces an IR several times larger and slows every subsequent pass.

Renaming can be done in one linear pass over the instructions.

Only for a single block. Across a CFG the scoping is dominance-shaped, which is why the walk is a tree traversal with an explicit push/pop discipline.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Building SSA is two steps. First decide where phi nodes go: at the places where a definition's influence ends, which dominance calls the dominance frontier, iterated because each new phi is itself a definition. Then rename: walk the dominator tree keeping a stack of the current value for each variable, rewriting reads to the top of the stack and writes to a fresh name.

practical

The two things to hold on to when reading a construction implementation are which traversal is being used where, and when the stack is popped. Dominator tree for recursion and scoping; CFG successors for filling phi operands. Pop on the way out of a block, not at the end of the function. If you see a bug where a value leaks between the arms of an if, one of those two is wrong. And if you see phis whose operands are all identical, nothing is wrong at all — that is what the algorithm produces by design.

internals

Cytron's placement is minimal with respect to its criterion but not with respect to what a human would call necessary, and the gap has a name in each direction. It ignores value equality, producing phis that merge a value with itself — removed later by copy propagation or by global value numbering. It ignores liveness, producing phis for variables dead after the merge — removed by pruning, which needs a liveness analysis first, or avoided entirely by Braun's on-the-fly construction, which naturally never creates them because it only asks for a variable's value when something actually reads it. The engineering question is therefore not "which produces fewer phis" but "where do you want to pay": an analysis before construction, a cleanup pass after it, or a construction algorithm with a different shape. All three ship in production compilers.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationThe pseudocode is a transcription of toSSA in src/compilers/sim/ir.ts at this commit, including the decision to delete loads rather than copy them and to substitute zero for a variable not defined on all paths. LLVM's PromoteMemToReg has several single-store and single-block fast paths before it reaches the general algorithm, and reports undefined rather than zero.

typicalCytron-style frontier placement is the textbook and the mainstream choice, in LLVM and GCC among others. It is not the only production choice: Braun et al.'s on-the-fly construction skips dominance entirely and is used in several JIT frontends, and it produces pruned SSA without a separate liveness pass.

simplifiedAtlasLang promotes every local unconditionally, because the language has no address-of operator and therefore no escaping slot. A compiler for C must run an escape check per slot first, and the ones that fail stay in memory — so a real mem2reg promotes a subset, not everything.

If you were asked this in an interview

Where do phi nodes go, and why is the dominance frontier the right answer rather than "every merge"?
Why does the placement step have to iterate?
The renaming walk uses two different traversals of the same function. Which is which, and what breaks if you swap them?
You see a phi whose two operands are the same register. Is that a bug? Justify your answer.

Connections

DSAdfs directed-graph stack topological-sort

Domains that do not exist yet

Testing & Reliability Engineering — Property-based testing over generated inputs
The invariants here — one definition per register, one phi operand per predecessor — are properties rather than examples, and our sim test checks them over every worked example. The general technique for generating the inputs is owned there; [[compiler-fuzzing]] is the compiler-specific application.