遞歸斐波那契組裝MIPS代碼

Question

我在模塊編譯器中爲我的課程創建了一個代碼生成器。它在MIPS彙編代碼中生成代碼，似乎工作正常（測試過非常簡單的程序和表達式）。 我測試了遞歸斐波那契程序，它現在一直循環。基本情況下，0和1，工作正常。但是當我嘗試fib（2）或更多時，它會保持循環。 不確定是什麼問題，誰能幫我找到它？

下面是代碼：

main: 
move $fp $sp 
sw $ra 0($sp) 
addiu $sp $sp -4 
sw $fp 0($sp) 
addiu $sp $sp -4 
li $a0 2 #testing comment 
sw $a0 0($sp) 
addiu $sp $sp -4 
jal fib_entry 
lw $ra 4($sp) 
addiu $sp $sp 8 
lw $fp 0($sp) 
li $v0, 10 
syscall 
fib_entry: 
move $fp $sp 
sw $ra 0($sp) 
addiu $sp $sp -4 
lw $a0 4($fp) 
sw $a0 0($sp) 
addiu $sp $sp -4 
li $a0 0 
lw $t1 4($sp) 
addiu $sp $sp 4 
beq $a0 $t1 thenBranch1 
elseBranch1: 
lw $a0 4($fp) 
sw $a0 0($sp) 
addiu $sp $sp -4 
li $a0 1 
lw $t1 4($sp) 
addiu $sp $sp 4 
beq $a0 $t1 thenBranch2 
elseBranch2: 
sw $fp 0($sp) 
addiu $sp $sp -4 
lw $a0 4($fp) 
sw $a0 0($sp) 
addiu $sp $sp -4 
li $a0 1 
lw $t1 4($sp) 
sub $a0 $t1 $a0 
addiu $sp $sp 4 
sw $a0 0($sp) 
addiu $sp $sp -4 
jal fib_entry 
sw $a0 0($sp) 
addiu $sp $sp -4 
sw $fp 0($sp) 
addiu $sp $sp -4 
lw $a0 4($fp) 
sw $a0 0($sp) 
addiu $sp $sp -4 
li $a0 2 
lw $t1 4($sp) 
sub $a0 $t1 $a0 
addiu $sp $sp 4 
sw $a0 0($sp) 
addiu $sp $sp -4 
jal fib_entry 
lw $t1 4($sp) 
add $a0 $a0 $t1 
addiu $sp $sp 4 
b endIf2 
thenBranch2: 
li $a0 1 
endIf2: 
b endIf1 
thenBranch1: 
li $a0 0 
endIf1: 
lw $ra 4($sp) 
addiu $sp $sp 12 
lw $fp 0($sp) 
jr $ra 

Answer 1

各種問題與該代碼。

1. 你應該遞減前$sp你寫($sp)（雖然這只是按照慣例）
2. 你應該前節省$fp修改它（這是常識;））
3. MIPS通常使用寄存器來傳遞參數（但您可以將 當作自己的約定）
4. 您的堆棧處理過程非常複雜，至少我ñmain這是不平衡的
5. 我們建議從main返回並嘗試生成一些之前未使用exit系統調用

當然，你應該能夠編寫和調試彙編代碼。

給定的輸入結構是這樣的C實現：

unsigned fib_entry(unsigned n) { 
    unsigned ret; 
    unsigned n1; 
    unsigned f1; 
    unsigned n2; 
    unsigned f2; 

    if (n <= 1) goto fib_small; 

    n1 = n - 1; 
    f1 = fib_entry(n1); 
    n2 = n - 2; 
    f2 = fib_entry(n2); 
    ret = f1 + f2; 
    goto fib_done; 

fib_small: 
    ret = n; 

fib_done: 
    return ret; 
} 

我希望一個不太聰明的編譯器能產生這樣的代碼：

fib_entry: 
    addiu $sp $sp -28 # we need room for $ra, n, ret, n1, n2, f1, f2 
    sw $ra, 24($sp)  # store $ra since not leaf function 
    sw $a0, 20($sp)  # store n 

    lw $t0, 20($sp)  # load n 
    ble $t0 1 fib_small 

    lw $t0, 20($sp)  # load n 
    addi $t0 $t0 -1  # n - 1 
    sw $t0, 12($sp)  # store as n1 

    lw $a0, 12($sp)  # pass n1 as argument 
    jal fib_entry 
    sw $v0 4($sp)  # store into f1 

    lw $t0, 20($sp)  # load n 
    addi $t0 $t0 -2  # n - 2 
    sw $t0, 8($sp)  # store as n2 

    lw $a0, 8($sp)  # pass n2 as argument 
    jal fib_entry 
    sw $v0 ($sp)  # store into f2 

    lw $t0 4($sp)  # f1 
    lw $t1 ($sp)  # f2 
    addu $t0 $t0 $t1 # f1 + f2 
    sw $t0 16($sp)  # store into ret 

    b fib_done 

fib_small: 
    lw $t0, 20($sp)  # load n 
    sw $t0 16($sp)  # store into ret 

fib_done: 
    lw $v0 16($sp)  # load return value 
    lw $ra 24($sp)  # restore $ra 
    addiu $sp $sp 28 # restore stack 
    jr $ra    # return 

注意我故意離開它未優化。這種代碼應該足夠簡單以生成。