Optimize a Listing by Hand · Principles of Compiler Design

Format pairsTime 50 minBring paper

The point

Optimize a listing by hand, to a fixed point, before trusting a program to do it. You will find at least one transformation you would have got wrong.

Do this

By hand, pass by pass. Optimize this listing, writing out each pass separately and labeling every change with the transformation that made it. Use the names from Dragon §9.1.
```
 1: t0 = 4 * 5
 2: n  = t0
 3: t1 = n + 0
 4: m  = t1
 5: t2 = m * 1
 6: k  = t2
 7: t3 = 7 - 7
 8: ifFalse t3 goto L1
 9: print 999
10: L1:
11: print k
```
Keep going until nothing changes. How many passes? How many instructions remain? Why could a single pass not have got there?
Now the compiler. Put an equivalent program through it, compare out.tac with out.optimized.tac, and read the scorecard.
Find a disagreement and explain it. There is at least one: the compiler will not eliminate a dead store to a user variable, only to a temporary. Which analysis would it need in order to do better, and why is it not safe without it?
Break the safety rule. Remove the 'forget everything at a label' step. Then compile a loop that changes a variable, and run it. Describe the wrong answer and say precisely which assumption failed, in flow-graph terms.

Step 5 is the important one

It produces a compiler that passes every straight-line test you have written and is silently wrong on loops. That failure mode — correct on the tests, wrong in reality — is why optimizer bugs have the reputation they do, and it is worth meeting once deliberately.

Deliverable

Your pass-by-pass hand optimization with every change named; the compiler's scorecard; your analysis of the disagreement; and a description of the step-5 failure. Feeds Lab Questions 19 and 20.