Loop-invariant code motion: Difference between revisions

Revision as of 18:13, 16 September 2020

Revision as of 23:57, 26 January 2021

Line 1:

{{UnreferencedMore citations needed|date=MayJanuary 20072021}}

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.

==Example==

In the following code sample, two optimizations can be applied.

<syntaxhighlight lang="C">

Line 15:

</syntaxhighlight>

Although the calculation <code>x = y + z</code> and <code>x * x</code> is loop-invariant, precautions must be taken before moving the code outside the loop. It is possible that the loop condition is <code>false</code> (for example, if <code>n</code> holds a negative value), and in such case, the loop body should not be executed at all. One way of guaranteeing correct behaviour is using a conditional branch outside of the loop. Evaluating the loop condition can have [[Side_effect_Side effect (computer_sciencecomputer science)|side effects]], so an additional evaluation by the <code>if</code> construct should be compensated by replacing the <code>while</code> loop with a <code>do {} while</code>. If the code used <code>do {} while</code> in the first place, the whole guarding process is not needed, as the loop body is guaranteed to execute at least once.

<syntaxhighlight lang="C">

Line 39:

==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 inverse optimization can be performed, [[rematerialization]].

Line 48:

==Further reading==

* Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools. Addison Wesley. {{ISBN|0-201-10088-6}}.

==References==

{{Reflist}}

==External links==

Line 55 ⟶ 58:

[[Category:Compiler optimizations]]

{{compu-prog-stub}}