Loop unswitching is a compiler optimization

Compiler optimization

Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...

. 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. This can improve the parallelization of the loop. Since modern processors can operate fast on vectors this increases the 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

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

 code:


int i, w, x[1000], y[1000];
for (i = 0; i < 1000; i++) {
x[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] = x[i] + y[i];
y[i] = 0;
}
} else {
for (i = 0; i < 1000; i++) {
x[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

GNU Compiler Collection

The GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...

in version 3.4.