Project 5

The library exports a procedure called print. To use this procedure, your generated MIPS assembly code must include the directive .import print at the top of the file.

The print procedure expects a parameter in $1. It interprets this parameter as a two's complement integer, formats the integer in base 10, and prints the base 10 representation to standard output, followed by a newline.

The procedure preserves the values of all registers. It modifies the stack, but only at locations above the stack pointer $30. As long as you are not storing important data above the stack pointer (which is improper use of the stack) it will not overwrite your data.

The procedure is called like any other MIPS procedure, by using jalr. Remember to save $31 before making the call, as jalr will modify $31.

Assemble your generated code with cs241.linkasm, then use cs241.linker to link the assembled MERL file with print.merl and produce a combined MERL file that you can execute. The "Testing Your Code Generator" section farther down the page gives a more detailed sequence of commands to use.

The library exports three procedure called init, new and delete. To use these procedures, your generated MIPS assembly code must include the following directives at the top of the file:

.import init
.import new
.import delete

Initialization

The init procedure sets up the heap. It must be called before any calls to new or delete, and it must not be called more than once.

The init procedure expects two parameters, in $1 and $2.

• If the first parameter of wain has type int*, meaning the MIPS program is to be run with mips.array, pass the starting address of the input array in $1 and the size of the input array in $2. Note that these are the default values stored in $1 and $2 when using mips.array. In other words, to pass the correct parameters, it suffices that you do not modify $1 or $2 before calling init.
• If the first parameter of wain has type int, meaning the MIPS program is to be run with mips.twoints, pass the value 0 in $2 (indicating that there is no input array). The value in $1 does not matter in this case.

Allocation (New)

The new procedure expects a parameter in $1, the size of the array to allocate. It attempts to allocate an array of the given size and returns a value in $3:

• If the allocation was successful, it returns the address of the allocated array in $3.
• If the allocation failed, it returns 0 in $3.

Note that your code generator is expected to return NULL on a failed allocation, and it is expected to use 1 (not 0) as the representation of NULL, so you will need to detect the case where new returns 0 and change the value in $3 to 1 instead.

Deallocation (Delete)

The delete procedure expects a parameter in $1, the address of the array to deallocate. This must be the address of a currently allocated array as returned by new, or else the behaviour is undefined. The procedure does not return a value; it simply deallocates the given array.

Note that in WLP4, deleting a NULL pointer is supposed to do nothing. However, passing the address 1 (which represents NULL in our course convention) to the delete procedure will cause an error. Thus, your code generator needs to detect the case where the pointer to delete is NULL and avoid making the call to delete.

Other Information

The init and delete procedures preserve the values of all registers, and the new procedure preserves the values of all registers except $3. All three procedures modify the stack, but only at locations above the stack pointer $30. As long as you are not storing important data above the stack pointer (which is improper use of the stack) it will not overwrite your data.

The procedures are called like any other MIPS procedure, by using jalr. Remember to save $31 before making the call, as jalr will modify $31.

Assembly & Linking

Assemble your generated code with cs241.linkasm, then use cs241.linker to link the assembled MERL file with alloc.merl and produce a combined MERL file that you can execute. The "Testing Your Code Generator" section farther down the page gives a more detailed sequence of commands to use.

Note that alloc.merl must appear as the last command line argument to the linker (that is, it must come after all other MERL files passed to the linker). This is because the heap is allocated after the end of alloc.merl, so if it is not the last argument, the heap will overwrite other linked code.

Your tree should have five string fields:

• A field rule, which is only used in nonterminal nodes, and stores the CFG rule used to expand the node.
• A field lhs, which is only used in nonterminal nodes, and stores the left-hand side of the CFG rule.
• Two fields kind and lexeme, which are only used in terminal nodes, and store the kind and lexeme of the token, respectively.
• A field type which stores the type of the node (int or int*) if the node has a type (otherwise, it just stores an empty string).

Additionally, it should have a field rhs which is a vector or list of strings, and stores the symbols on the right-hand side of the CFG rule in a nonterminal node.

This is just a very basic tree structure that gives you what you need to get started with the project. You are free modify this algorithm and your tree structure to to do extra processing and store additional useful information in the tree.

1. Read one line from standard input. The line consists of a number of whitespace-separated strings, which we will refer to as "parts" of the line. You can process the line part-by-part in C++ by creating a stringstream from the line; in Racket, you can use string-split to split the line on whitepace.
2. Initialize the rule field to an empty string. We will build up this string as we read each part of the line (which represents a CFG rule, optionally with a type annotation at the end).
3. The first part of the line is the left-hand side of the rule. Store this part in the lhs field, and append this part to the rule field.
4. Read the remaining parts of the line one at a time.
   • If the part is the special string .EMPTY, the CFG rule has an empty right-hand side, and there is no type annotation. Break and continue to the next step.
   • If the part is a colon (":"), then the next part after is a type annotation, int or int*. Read the next part and store it in the type field, then break and continue to the next step.
   • Otherwise, the part is a symbol from the right-hand side of the CFG rule. Add the symbol to the rhs vector. Append a space to the rule field, and then append the symbol.
5. Now, loop over the symbols in the rhs vector or list (if it is nonempty) and add one child to the root for each symbol. Determine whether the symbol is a terminal or nonterminal. In the WLP4 grammar, terminals are in ALL CAPS, and nonterminals are in lowercase, so you can just check whether the first character of the symbol is uppercase or lowercase to determine this.
   • If the symbol is a terminal, the child should be a leaf node storing the terminal. Read the next line of standard input, which is guaranteed to represent a terminal token if you have implemented the rest of the algorithm correctly.
     • Split the line into parts as before.
     • The first part is the kind of the token and the second part is the lexeme.
     • Create a leaf node and store the kind of the token in the leaf node's kind field, and the lexeme in the leaf node's lexeme field. The leaf node should be created directly rather than through a recursive call.
     • Type information for terminal nodes is not needed during code generation, so you can ignore the rest of the line (even if there are more parts).
   • If the symbol is a nonterminal, construct the child by recursively calling this algorithm.

The rule field in each nonterminal node should contain a representation of the CFG rule with no extraneous whitespace (there should be only a single space between each symbol, and no leading or trailing whitespace). This is important since it will allow you to do string comparisons to determine the rule at a node.

Consider the following input WLP4 program:

int wain(int a, int b) {
  return a+b+241;
}

The MIPS program you generate should assume the two parameters of wain are stored in $1 and $2. One possible correct output for your code generator would be:

add $3, $1, $2
lis $5
.word 241
add $3, $3, $5
jr $31

While this output is a correct MIPS program that returns the value a+b+241 in $3, it may be difficult to write a code generator that produces output like this. Below is another valid MIPS program for this WLP4 program, which may be closer to what your code generator would produce if you are following the conventions from lectures.

; wain prologue
lis $4
.word 4
sw $1, -4($30)
sub $30, $30, $4
sw $2, -4($30) 
sub $30, $30, $4
sub $29, $30, $4 

; wain body
lw $3, 8($29)
sw $3, -4($30)
sub $30, $30, $4
lw $3, 4($29)
add $30, $30, $4
lw $5, -4($30)
add $3, $5, $3
sw $3, -4($30)
sub $30, $30, $4
lis $3
.word 241
add $30, $30, $4
lw $5, -4($30)
add $3, $5, $3

; wain epilogue
add $30, $30, $4
add $30, $30, $4
jr $31

Notice that the code generator produced some comments and blank lines. These do not affect the behaviour of the MIPS program, so you are allowed to add them. They are not required but may make your generated code easier to read and debug.

Here is one more example of a valid possible output, although it is not clear how or why a code generator would produce output like this. It is included just to illustrate that any MIPS program which has the same visible behaviour as the WLP4 program is acceptable output.

add $5, $1, $0
add $7, $2, $0
lis $24
.word 240
lis $1
.word 1
add $14, $5, $7
add $23, $24, $1
add $3, $14, $23
jr $31

• NULL should be represented by the value 1, rather than 0. If NULL is deferenced, your generated MIPS program must crash with an error (Marmoset will actually explicitly check that your program crashes).
• If new fails to allocate an array of the desired size, it should return NULL, that is, 1. (In C++, this would throw an exception, but WLP4 does not have exceptions.) Note that the provided new procedure will actually return 0 on a failed allocation. Your generated code should detect this and return NULL (1) instead.
• If delete is called on NULL, nothing should happen. (This is actually how C++ behaves too.) Note that the provided delete procedure will crash if it is passed the value 1, so your generated code should detect this case and actually avoid making the call.
• Suppose i is an integer and p is a pointer. If p refers to the address a, then the expressions p+i and i+p should refer to the address a+4i, and the expression p-i should refer to the address a-4i. This differs from C++ in that C++ considers it undefined behaviour to do something like array+241 if the offset 241 is outside the bounds of the array. In WLP4, the pointer arithmetic itself is defined behaviour, but dereferencing an "out-of-bounds" pointer is undefined behaviour.
• If p and q are pointers, referring to addresses a and b respectively, then p-q should produce the integer value (a-b)/4. However, Marmoset will not test pointer-pointer subtraction in cases where the result could vary depending on implementation choices (for example, subtracting two pointers that refer to stack-allocated variables).
• Integer overflow should be handled by truncating any overflowing bits. Note that this is what naturally happens when you use the add and sub instructions in MIPS, and when you use mult followed by mflo, so you don't need to do anything special to ensure this happens.
• Anything which is undefined behaviour in C++ and is not addressed by the points above is also considered undefined behaviour in WLP4, and will not be tested by Marmoset.

Generate the MIPS assembly code with your code generator, assemble it with cs241.binasm, then run it with either mips.twoints or mips.array (depending on if the WLP4 program takes two int parameters, or int* and int).

Assuming mips.twoints is used:

./wlp4gen < program.wlp4 > program.asm
cs241.binasm < program.asm > program.mips
mips.twoints program.mips

mips.twoints <(./wlp4gen < program.wlp4 | cs241.binasm)

Make sure you have downloaded print.merl and alloc.merl and placed them in the same directory as your code generator.

You will need to use cs241.linkasm to assemble your output into MERL, and then cs241.linker to link the files together. Note that alloc.merl must be the last argument to the linker.

Assuming mips.twoints is used:

./wlp4gen < program.wlp4 > program.asm
cs241.linkasm < program.asm > program.merl
cs241.linker program.merl print.merl alloc.merl > linked.merl
mips.twoints linked.merl

mips.twoints <(cs241.linker <(./wlp4gen < program.wlp4 | cs241.linkasm) print.merl alloc.merl)

You can use the reference compiler to compile a WLP4 progam directly to MIPS machine code as follows:

wlp4c < program.wlp4 > reference.mips

You can run the MIPS program generated by the reference compiler with mips.twoints or mips.array to confirm the expected behaviour of the WLP4 program (return value in $3 and output from println). You can then compare it with the behaviour of your own generated MIPS programs.

Doing these comparisons can be awkward and time-consuming because there are multiple steps involved in compiling and running a WLP4 program. The runtests.bash script mentioned below gives you a more automated way of doing this.

Note that unless the WLP4 program does not use the input parameters (and thus always produces the same result when executed), it is not feasible to determine with 100% accuracy whether your MIPS program matches the behaviour of the reference compiler's MIPS program. You can run both MIPS programs with various different inputs and check that the results are the same, but you generally cannot confirm this for all possible inputs.

This essentially means there are two "layers" of testing: you have to come up with WLP4 programs as test inputs for your code generator, but you also need to come up with different inputs to test the generated MIPS programs.

Make sure your parse tree is ready to go. If you did not complete Project 4 and you are using the Preanalyzed Format, follow the instructions in the "Reconstructing the Tree (from Preanalyzed Format)" drop-down at the end of the "Input Formats" section higher up the page. Print out your tree after constructing it to ensure it contains all the correct data (not just the rules/tokens but also type information).

If you haven't already, implement the getChild function from the first step in the Project 4 Stepping Stones. It makes traversing the tree easier.

In this project, you will have to output a lot of MIPS code to standard output. It will be annoying and tedious to do this by writing std::cout << ... << "\n" or (displayln ...) over and over (or whatever output-printing functions you prefer).

We suggest writing one helper function for each MIPS instruction, which simply prints the instruction. Here are some examples in C++.

void Add(int d, int s, int t) { 
  std::cout << "add $" << d << ", $" << s << ", " << t << "\n"; 
}
void Beq(int s, int t, std::string label) { 
  std::cout << "beq $" << s << ", $" << t << ", " + label + "\n"; 
}
void Jr(int s) { 
  std::cout << "jr $"  << s << "\n"; 
}

Some other helpers might be useful too, like for .word directives, or for printing a label definition:

void Word(int i) {
  std::cout << ".word " << i << "\n";
}
void Word(std::string label) {
  std::cout << ".word " + label + "\n";
}
void Label(std::string name) {
  std::cout << name + ":\n";
}

The up-front work of defining these helper functions will be a little tedious, but then in the rest of the code generator, you can write your MIPS code very concisely, like this:

Add(3, 1, 0);
Label("loop");
Beq(3, 2, "end");
Add(3, 3, 1);
Beq(0, 0, "loop");
Label("end");
Jr(31);

Once you have written helper functions for printing MIPS code, define three more helper functions:

• push(s) outputs the following two-instruction sequence (push the value in $s to the stack):

  sw $s, -4($30)
  sub $30, $30, $4

• pop(d) outputs the following two-instruction sequence (pop the top item of the stack into $d):

  add $30, $30, $4
  lw $d, -4($30)

• pop() with no argument outputs the following instruction (pop the top item of the stack and discard it):

  add $30, $30, $4

Note that you must generate code that stores the constant 4 in $4 before calling push or pop or they will not work as expected.

You are free to define more helpers as you see fit. Another one that might be useful is a helper constant which generates code to store a constant value in $3 (using lis and .word).

In this step, we will implement code generation for programs that only contain the wain procedure, and don't do anything except return the value of one of wain's local variables, such as this program:

int wain(int one, int two) {
  int three = 3;
  int four = 4;
  return three;
}

For programs that only contain wain, the top of the parse tree has the following form:

start
├─BOF BOF
├─procedures
│ ╰─main
│   ╰─...
╰─EOF EOF

main → INT WAIN LPAREN dcl COMMA dcl RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE

Traverse the tree to access the main node. After finding this node, begin generating a block of code that implements the wain procedure.

Start by generating code that loads the value 4 into $4. This is important to do right at the start of the program, or else your push and pop helpers will not work.

Constructing the Offset Table

We will use the convention from the lectures and notes that the frame pointer separates the parameters from the non-parameters:

For a procedure with n parameters, the first parameter is at offset 4n. Offsets decrease by 4 for each new variable that you process. So for example, the second parameter is at offset 4n - 4, the third parameter is at 4n - 8, and so on. The first non-parameter variable is at offset 0, the second is at offset -4, the third is at offset -8, and so on.

In the case of wain, there are always exactly two parameters, so the first offset is 8 (4n where n = 2) and each subsequent offset decreases by 4.

Examine the first dcl child of the main subtree. It has this form:

dcl
├─type
│ ╰─...
╰─ID firstParamName

The type subtree is not relevant here. Look at the ID child to get the name of the variable. Add the variable to the offset table, and generate code that pushes $1 to the stack.

Repeat for the second dcl child (the second parameter of wain) except in this case you should generate code that pushes $2 to the stack.

Set the frame pointer by generating an instruction sub $29, $30, $4.

Finally, traverse the dcls subtree. This subtree contains declarations and initializations of non-parameter local variables. Add each variable to the offset table. Instead of pushing $1 or $2 to the stack, load the initial value of the variable into a register and push that value to the stack.

Null Pointer Note: A variable can be initialized to a NUM (an integer) but it can also be initialized to NULL (a null pointer). You should use the constant 1 to represent NULL.

For the example WLP4 program above, the dcls tree looks like this:

dcls
├─dcls
│ ├─dcls
│ ├─dcl
│ │ ├─type
│ │ │ ╰─INT int
│ │ ╰─ID three
│ ├─BECOMES =
│ ├─NUM 3
│ ╰─SEMI ;
├─dcl
│ ├─type
│ │ ╰─INT int
│ ╰─ID four
├─BECOMES =
├─NUM 4
╰─SEMI ;

Ensure you process the declarations in the correct order. You should process the declaration of "three" by descending into the inner "dcls" tree, then afterwards process "four". The initial value of "three" is 3, and the initial value of "four" is 4, which you can determine by examining the relevant NUM child.

You should now have a complete offset table for the local variables of wain. For the example program above, it would look like this:

Name	Offset
one	8
two	4
three	0
four	-4

Generating Code For The Return Expression

In this stepping stone, we are assuming that the wain procedure doesn't contain any statements, and doesn't have any complex expressions involving arithmetic or other operations – it simply returns one of its local variables.

Thus, generating code for the return expression is straightforward. Traverse the expr subtree of the main node to figure out which variable is returned, and generate a lw instruction that loads the variable's value from the appropriate offset and places it in $3, the return register.

For our example program, the expr subtree looks like this:

expr
╰─term
  ╰─factor
    ╰─ID three

Your code generator might process this tree as follows:

• Generate code for expr → term by recursively generating code for term.
• Generate code for term → factor by recursively generating code for factor.
• Generate code for factor → ID by looking up the ID's lexeme in the offset table, which for this example returns offset 0. Output the instruction: lw $3, 0($29)

Cleaning Up The Stack And Returning

Call your pop() helper one time for each local variable that you pushed, to clean up the stack. This is technically not required for wain, but it is a good practice as it is required for other procedures.

Then, end the program with jr $31!

Implement support for the following rules:

expr → term
expr → expr PLUS term
expr → expr MINUS term
term → factor
term → term STAR factor
term → term SLASH factor
term → term PCT factor
factor → ID
factor → NUM
factor → LPAREN expr RPAREN

In other words, your code generator should support arithmetic expressions involving variables, numbers, addition, subtraction, multiplication, division, modulo, and parentheses.

Use the technique from the lectures and notes of using the stack to store temporary expression values.

Assume that all expressions have integer type (pointer arithmetic is implemented in Step 4A).

Implement support for the following rules:

statements → statements statement  
statements →
statement → lvalue BECOMES expr SEMI
lvalue → ID  
lvalue → LPAREN lvalue RPAREN

In other words, your code generator should support assignment statements with a variable on the left-hand side.

Note that the variable can be optionally wrapped in parentheses, like ((x)) = y; This doesn't change the meaning of the statement, it's just a consequence of the fact that you can add parentheses wherever you want.

Implement support for the following rules:

statements → statements statement
statements →
statement → PRINTLN LPAREN expr RPAREN SEMI

In other words, your code generator should support println statements. The println function prints the value of the given expr as a base 10 (decimal) integer, followed by a newline.

One valid way of implementing this is to just take your entire solution to Question 6 and make your code generator output this print procedure alongside the rest of your generated code. When you encounter a println statement, call your print procedure.

However, complicated procedures like this are often compiled separately and linked externally. We provide this as an option for implementing println (and it is the only option you can use if you have not done Question 6).

If you choose the linking option, download the print.merl library and follow the instructions for "Using the print.merl library" in the Resources section at the top of the page.

Extend your support for the following rules to handle expressions of pointer (int*) type.

expr → expr PLUS term
expr → expr MINUS term

Additionally, you should implement support for the rule factor → NULL if you have not already (allowing NULL to appear in expressions).

You will need to update your handling of addition and subtraction to check the types of the left and right subexpressions. Depending on which expressions have int* type, you will need to modify the code you output.

• For the case of adding an integer offset to a pointer, or subtracting an integer offset from a pointer, the offset value should be multiplied by 4 after it is computed.
• For the case of subtracting two pointers, the result should be divided by 4 after it is computed.

You will likely need to implement Step 4B as well before you can write test programs that do meaningful things with pointer arithmetic, and test Steps 4A and 4B together.

Implement support for the following rules:

factor → NULL
factor → AMP lvalue
factor → STAR factor
lvalue → ID  
lvalue → STAR factor
lvalue → LPAREN lvalue RPAREN

In other words, your code generator should support the use of NULL in expressions, the pointer dereference operator, and the address-of operator. Additionally, assignment statements should permit not only assigning to a variable, but also a dereferenced pointer expression.

There are two different cases for pointer dereference, depending on if it occurs in an lvalue context or not. By "an lvalue context" we mean the dereference is occuring on the left-hand side of an assignment, or immediately following an address-of operator. In an lvalue context, the generated code should produce the address being dereferenced, while in other contexts, the generated code should produce the value at the address being dereferenced.

For address-of and assignment, the generated code depends on what type of lvalue you are taking the address of or assigning to. Review the lectures or notes for guidance.

Once you have implemented both Step 4A and Step 4B, you can write programs that freely manipulate the elements of an array. Without Step 4A, you can only really manipulate individual variables, or the first element of an array.

Implement support for the following rules:

statements → statements statement
statements →
statement → IF LPAREN test RPAREN LBRACE statements RBRACE ELSE LBRACE statements RBRACE
statement → WHILE LPAREN test RPAREN LBRACE statements RBRACE
test → expr EQ expr  
test → expr NE expr  
test → expr LT expr 
test → expr LE expr  
test → expr GE expr  
test → expr GT expr

In other words, your code generator should support if statements and while loops. Note that both these control structures can have more statements (including additional if statements and while loops) nested inside them! Be sure to test with nested structures.

The generated code for the comparison tests should compute the values of the left and right expressions, then perform a comparison between them that produces a boolean value (0 or 1).

Note that if the expressions have pointer (int*) type, you should use unsigned comparisons, that is, use sltu instead of slt. This is because pointers (memory addresses) cannot be negative and using slt may produce wrong results for large addresses.

Once comparisons are done, think about how to replicate the behaviour of an if statement or a while loop in MIPS assembly using branch instructions and labels. Have your code generator output MIPS code that implements the control structure, with appropriate calls mixed in to generate code for the comparison test and the nested statements.

The final issue to solve is the fact that all label names used in your generated code have to be unique. A suggestion is to write a helper function called generateLabel; each time you call it, it returns a unique label name that is guaranteed to have never been used before in your code. You could implement this by, for example, having the function increase a global counter every time it is called (and this global counter is not modified by any other function).

The reason we suggest completing Steps 3A, 3B, and 3C first is because it will enable you to write much more interesting test programs involving if statements and while loops:

• If you have not implemented assignment (3B) or printing (3C) then you cannot have anything interesting actually happen inside an if statement or a while loop.
• If you have not implemented arithmetic (3A) then your options in the body of a while loop are limited to assigning a variable to an existing variable, or printing an existing variable, whereas with arithmetic you can have programs that do something like incrementing a counter or doing calculations.

Implement support for the following rules:

factor → NEW INT LBRACK expr RBRACK
statements → statements statement
statements →
statement → DELETE LBRACK RBRACK expr SEMI

In other words, your code generator should support allocating memory with new in expressions, and deallocating memory with delete in statements.

Writing your own memory allocation routines is tricky, and writing them in MIPS assembly is even harder. So, we provide memory allocation routines through an external library, which you can link your generated code with.

Download the alloc.merl library and follow the instructions for "Using the alloc.merl library" in the Resources section at the top of the page. It is similar to using the print.merl library for println, but the instructions are more complicated and have more steps. Read and follow the instructions carefully.

Pay particular attention to:

• The requirements for calling init and the fact that there are different requirements depending on the type of the first parameter of wain.
• What you should do when new fails to allocate (return NULL, not 0).
• What you should do when delete is called on NULL (do nothing, don't crash).

Implement support for the following rules:

procedures → procedure procedures
procedure → INT ID LPAREN params RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
params →
params → paramlist
paramlist → dcl
paramlist → dcl COMMA paramlist
factor → ID LPAREN RPAREN
factor → ID LPAREN arglist RPAREN
arglist → expr
arglist → expr COMMA arglist

In other words, your code generator should support declaring procedures other than wain, which can have an arbitrary number of parameters of arbitrary types. Additionally, it should support procedure calls occurring in expressions.

Note that in a WLP4 program, wain is always the last procedure, but it is the first procedure to actually be executed at runtime because it is the entry point for the program. Ensure your generated code is set up so that wain is executed first.

Some notes about procedures:

• Each procedure should begin with a label definition that identifies the start of the procedure. A good practice is to use the procedure's name, but add a special prefix to it that is not used elsewhere in the code generator. For example, if the procedure is called else1 (a perfectly legal WLP4 procedure name) the label you generate could be Pelse1: (P for procedure). This will avoid conflicts with the labels you generate for if statements and while loops (as long as they don't also start with P).
• Each procedure should have its own offset table, separate from wain's. At runtime, each procedure call has its own frame pointer that it uses to access its local variables using the offsets. When a procedure p calls a procedure q, to avoid losing track of its frame pointer, the procedure p saves $29 on the stack, and restores it once q returns.

Calling Procedures

There are many ways to implement procedures in a code generator. Generally one defines a calling convention, describing how arguments are passed to a procedure and how values are returned from a procedure, and the implementation must adhere to this convention consistently. Other aspects of a calling convention include which registers are preserved by a procedure call.

Our suggested calling convention in this course is to pass all parameters on the stack. The procedure, once called, sets up its frame pointer and retrieves the parameters using positive offsets from the frame pointer. Values are returned in $3 (which conveniently is where our code generator places expression results). In terms of preserving registers, each procedure is responsible for preserving its own frame pointer ($29) and return address ($31); for other registers it is your decision if and how to preserve them.

For a call with arguments (the rule factor → ID LPAREN arglist RPAREN), these are the appropriate steps to implement this calling convention:

• Save $29 (the frame pointer) and $31 (the return address) on the stack.
• Traverse the arglist and push each expr argument to the stack, in left-to-right order.
• Call the procedure with jalr.
• Pop and discard each argument from the stack.
• Restore $31 (the return address) and $29 (the frame pointer) from the stack.

A call with no arguments (the rule factor → ID LPAREN RPAREN) is similar, but the steps about pushing and popping arguments are omitted.

Generating Code For Procedures

Generating code for each procedure itself (the nodes corresponding to the rule procedure → INT ID LPAREN params RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE) is similar to generating code for wain.

• Output the label that identifies the start of the procedure.
• Build an offset table and set up the stack and the frame pointer by examining the params and dcls. The process is very much like for wain, except:
  • The procedure can have any number of parameters (wain always has 2).
  • You should examine the params subtree to build the offset table, but do not push anything to the stack (the caller pushes the parameters to the stack).
• Depending on the design of your code generator and your chosen calling convention, your procedure may need to save some of the registers it modifies by pushing them to the stack. If so, save them here, after pushing local variables (to avoid disrupting your offset calculations).
• Generate code for the statements and the return expr.
• If you saved modified registers on the stack, pop and restore them.
• Pop the non-parameter local variables (the parameters were pushed by the caller, and will be popped by the caller).
• Return with jr $31.

You may want to focus first on getting procedures with no parameters and calls with no arguments working. Once you are confident in your implementation, move on to procedures with parameters and calls with arguments.