Lab3 MIPS procedures

1 Objectives

Following completion of this lab you should be able to:

2 General

3 Sorting an Array

  1. Pull your repository. Open the files lab03/p7/p7-loop.asm and lab03/p7/p7-swap.asm in MARS.

    Note the two locations marked for adding your code.

  2. In a previous lab, you worked with a program for swapping the maximum element of an array with the last element. Extract your code for "swapping the maximum value of an array with the last element of the array". You'll need all the code between the label p5: and the 'jr'. Don't copy the label or the 'jr'.

    If you have not already addressed the issue discussed in the last step of "Finding the Maximum" in lab 3, you'll need to do so now.

  3. Add your code to p7-swap.asm in the spot indicated below the label SwapMaxWithLast:.

  4. Modify your swap code so that it complies with the documentation and specifications in p7-swap.asm. Note, SwapMaxWithLast is a procedure which takes 2 arguments - the location (address) of an array of words in memory and the length (in words) of the array - and order matters. Be sure your code conforms with the MIPS procedure calling conventions (see pages A-22-A-33 of your text). Specifically, you will need to:

    1. Get the address of "A" from an argument register rather than doing a "la" on a label.

    2. Get the value of "N" from an argument register rather than loading it from memory.

    3. Return from the procedure by doing a "jr $ra" (this should already be done).

    4. You may need to reallocate registers or manage the stack to comply with the MIPS procedure calling convention.

  5. Modify the p7 procedure in p7-loop.asm so that it calls SwapMaxWithLast a single time with A and N as arguments. What output do you expect when you run p7-loop.asm?

  6. Run p7-loop.asm. Is the actual output what you expected?

  7. Replace your call to "SwapMaxWithLast" with a call to the procedure "ProcedureConventionTester". This procedure takes the same arguments as SwapMaxWithLast and calls "SwapMaxWithLast", but also check for compliance with the MIPS procedure call convention. Run the program with the new call. If the test fails, fix your code so it can pass the test.

  8. Modify the procedure p7 in p7-loop.asm so that it calls SwapMaxWithLast \( N-1 \) times and with each successive call the length of the array passed is decreased by 1. See the comments in p7-loop.asm for exactly where to put your code. In pseudocode:

      for (i=N; i>1; i--) {
    SwapMaxWithLast(A, i);
  }

    What output do you expect when you run p7-loop.asm?

  9. Run p7-loop.asm. Is the actual output what you expected?

  10. Again test your compliance with the MIPS procedure calling convention by calling "ProcedureConventionTester" instead of "SwapMaxWithLast"

  11. If SwapMaxWithLast needed to return a value how would that be accomplished?

  12. What changes would you need to make if SwapMaxWithLast needed more than 4 arguments?

  13. What changes would you need to make if SwapMaxWithLast called another procedure?

  14. The code in p7-loop.asm works almost like a procedure. Describe the changes you would make to convert the p7-loop.asm code into a sort procedure which is called and which in turn calls SwapMaxWithLast.

4 Recursive Procedures

The procedure call example on page A-27-A-30 of the book and this factorial example may be helpful in understanding recursive procedures.

5 The Fibonacci Sequence

The Fibonacci sequence is defined over nonnegative integers as follows:

$$ \begin{align*} F(0) = 0\\ F(1) = 1\\ F(i) = F(i-1) + F(i-2), i \geq 2\\ \end{align*}$$

While there are several ways to calculate the Fibonacci sequence, for this lab you must use a recursive procedure.

The sequence should be:

N 0 1 2 3 4 5 6 7 8 9 10 ..
Fibonacci number 0 1 1 2 3 5 8 13 21 34 55 ..

6 Recursive Procedures Revisited

  1. Open lab03/fib/fib.asm in MARS.

  2. This file contains code to execute a recursive procedure which takes one argument i and returns F(i). Psuedo code is provided below - your final code must implement the algorithm presented below. 

    int
fib(int n)
{
  if (n == 0) {
    return 0;
  }
  else if (n == 1) {
    return 1;
  }
  else {
    return fib(n-1)+fib(n-2);
  }
}

  3. The provided code does not follow the MIPS calling conventions, therefore it loops infinitely. You need to edit this code to follow the conventions. The comment block at the top of fib.asm describes how you should allocate stack frames for this code. Be sure any changes you make to your code conforms with these specifications as well as the MIPS procedure calling conventions (see pages B-22-B-33 of your text). Your code will work with alternative stack frames, but you will not receive full credit if you do not follow these requirements. You should only have to modify the code where the comments suggest allocation and deallocation of the stack.

  4. When you have correctly implemented the calling conventions run fib.asm. Does it behave as expected?

  5. In your fib procedure, replace the calls to fib with calls to fibtest. This is similar to the ProcedureConventionTester from the previous lab.

  6. Test your program with the new fibtest calls. If there are any issues, fix them. Once your program works correctly, restore the original calls to fib. Note: this test confirms that your code follows most of the calling conventions, but doesn't test them all. You should check the green sheet to make sure you haven't missed anything.

  7. Complete the lab question sheet. You will need to trace the execution of the program and record values from the stack. You can view the stack in MARS: in Execute view, the Data Segment window has a drop down that allows you to check memory at current $sp. Use this to see the stack frames.

7 Turning It In

Submit the answers to the questions contained in the lab guide using the question sheet via gradescope, only 1 per team (make sure all team member's names are included). In gradescope you are able add your team members names to the submission, make sure you do so. When you are prompted to indicate where the "code question" is on the answer sheet, just select the first page of the assignment, you DO NOT upload code to gradescope.

Lab code will be submitted to EVERY team member's git repository.