Correctnesstypical

Testing a Compiler

Seven layers, from a unit test on one pass to a fuzzer generating programs nobody wrote. The highest-value test in any compiler is the property that optimization never changes what a program prints — and it is the one most compilers add last.

The question

What does a serious test suite for a compiler actually contain, and which test earns the most?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A compiler under test is a function from source text to an artifact plus a diagnostic set. Testing it means pinning behavior at three different granularities: on the internal representations between passes (IR in, IR out), on the artifact (does this assembly match what we recorded), and on the *behavior of the artifact when run*. The third is the only one that tests what users care about, and it is the most expensive, which is why the other two exist.

What this phase may assume or do

A compiler test suite may assume the input program is well-defined — every generated or hand-written test program must be free of undefined behavior, or the expected result is not well-defined either and the test is asserting a coincidence. It may assume determinism from the compiler: the same input under the same flags must produce byte-identical output, or golden comparison is meaningless. Everything else it must establish rather than assume, and the property it exists to establish is that observable behavior is preserved by every transformation.

Key points

The layers are pass unit tests, frontend tests, diagnostic tests, golden tests, execution tests, property tests and fuzzing; each catches a class the cheaper layers structurally cannot.
The highest-value test in a compiler is: optimization never changes what the program prints, checked with the full pipeline and with each pass alone.
Compare termination status as well as output — turning a trap into a non-trap is a behavior change.
Test the legality guards, not the happy paths. The negative cases are where the bugs live.
Verify sequence-producing components by simulating the sequence, not by comparing against a hand-written expectation.
Assert invariants rather than outputs wherever an invariant exists: SSA single definition, phi arity, no overlapping register assignment.

The seven layers

A compiler is a pipeline, so its test suite is layered along the pipeline. Each layer catches a class the layer above it cannot, and each is cheaper per bug found than the layer below. Skipping a layer is a legitimate choice; not knowing which one you skipped is not.

The important thing about the table is the last column. A layer is only worth its cost if it catches something the cheaper layers structurally cannot. Unit tests on a pass cannot catch a phase-ordering bug, because a phase-ordering bug is by definition about two passes. Golden tests cannot catch a wrong-code bug, because a golden test asserts that the output is *what it was*, not that it is *right*. Only execution can catch that.

Test layers, cheapest firsttypical

Layer	What it asserts	Catches what nothing cheaper can
Pass unit test	This IR in, that IR out, for one transformation in isolation	Legality edge cases inside one pass — the trap, the volatile, the escaping address
Parser / lexer test	This text produces this token stream or this tree, and this bad text produces this error	Precedence, associativity and recovery — silent wrong-tree bugs that never error
Diagnostic test	This invalid program reports this message at this span	Regressions in error quality, which nothing else notices because nothing else fails
Golden / snapshot	The emitted IR or assembly is byte-identical to a recorded file	Unintended changes anywhere in the pipeline, including in code nobody meant to touch
End-to-end execution	Compiling and running this program prints this	Wrong-code bugs. Nothing above this layer can see them.
Property / metamorphic	For all programs P and all pass subsets S, output(P, S) equals output(P, none)	Bugs in pass combinations and in passes that are only wrong together
Differential + fuzzing	Two implementations agree on generated programs nobody wrote	The bugs your test authors did not think of, which is most of them

The highest-value test, stated as a property

simplifiedOur corpus is a dozen hand-written examples; a production compiler runs this property over thousands of files plus everything a generator produces. The shape is identical and the assertion is identical. What changes with scale is the need for the corpus itself to be free of undefined behavior — with hand-written examples you can simply read them, which is why generated corpora need [[compiler-fuzzing]]-grade generators rather than random text.

Here is the test that earns more than the rest combined, and it fits in a paragraph. Take a corpus of programs. For each one, run it with the optimizer disabled and record the output. Then run it again with the optimizer fully enabled, and with each individual pass enabled alone, and assert that the output never changes. That is the definition of an optimization, turned into an executable assertion.

It is worth being precise about why the per-pass loop matters. A pass that is wrong only in isolation still ships a compiler that miscompiles the moment somebody uses a different pass pipeline, and a pass that is wrong only in combination is invisible to a suite that tests each pass alone. Running the full pipeline and every singleton subset costs a constant factor and covers both ends. The middle — arbitrary subsets — is where fuzzing takes over.

Our own compiler does exactly this, and the test is short enough to read. It is the single most important test in scripts/compilers-sim.test.ts, and everything else in that file exists to localize a failure once this one goes red.

From `scripts/compilers-sim.test.ts` — the property that makes an optimization an optimization

1for (const src of programs) {
2  const baseline = compile(src, { passes: new Set<PassId>() })
3  const full = compile(src)
4  assert.deepEqual(full.execution.output, baseline.execution.output)
5  assert.equal(full.execution.status, baseline.execution.status)
6 
7  // And every single-pass subset, so a pass that is only wrong in
8  // isolation is still caught.
9  for (const pass of PASSES) {
10    const one = compile(src, { passes: new Set<PassId>([pass.id]) })
11    assert.deepEqual(one.execution.output, baseline.execution.output)
12  }
13}

Note that the termination *status* is compared as well as the output. An optimizer that turns a trapping program into a non-trapping one, or an infinite loop into a return, has changed observable behavior just as surely as one that prints the wrong number — and comparing only stdout would miss both.

Testing the guards, not just the outcomes

Every transformation has a legality precondition, and the precondition is where the bugs are. So the tests worth writing are not "constant folding folds 1 + 2" — that works on the first attempt and never breaks. They are the negative cases: the effectful instruction that must not be deleted, the division by literal zero that must not be folded, the call whose purity cannot be proved, the volatile access that must survive.

This is the same discipline as the transform device throughout this domain: a transformation shown without the case where it is wrong teaches that the rewrite is unconditional. A test suite written the same way asserts that the rewrite is unconditional, which is worse, because now the compiler will keep doing it.

The corresponding structural check is cheap and surprisingly effective: assert that every declared pass carries both a legality condition and a stated case where it would be illegal, and that every pass actually fires on at least one example in the corpus. A pass that never fires is a toggle that demonstrates nothing, and a pass with no stated illegal case has never been thought about.

For each pass, one test that it fires and one test that it declines to fire when the precondition fails.
Assert that effectful instructions survive dead-code elimination however dead their values look.
Assert that a potentially trapping operation is not folded — moving a fault to compile time is a behavior change.
Assert determinism: compile twice, compare every intermediate stage byte for byte. Golden tests depend on it.
Assert the internal invariants directly — one definition per SSA value, phi arity matching predecessor count, no two simultaneously-live values in one register.

Verify by simulation, not by expectation

One technique deserves naming because it is easy to get subtly wrong. When you test a component whose correct answer is a *sequence* — a parallel-copy sequencer, a scheduler, a spill placement — do not compare the sequence against a hand-written expected list. A wrong sequence that happens to match a wrong expectation passes forever, and hand-written expectations for this kind of thing are wrong surprisingly often.

Instead, execute the sequence and check the resulting state. For a parallel copy, run the moves against an initial register state and assert the final state is the permutation the copy was supposed to perform. The classic bug — sequencing a two-cycle swap as two sequential moves, so both registers end up holding the same value — is caught by simulation and invisible to comparison against an expectation the same person wrote.

The general form: prefer asserting the *property the component exists to maintain* over asserting the shape of its output. "No two simultaneously live values share a register" is an invariant; "the allocator assigns %3 to rcx" is a coincidence that will break on the next heuristic change and tell you nothing when it does.

How it works

The steps, in the order the compiler takes them.

Maintain a corpus of programs known to be free of undefined behavior, with a recorded expected output for each.
Run the corpus with optimization disabled to establish the baseline behavior, which is the reference every other configuration is compared against.
Re-run with the full pass pipeline and with each pass individually enabled, comparing output and termination status against the baseline.
Run pass-level unit tests that feed IR directly to one transformation and compare the resulting IR, including the cases where the transformation must decline.
Run an IR verifier after every pass so that a structurally broken representation is caught at the pass that broke it rather than three passes later.
Run golden comparison over emitted IR, assembly and diagnostics to catch unintended change anywhere else in the pipeline.
Feed generated programs from a generator that guarantees definedness, and compare against another compiler or another optimization level.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

The suite is entirely golden tests, so it fails loudly on every intentional change and silently accepts a wrong-code bug, because nothing in it ever runs a program.
The corpus contains a program with undefined behavior, so the expected output is a coincidence of the current compiler, and the test fails on an unrelated upgrade with an alarming and meaningless diff.
Only the full pipeline is tested. A pass that is wrong in isolation ships, and the first user with a custom pipeline hits it.
A pass is added with a toggle but never fires on any test program, so the pass is entirely untested while appearing in coverage reports as exercised code.
Tests compare a register allocator’s exact assignment, so every heuristic improvement breaks fifty tests and the team learns to bless the diffs without reading them.
Only stdout is compared, so an optimizer that removes an infinite loop or suppresses a trap passes every test while changing what the program does.

When it helps

Any project with a code generator in it, which is more projects than people think: template engines, query compilers, serializers, schema-to-code tools and ORM query builders are all compilers with the same failure modes.
Refactoring a compiler. The property test is what makes it possible to restructure the pass pipeline at all without a week of manual verification.
Onboarding: a suite organised by the claim each test defends teaches the invariants of the system faster than any document.

When it hurts

Very early in a prototype, where the pipeline changes shape weekly and golden files cost more to re-bless than they catch.
When the corpus cannot be executed — a cross-compiler for a target you do not have hardware or an emulator for. Then the execution layer is unavailable and everything above it has to work harder.
When test runtime becomes the bottleneck on every commit. The full property test over a large corpus with per-pass subsets is quadratic-ish in practice and usually belongs in a nightly job rather than in the pre-merge gate.

What it costs

Every one of these is paid by something.

The per-pass property loop buys detection of passes that are wrong in isolation and costs a full compile-and-run per pass per program, which is the single largest line item in a mature compiler’s test time.
Golden tests buy sensitivity to unintended change and cost a maintenance stream of diffs to re-bless, plus the standing risk that a wrong output gets blessed because the diff was large and the reviewer was tired.
Executing generated programs buys real wrong-code detection and costs a generator that can guarantee definedness — a serious engineering project in a language with as much undefined behavior as C.
IR verification after every pass buys precise localization of structural breakage and costs measurable compile time, which is why most compilers run it only in debug builds and thereby lose it exactly where users are.
Asserting invariants instead of outputs buys resilience to heuristic changes and costs the ability to notice a heuristic regression at all, so a performance-tracking layer has to be added back separately.

What else you could do

What a different compiler or language does instead, and when that is better.

Rely on a large downstream corpus instead — build the operating system, or a thousand packages, and see what breaks. This is what distribution rebuild programmes do; it finds real bugs and localizes none of them.
Lean on [[translation-validation]] rather than on tests: check each compilation for semantic preservation, which covers programs no test author wrote at the cost of a checker that must model the IR semantics.
Lean on proof: [[verified-compilers]] replace the middle-end test suite with a machine-checked theorem, which is stronger everywhere it applies and does not apply to the frontend, the runtime or the specification.
Snapshot-only suites, as some fast-moving frontends use, accepting that correctness is established by downstream users. Cheap, honest if stated, and a poor fit for anything safety-relevant.

See it for yourself

The flag, dump or tool that shows you this directly.

Read a real one: LLVM’s llvm/test uses lit and FileCheck, where each test is IR plus ; CHECK: lines asserting the shape of the output. llvm-lit -v llvm/test/Transforms/InstCombine runs one directory.
GCC’s test suite is DejaGnu-based: make check-gcc RUNTESTFLAGS="dg.exp=pr12345.c" runs a single case, and the dg-final { scan-tree-dump ... } directives are its golden-test mechanism.
Rust: ./x.py test src/test/ui runs the diagnostic tests, whose expected stderr lives in .stderr files next to each case — golden tests for error messages specifically.
Run our own: npx tsx --test scripts/compilers-sim.test.ts, and read it top to bottom. It is grouped by the claim each block defends rather than by the function each block calls.
Coverage on a compiler is worth measuring but reads oddly: llvm-cov will show high line coverage in a pass whose legality guard has never been exercised, because the guard is one branch on a hot path.

Plausible wrong readings

Stated the way a confident engineer states them.

"We have 90% coverage, so the compiler is tested." Coverage measures which lines ran, not which preconditions were violated. A legality guard is one line and needs two tests.
"Golden tests are regression tests, so they establish correctness." They establish that behavior has not changed. If the recorded behavior was wrong, they lock the bug in and defend it.
"Testing each pass in isolation is enough." Phase-ordering bugs are bugs in the interaction. By construction no isolated test can see them.
"If the compiler builds a large project successfully, it works." Successfully building is a claim about crashes and rejections. Wrong-code bugs build perfectly.

Misconceptions

The claim, and what is actually true.

A compiler test suite is just a big pile of example programs.

The pile is one layer. Without pass-level tests you cannot localize; without property tests you cannot cover pass combinations; without generated programs you only test what somebody thought to write.

Unit tests on passes are the foundation.

They are the cheapest layer, not the most valuable one. The property that behavior is preserved end to end finds more, because it does not depend on anyone having anticipated the interaction.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Testing a compiler means testing at several levels at once: does this pass do the right thing to this IR, does this bad program produce the right error message, does the emitted assembly still look like it did yesterday, and — most importantly — does the program still print the same thing after optimization as before it. That last one is the definition of an optimization written as a test, and it is the one worth writing first.

practical

Start with a corpus of small programs whose output you know and which contain no undefined behavior. Assert that output is unchanged with the optimizer off, with it fully on, and with each pass alone. Then add negative tests for every legality guard: the print that must not be deleted, the division by zero that must not be folded. Then add golden files for IR and assembly, accepting that you now own a stream of diffs. Add generated programs last, because a generator that emits undefined behavior is worse than no generator.

advanced

The interesting design question is how to keep tests from encoding heuristics. Anything that asserts a specific register, a specific block order or a specific inlining decision will break on every improvement and be blessed without reading, at which point the suite has become noise that occasionally hides a real regression. The durable form is invariant plus behavior: assert the property the component maintains, assert the program still computes the right answer, and track heuristic quality separately as a performance metric with its own noise budget — which is where [[compiler-performance]] and code-size tracking belong rather than in the correctness suite.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThe layer list describes production compilers such as LLVM, GCC and rustc. A research or teaching compiler often stops at execution tests, and a fast-moving frontend such as a bundler frequently ships with snapshot tests only. Neither is wrong in itself; what is wrong is not knowing which layer you skipped and therefore which bug class you have no defence against.

implementationThe property loop as described re-runs the whole pipeline per pass, which is affordable for our small compiler and for most test programs. LLVM instead relies on opt -passes=... to run one pass at a time over IR fixtures plus a very large end-to-end corpus, because re-running clang per pass per file would dominate CI. Same property, different cost model.

simplifiedWe describe the corpus as "programs known to be free of undefined behavior". Establishing that for a real language is itself hard, which is why generators such as Csmith exist and why hand-written corpora are periodically re-checked under sanitizers. Assuming definedness without checking it is how a suite acquires tests that assert a coincidence.

If you were asked this in an interview

You are handed a compiler with no tests. What is the first test you write, and why that one?
Why is comparing termination status as important as comparing stdout?
How would you test a register allocator without asserting which register anything got?

Connections

Securityfuzzing regression-testing

Domains that do not exist yet

Testing & Reliability Engineering — Property-based and metamorphic testing as general disciplines
The property "optimization preserves output" is a metamorphic relation, and the machinery for generating inputs and shrinking failures belongs to that domain. What is compiler-specific is which relation to pick and why this particular one dominates the rest.