https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/179665
>From 67561862797584af293898cbbfc9e23c2066b00d Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Wed, 4 Feb 2026 14:03:56 +0000 Subject: [PATCH] [DA] Rewrite the formula in the Strong SIV test --- .../llvm/Analysis/DependenceAnalysis.h | 9 +- llvm/lib/Analysis/DependenceAnalysis.cpp | 97 +++++++++---------- .../strong-siv-large-btc.ll | 25 +++-- 3 files changed, 64 insertions(+), 67 deletions(-) diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h b/llvm/include/llvm/Analysis/DependenceAnalysis.h index 6963914d6a03d..d69a9179f7df4 100644 --- a/llvm/include/llvm/Analysis/DependenceAnalysis.h +++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h @@ -555,7 +555,7 @@ class DependenceInfo { bool testMIV(const SCEV *Src, const SCEV *Dst, const SmallBitVector &Loops, FullDependence &Result) const; - /// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst) + /// strongSIVtest - Tests the strong SIV subscript pair (\p Src and \p Dst) /// for dependence. /// Things of the form [c1 + a*i] and [c2 + a*i], /// where i is an induction variable, c1 and c2 are loop invariant, @@ -563,10 +563,9 @@ class DependenceInfo { /// Returns true if any possible dependence is disproved. /// If there might be a dependence, returns false. /// Sets appropriate direction and distance. - bool strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst, - const SCEV *DstConst, const Loop *CurrentSrcLoop, - const Loop *CurrentDstLoop, unsigned Level, - FullDependence &Result, bool UnderRuntimeAssumptions); + bool strongSIVtest(const SCEVAddRecExpr *Src, const SCEVAddRecExpr *Dst, + unsigned Level, FullDependence &Result, + bool UnderRuntimeAssumptions); /// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair /// (Src and Dst) for dependence. diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index 51d0c32149330..35c378d8542a3 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -1245,32 +1245,6 @@ static const SCEV *minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B, return nullptr; } -/// Returns \p A * \p B if it guaranteed not to signed wrap. Otherwise returns -/// nullptr. \p A and \p B must have the same integer type. -static const SCEV *mulSCEVNoSignedOverflow(const SCEV *A, const SCEV *B, - ScalarEvolution &SE) { - if (SE.willNotOverflow(Instruction::Mul, /*Signed=*/true, A, B)) - return SE.getMulExpr(A, B); - return nullptr; -} - -/// Returns the absolute value of \p A. In the context of dependence analysis, -/// we need an absolute value in a mathematical sense. If \p A is the signed -/// minimum value, we cannot represent it unless extending the original type. -/// Thus if we cannot prove that \p A is not the signed minimum value, returns -/// nullptr. -static const SCEV *absSCEVNoSignedOverflow(const SCEV *A, ScalarEvolution &SE) { - IntegerType *Ty = cast<IntegerType>(A->getType()); - if (!Ty) - return nullptr; - - const SCEV *SMin = - SE.getConstant(APInt::getSignedMinValue(Ty->getBitWidth())); - if (!SE.isKnownPredicate(CmpInst::ICMP_NE, A, SMin)) - return nullptr; - return SE.getAbsExpr(A, /*IsNSW=*/true); -} - /// Returns true iff \p Test is enabled. static bool isDependenceTestEnabled(DependenceTestType Test) { if (EnableDependenceTest == DependenceTestType::All) @@ -1334,14 +1308,18 @@ bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst, // { > if d < 0 // // Return true if dependence disproved. -bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst, - const SCEV *DstConst, const Loop *CurSrcLoop, - const Loop *CurDstLoop, unsigned Level, +bool DependenceInfo::strongSIVtest(const SCEVAddRecExpr *Src, + const SCEVAddRecExpr *Dst, unsigned Level, FullDependence &Result, bool UnderRuntimeAssumptions) { if (!isDependenceTestEnabled(DependenceTestType::StrongSIV)) return false; + const SCEV *Coeff = Src->getStepRecurrence(*SE); + assert(Coeff == Dst->getStepRecurrence(*SE) && + "Expecting same coefficient in Strong SIV test"); + const SCEV *SrcConst = Src->getStart(); + const SCEV *DstConst = Dst->getStart(); LLVM_DEBUG(dbgs() << "\tStrong SIV test\n"); LLVM_DEBUG(dbgs() << "\t Coeff = " << *Coeff); LLVM_DEBUG(dbgs() << ", " << *Coeff->getType() << "\n"); @@ -1353,38 +1331,52 @@ bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst, assert(0 < Level && Level <= CommonLevels && "level out of range"); Level--; - const SCEV *Delta = minusSCEVNoSignedOverflow(SrcConst, DstConst, *SE); - if (!Delta) { - Result.Consistent = false; - return false; - } - LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta); - LLVM_DEBUG(dbgs() << ", " << *Delta->getType() << "\n"); - - // check that |Delta| < iteration count - bool IsDeltaLarge = [&] { - const SCEV *UpperBound = collectUpperBound(CurSrcLoop, Delta->getType()); + // Src: [a*0 + c1], [a*1 + c1], [a*2 + c1], ..., [a*BTC + c1] + // Dst: [a*0 + c2], [a*1 + c2], [a*2 + c2], ..., [a*BTC + c2] + // + // When 0 <=s a, we can prove independence if: + // + // (a*BTC + c1 <s a*0 + c2) or (a*BTC + c2 <s a*0 + c1) + // + // When a <s 0, we can prove independence if: + // + // (a*0 + c1 <s a*BTC + c2) or (a*0 + c2 <s a*BTC + c1) + // + // We can combine both cases by computing the smin and smax of the Src and + // Dst. + bool IsNoOverlap = [&] { + const SCEV *UpperBound = collectUpperBound(Src->getLoop(), Src->getType()); if (!UpperBound) return false; - LLVM_DEBUG(dbgs() << "\t UpperBound = " << *UpperBound); LLVM_DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n"); - const SCEV *AbsDelta = absSCEVNoSignedOverflow(Delta, *SE); - const SCEV *AbsCoeff = absSCEVNoSignedOverflow(Coeff, *SE); - if (!AbsDelta || !AbsCoeff) - return false; - const SCEV *Product = mulSCEVNoSignedOverflow(UpperBound, AbsCoeff, *SE); - if (!Product) - return false; - return SE->isKnownPredicate(CmpInst::ICMP_SGT, AbsDelta, Product); + + const SCEV *SrcBegin = SrcConst; + const SCEV *DstBegin = DstConst; + const SCEV *SrcEnd = Src->evaluateAtIteration(UpperBound, *SE); + const SCEV *DstEnd = Dst->evaluateAtIteration(UpperBound, *SE); + const SCEV *SrcMin = SE->getSMinExpr(SrcBegin, SrcEnd); + const SCEV *SrcMax = SE->getSMaxExpr(SrcBegin, SrcEnd); + const SCEV *DstMin = SE->getSMinExpr(DstBegin, DstEnd); + const SCEV *DstMax = SE->getSMaxExpr(DstBegin, DstEnd); + return SE->isKnownPredicate(ICmpInst::ICMP_SLT, SrcMax, DstMin) || + SE->isKnownPredicate(ICmpInst::ICMP_SLT, DstMax, SrcMin); }(); - if (IsDeltaLarge) { + if (IsNoOverlap) { // Distance greater than trip count - no dependence ++StrongSIVindependence; ++StrongSIVsuccesses; return true; } + const SCEV *Delta = minusSCEVNoSignedOverflow(SrcConst, DstConst, *SE); + if (!Delta) { + Result.Consistent = false; + return false; + } + LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta); + LLVM_DEBUG(dbgs() << ", " << *Delta->getType() << "\n"); + // Can we compute distance? if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) { APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt(); @@ -2430,9 +2422,8 @@ bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level, Level = mapSrcLoop(CurSrcLoop); bool disproven; if (SrcCoeff == DstCoeff) - disproven = - strongSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop, CurDstLoop, - Level, Result, UnderRuntimeAssumptions); + disproven = strongSIVtest(SrcAddRec, DstAddRec, Level, Result, + UnderRuntimeAssumptions); else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff)) disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop, CurDstLoop, Level, Result); diff --git a/llvm/test/Analysis/DependenceAnalysis/strong-siv-large-btc.ll b/llvm/test/Analysis/DependenceAnalysis/strong-siv-large-btc.ll index 1b3312419bc62..4d09e8b6e4625 100644 --- a/llvm/test/Analysis/DependenceAnalysis/strong-siv-large-btc.ll +++ b/llvm/test/Analysis/DependenceAnalysis/strong-siv-large-btc.ll @@ -17,13 +17,21 @@ ; dependency between them. ; define void @strong_siv_large_btc(ptr %A) { -; CHECK-LABEL: 'strong_siv_large_btc' -; CHECK-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.0, align 1 -; CHECK-NEXT: da analyze - none! -; CHECK-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.1, align 1 -; CHECK-NEXT: da analyze - none! -; CHECK-NEXT: Src: store i8 0, ptr %gep.1, align 1 --> Dst: store i8 0, ptr %gep.1, align 1 -; CHECK-NEXT: da analyze - none! +; CHECK-ALL-LABEL: 'strong_siv_large_btc' +; 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: Src: store i8 0, ptr %gep.1, align 1 --> Dst: store i8 0, ptr %gep.1, align 1 +; CHECK-ALL-NEXT: da analyze - none! +; +; CHECK-STRONG-SIV-LABEL: 'strong_siv_large_btc' +; CHECK-STRONG-SIV-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.0, align 1 +; CHECK-STRONG-SIV-NEXT: da analyze - none! +; CHECK-STRONG-SIV-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.1, align 1 +; CHECK-STRONG-SIV-NEXT: da analyze - consistent output [-1]! +; CHECK-STRONG-SIV-NEXT: Src: store i8 0, ptr %gep.1, align 1 --> Dst: store i8 0, ptr %gep.1, align 1 +; CHECK-STRONG-SIV-NEXT: da analyze - none! ; entry: br label %loop.header @@ -58,5 +66,4 @@ exit: ret void } ;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line: -; CHECK-ALL: {{.*}} -; CHECK-STRONG-SIV: {{.*}} +; CHECK: {{.*}} _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
