Good news about increased jump threading from my PHI merge patch

[Jeffrey A Law]

On Mon, 2004-12-13 at 12:57 -0500, Kazu Hirata wrote:
> Hi Jeff,
> 
> > Thanks.  It's still on my list of things to evaluate for 4.0, mostly
> > because of its potential to help compile-times on some of our 
> > problematical cases without introducing lots of regressions elsewhere.
> 
> If we are just merging PHI nodes and not constant-propagating PHI
> nodes (like killing casts), I get about 1% speed up on some test
> cases.  (For more accurate number, I have to retest.)
> 
> What I am doing is really the same as Zdenek's thread_jumps rewrite,
> which you recently approved.  The only difference is that I am trying
> to remove forwarder blocks with PHI nodes.  Zdenek's version tries to
> remove those without.
Right.  It seems like a pretty natural extension to Zdenek's code.


> But do note, though, that my pass helps if it is run once or twice,
> but if it's part of cleanup_tree_cfg, the compiler measurably slows
> down because cleanup_tree_cfg is run so many times.  
Sigh.   That is something on the long term todo list, but I haven't
really figured out where/how to start cutting down those calls.


> I think my pass
> basically requires DCE.  We clean up CFG before entering SSA, so we
> shouldn't have any PHI merge opportunity unless some dead code between
> two PHI nodes are removed.
Which almost makes me wonder if removing forwarder blocks is better
off as its own pass.

We would schedule it to run after the DCE/DSE.  We would also call
it from cleanup_tree_cfg if and only if we were able to determine
the result of a COND_EXPR_COND or SWITCH_COND.

  
> Here is a quick advertisement. :-) Let me mention that I can quickly
> determine if I can merge a forwarder block A (and its PHI nodes) into
> basic block B most of the time.  The only condition I need is:
> 
>   if (!dominated_by_p (CDI_DOMINATORS, B, A))
> 
> because if A does not dominate B, then the only valid place where any
> values produced in A can be used is PHI arguments on edge A->B.
> Otherwise, we would have a use that is not dominated by its def.  In
> other words, we don't need to compute immediate uses.
> 
> The reason why I said "most of the time" above is that sometimes A
> dominates B even if B has PHI nodes (and thus multiple incoming
> edges).  This case applies to B being a loop header.  I don't know how
> aggressive we want to be in this case because we are effectively
> undoing create_preheader.
Presumably we've already eliminate degenerate PHIs by this point.  I
see.

> 
> > You mentioned that we can't handle large PHI nodes.  Can you comment
> > more on that -- that would be my largest individual concern right now.
> 
> The only thing that's technically blocking my PHI merge is PHI-OPT.
> IIRC, PHI-OPT looks for a basic block with a single PHI node with
> exactly two arguments like so:
Oh.  That code.  I thought you meant there was some time-complexity
problem you needed to be solved with large PHI arguments.

It would seem to me that the phi-opt code would just make your changes
more effective, but the phi-opt code shouldn't be a prerequisite for
your code to merge phis.

jeff