Lesson 18.5 — Loop restructuring: rotation, peeling, unrolling, unswitching, versioning¶

Techniques: loop rotation, loop peeling, loop unrolling (full, partial, runtime with remainder), loop unswitching (trivial and non-trivial), loop versioning (runtime checks) · Pebble implements: ★ full unrolling (pebble-unroll, E4) · Lab: — (E4's tests compare before/after with lli) · Prerequisites: Lesson 18.1 (guaranteed execution), Lesson 18.3 (trip counts), Ch 15, Lesson 15.7 (LCSSA) · Time: 5–6 hours

The transformations of this lesson do not remove computations by themselves; they change the shape of a loop so that other optimizations can. Rotation puts the exit test at the bottom so that LICM may hoist trapping code (Lesson 18.1). Peeling pulls out the first iteration so that the rest of the loop has no special case. Unrolling replicates the body so that the copies can be scheduled, vectorized or simplified together. Unswitching moves an invariant if out of the loop by making two loops. Versioning makes two loops too, but chooses between them with a runtime test that the optimizer could not decide at compile time.

1. Problem and motivation¶

The problem. Given a loop in loop-simplify and LCSSA form, produce an equivalent control-flow graph with a different loop structure: a bottom-tested loop (rotation), a loop with its first \(k\) iterations moved out (peeling), a loop whose body is replicated \(u\) times (unrolling), a loop duplicated per value of an invariant condition (unswitching), or a loop duplicated under a runtime check of an assumption (versioning). Each must preserve the program's behavior for every input and every trip count, including 0. In LLVM these are loop-rotate, peeling inside loop-unroll, loop-unroll/loop-unroll-full, simple-loop-unswitch, and LoopVersioning (used by loop-versioning-licm, loop-distribute and the vectorizer); pebblec -O1 can use your pebble-unroll.

Loop rotation¶

A for/while loop tests its condition at the top. Compilers prefer the bottom-tested form if (c) { do body while (c); } — also called loop inversion [Muchnick, §18.5] — because then the body dominates the latch, it is executed at least once whenever the loop is entered, and there is one branch per iteration instead of two. LLVM rotates almost every loop early (loop-rotate right before LICM in the pipeline) [LLVM-LoopRotate].

Loop peeling¶

Peeling executes the first \(k\) iterations (or the last) as straight-line copies before the loop. It removes first-iteration special cases (i == 0 ? x : a[i-1]), turns wrap-around variables into induction variables (Lesson 18.2), and aligns data for vectorization. It is a standard transformation of the loop-restructuring literature [Wol96]; LLVM peels when a condition becomes invariant after a few iterations, when profile data says loops usually run very few times, and to make a phi loop-invariant [LLVM-Peel].

Loop unrolling¶

Unrolling by a factor \(u\) replaces \(u\) consecutive iterations by one iteration of a body containing \(u\) copies. Full unrolling (the trip count is a small constant) removes the loop entirely; partial unrolling (the trip count is a known multiple) keeps a loop of \(\mathrm{TC}/u\) iterations; runtime unrolling (the trip count is known only at run time) adds a remainder loop for the last \(\mathrm{TC} \bmod u\) iterations. It dates back to the earliest optimizing compilers [AC72b]; its modern purpose is to expose instruction-level parallelism and to amortize the loop overhead [LLVM-Unroll]. Your ★ pebble-unroll implements full unrolling.

Loop unswitching¶

If the condition of an if inside a loop is invariant, the loop can be duplicated — one copy per outcome — with the test hoisted before the loop. A trivial unswitch needs no duplication: when one side of the invariant branch leaves the loop, the test simply moves to the preheader. Allen and Cocke list unswitching in their catalogue [AC72b]; LLVM's SimpleLoopUnswitch performs trivial unswitching always and non-trivial unswitching within a code-size budget [LLVM-Unswitch].

Loop versioning¶

When an optimization needs a fact the compiler cannot prove statically — "a and b do not overlap", "n is a multiple of 4", "stride == 1" — it can create two versions of the loop and choose at run time with a cheap check: an optimized loop under the assumption and the original as a fallback. It is the basis of runtime alias checks in vectorizers (Lesson 18.8) and of loop-versioning-licm [LLVM-LVLICM]; the checks themselves come from LoopAccessAnalysis (Lesson 18.6) [LLVM-Versioning].

2. Definitions and algorithms¶

\(L\) is a loop in loop-simplify and LCSSA form with header \(h\), preheader \(P\), latch \(\ell\), a single exit block \(X\) unless stated otherwise. A copy of a set of blocks is made with a value map \(\mu\) (original value ↦ copy); instructions in the copy use \(\mu\) of their operands where defined.

Loop rotation¶

Definition 18.5.1 (Top-tested and rotated loops)

\(L\) is top-tested if its header is its only exiting block (it contains the exit test and no other work, or the work before the test). It is rotated (bottom-tested) if its latch is an exiting block. The rotation of a top-tested while (c(i)) B is if (c(i0)) do { B } while (c(i)): a copy of the header's test in the preheader (the guard), and the header's test moved to the latch.

Algorithm 18.5.2 (Loop rotation)

Input: a top-tested loop \(L\) in loop-simplify form whose header \(h\) has one successor \(b\) in \(L\) and one exit \(X\).
Output: an equivalent loop whose latch is exiting, with a guard in the old preheader.
Precondition: \(h\) is small enough to duplicate (LLVM: a size threshold) and contains no instruction that cannot be duplicated (e.g. indirectbr targets).
Postcondition: \(b\) is the new header; the new latch ends with a copy of \(h\)'s test; every run is equivalent (Theorem 18.5.13).
Invariant: the phis of the new header \(b\) receive, from the preheader, the values \(h\) computed on the first visit, and from the latch the values \(h\) computes on later visits.

function Rotate(L):
    h ← header, b ← h's successor in L, P ← preheader, ℓ ← latch
    # 1. guard: copy h's non-phi instructions into P, with h's phis mapped to their P-values
    μ ← {phi ↦ incoming value from P for each phi of h}
    for I in h (non-phi): append Clone(I, μ) to P; μ[I] ← the clone
    replace P's "br h" by the cloned branch "br c', b, X"          # c' = μ[c]
    # 2. move the test to the bottom: ℓ's "br h" becomes a copy of h's code and branch
    append h's non-phi instructions (with phis mapped to their ℓ-values) to ℓ
    replace ℓ's "br h" by "br c, b, X"
    # 3. b is the new header: give it phis for every value of h used in the loop,
    #    [μ[v], P] and [v_ℓ, ℓ]; fix X's phis for the two incoming edges; delete h
    # 4. split the edge P → b to create the new preheader (P.lr.ph) and restore LCSSA

LLVM's loop-rotate turns a for loop into guard + do-while

Reproduce (clang 23.1.2, opt 23.1.2):

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

Output (complete):

define dso_local void @fill(ptr noundef %a, i64 noundef %n, i64 noundef %x) #0 {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %i.0 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %cmp = icmp slt i64 %i.0, %n
  br i1 %cmp, label %for.body, label %for.end

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

for.inc:                                          ; preds = %for.body
  %inc = add nsw i64 %i.0, 1
  br label %for.cond, !llvm.loop !5

for.end:                                          ; preds = %for.cond
  ret void
}
--- after loop-rotate ---
define dso_local void @fill(ptr noundef %a, i64 noundef %n, i64 noundef %x) #0 {
entry:
  %cmp1 = icmp slt i64 0, %n
  br i1 %cmp1, label %for.body.lr.ph, label %for.end

for.body.lr.ph:                                   ; preds = %entry
  br label %for.body

for.body:                                         ; preds = %for.body.lr.ph, %for.inc
  %i.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
  %arrayidx = getelementptr inbounds i64, ptr %a, i64 %i.02
  store i64 %x, ptr %arrayidx, align 8
  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
  br label %for.end

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

What to notice: the header %for.cond disappeared. Its test was copied into %entry with the phi replaced by its entry value (icmp slt i64 0, %n: the guard, step 1 of Algorithm 18.5.2), and into the latch %for.inc with the phi replaced by the incremented value (icmp slt i64 %inc, %n, step 2). %for.body became the header and gained the phi %i.02 (step 3); %for.body.lr.ph ("loop rotated preheader") is the new preheader (step 4).

Loop peeling¶

Definition 18.5.3 (Peeling)

Peeling \(k\) iterations of \(L\) produces \(k\) straight-line copies \(B_1, \dots, B_k\) of the loop body before \(L\): copy \(j\) computes iteration \(j - 1\) (header phis replaced by the values of the previous copy, or of \(P\) for \(j = 1\)), each ends with a copy of the exit test that jumps to the exit on failure, and \(L\)'s header phis take their preheader values from copy \(k\).

Algorithm 18.5.4 (Peeling k iterations)

Input: \(L\) in loop-simplify and LCSSA form, with a single latch; \(k \ge 1\).
Output: \(k\) peeled copies followed by \(L\).
Precondition: every exiting block of \(L\) can be copied (no indirectbr, no callbr).
Postcondition: every run is equivalent (Theorem 18.5.14); inside \(L\), the iteration numbers are shifted by \(k\) (\(L\)'s first iteration is the original iteration \(k\)).
Invariant: before copy \(j\) runs, the values the header phis would have in iteration \(j-1\) are available (as \(\mu_{j-1}\) of the latch operands, or preheader values for \(j = 1\)).

function Peel(L, k):
    prev ← {phi ↦ its preheader value}
    insert point ← end of P
    for j in 1..k:
        μ_j ← prev;  B_j ← Clone(blocks of L, μ_j)
        in B_j: the back edge ℓ_j → h_j goes to the next copy's header (or to h for j = k);
                exit edges go to the original exit blocks (add their phi entries from B_j)
        prev ← {phi ↦ μ_j(latch operand of phi)}
        link the insert point to h_j;  insert point ← ℓ_j's back edge
    for each header phi φ of L: set φ's preheader value to prev[φ]

clang peels the first iteration to remove i == 0

Reproduce (clang 23.1.2):

cat > peel.c <<'X'
void first(long *a, long n, long x) {
  for (long i = 0; i < n; i++)
    a[i] = (i == 0) ? x : a[i - 1] + 1;
}
X
clang-23 -O2 -fno-vectorize -mllvm -unroll-runtime=false -Rpass=loop-unroll -c peel.c -o /dev/null
clang-23 -O2 -fno-vectorize -mllvm -unroll-runtime=false -fno-discard-value-names -S -emit-llvm peel.c -o - |
  sed -n '/^define/,/^}/p'

Output (complete):

peel.c:2:3: remark: peeled loop by 1 iterations [-Rpass=loop-unroll]
    2 |   for (long i = 0; i < n; i++)
      |   ^
define dso_local void @first(ptr nofree noundef captures(none) %a, i64 noundef %n, i64 noundef %x) local_unnamed_addr #0 {
entry:
  %cmp8 = icmp sgt i64 %n, 0
  br i1 %cmp8, label %cond.end.peel, label %for.cond.cleanup

cond.end.peel:                                    ; preds = %entry
  store i64 %x, ptr %a, align 8, !tbaa !9
  %exitcond.peel.not = icmp eq i64 %n, 1
  br i1 %exitcond.peel.not, label %for.cond.cleanup, label %cond.end.preheader

cond.end.preheader:                               ; preds = %cond.end.peel
  %load_initial = load i64, ptr %a, align 8
  br label %cond.end

for.cond.cleanup:                                 ; preds = %cond.end, %cond.end.peel, %entry
  ret void

cond.end:                                         ; preds = %cond.end.preheader, %cond.end
  %store_forwarded = phi i64 [ %load_initial, %cond.end.preheader ], [ %add, %cond.end ]
  %i.09 = phi i64 [ 1, %cond.end.preheader ], [ %inc, %cond.end ]
  %add = add nsw i64 %store_forwarded, 1
  %arrayidx2 = getelementptr inbounds nuw [8 x i8], ptr %a, i64 %i.09
  store i64 %add, ptr %arrayidx2, align 8, !tbaa !9
  %inc = add nuw nsw i64 %i.09, 1
  %exitcond.not = icmp eq i64 %inc, %n
  br i1 %exitcond.not, label %for.cond.cleanup, label %cond.end, !llvm.loop !11
}

What to notice: %cond.end.peel is iteration 0 (Definition 18.5.3, \(k = 1\)): the condition i == 0 folded to true, so it just stores x, followed by the copied exit test. The remaining loop starts at i = 1 (the header phi's preheader value is the peeled copy's i + 1) and has no condition left; a later pass then forwarded a[i-1] from the previous iteration's store (%store_forwarded), which the peeling made possible.

Loop unrolling¶

Definition 18.5.5 (Unrolling)

Unrolling \(L\) by \(u \ge 2\) replaces \(u\) consecutive iterations by one iteration of a body made of \(u\) copies, with the exit tests between copies removed when the trip count is known to allow it. It is full when \(u = \mathrm{TC}\) (the loop disappears), partial when \(u\) divides a known \(\mathrm{TC}\), and runtime when \(\mathrm{TC}\) is computed at run time and a remainder loop executes the last \(\mathrm{TC} \bmod u\) iterations (placed after the unrolled loop: an epilogue; or before: a prologue).

Algorithm 18.5.6 (Full unrolling of a rotated loop — pebble-unroll)

Input: an innermost loop \(L\) in loop-simplify and LCSSA form whose latch is its only exiting block, with exit block \(X\) and constant trip count \(\mathrm{TC} \ge 1\) (Lesson 18.3).
Output: \(\mathrm{TC}\) straight-line copies of \(L\)'s blocks, no loop.
Precondition: as stated; \(\mathrm{TC} \le\) the size budget (8 by default for pebble-unroll, pebble-unroll<max=N>).
Postcondition: every run is equivalent (Theorem 18.5.7).
Invariant: after creating copy \(k\), the map \(\mu_k\) sends every value of \(L\) to the value it has in iteration \(k\); in particular \(\mu_k(\varphi) = \mu_{k-1}(\text{latch operand of } \varphi)\) for every header phi \(\varphi\).

function FullUnroll(L, TC):
    copies ← [identity map μ_0 on the original blocks]
    for k in 1..TC-1:
        μ_k ← Clone(blocks of L)                     # new blocks, new values
        for each header phi φ: μ_k[φ] ← μ_{k-1}(latch operand of φ); delete φ's clone
        remap every instruction of copy k through μ_k
    for k in 0..TC-2: replace latch_k's conditional branch by "br header_{k+1}"
    replace latch_{TC-1}'s branch by "br X"
    for each LCSSA phi ψ in X: its operand from ℓ becomes μ_{TC-1}(operand), from latch_{TC-1}
    for each header phi φ of copy 0: replace φ by its preheader value

Theorem 18.5.7 (Full unrolling preserves behavior)

If \(L\) satisfies the precondition of Algorithm 18.5.6, the unrolled code executes, on every run, the same instructions with the same operand values in the same order as \(L\) does, and \(X\)'s phis receive the same values.

Proof

Since the latch is the only exiting block and \(\mathrm{TC}\) is exact, every entry into \(L\) executes the body exactly \(\mathrm{TC}\) times, iterations \(0, \dots, \mathrm{TC} - 1\), and the latch branch goes back to the header in iterations \(0, \dots, \mathrm{TC} - 2\) and to \(X\) in iteration \(\mathrm{TC}-1\). By induction on \(k\) (the invariant): copy 0's phis are replaced by their preheader values, which are their values in iteration 0; if \(\mu_{k-1}\) gives the iteration-\((k-1)\) values, then the header phis in iteration \(k\) take their latch operands' iteration-\((k-1)\) values, which is \(\mu_k(\varphi)\), and every other instruction of copy \(k\) computes from \(\mu_k\) of its operands what the original computes in iteration \(k\) (values defined outside \(L\) are shared). The branches of the copies follow exactly the edges the original takes: latch → header of the next iteration for \(k < \mathrm{TC} - 1\), latch → \(X\) for \(k = \mathrm{TC} - 1\); branches inside the body are copied unchanged. By LCSSA, the only uses outside \(L\) are \(X\)'s phis, which read the last iteration's values: \(\mu_{\mathrm{TC}-1}\).

Algorithm 18.5.8 (Runtime unrolling by u with an epilogue remainder)

Input: a rotated loop \(L\) with a single exit at the latch, whose trip count \(T\) can be computed in the preheader from loop-invariant values (Lesson 18.3); a factor \(u \ge 2\).
Output: an unrolled loop that executes \(u\) iterations per trip and an epilogue loop for the remaining \(T \bmod u\).
Precondition: \(T\) is exact (not a maximum) and computable before the loop; for \(u\) a power of two, \(T \bmod u\) is a mask.
Postcondition: every run is equivalent (Theorem 18.5.15).
Invariant: each trip of the unrolled loop starts at an iteration number that is a multiple of \(u\) and at least \(u\) iterations remain.

function RuntimeUnroll(L, u):
    in P: T ← trip count;  R ← T mod u;  M ← T - R
    if T ≥ u: run the unrolled loop:   # u copies of the body chained without exit tests,
                                       # latch test: "executed M iterations yet?"
    if R ≠ 0: run the epilogue:        # a copy of the original loop, R iterations,
                                       # starting from the values the unrolled loop ended with
    merge the exit values of both paths in X's phis (LCSSA)

LLVM's runtime unrolling with an epilogue, and full unrolling

Reproduce (clang 23.1.2, opt 23.1.2):

cat > unr.c <<'X'
long sum(const long *a, long n) {
  long s = 0;
  for (long i = 0; i < n; i++)
    s += a[i];
  return s;
}
long sum4(const long *a) {
  long s = 0;
  for (long i = 0; i < 4; i++)
    s += a[i];
  return s;
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm unr.c -o - |
  opt -passes='mem2reg,loop-simplify,loop-rotate,instcombine' -S -o unr.ll
opt -passes='loop-unroll<runtime>' -unroll-count=4 -pass-remarks=loop-unroll -S unr.ll -o out.ll
grep -E '^define|^[a-z._0-9-]+:' out.ll | awk '/^define.*sum4/ {exit} {print}'
opt -passes=loop-unroll-full -S unr.ll -o - | sed -n '/^define.*sum4/,/^}/p'

Output (complete):

remark: <unknown>:0:0: unrolled loop by a factor of 4 with run-time trip count
remark: <unknown>:0:0: completely unrolled loop with 4 iterations
define dso_local i64 @sum(ptr noundef %a, i64 noundef %n) #0 {
entry:
for.body.lr.ph:                                   ; preds = %entry
for.body.lr.ph.new:                               ; preds = %for.body.lr.ph
for.body:                                         ; preds = %for.inc.3, %for.body.lr.ph.new
for.inc:                                          ; preds = %for.body
for.inc.1:                                        ; preds = %for.inc
for.inc.2:                                        ; preds = %for.inc.1
for.inc.3:                                        ; preds = %for.inc.2
for.cond.for.end_crit_edge.unr-lcssa:             ; preds = %for.inc.3
for.body.epil.preheader:                          ; preds = %for.cond.for.end_crit_edge.unr-lcssa, %for.body.lr.ph
for.body.epil:                                    ; preds = %for.inc.epil, %for.body.epil.preheader
for.inc.epil:                                     ; preds = %for.body.epil
for.cond.for.end_crit_edge.epilog-lcssa:          ; preds = %for.inc.epil
for.cond.for.end_crit_edge:                       ; preds = %for.cond.for.end_crit_edge.unr-lcssa, %for.cond.for.end_crit_edge.epilog-lcssa
for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
define dso_local i64 @sum4(ptr noundef %a) #0 {
entry:
  br label %for.body

for.body:                                         ; preds = %entry
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %0 = load i64, ptr %a, align 8
  br label %for.inc.1

for.inc.1:                                        ; preds = %for.inc
  %arrayidx.1 = getelementptr inbounds nuw [8 x i8], ptr %a, i64 1
  %1 = load i64, ptr %arrayidx.1, align 8
  %add.1 = add nsw i64 %0, %1
  br label %for.inc.2

for.inc.2:                                        ; preds = %for.inc.1
  %arrayidx.2 = getelementptr inbounds nuw [8 x i8], ptr %a, i64 2
  %2 = load i64, ptr %arrayidx.2, align 8
  %add.2 = add nsw i64 %add.1, %2
  br label %for.inc.3

for.inc.3:                                        ; preds = %for.inc.2
  %arrayidx.3 = getelementptr inbounds nuw [8 x i8], ptr %a, i64 3
  %3 = load i64, ptr %arrayidx.3, align 8
  %add.3 = add nsw i64 %add.2, %3
  ret i64 %add.3
}

What to notice: runtime unrolling (Algorithm 18.5.8) produced the four copies %for.inc, .1, .2, .3 in one loop body, and an epilogue loop %for.body.epil that runs n mod 4 times; %for.body.lr.ph decides whether the unrolled loop runs at all (it goes to the epilogue directly when \(n < 4\)), and the two exit paths meet in LCSSA blocks (unr-lcssa, epilog-lcssa). Full unrolling of sum4 (Algorithm 18.5.6) removed the loop entirely; the first copy's 0 + a[0] folded to a[0].

Loop unswitching¶

Definition 18.5.9 (Unswitching)

Let \(L\) contain a conditional branch on a condition \(c\) that is invariant in \(L\). Unswitching on \(c\) replaces \(L\) by if (c) L_true else L_false, where \(L_v\) is a copy of \(L\) in which the branch is replaced by an unconditional branch to its \(v\)-successor. It is trivial if one successor of the branch leaves \(L\) (or leads only to an exit): then \(L_{\text{exit side}}\) is just the exit path and only one copy of \(L\) remains.

Algorithm 18.5.10 (Unswitching)

Input: \(L\) in loop-simplify and LCSSA form; a branch on an invariant condition \(c\).
Output: the branch hoisted to the preheader, the loop duplicated if needed.
Precondition: \(c\) is available in \(P\) (defined outside \(L\), e.g. after LICM); for non-trivial unswitching, the loop's size times the number of copies is within the budget.
Postcondition: each copy is equivalent to \(L\) on the runs where it is chosen (Theorem 18.5.16).
Invariant: —

function Unswitch(L, branch on c with successors T, F):
    if F exits L (trivial):
        in P: br c, P', F'           # F' = the exit path, with LCSSA values from P
        in L: replace the branch by "br T"
    else (non-trivial):
        L_T ← L;  L_F ← Clone(L)
        in L_T: branch → br T;   in L_F: branch → br F_clone
        in P: br c, preheader(L_T), preheader(L_F)
        X's phis get an entry from each copy's exiting blocks
    simplify: blocks of each copy that became unreachable are deleted

LLVM's simple-loop-unswitch: a non-trivial and a trivial unswitch

Reproduce (clang 23.1.2, opt 23.1.2):

cat > unsw.c <<'X'
void scale(long *a, long n, long k, int neg) {
  for (long i = 0; i < n; i++) {
    if (neg)
      a[i] = -a[i] * k;
    else
      a[i] = a[i] * k;
  }
}
void until(long *a, long n, int stop) {
  for (long i = 0; i < n; i++) {
    if (stop)
      break;
    a[i] = 0;
  }
}
X
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm unsw.c -o - |
  opt -passes='mem2reg,loop-simplify,loop-rotate,loop-mssa(licm)' -S -o unsw.ll
opt -passes='simple-loop-unswitch<nontrivial>' -S unsw.ll -o - |
  grep -E '^define|^[a-z._0-9]+:|br i1 %(tobool|stop|neg)'

Output (complete):

define dso_local void @scale(ptr noundef %a, i64 noundef %n, i64 noundef %k, i32 noundef %neg) #0 {
entry:
for.body.lr.ph:                                   ; preds = %entry
  br i1 %tobool, label %for.body.lr.ph.split.us, label %for.body.lr.ph.split
for.body.lr.ph.split.us:                          ; preds = %for.body.lr.ph
for.body.us:                                      ; preds = %for.inc.us, %for.body.lr.ph.split.us
if.then.us:                                       ; preds = %for.body.us
if.end.us:                                        ; preds = %if.then.us
for.inc.us:                                       ; preds = %if.end.us
for.cond.for.end_crit_edge.split.us:              ; preds = %for.inc.us
for.body.lr.ph.split:                             ; preds = %for.body.lr.ph
for.body:                                         ; preds = %for.inc, %for.body.lr.ph.split
if.else:                                          ; preds = %for.body
if.end:                                           ; preds = %if.else
for.inc:                                          ; preds = %if.end
for.cond.for.end_crit_edge.split:                 ; preds = %for.inc
for.cond.for.end_crit_edge:                       ; preds = %for.cond.for.end_crit_edge.split.us, %for.cond.for.end_crit_edge.split
for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry
define dso_local void @until(ptr noundef %a, i64 noundef %n, i32 noundef %stop) #0 {
entry:
for.body.lr.ph:                                   ; preds = %entry
  br i1 %tobool, label %if.then, label %for.body.lr.ph.split
for.body.lr.ph.split:                             ; preds = %for.body.lr.ph
for.body:                                         ; preds = %for.inc, %for.body.lr.ph.split
if.then:                                          ; preds = %for.body.lr.ph
if.end:                                           ; preds = %for.body
for.inc:                                          ; preds = %if.end
for.cond.for.end.loopexit_crit_edge:              ; preds = %for.inc
for.end.loopexit:                                 ; preds = %for.cond.for.end.loopexit_crit_edge, %entry
for.end:                                          ; preds = %for.end.loopexit, %if.then

What to notice: in scale, the test of neg (hoisted to the preheader by LICM first — unswitching needs the condition to be available there) now selects between two loops: for.body.us contains only if.then ("us" = unswitched, the true copy) and for.body only if.else — a non-trivial unswitch. In until, if (stop) break; leaves the loop, so the test moved to the preheader and jumps straight to the exit (%if.then now has the preheader as its predecessor) — a trivial unswitch, no copy.

Loop versioning¶

Definition 18.5.11 (Versioning)

Versioning \(L\) under a runtime predicate \(p\) (computed from values available in \(P\)) replaces \(L\) by if (p) L_opt else L_orig, where \(L_{\text{orig}}\) is a copy of \(L\) and \(L_{\text{opt}}\) is \(L\), to be optimized under the assumption \(p\). Typical predicates are no-overlap checks for memory ranges accessed by the loop: for ranges \([a, a + s_a)\) and \([b, b + s_b)\), \(p = (a + s_a \le b) \lor (b + s_b \le a)\).

Algorithm 18.5.12 (Loop versioning with memory checks)

Input: \(L\) in loop-simplify and LCSSA form; groups of pointers whose ranges must not overlap, each range \([\mathit{Low}, \mathit{High})\) an expression over the preheader's values (from SCEV: the start and the end of the add recurrence over the trip count; Lesson 18.6).
Output: a check block, \(L_{\text{orig}}\) and \(L_{\text{opt}}\); \(L_{\text{opt}}\) annotated (e.g. noalias metadata) so later passes may use the assumption.
Precondition: every range bound is computable before the loop.
Postcondition: every run is equivalent to the original (Theorem 18.5.17), whatever later passes do to \(L_{\text{opt}}\) as long as they rely only on \(p\).
Invariant: —

function Version(L, pairs of ranges (A_k, B_k)):
    in a new block C before L:
        conflict ← false
        for each pair: conflict ← conflict or (A.Low < B.High and B.Low < A.High)
        br conflict, preheader(L_orig), preheader(L)
    L_orig ← Clone(L)                  # exits merged through phis in the exit blocks
    attach "no alias between A_k and B_k" metadata to L's memory accesses

LLVM's loop-versioning emits the overlap check

Reproduce (clang 23.1.2, opt 23.1.2):

cat > vers.c <<'X'
void add(long *a, long *b, long n) {
  for (long i = 0; i < n; i++)
    a[i] = a[i] + b[i];
}
X
clang-23 -O1 -fno-vectorize -fno-unroll-loops -fno-discard-value-names -S -emit-llvm vers.c -o vers.ll
opt -passes='loop-simplify,loop-versioning' -S vers.ll -o out.ll
sed -n '/^for.body.lver.check:/,/^$/p' out.ll
grep -E '^[a-z._0-9]+:' out.ll

Output (complete):

for.body.lver.check:                              ; preds = %entry
  %0 = shl i64 %n, 3
  %scevgep = getelementptr i8, ptr %a, i64 %0
  %scevgep1 = getelementptr i8, ptr %b, i64 %0
  %bound0 = icmp ult ptr %a, %scevgep1
  %bound1 = icmp ult ptr %b, %scevgep
  %found.conflict = and i1 %bound0, %bound1
  br i1 %found.conflict, label %for.body.ph.lver.orig, label %for.body.ph

entry:
for.body.lver.check:                              ; preds = %entry
for.body.ph.lver.orig:                            ; preds = %for.body.lver.check
for.body.lver.orig:                               ; preds = %for.body.lver.orig, %for.body.ph.lver.orig
for.body.ph:                                      ; preds = %for.body.lver.check
for.cond.cleanup.loopexit.loopexit:               ; preds = %for.body.lver.orig
for.cond.cleanup.loopexit.loopexit2:              ; preds = %for.body
for.cond.cleanup.loopexit:                        ; preds = %for.cond.cleanup.loopexit.loopexit2, %for.cond.cleanup.loopexit.loopexit
for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
for.body:                                         ; preds = %for.body.ph, %for.body

What to notice: the ranges are \([a, a + 8n)\) and \([b, b + 8n)\) (from the add recurrences \(\{a,+,8\}\) and \(\{b,+,8\}\) over \(n\) iterations); %found.conflict is exactly the overlap test of Algorithm 18.5.12, and on conflict control goes to the unmodified copy %for.body.lver.orig. The original %for.body becomes the optimistic version.

3. Worked example¶

The running example is the sum loop of the unrolling box, for (i = 0; i < n; i++) s += a[i], and the unswitching and versioning loops above.

Rotation. The CFG before and after (from the real-world box):

flowchart TD
  E([entry]) --> C[for.cond]
  C --> B[for.body]
  C --> X[for.end]
  B --> I[for.inc]
  I --> C

flowchart TD
  E([entry: guard 0 < n]) --> PH[for.body.lr.ph]
  E --> X[for.end]
  PH --> B[for.body]
  B --> I[for.inc: inc < n]
  I --> B
  I --> CE[for.cond.for.end_crit_edge]
  CE --> X

The test ran \(n + 1\) times before rotation (header) and runs \(1 + n\) times after (guard + latch), but the loop body now dominates the only exit and the branch per iteration went from two to one.

Runtime unrolling by 4 (Algorithm 18.5.8): which original iterations run where, for several \(n\):

\(n\)	\(R = n \bmod 4\)	\(M = n - R\)	unrolled loop runs (iterations)	epilogue runs (iterations)	total
0	—	—	guard fails: nothing	nothing	0
3	3	0	skipped (\(n < 4\))	3 (0, 1, 2)	3
4	0	4	1 trip (0–3)	skipped (\(R = 0\))	4
7	3	4	1 trip (0–3)	3 (4, 5, 6)	7
10	2	8	2 trips (0–3, 4–7)	2 (8, 9)	10

Peeling one iteration of first (Algorithm 18.5.4, \(k = 1\)): copy 1 computes iteration 0 with i = 0, so i == 0 is true and the store writes x; its copied exit test is 1 < n (from i + 1 < n); the loop's header phi for i starts at 1 and the loop's condition i == 0 is now always false — the case the real-world box shows after cleanup.

Unswitching scale (Algorithm 18.5.10, non-trivial): the branch on %tobool has successors if.then and if.else, neither exits: two copies, one per value, with the test in for.body.lr.ph. For until the branch's true successor if.then goes to the exit: trivial, one copy.

Versioning add (Algorithm 18.5.12): for a = 1000, b = 1016, n = 4 (addresses in bytes): ranges \([1000, 1032)\) and \([1016, 1048)\); \(1000 < 1048\) and \(1016 < 1032\): conflict, the original loop runs — correctly, since a[2] and b[0] are the same element. For b = 1032: \(1016 < 1032\) fails, no conflict, the optimized loop runs.

Try it

Build the chapter (./course test 18) and run opt -load-pass-plugin=<build>/lib/PebblePasses.so -passes='pebble-unroll<max=16>' -S tests/ch18/lit/unroll.ll to see your (or the reference) full unrolling on the four test loops; there is no drill for restructuring — its decisions are driven by trip counts (./course drill trip-count) and legality (Lesson 18.7).

4. Invariants and correctness¶

Loop rotation¶

Theorem 18.5.13 (Rotation preserves behavior)

For a top-tested loop while (c(i)) { B }, the rotated form if (c(i)) { do { B } while (c(i)); } executes the same sequence of test evaluations and bodies on every run.

Proof

By induction on the number \(k\) of iterations the original executes. The original evaluates \(c\) on the states \(s_0, s_1, \dots, s_k\) (where \(s_{j+1} = B(s_j)\)), finds it true on \(s_0, \dots, s_{k-1}\) and false on \(s_k\) (or never false: \(k = \infty\)). The rotated form evaluates the guard on \(s_0\): if \(k = 0\) it is false and nothing else runs — the same as the original. Otherwise it runs \(B\) on \(s_0\), then evaluates the latch test on \(s_1\), and so on: it evaluates \(c\) exactly on \(s_0, s_1, \dots, s_k\) with the same results and runs \(B\) on the same states. The header's instructions before the test are pure (Algorithm 18.5.2 duplicates them; LLVM refuses to duplicate instructions with side effects that cannot be copied), so evaluating their copy in the guard or latch instead of the header changes nothing observable.

Loop peeling¶

Theorem 18.5.14 (Peeling preserves behavior)

Algorithm 18.5.4 preserves every run: the \(k\) peeled copies execute original iterations \(0, \dots, k-1\) (as far as the original gets), and the loop executes iterations \(k, k+1, \dots\).

Proof

By induction on \(j\), copy \(j\) starts with the header-phi values of iteration \(j - 1\) (the invariant) and executes the same blocks with the same values as iteration \(j - 1\) of the original, including its exit tests: if the original exits during iteration \(j - 1\), the copy takes the same exit edge, and the exit blocks' phis receive the same values (their new entries from the copy). If the original continues, the copy's back edge leads to the next copy, or, after copy \(k\), to \(L\)'s header, whose phis now take copy \(k\)'s latch values: \(L\)'s first iteration is original iteration \(k\), and from then on \(L\) is unchanged.

Loop unrolling¶

Full unrolling is Theorem 18.5.7 (§2).

Theorem 18.5.15 (Runtime unrolling with a remainder preserves behavior)

If the trip count \(T\) of \(L\) is exact and computed before the loop, Algorithm 18.5.8 executes original iterations \(0, \dots, M-1\) in the unrolled loop and \(M, \dots, T-1\) in the epilogue, where \(M = T - (T \bmod u)\).

Proof

The unrolled loop runs only if \(T \ge u\), i.e. \(M \ge u\). Each trip executes \(u\) consecutive iterations with no exit tests between them; this is sound because the invariant says at least \(u\) iterations remain at the start of each trip (initially \(M \ge u\); after a trip, the latch test "have \(M\) iterations run?" continues only if \(M - (\text{done}) \ge u\), since done and \(M\) are multiples of \(u\)). The body copies compute each iteration's values from the previous copy's, as in Theorem 18.5.7. After \(M/u\) trips, \(R = T - M < u\) iterations remain; the epilogue is a copy of the original loop entered with the values of iteration \(M\) and runs exactly \(R\) times (it keeps the original exit test). Both paths reach \(X\), whose LCSSA phis take the value from whichever ran last. When it breaks: if \(L\) has an exit other than the latch (a break), iterations inside a trip may need to exit early; LLVM then keeps the exit branches in each copy, or refuses.

Loop unswitching¶

Theorem 18.5.16 (Unswitching preserves behavior)

If the branch condition \(c\) is invariant in \(L\) and has no side effects, each run of the unswitched code executes the same instructions as the original, apart from the evaluation of \(c\) (once, in the preheader, instead of once per iteration).

Proof

\(c\) has the same value \(v\) in every iteration of an entry into \(L\) (invariance). In the original, every execution of the branch goes to the \(v\)-successor; in \(L_v\) the branch is replaced by an unconditional branch to the same successor, so \(L_v\) executes exactly the original's instructions. The preheader test selects \(L_v\) using the same value. In the trivial case, if \(v\) selects the exit, the original leaves \(L\) at the first execution of the branch; the hoisted test leaves before entering \(L\) — equivalent only if everything the original executes in \(L\) before that first branch execution is unobservable or is also executed: LLVM requires the branch to be in the header or to be reached with no side effects on the way (the until example: if (stop) break; is the first statement), otherwise it must duplicate. Evaluating \(c\) earlier, or not at all when \(L\) would not be entered, is safe because \(c\) has no side effects and cannot trap (LLVM inserts freeze when \(c\) might be poison: branching on poison is undefined, and hoisting the branch would otherwise make a run that never reached it undefined).

Loop versioning¶

Theorem 18.5.17 (Versioning preserves behavior)

Let \(p\) be computed without side effects in the check block. If every transformation later applied to \(L_{\text{opt}}\) is correct for all inputs satisfying \(p\), then the versioned code is equivalent to \(L\) on all inputs.

Proof

On inputs with \(\neg p\) (conflict), \(L_{\text{orig}}\) — an unmodified copy of \(L\) — runs. On inputs with \(p\), \(L_{\text{opt}}\) runs, and by hypothesis it is equivalent to \(L\) on such inputs. The check itself only reads values available in \(P\). For the no-overlap predicate: if the byte ranges accessed through \(A\) and \(B\) during the loop do not overlap, no access through \(A\) aliases one through \(B\), so treating them as noalias (the metadata of Algorithm 18.5.12) is correct under \(p\). The ranges must cover every access of the loop — which is why their bounds come from the add recurrences evaluated at the start and at the trip count.

5. Complexity¶

\(S\) = size (instructions) of \(L\), \(u\) = unroll factor, \(k\) = peel count, \(m\) = number of invariant branches unswitched, \(g\) = number of pointer groups checked.

Technique	Code size after	Compile time	Run-time cost added	Variables
Loop rotation	\(S\) + size of the header (guard copy)	\(O(S)\)	none (one branch less per iteration)	\(S\)
Loop peeling	\((k + 1) S\)	\(O(kS)\)	none	\(k\)
Loop unrolling	full: \(\mathrm{TC} \cdot S\); runtime: \((u + 1) S\) + trip-count code	\(O(uS)\)	a trip-count computation and a remainder branch	\(u\), \(\mathrm{TC}\)
Loop unswitching	\(2^m S\) in the worst case	\(O(2^m S)\)	\(m\) tests before the loop	\(m\)
Loop versioning	\(2S\) + checks	\(O(S + g^2)\)	\(O(g^2)\) comparisons per entry	\(g\)

Proposition 18.5.18 (Code growth of unswitching and runtime checks)

Unswitching a loop on \(m\) independent invariant conditions (each unswitch applied to both copies of the previous ones) produces \(2^m\) copies of \(L\); versioning with pairwise checks between \(g\) pointer groups needs \(g(g-1)/2\) overlap tests.

Proof

Each non-trivial unswitch doubles the number of copies of the loop, and each copy still contains the other \(m - 1\) invariant branches, so after unswitching all of them there are \(2^m\) copies (one per assignment of truth values). Two groups conflict unless proven otherwise, so each unordered pair needs its own test: \(\binom{g}{2}\).

Pathological input. A loop body with 10 independent if (flag_k) tests on invariant flags: unrestricted non-trivial unswitching yields \(2^{10} = 1024\) loop copies. LLVM bounds it with a cost budget (unswitch-threshold, default 50, scaled down as copies accumulate) [LLVM-Unswitch]; unrolling is bounded by unroll-threshold-default = 150 (300 at -O3) instructions of unrolled body [LLVM-Unroll]; LoopAccessAnalysis gives up beyond runtime-memory-check-threshold checks (Lesson 18.6).

At scale. These thresholds are what keeps -O2 code size reasonable; the vectorizer's runtime checks are the most common versioning in practice (Lesson 18.8).

Loop rotation¶

Rotation without header duplication (loop-rotate<no-header-duplication>): rotate only when no code must be copied — trade-off: size over the LICM benefit.
Loop inversion in the front end: Clang's code generation already emits a separate condition block, and GCC's ch ("copy header") pass is GCC's rotation [GCC-CH] — trade-off: the same transformation at a different level.

Loop peeling¶

Peeling the last iteration (PeelLast in LLVM's peelLoop): removes a last-iteration special case — trade-off: needs the trip count.
Profile-guided peeling: peel the number of iterations the profile says a loop usually runs — trade-off: needs profiles, helps short loops.

Loop unrolling¶

Unroll-and-jam (loop-unroll-and-jam [LLVM-UAJ]): unroll an outer loop and fuse the inner copies, improving register reuse in loop nests — trade-off: needs dependence analysis (Lesson 18.7).
Prologue vs epilogue remainder (-unroll-runtime-epilog): the remainder before or after the unrolled loop — trade-off: alignment vs simplicity.

Loop unswitching¶

Partial unswitching: unswitch on a condition that is invariant only on some paths or for some memory state, using MemorySSA — trade-off: a more complex check.
Guard unswitching (llvm.experimental.guard / widenable conditions, Lesson 18.9) — trade-off: special IR constructs.

Loop versioning¶

loop-versioning-licm [LLVM-LVLICM]: version to make loads invariant for LICM — trade-off: a check per loop for a hoist.
Predicated SCEV checks (Lesson 18.3): version on "no wrap" or "stride = 1" assumptions — trade-off: more checks, more analyzable loops.

7. In real compilers¶

Loop rotation¶

LLVM

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp — llvm::LoopRotation and LoopRotate::rotateLoop (Algorithm 18.5.2, including header-size limits and LCSSA repair) [LLVM-LoopRotate] (LLVM 23.1.2).

GCC gcc/tree-ssa-loop-ch.cc — "copy loop headers" (GCC 15) [GCC-CH].