Assume the following C code. Translate both functions to MIPS using the caller c

Question

Assume the following C code. Translate both functions to MIPS using the caller callee conventions. Do not translate the print statement. Hint: You can "cheat" and treat the global variable as a saved one (say s_0) but you will get extra credit if you do it properly using the global pointer ($gp):

int g=0; /*global variable */

int main(){

int u= fib(3);

printf("%d",g); /*print the number of times you called fib */

}

int fib(int n){

g+=1 /*increase global variable every time you have a funtion call */

if (n==0)

return 0;

else if (n==1)

return 1;

else

return fib(n-1) +fib(n-2);

}

a. What is printed by the previous program?

b. Show the instances of the stack during the execution

c. For arbitrary n what is the formula that gives g (i.e. How many times if fib(n) being called for arbitrary n)? Is fib effective? Explain

d. Rewrite a forLoop definition for fib and translate it to MIPS code.

e. Can you achieve the same effectiveness with a recursive definition? Give a fib implementation that behaves like a for loop given that your compiler optimizes tail calls(hint: the new function should have 3 arguments) .

Explanation / Answer

a) It prints output 5
since fib(3-1) == fib(2) ===> 3 times
since fib(3-2) == fib(1) ===> 2 times

so totally 5 times .. it prints 5

--------------------------------------------------------------
b)

as we pass number input as n == 3

So
fib(n-1) + fib(n-2)
fib(3-1) + fib(3-2)
fib(2) + fib(1)
fib(1) + fib(0) + returns 1
returns 1 + returns 0

-----------------------------------------------------------
c)

g value is given by ...
  
fib(n-1) + fib(n-2) + 2 [extra last conditions whether n = 0 or n = 1]

==> n-1 + n -2 + 2
==> 2n -3 + 2
g ==> 2n-1
----------------------------------------------------------
d)
int fib(int n){
int n, first = 0, second = 1, next, i;

for ( i = 0 ; i < n ; i++ )
{
g++;
if ( i <= 1 )
next = i;
else
{
next = first + second;
first = second;
second = next;
}
}
return next;
}

******* ASSEMBLY ************************
g:
.zero 4
fib(int):
sub sp, sp, #32
str w0, [sp,12]
str wzr, [sp,28]
mov w0, 1
str w0, [sp,24]
str wzr, [sp,16]
b .L2
.L5:
adrp x0, g
add x0, x0, :lo12:g
ldr w0, [x0]
add w1, w0, 1
adrp x0, g
add x0, x0, :lo12:g
str w1, [x0]
ldr w0, [sp,16]
cmp w0, 1
bgt .L3
ldr w0, [sp,16]
str w0, [sp,20]
b .L4
.L3:
ldr w1, [sp,28]
ldr w0, [sp,24]
add w0, w1, w0
str w0, [sp,20]
ldr w0, [sp,24]
str w0, [sp,28]
ldr w0, [sp,20]
str w0, [sp,24]
.L4:
ldr w0, [sp,16]
add w0, w0, 1
str w0, [sp,16]
.L2:
ldr w1, [sp,16]
ldr w0, [sp,12]
cmp w1, w0
blt .L5
ldr w0, [sp,20]
add sp, sp, 32
ret

---------------------------------------------------------------------------------
e)
int fib(int n, int a, int b)
{
g+=1;
if (n == 0) return a;
if (n == 1) return b;
return fib(n - 1, b, a + b);
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.