Re: PRE in gcse.c

[Jamie Lokier <egcs at tantalophile dot demon dot co dot uk>]

On Mon, Nov 09, 1998 at 04:08:05PM +0100, Andi Kleen wrote:
> Program flow optimization: use profile feedback/__builtin_expect to 
> generate code that doesn't jump at all for the fast path and moves all 
> infrequently called code out of line. 

Oh, __builtin_expect, I like the sound of that.  Would that be
__builtin_expect(expr) asserting that expr is expected to be non-zero?

As in:

   __builtin_expect(i != 0);
   if (i) { ... } else { ... }

   __builtin_expect(2 < x < 10);
   switch (x) { case 1: ... case 2: ... case 3: ... ... case 10: ... };

and so on?

Although for code that is executed at all during a typical run,
optimising from profile information is probably a lot easier _and_ more
reliable than using this kind of program annotation.

> I don't know if that would be enough for a Master's (it is definitely
> not a new technique), but it would be very nice to have in egcs because
> it is very important for good performance (currently it can be done by hand
> with gotos, but that it ugly) and for new CPUs like the Merced or the Alpha.

Actually it has scope for being faster than gotos.

  (a) You can jump to code in another section for code marked "extremely
unlikely" (or profiled to be extremely unlikely).  See Linux kernel SMP
lock functions for examples.  This minimises cache footprint for the
fast paths.

  (b) For "unlikely", you can jump to code beyond the normal return
sequence of the current function.  Whether that occurs now depends on
when the target's return sequences are merged.  If seen GCC 2.7.2 do the
wrong thing (i.e., what I didn't want) with i386 return sequences.

  (c) Currently there's no way to jump beyond the end of the caller from
the slow part of an inline function, not even with hand-crafted gotos.
This is worthwhile even if the slow case is just a call to an out of
line function, so that there are no branches taken (or mispredicted) in
the fast case.

  (d) Loop rearrangement and unrolling could also benefit from profile
driven optimisation.

  (e) Existing optimisations that rearrange, split or merge code could
benefit, in addition to perhaps a whole new "rearrange by likelihood"
pass.

Oh yes, and I wonder if cache profiling, that is measuring which bits of
code cause cache and TLB misses, can help direct the rearrangement of
code.  Wouldn't that be nice?

Thought for the day,
-- Jamie