OPEN CATALOG

# Loop unswitching

Loop unswitching is a program optimization technique, where invariant conditions inside loops (i.e. conditions whose value is always the same inside the loop) can be taken outside of the loop by creating copies of the loop.

To illustrate loop unswitching, consider the following example:

``````for (int i = 0; i < n; i++) {
if (debug) {
if (a[i] < 0) {
log_error(“Negative number”);
}
}
b[i] = sqrt(a[i]);
}
``````

In the above example, we are calculating the `sqrt` of elements of `a[i]`. But in case `a[i]` is negative and we are debugging, we want to log an error.

The condition `if (debug)` is loop invariant, since the variable `debug` never changes its value. By doing loop unswitching and moving this condition outside of the loop, the loop becomes faster. Here is the same loop after loop unswitching:

``````if (debug) {
for (int i = 0; i < n; i++) {
if (a[i] < 0) {
log_error(“Negative number”);
}
b[i] = sqrt(a[i]);
}
} else {
for (int i = 0; i < n; i++) {
b[i] = sqrt(a[i]);
}
}
``````

The loop switching was done by replicating the original loop’s body, once for the case where `debug` is true, and another time for the case when `debug` is false.

Compilers can do loop unswitching automatically, under following conditions:

• The condition is loop invariant: although seemingly trivial, in the presence of pointer aliasing, the compiler can omit this optimization.
• There is a limited number of conditions to unswitch: for each condition value, the loop body needs to be duplicated. This can lead to an explosion of code size. If the code grows too large, the compilers can omit this optimization.

In the presence of pointer aliasing or many conditions, it is possible to do this optimization manually.