Content deleted Content added
MathsPoetry (talk | contribs) mNo edit summary |
MathsPoetry (talk | contribs) More titles |
||
Line 1:
{{Unreferenced|date=May 2007}}
In [[computer programming]], '''loop-invariant code''' consists of statements or expressions (in an [[imperative programming|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 motion''' (also called '''hoisting''' or '''scalar promotion''') is a [[compiler optimization]] which performs this movement automatically. Usually a [[Reaching definition|reaching definitions analysis]] is used to detect whether a statement or expression is loop invariant. For example, if all reaching definitions for the operands of some simple expression are outside of the loop, the expression can be moved out of the loop.▼
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]].▼
==Example==
Line 30 ⟶ 24:
This code can be optimized further. For example, [[strength reduction]] could remove the two multiplications inside the loop (<code>6*i</code> and <code>a[i]</code>), and [[induction variable]] elimination could then elide <code>i</code> completely. Since <code>6 * i</code> must be in lock step with <code>i</code> itself, there is no need to have both.
==Invariant code detection==
▲
==Benefits==
▲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]].
==Further Reading==
| |||