add another level of caching for non-local pointer queries, keeping
track of whether the CachedNonLocalPointerInfo for a block is specific
to a block. If so, just return it without any pred scanning. This is
good for a 6% speedup on GVN (when it uses this lookup method, which
it doesn't right now).
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60695 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 2413bbc..c42633b 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -36,6 +36,8 @@
"Number of cached, but dirty, non-local ptr responses");
STATISTIC(NumUncacheNonLocalPtr,
"Number of uncached non-local ptr responses");
+STATISTIC(NumCacheCompleteNonLocalPtr,
+ "Number of block queries that were completely cached");
char MemoryDependenceAnalysis::ID = 0;
@@ -479,12 +481,32 @@
bool isLoad, BasicBlock *StartBB,
SmallVectorImpl<NonLocalDepEntry> &Result,
SmallPtrSet<BasicBlock*, 64> &Visited) {
- SmallVector<BasicBlock*, 32> Worklist;
- Worklist.push_back(StartBB);
-
// Look up the cached info for Pointer.
ValueIsLoadPair CacheKey(Pointer, isLoad);
- NonLocalDepInfo *Cache = &NonLocalPointerDeps[CacheKey];
+
+ std::pair<BasicBlock*, NonLocalDepInfo> &CacheInfo =
+ NonLocalPointerDeps[CacheKey];
+ NonLocalDepInfo *Cache = &CacheInfo.second;
+
+ // If we have valid cached information for exactly the block we are
+ // investigating, just return it with no recomputation.
+ if (CacheInfo.first == StartBB) {
+ for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
+ I != E; ++I)
+ if (!I->second.isNonLocal())
+ Result.push_back(*I);
+ ++NumCacheCompleteNonLocalPtr;
+ return;
+ }
+
+ // Otherwise, either this is a new block, a block with an invalid cache
+ // pointer or one that we're about to invalidate by putting more info into it
+ // than its valid cache info. If empty, the result will be valid cache info,
+ // otherwise it isn't.
+ CacheInfo.first = Cache->empty() ? StartBB : 0;
+
+ SmallVector<BasicBlock*, 32> Worklist;
+ Worklist.push_back(StartBB);
// Keep track of the entries that we know are sorted. Previously cached
// entries will all be sorted. The entries we add we only sort on demand (we
@@ -591,7 +613,7 @@
// Remove all of the entries in the BB->val map. This involves removing
// instructions from the reverse map.
- NonLocalDepInfo &PInfo = It->second;
+ NonLocalDepInfo &PInfo = It->second.second;
for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
Instruction *Target = PInfo[i].second.getInst();
@@ -741,7 +763,10 @@
assert(P.getPointer() != RemInst &&
"Already removed NonLocalPointerDeps info for RemInst");
- NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P];
+ NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].second;
+
+ // The cache is not valid for any specific block anymore.
+ NonLocalPointerDeps[P].first = 0;
// Update any entries for RemInst to use the instruction after it.
for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
@@ -784,7 +809,7 @@
for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
E = NonLocalPointerDeps.end(); I != E; ++I) {
assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
- const NonLocalDepInfo &Val = I->second;
+ const NonLocalDepInfo &Val = I->second.second;
for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
II != E; ++II)
assert(II->second.getInst() != D && "Inst occurs as NLPD value");