Index: include/llvm/Analysis/ValueTracking.h
===================================================================
--- include/llvm/Analysis/ValueTracking.h
+++ include/llvm/Analysis/ValueTracking.h
@@ -436,16 +436,18 @@
   /// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20).
   ConstantRange getConstantRangeFromMetadata(MDNode &RangeMD);
 
-  /// Return true if RHS is known to be implied by LHS.  A & B must be i1
-  /// (boolean) values or a vector of such values. Note that the truth table for
-  /// implication is the same as <=u on i1 values (but not <=s!).  The truth
-  /// table for both is:
+  /// Return true if RHS is known to be implied by LHS.  The implication may be
+  /// either true or false depending on what is returned in ImpliedTrue.
+  /// A & B must be i1 (boolean) values or a vector of such values. Note that
+  /// the truth table for implication is the same as <=u on i1 values (but not
+  /// <=s!).  The truth table for both is:
   ///    | T | F (B)
   ///  T | T | F
   ///  F | T | T
   /// (A)
-  bool isImpliedCondition(Value *LHS, Value *RHS, const DataLayout &DL,
-                          unsigned Depth = 0, AssumptionCache *AC = nullptr,
+  bool isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue,
+                          const DataLayout &DL, unsigned Depth = 0,
+                          AssumptionCache *AC = nullptr,
                           const Instruction *CxtI = nullptr,
                           const DominatorTree *DT = nullptr);
 } // end namespace llvm
Index: lib/Analysis/InstructionSimplify.cpp
===================================================================
--- lib/Analysis/InstructionSimplify.cpp
+++ lib/Analysis/InstructionSimplify.cpp
@@ -2131,14 +2131,16 @@
       if (match(RHS, m_Zero()))
         return LHS;
       break;
-    case ICmpInst::ICMP_UGE:
+    case ICmpInst::ICMP_UGE: {
       // X >=u 1 -> X
       if (match(RHS, m_One()))
         return LHS;
-      if (isImpliedCondition(RHS, LHS, Q.DL))
+      bool ImpliedTrue;
+      if (isImpliedCondition(RHS, LHS, ImpliedTrue, Q.DL) && ImpliedTrue)
         return getTrue(ITy);
       break;
-    case ICmpInst::ICMP_SGE:
+    }
+    case ICmpInst::ICMP_SGE: {
       /// For signed comparison, the values for an i1 are 0 and -1
       /// respectively. This maps into a truth table of:
       /// LHS | RHS | LHS >=s RHS   | LHS implies RHS
@@ -2146,9 +2148,11 @@
       ///  0  |  1  |  1 (0 >= -1)  |  1
       ///  1  |  0  |  0 (-1 >= 0)  |  0
       ///  1  |  1  |  1 (-1 >= -1) |  1
-      if (isImpliedCondition(LHS, RHS, Q.DL))
+      bool ImpliedTrue;
+      if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue)
         return getTrue(ITy);
       break;
+    }
     case ICmpInst::ICMP_SLT:
       // X <s 0 -> X
       if (match(RHS, m_Zero()))
@@ -2159,11 +2163,13 @@
       if (match(RHS, m_One()))
         return LHS;
       break;
-    case ICmpInst::ICMP_ULE:
-      if (isImpliedCondition(LHS, RHS, Q.DL))
+    case ICmpInst::ICMP_ULE: {
+      bool ImpliedTrue;
+      if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue)
         return getTrue(ITy);
       break;
     }
+    }
   }
 
   // If we are comparing with zero then try hard since this is a common case.
Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -3788,16 +3788,126 @@
   }
 }
 
-bool llvm::isImpliedCondition(Value *LHS, Value *RHS, const DataLayout &DL,
-                              unsigned Depth, AssumptionCache *AC,
-                              const Instruction *CxtI,
+// The predicates must match sign or at least one of them must be an equality
+// comparison (which is signless).
+static bool PredicatesComparable(CmpInst::Predicate APred,
+                                 CmpInst::Predicate BPred) {
+  if (ICmpInst::isSigned(APred) != ICmpInst::isSigned(BPred) &&
+      !ICmpInst::isEquality(APred) && !ICmpInst::isEquality(BPred))
+    return false;
+  return true;
+}
+
+/// Return true if "icmp2 BPred BLHS BRHS" is known to be implied by "icmp1
+/// APred ALHS ARHS".  The implication may be either true or false depending on
+/// the return value of ImpliedTrue.
+static bool isImpliedCondMatchingOperands(CmpInst::Predicate APred, Value *ALHS,
+                                          Value *ARHS, CmpInst::Predicate BPred,
+                                          Value *BLHS, Value *BRHS,
+                                          bool &ImpliedTrue) {
+  // The operands of the two compares must match.
+  bool IsMatchingOps = (ALHS == BLHS && ARHS == BRHS);
+  bool IsSwappedOps = (ALHS == BRHS && ARHS == BLHS);
+  if (!IsMatchingOps && !IsSwappedOps)
+    return false;
+
+  // Canonicalize the operands so they're matching.
+  if (IsSwappedOps) {
+    std::swap(BLHS, BRHS);
+    BPred = ICmpInst::getSwappedPredicate(BPred);
+  }
+
+  // If the predicates match, then we know the first condition implies the
+  // second is true.
+  if (APred == BPred) {
+    ImpliedTrue = true;
+    return true;
+  }
+
+  // The predicates must match sign or at least one of them must be an equality
+  // comparison (which is signless).
+  if (!PredicatesComparable(APred, BPred))
+    return false;
+
+  // The next bit of logic is the same for unsigned and signed comparison.
+  // Therefore, unconditionally convert the predicates to their unsigned
+  // equivalent to reduce the amount of logic needed.  This is safe because
+  // we've already verified that the sign of the predicates match.
+  auto UnsignedAPred = ICmpInst::getUnsignedPredicate(APred);
+  auto UnsignedBPred = ICmpInst::getUnsignedPredicate(BPred);
+
+  // If an inverted APred matches BPred, we can infer the second condition is
+  // false in many cases.
+  if (CmpInst::getInversePredicate(UnsignedAPred) == UnsignedBPred) {
+    switch (UnsignedAPred) {
+    default:
+      break;
+    case CmpInst::ICMP_EQ:  // A == B implies A != B is false.
+    case CmpInst::ICMP_NE:  // A != B implies A == B is false.
+    case CmpInst::ICMP_UGT: // A > B implies A <= B is false.
+    case CmpInst::ICMP_ULT: // A < B implies A >= B is false.
+    case CmpInst::ICMP_UGE: // A >= B implies A < B is false.
+    case CmpInst::ICMP_ULE: // A <= B implies A > B is false.
+      ImpliedTrue = false;
+      return true;
+    }
+  }
+
+  // If a swapped APred matches BPred, we can infer the second condition is
+  // false in many cases.
+  if (CmpInst::getSwappedPredicate(UnsignedAPred) == UnsignedBPred) {
+    switch (UnsignedAPred) {
+    default:
+      break;
+    case CmpInst::ICMP_UGT: // A > B implies A < B is false.
+    case CmpInst::ICMP_ULT: // A < B implies A > B is false.
+      ImpliedTrue = false;
+      return true;
+    }
+  }
+
+  switch (UnsignedAPred) {
+  default:
+    break;
+  case CmpInst::ICMP_EQ:
+    // A == B implies A > B and A < B are false.
+    if (CmpInst::isFalseWhenEqual(UnsignedBPred)) {
+      ImpliedTrue = false;
+      return true;
+    }
+    break;
+  case CmpInst::ICMP_UGT:
+  case CmpInst::ICMP_ULT:
+    // A > B implies A == B is false.
+    // A < B implies A == B is false.
+    if (UnsignedBPred == CmpInst::ICMP_EQ) {
+      ImpliedTrue = false;
+      return true;
+    }
+    // A > B implies A != B is true.
+    // A < B implies A != B is true.
+    if (UnsignedBPred == CmpInst::ICMP_NE) {
+      ImpliedTrue = true;
+      return true;
+    }
+    break;
+  }
+  return false;
+}
+
+bool llvm::isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue,
+                              const DataLayout &DL, unsigned Depth,
+                              AssumptionCache *AC, const Instruction *CxtI,
                               const DominatorTree *DT) {
   assert(LHS->getType() == RHS->getType() && "mismatched type");
   Type *OpTy = LHS->getType();
   assert(OpTy->getScalarType()->isIntegerTy(1));
 
   // LHS ==> RHS by definition
-  if (LHS == RHS) return true;
+  if (LHS == RHS) {
+    ImpliedTrue = true;
+    return true;
+  }
 
   if (OpTy->isVectorTy())
     // TODO: extending the code below to handle vectors
@@ -3812,9 +3922,15 @@
       !match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS))))
     return false;
 
-  if (APred == BPred)
+  if (isImpliedCondMatchingOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS,
+                                    ImpliedTrue))
+    return true;
+
+  if (APred == BPred) {
+    ImpliedTrue = true;
     return isImpliedCondOperands(APred, ALHS, ARHS, BLHS, BRHS, DL, Depth, AC,
                                  CxtI, DT);
+  }
 
   return false;
 }
Index: lib/Transforms/Scalar/JumpThreading.cpp
===================================================================
--- lib/Transforms/Scalar/JumpThreading.cpp
+++ lib/Transforms/Scalar/JumpThreading.cpp
@@ -928,9 +928,10 @@
     if (!PBI || !PBI->isConditional() || PBI->getSuccessor(0) != CurrentBB)
       return false;
 
-    if (isImpliedCondition(PBI->getCondition(), Cond, DL)) {
-      BI->getSuccessor(1)->removePredecessor(BB);
-      BranchInst::Create(BI->getSuccessor(0), BI);
+    bool ImpliedTrue;
+    if (isImpliedCondition(PBI->getCondition(), Cond, ImpliedTrue, DL)) {
+      BI->getSuccessor(ImpliedTrue ? 1 : 0)->removePredecessor(BB);
+      BranchInst::Create(BI->getSuccessor(ImpliedTrue ? 0 : 1), BI);
       BI->eraseFromParent();
       return true;
     }
Index: lib/Transforms/Utils/SimplifyCFG.cpp
===================================================================
--- lib/Transforms/Utils/SimplifyCFG.cpp
+++ lib/Transforms/Utils/SimplifyCFG.cpp
@@ -2722,13 +2722,17 @@
 
   // 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.
+  bool ImpliedTrue;
   if (PBI->getSuccessor(0) == BI->getParent() &&
-      isImpliedCondition(PBI->getCondition(), BI->getCondition(), DL) &&
+      isImpliedCondition(PBI->getCondition(), BI->getCondition(), ImpliedTrue,
+                         DL) &&
       PBI->getSuccessor(0) != PBI->getSuccessor(1) &&
       BB->getSinglePredecessor()) {
     // Turn this into a branch on constant.
     auto *OldCond = BI->getCondition();
-    BI->setCondition(ConstantInt::getTrue(BB->getContext()));
+    ConstantInt *CI = ImpliedTrue ? ConstantInt::getTrue(BB->getContext())
+                                  : ConstantInt::getFalse(BB->getContext());
+    BI->setCondition(CI);
     RecursivelyDeleteTriviallyDeadInstructions(OldCond);
     return true;  // Nuke the branch on constant.
   }
Index: test/Transforms/JumpThreading/implied-cond.ll
===================================================================
--- test/Transforms/JumpThreading/implied-cond.ll
+++ test/Transforms/JumpThreading/implied-cond.ll
@@ -96,3 +96,32 @@
   call void @side_effect(i32 %t)
   ret void
 }
+
+; A s<= B implies A s> B is false.
+; CHECK-LABEL: @test3(
+; CHECK: entry:
+; CHECK: br i1 %cmp, label %if.end, label %if.end3
+; CHECK-NOT: br i1 %cmp1, label %if.then2, label %if.end
+; CHECK-NOT: call void @side_effect(i32 0)
+; CHECK: br label %if.end3
+; CHECK: ret void
+
+define void @test3(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sle i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @side_effect(i32 0)
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
Index: test/Transforms/SimplifyCFG/implied-cond-matching.ll
===================================================================
--- /dev/null
+++ test/Transforms/SimplifyCFG/implied-cond-matching.ll
@@ -0,0 +1,310 @@
+; RUN: opt %s -S -simplifycfg | FileCheck %s
+
+; Test same condition with swapped operands.
+; void test_swapped_ops(unsigned a, unsigned b) {
+;   if (a > b) {
+;     if (b > a) <- always false
+;       dead();
+;     alive();
+;   }
+; }
+;
+; CHECK-LABEL: @test_swapped_ops
+; CHECK-NOT: call void @dead()
+; CHECK: call void @alive()
+; CHECK: ret
+define void @test_swapped_ops(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ugt i32 %b, %a
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  call void @alive()
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; void test_swapped_pred(unsigned a, unsigned b) {
+;   if (a > b) {
+;     alive();
+;     if (b < a) <- always true; remove branch
+;       alive();
+;   }
+; }
+;
+; CHECK-LABEL: @test_swapped_pred
+; CHECK: call void @alive()
+; CHECK-NEXT: call void @alive()
+; CHECK: ret
+define void @test_swapped_pred(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  call void @alive()
+  %cmp1 = icmp ult i32 %b, %a
+  br i1 %cmp1, label %if.then2, label %if.end3
+
+if.then2:
+  call void @alive()
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A == B implies A > B is false
+; A == B implies A < B is false
+; A == B implies A != B is false
+; CHECK-LABEL: @test_eq
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_eq(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, %b
+  br i1 %cmp, label %if.end, label %if.end9
+
+if.end:
+  %cmp3 = icmp ugt i32 %a, %b
+  br i1 %cmp3, label %if.then4, label %if.end5
+
+if.then4:
+  call void @dead()
+  br label %if.end5
+
+if.end5:
+  %cmp6 = icmp ult i32 %a, %b
+  br i1 %cmp6, label %if.then7, label %if.end8
+
+if.then7:
+  call void @dead()
+  br label %if.end8
+
+if.end8:
+  br label %if.end9
+
+if.end9:
+  ret void
+}
+
+; A != B implies A == B is false
+; CHECK-LABEL: @test_ne
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_ne(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ne i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A > B implies A == B is false.
+; A > B implies A <= B is false.
+; A > B implies A != B is true.
+; CHECK-LABEL: @test_gt
+; CHECK-NOT: dead
+; CHECK: alive
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_gt(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end9
+
+if.then:
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  %cmp3 = icmp ule i32 %a, %b
+  br i1 %cmp3, label %if.then4, label %if.end5
+
+if.then4:
+  call void @dead()
+  br label %if.end5
+
+if.end5:
+  %cmp6 = icmp ne i32 %a, %b
+  br i1 %cmp6, label %if.then7, label %if.end8
+
+if.then7:
+  call void @alive()
+  br label %if.end8
+
+if.end8:
+  br label %if.end9
+
+if.end9:
+  ret void
+}
+
+; A < B implies A == B is false.
+; A < B implies A >= B is false.
+; A < B implies A != B is true.
+; CHECK-LABEL: @test_lt
+; CHECK-NOT: dead
+; CHECK: alive
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_lt(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ult i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end9
+
+if.then:
+  %cmp1 = icmp eq i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  %cmp3 = icmp ult i32 %a, %b
+  br i1 %cmp3, label %if.end5, label %if.then4
+
+if.then4:
+  call void @dead()
+  br label %if.end5
+
+if.end5:
+  %cmp6 = icmp eq i32 %a, %b
+  br i1 %cmp6, label %if.end8, label %if.then7
+
+if.then7:
+  call void @alive()
+  br label %if.end8
+
+if.end8:
+  br label %if.end9
+
+if.end9:
+  ret void
+}
+
+; A >= B implies A < B is false.
+; CHECK-LABEL: @test_ge
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_ge(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp uge i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ult i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A <= B implies A > B is false.
+; CHECK-LABEL: @test_le
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_le(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ule i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ugt i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @dead()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A u<= B does not imply A s> B is false.
+; CHECK-LABEL: @test_ule_sgt_unsafe
+; CHECK: alive
+; CHECK: ret void
+define void @test_ule_sgt_unsafe(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ule i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %a, %b
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+; A u> B does not imply B s> A is false.
+; CHECK-LABEL: @test_ugt_sgt_unsafe
+; CHECK: alive
+; CHECK: ret void
+define void @test_ugt_sgt_unsafe(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, %b
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %b, %a
+  br i1 %cmp1, label %if.then2, label %if.end
+
+if.then2:
+  call void @alive()
+  br label %if.end
+
+if.end:
+  br label %if.end3
+
+if.end3:
+  ret void
+}
+
+declare void @dead()
+declare void @alive()