PA6 — Optimizing Compiler

Project Overview

PA6 is due 4/24 at 11:50pm.

Please use this link to submit for PA6

Special Note PA6 is, by default, an extra credit assignment that can give you a 10% boost on your final grade. However, you can also choose to use your PA6 submission in lieu of taking the written final exam for the course. If you would like to use your PA6 submission in place of the written final, you must email me your decision to do so before April 16 at 5pm. If you do not email me, I will assume you are sitting the written final exam. If you are on a team, each team member is graded individually. If your teammate does not want to take the written final and you all submit PA6, you will receive up to 10% extra credit, while your teammate will not.

If you choose to replace your final exam grade with PA6, you will not be eligible for extra credit via PA6. You are merely replacing your final exam grade with your PA6 grade.

You may do this assignment in OCaml, Haskell, JavaScript, Python, or Ruby. (There are no language restrictions for Compilers Assignments.) (If you don't know what to do, OCaml and Haskell are likely the best languages for the compiler and optimizer. Python is a reasonable third choice.)

You may work in a team of two people for this assignment. You may work in a team for any or all subsequent Compilers Assignments. You do not need to keep the same teammate. The course staff are not responsible for finding you a willing teammate.


For this assignment, you will produce a program that takes a cool AST as input and produces either optimized Cool assembly or optimized x86-64 assembly.

We are focused on optimizations that increase execution speed of the final program or the memory consumption of the final program. You do not need to consider optimizations generate code faster, optimize power consumption, or minimize code size. Focus only on optimizations that will produce the fastest possible code to execute or that consumes the least amount of memory. If you choose to minimze memory consumption, note that we count cache misses as a proxy for memory consumption

PA6 features a leaderboard that ranks you against the reference compiler (with and without optimizations turned on) and other students in the class. For each test case, your performance is evaluated and compared against the reference compiler. Please use this link to make your PA6 submissions.

For x86-64 submissions, we use perf to record performance counters in the CPU, specifically cycle count during execution and cache misses.

For Cool ASM submissions, the reference compiler has a built in performance checker that deterministically calculates how fast your submission is.

In either case, the better you do compared to the reference compiler, the better your grade will be. Note that we only care about minimizing CPU cycles or minimizing cache misses. While other optimizations exist, we do not care about them here.

The Specification

You must create three artifacts:

  1. A program that takes a single command-line argument (e.g., That argument will be an ASCII text Cool Annotated Abstract Syntax Tree file (as described in in PA4) corresponding to one or more classes and methods. The cl-type file will always be well-formed (i.e., you can assume is passed the type-checker).

    Your program should produce either file.s for x86-64 submissions or for Cool ASM submissions.

  2. A plain ASCII text file called readme.txt describing your design decisions and choice of test cases. See the grading rubric. A paragraph or two should suffice.
  3. Four testcases named,,, and

What To Turn In For PA6

You must turn in a zip file containing these files:

  1. readme.txt—your README file
  2. source_files—including
  3. Four test cases —,,, and

Your zip file may also contain:

Submit the file to the course autograding website.

Working In Teams

You may complete this project in a team of four. Teamwork imposes burdens of communication and coordination, but has the benefits of more thoughtful designs and cleaner programs. Team programming is also the norm in the professional world.

Students on a team are expected to participate equally in the effort and to be thoroughly familiar with all aspects of the joint work. All members bear full responsibility for the completion of assignments. Teams turn in one solution for each programming assignment; each member receives the same grade for the assignment. If group composition is not going well, the teaching assistants will help to negotiate new teams. Teams may not be dissolved in the middle of an assignment. If your partner drops the class at the last minute you are still responsible for the entire assignment.

If you are working in a team, exactly one team member should submit a PA6 zipfile. That submission should include the file team.txt, a line-delimited flat ASCII text file that contains the UniqName of all team members.


We will use scripts to run your program on various testcases. The testcases will come from the and files you and your classsmates submit as well as held-out testcases used only for grading. Your programs cannot use any special libraries (aside from the OCaml unix and str libraries, which are not necessary for this assignment). We will use (loosely) the following commands to execute them:

Note that, because of the * in the commands above, the names of your files and the order in which things are included between them may cause your submission to break. Please ensure that you can run your compiler using the appropriate command above.

You may thus have as many source files as you like (although two or three plus your parser definition should suffice)—they will be passed to your language compiler in alphabetical order (if it matters). Note that we will not run the parser generator for you—you should run it and produce the appropriate ML, Python, or Ruby file and submit that.

Your submission may not create any temporary files. Your submission may not read or write any files beyond its input and output. We may test your submission in a special "jail" or "sandbox".

Grading Rubric