* branch probabilities on multiway branches @ 2010-04-13 16:51 Rahul Kharche 2010-04-14 0:08 ` Jan Hubicka 0 siblings, 1 reply; 10+ messages in thread From: Rahul Kharche @ 2010-04-13 16:51 UTC (permalink / raw) To: gcc; +Cc: sdkteam-gnu 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: branch probabilities on multiway branches 2010-04-13 16:51 branch probabilities on multiway branches Rahul Kharche @ 2010-04-14 0:08 ` Jan Hubicka 2010-04-15 11:56 ` Rahul Kharche 0 siblings, 1 reply; 10+ messages in thread From: Jan Hubicka @ 2010-04-14 0:08 UTC (permalink / raw) To: Rahul Kharche; +Cc: gcc, sdkteam-gnu > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* RE: branch probabilities on multiway branches 2010-04-14 0:08 ` Jan Hubicka @ 2010-04-15 11:56 ` Rahul Kharche 2010-04-15 11:57 ` Steven Bosscher 0 siblings, 1 reply; 10+ messages in thread From: Rahul Kharche @ 2010-04-15 11:56 UTC (permalink / raw) To: Jan Hubicka; +Cc: gcc, sdkteam-gnu 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: branch probabilities on multiway branches 2010-04-15 11:56 ` Rahul Kharche @ 2010-04-15 11:57 ` Steven Bosscher 2010-04-15 14:54 ` Rahul Kharche ` (3 more replies) 0 siblings, 4 replies; 10+ messages in thread From: Steven Bosscher @ 2010-04-15 11:57 UTC (permalink / raw) To: Rahul Kharche; +Cc: Jan Hubicka, gcc, sdkteam-gnu 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* RE: branch probabilities on multiway branches 2010-04-15 11:57 ` Steven Bosscher @ 2010-04-15 14:54 ` Rahul Kharche 2010-04-15 16:59 ` Rahul Kharche ` (2 subsequent siblings) 3 siblings, 0 replies; 10+ messages in thread From: Rahul Kharche @ 2010-04-15 14:54 UTC (permalink / raw) To: Steven Bosscher; +Cc: Jan Hubicka, gcc, sdkteam-gnu >>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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* RE: branch probabilities on multiway branches 2010-04-15 11:57 ` Steven Bosscher 2010-04-15 14:54 ` Rahul Kharche @ 2010-04-15 16:59 ` Rahul Kharche 2010-04-15 22:54 ` Jan Hubicka 2010-04-20 18:20 ` Rahul Kharche 3 siblings, 0 replies; 10+ messages in thread From: Rahul Kharche @ 2010-04-15 16:59 UTC (permalink / raw) To: Steven Bosscher; +Cc: Jan Hubicka, gcc, sdkteam-gnu 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: branch probabilities on multiway branches 2010-04-15 11:57 ` Steven Bosscher 2010-04-15 14:54 ` Rahul Kharche 2010-04-15 16:59 ` Rahul Kharche @ 2010-04-15 22:54 ` Jan Hubicka 2010-04-20 18:20 ` Rahul Kharche 3 siblings, 0 replies; 10+ messages in thread From: Jan Hubicka @ 2010-04-15 22:54 UTC (permalink / raw) To: Steven Bosscher; +Cc: Rahul Kharche, Jan Hubicka, gcc, sdkteam-gnu > 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
* RE: branch probabilities on multiway branches 2010-04-15 11:57 ` Steven Bosscher ` (2 preceding siblings ...) 2010-04-15 22:54 ` Jan Hubicka @ 2010-04-20 18:20 ` Rahul Kharche [not found] ` <l2ld17039311004211227l9c7de73ex9cb83c186a945a51@mail.gmail.com> 3 siblings, 1 reply; 10+ messages in thread From: Rahul Kharche @ 2010-04-20 18:20 UTC (permalink / raw) To: Steven Bosscher; +Cc: Jan Hubicka, gcc, sdkteam-gnu 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
[parent not found: <l2ld17039311004211227l9c7de73ex9cb83c186a945a51@mail.gmail.com>]
* RE: branch probabilities on multiway branches [not found] ` <l2ld17039311004211227l9c7de73ex9cb83c186a945a51@mail.gmail.com> @ 2010-04-22 11:29 ` Rahul Kharche 2010-05-04 12:01 ` Rahul Kharche 0 siblings, 1 reply; 10+ messages in thread From: Rahul Kharche @ 2010-04-22 11:29 UTC (permalink / raw) To: Edmar Wienskoski; +Cc: Steven Bosscher, Jan Hubicka, gcc, sdkteam-gnu Thanks Edmar! I will try and work your patch into our GCC 4.4.1 port and get some results. Cheers, Rahul ^ permalink raw reply [flat|nested] 10+ messages in thread
* RE: branch probabilities on multiway branches 2010-04-22 11:29 ` Rahul Kharche @ 2010-05-04 12:01 ` Rahul Kharche 0 siblings, 0 replies; 10+ messages in thread From: Rahul Kharche @ 2010-05-04 12:01 UTC (permalink / raw) To: Edmar Wienskoski; +Cc: Steven Bosscher, Jan Hubicka, gcc, sdkteam-gnu 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 ^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2010-05-04 12:01 UTC | newest] Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2010-04-13 16:51 branch probabilities on multiway branches Rahul Kharche 2010-04-14 0:08 ` Jan Hubicka 2010-04-15 11:56 ` Rahul Kharche 2010-04-15 11:57 ` Steven Bosscher 2010-04-15 14:54 ` Rahul Kharche 2010-04-15 16:59 ` Rahul Kharche 2010-04-15 22:54 ` Jan Hubicka 2010-04-20 18:20 ` Rahul Kharche [not found] ` <l2ld17039311004211227l9c7de73ex9cb83c186a945a51@mail.gmail.com> 2010-04-22 11:29 ` Rahul Kharche 2010-05-04 12:01 ` Rahul Kharche
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).