CSE5317/4305 Project #5 (Simple IRs)

Due Thursday April 11 before midnight

Worth 18% of your project grade


For this project, you need to generate Intermediate Representation (IR) data structures for some of the ASTs. You should not generate any MIPS code for this project. You should generate IR data for all types of ASTs, except the following AST nodes:

ProcDec, RecordExp, RecordInit, RecordDeref, ArrayDeref, CallExp, CallSt, RetSt

That is, in this project, you should not generate IR code for record construction, array indexing, record projection, function/procedure call, and function/procedure prologue/epilogue (but you should generate IR code for their bodies and store their parameters in the symbol table). Everything left out will be generated by the next project. I have also given the IR for ArrayExp AST because it's difficult. You will have to use the TypeCheck code for ProcDec to make sure that parameters and local variables are inserted in the Symbol table.

Your ASTs that represent IRs, when printed by toString(), should follow the following syntax:

IRexp -> Const(INTEGER_LITERAL)         # integer constant
         Const(STRING_LITERAL)          # string constant
         Const(REAL_LITERAL)            # real constant
         Mem(IRexp)                     # retrieve the memory content at given address
         Reg(ID)                        # a register
         Binop(binop,IRexp,IRexp)       # binary operation
         Unop(unop,IRexp)               # unary operation
         Call(ID,IRexp,IRexp,...,IRexp) # set register ra to the return address,
                                        #    set v0 to the callee's static link (first IRexp),
                                        #    call function ID with the given arguments
					#    and return back the result
	 ESeq(IRStmt,IRexp)             # evaluate the statement and return the exp value
         Assert(IRexp,IRexp)            # if the first exp is true return the second exp value,
                                        #    otherwise, raise an exception
         Allocate(IRexp)		# allocate a number of words in the heap and return the address

IRstmt -> Move(Mem(IRexp),IRexp)        # set memory with given address
          Move(Reg(ID),IRexp)           # set register value
          Label(ID)                     # define a label to be the current address
          Jump(ID)                      # jump to label ID
          CJump(IRexp,ID)               # jump to label ID if condition (IRexp) is true
          Seq(IRstmt,... IRstmt)        # sequence of statements
          Call(ID,IRexp,IRexp,...,IRexp)# set register ra to the return address,
                                        #    set v0 to the callee's static link,
                                        #    and call procedure ID with the given arguments
          SystemCall(ID,IRexp)		# a system call can be: READ_INT, READ_FLOAT,
	                                #    WRITE_INT, WRITE_FLOAT, WRITE_BOOL, or WRITE_STRING
          Return()                      # jump to the address in register ra
binop -> GT | LT | EQ | GE | LE | NE | PLUS | MINUS | TIMES | SLASH | DIV | MOD | AND | OR 
unop  -> UMINUS | NOT
Read Section 8 in the notes for explanation of some of them. Note that SEQ(s1,s2) in the notes is now Seq(s1,s2,...sn), which makes the code generation easier. The IR Call(f,sl,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. For this project phase, 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 static method code in the file Code.gen, which gets an AST exp (for expressions, statements, declarations, etc) as input and generates its IR. The IR code generated is normalized by the normalize method (ie, Seq and ESeq are removed), and the resulting list of IRs is pretty-printed in the output.

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).

You should generate IRs for each type of expression, declaration, etc., so that for each input file, you get only one IR tree (like you get one AST only). 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(Label(loop_10_),
    CJump(Binop(EQ,Mem(Binop(PLUS,Reg(fp),Const(-12))),Const(0)),exit_11_),
    Move(Mem(Binop(PLUS,Reg(fp),Const(-60))),
         Binop(PLUS,Mem(Binop(PLUS,Reg(fp),Const(-60))),Const(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(SystemCall(WRITE_STRING,Const("x = ")),    # write "x = "
    SystemCall(WRITE_INT,Mem(...)),            # write x
    SystemCall(WRITE_STRING,Const("\n")))      # write end=of-line

Hints:

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

run 5 hello
You also need to compare your output with that of the solution:
solution 5 hello

After ensuring that your program compiles and executes correctly, cleanup your pcat directory using clean Then, if you are using Linux/MacOS, archive your pcat directory using tar cfz pcat.tgz pcat. If you are using Windows, zip the pcat directory into the file pcat.zip. Then submit your file (pcat.tgz or pcat.zip) here:

Submit Project #5:

Last modified: 03/26/13 by Leonidas Fegaras