https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/185577
>From 08645bf77282618f9b1ebb8980af6621cbe2e6bc Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Mon, 9 Mar 2026 13:32:35 +0000 Subject: [PATCH] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) --- .../llvm/Analysis/DependenceAnalysis.h | 5 + llvm/lib/Analysis/DependenceAnalysis.cpp | 200 +++++++----------- 2 files changed, 83 insertions(+), 122 deletions(-) diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h b/llvm/include/llvm/Analysis/DependenceAnalysis.h index 8adaf13dd5524..3bb8320fe174b 100644 --- a/llvm/include/llvm/Analysis/DependenceAnalysis.h +++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h @@ -552,6 +552,11 @@ class DependenceInfo { const Loop *CurrentSrcLoop, const Loop *CurrentDstLoop, unsigned Level, FullDependence &Result) const; + /// weakZeroSIVtestImpl - Core implementation for weakZeroSrcSIVtest and + /// weakZeroDstSIVtest. + bool weakZeroSIVtestImpl(const SCEVAddRecExpr *AR, const SCEV *Const, + unsigned Level, FullDependence &Result) const; + /// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair /// (Src and Dst) for dependence. /// Things of the form [c1] and [c2 + a*i], diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index 0b8666a27d349..b62425d0c492c 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -1785,75 +1785,32 @@ static bool isRemainderZero(const SCEVConstant *Dividend, return ConstDividend.srem(ConstDivisor) == 0; } -// weakZeroSrcSIVtest - -// From the paper, Practical Dependence Testing, Section 4.2.2 -// -// When we have a pair of subscripts of the form [c1] and [c2 + a*i], -// where i is an induction variable, c1 and c2 are loop invariant, -// and a is a constant, we can solve it exactly using the -// Weak-Zero SIV test. -// -// Given -// -// c1 = c2 + a*i -// -// we get -// -// (c1 - c2)/a = i -// -// If i is not an integer, there's no dependence. -// If i < 0 or > UB, there's no dependence. -// If i = 0, the direction is >=. -// If i = UB, the direction is <=. -// Otherwise, the direction is *. -// -// Can prove independence. Failing that, we can sometimes refine -// the directions. Can sometimes show that first or last -// iteration carries all the dependences (so worth peeling). -// -// (see also weakZeroDstSIVtest) -// -// Return true if dependence disproved. -bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *SrcConst, - const SCEVAddRecExpr *Dst, - 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 *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"); - LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); - ++WeakZeroSIVapplications; - assert(0 < Level && Level <= MaxLevels && "Level out of range"); - Level--; +bool DependenceInfo::weakZeroSIVtestImpl(const SCEVAddRecExpr *AR, + const SCEV *Const, unsigned Level, + FullDependence &Result) const { + const SCEV *ARCoeff = AR->getStepRecurrence(*SE); + const SCEV *ARConst = AR->getStart(); - ConstantRange SrcRange = SE->getSignedRange(SrcConst); - ConstantRange DstRange = SE->getSignedRange(Dst); - if (SrcRange.intersectWith(DstRange).isEmptySet()) { + ConstantRange ARRange = SE->getSignedRange(AR); + ConstantRange ConstRange = SE->getSignedRange(Const); + if (ARRange.intersectWith(ConstRange).isEmptySet()) { ++WeakZeroSIVindependence; ++WeakZeroSIVsuccesses; return true; } - if (SrcConst == DstConst && SE->isKnownNonZero(DstCoeff)) { + if (Const == ARConst && SE->isKnownNonZero(ARCoeff)) { if (Level < CommonLevels) { - Result.DV[Level].Direction &= Dependence::DVEntry::GE; + Result.DV[Level].Direction &= Dependence::DVEntry::LE; ++WeakZeroSIVsuccesses; } return false; // dependences caused by first iteration } - const SCEV *Delta = minusSCEVNoSignedOverflow(SrcConst, DstConst, *SE); + + const SCEV *Delta = minusSCEVNoSignedOverflow(Const, ARConst, *SE); if (!Delta) return false; - LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); - const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff); + const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(ARCoeff); if (!ConstCoeff) return false; @@ -1866,20 +1823,20 @@ bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *SrcConst, SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta; if (const SCEV *UpperBound = - collectUpperBound(Dst->getLoop(), Delta->getType())) { + collectUpperBound(AR->getLoop(), Delta->getType())) { LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); if (SE->isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) { // dependences caused by last iteration if (Level < CommonLevels) { - Result.DV[Level].Direction &= Dependence::DVEntry::LE; + Result.DV[Level].Direction &= Dependence::DVEntry::GE; ++WeakZeroSIVsuccesses; } return false; } } - // check that Delta/SrcCoeff >= 0 + // check that Delta/ARCoeff >= 0 // really check that NewDelta >= 0 if (SE->isKnownNegative(NewDelta)) { // No dependence, newDelta < 0 @@ -1888,7 +1845,7 @@ bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *SrcConst, return true; } - // if SrcCoeff doesn't divide Delta, then no dependence + // if ARCoeff doesn't divide Delta, then no dependence if (isa<SCEVConstant>(Delta) && !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) { ++WeakZeroSIVindependence; @@ -1898,6 +1855,66 @@ bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *SrcConst, return false; } +// weakZeroSrcSIVtest - +// From the paper, Practical Dependence Testing, Section 4.2.2 +// +// When we have a pair of subscripts of the form [c1] and [c2 + a*i], +// where i is an induction variable, c1 and c2 are loop invariant, +// and a is a constant, we can solve it exactly using the +// Weak-Zero SIV test. +// +// Given +// +// c1 = c2 + a*i +// +// we get +// +// (c1 - c2)/a = i +// +// If i is not an integer, there's no dependence. +// If i < 0 or > UB, there's no dependence. +// If i = 0, the direction is >=. +// If i = UB, the direction is <=. +// Otherwise, the direction is *. +// +// Can prove independence. Failing that, we can sometimes refine +// the directions. Can sometimes show that first or last +// iteration carries all the dependences (so worth peeling). +// +// (see also weakZeroDstSIVtest) +// +// Return true if dependence disproved. +bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *SrcConst, + const SCEVAddRecExpr *Dst, + 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 *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"); + LLVM_DEBUG(dbgs() << "\t DstConst = " << *DstConst << "\n"); + ++WeakZeroSIVapplications; + assert(0 < Level && Level <= MaxLevels && "Level out of range"); + Level--; + + // We have analyzed a dependence from Src to Dst, so \c Result may represent a + // dependence in that direction. However, \c weakZeroSIVtestImpl will analyze + // a dependence from \c Dst to \c SrcConst. To keep the consistency, we need + // to negate the current result before passing it to \c weakZeroSIVtestImpl, + // and negate it back after that. + Result.negate(*SE); + bool Res = weakZeroSIVtestImpl(Dst, SrcConst, Level, Result); + Result.negate(*SE); + return Res; +} + // weakZeroDstSIVtest - // From the paper, Practical Dependence Testing, Section 4.2.2 // @@ -1945,68 +1962,7 @@ bool DependenceInfo::weakZeroDstSIVtest(const SCEVAddRecExpr *Src, assert(0 < Level && Level <= SrcLevels && "Level out of range"); Level--; - ConstantRange SrcRange = SE->getSignedRange(Src); - ConstantRange DstRange = SE->getSignedRange(DstConst); - if (SrcRange.intersectWith(DstRange).isEmptySet()) { - ++WeakZeroSIVindependence; - ++WeakZeroSIVsuccesses; - return true; - } - - if (DstConst == SrcConst && SE->isKnownNonZero(SrcCoeff)) { - if (Level < CommonLevels) { - Result.DV[Level].Direction &= Dependence::DVEntry::LE; - ++WeakZeroSIVsuccesses; - } - return false; // dependences caused by first iteration - } - const SCEV *Delta = minusSCEVNoSignedOverflow(DstConst, SrcConst, *SE); - if (!Delta) - return false; - LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); - const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(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; - - if (const SCEV *UpperBound = - collectUpperBound(Src->getLoop(), Delta->getType())) { - LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound << "\n"); - const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound); - 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)) { - // No dependence, newDelta < 0 - ++WeakZeroSIVindependence; - ++WeakZeroSIVsuccesses; - return true; - } - - // if SrcCoeff doesn't divide Delta, then no dependence - if (isa<SCEVConstant>(Delta) && - !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) { - ++WeakZeroSIVindependence; - ++WeakZeroSIVsuccesses; - return true; - } - return false; + return weakZeroSIVtestImpl(Src, DstConst, Level, Result); } // exactRDIVtest - Tests the RDIV subscript pair for dependence. _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
