Loopstypical

Loop-Invariant Code Motion

Move a computation whose result never changes out of the loop — but only if it is invariant AND either cannot trap or is guaranteed to execute at least once. That second condition is the one that turns a hoist into a fault the original program never had.

The question

The expression inside my loop clearly does not change. Why did the compiler leave it there?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A control-flow graph with natural loops identified: a header, a back edge, a body, and — usually inserted for this transformation — a *preheader*, a block on the path into the header from outside that exists solely to hold hoisted code. The preheader is the representation this pass adds, and without it there is nowhere to put a hoisted instruction that is guaranteed to run exactly once before the loop.

What this phase may assume or do

Two conditions, both required. (1) Invariance: every operand is either defined outside the loop or is itself loop-invariant, and nothing inside the loop can redefine it — over memory that requires proving no store in the loop may alias the load. (2) Safety of speculation: the computation must either be unable to trap, or be guaranteed to execute on every execution of the loop. Hoisting a trapping computation out of a loop whose body might run zero times introduces a fault the original program did not have, which is a change in observable behavior even though the expression was genuinely invariant.

Key points

Two conditions: the computation is invariant, and hoisting cannot introduce an execution or a fault the original program did not have.
A loop that may run zero times is the case that blocks the hoist, because the preheader runs unconditionally and the body does not.
Compilers get the hoist anyway by proving a non-zero trip count, proving the operation cannot fault, or guarding the hoisted code with the loop condition.
Hoisting a load requires proving no store in the loop may alias it — which is alias analysis, and is why the same loop optimizes differently in C and in Rust.
The transformation needs a preheader, a natural-loop identification and a dominator tree; it is a consumer of the whole CFG module.

The condition everyone remembers, and the one they do not

Invariance is the obvious half and it is usually easy: walk the loop body, mark every instruction whose operands are all defined outside the loop or already marked, iterate. For pure arithmetic over SSA registers this converges in a couple of passes and is uncontroversial.

The half that stops compilers is that hoisting changes *when* — and, critically, *whether* — the computation runs. Code inside a loop body runs zero times when the loop does not execute. Code in the preheader runs once, unconditionally, on the way in. If the computation can fault, those are different programs.

The example below is the standard one. n may be zero, in which case the original program never dereferences p and never divides. Hoisted, both happen before the trip count is even tested. If p is null on the empty-loop path — a perfectly ordinary situation for an empty collection — the program now segfaults where it used to return quietly.

A hoist that is invariant and still illegal

Before

for (int i = 0; i < n; i++) {
    sum += *p / d;
}

After

// NOT permitted as written:
int t = *p / d;
for (int i = 0; i < n; i++) {
    sum += t;
}

Legal only when

*p / d is invariant only if no store inside the loop may alias p and neither p nor d is reassigned. Even given that, the hoist is legal only when the loop is guaranteed to execute at least once — a compiler can establish this by proving n > 0, or by *guarding* the hoisted code with the loop condition, which is what a real implementation does: if (n > 0) { t = *p / d; ... }.

Illegal when

n may be zero. Then the original program performs neither the load nor the division, and the transformed one performs both — introducing a possible null dereference and a possible division by zero on a path that previously did nothing at all. The same argument in miniature is why AtlasLang refuses to constant-fold 1 / 0: a transformation may not move a fault to a place the program would not have reached.

How compilers get the hoist anyway

The condition is not a dead end; it is a thing to establish. There are three standard routes, and a compiler will try all of them.

First, prove the loop runs at least once. If the trip count is a known constant, or the loop is a do-while, or an earlier check dominates the loop and implies n > 0, the body dominates the exit and hoisting is unconditionally safe. This is why rotating a while loop into a guarded do-while — loop rotation — is a standard preparatory transformation: it exists partly to make hoisting legal.

Second, prove the computation cannot trap. Pure arithmetic on registers cannot fault, so it hoists freely. A load can be proved non-faulting if the compiler knows the pointer is dereferenceable — LLVM has a dereferenceable attribute for exactly this, and Rust's references carry that guarantee by construction, which is one reason Rust loops hoist where equivalent C loops do not.

Third, guard it. Emit the hoisted code under the loop's entry condition. This costs one branch on entry and buys the hoist for every iteration, and it is what a compiler usually does when it cannot establish either of the first two.

Note what this means for the everyday advice to hoist expressions out of loops by hand: sometimes the compiler cannot do it, and the reason is almost never that it did not notice. It is that the expression touches memory it cannot prove is unchanged, or that the loop might not run.

Where hoisted code goes, and why the preheader has to exist

entryentryentry
```
%n = param 0
branch %n > 0 ? pre : exit
```
This test is what makes hoisting safe. Without it, `pre` runs even when the loop body never would.
prepreheader
```
%t = int %pval / %d
```
Runs exactly once, only on the path where the body will execute at least once.

headloop header↺ loop header

%i = phi i [0 from pre, %i2 from body]
branch %i < %n ? body : exit

bodyloop bodylatch
```
%sum2 = int %sum + %t
%i2 = int %i + 1
```
The division is gone from here — that is the entire payoff.
exitexit
```
ret
```

Edges

entry→pre
entry→exit
pre→head
head→body
head→exit
body→head

Immediate dominator

preidomentry
headidompre
bodyidomhead
exitidomentry

Read it asThe preheader is not part of the loop: it has exactly one successor, the header, and it is not a target of the back edge. That structure is what guarantees hoisted code runs exactly once. Building it is [[cfg-construction]] work, and identifying the header and back edge is [[natural-loops]] — this pass consumes both and would be unwritable without them.

Memory is where it stops

typicalMainstream compilers implement this as LICM (LLVM) or -fmove-loop-invariants plus store-motion (GCC), and both will guard the hoist with the loop entry condition when they cannot prove the loop is non-empty. Whether a specific load hoists is decided by the alias analysis in use and by the language's aliasing rules, so the same loop in C, Rust and Fortran gets three different answers with no difference in the optimizer.

Hoisting arithmetic is easy. Hoisting a *load* is where the value is, and where the difficulty is, because the load is invariant only if nothing in the loop can write to that location. In C, a loop that writes through one pointer and reads through another must generally assume they may be the same, so the read stays inside — which is exactly the situation restrict exists to fix and the reason the identical Rust or Fortran loop optimizes better.

The everyday version: for (i = 0; i < strlen(s); i++) calls strlen every iteration unless the compiler can prove the loop body does not modify s. Some compilers can, because strlen is a known pure function and the body does not write to char objects; many cannot, and the loop is quadratic. Hoisting it by hand is not micro-optimization, it is supplying information the compiler could not derive.

The other everyday version is a field load in a loop, hoisted only if the compiler can prove no call and no store in the body touches that field. A single call to a function it cannot see into is enough to block it, which is one of the reasons [[inlining]] is a prerequisite for so much loop optimization.

How it works

The steps, in the order the compiler takes them.

Identify natural loops from back edges in the CFG, and create a preheader for each loop header that does not already have a single non-loop predecessor.
Mark instructions in the loop body whose operands are all defined outside the loop; iterate until no new instruction is marked.
For each marked instruction, ask whether it can trap or otherwise have an effect. If it cannot, it is hoistable.
If it can trap, ask whether its block dominates every loop exit — that is, whether it executes on every iteration including the first. If so, hoisting it is safe because the loop is entered at all.
Otherwise, either prove the trip count is non-zero, or place the hoisted code under a guard testing the loop entry condition.
Move the instruction to the preheader and let the operands' live ranges lengthen accordingly; register pressure is the price and the allocator will pay it.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A program that ran fine now segfaults on an empty input, because a load was hoisted out of a loop that used to execute zero times. The crash is in the preheader, on a line the source shows inside the loop.
A loop containing strlen in its condition is quadratic in the string length, and the profile shows all the time inside strlen. Nothing looks wrong in the source.
A hoist lengthens a live range across the whole loop, register pressure exceeds the register file, and the allocator spills — the loop is now doing a load and a store per iteration instead of the arithmetic it saved.
A hand-hoisted expression is now stale because someone added a write to the underlying data inside the loop. The compiler would have refused the hoist; the human did not re-check it.

When it helps

Any loop whose body recomputes something fixed: an address base, a length, a configuration lookup, a conversion factor.
Loops after inlining, where the inlined body contains invariant setup that was not visible as invariant before the inline.
As a preparation for vectorization and unrolling: a body with no invariant work left is a much better candidate for both.

When it hurts

Where the hoisted value must stay live across the whole loop and the loop was already at register pressure — trading an arithmetic instruction per iteration for a spill slot accessed per iteration is a bad deal.
Where the guard the compiler had to insert costs more than the hoist saved, which happens in loops with very low average trip counts.

What it costs

Every one of these is paid by something.

Hoisting buys the removal of a per-iteration computation and pays in register pressure: the hoisted value is live for the entire loop, and if that forces a spill the loop does more memory work than before.
Guarding a hoist to make it legal buys the transformation for non-provable loops and costs a branch plus a duplicated entry path, which grows code size and matters when trip counts are small.
Extending the pass to loads buys the transformation that actually matters in real code and costs a full alias analysis, whose precision is itself a compile-time dial.

What else you could do

What a different compiler or language does instead, and when that is better.

Hoist it in the source. Free, portable, and it does not depend on the compiler proving anything — at the cost of source that separates a value from where it is used.
Supply the missing fact instead: restrict in C, const, or a reference type that carries a dereferenceability guarantee. This keeps the source shape and gives the compiler what it lacked.
Loop rotation first: converting a while into a guarded do-while establishes the "executes at least once" condition for the whole body, which is why compilers do it as a preparatory pass rather than as an optimization in its own right.
Partial redundancy elimination subsumes hoisting: an invariant expression inside a loop is partially redundant with itself across iterations, and PRE places it optimally without a special-cased loop pass — more general, more expensive.

See it for yourself

The flag, dump or tool that shows you this directly.

LLVM: opt -passes=licm -S on the IR, and -Rpass=licm from clang, report each hoist. -Rpass-missed=licm is more useful — it says what it declined.
GCC: -fdump-tree-lim-details prints the loop-invariant motion pass's decisions including the invariance analysis.
The empty-loop experiment: compile a loop containing an invariant load with -O2, then call it with a zero trip count under a debugger and see whether the load happens.
Compare for (i = 0; i < strlen(s); i++) against a hoisted length at -O2 in Compiler Explorer; whether the call survives is a direct readout of what the compiler could prove.

Plausible wrong readings

Stated the way a confident engineer states them.

"The compiler hoists anything that does not change." Only if it can also prove that running it eagerly cannot fault, or that the loop runs at least once. Invariance alone is not sufficient.
"Hoisting is always a win." It lengthens a live range across the loop. In a register-starved loop that means a spill, and a spill per iteration costs more than the arithmetic it replaced.
"A load that nothing in the loop obviously writes is invariant." Obvious to you is not proof to the compiler: a call it cannot see into, or a store through a pointer it cannot disambiguate, is enough to block it.

Misconceptions

The claim, and what is actually true.

If a value does not change in the loop, the compiler moves it out.

Only when it can also show that computing it early cannot fault on a path where the loop body would never have run. That is the condition that blocks most real hoists of loads.

Manually hoisting expressions out of loops is premature optimization.

It is sometimes the only way to supply information the compiler cannot derive — the strlen-in-the-condition case turns linear into quadratic and no optimizer will fix it for you if the body might modify the string.

Hoisting reduces work, so it reduces time.

It converts per-iteration computation into a longer live range. When that live range spills, the loop does a load and a store per iteration instead of an add.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

If a calculation inside a loop gives the same answer every time, do it once before the loop instead. The complication is that "before the loop" happens even when the loop body would not have — so anything that could crash or fail must not be moved unless the compiler knows the loop runs at least once.

practical

Assume arithmetic hoists and memory reads often do not. If a loop reads the same field or calls the same function every iteration and the profile says so, hoist it yourself or give the compiler the aliasing information it needs. And if a crash appears in a preheader on an empty input after a compiler upgrade, suspect a hoist that was newly enabled.

advanced

The general framing is speculation safety: a transformation may execute an operation on a path where the original would not, only if that operation is *safe to speculate* — provably non-faulting, or already guaranteed to execute. LLVM encodes this as isSafeToSpeculativelyExecute and threads it through LICM, if-conversion, select formation and unswitching, all of which face the same question. Attributes like dereferenceable(N) and nonnull exist so that a frontend which knows more than the IR can say so, and Rust's frontend emits them for references, which is a concrete case of a type system paying for itself inside the optimizer.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalMainstream compilers hoist invariant arithmetic reliably at -O2 and hoist invariant loads only when alias analysis permits. Whether a particular load hoists therefore depends on the language (C without restrict versus Rust versus Fortran), on whether the body contains an opaque call, and on the alias analysis in the specific compiler version.

specThe prohibition on introducing a fault is a language-level rule about observable behavior, not a compiler convention. C and C++ both permit an implementation to speculate only where the speculated operation is defined; introducing a dereference of a possibly-null pointer that the original program would not have performed changes the program, and no optimization level licenses it.

implementationAtlasLang does not implement loop-invariant code motion at all — it has natural-loop identification in its CFG but no loop passes. Its optimizer is scalar and intraprocedural, so a loop-invariant computation stays where the frontend put it, which is visible in the pass manager as a loop whose body never shrinks.

If you were asked this in an interview

A loop contains an obviously invariant expression and the compiler leaves it in place. Give me two reasons that could be correct behavior.
What is a preheader and why does loop-invariant code motion need one?
How would you make a hoist legal for a loop whose trip count you cannot determine?

Connections

Computer Architecturebranch-prediction registers

Performancecpu-profiling measure-before-optimizing