diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
--- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -473,8 +473,10 @@
   }
 }
 
+static bool processBinOp(BinaryOperator *BinOp, LazyValueInfo *LVI);
+
 // Rewrite this with.overflow intrinsic as non-overflowing.
-static void processOverflowIntrinsic(WithOverflowInst *WO) {
+static void processOverflowIntrinsic(WithOverflowInst *WO, LazyValueInfo *LVI) {
   IRBuilder<> B(WO);
   Instruction::BinaryOps Opcode = WO->getBinaryOp();
   bool NSW = WO->isSigned();
@@ -492,9 +494,13 @@
   WO->replaceAllUsesWith(NewI);
   WO->eraseFromParent();
   ++NumOverflows;
+
+  // See if we can infer the other no-wrap too.
+  if (auto *BO = dyn_cast<BinaryOperator>(NewOp))
+    processBinOp(BO, LVI);
 }
 
-static void processSaturatingInst(SaturatingInst *SI) {
+static void processSaturatingInst(SaturatingInst *SI, LazyValueInfo *LVI) {
   Instruction::BinaryOps Opcode = SI->getBinaryOp();
   bool NSW = SI->isSigned();
   bool NUW = !SI->isSigned();
@@ -506,6 +512,10 @@
   SI->replaceAllUsesWith(BinOp);
   SI->eraseFromParent();
   ++NumSaturating;
+
+  // See if we can infer the other no-wrap too.
+  if (auto *BO = dyn_cast<BinaryOperator>(BinOp))
+    processBinOp(BO, LVI);
 }
 
 /// Infer nonnull attributes for the arguments at the specified callsite.
@@ -515,14 +525,14 @@
 
   if (auto *WO = dyn_cast<WithOverflowInst>(CS.getInstruction())) {
     if (WO->getLHS()->getType()->isIntegerTy() && willNotOverflow(WO, LVI)) {
-      processOverflowIntrinsic(WO);
+      processOverflowIntrinsic(WO, LVI);
       return true;
     }
   }
 
   if (auto *SI = dyn_cast<SaturatingInst>(CS.getInstruction())) {
     if (SI->getType()->isIntegerTy() && willNotOverflow(SI, LVI)) {
-      processSaturatingInst(SI);
+      processSaturatingInst(SI, LVI);
       return true;
     }
   }
diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll b/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll
--- a/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll
+++ b/llvm/test/Transforms/CorrelatedValuePropagation/overflows.ll
@@ -38,7 +38,7 @@
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[LAND_LHS_TRUE:%.*]], label [[LOR_LHS_FALSE:%.*]]
 ; CHECK:       land.lhs.true:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub nsw i32 2147483647, [[Y]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nuw nsw i32 2147483647, [[Y]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[TMP0]], 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = extractvalue { i32, i1 } [[TMP1]], 1
 ; CHECK-NEXT:    br i1 [[TMP2]], label [[TRAP:%.*]], label [[CONT:%.*]]
@@ -116,7 +116,7 @@
 define i32 @unsigned_add(i32 %x, i32 %y) {
 ; CHECK-LABEL: @unsigned_add(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub nuw i32 -1, [[Y:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nuw nsw i32 -1, [[Y:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[TMP0]], 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = extractvalue { i32, i1 } [[TMP1]], 1
 ; CHECK-NEXT:    br i1 [[TMP2]], label [[TRAP:%.*]], label [[CONT:%.*]]
@@ -182,7 +182,7 @@
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[Y]], 0
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[COND_FALSE]], label [[LAND_LHS_TRUE3:%.*]]
 ; CHECK:       land.lhs.true3:
-; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i32 [[Y]], -2147483648
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i32 [[Y]], -2147483648
 ; CHECK-NEXT:    [[TMP5:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[TMP4]], 0
 ; CHECK-NEXT:    [[TMP6:%.*]] = extractvalue { i32, i1 } [[TMP5]], 1
 ; CHECK-NEXT:    br i1 [[TMP6]], label [[TRAP]], label [[CONT4:%.*]]
@@ -506,7 +506,7 @@
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[X:%.*]], 10000
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       cond.false:
-; CHECK-NEXT:    [[MULO1:%.*]] = mul nuw i32 [[X]], 100
+; CHECK-NEXT:    [[MULO1:%.*]] = mul nuw nsw i32 [[X]], 100
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[MULO1]], 0
 ; CHECK-NEXT:    [[RES:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i32, i1 } [[TMP0]], 1
@@ -760,7 +760,7 @@
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES1:%.*]] = add nuw i8 [[X]], 100
+; CHECK-NEXT:    [[RES1:%.*]] = add nuw nsw i8 [[X]], 100
 ; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ugt i8 %x, 27
@@ -806,7 +806,7 @@
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES1:%.*]] = add nsw i8 [[X]], 20
+; CHECK-NEXT:    [[RES1:%.*]] = add nuw nsw i8 [[X]], 20
 ; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ugt i8 %x, 107
@@ -852,7 +852,7 @@
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES1:%.*]] = sub nuw i8 [[X]], 100
+; CHECK-NEXT:    [[RES1:%.*]] = sub nuw nsw i8 [[X]], 100
 ; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ult i8 %x, 228
@@ -898,7 +898,7 @@
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cont:
-; CHECK-NEXT:    [[RES1:%.*]] = sub nsw i8 [[X]], 20
+; CHECK-NEXT:    [[RES1:%.*]] = sub nuw nsw i8 [[X]], 20
 ; CHECK-NEXT:    ret i8 [[RES1]]
 ;
   %cmp = icmp ult i8 %x, 148
@@ -982,7 +982,7 @@
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 10
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
-; CHECK-NEXT:    [[RES1:%.*]] = add nuw i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[RES1:%.*]] = add nuw nsw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[ADD:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
@@ -1023,7 +1023,7 @@
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[OFFSET:%.*]] = add nuw nsw i32 [[X]], 9
-; CHECK-NEXT:    [[RES1:%.*]] = sub nsw i32 [[OFFSET]], [[Y]]
+; CHECK-NEXT:    [[RES1:%.*]] = sub nuw nsw i32 [[OFFSET]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
@@ -1066,7 +1066,7 @@
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
 ; CHECK-NEXT:    [[OFFSET:%.*]] = add nuw nsw i32 [[X]], 9
-; CHECK-NEXT:    [[RES1:%.*]] = sub nuw i32 [[OFFSET]], [[Y]]
+; CHECK-NEXT:    [[RES1:%.*]] = sub nuw nsw i32 [[OFFSET]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]
@@ -1155,7 +1155,7 @@
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[Y:%.*]], 100
 ; CHECK-NEXT:    br i1 [[CMP2]], label [[CONT2:%.*]], label [[OUT]]
 ; CHECK:       cont2:
-; CHECK-NEXT:    [[RES1:%.*]] = mul nuw i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[RES1:%.*]] = mul nuw nsw i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 [[RES1]], 0
 ; CHECK-NEXT:    [[MUL:%.*]] = extractvalue { i32, i1 } [[TMP0]], 0
 ; CHECK-NEXT:    br label [[CONT3:%.*]]