More aggressive threading causing loop-interchange-9.c regression

[Jeff Law]

On 9/9/2021 3:21 AM, Aldy Hernandez wrote:
>
>>
>>    /* If this path does not thread through the loop latch, then we are
>>       using the FSM threader to find old style jump threads. This
>>       is good, except the FSM threader does not re-use an existing
>>       threading path to reduce code duplication.
>>
>>       So for that case, drastically reduce the number of statements
>>       we are allowed to copy.  */
>
> *blink*
>
> Woah.  The backward threader has been using FSM threads 
> indiscriminately as far as I can remember.  I wonder what would break 
> if we "fixed it".
?!?  I'm not sure what you're suggesting here.  If you s/FSM 
threader/backwards threader/ in the comment does it make more sense?   
The term FSM really should largely have been dropped as the backwards 
threader was improved to handle more cases.




>
>>
>> so these cases should use the "old style" validity/costing metrics 
>> and thus
>> classify threading opportunities in a different way?
>
> Jeff, do you have any insight here?
This is precisely what you're cleaning up.


>
>>
>> I think today "backwards" vs, "forwards" only refers to the way we find
>> threading opportunities.
>
> Yes, it's a mess.
>
> I ran some experiments a while back, and my current work on the 
> enhanced solver/threader, can fold virtually everything the 
> DOM/threader gets (even with its use of const_and_copies, avail_exprs, 
> and evrp_range_analyzer), while getting 5% more DOM threads and 1% 
> more overall threads.  That is, I've been testing if the path solver 
> can solve everything the DOM threader needs (the hybrid approach I 
> mentioned).
>
> Unfortunately, replacing the forward threader right now is not 
> feasible for a few reasons:
Right.  But I thought the short term goal was to replace/remove the 
forward threading from VRP.   Dropping from DOM is going to be tougher.

>
> a) The const_and_copies/avail_exprs relation framework can do floats, 
> and that's next year's ranger work.
Right.  I'd actually run into this as well when I wanted to drop all the 
range bits out of DOM and rely exclusively on EVRP.   It'd still be a 
step forward to rip out the EVRP engine from DOM and simplify all the 
code that derives one equivalence from another so that it's only working 
on FP values.

>
> b) Even though we can seemingly fold everything DOM/threader does, in 
> order to replace it with a backward threader instance we'd have to 
> merge the cost/profitability code scattered throughout the forward 
> threader, as well as the EDGE_FSM* / EDGE_COPY* business.
Right.  This is a prerequisite.  Though some of the costing will need to 
be conditional on the threader being used.  Refer back to the discussion 
around how the forward threader can commonize thread paths that lead to 
the same destination while the backwards threader can not.

>
> c) DOM changes the IL as it goes.  Though we could conceivably divorce 
> do the threading after DOM is done.
The only reason threading runs in parallel with DOM is so that it can 
use the context sensitive equivalences.  With the infrastructure you're 
building, there's a reasonable chance we can move to a model where we 
run DOM (and in the long term a simpler DOM) and threading as distinct, 
independent passes.

Jeff