[WIP][LazyValueInfo] Fix non-determinism in cache.

[efriedma]

Summary

OverDefinedCache contains a set of values that are overdefined in a given basic block. However, we don't reliably update the set when one of the values is erased.

This is really two fixes: one, add a PoisoningVH to catch the issue, and two, fix the resulting issue.

I'm posting this now for two reasons: one, to verify this actually fixes https://bugs.llvm.org/show_bug.cgi?id=43909, and two, to ask for ideas on how to improve the algorithm. The current implementation is really inefficient, but I'm not sure what the best approach looks like.

I haven't reduced the testcase yet.

Fixes https://bugs.llvm.org/show_bug.cgi?id=43909 (hopefully).

[lebedev.ri]

Was there any progress with test case?

[efriedma]

Abandoning in favor of D70376

llvm/lib/Analysis/LazyValueInfo.cpp

namespace {
   };
 } // end anonymous namespace
 
 namespace {
   /// This is the cache kept by LazyValueInfo which
   /// 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:
     /// This is all of the cached block information for exactly one Value*.
     /// The entries are sorted by the BasicBlock* of the
     /// entries, allowing us to do a lookup with a binary search.
     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
     /// memory overhead.
private:
     DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
     /// This tracks, on a per-block basis, the set of values that are
     /// over-defined at the end of that block.
     PerBlockValueCacheTy OverDefinedCache;
     /// This tracks, on a per-block basis, the set of pointers that are
     /// 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,
                       const ValueLatticeElement &Result) {
       SeenBlocks.insert(BB);
 
       // 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);
           It = ValueCache.find_as(Val);
           assert(It != ValueCache.end() && "Val was just added to the map!");
         }
         It->second->BlockVals[BB] = Result;
       }

 }
 
 static void eraseValueFromPerBlockValueCache(
     Value *V, LazyValueInfoCache::PerBlockValueCacheTy &Cache) {
   for (auto I = Cache.begin(), E = Cache.end(); I != E;) {
     // 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);
   }
 }
 
 void LazyValueInfoCache::eraseValue(Value *V) {
   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() {
   // This erasure deallocates *this, so it MUST happen after we're done
   // using any and all members of *this.
   Parent->eraseValue(*this);
 }
 
while (!worklist.empty()) {
 
     // Skip blocks only accessible through NewSucc.
     if (ToUpdate == NewSucc) continue;
 
     // If a value was marked overdefined in OldSucc, and is here too...
     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) {
       if (!ValueSet.erase(V))
         continue;
 
       // If we removed anything, then we potentially need to update
       // blocks successors too.
bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
 
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - unknown inst def found.\n");
   Res = getFromRangeMetadata(BBI);
   return true;
 }
 
 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);
     PtrSet.insert(Ptr);
   }
 }
 
 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)) {
     AddDereferencedPointer(S->getPointerOperand(), PtrSet, DL);
   } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
     if (MI->isVolatile()) return;
 
     // FIXME: check whether it has a valuerange that excludes zero?