Loop-invariant code motion

In computer programming, loop-invariant code consists of statements or expressions (in an 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

If we consider the following code sample, two optimizations can be easily applied.

for (int i = 0; i < n; i++) {
    x = y + z;
    a[i] = 6 * i + x * x;
}

The calculation x = y + z and x * x can be moved outside the loop since within they are loop-invariant code, so the optimized code will be something like this:

x = y + z;
t1 = x * x;
for (int i = 0; i < n; i++) {
    a[i] = 6 * i + t1;
}

This code can be optimized further. For example, strength reduction could remove the two multiplications inside the loop (6*i and a[i]), 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.

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 spilled. To counteract this, the inverse optimization can be performed, rematerialization.

External links

Compiler Optimizations — Hoisting

Compiler optimizations

Basic block	Peephole optimization

Loop optimization	Induction variable Strength reduction Loop fusion Loop inversion Loop interchange Loop-invariant code motion Loop nest optimization Loop unrolling Loop splitting Loop unswitching Software pipelining Automatic parallelization

Data-flow analysis	Common subexpression elimination Constant folding Induction variable recognition and elimination Dead store elimination Use-define chain Live variable analysis Available expression

SSA-based	Global value numbering Sparse conditional constant propagation

Code generation	Register allocation Instruction selection Instruction scheduling Rematerialization

Functional	Removing recursion Deforestation

Global	Interprocedural optimization

Other	Bounds-checking elimination Dead code elimination Inline expansion Jump threading

Static analysis	Alias analysis Pointer analysis Shape analysis Escape analysis Array access analysis Dependence analysis Control flow analysis Data flow analysis

This article is issued from Wikipedia - version of the Saturday, March 05, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Loop-invariant code motion

Example

Invariant code detection

Benefits

See also

Further reading

External links