Question 2.8.2: Compiling a Recursive C Procedure, Showing Nested Procedure ......
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); } |
What is the MIPS assembly code?
Th e 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 |
The first time fact is called, sw saves an address in the program that called fact. Th e next two instructions test whether n is less than 1, going to L1 if n ≥ 1.
| slti $t0, $a0, 1 # test for n < 1 beq $t0, $zero, L1 # if n >= 1, go to L1 |
If n is less than 1, fact returns 1 by putting 1 into a value register: it adds 1 to 0 and places that sum in $v0. It then pops the two saved values off the stack and jumps to the return address:
| addi $v0, $zero, 1 # return 1 addi $sp, $sp, 8 # pop 2 items off stack jr $ra # return to caller |
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 than 1, we skip those instructions.
If n is not less than 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) |
Th e next instruction is where fact returns. Now the old return address and 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 stack pointer to pop 2 items |
Next, the value register $v0 gets the product of old argument $a0 and the current value of the value register. We assume a multiply instruction is available, even though it is not covered until Chapter 3:
| mul $v0,$a0,$v0 # return n * fact (n – 1) |
Finally, fact jumps again to the return address:
| jr $ra # return to the caller |