Index: llvm/lib/Transforms/Utils/SimplifyCFG.cpp
===================================================================
--- llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -23,6 +23,7 @@
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CmpInstAnalysis.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/InstructionSimplify.h"
@@ -194,6 +195,9 @@
   bool SimplifyIndirectBr(IndirectBrInst *IBI);
   bool SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder);
   bool SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder);
+  Value *GetCombinedCompareInstruction(IRBuilder<> &Builder, Value *CmpA,
+                                       Value *CmpB, bool CmpAIsTrue,
+                                       bool CmpBIsTrue);
 
   bool tryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI,
                                              IRBuilder<> &Builder);
@@ -5821,6 +5825,76 @@
   return PredPred;
 }
 
+Value *SimplifyCFGOpt::GetCombinedCompareInstruction(IRBuilder<> &Builder,
+                                                     Value *CmpA,
+                                                     Value *CmpB,
+                                                     bool CmpAIsTrue,
+                                                     bool CmpBIsTrue) {
+  Type *OpTy = CmpA->getType();
+  if (OpTy != CmpB->getType())
+    return nullptr;
+
+  if (CmpA == CmpB)
+    return nullptr;
+
+  assert(OpTy->isIntegerTy(1) && "Expected i1 type only!");
+
+  ICmpInst *CmpAInst = dyn_cast<ICmpInst>(CmpA);
+  ICmpInst *CmpBInst = dyn_cast<ICmpInst>(CmpB);
+  if (!CmpAInst || !CmpBInst)
+    return nullptr;
+
+  Value *ALHS = CmpAInst->getOperand(0);
+  Value *ARHS = CmpAInst->getOperand(1);
+  // The rest of the logic assumes the CmpA condition is true.  If that's not
+  // the case, invert the predicate to make it so.
+  ICmpInst::Predicate APred =
+      CmpAIsTrue ? CmpAInst->getPredicate() : CmpAInst->getInversePredicate();
+
+  Value *BLHS = CmpBInst->getOperand(0);
+  Value *BRHS = CmpBInst->getOperand(1);
+  // The rest of the logic assumes the CmpB condition is true.  If that's not
+  // the case, invert the predicate to make it so.
+  ICmpInst::Predicate BPred =
+      CmpBIsTrue ? CmpBInst->getPredicate() : CmpBInst->getInversePredicate();
+
+  // Can we infer anything when the two compares have matching operands?
+  bool IsSwapped = false;
+  if (PredicatesFoldable(APred, BPred)) {
+    if (ALHS == BRHS && ARHS == BLHS) {
+      // (icmp1 A, B) & (icmp2 B, A) --> (icmp1 A, B) & (icmp2 A, B)
+      CmpBInst->swapOperands();
+      BLHS = CmpBInst->getOperand(0);
+      BRHS = CmpBInst->getOperand(1);
+      IsSwapped = true;
+    }
+
+    // (icmp1 A, B) & (icmp2 A, B) --> (icmp3 A, B)
+    if (ALHS == BLHS && ARHS == BRHS) {
+      unsigned Code = getICmpCode(CmpAInst, !CmpAIsTrue) &
+                      getICmpCode(CmpBInst, !CmpBIsTrue);
+
+      //if swapped, restore the instruction after calculation.
+      if (IsSwapped)
+        CmpBInst->swapOperands();
+
+      bool isSigned = CmpAInst->isSigned() || CmpBInst->isSigned();
+      ICmpInst::Predicate NewPred;
+      Value *ConstVal =
+          getICmpValue(isSigned, Code, CmpAInst, CmpBInst, NewPred);
+      // the AND Prediction result shouldn't be Constant as this can be
+      // processed in first round implecation check.
+      if (ConstVal)
+        return nullptr;
+
+      if (!CmpBIsTrue)
+        NewPred = ICmpInst::getInversePredicate(NewPred);
+      return Builder.CreateICmp(NewPred, ALHS, ARHS);
+    }
+  }
+  return nullptr;
+}
+
 bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   BasicBlock *BB = BI->getParent();
   const Function *Fn = BB->getParent();
@@ -5861,9 +5935,38 @@
     if (PBI && PBI->isConditional() &&
         PBI->getSuccessor(0) != PBI->getSuccessor(1)) {
       assert(PBI->getSuccessor(0) == BB || PBI->getSuccessor(1) == BB);
-      bool CondIsTrue = PBI->getSuccessor(0) == BB;
-      Optional<bool> Implication = isImpliedCondition(
-          PBI->getCondition(), BI->getCondition(), DL, CondIsTrue);
+
+      Optional<bool> Implication = None;
+      if (BasicBlock *PDom = Dom->getSinglePredecessor()) {
+        auto *PPBI = dyn_cast_or_null<BranchInst>(PDom->getTerminator());
+        // If the single dominating prodecessor block has a single dominating
+        // predecessor block and the two dominating block's condition implies
+        // BI's condition, we can combine the two conditions to know the
+        // direction of the BI branch. E.g. a>=b, a!=b => a>b
+        if (PPBI && PPBI->isConditional() &&
+            PPBI->getSuccessor(0) != PBI->getSuccessor(1)) {
+          bool PCondIsTrue = PPBI->getSuccessor(0) == Dom;
+          bool CondIsTrue = PBI->getSuccessor(0) == BB;
+          // generate an new compare instruction, this new instruction is
+          // the combined And Prediction of PPBI and PBI, it can be used to
+          // calculate implication with BI's condition.
+          Value *CombinedAndCmp = GetCombinedCompareInstruction(
+              Builder, PPBI->getCondition(), PBI->getCondition(), PCondIsTrue,
+              CondIsTrue);
+          if (CombinedAndCmp) {
+            Implication = isImpliedCondition(
+                CombinedAndCmp, BI->getCondition(), DL, CondIsTrue);
+            // CombinedAndCmp is a helper compare instruction for implication
+            // calculation only, need delete it after result returned.
+            RecursivelyDeleteTriviallyDeadInstructions(CombinedAndCmp);
+          }
+        }
+      } else {
+        bool CondIsTrue = PBI->getSuccessor(0) == BB;
+        Implication = isImpliedCondition(PBI->getCondition(),
+            BI->getCondition(), DL, CondIsTrue);
+      }
+
       if (Implication) {
         // Turn this into a branch on constant.
         auto *OldCond = BI->getCondition();
Index: llvm/test/Transforms/SimplifyCFG/branch-fold-three.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/SimplifyCFG/branch-fold-three.ll
@@ -0,0 +1,144 @@
+; RUN: opt %s -S -simplifycfg | not grep "call void @_Z4bar3ii"
+define void @_Z4foo1ii(i32 signext %s, i32 signext %t) #0 {
+entry:
+  %cmp = icmp sge i32 %s, %t
+  br i1 %cmp, label %if.then, label %if.end6
+
+if.then:                                          ; preds = %entry
+  call void @_Z4bar1ii(i32 signext %s, i32 signext %t)
+  %cmp1 = icmp ne i32 %s, %t
+  br i1 %cmp1, label %if.then2, label %if.end6
+
+if.then2:                                         ; preds = %if.then
+  call void @_Z4bar2ii(i32 signext %s, i32 signext %t)
+  %cmp3 = icmp sle i32 %s, %t
+  br i1 %cmp3, label %if.then4, label %if.end6
+
+if.then4:                                         ; preds = %if.then2
+  call void @_Z4bar3ii(i32 signext %s, i32 signext %t)
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.then, %if.then4, %if.then2, %entry
+  ret void
+}
+
+declare void @_Z4bar1ii(i32 signext, i32 signext) #1
+
+declare void @_Z4bar2ii(i32 signext, i32 signext) #1
+
+declare void @_Z4bar3ii(i32 signext, i32 signext) #1
+
+define void @_Z5foo11ii(i32 signext %s, i32 signext %t) #0 {
+entry:
+  %cmp = icmp ne i32 %s, %t
+  br i1 %cmp, label %if.then, label %if.end6
+
+if.then:                                          ; preds = %entry
+  call void @_Z4bar1ii(i32 signext %s, i32 signext %t)
+  %cmp1 = icmp sge i32 %s, %t
+  br i1 %cmp1, label %if.then2, label %if.end6
+
+if.then2:                                         ; preds = %if.then
+  call void @_Z4bar2ii(i32 signext %s, i32 signext %t)
+  %cmp3 = icmp sle i32 %s, %t
+  br i1 %cmp3, label %if.then4, label %if.end6
+
+if.then4:                                         ; preds = %if.then2
+  call void @_Z4bar3ii(i32 signext %s, i32 signext %t)
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.then, %if.then4, %if.then2, %entry
+  ret void
+}
+
+define void @_Z4foo2ii(i32 signext %s, i32 signext %t) #0 {
+entry:
+  %cmp = icmp sge i32 %s, %t
+  br i1 %cmp, label %if.then, label %if.end6
+
+if.then:                                          ; preds = %entry
+  call void @_Z4bar1ii(i32 signext %s, i32 signext %t)
+  %cmp1 = icmp ne i32 %t, %s
+  br i1 %cmp1, label %if.then2, label %if.end6
+
+if.then2:                                         ; preds = %if.then
+  call void @_Z4bar2ii(i32 signext %s, i32 signext %t)
+  %cmp3 = icmp sle i32 %s, %t
+  br i1 %cmp3, label %if.then4, label %if.end6
+
+if.then4:                                         ; preds = %if.then2
+  call void @_Z4bar3ii(i32 signext %s, i32 signext %t)
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.then, %if.then4, %if.then2, %entry
+  ret void
+}
+
+define void @_Z5foo21ii(i32 signext %s, i32 signext %t) #0 {
+entry:
+  %cmp = icmp ne i32 %s, %t
+  br i1 %cmp, label %if.then, label %if.end6
+
+if.then:                                          ; preds = %entry
+  call void @_Z4bar1ii(i32 signext %s, i32 signext %t)
+  %cmp1 = icmp sle i32 %t, %s
+  br i1 %cmp1, label %if.then2, label %if.end6
+
+if.then2:                                         ; preds = %if.then
+  call void @_Z4bar2ii(i32 signext %s, i32 signext %t)
+  %cmp3 = icmp sle i32 %s, %t
+  br i1 %cmp3, label %if.then4, label %if.end6
+
+if.then4:                                         ; preds = %if.then2
+  call void @_Z4bar3ii(i32 signext %s, i32 signext %t)
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.then, %if.then4, %if.then2, %entry
+  ret void
+}
+
+define void @_Z4foo3ii(i32 signext %s, i32 signext %t) #0 {
+entry:
+  %cmp = icmp sle i32 %t, %s
+  br i1 %cmp, label %if.then, label %if.end6
+
+if.then:                                          ; preds = %entry
+  call void @_Z4bar1ii(i32 signext %s, i32 signext %t)
+  %cmp1 = icmp ne i32 %t, %s
+  br i1 %cmp1, label %if.then2, label %if.end6
+
+if.then2:                                         ; preds = %if.then
+  call void @_Z4bar2ii(i32 signext %s, i32 signext %t)
+  %cmp3 = icmp sle i32 %s, %t
+  br i1 %cmp3, label %if.then4, label %if.end6
+
+if.then4:                                         ; preds = %if.then2
+  call void @_Z4bar3ii(i32 signext %s, i32 signext %t)
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.then, %if.then4, %if.then2, %entry
+  ret void
+}
+
+define void @_Z5foo31ii(i32 signext %s, i32 signext %t) #0 {
+entry:
+  %cmp = icmp ne i32 %t, %s
+  br i1 %cmp, label %if.then, label %if.end6
+
+if.then:                                          ; preds = %entry
+  call void @_Z4bar1ii(i32 signext %s, i32 signext %t)
+  %cmp1 = icmp sle i32 %t, %s
+  br i1 %cmp1, label %if.then2, label %if.end6
+
+if.then2:                                         ; preds = %if.then
+  call void @_Z4bar2ii(i32 signext %s, i32 signext %t)
+  %cmp3 = icmp sle i32 %s, %t
+  br i1 %cmp3, label %if.then4, label %if.end6
+
+if.then4:                                         ; preds = %if.then2
+  call void @_Z4bar3ii(i32 signext %s, i32 signext %t)
+  br label %if.end6
+
+if.end6:                                          ; preds = %if.then, %if.then4, %if.then2, %entry
+  ret void
+}