Loop inversion
From Wikipedia, the free encyclopedia
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.[1] When used correctly,[clarification needed] it may improve performance due to instruction pipelining[citation needed] or avoiding jump instructions to reduce branch 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.
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.[1]
