Skip to content

Lab 12 · Three oracles for one property, and a delta-debugging reducer

Chapter: 12 · Passes, Pass Managers & Testing Compilers · Lessons: 12.4, 12.5, 12.7 · Time: 8–12 hours · Tests: ./course test 12 (labels ch12, lab)

Goal

Part A compares three testing techniques on the same property. The system under test is the provided pass pebble-lab-fold (in the lab plugin Ch12LabPasses), which folds (x ± C1) ± C2 into one add (rule R1) and (x +nsw 1) > x into true (rule R2). pebble-lab-fold<bug=K> plants a known bug (see the header comment of provided/LabFold.cpp: 1 wrong constant, 2 R2 without the nsw check, 3 a crash when the constants cancel, 4 an equivalent but differently spelled result, 5 an unjustified nsw on the result). You write a FileCheck test, a snapshot suite and a differential tester, and the provided harness measures which bugs each detects. Part B implements Zeller and Hildebrandt's ddmin (Lesson 12.7, Algorithm 12.7.3) behind a one-function contract and uses it, through the provided tool ch12-reduce, to reduce a C file that crashes pebble-lab-fold<bug=3>; you then compare it with llvm-reduce (and ★ C-Reduce).

Requirements

Part A (your files in checks/, run by provided/mutation_matrix.py, ctest ch12.lab.matrix):

  • R1. checks/fold.ll is an IR file with FileCheck directives in comments. The harness runs opt -passes='pebble-lab-fold<bug=K>' -S checks/fold.ll | FileCheck checks/fold.ll. It must pass on bug 0 and bug 4 (bug 4 is semantically correct: check the property, not one spelling) and fail on bugs 1, 2, 3, 5.
  • R2. checks/snapshots/*.ll are inputs with reviewed snapshots *.ll.snap, created with provided/snap.py --update on the correct pass. They must pass on bug 0 and fail on bugs 1, 2, 3, 5 (bug 4 is not required either way: a snapshot cannot tell).
  • R3. checks/difftest.py is a differential tester with the CLI contract below. It generates random programs, runs each with lli before and after opt -passes=<pipeline>, and reports a difference. It must pass on bugs 0, 4 and 5 (no false alarms: generate only programs without undefined behavior or poison — no nsw/nuw flags, no division by possibly-zero values) and detect bugs 1, 2 and 3 with --seed 1 --count 100.
  • R4. Every check is deterministic (same seed, same verdict) and the whole matrix runs in under 5 minutes.

Part B (your code in src/, contract include/pebble/Reduce/DDMin.h):

  • R5. ddmin(N, Test) returns a configuration \(c\) (sorted indices) with Test(c) == Fail that is 1-minimal: for every \(e \in c\), Test(c \ {e}) != Fail (Definition 12.7.2).
  • R6. Every configuration passed to Test is sorted, nonempty and different from the whole input; no configuration is passed twice (cache outcomes); N == 1 returns {0} without calling Test.
  • R7. Unresolved outcomes are not failures: they neither reduce nor stop the search.
  • R8. At most \(3N^2 + 3N\) distinct tests (Theorem 12.7.9); a single failure-inducing element among \(N\) is found with at most \(2 \lceil \log_2 N \rceil\) tests (Proposition 12.7.10).
  • R9. ch12-reduce --test=inputs/crash-test.sh inputs/crash.c produces a C file that still crashes pebble-lab-fold<bug=3> and is 1-minimal with respect to line removal.

The contract

// labs/ch12-testing/include/pebble/Reduce/DDMin.h  (provided; do not change)
namespace pebble::reduce {
enum class Outcome { Pass, Fail, Unresolved };   // Fail = "the failure still occurs"
using TestFn = std::function<Outcome(std::span<const std::size_t> Config)>;
/// Preconditions: Test(all N elements) == Fail and Test(no element) != Fail.
/// Returns a 1-minimal failing configuration (sorted indices).
std::vector<std::size_t> ddmin(std::size_t N, const TestFn &Test);
}

usage: checks/difftest.py --opt OPT --lli LLI --plugin PLUGIN --pipeline PIPE --seed S --count N
exit status: 0 no difference in N programs; 1 a difference or a compiler failure (print the program);
             2 a tool error (e.g. a generated program does not run under lli before the pass)

Input and output formats

  • checks/fold.ll: textual LLVM IR (functions of your choice) plus ; CHECK...: comment lines. No RUN: line is needed; the harness supplies the pipeline.
  • checks/snapshots/NAME.ll and NAME.ll.snap: the snapshot is opt -S output with the ; ModuleID and source_filename lines removed and trailing whitespace stripped (provided/snap.py, function normalize).
  • ch12-reduce (provided, provided/ReduceMain.cpp): splits the input into lines (with their newline) or tokens (--granularity=tokens: a run of non-blanks plus the following blanks); runs <test> <tempfile> through the shell; exit 0 = interesting (Outcome::Fail), 125 = unresolved, anything else = pass; --stats prints ch12-reduce: <k> of <n> <unit> kept, <t> tests to stderr; exit 1 if the whole input is not interesting.

Provided infrastructure

File What it gives you
provided/LabFold.cpp the system under test, pebble-lab-fold<bug=K>, in plugin build/<preset>/lib/Ch12LabPasses.so
provided/snap.py a snapshot runner (check / --update), in the spirit of Turnt and insta
provided/mutation_matrix.py runs your three checks against bugs 0–5, prints the matrix, checks R1–R3 (--require)
provided/ReduceMain.cpp ch12-reduce, the file reducer around your ddmin
inputs/crash.c, inputs/crash-test.sh, inputs/crash-test-ir.sh the planted crash and its interestingness tests (C and IR); they need CLANG, OPT, LABPLUGIN in the environment

What the tests check

Test Checks
ch12.lab.matrix R1–R4: mutation_matrix.py --require on your checks/
ch12.DDMin.SingleElementIsReturnedWithoutTests R6 for \(N = 1\)
ch12.DDMin.OneFailureInducingElement, TwoElementsFarApart, WholeInputIsOneMinimal R5 on Zeller and Hildebrandt-style examples; R8's best case
ch12.DDMin.UnresolvedOutcomesAreNotFailures R7
ch12.DDMin.RandomMonotonePredicatesAreOneMinimal, RandomArbitraryPredicatesAreOneMinimal R5, R6, R8 on 3 000 random predicates (monotone, non-monotone, with unresolved outcomes)
ch12.DDMin.LogarithmicBestCase R8: one cause among 1 024 elements in at most 20 tests
ch12.lab (lit: tests/ch12/lab/) the provided pass's behavior; R9 on inputs/crash.c (still crashes, 1-minimal by line removal); ch12-reduce on tokens and its error exit

Milestones

  1. Part B first: implement ddmin — ctest --test-dir build/<preset> -R 'ch12.DDMin'.
  2. Reduce the crash — ctest --test-dir build/<preset> -R '^ch12.lab$'.
  3. checks/fold.ll, then snapshots (python3 labs/ch12-testing/provided/snap.py --opt $(which opt) --plugin build/<preset>/lib/Ch12LabPasses.so --update labs/ch12-testing/checks/snapshots, then read every .snap), then difftest.py — ctest ... -R ch12.lab.matrix --output-on-failure.
  4. Measure and fill in the tables below.
bug FileCheck snapshot differential
0 … 5
reducer kept tests time
ch12-reduce (lines)
ch12-reduce (tokens)
llvm-reduce (on clang -S -emit-llvm output, with inputs/crash-test-ir.sh)
★ C-Reduce

Hints

Hint 1 — where to start

Part B: write Split(c, n) and a cache first; trace the drill ./course drill ddmin-trace --seed 1 --solution and make your implementation produce the same rounds. Part A: run the plugin by hand on a few functions with each bug=K and look at the output before writing any check.

Hint 2 — the key idea

Part A: a FileCheck test is only as good as its negatives — bug 2 is caught only by a function that must not be folded (no nsw), bug 5 only by a check that pins the flags. A differential tester needs inputs at the boundaries (INT_MIN, INT_MAX, ±1, 0), because bug 2 differs only at INT_MAX (Lesson 12.5 §3). Part B: the 1-minimality proof (Theorem 12.7.8) tells you when to stop — only when \(n = \lvert c \rvert\) and no complement failed.

Hint 3 — a design sketch

Part B: std::map<std::vector<size_t>, Outcome> as the cache, std::set_difference for complements, a loop with the three cases of Algorithm 12.7.3. Part A: difftest.py = a generator of small functions over one i32 argument (chains of add/sub by constants, some pairs that cancel, some (x + 1) > x comparisons without nsw) and a main that prints the function on a fixed list of inputs; compare lli outputs, and treat an opt failure as a difference.

Stretch goals ★

  • Run C-Reduce on inputs/crash.c and explain why it beats line-level ddmin (Lesson 12.7 §7).
  • Add a fourth oracle to the matrix: validate pebble-lab-fold's output with chapters/12-passes-and-testing/examples/tv.py; which bugs does it detect?
  • Implement hierarchical delta debugging on brace-nested blocks and compare the result size.