projects
/
oota-llvm.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
[PM/AA] Add missing static dependency edges from DSE and memdep to TLI.
[oota-llvm.git]
/
lib
/
Analysis
/
MemoryDependenceAnalysis.cpp
diff --git
a/lib/Analysis/MemoryDependenceAnalysis.cpp
b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 782a67bf72d523f0366ca8e6753ce8784228ea92..decba79b5c7ae7844616062444c6b5940c6a9eb3 100644
(file)
--- a/
lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/
lib/Analysis/MemoryDependenceAnalysis.cpp
@@
-22,7
+22,9
@@
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/PHITransAddr.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
@@
-49,7
+51,11
@@
STATISTIC(NumCacheCompleteNonLocalPtr,
"Number of block queries that were completely cached");
// Limit for the number of instructions to scan in a block.
"Number of block queries that were completely cached");
// Limit for the number of instructions to scan in a block.
-static const unsigned int BlockScanLimit = 100;
+
+static cl::opt<unsigned> BlockScanLimit(
+ "memdep-block-scan-limit", cl::Hidden, cl::init(100),
+ cl::desc("The number of instructions to scan in a block in memory "
+ "dependency analysis (default = 100)"));
// Limit on the number of memdep results to process.
static const unsigned int NumResultsLimit = 100;
// Limit on the number of memdep results to process.
static const unsigned int NumResultsLimit = 100;
@@
-59,8
+65,9
@@
char MemoryDependenceAnalysis::ID = 0;
// Register this pass...
INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
"Memory Dependence Analysis", false, true)
// Register this pass...
INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
"Memory Dependence Analysis", false, true)
-INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
"Memory Dependence Analysis", false, true)
INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
"Memory Dependence Analysis", false, true)
@@
-88,6
+95,7
@@
void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<AssumptionCacheTracker>();
AU.addRequiredTransitive<AliasAnalysis>();
AU.setPreservesAll();
AU.addRequired<AssumptionCacheTracker>();
AU.addRequiredTransitive<AliasAnalysis>();
+ AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
}
bool MemoryDependenceAnalysis::runOnFunction(Function &F) {
}
bool MemoryDependenceAnalysis::runOnFunction(Function &F) {
@@
-96,6
+104,7
@@
bool MemoryDependenceAnalysis::runOnFunction(Function &F) {
DominatorTreeWrapperPass *DTWP =
getAnalysisIfAvailable<DominatorTreeWrapperPass>();
DT = DTWP ? &DTWP->getDomTree() : nullptr;
DominatorTreeWrapperPass *DTWP =
getAnalysisIfAvailable<DominatorTreeWrapperPass>();
DT = DTWP ? &DTWP->getDomTree() : nullptr;
+ TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
return false;
}
return false;
}
@@
-118,43
+127,43
@@
static void RemoveFromReverseMap(DenseMap<Instruction*,
/// location, fill in Loc with the details, otherwise set Loc.Ptr to null.
/// Return a ModRefInfo value describing the general behavior of the
/// instruction.
/// location, fill in Loc with the details, otherwise set Loc.Ptr to null.
/// Return a ModRefInfo value describing the general behavior of the
/// instruction.
-static
AliasAnalysis::ModRefResult
-
GetLocation(const Instruction *Inst, MemoryLocation &Loc, AliasAnalysis *AA
) {
+static
ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc,
+
const TargetLibraryInfo &TLI
) {
if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
if (LI->isUnordered()) {
Loc = MemoryLocation::get(LI);
if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
if (LI->isUnordered()) {
Loc = MemoryLocation::get(LI);
- return
AliasAnalysis::
Ref;
+ return
MRI_
Ref;
}
if (LI->getOrdering() == Monotonic) {
Loc = MemoryLocation::get(LI);
}
if (LI->getOrdering() == Monotonic) {
Loc = MemoryLocation::get(LI);
- return
AliasAnalysis::
ModRef;
+ return
MRI_
ModRef;
}
Loc = MemoryLocation();
}
Loc = MemoryLocation();
- return
AliasAnalysis::
ModRef;
+ return
MRI_
ModRef;
}
if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
if (SI->isUnordered()) {
Loc = MemoryLocation::get(SI);
}
if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
if (SI->isUnordered()) {
Loc = MemoryLocation::get(SI);
- return
AliasAnalysis::
Mod;
+ return
MRI_
Mod;
}
if (SI->getOrdering() == Monotonic) {
Loc = MemoryLocation::get(SI);
}
if (SI->getOrdering() == Monotonic) {
Loc = MemoryLocation::get(SI);
- return
AliasAnalysis::
ModRef;
+ return
MRI_
ModRef;
}
Loc = MemoryLocation();
}
Loc = MemoryLocation();
- return
AliasAnalysis::
ModRef;
+ return
MRI_
ModRef;
}
if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
Loc = MemoryLocation::get(V);
}
if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
Loc = MemoryLocation::get(V);
- return
AliasAnalysis::
ModRef;
+ return
MRI_
ModRef;
}
}
- if (const CallInst *CI = isFreeCall(Inst,
AA->getTargetLibraryInfo()
)) {
+ if (const CallInst *CI = isFreeCall(Inst,
&TLI
)) {
// calls to free() deallocate the entire structure
Loc = MemoryLocation(CI->getArgOperand(0));
// calls to free() deallocate the entire structure
Loc = MemoryLocation(CI->getArgOperand(0));
- return
AliasAnalysis::
Mod;
+ return
MRI_
Mod;
}
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
}
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
@@
-170,7
+179,7
@@
GetLocation(const Instruction *Inst, MemoryLocation &Loc, AliasAnalysis *AA) {
cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(), AAInfo);
// These intrinsics don't really modify the memory, but returning Mod
// will allow them to be handled conservatively.
cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(), AAInfo);
// These intrinsics don't really modify the memory, but returning Mod
// will allow them to be handled conservatively.
- return
AliasAnalysis::
Mod;
+ return
MRI_
Mod;
case Intrinsic::invariant_end:
II->getAAMetadata(AAInfo);
Loc = MemoryLocation(
case Intrinsic::invariant_end:
II->getAAMetadata(AAInfo);
Loc = MemoryLocation(
@@
-178,7
+187,7
@@
GetLocation(const Instruction *Inst, MemoryLocation &Loc, AliasAnalysis *AA) {
cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(), AAInfo);
// These intrinsics don't really modify the memory, but returning Mod
// will allow them to be handled conservatively.
cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(), AAInfo);
// These intrinsics don't really modify the memory, but returning Mod
// will allow them to be handled conservatively.
- return
AliasAnalysis::
Mod;
+ return
MRI_
Mod;
default:
break;
}
default:
break;
}
@@
-186,10
+195,10
@@
GetLocation(const Instruction *Inst, MemoryLocation &Loc, AliasAnalysis *AA) {
// Otherwise, just do the coarse-grained thing that always works.
if (Inst->mayWriteToMemory())
// Otherwise, just do the coarse-grained thing that always works.
if (Inst->mayWriteToMemory())
- return
AliasAnalysis::
ModRef;
+ return
MRI_
ModRef;
if (Inst->mayReadFromMemory())
if (Inst->mayReadFromMemory())
- return
AliasAnalysis::
Ref;
- return
AliasAnalysis::
NoModRef;
+ return
MRI_
Ref;
+ return
MRI_
NoModRef;
}
/// getCallSiteDependencyFrom - Private helper for finding the local
}
/// getCallSiteDependencyFrom - Private helper for finding the local
@@
-211,10
+220,10
@@
getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
// If this inst is a memory op, get the pointer it accessed
MemoryLocation Loc;
// If this inst is a memory op, get the pointer it accessed
MemoryLocation Loc;
-
AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA
);
+
ModRefInfo MR = GetLocation(Inst, Loc, *TLI
);
if (Loc.Ptr) {
// A simple instruction.
if (Loc.Ptr) {
// A simple instruction.
- if (AA->getModRefInfo(CS, Loc) !=
AliasAnalysis::
NoModRef)
+ if (AA->getModRefInfo(CS, Loc) !=
MRI_
NoModRef)
return MemDepResult::getClobber(Inst);
continue;
}
return MemDepResult::getClobber(Inst);
continue;
}
@@
-224,10
+233,10
@@
getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
if (isa<DbgInfoIntrinsic>(Inst)) continue;
// If these two calls do not interfere, look past it.
switch (AA->getModRefInfo(CS, InstCS)) {
if (isa<DbgInfoIntrinsic>(Inst)) continue;
// If these two calls do not interfere, look past it.
switch (AA->getModRefInfo(CS, InstCS)) {
- case
AliasAnalysis::
NoModRef:
+ case
MRI_
NoModRef:
// If the two calls are the same, return InstCS as a Def, so that
// CS can be found redundant and eliminated.
// If the two calls are the same, return InstCS as a Def, so that
// CS can be found redundant and eliminated.
- if (isReadOnlyCall && !(MR &
AliasAnalysis::
Mod) &&
+ if (isReadOnlyCall && !(MR &
MRI_
Mod) &&
CS.getInstruction()->isIdenticalToWhenDefined(Inst))
return MemDepResult::getDef(Inst);
CS.getInstruction()->isIdenticalToWhenDefined(Inst))
return MemDepResult::getDef(Inst);
@@
-241,7
+250,7
@@
getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
// If we could not obtain a pointer for the instruction and the instruction
// touches memory then assume that this is a dependency.
// If we could not obtain a pointer for the instruction and the instruction
// touches memory then assume that this is a dependency.
- if (MR !=
AliasAnalysis::
NoModRef)
+ if (MR !=
MRI_
NoModRef)
return MemDepResult::getClobber(Inst);
}
return MemDepResult::getClobber(Inst);
}
@@
-416,6
+425,12
@@
MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom(
const DataLayout &DL = BB->getModule()->getDataLayout();
const DataLayout &DL = BB->getModule()->getDataLayout();
+ // Create a numbered basic block to lazily compute and cache instruction
+ // positions inside a BB. This is used to provide fast queries for relative
+ // position between two instructions in a BB and can be used by
+ // AliasAnalysis::callCapturesBefore.
+ OrderedBasicBlock OBB(BB);
+
// Walk backwards through the basic block, looking for dependencies.
while (ScanIt != BB->begin()) {
Instruction *Inst = --ScanIt;
// Walk backwards through the basic block, looking for dependencies.
while (ScanIt != BB->begin()) {
Instruction *Inst = --ScanIt;
@@
-567,7
+582,7
@@
MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom(
// If alias analysis can tell that this store is guaranteed to not modify
// the query pointer, ignore it. Use getModRefInfo to handle cases where
// the query pointer points to constant memory etc.
// If alias analysis can tell that this store is guaranteed to not modify
// the query pointer, ignore it. Use getModRefInfo to handle cases where
// the query pointer points to constant memory etc.
- if (AA->getModRefInfo(SI, MemLoc) ==
AliasAnalysis::
NoModRef)
+ if (AA->getModRefInfo(SI, MemLoc) ==
MRI_
NoModRef)
continue;
// Ok, this store might clobber the query pointer. Check to see if it is
continue;
// Ok, this store might clobber the query pointer. Check to see if it is
@@
-594,7
+609,6
@@
MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom(
// a subsequent bitcast of the malloc call result. There can be stores to
// the malloced memory between the malloc call and its bitcast uses, and we
// need to continue scanning until the malloc call.
// a subsequent bitcast of the malloc call result. There can be stores to
// the malloced memory between the malloc call and its bitcast uses, and we
// need to continue scanning until the malloc call.
- const TargetLibraryInfo *TLI = AA->getTargetLibraryInfo();
if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, TLI)) {
const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL);
if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, TLI)) {
const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL);
@@
-616,17
+630,17
@@
MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom(
continue;
// See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
continue;
// See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
-
AliasAnalysis::ModRefResult
MR = AA->getModRefInfo(Inst, MemLoc);
+
ModRefInfo
MR = AA->getModRefInfo(Inst, MemLoc);
// If necessary, perform additional analysis.
// If necessary, perform additional analysis.
- if (MR ==
AliasAnalysis::
ModRef)
- MR = AA->callCapturesBefore(Inst, MemLoc, DT);
+ if (MR ==
MRI_
ModRef)
+ MR = AA->callCapturesBefore(Inst, MemLoc, DT
, &OBB
);
switch (MR) {
switch (MR) {
- case
AliasAnalysis::
NoModRef:
+ case
MRI_
NoModRef:
// If the call has no effect on the queried pointer, just ignore it.
continue;
// If the call has no effect on the queried pointer, just ignore it.
continue;
- case
AliasAnalysis::
Mod:
+ case
MRI_
Mod:
return MemDepResult::getClobber(Inst);
return MemDepResult::getClobber(Inst);
- case
AliasAnalysis::
Ref:
+ case
MRI_
Ref:
// If the call is known to never store to the pointer, and if this is a
// load query, we can safely ignore it (scan past it).
if (isLoad)
// If the call is known to never store to the pointer, and if this is a
// load query, we can safely ignore it (scan past it).
if (isLoad)
@@
-677,10
+691,10
@@
MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
LocalCache = MemDepResult::getNonFuncLocal();
} else {
MemoryLocation MemLoc;
LocalCache = MemDepResult::getNonFuncLocal();
} else {
MemoryLocation MemLoc;
-
AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA
);
+
ModRefInfo MR = GetLocation(QueryInst, MemLoc, *TLI
);
if (MemLoc.Ptr) {
// If we can do a pointer scan, make it happen.
if (MemLoc.Ptr) {
// If we can do a pointer scan, make it happen.
- bool isLoad = !(MR &
AliasAnalysis::
Mod);
+ bool isLoad = !(MR &
MRI_
Mod);
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst))
isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst))
isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
@@
-1614,7
+1628,6
@@
void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
- AA->deleteValue(RemInst);
DEBUG(verifyRemoved(RemInst));
}
/// verifyRemoved - Verify that the specified instruction does not occur
DEBUG(verifyRemoved(RemInst));
}
/// verifyRemoved - Verify that the specified instruction does not occur