shylie/llvm-project
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
llvm-project/llvm/test/Analysis/DependenceAnalysis/FlipFlopBaseAddress.ll
Ryotaro Kasuga b06f10d96c
[DA] Add check for base pointer invariance (#148241) 
As specified in #53942, DA assumes base pointer invariance in its
process. Some cases were fixed by #116628. However, that PR only
addressed the parts related to AliasAnalysis, so the original issue
persists in later stages, especially when the AliasAnalysis results in
`MustAlias`.
This patch insert an explicit loop-invariant checks for the base pointer
and skips analysis when it is not loop-invariant.

Fix the cases added in #148240.
2025-07-26 03:25:01 +09:00

317 lines
11 KiB
LLVM
Raw Permalink Blame History

; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5
; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 \
; RUN: | FileCheck %s
; Check that dependence analysis correctly handles flip-flop of base addresses.
; Bug 41488 - https://github.com/llvm/llvm-project/issues/41488
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 - 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 - confused!
;
entry:
%g = alloca float, align 4
%h = alloca float, align 4
br label %for.body
for.body:
%p = phi float* [ %g, %entry ], [ %q, %for.body ]
%q = phi float* [ %h, %entry ], [ %p, %for.body ]
%0 = load float, float* %p, align 4
store float %f, float* %q, align 4
%branch_cond = fcmp ugt float %0, 0.0
br i1 %branch_cond, label %for.cond.cleanup, label %for.body
for.cond.cleanup:
ret float %f
}
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 - 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 - confused!
;
entry:
%g = alloca float, align 4
%h = alloca float, align 4
br label %for.body
for.body:
%i = phi i32 [0, %entry ], [ %inc, %for.body ]
%p = phi float* [ %g, %entry ], [ %q, %for.body ]
%q = phi float* [ %h, %entry ], [ %p, %for.body ]
%0 = load float, float* %p, align 4
store float 0.0, float* %q, align 4
%inc = add nuw i32 %i, 1
%branch_cond = icmp ult i32 %i, %n
br i1 %branch_cond, label %for.body, label %for.cond.cleanup
for.cond.cleanup:
ret void
}
; Bug 53942 - https://github.com/llvm/llvm-project/issues/53942
define void @bug53942_foo(i32 noundef %n, ptr noalias nocapture noundef writeonly %A, ptr noalias nocapture noundef %B) {
; CHECK-LABEL: 'bug53942_foo'
; CHECK-NEXT: Src: %.pre = load double, ptr %B, align 8 --> Dst: %.pre = load double, ptr %B, align 8
; CHECK-NEXT: da analyze - consistent input [S]!
; 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 - confused!
;
entry:
%cmp8 = icmp sgt i32 %n, 1
br i1 %cmp8, label %for.body.preheader, label %for.cond.cleanup
for.body.preheader: ; preds = %entry
%wide.trip.count = zext nneg i32 %n to i64
br label %for.body
for.cond.cleanup: ; preds = %for.body, %entry
ret void
for.body: ; preds = %for.body.preheader, %for.body
%indvars.iv = phi i64 [ 1, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
%ptr1.011 = phi ptr [ %A, %for.body.preheader ], [ %ptr2.09, %for.body ]
%ptr2.09 = phi ptr [ %B, %for.body.preheader ], [ %ptr1.011, %for.body ]
%.pre = load double, ptr %B, align 8
%arrayidx2 = getelementptr inbounds double, ptr %ptr1.011, i64 %indvars.iv
store double %.pre, ptr %arrayidx2, align 8
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count
br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}
; Bug 53942 - https://github.com/llvm/llvm-project/issues/53942
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 - 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 - confused!
;
entry:
br label %for.cond
for.cond: ; preds = %for.inc, %entry
%i.0 = phi i32 [ 1, %entry ], [ %inc, %for.inc ]
%cmp = icmp slt i32 %i.0, %n
br i1 %cmp, label %for.body, label %for.cond.cleanup
for.cond.cleanup: ; preds = %for.cond
br label %for.end
for.body: ; preds = %for.cond
%and = and i32 %i.0, 2
%tobool.not = icmp eq i32 %and, 0
br i1 %tobool.not, label %cond.false, label %cond.true
cond.true: ; preds = %for.body
br label %cond.end
cond.false: ; preds = %for.body
br label %cond.end
cond.end: ; preds = %cond.false, %cond.true
%cond = phi ptr [ %A, %cond.true ], [ %B, %cond.false ]
%and1 = and i32 %i.0, 2
%tobool2.not = icmp eq i32 %and1, 0
br i1 %tobool2.not, label %cond.false4, label %cond.true3
cond.true3: ; preds = %cond.end
br label %cond.end5
cond.false4: ; preds = %cond.end
br label %cond.end5
cond.end5: ; preds = %cond.false4, %cond.true3
%cond6 = phi ptr [ %B, %cond.true3 ], [ %A, %cond.false4 ]
%sub = add nsw i32 %i.0, -1
%idxprom = sext i32 %sub to i64
%arrayidx = getelementptr inbounds double, ptr %cond6, i64 %idxprom
%0 = load double, ptr %arrayidx, align 8
%idxprom7 = zext nneg i32 %i.0 to i64
%arrayidx8 = getelementptr inbounds double, ptr %cond, i64 %idxprom7
store double %0, ptr %arrayidx8, align 8
br label %for.inc
for.inc: ; preds = %cond.end5
%inc = add nuw nsw i32 %i.0, 1
br label %for.cond
for.end: ; preds = %for.cond.cleanup
ret void
}
; Pseudo-code for the following IR:
;
; void f(int A[][42]) {
; for (int i = 0; i < 100; i++)
; for (int j = 0; j < 41; j++)
; (j % 2 == 0 ? A[i][j] : A[i][j+1]) = 1;
; }
;
; 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).
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 - confused!
;
entry:
br label %loop.i.header
loop.i.header:
%i = phi i32 [ 0, %entry ], [ %i.inc, %loop.i.latch ]
%A1 = getelementptr i32, ptr %A, i32 1
br label %loop.j
loop.j:
%j = phi i32 [ 0, %loop.i.header ], [ %j.inc, %loop.j ]
%ptr0 = phi ptr [ %A, %loop.i.header ], [ %ptr1, %loop.j ]
%ptr1 = phi ptr [ %A1, %loop.i.header ], [ %ptr0, %loop.j ]
%idx = getelementptr [42 x i32], ptr %ptr0, i32 %i, i32 %j
store i32 1, ptr %idx
%j.inc = add i32 %j, 1
%cmp.j = icmp slt i32 %j.inc, 41
br i1 %cmp.j, label %loop.j, label %loop.i.latch
loop.i.latch:
%i.inc = add i32 %i, 1
%cmp.i = icmp slt i32 %i.inc, 100
br i1 %cmp.i, label %loop.i.header, label %exit
exit:
ret void
}
; Pseudo-code for the following IR:
;
; void f(int A[][42][42]) {
; for (int i = 0; i < 100; i++)
; for (int j = 0; j < 41; j++) {
; int *ptr0 = (j % 2 == 0 ? A[i][j] : A[i][j+1]);
; for (int k = 0; k < 42; k++)
; ptr0[k] = 1;
; }
; }
;
; Similar to the above case, but ptr0 is loop-invariant with respsect to the
; k-loop.
;
; 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'
; CHECK-NEXT: Src: store i32 1, ptr %idx, align 4 --> Dst: store i32 1, ptr %idx, align 4
; CHECK-NEXT: da analyze - confused!
;
entry:
br label %loop.i.header
loop.i.header:
%i = phi i32 [ 0, %entry ], [ %i.inc, %loop.i.latch ]
%A1 = getelementptr i32, ptr %A, i32 1
br label %loop.j.header
loop.j.header:
%j = phi i32 [ 0, %loop.i.header ], [ %j.inc, %loop.j.latch ]
%ptr0 = phi ptr [ %A, %loop.i.header ], [ %ptr1, %loop.j.latch ]
%ptr1 = phi ptr [ %A1, %loop.i.header ], [ %ptr0, %loop.j.latch ]
br label %loop.k
loop.k:
%k = phi i32 [ 0, %loop.j.header ], [ %k.inc, %loop.k ]
%idx = getelementptr [42 x [42 x i32]], ptr %ptr0, i32 %i, i32 %k, i32 %j
store i32 1, ptr %idx
%k.inc = add i32 %k, 1
%cmp.k = icmp slt i32 %k.inc, 42
br i1 %cmp.k, label %loop.k, label %loop.j.latch
loop.j.latch:
%j.inc = add i32 %j, 1
%cmp.j = icmp slt i32 %j.inc, 41
br i1 %cmp.j, label %loop.j.header, label %loop.i.latch
loop.i.latch:
%i.inc = add i32 %i, 1
%cmp.i = icmp slt i32 %i.inc, 100
br i1 %cmp.i, label %loop.i.header, label %exit
exit:
ret void
}
; Pseudo-code that is approximately semantically equivalent to the below IR:
;
; void f(int A[][32]) {
; for (int i = 0; i < 100; i++)
; for (int j = 0; j < 15; j++) {
; int offset = (j % 2 == 0) ? 1 : 0;
; A[i][2 * j + offset + 0] = 1;
; A[i][2 * j + offset + 1] = 1;
; }
; }
;
; There are loop-carried dependencies between the two stores. For example,
; A[0][2] is accessed from both the former one when (i, j) = (0, 1) and the
; latter one when (i, j) = (0, 0).
;
define void @non_invariant_baseptr_with_identical_obj3(ptr %A) {
; CHECK-LABEL: 'non_invariant_baseptr_with_identical_obj3'
; CHECK-NEXT: Src: store i32 1, ptr %idx0, align 4 --> Dst: store i32 1, ptr %idx0, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i32 1, ptr %idx0, align 4 --> Dst: store i32 1, ptr %idx1, align 4
; CHECK-NEXT: da analyze - confused!
; CHECK-NEXT: Src: store i32 1, ptr %idx1, align 4 --> Dst: store i32 1, ptr %idx1, align 4
; CHECK-NEXT: da analyze - confused!
;
entry:
br label %loop.i.header
loop.i.header:
%i = phi i32 [ 0, %entry ], [ %i.inc, %loop.i.latch ]
%A1 = getelementptr i32, ptr %A, i32 1
br label %loop.j
loop.j:
%j = phi i32 [ 0, %loop.i.header ], [ %j.inc, %loop.j ]
%ptr0 = phi ptr [ %A1, %loop.i.header ], [ %ptr1, %loop.j ]
%ptr1 = phi ptr [ %A, %loop.i.header ], [ %ptr0, %loop.j ]
%j2_0 = shl i32 %j, 1
%j2_1 = add i32 %j2_0, 1
%idx0 = getelementptr [32 x i32], ptr %ptr0, i32 %i, i32 %j2_0
%idx1 = getelementptr [32 x i32], ptr %ptr0, i32 %i, i32 %j2_1
store i32 1, ptr %idx0
store i32 1, ptr %idx1
%j.inc = add i32 %j, 1
%cmp.j = icmp slt i32 %j.inc, 15
br i1 %cmp.j, label %loop.j, label %loop.i.latch
loop.i.latch:
%i.inc = add i32 %i, 1
%cmp.i = icmp slt i32 %i.inc, 100
br i1 %cmp.i, label %loop.i.header, label %exit
exit:
ret void
}
Reference in New Issue View Git Blame Copy Permalink