Question

Implement the following C code in MIPS assembly. What is the total number of MIPS instructions needed to execute the function?

int fib(int n){

if$\left(n==0\right)$

return 0;

else if$\left(n=1\right)$

return 1;

else

return $fib\left(n-1\right)+fib\left(n-2\right)$
;

}

Short answer

The total number of MIPS instructions needed to execute the function is 38.

Step-by-step solution

MIPS language

MIPS (Microprocessor without Interlocked Pipelined Stages)[1] is a RISC instruction set architecture invented by MIPS Computer Systems, now MIPS Technologies, in the United States. MIPS is available in several versions, including MIPS I, II, III, IV, and V, as well as five MIPS32/64 releases (for 32- and 64-bit implementations, respectively). MIPS architectures were originally 32-bit, although 64-bit versions were eventually developed. MIPS32/64 Release 6 is the most recent version as of April 2017. In addition to the user-mode architecture, MIPS32/64 differentiates from MIPS I–V by establishing the privileged kernel mode System Control Coprocessor.

MIPS instruction for the above function                  

The function fib() returns the integers as the output. The fib() gives the Fibonacci numbers according to the user input. The term of the Fibonacci number is the sum of its last two terms. The MIPS instruction are as belows:

fib:

addiu $sp,$sp,-3 //add immediate.

sw $31,28($sp) // store word from 28^th register in 31th.

sw $fp,24($sp) // store word from 24^th register to frame pointer.

sw $16,20($sp) // store word from 20^th register into 16^th .

move $fp,$sp //move the contents from stack pointer to frame pointer.

sw $4,32($fp) // store the contents fron frame pointer to 4^th register.

lw $2,32($fp) //load the words from frame pointer to 2^nd register

bne $2,$0,.L2 //branch or not equal

nop //does nothing

move $2,$0 //move the contents from 0^th register to 2^nd register.

b .L3 //branch instruction

nop //does nothing

.L2:

lw $3,32($fp) //load word the from frame pointer to 3^rd register.

li $2,1 // 0x1

bne $3,$2,.L4 //branch or not equal

nop //does nothing

li $2,1 // load immediate fron 2^nd register to 1^st register.

b .L3 //branch instruction

nop //does nothing

.L4:

lw $2,32($fp) ) //load contents from frame pointer to 2^nd register.

addiu $2,$2,-13 //add immediate from the 2^nd register.

move $4,$2 //move the contents from the 2^nd register to 4^th register.

jal fib //jump and link

nop //does nothing

move $16,$2 //move the contents from 2^nd register to 16^th .

lw $2,32($fp) //load word from frame pointer to the 2^nd register.

addiu $2,$2,-23 //add immeediate

move $4,$2 //move the contents from 2^nd regitsers to 4^th register.

jal fib //jump and link

nop //does nothing

addu $2,$16,$2 // add immediate

.L3:

move $sp,$fp //move the contents from the frame to stack pointer.

lw $31,28($sp) //load contents from the stack pointer to 31th register.

lw $fp,24($sp) //load contents from stack pointer to frame pointer.

lw $16,20($sp) //load word from stack pointer to 16^th register.

addiu $sp,$sp,323 //add immeediate

jr $31 //unconditionally jump

nop //does nothing

The “nop” in the MIPS instruction is an instruction that does nothing(has no side-effect).

The “lw” in the MIPS instruction is an instruction that loads a word into the register.

The “li” in the MIPS instruction is an instruction that stands for load immediate.

The “addiu” in the MIPS instruction is an instruction that is used to add constants to signed integers when we don’t care about overflow.

The “move” in the MIPS instruction is an instruction that stands for load immediate.

The “jr” in the MIPS instruction is an instruction that causes pc to jump to the contents of the first source register.

The “sw” in the MIPS instruction is an instruction that stands for store word.