Loop-invariant code motion

This is an old revision of this page, as edited by Alksentrs (talk | contribs) at 00:35, 27 November 2008 (move sentence to next paragraph; make other names bold). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Loop-invariant code 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 constants in registers and not having to calculate the address and access the memory/cache line at each iteration.

Loop-invariant code motion (also called hoisting or scalar promotion) is a compiler optimization which performs this movement automatically. 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.

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