Loop unrolling

Optimizing compilers will sometimes perform the unrolling automatically, or upon request.

Manual (or static) loop unrolling involves the programmer analyzing the loop and interpreting the iterations into a sequence of instructions which will reduce the loop overhead. This is in contrast to dynamic unrolling which is accomplished by the compiler.

But of course, the code performed need not be the invocation of a procedure, and this next example involves the index variable in computation:

In general, the content of a loop might be large, involving intricate array indexing. These cases are probably best left to optimizing compilers to unroll. Replicating innermost loops might allow many possible optimisations yet yield only a small gain unless n is large.

In this case, unrolling is faster because the ENDWHILE (a jump to the start of the loop) will be executed 66% less often.

Even better, the "tweaked" pseudocode example, that may be performed automatically by some optimizing compilers, eliminating unconditional jumps altogether.

In this example, approximately 202 instructions would be required with a "conventional" loop (50 iterations), whereas the above dynamic code would require only about 89 instructions (or a saving of approximately 56%). If the array had consisted of only two entries, it would still execute in approximately the same time as the original unwound loop. The increase in code size is only about 108 bytes – even if there are thousands of entries in the array.

It is, of course, perfectly possible to generate the above code "inline" using a single assembler macro statement, specifying just four or five operands (or alternatively, make it into a library subroutine, accessed by a simple call, passing a list of parameters), making the optimization readily accessible.

The following example demonstrates dynamic loop unrolling for a simple program written in C. Unlike the assembler example above, pointer/index arithmetic is still generated by the compiler in this example because a variable (i) is still used to address the array element. Full optimization is only possible if absolute indexes are used in the replacement statements.

/* Note that this number is a 'constant constant' reflecting the code below. *//* get repeat times required to do most processing in the while loop *//* Use a switch statement to process remaining by jumping to the case label */

Code duplication could be avoided by writing the two parts together as in Duff's device.

The following is MIPS assembly code that will compute the dot product of two 100-entry vectors, A and B, before implementing loop unrolling. The code below omits the loop initializations:

Note that the size of one element of the arrays (a double) is 8 bytes.

The following is the same as above, but with loop unrolling implemented at a factor of 4. Note again that the size of one element of the arrays (a double) is 8 bytes; thus the 0, 8, 16, 24 displacements and the 32 displacement on each loop.