Lesson 12.5 — Snapshot and differential testing, and random program generators¶

Techniques: snapshot (golden-file) testing (Turnt, insta); differential testing (McKeeman 1998); random program generation for compilers: Csmith (C programs free of undefined behavior), YARPGen (value-tracking generation policies), llvm-stress (random LLVM IR for crash testing) · Pebble implements: the lab's Part A: one property of pebble-lab-fold tested as FileCheck, snapshot and differential tests, measured against five planted bugs (labs/ch12-testing) · Drill: none (see §9) · Prerequisites: Lesson 12.4 · Time: 4–5 hours

A FileCheck test checks what its author thought of. Two other oracles need no such foresight. A snapshot records the whole output once and flags any later change; a differential test runs the same program through two implementations (two compilers, two optimization levels, before and after a pass) and flags any disagreement. The second oracle needs programs, many of them, which is why random program generators exist; and their programs must be free of undefined behavior, or a "disagreement" means nothing. Csmith found more than 325 bugs in GCC and LLVM this way in its first three years [YCER11]. This lesson develops the three ideas and measures them against each other on the same property and the same planted bugs.

1. Problem and motivation¶

Snapshot testing¶

When a whole output matters (a pretty-printer, a diagnostic, a small function's optimized IR), writing checks for every line is the job of a machine. A snapshot test stores the output as a golden file; the test fails when the output differs, prints a diff, and a reviewer either fixes the code or accepts the new output. Cornell's Turnt runs commands over files and compares their outputs with .out files [Turnt]; Rust's insta stores snapshots next to the code with a review tool (cargo insta review) [Insta]. update_test_checks.py (Lesson 12.4) is a snapshot generator in FileCheck clothing.

Differential testing¶

For a compiler, the specification — "the compiled program behaves as the language standard says" — is not executable. McKeeman's insight [McK98] was that two compilers (or one compiler at two optimization levels) are each an approximation of the specification, and a program on which they disagree exposes a bug in at least one of them, with no human-written expected output. It turns every program into a test.

Csmith¶

Random C programs almost always have undefined behavior (signed overflow, out-of-bounds access, unsequenced side effects), and then disagreement is allowed. Yang, Chen, Eide and Regehr's Csmith [YCER11] generates programs that are UB-free by construction — safe-math wrappers for arithmetic, a pointer analysis during generation, conservative effect analysis — and that print a checksum of all global variables at exit, so miscompilations show up as different checksums.

YARPGen¶

Csmith's programs have a characteristic shape, and compilers were tuned until Csmith stopped finding bugs. Livinskii, Babokin and Regehr's YARPGen [LBR20] attacks optimizations Csmith rarely reaches (loops with arrays, vectorizable code) with generation policies that bias the program toward patterns optimizations look for, and it avoids UB differently: it computes the value of every expression while generating it and rewrites an operation whose result would overflow.

llvm-stress¶

At the IR level, LLVM ships llvm-stress [LLVM-Stress], which emits a random, verifier-clean function built from a random mix of instructions. Its programs are not meant to be run (they read through pointer arguments); they are for crash testing passes and back ends: opt or llc must not crash or produce invalid IR.

2. Definitions and algorithms¶

Definition 12.5.1 (Oracle, false alarm, missed bug)

Let $C$ be a compiler (or pass) under test, $\mathcal{I}$ a set of inputs and, for $x \in \mathcal{I}$, $\mathrm{ok}(C, x) \in \{\mathsf{true}, \mathsf{false}\}$ whether $C$ handles $x$ correctly. A test oracle is a predicate $O(C, x)$ ("the test passes"). $O$ raises a false alarm on $x$ if $\neg O(C, x) \land \mathrm{ok}(C, x)$, and misses a bug on $x$ if $O(C, x) \land \neg \mathrm{ok}(C, x)$.

Snapshot testing¶

Definition 12.5.2 (Snapshot oracle)

A snapshot of $C$ on $x$ is a normalized output $g_x = \nu(C_0(x))$ recorded from a reviewed version $C_0$, where $\nu$ removes nondeterministic parts (file names, timestamps). The snapshot oracle is $O_{\mathrm{snap}}(C, x) \iff \nu(C(x)) = g_x$.

Algorithm 12.5.3 (Snapshot testing with review)

Input: inputs $x_1, \dots, x_k$; recorded snapshots $g_{x_i}$ (possibly missing); a mode check or accept.
Output: pass/fail per input and diffs; in accept mode, updated snapshots.
Precondition: $\nu$ makes the output deterministic.
Postcondition: in check mode, input $x$ passes iff $\nu(C(x)) = g_x$.
Invariant: a snapshot changes only in accept mode, i.e. only after review.

function Snapshot(inputs, mode):
    failed ← false
    for x in inputs:
        out ← ν(C(x))
        if mode = accept: g[x] ← out; continue       # the human review step
        if x ∉ dom(g): report "missing snapshot"; failed ← true
        else if out ≠ g[x]: print UnifiedDiff(g[x], out); failed ← true
    return failed

Differential testing¶

Definition 12.5.4 (Well-defined program, differential oracle)

A program $P$ with input $i$ is well defined if its behavior under the language semantics is a single observable result $\llbracket P \rrbracket(i)$ (terminating, deterministic, no undefined, unspecified or implementation-defined behavior that the observations can see). Two compilers $C_1, C_2$ conform on $P$ if running $C_j(P)$ on $i$ yields $\llbracket P \rrbracket(i)$. The differential oracle is $O_{\mathrm{diff}}(P, i) \iff \mathrm{run}(C_1(P), i) = \mathrm{run}(C_2(P), i)$.

Algorithm 12.5.5 (Differential testing with a generator)

Input: compilers (or configurations) $C_1, \dots, C_k$; a generator $\gamma$ of well-defined programs; a seed; a budget $N$.
Output: the first program (and seed) on which the configurations disagree, or "no difference".
Precondition: $\gamma$'s programs are well defined (Definition 12.5.4) and terminate within the timeout.
Postcondition: every reported program exposes a bug in at least one $C_j$ (Theorem 12.5.10).
Invariant: all programs before the current one produced identical results under every $C_j$.

function DiffTest(C_1..C_k, γ, seed, N):
    rng ← Random(seed)
    for n ← 1 to N:
        P ← γ(rng)
        results ← [ Run(C_j(P), timeout) for j in 1..k ]   # a compiler crash is a result too
        if results are not all equal:
            return (P, n, results)                           # then reduce it (Lesson 12.7)
    return "no difference"

Csmith¶

Algorithm 12.5.6 (Csmith-style generation of UB-free programs, after [YCER11])

Input: a seed; limits on size and nesting.
Output: a C program that prints a checksum of its global state.
Precondition: safe-math wrappers are available (csmith.h: safe_add_func_int32_t_s_s and friends).
Postcondition: the program is well defined for its (fixed) input: no signed overflow, no division by zero, no invalid pointer dereference, no unsequenced conflicting accesses.
Invariant: after generating each statement, the generator's points-to facts and effect summaries over-approximate what the program can do so far.

function Csmith(seed):
    emit random struct/union types and global variables with random initial values
    emit functions top-down: func_1 calls functions generated later
    GenerateStatement(ctx):
        choose a statement kind (assignment, if, for, return, call, block) by weighted random choice
        choose operands: variables in scope, constants, pointer dereferences whose points-to set is valid
        wrap every arithmetic operator on signed values in a safe_* macro (overflow → a defined result)
        reject the candidate if the effect analysis finds an unsequenced read/write conflict or a possibly
            invalid pointer (then retry another random choice)
        update points-to facts and effects
    emit main: call func_1, then hash every global into a checksum and print it

YARPGen¶

Algorithm 12.5.7 (YARPGen-style generation with value tracking, after [LBR20])

Input: a seed; generation policies (probability tables per code region).
Output: a C/C++ program func.c + driver.c (inputs, a test function, a hash of the results).
Precondition: all inputs are fixed values chosen by the generator.
Postcondition: every expression evaluates without UB on those inputs.
Invariant: the generator knows the concrete value of every variable at every point it generates (it interprets the program as it builds it).

function GenerateExpr(policy, env):
    e ← random expression tree drawn from policy (operators, operand kinds, common subexpressions, arrays)
    v ← Evaluate(e, env)                        # concrete values of all variables are known
    while Evaluate reports UB at some node n (overflow, shift ≥ width, division by 0):
        rewrite n by a UB-free alternative (e.g. + → -, or change the shift amount)
        v ← Evaluate(e, env)
    return (e, v)

function GenerateLoop(policy):
    pick bounds and an induction variable with known trip count
    generate a body over arrays indexed by the induction variable, applying the policy
    (vectorizable patterns, reductions, reuse of subexpressions)

llvm-stress¶

Algorithm 12.5.8 (llvm-stress, llvm/tools/llvm-stress/llvm-stress.cpp)

Input: a seed and a size $s$ (number of instruction-creating steps).
Output: one function autogen_SD<seed> in a verifier-clean module.
Precondition: none.
Postcondition: the module passes opt -passes=verify.
Invariant: a pool of already defined values of various types from which operands are drawn; every new instruction is type-correct given its operands.

function LLVMStress(seed, s):
    F ← function autogen_SD<seed>(ptr, ptr, ptr, i32, i64, i8); pool ← arguments, some allocas
    repeat s times:
        M ← a random Modifier: Load, Store, BinOp, Const, Alloca, ExtractElement, InsertElement,
            ShuffleVector, Cast, Select, Cmp
        M.act(pool)                               # create one instruction from pool values, add it to pool
    for each i1 value v of the block, in random order:          # IntroduceControlFlow
        split the block after v; end the first half with "br i1 v, <itself>, <next>" (a self-loop)
    run the verifier; return module

3. Worked example¶

The lab's system under test is pebble-lab-fold (Lesson 12.4 §9): rule R1 folds (x ± C1) ± C2 into one add, rule R2 folds (x + 1) > x into true when the add has nsw. Its planted bugs are: (1) a wrong constant, (2) R2 without the nsw check, (3) a crash when the constants cancel, (4) an equivalent but different spelling (sub x, -C), (5) an nsw flag added to R1's result (poison, no value change).

Differential testing, one step. difftest.py --seed 1 (the reference solution of the lab) generates, as its first program under bug 2:

define i32 @f(i32 %x) {
  %v1 = add i32 %x, 1
  %v2 = icmp slt i32 %x, %v1
  %v3 = zext i1 %v2 to i32
  %v4 = add i32 %x, %v3
  ret i32 %v4
}

and calls it on 15 inputs. Before and after the pass (evaluated with lli):

$x$	$x + 1$ (wraps)	`x < x+1` before	after bug 2 (`true`)	$f(x)$ before	$f(x)$ after
−2147483648	−2147483647	1	1	−2147483647	−2147483647
−1	0	1	1	0	0
0	1	1	1	1	1
2147483646	2147483647	1	1	2147483647	2147483647
2147483647	−2147483648	0	1	2147483647	−2147483648
(6 random values)		1	1	equal	equal

Only x = INT_MAX distinguishes the two programs, so a tester with uniformly random 32-bit inputs would need about $2^{32}$ tries per program; the boundary list finds it in the first program. The program itself is well defined (no nsw, so x + 1 wraps), which is what makes the difference a bug (Theorem 12.5.10).

The comparison matrix. Running the three reference tests of the lab against the six variants (ctest -R ch12.lab.matrix, about 20 s):

bug	FileCheck (`checks/fold.ll`)	snapshot (`checks/snapshots/`)	differential (`checks/difftest.py`)
0 (correct)	pass	pass	pass
1 (wrong constant)	detected	detected	detected
2 (missing `nsw` check)	detected (negative test `@succ_wrap`)	detected	detected (INT_MAX)
3 (crash)	detected	detected	detected
4 (equivalent new spelling)	pass (checks allow both spellings)	detected (a false alarm)	pass
5 (`nsw` added: poison only)	detected (the NEXT line pins the flags)	detected	pass (a miss: `lli` never shows poison)

Snapshot is the most sensitive and raises the only false alarm; the differential test has no false alarm and misses exactly the bug that is invisible at run time; FileCheck is as good as the author's foresight (two of its detections exist only because the solution wrote a negative test and a flag-sensitive CHECK-NEXT). Lesson 12.8's translation validation detects bug 5 too.

4. Invariants and correctness¶

Proposition 12.5.9 (Snapshots: no misses among output changes, every change alarms)

For every $C$ and $x$ with a snapshot, $O_{\mathrm{snap}}(C, x)$ fails iff $\nu(C(x)) \ne g_x$. Hence the snapshot oracle misses a bug on $x$ only if the wrong output equals the reviewed one, and it raises a false alarm on every correct change of the normalized output.

Proof

Immediate from Definition 12.5.2 and Algorithm 12.5.3's postcondition: the verdict is equality of the normalized output with $g_x$. A bug that changes the normalized output makes them unequal (a detection); a correct change does too (a false alarm, Definition 12.5.1); a bug that leaves the output equal to $g_x$ — including one already present when $g_x$ was accepted — passes. ∎

Theorem 12.5.10 (Differential oracle soundness)

If $P$ is well defined on $i$ (Definition 12.5.4) and $\mathrm{run}(C_1(P), i) \ne \mathrm{run}(C_2(P), i)$, then $C_1$ or $C_2$ does not conform on $P$. If $P$ is not well defined, a disagreement implies nothing.

Proof

If both conformed, both runs would equal the single result $\llbracket P \rrbracket(i)$ and hence each other, contradicting the disagreement. If $P$ has undefined behavior on $i$, the semantics permits any result from each compiler (Chapter 9, Lesson 9.7), so two different results are both conforming: the example return x + 1 > x; with x = INT_MAX prints 0 at -O0 and 1 at -O2 (Lesson 12.7) and neither compiler is wrong. ∎

Theorem 12.5.11 (Detection probability)

Suppose each generated program independently triggers a given bug and exposes it by a disagreement with probability $q > 0$. The probability that $N$ programs miss it is $(1 - q)^N \le e^{-qN}$; the expected number of programs until the first detection is $1/q$; and $N \ge \ln(1/\delta)/q$ programs detect it with probability at least $1 - \delta$.

Proof

Independence gives $\Pr[\text{all } N \text{ miss}] = (1-q)^N$, and $1 - q \le e^{-q}$ for all real $q$ gives the bound. The index of the first success of independent Bernoulli($q$) trials is geometric with mean $1/q$. Finally $e^{-qN} \le \delta$ iff $N \ge \ln(1/\delta)/q$. ∎

Proposition 12.5.12 (Agreement is not correctness)

A differential oracle misses every bug that all compared configurations share, and every bug whose effect is not observable in the compared outputs.

Proof

If $C_1$ and $C_2$ produce the same wrong result, the oracle's equality test passes (Definition 12.5.4). If the bug changes only unobserved state — for instance it adds an nsw flag that turns a wrapped value into poison, and the execution engine happens to compute the wrapped value anyway — the observed outputs are equal. The matrix of §3 shows the second case (bug 5). ∎

Theorem 12.5.13 (Csmith and YARPGen programs are well defined, sketch)

Under the invariants of Algorithms 12.5.6 and 12.5.7, every generated program is well defined on its fixed input.

Proof sketch (full arguments: [YCER11, §2], [LBR20, §3])

Csmith: every signed arithmetic operation goes through a wrapper that returns a defined value when the operation would overflow or divide by zero; dereferences are emitted only when the conservative points-to analysis proves the target valid; the effect analysis rejects expressions with unsequenced conflicting accesses; what remains of C's undefined behaviors is excluded by construction or by construction limits (no uninitialized reads: all variables are initialized). YARPGen: the generator evaluates every expression on the known inputs and rewrites any node whose evaluation would be undefined, so the final program performs exactly the evaluations the generator checked. Both papers give the full list of behaviors handled; neither guarantees termination within a time limit, which is why test harnesses use timeouts (§7). ∎

Proposition 12.5.14 (llvm-stress output verifies)

Every module produced by Algorithm 12.5.8 passes the IR verifier; its value is as a crash test: $O(C, P) \iff C$ terminates normally on $P$ and its output verifies.

Proof

Each modifier creates an instruction whose operands come from the pool with the types the instruction requires (casts and vector operations check element counts), so every instruction is type-correct. Control flow is introduced only by splitting the straight-line body into a chain whose blocks may branch back to themselves, so every definition still dominates its uses: a value defined in block $j$ of the chain is used in block $j$ or later, and every path to a later block passes through block $j$. Finally, main runs verifyModule and aborts instead of printing a broken module. Its programs read through pointer arguments, so they cannot be executed meaningfully, and the only oracle is the absence of crashes and verifier errors. ∎

Differential testing with undefined behavior

If your generator emits add nsw and an input makes it overflow, "before" and "after" may differ without any bug (Theorem 12.5.10). The lab's difftest.py must never generate nsw/nuw, division by possibly zero, or out-of-range shifts; SPEC.md R3 says so, and mutation_matrix.py counts a false alarm on bug 0 as a failure.

5. Complexity¶

Let $k$ be the number of configurations, $N$ the number of programs, $t$ the cost to compile and run one program with one configuration, $q$ the per-program probability of exposing a given bug, and $\lvert x \rvert$ the size of a snapshot.

Technique	Time (worst)	Time (typical)	Space	Notes
Snapshot testing	one run + $O(\lvert x \rvert)$ comparison per input	milliseconds per input	one golden file per input	review cost grows with every accepted change
Differential testing	$k \cdot N \cdot t$	$1/q$ programs to a detection (Theorem 12.5.11)	one program at a time	bugs with tiny $q$ may never be found
Csmith	generation $O(\text{program size} \times \text{effect analysis})$	a few seconds per program + compile/run	—	1 600 lines for seed 1 (§7); some programs run long: timeouts
YARPGen	$O(\text{program size})$ + evaluation during generation	under a second per test	—	~7 900 lines for seed 1 (§7)
llvm-stress	$O(s)$	milliseconds	—	crash testing only

Justification. Differential testing runs every program through every configuration; Theorem 12.5.11 gives the expected number of programs. Pathological family: a bug that fires only when a 32-bit input equals one specific value and the generator draws inputs uniformly has $q \le 2^{-32}$ per input, so about $2^{32}$ executions are expected before a detection (§3); biasing generators toward boundary values and patterns (YARPGen's policies) is the remedy. At scale, the Csmith authors report finding and reporting more than 325 previously unknown bugs in C compilers over three years of running such loops [YCER11].

Snapshot testing¶

Inline snapshots (insta's assert_snapshot! with the value in the source, Jest's toMatchInlineSnapshot): the expected output lives in the test [Insta]. Trade-off: long outputs clutter the code.
Redaction/normalization ($\nu$): insta's redactions, the lab's removal of ModuleID. Trade-off: over-normalizing hides bugs.
Generated FileCheck lines (Lesson 12.4): a snapshot that tolerates consistent renaming.

Differential testing¶

Cross-compiler vs cross-level vs cross-version comparisons (GCC vs Clang, -O0 vs -O2, LLVM 22 vs 23): different bugs, different false alarms (implementation-defined behavior differs across compilers) [McK98].
Metamorphic testing (Lesson 12.6): compare a program with a transformed but equivalent program on one compiler, which removes the need for a second implementation.
Before/after one pass (the lab): localizes the bug to the pass. Trade-off: only that pass is tested.

Csmith¶

Swarm testing (Groce et al., ISSTA 2012, surveyed in [CPS+20]): each program uses a random subset of features, which improves diversity. Trade-off: more programs.
Test-case reduction with C-Reduce (Lesson 12.7) is part of the workflow, since Csmith programs are thousands of lines.

YARPGen¶

Generation policies per code region (arithmetic-heavy, array-heavy, loop-heavy) [LBR20]. Trade-off: hand-designed policies.
Other targets: YARPGen 2's --std=ispc and --std=sycl emit tests for data-parallel compilers from the same generator. Trade-off: each target needs its own UB rules.

llvm-stress¶

Crash testing of llc for every target (llvm-stress | llc -march=...). Trade-off: no miscompilation detection.
Coverage-guided IR fuzzers (llvm-opt-fuzzer, llvm-isel-fuzzer, Lesson 12.6) mutate IR instead of generating it from scratch.

7. In real compilers¶

Snapshot testing¶

Turnt (cucapra/turnt, used for Cornell's Bril compiler infrastructure) and insta (mitsuhiko/insta) [Turnt, Insta]; in LLVM, the generated tests of update_test_checks.py play this role; the course's labs/ch12-testing/provided/snap.py.

A snapshot test with Turnt

Reproduce (Turnt 1.12.0 via uvx turnt, opt 23.1.2):

cat > turnt.toml <<'EOF'
command = "opt -passes=instcombine -S {filename} | grep -v -e ModuleID -e source_filename"
output.out = "-"
EOF
printf 'define i32 @f(i32 %%x) {\n  %%r = mul i32 %%x, 8\n  ret i32 %%r\n}\n' > mul.ll
uvx turnt --save mul.ll; cat mul.out
uvx turnt mul.ll
sed -i 's/, 8$/, 16/' mul.ll
uvx turnt --diff mul.ll 2>&1 | grep -v -e '^---' -e '^+++'

Output:

1..1
not ok 1 - mul.ll # skip: updated ./mul.out; missing: ./mul.out

define i32 @f(i32 %x) {
  %r = shl i32 %x, 3
  ret i32 %r
}
1..1
ok 1 - mul.ll
1..1
@@ -1,5 +1,5 @@

 define i32 @f(i32 %x) {
-  %r = shl i32 %x, 3
+  %r = shl i32 %x, 4
   ret i32 %r
 }
not ok 1 - mul.ll # differing: ./mul.out

What to notice: Algorithm 12.5.3: --save is the accept step and writes the golden file mul.out; the plain run passes; after the input changes, the comparison fails and prints a diff for review (Proposition 12.5.9 — here the change is in the input, but a change in opt would look the same).

Differential testing¶

McKeeman's DDT at Digital [McK98]; Csmith and YARPGen campaigns against GCC and LLVM [YCER11, LBR20]; in this course, the lab's difftest.py and the Chapter 24 fuzzer.

Differential testing clang -O0 against -O2 with Csmith

Reproduce (csmith 2.3.0 — Ubuntu 24.04: sudo apt install csmith libcsmith-dev (headers in /usr/include/csmith); macOS: brew install csmith and use -I$(brew --prefix csmith)/include/csmith-2.3.0 instead; clang 23.1.2):

for seed in $(seq 1 20); do
  csmith --seed $seed > p$seed.c
  for o in O0 O2; do
    clang-23 -$o -w -I/usr/include/csmith p$seed.c -o p$seed.$o 2>/dev/null
    timeout 10 ./p$seed.$o > out$seed.$o 2>&1 || echo "timeout/crash" >> out$seed.$o
  done
  if cmp -s out$seed.O0 out$seed.O2; then echo "seed $seed: $(cat out$seed.O0)"; else echo "seed $seed: MISMATCH"; fi
done

Output:

seed 1: checksum = F7B2B1F4
seed 2: checksum = B384B5F0
seed 3: checksum = B00C0056
seed 4: checksum = C80E68FC
seed 5: checksum = 6D682E79
seed 6: checksum = BAAD0D5B
seed 7: checksum = D9927B6C
seed 8: checksum = BA52A9F4
seed 9: checksum = 1A8057EA
seed 10: checksum = 768AC13A
seed 11: checksum = 84560AC5
seed 12: checksum = 9DCA6B5D
seed 13: checksum = AFCBD8FF
seed 14: checksum = AA18D9CC
seed 15: checksum = 37DBFFB7
seed 16: checksum = 615EE89B
seed 17: checksum = C55E8AF7
seed 18: checksum = F9B92124
seed 19: checksum = 82BA5750
seed 20: timeout/crash

What to notice: Algorithm 12.5.5 with $k = 2$ configurations: 20 programs, no disagreement — a mature compiler on 20 programs, as Theorem 12.5.11 predicts for a small $q$. Seed 20 runs longer than 10 s at both levels: Csmith does not guarantee termination (Theorem 12.5.13's sketch), so a harness needs a timeout and must treat "both timed out" as agreement, not as a bug.

Csmith¶

csmith-project/csmith — src/Statement.cpp (Statement::make_random), src/FactPointTo.cpp (the points-to facts), runtime/safe_math.m4 (the wrappers) [Csmith].

What a Csmith program looks like

Reproduce (csmith 2.3.0, installed as in the previous box):

csmith --seed 1 > p1.c
wc -l < p1.c
grep -o 'safe_[a-z_0-9]*' p1.c | sort | uniq -c | sort -rn | head -5
grep -n 'transparent_crc(g_2,\|platform_main_end' p1.c

Output:

1607
      7 safe_mul_func_int8_t_s_s
      7 safe_lshift_func_uint16_t_u_u
      6 safe_mul_func_uint8_t_u_u
      6 safe_mod_func_uint8_t_u_u
      6 safe_add_func_uint8_t_u_u
1324:    transparent_crc(g_2, "g_2", print_hash_value);
1499:    platform_main_end(crc32_context ^ 0xFFFFFFFFUL, print_hash_value);

What to notice: 1 607 lines for one seed, with arithmetic routed through the safe-math wrappers (Algorithm 12.5.6), even shifts and remainders; main feeds every global into a CRC (transparent_crc) and prints it with platform_main_end — the checksum that the differential harness compares.

YARPGen¶

intel/yarpgen — src/gen_policy.cpp (generation policies), src/expr.cpp (evaluate and the UB rewriting) [YARPGen] (built from commit e2a0512, 2026-08-19).

YARPGen tests against clang -O0, clang -O3 and gcc -O3

Reproduce (YARPGen 2.0 built from github.com/intel/yarpgen at commit e2a0512 with -Werror removed from src/CMakeLists.txt — exact commands in the chapter's tools outside the course toolchain; clang 23.1.2; gcc 14.2.0 — Ubuntu 24.04: sudo apt install gcc-14, macOS: brew install gcc@14):

for seed in 2 3 4 5; do
  mkdir -p s$seed && yarpgen --seed=$seed --std=c -o s$seed > /dev/null
  for cc in "clang-23 -O0" "clang-23 -O3" "gcc-14 -O3"; do
    $cc -w -mcmodel=large s$seed/driver.c s$seed/func.c -o s$seed/a.out && ./s$seed/a.out
  done | sort -u | tr '\n' ' '
  echo "<- seed $seed"
done

Output:

9940250760932188577 <- seed 2
16218585352091125952 <- seed 3
7180835882915813346 <- seed 4
3521749386858152757 <- seed 5

What to notice: three configurations, one distinct hash per seed (sort -u would print several if they disagreed): Algorithm 12.5.5 with $k = 3$ and two different compilers. YARPGen's large global arrays need -mcmodel=large; the generated code annotates constants with their tracked values (/*2*/) — the value tracking of Algorithm 12.5.7 made visible.

llvm-stress¶

llvm/tools/llvm-stress/llvm-stress.cpp — the Modifier subclasses (LoadModifier, BinModifier, CmpModifier, ...) and IntroduceControlFlow [LLVM-StressSrc] (LLVM 23.1.2).

Crash-testing opt and llc with llvm-stress

Reproduce (llvm-stress, opt, llc 23.1.2):

llvm-stress -seed=7 -size=12 -o - | sed -n '4,12p'
n=0
for s in $(seq 1 200); do
  llvm-stress -seed=$s -size=100 -o st.ll && opt -O2 st.ll -o st.bc 2>/dev/null \
    && llc -O2 st.bc -o /dev/null 2>/dev/null || { echo "seed $s failed"; n=$((n+1)); }
done
echo "failures: $n"

Output:

define void @autogen_SD7(ptr %0, ptr %1, ptr %2, i32 %3, i64 %4, i8 %5) {
BB:
  %A4 = alloca i32, align 4
  %A3 = alloca double, align 8
  %A2 = alloca double, align 8
  %A1 = alloca i64, align 8
  %A = alloca i64, align 8
  %L = load i8, ptr %A, align 1
  store <4 x i8> zeroinitializer, ptr %0, align 4
failures: 0

What to notice: the function reads and writes through its pointer arguments, so it cannot be run; the oracle is Proposition 12.5.14's "no crash, output verifies". 200 seeds of -O2 + code generation pass — the value is in running millions of seeds, and in running it on every new pass.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Snapshot testing	Detects every output change (Prop. 12.5.9); false alarm on every benign change	One run + diff per input	A diff to review; accepting is one command	Very low per test	Printers, diagnostics, small IR outputs; `update_test_checks`
Differential testing	Sound only for well-defined programs (Thm. 12.5.10); misses shared and unobservable bugs (Prop. 12.5.12)	$k$ compilations + runs per program; $1/q$ programs to a bug	A disagreeing program (large: reduce it)	Low (a harness) given a generator	Csmith/YARPGen campaigns, `-O0` vs `-O2`, before/after a pass
Csmith	UB-free C with pointers, structs, unions, volatile; checksum oracle	Seconds per program	Thousands of lines per failing program	High (a large C++ generator with its own pointer and effect analyses)	Finding miscompilations in C compilers
YARPGen	UB-free C/C++ with loops and arrays, policies for optimizations	Sub-second generation	Two files per test; hashes of results	High	Loop and vectorizer bugs in GCC/LLVM/ICC
llvm-stress	Random verifier-clean IR; crash oracle only	Milliseconds	Small IR functions	Low (one LLVM tool)	Crash testing passes and back ends

Choose snapshots when the whole output is the specification and humans review changes. Choose differential testing when there is a second implementation (another compiler, another level, the code before your pass) and a source of well-defined programs. Choose Csmith when testing a C compiler's middle and back end broadly; YARPGen when loops and vectorization are the target; llvm-stress when you want to know whether a new pass or target crashes on odd IR.

9. Assessment¶

Quiz: diff-ub, diff-prob (number), diff-matrix (mapping), snap-false-alarm, csmith-safe, yarpgen-values, stress-oracle, diff-agree.
Drill: none — generating programs by hand teaches little; the lab is the practice: you write the generator and the harness (Part A), and mutation_matrix.py grades them. The detection-probability reasoning is drilled by quiz diff-prob.
Flashcards: tags snapshot, differential, csmith, yarpgen, llvm-stress.
Lab: labs/ch12-testing, Part A (R1–R4).
Find where LLVM does it: in llvm/tools/llvm-stress/llvm-stress.cpp, which function adds branches to the generated straight-line code?

References¶

See the chapter references.

Technique	Time (worst)	Time (typical)	Space	Notes
Snapshot testing	one run + \(O(\lvert x \rvert)\) comparison per input	milliseconds per input	one golden file per input	review cost grows with every accepted change
Differential testing	\(k \cdot N \cdot t\)	\(1/q\) programs to a detection (Theorem 12.5.11)	one program at a time	bugs with tiny \(q\) may never be found
Csmith	generation \(O(\text{program size} \times \text{effect analysis})\)	a few seconds per program + compile/run	—	1 600 lines for seed 1 (§7); some programs run long: timeouts
YARPGen	\(O(\text{program size})\) + evaluation during generation	under a second per test	—	~7 900 lines for seed 1 (§7)
llvm-stress	\(O(s)\)	milliseconds	—	crash testing only

Lesson 12.5 — Snapshot and differential testing, and random program generators¶

1. Problem and motivation¶

Snapshot testing¶

Differential testing¶

Csmith¶

YARPGen¶

llvm-stress¶

2. Definitions and algorithms¶

Snapshot testing¶

Differential testing¶

Csmith¶

YARPGen¶

llvm-stress¶

3. Worked example¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

Snapshot testing¶

Differential testing¶

Csmith¶

YARPGen¶

llvm-stress¶

7. In real compilers¶

Snapshot testing¶

Differential testing¶

Csmith¶

YARPGen¶

llvm-stress¶

8. Comparison¶

9. Assessment¶

References¶