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