diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -5674,6 +5674,30 @@
   return false;
 }
 
+static bool isPoison(const Value *V, SmallSet<const Value *, 16> &KnownPoison,
+                     SmallSet<const Value *, 16> &KnownNonPoison) {
+  // Check if we already know whether V is poison.
+  if (KnownPoison.count(V))
+    return true;
+  if (KnownNonPoison.count(V))
+    return false;
+
+  // Not yet known whether V is poison, compute it lazily.
+  if (const Instruction *I = dyn_cast<const Instruction>(V)) {
+    if (propagatesPoison(cast<Operator>(I))) {
+      for (const Use &U : I->operands()) {
+        if (isPoison(U.get(), KnownPoison, KnownNonPoison)) {
+          KnownPoison.insert(V);
+          return true;
+        }
+      }
+    }
+  }
+
+  KnownNonPoison.insert(V);
+  return false;
+}
+
 static bool programUndefinedIfUndefOrPoison(const Value *V,
                                             bool PoisonOnly) {
   // We currently only look for uses of values within the same basic
@@ -5723,17 +5747,33 @@
     return false;
   }
 
-  // Set of instructions that we have proved will yield poison if Inst
-  // does.
-  SmallSet<const Value *, 16> YieldsPoison;
-  SmallSet<const BasicBlock *, 4> Visited;
+  // Instructions we have proven they will or will not yield poison if V does
+  SmallSet<const Value *, 16> KnownPoison;
+  SmallSet<const Value *, 16> KnownNonPoison;
 
-  YieldsPoison.insert(V);
-  auto Propagate = [&](const User *User) {
-    if (propagatesPoison(cast<Operator>(User)))
-      YieldsPoison.insert(User);
+  // Eagerly mark the first few uses of the poison Value as poison. This
+  // helps with the common case of having a handful of uses, but because we
+  // are only scanning instructions up to ScanLimit below, in cases where
+  // there are a lot of uses of this value (orders of magnitude more than
+  // ScanLimit), it can save a lot of time to compute the rest lazily in
+  // 'isPoison' instead.
+  auto PoisonAFewUsersEagerly = [&](const Value *Value) {
+    assert(KnownPoison.count(Value) && "Eagerly poisoning uses of non-poison");
+    unsigned EagerLimit = 3;
+    for (const User *U : Value->users()) {
+      if (propagatesPoison(cast<Operator>(U)))
+        KnownPoison.insert(U);
+      else
+        KnownNonPoison.insert(U);
+      if (--EagerLimit == 0)
+        return;
+    }
   };
-  for_each(V->users(), Propagate);
+
+  KnownPoison.insert(V);
+  PoisonAFewUsersEagerly(V);
+
+  SmallSet<const BasicBlock *, 4> Visited;
   Visited.insert(BB);
 
   while (true) {
@@ -5742,14 +5782,20 @@
         continue;
       if (--ScanLimit == 0)
         return false;
-      if (mustTriggerUB(&I, YieldsPoison))
-        return true;
+
+      // Like llvm::mustTriggerUB, but with lazy evaluation via 'isPoison'
+      SmallPtrSet<const Value *, 4> NonPoisonOps;
+      getGuaranteedNonPoisonOps(&I, NonPoisonOps);
+      for (const Value *O : NonPoisonOps)
+        if (isPoison(O, KnownPoison, KnownNonPoison))
+          return true;
+
       if (!isGuaranteedToTransferExecutionToSuccessor(&I))
         return false;
 
       // Mark poison that propagates from I through uses of I.
-      if (YieldsPoison.count(&I))
-        for_each(I.users(), Propagate);
+      if (isPoison(&I, KnownPoison, KnownNonPoison))
+        PoisonAFewUsersEagerly(&I);
     }
 
     BB = BB->getSingleSuccessor();