In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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
In mathematics, the term linear function refers to two distinct but related notions:
* In calculus and related areas, a linear function is a function (mathematics), function whose graph of a function, graph is a straight line, that is, a polynomia ...
of another induction variable.
For example, in the following loop,
i and
j are induction variables:
for (i = 0; i < 10; ++i)
Application to strength reduction
A common
compiler optimization
In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power con ...
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)
This optimization is a special case of
strength reduction
In compiler construction, 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 ...
.
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)
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)
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 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''. Broadly, there are two classes of depend ...
.
Example:
Input code:
int c, i;
c = 10;
for (i = 0; i < 10; i++)
Output code
int c, i;
c = 10;
for (i = 0; i < 10; i++)
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)
may be converted to
for (i = 0; i < 10; ++i)
See also
*
Mathematical induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
References
Further reading
*
*
*
*
{{DEFAULTSORT:Induction Variable
Compiler optimizations