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.