aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib
diff options
context:
space:
mode:
authorRyotaro Kasuga <kasuga.ryotaro@fujitsu.com>2025-08-08 10:58:13 +0900
committerGitHub <noreply@github.com>2025-08-08 10:58:13 +0900
commit05dd957cda663273ae0e5739656ffe701404f37c (patch)
treed892db99e3fe84474e3ed2afe4f7676d2a8a8d86 /llvm/lib
parent1458eb206fb652358b3ee7e75d95b52f3f4ac333 (diff)
downloadllvm-05dd957cda663273ae0e5739656ffe701404f37c.zip
llvm-05dd957cda663273ae0e5739656ffe701404f37c.tar.gz
llvm-05dd957cda663273ae0e5739656ffe701404f37c.tar.bz2
[DA] Fix the check between Subscript and Size after delinearization (#151326)
Delinearization provides two values: the size of the array, and the subscript of the access. DA checks their validity (`0 <= subscript < size`), with some special handling. In particular, to ensure `subscript < size`, calculate the maximum value of `subscript - size` and check if it is negative. There was an issue in its process: when `subscript - size` is expressed as an affine format like `init + step * i`, the value in the last iteration (`start + step * (num_iterations - 1)`) was assumed to be the maximum value. This assumption is incorrect in the following cases: - When `step` is negative - When the AddRec wraps This patch introduces extra checks to ensure the sign of `step` and verify the existence of nsw/nuw flags. Also, `isKnownNonNegative(S - smax(1, Size))` was used as a regular check, which is incorrect when `Size` is negative. This patch also replace it with `isKnownNonNegative(S - Size)`, although it's still unclear whether using `isKnownNonNegative` is appropriate in the first place. Fix #150604
Diffstat (limited to 'llvm/lib')
-rw-r--r--llvm/lib/Analysis/DependenceAnalysis.cpp37
1 files changed, 25 insertions, 12 deletions
diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp
index 256befa..835e270 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -1074,7 +1074,7 @@ bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X,
/// Compare to see if S is less than Size, using
///
-/// isKnownNegative(S - max(Size, 1))
+/// isKnownNegative(S - Size)
///
/// with some extra checking if S is an AddRec and we can prove less-than using
/// the loop bounds.
@@ -1090,21 +1090,34 @@ bool DependenceInfo::isKnownLessThan(const SCEV *S, const SCEV *Size) const {
Size = SE->getTruncateOrZeroExtend(Size, MaxType);
// Special check for addrecs using BE taken count
- const SCEV *Bound = SE->getMinusSCEV(S, Size);
- if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Bound)) {
- if (AddRec->isAffine()) {
+ if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
+ if (AddRec->isAffine() && AddRec->hasNoSignedWrap()) {
const SCEV *BECount = SE->getBackedgeTakenCount(AddRec->getLoop());
- if (!isa<SCEVCouldNotCompute>(BECount)) {
- const SCEV *Limit = AddRec->evaluateAtIteration(BECount, *SE);
- if (SE->isKnownNegative(Limit))
- return true;
- }
+ const SCEV *Start = AddRec->getStart();
+ const SCEV *Step = AddRec->getStepRecurrence(*SE);
+ const SCEV *End = AddRec->evaluateAtIteration(BECount, *SE);
+ const SCEV *Diff0 = SE->getMinusSCEV(Start, Size);
+ const SCEV *Diff1 = SE->getMinusSCEV(End, Size);
+
+ // If the value of Step is non-negative and the AddRec is non-wrap, it
+ // reaches its maximum at the last iteration. So it's enouth to check
+ // whether End - Size is negative.
+ if (SE->isKnownNonNegative(Step) && SE->isKnownNegative(Diff1))
+ return true;
+
+ // If the value of Step is non-positive and the AddRec is non-wrap, the
+ // initial value is its maximum.
+ if (SE->isKnownNonPositive(Step) && SE->isKnownNegative(Diff0))
+ return true;
+
+ // Even if we don't know the sign of Step, either Start or End must be
+ // the maximum value of the AddRec since it is non-wrap.
+ if (SE->isKnownNegative(Diff0) && SE->isKnownNegative(Diff1))
+ return true;
}
- }
// Check using normal isKnownNegative
- const SCEV *LimitedBound =
- SE->getMinusSCEV(S, SE->getSMaxExpr(Size, SE->getOne(Size->getType())));
+ const SCEV *LimitedBound = SE->getMinusSCEV(S, Size);
return SE->isKnownNegative(LimitedBound);
}