https://github.com/kasuga-fj created https://github.com/llvm/llvm-project/pull/179654
None >From 546ddcf452da49523820386d625ac3962ad773c1 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Wed, 4 Feb 2026 13:06:15 +0000 Subject: [PATCH] [DA] Remove "minor algebra" in the RDIV test --- llvm/lib/Analysis/DependenceAnalysis.cpp | 34 +------------------ .../Analysis/DependenceAnalysis/ExactRDIV.ll | 4 +-- .../DependenceAnalysis/rdiv-minor-algebra.ll | 9 +++-- 3 files changed, 7 insertions(+), 40 deletions(-) diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index 51d0c32149330..b870422ef1f55 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -1206,8 +1206,7 @@ DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest, return Subscript::ZIV; if (N == 1) return Subscript::SIV; - if (N == 2 && (SrcLoops.count() == 0 || DstLoops.count() == 0 || - (SrcLoops.count() == 1 && DstLoops.count() == 1))) + if (N == 2 && SrcLoops.count() == 1 && DstLoops.count() == 1) return Subscript::RDIV; return Subscript::MIV; } @@ -2476,18 +2475,9 @@ bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level, // so there's no point in making special versions of the Strong SIV test or // the Weak-crossing SIV test. // -// With minor algebra, this test can also be used for things like -// [c1 + a1*i + a2*j][c2]. -// // Return true if dependence disproved. bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const { - // we have 3 possible situations here: - // 1) [a*i + b] and [c*j + d] - // 2) [a*i + c*j + b] and [d] - // 3) [b] and [a*i + c*j + d] - // We need to find what we've got and get organized - const SCEV *SrcConst, *DstConst; const SCEV *SrcCoeff, *DstCoeff; const Loop *SrcLoop, *DstLoop; @@ -2503,28 +2493,6 @@ bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst, DstConst = DstAddRec->getStart(); DstCoeff = DstAddRec->getStepRecurrence(*SE); DstLoop = DstAddRec->getLoop(); - } else if (SrcAddRec) { - if (const SCEVAddRecExpr *tmpAddRec = - dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) { - SrcConst = tmpAddRec->getStart(); - SrcCoeff = tmpAddRec->getStepRecurrence(*SE); - SrcLoop = tmpAddRec->getLoop(); - DstConst = Dst; - DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE)); - DstLoop = SrcAddRec->getLoop(); - } else - llvm_unreachable("RDIV reached by surprising SCEVs"); - } else if (DstAddRec) { - if (const SCEVAddRecExpr *tmpAddRec = - dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) { - DstConst = tmpAddRec->getStart(); - DstCoeff = tmpAddRec->getStepRecurrence(*SE); - DstLoop = tmpAddRec->getLoop(); - SrcConst = Src; - SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE)); - SrcLoop = DstAddRec->getLoop(); - } else - llvm_unreachable("RDIV reached by surprising SCEVs"); } else llvm_unreachable("RDIV expected at least one AddRec"); return exactRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop, DstLoop, diff --git a/llvm/test/Analysis/DependenceAnalysis/ExactRDIV.ll b/llvm/test/Analysis/DependenceAnalysis/ExactRDIV.ll index b5ece14121686..2d3cb92923a03 100644 --- a/llvm/test/Analysis/DependenceAnalysis/ExactRDIV.ll +++ b/llvm/test/Analysis/DependenceAnalysis/ExactRDIV.ll @@ -556,7 +556,7 @@ define void @rdiv10(ptr %A, ptr %B) nounwind uwtable ssp { ; CHECK-NEXT: Src: store i32 %conv, ptr %arrayidx, align 4 --> Dst: store i32 %conv, ptr %arrayidx, align 4 ; CHECK-NEXT: da analyze - none! ; CHECK-NEXT: Src: store i32 %conv, ptr %arrayidx, align 4 --> Dst: %0 = load i32, ptr %arrayidx4, align 4 -; CHECK-NEXT: da analyze - none! +; CHECK-NEXT: da analyze - flow [=> *|<]! ; CHECK-NEXT: Src: store i32 %conv, ptr %arrayidx, align 4 --> Dst: store i32 %0, ptr %B.addr.11, align 4 ; CHECK-NEXT: da analyze - confused! ; CHECK-NEXT: Src: %0 = load i32, ptr %arrayidx4, align 4 --> Dst: %0 = load i32, ptr %arrayidx4, align 4 @@ -666,7 +666,7 @@ define void @rdiv12(ptr %A, ptr %B) nounwind uwtable ssp { ; CHECK-NEXT: Src: store i32 %conv, ptr %arrayidx, align 4 --> Dst: store i32 %conv, ptr %arrayidx, align 4 ; CHECK-NEXT: da analyze - none! ; CHECK-NEXT: Src: store i32 %conv, ptr %arrayidx, align 4 --> Dst: %0 = load i32, ptr %arrayidx4, align 4 -; CHECK-NEXT: da analyze - flow [* *|<]! +; CHECK-NEXT: da analyze - flow [=> *|<]! ; CHECK-NEXT: Src: store i32 %conv, ptr %arrayidx, align 4 --> Dst: store i32 %0, ptr %B.addr.11, align 4 ; CHECK-NEXT: da analyze - confused! ; CHECK-NEXT: Src: %0 = load i32, ptr %arrayidx4, align 4 --> Dst: %0 = load i32, ptr %arrayidx4, align 4 diff --git a/llvm/test/Analysis/DependenceAnalysis/rdiv-minor-algebra.ll b/llvm/test/Analysis/DependenceAnalysis/rdiv-minor-algebra.ll index dab4b9ae48611..0bfc612690370 100644 --- a/llvm/test/Analysis/DependenceAnalysis/rdiv-minor-algebra.ll +++ b/llvm/test/Analysis/DependenceAnalysis/rdiv-minor-algebra.ll @@ -12,15 +12,14 @@ ; } ; } ; -; FIXME: DependenceAnalysis currently detects no dependency between the two -; stores, but it does exist. +; There is a dependency between the two stores. ; ; memory access | (i, j) == (1, 1) ; ---------------------|------------------ ; A[3*i - 2] | A[-2] ; -; The root cause is that RDIV performs "minor algebra" and transforms the -; subscripts as follows: +; Previously, this dependency was missed because RDIV performs "minor algebra" +; and transforms the subscripts as follows: ; ; A[-2] and A[INT64_MAX*i + INT64_MAX*j] ; @@ -44,7 +43,7 @@ define void @f(ptr %A) { ; CHECK-SYMBOLIC-RDIV-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 0, ptr %gep.0, align 1 ; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - consistent output [S]! ; CHECK-SYMBOLIC-RDIV-NEXT: Src: store i8 0, ptr %gep.0, align 1 --> Dst: store i8 1, ptr %gep.1, align 1 -; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - none! +; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - output [*|<]! ; CHECK-SYMBOLIC-RDIV-NEXT: Src: store i8 1, ptr %gep.1, align 1 --> Dst: store i8 1, ptr %gep.1, align 1 ; CHECK-SYMBOLIC-RDIV-NEXT: da analyze - output [* *]! ; _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
