CFGimplementation

Dominators

A dominates B if every path from the entry to B goes through A — so if B runs, A has already run. Loops make the graph cyclic, so this cannot be computed in one traversal: the algorithm iterates until a full pass changes nothing, and the second pass is not optional.

The question

What does it mean for one block to dominate another, and why does computing it require iteration?

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

What the program is here

The CFG plus a map from each block to its immediate dominator — the closest block that dominates it. That map is a complete encoding of the full dominance relation, since A dominates B exactly when A is on the chain of immediate dominators from B up to the entry. It exists to answer one question that guards a great many transformations: if B executes, has A definitely already executed?

What this phase may assume or do

The computation assumes every block is reachable from the entry, because an unreachable block has no path from the entry and therefore no dominator, and the algorithm has no answer to give for it. AtlasLang enforces this by pruning unreachable blocks after lowering. It also assumes the predecessor lists agree with the terminators — dominance computed over stale edges is a correct answer about a graph that is not the program.

Key points

A dominates B when every path from the entry to B passes through A; the immediate dominator is the closest such block.
The immediate-dominator map encodes the whole relation, because A dominates B exactly when A is on B's chain of immediate dominators.
Loops make the graph cyclic, so a single traversal cannot compute dominance — a block's predecessor may not be settled when the block is visited.
Cooper-Harvey-Kennedy iterates over reverse post-order, skipping unsettled predecessors, until a full sweep changes nothing.
The final sweep that changes nothing is how the algorithm knows it is done; there is no cheaper termination test.
Dominance is the precondition for SSA well-formedness, hoisting, cross-block CSE and redundant-check elimination — everywhere "this already happened" is needed.

The relation

Block A dominates block B when every path from the entry to B passes through A. The entry dominates everything, trivially, since every path starts there. Every block dominates itself. A strictly dominates B if it dominates B and is not B.

The immediate dominator of B is the strict dominator of B that is closest to it — the last one you pass through on any path to B. Every block except the entry has exactly one, which is what makes the relation a tree, and that tree is [[dominator-tree]].

Read the relation as a guarantee about execution rather than as a graph property and it becomes useful immediately. If A dominates B, then at B you may assume everything A established: a value A defined is available, a check A performed has passed, memory A allocated exists. That is why dominance is the precondition on so many transformations — it is the compiler's formalisation of "this definitely already happened".

Dominance for if (c > 0) { print(1); } else { print(2); } print(3); — the idom map is verbatim engine output

b0entryentry
```
%1 = bool 1 > 0
branch %1 ? b1 : b2
```
Dominates everything. Every path starts here.
b1if.then
```
print 1
jump b3
```
Does not dominate b3: you can reach b3 through b2 instead.
b2if.else
```
print 2
jump b3
```
Also does not dominate b3, for the mirror-image reason.
b3if.join
```
print 3
ret
```
Its immediate dominator is b0, skipping both arms — because neither arm is on every path here.

Edges

b0→b1true
b0→b2false
b1→b3
b2→b3

Immediate dominator

b0idomb0(entry)
b1idomb0
b2idomb0
b3idomb0

Read it asEvery block's immediate dominator is b0. That is the shape of a diamond: the join is dominated by the block above the branch, not by either arm, because control can arrive from either side. A value defined in b1 and used in b3 therefore violates the dominance requirement — which is precisely the condition a phi node exists to repair.

Why it must iterate

simplifiedAtlasLang uses reverse post-order index as a stand-in for dominator-tree depth in intersect, which is the standard trick from the Cooper-Harvey-Kennedy paper and is correct because reverse post-order is a topological order on the dominator tree. Production compilers use Lengauer-Tarjan or the Semi-NCA variant instead, which are asymptotically better on very large functions and considerably harder to read. The results are identical; the algorithm shown is chosen so the lesson can display the code that produced the picture.

For an acyclic graph, dominance could be computed in one pass in topological order: by the time you reach a block, all its predecessors are settled. A loop breaks that. The header's predecessors include the latch, and the latch comes *after* the header in any traversal from the entry, so when you compute the header's dominator the latch's dominator is not yet known.

The iterative algorithm — Cooper, Harvey and Kennedy — handles this by starting with an incomplete answer and refining it. It processes blocks in reverse post-order, and for each block it intersects the current dominator estimates of its predecessors, *skipping any predecessor that does not have an estimate yet*. Then it repeats the whole sweep. If any block's answer changed during a sweep, another sweep is needed, because a change can propagate.

The intersection is the clever part and it is four lines. To intersect two blocks in the dominator tree — to find their nearest common ancestor — walk the deeper one up by immediate dominators until the two meet, using reverse post-order index as the depth proxy. That is the entire intersect function in the engine, and it is why the algorithm is twenty lines rather than the several hundred that Lengauer-Tarjan takes.

On AtlasLang's loop programs the sweep runs exactly twice: once to compute the answer and once to confirm nothing changed. The second sweep is not wasted — it is how the algorithm knows it is finished. There is no cheaper termination test than doing the work again and observing that it produced the same result.

The Cooper-Harvey-Kennedy loop, as `computeDominance()` implements it

1let changed = true
2while (changed) {
3  changed = false
4  for (const id of rpo) {                      // reverse post-order
5    if (id === fn.entry) continue
6    const preds = block(id).preds
7      .filter((p) => idom[p] !== undefined)     // skip not-yet-computed preds
8    if (!preds.length) continue
9    let newIdom = preds[0]
10    for (const p of preds.slice(1))
11      newIdom = intersect(p, newIdom)           // nearest common ancestor
12    if (idom[id] !== newIdom) {
13      idom[id] = newIdom
14      changed = true
15    }
16  }
17}

The filter is what makes the first sweep possible at all: on the first visit to a loop header, the latch has no estimate, so it is ignored and the header is dominated by the entry path alone. On the second sweep the latch does have one, and the intersection is recomputed with it. That is the fixed point, and it is the same shape as every other analysis in [[fixed-point-iteration]].

The loop case, worked

Take the while graph: b0 (entry) -> b1 (condition) -> b2 (body) -> back to b1, with b1 -> b3 (exit). Reverse post-order is b0, b1, b3, b2.

First sweep. b1 has predecessors b0 and b2; b2 has no estimate yet, so it is skipped, and b1's dominator is b0. b3 has one predecessor, b1, so its dominator is b1. b2 has one predecessor, b1, so its dominator is b1. Something changed on this sweep, so another is required.

Second sweep. b1 now has an estimate for b2, so it intersects b0 and b2: walking up from b2 gives b1, then b0, meeting b0. So b1's dominator stays b0. Nothing changed anywhere. Done.

The result — {b0: b0, b1: b0, b2: b1, b3: b1} — is what the engine returns. And now the loop test works: b1 dominates b2, so the edge b2 -> b1 is a back edge, so there is a natural loop with header b1. Dominance had to come first, and it had to iterate to get there.

The while graph with its computed immediate dominators

b0entryentry
```
store @n, 0
jump b1
```
b1while.cond↺ loop header
```
%1 = bool %0 < 3
branch %1 ? b2 : b3
```
idom is b0. Not b2, even though b2 is a predecessor — because the entry path reaches b1 without going through b2.
b2while.bodylatch
```
...
jump b1
```
idom is b1. Everything that reaches the body came through the condition.
b3while.exit
```
print %7
ret
```
idom is b1 as well — the only way out of the loop is through the condition.

Edges

b0→b1
b1→b2true
b1→b3false
b2→b1back edge

Immediate dominator

b0idomb0(entry)
b1idomb0
b2idomb1
b3idomb1

Read it asBoth b2 and b3 are dominated by b1, which is what makes b1 a loop header rather than an ordinary block: it is the single gateway to everything inside the loop and to the exit. That property is exactly what [[natural-loops]] tests for.

What dominance guards

Dominance is the precondition on a surprising number of transformations, and in each case it is standing in for "this definitely already happened".

A value may only be used where its definition dominates the use — that is the SSA well-formedness rule, and it is what [[ir-verification]] checks. Code may only be hoisted to a block that dominates every use of what it computes, which is the condition on [[loop-invariant-code-motion]]. A redundant computation may be eliminated in favour of an earlier one only if the earlier one dominates it, which is what makes [[common-subexpression-elimination]] sound across blocks rather than only within one. A null check may be elided if a dominating check already established the fact.

The negative form is just as important. Where dominance *fails* is where a definition stops being guaranteed, and that boundary is the dominance frontier — which is where phi nodes go. [[dominance-frontier]] is that lesson, and it is the payoff for all of this machinery.

How it works

The steps, in the order the compiler takes them.

Compute reverse post-order over the CFG by depth-first search from the entry.
Initialise the entry's immediate dominator to itself and leave every other block unset.
Sweep blocks in reverse post-order. For each, take its predecessors that already have an estimate and intersect them pairwise.
Intersect two blocks by walking each up its immediate-dominator chain, always advancing the one with the larger reverse post-order index, until they meet.
Record the result if it differs from the current estimate, and note that something changed.
Repeat the sweep until a full pass changes nothing.
Build the dominator tree by giving each block its immediate dominator as parent, and derive the dominance frontier from the same information.

How it breaks

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

An unreachable block reaches the computation, has no dominator, and every analysis that consults dominance for it or anything below it gets a meaningless answer — usually surfacing as a crash in a much later pass.
Predecessor lists are stale, so dominance is computed over a graph that does not match the code. A hoist is then performed to a block that does not actually dominate the uses, and a value is read before it is written on one path.
Dominator information is cached and not invalidated after a transformation changes the graph. The next pass gets a correct answer about a graph that no longer exists, and does something subtly wrong with it.
The iteration is stopped after one sweep as an optimization, and a loop header keeps a dominator computed while its latch was unknown. The error is small, local, and produces wrong loop detection.
Reverse post-order is computed from the wrong root, or recomputed inconsistently between sweeps, and the intersect walk fails to terminate — an infinite loop inside the compiler.

When it helps

Establishing that any transformation is safe. "Does A dominate B" is the standard formal version of "has A definitely run by the time we get to B", and that question appears in nearly every legality condition in the middle-end.
Building SSA. Both phi placement and renaming are stated over the dominator tree, so nothing in [[ssa-construction]] is possible without this.
Finding loops, which needs the dominance test to distinguish a back edge from an ordinary edge into a cycle.

When it hurts

On very large functions, where recomputing dominance after each of many transformations is a measurable fraction of compile time — which is why production compilers maintain incrementally updatable dominator trees despite the complexity.
When dominance is used as a proxy for "always executes". A block that dominates another still may not execute if the function returns early, throws, or diverges before reaching it. Dominance is conditional on reaching B, not unconditional.

What it costs

Every one of these is paid by something.

The iterative algorithm buys legibility and a small constant factor and pays asymptotically on very large graphs, where Lengauer-Tarjan is faster — a tradeoff Cooper, Harvey and Kennedy measured and argued was usually worth taking.
Caching dominance buys every consumer a cheap query and pays a real invalidation obligation on every transformation that changes the graph, where the cost of forgetting is a wrong answer rather than a slow one.
Storing only immediate dominators buys a compact representation and pays a walk up the chain for each "does A dominate B" query, rather than the constant-time answer a precomputed matrix would give at quadratic space.

What else you could do

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

Lengauer-Tarjan computes dominators in near-linear time and is what most production compilers use; it is substantially harder to read and to modify, which is the whole reason AtlasLang uses the iterative version.
Semi-NCA, a simpler variant of Lengauer-Tarjan used in LLVM, which trades a little asymptotic performance for a much more maintainable implementation and supports incremental updates.
A dominance matrix — a bit per block pair — giving constant-time queries at quadratic space. Reasonable for small functions, hopeless for large ones.
Do not compute dominance at all, and restrict optimizations to block-local ones. This is what a fast development-build compiler may reasonably do, and it forgoes SSA entirely.

See it for yourself

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

opt -passes='print<domtree>' file.ll prints LLVM's dominator tree for each function, with each node's children listed under it.
opt -passes=dot-dom file.ll writes a Graphviz dominator tree per function, which is the fastest way to see the tree next to the CFG.
gcc -fdump-tree-all includes dominance-based pass dumps; the .dom variants show the tree the passes worked from.
Our dominator-tree viewer at /compilers/dominators shows the CFG and the tree side by side for whatever you type, using computeDominance() output directly.
To see the iteration itself, instrument the while (changed) loop in src/compilers/sim/ir.ts with a pass counter and run any loop program — it reports two sweeps for AtlasLang's reducible loops.

Plausible wrong readings

Stated the way a confident engineer states them.

"A dominates B means A runs before B." It means that *if* B runs, A already ran. A may dominate B and neither may run at all, if the function returns first.
"The immediate dominator is the predecessor." Only when there is exactly one predecessor. A join block's immediate dominator is usually a block above the branch, several steps up the graph — as b3's is b0 in the diamond above.
"Dominance can be computed in one pass." Only for acyclic graphs. A back edge means a predecessor is unsettled when its successor is visited, and the algorithm has to come back.
"If A dominates B, everything A computed is available at B." Only if nothing between them redefined or invalidated it. Dominance establishes that A executed, not that its results survived.

Misconceptions

The claim, and what is actually true.

Dominance is about the order blocks appear in the listing.

It is about paths in the graph. Block ordering in a printed function is a convention, and permuting it changes no dominance relation whatsoever.

The entry dominating everything is a special case in the algorithm.

It falls out of the definition — every path from the entry begins at the entry — and appears in the code only as the initialisation idom[entry] = entry.

Post-dominance is the same thing backwards, so it is redundant.

It is the same relation on the reverse graph and answers a genuinely different question: "if A runs, will B definitely run afterwards". It is what sinking transformations and some dead-code arguments need, and it requires a unique exit block to be well defined.

Go deeper

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

overview

One block dominates another if there is no way to reach the second without passing through the first. That gives the compiler a formal version of "this definitely already happened", which is the precondition for moving code, reusing a computed value, or eliding a check that was already made. Because loops make the graph circular, working it out takes repeated passes rather than one.

practical

When a transformation refuses to fire and you cannot see why, dominance is a good first suspect. Common subexpression elimination will not reuse a value across blocks unless the defining block dominates the using one, and a value computed in one arm of a branch does not dominate anything in the other arm. Printing the dominator tree with opt -passes='print<domtree>' next to the CFG usually answers the question in one look.

advanced

Dominance is a dataflow problem in disguise, and seeing it that way is worth the effort. The fact at each block is "the set of blocks that dominate me", the transfer function is "add myself", and the meet operator is set intersection over predecessors — a forward analysis over a lattice, exactly like every analysis in [[data-flow-framework]]. Cooper, Harvey and Kennedy's contribution was noticing that the sets are always paths up a tree, so the whole set can be represented by one pointer and the intersection becomes a nearest-common-ancestor walk. That representation change turned a quadratic-space analysis into a twenty-line one, and it is a good example of a general principle: the algorithmic win came from finding a better encoding of the answer, not a better search.

How much this depends on

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

implementationLLVM uses Semi-NCA with incremental update support; GCC uses a Lengauer-Tarjan variant; AtlasLang uses the Cooper-Harvey-Kennedy iterative algorithm for legibility. All three compute the same relation. The choice matters for compile time on large functions and for whether the structure can be updated in place after a transformation rather than rebuilt.

typicalThe two-sweep behaviour described here holds for reducible graphs processed in reverse post-order, which covers essentially all code produced by structured control flow. Irreducible graphs can require more sweeps, since a cycle with two entries has no traversal order that settles every predecessor before its successors.

If you were asked this in an interview

Define dominance, then tell me why the join block of an if/else is not dominated by either arm.
Why can dominance not be computed in a single traversal?
What does the intersect step in the iterative algorithm actually compute, and why is reverse post-order index a valid depth proxy?

Connections

DSAdirected-graph dfs n-ary-tree adjacency-list

Domains that do not exist yet

Programming Languages & Runtime Internals — Deoptimization state validity at a given program point
A JIT can only deoptimize at a point where the values it needs to reconstruct the interpreter frame are available, and "available here" is a dominance question over the compiled graph — the runtime half of the same relation.