On 9/10/21 6:21 PM, Jeff Law wrote:
On 9/10/2021 10:05 AM, Aldy Hernandez wrote:
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.
No we shouldn't change it to any of the other types. EDGE_FSM_THREAD
means a thread found by the backwards threader and it's the key used to
determine which of the two CFG updating mechanisms should be used, the
generic copier in the case of EDGE_FSM_THREAD.
Changing the name, yes, absolutely. I probably should have done that
when the original FSM threader was tweaked to handle generic threading.
I'll put that on my list.
As you've probably heard me mention before, all the EDGE_FSM_THREAD
stuff in the registry really could be pulled out. The registry's
purpose is to deal with the two stage nature of jump threading in DOM
(find threads, then optimize them later). I don't think any of the
backwards threading bits need that two stage handling.
Yeah yeah. But you said that a year ago, and all I heard was *mumble
mumble/complicated things*. That was before I had much exposure to the
code. Now I feel a lot more comfortable ;-).
I'll also put this on my list, but it may not get done this release,
cause I'm running against the clock with the VRP/threader replacement,
which is what's keeping us back from replacing VRP with an evrp instance
right now :).
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.
And that's probably a reasonable intermediate step on the way towards
removing the VRP threading.
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.
Yea. Sorry about that tangle of insanity
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).
So once you plug those bits in, we don't have to carry around the
avail/copies tables for the threader anymore, right? That's a nice
cleanup in and of itself.
Correct. For the VRP/hybrid approach I'm working on, there are no
copies/avails. The solver can do everything they did. After all, it's
an easier target, since VRP threading only happens on ints and without
the IL changing constantly.
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.
I think we can go hybrid, then look at the next step, which could well
be bringing some consistency into the costing models.
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.
Essentially a realization of Bodik's work in GCC. The nugget in there
is it's a path sensitive optimizer. That's kindof what I've envisioned
DOM turning into.
1. We separate out jump threading from DOM.
2. We replace the bulk of DOM with FRE
3. The remnants of DOM turn into a path sensitive optimizer (and for
god's sake we don't want to call it DOM anymore :-)
Well, my tree has improvements to the solver for full path sensitive
ranges (using ranger to resolve definitions outside of the path). And
it also does path sensitive relations, though Andrew is overhauling them
next week. So yeah, given a path, we could tell you all sorts of
interesting things about it :).
Aldy