Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp
+++ lib/Analysis/ScalarEvolution.cpp
@@ -1325,6 +1325,49 @@
                         (SE->*GetExtendExpr)(PreStart, Ty));
 }
 
+// Try to prove away overflow for `AR`, an affine add recurrence, by looking at
+// recurrences a constant offset away from it.  Return true if such a proof
+// exists.
+//
+// A motivating example for this rule: if we know `{0,+,4}` is `ult` `-1` and it
+// does not itself wrap then we can conclude that `{1,+,4}` is `nuw`.
+//
+template <typename ExtendOpTy>
+static bool ProveNoWrapByVaryingStart(ScalarEvolution &SE,
+                                      const SCEVAddRecExpr *AR,
+                                      const SCEV *Start, const SCEV *Step) {
+
+  assert(AR->isAffine() && "precondition!");
+
+  auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
+
+  // We restrict `Start` to a constant to prevent SCEV from spending too much
+  // time here.  It is correct (but more expensive) to continue with a
+  // non-constant `Start` and do a general SCEV subtraction to compute
+  // `PreStart` below.
+  const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start);
+  if (!StartC)
+    return false;
+
+  APInt StartAI = StartC->getValue()->getValue();
+  for (unsigned Delta : {-2, -1, 1, 2}) {
+    const SCEV *PreStart = SE.getConstant(StartAI - Delta);
+    const SCEV *DeltaS = SE.getConstant(StartC->getType(), Delta);
+    const SCEVAddRecExpr *PreAR = dyn_cast<SCEVAddRecExpr>(
+        SE.getAddRecExpr(PreStart, Step, AR->getLoop(), SCEV::FlagAnyWrap));
+
+    if (PreAR && PreAR->getNoWrapFlags(WrapType)) {
+      ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
+      const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
+          DeltaS, &Pred, &SE);
+      if (Limit && SE.isKnownPredicate(Pred, PreAR, Limit))
+        return true;
+    }
+  }
+
+  return false;
+}
+
 const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op,
                                                Type *Ty) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
@@ -1473,6 +1516,14 @@
           }
         }
       }
+
+      if (ProveNoWrapByVaryingStart<SCEVZeroExtendExpr>(*this, AR, Start,
+                                                        Step)) {
+        const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW);
+        return getAddRecExpr(
+            getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this),
+            getZeroExtendExpr(Step, Ty), L, AR->getNoWrapFlags());
+      }
     }
 
   // The cast wasn't folded; create an explicit cast node.
@@ -1664,6 +1715,14 @@
           return getAddExpr(Start, getSignExtendExpr(NewAR, Ty));
         }
       }
+
+      if (ProveNoWrapByVaryingStart<SCEVSignExtendExpr>(*this, AR, Start,
+                                                        Step)) {
+        const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
+        return getAddRecExpr(
+            getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty, this),
+            getSignExtendExpr(Step, Ty), L, AR->getNoWrapFlags());
+      }
     }
 
   // The cast wasn't folded; create an explicit cast node.
Index: test/Analysis/ScalarEvolution/nowrap-preinc-limits.ll
===================================================================
--- /dev/null
+++ test/Analysis/ScalarEvolution/nowrap-preinc-limits.ll
@@ -0,0 +1,44 @@
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+define void @f(i1* %condition) {
+; CHECK-LABEL: Classifying expressions for: @f
+ entry: 
+  br label %loop
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %loop ]
+  %idx.inc = add nsw i32 %idx, 1
+
+  %idx.inc2 = add i32 %idx.inc, 1
+  %idx.inc2.zext = zext i32 %idx.inc2 to i64
+
+; CHECK: %idx.inc2.zext = zext i32 %idx.inc2 to i64
+; CHECK-NEXT: -->  {2,+,1}<nuw><%loop>
+
+  %c = load volatile i1, i1* %condition
+  br i1 %c, label %loop, label %exit
+
+ exit:
+  ret void
+}
+
+define void @g(i1* %condition) {
+; CHECK-LABEL: Classifying expressions for: @g
+ entry:
+  br label %loop
+
+ loop:
+  %idx = phi i32 [ 0, %entry ], [ %idx.inc, %loop ]
+  %idx.inc = add nsw i32 %idx, 3
+
+  %idx.inc2 = add i32 %idx.inc, -1
+  %idx.inc2.sext = sext i32 %idx.inc2 to i64
+; CHECK: %idx.inc2.sext = sext i32 %idx.inc2 to i64
+; CHECK-NEXT: -->  {2,+,3}<nuw><nsw><%loop>
+
+  %c = load volatile i1, i1* %condition
+  br i1 %c, label %loop, label %exit
+
+ exit:
+  ret void
+}