xref: /llvm-project/llvm/test/Analysis/LoopAccessAnalysis/loops-with-indirect-reads-and-writes.ll (revision a3ad5faa321848376b277db369313c80d3df2152) 
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 3
2; RUN: opt -passes='print<access-info>' -disable-output %s 2>&1 | FileCheck %s
3
4target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
5
6; Test cases for https://github.com/llvm/llvm-project/issues/69744.
7; Note that both loops in the tests are needed to incorrectly determine that
8; the loops are safe with runtime checks via FoundNonConstantDistanceDependence
9; handling code in LAA.
10
11define void @test_indirect_read_write_loop_also_modifies_pointer_array(ptr noundef %arr) {
12; CHECK-LABEL: 'test_indirect_read_write_loop_also_modifies_pointer_array'
13; CHECK-NEXT:    loop.1:
14; CHECK-NEXT:      Report: could not determine number of loop iterations
15; CHECK-NEXT:      Dependences:
16; CHECK-NEXT:      Run-time memory checks:
17; CHECK-NEXT:      Grouped accesses:
18; CHECK-EMPTY:
19; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
20; CHECK-NEXT:      SCEV assumptions:
21; CHECK-EMPTY:
22; CHECK-NEXT:      Expressions re-written:
23; CHECK-NEXT:    loop.2:
24; CHECK-NEXT:      Report: unsafe dependent memory operations in loop. Use #pragma clang loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
25; CHECK-NEXT:  Unsafe indirect dependence.
26; CHECK-NEXT:      Dependences:
27; CHECK-NEXT:        IndirectUnsafe:
28; CHECK-NEXT:            %l.2 = load i64, ptr %l.1, align 8, !tbaa !4 ->
29; CHECK-NEXT:            store i64 %inc, ptr %l.1, align 8, !tbaa !4
30; CHECK-EMPTY:
31; CHECK-NEXT:        Unknown:
32; CHECK-NEXT:            %l.1 = load ptr, ptr %gep.iv.1, align 8, !tbaa !0 ->
33; CHECK-NEXT:            store ptr %l.1, ptr %gep.iv.2, align 8, !tbaa !0
34; CHECK-EMPTY:
35; CHECK-NEXT:      Run-time memory checks:
36; CHECK-NEXT:      Grouped accesses:
37; CHECK-EMPTY:
38; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
39; CHECK-NEXT:      SCEV assumptions:
40; CHECK-EMPTY:
41; CHECK-NEXT:      Expressions re-written:
42;
43entry:
44  br label %loop.1
45
46loop.1:
47  %iv = phi i64 [ %iv.next, %loop.1 ], [ 8, %entry ]
48  %arr.addr.0.i = phi ptr [ %incdec.ptr.i, %loop.1 ], [ %arr, %entry ]
49  %incdec.ptr.i = getelementptr inbounds ptr, ptr %arr.addr.0.i, i64 1
50  %0 = load ptr, ptr %arr.addr.0.i, align 8, !tbaa !6
51  %tobool.not.i = icmp eq ptr %0, null
52  %iv.next = add i64 %iv, 8
53  br i1 %tobool.not.i, label %loop.1.exit, label %loop.1
54
55loop.1.exit:
56  %iv.lcssa = phi i64 [ %iv, %loop.1 ]
57  br label %loop.2
58
59loop.2:
60  %iv.1 = phi i64 [ 0, %loop.1.exit ], [ %iv.1.next, %loop.2 ]
61  %iv.2 = phi i64 [ %iv.lcssa, %loop.1.exit ], [ %iv.2.next, %loop.2 ]
62  %gep.iv.1 = getelementptr inbounds ptr, ptr %arr, i64 %iv.1
63  %l.1 = load ptr, ptr %gep.iv.1, align 8, !tbaa !6
64  %l.2 = load i64, ptr %l.1, align 8, !tbaa !13
65  %inc = add i64 %l.2, 1
66  store i64 %inc, ptr %l.1, align 8, !tbaa !13
67  %iv.2.next = add nsw i64 %iv.2, 1
68  %gep.iv.2 = getelementptr inbounds ptr, ptr %arr, i64 %iv.2
69  store ptr %l.1, ptr %gep.iv.2, align 8, !tbaa !6
70  %iv.1.next = add nuw nsw i64 %iv.1, 1
71  %cmp = icmp ult i64 %iv.1.next, 1000
72  br i1 %cmp, label %loop.2, label %exit
73
74exit:
75  ret void
76}
77
78define void @test_indirect_read_loop_also_modifies_pointer_array(ptr noundef %arr) {
79; CHECK-LABEL: 'test_indirect_read_loop_also_modifies_pointer_array'
80; CHECK-NEXT:    loop.1:
81; CHECK-NEXT:      Report: could not determine number of loop iterations
82; CHECK-NEXT:      Dependences:
83; CHECK-NEXT:      Run-time memory checks:
84; CHECK-NEXT:      Grouped accesses:
85; CHECK-EMPTY:
86; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
87; CHECK-NEXT:      SCEV assumptions:
88; CHECK-EMPTY:
89; CHECK-NEXT:      Expressions re-written:
90; CHECK-NEXT:    loop.2:
91; CHECK-NEXT:      Memory dependences are safe with run-time checks
92; CHECK-NEXT:      Dependences:
93; CHECK-NEXT:      Run-time memory checks:
94; CHECK-NEXT:      Check 0:
95; CHECK-NEXT:        Comparing group ([[GRP1:0x[0-9a-f]+]]):
96; CHECK-NEXT:          %gep.iv.2 = getelementptr inbounds i64, ptr %arr, i64 %iv.2
97; CHECK-NEXT:        Against group ([[GRP2:0x[0-9a-f]+]]):
98; CHECK-NEXT:          %gep.iv.1 = getelementptr inbounds ptr, ptr %arr, i64 %iv.1
99; CHECK-NEXT:      Grouped accesses:
100; CHECK-NEXT:        Group [[GRP1]]:
101; CHECK-NEXT:          (Low: {(64 + %arr),+,64}<%loop.1> High: {(8064 + %arr),+,64}<%loop.1>)
102; CHECK-NEXT:            Member: {{\{\{}}(64 + %arr),+,64}<%loop.1>,+,8}<%loop.2>
103; CHECK-NEXT:        Group [[GRP2]]:
104; CHECK-NEXT:          (Low: %arr High: (8000 + %arr))
105; CHECK-NEXT:            Member: {%arr,+,8}<nuw><%loop.2>
106; CHECK-EMPTY:
107; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
108; CHECK-NEXT:      SCEV assumptions:
109; CHECK-EMPTY:
110; CHECK-NEXT:      Expressions re-written:
111;
112entry:
113  br label %loop.1
114
115loop.1:
116  %iv = phi i64 [ %iv.next, %loop.1 ], [ 8, %entry ]
117  %arr.addr.0.i = phi ptr [ %incdec.ptr.i, %loop.1 ], [ %arr, %entry ]
118  %incdec.ptr.i = getelementptr inbounds ptr, ptr %arr.addr.0.i, i64 1
119  %0 = load ptr, ptr %arr.addr.0.i, align 8, !tbaa !6
120  %tobool.not.i = icmp eq ptr %0, null
121  %iv.next = add i64 %iv, 8
122  br i1 %tobool.not.i, label %loop.1.exit, label %loop.1
123
124loop.1.exit:
125  %iv.lcssa = phi i64 [ %iv, %loop.1 ]
126  br label %loop.2
127
128loop.2:
129  %iv.1 = phi i64 [ 0, %loop.1.exit ], [ %iv.1.next, %loop.2 ]
130  %iv.2 = phi i64 [ %iv.lcssa, %loop.1.exit ], [ %iv.2.next, %loop.2 ]
131  %gep.iv.1 = getelementptr inbounds ptr, ptr %arr, i64 %iv.1
132  %l.1 = load ptr, ptr %gep.iv.1, align 8, !tbaa !6
133  %l.2 = load i64, ptr %l.1, align 8, !tbaa !13
134  %inc = add i64 %l.2, 1
135  %iv.2.next = add nsw i64 %iv.2, 1
136  %gep.iv.2 = getelementptr inbounds i64, ptr %arr, i64 %iv.2
137  store i64 %l.2, ptr %gep.iv.2, align 8, !tbaa !6
138  %iv.1.next = add nuw nsw i64 %iv.1, 1
139  %cmp = icmp ult i64 %iv.1.next, 1000
140  br i1 %cmp, label %loop.2, label %exit
141
142exit:
143  ret void
144}
145
146define void @test_indirect_write_loop_also_modifies_pointer_array(ptr noundef %arr) {
147; CHECK-LABEL: 'test_indirect_write_loop_also_modifies_pointer_array'
148; CHECK-NEXT:    loop.1:
149; CHECK-NEXT:      Report: could not determine number of loop iterations
150; CHECK-NEXT:      Dependences:
151; CHECK-NEXT:      Run-time memory checks:
152; CHECK-NEXT:      Grouped accesses:
153; CHECK-EMPTY:
154; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
155; CHECK-NEXT:      SCEV assumptions:
156; CHECK-EMPTY:
157; CHECK-NEXT:      Expressions re-written:
158; CHECK-NEXT:    loop.2:
159; CHECK-NEXT:      Memory dependences are safe with run-time checks
160; CHECK-NEXT:      Dependences:
161; CHECK-NEXT:      Run-time memory checks:
162; CHECK-NEXT:      Check 0:
163; CHECK-NEXT:        Comparing group ([[GRP3:0x[0-9a-f]+]]):
164; CHECK-NEXT:          %gep.iv.2 = getelementptr inbounds ptr, ptr %arr, i64 %iv.2
165; CHECK-NEXT:        Against group ([[GRP4:0x[0-9a-f]+]]):
166; CHECK-NEXT:          %gep.iv.1 = getelementptr inbounds ptr, ptr %arr, i64 %iv.1
167; CHECK-NEXT:      Grouped accesses:
168; CHECK-NEXT:        Group [[GRP3]]:
169; CHECK-NEXT:          (Low: {(64 + %arr),+,64}<%loop.1> High: {(8064 + %arr),+,64}<%loop.1>)
170; CHECK-NEXT:            Member: {{\{\{}}(64 + %arr),+,64}<%loop.1>,+,8}<%loop.2>
171; CHECK-NEXT:        Group [[GRP4]]:
172; CHECK-NEXT:          (Low: %arr High: (8000 + %arr))
173; CHECK-NEXT:            Member: {%arr,+,8}<nuw><%loop.2>
174; CHECK-EMPTY:
175; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
176; CHECK-NEXT:      SCEV assumptions:
177; CHECK-EMPTY:
178; CHECK-NEXT:      Expressions re-written:
179;
180entry:
181  br label %loop.1
182
183loop.1:
184  %iv = phi i64 [ %iv.next, %loop.1 ], [ 8, %entry ]
185  %arr.addr.0.i = phi ptr [ %incdec.ptr.i, %loop.1 ], [ %arr, %entry ]
186  %incdec.ptr.i = getelementptr inbounds ptr, ptr %arr.addr.0.i, i64 1
187  %0 = load ptr, ptr %arr.addr.0.i, align 8, !tbaa !6
188  %tobool.not.i = icmp eq ptr %0, null
189  %iv.next = add i64 %iv, 8
190  br i1 %tobool.not.i, label %loop.1.exit, label %loop.1
191
192loop.1.exit:
193  %iv.lcssa = phi i64 [ %iv, %loop.1 ]
194  br label %loop.2
195
196loop.2:
197  %iv.1 = phi i64 [ 0, %loop.1.exit ], [ %iv.1.next, %loop.2 ]
198  %iv.2 = phi i64 [ %iv.lcssa, %loop.1.exit ], [ %iv.2.next, %loop.2 ]
199  %gep.iv.1 = getelementptr inbounds ptr, ptr %arr, i64 %iv.1
200  %l.1 = load ptr, ptr %gep.iv.1, align 8, !tbaa !6
201  %inc = add i64 %iv.1, 1
202  store i64 %inc, ptr %l.1, align 8, !tbaa !13
203  %iv.2.next = add nsw i64 %iv.2, 1
204  %gep.iv.2 = getelementptr inbounds ptr, ptr %arr, i64 %iv.2
205  store ptr %l.1, ptr %gep.iv.2, align 8, !tbaa !6
206  %iv.1.next = add nuw nsw i64 %iv.1, 1
207  %cmp = icmp ult i64 %iv.1.next, 1000
208  br i1 %cmp, label %loop.2, label %exit
209
210exit:
211  ret void
212}
213
214; FIXME: Not safe with runtime checks due to the indirect pointers are modified
215;        in the loop.
216define void @test_indirect_read_write_loop_does_not_modify_pointer_array(ptr noundef %arr, ptr noundef noalias %arr2) {
217; CHECK-LABEL: 'test_indirect_read_write_loop_does_not_modify_pointer_array'
218; CHECK-NEXT:    loop.1:
219; CHECK-NEXT:      Report: could not determine number of loop iterations
220; CHECK-NEXT:      Dependences:
221; CHECK-NEXT:      Run-time memory checks:
222; CHECK-NEXT:      Grouped accesses:
223; CHECK-EMPTY:
224; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
225; CHECK-NEXT:      SCEV assumptions:
226; CHECK-EMPTY:
227; CHECK-NEXT:      Expressions re-written:
228; CHECK-NEXT:    loop.2:
229; CHECK-NEXT:      Report: unsafe dependent memory operations in loop. Use #pragma clang loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
230; CHECK-NEXT:  Unsafe indirect dependence.
231; CHECK-NEXT:      Dependences:
232; CHECK-NEXT:        IndirectUnsafe:
233; CHECK-NEXT:            %l.2 = load i64, ptr %l.1, align 8, !tbaa !4 ->
234; CHECK-NEXT:            store i64 %inc, ptr %l.1, align 8, !tbaa !4
235; CHECK-EMPTY:
236; CHECK-NEXT:        Unknown:
237; CHECK-NEXT:            %l.3 = load i64, ptr %gep.arr2.iv.1, align 8 ->
238; CHECK-NEXT:            store i64 %inc.2, ptr %gep.arr2.iv.2, align 8, !tbaa !0
239; CHECK-EMPTY:
240; CHECK-NEXT:      Run-time memory checks:
241; CHECK-NEXT:      Grouped accesses:
242; CHECK-EMPTY:
243; CHECK-NEXT:      Non vectorizable stores to invariant address were not found in loop.
244; CHECK-NEXT:      SCEV assumptions:
245; CHECK-EMPTY:
246; CHECK-NEXT:      Expressions re-written:
247;
248entry:
249  br label %loop.1
250
251loop.1:
252  %iv = phi i64 [ %iv.next, %loop.1 ], [ 8, %entry ]
253  %arr.addr.0.i = phi ptr [ %incdec.ptr.i, %loop.1 ], [ %arr, %entry ]
254  %incdec.ptr.i = getelementptr inbounds ptr, ptr %arr.addr.0.i, i64 1
255  %0 = load ptr, ptr %arr.addr.0.i, align 8, !tbaa !6
256  %tobool.not.i = icmp eq ptr %0, null
257  %iv.next = add i64 %iv, 8
258  br i1 %tobool.not.i, label %loop.1.exit, label %loop.1
259
260loop.1.exit:
261  %iv.lcssa = phi i64 [ %iv, %loop.1 ]
262  br label %loop.2
263
264loop.2:
265  %iv.1 = phi i64 [ 0, %loop.1.exit ], [ %iv.1.next, %loop.2 ]
266  %iv.2 = phi i64 [ %iv.lcssa, %loop.1.exit ], [ %iv.2.next, %loop.2 ]
267  %gep.iv.1 = getelementptr inbounds ptr, ptr %arr, i64 %iv.1
268  %l.1 = load ptr, ptr %gep.iv.1, align 8, !tbaa !6
269  %l.2 = load i64, ptr %l.1, align 8, !tbaa !13
270  %inc = add i64 %l.2, 1
271  store i64 %inc, ptr %l.1, align 8, !tbaa !13
272  %iv.2.next = add nsw i64 %iv.2, 1
273  %gep.arr2.iv.1 = getelementptr inbounds i64 , ptr %arr2, i64 %iv.1
274  %gep.arr2.iv.2 = getelementptr inbounds i64 , ptr %arr2, i64 %iv.2
275  %l.3 = load i64, ptr %gep.arr2.iv.1
276  %inc.2 = add i64 %l.3, 5
277  store i64 %inc.2, ptr %gep.arr2.iv.2, align 8, !tbaa !6
278  %iv.1.next = add nuw nsw i64 %iv.1, 1
279  %cmp = icmp ult i64 %iv.1.next, 1000
280  br i1 %cmp, label %loop.2, label %exit
281
282exit:
283  ret void
284}
285
286!6 = !{!7, !7, i64 0}
287!7 = !{!"any pointer", !8, i64 0}
288!8 = !{!"omnipotent char", !9, i64 0}
289!9 = !{!"Simple C/C++ TBAA"}
290!13 = !{!14, !15, i64 0}
291!14 = !{!"", !15, i64 0}
292!15 = !{!"long long", !8, i64 0}
293