CMPS-2240 Homework 3: MIPS procedure call conventions

Refer to as needed:
Before starting this homework you should read and understand:

Use these references as needed:

1. What information is stored in the procedure call frame? (also called stack frame or stack activation record)

2. Early computer architectures and languages (circa 1960s) did not support a runtime stack. All modern architectures and languages do. What advantages are there to a runtime stack? Why not just store data in a procedure call in the data segments of the executable rather than in a stack frame?

3. Give the expanded symbolic name of each of these registers and state their purpose.
        $sp      $fp     $ra    $pc 

4. Explain what this instruction does.
         lw $v0, 0($fp) 

5. How do you compute the size of the current stack frame, assuming the $fp points to the first word in the current stack frame?

6. What is the purpose of caller-saved registers?

7. Explain these two instructions.
          jal a_label 
          jr  $ra

8. Assume you wish to construct a stack frame (also called call frame) for procedure foo. Which register is immediately assigned a new value? After that is done, which two registers must the procedure save to its newly constructed stack frame?

9. Before the callee can return to the caller what must the callee do?

10. What is the difference between caller-saved and callee-saved registers and when would you use one instead of the other?

11. Assume you write a programming language that does not support recursion nor allow a procedure to call another procedure. Does your language require the use of a runtime stack? Justify your answer.

12. This chunk of code from fact.s sets up a stack frame for main. Why do you substract 32 rather than add 32 from the current stack pointer? Why do you add 28 to the stack pointer to setup the current frame pointer?
  main:
          addi  $sp, $sp, -32   # stack frame is 32 bytes long
          sw    $ra, 20($sp)    # save return address
          sw    $fp, 16($sp)    # save old frame pointer
          addi  $fp, $sp, 28    # set up new frame pointer

13. Load fact.s and print.s into spim. Set a breakpoint in main. Run the program. Step through enough code to find the values of $sp before and after the call to fact (see detailed instructions in fact.s). Confirm that the values differ by 32 bytes.

14. This code sets up the stack frame for the fact procedure. In addition to storing the frame pointer and the return address on the stack, the last sw instruction stores the argument n from $a0 to the stack. Is this really necessary?
        addi  $sp, $sp, -32    # stack frame is 32 bytes long
        sw    $ra, 20($sp)     # save return address
        sw    $fp, 16($sp)     # save frame pointer
        addi  $fp, $sp, 28     # set up frame pointer
        sw    $a0, 0($fp)      # save argument (n)  

15. This chunk of code is also from the fact procedure. Without looking at the rest of the code, explain what is at label L2 and what is at label L1.
           lw    $v0, 0($fp)      # load n from stack to v0
           bgtz  $v0, L2          # branch to L2 if value in v0 > 0
           li    $v0, 1           # load 1 into the return value register
           j     L1               # unconditional jump to L1  

16. This chunk of code from the fact procedure decrements n in order to make the next recursive call. Why move n -1 into a0?
           lw    $v1, 0($fp)      # load current value of n
           addi  $a0, $v1, -1     
           jal   fact

17. The tak algorithm from Appendix A.6, implemented below in C, makes four recursive calls. When this algorithm is written in assembly, what values will need to be stored in the stack frame for each call to tak?
       int tak( int x, int y, int z) {
           if (y < x)
              return 1 + tak(tak(x-1,y,z), tak(y-1,z,x), tak(z-1,x,y));
           else 
              return z;
       }
       int main() {
           tak(18,12,6);
       }

18. Look at the code to construct the stack frame for tak (pg. A-31, Appen A). Unlike the fact procedure, which stores the frame pointer $fp on the stack, the tak procedure does not store $fp. Why does this work? Could you rewrite fact to not store $fp? Under what circumstances is storing $fp essential?