Chapter 17 exercises¶

You'll implement four scalar optimizations as opt plugin passes in pebble/lib/Passes/ScalarOpt/: SCCP, aggressive DCE, dominator-based value numbering and SimplifyCFG-lite. You'll also do the comparison lab in labs/ch17-scalar/, and optionally the ★ labs labs/ch17-lcm/ and labs/ch17-egraph/. Run the tests after every step:

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

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

How to write a pass. Put each pass in any .cpp file under pebble/lib/Passes/ScalarOpt/ (read its README.md), as a new-pass-manager function pass (PassInfoMixin, or RequiredPassInfoMixin so that it also runs on optnone functions; run(Function &, FunctionAnalysisManager &), Ch 12). Register it next to its definition with PEBBLE_FUNCTION_PASS("pebble-sccp", YourPass); 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-sccp -S input.ll

The inputs are LLVM IR in SSA form. To make your own from C, run clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm f.c -o f.O0.ll and then opt -passes=mem2reg -S f.O0.ll -o f.ll.

Common to E1–E4 (the lit test registry.test and equivalence.c): - Each pass keeps the module valid for opt's verifier. - Each pass returns PreservedAnalyses::all() when it changed nothing. Otherwise it returns PreservedAnalyses::none(), or the precise set if you track it. - Each pass preserves the observable behavior of every function. equivalence.c runs a C program under lli before and after each pass, and after the pipelines pebble-sccp,pebble-gvn,pebble-adce,pebble-simplifycfg (twice) and pebble-simplifycfg,pebble-gvn,pebble-sccp,pebble-adce (after sroa,instcombine), and diffs the output.

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

E1: pebble-sccp¶

Contract: a function pass registered as pebble-sccp. Tests: tests/ch17/lit/sccp-basic.ll, sccp-no-fold.ll, sccp-running.ll, registry.test, equivalence.c (all in ch17.lit)

Implement sparse conditional constant propagation (Algorithm 17.1.8) over integer constants, then apply what it proves. You choose the data structures. Lesson 17.1 §7 reads LLVM's SCCPSolver, which does the same with a richer lattice (ranges, structs, interprocedural).

Requirements:

R1. Lattice. Each integer SSA value is Unknown (⊥), a ConstantInt, or Overdefined (⊤).
Values start at ⊥, and edges start non-executable.
Arguments, undef, poison, non-integer values, loads, calls, and any instruction you do not model are Overdefined once their block is executable.
Model at least: binary operators, icmp, select, integer casts and phi.
Fold with ConstantFoldInstOperands (or your own folder). A fold that does not give a ConstantInt is Overdefined. Never fold to poison or undef (sdiv 7, 0 and shl 1, 40 stay).
R2. Solver.
Use two worklists, with CFG edges drained first.
A phi joins only the operands on executable edges, and equal constants join to that constant.
A conditional branch or switch on a constant makes only the selected edge executable.
A branch that still waits on an Unknown condition when both worklists are empty must be resolved as Overdefined, so that every path stays possible.
R3. Rewrite.
Replace every use of a value with a constant lattice value, in an executable block, by the constant, and delete the instruction (the modeled instructions have no side effects).
A conditional branch or switch whose other edges never became executable becomes br to the executable successor. The removed successors lose their phi entries.
Delete the blocks that are not executable.
R4. Optimism. In the running example, SCCP proves x.0 = x.1 = 1, deletes if.then, and returns add4 = sub + 1. i.0 and j.0 stay overdefined, because proving them equal needs Lesson 17.5.
R5. Complexity. Each value changes at most twice and each edge is marked once (Theorem 17.1.9), so the solver is \(O(U + e + I)\).

What the tests check:

Test	Asserts
`sccp-basic.ll`	a constant chain folds and the dead arm is deleted; a phi of equal constants is that constant; a switch on a constant keeps one successor; `select` on a constant condition, and with equal arms; a constant that survives a loop because the edge that would change it never becomes executable (R1–R3)
`sccp-no-fold.ll`	no folding to UB/poison (`sdiv 7, 0`, `shl 1, 40` stay, though `sub 5, 5` becomes 0); `undef`/`poison` operands make results overdefined; loads, volatile loads and calls are not modeled, so the branch on them stays; floating point is not in the lattice (R1)
`sccp-running.ll`	the running example: `x` becomes 1, `if.then` goes, the loop and `i`/`j` stay (R4)
`equivalence.c`, `registry.test`	behavior preserved under `lli`; the pass is registered in the `ch17` group

Hint 1 — where to start

Do the solver first and print the lattice values (errs() from the pass) on sccp-running.ll. Compare with the trace in Lesson 17.1 §3, or with ./course drill sccp-trace --solution on a small function. Write the rewrite only once the values are right.

Hint 2 — the key idea

Optimism lives in two places: values start at ⊥ and edges start non-executable. A phi reads only the operands whose edge is executable, so the 2 in x.1 = phi [2, if.then], … never counts, because the edge from if.then is never marked. Visit a block's instructions only the first time it becomes executable, and its phis again every time a new edge into it becomes executable.

Hint 3 — a design sketch

State. Use a DenseMap<Value *, LatticeVal>, a DenseSet<pair<BasicBlock *, BasicBlock *>> of executable edges, a SmallPtrSet of executable blocks, and two std::deques.
Rewrite. Replace uses (replaceAllUsesWith), turn terminators into BranchInst::Create(Succ) after calling Succ->removePredecessor(BB) on the dropped ones, and delete unreachable blocks with llvm::DeleteDeadBlocks or your own loop.

Common bugs the tests catch: - treating undef as a constant; - joining phi operands from non-executable edges; - deleting a block that still has uses in phis (remove the phi entries first).

Done when: ./course test 17 shows the sccp-* lit tests passing.

E2: pebble-adce¶

Contract: a function pass registered as pebble-adce. Tests: tests/ch17/lit/adce.ll, adce-effects.ll, equivalence.c

Implement aggressive dead code elimination (Algorithm 17.3.5): everything is dead until proven live, and branches are live only when a live block is control dependent on them. Use PostDominatorTreeAnalysis for control dependence (Lesson 15.4). Lesson 17.3 §7 reads LLVM's ADCE.cpp.

Requirements:

R1. Roots.
Instructions that may have side effects (mayHaveSideEffects(): stores, volatile accesses, calls that may write memory or may not return, llvm.assume), and EH pads.
Terminators other than br/switch (ret, unreachable, …).
The branches of blocks that cannot reach a function exit (an infinite loop must stay infinite).
The branch that ends each back edge, unless the function has the mustprogress attribute. Deleting a loop that might not terminate is not a refinement, and this is the remove_loops policy of Lesson 17.3.
R2. Marking.
A live instruction makes its operands' defining instructions live and its block useful.
A live phi makes its incoming blocks useful.
A useful block makes its terminator live if that terminator is an unconditional br. It also makes live the terminators of every block it is control dependent on (its post-dominance frontier).
R3. Sweep.
A dead br/switch becomes br to the nearest strict post-dominator that is useful. Keep the phis of the new target consistent: add an entry for the new edge, with poison if the value can never be observed on it.
Dead instructions are deleted. That includes dead phi cycles, which a use-count DCE (Ch 13) cannot remove.
Blocks left unreachable are removed.
Empty blocks may remain: merging them is E4's job.
R4. Complexity. Marking is linear in instructions + uses + control-dependence edges.

What the tests check:

Test	Asserts
`adce.ll`	a diamond computing a dead value becomes `br label %join`; a live phi keeps its branch; a side effect under a branch keeps the branch and its condition; a loop without `mustprogress` stays (its dead accumulator goes); the same loop in a `mustprogress` function is removed (`loop:` becomes `br label %exit`); a dead phi cycle goes; an infinite loop keeps its branch (R1–R3)
`adce-effects.ll`	stores, volatile loads, calls that may write memory or may not return, and `llvm.assume` stay, with their operands and the branches they depend on (R1)
`equivalence.c`	behavior preserved

Hint 1 — where to start

Write marking without control dependence first, i.e. mark–sweep DCE (Algorithm 17.3.2) that keeps every terminator. It passes the side-effect tests. Then make conditional branches non-roots and add the control-dependence step. ./course drill adce-marking --solution shows the marking order on small CFGs.

Hint 2 — the key idea

A block is control dependent on a branch in \(X\) if \(X\) can choose whether the block runs (Definition 17.3.3). When a block becomes useful, every branch that decides whether it runs becomes live.
A dead branch decides nothing that matters, so it may jump straight to where all its paths meet: its nearest useful post-dominator.
Without the virtual exit and the no-exit roots, an infinite loop would be "dead" and deleted.

Hint 3 — a design sketch

Control dependence. Compute it with the Ferrante–Ottenstein–Warren walk over the post-dominator tree, once per function. Keep a map from each block to the blocks it is control dependent on.
Marking. Use a SmallPtrSet<Instruction *, 32> for live instructions, a set of useful blocks, and one worklist of instructions.
Retargeting. Walk up the post-dominator tree with PDT.getNode(BB)->getIDom() until you reach a useful block.
Loops. Find back edges with a DFS or with LoopInfo.

Common bugs the tests catch: - forgetting the phi entry for the new edge (verifier error); - deleting a non-mustprogress loop; - leaving a dead phi whose operand you deleted.

Done when: the adce* lit tests pass.

E3: pebble-gvn¶

Contract: a function pass registered as pebble-gvn. Tests: tests/ch17/lit/gvn.ll, gvn-memory.ll, equivalence.c

Implement dominator-based value numbering (DVNT, Algorithm 17.4.5) with redundancy elimination. Walk the dominator tree with a scoped hash table, and replace each instruction whose expression is already available from a dominator by that dominator's leader. Lesson 17.4 §7 compares it with EarlyCSE and LLVM's GVN.

Requirements:

R1. Candidates. Binary operators (division and remainder included: a dominating identical division already executed), icmp/fcmp, select, casts and getelementptr. Loads, stores, calls (even readnone ones) and allocas are opaque: each gets a value number of its own. Memory is Ch 19's topic.
R2. Keys. A key is made of the opcode, the result type, the predicate (compares), the source element type (GEP) and the operands' value numbers. For commutative operators the operand numbers are sorted. Poison-generating flags are not in the key: when an instruction is replaced by its leader, the leader keeps the intersection of both flag sets (Instruction::andIRFlags).
R3. Walk. Visit the dominator tree in preorder, children in reverse postorder. Leaving a node removes the keys it added, so siblings never see each other's expressions. An operand with no value number yet, such as a phi operand over a back edge, counts as itself.
R4. Phis.
A meaningless phi (every incoming value is the same value, ignoring the phi itself) is replaced by that value.
A redundant phi (the same incoming value numbers per block as an earlier phi in the same block) is replaced by the earlier phi.
R5. Complexity. One walk: \(O(I + U)\) expected with hashing.

What the tests check:

Test	Asserts
`gvn.ll`	a dominated `add` is replaced, with commutative operands sorted and `nsw` dropped from the leader when the other copy lacks it; siblings keep their copies; meaningless and redundant phis disappear; `%i`/`%j` in a loop stay distinct (pessimistic at back edges); different predicates, cast kinds and GEP types are not merged (R1–R4)
`gvn-memory.ll`	loads across a store, volatile loads and calls are never merged; a dominated `sdiv` is (R1)
`equivalence.c`	behavior preserved

Hint 1 — where to start

Number the instructions of a single block first (local value numbering, Ch 13), then extend to the dominator tree with a scope stack. DominatorTreeAnalysis gives the tree, and ReversePostOrderTraversal gives the child order.

Hint 2 — the key idea

A value computed in block \(A\) is available in every block that \(A\) dominates, and in no other block. So the hash table's contents at a block are exactly the expressions of its dominators. Push a scope when entering a node and pop it when leaving.

Hint 3 — a design sketch

Table. Use a std::map<std::vector<uintptr_t>, Instruction *> (or a ScopedHashTable) from keys to leaders, a DenseMap<Value *, unsigned> of value numbers, and an explicit stack of (node, keys added) for the walk.
Replacement. Replace with I.replaceAllUsesWith(Leader), call Leader->andIRFlags(&I), and collect I for erasure at the end.

Common bugs the tests catch: - merging calls to @pure (R1); - keeping nsw on the leader (R2); - leaking a sibling's table entries (R3).

Done when: the gvn* lit tests pass. Then run pebble-gvn and LLVM's newgvn on tests/ch17/lit/sccp-running.ll's input and explain the difference with Lesson 17.5.

E4: pebble-simplifycfg¶

Contract: a function pass registered as pebble-simplifycfg. Tests: tests/ch17/lit/simplifycfg.ll, equivalence.c

Implement SimplifyCFG-lite (Algorithm 17.7.3): rewrites R1–R3 of Definition 17.7.1, iterated to a fixed point.

Requirements:

R1. Constant branches. br i1 true/false, a conditional branch whose two targets are the same block, and a switch on a constant become br to the selected block. The dropped successors lose their phi entries for this block (BasicBlock::removePredecessor).
R2. Unreachable blocks. Blocks not reachable from the entry are deleted, and their successors lose the corresponding phi entries.
R3. Block merging. A block \(B\) can be merged into \(P\) when:
\(B\) has exactly one predecessor \(P\);
\(P\) ends in an unconditional br to \(B\);
\(B\) is not the entry and \(B \neq P\);
\(B\)'s address is not taken.

\(B\)'s phis (one entry each) are replaced by their incoming values, \(B\)'s instructions move to the end of \(P\), successors' phis that named \(B\) now name \(P\), and \(B\) is deleted. - R4. Fixed point. Repeat until nothing changes. The number of blocks plus edges decreases with every change (Theorem 17.7.9).

What the tests check:

Test	Asserts
`simplifycfg.ll`	a constant branch folds, its dead arm and the phi entry disappear, and the chain merges into `entry`; branches with equal targets and a switch on a constant fold; a self-looping unreachable block is deleted with its phi entry; not merged: a block with two predecessors, the entry, a self loop (R1–R4)
`equivalence.c`	behavior preserved, alone and after `pebble-adce` (whose empty blocks this pass cleans up)

Hint 1 — where to start

Lesson 17.7 §3 applies the three rules by hand to @cleanup, and LLVM's simplifycfg gives the same result there (§7 box). Implement R1 and R2 first. They only remove edges and blocks.

Hint 2 — the key idea

Merging is safe because \(P\) always continues into \(B\) and \(B\) is only entered from \(P\), so the concatenated code runs in the same order.
The phi bookkeeping is the whole difficulty. Every removed edge must remove a phi entry, and every block that disappears must be renamed in its successors' phis.

Hint 3 — a design sketch

Use a changed loop around three sweeps.
R1. Call ConstantFoldTerminator or write your own.
R2. Do a DFS from the entry and delete everything else with DeleteDeadBlocks.
R3. Call B->replaceSuccessorsPhiUsesWith(P) before moving the instructions, then P->splice(P->end(), B) after erasing \(P\)'s terminator, and then erase \(B\).

Common bugs the tests catch: - B->replaceAllUsesWith(P) corrupts phis; - merging a self loop; - merging into the entry's successor when the entry has a conditional branch.

Done when: ./course test 17 shows every ch17.lit test passing.

Lab · Simple CP vs SCCP, hash VN vs partition VN¶

Spec: labs/ch17-scalar/SPEC.md · Your code: labs/ch17-scalar/src/ (any files you like) · Tests: ch17.Compare.*, ch17.lab (scalar-*.test)

Read the spec: it gives the requirements, the contract, the output formats, the performance targets, what the tests check and the milestones. Then compare your measurements with the comparison sections of Lessons 17.1 and 17.5.

Stretch goals¶

★ Lazy code motion on TAC: labs/ch17-lcm/SPEC.md (Lesson 17.6).
★ Equality saturation: labs/ch17-egraph/SPEC.md (Lesson 17.8).
Add ranges to pebble-sccp: replace the constant lattice by ConstantRange (Lesson 17.2) and fold icmp whose operand ranges decide it. Compare with LLVM's sccp on labs/ch17-scalar/corpus/*.ll.
Make pebble-gvn optimistic: replace the dominator walk by RPO iteration (Algorithm 17.5.6), and show that %i and %j in gvn.ll's @loop merge.
Add jump threading over phis of constants (Algorithm 17.7.7) to pebble-simplifycfg, with a size threshold, and run it on jt.c from Lesson 17.7 §7.