https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/157086
>From 9f8794a071e152cf128dc03d9994c884fecf5d12 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Fri, 5 Sep 2025 11:41:29 +0000 Subject: [PATCH 1/2] [DA] Add overflow check in ExactSIV --- llvm/lib/Analysis/DependenceAnalysis.cpp | 14 +++++++++++++- llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll | 2 +- 2 files changed, 14 insertions(+), 2 deletions(-) diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp index 0f77a1410e83b..6e576e866b310 100644 --- a/llvm/lib/Analysis/DependenceAnalysis.cpp +++ b/llvm/lib/Analysis/DependenceAnalysis.cpp @@ -1170,6 +1170,15 @@ const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L, 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 *minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B, + ScalarEvolution &SE) { + if (SE.willNotOverflow(Instruction::Sub, /*Signed=*/true, A, B)) + return SE.getMinusSCEV(A, B); + return nullptr; +} + // testZIV - // When we have a pair of subscripts of the form [c1] and [c2], // where c1 and c2 are both loop invariant, we attack it using @@ -1626,7 +1635,9 @@ bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, assert(0 < Level && Level <= CommonLevels && "Level out of range"); Level--; Result.Consistent = false; - const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); + const SCEV *Delta = minusSCEVNoSignedOverflow(DstConst, SrcConst, *SE); + if (!Delta) + return false; LLVM_DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff), Delta, CurLoop); @@ -1716,6 +1727,7 @@ bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff, // explore directions unsigned NewDirection = Dependence::DVEntry::NONE; APInt LowerDistance, UpperDistance; + // TODO: Overflow check may be needed. if (TA.sgt(TB)) { LowerDistance = (TY - TX) + (TA - TB) * TL; UpperDistance = (TY - TX) + (TA - TB) * TU; diff --git a/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll b/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll index 2a809c32d7d21..e8e7cb11bb23e 100644 --- a/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll +++ b/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll @@ -841,7 +841,7 @@ define void @exact14(ptr %A) { ; CHECK-SIV-ONLY-NEXT: Src: store i8 0, ptr %idx.0, align 1 --> Dst: store i8 0, ptr %idx.0, align 1 ; CHECK-SIV-ONLY-NEXT: da analyze - none! ; CHECK-SIV-ONLY-NEXT: Src: store i8 0, ptr %idx.0, align 1 --> Dst: store i8 1, ptr %idx.1, align 1 -; CHECK-SIV-ONLY-NEXT: da analyze - none! +; CHECK-SIV-ONLY-NEXT: da analyze - output [*|<]! ; CHECK-SIV-ONLY-NEXT: Src: store i8 1, ptr %idx.1, align 1 --> Dst: store i8 1, ptr %idx.1, align 1 ; CHECK-SIV-ONLY-NEXT: da analyze - none! ; >From a34c3208d903906caf5b9435f1705f695a68277e Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Tue, 16 Sep 2025 13:12:16 +0000 Subject: [PATCH 2/2] fix comment --- llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll b/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll index e8e7cb11bb23e..6f33e2314ffba 100644 --- a/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll +++ b/llvm/test/Analysis/DependenceAnalysis/ExactSIV.ll @@ -815,8 +815,8 @@ for.end: ; preds = %for.body ;; A[3*i - 2] = 1; ;; } ;; -;; FIXME: DependencyAnalsysis currently detects no dependency between -;; `A[-6*i + INT64_MAX]` and `A[3*i - 2]`, but it does exist. For example, +;; There exists dependency between `A[-6*i + INT64_MAX]` and `A[3*i - 2]`. +;; For example, ;; ;; | memory location | -6*i + INT64_MAX | 3*i - 2 ;; |------------------------|------------------------|----------- _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
