#include "llvm/Function.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Support/CFG.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Target/TargetData.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
+// Control the calculation of non-local dependencies by only examining the
+// predecessors if the basic block has less than X amount (50 by default).
+static cl::opt<int>
+PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50),
+ cl::desc("Control the calculation of non-local"
+ "dependencies (default = 50)"));
+
STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
// Register this pass...
static RegisterPass<MemoryDependenceAnalysis> X("memdep",
- "Memory Dependence Analysis");
+ "Memory Dependence Analysis", false, true);
void MemoryDependenceAnalysis::ping(Instruction *D) {
for (depMapType::iterator I = depGraphLocal.begin(), E = depGraphLocal.end();
for (nonLocalDepMapType::iterator I = depGraphNonLocal.begin(), E = depGraphNonLocal.end();
I != E; ++I) {
assert(I->first != D);
+ for (DenseMap<BasicBlock*, Value*>::iterator II = I->second.begin(),
+ EE = I->second.end(); II != EE; ++II)
+ assert(II->second != D);
}
for (reverseDepMapType::iterator I = reverseDep.begin(), E = reverseDep.end();
// If the starting point was specifiy, use it
if (start) {
QI = start;
- blockBegin = start->getParent()->end();
+ blockBegin = start->getParent()->begin();
// If the starting point wasn't specified, but the block was, use it
} else if (!start && block) {
QI = block->end();
- blockBegin = block->end();
+ blockBegin = block->begin();
}
// Walk backwards through the block, looking for dependencies
// FreeInsts erase the entire structure
pointerSize = ~0UL;
- } else if (isa<CallInst>(QI)) {
+ } else if (CallSite::get(QI).getInstruction() != 0) {
AliasAnalysis::ModRefBehavior result =
AA.getModRefBehavior(CallSite::get(QI));
- if (result != AliasAnalysis::DoesNotAccessMemory &&
- result != AliasAnalysis::OnlyReadsMemory) {
+ if (result != AliasAnalysis::DoesNotAccessMemory) {
if (!start && !block) {
cachedResult.first = QI;
cachedResult.second = true;
// Current stack of the DFS
SmallVector<BasicBlock*, 4> stack;
- stack.push_back(block);
+ for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
+ PI != PE; ++PI)
+ stack.push_back(*PI);
// Do a basic DFS
while (!stack.empty()) {
// If we re-encounter the starting block, we still need to search it
// because there might be a dependency in the starting block AFTER
// the position of the query. This is necessary to get loops right.
- } else if (BB == block && stack.size() > 1) {
+ } else if (BB == block) {
visited.insert(BB);
Instruction* localDep = getDependency(query, 0, BB);
}
// If we didn't find anything, recurse on the precessors of this block
+ // Only do this for blocks with a small number of predecessors.
bool predOnStack = false;
bool inserted = false;
- for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
- PI != PE; ++PI)
- if (!visited.count(*PI)) {
- stack.push_back(*PI);
- inserted = true;
- } else
- predOnStack = true;
+ if (std::distance(pred_begin(BB), pred_end(BB)) <= PredLimit) {
+ for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
+ PI != PE; ++PI)
+ if (!visited.count(*PI)) {
+ stack.push_back(*PI);
+ inserted = true;
+ } else
+ predOnStack = true;
+ }
// If we inserted a new predecessor, then we'll come back to this block
if (inserted)
resp = cached;
+ // Update the reverse non-local dependency cache
+ for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end();
+ I != E; ++I)
+ reverseDepNonLocal[I->second].insert(query);
+
return;
} else
NumUncacheNonlocal++;
}
/// getDependency - Return the instruction on which a memory operation
-/// depends. The local paramter indicates if the query should only
+/// depends. The local parameter indicates if the query should only
/// evaluate dependencies within the same basic block.
Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
Instruction* start,
return NonLocal;
}
+/// dropInstruction - Remove an instruction from the analysis, making
+/// absolutely conservative assumptions when updating the cache. This is
+/// useful, for example when an instruction is changed rather than removed.
+void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) {
+ depMapType::iterator depGraphEntry = depGraphLocal.find(drop);
+ if (depGraphEntry != depGraphLocal.end())
+ reverseDep[depGraphEntry->second.first].erase(drop);
+
+ // Drop dependency information for things that depended on this instr
+ SmallPtrSet<Instruction*, 4>& set = reverseDep[drop];
+ for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
+ I != E; ++I)
+ depGraphLocal.erase(*I);
+
+ depGraphLocal.erase(drop);
+ reverseDep.erase(drop);
+
+ for (DenseMap<BasicBlock*, Value*>::iterator DI =
+ depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end();
+ DI != DE; ++DI)
+ if (DI->second != None)
+ reverseDepNonLocal[DI->second].erase(drop);
+
+ if (reverseDepNonLocal.count(drop)) {
+ SmallPtrSet<Instruction*, 4>& set = reverseDepNonLocal[drop];
+ for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
+ I != E; ++I)
+ for (DenseMap<BasicBlock*, Value*>::iterator DI =
+ depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
+ DI != DE; ++DI)
+ if (DI->second == drop)
+ DI->second = Dirty;
+ }
+
+ reverseDepNonLocal.erase(drop);
+ nonLocalDepMapType::iterator I = depGraphNonLocal.find(drop);
+ if (I != depGraphNonLocal.end())
+ depGraphNonLocal.erase(I);
+}
+
/// removeInstruction - Remove an instruction from the dependence analysis,
/// updating the dependence of instructions that previously depended on it.
/// This method attempts to keep the cache coherent using the reverse map.
// Figure out the new dep for things that currently depend on rem
Instruction* newDep = NonLocal;
- reverseDep[depGraphLocal[rem].first].erase(rem);
-
for (DenseMap<BasicBlock*, Value*>::iterator DI =
depGraphNonLocal[rem].begin(), DE = depGraphNonLocal[rem].end();
DI != DE; ++DI)
depMapType::iterator depGraphEntry = depGraphLocal.find(rem);
if (depGraphEntry != depGraphLocal.end()) {
+ reverseDep[depGraphEntry->second.first].erase(rem);
+
if (depGraphEntry->second.first != NonLocal &&
+ depGraphEntry->second.first != None &&
depGraphEntry->second.second) {
// If we have dep info for rem, set them to it
BasicBlock::iterator RI = depGraphEntry->second.first;
RI++;
newDep = RI;
- } else if (depGraphEntry->second.first == NonLocal &&
+ } else if ( (depGraphEntry->second.first == NonLocal ||
+ depGraphEntry->second.first == None ) &&
depGraphEntry->second.second ) {
// If we have a confirmed non-local flag, use it
- newDep = NonLocal;
+ newDep = depGraphEntry->second.first;
} else {
// Otherwise, use the immediate successor of rem
// NOTE: This is because, when getDependence is called, it will first
RI++;
newDep = RI;
}
-
- SmallPtrSet<Instruction*, 4>& set = reverseDep[rem];
- for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
- I != E; ++I) {
- // Insert the new dependencies
- // Mark it as unconfirmed as long as it is not the non-local flag
- depGraphLocal[*I] = std::make_pair(newDep, !newDep);
- }
+ } else {
+ // Otherwise, use the immediate successor of rem
+ // NOTE: This is because, when getDependence is called, it will first
+ // check the immediate predecessor of what is in the cache.
+ BasicBlock::iterator RI = rem;
+ RI++;
+ newDep = RI;
+ }
+
+ SmallPtrSet<Instruction*, 4>& set = reverseDep[rem];
+ for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
+ I != E; ++I) {
+ // Insert the new dependencies
+ // Mark it as unconfirmed as long as it is not the non-local flag
+ depGraphLocal[*I] = std::make_pair(newDep, (newDep == NonLocal ||
+ newDep == None));
}
depGraphLocal.erase(rem);
projects / oota-llvm.git / blobdiff