Reimplement the non-local dependency data structure in terms of a sorted
vector instead of a densemap. This shrinks the memory usage of this thing
substantially (the high water mark) as well as making operations like
scanning it faster. This speeds up memdep slightly, gvn goes from
3.9376 to 3.9118s on 403.gcc
This also splits out the statistics for the cached non-local case to
differentiate between the dirty and clean cached case. Here's the stats
for 403.gcc:
6153 memdep - Number of dirty cached non-local responses
169336 memdep - Number of fully cached non-local responses
162428 memdep - Number of uncached non-local responses
yay for caching :)
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60313 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 14646ad..c47ec04 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -28,9 +28,9 @@
#include "llvm/Target/TargetData.h"
using namespace llvm;
-STATISTIC(NumCacheNonLocal, "Number of cached non-local responses");
+STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
+STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
-
char MemoryDependenceAnalysis::ID = 0;
// Register this pass...
@@ -51,10 +51,12 @@
return false;
}
+
/// getCallSiteDependency - Private helper for finding the local dependencies
/// of a call site.
MemDepResult MemoryDependenceAnalysis::
getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt, BasicBlock *BB) {
+
// Walk backwards through the block, looking for dependencies
while (ScanIt != BB->begin()) {
Instruction *Inst = --ScanIt;
@@ -224,16 +226,13 @@
/// This method assumes the instruction returns a "nonlocal" dependency
/// within its own block.
///
-void MemoryDependenceAnalysis::
-getNonLocalDependency(Instruction *QueryInst,
- SmallVectorImpl<std::pair<BasicBlock*,
- MemDepResult> > &Result) {
+const MemoryDependenceAnalysis::NonLocalDepInfo &
+MemoryDependenceAnalysis::getNonLocalDependency(Instruction *QueryInst) {
assert(getDependency(QueryInst).isNonLocal() &&
"getNonLocalDependency should only be used on insts with non-local deps!");
PerInstNLInfo &CacheP = NonLocalDeps[QueryInst];
- if (CacheP.getPointer() == 0) CacheP.setPointer(new NonLocalDepInfo());
- NonLocalDepInfo &Cache = *CacheP.getPointer();
+ NonLocalDepInfo &Cache = CacheP.first;
/// DirtyBlocks - This is the set of blocks that need to be recomputed. In
/// the cached case, this can happen due to instructions being deleted etc. In
@@ -242,17 +241,24 @@
SmallVector<BasicBlock*, 32> DirtyBlocks;
if (!Cache.empty()) {
+ // Okay, we have a cache entry. If we know it is not dirty, just return it
+ // with no computation.
+ if (!CacheP.second) {
+ NumCacheNonLocal++;
+ return Cache;
+ }
+
// If we already have a partially computed set of results, scan them to
- // determine what is dirty, seeding our initial DirtyBlocks worklist. The
- // Int bit of CacheP tells us if we have anything dirty.
- if (CacheP.getInt())
- for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
- I != E; ++I)
- if (I->second.isDirty())
- DirtyBlocks.push_back(I->first);
+ // determine what is dirty, seeding our initial DirtyBlocks worklist.
+ for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
+ I != E; ++I)
+ if (I->second.isDirty())
+ DirtyBlocks.push_back(I->first);
- NumCacheNonLocal++;
+ // Sort the cache so that we can do fast binary search lookups below.
+ std::sort(Cache.begin(), Cache.end());
+ ++NumCacheDirtyNonLocal;
//cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
// << Cache.size() << " cached: " << *QueryInst;
} else {
@@ -262,52 +268,80 @@
NumUncacheNonLocal++;
}
+ // Visited checked first, vector in sorted order.
+ SmallPtrSet<BasicBlock*, 64> Visited;
+
+ unsigned NumSortedEntries = Cache.size();
+
// Iterate while we still have blocks to update.
while (!DirtyBlocks.empty()) {
BasicBlock *DirtyBB = DirtyBlocks.back();
DirtyBlocks.pop_back();
- // Get the entry for this block. Note that this relies on MemDepResult
- // default initializing to Dirty.
- MemDepResult &DirtyBBEntry = Cache[DirtyBB];
+ // Already processed this block?
+ if (!Visited.insert(DirtyBB))
+ continue;
- // If DirtyBBEntry isn't dirty, it ended up on the worklist multiple times.
- if (!DirtyBBEntry.isDirty()) continue;
-
+ // Do a binary search to see if we already have an entry for this block in
+ // the cache set. If so, find it.
+ NonLocalDepInfo::iterator Entry =
+ std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
+ std::make_pair(DirtyBB, MemDepResult()));
+ if (Entry != Cache.begin() && (&*Entry)[-1].first == DirtyBB)
+ --Entry;
+
+ MemDepResult *ExistingResult = 0;
+ if (Entry != Cache.begin()+NumSortedEntries &&
+ Entry->first == DirtyBB) {
+ // If we already have an entry, and if it isn't already dirty, the block
+ // is done.
+ if (!Entry->second.isDirty())
+ continue;
+
+ // Otherwise, remember this slot so we can update the value.
+ ExistingResult = &Entry->second;
+ }
+
// If the dirty entry has a pointer, start scanning from it so we don't have
// to rescan the entire block.
BasicBlock::iterator ScanPos = DirtyBB->end();
- if (Instruction *Inst = DirtyBBEntry.getInst()) {
- ScanPos = Inst;
+ if (ExistingResult) {
+ if (Instruction *Inst = ExistingResult->getInst()) {
+ ScanPos = Inst;
- // We're removing QueryInst's dependence on Inst.
- SmallPtrSet<Instruction*, 4> &InstMap = ReverseNonLocalDeps[Inst];
- InstMap.erase(QueryInst);
- if (InstMap.empty()) ReverseNonLocalDeps.erase(Inst);
+ // We're removing QueryInst's use of Inst.
+ SmallPtrSet<Instruction*, 4> &InstMap = ReverseNonLocalDeps[Inst];
+ InstMap.erase(QueryInst);
+ if (InstMap.empty()) ReverseNonLocalDeps.erase(Inst);
+ }
}
// Find out if this block has a local dependency for QueryInst.
- DirtyBBEntry = getDependencyFrom(QueryInst, ScanPos, DirtyBB);
-
+ MemDepResult Dep = getDependencyFrom(QueryInst, ScanPos, DirtyBB);
+
+ // If we had a dirty entry for the block, update it. Otherwise, just add
+ // a new entry.
+ if (ExistingResult)
+ *ExistingResult = Dep;
+ else
+ Cache.push_back(std::make_pair(DirtyBB, Dep));
+
// If the block has a dependency (i.e. it isn't completely transparent to
- // the value), remember it!
- if (!DirtyBBEntry.isNonLocal()) {
+ // the value), remember the association!
+ if (!Dep.isNonLocal()) {
// Keep the ReverseNonLocalDeps map up to date so we can efficiently
// update this when we remove instructions.
- if (Instruction *Inst = DirtyBBEntry.getInst())
+ if (Instruction *Inst = Dep.getInst())
ReverseNonLocalDeps[Inst].insert(QueryInst);
- continue;
- }
+ } else {
- // If the block *is* completely transparent to the load, we need to check
- // the predecessors of this block. Add them to our worklist.
- DirtyBlocks.append(pred_begin(DirtyBB), pred_end(DirtyBB));
+ // If the block *is* completely transparent to the load, we need to check
+ // the predecessors of this block. Add them to our worklist.
+ DirtyBlocks.append(pred_begin(DirtyBB), pred_end(DirtyBB));
+ }
}
-
- // Copy the result into the output set.
- for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end(); I != E;++I)
- Result.push_back(std::make_pair(I->first, I->second));
+ return Cache;
}
/// removeInstruction - Remove an instruction from the dependence analysis,
@@ -318,12 +352,11 @@
// for any cached queries.
NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
if (NLDI != NonLocalDeps.end()) {
- NonLocalDepInfo &BlockMap = *NLDI->second.getPointer();
+ NonLocalDepInfo &BlockMap = NLDI->second.first;
for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
DI != DE; ++DI)
if (Instruction *Inst = DI->second.getInst())
ReverseNonLocalDeps[Inst].erase(RemInst);
- delete &BlockMap;
NonLocalDeps.erase(NLDI);
}
@@ -392,12 +425,11 @@
assert(*I != RemInst && "Already removed NonLocalDep info for RemInst");
PerInstNLInfo &INLD = NonLocalDeps[*I];
- assert(INLD.getPointer() != 0 && "Reverse mapping out of date?");
// The information is now dirty!
- INLD.setInt(true);
+ INLD.second = true;
- for (NonLocalDepInfo::iterator DI = INLD.getPointer()->begin(),
- DE = INLD.getPointer()->end(); DI != DE; ++DI) {
+ for (NonLocalDepInfo::iterator DI = INLD.first.begin(),
+ DE = INLD.first.end(); DI != DE; ++DI) {
if (DI->second.getInst() != RemInst) continue;
// Convert to a dirty entry for the subsequent instruction.
@@ -439,8 +471,8 @@
E = NonLocalDeps.end(); I != E; ++I) {
assert(I->first != D && "Inst occurs in data structures");
const PerInstNLInfo &INLD = I->second;
- for (NonLocalDepInfo::iterator II = INLD.getPointer()->begin(),
- EE = INLD.getPointer()->end(); II != EE; ++II)
+ for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
+ EE = INLD.first.end(); II != EE; ++II)
assert(II->second.getInst() != D && "Inst occurs in data structures");
}