 | This articlemay need to be rewritten to comply with Wikipedia'squality standards. Relevant discussion may be found on thetalk page.You can help. The talk page may contain suggestions.(February 2025) |
Incomputer science,loop inversion is acompiler optimization andloop transformation in which awhile loop is replaced by anif block containing ado..while loop.[1] When used correctly,[clarification needed] it may improve performance due toinstruction pipelining[citation needed] or avoidingjump instructions to reducebranch mis-prediction.[1]
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.
voidpre_inversion(){while(/* condition */){/* loop body */}}
is equivalent to:
voidpost_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.[1]
 | This sectionmay containoriginal research. Pleaseimprove it byverifying the claims made and addinginline citations. Statements consisting only of original research should be removed.(September 2017) (Learn how and when to remove this message) |
inti,a[100];i=0;while(i<100){a[i]=0;i++;}
is equivalent to:
inti,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 modernCPUs because they use aninstruction pipeline. By nature, any jump in the code causes apipeline stall, which is a detriment to performance.[citation needed]
Additionally, loop inversion allows safeloop-invariant code motion.[citation needed][clarification needed]
| This sectionmay containoriginal research. Pleaseimprove it byverifying the claims made and addinginline 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 thati had been initialized to some value less than 100. Now let us look at the instructions executed at the moment afteri 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 ifi is initialized to 100:
if i >= 100 goto L2
We didn't waste any cycles compared to the original version. Now consider the case wherei has been incremented:
if i < 100 goto L1 a[i] := 0 i := i + 1 if i < 100 <<at L2>>As you can see, twogotos (and thus, two pipeline stalls) have been eliminated in the execution.