Skip to content

Chapter 12 — Exercises: your first passes in the course plugin

You write three passes in pebble/lib/Passes/Basics/ (any file names, any number of files; every *.cpp there is compiled into the plugin PebblePasses and into pebblec), then the comparison lab in labs/ch12-testing/. Each pass's contract is its pipeline name plus its observable behavior on IR, checked by lit + FileCheck + lli in tests/ch12/lit/ (FOUNDATION §7, "Test contract under minimal scaffolding"). Nothing is stubbed: until you register a pass, the tests fail with

opt: unknown pass name 'pebble-strength'

which is the expected skeleton failure. Build and test with

./course test 12                       # all ch12 tests (lit, lab, unit)
build/<preset>/bin/pebble-lit -v tests/ch12/lit/strength.ll    # one test file

Register every pass next to its definition with the macros of pebble/include/pebble/Passes/Registry.h, for example PEBBLE_FUNCTION_PASS("pebble-strength", MyStrengthPass);, and check the registration with opt -load-pass-plugin=build/<preset>/lib/PebblePasses.so -passes='print<pebble-passes>' -disable-output x.ll.

E1 — pebble-stats and print<pebble-stats> (Lessons 12.1, 12.3)

Goal. A function analysis and its printer, cached and invalidated by the new pass manager.

Requirements.

  • R1. A function analysis registered as pebble-stats (so require<pebble-stats> and invalidate<pebble-stats> work).
  • R2. A printer registered as print<pebble-stats> that obtains the result from the analysis manager (FAM.getResult<...>), never by recomputing it itself, prints to stderr, and preserves all analyses.
  • R3. For every function definition (declarations print nothing), in module order, exactly:
pebble-stats: function '<name>'
  blocks: <number of basic blocks>
  edges: <sum over blocks of the terminator's number of successors>
  critical-edges: <successor slots (b, i) with >= 2 successors in b and >= 2 predecessor edges in the target>
  instructions: <number of instructions, terminators and phis included>
  opcodes: <name>=<count> ... sorted by opcode name (Instruction::getOpcodeName), space-separated

Edges are counted per successor slot (a switch with two cases to one block has two edges); critical edges are those of llvm::isCriticalEdge(T, i, /*AllowIdenticalEdges=*/false) (Definition 12.3.2). - R4. Two printers in a row compute the analysis once (the second is a cache hit); a transformation that changes instructions and does not preserve your analysis makes the next printer recompute it.

Tests. tests/ch12/lit/stats.ll (format, switch edges, declarations), stats-cache.ll (caching, invalidation), registry.test.

Hint 1 — where to start

Read LLVM-WNPM ("Writing an LLVM Pass") and look at how pebble/lib/Passes/Dominance/Ch15Passes.cpp declares an analysis (AnalysisInfoMixin, a static AnalysisKey, a Result type, run) and a printer.

Hint 2 — the key idea

The result is a small struct; std::map<std::string, unsigned> gives the sorted histogram for free. The default invalidation (not preserved ⇒ invalidated) is exactly right for an analysis that depends on every instruction (Algorithm 12.3.3's remark).

Hint 3 — a design sketch

StatsAnalysis : AnalysisInfoMixin<StatsAnalysis> with Result run(Function &, FunctionAnalysisManager &); StatsPrinter : RequiredPassInfoMixin<StatsPrinter> whose run returns PreservedAnalyses::all(). The most common bug: counting predecessors with a set of blocks instead of predecessor edges.

E2 — pebble-strength (Lessons 12.2, 12.3, 12.8)

Goal. Strength reduction by powers of two, with correct flags and a correct signed division.

Requirements.

  • R1. A function pass registered as pebble-strength, derived from OptionalPassInfoMixin (it must be skipped on optnone functions and counted by -opt-bisect-limit).
  • R2. For scalar integer types iN and a constant \(C = 2^k\) with \(k \ge 1\) (as an unsigned N-bit value): mul X, C or mul C, X becomes shl X, k; udiv X, C becomes lshr X, k; urem X, C becomes and X, C-1.
  • R3. sdiv X, C with \(C\) positive (so \(1 \le k \le N-2\)) becomes a sequence without division that rounds toward zero (Theorem 12.3.9); sdiv exact X, C becomes ashr exact X, k.
  • R4. Flags: nuw on mul carries over to shl; nsw carries over only when \(k \le N-2\) (Theorem 12.3.10); exact on udiv carries over to lshr. Never add a flag the source did not justify.
  • R5. Leave alone: constants that are not powers of two, 0, sdiv by a negative constant (including sdiv i8 %x, -128, whose bit pattern 0x80 is a power of two only as an unsigned value), vectors (optional).
  • R6. Return PreservedAnalyses::all() when nothing changed, and preserve the CFG analyses (PA.preserveSet<CFGAnalyses>()) when something did.
  • R7. Programs compute the same results before and after the pass (lli), including at INT_MIN, INT_MAX and negative non-multiples of the divisor.
  • R8 (when it works). Register it as the first course -O1 step: PEBBLE_COURSE_PIPELINE_STEP(1210, "function(pebble-strength)"); (Lesson 12.2, the pitfall). From then on pebblec -O1 runs only the registered course steps — no longer LLVM's default<O1>, which is the fallback while no step exists — so -O1 code gets less optimized until later chapters add their passes. Use pebblec -O2 for LLVM's optimizer.

Tests. strength.ll (R2–R4), strength-negative.ll (R4, R5, optnone), strength-lli.ll (R7), stats-cache.ll (R6), bisect.ll (R1).

Hint 1 — where to start

Collect the candidate BinaryOperators first, then rewrite, so you never modify the list you iterate. APInt::isPowerOf2, APInt::logBase2 and APInt::isNegative answer every question about \(C\).

Hint 2 — the key idea

For sdiv, add \(2^k - 1\) only when \(X\) is negative. You can compute that bias without a branch: an arithmetic shift by \(N-1\) gives all ones or zero, and a logical shift of that by \(N-k\) gives \(2^k - 1\) or 0. Check your sequence with ./course drill peephole-verify and with tv.py from Lesson 12.8.

Hint 3 — a design sketch

One rewrite(BinaryOperator &) -> Value * that returns the replacement or nullptr, built with an IRBuilder positioned at the old instruction; replaceAllUsesWith, takeName (not on constants), eraseFromParent. The bug the tests catch most: taking \(C = 2^{N-1}\) for sdiv or keeping nsw at \(k = N-1\).

E3 — pebble-bbcount (Lesson 12.3)

Goal. Instrument every basic block with a counter and report the counts at exit — the data behind profile-guided optimization (Chapter 20).

Requirements.

  • R1. A module pass registered as pebble-bbcount, derived from RequiredPassInfoMixin (it instruments optnone functions too and is never skipped by -opt-bisect-limit).
  • R2. One i64 counter per basic block of every defined function, in module order and then block order, stored in a zero-initialized global array named @__pebble_bbcount_counters; the block's counter is incremented (load, add 1, store) at its first insertion point, i.e. after its phis (and after a landingpad).
  • R3. Block names are "<function>:<block>", or "<function>:#<index>" (0-based position in the function) for an unnamed block; an array of pointers to these C strings is passed to the runtime.
  • R4. At exit, void __pebble_bbcount_dump(ptr counters, ptr names, i64 n) from the provided pebble/lib/Passes/Basics/provided/pebble_bbcount_rt.c is called once, from a function registered in @llvm.global_dtors; it prints pebble-bbcount: <n> blocks and <count> <name> lines on stderr.
  • R5. A module that already contains @__pebble_bbcount_counters is left unchanged (running the pass twice counts once); a module without definitions is unchanged. The program's own output is unchanged.

Tests. bbcount.c (counts of a real loop under lli -extra-module, idempotence, unnamed blocks, optnone), bbcount-phi.ll (placement after phis, the destructor, the runtime declaration), bisect.ll.

Hint 1 — where to start

Collect all blocks first (functions you create later must not be instrumented), then create the globals, then insert the increments. BasicBlock::getFirstInsertionPt is the insertion point of R2.

Hint 2 — the key idea

IRBuilder::CreateConstInBoundsGEP2_64 addresses counter \(j\); ConstantDataArray::getString makes each name; appendToGlobalDtors (llvm/Transforms/Utils/ModuleUtils.h) registers your exit function.

Hint 3 — a design sketch

Three phases in run(Module &, ModuleAnalysisManager &): enumerate (block, name) pairs; create @__pebble_bbcount_counters, the name strings and @__pebble_bbcount_names; insert increments; create an internal void() function that calls the runtime; return PreservedAnalyses::none(). The bug the tests catch most: inserting at BB.begin(), before the phis (the verifier rejects it).

E4 ★ — fuzz your Pebble parser with libFuzzer (Lesson 12.6, stretch, not graded)

Goal. Coverage-guided fuzzing (Algorithm 12.6.4) of the parser you wrote in Chapter 4. There are no tests: the oracle is "no crash, no sanitizer report, no hang"; syntax errors are expected and fine.

  • Write a fuzz target int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) that creates a SourceManager, adds the bytes with SM.addBuffer(std::string(reinterpret_cast<const char *>(Data), Size), "fuzz.pbl"), and parses them with a DiagnosticEngine, an ASTContext, a Lexer and parseModule (pebble/Parse/Parser.h; tests/ch04/unit/ParserTest.cpp shows the same setup). Return 0.
  • Compile it with -fsanitize=fuzzer,address and link the libraries pebble_parse, pebble_ast, pebble_lex, pebble_support and LLVM's Support library (the sanitizer runtimes: README). Seed the corpus with the tests/**/*.pbl files and give libFuzzer a dictionary of Pebble keywords and operators (-dict=), which plays the role of the CMP mutations of Theorem 12.6.8.
  • Report executions per second and coverage after ten minutes; reduce every crash with -minimize_crash=1, fix it, and keep the reduced input as a regression test for Chapter 4.

Lab — labs/ch12-testing

Part A (L1): test the provided pebble-lab-fold three ways — a FileCheck test, snapshots, a differential tester — and meet the detection requirements against its five planted bugs. Part B (L2): implement ddmin behind pebble/Reduce/DDMin.h, reduce the planted crash with ch12-reduce, and compare with llvm-reduce and C-Reduce.