diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp')
| -rw-r--r-- | contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp | 204 |
1 files changed, 97 insertions, 107 deletions
diff --git a/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp index c505aa4..255bae6 100644 --- a/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -65,7 +65,7 @@ INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep", "Memory Dependence Analysis", false, true) MemoryDependenceAnalysis::MemoryDependenceAnalysis() - : FunctionPass(ID), PredCache() { + : FunctionPass(ID) { initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry()); } MemoryDependenceAnalysis::~MemoryDependenceAnalysis() { @@ -79,11 +79,9 @@ void MemoryDependenceAnalysis::releaseMemory() { 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 { @@ -95,13 +93,9 @@ 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; } @@ -130,11 +124,11 @@ AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, AliasAnalysis *AA) { if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) { if (LI->isUnordered()) { - Loc = AA->getLocation(LI); + Loc = MemoryLocation::get(LI); return AliasAnalysis::Ref; } if (LI->getOrdering() == Monotonic) { - Loc = AA->getLocation(LI); + Loc = MemoryLocation::get(LI); return AliasAnalysis::ModRef; } Loc = AliasAnalysis::Location(); @@ -143,11 +137,11 @@ AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { if (SI->isUnordered()) { - Loc = AA->getLocation(SI); + Loc = MemoryLocation::get(SI); return AliasAnalysis::Mod; } if (SI->getOrdering() == Monotonic) { - Loc = AA->getLocation(SI); + Loc = MemoryLocation::get(SI); return AliasAnalysis::ModRef; } Loc = AliasAnalysis::Location(); @@ -155,7 +149,7 @@ AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, } if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) { - Loc = AA->getLocation(V); + Loc = MemoryLocation::get(V); return AliasAnalysis::ModRef; } @@ -227,7 +221,7 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, 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. @@ -265,22 +259,17 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, /// /// 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; } @@ -291,23 +280,23 @@ isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc, /// 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. @@ -346,9 +335,9 @@ getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, !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. @@ -362,6 +351,17 @@ getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, } } +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 @@ -405,14 +405,19 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // 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; @@ -448,14 +453,28 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // 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); @@ -465,19 +484,9 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, } 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); + AliasAnalysis::Location LoadLoc = MemoryLocation::get(LI); // If we found a pointer, check if it could be the same as our pointer. AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc); @@ -490,12 +499,12 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // 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; } @@ -534,12 +543,12 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, 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); @@ -549,9 +558,6 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, } else if (QueryInst->mayReadOrWriteMemory()) { return MemDepResult::getClobber(SI); } - - if (HasSeenAcquire && isAtLeastRelease(SI->getOrdering())) - return MemDepResult::getClobber(SI); } // FIXME: this is overly conservative. @@ -569,7 +575,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // Ok, this store might clobber the query pointer. Check to see if it is // a must alias: in this case, we want to return this as a def. - AliasAnalysis::Location StoreLoc = AA->getLocation(SI); + AliasAnalysis::Location StoreLoc = MemoryLocation::get(SI); // If we found a pointer, check if it could be the same as our pointer. AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc); @@ -597,6 +603,8 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, 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); @@ -607,6 +615,9 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, 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. @@ -757,8 +768,8 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { } 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; } @@ -843,8 +854,8 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { // 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); } } @@ -861,23 +872,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { 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 = MemoryLocation::get(QueryInst); bool isLoad = isa<LoadInst>(QueryInst); BasicBlock *FromBB = QueryInst->getParent(); assert(FromBB); @@ -890,14 +885,7 @@ getNonLocalPointerDependency(Instruction *QueryInst, // 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 @@ -915,8 +903,7 @@ getNonLocalPointerDependency(Instruction *QueryInst, 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 @@ -924,7 +911,7 @@ getNonLocalPointerDependency(Instruction *QueryInst, // a block with multiple different pointers. This can happen during PHI // translation. DenseMap<BasicBlock*, Value*> Visited; - if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB, + if (!getNonLocalPointerDepFromBB(QueryInst, Address, Loc, isLoad, FromBB, Result, Visited, true)) return; Result.clear(); @@ -938,7 +925,8 @@ getNonLocalPointerDependency(Instruction *QueryInst, /// lookup (which may use dirty cache info if available). If we do a lookup, /// add the result to the cache. MemDepResult MemoryDependenceAnalysis:: -GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, +GetNonLocalInfoForBlock(Instruction *QueryInst, + const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries) { @@ -979,7 +967,8 @@ GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, } // Scan the block for the dependency. - MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB); + MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB, + QueryInst); // If we had a dirty entry for the block, update it. Otherwise, just add // a new entry. @@ -1052,7 +1041,8 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, /// not compute dependence information for some reason. This should be treated /// as a clobber dependence on the first instruction in the predecessor block. bool MemoryDependenceAnalysis:: -getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, +getNonLocalPointerDepFromBB(Instruction *QueryInst, + const PHITransAddr &Pointer, const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *StartBB, SmallVectorImpl<NonLocalDepResult> &Result, @@ -1091,7 +1081,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, } else if (CacheInfo->Size > Loc.Size) { // This query's Size is less than the cached one. Conservatively restart // the query using the greater size. - return getNonLocalPointerDepFromBB(Pointer, + return getNonLocalPointerDepFromBB(QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad, StartBB, Result, Visited, SkipFirstBlock); @@ -1111,7 +1101,8 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, CacheInfo->NonLocalDeps.clear(); } if (Loc.AATags) - return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutAATags(), + return getNonLocalPointerDepFromBB(QueryInst, + Pointer, Loc.getWithoutAATags(), isLoad, StartBB, Result, Visited, SkipFirstBlock); } @@ -1214,7 +1205,8 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // Get the dependency info for Pointer in BB. If we have cached // information, we will use it, otherwise we compute it. DEBUG(AssertSorted(*Cache, NumSortedEntries)); - MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache, + MemDepResult Dep = GetNonLocalInfoForBlock(QueryInst, + Loc, isLoad, BB, Cache, NumSortedEntries); // If we got a Def or Clobber, add this to the list of results. @@ -1238,13 +1230,13 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, 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; } @@ -1280,15 +1272,13 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, 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 // not translatable, in which case the getAddr() returns null. PHITransAddr &PredPointer = PredList.back().second; - PredPointer.PHITranslateValue(BB, Pred, nullptr); - + PredPointer.PHITranslateValue(BB, Pred, DT, /*MustDominate=*/false); Value *PredPtrVal = PredPointer.getAddr(); // Check to see if we have already visited this pred block with another @@ -1348,7 +1338,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // result conflicted with the Visited list; we have to conservatively // assume it is unknown, but this also does not block PRE of the load. if (!CanTranslate || - getNonLocalPointerDepFromBB(PredPointer, + getNonLocalPointerDepFromBB(QueryInst, PredPointer, Loc.getWithNewPtr(PredPtrVal), isLoad, Pred, Result, Visited)) { @@ -1471,7 +1461,7 @@ void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) { /// 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, |
