Loop-invariant code motion

In computer programming, loop-invariant code consists of statements or expressions (in an imperative programming language) 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 that performs this movement automatically. In the following code sample, two optimizations can be applied. int i = 0; while (i < n) { x = y + z; a[i] = 6 * i + x * x; i; } 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) { x = y + z; int const t1 = x * x; do { a[i] = 6 * i + t1; i; } while (i < n); } 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. 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.