Loop inversion

In computer science, loop inversion is a compiler optimization and loop transformation where a while loop is replaced by an if block containing a do..while loop. When used correctly, it may improve performance due to instruction pipelining.

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 instructions executed at runtime would have been:

 1: if i >= 100
 2: 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:

 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 instructions executed if i is initialized to 100:

 1: if i >= 100
 2: goto L2

We didn't waste any cycles compared to the original version. Now consider the case where i has been incremented to 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.