Chapter 27

Testing a Compiler

A compiler is tested at several levels, each catching a different kind of mistake. For a compiler that emits WebAssembly, the levels are unusually well supported by existing tools: a validator to check every module it writes, a disassembler to compare output with expectations, several independent engines to compare results, and generators of random modules for fuzzing. This chapter builds a testing strategy layer by layer, with working examples of each, and finishes with this book's own test harness as a case study.

#The layers27.1

Layer Catches Tools
validation malformed bytes, invalid code V8, Wasmtime, wasm-validate
golden output unintended changes in generated code wasm2wat, wasm-objdump, diff
execution wrong results Node, Wasmtime, your own expected outputs
differential engine-dependent behaviour, and wrong results nobody wrote a test for several engines, a reference interpreter
fuzzing everything the other layers missed random programs, wasm-opt --fuzz-exec, wasm-tools smith
browser integration with the real host Playwright

Each layer is cheap to add once the previous one exists, and together they catch nearly everything.

#Layer 1: validate everything27.2

The first rule is that every module your compiler writes, in every test, is validated. Validation is fast, and an invalid module is always a compiler bug. The error message also points much closer to the cause than a wrong answer would.

Validate with more than one validator. They should agree on everything standard, and when they disagree, you have found either a bug in an engine (rare, but it happens), or a feature that one of them has not enabled. Here is a module checked by three validators, and an invalid one:

(module
  (func (export "f") (param i32) (result i32)
    (i32.mul (local.get 0) (i32.const 3))))

(module
  (func (export "f") (param i32) (result i32)
    (i32.mul (local.get 0) (f32.const 3))))

import re, subprocess, wasmtime

def v8(path):
    js = ("try { new WebAssembly.Module(require('fs').readFileSync(process.argv[1])) }"
          "catch (e) { console.log(e.message); process.exit(1) }")
    p = subprocess.run(["node", "-e", js, path], capture_output=True, text=True)
    return p.returncode == 0, p.stdout.strip()

def wasmtime_(path):
    try:
        wasmtime.Module.validate(wasmtime.Engine(), open(path, "rb").read())
        return True, ""
    except wasmtime.WasmtimeError as e:
        return False, str(e).splitlines()[-1].strip()

def wabt(path):
    p = subprocess.run(["wasm-validate", path], capture_output=True, text=True)
    return p.returncode == 0, re.sub(r"\x1b\[[0-9;]*m", "", p.stderr.strip())   # drop colours

def validate(path):
    results = {name: f(path) for name, f in [("v8", v8), ("wasmtime", wasmtime_), ("wabt", wabt)]}
    verdicts = {ok for ok, _ in results.values()}
    if len(verdicts) > 1:
        print(f"{path}: VALIDATORS DISAGREE")
    for name, (ok, msg) in results.items():
        print(f"{path}: {name:8} {'valid' if ok else 'invalid: ' + msg}")

validate("good.wasm")
validate("bad.wasm")

good.wasm: v8       valid
good.wasm: wasmtime valid
good.wasm: wabt     valid
bad.wasm: v8       invalid: WebAssembly.Module(): Compiling function #0 failed: i32.mul[1] expected type i32, found f32.const of type f32 @+34
bad.wasm: wasmtime invalid: type mismatch: expected i32, found f32 (at offset 0x27)
bad.wasm: wabt     invalid: bad.wasm:0000028: error: type mismatch in i32.mul, expected [i32, i32] but got [i32, f32]

Each validator explains the problem differently, and between them the cause is clear. Each also reports a different byte offset for the same mistake (0x22, 0x27 and 0x28), so tests that check error messages should not expect offsets to agree across tools.

For a compiler, the best place to validate is inside the compiler itself, in debug builds, right after encoding. Binaryen has a built-in validator for this; with your own encoder, the operand-stack tracking described in Chapter 13 catches problems at the instruction that caused them.

#Layer 2: golden output27.3

A golden test compares the compiler's output with a saved copy of what it produced before. It catches changes nobody intended, such as an optimisation that stopped firing, or a change in calling convention that was meant to affect one function and affected all of them.

Compare the text format, not the bytes. A diff of the text is readable; a diff of bytes is not. Here is a golden test, with a stand-in for a compiler's output:

(module
  (func (export "double") (param i32) (result i32)
    (i32.shl (local.get 0) (i32.const 1))))



cat > double.golden.wat <<'EOF'
(module
  (type (;0;) (func (param i32) (result i32)))
  (func (;0;) (type 0) (param i32) (result i32)
    local.get 0
    i32.const 1
    i32.shl)
  (export "double" (func 0)))
EOF
wasm2wat out.wasm > double.actual.wat
diff -u double.golden.wat double.actual.wat && echo "golden test passed"

golden test passed

Two practical points. First, give the test runner a flag that overwrites the golden files with the current output, so that intended changes are a single command followed by reviewing the diff in version control. (This book's harness has one, --accept.) Second, keep golden tests few and focused: one per code generation pattern, not one per program, or every change will touch hundreds of files and reviewers will stop reading them.

#Layer 3: execution tests27.4

The core of a compiler's test suite is programs in the source language together with their expected behaviour: the output they print, the value they return, or the error they report. These test what the user cares about, independent of how the code is generated, so they survive refactoring of the backend.

A good format keeps the expectation next to the program, in the same file, in comments:

// expect: 55
// expect: done
fn main() {
    var total = 0
    for i in 1..=10 { total += i }
    print(total)
    print("done")
}

The runner compiles each file, runs it in Node with a small host like this book's, and compares the output with the expect lines. Programs that should fail to compile carry expect-error lines, and programs that should trap carry expect-trap lines. Hundreds of such tests run in seconds, since compiling and instantiating small modules is fast.

Run each test under every configuration you ship: with and without optimisation, with and without SIMD or other optional features. A bug that appears only in one configuration is common, and easy to diagnose once you know which.

#Layer 4: differential testing27.5

Execution tests check what someone thought to check. Differential testing runs the same program in two different ways and checks that the results agree, so it finds bugs nobody wrote a test for.

The first kind compares engines. The same module, run in V8, in Wasmtime and in wabt's interpreter, should give the same results, except where WebAssembly allows differences (NaN bit patterns, relaxed SIMD, stack depth). A disagreement means your module depends on something it should not, or, occasionally, that an engine has a bug:

(module
  (func (export "f") (param i32) (result i32)
    (i32.add
      (i32.mul (local.get 0) (local.get 0))
      (i32.rotl (local.get 0) (i32.const 7)))))

import subprocess, wasmtime

def in_wasmtime(x):
    store = wasmtime.Store()
    module = wasmtime.Module.from_file(store.engine, "m.wasm")
    return wasmtime.Instance(store, module, []).exports(store)["f"](store, x)

def in_v8(x):
    out = subprocess.run(["node", "-e",
        "const m = new WebAssembly.Module(require('fs').readFileSync('m.wasm'));"
        f"console.log(new WebAssembly.Instance(m).exports.f({x}))"], capture_output=True, text=True)
    return int(out.stdout)

def in_wabt(x):
    # wasm-interp takes and prints unsigned values: f(i32:4294967295) => i32:0
    out = subprocess.run(["wasm-interp", "m.wasm", "-r", "f", "-a", f"i32:{x % 2**32}"],
                         capture_output=True, text=True)
    return int(out.stdout.split("=> i32:")[1])

for x in (0, 1, -1, 123456789, -2147483648):
    results = {"wasmtime": in_wasmtime(x), "v8": in_v8(x), "wabt": in_wabt(x)}
    # bring everything to signed i32 before comparing
    results = {k: (v + 2**31) % 2**32 - 2**31 for k, v in results.items()}
    agree = len(set(results.values())) == 1
    print(f"f({x}) = {results['v8']}", "(all agree)" if agree else f"DISAGREE: {results}")

f(0) = 0 (all agree)
f(1) = 129 (all agree)
f(-1) = 0 (all agree)
f(123456789) = 1159671356 (all agree)
f(-2147483648) = 64 (all agree)

The handling of wabt's unsigned numbers is typical of real differential testing: most of the work is normalising each engine's way of taking arguments and reporting results, and the first "disagreements" you find are usually in that normalisation.

The second, more powerful kind compares your compiler with an independent implementation of your language: an interpreter, written as simply as possible, directly from the language's semantics. Any program on which the compiled code and the interpreter disagree has found a bug in one of them. A simple interpreter is worth writing for this alone.

#Layer 5: fuzzing27.6

Differential testing becomes fuzzing when the programs are generated at random. A generator produces programs in your language, the compiler and the reference interpreter run each one, and any disagreement is saved as a failing test. Run long enough, this finds the bugs in the corners that neither you nor your users would have tested.

Here is a complete small fuzzer. It generates random 32-bit integer expressions over one variable, "compiles" them to WebAssembly by printing the text format, runs them in V8, and compares the results with a Python evaluator that implements WebAssembly's integer semantics directly. The compiler takes a flag that introduces a bug, to show the fuzzer finding it:

import random, subprocess, json, wasmtime

OPS = ["add", "sub", "mul", "and", "or", "xor", "shl", "shr_s", "shr_u", "div_s", "rem_u"]

def gen(rng, depth):
    """A random expression: ("x",), ("const", n) or (op, a, b)."""
    if depth == 0 or rng.random() < 0.3:
        return ("x",) if rng.random() < 0.5 else ("const", rng.choice([0, 1, -1, 7, 31, 2**31 - 1, -2**31, rng.randrange(-2**31, 2**31)]))
    return (rng.choice(OPS), gen(rng, depth - 1), gen(rng, depth - 1))

def s32(n):
    return (n + 2**31) % 2**32 - 2**31

class Trap(Exception):
    pass

def evaluate(e, x):
    """The reference: WebAssembly's i32 semantics, written out in Python."""
    if e[0] == "x": return x
    if e[0] == "const": return e[1]
    op, a, b = e[0], evaluate(e[1], x), evaluate(e[2], x)
    u = lambda n: n % 2**32
    if op == "add": return s32(a + b)
    if op == "sub": return s32(a - b)
    if op == "mul": return s32(a * b)
    if op == "and": return s32(a & b)
    if op == "or": return s32(a | b)
    if op == "xor": return s32(a ^ b)
    if op == "shl": return s32(a << (b % 32))
    if op == "shr_s": return a >> (b % 32)
    if op == "shr_u": return s32(u(a) >> (b % 32))
    if op == "div_s":
        if b == 0 or (a == -2**31 and b == -1): raise Trap()
        q = abs(a) // abs(b)
        return s32(q if (a < 0) == (b < 0) else -q)
    if op == "rem_u":
        if b == 0: raise Trap()
        return s32(u(a) % u(b))

def compile_expr(e, buggy=False):
    """The 'compiler': an expression to the text format."""
    if e[0] == "x": return "(local.get 0)"
    if e[0] == "const": return f"(i32.const {e[1]})"
    op = e[0]
    if buggy and op == "shr_s":
        op = "shr_u"                                  # the deliberate bug
    return f"(i32.{op} {compile_expr(e[1], buggy)} {compile_expr(e[2], buggy)})"

def run_in_v8(exprs, inputs, buggy):
    funcs = "".join(f'(func (export "f{i}") (param i32) (result i32) {compile_expr(e, buggy)})\n'
                    for i, e in enumerate(exprs))
    open("fuzz.wasm", "wb").write(wasmtime.wat2wasm(f"(module {funcs})"))
    js = f"""
      const {{ exports }} = new WebAssembly.Instance(new WebAssembly.Module(require('fs').readFileSync('fuzz.wasm')));
      const out = [];
      for (let i = 0; i < {len(exprs)}; i++)
        for (const x of {json.dumps(inputs)}) {{
          try {{ out.push(exports['f' + i](x)); }} catch (e) {{ out.push('trap'); }}
        }}
      console.log(JSON.stringify(out));"""
    return json.loads(subprocess.run(["node", "-e", js], capture_output=True, text=True).stdout)

def fuzz(seed, count, buggy=False):
    rng = random.Random(seed)
    exprs = [gen(rng, 4) for _ in range(count)]
    inputs = [0, 1, -1, 5, -123456, 2**31 - 1, -2**31]
    got = iter(run_in_v8(exprs, inputs, buggy))
    failures = []
    for e in exprs:
        for x in inputs:
            try:
                want = evaluate(e, x)
            except Trap:
                want = "trap"
            if next(got) != want:
                failures.append((e, x, want))
    return exprs, inputs, failures

exprs, inputs, failures = fuzz(seed=1, count=300)
print(f"{len(exprs)} expressions, {len(exprs) * len(inputs)} runs, {len(failures)} disagreements")

exprs, inputs, failures = fuzz(seed=1, count=300, buggy=True)
print(f"with the bug: {len(failures)} disagreements")
smallest = min(failures, key=lambda f: len(compile_expr(f[0])))
print("smallest:", compile_expr(smallest[0]), "with x =", smallest[1])

300 expressions, 2100 runs, 0 disagreements
with the bug: 55 disagreements
smallest: (i32.shr_s (local.get 0) (local.get 0)) with x = -1

The correct compiler agrees with the reference on all 2,100 runs. The buggy one is caught at once, and choosing the smallest failing expression points straight at the bug. Real fuzzers reduce failures automatically: repeatedly simplify the failing program, keeping each simplification that still fails, until nothing more can be removed. Binaryen's wasm-reduce does this for WebAssembly modules, and C-Reduce and its successors do it for source programs.

Several existing tools generate WebAssembly to fuzz with:

#Layer 6: the browser27.7

Everything above runs in Node, which uses the same V8 as Chrome. But users also run Firefox and Safari, and the host side of your runtime uses browser APIs that Node lacks. Playwright runs tests in all three browsers' engines, headless, from a script:

import { chromium, firefox, webkit } from 'playwright';

for (const browserType of [chromium, firefox, webkit]) {
  const browser = await browserType.launch();
  const page = await browser.newPage();
  await page.goto('http://localhost:8000/tests/runner.html');
  const result = await page.evaluate(() => window.testResults);   // set by the page
  console.log(browserType.name(), result.passed, 'passed', result.failed, 'failed');
  await browser.close();
}

Keep the browser layer thin: a page that loads a batch of compiled test modules and reports their output, run against the same expected outputs as layer 3. The point is to catch the differences between engines, not to run the whole suite three more times.

#Performance tests27.8

Speed regressions are bugs too, but timings are noisy, especially on shared CI machines. Track deterministic proxies instead, and time things only occasionally:

For real timings, run benchmarks in steady state (Chapter 25), many times, on a quiet machine, and compare distributions rather than single numbers.

#A case study: this book27.9

Every example in this book was checked by a harness built on these ideas, in about five hundred lines of Python and JavaScript, in the scripts directory beside the chapters:

The book's harness found real mistakes while it was being written: wrong byte counts, wrong offsets in disassembly, misremembered error messages, and more than one example whose output was simply not what the text said. Each was caught because the claim was executable. The same is true of a compiler: every expectation that can be checked by a machine should be.

#What you have seen27.10

A compiler's tests come in layers. Validate every module with several validators. Compare generated code with golden files in the text format. Run programs and compare their output with expectations stored beside them, in every configuration. Compare engines with each other, and your compiler with a simple interpreter. Fuzz with random programs, and reduce the failures. Run a thin layer of tests in real browsers. Each layer is built from existing tools, and together they make a compiler you can change with confidence.

That is the end of the book. The appendices follow: an instruction reference, a guide to the tools, and suggestions for further reading.