Chapter 19 exercises¶

You'll implement two memory optimizations as opt plugin passes in pebble/lib/Passes/Memory/ — dead-store elimination (pebble-dse) and store-to-load forwarding with redundant-load elimination (pebble-loadfwd) — on LLVM's AAResults and MemorySSA, and the comparison lab in labs/ch19-points-to/: Andersen's and Steensgaard's points-to analyses over LLVM IR (with ★ online cycle elimination). Run the tests after every step:

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

Before you start, every ch19 test fails. The pass tests fail with unknown pass name 'pebble-dse' (and pebble-loadfwd), because no pass is registered yet, and the points-to tests stop with TODO(ch19): …. That's expected.

How to write a pass. Put each pass in any .cpp file under pebble/lib/Passes/Memory/ (read its README.md; Ch19Passes.cpp there is provided and belongs to the lab), as a new-pass-manager function pass (PassInfoMixin or OptionalPassInfoMixin, run(Function &, FunctionAnalysisManager &), Ch 12). Register it next to its definition with PEBBLE_FUNCTION_PASS("pebble-dse", YourPass); from pebble/Passes/Registry.h. Get the analyses from the manager:

AAResults &AA = FAM.getResult<AAManager>(F);                 // the default AA pipeline (Lesson 19.1)
MemorySSA &MSSA = FAM.getResult<MemorySSAAnalysis>(F).getMSSA();
PostDominatorTree &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);

Try a pass with opt -load-pass-plugin=build/linux/lib/PebblePasses.so -passes=pebble-dse -S input.ll. To make 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 -S f.O0.ll -o f.ll (arrays and structs stay in memory).

Common to E1–E2 (the lit tests registry.test, equivalence.c and soundness.ll): - Each pass keeps the module valid for opt's verifier and keeps MemorySSA up to date when it deletes an access (MemorySSAUpdater::removeMemoryAccess before erasing the instruction), or does not claim to preserve it. - Each pass returns PreservedAnalyses::all() when it changed nothing. - Each pass preserves observable behavior: equivalence.c runs a C program under lli before and after each pass and after pebble-loadfwd,pebble-dse,pebble-loadfwd,pebble-dse, diffs the output, and checks that the pipeline removed at least one load or store; soundness.ll does the same on adversarial IR (may-alias pointers, calls, escaping pointers, volatile and atomic accesses, loops). - Neither pass touches volatile or atomic accesses (isSimple()), and neither deletes anything a call might read.

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

E1: pebble-dse¶

Contract: a function pass registered as pebble-dse. Tests: tests/ch19/lit/dse.ll (must delete), dse-keep.ll (must keep), registry.test, equivalence.c, soundness.ll (all in ch19.lit)

Implement dead-store elimination on MemorySSA (Lesson 19.11, Algorithm 19.11.5; Definition 19.11.4). You design the walk and the data structures.

Requirements:

R1. Killed stores. Delete a simple store \(S\) when (a) every path from \(S\) to the function exit passes through a store that completely overwrites \(S\) — MustAlias with \(S\)'s location (AA.isMustAlias on MemoryLocation::get) and at least as many bytes — and a single such store post-dominating \(S\) is enough; and (b) no instruction reachable from \(S\)'s MemoryDef along MemorySSA def-use edges, before a complete overwrite, may read \(S\)'s location (isRefSet(AA.getModRefInfo(I, Loc))).
R2. Stores dead at exit. Condition (a) also holds when the underlying object of \(S\)'s pointer (getUnderlyingObject) is an alloca that is never captured (PointerMayBeCaptured(Obj, /*ReturnCaptures=*/true)): its memory dies at return. Condition (b) must still hold.
R3. No-op stores. Delete store (load P), P when nothing between the load and the store may write the location (for example: the walker's clobber of the store's defining access dominates the load's MemoryUse).
R4. Must not transform. Keep: stores followed by a possible read (a load, a call that may read, a noalias-less argument that may alias); stores to escaped locals before calls; the last store to an escaped local; partial overwrites (an i8 store does not kill an i32 store); stores killed on one path only; volatile and atomic stores, which are also never killing stores; stores in loops to non-local memory.
R4a. Loops and unwinding. Alias answers compare two pointers within one iteration: a pointer computed inside a loop (for example gep %a, %i with %i a header phi) names a different address in the next iteration. So (i) a killing store in another block counts only when both pointers are loop-invariant (arguments, globals, or instructions outside every loop, after stripping casts and constant-index GEPs), and (ii) when the walk of R1(b) passes a MemoryPhi and \(S\)'s pointer is loop-variant, assume a read; past a MemoryPhi only kills through loop-invariant pointers stop a path. (iii) If an instruction between \(S\) and the killing store may unwind (mayThrow()), the caller can see \(S\)'s value: keep \(S\) unless R2 applies (a non-escaping local dies on unwinding too).
R5. Complexity. Bound the MemorySSA exploration per store (the reference uses 200 steps; LLVM uses dse-memoryssa-scanlimit = 150); when the budget runs out, keep the store.

What the tests check:

Test	Asserts
`dse.ll`	`@overwrite` (same pointer), `@other_local` (two allocas), `@noalias_args` (a load of a `noalias` argument does not read), `@postdom` (the killing store post-dominates), `@dead_local`, `@loop_local` (non-escaping allocas), `@noop_store`
`dse.ll` (cont.)	`@loop_invariant_kill` (a store after the loop kills the loop's stores to an invariant pointer)
`dse-keep.ll`	`@read_between`, `@may_alias_read`, `@escaped`, `@escaped_last`, `@partial`, `@one_path`, `@volatile_atomic`, `@loop_arg`, `@not_noop`, `@unwind` (a call that may throw), `@loop_variant_kill`, `@loop_carried_read` (R4a) keep their stores
`soundness.ll`	adversarial programs under `lli` before and after each pass: loop-variant kills, loop-carried reads, may-alias reads, calls that read, a local escaping through a global, volatile and atomic reads
`equivalence.c`	output unchanged under `lli`; the pipeline removes memory operations

Hint 1 — where to start

Handle R1 for stores in the same block first: store 1, p; store 2, p with nothing in between. Print MSSA.getMemoryAccess(S) and its users (opt -passes='print<memoryssa>') to see what "reachable along def-use edges" means.

Hint 2 — the key idea

Split the decision in two independent questions: is every path killed? (a post-dominance or non-escaping-local question, no MemorySSA needed) and is anything read before the kill? (a forward walk over the users of the MemoryDef: MemoryUses are reads to check, MemoryDefs are either complete overwrites — stop that path — or writes to look past, MemoryPhis are followed — but a MemoryPhi may be a loop header, so from there on remember that you may be in a later iteration, R4a). A MemoryDef user that is the store itself means you went around a loop. For the loop test, LoopInfo (FAM.getResult<LoopAnalysis>(F)) tells you whether a pointer's defining instruction lies in a loop.

Hint 3 — design sketch

A worklist of MemoryAccess * seeded with the users of \(S\)'s MemoryDef, a visited set and a step counter. For each popped access: phi → push its users; use or def → check getModRefInfo for Ref; def that completely overwrites → do not push its users; other def → push its users. Collect dead stores in a vector and erase them at the end (deleting a dead store never makes another dead store live), calling MemorySSAUpdater::removeMemoryAccess first.

E2: pebble-loadfwd¶

Contract: a function pass registered as pebble-loadfwd. Tests: tests/ch19/lit/loadfwd.ll (must replace), loadfwd-keep.ll (must keep), registry.test, equivalence.c, soundness.ll

Implement store-to-load forwarding and redundant-load elimination (Lesson 19.11, Algorithm 19.11.7; Definition 19.11.6) with the MemorySSA walker (Lesson 19.10, Algorithm 19.10.5).

Requirements:

R1. Forwarding. Replace a simple load \(L\) by the stored value when the walker's clobber of \(L\) (MSSA.getWalker()->getClobberingMemoryAccess(L)) is the MemoryDef of a simple store \(S\) that dominates \(L\), MustAliases \(L\)'s location, and stores a value of exactly \(L\)'s type.
R2. Redundant loads. Otherwise replace \(L\) by an earlier simple load \(L_2\) of the same type from a MustAlias location that dominates \(L\), when \(L\)'s clobber dominates \(L_2\)'s MemoryUse (MSSA.dominates): nothing between them can write the location.
R3. Alias analysis does the work. Use only AAResults and MemorySSA for "may this write that location": the tests expect distinct allocas, noalias arguments and TBAA (@tbaa in loadfwd.ll) to be exploited, and nothing else.
R4. Must not transform. Keep loads after a may-alias store, after an opaque call when the location escaped, volatile and atomic loads, loads of a different type than the store (i64 store, i32 load), loads whose value is stored on one path only (no dominating store: load PRE is not required), and loads after a loop that writes the location (a MemoryPhi clobber).
R5. Order. Visit blocks so that dominators come first (for example depth_first(&F.getEntryBlock())), so that R2's earlier load has already been kept or replaced.

What the tests check:

Test	Asserts
`loadfwd.ll`	`@forward`, `@other_local`, `@load_load`, `@dominating` (across blocks, `noalias` store on a side path), `@tbaa`
`loadfwd-keep.ll`	`@may_alias`, `@escaped`, `@volatile_atomic`, `@type_mismatch`, `@one_path`, `@loop`
`equivalence.c`, `soundness.ll`	output unchanged under `lli` (`soundness.ll`: may-alias stores, calls that write an escaped local, loop-carried loads, pointer selects)

Hint 1 — where to start

Print the clobbers with opt -passes='print<memoryssa-walker>' -disable-output f.ll: every case of R1 is "the clobber is a store to the same place".

Hint 2 — the key idea

The walker has already done the path reasoning: its clobber \(C\) is a write that may alias the load, with nothing that may alias in between on any path (Theorem 19.10.7). Forwarding is safe when \(C\) is a store that must alias and dominates the load. For load–load, the question "did anything write between \(L_2\) and \(L\)?" becomes "does \(L\)'s clobber come before \(L_2\)?", i.e. MSSA.dominates(C, MSSA.getMemoryAccess(L2)).

Hint 3 — design sketch

One pass over the loads in dominator-respecting order, a vector of kept loads, and for each replaced load: replaceAllUsesWith, MemorySSAUpdater::removeMemoryAccess, eraseFromParent. Preserve CFGAnalyses and MemorySSAAnalysis if you keep MemorySSA updated.

The comparison lab¶

The points-to lab is specified in labs/ch19-points-to/SPEC.md: implement computePointsTo (contract pebble/include/pebble/Analysis/PointsTo.h) in pebble/lib/Analysis/Alias/src/, for Andersen (Lesson 19.4), Steensgaard (Lesson 19.5) and ★ Andersen with online cycle elimination. Its tests (ch19.lab, ch19.PointsTo.*) check exact agreement with a Python oracle, run-time soundness through pebble-points-to-instrument and lli, and the precision ordering; its driver ch19-pointsto measures precision and speed.

★ Pebble idea. Pebble has no unions and no pointer casts, so its front end could attach TBAA tags (one type tree per Pebble type) to every load and store it emits. Try it on a copy of the lowering and measure how many more loads pebble-loadfwd forwards.