Index: lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
===================================================================
--- lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -18,6 +18,7 @@
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
@@ -381,6 +382,46 @@
   return true;
 }
 
+static bool processAdd(BinaryOperator *AI, LazyValueInfo *LVI) {
+  typedef OverflowingBinaryOperator OBO;
+
+  if (AI->getType()->isVectorTy() || hasLocalDefs(AI))
+    return false;
+
+  bool NSW = AI->hasNoSignedWrap();
+  bool NUW = AI->hasNoUnsignedWrap();
+  if (NSW && NUW)
+    return false;
+
+  BasicBlock *BB = AI->getParent();
+
+  Value *LHS = AI->getOperand(0);
+  Value *RHS = AI->getOperand(1);
+
+  ConstantRange LRange = LVI->getConstantRange(LHS, BB, AI);
+  ConstantRange RRange = LVI->getConstantRange(RHS, BB, AI);
+
+  bool Changed = false;
+  if (!NUW) {
+    ConstantRange NUWRange =
+            LRange.makeGuaranteedNoWrapRegion(BinaryOperator::Add, LRange,
+                                              OBO::NoUnsignedWrap);
+    bool NewNUW = NUWRange.contains(RRange);
+    AI->setHasNoUnsignedWrap(NewNUW);
+    Changed |= NewNUW;
+  }
+  if (!NSW) {
+    ConstantRange NSWRange =
+            LRange.makeGuaranteedNoWrapRegion(BinaryOperator::Add, LRange,
+                                              OBO::NoSignedWrap);
+    bool NewNSW = NSWRange.contains(RRange);
+    AI->setHasNoSignedWrap(NewNSW);
+    Changed |= NewNSW;
+  }
+
+  return Changed;
+}
+
 static Constant *getConstantAt(Value *V, Instruction *At, LazyValueInfo *LVI) {
   if (Constant *C = LVI->getConstant(V, At->getParent(), At))
     return C;
@@ -436,6 +477,9 @@
       case Instruction::SDiv:
         BBChanged |= processSDiv(cast<BinaryOperator>(II), LVI);
         break;
+      case Instruction::Add:
+        BBChanged |= processAdd(cast<BinaryOperator>(II), LVI);
+        break;
       }
     }
 
Index: test/Transforms/CorrelatedValuePropagation/add.ll
===================================================================
--- /dev/null
+++ test/Transforms/CorrelatedValuePropagation/add.ll
@@ -0,0 +1,61 @@
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; CHECK-LABEL: @test0(
+define void @test0(i32 %a) {
+entry:
+  %cmp = icmp slt i32 %a, 100
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %div1 = add nsw i32 %a, 1
+  %div = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test1(
+define void @test1(i32 %a) {
+entry:
+  %cmp = icmp ult i32 %a, 100
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %div1 = add nsw nuw i32 %a, 1
+  %div = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test2(
+define void @test2(i32 %a) {
+entry:
+  %cmp = icmp ult i32 %a, -1
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %div1 = add nuw i32 %a, 1
+  %div = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test3(
+define void @test3(i32 %a) {
+entry:
+  %cmp = icmp ule i32 %a, -1
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %div1 = add i32 %a, 1
+  %div = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}