RE: branch probabilities on multiway branches

["Rahul Kharche" <rahul at IceraSemi dot com>]

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