Project 6

Extend your implementation of the full OAT compiler to perform simple optimizations.

project6.tar.gz contains all that you need to get started with this assignment. Extract it to your projects directory such that full.ml is located at cis341/projects/fullopt/full.ml. (All files are stored in the tarball relative to cis341, so switching to your cis341 directory and running tar xvf project6.tar.gz should do the trick.) Edit the OMakefile at cis341/projects/OMakefile by adding the new directory to the .SUBDIRS declaration: PROJECT_SUBDIRS[] = x86interp expressions controlflow arrproc full fullopt

This package depends on the files from Project 5. It includes the idiv patch.

Remember that you may change the provided code so long as you keep the interfaces the same (so that we can use everyone's testers on everyone's assignments).

This is a group project. Groups of size 1 or 2 are acceptable.

The file full_basic_opt.mli defines an interface that the rest of the fullopt compiler uses to invoke optimizations at different points throughout the compilation process. Example implementations of each of these functions are provided in full_basic_opt.ml. (The examples do not encode a particularly good optimization.)

Your job is to use this interface to write at least one simple optimization that improves the quality of the generated code. The optimization should not rely on any dataflow analysis (although if you want to go that route, let us know). Extra credit will be assigned for implementing more than one optimization pass. We suggest that you choose from the following list of possible optimizations:

Constant folding: typed or untyped.
Constant propagation: typed or untyped.
Unreachable code elimination: remove blocks that cannot be reached from the control flow graph.
Inlining: make sure to document your heuristic.
Loop unrolling: make sure to document your heuristic.
Call site specialization: convert InvokeVirtual instructions to InvokeCdecl instructions when you're sure of the exact runtime type of the target object.
Peephole optimizations and strength reduction: at least 5 cases. This includes tactics like eliminating silly moves by walking once over an instruction sequence, converting multiplies to shifts, modulus divisions to bitmasks and so on.

For (each of) the optimizations you implement, provide a short description of the algorithm used and an example of the transformation being applied to a snippet of code (either as an AST or instruction sequence). You should also gather quantitative evidence to show that your method has improved the generated code: if you're targeting speed, develop some micro-benchmarks and calculate the speedup. If you're trying to reduce code size, demonstrate your success by running your compiler on larger examples and giving instruction counts. (The demos from previous projects are good candidates. It's easy to update examples from arrproc to full OAT.)

You can receive extra credit for this assignment by implementing more than one of the optimizations listed above. You can also receive credit by implementing the same optimization at both the AST level and at the machine code level. You will not receive credit for the same optimization more than once at the same coarse level of abstraction (so you won't get points for submitting both untyped constant folding and typed constant folding or for submitting both IL constant folding and X86lite/X86 constant folding). If you have any questions (or wish to implement an optimization that is not in the above list), please contact us.

Remember that you are likely to see an improvement in performance if you experiment with running different sequences of your optimizations. For example, you could run several passes of constant folding and constant propagation (or of constant folding and unreachable code elimination). Document your results.

Edit the included readme.txt file, making sure to fill in your name(s) and email address(es).

You should also spend some time to ensure that your code is readable and well-commented. We have some suggestions and requirements for your programming style. You will definitely lose points for the file submission requirements (code must compile, 80 column limit, no tabs); however, barring any particularly egregious cases, you may take the remaining rules as suggestions.

Part of your grade will be based on testing. Some example tests and utility functions are provided in full_test.ml. You must use the testing framework provided and explicitly note any modifications in your readme.txt file. We ask that you name your test cases regularly: choose a username from those in your group. All test names and files should contain that username followed by an underscore as a prefix. (For example, if your username is cat and you have written a test case called alive, that test should be called cat_alive.)

For this assignment, we require that you define at least 10 new unit tests. (These must be sufficiently different from one another to count— tests like 1 + 1 is 2, 1 + 2 is 3, 1 + 3 is 4 are too similar to be useful).
All test cases that you count toward the testing portion of your grade must be fully automatic and must check for some result. The tests must run when we call omake test from the fullopt directory.
For this assignment, you should not share test cases on the class mailing list. (We expect that everyone's implementations will be different enough that this would become confusing.)

The grading breakdown for this project is as follows:

~60%: Your optimization.
~20%: Your analysis.
~10%: Code style, readability and documentation.
~10%: Testing.

Each optimization you complete for extra credit is worth another +10% (with a maximum of 4). You will be expected to document each new optimization as well as provide an analysis of the effects the optimizations have on one another. We will count your best optimization toward the 80% in the regular assignment breakdown.

Remember that your raw score will be scaled— that is, more difficult assignments will be worth more than less difficult assignments, even if the more difficult assignment has fewer available points.

fullopt.run, the executable the OMakefile will produce, offers several helpful command line flags that might make debugging easier. These are:

-O: enables optimizations
-c: cleans the temporary directories c_bin and c_obj.
--showast: prints the AST to the console.
--printasm: prints the generated assembler (in AT&T syntax) to the console.
-p: prints the generated IL to the console.
-r: runs the resulting executable.
-d: runs the resulting executable in the debugger, setting a breakpoint at the start of your generated code.
--ddd: runs the program in DDD, a graphical interface to gdb.

A good combination of flags for this assignment is: ./fullopt.run -O -c --showast -p --printasm testfile.oat In particular, --showast, -p and --printasm will print out the intermediate results from your optimizations.

First, make sure to clean your project with omake clean. All of the files you've written should be in projects/fullopt. Submit your assignment on ENIAC. Your project must run on ENIAC, including all test cases. Be sure to submit from ENIAC and not from some other Linux machine; otherwise you will get an error.

Switch to the projects directory and type: turnin -c cis341 -p project6 fullopt Verify that you've submitted your files with: turnin -c cis341 -v -p project6 You can re-submit your work any number of times, but only the last submission will be counted. New submissions completely overwrite old submissions— so if you're missing a single file, make sure to resubmit your entire project. Check the main course page for information about late policies.