Closing the circle

The last chapter ended with a measurement: our Lisp is about a hundred times slower than Python, because on every call it works its way through the same tree all over again. There is another way: work the tree out once and translate the program into a language the machine understands. To see whether translating pays off, we take a small program with two nested loops and run it two ways. An interpreter walks its tree, like evaluate from Chapter 51. A translator turns the same tree into C once, and the sandbox’s C compiler, tcc, turns that into machine code.

The answer is the same, 56, and the speeds differ several hundredfold. The inner loop runs fifty thousand times, and fifty thousand times the interpreter finds out that it is looking at an assignment, that the right side is an exclusive OR, and where s is kept. The C program finds out nothing: all of that was settled during translation, and the processor is left with instructions to execute. The function to_c is about fifteen lines long, and it is already a compiler, though one that hands the hardest part over to tcc.

We will do the hard part ourselves and translate straight into the machine code of Iskra-8, the computer you built in Part IV of the course: the gates in Chapter 29, the adder and the ALU in Chapter 30, the memory in Chapter 31, the processor and the assembler in Chapter 32. We have had a lexer and a parser since Chapter 50, and a stack machine since Chapter 15 and Chapter 33. One link is missing: a program that translates text in a language people can read into bytes that Iskra can run. Once it exists, the circle closes, and a program you wrote will run along wires you put together.

1952. The compiler nobody would touch

A modern compiler does things A-0 never dreamed of, but the idea is the same: a program that writes a program. Before we write one for Iskra, we have to decide which language it will translate from.

The Ognivo language

Ognivo is Russian for a fire steel, the piece of steel you strike against flint to make a spark, and the Russian for “spark” is iskra. Our language will be a small subset of Python, so there is nothing new to learn, and Python itself can read any program written in it. Ognivo has:

• numbers from 0 to 255, as much as fits in an Iskra register, with all arithmetic done modulo 256, as in Chapter 33;
• variables with plain ASCII names and assignment, x = expression;
• the operators + - * & | ^ and parentheses;
• while loops and if … else branches, whose condition is a single comparison: < > <= >= == !=;
• plot(x, y) to light a pixel on the 8 × 8 screen, print(e) to print a number, read() to read a number from the input.

Here is the program we will be translating all through the chapter:

It sweeps the screen row by row and lights a pixel whenever the column number and the row number have no 1 bits in common. The result is a Sierpinski triangle; in Chapter 9 we drew one with recursion. Here it comes out of a single bitwise AND: the odd numbers of Pascal’s triangle fall on the cells where x & y == 0, and on no others. The condition has no parentheses because in Python & binds more tightly than ==, so x & y == 0 means (x & y) == 0. In C it’s the other way around, and the line would need parentheses there, one of the language’s famous traps.

The pipeline

A compiler works as a pipeline: each stage takes what the previous one produced, reworks it and hands it on. The first two stages you know from Chapter 50. The lexer cuts the text into words. The parser builds a tree out of the words. Ognivo is a subset of Python, so we can borrow these two stages ready-made from Python itself: its standard library has both a lexer, the tokenize module, and a parser, the ast module.

Python’s lexer turns the indentation a person sees into the words INDENT and DEDENT, an opening and a closing bracket that appear nowhere in the text. The next stages are new to you. Checking the meaning catches errors that the grammar lets through: a name that is never given a value, the number 300 that won’t fit in a byte, a call to a function nobody knows. Intermediate code rewrites the tree as simple instructions for an imaginary machine, convenient both for optimizing and for translating. The optimizer rewrites those instructions into shorter and faster ones. The code generator turns them into processor instructions, and the assembler from Chapter 32 turns those into bytes. Walk through the pipeline yourself: edit the program and watch what each stage makes of it.

The whole compiler

Here is the Ognivo compiler in full, in Python. Read it from top to bottom: each function is one stage of the pipeline. Below the line comes the test: we compile the Sierpinski triangle, assemble it with the assembler from Chapter 32 and run it on the Iskra emulator in the sandbox.

A triangle on Iskra’s screen, and not one line of assembly written by hand. Now the stages, one at a time.

The front end: only what Ognivo has

The function front has Python parse the text, then walks Python’s tree and rewrites it into a small tree of our own, made of tuples like ("=", "x", ("+", "x", 1)), the same shape as the formula trees of Chapter 50. On the way it turns down everything Ognivo doesn’t have. Python understands x = [1, 2] or def f():, but front answers them with a CompileError and a line number. Compilers are often built this way: the front end understands the language, the back end knows the machine, and an intermediate representation sits between them. That way one language can have many targets and one machine many languages. The Clang compiler’s front end understands C and C++, and its back end, LLVM, is shared with Rust, Swift and other languages.

Meaning: is every name accounted for?

The parser checks only the form. The program x = y + 1 is grammatically flawless, but y is never given a value, and running it makes no sense. The function check collects the names that are assigned to and the names that are read, and compares the two sets. It also draws up the list of variables, each of which will need a byte of memory. In big compilers this stage is called semantic analysis, and its main business is checking types. Ognivo has a single type, the byte, so there is nothing to check. Python has many types, and they are the subject of the next chapter.

Intermediate code: a stack machine

You can translate a tree straight into assembly, but it is awkward: a tree is a nested structure, while a program for a processor is a flat list of instructions with jumps. So nearly every compiler first translates the tree into an intermediate representation, simple instructions for an imaginary machine. Our imaginary machine is a stack machine, like CPython’s virtual machine in Chapter 33. The expression x + 1 becomes LOAD x, PUSH 1, +: first the operands, then the operation. This is the reverse Polish notation of Chapter 15, and it comes from a post-order walk of the tree: the left subtree, then the right subtree, then the root.

Loops and branches turn into labels and jumps. A while is a label at the top, a test of the condition with a jump past the end of the loop, the body, and a jump back to the label:

This is how you built loops out of jumps by hand in Chapter 32. Now gen_ir does it, and to keep the labels of nested loops from getting mixed up, it numbers them with a counter: L1, L2, L3…

Code generation: a few Iskra instructions for each one

The last stage, code generation, translates each stack-machine instruction into Iskra instructions. Iskra has a stack of its own, in hardware: PUSH, POP and the stack pointer SP from Chapter 32. So the translation is almost word for word. PUSH 1 means: put the number in R0 and push R0. + means: pop the right operand into R1 and the left one into R0, add them, push the result back. A variable is a byte of memory labeled v_x after the end of the program.

Comparisons are more interesting. CMP R0, R1 subtracts without keeping the difference and sets the flags: Z if the numbers are equal, C if it had to borrow, which means R0 < R1. Iskra has four jumps: always, if Z, if not Z, and if C. There is no “if not C,” so while y < 8, which has to jump past the loop when y < 8 is false, makes do with two jumps: if there was a carry, jump over the exit; otherwise, take the exit. The comparison is unsigned: 200 is greater than 100, even though in two’s complement 200 is a negative number. Our compiler never looks at the sign flag N.

Iskra can’t multiply or draw at all. Subroutines do that, and the compiler appends them to the end of the program when they are needed: __mul multiplies by shifts and adds, as in the task “Multiply fast” from Chapter 32, and __plot works out the address of the screen row and shifts a single 1 into the right column. A set of subroutines like this, which the compiler adds to every program, is called a runtime library. For C it is libc; for Python it is CPython itself, whose functions every BINARY_OP calls.

Iskra runs it

The cell showed only the result. Below, you can step through the machine code one cycle at a time. This is the Iskra-8 of Chapter 32: the screen, the registers, the flags and all of its memory, 256 bytes. It runs whatever the pipeline above compiled last, and next to the current instruction you can see the line of Ognivo it grew from.

Run Sierpinski at slow speed and watch the stack. It grows to two bytes and empties again, over and over: every expression pushes its operands and pops them right away. While you’re at it, count how much work goes into the single line x = x + 1: LD, PUSH, LDI, PUSH, POP, POP, ADD, PUSH, POP, ST, ten instructions and thirteen bytes. A person would write LD R0, [v_x], INC R0, ST R0, [v_x]: three instructions, five bytes. The compiler translates correctly, but word for word.

The optimizer

Iskra has 256 bytes of memory, and our Sierpinski takes up almost half of them. Time to trim. A compiler’s improvements to code are called optimizations, although they don’t promise optimal code: each one notices some common kind of waste and fixes it, changing nothing in what the program means.

Constant folding and dead code

We start with the intermediate code. If two numbers are pushed onto the stack and an operation follows, the result can be computed right away, at compile time: PUSH 2, PUSH 4, * become a single PUSH 8. This is constant folding. The same goes for a condition: if both operands of a comparison are known, so is the outcome. A condition that is always false turns an if into an unconditional jump, and whatever stands after an unconditional jump, up to the next label, will never run. That is dead code, and it can be thrown away. Here is an optimizer for intermediate code, on a program that has both.

Twenty-seven instructions became eighteen. 2 * 4 folded into 8, and 8 - 1 - y into 7 - y: the expression is read from left to right, as (8 - 1) - y, so the left-hand part can be computed in advance. The debugging print under if 1 == 0 vanished together with its condition. Production compilers do the same: they cut a line like if DEBUG: with a false constant out of the program, and debugging code costs the finished program not one cycle. This optimizer can’t fold x + 2 + 3, though. That expression starts with x + 2, so two numbers never end up next to each other on the stack. The compiler would have to regroup the additions, which is legal for addition modulo 256, but not for every operation.

Peephole optimization

The second optimization looks at the finished assembly, through a narrow window two or three instructions wide, and swaps wasteful pairs for thrifty ones. Our code is full of PUSH R0 followed at once by POP R0: push a value and pop it straight back. The pair does nothing and can go. PUSH R0 and POP R1 become a single MOV R1, R0. JMP L2 right before the label L2: is a jump to the next line. This is called peephole optimization. It knows nothing about the program as a whole, but it is cheap and more useful than it looks, because the code generator translates each instruction on its own and leaves the same marks at every seam.

Registers instead of the stack

The biggest waste is out of the peephole’s reach: all our intermediate values travel through memory. A stack in memory means PUSH and POP, a cycle and a byte for each. Yet Iskra has four registers, and three of them sit idle most of the time. The code generator can keep the top of the stack in registers, the left operand in R0 and the right one in R1, and put a value on the stack only when the right side of an expression is complicated itself and needs both registers. It can also choose better instructions: x + 1 is an INC, not an LDI and an ADD.

In grown-up compilers this is a big problem of its own, register allocation. There are many variables and intermediate values and few registers: x86-64 has sixteen general-purpose registers, Iskra has four. Two values that are needed at the same time can’t live in the same register. Draw a graph whose vertices are the values, with an edge between two of them if they are needed at the same time. Handing out registers then means coloring the vertices so that neighbors get different colors, with no more colors than there are registers. When the colors run out, some value is sent to memory. Coloring a graph is hard in general, like the problems of Chapter 58, so compilers solve it approximately, with greedy methods.

For Sierpinski, the optimizations shrink the code from 119 bytes to 79 and the work from 3,210 cycles to 1,744, almost by half. Constant folding has nothing to do here, since the program has no expressions made of numbers alone, but on the “constants” program it throws out two-fifths of the code all by itself. And none of the optimizations changed the meaning: the screen shows the same triangle. That is an optimizer’s first rule. But the source can’t tell you whether the compiler keeps it: the compiler decides what the program does, and the section after next shows why that is dangerous.

A compiler compiles itself

Our compiler is written in Python. It can’t compile itself: Ognivo has no strings, no lists and no functions, and a compiler needs all of them. With big languages, though, it happens all the time. The sandbox’s tcc compiler is written in C, the Go compiler has been written in Go since 2015, and the Rust compiler is written in Rust. A compiler written in the language it translates is called self-hosting. It is a relative of the metacircular interpreter from the last chapter, and it poses a chicken-and-egg riddle at once: what do you compile the first version with?

The way out is called bootstrapping, after the old joke about pulling yourself up by your own bootstraps. The first version is written in another language or run in an interpreter. With Pascal, for instance, it went like this. A first attempt to write its compiler in Fortran, in 1969, was abandoned, because Fortran was poor at describing complex data structures. The second version, as Wirth recalled, was written straight away in Pascal, which had no compiler yet. One of its authors, R. Schild, was then “banished to his home for two weeks” to translate it by hand into a low-level language of the CDC machine. The translated program compiled the Pascal text, and from then on the compiler built itself. At MIT, in 1962, Tim Hart and Mike Levin wrote a Lisp compiler in Lisp and ran it in the interpreter that had grown out of Russell’s eval. The interpreter executed the compiler, the compiler translated itself into machine code, and after that the interpreter was no longer needed. Their memo called it “the first compiler that has ever compiled itself by being executed interpretively.” By their estimate, a compiled function ran about forty times as fast as the same function in the interpreter. So the question the last chapter ended with found its answer three or four years after the first interpreter.

GCC is built in three stages to this day. First, some compiler that is already installed compiles its sources, and that gives the first stage. The first stage compiles the same sources, giving the second. The second compiles them once more, giving the third. The first and second stages are the same compiler, only built by different compilers, so from the same sources they must produce the same thing: the second and third stages have to match byte for byte. If they don’t, the compiler has a bug, which the build instructions call “a potentially serious bug which you should investigate and report.” It’s a good check, but all it shows is that the compiler agrees with itself. Is it honest?

Trusting trust

The same attack can be staged on our compiler. The program below is a lock: it reads a code and opens if the code is right. A compiler with a Trojan horse recognizes the comparison with the code and slips in a second code of its own. The sources of the compiler and of the lock are shown on the cards: watch at which step the Trojan is in them and at which step it is already gone.

Attacks of this kind have also been found in the wild. In 2009 the antivirus lab at Sophos found the Induc virus, which infected not programs but the Delphi development environment: it replaced part of Delphi’s standard library, and every program built with an infected Delphi carried the virus on, though its own sources were clean. In 2015 a counterfeit copy of Apple’s Xcode development environment, XcodeGhost, spread in China and planted malicious code in iPhone apps that made it into the App Store. At first a few dozen such apps were found; then the security firm FireEye counted more than four thousand. Neither case was an exact copy of Thompson’s, since the infected compiler did not reproduce itself from clean sources. But both showed that a tampered build tool infects everything built with it.

Since checking the sources isn’t enough, the defense has to work differently. In 2005 the American security researcher David A. Wheeler (a namesake of the David Wheeler of the “Wheeler jump” in Chapter 5), building on an idea of Henry Spencer’s, described a defense called diverse double-compiling and tested it in practice. The sources of the suspect compiler are built with an independent compiler, and the program that comes out builds the same sources again. If the suspect compiler was indeed built from these sources, the result has to match it byte for byte: both builds do the same thing, only by different hands. A Trojan horse that is in one compiler and can’t be in the other spoils the match. Another answer is reproducible builds: if anyone who builds a program from its published sources gets the same bytes as the developers, it becomes much harder to swap those bytes unnoticed. Chapter 61 has more on backdoors and how they are hunted down.

And here the circle closes once more. In Chapter 7 we asked whether a program can print itself, and the answer was yes, if it keeps a template of its own text and fills the template in with its own quoted copy. Thompson showed the dark side of that exercise: a program that can reproduce itself can reproduce itself together with anything at all.

Translating on the fly

An interpreter makes sense of a program afresh every time; a compiler does it once, in advance. There is a third way, which came up in Chapter 33: JIT compilation, translating while the program runs. The runtime starts out as an interpreter, counts which pieces of the program run most often, and translates only those into machine code, tailoring it to what it has seen. If x has always been an integer in this loop, it can emit a machine instruction for integer addition and check the type once, on the way into the loop. That is how JavaScript works in the browser, and Java, and PyPy. Python 3.13 gained an experimental JIT, switched off by default, built on a technique called “copy-and-patch”: ready-made templates of machine code, one for each bytecode instruction, are glued together, and addresses and numbers are patched into the holes. It is a little like our code generator, which also glues ready-made pieces of assembly together, only it happens while the program runs, and straight into memory.

How a program understands a program

Three chapters ago, in the museum of languages, we stood in front of the line 2 + 3 * (4 - 1) and asked how a machine makes sense of it. Now we have every part of the answer.

Tasks

Three tasks, three pieces of a compiler of your own: an optimizer that works on the tree, and code generators for expressions and for whole programs. The trees are the same ones front builds: a number, a name as a string, or a tuple (operator, left, right). The tests assemble your output with Iskra’s assembler and run it on the emulator, as the cell “ognivo.py” does.

What next

The circle is closed: a program in Ognivo has reached the machine you built out of gates. Everything that lies between your line of code and the wires can now be read, and so it can also be changed.

But remember what check does: it makes sure every name has a value, and nothing more. That is enough for Ognivo, because its values are all of one kind, the byte. Python has many kinds: numbers, strings, lists, dictionaries, and not every operation on them makes sense. Python’s compiler doesn’t worry about that.

A string can’t be multiplied by a dictionary, yet Python’s compiler translated the line into bytecode without a single question: LOAD_CONST, BUILD_MAP, BINARY_OP *. The error surfaced only at run time. Had this line sat in a branch of the program that rarely runs, it would have surfaced in front of a user a month later, in the middle of the night. We have learned to translate a program before it runs. Can we also check it before it runs, and discover that somebody means to multiply a string by a dictionary without executing a single instruction? That is the subject of the next chapter, where the most dangerous value in programming will stand trial.