The chicken and the egg: how Xo bootstraps a compiler written in Xo

xo is written in Xo. To build it, you need an Xo compiler, which is also xo. Every self-hosted language meets this chicken and egg problem, and the answers differ in interesting ways. This post is about Xo’s answer, and about the check we run to show it holds.

The seed

The first Xo compiler on a machine is built by a seed: Xo’s original implementation, written in Go. From a checkout of the repository, Go builds the seed, and the seed builds the compiler written in Xo:

go build -o .tools/bin/xo-seed ./cmd/xo
XO_SELF_DRIVER=0 .tools/bin/xo-seed build --backend=arm64 -o .tools/bin/xo selfhost/xo

(On an x86-64 host the second command uses the LLVM backend; the getting started page has both.) The Go implementation is frozen: new language work happens only in the Xo code and the specification, and the seed’s job is just to get the first Xo compiler built. After that, Xo builds Xo.

Update, 2026-10-13: the Go implementation has since been deleted (see We deleted the Go compiler). The seed on a machine with no xo is now the last Go version, tagged go-compiler-final, followed by a short recorded chain of intermediate compilers, and go run ./scripts/xobuild does it all. The commands above are for history.

The proof: a fixed point

How do you know the compiler you just built is right? Build it again with itself, and compare. scripts/bootstrap-xo.sh does it in three stages, each with empty caches:

1. the seed builds the compiler: s1;
2. s1 builds the compiler: s2;
3. s2 builds the compiler: s3.

s1 and s2 are both built from the same compiler source, so if the compiler’s output depends only on its input, what they build must be the same: s2 (built by s1) and s3 (built by s2) must be byte for byte identical. If they are not, the output depends on something other than the source. We also check that s1 equals s2.

Here is what that looks like in practice:

On the arm64 Linux run, the Go toolchain was deleted from the machine (/usr/local/go gone, no go on the PATH) once the seed was built, so the later stages could not have used Go. On Windows the two builds are identical except for the time stamp and checksum that the Windows linker writes into the file header; with those two fields zeroed, the files match.

Why identical bytes, and not just passing tests

A compiler that passes its tests can still differ in ways no test looks at. Identical bytes rule that out for the compiler’s own build, and every time a stage failed or differed, it pointed at a real problem:

• On a clean Linux machine, the first bootstrap attempt failed at s1: the Xo compiler, given a relative path to the standard library, doubled part of a path while building the TLS library. The development Mac never showed it because its cache already held that library. Only a cold build, which is what the bootstrap script does, could find it.
• On x86-64 Linux, s2 and s3 produced identical LLVM IR but different binaries. The cause was ThinLTO, which names the local symbols it promotes across modules with a hash that, by our experiment, follows each module’s path in the build directory. Each stage builds in its own directory, so the names differed. x86-64 builds of the compiler now use no link time optimization, and the binaries match.

There is a bonus on x86-64 Linux: s1, built by the seed written in Go, and s2 and s3, built by the compiler written in Xo, are all the same file. Two different compilers, in two different languages, produced the same bytes from the same source.

The runtime is in the loop too

The compiler is an Xo program like any other, so it links the same native runtime every Xo program does, including the parts of that runtime now written in Xo. Each bootstrap stage runs a full compile of the largest Xo program we have, with that runtime underneath. A runtime bug that changed the compiler’s behavior would show up as a stage that differs.

Trusting trust

In his 1984 Turing Award lecture, “Reflections on Trusting Trust,” Ken Thompson showed why a self-compiling compiler is hard to trust: a compromised compiler binary can insert a backdoor into the programs it compiles, including into new builds of itself, while the source looks clean. Reading the source does not help if you cannot trust the binary that compiles it.

The known answer has two parts. The first is reproducibility: the same source must give the same bytes, so anyone can rebuild and compare. The second is David A. Wheeler’s diverse double-compiling: build the compiler’s source with a second, independent compiler, use that result to build the source again, and check that the final binary is identical to the one you are asked to trust. A backdoor would have to be present in both independent compilers in the same way.

Xo has the first part: byte-identical fixed points on every platform above. It also has the ingredients of the second, since the seed written in Go is an independent implementation of Xo, and the x86-64 result above already shows the Go-built and Xo-built compilers agreeing byte for byte. Running that as a formal diverse double-compiling check against a given xo binary is an idea we have not done yet.

How others do it

Every self-hosted compiler needs a seed, and they choose differently. Go needs an earlier Go release to build a new one. Zig keeps a WebAssembly build of its own compiler in its repository, which a small C program can translate and compile on any machine with a C compiler, so building Zig needs no earlier Zig. Xo today uses its original Go implementation as the seed and checks the result with fixed points.

Like most of Xo, this machinery was built by AI agents, under a rule a person set early on: a rebuild that does not produce the same bytes is a problem until proven otherwise. So far, every time, it was.