Re: replacing the backwards threader and more

[Aldy Hernandez <aldyh@redhat.com>]

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.

> 
>> (Note that the new code gets even more opportunities, but I'm only
>> reporting the profitable ones that made it all the way through to the
>> threader backend, and actually eliminated a branch.)
>>
>> The overall compilation hit from this work is currently 1.38% as
>> measured by callgrind.  We should be able to reduce this a bit, plus we
>> could get some of that back if we can replace the DOM and VRP threaders
>> (future work).
>>
>> My proposed implementation should be able to get any threading
>> opportunity, and will get more as range-ops and ranger improve.
>>
>> I can go into the details if necessary, but the gist of it is that we
>> leverage the import facility in the ranger to only look up paths that
>> have a direct repercussion in the conditional being threaded, thus
>> reducing the search space.  This enhanced path discovery, plus an engine
>> to resolve conditionals based on knowledge from a CFG path, is all that
>> is needed to register new paths.  There is no limit to how far back we
>> look, though in practice, we stop looking once a path is too expensive
>> to continue the search in a given direction.
>>
>> The solver API is simple:
>>
>> // This class is a thread path solver.  Given a set of BBs indicating
>> // a path through the CFG, range_in_path() will return the range
>> // of an SSA as if the BBs in the path would have been executed in
>> // order.
>> //
>> // Note that the blocks are in reverse order, thus the exit block is
>> path[0].
>>
>> class thread_solver : gori_compute
>> {
>>
>> public:
>>     thread_solver (gimple_ranger &ranger);
>>     virtual ~thread_solver ();
>>     void set_path (const vec<basic_block> *, const bitmap_head *imports);
>>     void range_in_path (irange &, tree name);
>>     void range_in_path (irange &, gimple *);
>> ...
>> };
>>
>> Basically, as we're discovering paths, we ask the solver what the value
>> of the final conditional in a BB is in a given path.  If it resolves, we
>> register the path.
>>
>> A follow-up project would be to analyze what DOM/VRP are actually
>> getting that we don't, because in theory with an enhanced ranger, we
>> should be able to get everything they do (minus some float stuff, and
>> some CSE things DOM does).  However, IMO, this is good enough to at
>> least replace the current backwards threading code.
>>
>> My suggestion would be to keep both implementations, defaulting to the
>> ranger based, and running the old code immediately after-- trapping if
>> it can find any threading opportunities.
> 
> But due to iteration uncovering new opportunities this will inevitably
> break, no?

No, actually because I'm comparing current and new backwards threader 
behavior on the same IL, something I can't do with VRP because the IL is 
slightly different (VRP asserts).

So I can compare apples to apples in the backwards threader code.  What 
I do is run the new code first, and then run the old code on the same IL 
before the threader has altered the CFG, while asserting that the old 
code cannot register any "new" paths not already present in the registry.

I have tested this assertion throughout 200+ .ii files from a bootstrap, 
and there has never been a case where the old code can get something we 
can't.

> 
>> After a few weeks, we could
>> kill the old code.
> 
> Note that for analyzing threadings done apart from looking at overall
> numbers the statistics infrastructure can be useful, likewise could
> be the opt-info one where you can diff stats based on file or function
> (statistics) or even location of a participating jump (opt-info).
> 
> If you are re-using tree-ssa-thread{edge,update}.{c,h} anyway you
> probably only have to amend one or two places.  I'm personally
> breaking things down to file/function via statistics to spot gross
> differences more locally.

I am indeed re-using all of tree-ssa-thread{edge,update}.  That is 
unchanged.  I've been using the overall statistics plus an awk script to 
collate it all.  But thanks for the opt-info tip.  I didn't know about that.

> 
> IMHO removing threading from VRP (as a step to make "VRP"
> into another EVRP run) should be part of the initial transition,
> there's always a thread pass nearby.  Performing threading from
> EVRP itself might be another option to evaluate.  Trimming down
> the number of (now backwards-)threaders would be another goal.

Agreed.  I will have to sit down and investigate what VRP is getting. 
Last I peeked it was either stuff range-ops could be taught, or 
unconditional jumps to unconditional jumps that could be easily handled. 
  However, I think we can prove that the current backwards threader code 
cannot get anything in the presence of the new code, and could be easily 
replaced before concentrating on DOM/VRP.

That being said, figuring out exactly the discrepancies with DOM/VRP is 
on my short-term radar ;-).

Aldy