2.7 Milestone 5.5: Optimizations
2.7.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.
2.7.2 Practicalities
The due date for this milestone is: Sunday 12th of May 2024 23:59 CEST.
The project is preferably in teams of 2 students or otherwise individual. Please remember that sending code or sharing code between teams is strictly not allowed.
A snapshot of your repository will be made on the day and time indicated by the due date. Make sure your code runs with the expected Racket and nasm versions by running it on the wilma server (see below) before submitting it. You may create additional files to structure your code, e.g. utility function or testing harness etc., but put code relevant for a single compilation pass in a racket file under the passes directory that is named like the pass. Make sure you keep the compiler.rkt and interface-test.rkt files provided by the skeleton, so we can easily access your implementation for every exercise.
Make sure to thoroughly unit-test each compiler pass you implement (this will be graded as well). We would like you to write your own original tests. You can get some inspiration for tests by using the online interrogator. It is good practice to write your tests and design your code before implementing it. You can include your tests in the special test submodule
You should reinstall the support package to use the one from https://github.com/soft-compilers/cpsc411-pub. You can do this via the command raco pkg update –batch –auto https://github.com/soft-compilers/cpsc411-pub.git?path=cpsc411-lib. This updated support package allows "begin" to have an empty list of effects, which is produced by the new "bury-dead" pass.
2.7.3 Grading
The project assignment needs to be done individually. Sending code or sharing code is strictly not allowed. Your project assignment will be evaluated on the basis of 3 different criteria:
Correctness Is your compiler correct? In other words, is there a difference between (1) intepreting (running) the source code or (2) compiling the source code and interpreting the target? We ask you to provide tests for this as well.
Implementation Are the non-obvious aspects of your implementation properly documented in comments in the code? Is the code comprehensible given your comments? Does the code uses meaningful identifiers? Do you successfully avoid excessive code duplication? Does it use the Racket standard library when possible?
Tests Did you write your own tests? Are edge cases tested? Are all the cases tested?
2.7.4 Checklist
Completely new passes
propagate-copies
bury-dead
trace-schedule
inline-jumps
2.7.5 Reading
You should revisit the course slides on copy propagation and the book chapter on Register Allocation for undead analysis.
2.7.6 Exercises
Exercise 1: 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.
Exercise 2: 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.
Exercise 3: 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.
Exercise 4: 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.