Induction variable
From Wikipedia, the free encyclopedia
In computer science, an induction variable is a variable that gets increased or decreased by a fixed amount on every iteration of a loop, or is a linear function of another induction variable.
For example, in the following loop, i and j are induction variables:
for (i=0; i < 10; ++i) {
j = 17 * i;
}
Contents |
[edit] Application to strength reduction
A common compiler optimization is to recognize the existence of induction variables and replace them with simpler computations; for example, the code above could be rewritten by the compiler as follows, on the assumption that the addition of a constant will be cheaper than a multiplication.
j = 0;
for (i=0; i < 10; ++i) {
j = j + 17;
}
This optimization is a special case of strength reduction.
[edit] Application to reduce register pressure
In some cases, it is possible to reverse this optimization in order to remove an induction variable from the code entirely. For example:
extern int sum;
int foo(int n) {
int i, j;
j = 5;
for (i=0; i < n; ++i) {
j += 2;
sum += j;
}
return sum;
}
This function's loop has two induction variables: i and j. Either one can be rewritten as a linear function of the other; therefore, the compiler may optimize this code as if it had been written
extern int sum;
int foo(int n) {
int i;
for (i=0; i < n; ++i) {
sum += (5 + 2*i);
}
return sum;
}
[edit] Non-linear induction variables
The same optimizations can be applied to induction variables that are not necessarily linear functions of the loop counter; for example, the loop
j = 1;
for (i=0; i < 10; ++i) {
j = j << 1;
}
may be converted to
for (i=0; i < 10; ++i) {
j = 1 << i;
}
