The gcc that gave birth to Linux ── what made that gcc?
gcc. But gcc itself is also a program written in C. Where there's no compiler yet, what made the first gcc? The answer: "lift it once with an existing cc, then it builds itself from there" ── the three-stage bootstrap.
The parent that gave birth to Linux was gcc. So who gave birth to the parent gcc? gcc is just a program written in the C language. Which means that to turn gcc into something runnable, you need a C compiler. ── The loop again. gcc is made by gcc, and that gcc too by gcc… This time, we look at how to ignite this loop correctly and spin it correctly. As it happens, building gcc involves a strange ritual of "building it three times," and the third time is a device that self-checks the compiler's correctness.
First, let's confirm the starting point. gcc is written as C-language source code (modern gcc is C++; this is the honest line, discussed later). So to turn gcc into an executable, you need another C compiler to compile it. You need a compiler to make a compiler ── Episode 0's loop is buried inside the tool itself.
In 1987, when Richard Stallman released the first gcc (GNU C Compiler; 1.0 was May 23, 1987), it was built by the C compiler that already existed on that machine ── Unix's native cc. He borrowed a "someone else's compiler" from outside the loop, just once, as an ignition device. Once gcc ran, from then on gcc could make gcc (self-hosting).
gcc (only the C front end he wrote was reused). ── "The borrowed thing wouldn't run, so in the end he wrote it himself." A fitting anecdote from the front lines of bootstrapping.
gcc's claim is this ── "Lend me just one working C compiler. After that, I'll spin the loop myself." This is not a solution to the chicken and egg, but a deferral. The question gets passed down the staircase to "then, where did that first cc come from?" That cc is Unix's native C compiler = a descendant of Ritchie's first C compiler (Episode 5). The journey of tracing the ignition device outside the loop even further back continues.
Here is this episode's highlight. The standard procedure for building gcc correctly (make bootstrap) builds gcc three times. In the figure below, advance the stages one at a time.
stage 1 ── built by the existing cc
First make one gcc with the "someone-else's compiler." It works, but it's a scaffold with the outsider's quirks (optimization and code generation) mixed in.
stage 2 ── built by stage1
Make gcc once more with that gcc (stage1). This is the first "gcc made by gcc."
stage 3 ── built by stage2
Make gcc again with gcc (stage2). Both stage2 and stage3 are things "built from the same source by gcc."
A correct compiler should produce the same output from the same source, regardless of "what it was built with." So gcc (stage2) and gcc (stage3) ── both "the result of gcc building gcc" ── should match byte for byte. In fact, make compare compares these two. If they match, the compiler can stably reproduce itself = it is working correctly, which is a self-grading. If they differ, suspect a compiler bug or non-determinism in the build.
stage1 was made by the "outsider cc," so its quirks may linger in the optimization and the code. But every time you rebuild with gcc, the result converges to a single point (a fixed point): "gcc made by gcc." stage2 reaches that point, and stage3 confirms that "it no longer changes." So the final product is stage3, and stage1 is a used-up scaffold. In the figure below, see how, no matter what seed (ignition device) you start from, it settles into the same gcc.
The three-stage bootstrap is the right way to spin the loop, but stage1 still needs "an existing C compiler." On a brand-new machine (not a single compiler on it), this can't be done. So what do you do? ── Bake a gcc for that new CPU using a gcc on a different machine. This is cross-compilation, the modern version of Episode 8's "carrying paper tape from another machine" (a deep dive in a bonus episode too).
Either way, the ignition device cc must be obtained from somewhere. Trace its origin and you arrive at Unix's native C compiler, and then the first C compiler Ritchie wrote. It's time to trace the hand outside the loop back one more step.
(1) Modern gcc is written in C++, and building it requires a C++ compiler (since GCC 4.8 in 2012). "Written in C" is the historical story. The chicken-and-egg structure is the same (you need a compiler to make a compiler).
(2) stage3 is technically unnecessary for correctness; the functionally finished product is stage2. The third stage exists to "spread gcc's own optimization into the final binary" and to "compare against stage2 as a check." (3) "stage2 == stage3 match" presupposes a deterministic build (the ideal that, aside from things like timestamps creeping in, they match). Build reproducibility itself is covered in Bonus Episode ②, "Bootstrappable Builds." (4) And the biggest caveat of all ── can that "borrowed cc" even be trusted in the first place? This unsettling question goes to Bonus Episode ①, "Trusting Trust."
The gcc that gave birth to Linux is itself a program written in C, and running it requires a C compiler ── the chicken-and-egg loop is inside the tool too. The first gcc (1987, Stallman) was ignited just once by the machine's existing cc, and after that entered self-hosting. This is not a solution to the chicken and egg but a deferral, and the question gets passed down the staircase to "where did that cc come from?"
The right way to spin the loop is the three-stage bootstrap. Build three times ── existing cc→stage1→stage2→stage3 ── and use make compare to confirm the byte-for-byte match of stage2 and stage3. Since a correct compiler should produce the same output no matter what it was built with, a match is evidence of it having graded itself. No matter what seed you start from, the result converges to the fixed point "gcc made by gcc," so stage1 is a used-up scaffold and stage3 is the real deal. ── Now, on to the ancestor of that ignition device, cc. First, a detour to see ACK, the compiler of that other educational OS, MINIX.
gcc ── a design that inserts an intermediate bytecode called EM to support many languages and many machines. It's a good rehearsal for the great invention of "inserting intermediate code," which connects to BCPL/O-code in Episode 6.
make bootstrap performs a three-stage build in a native configuration, building stage1 with the host (existing) compiler, stage2 with stage1, and stage3 with stage2. make compare compares stage2 and stage3, checking soundness by exploiting the fact that a correct compiler produces identical output (regardless of what it was built with). stage3 is technically unnecessary for correctness; it is the stage for reflecting GCC's own optimization into the final binary and for the comparison check. Modern GCC is written in C++ (since GCC 4.8, 2012) and requires a C++ compiler to build. The existing cc used for ignition is a Unix-derived C compiler, whose lineage traces back to Ritchie's C compiler (Episode 5). ── To print, use your browser's "Print" and "Save as PDF" (in the print version, the figure controls and answers are frozen / hidden).
Printing / making a PDF: ⌘+P (on Windows, Ctrl+P). On screen, use the slider in Figure 1 to advance the three-stage bootstrap, and the buttons in Figure 2 to change the "seed compiler" and see the convergence to a fixed point. "Show answer" opens each solution.