Induction variable

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. ^[1]

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 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.

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:

externintsum;intfoo(intn){intj=5;for(inti=0;i<n;++i){j+=2;sum+=j;}returnsum;}

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

externintsum;intfoo(intn){for(inti=0;i<n;++i){sum+=5+2*(i+1);}returnsum;}

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 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.

Example:

Input code:

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

Output code

intc=10;for(inti=0;i<10;i++){c=10+5*(i+1);// c is explicitly 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);}

See also

• Mathematical induction

References

1. Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation . Morgan Kaufmann. ISBN   978-1-55860-320-2. induction variable.

Further reading

• Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986), Compilers: Principles, Techniques, and Tools (2nd ed.), ISBN   978-0-201-10088-4
• Allen, Francis E.; Cocke, John; Kennedy, Ken (1981), "Reduction of Operator Strength", in Munchnik, Steven S.; Jones, Neil D. (eds.), Program Flow Analysis: Theory and Applications, Prentice-Hall, ISBN   978-0-13-729681-1
• Cocke, John; Kennedy, Ken (November 1977), "An algorithm for reduction of operator strength", Communications of the ACM, 20 (11): 850–856, doi: 10.1145/359863.359888 , S2CID   1092505
• Cooper, Keith; Simpson, Taylor; Vick, Christopher (1995), Operator Strength Reduction (PDF), Rice University, retrieved April 22, 2010