Re: branch predictions

[Jeffrey A Law <law at cygnus dot com>]

  In message <20000504073951V.mitchell@codesourcery.com>you write:
  >     Jeffrey> I can think of three heuristics which would work to
  >     Jeffrey> resolve this problem.
  > 
  > I'm no expert on this issue, so take what I say with appropriate
  > grains of salt.
No problem :-)


  >     Jeffrey> 	1. Given two successors, if one unconditionally exits
  >     Jeffrey> and the other does not, then predict the path which does
  >     Jeffrey> not unconditionally exit.
  > 
  >     Jeffrey> 	2. Given two successors, if one passes control to a
  >     Jeffrey> loop that it dominates and the other does not, then
  >     Jeffrey> predict the path to the dominated loop.
  > 
  > I don't like either of these.  I know that I tend to write functions
  > where early exits are actually the normal case.  Take, for example, a
  > symbol-table lookup routine.  Usually, you hash the identifier, and
  > expect to find it in the table.  But, rarely, you're creating a new
  > entry, and you do some more work.
  > 
  > In other words, I'm not convinced this heuristic will be right more
  > than 50% of the time.  I'm not convinced it will be wrong more than
  > 50% of the time either -- to me this just sounds like a slower version
  > of random choice. :-)
  > 
  > But, I'd certainly believe you if you told me that you profiled and
  > found that it was right 75% of the time, or that there was a paper
  > that said so.
They're both common in literature.  Actually #1 is one I hacked into the
delay slot code years ago to keep it from doing some stupid things-- it
had a noticable (positive) impact on performance across a number of
benchmarks.  The problem was I didn't have a firm enough grasp on how to
use dataflow techniques to build the list of blocks which unconditionally
transfer control out of the current function.


  > My guess is that, ultimately, you need profile-directed optimization
  > to really get the kind of branches you mention predicted correctly.
Profiling certainly produces better predictions, though literature tends
show static predictions can get hit rates of roughly 70% (ignoring back
branches for loops, which are easily predicted).

jeff