Notice:
Due: By next Monday
Resources:
Multi-platform SPIM simulator
Spim Quick Reference
Files Needed:
fact.s
cmdline.s
gcd.s
from Sleipnir:
cp /home/fac/eddie/public_html/cmps2240/code/lab3/* .
from local directory:
scp sleipnir.cs.csubak.edu:/home/fac/eddie/public_html/cmps2240/code/lab3/* .
Until now you have called procedures (e.g., printf, read) without worrying about protecting the environment of the caller (i.e.,the registers). In a high level language, variables hold local data, return values from computations, the procedure's arguments, etc. When you make a function call in C, for example, you can assume the local variables in the calling function (the caller) will not be overwritten by the called function (the callee). In MIPS, you have no variables you have registers. In MIPS it is your responsibility to ensure the registers in the caller are not overwritten by code in the callee.
In MIPS you must also worry about the address in the stack pointer register ($sp) and the return address register ($ra) since these registers could also be overwritten. If the caller loads a value/address into a register before making a function call, the content of that register may need to be saved if the callee will overwrite the register and if the caller needs the contents in that register after the function call. The only way to protect the contents of registers is to construct a stack frame in memory (also called a call frame) for the caller, store the contents of registers to that stack frame before the call, and restore the contents of the registers after the call.
Creating a stack frame is not always necessary. Let's say you have a procedure named foo. If foo nevers calls another procedure (or itself) then foo does not need to be concerned about saving its own environment. In this scenario foo has no need for a stack frame. However, if foobar is the callee and does not know if foo (the caller) expects persistent values to be in some registers and foobar is going to modify those register then foobar needs to be concerned about CLOBBERING the environment of foo. Thus foobar must construct a stack from for itself in order to save the values in the persistent registers. Once those values are saved, foobar can do work, and then restore the values in the persistent registers before returning to the caller.
In conclusion, the only way to save an environment is to store the values in the registers onto the stack frame of the currently executing procedure. The environment is saved in the procedure's stack frame on the runtime stack and cannot be overwritten by another procedure. The two methods of storing and restoring registers are shown below.
Caller and Callee
When a function is called with jal, the state of the calling function
should be saved, just in case the called function changes register values.
Convention dictates that the calling function saves its temporary registers
($t0 - $t9) on the stack, and the called function saves the ($s0 - $s7)
registers.
Caller-saved...
In this method the caller stores to its stack frame the value of any register
that the caller wants to prevent from being overwritten by a procedure that it
calls. In this scenario the caller restores the value of the register after the callee returns. Storing a register to the stack before calling another
function is a CALLER-SAVED register. The convention is to use the
$t0 - $t7 and $t8 - $t9 for this purpose.
Callee-saved...
Before using a register the callee stores the register's value
to its stack and before exiting restores the register's value back.
This process will save the environment of the caller.
The registers that you perform this process on is a CALLEE-SAVED
register. You do this method for persistent values that you want to maintain
across procedure calls.
The convention is to use the $s0 - $s7 registers for this purpose.
Suggestion:
Copy the fact.s program to fib.s, then make your changes in fib.s.
Recursive procedures nicely demonstrate the need to do one or both of the above methods because you are generally relying on values computed in both the caller and the callee. When you write a recursive program in a high-level language, the job of creating a stack frame and cleaning up the stack upon exit is done for you by the compiler. In assembly, if you wish to utilize the runtime stack you must do all the setup yourself. You will do so in this lab as you implement this C function in MIPS assembly:
int main() {
printf("The 7th Fibonacci number is %d\n", fib(7));
}
int fib(int n) {
if (n == 1 || n == 2)
return 1;
return fib(n-1) + fib(n-2);
}
This function is a similar to fact.s and tac.s. fact.s is available in the code examples. tac.s is in Appendix A.6 of the text. In particular, review the fact.s program before beginning. Start with fact.s and modify it as shown above. If you are careful, you will only need to add/modify 6 instructions. I am giving you several of those instructions below. Just like fac, you will need to construct your own stack frame upon entering fib and cleanup after yourself (restore any registers you used) as you leave fib. In addition, since you need to make two recursive function calls, you will need to be sure to store the result of the first call onto the stack before making the second call. Use this instruction to do so:
sw $v0 4($sp) # store the result of jal fib
# sw ------>
# lw <------
(Normally, you would need to draw the stack to see which stack offsets are not being used and save your result there - I am giving it to you.) You will also need two (not one) conditional branches since there are two stopping conditions:
li $v0, 1 # Set return value to 1 beq $a0, $v0, L1 # If n=1, branch to exit and return 1 li $v1, 2 # Set test value to 2 beq $a0, $v1, L1 # If n=2, branch to exit and return 1
Required Files Copy fact.s from the resources one page 1 using wget and copy printf.s from the previous week's lab. Test your code from within spim:
$ spim (spim) re "fib.s" (spim) re "printf.s" (spim) run
Note that re is another way to load an ASM file.
lo can also be used.
re is short for read, lo is short for load.
Required Files gcd.s and commandline.s from the resources on page 1. In this part of the lab you will modify fib.s to take one integer from the command line. You will pass that integer to the fib function and return fib(n). In the current version of fib.s, the integer is hard-coded into the program.
The code you need to parse the command line is found in gcd.s. More examples of parsing the command line is found in cmdline.s. Before starting, read through gcd.s and cmdline.s until you have a fair understanding of what is going on. Run both programs so you understand the behavior.
Your job is to take the code from gcd.s that parses the command line and insert that code in the main subprogram in fib.s. Since cmdline args are read as strings, you will need to add the atoi function from gcd.s to convert the strings to integers. Since parsing the command line occurs before any other code in main, you do not need to construct a stack frame for atoi, just call it from main in gcd.s. You may also need a few more chunks of code from gcd.s, but I'll let you figure it out.
Display a usage message if an argument is not provided by the user and then and exit. If all goes successfully you should be able to do this:
$ spim -f fib.s 7 $ The 7th Fibonacci number is 13.
Mr. Fibonacci started his sequence at 1,1.
If you start the fib sequence at 1, fib(8) = 21: 1,1,2,3,5,8,13,21.
Note: Once you add a cmdline arg you will not be able to test your code from within spim - to my knowledge you cannot import command line arguments.
Check Off Have the instructor check off that your program is working with the commandline. This check off is worth 2.5 points.
Your lab program fib.s must be located in the correct directory on Sleipnir. directory name: /home/stu/yourname/2240/3/ Replace yourname with your own Sleipnir username!