Lesson 12.7 — Test-case reduction and bisection¶

Techniques: delta debugging, ddmin (Zeller and Hildebrandt 2002); C-Reduce, a transformation-based reducer for C (Regehr et al. 2012); llvm-reduce, LLVM's IR reducer, and its predecessor bugpoint; bisection over passes (-opt-bisect-limit, -print-changed) and over commits (git bisect) · Pebble implements: the lab's Part B: your ddmin behind the ch12-reduce tool, compared with llvm-reduce and C-Reduce on a planted crash (labs/ch12-testing) · Drill: ddmin-trace · Prerequisites: Lesson 12.5 · Time: 4–6 hours

A fuzzer's crash is a 1 600-line Csmith program; a miscompile report is a 20 000-line preprocessed file; a regression appeared somewhere in 400 commits and 120 passes. Nobody can debug that. Reduction shrinks the input while the failure persists; bisection shrinks the search space — which pass, which commit — by binary search. Both are mechanical, and both have precise guarantees: ddmin returns an input from which no single element can be removed, and bisection over a monotone history needs $\lceil \log_2 n \rceil$ tests.

1. Problem and motivation¶

Delta debugging (ddmin)¶

Given a failing input made of $n$ parts (lines, tokens, bytes, changes) and a test that says whether the failure still happens, find a small failing subset. Trying all subsets is $2^n$ tests. Zeller and Hildebrandt's ddmin [ZH02] generalizes binary search: split the input into $n$ chunks, try each chunk and each complement, and refine the granularity when nothing fails. It needs no knowledge of the input format, handles unresolved test outcomes (the input no longer compiles), and guarantees 1-minimality: removing any single part makes the failure disappear.

C-Reduce¶

On C programs, line- or token-level ddmin gets stuck: removing a } alone breaks compilation, so a function can only be deleted if all its lines go at once. Regehr et al.'s C-Reduce [RCC+12] instead applies transformations that know C — remove a function, inline a call, replace an expression by a constant, rename identifiers, remove an argument — each tried at every position, and repeats all of them until no transformation makes the file smaller while still interesting. It is the standard reducer for compiler bugs found by Csmith (Lesson 12.5).

llvm-reduce and bugpoint¶

For LLVM IR, the natural parts are functions, blocks, instructions, operands, attributes and metadata, and every candidate must still be valid IR. llvm-reduce runs one delta pass per kind of entity, each a chunk-based ddmin over that kind, and repairs the IR so it always verifies [LLVM-Reduce]. Its predecessor bugpoint combined reduction with automatic miscompilation diagnosis (splitting a module between a "safe" and a "test" compiler); it was hard to use, and LLVM 23's release notes record its removal in favor of llvm-reduce [LLVM-RN23, LLVM-BugpointRedesign].

Bisection¶

When a pipeline of $n$ passes miscompiles, which pass is to blame? LLVM numbers every optional pass execution and -opt-bisect-limit=k skips all executions after the $k$-th; a binary search on $k$ finds the first execution whose inclusion breaks the program [LLVM-OptBisect]. -print-changed then shows what that pass did. The same search over a version history is git bisect, which checks out the midpoint commit of a good/bad range and asks a script [GitBisect].

2. Definitions and algorithms¶

Delta debugging (ddmin)¶

Definition 12.7.1 (Configuration, test)

An input is a sequence of elements $c_{\mathsf{x}} = \langle x_1, \dots, x_N \rangle$; a configuration is a subset $c \subseteq \{1, \dots, N\}$, meaning the input made of the chosen elements in their original order. A test is a function $\mathrm{test} : 2^{\{1..N\}} \to \{\mathsf{fail}, \mathsf{pass}, \mathsf{unres}\}$ ("the failure occurs", "it does not", "cannot tell", e.g. the input does not compile). Preconditions of reduction: $\mathrm{test}(\{1..N\}) = \mathsf{fail}$ and $\mathrm{test}(\emptyset) \ne \mathsf{fail}$.

Definition 12.7.2 (Minimality)

A failing configuration $c$ is 1-minimal if $\mathrm{test}(c \setminus \{e\}) \ne \mathsf{fail}$ for every $e \in c$; $k$-minimal if removing any nonempty set of at most $k$ elements makes it not fail; and globally minimal if no failing configuration is smaller.

Algorithm 12.7.3 (ddmin, with the course's conventions)

Input: $N \ge 1$ and a test (Definition 12.7.1).
Output: a 1-minimal failing configuration (Theorem 12.7.8).
Precondition: $\mathrm{test}(\{1..N\}) = \mathsf{fail}$, $\mathrm{test}(\emptyset) \ne \mathsf{fail}$.
Postcondition: $\mathrm{test}(c) = \mathsf{fail}$ and $c$ is 1-minimal; no configuration was tested twice.
Invariant: $\mathrm{test}(c) = \mathsf{fail}$ and $2 \le n \le \lvert c \rvert$ at the start of every round with $\lvert c \rvert \ge 2$.

function DDMin(N, test):
    c ← ⟨1, ..., N⟩; n ← 2
    cache ← {c ↦ fail}                        # every lookup below goes through the cache
    while |c| ≥ 2:
        Δ_1..Δ_n ← Split(c, n)
        if some Δ_i (first in order) has test(Δ_i) = fail:          # reduce to subset
            c ← Δ_i; n ← 2
        else if n > 2 and some ∇_i = c \ Δ_i (first in order) has test(∇_i) = fail:   # reduce to complement
            c ← ∇_i; n ← max(n − 1, 2)
        else if n < |c|:                                           # increase granularity
            n ← min(2n, |c|)
        else:
            break                                                   # n = |c|: 1-minimal
        n ← min(n, |c|)
    return c

function Split(c, n):                          # Zeller's split: sizes floor(|c|/n) first
    start ← 0; parts ← ⟨⟩
    for i ← 0 to n − 1:
        size ← (|c| − start) div (n − i)
        parts ← parts · ⟨c[start .. start + size − 1]⟩; start ← start + size
    return parts

For $n = 2$ the complements are the two subsets, which is why they are skipped. The lab's C++ contract pebble::reduce::ddmin (labs/ch12-testing/include/pebble/Reduce/DDMin.h) and the drill oracle tools/course/lib/ddmin.py follow these conventions.

C-Reduce¶

Algorithm 12.7.4 (C-Reduce's fixpoint over transformation passes, after [RCC+12])

Input: a file $F$ and an interestingness test (exit status 0 = interesting).
Output: a file $F^{\star}$ that is interesting and a fixpoint of all passes.
Precondition: $F$ is interesting.
Postcondition: no single transformation of any pass, applied to $F^{\star}$, yields an interesting file smaller than $F^{\star}$ (Theorem 12.7.11).
Invariant: the current file is interesting; its size never increases.

function CReduce(F, interesting, passes):     # passes: lines at several granularities, blank, comments,
    repeat                                    # clex tokens (rm-toks-k, rename-toks), balanced parens/braces,
        size_before ← |F|                     # clang_delta transformations (remove function, inline, ...)
        for p in passes:
            state ← p.new(F)
            while state ≠ STOP:
                (G, result) ← p.transform(F, state)    # the transformation at position "state"
                if result = OK and |G| < |F| and interesting(G):
                    F ← G                              # keep; same state now points at new text
                else:
                    state ← p.advance(F, state)        # try the next position
    until |F| = size_before                            # a full round without progress
    return F

llvm-reduce and bugpoint¶

Algorithm 12.7.5 (llvm-reduce: chunked delta passes, runDeltaPass)

Input: an IR module $M$ and an interestingness test.
Output: a smaller module that verifies and is interesting.
Precondition: $M$ verifies and is interesting.
Postcondition: the output verifies and is interesting; the last round did not lower the complexity score, or --max-pass-iterations (default 5) rounds were run.
Invariant: the current module verifies and is interesting.

function LLVMReduce(M, interesting):
    rounds ← 0
    repeat
        old ← ComplexityScore(M); rounds ← rounds + 1
        for kind in [functions, function bodies, global values, global initializers, basic blocks,
                     instructions, operands (to undef/0/1/args), attributes, metadata, ..., sink-defs-to-uses]:
            targets ← the entities of this kind in M, numbered 0..k−1
            chunks ← [ [0, k) ]
            while some chunk has length ≥ 1:
                for each chunk C (in order):
                    M' ← M with the entities of C removed or simplified, then repaired to verify
                    if interesting(M'): M ← M'; renumber; drop C
                split every remaining chunk in two halves   # ddmin-like refinement, no complements
    until ComplexityScore(M) ≥ old or rounds = MaxPassIterations
    return M

Bisection¶

Definition 12.7.6 (Monotone history)

A history is a sequence of states $v_0, v_1, \dots, v_n$ (the pipeline truncated after $k$ optional pass executions, $k = 0..n$; or commits in order). A predicate $\mathrm{bad}$ is monotone on it if $\mathrm{bad}(v_i) \Rightarrow \mathrm{bad}(v_j)$ for all $i \le j$, with $\neg\mathrm{bad}(v_0)$ and $\mathrm{bad}(v_n)$. The first bad state is the least $i$ with $\mathrm{bad}(v_i)$.

Algorithm 12.7.7 (Bisection)

Input: a history $v_0..v_n$ with $\neg\mathrm{bad}(v_0)$ and $\mathrm{bad}(v_n)$; a test returning good, bad or skip.
Output: the first bad state (for a monotone predicate without skips).
Precondition: $\mathrm{bad}$ is monotone (Definition 12.7.6).
Postcondition: $\neg\mathrm{bad}(v_{\mathrm{lo}})$, $\mathrm{bad}(v_{\mathrm{hi}})$ and $\mathrm{hi} = \mathrm{lo} + 1$.
Invariant: $\neg\mathrm{bad}(v_{\mathrm{lo}}) \land \mathrm{bad}(v_{\mathrm{hi}})$; $\mathrm{hi} - \mathrm{lo}$ at least halves (rounded up) per test.

function Bisect(lo = 0, hi = n):
    while hi − lo > 1:
        mid ← (lo + hi) div 2
        case test(v_mid):
            bad:  hi ← mid
            good: lo ← mid
            skip: choose another untested m in (lo, hi) (git: near mid), or give up and report the range
    return hi                                  # opt-bisect: -opt-bisect-limit=hi shows the culprit as its last pass

3. Worked example¶

ddmin on ten elements. The failure needs elements 2 and 8 together (./course drill ddmin-trace --seed 1 --difficulty medium). The trace of Algorithm 12.7.3, one row per round (P = pass, F = fail; "cached" tests cost nothing):

round	$c$	$n$	tests	action
1	{1, …, 10}	2	Δ1 {1..5} P; Δ2 {6..10} P	granularity 4
2	{1, …, 10}	4	Δ1 {1,2} P; Δ2 {3,4} P; Δ3 {5,6,7} P; Δ4 {8,9,10} P; ∇1 {3..10} P; ∇2 {1,2,5..10} F	complement 2
3	{1,2,5,6,7,8,9,10}	3	Δ1 {1,2} P cached; Δ2 {5,6,7} P cached; Δ3 {8,9,10} P cached; ∇1 {5..10} P; ∇2 {1,2,8,9,10} F	complement 2
4	{1,2,8,9,10}	2	Δ1 {1,2} P cached; Δ2 {8,9,10} P cached	granularity 4
5	{1,2,8,9,10}	4	Δ1 {1} P; Δ2 {2} P; Δ3 {8} P; Δ4 {9,10} P; ∇1 {2,8,9,10} F	complement 1
6	{2,8,9,10}	3	Δ1 {2}, Δ2 {8}, Δ3 {9,10}, ∇1 {8,9,10} P cached; ∇2 {2,9,10} P; ∇3 {2,8} F	complement 3
7	{2,8}	2	Δ1 {2} P cached; Δ2 {8} P cached; $n = \lvert c \rvert$	done

Result $\{2, 8\}$ after 17 distinct tests (a subset search would need up to $2^{10} = 1024$). Note round 3: after a complement reduction $n$ drops to $\max(n-1, 2) = 3$, and the three subsets were tested before.

Bisection over passes. The C function check(x) { return x + 1 > x; } has undefined behavior for x = INT_MAX; at -O0 it returns 0 there, at -O2 1. opt -O2 runs 181 counted pass executions; bisecting the limit $k$ (good = prints 0, as at -O0):

test	$k$	output	new range $(lo, hi]$
—	—	—	(0, 181]
1	90	1 (bad)	(0, 90]
2	45	1	(0, 45]
3	22	1	(0, 22]
4	11	1	(0, 11]
5	5	0 (good)	(5, 11]
6	8	1	(5, 8]
7	6	0	(6, 8]
8	7	0	(7, 8]

$\lceil \log_2 181 \rceil = 8$ tests; execution 8 is early-cse on check (§7). The "culprit" here is not a bug: the program has undefined behavior, and bisection only localizes where optimization exploited it.

Try it

./course drill ddmin-trace --seed 1 --difficulty medium --solution prints the table above; --difficulty hard adds unresolved outcomes ("5 without 2 does not compile").

4. Invariants and correctness¶

Theorem 12.7.8 (ddmin terminates with a 1-minimal failing configuration)

Under the preconditions of Algorithm 12.7.3, the loop terminates and the returned $c$ fails and is 1-minimal.

Proof

Invariant. Initially $c = \{1..N\}$ fails (precondition) and $n = 2 \le \lvert c \rvert$ when $\lvert c \rvert \ge 2$. Each reduction replaces $c$ by a configuration that was tested and failed; granularity steps keep $c$. The last line of the loop body restores $n \le \lvert c \rvert$, and $n \ge 2$ holds because every assignment gives $n \ge 2$. Termination. Order the pairs $(\lvert c \rvert, \lvert c \rvert - n)$ lexicographically: a reduction strictly decreases $\lvert c \rvert$ (a subset or complement of an $n$-way split with $n \ge 2$ and nonempty parts is a proper subset); a granularity step keeps $\lvert c \rvert$ and strictly increases $n$, decreasing $\lvert c \rvert - n \ge 0$. Both components are natural numbers, so the loop ends. 1-minimality. The loop ends either because $\lvert c \rvert = 1$ — then $c = \{e\}$ and $\mathrm{test}(c \setminus \{e\}) = \mathrm{test}(\emptyset) \ne \mathsf{fail}$ by the precondition — or at the break, when no subset and no complement failed and $n = \lvert c \rvert$. Then the split has $\lvert c \rvert$ parts of size 1, $\Delta_i = \{e_i\}$, and the complements are $\nabla_i = c \setminus \{e_i\}$. If $n > 2$ they were tested and none failed. If $n = 2 = \lvert c \rvert$, $c \setminus \{e_1\} = \{e_2\} = \Delta_2$ and $c \setminus \{e_2\} = \Delta_1$, which were tested and did not fail. Either way, removing any single element makes the test not fail. ∎

Theorem 12.7.9 (Test bound)

Algorithm 12.7.3 performs at most $3N^2 + 3N$ distinct tests on an input of $N$ elements.

Proof

A round at granularity $n$ performs at most $2n$ tests ($n$ subsets and at most $n$ complements). Group the rounds by the value $m$ of $\lvert c \rvert$ during them. Sizes only decrease, and every reduction changes the size, so the rounds with $\lvert c \rvert = m$ are consecutive, contain no reduction except possibly the last, and in all but the last the granularity doubles (capped at $m$): their values $n_1 < n_2 < \dots < n_t \le m$ satisfy $n_{i+1} \ge \min(2 n_i, m)$. Hence $n_{t-1} < m$, $n_{t-2} < m/2$, $n_{t-3} < m/4, \dots$, and $\sum_i n_i \le m + m(1 + \tfrac12 + \tfrac14 + \cdots) \le 3m$, so these rounds perform at most $6m$ tests. The sizes visited are distinct values in $\{2, \dots, N\}$ (size 1 performs no test), so the total is at most $\sum_{m=2}^{N} 6m \le 3N(N+1)$. ∎

Proposition 12.7.10 (Best case: one failure-inducing element)

If $\mathrm{test}(c) = \mathsf{fail} \iff e^{\star} \in c$ for one element $e^{\star}$, ddmin returns $\{e^{\star}\}$ after at most $2 \lceil \log_2 N \rceil$ tests.

Proof

With $n = 2$, $e^{\star}$ lies in $\Delta_1$ or $\Delta_2$; that subset fails, the algorithm reduces to it and sets $n = 2$ again, after at most 2 tests. The new size is $\lceil m/2 \rceil$ at most, so after $\lceil \log_2 N \rceil$ rounds the size is 1 and the loop stops. This is also Zeller and Hildebrandt's best case for their ddmin [ZH02]. ∎

How tight is Theorem 12.7.9?

Not very: the proof charges $2n$ tests to every round and ignores the cache. Zeller and Hildebrandt's own analysis of their ddmin [ZH02] gives a worst case of $\lvert c_{\mathsf{x}} \rvert^2 + 3\lvert c_{\mathsf{x}} \rvert$ tests for an input of $\lvert c_{\mathsf{x}} \rvert$ elements — the bad case is the finest granularity, where every removal is tried and only removing the last element still fails, so each round removes a single element — and the best case $2 \lceil \log_2 \lvert c_{\mathsf{x}} \rvert \rceil$ of Proposition 12.7.10. For the course's variant with its cache, the exact worst case can be computed by letting an adversary answer every new test with whichever of fail/not-fail maximizes the remaining work (a search over all answer sequences). For $N = 1, 2, \dots, 13$ it is 0, 2, 6, 12, 19, 28, 38, 48, 59, 72, 86, 101, 117 distinct tests, about $N^2/2 + 5N/2$ and below $N^2 + 3N$ in every case; the unit test test_exact_worst_case_small_n in tools/course/tests/test_ch12.py recomputes the values up to $N = 9$. Theorem 12.7.9 is kept because its proof is short and complete; the adversary values are computed, not proved, for larger $N$. The quadratic growth itself is real: the adversary forces about $m$ new complement tests at almost every size $m$.

Theorem 12.7.11 (C-Reduce and llvm-reduce terminate)

Algorithms 12.7.4 and 12.7.5 terminate with an interesting output. For C-Reduce the output is a fixpoint: in the final round no transformation of any pass produced a smaller interesting input. For llvm-reduce the output verifies, and either a whole round failed to lower the complexity score or the round limit was reached.

Proof

C-Reduce keeps a candidate only if it is interesting and strictly smaller ($\lvert G \rvert < \lvert F \rvert$), so the number of accepted changes is bounded by the initial size; between accepted changes each pass advances its finite state (a position in the file) and stops, so every round is finite, and a round with no accepted change ends the outer loop — the fixpoint property is exactly that round's failures. llvm-reduce: inside one delta pass, the chunk list is finite, a chunk that was removed is deleted from it, and when nothing was removed at the current granularity every chunk is split, until chunks have one element; so each pass terminates. The outer loop runs at most MaxPassIterations rounds and stops earlier when the complexity score does not decrease. Every accepted candidate was repaired to verify and tested interesting, which is the invariant. Note what this is not: a guarantee of global minimality — the lab's crash is reduced to 4 lines by C-Reduce but to 10 by line-level ddmin (§7). ∎

Theorem 12.7.12 (Bisection is optimal for monotone histories)

For a monotone predicate without skips, Algorithm 12.7.7 finds the first bad state with at most $\lceil \log_2 n \rceil$ tests, and no algorithm that learns only good/bad answers can do better in the worst case.

Proof

Correctness: the invariant holds initially by the precondition, each test keeps it by monotonicity (if $v_{\mathrm{mid}}$ is bad, everything after is bad; if good, everything before is good), and at the end $\mathrm{hi} = \mathrm{lo} + 1$ with $v_{\mathrm{lo}}$ good and $v_{\mathrm{hi}}$ bad, so $\mathrm{hi}$ is the first bad state. Cost: $\mathrm{hi} - \mathrm{lo}$ goes from $n$ to at most $\lceil (\mathrm{hi} - \mathrm{lo}) / 2 \rceil$ per test, reaching 1 after $\lceil \log_2 n \rceil$ tests. Lower bound: there are $n$ possible answers (first bad state $1..n$), each test has two outcomes, so a decision tree with fewer than $\lceil \log_2 n \rceil$ levels has fewer than $n$ leaves. ∎

Reducing a miscompile can introduce undefined behavior

A reducer that only checks "the two compilers still disagree" happily removes the initialization of a variable — and then the program has undefined behavior and the disagreement is no longer a bug (Theorem 12.5.10). The C-Reduce output in §7 reads an uninitialized b: fine for a crash, fatal for a miscompile. Interestingness tests for miscompiles must also reject programs with undefined behavior (C-Reduce's authors used the Frama-C and KCC checkers for this [RCC+12]; -fsanitize=undefined catches part of it).

5. Complexity¶

Let $N$ be the number of elements (lines, tokens, IR entities), $T$ the cost of one interestingness test, $n$ the history length, $s$ the input size in bytes.

Technique	Tests (worst)	Tests (typical)	Space	Notes
ddmin	$\le 3N^2 + 3N$ (Theorem 12.7.9)	$O(\log N)$ for a single cause (Prop. 12.7.10); lab: 195 tests for 53 lines	cache of tested configurations	all tests at $T$ each; the cache avoids repeats
C-Reduce	bounded by (accepted steps) × (positions per pass)	minutes to hours on real reports	a copy of the file	lab crash: 104 s at `--n 2` (§7)
llvm-reduce	per delta pass a chunk search over $k$ entities: $O(k)$ tests if most chunks are removable	seconds to minutes	modules in memory	lab crash: 8.5 s (§7)
Bisection	$\lceil \log_2 n \rceil$ (Theorem 12.7.12)	8 tests for 181 passes (§3)	—	each test compiles and runs the program

Justification. Theorems 12.7.9 and 12.7.12 and the proofs above. Pathological family for ddmin: a program in which every element is needed ($\mathrm{test}(c) = \mathsf{fail}$ iff $c = \{1..N\}$). ddmin must still establish 1-minimality: it refines to $n = N$ and tests all $N$ complements, $\Theta(N)$ tests for no reduction at all, and at each smaller granularity $2n$ more — $2(2 + 4 + \dots + N) < 4N$ tests in total. And the lab's crash shows the structural weakness: line-level ddmin keeps int manhattan(...) { and } because each alone breaks the parse and they can only go together — the result is 1-minimal but 2.5× the size of C-Reduce's.

Delta debugging (ddmin)¶

Isolation (dd): find a minimal difference between a passing and a failing input rather than a minimal failing input [ZH02]. Trade-off: two inputs needed.
Hierarchical delta debugging (Misherghi and Su, 2006): reduce a syntax tree level by level, so that whole subtrees go at once. Trade-off: needs a parser.
Complement-first and "zoom" variants (as in Zeller's later book [WPF]): test complements before subsets. Trade-off: different trace, same guarantee.

C-Reduce¶

C-Vise (a Python re-implementation of C-Reduce) and Perses/Vulcan (grammar-based reduction). Trade-off: portability versus C-specific power.
Parallel interestingness tests (--n): run several candidates at once. Trade-off: wasted work when one succeeds.

llvm-reduce and bugpoint¶

--delta-passes= selects deltas; --test-arg passes arguments to the test [LLVM-Reduce]. Trade-off: speed versus final size.
bugpoint's miscompilation mode split the module between a reference and a test compiler; llvm-reduce leaves miscompilation checks to the interestingness script [LLVM-BugpointRedesign]. Trade-off: flexibility versus built-in magic.
-mlir-pass-pipeline-crash-reproducer / mlir-reduce: the same ideas for MLIR.

Bisection¶

-opt-bisect-limit counts optional pass executions; -opt-disable=<pass> and -print-before=/-print-after= narrow further; -print-changed=diff prints only diffs [LLVM-OptBisect].
git bisect run with exit status 125 (skip) for commits that do not build [GitBisect]. Trade-off: the result may be a range.
Bisecting inlining decisions or LTO partitions (e.g. -bisect-limit style options in some compilers).

7. In real compilers¶

Delta debugging (ddmin)¶

Zeller's reference implementations accompany Why Programs Fail [WPF, Ch. 5]; libFuzzer's -minimize_crash minimizes byte inputs; the course's ch12-reduce (labs/ch12-testing/provided/ReduceMain.cpp) runs your pebble::reduce::ddmin over lines or tokens.

ddmin over lines on the lab's planted crash

Reproduce (the course build with the reference solution: ./course test 12 --solution; clang and opt 23.1.2; $SOL is that build: SOL=$PWD/build/ci-solutions-linux from the repository root, ci-solutions-macos on macOS):

export CLANG=clang-23 OPT=opt LABPLUGIN=$SOL/lib/Ch12LabPasses.so
wc -l < labs/ch12-testing/inputs/crash.c
$SOL/bin/ch12-reduce --stats --test=$PWD/labs/ch12-testing/inputs/crash-test.sh \
    labs/ch12-testing/inputs/crash.c

Output:

53
struct point {
};
int clamp(int v, int lo, int hi) {
}
int manhattan(struct point a, struct point b) {
}
int shifted(int v) {
  int w = v * 2;
  int u = w + 7 - 7;
}
ch12-reduce: 10 of 53 lines kept, 195 tests

What to notice: the crash (bug 3 of pebble-lab-fold: constants that cancel) needs only line int u = w + 7 - 7; and enough context to compile. The result is 1-minimal (Theorem 12.7.8; the lab's test checks every single-line removal), yet clamp and manhattan survive: removing one line of a function breaks compilation, and ddmin never removes the two lines together once the granularity is at single lines. struct point survives because manhattan's signature needs it. With --granularity=tokens the lab measures 1 653 tests and 119 of 205 tokens.

C-Reduce¶

csmith-project/creduce — creduce/creduce.in (the driver loop), creduce/pass_lines.pm, pass_clex.pm, clang_delta/ (the C/C++-aware transformations) [CReduce].

C-Reduce on the same crash

Reproduce (creduce 2.11.0 — Ubuntu 24.04: sudo apt install creduce; macOS: brew install creduce, which is 2.10.0 and may print other pass statistics; clang 23.1.2; test.sh wraps the lab's interestingness test; $SOL is the reference build of ./course test 12 --solution: SOL=$PWD/build/ci-solutions-linux from the repository root, ci-solutions-macos on macOS):

cp labs/ch12-testing/inputs/crash.c . && mkdir -p cr && mv crash.c cr/ && cd cr
cat > test.sh <<EOF
#!/bin/sh
CLANG=clang-23 OPT=opt LABPLUGIN=$SOL/lib/Ch12LabPasses.so \
  $PWD/../labs/ch12-testing/inputs/crash-test.sh crash.c
EOF
chmod +x test.sh
creduce --n 2 test.sh crash.c > log.txt 2>&1
grep -E 'method (pass_lines :: 0|pass_clex :: rename-toks) ' log.txt; cat crash.c

Output:

  method pass_clex :: rename-toks worked 2 times and failed 0 times
  method pass_lines :: 0 worked 8 times and failed 17 times
int a() {
  int b;
  b + 7 - 7;
}

What to notice: Algorithm 12.7.4's fixpoint: passes that delete lines, tokens and balanced groups, then rename identifiers (rename-toks: shifted → a), until a round makes no progress — 4 lines instead of ddmin's 10, in about 100 s instead of 12 s. The reduced program reads an uninitialized b: harmless for a crash, but the pitfall above explains why a miscompile test must reject it.

llvm-reduce and bugpoint¶

llvm/tools/llvm-reduce/deltas/Delta.cpp — runDeltaPass; one file per delta in llvm/tools/llvm-reduce/deltas/ (ReduceFunctions.cpp, ReduceInstructions.cpp, ...) [LLVM-DeltaSrc] (LLVM 23.1.2). bugpoint is no longer in the 23.1.2 release; its redesign document explains why [LLVM-BugpointRedesign].

llvm-reduce on the IR of the same crash

Reproduce (clang, opt and llvm-reduce 23.1.2; the course build with the reference solution; $SOL is that build: SOL=$PWD/build/ci-solutions-linux from the repository root, ci-solutions-macos on macOS):

export OPT=opt LABPLUGIN=$SOL/lib/Ch12LabPasses.so
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -w -S -emit-llvm \
    labs/ch12-testing/inputs/crash.c -o crash.ll
wc -l < crash.ll
llvm-reduce --test=$PWD/labs/ch12-testing/inputs/crash-test-ir.sh crash.ll -o reduced.ll > /dev/null 2>&1
sed -n '/^define/,/^}/p' reduced.ll

Output:

220
define i32 @shifted(i32 %0) {
entry:
  %add = add i32 %0, 7
  %sub = sub i32 %add, 7
  ret i32 %sub
}

What to notice: Algorithm 12.7.5 worked on IR entities: other functions, the alloca/load/store traffic, nsw flags, attributes and metadata are gone, and the operand of the add became an argument (%0) — a reduction no line-level reducer can express. The result is the minimal pattern for pebble-lab-fold<bug=3>: an add and a sub whose constants cancel.

Bisection¶

LLVM: llvm/lib/IR/OptBisect.cpp — OptBisect::shouldRunPass; llvm/lib/Passes/StandardInstrumentations.cpp — OptPassGateInstrumentation::shouldRun (the pass-manager side) and IRChangedPrinter (-print-changed) [LLVM-SI] (LLVM 23.1.2). Git: git bisect run [GitBisect].

opt-bisect-limit finds where -O2 exploits undefined behavior

Reproduce (clang, opt, lli 23.1.2):

cat > ub.c <<'EOF'
#include <stdio.h>
int check(int x) { return x + 1 > x; }
int main(void) {
  volatile int v = 2147483647;
  printf("%d\n", check(v));
  return 0;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm ub.c -o ub.ll
echo "O0: $(lli ub.ll)  O2: $(opt -O2 ub.ll | lli)"
lo=0; hi=$(opt -O2 -opt-bisect-limit=-1 -disable-output ub.ll 2>&1 | wc -l); good=$(lli ub.ll)
while [ $((hi - lo)) -gt 1 ]; do
  mid=$(((lo + hi) / 2)); out=$(opt -O2 -opt-bisect-limit=$mid ub.ll 2>/dev/null | lli)
  echo "limit $mid -> $out"; if [ "$out" = "$good" ]; then lo=$mid; else hi=$mid; fi
done
opt -O2 -opt-bisect-limit=$hi -print-changed -filter-print-funcs=check -disable-output ub.ll 2>&1 \
  | sed -n '/running pass (7)/,/PassManager<Function> on check ignored/p' | grep -v '^;'

Output:

O0: 0  O2: 1
limit 90 -> 1
limit 45 -> 1
limit 22 -> 1
limit 11 -> 1
limit 5 -> 0
limit 8 -> 1
limit 6 -> 0
limit 7 -> 0
BISECT: running pass (7) sroa on check
*** IR Dump After SROAPass on check ***
define dso_local i32 @check(i32 noundef %x) #0 {
entry:
  %add = add nsw i32 %x, 1
  %cmp = icmp sgt i32 %add, %x
  %conv = zext i1 %cmp to i32
  ret i32 %conv
}
BISECT: running pass (8) early-cse on check
*** IR Dump After EarlyCSEPass on check ***
define dso_local i32 @check(i32 noundef %x) #0 {
entry:
  %add = add nsw i32 %x, 1
  ret i32 1
}
*** IR Pass PassManager<Function> on check ignored ***

What to notice: Algorithm 12.7.7 over 181 counted executions in 8 tests (Theorem 12.7.12). -print-changed then shows the culprit: EarlyCSE (through InstSimplify) folds icmp sgt (add nsw x, 1), x to true — legal, because nsw makes overflow poison. Only optional passes carry a BISECT: number; required ones (the verifier, the pass managers) are never skipped (Lesson 12.1).

git bisect run with a test script

Reproduce (git 2.43.0; a throw-away repository with 16 commits, the 11^th introduces the bug):

git init -q gb && cd gb && git config user.email a@b.c && git config user.name demo
for i in $(seq 1 16); do
  if [ $i -lt 11 ]; then r=3; else r=2; fi
  echo "int shift(void) { return $r; }  /* rev $i */" > opt.c; git add opt.c
  GIT_AUTHOR_DATE="2026-01-$(printf %02d $i)T00:00:00" GIT_COMMITTER_DATE="2026-01-$(printf %02d $i)T00:00:00" \
    git commit -q -m "rev $i"
done
printf '#!/bin/sh\ngrep -q "return 3" opt.c\n' > test.sh && chmod +x test.sh
git bisect start HEAD HEAD~15 > /dev/null
git bisect run ./test.sh 2>&1 | grep -E '^Bisecting|is the first bad commit|^    rev'

Output:

Bisecting: 3 revisions left to test after this (roughly 2 steps)
Bisecting: 1 revision left to test after this (roughly 1 step)
Bisecting: 0 revisions left to test after this (roughly 0 steps)
c6c364d80da7fe12ceedfe3743a1f7808fec0526 is the first bad commit
    rev 11

What to notice: 15 commits, 4 tests (the first, at rev 8, is done by git bisect start's checkout and hidden here); the script's exit status is the predicate (0 good, 1–124 bad, 125 skip). Fixed dates and author make the commit hashes reproducible.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Delta debugging (ddmin)	1-minimal (Thm. 12.7.8), format-agnostic; stuck on structure (paired lines)	$O(\log N)$ best, $\le 3N^2 + 3N$ tests worst; lab: 195 tests for 53 lines	Readable only at the chosen granularity	Low (≈100 lines; the lab)	Byte inputs, change sets, line-level first cuts
C-Reduce	Fixpoint of C-aware transformations (Thm. 12.7.11); far smaller than ddmin	Minutes to hours; lab: ~100 s	Tiny, idiomatic C (may contain UB)	High (a tool) — use it	Csmith and user reports of C/C++ compiler bugs
llvm-reduce (bugpoint)	Fixpoint over IR entities; output always verifies	Seconds to minutes; lab: 8.5 s	Minimal IR tests ready for `llvm/test`	Low to use	Any LLVM crash or IR-level miscompile with a script
Bisection	Exact first bad state for monotone histories (Thm. 12.7.12)	$\lceil \log_2 n \rceil$ tests	One pass execution or one commit	Very low	Localizing a pass (`-opt-bisect-limit`) or a commit (`git bisect`)

Choose ddmin when the input has no structure a tool knows, or as a first cut; C-Reduce when the input is C/C++ (always, for compiler bugs); llvm-reduce when you can reproduce the problem on IR — it is faster and its output is already a test; bisection when you have a good and a bad end and a monotone predicate — before reducing, to know what you are reducing for.

9. Assessment¶

Quiz: ddmin-trace (sequence), ddmin-tests (number), ddmin-one-minimal, ddmin-bound, creduce-fixpoint, llvm-reduce-valid, bisect-steps (number), bisect-limits (sequence), llvm-where-optbisect.
Drill: ./course drill ddmin-trace (actions, result and test count; hard adds unresolved outcomes).
Flashcards: tags ddmin, creduce, llvm-reduce, bisection.
Lab: Part B, requirements R5–R9 of SPEC.md.
Find where LLVM does it: in llvm/lib/IR/OptBisect.cpp, which member function decides whether a pass runs?

References¶

See the chapter references.

Technique	Tests (worst)	Tests (typical)	Space	Notes
ddmin	\(\le 3N^2 + 3N\) (Theorem 12.7.9)	\(O(\log N)\) for a single cause (Prop. 12.7.10); lab: 195 tests for 53 lines	cache of tested configurations	all tests at \(T\) each; the cache avoids repeats
C-Reduce	bounded by (accepted steps) × (positions per pass)	minutes to hours on real reports	a copy of the file	lab crash: 104 s at `--n 2` (§7)
llvm-reduce	per delta pass a chunk search over \(k\) entities: \(O(k)\) tests if most chunks are removable	seconds to minutes	modules in memory	lab crash: 8.5 s (§7)
Bisection	\(\lceil \log_2 n \rceil\) (Theorem 12.7.12)	8 tests for 181 passes (§3)	—	each test compiles and runs the program

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Delta debugging (ddmin)	1-minimal (Thm. 12.7.8), format-agnostic; stuck on structure (paired lines)	\(O(\log N)\) best, \(\le 3N^2 + 3N\) tests worst; lab: 195 tests for 53 lines	Readable only at the chosen granularity	Low (≈100 lines; the lab)	Byte inputs, change sets, line-level first cuts
C-Reduce	Fixpoint of C-aware transformations (Thm. 12.7.11); far smaller than ddmin	Minutes to hours; lab: ~100 s	Tiny, idiomatic C (may contain UB)	High (a tool) — use it	Csmith and user reports of C/C++ compiler bugs
llvm-reduce (bugpoint)	Fixpoint over IR entities; output always verifies	Seconds to minutes; lab: 8.5 s	Minimal IR tests ready for `llvm/test`	Low to use	Any LLVM crash or IR-level miscompile with a script
Bisection	Exact first bad state for monotone histories (Thm. 12.7.12)	\(\lceil \log_2 n \rceil\) tests	One pass execution or one commit	Very low	Localizing a pass (`-opt-bisect-limit`) or a commit (`git bisect`)

Lesson 12.7 — Test-case reduction and bisection¶

1. Problem and motivation¶

Delta debugging (ddmin)¶

C-Reduce¶

llvm-reduce and bugpoint¶

Bisection¶

2. Definitions and algorithms¶

Delta debugging (ddmin)¶

C-Reduce¶

llvm-reduce and bugpoint¶

Bisection¶

3. Worked example¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

Delta debugging (ddmin)¶

C-Reduce¶

llvm-reduce and bugpoint¶

Bisection¶

7. In real compilers¶

Delta debugging (ddmin)¶

C-Reduce¶

llvm-reduce and bugpoint¶

Bisection¶

8. Comparison¶

9. Assessment¶

References¶