CSC488 Assignment 4: Code generation templates

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

Note: This assignment is optional. You may choose to skip it and go straight onto Assignment 5 if you wish.

Introduction

In this assignment your team will be designing and documenting your code generation strategy that you will implement in Assignment 5. See the Source language code generation overview for details.

You will provide this documentation in the form of a collection of *.mas assembly source files, which must contain a combination of written documentation as comments, along with short illustrative fragments of working assembly code. The .mas code should be correct and runnable, although it does not necessarily have to produce any particular output.

You have been provided with the mas assembler tool in the starter code. There is no additional Python code to write for this assignment, but you will be writing assembly code and using this tool to run it. See the lecture slides for details on the Machine architecture and instruction set, as well as the tests in the starter code.

Since the final code generation step will involve mapping AST nodes onto these code generation templates, it is useful to think in terms those AST nodes. The mapping does not have to be one-to-one (i.e. you can group several constructs into a single assembly file), but you must acknowledge and provide sufficient detail for every facet of the language. For example, do not gloss over the fact that the Source language has binary expressions for which there are no corresponding Machine instructions.

To summarize, the code generation templates should provide sufficient detail such that a motivated student could take them and successfully implement Assignment 5.

Example stmt_foo.mas

Here is an example for a ficticious foo statement construct. Note the use of stack pre- and post-conditions, along with symbolic tracking of stack contents.

    /*
    Source languange: handling the _foo_ statement.

    To execute a _foo_, we will need the address of a _BAR_, as well as the
    offset for _QUUX_. We will use a label `label_BAR` from our global list,
    and lookup the constant for QUUX form our activation record for the
    enclosing magic scope, which we will save within the AST node during the
    semantic analysis phase (see `other.mas` for details on this layout).

    We will generate code for the _FOO_ statement as follows:
    */

    _foo_stmt:
                                # Stack:
        push label_BAR          # Stack: <label_BAR>
        push 1                  # Stack: <label_BAR> 1
        whizbang                # Stack: <label_BAR> 3 1 4 1 5 9 2

        # Note that we choose to use the `splat` instruction here because the
        # alternative `splort` would require a different ordering of the stack.
        splat                   # Stack: <label_BAR + 488>

        yada offset_QUUX        # Stack: <label_BAR + 488> <offset_QUUX>
        magic                   # Stack: <final answer>
        printi                  # Stack:

        # Final result is the output of a BAR foo'd with a QUUX.

Language features

Storage

Describe and illustrate your strategy for allocating and addressing storage for all elements of a compiled program: code, constants, routine definitions, local variables.

  1. Variables in the main program
  2. Variables in procedures and functions
  3. Variables in minor scopes (ex: if true { var x integer })
  4. Integer and Boolean valued constants (ex: small integers such as 488, larger than signed 24 bit values such as 1073741824, etc.)
  5. Text constant (as in, print "Hello World!")

Expressions

Describe how all forms of expressions will be implemented.

  1. Describe how the value of constants (small and large integers, as well as text constants) will be handled.
  2. Describe how the address and value of scalar variables will be handled.
  3. Describe how subscripting array elements will be handled. Given an example of both a 1D and a 2D case.
  4. Describe how each of the arithmetic operators will be implemented: +, -, *, /
  5. Describe how the relational operators will be implemented: <, <=, >, >=
  6. Describe how the equality/inequality operators will be implemented: =, !=
  7. Describe how the Boolean operators will be implemented such that they short circuit when necessary: not, and, or
  8. Describe how the Python-style ternary conditional operator will be implemented.

Functions and Procedures

  1. Describe the layout of the activation record for functions and procedures.
  2. Describe the routine prologue (entrance): activation record setup, display modification, allocation for local storage, etc.
  3. Describe the routine epilogue (exit): handling of cleanup, display restoration, return values, return jump
  4. Describe how you will implement parameter passing.
  5. Describe how you will implement a function call that yields a function return value.
  6. Describe how you will implement a procedure call.
  7. Describe your strategy for managing the display.

Hint: it is recommended that you keep the operation of procedures and functions as similar as possible, even if it wastes a small amount of memory at runtime.

Example sum.mas

Manually write the complete and functional assembly code corresponding to the following Source language program. Your program should faithfully implement the descriptions you provided above.

    func sum(x, y integer) integer {
        var sum integer

        sum = x + y
        print sum, newline

        return (sum)
    }

    print sum(44, 444), newline

Statements

Describe the code that should be generated for each of the following statement constructs.

  1. Assignment statement
  2. if statements
  3. while and repeat...until loops
  4. break statements
  5. Both kinds of return statements
  6. print and input statements
  7. Handling of minor scopes

Everything else

  1. Main program initialization
  2. Any handling of scopes not described above
  3. Any other information you think is important to include

A Suggested Strategy

Suggested by Peter Goodman, CSC488S TA, Winter 2013/2014.

  1. Each group member should independently review the entire document, ideally once or twice with a break in between reviews. This will help detect blatant contradictions / inconsistencies across the sections of the document. It's much better to discover these problems before submitting the document for marking.
  2. A good Rule of Thumb would be If everyone understands and agrees on all parts of the document then it is ready to submit. If anyone doesn't understand any part of the document then either there is a communication problem, a mistake, or the person doesn't understand the machine model.
  3. Be explicit about everything! Examples: order of operations/argument evaluation, What happens during function call (e.g. is it the caller or the callee of a function that is responsible for argument evaluation, activation record allocation/deallocation, etc.)

Starter code package

Within your private team repository on GitHub, a a4starter branch has been pushed. Merge that branch into your master branch and follow the Getting started instructions in a4/README.md. There is no new Python code to write for this assignment, but you will need to use the mas tool, and you may find the tests in csc488/machine/tests/ to be educational in terms of understanding the Machine architecture.

How to submit

Add your collection of .mas files under a4/docs/.

Modify a4/README.md by adding the following: