Re: Good news about increased jump threading from my PHI mergepatch

[Kazu Hirata <kazu at cs dot umass dot edu>]

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.

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.  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.

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.

> 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:

  a_1 = PHI <0(here), 1(there)>
<L123>:;

and it tries to convert this to

<L123>:;
  a_1 = COND;

The newer version of PHI-OPT on tree cleanup branch looks at COND_EXPR
instead of a PHI node and sees if two arms of COND_EXPR feed 0 and 1
into some PHI node, so we end up with

<L100>:;
  :
  :
  c_7 = COND;
  goto <L123>;

  a_1 = PHI <c_7(here), ... arbitrarily long ...>
<L123>:;

Of course, in the special case of two incoming edges, the PHI node is
equivalent to a copy statement because we would have

  a_1 = PHI <c_7(here)>
<L123>:;

Kazu Hirata