Due Date: Friday, April 5 at 11:59pm via GitHub.

Introduction

In this assignment your team will be completing the backend of your Source language compiler by implementing a code generator that targets the CSC488 Machine.

• See the lecture slides for details on the Machine architecture and instruction set.
• See the Source language code generation overview for a description of what is required to support each aspect of the language.
• See the Assignment 4 document for break down of the kinds of design issues you will need to resolve before you will be able to complete the code generator.

Getting started

There is no new starter code for Assignment 5. Copy the contents of your A3 assignment submission with the A4 starter code into a new a5 directory. The A4 starter code package is disjoint from previous packages, so it should not accidentally clobber any of your teams' work when you combine them.

1. Create a new directory csc488/codegen, and put an empty file __init__.py there.
2. Create a new class CodeGen in csc488/codegen/codegen.py, similar to the SemanticAnalyzer in csc488/semantics/analyzer.py. This class should have an entry point that takes a Program AST as input (plus anything else you deem important), and returns a Python list of AssemblyCode such as Instrns, Labels, etc. (see csc488/machine/defs.py from A4)
3. Modify the sc tool (under csc488/tool/sc/main.py) to add a code generation step just after successful semantic analysis (at the # Backend... comment). Duplicate what csc488/tool/mas/main.py does from about line 316 onwards (that is, instantiate a Machine, assemble the code into it, and then run it.)

Inside of the CodeGen class, implement your code generation strategy. If you choose to use the suggested visitor pattern approach, this will take the form of a series of AST node type visit methods that will work together to generate Machine instructions for each aspect of the language.

The net effect of running sc on a semantically valid .488 program source file should be to compile and execute it.

Suggestions

• Carefully study csc488/machine/tests/test_machine_core.py and csc488/machine/tests/test_codegen_ideas.py, which contain extensive examples and tips on how to programmatically generate code for the Machine. Remember, prior to assembly the code is simply lists of instructions, so think in terms of creating helper functions and methods for yourself.
• You are free to revisit your A3 semantic analyzer and add any additional AST annotations or transformations that will make your life easier.
• During codegen visitation, consider saving additional Labels into the AST. They will help you as you go. Just don't forget to eventually include them in the code list, so that their address can be resolved.
• Try starting with very small subsets of the Source language first, and then progressively build up to more and more aspects of the language:
  • Printing constant expressions
    • Only the print statement
    • Only integer and Boolean valued constant expressions
    • No named local variables or procedures/functions
    • Only non-shortcircuiting expression types
    • Example: print 1, print 1 + 2, print 1 < 2, print (1 if true else 2), etc.
  • Next add Boolean and/or conditionals
  • Add if statements
  • Add looping constructs
  • Add break statements
  • Add scalar variables to the top level only, plus assignment statements and variable references in expressions
    • Lay out a very simple activation record for lexical level 0
  • Add input statements
  • Add support for arrays
  • Implement non-recursive procedures with no parameters at static nesting depth 1 only (no procedures-within-procedures)
    • Work out how call into a procedure and successfully return back to the original callsite
    • Implement local variables for procedures
  • Implement non-recursive procedures with parameters (at depth 1 only)
    • Work out how the caller and callee need to coordinate to handle parameter passing and cleanup
  • Implement non-recursive functions with and without parameters (at depth 1 only)
    • Work out how to return a value out from a function
    • Implement function calls as expressions
  • Implement recursive procedures/functions at any depth
    • Work out the full activation record, including saving and restoring the display entry for a given lexical level into the activation record

Testing

Implement and document a strategy for testing your code generation. Whereas earlier assignments focused on testing for correct values and the structure of certain outputs, for this assignment consider testing your code generation in terms of the correct effect of actually running the resultant code.

For example, a good series of functional tests would take the form:

• Source program print 488 should output 488
• Source program var x integer x = 2019 print x, " ", x + 1 should output 2019 2020
• etc.

Consider how you can wire up all the phases of your compiler in order to write this kind of test. The tests in csc488/machine/tests/ demonstrate what is required in terms of providing input and capturing output from the Machine towards accomplish this.

How to submit

Copy your a3 directory and the starter code in the a4 directory (from the a4starter branch) into in a final a5 directory.

Implement code generation, along with any associated tests.

You submission must run correctly on teach.cs.toronto.edu. Failure to correctly run in that environment may result in an overall assignment mark of 0.

Modify a5/README.md by adding the following:

• Your team member names
• A brief summary of the contributions made by each team member
• 1-4 paragraphs providing a high-level overview of your testing strategy, with justification for the choices you've made and a brief commentary on the relative strengths and/or weaknesses of the approach you've adopted

Push your commits to the master branch of your repository.

Submission checklist

• Check that your submission runs correctly on teach.cs.toronto.edu
• Code generation under a5/csc488/codegen/codegen.py
• Add some fun Source language example programs under a5/examples/ which your compiler is able to run
• Choose and implement a strategy for testing (possibly adding tests under a5/csc488/codegen/tests/), and remember, automated testing is your friend and ally

---