Re: Minor SSA cleanups

[law at redhat dot com]

  In message <Pine.LNX.4.33.0106222340120.19001-100000@www.cgsoftware.com>you w
rite:
  > Not necessarily.
  > SCC-based value numbering can make optimistic assumptions  about values
  > that propagate along back edges, and prove/disprove them later.
Yes, as do a number of SSA optimizers, but none of them to the best of
my knowledge require one to change the incoming edge for a definition.  At
the most these require you remove an incoming edge.

  > 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.
I think your implementation is buggy.


  > >   > 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 replac
  > ement
  > >   > 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.
I think you need to do more debugging.

While you may find cases where it *appears* you need to change the edge
because of a copy propagation or similar action, in reality the edge does
not need to be updated as both edges are from within the same dominance
frontier.

  > >   > that register, and replace the block number/pointer.
  > > OK.  Are you moving it into a new dominance frontier?  If so, then it see
  > ms
  > > to me you would need to rebuild the SSA graph.  If you're keeping it with
  > in
  > > 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 that still doesn't answer the question I asked.  You need to go back
and verify that the cases you're seeing where you think you need to change
the edge pointer are in fact correct applications of the optimization
algorithm, then you need to think about whether or not you actually changed
dominance frontiers when you change the incoming definition.  If you haven't
changed the DF, then you wouldn't need to update the embedded pointer.

  > But making sure we update all these edge pointers, is just one more thing
  > to worry about when doing that.
But you're missing my point.  I don't think you need or should be updating
those edges.  I think your code is buggy in some way or that you're mis-
understanding certain aspects of the optimization.

It's very easy to write an 80% complete optimization pass and think that
all that's left is minor cleanups, but in reality it's got significant
issues that need to be addressed that affect its correctness.  Your SCP
pass was an excellent example.  Aside from not being complete, it was buggy
in a number of ways that caused it to make incorrect transformations.


  > If it's only used to convert out of SSA, then why isn't it local to the
  > "convert out of ssa" pass?
Because it's trivial to record the edge when we're translating from normal
into SSA form and if we're going to record it for later use, then it needs
to be recorded in the RTL.  

One of the lamest aspects of GCC is that there is significant hunks of 
information that live across passes, but which are not part of the RTL
format.  That's an insanely dumb design and one that is prone to programmer
error.


  > 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.
You can get away with not updating them.  However, you'll find that you'll
get better optimizations if you do update them as you prove certain properties
about the CFG/SSA graphs.  Furthermore, when I say "update", I'm really
talking about just removal.

That's part of the whole point behind moving to embedded edge/block pointers
instead of embedded block #s -- to help lessen the need to update them as
we make incremental changes to the CFG.

Consider when we prove a block is unreachable.  It's a given that we're
going to remove the PHI alternatives for the outgoing edges from that
block since they can never be executed and doing so makes other optimizations
possible.  We have a trivial routine to do this for us (and it needs 
*something* to key its actions on, either an edge or incoming block #).
It's also a given that we'll remove the unexecutable edge from the CFG.

However, we also want to remove the block from the CFG as that provides
further optimization opportunities.  Removal of the block from the CFG
will cause block #s to change, which in turn breaks the conversion from
SSA back to normal form because of the embedded block #s.

We could build a mapping from old #s to new #s and update all the PHI
nodes.  However, that's lame and a waste of time.

Instead if we record the block pointer or edge pointer, then we don't have
to build any kind of mapping to update the PHI nodes.  The only updates are
removal of alternatives, which we were going to do anyway.

jeff