aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/LoopAccessAnalysis.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis/LoopAccessAnalysis.cpp')
-rw-r--r--llvm/lib/Analysis/LoopAccessAnalysis.cpp95
1 files changed, 74 insertions, 21 deletions
diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index a239928ecf38..f9bd7167317f 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -142,13 +142,12 @@ Value *llvm::stripIntegerCast(Value *V) {
const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
const ValueToValueMap &PtrToStride,
- Value *Ptr, Value *OrigPtr) {
+ Value *Ptr) {
const SCEV *OrigSCEV = PSE.getSCEV(Ptr);
// If there is an entry in the map return the SCEV of the pointer with the
// symbolic stride replaced by one.
- ValueToValueMap::const_iterator SI =
- PtrToStride.find(OrigPtr ? OrigPtr : Ptr);
+ ValueToValueMap::const_iterator SI = PtrToStride.find(Ptr);
if (SI == PtrToStride.end())
// For a non-symbolic stride, just return the original expression.
return OrigSCEV;
@@ -659,7 +658,8 @@ static bool isNoWrap(PredicatedScalarEvolution &PSE,
if (PSE.getSE()->isLoopInvariant(PtrScev, L))
return true;
- int64_t Stride = getPtrStride(PSE, Ptr, L, Strides);
+ Type *AccessTy = Ptr->getType()->getPointerElementType();
+ int64_t Stride = getPtrStride(PSE, AccessTy, Ptr, L, Strides);
if (Stride == 1 || PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW))
return true;
@@ -1026,15 +1026,17 @@ static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR,
}
/// Check whether the access through \p Ptr has a constant stride.
-int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr,
- const Loop *Lp, const ValueToValueMap &StridesMap,
- bool Assume, bool ShouldCheckWrap) {
+int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
+ Value *Ptr, const Loop *Lp,
+ const ValueToValueMap &StridesMap, bool Assume,
+ bool ShouldCheckWrap) {
Type *Ty = Ptr->getType();
assert(Ty->isPointerTy() && "Unexpected non-ptr");
+ unsigned AddrSpace = Ty->getPointerAddressSpace();
- // Make sure that the pointer does not point to aggregate types.
- auto *PtrTy = cast<PointerType>(Ty);
- if (PtrTy->getElementType()->isAggregateType()) {
+ // Make sure we're not accessing an aggregate type.
+ // TODO: Why? This doesn't make any sense.
+ if (AccessTy->isAggregateType()) {
LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type"
<< *Ptr << "\n");
return 0;
@@ -1071,8 +1073,7 @@ int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr,
PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW) ||
isNoWrapAddRec(Ptr, AR, PSE, Lp);
if (!IsNoWrapAddRec && !IsInBoundsGEP &&
- NullPointerIsDefined(Lp->getHeader()->getParent(),
- PtrTy->getAddressSpace())) {
+ NullPointerIsDefined(Lp->getHeader()->getParent(), AddrSpace)) {
if (Assume) {
PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
IsNoWrapAddRec = true;
@@ -1100,7 +1101,7 @@ int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr,
}
auto &DL = Lp->getHeader()->getModule()->getDataLayout();
- int64_t Size = DL.getTypeAllocSize(PtrTy->getElementType());
+ int64_t Size = DL.getTypeAllocSize(AccessTy);
const APInt &APStepVal = C->getAPInt();
// Huge step value - give up.
@@ -1120,7 +1121,7 @@ int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr,
// zero we know that this won't happen without triggering undefined behavior.
if (!IsNoWrapAddRec && Stride != 1 && Stride != -1 &&
(IsInBoundsGEP || !NullPointerIsDefined(Lp->getHeader()->getParent(),
- PtrTy->getAddressSpace()))) {
+ AddrSpace))) {
if (Assume) {
// We can avoid this case by adding a run-time check.
LLVM_DEBUG(dbgs() << "LAA: Non unit strided pointer which is not either "
@@ -1262,6 +1263,47 @@ bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
return Diff && *Diff == 1;
}
+static void visitPointers(Value *StartPtr, const Loop &InnermostLoop,
+ function_ref<void(Value *)> AddPointer) {
+ SmallPtrSet<Value *, 8> Visited;
+ SmallVector<Value *> WorkList;
+ WorkList.push_back(StartPtr);
+
+ while (!WorkList.empty()) {
+ Value *Ptr = WorkList.pop_back_val();
+ if (!Visited.insert(Ptr).second)
+ continue;
+ auto *PN = dyn_cast<PHINode>(Ptr);
+ // SCEV does not look through non-header PHIs inside the loop. Such phis
+ // can be analyzed by adding separate accesses for each incoming pointer
+ // value.
+ if (PN && InnermostLoop.contains(PN->getParent()) &&
+ PN->getParent() != InnermostLoop.getHeader()) {
+ for (const Use &Inc : PN->incoming_values())
+ WorkList.push_back(Inc);
+ } else
+ AddPointer(Ptr);
+ }
+}
+
+void MemoryDepChecker::addAccess(StoreInst *SI) {
+ visitPointers(SI->getPointerOperand(), *InnermostLoop,
+ [this, SI](Value *Ptr) {
+ Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
+ InstMap.push_back(SI);
+ ++AccessIdx;
+ });
+}
+
+void MemoryDepChecker::addAccess(LoadInst *LI) {
+ visitPointers(LI->getPointerOperand(), *InnermostLoop,
+ [this, LI](Value *Ptr) {
+ Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
+ InstMap.push_back(LI);
+ ++AccessIdx;
+ });
+}
+
MemoryDepChecker::VectorizationSafetyStatus
MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
switch (Type) {
@@ -1478,6 +1520,8 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
Value *BPtr = B.getPointer();
bool AIsWrite = A.getInt();
bool BIsWrite = B.getInt();
+ Type *ATy = APtr->getType()->getPointerElementType();
+ Type *BTy = BPtr->getType()->getPointerElementType();
// Two reads are independent.
if (!AIsWrite && !BIsWrite)
@@ -1488,8 +1532,10 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
BPtr->getType()->getPointerAddressSpace())
return Dependence::Unknown;
- int64_t StrideAPtr = getPtrStride(PSE, APtr, InnermostLoop, Strides, true);
- int64_t StrideBPtr = getPtrStride(PSE, BPtr, InnermostLoop, Strides, true);
+ int64_t StrideAPtr =
+ getPtrStride(PSE, ATy, APtr, InnermostLoop, Strides, true);
+ int64_t StrideBPtr =
+ getPtrStride(PSE, BTy, BPtr, InnermostLoop, Strides, true);
const SCEV *Src = PSE.getSCEV(APtr);
const SCEV *Sink = PSE.getSCEV(BPtr);
@@ -1498,6 +1544,7 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
// dependence.
if (StrideAPtr < 0) {
std::swap(APtr, BPtr);
+ std::swap(ATy, BTy);
std::swap(Src, Sink);
std::swap(AIsWrite, BIsWrite);
std::swap(AIdx, BIdx);
@@ -1519,8 +1566,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
return Dependence::Unknown;
}
- Type *ATy = APtr->getType()->getPointerElementType();
- Type *BTy = BPtr->getType()->getPointerElementType();
auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
uint64_t TypeByteSize = DL.getTypeAllocSize(ATy);
uint64_t Stride = std::abs(StrideAPtr);
@@ -1958,7 +2003,11 @@ void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
if (blockNeedsPredication(ST->getParent(), TheLoop, DT))
Loc.AATags.TBAA = nullptr;
- Accesses.addStore(Loc);
+ visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop,
+ [&Accesses, Loc](Value *Ptr) {
+ MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
+ Accesses.addStore(NewLoc);
+ });
}
}
@@ -1982,7 +2031,7 @@ void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
// words may be written to the same address.
bool IsReadOnlyPtr = false;
if (Seen.insert(Ptr).second ||
- !getPtrStride(*PSE, Ptr, TheLoop, SymbolicStrides)) {
+ !getPtrStride(*PSE, LD->getType(), Ptr, TheLoop, SymbolicStrides)) {
++NumReads;
IsReadOnlyPtr = true;
}
@@ -2002,7 +2051,11 @@ void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
if (blockNeedsPredication(LD->getParent(), TheLoop, DT))
Loc.AATags.TBAA = nullptr;
- Accesses.addLoad(Loc, IsReadOnlyPtr);
+ visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop,
+ [&Accesses, Loc, IsReadOnlyPtr](Value *Ptr) {
+ MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
+ Accesses.addLoad(NewLoc, IsReadOnlyPtr);
+ });
}
// If we write (or read-write) to a single destination and there are no
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-12 01:28:25 +0000