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.cpp71
1 files changed, 57 insertions, 14 deletions
diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index 3d1edd5f..6803960 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -717,6 +717,11 @@ public:
MemAccessInfoList &getDependenciesToCheck() { return CheckDeps; }
+ const DenseMap<Value *, SmallVector<const Value *, 16>> &
+ getUnderlyingObjects() {
+ return UnderlyingObjects;
+ }
+
private:
typedef MapVector<MemAccessInfo, SmallSetVector<Type *, 1>> PtrAccessMap;
@@ -762,6 +767,8 @@ private:
/// The SCEV predicate containing all the SCEV-related assumptions.
PredicatedScalarEvolution &PSE;
+
+ DenseMap<Value *, SmallVector<const Value *, 16>> UnderlyingObjects;
};
} // end anonymous namespace
@@ -1116,7 +1123,6 @@ bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
for (const auto &A : AS) {
Value *Ptr = A.getValue();
bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
-
if (IsWrite)
++NumWritePtrChecks;
else
@@ -1331,10 +1337,12 @@ void AccessAnalysis::processMemAccesses() {
typedef SmallVector<const Value *, 16> ValueVector;
ValueVector TempObjects;
- getUnderlyingObjects(Ptr, TempObjects, LI);
+ UnderlyingObjects[Ptr] = {};
+ SmallVector<const Value *, 16> &UOs = UnderlyingObjects[Ptr];
+ ::getUnderlyingObjects(Ptr, UOs, LI);
LLVM_DEBUG(dbgs()
<< "Underlying objects for pointer " << *Ptr << "\n");
- for (const Value *UnderlyingObj : TempObjects) {
+ for (const Value *UnderlyingObj : UOs) {
// nullptr never alias, don't join sets for pointer that have "null"
// in their UnderlyingObjects list.
if (isa<ConstantPointerNull>(UnderlyingObj) &&
@@ -1662,6 +1670,7 @@ MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
case ForwardButPreventsForwarding:
case Backward:
case BackwardVectorizableButPreventsForwarding:
+ case IndirectUnsafe:
return VectorizationSafetyStatus::Unsafe;
}
llvm_unreachable("unexpected DepType!");
@@ -1673,6 +1682,7 @@ bool MemoryDepChecker::Dependence::isBackward() const {
case Forward:
case ForwardButPreventsForwarding:
case Unknown:
+ case IndirectUnsafe:
return false;
case BackwardVectorizable:
@@ -1698,6 +1708,7 @@ bool MemoryDepChecker::Dependence::isForward() const {
case BackwardVectorizable:
case Backward:
case BackwardVectorizableButPreventsForwarding:
+ case IndirectUnsafe:
return false;
}
llvm_unreachable("unexpected DepType!");
@@ -1855,10 +1866,21 @@ static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride,
return ScaledDist % Stride;
}
-MemoryDepChecker::Dependence::DepType
-MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
- const MemAccessInfo &B, unsigned BIdx,
- const DenseMap<Value *, const SCEV *> &Strides) {
+/// Returns true if any of the underlying objects has a loop varying address,
+/// i.e. may change in \p L.
+static bool
+isLoopVariantIndirectAddress(ArrayRef<const Value *> UnderlyingObjects,
+ ScalarEvolution &SE, const Loop *L) {
+ return any_of(UnderlyingObjects, [&SE, L](const Value *UO) {
+ return !SE.isLoopInvariant(SE.getSCEV(const_cast<Value *>(UO)), L);
+ });
+}
+
+MemoryDepChecker::Dependence::DepType MemoryDepChecker::isDependent(
+ const MemAccessInfo &A, unsigned AIdx, const MemAccessInfo &B,
+ unsigned BIdx, const DenseMap<Value *, const SCEV *> &Strides,
+ const DenseMap<Value *, SmallVector<const Value *, 16>>
+ &UnderlyingObjects) {
assert (AIdx < BIdx && "Must pass arguments in program order");
auto [APtr, AIsWrite] = A;
@@ -1902,6 +1924,14 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
LLVM_DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
<< *InstMap[BIdx] << ": " << *Dist << "\n");
+ // Needs accesses where the addresses of the accessed underlying objects do
+ // not change within the loop.
+ if (isLoopVariantIndirectAddress(UnderlyingObjects.find(APtr)->second, SE,
+ InnermostLoop) ||
+ isLoopVariantIndirectAddress(UnderlyingObjects.find(BPtr)->second, SE,
+ InnermostLoop))
+ return Dependence::IndirectUnsafe;
+
// Need accesses with constant stride. We don't want to vectorize
// "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
// the address space.
@@ -2064,9 +2094,11 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
return Dependence::BackwardVectorizable;
}
-bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
- MemAccessInfoList &CheckDeps,
- const DenseMap<Value *, const SCEV *> &Strides) {
+bool MemoryDepChecker::areDepsSafe(
+ DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
+ const DenseMap<Value *, const SCEV *> &Strides,
+ const DenseMap<Value *, SmallVector<const Value *, 16>>
+ &UnderlyingObjects) {
MinDepDistBytes = -1;
SmallPtrSet<MemAccessInfo, 8> Visited;
@@ -2110,7 +2142,8 @@ bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
std::swap(A, B);
Dependence::DepType Type =
- isDependent(*A.first, A.second, *B.first, B.second, Strides);
+ isDependent(*A.first, A.second, *B.first, B.second, Strides,
+ UnderlyingObjects);
mergeInStatus(Dependence::isSafeForVectorization(Type));
// Gather dependences unless we accumulated MaxDependences
@@ -2154,8 +2187,14 @@ MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
}
const char *MemoryDepChecker::Dependence::DepName[] = {
- "NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward",
- "BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"};
+ "NoDep",
+ "Unknown",
+ "IndidrectUnsafe",
+ "Forward",
+ "ForwardButPreventsForwarding",
+ "Backward",
+ "BackwardVectorizable",
+ "BackwardVectorizableButPreventsForwarding"};
void MemoryDepChecker::Dependence::print(
raw_ostream &OS, unsigned Depth,
@@ -2456,7 +2495,8 @@ void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
if (Accesses.isDependencyCheckNeeded()) {
LLVM_DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
CanVecMem = DepChecker->areDepsSafe(
- DependentAccesses, Accesses.getDependenciesToCheck(), SymbolicStrides);
+ DependentAccesses, Accesses.getDependenciesToCheck(), SymbolicStrides,
+ Accesses.getUnderlyingObjects());
if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) {
LLVM_DEBUG(dbgs() << "LAA: Retrying with memory checks\n");
@@ -2554,6 +2594,9 @@ void LoopAccessInfo::emitUnsafeDependenceRemark() {
R << "\nBackward loop carried data dependence that prevents "
"store-to-load forwarding.";
break;
+ case MemoryDepChecker::Dependence::IndirectUnsafe:
+ R << "\nUnsafe indirect dependence.";
+ break;
case MemoryDepChecker::Dependence::Unknown:
R << "\nUnknown data dependence.";
break;
generated by cgit v1.1 at 2025-09-29 09:56:44 +0000