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

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