Value profile based optimizations

Value profile based optimizations are transformations the compiler can make where value profile information is used to identify and exploit properties of expressions that are hard to analyze statically. Usually, these transformations prepend expensive instructions with a branch. In one arm of the branch you have the expensive instruction, and in the other arm you have equivalent but less expensive instructions for the common case, ie. the case that occurs significantly more than any other according to the value profile.

Some examples of the transformations GCC can do or that we plan to implement:

Simplifying divide and modulo instructions.

Divide and modulo instructions are usually expensive. But we can transform some cases to cheaper instructions, e.g.

   x = a/b // where b is almost always a constant N.

This can be transformed to

   if (b == N)
     x = a / N;
   else
     x = a / b;

Loop versioning

It is easy to transform a loop that almost always rolls N times to a pair of loops, where one loop rolls N times and the other has the original loop exit condition.

   for (i = 0; i < n; i++)
     ...

This can be transformed to:

   if (n == N)
     for (i = 0; i < N; i++)
       ...
   else
     for (i = 0; i < n; i++)
       ...

This makes the unroller and vectorizer happier. Since this may grow the code significantly, we would have to be very careful here.

Optimize indirect functions.

Indirect calls happen more often than one might expect. Think about C++ vtables, for example. Indirect calls are quite expensive on most architectures because they are hard to predict. With value profiling it may be possible to determine that one particular function is called most of the time via an indirect function call.

It may be profitable to turn such an indirect call into a conditional expression. One arm of the condition calls the often called function directly if the called address is that of that function. The other arm would simply execute the indirect call. If this is done early enough, it might even be possible to inline the often called function.

None: Value_based_transformations (last edited 2008-01-10 19:38:51 by localhost)