10.2.2 Induction Variable Detection and Elimination
An induction variable is a variable whose value on each loop iteration is a linear function of the iteration index. When such variables and the expressions they compute are found, often the variable itself can be eliminated or a strength reduction can be performed.
EXAMPLE 10 Induction variable
J := 0
FOR I := 1 to N DO
...
J := J + 1
K := 2 * J
M := 3 * K
...
A[M] :=
ENDFOR
J, K and M are all induction variables. (The loop index, i, is trivally an induction variable.)
EXAMPLE 11 More induction variables
t := b * c
FOR i := 1 TO10000 DO
BEGIN
a := t
d := i * 3
...
...
d is an induction variable.
The most common induction variables are those which result from indexing elements of an array. Multiplications of the index are created when an array takes more than one byte or when the offset is computed for multidimensional array.
Induction Variables
We find induction variables incrementally. A basic induction variable is a variable X whose only assignments within the loop are of the form:
X := X + C
X := X - C
where C is a constant or a loop-invariant variable. In Example 10, I and J are basic induction variables.
We define an induction variable, recursively, to be a basic induction variable or one which is linear function of some induction variable. In Example 10, K is an induction variable since K is a linear function of J. M is an induction variable since M := 3 * K = 3 * (2 * J) = 6 * J. The expressions J + 1, 2 * J, and 3 * K are called induction expressions.
Finding Induction Variables
After reaching definitions find all definitions of Y and Z in X := Y op Z which reach the beginning of the loop, basic induction variables can be found by a simple scan of the loop. To find other induction variables, we find variables, W , such that
W := A * X + B
where A and B are constants or loop invariants, and X is an induction variable. These can be found by iterating through the loop until no more induction variables are found.
In Example 10, the variable J reaches the top of the loop. The statement J := J + 1 satisfies the definition of a basic induction variable. The other statements will be found on successive visits through the loop.