CS 432

P5: 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 do this conversion, you will write visitor methods that generate code for each AST node. I recommend doing this using the "code" and "reg" attributes to store the generated code and any temporary result register, respectively, as we discussed in class. I have provided many helper functions in ILOCGenerator to aid in writing these methods.

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 as well as the size of local variables for functions (necessary for prologue emission). 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. In addition, the reference compiler re-numbers registers and labels sequentially in between P5 and P6. Thus, your generated output will likely not exactly match the sample output below, and that is fine. I will primarily be testing your emitted code for correctness. You must also abide by the standard calling conventions as described in the language reference and as discussed in class.

Notes:

• You can ignore the PHI instruction--it's for data flow analysis in static single-assignment form, which we will not be doing in this project.
• 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.
• Recursive functions will not work properly at this point in the project because we're re-using virtual registers across function invocations. We'll fix this in P6 by spilling registers at call sites so it's ok for now.

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:
  push bp                               // prologue
  i2i sp => bp
  addI sp, 0 => sp                      // allocate space for local variables (0 bytes)
  loadAI [bp+8] => r1 {x}
  loadAI [bp+12] => r2 {y}
  add r1, r2 => r3
  i2i r3 => ret
  jump l1                               // return (x+y)
l1:
  i2i bp => sp                          // epilogue
  pop bp
  return

main:
  push bp                               // prologue
  i2i sp => bp
  addI sp, -4 => sp                     // allocate space for local variables (4 bytes)
  loadI 3 => r4
  storeAI r4 => [bp-4] {a}              // a = 3
  loadAI [bp-4] => r5 {a}
  loadI 2 => r6
  push r6
  push r5
  call add
  addI sp, 8 => sp                      // de-allocate space for parameters (8 bytes)
  i2i ret => r7
  i2i r7 => ret
  jump l2                               // return add(a, 2)
l2:
  i2i bp => sp                          // epilogue
  pop bp
  return

Result: 5

Submission

Please submit your MyILOCGenerator.java file to the appropriate assignment on Canvas by the due date indicated there.

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 midnight a week following the original project due date.

Grading

Here is the grading breakdown for this project: