Skip to content
Tutorials Center
My learning

Topics

Lesson 59 of 61 ยท Practice and Review

Testing and Debugging a Compiler

Learn how to test and debug a compiler: golden tests, error message tests, random program fuzzing, differential testing against Python and test case shrinking.

A compiler is one of the hardest programs to test, and one of the most important to get right. Its input is any program a person can write, so the set of inputs is infinite. Its bugs are often silent: a wrong optimization does not crash, it produces a program that quietly computes the wrong answer. Users blame their own code first, and may take days to realize that the compiler was at fault.

This lesson collects the techniques that working compiler teams use, and shows each of them on a small but complete compiler: a lexer, a precedence-climbing parser, a bytecode generator and a stack VM for integer expressions. You will write golden tests, error message tests, a random program generator, a differential test against Python itself, and a shrinker that boils a huge failing program down to a five-node tree. Along the way you will plant a classic bug in the VM and watch the tools find it.

flowchart LR
    subgraph Stages
      A["Lexer"] --> B["Parser"] --> C["Code generator"] --> D["VM"]
    end
    T1["Token tests"] -.-> A
    T2["Golden AST tests<br/>error message tests"] -.-> B
    T3["Golden bytecode tests"] -.-> C
    T4["End-to-end tests<br/>fuzzing, differential tests"] -.-> D

Test each stage on its own, then test the whole pipeline with many programs.

Test each stage separately

A bug in an early stage looks like a different bug in a later one. If the parser builds (1 + 2) * 3 for 1 + 2 * 3, you will see a wrong final answer and may blame the VM. So test each stage on its own input and output:

  • Lexer: source text in, a list of tokens out. Check positions too.
  • Parser: source text in, a tree out. Compare against an expected tree or a printed form of it.
  • Code generator: tree in, bytecode out. Compare against expected instructions.
  • VM: bytecode in, a value out. Hand-written bytecode is enough here.
  • End to end: source text in, program output out.

The tests are cheap to write if every stage has a plain-text form that is easy to print. That is a design rule worth following from the start: give your tree a to_source function, give your bytecode a disassembler, and give your tokens a readable repr. They help in tests, in error messages and in debugging.

Golden tests

A golden test stores the expected output as text and compares it with the actual output. It is the main workhorse of compiler testing, because compilers produce text-like results: token lists, trees, assembly, IR dumps and error messages. The LLVM project has thousands of them, written in a style of "run this pass on this IR and check the output lines".

Golden tests have three attractive properties. They are easy to write (paste the output once you have checked it by eye). They document the compiler's behavior. And when a change breaks one, the diff shows exactly what changed. Always print a diff on failure, not just the word FAIL.

The program below defines the compiler and then runs three groups of tests: values, bytecode, and error messages. For errors, the whole message is compared, including the line of source and the caret, because error quality is a feature users see every day.

Python Golden tests and error message tests

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two practical notes. First, when you deliberately change the compiler's output (a better error message, a smarter optimization), you update the golden files in one go and review the diff in version control, instead of editing dozens of expectations by hand. Many projects have an "update goldens" command for this. Second, goldens must be deterministic: iterate over dictionaries and sets in a fixed order, and never print memory addresses or timestamps.

Random programs: fuzzing and properties

Hand-written tests only find the bugs you imagined. A fuzzer generates programs at random and looks for trouble, which finds the bugs you did not imagine. Three kinds of check make a fuzzer useful:

  1. Crash checks. For any input, the compiler must either succeed or report an ordinary error. A Python traceback from inside the compiler is always a bug. This works even with garbage input and needs no reference answer.
  2. Property checks. Some laws hold for every input. One is the round trip: printing a tree as source text and parsing it again must give back the same tree. Another is that an optimizer must never change a program's output.
  3. Differential checks. Run the same program through two implementations and compare. The next section does this.

Generating valid programs is easy when you already have a grammar: pick a production at random and recurse, with a depth limit. Grammar-based generators reach deep into the compiler, because the parser accepts everything they produce. Generating almost valid programs (take a good one and delete or change a character) reaches the error paths, as in the JSON project.

Always use a seeded random generator. A failure you cannot reproduce is only an anecdote.

Differential testing against an oracle

An oracle is a trusted way to get the right answer. For our integer expressions, Python is the oracle: it evaluates arithmetic correctly. Tiny's / is floor division, so we translate it to Python's //, and everything else has the same spelling. (This is the same trick used by the transpiler project.)

The harness generates random expression trees, prints each as source text with to_source, runs it through our compiler and VM, runs it through the oracle, and compares the outcomes. An outcome is either ("ok", value) or ("error", kind). Division by zero must be an error in both. Treating errors as comparable results matters: a compiler that crashes on 1 / 0 while Python reports a clean error is a bug.

The same technique is how serious compilers are tested. Tools such as Csmith generate random C programs that avoid undefined behavior, compile each with GCC and Clang at several optimization levels, and complain when the programs print different results. Dozens of real compiler bugs were found this way.

Plant a bug, find it, shrink it

To see the harness work, the VM takes a buggy flag. When set, the remainder instruction uses the C-style remainder, whose sign follows the left operand, instead of Python's, whose sign follows the right operand. This is a very realistic bug: the two conventions agree on positive numbers and differ on negative ones, so ordinary tests pass while real programs break.

The harness reports how many random programs disagree. The first failing program is a monster with 37 nodes, which is useless for debugging. That is where a shrinker comes in: it tries to replace the program with smaller variants (a child instead of its parent, or a smaller number) and keeps any smaller variant that still fails. It repeats until nothing smaller works. The same idea powers tools like Hypothesis for Python and C-Reduce for C.

Python Fuzzing, differential testing and shrinking

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All 500 random trees survive the round trip, and the correct VM agrees with Python on all of them, whether the answer is a number or a division-by-zero error. The buggy VM disagrees on 50 programs. The shrinker reduces the first failure from 37 nodes to (1 % (0 - 3)), which has 5 nodes. Python says the remainder is -2 (the result takes the sign of the divisor), the buggy VM says 1. Now the bug is obvious: the sign convention of %.

Notice what made this work. The harness needs no expected values written by hand, only a source of truth. The reduced test case is small enough to paste into a bug report, and it can go straight into the golden tests as a regression test. Every bug you fix should leave a test behind.

When you find a bug through fuzzing, first shrink the input, then fix the bug, then add the shrunken program to the permanent test suite. The fuzzer keeps exploring new territory while the suite guards the old.

Debugging techniques

When a test fails and the cause is not obvious, these habits save hours:

  • Dump every stage. Provide flags (or functions) that print the tokens, the tree, the IR and the bytecode. Bugs show up at the first stage whose output looks wrong.
  • Trace the VM. Print the instruction pointer, the instruction and the stack after every step. The trace of a stack machine reads like a worked example.
  • Bisect the pipeline. If an optimizer is suspected, disable passes one at a time (or binary-search the list) and see when the bug disappears. LLVM has a "bisect limit" option that applies only the first N optimization steps for exactly this purpose.
  • Check invariants. After each pass, run a verifier that checks facts the later stages rely on: every jump target exists, every variable is defined before use, the stack is empty at the end. A failed assertion right after the guilty pass beats a wrong answer at the end.
  • Shrink first, think second. Reduce the failing program before reading any compiler code.

The next program dumps all stages for one expression, traces the VM, and shows how two different failures look: a run-time error stops in the middle of the trace, and a compile-time error stops before any bytecode exists.

Python Dump every stage and trace the VM

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the trace, the stack grows to [7, 2, 1, 2] and then collapses step by step: ADD turns the top two values into 3, MUL turns 2 and 3 into 6, and SUB leaves 1. If a bug made the result wrong, the first step whose stack looks wrong points at the instruction (and therefore the part of the code generator) to inspect.

A checklist for your own compiler

  • One test per language feature, written before the feature.
  • Golden tests for each stage, with readable text output and diffs.
  • Error message tests that include positions.
  • A seeded random program generator and an oracle (a reference interpreter, or another language).
  • A shrinker, or at least a manual habit of reducing failing programs.
  • A regression test for every fixed bug.
  • A fast test command, so people actually run it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is it useful to test the parser separately from the VM?

    Bugs travel down the pipeline. A wrong tree gives wrong bytecode and a wrong result. Stage-level tests point straight at the stage that went wrong.
  2. 2. What is a golden test?

    Goldens store expected tokens, trees, assembly or error messages. A failure shows a diff between expected and actual.
  3. 3. In the differential test, why are errors compared as outcomes too?

    Behavior includes failing in the right way. Treating an error as a value to compare catches both missing and unexpected errors.
  4. 4. What does a shrinker do?

    A small failing program is much easier to understand and makes a better regression test.
  5. 5. Why use a seeded random generator in a fuzzer?

    The same seed produces the same sequence of programs, so any failure can be rerun, debugged and turned into a regression test.

Summary

  • Test each compiler stage on its own, then test the pipeline end to end.
  • Golden tests store expected text output (tokens, trees, bytecode, error messages) and report failures as diffs.
  • Error messages, including source line and caret, deserve exact-match tests.
  • Fuzzing uses a seeded generator and checks for crashes, properties like the parse-print round trip, and differential agreement with an oracle.
  • A shrinker reduces a failing program to a minimal one, which becomes a regression test.
  • For debugging, dump all stages, trace the VM, bisect optimization passes and verify invariants after every pass.

Next: Compiler Design Interview Questions