3.6 Iteration 5: Optimizations

3.6.1 Milestone Summary

The goals of this milestone is to implement multiple optimization passes along the pipeline of the compiler.

For this milestone you will reuse the passes of milestone 5 unmodified and only add new optimization passes.

For this milestone you do not have access to the reference solution. You should take extra care to understand when and how optimizations can be performed and test accordingly.

3.6.1.1 Checklist

Completely new passes

• propagate-copies

• bury-dead

• trace-schedule

• inline-jumps

3.6.2 Reading

You should revisit the course slides on copy propagation and the book chapter on Register Allocation for undead analysis.

3.6.3 Assignment

• Implement a function propagate-copies that performs copy propagation. The source and target language of this pass is Proc-imp-cmf-lang v5.

  Perform a single traversal over the body of a procedure that implements the analysis and transformation. Just like the undead-analysis of our register allocator this deals with procedures separately instead of combining the results of multiple procedures. Therefore, it is closer to local copy propagation than global copy propagation, even though this intermediate language still has structured control flow.

  Try to eliminate as many copy statements as possible and if necessary change the definition of the transfer functions.

• Our register allocation performs undead analysis as a dependency for conflict analysis. We could use the undead information to design an optimization to remove dead variables. An assignment to a variable is dead if it is not in the undead-out set for the instruction. However, to separate concerns, we should not do this during register allocation. Instead, we design an optimization pass that happens before register allocation.

  Design and implement the function bury-dead, which removes assignments to unused abstract locations. The source and target language of this pass is Proc-imp-cmf-lang v5.

  Since the undead analysis of the register allocator works with another language, you will have to separately implement undead analysis for Proc-imp-cmf-lang v5. Perform a single traversal over the body of a procedure that implements the analysis and transformation. That means you do not have to calculate and store the undead-out tree.

  As detailed above, you need the support package from https://github.com/soft-compilers/cpsc411-pub. Unfortunately, the generic interpreters have trouble with empty begins. The skeleton code provides clean-proc-imp-cmf-lang which you can use as the last step inside your bury-dead function. If you encounter failing cases because of this, then please produce (set! nop.0 nop.0) instead of empty begins.

• Branches are often thought of as expensive, so real compilers often perform trace scheduling, an optimization that rearranges blocks and takes advantage of fall-through between blocks to reduce the number of jumps.

  Implement a function trace-schedule to perform this optimization. The source and target language is Block-asm-lang v4.

  This optimization works in conjunction with the next optimization.

• In Para-asm-lang v4, it’s unnecessary to have a jump when the target of the jump is the next instruction. Design and implement a peephole optimization pass, called inline-jump, that eliminates these unnecessary jumps. The source and target language is Para-asm-lang v4.

  Be careful to only eliminate the label if you know its unused.