[IR] Simplify BasicBlock::removePredecessor. NFCI.

[stephenneuendorffer]

This is less clear to me, since it's not clear to me what the original code is trying to do with all the special cases. LGTM, but I'm not an expert in this code.

[foad]

Rebase.

[lattner]

Very nice! Thank you for dusting off this old code

[foad]

Reverted in b42b30c335bccccca95470aa47dade2e25cb8994 due to buildbots failing tests:

test/Transforms/SimplifyCFG/bug-25299.ll
test/Transforms/SimplifyCFG/invoke_unwind.ll

llvm/include/llvm/IR/BasicBlock.h

public:
   ///
   /// This allows one to 'delete' a whole class at a time, even though there may
   /// be circular references... first all references are dropped, and all use
   /// counts go to zero.  Then everything is delete'd for real.  Note that no
   /// operations are valid on an object that has "dropped all references",
   /// except operator delete.
   void dropAllReferences();
 
-  /// Notify the BasicBlock that the predecessor \p Pred is no longer able to
-  /// reach it.
+  /// Update PHI nodes in this BasicBlock before removal of predecessor \p Pred.
+  /// Note that this function does not actually remove the predecessor.
   ///
-  /// This is actually not used to update the Predecessor list, but is actually
-  /// used to update the PHI nodes that reside in the block.  Note that this
-  /// should be called while the predecessor still refers to this block.
+  /// If \p KeepOneInputPHIs is true then don't remove PHIs that are left with
+  /// zero or one incoming values, and don't simplify PHIs with all incoming
+  /// values the same.
   void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs = false);
 
   bool canSplitPredecessors() const;
 
   /// Split the basic block into two basic blocks at the specified instruction.
   ///
   /// Note that all instructions BEFORE the specified iterator stay as part of
   /// the original basic block, an unconditional branch is added to the original

llvm/lib/IR/BasicBlock.cpp

const BasicBlock *BasicBlock::getUniqueSuccessor() const {
   return SuccBB;
 }
 
 iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
   PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
   return make_range<phi_iterator>(P, nullptr);
 }
 
-/// This method is used to notify a BasicBlock that the
-/// specified Predecessor of the block is no longer able to reach it.  This is
-/// actually not used to update the Predecessor list, but is actually used to
-/// update the PHI nodes that reside in the block.  Note that this should be
-/// called while the predecessor still refers to this block.
+/// Update PHI nodes in this BasicBlock before removal of predecessor \p Pred.
+/// Note that this function does not actually remove the predecessor.
 ///
+/// If \p KeepOneInputPHIs is true then don't remove PHIs that are left with
+/// zero or one incoming values, and don't simplify PHIs with all incoming
+/// values the same.
 void BasicBlock::removePredecessor(BasicBlock *Pred,
                                    bool KeepOneInputPHIs) {
-  assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
+  // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
+  assert((hasNUsesOrMore(16) ||
           find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
-         "removePredecessor: BB is not a predecessor!");
+         "Pred is not a predecessor!");
 
-  if (InstList.empty()) return;
-  PHINode *APN = dyn_cast<PHINode>(&front());
-  if (!APN) return;   // Quick exit.
-
-  // If there are exactly two predecessors, then we want to nuke the PHI nodes
-  // altogether.
-  unsigned max_idx = APN->getNumIncomingValues();
-  assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
-
-  // <= Two predecessors BEFORE I remove one?
-  if (max_idx <= 2 && !KeepOneInputPHIs) {
-    // Yup, loop through and nuke the PHI nodes
-    while (PHINode *PN = dyn_cast<PHINode>(&front())) {
-      // Remove the predecessor first.
-      PN->removeIncomingValue(Pred, !KeepOneInputPHIs);
+  // Return early if there are no PHI nodes to update.
+  if (!isa<PHINode>(begin()))
+    return;
+  unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
 
-      // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
-      if (max_idx == 2) {
-        if (PN->getIncomingValue(0) != PN)
-          PN->replaceAllUsesWith(PN->getIncomingValue(0));
-        else
-          // We are left with an infinite loop with no entries: kill the PHI.
-          PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
-        getInstList().pop_front();    // Remove the PHI node
-      }
-
-      // If the PHI node already only had one entry, it got deleted by
-      // removeIncomingValue.
-    }
-  } else {
-    // Okay, now we know that we need to remove predecessor #pred_idx from all
-    // PHI nodes.  Iterate over each PHI node fixing them up
-    PHINode *PN;
-    for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
-      ++II;
-      PN->removeIncomingValue(Pred, false);
-      // If all incoming values to the Phi are the same, we can replace the Phi
-      // with that value.
-      Value* PNV = nullptr;
-      if (!KeepOneInputPHIs && (PNV = PN->hasConstantValue())) {
+  // Update all PHI nodes.
+  for (iterator II = begin(); isa<PHINode>(II);) {
+    PHINode *PN = cast<PHINode>(II++);
+    PN->removeIncomingValue(Pred, !KeepOneInputPHIs);
+    if (!KeepOneInputPHIs) {
+      // If we have a single predecessor, removeIncomingValue erased the PHI
+      // node itself.
+      if (NumPreds > 1) {
+        if (Value *PNV = PN->hasConstantValue()) {
+          // Replace the PHI node with its constant value.
           PN->replaceAllUsesWith(PNV);
           PN->eraseFromParent();
         }
       }
     }
   }
+}
 
 bool BasicBlock::canSplitPredecessors() const {
   const Instruction *FirstNonPHI = getFirstNonPHI();
   if (isa<LandingPadInst>(FirstNonPHI))
     return true;
   // This is perhaps a little conservative because constructs like
   // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
   // cannot handle such things just yet.