Re: Minor SSA cleanups

[Daniel Berlin <dan at www dot cgsoftware dot com>]

On Fri, 22 Jun 2001 law@redhat.com wrote:

>   In message <Pine.LNX.4.33.0106220536570.5894-100000@www.cgsoftware.com>you wr
> ite:
>   > I'll happily agree to disagree about whether df.[ch] is
>   > overkill/approriate. We just seem to have a difference of opinion.
>   >
>   > However, the above statement would be incorrect.
>   > Think about what happens now when I want to replace part of a phi node,
>   > like SSA GVN can, and often does, do.
> Yes, I've thought about that -- and in that case it seems to me that you
> absolutely shouldn't muck around with the block #.
>
> The fact that you're replacing one register with a different register or
> a constant doesn't change the fact that the new register/constant needs
> to be associated with the same edge as the original register.

Not necessarily.
SCC-based value numbering can make optimistic assumptions  about values
that propagate along back edges, and prove/disprove them later.
So with multiple incoming edges, we may end up switching the incoming
edge the definition comes from.  It's a corner case, since we usually end
up proving the phi node is equal to a given value, and just replace the
whole thing. But i've run into cases where we do switch the edge.
If this isn't supposed to happen, even in this case, my implemenation is
buggy.

>
>   > However, updating them is annoying.
> Not really.  I have CCP doing that.
>
>   > By keeping the block number there, you *force* SSA-GVN to keep track of
>   > where each register is def'd.  Without it, I could do a simple replacement
>   > of register with register.
> Why can't you do the simple replacement.  Details please.
Because the incoming edge isn't the same necessarily, unless, again, i
need to do some more debugging.


See simpson's 1996 paper on value numbering for a description of the
algorithm.
The code actually implements *all* the algorithms in the paper, the SCC
based one is the default.
(It's easy to reuse the other algorithms in other optimizations).

In order to let something else deal with the problem of actually removing
the code, we just prepare for PRE by renaming everything to it's value
number, if it's got one.
(Yes, this violates SSA form. I clean it up through deleting the dead
insns, and incrementally rebuilding the ssa form.)

 >
>   > If you move a register def, you need to hunt down all the phi nodes using
>   > that register, and replace the block number/pointer.
> OK.  Are you moving it into a new dominance frontier?  If so, then it seems
> to me you would need to rebuild the SSA graph.  If you're keeping it within
> the same frontier, then it seems to me you don't need to update the
> embedded edge pointer.

I can incrementally rebuild the SSA graph, because dj-graphs allow me to
incrementally recompute the dominance frontier relationship, which is,
of course, the key to building the SSA graph.

But making sure we update all these edge pointers, is just one more thing
to worry about when doing that.

I'm not trying to say that updating these edge pointers isn't trivial,
but it's certainly just another, IMHO, pointless, thing to worry about
when building optimizations, and really, anything that will change phi
nodes.

If it's only used to convert out of SSA, then why isn't it local to the
"convert out of ssa" pass?

Because the number of SSA passes is currently 1, we can remove the block
pointers, which, IMHO, don't really belong there, before it becomes
another not easily changeable piece of gcc.

If you really think they are going to be useful to other passes, and we
are committed to updating them, then let's document it somewhere, and be
done with it, and i'll stop biching, and live with it.

Because right now, there is nothing that says they *must* be updated,
nothing that says where they came from, what their original intention is,
and what is supposed to be the consumer of them.

We only have a little thing in rtl.def that says they are there.
> jeff
>