Index: lib/Analysis/ValueTracking.cpp
===================================================================
--- lib/Analysis/ValueTracking.cpp
+++ lib/Analysis/ValueTracking.cpp
@@ -3788,6 +3788,97 @@
   }
 }
 
+static bool isImpliedCondImmOperands(CmpInst::Predicate APred, Value *ALHS,
+                                     Value *ARHS, CmpInst::Predicate BPred,
+                                     Value *BLHS, Value *BRHS,
+                                     bool &ImpliedTrue) {
+  // The below logic assumes the ALHS == BLHS and both RHS are constants.
+  if (ALHS != BLHS || !isa<ConstantInt>(ARHS) || !isa<ConstantInt>(BRHS))
+    return false;
+
+  // Both the LHSs and RHSs (i.e., constant operands) match.
+  if (ARHS == BRHS) {
+    // If the constant operands and predicates match the first condition imples
+    // the second condition is true.
+    if (APred == BPred) {
+      ImpliedTrue = true;
+      return true;
+    }
+
+    // If the constant operands match and the predicates are swapped we can
+    // infer the second condition is false because if, for example, A > 5 is
+    // true, then A < 5 must be false.
+    if (APred == ICmpInst::getSwappedPredicate(BPred)) {
+      switch (APred) {
+      default:
+        break;
+      case CmpInst::ICMP_UGT:
+      case CmpInst::ICMP_ULT:
+      case CmpInst::ICMP_SGT:
+      case CmpInst::ICMP_SLT:
+        ImpliedTrue = false;
+        return true;
+      }
+    }
+  }
+
+  if (APred == BPred) {
+    switch (APred) {
+    default:
+      break;
+    case CmpInst::ICMP_EQ:
+      // A == C implies A == C' is false.
+      if (ARHS != BRHS) {
+        ImpliedTrue = false;
+        return true;
+      }
+      break;
+    case CmpInst::ICMP_SGT:
+    case CmpInst::ICMP_SGE:
+      // A > C implies A > C' is true if C >= C'.
+      // A >= C implies A >= C' is true if C >= C'.
+      if (cast<ConstantInt>(ARHS)->getSExtValue() >=
+          cast<ConstantInt>(BRHS)->getSExtValue()) {
+        ImpliedTrue = true;
+        return true;
+      }
+      break;
+    case CmpInst::ICMP_UGT:
+    case CmpInst::ICMP_UGE:
+      // A > C implies A > C' is true if C >= C'.
+      // A >= C implies A >= C' is true if C >= C'.
+      if (cast<ConstantInt>(ARHS)->getZExtValue() >=
+          cast<ConstantInt>(BRHS)->getZExtValue()) {
+        ImpliedTrue = true;
+        return true;
+      }
+      break;
+    case CmpInst::ICMP_SLT:
+    case CmpInst::ICMP_SLE:
+      // A < C implies A < C' is true if C <= C'.
+      // A <= C implies A <= C' is true if C <= C'.
+      if (cast<ConstantInt>(ARHS)->getSExtValue() <=
+          cast<ConstantInt>(BRHS)->getSExtValue()) {
+        ImpliedTrue = true;
+        return true;
+      }
+      break;
+    case CmpInst::ICMP_ULT:
+    case CmpInst::ICMP_ULE:
+      // A < C implies A < C' is true if C < C'.
+      // A <= C implies A <= C' is true if C <= C'.
+      if (cast<ConstantInt>(ARHS)->getZExtValue() <=
+          cast<ConstantInt>(BRHS)->getZExtValue()) {
+        ImpliedTrue = true;
+        return true;
+      }
+      break;
+    }
+  }
+  // FIXME: Handle cases where APred != BPred.
+  return false;
+}
+
 /// Return true if "icmp2 Pred op1 op2" is known to be implied by "icmp1 Pred
 /// op1 op2".  The implication may be either true or false depending on the
 /// return value of ImpliedTrue.
@@ -3914,6 +4005,10 @@
       !match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS))))
     return false;
 
+  if (isImpliedCondImmOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS,
+                               ImpliedTrue))
+    return true;
+
   if (isImpliedCondMatchingOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS,
                                     ImpliedTrue))
     return true;
Index: test/Transforms/SimplifyCFG/implied-cond-imm.ll
===================================================================
--- /dev/null
+++ test/Transforms/SimplifyCFG/implied-cond-imm.ll
@@ -0,0 +1,318 @@
+; RUN: opt %s -S -simplifycfg | FileCheck %s
+
+; A == C implies A == C is true.
+; CHECK-LABEL: @test_eq5_eq5
+; CHECK: %cmp = icmp eq i32 %a, 5
+; CHECK-NOT: %cmp1 = icmp eq i32 %a, 5
+; CHECK: ret void
+define void @test_eq5_eq5(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp eq i32 %a, 5
+  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 == C implies A == C' is false.
+; CHECK-LABEL: @test_eq5_eq6
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_eq5_eq6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp eq i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp eq i32 %a, 6
+  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 != C implies A != C is true.
+; CHECK-LABEL: @test_ne5_ne5
+; CHECK: %cmp = icmp ne i32 %a, 5
+; CHECK-NOT: %cmp1 = icmp ne i32 %a, 5
+; CHECK: ret void
+define void @test_ne5_ne5(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ne i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ne i32 %a, 5
+  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 > C implies A < C is false.
+; CHECK-LABEL: @test_ugt5_ult5
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_ugt5_ult5(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ult i32 %a, 5
+  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 < C implies A > C is false.
+; CHECK-LABEL: @test_slt5_sgt5
+; CHECK-NOT: dead
+; CHECK: ret void
+define void @test_slt5_sgt5(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp slt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %a, 5
+  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 > C implies A > C' is true if C >= C'.
+; CHECK-LABEL: @test_sgt5_sgt4
+; CHECK-NOT: %cmp1 = icmp sgt i32 %a, 4
+; CHECK: ret void
+define void @test_sgt5_sgt4(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sgt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sgt i32 %a, 4
+  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 >= C implies A >= C' is true if C >= C'.
+; CHECK-LABEL: @test_sge5_sge4
+; CHECK-NOT: %cmp1 = icmp sge i32 %a, 4
+; CHECK: ret void
+define void @test_sge5_sge4(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sge i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sge i32 %a, 4
+  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 < C implies A < C' is true if C <= C'.
+; CHECK-LABEL: @test_slt5_slt6
+; CHECK-NOT: %cmp1 = icmp slt i32 %a, 6
+; CHECK: ret void
+define void @test_slt5_slt6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp slt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp slt i32 %a, 6
+  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 <= C implies A <= C' is true if C <= C'.
+; CHECK-LABEL: @test_sle5_sle6
+; CHECK-NOT: %cmp1 = icmp sle i32 %a, 6
+; CHECK: ret void
+define void @test_sle5_sle6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp sle i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp sle i32 %a, 6
+  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 > C implies A > C' is true if C >= C'.
+; CHECK-LABEL: @test_ugt5_ugt4
+; CHECK-NOT: %cmp1 = icmp ugt i32 %a, 4
+; CHECK: ret void
+define void @test_ugt5_ugt4(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ugt i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ugt i32 %a, 4
+  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 >= C implies A >= C' is true if C >= C'.
+; CHECK-LABEL: @test_uge5_uge4
+; CHECK-NOT: %cmp1 = icmp uge i32 %a, 4
+; CHECK: ret void
+define void @test_uge5_uge4(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp uge i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp uge i32 %a, 4
+  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 < C implies A < C' is true if C <= C'.
+; CHECK-LABEL: @test_ult5_ult6
+; CHECK-NOT: %cmp1 = icmp ult i32 %a, 6
+; CHECK: ret void
+define void @test_ult5_ult6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ult i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ult i32 %a, 6
+  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 <= C implies A <= C' is true if C <= C'.
+; CHECK-LABEL: @test_ule5_ule6
+; CHECK-NOT: %cmp1 = icmp ule i32 %a, 6
+; CHECK: ret void
+define void @test_ule5_ule6(i32 %a, i32 %b) {
+entry:
+  %cmp = icmp ule i32 %a, 5
+  br i1 %cmp, label %if.then, label %if.end3
+
+if.then:
+  %cmp1 = icmp ule i32 %a, 6
+  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()