[llvm-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
https://github.com/kasuga-fj updated
https://github.com/llvm/llvm-project/pull/185577
>From e284717ddfb507a48f49287850f9dbf827caafae Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga
Date: Mon, 9 Mar 2026 13:32:35 +
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 ca5a72e953f57..789b62ead0987 100644
--- a/llvm/include/llvm/Analysis/DependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h
@@ -550,6 +550,11 @@ class DependenceInfo {
bool exactSIVtest(const SCEVAddRecExpr *Src, const SCEVAddRecExpr *Dst,
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 aa689ac346584..cb7a42fc7977c 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -1789,75 +1789,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() << "\tDstCoeff = " << *DstCoeff << "\n");
- LLVM_DEBUG(dbgs() << "\tSrcConst = " << *SrcConst << "\n");
- LLVM_DEBUG(dbgs() << "\tDstConst = " << *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() << "\tDelta = " << *Delta << "\n");
- const SCEVConstant *ConstCoeff = dyn_cast(DstCoeff);
+ const SCEVConstant
[llvm-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
https://github.com/kasuga-fj updated
https://github.com/llvm/llvm-project/pull/185577
>From e284717ddfb507a48f49287850f9dbf827caafae Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga
Date: Mon, 9 Mar 2026 13:32:35 +
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 ca5a72e953f57..789b62ead0987 100644
--- a/llvm/include/llvm/Analysis/DependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h
@@ -550,6 +550,11 @@ class DependenceInfo {
bool exactSIVtest(const SCEVAddRecExpr *Src, const SCEVAddRecExpr *Dst,
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 aa689ac346584..cb7a42fc7977c 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -1789,75 +1789,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() << "\tDstCoeff = " << *DstCoeff << "\n");
- LLVM_DEBUG(dbgs() << "\tSrcConst = " << *SrcConst << "\n");
- LLVM_DEBUG(dbgs() << "\tDstConst = " << *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() << "\tDelta = " << *Delta << "\n");
- const SCEVConstant *ConstCoeff = dyn_cast(DstCoeff);
+ const SCEVConstant
[llvm-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
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
Date: Mon, 9 Mar 2026 13:32:35 +
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() << "\tDstCoeff = " << *DstCoeff << "\n");
- LLVM_DEBUG(dbgs() << "\tSrcConst = " << *SrcConst << "\n");
- LLVM_DEBUG(dbgs() << "\tDstConst = " << *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() << "\tDelta = " << *Delta << "\n");
- const SCEVConstant *ConstCoeff = dyn_cast(DstCoeff);
+ const
[llvm-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
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
Date: Mon, 9 Mar 2026 13:32:35 +
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() << "\tDstCoeff = " << *DstCoeff << "\n");
- LLVM_DEBUG(dbgs() << "\tSrcConst = " << *SrcConst << "\n");
- LLVM_DEBUG(dbgs() << "\tDstConst = " << *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() << "\tDelta = " << *Delta << "\n");
- const SCEVConstant *ConstCoeff = dyn_cast(DstCoeff);
+ const
[llvm-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
https://github.com/kasuga-fj updated
https://github.com/llvm/llvm-project/pull/185577
>From 030571bb90e340a97f3329d8a72835a76efa2fa6 Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga
Date: Mon, 9 Mar 2026 13:32:35 +
Subject: [PATCH] [DA] Consolidate the core logic of the Weak Zero SIV tests
(NFCI)
---
.../llvm/Analysis/DependenceAnalysis.h| 5 +
llvm/lib/Analysis/DependenceAnalysis.cpp | 204 +++---
2 files changed, 85 insertions(+), 124 deletions(-)
diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h
b/llvm/include/llvm/Analysis/DependenceAnalysis.h
index 7ced97c34715b..092280eddbc01 100644
--- a/llvm/include/llvm/Analysis/DependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h
@@ -557,6 +557,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 29e04e59c414a..8beefedef5262 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -1785,77 +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 >= and peeling the
-// 1st iteration will break the dependence.
-// If i = UB, the direction is <= and peeling the
-// last iteration will break the dependence.
-// 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() << "\tDstCoeff = " << *DstCoeff << "\n");
- LLVM_DEBUG(dbgs() << "\tSrcConst = " << *SrcConst << "\n");
- LLVM_DEBUG(dbgs() << "\tDstConst = " << *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-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
github-actions[bot] wrote: :warning: C/C++ code formatter, clang-format found issues in your code. :warning: You can test this locally with the following command: ``bash git-clang-format --diff origin/main HEAD --extensions cpp,h -- llvm/include/llvm/Analysis/DependenceAnalysis.h llvm/lib/Analysis/DependenceAnalysis.cpp --diff_from_common_commit `` :warning: The reproduction instructions above might return results for more than one PR in a stack if you are using a stacked PR workflow. You can limit the results by changing `origin/main` to the base branch/commit you want to compare against. :warning: View the diff from clang-format here. ``diff diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index e149657ae..8beefedef 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -1906,7 +1906,11 @@ bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *SrcConst, 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. + // 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); `` https://github.com/llvm/llvm-project/pull/185577 ___ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
[llvm-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
https://github.com/kasuga-fj updated
https://github.com/llvm/llvm-project/pull/185577
>From e3c14becc4c64992238333c45e532ea637b94781 Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga
Date: Mon, 9 Mar 2026 13:32:35 +
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, 81 insertions(+), 124 deletions(-)
diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h
b/llvm/include/llvm/Analysis/DependenceAnalysis.h
index 7ced97c34715b..092280eddbc01 100644
--- a/llvm/include/llvm/Analysis/DependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h
@@ -557,6 +557,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 29e04e59c414a..e149657ae29d5 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -1785,77 +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 >= and peeling the
-// 1st iteration will break the dependence.
-// If i = UB, the direction is <= and peeling the
-// last iteration will break the dependence.
-// 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() << "\tDstCoeff = " << *DstCoeff << "\n");
- LLVM_DEBUG(dbgs() << "\tSrcConst = " << *SrcConst << "\n");
- LLVM_DEBUG(dbgs() << "\tDstConst = " << *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-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
https://github.com/kasuga-fj updated
https://github.com/llvm/llvm-project/pull/185577
>From 6907dc19ea641e584aa739eee10b13672fd09122 Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga
Date: Mon, 9 Mar 2026 13:32:35 +
Subject: [PATCH] [DA] Consolidate the core logic of the Weak Zero SIV tests
(NFCI)
---
.../llvm/Analysis/DependenceAnalysis.h| 5 +
llvm/lib/Analysis/DependenceAnalysis.cpp | 199 +++---
2 files changed, 80 insertions(+), 124 deletions(-)
diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h
b/llvm/include/llvm/Analysis/DependenceAnalysis.h
index 7ced97c34715b..092280eddbc01 100644
--- a/llvm/include/llvm/Analysis/DependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h
@@ -557,6 +557,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 29e04e59c414a..ed0a19b3332fd 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -1785,77 +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 >= and peeling the
-// 1st iteration will break the dependence.
-// If i = UB, the direction is <= and peeling the
-// last iteration will break the dependence.
-// 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() << "\tDstCoeff = " << *DstCoeff << "\n");
- LLVM_DEBUG(dbgs() << "\tSrcConst = " << *SrcConst << "\n");
- LLVM_DEBUG(dbgs() << "\tDstConst = " << *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-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
https://github.com/kasuga-fj updated
https://github.com/llvm/llvm-project/pull/185577
>From 6907dc19ea641e584aa739eee10b13672fd09122 Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga
Date: Mon, 9 Mar 2026 13:32:35 +
Subject: [PATCH] [DA] Consolidate the core logic of the Weak Zero SIV tests
(NFCI)
---
.../llvm/Analysis/DependenceAnalysis.h| 5 +
llvm/lib/Analysis/DependenceAnalysis.cpp | 199 +++---
2 files changed, 80 insertions(+), 124 deletions(-)
diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h
b/llvm/include/llvm/Analysis/DependenceAnalysis.h
index 7ced97c34715b..092280eddbc01 100644
--- a/llvm/include/llvm/Analysis/DependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h
@@ -557,6 +557,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 29e04e59c414a..ed0a19b3332fd 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -1785,77 +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 >= and peeling the
-// 1st iteration will break the dependence.
-// If i = UB, the direction is <= and peeling the
-// last iteration will break the dependence.
-// 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() << "\tDstCoeff = " << *DstCoeff << "\n");
- LLVM_DEBUG(dbgs() << "\tSrcConst = " << *SrcConst << "\n");
- LLVM_DEBUG(dbgs() << "\tDstConst = " << *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-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
kasuga-fj wrote: > [!WARNING] > This pull request is not mergeable via GitHub because a downstack PR is > open. Once all requirements are satisfied, merge this PR as a stack href="https://app.graphite.com/github/pr/llvm/llvm-project/185577?utm_source=stack-comment-downstack-mergeability-warning"; > >on Graphite. > https://graphite.dev/docs/merge-pull-requests";>Learn more * **#185580** https://app.graphite.com/github/pr/llvm/llvm-project/185580?utm_source=stack-comment-icon"; target="_blank">https://static.graphite.dev/graphite-32x32-black.png"; alt="Graphite" width="10px" height="10px"/> * **#185579** https://app.graphite.com/github/pr/llvm/llvm-project/185579?utm_source=stack-comment-icon"; target="_blank">https://static.graphite.dev/graphite-32x32-black.png"; alt="Graphite" width="10px" height="10px"/> * **#185578** https://app.graphite.com/github/pr/llvm/llvm-project/185578?utm_source=stack-comment-icon"; target="_blank">https://static.graphite.dev/graphite-32x32-black.png"; alt="Graphite" width="10px" height="10px"/> * **#185577** https://app.graphite.com/github/pr/llvm/llvm-project/185577?utm_source=stack-comment-icon"; target="_blank">https://static.graphite.dev/graphite-32x32-black.png"; alt="Graphite" width="10px" height="10px"/> 👈 https://app.graphite.com/github/pr/llvm/llvm-project/185577?utm_source=stack-comment-view-in-graphite"; target="_blank">(View in Graphite) * **#185576** https://app.graphite.com/github/pr/llvm/llvm-project/185576?utm_source=stack-comment-icon"; target="_blank">https://static.graphite.dev/graphite-32x32-black.png"; alt="Graphite" width="10px" height="10px"/> * **#183738** https://app.graphite.com/github/pr/llvm/llvm-project/183738?utm_source=stack-comment-icon"; target="_blank">https://static.graphite.dev/graphite-32x32-black.png"; alt="Graphite" width="10px" height="10px"/> * **#183737** https://app.graphite.com/github/pr/llvm/llvm-project/183737?utm_source=stack-comment-icon"; target="_blank">https://static.graphite.dev/graphite-32x32-black.png"; alt="Graphite" width="10px" height="10px"/> * **#183736** https://app.graphite.com/github/pr/llvm/llvm-project/183736?utm_source=stack-comment-icon"; target="_blank">https://static.graphite.dev/graphite-32x32-black.png"; alt="Graphite" width="10px" height="10px"/> * **#183735** https://app.graphite.com/github/pr/llvm/llvm-project/183735?utm_source=stack-comment-icon"; target="_blank">https://static.graphite.dev/graphite-32x32-black.png"; alt="Graphite" width="10px" height="10px"/> * `main` This stack of pull requests is managed by https://graphite.dev?utm-source=stack-comment";>Graphite. Learn more about https://stacking.dev/?utm_source=stack-comment";>stacking. https://github.com/llvm/llvm-project/pull/185577 ___ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
[llvm-branch-commits] [llvm] [DA] Consolidate the core logic of the Weak Zero SIV tests (NFCI) (PR #185577)
https://github.com/kasuga-fj created
https://github.com/llvm/llvm-project/pull/185577
None
>From 62538e5e95b4cdb76b0866cfc29b4a11fd604748 Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga
Date: Mon, 9 Mar 2026 13:32:35 +
Subject: [PATCH] [DA] Consolidate the core logic of the Weak Zero SIV tests
(NFCI)
---
.../llvm/Analysis/DependenceAnalysis.h| 5 +
llvm/lib/Analysis/DependenceAnalysis.cpp | 199 +++---
2 files changed, 80 insertions(+), 124 deletions(-)
diff --git a/llvm/include/llvm/Analysis/DependenceAnalysis.h
b/llvm/include/llvm/Analysis/DependenceAnalysis.h
index 76e069238f45e..b41a9bfb12a8a 100644
--- a/llvm/include/llvm/Analysis/DependenceAnalysis.h
+++ b/llvm/include/llvm/Analysis/DependenceAnalysis.h
@@ -557,6 +557,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 b052694e5d784..fd5e99a8854df 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -1785,77 +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 >= and peeling the
-// 1st iteration will break the dependence.
-// If i = UB, the direction is <= and peeling the
-// last iteration will break the dependence.
-// 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() << "\tDstCoeff = " << *DstCoeff << "\n");
- LLVM_DEBUG(dbgs() << "\tSrcConst = " << *SrcConst << "\n");
- LLVM_DEBUG(dbgs() << "\tDstConst = " << *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;
-
