Resources

Problem Set 3: Building a Back-End for Cish

Due Wednesday, 20 Feb 2013, 11:59pm

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 ps2'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

Download the assignment zip file. You will find all of the files needed for this assignment in your directory.

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

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

To statements, we have added a new form:

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

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