diff --git a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
--- a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -102,8 +102,10 @@
 // implement a strong expression equivalence checker in SCEV. Until then, we
 // use the verify-indvars flag, which may assert in some cases.
 static cl::opt<bool> VerifyIndvars(
-  "verify-indvars", cl::Hidden,
-  cl::desc("Verify the ScalarEvolution result after running indvars"));
+    "verify-indvars", cl::Hidden,
+    cl::desc("Verify the ScalarEvolution result after running indvars. Has no "
+             "effect in release builds. (Note: this adds additional SCEV "
+             "queries potentially changing the analysis result)"));
 
 static cl::opt<ReplaceExitVal> ReplaceExitValue(
     "replexitval", cl::Hidden, cl::init(OnlyCheapRepl),
@@ -2663,7 +2665,12 @@
 
 #ifndef NDEBUG
   // Used below for a consistency check only
-  const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
+  // Note: Since the result returned by ScalarEvolution may depend on the order
+  // in which previous results are added to its cache, the call to
+  // getBackedgeTakenCount() may change following SCEV queries.
+  const SCEV *BackedgeTakenCount;
+  if (VerifyIndvars)
+    BackedgeTakenCount = SE->getBackedgeTakenCount(L);
 #endif
 
   bool Changed = false;
diff --git a/llvm/test/Transforms/IndVarSimplify/deterministic-scev-verify.ll b/llvm/test/Transforms/IndVarSimplify/deterministic-scev-verify.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/IndVarSimplify/deterministic-scev-verify.ll
@@ -0,0 +1,38 @@
+; RUN: opt -indvars -stats -disable-output < %s 2>&1 | FileCheck %s --check-prefix=STATS
+; RUN: opt -indvars -S < %s | FileCheck %s --check-prefix=IR
+; REQUIRES: asserts
+
+; Check that IndVarSimplify's result is not influenced by stray calls to
+; ScalarEvolution in debug builds. However, -verify-indvars may still do
+; such calls.
+; llvm.org/PR44815
+
+; STATS: 1 scalar-evolution - Number of loops with trip counts computed by force
+; STATS: 2 scalar-evolution - Number of loops with predictable loop counts
+
+; In this test, adding -verify-indvars causes %tmp13 to not be optimized away.
+; IR-LABEL: @foo
+; IR-NOT:   phi i32
+
+target triple = "x86_64-unknown-linux-gnu"
+
+@b = external dso_local local_unnamed_addr global i32
+
+define dso_local void @foo() {
+tmp0:
+  br label %tmp12
+
+tmp7:
+  %tmp8 = add nuw nsw i32 %tmp13, 1
+  store i32 undef, i32* @b
+  br label %tmp12
+
+tmp12:
+  %tmp13 = phi i32 [ 2, %tmp0 ], [ %tmp8, %tmp7 ]
+  %tmp14 = phi i32 [ 1, %tmp0 ], [ %tmp13, %tmp7 ]
+  %tmp15 = icmp ult i32 %tmp14, undef
+  br i1 %tmp15, label %tmp7, label %tmp16
+
+tmp16:
+  ret void
+}