RE: [cygnus.project.sid] branch probability hinting

["Boehm, Hans" <hans_boehm at hp dot com>]

My intuition is that theoretically even a 50-50 frequency specification is
useful:

- It gives information to the register allocator about the relative
importance of allocating different live ranges to registers.  It tells you
that both branches matter.  If you see:

	for (...) { ... if (50-50 branch) use global g1 else use global g2
... }

you want both g1 and g2 in registers.  If you predicted the branch to go one
specific way 99% of the time, you'd probably only keep one in a register, at
least if the register use is not free.

- It lets you get better static approximations to execution frequency for
inline expansion, etc.
If you see:

  	if (50-50 branch) call to inlinable function g else different call
to g

and the inline expansion of g is substantially bigger than the calling code,
you probably want to inline either both or neither call.  If you predict the
branch always goes one way, it would make sense to inline just the
frequently executed one.

- I believe that for IA64 if you have a good static prediction either way,
you can win by using the "statically predict taken" or "statically predict
not taken" hint, which I think frees up branch prediction resources.  For an
unknown branch, you should use dynamic prediction.  (If it's really 50-50,
with no regularity in the branch direction, that won't help either.
Hopefully that doesn't happen too often.)

I know very little about the current gcc back end.  I'll believe that a
50-50 hint currently doesn't help.  But it would be nice to design this
facility so that the right information could be supplied.

Hans

> -----Original Message-----
> From: Jeff Sturm [mailto:jsturm@one-point.com]
> Sent: Monday, March 05, 2001 8:56 PM
> To: Tom Tromey
> Cc: Boehm, Hans; 'Andrew Haley'; Java Discuss List
> Subject: Re: [cygnus.project.sid] branch probability hinting
> 
> 
> 
> 
> On 5 Mar 2001, Tom Tromey wrote:
> > Hans> How do you tell gcc that the branch probability is 
> around 50-50
> > Hans> if it already believes otherwise?  (E.g. half the 
> child pointers
> > Hans> in a binary tree are NULL.)
> > 
> > I don't think there is a way.  Maybe this should be 
> reported as a gcc
> > bug.  Maybe you ought to be able to tell __builtin_expect the
> > probability that the branch is taken.
> 
> If I understand right, GCC takes branch probabilities into account
> during a basic block reordering pass.  50-50 cannot be expressed by
> simple reordering.
> 
> Out of curiosity, are there any targets that can make use of a 50-50
> branch probability?  IA-64 perhaps?
> 
> Jeff
> 
>