Skip to content

References — Chapter 15 · Control-Flow Analysis: Dominance & Loops

Every source this chapter cites, grouped by kind. Lessons cite entries inline as [KEY]; each entry says why and when to read it. Core reading marks the entries the chapter assumes you will open.

Foundational and research papers

  • [AC76] Frances E. Allen and John Cocke. A Program Data Flow Analysis Procedure. Communications of the ACM 19(3), pp. 137-147, 1976. doi:10.1145/360018.360025
    Why and when: Interval-based elimination dataflow over the derived sequence; read after Ch 14 and Lesson 15.6 §6 to see what intervals were for.
    Cited in: 06-reducibility

  • [AHLT99] Stephen Alstrup, Dov Harel, Peter W. Lauridsen, and Mikkel Thorup. Dominators in Linear Time. SIAM Journal on Computing 28(6), pp. 2117-2132, 1999. doi:10.1137/S0097539797317263
    Why and when: Removes the inverse-Ackermann factor with microtrees; cited in Lesson 15.1 §6 as the theoretical end point. Read only the introduction: no production compiler uses it.
    Cited in: 01-dominator-algorithms

  • [All70] Frances E. Allen. Control Flow Analysis. SIGPLAN Notices 5(7), Proc. Symposium on Compiler Optimization, pp. 1-19, 1970. doi:10.1145/390013.808479
    Why and when: Core reading. Intervals, the derived sequence (Definition 15.6.5) and loops defined through dominance; the paper that made control-flow analysis a subject. Read §2-4 with Lessons 15.5 and 15.6.
    Cited in: 05-loop-nesting-forests, 06-reducibility

  • [BGKRTW08] Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert E. Tarjan, and Jeffery R. Westbrook. Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems. SIAM Journal on Computing 38(4), pp. 1533-1573, 2008. doi:10.1137/070693217
    Why and when: A simpler linear-time dominator algorithm (and a correction of earlier claims); §1-2 give the clearest survey of the dominator-algorithm landscape after Lesson 15.1.
    Cited in: 01-dominator-algorithms

  • [CCF91] Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante. Automatic Construction of Sparse Data Flow Evaluation Graphs. Proc. 18th ACM Symposium on Principles of Programming Languages (POPL), pp. 55-66, 1991. doi:10.1145/99583.99594
    Why and when: Pruned phi placement: intersect DF+ with liveness, which is what IDFCalculator::setLiveInBlocks does in mem2reg; read after Lesson 15.3 §6, before Ch 16.
    Cited in: 03-dominance-frontiers

  • [CFRWZ91] Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM TOPLAS 13(4), pp. 451-490, 1991. doi:10.1145/115372.115320
    Why and when: Core reading. Defines dominance frontiers, proves the DF_local/DF_up decomposition (Theorem 15.3.5), the phi-placement theorem (Theorem 15.3.10) and control dependence = reverse DF (Theorem 15.4.6). Read §4-5 (frontiers, phi placement) with Lesson 15.3 and §6 with Lesson 15.4.
    Cited in: overview, 03-dominance-frontiers, 04-post-dominance-and-control-dependence

  • [CFS90] Ron Cytron, Jeanne Ferrante, and Vivek Sarkar. Compact Representations for Control Dependence. Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 337-351, 1990. doi:10.1145/93548.93592
    Why and when: Factors control dependence into regions to shrink PDGs; the "compact representation" variant of Lesson 15.4 §6. Optional.
    Cited in: 04-post-dominance-and-control-dependence

  • [CFT03] Larry Carter, Jeanne Ferrante, and Clark Thomborson. Folklore Confirmed: Reducible Flow Graphs Are Exponentially Larger. Proc. 30th ACM Symposium on Principles of Programming Languages (POPL), pp. 106-114, 2003. doi:10.1145/604131.604141
    Why and when: Proves the exponential lower bound behind Proposition 15.6.15 (node splitting can blow up); read the introduction and the construction.
    Cited in: 06-reducibility

  • [CHK01] Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy. A Simple, Fast Dominance Algorithm. Software Practice & Experience 4 (also Rice University TR-06-33870), 2001. pdf
    Why and when: Core reading. The origin of the CHK algorithm Pebble implements (Figure 3 = Algorithm 15.1.12) and of the runner algorithm for dominance frontiers (Algorithm 15.3.8). Read §2-4 after Lesson 15.1 §2; the timing section backs the "CHK beats Lengauer-Tarjan on normal CFGs" claim.
    Cited in: overview, 01-dominator-algorithms, 03-dominance-frontiers

  • [CM69] John Cocke and Raymond E. Miller. Some Analysis Techniques for Optimizing Computer Programs. Proc. 2nd Hawaii International Conference on System Sciences, pp. 143-146, 1969.
    Why and when: Where node splitting (Algorithm 15.6.9) is attributed; read HU74 and JC97 instead for the modern treatment.
    Note: Conference proceedings without a DOI; cited for the origin of node splitting.
    Cited in: 06-reducibility

  • [DR05] Dibyendu Das and U. Ramakrishna. A Practical and Fast Iterative Algorithm for φ-Function Computation Using DJ Graphs. ACM TOPLAS 27(3), pp. 426-440, 2005. doi:10.1145/1065887.1065890
    Why and when: Merge sets: precompute DF+({X}) per node once and answer DF+(S) as a union; the variant of Lesson 15.3 §6 that trades quadratic space for fast repeated queries.
    Cited in: 03-dominance-frontiers

  • [FOW87] Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The Program Dependence Graph and Its Use in Optimization. ACM TOPLAS 9(3), pp. 319-349, 1987. doi:10.1145/24039.24041
    Why and when: Core reading. Defines control dependence (Definition 15.4.4) and the post-dominator-tree walk of Algorithm 15.4.10; read §2-3 with Lesson 15.4, the rest when you meet program slicing.
    Cited in: 04-post-dominance-and-control-dependence

  • [GILS16] Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni. An Experimental Study of Dynamic Dominators. arXiv:1604.02711 (conference version ESA 2012, LNCS 7501), 2016. link
    Why and when: Core reading. The paper LLVM's updater implements ("[2]" in GenericDomTreeConstruction.h): Lemma 2.5 (insertion, Lemma 15.2.3 here), Lemma 2.6 (deletion, Lemma 15.2.5), the proper-support test (p. 3) and the measurements. Read §2-3 alongside Lesson 15.2.
    Cited in: 01-dominator-algorithms, 02-incremental-dominators

  • [Hav97] Paul Havlak. Nesting of Reducible and Irreducible Loops. ACM TOPLAS 19(4), pp. 557-567, 1997. doi:10.1145/262004.262005
    Why and when: Core reading. Havlak's loop nesting forest (Algorithm 15.5.9, the definition LLVM's CycleInfo implements); read Figure 3 and §3 with Lesson 15.5, then Ram99 for the complexity fix.
    Cited in: overview, 05-loop-nesting-forests

  • [HU72] Matthew S. Hecht and Jeffrey D. Ullman. Flow Graph Reducibility. SIAM Journal on Computing 1(2), pp. 188-202, 1972. doi:10.1137/0201014
    Why and when: Core reading. Defines T1/T2 and proves the result independent of the order of application (Theorem 15.6.3); read §2-3 with Lesson 15.6.
    Cited in: 06-reducibility

  • [HU74] Matthew S. Hecht and Jeffrey D. Ullman. Characterizations of Reducible Flow Graphs. Journal of the ACM 21(3), pp. 367-375, 1974. doi:10.1145/321832.321835
    Why and when: Core reading. The equivalences of Theorem 15.6.4: T1/T2, DFS back edges = dominance back edges, acyclic forward graph, and the forbidden () subgraph. Nine pages; read all of it after Lesson 15.6.
    Cited in:* overview, 06-reducibility

  • [JC97] Johan Janssen and Henk Corporaal. Making Graphs Reducible with Controlled Node Splitting. ACM TOPLAS 19(6), pp. 1031-1052, 1997. doi:10.1145/267959.269971
    Why and when: Chooses split nodes to keep the copies small; the controlled variant of Lesson 15.6 §6 and the best description of node splitting as an algorithm.
    Cited in: 06-reducibility

  • [KU76] John B. Kam and Jeffrey D. Ullman. Global Data Flow Analysis and Iterative Algorithms. Journal of the ACM 23(1), pp. 158-171, 1976. doi:10.1145/321921.321938
    Why and when: Proves the d + 2 pass bound for round-robin iteration in reverse postorder that Lesson 15.1 (Proposition 15.1.23) uses for the iterative and CHK algorithms; read §3-4 with Ch 14 open.
    Cited in: 01-dominator-algorithms

  • [LM69] Edward S. Lowry and C. W. Medlock. Object Code Optimization. Communications of the ACM 12(1), pp. 13-22, 1969. doi:10.1145/362835.362838
    Why and when: Core reading. The FORTRAN H optimizer: "predominators" by iterating set equations, loops found from them, code moved into a landing pad (the preheader), and postdominators by running the same code backwards. Read after Lessons 15.1 and 15.7 to see how much of the chapter was already there.
    Cited in: 01-dominator-algorithms, 04-post-dominance-and-control-dependence, 05-loop-nesting-forests, 07-canonical-loop-forms

  • [LT79] Thomas Lengauer and Robert Endre Tarjan. A Fast Algorithm for Finding Dominators in a Flowgraph. ACM TOPLAS 1(1), pp. 121-141, 1979. doi:10.1145/357062.357071
    Why and when: Core reading. The origin of semidominators, EVAL/LINK and the two-phase algorithm of Lesson 15.1. Read §2 (Theorems 1-4 and Corollary 1, which Theorem 15.1.15 and Corollary 15.1.16 restate), then the pseudo-code of §3 and the appendix (sophisticated LINK). The complexity analysis of §4 can wait.
    Cited in: overview, 01-dominator-algorithms

  • [PB97] Keshav Pingali and Gianfranco Bilardi. Optimal Control Dependence Computation and the Roman Chariots Problem. ACM TOPLAS 19(3), pp. 462-491, 1997. doi:10.1145/256167.256217
    Why and when: The APT structure answers control-dependence queries in time proportional to the answer, avoiding the quadratic output of Lesson 15.4 §5; read §1-3 for the idea.
    Cited in: 04-post-dominance-and-control-dependence

  • [PM72] Paul W. Purdom Jr. and Edward F. Moore. Immediate Predominators in a Directed Graph. Communications of the ACM 15(8), pp. 777-778, 1972. doi:10.1145/361532.361566
    Why and when: The "delete d and see what becomes unreachable" definition of dominance (Proposition 15.1.4) turned into an O(n·m) algorithm; the course's Python oracle dominators_by_removal is this idea. Two pages; read with Lesson 15.1 §6.
    Cited in: 01-dominator-algorithms

  • [Pro59] Reese T. Prosser. Applications of Boolean Matrices to the Analysis of Flow Diagrams. Proc. Eastern Joint IRE-AIEE-ACM Computer Conference (1959), pp. 133-138, 1959. doi:10.1145/1460299.1460314
    Why and when: Where "dominance" first appears, as a property of connectivity matrices of flow diagrams. Worth a skim after Lesson 15.1 §1 for history only; nothing in the chapter depends on it.
    Cited in: 01-dominator-algorithms

  • [Ram02] G. Ramalingam. On Loops, Dominators, and Dominance Frontiers. ACM TOPLAS 24(5), pp. 455-490, 2002. doi:10.1145/570886.570887
    Why and when: Core reading. The general definition of a loop nesting forest (Definition 15.5.6) and a comparison of Tarjan's, Havlak's, Steensgaard's and Sreedhar-Gao-Lee's forests; the best single paper to read after Lesson 15.5.
    Cited in: overview, 05-loop-nesting-forests

  • [Ram99] G. Ramalingam. Identifying Loops in Almost Linear Time. ACM TOPLAS 21(2), pp. 175-188, 1999. doi:10.1145/316686.316687
    Why and when: Shows Havlak's bookkeeping can be quadratic (the pathological family of Lesson 15.5 §5) and restores the almost-linear bound; read §3.
    Cited in: 05-loop-nesting-forests

  • [RR94] G. Ramalingam and Thomas Reps. An Incremental Algorithm for Maintaining the Dominator Tree of a Reducible Flowgraph. Proc. 21st ACM Symposium on Principles of Programming Languages (POPL), pp. 287-296, 1994. doi:10.1145/174675.177905
    Why and when: The first incremental dominator algorithm, restricted to reducible flowgraphs; its insertion lemma is the ancestor of Lemma 15.2.3. Read §3 after Lesson 15.2 for the history.
    Cited in: 02-incremental-dominators

  • [SG95] Vugranam C. Sreedhar and Guang R. Gao. A Linear Time Algorithm for Placing φ-Nodes. Proc. 22nd ACM Symposium on Principles of Programming Languages (POPL), pp. 62-73, 1995. doi:10.1145/199448.199464
    Why and when: Core reading. DJ graphs and the level-ordered DF+ computation behind LLVM's IDFCalculator (Algorithm 15.3.14); read §3-4 after Lesson 15.3 §2, then compare with IDFCalculatorBase::calculate.
    Cited in: 03-dominance-frontiers

  • [SGL96] Vugranam C. Sreedhar, Guang R. Gao, and Yong-Fong Lee. Identifying Loops Using DJ Graphs. ACM TOPLAS 18(6), pp. 649-658, 1996. doi:10.1145/236114.236115
    Why and when: Uses the DJ graph of Lesson 15.3 to find reducible and irreducible loops in one framework; read with Lesson 15.5 §6 as the bridge between frontiers and loop forests.
    Cited in: 03-dominance-frontiers, 05-loop-nesting-forests

  • [SGL97] Vugranam C. Sreedhar, Guang R. Gao, and Yong-Fong Lee. Incremental Computation of Dominator Trees. ACM TOPLAS 19(2), pp. 239-252, 1997. doi:10.1145/244795.244799
    Why and when: Updates dominator trees and DJ graphs together under edge insertions and deletions, using dominance frontiers to find affected nodes; the alternative Lesson 15.2 §6 compares with DBS.
    Cited in: 02-incremental-dominators, 03-dominance-frontiers

  • [Tar72] Robert Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing 1(2), pp. 146-160, 1972. doi:10.1137/0201010
    Why and when: DFS edge classification and linear-time SCCs (Algorithm 15.5.2 and the SCC routine of Algorithm 15.5.10); read §2-3 if the lemma "every cycle contains a retreating edge" is new.
    Cited in: 05-loop-nesting-forests

  • [Tar74] Robert Endre Tarjan. Testing Flow Graph Reducibility. Journal of Computer and System Sciences 9(3), pp. 355-365, 1974. doi:10.1016/S0022-0000(74)80049-8
    Why and when: Core reading. The almost-linear loop-nesting / reducibility test with union-find (Algorithm 15.5.8) that Havlak later extended; read §2-3 after Lesson 15.5 §2.
    Cited in: 05-loop-nesting-forests, 06-reducibility

  • [UM02] Sebastian Unger and Frank Mueller. Handling Irreducible Loops: Optimized Node Splitting versus DJ-Graphs. ACM TOPLAS 24(4), pp. 299-333, 2002. doi:10.1145/567097.567098
    Why and when: Measures node splitting against analyzing irreducible loops directly; read §1 and the results after Lesson 15.6 when deciding between transforming and analyzing.
    Cited in: 06-reducibility

  • [WMZC07] Tao Wei, Jian Mao, Wei Zou, and Yu Chen. A New Algorithm for Identifying Loops in Decompilation. Static Analysis Symposium (SAS 2007), LNCS 4634, pp. 170-183, 2007. doi:10.1007/978-3-540-74061-2_11
    Why and when: A one-pass loop-nesting algorithm designed for decompilers; the Havlak variant listed in Lesson 15.5 §6. Optional.
    Cited in: 05-loop-nesting-forests

Textbooks and monographs

  • [Appel] Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998. Read: §18.1 Dominators (natural loops, loop-nest trees, preheaders); §19.1 Converting to SSA form (dominance frontiers); §19.2 Efficient computation of the dominator tree (Lengauer-Tarjan).
    Why and when: The most readable walk through Lengauer-Tarjan with code; read §19.2 alongside Lesson 15.1's trace table if the EVAL/LINK bookkeeping is unclear. The C and Java editions share the numbering.

  • [Dragon2] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed.. Addison-Wesley, 2006. Read: §9.6 Loops in Flow Graphs (§9.6.1 dominators, §9.6.2-9.6.3 depth-first ordering and edge kinds, §9.6.4 back edges and reducibility, §9.6.5 depth, §9.6.6 natural loops, §9.6.7 convergence); §9.7 Region-Based Analysis.
    Why and when: Core reading. The classic proofs for Lessons 15.5 and 15.6 (natural loops are disjoint or nested, reducibility via back edges, the d + 2 bound). Read §9.6 before Lesson 15.5 if DFS orders are rusty.
    Cited in: overview, 01-dominator-algorithms, 07-canonical-loop-forms

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: §9.2 (dominance as an iterative data-flow problem), §9.3 (SSA construction: dominance frontiers and phi placement).
    Why and when: Core reading. The gentlest treatment of iterative dominators, the CHK tree representation and frontiers, by two of CHK's authors; read §9.2 before Lesson 15.1 if the proofs feel compressed.
    Cited in: overview

  • [Hec77] Matthew S. Hecht. Flow Analysis of Computer Programs. Elsevier North-Holland, 1977. Read: the chapters on flow-graph reducibility and node splitting (section numbers not verified for this course).
    Why and when: The monograph that systematized T1/T2, intervals and node splitting; use it as a reference for the proofs Lesson 15.6 sketches if your library has it.
    Cited in: 06-reducibility

  • [Muchnick] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. Read: Ch. 7 Control-Flow Analysis (§7.3 dominators and postdominators, §7.4 loops and SCCs, §7.5 reducibility, §7.6 interval analysis and control trees, §7.7 structural analysis); §9.5 program-dependence graphs.
    Why and when: Complete pseudo-code for every chapter topic, including structural analysis (the T1/T2 generalization of Lesson 15.6 §6). Use it as a second source of pseudo-code.
    Cited in: 06-reducibility

  • [SSAB] Fabrice Rastello and Florent Bouchez Tichadou. SSA-based Compiler Design. Springer, 2022. Read: Ch. 3 Standard Construction and Destruction Algorithms (dominance frontiers, phi placement); Ch. 4 Advanced Construction Algorithms for SSA (DJ graphs, merge sets, loop nesting forests). doi:10.1007/978-3-030-80515-9
    Why and when: Frontiers, DJ graphs and loop forests from the SSA point of view; read Ch. 4 after Lesson 15.3 and again during Ch 16.
    Cited in: 07-canonical-loop-forms

Surveys and tutorials

  • [GTW06] Loukas Georgiadis, Robert E. Tarjan, and Renato F. Werneck. Finding Dominators in Practice. Journal of Graph Algorithms and Applications 10(1), pp. 69-94, 2006. doi:10.7155/jgaa.00119
    Why and when: Core reading. The experimental comparison of iterative, Lengauer-Tarjan and Semi-NCA on real CFGs and adversarial families (the ladder of Lesson 15.1 §5 among them) behind LLVM's choice of Semi-NCA. Read §4-5 before running the comparison lab.
    Cited in: overview, 01-dominator-algorithms

Theses and technical reports

  • [AC72] Frances E. Allen and John Cocke. Graph-Theoretic Constructs for Program Control Flow Analysis. IBM Research Report RC 3923, IBM T. J. Watson Research Center, 1972.
    Why and when: The set-based formulation of dominators (Dom(n) = {n} ∪ ⋂ Dom(p)) that Lesson 15.1's Algorithm 15.1.11 iterates, together with intervals and the derived sequence of Lesson 15.6.
    Note: No DOI; the report circulates as a scanned copy (Frances Allen's papers). Cited for history.
    Cited in: 01-dominator-algorithms

  • [AL96] Stephen Alstrup and Peter W. Lauridsen. A Simple Dynamic Algorithm for Maintaining a Dominator Tree. Technical Report 96-3, Department of Computer Science, University of Copenhagen, 1996.
    Why and when: The depth-based insertion search that GILS16 turned into DBS (Algorithm 15.2.4); read GILS16 instead unless you want the original argument.
    Note: Technical report without a DOI; GILS16 summarizes it.
    Cited in: 02-incremental-dominators

  • [Geo05] Loukas Georgiadis. Linear-Time Algorithms for Dominators and Related Problems. PhD thesis, Princeton University (TR-737-05), 2005. link
    Why and when: Core reading. Semi-NCA (pp. 21-23) and the proof that idom(w) = NCA(parent(w), sdom(w)) (Lemma 15.1.18). This is the reference LLVM's GenericDomTreeConstruction.h cites; read the Semi-NCA pages after Lesson 15.1 §4, then compare with SemiNCAInfo::runSemiNCA.
    Cited in: 01-dominator-algorithms

  • [Ste93] Bjarne Steensgaard. Sequentializing Program Dependence Graphs for Irreducible Programs. Technical Report MSR-TR-93-14, Microsoft Research, 1993.
    Why and when: The SCC-based loop forest with header sets (Algorithm 15.5.10); read the loop-forest section only, after Lesson 15.5, or the summary in Ram02 §3.
    Note: Microsoft Research technical report without a DOI; listed on Microsoft Research's publications site.
    Cited in: 05-loop-nesting-forests

Source code (pinned versions)

  • [Cranelift-Dom] Cranelift's Semi-NCA dominator tree (and its CHK baseline in dominator_tree/simple.rs) — cranelift/codegen/src/dominator_tree.rs in bytecodealliance/wasmtime at v36.0.0. Symbols: DominatorTree::compute, SimpleDominatorTree.
    Why and when: Semi-NCA for production, CHK kept as a simple baseline; the comment lists Julia, SpiderMonkey and LLVM as other Semi-NCA users.
    Cited in: 01-dominator-algorithms

  • [Cranelift-Loops] Cranelift's natural-loop analysis — cranelift/codegen/src/loop_analysis.rs in bytecodealliance/wasmtime at v36.0.0. Symbols: LoopAnalysis::compute, find_loop_headers, discover_loop_blocks.
    Why and when: Natural loops in their plainest form ("a block is a loop header if it dominates any of its predecessors"); read after Lesson 15.5 §2.
    Cited in: 05-loop-nesting-forests

  • [GCC-Cfganal] GCC's CFG analyses (DFS back edges, CHK frontiers, DF+, control dependence) — gcc/cfganal.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: mark_dfs_back_edges, compute_dominance_frontiers, compute_idf, connect_infinite_loops_to_exit, control_dependences::find_control_dependence.
    Why and when: One file with four of the chapter's techniques: the runner loop of Algorithm 15.3.8, the worklist of Algorithm 15.3.11, the FOW walk of Algorithm 15.4.10 and DFS_BACK marking.
    Cited in: 03-dominance-frontiers, 04-post-dominance-and-control-dependence, 05-loop-nesting-forests

  • [GCC-Dominance] GCC's Lengauer-Tarjan (balanced) and its CHK-based incremental fix-up — gcc/dominance.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: dom_info::calc_idoms, dom_info::eval, dom_info::compress, dom_info::link_roots, iterate_fix_dominators.
    Why and when: Sophisticated-linking Lengauer-Tarjan for full builds and CHK for small affected block sets; read the header comment after Lesson 15.1 and iterate_fix_dominators after Lesson 15.2.
    Cited in: 01-dominator-algorithms, 02-incremental-dominators, 04-post-dominance-and-control-dependence

  • [GCC-LCSSA] GCC's loop-closed SSA rewriting — gcc/tree-ssa-loop-manip.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: rewrite_into_loop_closed_ssa, rewrite_into_loop_closed_ssa_1.
    Why and when: The GCC counterpart of LLVM's LCSSA pass (Lesson 15.7 §7); read with the GCC-LoopDoc node.
    Cited in: 07-canonical-loop-forms

  • [GCC-Loops] GCC's SCC-based irreducible-region marking — gcc/cfgloopanal.cc in gcc-mirror/gcc at releases/gcc-15. Symbols: mark_irreducible_loops.
    Why and when: Throws away latch edges and marks blocks and edges inside remaining SCCs (IRREDUCIBLE_LOOP): the Steensgaard-style marking of Lesson 15.5 §7; natural loops are found by flow_loops_find in gcc/cfgloop.cc.
    Cited in: 05-loop-nesting-forests

  • [Go-Dom] The Go compiler's dominators (Lengauer-Tarjan and CHK side by side) — src/cmd/compile/internal/ssa/dom.go in golang/go at go1.25.0. Symbols: dominators, dominatorsLTOrig, evalOrig, linkOrig, dominatorsSimple, intersect.
    Why and when: Both algorithms of the comparison lab in one short file, with comments naming the papers; read after Lesson 15.1 §7.
    Cited in: 01-dominator-algorithms

  • [Go-Loopnest] The Go compiler's loop nest with irreducibility detection — src/cmd/compile/internal/ssa/likelyadjust.go in golang/go at go1.25.0. Symbols: loopnestfor.
    Why and when: Natural loops from dominated predecessors and a sawIrred flag when a retreating edge is not a dominance back edge (Theorem 15.6.4(b)); Lesson 15.5 §7 and 15.6 §7.
    Cited in: 05-loop-nesting-forests, 06-reducibility

  • [Go-Phi] The Go compiler's phi placement (Sreedhar-Gao above 500 blocks) — src/cmd/compile/internal/ssagen/phi.go in golang/go at go1.25.0. Symbols: phiState.insertVarPhis, smallBlocks.
    Why and when: A second production implementation of Algorithm 15.3.14 with a block-level heap; read after Lesson 15.3 §7.
    Cited in: 03-dominance-frontiers

  • [HotSpot-Dom] HotSpot C2's Lengauer-Tarjan with sophisticated linking — src/hotspot/share/opto/domgraph.cpp in openjdk/jdk at jdk-25+36. Symbols: PhaseCFG::build_dominator_tree, Tarjan.
    Why and when: The balanced LINK/EVAL of Algorithm 15.1.17 with _size and _child fields; read after the balanced-linking trace in Lesson 15.1 §3.
    Cited in: 01-dominator-algorithms

  • [HotSpot-Loops] HotSpot C2's loop tree ("a modified Vick/Tarjan algorithm") — src/hotspot/share/opto/loopnode.cpp in openjdk/jdk at jdk-25+36. Symbols: PhaseIdealLoop::build_loop_tree, IdealLoopTree.
    Why and when: A Tarjan-style loop nesting that flags irreducible loops instead of stopping; the production relative of Algorithm 15.5.8.
    Cited in: 05-loop-nesting-forests

  • [LLVM-ADCE] Aggressive dead code elimination via post-dominance frontiers — llvm/lib/Transforms/Scalar/ADCE.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences.
    Why and when: Control dependence as a ReverseIDFCalculator query over the live blocks (Theorem 15.4.6 in action); the "find it in LLVM" task of Lesson 15.4.
    Cited in: 04-post-dominance-and-control-dependence

  • [LLVM-CFG] LLVM's reducibility test over an RPO traversal and LoopInfo — llvm/include/llvm/Analysis/CFG.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: containsIrreducibleCFG.
    Why and when: The DFS back-edge test of Algorithm 15.6.8 in twenty lines (the isProperBackedge lambda); the "find it in LLVM" task of Lesson 15.6.
    Cited in: 06-reducibility

  • [LLVM-CFGcpp] LLVM's retreating-edge finder — llvm/lib/Analysis/CFG.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: FindFunctionBackedges.
    Why and when: A DFS with an explicit stack that reports retreating ("back") edges, Definition 15.5.1's kind Back; compare with the course's computeDFS.
    Cited in: 05-loop-nesting-forests

  • [LLVM-CFGUpdate] Cancelling and deduplicating a batch of CFG updates — llvm/include/llvm/Support/CFGUpdate.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: cfg::LegalizeUpdates.
    Why and when: The Legalize step of Algorithm 15.2.8 (insert/delete pairs cancel); a short read after the batched-updates worked example.
    Cited in: 02-incremental-dominators

  • [LLVM-Cycle] LLVM's CycleInfo (Havlak's loop nesting forest) — llvm/include/llvm/ADT/GenericCycleImpl.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: GenericCycleInfoCompute::run, GenericCycleInfoCompute::dfs, GenericCycle::appendEntry.
    Why and when: Core reading. Header candidates in reverse preorder, non-descendant predecessors as extra entries: the production version of Algorithm 15.5.9; read after Lesson 15.5 §4.
    Cited in: overview, 05-loop-nesting-forests

  • [LLVM-DFImpl] LLVM's Cytron-style dominance frontier computation — llvm/include/llvm/Analysis/DominanceFrontierImpl.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: DominanceFrontierBase::analyze, DFCalculateWorkObject.
    Why and when: DF_local then DF_up over the dominator tree with an explicit work stack: Algorithm 15.3.6 without recursion. Read after Lesson 15.3 §2.
    Cited in: 03-dominance-frontiers

  • [LLVM-DTU] LLVM's batched, eager or lazy dominator-tree updater — llvm/include/llvm/Analysis/GenericDomTreeUpdater.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: GenericDomTreeUpdater::applyUpdates, GenericDomTreeUpdater::flush, GenericDomTreeUpdater::UpdateStrategy.
    Why and when: The API every CFG-changing transform uses (Algorithm 15.2.8); read with Lesson 15.2 §7 and the jump-threading box there.
    Cited in: 02-incremental-dominators

  • [LLVM-FixIrr] LLVM's fix-irreducible (guard blocks instead of node splitting) — llvm/lib/Transforms/Utils/FixIrreducible.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: fixIrreducible.
    Why and when: Turns each irreducible cycle into a natural loop through a ControlFlowHub dispatch block; the alternative to node splitting in Lesson 15.6 §6-7.
    Cited in: 05-loop-nesting-forests, 06-reducibility

  • [LLVM-GDT] LLVM's dominator-tree data structure, queries and printer — llvm/include/llvm/Support/GenericDomTree.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: DominatorTreeBase::dominates, DominatorTreeBase::updateDFSNumbers, DominatorTreeBase::findNearestCommonDominator, DominatorTreeBase::print.
    Why and when: The {in,out} DFS numbers of print and the O(1) dominance query of Corollary 15.1.7; compare with the course's provided DomTree after Lesson 15.1 §7.
    Cited in: 01-dominator-algorithms

  • [LLVM-GDTC] LLVM's Semi-NCA dominator and post-dominator construction and incremental updates — llvm/include/llvm/Support/GenericDomTreeConstruction.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: SemiNCAInfo::runDFS, SemiNCAInfo::eval, SemiNCAInfo::runSemiNCA, SemiNCAInfo::FindRoots, SemiNCAInfo::RemoveRedundantRoots, SemiNCAInfo::InsertReachable, SemiNCAInfo::DeleteReachable, SemiNCAInfo::DeleteUnreachable, SemiNCAInfo::HasProperSupport, SemiNCAInfo::ApplyUpdates.
    Why and when: Core reading. The production implementation behind DominatorTree and PostDominatorTree. Read runSemiNCA after Lesson 15.1 (phase 2 is the three-line climb of Algorithm 15.1.19), FindRoots after Lesson 15.4, and InsertReachable/DeleteReachable after Lesson 15.2.
    Cited in: overview, 01-dominator-algorithms, 02-incremental-dominators, 04-post-dominance-and-control-dependence

  • [LLVM-IDF] LLVM's Sreedhar-Gao iterated dominance frontier (IDFCalculator) — llvm/include/llvm/Support/GenericIteratedDominanceFrontier.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: IDFCalculatorBase::calculate, IDFCalculatorBase::setLiveInBlocks.
    Why and when: Core reading. The priority queue keyed by (level, DFS-in number) and the SuccLevel > RootLevel filter of Algorithm 15.3.14; the "find it in LLVM" task of Lesson 15.3 starts here.
    Cited in: overview, 03-dominance-frontiers

  • [LLVM-JumpThreading] Jump threading with a lazy DomTreeUpdater — llvm/lib/Transforms/Scalar/JumpThreading.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: JumpThreadingPass::runImpl, JumpThreadingPass::threadEdge.
    Why and when: Makes many insertions and deletions per function and flushes them lazily; the batched-updates example of Lesson 15.2. Search for UpdateStrategy::Lazy.
    Cited in: 02-incremental-dominators

  • [LLVM-LCSSA] The LCSSA pass — llvm/lib/Transforms/Utils/LCSSA.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: formLCSSAForInstructions, formLCSSA, formLCSSARecursively.
    Why and when: Core reading. Algorithm 15.7.8: exit phis for every instruction used outside its loop, then SSAUpdater; the "find it in LLVM" task of Lesson 15.7.
    Cited in: 07-canonical-loop-forms

  • [LLVM-LoopInfo] LLVM's natural-loop discovery (LoopInfo) — llvm/include/llvm/Support/GenericLoopInfoImpl.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: LoopInfoBase::analyze, discoverAndMapSubloop, PopulateLoopsDFS.
    Why and when: Core reading. Natural loops discovered by a backward walk per header that skips inner subloops (Algorithm 15.5.7 made linear); read after Lesson 15.5 §2.
    Cited in: overview, 05-loop-nesting-forests

  • [LLVM-LoopInfoCpp] LoopInfo for IR, and the canonical-form predicates — llvm/lib/Analysis/LoopInfo.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: Loop::isLoopSimplifyForm, Loop::isLCSSAForm, Loop::isRecursivelyLCSSAForm.
    Why and when: The checks behind Definitions 15.7.3 and 15.7.4; short, read them before Lesson 15.7 §2.
    Cited in: 05-loop-nesting-forests, 07-canonical-loop-forms

  • [LLVM-LoopRotate] Loop rotation, and the dominator-tree updates it submits — llvm/lib/Transforms/Utils/LoopRotationUtils.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LoopRotate::rotateLoop.
    Why and when: Submits two Insert and one Delete update to DT.applyUpdates when it rotates a loop: the real-world insertion example of Lesson 15.2 and the rotation variant of Lesson 15.7 §6.
    Cited in: 02-incremental-dominators, 07-canonical-loop-forms

  • [LLVM-LoopSimplify] The loop-simplify pass — llvm/lib/Transforms/Utils/LoopSimplify.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: simplifyOneLoop, InsertPreheaderForLoop, separateNestedLoop, insertUniqueBackedgeBlock.
    Why and when: Core reading. Algorithm 15.7.6 in production; read simplifyOneLoop top to bottom after Lesson 15.7 §2, then separateNestedLoop with the skip.c box.
    Cited in: 07-canonical-loop-forms

  • [LLVM-Mem2Reg] mem2reg, the main client of IDFCalculator — llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PromoteMem2Reg::run.
    Why and when: Computes defining and live-in blocks per alloca and asks IDFCalculator where the phis go; read after Lesson 15.3 and again in Ch 16.
    Cited in: 03-dominance-frontiers

  • [LLVM-PostDom] LLVM's post-dominator tree analysis and printer — llvm/lib/Analysis/PostDominators.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: PostDominatorTree, PostDominatorTreeAnalysis, PostDominatorTreePrinterPass.
    Why and when: The analysis wrapper of Lesson 15.4 (the tree itself is built by LLVM-GDTC with a virtual root); open it with the print box.
    Cited in: 04-post-dominance-and-control-dependence

  • [LLVM-RegionInfo] Single-entry single-exit regions (print) — llvm/lib/Analysis/RegionInfo.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: RegionInfo, RegionInfoPrinterPass.
    Why and when: The modern descendant of intervals (Lesson 15.6): nested SESE regions computed from dominance and post-dominance frontiers, used by Polly.
    Cited in: 06-reducibility

  • [LLVM-SCCP] SCCP's removal of infeasible CFG edges through a DomTreeUpdater — llvm/lib/Transforms/Utils/SCCPSolver.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SCCPSolver::removeNonFeasibleEdges.
    Why and when: Deletes branch edges proven infeasible and reports them to a lazy DomTreeUpdater: the real-world deletion example of Lesson 15.2.
    Cited in: 02-incremental-dominators

  • [Rustc-Dom] rustc's Semi-NCA dominators — compiler/rustc_data_structures/src/graph/dominators/mod.rs in rust-lang/rust at 1.90.0. Symbols: dominators.
    Why and when: A compact Semi-NCA following Georgiadis's thesis, with comments that restate Lemma 15.1.18; read after Lesson 15.1 §7.
    Cited in: 01-dominator-algorithms

  • [V8-Scheduler] V8 TurboFan's loop-aware special RPO — src/compiler/scheduler.cc in v8/v8 at 13.8.1. Symbols: SpecialRPONumberer::ComputeSpecialRPO.
    Why and when: A DFS that identifies loops by their back edges and keeps each loop contiguous in the block order; the variant of DFS numbering in Lesson 15.5 §6.
    Cited in: 05-loop-nesting-forests

  • [WebKit-Dom] WebKit's dominators (Semi-NCA below 20 000 nodes, Lengauer-Tarjan above, naive self-check) — Source/WTF/wtf/Dominators.h in WebKit/WebKit at wpewebkit-2.48.0. Symbols: Dominators, NaiveDominators, maxNodesForSemiNCADominance.
    Why and when: The hybrid of Lesson 15.1 §6 and the only production use of iterative dominator sets (as a self-check); read after the comparison lab.
    Cited in: 01-dominator-algorithms

Official documentation and specifications

  • [GCC-LoopDoc] GCC Internals, "Loop Analysis and Representation" (node LCSSA). GCC 15. link
    Why and when: GCC's loop tree, its canonical-loop properties and loop-closed SSA, in the texinfo source of the internals manual; read after Lesson 15.7 to compare with LLVM.
    Cited in: 07-canonical-loop-forms

  • [LLVM-CycleTerm] LLVM Cycle Terminology. LLVM 23.1.2. link
    Why and when: The definition of cycles, entries and the cycle nesting forest that CycleInfo computes, citing Havlak; read after Lesson 15.5 §2 and compare with Definition 15.5.6.
    Cited in: 05-loop-nesting-forests

  • [LLVM-LoopTerm] LLVM Loop Terminology (and Canonical Forms). LLVM 23.1.2. link
    Why and when: Core reading. The exact definitions LoopInfo implements (header, latch, exiting block, loop-simplify form, LCSSA, rotated form); keep it open for Lessons 15.5 and 15.7.
    Cited in: overview, 05-loop-nesting-forests, 07-canonical-loop-forms

  • [LLVM-Passes] LLVM's Analysis and Transform Passes. LLVM 23.1.2. link
    Why and when: One-paragraph descriptions of domtree, postdomtree, domfrontier, loops, loop-simplify, lcssa, adce and the printers used in this chapter's real-world boxes.

Talks and videos

  • [Kud17] Jakub Kuderski. Dominator Trees and incremental updates that transcend time. 2017 LLVM Developers' Meeting, San Jose, 2017. link
    Why and when: The author of LLVM's incremental updater explains why hand-written updates kept breaking, how DBS and the Semi-NCA subtree rebuild replaced them, and how batched updates (applyUpdates) work; the DomTreeUpdater wrapper came a year later (2018). Slides at the URL; the video is on the LLVM YouTube channel. Watch after Lesson 15.2 §7 (extra reading, not an origin).
    Cited in: 02-incremental-dominators

  • [LoopTut19] Kit Barton, Ettore Tiotto, Hal Finkel, Michael Kruse, and Johannes Doerfert. Writing Loop Optimizations in LLVM (tutorial). 2019 LLVM Developers' Meeting, San Jose, 2019. link
    Why and when: Walks through LoopInfo, loop-simplify form, LCSSA and rotation as a pass writer sees them; watch before Ch 18, after Lesson 15.7 (extra reading).