Loop-invariant code motion: Difference between revisions

Revision as of 22:07, 9 March 2009

Latest revision as of 05:14, 19 December 2024

(56 intermediate revisions by 35 users not shown)

Line 1:

{{short description|Type of compiler optimization}}

{{Unreferenced|date=May 2007}}

{{More citations needed|date=January 2021}}

In [[computer programming]], '''[[loop-invariant code''']] consists of statements or expressions (in an [[imperative programming|imperative]] [[programming language]]) whichthat 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]] that performs this movement automatically.

==Example==

'''Loop-invariant code motion''' (also called '''hoisting''' or '''scalar promotion''') is a [[compiler optimization]] which performs this movement automatically.

If we considerIn the following code sample, two optimization possibilitiesoptimizations can be applied.

<sourcesyntaxhighlight lang="C">

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.

int i = 0;

while (ji < maxvaln) {

x = y + z;

a[i] = 6 * i + x * x;

++i;

}

</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 (computer 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 loop|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.

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]].

<sourcesyntaxhighlight lang="C">

==Worked example==

int i = 0;

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

if (i < n) {

x = y + z;

<source lang="C">

int const t1 = x * x;

while (j < maximum - 1)

do {

{

j = j + (4+arraya[ki]) = 6 *pi i +5; t1;

++i;

} while (i < n);

}

</syntaxhighlight>

</source>

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.

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:

==Invariant code detection==

<source lang="C">

Usually, a [[Reaching definition|reaching definitions analysis]] is used to detect whether a statement or expression is loop invariant.

int maxval = maximum - 1;

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

while (j < maxval)

{

j += calcval;

}

</source>

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.

It might then occur to us that the since the loop exit value of <code>j</code> must fall between <code> maxval - calcval</code> and <code>maxval + calcval</code>, or if not it was already beyond that range, then there is no need for the loop at all.

[[Category:Compiler optimizations]]

Recent work by Moyen, Rubiano and [[Thomas Seiller|Seiller]] uses data-flow dependence analysis <ref>{{cite book |last1=Moyen |first1=Jean-Yves |last2=Rubiano |first2=Thomas |last3=Seiller |first3=Thomas |chapter=Loop Quasi-Invariant Chunk Detection |title=Automated Technology for Verification and Analysis |series=Lecture Notes in Computer Science |date=2017 |volume=10482 |pages=91–108 |doi=10.1007/978-3-319-68167-2_7|isbn=978-3-319-68166-5 }}</ref> to detect not only invariant commands but larger code fragments such as an inner loop. The analysis also detects quasi-invariants of arbitrary degrees, that is commands or code fragments that become invariant after a fixed number of iterations of the loop body. This technique was later used by Aubert, Rubiano, Rusch, and [[Thomas Seiller|Seiller]] to automatically parallelise loops.<ref>{{cite book |last1=Aubert |first1=Clément |last2=Rubiano |first2=Thomas

|last3=Rusch |first3=Neea |last4=Seiller |first4=Thomas |chapter= Distributing and Parallelizing Non-canonical Loops |title= Verification, Model Checking, and Abstract Interpretation |series=Lecture Notes in Computer Science |date=2023 |volume=13881 |pages=91–108 |doi=10.1007/978-3-031-24950-1_1 }}</ref>

==Benefits==

{{compu-prog-stub}}

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

==See also==

* [[Code motion]]

* [[Loop invariant]]

==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==

* [https://web.archive.org/web/20170806083023/http://www.compileroptimizations.com/category/hoisting.htm Compiler Optimizations &mdash; Hoisting]

{{Compiler optimizations}}

[[Category:Compiler optimizations]]