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 @@ -137,12 +137,9 @@ /// A callback value handle updates the cache when values are erased. class LazyValueInfoCache; struct LVIValueHandle final : public CallbackVH { - // Needs to access getValPtr(), which is protected. - friend struct DenseMapInfo; - LazyValueInfoCache *Parent; - LVIValueHandle(Value *V, LazyValueInfoCache *P) + LVIValueHandle(Value *V, LazyValueInfoCache *P = nullptr) : CallbackVH(V), Parent(P) { } void deleted() override; @@ -156,79 +153,73 @@ /// This is the cache kept by LazyValueInfo which /// maintains information about queries across the clients' queries. class LazyValueInfoCache { - /// 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. - struct ValueCacheEntryTy { - ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {} - LVIValueHandle Handle; - SmallDenseMap, ValueLatticeElement, 4> BlockVals; + /// This is all of the cached information for one basic block. It contains + /// the per-value lattice elements, as well as a separate set for + /// overdefined values to reduce memory usage. + struct BlockCacheEntry { + SmallDenseMap, ValueLatticeElement, 4> LatticeElements; + SmallDenseSet, 4> OverDefined; }; - /// This tracks, on a per-block basis, the set of values that are - /// over-defined at the end of that block. - typedef DenseMap, SmallPtrSet> - OverDefinedCacheTy; - /// Keep track of all blocks that we have ever seen, so we - /// don't spend time removing unused blocks from our caches. - DenseSet > SeenBlocks; + /// Cached information per basic block. + DenseMap, std::unique_ptr> + BlockCache; + /// Set of value handles used to erase values from the cache on deletion. + DenseSet> ValueHandles; + + const BlockCacheEntry *getBlockEntry(BasicBlock *BB) const { + auto It = BlockCache.find(BB); + if (It == BlockCache.end()) + return nullptr; + return It->second.get(); + } - /// This is all of the cached information for all values, - /// mapped from Value* to key information. - DenseMap> ValueCache; - OverDefinedCacheTy OverDefinedCache; + BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) { + auto It = BlockCache.find(BB); + if (It == BlockCache.end()) + It = BlockCache.insert({ BB, std::make_unique() }) + .first; + return It->second.get(); + } public: void insertResult(Value *Val, BasicBlock *BB, const ValueLatticeElement &Result) { - SeenBlocks.insert(BB); + BlockCacheEntry *Entry = getOrCreateBlockEntry(BB); // Insert over-defined values into their own cache to reduce memory // overhead. if (Result.isOverdefined()) - OverDefinedCache[BB].insert(Val); - else { - auto It = ValueCache.find_as(Val); - if (It == ValueCache.end()) { - ValueCache[Val] = std::make_unique(Val, this); - It = ValueCache.find_as(Val); - assert(It != ValueCache.end() && "Val was just added to the map!"); - } - It->second->BlockVals[BB] = Result; - } - } - - bool isOverdefined(Value *V, BasicBlock *BB) const { - auto ODI = OverDefinedCache.find(BB); - - if (ODI == OverDefinedCache.end()) - return false; + Entry->OverDefined.insert(Val); + else + Entry->LatticeElements.insert({ Val, Result }); - return ODI->second.count(V); + auto HandleIt = ValueHandles.find_as(Val); + if (HandleIt == ValueHandles.end()) + ValueHandles.insert({ Val, this }); } Optional getCachedValueInfo(Value *V, BasicBlock *BB) const { - if (isOverdefined(V, BB)) + const BlockCacheEntry *Entry = getBlockEntry(BB); + if (!Entry) + return None; + + if (Entry->OverDefined.count(V)) return ValueLatticeElement::getOverdefined(); - auto I = ValueCache.find_as(V); - if (I == ValueCache.end()) + auto LatticeIt = Entry->LatticeElements.find(V); + if (LatticeIt == Entry->LatticeElements.end()) return None; - auto BBI = I->second->BlockVals.find(BB); - if (BBI == I->second->BlockVals.end()) - return None; - return BBI->second; + + return LatticeIt->second; } /// clear - Empty the cache. void clear() { - SeenBlocks.clear(); - ValueCache.clear(); - OverDefinedCache.clear(); + BlockCache.clear(); + ValueHandles.clear(); } /// Inform the cache that a given value has been deleted. @@ -242,23 +233,18 @@ /// OldSucc might have (unless also overdefined in NewSucc). This just /// flushes elements from the cache and does not add any. void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc); - - friend struct LVIValueHandle; }; } void LazyValueInfoCache::eraseValue(Value *V) { - for (auto I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E;) { - // Copy and increment the iterator immediately so we can erase behind - // ourselves. - auto Iter = I++; - SmallPtrSetImpl &ValueSet = Iter->second; - ValueSet.erase(V); - if (ValueSet.empty()) - OverDefinedCache.erase(Iter); + for (auto &Pair : BlockCache) { + Pair.second->LatticeElements.erase(V); + Pair.second->OverDefined.erase(V); } - ValueCache.erase(V); + auto HandleIt = ValueHandles.find_as(V); + if (HandleIt != ValueHandles.end()) + ValueHandles.erase(HandleIt); } void LVIValueHandle::deleted() { @@ -268,18 +254,7 @@ } void LazyValueInfoCache::eraseBlock(BasicBlock *BB) { - // Shortcut if we have never seen this block. - DenseSet >::iterator I = SeenBlocks.find(BB); - if (I == SeenBlocks.end()) - return; - SeenBlocks.erase(I); - - auto ODI = OverDefinedCache.find(BB); - if (ODI != OverDefinedCache.end()) - OverDefinedCache.erase(ODI); - - for (auto &I : ValueCache) - I.second->BlockVals.erase(BB); + BlockCache.erase(BB); } void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc, @@ -297,10 +272,11 @@ std::vector worklist; worklist.push_back(OldSucc); - auto I = OverDefinedCache.find(OldSucc); - if (I == OverDefinedCache.end()) + const BlockCacheEntry *Entry = getBlockEntry(OldSucc); + if (!Entry || Entry->OverDefined.empty()) return; // Nothing to process here. - SmallVector ValsToClear(I->second.begin(), I->second.end()); + SmallVector ValsToClear(Entry->OverDefined.begin(), + Entry->OverDefined.end()); // Use a worklist to perform a depth-first search of OldSucc's successors. // NOTE: We do not need a visited list since any blocks we have already @@ -314,10 +290,10 @@ 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()) + auto OI = BlockCache.find(ToUpdate); + if (OI == BlockCache.end() || OI->second->OverDefined.empty()) continue; - SmallPtrSetImpl &ValueSet = OI->second; + auto &ValueSet = OI->second->OverDefined; bool changed = false; for (Value *V : ValsToClear) { @@ -327,11 +303,6 @@ // If we removed anything, then we potentially need to update // blocks successors too. changed = true; - - if (ValueSet.empty()) { - OverDefinedCache.erase(OI); - break; - } } if (!changed) continue;