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
@@ -12443,11 +12443,11 @@
   if (IsSigned && BitWidth == 1)
     return getZero(Stride->getType());
 
-  // This code has only been closely audited for negative strides in the
+  // This code below only been closely audited for negative strides in the
   // unsigned comparison case, it may be correct for signed comparison, but
   // that needs to be established.
-  assert((!IsSigned || !isKnownNonPositive(Stride)) &&
-         "Stride is expected strictly positive for signed case!");
+  if (IsSigned && isKnownNegative(Stride))
+    return getCouldNotCompute();
 
   // Calculate the maximum backedge count based on the range of values
   // permitted by Start, End, and Stride.
@@ -12633,13 +12633,6 @@
         !loopHasNoAbnormalExits(L))
       return getCouldNotCompute();
 
-    // This bailout is protecting the logic in computeMaxBECountForLT which
-    // has not yet been sufficiently auditted or tested with negative strides.
-    // We used to filter out all known-non-positive cases here, we're in the
-    // process of being less restrictive bit by bit.
-    if (IsSigned && isKnownNonPositive(Stride))
-      return getCouldNotCompute();
-
     if (!isKnownNonZero(Stride)) {
       // If we have a step of zero, and RHS isn't invariant in L, we don't know
       // if it might eventually be greater than start and if so, on which
diff --git a/llvm/test/Analysis/ScalarEvolution/max-trip-count.ll b/llvm/test/Analysis/ScalarEvolution/max-trip-count.ll
--- a/llvm/test/Analysis/ScalarEvolution/max-trip-count.ll
+++ b/llvm/test/Analysis/ScalarEvolution/max-trip-count.ll
@@ -502,8 +502,8 @@
 ; Max backedge-taken count is zero.
 define void @bool_stride(i1 %s, i1 %n) mustprogress {
 ; CHECK-LABEL: Determining loop execution counts for: @bool_stride
-; CHECK: Loop %loop: Unpredictable backedge-taken count.
-; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+; CHECK: Loop %loop: backedge-taken count is false
+; CHECK: Loop %loop: max backedge-taken count is false
 entry:
   br label %loop
 
diff --git a/llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll b/llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll
--- a/llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll
+++ b/llvm/test/Analysis/ScalarEvolution/trip-count-negative-stride.ll
@@ -411,9 +411,11 @@
 define void @slt_129_unknown_start(i8 %start) mustprogress {
 ; CHECK-LABEL: 'slt_129_unknown_start'
 ; CHECK-NEXT:  Determining loop execution counts for: @slt_129_unknown_start
-; 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 (((127 + (-1 * (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))<nuw><nsw> + (-1 * %start) + (0 smax (-127 + %start)<nsw>)) /u -127) + (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 2
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (((127 + (-1 * (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))<nuw><nsw> + (-1 * %start) + (0 smax (-127 + %start)<nsw>)) /u -127) + (1 umin (127 + (-1 * %start) + (0 smax (-127 + %start)<nsw>))))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
@@ -571,4 +573,126 @@
 
 declare void @llvm.assume(i1)
 
+; Test case for PR57818.
+define void @step_is_neg_addrec_slt_8(i64 %n) {
+; CHECK-LABEL: 'step_is_neg_addrec_slt_8'
+; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_slt_8
+; CHECK-NEXT:  Loop %inner: backedge-taken count is (7 /u {0,+,-1}<nuw><nsw><%outer.header>)
+; CHECK-NEXT:  Loop %inner: max backedge-taken count is -2147483640
+; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is (7 /u {0,+,-1}<nuw><nsw><%outer.header>)
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %inner: Trip multiple is 1
+; CHECK-NEXT:  Loop %outer.header: backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: Predicated backedge-taken count is 0
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %outer.header: Trip multiple is 1
+;
+entry:
+  br label %outer.header
+
+outer.header:
+  %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
+  %ec.1 = icmp eq i64 %outer.iv, 100
+  br i1 %ec.1, label %inner.ph, label %exit
+
+inner.ph:
+  %outer.trunc = trunc i64 %outer.iv to i32
+  br label %inner
+
+inner:
+  %inner.iv = phi i32 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]
+  %inner.iv.next = add nsw i32 %inner.iv, %outer.trunc
+  %inner.c = icmp slt i32 %inner.iv.next, 8
+  br i1 %inner.c, label %inner, label %outer.latch, !llvm.loop !0
+
+outer.latch:
+  %outer.iv.next = add nsw i64 %outer.iv, -1
+  br label %outer.header
+
+exit:
+  ret void
+}
+
+define void @step_is_neg_addrec_slt_var(i32 %n) {
+; CHECK-LABEL: 'step_is_neg_addrec_slt_var'
+; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_slt_var
+; CHECK-NEXT:  Loop %inner: backedge-taken count is ((((-1 * (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))<nuw><nsw> + {0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n)) /u (1 umax {0,+,-1}<nuw><nsw><%outer.header>)) + (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))
+; CHECK-NEXT:  Loop %inner: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is ((((-1 * (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))<nuw><nsw> + {0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n)) /u (1 umax {0,+,-1}<nuw><nsw><%outer.header>)) + (1 umin ({0,+,1}<nuw><%outer.header> + ({0,+,-1}<nuw><nsw><%outer.header> smax %n))))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %inner: Trip multiple is 1
+; CHECK-NEXT:  Loop %outer.header: backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: Predicated backedge-taken count is 0
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %outer.header: Trip multiple is 1
+;
+entry:
+  br label %outer.header
+
+outer.header:
+  %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
+  %ec.1 = icmp eq i64 %outer.iv, 100
+  br i1 %ec.1, label %inner.ph, label %exit
+
+inner.ph:
+  %outer.trunc = trunc i64 %outer.iv to i32
+  br label %inner
+
+inner:
+  %inner.iv = phi i32 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]
+  %inner.iv.next = add nsw i32 %inner.iv, %outer.trunc
+  %inner.c = icmp slt i32 %inner.iv.next, %n
+  br i1 %inner.c, label %inner, label %outer.latch, !llvm.loop !0
+
+outer.latch:
+  %outer.iv.next = add nsw i64 %outer.iv, -1
+  br label %outer.header
+
+exit:
+  ret void
+}
+
+define void @step_is_neg_addrec_unknown_start(i32 %n) {
+; CHECK-LABEL: 'step_is_neg_addrec_unknown_start'
+; CHECK-NEXT:  Determining loop execution counts for: @step_is_neg_addrec_unknown_start
+; CHECK-NEXT:  Loop %inner: backedge-taken count is ((((-1 * (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))<nuw><nsw> + {(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>)) /u (1 umax {0,+,-1}<%outer.header>)) + (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))
+; CHECK-NEXT:  Loop %inner: max backedge-taken count is -2147483640
+; CHECK-NEXT:  Loop %inner: Predicated backedge-taken count is ((((-1 * (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))<nuw><nsw> + {(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>)) /u (1 umax {0,+,-1}<%outer.header>)) + (1 umin ({(-1 * %n),+,1}<nw><%outer.header> + (8 smax {%n,+,-1}<nuw><nsw><%outer.header>))))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %inner: Trip multiple is 1
+; CHECK-NEXT:  Loop %outer.header: backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %outer.header: Predicated backedge-taken count is 0
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %outer.header: Trip multiple is 1
+;
+entry:
+  br label %outer.header
+
+outer.header:
+  %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
+  %ec.1 = icmp eq i64 %outer.iv, 100
+  br i1 %ec.1, label %inner.ph, label %exit
+
+inner.ph:
+  %outer.trunc = trunc i64 %outer.iv to i32
+  br label %inner
+
+inner:
+  %inner.iv = phi i32 [ %n, %inner.ph ], [ %inner.iv.next, %inner ]
+  %inner.iv.next = add nsw i32 %inner.iv, %outer.trunc
+  %inner.c = icmp slt i32 %inner.iv.next, 8
+  br i1 %inner.c, label %inner, label %outer.latch, !llvm.loop !0
+
+outer.latch:
+  %outer.iv.next = add nsw i64 %outer.iv, -1
+  br label %outer.header
+
+exit:
+  ret void
+}
 
+!0 = distinct !{!0, !1}
+!1 = !{!"llvm.loop.mustprogress"}