Milestone #4: Final Compiler and Paper Submission

Final Code Submission: Wednesday March 8th at 11:59pm CDT. No extensions can be used for this submission. Final Paper Submission: Thursday March 9th at 11:59pm CDT. No extensions can be used for this submission.

This milestone will require you to turn in the fully completed compiler for Golite.

Getting started

You will not be creating a new repository for every milestone. Continue to work out of the same repository as Milestone #1 for all remaining milestones and the final submission of the compiler.

Language Overview: GoLite

Please make sure you read over the document that describes the language we will be implementing this quarter: Language Overview

Milestone Requirement: Completed Compiler

You must complete the compiler in it’s entirety. Your program must perform register allocation (using the naive algorithm or graph-coloring discussed in lecture/pre-recorded video) for ARM assembly. The resulting output from this stage of the project should be valid assembly that can be assembled, linked, and executed.

Milestone Extra-Credit (Optimizations)

For extra-credit, you must implement at least one optimization from the list below:

• Copy Propagation

• Constant folding and propagation (These count as one optimization and not two)

• Dead Code Elimination

• Value Numbering

• Common Subexpression Elimination

• Tail Call Elimination

• Register Allocation via Graph Coloring (this counts as two optimizations due to its difficulty)

If there’s a compiler optimization that you found in the literature that you wish to implement then you need to get approval from Professor Samuels before implementing it.

Extra-Credit

You must have fully completed the compiler implementation and pass all the benchmarks before receiving extra-credit. You cannot have a partially correct compiler and receive extra-credit. Points will be rewarded based on implementation and difficulty of the optimization.

Command-line Options

Please make sure to include the options from the previous milestones in your final submission along with the following:

• -S: Produces the ARM assembly code for the program to a file. The file name should be the same name as the file provided to the compiler originally with a .s extension.

• -o programName”: Names the executable with the argument programName. If the -o is no specified then the program is named a.out.

• -O1: Turns on the optimizations for the compiler. By default the compiler produces an executable with no optimizations.

Paper Submission

The final paper must provide an overview of the architecture of your compiler and the important data structures used within. In particular, discuss the different phases of your compiler (listed below). Each of the following can be addressed in a paragraph or two.

• Lexing and Parsing: Describe how your compiler lexes and parses a Golite program?

• Static Semantics: Discuss how your compiler implements static type checking and how it checks to ensure all control-flow paths have a return statement.

• LLVM Intermediate Representation: Discuss the structure used to implement the LLVM instructions and how they are store after converting the AST nodes to LLVM instructions.

• Optimizations: State the specific optimization implemented and how you implemented the optimization in your code. Discuss the representation of the program as a set of control flow graphs with LLVM instructions. If you did not implement an optimization then discuss how you would modify your compiler to include one. Talk specifically about what packages you would need to add, how your LLVM representation would need to change, etc.

• Code Generation and Register Allocation: Discuss any interesting aspects of your translation from LLVM to assembly.

• Misc.: Discuss other aspects of your compiler that you find interesting. Be proud that you implemented you very first compiler and talk about your struggles and what you learned in the process.

Each member of a group or individuals must submit their own paper separately. This ensures each group member/individual understood the implementation details for each component. I expect the paper to be in range of 3 pages. However, you can definitely describe these details in less than 3 pages. You can go pass the 3 page requirement.

Grading and What to Submit

You must provide the following to get full credit for this milestone:

1. Submit your final paper at the root of your repository in a PDF format. Please use your CNET-ID for the name of the paper.

2. A README file that states how any information we will need to run your compiler.

3. Please submit your final paper and final code submissions separately on Gradescope. There will be two submissions pages for each. However, make sure to also include your paper in the root directory of your compiler.

The following table breaks down the highest possible grade you can receive on your final submission based on fulfilling the requirements specified. This does not mean you will automatically get that specific letter grade in a range if you generate the expected output for the benchmarks. We will also look over you code and implementation for the various phases of the compiler. The front-end of the compiler refers to lexing, parsing, and semantic analysis. The backend refers to LLVM translation and code generation. The breakdown is a bit subjective to allow for you to get the most points as possible.

Grade Range	Requirements
A range	Frontend and backend of the compiler is fully implemented and produces the expected output for all benchmarks using a naive register allocation. You can implement register allocation with graph coloring and that will count as an optimization.
Low A to high B range	Frontend of the compiler is fully implemented and backend produces the expected output for some benchmarks using naive register allocation.
B range	Frontend of the compiler is fully implemented but the backend does not produce any expected output for ARM but LLVM IR translation fully works for all benchmarks.
Low B to C range	Frontend of the compiler is fully implemented but the backend does not produce any expected output for the benchmark programs.
Lower than C	Frontend and backend of the compiler are not fully working and have many errors. This will be graded on a case-by-case basis.

Please note that at least 1/3 of the grading will be dedicated to verifying that the front-end (i.e., lexing, parsing, and semantic analysis) is working correctly.

Submission

Before submitting, make sure you’ve added, committed, and pushed all your code to GitHub. You must submit your final code submission through Gradescope (linked from our Canvas site) in the “Milestone #4 (Final Submission)” assignment page and the paper in the “Compiler Paper” page. Submissions for both can be done via two ways,

1. Uploading from Github directly (recommended way): You can link your Github account to your Gradescope account and upload the correct repository based on the homework assignment. When you submit your homework, a pop window will appear. Click on “Github” and then “Connect to Github” to connect your Github account to Gradescope. Once you connect (you will only need to do this once), then you can select the repository you wish to upload and the branch (which should always be “main” or “master”) for this course.

2. Uploading via a Zip file: You can also upload a zip file of the assignment directory.