从 C 代码到 MIPS 的递归斐波那契数列

Question

您好，我正在尝试重写问题 2 中的 fib 函数：https://inst.eecs.berkeley.edu/~cs61c/sp15/hw/03/CS61C_Homework3Soln.pdf

为了更好地理解代码，它似乎在某个地方给了我一个无限循环。

我试图手动跟踪堆栈，但目前非常混乱，因为我不太确定错误发生的位置。我尝试使用 QtSpim 进行调试，但这不起作用

我的 fib 被递归调用：

fib:
li $t4,1 # to compare 1 with other registers
sub $sp , $sp , 12
sw $ra , 0($sp) 
sw $t0 , 4($sp)
sw $t1 , 8($sp)

move $t1, $a0   #load n from a0 to t1

beq $t1 , $zero , Returnzero 
move $t0, $v0
beq $t1, $t4, Returnone

addi $a0, $t1 , −1

jal fib # compute fib(n-1)

move $t3 , $v0 # store return value of fib(n-1)

lw $a0 , 4 ($sp)

addi $a0, $t1, −2 # n-2

jal fib # compute fib(n-2)

add $v0, $v0, $t3 # sum of fib(n-1) + fib(n-2)

# restore stack here
lw $t1, 8($sp)
lw $t3, 4($sp)
lw $ra, 0($sp)
addi $sp, $sp, 12 

jr $ra


lw $s0, 8($sp)
lw $ra, 0($sp)

Returnzero:
move $v0, $zero #if 0 go return 0
jr $ra

Returnone:
move $v0, $s0 #if 1 go return 1
jr $ra

Answer 1

最严重的错误在这里：

    ...
    jr $ra          # <--- this is an unconditional branch; it won't come back


    lw $s0, 8($sp)  # <--- this code will never execute: it is what we call "dead" code
    lw $ra, 0($sp)

Returnzero:
    move $v0, $zero #if 0 go return 0
    jr $ra

Returnone:
    move $v0, $s0 #if 1 go return 1
    jr $ra

无条件分支和标签之间的任何代码都是"dead"，永远无法到达！ _{（这有点过于简单化，但总体上是准确且非常合适的）}所以该代码显然对您没有帮助。

因此，在某些情况下，您 return 没有运行结尾代码，它会撤消序言，而且，如您所知，这种撤消是绝对需要的。

需要说明的是，return 1 和 return 0 的结尾代码都缺失，需要反映完整序言序列的撤消。

从根本上说，您的寄存器用法有点混乱。

您正在将 $t0 和 $t1 存储到堆栈中，但第一次存储时它们中没有任何内容。稍后您将使用从 $t0 存储的内容，就好像其中有一些有意义的东西（实际上没有）。我怀疑您想在这里存储的是 $a0 和 $s0 — 尽管每个原因不同。

从 C 代码到 MIPS 的递归斐波那契数列

Recursive Fibonacci Sequence from C Code to MIPS

recursion

stack

mips