diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -5479,12 +5479,12 @@
         if (!isKnownNonPositive(AddRec->getOperand(i)))
           AllNonPos = false;
       }
-      if (AllNonNeg)
+      if (AllNonNeg) {
         ConservativeResult = ConservativeResult.intersectWith(
             ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()),
                                        APInt::getSignedMinValue(BitWidth)),
             RangeType);
-      else if (AllNonPos)
+      } else if (AllNonPos)
         ConservativeResult = ConservativeResult.intersectWith(
             ConstantRange::getNonEmpty(
                 APInt::getSignedMinValue(BitWidth),
@@ -7384,12 +7384,33 @@
         if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
       }
 
+  auto ClampMaxBTCByIV = [this](const SCEV *IV, ExitLimit EL) {
+    auto AR = dyn_cast<SCEVAddRecExpr>(IV);
+    if (!AR)
+      return EL;
+
+    auto StepC = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this));
+    if (!StepC || StepC->getAPInt().isNonPositive())
+      return EL;
+
+    auto R = getUnsignedRange(AR);
+    if (R.isWrappedSet() || R.isFullSet())
+      return EL;
+    auto *IVBound = getUMinExpr(
+        getConstant((R.getUpper() - R.getLower()).udiv(StepC->getAPInt())),
+        EL.MaxNotTaken);
+    assert(isa<SCEVConstant>(IVBound) &&
+           "should have managed to simplify to a constant");
+    EL.MaxNotTaken = IVBound;
+    return EL;
+  };
   switch (Pred) {
   case ICmpInst::ICMP_NE: {                     // while (X != Y)
     // Convert to: while (X-Y != 0)
     ExitLimit EL = howFarToZero(getMinusSCEV(LHS, RHS), L, ControlsExit,
                                 AllowPredicates);
-    if (EL.hasAnyInfo()) return EL;
+    if (EL.hasAnyInfo())
+      return ClampMaxBTCByIV(LHS, EL);
     break;
   }
   case ICmpInst::ICMP_EQ: {                     // while (X == Y)
@@ -7403,7 +7424,8 @@
     bool IsSigned = Pred == ICmpInst::ICMP_SLT;
     ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit,
                                     AllowPredicates);
-    if (EL.hasAnyInfo()) return EL;
+    if (EL.hasAnyInfo())
+      return ClampMaxBTCByIV(LHS, EL);
     break;
   }
   case ICmpInst::ICMP_SGT:
@@ -7412,7 +7434,8 @@
     ExitLimit EL =
         howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit,
                             AllowPredicates);
-    if (EL.hasAnyInfo()) return EL;
+    if (EL.hasAnyInfo())
+      return ClampMaxBTCByIV(LHS, EL);
     break;
   }
   default:
diff --git a/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll b/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll
--- a/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll
+++ b/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll
@@ -204,10 +204,10 @@
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,8}<nsw><%loop> U: full-set S: full-set Exits: ((8 * (%N /u 2)) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 2
-; CHECK-NEXT:    --> {2,+,2}<nuw><%loop> U: [2,-1) S: [-9223372036854775808,9223372036854775807) Exits: (2 + (2 * (%N /u 2))<nuw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {2,+,2}<nuw><%loop> U: [2,-9223372036854775805) S: [-9223372036854775808,9223372036854775807) Exits: (2 + (2 * (%N /u 2))<nuw>) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_guard_ule_12_step2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (%N /u 2)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 9223372036854775807
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 4611686018427387904
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%N /u 2)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
@@ -309,10 +309,10 @@
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,4}<nsw><%loop> U: full-set S: full-set Exits: ((4 * %i) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,-9223372036854775806) S: [1,-9223372036854775806) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_multiple_var_guards_order1
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is %i
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -9223372036854775808
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %i
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
@@ -346,10 +346,10 @@
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,4}<nsw><%loop> U: full-set S: full-set Exits: ((4 * %i) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,-9223372036854775806) S: [1,-9223372036854775806) Exits: (1 + %i) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_multiple_var_guards_order2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is %i
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -9223372036854775808
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %i
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
@@ -383,10 +383,10 @@
 ; CHECK-NEXT:    %idx = getelementptr inbounds i32, i32* %a, i64 %iv
 ; CHECK-NEXT:    --> {%a,+,4}<nsw><%loop> U: full-set S: full-set Exits: ((4 * %N) + %a) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
-; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %N) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,-9223372036854775806) S: [1,-9223372036854775806) Exits: (1 + %N) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_multiple_var_guards_cycle
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is %N
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -9223372036854775808
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %N
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
diff --git a/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-limit-by-wrapping.ll b/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-limit-by-wrapping.ll
--- a/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-limit-by-wrapping.ll
+++ b/llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-limit-by-wrapping.ll
@@ -7,7 +7,7 @@
 define void @max_backedge_taken_count_by_wrapping1_nsw_nuw(i8 %N, i8* %ptr) {
 ; CHECK-LABEL: Determining loop execution counts for: @max_backedge_taken_count_by_wrapping1_nsw_nuw
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (%N /u 4)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 63
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 32
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (%N /u 4)
 ;
 entry:
@@ -49,7 +49,7 @@
 define void @max_backedge_taken_count_by_wrapping2_nsw_nuw(i8 %N, i8* %ptr) {
 ; CHECK-LABEL: Determining loop execution counts for: @max_backedge_taken_count_by_wrapping2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-64 + %N) /u 4)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 63
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 16
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-64 + %N) /u 4)
 ;
 entry:
@@ -70,7 +70,7 @@
 define void @max_backedge_taken_count_by_wrapping2_nuw(i8 %N, i8* %ptr) {
 ; CHECK-LABEL: Determining loop execution counts for: @max_backedge_taken_count_by_wrapping2
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-64  + %N) /u 4)
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is 63
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 47
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-64 + %N) /u 4)
 ;
 entry:
diff --git a/llvm/test/Analysis/ScalarEvolution/trip-count.ll b/llvm/test/Analysis/ScalarEvolution/trip-count.ll
--- a/llvm/test/Analysis/ScalarEvolution/trip-count.ll
+++ b/llvm/test/Analysis/ScalarEvolution/trip-count.ll
@@ -100,23 +100,23 @@
 
 declare void @may_exit() nounwind
 
-define void @pr28012(i32 %n) {
+define void @pr28012(i8 %n) {
 ; CHECK-LABEL: 'pr28012'
 ; CHECK-NEXT:  Determining loop execution counts for: @pr28012
-; CHECK-NEXT:  Loop %loop: backedge-taken count is -1431655751
-; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1431655751
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is -1431655751
+; CHECK-NEXT:  Loop %loop: backedge-taken count is -71
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 84
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is -71
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %loop: Trip multiple is 2863311546
+; CHECK:       Loop %loop: Trip multiple is 186
 ;
 entry:
   br label %loop
 
 loop:
-  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
-  %iv.inc = add nsw i32 %iv, 3
+  %iv = phi i8 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i8 %iv, 3
   call void @may_exit()
-  %becond = icmp ne i32 %iv.inc, 46
+  %becond = icmp ne i8 %iv.inc, 46
   br i1 %becond, label %loop, label %leave
 
 leave: