THE LICM hoist what does not change out of the loop
If an expression inside a loop computes the same value on every iteration — its inputs never change in the loop — then computing it each time is pure waste. Loop-invariant code motion detects such expressions and hoists them to a pre-header that runs once. A loop of n iterations that recomputed an invariant now computes it once, saving n−1 evaluations. The analysis is exactly def-use plus the loop structure: an expression is invariant if every definition it depends on lies outside the loop.
THE TECHNIQUE invariant computed n times → hoisted, computed once
An invariant c = a*b sits in a loop of n iterations. Hoisting it saves n−1 recomputations. Set n: live demo
HISTORY & CREDIT Allen & Cocke, 1971
“The loop body is where the work is; leave it alone.” — some of the work in the body does not belong there at all. If it is the same every time, it belongs before the loop. Hoisting is the compiler noticing what the loop keeps redoing for no reason. cited
1971 · Frances Allen & John Cocke — “A Catalogue of Optimizing Transformations”: loop-invariant code motion, strength reduction, and the rest of the classical loop optimizations. with · identifying the loop via dominators and back-edges (the natural loop). now · LICM is a headline pass in LLVM and GCC; often the biggest single loop win.
Invariance is a def-use fact: an expression is invariant when none of its inputs is redefined in the loop. Move it once; run it once. The loop keeps only the work that actually varies. Allen & Cocke 1971
RECOMMEND FOR I-13 recomputations saved by hoisting, computed
On the canonical compiler, an invariant a*b (=42) hoisted out of a 1000-iteration loop saves 999 recomputations:
$ i13 run licm.i13 # invariant a*b, loop of n=1000
inv = 42
saved = 999 -- computed once instead of n times
Recommend: LICM is N/A for I-13 as written — and revealingly so: i13 has no loops. Iteration is recursion, and an invariant is simply an argument you compute once and thread through the recursive calls (the std library does exactly this — sqrt passes x down unchanged). So i13 gets LICM's benefit by style, not by a pass: hoisting is manual and visible, a parameter rather than a compiler-invented pre-header. The optimization dissolves into the calling convention.