Introduction

Every time you write a loop, you implicitly ask: how many times must this work be done? Sometimes the answer is obvious — counting array elements clearly requires visiting each one. But sometimes a computation inside the loop does not change from one iteration to the next. Its inputs are the same, so its output is the same, every single time.

Loop-Invariant Code Motion (LICM) is the compiler technique that spots those computations and hoists them above the loop — so they run exactly once, before the first iteration, instead of once per iteration.

A computation is loop-invariant if every variable it reads is either a constant or is defined outside the loop and never modified inside it. The value of such an expression is identical on every trip around the loop. Executing it repeatedly is pure waste.

The idea sounds obvious, yet the details matter enormously. The compiler must guarantee that moving the computation is safe: it must not change program behavior, must not introduce a division by zero that would have been avoided, and must not run code on a path where it never would have reached. Those correctness conditions — combined with the performance pay-off — make LICM one of the most studied transformations in compiler theory.

Try It

The demo below shows a simple loop. Toggle each variable to mark it as changing (modified inside the loop) or fixed (constant across iterations). The compiler checks whether the expression a×b+c\text{a} \times \text{b} + \text{c} is loop-invariant and, when it is, hoists it above the loop.

<!-- Demo layout — variable toggles, loop visualization, stats -->
<div class="panel">
  <div class="vars-row">
    <span class="label">Variables:</span>
    <label class="toggle-wrap">
      <span class="var-name">a</span>
      <input type="checkbox" id="toggle-a">
      <span class="slider"></span>
      <span class="var-state" id="state-a">fixed</span>
    </label>
    <label class="toggle-wrap">
      <span class="var-name">b</span>
      <input type="checkbox" id="toggle-b">
      <span class="slider"></span>
      <span class="var-state" id="state-b">fixed</span>
    </label>
    <label class="toggle-wrap">
      <span class="var-name">c</span>
      <input type="checkbox" id="toggle-c">
      <span class="slider"></span>
      <span class="var-state" id="state-c">fixed</span>
    </label>
  </div>
  <div class="loop-area" id="loop-area">
    <!-- Loop visualization area — hoisted zone above, loop body below -->
    <div class="hoist-zone" id="hoist-zone">
      <span class="zone-label">before loop:</span>
      <div class="code-block hoisted" id="hoisted-block" style="display:none">
        <span class="keyword">let</span> t = a * b + c;
      </div>
    </div>
    <div class="loop-block">
      <div class="loop-header">
        <span class="keyword">for</span> (<span class="keyword">let</span> i = 0; i &lt; N; i++) {
      </div>
      <div class="loop-body" id="loop-body">
        <div class="code-block expr" id="expr-block">
          <span class="keyword">let</span> t = a * b + c;
        </div>
        <div class="code-block use">
          work(t);
        </div>
      </div>
      <div class="loop-footer">}</div>
    </div>
  </div>
  <div class="stats-row">
    <div class="stat-box">
      <div class="stat-val" id="eval-count">N</div>
      <div class="stat-lab">evaluations of a*b+c</div>
    </div>
    <div class="stat-box highlight" id="box-savings" style="display:none">
      <div class="stat-val" id="savings-val"></div>
      <div class="stat-lab">iterations saved</div>
    </div>
  </div>
  <div class="verdict" id="verdict">✓ All variables fixed — expression is loop-invariant, will be hoisted.</div>
</div>

/* Styles for the LICM demo */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: transparent; }
.panel { padding: .8rem 1rem; }

/* Variable toggle row */
.vars-row { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap; margin-bottom: .9rem; }
.label { font-size: .85rem; color: #555; font-weight: 600; }
.toggle-wrap { display: flex; align-items: center; gap: .35rem; cursor: pointer; user-select: none; }
.var-name { font: 700 15px ui-monospace, monospace; color: #1d3557; min-width: .6rem; }
.toggle-wrap input { display: none; }
.slider { width: 34px; height: 18px; background: #b0c4d8; border-radius: 9px; position: relative;
          transition: background .2s; flex-shrink: 0; }
.slider::after { content: ''; position: absolute; left: 2px; top: 2px; width: 14px; height: 14px;
                 border-radius: 50%; background: #fff; transition: left .2s; }
input:checked + .slider { background: #e63946; }
input:checked + .slider::after { left: 18px; }
.var-state { font-size: .75rem; color: #666; min-width: 3.5rem; }
input:checked ~ .var-state { color: #c92f3c; }

/* Loop area and code blocks */
.loop-area { border: 1.5px solid #c0cdd8; border-radius: 10px; overflow: hidden; margin-bottom: .8rem; }
.hoist-zone { background: #f0f6fb; padding: .5rem .8rem; border-bottom: 1.5px dashed #a0b8cc; min-height: 2.4rem;
              display: flex; align-items: flex-start; gap: .6rem; }
.zone-label { font-size: .72rem; color: #6a8aa0; font-weight: 600; margin-top: .25rem; white-space: nowrap; }
.loop-block { background: #fff; }
.loop-header, .loop-footer { padding: .35rem .8rem; font: 700 13px ui-monospace, monospace; color: #333; background: #f7f9fb; }
.loop-body { padding: .3rem .8rem .5rem 2rem; display: flex; flex-direction: column; gap: .25rem; }
.code-block { font: 14px ui-monospace, monospace; padding: .3rem .6rem; border-radius: 6px; }
.code-block.expr { background: #fff3cd; border: 1.5px solid #e6c040; transition: all .35s; }
.code-block.hoisted { background: #d4edda; border: 1.5px solid #4caf50; }
.code-block.use { color: #555; }
.code-block.expr.invariant { background: #d4edda; border-color: #4caf50; }
.keyword { color: #1d3557; font-weight: 700; }

/* Stats boxes */
.stats-row { display: flex; gap: .7rem; margin-bottom: .6rem; flex-wrap: wrap; }
.stat-box { background: #f0f4f8; border: 1.5px solid #c0cdd8; border-radius: 8px;
            padding: .4rem .8rem; text-align: center; min-width: 7rem; }
.stat-box.highlight { border-color: #4caf50; background: #eaf7ec; }
.stat-val { font: 700 1.5rem ui-monospace, monospace; color: #1d3557; }
.stat-lab { font-size: .72rem; color: #666; margin-top: .1rem; }
.verdict { font-size: .9rem; font-weight: 600; padding: .3rem 0; min-height: 1.4em; }
.verdict.ok { color: #0a7d33; }
.verdict.bad { color: #c92f3c; }
.verdict.info { color: #1d3557; }
@media (prefers-color-scheme: dark) {
  body { color: #dce8f0; }
  .loop-area { border-color: #3a5068; }
  .hoist-zone { background: #1e2e3d; border-color: #3a5068; }
  .zone-label { color: #7a9ab8; }
  .loop-block { background: #192634; }
  .loop-header, .loop-footer { background: #1e2e3d; color: #c8dae8; }
  .code-block.expr { background: #3d3000; border-color: #a08020; }
  .code-block.hoisted { background: #1a3a1e; border-color: #4caf50; }
  .code-block.use { color: #8aabb8; }
  .code-block.expr.invariant { background: #1a3a1e; border-color: #4caf50; }
  .keyword { color: #7ab8e0; }
  .stat-box { background: #1e2e3d; border-color: #3a5068; }
  .stat-box.highlight { border-color: #4caf50; background: #1a3a1e; }
  .stat-val { color: #b8d4e8; }
  .label { color: #9ab8c8; }
  .var-name { color: #7ab8e0; }
  .var-state { color: #9ab8c8; }
}

// Loop-Invariant Code Motion demo — toggle variables, watch expression hop out of the loop
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const N = 10; // number of loop iterations shown in the demo

// tracks whether each variable is modified inside the loop
const changing = { a: false, b: false, c: false };

function isInvariant() {
  // expression is invariant iff no variable changes inside the loop
  return !changing.a && !changing.b && !changing.c;
}

function update() {
  const inv = isInvariant();
  const exprBlock = document.getElementById('expr-block');
  const hoistedBlock = document.getElementById('hoisted-block');
  const evalCount = document.getElementById('eval-count');
  const boxSavings = document.getElementById('box-savings');
  const savingsVal = document.getElementById('savings-val');
  const verdict = document.getElementById('verdict');

  if (inv) {
    // expression is loop-invariant — hoist it above the loop
    exprBlock.style.display = 'none';
    hoistedBlock.style.display = 'block';
    evalCount.textContent = '1';
    boxSavings.style.display = 'block';
    savingsVal.textContent = i18nFmt('%n% fewer', { n: N - 1 });
    verdict.textContent = '✓ Expression hoisted! Evaluated once before the loop.';
    verdict.className = 'verdict ok';
  } else {
    // at least one variable changes — expression must stay in the loop body
    exprBlock.style.display = 'block';
    hoistedBlock.style.display = 'none';
    exprBlock.classList.remove('invariant');
    evalCount.textContent = 'N';
    boxSavings.style.display = 'none';
    verdict.textContent = '✗ At least one variable changes — expression must stay inside the loop.';
    verdict.className = 'verdict bad';
  }

  // update the displayed state label for each variable toggle
  for (const v of ['a', 'b', 'c']) {
    document.getElementById('state-' + v).textContent =
      changing[v] ? 'changes' : 'fixed';
  }
}

// attach change listeners to each variable toggle
for (const v of ['a', 'b', 'c']) {
  document.getElementById('toggle-' + v).addEventListener('change', function() {
    changing[v] = this.checked;
    update();
  });
}

update();
Result
Console

Notice what changes when hoisting fires: the expression moves out of the loop body, and the number of times it is evaluated drops from NN to 11. With a large loop count that is the difference between a millisecond and a second. Real compilers perform the same analysis — across hundreds of loops — every time they compile your code.

The Real Complexity

Unlike many questions in theoretical computer science, LICM is not an NP-hard puzzle — it is an efficiently solvable analysis problem. But it rests on machinery that took decades to formalize.

Identifying loop-invariant expressions is a fixed-point data-flow problem. Starting from the assumption that all expressions are invariant, the compiler propagates exceptions: if a variable is defined inside the loop, every expression that reads it is no longer invariant. This converges in time proportional to the number of statements times the loop nesting depth — well within polynomial time.

Proving the hoist is safe requires three conditions, all checkable in polynomial time:

  • The expression's definition must dominate all loop exits where its result is used — the compiler constructs a dominator tree in O(nlog⁡n)O(n \log n) over the control-flow graph.
  • The variable that receives the hoisted value must not be live on any path that bypasses the loop — checked via live-variable analysis, another data-flow pass.
  • The expression must not have side effects (no writes to memory that the loop body later reads, no exceptions that would change behavior if pre-executed).

Static Single Assignment (SSA) form makes the analysis clean: in SSA every variable is defined exactly once, so reading a variable's definition immediately tells you where it came from and whether a loop can modify it. Modern compilers such as GCC, LLVM/Clang, and the JVM's JIT compiler run LICM after converting to SSA — it becomes a single pass over the loop's definition sites.

The result is a transformation that is both provably correct and provably efficient — a rare combination that explains why LICM appears in essentially every production compiler. Compare that with the related question of program equivalence, which asks whether two arbitrary programs compute the same thing: that problem is undecidable. LICM sidesteps undecidability by asking only a local, syntactic question about individual expressions within a loop.

Where It Matters

The gain from hoisting one expression looks modest on paper, but multiplied across millions of loop iterations it becomes the difference between a sluggish application and a fast one.

  • Graphics and GPU shaders: the inner loop of a vertex shader often computes the same matrix–vector product on every vertex. Hoisting it to a uniform variable is the single biggest optimization a shader compiler can apply.
  • Scientific computing: tight numerical loops — finite-element solvers, molecular dynamics, signal processing — frequently recompute constants such as Δt2\Delta t^{2} or π/N\pi / N inside the hot path. LICM removes them automatically.
  • JIT-compiled languages: the Java HotSpot JVM and the V8 JavaScript engine perform LICM at runtime, hoisting expressions that only become invariant after type specialization — something a static compiler cannot see.
  • Embedded and real-time systems: on microcontrollers with no hardware multiply, hoisting a multiplication out of a 10 000-iteration loop can cut execution time enough to meet a hard deadline.
  • Auto-vectorization: LICM often runs before the vectorizer. By pulling invariant scalars out of the loop, it leaves a cleaner inner loop that maps directly onto SIMD instructions.

Understanding LICM is the gateway to a whole family of loop transformations — strength reduction, loop unrolling, and program synthesis tools that search for even faster equivalent code.

Conclusion

Loop-Invariant Code Motion is one of the most satisfying ideas in compiler engineering. The insight is small — if it does not change, do not repeat it — but the engineering required to apply it safely and efficiently is a showcase of data-flow analysis, dominator trees, and SSA form working together.

Every production compiler applies LICM automatically, so every loop you write is already a potential beneficiary. The next time your profiler shows a hot loop, ask: is there a computation in there that never changes? If so, your compiler probably already moved it — and now you know exactly how it decided that was safe.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/loop-invariant-code-motion/Content licensed under CC BY-NC 4.0.