Early jump threading

[Jeff Law]

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