From: "Martin Liška" <mliska@suse.cz>
To: Yury Gribov <tetra2005.patches@gmail.com>
Cc: Jan Hubicka <hubicka@ucw.cz>, Yuri Gribov <tetra2005@gmail.com>,
GCC Patches <gcc-patches@gcc.gnu.org>,
marxin <marxin@gcc.gnu.org>
Subject: Re: [PATCH][PR 59521] Respect probabilities when expanding switch statement
Date: Wed, 02 Aug 2017 10:54:00 -0000 [thread overview]
Message-ID: <778a5afa-ea21-7397-6553-198453cd483b@suse.cz> (raw)
In-Reply-To: <CAKuS3ctcmpN7ws_0sym0dQgLUZdi7oYrtWyaYMt3mM6SEgXc0A@mail.gmail.com>
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
> >
>
>
next prev parent reply other threads:[~2017-08-02 10:54 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-07-18 7:04 Yuri Gribov
2017-07-18 7:46 ` Jan Hubicka
2017-07-18 8:39 ` Yuri Gribov
2017-08-02 9:53 ` Jan Hubicka
2017-08-02 10:42 ` Martin Liška
[not found] ` <CAKuS3ctcmpN7ws_0sym0dQgLUZdi7oYrtWyaYMt3mM6SEgXc0A@mail.gmail.com>
2017-08-02 10:54 ` Martin Liška [this message]
2017-07-20 19:42 ` Steven Bosscher
2017-07-21 5:40 ` Yuri Gribov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=778a5afa-ea21-7397-6553-198453cd483b@suse.cz \
--to=mliska@suse.cz \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=marxin@gcc.gnu.org \
--cc=tetra2005.patches@gmail.com \
--cc=tetra2005@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).