Debian Codegraph @

llvm/test/Transforms/LoopInterchange/legality-for-scalar-deps.ll

raw
1 ; RUN: opt < %s -passes=loop-interchange -pass-remarks-output=%t -disable-output
2 ; RUN: FileCheck -input-file %t %s
3
4 ; This is a collection of cases where the loops were incorrectly interchanged
5 ; due to mishandling of scalar dependencies.
6
7 ;; The original code is as follows, with some simplifications from the one in
8 ;; the issue #46867. The interchange is illegal due to the dependency of `s`.
9 ;;
10 ;; void issue46867(int *s, int c, int ff[4][9]) {
11 ;; for (int d = 0; d <= 2; d++) {
12 ;; for (int e = 0; e <= 2; e++) {
13 ;; if ((long)(ff[e][d] && (*s = 3), c) % 4073709551606)
14 ;; ++*s;
15 ;; }
16 ;; }
17 ;; }
18
19 ; CHECK: --- !Missed
20 ; CHECK-NEXT: Pass: loop-interchange
21 ; CHECK-NEXT: Name: Dependence
22 ; CHECK-NEXT: Function: issue46867
23 ; CHECK-NEXT: Args:
24 ; CHECK-NEXT: - String: All loops have dependencies in all directions.
25 ; CHECK: --- !Missed
26 ; CHECK-NEXT: Pass: loop-interchange
27 ; CHECK-NEXT: Name: Dependence
28 ; CHECK-NEXT: Function: issue46867
29 ; CHECK-NEXT: Args:
30 ; CHECK-NEXT: - String: All loops have dependencies in all directions.
31 define void @issue46867(ptr noundef captures(none) %s, i32 noundef %c, ptr noundef readonly captures(none) %ff) {
32 entry:
33 %tobool7.not = icmp eq i32 %c, 0
34 br i1 %tobool7.not, label %for.cond1.preheader.us.preheader, label %entry.split
35
36 for.cond1.preheader.us.preheader:
37 br label %for.cond1.preheader.us
38
39 for.cond1.preheader.us:
40 %indvars.iv31 = phi i64 [ 0, %for.cond1.preheader.us.preheader ], [ %indvars.iv.next32, %for.cond.cleanup3.split.us.us ]
41 br label %for.body4.us.us
42
43 for.body4.us.us:
44 %indvars.iv27 = phi i64 [ %indvars.iv.next28, %land.end.us.us ], [ 0, %for.cond1.preheader.us ]
45 %arrayidx6.us.us = getelementptr inbounds nuw [9 x i32], ptr %ff, i64 %indvars.iv27, i64 %indvars.iv31
46 %0 = load i32, ptr %arrayidx6.us.us, align 4
47 %tobool.not.us.us = icmp eq i32 %0, 0
48 br i1 %tobool.not.us.us, label %land.end.us.us, label %land.rhs.us.us
49
50 land.rhs.us.us:
51 store i32 3, ptr %s, align 4
52 br label %land.end.us.us
53
54 land.end.us.us:
55 %indvars.iv.next28 = add nuw nsw i64 %indvars.iv27, 1
56 %exitcond30 = icmp ne i64 %indvars.iv.next28, 3
57 br i1 %exitcond30, label %for.body4.us.us, label %for.cond.cleanup3.split.us.us
58
59 for.cond.cleanup3.split.us.us:
60 %indvars.iv.next32 = add nuw nsw i64 %indvars.iv31, 1
61 %exitcond34 = icmp ne i64 %indvars.iv.next32, 3
62 br i1 %exitcond34, label %for.cond1.preheader.us, label %for.cond.cleanup.loopexit
63
64 entry.split:
65 %s.promoted19 = load i32, ptr %s, align 4
66 br label %for.cond1.preheader
67
68 for.cond1.preheader:
69 %indvars.iv23 = phi i64 [ 0, %entry.split ], [ %indvars.iv.next24, %for.cond.cleanup3.split ]
70 %s.promoted20 = phi i32 [ %s.promoted19, %entry.split ], [ %inc.lcssa, %for.cond.cleanup3.split ]
71 br label %for.body4
72
73 for.cond.cleanup.loopexit:
74 br label %for.cond.cleanup
75
76 for.cond.cleanup.loopexit21:
77 br label %for.cond.cleanup
78
79 for.cond.cleanup:
80 ret void
81
82 for.cond.cleanup3.split:
83 %inc.lcssa = phi i32 [ %inc, %land.end ]
84 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
85 %exitcond26 = icmp ne i64 %indvars.iv.next24, 3
86 br i1 %exitcond26, label %for.cond1.preheader, label %for.cond.cleanup.loopexit21
87
88 for.body4:
89 %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %land.end ]
90 %1 = phi i32 [ %s.promoted20, %for.cond1.preheader ], [ %inc, %land.end ]
91 %arrayidx6 = getelementptr inbounds nuw [9 x i32], ptr %ff, i64 %indvars.iv, i64 %indvars.iv23
92 %2 = load i32, ptr %arrayidx6, align 4
93 %tobool.not = icmp eq i32 %2, 0
94 br i1 %tobool.not, label %land.end, label %land.rhs
95
96 land.rhs:
97 store i32 3, ptr %s, align 4
98 br label %land.end
99
100 land.end:
101 %3 = phi i32 [ 3, %land.rhs ], [ %1, %for.body4 ]
102 %inc = add nsw i32 %3, 1
103 store i32 %inc, ptr %s, align 4
104 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
105 %exitcond = icmp ne i64 %indvars.iv.next, 3
106 br i1 %exitcond, label %for.body4, label %for.cond.cleanup3.split
107 }
108
109
110 ;; The original code is as follows, with some simplifications from the one in
111 ;; the issue #47401. The interchange is illegal due to the dependency of `e`.
112 ;;
113 ;; void issue47401(int *e, int bb[][8]) {
114 ;; for (int c = 0; c <= 7; c++)
115 ;; for (int d = 4; d; d--)
116 ;; bb[d + 2][c] && (*e = bb[d][0]);
117 ;; }
118
119 ; CHECK: --- !Missed
120 ; CHECK-NEXT: Pass: loop-interchange
121 ; CHECK-NEXT: Name: Dependence
122 ; CHECK-NEXT: Function: issue47401
123 ; CHECK-NEXT: Args:
124 ; CHECK-NEXT: - String: All loops have dependencies in all directions.
125 define void @issue47401(ptr noundef writeonly captures(none) %e, ptr noundef readonly captures(none) %bb) {
126 entry:
127 br label %for.cond1.preheader
128
129 for.cond1.preheader:
130 %indvars.iv22 = phi i64 [ 0, %entry ], [ %indvars.iv.next23, %for.cond.cleanup2 ]
131 br label %for.body3
132
133 for.cond.cleanup:
134 ret void
135
136 for.cond.cleanup2:
137 %indvars.iv.next23 = add nuw nsw i64 %indvars.iv22, 1
138 %exitcond = icmp ne i64 %indvars.iv.next23, 8
139 br i1 %exitcond, label %for.cond1.preheader, label %for.cond.cleanup
140
141 for.body3:
142 %indvars.iv = phi i64 [ 4, %for.cond1.preheader ], [ %indvars.iv.next, %land.end ]
143 %0 = getelementptr [8 x i32], ptr %bb, i64 %indvars.iv
144 %arrayidx = getelementptr i8, ptr %0, i64 64
145 %arrayidx5 = getelementptr inbounds nuw [8 x i32], ptr %arrayidx, i64 0, i64 %indvars.iv22
146 %1 = load i32, ptr %arrayidx5, align 4
147 %tobool6.not = icmp eq i32 %1, 0
148 br i1 %tobool6.not, label %land.end, label %land.rhs
149
150 land.rhs:
151 %2 = load i32, ptr %0, align 4
152 store i32 %2, ptr %e, align 4
153 br label %land.end
154
155 land.end:
156 %indvars.iv.next = add nsw i64 %indvars.iv, -1
157 %tobool.not = icmp eq i64 %indvars.iv.next, 0
158 br i1 %tobool.not, label %for.cond.cleanup2, label %for.body3
159 }
160
161 ;; The original code is as follows, with some simplifications from the one in
162 ;; the issue #47295. The interchange is illegal due to the dependency of `f`.
163 ;;
164 ;; void issue47295(int *f, int cc[4][4]) {
165 ;; for (int i = 0; i <= 3; i++) {
166 ;; for (int j = 0; j <= 3; j++) {
167 ;; *f ^= 0x1000;
168 ;; cc[j][i] = *f;
169 ;; }
170 ;; }
171 ;; }
172
173 ; CHECK: --- !Missed
174 ; CHECK-NEXT: Pass: loop-interchange
175 ; CHECK-NEXT: Name: Dependence
176 ; CHECK-NEXT: Function: issue47295
177 ; CHECK-NEXT: Args:
178 ; CHECK-NEXT: - String: All loops have dependencies in all directions.
179 define void @issue47295(ptr noundef captures(none) %f, ptr noundef writeonly captures(none) %cc) {
180 entry:
181 br label %for.cond1.preheader
182
183 for.cond1.preheader:
184 %indvars.iv18 = phi i64 [ 0, %entry ], [ %indvars.iv.next19, %for.cond.cleanup3 ]
185 br label %for.body4
186
187 for.cond.cleanup:
188 ret void
189
190 for.cond.cleanup3:
191 %indvars.iv.next19 = add nuw nsw i64 %indvars.iv18, 1
192 %exitcond21 = icmp ne i64 %indvars.iv.next19, 4
193 br i1 %exitcond21, label %for.cond1.preheader, label %for.cond.cleanup
194
195 for.body4:
196 %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
197 %0 = load i32, ptr %f, align 4
198 %xor = xor i32 %0, 4096
199 store i32 %xor, ptr %f, align 4
200 %arrayidx6 = getelementptr inbounds nuw [4 x i32], ptr %cc, i64 %indvars.iv, i64 %indvars.iv18
201 store i32 %xor, ptr %arrayidx6, align 4
202 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
203 %exitcond = icmp ne i64 %indvars.iv.next, 4
204 br i1 %exitcond, label %for.body4, label %for.cond.cleanup3
205 }
206
207 ;; The original code is as follows, with some simplifications from the one in
208 ;; the issue #54176. The interchange is illegal due to the dependency of `aa`.
209 ;;
210 ;; void issue54176(int n, int m, float aa[1024][128], float bb[1024][128], float cc[1024][128]) {
211 ;; for (int j = 1; j < 128; j++) {
212 ;; for (int i = 1; i < 1024; i++) {
213 ;; cc[i][j] = aa[1][j];
214 ;; aa[1][j-1] += bb[i][j];
215 ;; }
216 ;; }
217 ;; }
218
219 ; CHECK: --- !Missed
220 ; CHECK-NEXT: Pass: loop-interchange
221 ; CHECK-NEXT: Name: Dependence
222 ; CHECK-NEXT: Function: issue54176
223 ; CHECK-NEXT: Args:
224 ; CHECK-NEXT: - String: All loops have dependencies in all directions.
225 define void @issue54176(i32 noundef %n, i32 noundef %m, ptr noundef captures(none) %aa, ptr noundef readonly captures(none) %bb, ptr noundef writeonly captures(none) %cc) {
226
227 entry:
228 %arrayidx = getelementptr inbounds nuw i8, ptr %aa, i64 512
229 br label %for.cond1.preheader
230
231 for.cond1.preheader:
232 %indvars.iv32 = phi i64 [ 1, %entry ], [ %indvars.iv.next33, %for.cond.cleanup3 ]
233 %arrayidx5 = getelementptr inbounds nuw [128 x float], ptr %arrayidx, i64 0, i64 %indvars.iv32
234 %0 = add nsw i64 %indvars.iv32, -1
235 %arrayidx16 = getelementptr inbounds [128 x float], ptr %arrayidx, i64 0, i64 %0
236 br label %for.body4
237
238 for.cond.cleanup3:
239 %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1
240 %exitcond36 = icmp ne i64 %indvars.iv.next33, 128
241 br i1 %exitcond36, label %for.cond1.preheader, label %for.cond.cleanup
242
243 for.body4:
244 %indvars.iv = phi i64 [ 1, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
245 %1 = load float, ptr %arrayidx5, align 4
246 %arrayidx9 = getelementptr inbounds nuw [128 x float], ptr %cc, i64 %indvars.iv, i64 %indvars.iv32
247 store float %1, ptr %arrayidx9, align 4
248 %arrayidx13 = getelementptr inbounds nuw [128 x float], ptr %bb, i64 %indvars.iv, i64 %indvars.iv32
249 %2 = load float, ptr %arrayidx13, align 4
250 %3 = load float, ptr %arrayidx16, align 4
251 %add = fadd float %2, %3
252 store float %add, ptr %arrayidx16, align 4
253 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
254 %exitcond = icmp ne i64 %indvars.iv.next, 1024
255 br i1 %exitcond, label %for.body4, label %for.cond.cleanup3
256
257 for.cond.cleanup:
258 ret void
259 }
260
261 ;; The original code is as follows, with some simplifications from the one in
262 ;; the issue #116114. The interchange is illegal due to the dependency of `A`.
263 ;;
264 ;; void issue116114(int *A, int x, unsigned N, unsigned M) {
265 ;; for (unsigned m = 0; m < M; ++m)
266 ;; for (unsigned i = 0U; i < N - 1; ++i) {
267 ;; A[i] = A[i + 1] + x;
268 ;; }
269 ;; }
270
271 ; CHECK: --- !Missed
272 ; CHECK-NEXT: Pass: loop-interchange
273 ; CHECK-NEXT: Name: Dependence
274 ; CHECK-NEXT: Function: issue116114
275 ; CHECK-NEXT: Args:
276 ; CHECK-NEXT: - String: Cannot interchange loops due to dependences.
277 define void @issue116114(ptr noundef captures(none) %A, i32 noundef %x, i32 noundef %N, i32 noundef %M) {
278 entry:
279 %cmp18.not = icmp eq i32 %M, 0
280 br i1 %cmp18.not, label %for.cond.cleanup, label %for.cond1.preheader.lr.ph
281
282 for.cond1.preheader.lr.ph:
283 %sub = add i32 %N, -1
284 %cmp216.not = icmp eq i32 %sub, 0
285 br i1 %cmp216.not, label %for.cond1.preheader.preheader, label %for.cond1.preheader.us.preheader
286
287 for.cond1.preheader.us.preheader:
288 br label %for.cond1.preheader.us
289
290 for.cond1.preheader.preheader:
291 br label %for.cond.cleanup.loopexit
292
293 for.cond1.preheader.us:
294 %m.019.us = phi i32 [ %inc9.us, %for.cond1.for.cond.cleanup3_crit_edge.us ], [ 0, %for.cond1.preheader.us.preheader ]
295 %wide.trip.count = zext i32 %sub to i64
296 br label %for.body4.us
297
298 for.body4.us:
299 %indvars.iv = phi i64 [ 0, %for.cond1.preheader.us ], [ %indvars.iv.next, %for.body4.us ]
300 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
301 %arrayidx.us = getelementptr inbounds nuw i32, ptr %A, i64 %indvars.iv.next
302 %0 = load i32, ptr %arrayidx.us, align 4
303 %add5.us = add nsw i32 %0, %x
304 %arrayidx7.us = getelementptr inbounds nuw i32, ptr %A, i64 %indvars.iv
305 store i32 %add5.us, ptr %arrayidx7.us, align 4
306 %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count
307 br i1 %exitcond, label %for.body4.us, label %for.cond1.for.cond.cleanup3_crit_edge.us
308
309 for.cond1.for.cond.cleanup3_crit_edge.us:
310 %inc9.us = add nuw i32 %m.019.us, 1
311 %exitcond22 = icmp ne i32 %inc9.us, %M
312 br i1 %exitcond22, label %for.cond1.preheader.us, label %for.cond.cleanup.loopexit20
313
314 for.cond.cleanup.loopexit:
315 br label %for.cond.cleanup
316
317 for.cond.cleanup.loopexit20:
318 br label %for.cond.cleanup
319
320 for.cond.cleanup:
321 ret void
322 }