This article does not cite any sources. Please help improve this articlebyadding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Loop inversion" – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message) |
Incomputer 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.
This section possibly contains original research. Please improve itbyverifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (September 2017) (Learn how and when to remove this message)
|
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.
Additionally, loop inversion allows safe loop-invariant code motion.
This section possibly contains original research. Please improve itbyverifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (September 2017) (Learn how and when to remove this message)
|
i := 0
L1: if i >= 100 goto L2
a[i] := 0
i := i + 1
goto L1
L2:
Ifi 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
<<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:
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
<<at L2>>
As you can see, two gotos (and thus, two pipeline stalls) have been eliminated in the execution.