pretty-ipa merge 17: CD-DCE wrt cyclic CFGs fix

[Steven Bosscher]

On Mon, Apr 27, 2009 at 1:53 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
> Hi,
> enabling CD-DCE on looping regions shows bug in current way it is removing
> control flow statements.
>
> !       /* There are three particularly problematical cases.
> !
> !        1. Blocks that do not have an immediate post dominator.  This
> !           can happen with infinite loops.
> !
> !        2. Blocks that are only post dominated by the exit block.  These
> !           can also happen for infinite loops as we create fake edges
> !           in the dominator tree.
> !
> !        3. If the post dominator has PHI nodes we may be able to compute
> !           the right PHI args for them.
> !
> !        In each of these cases we must remove the control statement
> !        as it may reference SSA_NAMEs which are going to be removed and
> !        we remove all but one outgoing edge from the block.  */
>
> This leads on several testcases in testuite and mpfr library to be miscompiled in
> a way turning finite dead loop to infinite.  The problem here is that skipping
> the redirection and following to code removing all but first succestor edge
> of the BB might lead to picking "wrong" edge and removing everything except
> for loopback.
>
> The function is slightly wrong in two ways.  First the formulation of algoritm
> says that edges should be forwarded to first "useful" postdomominator (i.e. BB
> containing live statements or one marked in control dependency because of PHI).
> Second it should be able to update the PHIs: since control dependent BB are
> marked as neccesary, we know that the edge being forwarded is control dependent
> BB.  As such it is at post-dominance frontier of one of blocks corresponding to
> PHI arguments.  Looking those up is easy and PHI argument can be copied by one
> corresponding to the edge found. (I hope that this is right with the actual
> implementation, there are multiple CD-DCE formulations and there is no specific
> paper quoted).
>
> This works for acyclic regions, since every random path through the acyclic
> region eventually leads to postdominance, so cfgcleanup and PHI merging does
> the job later.
>
> Updating however run into problem with VOP PHIs.  Since those are not marked,
> the invariants here are broken. We can not be sure about control dependence of
> BB forwarded and we can not be sure that useless basic blocks are not
> containing live PHIs and they do in practice.
>
> So I made virtual PHIs to be simply marked for renaming when they are reached
> via new edges and in addition to that, unreachable basic blocks are removed,
> virtual PHIs there are inspected and in case they define result that  might be
> used in live BBs, they are also sent for renaming.
>
> This patch bootstraps/regtests x86_64-linux with the infinite loop hack removed.
> Seems sane?

Ugh, how ugly.

I'm at the point now where I believe DCE and CD-DCE are getting so
complicated, that I would remove the CD-DCE bits completely again.
When I added then, the benefit was minimal but real.  By now, I wonder
if there still is any benefit at all.  I would measure that first and
if it doesn't do anything, remove it.

Note that the comment you quote comes from Jeff Law, you may want to
ask him what it means.  I don't see where we add the fake edges
mentioned in point 2, for example.

Ciao!
Steven