branch probabilities on multiway branches

branch probabilities on multiway branches

[Rahul Kharche]

Hi All,

The following bit of code in predict.c implies branch probabilities
are strictly evenly distributed for multiway branches at present. The
comment suggests it is possible to generate better estimates for more
generic cases, apart from being involved. Could anyone point me to
the reference and/or if an implementation exists already.


/* When there is no successor or only one choice, prediction is easy. 

   We are lazy for now and predict only basic blocks with two outgoing
   edges.  It is possible to predict generic case too, but we have to
   ignore first match heuristics and do more involved combining.
Implement
   this later.  */
if (nedges != 2)
  {
    if (!bb->count)
      set_even_probabilities (bb);
    clear_bb_predictions (bb);
    if (dump_file)
      fprintf (dump_file, "%i edges in bb %i predicted to even
probabilities\n",
	       nedges, bb->index);
    return;
  }


Many Thanks,
Rahul

Re: branch probabilities on multiway branches

[Jan Hubicka]

> Hi All,
> 
> The following bit of code in predict.c implies branch probabilities
> are strictly evenly distributed for multiway branches at present. The
> comment suggests it is possible to generate better estimates for more
> generic cases, apart from being involved. Could anyone point me to
> the reference and/or if an implementation exists already.

There is Wu & Larus paper cited in the comment at the begging of file.

Honza

RE: branch probabilities on multiway branches

[Rahul Kharche]

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?


-----Original Message-----
From: Jan Hubicka [mailto:hubicka@ucw.cz] 
Sent: 14 April 2010 00:44
To: Rahul Kharche
Cc: gcc@gcc.gnu.org; sdkteam-gnu
Subject: Re: branch probabilities on multiway branches

> Hi All,
> 
> The following bit of code in predict.c implies branch probabilities
> are strictly evenly distributed for multiway branches at present. The
> comment suggests it is possible to generate better estimates for more
> generic cases, apart from being involved. Could anyone point me to
> the reference and/or if an implementation exists already.

There is Wu & Larus paper cited in the comment at the begging of file.

Honza

Re: branch probabilities on multiway branches

[Steven Bosscher]

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?

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

RE: branch probabilities on multiway branches

[Rahul Kharche]

>>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

RE: branch probabilities on multiway branches

[Rahul Kharche]

The other case I'm working on is to selectively apply tailcall
optimization when optimizing for size. Clearly tail call optimiztion
is desirable along frequently executed edges. Otherwise we found
tailcall optimization generates a sicall_epilogue for each tailcall
which has a significant impact on size. This is true if the generated
epilogue is large. I have a patch which prunes tail calls along edges
which are determined to be infrequently executed from profile
information. When no profile information is available we are reduced
to using a heuristic whether the optimization will increase code size.
However it would be useful to also use estimated branch probabilities
The cases I'm looking at use switch cases heavily where branch
probability information is reduced to even probabilities across all
cases.

We're keen on improving the estimated branch probabilities in switch
cases because we cannot always gather profile information on all code
paths through a program.

Cheers,
Rahul

Re: branch probabilities on multiway branches

[Jan Hubicka]

> 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

RE: branch probabilities on multiway branches

[Rahul Kharche]

Hi Steven,

> 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

Could you point me to the bit of code that does this?

I'm exploring the idea of implementing source hints much like
__builtin_expect which would assign a probability to a case range
in a switch construct. I will have to tweak the case expansion
phase to implement a similar transformation to the one you mentioned
earlier.

Cheers,
Rahul

RE: branch probabilities on multiway branches

[Rahul Kharche]

Thanks Edmar! I will try and work your patch into our GCC 4.4.1
port and get some results.

Cheers,
Rahul

RE: branch probabilities on multiway branches

[Rahul Kharche]

Hi Edmar,

I have been testing your patch on our port of GCC4.4.1. The patch
works well, although I stumbled on an issue.

Many of our interesting cases have large case values, so profiling
the default range of values 0 - 255, or even as large as 0 - 2047 is
insufficient. Profiling for a larger ranges is impractical. I am
attempting to use edge frequencies instead of value profile to
effect the same transformation.

We also use an adapted form of the patch below to form sparse clusters
of contiguous large case values and shrink the switch case jump table.
I have merged your work into this patch so we can form a
probability/frequency based balanced decision tree for more likely
cases, and jump tables with clusters otherwise.

http://gcc.gnu.org/ml/gcc-patches/2004-07/msg02479.html


Here's a modified test case from your patch to demonstrate the need
for clusters in addition to cost balanced decision tree.

enum { NEVER=1000, HARDLY=10001, FOO=1002, FOO1=1003, FOO2=1004,
       FOO3=1005, FOO4=1006, OFTEN=2500, BAR=2501, DUMMY=2502,
       DUMMY1=2503, DUMMY2=2504, DUMMY3=2505};

int seq[] = {
  OFTEN, OFTEN, OFTEN, OFTEN, OFTEN, HARDLY,
  BAR, FOO, OFTEN, FOO, OFTEN, HARDLY,
  OFTEN, OFTEN, OFTEN, OFTEN, OFTEN, HARDLY,
  OFTEN, OFTEN, OFTEN, OFTEN, OFTEN, HARDLY,
  OFTEN, OFTEN, OFTEN, OFTEN, OFTEN, HARDLY,
  300, -1, OFTEN, OFTEN, OFTEN, OFTEN, HARDLY,
};
int result;

int
test_it (int k, int i)
{
  int j;

  j = k;
    switch (seq[i])
    {
    case NEVER:
      j = j * i;
      break;
    case FOO:
      j = j + k;
      break;
    case FOO1:
      j = j + k<<2;
      break;
    case FOO2:
      j = j + k<<5;
      break;
    case FOO3:
      j = j + k<<6;
      break;
    case FOO4:
      j = j + k<<7;
      break;
    case BAR:
      j = j + i + k;
    case DUMMY:
      j = j * (k + i);
      break;
    case DUMMY1:
      j = j * (k + i<<2);
      break;
    case OFTEN:
      j = j + i;
      break;
    case DUMMY2:
      j = j * (k + i<<5);
      break;
    case DUMMY3:
      j = j * (k + i<<6);
      break;
    default:
      j = j * k;
      break;
    }
  return j;
}

int
main (int argc, char **argv)
{
  int i;
  for (i = 0; i < sizeof(seq)/sizeof(seq[0]); i++)
    result = test_it (1, i);
  return 0;
}


Cheers,
Rahul


-----Original Message-----
From: Rahul Kharche 
Sent: 22 April 2010 11:24
To: Edmar Wienskoski
Cc: Steven Bosscher; Jan Hubicka; gcc@gcc.gnu.org; sdkteam-gnu
Subject: RE: branch probabilities on multiway branches

Thanks Edmar! I will try and work your patch into our GCC 4.4.1
port and get some results.

Cheers,
Rahul