https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/183738
>From b3d2953db94838cf8b230719868275ae1162e590 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Fri, 27 Feb 2026 12:53:35 +0000 Subject: [PATCH] [DA] Rewrite formula in the Weak Zero SIV tests --- .../llvm/Analysis/DependenceAnalysis.h | 12 +- llvm/lib/Analysis/DependenceAnalysis.cpp | 139 +++++++++--------- .../weak-crossing-siv-large-btc.ll | 4 +- .../weak-zero-siv-large-btc.ll | 16 +- .../weak-zero-siv-overflow.ll | 8 +- 5 files changed, 83 insertions(+), 96 deletions(-) diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h b/llvm/include/llvm/Analysis/DependenceAnalysis.h index b99b2f5960049..25954a2535df3 100644 --- a/llvm/include/llvm/Analysis/DependenceAnalysis.h +++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h @@ -570,10 +570,8 @@ class DependenceInfo { /// Sets appropriate direction entry. /// Set consistent to false. /// If loop peeling will break the dependence, mark appropriately. - bool weakZeroSrcSIVtest(const SCEV *DstCoeff, const SCEV *SrcConst, - const SCEV *DstConst, const Loop *CurrentSrcLoop, - const Loop *CurrentDstLoop, unsigned Level, - FullDependence &Result) const; + bool weakZeroSrcSIVtest(const SCEV *SrcConst, const SCEVAddRecExpr *Dst, + unsigned Level, FullDependence &Result) const; /// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair /// (Src and Dst) for dependence. @@ -585,10 +583,8 @@ class DependenceInfo { /// Sets appropriate direction entry. /// Set consistent to false. /// If loop peeling will break the dependence, mark appropriately. - bool weakZeroDstSIVtest(const SCEV *SrcCoeff, const SCEV *SrcConst, - const SCEV *DstConst, const Loop *CurrentSrcLoop, - const Loop *CurrentDstLoop, unsigned Level, - FullDependence &Result) const; + bool weakZeroDstSIVtest(const SCEVAddRecExpr *Src, const SCEV *DstConst, + unsigned Level, FullDependence &Result) const; /// exactRDIVtest - Tests the RDIV subscript pair for dependence. /// Things of the form [c1 + a*i] and [c2 + b*j], diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index b9be42e5ad792..67444933579cb 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -1789,6 +1789,19 @@ static bool isRemainderZero(const SCEVConstant *Dividend, return ConstDividend.srem(ConstDivisor) == 0; } +/// An auxiliary function for the Weak-Zero SIV test. Return true if \p AR +/// overlaps with \p Const iff at the last iteration of the loop, where \p AR is +/// an affine AddRec expression, \p Const is a loop invariant constant, and \p +/// UpperBound is the exact backedge-taken count of the loop. +static bool isOverlapLastWeakZeroSIV(const SCEVAddRecExpr *AR, + const SCEV *Const, ScalarEvolution &SE, + const SCEV *UpperBound) { + return AR->hasNoSignedWrap() && + SE.isKnownNonZero(AR->getStepRecurrence(SE)) && + SE.isKnownPredicate(CmpInst::ICMP_EQ, + AR->evaluateAtIteration(UpperBound, SE), Const); +} + // weakZeroSrcSIVtest - // From the paper, Practical Dependence Testing, Section 4.2.2 // @@ -1820,11 +1833,9 @@ static bool isRemainderZero(const SCEVConstant *Dividend, // (see also weakZeroDstSIVtest) // // Return true if dependence disproved. -bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff, - const SCEV *SrcConst, - const SCEV *DstConst, - const Loop *CurSrcLoop, - const Loop *CurDstLoop, unsigned Level, +bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *SrcConst, + const SCEVAddRecExpr *Dst, + unsigned Level, FullDependence &Result) const { if (!isDependenceTestEnabled(DependenceTestType::WeakZeroSIV)) return false; @@ -1832,6 +1843,8 @@ bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff, // For the WeakSIV test, it's possible the loop isn't common to // the Src and Dst loops. If it isn't, then there's no need to // record a direction. + const SCEV *DstCoeff = Dst->getStepRecurrence(*SE); + const SCEV *DstConst = Dst->getStart(); LLVM_DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n"); LLVM_DEBUG(dbgs() << "\t DstCoeff = " << *DstCoeff << "\n"); LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); @@ -1840,6 +1853,27 @@ bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff, assert(0 < Level && Level <= MaxLevels && "Level out of range"); Level--; Result.Consistent = false; + + ConstantRange SrcRange = SE->getSignedRange(SrcConst); + ConstantRange DstRange = SE->getSignedRange(Dst); + if (SrcRange.intersectWith(DstRange).isEmptySet()) { + ++WeakZeroSIVindependence; + ++WeakZeroSIVsuccesses; + return true; + } + if (const SCEV *UpperBound = + collectUpperBound(Dst->getLoop(), Dst->getType())) { + bool OverlapAtLast = + isOverlapLastWeakZeroSIV(Dst, SrcConst, *SE, UpperBound); + if (OverlapAtLast) { + if (Level < CommonLevels) { + Result.DV[Level].Direction &= Dependence::DVEntry::LE; + ++WeakZeroSIVsuccesses; + } + return false; + } + } + const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); if (SE->isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst) && @@ -1850,39 +1884,14 @@ bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff, } return false; // dependences caused by first iteration } + const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff); if (!ConstCoeff) return false; - // Since ConstCoeff is constant, !isKnownNegative means it's non-negative. - // TODO: Bail out if it's a signed minimum value. - const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff) - ? SE->getNegativeSCEV(ConstCoeff) - : ConstCoeff; const SCEV *NewDelta = SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; - // check that Delta/SrcCoeff < iteration count - // really check NewDelta < count*AbsCoeff - if (const SCEV *UpperBound = - collectUpperBound(CurSrcLoop, Delta->getType())) { - LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); - const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); - if (SE->isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) { - ++WeakZeroSIVindependence; - ++WeakZeroSIVsuccesses; - return true; - } - if (SE->isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) { - // dependences caused by last iteration - if (Level < CommonLevels) { - Result.DV[Level].Direction &= Dependence::DVEntry::LE; - ++WeakZeroSIVsuccesses; - } - return false; - } - } - // check that Delta/SrcCoeff >= 0 // really check that NewDelta >= 0 if (SE->isKnownNegative(NewDelta)) { @@ -1933,17 +1942,16 @@ bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff, // (see also weakZeroSrcSIVtest) // // Return true if dependence disproved. -bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff, - const SCEV *SrcConst, - const SCEV *DstConst, - const Loop *CurSrcLoop, - const Loop *CurDstLoop, unsigned Level, +bool DependenceInfo::weakZeroDstSIVtest(const SCEVAddRecExpr *Src, + const SCEV *DstConst, unsigned Level, FullDependence &Result) const { if (!isDependenceTestEnabled(DependenceTestType::WeakZeroSIV)) return false; // For the WeakSIV test, it's possible the loop isn't common to the // Src and Dst loops. If it isn't, then there's no need to record a direction. + const SCEV *SrcCoeff = Src->getStepRecurrence(*SE); + const SCEV *SrcConst = Src->getStart(); LLVM_DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n"); LLVM_DEBUG(dbgs() << "\t SrcCoeff = " << *SrcCoeff << "\n"); LLVM_DEBUG(dbgs() << "\t SrcConst = " << *SrcConst << "\n"); @@ -1952,6 +1960,27 @@ bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff, assert(0 < Level && Level <= SrcLevels && "Level out of range"); Level--; Result.Consistent = false; + + ConstantRange SrcRange = SE->getSignedRange(Src); + ConstantRange DstRange = SE->getSignedRange(DstConst); + if (SrcRange.intersectWith(DstRange).isEmptySet()) { + ++WeakZeroSIVindependence; + ++WeakZeroSIVsuccesses; + return true; + } + if (const SCEV *UpperBound = + collectUpperBound(Src->getLoop(), Src->getType())) { + bool OverlapAtLast = + isOverlapLastWeakZeroSIV(Src, DstConst, *SE, UpperBound); + if (OverlapAtLast) { + if (Level < CommonLevels) { + Result.DV[Level].Direction &= Dependence::DVEntry::GE; + ++WeakZeroSIVsuccesses; + } + return false; + } + } + const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); if (SE->isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst) && @@ -1966,35 +1995,9 @@ bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff, if (!ConstCoeff) return false; - // Since ConstCoeff is constant, !isKnownNegative means it's non-negative. - // TODO: Bail out if it's a signed minimum value. - const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff) - ? SE->getNegativeSCEV(ConstCoeff) - : ConstCoeff; const SCEV *NewDelta = SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; - // check that Delta/SrcCoeff < iteration count - // really check NewDelta < count*AbsCoeff - if (const SCEV *UpperBound = - collectUpperBound(CurSrcLoop, Delta->getType())) { - LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); - const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); - if (SE->isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) { - ++WeakZeroSIVindependence; - ++WeakZeroSIVsuccesses; - return true; - } - if (SE->isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) { - // dependences caused by last iteration - if (Level < CommonLevels) { - Result.DV[Level].Direction &= Dependence::DVEntry::GE; - ++WeakZeroSIVsuccesses; - } - return false; - } - } - // check that Delta/SrcCoeff >= 0 // really check that NewDelta >= 0 if (SE->isKnownNegative(NewDelta)) { @@ -2315,23 +2318,15 @@ bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level, CurDstLoop); } if (SrcAddRec) { - const SCEV *SrcConst = SrcAddRec->getStart(); - const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE); - const SCEV *DstConst = Dst; const Loop *CurSrcLoop = SrcAddRec->getLoop(); Level = mapSrcLoop(CurSrcLoop); - return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop, - CurSrcLoop, Level, Result) || + return weakZeroDstSIVtest(SrcAddRec, Dst, Level, Result) || gcdMIVtest(Src, Dst, Result); } if (DstAddRec) { - const SCEV *DstConst = DstAddRec->getStart(); - const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE); - const SCEV *SrcConst = Src; const Loop *CurDstLoop = DstAddRec->getLoop(); Level = mapDstLoop(CurDstLoop); - return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst, CurDstLoop, - CurDstLoop, Level, Result) || + return weakZeroSrcSIVtest(Src, DstAddRec, Level, Result) || gcdMIVtest(Src, Dst, Result); } llvm_unreachable("SIV test expected at least one AddRec"); diff --git a/llvm/test/Analysis/DependenceAnalysis/weak-crossing-siv-large-btc.ll b/llvm/test/Analysis/DependenceAnalysis/weak-crossing-siv-large-btc.ll index b097c06e31202..d85ce2d9eea63 100644 --- a/llvm/test/Analysis/DependenceAnalysis/weak-crossing-siv-large-btc.ll +++ b/llvm/test/Analysis/DependenceAnalysis/weak-crossing-siv-large-btc.ll @@ -13,8 +13,8 @@ ; A[i1] = 0; ; } ; -; FIXME: Both `A[i0] = 0` and `A[i1] = 0` must be executed, so there is a -; dependency between them. +; Both `A[i0] = 0` and `A[i1] = 0` must be executed, so there is a dependency +; between them. ; define void @weak_crossing_siv_large_btc(ptr %A) { ; CHECK-ALL-LABEL: 'weak_crossing_siv_large_btc' diff --git a/llvm/test/Analysis/DependenceAnalysis/weak-zero-siv-large-btc.ll b/llvm/test/Analysis/DependenceAnalysis/weak-zero-siv-large-btc.ll index c06032798c792..eb35e39be36a3 100644 --- a/llvm/test/Analysis/DependenceAnalysis/weak-zero-siv-large-btc.ll +++ b/llvm/test/Analysis/DependenceAnalysis/weak-zero-siv-large-btc.ll @@ -10,15 +10,15 @@ ; A[0] = 1; ; } ; -; FIXME: `A[i] = 0` will be executed (when i == 0), so there is a ; dependency -; between the ; two stores. +; `A[i] = 0` will be executed (when i == 0), so there is a dependency between +; the two stores. ; define void @weak_zero_src_siv_large_btc(ptr %A) { ; CHECK-ALL-LABEL: 'weak_zero_src_siv_large_btc' ; CHECK-ALL-NEXT: Src: store i8 0, ptr %gep, align 1 --> Dst: store i8 0, ptr %gep, align 1 ; CHECK-ALL-NEXT: da analyze - none! ; CHECK-ALL-NEXT: Src: store i8 0, ptr %gep, align 1 --> Dst: store i8 1, ptr %A, align 1 -; CHECK-ALL-NEXT: da analyze - none! +; CHECK-ALL-NEXT: da analyze - output [*|<]! ; CHECK-ALL-NEXT: Src: store i8 1, ptr %A, align 1 --> Dst: store i8 1, ptr %A, align 1 ; CHECK-ALL-NEXT: da analyze - consistent output [S]! ; @@ -26,7 +26,7 @@ define void @weak_zero_src_siv_large_btc(ptr %A) { ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: Src: store i8 0, ptr %gep, align 1 --> Dst: store i8 0, ptr %gep, align 1 ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: da analyze - consistent output [*]! ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: Src: store i8 0, ptr %gep, align 1 --> Dst: store i8 1, ptr %A, align 1 -; CHECK-WEAK-ZERO-SRC-SIV-NEXT: da analyze - none! +; CHECK-WEAK-ZERO-SRC-SIV-NEXT: da analyze - output [*|<]! ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: Src: store i8 1, ptr %A, align 1 --> Dst: store i8 1, ptr %A, align 1 ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: da analyze - consistent output [S]! ; @@ -60,15 +60,15 @@ exit: ; A[i] = 0; ; } ; -; FIXME: `A[i] = 0` will be executed (when i == 0), so there is a ; dependency -; between the ; two stores. +; `A[i] = 0` will be executed (when i == 0), so there is a dependency between +; the two stores. ; define void @weak_zero_dst_siv_large_btc(ptr %A) { ; CHECK-ALL-LABEL: 'weak_zero_dst_siv_large_btc' ; CHECK-ALL-NEXT: Src: store i8 1, ptr %A, align 1 --> Dst: store i8 1, ptr %A, align 1 ; CHECK-ALL-NEXT: da analyze - consistent output [S]! ; CHECK-ALL-NEXT: Src: store i8 1, ptr %A, align 1 --> Dst: store i8 0, ptr %gep, align 1 -; CHECK-ALL-NEXT: da analyze - none! +; CHECK-ALL-NEXT: da analyze - output [*|<]! ; CHECK-ALL-NEXT: Src: store i8 0, ptr %gep, align 1 --> Dst: store i8 0, ptr %gep, align 1 ; CHECK-ALL-NEXT: da analyze - none! ; @@ -76,7 +76,7 @@ define void @weak_zero_dst_siv_large_btc(ptr %A) { ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: Src: store i8 1, ptr %A, align 1 --> Dst: store i8 1, ptr %A, align 1 ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: da analyze - consistent output [S]! ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: Src: store i8 1, ptr %A, align 1 --> Dst: store i8 0, ptr %gep, align 1 -; CHECK-WEAK-ZERO-SRC-SIV-NEXT: da analyze - none! +; CHECK-WEAK-ZERO-SRC-SIV-NEXT: da analyze - output [*|<]! ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: Src: store i8 0, ptr %gep, align 1 --> Dst: store i8 0, ptr %gep, align 1 ; CHECK-WEAK-ZERO-SRC-SIV-NEXT: da analyze - consistent output [*]! ; diff --git a/llvm/test/Analysis/DependenceAnalysis/weak-zero-siv-overflow.ll b/llvm/test/Analysis/DependenceAnalysis/weak-zero-siv-overflow.ll index 6317c387858d3..7ce0ef32100cf 100644 --- a/llvm/test/Analysis/DependenceAnalysis/weak-zero-siv-overflow.ll +++ b/llvm/test/Analysis/DependenceAnalysis/weak-zero-siv-overflow.ll @@ -10,16 +10,12 @@ ; A[2] = 2; ; } ; -; FIXME: DependenceAnalysis currently detects no dependency between the two -; stores, but it does exist. The root cause is that the product of the BTC and -; the coefficient ((1LL << 62) - 1 and 2) overflows in a signed sense. -; define void @weakzero_dst_siv_prod_ovfl(ptr %A) { ; CHECK-ALL-LABEL: 'weakzero_dst_siv_prod_ovfl' ; CHECK-ALL-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 1, ptr %gep.0, align 1 ; CHECK-ALL-NEXT: da analyze - none! ; CHECK-ALL-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 -; CHECK-ALL-NEXT: da analyze - none! +; CHECK-ALL-NEXT: da analyze - output [*|<]! ; CHECK-ALL-NEXT: Src: store i8 2, ptr %gep.1, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 ; CHECK-ALL-NEXT: da analyze - consistent output [S]! ; @@ -27,7 +23,7 @@ define void @weakzero_dst_siv_prod_ovfl(ptr %A) { ; CHECK-WEAK-ZERO-SIV-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 1, ptr %gep.0, align 1 ; CHECK-WEAK-ZERO-SIV-NEXT: da analyze - consistent output [*]! ; CHECK-WEAK-ZERO-SIV-NEXT: Src: store i8 1, ptr %gep.0, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 -; CHECK-WEAK-ZERO-SIV-NEXT: da analyze - none! +; CHECK-WEAK-ZERO-SIV-NEXT: da analyze - output [*|<]! ; CHECK-WEAK-ZERO-SIV-NEXT: Src: store i8 2, ptr %gep.1, align 1 --> Dst: store i8 2, ptr %gep.1, align 1 ; CHECK-WEAK-ZERO-SIV-NEXT: da analyze - consistent output [S]! ; _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
