Index: llvm/trunk/lib/Analysis/ValueTracking.cpp
===================================================================
--- llvm/trunk/lib/Analysis/ValueTracking.cpp
+++ llvm/trunk/lib/Analysis/ValueTracking.cpp
@@ -3543,26 +3543,44 @@
   // Set of instructions that we have proved will yield poison if PoisonI
   // does.
   SmallSet<const Value *, 16> YieldsPoison;
+  SmallSet<const BasicBlock *, 4> Visited;
   YieldsPoison.insert(PoisonI);
+  Visited.insert(PoisonI->getParent());
 
-  for (BasicBlock::const_iterator I = PoisonI->getIterator(), E = BB->end();
-       I != E; ++I) {
-    if (&*I != PoisonI) {
-      const Value *NotPoison = getGuaranteedNonFullPoisonOp(&*I);
-      if (NotPoison != nullptr && YieldsPoison.count(NotPoison)) return true;
-      if (!isGuaranteedToTransferExecutionToSuccessor(&*I))
-        return false;
+  BasicBlock::const_iterator Begin = PoisonI->getIterator(), End = BB->end();
+
+  unsigned Iter = 0;
+  while (Iter++ < MaxDepth) {
+    for (auto &I : make_range(Begin, End)) {
+      if (&I != PoisonI) {
+        const Value *NotPoison = getGuaranteedNonFullPoisonOp(&I);
+        if (NotPoison != nullptr && YieldsPoison.count(NotPoison))
+          return true;
+        if (!isGuaranteedToTransferExecutionToSuccessor(&I))
+          return false;
+      }
+
+      // Mark poison that propagates from I through uses of I.
+      if (YieldsPoison.count(&I)) {
+        for (const User *User : I.users()) {
+          const Instruction *UserI = cast<Instruction>(User);
+          if (propagatesFullPoison(UserI))
+            YieldsPoison.insert(User);
+        }
+      }
     }
 
-    // Mark poison that propagates from I through uses of I.
-    if (YieldsPoison.count(&*I)) {
-      for (const User *User : I->users()) {
-        const Instruction *UserI = cast<Instruction>(User);
-        if (UserI->getParent() == BB && propagatesFullPoison(UserI))
-          YieldsPoison.insert(User);
+    if (auto *NextBB = BB->getSingleSuccessor()) {
+      if (Visited.insert(NextBB).second) {
+        BB = NextBB;
+        Begin = BB->getFirstNonPHI()->getIterator();
+        End = BB->end();
+        continue;
       }
     }
-  }
+
+    break;
+  };
   return false;
 }
 
Index: llvm/trunk/test/Analysis/ScalarEvolution/flags-from-poison.ll
===================================================================
--- llvm/trunk/test/Analysis/ScalarEvolution/flags-from-poison.ll
+++ llvm/trunk/test/Analysis/ScalarEvolution/flags-from-poison.ll
@@ -113,11 +113,65 @@
   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 
 ; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nsw>
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  br label %loop2
+loop2:
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Similar to test-add-not-header, but in this case the load
+; instruction may not be executed.
+define void @test-add-not-header3(float* %input, i32 %offset, i32 %numIterations,
+                                 i1* %cond_buf) {
+; CHECK-LABEL: @test-add-not-header3
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
+
+; CHECK: %index32 =
 ; CHECK: --> {%offset,+,1}<nw>
   %index32 = add nsw i32 %i, %offset
 
   %ptr = getelementptr inbounds float, float* %input, i32 %index32
   %nexti = add nsw i32 %i, 1
+  %cond = load volatile i1, i1* %cond_buf
+  br i1 %cond, label %loop2, label %exit
+loop2:
+  %f = load float, float* %ptr, align 4
+  %exitcond = icmp eq i32 %nexti, %numIterations
+  br i1 %exitcond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; Same thing as test-add-not-header2, except we have a few extra
+; blocks.
+define void @test-add-not-header4(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-add-not-header4
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nsw>
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  br label %loop3
+loop3:
+  br label %loop4
+loop4:
   br label %loop2
 loop2:
   %f = load float, float* %ptr, align 4
@@ -127,6 +181,26 @@
   ret void
 }
 
+; Demonstrate why we need a Visited set in llvm::isKnownNotFullPoison.
+define void @test-add-not-header5(float* %input, i32 %offset) {
+; CHECK-LABEL: @test-add-not-header5
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
+
+; CHECK: %index32 =
+; CHECK: --> {%offset,+,1}<nw>
+  %index32 = add nsw i32 %i, %offset
+
+  %ptr = getelementptr inbounds float, float* %input, i32 %index32
+  %nexti = add nsw i32 %i, 1
+  br label %loop
+
+exit:
+  ret void
+}
+
 ; The call instruction makes it not guaranteed that the add will be
 ; executed, since it could run forever or throw an exception, so we
 ; cannot assume that the UB is realized.