On 08/02/2017 12:52 PM, Yury Gribov wrote: > On Wed, Aug 2, 2017 at 11:42 AM, Martin Liška <mli...@suse.cz > <mailto:mli...@suse.cz>> wrote: > > On 08/02/2017 11:53 AM, Jan Hubicka wrote: > > Hello, > > sorry for not responding for a while. Martin Liska has patch to move > switch > > expansion to gimple level that will likely simplify the code > combinatoin. > > Hello. > > Yep, will land today to gcc-patches mailing list. > > > > >> > >> combine_predictions_for_bb calculates final probability for edges of > >> if-else or switch statements. > >> > >> For if-elses this is done by combining values computed by different > >> predictors using Dempster-Shafer theory. For switch statement DS is > >> not used, mainly because we do not have heuristics for predicting > >> which case will be taken (paper by Larus concluded that using if-else > >> heuristics does not give good results). > >> > >> So until this patch we just used set_even_probabilities. The name of > >> this function is misleading, in addition to setting even probabilities > >> it can also understand that some edges are very unlikely and set > >> unlikely probs for those. With patch it now also understands that one > >> edge is very likely. > > > > I am not sure that the conclusion of Ball&Larus paper applies to us > here. > > In addition to usual if-then-else heuristics we have those based on walk > > of CFG (such as ones predicting paths to unlikely calls) and those > should > > work well on switch statements. > > > > We discussed adding predictor combining code for BBs with more than 2 > > successors. Martin, do you have some code for that? > > This has been discussed and we decided to reject that as we're unable to > apply DS theory as we can't evaluate what probability has a predictor for > edges different from the edge which it can evaluate. Note that with 2 > edges > and probability x, one can calculate probability of the second edge > simply by 1 - x. That's not doable if one has > 2 edges. > > > Did you consider splitting 1 - x equally among alternatives?
That's quite obvious simplification. I'll take a look one more time what was problematic there. Thanks, Martin > > > That was reason > why I decided to use DF theory for such situations and wrote just simple > handling of very {un,}likely probabilities. > > Maybe I overlooked something in understanding of DF theory? > > Martin > > > > > I guess teaching even propbabilities about likely edges also works, but > > perhaps doing more general prediction combining would be cleaner... > > > > Honza > > > >