Lecture Notes


CS4410/6410: Compilers
Spring 2013

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.


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


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

When you have completed the assignment, zip up your ps3 directory as ps3-lastname1-lastname2and email it to 4410staff at ccs.neu.edu.