On 9/10/21 5:43 PM, Jeff Law wrote:
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.
back_threader_registry::register_path() uses EDGE_FSM_THREAD as the
thread type to register threads. I was wondering if it should have been
some combination of EDGE_START_JUMP_THREAD / EDGE_*_COPY_SRC_BLOCK, etc.
I (purposely) know nothing about the underlying threading types ;-).
But if the backwards threader has been improved, then perhaps we should
just remove the confusing FSM references.
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.
My current thinking is that replacing the forward VRP threader with a
hybrid one is a gentler approach to the longer term goal of replacing
the forward threader altogether. However, all the work I've been doing
could go either way-- we could try the forward/VRP replacement or a
hybrid approach. It will all use the path solver underneath.
My main problem with replacing the forward/VRP with a backward client is
that the cost models are so different that it was difficult to compare
how we fared. I constantly ran into threads the solver could handle
just fine, but profitable_path_p was holding it back.
FWIW, we get virtually everything the forward threader gets, minus a
very few things. At least when I plug in the solver to the
DOM/forwarder threader, it can solve everything it can (minus noise and
floats).
If you prefer a backward threader instance to replace the VRP/forward
threader, I'm game. It's just harder to compare. Either way (backward
threader or a hybrid forward+solver) uses the same underlying solver
which is solid.
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.
Sure.
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.
Yup, yup.
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.
Andrew mumbled something about replacing all of DOM eventually :-).
Well, except that value-numbering business I bet.
Aldy
