Do not mark obviously unreachable blocks live when processing PHI nodes,

and handle incomplete control dependences correctly.  This fixes:

Regression/Transforms/ADCE/dead-phi-edge.ll
  -> a missed optimization

Regression/Transforms/ADCE/dead-phi-edge.ll
  -> a compiler crash distilled from QT4


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20227 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 61 insertions, 40 deletions

diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp
index ca876de681..cb09a4e6fc 100644
--- a/lib/Transforms/Scalar/ADCE.cpp
+++ b/lib/Transforms/Scalar/ADCE.cpp
@@ -253,7 +253,7 @@ bool ADCE::doADCE() {
   // function which unwinds, exits or has side-effects, we don't want to delete
   // the infinite loop or those blocks leading up to it.
   for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I)
-    if (DT[I] == 0)
+    if (DT[I] == 0 && ReachableBBs.count(I))
       for (pred_iterator PI = pred_begin(I), E = pred_end(I); PI != E; ++PI)
         markInstructionLive((*PI)->getTerminator());
 
@@ -281,17 +281,28 @@ bool ADCE::doADCE() {
     // defined in the predecessor nodes of this block, meaning that the PHI
     // makes the predecessors alive.
     //
-    if (PHINode *PN = dyn_cast<PHINode>(I))
-      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
-        if (AliveBlocks.insert(PN->getIncomingBlock(i)).second)
-          markBlockAlive(PN->getIncomingBlock(i));     // Block is newly ALIVE!
-
-    // Loop over all of the operands of the live instruction, making sure that
-    // they are known to be alive as well.
-    //
-    for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op)
-      if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op)))
-	markInstructionLive(Operand);
+    if (PHINode *PN = dyn_cast<PHINode>(I)) {
+      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+        // If the incoming edge is clearly dead, it won't have control
+        // dependence information.  Do not mark it live.
+        BasicBlock *PredBB = PN->getIncomingBlock(i);
+        if (ReachableBBs.count(PredBB)) {
+          // FIXME: This should mark the control dependent edge as live, not
+          // necessarily the predecessor itself!
+          if (AliveBlocks.insert(PredBB).second)
+            markBlockAlive(PN->getIncomingBlock(i));   // Block is newly ALIVE!
+          if (Instruction *Op = dyn_cast<Instruction>(PN->getIncomingValue(i)))
+            markInstructionLive(Op);
+        }
+      }
+    } else {
+      // Loop over all of the operands of the live instruction, making sure that
+      // they are known to be alive as well.
+      //
+      for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op)
+        if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op)))
+          markInstructionLive(Operand);
+    }
   }
 
   DEBUG(
@@ -359,7 +370,7 @@ bool ADCE::doADCE() {
 
       // Loop over all of the successors, looking for ones that are not alive.
       // We cannot save the number of successors in the terminator instruction
-      // here because we may remove them if we don't have a postdominator...
+      // here because we may remove them if we don't have a postdominator.
       //
       for (unsigned i = 0; i != TI->getNumSuccessors(); ++i)
         if (!AliveBlocks.count(TI->getSuccessor(i))) {
@@ -368,39 +379,49 @@ bool ADCE::doADCE() {
           // dead...
           //
           PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)];
+          PostDominatorTree::Node *NextNode = 0;
+
+          if (LastNode) {
+            NextNode = LastNode->getIDom();
+            while (!AliveBlocks.count(NextNode->getBlock())) {
+              LastNode = NextNode;
+              NextNode = NextNode->getIDom();
+              if (NextNode == 0) {
+                LastNode = 0;
+                break;
+              }
+            }
+          }          
 
           // There is a special case here... if there IS no post-dominator for
-          // the block we have no owhere to point our branch to.  Instead,
-          // convert it to a return.  This can only happen if the code branched
-          // into an infinite loop.  Note that this may not be desirable,
-          // because we _are_ altering the behavior of the code.  This is a well
-          // known drawback of ADCE, so in the future if we choose to revisit
-          // the decision, this is where it should be.
+          // the block we have nowhere to point our branch to.  Instead, convert
+          // it to a return.  This can only happen if the code branched into an
+          // infinite loop.  Note that this may not be desirable, because we
+          // _are_ altering the behavior of the code.  This is a well known
+          // drawback of ADCE, so in the future if we choose to revisit the
+          // decision, this is where it should be.
           //
           if (LastNode == 0) {        // No postdominator!
-            // Call RemoveSuccessor to transmogrify the terminator instruction
-            // to not contain the outgoing branch, or to create a new terminator
-            // if the form fundamentally changes (i.e., unconditional branch to
-            // return).  Note that this will change a branch into an infinite
-            // loop into a return instruction!
-            //
-            RemoveSuccessor(TI, i);
-
-            // RemoveSuccessor may replace TI... make sure we have a fresh
-            // pointer... and e variable.
-            //
-            TI = BB->getTerminator();
-
-            // Rescan this successor...
-            --i;
-          } else {
-            PostDominatorTree::Node *NextNode = LastNode->getIDom();
+            if (!isa<InvokeInst>(TI)) {
+              // Call RemoveSuccessor to transmogrify the terminator instruction
+              // to not contain the outgoing branch, or to create a new
+              // terminator if the form fundamentally changes (i.e.,
+              // unconditional branch to return).  Note that this will change a
+              // branch into an infinite loop into a return instruction!
+              //
+              RemoveSuccessor(TI, i);
+              
+              // RemoveSuccessor may replace TI... make sure we have a fresh
+              // pointer.
+              //
+              TI = BB->getTerminator();
+              
+              // Rescan this successor...
+              --i;
+            } else {
 
-            while (!AliveBlocks.count(NextNode->getBlock())) {
-              LastNode = NextNode;
-              NextNode = NextNode->getIDom();
             }
-            
+          } else {
             // Get the basic blocks that we need...
             BasicBlock *LastDead = LastNode->getBlock();
             BasicBlock *NextAlive = NextNode->getBlock();