RE: branch probabilities on multiway branches

["Rahul Kharche" <rahul@IceraSemi.com>]

>>What is the problem you're trying to solve?

Generally speaking I was looking for a better logic based on estimated
branch probability to decide between using binary search tree and jump
table implementation of a switch case.

One interesting test case is where the gross structure of a function
is a switch case. The function is parameterized on input to the switch
i.e. of the following type:

void foo (int val, int arg1, ...)
{
  switch (val)
  {
  case 100: /* blah1 */ break;
  case 101: /* blah2 */ break;
    .
    .
    .
  case 10000: /* blah10000 */ break;

  default:
    ;
  }
}

On the basis of the static call graph, the estimated frequencies of
the calls to foo (), and assuming argument val is constant at each
call site, is it possible to optimize the switch case in foo ()?
Perhaps along the line of pulling out the most frequent case like you
mentioned in your example. Or specializing foo () on frequent cases of
val.

In this case inlining and VRP would have automatically done what I am
suggesting. Inlining however is not attempted because foo () is
estimated to be large.


Many Thanks,
Rahul