This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][PR 59521] Respect probabilities when expanding switch statement
- From: Martin Liška <mliska at suse dot cz>
- To: Jan Hubicka <hubicka at ucw dot cz>, Yuri Gribov <tetra2005 at gmail dot com>
- Cc: GCC Patches <gcc-patches at gcc dot gnu dot org>, marxin at gcc dot gnu dot org
- Date: Wed, 2 Aug 2017 12:42:20 +0200
- Subject: Re: [PATCH][PR 59521] Respect probabilities when expanding switch statement
- Authentication-results: sourceware.org; auth=none
- References: <CAJOtW+5-v6twsrRbLc7qQwkGt6TM8iu-hphznjGDMpWoxG6aLw@mail.gmail.com> <20170718074519.GA55807@kam.mff.cuni.cz> <CAJOtW+5TZz2zyHoW0ATbnhCsaHvfUBf970W1h9rTE8C7-rqD9w@mail.gmail.com> <20170802095336.GD98370@kam.mff.cuni.cz>
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. 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
>