Bootstrapping a Self-Hosted Compiler and Why the Build Is Compared Against Itself

Most compilers are written in the language they compile. A C compiler’s source is largely C; a compiler for a systems language is usually written in that language. The arrangement is convenient because the authors can use the language’s own abstractions, and it is a problem at exactly one moment: the first build, when no compiler for that language exists on the machine.

The standard solution is a staged build, and the reason it has three stages rather than two is not redundancy. The stages are a correctness check, and the property they check is one that no test suite can establish by itself.

The chicken-and-egg problem and the bootstrap compiler

A self-hosted compiler needs a working compiler to be compiled. The usual answer is to start from a compiler that already exists: a different implementation of the same language, an earlier version of the same compiler, or a compiler for a subset of the language.

Building the new compiler with that existing compiler produces the first-stage binary. That binary is built by a compiler whose code generation may be quite different from its own, and it may therefore contain code that is subtly wrong in ways the source does not explain: a miscompiled construct, a wrong assumption about an undefined behaviour, a difference in how an extension is handled. The first-stage binary is a hypothesis, not a result.

The second stage is the new compiler compiled by the first-stage binary. Now the compiler is compiling its own source with its own code generator. If the source is correct and the first-stage binary is faithful, the second-stage binary should be a correct compiler. But “should be” is doing work: the second-stage binary is the product of a compiler that was itself produced by a foreign compiler, and any defect introduced at the first stage propagates into the second.

The third stage is the second-stage binary compiling the same source again. The output of the third stage and the output of the second stage are compared. If they are byte-identical, the compiler is a fixed point of its own compilation: compiling its source with itself yields itself. That is the check, and it is a strong one because it is insensitive to what the compiler does internally. It does not verify that the compiler is correct; it verifies that the compiler is stable, which is the property required for any further reasoning about it.

Why the comparison is meaningful

A fixed point means the transformation from source to binary has converged. If the second-stage binary miscompiled its own source in some way, the third-stage binary would differ, because the third stage is compiled by the miscompiling compiler and the second is not. The comparison therefore detects any difference between the compiler’s behaviour when it is the compiler and when it is the program being compiled, which is exactly the class of bugs that a self-hosted build is prone to.

The comparison is a byte comparison of the produced binaries, and byte comparison requires determinism. Two binaries built from the same source by the same compiler must be identical for the check to mean anything, which is why bootstrapping a compiler and making its output reproducible are related problems: a compiler whose output varies between runs cannot be checked by a fixed-point comparison, because the third stage will differ from the second for reasons that have nothing to do with correctness. The mechanisms behind those variations are enumerated in Sources of Nondeterminism in Compiled Artifacts.

There is a second, subtler use of the staged build. The first stage is often built with a different compiler, and comparing the first stage’s output to the second’s tests the new compiler against a reference implementation. Differences are expected in code generation and are not errors, but differences in the diagnostics produced for a test suite are meaningful: the two compilers should accept and reject the same programs, and a divergence points at a semantic difference that the source does not intend.

Stage boundaries and what each one proves

The stages are conventionally named, and the naming reflects what each one establishes.

Stage one is the compiler built by a foreign compiler. It establishes that the source is syntactically and semantically acceptable to a compiler that is not itself. This catches a class of error that a self-hosted build cannot: a construct the compiler accepts because of a bug in its own front end, which a conforming foreign compiler rejects.

Stage two is the compiler built by stage one. It establishes that the compiler can compile itself. If stage one produced a binary that crashes or produces wrong output, stage two fails, and the failure is attributable to stage one’s code generation rather than to the source.

Stage three is stage two building the compiler again, and its output is compared to stage two’s. Equality establishes the fixed point. The comparison is the acceptance criterion for the whole bootstrap, and it is the reason a release build of a self-hosted compiler is normally a stage-three build: the binary that ships is one that has been produced by a compiler that has been shown to be stable.

# The shape of a staged build, with a foreign compiler as the seed
CC=seed-cc ./configure --prefix=/opt/newcc && make    # stage 1: the seed builds newcc
cp ./cc /tmp/cc.stage1
make clean && CC=/tmp/cc.stage1 ./configure && make   # stage 2: stage 1 builds newcc
cp ./cc /tmp/cc.stage2
make clean && CC=/tmp/cc.stage2 ./configure && make   # stage 3: stage 2 builds newcc
cmp /tmp/cc.stage2 ./cc                               # equality is the fixed point

The commands above are schematic: real build systems have their own targets and their own naming. The structure, a seed compiler, a rebuild under the new compiler, and a comparison, is what every self-hosted bootstrap implements.

The trusting-trust problem and what bootstrapping can and cannot fix

The fixed-point check establishes stability, not trust. A compiler that has been subverted in a way that survives its own recompilation will pass every stage of the check, because each stage reproduces the subversion. The classical statement of this is Thompson’s argument that a compiler can be built to insert a back door into programs it compiles, including into a future version of itself, so that the back door persists in the binary while being absent from the source.

The argument matters here because it defines what a bootstrap can and cannot establish. A staged build proves that the shipped binary corresponds to the source it was built from, given the seed compiler. It does not prove that the seed compiler is honest, and it cannot, because the seed is an unexamined binary. The chain of trust terminates at a binary that someone else built.

The mitigations are all variations on reducing the size and the number of unexamined binaries. One is to build the seed from source with a compiler that is itself built from source, iterating back to a compiler small enough to audit. This is why some projects maintain a minimal bootstrap path that uses only a tiny, simple compiler and a small amount of hand-written code. Another is diverse double compilation: build the compiler with two independent compilers, and compare the outputs. If the two produce identical binaries from identical source, a subversion in one would have to be reproduced exactly by the other, which is far less likely than a subversion in one surviving its own recompilation.

Diverse double compilation has a cost that makes it rare in practice: it requires two compilers capable of building the target, which for a self-hosted systems language usually means maintaining a second implementation. The projects that do it treat the second compiler as a bootstrap artifact rather than a product, which bounds the maintenance.

Bootstrapping the rest of the toolchain

The compiler is not the only component that must be built from something. The assembler, the linker, and the C library are also self-hosted in the same sense, and the ordering constraints between them are tighter than they look.

The linker is needed to produce the compiler binary, and the compiler is needed to build the linker. The usual resolution is that the seed toolchain provides a linker for the first stage, and the new linker is built by the new compiler once it exists. The C library is the hardest case: it is needed by the compiler’s own runtime and by every program the compiler produces, and a new C library cannot be tested until a compiler exists to compile test programs. Bootstrapping from a seed libc and then rebuilding is the standard sequence, with the rebuilt libc installed into a sysroot that the rebuilt compiler then uses.

This ordering is why a cross-toolchain and a bootstrap toolchain are related but not identical. A cross-toolchain can borrow the target’s libc because a compiler for the target already exists somewhere, as described in Target Triples, Sysroots, and What Actually Changes When Cross-Compiling; a bootstrap must produce every component in sequence because nothing for the target exists yet. The sysroot that a bootstrap produces is the artifact of that sequence, and its contents are determined by the order in which the components were built, which is why a bootstrap is reproducible only if the whole sequence is pinned.

The final point is about what the stages cost. A three-stage bootstrap compiles the compiler twice, which for a large compiler is a substantial multiple of a single build. The second and third stages exist for verification, not for production, and builds that skip them are trading a check for time. The check is worth running when the compiler’s source has changed in a way that affects code generation, and it is worth running on a release candidate rather than on every commit.