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.cpp81
1 files changed, 23 insertions, 58 deletions
diff --git a/llvm/lib/Analysis/LoopAccessAnalysis.cpp b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
index 8d53a27..980f142 100644
--- a/llvm/lib/Analysis/LoopAccessAnalysis.cpp
+++ b/llvm/lib/Analysis/LoopAccessAnalysis.cpp
@@ -1937,6 +1937,27 @@ MemoryDepChecker::getDependenceDistanceStrideAndSize(
LLVM_DEBUG(dbgs() << "LAA: Distance for " << *AInst << " to " << *BInst
<< ": " << *Dist << "\n");
+ // Check if we can prove that Sink only accesses memory after Src's end or
+ // vice versa. At the moment this is limited to cases where either source or
+ // sink are loop invariant to avoid compile-time increases. This is not
+ // required for correctness.
+ if (SE.isLoopInvariant(Src, InnermostLoop) ||
+ SE.isLoopInvariant(Sink, InnermostLoop)) {
+ const auto &[SrcStart, SrcEnd] =
+ getStartAndEndForAccess(InnermostLoop, Src, ATy, PSE, PointerBounds);
+ const auto &[SinkStart, SinkEnd] =
+ getStartAndEndForAccess(InnermostLoop, Sink, BTy, PSE, PointerBounds);
+ if (!isa<SCEVCouldNotCompute>(SrcStart) &&
+ !isa<SCEVCouldNotCompute>(SrcEnd) &&
+ !isa<SCEVCouldNotCompute>(SinkStart) &&
+ !isa<SCEVCouldNotCompute>(SinkEnd)) {
+ if (SE.isKnownPredicate(CmpInst::ICMP_ULE, SrcEnd, SinkStart))
+ return MemoryDepChecker::Dependence::NoDep;
+ if (SE.isKnownPredicate(CmpInst::ICMP_ULE, SinkEnd, SrcStart))
+ return MemoryDepChecker::Dependence::NoDep;
+ }
+ }
+
// Need accesses with constant strides and the same direction for further
// dependence analysis. We don't want to vectorize "A[B[i]] += ..." and
// similar code or pointer arithmetic that could wrap in the address space.
@@ -1982,45 +2003,12 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
const MemAccessInfo &B, unsigned BIdx) {
assert(AIdx < BIdx && "Must pass arguments in program order");
- // Check if we can prove that Sink only accesses memory after Src's end or
- // vice versa. The helper is used to perform the checks only on the exit paths
- // where it helps to improve the analysis result.
- auto CheckCompletelyBeforeOrAfter = [&]() {
- auto *APtr = A.getPointer();
- auto *BPtr = B.getPointer();
-
- Type *ATy = getLoadStoreType(InstMap[AIdx]);
- Type *BTy = getLoadStoreType(InstMap[BIdx]);
-
- const SCEV *Src = PSE.getSCEV(APtr);
- const SCEV *Sink = PSE.getSCEV(BPtr);
-
- const auto &[SrcStart, SrcEnd] =
- getStartAndEndForAccess(InnermostLoop, Src, ATy, PSE, PointerBounds);
- if (isa<SCEVCouldNotCompute>(SrcStart) || isa<SCEVCouldNotCompute>(SrcEnd))
- return false;
-
- const auto &[SinkStart, SinkEnd] =
- getStartAndEndForAccess(InnermostLoop, Sink, BTy, PSE, PointerBounds);
- if (isa<SCEVCouldNotCompute>(SinkStart) ||
- isa<SCEVCouldNotCompute>(SinkEnd))
- return false;
-
- auto &SE = *PSE.getSE();
- return SE.isKnownPredicate(CmpInst::ICMP_ULE, SrcEnd, SinkStart) ||
- SE.isKnownPredicate(CmpInst::ICMP_ULE, SinkEnd, SrcStart);
- };
-
// Get the dependence distance, stride, type size and what access writes for
// the dependence between A and B.
auto Res =
getDependenceDistanceStrideAndSize(A, InstMap[AIdx], B, InstMap[BIdx]);
- if (std::holds_alternative<Dependence::DepType>(Res)) {
- if (std::get<Dependence::DepType>(Res) == Dependence::Unknown &&
- CheckCompletelyBeforeOrAfter())
- return Dependence::NoDep;
+ if (std::holds_alternative<Dependence::DepType>(Res))
return std::get<Dependence::DepType>(Res);
- }
auto &[Dist, StrideA, StrideB, TypeByteSize, AIsWrite, BIsWrite] =
std::get<DepDistanceStrideAndSizeInfo>(Res);
@@ -2029,9 +2017,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
std::optional<uint64_t> CommonStride =
StrideA == StrideB ? std::make_optional(StrideA) : std::nullopt;
if (isa<SCEVCouldNotCompute>(Dist)) {
- if (CheckCompletelyBeforeOrAfter())
- return Dependence::NoDep;
-
// TODO: Relax requirement that there is a common stride to retry with
// non-constant distance dependencies.
FoundNonConstantDistanceDependence |= CommonStride.has_value();
@@ -2083,8 +2068,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
// Write to the same location with the same size.
return Dependence::Forward;
}
- assert(!CheckCompletelyBeforeOrAfter() &&
- "unexpectedly proved no dependence");
LLVM_DEBUG(dbgs() << "LAA: possibly zero dependence difference but "
"different type sizes\n");
return Dependence::Unknown;
@@ -2106,8 +2089,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
// did not set it when strides were different but there is no inherent
// reason to.
FoundNonConstantDistanceDependence |= CommonStride.has_value();
- if (CheckCompletelyBeforeOrAfter())
- return Dependence::NoDep;
return Dependence::Unknown;
}
if (!HasSameSize ||
@@ -2127,9 +2108,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
// Below we only handle strictly positive distances.
if (MinDistance <= 0) {
FoundNonConstantDistanceDependence |= CommonStride.has_value();
- if (CheckCompletelyBeforeOrAfter())
- return Dependence::NoDep;
-
return Dependence::Unknown;
}
@@ -2146,18 +2124,13 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
}
if (!HasSameSize) {
- if (CheckCompletelyBeforeOrAfter())
- return Dependence::NoDep;
LLVM_DEBUG(dbgs() << "LAA: ReadWrite-Write positive dependency with "
"different type sizes\n");
return Dependence::Unknown;
}
- if (!CommonStride) {
- if (CheckCompletelyBeforeOrAfter())
- return Dependence::NoDep;
+ if (!CommonStride)
return Dependence::Unknown;
- }
// Bail out early if passed-in parameters make vectorization not feasible.
unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
@@ -2205,10 +2178,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
// dependence distance and the distance may be larger at runtime (and safe
// for vectorization). Classify it as Unknown, so we re-try with runtime
// checks.
- //
- if (CheckCompletelyBeforeOrAfter())
- return Dependence::NoDep;
-
return Dependence::Unknown;
}
LLVM_DEBUG(dbgs() << "LAA: Failure because of positive minimum distance "
@@ -2221,8 +2190,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
if (MinDistanceNeeded > MinDepDistBytes) {
LLVM_DEBUG(dbgs() << "LAA: Failure because it needs at least "
<< MinDistanceNeeded << " size in bytes\n");
- assert(!CheckCompletelyBeforeOrAfter() &&
- "unexpectedly proved no dependence");
return Dependence::Backward;
}
@@ -2270,8 +2237,6 @@ MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
// For non-constant distances, we checked the lower bound of the dependence
// distance and the distance may be larger at runtime (and safe for
// vectorization). Classify it as Unknown, so we re-try with runtime checks.
- assert(!CheckCompletelyBeforeOrAfter() &&
- "unexpectedly proved no dependence");
return Dependence::Unknown;
}
generated by cgit v1.1 at 2025-09-29 13:40:32 +0000