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

[Jan Hubicka <hubicka at ucw dot cz>]

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.

> 
> 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?

I guess teaching even propbabilities about likely edges also works, but
perhaps doing more general prediction combining would be cleaner...

Honza