Editing Loop unrolling (section)

==Static/manual loop unrolling==
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.

===Simple manual example in C===
A procedure in a computer program is to delete 100 items from a collection. This is normally accomplished by means of a <code>''for''</code>-loop which calls the function ''delete(item_number)''. If this part of the program is to be optimized, and the overhead of the loop requires significant resources compared to those for the ''delete(x)'' function, unwinding can be used to speed it up.

{| class="wikitable"
!Normal loop
!After loop unrolling
|-style="vertical-align:top"
|
<syntaxhighlight lang="c">
 int x;
 for (x = 0; x < 100; x++)
 {
     delete(x);
 }
</syntaxhighlight>
|
<syntaxhighlight lang="c">
 int x; 
 for (x = 0; x < 100; x += 5)
 {
     delete(x);
     delete(x + 1);
     delete(x + 2);
     delete(x + 3);
     delete(x + 4);
 }
</syntaxhighlight>
|}

As a result of this modification, the new program has to make only 20 iterations, instead of 100. Afterwards, only 20% of the jumps and conditional branches need to be taken, and represents, over many iterations, a potentially significant decrease in the loop administration overhead. To produce the optimal benefit, no variables should be specified in the unrolled code that require [[pointer arithmetic]]. This usually requires "[[Base address|base]] plus offset" addressing, rather than indexed referencing.

On the other hand, this ''manual'' loop unrolling expands the source code size from 3 lines to 7, that have to be produced, checked, and debugged, and the compiler may have to allocate more registers to store variables in the expanded loop iteration {{Dubious|date=December 2009}}. In addition, the loop control variables and number of operations inside the unrolled loop structure have to be chosen carefully so that the result is indeed the same as in the original code (assuming this is a later optimization on already working code). For example, consider the implications if the iteration count were not divisible by 5. The manual amendments required also become somewhat more complicated if the test conditions are variables. See also [[Duff's device]].

===Early complexity===
In the simple case, the loop control is merely an administrative overhead that arranges the productive statements. The loop itself contributes nothing to the results desired, merely saving the programmer the tedium of replicating the code a hundred times which could have been done by a pre-processor generating the replications, or a text editor. Similarly, <code>if</code>-statements and other flow control statements could be replaced by code replication, except that [[code bloat]] can be the result. Computer programs easily track the combinations, but programmers find this repetition boring and make mistakes. 
Consider:

{| class="wikitable"
!Normal loop
!After loop unrolling
|-
|
 for i := 1:8 do
     if i mod 2 = 0 then do_even_stuff(i) 
                    else do_odd_stuff(i);
     next i;
|
 do_odd_stuff(1); do_even_stuff(2);
 do_odd_stuff(3); do_even_stuff(4);
 do_odd_stuff(5); do_even_stuff(6);
 do_odd_stuff(7); do_even_stuff(8);
|}

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

{| class="wikitable"
!Normal loop
!After loop unrolling
|-
|
 x(1) := 1;
 for i := 2:9 do
     x(i) := x(i - 1) * i;
     print i, x(i);
     next i;
|
 x(1) := 1;
 x(2) := x(1) * 2; print 2, x(2);
 x(3) := x(2) * 3; print 3, x(3);
 x(4) := x(3) * 4; print 4, x(4);
 ... etc.
|}

which, if compiled, might produce a lot of code (''print'' statements being notorious) but further optimization is possible. This example makes reference only to ''x(i)'' and ''x(i - 1)'' in the loop (the latter only to develop the new value ''x(i)'') therefore, given that there is no later reference to the array ''x'' developed here, its usages could be replaced by a simple variable. Such a change would however mean a simple variable ''whose value is changed'' whereas if staying with the array, the compiler's analysis might note that the array's values are constant, each derived from a previous constant, and therefore carries forward the constant values so that the code becomes 
 print 2, 2;
 print 3, 6;
 print 4, 24;
 ...etc.

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.

=== Unrolling WHILE loops ===
Consider a pseudocode WHILE loop similar to the following:

{| class="wikitable"
!Normal loop
!After loop unrolling
!Unrolled & "tweaked" loop
|-style="vertical-align:top"
|
 WHILE (condition) DO
     action
 ENDWHILE
 .
 .
 .
 .
 .
 .
|
 WHILE (condition) DO
     action
     IF NOT(condition) THEN GOTO break
     action
     IF NOT(condition) THEN GOTO break
     action
 ENDWHILE
 LABEL break:
 .
|
 IF (condition) THEN
     REPEAT
         action
         IF NOT(condition) THEN GOTO break
         action
         IF NOT(condition) THEN GOTO break
         action
     WHILE (condition)
 LABEL break:
|}
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.