Chapter 18 exercises¶

You'll implement five loop passes as opt plugin passes in pebble/lib/Passes/Loops/: LICM (E1), SSA-based induction-variable recognition with a printer (E2), operator strength reduction (E3), and optionally ★ full unrolling (E4) and ★ bounds-check elimination for Pebble's array checks (E5). You'll also do the comparison lab in labs/ch18-loops/ (SPEC.md). Run the tests after every step:

./course test 18                                        # builds, then runs every test labelled ch18
ctest --preset linux -L '^ch18$' -R ch18.lit             # the pass tests only (macos preset on a Mac)
build/<preset>/bin/pebble-lit -v tests/ch18/lit/licm-hoist.ll   # one lit file, verbose

Before you start, every ch18 test fails. The pass tests fail with unknown pass name 'pebble-licm' (and so on), because no pass is registered yet, and the lab tests stop with TODO(ch18): …. That's expected.

How to write a pass. Put each pass in any .cpp file under pebble/lib/Passes/Loops/ (read its README.md), as a new-pass-manager function pass (run(Function &, FunctionAnalysisManager &), Ch 12); get loops from FAM.getResult<LoopAnalysis>(F) and walk them yourself. Register it next to its definition with PEBBLE_FUNCTION_PASS("pebble-licm", YourPass); (an analysis with PEBBLE_FUNCTION_ANALYSIS) from pebble/Passes/Registry.h. Every file in the directory is compiled into the course plugin PebblePasses and into pebblec. Try a pass with:

opt -load-pass-plugin=build/linux/lib/PebblePasses.so -passes=pebble-licm -S input.ll

To make your own inputs from C: clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm f.c -o f.O0.ll, then opt -passes='mem2reg,loop-simplify' -S f.O0.ll -o f.ll (add loop-rotate for rotated loops, lcssa for E4).

Common to E1–E5: each pass keeps the module valid (opt -passes=verify), returns PreservedAnalyses::all() when it changed nothing, and preserves the observable behavior of every function: the *-lli tests run programs under lli before and after and diff the output.

Stuck? Work through the hints in order. The reference solutions are in solutions/pebble/lib/Passes/Loops/. Only look at them after you've passed the tests, or after an honest hour.

E1 · pebble-licm: hoist loop-invariant code¶

Contract: a function pass registered as pebble-licm. Tests: tests/ch18/lit/licm-hoist.ll, licm-speculation.ll, licm-memory.ll (★ R4), licm-must-not.ll, licm-lli.c (all in ch18.lit)

Implement LICM hoisting, Algorithm 18.1.4 of Lesson 18.1: for every loop, innermost first, move each loop-invariant instruction that is safe to move to the end of the loop's preheader. You choose the data structures. Lesson 18.1 §7 reads LLVM's hoistRegion, which does the same with MemorySSA.

Requirements:

R1. Which loops, in which order. Process every loop that has a preheader, innermost first, so that an instruction hoisted out of an inner loop can then be hoisted out of the outer one (it lands in the outermost preheader it is invariant in). Visit the blocks whose innermost loop is L in dominator-tree order, so operands are hoisted before their users (Lemma 18.1.9). Loops without a preheader are left alone.
R2. Invariance. An instruction is invariant in L if every operand is a constant, an argument, or defined outside L (after the hoists done so far).
R3. Which instructions move. Pure computations: binary operators, casts, comparisons, select, getelementptr. Never calls (even readnone ones), stores, phis, allocas, volatile or atomic accesses.
R4 ★. Loads. A non-volatile, non-atomic load moves if, in addition, no instruction of L may write the loaded location (ask alias analysis, AAManager: getModRefInfo of every instruction that may write memory; any call that may write memory blocks it).
R5. Safety. An invariant instruction moves only if it is safe to speculate (isSafeToSpeculativelyExecute, Definition 18.1.2: e.g. division by a nonzero constant, a load from a dereferenceable and aligned pointer) or guaranteed to execute (Definition 18.1.3): its block dominates every exiting block and every latch, no instruction that may fail to transfer control to its successor (isGuaranteedToTransferExecutionToSuccessor) precedes it in its block or occurs in a loop block its block does not dominate (such a block can run before it), and no such block lies in a subloop that may run forever (isMustProgress). When you hoist speculatively, drop metadata and attributes that would make the moved instruction immediate UB (dropUBImplyingAttrsAndMetadata).
R6. Complexity. One pass over each loop in dominator order suffices for pure code (Theorem 18.1.11); total work \(O(\text{instructions} \times \text{depth})\) plus the alias queries.

What the tests check:

Test	Asserts
`licm-hoist.ll`	chains of invariant pure instructions, invariant GEPs and compares move; a nest's doubly-invariant value lands in the outer preheader, a value depending on the outer IV in the inner preheader; the loop-variant `select` stays; the output verifies (R1–R3)
`licm-speculation.ll`	`x / y` stays in a top-tested loop but moves in the rotated one; `x / 4` moves in both; a division in a conditionally executed block stays; a division after a call that may not return stays, also when the call sits in a side block that does not dominate it, or after a subloop that may not terminate (R5)
`licm-memory.ll` ★	a load moves when the stores go through a `noalias` pointer, stays without `noalias`, stays when volatile or after an unknown call, stays when conditional from a possibly invalid pointer, and moves from a `dereferenceable` pointer (R4, R5)
`licm-must-not.ll`	calls, stores, phis and instructions with an in-loop operand stay (R3)
`licm-lli.c`	the program prints the same results before and after, unrotated and rotated, including a zero-trip loop whose hoisted division would raise SIGFPE; something really moved (R5)

Hint 1 — where to start

Start with R1–R3 and R5 for pure instructions only, on licm-hoist.ll. LI.getLoopsInPreorder() reversed gives innermost first; DT.getNode(L.getHeader()) and a preorder walk of the dominator subtree restricted to LI.getLoopFor(BB) == &L gives the visiting order. Move with I.moveBefore(Preheader->getTerminator()).

Hint 2 — the key idea

The two safety conditions are alternatives: speculation safety is a property of the instruction alone, guaranteed execution a property of its position. A rotated loop's header dominates its latch (the only exiting block), which is why x / y moves only after loop-rotate — look at the two tables of Lesson 18.1 §3.

Hint 3 — a design sketch

hoistLoop(L): compute the exiting blocks and latches once; for each candidate I in order: invariant(I) && movable(I) && (isSafeToSpeculativelyExecute(&I, Pre->getTerminator(), …) || guaranteed(I)) → move. For loads (R4), collect the loop's writing instructions once and ask AA.getModRefInfo(W, MemoryLocation::get(Load)). The common bugs the tests catch: forgetting that a call before the instruction breaks "guaranteed to execute", including a call in a side block (if (c) f();) that does not dominate it.

Done when: ./course test 18 shows the four licm-* tests passing (licm-memory.ll only if you did ★ R4).

E2 · pebble-iv and print: induction variables by SCCs¶

Contract: a function analysis registered as pebble-iv and a printer pass registered as print<pebble-iv> that prints to stderr in the format below. Tests: tests/ch18/lit/iv-corpus.test, iv-classes.ll, iv-scev.test; the lab test ivs-compare.test

Implement Algorithm 18.2.6 of Lesson 18.2: find the strongly connected components of each loop's SSA graph (Tarjan, [Tar72]) and classify every integer value by the classes of Definition 18.2.5, with chains of recurrences (Lesson 18.3, Definition 18.3.1) as the result. E3 uses your analysis.

Output format. For each function, a line pebble-iv: function @NAME; then for each loop, in the order of the loop headers in the function's block list, loop %HEADER (depth D); then, indented by two spaces and in instruction order (header phis first), one line per classified integer value whose innermost loop is that loop:

pebble-iv: function @f
loop %for.cond (depth 1)
  %i.0: linear {0,+,1}
  %s.0: polynomial {0,+,0,+,1}
  %g: geometric {1,*,2}
  %w: wrap-around
  %p: periodic 2
  %m: monotonic increasing

Values are spelled as LLVM prints operands (%name, %0).
A CR coefficient is an affine combination of loop-invariant values: terms COEFF*%v sorted by the operand spelling, coefficient 1 omitted, -%v for −1, the constant last and omitted when 0 (unless it is the only part), and a negative term or constant joined with - (e.g. %n - 1, 2*%a + %b + 3).
Constants are signed values of the value's bit width, computed modulo \(2^w\) (an i8 start of 250 prints as -6).
Geometric CRs print as {START,*,RATIO}; periodic values print their period; monotonic values print increasing or decreasing; wrap-around values print no CR.
A loop that is not in loop-simplify form prints loop %HEADER (depth D): not in loop-simplify form and nothing else.
Values that fit no class are not printed.

Requirements:

R1. SCCs. Tarjan's algorithm over the SSA graph restricted to the loop's instructions, edges from a use to its operands (Definition 18.2.4); classify SCCs in completion order (Lemma 18.2.7).
R2. Linear and polynomial. A header phi whose SCC is a chain phi → ± terms → phi whose other operands are loop-invariant or already-classified CRs is {start,+,E} with E the sum of the terms' CRs (Lemma 18.3.5's prepend); the non-phi members get their CRs from the phi's. Degree ≥ 2 is polynomial.
R3. Combinations. A trivial SCC x = a op b with op ∈ {add, sub, mul by an invariant or constant, shl by a constant} of classified operands gets the CR of Lemma 18.3.3 (and the product of Lemma 18.3.4 for two CRs, which is polynomial).
R4. Geometric. A header phi whose chain multiplies by a constant ratio r ≠ 0, 1 (and adds nothing) is {start,*,r}.
R5. Wrap-around and periodic. A trivial header phi phi(init, v) with v classified is wrap-around — unless init equals v's value one iteration before the first (then it is linear, Lemma 18.2.8). An SCC of k header phis that only rotate values among themselves is periodic k.
R6. Monotonic. An SCC that only adds non-negative (or only non-positive) constants, some conditionally, and whose phis merge only values of the SCC (apart from the header phi's start), is monotonic increasing (decreasing). A phi operand from outside the SCC (phi [%a, %then], [0, %else]) resets the value: not monotonic.
R7. Agreement. Every linear or polynomial CR you print must equal LLVM ScalarEvolution's add recurrence for the same value whenever SCEV's is affine in named values (iv-scev.test).

What the tests check:

Test	Asserts
`iv-corpus.test`	the exact output on the lab corpus `labs/ch18-loops/corpus/ivs.ll`: every class, symbolic starts and steps, nested loops (R1–R6)
`iv-classes.ll`	edge cases: `i8`/`i32` widths with wrapping constants, a wrap-around phi whose first value fits (linear), subtraction with the IV on the right, multiplication by an invariant, a loop without a preheader (format), a conditional reset that is not monotonic
`iv-scev.test`, lab `ivs-compare.test`	agreement with ScalarEvolution on the lab corpora; every classic IV of the lab is also reported by you (R7)

Hint 1 — where to start

Write the printer and the linear case first (header phi + additions of constants) and diff your output against the first function of iv-corpus.test. Represent a CR as a vector of affine coefficients over std::map<std::string, std::pair<Value *, APInt>> keyed by spelling — the map order is the required term order.

Hint 2 — the key idea

Tarjan's completion order is what makes one pass enough: when you classify an SCC, every operand outside it is already classified (or is not an IV, and then nothing that uses it is one either). Inside a header SCC, walk from the latch value back to the phi and collect what is added along the way.

Hint 3 — a design sketch

LoopClassifier(L): build the node set (integer instructions of blocks whose innermost loop is L), run Tarjan, then dispatch per SCC: trivial non-phi → combine; trivial phi → wrap-around check; one phi + chain → recurrence; several phis rotating → periodic; otherwise → monotonic check. The common bug: counting operands that are outside the SCC as part of the chain (they are the terms E, not the recurrence).

Done when: ./course test 18 shows iv-corpus.test, iv-classes.ll and iv-scev.test passing.

E3 · pebble-osr: operator strength reduction¶

Contract: a function pass registered as pebble-osr. Tests: tests/ch18/lit/osr.ll, osr-lli.test

Implement the multiplicative case of OSR, Algorithm 18.4.6 of Lesson 18.4, using your E2 analysis: every mul X, C, mul C, X or shl X, k inside loop L, where X is a linear induction variable of L with CR \(\{s,+,t\}\) and C is a constant or a value defined outside L, becomes a new induction variable.

Requirements:

R1. The new IV. In the preheader compute r0 = C·s and rstep = C·t (expanded from the affine start and step); in the header a phi r = phi [r0, preheader], [r.next, latch]; in the latch r.next = r + rstep. Its CR is \(\{C s,+,C t\}\) (Theorem 18.4.7).
R2. Uses. Uses of the multiplication inside L use r (count an exit block's LCSSA phi as a use inside L: its operand is used on the edge leaving L). Other uses outside L may keep the multiplication; replacing them by r would also be correct, because the multiplication dominates them, so it ran in the loop's last iteration, when r held the same value (r.next only reaches r through the back edge). Erase the multiplication when nothing uses it.
R3. Must not transform. A multiplier computed in the loop (for example a load), a product of two induction variables (polynomial), or a loop not in loop-simplify form.
R4. Flags. The new additions carry no nsw/nuw (they compute the product modulo \(2^N\), which refines a multiplication that may have been poison).

What the tests check:

Test	Asserts
`osr.ll`	`i * 4` with `i = {0,+,1}` becomes an IV `{0,+,4}` and the multiplication is gone; a symbolic multiplier `w * i` with `i = {1,+,2}` gets its start and step computed once in the preheader; the must-not cases stay; the output verifies (R1–R4)
`osr-lli.test`	the lab corpus `sr.ll` prints the same results after `pebble-osr` and after `pebble-licm,pebble-osr`, and the multiplications are gone (R1, R2)

Hint 1 — where to start

Get the IVs from FAM.getResult<YourIVAnalysis>(F) before changing anything, collect the candidate multiplications, then transform. An IRBuilder positioned at the preheader's terminator expands C·s from your affine CR coefficient.

Hint 2 — the key idea

You never need Reduce's recursion for the multiplicative case: the CR of the product is known in closed form (\(C \cdot \{s,+,t\} = \{Cs,+,Ct\}\)), so building the phi and its increment directly is equivalent to cloning the SCC (Lesson 18.4 §3 shows both).

Hint 3 — a design sketch

For each candidate: check X's class and C's invariance, build r0/rstep in the preheader, r at the top of the header (phi), r.next before the latch's terminator, then replaceUsesWithIf(r, inside L). The common bugs the tests catch: seeding r with C·t instead of C·s, and multiplying by k instead of \(2^k\) for shl X, k.

Done when: ./course test 18 shows osr.ll and osr-lli.test passing.

E4 ★ · pebble-unroll: full unrolling¶

Contract: a function pass registered as pebble-unroll, with the optional parameter pebble-unroll<max=N> (default 8); any other parameter is rejected, so that opt reports unknown pass name 'pebble-unroll<bogus>'. Tests: tests/ch18/lit/unroll.ll, unroll-lli.c

Implement Algorithm 18.5.6 of Lesson 18.5: replace an innermost loop whose constant trip count TC ≤ max by TC straight-line copies of its body.

Requirements:

R1. Accepted loops. Innermost, loop-simplify form, one exit block, the latch is the only exiting block (a rotated loop), and ScalarEvolution's exact small constant trip count (getSmallConstantTripCount) is between 1 and max. Leave every other loop alone.
R2. Construction. Put the loop into LCSSA form first (formLCSSA). Copy 0 is the original body; in copy k ≥ 1, each header phi is replaced by the value its latch operand had in copy k − 1; copy k's latch branches unconditionally to copy k + 1's header and the last copy's latch to the exit block; the exit block's LCSSA phis take the last copy's values; the original header phis are replaced by their preheader values.
R3. Result. No conditional branch of the loop and no back edge remain; the function computes the same values (Theorem 18.5.7).
R4. Parameter. Register with PEBBLE_REGISTER_PASSES and R.functionPass<YourPass>("pebble-unroll", parser), where the parser accepts "" and max=N (N > 0) and returns std::nullopt otherwise.

What the tests check:

Test	Asserts
`unroll.ll`	trip count 4: four copies of the store and no conditional branch; the exit value flows out of the LCSSA phi from the last copy; trip count 12 stays by default and is unrolled with `max=16`; non-innermost and unknown-trip-count loops stay; `pebble-unroll<bogus>` is rejected; the output verifies (R1–R4)
`unroll-lli.c`	small constant-trip loops with loop-carried values (a Fibonacci pair, a swap) and a value used after the loop print the same results after unrolling (R2, R3)

Hint 1 — where to start

CloneBasicBlock with a ValueToValueMapTy per copy, then remapInstructionsInBlocks. Before cloning copy k, seed the map with header phi ↦ (copy k − 1's value of its latch operand).

Hint 2 — the key idea

A rotated loop's exit test is at the latch and fails exactly TC − 1 times, so every copy's conditional branch is known: "continue" for copies 0..TC−2 and "exit" for the last. That is why R1 requires a rotated loop.

Hint 3 — a design sketch

Collect the jobs (loops and their trip counts) before changing anything — unrolling invalidates LoopInfo. Per job: formLCSSA, clone TC − 1 times, rewire the latches, fix the exit phis, replace the original phis, delete the original back edge. Return PreservedAnalyses::none(). The common bug: forgetting to update the exit block's phis, so the value after the loop comes from copy 0.

Done when: ./course test 18 shows unroll.ll and unroll-lli.c passing.

E5 ★ · pebble-bce: remove Pebble's provably redundant bounds checks¶

Contract: a function pass registered as pebble-bce. Tests: tests/ch18/lit/bce.ll, bce-lli.c

Pebble's assert c, bounds is lowered by pebblec --emit=llvm to %c = icmp ult i64 %idx, LEN (or icmp uge with the successors swapped) and a conditional branch whose failing successor calls pebble_trap(i32 3, …) and ends in unreachable. Implement Algorithm 18.9.3 of Lesson 18.9: remove the checks that can never fail.

Requirements:

R1. Recognize exactly the branches on icmp ult idx, len (or uge, swapped) whose failing successor is a block containing a call to pebble_trap with first argument 3 and ending in unreachable.
R2. Decide with ScalarEvolution: the check is redundant if SE.isKnownPredicateAt(ICMP_ULT, getSCEV(idx), getSCEV(len), branch) holds (Theorem 18.9.2's range argument, including the dominating loop guard).
R3. Rewrite a redundant check into an unconditional branch to the success successor, remove the block from the trap block's predecessors, and delete the trap block if it has no predecessors left. Make all queries before the first rewrite.
R4. Keep every check that can fail, so that a program that trapped still traps at the same point.

What the tests check:

Test	Asserts
`bce.ll`	`sum4` (`for i in 0..4: xs[i]`, length 4) and `next3` (`xs[i + 1]` for `i in 0..3`) lose their checks; `sum5` (`0..5`) and `sumn` (`0..n`) keep them; the program prints the same output and still traps with `pebble: trap: kind 3` (R1–R4)
`bce-lli.c`	adversarial ranges — `a[i - 1]` from 0, `a[i + 1]` up to the last index, a step of 2 that overshoots, a decreasing loop down to −1, a guard `n <= 5` on a length-4 array, `i <= 4`, unsigned and 32-bit counters, `len - 1`: every check that can fail stays and traps at the same line under `lli`, unrotated and rotated; three provably safe checks disappear (R2, R4)

Hint 1 — where to start

Lower a small Pebble program with a loop over an array (pebblec --emit=llvm) and clean it with opt -passes='mem2reg,instsimplify,simplifycfg' to see the exact shape of a check; bce.ll was made this way.

Hint 2 — the key idea

You do not need to compute ranges yourself: isKnownPredicateAt combines the index's add recurrence, its no-wrap flags and the conditions of dominating branches (the loop guard i < n). The only reasoning left to you is recognizing the check and editing the CFG safely.

Hint 3 — a design sketch

Pass 1: collect redundant branches. Pass 2: for each, Trap->removePredecessor(BB), create BranchInst::Create(Ok, Br), erase Br (and the compare if unused), and DeleteDeadBlock(Trap) if pred_empty(Trap). The common bug: deleting a trap block shared by several checks while some are kept.

Done when: ./course test 18 shows bce.ll and bce-lli.c passing.

Lab · Classic vs SSA IVs, classic SR vs OSR, GCD vs Banerjee¶

Spec: labs/ch18-loops/SPEC.md · Your code: labs/ch18-loops/src/ (any files you like) · Tests: ch18.lab.*

Read the spec: it gives the requirements, the contract (include/lab18/Loops.h), the input and output formats, what the tests check and the milestones. Then compare your measurements with Lesson 18.2 §3, Lesson 18.4 §3 and Lesson 18.6 §3.

★ Optional: the strong SIV test as a third column of ch18-loops dep (SPEC.md, stretch goals).