Due: 18 April 2013 at 11:59:59pm
Download: project6.zip
To Submit: Go Here
This is a group project. Teams of size 1 or 2 are acceptable. If you are working in a team of two, only one student needs to submit the project. Be sure to fill in the team.txt file.
What to turn in:
Turn in a file called project6.zip. It should contain at minimum:- The file opt.ml modified to implemenat an optimization of your choice for one of the stub functions provided in opt.ml (but see below about extra credit).
- Any additional .oat test files and the accompanying providedtests.ml needed to run them.
- A description of your optimization and its evaluation in README.txt
- The team.txt file.
Overview
The OAT compiler produces pretty inefficient executables because it does no optimizations and it uses too many temporary slots when computing intermediate values. In this project you are free to implement OAT optimizations of your choice at one (or more) of the different levels of program representations: at the AST level, at the IL level, or at the assembly level.
Building/Running the Project
This project uses the same build configuration as in Project 5.
The main executable also supports three new command-line flags: -Oast, -Oil, and -Oasm. These direct the compiler to apply the optimization function found at the AST, the IL, or the assembly level of the compiler, respectively. For example, if you choose to implement some AST-level optimizations (implemented in the file optast.ml), you can enable your optimizations by adding the -Oast flag to the command line.
What to Do
We have provided a complete, working implementation of the OAT compiler. The new framework has hooks into three places where you can apply optimizations: at the AST level, at the IL level, and at the assembly level (see opt.ml). By default, these optimizations are implemented simply as identity functions. Pick one of these levels and implement an optimization of your choice at that level. See the lecture notes for inspiration about the kind of optimizations you might choose.
Whatever optimization you choose to implement, it should preserve the correctness of the compiler. We have included the usual suite of test cases -- your compiler should yield the same answers for them with or without optimizations turned on.
The optimization you pick can impact the generated code in various ways: it might improve the runtime performance or it might change the code size (making it smaller or larger, for example). Design some experiments to measure the impact of your optimizations. For example, you might look at the running time of a number of benchmarks with and without the optimization enabled.
You may use the given test suite to help measure the impact of your optimizations, but since most of them are very short-running programs, you may need to develop additional test cases. For example, you might want to create a long-running loop that does some complex calculations to measure performance improvements. You can add additional test cases to be run via the --test flag in the providedtests.ml file. See the gradedtests.ml file for examples of how to set up tests that run .oat files.
Finally, document your project so that the TA can verify your results. Complete the README.txt file with a brief description of your optimization and test methodology and a summary of your results. The README.txt should also include step-by-step instructions that we can use to check your claims.
Measurements
Code size can easily be measured by looking at (for example) the number of bytes in the resulting .o file.
The running-time of your program can be measured using the time command on Linux/Unix/Mac. To get better measurements, you will want to test your programs on a "lightly loaded" machine (e.g. your laptop running only a minimum number of processes). Such an isolated environment might be hard to do get on Eniac; we aren't going to hold you to rigorous scientific methodology, but do the best you can.
We aren't looking for a deep statistical analysis of the performance measurements you make, but you might want to test your results multiple times and compute averages. You might also want to create a program that is parameterized in some way (e.g. by a number of loop iterations or by a size of some data structure) and test your optimizations for varying sizes of inputs or run durations. Such series tests can help you determine whether there are other low-level effects (such as caching) that contribute the the behaviors you see.
Comparing against LLVM
To get a sense of what a sophisticated optimizing compiler can do, we have configured OAT so that if the --llvm-backend flag is used, the LLVM compiler will perform -O2 level optimizations, which includes the alloca promotion and register allocation optimizations (along with many others) discussed in class. Compare your (simple) optimization to both un-optimized OAT and to LLVM-optimized OAT.Hints
Doing a really good job of optimization (e.g. register allocation), while likely to have a very significant impact on the quality of the code, is a very difficult project for the given time frame. You are welcome to try for such an ambitious optimization, but that level of sophistication is not required to get a good score on this project. If you are in doubt about whether your optimization is too ambitious, contact one of the course staff and ask us about it.
- Many of the optimization passes work on specific parts of the
the program -- for example, you might want to process only the
arithmetic expressions at the AST level. However, to apply those
optimizations, you will need to write code that traverses the
program, searching for expressions, and applying the optimizations
to them. For other parts of the code, it is likely that your
transformation is just the identity function -- i.e. it just copies
over the original program fragments.
The code that does this program traversal will be very similar to the pretty-printing code at the corresponding level (e.g. astutil.ml pretty-prints AST programs, and il.ml has code for pretty-printing the IL). You might like to structure code similarly.
- Depending on the transformation you need to do, you might need context information (about the types of variables or which temporaries are in scope, for example). If so, you'll need to create and thread through an appropriate context (as in the typechecker or phase1 code).
Grading
Unlike the previous projects, this project does not have as much automated grading support. Your grade will be determined by:- Implementation / level of difficulty of the optimization: 40 pts.
- Correctness of your optimization pass(es): 20 pts.
- Thoroughness of your evaluation, experiments, and writeup in README.txt: 30 pts.
- Coding Style: 10 pts.
Extra Credit
Should you choose to implement optimizations at more than one level, you can earn extra credit, depending on the sophistication of the additional optimization and the thoroughness of the evaluation. At most 20 points of extra credit can be earned this way. Do not attempt extra credit until you have complete one optimization pass completely.