MIPS recursion: How to compute end result from stack
My task is to implement egyptian multiplication in MIPS assembler recursively. I think I understood most of the relevant stuff, but I just can't get behind one thing: How is the end result computed? For example in this code(taken from this question):
# int fact(int n) fact: subu sp, sp, 32 # Allocate a 32-byte stack frame sw ra, 20(sp) # Save Return Address sw fp, 16(sp) # Save old frame pointer addiu fp, sp, 28 # Setup new frame pointer sw a0, 0(fp) # Save argument (n) to stack lw v0, 0(fp) # Load n into v0 bgtz v0, L2 # if n > 0 jump to rest of the function li v0, 1 # n==1, return 1 j L1 # jump to frame clean-up code L2: lw v1, 0(fp) # Load n into v1 subu v0, v1, 1 # Compute n-1 move a0, v0 # Move n-1 into first argument jal fact # Recursive call lw v1, 0(fp) # Load n into v1 mul v0, v0, v1 # Compute fact(n-1) * n #Result is in v0, so clean up the stack and return L1: lw ra, 20(sp) # Restore return address lw fp, 16(sp) # Restore frame pointer addiu sp, sp, 32 # Pop stack jr ra # return .end fact
How/ when are the two lines between
ever reached? In my understanding, either L1/L2 are branched to, or fact is called recursively...
Ok, it seems that I figured out how to implement something recursively in MIPS. However, I have one last problem: With the code below, my program lacks one "turn", meaning that the last value isn't considered when computing the final result.
pharao: li $t0, 2 #load imm for division by 2 lw $a0, fac_1 #load fac_1 into $a0 lw $a1, fac_2 #load fac_2 into $a1 li $t7, 0 #zero $t7 li $t6, 1 #load 1 into $t6 jal egypt #jump to egypt j end egypt: subiu $sp,$sp,16 #space on stack for 4 values sw $ra,0($sp) #store return address sw $a0, 4($sp) #store fac_1 sw $a1, 8($sp) #store fac_2 divu $a1, $t0 #div fac_2 by 2 mflo $a1 #store quotient in $a1 mfhi $a2 #store remainder in $a2 sw $a2, 12($sp) #store remainder on stack multu $a0, $t0 #multiply fac_1 by 2 mflo $a0 beq $a1, $t6, return #base case jal egypt #call egypt recursively addingup: lw $a0, 4($sp) #load values from stack lw $a1, 8($sp) # " lw $a2, 12($sp) # " beqz $a2, return #jump on if remainder is 0 addu $t7, $t7, $a0 #add if remainder is 1 return: lw $ra, 0($sp) #restore return address addiu $sp, $sp, 16 #inc stackpointer jr $ra
When I try running the program with the values 10 and 20, the result (in $t7) is 40, because the last value, 160, isn't added. How can I fix this?
jal is the instruction JUMP AND LINK, which means it stores the next instruction's address in r31 and jumps to the label given. You could say it's (one/the) way to do subroutine calls in MIPS assembler.
The jr $ra jumps to the address contained in r31, which means it returns to the instruction following jal. As you can see, that's done just before the .end.
In short, jal is a subroutine call, and when the call returns, it will execute the instructions following jal.
In your edited question, you check the base case a bit strangely, something like;
a = n >> 1; b = n & 1; if(a == 0) return 0; ...do calculation...
...when a much better base case would be;
if(n == 0) return 0; a = n >> 1; b = n & 1; ...do calculation...
The problem with the first base case is that b can still be 1 and give a result, but you return anyway without using the value.