#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Support/CFG.h"
#include "llvm/Target/TargetData.h"
+#include "llvm/ADT/Statistic.h"
+
+#define DEBUG_TYPE "memdep"
using namespace llvm;
+STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
+STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
+
char MemoryDependenceAnalysis::ID = 0;
Instruction* const MemoryDependenceAnalysis::NonLocal = (Instruction*)-3;
Instruction* const MemoryDependenceAnalysis::None = (Instruction*)-4;
+Instruction* const MemoryDependenceAnalysis::Dirty = (Instruction*)-5;
// Register this pass...
static RegisterPass<MemoryDependenceAnalysis> X("memdep",
DenseMap<BasicBlock*, Value*>& resp) {
// Set of blocks that we've already visited in our DFS
SmallPtrSet<BasicBlock*, 4> visited;
+ // If we're updating a dirtied cache entry, we don't need to reprocess
+ // already computed entries.
+ for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(),
+ E = resp.end(); I != E; ++I)
+ if (I->second != Dirty)
+ visited.insert(I->first);
+
// Current stack of the DFS
SmallVector<BasicBlock*, 4> stack;
stack.push_back(block);
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) {
- resp.insert(std::make_pair(query->getParent(),localDep));
+ DenseMap<BasicBlock*, Value*>& cached = depGraphNonLocal[query];
+ NumCacheNonlocal++;
+
+ SmallVector<BasicBlock*, 4> dirtied;
+ for (DenseMap<BasicBlock*, Value*>::iterator I = cached.begin(),
+ E = cached.end(); I != E; ++I)
+ if (I->second == Dirty)
+ dirtied.push_back(I->first);
+
+ for (SmallVector<BasicBlock*, 4>::iterator I = dirtied.begin(),
+ E = dirtied.end(); I != E; ++I) {
+ Instruction* localDep = getDependency(query, 0, *I);
+ if (localDep != NonLocal)
+ cached[*I] = localDep;
+ else {
+ cached.erase(*I);
+ nonLocalHelper(query, *I, cached);
+ }
+ }
+
+ resp = cached;
+
return;
- }
+ } else
+ NumUncacheNonlocal++;
- // If not, go ahead and search for non-local ones.
+ // If not, go ahead and search for non-local deps.
nonLocalHelper(query, query->getParent(), resp);
// Update the non-local dependency cache
reverseDep.erase(rem);
}
- if (depGraphNonLocal.count(rem)) {
+ if (reverseDepNonLocal.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);
+ for (DenseMap<BasicBlock*, Value*>::iterator DI =
+ depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
+ DI != DE; ++DI)
+ if (DI->second == rem)
+ DI->second = Dirty;
reverseDepNonLocal.erase(rem);
}