Self-Hosting and the Three-Stage Build
A self-hosted compiler compiles itself, and that gives you a genuine test for free: stage 2 and stage 3 are built from identical source by compilers that should behave identically, so their binaries must be byte-identical. When they are not, the compiler miscompiled itself.
What does a three-stage build actually prove, and why must stage 2 and stage 3 be identical?
The compiler as a fixed point of its own compilation. Stage 2 and stage 3 are two binaries produced from one source by two compilers that are supposed to be behaviourally equivalent; the equality of those binaries is a checkable proposition about the compiler, expressed entirely in artifacts. That representation exists because a compiler is the one program whose correctness can be probed by applying it to itself.
The stage 2 / stage 3 comparison is a valid test only if the compilation is deterministic in every respect that affects output — no timestamps, no absolute paths, no hash ordering that varies between runs, no parallelism-dependent naming. Under that precondition, any difference between the two binaries implies that stage 1 and stage 2 behaved differently on identical input, which means at least one of them compiled the compiler incorrectly. Without determinism the test is worthless, because a difference proves nothing, which is why [[reproducible-compilation]] is a prerequisite rather than a neighbouring topic.
Key points
- Stage 2 and stage 3 are compiled from identical source by two compilers that should be behaviourally identical, so their binaries must be byte-identical.
- A mismatch means stage 1 and stage 2 disagreed, which means one of them compiled the compiler incorrectly.
- Stage 1 and stage 2 are *expected* to differ, because stage 1 was compiled by a worse compiler. The fixed point begins at stage 2.
- The check is only meaningful if compilation is deterministic, which makes reproducibility a prerequisite rather than a related topic.
- It is a consistency check, not a correctness check: a bug present identically in both stages passes, and so does a self-reproducing backdoor.
- Self-hosting also buys dogfooding and costs a bootstrap dependency plus a compiler source constrained to the previous release's features.
Why three stages, and what each one is for
make bootstrap, and is used in various forms by LLVM and rustc. It is not universal: toolchains that bootstrap from a previous binary release and ship stage 1 skip the check entirely, and the check is only meaningful where the build is deterministic.Recall the chain: stage 1 is the compiler source compiled by stage 0, stage 2 is the same source compiled by stage 1, stage 3 is the same source compiled by stage 2. It is easy to see why you need stage 2 — stage 1 was compiled by a poor compiler and would be slow. It is less obvious why you build stage 3 at all, since it is functionally the same as stage 2.
You build it to compare it. Stage 2 and stage 3 were produced from *the same source* by two compilers — stage 1 and stage 2 — that were themselves built from the same source and should therefore implement the same language identically. If the two compilers behave the same on all inputs, they behave the same on this input, and the two outputs must be byte-identical.
So the comparison is a real test with a real failure signal. A difference means stage 1 and stage 2 disagreed about how to compile the compiler, which means one of them is wrong. Since stage 2 is the artifact that ships, a mismatch is a signal that you may be about to ship a compiler produced by a miscompilation.
Note precisely what stage 1 and stage 2 differ in: not what they do, but what compiled them. Stage 1 came from stage 0, stage 2 came from stage 1. If stage 0 had a code-generation bug, stage 1 may be subtly wrong even though its source is correct — and stage 3, being compiled by a stage 2 that was compiled by that broken stage 1, is where the discrepancy shows up.
1stage0 = compile_with(external_compiler, bootstrap_source)2stage1 = compile_with(stage0, compiler_source)3stage2 = compile_with(stage1, compiler_source)4stage3 = compile_with(stage2, compiler_source)5 6assert stage2 == stage3 # byte-for-byte7 8Why: stage1 and stage2 come from the SAME source and should be9behaviourally identical compilers. Two identical compilers applied to10one input must produce one output. If stage2 != stage3, then stage111and stage2 disagreed -- so one of them compiled the compiler wrongly.12 13Why not assert stage1 == stage2?14 Because stage1 was built by stage0, which optimizes differently (or15 not at all). Same behavior, different code. Only from stage2 onward16 is the chain a fixed point.The last note is the part people get wrong. Stage 1 and stage 2 are supposed to differ — they are the same program compiled by different compilers. The fixed point starts at stage 2, which is why the comparison is 2 against 3 and never 1 against 2.
What it catches, and what it does not
It catches real miscompilations, and there are documented cases where a GCC bootstrap comparison failure was the first sign of a code-generation bug. It is a particularly good test because the input — a compiler — is a large, complex, self-referential program exercising an enormous amount of the language and of the optimizer, in a way no hand-written test suite does.
It also catches non-determinism, and in practice that is what it catches most often. Any timestamp, absolute path, iteration over a hash map with address-dependent ordering, or parallelism-dependent name mangling will make stage 2 and stage 3 differ. Those are usually build hygiene issues rather than miscompilations, but they are worth finding: a compiler that is not deterministic cannot be verified by this test at all, and cannot support [[reproducible-compilation]] downstream.
What it does not catch is the more important half. It is a *consistency* check, not a correctness check. If the compiler has a bug that both stage 1 and stage 2 exhibit identically, the two outputs agree and the test passes. A compiler that miscompiles a construct its own source does not use will pass every stage. And — the case that makes this a lesson rather than a technique — a compiler containing a deliberate backdoor that reproduces itself will pass, because stages 2 and 3 are equally infected. That is [[trusting-trust]].
| Condition | Detected? | Why |
|---|---|---|
| Stage 0 miscompiled stage 1typical | Usually | Stage 1 then compiles differently from stage 2, so the outputs diverge |
| Non-deterministic compilation | Yes | Two runs of the same compiler on the same input differ, which is exactly the comparison |
| A code-generation bug hit by the compiler's own sourcetypical | Often | It affects stage 1 and stage 2 differently only if they were built differently — which they were |
| A bug in a construct the compiler does not use | No | The compiler is the only test input; unexercised paths are untested |
| A bug present identically in both stages | No | Both outputs are wrong in the same way, so they match |
| A self-reproducing backdoor | No | It infects both stages equally and is therefore invisible to a consistency check |
Self-hosting as a design decision
Beyond the verification, writing a compiler in its own language is a deliberate choice with arguments on both sides. The case for it is dogfooding of an unusually pure kind: the language team is the compiler's heaviest user, so every ergonomic failure, every missing feature and every bad diagnostic is felt first by the people who can fix it. Languages that self-host tend to have better tooling for exactly this reason.
The case against is real too. It creates the bootstrap dependency, it lengthens the build by a factor of two or three, and it means the compiler's own source is constrained to features the bootstrap compiler already supports — so the team is always writing in a version of the language one release behind the one they are building. It also risks a monoculture of judgement: a language optimised by and for people writing compilers is a language optimised for one workload.
The middle position is common and sensible. Many toolchains self-host the compiler and write the runtime, the standard library's low-level parts, or the build system in something else. And plenty of excellent compilers are not self-hosted at all — writing a compiler in a language well suited to compilers, rather than in the language being compiled, is a defensible choice that simply gives up the bootstrap ceremony and the dogfooding.
- Self-hosting makes the language team its own most demanding user, which shows up in diagnostics and tooling quality.
- It costs a bootstrap chain, a build that is two to three times longer, and a compiler source restricted to last release's features.
- It provides the stage 2 / stage 3 identity check, which is a large, free, self-generating test.
- It creates the exact condition
[[trusting-trust]]exploits: the compiler that builds the compiler is the compiler. - It is not obligatory: a compiler written in a different language is a legitimate design, and gives up only the two items above.
How it works
The steps, in the order the compiler takes them.
- Build stage 1 by compiling the compiler source with stage 0, whatever that is.
- Build stage 2 by compiling the same source with stage 1.
- Build stage 3 by compiling the same source with stage 2.
- Compare stage 2 and stage 3 byte for byte, usually after stripping anything intentionally non-reproducible such as embedded build identifiers.
- On a mismatch, investigate in two directions: first eliminate non-determinism in the build, then look for a code-generation difference between stage 1 and stage 2.
- Ship stage 2, which is the compiler source compiled by a compiler with the same optimizations, verified against stage 3.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- The bootstrap comparison fails and the cause turns out to be an embedded timestamp or build path — a real finding, but a build hygiene problem rather than a compiler bug.
- The comparison fails because a pass iterates a hash map keyed by pointer addresses, so output ordering varies between runs on an address-randomised system.
- The comparison passes and the compiler is still wrong, because the bug is in a language construct the compiler's own source does not use.
- The comparison is skipped to save build time, and a miscompilation reaches a release that would have been caught.
- A parallel build produces different temporary names in different runs and the comparison becomes flaky, so the team disables it rather than fixing the determinism.
When it helps
- Validating a compiler change against an enormous, realistic input for free — the compiler's own source exercises more of the language than any test suite anyone would write.
- Finding non-determinism in a build, which is otherwise hard to detect and is a prerequisite for reproducible builds downstream.
- Establishing that a new stage 0 — a new bootstrap compiler, a new host toolchain — did not introduce a miscompilation.
When it hurts
- As a substitute for a test suite. It exercises exactly one program, so anything the compiler's own source avoids is entirely untested by it.
- As a security guarantee. It proves the chain is self-consistent, which is precisely the property a self-reproducing compiler attack preserves.
What it costs
Every one of these is paid by something.
- The three-stage build buys a large self-generating correctness signal and costs a compile of the entire compiler that is thrown away — typically a third of a long build, spent to produce a binary nobody ships.
- Self-hosting buys dogfooding and the identity check, and costs a bootstrap dependency plus a source base restricted to previously-supported features.
- Requiring byte-identical output buys the check and costs the elimination of every convenient non-determinism — timestamps, paths, address-ordered iteration — which is real engineering work spread across the whole compiler.
- Shipping stage 2 rather than stage 1 buys a properly optimized compiler and costs the extra stage; shipping stage 1 saves time and gives up both the optimization and the check.
What else you could do
What a different compiler or language does instead, and when that is better.
- A differential test against another compiler for the same language, which catches bugs a self-consistency check cannot because the two implementations are genuinely independent — see
[[differential-testing]]. - Random program generation and comparison, as Csmith does for C: it exercises constructs no real program contains, which is exactly the complement of what the compiler's own source covers — see
[[compiler-fuzzing]]. - Translation validation, proving that a specific compilation preserved semantics rather than that two compilations agreed — see
[[translation-validation]]. - A formally verified compiler such as CompCert, where the correctness argument is a proof rather than an artifact comparison — see
[[verified-compilers]]. - Diverse double-compiling, which uses a second, independent compiler to check that the self-hosted result is what the source says — the one technique in this list that addresses the backdoor case, covered in
[[trusting-trust]].
See it for yourself
The flag, dump or tool that shows you this directly.
- Run one:
make bootstrapin a GCC source tree performs the three-stage build and the comparison by default, and reports a bootstrap comparison failure explicitly if the stages differ. - See the comparison itself: GCC's
comparestep diffs the stage 2 and stage 3 object files; the build log names which object differed, which is the starting point for any investigation. - Test determinism directly without a full bootstrap: compile one file twice and
cmpthe outputs. Any difference is a determinism bug and would break the bootstrap comparison too. - Rust's
x.py build --stage 2and its bootstrap documentation show the staging explicitly, including which artifacts are compared. - Our own determinism check is in
scripts/compilers-sim.test.ts: it compiles each example twice and asserts the IR, the SSA, the optimized IR and the assembly are all identical, which is the same proposition at a much smaller scale.
Plausible wrong readings
Stated the way a confident engineer states them.
- "Stage 1 and stage 2 should be identical." They should not. They are the same program compiled by different compilers, and only from stage 2 onward is the chain a fixed point.
- "A successful bootstrap proves the compiler is correct." It proves the chain is self-consistent. A bug shared by both stages, and any self-reproducing modification, passes it.
- "A bootstrap comparison failure means a compiler bug." Most of them are non-determinism in the build. That is worth fixing and it is a different problem.
- "Self-hosting is required for a serious language." It is a common choice with real benefits and real costs, and several serious compilers are written in something else entirely.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
A compiler that is written in its own language gets compiled several times during its build. The last two of those compilations use the same source and two compilers that are supposed to behave identically, so the two results should be exactly the same file. Checking that they are is a real test, and when it fails something is genuinely wrong.
practical
If a bootstrap comparison fails, look for non-determinism first: timestamps, absolute paths, anything iterating a hash map keyed by addresses, anything whose name depends on how the build was parallelised. Those account for most failures. If the build is genuinely deterministic and the stages still differ, you have a code-generation difference between two compilers built from the same source, which is a real miscompilation and worth escalating.
advanced
The property being tested is a fixed point: the compiler is a function from source to binary, and stage 2 is the point where applying that function again changes nothing. That framing makes the limits obvious. A fixed point says the function agrees with itself; it says nothing about whether the function is the one the source describes. Any modification that is preserved under the function — which is exactly what a self-reproducing backdoor is engineered to be — sits at the fixed point just as comfortably as the correct compiler does. This is why the technique is a good bug detector and a worthless security control, and why the only known answer to the security question, diverse double-compiling, works by introducing a *second, independent* function and checking that both agree on the source rather than that either agrees with itself.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
scripts/compilers-sim.test.ts compiles the same source twice in one process and compares the textual IR, SSA, optimized IR and assembly. It establishes that our pipeline has no run-to-run variation, which is the same property, and it does not involve a self-hosted compiler or a bootstrap chain at all.If you were asked this in an interview
- Why must stage 2 and stage 3 be byte-identical, and why is it wrong to expect that of stage 1 and stage 2?
- Name two things a bootstrap comparison catches and two it cannot.
- Why is determinism a prerequisite for this check rather than a nice-to-have?
Connections
- Testing & Reliability Engineering — Self-consistency checks and their limits as verificationA stage 2 / stage 3 comparison is a metamorphic test — the same relation that underpins much property-based testing — and it inherits that family's blind spot for errors preserved by the relation. The general theory of what such tests can and cannot establish is owned there.