Merge the enhancements from LoopUnroll's FoldBlockIntoPredecessor into

MergeBlockIntoPredecessor. This makes SimplifyCFG slightly more aggressive,
and makes it unnecessary for LoopUnroll to have its own copy of this code.


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

1 files changed, 23 insertions, 47 deletions

diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp
index c2c662fb14..b6f00e24c7 100644
--- a/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -95,54 +95,28 @@ void llvm::DeleteDeadPHIs(BasicBlock *BB) {
       RecursivelyDeleteDeadPHINode(PN);
 }
 
-/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor,
-/// if possible.  The return value indicates success or failure.
-bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) {
-  pred_iterator PI(pred_begin(BB)), PE(pred_end(BB));
-  // Can't merge the entry block.
-  if (pred_begin(BB) == pred_end(BB)) return false;
-  
-  BasicBlock *PredBB = *PI++;
-  for (; PI != PE; ++PI)  // Search all predecessors, see if they are all same
-    if (*PI != PredBB) {
-      PredBB = 0;       // There are multiple different predecessors...
-      break;
-    }
-  
-  // Can't merge if there are multiple predecessors.
-  if (!PredBB) return false;
+/// MergeBlockIntoPredecessor - Folds a basic block into its predecessor if it
+/// only has one predecessor, and that predecessor only has one successor.
+/// If a Pass is given, the LoopInfo and DominatorTree analyses will be kept
+/// current. Returns the combined block, or null if no merging was performed.
+BasicBlock *llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) {
+  // Don't merge if the block has multiple predecessors.
+  BasicBlock *PredBB = BB->getSinglePredecessor();
+  if (!PredBB) return 0;
+  // Don't merge if the predecessor has multiple successors.
+  if (PredBB->getTerminator()->getNumSuccessors() != 1) return 0;
   // Don't break self-loops.
-  if (PredBB == BB) return false;
+  if (PredBB == BB) return 0;
   // Don't break invokes.
-  if (isa<InvokeInst>(PredBB->getTerminator())) return false;
-  
-  succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB));
-  BasicBlock* OnlySucc = BB;
-  for (; SI != SE; ++SI)
-    if (*SI != OnlySucc) {
-      OnlySucc = 0;     // There are multiple distinct successors!
-      break;
-    }
+  if (isa<InvokeInst>(PredBB->getTerminator())) return 0;
   
-  // Can't merge if there are multiple successors.
-  if (!OnlySucc) return false;
-
-  // Can't merge if there is PHI loop.
-  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) {
-    if (PHINode *PN = dyn_cast<PHINode>(BI)) {
-      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
-        if (PN->getIncomingValue(i) == PN)
-          return false;
-    } else
-      break;
-  }
+  // Resolve any PHI nodes at the start of the block.  They are all
+  // guaranteed to have exactly one entry if they exist, unless there are
+  // multiple duplicate (but guaranteed to be equal) entries for the
+  // incoming edges.  This occurs when there are multiple edges from
+  // PredBB to BB.
+  FoldSingleEntryPHINodes(BB);
 
-  // Begin by getting rid of unneeded PHIs.
-  while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
-    PN->replaceAllUsesWith(PN->getIncomingValue(0));
-    BB->getInstList().pop_front();  // Delete the phi node...
-  }
-  
   // Delete the unconditional branch from the predecessor...
   PredBB->getInstList().pop_back();
   
@@ -153,7 +127,7 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) {
   // source...
   BB->replaceAllUsesWith(PredBB);
   
-  // Inherit predecessors name if it exists.
+  // If the predecessor doesn't have a name, take the successor's name.
   if (!PredBB->hasName())
     PredBB->takeName(BB);
   
@@ -172,12 +146,14 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P) {
         DT->eraseNode(BB);
       }
     }
+    // Notify LoopInfo that the block is removed.
+    if (LoopInfo *LI = P->getAnalysisIfAvailable<LoopInfo>())
+      LI->removeBlock(BB);
   }
   
   BB->eraseFromParent();
   
-  
-  return true;
+  return PredBB;
 }
 
 /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)