# Error propagation when compiling a compiler

Just for curiosity, I recently heard that many compilers are written in its own language. For example, gcc is partially written in C. And old version of compiler is used to compile the new version of compiler.

Then I have a question, if there is a bug in the compiler, and you fix the bug in the source code and use the previous buggy compiler to compile a new compiler, how can you ensure that the bug in the new compiler is fixed?

Theoretically, if you have a very buggy old compiler, and now you have a new, bug-free version of the compiler source code, would the compiler converges to a bug-free compiler if you keep repeating compilation of the compiler starting from the old compiler?

There is no reason why compiling a compiler's source code with a broken compiler would result in a working compiler. The bug in the existing binary could well lead to a binary that is completely broken, or subtly broken, or has the very same bug.

For example, there once was a version of CAML (an ancestor language of Ocaml) where one version of the compiler omitted the code for a case in a match-case construct under certain circumstances. So the developers fixed the bug — a case was missing in a match-case construct in the source code. But the compiler was bootstrapped (the CAML compiler was written in CAML), and compiling the corrected source generated a binary that was still buggy, because the compiler bug caused the new case to not have generated code. The developers had to rewrite the code in a different way, then recompile to get a correct compiler, and after that they could change the source code back to using the desired match-case construct.

There is a rather famous example where such a self-reproducing bug was introduced deliberately: the “Thompson hack”. Ken Thompson was one of the main authors of the Unix operating system and the first C compiler. He introduced a backdoor in the operating system by modifying the source code of the login program to allow him to log in on any Unix system. Then he reverted this change and instead modified the C compiler to insert this backdoor whenever it was compiling login.c. Then he modified the C compiler again to add code to insert the backdoor in login whenever the compiler was compiling itself. He recompiled the compiler and removed all traces of his backdoor. So he had a self-perpetuating bug which happened to be a backdoor. I strongly recommend “Reflections on Trusting Trust”, his Turing award lecture, where he revealed and explained this backdoor.

In practice, there are a few ways to reduce the risk of self-perpetuating compiler bugs. Compiler writers usually try to use a well-known, stable subset of the language, and avoid newer features where the compiler is more likely to have bugs. Some compilers have a bootstrap compiler which depends on a subset $$A$$ of the language and is capable of compiling a subset $$B \supset A$$; the full compiler is written in $$B$$ and is capable of compiling the whole language. If multiple compilers exist for the language the compiler is written in, this makes it unlikely that they'll all be too buggy to compile the compiler.

There are research efforts to reduce the trusted base of compilers, i.e. the amount of software that must be assumed to be correct in order to guarantee that the compiler binaries will work correctly. In particular, certified compilers come with a proof that the compiler binary has the semantics specified by its source code. A correctness statement goes like this: “assuming that the proof checker for the compiler is correct, and assuming that the runtime environment in which the compiler runs conforms to its model, then the compiler always produces binaries that have the semantics specified by their source code”. The trusted base consists in the runtime environment and the proof checker, which is typically orders of magnitude smaller than a compiler.

Let's say you had a working compiler with source code X and compiled with a working compiler as CX. Then you add a "bug" where every integer literal i is compiled as if it was i+1. So int a[10]; for (int i = 0; i < 10; ++i) a[i] = i; will actually produce an array with 11 elements, and initialised elements 1 to 10 but not 0.

This is your new compiler with source Y, and you compile it with CX to produce CY which has the same bug. If you compile Y with CY to produce CCY, you now have a compiler that does not just have a bug in its code generation, but that is completely broken. There is not a chance in hell that you will get anything useful if you try to compile X, Y, or Y or any other code with CCY.

So if you write a compiler that is supposed to compile itself, make sure it also compiles with some other compiler, and keep quite a few working compiled compilers around.

On the other hand, you will have compiler bugs that are really obscure and only affect source code that is weird in the first place. For example, I remember a compiler having problems with a loop for (unsigned char c = 100; c != 50; ++c) { ... } (not realising that this loop will wrap around from c = 255 to c = 0). I would bet that no compiler in the world is affected by this bug, so fixing the bug in the source code and recompiling the fixed source code with the broken compiler will produce most most likeky a compiler with the bug fixed.