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. This can improve the parallization 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 (vectors) and also do something depending on the variable w. We have the following pseudo code:
for i to 1000 do x[i] = x[i] + y[i]; if (w) then y[i] = 0; od;
The conditional inside this loop makes it hard to safely parellize this loop. After unswitching this becomes:
if (w) then
for i to 1000 do
x[i] = x[i] + y[i];
y[i] = 0;
od;
else
for i to 1000 do
x[i] = x[i] + y[i];
od
fi;
Each of these new loops can be separately optimized. Note that loop unswitching will double the amount of code generated.
Loop unswitching was introduced in gcc in version 3.4.