Skip to content

Chapter 16 exercises

You'll implement pruned SSA construction from allocas, pebble-mem2reg, in pebble/lib/Passes/SSA/, and the two comparison labs in labs/ch16-ssa-construct/ and labs/ch16-out-of-ssa/. Run the tests after every step:

./course test 16                                   # builds, then runs every test labelled ch16
ctest --preset linux -L '^ch16$' -R ch16_mem2reg    # one suite while iterating (macos preset on a Mac)

Before you start, every ch16 test fails: the lab tests with TODO(ch16): …, and the mem2reg tests with unknown pass name 'pebble-mem2reg' because no pass is registered yet. That's expected.

Stuck? Work through the hints in order. The reference solutions are in solutions/<same path>. Only look at them after you've passed the tests, or after an honest hour.

E1 · pebble-mem2reg: pruned SSA from allocas

Contract: a function pass registered as pebble-mem2reg (and pebble-mem2reg<stats>) through PEBBLE_REGISTER_PASSES in any .cpp under pebble/lib/Passes/SSA/ (see its README.md). Tests: - ch16_mem2reg_test: Fixture.NoPromotableAllocasLeft, Fixture.PrunedPhiCount, Fixture.MatchesLLVMAfterSimplification - tests/ch16/lit/mem2reg-*.{ll,c,test}

Promote every promotable alloca of each function to SSA values with Cytron's construction in its pruned flavor:

  1. Find the definition blocks and the live-in blocks of each alloca (Algorithm 16.4.2).
  2. Place phis at \(\mathrm{DF}^+\) of the definition blocks, restricted to the live-in blocks (Definition 16.1.7, Algorithm 16.2.4). llvm::ForwardIDFCalculator is allowed, or use your own \(\mathrm{DF}^+\).
  3. Rename along the dominator tree, with one value stack per alloca (Algorithm 16.2.3).

Lesson 16.4 reads LLVM's PromoteMemoryToRegister.cpp, which does the same plus fast paths and phi simplification. You choose the data structures.

Requirements:

  • R1. What to promote. Promote exactly the allocas of Definition 16.4.1:
  • the alloca is in the entry block;
  • every user is a non-volatile load, a non-volatile store into it, or a llvm.lifetime.start/llvm.lifetime.end;
  • all loads and stores use one type.

Delete promoted allocas, their loads, stores and lifetime markers. Promoting one alloca can make another promotable (a pointer local that pointed at it goes away). Repeat until no promotable alloca is left. - R2. Where the phis go. For each promoted alloca, insert one phi at exactly each block of \(\mathrm{DF}^+(\text{store blocks}) \cap \text{LiveIn}\), and nowhere else. Do not simplify phis afterwards: the tests count your phis against the pruned count. - R3. Values. - Each load is replaced by the value that reaches it. - A load that no store reaches reads undef of the alloca's type. - A phi has one incoming entry per predecessor edge: a switch with two edges to one block gives two entries. - A predecessor that is unreachable from the entry contributes poison. - R4. Correctness. The module still passes verify, and every function keeps its observable behavior. The lit test runs the C corpus with lli before and after the pass and diffs the output. - R5. Complexity. Placement is linear per alloca given the dominator tree (Sreedhar–Gao), plus the liveness walk. The 65-function corpus must run in well under a second. - R6. Parameters. - The accepted parameter strings are "" and "stats". With stats, print one line on stderr for each function that promoted at least one alloca: pebble-mem2reg: @<function>: promoted <A> allocas, inserted <P> phis. - Any other parameter must make the parser return no pass, so that opt reports unknown pass name 'pebble-mem2reg<…>'.

What the tests check:

Test Asserts
Fixture.NoPromotableAllocasLeft after the pass on tests/ch16/Inputs/mem2reg/corpus.ll, the module verifies and no function has a promotable alloca left (R1)
Fixture.PrunedPhiCount for each function promoted in one round, phis after = phis already in the input + the pruned count computed independently in the test (R2)
Fixture.MatchesLLVMAfterSimplification you never have fewer phis than LLVM's mem2reg, and after folding the phis simplifyInstruction folds, you have exactly as many (R2 and R3)
lit/mem2reg-shapes.ll a diamond gets one phi; a variable dead at the join gets none; a loop phi has undef on entry; a switch with two edges to one block; a non-promotable alloca stays; a pointer local needs two rounds; an unreachable predecessor contributes poison (R1–R3)
lit/mem2reg-equivalence.test the C corpus: same output under lli, verified IR, no allocas where all locals are promotable, array_sum keeps its array (R1 and R4)
lit/mem2reg-running-example.c the running example of Lessons 15.3 and 16.2: phis in B, E and H only, the same blocks as LLVM (R2)
lit/mem2reg-stats.ll the stats line, and the error for an unknown parameter (R6)
Hint 1 — where to start

Write the promotability check first, and make NoPromotableAllocasLeft pass with a deliberately wrong but simple promotion: put a phi at every join block. PrunedPhiCount will then show how far off minimal-at-every-join is. Get the DominatorTree from the FunctionAnalysisManager.

Hint 2 — the key idea
  • The live-in blocks are found backwards. Start from each block whose first access to the alloca is a load (the use is upward-exposed), and walk predecessors. Stop at blocks that store to the alloca, because the value is defined there.
  • Then filter \(\mathrm{DF}^+\) with that set: this is exactly IDFCalculator::setLiveInBlocks.
  • Renaming is Lesson 16.2's stack walk. A store pushes its value operand; a load is replaced by the top of the stack. At the end of each block, fill the successors' phi entries for this edge with the current tops.
Hint 3 — a design sketch
  • Use an index per promotable alloca, a DenseMap<PHINode *, unsigned> from each phi to its alloca, and a vector of current values per alloca.
  • Do an iterative walk of the dominator tree with an explicit stack of (node, saved values), so that deep CFGs cannot overflow the call stack.
  • Collect the instructions to delete and erase them at the end.

Common bugs the tests catch: - Forgetting a second phi entry for a duplicated switch edge makes the verifier fail. - Simplifying phis like LLVM does makes PrunedPhiCount fail.

Done when: ./course test 16 shows ch16_mem2reg_test and the mem2reg-* lit tests passing. Then compare with LLVM on the box of Lesson 16.4 §7:

opt -load-pass-plugin=build/linux/lib/PebblePasses.so -passes='pebble-mem2reg<stats>' -disable-output swap.ll

Lab L1 · SSA construction: Cytron's three flavors vs Braun et al. (vs ★ Aycock–Horspool)

Spec: labs/ch16-ssa-construct/SPEC.md · Your code: labs/ch16-ssa-construct/src/ (any files you like) · Tests: ch16_construct_test, lit/lab-construct.test, ch16.lab.compare-smoke

Read the spec for the requirements (exact phi counts per algorithm), the contract (ssalab::construct), the formats, what the tests check and the milestones. Then compare your measurements with the comparison tables of Lessons 16.1–16.3.

★ Optional: Aycock–Horspool (R7).

Lab L2 · Out of SSA: naive vs split vs coalesce

Spec: labs/ch16-out-of-ssa/SPEC.md · Your code: labs/ch16-out-of-ssa/src/ · Tests: ch16_destruct_test, lit/lab-destruct.test

The naive method must be wrong in exactly Cytron's way; split must use the optimal number of moves; coalesce must beat split. Compare your copy counts with Lessons 16.6–16.7.

★ Optional: Sreedhar's Method I as a fourth mode, and Algorithm 16.7.4 in place of pairwise interference.