Programming Assignment 7
Due Thursday, May 8

Introduction

In this assignment you will implement code generation for Cool. This assignment is the end of the line: when completed, you will have a fully functional Cool compiler.

The code generator makes use of the AST constructed in PA3, the static analysis performed in PA4 and PA5 and the global structures created in PA6. Your code generator should produce MIPS assembly code that faithfully implements any (statically) correct Cool program. This assignment is one of the most difficult in the course, but you should be familiar with the AST structure used, especially from PA4. Do not delay starting this assignment.

Files and Directories

To get the assignment type

make -f /afs/cs/users/classes/cs654/assignments/PA7/Makefile

in a directory named PA7. This command copies a number of files to your directory, some of them with read-only permission. As usual, you should not modify files that are read-only. Please read and follow the directions in the README file.

The files that you may need to modify are:

• cgen.cc This file will contain your code generator.

  You are given the same skeleton files as for PA6. Therefore, you should use the cgen.cc, cgen.h, and cool-tree.h files you wrote for PA6. Copy these files from your PA6 directory into your PA7 directory. When your PA7 is graded, you will get credit for those things you fixed in your PA6 (up to a maximum of 100%).

• cgen.h This file is the header for the code generator. You may add anything you like to this file. It provides classes to help in code generation. You may replace or modify them as you wish.

• cool-tree.h As usual, this file contains the definitions of classes for AST nodes. You can add field and method declarations to the classes in cool-tree.h. Put the definitions of the methods in cgen.cc; cool-tree.cc should not be modified. NB: these files do not contain the data members and member functions needed only by the static analysis phase, since these two phases will not be linked together. If you wish to create a single executable for your compiler after this semester, you will need to merge these files with the ones from PA4 and PA5.

• example.cl This file should contain a test program of your own design. The file should test every feature of the code generator. It does not need to test the creation of the global tables per se, but should test anything that could go wrong in code generation for methods.

  Unlike previous assignments, the resulting program should be executable. The output of running the program should be changed if the code generator has a mistake in it. The program may accept one integer (between 0 and 10) as input during the run, to allow it to test various termination conditions. Part of the grading will involving checking that your program detects errors in each of the buggy code generators that will be provided. You must test every kind of expression in Cool, but you are not required to debug complicated optimizing compilers. We have provided commands buggy-cgen-coolc and check-buggy-cgen that can help to check your test suite. The bug numbers and number of bugs may change from time to time.

• README This file will contain the write-up for your assignment. It is critical that you explain design decisions, how your code is structured, and why you believe your design is a good one (i.e., why it leads to a correct and robust program). It is part of the assignment to explain things in text as well as to comment your code.

In addition you are given read-only access to the following files:

• emit.h This file contains code generation macros.

There will be many other files in your directory containing other pieces of the compiler. These files were described in previous handouts and are listed in the README file. The files we will collect and use to grade your assignment are the first set listed above; you should not modify any other files.

Designing and Testing the Code Generator

You will need a working lexer, parser, and semantic analyzer to test your code generator. See the README file for instructions on how to use either your own components or the components from coolc. It is wise to test your code generator with the coolc lexer, parser, and semantic analyzer at least once, because we will grade your code generator using coolc's version.

See the README file for instructions for compiling and running a compiler with your code generator. For your convenience, a command line debugging flag -c is included in the skeleton, which controls the global variable cgen_debug.

There are a number of things you must keep in mind while designing your code generator. First, your code generator must work correctly with the Cool runtime system, which is explained in the Cool Tour handout. Second, you should have a clear picture of the runtime semantics of Cool programs. The semantics are described informally in the first part of the CoolAid, and a precise description of how Cool programs should behave is given in Section 13 of the manual. Third, you should understand the MIPS instruction set. An overview of MIPS operations is given in the spim documentation, which is on the class Web page.

Code Generator Interface

The semantic analyzer decorates the AST with information that will be useful to you while writing the code generator. The following table summarizes this information:

constructor or phylum	attribute	meaning
program	obj_class	AST for class Object
	int_class	AST for class Integer
	str_class	AST for class String
	bool_class	AST for class Boolean
class	super	AST for super class (or NULL for Object)
method	overrides	AST of method being overridden (or NULL)
	return_of_class	AST for class of return type
attr	of_class	AST for class of type
formal	of_class	AST for class of type
branch	of_class	AST for class of type of branch variable
	type	symbol for type of value of expression in branch
Expression	type	symbol for type of value of expression (or NoType)
let	of_class	AST for class of type of let variable
object	binding	description of variable being used
assign	binding	description of variable being assigned
dispatch	method	AST for (statically selected) method
static_dispatch	method	AST for method selected
new_	of_class	AST for class being instantiated.

Optimization

In a word: don't. For CompSci 654, we do no optimization. Optimization is a fascinating topic, but with many traps for the unwary. If you are interested in optimization, take an independent study course, or take CompSci 854. Do not attempt optimization for PA7. Instead, use the time writing exhaustive test cases and ensuring your code generator is completely correct. You may even wish to work on other classes!

Garbage Collection

The standard Cool compiler works with garbage collection. Your compiler need not work with garbage collection. If you decide to use the collector, be sure to carefully review the garbage collection interface described in the Cool Tour. Ensuring that your code generator correctly works with the garbage collector in all circumstances is not trivial.

Spim and XSpim

You will find spim and xspim useful for debugging your generated code. xspim works like spim in that it lets you run MIPS assembly programs. However, it has many features that allow you to look at the memory, registers, data segment, and code segment of the code. You can also set breakpoints and single step your program. Look at the documentation for spim/xspim on the class home page.

Warning: One thing that makes debugging with spim difficult is that spim is an interpreter for assembly code and not a true assembler. If your code or data definitions refer to undefined labels, the error shows up only if the executing code actually refers to such a label. Moreover, an error is reported only for undefined labels that appear in the code section of your program. If you have constant data definitions that refer to undefined labels, spim won't tell you anything. It will just assume the value 0 for such undefined labels.

Overview

The basic stages of the code generator for this assignment are as follows:

1. Compute the number of temporaries for a method, and assign temporaries where they are needed.
2. Write the function prologue and epilogue code generators
3. Generate code for each method.

Your test case example.cl should also test all aspects of the code generation.