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?
Probably not.
GCC has some funny heuristics for mutli-way branches itself, but these
heuristics are not used for estimating edge probabilities. They should
be only used to determine the expand order of switch-statements with a
char-typed switch-expr to a series of if-then-else blocks. In practice
they're also used for all integer switch-exprs with case label values
between 0 and 127. See estimate_case_costs. I have no idea whether
this heuristic makes any sense.
Multi-way branches are not predictable in general. Profile information
is much more useful. There is a transformation implemented in GCC's
value profiling to put the most-frequently taken case-label of a
switch-expr at the top of the switch, i.e.
switch (bla) {
case 1: /* happens 1000 times */ blah3; break;
case 2: /* happens 10 times */ blah2; break;
case 3: /* happens 1 times */ blah3; break;
...
}
=>
if (bla == 1) { blah3; } else
switch (bla) {
case 2: /* happens 10 times */ blah2; break;
case 3: /* happens 1 times */ blah3; break;
...
}
but you need profiling for this.
What is the problem you're trying to solve?
Ciao!
Steven
