[PATCH][PR 59521] Respect probabilities when expanding switch statement

[Martin Liška]

On 08/02/2017 12:52 PM, Yury Gribov wrote:
> On Wed, Aug 2, 2017 at 11:42 AM, Martin Liška <mliska@suse.cz <mailto:mliska@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
>     >
> 
>