CSE 304/504: Compiler Design
Spring 2016
Homework #6, Final Code Generation
Due: May 9
Contents
In this assignment, you will complete your Decaf compiler by generating MIPS
assembly code. For this assignment, you may assume that your
input Decaf program is syntactically and semantically valid.
As in the past, you will produce a compiler that
will take a single command-line argument, which is a
file name; if that file contains a
syntactically valid Decaf program, then it will
construct an AST, perform type checking with name resolution, and
intermediate code generation. Finally, (and the main step of this
assignment) the compiler will generate final machine code for
MIPS. It will output the machine code as a .asm file
with the same name as the input Decaf file. For
instance, if your compiler were invoked with foo.decaf,
it should produce foo.asm.
Main Method:
This assignment will introduce an important
assumption: that a program in foo.decaf has a class
called foo, which has a public, static, void method
called main (that has no parameters).
The main() method will form the entry point to your entire
program.
You may assume that every program used with your compiler will satisfy
the above requirement, and you do not have to explicitly check for this.
On output, the code for the main method must have as a label
"main_entry_point" at its entry point. This is to make
sure that we know where to start your program execution from.
In and Out:
For the purposes of this assignment, assume that the input decaf
programs do not use the input and output methods in In and
Out. Again, you do not have to check to see if the program
satisfies this assumption.
CSE 504 vs CSE 304
- CSE 504 students are expected to generate code for the entire
Decaf language.
- CSE 304 students are expected to generate code for the a subset of
Decaf, the same subset used in prior homeworks. It is
the whole language except the following:
- Arrays: there are no arrays in the CSE 304 subset.
- Implicit field accesses: all field accesses in the CSE 304
subset will specify the object explicitly.
- Implicit method calls: all method calls in the CSE 304
subset will specify the object explicitly.
- No overloaded methods/constructors:
Assume that in each class, there is at most one constructor, and
at most one method with a given name. Also assume that names of
methods defined in a class are distinct from method names in its
super classes. You do not need to check for these
constraints. Your type checker can safely assume these are
true!.
Available Material
MIPS and SPIM
MIPS has been used for over 25 years in undergraduate Computer
Organization and Assembly Language Programming courses. So it also
has tons of very good reference material.
- The first stop should be http://spimsimulator.sourceforge.net/,
SPIM's pages on SourceForge. You can download SPIM from there, and
has links to very useful documents on SPIM and MIPS.
- I found a very nicely written guide to Assembly Language
Programming using MIPS, by Daniel Ellard. This (old is
gold) tutorial is here.
- Offline Resource: Britton, MIPS Assembly Language Programming, Prentice Hall, 2004.
(ISBN 0-13-14204405, 978-0131420441) is a textbook used in CSE
220.
- Start with building control flow graphs for each function in the intermediate
code.
- Convert the graphs into SSA form.
- For each function, generate final code by
- Mapping temporary registers of the register abstract machine
to MIPS registers.
- Translating abstract machine instructions to MIPS
instructions.
- Go through MIPS emulator SPIM. (You may use MARS if you are
more familiar with it, but my personal recommendation is to use
SPIM).
- First generate code for programs that do not access objects
and have no dynamic memory allocation (halloc).
- Implement halloc using features of the emulator.
- Specify .data layout to implement the static area
and heap in MIPS.
- Output final code to a .asm file that can be
immediately executed in the emulator.
-
Proceed by adding field accesses first, and finally method
invocations and constructors.
-
For CSE 504 students only: work on conversion to SSA form after
all else is completed.
Your Decaf compiler should be organized into clearly labeled
files with each files function stated in a Readme file. The top-level
will be in decafc.py, a file containing the main
python function that ties the modules together, takes command line
argument of input file name, and processes the Decaf
program in that file.
decafc takes a single command line argument, with the name
of the Decaf program to be translated. For example, if the Decaf
program is in fum.decaf, then the invocation will be as
python decafc.py fum
or python decafc.py fum.decaf
The translated MIPS program will be written to a file with
the same base name with ".asm" extension (fum.asm
in the above example).
This maximum score on this assignment will be
40, divided as follows:
20 points for register allocation without spilling, and no method
calls. This involves correct construction of register interference
graph, which in turn needs correct computation of liveness
information;
10 points for correct issue of MIPS instructions;
5 points for correct handling of method calls and parameter passing.
5 points for correct handling of heap access and allocation. In
addition, 5 points for SSA form originally allocated for hw5 may be
earned here. Make sure you specify this clearly in Readme.
As usual, complicated programs may not get the full grade unless
accompanied by comments documenting it.
Submit your homework using Git, as done for HW1,
before midnight of the posted deadline.
You may submit the homework multiple times; the last submission
will be graded.
- Mon May 2 14:40:13 EDT 2016: "Project path" had
spurious instructions left over from HW5. They've since been
struck off.
- Fri Apr 30 22:44:38 EDT 2016: Original version.
C. R. Ramakrishnan
Last modified: Mon May 2 14:41:10 EDT 2016