FallSep.pptVIP

Fall 08, Sep 12 . . . ELEC 5200-001/6200-001 Lecture 4 * What to Save? Recursive procedure will call itself. So, will reuse return address register $ra will change argument register $a0 These two registers must be saved. Fall 08, Sep 12 . . . ELEC 5200-001/6200-001 Lecture 4 * Saved Registers for 4! Example Initial $sp $sp fact calls fact, $a0 = 3 fact calls fact, $a0 = 2 fact calls fact, $a0 = 1 fact calls fact, $a0 = 0 Return address within main program Argument register, $a0 = 4 Return address within fact Argument register, $a0 = 3 Return address within fact Argument register, $a0 = 2 Return address within fact Argument register, $a0 = 1 } } } } Fall 08, Sep 12 . . . ELEC 5200-001/6200-001 Lecture 4 * Assembly Code for fact fact: addi $sp, $sp, -8 # adjust stack for two items sw $ra, 4($sp) # save return address of caller sw $a0, 0($sp) # save caller supplied argument n slti $t0, $a0, 1 # $t0 = 1, if n ≤ 1, i.e., n = 0 beq $t0, $zero, L1 # go to L1, if n ≥ 1 addi $v0, $zero, 1 # return $v0 = 1 to caller addi $sp, $sp, 8 # no need to restore registers, since none was changed, but must restore stack pointer jr $ra # return to caller instruction after jal Fall 08, Sep 12 . . . ELEC 5200-001/6200-001 Lecture 4 * Assembly Code Continued L1: addi $a0, $a0, -1 # set $a0 to n-1 jal fact # call fact with argument n-1 lw $a0, 0($sp) # on return from fact, restore n lw $ra, 4($sp) # restore return address addi $sp, $sp, 8 # adjust stack pointer mul $v0, $a0, $v0 # n! = n × (n-1)! jr $ra # return to caller Fall 08, Sep 12 . . . ELEC 5200-001/6200-001 Lecture 4 * Execution of fact for n ≥ 1 Call Caller #a0 $ra Returned $v0 Sequence 1 Main Program n PC+4 n×(n-1)! 2 fact n-1 L1+8 (n-1)×(n-2)! 3 fact n-2 L1+8 (n-2)×(n-3)! fact . fact . fact . n-2 fact 3 L1+8 3×2 = 6 n-1 fact 2 L1+8 2×1 = 2 n fact 1 L1+8 1×1 = 1 n+1 fact 0 L1+8 1 Fall 08, Sep 12 . . . ELEC 5200-001/6200-0