Milestone #4: Semantic Analysis and CFG

Due: Friday February 21st at 11:59pm

This milestone will require you to complete the front-end of the compiler along with beginning the back-end generation with producing LLVM code.

Getting started

You will not be creating a new repository for every milestone. Continue to work out of the same repository as Milestone #3 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: Semantic Analysis

After constructing the AST, the final phase of the front-end must validate the AST to ensure that the program conforms to the static semantics of the language. Your validity checks must include those mentioned in the description of the Language Overview. The semantic analysis phase must report an error if an appropriate main function is not defined. You must check to ensure that if a function returns a type that all control-flow paths have a return statement. This will require a bit of bookkeeping that you will need to think about. For example,

//Standard Case
func foo (num int) int {
  return num;
}

//Control-flow case
func bar (num int) int {
   if (num == 0) {
     return 1;
   } else {
     if (num >= 1) {
       return 1;
     }else {
       return -1;
     }
   }
}

If any of these return statements are removed then an error should be thrown.

We will verify the correctness/completeness of this requirement by writing test-cases based on the Language semantics specified in the Language Overview document. We recommend you write a few test case for each bullet point specified in the Language Semantics section in the Language Overview document to ensure your semantic analysis implementation is working correctly. We have provide few testcases under the sa directory of golite-benchmarks repository. Please note: Your errors messages do not have to match the expected error messages inside each sa testcase! The expected error output is showing what type of error should be produced.

If you need assistance getting started with semantic analysis then please watch the video Semantic Analysis Code Structure inside the M4 Videos folder.

Milestone Requirement: LLVM IR

For this milestone, your compiler will take the validated AST from semantic analysis translate it into LLVM IR. As stated in lecture, the output of LLVM IR is a .ll file that contains the original source code represented in its LLVM IR form.

We will verify the correctness/completeness of this requirement by running the golite-benchmarks on the provided input and ensures it matches the expected output (also provided).

You are only required to use a stack-based implementation.

The slides and videos in the M4 Videos folder provide guidance on how to get started with this phase.

Command-line Options Augmented

For this milestone, the must augment the compiler with the additional command line argument flags:

  • -ast: Produces a print out of the AST generated by the compiler after parsing. We are not requiring you to produce the exact whitespace formatting of the original source code.. However, the structure should strongly resemble the original source code. Many of you already did this in the prior milestone; although, some of you may have used the default string output but now you must a separate String() method to resemble the original source code.

  • -llvm: Produces the LLVM IR form from the input source file. The filename must be the same as the original source filename but with the extension of .ll.

  • -target=STRING: Changes the llvm target triple value. The STRING argument is an argument that states the target triple string to use. The default target triple string must be “x86_64-linux-gnu” (i.e., the CS Linux Servers).

Grading and What to Submit

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

1. A completed semantics analysis and LLV IR phase. 1. A README file that states how to read the printing of your -ast, --llvm, and -target=STRING command line options. Explicitly state which golite-benchmarks are working.

The milestone is 6% of your grade and the exact weights for grading are:

  • 6%-5% credit: Semantic Analysis is fully implemented and works correctly, and LLVM IR works is completed for all of the golite-benchmarks. This means you are generating the expected output for each benchmark.

  • 4% credit: Semantic Analysis is fully implemented and works correctly. LLVM IR work has started and works for at least 4 of the golite-benchmarks. The sa directory is not considered one of the 4 golite-bechmarks since that directory is used to test if semantics analysis is working.

  • 3%-2% credit: Semantic Analysis is fully implemented and some LLVM IR work has begun.

  • 1%-0% credit: Semantic Analysis is partially completed or no solution.

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