Flashcards — Chapter 18¶
110 cards. Review them with spaced repetition in the terminal (./course flash 18) or export them to Anki (./course flash export 18). Here, click a card to reveal its back.
licm-hoist¶
LICM hoisting: when is an instruction loop-invariant (Definition 18.1.1)?
Every operand is a constant, defined outside the loop, or itself loop-invariant (a fixed point computed in dominator-tree order); for a load, additionally no instruction in the loop may write the loaded location.
LICM hoisting: the two alternative safety conditions (Theorem 18.1.10)?
The instruction is safe to speculate (cannot trap, no UB, no side effect: isSafeToSpeculativelyExecute) OR guaranteed to execute (its block dominates every exiting block and latch, and nothing that can run before it in an iteration — in its block, or in any loop block it does not dominate — may fail to transfer control).
LICM hoisting: why does loop rotation matter?
In a top-tested loop the header is the only exiting block, so body blocks do not dominate it and nothing in the body is guaranteed to execute. After rotation the body dominates the latch/exit test, so trapping invariant code (a / b, loads) can be hoisted.
LICM hoisting: cost (Proposition 18.1.14)?
One walk over the loop per round in dominator-tree order; visiting operands before users (Lemma 18.1.9) makes one round enough for pure code, O(instructions) plus alias queries (MemorySSA) for loads.
licm-sink¶
LICM sinking: what is a sinkable instruction (Definition 18.1.5)?
A pure instruction with no use inside the loop whose outside uses are LCSSA phis in exit blocks reached from exiting blocks its block dominates; its operands are available at those exits.
LICM sinking: why visit blocks in dominator-tree postorder, instructions last to first?
So an instruction is examined after all its in-loop users have been sunk; a user sunk first no longer keeps it in the loop (Algorithm 18.1.6).
LICM sinking: why is sinking a load past the loop legal in last (t = a[i]*k)?
The sunk copy runs once in the exit block, on the last iteration's index (via an LCSSA phi), and nothing in the loop writes memory; it executes only where the original did (Theorem 18.1.12). Savings: 3n executions become 3.
scalar-promotion¶
Scalar promotion: what does it do (Algorithm 18.1.8)?
Replaces the loads and stores of one memory location in a loop by an SSA value: one load in the preheader, phis in the loop, one store per exit block if the loop stored it.
Scalar promotion: the three conditions of Definition 18.1.7?
(i) every access that may alias p must-aliases it and is simple; (ii) loading p in the preheader is safe; (iii) the exit stores add no store on a path that had none, or p is thread-local.
Scalar promotion: why does restrict matter for *total += a[i]?
Without it, a[i] may alias *total, so condition (i) fails; LLVM remarks that the loop may invalidate the load. With restrict: 2n memory operations on *total become 2.
classic-iv¶
Classic IV detection: basic vs derived induction variable (Definition 18.2.1)?
Basic: the only in-loop assignments add or subtract a loop-invariant amount. Derived: an affine function c·i + d of a basic IV i, recorded as the triple (i, c, d).
Classic IV detection: what does it miss?
Everything non-linear: polynomial values (s = s + i), geometric ones (g = 2g), wrap-around variables (p = phi(n, i)), periodic and monotonic ones. On the lab corpus: 34 IVs found vs 58 by the SCC method.
Classic IV detection: cost?
A fixed point over the loop's instructions: each pass O(instructions), at most one pass per derivation level (Proposition 18.2.11).
ssa-iv¶
SSA-based IV recognition: the key observation (Wolfe 1992)?
An induction variable is a strongly connected component of the SSA graph (header phi + its update chain); classify each SCC by shape in Tarjan's completion order.
SSA-based IV recognition: why is Tarjan's completion order the right processing order (Lemma 18.2.7)?
Tarjan completes an SCC only after every SCC it depends on (its operands), so each SCC's classification can use the already-computed CRs of its operands.
SSA-based IV recognition: the sequence classes (Definition 18.2.5)?
linear {a,+,b}, polynomial {a,+,b,+,c,…}, geometric {a,*,r}, wrap-around (phi(init, iv)), periodic (phi cycles), monotonic (only a direction is known).
SSA-based IV recognition: cost?
Tarjan is O(V + E) over the SSA graph of the loop, plus constant work per SCC for the classification: linear time.
chains-of-recurrences¶
Chains of recurrences: what does {c0,+,c1,+,c2} denote (Definition 18.3.1)?
The sequence f(n) = c0 + c1·C(n,1) + c2·C(n,2): start c0, whose increment is itself the chain {c1,+,c2}.
Chains of recurrences: how are the coefficients related to the values (Lemma 18.3.2)?
They are Newton's forward differences at n = 0: c_k = Δ^k f(0).
Chains of recurrences: product of two linear CRs (Lemma 18.3.4)?
{a,+,b}·{c,+,d} = {ac, +, ad + bc + bd, +, 2bd}: degree adds. Example {1,+,2}·{0,+,1} = {0,+,3,+,4}.
Chains of recurrences: the pitfall of statement order in the loop body?
A variable read after its update in the same iteration must use the shifted CR (Lemma 18.3.5): j = j + i; s = s + j gives s = {0,+,0,+,1,+,1}, not {0,+,0,+,0,+,1}.
scev¶
ScalarEvolution: what is an add recurrence {start,+,step}<flags><%loop>?
A value whose loop-iteration-n value is start + n·step (nested for polynomial ones); flags nuw/nsw/nw say the arithmetic does not wrap.
ScalarEvolution: how is a header phi turned into an add recurrence?
createNodeForPHI → createAddRecFromPHI: if the latch value is the phi plus loop-invariant (or recurrent) terms, build {start,+,step} and infer no-wrap flags.
ScalarEvolution: why is the address of a[4i+3] (long) {(24 + %a),+,32}?
SCEV computes pointer arithmetic in bytes: 8·{3,+,4} = {24,+,32}, plus the base %a.
ScalarEvolution: cost model of getSCEV?
Demand-driven and memoized per value; folding normalizes expressions; queries (trip counts, isKnownPredicate) are cached per loop.
trip-count¶
Trip count vs backedge-taken count (Definition 18.3.9)?
Trip count = number of times the body runs (TC); backedge-taken count BTC = TC − 1 for a rotated loop. SCEV reports BTC.
Trip count of a != loop on w-bit integers (Theorem 18.3.13)?
The least k ≥ 0 with a + k·s ≡ b (mod 2^w): solvable iff gcd(s, 2^w) divides b − a; otherwise the loop is infinite.
Trip count of a < loop that can wrap (Theorem 18.3.14)?
Without wrap: ⌈(b − a)/s⌉. If i can jump past the maximum, the value wraps and the walk continues (possibly forever); e.g. u8 250 < 255 step 3 runs 87 times.
Trip count: cost of the formulas?
O(w) for the modular inverse (extended Euclid) and O(1) arithmetic otherwise (Proposition 18.3.15); simulation would be O(2^w).
ack-sr¶
ACK strength reduction: what does it do to j = c·i + d (Algorithm 18.4.2)?
Creates a temporary initialized to c·i0 + d in the preheader and incremented by c·s wherever i is incremented by s; uses of j read the temporary.
ACK strength reduction: correctness invariant (Theorem 18.4.12)?
At every point in the loop the temporary equals c·i + d for the current i.
ACK strength reduction: limits?
Works per loop on derived IVs of that loop; IV × value invariant only in an inner loop needs LICM first; one temporary per reduced expression.
osr¶
OSR (Cooper, Simpson, Vick): what is a candidate operation (Definition 18.4.5)?
x = iv × rc, iv ± rc or rc × iv, where iv is an OSR induction variable and rc a region constant (defined outside the loop / dominating the header).
OSR: how does Reduce(op, iv, rc) build the new IV?
Clone iv's SCC; replace operands outside the SCC by Apply(op, operand, rc) and inside the SCC by Reduce recursively; memoize (op, iv, rc) in a hash table.
OSR: complexity (Proposition 18.4.14)?
One Tarjan walk over the SSA graph; the hash table makes each (op, iv, rc) reduced once: linear in the number of values created.
lsr¶
LLVM LSR: uses, formulae, cost (Definition 18.4.8)?
Each use of an IV expression gets candidate formulae reg + scale·reg + imm; LSR picks one per use minimizing registers, instructions and addressing-mode cost.
LLVM LSR: why is the search pruned?
Choosing one formula per use is exponential; NarrowSearchSpaceUsingHeuristics cuts candidates before SolveRecurse's branch-and-bound.
LLVM LSR: why prefer a pointer IV for a[3*i] with 8-byte elements on x86-64?
Scale 24 is not a legal addressing mode (1, 2, 4, 8), so a pointer IV stepping by 24 bytes with [reg] addressing is cheaper.
lftr¶
LFTR: what does it replace (Definition 18.4.10)?
The exit test on an IV that has no other uses (i < n) by a test on another IV evaluated at the trip count (p != a + 8·TC), so the old IV dies.
LFTR: correctness condition (Theorem 18.4.13)?
The new IV must reach the limit exactly at the trip count without wrapping (no-wrap facts from SCEV).
LFTR: example limit?
i = 0..99 with p = {a,+,8}: the test becomes p != a + 800.
rotation¶
Loop rotation: what does it produce (Algorithm 18.5.2)?
A guard (the header test on initial values) before a do-while loop whose test is at the latch; the header is duplicated.
Loop rotation: why do it?
The body then dominates the exit test, so LICM may hoist trapping invariant code; one conditional branch per iteration instead of two.
Loop rotation: tests executed for n iterations?
n + 1 before and after (guard + n latch tests); the guard runs once even for n = 0.
peeling¶
Loop peeling: definition (Definition 18.5.3)?
Execute the first (or last) k iterations as straight-line copies, each with its own exit test, before the loop.
Loop peeling: what does peeling one iteration do to a wrap-around variable?
In the remaining loop it becomes a linear IV (Lemma 18.2.8), and first-iteration conditions like i == 0 fold away.
Loop peeling: code size?
(k + 1)·S for loop size S; LLVM decides the count in computePeelCount.
unrolling¶
Loop unrolling: full vs runtime?
Full: a small constant trip count, the loop disappears (E4). Runtime: u copies per iteration plus a remainder loop for n mod u iterations.
Loop unrolling: runtime unrolling by 4 for n = 10?
M = 8: 2 unrolled iterations (0–3, 4–7) and a remainder of 2 (8, 9); n < 4 skips the unrolled loop (Theorem 18.5.15).
Loop unrolling: LLVM's default size threshold?
unroll-threshold-default = 150 (unroll-threshold-aggressive = 300 at -O3), in LoopUnrollPass.cpp.
unswitching¶
Loop unswitching: definition (Definition 18.5.9)?
Hoist an invariant branch out of the loop by making one loop copy per outcome, with the test before the loops.
Loop unswitching: trivial vs non-trivial?
Trivial: one side exits the loop, so no copy is needed. Non-trivial: both sides stay, the loop is duplicated.
Loop unswitching: code growth (Proposition 18.5.18)?
m independent invariant conditions give 2^m copies; LLVM bounds it with unswitch-threshold.
versioning¶
Loop versioning: definition (Definition 18.5.11)?
Two copies of the loop, chosen by a runtime check (e.g. no overlap of pointer ranges); the optimized copy may assume the checked property.
Loop versioning: the overlap check for ranges [a, a+x) and [b, b+y)?
Conflict iff a < b + y and b < a + x (half-open intervals); otherwise run the no-alias copy.
Loop versioning: number of checks for g pointer groups?
One per pair that may conflict: up to g(g−1)/2; LAA gives up beyond runtime-memory-check-threshold (8).
gcd-test¶
GCD test (Theorem 18.6.5)?
Σ a_k x_k − Σ b_k y_k = c has an integer solution iff gcd of all coefficients divides c; if not, the references are independent.
GCD test: what does it ignore?
Loop bounds and directions: A[i] vs A[i+100] in 1..10 passes the GCD test (gcd 1) although no dependence exists.
GCD test: cost?
O(number of coefficients · log(max coefficient)) per subscript: the cheapest test.
GCD test: example A[2i+4j] vs A[2i+4j+1]?
gcd(2,4,2,4) = 2 does not divide 1: independent (LLVM DA with only gcd-miv prints none!).
banerjee¶
Banerjee test (Theorem 18.6.8)?
Bound Σ(a_k x_k − b_k y_k) over the loop bounds under a direction vector; if the constant lies outside [LB, UB], no dependence with that direction (not even a real solution).
Banerjee test: bounds of a·x − b·y under = (Lemma 18.6.7)?
[(a−b)⁺L − (a−b)⁻U, (a−b)⁺U − (a−b)⁻L]: the segment x = y.
Banerjee test: hierarchical refinement (Algorithm 18.6.9)?
Test (,…,), refine one position at a time into <, =, >; a pruned vector prunes all its refinements.
Banerjee test in LLVM 23?
DependenceInfo::banerjeeMIVtest, disabled by default (Default = all tests except BanerjeeMIV).
siv-tests¶
ZIV / SIV / MIV (Definition 18.6.10)?
Zero, single or multiple index variables in a subscript pair; SIV pairs are strong (a = b), weak-zero (one coefficient 0) or weak-crossing (a = −b).
Strong SIV test (Theorem 18.6.12)?
a·i + c1 vs a·i' + c2: distance d = (c1 − c2)/a; dependence iff d is an integer with |d| ≤ U − L. Exact.
Weak-crossing SIV?
a·i + c1 vs −a·i' + c2: dependences cross at i = (c2 − c1)/(2a); = occurs only if that point is an integer in range.
Delta test (Goff, Kennedy, Tseng)?
Propagate exact SIV constraints (distances) into coupled subscripts, preserving soundness and improving precision.
omega¶
Omega test: what does it decide?
Exact integer feasibility of a conjunction of linear constraints (Presburger), by Fourier–Motzkin extended to integers.
Omega test: real and dark shadow (Definition 18.6.13)?
For α ≤ a·z and b·z ≤ β: real shadow bα ≤ aβ (may over-approximate), dark shadow aβ − bα ≥ (a−1)(b−1) (under-approximates); if they differ, splinter.
Omega test: cost?
Exponential worst case (splintering, Fourier–Motzkin growth, Proposition 18.6.20) but fast on typical dependence problems.
Omega test: why does it catch coupled subscripts?
It solves all equations together: i+j = i'+j'+1 and i−j = i'−j' imply 2i = 2i'+1, impossible, which per-subscript tests cannot see.
runtime-checks¶
LoopAccessAnalysis: what does it classify?
Dependences of an innermost loop's memory accesses by byte distance of their add recurrences: Forward, Backward, BackwardVectorizable(ButPreventsForwarding), Unknown; plus runtime checks for unrelated bases.
LAA: safe VF for a backward dependence of δ bytes (Definition 18.6.16)?
Safe iff δ ≥ VF · element size; a[i+4] = a[i] with 4-byte elements: VF ≤ 4.
LAA: runtime checks (Theorem 18.6.18)?
Group accesses by base; one overlap test [Low, High) per pair of groups that may conflict; if all pass, no cross-group dependence exists.
fusion-fission¶
Loop distribution (Algorithm 18.7.2)?
One loop per strongly connected component of the statement dependence graph, in topological order; acyclic components are parallel (vectorizable).
Loop fusion legality (Theorem 18.7.15)?
Legal iff no dependence from L1's iteration i to L2's iteration i' has i' < i (no fusion-preventing dependence).
Fusion/fission cost?
Distribution: SCCs O(m + E). Fusion for maximal locality is NP-hard (Kennedy & McKinley).
interchange¶
Loop permutation legality (Theorem 18.7.4)?
Legal iff every non-zero distance vector stays lexicographically positive after permuting its components.
Interchange: which direction vector forbids swapping two loops?
(<, >) (with = outside): it becomes (>, <).
Interchange in LLVM 23?
loop-interchange is in the default -O2 pipeline; isLegalToInterChangeLoops checks the direction matrix, CacheCost the profitability.
tiling¶
Strip-mining vs tiling (Definition 18.7.6)?
Strip-mining splits one loop into tile and point loops (always legal); tiling strip-mines a band and moves all tile loops outside.
Tiling legality (Theorem 18.7.16)?
Legal if the band is fully permutable: every dependence not carried outside has non-negative components in the band.
Skewing (Lemma 18.7.8)?
j' = j + f·i maps (dᵢ, dⱼ) to (dᵢ, dⱼ + f·dᵢ); always legal, and f ≥ max⌈−dⱼ/dᵢ⌉ makes the band fully permutable.
polyhedral¶
Polyhedral model: iteration domain, access relation, schedule (Definition 18.7.9)?
Integer points of a polyhedron per statement; affine maps to array elements; an affine map to time whose lexicographic order is the execution order.
Feautrier's dataflow analysis (Algorithm 18.7.11)?
For each read instance, the lexicographically last write instance to the same element that precedes it, computed by parametric integer programming.
Feautrier's scheduling (Algorithm 18.7.13)?
Find affine θ with θ_T(y) − θ_S(x) ≥ 1 on every dependence polyhedron; Farkas' lemma turns this into linear constraints on θ's coefficients (an LP).
Affine Farkas lemma (Theorem 18.7.12)?
An affine φ is ≥ 0 on a non-empty polyhedron {Ax + b ≥ 0} iff φ = λ0 + λᵀ(Ax + b) with λ0, λ ≥ 0.
loop-vectorizer¶
Loop vectorization legality (Theorem 18.8.2)?
Lockstep execution of VF iterations is legal if every dependence with distance 0 < d < VF is forward (source statement before sink statement).
Loop vectorizer: VF vs IC?
VF = elements per vector instruction; IC = interleave (unroll) count of the vector loop: VF·IC scalar iterations per vector-loop iteration.
Loop vectorizer: iterations for n with W = VF·IC and epilogue VF_e (Proposition 18.8.15)?
Main ⌊n/W⌋, epilogue ⌊(n mod W)/VF_e⌋, scalar n mod VF_e.
Loop vectorizer: why do FP reductions need permission?
Vectorizing s += a[i] reassociates the sum into VF·IC partial sums; exact for integers, not for floating point without reassociation (-ffast-math).
vplan¶
VPlan (Definition 18.8.4)?
An explicit plan of the vector loop: a hierarchical CFG of recipes (WIDEN, REPLICATE, blend, …) in VPBasicBlocks and regions, one plan per range of VFs.
VPlan: why can one plan serve VF = 2 and VF = 4?
The recipes are the same; VF and VF·UF are symbolic live-ins until code generation.
VPlan: how to see plans in a release build of LLVM 23?
opt -passes=loop-vectorize -vplan-print-after=<transformation regexp> (or -vplan-print-after-all).
slp¶
SLP vectorization (Definition 18.8.6)?
Pack independent isomorphic instructions of a basic block (seeds: consecutive stores) and build a tree over their operands; replace profitable trees by vector instructions.
SLP: cost of a tree?
Σ(vector cost − scalar costs) + gather/extract costs; vectorize if below −slp-threshold (default 0). add4: −12.
SLP: alternate-opcode nodes?
A pack of fadd and fmul lanes is computed as both vector ops plus a shufflevector selecting lanes (the mixed box).
predication¶
If-conversion (Algorithm 18.8.9)?
Compute a predicate per block, execute all blocks unconditionally, replace phis by selects (blends), mask stores and non-speculatable loads.
Tail folding (Algorithm 18.8.10)?
Run the last partial vector iteration with lane mask {k : jVF + k < n} (get.active.lane.mask) instead of a scalar remainder.
Scalable vectors?
<vscale x k x T>: vscale·k elements, vscale a runtime constant of the machine (SVE: 128–2048-bit registers); one binary for all vector lengths.
range-bce¶
Range-based BCE (Theorem 18.9.2)?
For i = {a,+,s}<nsw>, s ≥ 1, guarded by i < n: i ∈ [a, n−1], so i + c is in range if a + c ≥ 0 and n + c ≤ len.
Range-based BCE: the wrap pitfall?
i + 2 < len does not imply i < len for unsigned i when i + 2 can wrap; LLVM correctly keeps that check.
Range-based BCE in LLVM?
indvars (eliminateIVComparison), correlated-propagation (ranges, nuw inference) and constraint-elimination (dominating facts).
abcd¶
ABCD's inequality graph (Definition 18.9.4)?
Edges u →c v for facts v ≤ u + c from assignments and π-nodes of e-SSA; φ-nodes are max-vertices (all inputs must satisfy a bound).
ABCD proof of a check x < len?
Prove(len, x, −1): a path len ⇝ x of total weight ≤ −1 (Lemma 18.9.6), all inputs at φ-vertices.
ABCD cycles?
Harmless (requirement not smaller on return): true by induction over iterations; amplifying (smaller): false (Theorem 18.9.11).
irce-predication¶
IRCE (Algorithm 18.9.8)?
Split the loop into pre-, main and post-loops so that the main loop's iterations lie in every range check's safe space and need no checks.
Loop predication (Algorithm 18.9.9)?
Replace guard(i <u len) by one guard of (start <u len) ∧ (last <u len) computed before the loop; failing deoptimizes earlier.
Why is loop predication legal only for guards (Theorem 18.9.13)?
Failing early is acceptable only if the runtime can deoptimize and re-execute precisely up to the real failure; a plain trap would skip the effects of the earlier iterations.