Loop inversion
In
Example in C
![]() | This section possibly contains original research. (September 2017) |
int i, a[100];
i = 0;
while (i < 100) {
a[i] = 0;
i++;
}
is equivalent to:
int i, a[100];
i = 0;
if (i < 100) {
do {
a[i] = 0;
i++;
} while (i < 100);
}
Despite the seemingly greater complexity of the second example, it may actually run faster on modern
Additionally, loop inversion allows safe loop-invariant code motion.
Example in three-address code
![]() | This section possibly contains original research. (September 2017) |
i := 0 L1: if i >= 100 goto L2 a[i] := 0 i := i + 1 goto L1 L2:
If i had been initialized at 100, the instructions executed at runtime would have been:
if i >= 100
goto L2
Let us assume that i had been initialized to some value less than 100. Now let us look at the instructions executed at the moment after i has been incremented to 99 in the loop:
goto L1
if i < 100
a[i] := 0
i := i + 1
goto L1
if i >= 100
goto L2
<<at L2>>
Now, let's look at the optimized version:
i := 0 if i >= 100 goto L2 L1: a[i] := 0 i := i + 1 if i < 100 goto L1 L2:
Again, let's look at the instructions executed if i is initialized to 100:
if i >= 100
goto L2
We didn't waste any cycles compared to the original version. Now consider the case where i has been incremented to 99:
if i < 100
goto L1
a[i] := 0
i := i + 1
if i < 100
<<at L2>>
As you can see, two gotos (and thus, two pipeline stalls) have been eliminated in the execution.