Loop-invariant code motion: Difference between revisions

Revision as of 09:29, 18 September 2008

Revision as of 00:30, 27 November 2008

Line 3:

'''Loop-invariant code''' in an [[Imperative programming|imperative]] [[Computer programming|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 [[register spilling|spilled]]. To counteract this, the “opposite” optimization can be performed, [[rematerialization]].

==Worked Example==

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

==Worked Exampleexample==

<code><pre>

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

<code><pre>

while (j < maximum - 1)

{

j = j + (4+array[k])*pi+5;

}

}</pre></code>

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

<code><pre>

int maxval = maximum - 1;

int calcval = (4+array[k])*pi+5;

while (j < maxval)

{

j = j + calcval;

}

}</pre></code>

[[Category:Compiler optimizations]]

{{compu-prog-stub}}