Re: branch predictions

[Mark Mitchell <mark at codesourcery dot com>]

>>>>> "Jeffrey" == Jeffrey A Law <law@cygnus.com> writes:


    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.

    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.

    Jeffrey> 	3. If we do not have any kind of prediction and one of
    Jeffrey> the blocks physically follows the current block, then
    Jeffrey> predict the block which physically follows the current
    Jeffrey> block.  ie, don't rearrange code at random ;-)

That last sentence is quite compelling.

My guess is that, ultimately, you need profile-directed optimization
to really get the kind of branches you mention predicted correctly.

(Now goes back to worrying about front ends...)

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com