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
