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
@@ -6597,11 +6597,37 @@
 
 const Instruction *
 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops) {
-  const Instruction *Bound = nullptr;
+  // Do a bounded search of the def relation of the requested SCEVs.
+  SmallSet<const SCEV *, 16> Visited;
+  SmallVector<const SCEV *> Worklist;
+  auto pushOp = [&](const SCEV *S) {
+    if (!Visited.insert(S).second)
+      return;
+    // Threshold of 30 here is arbitrary.
+    if (Visited.size() > 30)
+      return;
+    Worklist.push_back(S);
+  };
+
   for (auto *S : Ops)
-    if (auto *DefI = getNonTrivialDefiningScopeBound(S))
+    pushOp(S);
+
+  const Instruction *Bound = nullptr;
+  while (!Worklist.empty()) {
+    auto *S = Worklist.pop_back_val();
+    if (auto *DefI = getNonTrivialDefiningScopeBound(S)) {
       if (!Bound || DT.dominates(Bound, DefI))
         Bound = DefI;
+    } else if (auto *S2 = dyn_cast<SCEVCastExpr>(S))
+      for (auto *Op : S2->operands())
+        pushOp(Op);
+    else if (auto *S2 = dyn_cast<SCEVNAryExpr>(S))
+      for (auto *Op : S2->operands())
+        pushOp(Op);
+    else if (auto *S2 = dyn_cast<SCEVUDivExpr>(S))
+      for (auto *Op : S2->operands())
+        pushOp(Op);
+  }
   return Bound ? Bound : &*F.getEntryBlock().begin();
 }
 
diff --git a/llvm/test/Analysis/LoopAccessAnalysis/memcheck-wrapping-pointers.ll b/llvm/test/Analysis/LoopAccessAnalysis/memcheck-wrapping-pointers.ll
--- a/llvm/test/Analysis/LoopAccessAnalysis/memcheck-wrapping-pointers.ll
+++ b/llvm/test/Analysis/LoopAccessAnalysis/memcheck-wrapping-pointers.ll
@@ -45,10 +45,10 @@
 ; CHECK-NEXT:    {0,+,1}<%for.body> Added Flags: <nusw>
 ; CHECK:         Expressions re-written:
 ; CHECK-NEXT:    [PSE]  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %idxprom:
-; CHECK-NEXT:      ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)
+; CHECK-NEXT:      ((4 * (zext i32 {1,+,1}<%for.body> to i64))<nuw><nsw> + %a)<nuw>
 ; CHECK-NEXT:      --> {(4 + %a),+,4}<%for.body>
 ; CHECK-NEXT:    [PSE]  %arrayidx4 = getelementptr inbounds i32, i32* %b, i64 %conv11:
-; CHECK-NEXT:      ((4 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %b)
+; CHECK-NEXT:      ((4 * (zext i32 {0,+,1}<%for.body> to i64))<nuw><nsw> + %b)<nuw>
 ; CHECK-NEXT:      --> {%b,+,4}<%for.body>
 define void @test1(i64 %x, i32* %a, i32* %b) {
 entry:
diff --git a/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll b/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll
--- a/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll
+++ b/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll
@@ -1678,7 +1678,7 @@
 ; CHECK-NEXT:    %x = zext i32 %a to i64
 ; CHECK-NEXT:    --> (zext i32 %a to i64) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:    %res = add nuw i64 %x, %arg
-; CHECK-NEXT:    --> ((zext i32 %a to i64) + %arg) U: full-set S: full-set
+; CHECK-NEXT:    --> ((zext i32 %a to i64) + %arg)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @add-zext-recurse
 ;
   call void @foo()
@@ -1696,7 +1696,7 @@
 ; CHECK-NEXT:    %x = sext i32 %a to i64
 ; CHECK-NEXT:    --> (sext i32 %a to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:    %res = add nuw i64 %x, %arg
-; CHECK-NEXT:    --> ((sext i32 %a to i64) + %arg) U: full-set S: full-set
+; CHECK-NEXT:    --> ((sext i32 %a to i64) + %arg)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @add-sext-recurse
 ;
   call void @foo()
@@ -1714,7 +1714,7 @@
 ; CHECK-NEXT:    %x = trunc i32 %a to i16
 ; CHECK-NEXT:    --> (trunc i32 %a to i16) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i16 %x, 1
-; CHECK-NEXT:    --> (1 + (trunc i32 %a to i16)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (trunc i32 %a to i16))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-trunc-recurse
 ;
   call void @foo()
@@ -1732,7 +1732,7 @@
 ; CHECK-NEXT:    %x = udiv i32 %a, %arg
 ; CHECK-NEXT:    --> (%a /u %arg) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%a /u %arg)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%a /u %arg))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-udiv-recurse
 ;
   call void @foo()
@@ -1750,7 +1750,7 @@
 ; CHECK-NEXT:    %x = mul i32 %a, 3
 ; CHECK-NEXT:    --> (3 * %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (3 * %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (3 * %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-mul-recurse
 ;
   call void @foo()
@@ -1773,7 +1773,7 @@
 ; CHECK-NEXT:    %x = call i32 @llvm.smin.i32(i32 %a, i32 %arg)
 ; CHECK-NEXT:    --> (%arg smin %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%arg smin %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%arg smin %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-smin-recurse
 ;
   call void @foo()
@@ -1791,7 +1791,7 @@
 ; CHECK-NEXT:    %x = call i32 @llvm.smax.i32(i32 %a, i32 %arg)
 ; CHECK-NEXT:    --> (%arg smax %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%arg smax %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%arg smax %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-smax-recurse
 ;
   call void @foo()
@@ -1809,7 +1809,7 @@
 ; CHECK-NEXT:    %x = call i32 @llvm.umin.i32(i32 %a, i32 %arg)
 ; CHECK-NEXT:    --> (%arg umin %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%arg umin %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%arg umin %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-umin-recurse
 ;
   call void @foo()
@@ -1827,7 +1827,7 @@
 ; CHECK-NEXT:    %x = call i32 @llvm.umax.i32(i32 %a, i32 %arg)
 ; CHECK-NEXT:    --> (%arg umax %a) U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
-; CHECK-NEXT:    --> (1 + (%arg umax %a)) U: full-set S: full-set
+; CHECK-NEXT:    --> (1 + (%arg umax %a))<nuw> U: [1,0) S: [1,0)
 ; CHECK-NEXT:  Determining loop execution counts for: @add-umax-recurse
 ;
   call void @foo()
@@ -1854,7 +1854,7 @@
 ; CHECK-NEXT:    %y = add nuw i32 %c, %d
 ; CHECK-NEXT:    --> (%c + %d)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:    %res = add nuw i32 %x, %y
-; CHECK-NEXT:    --> (%a + %b + %c + %d) U: full-set S: full-set
+; CHECK-NEXT:    --> (%a + %b + %c + %d)<nuw> U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @add-recurse-inline
 ;
   call void @foo()