Milestone #4: Final Compiler and Paper Submission

Due Dates:

  • Graduating Students: Friday December 3rd at 11:59pm CDT. No extensions can be used for this submission.

  • Non-graduating Students: Friday, December 10th 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 discussed in lecture/pre-recorded video) for ARM assembly. However, you can implement graph-coloring if you wish. The resulting output from this stage of the project should be valid assembly that can be assembled, linked, and executed.

Milestone Extra-Credit: Compiler Optimization

If you have time then for extra-credit, implement value numbering optimization discussed in class or any compiler optimization you wish that we may or may not have talked about. You will use a flag to turn on the optimization that is described in the next section.

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.

  • ILOC Intermediate Representation: Discuss the structure used to implement the ILOC instructions and how they are store after converting the AST nodes to ILOC 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 ILOC 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 ILOC representation would need to change, etc.

  • Code Generation and Register Allocation: Discuss any interesting aspects of your translation from ILOC 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. Remember the grading of the paper will count towards your midterm weight.

Grading and What to Submit

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

  1. At the beginning of week 9, Professor Samuels will provide a few benchmarks that will help you verify the validity of your compiler. They will be provided on Ed. Specfically the link is here:

Ed Post for benchmarks

  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.

The following table breakdown 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 back-end refers to ILOC 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

Front-end and Back-end of the compiler is fully implemented and produces the expected output for at least three three benchmarks with one benchmark being binarytree.golite or linkedlist.golite . This means you can still receive an A on the compiler even if your ARM code does not fully work for all edge cases in the language defined. We will not specify which benchmarks that need to be correct. You should focus on trying to produce the expected output for all of them.

B range

Front-end of the compiler is fully implemented but the back-end partially completed and produces an expected output for 1 or 2 of the benchmark programs.

C range

Front-end of the compiler is fully implemented but the back-end does not produce any expected output for the benchmark programs.

Lower than C

Front-end and back-end of the compiler are not fully working and have many errors. This will be graded on a case-by-case basis.

Graduating Students

You are not required to implement a fully working compiler. If you are in a group that is a mixture of a graduating and non graduating student then the graduating student must be the main group member working on code generation. The other group member can continue working on the generation code until their deadline. Please know that due to time constraints that as a graduating student you may not get code generation fully working. I will take this time constraint into consideration when assigning your grade to the compiler. However, I do expect at least the ILOC translation to be fully completed by your deadline.

Submission

Before submitting, make sure you’ve added, committed, and pushed all your code to GitHub. You must submit your final work through Gradescope (linked from our Canvas site) in the “Milestone #4 (Final Submission)” assignment page 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.