Loop inversion
{{cleanup_rewrite|date=February 2025}}
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.{{Citation |title=Loop Optimizations in Modern C Compilers |url=http://www.cs.columbia.edu/~ecj2122/research/x86_loop_optimizations/x86_loop_optimizations.pdf |last1=Jubb |first1=Chae}} When used correctly,{{clarification_needed|date=February 2025}} it may improve performance due to instruction pipelining{{citation_needed|date=February 2025}} or avoiding jump instructions to reduce branch mis-prediction.
Example in Java
void pre_inversion() {
while (/* condition */) {
/* loop body */
}
}
is equivalent to:
void post_inversion() {
if (/* condition */) {
do {
/* loop body */
} while (/* condition */);
}
}
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.
Example in C
{{original research|section|date=September 2017}}
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);
}
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. {{citation_needed |reason=Citation implies that a branch predictor can reduce or eliminate the presence of pipeline stalls due to jump instructions, which partially contradicts this sentence.|date=February 2025}}
Additionally, loop inversion allows safe loop-invariant code motion.{{citation_needed |reason=The referenced article uses loop inversion in its example, but no citation is given.|date=February 2025}}{{clarification_needed |reason=Why does loop-invariant code motion matter in context of loop inversion?|date=February 2025}}
Example in three-address code
{{original research|section|date=September 2017}}
{{clarification_needed |reason=This code reads as a compiled version of the example in C, but the linkage between the examples is missing. Details relating these examples or a good source are needed to support this segment.|date=February 2025}}
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:
if i >= 100
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:
goto L1
if i < 100
a[i] := 0
i := i + 1
goto L1
if i >= 100
goto 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:
if i >= 100
goto L2
We didn't waste any cycles compared to the original version. Now consider the case where i has been incremented to 99:
if i < 100
goto L1
a[i] := 0
i := i + 1
if i < 100
<
As you can see, two gotos (and thus, two pipeline stalls) have been eliminated in the execution.
References
{{reflist}}
{{Compiler optimizations}}
{{DEFAULTSORT:Loop Inversion}}