Lesson 18.3 — Scalar evolution: chains of recurrences and trip counts¶
Techniques: chains of recurrences (Bachmann–Wang–Zima; van Engelen), LLVM's ScalarEvolution (add recurrences
{a,+,b}<flags><L>), trip counts and backedge-taken counts (including overflow) · Pebble implements: the CR algebra insidepebble-iv(E2); ★pebble-unrolluses trip counts (E4) · Lab:pebble-ivvs SCEV agreement (Part A) · Prerequisites: Lesson 18.2, Ch 9 (nsw/nuw, poison) · Time: 5–6 hours
Lesson 18.2 found the induction variables. This lesson gives them a precise algebra. The running sum
produces j = 0, 0, 1, 3, 6, 10, … and s = 0, 0, 0, 1, 4, 10, …. Both are polynomials in the iteration number, and a compiler can compute them — and their values when the loop exits — without running the loop, if it represents them the right way. The representation is the chain of recurrences, and with it comes the question every loop optimization asks first: how many times does this loop run?
1. Problem and motivation¶
The problem. Represent the value of every integer (and pointer) expression in a loop as a closed-form function of the iteration number, in a canonical form that can be added, multiplied, compared and evaluated symbolically; and from the loop's exit conditions, compute the number of iterations (the trip count) — exactly when possible, as an upper bound otherwise, and correctly in the presence of fixed-width wrap-around. In LLVM this is the ScalarEvolution analysis ("SCEV"), which almost every loop pass consumes: indvars, loop-reduce, loop-unroll, loop-vectorize, loop-idiom, irce, LoopAccessAnalysis, DependenceAnalysis.
Chains of recurrences¶
Bachmann, Wang and Zima introduced chains of recurrences (CRs) to evaluate a closed-form function at many equally spaced points with only additions: \(\{c_0, +, c_1, +, \dots, +, c_k\}\) describes the sequence whose \(k\)-th forward difference is constant [BWZ94]. Zima's earlier work on recurrence evaluation and van Engelen's application to compiler induction-variable analysis turned CRs into the standard representation of scalar evolution: van Engelen showed that CR algebra recognizes more induction variables than Wolfe's classification, with simpler code, and handles nested loops by letting coefficients be CRs of outer loops [vEn01].
LLVM ScalarEvolution¶
LLVM's ScalarEvolution implements CRs as add recurrences {Start,+,Step}<flags><L> inside a general symbolic-expression language (constants, unknown values, additions, multiplications, unsigned division, min/max, casts), with every expression hash-consed into a canonical form so that equality is pointer equality [LLVM-SCEV]. It is demand-driven: getSCEV(V) builds and caches the expression for one value. It adds what CRs alone do not have: no-wrap flags (nuw, nsw, nw) that record which recurrences provably do not overflow, and value ranges for every expression. GCC's tree-scalar-evolution.cc implements the same idea as "chrecs" [PCS05, GCC-SCEV].
Trip counts¶
The trip count connects the recurrences to the exit test: if the exit is taken when \(\{a,+,s\} \ge b\), the trip count is the least \(n\) that makes the test fail — a linear equation or inequality in \(n\), modulo \(2^w\). Classic compilers computed it only for DO loops with a known step; SCEV computes it for any exit whose condition compares two SCEV expressions, and reports a backedge-taken count, a constant maximum and a symbolic maximum [LLVM-SCEV]. Unrolling, vectorization, LFTR (Lesson 18.4) and bounds-check elimination (Lesson 18.9) all need it.
2. Definitions and algorithms¶
As in Lesson 18.2, \(n = 0, 1, 2, \dots\) is the iteration number, arithmetic is on \(w\)-bit integers modulo \(2^w\) unless stated otherwise, and \(\binom{n}{j}\) is the binomial coefficient (\(\binom{n}{j} = 0\) for \(j > n\)).
Chains of recurrences¶
Definition 18.3.1 (Chain of recurrences)
A (pure-sum) chain of recurrences of length \(k + 1\) is a tuple of loop-invariant values written \(\{c_0, +, c_1, +, \dots, +, c_k\}\). It denotes the sequence
Equivalently, recursively: \(\{c_0\}(n) = c_0\) and \(\{c_0, +, F\}(n) = c_0 + \sum_{m=0}^{n-1} F(m)\), where \(F = \{c_1, +, \dots, +, c_k\}\) — the sequence starts at \(c_0\) and its forward difference is \(F\). A geometric CR \(\{a, *, r\}\) denotes \(a \cdot r^{n}\). A CR with \(k = 1\) is linear; with \(k \ge 2\), polynomial of degree \(k\) (if \(c_k \ne 0\)).
The running sum
j \(= \{0, +, 0, +, 1\}\): \(j(n) = 0 + 0 \cdot n + \binom{n}{2}\), i.e. \(0, 0, 1, 3, 6, \dots\). s \(= \{0,+,0,+,0,+,1\}\): \(s(n) = \binom{n}{3}\), i.e. \(0, 0, 0, 1, 4, 10, \dots\).
Lemma 18.3.2 (Coefficients are forward differences)
Let \(f(n)\) be a sequence and \(\Delta f(n) = f(n+1) - f(n)\). Then \(f = \{c_0, +, \dots, +, c_k\}\) if and only if \(c_j = (\Delta^{j} f)(0)\) for \(j \le k\) and \(\Delta^{k+1} f = 0\). In particular every polynomial of degree \(k\) in \(n\) has exactly one CR of length \(k + 1\).
Proof
\(\Delta \binom{n}{j} = \binom{n+1}{j} - \binom{n}{j} = \binom{n}{j-1}\) (Pascal's rule), so \(\Delta \{c_0, +, c_1, \dots, c_k\} = \{c_1, +, \dots, +, c_k\}\) and \(\Delta^{k+1}\) of a CR of length \(k+1\) is \(0\). Evaluating at \(n = 0\), \(\binom{0}{j} = [j = 0]\), gives \((\Delta^j f)(0) = c_j\). Conversely, if \(\Delta^{k+1} f = 0\), then by Newton's forward-difference formula \(f(n) = \sum_{j=0}^{k} (\Delta^j f)(0) \binom{n}{j}\) (proved by induction on \(n\): \(f(n+1) = f(n) + \Delta f(n)\) and \(\Delta f\) satisfies the formula with the shifted coefficients). A polynomial of degree \(k\) has \(\Delta^{k+1} f = 0\), and the coefficients \((\Delta^j f)(0)\) are unique.
Lemma 18.3.3 (Sum and scaling)
\(\{a_0, +, \dots, +, a_k\} + \{b_0, +, \dots, +, b_k\} = \{a_0 + b_0, +, \dots, +, a_k + b_k\}\) (pad the shorter with zeros), and \(c \cdot \{a_0, +, \dots, +, a_k\} = \{c\,a_0, +, \dots, +, c\,a_k\}\) for invariant \(c\). A constant \(c\) is the CR \(\{c\}\).
Proof
Both sides are \(\sum_j (\dots) \binom{n}{j}\) and Definition 18.3.1 is linear in the coefficients; the identities hold in \(\mathbb{Z}\) and therefore modulo \(2^w\).
Lemma 18.3.4 (Product)
\(\{a, +, b\} \cdot \{c, +, d\} = \{a c, +, a d + b c + b d, +, 2 b d\}\). More generally the product of CRs of lengths \(k+1\) and \(m+1\) is a CR of length \(k + m + 1\), whose coefficients are the forward differences at 0 of the pointwise product (Lemma 18.3.2).
Proof
The product \(f(n) g(n)\) of polynomials of degrees \(k\) and \(m\) is a polynomial of degree at most \(k + m\), so by Lemma 18.3.2 it is the CR with coefficients \(\Delta^j (fg)(0)\), \(j \le k + m\). For the linear case: \((fg)(0) = ac\); \((fg)(1) = (a+b)(c+d)\), so \(\Delta(fg)(0) = ad + bc + bd\); \((fg)(2) = (a+2b)(c+2d)\), so \(\Delta^2 (fg)(0) = (a+2b)(c+2d) - 2(a+b)(c+d) + ac = 2bd\).
Lemma 18.3.5 (Prepend and shift)
(a) If \(x(0) = x_0\) and \(x(n+1) = x(n) + E(n)\) with \(E = \{e_0, +, \dots, +, e_k\}\), then \(x = \{x_0, +, e_0, +, \dots, +, e_k\}\). (b) The shifted sequence \(n \mapsto f(n+1)\) of \(f = \{c_0, +, \dots, +, c_k\}\) is \(\{c_0 + c_1, +, c_1 + c_2, +, \dots, +, c_{k-1} + c_k, +, c_k\}\). (c) If \(x(n+1) = r \cdot x(n)\) with a constant \(r\), then \(x = \{x_0, *, r\}\).
Proof
(a) The recursive form of Definition 18.3.1: \(\{x_0, +, E\}(n) = x_0 + \sum_{m<n} E(m)\) satisfies both equations, and they determine \(x\) uniquely by induction on \(n\). (b) \(\Delta^j\) of the shifted sequence at 0 is \((\Delta^j f)(1) = (\Delta^j f)(0) + (\Delta^{j+1} f)(0) = c_j + c_{j+1}\) (with \(c_{k+1} = 0\)); apply Lemma 18.3.2. (c) By induction, \(x(n) = x_0 r^n\).
Algorithm 18.3.6 (CR construction for the variables of a loop)
- Input: a loop body as a sequence of statements over integer variables: updates
x = x + e,x = x * r(a constant) for carried variables with initial values \(x_0\), and definitionsv = k * a + corv = k * a * b + cof body values. - Output: for each carried variable the CR of its value at the top of iteration \(n\); for each body value the CR of the value computed in iteration \(n\).
- Precondition: apart from self-updates, the "uses" relation between variables is acyclic (the case in which a recurrence has a CR; the drill generator guarantees it).
- Postcondition: every returned CR equals the variable's sequence (Theorem 18.3.12).
- Invariant: a CR is returned for a variable only after the CRs of everything its statement reads, as read by that statement, are final.
function CROf(x): # memoized
if x is carried and never updated: return {x0}
S ← the statement that updates / defines x, at position p
if S is "x = x * r": return {x0, *, r} # Lemma 18.3.5(c)
if S is "x = x + e": return Prepend(x0, ReadAt(e, p)) # Lemma 18.3.5(a)
if S is "v = k*a + c": return k·ReadAt(a, p) + {c} # Lemma 18.3.3
if S is "v = k*a*b + c": return k·(ReadAt(a, p) · ReadAt(b, p)) + {c} # Lemma 18.3.4
function ReadAt(y, p): # the CR of y as read by the statement at position p
if y is a constant: return {y}
C ← CROf(y)
if y is carried and y's own update is at a position < p: return Shift(C) # Lemma 18.3.5(b)
return C
function Prepend(x0, {e0, +, …, +, ek}): return {x0, +, e0, +, …, +, ek}
function Shift({c0, +, …, +, ck}): return {c0 + c1, +, …, +, c(k-1) + ck, +, ck}
LLVM's ScalarEvolution prints the chains of recurrences of the running sum
Reproduce (clang 23.1.2, opt 23.1.2):
cat > cr.c <<'X'
long tri(long n) { /* s = 0 + 0 + 1 + 3 + 6 + ... */
long s = 0, j = 0;
for (long i = 0; i < n; i++) {
s = s + j;
j = j + i;
}
return s;
}
long geo(long n) {
long g = 1;
for (long i = 0; i < n; i++)
g = g * 2;
return g;
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm cr.c -o - |
opt -passes='mem2reg,print<scalar-evolution>' -disable-output 2>&1 |
awk '/^ %(s|j|i|g)\.0 =|^ %mul =/ {v = $1; next} v && /-->/ {sub(/ U: .*/, ""); sub(/^ --> /, ""); print v " = " $0; v = ""}'
Output (complete):
%j.0 = {0,+,0,+,1}<%for.cond>
%s.0 = {0,+,0,+,0,+,1}<%for.cond>
%i.0 = {0,+,1}<nuw><nsw><%for.cond>
%g.0 = %g.0
%i.0 = {0,+,1}<nuw><nsw><%for.cond>
%mul = (2 * %g.0)<nuw>
What to notice: the polynomial recurrences are exactly the CRs of the example after Definition 18.3.1 (s is \(\binom{n}{3}\)). SCEV has add recurrences only: the geometric g \(= \{1,*,2\}\) is left as the unknown %g.0, and g * 2 is an ordinary multiplication of it — the class of Definition 18.3.1 that van Engelen's CR algebra has and LLVM's does not.
LLVM ScalarEvolution¶
Definition 18.3.7 (SCEV expressions; add recurrences with no-wrap flags)
A SCEV expression of \(w\)-bit type is one of: a constant; vscale; an unknown \(\langle V \rangle\) (an IR value SCEV does not look into); \((e_1 + \dots + e_m)\); \((e_1 * \dots * e_m)\); \((e_1 \,/_u\, e_2)\); smax/umax/smin/umin; trunc/zext/sext/ptrtoint casts; or an add recurrence \(\{e_0, +, e_1, +, \dots, +, e_k\}\langle L \rangle\) whose operands are invariant in loop \(L\) (they may be add recurrences of outer loops). Its value in iteration \(n\) of \(L\) is Definition 18.3.1 evaluated modulo \(2^w\). Flags qualify an add recurrence:
nuw: evaluated in unbounded unsigned integers, no value in the iterations that execute exceeds \(2^w - 1\) (no unsigned wrap);nsw: likewise for the signed range \([-2^{w-1}, 2^{w-1})\);nw: the value never wraps around its full range (it does not cross its starting point) — "no self-wrap".
Expressions are canonical: operands of commutative operators are sorted, constants folded, nested sums flattened, and each expression is unique in memory.
Algorithm 18.3.8 (getSCEV: demand-driven construction)
- Input: an IR value \(V\); the loop forest and dominator tree.
- Output: the canonical SCEV expression of \(V\) (cached).
- Precondition: SSA form; loops in loop-simplify form for recurrences to be recognized.
- Postcondition: the expression evaluates to \(V\)'s value in every iteration of every enclosing loop (Theorem 18.3.12 for the recurrence case).
- Invariant: the cache maps values to final expressions; a phi under construction is temporarily mapped to the unknown \(\langle \varphi \rangle\), which is what makes recursion through cycles terminate.
function getSCEV(V):
if V in cache: return cache[V]
if V is a constant: e ← Constant(V)
else if V = add/sub/mul/shl/udiv/cast of operands a, b:
e ← Fold(op, getSCEV(a), getSCEV(b)) # canonicalize: sort, fold, flatten;
# {a,+,b}+c = {a+c,+,b}; c·{a,+,b} = {c·a,+,c·b}
# {a,+,b}·{c,+,d} per Lemma 18.3.4
else if V is a header phi of L with operands (init from preheader, back from latch):
cache[V] ← Unknown(V) # break the cycle
B ← getSCEV(back)
if B = (Unknown(V) + X) with X invariant in L (X may itself be a recurrence of L):
e ← AddRec(getSCEV(init), X, L) # Lemma 18.3.5(a)
infer no-wrap flags (from nsw/nuw on the increment, from ranges)
else: e ← Unknown(V)
forget every expression built while cache[V] was Unknown(V); recompute them
else: e ← Unknown(V) # loads, calls, non-header phis …
cache[V] ← e
return e
SCEV of an array address: byte offsets, flags and the exit value
Reproduce (clang 23.1.2, opt 23.1.2):
cat > iv.c <<'X'
long f(long *a, long n) {
long s = 0;
for (long i = 0; i < n; i++)
s += a[4 * i + 3];
return s;
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm iv.c -o - |
opt -passes='mem2reg,print<scalar-evolution>' -disable-output 2>&1 |
tr '\t' ' ' | sed -e 's/ *LoopDispositions.*//' |
awk '/^ %/ {keep = ($1 != "%s.0" && $1 != "%0" && $1 != "%add1")} keep || !/^ /'
Output (the accumulator s and the loaded value are filtered out):
Printing analysis 'Scalar Evolution Analysis' for function 'f':
Classifying expressions for: @f
%i.0 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
--> {0,+,1}<nuw><nsw><%for.cond> U: [0,-9223372036854775808) S: [0,-9223372036854775808) Exits: (0 smax %n)
%mul = mul nsw i64 4, %i.0
--> {0,+,4}<%for.cond> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * (0 smax %n))
%add = add nsw i64 %mul, 3
--> {3,+,4}<%for.cond> U: full-set S: full-set Exits: (3 + (4 * (0 smax %n)))<nuw><nsw>
%arrayidx = getelementptr inbounds i64, ptr %a, i64 %add
--> {(24 + %a),+,32}<%for.cond> U: full-set S: full-set Exits: (24 + (32 * (0 smax %n)) + %a)
%inc = add nsw i64 %i.0, 1
--> {1,+,1}<nuw><%for.cond> U: [1,-9223372036854775807) S: [1,-9223372036854775807) Exits: (1 + (0 smax %n))<nuw>
Determining loop execution counts for: @f
Loop %for.cond: backedge-taken count is (0 smax %n)
Loop %for.cond: constant max backedge-taken count is i64 9223372036854775807
Loop %for.cond: symbolic max backedge-taken count is (0 smax %n)
Loop %for.cond: Trip multiple is 1
What to notice: U: and S: are the unsigned and signed ranges SCEV derived for each value; Exits: is the value in the last iteration, obtained by evaluating the recurrence at the backedge-taken count (Lemma 18.3.2 with \(n = \mathrm{BTC}\)). The address a + 8·(4i + 3) is the add recurrence \(\{24 + a, +, 32\}\) in bytes — pointer recurrences are how LSR and the vectorizer see array accesses. The nuw/nsw flags of {0,+,1} come from the nsw on %inc and the fact that i starts at 0 and stops at n.
Trip counts¶
Definition 18.3.9 (Trip count, backedge-taken count)
For one entry into a loop \(L\), the trip count \(\mathrm{TC}\) is the number of times the loop's body is executed, and the backedge-taken count \(\mathrm{BTC}\) is the number of times the latch → header edge is taken. For a top-tested loop (the exit test in the header, while/for before rotation) the header runs \(\mathrm{TC} + 1\) times and \(\mathrm{BTC} = \mathrm{TC}\); for a bottom-tested loop (after rotation, do-while) the header is the first body block, it runs \(\mathrm{TC}\) times and \(\mathrm{BTC} = \mathrm{TC} - 1\). Either may be \(\infty\). For the counted loop for (i = a; i PRED b; i += s) on \(w\)-bit integers, \(\mathrm{TC}\) is the least \(k \ge 0\) such that the test fails for the value \(a + k\,s \bmod 2^w\), or \(\infty\) if none exists.
Lemma 18.3.10 (Linear congruences modulo a power of two)
Let \(m = 2^w\), \(s, d \in \mathbb{Z}\), \(g = \gcd(s \bmod m, m)\). The congruence \(s\,k \equiv d \pmod m\) has a solution iff \(g \mid d\); then its least non-negative solution is \(k_0 = (d/g) \cdot (s/g)^{-1} \bmod (m/g)\), where the inverse is taken modulo \(m/g\) (\(s/g\) is odd, hence invertible modulo the power of two \(m/g\)).
Proof
If \(s k - d = q m\) then \(g \mid s\) and \(g \mid m\) give \(g \mid d\). Conversely, if \(g \mid d\), divide by \(g\): \((s/g) k \equiv d/g \pmod{m/g}\). Since \(g\) contains every factor 2 of \(s\) that \(m\) has room for, \(s/g\) is odd whenever \(m/g > 1\), so it has an inverse modulo \(m/g\), and the solutions are exactly \(k \equiv (d/g)(s/g)^{-1} \pmod{m/g}\); the least non-negative one is the residue \(k_0 \in [0, m/g)\). (If \(m/g = 1\), every \(k\) works and \(k_0 = 0\).)
Algorithm 18.3.11 (Trip count of a counted loop)
- Input: \(a\), a predicate \(\mathrm{PRED} \in \{\ne, <, \le, >, \ge\}\) (signed or unsigned), \(b\), a step \(s\), a width \(w\).
- Output: \(\mathrm{TC}\) of Definition 18.3.9, or \(\infty\).
- Precondition: \(a\), \(b\), \(s\) are known (constants, or symbolic with the no-wrap facts stated below).
- Postcondition: the result equals the brute-force count (Theorems 18.3.13, 18.3.14).
- Invariant: (wrap walk) after \(k\) steps the variable holds \(a + k s \bmod 2^w\) and the test has held for all smaller \(k\).
function TripCount(a, PRED, b, s, w):
if PRED is "≠":
return LeastSolution(s·k ≡ b - a (mod 2^w)) or ∞ # Lemma 18.3.10
if the test fails for a: return 0
if PRED is "<" or "≤" and s > 0 (as a value of the comparison's signedness):
last ← (b - 1 if "<" else b) # largest value that passes
k ← ⌊(last - a) / s⌋ + 1 # values a, a+s, …, ≤ last
if a + k·s ≤ MAX (the type's maximum): return k # no wrap: Theorem 18.3.14(a)
return WrapWalk(k) # Theorem 18.3.14(b)
symmetric for ">" and "≥" with s < 0
otherwise (step in the wrong direction or zero): return WrapWalk(0)
function WrapWalk(k0): # continue after the wrap: i mod 2^w has period P = 2^w / gcd(s, 2^w)
for k from k0 to k0 + P: if the test fails for a + k·s mod 2^w: return k
return ∞
SCEV computes backedge-taken counts for wrapping i8 loops
Reproduce (opt 23.1.2):
cat > tc.ll <<'X'
; do { i = i + 4; } while (i != B), i8, starting from i = 10: the latch tests i.next
define void @ne(i8 %b) {
entry:
br label %loop
loop:
%i = phi i8 [ 10, %entry ], [ %i.next, %loop ]
%i.next = add i8 %i, 4
%c = icmp ne i8 %i.next, %b
br i1 %c, label %loop, label %exit
exit:
ret void
}
define void @ne2() {
entry:
br label %loop
loop:
%i = phi i8 [ 10, %entry ], [ %i.next, %loop ]
%i.next = add i8 %i, 4
%c = icmp ne i8 %i.next, 2
br i1 %c, label %loop, label %exit
exit:
ret void
}
define void @ne3() {
entry:
br label %loop
loop:
%i = phi i8 [ 10, %entry ], [ %i.next, %loop ]
%i.next = add i8 %i, 4
%c = icmp ne i8 %i.next, 3
br i1 %c, label %loop, label %exit
exit:
ret void
}
define void @ne6() {
entry:
br label %loop
loop:
%i = phi i8 [ 10, %entry ], [ %i.next, %loop ]
%i.next = add i8 %i, 6
%c = icmp ne i8 %i.next, 2
br i1 %c, label %loop, label %exit
exit:
ret void
}
X
opt -passes='print<scalar-evolution>' -disable-output tc.ll 2>&1 |
grep -E '^Determining|^Loop .*(: backedge-taken count is|Unpredictable backedge|Predicated backedge-taken count is)'
Output (complete):
Determining loop execution counts for: @ne
Loop %loop: Unpredictable backedge-taken count.
Loop %loop: Predicated backedge-taken count is ((-14 + %b) /u 4)
Determining loop execution counts for: @ne2
Loop %loop: backedge-taken count is i8 61
Determining loop execution counts for: @ne3
Loop %loop: Unpredictable backedge-taken count.
Determining loop execution counts for: @ne6
Loop %loop: backedge-taken count is i8 83
What to notice: each latch test sees \(\{14, +, 4\}\) (or \(\{16,+,6\}\)), so BTC is the trip count of for (i = 14; i != B; i += 4). For @ne2 that is the solution of \(4k \equiv 2 - 14 \pmod{256}\), \(k = 61\); for @ne6, \(6k \equiv 242\) gives \(k = 83\) (§3); for @ne3 the difference \(3 - 14 \equiv 245\) is odd and \(\gcd(4, 256) = 4\) does not divide it — the loop never exits (Lemma 18.3.10), so no count exists. With a symbolic bound (@ne) SCEV can only give the count under the predicate that \(b - 14\) is a multiple of 4 — a runtime check the vectorizer can emit (Lesson 18.8).
3. Worked example¶
Chains of recurrences on the running example¶
Algorithm 18.3.6 on tri (statements in order: s = s + j at position 1, j = j + i at 2, i = i + 1 at 3; initial values all 0):
| step | call | rule | result |
|---|---|---|---|
| 1 | CROf(s) | s = s + j: Prepend(0, ReadAt(j, 1)) |
needs CROf(j) |
| 2 | CROf(j) | j = j + i: Prepend(0, ReadAt(i, 2)) |
needs CROf(i) |
| 3 | CROf(i) | i = i + 1: Prepend(0, {1}) |
\(\{0,+,1\}\) |
| 4 | ReadAt(i, 2) | i's update is at 3 > 2: not shifted |
\(\{0,+,1\}\) |
| 5 | CROf(j) | Prepend(0, \(\{0,+,1\}\)) | \(\{0,+,0,+,1\}\) |
| 6 | ReadAt(j, 1) | j's update is at 2 > 1: not shifted |
\(\{0,+,0,+,1\}\) |
| 7 | CROf(s) | Prepend(0, \(\{0,+,0,+,1\}\)) | \(\{0,+,0,+,0,+,1\}\) |
Check by Lemma 18.3.2 (forward differences of the simulated values):
| variable | n=0 | 1 | 2 | 3 | 4 | 5 | \(\Delta^0,\Delta^1,\Delta^2,\Delta^3\) at 0 |
|---|---|---|---|---|---|---|---|
| i | 0 | 1 | 2 | 3 | 4 | 5 | 0, 1, 0, 0 |
| j | 0 | 0 | 1 | 3 | 6 | 10 | 0, 0, 1, 0 |
| s | 0 | 0 | 0 | 1 | 4 | 10 | 0, 0, 0, 1 |
and the closed form of \(s\) is \(\binom{n}{3} = \tfrac{1}{3}n - \tfrac{1}{2}n^2 + \tfrac{1}{6}n^3\) (cr_closed_form in tools/course/lib/loops.py). Had the body been j = j + i; s = s + j; (swapped), step 6 would read j after its update and use Shift(\(\{0,+,0,+,1\}\)) = \(\{0,+,1,+,1\}\), giving \(s = \{0,+,0,+,1,+,1\}\) — the pitfall the scev-form drill checks for.
Try it
./course drill scev-form --seed 3 --difficulty hard --solution shows this derivation on a loop with a polynomial, a geometric and a product variable.
LLVM ScalarEvolution on the running example¶
getSCEV(%arrayidx) for the address in iv.c (the real-world box above), each line one call of Algorithm 18.3.8:
| call | V | rule | result (cached) |
|---|---|---|---|
| 1 | %arrayidx = gep i64, %a, %add |
pointer arithmetic: \(a + 8 \cdot\) getSCEV(%add) |
pending |
| 2 | %add = add %mul, 3 |
Fold(+, getSCEV(%mul), 3) |
pending |
| 3 | %mul = mul 4, %i.0 |
Fold(*, 4, getSCEV(%i.0)) |
pending |
| 4 | %i.0 = phi [0], [%inc] |
header phi: cache ← \(\langle i.0 \rangle\), getSCEV(%inc) |
pending |
| 5 | %inc = add %i.0, 1 |
Fold(+, \(\langle i.0 \rangle\), 1) = \((1 + \langle i.0 \rangle)\) | temporary |
| 6 | back in 4 | back = \(\langle i.0 \rangle + 1\): AddRec(0, 1); nsw on %inc + range → nuw, nsw |
\(\{0,+,1\}\langle nuw, nsw \rangle\); forget step 5 |
| 7 | back in 3 | \(4 \cdot \{0,+,1\} = \{0,+,4\}\) (Lemma 18.3.3) | \(\{0,+,4\}\) |
| 8 | back in 2 | \(\{0,+,4\} + 3 = \{3,+,4\}\) | \(\{3,+,4\}\) |
| 9 | back in 1 | \(a + 8 \cdot \{3,+,4\} = \{24 + a,+,32\}\) | \(\{(24 + a),+,32\}\) |
Trip counts on the running example¶
The four loops of the trip-count box, as for (i = 14; i != B; i += 4) on u8 (and step 6 from 16), by Algorithm 18.3.11:
| loop | congruence \(s k \equiv b - a \pmod{256}\) | \(g = \gcd(s, 256)\) | \(g \mid d\)? | reduced | inverse | \(k_0\) | SCEV BTC |
|---|---|---|---|---|---|---|---|
| @ne2: 14 → 2, step 4 | \(4k \equiv 244\) | 4 | yes | \(k \equiv 61 \pmod{64}\) | \(1^{-1} = 1\) | 61 | 61 |
| @ne6: 16 → 2, step 6 | \(6k \equiv 242\) | 2 | yes | \(3k \equiv 121 \pmod{128}\) | \(3^{-1} = 43\) (\(3 \cdot 43 = 129\)) | \(121 \cdot 43 \bmod 128 = 83\) | 83 |
| @ne3: 14 → 3, step 4 | \(4k \equiv 245\) | 4 | no | — | — | \(\infty\) | Unpredictable |
A < loop that wraps: for (u8 i = 250; i < 255; i += 3) passes 250, 253, then \(256 \equiv 0\) still passes: the no-wrap case would give \(\lfloor (254 - 250)/3 \rfloor + 1 = 2\) with \(250 + 2 \cdot 3 = 256 > 255\), so Algorithm 18.3.11 walks on: 0, 3, …, 252 (85 more values) and then 255 fails: TC \(= 2 + 85 = 87\) (./course drill trip-count computes exactly this; trip_count_simulate agrees).
Try it
./course drill trip-count --seed 5 --difficulty hard (8-bit loops that may wrap), then --solution.
4. Invariants and correctness¶
Chains of recurrences¶
Theorem 18.3.12 (Algorithm 18.3.6 is correct)
Under its precondition, Algorithm 18.3.6 terminates and returns, for every variable, the CR of its sequence (at the top of iteration \(n\) for carried variables, in iteration \(n\) for body values).
Proof
Termination: CROf is memoized and each call recurses only into variables its statement reads, other than itself; by the precondition this relation is acyclic, so the recursion depth is bounded by the number of variables. Correctness, by induction along that acyclic order. Let the statement of \(x\) be at position \(p\). A variable \(y\) read at \(p\) has, at that moment of iteration \(n\), the value \(y(n)\) if \(y\) is not updated before \(p\) in the body, and \(y(n+1)\) (its value at the top of the next iteration) if it is — hence ReadAt returns \(\mathrm{CR}(y)\) or its shift (Lemma 18.3.5(b)), correct by the induction hypothesis. For x = x + e, \(x(n+1) = x(n) + e_{\text{read}}(n)\) and \(x(0) = x_0\): Lemma 18.3.5(a). For x = x * r: Lemma 18.3.5(c). For body values, Lemmas 18.3.3 and 18.3.4. Every step holds modulo \(2^w\) as well, since the lemmas are ring identities (binomial coefficients are integers).
LLVM ScalarEvolution¶
The correctness of getSCEV for a header phi is Lemma 18.3.5(a) with \(E\) = the invariant step, and of the folding rules Lemmas 18.3.3–18.3.4 — Theorem 18.3.12 restricted to the shapes SCEV recognizes. The subtle part is the flags: a flag may be attached only if it holds in every iteration that executes. LLVM infers nsw on \(\{0,+,1\}\) above from the nsw flag of %inc together with the fact that the loop's execution is guarded by i < n (an overflowing add nsw would be poison, and a poison branch condition is undefined behavior, so a well-defined run cannot overflow); the verification of such inferences is part of ScalarEvolution::createAddRecFromPHI and the "strengthen no-wrap flags" helpers [LLVM-SCEV].
Trip counts¶
Theorem 18.3.13 (Trip count of a ≠ loop)
For for (i = a; i != b; i += s) on \(w\)-bit integers, \(\mathrm{TC}\) is the least non-negative solution \(k_0\) of \(s k \equiv b - a \pmod{2^w}\) if \(\gcd(s \bmod 2^w, 2^w)\) divides \(b - a\), and \(\infty\) otherwise.
Proof
The value tested in iteration \(k\) is \(a + k s \bmod 2^w\) (the addition wraps). The test fails exactly when \(a + ks \equiv b\), i.e. \(s k \equiv b - a \pmod {2^w}\). \(\mathrm{TC}\) is the least such \(k\); by Lemma 18.3.10 it is \(k_0\) when a solution exists, and no iteration fails the test otherwise.
Theorem 18.3.14 (Trip count of a < loop, with and without wrap)
For for (i = a; i < b; i += s) with \(s > 0\) and comparison in the signed or unsigned interpretation with maximum \(M\) (so \(a, b \le M\)): (a) if \(a \ge b\) then \(\mathrm{TC} = 0\); otherwise let \(k = \lceil (b - a)/s \rceil\); if \(a + k s \le M\) (computed in \(\mathbb{Z}\)), then \(\mathrm{TC} = k\). (b) If \(a + ks > M\), the variable wraps before the test can fail at \(a + ks\), and \(\mathrm{TC} = k + \mathrm{TC}'\), where \(\mathrm{TC}'\) is the trip count of the same loop started at \((a + k s) \bmod 2^w\) (interpreted), which is either found within \(2^w / \gcd(s, 2^w)\) further steps or is \(\infty\). (c) If the increment carries nsw (signed) or nuw (unsigned) and the loop has no undefined behavior, case (b) cannot occur.
Proof
(a) For \(a < b\): the values \(a + js\), \(0 \le j < k\), are all \(< b\) (since \(js < b - a\) for \(j < k\)) and none of them exceeds \(M\), so no wrap occurred and the test passed \(k\) times; \(a + ks \ge b\) is the first failing value, and it is representable when \(a + ks \le M\), so the test fails there: \(\mathrm{TC} = k\). (b) If \(a + ks > M\), the \(k\)-th value wraps to \((a + ks) - 2^w\), which may pass the test again (it need not lie below \(a\): u8 \(a = 0\), \(s = 200\) wraps to 144); from there the loop behaves as a fresh loop starting at that value. Since \(i \bmod 2^w\) takes the values of the arithmetic progression with period \(P = 2^w/\gcd(s, 2^w)\), if the test does not fail within \(P\) further steps the sequence repeats and it never fails. (c) With nsw/nuw, the step that would wrap produces poison; the next test branches on poison, which is undefined behavior; a run without undefined behavior therefore never reaches that step, so only case (a) remains — this is why SCEV's counts for nsw loops are simple closed forms ((0 smax %n) above) and why the C rule "signed overflow is undefined" makes loops analyzable.
When it breaks. Without no-wrap facts the formula of (a) is wrong for symbolic bounds near the top of the range: for (u8 i = 250; i < b; i += 3) with \(b = 255\) runs 87 times, not 2. SCEV guards against it: for @b (i != n step 2) and @a in the second trip-count box of §7 it either proves no wrap from the nsw flag or returns "Unpredictable" / a predicated count.
5. Complexity¶
\(N\) = number of SSA values in the function, \(k\) = maximal CR length, \(w\) = bit width.
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| Chains of recurrences | \(O(k)\) per sum, \(O(k^2)\) per product (Lemma 18.3.4 via \(k\) differences) | \(k \le 3\) in practice | \(O(k)\) per CR | \(k\) CR length |
| LLVM ScalarEvolution | expression canonicalization is superlinear (sorting operands of \(m\)-ary sums: \(O(m \log m)\)); per value amortized over the cache | near-linear in \(N\) with caching | \(O(N)\) expressions | \(N\) values |
| Trip counts | \(O(w^2)\) bit operations for the congruence (extended Euclid / Newton inverse on \(w\)-bit numbers); \(O(1)\) symbolic for < |
constant | \(O(1)\) | \(w\) bits |
Proposition 18.3.15 (Cost of the trip-count formulas)
Algorithm 18.3.11 decides the ≠ case with one gcd and one modular inverse of \(w\)-bit numbers (\(O(w^2)\) bit operations with schoolbook arithmetic), and the < case without wrap with one division; the wrap walk takes at most \(2^w/\gcd(s, 2^w)\) steps.
Proof
The gcd of two \(w\)-bit numbers by Euclid's algorithm takes \(O(w)\) division steps of \(O(w)\) bit operations each amortized (\(O(w^2)\) in total by the standard analysis), and the inverse of an odd number modulo \(2^j\) by extended Euclid costs the same; the division for the < case is one \(w\)-bit division. The walk bound is the period of \(a + ks \bmod 2^w\) in \(k\).
Pathological input. The wrap walk is exponential in \(w\): an 8-bit loop needs at most 256 steps, a 64-bit one \(2^{64}\) — which is why the drill uses \(w = 8\) for wrapping loops and why no compiler walks: SCEV returns "Unpredictable" or a predicated count instead. For SCEV itself, deeply nested sums of many unknowns (machine-generated code) make canonicalization expensive; LLVM caps expression size and depth with hidden options such as scalar-evolution-max-arith-depth [LLVM-SCEV].
At scale. ScalarEvolution is among the more expensive analyses in LLVM's pipeline but is computed lazily and preserved across loop passes; the loop pass manager keeps it alive through a whole loop(...) pipeline to avoid recomputation (LoopStandardAnalysisResults).
6. Variants and refinements¶
Chains of recurrences¶
- Multivariate CRs [vEn01]: coefficients may be CRs of outer loops, e.g. \(\{\{0,+,m\}_i, +, 1\}_j\) for
i*m + j— trade-off: more algebra, but nested loops and linearized subscripts become analyzable (LLVM's nested add recurrences). - CRs with other operators [BWZ94]: \(\{a, *, r\}\) (geometric) and mixed chains \(\{a, +, b, *, r\}\) — trade-off: not closed under all operations; LLVM drops them.
LLVM ScalarEvolution¶
- Predicated SCEV (
PredicatedScalarEvolution): add assumptions such as "no wrap" or "\(b - 14\) is a multiple of 4" and let the client (the vectorizer) check them at run time — trade-off: code versioning (Lesson 18.5). - GCC's chrecs [PCS05]: the same algebra with "delayed abstraction" (a chrec may stay symbolic until instantiated in a given loop) — trade-off: different engineering, same power.
Trip counts¶
- Upper bounds instead of exact counts: from array sizes or
inboundsGEPs ("constant max backedge-taken count") — trade-off: good enough for unrolling decisions, not for LFTR. - Multiple exits: the exact count is the minimum over exits, the symbolic max is an upper bound computed from exits that dominate the latch — trade-off: precision vs generality (SCEV's
getBackedgeTakenCount(L, SymbolicMaximum)).
7. In real compilers¶
Chains of recurrences¶
GCC
gcc/tree-chrec.cc — chrec_fold_plus, chrec_fold_multiply and chrec_apply implement Lemmas 18.3.3–18.3.4 and Definition 18.3.1's evaluation on "polynomial chrecs" {base, +, step}_loop (GCC 15) [GCC-Chrec].
- LLVM
llvm/lib/Analysis/ScalarEvolution.cpp—SCEVAddRecExpr::evaluateAtIterationevaluates a recurrence as \(\sum_j c_j \binom{n}{j}\) using the helperBinomialCoefficient(Definition 18.3.1 verbatim) [LLVM-SCEV].
The real-world box for this technique is in §2 (the running sum in LLVM).
LLVM ScalarEvolution¶
LLVM
llvm/lib/Analysis/ScalarEvolution.cpp — ScalarEvolution::getAddExpr, getMulExpr, getAddRecExpr (canonicalization and folding), createNodeForPHI → createAddRecFromPHI (the header-phi case of Algorithm 18.3.8); llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h — the expression classes SCEVAddRecExpr, SCEVUnknown, … [LLVM-SCEVExpr] (LLVM 23.1.2).
- GCC
gcc/tree-scalar-evolution.cc—analyze_scalar_evolution,instantiate_scev(GCC 15) [GCC-SCEV].
Find where LLVM does it. In ScalarEvolution.cpp, find the function that turns a header phi into an add recurrence. Question: what is its name? (Quiz scev-find-addrec.)
The real-world box for this technique is in §2 (the address recurrence {(24 + %a),+,32}).
Trip counts¶
LLVM
llvm/lib/Analysis/ScalarEvolution.cpp — computeBackedgeTakenCount → computeExitLimit → computeExitLimitFromICmp, which dispatches to howFarToZero for ≠ exits (it calls SolveLinEquationWithOverflow, Lemma 18.3.10) and howManyLessThans for < exits (Theorem 18.3.14, with the no-wrap reasoning of (c)); getSmallConstantTripCount returns BTC + 1 when it is a small constant [LLVM-SCEV] (LLVM 23.1.2).
- GCC
gcc/tree-ssa-loop-niter.cc—number_of_iterations_exit,number_of_iterations_ne,number_of_iterations_lt(GCC 15) [GCC-Niter].
Backedge-taken counts SCEV derives for typical C loops
Reproduce (clang 23.1.2, opt 23.1.2):
cat > tc.c <<'X'
void use(long);
void a(long n) { for (long i = 0; i < n; i += 3) use(i); }
void b(long n) { for (long i = 0; i != n; i += 2) use(i); }
void e(long n) { for (long i = n; i > 0; i -= 2) use(i); }
void f(int n) { for (int i = 0; i <= n; i++) use(i); }
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm tc.c -o - |
opt -passes='mem2reg,print<scalar-evolution>' -disable-output 2>&1 |
grep -E '^Determining|^Loop .*(: backedge-taken count is|Unpredictable backedge|Predicated backedge-taken count is)'
Output (complete):
Determining loop execution counts for: @a
Loop %for.cond: backedge-taken count is ((((-1 * (1 umin (0 smax %n)))<nuw><nsw> + (0 smax %n)) /u 3) + (1 umin (0 smax %n)))
Determining loop execution counts for: @b
Loop %for.cond: Unpredictable backedge-taken count.
Loop %for.cond: Predicated backedge-taken count is (%n /u 2)
Determining loop execution counts for: @e
Loop %for.cond: backedge-taken count is ((1 + (-1 * (0 smin %n)) + %n) /u 2)
Determining loop execution counts for: @f
Loop %for.cond: backedge-taken count is (1 + (-1 smax %n))
What to notice: these are top-tested loops, so BTC = TC (Definition 18.3.9). For @a, with \(N = \max(n, 0)\), the expression is \(\lfloor (N - [N \ge 1]) / 3 \rfloor + [N \ge 1] = \lceil N/3 \rceil\) — Theorem 18.3.14(a) written without a division that rounds up. @b (!= with step 2) has no count unless \(n\) is even (Theorem 18.3.13: \(\gcd(2, 2^{64}) = 2\) must divide \(n\)), so SCEV offers only a predicated count. @f (<= on int, \(n\) up to INT_MAX) is finite only because signed overflow is undefined (Theorem 18.3.14(c)): the count is \(\max(n, -1) + 1\).
8. Comparison¶
| 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 |
Choose chains of recurrences as the internal representation of any induction-variable analysis: they compose. Choose a SCEV-like canonical expression language when many clients must compare and simplify loop expressions (equality by pointer comparison pays off). Compute trip counts with the congruence for ≠ and with no-wrap facts for <; never assume "no overflow" without a flag or a proof.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch18.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Chains of recurrences | cr-product, cr-value |
./course drill scev-form |
chains-of-recurrences |
E2 |
| LLVM ScalarEvolution | scev-gep-bytes, scev-find-addrec |
./course drill scev-form --difficulty hard |
scev |
E2 (SCEV agreement test) |
| Trip counts | tc-ne-i8, tc-wrap |
./course drill trip-count |
trip-count |
E4 (★ uses them) |
Pitfall
The trip count is not \(\lceil (b - a)/s \rceil\) in general. It is that only for <-style loops that cannot wrap; for != loops it is a congruence that may have no solution, and for wrapping types the loop may run far longer or forever. "Backedge-taken count" and "trip count" also differ by one in rotated loops.
References¶
See the chapter references.