Compiler from Java to MIPS

in Four Nifty Steps

HundredHourWood



Course Info

CS 179E: Project in Computer Science (Compilers)
Class discussions: Time: Mon, 9:10-10am, Place: Surge 173
Professor: Mohsen Lesani (lesani AT cs.ucr.edu).
Professor office hours: Monday 10-11am
Labs: Time: Thursdays at 9-12pm, Place: Chung 129
Teaching assistant: Saheli Ghosh (sghos006 AT ucr.edu) 
TA Office hours: Wednesday 11am-12pm
Discussions: Piazza
Prerequisites:  CS 100 and CS 152 with grades of C or better; ENGR 180W; 8 additional upper­division units in Computer Science
Units:  4
Suggested book: Andrew Appel with Jens Palsberg, Modern Compiler Implementation in Java, 2nd edition. Cambridge University Press, 2002.

The goal of the course is to design and implement the main phases of a modern compiler. The project consists of four phases. In these phases, you will be converting a subset of the Java language called MiniJava to simpler languages and eventually to complete MIPS machine code. The phases can be combined into a MiniJava-to-MIPS compiler.

This project was first designed and implemented by Jens Palsberg's group. It is adopted and extended by Mohsen Lesani.

Evaluation:
    Class participation is mandatory.
    This course requires four essays to comply with ABET.
    Submissions:
         Week 1: April 9
              None
         Week 2: April 16
              None
         Week 3: April 23
              Essay 1: (1) Analyzing the local and global impact of computing on
                         individuals, organizations, and society and (2) Recognition of
                         the need for and an ability to engage in continuing professional
                         development, 5%
              Essay 2: Professional, ethical, legal, security and social issues and
                         responsibilities, 5%
         Week 4: April 30
              Project Phase 1: Code and Document, 25%
         Week 5:  May 7
              Essay 3: Effective communication with a range of audiences, 5%         
         Week 6: May 14
              None
         Week 7: May 21
              Project Phase 2: Code and Document, 25%
         Week 8: May 28
              None
         Week 9: May 4
              Essay 4: Effective functioning in teams to accomplish a common goal
         Week 10: May 11
            Project Phase 3: Code and Document, 25%
            Project Phase 4: Code and Document, Extra 25%
         Final week
            Presentation, 5%

         Note that the submission of each phase of the project should include a
         document with the following secitons: (1) requirements and specifications,
         (2) design, (3) testing and verification

    Academic Integrity:
         You may talk about the problem with fellow students, the TA, and the
         instructor, consult books, papers, published material or the Web. However,
         you must reference all the sources that helped you. You should write
         solutions in your own words and coding.


Phase 1: Type-checking

Introduction. MiniJava is a subset of java that includes the bare minimum of Java: integers, integer arrays, classes, subclasses, and printing integers to standard out. It does not permit any float types, strings, overloading and overriding methods, or any interfaces. It has a few other restrictions, but those are minor. Thus, the MiniJava statement System.out.println(...); can only print integers. The MiniJava expression e.length only applies to expressions of type int[].

A sample MiniJava program is Factorial.java. Download

class Factorial{
public static void main(String[] a){
System.out.println(new Fac().ComputeFac(10));
}
}

class Fac {
public int ComputeFac(int num){
int num_aux;
if (num < 1)
num_aux = 1;
else
num_aux = num * (this.ComputeFac(num-1));
return num_aux;
}
}

The goal of phase 1 is to write a type checker for MiniJava. Given a program, the type checker checks at compile time that type mismatch does not happen at run time. It either approves or rejects the program. The set of rules that the type checker checks are represented as a type system. You can consult the book chapter 5 on semantic analysis and the following MiniJava type system. Download

Dependencies

We need to have the following:
- JavaCC (Java Compiler Compiler) parser generator. Install javacc:
   $ sudo apt-get install javacc
  Given a context free grammer, JavaCC generates a parser.

- JTB (Java Tree Builder) jar file jtb.jar: Download
  JTB is a syntax tree builder to be used with JavaCC.  Given a JavaCC grammar file, it automatically generates syntax tree and visitor classes and an annotated JavaCC grammer to build syntax trees.

- MiniJava Grammer for JavaCC minijava.jj: Download
  The context free grammer of MiniJava that is input to JTB and JavaCC.
  Here is a more readable representation of the MiniJava grammar.

- Test cases Phase1Tests.tar.gz: Download
  The test cases that we test our type checker with.

Parser Generator

We must first create a parser for the MiniJava language and generate a set of syntax tree classes and visitor classes. To do this, complete the following steps.

   $ java -jar /path/to/jtb.jar /path/to/minijava.jj

   $ javacc jtb.out.jj

Once this is done, you will have a complete parser for MiniJava and a set of classes used for traversing the syntax tree. You will also have two different default visitors: DepthFirstVisitor and GJDepthFirst. You should extend these two visitors to type check a MiniJava program.

Submission

Your main file should be called Typecheck.java, and if P.java contains a program to be type checked, then:

java Typecheck < P.java

should print either Program type checked successfully or Type error.

Untar the following tarball and read the instructions in the ReadMe.txt file.
Your submission must work with the testing script when run on the department servers.  Make sure you test your final tarball before submitting.

Phase1Tester.tar.gz Download


Phase 2: Intermediate Code Generation

Introduction

In this phase, we translate programs in the MiniJava language to programs in the Vapor language. Vapor is a low level assembly-like language. Vapor programs are described as a set of functions and data segments. In contrast to architecutal assembly languages that support a finite number of registers, Vapor functions can use an unbounded number of variables. The main challenge in the translation from MiniJava to Vapor is mapping objects to memory and object-oriented method calls to function calls. Consult the book chapter 7 on Translation to Intermediate Code and chapter 14 on Object-Oriented Languages.

Dependencies

We need to have the following items. We had the first three in phase 1.

- JavaCC (Java Compiler Compiler) parser generator. Install javacc:
   $ sudo apt-get install javacc
  Given a context free grammer, JavaCC generates a parser.

- JTB (Java Tree Builder) jar file jtb.jar: Download
  JTB is a syntax tree builder to be used with JavaCC.  Given a JavaCC grammar file, it automatically generates syntax tree and visitor classes and an annotated JavaCC grammer to build syntax trees.

- MiniJava Grammer for JavaCC minijava.jj: Download
  The context free grammer of MiniJava that is input to JTB and JavaCC.
  Here is a more readable representation of the MiniJava grammar.

- Vapor Interpretor vapor.jar: Download

- Test cases
  Sample input programs Phase2Tests.tar.gz: Download
  Sample output programs Phase3Tests.tar.gz: Download

Vapor Language Specification

Vapor program is a list of functions and data segments. For example:

  const Table
    2
    3
    5
    7

   func LoadTableData(offset)
    addr = Add(:Table offset)
    ret addr

  func DoSomething(a b)
    PrintInt(a)
    addr = call :LoadTableData(b)
    val = [addr+4]
    ret val

Identifiers.
Identifiers are used for two things: variables and labels. Identifiers consist of a sequence of letters, digits, dots (., and underscores (_, but the first character cannot be a digit or a dot.

Variables are always local to a function; variable names must be unique within a function.

There are three types of labels: data labels, function labels and code labels. All label names must be unique across the entire program.

Data Segments.
Vapor has two types of global data segments. A const segment is for read-only data (like virtual function tables). A var segment is for global mutable data.

Each section starts with a data labels and is followed by static data values. For example:

  const MinutesPerHour
    60

  var MyClass.FunctionTable
    :MyClass.Start
    :MyClass.Finish
    -1

Each entry in a data segment is four bytes long. The entire first segment is four bytes long and contains the 2's complement representation of the number 60. It's a constant data segment and so memory write operations will fail at runtime.

The second segment is twelve byte long and consists of the address of the MyClass.Start function, followed by the address of the MyClass.Finish function, followed by the 2's complement representation of the number -1. This is a variable data segment and can be written to at runtime.

The two data labels, MinutesPerHour and MyClass.FunctionTable, can be used in other places in the program.

All values (integers and addresses) are four bytes long.

Functions.
The syntax for a function definition is:

  func FunctionLabel(params...)
    body...

Each line of the body of a function is one of:
- code label: Label:
- assignment: Location = Value
- branch: if Value goto CodeAddress
- goto: goto CodeAddress
- function call: call FunctionAddress (Args...)
- function return: ret Value
- call to built-in operation: OpName (Args...)

Assignment.
There are three distinct types of assignment. The first is variable assignment:

Var = Value
Here, Value is either an integer literal, a string literal, a variable name, or a label reference :Label.

For example:
a = 12              Store the integer literal 12 into variable a.
a = "abc"           Store the string abc into variable a.
a = sum             Copy the value in variable sum into variable a.
a = :Factorial      Store the address of the label Factorial into variable a.

For your homework, strings are only allowed as arguments to the Error built-in that we consider below.

The next two types of assignment are memory load and memory store. Memory operations always operate on 4-byte quantities and memory addresses must be 4-byte aligned.

  Var = MemoryReference
  MemoryReference = Value

A memory reference consists of a base address, which is either a label reference or a register, followed by an integer offset (either positive or negative).
[:MyArray+4] refers to the address 4 bytes past the MyArray label.
[x-4] refers to the address 4 bytes before the address stored in variable x.

Some memory load and store examples:
  x = [:FunctionTable+8]
  [:GlobalCounter] = 15
  [array-4] = length

Branch
There are two variants of the branch instruction:

  if Value goto :CodeLabel
  if0 Value goto :CodeLabel

The if jumps to CodeLabel if Value is non-zero and falls through to the next instruction otherwise. The if0 does the opposite, jumping to the specified label if Value is zero.

Goto
The goto instruction is an unconditional jump to the specified target.

  goto :CodeLabel

In addition to jumping to fixed labels, the goto instruction can also jump to a computed address read in from a variable.

  goto Var

For this phase, goto can only refer to code labels.

Function Call
Var = call :FunctionLabel (Args...)

The assignment Var = is optional. The arguements list Args... is a whitespace-separated list of value entries (either integer literals, variables, or label references). The return value of the function is stored in the Var variable.

Like goto, call can also use a function address loaded from a variable:

  Var = call Var (Args...)

Function Return
The ret instruction returns from a function. The return value is optional.

  ret Value
  ret

Built-In Operations
In addition to the core language, the Vapor interpreter also supports a set of built-in operations for  arithmetic, memory allocation, and displaying output.

Basic arithmetic: Add, Sub, Mul, Div, Rem, MulS, DivS, RemS, ShiftL, ShiftR, ShiftLA. The "-S" variants operate on signed integers.

  a = Add(a b)

Comparison: Eq, Ne, Lt, Le, LtS, LeS. The "-S" variants operate on signed integers.

Bitwise boolean operators: And, Or, Not.

HeapAlloc and HeapAllocZ take an integer — the number of bytes of memory to allocate — and returns the address of newly-allocated memory. The "-Z" variant also initalizes the memory to all zero.

  a = HeapAlloc(20)

Output: PrintInt and PrintIntS print out unsigned and signed integers, respectively. PrintString prints out strings. These do not return a value.

  PrintInt(13)
  s = "Hello"
  PrintString(s)

Error
is for abnormal program termination (for errors like null pointer deferences, etc). It takes a string message to display to the user.

DebugPrint is only for debugging. It accepts any number of values and prints out the interpreter's internal representation of the value. This can be useful for getting information about pointers.

Though the full specification defines many built-in operations, for your homework you are only allowed to use the following:

  • Basic Arithmetic: Add, Sub, MulS
  • Comparison: Eq, Lt, LtS
  • Displaying Output: PrintIntS
  • Memory Allocation: HeapAllocZ
  • Error: Error

Translator

Given a MiniJava program as input, the translator should output an equivalent Vapor program.

Consider the factorial MiniJava program. Factorial.java Download

class Factorial{
public static void main(String[] a){
System.out.println(new Fac().ComputeFac(10));
}
}

class Fac {
public int ComputeFac(int num){
int num_aux;
if (num < 1)
num_aux = 1;
else
num_aux = num * (this.ComputeFac(num-1));
return num_aux;
}
}
The translator should traslate it to a Vapor program like the following. Factorial.vapor Dowload

const vmt_Fac
  :Fac.ComputeFac

func Main()
  t.0 = HeapAllocZ(4)
  [t.0] = :vmt_Fac
  if t.0 goto :null1
  Error("null pointer")
  null1:
  t.1 = [t.0]
  t.1 = [t.1+0]
  t.2 = call t.1(t.0 10)
  PrintIntS(t.2)
  ret

func Fac.ComputeFac(this num)
  t.0 = LtS(num 1)
  if0 t.0 goto :if1_else
    num_aux = 1
    goto :if1_end
  if1_else:
    t.1 = [this]
    t.1 = [t.1+0]
    t.2 = Sub(num 1)
    t.3 = call t.1(this t.2)
    num_aux = MulS(num t.3)
  if1_end:
  ret num_aux

A Vapor program p.vapor can be run using the Vapor interpreter vapor.jar as follows:

  $ java -jar vapor.jar run p.vapor

Hints

During the translation, for each class, we construct the two objects class record and class v-table that keep information about the location of the fields and methods. These object are incrementally built at the beginning and used during the translation.

A class record maps field names to their offsets. Fields are assigned offsets in the order that they are visited. The class record of a subclass has a reference to the class record of the superclass and the offsets of the former start from the size of the latter. When a field access is translated to a memory operation, the class record is used to determine the offset of the object memory that the memory operation should access.

The class v-table maps method names of the class to their assigned offsets. The v-table of a subclass is a copy of the v-table of superclass that is extended for new methods of the subclass. It is also good to keep a list of method names in the order of their offset that is used when the v-table is written.

From type-checking, we get the classes in an order where every subclass comes after its superclass. The list is traversed in order and the class record and v-table for each class is created as extensions of those of its superclass.

Translation is done recursively using visitors. To generate the translation, a printer class is used where indentation can be increased and decreased on the entry and exit from scopes.

Identifiers can be declared with different types in different scopes. Thus, a symbol table that maps identifiers to types is kept during the translation. The type of an identifier is either class, method, field or local variable. The symbol table keeps a stack of scopes. For example at the beginning of a class, a new scope is pushed and the implicit field "this", the fields and the methods of the class are added to the scope. The main class is handled separately to generate the "Main()" function.

In the translation of each class, its v-table is translated to a const data segment.

In the translation of each (non-static) method, the implicit this parameters is explicitly added to the parameters of the translated function.

In the translation of statements, we create unique temporal variables using a sequence number. Similarly, we can generate unique labels.

In the translation of an identifier either in an expression or as the left hand side of an assignment, its type is retrieved from the symbol table. If it is a field, the class object for "this" can be retrieved from the symbol table, the class record can be retrieved from the class record and the index of the field can be retrieved from the class record. If the retrieved index of the field is i, the offset for the memory access is statically computed as i * 4 + 4. This is because, a word is four bytes and the first location of an object stores a reference to the v-table.

In the translation of an array access or assignment, the index is multiplied (using the MulS instruction) by 4 and then it is added (using the Add instruction) to the base address. This is because words are 4 bytes. Then, another 4 is added to it because the first word stores the size of the array. Note that before these instructions, the out of bound condition should be checked. The size of the array is read from the base address of the array and compared to the index. The array length instruction is simply translated to an access to the array base address.

      s = [b]   where b is the base address
      ok = Lt(i, s)   where is is the index
      if ok goto :l
      Error("Array index out of bounds")
   l: o = MulS(i 4)
      d = Add(b, o)
      r = [d+4]

In the translation of the if statement, we label the beginning of the else statement and the end and use the instruction if0 to goto to the else label if the condition fails. We goto to the end label at the end of the then statement. The while statement can be similarly translated by labeling the start and the end.

In the translation of a method call, if the value of the receiver is zero, a null pointer error is reported. The class and the v-table of the receiver object can be retrieved from the symbol table. The offset if the method can be retrieved from the v-table.
  
   vt = [rc]   where rc is the receiver
   f = [vt + d]   where d = o * 4,
                        o is the offset of the method retrieved from the v-table
   r = call f(rc arg1 arg2)

In the translation of an object allocation, the class object and then the class record can be retrieved from the symbol table. The allocation size is 4 times the record size plus 4. This is because a word is four bytes and the first word is used to store a reference to the v-table of the object.

   r = HeapAllocZ(s)   where s = rs * 4 + 4  and  rs is the record size
   [r] = :ClassVTableName

In the translation of array allocation, the size is multiplied (using the MulS instruction) by 4 and added (using the Add instruction) by 4. This is because a word is 4 bytes and the first word stores the array size. The resulting size is passed to the HeapAllocZ instruction.

The and expression can be translated to two if0 instructions that check if each of the operands is zero, assign zero to the result and goto the end label. Before the end label, one is assigned to the result. The not expression can be similarly translated.

Less than, addition, subtraction and multiplication operations are directly mapped to LtS, Add, Sub, and MulS instructions.
  
True and false literals are translated to 1 and 0 and integer literals are directly translated.

Submission

Your main file should be called J2V.java, and if P.java contains a syntactically correct MiniJava program, then

java J2V < P.java > P.vapor

creates a Vapor program P.vapor with the same behavior as P.java.

Untar the following tarball and read the instructions in the ReadMe.txt file. Your submission must work with the testing script when run on the department servers.  Make sure you test your final tarball before submitting.

Phase2Tester.tar.gz Download


Pahse 3: Register Allocation

Introduction

In this phase, we translate the Vapor language to the Vapor-M language. In contrast to Vapor that provides local variables, Vapor-M provides registers and stacks. The local variables should be mapped to registers and run-time stack elements. Consult the book chapter 6 on Activation Records, chapter 10 on Liveness Analaysis and the following paper on register allocation.

Massimiliano Poletto and Vivek Sarkar, Linear Scan Register Allocation, ACM TOPLAS 21(5):895-913, 1999.

Dependencies

We need to have the following items. We had the first item in phase 2.

- Vapor Interpretor vapor.jar: Download

- Vapor Parser vapor-parser.jar: Download
  The source code vapor-parser-source.tar.gz Download and
  the java doc vapor-parser-javadoc.tar.gz Download for this parser are also available.

- Test cases
  Sample input programs Phase3Tests.tar.gz: Download
  Sample output programs Phase4Tests.tar.gz: Download

Vapor-M Language Specification

A Vapor-M program is largely the same as a Vapor program except that instead of local variables, registers and stack memory are used.

Instead of local variables we have 23 registers: $s0..$s7, $t0..$t8, $a0..$a3, $v0, $v1.
Registers are global to all functions (whereas local variables were local to a function activation).
To follow MIPS calling conventions, we use the registers as follows:
$s0..$s7: general use callee-saved
$t0..$t8: general use caller-saved
$a0..$a3: reserved for argument passing
$v0: returning a result from a call
$v0, $v1: can also be used as temporary registers for loading values from the stack

The register $t9 is reserved for the next assignment.

Each function has three stack arrays called in, out, and locals. The in and out arrays are for passing arguments between functions. The in array refers to the out array of the caller. The local array is for function-local storage that can be used for spilled registers. The sizes of these arrays are declared at the top of every function (instead of a parameter list).

Each element of each array is a 4-byte word. The indexes into the array is the word-offset (not the byte offset). Array references can be used wherever memory references can be used. So in[1] refers to the second element of the in stack array.

func Run [in 2, out 0, local 4]
  $r1 = in[1]
  local[3] = $r1
  PrintString($r1)
  $v0 = 1
  ret

Translation

Consider the factorial Vapor program Factorial.vapor. Download

const vmt_Fac
  :Fac.ComputeFac

func Main()
  t.0 = HeapAllocZ(4)
  [t.0] = :vmt_Fac
  if t.0 goto :null1
  Error("null pointer")
  null1:
  t.1 = [t.0]
  t.1 = [t.1+0]
  t.2 = call t.1(t.0 10)
  PrintIntS(t.2)
  ret

func Fac.ComputeFac(this num)
  t.0 = LtS(num 1)
  if0 t.0 goto :if1_else
    num_aux = 1
    goto :if1_end
  if1_else:
    t.1 = [this]
    t.1 = [t.1+0]
    t.2 = Sub(num 1)
    t.3 = call t.1(this t.2)
    num_aux = MulS(num t.3)
  if1_end:
  ret num_aux

The translator should traslate it to a Vapor-M program like the following. Factorial.vaporm. Download

const vmt_Fac
  :Fac.ComputeFac

func Main [in 0, out 0, local 0]
  $t0 = HeapAllocZ(4)
  [$t0] = :vmt_Fac
  if $t0 goto :null1
  Error("null pointer")
null1:
  $t1 = [$t0]
  $t1 = [$t1]
  $a0 = $t0
  $a1 = 10
  call $t1
  $t1 = $v0
  PrintIntS($t1)
  ret

func Fac.ComputeFac [in 0, out 0, local 1]
  local[0] = $s0
  $t0 = $a0
  $s0 = $a1
  $t1 = LtS($s0 1)
  if0 $t1 goto :if1_else
  $t1 = 1
  goto :if1_end
if1_else:
  $t2 = [$t0]
  $t2 = [$t2]
  $t3 = Sub($s0 1)
  $a0 = $t0
  $a1 = $t3
  call $t2
  $t3 = $v0
  $t1 = MulS($s0 $t3)
if1_end:
  $v0 = $t1
  $s0 = local[0]
  ret

The jar file vapor-parser.jar includes both the parser and syntax tree classes for the Vapor language. Compile your program against it using the -classpath option. A Vapor program can be parsed to Vapor syntax tree using the Vapor parser vapor-parser.jar as follows. A Vapor program will never contain the following AST nodes: VVarRef.Register, VMemRef.Stack.

import cs132.util.ProblemException;
import cs132.vapor.parser.VaporParser;
import cs132.vapor.ast.VaporProgram;
import cs132.vapor.ast.VBuiltIn.Op;

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintStream;


public static VaporProgram parseVapor(InputStream in, PrintStream err) throws IOException {
  Op[] ops = {
    Op.Add, Op.Sub, Op.MulS, Op.Eq, Op.Lt, Op.LtS,
    Op.PrintIntS, Op.HeapAllocZ, Op.Error,
  };
  boolean allowLocals = true;
  String[] registers = null;
  boolean allowStack = false;

  VaporProgram tree;
  try {
    tree = VaporParser.run(new InputStreamReader(in), 1, 1,
                           java.util.Arrays.asList(ops),
                           allowLocals, registers, allowStack);
  }
  catch (ProblemException ex) {
    err.println(ex.getMessage());
    return null;
  }

  return tree;
}

A Vapor-M program p.vaporm can be run using the Vapor interpreter vapor.jar as follows:

  $ java -jar vapor.jar run -mips p.vaporm

Hints

The data segments are simply translated to const segments.

Register allocation is applied to each function separately.

$a0..$a3: reserved for argument passing
$s0..$s7: general use callee-saved
$t0..$t8: general use caller-saved  
$v0: returning a result from a call

The $t variables are temporary caller saved registers, while the $s registers are callee saved. Each function saves the $s registers that it will use at the beginning of the function and saves the $t registers that it will need before calling another function.

Each frame for a function has three parts
   In
      The arguments of the call that are spilled to the stack.
      This section is sometimes considered to be part of the caller stack.
   Local
      The local variables (that are spilled to the stack)  
      The backup for the saved registers used by the function
      The backup for the registers before function calls
         The size of this space is the maximum needed by the function calls.
      The return address (if the function calls any other function)
   Out
      The backup for arguments passed by registers
      Arguments that are spilled on the stack
      The size of these sections is the maximum number of arguments of called functions.

For each function, the data flow analysis results in the def, use, in, and out sets of variables for each instruction. The set of active variables at each instruction is the union of the def and in sets for the instruction. The live intervals (used by the linear scan algorithm) can be calculated using the active sets by a top-down scan of the instructions.

The first parameters are mapped to the argument registers. The parameters that do not fit in the argument registers are spilled to the (in) stack. The argument registers that are not used for arguments are added to the pool of registers used for register allocation. The pool includes $s and $t registers.

We use the linear scan algorithm for register allocation. See the algorithm in the paper. The algorithm returns a mapping from variables to locations and the number variables spilled to the stack. A location is either a register, a (local) stack offset or an (in) stack offset.
Note that for each parameter that is mapped to an argument register, an interval starts from the first instruction. These intervals are marked as fixed so that they are not spilled by the algorithm to the stack. Once these intervals reach their end points, their argument registers can be put back to the pool to be reused.

Using the allocation map resulted from the register allocation algorithm and the out sets resulted from the liveness analysis, the sets of registers that are used after an instruction can be calculated. This set is later used to determine the registers that should be saved before a function call.

On entry to a function
   Saving the used saved registers $s

On exit from a function
   Assigning the return value to $v0
   Restoring the saved registers $s

Before a function call
   Saving temporal registers $t that will be used after the call
   Saving the argument registers $a
   Copying the argument to the argument registers and the stack
      If arguments of the caller should be passed to callee, they should be read from the stack as otherwise $a registers would be both read and written.

After a function call
   Restoring temporal registers
   Restoring argument registers

Some instructions accept only registers as operands. The registers $v0 and $v1 can also be used as temporary registers for loading values from the stack.

An implementation-specific note is that during the parsing, unique integer values are assigned to variables that we use for reference instead of names.

Submission

Your main file should be called V2VM.java, and if P.vapor contains a syntactically correct Vapor program, then

java V2VM < P.vapor > P.vaporm

creates a Vapor-M program P.vaporm with the same behavior as P.vapor

Untar the following tarball and read the instructions in the ReadMe.txt file. Your submission must work with the testing script when run on the department servers.  Make sure you test your final tarball before submitting.

Phase3Tester.tar.gz Download


Phase 4: Activation Records and Instruction Selection

Introduction

In this phase, the Vapor-M registers and stacks should be mapped to MIPS registers and runtime stack. In addition, the Vapor-M instuctions should be mapped to MIPS instructions.

Dependencies

We need to have the following items. We had the first item in phase 3.

- Vapor Parser vapor-parser.jar: Download
  The source code vapor-parser-source.tar.gz Download and
  the java doc vapor-parser-javadoc.tar.gz Download for this parser are also available.

- Test cases
  Sample input programs Phase4Tests.tar.gz: Download
  Sample output programs Phase5Tests.tar.gz: Download

- MIPS Interpreter mars.jar Download from the MARS project

Translation

The translator should traslate a Vapor-M program like Factorial.vaporm (Download) to a MIPS program like Factorial.s (Download)

The jar file vapor-parser.jar includes both the parser and syntax tree classes for the Vapor-M language. Compile your program against it using the -classpath option. A Vapor-M program can be parsed to Vapor-M syntax tree using the Vapor parser vapor-parser.jar as follows. A Vapor-M program will never contain the following AST node: VVarRef.Local.

import cs132.util.ProblemException;
import cs132.vapor.parser.VaporParser;
import cs132.vapor.ast.VaporProgram;
import cs132.vapor.ast.VBuiltIn.Op;

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintStream;


public static VaporProgram parseVapor(InputStream in, PrintStream err) throws IOException {
  Op[] ops = {
    Op.Add, Op.Sub, Op.MulS, Op.Eq, Op.Lt, Op.LtS,
    Op.PrintIntS, Op.HeapAllocZ, Op.Error,
  };

  boolean allowLocals = false;
  String[] registers = {
    "v0", "v1",
    "a0", "a1", "a2", "a3",
    "t0", "t1", "t2", "t3", "t4", "t5", "t6", "t7",
    "s0", "s1", "s2", "s3", "s4", "s5", "s6", "s7",
    "t8",
  };
  boolean allowStack = true;

  VaporProgram tree;
  try {
    tree = VaporParser.run(new InputStreamReader(in), 1, 1,
                           java.util.Arrays.asList(ops),
                           allowLocals, registers, allowStack);
  }
  catch (ProblemException ex) {
    err.println(ex.getMessage());
    return null;
  }

  return tree;
}

A MIPS program P.s can be run as

  $ java -jar mars.jar nc P.s

Running without any arguments will bring up the simulator GUI, which will let you step forward and backward through your program.

Hints

MIPS snippet
   .data
      var1: .word 5
      table:
         Label1
         Label2
     
   .text
      jal Main
      li $v0 10   # syscall: exit
      syscall

      _print:
         li $v0 1   # syscall: print integer
         syscall
         la $a0 _newline   # address of string in memory
         li $v0 4   # syscall: print string
         syscall
         jr $ra
      _error:
         li $v0 4   # syscall: print string
         syscall
         li $v0 10  # syscall: exit
         syscall
      _heapAlloc:
         li $v0 9   # syscall: sbrk
         syscall    # address in $v0
         jr $ra
      .data
      .align 0
         _newline: .asciiz "\n"
         _str0: .asciiz "null pointer\n"

Common instructions
   li reg, value   # load immediate
      load immediate value into destination register
   la reg, label   # load address
      load address of the label to the register
   lw $t2, ($t0)   # load word
   lw $t2, 4($t0)
      load word at $t0 (St0 + 4) to $t2
   sw reg, label   # store word
      store word reg to location label
   move reg1, reg2
      copy the value of reg1 to reg2
   jal label   # jump and link
      copy program counter (return address) to register $ra
      jump to program statement at label
   jalr reg   # jump to reg and link
      copy program counter (return address) to register $ra
      jump to program statement at the address in reg
   j label   #  jump
      jump to label
   jr reg   # jump register
      jump to return address in reg
   addi $t2, $t3, 5   # add immediate
      $t2 = $t3 + 5
   add $t0, $t1, $t2   # add
      $t0 = $t1 + $t2 add as signed (2's complement) integers
   sub $t2, $t3, $t4   # subtract
      $t2 = $t3 - $t4
   addiu $t, $s, imm
      Adds $s and a sign-extended immediate value and stores the result in $t
   addu $t1, $t6, $t7   # add as unsigned integers
      $t1 = $t6 + $t7
   subu reg1, reg2, reg3   # subtract as unsigned integers
      reg1 = reg2 - reg3
   mult  reg1, reg2   #  multiply
      multiply 32-bit quantities in reg1 and reg2, and store 64-bit
      result in special registers Lo and Hi: (Hi, Lo) = reg1 * reg2
   slt $d, $s, $t   # set on less than
      If $s is less than $t, $d is set to one. It gets zero otherwise.
   beqz reg, label   # branch if equal to zero
      branch to label if the value reg is zero
   bnez reg, label   # branch if not equal to zero
      branch to label if the value reg is not zero

The stack grows from higher addresses down to lower addresses.  

Higher address
         ----------------------
         |
         ----------------------
         |
$fp ->   | In
         ----------------------
         |
         | Local
         ----------------------
         |
$sp ->   | Out
         ----------------------
         | ra
         ----------------------
         | fp
         ----------------------
        
         Callee frame
        
Lower address

Note that each word is 4 bytes and literals below should be multiplied by 4.

On entry to a function
   Safe fp to location $sp - 2
   Move fp to sp
   Pushing the frame
      Decrease $sp by size = Local + Out + 2
         1 for Return address
         1 for frame pointer
   Saving the return register at $fp - 1 (if the function calls any other function)
      Note that $fp now holds the old $sp
     
On exit from a function
   Restoring the return register $ra (if the function calls any other function)
      from $fp - 1
   Restore $fp from $fp - 2
   Popping the frame
      Decreasing $sp by size = Local + Out + 2
   Jumping to the return register

The register $t9 can be used to load values for instructions that accept only registers.

Submission

Your main file should be called VM2M.java, and if P.vaporm contains a syntactically correct Vapor-M program, then

java VM2M < P.vaporm > P.s

creates a MIPS program P.s with the same behavior as P.vaporm.

Untar the following tarball and read the instructions in the ReadMe.txt file. Your submission must work with the testing script when run on the department servers.  Make sure you test your final tarball before submitting.

Phase4Tester.tar.gz Download