Cish to MIPS Compiler

Your job for this assignment is to implement a compiler that maps Cish source code down to MIPS assembly. Cish is quite similar to Fish except that it adds functions, function calls, and local variables. You will fill in missing code in compile.ml and then submit by uploading this file to gradescope.

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

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

mimicking functions in C. Here, var is the name of the function and var1,...,varn are the formal parameters of the functions. The { stmt_list } is a statement which should return an integer 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 variables 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.

NOTE: The starter code also automatically emits assembly code for a helper function called printInt that takes an integer as an argument and prints it using a system call that is supported by the Spim emulator. You can think of this as a very simple "standard library" function for Cish. The rest of the compiler code you write therefore does not have to generate any more code to implement this function, but your compiler should support calls to this function much like a call to any other function. You can use printInt to help test and debug your compiler. Take a look at the example test/print_01ceper_01add.cish.

I've provided the abstract syntax, lexer, parser, and updated interpreter. You have to provide the compiler. You'll ideally want to follow the MIPS standard calling convention (see the MIPS manual and the discussion in the lecture slides) 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. That said, our testing code will NOT check directly whether you follow a particular calling convention -- but whatever calling convention you end up implementing ought to at least be consistent and also support calling printInt.

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 experimenting with something more sophisticated!

Getting Started

Running make in the current directory generates an exectuable ps4, which expects a file to compile, i.e. running

./ps4 tests/01cexpr_01add.cish

will emit the resulting assembly code. You can then save this to a file and run it with spim as you did for ps3.

NOTE: unlike the tests for ps3, the emitted assembly code will NOT by default print out the return value of main. Instead, add calls to printInt if you want to print some output for testing.