Lesson 18.4 — Strength reduction and linear-function test replacement¶
Techniques: Allen–Cocke–Kennedy strength reduction, operator strength reduction (Cooper–Simpson–Vick), LLVM's Loop Strength Reduce (formulae and a cost model), linear-function test replacement · Pebble implements: OSR (
pebble-osr, E3) · Lab: classic strength reduction (labs/ch18-loops, Part B) vs yourpebble-osr, compared by instruction counts and checked withlli· Prerequisites: Lesson 18.2, Lesson 18.3, Ch 12, Lesson 12.3 (strength reduction of single operations by powers of two) · Time: 4–5 hours
Ch 12 replaced one multiplication by a shift. Loop strength reduction removes multiplications altogether: if i goes \(0, 1, 2, \dots\) then 4*i + 3 goes \(3, 7, 11, \dots\), and the next value is the previous one plus 4. So instead of multiplying every iteration, keep a second variable that starts at 3 and grows by 4. After that, the original counter may only be needed for the exit test, and rewriting the test in terms of the new variable (linear-function test replacement, LFTR) lets the counter disappear too.
1. Problem and motivation¶
The problem. Given a loop and its induction variables, replace each loop-varying multiplication iv * c (with c loop-invariant) by a new induction variable updated with an addition, and then, where possible, rewrite the loop's exit test so that induction variables used only by the test can be deleted. The result computes the same values with cheaper operations and — on machines with addressing modes — often with fewer registers. pebblec -O1 runs your OSR pass; LLVM runs indvars (which does LFTR) in the middle of the pipeline and loop-reduce (LSR) just before instruction selection, where the target's addressing modes are known.
Allen–Cocke–Kennedy strength reduction¶
The classical algorithm works on derived induction variables \(j = c \cdot i + d\) of Lesson 18.2: for each, create a temporary initialized to \(c \cdot i_0 + d\) before the loop and incremented by \(c \cdot \mathrm{step}\) right after every increment of \(i\); replace \(j\) by the temporary [ACK81]. It was the central loop optimization of FORTRAN compilers (Allen and Cocke's catalogue lists it [AC72b]); its textbook form is in Muchnick [Muchnick, §14.1.2].
Operator strength reduction¶
Cooper, Simpson and Vick reformulated strength reduction on SSA form: one depth-first walk of the SSA graph finds the induction variables as SCCs (as in Lesson 18.2) and, whenever it meets a candidate operation iv × rc, iv ± rc with a region constant rc, creates the reduced induction variable on the fly, reusing reductions through a hash table [CSV01]. It needs no separate induction-variable pass and no iteration to a fixed point, and it comes with an integrated LFTR. It is the algorithm of Engineering a Compiler [EaC3, Ch. 10] and of pebble-osr.
LLVM Loop Strength Reduce¶
Modern targets change the question: a load of a[4*i + 3] on x86 can use the addressing mode base + 8*index + 24 for free, so the best choice of induction variables depends on which addresses the target can fold, how many registers the loop can afford, and what the exit compare needs. LLVM's LSR collects every use of an induction variable, generates alternative formulae for each (base registers, a scaled register, an immediate offset), and chooses one formula per use minimizing a target-provided cost (registers first, then instructions) [LLVM-LSR]. GCC's ivopts makes the same decision with a different search ("IV candidates" and a cost per use/candidate pair) [GCC-IVOPTS].
Linear-function test replacement¶
LFTR rewrites a loop's exit test i < n into an equivalent test on another induction variable, such as 4*i + 3 < 4*n + 3, typically as an equality iv != limit with the limit computed from the trip count. Then the original counter, used only by the test and its own increment, becomes dead. It is part of the original strength-reduction work [ACK81] and of OSR [CSV01]; LLVM does it in indvars (linearFunctionTestReplace), GCC in ivopts (rewrite_use_compare).
2. Definitions and algorithms¶
Loops are in loop-simplify form with preheader \(P\) and latch \(\ell\); SSA form; induction variables and chains of recurrences are those of Lessons 18.2–18.3.
Definition 18.4.1 (Reducible multiplication)
An instruction \(x = i \times c\) (or \(c \times i\), or \(i \ll k\) with constant \(k\), read as \(i \times 2^k\)) inside loop \(L\) is reducible if \(i\) is a linear induction variable of \(L\), \(i = \{a, +, b\}\), and \(c\) is loop-invariant and available in \(P\). Its reduction is a new induction variable \(r = \{c\,a, +, c\,b\}\): r = phi [c*a, P], [r + c*b, ℓ].
Allen–Cocke–Kennedy strength reduction¶
Algorithm 18.4.2 (Allen–Cocke–Kennedy strength reduction)
- Input: a loop \(L\) with its basic and derived induction variables (Algorithm 18.2.2): each derived \(j\) with triple \((i, c_j, d_j)\), i.e. \(j = \{S_j, +, T_j\}\).
- Output: \(L\) where every derived induction variable computed with a multiplication is replaced by a temporary updated by additions.
- Precondition: \(L\) has a preheader and a single latch; \(S_j\), \(T_j\) are affine in values available in \(P\).
- Postcondition: every in-loop use of a reduced \(j\) reads a value equal to \(j\) (Theorem 18.4.12); the multiplications and additions that computed only \(j\) are dead and removed.
- Invariant: each new temporary \(r_j\) satisfies \(r_j(n) = S_j + n\,T_j\) at every point of iteration \(n\) after the header (it is updated only at the end of the latch).
function ACKReduce(L):
IVs ← ClassicIVs(L) # Algorithm 18.2.2
for j in derived IVs of IVs, latest definition first:
f ← family(j) # its basic IV
if T_j = ± Step(f): continue # no multiplication involved
if j has no use inside L: continue
in P: s0 ← expand(S_j); st ← expand(T_j)
in h: r_j ← phi [s0, P], [r_next, ℓ]
in ℓ: r_next ← r_j + st # classically: after each increment of f
replace every use of j inside L by r_j
delete j and every instruction that became dead
Processing the latest definition first means that for t = 4*i; u = t + 3 the temporary is created for u (triple \((i, 4, 3)\)) and t dies with it — the classic "one temporary per \((c, d)\) pair".
GCC's ivopts reduces i * w and replaces the exit test
Reproduce (gcc 14.2.0):
cat > sr.c <<'X'
long weighted(const long *a, long n, long w) {
long s = 0;
for (long i = 0; i < n; i++)
s += a[i] * (i * w);
return s;
}
X
gcc-14 -O2 -fno-tree-vectorize -fdump-tree-ivopts -c sr.c -o /dev/null
sed -n '/^ <bb 3>/,/^ <bb 5>/p' sr.c.*.ivopts
Output (complete):
<bb 3> [local count: 955630224]:
# s_17 = PHI <s_13(6), 0(5)>
# ivtmp.8_21 = PHI <ivtmp.8_20(6), ivtmp.8_16(5)>
# ivtmp.9_15 = PHI <ivtmp.9_8(6), 0(5)>
_23 = (void *) ivtmp.8_21;
_4 = MEM[(const long int *)_23];
_5 = (long int) ivtmp.9_15;
_6 = _4 * _5;
s_13 = _6 + s_17;
ivtmp.8_20 = ivtmp.8_21 + 8;
ivtmp.9_8 = ivtmp.9_15 + _7;
if (ivtmp.8_20 != _27)
goto <bb 6>; [89.00%]
else
goto <bb 8>; [11.00%]
<bb 8> [local count: 105119324]:
# s_22 = PHI <s_13(3)>
goto <bb 4>; [100.00%]
<bb 6> [local count: 850510900]:
goto <bb 3>; [100.00%]
<bb 7> [local count: 12992276]:
<bb 4> [local count: 118111600]:
# s_18 = PHI <s_22(8), 0(7)>
return s_18;
}
What to notice: the product i * w is gone: ivtmp.9 starts at 0 and grows by _7 (which is w, computed before the loop) — Algorithm 18.4.2's temporary for the derived variable \((i, w, 0)\). The address a + 8i became the pointer induction variable ivtmp.8 (+8 per iteration), and the exit test i < n was rewritten as ivtmp.8 != _27 (an end pointer computed before the loop): LFTR, after which i itself no longer exists. The remaining multiplication _4 * _5 multiplies two loop-varying values and is not reducible.
Operator strength reduction¶
Definition 18.4.3 (Region constant)
For a loop \(L\) with header \(h\), a value is a region constant (RC) if it is a constant or it is defined in a block that strictly dominates \(h\) (so it is available in \(P\) and never changes during an entry into \(L\)).
Definition 18.4.4 (OSR induction variable)
An SCC of the SSA graph of \(L\) (Definition 18.2.4) is an induction variable in the sense of OSR if all its members are phis, copies, additions or subtractions, every operand of a member is a member or a region constant, and a subtraction's member operand is its left one (y - rc; with rc - y the values alternate instead of stepping, and shifting \(y\) by \(\mathit{rc}'\) would shift the difference by \(-\mathit{rc}'\)). All members get the same header \(h\).
Definition 18.4.5 (Candidate operation)
An instruction \(x = \mathit{op}(y, z)\) is a candidate for OSR if \(\mathit{op} \in \{\times, +, -\}\) and one operand is an induction variable with header \(h\) and the other a region constant for \(h\) (for \(-\), the induction variable must be the left operand, or the result is negated).
Algorithm 18.4.6 (Operator strength reduction — Cooper, Simpson, Vick)
- Input: a function in SSA form, its dominator tree and loop headers.
- Output: the same function where every candidate operation is replaced by a copy of a new induction variable.
- Precondition: SSA form; loops with a preheader (for placing the initial values).
- Postcondition: every rewritten use reads the value the candidate had (Theorem 18.4.7); each distinct reduction \((\mathit{op}, \mathit{iv}, \mathit{rc})\) is created once.
- Invariant: the hash table maps \((\mathit{op}, a, b)\) to a value equal to \(a \mathbin{\mathit{op}} b\) wherever \(a\) and \(b\) are defined; SCCs are processed operands-first (Lemma 18.2.7), so an operand's induction-variable status is known when its user's SCC is processed.
function OSR(G): # Tarjan's SCC algorithm on the SSA graph (use → operand)
for each unvisited node n: DFS(n)
function DFS(n): … Tarjan's bookkeeping (Lesson 18.2 §3) …; on completing an SCC S: Process(S)
function Process(S):
if S = {n} and n is a candidate op(iv, rc): Replace(n, iv, rc)
else if S = {n}: header(n) ← none
else: ClassifyIV(S)
function ClassifyIV(S):
h ← the loop header of the header phis in S
if every member is a phi/copy/add/sub and every operand is in S or IsRC(operand, h):
for n in S: header(n) ← h
else:
for n in S: header(n) ← none; then Process each member n as a singleton
function Replace(n, iv, rc):
r ← Reduce(op(n), iv, rc)
replace n by a copy of r; header(n) ← header(iv)
function Reduce(op, iv, rc): # the reduced IV equal to iv op rc
if (op, iv, rc) in Hash: return Hash[(op, iv, rc)]
r ← a clone of iv's definition with a fresh name; Hash[(op, iv, rc)] ← r; header(r) ← header(iv)
for each operand o of r:
if header(o) = header(iv): o ← Reduce(op, o, rc) # follow the IV's cycle
else if op = × or r is a phi: o ← Apply(op, o, rc) # initial value / step
return r
function Apply(op, a, b): # a op b, created once, where both are available
if (op, a, b) in Hash: return Hash[(op, a, b)]
if a is an IV and b is an RC of its header: t ← Reduce(op, a, b)
else if b is an IV and a is an RC: t ← Reduce(op, b, a)
else: t ← new instruction a op b at the end of the block that is dominated by
the definitions of both a and b (for RCs: the preheader)
Hash[(op, a, b)] ← t; return t
For i = phi(0, i1), i1 = i + 1, t = i * 4: Reduce(×, i, 4) clones the phi as r = phi(·, ·); its preheader operand 0 is not in the cycle, so it becomes Apply(×, 0, 4) = 0; its latch operand i1 is, so it becomes Reduce(×, i1, 4), a clone of i1 = i + 1, i.e. r1 = r + 1' whose operand i → Reduce(×, i, 4) = r (hash hit) and whose constant 1 becomes Apply(×, 1, 4) = 4 only because the operation is \(\times\). Result: r = phi(0, r1), r1 = r + 4 — the reduced IV \(\{0,+,4\}\).
Theorem 18.4.7 (Correctness of OSR)
After Algorithm 18.4.6, every value created by Reduce(op, iv, rc) equals \(\mathit{iv} \mathbin{\mathit{op}} \mathit{rc}\) at every point where \(\mathit{iv}\) is defined in the loop, and every replaced candidate's uses read an equal value. The algorithm creates at most one reduced value per distinct triple.
Proof
Uniqueness is the hash table. Values, by induction on the recursion of Reduce (well founded: each call either hits the table or clones one member of \(\mathit{iv}\)'s SCC, and the table is filled before recursing, which breaks the cycle). Let \(\mathit{iv}\)'s definition be \(\mathit{iv} = g(o_1, \dots, o_m)\) with \(g\) a phi, copy, \(+\) or \(-\) (Definition 18.4.4). The clone computes \(g(o_1', \dots, o_m')\) where an operand in the same SCC is replaced by its reduction and a region-constant operand \(o\) by \(o \mathbin{\mathit{op}} \mathit{rc}\) when \(\mathit{op} = \times\) or \(g\) is a phi, and kept otherwise. We need \(g(o_1', \dots) = g(o_1, \dots) \mathbin{\mathit{op}} \mathit{rc}\):
- \(\mathit{op} = \times\): multiplication distributes over \(+\), \(-\) and commutes with selecting a phi operand, so every operand is multiplied by \(\mathit{rc}\) — exactly what the rule does, and correct modulo \(2^w\) (a ring).
- \(\mathit{op} = +\) (or \(-\)): for a phi, each incoming value is shifted by \(\mathit{rc}\) (the rule: RC operands via Apply, SCC operands via Reduce); for an addition \(y + z\) or a subtraction \(y - z\) with \(y\) in the SCC and \(z\) a region constant, \((y + \mathit{rc}) \pm z = (y \pm z) + \mathit{rc}\): only the SCC operand is shifted — the rule keeps \(z\) (this is where Definition 18.4.4 needs the member on the left of a subtraction).
By the induction hypothesis the reduced SCC operands equal \(o \mathbin{\mathit{op}} \mathit{rc}\) at the corresponding points, so the clone equals \(\mathit{iv} \mathbin{\mathit{op}} \mathit{rc}\). The new instructions from Apply are placed where both operands are available (for region constants, the preheader), so SSA dominance holds. Finally Replace makes the candidate a copy of that value.
GCC's straight-line strength reduction: the same idea without a loop
Reproduce (gcc 14.2.0):
cat > slsr.c <<'X'
long f(long *a, long i, long s) {
return a[i * s] + a[(i + 1) * s] + a[(i + 2) * s];
}
X
gcc-14 -O2 -fdump-tree-slsr -c slsr.c -o /dev/null
sed -n "/<bb 2>/,/return/p" slsr.c.*.slsr
Output (complete):
<bb 2> [local count: 1073741824]:
_1 = i_19(D) * s_20(D);
_2 = (long unsigned int) _1;
_3 = _2 * 8;
_4 = a_21(D) + _3;
_5 = *_4;
_6 = i_19(D) + 1;
_7 = _1 + s_20(D);
_8 = (long unsigned int) _7;
_9 = _8 * 8;
_10 = a_21(D) + _9;
_11 = *_10;
_12 = _5 + _11;
_13 = i_19(D) + 2;
_14 = _7 + s_20(D);
_15 = (long unsigned int) _14;
_16 = _15 * 8;
_17 = a_21(D) + _16;
_18 = *_17;
_23 = _12 + _18;
return _23;
What to notice: no production compiler ships OSR as published (LLVM uses LSR, GCC ivopts), but GCC's slsr pass applies OSR's key rewrite — \((y + c) \times s = y \times s + c \times s\), found through a table of candidate chains over the dominator tree — to straight-line code: (i + 1) * s became _7 = _1 + s and (i + 2) * s became _14 = _7 + s. In a loop, the same rule applied around the IV's cycle is exactly Reduce (Theorem 18.4.7's \(\mathit{op} = \times\) case).
LLVM Loop Strength Reduce¶
Definition 18.4.8 (LSR uses, formulae, cost)
An IV use is an instruction operand whose SCEV is an add recurrence of \(L\), classified as an address use (the pointer operand of a load/store), a compare use (the exit test), or a basic use. A formula for a use is a way to compute its SCEV \(S\) as
where the registers are SCEV expressions (invariant values or add recurrences, each of which will become one register) and the rest must fit the target's addressing mode for that use. The cost of a solution (one formula per use) is lexicographic: first the number of distinct registers (shared registers count once), then the cost of the add recurrences they need, the number of multiplications of IVs, base additions, immediate and setup costs, scale costs, and instructions — the fields NumRegs, AddRecCost, NumIVMuls, NumBaseAdds, ImmCost, SetupCost, ScaleCost, Insns of LSR's Cost class, compared by the target's isLSRCostLess.
Algorithm 18.4.9 (LLVM Loop Strength Reduce, simplified)
- Input: a loop in loop-simplify form, SCEV, the target's addressing modes and costs (
TargetTransformInfo). - Output: the loop rewritten so that each IV use computes its value with the chosen formula.
- Precondition: every IV use has an add-recurrence SCEV; the target cost hooks are available.
- Postcondition: each use computes the same value (SCEV expansion is value-preserving); the chosen solution has the least cost among the formulae that survived pruning (not a global optimum: the search space is pruned heuristically).
- Invariant: every formula in a use's list is a legal addressing mode for that use and denotes the use's SCEV.
function LSR(L):
uses ← CollectFixupsAndInitialFormulae(L) # one initial formula per use: reg(S)
for u in uses: generate alternative formulae: # GenerateAllReuseFormulae
split S into BaseRegs + Scale·ScaledReg + BaseOffset in every legal way;
reuse registers that other uses already have (e.g. share {0,+,1})
NarrowSearchSpaceUsingHeuristics(uses) # drop dominated / expensive formulae
best ← none
SolveRecurse(0, {}, cost 0, registers {}): # depth-first over uses
for each formula F of uses[k], cheaper registers first:
c ← cost after adding F (registers shared with the partial solution are free)
if c < cost(best): recurse on uses[k+1]
ImplementSolution(best): # SCEV expander creates the IVs,
# rewrites uses, deletes dead code
LLVM's LSR turns the address arithmetic into a pointer induction variable
Reproduce (clang 23.1.2, opt 23.1.2; default target x86-64):
cat > lsr.c <<'X'
long f(long *a, long n) {
long s = 0;
for (long i = 0; i < n; i++)
s += a[4 * i + 3] * i;
return s;
}
X
clang-23 -O1 -fno-discard-value-names -fno-unroll-loops -fno-vectorize -S -emit-llvm lsr.c -o lsr.ll
sed -n '/^for.body:/,/^}/p' lsr.ll
opt -passes=loop-reduce -S lsr.ll -o - | sed -n '/^for.body:/,/^}/p'
Output (complete):
for.body: ; preds = %entry, %for.body
%i.09 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
%s.08 = phi i64 [ %add2, %for.body ], [ 0, %entry ]
%.idx = shl nsw i64 %i.09, 5
%0 = getelementptr inbounds nuw i8, ptr %a, i64 %.idx
%arrayidx = getelementptr inbounds nuw i8, ptr %0, i64 24
%1 = load i64, ptr %arrayidx, align 8, !tbaa !9
%mul1 = mul nsw i64 %1, %i.09
%add2 = add nsw i64 %mul1, %s.08
%inc = add nuw nsw i64 %i.09, 1
%exitcond.not = icmp eq i64 %inc, %n
br i1 %exitcond.not, label %for.cond.cleanup, label %for.body, !llvm.loop !11
}
for.body: ; preds = %for.body.preheader, %for.body
%lsr.iv = phi ptr [ %scevgep, %for.body.preheader ], [ %scevgep1, %for.body ]
%i.09 = phi i64 [ %inc, %for.body ], [ 0, %for.body.preheader ]
%s.08 = phi i64 [ %add2, %for.body ], [ 0, %for.body.preheader ]
%0 = load i64, ptr %lsr.iv, align 8, !tbaa !9
%mul1 = mul nsw i64 %0, %i.09
%add2 = add nsw i64 %mul1, %s.08
%inc = add nuw nsw i64 %i.09, 1
%scevgep1 = getelementptr i8, ptr %lsr.iv, i64 32
%exitcond.not = icmp eq i64 %n, %inc
br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body, !llvm.loop !11
}
What to notice: the address use has SCEV \(\{24 + a, +, 32\}\). Its formulae include \(a + 32 \cdot \{0,+,1\} + 24\) (not legal on x86-64: the scale 32 is not in \(\{1, 2, 4, 8\}\)), and the single register \(\{24 + a,+,32\}\). LSR chose the latter (%lsr.iv, set up in the preheader as %scevgep = a + 24 and advanced by 32): one extra register, and the shl and both GEPs disappear. i stays because the multiplication %1 * i (two varying values, not reducible) and the exit compare use it.
Linear-function test replacement¶
Definition 18.4.10 (LFTR)
Let the exit test of \(L\) be \(i \mathrel{R} B\) on an induction variable \(i = \{a, +, s\}\) with invariant \(B\), and let \(r = \{a', +, s'\}\) be another induction variable of \(L\) with \(s' \ne 0\). Linear-function test replacement replaces the test by an equivalent test on \(r\): with the exact backedge-taken count \(\mathrm{BTC}\) of \(L\) (Definition 18.3.9), by \(r_{\text{latch}} \ne r(\mathrm{BTC})\) evaluated at the test's position — the limit \(a' + s' \cdot \mathrm{BTC}\) (plus \(s'\) if the test uses the incremented value) computed in the preheader.
Algorithm 18.4.11 (LFTR, as in LLVM's indvars)
- Input: a loop \(L\) with a computable exact backedge-taken count \(\mathrm{BTC}\) (Lesson 18.3), its exiting compare, and a candidate counter \(r\).
- Output: the exit compare rewritten as
icmp ne r.next, Limit(oreq, with the branch successors kept). - Precondition: \(r\) is an add recurrence of \(L\) whose values in iterations \(0 \dots \mathrm{BTC}\) are distinct (it does not wrap back to a value it had:
nwornuw/nswover that range); \(\mathrm{BTC}\) is exact (not a maximum). - Postcondition: the new test is false exactly in the iterations in which the old one was (Theorem 18.4.13).
- Invariant: —
function LFTR(L):
BTC ← exact backedge-taken count of L (else give up)
r ← FindLoopCounter(L): prefer an IV with unit step, no wrap, used elsewhere anyway
Limit ← expand(r.start + r.step · (BTC + 1)) in the preheader # value of r.next at exit
replace the exiting compare by "r.next != Limit"
delete instructions that became dead (typically the old counter)
indvars widens the counter and replaces the exit test
Reproduce (clang 23.1.2, opt 23.1.2):
cat > lftr.c <<'X'
void clear(int *a, int n) {
for (int i = 0; i < n; i++)
a[i] = 0;
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm lftr.c -o - |
opt -passes='mem2reg,loop-rotate' -S -o rot.ll
sed -n '/^for.body:/,/^for.cond.for.end_crit_edge:/p' rot.ll
echo '--- after indvars ---'
opt -passes=indvars -S rot.ll -o - | sed -n '/^for.body.lr.ph:/,/^for.cond.for.end_crit_edge:/p'
Output (complete):
for.body: ; preds = %for.body.lr.ph, %for.inc
%i.02 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
%idxprom = sext i32 %i.02 to i64
%arrayidx = getelementptr inbounds i32, ptr %a, i64 %idxprom
store i32 0, ptr %arrayidx, align 4
br label %for.inc
for.inc: ; preds = %for.body
%inc = add nsw i32 %i.02, 1
%cmp = icmp slt i32 %inc, %n
br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge, !llvm.loop !5
for.cond.for.end_crit_edge: ; preds = %for.inc
--- after indvars ---
for.body.lr.ph: ; preds = %entry
%wide.trip.count = zext i32 %n to i64
br label %for.body
for.body: ; preds = %for.inc, %for.body.lr.ph
%indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body.lr.ph ]
%arrayidx = getelementptr inbounds i32, ptr %a, i64 %indvars.iv
store i32 0, ptr %arrayidx, align 4
br label %for.inc
for.inc: ; preds = %for.body
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count
br i1 %exitcond, label %for.body, label %for.cond.for.end_crit_edge, !llvm.loop !5
for.cond.for.end_crit_edge: ; preds = %for.inc
What to notice: indvars first widened the 32-bit counter to 64 bits (the sext in the loop is gone — legal because nsw guarantees \(i\) never wraps), then replaced icmp slt i32 %inc, %n by icmp ne i64 %indvars.iv.next, %wide.trip.count: the limit is the trip count \(n\) (the loop is guarded by \(0 < n\)), computed once in the preheader (Algorithm 18.4.11). The signed < became ≠, which is legal only because \(\mathrm{BTC}\) is exact (Theorem 18.4.13).
3. Worked example¶
The running example is the stride loop of the lab corpus (labs/ch18-loops/corpus/sr.c), as SSA:
loop:
%i = phi i64 [ 0, %entry ], [ %i1, %loop ]
%s = phi i64 [ 0, %entry ], [ %s1, %loop ]
%t = mul i64 %i, 4
%u = add i64 %t, 3
%p = getelementptr inbounds i64, ptr %a, i64 %u
%v = load i64, ptr %p
%s1 = add i64 %s, %v
%i1 = add i64 %i, 1
%c = icmp slt i64 %i1, %n
br i1 %c, label %loop, label %exit
Allen–Cocke–Kennedy strength reduction on the running example¶
Classic detection (Algorithm 18.2.2): basic i (0, 1); derived t \(= (i, 4, 0)\), u \(= (i, 4, 3)\), i1 \(= (i, 1, 1)\). Algorithm 18.4.2, latest definition first:
| step | derived IV | triple | step ≠ ±1? | uses in L? | action |
|---|---|---|---|---|---|
| 1 | i1 |
\((i, 1, 1)\) | no (step 1) | yes | skip |
| 2 | u |
\((i, 4, 3)\) | yes (4) | %p |
u.sr = phi [3, entry], [u.sr + 4, loop]; %p uses u.sr; delete u, then t (now dead) |
| 3 | t |
\((i, 4, 0)\) | — | deleted in step 2 | skip |
Result (from ch18-loops sr, the lab's reference solution):
loop:
%i = phi i64 [ 0, %entry ], [ %i1, %loop ]
%s = phi i64 [ 0, %entry ], [ %s1, %loop ]
%u.sr = phi i64 [ 3, %entry ], [ %u.sr.next, %loop ]
%p = getelementptr inbounds i64, ptr %a, i64 %u.sr
%v = load i64, ptr %p, align 4
%s1 = add i64 %s, %v
%i1 = add i64 %i, 1
%c = icmp slt i64 %i1, %n
%u.sr.next = add i64 %u.sr, 4
br i1 %c, label %loop, label %exit
Operator strength reduction on the running example¶
Tarjan's walk completes SCCs in the order {i, i1} (an OSR induction variable, header loop), {t}, {u}, … . Processing:
| step | SCC | classification | action | hash table after |
|---|---|---|---|---|
| 1 | {i, i1} | phi + add of RC 1: IV, header loop |
— | — |
| 2 | {t} = i * 4 |
candidate (×, IV i, RC 4) |
Replace → Reduce(×, i, 4): clone i as r |
(×, i, 4) ↦ r |
| 2a | r's operand 0 (entry) is not in the SCC, \(\times\): Apply(×, 0, 4) |
constant 0 | (×, 0, 4) ↦ 0 | |
| 2b | r's operand i1 is in the SCC: Reduce(×, i1, 4): clone i1 = i + 1 as r1 |
(×, i1, 4) ↦ r1 | ||
| 2c | r1's operand i → Reduce(×, i, 4) = r (hit); operand 1, op = ×: Apply(×, 1, 4) |
constant 4 | (×, 1, 4) ↦ 4 | |
| 2d | t becomes a copy of r; header(t) ← loop |
r = phi [0], [r1], r1 = r + 4 |
||
| 3 | {u} = t + 3 |
candidate (+, IV t, RC 3) |
CSV reduce it too: Reduce(+, t, 3) → r' = phi [3], [r' + 4] |
(+, t, 3) ↦ r' |
pebble-osr implements the multiplicative case only (Definition 18.4.1), so it stops after step 2 and leaves %u = add %t.osr, 3; full OSR (step 3) reaches the same single IV as ACK after dead-code elimination removes r:
loop:
%i = phi i64 [ 0, %entry ], [ %i1, %loop ]
%s = phi i64 [ 0, %entry ], [ %s1, %loop ]
%t.osr = phi i64 [ 0, %entry ], [ %t.osr.next, %loop ]
%u = add i64 %t.osr, 3
%p = getelementptr inbounds i64, ptr %a, i64 %u
...
%t.osr.next = add i64 %t.osr, 4
The lab measures the difference on the whole corpus (static counts after dce; reproduce with ch18-loops sr and opt -passes='pebble-licm,pebble-osr' then ch18-loops count):
| function | original: loop insts / muls / header phis | classic SR | pebble-osr |
pebble-licm,pebble-osr |
|---|---|---|---|---|
stride |
12 / 1 / 2 | 12 / 0 / 3 | 13 / 0 / 3 | 13 / 0 / 3 |
matrix (a[i*m + j]) |
20 / 1 / 4 | 20 / 1 / 4 | 20 / 1 / 4 | 21 / 0 / 5 |
weighted |
16 / 4 / 2 | 17 / 1 / 4 | 19 / 1 / 5 | 19 / 1 / 5 |
twice |
12 / 2 / 2 | 13 / 0 / 4 | 14 / 0 / 4 | 14 / 0 / 4 |
matrix shows why pass order matters: i*m sits in the inner loop, where it is invariant but not an induction variable, so neither strength reduction touches it; LICM first moves it to the inner preheader — into the outer loop, where it is the reducible \(i \times m\) — and then OSR removes it.
LLVM Loop Strength Reduce on the running example¶
For lsr.c above, the uses and some of their formulae (costs illustrative, not LLVM's exact weights; the choice matches the real-world box):
| use | SCEV | formulae (legal on x86-64?) |
|---|---|---|
address of a[4i+3] |
\(\{24 + a,+,32\}\) | reg(\(\{24+a,+,32\}\)) ✓; reg(\(a\)) + 32·reg(\(\{0,+,1\}\)) + 24 ✗ (scale 32); reg(\(\{a,+,32\}\)) + 24 ✓ |
mul %1, %i |
\(\{0,+,1\}\) | reg(\(\{0,+,1\}\)) ✓ |
| exit compare | \(\{1,+,1\}\) vs \(n\) | reg(\(\{0,+,1\}\)) + 1 ✓; reg(\(\{24+a,+,32\}\)) vs \(24 + a + 32n\) ✓ |
Registers are counted once per solution: \(\{0,+,1\}\) is needed by the multiplication anyway, so the compare reuses it for free; the address needs one more register either way. LSR's SolveRecurse picks reg(\(\{24+a,+,32\}\)) with offset 0 (no immediate add in the loop): 2 induction registers in total.
Linear-function test replacement on the running example¶
After ACK SR the loop still tests i1 < n and i is used only by i1 and the test. LFTR with \(r\) = u.sr = \(\{3,+,4\}\) and the exact BTC \(= \max(n, 1) - 1\) (the loop is bottom-tested and entered once): Limit \(= 3 + 4 \cdot (\mathrm{BTC} + 1)\), test u.sr.next != Limit. Now i, i1 and c are dead: one induction variable remains. Precondition check: u.sr must not wrap over the loop's iterations; for 64-bit i < n that holds when \(4n + 3\) does not overflow — which the nsw flags of the original code give (Theorem 18.4.13).
Try it
Build the lab (./course test 18) and run build/<preset>/bin/ch18-loops count on labs/ch18-loops/corpus/sr.ll before and after both reductions, as in the table above.
4. Invariants and correctness¶
Allen–Cocke–Kennedy strength reduction¶
Theorem 18.4.12 (Correctness of Algorithm 18.4.2)
For every reduced derived induction variable \(j = \{S_j, +, T_j\}\), the temporary \(r_j\) equals \(j\) at every in-loop use of \(j\), so replacing those uses preserves the function's behavior.
Proof
\(r_j\) is a header phi with preheader value \(S_j\) and latch value \(r_j + T_j\), so \(r_j(n) = S_j + n T_j\) during all of iteration \(n\) (its update is the last instruction of the latch, and the phi changes only on entry to the next iteration). By Theorem 18.2.9, \(j(n) = S_j + n T_j\) as well. An in-loop use of \(j\) in iteration \(n\) reads \(j(n)\) — for a phi use through the latch, the value at the end of iteration \(n\), which is still \(r_j(n)\) since the update of \(r_j\) feeds only the header phi. Uses outside the loop are not rewritten. The deleted instructions have no uses left, and are pure.
Operator strength reduction¶
Theorem 18.4.7 in §2 is the correctness argument; the replaced candidate is a copy of a value equal to it at every point, and SSA dominance is preserved because Reduce puts its phi clones in the IV's header and Apply places initial values and steps where their operands are available.
LLVM Loop Strength Reduce¶
LSR's correctness reduces to two facts: every formula denotes its use's SCEV (by construction: formulae are generated by splitting the SCEV into summands), and SCEV expansion emits code that computes that SCEV. The choice is heuristic — the search space is exponential and LSR prunes it (§5) — so LSR is correct but not optimal. Its known risks are about wrap: an expanded recurrence must not introduce poison, which is why LSR's new instructions carry no nsw/nuw flags (compare the flagless getelementptr i8 in the box above with the original inbounds nuw).
Linear-function test replacement¶
Theorem 18.4.13 (Correctness of LFTR)
Let the loop exit exactly after \(\mathrm{BTC}\) back edges (exact count), and let \(r = \{a', +, s'\}\) with \(s' \ne 0\) take pairwise distinct values in iterations \(0, \dots, \mathrm{BTC}\) (no self-wrap). Then the test r.next != Limit with \(\mathrm{Limit} = a' + s'(\mathrm{BTC} + 1)\), placed where the original exit test was, is true in iterations \(0, \dots, \mathrm{BTC} - 1\) and false in iteration \(\mathrm{BTC}\), exactly like the original test.
Proof
In iteration \(k\) the incremented value is \(r(k) + s' = a' + s'(k + 1)\). For \(k = \mathrm{BTC}\) it equals \(\mathrm{Limit}\), so the new test is false and the loop exits — as the original does, by definition of the exact \(\mathrm{BTC}\). For \(k < \mathrm{BTC}\), \(a' + s'(k+1)\) and \(a' + s'(\mathrm{BTC}+1)\) are the values of \(r\) in iterations \(k + 1 \le \mathrm{BTC}\) and \(\mathrm{BTC} + 1\); they differ because \(r\) does not revisit a value within these iterations (the no-wrap hypothesis extended by one step, which LLVM checks by requiring the recurrence not to wrap up to the exit value), so the new test is true and the loop continues — as the original does. When it breaks: without the no-wrap hypothesis, e.g. u8 r = {0,+,64}, the values repeat every 4 iterations, and r.next != Limit exits too early; with only a maximum (not exact) BTC, the loop may need to exit earlier than the limit.
5. Complexity¶
\(N\) = instructions in the loop, \(U\) = IV uses, \(F\) = formulae per use after pruning.
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| Allen–Cocke–Kennedy strength reduction | \(O(N^2)\) (the classic IV fixed point) + \(O(N)\) rewriting | \(O(N)\) | one new IV per reduced derived IV | \(N\) |
| Operator strength reduction | \(O(N + E)\) plus the new instructions | linear | at most one new value per distinct (op, iv, rc) | \(E\) SSA edges |
| LLVM Loop Strength Reduce | \(O(F^U)\) search without pruning | pruned to a small constant per use | \(O(U F)\) formulae | \(U\), \(F\) |
| Linear-function test replacement | \(O(1)\) per loop after SCEV | constant | \(O(1)\) | — |
Proposition 18.4.14 (OSR creates linearly many values; LSR's unpruned search is exponential)
OSR creates at most \(|\mathrm{IVs}| \times |\mathrm{RCs}| \times 3\) reduced values (one per member of each reduced SCC), and runs in time linear in the size of the SSA graph plus the number of values created. LSR's SolveRecurse explores up to \(\prod_{u} F_u\) partial solutions without pruning.
Proof
Every Reduce call either hits the hash table or clones one member of an IV's SCC for one (op, rc) pair; every Apply call either hits the table or creates one instruction. Tarjan's walk is linear [Tar72]. For LSR, the recursion chooses one formula for each use in turn, so the number of leaves is the product of the choice counts; NarrowSearchSpaceUsingHeuristics and the bound on the current best cost cut it down.
Pathological input. A loop with \(U\) address uses of different strides into the same array gives LSR \(F \ge 3\) formulae each and \(3^U\) solutions; LSR bounds the search with lsr-complexity-limit (hidden option) and falls back to greedy narrowing. For classic SR, the reverse-order chain of Lesson 18.2 §5 makes the IV fixed point quadratic.
At scale. OSR's linear time was the point of [CSV01]; the paper reports it running in a fraction of the time of the whole optimizer. LSR's pruning keeps it cheap in practice on LLVM's test suite; its complexity limits exist for machine-generated code.
6. Variants and refinements¶
Allen–Cocke–Kennedy strength reduction¶
- Reduction of address arithmetic only (many early compilers): reduce only derived IVs used in subscripts — trade-off: misses scalar multiplications, simpler.
- With induction-variable elimination [Muchnick, §14.1.4]: after SR and LFTR, delete basic IVs used only by their own increments and the test — trade-off: needs liveness; saves a register.
Operator strength reduction¶
- Reducing additions too (CSV's full algorithm): candidates \(\mathit{iv} \pm \mathit{rc}\) create new IVs as well, so chains like
4*i + 3become one IV — trade-off: more phis unless followed by dead-code elimination (§3). - SSA-based straight-line strength reduction (GCC
slsr): the same rewrite over the dominator tree without loops — trade-off: no induction variables needed, only local chains.
LLVM Loop Strength Reduce¶
- IV chains (
LSRInstance::CollectChains): reuse the previous iteration's address plus an increment for related addresses — trade-off: fewer registers, longer dependence chains. - Target-specific term folding (
-lsr-term-fold, off by default): LSR itself replaces the exit test with one on a pointer IV — trade-off: overlaps with indvars' LFTR.
Linear-function test replacement¶
- Pointer LFTR (GCC
ivopts, the real-world box of §2): compare an address IV against an end pointer — trade-off: frees the integer counter, requires a pointer limit computation before the loop. - Equality form (
!=instead of<): lets the backend use a flag-setting decrement — trade-off: correct only with an exact trip count (Theorem 18.4.13).
7. In real compilers¶
Allen–Cocke–Kennedy strength reduction¶
GCC
gcc/tree-ssa-loop-ivopts.cc — find_induction_variables (bivs and givs), find_iv_candidates (the new variables it may create, including \(c\cdot i + d\) temporaries and pointer IVs), tree_ssa_iv_optimize_loop (choose a set, rewrite uses) (GCC 15) [GCC-IVOPTS]. GCC's choice is cost-driven like LSR, but its vocabulary and effect (one temporary per reduced \(c \cdot i + d\)) are ACK's.
- LLVM has no ACK pass;
loop-reducesubsumes it.
The real-world box for this technique is in §2 (GCC reduces i * w).
Operator strength reduction¶
Research and teaching compilers
OSR is the algorithm of Engineering a Compiler [EaC3, Ch. 10] and of Rice's Massively Scalar Compiler Project, where it was developed [CSV01]. No production compiler ships it as published; GCC's gcc/gimple-ssa-strength-reduction.cc (slsr) applies its algebra to straight-line code (GCC 15) [GCC-SLSR], and LLVM's LSR subsumes its effect in loops.
Find where GCC does it. Open gcc/gimple-ssa-strength-reduction.cc. Question: what kind of code does this pass reduce — loops or straight-line code? (Quiz osr-find-slsr.)
The real-world box for this technique is in §2 (GCC's slsr).
LLVM Loop Strength Reduce¶
LLVM
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp — struct Formula, class Cost (RateFormula, RateRegister), class LSRUse, LSRInstance::CollectFixupsAndInitialFormulae, GenerateAllReuseFormulae, NarrowSearchSpaceUsingHeuristics, SolveRecurse, ImplementSolution, OptimizeLoopTermCond [LLVM-LSR] (LLVM 23.1.2). It runs in the codegen-prepare part of the pipeline (llc/the backend's IR passes), where TargetTransformInfo knows the addressing modes.
- GCC
gcc/tree-ssa-loop-ivopts.cc— the same decision problem, solved by "IV set" search with a cost per (use, candidate) pair [GCC-IVOPTS].
Find where LLVM does it. In LoopStrengthReduce.cpp, find the recursive search that picks one formula per use. Question: its name? (Quiz lsr-find-solve.)
The real-world box for this technique is in §2.
Linear-function test replacement¶
LLVM
llvm/lib/Transforms/Scalar/IndVarSimplify.cpp — IndVarSimplify::linearFunctionTestReplace, with FindLoopCounter choosing the counter [LLVM-IndVars] (LLVM 23.1.2).
- GCC
gcc/tree-ssa-loop-ivopts.cc—may_eliminate_ivandrewrite_use_compare[GCC-IVOPTS].
The real-world box for this technique is in §2 (indvars), and GCC's pointer LFTR appears in the ACK box.
8. Comparison¶
| 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 |
On the lab corpus (§3 table): classic SR removes every reducible multiplication with one IV per derived variable (e.g. stride: 1 → 0 multiplications, +1 phi); pebble-osr removes the same multiplications but leaves the additions of c·i + d (stride: 13 instead of 12 loop instructions); with LICM first, OSR also reduces i*m in matrix, which classic SR misses.
Choose ACK when you have classic IV information and no SSA. Choose OSR in an SSA middle end without target knowledge (fast, simple, provably correct). Choose LSR close to code generation, when addressing modes and register pressure decide what is cheap. Always run LFTR after strength reduction when the trip count is exact, or the old counter survives.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch18.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Allen–Cocke–Kennedy strength reduction | ack-temp-init, ack-counts |
./course drill scev-form (the derived IVs' CRs are the temporaries' start and step) |
ack-sr |
Lab Part B (B1) |
| Operator strength reduction | osr-reduce-cr, osr-find-slsr |
./course drill scev-form (the reduced IV of \(c \cdot \{a,+,b\}\) is \(\{ca,+,cb\}\)) |
osr |
E3 |
| LLVM Loop Strength Reduce | lsr-scale-illegal, lsr-find-solve |
none: LSR's decision depends on a target cost model that a drill cannot reproduce faithfully; the formulae table of §3 is the exercise | lsr |
— |
| Linear-function test replacement | lftr-limit, lftr-wrap |
./course drill trip-count (the limit is computed from the exact trip count) |
lftr |
— |
Pitfall
Strength reduction alone often makes a loop bigger: it adds a phi and an addition per reduced variable, and the original counter stays alive for the exit test. The win comes from the combination — SR, LFTR, then dead-code elimination of the old induction variable — and on modern targets from folding the new address IV into the addressing mode.
References¶
See the chapter references.