[SimplifyCFG] Prefer a simplification based on dominating conditions over merging a common destination.

[mcrosier]

Summary

Often we can simplify the CFG based on dominating conditions. However, we miss opportunities when we merge blocks with a common destination.

For example, before this change we would need to run -simplifycfg -instcombine -simplifycfg on test4_no_fold to arrive at the code we can now generate after a single run of -simplifycfg. We didn't appear to have any test coverage when merging common destinations, so I went ahead and added test4_fold as an example.

I found a case in Spec2006/soplex where this further removed unreachable code. As expected, I found no cases where code size increased across Spec2000/Spec2006. As isImpliedCondition continues to expand in capabilities I expect more opportunities to be exposed.

Chad

[mcrosier]

Ping.

[reames]

LGTM

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

if (BlockIsSimpleEnoughToThreadThrough(BB)) {
       return true;
     }
   }
 
   if (auto *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
     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.
   if (MergeCondStores && mergeConditionalStores(PBI, BI))
     return true;
 
   // If this is a conditional branch in an empty block, and if any
   // predecessors are a conditional branch to one of our destinations,
if (&*I == BI) {
         return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
     }
   }
 
   // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction.
   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.
   if (FoldBranchToCommonDest(BI, BonusInstThreshold))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
   // We have a conditional branch to two blocks that are only reachable
   // from BI.  We know that the condbr dominates the two blocks, so see if

llvm/trunk/test/Transforms/SimplifyCFG/basictest.ll

 
 define void @test3(i1 %T) {
         br i1 %T, label %1, label %1
         ret void
 ; CHECK-LABEL: @test3(
 ; 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) {
   switch i32 %A, label %return [
     i32 2, label %1
     i32 10, label %2
   ]