Re: Question re: SSA Aggressive Dead Code Elimination

[law at redhat dot com]

  In message <Pine.LNX.4.33.0106271250300.30643-100000@www.cgsoftware.com>you w
rite:
  > > 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 it should be marked as important, and not turned unconditional.  And
  > every other implementation of
  > Morgan's DCE i see does this by following the phi node definitions.
We follow the definitions too.  But if you go back and look at the RTL you'll
find that's not sufficient.  The definition of both alternatives in the PHI
node is in block #0.

  > If you are saying that morgan's book doesn't say to do this, it's wrong.
  > However, those that are using Morgan's DCE do mark the phi node control
  > dependences properly, so either they are using a different one of
  > morgan's dce algorithms (I don't have his book), or something.
The algorithm presented in Morgan's book doesn't do anything special with
PHI nodes.

When a PHI node becomes important, we follow the control dependencies for
the block with the PHI node itself and mark those edges as important (as
it does when any insn becomes important).  Similarly, for each alternative
in a PHI node, it marks the instruction which defines the source of the
PHI alternative as important.

In the example I posted, block #2 (the block with the PHI node) is not
control dependent on edge/block and the registers referenced by the PHI
node are both defined in block #0.

Since block #1 has no instructions marked as important and no important
block is control dependent on block #1 it gets (incorrectly) removed.

What I think needs to happen is when we have a PHI node, we mark the
edge/block associated with each PHI alternative as important.  Once we do
that all the right things should happen.

  >         // Follow control dependences: mark as necessary the CTIs of each
  >         // block on which operation depends.  Since a phi-node operation
  >         // represents copies at the end of each of the predecessors of the
  >         // block to which it's attached, follow dependences from those
  >         // predecessors in the phi-node case.
  > 
  >         if (operation.is_phi_node()) {
  >             CfgNode *block =  ssa_form->phi_node_block(operation.get_phi_no
  > de());
  >             for (CfgNodeHandle pit = preds_start(block);
  >                  pit != preds_end(block); ++pit)
  >                 mark_controlling_ctis(*pit);
  >         } else {
  >             CfgNode *block =  get_parent_node(*operation.get_instr_handle()
  > );
  >             mark_controlling_ctis(block);
  >         }
OK.  This is subtly different than the algorithm presented in Morgan's
book and other literature.  Note how it marks controlling CTIs for each
predecessor of the block with the PHI node.

That's the moral equivalent of what I've suggested (iterating over the
PHI alternatives marking their associated edge/block as important).

Thanks, it's good to see a verification that a. I'm not crazy and b. the
proposed solution mirrors what others have done.

jeff