将 C 代码转换为 MIPS 汇编 - 使用递归的组合函数

Question

我在将 C 代码转换为组合函数 (nCr) 的 MIPS 汇编代码时遇到问题。

nCr = (n-1Cr-1) + (n-1Cr)

当我为 n 输入 5，为 r（数字数据）输入 3 时，结果必须是 10。

我想使用递归和堆栈指针，但出现堆栈溢出错误。

我的 MIPS 代码如下。

我的代码有什么问题？

我不能很好地识别问题...

##data
.data
digit: .word 5, 3

.text
.globl main

main:
##load data
la $t0, digit
lw $a0, 0($t0)  #put 5 in a
lw $a1, 4($t0)  #put 3 in b

##call Function comb
jal comb
##save return value in $t1
move $t1, $v0

##print result
li $v0, 1
add $a0, [=10=], $t1
syscall

##exit
li $v0, 10
syscall

##Function int comb(int a, int b)
comb:
addi $sp, $sp, -8
sw $ra, 4($sp)
sw $s0, 0($sp)

##base case
bne $a0, $a1, gen  #if (a==b)
addi $v0, [=10=], 1 #$v0 (1)
j rtn
bne $a1, [=10=], gen  #if (b==0)
addi $v0, [=10=], 1 #$v0 (1)
j rtn

##recursive call
gen:
addi $a0, $a0, -1 #$a0 (a-1)
addi $a1, $a1, -1 #$a1 (b-1)
jal comb  #call comb(a-1, b-1)
add $s0, $v0, [=10=]  #$s0 comb(a-1, b-1)
addi $a1, $a1, 1  #$a1 (b)
jal comb  #call comb(a-1, b)
add $v0, $v0, $s0 #$v0 (comb(a-1, b-1) + comb(a-1, b))
j rtn

rtn:
lw $s0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
jr $ra

.end

Answer 1

你的基本问题是你没有在（递归）调用中保存寄存器值，所以这些值被破坏了。 $a0 和 $a1 是调用者保存寄存器，因此任何调用都可能破坏它们，而您的函数 comb 实际上确实破坏了它们。但这意味着在第一次递归调用之后，值消失了，所以第二次递归调用是垃圾。

您需要在第一次递归调用之前将 $a0 和 $a1 的值保存在堆栈帧中，并在 returns 之后（第二次调用之前）恢复它们。您还需要在第二次调用前后保存 $v0 的值，因为 $v0 同样会被调用破坏。

Answer 2

您的代码存在多个问题。

首先，您选择的递归关系效率很低，而且比必要的复杂得多。甚至Wikipedia还有几个比较好的递归关系，比如

n over k = (n-1 over k-1) * (n/k)

避免多次递归到函数中（从而允许尾递归地编写函数）。

您使用的循环还有一个缺点，即您必须同时检查 k==0 和 k==n.

这将我们带到您的实现中，它未能正确检查这两个条件：

##base case
bne $a0, $a1, gen  #if (a==b)
addi $v0, [=10=], 1 #$v0 (1)
j rtn
bne $a1, [=10=], gen  #if (b==0)
addi $v0, [=10=], 1 #$v0 (1)
j rtn

如果a!=b，无论是否b==0，这些测试中的第一个都会跳过第二个测试，因此无法访问第二个测试。您必须将代码更改为

##base case
bne $a0, $a1, isbzero  #if (a==b)
addi $v0, [=11=], 1 #$v0 (1)
j rtn
isbzero:
bne $a1, [=11=], gen  #if (b==0)
addi $v0, [=11=], 1 #$v0 (1)
j rtn

最后，您在递归调用之前不保留函数参数的值。如果您想符合 ABI，则不能假定函数参数寄存器中的值在整个调用过程中都得到保留。

特别是在

之后

##recursive call
gen:
addi $a0, $a0, -1 #$a0 (a-1)
addi $a1, $a1, -1 #$a1 (b-1)
jal comb  #call comb(a-1, b-1)

以下

add $s0, $v0, [=13=]  #$s0 comb(a-1, b-1)
addi $a1, $a1, 1  #$a1 (b)
jal comb  #call comb(a-1, b)

$a0 和 $a1 的值不正确。

如果 ABI 合规性对您来说无关紧要，您可以在返回之前通过再次递增参数来恢复值。

将 C 代码转换为 MIPS 汇编 - 使用递归的组合函数

convert C code to MIPS assembly - combination function using recursion

c

recursion

mips

stack-overflow

stack-pointer