Read this first. Each section after it takes about ten minutes.
An optimization pass reads the code a compiler has generated and writes new code that computes the same results at less cost: fewer instructions run, or cheaper ones. Each pass on this page applies one simple rule to every instruction it visits. The interest is in what the rule notices, and in why applying it is always safe.
Always safe means on every execution (slide 3). The compiler cannot run the program to see what happens: the code it writes must be correct for every input and every path through the program. So a pass changes an instruction only when it can prove the change is correct, and leaves it alone otherwise. Most of what each section explains is where that line falls.
Passes run one after another, and one pass often creates work for the next. Constant propagation, for example, leaves instructions whose results are no longer used, which dead code elimination then deletes.
The examples, the ILOC they use, and the colors.
Most examples are a short block of ILOC with each variable in a register, as an optimizing compiler would
keep it. Each section lists which register holds which variable, and hovering over a Decaf statement marks its
instructions. decaf-ref (and your P4 compiler) keeps every variable in memory instead, loading it at
each use and storing it at each assignment; that adds loads and stores but no new ideas. Peephole optimization is
the exception: it works on decaf-ref's own output, which is what it exists to clean up.
| Instruction | Meaning |
|---|---|
| loadI 4 => r1 | r1 = 4 |
| add r1, r2 => r3 | r3 = r1 + r2 (also sub, mult, div) |
| addI r1, 5 => r2 | r2 = r1 + 5, with the constant in the instruction (also multI) |
| i2i r1 => r2 | r2 = r1, a copy |
| i2i r3 => RET | the function returns the value in r3 |
In each before-and-after listing, old new is a replaced instruction, struck through in red is a deleted one, and plain lines are kept. The reason for each change is beside it. In the step-by-step view, the line the pass is at is gold.
Below each listing, isim runs the whole program twice, once with each block: the results must
match.
Grouped by scope, as on slide 4.