Re: [patch] tree-ssa-phiopt.c: Update a comment about the pass

[Jeffrey A Law <law at redhat dot com>]

On Wed, 2005-04-20 at 22:07 -0400, Diego Novillo wrote:
> On Wed, Apr 20, 2005 at 12:33:46PM -0600, Jeffrey A Law wrote:
> 
> > And it appears that we do not have cprop & DCE scheduled immediately
> > after phi-opt, which means this stuff is lying around a long longer
> > than is necessary (and a lot longer than it used to be since we used
> > to have redundant phi removal scheduled soon after phi-opt).
> > 
> Well, yes.  Is this causing significant hardship or slow downs?
> No scheduling will be ideal for all inputs.
Unknown.  The primary purpose of PHI-OPT is to perform some
simple if-converesions to generate straight-line code.  The
removal of the useless basic block, propagation of the RHS
of the degenerate PHI and removal of the degenerate PHI are
secondary effects.

My suspicion is that we're not losing any significant optimization
opportunities since all this crud gets cleaned up later.

> 
> > I'll note this would be another excellent case where having an API
> > into the cprop code which allowed a pass which uncovers const/copy
> > propagation opportunity to propagate the values to their uses would
> > be helpful and probably significantly lower overhead than having
> > to schedule cprop & dce passes.
> > 
> Is it really *that* important to remove these redundancies
> immediately instead of scheduling cleanups every few passes in
> the pipeline? (numbers, please).
Every transformation made by PHI-OPT is going to result in this
useless crud lying around.  That was part of the reason why we
ran Zdenek's useless phi removal code right after phi-opt.  We
knew it would have stuff to clean up :-) 

If we're losing anything, it would be on the compile-time side
and on just having clean code for each pass to deal with.


> 
> In terms of the API, how's this?  The caller discovers that NAME
> has value VAL and calls:
> 
> void replace_uses_of_with (tree name, tree val);
> 
> 	1- Replace all immediate uses of NAME with VAL.
> 
> 	2- Remove the defining statement for NAME.
> 
> 	3- Fold as necessary and schedule a CFG cleanup.
> 
> That would be trivial to implement.
That's exactly what we need.  Note I would expect this API to be
used by other code as well.  For example, the outline I've given
for eliminating the iteration step in DOM would use this API.

By far the most important part is #1.  Given a name, value pair,
propagate the value to all uses of the name.

#2 is pretty natural as well since by propagating to all uses, the
definition site must be dead.  My concern would be that in the
general case that to delete the defining statement you would have
to get a BSI and I think that still requires a search through the
block.

In this specific instance the defining statement is always going to
be a PHI.  However, in the case of optimizing after jump threading
the defining statement could well be a real statement -- and in fact
it's pretty important that we _not_ do a search through the block
to get the BSI. 

There are cases where the threader will eliminate a loop when the
backedge is always threadable.  To handle this case well it is
important that we're able to cprop and delete the dead assignemnts
quickly -- failure to do that will result in compile-time explosions
(currently we throttle threading to avoid compile-time explosions for
these kind of cases).

So I would probably suggest that the routine take an optional BSI
for the defining statement.  If the BSI is null, then the routine has
to search.  If the BSI is non-null, then it's used for removing the
defining statement.

I would probably avoid #3 or at least make #3 conditional on a
flag.  For the optimization after jump threading case we're going
to want to do #3, but we need to know if step #3 resulted in
any new const/copy propagation opportunities -- and thus to use
this API for avoiding the threading/DOM iteration the API would
have to arrange to inform the caller what was folded in step #3.

Jeff