https://github.com/kasuga-fj updated
https://github.com/llvm/llvm-project/pull/148241
>From d914ea5f3c44387570cab65ce9a507ebf429f827 Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga <kasuga.ryot...@fujitsu.com>
Date: Fri, 11 Jul 2025 13:10:44 +0000
Subject: [PATCH 1/3] [DA] Add check for base pointer invariance
---
llvm/lib/Analysis/DependenceAnalysis.cpp | 16 ++++++++++++++++
.../DependenceAnalysis/FlipFlopBaseAddress.ll | 18 +++++++++---------
2 files changed, 25 insertions(+), 9 deletions(-)
diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp
b/llvm/lib/Analysis/DependenceAnalysis.cpp
index 428342f51ad2e..07bf560772c8c 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -3383,6 +3383,10 @@ bool DependenceInfo::tryDelinearize(Instruction *Src,
Instruction *Dst,
SrcSubscripts, DstSubscripts))
return false;
+ assert(isLoopInvariant(SrcBase, SrcLoop) &&
+ isLoopInvariant(DstBase, DstLoop) &&
+ "Expected SrcBase and DstBase to be loop invariant");
+
int Size = SrcSubscripts.size();
LLVM_DEBUG({
dbgs() << "\nSrcSubscripts: ";
@@ -3666,6 +3670,18 @@ DependenceInfo::depends(Instruction *Src, Instruction
*Dst,
SCEVUnionPredicate(Assume, *SE));
}
+ // Even if the base pointers are the same, they may not be loop-invariant. It
+ // could lead to incorrect results, as we're analyzing loop-carried
+ // dependencies.
+ Loop *SrcLoop = LI->getLoopFor(Src->getParent());
+ Loop *DstLoop = LI->getLoopFor(Dst->getParent());
+ if (!isLoopInvariant(SrcBase, SrcLoop) ||
+ !isLoopInvariant(DstBase, DstLoop)) {
+ LLVM_DEBUG(dbgs() << "The base pointer is not loop invariant.\n");
+ return std::make_unique<Dependence>(Src, Dst,
+ SCEVUnionPredicate(Assume, *SE));
+ }
+
uint64_t EltSize = SrcLoc.Size.toRaw();
const SCEV *SrcEv = SE->getMinusSCEV(SrcSCEV, SrcBase);
const SCEV *DstEv = SE->getMinusSCEV(DstSCEV, DstBase);
diff --git a/llvm/test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll
b/llvm/test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll
index 3e3426afab0f7..52cab0f77e73e 100644
--- a/llvm/test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll
+++ b/llvm/test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll
@@ -8,11 +8,11 @@
define float @bug41488_test1(float %f) {
; CHECK-LABEL: 'bug41488_test1'
; CHECK-NEXT: Src: %0 = load float, ptr %p, align 4 --> Dst: %0 = load float,
ptr %p, align 4
-; CHECK-NEXT: da analyze - input [*]!
+; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: %0 = load float, ptr %p, align 4 --> Dst: store float %f,
ptr %q, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store float %f, ptr %q, align 4 --> Dst: store float %f,
ptr %q, align 4
-; CHECK-NEXT: da analyze - output [*]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
%g = alloca float, align 4
@@ -34,11 +34,11 @@ for.cond.cleanup:
define void @bug41488_test2(i32 %n) {
; CHECK-LABEL: 'bug41488_test2'
; CHECK-NEXT: Src: %0 = load float, ptr %p, align 4 --> Dst: %0 = load float,
ptr %p, align 4
-; CHECK-NEXT: da analyze - input [*]!
+; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: %0 = load float, ptr %p, align 4 --> Dst: store float
0.000000e+00, ptr %q, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store float 0.000000e+00, ptr %q, align 4 --> Dst: store
float 0.000000e+00, ptr %q, align 4
-; CHECK-NEXT: da analyze - output [*]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
%g = alloca float, align 4
@@ -68,7 +68,7 @@ define void @bug53942_foo(i32 noundef %n, ptr noalias
nocapture noundef writeonl
; CHECK-NEXT: Src: %.pre = load double, ptr %B, align 8 --> Dst: store double
%.pre, ptr %arrayidx2, align 8
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store double %.pre, ptr %arrayidx2, align 8 --> Dst: store
double %.pre, ptr %arrayidx2, align 8
-; CHECK-NEXT: da analyze - output [*]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
%cmp8 = icmp sgt i32 %n, 1
@@ -99,11 +99,11 @@ for.body: ; preds =
%for.body.preheader,
define void @bug53942_bar(i32 noundef %n, ptr noalias noundef %A, ptr noalias
noundef %B) {
; CHECK-LABEL: 'bug53942_bar'
; CHECK-NEXT: Src: %0 = load double, ptr %arrayidx, align 8 --> Dst: %0 =
load double, ptr %arrayidx, align 8
-; CHECK-NEXT: da analyze - input [*]!
+; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: %0 = load double, ptr %arrayidx, align 8 --> Dst: store
double %0, ptr %arrayidx8, align 8
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store double %0, ptr %arrayidx8, align 8 --> Dst: store
double %0, ptr %arrayidx8, align 8
-; CHECK-NEXT: da analyze - output [*]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
br label %for.cond
@@ -173,7 +173,7 @@ for.end: ; preds =
%for.cond.cleanup
define void @non_invariant_baseptr_with_identical_obj(ptr %A) {
; CHECK-LABEL: 'non_invariant_baseptr_with_identical_obj'
; CHECK-NEXT: Src: store i32 1, ptr %idx, align 4 --> Dst: store i32 1, ptr
%idx, align 4
-; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - confused!
;
entry:
br label %loop.i.header
@@ -222,7 +222,7 @@ exit:
define void @non_invariant_baseptr_with_identical_obj2(ptr %A) {
; CHECK-LABEL: 'non_invariant_baseptr_with_identical_obj2'
; CHECK-NEXT: Src: store i32 1, ptr %idx, align 4 --> Dst: store i32 1, ptr
%idx, align 4
-; CHECK-NEXT: da analyze - none!
+; CHECK-NEXT: da analyze - confused!
;
entry:
br label %loop.i.header
>From 607505e39e0fb9b781e9457a81b8e0868f5c7baa Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga <kasuga.ryot...@fujitsu.com>
Date: Fri, 11 Jul 2025 22:55:11 +0900
Subject: [PATCH 2/3] Remove FIXME label
---
.../test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/llvm/test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll
b/llvm/test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll
index 52cab0f77e73e..25ecf3112b941 100644
--- a/llvm/test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll
+++ b/llvm/test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll
@@ -166,7 +166,7 @@ for.end: ; preds =
%for.cond.cleanup
; (j % 2 == 0 ? A[i][j] : A[i][j+1]) = 1;
; }
;
-; FIXME: There are loop-carried dependencies between the store instruction. For
+; There are loop-carried dependencies between the store instruction. For
; example, the value of %ptr0 when (i, j) = (0, 1) is %A+8, which is the same
; as when (i, j) = (0, 2).
@@ -216,8 +216,8 @@ exit:
; Similar to the above case, but ptr0 is loop-invariant with respsect to the
; k-loop.
;
-; FIXME: Same as the above case, there are loop-carried dependencies between
-; the store.
+; Same as the above case, there are loop-carried dependencies between the
+; store.
define void @non_invariant_baseptr_with_identical_obj2(ptr %A) {
; CHECK-LABEL: 'non_invariant_baseptr_with_identical_obj2'
>From b10a5ab6024d977a9d7c920f55295bce055b81cf Mon Sep 17 00:00:00 2001
From: Ryotaro Kasuga <kasuga.ryot...@fujitsu.com>
Date: Sat, 12 Jul 2025 02:31:32 +0900
Subject: [PATCH 3/3] Update tests
---
llvm/lib/Analysis/DependenceAnalysis.cpp | 3 ++-
llvm/test/Analysis/DependenceAnalysis/Banerjee.ll | 6 +++---
llvm/test/Analysis/DependenceAnalysis/GCD.ll | 8 ++++----
llvm/test/Analysis/DependenceAnalysis/NonAffineExpr.ll | 2 +-
llvm/test/Analysis/DependenceAnalysis/Preliminary.ll | 2 +-
.../PreliminaryNoValidityCheckFixedSize.ll | 4 ++--
llvm/test/Analysis/DependenceAnalysis/SymbolicRDIV.ll | 2 +-
7 files changed, 14 insertions(+), 13 deletions(-)
diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp
b/llvm/lib/Analysis/DependenceAnalysis.cpp
index 07bf560772c8c..5188830b831a1 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -3672,7 +3672,8 @@ DependenceInfo::depends(Instruction *Src, Instruction
*Dst,
// Even if the base pointers are the same, they may not be loop-invariant. It
// could lead to incorrect results, as we're analyzing loop-carried
- // dependencies.
+ // dependencies. Src and Dst can be in different loops, so we need to check
+ // the base pointer is invariant in both loops.
Loop *SrcLoop = LI->getLoopFor(Src->getParent());
Loop *DstLoop = LI->getLoopFor(Dst->getParent());
if (!isLoopInvariant(SrcBase, SrcLoop) ||
diff --git a/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll
b/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll
index d3301520fd107..e0def901d1759 100644
--- a/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll
+++ b/llvm/test/Analysis/DependenceAnalysis/Banerjee.ll
@@ -113,7 +113,7 @@ define void @banerjee1(ptr %A, ptr %B, i64 %m, i64 %n)
nounwind uwtable ssp {
; CHECK-NEXT: Src: %2 = load i64, ptr %arrayidx6, align 8 --> Dst: store i64
%2, ptr %B.addr.12, align 8
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i64 %2, ptr %B.addr.12, align 8 --> Dst: store i64
%2, ptr %B.addr.12, align 8
-; CHECK-NEXT: da analyze - output [* *]!
+; CHECK-NEXT: da analyze - confused!
;
; NORMALIZE-LABEL: 'banerjee1'
; NORMALIZE-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64
0, ptr %arrayidx, align 8
@@ -127,7 +127,7 @@ define void @banerjee1(ptr %A, ptr %B, i64 %m, i64 %n)
nounwind uwtable ssp {
; NORMALIZE-NEXT: Src: %2 = load i64, ptr %arrayidx6, align 8 --> Dst: store
i64 %2, ptr %B.addr.12, align 8
; NORMALIZE-NEXT: da analyze - confused!
; NORMALIZE-NEXT: Src: store i64 %2, ptr %B.addr.12, align 8 --> Dst: store
i64 %2, ptr %B.addr.12, align 8
-; NORMALIZE-NEXT: da analyze - output [* *]!
+; NORMALIZE-NEXT: da analyze - confused!
;
; DELIN-LABEL: 'banerjee1'
; DELIN-NEXT: Src: store i64 0, ptr %arrayidx, align 8 --> Dst: store i64 0,
ptr %arrayidx, align 8
@@ -141,7 +141,7 @@ define void @banerjee1(ptr %A, ptr %B, i64 %m, i64 %n)
nounwind uwtable ssp {
; DELIN-NEXT: Src: %2 = load i64, ptr %arrayidx6, align 8 --> Dst: store i64
%2, ptr %B.addr.12, align 8
; DELIN-NEXT: da analyze - confused!
; DELIN-NEXT: Src: store i64 %2, ptr %B.addr.12, align 8 --> Dst: store i64
%2, ptr %B.addr.12, align 8
-; DELIN-NEXT: da analyze - output [* *]!
+; DELIN-NEXT: da analyze - confused!
;
entry:
%cmp4 = icmp sgt i64 %n, 0
diff --git a/llvm/test/Analysis/DependenceAnalysis/GCD.ll
b/llvm/test/Analysis/DependenceAnalysis/GCD.ll
index c0e1362c82b50..03343e7a98211 100644
--- a/llvm/test/Analysis/DependenceAnalysis/GCD.ll
+++ b/llvm/test/Analysis/DependenceAnalysis/GCD.ll
@@ -398,7 +398,7 @@ define void @gcd6(i64 %n, ptr %A, ptr %B) nounwind uwtable
ssp {
; CHECK-NEXT: Src: %2 = load i32, ptr %arrayidx9, align 4 --> Dst: store i32
%2, ptr %B.addr.12, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i32 %2, ptr %B.addr.12, align 4 --> Dst: store i32
%2, ptr %B.addr.12, align 4
-; CHECK-NEXT: da analyze - output [* *]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
%cmp4 = icmp sgt i64 %n, 0
@@ -475,7 +475,7 @@ define void @gcd7(i32 %n, ptr %A, ptr %B) nounwind uwtable
ssp {
; CHECK-NEXT: Src: %11 = load i32, ptr %arrayidx12, align 4 --> Dst: store
i32 %11, ptr %B.addr.12, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i32 %11, ptr %B.addr.12, align 4 --> Dst: store i32
%11, ptr %B.addr.12, align 4
-; CHECK-NEXT: da analyze - output [* *]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
%0 = zext i32 %n to i64
@@ -566,7 +566,7 @@ define void @gcd8(i32 %n, ptr %A, ptr %B) nounwind uwtable
ssp {
; CHECK-NEXT: Src: %5 = load i32, ptr %arrayidx12, align 4 --> Dst: store i32
%5, ptr %B.addr.12, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i32 %5, ptr %B.addr.12, align 4 --> Dst: store i32
%5, ptr %B.addr.12, align 4
-; CHECK-NEXT: da analyze - output [* *]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
%cmp4 = icmp sgt i32 %n, 0
@@ -650,7 +650,7 @@ define void @gcd9(i32 %n, ptr %A, ptr %B) nounwind uwtable
ssp {
; CHECK-NEXT: Src: %11 = load i32, ptr %arrayidx12, align 4 --> Dst: store
i32 %11, ptr %B.addr.12, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i32 %11, ptr %B.addr.12, align 4 --> Dst: store i32
%11, ptr %B.addr.12, align 4
-; CHECK-NEXT: da analyze - output [* *]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
%0 = zext i32 %n to i64
diff --git a/llvm/test/Analysis/DependenceAnalysis/NonAffineExpr.ll
b/llvm/test/Analysis/DependenceAnalysis/NonAffineExpr.ll
index d983bd49d49d6..3e110acbefb20 100644
--- a/llvm/test/Analysis/DependenceAnalysis/NonAffineExpr.ll
+++ b/llvm/test/Analysis/DependenceAnalysis/NonAffineExpr.ll
@@ -12,7 +12,7 @@ define void @f(ptr %a, i32 %n, i1 %arg) align 2 {
; CHECK-NEXT: Src: %t.2 = load ptr, ptr %a, align 4 --> Dst: %t.4 = load i32,
ptr %t.3, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: %t.4 = load i32, ptr %t.3, align 4 --> Dst: %t.4 = load
i32, ptr %t.3, align 4
-; CHECK-NEXT: da analyze - input [* *]!
+; CHECK-NEXT: da analyze - confused!
;
for.preheader:
%t.0 = ashr exact i32 %n, 3
diff --git a/llvm/test/Analysis/DependenceAnalysis/Preliminary.ll
b/llvm/test/Analysis/DependenceAnalysis/Preliminary.ll
index 4ab87771417e5..8cb0e2ac770dc 100644
--- a/llvm/test/Analysis/DependenceAnalysis/Preliminary.ll
+++ b/llvm/test/Analysis/DependenceAnalysis/Preliminary.ll
@@ -69,7 +69,7 @@ define void @p2(i64 %n, ptr %A, ptr %B) nounwind uwtable ssp {
; CHECK-NEXT: Src: %0 = load i64, ptr %arrayidx17, align 8 --> Dst: store i64
%0, ptr %B.addr.24, align 8
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i64 %0, ptr %B.addr.24, align 8 --> Dst: store i64
%0, ptr %B.addr.24, align 8
-; CHECK-NEXT: da analyze - output [* * *]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
%cmp10 = icmp sgt i64 %n, 0
diff --git
a/llvm/test/Analysis/DependenceAnalysis/PreliminaryNoValidityCheckFixedSize.ll
b/llvm/test/Analysis/DependenceAnalysis/PreliminaryNoValidityCheckFixedSize.ll
index 404018707c0a5..e67cae7d39a75 100644
---
a/llvm/test/Analysis/DependenceAnalysis/PreliminaryNoValidityCheckFixedSize.ll
+++
b/llvm/test/Analysis/DependenceAnalysis/PreliminaryNoValidityCheckFixedSize.ll
@@ -28,7 +28,7 @@ define void @p2(i64 %n, ptr %A, ptr %B) nounwind uwtable ssp {
; CHECK-NEXT: Src: %0 = load i64, ptr %arrayidx17, align 8 --> Dst: store i64
%0, ptr %B.addr.24, align 8
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i64 %0, ptr %B.addr.24, align 8 --> Dst: store i64
%0, ptr %B.addr.24, align 8
-; CHECK-NEXT: da analyze - output [* * *]!
+; CHECK-NEXT: da analyze - confused!
;
; LIN-LABEL: 'p2'
; LIN-NEXT: Src: store i64 %i.011, ptr %arrayidx8, align 8 --> Dst: store i64
%i.011, ptr %arrayidx8, align 8
@@ -42,7 +42,7 @@ define void @p2(i64 %n, ptr %A, ptr %B) nounwind uwtable ssp {
; LIN-NEXT: Src: %0 = load i64, ptr %arrayidx17, align 8 --> Dst: store i64
%0, ptr %B.addr.24, align 8
; LIN-NEXT: da analyze - confused!
; LIN-NEXT: Src: store i64 %0, ptr %B.addr.24, align 8 --> Dst: store i64 %0,
ptr %B.addr.24, align 8
-; LIN-NEXT: da analyze - output [* * *]!
+; LIN-NEXT: da analyze - confused!
;
entry:
%cmp10 = icmp sgt i64 %n, 0
diff --git a/llvm/test/Analysis/DependenceAnalysis/SymbolicRDIV.ll
b/llvm/test/Analysis/DependenceAnalysis/SymbolicRDIV.ll
index f64a7483d7b66..8b9aa257a7c57 100644
--- a/llvm/test/Analysis/DependenceAnalysis/SymbolicRDIV.ll
+++ b/llvm/test/Analysis/DependenceAnalysis/SymbolicRDIV.ll
@@ -437,7 +437,7 @@ define void @symbolicrdiv6(ptr %A, ptr %B, i64 %n1, i64
%n2) nounwind uwtable ss
; CHECK-NEXT: Src: %0 = load i32, ptr %arrayidx4, align 4 --> Dst: store i32
%0, ptr %B.addr.12, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i32 %0, ptr %B.addr.12, align 4 --> Dst: store i32
%0, ptr %B.addr.12, align 4
-; CHECK-NEXT: da analyze - output [* *]!
+; CHECK-NEXT: da analyze - confused!
;
entry:
%cmp4 = icmp eq i64 %n1, 0
_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
