HOME

TheInfoList



OR:

In
computer programming Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...
, loop-invariant code consists of statements or expressions (in an imperative
programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming l ...
) that 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 In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power c ...
that performs this movement automatically.


Example

In the following code sample, two optimizations can be applied. int i = 0; while (i < n) Although the calculation x = y + z and x * x is loop-invariant, precautions must be taken before moving the code outside the loop. It is possible that the loop condition is false (for example, if n 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 effects, so an additional evaluation by the if construct should be compensated by replacing the while loop with a do while. If the code used do while in the first place, the whole guarding process is not needed, as the loop body is guaranteed to execute at least once. int i = 0; if (i < n) This code can be optimized further. For example, strength reduction could remove the two multiplications inside the loop (6*i and a /code>), and induction variable elimination could then elide i completely. Since 6 * i must be in lock step with i itself, there is no need to have both.


Invariant code detection

Usually, a 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. Recent work using data-flow dependence analysis allows 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.


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 Register or registration may refer to: Arts entertainment, and media Music * Register (music), the relative "height" or range of a note, melody, part, instrument, etc. * ''Register'', a 2017 album by Travis Miller * Registration (organ), t ...
, especially on processors with few registers, like the 32-bit x86. If the compiler runs out of registers, some variables will be spilled. To counteract this, the inverse optimization can be performed, rematerialization.


See also

* Code motion *
Loop invariant In computer science, a loop invariant is a property of a program loop that is true before (and after) each iteration. It is a logical assertion, sometimes checked within the code by an assertion call. Knowing its invariant(s) is essential in ...


Further reading

* Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools. Addison Wesley. .


References


External links


Compiler Optimizations — Hoisting
{{Compiler optimizations Compiler optimizations