Loop-invariant code motion

Loop-invariant code (also called hoisting or scalar promotion) in an imperative programming language consists of statements which could be moved to before the loop (if the loop always terminates), or after the loop, without affecting the semantics of the program. As a result it is executed less often, providing a speedup. Another effect of this transformation is allowing to store constant into registers and not having to calculate the address and access the memory/cache line at each iteration. Loop-invariant code motion is often a compiler optimization which performs this movement automatically.

Worked Example

If we consider the code sample, two optimization possibilities can be applied.

while (j < maximum - 1)
{
     j = j + (4+array[k])*pi+5; 
}

The calculation of maximum - 1 and (4+array[k])*pi+5 can be moved outside the loop, and precalculated, resulting in something similar to:

int maxval = maximum - 1;
int calcval = (4+array[k])*pi+5;
while (j < maxval)
{
     j = j + calcval; 
}

This can then be further optimized, leading to less overall executed code for larger values of maxval and/or smaller values of calcval.

int calcval = (4+array[k])*pi+5;
j = j + integer_part((maximum - 1 - j) / calcval) * calcval;