Lesson 18.2 — Induction variables: classic detection and SSA-based recognition¶
Techniques: classic basic/derived induction-variable detection (Allen–Cocke–Kennedy), SSA-based recognition by strongly connected components (Wolfe; Gerlek–Stoltz–Wolfe) · Pebble implements: SCC-based recognition with chains of recurrences (
pebble-iv,print<pebble-iv>, E2) · Lab: classic detection (labs/ch18-loops, Part A) vs yourpebble-ivvs LLVM's ScalarEvolution · Prerequisites: Lesson 18.1 (loop invariance), Ch 16 (SSA form, phis), Ch 15, Lesson 15.5 (Tarjan's SCC algorithm) · Time: 4–5 hours
An induction variable is a variable whose value in iteration \(n\) of a loop follows a simple rule in \(n\). In
i takes the values \(0, 1, 2, \dots\) and 4 * i + 3 the values \(3, 7, 11, \dots\). Knowing that is what lets a compiler replace the multiplication by an addition (Lesson 18.4), compute how often the loop runs (Lesson 18.3), decide whether two array accesses can touch the same element (Lesson 18.6) and whether an array index stays in bounds (Lesson 18.9). This lesson is about finding induction variables; the next one is about the algebra of the rules they follow.
1. Problem and motivation¶
The problem. Given a loop \(L\), classify the integer values computed in \(L\): which of them are affine functions of the iteration number \(n\) (\(v(n) = a + n\,b\) with \(a\), \(b\) loop-invariant), and — for the SSA-based methods — which follow other recognizable sequences (polynomials in \(n\), geometric sequences, "the previous value of an induction variable", periodic sequences, monotonic sequences). The output is a map from values to their class and closed form. In pebblec your pebble-iv analysis produces it (E2) and pebble-osr consumes it (E3); in LLVM, ScalarEvolution produces the equivalent answer for every value on demand.
Classic induction-variable detection¶
Allen, Cocke and Kennedy defined induction variables on a program without SSA: a basic induction variable is a variable whose only assignments in the loop add or subtract a loop-invariant amount; a derived one is computed once per iteration as \(c \cdot i + d\) from a basic one [ACK81]; the ideas go back to Allen and Cocke's catalogue [AC72b] and to FORTRAN compilers of the 1960s. Detection is a fixed point over the loop's statements; the textbook presentations are Muchnick [Muchnick, §14.1.1] and the Dragon book [Dragon2 §9.1.7]. The classic method was designed for strength reduction; it is simple but blind to anything that is not "basic plus affine".
SSA-based recognition (SCC classification)¶
Wolfe observed that in SSA form an induction variable is a cycle in the SSA graph: the header phi i = phi(0, i1) and i1 = i + 1 feed each other. Finding strongly connected components (SCCs) of the SSA graph and classifying each by its shape finds every linear induction variable — including those computed through several statements and several variables — in one linear-time pass [Wol92]. Gerlek, Stoltz and Wolfe extended the classification to polynomial, geometric, wrap-around, periodic and monotonic sequences [GSW95]. This is the foundation of GCC's and LLVM's scalar-evolution analyses (Lesson 18.3).
2. Definitions and algorithms¶
\(L\) is a natural loop in loop-simplify form with header \(h\), preheader \(P\) and latch \(\ell\). The iteration number \(n \in \{0, 1, 2, \dots\}\) counts the visits of \(h\) during one entry into \(L\). A value \(v\) computed in \(L\) has value \(v(n)\) in iteration \(n\) if, in every entry, the execution of its definition during iteration \(n\) (the unique one, for definitions whose innermost loop is \(L\)) produces \(v(n)\); a header phi has the value it receives on entry to iteration \(n\). Invariance is as in Definition 18.1.1.
Definition 18.2.1 (Basic and derived induction variables — Allen, Cocke, Kennedy)
In a (not necessarily SSA) program, a variable \(i\) is a basic induction variable of \(L\) if every assignment to \(i\) inside \(L\) has the form \(i \gets i + c\) or \(i \gets i - c\) with \(c\) invariant in \(L\). A variable \(j\) is a derived induction variable in the family of \(i\) if it has exactly one assignment in \(L\), of the form \(j \gets c \cdot k\), \(j \gets k \cdot c\), \(j \gets k \pm c\) or \(j \gets c \pm k\), where \(k\) is \(i\) or a derived variable of the family of \(i\), and \(c\) is invariant. Each derived \(j\) is described by a triple \((i, c_j, d_j)\) meaning \(j = c_j \cdot i + d_j\). On SSA form, the "variable" \(i\) is the web formed by a header phi and the chain of additions that computes its latch operand; derived induction variables are single SSA values.
Basic and derived on the running example
In for (i = 0; i < n; i++) s += a[4*i + 3], i is basic (its only assignment is i = i + 1), 4*i has triple \((i, 4, 0)\) and 4*i + 3 has triple \((i, 4, 3)\). s is not an induction variable: its increment a[...] is not invariant.
Classic induction-variable detection¶
Algorithm 18.2.2 (Classic detection, on SSA form)
- Input: a loop \(L\) in loop-simplify form, SSA form.
- Output: the set of basic and derived induction variables of \(L\), each with \(\mathrm{Start}\) and \(\mathrm{Step}\), affine in invariant values: \(v(n) = \mathrm{Start} + n \cdot \mathrm{Step}\).
- Precondition: \(L\) has a preheader \(P\) and a single latch \(\ell\).
- Postcondition: every reported \(v\) satisfies \(v(n) = \mathrm{Start}_v + n\,\mathrm{Step}_v\) (Theorem 18.2.9).
- Invariant: every value in the set \(K\) of known induction variables satisfies the postcondition; \(K\) only grows.
function ClassicIVs(L):
K ← {} # value -> (family, Start, Step)
for each header phi φ = phi [init, P], [back, ℓ] of integer type:
if init is not invariant: continue
step ← 0; v ← back
while v ≠ φ: # walk the update chain back to φ
if v is "x + c" or "c + x" with c invariant: step ← step + c; v ← x
else if v is "x - c" with c invariant: step ← step - c; v ← x
else: fail # not a basic IV
K[φ] ← (φ, init, step) # basic
repeat until no change: # derived, to a fixed point
for each integer instruction j of L (innermost loop L) not in K:
if j = op(k, c) or op(c, k) with k ∈ K and c invariant:
(f, S, T) ← K[k]
j + c: K[j] ← (f, S + c, T) j - c: K[j] ← (f, S - c, T)
c - j: K[j] ← (f, c - S, -T)
c * j: K[j] ← (f, c·S, c·T) if c·S and c·T are affine
j << k: K[j] ← (f, 2^k·S, 2^k·T) for a constant k
return K
GCC's induction-variable table: bases, steps, and which are basic
Reproduce (gcc 14.2.0):
cat > ivs.c <<'X'
long f(long *a, long n) {
long s = 0;
for (long i = 0; i < n; i++) {
long j = 4 * i + 3;
s += a[j];
}
return s;
}
X
gcc-14 -O2 -fno-tree-vectorize -fdump-tree-ivopts-details -c ivs.c -o /dev/null
sed -n '/^<Induction Vars>:/,/^$/p' ivs.c.*.ivopts
Output (abridged: 3 of the 7 entries — _1 = 4*i, j_10, and the basic IV i_18; the others are the byte offset _3, the address _4, an unsigned copy of j, and i + 1):
<Induction Vars>:
IV struct:
SSA_NAME: _1
Type: long int
Base: 0
Step: 4
Biv: N
Overflowness wrto loop niter: No-overflow
…
IV struct:
SSA_NAME: j_10
Type: long int
Base: 3
Step: 4
Biv: N
Overflowness wrto loop niter: No-overflow
…
IV struct:
SSA_NAME: i_18
Type: long int
Base: 0
Step: 1
Biv: Y
Overflowness wrto loop niter: No-overflow
What to notice: GCC's ivopts records exactly the classic information — base (Start), step, and whether the value is a basic induction variable (Biv: Y) or derived from one — for every induction variable, including the address a + 24 + 32·i (not shown). find_bivs and find_givs in gcc/tree-ssa-loop-ivopts.cc keep the classic names; the values themselves come from GCC's SSA-based scalar evolution.
SSA-based recognition (SCC classification)¶
Definition 18.2.3 (Linear induction variable)
A value \(v\) of \(L\) is a linear induction variable if there are invariant values \(a\), \(b\) with \(v(n) = a + n\,b\) for all iterations \(n\) of every entry. Its chain of recurrences is written \(\{a, +, b\}\) (Lesson 18.3, Definition 18.3.1).
Definition 18.2.4 (SSA graph of a loop; its SCCs)
The SSA graph of \(L\) has a node for every integer phi, add, sub, mul and shl whose innermost loop is \(L\) and which is not invariant, and an edge \(u \to w\) whenever \(w\) is an operand of \(u\) ("\(u\) uses \(w\)"). Its strongly connected components (SCCs) are maximal sets of nodes that reach each other; an SCC is trivial if it is one node without a self-edge. Every non-trivial SCC contains a header phi (a cycle of SSA uses must pass a phi, and a cycle inside \(L\)'s own blocks that avoids \(h\) would be a subloop).
Definition 18.2.5 (Sequence classes — Gerlek, Stoltz, Wolfe)
Let \(v\) be a value of \(L\).
- \(v\) is polynomial of degree \(k \ge 2\) if \(v(n)\) is a polynomial of degree \(k\) in \(n\) with invariant coefficients (for example \(v \gets v + i\) with \(i\) linear).
- \(v\) is geometric if \(v(n) = a \cdot r^{n}\) with \(a\) invariant and \(r\) a constant, \(r \notin \{0, 1\}\) (\(v \gets v \cdot r\)).
- \(v\) is wrap-around if \(v(0) = x\) and \(v(n) = w(n-1)\) for \(n \ge 1\), for an invariant \(x\) and an induction variable \(w\) (the header phi
v = phi(x, w): "the previous value of \(w\)"). - A group of header phis is periodic with period \(p\) if their latch operands form a cycle \(v_1 \gets v_2 \gets \dots \gets v_p \gets v_1\) (the values rotate every iteration).
- \(v\) is monotonic (increasing, respectively decreasing) if \(v(n+1) \ge v(n)\) (respectively \(\le\)) for all \(n\), computing in unbounded integers (ignoring wrap-around, see "When it breaks" in §4), but no closed form is claimed — typically a conditional increment by a non-negative constant.
Algorithm 18.2.6 (SCC classification — Wolfe; Gerlek, Stoltz, Wolfe)
- Input: a loop \(L\) in loop-simplify form, SSA form.
- Output: a class (Definitions 18.2.3, 18.2.5) for the values of \(L\) that have one, with a chain of recurrences for linear, polynomial and geometric values.
- Precondition: \(L\) has a preheader \(P\) and a single latch \(\ell\).
- Postcondition: every reported chain of recurrences equals the value's sequence (Theorem 18.2.10).
- Invariant: when an SCC is classified, every SCC it uses has been classified already (Lemma 18.2.7), so
CR(w)of any operand \(w\) outside the SCC is final.
function ClassifyLoop(L):
build the SSA graph G_L of L (Definition 18.2.4)
for each SCC C of G_L, in the order Tarjan's algorithm completes them: # operands first
Classify(C)
function CR(w): # an operand's sequence
if w is invariant: return {w} # a constant CR
return the chain of recurrences recorded for w, or ⊥
function Classify(C):
if C = {x} is trivial:
if x is a header phi phi[init, P][back, ℓ]: WrapAround(x)
else if x is a phi inside L: CR(x) ← the common CR of its operands, if equal
else: CR(x) ← Combine(op(x), CR(operand 1), CR(operand 2)) # Lesson 18.3 algebra
return
H ← header phis in C; Q ← other phis in C; A ← the rest
if A = Q = {} and the latch operands of H form one cycle: mark H periodic, period |H|
else if |H| = 1, Q = {}: Recurrence(φ ∈ H, C)
else if |H| = 1, Q ≠ {}, every x ∈ A is "y + c" (or "y - c") with y ∈ C and constants
c of one sign, and every phi operand is in C (except the header phi's init):
mark C monotonic (increasing if c ≥ 0)
else: leave C unclassified
function Recurrence(φ, C):
chain ← x_1, …, x_m from φ to back = x_m, each x_k having exactly one operand in C
if chain does not cover C: return
if every x_k is "x_{k-1} + e_k", "e_k + x_{k-1}" or "x_{k-1} - e_k":
E ← Σ_k ±CR(e_k) # all operands outside C: final CRs
CR(φ) ← {init, +, E} # "prepend", Lemma 18.3.5
CR(x_k) ← CR(φ) + Σ_{j ≤ k} ±CR(e_j)
else if every x_k is "x_{k-1} · r_k" or "x_{k-1} << s_k" with constants:
r ← Π r_k (2^{s_k} for shifts); CR(φ) ← {init, *, r}; CR(x_k) ← {init·Π_{j≤k} r_j, *, r}
function WrapAround(φ = phi[init, P][back, ℓ]):
if CR(back) = {a, +, b} and init = a - b: CR(φ) ← {init, +, b} # Lemma 18.2.8
else if back is an induction variable: mark φ wrap-around
A chain of recurrences with two coefficients is linear, with three or more polynomial.
LLVM's ScalarEvolution classifies the SSA recurrences of a loop — but not wrap-around
Reproduce (opt 23.1.2):
cat > run.ll <<'X'
define i64 @run(i64 %n) {
entry:
br label %loop
loop:
%i = phi i64 [ 0, %entry ], [ %i1, %loop ]
%s = phi i64 [ 0, %entry ], [ %s1, %loop ]
%p = phi i64 [ %n, %entry ], [ %i, %loop ]
%t = mul i64 %i, 4
%u = add i64 %t, 3
%s1 = add i64 %s, %i
%i1 = add i64 %i, 1
%c = icmp slt i64 %i1, %n
br i1 %c, label %loop, label %exit
exit:
%r = add i64 %u, %p
%r2 = add i64 %r, %s1
ret i64 %r2
}
X
opt -passes='print<scalar-evolution>' -disable-output run.ll 2>&1 | grep -A1 -E '^ %(i|s|p|t|u|s1|i1) =' | grep -o -E '^ %[a-z0-9]+|--> [^ ]+' | paste - -
Output (complete):
%i --> {0,+,1}<nuw><nsw><%loop>
%s --> {0,+,0,+,1}<%loop>
%p --> %p
%t --> {0,+,4}<%loop>
%u --> {3,+,4}<%loop>
%s1 --> {0,+,1,+,1}<%loop>
%i1 --> {1,+,1}<nuw><nsw><%loop>
What to notice: ScalarEvolution recognizes the SCC {i, i1} as the linear recurrence \(\{0,+,1\}\), derives t and u from it, and recognizes the SCC {s, s1} — an accumulation of a linear induction variable — as the polynomial \(\{0,+,0,+,1\}\) (\(s(n) = n(n-1)/2\), Definition 18.2.5). The wrap-around phi %p = phi(%n, %i) is left as an opaque value (%p): SCEV has no class for it, while Algorithm 18.2.6 reports it as wrap-around. Your print<pebble-iv> prints the same seven classifications (E2).
3. Worked example¶
The running example is the loop of the real-world box above (@run): seven values of interest in one block.
flowchart LR
i["i = phi(0, i1)"] --> i1["i1 = i + 1"]
i1 --> i
s["s = phi(0, s1)"] --> s1["s1 = s + i"]
s1 --> s
s1 --> i
p["p = phi(n, i)"] --> i
t["t = i * 4"] --> i
u["u = t + 3"] --> t(Arrows point from a use to its operand, the direction of Definition 18.2.4.)
Classic induction-variable detection on the running example¶
Basic induction variables (walk each header phi's latch operand back to the phi):
| header phi | latch operand | walk | result |
|---|---|---|---|
i |
i1 |
i1 = i + 1: step ← 1, reach i |
basic, Start 0, Step 1 |
s |
s1 |
s1 = s + i: i is not invariant |
fail |
p |
i |
i is not an addition |
fail |
Derived induction variables (instruction order, to a fixed point):
| pass | instruction | known operand | rule | result |
|---|---|---|---|---|
| 1 | t = i * 4 |
i (0, 1) |
\(c \cdot j\) | derived, \((i, 4, 0)\): \(\{0,+,4\}\) |
| 1 | u = t + 3 |
t (0, 4) |
\(j + c\) | derived, \((i, 4, 3)\): \(\{3,+,4\}\) |
| 1 | s1 = s + i |
i, but s is neither known nor invariant |
— | no |
| 1 | i1 = i + 1 |
i (0, 1) |
\(j + c\) | derived, \((i, 1, 1)\): \(\{1,+,1\}\) |
| 2 | (all) | no change → fixed point |
Classic detection finds i, t, u, i1 and misses s, s1 (polynomial) and p (wrap-around).
SSA-based recognition (SCC classification) on the running example¶
Tarjan's algorithm on the SSA graph, starting from the nodes in instruction order i s p t u s1 i1, following use → operand edges:
| step | action | num / low | stack (bottom → top) | SCC emitted |
|---|---|---|---|---|
| 1 | visit i |
i: 1/1 | i | |
| 2 | visit i1 (operand of i) |
i1: 2/2 | i i1 | |
| 3 | i1 → i on stack |
i1: low 1 | i i1 | |
| 4 | back in i |
i: low 1 = num | i i1 | {i, i1} |
| 5 | visit s |
s: 3/3 | s | |
| 6 | visit s1 |
s1: 4/4 | s s1 | |
| 7 | s1 → s on stack |
s1: low 3 | s s1 | |
| 8 | s1 → i: i finished, in an earlier SCC |
— | s s1 | |
| 9 | back in s |
s: low 3 = num | s s1 | {s, s1} |
| 10 | visit p; p → i finished |
p: 5/5 | p | {p} |
| 11 | visit t; t → i finished |
t: 6/6 | t | {t} |
| 12 | visit u; u → t finished |
u: 7/7 | u | {u} |
Classification in that order:
| SCC | shape | rule of Algorithm 18.2.6 | result |
|---|---|---|---|
| {i, i1} | one header phi, chain i1 = i + 1 |
Recurrence: E = | i = \(\{0,+,1\}\), i1 = \(\{1,+,1\}\) |
| {s, s1} | one header phi, chain s1 = s + i |
Recurrence: E = CR(i) = \(\{0,+,1\}\) | s = \(\{0,+,0,+,1\}\) (polynomial), s1 = \(\{0,+,1,+,1\}\) |
| {p} | trivial header phi, back = i = \(\{0,+,1\}\) |
WrapAround: \(\mathit{init} = n \ne 0 - 1\) | wrap-around |
| {t} | trivial, i * 4 |
Combine: \(4 \cdot \{0,+,1\}\) | \(\{0,+,4\}\) |
| {u} | trivial, t + 3 |
Combine: \(\{0,+,4\} + 3\) | \(\{3,+,4\}\) |
The result matches LLVM's SCEV on every value SCEV classifies, and print<pebble-iv> on the same function prints exactly these classes (E2). The lab's comparison (labs/ch18-loops, Part A) measures the difference over a corpus: on corpus/ivs.c classic detection finds 34 induction variables, the SCC method 58 (37 linear, 11 polynomial, 4 geometric, 1 wrap-around, 2 periodic, 3 monotonic), and SCEV agrees with all 47 comparable linear and polynomial ones.
Try it
./course drill scev-form --seed 3 --difficulty medium gives a loop with a polynomial variable; derive the CR of every variable, then compare with --solution, which shows the same prepend rule Algorithm 18.2.6 uses.
4. Invariants and correctness¶
Lemma 18.2.7 (Tarjan's algorithm completes SCCs operands first)
If Tarjan's SCC algorithm follows use → operand edges, then whenever an SCC \(C\) is completed, every SCC containing an operand of a node of \(C\) has already been completed.
Proof
Tarjan's algorithm completes SCCs in reverse topological order of the condensation of the graph it explores: an SCC is emitted only after every SCC reachable from it along explored edges has been emitted [Tar72]. Edges go from a use to its operands, so everything reachable from \(C\) — in particular every operand's SCC — is emitted before \(C\).
Lemma 18.2.8 (A wrap-around variable with the right first value is linear)
Let \(v = \mathrm{phi}(x, w)\) be a header phi with \(x\) invariant and \(w\) linear, \(w(n) = a + n\,b\). Then \(v(0) = x\) and \(v(n) = a + (n-1)\,b\) for \(n \ge 1\); hence \(v\) is linear, \(v = \{x, +, b\}\), if and only if \(x = a - b\).
Proof
On entry the phi takes its preheader operand: \(v(0) = x\). On entry to iteration \(n \ge 1\) it takes the latch operand, i.e. the value \(w\) had in iteration \(n-1\): \(v(n) = w(n-1) = a + (n-1)b\). If \(x = a - b\), then \(v(n) = x + n\,b\) for all \(n \ge 0\) (for \(n = 0\) trivially). Conversely if \(v(n) = x' + n b'\) for all \(n\), then from \(n = 1, 2\): \(b' = b\) and \(x' = a - b\); from \(n = 0\): \(x = x' = a - b\).
Theorem 18.2.9 (Soundness of classic detection)
Every value reported by Algorithm 18.2.2 satisfies \(v(n) = \mathrm{Start}_v + n\,\mathrm{Step}_v\) in every entry into \(L\), and the algorithm terminates.
Proof
Basic. The walk visits the chain \(\varphi \to x_1 \to \dots \to x_m = \mathit{back}\) backward; each \(x_k = x_{k-1} \pm c_k\) with \(c_k\) invariant. So in iteration \(n\), \(\mathit{back}(n) = \varphi(n) + \sum_k \pm c_k = \varphi(n) + \mathrm{step}\), and \(\varphi(n+1) = \mathit{back}(n)\), \(\varphi(0) = \mathit{init}\); by induction on \(n\), \(\varphi(n) = \mathit{init} + n \cdot \mathrm{step}\). Derived. By induction on the order in which values enter \(K\) (the invariant): if \(k \in K\) satisfies \(k(n) = S + nT\) and \(c\) is invariant, then \(k + c\) has value \((S + c) + nT\), \(c - k\) has \((c - S) + n(-T)\), \(c \cdot k\) has \(cS + n\,cT\), and \(k \ll s\) has \(2^s S + n\,2^s T\) (all modulo \(2^w\), which preserves the identities). Since \(j\) is computed from \(k\) in the same iteration (both have innermost loop \(L\), and SSA use-before-def within an iteration cannot happen for a non-phi), the rule holds for every \(n\). Termination: each pass that changes something adds a value of \(L\) to \(K\); there are finitely many.
Theorem 18.2.10 (Soundness of SCC classification)
Every chain of recurrences recorded by Algorithm 18.2.6 describes the value's sequence; every value marked periodic, wrap-around or monotonic has that property. The algorithm visits each node and edge of the SSA graph \(O(1)\) times.
Proof (the CR algebra it relies on is proved in Lesson 18.3, Lemmas 18.3.3–18.3.5)
By Lemma 18.2.7 and induction over the completion order, when \(C\) is classified every operand outside \(C\) has its final classification. Trivial non-phi SCCs: the value is an arithmetic function of operands whose sequences are known; the CR algebra (Lemmas 18.3.3, 18.3.4) computes the sequence of the result exactly. Trivial header phi: Lemma 18.2.8. Recurrence with additions: along the chain, \(x_k(n) = \varphi(n) + \sum_{j \le k} \pm e_j(n)\) within an iteration, so \(\varphi(n+1) = x_m(n) = \varphi(n) + E(n)\) with \(E = \sum_j \pm e_j\); a sequence with \(\varphi(0) = \mathit{init}\) and forward difference \(E\) is the CR \(\{\mathit{init}, +, E\}\) (Lemma 18.3.5), and \(x_k\) is that plus the partial sum. Recurrence with multiplications: \(\varphi(n+1) = r\,\varphi(n)\), so \(\varphi(n) = \mathit{init}\,r^n\). Periodic: the phis' latch operands are the phis themselves shifted by one, so each value repeats with period \(|H|\). Monotonic: every phi of \(C\) merges only values of \(C\) (the header phi's start aside), and every other node adds a constant of one sign to a value of \(C\); so every value of \(C\) is the header phi's value plus a sum of such constants, and every path around the loop adds constants of one sign to the single header phi. (Without the phi condition the claim is false: m2 = phi(m + 1, 0) resets \(m\) to 0.) Cost: Tarjan's algorithm is linear in nodes plus edges [Tar72]; each classification looks at the nodes of its SCC and their operands once.
When it breaks. Both methods assume the arithmetic is exact modulo \(2^w\) and describe the value as a bit pattern: \(\{0,+,1\}\) in i8 really is \(0, 1, \dots, 127, -128, \dots\). The closed forms are right, but conclusions such as "\(v\) increases" need the no-wrap facts of Lesson 18.3 (nsw/nuw). Classic detection additionally assumes one assignment per derived variable; on non-SSA code with a conditionally executed derived assignment its triple is wrong — the reason ACK require the definition to be the only one in the loop.
5. Complexity¶
\(N\) = number of instructions in \(L\), \(E\) = number of operand edges among them (at most \(2N\) for binary operations plus phi operands).
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| Classic detection | \(O(N^2)\) | \(O(N)\) (2 passes) | \(O(N)\) | \(N\) instructions of \(L\) |
| SCC classification | \(O(N + E)\) | \(O(N + E)\) | \(O(N)\) | \(E\) operand edges |
Proposition 18.2.11 (Cost of the two detectors)
Algorithm 18.2.2 performs at most \(N + 1\) passes of \(O(N)\) work, so \(O(N^2)\); Algorithm 18.2.6 runs in \(O(N + E)\).
Proof
Each non-final pass of the derived fixed point adds at least one value to \(K\), so there are at most \(N + 1\) passes, each scanning \(N\) instructions; the basic-IV walks follow each chain once, \(O(N)\) in total. For Algorithm 18.2.6, Tarjan's algorithm is \(O(N + E)\) [Tar72], and every classification step inspects each node of its SCC and its operands a constant number of times.
Pathological input. A chain of derived induction variables listed in reverse definition order — j_m = j_{m-1} + 1 placed before j_{m-1} = …, possible in a non-SSA program or in an SSA function whose blocks are listed out of dominance order — makes the classic fixed point discover one new variable per pass: \(m\) passes of \(\Theta(N)\), \(\Theta(N^2)\) in total. The SCC method is linear on it, because Tarjan's traversal follows operands directly.
At scale. Both are cheap compared with their clients; LLVM computes the equivalent SCEV classification lazily per value and caches it (Lesson 18.3).
6. Variants and refinements¶
Classic induction-variable detection¶
- Muchnick's formulation [Muchnick, §14.1.1] tracks triples through copies and allows derived variables defined in terms of other derived variables — trade-off: the same power, more bookkeeping.
- Induction-variable substitution (Allen–Kennedy [AK02, Ch. 4]) rewrites derived variables as explicit functions of the loop index before dependence testing — trade-off: exposes subscripts to Lesson 18.6's tests, but introduces multiplications that strength reduction must undo.
SSA-based recognition (SCC classification)¶
- Demand-driven classification [GSW95] classifies only the SCCs a client asks about, using factored use-def chains — trade-off: less work when few values matter; the full pass is simpler.
- Chains of recurrences as the result [vEn01; PCS05]: instead of classes, return a CR for every value, including nested loops and polynomial/geometric forms — trade-off: a symbolic algebra to implement (Lesson 18.3), but one uniform answer.
- Wrap-around peeling: peeling one iteration turns a wrap-around variable into a linear one (Lesson 18.5) — trade-off: code size.
7. In real compilers¶
Classic induction-variable detection¶
GCC
gcc/tree-ssa-loop-ivopts.cc — find_bivs, mark_bivs, find_givs and find_induction_variables build the table of the real-world box in §2 (GCC 15) [GCC-IVOPTS]; the RTL-level unroller uses the older, non-SSA analysis in gcc/loop-iv.cc — iv_analyze_biv detects basic induction variables on registers exactly in the classic sense [GCC-LoopIV].
- LLVM has no separate classic detector:
llvm/lib/Analysis/IVDescriptors.cpp—InductionDescriptor::isInductionPHIanswers "is this phi \(\{a,+,b\}\)?" by asking ScalarEvolution, and the loop vectorizer uses it to find basic induction variables (LLVM 23.1.2) [LLVM-IVDesc].
Find where GCC does it. Open gcc/tree-ssa-loop-ivopts.cc at find_bivs. Question: what does GCC call a derived induction variable in that file? (Quiz iv-find-givs.)
SSA-based recognition (SCC classification)¶
LLVM
llvm/lib/Analysis/ScalarEvolution.cpp — ScalarEvolution::createNodeForPHI → createAddRecFromPHI recognizes a header phi whose latch operand is the phi plus a loop-invariant or recurrent term (the "Recurrence" case of Algorithm 18.2.6, found by walking the SSA graph from the phi rather than by an explicit SCC pass); createSimpleAffineAddRec handles the common i + c case directly [LLVM-SCEV]. llvm/lib/Analysis/IVDescriptors.cpp — RecurrenceDescriptor::isFixedOrderRecurrence recognizes exactly the wrap-around shape of Definition 18.2.5 (a header phi whose latch operand is a loop value), which the loop vectorizer then handles with a vector splice [LLVM-IVDesc] (LLVM 23.1.2).
- GCC
gcc/tree-scalar-evolution.cc—analyze_scalar_evolutionandanalyze_evolution_in_loopwalk the SSA graph from a loop phi and build a chain of recurrence (GCC 15) [GCC-SCEV] (Pop, Cohen and Silber's design [PCS05]).
The real-world box for this technique is in §2 (LLVM's SCEV on the running example).
8. Comparison¶
| 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 |
On the lab corpus (./course test 18, test ch18/lab/ivs-compare.test; reproduce with python3 labs/ch18-loops/provided/compare_ivs.py labs/ch18-loops/corpus/ivs.ll --plugin <build>/lib/PebblePasses.so --driver <build>/bin/ch18-loops): classic 34 IVs, SCC 58, and every classic IV is found by the SCC method with the same chain of recurrences.
Choose classic detection when you only need affine IVs of one family for strength reduction and have no SSA form. Choose SCC classification in any SSA compiler: it is linear, strictly more powerful, and its output feeds trip counts and dependence tests.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch18.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Classic induction-variable detection | iv-classic-found, iv-find-givs |
./course drill scev-form (the linear CRs are exactly the classic triples) |
classic-iv |
Lab Part A (A1) |
| SSA-based recognition (SCC classification) | iv-scc-order, iv-classes |
./course drill scev-form --difficulty hard |
ssa-iv |
E2 |
Pitfall
"The loop counter is the only induction variable" is the misconception this lesson exists to break: every address, every 4*i + 3, and every accumulated sum of a counter is an induction variable of some class, and the optimizations of this chapter need all of them.
References¶
See the chapter references.