diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp
--- a/llvm/lib/Analysis/LazyValueInfo.cpp
+++ b/llvm/lib/Analysis/LazyValueInfo.cpp
@@ -152,7 +152,7 @@
   /// maintains information about queries across the clients' queries.
   class LazyValueInfoCache {
   public:
-    typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
+    typedef DenseMap<PoisoningVH<BasicBlock>, DenseSet<PoisoningVH<Value>>>
         PerBlockValueCacheTy;
 
   private:
@@ -181,6 +181,7 @@
     /// dereferenced in the block (and thus non-null at the end of the block).
     PerBlockValueCacheTy DereferencedPointerCache;
 
+    std::vector<LVIValueHandle> OverdefinedHandles;
 
   public:
     void insertResult(Value *Val, BasicBlock *BB,
@@ -189,9 +190,12 @@
 
       // Insert over-defined values into their own cache to reduce memory
       // overhead.
-      if (Result.isOverdefined())
+      if (Result.isOverdefined()) {
         OverDefinedCache[BB].insert(Val);
-      else {
+        auto I = llvm::find_if(OverdefinedHandles, [Val](auto &P) { return P == Val; });
+        if (I == OverdefinedHandles.end())
+          OverdefinedHandles.emplace_back(Val, this);
+      } else {
         auto It = ValueCache.find_as(Val);
         if (It == ValueCache.end()) {
           ValueCache[Val] = std::make_unique<ValueCacheEntryTy>(Val, this);
@@ -270,7 +274,7 @@
     // Copy and increment the iterator immediately so we can erase behind
     // ourselves.
     auto Iter = I++;
-    SmallPtrSetImpl<Value *> &ValueSet = Iter->second;
+    auto &ValueSet = Iter->second;
     ValueSet.erase(V);
     if (ValueSet.empty())
       Cache.erase(Iter);
@@ -281,6 +285,10 @@
   eraseValueFromPerBlockValueCache(V, OverDefinedCache);
   eraseValueFromPerBlockValueCache(V, DereferencedPointerCache);
   ValueCache.erase(V);
+  auto I = llvm::find_if(OverdefinedHandles, [V](auto &P) { return P == V; });
+  if (I != OverdefinedHandles.end())
+    OverdefinedHandles.erase(I);
+
 }
 
 void LVIValueHandle::deleted() {
@@ -341,7 +349,7 @@
     auto OI = OverDefinedCache.find(ToUpdate);
     if (OI == OverDefinedCache.end())
       continue;
-    SmallPtrSetImpl<Value *> &ValueSet = OI->second;
+    auto &ValueSet = OI->second;
 
     bool changed = false;
     for (Value *V : ValsToClear) {
@@ -685,7 +693,7 @@
 }
 
 static void AddDereferencedPointer(
-    Value *Ptr, SmallPtrSet<Value *, 4> &PtrSet, const DataLayout &DL) {
+    Value *Ptr, DenseSet<PoisoningVH<Value>> &PtrSet, const DataLayout &DL) {
   // TODO: Use NullPointerIsDefined instead.
   if (Ptr->getType()->getPointerAddressSpace() == 0) {
     Ptr = GetUnderlyingObject(Ptr, DL);
@@ -694,7 +702,7 @@
 }
 
 static void AddPointersDereferencedByInstruction(
-    Instruction *I, SmallPtrSet<Value *, 4> &PtrSet, const DataLayout &DL) {
+    Instruction *I, DenseSet<PoisoningVH<Value>> &PtrSet, const DataLayout &DL) {
   if (LoadInst *L = dyn_cast<LoadInst>(I)) {
     AddDereferencedPointer(L->getPointerOperand(), PtrSet, DL);
   } else if (StoreInst *S = dyn_cast<StoreInst>(I)) {