Lesson 15.4 — Post-dominance and control dependence

Techniques: post-dominator trees on the reverse CFG with a virtual exit (including LLVM's roots for infinite loops), control dependence (Ferrante–Ottenstein–Warren walk; Cytron's reverse dominance frontier) · Pebble implements: both (E11, E12); LLVM's root selection is provided (pebble/lib/Analysis/Dominance/provided/PostDomRoots.cpp) · Lab: your post-dominator tree vs llvm::PostDominatorTree; control dependence vs its definition evaluated with LLVM's tree · Prerequisites: Lesson 15.1, Lesson 15.3 · Time: 3–4 hours

In the running example, every path from B to the exit passes through H, and every path from F passes through G and then H. H post-dominates B: whatever B decides, H will run. By contrast, D runs only if C branches to D, and C runs only if B branches to C. D is control dependent on C, and C on B. Dead-code elimination uses exactly this: a branch is live only if something live is control dependent on it.

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

1. Problem and motivation

The problem. Compute (a) the immediate post-dominator \(\mathrm{ipdom}(n)\) of every block: the first block that every path from \(n\) to the function's exit must pass through; and (b) for every block \(Y\), the set \(\mathrm{CD}(Y)\) of branches \(X\) that decide whether \(Y\) runs (control dependence). LLVM's PostDominatorTree feeds adce (aggressive dead code elimination), SimplifyCFG's sinking, GPU divergence analysis and pebblec's dead-branch removal in Ch 17; control dependence is the backbone of program slicing and of the program dependence graph.

Post-dominance is as old as dominance: the FORTRAN H optimizer already computed "postdominators" by running its dominator code backwards [LM69]. The subtle part is the exit: a function may have several returns, unreachable terminators, or infinite loops that never reach an exit. Every compiler adds a virtual exit node joined to all real exits; LLVM additionally picks one node inside each infinite loop to connect, with a specific heuristic you need to reproduce if you want to match it [LLVM-GDTC].

Post-dominator trees

Post-dominance in \(G\) is dominance in the reverse graph, rooted at the virtual exit (Proposition 15.4.3). Any dominator algorithm from Lesson 15.1 works unchanged; the only new decisions are which nodes the virtual exit connects to (the roots) and how to handle nodes that cannot reach any exit. Pebble reuses your CHK (your computePostDominators, E11).

Control dependence

Ferrante, Ottenstein and Warren defined control dependence to build the program dependence graph (PDG), a representation where data and control dependences are edges of one graph, and gave an algorithm that walks the post-dominator tree once per CFG edge [FOW87]. Cytron et al. then showed that control dependence is the dominance frontier of the reverse CFG, so any frontier algorithm computes it [CFRWZ91, §6]. Pebble implements the FOW walk (your computeControlDependence, E12); the tests check it against the definition.

2. Definitions and algorithms

\(G = (N, E, r)\). An exit is a node without successors.

Definition 15.4.1 (Roots, virtual exit, augmented reverse graph)

A set of roots \(R \subseteq N\) is a set such that every node reaches some root, and every exit is a root. (If some node reaches no exit, \(R\) must also contain a node of each such region.) Let \(\hat{x} \notin N\) be a fresh virtual exit. The augmented reverse graph \(G^{R}_{\hat{x}}\) has nodes \(N \cup \{\hat{x}\}\), an edge \(v \to u\) for every edge \(u \to v\) of \(G\), and an edge \(\hat{x} \to \rho\) for every \(\rho \in R\); its entry is \(\hat{x}\).

Definition 15.4.2 (Post-dominance)

\(p\) post-dominates \(n\), written \(p \mathrel{\mathrm{pdom}} n\), if \(p\) dominates \(n\) in \(G^{R}_{\hat{x}}\), i.e. every path from \(n\) to \(\hat{x}\) in the forward augmented graph (\(G\) plus \(\rho \to \hat{x}\) for each root) contains \(p\). \(\mathrm{ipdom}(n)\) is the immediate dominator of \(n\) in \(G^{R}_{\hat{x}}\); it is \(\hat{x}\) for nodes whose only strict post-dominator is \(\hat{x}\). \(p\) strictly post-dominates \(n\) if \(p \mathrel{\mathrm{pdom}} n\) and \(p \neq n\).

Proposition 15.4.3 (The post-dominator tree)

With roots as in Definition 15.4.1, every node of \(G^{R}_{\hat{x}}\) is reachable from \(\hat{x}\); \(\mathrel{\mathrm{pdom}}\) is a partial order on \(N \cup \{\hat{x}\}\), and the edges \(\mathrm{ipdom}(n) \to n\) form a tree rooted at \(\hat{x}\) whose ancestors of \(n\) are exactly the post-dominators of \(n\).

Proof

A node \(n\) reaches some root \(\rho\) in \(G\); the reverse of that path, preceded by \(\hat{x} \to \rho\), is a path \(\hat{x} \leadsto n\) in \(G^{R}_{\hat{x}}\). So \(G^{R}_{\hat{x}}\) is a flowgraph with every node reachable (\(\hat{x}\) has no predecessors), and Theorems 15.1.3 and 15.1.6 apply to it verbatim.

Definition 15.4.4 (Control dependence)

\(Y\) is control dependent on \(X\) [FOW87] iff (1) \(X\) has a successor \(S\) with \(Y \mathrel{\mathrm{pdom}} S\) (\(Y = S\) allowed), and (2) \(Y\) does not strictly post-dominate \(X\). \(\mathrm{CD}(Y) \triangleq \{\, X \mid Y \text{ is control dependent on } X \,\}\). Informally, \(X\) can decide whether \(Y\) runs: one successor of \(X\) leads to \(Y\) for sure, and \(X\) itself does not.

Definition 15.4.5 (Post-dominance frontier)

\(\mathrm{PDF}(Y)\) is the dominance frontier of \(Y\) in \(G^{R}_{\hat{x}}\) (Definition 15.3.1), restricted to \(N\).

Theorem 15.4.6 (Control dependence is the reverse dominance frontier)

For \(X, Y \in N\): \(Y\) is control dependent on \(X\) iff \(X \in \mathrm{PDF}(Y)\).

Proof

In \(G^{R}_{\hat{x}}\) the predecessors of \(X\) are its successors in \(G\) (plus \(\hat{x}\) if \(X\) is a root; \(\hat{x}\) is dominated in \(G^{R}_{\hat{x}}\) by no \(Y \in N\), so it never witnesses anything). By Definition 15.3.1 applied to \(G^{R}_{\hat{x}}\), \(X \in \mathrm{PDF}(Y)\) iff \(Y\) dominates some predecessor \(S\) of \(X\) there, i.e. \(Y \mathrel{\mathrm{pdom}} S\) for a successor \(S\) of \(X\) in \(G\), and \(Y\) does not strictly dominate \(X\) there, i.e. does not strictly post-dominate \(X\). That is Definition 15.4.4 word for word.

LLVM's roots. LLVM picks \(R\) with the following procedure, replayed by the provided findPostDomRoots and by the Python oracle llvm_postdom_roots:

Algorithm 15.4.7 (LLVM's post-dominator roots)

• Input: \(G\) and its block order.
• Output: a list of roots \(R\).
• Precondition: none (unreachable blocks, infinite loops and several exits allowed).
• Postcondition: \(R\) satisfies Definition 15.4.1, contains every exit, and no non-exit root reaches another root.
• Invariant: after step 1 the marked nodes are exactly those that reach an exit; after each step-2 iteration every marked node reaches a root; step 3 only removes a root that reaches another current root (Theorem 15.4.11).

function FindRoots(G, blockOrder):
    roots ← []
    marked ← {}
    for n in blockOrder:                            # 1. trivial roots
        if succs(n) is empty:
            append n to roots
            ReverseMark(n)
    for n in blockOrder:                            # 2. one root per region that reaches no exit
        if n ∉ marked:
            seen ← DFS from n over unmarked nodes, pushing successors in blockOrder
                   (so the one listed last is explored first), in visit order
            f ← the last node of seen                # "FurthestAway"
            append f to roots
            ReverseMark(f)
    for each non-trivial root ρ in roots:            # 3. RemoveRedundantRoots
        if a forward DFS from ρ reaches another root:
            remove ρ (swap it with the last root, pop)
    return roots

function ReverseMark(n):
    mark n and every unmarked node that reaches n (DFS over predecessors)

Post-dominator trees

Algorithm 15.4.8 (Post-dominators via the reverse graph)

• Input: \(G\) and roots \(R\) (Algorithm 15.4.7).
• Output: \(\mathrm{ipdom}(n)\) for every \(n \in N\), as a tree over \(N \cup \{\hat{x}\}\) rooted at \(\hat{x}\).
• Precondition: \(R\) satisfies Definition 15.4.1.
• Postcondition: the returned vector is the idom vector of \(G^{R}_{\hat{x}}\) (Definition 15.4.2).
• Invariant: \(G^{R}_{\hat{x}}\) is a flowgraph in which every node is reachable (Proposition 15.4.3), so the dominator algorithm's precondition holds.

function PostDominators(G = (N, E, r), R):
    X ← a new node
    G_R ← graph with nodes N ∪ {X} and entry X
    for ρ in R: add edge X → ρ to G_R
    for each edge u → v in E: add edge v → u to G_R
    ipdom ← CHK(G_R)                                # Lesson 15.1; any dominator algorithm
    return ipdom                                    # ipdom[X] = none

You implement it as computePostDominators(G, Roots), which returns an IdomVector with \(\lvert N \rvert + 1\) entries (node \(\lvert N \rvert\) is \(\hat{x}\)) (E11).

Control dependence

Lemma 15.4.9 (Walking the post-dominator tree)

For an edge \(A \to B\) such that \(B\) does not strictly post-dominate \(A\), the nodes \(Y \in N\) with \(Y \mathrel{\mathrm{pdom}} B\) and \(\neg(Y\) strictly post-dominates \(A)\) are exactly the nodes on the post-dominator-tree path from \(B\) up to, but excluding, \(\mathrm{ipdom}(A)\).

Proof

Every path from \(B\) to \(\hat{x}\), prefixed by \(A \to B\), is a path from \(A\), so it contains \(\mathrm{ipdom}(A)\); not as its first node, since \(\mathrm{ipdom}(A) \neq A\), so on the part starting at \(B\). Hence \(\mathrm{ipdom}(A) \mathrel{\mathrm{pdom}} B\), and \(\mathrm{ipdom}(A) \neq B\) because \(B\) does not strictly post-dominate \(A\): \(\mathrm{ipdom}(A)\) is a proper ancestor of \(B\) in the post-dominator tree. A node \(Y\) on the path from \(B\) up to, excluding, \(\mathrm{ipdom}(A)\) post-dominates \(B\) (it is an ancestor-or-self), and does not strictly post-dominate \(A\): the strict post-dominators of \(A\) are \(\mathrm{ipdom}(A)\) and its ancestors (Proposition 15.4.3 and Theorem 15.1.6). Conversely, a \(Y\) that post-dominates \(B\) is an ancestor-or-self of \(B\); if it is not a strict post-dominator of \(A\) it is not \(\mathrm{ipdom}(A)\) or above, so it lies strictly below \(\mathrm{ipdom}(A)\) on \(B\)'s root path.

Algorithm 15.4.10 (Ferrante–Ottenstein–Warren control dependence)

• Input: \(G\) and its post-dominator tree.
• Output: \(\mathrm{CD}(Y)\) for every \(Y \in N\).
• Precondition: the tree was built with roots satisfying Definition 15.4.1.
• Postcondition: CD[Y] \(= \mathrm{CD}(Y)\) (Definition 15.4.4).
• Invariant: after the edges \(A \to B\) processed so far, CD[Y] contains exactly the \(A\) that some processed edge makes \(Y\) control dependent on (Lemma 15.4.9).

function ControlDependence(G, PDT):
    for Y in N: CD[Y] ← {}
    for each edge A → B in E:
        if B ≠ A and B post-dominates A: continue   # B runs anyway once A runs
        stop ← ipdom(A)
        runner ← B
        while runner ≠ stop and runner ≠ X:
            CD[runner] ← CD[runner] ∪ {A}
            runner ← ipdom(runner)
    return CD

This is [FOW87] with the edge test stated for self loops. The alternative is CytronDF (Algorithm 15.3.6) on \(G^{R}_{\hat{x}}\), then \(\mathrm{CD}(Y) = \mathrm{PDF}(Y)\) by Theorem 15.4.6. You implement it as computeControlDependence(G, PDT) (E12).

3. Worked examples

Post-dominator tree of the running example

The only exit is I, so R = {I} (LLVM's roots agree: nothing is left unmarked after step 1). The reverse graph, successors listed in the order of the original predecessors:

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

DFS from X: X I H C B A E D G F (preorder); postorder numbers A=0, B=1, C=2, D=3, F=4, G=5, E=6, H=7, I=8, X=9; RPO: X I H E G F D C B A. CHK:

pass	node	processed preds (in G_R)	intersect walks	ipdom
1	I	X	—	X
1	H	I (B not yet)	—	I
1	E	H (F not yet)	—	H
1	G	E, H	intersect(H, E): (H:7, E:6) → E moves to H ⇒ H	H
1	F	G	—	G
1	D	E	—	E
1	C	D, H	intersect(H, D): D:3 → E:6 → H:7 ⇒ H	H
1	B	C, E	intersect(E, C): C:2 → H:7; E:6 → H:7 ⇒ H	H
1	A	B	—	B
2	I, E, G, F, D, C, B, A	all	same results (H now also meets B: intersect(B, I) ⇒ I; E meets F: ⇒ H)	unchanged

Post-dominator tree (children in RPO of \(G^{R}_{\hat{x}}\)):

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

So ipdom(B) = H (whichever way B branches, H runs), ipdom(C) = H, ipdom(D) = E, ipdom(E) = H, ipdom(F) = G.

Control dependence of the running example

One row per CFG edge A → B; skipped edges are those whose target strictly post-dominates their source: A→B, D→E, F→G, G→H, E→H, C→H, H→I.

edge A→B	B strictly post-dominates A?	stop = ipdom(A)	walk from B (each node gets A in its CD set)
B → C	no	H	C
B → E	no	H	E
C → D	no	H	D, E
E → F	no	H	F, G
G → E	no	H	E
H → B	no	I	B, H

Result: CD(B) = {H}, CD(C) = {B}, CD(D) = {C}, CD(E) = {B, C, G}, CD(F) = {E}, CD(G) = {E}, CD(H) = {H}, CD(A) = CD(I) = {}. Read them as sentences: E runs if B goes right, or C goes to D, or G loops back; the loop body B … H runs again only if H branches back, so both B and H depend on H. The post-dominance frontiers computed by Cytron's algorithm on \(G^{R}_{\hat{x}}\) are the same sets (Theorem 15.4.6).

Try it

./course drill post-dominance --seed 5 --difficulty medium --solution prints both traces for a random CFG.

Which roots? Exits and infinite loops

tests/ch15/Inputs/infinite-loops.ll, function @loop_and_exit: entry → spin, exit; spin → spin2; spin2 → spin; exit returns.

step	action	roots	marked
1	exit has no successors: trivial root; mark what reaches it	exit	exit, entry
2	spin is unmarked: forward DFS over unmarked nodes: spin, spin2 (spin again: seen)
3	last visited = spin2 ("FurthestAway"): new root; mark what reaches it	exit, spin2	+ spin2, spin
4	RemoveRedundantRoots: a forward DFS from spin2 reaches spin only, not another root	exit, spin2

opt -passes='print<postdomtree>' prints Roots: %exit %spin2; ipdom(spin) = spin2, and entry, exit, spin2 hang directly below X.

The choice is a heuristic, and it can break symmetry. In @branchy_infinite (entry → top; top → left, right; left → join; right → join; join → top; no exit at all), the forward DFS from entry pushes left before right, so it explores right first and visits entry, top, right, join, left: the root becomes left. Then ipdom(top) = left and ipdom(right) = join, so CD(left) = {left} while CD(right) = {top}: two symmetric branches get different control dependences. A post-dominator tree inside an infinite loop describes one choice of "exit", not the program's semantics.

4. Invariants and correctness

Post-dominator trees

Theorem 15.4.11 (LLVM's roots are valid)

Algorithm 15.4.7 terminates, and every node reaches a root of its output.

Proof

Step 1: ReverseMark(n) marks \(n\) and every node that reaches it, so afterwards the marked nodes are exactly those reaching some exit, each of which is a root. Step 2: for an unmarked \(n\), the forward DFS visits only nodes reachable from \(n\), so the chosen \(f\) is reachable from \(n\); ReverseMark(f) then marks every unmarked node reaching \(f\), including \(n\). So after step 2 all nodes are marked, and every marked node reaches a root. Step 3: by induction on the removals — when \(\rho\) is removed it reaches a root \(\rho'\) that is current at that moment, so every node that reached \(\rho\) still reaches a current root; later removals of \(\rho'\) are handled by the same argument. Termination: step 1 and 2 mark each node once (the forward DFS of step 2 is repeated at most once per root); step 3 does one DFS per root.

Theorem 15.4.12 (Correctness of Algorithm 15.4.8)

Algorithm 15.4.8 returns the immediate post-dominators of Definition 15.4.2.

Proof

By Proposition 15.4.3, \(G^{R}_{\hat{x}}\) is a flowgraph with all nodes reachable, and by Definition 15.4.2 post-dominance is dominance in it; CHK is correct on any flowgraph (Theorem 15.1.25).

When it breaks: omitting the non-trivial roots leaves infinite-loop nodes unreachable from \(\hat{x}\), so they get no ipdom and every query about them lies; choosing different roots than LLVM gives a valid but different tree.

Control dependence

Theorem 15.4.13 (Correctness of Algorithm 15.4.10)

Algorithm 15.4.10 terminates and returns \(\mathrm{CD}(Y)\) for every \(Y\).

Proof

Fix \(X\). By Definition 15.4.4, \(X \in \mathrm{CD}(Y)\) iff some edge \(X \to S\) has \(Y \mathrel{\mathrm{pdom}} S\) and \(\neg(Y\) strictly post-dominates \(X)\). An edge \(X \to S\) whose target strictly post-dominates \(X\) contributes nothing: every \(Y\) with \(Y \mathrel{\mathrm{pdom}} S\) then strictly post-dominates \(X\) too (transitivity, and \(Y = X\) is impossible because \(S\) strictly post-dominates \(X\)). Every other edge — including a self loop \(X \to X\), whose target does not strictly post-dominate its source — contributes exactly the nodes of Lemma 15.4.9, which is the walk. The walk stops at \(\mathrm{ipdom}(X)\), a proper ancestor of \(S\) (proof of Lemma 15.4.9), or at \(\hat{x}\). Termination: each walk climbs a finite tree path.

Self loops: for A → A the walk starts at A itself and marks A (A is control dependent on its own loop branch); that is why the skip test says B ≠ A. When it breaks: skipping edges whose target non-strictly post-dominates the source drops self-dependences; walking past ipdom(A) (for instance when B strictly post-dominates A and the edge was not skipped) runs to the root and marks too much.

5. Complexity

\(n\) = nodes, \(m\) = edges, \(h\) = height of the post-dominator tree, \(\lvert \mathrm{CD} \rvert\) = total size of all control-dependence sets.

Technique	Time (worst)	Time (typical)	Space	Notes
Post-dominator tree	cost of the dominator algorithm on \(n + 1\) nodes and \(m + \lvert R \rvert\) edges	same as dominators	\(O(n + m)\)	plus \(O(n + m)\) for LLVM's root finding
Control dependence (FOW walk)	\(O(m \cdot h)\), and \(O(m + \Delta \cdot \lvert \mathrm{CD} \rvert)\) with \(\Delta\) the largest out-degree	linear in the output	\(O(\lvert \mathrm{CD} \rvert)\)	output can be \(\Theta(n^2)\)
Control dependence (Cytron RDF)	\(O(m + \lvert \mathrm{CD} \rvert)\)	linear in the output	\(O(\lvert \mathrm{CD} \rvert)\)	reuses a frontier implementation

Proposition 15.4.14 (Cost and a quadratic family)

Algorithm 15.4.10 runs in \(O(m + \Delta \cdot \lvert \mathrm{CD} \rvert)\) after the tree is built, where \(\Delta\) is the largest out-degree (2 for conditional branches). There are CFGs with \(n\) nodes and \(\lvert \mathrm{CD} \rvert = \Theta(n^2)\).

Proof

Every edge costs one skip test. A walk for the edge \(A \to B\) visits distinct nodes \(Y\), and each visit records a pair \((A, Y)\) with \(A \in \mathrm{CD}(Y)\); a pair can be recorded by at most \(\mathrm{outdeg}(A) \le \Delta\) walks (one per out-edge of \(A\)). So the walks take at most \(\Delta \cdot \lvert \mathrm{CD} \rvert\) steps. Quadratic family: reverse every edge of the nested repeat-until family of Lesson 15.3, section 5 (its exit becomes the entry and its entry the only exit). The post-dominator tree of the result is the dominator tree of the original, so by Theorem 15.4.6 \(\lvert \mathrm{CD} \rvert = \lvert \mathrm{DF} \rvert = k(k + 1) = \Theta(n^2)\).

Pingali and Bilardi's APT structure answers CD queries in time proportional to the answer instead [PB97].

At scale: LLVM's ADCE never materializes CD sets: it asks ReverseIDFCalculator for the post-dominance frontier of the live blocks only, a linear-time query per worklist round (AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences) [LLVM-ADCE].

6. Variants and refinements

Post-dominator trees

• Virtual exit only for real exits (the classic textbook) — trade-off: simple, but nodes in infinite loops have no post-dominators at all; LLVM's extra roots fix that.
• Adding fake exit edges from infinite loops (GCC's connect_infinite_loops_to_exit, in gcc/cfganal.cc) [GCC-Cfganal] — trade-off: the CFG itself is changed (fake edges) instead of choosing roots; results depend on which block gets the fake edge, just like LLVM's heuristic.
• Incremental post-dominators: deleting an edge can create a new infinite loop and thus a new root (LLVM's DeleteUnreachable post-dom branch, Lesson 15.2) — trade-off: roots must be re-minimized after updates.

Control dependence

• Control dependence on edges (label each dependence with the successor that causes it, as FOW's PDG does) — trade-off: more information (which branch direction), more space.
• Cytron's RDF formulation [CFRWZ91, §6] — trade-off: reuses frontier code; identical results (Theorem 15.4.6).
• Roman chariots / APT [PB97]: an \(O(n + m)\) data structure that answers "which nodes are control dependent on X" and "on which nodes is Y control dependent" in time proportional to the answer — trade-off: much more complex, avoids the quadratic output.
• Compact representations [CFS90]: factor control dependence regions — trade-off: smaller graphs for PDG-based tools.

7. In real compilers

Post-dominator trees

LLVM

llvm/lib/Analysis/PostDominators.cpp — PostDominatorTree, PostDominatorTreeAnalysis and print<postdomtree> [LLVM-PostDom]; the tree is DominatorTreeBase<BasicBlock, true>, built by SemiNCAInfo::CalculateFromScratch after SemiNCAInfo::FindRoots and RemoveRedundantRoots in llvm/include/llvm/Support/GenericDomTreeConstruction.h (LLVM 23.1.2) [LLVM-GDTC]. The virtual root is the tree node whose block is nullptr (printed as <<exit node>>).

• GCC 15 gcc/dominance.cc — calculate_dominance_info (CDI_POST_DOMINATORS) runs the same Lengauer–Tarjan code on the reverse CFG with GCC's EXIT_BLOCK_PTR as the root [GCC-Dominance]; gcc/cfganal.cc — connect_infinite_loops_to_exit adds fake edges first.
• MLIR mlir/lib/IR/Dominance.cpp instantiates DominatorTreeBase<Block, /*IsPostDom=*/true> for PostDominanceInfo.
• Pebble your computePostDominators (E11), print<pebble-postdomtree>.

Three kinds of roots in one C function

Reproduce (clang 23.1.2, opt 23.1.2):

cat > server.c <<'EOF'
void work(int);
void fail(void) __attribute__((noreturn));
int server(int n) {
  if (n < 0)
    fail();
  if (n == 0)
    for (;;)
      work(0);
  work(n);
  return n;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm server.c -o server.ll
opt -passes='sroa,print<postdomtree>' -disable-output server.ll

Output (complete):

PostDominatorTree for function: server
=============================--------------------------------
Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries.
  [1]  <<exit node>> {4294967295,4294967295} [0]
    [2] %if.then {4294967295,4294967295} [1]
    [2] %entry {4294967295,4294967295} [1]
    [2] %if.end3 {4294967295,4294967295} [1]
    [2] %if.end {4294967295,4294967295} [1]
    [2] %for.cond {4294967295,4294967295} [1]
      [3] %if.then2 {4294967295,4294967295} [2]
Roots: %if.then %if.end3 %for.cond 

What to notice: the virtual exit \(\hat{x}\) (<<exit node>>) has three roots (Definition 15.4.1): if.then ends in unreachable after the noreturn call and if.end3 returns — both exits, found in step 1 of Algorithm 15.4.7 — and for.cond is the infinite loop's non-trivial root, chosen in step 2 because nothing in it reaches an exit. entry and if.end hang directly below \(\hat{x}\): no single block post-dominates a branch whose arms end in different roots. if.then2 is post-dominated by the loop it enters. The {4294967295,…} numbers are LLVM's lazily computed DFS numbers, not yet valid.

Control dependence

LLVM

llvm/lib/Transforms/Scalar/ADCE.cpp — AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences: collects the blocks that became live, runs a ReverseIDFCalculator over the post-dominator tree to find their post-dominance frontier, and marks the terminators of those blocks live (LLVM 23.1.2) [LLVM-ADCE].

• GCC 15 gcc/cfganal.cc — class control_dependences with find_control_dependence, the FOW walk over edges; used by gcc/tree-ssa-dce.cc (cd = new control_dependences () in aggressive mode) [GCC-Cfganal].
• Pebble your computeControlDependence (E12), print<pebble-control-deps>.

ADCE deletes a branch nothing live depends on

Reproduce (clang 23.1.2, opt 23.1.2):

cat > cd.c <<'EOF'
int cd(int a, int b) {
  int t;
  if (a > b)
    t = a * 7;
  else
    t = b * 5;
  return a + b;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm cd.c -o cd.ll
opt -passes='sroa,adce' -debug-pass-manager -S cd.ll 2>&1 |
  grep -E '^Running (pass|analysis): (ADCE|PostDom)|^[a-z.]+:|^  (br|%add|ret)'

Output (complete, filtered by the grep):

Running pass: ADCEPass on cd (8 instructions)
Running analysis: PostDominatorTreeAnalysis on cd
entry:
  br label %if.then
if.then:                                          ; preds = %entry
  br label %if.end
if.else:                                          ; No predecessors!
  br label %if.end
if.end:                                           ; preds = %if.else, %if.then
  %add = add nsw i32 %a, %b
  ret i32 %add

What to notice: after SROA, t is computed in both arms but never used. ADCE starts from the live ret, whose block if.end post-dominates entry, so by Theorem 15.4.6 no live block is control dependent on the branch in entry (\(\mathrm{PDF}(\texttt{if.end}) = \emptyset\)). The branch stays dead and ADCE rewrites it into an unconditional branch to one of its successors (if.then), leaving if.else with no predecessors for a later simplifycfg. PostDominatorTreeAnalysis is requested by ADCE itself.

Find where LLVM does it. Open llvm/lib/Transforms/Scalar/ADCE.cpp (LLVM 23.1.2) and read markLiveBranchesFromControlDependences. Question: which class does it instantiate to compute post-dominance frontiers? (Quiz llvm-where-cd.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Post-dominator tree (virtual exit)	exact given the roots; infinite loops need a root choice	same as the dominator algorithm used	ipdom; roots tell where exits are	small on top of a dominator algorithm	LLVM PostDominatorTree, GCC CDI_POST_DOMINATORS
Control dependence (FOW / RDF)	exact CD relation	O(m · h) walk, or DF on the reverse CFG	CD sets per node or per edge	~20 lines	ADCE, program slicing, PDG, if-conversion

Choose a post-dominator tree when you need "must run after" facts: sinking code, proving that a block always reaches a cleanup, divergence analysis. Match LLVM's roots when you compare against LLVM or feed LLVM passes. Choose the FOW walk when you want explicit CD sets for a PDG or slicer; choose PDF queries (RDF with an IDF calculator) when you only need the control dependences of a changing set of live blocks, as ADCE does.

The oracle tests check your post-dominator trees against llvm::PostDominatorTree (roots included) and your CD sets against the definition evaluated with LLVM's tree, on the corpus (including infinite-loops.ll) and 1 650 random CFGs (ch15.PostDominators.*, ch15.ControlDependence.*).

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch15.yaml)	Drill	Flashcard tag	Exercises
Post-dominator trees	ipdom-trace, cd-sets, llvm-where-cd	./course drill post-dominance (hard: infinite loops)	post-dominance	E11
Control dependence	cd-sets, llvm-where-cd	./course drill post-dominance --difficulty medium	control-dependence	E12

Post-dominance is not dominance read backwards on the same tree

ipdom(n) is not "the successor of n that dominates the rest". In the running example ipdom(C) = H although C's other successor D does not reach H through C's subtree; and inside infinite loops the answer depends on which root was chosen (@branchy_infinite above).

References

See the chapter references.