Index: llvm/lib/Analysis/LazyValueInfo.cpp
===================================================================
--- llvm/lib/Analysis/LazyValueInfo.cpp
+++ llvm/lib/Analysis/LazyValueInfo.cpp
@@ -1134,6 +1134,61 @@
   return ValueLatticeElement::getOverdefined();
 }
 
+// Handle conditions of the form
+// extractvalue(op.with.overflow(%x, C), 1).
+static ValueLatticeElement getValueFromOverflowCondition(
+    Value *Val, IntrinsicInst *II, bool isTrueDest) {
+  Instruction::BinaryOps BinOp;
+  unsigned WrapType;
+  switch (II->getIntrinsicID()) {
+    default:
+      return ValueLatticeElement::getOverdefined();
+    case Intrinsic::uadd_with_overflow:
+      BinOp = Instruction::Add;
+      WrapType = OverflowingBinaryOperator::NoUnsignedWrap;
+      break;
+    case Intrinsic::sadd_with_overflow:
+      BinOp = Instruction::Add;
+      WrapType = OverflowingBinaryOperator::NoSignedWrap;
+      break;
+    case Intrinsic::usub_with_overflow:
+      BinOp = Instruction::Sub;
+      WrapType = OverflowingBinaryOperator::NoUnsignedWrap;
+      break;
+    case Intrinsic::ssub_with_overflow:
+      BinOp = Instruction::Sub;
+      WrapType = OverflowingBinaryOperator::NoSignedWrap;
+      break;
+    case Intrinsic::umul_with_overflow:
+      BinOp = Instruction::Mul;
+      WrapType = OverflowingBinaryOperator::NoUnsignedWrap;
+      break;
+    case Intrinsic::smul_with_overflow:
+      BinOp = Instruction::Mul;
+      WrapType = OverflowingBinaryOperator::NoSignedWrap;
+      break;
+  }
+
+  // TODO This only works with a constant RHS for now. We could also compute
+  // the range of the RHS, but this doesn't fit into the current structure of
+  // the edge value calculation.
+  Value *LHS = II->getArgOperand(0);
+  Value *RHS = II->getArgOperand(1);
+  const APInt *C;
+  if (LHS != Val || !match(RHS, m_APInt(C)))
+    return ValueLatticeElement::getOverdefined();
+
+  // Calculate the possible values of %x for which no overflow occurs.
+  ConstantRange NWR = ConstantRange::makeGuaranteedNoWrapRegion(
+      BinOp, ConstantRange(*C), WrapType);
+
+  // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
+  // constrained to it's inverse (all values that might cause overflow).
+  if (isTrueDest)
+    NWR = NWR.inverse();
+  return ValueLatticeElement::getRange(NWR);
+}
+
 static ValueLatticeElement
 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
                       DenseMap<Value*, ValueLatticeElement> &Visited);
@@ -1144,6 +1199,11 @@
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
     return getValueFromICmpCondition(Val, ICI, isTrueDest);
 
+  if (ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Cond))
+    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(EVI->getAggregateOperand()))
+      if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
+        return getValueFromOverflowCondition(Val, II, isTrueDest);
+
   // Handle conditions in the form of (cond1 && cond2), we know that on the
   // true dest path both of the conditions hold. Similarly for conditions of
   // the form (cond1 || cond2), we know that on the false dest path neither
Index: llvm/test/Transforms/CorrelatedValuePropagation/overflow_predicate.ll
===================================================================
--- llvm/test/Transforms/CorrelatedValuePropagation/overflow_predicate.ll
+++ llvm/test/Transforms/CorrelatedValuePropagation/overflow_predicate.ll
@@ -19,8 +19,7 @@
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ugt i8 [[X]], -102
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ugt i8 [[X]], -101
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -52,8 +51,7 @@
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ugt i8 [[X]], -100
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ugt i8 [[X]], -101
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -85,8 +83,7 @@
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i8 [[X]], 26
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp sgt i8 [[X]], 27
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -118,8 +115,7 @@
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i8 [[X]], 28
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp sgt i8 [[X]], 27
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -151,8 +147,7 @@
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ult i8 [[X]], 101
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ult i8 [[X]], 100
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -184,8 +179,7 @@
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ult i8 [[X]], 99
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ult i8 [[X]], 100
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -217,8 +211,7 @@
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i8 [[X]], -27
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i8 [[X]], -28
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -250,8 +243,7 @@
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i8 [[X]], -29
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i8 [[X]], -28
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -283,8 +275,7 @@
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ugt i8 [[X]], 24
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ugt i8 [[X]], 25
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -316,8 +307,7 @@
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ugt i8 [[X]], 26
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ugt i8 [[X]], 25
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -350,8 +340,7 @@
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i8 [[X]], -11
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i8 [[X]], -12
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -383,8 +372,7 @@
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i8 [[X]], 11
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp sgt i8 [[X]], 12
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -417,8 +405,7 @@
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[X]], -13
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[X]], -12
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
@@ -450,8 +437,7 @@
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[X]], 13
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[X]], 12
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable