Page 48 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 3: Recursion

A MIPS Translation Notes
Usually, the hard part is to decide what registers to save. arr is stored in $a0, and that this
value really doesn’t change throughout. size may need to be saved, though size - 1 appears
to be more useful. Since we make calls to sumOdd, we need to save $ra.
So, let’s save size - 1 and $ra to the stack. It turns out we also need to save arr[ size - 1 ] to
the stack too.
sumOdd: addi $sp, $sp, -12 # Adjust sp
addi $t0, $a0, -1 # Compute size - 1
sw $t0, 0($sp) # Save size - 1 to stack
sw $ra, 4($sp) # Save return address
bne $a0, $zero, ELSE2 # branch !( size == 0 )
li $v0, 0 # Set return value to 0
addi $sp, $sp, 12 # Adjust sp
jr $ra # Return
ELSE2: li $t7, 4 # t7 = 4
multi $t0, t7 # Multiple size - 1 by 4
mflo $t1 # Put result in t1
add $t1, $t1, $a0 # Compute & arr[ size - 1 ]
lw $t2, 0($t1) # t2 = arr[ size - 1 ]
andi $t3, $t2, 1 # is arr[ size - 1 ] odd
beq $t3, $zero, ELSE3 # branch if even
sw $t2, 8($sp) # save arr[ size - 1 ] on stack
move $a1, $t0 # update second arg
jal sumOdd
lw $t2, 8($sp) # restore arr[ size - 1 ] from stack
add $v0, $v0, $t2 # update return value
lw $ra, 4($sp) # restore return address from stack
addi $sp, $sp, 12 # Adjust sp
jr $ra # Return
ELSE3: move $a1, $t0 # update second arg
jal sumOdd
lw $ra, 4($sp) # restore return address from stack
addi $sp, $sp, 12 # Adjust sp
jr $ra # Return
As it turns out, we didn’t have to save size - 1. So we can leave that off the stack if you want.
As a rule of thumb, you may end up deciding later on what to save and what not to save.
A compiler, of course, has to determine this without being too clever. Sometimes a compiler
might save too much to the stack, just so it’s easier to generate code.
A few comments:

In ELSE2, we use mult. The result is placed in two registers HI and LO. Since the
number is likely to be quite small, we can assume the result is in LO, and HI contains
all 0’s. We can access the low word from LO, using mflo (move from LO).
Contd...

LOVELY PROFESSIONAL UNIVERSITY 41