Loop-Invariant Code Motion and the Conditions It Needs

A loop-invariant expression is one whose value does not change across iterations. Moving it to the loop preheader — the block that executes once before the loop — removes the computation from every iteration and leaves a single evaluation. The transformation is among the oldest in optimizing compilers, described in Allen and Cocke’s 1972 catalogue, and it is still the one most often blocked by imprecise analyses rather than by the transformation itself.

The difficulty is entirely in the conditions. An expression is invariant if its operands are invariant along every path that reaches the expression, which is a dataflow question. Hoisting it is legal if the expression has no side effects, if executing it earlier cannot introduce a trap the program would not have reached, and if the loop is guaranteed to execute at least once — or if the expression is safe to execute speculatively. Each of those conditions has a failure mode that produces a miscompile rather than merely a missed optimization.

Invariance is not a syntactic property

The naive test — does the expression mention a variable assigned inside the loop — is both too strong and too weak. It is too strong because a variable assigned inside the loop can still be invariant at the point of the expression: a loop that resets a counter at the top and reads it later has a definition inside the loop, but the value reaching the read is the same every iteration. It is too weak because an operand that is not assigned in the loop can still change: *p and a[i] are not variables, and a store through a different pointer inside the loop can change both.

The correct formulation uses reaching definitions, run on the loop body. An expression is invariant with respect to a loop if, for every operand, all reaching definitions of that operand are outside the loop. That is a question the analysis from Reaching Definitions and the Monotone Dataflow Framework answers directly, and on SSA form it becomes a reachability test over def-use edges: an operand is invariant if its single definition dominates the loop and no phi in the loop’s header feeds it.

For memory operands the question becomes whether any store inside the loop may write the location the load reads. That is an alias question, and the answer determines almost all of the practical power of the pass. A load from a local array whose address never escapes is invariant if no store inside the loop writes the array; a load through a pointer parameter is invariant only if the analysis can prove no store aliases it. Compilers with no alias information must assume any store may write any address-taken location, which makes nearly every load invariant-blocked. This is the concrete reason escape analysis improves loop performance indirectly, as discussed in Escape Analysis and Scalar Replacement of Aggregates.

/* With restrict on out, a store through it cannot alias the other pointers. */
void scale(float *restrict out, const float *in, const float *coeff, int n, int k) {
    float c = coeff[k];          /* invariant: nothing in the loop writes coeff */
    for (int i = 0; i < n; i++) {
        float base = in[0];      /* invariant address, but is the load movable? */
        out[i] = (in[i] + base) * c;
    }
}

The base load has a loop-invariant address, so the invariance question is settled; whether the load may be moved is the alias question, and restrict on out is what answers it, since without the qualifier a store to out[i] could write in[0] and the hoisted value would be stale.

The preheader, and why it exists

Loop canonicalization guarantees a unique preheader: a block with exactly one successor, which is the loop header, and whose only predecessor is outside the loop. Hoisting targets that block because it executes exactly once, before any iteration, and dominates every block in the loop.

Without a preheader the transformation has nowhere legal to place the computation. Inserting a block is not optional bookkeeping; it is what makes the dominance argument work, because the hoisted definition must dominate every use inside the loop, and a definition placed in an arbitrary predecessor block does not.

A related requirement is that the loop have a single entry. A loop with two entry edges has two preheaders at best and no unique point that dominates the body; irreducible control flow must be restructured before loop optimizations apply. This is why compilers run loop simplification — turning while into a rotated form with a single back edge — as a prerequisite pass rather than as an optimization in its own right.

Speculation and the trap problem

Consider hoisting x / y where y is loop-invariant but may be zero. The division traps. Inside the loop, the division executes only on iterations that reach it; if the loop body has an early exit that skips the division on the last iteration, hoisting it executes a trap the program would have avoided. The transformation has changed the set of observable behaviours.

The same argument applies to loads. Hoisting a load out of a loop executes it before the loop, which is a problem if the address is invalid on the path that enters the loop but never reaches the load, or if the loop may execute zero times. A load from a null pointer that the original program never performed is a fault the compiler introduced.

Three resolutions are available and real compilers choose among them by policy.

Prove the loop executes at least once. A rotated loop whose header is entered only after a guard that tests the condition has a body that runs at least once, so hoisting out of the body is safe with respect to the zero-trip case. This is one of the reasons loop rotation is done early.

Prove the operation cannot trap. A division whose divisor is a nonzero constant is safe. A load whose address is provably within a valid object is safe under the language’s rules. The analysis needed is a range or non-null analysis, and it is the same machinery used for bounds-check elimination.

Speculate and guard. Hoist the operation into the preheader, and if the original execution was conditional, either keep a guard or rely on the language’s rules about speculative execution. Some language definitions permit moving a potentially trapping operation as long as the program’s defined behaviour is unchanged, which is a licence that depends on the language rather than on the compiler.

The four conditions reduce to a checklist that a pass applies per candidate expression:

Condition	Fails when	Consequence of getting it wrong
Operands invariant	a store in the loop may write the loaded address	stale value used
No side effect	the expression stores, calls, or is volatile	effect count changes
Cannot trap, or loop runs at least once	divisor may be zero, address may be null	fault on a path that never executed it
Pressure budget	unrolled body is already at the register limit	spill costs exceed the saved work

A candidate that fails any row is left in place. The pass does not build guards to rescue a failing candidate, which is why the alias and range analyses determine its reach more than the hoisting logic does.

Side effects and the operations that cannot move

An expression with a side effect cannot be hoisted because hoisting changes how many times the effect occurs. A store, a call to a function with effects, an atomic operation, and a volatile access all fall in this class. Volatile is worth naming separately: a volatile load must occur exactly as many times as the source says, so hoisting it out of a loop changes the program’s interaction with hardware or another thread. Compilers treat volatile accesses as immovable regardless of invariance.

Calls need a purity argument. A call to a function with no side effects and whose result depends only on its arguments can be hoisted if the arguments are invariant. That requires an interprocedural summary, which is why the pass improves substantially under link-time optimization: without a summary, every call is opaque and blocks hoisting of anything that depends on its result.

The exception path is the subtle one. A call that may throw cannot be hoisted out of a loop that catches the exception inside the loop, because the handler’s position relative to the loop changes. Even without a handler inside the loop, hoisting a throwing call past an earlier statement changes which statement is reported as the faulting one. Compilers that model exceptions as explicit edges in the CFG see this; compilers that do not must refuse to move calls that may throw.

Register pressure and the reason not to hoist

Hoisting lengthens live ranges. A value computed in the preheader and used in the last block of the loop is live across the entire loop body, which may force the allocator to spill something else. If the loop body is already at the register limit, hoisting one more value can cost more than the computation saved.

Production implementations therefore gate hoisting on a pressure estimate. The usual rule is to hoist only if the loop’s maximum live-value count stays below a threshold, or to hoist into a register only when the value’s uses are few and clustered. This is a real trade rather than a theoretical one: on targets with sixteen general-purpose registers, a loop body holding fourteen live values has room for two hoisted results and no more.

The interaction with unrolling is worth noting. Unrolling the loop multiplies the number of simultaneously live values at any point, so a hoist that was safe before unrolling may become a spill after it. Passes that unroll should therefore re-run or invalidate the hoisting decisions, and unrolling after hoisting sometimes undoes the hoist’s benefit without undoing the hoist.

What survives after the hoist

Hoisting rarely stands alone. A hoisted load feeding a hoisted arithmetic operation lets the operation be constant-folded in the preheader, which then lets the branch that used its result be simplified, which then makes part of the loop body unreachable. The sequence is the same pattern as Constant Propagation over a Flat Lattice describes: a small local transformation exposes a larger one, and the optimizer’s job is to iterate until nothing changes.

The complementary transformation is sinking, which moves an expression from the preheader into the loop or from a loop into its exit when the expression is used only there. Sinking reduces live ranges at the cost of recomputation, and the two passes together implement a placement policy: compute at the point that minimizes the product of execution frequency and live-range length. That policy is what loop-invariant code motion approximates with a single, cheap rule.