From: Jeff Law <jeffreyalaw@gmail.com>
To: Aldy Hernandez <aldyh@redhat.com>,
Richard Biener <richard.guenther@gmail.com>
Cc: GCC Mailing List <gcc@gcc.gnu.org>
Subject: Re: replacing the backwards threader and more
Date: Wed, 9 Jun 2021 14:43:53 -0600 [thread overview]
Message-ID: <bfee0abd-c12f-dd31-f7b5-4d95f4b25e3a@gmail.com> (raw)
In-Reply-To: <b7f167e7-2eda-4be4-78ba-9dc2c224fecf@redhat.com>
On 6/9/2021 2:39 PM, Aldy Hernandez wrote:
>
>
> On 6/9/21 9:47 PM, Jeff Law wrote:
>>
>>
>> On 6/9/2021 9:34 AM, Aldy Hernandez wrote:
>>>
>>>
>>> On 6/9/21 2:09 PM, Richard Biener wrote:
>>>> On Wed, Jun 9, 2021 at 1:50 PM Aldy Hernandez via Gcc
>>>> <gcc@gcc.gnu.org> wrote:
>>>>>
>>>>> Hi Jeff. Hi folks.
>>>>>
>>>>> What started as a foray into severing the old (forward) threader's
>>>>> dependency on evrp, turned into a rewrite of the backwards threader
>>>>> code. I'd like to discuss the possibility of replacing the current
>>>>> backwards threader with a new one that gets far more threads and can
>>>>> potentially subsume all threaders in the future.
>>>>>
>>>>> I won't include code here, as it will just detract from the high
>>>>> level
>>>>> discussion. But if it helps, I could post what I have, which just
>>>>> needs
>>>>> some cleanups and porting to the latest trunk changes Andrew has
>>>>> made.
>>>>>
>>>>> Currently the backwards threader works by traversing DEF chains
>>>>> through
>>>>> PHIs leading to possible paths that start in a constant. When such a
>>>>> path is found, it is checked to see if it is profitable, and if
>>>>> so, the
>>>>> constant path is threaded. The current implementation is rather
>>>>> limited
>>>>> since backwards paths must end in a constant. For example, the
>>>>> backwards threader can't get any of the tests in
>>>>> gcc.dg/tree-ssa/ssa-thread-14.c:
>>>>>
>>>>> if (a && b)
>>>>> foo ();
>>>>> if (!b && c)
>>>>> bar ();
>>>>>
>>>>> etc.
>>>>>
>>>>> After my refactoring patches to the threading code, it is now
>>>>> possible
>>>>> to drop in an alternate implementation that shares the profitability
>>>>> code (is this path profitable?), the jump registry, and the actual
>>>>> jump
>>>>> threading code. I have leveraged this to write a ranger-based
>>>>> threader
>>>>> that gets every single thread the current code gets, plus 90-130%
>>>>> more.
>>>>>
>>>>> Here are the details from the branch, which should be very similar to
>>>>> trunk. I'm presenting the branch numbers because they contain
>>>>> Andrew's
>>>>> upcoming relational query which significantly juices up the results.
>>>>>
>>>>> New threader:
>>>>> ethread:65043 (+3.06%)
>>>>> dom:32450 (-13.3%)
>>>>> backwards threader:72482 (+89.6%)
>>>>> vrp:40532 (-30.7%)
>>>>> Total threaded: 210507 (+6.70%)
>>>>>
>>>>> This means that the new code gets 89.6% more jump threading
>>>>> opportunities than the code I want to replace. In doing so, it
>>>>> reduces
>>>>> the amount of DOM threading opportunities by 13.3% and by 30.7%
>>>>> from the
>>>>> VRP jump threader. The total improvement across the jump threading
>>>>> opportunities in the compiler is 6.70%.
>>>>>
>>>>> However, these are pessimistic numbers...
>>>>>
>>>>> I have noticed that some of the threading opportunities that DOM
>>>>> and VRP
>>>>> now get are not because they're smarter, but because they're
>>>>> picking up
>>>>> opportunities that the new code exposes. I experimented with
>>>>> running an
>>>>> iterative threader, and then seeing what VRP and DOM could
>>>>> actually get.
>>>>> This is too expensive to do in real life, but it at least shows
>>>>> what
>>>>> the effect of the new code is on DOM/VRP's abilities:
>>>>>
>>>>> Iterative threader:
>>>>> ethread:65043 (+3.06%)
>>>>> dom:31170 (-16.7%)
>>>>> thread:86717 (+127%)
>>>>> vrp:33851 (-42.2%)
>>>>> Total threaded: 216781 (+9.90%)
>>>>>
>>>>> This means that the new code not only gets 127% more cases, but it
>>>>> reduces the DOM and VRP opportunities considerably (16.7% and 42.2%
>>>>> respectively). The end result is that we have the possibility of
>>>>> getting almost 10% more jump threading opportunities in the entire
>>>>> compilation run.
>>>>
>>>> Yeah, DOM once was iterating ...
>>>>
>>>> You probably have noticed that we have very man (way too many)
>>>> 'thread' passes, often in close succession with each other or
>>>> DOM or VRP. So in the above numbers I wonder if you can break
>>>> down the numbers individually for the actual passes (in their order)?
>>>
>>> Sure, I can do that. Let me whip up the old branch and gather some
>>> info.
>> I'll save you some time. The jump threaders in VRP are doing the
>> least amount of lifting and the ones we want to kill first. IIRC the
>> one from vrp2 is doing nearly nothing at this point.
>
> Sure, that was going to be my next target.
>
> What are your thoughts on replacing the current backwards threader,
> though? That's basically ready to go.
Going to take a deep dive into it Saturday.
Jeff
next prev parent reply other threads:[~2021-06-09 20:43 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-06-09 11:48 Aldy Hernandez
2021-06-09 12:09 ` Richard Biener
2021-06-09 15:34 ` Aldy Hernandez
2021-06-09 16:18 ` Richard Biener
2021-06-09 19:47 ` Jeff Law
2021-06-09 20:39 ` Aldy Hernandez
2021-06-09 20:43 ` Jeff Law [this message]
2021-06-21 14:40 ` Aldy Hernandez
2021-06-24 16:14 ` Jeff Law
2021-06-25 7:54 ` Richard Biener
2021-06-25 7:58 ` Richard Biener
2021-06-25 16:20 ` Aldy Hernandez
2021-06-25 17:19 ` Martin Sebor
2021-06-28 6:17 ` Aldy Hernandez
2021-06-28 22:29 ` Martin Sebor
2021-06-29 0:32 ` Aldy Hernandez
2021-06-29 22:16 ` Martin Sebor
2021-06-30 6:07 ` Aldy Hernandez
2021-06-28 8:22 ` Richard Biener
2021-06-28 12:05 ` Aldy Hernandez
2021-06-13 21:59 ` Jeff Law
2021-06-14 6:40 ` Richard Biener
2021-06-15 4:03 ` Jeff Law
2021-06-15 5:39 ` Aldy Hernandez
2021-06-15 16:35 ` Jeff Law
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=bfee0abd-c12f-dd31-f7b5-4d95f4b25e3a@gmail.com \
--to=jeffreyalaw@gmail.com \
--cc=aldyh@redhat.com \
--cc=gcc@gcc.gnu.org \
--cc=richard.guenther@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).