In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, 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

Linear function

In mathematics, the term linear function can refer to either of two different but related concepts:* a first-degree polynomial function of one variable;* a map between two vector spaces that preserves vector addition and scalar multiplication....

 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;
}

Application to strength reduction

A common compiler optimization

Compiler optimization

Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...

 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 = -17;
for (i = 0; i < 10; ++i) {
j = j + 17;
}

This optimization is a special case of strength reduction

Strength reduction

Strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array...

.

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+1));
}
return sum;
}

Induction variable substitution

Induction variable substitution is a compiler transformation to recognize variables which can be expressed as functions of the indices of enclosing loops and replace them with induction variables with the expressions involving loop indices.

This transformation makes the relationship between the variables and loop indices explicit, which helps other compiler analysis, such as dependence analysis

Dependence analysis

In compiler theory, dependence analysis produces execution-order constraints between statements/instructions. Broadly speaking, a statement S2 depends on S1 if S1 must be executed before S2...

.

Example.

Input code:

int c, i;
c = 10;
for (i=0; i<10; i++)
{
c = c + 5; // c is incremented by 5 for each loop iteration
}

Output code

int c, i;
c = 10;
for (i=0; i<10; i++)
{
c = 10 + 5*i; // c is explicity expressed as a function of loop index
}

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+1;
}