Dominator Tree: Finding Which Blocks Must Execute Before Each Node

The Problem: Which Blocks Are Guaranteed to Run First

A control-flow graph (CFG) models a function as basic blocks (nodes) connected by branch edges. Many optimizations need a precise answer to a guarantee question: if control reaches block n, which other blocks must it have already executed? A definition is safe to reuse at n only if the block computing it is guaranteed to run first; hoisting an instruction out of a loop is safe only into a block that guarantees the loop body still runs.

The dominance relation formalizes this. Node d dominates n (written d dom n) if every path from the entry to n passes through d. Every node dominates itself; the entry dominates everything. Dominance is a partial order, and — crucially — it forms a tree: every node except the entry has exactly one immediate dominator, its closest strict dominator. Linking each node to its idom gives the dominator tree, where the ancestors of n are exactly the blocks guaranteed to execute before it.

• Post-dominators answer the mirror question (what must run after n) by running the same algorithm on the reverse CFG.

How It Works: From Data-Flow to Lengauer-Tarjan

The textbook definition gives a direct iterative data-flow algorithm. Let Dom(entry) = {entry} and for every other node initialize Dom(n) to all nodes. Then repeat until nothing changes:

Dom(n) = {n} ∪ ( ∩ over preds p of n:  Dom(p) )

A node's dominators are itself plus everything that dominates all of its predecessors. This converges to the least fixed point; visiting in reverse-postorder speeds convergence.

Representing Dom as full bit-vectors is O(n^2) space. Cooper-Harvey-Kennedy (2001) instead stores only idom and "intersects" two nodes by walking up the partial dominator tree using postorder numbers until they meet — simple and fast in practice.

The classic Lengauer-Tarjan algorithm (1979) is asymptotically faster. It does a DFS to number nodes, computes each node's semidominator (the smallest-numbered node reachable via a path through higher-numbered nodes), and derives idom from semidominators using a link-eval forest with path compression, hitting O(m·α(m,n)).

Complexity and a Worked Trace

For a CFG with n nodes and m edges: the iterative method is O(n) rounds × O(m) work = O(n·m) worst case but usually converges in a couple of passes. Cooper-Harvey-Kennedy is O(n^2) worst case yet often the fastest choice on real functions. Lengauer-Tarjan runs in O(m·α(m,n)) — effectively linear, since the inverse-Ackermann α never exceeds 4 for any input that fits in the universe. The tree itself is O(n) space.

Consider this CFG (entry = A): edges A→B, A→C, B→D, C→D, D→E, D→F, E→G, F→G, G→D (a loop back-edge).

idom(A) = —        (root)
idom(B) = A
idom(C) = A
idom(D) = A   (D reachable via B and via C, so their common dominator is A)
idom(E) = D
idom(F) = D
idom(G) = D   (G reachable via E and via F; common dom is D)

D does not dominate itself's predecessors uniquely — B and C both reach D, so neither dominates it; only A does. The back-edge G→D confirms D dominates G, marking a natural loop with header D.

Where It's Used in Real Systems

The dominator tree is one of the most heavily used structures in production compilers:

• SSA construction: Cytron et al.'s algorithm places φ-functions at the dominance frontier of each definition — the frontier is computed directly from the dominator tree. LLVM, GCC, V8's TurboFan, and HotSpot's C2 all rely on it.
• Loop detection: a back-edge t→h where h dominates t identifies a natural loop with header h, driving loop-invariant code motion, unrolling, and vectorization.
• Redundancy elimination & code motion: global value numbering and GVN-PRE use dominance to know a value is available; a computation can be hoisted only to a dominating block.
• Security & analysis: guard/bounds-check elimination proves a check dominates its uses.
• Memory profiling: Chrome DevTools and Java heap analyzers use the dominator tree of the object graph to compute retained size — how much memory frees if an object is collected.

Dominator Tree vs. Its Cousins

Several related structures answer neighboring questions, and picking the wrong one silently breaks optimizations:

• Dominator sets vs. dominator tree: the full Dom(n) sets are O(n^2) bits; the tree encodes the same information in O(n) space because ancestors-in-tree = dominators. Always prefer the tree unless you need explicit set membership.
• Post-dominator tree: same algorithm on the reversed CFG with a virtual exit; answers "must run after." Combining dominators and post-dominators yields control dependence and the program-dependence graph.
• Dominance frontier: not the tree itself but derived from it — the set of nodes where a definition's dominance ends; the trigger for φ-placement in SSA.
• Loop nesting forest: built from back-edges identified via dominance, but a distinct structure.

The tradeoff between the algorithms is engineering, not asymptotics: Cooper-Harvey-Kennedy is ~2× simpler code and frequently faster on the small, sparse CFGs typical of real functions, while Lengauer-Tarjan wins on huge or adversarial graphs.

Pitfalls, Failure Modes, and Significance

Dominator computation is subtle enough that several classic bugs recur:

• Unreachable code: the algorithms assume every node is reachable from entry. Blocks with no path from entry have undefined dominators; you must prune unreachable blocks (or treat their idom as ⊥) before or during the pass, or intersection over an empty predecessor set corrupts results.
• Irreducible CFGs: graphs with multiple loop entries (from goto, some exception handlers, or optimized tail-merged code) are still handled correctly by dominance — the tree is always well-defined — but downstream loop analyses that assume reducibility can misfire.
• Incremental updates: after inlining or block splitting, recomputing from scratch is O(m); dynamic dominator maintenance (Sreedhar-Gao-Lee, or LLVM's DominatorTree updater) is fiddly and a frequent source of stale-tree miscompiles.
• Multiple predecessors of the entry / infinite loops: post-dominance needs a single virtual exit or infinite loops leave nodes with no post-dominator.

Its significance is hard to overstate: dominance is the backbone that makes SSA — and therefore nearly all modern optimization — tractable, turning a global "what always happens first?" question into a single tree lookup.

Algorithms for computing the dominator tree

Algorithm	Year	Time complexity	Notes
Iterative data-flow (Allen-Cocke)	1970	O(n^2 · m) worst, fast in practice	Simple, computes full dominator sets; slow on pathological graphs
Cooper-Harvey-Kennedy	2001	O(n^2) worst, near-linear typical	Engineering-simple, often beats LT on real CFGs; computes idom directly
Lengauer-Tarjan (simple)	1979	O(m · log n)	Path compression only
Lengauer-Tarjan (sophisticated)	1979	O(m · α(m,n))	Balanced link-eval; α ≤ 4 in practice
Buchsbaum et al. / Georgiadis-Tarjan	2004-08	O(m + n) linear	Truly linear-time, complex; mostly of theoretical interest