factorial procedure in mips32

[blob84]

Hi this is the fact procedure:

fact:
	addi $sp, $sp, -8
	sw $ra, 4($sp)
	sw $a0, 0($sp)

	slti $t0, $a0, 1
	beq $t0, $zero, L1
	
	addi $v0, $zero, 1
	addi $sp, $sp, 8
	jr $ra

L1:	addi $a0, $a0, -1
	jal fact

	lw $a0, 0($sp)
	lw $ra, 4($sp)
	addi $sp, $sp, 8

	mul $v0, $a0, $v0
	jr $ra

Book explanation:

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

When it call jal fact where does it go the code?