Feature #3: Loop Unrolling

Description

Loop unrolling is a technique that compilers use to optimize a program’s execution speed. It minimizes the overhead cost of a loop, including frequency of branches and loop maintenance instructions. The idea behind loop unrolling is to replicate the statements inside the loop by the number of times the loop will execute. There are other factors that go into determining how to calculate exactly how many times a loop will run to minimize the number of total instructions.

Suppose a module in your language compiler product already determines how many times a block of code will execute. This module replaces the loops in the intermediate code by adding blocks in the following format: n[statements]. For example, consider the following code snippet:

for (int i=0; i<3; i++) 
    printf("output");

This block of code will be replaced in the intermediate code by the following code snippet:

3[printf("output"); ]

These loops can also be nested. For example, this could be an intermediate code for a nested loop:

2[sum = sum + i; 2[i++; ]]

Now, your job is to translate these blocks of code and replace them with repeated instructions. The following illustration shows how to translate the above-mentioned nested loop block: