Implement PR5795 by merging duplicated return blocks. This could go further

by merging all returns in a function into a single one, but simplifycfg 
currently likes to duplicate the return (an unfortunate choice!)


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

1 files changed, 72 insertions, 0 deletions

diff --git a/lib/Transforms/Scalar/SimplifyCFGPass.cpp b/lib/Transforms/Scalar/SimplifyCFGPass.cpp
index e905952c5d..a36da78519 100644
--- a/lib/Transforms/Scalar/SimplifyCFGPass.cpp
+++ b/lib/Transforms/Scalar/SimplifyCFGPass.cpp
@@ -189,6 +189,77 @@ static bool RemoveUnreachableBlocksFromFn(Function &F) {
   return true;
 }
 
+/// MergeEmptyReturnBlocks - If we have more than one empty (other than phi
+/// node) return blocks, merge them together to promote recursive block merging.
+static bool MergeEmptyReturnBlocks(Function &F) {
+  bool Changed = false;
+  
+  BasicBlock *RetBlock = 0;
+  
+  // Scan all the blocks in the function, looking for empty return blocks.
+  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
+    BasicBlock &BB = *BBI++;
+    
+    // Only look at return blocks.
+    ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
+    if (Ret == 0) continue;
+    
+    // Only look at the block if it is empty or the only other thing in it is a
+    // single PHI node that is the operand to the return.
+    if (Ret != &BB.front()) {
+      // Check for something else in the block.
+      BasicBlock::iterator I = Ret;
+      --I;
+      if (!isa<PHINode>(I) || I != BB.begin() ||
+          Ret->getNumOperands() == 0 ||
+          Ret->getOperand(0) != I)
+        continue;
+    }
+    
+    // If this is the first returning block, remember it and keep going.
+    if (RetBlock == 0) {
+      RetBlock = &BB;
+      continue;
+    }
+    
+    // Otherwise, we found a duplicate return block.  Merge the two.
+    Changed = true;
+    
+    // Case when there is no input to the return or when the returned values
+    // agree is trivial.  Note that they can't agree if there are phis in the
+    // blocks.
+    if (Ret->getNumOperands() == 0 ||
+        Ret->getOperand(0) == 
+          cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
+      BB.replaceAllUsesWith(RetBlock);
+      BB.eraseFromParent();
+      continue;
+    }
+    
+    // If the canonical return block has no PHI node, create one now.
+    PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
+    if (RetBlockPHI == 0) {
+      Value *InVal = cast<ReturnInst>(RetBlock->begin())->getOperand(0);
+      RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(), "merge",
+                                    &RetBlock->front());
+      
+      for (pred_iterator PI = pred_begin(RetBlock), E = pred_end(RetBlock);
+           PI != E; ++PI)
+        RetBlockPHI->addIncoming(InVal, *PI);
+      RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
+    }
+    
+    // Turn BB into a block that just unconditionally branches to the return
+    // block.  This handles the case when the two return blocks have a common
+    // predecessor but that return different things.
+    RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
+    BB.getTerminator()->eraseFromParent();
+    BranchInst::Create(RetBlock, &BB);
+  }
+  
+  return Changed;
+}
+
 /// IterativeSimplifyCFG - Call SimplifyCFG on all the blocks in the function,
 /// iterating until no more changes are made.
 static bool IterativeSimplifyCFG(Function &F) {
@@ -216,6 +287,7 @@ static bool IterativeSimplifyCFG(Function &F) {
 //
 bool CFGSimplifyPass::runOnFunction(Function &F) {
   bool EverChanged = RemoveUnreachableBlocksFromFn(F);
+  EverChanged |= MergeEmptyReturnBlocks(F);
   EverChanged |= IterativeSimplifyCFG(F);
   
   // If neither pass changed anything, we're done.