Re: Question re: SSA Aggressive Dead Code Elimination

[law at redhat dot com]

  In message <878ziebfl7.fsf@cgsoftware.com>you write:
  > law@redhat.com writes:
  > 
  > > I'm not sure which is the better solution.  
  > 
  > Oh, and BTW, the reason you are running into this problem is that
  > you've changed the dominance frontier (by removing 0 as a dominator of
  > 1) , and thus, changed the IDF, and thus, eliminated the need for a
  >    phi node there. 
  > I think, anyway.
No.  Per Morgan's book, we do not change the dominance trees that we've
already computed as doing so would lead to an iterative algorithm as we'd
need to re-do the conversion to SSA when the DF information changed.

  > So it's not really valid SSA until you do something about the PHI node.
  > Then again, going by muchnik, we don't have SSA anyway.
?!?    Details please.

  > By adding those edge pointers, what you've got isn't SSA, it's Gated
  > Single Assignment. To quote muchnick, "An extension of SSA form called
  > gated single-assignment form includes in each phi function a selector
  > that indicates which position to select according to the path taken to
  > reach the join point". Normal SSA has no such thing.  This is for certain. 
And this is relevant how?  Even without the pointers we'll still end up with
the wrong code if the same transformations were made.


  > To quote another paper abstract to make sure muchnik's not just wrong,
  > "
  >                  In this paper, we present an almost-linear time
  >                  algorithm for constructing Gated Single Assignment
  >                  (GSA), which is SSA augmented with gating functions at
  >                  {$\phi$}-nodes. The gating functions specify the
  >                  control dependences for each reaching definition at a
  >                  {$\phi$}-node. 
  > "
  > Which is what we've got, no?
  > 
  > If so, then even if you've not changed the DF, you've certainly
  > changed the gating path.  And changing the gating path means updating
  > the edge gating functions approriately, which you've not done.
  > 
  > Just a thought.
Again, I think you're missing the point.  Go back to the RTL I posted and
consider that behavior of the jump insn is dependent on the inputs to the
registers I mentioned had live values at entry.  Then look at the series
of transformations made to the RTL and think about  their validity in terms
of whether or not the program gives the same results for all sets of inputs.

I think you'll find that clearly it doesn't and it has no relation to updating
the gating paths or anything like that.  I believe there is an algorithmic
bug in the optimization descriptions from Morgan's book, either in the
dominator optimization phase or the aggressive dead code elimination phase.

jeff