Loop unswitching

From Free net encyclopedia

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 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 (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;
 end_for;

The conditional inside this loop makes it hard to safely parallelize this loop. After unswitching this becomes:

 if (w) then
   for i to 1000 do
     x[i] = x[i] + y[i];
     y[i] = 0;
   end_for;
 else
   for i to 1000 do
     x[i] = x[i] + y[i];
   end_for
 end_if;

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.