MIPS Fibonacci再帰を​​使用して

Question

私はMIPSのフィボナッチで作業しています。問題を解決するための再帰的な方法のプリアンブルが必要です。私のコードは現在、間違った出力を生成しており、編集する部分を特定することはできません。

.text 

main: li $v0, 5 
    syscall 
    move $a0, $v0 
    move $v0, $zero 
    jal fibo 

    move $t2, $v0 
    li $v0, 1 
    move $a0, $t2 
    syscall 

    li $v0, 10 
    syscall 


fibo: ####preamble#### #push from stack 
     subu $sp, $sp, 32 
     sw $ra, 0($sp)  #store return address 
     sw $a0, 4($sp) 
     sw $fp, 8($sp) 
     sw $v0, 12($sp) 
     addu $fp, $sp, 32 
     ####preamble####  

zero: bne $a0, 0, one 
     move $v0, $a0 
     jr $ra 

one: bne $a0, 1, fn1 
     move $v0, $a0 
     jr $ra 

fn1: subi $a0, $a0, 1 #call for fibo(n-1) 
     jal fibo   #recursive 

     lw $a0, 4($sp) 
     addi $a0, $a0, 1 

     subi $a0, $a0, 2 #call for fibo(n-2) 
     jal fibo   

result: lw $ra, 0($sp)  #load ra 
     lw $fp, 8($sp) 
     lw $t0, 12($sp) 
     add $v0, $t0, $v0 
     addu $sp, $sp, 32 
     addu $fp, $fp, 32 
     jr $ra 

Answer 1

さて、あなたは、残念ながら、バグの数があった、基本的な構造や正しいコンポーネントを持っていましたが、。

私はあなたのプログラムの2つのバージョンを作成しました。 1つは、バグを詳述するコメント付きです。そして、クリーンアップの事を有する第二のバージョンは、簡略化され、ここで注釈付きバージョンは、[無償スタイルのクリーンアップをご容赦ください]です

---

作業：

.text 

main: 
    li  $v0,5 
    syscall 
    move $a0,$v0 

    # NOTE/BUG: doing this is unnecessary/wrong if fibo is correct 
    move $v0,$zero 

    jal  fibo 

    move $t2,$v0 
    li  $v0,1 
    move $a0,$t2 
    syscall 

    li  $v0,10 
    syscall 

####preamble#### #push from stack 
fibo: 
    # NOTE/BUG: for simple functions like this, setting up fp is extra work 
    # NOTE/BUG: we want to have extra space in the frame but we don't need 
    # to push/pop for some 
    subu $sp,$sp,32 
    sw  $ra,0($sp)    # store return address 
    sw  $a0,4($sp) 
    sw  $fp,8($sp) 
    sw  $v0,12($sp) 
    addu $fp,$sp,32 
    ####preamble#### 

    # NOTE/BUG: we must zero out t0 so that the add in result: is valid 

    # NOTE/BUG: a stack frame has already been established -- it must be popped 
    # we can _not_ just do a "jr" here 
zero: 
    bne  $a0,0,one 
    move $v0,$a0 
    jr  $ra 

    # NOTE/BUG: a stack frame has already been established -- it must be popped 
one: 
    bne  $a0,1,fn1 
    move $v0,$a0 
    jr  $ra 

fn1: 
    subi $a0,$a0,1    # call for fibo(n-1) 
    jal  fibo     # recursive 

    # NOTE/BUG: we must save the result for fibo(n-1) in our stack frame 

    # NOTE/BUG: this is incorrect -- by doing it, we [effectively] do fibo(n-1) 
    # again (i.e.) (n+1)-2 --> (n-1) and _not_ (n-2) as we wish 
    # do one of these but _not_ both 
    lw  $a0,4($sp) 
    addi $a0,$a0,1 

    subi $a0,$a0,2    # call for fibo(n-2) 
    jal  fibo 

    # NOTE/BUG: fibo(n-1) must be added to fibo(n-2) 

result: 
    lw  $ra,0($sp)    # load ra 
    lw  $fp,8($sp) 

    # NOTE/BUG: this is misplaced because entering this block should already 
    # have v0 set correctly 
    lw  $t0,12($sp) 
    add  $v0,$t0,$v0 

    # NOTE/BUG: the correct way to restore $fp is using: lw $fp,8($sp) 
    addu $sp,$sp,32 
    addu $fp,$fp,32 
    jr  $ra 

ここ

---

が作業バージョンです：

.data 
msg_ask: .asciiz  "Enter n for fibonacci(n) (-1=stop): " 
msg_fibo: .asciiz  "fibonacci(n) is: " 
msg_nl:  .asciiz  "\n" 
    .text 

main: 
    # prompt user 
    la  $a0,msg_ask 
    li  $v0,4 
    syscall 

    # get number from user 
    li  $v0,5 
    syscall 
    move $a0,$v0 
    bltz $a0,main_exit 

    jal  fibo 
    move $t2,$v0     # save the result 

    # print message 
    la  $a0,msg_fibo 
    li  $v0,4 
    syscall 

    # print the result 
    li  $v0,1 
    move $a0,$t2 
    syscall 

    # print message 
    la  $a0,msg_nl 
    li  $v0,4 
    syscall 

    j  main 

main_exit: 
    li  $v0,10 
    syscall 

# fibo -- recursive fibonacci 
# 
# RETURNS: 
# v0 -- fibonacci(n) 
# 
# arguments: 
# a0 -- the "n" for the Nth fibonacci number 
# 
# registers: 
# t0 -- temporary 
fibo: 
    # fibo(0) is 0 and fibo(1) is 1 -- no need to establish a stack frame 
    bgt  $a0,1,fibo_full   # do we need recursion? if yes, fly 
    move $v0,$a0     # no, just set return value 
    jr  $ra      # fast return 

    # establish stack frame 
    # we need an extra cell (to preserve the result of fibo(n-1)) 
fibo_full: 
    # this gives us a temp word at 0($sp) 
    subu $sp,$sp,12    # one more than we need 
    sw  $ra,4($sp) 
    sw  $a0,8($sp) 

    subi $a0,$a0,1    # call for fibo(n-1) 
    jal  fibo     # recursive 
    sw  $v0,0($sp)    # save result in our frame (in extra cell) 

    subi $a0,$a0,1    # call for fibo(n-2) 
    jal  fibo     # recursive 

    lw  $t0,0($sp)    # restore fibo(n-1) from our stack frame 
    add  $v0,$t0,$v0    # result is: fibo(n-1) + fibo(n-2) 

    # restore from stack frame 
    lw  $ra,4($sp) 
    lw  $a0,8($sp) 
    addu $sp,$sp,12 

    jr  $ra      # return