Lesson 15.1 — Dominator algorithms¶

Techniques: iterative dataflow with bit vectors, Cooper–Harvey–Kennedy (CHK), Lengauer–Tarjan (simple and sophisticated linking), Semi-NCA · Pebble implements: all four; CHK is the one the Pebble analyses use, the others are in the comparison lab (balanced linking and Semi-NCA are ★) · Lab: CHK vs Lengauer–Tarjan vs Semi-NCA vs LLVM · Prerequisites: Ch 8 (CFGs, DFS orders), Ch 14 (monotone frameworks, iteration in RPO) · Time: 6–8 hours

Look at this CFG, the running example of the whole chapter. Block B heads an outer loop, E heads an inner loop, and H is where the two loop bodies join before the latch back to B.

flowchart TD
  A([A]) --> B[B]
  B --> C[C]
  B --> E[E]
  C --> D[D]
  C --> H[H]
  D --> E
  E --> F[F]
  E --> H
  F --> G[G]
  G --> H
  G --> E
  H --> I[I]
  H --> B

Every path from A to H passes through B, but not through C (take B → E → H) and not through E (take B → C → H). So B is the closest block that must have run before H. That fact is what SSA construction needs to know where a definition reaches (Ch 16), what LICM needs to know that hoisting is safe (Ch 18), and what loop detection needs to recognize the back edge H → B. This lesson computes it four ways.

1. Problem and motivation¶

Given a flowgraph, compute for every block \(n\) its immediate dominator \(\mathrm{idom}(n)\): the last block that every path from the entry to \(n\) must pass through. The answer is a tree, the dominator tree, and almost every analysis after this chapter walks it. In LLVM, DominatorTree is the most requested analysis of all; pebblec computes it for every function before SSA construction, and recomputes or updates it after every transformation that changes the CFG.

The notion comes from Prosser's 1959 work on Boolean connectivity matrices of flow diagrams [Pro59]. The first optimizing compilers needed it to find loops and move code out of them: the FORTRAN H compiler computed "predominators" by iterating set equations [LM69], and Allen and Cocke gave the set-based formulation still taught today [AC72]. Those algorithms are quadratic or worse. Lengauer and Tarjan showed in 1979 that dominators can be found in almost linear time through semidominators [LT79]. Their algorithm is fast but hard to get right, so for twenty years compilers kept iterating. In 2001 Cooper, Harvey and Kennedy showed that the iterative algorithm, with the right data structure, is simpler than Lengauer–Tarjan and faster on real CFGs [CHK01]. Georgiadis then combined the semidominators of Lengauer–Tarjan with a simple nearest-common-ancestor step: Semi-NCA, which is what LLVM uses today [Geo05, GTW06].

Iterative dataflow¶

Dominance is a forward dataflow problem (Ch 14): the set of dominators of a block is the block itself plus whatever dominates all of its predecessors (Theorem 15.1.8). Allen and Cocke solved the equations by round-robin iteration over bit vectors [AC72], following the FORTRAN H approach [LM69]. It is the baseline every other algorithm is measured against, and it is still what you write when you need dominators for ten blocks, or when you want an obviously correct oracle.

Cooper–Harvey–Kennedy¶

The iterative algorithm wastes space and time on sets: \(n\) bit vectors of \(n\) bits. CHK observe that at every point of the iteration each set is a path in a tree, so a single array doms[] of tree parents represents all of them, and intersecting two sets is a walk towards the root [CHK01]. The result is the same fixed point computed with \(O(n)\) space and short, cache-friendly loops. Pebble's analyses use CHK (your computeIdoms(G, D, DomAlgorithm::CHK), exercise E3) because it is short enough to get right and fast on the CFGs a front end produces.

Lengauer–Tarjan¶

Iteration needs several passes on irreducible graphs and each pass may walk long tree paths. Lengauer and Tarjan instead compute, in one sweep over a depth-first spanning tree, the semidominator of every node: a cheap-to-compute stand-in for the dominator that sits on the tree path above it. A second, linear pass turns semidominators into immediate dominators [LT79]. With a union-find-like forest (EVAL/LINK) the whole algorithm runs in \(O(m \log n)\), or \(O(m\,\alpha(m, n))\) with balanced linking. GCC, Go and HotSpot use it.

Semi-NCA¶

Lengauer–Tarjan's second phase needs buckets and a deferred-fix-up pass. Georgiadis showed that once semidominators are known, \(\mathrm{idom}(w)\) is simply the nearest common ancestor of \(\mathrm{parent}(w)\) and \(\mathrm{sdom}(w)\) in the dominator tree built so far, if nodes are processed in DFS preorder [Geo05]. That NCA walk can be long in theory (\(O(n^2)\) worst case), but in measurements it is the fastest algorithm on real CFGs [GTW06]. It also works on a part of a tree, which makes it the natural engine for incremental updates (Lesson 15.2). LLVM, rustc and Cranelift use it.

2. Definitions and algorithms¶

Throughout, \(G = (N, E, r)\) is a flowgraph and \(n = \lvert N \rvert\), \(m = \lvert E \rvert\) (the chapter's Notation).

Definition 15.1.1 (Flowgraph, path, reachability)

A flowgraph \(G = (N, E, r)\) is a finite directed graph with a distinguished entry \(r \in N\) that has no predecessors. A path \(v_0 \to v_1 \to \dots \to v_k\) (\(k \ge 0\)) is a sequence of nodes with \((v_i, v_{i+1}) \in E\); it is simple if its nodes are pairwise distinct. A node \(n\) is reachable if some path \(r \leadsto n\) exists; \(N_r \subseteq N\) is the set of reachable nodes. Every path contains a simple path with the same endpoints whose nodes are a subset of its nodes (cut out the cycles).

Definition 15.1.2 (Dominance)

For \(d, n \in N_r\): \(d\) dominates \(n\), written \(d \mathrel{\mathrm{dom}} n\), if every path \(r \leadsto n\) contains \(d\); \(d\) strictly dominates \(n\), \(d \mathrel{\mathrm{sdom}} n\), if \(d \mathrel{\mathrm{dom}} n\) and \(d \neq n\). The dominator set is \(\mathrm{Dom}(n) \triangleq \{\, d \in N_r \mid d \mathrel{\mathrm{dom}} n \,\}\). Unreachable nodes have no dominators in any useful sense; we follow LLVM: they get no immediate dominator and no tree node, and the block-level query dominates(a, b) answers true when \(b\) is unreachable and false when only \(a\) is (section 7).

Dominance on the running example

\(\mathrm{Dom}(H) = \{A, B, H\}\): the paths \(A \to B \to C \to H\) and \(A \to B \to E \to H\) share only \(A\), \(B\) and \(H\). \(\mathrm{Dom}(G) = \{A, B, E, F, G\}\). And \(C \not\mathrel{\mathrm{dom}} H\) although \(C\) is a predecessor of \(H\).

Because "every path contains \(d\)" and "every simple path contains \(d\)" are equivalent (Definition 15.1.1), dominance only ever depends on simple paths. Two facts follow directly.

Theorem 15.1.3 (Dominance is a partial order)

On \(N_r\), \(\mathrel{\mathrm{dom}}\) is reflexive, antisymmetric and transitive.

Proof

Reflexive: every path \(r \leadsto n\) ends in \(n\). Transitive: let \(a \mathrel{\mathrm{dom}} b\) and \(b \mathrel{\mathrm{dom}} c\), and take any path \(P : r \leadsto c\). \(P\) contains \(b\); the prefix of \(P\) up to that occurrence of \(b\) is a path \(r \leadsto b\), so it contains \(a\), hence \(P\) contains \(a\). Antisymmetric: suppose \(a \mathrel{\mathrm{dom}} b\), \(b \mathrel{\mathrm{dom}} a\) and \(a \neq b\). Take a simple path \(P : r \leadsto a\) (it exists since \(a \in N_r\)). \(P\) contains \(b\) at some position before its last node \(a\). The prefix of \(P\) ending at \(b\) is a path \(r \leadsto b\) that does not contain \(a\), because \(P\) is simple and \(a\) occurs only at its end. This contradicts \(a \mathrel{\mathrm{dom}} b\).

Proposition 15.1.4 (Dominance by removal)

For \(d \neq r\) and \(n \in N_r\) with \(n \neq d\): \(d \mathrel{\mathrm{dom}} n\) iff \(n\) is unreachable from \(r\) in \(G - d\) (the graph with \(d\) and its edges deleted).

Proof

A path \(r \leadsto n\) in \(G - d\) is exactly a path \(r \leadsto n\) in \(G\) that avoids \(d\). So "no such path in \(G - d\)" is "every path in \(G\) contains \(d\)", which is Definition 15.1.2.

This is Purdom and Moore's algorithm [PM72] and the course's Python oracle dominators_by_removal: \(O(n \cdot m)\), trivially correct.

Definition 15.1.5 (Immediate dominator)

For \(n \in N_r \setminus \{r\}\), the immediate dominator \(\mathrm{idom}(n)\) is the strict dominator of \(n\) that every other strict dominator of \(n\) dominates.

Theorem 15.1.6 (Dominator tree)

For every \(n \in N_r \setminus \{r\}\): (a) the strict dominators of \(n\) form a chain \(r = d_1 \mathrel{\mathrm{sdom}} d_2 \mathrel{\mathrm{sdom}} \cdots \mathrel{\mathrm{sdom}} d_k\) with \(k \ge 1\); (b) hence \(\mathrm{idom}(n) = d_k\) exists and is unique; (c) \(\mathrm{Dom}(\mathrm{idom}(n)) = \mathrm{Dom}(n) \setminus \{n\}\); (d) the edges \(\mathrm{idom}(n) \to n\) form a tree \(\mathcal{D}\) rooted at \(r\) spanning \(N_r\), and the ancestors of \(n\) in \(\mathcal{D}\) (including \(n\)) are exactly \(\mathrm{Dom}(n)\).

Proof

(a) \(r\) strictly dominates \(n\) (every path starts at \(r\) and \(n \neq r\)), so the set \(S\) of strict dominators is non-empty. Take \(a \neq b\) in \(S\) and a simple path \(P : r \leadsto n\); both occur on \(P\), exactly once. Say \(b\) occurs after \(a\). If \(a\) did not dominate \(b\), some path \(Q : r \leadsto b\) avoids \(a\); \(Q\) followed by the part of \(P\) after \(b\) is a path \(r \leadsto n\), and that part of \(P\) does not contain \(a\) (it lies after \(b\), hence after \(a\), and \(P\) is simple). This path avoids \(a\), contradicting \(a \mathrel{\mathrm{dom}} n\). So any two elements of \(S\) are comparable, and by Theorem 15.1.3 \(S\) is totally ordered by \(\mathrel{\mathrm{dom}}\). (b) A finite chain has a unique largest element in that order, the \(d_k\) dominated by all others; it is \(\mathrm{idom}(n)\) by Definition 15.1.5, and two candidates would dominate each other, so they are equal by antisymmetry. (c) If \(d \mathrel{\mathrm{sdom}} n\), then \(d = d_k\) or \(d \mathrel{\mathrm{dom}} d_k\) by (a), so \(d \in \mathrm{Dom}(d_k)\). Conversely, if \(d \mathrel{\mathrm{dom}} d_k\) then \(d \mathrel{\mathrm{dom}} n\) by transitivity, and \(d \neq n\): otherwise \(n \mathrel{\mathrm{dom}} d_k\) and \(d_k \mathrel{\mathrm{dom}} n\) with \(d_k \neq n\), contradicting antisymmetry. (d) By (c), \(\lvert \mathrm{Dom}(\mathrm{idom}(n)) \rvert = \lvert \mathrm{Dom}(n) \rvert - 1\). Following \(\mathrm{idom}\) strictly decreases \(\lvert \mathrm{Dom} \rvert\), so it cannot cycle, and it can only stop at a node without an idom, which is \(r\) (\(\mathrm{Dom}(r) = \{r\}\), via the path consisting of \(r\) alone). So the parent map is a tree rooted at \(r\); by induction on \(\lvert \mathrm{Dom}(n) \rvert\) using (c), the ancestors of \(n\) are \(\{n\} \cup \mathrm{Dom}(\mathrm{idom}(n)) = \mathrm{Dom}(n)\).

Corollary 15.1.7 (Dominance queries on the tree)

Number the nodes of \(\mathcal{D}\) by one depth-first walk, giving each node an entry number \(\mathrm{in}(x)\) and an exit number \(\mathrm{out}(x)\) from one shared counter. Then \(a \mathrel{\mathrm{dom}} b \iff \mathrm{in}(a) \le \mathrm{in}(b) \land \mathrm{out}(b) \le \mathrm{out}(a)\), an \(O(1)\) test.

Proof

By Theorem 15.1.6(d), \(a \mathrel{\mathrm{dom}} b\) iff \(a\) is an ancestor of \(b\) in \(\mathcal{D}\). In a depth-first walk of a tree, \(b\) is entered and left while \(a\) is active exactly when \(b\) lies in \(a\)'s subtree, so the interval \([\mathrm{in}(b), \mathrm{out}(b)]\) nests inside \([\mathrm{in}(a), \mathrm{out}(a)]\) iff \(a\) is an ancestor-or-self of \(b\); intervals of unrelated nodes are disjoint.

This is how LLVM's DominatorTreeBase::dominates answers queries once its DFS numbers are valid (the {in,out} pairs printed by print<domtree>), and how the course's provided DomTree works (pebble/include/pebble/Analysis/DomTree.h).

Theorem 15.1.8 (Dataflow characterization)

\(\mathrm{Dom}\) is the greatest solution, under \(\subseteq\) pointwise, of

\[ \begin{aligned} X(r) &= \{r\}, \\ X(n) &= \{n\} \cup \bigcap_{p \in \mathrm{preds}(n) \cap N_r} X(p) \qquad (n \in N_r \setminus \{r\}). \end{aligned} \]

Proof

Every \(n \in N_r \setminus \{r\}\) has a reachable predecessor (the second-to-last node of a path \(r \leadsto n\)), so the intersection is over a non-empty family. \(\mathrm{Dom}\) is a solution. \(\mathrm{Dom}(r) = \{r\}\). For \(n \neq r\) and \(d \neq n\): if \(d \in \mathrm{Dom}(n)\) and \(p\) is a reachable predecessor, any path \(r \leadsto p\) extended by \(p \to n\) contains \(d\) at a position other than the last, so \(d \in \mathrm{Dom}(p)\). Conversely, if \(d\) dominates every reachable predecessor, every path \(r \leadsto n\) (length \(\ge 1\)) ends \(\dots \to p \to n\) with \(p\) reachable, and its prefix \(r \leadsto p\) contains \(d\). Every solution is below \(\mathrm{Dom}\). Let \(X\) be a solution and \(d \in X(n)\). We show every path \(P : r \leadsto n\) contains \(d\) by induction on the length of \(P\). Length 0: \(n = r\) and \(X(r) = \{r\}\), so \(d = r\). Length \(\ge 1\): \(P = P' \to n\) with \(P' : r \leadsto p\) and \(p\) a reachable predecessor. If \(d = n\) we are done; otherwise \(d \in X(p)\) by the equation, and \(P'\) contains \(d\) by the induction hypothesis.

Theorem 15.1.8 is the lattice view of Ch 14 with the dual orientation: dominator sets shrink from \(\top = N_r\), and the answer is the maximal fixed point.

Definition 15.1.9 (DFS numbering and spanning tree)

A depth-first search from \(r\) that tries successors in listed order (Lesson 15.5, Algorithm 15.5.2) gives a spanning tree \(T\) of \(N_r\) with \(\mathrm{parent}(w)\), a preorder number \(\mathrm{pre}(w) \in 1..n\) (order of first visit), a postorder number \(\mathrm{post}(w)\) (order of finish) and the reverse postorder (RPO). \(u \preceq_T v\) means \(u\) is an ancestor of \(v\) in \(T\) (\(u = v\) allowed); \(u \prec_T v\) a proper ancestor.

Lemma 15.1.10 (Dominators are tree ancestors)

If \(d \mathrel{\mathrm{dom}} n\) then \(d \preceq_T n\); consequently \(\mathrm{pre}(d) \le \mathrm{pre}(n)\) and \(\mathrm{post}(d) \ge \mathrm{post}(n)\).

Proof

The tree path \(r \leadsto n\) in \(T\) is a path in \(G\), so it contains \(d\); the nodes on it are exactly the \(T\)-ancestors of \(n\). Ancestors are visited first and finished last.

Iterative dataflow¶

Algorithm 15.1.11 (Iterative dominator sets)

Input: a flowgraph \(G = (N, E, r)\), any shape.
Output: \(\mathrm{Dom}(n)\) for every \(n \in N_r\) as bit vectors, the number of passes, and \(\mathrm{idom}\).
Precondition: none (irreducible graphs and unreachable nodes allowed; unreachable predecessors are ignored).
Postcondition: Dom[n] \(= \mathrm{Dom}(n)\) for every \(n \in N_r\) (Theorem 15.1.8).
Invariant: Dom[n] \(\supseteq \mathrm{Dom}(n)\) at all times, and every Dom[n] only shrinks (Lemma 15.1.21).

function IterativeDominators(G = (N, E, r)):
    order ← ReversePostorder(G)             # reachable nodes only (Lesson 15.5)
    ALL ← set of the nodes in order         # ⊤ of the lattice
    Dom[r] ← {r}
    for n in order, n ≠ r:
        Dom[n] ← ALL
    passes ← 0
    repeat
        changed ← false
        passes ← passes + 1
        for n in order, n ≠ r:
            new ← ALL
            for p in preds(n):
                if p is reachable:
                    new ← new ∩ Dom[p]      # bitwise AND
            new ← new ∪ {n}
            if new ≠ Dom[n]:
                Dom[n] ← new
                changed ← true
    until not changed
    return Dom, passes

function IdomFromDomSets(Dom, n):           # n reachable, n ≠ r
    return the d ∈ Dom[n] ∖ {n} with the largest |Dom[d]|

IdomFromDomSets is correct by Theorem 15.1.6: the strict dominators form a chain and, by part (c), each one's set is strictly larger than the sets above it. You implement this as computeIdoms(G, D, DomAlgorithm::Iterative, &Stats) with Stats->Passes (exercise E2).

Cooper–Harvey–Kennedy¶

Algorithm 15.1.12 (Cooper–Harvey–Kennedy)

Input: a flowgraph \(G\) and a DFS of it (postorder numbers postnum, RPO).
Output: doms[n] \(= \mathrm{idom}(n)\) for every \(n \in N_r \setminus \{r\}\).
Precondition: nodes are processed in RPO, so the DFS parent of each node is processed before it (unreachable predecessors are never processed).
Postcondition: doms is the parent array of the dominator tree \(\mathcal{D}\).
Invariant: for every processed \(b\), the chain \(b,\) doms[b]\(,\) doms[doms[b]]\(, \dots, r\) has strictly increasing postorder numbers and, as a set, contains \(\mathrm{Dom}(b)\) and only DFS-tree ancestors of \(b\); chains only shrink (Lemma 15.1.24).

function CHK(G = (N, E, r)):
    (rpo, postnum) ← ReversePostorder(G) with postorder numbers
    for n in N: doms[n] ← undefined
    doms[r] ← r                             # the root points at itself while iterating
    repeat
        changed ← false
        for b in rpo, b ≠ r:
            new ← undefined
            for p in preds(b):
                if doms[p] is defined:      # p already processed (and reachable)
                    if new is undefined:
                        new ← p
                    else:
                        new ← Intersect(p, new)
            if doms[b] ≠ new:
                doms[b] ← new
                changed ← true
    until not changed
    doms[r] ← undefined                     # the root has no idom
    return doms

function Intersect(b1, b2):                 # nearest common ancestor in the doms[] tree
    finger1 ← b1
    finger2 ← b2
    while finger1 ≠ finger2:
        while postnum[finger1] < postnum[finger2]:
            finger1 ← doms[finger1]
        while postnum[finger2] < postnum[finger1]:
            finger2 ← doms[finger2]
    return finger1

This is Figure 3 of [CHK01]. The finger with the smaller postorder number is deeper in the tree, so it moves up; when both fingers stand on the same node, that node is the nearest common ancestor of b1 and b2 in the current tree. You implement it as computeIdoms(G, D, DomAlgorithm::CHK, &Stats) (exercise E3).

Lengauer–Tarjan¶

Identify every reachable node with its preorder number \(1..n\) (\(r = 1\)).

Definition 15.1.13 (Semidominator)

For \(w \neq r\),

\[ \mathrm{sdom}(w) \triangleq \min \{\, v \mid \exists\, v = v_0 \to v_1 \to \dots \to v_k = w \text{ with } v_i > w \text{ for } 0 < i < k \,\}. \]

The parent of \(w\) qualifies (\(k = 1\)), so \(\mathrm{sdom}(w) \le \mathrm{parent}(w) < w\).

Lemma 15.1.14 (Where the semidominator sits)

For \(w \neq r\): \(\mathrm{sdom}(w) \prec_T w\), and \(\mathrm{idom}(w) \preceq_T \mathrm{sdom}(w)\).

Proof sketch (full proof: [LT79, §2, Lemmas 1, 3 and 4])

First claim. A standard DFS fact [LT79, Lemma 1]: if \(v < w\) (preorder), every path \(v \leadsto w\) contains a common \(T\)-ancestor of \(v\) and \(w\). Apply it to the path of Definition 15.1.13: its inner nodes are \(> w\), so the common ancestor it contains is its first node \(v = \mathrm{sdom}(w)\), which is therefore an ancestor of \(w\). Second claim. \(\mathrm{idom}(w)\) is a \(T\)-ancestor of \(w\) (Lemma 15.1.10). If it were a proper descendant of \(\mathrm{sdom}(w)\), the tree path \(r \leadsto \mathrm{sdom}(w)\) (all numbers \(\le \mathrm{sdom}(w)\)) followed by the semidominator path (inner numbers \(> w\)) would reach \(w\) without passing through any node numbered strictly between \(\mathrm{sdom}(w)\) and \(w\), in particular avoiding \(\mathrm{idom}(w)\): a contradiction.

Theorem 15.1.15 (Semidominator theorem)

For \(w \neq r\),

\[ \mathrm{sdom}(w) = \min\bigl( \{\, v \mid (v, w) \in E,\ v < w \,\} \cup \{\, \mathrm{sdom}(u) \mid u > w \text{ and } \exists (v, w) \in E \text{ with } u \preceq_T v \,\} \bigr). \]

Proof sketch (full proof: [LT79, §2, Theorem 4])

Let \(x\) be the right-hand side. \(\mathrm{sdom}(w) \le x\): a predecessor \(v < w\) gives a semidominator path of length 1. For the second set, take \(u > w\) with \(u \preceq_T v\) and \((v, w) \in E\): the semidominator path of \(u\) (inner nodes \(> u > w\)), then the tree path \(u \leadsto v\) (descendants of \(u\), numbers \(\ge u > w\)), then \(v \to w\) is a path from \(\mathrm{sdom}(u)\) to \(w\) whose inner nodes are all \(> w\). \(x \le \mathrm{sdom}(w)\): take a semidominator path \(v_0 \to \dots \to v_k = w\) with \(v_0 = \mathrm{sdom}(w)\). If \(k = 1\), \(v_0\) is in the first set. Otherwise \(v_{k-1} > w\); let \(j\) be the smallest index \(\ge 1\) with \(v_j \preceq_T v_{k-1}\). Using Lemma 1 of [LT79] again, every \(v_i\) with \(1 \le i < j\) is \(> v_j\), so \(v_0 \to \dots \to v_j\) witnesses \(\mathrm{sdom}(v_j) \le v_0\), and \(u = v_j\) is in the second set.

Corollary 15.1.16 (Immediate dominators from semidominators)

For \(w \neq r\), let \(u\) be a node with minimum \(\mathrm{sdom}(u)\) among the nodes on the tree path \(\mathrm{sdom}(w) \prec_T u \preceq_T w\). Then \(\mathrm{idom}(w) = \mathrm{sdom}(w)\) if \(\mathrm{sdom}(u) = \mathrm{sdom}(w)\), and \(\mathrm{idom}(w) = \mathrm{idom}(u)\) otherwise.

Proof sketch (full proof: [LT79, §2, Theorems 2–3 and Corollary 1])

If no node strictly between \(\mathrm{sdom}(w)\) and \(w\) on the tree path has a smaller semidominator, then every path from \(r\) to \(w\) must enter that tree path through \(\mathrm{sdom}(w)\) or above it: a path that jumps past \(\mathrm{sdom}(w)\) into the segment would give some node on it a semidominator above \(\mathrm{sdom}(w)\). Hence \(\mathrm{sdom}(w)\) dominates \(w\), and by Lemma 15.1.14 it is the idom ([LT79, Theorem 2]). Otherwise, \(u\)'s semidominator lies above \(\mathrm{sdom}(w)\), so paths can bypass \(\mathrm{sdom}(w)\) through \(u\)'s segment, and the dominators of \(w\) are exactly those of \(u\) ([LT79, Theorem 3]).

A semidominator is not always the idom

In the running example (preorder \(A{=}1, \dots, I{=}9\)), \(\mathrm{sdom}(H) = C\): \(C \to H\) is an edge and no smaller node reaches \(H\) through nodes numbered above 8. But \(\mathrm{idom}(H) = B\), because the node \(E\) on the tree path from \(C\) to \(H\) has \(\mathrm{sdom}(E) = B < C\): the path \(A \to B \to E \to H\) bypasses \(C\). Corollary 15.1.16 applies with \(u = E\): \(\mathrm{idom}(H) = \mathrm{idom}(E) = B\).

Algorithm 15.1.17 (Lengauer–Tarjan)

Input: a flowgraph \(G\) and its DFS: vertex[i] (node with preorder number \(i\)), parent.
Output: dom[w] \(= \mathrm{idom}(w)\) for every reachable \(w \ge 2\), and semi[w] \(= \mathrm{sdom}(w)\) as a by-product.
Precondition: the numbering is a DFS preorder (\(1..n\)); 0 is a sentinel "no node" with semi[0] = label[0] = size[0] = 0.
Postcondition: dom is the parent array of \(\mathcal{D}\) in preorder numbers.
Invariant: when \(w\) is processed in step 2, the forest contains exactly the tree edges into nodes numbered \(> w\), and EVAL(v) returns a node of minimum semi on the forest path from \(v\) up to (excluding) the root of \(v\)'s tree, or \(v\) itself if \(v\) is a root (Lemma 15.1.26).

function LengauerTarjan(G = (N, E, r)):
 1:  number the reachable nodes 1..n in DFS preorder; vertex[i] = node i; parent[w]
 2:  for w in 1..n:
 3:      semi[w] ← w;  label[w] ← w;  ancestor[w] ← 0
 4:      size[w] ← 1;  child[w] ← 0;  bucket[w] ← {}
 5:  for w from n down to 2:
 6:      for v in preds(w), v reachable:            # step 2: semidominator
 7:          u ← EVAL(v)
 8:          if semi[u] < semi[w]: semi[w] ← semi[u]
 9:      add w to bucket[semi[w]]
10:      LINK(parent[w], w)
11:      for v in bucket[parent[w]]:                # step 3: implicit idoms
12:          remove v from bucket[parent[w]]
13:          u ← EVAL(v)
14:          dom[v] ← u if semi[u] < semi[v] else parent[w]
15:  for w from 2 to n:                             # step 4: explicit idoms
16:      if dom[w] ≠ semi[w]: dom[w] ← dom[dom[w]]
17:  return dom                                     # dom[w] = idom(w) for w ≥ 2

Simple linking: the forest is a subgraph of \(T\); EVAL compresses the path it walks.

function LINK_simple(v, w):
    ancestor[w] ← v

function EVAL_simple(v):
    if ancestor[v] = 0: return v
    COMPRESS(v)
    return label[v]

function COMPRESS(v):                               # precondition: ancestor[v] ≠ 0
    if ancestor[ancestor[v]] ≠ 0:
        COMPRESS(ancestor[v])
        if semi[label[ancestor[v]]] < semi[label[v]]:
            label[v] ← label[ancestor[v]]
        ancestor[v] ← ancestor[ancestor[v]]

Sophisticated (balanced) linking keeps each tree of the forest as a root with a chain of "subtree roots" linked through child, sized so that paths stay logarithmic before compression (the appendix of [LT79]):

function LINK_balanced(v, w):
    s ← w
    while semi[label[w]] < semi[label[child[s]]]:
        if size[s] + size[child[child[s]]] ≥ 2 · size[child[s]]:
            ancestor[child[s]] ← s
            child[s] ← child[child[s]]
        else:
            size[child[s]] ← size[s]
            ancestor[s] ← child[s]
            s ← child[s]
    label[s] ← label[w]
    size[v] ← size[v] + size[w]
    if size[v] < 2 · size[w]:
        swap(s, child[v])
    while s ≠ 0:
        ancestor[s] ← v
        s ← child[s]

function EVAL_balanced(v):
    if ancestor[v] = 0: return label[v]
    COMPRESS(v)
    if semi[label[ancestor[v]]] ≥ semi[label[v]]: return label[v]
    return label[ancestor[v]]

The course solution uses an explicit stack instead of recursion in COMPRESS (same effect, no stack overflow on 100 000-node chains). You implement it as computeIdoms(G, D, DomAlgorithm::LengauerTarjan) (E4) and, optionally, DomAlgorithm::LengauerTarjanBalanced (E5 ★).

Semi-NCA¶

Lemma 15.1.18 (Semi-NCA)

For \(w \neq r\), \(\mathrm{idom}(w) = \mathrm{NCA}_{\mathcal{D}}(\mathrm{parent}(w), \mathrm{sdom}(w))\), the nearest common ancestor in the dominator tree.

Proof sketch (full proof: [Geo05, pp. 21–23])

Let \(x = \mathrm{NCA}_{\mathcal{D}}(\mathrm{parent}(w), \mathrm{sdom}(w))\). \(x\) dominates \(w\): every path \(r \leadsto w\) either enters \(w\) from its parent's side or through a path that, by Theorem 15.1.15, starts at or above \(\mathrm{sdom}(w)\) with all inner nodes \(> w\); in both cases it passes through a node that \(x\) dominates before reaching \(w\) without re-entering \(x\)'s complement, so it contains \(x\) ([Geo05] makes this precise with Corollary 15.1.16). No deeper node dominates \(w\): a strict dominator \(d\) of \(w\) below \(x\) would dominate both \(\mathrm{parent}(w)\) (every path to the parent extends to \(w\)) and, by Lemma 15.1.14 applied to \(d\)'s position on the tree path, \(\mathrm{sdom}(w)\), contradicting that \(x\) is the nearest common ancestor.

Algorithm 15.1.19 (Semi-NCA)

Input: a flowgraph \(G\) and its DFS preorder numbering with parent.
Output: idom[w] for every reachable \(w \ge 2\).
Precondition: the numbering is a DFS preorder; phase 2 processes \(w\) in increasing number.
Postcondition: idom is the parent array of \(\mathcal{D}\).
Invariant: when \(w\) is processed in phase 2, idom[x] is final for every \(x < w\), so the idom pointers of \(1..w-1\) form the dominator tree of those nodes (Theorem 15.1.28).

function SemiNCA(G = (N, E, r)):
    number the reachable nodes 1..n in DFS preorder; parent[w]
    for w in 1..n:
        semi[w] ← w;  label[w] ← w;  ancestor[w] ← 0;  idom[w] ← parent[w]
    for w from n down to 2:                         # phase 1: semidominators
        for v in preds(w), v reachable:
            u ← EVAL_simple(v)
            if semi[u] < semi[w]: semi[w] ← semi[u]
        LINK_simple(parent[w], w)
    for w from 2 to n:                              # phase 2: NCA in the partial tree
        x ← idom[w]                                 # = parent[w]
        while x > semi[w]:
            x ← idom[x]
        idom[w] ← x
    return idom

This is Georgiadis's formulation [Geo05, pp. 21–23], the same one SemiNCAInfo::runSemiNCA uses [LLVM-GDTC]. You implement it as computeIdoms(G, D, DomAlgorithm::SemiNCA) (E6 ★).

3. Worked example¶

The running example, as a flowgraph with successors in listed order:

A -> B        B -> C, E     C -> D, H     D -> E     E -> F, H
F -> G        G -> H, E     H -> I, B     I -> (exit)

A depth-first search from A (successors in listed order) visits A B C D E F G H I, so the preorder numbers are A=1 … I=9 and the DFS tree is the chain A–B–C–D–E–F–G–H–I. The non-tree edges are H→B and G→E (back edges), and B→E, C→H, E→H (forward edges). Postorder is I H G F E D C B A, so RPO is again A … I and the postorder numbers (0-based, as CHK uses them) are I=0, H=1, G=2, F=3, E=4, D=5, C=6, B=7, A=8.

Try it

./course drill rpo --difficulty easy --solution prints the DFS as an event table; the chapter's example is tests/ch15/Inputs/running-example.ll, and opt -load-pass-plugin=build/<preset>/lib/PebblePasses.so -passes='print<pebble-dfs>' -disable-output tests/ch15/Inputs/running-example.ll shows your own numbering.

Iterative dataflow on the running example¶

Dom sets start at ⊤ (all nodes) except Dom(A) = {A}; each pass visits the nodes in RPO.

node	init	pass 1	pass 2
A	{A}	{A}	{A}
B	⊤	{A,B}	{A,B}
C	⊤	{A,B,C}	{A,B,C}
D	⊤	{A,B,C,D}	{A,B,C,D}
E	⊤	{A,B,E}	{A,B,E}
F	⊤	{A,B,E,F}	{A,B,E,F}
G	⊤	{A,B,E,F,G}	{A,B,E,F,G}
H	⊤	{A,B,H}	{A,B,H}
I	⊤	{A,B,H,I}	{A,B,H,I}

Pass 1, B: preds A ({A}) and H (still ⊤) → {A} ∩ ⊤ ∪ {B} = {A,B}. A ⊤ predecessor never removes anything, which is why ⊤ is the right initial value (Lemma 15.1.21).
Pass 1, E: preds B ({A,B}), D ({A,B,C,D}) and G (still ⊤) → {A,B} ∪ {E}.
Pass 1, H: preds C ({A,B,C}), E ({A,B,E}), G ({A,B,E,F,G}) → {A,B} ∪ {H}.
Pass 2 recomputes every set with the final predecessor sets and changes nothing, so the sets are the fixed point. Two passes: the CFG is reducible, and in RPO every predecessor that is not a back-edge source comes first (Theorem 15.1.22).

Immediate dominators from the sets: idom(E) is the member of {A,B} with the largest set, B; likewise idom(H) = B, idom(I) = H.

Cooper–Harvey–Kennedy on the running example¶

doms[A] = A; all others undefined. Postorder numbers: I=0, H=1, G=2, F=3, E=4, D=5, C=6, B=7, A=8. Each intersect lists the finger positions as (finger1:postnum, finger2:postnum).

Pass 1

step	b	processed preds	start	intersect walks	doms[b]
1	B	A (H not yet)	A	—	A (was undefined)
2	C	B	B	—	B
3	D	C	C	—	C
4	E	B, D (G not yet)	B	intersect(D, B): (D:5, B:7) → (C:6, B:7) → (B:7, B:7) ⇒ B	B
5	F	E	E	—	E
6	G	F	F	—	F
7	H	C, E, G	C	intersect(E, C): (E:4, C:6) → (B:7, C:6) → (B:7, B:7) ⇒ B; intersect(G, B): (G:2, B:7) → (F:3, B:7) → (E:4, B:7) → (B:7, B:7) ⇒ B	B
8	I	H	H	—	H

Pass 2 (confirming)

step	b	processed preds	start	intersect walks	doms[b]
9	B	A, H	A	intersect(H, A): (H:1, A:8) → (B:7, A:8) → (A:8, A:8) ⇒ A	A (unchanged)
10	C	B	B	—	B
11	D	C	C	—	C
12	E	B, D, G	B	intersect(D, B) ⇒ B (as step 4); intersect(G, B) ⇒ B (as step 7)	B
13	F	E	E	—	E
14	G	F	F	—	F
15	H	C, E, G	C	as step 7 ⇒ B	B
16	I	H	H	—	H

Nothing changed in pass 2, so doms is final: idom = {B: A, C: B, D: C, E: B, F: E, G: F, H: B, I: H}.

The irreducible function @chk_irreducible in tests/ch15/Inputs/running-example.ll (R → A, B; A → E; B → C, D; E → C; C → E, D; D → C) shows why CHK can need more passes: in RPO R B A E C D, E is processed with only A as a processed predecessor, so pass 1 sets doms[E] = A; C's intersect then pulls C to R, and only in pass 2 does intersect(C, A) move E to R. Pass 3 confirms: three passes.

Lengauer–Tarjan on the running example¶

Preorder numbers A=1 … I=9; parent is the previous letter. The table shows, for each w from 9 down to 2: EVAL of each predecessor (with the semidominator number of the node EVAL returns), the resulting sdom(w), where w is put, the LINK, the implicit idoms defined by draining bucket(parent(w)), and the forest afterwards (ancestor pointers that are set; label values that differ from the node itself). Buckets not listed are empty.

w (num)	predecessors: EVAL	sdom(w)	bucket	LINK	bucket(parent(w)) drained	ancestor after	label ≠ self	buckets after
I (9)	EVAL(H)=H (8)	H	H	H→I	I: semi(I)=semi(I) ⇒ dom(I) = H	I→H	—	—
H (8)	EVAL(C)=C (3), EVAL(E)=E (5), EVAL(G)=G (7)	C	C	G→H	bucket(G) empty	I→H, H→G	—	C:
G (7)	EVAL(F)=F (6)	F	F	F→G	G ⇒ dom(G) = F	I→H, H→G, G→F	—	C:
F (6)	EVAL(E)=E (5)	E	E	E→F	F ⇒ dom(F) = E	I→H, H→G, G→F, F→E	—	C:
E (5)	EVAL(B)=B (2), EVAL(D)=D (4), EVAL(G)=F (5)	B	B	D→E	bucket(D) empty	E→D, F→E, G→E, H→G, I→H	G→F	B: {E}, C: {H}
D (4)	EVAL(C)=C (3)	C	C	C→D	H: EVAL(H)=E, semi(E)=2 < semi(H)=3 ⇒ dom(H) = E (deferred); D: EVAL(D)=D ⇒ dom(D) = C	D→C, E→C, F→E, G→C, H→C, I→H	G→E, H→E	B:
C (3)	EVAL(B)=B (2)	B	B	B→C	E: EVAL(E)=E ⇒ dom(E) = B; C ⇒ dom(C) = B	C→B, D→C, E→B, F→E, G→C, H→C, I→H	G→E, H→E	—
B (2)	EVAL(A)=A (1), EVAL(H)=E (2)	A	A	A→B	B ⇒ dom(B) = A	B→A, C→B, D→C, E→B, F→E, G→C, H→B, I→H	G→E, H→E	—

What happened at the interesting rows:

w = E. Predecessor G is already linked (G > E). Its forest path is G → F → E, and E is the root of that tree (E is not linked yet). EVAL(G) compresses: G's ancestor becomes the root E and label(G) becomes F, because semi(F) = 5 < semi(G) = 6. The best candidate is still B (a direct predecessor numbered below E), so sdom(E) = B (Theorem 15.1.15, first set).
w = D, draining bucket(C) = {H}. After LINK(C, D) the forest path of H is H → G → E → D → C with root C. EVAL(H) compresses it: H, G and E now point straight at C, and H and G get label E, the node with the smallest semi on the path (semi(E) = 2). It returns E, whose semi (B = 2) is smaller than semi(H) (C = 3). So H's idom is not its semidominator: this is the second case of Corollary 15.1.16 with \(u = E\). Lengauer–Tarjan records dom(H) = E and fixes it in step 4.
w = B. Predecessor H is linked; EVAL(H) = E with semi 2 (B), so the back edge H → B contributes nothing better than A.

Step 4, in increasing number: dom(w) = semi(w) for every w except H, whose deferred value E is replaced by dom(E) = B. Result:

node	B	C	D	E	F	G	H	I
sdom	A	B	C	B	E	F	C	H
idom	A	B	C	B	E	F	B	H

Balanced linking. The semidominators and idoms are the same; only the forest differs. size and child evolve as follows (entries equal to the defaults size = 1, child = 0 omitted):

after w	size	child	ancestor	label ≠ self
I	H=2	—	I→H	—
H	G=3, H=2	G=H	I→H	—
G	F=4, G=3, H=2	F=G, G=H	I→H	—
F	E=5, F=4, G=3, H=2	E=F, F=H, G=H	G→F, I→H	—
E	D=6, E=5, F=5, G=3, H=2	D=F, E=F, G=H	E→F, G→F, H→F, I→H	F→E
D	C=7, D=6, E=5, F=5, G=3, H=2	C=D, D=F, E=F, G=H	E→F, G→F, H→F, I→H	F→E
C	B=8, C=7, D=6, E=5, F=5, G=3, H=2	B=C, C=F, D=F, E=F, G=H	D→C, E→F, G→F, H→F, I→H	F→E
B	A=9, B=8, C=8, D=6, E=5, F=8, G=3, H=2	A=F, B=C, C=F, D=F, E=F, G=H	B→F, C→F, D→C, E→F, G→F, H→F, I→H	F→B

The balanced forest is not a subgraph of T: LINK re-hangs subtrees by size, so pointers such as B→F cross the DFS tree. That rebalancing is what bounds the length of EVAL paths before compression.

Try it

./course drill lengauer-tarjan --seed 12 --difficulty medium --solution prints this table for a fresh CFG; the hard level mixes in irreducible CFGs.

Semi-NCA on the running example¶

Same semidominators (A, B, C, B, E, F, C, H for B … I). Phase 2 in preorder, climbing through finished idoms while the number is above num(sdom(w)):

w	parent	sdom (num)	climb	idom
B	A	A (1)	A	A
C	B	B (2)	B	B
D	C	C (3)	C	C
E	D	B (2)	D (4) → C (3) → B (2)	B
F	E	E (5)	E	E
G	F	F (6)	F	F
H	G	C (3)	G (7) → F (6) → E (5) → B (2)	B
I	H	H (8)	H	H

H shows the difference from Lengauer–Tarjan: instead of deferring through buckets, the climb passes C's level (E has number 5 > 3, E's idom B has 2 ≤ 3) and lands on B directly, which is \(\mathrm{NCA}_{\mathcal{D}}(G, C)\) as Lemma 15.1.18 promises.

All four algorithms give the same tree:

A
└── B
    ├── C
    │   └── D
    ├── E
    │   └── F
    │       └── G
    └── H
        └── I

Try it

./course drill dominators --seed 15 --difficulty medium --solution shows the iterative and CHK traces side by side for a random CFG.

4. Invariants and correctness¶

Iterative dataflow¶

Lemma 15.1.20 (Iteration stays above the answer)

Let \(F\) be the function on vectors of sets defined by the right-hand sides of Theorem 15.1.8. If \(X \supseteq \mathrm{Dom}\) pointwise, then \(F(X) \supseteq \mathrm{Dom}\) pointwise; and applying \(F\) to any single component preserves \(X \supseteq \mathrm{Dom}\).

Proof

\(F\) is monotone: a larger \(X(p)\) gives a larger intersection. So \(X \supseteq \mathrm{Dom}\) implies \(F(X) \supseteq F(\mathrm{Dom}) = \mathrm{Dom}\), the last step by Theorem 15.1.8. Updating one component \(n\) to \(F(X)(n)\) changes only that component, and \(F(X)(n) \supseteq \mathrm{Dom}(n)\).

Lemma 15.1.21 (Invariant of Algorithm 15.1.11)

At every point of Algorithm 15.1.11, Dom[n] \(\supseteq \mathrm{Dom}(n)\) for all \(n \in N_r\), and no Dom[n] ever grows.

Proof

Initialization: Dom[r] \(= \{r\} = \mathrm{Dom}(r)\) and every other Dom[n] \(= N_r \supseteq \mathrm{Dom}(n)\). Maintenance: each update sets Dom[n] to \(F(\text{Dom})(n)\) (skipping unreachable predecessors is exactly the \(\cap N_r\) of Theorem 15.1.8), so Lemma 15.1.20 applies. No growth, by induction on the number of updates: the first update of \(n\) replaces \(N_r\) by a subset; later, every argument Dom[p] has only shrunk since \(n\)'s previous update, so by monotonicity the new value is a subset of the old one.

Theorem 15.1.22 (Correctness and termination of the iterative algorithm)

Algorithm 15.1.11 terminates after at most \(\lvert N_r \rvert^2 + 1\) passes and returns \(\mathrm{Dom}\). On a reducible CFG it needs at most 2 passes: exactly 2 when \(\lvert N_r \rvert \ge 3\), and 1 when \(\lvert N_r \rvert \le 2\) (then every set already starts at its final value, so pass 1 changes nothing).

Proof

Termination: by Lemma 15.1.21 each set only shrinks; there are \(\lvert N_r \rvert\) sets of at most \(\lvert N_r \rvert\) elements, and every pass except the last removes at least one element. Result: at termination a whole pass changed nothing, so Dom is a solution of the equations of Theorem 15.1.8, hence Dom \(\subseteq \mathrm{Dom}\); with Lemma 15.1.21, Dom \(= \mathrm{Dom}\). Two passes on reducible CFGs: in a reducible CFG every retreating edge \(p \to n\) has \(n \mathrel{\mathrm{dom}} p\) (Theorem 15.6.4(b) in Lesson 15.6), and a simple path from \(r\) never uses such an edge (it would visit \(n\) both before \(p\), because \(n \mathrel{\mathrm{dom}} p\), and after it). So \(\mathrm{Dom}\) is also the dominator relation of the graph without retreating edges, where it satisfies the equations of Theorem 15.1.8 with only the non-retreating predecessors. In RPO those predecessors precede \(n\). By induction along RPO, pass 1 gives each \(n\) the value \(\{n\} \cup \bigcap_{p\ \text{non-retreating}} \mathrm{Dom}(p) \cap \bigcap_{p\ \text{retreating}} \texttt{Dom}[p] = \mathrm{Dom}(n)\), because every retreating predecessor has Dom[p] \(\supseteq \mathrm{Dom}(p) \supseteq \mathrm{Dom}(n)\) (Lemma 15.1.21 and \(n \mathrel{\mathrm{dom}} p\)). Pass 2 changes nothing.

Proposition 15.1.23 (Pass bound in general)

With RPO order, the number of passes is at most \(d(G) + 2\), where \(d(G)\) is the loop connectedness (the largest number of retreating edges on any cycle-free path).

Proof sketch (full proof: [KU76, §3–4]; [Dragon2 §9.6.7])

After pass \(i\), Dom[n] is correct with respect to all paths that use at most \(i - 1\) retreating edges: a path with \(j\) retreating edges splits into \(j + 1\) RPO-increasing segments, and each pass propagates information along a whole increasing segment. Dominance is decided by simple paths, which use at most \(d(G)\) retreating edges, so pass \(d(G) + 1\) has the answer and pass \(d(G) + 2\) confirms it.

When it breaks: never on correctness; irreducible CFGs only cost passes (the bichain of section 5).

Cooper–Harvey–Kennedy¶

Lemma 15.1.24 (CHK's chains bracket the dominator sets)

Call \(b\) processed once doms[b] is defined, and let \(\mathrm{chain}(b) = \{b, \texttt{doms}[b], \texttt{doms}[\texttt{doms}[b]], \dots, r\}\) (for an unprocessed \(b\), read \(\mathrm{chain}(b)\) as ⊤ \(= N_r\)). At every point of Algorithm 15.1.12, for every processed \(b\): (a) \(\mathrm{post}(\texttt{doms}[b]) > \mathrm{post}(b)\) for \(b \neq r\), so the doms pointers form a tree rooted at \(r\); (b) Intersect(b1, b2) returns the nearest common ancestor of \(b_1\) and \(b_2\) in that tree; (c) \(\mathrm{Dom}(b) \subseteq \mathrm{chain}(b) \subseteq \{\, a \mid a \preceq_T b \,\}\); (d) \(\mathrm{chain}(b)\) never grows, and it strictly shrinks whenever doms[b] changes. (e) If Algorithm 15.1.11 is run in lockstep (same order, the same node updated at the same time), then \(\mathrm{chain}(b) \subseteq\) Dom[b] at every point.

Proof

By simultaneous induction on the updates. Note first that the DFS parent \(q\) of \(b\) precedes \(b\) in RPO, so it is processed before \(b\) and is one of the predecessors folded into new. (a) The fold returns a common ancestor of all folded nodes (by (b)), hence an ancestor-or-self of \(q\), whose postorder number exceeds \(\mathrm{post}(b)\); along doms pointers postorder numbers increase, so there is no cycle except \(r\)'s self-pointer. (b) Let \(c\) be the nearest common ancestor. Invariant of the loop: \(c\) is an ancestor-or-self of both fingers. If \(\mathrm{post}(f_1) < \mathrm{post}(f_2)\) then \(f_1 \neq c\) (otherwise \(c = f_1\) would be a proper ancestor of \(f_2\), with a larger postorder number), so moving \(f_1\) to its parent keeps the invariant. The postorder numbers strictly increase, so the loop ends, with both fingers on a common ancestor that \(c\) is an ancestor-or-self of; being common, it is \(c\). (c) Two kinds of events change chains. \(b\) gets a new pointer: the new chain is \(\{b\} \cup \bigcap_p \mathrm{chain}(p)\) over the processed predecessors \(p\), because the root paths of a tree intersect in the root path of the nearest common ancestor, which (b) computes. Upper bound: \(q\) is among the \(p\), and \(\mathrm{chain}(q) \subseteq \{a \preceq_T q\} \subseteq \{a \preceq_T b\}\). Lower bound: each processed \(p\) is reachable, a dominator of \(b\) other than \(b\) dominates \(p\) (a path to \(p\) avoiding it extends to \(b\)), so \(\mathrm{Dom}(b) \setminus \{b\} \subseteq \mathrm{Dom}(p) \subseteq \mathrm{chain}(p)\) for each \(p\). A proper ancestor \(a\) of \(b\) in the doms tree gets a new pointer: \(\mathrm{chain}(b)\) becomes \(S \cup \mathrm{chain}_{\mathrm{new}}(a)\), where \(S\) is the unchanged segment from \(b\) up to, excluding, \(a\). Upper bound: \(S \subseteq \mathrm{chain}_{\mathrm{old}}(b)\) consists of \(T\)-ancestors of \(b\), and \(a\) is one of them, so \(\mathrm{chain}_{\mathrm{new}}(a) \subseteq \{a' \preceq_T a\} \subseteq \{a' \preceq_T b\}\). Lower bound: let \(d \in \mathrm{Dom}(b) \setminus S\); then \(d \in \mathrm{chain}_{\mathrm{old}}(a)\), so \(d \preceq_T a \preceq_T b\). If \(d = a\) we are done. Otherwise \(d \mathrel{\mathrm{dom}} a\): a path \(r \leadsto a\) avoiding \(d\), followed by the tree path \(a \leadsto b\) (proper \(T\)-descendants of \(d\), so never \(d\)), would reach \(b\) avoiding \(d\). Hence \(d \in \mathrm{Dom}(a) \subseteq \mathrm{chain}_{\mathrm{new}}(a)\) by the first case. (d) The set of processed predecessors only grows and, by induction, their chains only shrink, so a re-assignment of \(b\) gives a subset of its previous chain; the chains of \(b\)'s descendants shrink with it. A chain determines its pointer (by (a), doms[b] is the element of \(\mathrm{chain}(b) \setminus \{b\}\) with the smallest postorder number), so a changed pointer means a strictly smaller chain. (e) Initially both sides are ⊤ except at \(r\). When \(b\) is updated, CHK's new chain is \(\{b\} \cup \bigcap_p \mathrm{chain}(p) \subseteq \{b\} \cup \bigcap_p\) Dom[p], Algorithm 15.1.11's new value (its unprocessed predecessors hold ⊤ and remove nothing). Implicit shrinking of descendants' chains only makes them smaller.

The inclusion (e) can be strict in the middle of a pass: when doms[a] changes, every chain through \(a\) shrinks at once, while the iterative algorithm's sets for \(a\)'s descendants change only when those nodes are revisited later in the pass. So "CHK is the iterative algorithm on another representation" holds for the fixed point, not step by step.

Theorem 15.1.25 (Correctness of CHK)

Algorithm 15.1.12 terminates and returns \(\mathrm{idom}\). When \(\lvert N_r \rvert \ge 2\) it makes at least 2 passes and at most as many as Algorithm 15.1.11 run with the same order (or 2, if that is larger); in particular exactly 2 on a reducible CFG, and at most \(d(G) + 2\) in general (Proposition 15.1.23).

Proof (following [CHK01, §3], with the invariant of Lemma 15.1.24)

Termination: every pass except the last changes some pointer, hence (Lemma 15.1.24(d)) strictly shrinks some chain or defines a pointer for the first time; there are \(\lvert N_r \rvert\) chains of at most \(\lvert N_r \rvert\) elements. Result: pass 1 processes every reachable node, so the last pass (pass 2 or later) recomputes every pointer from all reachable predecessors, and none changes; hence no chain changes during that pass, and at its end \(\mathrm{chain}(r) = \{r\}\) and \(\mathrm{chain}(b) = \{b\} \cup \bigcap_{p \in \mathrm{preds}(b) \cap N_r} \mathrm{chain}(p)\) for every other \(b\). So the chains are a solution of the equations of Theorem 15.1.8, hence \(\mathrm{chain}(b) \subseteq \mathrm{Dom}(b)\), and with Lemma 15.1.24(c) \(\mathrm{chain}(b) = \mathrm{Dom}(b)\). A root path of the doms tree equal to \(\mathrm{Dom}(b)\) has doms[b] as the strict dominator dominated by all the others, which is \(\mathrm{idom}(b)\) (Theorem 15.1.6). Passes: if Algorithm 15.1.11 holds the final sets after its pass \(j \ge 1\), then after CHK's pass \(j\) every chain lies between \(\mathrm{Dom}\) and Dom[] \(= \mathrm{Dom}\) (Lemma 15.1.24(c), (e)); in pass \(\max(j, 1) + 1\) every pointer is recomputed from chains equal to the fixed point, so nothing changes. Pass 1 always changes something when \(\lvert N_r \rvert \ge 2\) (pointers go from undefined to defined). The bounds follow from Theorem 15.1.22 and Proposition 15.1.23.

In the course's oracle tests the two algorithms make the same number of passes on every one of 50 000 random CFGs of up to 12 nodes (with the convention that CHK needs 2 when Algorithm 15.1.11 needs 1), but the proof above only gives the inequality.

Why RPO: the first processed predecessor must exist; in RPO the DFS parent of b is processed before b, so every reachable b has one. RPO also makes one pass suffice on reducible CFGs (Theorem 15.1.22). The numbering inside Intersect only has to put dominators before the nodes they dominate (Lemma 15.1.10): postorder (move the finger with the smaller number), preorder or RPO (move the finger with the larger number) all work. When it breaks: processing b when no predecessor is processed (possible in a non-topological order) leaves new undefined; unreachable predecessors must be skipped.

Lengauer–Tarjan¶

Lemma 15.1.26 (EVAL invariant)

In Algorithm 15.1.17, when \(w\) is processed the forest contains exactly the tree edges \((\mathrm{parent}(x), x)\) with \(x > w\). For \(v < w\), EVAL(v) \(= v\) with semi[v] \(= v\); for \(v > w\), EVAL(v) returns a node \(u\) with minimum semi[u] on the forest path from \(v\) up to, but excluding, the root of its tree, and every such \(u\) satisfies \(w < u \preceq_T v\).

Proof sketch (full proof: [LT79, §3])

Forest contents: line 10 links \(w\) to its parent right after processing \(w\), in decreasing order. Roots: the root of \(v\)'s tree is the first unlinked node on \(v\)'s tree path, i.e. the first ancestor numbered \(\le w\); so the path below the root consists exactly of the ancestors \(u\) of \(v\) with \(u > w\). Labels: COMPRESS shortcuts ancestor pointers to the root and keeps in label the minimum-semi node of the skipped segment, so after compression label[v] is the minimum over the whole path below the root. At the time line 7 or 13 runs, semi[u] is final for every linked \(u\) (linked nodes were processed before).

Theorem 15.1.27 (Correctness of Lengauer–Tarjan)

Algorithm 15.1.17 terminates and returns semi[w] \(= \mathrm{sdom}(w)\) and dom[w] \(= \mathrm{idom}(w)\) for every reachable \(w \ge 2\).

Proof

Termination: two loops over \(n\) nodes; COMPRESS recurses along ancestor pointers towards a root and every bucket element is removed once. Semidominators: by Lemma 15.1.26, lines 6–8 take the minimum over predecessors \(v < w\) (EVAL returns \(v\), semi[v] \(= v\)) and over semi[u] for the ancestors \(u > w\) of predecessors \(v > w\), which is the right-hand side of Theorem 15.1.15. Implicit idoms (lines 11–14): \(w\) is in bucket(\(\mathrm{sdom}(w)\)), drained right after \(\mathrm{sdom}(w)\)'s child on the tree path to \(w\) is linked (that child is the node whose parent is \(\mathrm{sdom}(w)\)); at that moment the forest path of \(w\) below the root is exactly the tree path segment \(\mathrm{sdom}(w) \prec_T u \preceq_T w\) of Corollary 15.1.16, so EVAL(w) returns its node \(u\) of minimum semidominator. Line 14 records \(\mathrm{sdom}(w)\) in the first case of the corollary and \(u\) in the second. Explicit idoms (lines 15–16): in the second case \(u < w\) and \(\mathrm{idom}(u)\) is already final when \(w\) is visited in increasing order, so dom[w] \(\gets\) dom[u] \(= \mathrm{idom}(u) = \mathrm{idom}(w)\).

When it breaks: a numbering that is not a DFS preorder (for example BFS) breaks Lemma 15.1.14, on which everything rests: semidominators must be computed w.r.t. a DFS spanning tree.

Semi-NCA¶

Theorem 15.1.28 (Correctness of Semi-NCA)

Phase 2 of Algorithm 15.1.19, run in increasing preorder, sets idom[w] \(= \mathrm{NCA}_{\mathcal{D}}(\mathrm{parent}(w), \mathrm{sdom}(w)) = \mathrm{idom}(w)\).

Proof

By induction on \(w\): idom[x] is correct for all \(x < w\) (base: idom[2] \(= 1 = r\)). The climb starts at \(\mathrm{parent}(w)\) and follows correct idoms, visiting the \(\mathcal{D}\)-ancestors of \(\mathrm{parent}(w)\), whose numbers strictly decrease (Lemma 15.1.10). It stops at the first ancestor \(x\) with \(x \le \mathrm{sdom}(w)\). \(x\) is an ancestor of \(\mathrm{sdom}(w)\) in \(\mathcal{D}\). \(x\) and \(\mathrm{sdom}(w)\) are both \(T\)-ancestors of \(\mathrm{parent}(w)\) (Lemmas 15.1.10 and 15.1.14), and \(x \le \mathrm{sdom}(w)\), so \(x \preceq_T \mathrm{sdom}(w)\). If \(x\) did not dominate \(\mathrm{sdom}(w)\), a path \(Q : r \leadsto \mathrm{sdom}(w)\) avoids \(x\); the tree path \(\mathrm{sdom}(w) \leadsto \mathrm{parent}(w)\) has numbers \(\ge \mathrm{sdom}(w)\), so it avoids \(x\) too unless \(x = \mathrm{sdom}(w)\), which \(Q\) would contain. Their concatenation reaches \(\mathrm{parent}(w)\) avoiding \(x\), contradicting \(x \mathrel{\mathrm{dom}} \mathrm{parent}(w)\). \(x\) is the nearest one. Every node visited before \(x\) has a number \(> \mathrm{sdom}(w)\) and so cannot dominate \(\mathrm{sdom}(w)\) (Lemma 15.1.10). Hence \(x = \mathrm{NCA}_{\mathcal{D}}(\mathrm{parent}(w), \mathrm{sdom}(w))\), which is \(\mathrm{idom}(w)\) by Lemma 15.1.18. Termination: the climb strictly decreases the node number.

When it breaks: processing in any order other than increasing preorder (the chain above parent(w) would not be final yet).

5. Complexity¶

\(n\) = reachable nodes, \(m\) = edges, \(h\) = height of the dominator tree, \(d = d(G)\) = loop connectedness, \(\alpha\) = inverse Ackermann function, \(w\) = machine word size in bits.

Technique	Time (worst)	Time (typical)	Space	Notes
Iterative bit vectors	\(O((d + 2) \cdot m \cdot n / w)\)	2–3 passes on real CFGs	\(O(n^2 / w)\) bits	2 passes on reducible CFGs
Cooper–Harvey–Kennedy	\(O((d + 2) \cdot m \cdot h)\)	near-linear, small constants	\(O(n)\)	intersect walks are the cost
Lengauer–Tarjan, simple	\(O(m \log n)\)	near-linear	\(O(n + m)\)	path compression only
Lengauer–Tarjan, sophisticated	\(O(m\,\alpha(m, n))\)	same as simple in practice	\(O(n + m)\)	extra `size`, `child` arrays
Semi-NCA	\(O(n^2)\)	near-linear	\(O(n + m)\)	phase 1 is LT's; phase 2 climbs

Proposition 15.1.29 (Cost of the iterative algorithm and CHK)

One pass of Algorithm 15.1.11 costs \(O(m \cdot n / w)\) word operations; one pass of Algorithm 15.1.12 costs \(O(m \cdot h)\). With Proposition 15.1.23 the totals are the first two rows of the table.

Proof

Each pass handles every edge once. The iterative algorithm does one \(n\)-bit AND per edge, \(\lceil n / w \rceil\) word operations. In CHK each edge costs at most one Intersect, whose fingers only move up and never below their start, so at most \(2h\) steps.

Proposition 15.1.30 (Cost of Lengauer–Tarjan and Semi-NCA)

Lengauer–Tarjan with simple linking runs in \(O(m \log n)\), with sophisticated linking in \(O(m\,\alpha(m, n))\); Semi-NCA's phase 1 costs \(O(m \log n)\) and its phase 2 \(O(n \cdot h) \subseteq O(n^2)\).

Proof sketch (full proof: [LT79, §4]; Semi-NCA: [Geo05])

Lines 1–4, 9–12 and 15–16 are \(O(n + m)\). The \(m + n\) EVAL calls on a forest built by \(n - 1\) LINKs are an instance of path compression over a union-find-like structure: Tarjan's analysis gives \(O(m \log n)\) for compression alone and \(O(m\,\alpha(m, n))\) with union by size, which is what the balanced LINK implements. Semi-NCA's climb for \(w\) walks at most the depth of \(\mathrm{parent}(w)\) in \(\mathcal{D}\).

Proposition 15.1.31 (Three pathological families)

(a) Ladder \(L_k\): nodes \(a_0, \dots, a_k, b_0, \dots, b_k\), edges \(a_i \to a_{i+1}\) (listed first), \(a_i \to b_i\), \(b_i \to b_{i+1}\). CHK and Semi-NCA take \(\Theta(k^2)\) steps; Lengauer–Tarjan stays \(O(k \log k)\). (b) Comb \(C_k\): a chain \(c_0 \to c_1 \to \dots \to c_k\) (listed first) where every \(c_i \to J\). CHK takes \(\Theta(k^2)\); Semi-NCA and Lengauer–Tarjan \(O(k \log k)\). (c) Bichain \(B_k\): \(R \to x_1\), \(R \to x_k\), \(x_i \leftrightarrow x_{i+1}\). The iterative algorithm and CHK need \(\Theta(k)\) passes.

Proof

(a) Paths to \(b_i\) are \(a_0 \to \dots \to a_j \to b_j \to \dots \to b_i\) for \(j \le i\); the paths for \(j = 0\) and \(j = i\) share only \(a_0\) and \(b_i\), so \(\mathrm{idom}(b_i) = a_0\). The DFS goes down the \(a\)-chain first, so \(\mathrm{parent}(b_i) = a_i\), the postorder is \(b_k, a_k, b_{k-1}, \dots, b_0, a_0\), and RPO is \(a_0, b_0, a_1, b_1, \dots\). When CHK processes \(b_i\) (in both passes), doms[b_{i-1}] \(= a_0\) and Intersect(a_i, b_{i-1}) climbs \(a_i \to a_{i-1} \to \dots \to a_0\): \(i\) steps, \(\sum_i i = \Theta(k^2)\). For Semi-NCA, \(\mathrm{sdom}(b_i) = a_0\): the DFS reaches the \(b\)-chain from its far end, so \(b_0, \dots, b_{i-1}\) are numbered above \(b_i\) and the path \(a_0 \to b_0 \to \dots \to b_i\) qualifies in Definition 15.1.13. Phase 2 climbs from \(\mathrm{parent}(b_i) = a_i\) through \(a_{i-1}, \dots, a_0\): again \(\Theta(k^2)\). Lengauer–Tarjan performs \(O(k)\) EVALs and LINKs, so Proposition 15.1.30 applies. (b) RPO is \(c_0, \dots, c_k, J\). Folding \(J\)'s predecessors \(c_0, c_1, \dots\) into new \(= c_0\), Intersect(c_i, c_0) climbs \(i\) steps: \(\Theta(k^2)\). Semi-NCA's only long climb is from \(\mathrm{parent}(J) = c_k\) to \(\mathrm{sdom}(J) = c_0\), \(k\) steps once. (c) RPO is \(R, x_1, \dots, x_k\). Pass 1 sets doms[x_i] \(= x_{i-1}\) for \(i < k\) (the successor \(x_{i+1}\) is not processed yet) and doms[x_k] \(= R\). In each later pass only the highest wrong node \(x_j\) sees a predecessor \(x_{j+1}\) whose chain already reaches \(R\) directly, and becomes \(R\); the others keep their chain. So the correct idom \(R\) travels down one node per pass: \(k\) passes (the course oracle idom_chk reports 5 passes for \(k = 5\); the lab measures 999 for \(k = 999\)).

At scale: Cooper, Harvey and Kennedy report their algorithm faster than their Lengauer–Tarjan implementation on the CFGs of their test suites, whose largest had tens of thousands of blocks [CHK01]; Georgiadis, Tarjan and Werneck found Semi-NCA the fastest overall on CFGs and synthetic families, with the iterative algorithm competitive on typical CFGs but degrading badly on adversarial ones [GTW06]. The lab reproduces both observations (section 8).

Iterative dataflow¶

Worklist instead of round-robin [KU76]: revisit only nodes whose predecessors changed — trade-off: saves work on large graphs, loses the simple "passes" bound.
Removal / path definitions [PM72]: Proposition 15.1.4 as an algorithm, \(O(n \cdot m)\) and trivially correct, the course's Python oracle dominators_by_removal — trade-off: quadratic, but no fixed point to reason about.
Sparse sets: store Dom(n) as a sorted list and intersect by merging — trade-off: better than bit vectors when sets are short (shallow trees), worse when deep.

Cooper–Harvey–Kennedy¶

Renumber nodes by postorder so doms and postnum are the same index space [CHK01] — trade-off: an extra array copy for much better locality; LLVM's SemiNCAInfo makes the same move with DFS numbers.
Preorder or RPO numbers in intersect (move the finger with the larger preorder / larger RPO number) — trade-off: none in correctness, choose whatever numbering you already have.
Same framework for frontiers: CHK's runner algorithm reuses doms (Lesson 15.3) — trade-off: none; it is why CHK is popular in teaching compilers.

Lengauer–Tarjan¶

Simple vs sophisticated linking [LT79]: \(O(m \log n)\) vs \(O(m\,\alpha)\) — trade-off: the balanced version needs two more arrays and more code and is rarely faster (the lab: 15.10 vs 15.16 ms at 100 000 blocks). LLVM's comment above SemiNCAInfo::eval says exactly this [LLVM-GDTC].
Truly linear algorithms [AHLT99, BGKRTW08]: microtree / path-compression tricks remove the \(\alpha\) factor — trade-off: far more complex, slower in practice.
Iterative DFS and COMPRESS — trade-off: none but code size; recursion overflows the stack on long chains (the course's DFS.DeepChainDoesNotOverflowTheStack test).

Semi-NCA¶

SNCA vs SLT hybrid: WebKit runs Semi-NCA below 20 000 blocks and LT above [WebKit-Dom] — trade-off: guards the \(O(n^2)\) case at the cost of two implementations.
Reverse-children caching: LLVM's runDFS records each node's predecessors seen during the DFS so phase 1 does not re-query the CFG (SemiNCAInfo::ReverseChildren) — trade-off: memory for speed.
Incremental use [GILS16]: run Semi-NCA only on an affected subtree (Lesson 15.2) — trade-off: needs the proper-support test to know which subtree.

7. In real compilers¶

Iterative dataflow¶

In production the bit-vector algorithm survives only as a checker, because its \(n^2\) bits and repeated passes lose to every alternative once a function has more than a few hundred blocks:

WebKit Source/WTF/wtf/Dominators.h — class NaiveDominators: iterative dominator sets, used when a Dominators object is built with selfCheck to cross-check the fast tree [WebKit-Dom].
LLVM has no iterative dominator algorithm; its verifier instead rebuilds a fresh tree and compares (SemiNCAInfo::IsSameAsFreshTree in llvm/include/llvm/Support/GenericDomTreeConstruction.h, LLVM 23.1.2) [LLVM-GDTC].
This course uses it the same way: dominators_iterative in tools/course/lib/cfg.py is one of four independent oracles, and your E2 is checked against LLVM.

Reading Dom sets off LLVM's dominator tree

Reproduce (clang 23.1.2, opt 23.1.2; clang-23 is the course toolchain's clang, called plain clang in Homebrew's LLVM 23; any OS):

cat > nest.c <<'EOF'
int f(int n) { int s = 0; for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) s += j; return s; }
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm nest.c -o nest.ll
opt -passes='sroa,print<domtree>' -disable-output nest.ll

Output (complete):

DominatorTree for function: f
=============================--------------------------------
Inorder Dominator Tree: 
  [1] %entry {0,9} [0]
    [2] %for.cond {1,9} [1]
      [3] %for.body {2,8} [2]
        [4] %for.cond1 {3,8} [3]
          [5] %for.body3 {4,6} [4]
            [6] %for.inc {5,6} [5]
          [5] %for.end {6,8} [4]
            [6] %for.inc4 {7,8} [5]
      [3] %for.end6 {8,9} [2]
Roots: %entry

What to notice: by Theorem 15.1.6(d), \(\mathrm{Dom}(n)\) is the root path of \(n\): \(\mathrm{Dom}(\texttt{for.inc}) = \{\texttt{entry}, \texttt{for.cond}, \texttt{for.body}, \texttt{for.cond1}, \texttt{for.body3}, \texttt{for.inc}\}\). Check the equation of Theorem 15.1.8 at the inner header: its predecessors are for.body and for.inc (the latch), and \(\{n\} \cup (\mathrm{Dom}(\texttt{for.body}) \cap \mathrm{Dom}(\texttt{for.inc}))\) is for.cond1's root path; the back-edge predecessor's larger set does not change the intersection, which is why the iterative algorithm needs only two passes on this reducible CFG (Theorem 15.1.22). Each [d] is the depth and {in,out} the interval of Corollary 15.1.7.

Cooper–Harvey–Kennedy¶

GCC 15 gcc/dominance.cc — iterate_fix_dominators: after a CFG change, GCC recomputes the dominators of the affected block set with CHK (its reference [3]), "since the set BBS is usually small (rarely exceeding 10 during gcc bootstrap)", instead of running Lengauer–Tarjan again. The same comment cites Ramalingam–Reps and Sreedhar–Gao–Lee (Lesson 15.2) [GCC-Dominance].
Go 1.25 src/cmd/compile/internal/ssa/dom.go — dominatorsSimple is CHK (the comment names Cooper, Harvey and Kennedy; intersect compares postorder numbers); the default dominators calls Lengauer–Tarjan [Go-Dom].
Cranelift (Wasmtime 36) cranelift/codegen/src/dominator_tree/simple.rs — SimpleDominatorTree, "computed using Keith D. Cooper's 'Simple, Fast Dominator Algorithm'", kept as the baseline for verification now that the main tree uses Semi-NCA [Cranelift-Dom]. It compares RPO numbers rather than postorder numbers (the variant of section 6).
Pebble your computeIdoms(…, DomAlgorithm::CHK, …) behind the pebble-domtree analysis (pebble/lib/Passes/Dominance/Ch15Passes.cpp).

An irreducible loop from C: where CHK needs its extra pass

Reproduce (clang 23.1.2, opt 23.1.2):

cat > goto.c <<'EOF'
int g(int n, int k) {
  int s = 0, i = 0;
  if (k) goto inside;
  while (i < n) {
    s += i;
  inside:
    s += 2;
    i++;
  }
  return s;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm goto.c -o goto.ll
opt -passes='sroa,print<domtree>,print<cycles>' -disable-output goto.ll

Output (complete):

DominatorTree for function: g
=============================--------------------------------
Inorder Dominator Tree: 
  [1] %entry {0,7} [0]
    [2] %if.then {1,2} [1]
    [2] %inside {2,3} [1]
    [2] %while.cond {3,6} [1]
      [3] %while.body {4,5} [2]
      [3] %while.end {5,6} [2]
    [2] %if.end {6,7} [1]
Roots: %entry 
CycleInfo for function: g
    depth=1: entries(while.cond inside) while.body

What to notice: the goto makes the loop's cycle while.cond → while.body → inside → while.cond enterable at two blocks, and print<cycles> lists both entries. Neither entry dominates the other, so both get the idom entry (from different predecessors, if.end and if.then). This is the shape of @chk_irreducible: in RPO one entry is processed before the edge from the other entry's side is known, so CHK first records a too-deep idom and needs a further pass to pull it up to entry (Proposition 15.1.23: a retreating edge that is not a back edge costs a pass).

Lengauer–Tarjan¶

GCC 15 gcc/dominance.cc — dom_info::calc_idoms with dom_info::eval, dom_info::compress and dom_info::link_roots: the header comment says it uses "tree balancing and path compression, so it's the O(e*a(e,v)) variant". The same code computes post-dominators (direction CDI_POST_DOMINATORS) [GCC-Dominance].
HotSpot C2 (JDK 25) src/hotspot/share/opto/domgraph.cpp — PhaseCFG::build_dominator_tree and struct Tarjan with _label, _ancestor, _child and _size: the sophisticated LINK/EVAL [HotSpot-Dom].
Go 1.25 dom.go — dominatorsLTOrig, evalOrig, linkOrig: the simple version, with a comment that it follows the "original Tarjan-Lengauer TOPLAS article" [Go-Dom].

The running example from C: sdom(H) = C, idom(H) = B

Reproduce (clang 23.1.2, opt 23.1.2; simplifycfg only removes the empty blocks clang emits for each goto, and merges G into its only predecessor F):

cat > running.c <<'EOF'
void work(int);
void running(int *c) {
B:  if (c[0]) goto C; goto E;
C:  if (c[1]) goto D; goto H;
D:  work(4); goto E;
E:  if (c[2]) goto F; goto H;
F:  work(6); goto G;
G:  if (c[3]) goto H; goto E;
H:  if (c[4]) goto I; goto B;
I:  return;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm running.c -o running.ll
opt -passes='simplifycfg,print<domtree>' -disable-output running.ll

Output (complete):

DominatorTree for function: running
=============================--------------------------------
Inorder Dominator Tree: DFSNumbers invalid: 0 slow queries.
  [1] %entry {4294967295,4294967295} [0]
    [2] %B {4294967295,4294967295} [1]
      [3] %C {4294967295,4294967295} [2]
        [4] %D {4294967295,4294967295} [3]
      [3] %E {4294967295,4294967295} [2]
        [4] %F {4294967295,4294967295} [3]
      [3] %H {4294967295,4294967295} [2]
        [4] %I {4294967295,4294967295} [3]
Roots: %entry

What to notice: this is the lesson's running example with F and G fused into one block F. With successors in listed order, the DFS numbers are entry 1, B 2, C 3, D 4, E 5, F 6, H 7, I 8, and every predecessor of H (C, E, F) has a smaller number, so \(\mathrm{sdom}(H) = C\) (Definition 15.1.13). LLVM prints \(\mathrm{idom}(H) = B\): exactly the second case of Corollary 15.1.16, with \(u = E\) and \(\mathrm{sdom}(E) = B\). "DFSNumbers invalid" means no query has needed the {in,out} numbers yet; LLVM computes them lazily (DominatorTreeBase::updateDFSNumbers) [LLVM-GDT].

Semi-NCA¶

LLVM

llvm/include/llvm/Support/GenericDomTreeConstruction.h — SemiNCAInfo::runSemiNCA (phase 1 over ReverseChildren, then the NCA climb), SemiNCAInfo::eval (path compression, no balancing), SemiNCAInfo::runDFS (iterative, successors reversed so the stack visits them in order), CalculateFromScratch. llvm/lib/IR/Dominators.cpp instantiates it for BasicBlock, llvm/lib/CodeGen/MachineDominators.cpp for MachineBasicBlock (LLVM 23.1.2) [LLVM-GDTC]. Phase 2 is, verbatim (excerpt from runSemiNCA):

// Step #2: Explicitly define the immediate dominator of each vertex.
//          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
// SDom[i]'s DFS number is just Semi.
for (unsigned i = 1; i < NextDFSNum; ++i) {
  auto &WInfo = *NumToInfo[i];
  unsigned WIDom = IDoms[i];
  while (WIDom > WInfo.Semi)
    WIDom = IDoms[WIDom];
  IDoms[i] = WIDom;
  WInfo.IDom = NumToNode[WIDom];
}

Differences from the textbook: node numbers come from a DFS that is itself generic over graph traits, the virtual root handles post-dominators, and the DFS can be restricted by a predicate (DescendCondition) so the same code rebuilds subtrees.

rustc 1.90 compiler/rustc_data_structures/src/graph/dominators/mod.rs — dominators: the header cites Georgiadis's thesis; the loop comments explain semidominators and the NCA step [Rustc-Dom].
Cranelift (Wasmtime 36) cranelift/codegen/src/dominator_tree.rs — DominatorTree::compute ("using Semi-NCA algorithm… The same algorithm is used by Julia, SpiderMonkey and LLVM") [Cranelift-Dom].
WebKit WTF/Dominators.h — Dominators uses SemiNCA up to maxNodesForSemiNCADominance = 20000 [WebKit-Dom].
Swift 6, MLIR: lib/SIL/Utils/Dominance.cpp (DominanceInfo derives from llvm::DominatorTreeBase<SILBasicBlock>) and mlir/lib/IR/Dominance.cpp reuse LLVM's template, so they run Semi-NCA too.

One Semi-NCA run, shared by every client

Reproduce (clang 23.1.2, opt 23.1.2):

cat > running.c <<'EOF'
void work(int);
void running(int *c) {
B:  if (c[0]) goto C; goto E;
C:  if (c[1]) goto D; goto H;
D:  work(4); goto E;
E:  if (c[2]) goto F; goto H;
F:  work(6); goto G;
G:  if (c[3]) goto H; goto E;
H:  if (c[4]) goto I; goto B;
I:  return;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm running.c -o running.ll
opt -passes='simplifycfg,print<domtree>,print<loops>' -debug-pass-manager \
    -disable-output running.ll 2>&1 | grep -E '^Running|^  +\[|Loop at'

Output (complete, filtered by the grep):

Running analysis: InnerAnalysisManagerProxy<AnalysisManager<Function>, Module> on [module]
Running pass: SimplifyCFGPass on running (43 instructions)
Running analysis: TargetIRAnalysis on running
Running analysis: AssumptionAnalysis on running
Running pass: DominatorTreePrinterPass on running (32 instructions)
Running analysis: DominatorTreeAnalysis on running
  [1] %entry {4294967295,4294967295} [0]
    [2] %B {4294967295,4294967295} [1]
      [3] %C {4294967295,4294967295} [2]
        [4] %D {4294967295,4294967295} [3]
      [3] %E {4294967295,4294967295} [2]
        [4] %F {4294967295,4294967295} [3]
      [3] %H {4294967295,4294967295} [2]
        [4] %I {4294967295,4294967295} [3]
Running pass: LoopPrinterPass on running (32 instructions)
Running analysis: LoopAnalysis on running
Loop at depth 1 containing: %B<header>,%C,%D,%E,%F,%H<latch><exiting>
    Loop at depth 2 containing: %E<header><exiting>,%F<latch><exiting>
Running pass: VerifierPass on [module]
Running analysis: VerifierAnalysis on [module]

What to notice: DominatorTreeAnalysis runs once (that run is CalculateFromScratch → runDFS → runSemiNCA), and LoopAnalysis reuses the cached tree instead of recomputing it: the analysis manager hands the same Semi-NCA result to every client until a pass invalidates it. The loop forest is read off the tree: B and E are headers because they dominate their latches H and F (Lesson 15.5).

Find where LLVM does it. Open llvm/include/llvm/Support/GenericDomTreeConstruction.h at tag llvmorg-23.1.2. Find the member function of SemiNCAInfo that performs both phases (the semidominator loop and the loop commented "Explicitly define the immediate dominator of each vertex"). Question: what is its name, and what does the inner while loop of phase 2 compare WIDom with? (Quiz llvm-where-seminca.) While you are there, read the comment above SemiNCAInfo::eval: it states the bound path compression alone gives and why LLVM does not implement balanced linking.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use	Irreducible CFGs
Iterative bit vectors	exact Dom sets	O((d+2)·m·n/w) with w-bit words · slow above a few thousand nodes (n² bits)	full Dom sets, easy to inspect	~30 lines	teaching, verification oracles (WebKit `NaiveDominators`)	yes, more passes
Cooper–Harvey–Kennedy	exact idoms	O((d+2)·m·h) · fast on small CFGs; lab: 1.9 ms at 10 000 blocks, 609 ms on a 20 000-block comb	idoms only; pass count shows irreducibility	~40 lines	small graphs: GCC's incremental fix-up, Cranelift's baseline, Pebble's analysis	yes, more passes
Lengauer–Tarjan (simple / sophisticated)	exact idoms and semidominators	O(m log n) / O(m α(m,n)) · robust; lab: 1.05 ms at 10 000, 0.8 ms on the 20 000-block ladder	idoms; sdom as a by-product	~120 lines, subtle	GCC, Go, HotSpot, WebKit (large graphs)	yes, no extra cost
Semi-NCA	exact idoms	O(n²) worst, near-linear in practice · lab: fastest on random CFGs (0.85 ms at 10 000), 94 ms on the ladder	idoms; a partial tree usable for updates	~70 lines	LLVM, rustc, Cranelift, WebKit	yes

Choose iterative dataflow when you need an oracle, the region is tiny, or you want full Dom sets for teaching or debugging. Choose CHK when you want the simplest fast algorithm, graphs are the size of normal functions, and you control the inputs (a JIT, a teaching compiler, Pebble). Choose Lengauer–Tarjan when inputs can be huge or adversarial (machine-generated code, fuzzers, whole-program graphs): it is the only one of the four without a quadratic case. Choose Semi-NCA when you want the best typical speed and plan to update trees incrementally, as LLVM does; guard the worst case (WebKit's switch to LT, or LLVM's willingness to accept it).

Measured by the comparison lab on this course's reference machine (build/<preset>/bin/ch15-dombench --reps 5, LLVM 23.1.2, milliseconds, median of 5, DFS included):

shape	blocks	edges	CHK passes	iterative	chk	lt	lt-bal	semi-nca	llvm
random	1000	1399	4	0.24	0.09	0.08	0.08	0.06	0.07
random	10000	13990	5	-	1.87	1.05	1.12	0.85	1.84
random	100000	140116	5	-	56.08	15.16	15.10	13.90	26.72
ladder	1000	1498	2	2.15	0.43	0.03	0.03	0.25	0.22
ladder	5000	7498	2	-	9.86	0.16	0.18	6.19	5.14
ladder	20000	29998	2	-	159.42	0.79	0.78	93.99	80.08
comb	1000	1997	2	8.41	1.55	0.03	0.03	0.02	0.03
comb	5000	9997	2	-	37.89	0.17	0.17	0.12	0.19
comb	20000	39997	2	-	608.68	0.82	0.79	0.58	1.22
bichain	250	498	249	0.80	0.26	0.01	0.01	0.01	0.01
bichain	500	998	499	3.57	0.97	0.02	0.02	0.01	0.01
bichain	1000	1998	999	17.21	4.30	0.03	0.03	0.02	0.03

Read it this way. On random CFGs the three near-linear algorithms are within 2× of each other and Semi-NCA wins; CHK's extra passes (4–5, because the random back edges make the graphs irreducible) cost it a factor 4 at 100 000 blocks. The ladder grows CHK, Semi-NCA and LLVM quadratically (4× the blocks, 16× the time; Proposition 15.1.31(a)), while LT grows linearly. The comb hurts only CHK (Proposition 15.1.31(b)). The bichain shows the pass count: CHK needs a pass per node (Proposition 15.1.31(c)). Your numbers will differ; the shapes of the curves will not.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch15.yaml`)	Drill	Flashcard tag	Exercises
Iterative dataflow	`dom-definitions`, `iterative-passes`	`./course drill dominators --solution` (step 2)	`iterative-dom`	E2
Cooper–Harvey–Kennedy	`dom-definitions`, `iterative-passes`, `chk-intersect-walk`	`./course drill dominators`	`chk`	E3
Lengauer–Tarjan	`lt-semidominators`, `lt-sdom-vs-idom`, `dom-definitions`, `llvm-where-seminca`	`./course drill lengauer-tarjan`	`lengauer-tarjan`	E4, E5 ★
Semi-NCA	`lt-semidominators`, `lt-sdom-vs-idom`, `dom-definitions`, `llvm-where-seminca`	`./course drill lengauer-tarjan --solution` (the Semi-NCA cross-check)	`semi-nca`	E6 ★
The dominator tree itself	`dom-definitions`, `iterative-passes`, `lt-sdom-vs-idom`	`./course drill dominators`	`dominators`	E7

A semidominator is not a dominator

sdom(H) = C in the running example, yet the path A → B → E → H avoids C. The semidominator is only a candidate on the DFS-tree path; Lengauer–Tarjan's corollary (Corollary 15.1.16) and Semi-NCA's NCA step (Lemma 15.1.18) are what turn it into idom(H) = B.

Unreachable blocks

LLVM's DominatorTree::dominates(A, B) is true for an unreachable B (every block dominates an unreachable block), and properlyDominates(A, B) on blocks is true too unless A = B, while the DomTreeNode overloads return false for a null node. Code that asks "does the definition dominate the use?" in unreachable code gets "yes": that is intentional, and the provided DomTree reproduces it.

References¶

See the chapter references.

Lesson 15.1 — Dominator algorithms¶

1. Problem and motivation¶

Iterative dataflow¶

Cooper–Harvey–Kennedy¶

Lengauer–Tarjan¶

Semi-NCA¶

2. Definitions and algorithms¶

Iterative dataflow¶

Cooper–Harvey–Kennedy¶

Lengauer–Tarjan¶

Semi-NCA¶

3. Worked example¶

Iterative dataflow on the running example¶

Cooper–Harvey–Kennedy on the running example¶

Lengauer–Tarjan on the running example¶

Semi-NCA on the running example¶

4. Invariants and correctness¶

Iterative dataflow¶

Cooper–Harvey–Kennedy¶

Lengauer–Tarjan¶

Semi-NCA¶

5. Complexity¶

6. Variants and refinements¶

Iterative dataflow¶

Cooper–Harvey–Kennedy¶

Lengauer–Tarjan¶

Semi-NCA¶

7. In real compilers¶

Iterative dataflow¶

Cooper–Harvey–Kennedy¶

Lengauer–Tarjan¶

Semi-NCA¶

8. Comparison¶

9. Assessment¶

References¶