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