> On Thu, Apr 15, 2010 at 1:11 PM, Rahul Kharche <ra...@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
