In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, loop inversion is a
compiler optimization
In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power c ...
and
loop transformation in which a
while loop
In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given Boolean condition. The ''while'' loop can be thought of as a repeating if statement.
Overview
The '' ...
is replaced by an
if block containing a
do..while loop. When used correctly, it may improve performance due to
instruction pipelining
In computer engineering, instruction pipelining or ILP is a technique for implementing instruction-level parallelism within a single processor. Pipelining attempts to keep every part of the processor busy with some instruction by dividing inco ...
.
Example in C
int i, a 00
i = 0;
while (i < 100)
is equivalent to:
int i, a 00
i = 0;
if (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
In computer engineering, instruction pipelining or ILP is a technique for implementing instruction-level parallelism within a single processor. Pipelining attempts to keep every part of the processor busy with some instruction by dividing inco ...
. 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
In computer programming, loop-invariant code consists of statements or expressions (in an imperative programming language) that can be moved outside the body of a loop without affecting the semantics of the program. Loop-invariant code motion ( ...
.
Example in three-address code
i := 0
L1: if i >= 100 goto L2
a
:= 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 := 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
:= 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 := 0
i := i + 1
if i < 100
<>
As you can see, two ''goto''s (and thus, two pipeline stalls) have been eliminated in the execution.
{{DEFAULTSORT:Loop Inversion
Compiler optimizations