"Memory Dependence Analysis", false, true)
MemoryDependenceAnalysis::MemoryDependenceAnalysis()
- : FunctionPass(ID), PredCache() {
+ : FunctionPass(ID) {
initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry());
}
MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
ReverseLocalDeps.clear();
ReverseNonLocalDeps.clear();
ReverseNonLocalPtrDeps.clear();
- PredCache->clear();
+ PredCache.clear();
}
-
-
/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
///
void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
bool MemoryDependenceAnalysis::runOnFunction(Function &F) {
AA = &getAnalysis<AliasAnalysis>();
AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
- DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
- DL = DLP ? &DLP->getDataLayout() : nullptr;
DominatorTreeWrapperPass *DTWP =
getAnalysisIfAvailable<DominatorTreeWrapperPass>();
DT = DTWP ? &DTWP->getDomTree() : nullptr;
- if (!PredCache)
- PredCache.reset(new PredIteratorCache());
return false;
}
continue;
}
- if (CallSite InstCS = cast<Value>(Inst)) {
+ if (auto InstCS = CallSite(Inst)) {
// Debug intrinsics don't cause dependences.
if (isa<DbgInfoIntrinsic>(Inst)) continue;
// If these two calls do not interfere, look past it.
///
/// MemLocBase, MemLocOffset are lazily computed here the first time the
/// base/offs of memloc is needed.
-static bool
-isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc,
- const Value *&MemLocBase,
- int64_t &MemLocOffs,
- const LoadInst *LI,
- const DataLayout *DL) {
- // If we have no target data, we can't do this.
- if (!DL) return false;
+static bool isLoadLoadClobberIfExtendedToFullWidth(
+ const AliasAnalysis::Location &MemLoc, const Value *&MemLocBase,
+ int64_t &MemLocOffs, const LoadInst *LI) {
+ const DataLayout &DL = LI->getModule()->getDataLayout();
// If we haven't already computed the base/offset of MemLoc, do so now.
if (!MemLocBase)
MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, DL);
- unsigned Size = MemoryDependenceAnalysis::
- getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size,
- LI, *DL);
+ unsigned Size = MemoryDependenceAnalysis::getLoadLoadClobberFullWidthSize(
+ MemLocBase, MemLocOffs, MemLoc.Size, LI);
return Size != 0;
}
/// 2) safe for the target, and 3) would provide the specified memory
/// location value, then this function returns the size in bytes of the
/// load width to use. If not, this returns zero.
-unsigned MemoryDependenceAnalysis::
-getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs,
- unsigned MemLocSize, const LoadInst *LI,
- const DataLayout &DL) {
+unsigned MemoryDependenceAnalysis::getLoadLoadClobberFullWidthSize(
+ const Value *MemLocBase, int64_t MemLocOffs, unsigned MemLocSize,
+ const LoadInst *LI) {
// We can only extend simple integer loads.
if (!isa<IntegerType>(LI->getType()) || !LI->isSimple()) return 0;
// Load widening is hostile to ThreadSanitizer: it may cause false positives
// or make the reports more cryptic (access sizes are wrong).
- if (LI->getParent()->getParent()->getAttributes().
- hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeThread))
+ if (LI->getParent()->getParent()->hasFnAttribute(Attribute::SanitizeThread))
return 0;
+ const DataLayout &DL = LI->getModule()->getDataLayout();
+
// Get the base of this load.
int64_t LIOffs = 0;
const Value *LIBase =
- GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, &DL);
+ GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, DL);
// If the two pointers are not based on the same pointer, we can't tell that
// they are related.
!DL.fitsInLegalInteger(NewLoadByteSize*8))
return 0;
- if (LIOffs+NewLoadByteSize > MemLocEnd &&
- LI->getParent()->getParent()->getAttributes().
- hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeAddress))
+ if (LIOffs + NewLoadByteSize > MemLocEnd &&
+ LI->getParent()->getParent()->hasFnAttribute(
+ Attribute::SanitizeAddress))
// We will be reading past the location accessed by the original program.
// While this is safe in a regular build, Address Safety analysis tools
// may start reporting false warnings. So, don't do widening.
}
}
+static bool isVolatile(Instruction *Inst) {
+ if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
+ return LI->isVolatile();
+ else if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
+ return SI->isVolatile();
+ else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst))
+ return AI->isVolatile();
+ return false;
+}
+
+
/// getPointerDependencyFrom - Return the instruction on which a memory
/// location depends. If isLoad is true, this routine ignores may-aliases with
/// read-only operations. If isLoad is false, this routine ignores may-aliases
// by every program that can detect any optimisation of that kind: either
// it is racy (undefined) or there is a release followed by an acquire
// between the pair of accesses under consideration.
- bool HasSeenAcquire = false;
+ // If the load is invariant, we "know" that it doesn't alias *any* write. We
+ // do want to respect mustalias results since defs are useful for value
+ // forwarding, but any mayalias write can be assumed to be noalias.
+ // Arguably, this logic should be pushed inside AliasAnalysis itself.
if (isLoad && QueryInst) {
LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
isInvariantLoad = true;
}
+ const DataLayout &DL = BB->getModule()->getDataLayout();
+
// Walk backwards through the basic block, looking for dependencies.
while (ScanIt != BB->begin()) {
Instruction *Inst = --ScanIt;
// does not alias with when this atomic load indicates that another thread may
// be accessing the location.
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
+
+ // While volatile access cannot be eliminated, they do not have to clobber
+ // non-aliasing locations, as normal accesses, for example, can be safely
+ // reordered with volatile accesses.
+ if (LI->isVolatile()) {
+ if (!QueryInst)
+ // Original QueryInst *may* be volatile
+ return MemDepResult::getClobber(LI);
+ if (isVolatile(QueryInst))
+ // Ordering required if QueryInst is itself volatile
+ return MemDepResult::getClobber(LI);
+ // Otherwise, volatile doesn't imply any special ordering
+ }
+
// Atomic loads have complications involved.
// A Monotonic (or higher) load is OK if the query inst is itself not atomic.
- // An Acquire (or higher) load sets the HasSeenAcquire flag, so that any
- // release store will know to return getClobber.
// FIXME: This is overly conservative.
- if (!LI->isUnordered()) {
+ if (LI->isAtomic() && LI->getOrdering() > Unordered) {
if (!QueryInst)
return MemDepResult::getClobber(LI);
+ if (LI->getOrdering() != Monotonic)
+ return MemDepResult::getClobber(LI);
if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst)) {
if (!QueryLI->isSimple())
return MemDepResult::getClobber(LI);
} else if (QueryInst->mayReadOrWriteMemory()) {
return MemDepResult::getClobber(LI);
}
-
- if (isAtLeastAcquire(LI->getOrdering()))
- HasSeenAcquire = true;
}
- // FIXME: this is overly conservative.
- // While volatile access cannot be eliminated, they do not have to clobber
- // non-aliasing locations, as normal accesses can for example be reordered
- // with volatile accesses.
- if (LI->isVolatile())
- return MemDepResult::getClobber(LI);
-
AliasAnalysis::Location LoadLoc = AA->getLocation(LI);
// If we found a pointer, check if it could be the same as our pointer.
// location is 1 byte at P+1). If so, return it as a load/load
// clobber result, allowing the client to decide to widen the load if
// it wants to.
- if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType()))
- if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() &&
+ if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType())) {
+ if (LI->getAlignment() * 8 > ITy->getPrimitiveSizeInBits() &&
isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase,
- MemLocOffset, LI, DL))
+ MemLocOffset, LI))
return MemDepResult::getClobber(Inst);
-
+ }
continue;
}
if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
// Atomic stores have complications involved.
// A Monotonic store is OK if the query inst is itself not atomic.
- // A Release (or higher) store further requires that no acquire load
- // has been seen.
// FIXME: This is overly conservative.
if (!SI->isUnordered()) {
if (!QueryInst)
return MemDepResult::getClobber(SI);
+ if (SI->getOrdering() != Monotonic)
+ return MemDepResult::getClobber(SI);
if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst)) {
if (!QueryLI->isSimple())
return MemDepResult::getClobber(SI);
} else if (QueryInst->mayReadOrWriteMemory()) {
return MemDepResult::getClobber(SI);
}
-
- if (HasSeenAcquire && isAtLeastRelease(SI->getOrdering()))
- return MemDepResult::getClobber(SI);
}
// FIXME: this is overly conservative.
if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr))
return MemDepResult::getDef(Inst);
+ if (isInvariantLoad)
+ continue;
// Be conservative if the accessed pointer may alias the allocation.
if (AA->alias(Inst, AccessPtr) != AliasAnalysis::NoAlias)
return MemDepResult::getClobber(Inst);
continue;
}
+ if (isInvariantLoad)
+ continue;
+
// See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc);
// If necessary, perform additional analysis.
} else {
// Seed DirtyBlocks with each of the preds of QueryInst's block.
BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
- for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
- DirtyBlocks.push_back(*PI);
+ for (BasicBlock *Pred : PredCache.get(QueryBB))
+ DirtyBlocks.push_back(Pred);
++NumUncacheNonLocal;
}
// If the block *is* completely transparent to the load, we need to check
// the predecessors of this block. Add them to our worklist.
- for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI)
- DirtyBlocks.push_back(*PI);
+ for (BasicBlock *Pred : PredCache.get(DirtyBB))
+ DirtyBlocks.push_back(Pred);
}
}
void MemoryDependenceAnalysis::
getNonLocalPointerDependency(Instruction *QueryInst,
SmallVectorImpl<NonLocalDepResult> &Result) {
-
- auto getLocation = [](AliasAnalysis *AA, Instruction *Inst) {
- if (auto *I = dyn_cast<LoadInst>(Inst))
- return AA->getLocation(I);
- else if (auto *I = dyn_cast<StoreInst>(Inst))
- return AA->getLocation(I);
- else if (auto *I = dyn_cast<VAArgInst>(Inst))
- return AA->getLocation(I);
- else if (auto *I = dyn_cast<AtomicCmpXchgInst>(Inst))
- return AA->getLocation(I);
- else if (auto *I = dyn_cast<AtomicRMWInst>(Inst))
- return AA->getLocation(I);
- else
- llvm_unreachable("unsupported memory instruction");
- };
-
- const AliasAnalysis::Location Loc = getLocation(AA, QueryInst);
+ const AliasAnalysis::Location Loc = AA->getLocation(QueryInst);
bool isLoad = isa<LoadInst>(QueryInst);
BasicBlock *FromBB = QueryInst->getParent();
assert(FromBB);
// Doing so would require piping through the QueryInst all the way through.
// TODO: volatiles can't be elided, but they can be reordered with other
// non-volatile accesses.
- auto isVolatile = [](Instruction *Inst) {
- if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
- return LI->isVolatile();
- } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
- return SI->isVolatile();
- }
- return false;
- };
+
// We currently give up on any instruction which is ordered, but we do handle
// atomic instructions which are unordered.
// TODO: Handle ordered instructions
const_cast<Value *>(Loc.Ptr)));
return;
}
-
-
+ const DataLayout &DL = FromBB->getModule()->getDataLayout();
PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL, AC);
// This is the set of blocks we've inspected, and the pointer we consider in
if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
SkipFirstBlock = false;
SmallVector<BasicBlock*, 16> NewBlocks;
- for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
+ for (BasicBlock *Pred : PredCache.get(BB)) {
// Verify that we haven't looked at this block yet.
std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
- InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr()));
+ InsertRes = Visited.insert(std::make_pair(Pred, Pointer.getAddr()));
if (InsertRes.second) {
// First time we've looked at *PI.
- NewBlocks.push_back(*PI);
+ NewBlocks.push_back(Pred);
continue;
}
Cache = nullptr;
PredList.clear();
- for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
- BasicBlock *Pred = *PI;
+ for (BasicBlock *Pred : PredCache.get(BB)) {
PredList.push_back(std::make_pair(Pred, Pointer));
// Get the PHI translated pointer in this predecessor. This can fail if
/// This needs to be done when the CFG changes, e.g., due to splitting
/// critical edges.
void MemoryDependenceAnalysis::invalidateCachedPredecessors() {
- PredCache->clear();
+ PredCache.clear();
}
/// removeInstruction - Remove an instruction from the dependence analysis,
projects / oota-llvm.git / blobdiff