branch probabilities on multiway branches

Jan Hubicka hubicka@ucw.cz
Thu Apr 15 22:54:00 GMT 2010


> On Thu, Apr 15, 2010 at 1:11 PM, Rahul Kharche <rahul@icerasemi.com> wrote:
> > The calculate branch probabilities algorithm (1) in the Wu Larus paper
> > also evenly distributes branch probabilities when number of outgoing
> > edges is > 2, e.g. switch cases implemented as jump tables.
> >
> > Are they any known heuristics to generate better branch probabilities
> > in this case?

Well, wu&larus paper has info how to combine probabilities.  Some of the heuristics
(such as predicting paths leading to noreturn call) apply to multiway branches too
and if we combined them, we can use them.

In addition to code in switch expansion (that tries to estimate stuff i.e. based
on frequencies of letters in english text) one can apply value range propagation
(that needs to be modified to propagate discrete value range intervals) or such.

You can look for papers citing Wu&Larus, they list several extra ideas.  When
we was implementing the branch predictor years back, we left this out as bit
too exotic.

Honza



More information about the Gcc mailing list