In computer programming, loop-invariant code consists of statements (in an imperative programming language) which can be moved outside the body of a loop without affecting the semantics of the program.
Loop-invariant code motion (also called hoisting or scalar promotion) is a compiler optimization which performs this movement automatically.
Loop-invariant code which has been hoisted out of a loop is executed less often, providing a speedup. Another effect of this transformation is allowing constants to be stored in registers and not having to calculate the address and access the memory (or cache line) at each iteration.
However, if too many variables are created, there will be high register pressure, especially on processors with few registers, like the 32-bit x86. If the compiler runs out of registers, some variables will be spilled. To counteract this, the “opposite” optimization can be performed, rematerialization.
Worked example
If we consider the following code sample, two optimization possibilities can be applied.
for (i = 0; i < n; i++) {
x = y + z;
a[i] = 6*i + x*x;
}
The calculations x = y + z and x*x can be moved outside the loop, resulting in something similar to:
x = y + z;
t1 = x*x;
for (i = 0; i < n; i++) {
a[i] = 6*i + t1;
}
This code can be optimized further. For example, strength reduction could remove the two multiplications inside the loop (6*i and a[i]), and induction variable elimination could then elide i completely.
See also
 | This computer-programming-related article is a stub. You can help Wikipedia by expanding it. |