In computer science, loop inversion is a compiler optimization and loop transformation in which 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 or avoiding jump instructions to reduce branch mis-prediction.
In a while loop (indefinite iteration), the condition must be tested for each iteration. When the test fails, the loop is exited. By putting the test at the end of the loop body, loop inversion avoids any jumps at the end of the final iteration.
is equivalent to:
No change in performance occurs for initial and non-final iterations through the loop, including when the loop is not entered because the condition is false. However, the final iteration has 2 fewer jump instructions when the loop is entered because the do-while loop does not need to jump to the start of the while loop to evaluate the loop condition.
is equivalent to:
Despite the seemingly greater complexity of the second example, it may actually run faster on modern CPUs because they use an instruction pipeline. By nature, any jump in the code causes a pipeline stall, which is a detriment to performance.
Additionally, loop inversion allows safe loop-invariant code motion.
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:
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:
