Turning Text Into Instructions
Every Transformation Obeys One Rule, and the Rule Is Narrower Than You Think
Last timeThe Form in the Middle
The standard optimisations are each simple enough to do by hand. What matters is the single property all of them preserve, and how little that property actually promises.
The rule they all obey
An optimisation changes the program. The question is what it is not allowed to
change, and the answer is narrower than most people assume.
What must be preserved is the observable behaviour: the output the program
produces, and the effects it has on the world outside itself, in the order
those effects are visible. That is the entire obligation.
Things that are not protected: how long the program takes, how much memory it
uses, the order in which invisible work happens, whether a computation happens
at all, how many times a loop body actually runs, and the contents of memory
locations nobody reads. All of these may be changed freely.
This is why an optimiser can delete a loop that computes a sum nobody uses, and
why it can run two independent calculations in either order. It is also the
source of every surprise in the next lesson, because a program that breaks a
rule of the language has no defined observable behaviour, and preserving
nothing is easy.
before:
t1 = 4 * 8
t2 = x + y
t3 = x + y
t4 = t1 + t2
t5 = t3 * 2
t6 = t5 + 1
result = t4
after:
t2 = x + y
result = 32 + t2
removed: a constant computed at run time,
a repeated addition, and three operations
whose results nothing readsThe standard moves
Five moves cover most of the gain.
Folding constants evaluates at compile time anything whose inputs are all
known. The obvious cases are rare in handwritten code and common in code
produced by inlining and by macro expansion, which is most code by the time
the optimiser sees it.
Removing repeated work finds two computations with identical inputs and keeps
one. The reason this matters is the same: array indexing, field access and
bounds checks generate the same address arithmetic many times over, none of
which a person wrote.
Deleting unused results walks backwards from the things that are observable and
removes everything nothing depends on. This is the pass that cleans up after
all the others, which is why it runs last and also several times before that.
Replacing expensive operations with cheap ones swaps a multiplication for a
shift, a division by a constant for a multiplication, or a repeated
multiplication in a loop for a repeated addition. The savings per instance are
small and the instances are everywhere.
Lifting work out of loops moves a computation whose inputs do not change inside
the loop to just before it. The gain is proportional to the trip count, which
makes this the one on the list with unbounded upside.
| the definitions of its i | that nothing wrote to me | that the loop runs at le | |
|---|---|---|---|
| fold a constant | 1 | 0 | 0 |
| remove a repeated comput | 1 | 1 | 0 |
| delete an unused result | 1 | 1 | 0 |
| replace an expensive ope | 1 | 0 | 0 |
| lift work out of a loop | 1 | 1 | 1 |
They feed each other
No pass is run once. Each one creates opportunities for the others, and the
cascade is where the real gain comes from.
The lesson stops here
1 more paragraph to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents