The Dominance Frontier
The frontier of A is the set of blocks where A stops being guaranteed — the first blocks reachable from A that A does not dominate. That is exactly the set of places where a definition in A might not be the one that arrives, which is exactly where a phi node goes.
Where does a definition stop being guaranteed, and why is that the same set as "where the phi nodes go"?
A map from each block to the set of blocks on the boundary of its dominance region — the blocks it can reach but does not dominate, whose immediate predecessor on that path it does dominate. It exists to answer the placement question at the heart of SSA construction: given that a variable is defined in block A, at which blocks might a different definition also arrive?
The frontier computation assumes a correct immediate-dominator map over a graph where every block is reachable. Its own correctness condition is stated as a placement rule: a phi for a variable must be inserted at every block in the *iterated* dominance frontier of the set of blocks defining that variable. Inserting fewer means a use somewhere reads a value that is wrong on one path; inserting more is merely wasteful, since a phi whose operands are all the same value is a copy that a later pass removes.
Key points
- The dominance frontier of A is the set of blocks A does not dominate but which have a predecessor A does dominate — the boundary of A's dominance region.
- It is exactly where a definition in A stops being the guaranteed one, which is exactly where a phi node is needed.
- A block that dominates the whole function has an empty frontier and contributes no phi, because its definition never stops being guaranteed.
- A phi is itself a definition, so the frontier must be iterated until it stops adding blocks — which is what produces loop-carried phis.
- A loop header appears in its own frontier, because the back edge reaches it from a block it dominates.
- Too few phis means a wrong value on some path; too many is merely wasteful and a later pass removes them.
The boundary of a guarantee
Block A dominates a region of the graph — everything for which A is guaranteed to have run. The dominance frontier of A is the boundary of that region: the blocks that A does *not* dominate, but which have at least one predecessor that A does dominate.
Read it as a claim about a value. If A defines x, then everywhere A dominates, that definition is the one in effect — no other path got there. At a block on A's frontier, control might have arrived through A's region or through somewhere else entirely, so A's definition is one possibility among several. That block is where the ambiguity begins.
Which is why the frontier is exactly the phi placement rule. A phi node is the IR construct that says "the value here depends on which edge you came in on", and the blocks where that statement is needed are precisely the blocks where a dominating definition stops dominating.
The simplest case: an `if` with no `else`
Take let x = 0; let c = 7; if (c > 3) { x = 1; } print(x);. AtlasLang lowers it to three blocks: b0 sets x to 0 and branches, b1 sets x to 1, and b2 reads x and prints. b0 branches to b1 or straight to b2; b1 jumps to b2.
The dominator relation is flat: idom is {b0: b0, b1: b0, b2: b0}. b0 dominates everything. b1 dominates only itself, because b2 is reachable without it.
So the frontier of b1 is {b2}: b1 does not dominate b2, but b1 is a predecessor of b2. The engine returns frontier = {b0: [], b1: ["b2"], b2: []}, exactly. And b1 defines x, so a phi for x goes at b2 — which is what toSSA() produces: %3 = phi x [0 from b0, 1 from b1].
Notice that b0 also defines x, and b0's frontier is empty, so b0 contributes no phi. That is right: b0 dominates the entire function, so its definition never stops being guaranteed by any path — it can only be *overwritten*, which is a different thing and is handled by renaming rather than by a phi.
if with no else- b0entryentry
store @x, 0 store @c, 7 %1 = bool 7 > 3 branch %1 ? b1 : b2
Frontier: empty. It dominates every block, so its definition never stops being the guaranteed one. - b1if.then
store @x, 1 jump b2
Frontier: {b2}. b1 does not dominate b2, but is a predecessor of it. This is the boundary. - b2if.join
%3 = phi x [0 from b0, 1 from b1] print %3
The phi goes here because b2 is in the frontier of b1, and b1 defines x.
- b0→b1true
- b0→b2false — critical edge
- b1→b2
- b0idomb0(entry)
- b1idomb0
- b2idomb0
Read it asEverything here is verbatim engine output: the idom map, the frontier {b0: [], b1: ["b2"], b2: []}, and the phi instruction. Note also that the b0 -> b2 edge is critical — b0 has two successors and b2 has two predecessors — which is why outOfSSA reports it when resolving this phi. [[cfg-construction]] is where that consequence is worked out.
Iterated, because a phi is itself a definition
toSSA(). Production implementations frequently compute the iterated frontier directly, or skip explicit frontiers altogether using semi-pruned or sealed-block SSA construction, which places fewer dead phis. The placement result is the same set of *necessary* phis; the number of unnecessary ones differs.A phi node defines a value. So placing one creates a new definition, in a new block, which has its own frontier, which may need another phi. The rule is therefore stated over the iterated dominance frontier: keep placing until placing stops adding blocks.
The clearest small example is a loop containing an if: while (i < 5) { if (i > 2) { t = t + 1; } i = i + 1; }. AtlasLang produces six blocks, and the frontier map is {b0: [], b1: ["b1"], b2: ["b1"], b3: [], b4: ["b5"], b5: ["b1"]}.
Now trace t. It is stored in b0 and in b4. The frontier of b4 is {b5}, so a phi for t goes in b5. But that phi is a definition of t in b5, and the frontier of b5 is {b1} — so a second phi for t goes in b1, the loop header. The engine inserts three phis for this function in total, and the SSA output shows exactly that: %11 = phi t [%9 from b2, %5 from b4] in b5, and %9 = phi t [0 from b0, %11 from b5] in b1.
That second phi is the loop-carried one, and it exists only because of the iteration. A construction that computed the frontier once and stopped would place the b5 phi and miss the header phi, and the loop would read t's initial value on every iteration.
Note also frontier[b1] = ["b1"]. A loop header is in its own dominance frontier, because the back edge reaches it from a block it dominates. That self-reference is not a bug — it is how the algorithm knows a loop header needs a phi for anything modified inside the loop.
t in a loop containing an ifsimplified| Step | Definition sites of `t` | Frontier of those sites | Phi placed |
|---|---|---|---|
| 1 | b0 (initial store), b4 (t = t + 1) | DF(b0) = {}, DF(b4) = {b5} | phi for t in b5 |
| 2 | ... plus b5, which the new phi defines | DF(b5) = {b1} | phi for t in b1 — the loop-carried one |
| 3 | ... plus b1 | DF(b1) = {b1}, already placed | nothing; fixed point reached |
Where this goes next
The frontier is the last piece of machinery SSA construction needs, and it is worth naming what the pieces now are. Dominance says which blocks are guaranteed. The dominator tree encodes that as ancestry and gives a valid recursion order. The frontier marks where a guarantee ends. Together they give the two halves of [[ssa-construction]]: place a phi at the iterated dominance frontier of every variable's definition sites, then walk the dominator tree with a stack per variable, renaming each load to the current definition and each store to a fresh one.
That is the entire mem2reg algorithm, and it is what toSSA() in the engine implements. Everything in this module — blocks, edges, dominance, the tree, the frontier — exists to make those two paragraphs possible.
The SSA module picks it up from here: what a phi node actually means, why one definition per value makes so many analyses cheaper, and how you leave SSA again without introducing the swap bug or mishandling the critical edge this lesson's first example produced. Start with [[ssa-construction]].
How it works
The steps, in the order the compiler takes them.
- Compute the immediate-dominator map for the function.
- Initialise an empty frontier set for every block.
- For every block with more than one predecessor, and for each of those predecessors, walk up the immediate-dominator chain from that predecessor, adding the block to the frontier of each block visited, stopping at the block's own immediate dominator.
- For SSA construction, collect the set of blocks that define each variable.
- Place a phi for that variable at every block in the frontier of those blocks, adding each newly-phi-ed block to the worklist, until no new blocks are added.
- Then rename by a pre-order walk of the dominator tree, with a stack of current definitions per variable.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- The frontier is computed once instead of iterated, so a loop-carried phi is missing from the header. The loop reads the variable's initial value on every iteration and the result is wrong in a way that looks like a logic bug in the source.
- A phi is placed with fewer operands than the block has predecessors, and one incoming edge supplies nothing. On that path the value is whatever the resolution pass defaulted to — often zero, and silently.
- The frontier is computed from a stale dominator map after a transformation changed the graph, and phis are placed at blocks that are no longer merge points while real merge points get none.
- Phis are placed everywhere control merges rather than at the frontier, and the function fills with phis whose operands are all identical. Nothing is wrong, and compile time and IR size both grow noticeably on large functions.
- The self-frontier of a loop header is treated as a bug and filtered out, and every loop-carried variable loses its phi — producing exactly the first failure mode with a plausible-sounding justification.
When it helps
- SSA construction, which is the reason the concept exists and by far its main consumer.
- Any analysis that needs to know where control-dependent information becomes uncertain — the frontier is closely related to control dependence, and the reverse-graph version of it is what control-dependence analysis computes.
- Understanding why phis appear where they do in a dump. "Why is there a phi here and not there" is answered directly by the frontier of the defining blocks.
When it hurts
- For a variable defined in only one block that dominates all its uses, the whole apparatus produces nothing and the computation was pure overhead — which is why construction algorithms that avoid computing explicit frontiers exist.
- On very large functions, where frontier sets can grow large and the iteration is a real compile-time cost. Semi-pruned and sealed-block construction exist substantially for this reason.
What it costs
Every one of these is paid by something.
- Placing phis at the iterated frontier buys minimal correct placement and pays with a dominance computation, a frontier computation, and a per-variable worklist iteration before any renaming can start.
- Placing phis at every merge point instead buys a much simpler implementation and pays in IR size and compile time, since most of those phis have identical operands and a later pass has to remove them.
- Pruned construction — placing a phi only where the variable is actually live — buys fewer dead phis and pays with a liveness analysis before construction, which is an extra pass over the function.
What else you could do
What a different compiler or language does instead, and when that is better.
- Braun et al.'s sealed-block construction builds SSA directly during IR generation with no explicit dominance or frontier computation, querying predecessors on demand and sealing a block once all its predecessors are known. It is the standard modern choice for a frontend that generates SSA as it lowers, and it produces minimal SSA without ever materialising a frontier.
- Semi-pruned SSA, which excludes variables that are local to a single block before computing anything, cutting the work substantially for the common case at the cost of one extra scan.
- Pruned SSA, which additionally consults liveness so that no phi is placed for a variable that is dead at that point — fewer phis, one more analysis.
- Block parameters instead of phi nodes, as Cranelift and Swift SIL use. The placement question is the same; what changes is that the value rides the jump, so the critical-edge problem this lesson's first example produces never arises —
[[ir-design-tradeoffs]].
See it for yourself
The flag, dump or tool that shows you this directly.
opt -passes=mem2reg -S file.llpromotes stack slots to SSA registers and shows the resulting phis; running it on-O0output for a function with anifshows exactly the placement this lesson describes.opt -passes='print<domtree>' file.llprints the tree the frontier is derived from, which is usually what you actually want when a phi looks misplaced.rustc --emit=mirshows MIR, which is deliberately *not* in SSA form — a useful contrast, since Rust's borrow checker wanted a representation with named locals rather than phis.- Our SSA converter at
/compilers/ssashows the frontier map and the phis it produced for whatever you type, usingcomputeDominance()andtoSSA()directly.
Plausible wrong readings
Stated the way a confident engineer states them.
- "The frontier of A is the blocks A can reach." It is the boundary — the blocks A can reach but does not dominate, whose predecessor on that path A does dominate. A can reach far beyond its frontier.
- "Phis go at every merge point." They go where a *definition* stops dominating. A merge point where nothing relevant was redefined needs no phi, which is why the frontier and not the predecessor count is the rule.
- "A block cannot be in its own dominance frontier." A loop header always is, because the back edge reaches it from a block it dominates. That self-reference is what places the loop-carried phi.
- "One pass of frontier placement is enough." A phi is a definition, so placement must iterate. Missing the iteration is precisely how loop-carried phis go missing.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
A block guarantees everything it computes for the region it dominates. The dominance frontier is where that region ends — the first blocks reachable from it that it no longer guarantees. Those are exactly the places where the value might have come from somewhere else instead, and that is exactly where the compiler has to insert a phi node saying "it depends which way you came in".
practical
When a phi in a dump looks like it is in the wrong place, work it backwards: find the blocks that define the variable, and compute where each stops dominating. That set is where the phis must be. If a phi is missing where you expect one, the usual cause is that the placement was not iterated — the phi in the inner merge is itself a definition, and its own frontier needs one too. Loop headers are where that shows up first.
advanced
The dominance frontier is one half of a duality worth knowing. Computed on the reverse graph with post-dominance, the same construction yields *control dependence*: block B is control-dependent on A when A decides whether B executes. Cytron et al. observed that phi placement and control dependence are the same computation on two different graphs, which is why a compiler that has one usually gets the other cheaply. It also explains why the frontier feels like it is about values when it is really about control: a value becomes uncertain exactly where control did.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
If you were asked this in an interview
- Define the dominance frontier, then explain why it is the right place for a phi node.
- Why must phi placement iterate rather than run once?
- Why is a loop header in its own dominance frontier?
Connections
- Programming Languages & Runtime Internals — Reconstructing interpreter state at a deoptimization pointA JIT that bails out to the interpreter must know which value is live for each source variable at that point, which is the same "which definition reaches here" question SSA answers — asked of compiled code at run time rather than at build time.