Code Generation

Assignment 5
CPTR 415 Compiler Construction

Overview

In this assignment you will implement a code generator that generates MIPS assembly language for a Decaf program. The assembly code your compiler generates will be run on the SPIM simulator. SPIM simulates the MIPS machine architecture.

Issues

Strategy. You should use the code generation techniques discussed in class and in the dragon book to generate the MIPS assembly code for Decaf programs. The SPIM handout describes the MIPS assembly instructions and architecture. You will only need to use a subset of the MIPS instruction set.
In addition to generating assembly code for a Decaf program, your compiler is also responsible for generating assembly code that creates a runtime environment for the Decaf program. This runtime environment includes:
- Program initialization. When a program starts its execution, it is necessary for the runtime environment to create an instance of the class that contains main() and invoke that object's main() method. (Note that in Java, unlike in Decaf, main() is a static method so it is not necessary to create an object to make a working program.)
- Memory allocation. A MIPS assembly language routine is available to manage the heap and allocate memory. You should incorporate this _malloc subroutine into your generated code and use it when memory must be allocated for objects (i.e., via new).
- Null reference accesses. Your compiler needs to generate code that ensures that a Decaf program does not try to reference an instance variable or method of a variable that is a null reference. For example, if w is declared to be of type Widget and w has not yet been initialized, then the reference w.a is invalid. Consequently, if your compiler cannot prove that a variable will have a non-null reference when one of its fields is accessed, your compiler must generate assembly code that checks for a null reference at runtime and prints an appropriate error message if one is encountered. It is appropriate for a Decaf program to terminate if this condition is detected.
- Array bounds checking. In Decaf, as in Java, all array accesses are checked to make sure the index does not attempt to access a location outside the array's bounds. Your compiler must generate assembly code that checks for out-of-bounds references at runtime and prints an appropriate error message if one is encountered. It is appropriate for a Decaf program to terminate if this condition is detected.
- Division by zero. Your compiler should generate assembly code that detects and reports division by zero. It is appropriate for a Decaf program to terminate if this condition is detected.
- Variable initialization. Recall that integer variables are to be initialized to zero and that reference variables (i.e., object and array variables) are to be initialized to null. Consequently, your compiler should generate assembly code to perform these initializations.
Decaf Details. Most questions about Decaf behavior such as how the operators work can be answered by consulting the original Decaf language specification. You should be very familiar with this specification and follow it carefully as you generate code. The semantics of parameter passing is not addressed in that document. Decaf uses call-by-value, just like Java. This means the contents of integer variables and reference variables are both copied. Note that the reference for a reference variable is copied, not the object itself. Consequently, it is possible for a method to modify the contents of an array or object parameter. This should not be surprising, as Java's parameter passing mechanism works the same way.

Format of Output

If a Decaf program contains no errors, your Decaf compiler should place the compiled program in a file named a.out; otherwise, it should generate an appropriate set of error messages.

When the a.out file is run in the SPIM simulator, the output should consist of

the output generated by the print statements, and
an error message if a runtime error is detected.

Compiled Decaf programs should not crash. Instead, they should exit gracefully with an error message. If you are unable to fully implement the assignment, then your compiler should not generate the a.out file and a message should be printed indicating that the feature is unimplemented. Please do not allow your compiler to produce segmentation faults!

Assignment Submission and Grading

You should do all your developement within a single directory. When you are ready to submit the assignment, copy the contents of this directory to a new directory named DECAF_COMPILER_FINAL under your home directory. Provide a make file so that I need only run make to build your compiler. Everything should be present in that directory to build a working compiler. The executable should be named decafc. It should be possible to execute this program on a Decaf source file using the command

decafc < filename

Include a file named README describing any limitations of your compiler. It is better to say a feature is not implemented than to have it fail while testing. Decaf programs that exercise a documented unimplemented feature of your compiler will be avoided while testing your compiler.

Your compiler will be tested against a variety of test files.

Points will be awarded based on the level of functionality exhibited by your compiler. The levels are described below.

Level 1. Your compiler correctly generates MIPS assembly code for all Decaf programs that
- contain only one class
- contain only one method (main())
- have no instance variables
- have no local variables
- uses only the print statement to display integer literals, and no more than one parameter is passed to print
Programs of this type are considered the lowest level of reasonably functioning Decaf programs. For example,
```
		class MyMain {
		    void main() {
		        print(2);    //  Prints 2 followed by a space
		        print(-45);  //  Prints -45 followed by a space
		        print();     //  Prints a newline
		    }
		}
		
```
At this level you need not worry about parameter passing, argument lists, significant stack management (parameters, locals, return address), objects, expressions, and control flow statements. Eventually you must be able to use argument lists with print, but here you'll find it easy to pass a single argument to print without using the stack.
Level 2. Your compiler correctly generates MIPS assembly code for all legal Level 1 Decaf programs and supports local variables, assignment statements and arithmetic expressions. Programs at this level are more sophisticated but still fairly simple. For example,
```
		class MyMain {
		    void main() {
		        int x;
			int y;

			x = 10;
			y = 2;
			print((x - 2) * 2);
			print(x + y);
		    }
		}
		
```
At this level you'll need to address stack mangement (for local variables and temporaries) and deal with arithmetic expressions.
Level 3. Your compiler correctly generates MIPS assembly code for all legal Level 2 Decaf programs and supports multiple methods and method calls. print can now accept multiple arguments. For example,
```
		class MyMain {
		    int f(int i) { return i + 4; }
		    void g(int a, int b) {
			int x;
			x = 2;
			print(x + a);
		    }
		    void main() {
		        int x;
			int y;

			x = 10;
			y = 2;
			print((x - 2) * 2, 3, x + 2);
			print(x + y);
			x = f(x + y);
			g(y - 7, 2);
			g(f(4) - f(x), x + 10);
		    }
		}
		
```
At this level you'll need to enhance your stack mangement to include method return addresses, return values, and parameters. Your program may have more than one stack frame active at any given time.
Levels 4-7. See table below.

The possible number of points for this assignment is 10. Points are based upon the highest level achieved:

Level 1	See above	3
Level 2	See above	5
Level 3	See above	6
Level 4	All the Level 3 stuff plus control statements `if, while` and relational operators	7
Level 5	All the Level 4 stuff plus multiple classes, multiple objects, and instance variables	8
Level 6	All the Level 5 stuff plus arrays	9
Level 7	Generates executable MIPS assembly code for all correct Decaf programs	10

Important! Even if you have implemented portions of functionality at higher levels, your grade is based on the highest level achieved with complete functionality at that level. Complete functionality at a given level requires complete functionality of all levels below that level.