llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-analysis Author: Ryotaro Kasuga (kasuga-fj) <details> <summary>Changes</summary> This patch fixes issues where the Exact SIV/RDIV tests can return incorrect results when the BTC is negative in a signed sense. The root cause is that BTCs should be interpreted in an unsigned sense, but `inferAffineDomain` uses the BTC in inequalities that are interpreted in a signed sense. These inequalities make sense only when the BTC is non-negative. Thus we need to check it beforehand. --- Full diff: https://github.com/llvm/llvm-project/pull/187218.diff 2 Files Affected: - (modified) llvm/lib/Analysis/DependenceAnalysis.cpp (+23-12) - (modified) llvm/test/Analysis/DependenceAnalysis/rdiv-large-btc.ll (+2-2) ``````````diff diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index 01300d0acbdf1..83777fe82afe2 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -1561,11 +1561,11 @@ ceilingOfQuotient(const OverflowSafeSignedAPInt &OA, /// integer, infer the possible range of k based on the known range of the /// affine expression. If we know A*k + B is non-negative, i.e., /// -/// A*k + B >= 0 +/// A*k + B >=s 0 /// /// we can derive the following inequalities for k when A is positive: /// -/// k >= -B / A +/// k >=s -B / A /// /// Since k is an integer, it means k is greater than or equal to the /// ceil(-B / A). @@ -1573,11 +1573,11 @@ ceilingOfQuotient(const OverflowSafeSignedAPInt &OA, /// If the upper bound of the affine expression \p UB is passed, the following /// inequality can be derived as well: /// -/// A*k + B <= UB +/// A*k + B <=s UB /// /// which leads to: /// -/// k <= (UB - B) / A +/// k <=s (UB - B) / A /// /// Again, as k is an integer, it means k is less than or equal to the /// floor((UB - B) / A). @@ -1585,12 +1585,14 @@ ceilingOfQuotient(const OverflowSafeSignedAPInt &OA, /// The similar logic applies when A is negative, but the inequalities sign flip /// while working with them. /// -/// Preconditions: \p A is non-zero, and we know A*k + B is non-negative. +/// Preconditions: \p A is non-zero, and we know A*k + B and \p UB are +/// non-negative. static std::pair<OverflowSafeSignedAPInt, OverflowSafeSignedAPInt> inferDomainOfAffine(OverflowSafeSignedAPInt A, OverflowSafeSignedAPInt B, OverflowSafeSignedAPInt UB) { assert(A && B && "A and B must be available"); assert(*A != 0 && "A must be non-zero"); + assert((!UB || UB->isNonNegative()) && "UB must be non-negative"); OverflowSafeSignedAPInt TL, TU; if (A->sgt(0)) { TL = ceilingOfQuotient(-B, A); @@ -1681,8 +1683,11 @@ bool DependenceInfo::exactSIVtest(const SCEVAddRecExpr *Src, // UM is perhaps unavailable, let's check if (const SCEVConstant *CUB = collectConstantUpperBound(Src->getLoop(), Delta->getType())) { - UM = CUB->getAPInt(); - LLVM_DEBUG(dbgs() << "\t UM = " << *UM << "\n"); + APInt Tmp = CUB->getAPInt(); + if (Tmp.isNonNegative()) { + UM = CUB->getAPInt(); + LLVM_DEBUG(dbgs() << "\t UM = " << *UM << "\n"); + } } APInt TU(APInt::getSignedMaxValue(Bits)); @@ -2060,16 +2065,22 @@ bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, // SrcUM is perhaps unavailable, let's check if (const SCEVConstant *UpperBound = collectConstantUpperBound(SrcLoop, Delta->getType())) { - SrcUM = UpperBound->getAPInt(); - LLVM_DEBUG(dbgs() << "\t SrcUM = " << *SrcUM << "\n"); + APInt Tmp = UpperBound->getAPInt(); + if (Tmp.isNonNegative()) { + SrcUM = UpperBound->getAPInt(); + LLVM_DEBUG(dbgs() << "\t SrcUM = " << *SrcUM << "\n"); + } } std::optional<APInt> DstUM; - // UM is perhaps unavailable, let's check + // DstUM is perhaps unavailable, let's check if (const SCEVConstant *UpperBound = collectConstantUpperBound(DstLoop, Delta->getType())) { - DstUM = UpperBound->getAPInt(); - LLVM_DEBUG(dbgs() << "\t DstUM = " << *DstUM << "\n"); + APInt Tmp = UpperBound->getAPInt(); + if (Tmp.isNonNegative()) { + DstUM = UpperBound->getAPInt(); + LLVM_DEBUG(dbgs() << "\t DstUM = " << *DstUM << "\n"); + } } APInt TU(APInt::getSignedMaxValue(Bits)); diff --git a/llvm/test/Analysis/DependenceAnalysis/rdiv-large-btc.ll b/llvm/test/Analysis/DependenceAnalysis/rdiv-large-btc.ll index 575b22028e40a..56ab9c08a9336 100644 --- a/llvm/test/Analysis/DependenceAnalysis/rdiv-large-btc.ll +++ b/llvm/test/Analysis/DependenceAnalysis/rdiv-large-btc.ll @@ -23,7 +23,7 @@ define void @rdiv_large_btc(ptr %A) { ; CHECK-ALL-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.0, align 1 ; CHECK-ALL-NEXT: da analyze - none! ; CHECK-ALL-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.1, align 1 -; CHECK-ALL-NEXT: da analyze - none! +; CHECK-ALL-NEXT: da analyze - output [|<]! ; CHECK-ALL-NEXT: Src: store i8 0, ptr %gep.1, align 1 --> Dst: store i8 0, ptr %gep.1, align 1 ; CHECK-ALL-NEXT: da analyze - none! ; @@ -31,7 +31,7 @@ define void @rdiv_large_btc(ptr %A) { ; CHECK-EXACT-RDIV-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.0, align 1 ; CHECK-EXACT-RDIV-NEXT: da analyze - output [*]! ; CHECK-EXACT-RDIV-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.1, align 1 -; CHECK-EXACT-RDIV-NEXT: da analyze - none! +; CHECK-EXACT-RDIV-NEXT: da analyze - output [|<]! ; CHECK-EXACT-RDIV-NEXT: Src: store i8 0, ptr %gep.1, align 1 --> Dst: store i8 0, ptr %gep.1, align 1 ; CHECK-EXACT-RDIV-NEXT: da analyze - output [*]! ; `````````` </details> https://github.com/llvm/llvm-project/pull/187218 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
