Loop inversion
Loop inversion is a compiler optimization, a loop transformation, which replaces a while loop by an if block containing a do..while loop.
Example in C
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)
}
At a first glance, this seems like a bad idea: there's more code so it probably takes longer to execute. However, most modern CPUs use a pipeline for executing instructions. By nature, any jump in the code causes a pipeline stall. Let's watch what happens in Assembly-like Three address code version of the above code:
Example in Three-address code
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 order of instructions at runtime would have been:
1: if i >= 100 2: goto L2
On the other hand, if we looked at the order of instructions at the moment when i was assigned value 99, we would have seen:
1: goto L1 2: if i >= 100 3: a[i] := 0 4: i := i + 1 5: goto L1 6: if i >= 100 7: goto L2 8: <<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 order of instructions executed for i equal 100
1: if i >= 100 2: goto L2
We didn't waste any cycles compared to the original version. Now again jump in to when i was assigned value 99:
1: if i < 100 2: goto L1 3: a[i] := 0 4: i := i + 1 5: if i < 100 6: <<at L2>>
As you can see, two gotos (and thus, two pipeline stalls) have been eliminated in the execution.
Additionally, Loop Inversion allows safe loop-invariant code motion to be performed.
Example in C
int i, n;
int x[10], y, z;
...
while (i < 10) {
x[i] = y + z;
i++;
}
In the example above, the expression x[i] = y + z; is loop-invariant, but cannot be safely moved outside the loop: i < 10 acts as a guard and does not allow x[i] = y + z to execute if i >= 10 was true at the first moment we appeared at the while loop. Executing such code is very dangerous. If we perform Loop Inversion, however, we can safely move the invariant outside the loop:
int i, n;
int x[10], y, z;
...
if (i < 10) {
x[i] = y + z;
do {
i++;
} while (i < 10)
}