diff options
author | Ryotaro Kasuga <kasuga.ryotaro@fujitsu.com> | 2025-08-08 10:58:13 +0900 |
---|---|---|
committer | GitHub <noreply@github.com> | 2025-08-08 10:58:13 +0900 |
commit | 05dd957cda663273ae0e5739656ffe701404f37c (patch) | |
tree | d892db99e3fe84474e3ed2afe4f7676d2a8a8d86 /llvm/lib | |
parent | 1458eb206fb652358b3ee7e75d95b52f3f4ac333 (diff) | |
download | llvm-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.cpp | 37 |
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); } |