CFGtypical

The Dominator Tree

Every block has exactly one immediate dominator, so the relation is a tree — and it is a different tree from the CFG, drawn on the same nodes. Draw it separately, because the edges mean something the CFG edges do not, and half the confusion about dominance comes from overlaying them.

The question

What does the dominator tree look like, how is it different from the CFG, and what walks it?

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

What the program is here

A rooted tree over the same set of blocks as the CFG, in which each block's parent is its immediate dominator and the root is the entry. It exists to answer dominance queries structurally: A dominates B exactly when A is an ancestor of B in this tree. Every "did this definitely already happen" question becomes an ancestor test, and every algorithm that needs to process a block after everything guaranteed before it becomes a pre-order walk.

What this phase may assume or do

The structure is a tree because every block except the entry has exactly one immediate dominator, which holds only when every block is reachable from the entry. An unreachable block has no dominator and no parent, so it is not in the tree at all — which is why reachability pruning is a precondition and not a tidiness measure. It is also only valid for the graph it was computed from: any transformation changing an edge invalidates it, and a stale tree answers correctly about a graph that no longer exists.

Key points

Each block's parent is its immediate dominator, so the relation forms a tree rooted at the entry.
A dominates B exactly when A is an ancestor of B in the tree, so dominance queries become ancestor tests.
The tree is a different shape from the CFG on the same nodes — the join of a diamond is a sibling of the arms, not a child.
The tree is acyclic even when the CFG is cyclic, because a back edge points at an ancestor and contributes no parent edge.
A pre-order walk of the tree with a push/pop stack gives exactly the definitions visible at each block, which is how SSA renaming and scoped value numbering work.
Building the tree is cheap; keeping it valid across transformations is where the compile time and the subtle bugs are.

Two graphs on the same nodes

The CFG and the dominator tree share every node and share almost no edges. A CFG edge means "control can pass from here to there". A dominator-tree edge means "this is the nearest block guaranteed to have run before that one". Those are different claims, and the shapes diverge immediately.

Take the diamond. In the CFG, b3 has two incoming edges, from b1 and from b2. In the dominator tree, b3's parent is b0, and b1, b2 and b3 are all siblings under it. The tree edge from b0 to b3 corresponds to no CFG edge at all — they are not adjacent in the CFG, and that is exactly the information the tree is carrying.

This is why the tree should be drawn separately rather than overlaid. Overlaying produces a picture in which the reader cannot tell which edges mean which thing, and the single most common misunderstanding about dominance — that a block is dominated by its predecessor — is precisely what an overlaid picture encourages.

The dominator tree for the diamond, drawn as a tree — parent edges only

b0entry — tree rootentry
```
dominates b1, b2, b3
```
The root. Every block hangs below it, directly in this case.
b1if.then
```
dominates nothing else
```
A leaf. It dominates itself and no other block, because b3 is reachable without it.
b2if.else
```
dominates nothing else
```
Also a leaf, for the mirror reason.
b3if.join
```
dominates nothing else
```
A sibling of the two arms, not a child of either. The tree edge b0 -> b3 has no counterpart in the CFG.

Edges

b0→b1idom
b0→b2idom
b0→b3idom

Immediate dominator

b0idomb0(entry)
b1idomb0
b2idomb0
b3idomb0

Read it asCompare this with the CFG for the same program in [[dominators]]: there, b3 is below b1 and b2. Here it is beside them. The engine's domTree for this function is {b0: [b1, b2, b3], b1: [], b2: [], b3: []} — one root with three children.

The loop tree, and what it says

For the while graph, the tree is a chain that then forks: b0 -> b1 -> {b2, b3}. The engine returns domTree = {b0: [b1], b1: [b2, b3], b2: [], b3: []}.

Read the fork: the loop header b1 is the parent of both the body and the exit. That is a precise statement of what a loop header *is* — the single gateway through which everything inside the loop and everything leaving it must pass. The back edge from b2 to b1 does not appear in the tree at all, because a back edge never contributes a parent relation; the target of a back edge is an ancestor of its source, and an ancestor is already above it.

The absence of back edges is worth stating plainly: the dominator tree is acyclic even when the CFG is not. That is the property that makes it useful as a traversal order. Anything that has to process each block after everything guaranteed before it can walk the tree in pre-order and never worry about loops.

The dominator tree of the while graph — verbatim domTree output

b0entry — tree rootentry
```
child: b1
```
b1while.cond — loop header
```
children: b2, b3
```
Parent of both the loop body and the loop exit. Nothing enters or leaves the loop without passing through here.
b2while.body
```
leaf
```
Its back edge to b1 is invisible here — b1 is already its ancestor.
b3while.exit
```
leaf
```

Edges

b0→b1idom
b1→b2idom
b1→b3idom

Immediate dominator

b0idomb0(entry)
b1idomb0
b2idomb1
b3idomb1

Read it asThe tree is acyclic even though the CFG has a cycle, because the back edge points to an ancestor and ancestors do not get parent edges. That is what makes the tree usable as a recursion order — a walk over it terminates, and a walk over the CFG would not.

What walks the tree

The SSA renaming pass is the canonical consumer. It walks the dominator tree in pre-order, maintaining a stack of the current definition for each variable: on entering a block it pushes each new definition, rewrites uses to the top of the stack, recurses into the tree children, and on the way out pops everything it pushed. The stack discipline is correct precisely because the tree is the dominance relation — the definitions visible at a block are exactly those made by its ancestors, which are exactly the ones on the stack. [[ssa-construction]] is that algorithm, and AtlasLang's rename() function is it, verbatim.

Global value numbering and cross-block CSE use the tree the same way: a computation available at a block is one made by an ancestor, so a scoped hash table pushed and popped along the tree walk gives exactly the right visibility. Trying to do this over the CFG requires a dataflow analysis; over the tree it is a stack.

And [[loop-invariant-code-motion]] uses it to check that a hoist target dominates every use, which is an ancestor query. Represented as a tree with pre-order and post-order numbers, that query is two integer comparisons rather than a walk.

CFG edge versus dominator-tree edgetypical

Property	CFG	Dominator tree
What an edge means	Control can transfer from here to there	This is the nearest block guaranteed to run before that one
In-degree	Any number — merges have several predecessors	Exactly one, except the root
Cycles	Yes, whenever there is a loop	Never — back edges point at ancestors
Join block of a diamond	A child of both arms	A sibling of both arms, child of the block above the branch
Typical use	Reachability, dataflow, loop detection	SSA renaming, scoped value numbering, ancestor queries

Maintaining it is the expensive part

implementationLLVM's pass manager tracks analysis preservation explicitly: a pass declares which analyses it preserves, and the manager invalidates the rest. A pass that wrongly claims to preserve the dominator tree produces a stale-analysis bug that no verifier catches, because the tree is internally consistent — it is just about a different graph. GCC and Go handle invalidation with different mechanisms and the same failure mode. This is one of the few places where the bug class is a property of the infrastructure rather than of any algorithm.

Computing the tree is a byproduct of computing dominance: each block's parent is its immediate dominator, and the whole construction is one loop. The cost is not in building it — it is in keeping it.

Every transformation that changes an edge potentially changes the tree. Splitting a critical edge inserts a node. Deleting an unreachable block removes a subtree. Merging two blocks changes a parent. Naively, each of those means recomputing dominance for the whole function, and in a pipeline of a hundred and fifty passes that adds up to a significant fraction of compile time.

Production compilers therefore maintain the tree incrementally, updating it in place for local changes and recomputing only when a transformation has changed too much. LLVM has a DominatorTree with an update API and a pass-manager mechanism for declaring whether a pass preserved it. The bugs in that machinery are notoriously subtle: a pass that says it preserved the tree and did not causes a later pass to reason about a graph that no longer exists, and nothing detects it until the output is wrong.

How it works

The steps, in the order the compiler takes them.

Compute the immediate dominator of every block.
For each block other than the entry, add it as a child of its immediate dominator.
The entry is the root, and the tree contains exactly the blocks reachable from it.
Assign pre-order and post-order numbers by one depth-first walk, so that ancestor queries become two integer comparisons.
Invalidate or update the tree after any transformation that changes an edge, and be explicit about which of the two a given pass does.

How it breaks

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

The tree is overlaid on the CFG in a diagram or a mental model, and a reader concludes that a block is dominated by its predecessor. Every subsequent reasoning step about phi placement is then wrong.
A pass claims to preserve the dominator tree and does not. A later pass hoists to a block that no longer dominates its uses, and a value is read before it is written on one path — with no verifier failure, because the tree is internally consistent.
An unreachable block reaches the construction, has no parent, and is silently absent from the tree. Any pass iterating the tree instead of the block list skips it, and a transformation that should have deleted it never runs.
Ancestor queries are answered by walking the parent chain in a hot loop, and compile time on deep functions degrades quadratically — the symptom is a compiler that is fine on normal code and unusable on generated code.

When it helps

SSA construction and renaming, which are stated entirely over the tree and become a simple stack discipline because of it.
Any scoped analysis where "visible here" means "established by something guaranteed to have run" — value numbering, available expressions, redundant check elimination.
Fast dominance queries. With pre-order and post-order numbers, "does A dominate B" is two comparisons, which matters because the query appears inside the inner loops of many passes.

When it hurts

When the question is about paths rather than about guarantees. The tree cannot tell you whether two blocks are on the same path, only whether one is guaranteed before the other — for path questions you need the CFG.
In pipelines with many graph-changing transformations, where maintenance cost and invalidation correctness become the dominant concerns rather than the algorithm itself.

What it costs

Every one of these is paid by something.

The tree buys constant-time dominance queries and a valid recursion order, and pays with a second structure that must be invalidated or updated by every transformation that touches an edge.
Incremental maintenance buys compile time and pays with a class of stale-analysis bug that no verifier catches, because a stale tree is internally consistent and merely describes the wrong graph.
Pre-order and post-order numbering buys two-comparison ancestor tests and pays with renumbering on every structural change, which makes incremental update harder than it first appears.

What else you could do

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

Answer dominance queries by walking the immediate-dominator chain with no tree materialised, which is what AtlasLang's dominates() does. Simple and correct, and linear per query rather than constant.
A dominance bit matrix, giving constant-time queries with no numbering to maintain, at quadratic space — fine for small functions and hopeless for large ones.
A dominator forest that also records the dominance frontier and loop nesting in one structure, which some compilers build together since all three come from the same computation.
Do not build one: a compiler doing only block-local optimization needs neither the tree nor SSA, which is a reasonable design for a fast development-build compiler.

See it for yourself

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

opt -passes='print<domtree>' file.ll prints the tree with each node's children indented beneath it.
opt -passes=dot-dom file.ll writes a Graphviz dominator tree; render it next to -passes=dot-cfg output for the same function and the difference in shape is immediate.
opt -passes='print<postdomtree>' file.ll prints the post-dominator tree, which answers the mirror question — "if A runs, will B definitely run afterwards".
Our dominator-tree viewer at /compilers/dominators draws the CFG and the tree side by side for whatever you type, with the tree built from the engine's domTree output.

Plausible wrong readings

Stated the way a confident engineer states them.

"The dominator tree is a spanning tree of the CFG." It is not. Its edges frequently connect blocks that have no CFG edge between them — the join of a diamond is a child of the block above the branch, which is two CFG steps away.
"A block's parent in the tree is its predecessor." Only when it has exactly one predecessor. Merge points have parents further up.
"The tree has cycles if the CFG does." It never has cycles. A back edge targets an ancestor, and ancestors do not become children.
"If I have the tree I do not need the CFG." The tree answers guarantee questions. Path questions, reachability and loop detection all need the graph.

Misconceptions

The claim, and what is actually true.

The dominator tree and the CFG should be drawn on the same picture.

Drawing them together is the main source of confusion about dominance, because the two edge types mean incompatible things and a reader cannot tell them apart. Draw them side by side on the same node set instead.

Depth in the dominator tree tells you loop nesting depth.

They are different measures. A deeply nested if chain produces a deep dominator tree with no loops in it at all. Loop depth comes from loop analysis, not from tree depth.

The post-dominator tree is redundant.

It answers the mirror question and is what sinking transformations and some control-dependence analyses need. It also requires a unique exit block to be well defined, which the dominator tree does not.

Go deeper

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

overview

Because every block has exactly one nearest block that is guaranteed to run before it, the dominance relation forms a tree. It is drawn on the same blocks as the control-flow graph but has different edges: the point where two branches rejoin is a sibling of the two arms, not a child of either. Keeping the two pictures separate is most of understanding dominance.

practical

When debugging a pass that reasons about dominance, print the tree with opt -passes='print<domtree>' and the CFG with -passes=dot-cfg, and look at both. Most confusion resolves the moment you can see that a join block's tree parent is above the branch rather than in an arm. If a pass is producing wrong code and the tree looks right, suspect staleness next: a pass earlier in the pipeline may have claimed to preserve an analysis it invalidated.

advanced

The reason the tree is the natural recursion order for SSA renaming is worth stating precisely, because it is the crux of the whole construction. At a block B, the definitions that could possibly be visible are exactly those made in blocks that dominate B — anything else is not guaranteed to have run. Those blocks are exactly B's ancestors in the tree. So a depth-first walk maintaining a per-variable stack, pushing on entry and popping on exit, has on the stack precisely the set of definitions visible at every point. No dataflow analysis is required, no fixed point, no iteration: the tree structure *is* the answer, and the algorithm is a walk. That is why building the dominator tree is the price of admission for SSA, and why the two lessons are adjacent.

How much this depends on

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

typicalEvery SSA-based compiler builds this tree, and the construction is identical everywhere because the relation is mathematical. What differs is whether it is stored with pre/post-order numbering for constant-time queries, whether it supports incremental update, and how invalidation is tracked — all of which are infrastructure decisions with real consequences for compile time.

simplifiedAtlasLang materialises domTree as a children map and answers dominance queries by walking the immediate-dominator chain in dominates(), with no numbering. That is correct and linear per query; a production implementation numbers the tree so that the same query in a pass inner loop is two integer comparisons.

If you were asked this in an interview

Draw the CFG and the dominator tree for an if/else with a join, and explain why they differ.
Why is the dominator tree acyclic even when the CFG contains a loop?
Why is a pre-order walk of the dominator tree the right traversal for SSA renaming?

Connections

DSAn-ary-tree dfs directed-graph binary-tree

Domains that do not exist yet

Software Design — Choosing a data structure whose shape makes the invariant free
The dominator tree turns a dataflow problem into a stack discipline purely by re-encoding the same information. That is a design move rather than an algorithmic one, and the general principle belongs there.