재귀 피보나치 어셈블리 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

다양한 문제 : 여기

코드이다.

당신이 당신이 전에 $fp 을 저장해야
1. 당신이 그것을 (이 상식입니다) 수정 (이것은 단지 관례이지만) 당신이 ($sp)에 기록 전에 $sp을 감소시키는해야
2. )
3. 당신의 스택 처리는 적어도 끔찍하게 overcomplicated이며,
4. MIPS는 일반적으로 인수를 전달하는 레지스터를 사용 (하지만 과정의 수는 자신의 규칙을 구성하는) 내가 N main이 main에서 반환하고 일부를 생성하기 전에 당신은 물론 디버그 ASM 코드를 쓸 수 있어야 exit 콜

를 사용하지 않도록 권장

불균형이다.

을 감안할 때이 C 구현 등의 입력 구조 뭔가 : 나는 일부러 남아있는

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 

참고 : 나는하지 너무나 영리한 컴파일러는이 같은 코드를 생성하는 기대

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; 
} 

최적화되지 않았다. 이런 종류의 코드는 생성하기에 충분히 단순해야합니다.