[tcb] Merge PHI nodes -- 7.4% reduction of PHI nodes (Take 2)

[Kazu Hirata]

Hi Jeff,

> BB3:
>   x1 = PHI (0 (BB0), 1 (BB1))
> 
> BB4:
>   x2 = PHI (x1 (BB3), x0 (BB2))
>   if (x2 == 0)
>     goto BB5;
>   else
>     goto BB6;

Thanks for detailed explanation.  By the way, I'd like to point out
that I often see a variant of your example like so:

BB3:
  x1 = PHI (0 (BB0), 1 (BB1))
  x2 = (_Bool) x1;              <- Notice this cast!

BB4:
  x2 = PHI (x1 (BB3), x0 (BB2))
  if (x2)
    goto BB5;
  else
    goto BB6;

Notice that my PHI merge pass cannot get at this king as the two PHI
nodes are separated by a cast to _Bool, meaning that we miss a jump
threading opportunities.

I've written a small pass to kill the above cast like so

BB3:
  x2 = PHI (0 (BB0), 1 (BB1))

BB4:
  x2 = PHI (x2 (BB3), x0 (BB2))
  if (x2)
    goto BB5;
  else
    goto BB6;

provided that x1 is a single use variable, and that all the arguments
in "x1 = PHI <...>" are constants.  By running this pass immediately
before my PHI merge pass, I can remove 7.9% of PHI nodes in GCC's
source code, which is 0.5% more than without this pass.

> Probably the closest thing I've come to a guideline is the threader
> will prefer to have fewer PHIs with larger vectors.  if-conversion
> and CSE will tend to want more PHIs with smaller vectors.

By if-convesion, do you mean phiopt?  If that's the case, I am
thinking about rewriting phiopt by looking at COND_EXPR, not the PHI
node that two edges comes to.  That is, if we have

BB1
  if (COND) goto BB3; else goto BB2;

BB2:;

BB3:;
  x1 = PHI <1(BB1), 0(BB2), 0(BBx)>    <- Notice three arguments!

then we can convert this to:

BB1
  x2 = COND;
  if (1) goto BB3; else goto BB2;

BB2:;

BB3:;
  x1 = PHI <x2(BB1), 0(BB2), 0(BBx)>    <- Notice three arguments!

Now that BB2 is unreachable, we get:

BB1
  x2 = COND;

BB3:;
  x1 = PHI <x2(BB1), 0(BBx)>    <- Notice three arguments!

This problem has been filed as PR 14442.

> > And if the pass has negative compile time effects, then I'm definitely
> > not interested ;)
> I'd like to postpone trying to tackle this problem.  I don't think
> it's something we want to be spending time on during stage3.

OK.  I posted my patch simply because Diego started
tree-cleanup-branch. ;-)

Kazu Hirata