Get emulator to correctly execute gcc -Os Fibonacci

[kevinacahalan]

static int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
 
int main()
{
    int n = 6;
    int ans = fib(n);
    // return ans;
    return ans + 100;
}

The following code was partially generated with GCC using the -Os option. The return from main was replaced with a syscall to halt. Branch and load instructions were moved around as needed to undo GCC reorganization of instructions. GCC did instruction reorganization to fill the delay slots. Our emulator does not implement delay slots.

This code should result in 108 in register $2. Currently this code executes forever. There is some fishy bug that needs to be fixed.

fib(int):
        addiu   $sp,$sp,-40
        sw      $18,32($sp)
        sw      $17,28($sp)
        sw      $16,24($sp)
        sw      $31,36($sp)
        move    $16,$4
        move    $17,$4
        move    $18,$0
$L3:
        addi    $5,$zero, 2
        slt     $2,$17,$5
        andi    $2,$16,0x1
        bne     $2,$0,$L5

        addiu   $4,$17,-1
        jal     fib(int)

        addiu   $17,$17,-2
        addu    $18,$18,$2
        b       $L3

$L5:
        lw      $31,36($sp)
        lw      $17,28($sp)
        lw      $16,24($sp)
        addu    $2,$2,$18
        lw      $18,32($sp)
        addiu   $sp,$sp,40
        jr      $31

main:
        addiu   $sp,$sp,-32
        sw      $31,28($sp)
        li      $4,6                        # 0x6
        jal     fib(int)

        lw      $31,28($sp)
        addiu   $2,$2,100
        addiu   $sp,$sp,32
        syscall

Here's the initial GCC generated code:

fib(int):
        addiu   $sp,$sp,-40
        sw      $18,32($sp)
        sw      $17,28($sp)
        sw      $16,24($sp)
        sw      $31,36($sp)
        move    $16,$4
        move    $17,$4
        move    $18,$0
$L3:
        slt     $2,$17,2
        bne     $2,$0,$L5
        andi    $2,$16,0x1

        jal     fib(int)
        addiu   $4,$17,-1

        addiu   $17,$17,-2
        b       $L3
        addu    $18,$18,$2

$L5:
        lw      $31,36($sp)
        lw      $17,28($sp)
        lw      $16,24($sp)
        addu    $2,$2,$18
        lw      $18,32($sp)
        jr      $31
        addiu   $sp,$sp,40

main:
        addiu   $sp,$sp,-32
        sw      $31,28($sp)
        jal     fib(int)
        li      $4,6                        # 0x6

        lw      $31,28($sp)
        addiu   $2,$2,100
        jr      $31
        addiu   $sp,$sp,32

Bugs to look out for:

• Emulation core doing something wrong
• Some instruction being assembled wrong
• Kevin messed up undoing GCC instruction reorganization (unlikely)

[jerrettl]

Not sure what the issue is with the GCC compilation, but I wrote the Fibonacci program myself in assembly and it worked fine, for what it's worth.

Reference code:

static int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
 
int main()
{
    int n = 6;
    int ans = fib(n);
    return ans;
}

Assembly:

main:
        addiu $sp, $sp, -4
        sw $ra, 0($sp)

        ori $a0, $zero, 6 # n = 6
        jal fib
        # Answer will be in $v0.

        lw $ra, 0($sp)
        addiu $sp, $sp, 4
        syscall # End program.


fib:
        addiu $sp, $sp, -20
        sw $s0, 0($sp) # $s0 stores the result of fib(n - 1).
        sw $s1, 4($sp) # $s1 stores the result of fib(n - 2).
        sw $s2, 8($sp) # $s2 stores a copy of n.
        sw $a0, 12($sp) # $a0 stores n.
        sw $ra, 16($sp)

        # Copy n to $s2.
        or $s2, $zero, $a0
        
        # If n <= 1 (or n < 2), return.
        ori $at, $zero, 2
        slt $t0, $s2, $at
        bne $t0, $zero, return_base_case

        # fib(n - 1)
        or $a0, $zero, $s2
        addiu $a0, $a0, -1
        jal fib
        # Save result in $s0.
        or $s0, $zero, $v0

        # fib(n - 2)
        or $a0, $zero, $s2
        addiu $a0, $a0, -2
        jal fib
        # Save result in $s1.
        or $s1, $zero, $v0

        # Add the two results together.
        addu $v0, $s0, $s1
        b return_fib

return_base_case:
        # Copy n to the return value register.
        or $v0, $zero, $s2

return_fib:
        lw $ra, 16($sp)
        lw $a0, 12($sp)
        lw $s2, 8($sp)
        lw $s1, 4($sp)
        lw $s0, 0($sp)
        addiu $sp, $sp, 20
        jr $ra

At the end of this program, $v0 (or $2) will contain 8, for the 6th Fibonacci number.

[jerrettl]

Some relevant Stack Overflow posts you may have already seen:

• https://stackoverflow.com/questions/27528631/how-to-cross-compile-source-code-for-mips-without-delay-slot-implemented
• https://stackoverflow.com/questions/4042517/how-to-turn-off-mips-gcc-automatic-instruction-reordering