Index: llvm/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/lib/Analysis/LazyValueInfo.cpp +++ llvm/lib/Analysis/LazyValueInfo.cpp @@ -136,12 +136,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; @@ -155,89 +152,63 @@ /// 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 BlockCacheEntryTy { + 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; - - /// This is all of the cached information for all values, - /// mapped from Value* to key information. - DenseMap> ValueCache; - OverDefinedCacheTy OverDefinedCache; - + /// Cached information per basic block. + DenseMap, BlockCacheEntryTy> BlockCache; + /// Set of value handles used to erase values from the cache on deletion. + DenseSet> ValueHandles; public: void insertResult(Value *Val, BasicBlock *BB, const ValueLatticeElement &Result) { - SeenBlocks.insert(BB); - + auto &CacheEntry = BlockCache.try_emplace(BB).first->second; // 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; + CacheEntry.OverDefined.insert(Val); + else + CacheEntry.LatticeElements.insert({ Val, Result }); - return ODI->second.count(V); + auto HandleIt = ValueHandles.find_as(Val); + if (HandleIt == ValueHandles.end()) + ValueHandles.insert({ Val, this }); } bool hasCachedValueInfo(Value *V, BasicBlock *BB) const { - if (isOverdefined(V, BB)) - return true; - - auto I = ValueCache.find_as(V); - if (I == ValueCache.end()) + auto It = BlockCache.find(BB); + if (It == BlockCache.end()) return false; - return I->second->BlockVals.count(BB); + return It->second.OverDefined.count(V) || + It->second.LatticeElements.count(V); } ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const { - if (isOverdefined(V, BB)) + auto It = BlockCache.find(BB); + if (It == BlockCache.end()) + return ValueLatticeElement(); + + if (It->second.OverDefined.count(V)) return ValueLatticeElement::getOverdefined(); - auto I = ValueCache.find_as(V); - if (I == ValueCache.end()) + auto LatticeIt = It->second.LatticeElements.find(V); + if (LatticeIt == It->second.LatticeElements.end()) return ValueLatticeElement(); - auto BBI = I->second->BlockVals.find(BB); - if (BBI == I->second->BlockVals.end()) - return ValueLatticeElement(); - 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. @@ -251,23 +222,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() { @@ -277,18 +243,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, @@ -306,10 +261,11 @@ std::vector worklist; worklist.push_back(OldSucc); - auto I = OverDefinedCache.find(OldSucc); - if (I == OverDefinedCache.end()) + auto I = BlockCache.find(OldSucc); + if (I == BlockCache.end() || I->second.OverDefined.empty()) return; // Nothing to process here. - SmallVector ValsToClear(I->second.begin(), I->second.end()); + SmallVector ValsToClear(I->second.OverDefined.begin(), + I->second.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 @@ -323,10 +279,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) { @@ -336,11 +292,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;