#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Support/CFG.h"
#include "llvm/Target/TargetData.h"
using namespace llvm;
char MemoryDependenceAnalysis::ID = 0;
-Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)0;
-Instruction* MemoryDependenceAnalysis::None = (Instruction*)~0;
+Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)-2;
+Instruction* MemoryDependenceAnalysis::None = (Instruction*)-3;
// Register this pass...
-RegisterPass<MemoryDependenceAnalysis> X("memdep",
- "Memory Dependence Analysis");
+static RegisterPass<MemoryDependenceAnalysis> X("memdep",
+ "Memory Dependence Analysis");
/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
///
}
// Find the dependency of a CallSite
-Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, bool local) {
+Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruction* start,
+ bool local) {
assert(local && "Non-local memory dependence analysis not yet implemented");
AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
} else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
pointer = AI;
if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
- pointerSize = C->getZExtValue();
+ pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
else
pointerSize = ~0UL;
} else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
} else {
continue;
}
- }
+ } else
+ continue;
if (AA.getModRefInfo(C, pointer, pointerSize) != AliasAnalysis::NoModRef) {
depGraphLocal.insert(std::make_pair(C.getInstruction(), std::make_pair(QI, true)));
return NonLocal;
}
+void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
+ BasicBlock* block,
+ DenseMap<BasicBlock*, Value*>& resp) {
+ SmallPtrSet<BasicBlock*, 4> visited;
+ SmallVector<BasicBlock*, 4> stack;
+ stack.push_back(block);
+
+ while (!stack.empty()) {
+ BasicBlock* BB = stack.back();
+
+ visited.insert(BB);
+
+ if (resp.count(BB)) {
+ stack.pop_back();
+ continue;
+ }
+
+ if (BB != block) {
+ Instruction* localDep = getDependency(query, 0, BB);
+ if (localDep != NonLocal) {
+ resp.insert(std::make_pair(BB, localDep));
+ continue;
+ }
+ }
+
+ 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 (inserted)
+ continue;
+ else if (!inserted && !predOnStack) {
+ resp.insert(std::make_pair(BB, None));
+ } else if (!inserted && predOnStack){
+ resp.insert(std::make_pair(BB, NonLocal));
+ }
+
+ stack.pop_back();
+ }
+}
+
+void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
+ DenseMap<BasicBlock*, Value*>& resp) {
+ Instruction* localDep = getDependency(query);
+ if (localDep != NonLocal) {
+ resp.insert(std::make_pair(query->getParent(), localDep));
+ return;
+ }
+
+ nonLocalHelper(query, query->getParent(), resp);
+}
+
/// getDependency - Return the instruction on which a memory operation
/// depends. The local paramter indicates if the query should only
/// evaluate dependencies within the same basic block.
Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
- bool local) {
- if (!local)
- assert(0 && "Non-local memory dependence is not yet supported.");
-
+ Instruction* start,
+ BasicBlock* block) {
// Start looking for dependencies with the queried inst
BasicBlock::iterator QI = query;
// If we have a _confirmed_ cached entry, return it
if (cachedResult.second)
return cachedResult.first;
- else if (cachedResult.first != NonLocal)
+ else if (cachedResult.first && cachedResult.first != NonLocal)
// If we have an unconfirmed cached entry, we can start our search from there
QI = cachedResult.first;
+ if (start)
+ QI = start;
+ else if (!start && block)
+ QI = block->end();
+
AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
TargetData& TD = getAnalysis<TargetData>();
Value* dependee = 0;
uint64_t dependeeSize = 0;
bool queryIsVolatile = false;
- if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
+ if (StoreInst* S = dyn_cast<StoreInst>(query)) {
dependee = S->getPointerOperand();
dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
queryIsVolatile = S->isVolatile();
- } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
+ } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
dependee = L->getPointerOperand();
dependeeSize = TD.getTypeSize(L->getType());
queryIsVolatile = L->isVolatile();
- } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
+ } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
dependee = V->getOperand(0);
dependeeSize = TD.getTypeSize(V->getType());
- } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
+ } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
dependee = F->getPointerOperand();
// FreeInsts erase the entire structure, not just a field
dependeeSize = ~0UL;
- } else if (CallSite::get(QI).getInstruction() != 0)
- return getCallSiteDependency(CallSite::get(QI));
+ } else if (CallSite::get(query).getInstruction() != 0)
+ return getCallSiteDependency(CallSite::get(query), start);
else if (isa<AllocationInst>(query))
return None;
else
return None;
- BasicBlock::iterator blockBegin = query->getParent()->begin();
+ BasicBlock::iterator blockBegin = block ? block->begin()
+ : query->getParent()->begin();
while (QI != blockBegin) {
--QI;
if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
// All volatile loads/stores depend on each other
if (queryIsVolatile && S->isVolatile()) {
- depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
- reverseDep.insert(std::make_pair(S, query));
+ if (!start || block) {
+ depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
+ reverseDep.insert(std::make_pair(S, query));
+ }
+
return S;
}
} else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
// All volatile loads/stores depend on each other
if (queryIsVolatile && L->isVolatile()) {
- depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
- reverseDep.insert(std::make_pair(L, query));
+ if (!start || block) {
+ depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
+ reverseDep.insert(std::make_pair(L, query));
+ }
+
return L;
}
} else if (AllocationInst* AI = dyn_cast<AllocationInst>(QI)) {
pointer = AI;
if (ConstantInt* C = dyn_cast<ConstantInt>(AI->getArraySize()))
- pointerSize = C->getZExtValue();
+ pointerSize = C->getZExtValue() * TD.getTypeSize(AI->getAllocatedType());
else
pointerSize = ~0UL;
} else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
// Call insts need special handling. Check is they can modify our pointer
if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) !=
AliasAnalysis::NoModRef) {
- depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
- reverseDep.insert(std::make_pair(QI, query));
+ if (!start || block) {
+ depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
+ reverseDep.insert(std::make_pair(QI, query));
+ }
+
return QI;
} else {
continue;
dependee, dependeeSize);
if (R != AliasAnalysis::NoAlias) {
- depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
- reverseDep.insert(std::make_pair(QI, query));
+ if (!start || block) {
+ depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
+ reverseDep.insert(std::make_pair(QI, query));
+ }
+
return QI;
}
}
}
// If we found nothing, return the non-local flag
- depGraphLocal.insert(std::make_pair(query,
- std::make_pair(NonLocal, true)));
- reverseDep.insert(std::make_pair(NonLocal, query));
+ if (!start || block) {
+ depGraphLocal.insert(std::make_pair(query,
+ std::make_pair(NonLocal, true)));
+ reverseDep.insert(std::make_pair(NonLocal, query));
+ }
return NonLocal;
}
void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
// Figure out the new dep for things that currently depend on rem
Instruction* newDep = NonLocal;
- if (depGraphLocal[rem].first != NonLocal) {
- // If we have dep info for rem, set them to it
- BasicBlock::iterator RI = depGraphLocal[rem].first;
- RI++;
- newDep = RI;
- } else if (depGraphLocal[rem].first == NonLocal &&
- depGraphLocal[rem].second ) {
- // If we have a confirmed non-local flag, use it
- newDep = NonLocal;
- } 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;
- }
- std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
- while (I->first == rem) {
- // Insert the new dependencies
- // Mark it as unconfirmed as long as it is not the non-local flag
- depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
- reverseDep.erase(I);
- I = reverseDep.find(rem);
+ 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 &&
+ 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 &&
+ depGraphEntry->second.second ) {
+ // If we have a confirmed non-local flag, use it
+ newDep = NonLocal;
+ } 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;
+ }
+
+ std::multimap<Instruction*, Instruction*>::iterator I = reverseDep.find(rem);
+ while (I != reverseDep.end() && I->first == rem) {
+ // Insert the new dependencies
+ // Mark it as unconfirmed as long as it is not the non-local flag
+ depGraphLocal[I->second] = std::make_pair(newDep, !newDep);
+ reverseDep.erase(I);
+ I = reverseDep.find(rem);
+ }
}
+
+ getAnalysis<AliasAnalysis>().deleteValue(rem);
}
projects / oota-llvm.git / blobdiff