Конвертировать код 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 аналогичным образом перекрывается вызовами.