On 08/12/2016 12:02 AM, Richard Biener wrote:
Hmm, isn't walking backwards from uses doing a lot of redundant stmt
walking compared to walking stmts once in forward direction? To me
it sounds like a 'local' patterns matching like optimization rather
than a global one with proper data flow or a lattice?
You end up walking the use-def chain, so you look only at the chain of
feeding statements.
Forward threading is actually worse because it tries to walk *past* the
current point in the dominator walk. For example at a dominance
frontier we have multiple paths merging -- we will walk all statements
in the merge block for every incoming path as well as all statements on
the outgoing paths of the merge block. We have to update the various
tables, then unwind them as we work through all those paths.
I have not done a full analysis, but I strongly suspect the backwards
threader will ultimately end up doing less work, both in the common and
pathological cases.
jeff
