Skip to content

References — Chapter 18 · Loop Optimizations

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

  • [AC72b] Frances E. Allen and John Cocke. A Catalogue of Optimizing Transformations. In R. Rustin (ed.), Design and Optimization of Compilers, Prentice-Hall, pp. 1–30, 1972.
    Why and when: The catalogue that named code motion, strength reduction, unrolling and unswitching as standard transformations; skim it for the vocabulary Lessons 18.1, 18.4 and 18.5 inherit.
    Note: A book chapter; no DOI. Found in university libraries and as scans of the Allen archive.
    Cited in: 01-loop-invariant-code-motion, 02-induction-variables, 04-strength-reduction, 05-loop-restructuring

  • [ACK81] Frances E. Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. In S. S. Muchnick and N. D. Jones (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, pp. 79–101, 1981.
    Why and when: Core reading. Basic and derived induction variables and the classical strength-reduction algorithm (Lessons 18.2 and 18.4); the lab's classic detector and reducer implement its definitions.
    Note: Book chapter; no DOI.
    Cited in: overview, 02-induction-variables, 04-strength-reduction

  • [AK84] John R. Allen and Ken Kennedy. Automatic Loop Interchange. SIGPLAN Symposium on Compiler Construction 1984 (SIGPLAN Notices 19(6)), pp. 233-246, 1984. doi:10.1145/502949.502897
    Why and when: Interchange legality with direction vectors, as implemented in PFC; the origin of Theorem 18.7.4's two-loop case.
    Cited in: 07-dependence-driven-transformations

  • [AK87] Randy Allen and Ken Kennedy. Automatic Translation of FORTRAN Programs to Vector Form. ACM TOPLAS 9(4), pp. 491-542, 1987. doi:10.1145/29873.29875
    Why and when: The classic vectorizer: dependence graph, distribution by SCCs, vector statements (Lesson 18.7's Algorithm 18.7.2 and Lesson 18.8's history).
    Cited in: 08-vectorization

  • [AKPW83] J. R. Allen, Ken Kennedy, Carrie Porterfield, and Joe Warren. Conversion of Control Dependence to Data Dependence. POPL 1983, pp. 177-189, 1983. doi:10.1145/567067.567085
    Why and when: If-conversion, the basis of predication in Lesson 18.8 (Algorithm 18.8.9).
    Cited in: 08-vectorization

  • [BGS00] Rastislav Bodík, Rajiv Gupta, and Vivek Sarkar. ABCD: Eliminating Array Bounds Checks on Demand. PLDI 2000 (SIGPLAN Notices 35(5)), pp. 321-333, 2000. doi:10.1145/358438.349342
    Why and when: Core reading. e-SSA, the inequality graph and the demand-driven proof (Algorithm 18.9.5); §4 on cycles is the part Theorem 18.9.11 formalizes.
    Cited in: overview, 09-bounds-check-elimination

  • [BHRS08] Uday Bondhugula, Albert Hartono, J. Ramanujam, and P. Sadayappan. A Practical Automatic Polyhedral Parallelizer and Locality Optimizer. PLDI 2008, pp. 101-113, 2008. doi:10.1145/1375581.1375595
    Why and when: Pluto: choose tiling hyperplanes that minimize dependence distances; the scheduler behind the skew isl found in Lesson 18.7's box.
    Cited in: 07-dependence-driven-transformations

  • [BWZ94] Olaf Bachmann, Paul S. Wang, and Eugene V. Zima. Chains of Recurrences — a Method to Expedite the Evaluation of Closed-Form Functions. ISSAC 1994, pp. 242-249, 1994. doi:10.1145/190347.190423
    Why and when: The origin of chains of recurrences and their algebra (Lesson 18.3, Lemmas 18.3.2–18.3.5), from symbolic computation rather than compilers.
    Cited in: overview, 03-scalar-evolution-and-trip-counts

  • [CL97] Keith D. Cooper and John Lu. Register Promotion in C Programs. PLDI 1997, pp. 308-319, 1997. doi:10.1145/258915.258943
    Why and when: Scalar (register) promotion of memory references in loops, with measurements on C programs; the motivation and conditions of Lesson 18.1's promotion section.
    Cited in: 01-loop-invariant-code-motion

  • [CSV01] Keith D. Cooper, L. Taylor Simpson, and Christopher A. Vick. Operator Strength Reduction. ACM TOPLAS 23(5), pp. 603-625, 2001. doi:10.1145/504709.504710
    Why and when: Core reading. OSR on SSA (Algorithm 18.4.6) — the algorithm E3's pebble-osr implements. Read §3 with the lesson's worked example; §4 covers LFTR.
    Cited in: overview, 04-strength-reduction

  • [Fea91] Paul Feautrier. Dataflow Analysis of Array and Scalar References. International Journal of Parallel Programming 20(1), pp. 23-53, 1991. doi:10.1007/BF01407931
    Why and when: Core reading. Exact array dataflow by parametric integer programming (Algorithm 18.7.11), which isl's compute_flow in the real-world box performs.
    Cited in: overview, 06-dependence-analysis, 07-dependence-driven-transformations

  • [Fea92] Paul Feautrier. Some Efficient Solutions to the Affine Scheduling Problem. I. One-dimensional Time. International Journal of Parallel Programming 21(5), pp. 313-347, 1992. doi:10.1007/BF01407835
    Why and when: Affine scheduling with the Farkas lemma (Algorithm 18.7.13, Theorem 18.7.17). Part II (multidimensional time) handles programs without one-dimensional schedules.
    Cited in: 07-dependence-driven-transformations

  • [GGL12] Tobias Grosser, Armin Größlinger, and Christian Lengauer. Polly — Performing Polyhedral Optimizations on a Low-Level Intermediate Representation. Parallel Processing Letters 22(4), 1250010, 2012. doi:10.1142/S0129626412500107
    Why and when: How Polly detects SCoPs in LLVM IR and applies isl schedules; read with Lesson 18.7 §7 since Polly is not in this course's LLVM build.
    Cited in: 07-dependence-driven-transformations

  • [GKT91] Gina Goff, Ken Kennedy, and Chau-Wen Tseng. Practical Dependence Testing. PLDI 1991, pp. 15-29, 1991. doi:10.1145/113445.113448
    Why and when: Core reading. ZIV/SIV/MIV classification, exact SIV tests and the Delta test; the paper LLVM's DependenceAnalysis says it implements. Read with Lesson 18.6's SIV section.
    Cited in: overview, 06-dependence-analysis

  • [GSW95] Michael P. Gerlek, Eric Stoltz, and Michael Wolfe. Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form. ACM TOPLAS 17(1), pp. 85-122, 1995. doi:10.1145/200994.201003
    Why and when: The journal version with the full classification (polynomial, geometric, wrap-around, periodic, monotonic) that Lesson 18.2's Definition 18.2.5 uses.
    Cited in: 02-induction-variables

  • [Gup93] Rajiv Gupta. Optimizing Array Bound Checks Using Flow Analysis. ACM Letters on Programming Languages and Systems 2(1-4), pp. 135-150, 1993. doi:10.1145/176454.176507
    Why and when: Range checks eliminated and hoisted by dataflow analysis; the pre-SSA view of Lesson 18.9's first technique.
    Cited in: 09-bounds-check-elimination

  • [IT88] François Irigoin and Rémi Triolet. Supernode Partitioning. POPL 1988, pp. 319-329, 1988. doi:10.1145/73560.73588
    Why and when: The legality condition for tiling (Theorem 18.7.16); read §2–3 after Lesson 18.7's tiling section.
    Cited in: 07-dependence-driven-transformations

  • [KM93] Ken Kennedy and Kathryn S. McKinley. Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution. Languages and Compilers for Parallel Computing (LCPC 1993), LNCS 768, 1993. doi:10.1007/3-540-57659-2_18
    Why and when: Fusion and distribution as graph problems, and the NP-hardness of fusion for locality cited in Lesson 18.7 §5.
    Cited in: 07-dependence-driven-transformations

  • [KRS92] Jens Knoop, Oliver Rüthing, and Bernhard Steffen. Lazy Code Motion. PLDI 1992, pp. 224-234, 1992. doi:10.1145/143095.143136
    Why and when: The PRE formulation that places hoisted code as late as possible; read after Lesson 18.1 to see invariant hoisting as a special case of partial redundancy.
    Cited in: 01-loop-invariant-code-motion

  • [KRS94b] Jens Knoop, Oliver Rüthing, and Bernhard Steffen. Partial Dead Code Elimination. PLDI 1994, pp. 147-158, 1994. doi:10.1145/178243.178256
    Why and when: Sinking generalized: move assignments to where they are live. Read after Lesson 18.1's sinking section for the dataflow framework behind it.
    Cited in: 01-loop-invariant-code-motion

  • [KW95] Priyadarshan Kolte and Michael Wolfe. Elimination of Redundant Array Subscript Range Checks. PLDI 1995 (SIGPLAN Notices 30(6)), pp. 270-278, 1995. doi:10.1145/223428.207160
    Why and when: Range checks on induction variables in SSA form, the idea behind Theorem 18.9.2.
    Cited in: 09-bounds-check-elimination

  • [LA00] Samuel Larsen and Saman Amarasinghe. Exploiting Superword Level Parallelism with Multimedia Instruction Sets. PLDI 2000, pp. 145-156, 2000. doi:10.1145/349299.349320
    Why and when: SLP vectorization: packing isomorphic statements of a basic block (Definition 18.8.6).
    Cited in: 08-vectorization

  • [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: FORTRAN H's optimizer: code moved out of loops into a landing pad (today's preheader). Read it for Lesson 18.1's history; the safety conditions are informal there.
    Cited in: 01-loop-invariant-code-motion

  • [MR79] Etienne Morel and Claude Renvoise. Global optimization by suppression of partial redundancies. Communications of the ACM 22(2), pp. 96-103, 1979. doi:10.1145/359060.359069
    Why and when: Partial redundancy elimination, which subsumes loop-invariant hoisting; cited in Lesson 18.1 §6 as the alternative to a dedicated LICM pass.
    Cited in: 01-loop-invariant-code-motion

  • [NRZ06] Dorit Nuzman, Ira Rosen, and Ayal Zaks. Auto-Vectorization of Interleaved Data for SIMD. PLDI 2006, pp. 132-143, 2006. doi:10.1145/1133981.1133997
    Why and when: Interleaved and strided accesses in GCC's vectorizer; read for Lesson 18.8 §6's interleave groups.
    Cited in: 08-vectorization

  • [PCS05] Sebastian Pop, Albert Cohen, and Georges-André Silber. Induction Variable Analysis with Delayed Abstractions. HiPEAC 2005, LNCS 3793, pp. 218-232, 2005. doi:10.1007/11587514_15
    Why and when: The design of GCC's scalar evolution analysis ("chrecs"); the closest paper to what LLVM's ScalarEvolution does, read after Lesson 18.3.
    Cited in: overview, 02-induction-variables, 03-scalar-evolution-and-trip-counts

  • [Pug91] William Pugh. The Omega Test: a Fast and Practical Integer Programming Algorithm for Dependence Analysis. Supercomputing '91 (ACM/IEEE Conference on Supercomputing), 1991. doi:10.1145/125826.125848
    Why and when: The Omega test: exact integer feasibility by extended Fourier–Motzkin elimination (Lesson 18.6, Algorithm 18.6.14).
    Cited in: 06-dependence-analysis

  • [Pug92] William Pugh. A Practical Algorithm for Exact Array Dependence Analysis. Communications of the ACM 35(8), pp. 102-114, 1992. doi:10.1145/135226.135233
    Why and when: The journal presentation of the Omega test with dark and grey shadows; the more readable of the two for Lesson 18.6.
    Cited in: overview, 06-dependence-analysis

  • [SVE17] Nigel Stephens, Stuart Biles, Matthias Boettcher, Jacob Eapen, Mbou Eyole, Giacomo Gabrielli, Matt Horsnell, Grigorios Magklis, Alejandro Martinez, Nathanael Premillieu, Alastair Reid, Alejandro Rico, and Paul Walker. The ARM Scalable Vector Extension. IEEE Micro 37(2), pp. 26-39, 2017. doi:10.1109/MM.2017.35
    Why and when: Vector-length-agnostic code, predicates and whilelo: the hardware behind Lesson 18.8's scalable-vector box.
    Cited in: 08-vectorization

  • [Tar72] Robert E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1(2), 146–160, 1972. doi:10.1137/0201010
    Why and when: The SCC algorithm that SSA-based induction-variable recognition (Lesson 18.2) and OSR (Lesson 18.4) run over the SSA graph.
    Cited in: exercises, 02-induction-variables, 04-strength-reduction

  • [vEn01] Robert A. van Engelen. Efficient Symbolic Analysis for Optimizing Compilers. Compiler Construction (CC 2001), LNCS 2027, pp. 118-132, 2001. doi:10.1007/3-540-45306-7_9
    Why and when: Brings CRs into compilers for induction-variable analysis; read after Lesson 18.3 §2 to see the CR rewrite rules applied to loops.
    Cited in: 02-induction-variables, 03-scalar-evolution-and-trip-counts

  • [Ver10] Sven Verdoolaege. isl: An Integer Set Library for the Polyhedral Model. Mathematical Software – ICMS 2010, LNCS 6327, pp. 299-302, 2010. doi:10.1007/978-3-642-15582-6_49
    Why and when: The library used in the Omega and polyhedral real-world boxes (via islpy), inside Polly and GCC Graphite. Short; read it before running Lesson 18.7's isl box.
    Cited in: 06-dependence-analysis, 07-dependence-driven-transformations

  • [WL91] Michael E. Wolf and Monica S. Lam. A Data Locality Optimizing Algorithm. PLDI 1991, pp. 30-44, 1991. doi:10.1145/113445.113449
    Why and when: Unimodular transformations (interchange, reversal, skewing) plus tiling, and the skewing that makes a band fully permutable (Lemma 18.7.8).
    Cited in: 07-dependence-driven-transformations

  • [Wol92] Michael Wolfe. Beyond Induction Variables. PLDI 1992, pp. 162-174, 1992. doi:10.1145/143095.143131
    Why and when: Core reading. Induction variables as SCCs of the SSA graph (Algorithm 18.2.6). Read §2–3 after Lesson 18.2 §2; E2's print<pebble-iv> follows its classification.
    Cited in: overview, 02-induction-variables

  • [WWM07] Thomas Würthinger, Christian Wimmer, and Hanspeter Mössenböck. Array Bounds Check Elimination for the Java HotSpot Client Compiler. PPPJ 2007, pp. 125-133, 2007. doi:10.1145/1294325.1294343
    Why and when: BCE in a production JIT with deoptimization; read after Lesson 18.9 for loop-invariant check hoisting in practice.
    Cited in: 09-bounds-check-elimination

Textbooks and monographs

  • [AK02] Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach. Morgan Kaufmann, 2002. Read: Ch. 2–3 (dependence theory and testing), Ch. 4 (preliminary transformations, induction-variable substitution), Ch. 5–6 (vectorization, loop distribution, interchange, fusion).
    Why and when: Core reading. The standard reference for Lessons 18.6–18.8: dependence vectors, the testing hierarchy of GCD/Banerjee/SIV, and the Allen–Kennedy distribution and vectorization algorithms. Read Ch. 2 before Lesson 18.6 if distance and direction vectors are new.
    Cited in: overview, 02-induction-variables, 07-dependence-driven-transformations, 08-vectorization

  • [Ban88] Utpal Banerjee. Dependence Analysis for Supercomputing. Kluwer Academic Publishers, 1988. Read: the chapters on the GCD test and the bounds (Banerjee's inequalities) under direction vectors.
    Why and when: The origin of the inequalities of Lemma 18.6.7 and Theorem 18.6.8 with direction vectors. Consult it for the general (trapezoidal) bounds that the lesson's rectangular case simplifies.
    Cited in: 06-dependence-analysis

  • [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.1.6–9.1.7 (code motion, induction variables and reduction in strength), Ch. 11 (parallelism and locality: affine transforms).
    Why and when: The gentle entry point: §9.1.7 motivates induction variables and strength reduction with a quicksort example; Ch. 11 covers affine partitioning, a polyhedral view of Lesson 18.7.
    Cited in: 02-induction-variables

  • [EaC3] Keith D. Cooper and Linda Torczon. Engineering a Compiler, 3rd ed.. Morgan Kaufmann, 2022. Read: Ch. 10 (scalar optimizations: operator strength reduction on SSA, LFTR).
    Why and when: OSR as a textbook algorithm with the SCC walk of Lesson 18.4; read it if the paper [CSV01] feels dense.
    Cited in: 04-strength-reduction

  • [Muchnick] Steven S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997. Read: §13.2 (loop-invariant code motion), §14.1 (induction variables, strength reduction, linear-function test replacement), §18.5 (unswitching and other loop restructuring).
    Why and when: Core reading. The textbook versions of Lessons 18.1, 18.2 and 18.4 with full pseudo-code on a non-SSA IR: invariance by fixed point, the conditions for moving code, and ACK-style strength reduction. Read §14.1 next to Lesson 18.4's Algorithm 18.4.2.
    Cited in: 01-loop-invariant-code-motion, 02-induction-variables, 04-strength-reduction, 05-loop-restructuring

  • [Sch86] Alexander Schrijver. Theory of Linear and Integer Programming. Wiley, 1986. Read: Ch. 7 (Farkas' lemma and its variants, including the affine form, Corollary 7.1h).
    Why and when: The mathematical background for Lesson 18.7's Theorem 18.7.12; read Ch. 7 if you want the duality proof in full generality.

  • [Wol96] Michael Wolfe. High Performance Compilers for Parallel Computing. Addison-Wesley, 1996. Read: the chapters on data dependence, dependence testing (extreme-value / Banerjee test) and loop restructuring (interchange, skewing, tiling, peeling).
    Why and when: Wolfe's book presents Banerjee's inequalities as the "extreme value test" and treats loop restructuring as a catalogue with legality conditions; a second view of Lessons 18.5–18.7.
    Cited in: 05-loop-restructuring, 06-dependence-analysis

Source code (pinned versions)

  • [GCC-CH] GCC's loop header copying (rotation) — gcc/tree-ssa-loop-ch.cc in gcc-mirror/gcc at releases/gcc-15.1.0.
    Why and when: GCC's form of Lesson 18.5's loop rotation.
    Cited in: 05-loop-restructuring

  • [GCC-Chrec] GCC's chrec algebra — gcc/tree-chrec.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: chrec_fold_plus, chrec_fold_multiply, chrec_apply.
    Why and when: The CR operations of Lemmas 18.3.3–18.3.4 in production code.
    Cited in: 03-scalar-evolution-and-trip-counts

  • [GCC-DataRef] GCC's data dependence analysis — gcc/tree-data-ref.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: compute_affine_dependence, analyze_siv_subscript, analyze_miv_subscript.
    Why and when: ZIV/SIV/MIV subscript tests (Lesson 18.6) as GCC's vectorizer and loop passes use them.
    Cited in: 06-dependence-analysis

  • [GCC-Distribution] GCC's loop distribution — gcc/tree-loop-distribution.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: loop_distribution::build_rdg, loop_distribution::classify_partition, loop_distribution::distribute_loop.
    Why and when: Distribution over a reduced dependence graph, with memset/memcpy partitions (Lesson 18.7).
    Cited in: 07-dependence-driven-transformations

  • [GCC-Graphite] GCC Graphite's isl scheduling and tiling — gcc/graphite-optimize-isl.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: optimize_isl.
    Why and when: GCC's polyhedral optimizer (Lesson 18.7's Graphite box); the driver is gcc/graphite.cc.
    Cited in: 07-dependence-driven-transformations

  • [GCC-Interchange] GCC's loop interchange — gcc/gimple-loop-interchange.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: tree_loop_interchange::valid_data_dependences, should_interchange_loops.
    Why and when: Interchange legality and a stride cost model (Lesson 18.7's GCC box).
    Cited in: 07-dependence-driven-transformations

  • [GCC-Ivcanon] GCC's complete unrolling and peeling — gcc/tree-ssa-loop-ivcanon.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: try_peel_loop.
    Why and when: Full unrolling and complete peeling of loops with small trip counts (Lesson 18.5).
    Cited in: 05-loop-restructuring

  • [GCC-IVOPTS] GCC's induction-variable optimizations — gcc/tree-ssa-loop-ivopts.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: find_induction_variables, find_iv_candidates, may_eliminate_iv.
    Why and when: Biv/giv detection, strength reduction and IV elimination by cost (Lessons 18.2 and 18.4).
    Cited in: 02-induction-variables, 04-strength-reduction

  • [GCC-LIM] GCC's loop invariant motion and store motion — gcc/tree-ssa-loop-im.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: determine_max_movement, hoist_memory_references, execute_sm.
    Why and when: Hoisting to the outermost loop in one step and store motion (Lesson 18.1).
    Cited in: 01-loop-invariant-code-motion

  • [GCC-LoopIV] GCC's RTL induction-variable analysis — gcc/loop-iv.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: iv_analyze_biv.
    Why and when: Classic basic-IV detection on registers (Lesson 18.2's Algorithm 18.2.2).
    Cited in: 02-induction-variables

  • [GCC-Niter] GCC's trip-count computation — gcc/tree-ssa-loop-niter.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: number_of_iterations_exit, number_of_iterations_ne, number_of_iterations_lt.
    Why and when: Trip counts for != and < exits (Theorems 18.3.13–18.3.14).
    Cited in: 03-scalar-evolution-and-trip-counts

  • [GCC-SCEV] GCC's scalar evolution analysis — gcc/tree-scalar-evolution.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: analyze_scalar_evolution, instantiate_scev.
    Why and when: Chains of recurrences on GIMPLE SSA ([PCS05]); compare with LLVM's SCEV after Lesson 18.3.
    Cited in: 02-induction-variables, 03-scalar-evolution-and-trip-counts

  • [GCC-Sink] GCC's code sinking pass — gcc/tree-ssa-sink.cc in gcc-mirror/gcc at releases/gcc-15.1.0.
    Why and when: Sinking statements toward their uses, including out of loops (Lesson 18.1).
    Cited in: 01-loop-invariant-code-motion

  • [GCC-SLP] GCC's SLP vectorizer — gcc/tree-vect-slp.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: vect_build_slp_tree, vect_slp_function.
    Why and when: SLP trees for basic blocks and loops (Lesson 18.8's SLP box).
    Cited in: 08-vectorization

  • [GCC-SLSR] GCC's straight-line strength reduction — gcc/gimple-ssa-strength-reduction.cc in gcc-mirror/gcc at releases/gcc-15.1.0.
    Why and when: Strength reduction outside loops on related multiplications (Lesson 18.4's OSR box).
    Cited in: 04-strength-reduction

  • [GCC-Unswitch] GCC's loop unswitching — gcc/tree-ssa-loop-unswitch.cc in gcc-mirror/gcc at releases/gcc-15.1.0.
    Why and when: Unswitching on invariant conditions (Lesson 18.5).
    Cited in: 05-loop-restructuring

  • [GCC-Vect] GCC's loop vectorizer — gcc/tree-vect-loop.cc in gcc-mirror/gcc at releases/gcc-15.1.0. Symbols: vect_analyze_loop, vect_transform_loop.
    Why and when: GCC's analysis and transformation of vectorizable loops, including epilogues and fully masked loops (Lesson 18.8).
    Cited in: 08-vectorization

  • [GCC-Versioning] GCC's loop versioning for unit strides — gcc/gimple-loop-versioning.cc in gcc-mirror/gcc at releases/gcc-15.1.0.
    Why and when: Versioning on "stride = 1" assumptions (Lesson 18.5 §7).
    Cited in: 05-loop-restructuring

  • [Go-Prove] The Go compiler's prove pass (bounds-check elimination) — src/cmd/compile/internal/ssa/prove.go in golang/go at go1.24.7. Symbols: prove, factsTable.update.
    Why and when: Fact-based BCE with a poset of SSA values (poset.go) and induction-variable limits (loopbce.go); the Go box of Lesson 18.9 prints its decisions.
    Cited in: 09-bounds-check-elimination

  • [LLVM-CE] Constraint elimination over dominating conditions — llvm/lib/Transforms/Scalar/ConstraintElimination.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ConstraintInfo, checkCondition.
    Why and when: Fourier–Motzkin over facts from dominating branches (ConstraintSystem.cpp); the ABCD-like component of LLVM's bounds-check removal in Lesson 18.9.
    Cited in: 09-bounds-check-elimination

  • [LLVM-DA] LLVM's dependence analysis (GKT tests) — llvm/lib/Analysis/DependenceAnalysis.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: DependenceInfo::depends, DependenceInfo::gcdMIVtest, DependenceInfo::banerjeeMIVtest, DependenceInfo::strongSIVtest.
    Why and when: Core reading. The GCD, Banerjee and SIV tests of Lesson 18.6 as LLVM runs them; the header comment names [GKT91] as its source.
    Cited in: overview, 06-dependence-analysis

  • [LLVM-Distribute] Loop distribution driven by LoopAccessAnalysis — llvm/lib/Transforms/Scalar/LoopDistribute.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InstPartitionContainer.
    Why and when: Lesson 18.7's fission in LLVM: the file header explains why it preserves the textual order of memory operations.
    Cited in: 07-dependence-driven-transformations

  • [LLVM-Fuse] Loop fusion — llvm/lib/Transforms/Scalar/LoopFuse.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: dependencesAllowFusion.
    Why and when: Fusion legality (Theorem 18.7.15) with dependence analysis; read after the fusion box.
    Cited in: 07-dependence-driven-transformations

  • [LLVM-IndVars] Induction-variable simplification, LFTR and IV-comparison folding — llvm/lib/Transforms/Scalar/IndVarSimplify.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: IndVarSimplify::linearFunctionTestReplace.
    Why and when: LFTR (Lesson 18.4) and the removal of IV comparisons that makes loop bounds checks vanish (Lesson 18.9; see also SimplifyIndVar.cpp).
    Cited in: 04-strength-reduction, 09-bounds-check-elimination

  • [LLVM-Interchange] Loop interchange — llvm/lib/Transforms/Scalar/LoopInterchange.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: populateDependencyMatrix, isLegalToInterChangeLoops, LoopInterchangeProfitability::isProfitable.
    Why and when: Theorem 18.7.4 on a direction matrix, with a cache-cost profitability model; in the default -O2 pipeline of LLVM 23.
    Cited in: 07-dependence-driven-transformations

  • [LLVM-IRCE] Inductive range-check elimination — llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InductiveRangeCheck::extractRangeChecksFromBranch, InductiveRangeCheckElimination::run.
    Why and when: Algorithm 18.9.8; the file header's example is exactly sum_n of Lesson 18.9.
    Cited in: 09-bounds-check-elimination

  • [LLVM-IVDesc] Induction and reduction descriptors used by the vectorizer — llvm/lib/Analysis/IVDescriptors.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: InductionDescriptor::isInductionPHI, RecurrenceDescriptor::isReductionPHI.
    Why and when: How LLVM classifies header phis as inductions or reductions (Lessons 18.2 and 18.8).
    Cited in: 02-induction-variables

  • [LLVM-LAA] LoopAccessAnalysis — llvm/lib/Analysis/LoopAccessAnalysis.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: MemoryDepChecker::isDependent, MemoryDepChecker::Dependence::isSafeForVectorization, RuntimePointerChecking::generateChecks.
    Why and when: Core reading. Byte distances, the safe VF and runtime checks (Lesson 18.6); used by the vectorizer, loop distribution and versioning.
    Cited in: overview, 06-dependence-analysis

  • [LLVM-LICM] LLVM's loop-invariant code motion, sinking and scalar promotion — llvm/lib/Transforms/Scalar/LICM.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: llvm::hoistRegion, llvm::sinkRegion, llvm::canSinkOrHoistInst, llvm::promoteLoopAccessesToScalars.
    Why and when: The production LICM with MemorySSA; compare hoistRegion with E1's pass after Lesson 18.1.
    Cited in: overview, 01-loop-invariant-code-motion

  • [LLVM-LoopPredication] Loop predication of guards — llvm/lib/Transforms/Scalar/LoopPredication.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LoopPredication::widenICmpRangeCheck.
    Why and when: Algorithm 18.9.9; the header comment explains why SCEV facts must not be used circularly to widen a guard.
    Cited in: 09-bounds-check-elimination

  • [LLVM-LoopRotate] Loop rotation — llvm/lib/Transforms/Utils/LoopRotationUtils.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: llvm::LoopRotation.
    Why and when: Algorithm 18.5.2 in production form; read after Lesson 18.5's rotation box.
    Cited in: 05-loop-restructuring

  • [LLVM-LSR] LLVM's Loop Strength Reduce — llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LSRInstance::SolveRecurse, LSRInstance::NarrowSearchSpaceUsingHeuristics.
    Why and when: The cost-driven formula search of Lesson 18.4; read the file header's overview first.
    Cited in: 04-strength-reduction

  • [LLVM-LV] The loop vectorizer — llvm/lib/Transforms/Vectorize/LoopVectorize.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LoopVectorizePass::processLoop, LoopVectorizationPlanner::computeBestVF, LoopVectorizationPlanner::selectInterleaveCount, LoopVectorizationCostModel::isEpilogueVectorizationProfitable.
    Why and when: Core reading. Algorithm 18.8.3 in production; start at processLoop and follow the planner (Lesson 18.8).
    Cited in: overview, 08-vectorization

  • [LLVM-LVLegality] Vectorization legality — llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LoopVectorizationLegality::canVectorize, LoopVectorizationLegality::canVectorizeWithIfConvert, LoopVectorizationLegality::canFoldTailByMasking.
    Why and when: What the vectorizer accepts: inductions, reductions, if-convertible control flow, masked tails.
    Cited in: 08-vectorization

  • [LLVM-LVLICM] Loop versioning to enable LICM of possibly aliased memory — llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp in llvm/llvm-project at llvmorg-23.1.2.
    Why and when: Versioning (Lesson 18.5) used for LICM (Lesson 18.1): a runtime no-alias check buys hoisting.
    Cited in: 01-loop-invariant-code-motion, 05-loop-restructuring

  • [LLVM-MustExec] Guaranteed-execution queries used by LICM — llvm/lib/Analysis/MustExecute.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: SimpleLoopSafetyInfo::isGuaranteedToExecute, ICFLoopSafetyInfo::isGuaranteedToExecute.
    Why and when: Definition 18.1.3 in code; read after the "guaranteed execution" part of Lesson 18.1.
    Cited in: 01-loop-invariant-code-motion

  • [LLVM-Peel] Loop peeling — llvm/lib/Transforms/Utils/LoopPeel.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: llvm::peelLoop, llvm::canPeel.
    Why and when: Peeling first and last iterations (Lesson 18.5); the count heuristics are in computePeelCount.
    Cited in: 05-loop-restructuring

  • [LLVM-SCEV] LLVM's ScalarEvolution analysis — llvm/lib/Analysis/ScalarEvolution.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: ScalarEvolution::createAddRecFromPHI, ScalarEvolution::howFarToZero, ScalarEvolution::howManyLessThans, ScalarEvolution::isKnownPredicateAt.
    Why and when: Core reading. Add recurrences, trip counts and the predicate queries E5 uses; read the trip-count functions after Lesson 18.3 §2.
    Cited in: overview, 02-induction-variables, 03-scalar-evolution-and-trip-counts, 09-bounds-check-elimination

  • [LLVM-SCEVExpr] The SCEV expression classes — llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h in llvm/llvm-project at llvmorg-23.1.2. Symbols: SCEVAddRecExpr, SCEVUnknown.
    Why and when: The data structure behind the CR notation of Lesson 18.3; SCEVAddRecExpr::evaluateAtIteration is Definition 18.3.1's evaluation.
    Cited in: 03-scalar-evolution-and-trip-counts

  • [LLVM-SLP] The SLP vectorizer — llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: BoUpSLP::buildTree, BoUpSLP::getTreeCost, SLPVectorizerPass::vectorizeStores.
    Why and when: Algorithm 18.8.7 in production; the tree building and cost model behind the SLP box.
    Cited in: 08-vectorization

  • [LLVM-UAJ] Unroll-and-jam — llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp in llvm/llvm-project at llvmorg-23.1.2.
    Why and when: Unrolling an outer loop and fusing the inner copies: a combination of Lessons 18.5 and 18.7.
    Cited in: 05-loop-restructuring

  • [LLVM-Unroll] The loop unrolling transformation — llvm/lib/Transforms/Utils/LoopUnroll.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: llvm::UnrollLoop.
    Why and when: The IR surgery of unrolling that E4 reimplements for full unrolling (Lesson 18.5).
    Cited in: 05-loop-restructuring

  • [LLVM-UnrollPass] Unrolling heuristics and thresholds — llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: llvm::computeUnrollCount.
    Why and when: Where full, partial and runtime unrolling are decided; the quiz asks for its default threshold.
    Cited in: 05-loop-restructuring

  • [LLVM-Unswitch] Trivial and non-trivial loop unswitching — llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: unswitchTrivialBranch, unswitchNontrivialInvariants.
    Why and when: Algorithm 18.5.10 with the cost budget of Lesson 18.5 §5.
    Cited in: 05-loop-restructuring

  • [LLVM-ValueTracking] Speculation safety and guaranteed transfer of execution — llvm/lib/Analysis/ValueTracking.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: llvm::isSafeToSpeculativelyExecute, llvm::isGuaranteedToTransferExecutionToSuccessor.
    Why and when: The two predicates E1 calls; read their cases (division, loads, calls) after Lesson 18.1 §2.
    Cited in: 01-loop-invariant-code-motion

  • [LLVM-Versioning] Loop versioning with runtime memory checks — llvm/lib/Transforms/Utils/LoopVersioning.cpp in llvm/llvm-project at llvmorg-23.1.2. Symbols: LoopVersioning::versionLoop, LoopVersioning::annotateLoopWithNoAlias.
    Why and when: Algorithm 18.5.12; the checks come from LoopAccessAnalysis (Lesson 18.6).
    Cited in: 05-loop-restructuring

Official documentation and specifications

  • [LLVM-Vectorizers] Auto-Vectorization in LLVM. LLVM 23.1.2. link
    Why and when: The user-level overview of the loop and SLP vectorizers, with pragmas and remarks; read it before Lesson 18.8.
    Cited in: 08-vectorization

  • [LLVM-VPlan] Vectorization Plan. LLVM 23.1.2. link
    Why and when: The design of VPlan (recipes, regions, planning); read after Lesson 18.8's VPlan box.
    Cited in: 08-vectorization

  • [Polly-Docs] Polly — The Architecture. LLVM 23.1.2. link
    Why and when: Where Polly sits in the pipeline and how SCoPs are detected, optimized and code-generated; Lesson 18.7 §7 relies on it because Polly is not in this course's LLVM build.
    Cited in: 06-dependence-analysis, 07-dependence-driven-transformations