next up previous
Next: Trichotomy Up: Loop Optimizations Previous: Loop Optimizations

Loops

Moving operations out of a loop may be incorrect, even if they merely replace computations by constants.

  loop for x in range
     if (condition(x)) then 0.0/0.0   //force exception & trap
             else compute(x)
   end

Clearly the 0.0/0.0 is a constant, and hence could be evaluated outside the loop. If it is moved outside the loop, it forces an exception without testing the condition. A moderately clever compiler would try to execute this constant calculation earlier, at compile-time. This would probably remove ANY exceptions at run-time, inserting a NaN.

Any expression that could cause an exception but would not necessarily be evaluated, cannot be moved out of a loop! Here's a trick though..

Loop peeling is when you execute the first iteration of a loop ``unoptimized'' and then re-use the common components in subsequent iterations. For example,

// a and c are loop invariant
for(i=0; i < n; i++)
{ b = a/c;
  <rest of loop>}
gets turned into
// "peeled" first iteration
i=0
if ~(i<n){
t1 = a/c;       // only perform one divide
b = t1
<rest of loop>
i++

// a and c are loop invariant
for(i=1; i < n; i++)
{
  b = t1;
  <rest of loop>
}
}
This optimization preserves the exceptional behavior, but this simplistic version is inadequate in general to preserve behavior if sticky flags are tested and reset in the loop (cf. Borneo admits/yields)

Other ways that ``constant expressions'' could change:

  for i from 0 to 4
     rounding_mode := i  // change rounding 
      a[i]:=f(x)  // compute constant (?) expression
  end
Similar problems may occur when apparently common subexpressions are ``eliminated'' but must maintain their own identities because of mode variations.



Richard J. Fateman
Thu Aug 13 13:55:33 PDT 1998