Re: [PR tree-optimization/20640] add phi args to dests ofdce-redirected edges

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

On Thu, 2005-03-31 at 05:26 -0300, Alexandre Oliva wrote:
> On Mar 31, 2005, Alexandre Oliva <aoliva@redhat.com> wrote:
> 
> > I have a gut feeling that we'll always get a PHI arg from one of the
> > previous successors of the src of the redirected edge, but I can't
> > quite prove it.  What do you think?
> 
> A few seconds after posting the patch, ssa-dce-3.c failed, showing my
> gut feeling was wrong.  Oh well...
Worse yet, you can't depend on testing SSA_NAME_VAR to find your
PHI node.  It's rare, but possible to have two PHIs in the same block
with the same underlying SSA_NAME_VAR.  It's also possible to get a
mis-match between the underlying var for PHI_RESULT and PHI_ARG_...

At which point you're probably coming to realize that updating PHI
nodes is a non-trivial problem in the general case.

Fundamentally, this code is trying to optimize the case where selection
of either arm of the conditional has no visible impact on the behavior
of the program.  So while the arms may contain code, we know that we
could execute either arm or even bypass both completely and get correct
code.  From this you can derive that any assignments in the arms must
be dead and any PHIs those assignments feed must also be dead, and so
on.

So we could proceed by first eliminating all the assignments and PHI
nodes which are dead, then we proceed to eliminate the dead control 
statements. As you noted, this makes it less likely that there will be
any PHIs in the post-dominator node.  It also makes it easier to update
any PHIs which remain in the post-dominator node.

For each PHI in post_dominator_bb
  For each PHI argument
    if (dominated_by_p (arg->edge->src, control_statement_bb))
      arg->value is the value we want to associate with the new edge
      from control_statement_bb to post_dominator_bb



At least I think that or something similar should do the trick.  I
haven't finished my first coke for the day, but it feels right.

Alternately, we could go with your second approach which is to 
remove all the dead phis first, then avoid redirecting to a
post-dominator with phis (instead redirecting to the fall-thru
edge).



> On Mar 30, 2005, Jeffrey A Law <law@redhat.com> wrote:
> 
> >> This code is triggered rarely, I would expect it to be even rarer still
> >> for POST_DOM_BB to have PHI nodes.  You could probably just ignore dead
> >> control statements where the post dominator has PHI nodes and I doubt
> >> it would ever be noticed.
> 
> It is noticed if we take the same path as the no-post_dom_bb,
> infinite-loop case, because then the instruction that remains may
> still reference variables that were deleted.
We can change the COND_EXPR_COND to be anything we want --
remember, the whole point is that we've determined that the branch
itself is dead -- we can take either arm and nothing can tell the
difference.  So we could just change the condition to if (0) and
we would be safe.  Or we could just delete the condition and
fall-thru as you've suggested.

The only advantage of redirecting to the post-dominator block is that
we have less cleanup work to do later.   It's not clear to me if there
is an advantage (compile-time wise) to redirecting to the post-dominator
block or just redirecting to the fall-thru and letting cleanup_tree_cfg
remove the forwarders.


> This patch, however, arranges for us to turn the edge into a
> fall-through edge to its original destination should the immediate
> post dominator be found to have PHI nodes.
Which would be fine.


> I've also tweaked the code so as to remove all dead phi nodes before
> removing all other statements, thereby improving the odds of
> redirecting a dead control stmt to the post dominator.
Right.  That was a good piece of insight.  I think this is really the
key step for either solution (update the post-dominator phis, or 
just redirect to the fall-thru edge).



> Interestingly, the resulting code was no different for some cases I
> inspected (the testcase included in the patch and ssa-dce-3.c).
> That's because the edge dest bb ends up becoming a simple forwarding
> block that is later removed.
Precisely.  Again, redirecting to the post-dominator is just avoiding
some of the later cleanup work.

> 
> As for infinite loops, I'm wondering if we should somehow try to
> remove the condition from the loop.  If the conditional branch is
> found to be dead, it's quite possible that the set of that variable is
> dead as well, and so we'd be keeping a reference to a deleted
> variable.  I couldn't actually exercise such an error, and I'm not
> convinced it's possible, but I thought I'd bring this up.  Thoughts?
I'm not sure either.  I haven't thought much about the infinite loop
cases much.  It would seem to me that we could/should remove the
conditional as well.  Presumably this code is meant to handle the case
where the conditional will always end up looping, regardless of 
whether or not the conditional is true or false.

Jeff