Compilers and Optimization

An interpreter pays its tax every time an instruction runs. A compiler pays once, before the program starts. It translates the whole program into the processor's own instructions, the ones Chapter 3 follows through the instruction cycle, and spends that time making the result smaller and faster. The price moves from run time to build time.

That move has a limit built into it. The compiler works before the program has seen a single input, so everything it decides about which branches are hot, which calls to inline and which values are common is a guess from the code alone. Following a program through the compiler's stages leads, at the end, to what the compiler cannot know.

Front End, Middle, Back End

The front end of a compiler is the previous three topics for one language: lex, parse, resolve names and check types. The back end produces machine code for one processor family, such as x86-64 or ARM64. Between them sits an intermediate representation, a form of the program that belongs to neither the language nor the processor.

That middle form is what makes compilers affordable. With it, M languages and N processors need M front ends and N back ends, not M times N separate compilers. LLVM is this idea shipped: Clang for C and C++, Rust's compiler and Swift's all translate their programs into LLVM's intermediate form, and share its optimizer and its back ends.

In the figure, three languages feed one intermediate representation, and two back ends produce machine code from it. Adding a new language means writing one front end, and it runs on every processor LLVM supports on its first day. Adding a processor means writing one back end, and every language gets it.

The Intermediate Representation

An intermediate representation is lower than a syntax tree and higher than machine code. It is a list of simple operations, such as add, compare, load and branch, on an unlimited supply of named temporary values. Most compilers arrange it so that each temporary is assigned exactly once, a form called static single assignment.

Single assignment gives the question "where did this value come from?" exactly one answer, which is the question every optimization asks. Every optimization reads and rewrites this form, never the source. The source's variable names, loops and functions are still recognizable in it, but only as patterns of simple operations.

Optimization Passes

Each optimization pass rewrites the program without changing what it does. Constant folding computes 60 * 60 * 24 into 86400 at compile time, so the multiplication never runs. Inlining copies a small function's body into its caller, removing the call frame of Chapter 3 and exposing the body to the other passes. Dead code elimination deletes code that can never run, or whose result nobody reads. Hoisting moves work that gives the same answer on every iteration out of a loop.

The passes run in sequence, and each makes the next one more effective. In the figure, the function to_seconds multiplies days by the result of a call to per_day and logs the result when a debug flag is set. Inlining replaces the call with 60 times 60 times 24. Folding turns that into 86400, and propagating the constant False turns the debug test into "if False". Dead code elimination then removes the test and the log call, leaving one line that returns days times 86400.

CPython's own compiler does a little of this. On Python 3.15, dis shows that SECONDS_PER_DAY = 60 * 60 * 24 compiles to a single load of the constant 86400, and the body of a block guarded by if False: is removed, leaving only a do-nothing placeholder instruction. What CPython's compiler cannot do is inline a call or specialize for types: a function's name can be rebound while the program runs, and the types of values are not known until then.

The As-If Rule

A compiler may do anything whose observable result is the same as the program as written: reorder operations, merge them, delete them. This freedom is called the as-if rule, and it has consequences an engineer meets every week. A debugger stepping through an optimized build jumps between lines and reports variables as "optimized out". A benchmark loop whose result is never used can disappear entirely, and report an impressive time for doing nothing.

It also explains why memory operations can be reordered in ways other threads can see, which the atomics and memory models topic in Chapter 11 covers. In C and C++, undefined behaviour widens the rule further: the compiler may assume it never happens, and delete a check the programmer believed was there, as the integer overflow topic in Chapter 2 describes.

Instruction Selection and Register Allocation

The back end picks machine instructions for each operation, then fits the unlimited temporaries into a handful of registers: 16 general-purpose registers on x86-64, 31 on ARM64. Values that do not fit spill to memory, and every spill is a load or store that a better allocation would have avoided.

Deciding which values stay in registers is a graph-colouring problem, first formulated that way for compilers in the early 1980s, and graph colouring has no known fast exact method, the class of problem Chapter 14 describes. Every compiler uses a heuristic. Truly optimal code is out of reach even in principle, because a perfect optimizer would have to decide what any program does, which Chapter 14 shows is impossible.

What Ahead-of-Time Compilation Costs

Ahead-of-time compilation pays at build time: minutes of processor time for a release build of a large C++ or Rust program, repaid on every run. The output targets one processor family and one operating system, so a release is one build per target. And the compiler optimizes for inputs it has never seen, guessing from the code alone which branches are hot and which calls deserve inlining.

Profile-guided optimization replaces the guess with measurement: run a build on a real workload, record what happened and feed the record back into the next build. CPython itself is built this way when configured with its optimizations flag. The next topic is the other answer: compile while the program runs, when the inputs are known.