MIPS: Millions of Instructions Per Second (Part 5)

It's the last part!  There might be additional posts on tangential topics, but this is the last of the must-know tutorials.  In any case, if you've made it here you're probably pretty confident about programming in MIPS.

Previously I discussed bitwise operations and files.  In this chapter I will talk about recursion and the frame pointer.  You should be familiar with recursion in high level languages before continuing.  If you know what it is but still get tripped up here and there, then some of this post will act as a refresher.

 

Recursion

 

Recursion is just the act of defining a procedure in terms of that same procedure.  In both MIPS and Java, it is achieved by calling some function within its definition.  A recursive function will have two parts - some base case that returns without making a self-referential call, and an "else" section that does.  Without a base case that's properly defined, the recursive function will enter an infinite loop of calls.  This makes it different from regular functions in practice, because it is more likely that a programmer will have to visit the debugger when writing a recursive function than not.  For this reason I highly advise that you read Debugging in MARS first.

The automatic example used for recursion is the Fibonacci sequence.  Kind of cliché, I know, but it's what works.  Here is an implementation in Java:

In this case we're using the classic interpretation of the sequence, which begins with 1 instead of 0.  We have two base cases defined - one if n is 0, and another if n is 1.  They both return the same thing, so we capture their behavior in a single if bracket.  For every other case, we return the sum of the last two terms.  We're assuming we get no negative numbers as input - if we did, this would produce an integer underflow.  But that's not too important, since there are no negative Fibonacci terms.

The MIPS equivalent has three labels.  The beginning of the function, the base case, and the else case.  At the beginning of the function we check the value of the integer passed to the function to determine if we've hit the base case.  If so, all we have to do is return 1.  If we haven't, then we have to recursively call fibonacci twice to get the two composite terms.  It's only when the program hits the else case that I need to save anything onto the stack - this might not be true for all recursive functions, but it works here.

I must save $ra or I will get stuck in an infinite loop.  Every time fibonacci is called, $ra will be replaced with the start address of fibonacci.  We have to hold on to the address that points to main or we will lose it.  I also need a place to save the intermediate result of the first composite term (and the integer argument for a moment), so I reserve $s0.  Successive recursive calls will save my intermediate result for me because I have used correct register convention, saving $s0 before using it.  Of course, I load the old values back and restore the stack pointer before returning to the caller.

If you think about it, there is nothing special happening here that does not apply to other parent functions.  The only thing that is different is that I am "calling myself" instead of something else.  Register convention ensures that recursion does not introduce additional complications - if you use it correctly outside of recursive functions, you use it correctly inside recursive functions.

Frame Pointer

The frame pointer ($fp) is a special register used for pointing to different places on the stack.  The stack pointer always points to the top of the stack, so if you want to communicate the location of some data to a subroutine (function) then you need to pass that address with some other register than $sp.  Usually this will involve arguments - the frame pointer can be used to point to extra arguments that the caller placed on the stack.  Using an argument register to point to this region is wasteful, since there are only four of them.  Ideally all arguments would sit in registers for speed reasons, but register memory is expensive.  Having that extra room makes a difference.

If I have a function that takes 10 arguments, 4 of them can reside in registers while 6 of them will be on the stack.  The frame pointer will hold the address of the first of those 6:

On the caller side of things, the old frame pointer is first saved to the stack.  It is then modified to point to wherever on the stack I want it to, in this case with an offset of 4, because that is where my 6 arguments will go.  I load these arguments with $fp as my base address.  I then call the function that takes in these arguments, load the old value of the frame pointer back, and restore the stack.

As the callee, I can load the 6 extra arguments directly into temporary registers using the frame pointer as the base.  I can then do as I please with that information, and return to the caller when I'm done.

Really, the frame pointer is not all that mysterious.  It is just an extra register that you can use to point to a region on the stack other than its top.

Conclusion

We're done!  Well, done with the important material anyway.  There are other interesting things you can do as a side project.  MIPS syscalls in MARS support midi, so you could use it to play music if you wanted to.  But that is all supplemental, and if you have understood the core material you can learn the extra stuff with little effort.  Hopefully this tutorial has been helpful.