Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp
+++ lib/Analysis/ScalarEvolution.cpp
@@ -5741,8 +5741,14 @@
   // computed by this udiv could be smaller than the number of well-defined
   // iterations.
   if (!IsSubExpr && AddRec->getNoWrapFlags(SCEV::FlagNW)) {
+    // if start and step, both constant and start % step != 0, loop will never
+    // terminate by this condition.
+    if (isa<SCEVConstant>(Start) &&
+        GetMinTrailingZeros(Start) < GetMinTrailingZeros(Step))
+      return getCouldNotCompute();
+
     const SCEV *Exact =
-      getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
+        getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
     return ExitLimit(Exact, Exact, /*MustExit=*/false);
   }
 
Index: test/Transforms/IndVarSimplify/pr18886.ll
===================================================================
--- /dev/null
+++ test/Transforms/IndVarSimplify/pr18886.ll
@@ -0,0 +1,27 @@
+; RUN: opt -indvars -S < %s | FileCheck %s
+
+; CHECK-LABEL: @main(
+; CHECK-NOT: br i1 false, label %return, label %for.cond
+; CHECK-NOT: br i1 true, label %for.body, label %return
+
+@a = global i64 0, align 8
+define i32 @main() {
+entry:
+  store i64 -21, i64* @a, align 8
+  br label %for.body
+
+for.body:
+  %storemerge1 = phi i64 [ -21, %entry ], [ %add, %for.cond ]
+  %tobool = icmp eq i64 %storemerge1, 0
+  %add = add nsw i64 %storemerge1, 8
+  br i1 %tobool, label %return, label %for.cond
+
+for.cond:
+  store i64 %add, i64* @a, align 8
+  %cmp = icmp slt i64 %add, 9
+  br i1 %cmp, label %for.body, label %return
+
+return:
+  %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ]
+  ret i32 %retval.0
+}
Index: test/Transforms/IndVarSimplify/pr19799.ll
===================================================================
--- /dev/null
+++ test/Transforms/IndVarSimplify/pr19799.ll
@@ -0,0 +1,27 @@
+; RUN: opt -indvars -S < %s | FileCheck %s
+
+; CHECK-LABEL: @bar(
+; CHECK-NOT: br i1 true, label %for.body, label %return
+; CHECK-NOT: br i1 false, label %return, label %for.cond
+
+@a = global i32 0, align 8
+define i32 @bar() {
+entry:
+  store i32 -1, i32* @a, align 4
+  br label %for.body
+
+for.cond:
+  store i32 %add.i, i32* @a, align 4
+  %cmp = icmp slt i32 %storemerge1, 0
+  br i1 %cmp, label %for.body, label %return
+
+for.body:
+  %storemerge1 = phi i32 [ -1, %entry ], [ %add.i, %for.cond ]
+  %tobool = icmp eq i32 %storemerge1, 0
+  %add.i = add nsw i32 %storemerge1, 2
+  br i1 %tobool, label %return, label %for.cond
+
+return:
+  %retval.0 = phi i32 [ 0, %for.body ], [ 1, %for.cond ]
+  ret i32 %retval.0
+}