CSE5317/4305 Project #5 (Code Generation)

Due Wednesday April 27 before midnight

Worth 25% of your project grade


For this project, you need to generate Intermediate Representation (IR) data structures from the ASTs. You should not generate any MIPS code for this project. The IRs are described in pcat/src/main/scala/edu/uta/pcat/IR.scala. I have also given the IR for ArrayExp, Body, and ProcDec because they are difficult. (The code for Body inserts parameters and local variables into the Symbol table using access_variable.)

Read Section 8 in the notes for explanation of IRs. Note that SEQ(s1,s2) in the notes is now Seq(List(s1,s2,...,sn)), which makes the code generation easier. The IR Call(f,sl,List(e1,...,en)) takes the function/procedure name, f, the static link of the callee, sl, and zero or more arguments e1 ... en. It pushes the arguments e1 ... en in the stack, sets the register v0 to sl, calls procedure f, and, after f returns, it pops n values from the stack. If it is a function, it returns a value. You can use the following six reserved registers (which should not be used for any other purpose):

fp       frame pointer
sp       stack pointer
gp       pointer to heap (implicitly used by Allocate only)
ra       return address
v0       used in passing the static link from the caller to the callee
a0       used in passing the result of a function from the callee to the caller
For example, the IR Reg("fp") represents the register fp. The IR code Allocate(n) allocates n words in the heap, and returns the address of the first word, that is, it is equivalent to gp:=gp+n*4; return gp. You will never deallocate objects from heap.

The only thing that you have to do for this project is to write more code in the method code in the file pcat/src/main/scala/edu/uta/pcat/Code.scala, which gets an AST (expression, statement, declaration, etc) as input and generates its IR.

Assumptions:
Every data value occupies 4 bytes regardless of its type. More specifically, this is how you map PCAT types to IRs:

All PCAT variables should be allocated in the run-time stack, including all global variables (you store global variables in the activation record of the main program). The frame layout will be similar to that in Section 7.2 in the notes, but function arguments are pushed in the stack from left to right. The register v0 is used in passing the static link from the caller to the callee. This is done implicitly inside the IR Call(f,sl,...). There are two different cases for the static link. Lets say that caller_level and callee_level are the nesting levels of the caller and the callee procedures (recall that the nesting level of a top-level procedure is 0, while the nesting level of a nested procedure embedded inside another procedure with nesting level n, is n+1). When the callee is lexically inside the caller's body, that is, when callee_level=caller_level+1, the static link is Reg("fp"). Otherwise, we follow the static link of the caller d+1 times, where d=caller_level-callee_level (the difference between the nesting level of the caller from that of the callee). For d=0, that is, when both caller and callee are at the same level, we have Mem(Binop("PLUS",Reg("fp"),IntValue(-8))). For d=2 we have:

Mem(Binop("PLUS",Mem(Binop("PLUS",Mem(Binop("PLUS",Reg("fp"),IntValue(-8))),IntValue(-8))),IntValue(-8)))

You should generate IRs for each type of expression, declaration, etc., so that for each input file, you get only one IR tree. Statements are a bit tricky. For example, the while loop:

while c do x:= x+5;
where x is an integer with offset -60 and c is a boolean with offset -12, generates the following IR when printed:
Seq(List(Label("loop_10_"),
         CJump(Binop("EQ",Mem(Binop("PLUS",Reg("fp"),IntValue(-12))),IntValue(0)),"exit_11_"),
         Move(Mem(Binop("PLUS",Reg("fp"),IntValue(-60))),
              Binop("PLUS",Mem(Binop("PLUS",Reg("fp"),IntValue(-60))),IntValue(5))),
         Jump("loop_10_"),
         Label("exit_11_")))
Here, I used the name generator new_name for labels that generates new names, such as loop_10_ and exit_11_, each time.

PCAT read/write statements need special attention. You need to use various system calls: READ_INT, WRITE_INT, WRITE_STRING, etc. For example, the PCAT statement write("x = ",x) has IR:

Seq(List(SystemCall("WRITE_STRING",StringValue("x = ")),    # write "x = "
         SystemCall("WRITE_INT",Mem(...)),                  # write x
         SystemCall("WRITE_STRING",StringValue("\n"))))     # write end=of-line

Hints:

You need to run your parser against all tests/*.pcat files. For example:

scala lib/pcat.jar 5 tests/hello.pcat
You also need to compare your output with that of the solution:
scala pcat-solution.jar 5 tests/hello.pcat

After ensuring that your program compiles and executes correctly, cleanup your pcat directory using mvn clean. Then, zip the pcat directory into the file pcat.zip and submit it here:

Submit Project #5:

Last modified: 04/04/2016 by Leonidas Fegaras