Chapter 18 · Loop Optimizations¶

Part 4 · Optimization · about 4–5 weeks · Previous: Ch 17 · Next: Ch 19

The problem¶

Programs spend their time in loops, so a compiler earns most of its speedup there. Given a function in SSA form whose loops are in canonical shape (loop-simplify form and LCSSA, Ch 15), this chapter asks: which computations can leave a loop (loop-invariant code motion, sinking, scalar promotion); which values change predictably from one iteration to the next (induction variables, chains of recurrences, LLVM's ScalarEvolution) and how many iterations run (trip counts); how to replace expensive per-iteration arithmetic by cheaper recurrences (strength reduction, LSR, LFTR); how to reshape loops so that other optimizations apply (rotation, peeling, unrolling, unswitching, versioning); which iterations touch the same memory (dependence analysis: GCD, Banerjee, SIV, Omega, runtime checks); which reorderings that knowledge permits (fusion, fission, interchange, tiling, the polyhedral model); how to run several iterations at once on SIMD hardware (the loop vectorizer, VPlan, SLP, predication, scalable vectors); and how to remove the bounds checks of a safe language without changing where it traps. The inputs are LLVM IR functions (and, for the dependence tests, affine loop nests); the outputs are transformed IR and the analyses (ScalarEvolution, DependenceAnalysis, LoopAccessAnalysis) that justify each transformation. In LLVM 23 these passes run in the middle of the -O2 pipeline, after SSA construction (Ch 16) and the scalar cleanups of Ch 17, and they rely on alias analysis (Ch 19).

What you will be able to do¶

Decide by hand which instructions LICM may hoist, sink or promote in a given loop, and prove why rotation changes the answer (speculation vs guaranteed execution).
Classify every value of a loop as linear, polynomial, geometric, wrap-around, periodic or monotonic, compute its chain of recurrences, and read LLVM's print<scalar-evolution> output, including no-wrap flags and trip counts of loops that wrap.
Apply Allen–Cocke–Kennedy strength reduction and operator strength reduction to a loop and explain what LLVM's LSR and LFTR add.
Compute dependence distance and direction vectors, run the GCD, Banerjee, SIV and Omega tests by hand, and say which one is exact where.
Decide whether fusion, distribution, a loop permutation or tiling is legal from the distance vectors, find the skewing that makes tiling legal, and derive a Feautrier schedule for a small nest.
Predict the VF, interleave count, runtime checks and epilogue of LLVM's loop vectorizer for a simple loop, read a VPlan, and explain masking, tail folding and scalable vectors.
Implement LICM, SSA-based induction-variable recognition with a printer, operator strength reduction, and (★) full unrolling and bounds-check elimination as opt plugin passes, and measure classic against SSA-based techniques in the comparison lab.
Find where LLVM 23 (and GCC 15) implement each technique and read the code.

Prerequisites: Ch 12 (new-pass-manager plugin passes, lit + FileCheck), Ch 15 (dominator trees, natural loops, loop-simplify form, LCSSA), Ch 16 (SSA form, Tarjan's SCCs on the SSA graph) and Ch 17 (dead-code elimination, partial redundancy elimination). Chapter 19 (alias analysis) is useful background for the memory side of LICM and for LoopAccessAnalysis; the lessons state what they need from it.

Notation¶

Shared notation follows the house notation: §1 (sets, functions, logic), §3 (graphs and CFGs) and §4 (dominance and loops). In this chapter:

Symbol	Meaning
\(L\), \(h\), \(P\), \(X\)	a loop, its header, its preheader, an exit block (loop-simplify form, Ch 15)
\(\mathrm{TC}\), \(\mathrm{BTC}\)	trip count (body executions) and backedge-taken count \(= \mathrm{TC} - 1\) (Definition 18.3.9)
\(\{c_0,+,c_1,+,\dots,+,c_k\}\)	chain of recurrences: the sequence \(f(n) = \sum_j c_j \binom{n}{j}\) (Definition 18.3.1)
\(\{a,*,r\}\)	geometric chain of recurrences: \(f(n) = a \cdot r^n\)
\(\{a,+,b\}\langle nuw, nsw \rangle\)	an LLVM add recurrence with no-unsigned-wrap / no-signed-wrap flags (Definition 18.3.7)
\(\Delta^k f(0)\)	\(k\)-th forward difference of a sequence at 0 (Lemma 18.3.2)
\(w\)	bit width of an integer type; arithmetic is modulo \(2^w\)
\((i, c, d)\)	a derived induction variable \(c \cdot i + d\) of basic induction variable \(i\) (Definition 18.2.1)
\(\mathbf{i} = (i_1, \dots, i_d)\), \(\mathcal{I}\)	iteration vector and iteration space of a depth-\(d\) nest (Definition 18.6.1)
\(\mathbf{i} \prec \mathbf{i}'\), \(\mathbf{d} \succ \mathbf{0}\)	lexicographic order; lexicographically positive
\(\mathbf{d}\), \(\psi\)	distance vector (sink minus source) and direction vector over \(\{<, =, >, *\}\) (Definition 18.6.3)
\(t^+ = \max(t, 0)\), \(t^- = \max(-t, 0)\)	positive and negative parts (Lemma 18.6.7)
ZIV, SIV, MIV	subscripts with zero, one, several index variables (Definition 18.6.10)
\(\delta\), \(VF\), \(IC\), \(UF\)	byte dependence distance (Definition 18.6.16); vectorization factor, interleave count, unroll factor of a vector plan (Definition 18.8.1)
\(\mathit{vscale}\)	the run-time multiple of a scalable vector type `<vscale x k x T>` (Definition 18.8.8)
\(\pi(\mathbf{d})\)	a distance vector with its components permuted by loop permutation \(\pi\) (Theorem 18.7.4)
\(\mathcal{D}_S\), \(\theta_S\)	iteration domain and affine schedule of statement \(S\) (Definition 18.7.9)
\(u \xrightarrow{c} v\)	an inequality-graph edge meaning \(v \le u + c\) (Definition 18.9.4)

Numbered statements are N.k.m (chapter, lesson, counter), as in NOTATION.md §9.

Technique map¶

Family	Techniques (origin)	Lesson
Loop-invariant code motion	Hoisting with speculation safety and guaranteed execution (Lowry & Medlock 1969; Allen & Cocke 1972; LLVM LICM with MemorySSA), sinking (partial dead-code elimination, Knoop, Rüthing & Steffen 1994), scalar promotion (Cooper & Lu 1997)	18.1
Induction variables	Classic detection of basic and derived IVs (Allen, Cocke & Kennedy 1981), SSA-based recognition by SCCs (Wolfe 1992; Gerlek, Stoltz & Wolfe 1995)	18.2
Scalar evolution	Chains of recurrences (Bachmann, Wang & Zima 1994; van Engelen 2001), LLVM ScalarEvolution and GCC's chrecs (Pop, Cohen & Silber 2005), trip counts with overflow	18.3
Strength reduction	Allen–Cocke–Kennedy (1981), operator strength reduction on SSA (Cooper, Simpson & Vick 2001), LLVM Loop Strength Reduce, linear-function test replacement	18.4
Loop restructuring	Rotation, peeling, unrolling, unswitching (Allen & Cocke 1972), versioning with runtime checks	18.5
Dependence analysis	GCD test and Banerjee's inequalities (Banerjee 1988), SIV tests and the Delta test (Goff, Kennedy & Tseng 1991), the Omega test (Pugh 1991), LoopAccessAnalysis runtime checks (LLVM)	18.6
Dependence-driven transformations	Fusion and fission (Allen & Kennedy 1987; Kennedy & McKinley 1993), interchange (Allen & Kennedy 1984), strip-mining, skewing and tiling (Irigoin & Triolet 1988; Wolf & Lam 1991), the polyhedral model (Feautrier 1991, 1992; Pluto 2008; isl 2010; Polly 2012)	18.7
Vectorization	The loop vectorizer with legality, cost model, interleaving, runtime checks and epilogues (Allen & Kennedy 1987; LLVM), VPlan (LLVM), SLP (Larsen & Amarasinghe 2000), predication, masking and scalable vectors (Allen, Kennedy, Porterfield & Warren 1983; Arm SVE 2017)	18.8
Bounds-check elimination	Range-based elimination (Gupta 1993; Kolte & Wolfe 1995), ABCD (Bodík, Gupta & Sarkar 2000), IRCE and loop predication (LLVM)	18.9

Software pipelining (modulo scheduling) is a loop optimization too, but it overlaps iterations at the level of machine instructions and needs a scheduler's resource model; the syllabus places it with instruction scheduling (Chapter 23, Rau's iterative modulo scheduling).

flowchart LR
  LICM[LICM: hoist, sink, promote<br/>Lowry-Medlock 1969] -->|needs| ROT[Rotation]
  CIV[Classic IVs<br/>ACK 1981] -->|SSA SCCs| SIV2[SCC classification<br/>Wolfe 1992, GSW 1995]
  SIV2 -->|closed forms| CR[Chains of recurrences<br/>BWZ 1994]
  CR --> SCEV[LLVM ScalarEvolution<br/>GCC chrecs 2005]
  SCEV --> TC[Trip counts]
  CIV --> ACK[ACK strength reduction]
  ACK -->|on SSA, one walk| OSR[OSR<br/>CSV 2001]
  SCEV --> LSR[LSR: target cost] --> LFTR[LFTR]
  TC --> UNR[Unrolling, peeling]
  ROT --> UNS[Unswitching]
  GCD[GCD test] -->|bounds + directions| BAN[Banerjee 1988]
  BAN -->|exact cases| GKT[SIV and Delta tests<br/>GKT 1991]
  GKT -->|exact integer test| OMEGA[Omega test<br/>Pugh 1991]
  OMEGA -->|integer sets| ISL[isl 2010]
  SCEV --> LAA[LoopAccessAnalysis<br/>runtime checks] --> VER[Versioning]
  BAN --> XF[Fusion, fission, interchange]
  XF -->|skewing + full permutability| TILE[Tiling<br/>IT 1988, WL 1991]
  ISL --> POLY[Polyhedral model<br/>Feautrier 1991-92, Pluto, Polly]
  LAA --> LV[Loop vectorizer] -->|explicit plans| VPLAN[VPlan]
  LV -->|if-conversion, masks| PRED[Predication, scalable vectors]
  SLP[SLP<br/>Larsen-Amarasinghe 2000] --- LV
  SCEV --> BCE[Range-based BCE]
  BCE -->|inequality graph| ABCD[ABCD 2000]
  BCE -->|split / widen| IRCE[IRCE, loop predication]

Who uses what¶

System	Technique	Notes
LLVM 23	LICM with MemorySSA (hoist, sink, promote); ScalarEvolution; IndVarSimplify with LFTR; LSR; rotation, peeling, full/runtime unrolling, SimpleLoopUnswitch, LoopVersioning; DependenceAnalysis (GKT tests; Banerjee off by default); LoopAccessAnalysis; loop-distribute, loop-fusion, loop-interchange (in the default `-O2` pipeline); loop vectorizer with VPlan and epilogue vectorization; SLP; IRCE, loop predication, constraint elimination	lessons 18.1–18.9, §7 of each
GCC 15	`lim` (invariant and store motion), `sink`, `ivopts` (bivs/givs, IV selection by cost), chrecs and `niter`, SLSR, `ch` (rotation), `cunroll`, unswitching, `tree-data-ref` dependence tests, loop distribution with `memset`/`memcpy` partitions, `linterchange`, the vectorizer (versioning for alias, vector epilogues, fully masked loops), SLP; Graphite with isl	GCC boxes in lessons 18.1–18.8
Polly (LLVM project)	SCoP detection, isl-based dependences and scheduling (Pluto-style), tiling, code generation from isl ASTs	not in this course's LLVM build; lesson 18.7
Go 1.24 (`cmd/compile`)	`prove` pass: bounds-check elimination with facts, a poset of SSA values and induction-variable limits (`loopbce.go`)	lesson 18.9
HotSpot C2 (JDK 21)	range-check elimination by loop splitting, loop predication with deoptimization	lesson 18.9
Clang (OpenMP)	`#pragma omp tile` / `unroll` as programmer-directed loop transformations	lesson 18.7
isl / islpy	integer sets and relations, exact dataflow (`compute_flow`), scheduling, AST generation	lessons 18.6–18.7

Comparison¶

The fixed columns follow docs/authoring/DEPTH_CONTRACT.md §3 item 8; every lesson repeats its own rows (and discusses them in its §8).

LICM and scalar promotion (lesson 18.1)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Hoisting (invariance and speculation safety)	Moves every invariant pure computation; speculation or guaranteed execution decides trapping ones; loads need alias analysis	\(O(d\,n)\) plus alias queries (Proposition 18.1.14)	Preheader code; misses what alias analysis cannot prove (fix: versioning)	Low without memory, medium with alias analysis	Every optimizing compiler, several times per pipeline (LLVM `licm`, GCC `lim`)
Sinking	Moves computations used only after the loop into the exits	\(O(d\,n)\)	Exit-block code with LCSSA phis	Low (needs LCSSA)	LLVM LICM's first phase, GCC `sink`
Scalar promotion	Removes all loads/stores of one must-aliased location	\(O(d\,(n + m\ell))\) plus SSA construction	Registers instead of memory traffic; blocked by any may-alias access or call	Medium (SSA update, thread-safety rule)	Globals and pointer-accumulated values in hot loops

Induction variables (lesson 18.2)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Classic induction-variable detection	Basic IVs and affine functions of one basic IV; misses polynomial, geometric, wrap-around, periodic, monotonic, and combinations of two families	\(O(N)\) typical, \(O(N^2)\) worst (Proposition 18.2.11)	Triples \((i, c, d)\) for strength reduction	Low	Historical strength reduction; GCC's `ivopts` vocabulary (bivs/givs)
SSA-based recognition (SCC classification)	Every linear IV, plus the five classes of Definition 18.2.5	\(O(N + E)\)	A class and a chain of recurrences per value	Medium (Tarjan + CR algebra)	The core of LLVM's and GCC's scalar evolution; `pebble-iv`

Chains of recurrences, SCEV, trip counts (lesson 18.3)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Chains of recurrences	Exact closed forms of polynomial (and geometric) sequences; closed under \(+\), \(\times\), shift	\(O(k)\)–\(O(k^2)\) per operation, \(k \le 3\) typically	CRs readable as sequences; evaluation by additions only	Low (a tuple and four lemmas)	The representation behind every scalar-evolution analysis; `pebble-iv`
LLVM ScalarEvolution	CRs embedded in a canonical symbolic language, with ranges and no-wrap flags; no geometric CRs	Lazy, cached, near-linear	Printable expressions, `Exits:` values, ranges; "Unknown" when it gives up	High (canonicalization, flags, predicates)	Every LLVM loop pass (indvars, LSR, unroll, vectorize, LAA, DA)
Trip counts	Exact for `≠` (congruence) and `<` without wrap; predicated or max otherwise	\(O(w^2)\) bit operations	Exact count, constant max, symbolic max, or "Unpredictable"	Medium (all predicates, signedness, wrap)	Unrolling, vectorization, LFTR, BCE, loop deletion

Strength reduction (lesson 18.4)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Allen–Cocke–Kennedy strength reduction	Derived IVs \(c\cdot i + d\) of one family; one temporary per (c, d)	\(O(N)\) typical after classic IV detection	New IVs updated by additions; needs DCE and LFTR to pay off fully	Low	Classic compilers; GCC ivopts' candidates
Operator strength reduction	Every candidate \(\mathit{iv} \times \mathit{rc}\), \(\mathit{iv} \pm \mathit{rc}\) found in one SSA walk, chains through several IVs	\(O(N + E)\)	Reduced IVs shared through a hash table; integrated LFTR	Medium (Tarjan + Reduce/Apply)	SSA teaching compilers; `pebble-osr`
LLVM Loop Strength Reduce	Target-aware: chooses IVs and addressing-mode formulae to minimize registers and instructions	Pruned exponential search	Near-optimal register use on real targets; heuristic	Very high	LLVM's backend-facing IV optimization
Linear-function test replacement	Rewrites the exit test onto another IV when the trip count is exact and the IV cannot wrap	\(O(1)\) after SCEV	Frees the old counter	Low with SCEV	LLVM `indvars`, GCC `ivopts`

Loop restructuring (lesson 18.5)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Loop rotation	Enables LICM of trapping code and a single branch per iteration	\(O(S)\); no run-time cost	Guard + do-while; header duplicated	Medium (phis, LCSSA)	Every loop, early in the pipeline
Loop peeling	Removes first/last-iteration special cases; turns wrap-around variables into IVs	\(O(kS)\)	\(k\) copies before the loop	Medium	First-iteration conditions, alignment, short loops
Loop unrolling	Exposes ILP, amortizes loop overhead, enables SLP; full unrolling removes the loop	\(O(uS)\); runtime version adds a trip-count computation	Larger code; remainder loop	Medium (full) to high (runtime + remainder)	Small hot loops; vectorizer interleaving
Loop unswitching	Removes invariant branches from the loop body	\(O(2^m S)\) worst	Duplicate loops; bounded by a cost budget	High (non-trivial, SSA repair)	Loops with invariant flags
Loop versioning	Enables optimizations under unprovable assumptions (no alias, stride 1, no wrap)	\(O(S)\) + \(O(g^2)\) run-time checks	Two copies + a check block	Medium (given LAA)	Vectorization, LICM of maybe-aliased loads

Dependence analysis (lesson 18.6)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
GCD test	Exact for integrality, ignores bounds; proves independence only by divisibility	\(O(md)\) gcds	Yes/no (+ per-level `=` removal)	Very low	First filter; MIV subscripts (LLVM `gcdMIVtest`)
Banerjee test	Uses bounds and directions, ignores integrality; subscript by subscript	\(O(md\,3^d)\) with refinement	Direction vectors	Low	MIV subscripts, direction vectors for interchange
SIV tests and the Delta test	Exact for ZIV and SIV (the common case); coupled subscripts via propagation	\(O(md)\)	Exact distances	Medium (many cases)	LLVM `DependenceAnalysis`, GCC `tree-data-ref.cc`
Omega test	Exact integer feasibility for any affine system	Exponential worst, fast in practice	Yes/no, or exact dependence relations (with isl)	High	Polyhedral compilers (via isl)
Runtime checks (LAA)	Constant distances exact; unknown aliasing deferred to a run-time check	Linear-ish	Safe / safe with checks / unsafe, MaxSafeVF	Medium	LLVM vectorizer, distribution, versioning

Dependence-driven transformations (lesson 18.7)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Loop fusion and fission	Separates cycles from vectorizable work; merges loops for reuse	SCCs linear; fusion check per dependence	More (or fewer) loops; remarks on preventing dependences	Medium	Enabling vectorization; locality of producer–consumer loops
Loop interchange and permutation	Any legal order of a perfect nest	\(O(Dd)\) per candidate	Same body, different loop order	Medium (IR surgery on headers/latches)	Unit-stride inner loops; outer-loop parallelism
Strip-mining, skewing and tiling	Cache blocking; wavefront parallelism after skewing	Cheap legality; bounds by projection	Deeper nests with `min`/`max` bounds	Medium to high	Dense linear algebra, stencils
The polyhedral model	Exact dependences and optimal affine schedules for SCoPs	Expensive (integer programming)	Arbitrary affine restructuring in one step	Very high (isl, code generation)	HPC kernels; Polly, Graphite, MLIR affine

Vectorization (lesson 18.8)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Loop vectorization	Innermost loops with analyzable accesses, reductions, inductions	Cost model per VF; LAA quadratic in accesses	Vector body + checks + epilogue + remainder; good remarks	Very high	Numeric loops at `-O2`
VPlan	Makes decisions explicit and composable	Linear per plan	Printable plans in release builds	High (framework)	LLVM's vectorizer internals
SLP vectorization	Straight-line isomorphic code, unrolled loops, struct fields	Near linear in practice	Tree-by-tree decisions, cost in remarks	High	Unrolled code, complex arithmetic, small structs
Predication, masking and scalable vectors	Loops with `if`s; no remainder; vector-length agnostic code	Mask computation in every iteration	Masked intrinsics, `vscale`	Medium on top of the vectorizer	AVX-512, SVE, RVV targets

Bounds-check elimination (lesson 18.9)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Range-based bounds-check elimination	Affine indices with known ranges; defeated by wrap-around and unrelated bounds	One analysis query per check	Checks disappear; kept checks unchanged	Low given SCEV (E5 is ~80 lines)	AOT compilers of safe languages
ABCD	Chains of inequalities between variables, including loop-carried ones	Demand-driven, cheap per check	Proof or nothing	Medium (e-SSA, cycle handling)	JITs; Go's `prove` in poset form
IRCE and loop predication	Checks whose bounds are unrelated to the loop bound	Linear	IRCE: more loops; predication: one invariant check	Medium to high	JITs with deoptimization (predication); AOT (IRCE)

Comparison-lab results (reproduce with build/<preset>/bin/ch18-loops and the commands in labs/ch18-loops/SPEC.md; reference solution, LLVM 23.1.2): on corpus/ivs.ll classic detection finds 34 induction variables and the SCC method 58 (37 linear, 11 polynomial, 4 geometric, 1 wrap-around, 2 periodic, 3 monotonic), agreeing with ScalarEvolution on all 47 comparable ones; on corpus/sr.ll classic strength reduction and pebble-osr both remove the multiplications of stride and twice, and only pebble-licm,pebble-osr removes the one in matrix (Lesson 18.4 §3 has the full table); of the 67 dependence problems of corpus/deps.dep, the GCD test proves 4 independent, Banerjee's test 11, and 16 are exactly independent.

Route through this chapter¶

Step	What	Techniques	How it is exercised
1	Lesson 18.1	hoisting, sinking, scalar promotion	drill `licm-legality`; Pebble implements hoisting: exercise E1 (`pebble-licm`, ★ loads)
2	Lesson 18.2	classic IV detection, SCC classification	drill `scev-form`; exercise E2 (`pebble-iv`, `print<pebble-iv>`); lab Part A (classic detection)
3	Lesson 18.3	chains of recurrences, ScalarEvolution, trip counts	drills `scev-form`, `trip-count`; E2's CRs are checked against SCEV
4	Lesson 18.4	ACK, OSR, LSR, LFTR	exercise E3 (`pebble-osr`); lab Part B (classic SR); LSR and LFTR: theory + real-world boxes
5	Lesson 18.5	rotation, peeling, unrolling, unswitching, versioning	★ exercise E4 (`pebble-unroll`); the rest: theory + real-world boxes
6	Lesson 18.6	GCD, Banerjee, SIV/Delta, Omega, runtime checks	drill `dependence-test`; lab Part C (GCD and Banerjee vs exact)
7	Lesson 18.7	fusion/fission, interchange, tiling, polyhedral model	drill `interchange-legal`; isl real-world box
8	Lesson 18.8	loop vectorizer, VPlan, SLP, predication and scalable vectors	theory + real-world boxes (clang, opt, GCC, AArch64 SVE)
9	Lesson 18.9	range-based BCE, ABCD, IRCE and loop predication	★ exercise E5 (`pebble-bce` on Pebble's own bounds checks)
10	Exercises	E1–E3, ★ E4–E5	`./course test 18`
11	Comparison lab `labs/ch18-loops/SPEC.md`	classic IVs vs SCC vs SCEV; classic SR vs OSR; GCD vs Banerjee vs exact	`ch18.lab.*`
12	Theory test	all	`./course quiz 18` (≥ 80 % to finish)

Practice and check¶

./course drill licm-legality --difficulty medium     # hoist or stay? --solution shows the reasoning
./course drill scev-form --seed 3 --solution         # chains of recurrences, step by step
./course drill trip-count --difficulty hard          # 8-bit loops that wrap
./course drill dependence-test --difficulty hard     # GCD, Banerjee and exact distances
./course drill interchange-legal --difficulty hard   # which loop orders are legal
./course flash 18                                    # daily, a few minutes
./course quiz 18                                     # after the lessons
./course test 18                                     # after the exercises
./course status                                      # done = quiz ≥ 80 % and tests pass

References¶

The chapter's annotated bibliography (papers, textbook sections, pinned LLVM 23.1.2, GCC 15 and Go source files, and documentation) is in references.md. Start with: [ACK81] and [Wol92] (induction variables, classic vs SSA), [BWZ94] and [PCS05] (chains of recurrences and scalar evolution), [CSV01] (operator strength reduction), [GKT91] and [Pug92] (dependence testing), [AK02] (the dependence-based view of the whole chapter), [Fea91] (exact dataflow), and [BGS00] (ABCD). The LLVM files to keep open are [LLVM-LICM], [LLVM-SCEV], [LLVM-DA], [LLVM-LAA] and [LLVM-LV].