#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;
}
+bool MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
+ BasicBlock* block,
+ DenseMap<BasicBlock*, Value*>& resp,
+ SmallPtrSet<BasicBlock*, 4>& visited) {
+ if (resp.count(block))
+ return resp[block] != None;
+
+ Instruction* localDep = getDependency(query, 0, block);
+ if (localDep != NonLocal) {
+ resp.insert(std::make_pair(block, localDep));
+ return true;
+ }
+
+ visited.insert(block);
+
+ bool inserted = false;
+ for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
+ PI != PE; ++PI)
+ if (!visited.count(*PI))
+ inserted |= nonLocalHelper(query, *PI, resp, visited);
+
+ visited.erase(block);
+
+ if (!inserted)
+ resp.insert(std::make_pair(block, None));
+
+ return inserted;
+}
+
+bool MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
+ DenseMap<BasicBlock*, Value*>& resp) {
+ Instruction* localDep = getDependency(query);
+ if (localDep != NonLocal) {
+ resp.insert(std::make_pair(query->getParent(), localDep));
+ return true;
+ }
+
+ bool inserted = false;
+ SmallPtrSet<BasicBlock*, 4> visited;
+ visited.insert(query->getParent());
+
+ BasicBlock* parent = query->getParent();
+ for (pred_iterator PI = pred_begin(parent), PE = pred_end(parent);
+ PI != PE; ++PI) {
+ if (!visited.count(*PI))
+ inserted |= nonLocalHelper(query, *PI, resp, visited);
+ }
+
+ if (!inserted)
+ resp.insert(std::make_pair(query->getParent(), None));
+
+ return inserted;
+}
+
/// 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 (depGraphLocal[rem].first != NonLocal &&
+ depGraphLocal[rem].second) {
// If we have dep info for rem, set them to it
BasicBlock::iterator RI = depGraphLocal[rem].first;
RI++;
reverseDep.erase(I);
I = reverseDep.find(rem);
}
+
+ getAnalysis<AliasAnalysis>().deleteValue(rem);
}
projects / oota-llvm.git / blobdiff