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: <>

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: <>

As you can see, two "goto"s (and thus, two pipeline stalls) have been eliminated in the execution.

Additionally, Loop Inversion allows safe loop-invariant code motion to be performed.