конвертировать код C в сборку MIPS - комбинированная функция с использованием рекурсии

Question

У меня проблема с преобразованием кода C в код сборки MIPS комбинированной функции (nCr).

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

икогда я ставлю int 5 для n и 3 для r (цифровые данные), результат должен быть 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, $0, $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, $0, 1 #$v0 (1)
j rtn
bne $a1, $0, gen  #if (b==0)
addi $v0, $0, 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, $0  #$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

С вашим кодом много проблем.

Во-первых, выбранное вами отношение повторения очень неэффективно и намного сложнее, чем необходимо.Даже Википедия имеет несколько лучших рекуррентных отношений, например

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, $0, 1 #$v0 (1)
j rtn
bne $a1, $0, gen  #if (b==0)
addi $v0, $0, 1 #$v0 (1)
j rtn

Первый из этих тестов перепрыгивает через второй тест, если a!=b, независимо от того, b==0, поэтому второй тест недоступен.Вам придется изменить код на

##base case
bne $a0, $a1, isbzero  #if (a==b)
addi $v0, $0, 1 #$v0 (1)
j rtn
isbzero:
bne $a1, $0, gen  #if (b==0)
addi $v0, $0, 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, $0  #$s0 comb(a-1, b-1)
addi $a1, $a1, 1  #$a1 (b)
jal comb  #call comb(a-1, b)

будет иметь неверные значения для $a0 и $a1.

Если соответствие ABI для вас не имеет значения, вы можете восстановить значения перед возвратом, снова увеличив аргументы.

Answer 2

Ваша основная проблема заключается в том, что вы не сохраняете значения регистров между (рекурсивными) вызовами, поэтому значения закрываются.$ a0 и $ a1 являются регистрами сохранения вызовов, поэтому любой вызов может их заглушить, а ваша функция comb фактически заглушает их.Но это означает, что после первого рекурсивного вызова значения исчезают, поэтому второй рекурсивный вызов является мусором.

Вам необходимо сохранить значения $ a0 и $ a1 в кадре стека перед первым рекурсивным вызовом ивосстановить их после возвращения (до второго вызова).Вам также необходимо сохранить значение $ v0 во втором вызове, так как $ v0 аналогично перекрывается вызовами.