Рекурсивная последовательность Фибоначчи от C кода до MIPS - PullRequest
Новая
       13

Рекурсивная последовательность Фибоначчи от C кода до MIPS

0 голосов
/ 25 марта 2020

Привет, я пытаюсь переписать функцию fib из Задачи 2 на: https://inst.eecs.berkeley.edu/~cs61c/sp15/hw/03/CS61C_Homework3Soln.pdf

, чтобы лучше понять код и, похоже, дает мне бесконечный l oop где-то.

Я пытался отследить стек вручную, но в настоящий момент это очень сбивает с толку, так как я не очень уверен, где происходит ошибка. Я попытался отладить с помощью 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

1 Ответ

0 голосов
/ 25 марта 2020

Здесь наихудшая ошибка: 

    ...
    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

Любой код между безусловной ветвью и меткой "мертв", он никогда не будет достигнут! (это небольшое упрощение, но в целом точное и очень уместное здесь) Так что этот код, очевидно, вам не помогает.

В результате вы возвращаетесь в некоторых случаях без выполнения кода эпилога , который отменяет пролог, и это удаление абсолютно необходимо, как вы знаете.

Для ясности, код эпилога в случае возврата 1 и возврата 0 отсутствует и должен отражать отмену полная последовательность прологов.

По сути, ваши регистры немного запутаны.

Вы храните $t0 и $t1 в стеке, но в них ничего нет первый go. Позже вы используете то, что было сохранено из $t0, как если бы в нем было что-то значимое (нет). Я подозреваю, что вы хотите хранить здесь $a0 и $s0 - хотя каждый по разным причинам.

...