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

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> > I'm trying to understand what benefits do we get from this pass.  It
> > doesn't seem to me like increasing the in-degree of a basic block should
> > have any benefits.  Yes, we get to join more basic blocks, but at the
> > same time we increase the number of PHI arguments.
> We decrease the number of blocks and edges.  As far as PHIs are
> concerned, I suspect it's a wash (we'll have fewer PHI nodes, but
> the number of arguments in the existing PHIs is slightly higher).
> 
> > 
> > If we are missing optimization opportunities in the threader.  Then it
> > looks like we should be fixing that.  Adding more passes to cover for
> > shortcomings of existing passes is not usually a win.
> Err, no.  The jump threader isn't likely to be extended to deal with
> this kind of thing.
> 
> The threader can not walk back multiple blocks and assign values
> to the PHI results.  It's simply wrong.  Consider this fragment:
> 
> BB0:
>   <whatever>
>   goto BB3;
> 
> BB1:
>   <whatever>
>   goto BB3;
> 
> BB2
>   <whatever>
>   goto BB4;
> 
> BB3:
>   x1 = PHI (0 (BB0), 1 (BB1))
> 
> BB4:
>   x2 = PHI (x1 (BB3), x0 (BB2))
>   if (x2 == 0)
>     goto BB5;
>   else
>     goto BB6;
> 
> 
> As it stands, I don't see any way for the threader to optimize
> that code without first duplicating BB4, then applying a 
> transformation similar to Kazu's.

huh?  When jump threading sees edge bb0 --> bb3, it notices that
x1 has only a single use in phi node in bb4.  This enables it to perform
the jump threading

BB0:
  whatever;
  goto BB4;

BB1:
  <whatever>
  goto BB3;

BB2:
  <whatever>
  goto BB4;

BB3:
  x1 = PHI (1 (BB1));
  goto BB4;

BB4:
  x2 = PHI (x1 (BB3), x0 (BB2), 0 (BB0));
  whatever;

Similarly edge bb1 --> bb3 can be threaded over to BB4, and bb3 can be
removed as unreachable.  This achieves exactly the same effect as the
proposed optimization pass.

Zdenek