Lab3 MIPS procedures
1 Objectives
Following completion of this lab you should be able to:
- Call and pass arguments to procedures in MIPS programs.
- Return from procedures.
- Discuss register allocation strategies.
- Save and restore registers.
- Correctly manage the stack.
2 General
-
Get a copy of the question sheet to edit (Word doc version)
-
Be sure to follow the MIPS procedure calling conventions as described in your book (Section 2.8 and Appendix A.6).
-
test7.asm
uses the.asciiz
assembler directive. See page A-47-A-49 and A-14-A-15 of your text for details. -
MARS also provides a small set system calls to make input and output easier. We've been using a system call to exit our programs.
test7.asm
uses system calls to print integers and strings. See SYSCALL functions available in MARS and page A-44 of your text for additional information on the available system calls.
3 Sorting an Array
- NOTE: You may not use the 's' registers for this portion of the lab.
-
Pull your repository. Open the files
lab03/p7/p7-loop.asm
andlab03/p7/p7-swap.asm
in MARS.Note the two locations marked for adding your code.
-
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.
-
Add your code to
p7-swap.asm
in the spot indicated below the labelSwapMaxWithLast:
. -
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:-
Get the address of "
A
" from an argument register rather than doing a "la
" on a label. -
Get the value of "
N
" from an argument register rather than loading it from memory. -
Return from the procedure by doing a "
jr $ra
" (this should already be done). -
You may need to reallocate registers or manage the stack to comply with the MIPS procedure calling convention.
-
-
Modify the
p7
procedure inp7-loop.asm
so that it callsSwapMaxWithLast
a single time withA
andN
as arguments. What output do you expect when you runp7-loop.asm
? -
Run
p7-loop.asm
. Is the actual output what you expected? -
Replace your call to "
SwapMaxWithLast
" with a call to the procedure "ProcedureConventionTester
". This procedure takes the same arguments asSwapMaxWithLast
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. -
Modify the procedure
p7
inp7-loop.asm
so that it callsSwapMaxWithLast
\( N-1 \) times and with each successive call the length of the array passed is decreased by 1. See the comments inp7-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
? -
Run
p7-loop.asm
. Is the actual output what you expected? -
Again test your compliance with the MIPS procedure calling convention by calling "
ProcedureConventionTester
" instead of "SwapMaxWithLast
" -
If
SwapMaxWithLast
needed to return a value how would that be accomplished? -
What changes would you need to make if
SwapMaxWithLast
needed more than 4 arguments? -
What changes would you need to make if
SwapMaxWithLast
called another procedure? -
The code in
p7-loop.asm
works almost like a procedure. Describe the changes you would make to convert thep7-loop.asm
code into asort
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
-
Open
lab03/fib/fib.asm
in MARS. -
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); } }
-
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. -
When you have correctly implemented the calling conventions run
fib.asm
. Does it behave as expected? -
In your
fib
procedure, replace the calls tofib
with calls tofibtest
. This is similar to theProcedureConventionTester
from the previous lab. -
Test your program with the new
fibtest
calls. If there are any issues, fix them. Once your program works correctly, restore the original calls tofib
. 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. -
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.