Loop-Invariant Code Motion

Programs spend almost all of their time in loops, so a computation that lands inside a loop is the most expensive real estate in the whole procedure — run it a million times and you pay a million times over. Yet loops are full of work that does not actually depend on the loop. Inside for (i = 0; i < n; i++) a[i] = x * y + i;, the product x * y is recomputed on every iteration even though x and y never change. Loop-invariant code motion (LICM, also called hoisting) is the optimisation that spots such a computation and lifts it out of the loop, so it runs once instead of n times.

The pay-off is enormous, but the reasoning is delicate: move the wrong thing, or move it to the wrong place, and you change what the program computes — or make it crash on an input where it used to run fine. LICM is therefore a small masterclass in the compiler's central discipline: an optimisation is only worth doing if it is provably safe on every path. Getting the safety conditions exactly right is what this page is about.

First, what is a loop?

Before you can move code out of a loop, the compiler must identify the loop in the raw control-flow graph — there is no for keyword left by this stage. The precise, structural definition rests on dominators. A node d dominates a node n if every path from the entry to n goes through d.

A back edge is a CFG edge n \to h whose head h dominates its tail n;
the header h is the single entry point of the loop — it dominates every node in the loop;
the natural loop of the back edge n \to h is h together with every node that can reach n without passing through h.

A single-entry header is what makes hoisting well-defined: there is one place, just before the header, where hoisted code can live and be sure to run exactly once per entry to the loop. That place does not exist yet, so we create it — the preheader.

The preheader: a landing pad for hoisted code

A preheader is a fresh basic block inserted on the edge(s) entering the header from outside the loop; every such entry edge is redirected through it, while the loop's back edge still targets the header directly. It is the one block that dominates the header and runs once before the loop begins — the natural home for anything we lift out.

Reveal the diagram: the raw loop (header B_2, body B_3, back edge B_3 \to B_2) first gets a preheader spliced onto its entry edge, and then the invariant statement t = x * y migrates up into it. Inside the loop, the body now just reads t.

Which computations are invariant?

A statement in the loop computes a loop-invariant value if — no matter which iteration you are on — its operands always have the same value. Formally, an operand is invariant if it is:

An operand is loop-invariant if…
it is a literal constant, or
all of its reaching definitions lie outside the loop, or
it has exactly one reaching definition, and that definition is itself a statement already marked loop-invariant.

That last clause is recursive, so you compute the invariant set by iteration to a fixed point: repeatedly sweep the loop marking any statement whose operands are all now invariant, until a sweep marks nothing new. It leans directly on reaching definitions to answer "where could this operand have come from?", and it composes with available expressions, which catches the redundancy across iterations.

Marking invariants, in code

The engine below takes a loop body as a list of three-address statements, plus the set of variables defined outside the loop, and marks the invariant statements by fixed-point iteration — exactly the recursive rule above.

type Stmt = { dst: string; args: string[] }; // dst = f(args...) // Variables whose reaching definitions are all OUTSIDE the loop. const outside = new Set(["x", "y", "n"]); const isNum = (s: string) => /^-?\d+$/.test(s); // Loop body: t = x * y; s = t + n; a = i * 4; i = i + 1; const body: Stmt[] = [ { dst: "t", args: ["x", "y"] }, { dst: "s", args: ["t", "n"] }, { dst: "a", args: ["i", "4"] }, { dst: "i", args: ["i", "1"] }, ]; // A variable is defined inside the loop if some body statement writes it. const definedInside = new Set(body.map((st) => st.dst)); const invariantStmts = new Set<number>(); // An operand is invariant if: a literal, or defined only outside, // or its single in-loop def is an already-invariant statement. const operandInvariant = (v: string): boolean => { if (isNum(v)) return true; if (!definedInside.has(v)) return outside.has(v); // reaches from outside // find the in-loop def(s) of v const defs = body.map((st, i) => (st.dst === v ? i : -1)).filter((i) => i >= 0); return defs.length === 1 && invariantStmts.has(defs[0]); }; let changed = true, rounds = 0; while (changed) { changed = false; rounds++; body.forEach((st, i) => { if (invariantStmts.has(i)) return; if (st.args.every(operandInvariant)) { invariantStmts.add(i); changed = true; } }); } console.log(`fixed point in ${rounds} sweeps`); body.forEach((st, i) => { const tag = invariantStmts.has(i) ? "INVARIANT -> hoist" : "varies (stays in loop)"; console.log(`${st.dst} = ${st.args.join(" op ")} ${tag}`); });

t = x * y is invariant (both operands come from outside), and then s = t + n becomes invariant on the next sweep because its only in-loop operand, t, was just marked — the fixed point in action. But a = i * 4 and i = i + 1 stay put: i is redefined every iteration, so they vary.

Invariant is necessary, not sufficient — the safety conditions

Here is the deep point: a statement being loop-invariant does not by itself make it safe to hoist. Move it to the preheader and it will now execute unconditionally, once, before the loop — even if, in the original program, some iterations (or all of them) would have skipped it. For the transformation to preserve meaning, the statement d\!:\ t = u \circ v (defining t) must satisfy all three:

d's block dominates all exits of the loop (every loop exit is reached only through d) — so if the loop is entered, d would definitely have run;
t is not assigned elsewhere in the loop — d is the only definition of t in it;
d dominates every use of t in the loop — so no use ever reads a different, pre-hoist value.

The first condition is the one people forget, and it is the one that protects correctness of outcome. If d sits inside an if within the loop, or after a possible early exit, then some run of the loop might never have executed d at all. Hoisting it forces it to run — and if it can fault (divide by zero, dereference a null, index out of bounds), you have just introduced a crash into a program that was previously correct. Domination of exits is exactly the guarantee that "the loop ran \Rightarrow d ran", which is what lets you safely run d up front.

A companion: strength reduction of induction variables

Hoisting has a famous sibling that also exploits loop structure. An induction variable is one that changes by a fixed amount each iteration — the loop counter i, and any variable of the form j = c_1 \cdot i + c_2 derived from it. Strength reduction replaces the expensive recomputation j = 4 \cdot i (a multiply, every iteration) with a cheap running update j \mathrel{+}= 4 (an add), seeded once in the preheader:

\underbrace{j = 4 \cdot i}_{\text{multiply each pass}} \quad\longrightarrow\quad \underbrace{j = j + 4}_{\text{add each pass, }j\text{ init'd in preheader}}.

It is not invariant code — j genuinely changes every iteration — but it uses the same loop analysis (finding the header, the preheader, and the basic induction variable i) to trade a costly operation for a cheap one. Array-address arithmetic in tight loops is the classic beneficiary, which is why LICM and strength reduction are almost always run together.

Because a loop header can have several predecessors from outside the loop (think two if arms that both fall into the same while). If you hoisted into one of them, the code would not run when control entered through the other — and if you hoisted into all of them you would duplicate it and risk running it when the loop is never entered from a third path. The preheader solves this cleanly: it is a single block on the combined entry, dominating the header, guaranteed to run exactly once each time the loop is entered and never otherwise. Creating it is cheap, and it gives every subsequent loop optimisation (LICM, strength reduction, invariant guards) a canonical place to deposit setup code.

The classic bug: you find t = a / b loop-invariant (both a and b defined outside) and hoist it — but in the original loop that statement sat inside if (b != 0) { … }, so it only ran when b was non-zero. Hoisted to the preheader it runs unconditionally, and on an input where the loop body's guard would have kept b == 0 away from the division, your "optimised" program now divides by zero and crashes. The guardrail is the dominance condition: hoist d only if its block dominates all loop exits (so entering the loop guarantees d would have executed). A statement buried in a conditional inside the loop does not dominate the exits, so it is not a legal hoist — invariance notwithstanding. (Compilers relax this only for statements proven never to fault and whose result is dead if the loop doesn't run — "speculative" hoisting — but the default rule is: dominate the exits, or stay put.)