Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -8316,6 +8316,32 @@
         if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
       }
 
+  // If this loop must exit based on this condition (or execute undefined
+  // behaviour), and we can prove the test sequence produced must repeat
+  // the same values on self-wrap of the IV, then we can infer that IV
+  // doesn't self wrap because if it did, we'd have an infinite (undefined)
+  // loop.
+  if (ControlsExit && isLoopInvariant(RHS, L) && loopHasNoAbnormalExits(L) &&
+      loopIsFiniteByAssumption(L)) {
+
+    // TODO: We can peel off any functions which are invertible *in L*.  Loop
+    // invariant terms are effectively constants for our purposes here.
+    auto *InnerLHS = LHS;
+    if (auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS))
+      InnerLHS = ZExt->getOperand();
+    if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(InnerLHS)) {
+      auto *StrideC = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this));
+      if (AR->getLoop() == L && AR->isAffine() && StrideC &&
+          StrideC->getAPInt().isPowerOf2()) {
+        auto Flags = AR->getNoWrapFlags();
+        Flags = setFlags(Flags, SCEV::FlagNW);
+        SmallVector<const SCEV*> Operands{AR->operands()};
+        Flags = StrengthenNoWrapFlags(this, scAddRecExpr, Operands, Flags);
+        setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), Flags);
+      }
+    }
+  }
+
   switch (Pred) {
   case ICmpInst::ICMP_NE: {                     // while (X != Y)
     // Convert to: while (X-Y != 0)
@@ -11821,14 +11847,6 @@
     if (auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS)) {
       const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(ZExt->getOperand());
       if (AR && AR->getLoop() == L && AR->isAffine()) {
-        auto Flags = AR->getNoWrapFlags();
-        if (!hasFlags(Flags, SCEV::FlagNW) && canAssumeNoSelfWrap(AR)) {
-          Flags = setFlags(Flags, SCEV::FlagNW);
-
-          SmallVector<const SCEV*> Operands{AR->operands()};
-          Flags = StrengthenNoWrapFlags(this, scAddRecExpr, Operands, Flags);
-        }
-
         auto canProveNUW = [&]() {
           if (!isLoopInvariant(RHS, L))
             return false;
@@ -11851,6 +11869,7 @@
           Limit = Limit.zext(OuterBitWidth);
           return getUnsignedRangeMax(applyLoopGuards(RHS, L)).ule(Limit);
         };
+        auto Flags = AR->getNoWrapFlags();
         if (!hasFlags(Flags, SCEV::FlagNUW) && canProveNUW())
           Flags = setFlags(Flags, SCEV::FlagNUW);
 
Index: llvm/test/Analysis/ScalarEvolution/ne-overflow.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/ne-overflow.ll
+++ llvm/test/Analysis/ScalarEvolution/ne-overflow.ll
@@ -1,5 +1,4 @@
 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
-
 ; RUN: opt %s -passes='print<scalar-evolution>' -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
@@ -11,9 +10,11 @@
 define void @test(i32 %N) mustprogress {
 ; CHECK-LABEL: 'test'
 ; CHECK-NEXT:  Determining loop execution counts for: @test
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is ((-2 + %N) /u 2)
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 2147483647
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((-2 + %N) /u 2)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
@@ -31,9 +32,11 @@
 define void @test_preinc(i32 %N) mustprogress {
 ; CHECK-LABEL: 'test_preinc'
 ; CHECK-NEXT:  Determining loop execution counts for: @test_preinc
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (%N /u 2)
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 2147483647
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (%N /u 2)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
@@ -118,9 +121,11 @@
 define void @test_1024(i32 %N) mustprogress {
 ; CHECK-LABEL: 'test_1024'
 ; CHECK-NEXT:  Determining loop execution counts for: @test_1024
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is ((-1024 + %N) /u 1024)
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 4194303
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((-1024 + %N) /u 1024)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
@@ -227,5 +232,3 @@
 for.cond.cleanup:
   ret void
 }
-
-
Index: llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll
+++ llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll
@@ -56,9 +56,11 @@
 define void @ult_infinite_ub() mustprogress {
 ; CHECK-LABEL: 'ult_infinite_ub'
 ; CHECK-NEXT:  Determining loop execution counts for: @ult_infinite_ub
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is 1
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 1
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 1
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 2
 ;
 entry:
   br label %for.body
@@ -340,9 +342,11 @@
 define void @slt_infinite_ub() mustprogress {
 ; CHECK-LABEL: 'slt_infinite_ub'
 ; CHECK-NEXT:  Determining loop execution counts for: @slt_infinite_ub
-; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is 0
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is 0
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body