Problem Set 4: Building a Back-End for Cish

Due Monday, 19 October 2009, 11:00am.

The goal of this problem set is to understand how procedures (functions) are implemented for C-like languages. To that end, you will compile a language called Cish down to MIPS code. Cish is just like ps3's Fish, except that it adds functions, function calls, and local variables.

You can find details about the MIPS calling convention for procedures in both the lecture notes and the SPIM manual.

Instructions

Create a directory ps4. Download the cish.zip zip file and unzip it within the ps4 directory. You should find a directory cish that contains all of the files that you will need for this assignment. You will be modifying the file compile.sml.

A Cish program is a list of functions. Each function is of the form

  var(var1,...,varn) { stmt_list }

mimicking functions in C, except that we don't have any types. Here, var is the name of the function and var1,...,varn are the formal parameters of the function. The stmt_list is a list of statements which should return a word-sized value to the caller. The distinguished function main is used to launch the program. For Cish, main should take no arguments.

To statements, we have added a new form:

   stmt ::= ... | let var = exp; stmt

The intention is that this evaluates the expression exp, then declares a new, locally-scoped variable var, and assigns the value of exp to var as its initial value. The scope of var extends across the adjacent statement, and becomes unavailable outside.

To expressions, we have added a new form var(exp1,...,expn) which represents a function call. Here, var is the name of the function and exp1,...,expn are the actual argument expressions.

I've provided the abstract syntax, lexer, parser, and updated interpreter. You have to provide the compiler. You'll want to follow the MIPS standard calling convention (see the MIPS manual and lecture notes for details) except that you do not need to worry about keeping the stack-pointer double-word aligned. In particular, when calling a function, make sure to save any caller-saves registers that you need preserved across the call, and within a function, make sure to save any caller-saves registers used by the function.

Strategies:

A simple strategy for compilation is to keep an environment around that maps variables (including formal parameters and local variables) to integer offsets relative to the frame-pointer. One option is to make a pass over the code and determine how many distinct variables and where they will live before compiling the code. After this pass, you will be able to generate the prologue and epilogue. Another strategy is to "push" locally-defined variables on the stack and "pop" them off as you encounter them. Regardless, you'll need to keep track of where each variable lives relative to either the stack or the frame pointer.

I would suggest pushing temporary values on the stack and popping them off instead of trying to do something fancier (as sketched in the class notes.) Get this working first before you move on to something more sophisticated!

Testing Your Code:

The file test.cish contains a sample program but you can find more here (again, thanks to Chris Jeris.)

Finally, to help in debugging, you can insert code to call the functions assembly language functions printInt, printSpace, and printNewline. The code for these functions can be found in the file print.asm but is automatically appended to the end of the MIPS code that you generate.

Submitting your work

Please use the CS153 submission script provided on the nice servers at ~lib153/bin/cs153submit. For each assignment, you should create a new subdirectory to hold all of the supplied files along with any file you create. When you have complete the assignment, submit your work with the following command:

# ~lib153/bin/cs153submit N dir

where N is the assignment number, and dir the the directory containing the files for the assignment. For example, if you are using a directory called ps4 for this assignment, you can submit your work with the command.

# ~lib153/bin/cs153submit 4 ps4

You can submit your work as many times as you like. Only the last submission will be graded. You can view your current submission using the submit command:

submit ls lib153 4: Show the time-stamp and size of your last submission for assignment 4.
submit contents lib153 4: Show the contents of your last submission for assignment 4.

For more information, see man submit on the nice servers.