1; RUN: opt -loop-accesses -analyze < %s | FileCheck %s
2; RUN: opt -passes='require<scalar-evolution>,require<aa>,loop(print-access-info)' -disable-output  < %s 2>&1 | FileCheck %s
3
4target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
5target triple = "aarch64--linux-gnueabi"
6
7; 3 reads and 3 writes should need 12 memchecks
8; CHECK: function 'testf':
9; CHECK: Memory dependences are safe with run-time checks
10
11; Memory dependencies have labels starting from 0, so in
12; order to verify that we have n checks, we look for
13; (n-1): and not n:.
14
15; CHECK: Run-time memory checks:
16; CHECK-NEXT: Check 0:
17; CHECK: Check 11:
18; CHECK-NOT: Check 12:
19
20define void @testf(i16* %a,
21               i16* %b,
22               i16* %c,
23               i16* %d,
24               i16* %e,
25               i16* %f) {
26entry:
27  br label %for.body
28
29for.body:                                         ; preds = %for.body, %entry
30  %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
31
32  %add = add nuw nsw i64 %ind, 1
33
34  %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %ind
35  %loadA = load i16, i16* %arrayidxA, align 2
36
37  %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
38  %loadB = load i16, i16* %arrayidxB, align 2
39
40  %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %ind
41  %loadC = load i16, i16* %arrayidxC, align 2
42
43  %mul = mul i16 %loadB, %loadA
44  %mul1 = mul i16 %mul, %loadC
45
46  %arrayidxD = getelementptr inbounds i16, i16* %d, i64 %ind
47  store i16 %mul1, i16* %arrayidxD, align 2
48
49  %arrayidxE = getelementptr inbounds i16, i16* %e, i64 %ind
50  store i16 %mul, i16* %arrayidxE, align 2
51
52  %arrayidxF = getelementptr inbounds i16, i16* %f, i64 %ind
53  store i16 %mul1, i16* %arrayidxF, align 2
54
55  %exitcond = icmp eq i64 %add, 20
56  br i1 %exitcond, label %for.end, label %for.body
57
58for.end:                                          ; preds = %for.body
59  ret void
60}
61
62; The following (testg and testh) check that we can group
63; memory checks of accesses which differ by a constant value.
64; Both tests are based on the following C code:
65;
66; void testh(short *a, short *b, short *c) {
67;   unsigned long ind = 0;
68;   for (unsigned long ind = 0; ind < 20; ++ind) {
69;     c[2 * ind] = a[ind] * a[ind + 1];
70;     c[2 * ind + 1] = a[ind] * a[ind + 1] * b[ind];
71;   }
72; }
73;
74; It is sufficient to check the intervals
75; [a, a + 21], [b, b + 20] against [c, c + 41].
76
77; 3 reads and 2 writes - two of the reads can be merged,
78; and the writes can be merged as well. This gives us a
79; total of 2 memory checks.
80
81; CHECK: function 'testg':
82
83; CHECK: Run-time memory checks:
84; CHECK-NEXT:   Check 0:
85; CHECK-NEXT:     Comparing group ([[ZERO:.+]]):
86; CHECK-NEXT:       %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
87; CHECK-NEXT:       %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
88; CHECK-NEXT:     Against group ([[ONE:.+]]):
89; CHECK-NEXT:       %arrayidxA1 = getelementptr inbounds i16, i16* %a, i64 %add
90; CHECK-NEXT:       %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %ind
91; CHECK-NEXT:   Check 1:
92; CHECK-NEXT:     Comparing group ({{.*}}[[ZERO]]):
93; CHECK-NEXT:       %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
94; CHECK-NEXT:       %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
95; CHECK-NEXT:     Against group ([[TWO:.+]]):
96; CHECK-NEXT:       %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
97; CHECK-NEXT:   Grouped accesses:
98; CHECK-NEXT:    Group {{.*}}[[ZERO]]:
99; CHECK-NEXT:       (Low: %c High: (80 + %c))
100; CHECK-NEXT:         Member: {(2 + %c)<nsw>,+,4}
101; CHECK-NEXT:         Member: {%c,+,4}
102; CHECK-NEXT:     Group {{.*}}[[ONE]]:
103; CHECK-NEXT:       (Low: %a High: (42 + %a))
104; CHECK-NEXT:         Member: {(2 + %a)<nsw>,+,2}
105; CHECK-NEXT:         Member: {%a,+,2}
106; CHECK-NEXT:     Group {{.*}}[[TWO]]:
107; CHECK-NEXT:       (Low: %b High: (40 + %b))
108; CHECK-NEXT:         Member: {%b,+,2}
109
110define void @testg(i16* %a,
111               i16* %b,
112               i16* %c) {
113entry:
114  br label %for.body
115
116for.body:                                         ; preds = %for.body, %entry
117  %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
118  %store_ind = phi i64 [ 0, %entry ], [ %store_ind_next, %for.body ]
119
120  %add = add nuw nsw i64 %ind, 1
121  %store_ind_inc = add nuw nsw i64 %store_ind, 1
122  %store_ind_next = add nuw nsw i64 %store_ind_inc, 1
123
124  %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %ind
125  %loadA = load i16, i16* %arrayidxA, align 2
126
127  %arrayidxA1 = getelementptr inbounds i16, i16* %a, i64 %add
128  %loadA1 = load i16, i16* %arrayidxA1, align 2
129
130  %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
131  %loadB = load i16, i16* %arrayidxB, align 2
132
133  %mul = mul i16 %loadA, %loadA1
134  %mul1 = mul i16 %mul, %loadB
135
136  %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
137  store i16 %mul1, i16* %arrayidxC, align 2
138
139  %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
140  store i16 %mul, i16* %arrayidxC1, align 2
141
142  %exitcond = icmp eq i64 %add, 20
143  br i1 %exitcond, label %for.end, label %for.body
144
145for.end:                                          ; preds = %for.body
146  ret void
147}
148
149; 3 reads and 2 writes - the writes can be merged into a single
150; group, but the GEPs used for the reads are not marked as inbounds.
151; We can still merge them because we are using a unit stride for
152; accesses, so we cannot overflow the GEPs.
153
154; CHECK: function 'testh':
155; CHECK: Run-time memory checks:
156; CHECK-NEXT:   Check 0:
157; CHECK-NEXT:     Comparing group ([[ZERO:.+]]):
158; CHECK-NEXT:         %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
159; CHECK-NEXT:         %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
160; CHECK-NEXT:     Against group ([[ONE:.+]]):
161; CHECK-NEXT:         %arrayidxA1 = getelementptr i16, i16* %a, i64 %add
162; CHECK-NEXT:         %arrayidxA = getelementptr i16, i16* %a, i64 %ind
163; CHECK-NEXT:   Check 1:
164; CHECK-NEXT:     Comparing group ({{.*}}[[ZERO]]):
165; CHECK-NEXT:         %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
166; CHECK-NEXT:         %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
167; CHECK-NEXT:     Against group ([[TWO:.+]]):
168; CHECK-NEXT:         %arrayidxB = getelementptr i16, i16* %b, i64 %ind
169; CHECK-NEXT:   Grouped accesses:
170; CHECK-NEXT:     Group {{.*}}[[ZERO]]:
171; CHECK-NEXT:       (Low: %c High: (80 + %c))
172; CHECK-NEXT:         Member: {(2 + %c)<nsw>,+,4}
173; CHECK-NEXT:         Member: {%c,+,4}
174; CHECK-NEXT:     Group {{.*}}[[ONE]]:
175; CHECK-NEXT:       (Low: %a High: (42 + %a))
176; CHECK-NEXT:         Member: {(2 + %a),+,2}
177; CHECK-NEXT:         Member: {%a,+,2}
178; CHECK-NEXT:     Group {{.*}}[[TWO]]:
179; CHECK-NEXT:       (Low: %b High: (40 + %b))
180; CHECK-NEXT:         Member: {%b,+,2}
181
182define void @testh(i16* %a,
183               i16* %b,
184               i16* %c) {
185entry:
186  br label %for.body
187
188for.body:                                         ; preds = %for.body, %entry
189  %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
190  %store_ind = phi i64 [ 0, %entry ], [ %store_ind_next, %for.body ]
191
192  %add = add nuw nsw i64 %ind, 1
193  %store_ind_inc = add nuw nsw i64 %store_ind, 1
194  %store_ind_next = add nuw nsw i64 %store_ind_inc, 1
195
196  %arrayidxA = getelementptr i16, i16* %a, i64 %ind
197  %loadA = load i16, i16* %arrayidxA, align 2
198
199  %arrayidxA1 = getelementptr i16, i16* %a, i64 %add
200  %loadA1 = load i16, i16* %arrayidxA1, align 2
201
202  %arrayidxB = getelementptr i16, i16* %b, i64 %ind
203  %loadB = load i16, i16* %arrayidxB, align 2
204
205  %mul = mul i16 %loadA, %loadA1
206  %mul1 = mul i16 %mul, %loadB
207
208  %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
209  store i16 %mul1, i16* %arrayidxC, align 2
210
211  %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
212  store i16 %mul, i16* %arrayidxC1, align 2
213
214  %exitcond = icmp eq i64 %add, 20
215  br i1 %exitcond, label %for.end, label %for.body
216
217for.end:                                          ; preds = %for.body
218  ret void
219}
220
221; Don't merge pointers if we need to perform a check against a pointer
222; to the same underlying object (doing so would emit a check that could be
223; falsely invalidated) For example, in the following loop:
224;
225; for (i = 0; i < 5000; ++i)
226;   a[i + offset] = a[i] + a[i + 10000]
227;
228; we should not merge the intervals associated with the reads (0,5000) and
229; (10000, 15000) into (0, 15000) as this will pottentially fail the check
230; against the interval associated with the write.
231;
232; We cannot have this check unless ShouldRetryWithRuntimeCheck is set,
233; and therefore the grouping algorithm would create a separate group for
234; each pointer.
235
236; CHECK: function 'testi':
237; CHECK: Run-time memory checks:
238; CHECK-NEXT:   Check 0:
239; CHECK-NEXT:     Comparing group ([[ZERO:.+]]):
240; CHECK-NEXT:       %storeidx = getelementptr inbounds i16, i16* %a, i64 %store_ind
241; CHECK-NEXT:     Against group ([[ONE:.+]]):
242; CHECK-NEXT:       %arrayidxA1 = getelementptr i16, i16* %a, i64 %ind
243; CHECK-NEXT:   Check 1:
244; CHECK-NEXT:     Comparing group ({{.*}}[[ZERO]]):
245; CHECK-NEXT:       %storeidx = getelementptr inbounds i16, i16* %a, i64 %store_ind
246; CHECK-NEXT:     Against group ([[TWO:.+]]):
247; CHECK-NEXT:       %arrayidxA2 = getelementptr i16, i16* %a, i64 %ind2
248; CHECK-NEXT:   Grouped accesses:
249; CHECK-NEXT:     Group {{.*}}[[ZERO]]:
250; CHECK-NEXT:       (Low: ((2 * %offset) + %a)<nsw> High: (10000 + (2 * %offset) + %a))
251; CHECK-NEXT:         Member: {((2 * %offset) + %a)<nsw>,+,2}<nsw><%for.body>
252; CHECK-NEXT:     Group {{.*}}[[ONE]]:
253; CHECK-NEXT:       (Low: %a High: (10000 + %a))
254; CHECK-NEXT:         Member: {%a,+,2}<nw><%for.body>
255; CHECK-NEXT:     Group {{.*}}[[TWO]]:
256; CHECK-NEXT:       (Low: (20000 + %a) High: (30000 + %a))
257; CHECK-NEXT:         Member: {(20000 + %a),+,2}<nw><%for.body>
258
259define void @testi(i16* %a,
260                   i64 %offset) {
261entry:
262  br label %for.body
263
264for.body:                                         ; preds = %for.body, %entry
265  %ind = phi i64 [ 0, %entry ], [ %add, %for.body ]
266  %store_ind = phi i64 [ %offset, %entry ], [ %store_ind_inc, %for.body ]
267
268  %add = add nuw nsw i64 %ind, 1
269  %store_ind_inc = add nuw nsw i64 %store_ind, 1
270
271  %arrayidxA1 = getelementptr i16, i16* %a, i64 %ind
272  %ind2 = add nuw nsw i64 %ind, 10000
273  %arrayidxA2 = getelementptr i16, i16* %a, i64 %ind2
274
275  %loadA1 = load i16, i16* %arrayidxA1, align 2
276  %loadA2 = load i16, i16* %arrayidxA2, align 2
277
278  %addres = add i16 %loadA1, %loadA2
279
280  %storeidx = getelementptr inbounds i16, i16* %a, i64 %store_ind
281  store i16 %addres, i16* %storeidx, align 2
282
283  %exitcond = icmp eq i64 %add, 5000
284  br i1 %exitcond, label %for.end, label %for.body
285
286for.end:                                          ; preds = %for.body
287  ret void
288}
289