0

モジュールコンパイラでコースワーク用のコードジェネレータを作成しました。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
4

1 に答える 1

2

そのコードに関するさまざまな問題。

  1. 書き込む$sp 前にデクリメントする必要があります($sp)（これは慣例によるものですが）
  2. $fp 変更する前に保存する必要があります（これは常識です;））
  3. MIPSは通常、レジスタを使用して引数を渡します（ただし、もちろん、独自の規則を作成することもできます）
  4. スタックの処理はひどく複雑で、少なくともmainバランスが取れていません
  5. syscallから戻り、syscallmainを使用しないことをお勧めしますexit

もちろん、いくつかを生成する前に、asmコードを記述してデバッグできるはずです。

この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

意図的に最適化せずに残していることに注意してください。この種のコードは、生成するのに十分単純でなければなりません。

于 2012-11-19T18:34:26.523 に答える