Chapter 05 · Optimisation
Doing less, faster
An optimiser rewrites a program into a cheaper one that behaves exactly the same. Some rewrites are obvious, like computing 2 × 60 at compile time; others need a careful analysis of how values flow through the program. All of them live under one rule: nobody must be able to tell the difference.
When FORTRAN appeared in 1957, programmers were sure that a machine could never write code as good as theirs. John Backus knew that if the first compiler produced slow programs, the whole idea would be dismissed, so his team spent much of its effort on optimisation, and the FORTRAN I compiler surprised its users with code close to what an expert would write. Optimisation has been the reason compilers are trusted ever since.
The word is a little misleading. No compiler finds the optimal program; it applies a catalogue of safe transformations that usually make the program smaller or faster. Wahoo's optimizer (optimizer.rs) works on the checked HIR, before code generation, and you can switch it on and off in the playground.
The as-if rule
An optimiser may change anything about a program except its observable behaviour: what it prints, what it returns, and whether and how it fails. The C standard calls this the as-if rule: the program must behave as if it had been executed exactly as written.
What counts as observable is a decision of the language. In Wahoo, output and run-time failures do. So 10 / 0 is not folded at compile time, even though the compiler can see both numbers: the program must still fall into the pit when, and only when, it reaches that line. And loud() * 0 is not simplified to 0, because loud() might print something. Only pure expressions, with no calls and no possible traps, can be thrown away.
What Wahoo's optimizer does
Constant folding. Any operation whose operands are known at compile time is computed then: 2 * 60 + 30 becomes 150, 3 < 5 becomes star. The folding must use exactly the arithmetic of the target machine: Wahoo's coins are 32-bit integers that wrap around, so 2147483647 + 1 folds to -2147483648, the same value the program would compute at run time.
Algebraic simplification. Identities that hold for every value: x + 0, x - 0, x * 1 and x / 1 are x; not not s is s; star and s is s; goomba and s is goomba (and s would not have run anyway, because and short-circuits).
Branch elimination. A question whose condition folded to a constant is replaced by the branch that will run; a bounce goomba loop disappears; a run loop whose bounds are constants and empty (from 5 to 1) disappears too.
Dead code elimination. Statements after a flag can never run and are dropped (the checker has already warned about them).
question with a constant condition, or code after a flag, and watch it vanish from the right-hand side.What it doesn't do (yet)
Wahoo's optimizer is deliberately small. Production compilers apply dozens of passes, many of them over and over. A few of the classics, each with the opportunity it exploits:
| Transformation | Before | After |
|---|---|---|
| Constant propagation | coin t = 150 … wahoo(t * 2) | wahoo(300) if t never changes |
| Common subexpressions | (a + b) * (a + b) | compute a + b once |
| Loop-invariant code motion | bounce i < n { wahoo(i * (w * h)) … } | compute w * h once, before the loop |
| Strength reduction | i * 8 in a loop | a shift, or adding 8 each iteration |
| Inlining | a call to a short pipe | the pipe's body, in place, opening the door to every other optimisation |
| Peephole | i32.gt_s followed by i32.eqz | i32.le_s (Wahoo emits that pair in every bounce!) |
| Tail-call elimination | a pipe whose last act is to call itself | a jump back to the start: recursion without a growing stack |
| Vectorisation | a loop adding two arrays element by element | one instruction adding four or eight elements at a time |
Each of these is a nice exercise: the code generator's loop pattern, for instance, is crying out for the peephole rule in the table.
Data-flow analysis
Folding 2 * 60 only needs to look at one node of the tree. Propagating constants through variables, finding expressions computed twice or variables that are dead needs to know how values flow through the whole function, across branches and loops. The foundations were laid at IBM by Frances Allen and John Cocke. Allen's 1970 paper Control Flow Analysis cut functions into basic blocks (straight-line runs of code with one way in and one way out) joined by edges into a control-flow graph, and in 1971 Allen and Cocke published A Catalogue of Optimizing Transformations, the list most compilers still follow. In 2006 Allen became the first woman to receive the Turing Award, for this work.
In 1973 Gary Kildall (later the author of the CP/M operating system) unified the analyses into one framework: each one is a set of facts that propagates along the graph, combined where paths meet, and iterated until nothing changes. The lattice theory behind it guarantees that the iteration stops. In the late 1980s Mark Wegman, Kenneth Zadeck and their colleagues at IBM introduced SSA form (chapter 04), which makes many of these analyses faster and simpler, and which nearly every optimising compiler now uses.
The dark side: undefined behaviour
The as-if rule only protects programs whose behaviour is defined. C and C++ leave many things undefined: signed integer overflow, reading outside an array, dereferencing a null pointer. The compiler may assume they never happen, and optimise accordingly. A programmer who writes an overflow check like
if (x + 1 < x) { /* overflow! */ }may find it deleted, because for a signed int the condition can only be true after an overflow, which “cannot happen”. Such surprises have caused real security holes. Wahoo, like Rust in release mode, Java and WebAssembly itself, defines overflow as wrap-around, so there is nothing for the optimiser to exploit and nothing to surprise anyone.
No perfect optimiser
Could a sufficiently clever compiler always find the smallest equivalent program? No. If it could, then given any program that never prints and never stops, it would turn it into the smallest program that never prints and never stops, an empty infinite loop, and comparing outputs would decide the halting problem. Andrew Appel calls this the full employment theorem for compiler writers: there is always a better optimiser to write. In practice the limits are economic rather than mathematical: every pass costs compilation time, which is why compilers offer levels (-O0 to -O3), why JITs only optimise hot code (chapter 00), and why Wahoo lets you turn it off and compare.
References
- J. W. Backus (1978). “The History of FORTRAN I, II, and III”. ACM SIGPLAN Notices, 13(8).
- F. E. Allen (1970). “Control Flow Analysis”. ACM SIGPLAN Notices, 5(7).
- F. E. Allen and J. Cocke (1971). “A Catalogue of Optimizing Transformations”. In Design and Optimization of Compilers, Prentice-Hall.
- G. A. Kildall (1973). “A Unified Approach to Global Program Optimization”. Proceedings of the 1st ACM Symposium on Principles of Programming Languages.
- B. K. Rosen, M. N. Wegman and F. K. Zadeck (1988). “Global Value Numbers and Redundant Computations”. Proceedings of POPL.
- A. W. Appel (1998). Modern Compiler Implementation in ML. Cambridge University Press.
- C. Lattner (2011). “What Every C Programmer Should Know About Undefined Behavior”. LLVM Project Blog.