Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 61 ยท Getting Started

Bootstrapping and Cross-Compilers

Learn how compilers are built with themselves: T-diagrams, bootstrapping from a small subset, self-hosting, three-stage builds, cross-compilers and the Canadian cross.

A C compiler is usually written in C. A Rust compiler is written in Rust, and the Go compiler is written in Go. That sounds like a chicken-and-egg puzzle: to compile the compiler you already need a compiler. How did the very first one come to exist? And how do you build a compiler for a brand-new processor on which no compiler exists yet?

Both questions have clean answers. The first is bootstrapping: grow a compiler from a tiny seed, one step at a time. The second is cross-compilation: use a compiler on one machine to produce programs for another. This lesson explains both with a simple notation, the T-diagram, and lets you run the build steps in a small simulation that checks which steps are even possible.

Describing a compiler: three languages

Every compiler involves three languages, and mixing them up is the main source of confusion:

  • the source language S that it reads,
  • the target language T that it produces (usually the machine code of some processor), and
  • the implementation language I in which the compiler itself is written. When I is machine code, the compiler is directly executable on that machine.

A T-diagram puts these three on a T-shaped box: S at the top left, T at the top right, and I at the bottom. We will write it as [S -> T] in I.

flowchart TB
    subgraph T1["Compiler"]
        direction LR
        S["Source S"] --> TT["Target T"]
        IMPL["Written in I"]
    end

A compiler [S -> T] in I. For example [C -> x86] in x86 is a C compiler for x86 that is itself an x86 program.

Two T-diagrams can be combined when the implementation language of one matches a language the other understands. If you have a compiler [L -> M] in H that runs on machine H, and a program written in L, then compiling that program produces the same program written in M. When the program is itself a compiler [S -> T] in L, the result is [S -> T] in M. There is one extra condition that people forget: the compiler that does the work must be runnable. A program written in the machine language of a machine you do not have cannot be executed.

Bootstrapping a language from nothing

Suppose you have designed a language Lang and you want a compiler for it that is written in Lang itself (a self-hosting compiler), running on machine A. You only have an assembler. The standard route:

  1. Stage 0. Write a small compiler by hand for a tiny subset of the language, Core, directly in machine code (or assembly) for A. The subset needs only the features required to write a compiler: functions, integers, strings, simple control flow. It need not be fast or friendly. This is [Core -> A] in A.
  2. Stage 1. Write a compiler for the full language in the subset Core: [Lang -> A] in Core. Run the stage-0 compiler on it. The result is [Lang -> A] in A: a real compiler for the full language, as a machine-code program.
  3. Self-hosting. Now rewrite the compiler in Lang itself, [Lang -> A] in Lang. Compile it with the stage-1 compiler to get stage 2. From now on, new features and fixes can be written in Lang, and every version of the compiler is compiled by the previous one.

The stage-0 compiler can then be thrown away. Languages such as Pascal, C, Go and Rust were bootstrapped in roughly this way, often using an existing compiler of another language for the first step instead of hand-written machine code (the first Rust compiler was written in OCaml, for example).

A self-hosting compiler is a strong test of a language: the compiler is a large, serious program, so a language that can compile itself is clearly expressive enough for real work. It also means the language developers use their own product every day.

The three-stage fixed-point test

Self-hosting suggests a simple correctness check. Build the compiler three times:

  • Stage 1 is the compiler built by the old compiler (the seed).
  • Stage 2 is the compiler's source built by stage 1.
  • Stage 3 is the compiler's source built by stage 2.

Stage 1 and stage 2 may differ: stage 1 was produced by a different compiler, maybe a slow or less optimizing one, so its machine code differs. But stage 2 and stage 3 were both produced by compilers that behave identically (both are builds of the same source), so their output should be bit-for-bit identical. If stage 2 and stage 3 differ, something is wrong: either the compiler has a bug or its output depends on something it should not, such as the time or a memory address. GCC's build system runs exactly this comparison. The code below simulates it.

Cross-compilers

A cross-compiler runs on one machine and produces code for a different one: [L -> B] in A. You need it whenever the target cannot (yet) host a compiler: microcontrollers with a few kilobytes of memory, a new processor architecture before any software exists, game consoles, phones. Android apps and embedded firmware are built this way.

To get a native compiler for a new machine B when you only own machine A:

  1. Take a compiler for L that runs on A, [L -> A] in A.
  2. Take the compiler's source, which must be retargetable (the code generator can be switched to a new target), and compile it for target B: [L -> B] in L. Compile it with the compiler from step 1, producing the cross-compiler [L -> B] in A.
  3. Compile the same source [L -> B] in L again, now with the cross-compiler. The result is [L -> B] in B: a native compiler for B, which you copy to a B machine. From then on, B is self-sufficient.

The Canadian cross

Sometimes three machines are involved: you build on A, the compiler should run on B, and it should produce code for C. This arises when B is a slow or awkward machine, for example building a compiler that runs on a small embedded board but generates code for another board. The trick is to build a cross-compiler for B first, then use it to compile the source retargeted at C:

TEXT
[L -> A] in A    builds    [L -> B] in L    giving   [L -> B] in A    (cross: A to B)
[L -> B] in A    builds    [L -> C] in L    giving   [L -> C] in B    (runs on B, targets C)

The odd name is a joke from the 1980s, when Canada had three national political parties. Build systems call these three roles build, host and target.

Simulating the build steps

The program models a compiler as a triple (S, T, I) and the build step as a function. It refuses steps that are impossible: compiling something with a compiler that reads a different language, or running a compiler written for a machine you do not own. Then it plays through the cross-compiler, Canadian cross and bootstrapping examples, and finishes with the fixed-point test using hashes to stand for binaries.

Python T-diagrams as code: bootstrap and cross builds

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.

Check the results against the theory:

  1. The cross-compiler is [L -> B] in A (it runs on A). Using it to compile the same source gives [L -> B] in B, the native compiler. Trying to run it on our machine fails, because we do not own a B. It has to be copied to one.
  2. In the Canadian cross, the result is [L -> C] in B: a compiler that runs on B and targets C, built entirely on A.
  3. The bootstrap path reaches [Lang -> A] in A twice: once from the Core seed, once from the self-hosted source.
  4. In the fixed-point test, stages 2 and 3 are identical, while stage 1 differs because the seed compiler produced different code. When you compare real compiler builds, the same pattern shows up: an unexpected difference between stage 2 and stage 3 is a bug report.

Other uses of the same idea

  • Self-hosting and trust. In 1984 Ken Thompson pointed out that a self-hosting compiler can carry a hidden modification: the binary could insert a back door when it compiles a login program, and also insert itself whenever it compiles a compiler. Reading the source code would show nothing. The defense is to rebuild from an independent compiler ("diverse double-compiling") and compare the outputs, and the practice of reproducible builds, where every build of the same source gives the same bits.
  • Bootstrapping chains for distributions: Linux distributions need a way to get from nothing to a working C compiler, which led to projects that start from a few hundred bytes of machine code and grow all the way to GCC.
  • Interpreters and bytecode. Instead of machine code for the first step, some projects write a tiny interpreter for a bytecode that is portable. Moving the language to a new machine then needs only the interpreter, as in bytecode virtual machines.
  • Compiler-compilers such as Yacc and parser generators are themselves bootstrapped: their grammar files are parsed by an earlier version of the tool.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the T-diagram notation [S -> T] in I, which language is the compiler itself written in?

    S is the language the compiler reads, T is the language it produces, and I is the language the compiler's own program is written in.
  2. 2. Why does bootstrapping start with a compiler for a small subset of the language?

    The seed has to be written in machine code or an existing language, so it is kept as small as possible. The next stage is written in the subset.
  3. 3. You own machine A only. Which compiler do you build first to get a native compiler for machine B?

    You can only run programs on A. The cross-compiler [L -> B] in A produces B programs, including the native compiler for B.
  4. 4. In the three-stage test, which two builds should be identical?

    Stages 2 and 3 are built by compilers that behave identically, because both are builds of the same source. A difference points to a bug or a non-deterministic build.
  5. 5. What does a Canadian cross involve?

    It is the three-machine case of cross compilation: build, host and target are all different.

Summary

  • Every compiler has a source language, a target language and an implementation language, drawn as a T-diagram [S -> T] in I.
  • A compiler can compile another one only if the implementation language of the second is the source language of the first, and the first can actually run on a machine you have.
  • Bootstrapping starts from a tiny hand-written compiler for a subset, builds a compiler for the full language in that subset, and then rewrites the compiler in its own language (self-hosting).
  • Three-stage builds test self-hosting: stage 2 and stage 3 must be identical.
  • A cross-compiler runs on one machine and targets another. Compile its source with itself to get a native compiler. A Canadian cross builds on one machine a compiler that runs on a second and targets a third.
  • A self-hosted compiler can hide a back door, which is why reproducible builds and independent rebuilds matter.

Next, look at the whole pipeline in The Phases of a Compiler.