Loop unswitching
Loop unswitching is a compiler optimization. It moves a conditional inside a loop outside of it by duplicating the loop's body, and placing a version of it inside each of the if and else clauses of the conditional.[1] This can improve the parallelization of the loop. Since modern processors can operate quickly on vectors, this improvement increases the speed of the program.
Here is a simple example. Suppose we want to add the two arrays x and y and also do something depending on the variable w. We have the following C code:
int i, w, x[1000], y[1000]; for (i = 0; i < 1000; i++) { x[i] += y[i]; if (w) y[i] = 0; }
The conditional inside this loop makes it difficult to safely parallelize this loop. When we unswitch the loop, this becomes:
int i, w, x[1000], y[1000]; if (w) { for (i = 0; i < 1000; i++) { x[i] += y[i]; y[i] = 0; } } else { for (i = 0; i < 1000; i++) { x[i] += y[i]; } }
While the loop unswitching may double the amount of code written, each of these new loops may now be separately optimized.
Loop unswitching was introduced in gcc in version 3.4.[2]
References
- v
- t
- e
- Peephole optimization
- Local value numbering
- Automatic parallelization
- Automatic vectorization
- Induction variable
- Loop fusion
- Loop-invariant code motion
- Loop inversion
- Loop interchange
- Loop nest optimization
- Loop splitting
- Loop unrolling
- Loop unswitching
- Software pipelining
- Strength reduction
analysis
- Available expression
- Common subexpression elimination
- Constant folding
- Dead store elimination
- Induction variable recognition and elimination
- Live-variable analysis
- Use-define chain
- Deforestation
- Tail-call elimination