PA5: Decaf ILOC Generator
Objective
The goal of our semester-long project is to gain experience in compiler implementation by constructing a simple compiler.
The goal of this part of the project is to gain experience implementing code generation by converting Decaf ASTs into a linear code (ILOC).
Introduction
The semester-long project for this course is to build a compiler for the Decaf language. In this project, you will implement code generation for Decaf, which will be the fourth phase in our compiler. You will do this by traversing the annotated AST from the fourth phase, generating equivalent ILOC code.
You should download the project starter files from the "Files" tab in Canvas. The starter files include many new .java files as well as .class files representing compiled solutions.
Before you begin writing code, you should spend some time reading through all of the infrastructure files provided in the starter files. Our compiler this semester is a large project. Your solution will need to interface with several other classes, and you will need to thoroughly read through those classes to understand their interactions. Also, there are utility functions that you may find useful.
If you have questions about the existing code, please ask them on the Piazza forum (see the link on the sidebar in Canvas).
For this project, you will be implementing MyILOCGenerator
, a
subclass of the ILOCGenerator
. These classes handle the conversion
from an annotated ASTProgram
to sequential ILOC code in an
ILOCProgram
structure.
To help you test your code generation, I wrote a simple ILOC interpreter,
which you can find in the ILOCInterpreter
class. Its implementation
may be of interest to you as you write your code generator. You can also use the
interpreter to test your ILOC output, and I have added a final pass to
DecafCompiler
that invokes the interpreter on your generated ILOC
code.
It may also help to turn on tracing in the interpreter, which will print out
the system state after each instruction. To enable this, find the following
line in DecafCompiler
:
ILOCInterpreter interp = new ILOCInterpreter();
Change it to the following:
ILOCInterpreter interp = new ILOCInterpreter(true);
Assignment
WARNING: You should only proceed with actual development once you are SURE you understand exactly what your task is and how your code should interact with the rest of the system.
For this particular project, you should pay special attention to the following classes:
ILOCGenerator
- Base class for ILOC code generators.ILOCProgram
- Collection of ILOC functions.ILOCFunction
- Collection of ILOC instructions.ILOCInstruction
- Single ILOC instruction.ILOCOperand
- Single ILOC operand. This class also handles generation of temporary registers and anonymous labels.ILOCInterpreter
- Interprets ("executes") an ILOC program.AllocateSymbols
- AST traversal that calculates static coordinates and runtime locations for all symbols. This pass must be completed before code generation.
Implement the MyILOCGenerator
class. This project is by design
more open-ended than any of the previous projects in this course. There are
infinitely many ILOC programs that are equivalent to any given Decaf program.
Some are more efficient, some are easier to analyze, some are easier to read.
Thus, your generated output may not exactly match the sample output below, and
that is fine. I will be testing your emitted code for correctness (the majority
of your grade), efficiency, and readability.
NOTE: You can ignore the PHI instruction--it's for static single-assignment form, which we will not be using explicitly in this project.
NOTE: You can also ignore the ILOCBasicBlock
class--it's for
building and analyzing control flow graphs, which we will not be using in this
project.
Sample Input
def int add(int x, int y) { return x + y; } def int main() { int a; a = 3; return add(a, 2); }
Sample Output
add: loadAI [bp+8] => r1 loadAI [bp+12] => r2 add r1, r2 => r3 i2i r3 => ret jump l1 // return (x+y) l1: return main: loadI 3 => r4 storeAI r4 => [bp-4] // a = 3 loadAI [bp-4] => r5 loadI 2 => r6 param r6 param r5 call add i2i ret => r7 i2i r7 => ret jump l2 // return add(a, 2) l2: return Result: 5
Reflection
One of the goals of this course is to encourage introspection and thoughtful, deliberate development processes. For this project, you will compose a short (2-3 paragraphs) reflection, answering any (or all) of the following questions as appropriate:
- How does this project fit into the overall picture of our semester-long compiler project? Why is it important?
- Describe your design and development process. Did you use a formal software development method?
- What aspects of this project proved to be the most rewarding?
- What aspects of this project proved to be the most challenging? How did you overcome these challenges?
- How do you know your submission is correct? Briefly describe your testing regimen.
- If you had to start the project again from scratch, what would you do differently?
- What concepts from our theoretical class material or techniques from our classroom activities did you apply in this project?
- Suppose you weren’t using any of the concepts or techniques we’ve covered in class this semester; how would your solution to this project be different?
- What other areas of computer science (or CS courses you’ve taken) impacted your solution to this project?
- Do you have any other feedback about this project?
Include as much detail as you can, but do not ramble. Concise answers are preferred over verbose ones. Your reflection will be graded on a five-point scale:
Insightful | 5 |
4 | |
Superficial | 3 |
2 | |
Deficient | 1 |
No submission | 0 |
Submission
DUE DATE: Friday, November 17, 23:59 EDT (11:59PM)
Please submit your MyILOCGenerator.java
file and your reflection
to the appropriate assignments on Canvas.
Code Reviews
One of the goals of this course is to encourage good software development practices, especially when building a large software system (such as a compiler). For this project, you will be assigned two other random students in the course. You must review their code and offer constructive feedback according to the given rubric.
Submit your review on Canvas by Friday, December 1. Please submit your review as a comment (not an attached file).
Grading
Here is the grading breakdown for this project:
Automated tests | 80 |
Instructor review | 5 |
Reflection paper | 5 |
Peer review | 10 |
TOTAL | 100 |