Loop Optimizations and Loop-Invariant Code Motion

A loop, in the compiler sense, is not just "code that looks like a `for` or `while`" — it is a precise graph-theoretic structure in the control-flow graph (CFG), where nodes are basic blocks and edges represent possible control transfers. We say block `d` dominates block `n` (written `d dom n`) if every path from the CFG's entry block to `n` passes through `d`. Every block dominates itself, and dominance is a partial order (reflexive, transitive, antisymmetric on the reachable graph), which lets us build a dominator tree where each node's parent is its immediate dominator — the unique closest dominator other than itself. A back edge is an edge `n → h` in the CFG where the target `h` dominates the source `n`. A natural loop for a back edge `n → h` is the smallest set of blocks containing `h` and `n` such that every block in the set (other than `h`) has all of its predecessors also in the set. The block `h` is the loop header — the single entry point through which all iterations must pass. This dominator-based definition is what makes natural loops well-behaved: every natural loop has exactly one entry (the header), which is essential for the safety arguments behind hoisting. Loops that don't fit this pattern — multiple-entry cycles arising from `goto`s crossing into a loop body — are called irreducible, and classical loop optimizations either skip them or first apply node-splitting to make them reducible. Three transformations exploit this structure once loops are identified. Loop-invariant code motion (LICM) finds computations whose result doesn't change across iterations and moves them to a synthetic preheader block that executes exactly once before the loop begins. Strength reduction targets a special class of loop-invariant-adjacent values called induction variables — variables that change by a fixed, loop-invariant amount each iteration — and rewrites expensive derived computations (multiplications, in particular) as cheap running updates. Induction-variable elimination then notices when several induction variables are affine functions of one another and eliminates all but one, reducing both the instruction count and the number of live registers. All three build directly on the value and redundancy analysis from Common Subexpression Elimination and interact tightly with Constant Folding and Constant Propagation, since constants discovered by those passes often reveal that a computation is loop-invariant.

Step 1 — Build the dominator tree. The standard approach computes, for every node `n`, the set `Dom(n)` of nodes that dominate it, via the iterative dataflow equation ``` Dom(entry) = { entry } Dom(n) = { n } ∪ ⋂_{p ∈ preds(n)} Dom(p) for n ≠ entry ``` iterated to a fixed point (or using the faster Lengauer–Tarjan algorithm for large graphs, which runs in near-linear time). This directly parallels the fixed-point style used in Constant Folding and Constant Propagation's dataflow framework, since dominator computation is itself a forward "must" dataflow analysis over sets.

Step 2 — Identify back edges and natural loops. For every CFG edge `n → h`, check whether `h ∈ Dom(n)`; if so it's a back edge and defines a natural loop, found by a backward reachability search from `n` that stops at `h`.

Step 3 — Build a preheader. Insert a new empty block between the loop header and all of its outside-the-loop predecessors, so hoisted code has a single, unambiguous landing spot that runs exactly once per loop entry (not once per iteration, and not zero times if the loop runs at all).

Step 4 — Detect invariant instructions. An instruction `t = a op b` is loop-invariant if, for each operand, either it's a constant, or it's defined outside the loop, or it's defined by exactly one reaching definition inside the loop that is itself already marked invariant. This is computed to a fixed point: keep scanning the loop body marking newly-provable-invariant instructions until no new ones are found.

Step 5 — Apply hoisting under safety conditions. An invariant instruction can be moved to the preheader only if all of the following hold: 1. It is in a block that dominates all exits of the loop (so it would have executed anyway on every path out). 2. Its destination is not assigned anywhere else in the loop (single reaching definition — otherwise moving it changes which write "wins"). 3. Its destination is not live-out before its original position in a way that a later hoisted definition would be observed too early (subtlety for reordering multiple hoists). 4. It has no side effects that must occur once per iteration (no memory writes, no potentially-trapping division/dereference) unless it can be proven the operation is safe. ```pseudocode // Loop identification function FindNaturalLoops(CFG): Dom ← ComputeDominators(CFG) loops ← ∅ for each edge (n → h) in CFG.edges: if h in Dom[n]: // back edge test loop ← { h, n } worklist ← [n] while worklist not empty: b ← worklist.pop() for p in preds(b): if p not in loop: loop.add(p) worklist.push(p) loops.add((header = h, body = loop)) return loops // Loop-invariant code motion function LICM(loop): header, body ← loop.header, loop.body preheader ← InsertPreheader(header) changed ← true invariant ← ∅ while changed: changed ← false for instr in TopoOrderOverBody(body): if instr already in invariant: continue if IsInvariantOperand(instr.op1, body, invariant) and IsInvariantOperand(instr.op2, body, invariant): invariant.add(instr) changed ← true for instr in invariant, in original order: if DominatesAllExits(instr.block, body) and HasSingleReachingDefinition(instr.dest, body) and NotLiveBeforeLoop(instr.dest) and NoUnsafeSideEffect(instr): MoveToEnd(preheader, instr) // preserve relative order among hoisted instrs function IsInvariantOperand(x, body, invariant): if x is constant: return true if DefinitionOf(x) is outside body: return true defs ← AllDefinitionsOf(x, body) return |defs| == 1 and defs[0] in invariant ```

Step 6 — Strength reduction on induction variables. After LICM, identify basic induction variables: variables `i` updated in the loop only by `i ← i + c` for loop-invariant `c`. Then find derived induction variables: variables defined as `j ← i a + b` for loop-invariant `a, b` where `i` is a basic (or already-derived) induction variable. Each derived induction variable `j = ia + b` can be replaced by a new variable `j'` initialized once as `ai₀ + b` in the preheader and updated each iteration by `j' ← j' + ac` (loop-invariant increment, itself hoistable), eliminating the multiply entirely. ```pseudocode function StrengthReduce(loop): basicIVs ← FindBasicInductionVariables(loop) // i += c form for j = i a + b found in loop.body, with i in basicIVs, a,b invariant: j' ← NewTemp() Insert(preheader, j' ← a i_initial + b) // computed once Insert(loop.body, after i's update, j' ← j' + a*c) // c = i's increment ReplaceAllUsesOf(j, j') RemoveOriginalDefinitionOf(j) ```

Step 7 — Induction-variable elimination. Once several induction variables are affine images of one another, keep only the variables actually needed to compute loop conditions or live results, and rewrite the loop test in terms of a surviving variable, deleting the rest along with their per-iteration update instructions.

Dominator computation. The naive iterative dataflow algorithm converges in `O(V·E)` time in the worst case because each iteration can change `Dom` sets and there are at most `O(V)` meaningful iterations over `O(E)` edges; in practice it converges in a handful of passes on typical CFGs. The Lengauer–Tarjan algorithm computes exact dominators in `O(E · α(E,V))` (near-linear with the inverse-Ackermann function), which is what production compilers use for large functions.

Loop identification. Finding all back edges is `O(E)` (one dominator membership test per edge, each `O(1)` given precomputed dominator sets or tree ancestor queries via `O(log V)` per query with appropriate preprocessing). Building each natural loop is a bounded graph traversal, so identifying all loops is `O(V + E)` overall.

LICM. The fixed-point marking loop runs at most `|body|` rounds (each round must mark at least one new instruction invariant or terminate), each round doing `O(|body|)` work, giving `O(|body|²)` worst case; in practice a single topological pass over the loop body suffices for the vast majority of real loops because dependency chains are shallow, making it effectively linear. The final hoisting pass is `O(|body|)`.

Correctness of hoisting. The key invariant to prove is: after hoisting, every execution path that reached the original instruction still computes the identical value, and no path that previously didn't reach it now observes a value that wasn't computed before.

• Invariance correctness: by construction, an instruction marked invariant has all operands either constant, defined outside the loop (hence fixed for the loop's whole execution), or defined by another invariant instruction — inductively, its computed value is the same on every iteration once its operand values stabilize (they do so trivially on iteration one, since nothing inside the loop can change them). This is a structural induction on the fixed-point marking order.
• Dominates-all-exits condition: if the instruction's block does not dominate every loop exit, there may be an execution that enters the loop, takes a path that skips the instruction, and exits — in the original program this instruction never ran on that path, but hoisting it into the preheader would force it to run on every entry to the loop, changing behavior (most critically: a program that would not have caused a division-by-zero could now crash on the hoisted division). Requiring domination of all exits guarantees the instruction was always going to execute whenever the loop is entered at all, so running it once in the preheader is behaviorally identical.
• Single reaching definition: if the destination variable is written more than once, hoisting one definition doesn't account for the other write's ordering relative to loop iterations — moving it could let a stale hoisted value survive incorrectly. Requiring a unique definition inside the loop rules this out.
• No side effects: pure hoisting is unsound for instructions with observable effects (stores, I/O, calls with side effects) because reducing "runs once per iteration" to "runs once" changes program semantics whenever the loop body executes zero or more than one time.

Strength reduction correctness. The replacement relies on the algebraic identity that if `i` is updated as `i ← i + c` each iteration and `j = a·i + b` initially, then after the update `j_new = a·(i + c) + b = (a·i + b) + a·c = j_old + a·c`. This is exactly the recurrence installed by the transformation, so `j'` and the original `j = a·i + b` are provably equal at every corresponding program point by induction on iteration count — the base case is the preheader initialization, and the inductive step is precisely the algebraic identity above.

Tradeoffs. LICM increases live ranges (a hoisted value must survive from the preheader through the whole loop), which can increase register pressure and spilling, occasionally making code slower if the hoisted value must be spilled to memory and reloaded every iteration — a real tension with register allocation that production compilers resolve heuristically (e.g., LLVM's LICM has profitability heuristics, not just legality checks). Strength reduction trades a multiply for an add plus one extra live register (the running value), which is a clear win on virtually all architectures since integer multiplication has historically cost more cycles than addition, though on modern superscalar CPUs with single-cycle multipliers the win shrinks and can occasionally be a wash if it increases register pressure enough to force a spill.

Consider this loop computing sums over an array, written in a simple three-address intermediate representation. Assume `a` is the loop-invariant array base, `stride` is a loop-invariant constant (4, for 4-byte elements), and `n` is loop-invariant (the trip count). ``` i = 0 sum = 0 L1: if i >= n goto L3 // header, back edge target t1 = i stride // address offset -- candidate for hoist? NO: i changes! t2 = a + t1 // address -- depends on t1, changes each iter t3 = load(t2) sum = sum + t3 i = i + 1 goto L1 L3: ... ``` At first glance `t1 = i stride` looks like an obvious LICM candidate because `stride` is invariant — but `i` changes every iteration, so `t1` is not loop-invariant; instead it is the textbook target for strength reduction, since `i` is a basic induction variable (`i ← i + 1`) and `t1 = i * stride` is exactly the affine form `a·i + b` with `a = stride, b = 0`.

Trace of the transformation pipeline:

Rewritten code after strength reduction: ``` i = 0 sum = 0 t1 = 0 stride // preheader: computed once L1: if i >= n goto L3 t2 = a + t1 // address computed via cheap add t3 = load(t2) sum = sum + t3 i = i + 1 t1 = t1 + stride // running update replaces multiply goto L1 L3: ... ``` The multiply `i stride` — executed `n` times in the original — now executes zero times inside the loop; it is replaced by one add per iteration (`t1 = t1 + stride`), which was already needed for pointer bumping in hand-optimized code. A final induction-variable elimination pass notices that `i` is now used only in the loop guard `i >= n`, while `t1` drives the address; if the guard can be rewritten in terms of `t1` (`t1 >= nstride`, with `nstride` hoisted to the preheader as a loop-invariant constant), then `i` itself becomes dead and is deleted entirely: ``` sum = 0 t1 = 0 bound = n * stride // preheader, invariant L1: if t1 >= bound goto L3 t2 = a + t1 t3 = load(t2) sum = sum + t3 t1 = t1 + stride goto L1 L3: ... ``` The loop body has shrunk from seven instructions (with one multiply) to five (with zero multiplies and one fewer live variable), a transformation chain that mirrors exactly what a real array-summation loop undergoes inside GCC or LLVM's `-O2` pipeline.

Loop optimization theory grew out of the earliest serious optimizing compilers, where researchers realized that redundancy elimination inside loops mattered far more than optimizing straight-line code, because loops dominate dynamic execution counts. The formalization of dominators, back edges, and reducibility was central to making these optimizations provable and automatable rather than ad hoc pattern matching.

Every mainstream optimizing compiler backend — GCC's GIMPLE loop optimizer, LLVM's `LICM` and `IndVarSimplify` passes, the JVM's C2 compiler, and V8's TurboFan — implements exactly this pipeline: dominator-based loop discovery, invariant hoisting, strength reduction, and induction-variable canonicalization. Scientific computing and numerical libraries (BLAS, image-processing kernels, physics simulations) depend on these optimizations to make naively-written nested loops run at speeds competitive with hand-tuned assembly. Just-in-time compilers for dynamic languages apply cheaper, time-budgeted variants of these same passes at runtime, since they cannot afford the full static analysis cost on every compile — a tradeoff that becomes central once you study Just-In-Time Compilation, where loop detection must happen on live, profiled bytecode rather than a fully-available static CFG. GPU kernel compilers (CUDA's `nvcc`, various shader compilers) apply loop-invariant hoisting aggressively because register and memory-bandwidth pressure inside tight parallel loops is often the dominant performance bottleneck. Even hardware-adjacent tools — vectorizing compilers, auto-parallelizers, and polyhedral loop transformation frameworks used in HPC — build directly on the natural-loop and induction-variable abstractions introduced here as their starting representation.

Ask the tutor: How would you extend the dominator-based loop-finding algorithm to correctly handle irreducible control flow introduced by computed `goto`s?