CA5 — Optimizing Compiler

Project Overview

CA5 is due 5/10 at 11PM.

CA5 is not submitted through the LDI course website. Please use https://kleach.cs.virginia.edu/shibboleth for your submission.

Compilers Assignments 1 through 5 will direct you to design and build an optimizing compiler for Cool. Each assignment will cover an intermediate step along the path to a complete optimizing compiler.

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.

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.

We are focused on optimizations that increase execution speed of the final program. You do not need to consider optimizations that save memory, generate code faster, or optimize power consumption. Focus only on optimizations that will produce the fastest possible code to execute.

CA5 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.

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. 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., file.cl-type). That argument will be an ASCII text Cool Annotated Abstract Syntax Tree file (as described in below) 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 CA5

You must turn in a zip file containing these files:

  1. readme.txt—your README file
  2. source_files—including
    • main.rb or
    • main.py or
    • main.js or
    • main.hs or
    • main.ml
  3. Four test cases — test1.cl, test2.cl, test3.cl, and test4.cl

Your zip file may also contain:

Submit the file to the course autograding website.

Working In Pairs

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. Both members bear full responsibility for the completion of assignments. Partners turn in one solution for each programming assignment; each member receives the same grade for the assignment. If a partnership is not going well, the teaching assistants will help to negotiate new partnerships. 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 CA5 zipfile. That submission should include the file team.txt, a one-line flat ASCII text file that contains the email address of your teammate. Don't include the @virgnia.edu bit. Example: If ph4u and wrw6y are working together, ph4u would submit ph4u-ca5.zip with a team.txt file that contains the word wrw6y. Then ph4u and wrw6y will both receive the same grade for that submission.

Autograding

We will use scripts to run your program on various testcases. The testcases will come from the test1.cl and test2.cl 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:

  • ghc --make -o a.out *.hs ; ./a.out testcase.cl-tac >& testcase.out
  • node main.js testcase.cl-tac >& testcase.out
  • ocamlc unix.cma str.cma *.ml ; ./a.out testcase.cl-tac >& testcase.out
  • python main.py testcase.cl-tac >& testcase.out
  • ruby main.rb testcase.cl-tac >& testcase.out

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