Chapter 15 · Control-Flow Analysis: Dominance & Loops¶
Part 3 · Analysis Foundations & SSA · about 2–3 weeks · Previous: Ch 14 · Next: Ch 16
The problem¶
You are given a control-flow graph (CFG) \(G = (N, E, r)\): the basic blocks of one function, an edge for every possible jump, and one entry block without predecessors. You want its shape, in the form every later optimization consumes. Which blocks must run before which (dominance: \(d \mathrel{\mathrm{dom}} n\) if every path from \(r\) to \(n\) contains \(d\))? Where do paths from different definitions meet (dominance frontiers, and iterated frontiers for a set of blocks)? Which blocks run on every path to the exit (post-dominance), and which branches decide whether a block runs (control dependence)? Where are the loops, how do they nest, and are they well behaved (natural loops, loop nesting forests, reducibility)? Finally, how do you put loops into a canonical shape that loop optimizations can rely on (preheaders, single latches, dedicated exits, loop-closed SSA)? The outputs are a dominator tree with O(1) queries, a post-dominator tree with a virtual exit, frontier sets, control-dependence sets, and a loop forest. In LLVM they are the analyses DominatorTree, PostDominatorTree, DominanceFrontier/IDFCalculator, LoopInfo and CycleInfo, recomputed or incrementally updated between passes. In pebblec they run after lowering to LLVM IR and before SSA construction (Ch 16), loop optimizations (Ch 18) and dead-code elimination (Ch 17).
What you will be able to do¶
- Trace iterative dominators, Cooper–Harvey–Kennedy (every
intersectfinger walk) and Lengauer–Tarjan (every EVAL, LINK and bucket) by hand on a 10-node CFG, and get the same dominator tree three ways. - Prove the dominator tree theorem and explain why CHK needs reverse postorder, why a semidominator is not always the immediate dominator, and why the post-dominator tree needs a virtual exit.
- Compute dominance frontiers bottom-up (Cytron) and with runners (CHK), the iterated frontier of a set of blocks (worklist and DJ graph), and control dependences from the post-dominator tree.
- Find back edges, natural loops and their nesting; decide reducibility with T1/T2; build Havlak's forest for an irreducible CFG and say what LLVM's
LoopInfoandCycleInfoeach report. - Implement all of the above behind the nine-function contract
pebble/include/pebble/Analysis/Dominance.h(your code inpebble/lib/Analysis/Dominance/src/, the shared analysis library later chapters reuse), check it against LLVM on thousands of random CFGs, and run it insideoptasprint<pebble-domtree>and friends. - Choose between CHK, Lengauer–Tarjan and Semi-NCA for a given compiler with measured numbers, and explain the quadratic worst cases of CHK and Semi-NCA.
- Find where LLVM 23 builds dominator trees, updates them incrementally, places phis with
IDFCalculator, discovers loops, and enforces loop-simplify form and LCSSA.
Prerequisites: Ch 8 (CFGs, basic blocks, DFS preorder/postorder and reverse postorder), Ch 12 (new-pass-manager analyses, plugins, lit + FileCheck) and Ch 14 (monotone frameworks, round-robin iteration in RPO, lattice height).
Notation¶
Shared notation follows the house notation: §1 (sets, functions, logic), §3 (graphs and CFGs) and §4 (dominance and loops). Orientation: dominator sets form a lattice ordered by \(\subseteq\) in which the answer is the greatest fixed point: the iteration starts at \(\top = N_r\) and sets only shrink (the dual of the may-analyses of Ch 14). In this chapter:
| Symbol | Meaning |
|---|---|
| \(G = (N, E, r)\) | a flowgraph: nodes (basic blocks), edges, entry \(r\) without predecessors (Definition 15.1.1) |
| \(n = \lvert N \rvert\), \(m = \lvert E \rvert\) | numbers of nodes and edges (lessons use \(m\) for edges; NOTATION.md's \(e\) is the same) |
| \(N_r\) | the nodes reachable from \(r\) |
| \(\mathrm{preds}(n)\), \(\mathrm{succs}(n)\) | predecessors, successors, in listed order |
| \(u \to v\), \(u \leadsto v\) | an edge; a path (possibly empty) |
| \(d \mathrel{\mathrm{dom}} n\), \(d \mathrel{\mathrm{sdom}} n\) | dominance, strict dominance (Definition 15.1.2) |
| \(\mathrm{Dom}(n)\) | the set of dominators of \(n\) |
| \(\mathrm{idom}(n)\) | immediate dominator (Definition 15.1.5) |
| \(\mathcal{D}\), \(\mathrm{level}(x)\), \(\mathrm{depth}(x)\) | the dominator tree and the depth of \(x\) in it (Theorem 15.1.6) |
| \(\mathrm{NCA}(a, b)\) | nearest common ancestor in a tree (in \(\mathcal{D}\) unless stated) |
| \(\mathrm{in}(x)\), \(\mathrm{out}(x)\) | DFS entry/exit numbers of the dominator tree (Corollary 15.1.7) |
| \(T\), \(\mathrm{parent}(w)\), \(u \preceq_T v\), \(u \prec_T v\) | DFS spanning tree, tree parent, ancestor-or-self, proper ancestor (Definition 15.1.9) |
| \(\mathrm{pre}(v)\), \(\mathrm{post}(v)\), \(\mathrm{rpo}(v)\) | DFS preorder, postorder and reverse-postorder numbers |
| \(\mathrm{sdom}(w)\) | the semidominator function of Lengauer–Tarjan (Definition 15.1.13), not the relation \(\mathrel{\mathrm{sdom}}\) |
| \(d(G)\) | loop connectedness: the most retreating edges on any cycle-free path |
| \(h\) | height of the dominator (or post-dominator) tree |
| \(\alpha(m, n)\) | inverse Ackermann function |
| \(\mathrm{DF}(X)\), \(\mathrm{DF}(S)\), \(\mathrm{DF}^{+}(S)\) | dominance frontier, of a set, iterated (Definitions 15.3.1–15.3.2) |
| \(\mathrm{DF}_{\mathrm{local}}\), \(\mathrm{DF}_{\mathrm{up}}\) | Cytron's local and up frontiers (Definition 15.3.3) |
| \(J(S)\), \(J^{+}(S)\) | join set and iterated join set (Definition 15.3.9) |
| \(\hat{x}\), \(R\), \(G^{R}_{\hat{x}}\) | virtual exit, post-dominator roots, augmented reverse graph (Definition 15.4.1) |
| \(p \mathrel{\mathrm{pdom}} n\), \(\mathrm{ipdom}(n)\) | post-dominance, immediate post-dominator (Definition 15.4.2) |
| \(\mathrm{CD}(Y)\), \(\mathrm{PDF}(Y)\) | control dependences of \(Y\), post-dominance frontier (Definitions 15.4.4–15.4.5) |
| \(\mathrm{body}(h)\), \(\mathrm{loop}(t \to h)\) | natural loop of a header, of one back edge (Definition 15.5.4) |
| T1, T2 | Hecht–Ullman reduction rules (Definition 15.6.1) |
| \(I(h)\), \(I(G)\) | interval with header \(h\), derived graph (Definition 15.6.5) |
Numbered statements are N.k.m (chapter, lesson, counter), as in NOTATION.md §9.
Technique map¶
| Family | Techniques (origin) | Lesson |
|---|---|---|
| Dominator algorithms | Iterative dataflow with bit vectors (Prosser 1959; Lowry & Medlock 1969; Allen & Cocke 1972), Cooper–Harvey–Kennedy (2001), Lengauer–Tarjan with simple and sophisticated linking (1979), Semi-NCA (Georgiadis 2005) | 15.1 |
| Incremental dominators | Edge insertion by depth-based search (Georgiadis, Italiano, Laura & Santaroni 2016, after Ramalingam & Reps 1994), edge deletion by subtree rebuild (Georgiadis et al. 2016), batched updates with DomTreeUpdater (LLVM, 2017–2018) |
15.2 |
| Dominance frontiers | Cytron's bottom-up DF (Cytron, Ferrante, Rosen, Wegman & Zadeck 1991), CHK's per-join runners (Cooper, Harvey & Kennedy 2001), iterated DF by worklist (Cytron et al. 1991), DJ graphs and linear-time DF⁺ (Sreedhar & Gao 1995) | 15.3 |
| Post-dominance and control dependence | Post-dominator trees on the reverse CFG with a virtual exit (Lowry & Medlock 1969; LLVM root selection), control dependence (Ferrante, Ottenstein & Warren 1987; Cytron et al. 1991) | 15.4 |
| Loop nesting forests | DFS edge classification (Tarjan 1972), natural loops and LoopInfo (Lowry & Medlock 1969; Allen 1970), Tarjan's loop nesting (Tarjan 1974), Havlak's forest for irreducible loops (Havlak 1997; Ramalingam 1999), Steensgaard's forest (Steensgaard 1993) |
15.5 |
| Reducibility | T1/T2 reduction (Hecht & Ullman 1972), interval derived sequences (Allen 1970; Allen & Cocke 1976), DFS back-edge characterization (Hecht & Ullman 1974; Tarjan 1974), node splitting (Cocke & Miller 1969; Janssen & Corporaal 1997) | 15.6 |
| Canonical loop forms | Loop-simplify form: preheader, single latch, dedicated exits (Lowry & Medlock 1969; LLVM LoopSimplify), loop-closed SSA (GCC tree-SSA loop optimizer; LLVM LCSSA) |
15.7 |
flowchart LR
IT[Iterative Dom sets<br/>Prosser 1959, Lowry-Medlock 1969] -->|same fixed point, sets as tree paths| CHK[Cooper-Harvey-Kennedy 2001]
IT -->|semidominators, near-linear| LT[Lengauer-Tarjan 1979<br/>simple / sophisticated LINK]
LT -->|keep semidominators, NCA instead of buckets| SNCA[Semi-NCA<br/>Georgiadis 2005]
SNCA -->|local rebuilds| INC[Incremental: DBS insert,<br/>subtree delete 2016]
RR[Ramalingam-Reps 1994] -->|insertion lemma| INC
CHK -->|runners| CHKDF[CHK frontiers]
DT[Dominator tree] --> CYDF[Cytron DF 1991] -->|worklist| IDF[Iterated DF]
DT --> DJ[DJ graph<br/>Sreedhar-Gao 1995] -->|linear DF+| IDF
DT -->|reverse CFG + virtual exit| PDT[Post-dominators] -->|reverse DF| CD[Control dependence<br/>FOW 1987]
DT -->|head dominates tail| NL[Natural loops]
DFS[DFS edge kinds<br/>Tarjan 1972] --> TL[Tarjan loop nesting 1974] -->|irreducible entries| HV[Havlak 1997<br/>Ramalingam 1999]
DFS --> RED[Reducibility tests]
T12[T1/T2 1972] --- RED
INT[Intervals 1970] --- RED
RED -->|if irreducible| NS[Node splitting]
SCC[SCCs] --> ST[Steensgaard 1993]
NL --> LS[Loop-simplify form] --> LCSSA[LCSSA]Who uses what¶
| System | Technique | Notes |
|---|---|---|
| LLVM 23 | Semi-NCA (full build), DBS insertion and subtree-rebuild deletion (updates), DomTreeUpdater batching; Cytron DF; Sreedhar–Gao DF⁺ (IDFCalculator); natural loops (LoopInfo) plus a Havlak-style cycle forest (CycleInfo); LoopSimplify, LCSSA |
llvm/include/llvm/Support/GenericDomTreeConstruction.h; lessons 15.1–15.7 |
| GCC 15 | Lengauer–Tarjan with path compression and balancing (dominance.cc); CHK to fix up small block sets after CFG changes; CHK runners for DF; worklist DF⁺; natural loops (flow_loops_find), SCC-based irreducible-region marking; loop-closed SSA |
15.1, 15.3, 15.5 |
Go 1.25 (cmd/compile) |
Lengauer–Tarjan, simple LINK/EVAL (dominatorsLTOrig); CHK kept as dominatorsSimple; Sreedhar–Gao phi placement for functions with ≥ 500 blocks (ssagen/phi.go); dominator-based loop nest with irreducible detection (loopnestfor) |
15.1, 15.3, 15.5 |
| rustc 1.90 | Semi-NCA following Georgiadis's thesis (rustc_data_structures::graph::dominators) |
15.1 |
| Cranelift (Wasmtime 36) | Semi-NCA dominator tree (CHK kept as the verification baseline); natural loops from back edges (LoopAnalysis) |
15.1, 15.5 |
| HotSpot C2 (JDK 25) | Lengauer–Tarjan with the sophisticated LINK (domgraph.cpp); loop tree with explicit irreducible-loop flags (loopnode.cpp) |
15.1, 15.5 |
| WebKit (B3, DFG) | Semi-NCA below 20 000 blocks, Lengauer–Tarjan above; naive iterative dominators as a self-check (WTF/Dominators.h) |
15.1 |
| V8 TurboFan | Loop-aware "special RPO" that keeps loops contiguous; dominators by common-dominator walks (scheduler.cc) |
15.5 |
| Swift 6, MLIR | Reuse LLVM's DominatorTreeBase templates for SIL and for MLIR regions |
15.1 |
Comparison¶
The fixed columns follow docs/authoring/DEPTH_CONTRACT.md §3 item 8; every lesson repeats its own rows. n = nodes, m = edges, h = dominator-tree height, d = loop connectedness (the most back edges on any acyclic path), α = inverse Ackermann.
Dominator algorithms (lesson 15.1)
| 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 |
Incremental dominators (lesson 15.2)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| DBS edge insertion | exact; only affected nodes change | O(m) worst per insertion, usually a few nodes | the affected set, all re-parented to one NCA | ~60 lines | LLVM InsertReachable |
| Subtree-rebuild deletion | exact | Semi-NCA on the subtree of NCA(u, v); whole tree if that is the root | rebuilt subtree | ~80 lines + support test | LLVM DeleteReachable/DeleteUnreachable |
Batched updates (DomTreeUpdater) |
exact once flushed | lazy: one flush per batch; recompute when updates > n/40 (n > 100) | tree valid only after flush() |
API discipline | every CFG-changing LLVM transform |
Dominance frontiers (lesson 15.3)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Cytron DF | all DF sets | O(n + Σ|DF|) but Θ(n²) output on nested repeat-until loops · fast | explicit sets for every node | ~30 lines | LLVM DominanceFrontier, classic SSA |
| CHK runners | all DF sets | same bound; touches only join nodes · fastest in practice | same sets | ~15 lines | GCC compute_dominance_frontiers |
| Iterated DF worklist | DF⁺ of any set | O(Σ|DF|) after DF · needs all DF sets | phi blocks | ~15 lines | GCC compute_idf, Cytron SSA |
| DJ graph / Sreedhar–Gao | DF⁺ without DF sets | O(n + m) per query · no quadratic DF | phi blocks, deterministic order | ~50 lines | LLVM IDFCalculator (mem2reg, ADCE), Go (≥ 500 blocks) |
Post-dominance and control dependence (lesson 15.4)
| 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 |
Loop nesting forests (lesson 15.5)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use | Irreducible CFGs |
|---|---|---|---|---|---|---|
| DFS edge classification | classifies every edge | O(n + m) | tree/back/forward/cross per edge; back edges depend on the DFS | ~40 lines | every loop and SCC algorithm | back edges ≠ loops |
Natural loops (LoopInfo) |
reducible loops only | O(n + m) after dominators | header, latches, body, nesting | ~60 lines | LLVM, GCC, Cranelift loop optimizers | ignored |
| Tarjan loop nesting | reducible graphs; stops on irreducible | O(m α(m,n)) | forest + reducibility verdict | ~70 lines | reducibility test, structural analysis | detected, not handled |
| Havlak | all cycles; header = first DFS entry | O(m α(m,n)) with Ramalingam's fix | forest with irreducible flags and entries | ~90 lines | LLVM CycleInfo, GPU divergence analysis |
yes |
| Steensgaard | all cycles; all entries are headers | O(n·m) worst (nested SCCs) | forest with header sets | ~50 lines with an SCC routine | GCC irreducible marking (SCC-based) | yes |
Reducibility (lesson 15.6)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| T1/T2 | exact verdict | O(n·m) naive, near-linear with care | limit graph shows the irreducible core | ~40 lines | textbooks, verification |
| Interval derived sequence | exact verdict + intervals | O(n·m) | nested intervals (Allen–Cocke analysis) | ~60 lines | interval dataflow analysis (Ch 14) |
| DFS back-edge test | exact verdict | O(n + m) after dominators | the offending retreating edges | ~10 lines | LLVM containsIrreducibleCFG |
| Node splitting | makes any CFG reducible | exponential code growth worst case | an equivalent reducible CFG | ~80 lines | GPU back ends, structurizers; LLVM uses guard blocks instead (fix-irreducible) |
Canonical loop forms (lesson 15.7)
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Loop-simplify form | canonical shape for every natural loop | O(n + m) per loop, plus DomTree/LoopInfo updates | new preheader / latch / exit blocks | LoopSimplify.cpp is ~900 lines |
before LICM, unrolling, vectorization |
| LCSSA | every loop-defined value used outside flows through an exit phi | O(uses · exits) | .lcssa phis in exit blocks |
LCSSA.cpp is ~550 lines (plus SSAUpdater) |
before loop transforms, SCEV rewriting |
Comparison-lab results (reproduce with build/<preset>/bin/ch15-dombench --reps 5; this machine, LLVM 23.1.2, milliseconds, DFS included): random CFGs with 100 000 blocks — CHK 56, Lengauer–Tarjan 15, balanced LT 15, Semi-NCA 14, LLVM 27; the 20 000-block ladder — CHK 159, LT 0.8, Semi-NCA 94, LLVM 80; the 20 000-block comb — CHK 609, LT 0.8, Semi-NCA 0.6, LLVM 1.2; the 1 000-block bichain — CHK needs 999 passes (4.3 ms) while LT takes 0.03 ms. Lesson 15.1, section 8, has the full table and discusses it.
Route through this chapter¶
| Step | What | Techniques | How it is exercised |
|---|---|---|---|
| 1 | Lesson 15.1 | iterative, CHK, Lengauer–Tarjan, Semi-NCA | drills dominators, rpo, lengauer-tarjan; exercises E1–E6 (E7: read the provided DomTree) |
| 2 | Lesson 15.2 | DBS insertion, subtree deletion, DomTreeUpdater |
drill dom-update; DomTreeUpdates.* oracle tests |
| 3 | Lesson 15.3 | Cytron DF, CHK DF, iterated DF, DJ graphs | drills dominators (DF), idf; exercises E8–E10 |
| 4 | Lesson 15.4 | post-dominators, control dependence | drill post-dominance; exercises E11–E12 |
| 5 | Lesson 15.5 | DFS edges, natural loops, Tarjan, Havlak, Steensgaard | drills rpo, natural-loops; exercises E1, E13–E14 |
| 6 | Lesson 15.6 | T1/T2, intervals, DFS test, node splitting | drill natural-loops --difficulty hard; exercise E15 |
| 7 | Lesson 15.7 | loop-simplify form, LCSSA | drill loop-forms; lit tests with opt |
| 8 | Exercises (the spec of the contract pebble/include/pebble/Analysis/Dominance.h) |
Pebble uses CHK (full implementation) plus everything above | ./course test 15 |
| 9 | Comparison lab labs/ch15-dominance/SPEC.md |
CHK vs Lengauer–Tarjan (vs ★ balanced LT, ★ Semi-NCA) vs LLVM | ch15.LabAgreement.*, ch15.lab.bench-smoke, ch15-dombench |
| 10 | Theory test | all | ./course quiz 15 (≥ 80 % to finish) |
Practice and check¶
./course drill dominators --difficulty easy # warm up; --solution shows every step
./course drill lengauer-tarjan --seed 12 --solution # the EVAL/LINK table
./course drill natural-loops --difficulty hard # irreducible CFGs appear here
./course flash 15 # daily, a few minutes
./course quiz 15 # after the lessons
./course test 15 # after the exercises
./course status # done = quiz ≥ 80 % and tests pass
References¶
The chapter's annotated bibliography (papers, textbook sections, pinned source files for LLVM 23.1.2, GCC 15, Go, rustc, Cranelift, HotSpot, WebKit and V8, docs and talks) is in references.md. Start with: [LT79] and [CHK01] (the two dominator algorithms of the lab), [GTW06] (why LLVM chose Semi-NCA), [CFRWZ91] (frontiers, phi placement and control dependence), [Hav97] with [Ram02] (loop forests), [HU74] (reducibility), and for a gentler route [EaC3 §9.2] and [Dragon2 §9.6]. The LLVM files to keep open are [LLVM-GDTC], [LLVM-IDF], [LLVM-LoopInfo], [LLVM-Cycle] and [LLVM-LoopTerm].