Lesson 18.1 — Loop-invariant code motion¶

Techniques: hoisting (invariance detection, speculation safety, guaranteed execution), sinking, scalar promotion of memory (register promotion) · Pebble implements: hoisting of pure computations and ★ loads (pebble-licm, E1) · Lab: none for this lesson; ./course drill licm-legality · Prerequisites: Ch 15, Lesson 15.7 (preheaders, dedicated exits, LCSSA), Ch 15, Lesson 15.1 (dominance), Ch 9 (poison and undefined behavior) · Time: 4–5 hours

A loop runs its body many times. Anything the body computes that has the same value on every iteration is wasted work after the first. In

for (long i = 0; i < n; i++)
    a[i] = a[i] + x * y;

x * y is the same in every iteration, so it can be computed once, before the loop. The question this lesson answers is when such a move is legal. x * y can always move; x / y cannot always move, because if n == 0 the original program never divides, and the moved division could divide by zero. A load *p can move only if nothing in the loop may write *p. And when a value is only needed after the loop, the opposite move — pushing the computation down past the loop — also saves work.

1. Problem and motivation¶

The problem. Given a loop \(L\) in loop-simplify form (a preheader \(P\), one latch, dedicated exits; Lesson 15.7), move computations out of \(L\) without changing the program's observable behavior: compute each loop-invariant value once in \(P\) (hoisting), compute values used only after the loop once in the exit blocks (sinking), and keep a memory location that the loop reads and writes in a register for the duration of the loop (scalar promotion). The output is the same function with fewer instructions executed per iteration. LICM is one of the most profitable passes in any optimizer: every compiler pipeline runs it several times (LLVM 23's -O2 pipeline runs licm four times: opt -passes='default<O2>' -print-pipeline-passes lists three licm<allowspeculation> and one licm<no-allowspeculation>), and pebblec -O1 runs your pebble-licm.

Hoisting (invariance and speculation safety)¶

Code motion out of loops is as old as optimizing compilers: IBM's FORTRAN H compiler moved "loop-independent" computations to a block executed before the loop [LM69], and Allen and Cocke's catalogue of optimizing transformations lists it among the basic transformations [AC72b]. The textbook formulation — find the invariant instructions by a fixed point, then move those that dominate every exit — is in Muchnick [Muchnick, §13.2]. Two refinements matter in modern IR. First, instructions that cannot trap or cause undefined behavior may be moved even when they do not dominate the exits: that is speculation, and LLVM decides it with isSafeToSpeculativelyExecute [LLVM-ValueTracking]. Second, "the same value on every iteration" for a load needs alias analysis (Ch 19); LLVM's LICM uses MemorySSA to answer it [LLVM-LICM]. Partial-redundancy elimination (Morel–Renvoise, lazy code motion; Ch 17) subsumes loop-invariant hoisting as a special case, but compilers keep a dedicated LICM pass because it also handles loads, speculation and promotion.

Sinking¶

Sinking moves an instruction whose result is used only after the loop from the loop body into the exit blocks, so that it runs once instead of once per iteration. It is the mirror image of hoisting; GCC performs it in tree-ssa-sink.cc and LLVM's LICM sinks before it hoists ("sinkRegion" then "hoistRegion") [LLVM-LICM].

Scalar promotion¶

Scalar promotion (also register promotion or store motion) replaces the loads and stores of one memory location inside a loop by a register: load it once before the loop, keep it in an SSA value, store it once at the exits. C programs access globals and through pointers so often that Cooper and Lu measured large reductions in executed loads and stores from it [CL97]. It needs everything hoisting needs plus a must-alias guarantee (every access in the loop that may touch the location is an access to exactly that location) and care about introducing stores other threads could observe.

2. Definitions and algorithms¶

Throughout, \(L\) is a natural loop with header \(h\), preheader \(P\), and \(\mathrm{Exiting}(L)\) its exiting blocks; the function is in SSA form. A run of the function is a sequence of executed instructions; an entry into \(L\) is a maximal segment of a run that starts at \(h\) coming from \(P\) and stays in \(L\).

Definition 18.1.1 (Loop-invariant instruction)

A value \(v\) is invariant in \(L\) if it is a constant, an argument, an instruction outside \(L\), or an instruction \(I\) inside \(L\) such that (i) \(I\) is pure: it has no side effects and its result depends only on its operands (arithmetic, comparisons, casts, select, getelementptr), and every operand of \(I\) is invariant in \(L\); or (ii) \(I\) is a non-volatile, non-atomic load whose address is invariant in \(L\) and no instruction of \(L\) may write the loaded location. The invariant instructions of \(L\) are the least set closed under (i)–(ii) (a fixed point over the loop's instructions).

Invariance on the lesson's loop

In a[i] = a[i] + x * y, x * y is invariant (pure, operands are arguments); the address &a[i] is not (i is a header phi, not invariant); so the load a[i] is not invariant either, and neither is the add.

Definition 18.1.2 (Safe to speculate)

An instruction \(I\) is safe to speculate at a program point if executing it there, with any operand values it can have there, cannot trap, cannot have undefined behavior and has no side effects. In LLVM IR: udiv/sdiv/urem/srem only with a constant divisor that is nonzero (and not \(-1\) for signed division), a load only from a pointer known dereferenceable and suitably aligned at that point (isSafeToSpeculativelyExecute). Poison is allowed: a speculated add nsw that overflows produces poison, which is harmless unless used.

Definition 18.1.3 (Guaranteed to execute)

An instruction \(I\) in block \(B\) of \(L\) is guaranteed to execute if, in every entry into \(L\), \(I\) executes at least once before control leaves \(L\). A sufficient condition, which this lesson and pebble-licm use: \(B\) dominates every exiting block and every latch of \(L\), and nothing that can run before \(I\) in an iteration can stop the run there: no instruction that may fail to transfer control to its successor (a call that may not return or may unwind) precedes \(I\) in \(B\) or occurs in a block of \(L\) that \(B\) does not dominate, and no block of \(L\) that \(B\) does not dominate belongs to a subloop that may run forever (one not marked mustprogress). Checking only the blocks that dominate \(B\) is not enough: in if (c) maybe_exit(); x / y; the call's block does not dominate the division's, yet it runs first.

Guaranteed to execute: top-tested vs rotated loops

In the top-tested loop for (i = 0; i < n; i++) body, the exiting block is the header, and the body does not dominate it: the body is not guaranteed to execute (it runs zero times when \(n \le 0\)). After loop rotation (Lesson 18.5) the test moves to the latch, the body dominates the latch, and it is guaranteed to execute — the entry into the loop happens only after the guard \(0 < n\) succeeded.

Hoisting (invariance and speculation safety)¶

Algorithm 18.1.4 (LICM hoisting)

Input: a function in SSA form, its loops \(L\) in loop-simplify form, the dominator tree, alias analysis.
Output: the same function with every hoistable instruction moved to the end of its loop's preheader.
Precondition: every loop to process has a preheader \(P\) (otherwise it is skipped).
Postcondition: for each processed \(L\), no instruction left in \(L\) satisfies the conditions of Theorem 18.1.10 (the fixed point is reached, Theorem 18.1.11), and the function's behavior is unchanged (Theorem 18.1.10).
Invariant: every instruction already moved to \(P\) satisfied the conditions of Theorem 18.1.10 in the program as it was when it moved; blocks are visited in dominator-tree preorder, so an instruction's operands defined in \(L\) are examined before it (Lemma 18.1.9).

function HoistAllLoops(F):
    for L in loops of F, innermost first:           # postorder of the loop forest
        if L has a preheader P:
            HoistLoop(L, P)

function HoistLoop(L, P):
    changed ← true
    while changed:                                   # a second pass only confirms the fixed point
        changed ← false
        for B in dominator-tree preorder of blocks with innermost loop L:
            for I in B, in order:
                if CanHoist(I, L, P):
                    move I to just before the terminator of P
                    if not GuaranteedToExecute(I, L): drop UB-implying flags/metadata of I
                    changed ← true

function CanHoist(I, L, P):
    if some operand of I is defined inside L: return false
    if I is pure (arithmetic, cmp, cast, select, gep): kind ← pure
    else if I is a non-volatile, non-atomic load: kind ← load
    else: return false                               # calls, stores, phis, allocas, atomics
    if kind = load and MayWriteInLoop(address of I, L): return false
    return SafeToSpeculate(I, at end of P) or GuaranteedToExecute(I, L)

function MayWriteInLoop(loc, L):
    return some instruction J in L writes memory and alias analysis
           cannot prove J does not modify loc

function GuaranteedToExecute(I, L):                  # Definition 18.1.3
    B ← block of I
    if B does not dominate every exiting block and every latch of L: return false
    for J in B before I, and in every block of L that B does not dominate:
        if J may not transfer control to its successor: return false
    if a block of L that B does not dominate lies in a subloop that is not mustprogress:
        return false
    return true

Rotation decides whether LLVM's LICM may hoist a division

Reproduce (clang 23.1.2, opt 23.1.2):

cat > div.c <<'X'
void fill(long *a, long n, long x, long y) {
  for (long i = 0; i < n; i++)
    a[i] = x / y;
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm div.c -o div.ll
opt -passes='mem2reg,loop-mssa(licm)' -S div.ll -o - | sed -n '/^for.body:/,/^$/p'
opt -passes='mem2reg,loop-rotate,loop-mssa(licm)' -S div.ll -o - | sed -n '/^for.body.lr.ph:/,/^$/p'

Output (complete):

for.body:                                         ; preds = %for.cond
  %div = sdiv i64 %x, %y
  %arrayidx = getelementptr inbounds i64, ptr %a, i64 %i.0
  store i64 %div, ptr %arrayidx, align 8
  br label %for.inc

for.body.lr.ph:                                   ; preds = %entry
  %div = sdiv i64 %x, %y
  br label %for.body

What to notice: without rotation the sdiv stays in %for.body: it is invariant (Definition 18.1.1) but neither safe to speculate (\(y\) may be 0) nor guaranteed to execute (the body does not dominate the exiting header). After loop-rotate the body dominates the latch, which is the only exiting block, so the division is guaranteed to execute and LICM moves it into the new preheader %for.body.lr.ph (Theorem 18.1.10, case (b)). LLVM's LICM requires MemorySSA, hence loop-mssa(licm).

Sinking¶

Definition 18.1.5 (Sinkable instruction)

An instruction \(I\) of \(L\) is sinkable if it is pure, its block \(B\) has innermost loop \(L\), it has no use inside \(L\), and every use outside \(L\) is a phi (in LCSSA form) in an exit block \(X\) on an edge \(E \to X\) from an exiting block \(E\) that \(B\) dominates; moreover every operand of \(I\) is defined outside \(L\) or in a block whose innermost loop is \(L\).

Algorithm 18.1.6 (LICM sinking)

Input: a loop \(L\) in loop-simplify and LCSSA form.
Output: \(L\) with every sinkable instruction replaced by copies in the exit blocks that use it.
Precondition: LCSSA form, so every use outside \(L\) is an exit-block phi.
Postcondition: no sinkable instruction remains in \(L\); behavior unchanged (Theorem 18.1.12).
Invariant: blocks are visited in post-order of the dominator tree, so an instruction is examined after all its users inside \(L\) (which could otherwise keep it in the loop) have been sunk.

function SinkLoop(L):
    for B in dominator-tree postorder of blocks with innermost loop L:
        for I in B, from last to first:
            if Sinkable(I, L):                         # Definition 18.1.5
                for each exit phi Φ = phi [I, E], ... in exit block X:
                    C ← clone of I placed at the start of X (after its phis),
                        with each operand v defined in L replaced by an LCSSA
                        phi of v in X (created if needed)
                    replace the use of I in Φ by C      # Φ is now a trivial phi
                erase I

LLVM sinks a computation used only after the loop

Reproduce (clang 23.1.2, opt 23.1.2):

cat > sink.c <<'X'
long last(const long *a, long n, long k) {
  long t = 0;
  for (long i = 0; i < n; i++)
    t = a[i] * k;
  return t;
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm sink.c -o sink.ll
opt -passes='mem2reg,loop-rotate,loop-mssa(licm)' -pass-remarks=licm -S sink.ll -o out.ll
sed -n '/^for.body:/,/^}/p' out.ll

Output (complete):

remark: <unknown>:0:0: sinking mul
remark: <unknown>:0:0: sinking load
remark: <unknown>:0:0: sinking getelementptr
for.body:                                         ; preds = %for.body.lr.ph, %for.inc
  %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i64 %i.02, 1
  %cmp = icmp slt i64 %inc, %n
  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge, !llvm.loop !5

for.cond.for.end_crit_edge:                       ; preds = %for.inc
  %i.02.lcssa = phi i64 [ %i.02, %for.inc ]
  %arrayidx.le = getelementptr inbounds i64, ptr %a, i64 %i.02.lcssa
  %0 = load i64, ptr %arrayidx.le, align 8
  %mul.le = mul nsw i64 %0, %k
  br label %for.end

for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
  %t.0.lcssa = phi i64 [ %mul.le, %for.cond.for.end_crit_edge ], [ 0, %entry ]
  ret i64 %t.0.lcssa
}

What to notice: the getelementptr, the load and the mul are only used by the exit value, so LICM sinks all three (in reverse order, Algorithm 18.1.6) into the dedicated exit block, where they run once. Their operand %i.02 reaches the exit through a new LCSSA phi %i.02.lcssa; the copies carry the suffix .le ("loop exit"). Sinking a load past the loop is legal here because nothing in the loop writes memory.

Scalar promotion¶

Definition 18.1.7 (Promotable location)

A memory location with loop-invariant address \(p\) is promotable in \(L\) if (i) every instruction of \(L\) that may access memory aliasing \(p\) is a simple (non-volatile, non-atomic) load or store whose address must-alias \(p\); (ii) a load from \(p\) in \(P\) is safe (it is guaranteed to execute in \(L\) or \(p\) is dereferenceable); and (iii) storing to \(p\) at the exits introduces no store on a path that had none, or \(p\) cannot be observed by any other thread (for example a local alloca that does not escape): a store to \(p\) is guaranteed to execute in \(L\), or \(p\) is thread-local.

Algorithm 18.1.8 (Scalar promotion)

Input: \(L\) in loop-simplify and LCSSA form, a promotable location \(p\) (Definition 18.1.7).
Output: \(L\) without loads or stores of \(p\); one load in \(P\), one store per exit block if \(L\) stores \(p\).
Precondition: Definition 18.1.7 holds.
Postcondition: the value of \(p\) in memory after the loop, and every value loaded from \(p\) in the loop, are unchanged (Theorem 18.1.13).
Invariant: at every point of every entry into \(L\), the SSA value \(\mathit{cur}\) (built by SSA construction, Ch 16) equals the contents of \(p\) in the original program.

function Promote(L, p):
    v0 ← load p            placed at the end of P
    # SSA-construct a variable "cur" whose definitions are the stores of L:
    for each store "store s, p" in L:     record s as a definition of cur, erase the store
    for each load "x = load p" in L:      replace x by the reaching definition of cur (v0 at h)
    insert the phis cur needs (at h, and at merge points inside L)       # SSA construction, Ch 16
    if L contained a store to p:
        for each exit block X:            insert "store cur_X, p" at the start of X,
                                          cur_X = the LCSSA phi of cur in X

LLVM promotes *total to a register

Reproduce (clang 23.1.2, opt 23.1.2):

cat > promo.c <<'X'
void sum(long *restrict total, const long *restrict a, long n) {
  for (long i = 0; i < n; i++)
    *total += a[i];
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm promo.c -o promo.ll
opt -passes='mem2reg,loop-rotate,loop-mssa(licm)' -pass-remarks=licm -S promo.ll -o out.ll
sed -n '/^for.body.lr.ph:/,/^}/p' out.ll

Output (complete):

remark: <unknown>:0:0: Moving accesses to memory location out of the loop
for.body.lr.ph:                                   ; preds = %entry
  %total.promoted = load i64, ptr %total, align 8
  br label %for.body

for.body:                                         ; preds = %for.body.lr.ph, %for.inc
  %0 = phi i64 [ %total.promoted, %for.body.lr.ph ], [ %add, %for.inc ]
  %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
  %arrayidx = getelementptr inbounds i64, ptr %a, i64 %i.02
  %1 = load i64, ptr %arrayidx, align 8
  %add = add nsw i64 %0, %1
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i64 %i.02, 1
  %cmp = icmp slt i64 %inc, %n
  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge, !llvm.loop !5

for.cond.for.end_crit_edge:                       ; preds = %for.inc
  %add.lcssa = phi i64 [ %add, %for.inc ]
  store i64 %add.lcssa, ptr %total, align 8
  br label %for.end

for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
  ret void
}

What to notice: one load in the preheader (%total.promoted), the header phi %0 playing the role of cur in Algorithm 18.1.8, and one store in the exit block. restrict makes the two pointers noalias, which gives condition (i) of Definition 18.1.7. Remove restrict and re-run: the remark "failed to move load with loop-invariant address because the loop may invalidate its value" appears, and the loop keeps a store i64 %add, ptr %total in every iteration, because a later load of a[i] may read *total and must see the new value.

3. Worked example¶

The running example of this lesson is one loop written in the three-address form of the licm-legality drill; X and Y are distinct arrays, a b n are defined before the loop, / is unsigned division (undefined for a zero divisor, like LLVM udiv). First the top-tested form:

P:  ; preheader
    goto H
H:  ; header
    i = phi(0 from P, i2 from the latch)
    if i < n goto B else goto X
B:
    t1 = a * b
    t2 = a / b
    t3 = a / 4
    t4 = load X[a]
    t5 = t4 + t1
    t6 = t5 + i
    if (i & 1) goto C else goto L
C:  ; runs on some iterations
    store Y[i] = t6
    goto L
L:
    i2 = i + 1
    goto H
X:  ; exit

flowchart TD
  P([P]) --> H[H]
  H --> B[B]
  H --> X[X]
  B --> C[C]
  B --> L[L]
  C --> L
  L --> H

The only exiting block is H; B, C and L do not dominate it, so nothing in B is guaranteed to execute (Definition 18.1.3). Algorithm 18.1.4 visits H, B, C, L (dominator-tree preorder):

step	instruction	operands invariant?	kind	may be written in L?	safe to speculate?	guaranteed?	action
1	`i = phi(…)`	—	phi	—	—	—	stay (never moved)
2	`t1 = a * b`	yes	pure	—	yes	no	hoist
3	`t2 = a / b`	yes	pure	—	no (\(b\) may be 0)	no	stay
4	`t3 = a / 4`	yes	pure	—	yes (nonzero constant)	no	hoist
5	`t4 = load X[a]`	yes	load	no (L stores only Y)	no (X[a] may be invalid)	no	stay
6	`t5 = t4 + t1`	no (`t4` in L)	pure	—	—	—	stay
7	`t6 = t5 + i`	no	pure	—	—	—	stay
8	`i2 = i + 1`	no	pure	—	—	—	stay
pass 2	(all remaining)	unchanged					no change → fixed point

Now rotate the loop: the header test moves to the latch (if i2 < n goto B else goto X), B becomes the header, and B dominates the only exiting block L and the latch L:

step	instruction	operands invariant?	kind	may be written in L?	safe to speculate?	guaranteed?	action
1	`t1 = a * b`	yes	pure	—	yes	yes	hoist
2	`t2 = a / b`	yes	pure	—	no	yes	hoist
3	`t3 = a / 4`	yes	pure	—	yes	yes	hoist
4	`t4 = load X[a]`	yes	load	no	no	yes	hoist
5	`t5 = t4 + t1`	yes (both hoisted already)	pure	—	yes	yes	hoist
6	`t6 = t5 + i`	no	pure	—	—	—	stay
7	`i2 = i + 1`	no	pure	—	—	—	stay
pass 2	(all remaining)	unchanged					no change → fixed point

Step 5 shows why the dominator-tree order matters: t5 becomes invariant only because t4 and t1, which dominate it, were hoisted first (Lemma 18.1.9). Both tables were produced by the course oracle (tools/course/lib/loops.py, licm_decisions) and are the golden test Licm.test_unrotated_vs_rotated in tools/course/tests/test_ch18.py.

Try it

./course drill licm-legality --seed 4 --difficulty hard, then check yourself with --solution. Medium problems mix rotated and top-tested loops; hard ones add volatile loads, calls and dereferenceable arrays.

4. Invariants and correctness¶

Hoisting (invariance and speculation safety)¶

Lemma 18.1.9 (Operands first)

If block \(B\) of \(L\) is visited in dominator-tree preorder, then when an instruction \(I \in B\) is examined, every instruction of \(L\) that defines an operand of \(I\) has already been examined, and was hoisted if it satisfied CanHoist at that moment.

Proof

In SSA form the definition \(D\) of an operand of \(I\) dominates \(I\) (a phi's operands are the exception, but phis are never hoisted and never examined as candidates). If \(D\) is in \(B\) it precedes \(I\) in \(B\). Otherwise \(D\)'s block strictly dominates \(B\), so it is an ancestor of \(B\) in the dominator tree and preorder visits it first. When \(D\) was examined, CanHoist(D) was evaluated on the current program and \(D\) moved if it held.

Theorem 18.1.10 (Correctness of hoisting)

Let \(I\) be an instruction of \(L\) such that every operand is defined outside \(L\), \(I\) is pure or a simple load whose location no instruction of \(L\) may write, and (a) \(I\) is safe to speculate at the end of \(P\), or (b) \(I\) is guaranteed to execute in \(L\). Moving \(I\) to the end of \(P\) (dropping flags and metadata that make it undefined when (a) applies but (b) does not) yields a function whose every run either behaves exactly like the original run or the original run has undefined behavior.

Proof

SSA validity. \(P\) dominates \(h\), \(h\) dominates every block of \(L\), and every use of \(I\) was dominated by \(I\), hence by \(h\) (a use outside \(L\) is reached only through \(L\)'s exits, since \(I\) dominates it); so the end of \(P\) dominates every use. The operands are defined outside \(L\) and dominate \(I\); since they are not in \(L\) and \(h\) dominates \(I\), they dominate \(h\)'s only outside predecessor \(P\)'s end (a definition outside \(L\) that dominates a block of \(L\) dominates \(h\), because every path to that block enters \(L\) through \(h\)).

Same value. Consider one entry into \(L\), preceded by exactly one execution of \(P\). The operands are SSA values defined outside \(L\): their values do not change during the entry. For a load, no instruction of \(L\) writes the location, and between the end of \(P\) and any execution of \(I\) in this entry only instructions of \(L\) run; so memory at the location is the same at the end of \(P\) as at each original execution of \(I\). A pure \(I\) (or such a load) therefore computes, at the end of \(P\), the value every original execution of \(I\) in this entry computes, and each use sees that value. The number of executions changes (one per entry instead of one per iteration), but a pure instruction or a load has no side effect, so this is unobservable.

No new behavior. The only runs that differ are those where the original did not execute \(I\) in some entry but the new program does (at the end of \(P\)). In case (a) that execution cannot trap or be undefined and has no side effects; its result is used only by the former users of \(I\), which do not execute in that entry either (they were dominated by \(I\)), except through flags/metadata we dropped. In case (b) the original executes \(I\) in every entry, with the same operand values, so if the new execution at the end of \(P\) is undefined, the original run reaches the same undefined operation later in the same entry: in LLVM's semantics the whole original run is undefined, and the new run refines it (Ch 13).

Theorem 18.1.11 (Algorithm 18.1.4 terminates at the fixed point)

Algorithm 18.1.4 terminates after at most \(k + 1\) passes over \(L\), where \(k\) is the number of instructions it hoists, and when it stops, no instruction left in \(L\) satisfies CanHoist.

Proof

Every pass that does not stop hoists at least one instruction, and an instruction leaves \(L\) at most once; so there are at most \(k\) changing passes plus one pass that changes nothing. At the end the last pass examined every instruction of \(L\) in the final program and moved none, so CanHoist is false for all of them. With the dominator-tree order the second pass never moves anything on SSA input (Lemma 18.1.9: when an instruction is examined its operands have already had their chance), so in practice \(k\) is reached in one pass plus the confirming one — exactly the two passes of the worked example.

When it breaks. Drop "guaranteed to execute" and the zero-trip loop above divides by zero. Drop the memory condition and for (…) { a[i] = i * 3; s += *p; } with p == &a[5] reads a stale *p from iteration 5 on (the test tests/ch18/lit/licm-lli.c runs exactly this program). Drop "no instruction that may not return before \(I\)" and a loop whose first statement is if (fatal) report_and_exit(); (a call that may not return, in a block that does not dominate the division) could trap on x / 0 before the call exits — the observable behavior (a clean exit) changes; bail in tests/ch18/lit/licm-lli.c runs exactly this program. Hoisting a store is never allowed by this theorem: it has a side effect.

Sinking¶

Theorem 18.1.12 (Correctness of sinking)

If \(I\) is sinkable (Definition 18.1.5), Algorithm 18.1.6 preserves the function's behavior.

Proof

Fix a run that leaves \(L\) along \(E \to X\) where \(X\) has a phi \(\Phi\) using \(I\) on that edge. Every path from \(h\) to \(E\) passes through \(B\) (the block of \(I\)): otherwise the path from the entry through \(P\) to \(h\) followed by that path would reach \(E\) avoiding \(B\), contradicting \(B \mathrel{\mathrm{dom}} E\). So in the last iteration (from the last visit of \(h\) to \(E\)), \(I\) executes, and — since \(B\)'s innermost loop is \(L\) — exactly once (two executions without passing \(h\) would lie on a cycle avoiding \(h\), i.e. in a subloop). The operands of \(I\) defined in \(L\) lie in blocks whose innermost loop is \(L\) and dominate \(B\); by the same argument each executes exactly once in the last iteration, before \(I\) (they dominate it) and not again after it (again because a second execution would need a cycle avoiding \(h\)). Hence at the exit, the latest value of each operand is the value \(I\) used in the last iteration, the clone in \(X\) — whose operands are those latest values via LCSSA phis — computes the same value \(\Phi\) read before, and \(I\) being pure, not executing it in the loop is unobservable.

Scalar promotion¶

Theorem 18.1.13 (Correctness of scalar promotion)

If \(p\) is promotable in \(L\) (Definition 18.1.7), Algorithm 18.1.8 preserves every value loaded from \(p\) in \(L\) and the contents of \(p\) after the loop, and it adds no load or store that could fault or race.

Proof sketch (full proof of the SSA construction step: Ch 16; of the thread-safety condition: [CL97, §3] and promoteLoopAccessesToScalars in [LLVM-LICM])

By (i), inside \(L\) the only instructions that read or write the bytes of \(p\) are the loads and stores of \(p\) itself; so the contents of \(p\) at any point of an entry are determined by the value at entry (loaded by \(v_0\)) and the most recent store in \(L\) — which is exactly what SSA construction's reaching definition cur denotes (the invariant of Algorithm 18.1.8, by induction on the run). Replacing each load by cur therefore preserves its value. At an exit, memory must hold cur; storing it in each exit block restores that. The new load in \(P\) is safe by (ii); the new stores execute only after an entry into \(L\) in which, by (iii), the original also stored \(p\) (so no new write becomes visible to another thread) or no other thread can observe \(p\).

5. Complexity¶

Let \(n\) be the number of instructions of the function, \(d\) the maximal loop depth, \(m_L\) the number of memory-writing instructions and \(\ell_L\) the number of loads in loop \(L\).

Technique	Time (worst)	Time (typical)	Space	Variables
Hoisting	\(O(d\,n + \sum_L \ell_L m_L \cdot c_{AA})\)	two passes per loop, \(O(n)\) plus capped alias queries	\(O(n)\)	\(c_{AA}\) = cost of one alias query
Sinking	\(O(d\,n)\) plus LCSSA repair	linear	\(O(n)\)
Scalar promotion	\(O(d\,(n + m_L \ell_L))\) plus SSA construction \(O(n \log n)\) worst	near-linear	\(O(n)\)

Proposition 18.1.14 (Cost of LICM hoisting)

Algorithm 18.1.4 examines each instruction at most \(2d\) times and performs at most \(\sum_L \ell_L\, m_L\) alias queries per pass.

Proof

An instruction belongs to the blocks of at most \(d\) nested loops; for each it is examined in at most two passes (Theorem 18.1.11 and the remark after it). CanHoist scans operands (\(O(1)\) amortized, the operand count is bounded by the instruction's size) and, for a load, asks one alias query per writing instruction of \(L\). GuaranteedToExecute is \(O(1)\) per candidate after an \(O(|L|)\) precomputation per loop: \(B\) dominates every block of a set \(S\) iff \(B\) dominates their nearest common dominator, so compute once the nearest common dominator of the exiting blocks and latches and that of the blocks containing a non-transferring instruction or a non-mustprogress subloop, and scan \(B\)'s own prefix once per block. (The reference solution simply rescans the loop's blocks for each candidate, \(O(|L|)\) each, which is fine at course sizes.)

Pathological input. A loop nest of depth \(d\) whose innermost body has \(\ell\) invariant-address loads and \(m\) stores to other arrays costs \(\Theta(d\,\ell\,m)\) alias queries: each load is re-examined in every enclosing loop against every store. LLVM avoids the quadratic term with MemorySSA (a load's clobbering access is a walk up the def chain) and caps it: after licm-mssa-optimization-cap = 100 precise clobber walks per loop it falls back to the imprecise defining access, and it attempts promotion only when the loop has at most licm-mssa-max-acc-promotion = 250 memory accesses [LLVM-LICM].

At scale. LICM is not a compile-time hotspot in LLVM; the caps exist precisely for machine-generated code with thousands of accesses per loop (the comment at the definition of licm-mssa-optimization-cap in [LLVM-LICM] documents the trade-off).

Hoisting (invariance and speculation safety)¶

Hoisting through partial-redundancy elimination [MR79; KRS92]: lazy code motion hoists loop-invariant expressions as a special case of partial redundancy, and places them as late as possible — trade-off: no speculation (a PRE-based hoist never executes a computation on a path where the original did not), so it cannot hoist x/4 out of a top-tested loop; see Ch 17.
Loop rotation first (Lesson 18.5): turning the loop into guard + do-while makes the body guaranteed to execute — trade-off: duplicates the header test.
Control-flow hoisting (LLVM's -licm-control-flow-hoisting, off by default): hoists a whole invariant conditional (the branch plus both arms) into the preheader — trade-off: more code in the preheader, needs the branch to be invariant.
Versioning for LICM (LLVM loop-versioning-licm [LLVM-LVLICM]): when alias analysis cannot prove a load invariant, create two copies of the loop guarded by a runtime no-overlap check, and hoist in the checked copy — trade-off: code size and a runtime test; see Lesson 18.5.

Sinking¶

Sinking into cold blocks (LLVM's LoopSink pass, GCC's sink pass): the reverse of hoisting — move code from the preheader into the loop when the loop is cold according to profile data — trade-off: needs profiles.
Sinking as partial dead-code elimination [KRS94b]: sinking computations to the points where they are live generalizes to partial dead code elimination — trade-off: needs a dataflow framework, catches non-loop cases.

Scalar promotion¶

Conditional promotion with a flag (GCC's execute_sm_if_changed, [GCC-LIM]): when the store is not guaranteed to execute, promote anyway and store at the exit only if a flag says the loop stored — trade-off: an extra register and branch, but no race is introduced.
Promotion across calls with interprocedural mod/ref [CL97]: promote globals in loops that call functions known not to access them — trade-off: needs interprocedural analysis (Ch 20).

7. In real compilers¶

Hoisting (invariance and speculation safety)¶

LLVM

llvm/lib/Transforms/Scalar/LICM.cpp — LICMPass::run, LoopInvariantCodeMotion::runOnLoop, llvm::hoistRegion (dominator-tree preorder walk), llvm::canSinkOrHoistInst (the memory conditions, via MemorySSA), isSafeToExecuteUnconditionally (speculation or isGuaranteedToExecute) [LLVM-LICM]; llvm/lib/Analysis/MustExecute.cpp — SimpleLoopSafetyInfo::isGuaranteedToExecute, LoopSafetyInfo::allLoopPathsLeadToBlock [LLVM-MustExec]; llvm/lib/Analysis/ValueTracking.cpp — isSafeToSpeculativelyExecute [LLVM-ValueTracking] (LLVM 23.1.2). Differences from Algorithm 18.1.4: LLVM's guaranteed-to-execute test is more precise (it discharges exits that cannot be taken in the first iteration), and it hoists invariant.start-protected loads, readonly calls without aliasing writes, and whole invariant conditions.

GCC gcc/tree-ssa-loop-im.cc — determine_max_movement computes for each statement the outermost loop it is invariant in, move_computations_worker moves it, hoist_memory_references and execute_sm do store motion (GCC 15) [GCC-LIM]. GCC moves a statement as far out as it is invariant in one step, instead of loop by loop.

Find where LLVM does it. Open llvm/lib/Transforms/Scalar/LICM.cpp, find isSafeToExecuteUnconditionally. Question: which two conditions does it try, in which order? (Quiz licm-find-safe-exec.)

GCC's loop invariant motion dump

Reproduce (gcc 14.2.0):

cat > lim.c <<'X'
void scale(long *a, long n, long x, long y) {
  for (long i = 0; i < n; i++)
    a[i] = a[i] + x * y;
}
void sum(long *restrict total, const long *restrict a, long n) {
  for (long i = 0; i < n; i++)
    *total += a[i];
}
X
gcc-14 -O2 -fno-tree-vectorize -fdump-tree-lim2-details -c lim.c -o /dev/null
grep -E -A1 "^Moving statement|^Executing store motion" lim.c.*.lim2

Output (complete):

Moving statement
_5 = x_12(D) * y_13(D);
--
Executing store motion of *total_11(D) from loop 1
Moving statement
total__lsm.16 = *total_11(D);

What to notice: GCC's lim2 pass hoists x * y (hoisting, Algorithm 18.1.4) and performs store motion on *total (scalar promotion, Algorithm 18.1.8): the promoted temporary is named total__lsm ("load/store motion").

Sinking¶

LLVM

llvm/lib/Transforms/Scalar/LICM.cpp — llvm::sinkRegion walks the loop in dominator-tree postorder; the static sink clones the instruction into exit blocks and isNotUsedOrFoldableInLoop checks the "no use in the loop" condition [LLVM-LICM] (LLVM 23.1.2).

GCC gcc/tree-ssa-sink.cc — the sink pass moves statements to the blocks where they are used, including out of loops (GCC 15) [GCC-Sink].

The real-world box for sinking is in §2 (LLVM sinks a[i] * k out of the loop).

Scalar promotion¶

LLVM

llvm/lib/Transforms/Scalar/LICM.cpp — llvm::promoteLoopAccessesToScalars (conditions (i)–(iii) of Definition 18.1.7; it uses SSAUpdater for the construction step) [LLVM-LICM] (LLVM 23.1.2).

GCC gcc/tree-ssa-loop-im.cc — hoist_memory_references, execute_sm, execute_sm_if_changed (the flag variant of §6) [GCC-LIM].

The real-world boxes for scalar promotion are in §2 (LLVM) and above (GCC's total__lsm).

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Hoisting (invariance and speculation safety)	Moves every invariant pure computation; speculation or guaranteed execution decides trapping ones; loads need alias analysis	\(O(d\,n)\) plus alias queries (Proposition 18.1.14)	Preheader code; misses what alias analysis cannot prove (fix: versioning)	Low without memory, medium with alias analysis	Every optimizing compiler, several times per pipeline (LLVM `licm`, GCC `lim`)
Sinking	Moves computations used only after the loop into the exits	\(O(d\,n)\)	Exit-block code with LCSSA phis	Low (needs LCSSA)	LLVM LICM's first phase, GCC `sink`
Scalar promotion	Removes all loads/stores of one must-aliased location	\(O(d\,(n + m\ell))\) plus SSA construction	Registers instead of memory traffic; blocked by any may-alias access or call	Medium (SSA update, thread-safety rule)	Globals and pointer-accumulated values in hot loops

Choose hoisting always; make it more effective by running loop rotation first and giving it good alias information. Choose sinking when values are computed in the loop but consumed only afterward (common after other transformations leave dead-in-loop code). Choose scalar promotion for accumulators and globals updated in loops; it is the loop-level form of what mem2reg does for whole functions.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch18.yaml`)	Drill	Flashcard tag	Exercises
Hoisting (invariance and speculation safety)	`licm-hoistable-set`, `licm-find-safe-exec`	`./course drill licm-legality`	`licm-hoist`	E1
Sinking	`licm-sink-condition`, `licm-sink-count`	`./course drill licm-legality` (the same legality conditions, dual direction; no separate drill: the decision is a single dominance test once the uses are known)	`licm-sink`	—
Scalar promotion	`promotion-conditions`, `promotion-loads`	`./course drill licm-legality` (memory rows)	`scalar-promotion`	—

Pitfall

"Invariant" is not the same as "hoistable". x / y in a loop body is invariant but not hoistable out of a loop that may run zero times, and a load from a never-written address is invariant but not hoistable if it sits under a condition and the address may be invalid. The two questions are separate: invariance (Definition 18.1.1), then safety (Definitions 18.1.2 and 18.1.3).

References¶

See the chapter references.

Lesson 18.1 — Loop-invariant code motion¶

1. Problem and motivation¶

Hoisting (invariance and speculation safety)¶

Sinking¶

Scalar promotion¶

2. Definitions and algorithms¶

Hoisting (invariance and speculation safety)¶

Sinking¶

Scalar promotion¶

3. Worked example¶

4. Invariants and correctness¶

Hoisting (invariance and speculation safety)¶

Sinking¶

Scalar promotion¶

5. Complexity¶

6. Variants and refinements¶

Hoisting (invariance and speculation safety)¶

Sinking¶

Scalar promotion¶

7. In real compilers¶

Hoisting (invariance and speculation safety)¶

Sinking¶

Scalar promotion¶

8. Comparison¶

9. Assessment¶

References¶