Teach LoopSimplify how to merge multiple loop exits into a single exit,

when one of them can be converted to a trivial icmp and conditional
branch.

This addresses what is essentially a phase ordering problem.
SimplifyCFG knows how to do this transformation, but it doesn't do so
if the primary block has any instructions in it other than an icmp and
a branch. In the given testcase, the block contains other instructions,
however they are loop-invariant and can be hoisted. SimplifyCFG doesn't
have LoopInfo though, so it can't hoist them. And, it's important that
the blocks be merged before LoopRotation, as it doesn't support
multiple-exit loops.


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

2 files changed, 76 insertions, 1 deletions

diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 03d273d25d..d03591081f 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -42,6 +42,7 @@
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/ADT/SetOperations.h"
@@ -258,6 +259,80 @@ ReprocessLoop:
       PN->eraseFromParent();
     }
 
+  // If this loop has muliple exits and the exits all go to the same
+  // block, attempt to merge the exits. This helps several passes, such
+  // as LoopRotation, which do not support loops with multiple exits.
+  // SimplifyCFG also does this (and this code uses the same utility
+  // function), however this code is loop-aware, where SimplifyCFG is
+  // not. That gives it the advantage of being able to hoist
+  // loop-invariant instructions out of the way to open up more
+  // opportunities, and the disadvantage of having the responsibility
+  // to preserve dominator information.
+  if (ExitBlocks.size() > 1 && L->getUniqueExitBlock()) {
+    SmallVector<BasicBlock*, 8> ExitingBlocks;
+    L->getExitingBlocks(ExitingBlocks);
+    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
+      BasicBlock *ExitingBlock = ExitingBlocks[i];
+      if (!ExitingBlock->getSinglePredecessor()) continue;
+      BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
+      if (!BI || !BI->isConditional()) continue;
+      CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
+      if (!CI || CI->getParent() != ExitingBlock) continue;
+
+      // Attempt to hoist out all instructions except for the
+      // comparison and the branch.
+      bool AllInvariant = true;
+      for (BasicBlock::iterator I = ExitingBlock->begin(),
+           E = ExitingBlock->end(); I != E; ) {
+        Instruction *Inst = I++;
+        if (Inst == BI || Inst == CI)
+          continue;
+        if (Inst->isTrapping()) {
+          AllInvariant = false;
+          break;
+        }
+        for (unsigned j = 0, f = Inst->getNumOperands(); j != f; ++j)
+          if (!L->isLoopInvariant(Inst->getOperand(j))) {
+            AllInvariant = false;
+            break;
+          }
+        if (!AllInvariant)
+          break;
+        // Hoist.
+        Inst->moveBefore(L->getLoopPreheader()->getTerminator());
+      }
+      if (!AllInvariant) continue;
+
+      // The block has now been cleared of all instructions except for
+      // a comparison and a conditional branch. SimplifyCFG may be able
+      // to fold it now.
+      if (!FoldBranchToCommonDest(BI)) continue;
+
+      // Success. The block is now dead, so remove it from the loop,
+      // update the dominator tree and dominance frontier, and delete it.
+      assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock));
+      Changed = true;
+      L->removeBlockFromLoop(ExitingBlock);
+
+      DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>();
+      DomTreeNode *Node = DT->getNode(ExitingBlock);
+      const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
+        Node->getChildren();
+      for (unsigned k = 0, g = Children.size(); k != g; ++k) {
+        DT->changeImmediateDominator(Children[k], Node->getIDom());
+        if (DF) DF->changeImmediateDominator(Children[k]->getBlock(),
+                                             Node->getIDom()->getBlock(),
+                                             DT);
+      }
+      DT->eraseNode(ExitingBlock);
+      if (DF) DF->removeBlock(ExitingBlock);
+
+      BI->getSuccessor(0)->removePredecessor(ExitingBlock);
+      BI->getSuccessor(1)->removePredecessor(ExitingBlock);
+      ExitingBlock->eraseFromParent();
+    }
+  }
+
   return Changed;
 }
 
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index ee0f6a65de..58d4d5a344 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -1492,7 +1492,7 @@ static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) {
 /// and if a predecessor branches to us and one of our successors, fold the
 /// setcc into the predecessor and use logical operations to pick the right
 /// destination.
-static bool FoldBranchToCommonDest(BranchInst *BI) {
+bool llvm::FoldBranchToCommonDest(BranchInst *BI) {
   BasicBlock *BB = BI->getParent();
   Instruction *Cond = dyn_cast<Instruction>(BI->getCondition());
   if (Cond == 0) return false;