Chapter 13 exercises¶
You'll write five LLVM IR passes in pebble/lib/Passes/LocalOpt/: constant folding (E1), a flag-aware peephole engine (E2), local value numbering with memory versions (E3), dead-code elimination (E4) and rank-based reassociation (E5). They run as opt passes from the course plugin PebblePasses and inside pebblec. The comparison lab (labs/ch13-peephole/SPEC.md) adds a DSL-driven engine, a bounded exhaustive rewrite checker and an optional superoptimizer. Run the tests after every step:
./course test 13 # builds, then runs every test labelled ch13
ctest --preset linux -L '^ch13$' --output-on-failure # the same through ctest (macos: --preset macos)
opt -load-pass-plugin=build/<preset>/lib/PebblePasses.so -passes=pebble-constfold -S tests/ch13/lit/constfold-int.ll
Before you start, every ch13 test fails with unknown pass name 'pebble-constfold' (and the like) or, for the lab tools, TODO(ch13): …. That's expected: each message names the exercise or lab part that fixes it.
The contract is the pipeline name and the observable IR. There is no header to implement: each exercise below specifies what opt -passes=<name> must do to a function, and the lit tests in tests/ch13/lit/ check exactly that with FileCheck. Write the passes in any .cpp files in pebble/lib/Passes/LocalOpt/ (any names, any helpers; every *.cpp there is compiled) and register each next to its definition:
#include "pebble/Passes/Registry.h"
PEBBLE_FUNCTION_PASS("pebble-dce", YourDCEPass); // no parameters
PEBBLE_REGISTER_PASSES(my_peephole) { // with <parameters>
R.functionPass<PeepholePass>("pebble-peephole", parseParams);
}
Ch13Provided.cpp is provided: it defines print<pebble-icount>, which prints pebble-icount: @<function> <instructions> per defined function (the pipeline test uses it). The FOUNDATION page of the course explains the registry; Ch 12 explains passes, parameters and lit tests.
Stuck? Work through the hints in order. The reference solution is in solutions/pebble/lib/Passes/LocalOpt/, but only look at it after you've passed the tests, or after an honest hour.
Common rules for all five passes.
- C1. Each is a function pass that works on every defined function and returns PreservedAnalyses::all() when it changed nothing, and preserves at least the CFG analyses otherwise (none of them changes the CFG).
- C2. Scalars only: vector-typed instructions are left alone.
- C3. Every transformation must be a refinement (Definition 13.8.2): never introduce UB or poison where the input had none. The course tests include must-not-transform cases for each pass, and tests/ch13/lit/equivalence.c runs each pass (and the whole local pipeline) on a C program and compares its output under lli with the unoptimized program.
- C4. Don't call LLVM's own implementation of the technique (ConstantFoldInstruction, simplifyInstruction, InstCombine, EarlyCSE, Reassociate, isInstructionTriviallyDead …). PatternMatch, APInt, APFloat, IRBuilder, ConstantFold*Operands (in E3 only) and the Instruction API are fine.
E1 · pebble-constfold: constant folding from the semantics¶
Lesson: 13.1 (Algorithm 13.1.7, Theorem 13.1.12, Proposition 13.1.14), poison rules from 13.8
Tests: constfold-int.ll, constfold-ub.ll, constfold-fp.ll, equivalence.c, pipeline-icount.ll (@fold)
Replace every instruction whose operands are all constants (or poison) by the constant it computes, computing with APInt and APFloat yourself, and repeat until nothing changes.
Requirements:
- E1-R1. Folds the integer binary operators add sub mul shl lshr ashr and or xor udiv sdiv urem srem, icmp (all ten predicates), trunc, zext, sext and select, on scalar integers of any width, with two's-complement results at the instruction's width.
- E1-R2. Poison. A poison operand makes the result poison (for select: only a poison condition does; a constant condition picks its arm, even if the other arm is poison). A violated poison-generating flag folds to poison: nsw/nuw on add sub mul shl when the exact result does not fit; exact on udiv sdiv lshr ashr when a nonzero remainder or a set bit would be discarded; disjoint on or when the operands share a set bit; samesign on icmp when the operands have different signs; nneg on zext of a negative value; nuw/nsw on trunc when the value does not survive the round trip. A shift amount \(\ge N\) folds to poison.
- E1-R3. Immediate UB is never folded: udiv sdiv urem srem by zero or by poison, and sdiv/srem of INT_MIN by \(-1\), stay in the IR (a poison dividend with a nonzero constant divisor folds to poison). Removing the UB would be a refinement, but hiding it silently is bad engineering (Lesson 13.1 §4).
- E1-R4. Floating point: fadd fsub fmul fdiv fneg fcmp on scalar ConstantFP operands, in round-to-nearest-even, exactly as IEEE 754 prescribes (signed zeros and NaNs included); frem and calls are not folded. With nnan (ninf), a NaN (infinite) operand or result folds to poison.
- E1-R5. Functions with the strictfp attribute are left untouched (their FP operations depend on the dynamic rounding mode).
- E1-R6. Folding reaches a fixed point: after folding an instruction, its users are re-examined (a worklist); folded instructions are erased. \(O(n + u)\) folds and re-examinations for \(n\) instructions and \(u\) uses (Theorem 13.1.13).
What the tests check: constfold-int.ll: each operator, each flag (folded to poison when violated, to the value otherwise), oversized shifts, casts with flags, select with constant and poison conditions, and chains that fold completely. constfold-ub.ll: division by zero, by poison and INT_MIN / -1 survive; a strictfp function is unchanged. constfold-fp.ll: signed zeros (\(-0.0 + (+0.0) = +0.0\), while \(-0.0 + (-0.0)\) stays \(-0.0\)), a NaN result, a float sum that must round to nearest-even, overflow to \(+\infty\), nnan/ninf results folded to poison, ordered and unordered fcmp with a NaN, fneg, and fmul x, 0.0 left alone because x is not a constant.
Hint 1 — where to start
Write Value *fold(Instruction &) that returns the folded constant or nullptr, one small function per instruction class (integer binary, icmp, casts, select, FP). Start with add without flags and the worklist loop; the tests are ordered roughly from easy to hard within each file.
Hint 2 — the key idea
Compute every flag condition from the exact result: APInt::sadd_ov, uadd_ov, smul_ov and friends tell you whether the mathematical result fits. For shl, shift and shift back (lshr for nuw, ashr for nsw) and compare with the input. The pitfall list of Proposition 13.1.14 is the FP checklist: APFloat::add(…, rmNearestTiesToEven) already rounds correctly; your job is not to "simplify" anything on the way.
Hint 3 — a design sketch
A SetVector<Instruction *> seeded with all instructions; pop, fold, and on success push the users, replaceAllUsesWith, remove the instruction from the worklist and erase it. Check F.hasFnAttribute(Attribute::StrictFP) before anything else. The common bugs the tests catch: folding sdiv i8 -128, -1, treating select with a poison false arm as poison, and exact shifts (the discarded bits are the low amount bits).
Done when: ctest --preset linux -L '^ch13$' -R constfold --output-on-failure passes (the lit suite runs as one test; read its output for the files).
E2 · pebble-peephole: a flag-aware peephole engine¶
Lessons: 13.2 (Algorithm 13.2.4), 13.4 (canonical forms, Theorem 13.4.9), 13.7 (powers of two), 13.8 (flag transfer, Theorems 13.8.13–13.8.14, Example 13.8.15, Proposition 13.8.16)
Tests: peephole-<rule>.ll (one file per rule), peephole-stats.ll, equivalence.c, pipeline-icount.ll (@peep)
Implement the rule set below by hand with PatternMatch and run it with a worklist to a fixed point. \(C\), \(C_1\), \(C_2\) are integer constants (ConstantInt), \(x\), \(y\) any values; \(N\) is the bit width; "flags kept" means the result carries the listed flags of the matched instruction(s) and no others.
| Rule | Name (for <stats>) |
Pattern ⇒ result | Condition | Flags of the result |
|---|---|---|---|---|
| R1 | const-rhs |
op C, x ⇒ op x, C for commutative add mul and or xor; icmp P C, x ⇒ icmp swap(P) x, C; fadd/fmul C, x ⇒ x, C |
\(x\) not a constant | all flags kept (samesign, fast-math flags too) |
| R2 | zero-identity |
x op 0 ⇒ x for add sub or xor shl lshr ashr |
— | — |
| R3 | one-identity |
mul x, 1, udiv x, 1, sdiv x, 1 ⇒ x; fmul x, 1.0, fdiv x, 1.0 ⇒ x |
— | — |
| R4 | zero-absorb |
mul x, 0, and x, 0 ⇒ 0 |
integers only | — |
| R5 | self-cancel |
sub x, x, xor x, x ⇒ 0 |
— | — |
| R6 | idempotent |
and x, x, or x, x ⇒ x |
— | — |
| R7 | neg-neg |
sub 0, (sub 0, x) ⇒ x |
— | — |
| R8 | sub-const |
sub x, C ⇒ add x, -C |
\(C \ne 0\) | nsw iff the sub had nsw and \(C \ne\) INT_MIN; never nuw |
| R9 | add-add-const |
add (add x, C1), C2 ⇒ add x, C1+C2 |
— | nsw iff both adds had nsw and \(C_1 + C_2\) does not overflow signed; nuw likewise with unsigned overflow |
| R10 | mul-pow2 |
mul x, 2^k ⇒ shl x, k |
\(k \ge 1\) | nuw kept; nsw kept iff \(k < N - 1\) |
| R11 | add-self |
add x, x ⇒ shl x, 1 |
\(N \ge 2\) | nsw and nuw kept |
| R12 | udiv-pow2 |
udiv x, 2^k ⇒ lshr x, k |
— | exact kept |
| R13 | sdiv-exact-pow2 |
sdiv exact x, 2^k ⇒ ashr exact x, k |
\(2^k > 0\) as a signed constant; only with exact |
exact |
| R14 | urem-pow2 |
urem x, 2^k ⇒ and x, 2^k - 1 |
— | — |
| R15 | icmp-strict |
icmp sge x, C ⇒ sgt x, C-1; sle ⇒ slt x, C+1; uge ⇒ ugt x, C-1; ule ⇒ ult x, C+1 |
the new constant does not wrap (no rewrite of sge x, INT_MIN, sle x, INT_MAX, uge x, 0, ule x, -1) |
samesign kept iff \(C\) and the new constant have the same sign (Example 13.8.15) |
| R16 | fp-zero-identity |
fadd x, -0.0 ⇒ x and fsub x, +0.0 ⇒ x always; fadd x, +0.0 ⇒ x and fsub x, -0.0 ⇒ x only with nsz |
see left | — |
| R17 | fsub-self |
fsub x, x ⇒ +0.0 |
only with nnan |
— |
Requirements:
- E2-R1. Every rule above, with exactly the stated conditions and result flags. A rule whose flag condition fails still fires; it just drops the flag. A rule whose applicability condition fails does not fire.
- E2-R2. Priority: for one instruction, rules are tried in the order R1, R2, …, R17; the first that applies wins. Instructions whose operands are all constants are skipped (they belong to E1; this removes the critical pair of Example 13.4.10).
- E2-R3. Engine discipline (Algorithm 13.2.4; the rule counts in the tests depend on it): the worklist starts with all instructions in program order and is processed first-in, first-out; an instruction already on the list is not added again. When a rule fires on \(i\): a new instruction (if any) is inserted before \(i\), takes \(i\)'s name and is pushed; then every user of \(i\) is pushed, each followed by its users (rules look two levels deep); then \(i\)'s uses are replaced and \(i\) is erased, together with every operand that became unused and has no side effects (transitively), removing erased instructions from the worklist.
- E2-R4. pebble-peephole<stats> does the same and prints to stderr, for each function with at least one rewrite, one line per rule that fired, sorted by rule name: pebble-peephole: @<function> <rule-name> <count>. Any other parameter is an error (opt reports unknown pass name).
- E2-R5. Termination: the engine stops on every input (Theorem 13.4.9 gives the measure for exactly this rule set; don't add rules without extending it).
What the tests check: one file per rule with positive cases, flag cases (kept and dropped, following Lesson 13.8's tables) and must-not-transform cases (add i1 x, x; sdiv without exact; x * 0.0; fsub x, x without nnan; icmp sge x, -128 at i8; samesign with a sign change); peephole-stats.ll — the worked example of Lesson 13.2 §3 ends with 5 instructions and the statistics lines listed there; pipeline-icount.ll — the instruction count after the local pipeline.
Hint 1 — where to start
Write the engine first with only R1 and R2, and get peephole-const-rhs.ll and peephole-zero-identity.ll passing. A rule is a function from an instruction to "no match", "use this existing value" or "use this new instruction": that one return type keeps the engine independent of the rules.
Hint 2 — the key idea
Each flag decision is a fact about exact integers (Algorithm 13.8.7): write the result as a mathematical expression of the inputs, and keep a flag only if its condition follows from the source's flags for every input. For R9 this is "both adds had the flag and \(C_1 + C_2\) fits"; for R10 it is "\(2^k\) is positive as a signed constant". Run the drill ./course drill rewrite-validity --difficulty hard until these feel routine, and test a doubtful rule with Alive2 or your lab checker before you implement it.
Hint 3 — a design sketch
A SetVector<Instruction *> (FIFO: take front(), then remove); a std::map<std::string, unsigned> of counts (sorted for free); match(&I, m_Sub(m_Zero(), m_Sub(m_Zero(), m_Value(X)))) for R7, m_Power2(C) for R10/R12–R14, m_APInt(C) for constants. Create new instructions with BinaryOperator::Create and set flags explicitly (setHasNoSignedWrap, setIsExact, ICmpInst::setSameSign). Common bugs the tests catch: keeping nsw in R10 at \(k = N-1\), forgetting that m_Power2 accepts \(1\) (R10 needs \(k \ge 1\)) and INT_MIN (R13 must reject it), and erasing a dead instruction that is still on the worklist.
Done when: every peephole-*.ll test passes.
E3 · pebble-lvn: local value numbering with identities, folding and memory¶
Lesson: 13.5 (Algorithms 13.5.3 and 13.5.5, Theorems 13.5.12–13.5.13)
Tests: lvn-basic.ll, lvn-flags.ll, lvn-memory.ll, equivalence.c, pipeline-icount.ll (@cse, @mem)
Number the values of each basic block separately (a fresh table per block) and replace every instruction whose value is already available by the earlier holder.
Requirements:
- E3-R1. Keys. Integer binary operators, icmp, casts and getelementptr are keyed by (opcode, predicate, type, operand value numbers), plus the source element type for a GEP. Operands of commutative operators and of icmp eq/ne are sorted by value number. Values defined outside the block, arguments and constants are leaves (equal constants share a number).
- E3-R2. Identities: \(x+0\), \(x-0\), \(x \mid 0\), \(x \oplus 0\), shifts by 0, \(x \cdot 1\) ⇒ \(x\); \(x - x\), \(x \oplus x\), \(x \cdot 0\), \(x \,\&\, 0\) ⇒ 0; \(x \,\&\, x\), \(x \mid x\) ⇒ \(x\) — decided on value numbers, so %y = add %a, 0 followed by %z = sub %y, %a gives 0.
- E3-R3. Folding in the table: an operator whose operands' value numbers all hold constants is replaced by the folded constant (you may use ConstantFoldBinaryOpOperands, ConstantFoldCompareInstOperands, ConstantFoldCastOperand), except division and remainder by zero and sdiv/srem by \(-1\).
- E3-R4. Flags: when an instruction is replaced by an earlier holder, the holder keeps only the poison-generating flags both had (andIRFlags); otherwise the result is more poisonous than the source (Theorem 13.5.12).
- E3-R5. Memory (Definition 13.5.4): a counter, the memory version, is bumped by every store and every other instruction that may write memory (calls, fences). A simple load is keyed by (type, VN(pointer), version): a second load of the same address in the same version is redundant. A simple store of \(v\) to \(p\) makes \(v\) available to a later load of the same type from an address with the same value number (store-to-load forwarding). Volatile and atomic accesses are never numbered and bump the version.
- E3-R6. Calls that are memory(none), willreturn and nounwind (and not convergent) are numbered like operators, by callee and arguments; they don't bump the version.
- E3-R7. Expected \(O(n)\) time per block with hash maps (or \(O(n \log n)\) with ordered maps).
What the tests check: lvn-basic.ll — the worked example of Lesson 13.5 §3 (commutativity, identities, folding; the exact surviving instructions); lvn-flags.ll — flag intersection in both directions; lvn-memory.ll — redundant loads, forwarding, a store to an unknown pointer killing loads, calls that may write killing them and memory(none)/memory(read) calls not, equal GEP addresses, and volatile loads left alone.
Hint 1 — where to start
Do the drill first: ./course drill lvn-table makes you fill the table by hand with the same rules (its oracle is tools/course/lib/localopt.py). Then write the pass for arithmetic only: DenseMap<Value *, unsigned> for value numbers, a map from key to value number, and a vector from value number to the value that holds it.
Hint 2 — the key idea
A replaced instruction must still get a value number: map it to the holder's number, so its later users find the same key. Memory is just one more operand of a load's key: bump the version on every possible write and old loads become unreachable in the table without being deleted. Forwarding is "a store enters the key a load would have after it".
Hint 3 — a design sketch
struct Key { unsigned Opcode, Pred; Type *Ty; SmallVector<unsigned> Ops; unsigned Mem; Type *Aux; } with operator< (or a hash). Visit the block with make_early_inc_range so you can erase as you go. Common bugs the tests catch: forgetting andIRFlags, numbering icmp slt a, b and icmp slt b, a alike (only eq/ne commute), and not bumping the version on a call that writes memory.
Done when: lvn-*.ll pass.
E4 · pebble-dce: worklist dead-code elimination¶
Lesson: 13.5 (Definition 13.5.9, Algorithm 13.5.10, Theorem 13.5.15)
Tests: dce.ll, registry.test, equivalence.c
Requirements:
- E4-R1. An instruction is trivially dead when it has no uses, is not a terminator or an exception-handling pad, has no side effects (it doesn't write memory and can't unwind) and is guaranteed to return (willReturn). Delete every trivially dead instruction.
- E4-R2. Deleting an instruction can make its operands trivially dead: they are re-examined (a worklist), so whole dead chains disappear in one run.
- E4-R3. An unused division that may be UB is dead too (removing UB is a refinement, Lesson 13.8); stores, calls that may write, volatile accesses and terminators always stay.
- E4-R4. Dead cycles (a phi and an add feeding each other with no other use) are not required to be removed: that needs a mark-and-sweep (aggressive DCE, Lesson 13.5 §6). \(O(n + u)\).
What the tests check: dce.ll: a dead chain vanishes; stores, calls and volatile loads stay; a dead loop cycle stays (documenting E4-R4). registry.test: all five passes (and nothing misspelled) are registered.
Hint 1 — where to start
The whole pass fits in one screen. Seed the worklist with every instruction; pop; if trivially dead, push its instruction operands and erase it.
Hint 2 — the key idea
mayHaveSideEffects() covers "writes memory or may unwind"; willReturn() excludes calls that may loop forever. Don't erase an instruction that is still on the worklist without removing it first.
Hint 3 — a design sketch
A SetVector<Instruction *>; pop from the back; a helper bool triviallyDead(const Instruction &) with the four conditions of E4-R1. Common bug: pushing operands after erasing (read them first).
Done when: dce.ll and registry.test pass.
E5 · pebble-reassociate: rank-based reassociation¶
Lesson: 13.6 (Definition 13.6.2, Algorithm 13.6.3, Theorems 13.6.7–13.6.9)
Tests: reassoc-ranks.ll, reassoc-rewrite.ll, reassoc-flags.ll, equivalence.c
Requirements:
- E5-R1. Ranks (Definition 13.6.2): number the blocks in reverse postorder from 1, \(R(B)\). Constants have rank 0, arguments rank 1; a phi, load, call or any other instruction that is not arithmetic (including fneg), logic, compare, cast, select or getelementptr gets \(R(B)\) of its block; every other instruction gets the maximum rank of its operands.
- E5-R2. pebble-reassociate<print-ranks> prints the ranks to stderr and does not transform: one line pebble-reassociate: @<function> <operand> rank <r> per argument and per value-producing instruction, arguments first, then instructions block by block in reverse postorder, in block order. Any other parameter is an error.
- E5-R3. Trees: an expression tree is rooted at a scalar integer add, mul, and, or or xor that is not an internal node; an internal node has the same opcode as its only user, which is in the same block. The leaves of a root are gathered through its internal nodes.
- E5-R4. Rebuilding: fold all constant leaves into one constant \(K\); sort the other leaves by (rank, position), where the position of a value is its index in the order of E5-R2; rebuild the tree as a left-deep chain \(((l_1 \oplus l_2) \oplus l_3) \cdots\) and append \(K\) as the last operand, omitted when it is the identity of \(\oplus\); when \(K\) is absorbing (\(0\) for mul/and, all-ones for or), the whole tree becomes \(K\). The chain's final instruction takes the root's name; newly created instructions take the root's rank and position.
- E5-R5. Flags (Theorem 13.6.8): the rebuilt instructions carry no flags, except nuw on add when every node of the tree had nuw, and disjoint on or when every node had disjoint. nsw never survives.
- E5-R6. \(O(n + \sum_T k_T \log k_T)\) for trees with \(k_T\) leaves.
What the tests check: reassoc-ranks.ll — the ranks of Lesson 13.6's running loop, line by line; reassoc-rewrite.ll — the running example (the loop-invariant part is grouped first), constant folding into one trailing constant, canonical order for permuted inputs, absorbing and identity constants, shared subtrees (a value with two users is a leaf), and trees within one block only; reassoc-flags.ll — nsw dropped, nuw kept only when every add had it, disjoint likewise.
Hint 1 — where to start
Compute and print the ranks first (E5-R2): ReversePostOrderTraversal<Function *> gives the block order. Do the drill ./course drill reassoc-ranks, whose oracle implements exactly this definition.
Hint 2 — the key idea
Collect roots first, then rewrite: rewriting while you walk invalidates the "only user" test. Sorting by rank puts the loop-invariant leaves together at the bottom of the chain, where LICM (and E3 across iterations of the pipeline) can find them as a common subexpression.
Hint 3 — a design sketch
DenseMap<Value *, unsigned> Rank, Pos; isInternal(I); gatherLeaves(Root) with an explicit stack; std::stable_sort on (rank, pos); IRBuilder positioned before the root. Delete the old internal nodes after replaceAllUsesWith on the root (they are now dead). Common bugs the tests catch: keeping nsw, treating a node with two users as internal, and folding a constant of the wrong width (APInt widths must match the type).
Done when: reassoc-*.ll, equivalence.c and pipeline-icount.ll pass; ./course test 13 is then green except for the lab (see the lab spec).