[SimplifyCFG] Prefer a simplification based on a dominating condition.

Chad Rosier · Chad Rosier · commit 4ab37c00379d · 2016-05-06T14:25:14.000Z
Rather than merge two branches with a common destination. Differential Revision: http://reviews.llvm.org/D19743 llvm-svn: 268735
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -2706,26 +2706,6 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
     if (CE->canTrap())
       return false;
 
-  // If BI is reached from the true path of PBI and PBI's condition implies
-  // BI's condition, we know the direction of the BI branch.
-  if ((PBI->getSuccessor(0) == BI->getParent() ||
-       PBI->getSuccessor(1) == BI->getParent()) &&
-      PBI->getSuccessor(0) != PBI->getSuccessor(1) &&
-      BB->getSinglePredecessor()) {
-    bool FalseDest = PBI->getSuccessor(1) == BI->getParent();
-    Optional<bool> Implication = isImpliedCondition(
-        PBI->getCondition(), BI->getCondition(), DL, FalseDest);
-    if (Implication) {
-      // Turn this into a branch on constant.
-      auto *OldCond = BI->getCondition();
-      ConstantInt *CI = *Implication ? ConstantInt::getTrue(BB->getContext())
-                                     : ConstantInt::getFalse(BB->getContext());
-      BI->setCondition(CI);
-      RecursivelyDeleteTriviallyDeadInstructions(OldCond);
-      return true; // Nuke the branch on constant.
-    }
-  }
-
   // If both branches are conditional and both contain stores to the same
   // address, remove the stores from the conditionals and create a conditional
   // merged store at the end.
@@ -5149,6 +5129,30 @@ bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   if (SimplifyBranchOnICmpChain(BI, Builder, DL))
     return true;
 
+  // If this basic block has a single dominating predecessor block and the
+  // dominating block's condition implies BI's condition, we know the direction
+  // of the BI branch.
+  if (BasicBlock *Dom = BB->getSinglePredecessor()) {
+    auto *PBI = dyn_cast_or_null<BranchInst>(Dom->getTerminator());
+    if (PBI && PBI->isConditional() &&
+        PBI->getSuccessor(0) != PBI->getSuccessor(1) &&
+        (PBI->getSuccessor(0) == BB || PBI->getSuccessor(1) == BB)) {
+      bool CondIsFalse = PBI->getSuccessor(1) == BB;
+      Optional<bool> Implication = isImpliedCondition(
+          PBI->getCondition(), BI->getCondition(), DL, CondIsFalse);
+      if (Implication) {
+        // Turn this into a branch on constant.
+        auto *OldCond = BI->getCondition();
+        ConstantInt *CI = *Implication
+                              ? ConstantInt::getTrue(BB->getContext())
+                              : ConstantInt::getFalse(BB->getContext());
+        BI->setCondition(CI);
+        RecursivelyDeleteTriviallyDeadInstructions(OldCond);
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+      }
+    }
+  }
+
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.
diff --git a/llvm/test/Transforms/SimplifyCFG/basictest.ll b/llvm/test/Transforms/SimplifyCFG/basictest.ll
@@ -25,6 +25,54 @@ define void @test3(i1 %T) {
 ; CHECK-NEXT: ret void
 }
 
+; Folding branch to a common destination.
+; CHECK-LABEL: @test4_fold
+; CHECK: %cmp1 = icmp eq i32 %a, %b
+; CHECK: %cmp2 = icmp ugt i32 %a, 0
+; CHECK: %or.cond = and i1 %cmp1, %cmp2
+; CHECK: br i1 %or.cond, label %else, label %untaken
+; CHECK-NOT: taken:
+; CHECK: ret void
+define void @test4_fold(i32 %a, i32 %b) {
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %taken, label %untaken
+
+taken:
+  %cmp2 = icmp ugt i32 %a, 0
+  br i1 %cmp2, label %else, label %untaken
+
+else:
+  call void @foo()
+  ret void
+
+untaken:
+  ret void
+}
+
+; Prefer a simplification based on a dominating condition rather than folding a
+; branch to a common destination.
+; CHECK-LABEL: @test4
+; CHECK-NOT: br
+; CHECK-NOT: br
+; CHECK-NOT: call
+; CHECK: ret void
+define void @test4_no_fold(i32 %a, i32 %b) {
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %taken, label %untaken
+
+taken:
+  %cmp2 = icmp ugt i32 %a, %b
+  br i1 %cmp2, label %else, label %untaken
+
+else:
+  call void @foo()
+  ret void
+
+untaken:
+  ret void
+}
+
+declare void @foo()
 
 ; PR5795
 define void @test5(i32 %A) {
