replacing the backwards threader and more

[Jeff Law]

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