Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -11418,8 +11418,8 @@
   if (!IV || IV->getLoop() != L || !IV->isAffine())
     return getCouldNotCompute();
 
-  bool NoWrap = ControlsExit &&
-                IV->getNoWrapFlags(IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW);
+  auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW;
+  bool NoWrap = ControlsExit && IV->getNoWrapFlags(WrapType);
 
   const SCEV *Stride = IV->getStepRecurrence(*this);
 
@@ -11513,6 +11513,9 @@
     // undefined behaviors like the case of C language.
     if (canIVOverflowOnLT(RHS, Stride, IsSigned) && !isUBOnWrap())
       return getCouldNotCompute();
+
+    // We have proven that IV can not overflow, remember that fact.
+    setNoWrapFlags(const_cast<SCEVAddRecExpr *>(IV), WrapType);
   }
 
   ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT
Index: llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll
+++ llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll
@@ -79,7 +79,7 @@
 ; CHECK:       %sum2 = add i32 %sum1, %phi3
 ; CHECK-NEXT:  -->  {(6 + %a + %b),+,6}<%loop1>
 ; CHECK:       %is1 = add i32 %sum2, %a
-; CHECK-NEXT:  -->  {(6 + (2 * %a) + %b),+,6}<%loop1>
+; CHECK-NEXT:  -->  {(6 + (2 * %a) + %b),+,6}<nuw><%loop1>
 ; CHECK:       %sum3 = add i32 %phi4, %phi5
 ; CHECK-NEXT:  -->  {116,+,3}<%loop2>
 ; CHECK:       %sum4 = add i32 %sum3, %phi6
@@ -87,19 +87,19 @@
 ; CHECK:       %is2 = add i32 %sum4, %b
 ; CHECK-NEXT:  -->  {(159 + %b),+,6}<%loop2>
 ; CHECK:       %ec2 = add i32 %is1, %is2
-; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2>
+; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<nw><%loop1>,+,6}<%loop2>
 ; CHECK:       %s1 = add i32 %phi1, %is1
 ; CHECK-NEXT:  -->  {(6 + (3 * %a) + %b),+,7}<%loop1>
 ; CHECK:       %s2 = add i32 %is2, %phi4
 ; CHECK-NEXT:  -->  {(222 + %b),+,7}<%loop2>
 ; CHECK:       %s3 = add i32 %is1, %phi5
-; CHECK-NEXT:  -->  {{{{}}(59 + (2 * %a) + %b),+,6}<%loop1>,+,2}<%loop2>
+; CHECK-NEXT:  -->  {{{{}}(59 + (2 * %a) + %b),+,6}<nw><%loop1>,+,2}<%loop2>
 ; CHECK:       %s4 = add i32 %phi2, %is2
 ; CHECK-NEXT:  -->  {{{{}}(159 + (2 * %b)),+,2}<%loop1>,+,6}<%loop2>
 ; CHECK:       %s5 = add i32 %is1, %is2
-; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2>
+; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<nw><%loop1>,+,6}<%loop2>
 ; CHECK:       %s6 = add i32 %is2, %is1
-; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2>
+; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<nw><%loop1>,+,6}<%loop2>
 
 entry:
   br label %loop1