PA6 — Optimizing Compiler

Project Overview

PA6 is due 12/14 at noon Central Time. Note this is different owing to the final exam schedule. Absolutely all course material must be turned in by this point. I recommend you complete this assignment by the last day of class, 12/4.

If you complete this assignment using x86-64 assembly, you do not need to submit it to the autograder. There is a separate process for demonstrating performance improvement for x86-64 optimizing compilers.

You must complete this assignment in Python.

You may work in a team of up to 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. If you want to work on a team, you must register your group on the autograder before submitting!

Goal

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.

The autograder only supports Cool ASM. More information forthcoming about the x86-64 option.

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.

This is a conceptual hurdle. In previous assignments, we have evaluated your submission's output directly against a known-good output. In this assignment, however, your compiler produces assembly code that is executed in turn. That is, we are evaluating the execution speed of the code produced by your compiler (and not of the compilation itself).

As an example, consider the following code:

class Main inherits IO {
  main() : Object {
    let x : Int in {
      x <- 5 + 4;
      out_int(x);
    }
  } ;
} ;

If we compile this code without thinking about optimizations, the x < 5 + 4; expression will result in an add instruction and an instruction to store x in a register. However, this is wasteful because the 5+4 can be shorted to 9 during compilation to save an add instruction. Your job in this assignment is to analyze the abstract syntax tree of the input program and automatically transform it to optimize generated code. This optimization is called constant propogation.

You can consider several other types of optimizations:

It is quite possible to get the vast majority of the points by implementing dead code elimination and peephole optimization. Indeed, you may first try submitting your PA5 code unchanged -- some students produce reasonably efficient code to begin with.

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. For each test case, we will compare the performance of your compiler's generated code against the optimizations implemented in the reference compiler. You can use cool --profile some_file.cl-asm to produce a performance report. In particular, we care about the last line of the output which counts the number of CPU cycles consumed by running your code.

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. While other optimizations exist, we do not consider them here.

The Specification

You must create three artifacts:

  1. A program, main.py, that takes a single command-line argument (e.g., file.cl-type). 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 file.cl-asm 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 test1.cl, test2.cl, test3.cl, and test4.cl

What To Turn In For PA6

You must submit the following files to the autograder.

  1. readme.txt>>&mdash;your README file
  2. Your source files—including
  3. Four test cases — test1.cl, test2.cl, test3.cl, and test4.cl. These test cases should contain opportunities for optimization (e.g., dead code, boxed types, etc.).

Submit the file to the course autograding website.

Working In Teams

You may complete this project in a team of two. 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 on a team, you must register your team on the autograder before submission. Your team will share submissions (a total of 5 per day per assignment) and late day tokens (4 per group). All team members will share the same submission grade.

Autograding

We will use scripts to run your program on various testcases. These test cases include .cl files from students in previous semesters. We may use your test cases in future semesters if they are high enough quality.

We will use python3 main.py test_file.cl-type to compile each test case with your submission. Then, we will use cool.exe --profile test_file.cl-asm to evaluate the performance of your generated code.

Students frequently separate their submissions across multiple files or modules (e.g., one for deserializing the input, one for creating AST structures, one for dataflow analyses, and one for code genertion). You can do the same and include up to 20 additional *.py files in addition to your main.py file.

Your submission does not need to produce any intermediate files or output. If only needs to produce an appropriate .cl-asm file. Any attempt to subvert the autograder (e.g., by uploading the reference compiler, attempting to reveal the contents of test cases, or intentionally depleting computing resources) is a violation of the honor code and will result in a failing grade for the assignment or course.

Grading Rubric