MIPS stack visualization

Question

Below is a c code for a factorial function. I clearly understand how the recursive function works. but I can't visualize or don't know how to works on the MIPS stack.

MIPS CODE

My question is, how are we saving the recursive function (saving return address & arguments) in the stack for each step of the recursion?

I know that for each recursive function, we are saving the arguments and return address and then readjusting the stack pointer.

Can someone help me visualize how the process works.

You pretty much explained it. You store those two values in the stack each time a call is made. It's a stack so it's a linear block of memory. I don't know how it can be made any clearer. — Sami Kuhmonen
Just some pictures of each recursive call would be great so I'm 100% confident about the idea — Can't see me

Margaret Bloom Margaret Bloom · Accepted Answer · 2016-09-27T07:40:54

Premise The stack in MIPS works just as the stack in any other architecture, so you can just Google for that.

Assume the stack point to an arbitrary location of memory:

|  xxx   |                xxx = Undefined 
|  xxx   | <- $sp
|        |
|        | | Free area, stack moves down
|        | V

Now just simulate a call to, say, fact(3).
^{_{You pasted an image of the code, so no code will be shown here. A copy-pastable code would have made this answer much clearer.}}

Each invocation of fact pushes the return address and the argument, in this order.
Let's assume fact is at 0x1000 and that the call to fact is at 0x1ffc.

fact(3)

|  xxx   | 
|  xxx   |
| 0x2000 | Return address to caller of fact(3)
|    3   | <- $sp          Argument of fact(3) 
|        | 

fact(2) called from fact(3)

|  xxx   | 
|  xxx   |
| 0x2000 | Return address to caller of fact(3)
|    3   | Argument of fact(3)
| 0x1028 | Return address to L1+8 label
|    2   | <- $sp          Argument of fact(2)

fact(1) called from fact(2)

|  xxx   | 
|  xxx   |
| 0x2000 | Return address to caller of fact(3)
|    3   | Argument of fact(3)
| 0x1028 | Return address to L1+8 label
|    2   | Argument of fact(2)
| 0x1028 | Return address to L1+8 label
|    1   | <- $sp          Argument of fact(1)

fact(0) called from fact(1)

|  xxx   | 
|  xxx   |
| 0x2000 | Return address to caller of fact(3)
|    3   | Argument of fact(3)
| 0x1028 | Return address to L1+8 label
|    2   | Argument of fact(2)
| 0x1028 | Return address to L1+8 label
|    1   | Argument of fact(1)
| 0x1028 | Return address to L1+8 label
|    0   | <- $sp          Argument of fact(0)

fact(0) return 1 and remove two items from the stack.
fact(0) is a leaf invocation, i.e. the last invocation, so no other call changed $ra, furthermore $a0 (the argument) is not needed, thus these two values saved on the stack are simply discarded by incrementing $sp.

Just before "jr $ra" in fact(0)

|  xxx   | 
|  xxx   |
| 0x2000 | Return address to caller of fact(3)
|    3   | Argument of fact(3)
| 0x1028 | Return address to L1+8 label
|    2   | Argument of fact(2)
| 0x1028 | Return address to L1+8 label
|    1   | <- $sp           Argument of fact(1)

The other returns restore the values of $a0 and $ra from the stack to compute n*fact(n-1) and return to their caller.

Just before "jr $ra" in fact(1)

|  xxx   | 
|  xxx   |
| 0x2000 | Return address to caller of fact(3)
|    3   | Argument of fact(3)
| 0x1028 | Return address to L1+8 label
|    2   | <- $sp           Argument of fact(2)

Just before "jr $ra" in fact(2)

|  xxx   | 
|  xxx   |
| 0x2000 | Return address to caller of fact(3)
|    3   | <- $sp            Argument of fact(3)

Just before "jr $ra" in fact(3)

|  xxx   | 
|  xxx   | <- $sp

Note how the stack is returned to the original position at the end of the recursion chain.

MIPS stack visualization

1 Answers