◄ WORLD V · SONNY 5DART 238 · a helldive at the net

THE INDUCTION VARIABLE i, i+c, i+2c... replace the pattern with its closed form

An induction variable changes by a fixed step each loop iteration: i = i + c. Once the compiler recognizes the pattern, it can do arithmetic on the recurrence itself — the k-th value is the closed form i₀ + k·c — and use it to strength-reduce a multiply into an add, eliminate the counter, or bound the loop. Induction-variable analysis is what lets a compiler turn a[i] address arithmetic (a multiply per iteration) into a running pointer (one add per iteration).

THE TECHNIQUE recurrence iₖ=iₖ₋₁+c ≡ closed form i₀+k·c

An induction variable starts at i₀ and steps by c. The demo runs the recurrence k times and checks it against the closed form i₀+k·c: live demo







  
HISTORY & CREDIT Allen 1969 · Allen-Cocke-Kennedy 1981

  
“A loop counter is just a counter.” — it is an arithmetic sequence, and its k-th term has a closed form. Seeing the counter as algebra, not as steps, is what lets the compiler replace a multiply with an add and delete the counter entirely. cited

  
1969 · Frances Allen — induction-variable recognition for program optimization.
1981 · Allen, Cocke & Kennedy — “Reduction of Operator Strength”: systematic strength reduction driven by induction variables, replacing multiplies with adds.
now · scalar-evolution analysis (LLVM's SCEV) is induction variables grown up — it reasons about whole recurrences.

  
The recurrence and the closed form are the same sequence seen two ways: step-by-step, or all at once. The optimizer keeps whichever is cheaper — usually the add, sometimes the formula. Allen-Cocke-Kennedy 1981






  
RECOMMEND FOR I-13 recurrence vs closed form, both computed

  
On the canonical compiler, the recurrence i₀=5, c=3 stepped k=7 times equals the closed form 5+7·3 = 26 — identical:

  
$ i13 run iv.i13   # recurrence vs closed form
byrec = 26          -- i stepped by c, seven times, via recursion
closed = 26          -- i0 + k*c, in one multiply

  
Recommend: induction variables are N/A for I-13 — there are no loops, so there is no counter to recognize. In i13 the “induction variable” is an explicit recursion argument: you already wrote i+1 as the next call's parameter, in the open. The classical pass exists to recover a structure the loop hid; i13 never hides it. Its recursion carries the sequence on the surface, where byrec and closed agreeing (26 = 26) is something you can simply read.