Re: replacing the backwards threader and more

[Jeff Law <jeffreyalaw@gmail.com>]

On 6/9/2021 5:48 AM, Aldy Hernandez 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.
Right.  And these kinds of cases are particularly interesting to capture 
-- not only do you remove the runtime test/compare, all the setup code 
usually dies as well.  I can't remember who, but someone added some bits 
to detect these cases in DOM a while back and while the number of 
additional jumps threaded wasn't great, the overall impact was much 
better than we initially realized.   Instead of allowign removal of a 
single compare/branch, it typically allowed removal of a chain of 
logicals that fed the conditional.

>
> 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.
Sweet.

>
> 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.
Yea, I'm not surprised that the relational query helps significantly 
here.  And I'm not surprised that we can do much better with the 
backwards threader with a rewrite.

Much of the ranger design was with the idea behind using it in the 
backwards jump threader in mind.  Backwards threading is, IMHO, a much 
better way to think about the problem.  THe backwards threader also has 
a much stronger region copier -- so we don't have to live with the 
various limitations of the old jump threading approach.



>
> 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%.
This looks good at first glance.  It's worth noting that the backwards 
threader runs before the others, so, yea, as it captures more stuff I 
would expect DOM/VRP to capture fewer things.    It would be interesting 
to know the breakdown of things caught by VRP1/VRP2 and how much of that 
is secondary opportunities that are only appearing because we've done a 
better job earlier.

And just to be clear, I expect that we're going to leave some of those 
secondary opportunities on the table -- we just don't want it to be too 
many :-)  When I last looked at this my sense was wiring the backwards 
threader and ranger together should be enough to subsume VRP1/VRP2 jump 
threading.

>
> 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.
>
> (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.)
Thanks for clarifying that.  It was one of the questions that first 
popped into my mind.

>
> 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).
Given how close we were to dropping the VRP threaders before, I would 
support dropping them at the same time.  That gives you a bit more 
compile-time budget.

>
> 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.
Right.  That's one of the great things about Ranger -- it can 
dramatically reduce the search space.

>
> 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.
Exactly.  Given a path, do we know enough to resolve the conditional at 
the end.  If so register the path as a potential jump threading opportunity.

>
> 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.
I bet it's going to be tougher to remove DOM's threader.  It knows how 
to do thinks like resolve memory references using temporary equivalences 
and such.  But I bet it's enough to drop the VRP based threaders.

>
> 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.  After a few weeks, we could 
> kill the old code.
I can live with that :-)

> p.s. BTW, ranger-based is technically a minomer.  It's gori based.  We 
> don't need the entire ranger caching ability here.  I'm only using it 
> to get the imports for the interesting conditionals, since those are 
> static.
That's probably sufficient to capture the first order effects.  I can 
come up with theoritical cases that it'd likely miss (involving 
temporary equivalences which could affect the set of interesting 
conditionals), but I doubt they're important in practice.

jeff