Project Overview

You may do this assignment in OCaml, Python or Ruby. Almost invariably this assignment is done by modifying your PA5 submission.

You may work in a team of two people for this assignment. You may work in a team for any or all subsequent programming assignments. You do not need to keep the same teammate (but it may be tricky to work things out if you switch between PA5 and PA6). The course staff are not responsible for finding you a willing teammate.

Goal

In all cases, the optimized assembly code you emit must produce exactly the same result as the reference interpreter. The first rule of optimization is "don't break the program".

You do not have to worry about "malformed input" because the semantic analyzer (from PA4) has already ruled out bad programs.

The Specification

1. A program that takes a single command-line argument (e.g., file.cl-type). That argument will be an ASCII text Cool class map, implementation map, parent map and annotated AST file (as described in PA4). Your program must emit file.cl-asm, a Cool Assembly Language program. Executing file.cl-asm in a Cool CPU Simulator must produce the correct output for file.cl according to Cool's operational semantics. Your program will consist of a number of OCaml files, a number of Python files, or a number of Ruby files.
   • You will only be given .cl-type files from programs that pass the semantic analysis phase of the reference compiler. You are not responsible for correctly handling (1+"hello") programs.
2. A plain ASCII text file called readme.txt describing your optimization design decisions and choice of benchmarks. See the grading rubric. A few paragraphs should suffice.
3. Two benchmarks test1.cl and test2.cl. Each benchmark should be a valid Cool program that takes 50,000 instructions or fewer to execute (via the reference compiler and --asm and --profile). Optimizers will be graded on the average of their performance on a pool of programs: that pool contains some baseline Cool programs as well as all benchmarks submitted by participants. You can thus "stack the deck" in your favor by constructing programs that you are very good at optimizing but that others may not be able to handle.

Scoring

Each optimizer will be evaluated on the same set of benchmark programs. Your optimizer's "score" for a program is the factor reduction it obtains over the reference non-optimizing compiler expressed as a percentage. For example, if cool --asm on benchmark1 produces a program that takes 722564 cycles and your optimizer on benchmark1 produces a program that takes 551855 cycles, your speedup on benchmark1 is 1.31x. Note that scores below 1.00x are possible, but unlikely.

Your final score over the benchmark suite is the average of your scores on the individual benchmarks.

If your optimizer "breaks" any benchmark program, your overall score immediately becomes zero. If we deem your README to be inadequate, your overall score is cut in half. If an inspection of your code reveals that you are hard-coding the benchmark files (e.g., by including pattern matching that works for the baseline Cool benchmark programs but few others), your overall score will be cut in half.

Baseline Benchmarks

• cool-optimizer-benchmarks.zip (as of Wed Nov 11 15:20:48 EST 2009)

You can test your optimizer's performance (and see its average speedup) by submitting it to our testing server.

Proposed Extra Credit

We currently propose that any optimizer that is twice as good as cool --asm --opt will grant a 2% overall course grade improvement. When you submit your optimizer for testing, we will show you the reference optimizer's performance as a comparison.

We currently propose that the best optimizer in the class (or best two optimizers) will grant a 5% overall course grade improvement. Doing a stellar job on the optimizer also makes it easier for me to write you a strong letter of recommendation, since it is a largely independent project where you must synthesize and apply concepts from class on your own. For letters of recommendation, the complexity of the optimizations you attempt matters more than the final numerical speedup.

Commentary and Suggestions

• Constructing a CFG and performing dataflow analyses, such as:
  • Constant folding and propagation
  • Dead code elimination
  • Common subexpression elimination
• General AST pattern-matching optimizations, such as:
  • Loop unrolling
  • Loop-invariant code motion
  • Inlining method or constructor calls
  • Constant string merging
• Object-oriented optimizations, such as:
  • Constant constructors
  • "Unboxing" Integers
  • "Unboxing" Bools, Jump Threading for conditionals
  • Removing unused methods and fields
• Assembly-level optimizations, such as:
  • Peephole optimization
  • Strength reduction
  • Code layout optimizations
• Register optimizations, such as:
  • Using R4 through R7 as the first four stack slots
  • Making your own calling convention (e.g., for constructors)
  • Full-blown register allocation

What To Turn In For PA6

1. readme.txt -- your README file
2. benchmark1.cl -- a testcase
3. benchmark2.cl -- a testcase
4. source_files -- your implementation, including
   • main.rb or
   • main.py or
   • main.ml

• team.txt -- an optional file listing your other team member (see below -- if you are not working in a team, do not include this file)

Working In Pairs

Autograding