PA6 is not required for the F23 semester.
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!
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.
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:
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.
You must create three artifacts:
Your program should produce either file.s for x86-64 submissions or file.cl-asm for Cool ASM submissions.
You must submit the following files to the autograder.
Submit the file to the course autograding website.
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.
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.