From 7f9cb744f284f23b362b010c1986d230c89d179c Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Fri, 30 Jul 2010 23:59:40 +0000 Subject: [PATCH] Add an initial implementation of PHI translation for LazyValueInfo. This involves rolling back some of my earlier data structure improvements until I can ensure that there are no iterator invalidation problems. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@109935 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/LazyValueInfo.cpp | 107 +++++++++++++++++++++++++++-------------- 1 file changed, 72 insertions(+), 35 deletions(-) diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp index 7fef6289209..ecc1831dbe5 100644 --- a/lib/Analysis/LazyValueInfo.cpp +++ b/lib/Analysis/LazyValueInfo.cpp @@ -21,6 +21,7 @@ #include "llvm/Support/CFG.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Support/ValueHandle.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/PointerIntPair.h" @@ -212,17 +213,36 @@ namespace { /// ValueCacheEntryTy - 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. - typedef DenseMap ValueCacheEntryTy; + typedef std::map ValueCacheEntryTy; private: + /// LVIValueHandle - A callback value handle update the cache when + /// values are erased. + struct LVIValueHandle : public CallbackVH { + LazyValueInfoCache *Parent; + + LVIValueHandle(Value *V, LazyValueInfoCache *P) + : CallbackVH(V), Parent(P) { } + + void deleted(); + void allUsesReplacedWith(Value* V) { + deleted(); + } + + LVIValueHandle &operator=(Value *V) { + return *this = LVIValueHandle(V, Parent); + } + }; + /// ValueCache - This is all of the cached information for all values, /// mapped from Value* to key information. - DenseMap ValueCache; + std::map ValueCache; /// OverDefinedCache - This tracks, on a per-block basis, the set of /// values that are over-defined at the end of that block. This is required /// for cache updating. - DenseSet > OverDefinedCache; + std::set > OverDefinedCache; + public: /// getValueInBlock - This is the query interface to determine the lattice @@ -240,27 +260,6 @@ namespace { }; } // end anonymous namespace -namespace { - struct BlockCacheEntryComparator { - static int Compare(const void *LHSv, const void *RHSv) { - const LazyValueInfoCache::BlockCacheEntryTy *LHS = - static_cast(LHSv); - const LazyValueInfoCache::BlockCacheEntryTy *RHS = - static_cast(RHSv); - if (LHS->first < RHS->first) - return -1; - if (LHS->first > RHS->first) - return 1; - return 0; - } - - bool operator()(const LazyValueInfoCache::BlockCacheEntryTy &LHS, - const LazyValueInfoCache::BlockCacheEntryTy &RHS) const { - return LHS.first < RHS.first; - } - }; -} - //===----------------------------------------------------------------------===// // LVIQuery Impl //===----------------------------------------------------------------------===// @@ -278,20 +277,24 @@ namespace { /// This is the current value being queried for. Value *Val; + /// This is a pointer to the owning cache, for recursive queries. + LazyValueInfoCache &Parent; + /// This is all of the cached information about this value. ValueCacheEntryTy &Cache; /// This tracks, for each block, what values are overdefined. - DenseSet > &OverDefinedCache; + std::set > &OverDefinedCache; /// NewBlocks - This is a mapping of the new BasicBlocks which have been /// added to cache but that are not in sorted order. DenseSet NewBlockInfo; public: - LVIQuery(Value *V, ValueCacheEntryTy &VC, - DenseSet > &ODC) - : Val(V), Cache(VC), OverDefinedCache(ODC) { + LVIQuery(Value *V, LazyValueInfoCache &P, + ValueCacheEntryTy &VC, + std::set > &ODC) + : Val(V), Parent(P), Cache(VC), OverDefinedCache(ODC) { } ~LVIQuery() { @@ -314,6 +317,20 @@ namespace { }; } // end anonymous namespace +void LazyValueInfoCache::LVIValueHandle::deleted() { + Parent->ValueCache.erase(*this); + for (std::set >::iterator + I = Parent->OverDefinedCache.begin(), + E = Parent->OverDefinedCache.end(); + I != E; ) { + std::set >::iterator tmp = I; + ++I; + if (tmp->second == getValPtr()) + Parent->OverDefinedCache.erase(tmp); + } +} + + /// getCachedEntryForBlock - See if we already have a value for this block. If /// so, return it, otherwise create a new entry in the Cache map to use. LVILatticeVal &LVIQuery::getCachedEntryForBlock(BasicBlock *BB) { @@ -373,8 +390,27 @@ LVILatticeVal LVIQuery::getBlockValue(BasicBlock *BB) { // If this value is defined by an instruction in this block, we have to // process it here somehow or return overdefined. if (PHINode *PN = dyn_cast(BBI)) { - (void)PN; - // TODO: PHI Translation in preds. + LVILatticeVal Result; // Start Undefined. + + // Loop over all of our predecessors, merging what we know from them into + // result. + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + Value* PhiVal = PN->getIncomingValueForBlock(*PI); + Result.mergeIn(Parent.getValueOnEdge(PhiVal, *PI, BB)); + + // If we hit overdefined, exit early. The BlockVals entry is already set + // to overdefined. + if (Result.isOverdefined()) { + DEBUG(dbgs() << " compute BB '" << BB->getName() + << "' - overdefined because of pred.\n"); + return Result; + } + } + + // Return the merged value, which is more precise than 'overdefined'. + assert(!Result.isOverdefined()); + return getCachedEntryForBlock(BB) = Result; + } else { } @@ -459,7 +495,8 @@ LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB) { DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '" << BB->getName() << "'\n"); - LVILatticeVal Result = LVIQuery(V, ValueCache[V], + LVILatticeVal Result = LVIQuery(V, *this, + ValueCache[LVIValueHandle(V, this)], OverDefinedCache).getBlockValue(BB); DEBUG(dbgs() << " Result = " << Result << "\n"); @@ -476,7 +513,7 @@ getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB) { << FromBB->getName() << "' to '" << ToBB->getName() << "'\n"); LVILatticeVal Result = - LVIQuery(V, ValueCache[V], + LVIQuery(V, *this, ValueCache[LVIValueHandle(V, this)], OverDefinedCache).getEdgeValue(FromBB, ToBB); DEBUG(dbgs() << " Result = " << Result << "\n"); @@ -500,7 +537,7 @@ void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, worklist.push_back(OldSucc); DenseSet ClearSet; - for (DenseSet >::iterator + for (std::set >::iterator I = OverDefinedCache.begin(), E = OverDefinedCache.end(); I != E; ++I) { if (I->first == OldSucc) ClearSet.insert(I->second); @@ -521,12 +558,12 @@ void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, for (DenseSet::iterator I = ClearSet.begin(),E = ClearSet.end(); I != E; ++I) { // If a value was marked overdefined in OldSucc, and is here too... - DenseSet >::iterator OI = + std::set >::iterator OI = OverDefinedCache.find(std::make_pair(ToUpdate, *I)); if (OI == OverDefinedCache.end()) continue; // Remove it from the caches. - ValueCacheEntryTy &Entry = ValueCache[*I]; + ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(*I, this)]; ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate); assert(CI != Entry.end() && "Couldn't find entry to update?"); -- 2.11.0