MIPS 피보나치 재귀 사용하기

Question

필자는 MIPS에서 fibonacci를 작업하고 있으며, 규칙은 문제 해결의 재귀 적 방법을위한 전문을 가지고 있어야합니다. 내 코드가 현재 잘못된 출력을 생성하고 어떤 부분을 편집해야하는지 식별 할 수 없습니다.

.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

그래, 기본 구조와 구성 요소는 정확하지만, 불행히도 많은 버그가있었습니다.

두 가지 버전의 프로그램을 만들었습니다. 하나는 버그를 자세히 설명하는 주석이 있습니다. 그리고, 청소 것들로 두 번째 버전은, 간단하고, 여기에 주석 버전 [무상 스타일의 정리를 용서하십시오]입니다

---

작업 :

.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