aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis/MemoryDependenceAnalysis.cpp')
-rw-r--r--llvm/lib/Analysis/MemoryDependenceAnalysis.cpp220
1 files changed, 93 insertions, 127 deletions
diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
index a97a56e25805..566eba5c54af 100644
--- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -23,7 +23,6 @@
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemoryLocation.h"
-#include "llvm/Analysis/OrderedBasicBlock.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/PhiValues.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
@@ -238,83 +237,6 @@ MemDepResult MemoryDependenceResults::getCallDependencyFrom(
return MemDepResult::getNonFuncLocal();
}
-unsigned MemoryDependenceResults::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()->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);
-
- // If the two pointers are not based on the same pointer, we can't tell that
- // they are related.
- if (LIBase != MemLocBase)
- return 0;
-
- // Okay, the two values are based on the same pointer, but returned as
- // no-alias. This happens when we have things like two byte loads at "P+1"
- // and "P+3". Check to see if increasing the size of the "LI" load up to its
- // alignment (or the largest native integer type) will allow us to load all
- // the bits required by MemLoc.
-
- // If MemLoc is before LI, then no widening of LI will help us out.
- if (MemLocOffs < LIOffs)
- return 0;
-
- // Get the alignment of the load in bytes. We assume that it is safe to load
- // any legal integer up to this size without a problem. For example, if we're
- // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can
- // widen it up to an i32 load. If it is known 2-byte aligned, we can widen it
- // to i16.
- unsigned LoadAlign = LI->getAlignment();
-
- int64_t MemLocEnd = MemLocOffs + MemLocSize;
-
- // If no amount of rounding up will let MemLoc fit into LI, then bail out.
- if (LIOffs + LoadAlign < MemLocEnd)
- return 0;
-
- // This is the size of the load to try. Start with the next larger power of
- // two.
- unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits() / 8U;
- NewLoadByteSize = NextPowerOf2(NewLoadByteSize);
-
- while (true) {
- // If this load size is bigger than our known alignment or would not fit
- // into a native integer register, then we fail.
- if (NewLoadByteSize > LoadAlign ||
- !DL.fitsInLegalInteger(NewLoadByteSize * 8))
- return 0;
-
- if (LIOffs + NewLoadByteSize > MemLocEnd &&
- (LI->getParent()->getParent()->hasFnAttribute(
- Attribute::SanitizeAddress) ||
- LI->getParent()->getParent()->hasFnAttribute(
- Attribute::SanitizeHWAddress)))
- // 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.
- return 0;
-
- // If a load of this width would include all of MemLoc, then we succeed.
- if (LIOffs + NewLoadByteSize >= MemLocEnd)
- return NewLoadByteSize;
-
- NewLoadByteSize <<= 1;
- }
-}
-
static bool isVolatile(Instruction *Inst) {
if (auto *LI = dyn_cast<LoadInst>(Inst))
return LI->isVolatile();
@@ -327,8 +249,7 @@ static bool isVolatile(Instruction *Inst) {
MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
- BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
- OrderedBasicBlock *OBB) {
+ BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
MemDepResult InvariantGroupDependency = MemDepResult::getUnknown();
if (QueryInst != nullptr) {
if (auto *LI = dyn_cast<LoadInst>(QueryInst)) {
@@ -339,7 +260,7 @@ MemDepResult MemoryDependenceResults::getPointerDependencyFrom(
}
}
MemDepResult SimpleDep = getSimplePointerDependencyFrom(
- MemLoc, isLoad, ScanIt, BB, QueryInst, Limit, OBB);
+ MemLoc, isLoad, ScanIt, BB, QueryInst, Limit);
if (SimpleDep.isDef())
return SimpleDep;
// Non-local invariant group dependency indicates there is non local Def
@@ -440,8 +361,7 @@ MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI,
MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt,
- BasicBlock *BB, Instruction *QueryInst, unsigned *Limit,
- OrderedBasicBlock *OBB) {
+ BasicBlock *BB, Instruction *QueryInst, unsigned *Limit) {
bool isInvariantLoad = false;
unsigned DefaultLimit = getDefaultBlockScanLimit();
@@ -488,15 +408,6 @@ MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
const DataLayout &DL = BB->getModule()->getDataLayout();
- // If the caller did not provide an ordered basic block,
- // create one 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 OBBTmp(BB);
- if (!OBB)
- OBB = &OBBTmp;
-
// Return "true" if and only if the instruction I is either a non-simple
// load or a non-simple store.
auto isNonSimpleLoadOrStore = [](Instruction *I) -> bool {
@@ -686,7 +597,7 @@ MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
ModRefInfo MR = AA.getModRefInfo(Inst, MemLoc);
// If necessary, perform additional analysis.
if (isModAndRefSet(MR))
- MR = AA.callCapturesBefore(Inst, MemLoc, &DT, OBB);
+ MR = AA.callCapturesBefore(Inst, MemLoc, &DT);
switch (clearMust(MR)) {
case ModRefInfo::NoModRef:
// If the call has no effect on the queried pointer, just ignore it.
@@ -712,8 +623,7 @@ MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
return MemDepResult::getNonFuncLocal();
}
-MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst,
- OrderedBasicBlock *OBB) {
+MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) {
Instruction *ScanPos = QueryInst;
// Check for a cached result
@@ -753,7 +663,7 @@ MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst,
LocalCache =
getPointerDependencyFrom(MemLoc, isLoad, ScanPos->getIterator(),
- QueryParent, QueryInst, nullptr, OBB);
+ QueryParent, QueryInst, nullptr);
} else if (auto *QueryCall = dyn_cast<CallBase>(QueryInst)) {
bool isReadOnly = AA.onlyReadsMemory(QueryCall);
LocalCache = getCallDependencyFrom(QueryCall, isReadOnly,
@@ -979,6 +889,11 @@ MemDepResult MemoryDependenceResults::GetNonLocalInfoForBlock(
Instruction *QueryInst, const MemoryLocation &Loc, bool isLoad,
BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
+ bool isInvariantLoad = false;
+
+ if (LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
+ isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
+
// Do a binary search to see if we already have an entry for this block in
// the cache set. If so, find it.
NonLocalDepInfo::iterator Entry = std::upper_bound(
@@ -990,6 +905,13 @@ MemDepResult MemoryDependenceResults::GetNonLocalInfoForBlock(
if (Entry != Cache->begin() + NumSortedEntries && Entry->getBB() == BB)
ExistingResult = &*Entry;
+ // Use cached result for invariant load only if there is no dependency for non
+ // invariant load. In this case invariant load can not have any dependency as
+ // well.
+ if (ExistingResult && isInvariantLoad &&
+ !ExistingResult->getResult().isNonFuncLocal())
+ ExistingResult = nullptr;
+
// If we have a cached entry, and it is non-dirty, use it as the value for
// this dependency.
if (ExistingResult && !ExistingResult->getResult().isDirty()) {
@@ -1018,6 +940,10 @@ MemDepResult MemoryDependenceResults::GetNonLocalInfoForBlock(
MemDepResult Dep =
getPointerDependencyFrom(Loc, isLoad, ScanPos, BB, QueryInst);
+ // Don't cache results for invariant load.
+ if (isInvariantLoad)
+ return Dep;
+
// If we had a dirty entry for the block, update it. Otherwise, just add
// a new entry.
if (ExistingResult)
@@ -1094,7 +1020,8 @@ bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
Instruction *QueryInst, const PHITransAddr &Pointer,
const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB,
SmallVectorImpl<NonLocalDepResult> &Result,
- DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock) {
+ DenseMap<BasicBlock *, Value *> &Visited, bool SkipFirstBlock,
+ bool IsIncomplete) {
// Look up the cached info for Pointer.
ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
@@ -1106,6 +1033,10 @@ bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
InitialNLPI.Size = Loc.Size;
InitialNLPI.AATags = Loc.AATags;
+ bool isInvariantLoad = false;
+ if (LoadInst *LI = dyn_cast_or_null<LoadInst>(QueryInst))
+ isInvariantLoad = LI->getMetadata(LLVMContext::MD_invariant_load);
+
// Get the NLPI for CacheKey, inserting one into the map if it doesn't
// already have one.
std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
@@ -1114,7 +1045,8 @@ bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
// If we already have a cache entry for this CacheKey, we may need to do some
// work to reconcile the cache entry and the current query.
- if (!Pair.second) {
+ // Invariant loads don't participate in caching. Thus no need to reconcile.
+ if (!isInvariantLoad && !Pair.second) {
if (CacheInfo->Size != Loc.Size) {
bool ThrowOutEverything;
if (CacheInfo->Size.hasValue() && Loc.Size.hasValue()) {
@@ -1138,12 +1070,16 @@ bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
if (Instruction *Inst = Entry.getResult().getInst())
RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
CacheInfo->NonLocalDeps.clear();
+ // The cache is cleared (in the above line) so we will have lost
+ // information about blocks we have already visited. We therefore must
+ // assume that the cache information is incomplete.
+ IsIncomplete = true;
} else {
// This query's Size is less than the cached one. Conservatively restart
// the query using the greater size.
return getNonLocalPointerDepFromBB(
QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
- StartBB, Result, Visited, SkipFirstBlock);
+ StartBB, Result, Visited, SkipFirstBlock, IsIncomplete);
}
}
@@ -1158,11 +1094,15 @@ bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
if (Instruction *Inst = Entry.getResult().getInst())
RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
CacheInfo->NonLocalDeps.clear();
+ // The cache is cleared (in the above line) so we will have lost
+ // information about blocks we have already visited. We therefore must
+ // assume that the cache information is incomplete.
+ IsIncomplete = true;
}
if (Loc.AATags)
return getNonLocalPointerDepFromBB(
QueryInst, Pointer, Loc.getWithoutAATags(), isLoad, StartBB, Result,
- Visited, SkipFirstBlock);
+ Visited, SkipFirstBlock, IsIncomplete);
}
}
@@ -1170,7 +1110,13 @@ bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
// If we have valid cached information for exactly the block we are
// investigating, just return it with no recomputation.
- if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
+ // Don't use cached information for invariant loads since it is valid for
+ // non-invariant loads only.
+ //
+ // Don't use cached information for invariant loads since it is valid for
+ // non-invariant loads only.
+ if (!IsIncomplete && !isInvariantLoad &&
+ CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
// We have a fully cached result for this query then we can just return the
// cached results and populate the visited set. However, we have to verify
// that we don't already have conflicting results for these blocks. Check
@@ -1207,13 +1153,18 @@ bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
}
// Otherwise, either this is a new block, a block with an invalid cache
- // pointer or one that we're about to invalidate by putting more info into it
- // than its valid cache info. If empty, the result will be valid cache info,
- // otherwise it isn't.
- if (Cache->empty())
- CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
- else
- CacheInfo->Pair = BBSkipFirstBlockPair();
+ // pointer or one that we're about to invalidate by putting more info into
+ // it than its valid cache info. If empty and not explicitly indicated as
+ // incomplete, the result will be valid cache info, otherwise it isn't.
+ //
+ // Invariant loads don't affect cache in any way thus no need to update
+ // CacheInfo as well.
+ if (!isInvariantLoad) {
+ if (!IsIncomplete && Cache->empty())
+ CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
+ else
+ CacheInfo->Pair = BBSkipFirstBlockPair();
+ }
SmallVector<BasicBlock *, 32> Worklist;
Worklist.push_back(StartBB);
@@ -1454,22 +1405,27 @@ bool MemoryDependenceResults::getNonLocalPointerDepFromBB(
if (SkipFirstBlock)
return false;
- bool foundBlock = false;
- for (NonLocalDepEntry &I : llvm::reverse(*Cache)) {
- if (I.getBB() != BB)
- continue;
+ // Results of invariant loads are not cached thus no need to update cached
+ // information.
+ if (!isInvariantLoad) {
+ for (NonLocalDepEntry &I : llvm::reverse(*Cache)) {
+ if (I.getBB() != BB)
+ continue;
- assert((GotWorklistLimit || I.getResult().isNonLocal() ||
- !DT.isReachableFromEntry(BB)) &&
- "Should only be here with transparent block");
- foundBlock = true;
- I.setResult(MemDepResult::getUnknown());
- Result.push_back(
- NonLocalDepResult(I.getBB(), I.getResult(), Pointer.getAddr()));
- break;
+ assert((GotWorklistLimit || I.getResult().isNonLocal() ||
+ !DT.isReachableFromEntry(BB)) &&
+ "Should only be here with transparent block");
+
+ I.setResult(MemDepResult::getUnknown());
+
+
+ break;
+ }
}
- (void)foundBlock; (void)GotWorklistLimit;
- assert((foundBlock || GotWorklistLimit) && "Current block not in cache?");
+ (void)GotWorklistLimit;
+ // Go ahead and report unknown dependence.
+ Result.push_back(
+ NonLocalDepResult(BB, MemDepResult::getUnknown(), Pointer.getAddr()));
}
// Okay, we're done now. If we added new values to the cache, re-sort it.
@@ -1562,15 +1518,25 @@ void MemoryDependenceResults::removeInstruction(Instruction *RemInst) {
LocalDeps.erase(LocalDepEntry);
}
- // If we have any cached pointer dependencies on this instruction, remove
- // them. If the instruction has non-pointer type, then it can't be a pointer
- // base.
+ // If we have any cached dependencies on this instruction, remove
+ // them.
- // Remove it from both the load info and the store info. The instruction
- // can't be in either of these maps if it is non-pointer.
+ // If the instruction is a pointer, remove it from both the load info and the
+ // store info.
if (RemInst->getType()->isPointerTy()) {
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
+ } else {
+ // Otherwise, if the instructions is in the map directly, it must be a load.
+ // Remove it.
+ auto toRemoveIt = NonLocalDefsCache.find(RemInst);
+ if (toRemoveIt != NonLocalDefsCache.end()) {
+ assert(isa<LoadInst>(RemInst) &&
+ "only load instructions should be added directly");
+ const Instruction *DepV = toRemoveIt->second.getResult().getInst();
+ ReverseNonLocalDefsCache.find(DepV)->second.erase(RemInst);
+ NonLocalDefsCache.erase(toRemoveIt);
+ }
}
// Loop over all of the things that depend on the instruction we're removing.
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-08 06:27:40 +0000