Loop Unrolling and Fibonacci: Consider the Following Pseudo-C Code to Compute

question 12

Essay

Loop Unrolling and Fibonacci: Consider the following pseudo-C code to compute the fifth Fibonacci number (F(5)).
1 int a,b,i,t;
2 a=b=1; /* Set a and b to F(2) and F(1) respectively */ 3 for(i=0;i<2;i++)
4 {
5 t=a; /* save F(n-1) to a temporary location */ 6 a+=b; /* F(n) = F(n-1) + F(n-2) */
7 b=t; /* set b to F(n-1) */ 8 }
One observation that a compiler might make is that the loop construction is somewhat unnecessary. Since the the range of the loop indices is fixed, one can unroll the loop by simply writing three iterations of the loop one after the other without the intervening increment/comparison on i. For example, the above could be written as:
1 int a,b,t;
2 a=b=1;
3 t=a;
4 a+=b;
5 b=t;
6 t=a;
7 a+=b;
8 b=t;
(a) Convert the pseudo-C code for both of the snippets above into reasonably efficient MIPS code. Represent each variable of the pseudo-C program with a register. Try to follow the pseudo-C code as closely as possible (i.e. the first snippet should have a loop in it, while the second should not).
(b) Now suppose that instead of the fifth Fibonacci number we decided to compute the 20th. How many static instructions would there be in the first version and how many would there be in the unrolled version? What about dynamic instructions? You do not need to write out the assembly for this part.