Author: resistor
Date: Thu Aug 16 16:27:05 2007
New Revision: 41126
URL: http://llvm.org/viewvc/llvm-project?rev=41126&view=rev
Log:
Cache non-local memory dependence analysis. This is a significant compile
time performance win in most cases.
Modified:
llvm/trunk/include/llvm/Analysis/MemoryDependenceAnalysis.h
llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp
Modified: llvm/trunk/include/llvm/Analysis/MemoryDependenceAnalysis.h
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/MemoryDependenceAnalysis.h?rev=41126&r1=41125&r2=41126&view=diff
==============================================================================
--- llvm/trunk/include/llvm/Analysis/MemoryDependenceAnalysis.h (original)
+++ llvm/trunk/include/llvm/Analysis/MemoryDependenceAnalysis.h Thu Aug 16
16:27:05 2007
@@ -37,12 +37,20 @@
depMapType;
depMapType depGraphLocal;
+ // A map from instructions to their non-local dependencies.
+ typedef DenseMap<Instruction*, DenseMap<BasicBlock*, Value*> >
+ nonLocalDepMapType;
+ nonLocalDepMapType depGraphNonLocal;
+
// A reverse mapping form dependencies to the dependees. This is
// used when removing instructions to keep the cache coherent.
- typedef DenseMap<Instruction*, SmallPtrSet<Instruction*, 4> >
+ typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> >
reverseDepMapType;
reverseDepMapType reverseDep;
+ // A reverse mapping form dependencies to the non-local dependees.
+ reverseDepMapType reverseDepNonLocal;
+
public:
// Special marker indicating that the query has no dependency
// in the specified block.
@@ -61,7 +69,9 @@
/// Clean up memory in between runs
void releaseMemory() {
depGraphLocal.clear();
+ depGraphNonLocal.clear();
reverseDep.clear();
+ reverseDepNonLocal.clear();
}
/// getAnalysisUsage - Does not modify anything. It uses Value Numbering
Modified: llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp?rev=41126&r1=41125&r2=41126&view=diff
==============================================================================
--- llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp (original)
+++ llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp Thu Aug 16 16:27:05
2007
@@ -203,6 +203,11 @@
/// blocks between the query and its dependencies.
void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
DenseMap<BasicBlock*, Value*>& resp) {
+ if (depGraphNonLocal.count(query)) {
+ resp = depGraphNonLocal[query];
+ return;
+ }
+
// First check that we don't actually have a local dependency.
Instruction* localDep = getDependency(query);
if (localDep != NonLocal) {
@@ -212,6 +217,13 @@
// If not, go ahead and search for non-local ones.
nonLocalHelper(query, query->getParent(), resp);
+
+ // Update the non-local dependency cache
+ for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E =
resp.end();
+ I != E; ++I) {
+ depGraphNonLocal[query].insert(*I);
+ reverseDepNonLocal[I->second].insert(query);
+ }
}
/// getDependency - Return the instruction on which a memory operation
@@ -380,8 +392,6 @@
Instruction* newDep = NonLocal;
depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
- // We assume here that it's not in the reverse map if it's not in
- // the dep map. Checking it could be expensive, so don't do it.
if (depGraphEntry != depGraphLocal.end()) {
if (depGraphEntry->second.first != NonLocal &&
@@ -410,8 +420,18 @@
// Mark it as unconfirmed as long as it is not the non-local flag
depGraphLocal[*I] = std::make_pair(newDep, !newDep);
}
+
reverseDep.erase(rem);
}
+
+ if (depGraphNonLocal.count(rem)) {
+ SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[rem];
+ for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
+ I != E; ++I)
+ depGraphNonLocal.erase(*I);
+
+ reverseDepNonLocal.erase(rem);
+ }
getAnalysis<AliasAnalysis>().deleteValue(rem);
}
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
