Loop-Invariant Code Motion

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.

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 $\text{a} \times \text{b} + \text{c}$ is loop-invariant and, when it is, hoists it above the loop.

<!-- {{c_html_intro}} -->
<div class="panel">
  <div class="vars-row">
    <span class="label">{{label_vars}}</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">{{state_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">{{state_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">{{state_fixed}}</span>
    </label>
  </div>
  <div class="loop-area" id="loop-area">
    <!-- {{c_loop_area}} -->
    <div class="hoist-zone" id="hoist-zone">
      <span class="zone-label">{{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">{{label_evaluations}}</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">{{label_savings}}</div>
    </div>
  </div>
  <div class="verdict" id="verdict">{{verdict_invariant}}</div>
</div>

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

/* {{c_css_vars}} */
.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; }

/* {{c_css_loop}} */
.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; }

/* {{c_css_stats}} */
.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; }
}

// Code not found

Notice what changes when hoisting fires: the expression moves out of the loop body, and the number of times it is evaluated drops from $N$ to $1$. 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.

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(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.

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 $\Delta t^{2}$ or $\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.

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.