Loop-invariant code motion: Difference between revisions

Revision as of 00:50, 27 November 2008

Revision as of 15:36, 24 December 2008

Line 1:

{{Unreferenced|date=May 2007}}

In [[computer programming]], '''loop-invariant code''' consists of statements (in an [[imperative programming|imperative]] [[programming language]]) which can be moved outside the body of a 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 constants to be stored in registers and not having to calculate the address and access the memory (or cache line) at each iteration.

'''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 [[register spilling|spilled]]. To counteract this, the “opposite” optimization can be performed, [[rematerialization]].

==Worked example==