MIPS 程序集 - 斐波那契寄存器

Question

我正在为 MIPS 编写递归 Fib 函数。我需要帮助来理解 $a0 寄存器。我想用 n-1 和 n-2 调用函数，但是在你用 n-1 调用它之后，$a0 寄存器发生了变化。所以说你想要 fib(2)，即使在它 jal 之后，它应该保持原来的值 2，但是它仍然是之前 n-1 调用的 1。而1-2=-1，则无穷无尽。我曾尝试在调用 n-2 之前加载 $a0，但这也会导致一切失败。这是代码。谢谢

# switch to the Text segment
.text
# the program is defined here

.globl  main
main:


add $a0, $zero, 2
add $a1, $zero, 0
jal fib

j print_end


fib:
addi    $sp, $sp, -12
sw  $ra, 0($sp)
sw  $a0, 4($sp)
sw  $a1, 8($sp)

addi    $t5, $zero, 1
beq $a0, $zero, end_fib
beq $a0, $t5, end_fib
j   not_base
end_fib:
addi    $v0, $a0, 0     #base return 0 or 1
addi    $sp, $sp, 12
jr  $ra


not_base:
addi    $a0, $a0, -1
jal fib
addi    $a1, $v0, 0 #a1 = fib(n-1)
addi    $a0, $a0, -2
jal fib

b_k:
lw  $ra, 0($sp)
lw  $a0, 4($sp)
lw  $a1, 8($sp)
add $v0, $v0, $a1           #fibn = fib n-1 + fib n-2
addi    $sp, $sp, 12
jr  $ra

print_end:
addi    $a0,$v0, 0
jal Print_integer


bottom:

la  $a0, done   # mark the end of the program
jal Print_string

jal Exit0   # end the program, default return status


.data
# global data is defined here




.text

.globl  Print_integer
Print_integer:  # print the integer in register $a0 (decimal)
li  $v0, 1
syscall
jr  $ra

Answer 1

不需要在函数中间保存和恢复$a0。你是 saving/restoring $a0 entry/exit，所以当 fib(n-1) returns $a0 将是 n-1，所以得到 n-2 你再减 1:

# In:  $a0 = n
# Out: $v0 = fib(n)
fib:
    addiu $sp,$sp,-8
    sw $a0,0($sp)
    sw $ra,4($sp)

    sltiu $t0,$a0,2
    beq $t0,$zero,recurse

    # Base case: return n
    move $v0, $a0
    j return

recurse:
    # Compute fib(n-1)
    addiu $a0,$a0,-1
    jal fib

    # Save fib(n-1) on the stack    
    addiu $sp,$sp,-4
    sw $v0,($sp)

    # Compute fib(n-2)
    addiu $a0,$a0,-1
    jal fib

    # Return fib(n-1) + fib(n-2)
    lw $t0,($sp)
    addiu $sp,$sp,4
    addu $v0,$v0,$t0

return:
    lw $ra,4($sp)
    lw $a0,0($sp)
    addiu $sp,$sp,8
    jr $ra

MIPS 程序集 - 斐波那契寄存器

MIPS Assembly - Fibonacci Registers

recursion

assembly

stack

fibonacci

mips32