Skip to content

Lab 24 · A random Pebble program generator, differential fuzzing and benchmarking of your pipeline

Chapter: 24 · The Complete Pebble Compiler — and Beyond · Lessons: 24.1, 24.2, 24.7; 12.6 (grammar-directed generation) · Time: 6–8 hours for L1, then as long as you like for the measurements · Tests: ./course test 24 (label ch24)

1. Goal

Chapter 12 fuzzed the front end. This lab fuzzes your optimizer: you write a generator of random Pebble programs that are accepted by construction and terminate, and the provided scripts run every program through pir-run (the oracle) and through pebblec at -O0, -O1 (your pipeline from E1) and -O2 (LLVM's), comparing stdout, stderr and exit status. Pebble has no undefined behavior (spec §11.2), so any difference is a miscompilation, and a trap is an ordinary, comparable outcome. The second half is measurement: eight benchmark programs, compile time, run time, instruction counts and object size per level, and the report that closes the chapter (benchmark.md is the reference's).

2. The contract and the command line

One function, declared in include/capstone/Generator.h, is what the tests and ch24-gen call. You write it in src/ (any files; the provided Stub.cpp stops with TODO(ch24) until you replace it):

namespace capstone {
struct GenOptions {
  unsigned MaxFunctions = 4;    // helper functions besides main (0 = only main)
  unsigned MaxStatements = 10;  // statements per block, at most
  unsigned MaxDepth = 3;        // expression nesting, at most
  unsigned MaxLoopDepth = 2;    // loop nesting, at most
  unsigned LoopBound = 8;       // for trip counts and while iteration counts, at most
  bool AllowTraps = true;       // false: trap-free by construction
};
std::string generateProgram(uint64_t Seed, const GenOptions &Opts = {});
}

The provided driver:

ch24-gen [--seed S] [--count N] [--no-traps] [--max-functions K] [--max-statements K]
         [--max-depth K] [--max-loop-depth K] [--loop-bound K] [-o DIR]

With --count 1 (the default) the program for seed S goes to stdout; with -o DIR and --count N, seeds S..S+N-1 are written to DIR/pS.pbl. The two provided Python scripts drive everything else:

fuzz.py  --gen ch24-gen --pebblec P --pir-run R --pir-opt O --opt OPT
         [--seed 1] [--count 50] [--levels -O0,-O1,-O2] [--no-traps] [--keep DIR] [--gen-arg=ARG ...] [--quiet]
bench.py --pebblec P [--levels -O0,-O1,-O2] [--repeat 5] [--json OUT] [--markdown] [--quick] program.pbl ...

3. Requirements

  • R1 (determinism). generateProgram(S, O) returns the same text for the same (S, O) on every platform: use std::mt19937_64's raw output only (its sequence is specified by the standard; std::uniform_int_distribution is not) and derive every choice from it. Different seeds give different programs.
  • R2 (accepted by construction). Every program is accepted by the reference front end and its PIR verifies: well-typed (generate expressions for a requested type from an environment of typed variables, as bidirectional checking reads them, spec §8.1), definitely assigned (initialize at declaration), every function ends in return, break/continue only inside loops, references obey the exclusivity rule of spec §9 (never borrow a variable &mut while another borrow of it is live; the reference solution passes &mut only to a provided helper with literal second arguments), and every call's arguments match the callee's declared parameter kinds (&/&mut/by value; spec §9's copy semantics).
  • R3 (termination). Every program finishes in the interpreter within 20 000 000 steps and call depth 10 000: for bounds are constants or masked values at most LoopBound; a while loop counts a fresh variable that is incremented first in its body, so that continue cannot skip the increment, and the counter is never reassigned elsewhere; helper functions call only functions defined earlier (no mutual recursion); a recursive helper is called with a bounded argument.
  • R4 (comparison power). Every program prints something that depends on its computation; with AllowTraps, more than a third of the programs return normally (a corpus that always traps at the first statement compares nothing) and some do trap.
  • R5 (trap-free mode). With AllowTraps == false, no program traps: wrapping operators (&+ &- &*), shifts masked to 0..63, array indices masked to the array's length, divisors of the form ((e & 7) + 1), / and % guarded against MIN / -1 (or use a positive divisor).
  • R6 (options). MaxFunctions == 0 produces no helper fn f0..; MaxLoopDepth == 0 produces no generated loop (while, for iN in); MaxDepth == 1 produces only leaves and one operator.

4. What to generate

The reference solution's grammar, which you may follow or improve on:

Category Forms
Types int, float, bool, [int; N] with N in 1..8, one struct P { x: int, y: int }
Expressions literals, variables, + - * / % & \| ^ << >> and the wrapping &+ &- &*, comparisons, && \|\| (short-circuit: the right side may trap), unary - !, calls to earlier helpers and to the preamble (tri, bump, sum4, sum8), field and index reads, as casts between int and float
Statements let/let mut with initializer, assignment to a local, a field or an element, print(e) for each printable type, if/else, while with a counter, for iN in a..b, break/continue as the last statement of a loop body, return
Functions up to MaxFunctions helpers f0.. with 1–3 parameters by value (the preamble's bump, sum4 and sum8 take &mut int, &[int; 4] and &[int; 8]), then fn main() -> int

Traps that AllowTraps may produce, all defined behavior with exit status 101 and a message the levels must agree on: overflow of checked + - *, division by zero, MIN / -1, a shift out of range, an index out of bounds. Every one is compared exactly by the fuzzer, message and column included: the column depends on the front end's spans, which is one of the things the ★ Rust front end is held to.

5. What the fuzzer does with a program

  1. ch24-gen --seed s (a generator failure, including TODO(ch24), ends the run with status 2);
  2. pebblec --emit=pir must accept it; pir-opt --verify-only must accept the PIR: otherwise a front-end failure (a generator bug under R2, or a front-end bug);
  3. pir-run is the oracle: its stdout, stderr and exit status; an interpreter diagnostic (pir-run: error: … on stderr: status 70 for undefined behavior, 1 for an interpreter error or a resource limit) is reported as a front-end failure, a timeout (120 s) as status 124. A bare exit status is main's return value, whatever it is: a program that returns 1 is compared like any other;
  4. for every level, pebblec <level> must produce an executable whose stdout, stderr and status equal the oracle's; a mismatch is a difference, and the program, PIR and the IR of every level stay in --keep for reduction (Chapter 12's ddmin) and bisection (pebblec --passes='<fewer stages>').

The summary line's format is fixed (the tests match it): fuzz: <n> programs, <k> traps, <d> differences, <e> front-end failures; exit 0 iff every seed agreed, 2 if the generator or front end failed.

6. What the tests check

Test What
ch24.Generator.ProgramsAreAcceptedAndTerminate seeds 1–150: accepted, verified, interpreted to a return or a trap; more than 50 return, at least one traps (R2–R4)
ch24.Generator.TrapFreeModeNeverTraps seeds 1–400 with AllowTraps = false all return (R5)
ch24.Generator.PrintsSomething seeds 1–40 contain print( (R4)
ch24.Generator.Deterministic same seed, same text; seeds 1 and 2 differ (R1)
ch24.Generator.OptionsAreRespected no helpers, no loops with the small options (R6)
tests/ch24/lit/gen-cli.test ch24-gen --seed 5 twice gives the same file; --count 3 -o DIR writes p1.pbl..p3.pbl; the program is accepted
tests/ch24/lit/fuzz-run.test seeds 1–30 with traps and 100–109 without: 0 differences, 0 front-end failures at -O0, -O1, -O2
tests/ch24/lit/bench-smoke.test bench.py --quick on two programs prints the table and the levels agree
ch24.e2e the eight benchmark programs, each at the three levels, against their EXPECT-STDOUT lines

7. Milestones

  1. Straight-line main. Integer lets, arithmetic, print. Deterministic and PrintsSomething pass; fuzz.py --count 20 agrees.
  2. Control flow. if, while with a counter, for, break/continue; MaxLoopDepth. Watch R3: the first infinite loop is usually a counter reassigned in the body.
  3. Types. bool, float (printing is the runtime's; no level uses fast-math flags, so the levels must agree bit for bit), arrays with masked indices, the struct.
  4. Functions. Helpers with parameters by value; calls to the preamble's bump(&mut v, k), sum4(&a), sum8(&a); tri recursion with a masked argument. ProgramsAreAcceptedAndTerminate passes.
  5. Traps. Checked operators on arbitrary data; AllowTraps = false switches to the wrapping forms and masks (R5). TrapFreeModeNeverTraps passes; fuzz-run.test passes.
  6. Run it for real. 500 seeds with traps, 100 without, then --gen-arg=--max-statements --gen-arg=30 for larger programs (the = form, so that the option parser does not read --max-statements as one of its own). Keep any witness.

8. Measurement

bench.py on inputs/bench/: bench-fib (recursion), bench-collatz (a while with a data-dependent trip count), bench-sieve (an array in a loop nest), bench-matmul (24×24 products in a triple loop through array references), bench-sort (insertion sort through &mut), bench-nbody (floats), bench-structs (struct copies and field updates), bench-checks (arithmetic whose overflow checks are provable). For each program and level: compile time, run time (minimum of --repeat), LLVM instructions, object size. Report:

Program -O0 ms -O1 ms -O2 ms O1 speedup O2 speedup instr O0/O1/O2 traps O0/O1/O2

(the trap column is grep -c pebble_trap on --emit=llvm; Lesson 24.2's static check elimination), plus the geometric means, and three sentences (exercises.md E2). The reference's numbers: geometric-mean speedup 3.6× (-O1) and 4.1× (-O2); -O1 keeps 1.3× the instructions of -O2; compile time 1.2–2.2× (-O1) and 1.3–2.9× (-O2) that of -O0. Wall-clock on a shared machine: compare ratios, and re-run when the numbers move.

9. Hints

  1. Generate into a type: expr(Type, Depth) chooses among the forms that produce Type; at Depth == 0 only literals and variables of that type. Keep the environment as a vector of (name, type, mutable) and a scope stack.
  2. Record loop counters as immutable in the environment (they are declared let mut for the increment, but no generated statement may assign them).
  3. For &mut arguments, borrow a variable that no other live borrow names: the simplest rule is "only a call's own argument list", and only one &mut per call.
  4. Emit the preamble (struct P, tri, bump, sum4, sum8) verbatim at the top of every program; the tests' regexes distinguish generated loops (for iN in) from the preamble's (for i in).
  5. Masks: (e & 7) for a shift, (e & (N-1)) for an index into [int; N] with N a power of two, ((e & 7) + 1) for a divisor. With AllowTraps choose between the masked and the raw form per site.
  6. To keep AllowTraps programs from trapping too early, put the risky operators late in main and use small literals: R4 wants more than a third of the corpus to return.
  7. When fuzz.py reports a difference, first re-run the kept program by hand at the failing level with --passes='pebble-o1<trace>' to see which stage changed the instruction count last; then --passes= with the stages up to that one.

10. Stretch goals

  • Generate struct definitions and arrays of structs; strings and interpolation (e2e-str-interp.pbl is the model).
  • Minimize witnesses automatically: call Chapter 12's ddmin on the program text with "still differs" as the predicate.
  • Run alive-tv on every kept program's intraprocedural stages (Lesson 24.7, Algorithm 24.7.5) and count the failed-to-prove cases; unroll with --src-unroll=8 --tgt-unroll=8 for the loops.