Having trouble with "stacks" concept in MIPS Assembly Language (as an instruction)

[Mothergoose729]

I am trying to teach myself underlying computer concepts with the help of Computer Organization and Design 3rd Edition. In it the authors use the 32bit MIPS Assembly language and architecture to teach concepts.

I am on Section 2.7 which covers Stacks, procedures, and nested procedures using a sort of sudo assembly language that is has presented thus far. This is the problem it presents step by step with explanations:

COMPILING A RECURSIVE C PROCEDURE, SHOWING NESTED PROCEDURE LINKING

Let's tackle a recursive procedure that calculates factorial:

int fact (int n)
{
if (n<1) return (1);
else return (n * fact(n-1));
}

What is the MIPS assembly code?

The parameter variable n corresponds to the argument register $a0. The compiled program starts with the label of the procedure and then saves two registers on the stack, the return address and $a0:

fact:
addi $sp, $sp, -8 #adjust stack for 2 items
sw $ra, 4($sp) # save the return address
sw $a0, 0($sp) # save the argument n

The first time fact is called, sw saves an address in the program called fact. The next two instructions test if n is less then 1, going to L1 f N>=1.

slti $$t0, $a0, 1 #test for n < 1
beq $t0, $zero, L1 #if n>= 1, go to L1

If n is less then 1, fact returns 1 by putting 1 into the value register: it adds 1 to 0 and places the sum in $v0. If then pops the two saved values off the stack and jumps to the return address:

addi $v0, $zero, 1 #returns 1
addi $sp, $sp,8 # pop 2 items off the stack
jr $ra # returns to after jal

Before popping two items off the stack, we could have loaded $a0 and $ra. Since $a0 and $ra don't change when n is less then 1, we skip those instructions.

If n is less then 1, the argument n is decremented and then fact is called again with the decremented value:

L1: addi $a0, $a0, -1 #n >=1: argument gets (n-1)
jal fact # call fact with (n-1)

The next instruction is where fact returns, Now the old return address and the old argument are restored, along with the stack pointer:

lw $a0, 0($sp) #return from jal: restore argument n
lw $ra, 4($sp) #restore the return address
addi $sp, $sp, 8 #adjust the stack pointer to pop 2 items

Next, the value register $v0 gets the product of the old argument $a0 and the current value of the value register. We assume a muliply instruction is available, eve though it is not covered tell chapter 3:

mul $v0, $a0, $v0 #return n * fact (n-1)

Finally, fact jumps again to the return addresss:

Jr $ra #returns to caller

I understand that the original value for n or argument $a0 is stored in the stack before L1 procedure is executed. My problem is when the recursion happens I don't see how the new value of n (n-1) makes it into the equation. I am assuming that the multiply command:

mul $v0, $a0, $v0

Contains the modified value and the original value (or the last value used before being decremented).

If this equation recurs twice; once for the initial call and one for a nested call, then where does n-1 go? Further more if it recurs three or more times, then where is the intermediate value stored? In the stack and the beginning of each time through L1? That is the part I am confused about.

 

[Gamingphreek]

I believe that MIPS (as well as other architectures) is the same as x86 in this respect. I apologize, its been 2 years since I have worked with the MIPS architecture in depth.

The parameters that are passed in the program from function calls are accessed at various places in the current activation record.

For instance consider:
void foo( int a, int b, int c )
{
//Do stuff
}

Assuming a 32-bit architecture and no optimizations, a, b, and c would be accessed at the stack pointer - 4, -8, and -12 respectively.

-Kevin

(On a side note, I read your other thread and strongly advise that you get a better understanding before jumping right into the MIPS architecture. ESPECIALLY make sure you have a full understanding of pipelining and the von Neumann architecture - otherwise assembly code that you think will do one thing will do something completely different)

 

[Mothergoose729]

I believe that MIPS (as well as other architectures) is the same as x86 in this respect. I apologize, its been 2 years since I have worked with the MIPS architecture in depth.

The parameters that are passed in the program from function calls are accessed at various places in the current activation record.

For instance consider:
void foo( int a, int b, int c )
{
//Do stuff
}

Assuming a 32-bit architecture and no optimizations, a, b, and c would be accessed at the stack pointer - 4, -8, and -12 respectively.

-Kevin

(On a side note, I read your other thread and strongly advise that you get a better understanding before jumping right into the MIPS architecture. ESPECIALLY make sure you have a full understanding of pipelining and the von Neumann architecture - otherwise assembly code that you think will do one thing will do something completely different)

The text goes on to describe pipelining in chapter six. The outline of the chapters start with basic computer science stuff (voliatile, memory hierarchy, all review), then 2-3 is all MIPS, with performance assessment, data path and control, then pipelining being covered in 4-6. Is this text to advanced for me? I have been able to understand everything so far up to this point.

As I said before this is more "sudo" assembly code. The actual assigning of adresses and registers is not actually done, just the idea of it within registers.

EDIT:

Maybe if I explain what I think is happening somebody can tell me what I am doing wrong.

The program tests to see if N is greater then 1, if it is it multiplies n by itself minus 1 (mimicking a factorial) and then calls the function again mimicking the process until N<1. This is recursion. I covered this is my altorithms class using VB.

The body calls fact and passes n as argument register $a0 and the instruction address (where to return to in the body) as return address register $ra. The stack in adjusted by 8 (which is decremented from the stack pointer $sp) making way for two 4 byte words.

$slti checks if the argument register $a0 is greater then one. If it is register temporary register $t0 is annotated true by recieving the value of zero. The beq instruction tests for the false value by looking for one in that register. If it is false it branches to L1 where the return register $v0 gets the value of one the two items in the stack are deleted when the $sp is incremented by 8 (adjusting the stack down by 2 4 byte words) and then the jr command jumped to the register stored in $ra.

If it is$a0 is decremented by one the jal instruction is used to jump to fac and the proses repeats. The problem I have is the load word instructions that follow. Wouldn't the new value for N in $a0 be restored to the old value of N, which was stored as Fact was executed the first time? For instance:

N= 7
N =7 is stored

Is N> 1?

yes N= N-1

Load N (which was stored as 7)

Return $v0 (which was never given a value?) * Old N

Does that make things more clear? Where does my logic go wrong?

 

[Gamingphreek]

I mean only you can determine if the text is too advanced If you are understanding it then keep going through it.

It is my personal opinion that learning the absolute basics first is more beneficial. The logic behind XOR, XNOR; how multiplexing and demultiplexing work.

Additionally, it is going to be very tough for you to understand assembly on a 32-bit architecture like MIPS. There are just a great deal of commands. Without an understanding of jumps and branches and what not, you might find that difficult as well.

It is my view that once you understand stuff like that, as you read through this discussion you can ask yourself why components are where they are in the execution cycle. Why is this switch/gate needed.

Feel free to continue reading and asking questions though. There is a reason these forums are here - we are happy to help

-Kevin

 

[Mothergoose729]

I think I edited my post after you posted. Would mind reading my logic?