Loop unswitching

Last updated

Loop unswitching is a compiler optimization. It moves a conditional statement inside a loop outside 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 enhances loop's parallelization. As modern processors can efficiently handle vectors, this optimization increases program speed.

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:

boolw;intx[1000];inty[1000];for(inti=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:

boolw;intx[1000];inty[1000];if(w){for(inti=0;i<1000;i++){x[i]+=y[i];y[i]=0;}}else{for(inti=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

  1. Cooper, Keith; Torczon, Linda (2004). Engineering a Compiler. Elsevier. ISBN   9781558606982.
  2. "GCC 3.4 Release Series — Changes, New Features, and Fixes - GNU Project".