• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1; RUN: opt < %s -passes='print<loopnest>' -disable-output 2>&1 | FileCheck %s
2
3; Test an imperfect 2-dim loop nest of the form:
4;   for (int i = 0; i < nx; ++i) {
5;     x[i] = i;
6;     for (int j = 0; j < ny; ++j)
7;       y[j][i] = x[i] + j;
8;   }
9
10define void @imperf_nest_1(i32 signext %nx, i32 signext %ny) {
11; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_1_loop_i, Loops: ( imperf_nest_1_loop_i imperf_nest_1_loop_j )
12entry:
13  %0 = zext i32 %ny to i64
14  %1 = zext i32 %nx to i64
15  %2 = mul nuw i64 %0, %1
16  %vla = alloca double, i64 %2, align 8
17  %3 = zext i32 %ny to i64
18  %vla1 = alloca double, i64 %3, align 8
19  br label %imperf_nest_1_loop_i
20
21imperf_nest_1_loop_i:
22  %i2.0 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ]
23  %cmp = icmp slt i32 %i2.0, %nx
24  br i1 %cmp, label %for.body, label %for.end17
25
26for.body:
27  %conv = sitofp i32 %i2.0 to double
28  %idxprom = sext i32 %i2.0 to i64
29  %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
30  store double %conv, double* %arrayidx, align 8
31  br label %imperf_nest_1_loop_j
32
33imperf_nest_1_loop_j:
34  %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
35  %cmp5 = icmp slt i32 %j3.0, %ny
36  br i1 %cmp5, label %for.body7, label %for.end
37
38for.body7:
39  %idxprom8 = sext i32 %i2.0 to i64
40  %arrayidx9 = getelementptr inbounds double, double* %vla1, i64 %idxprom8
41  %4 = load double, double* %arrayidx9, align 8
42  %conv10 = sitofp i32 %j3.0 to double
43  %add = fadd double %4, %conv10
44  %idxprom11 = sext i32 %j3.0 to i64
45  %5 = mul nsw i64 %idxprom11, %1
46  %arrayidx12 = getelementptr inbounds double, double* %vla, i64 %5
47  %idxprom13 = sext i32 %i2.0 to i64
48  %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13
49  store double %add, double* %arrayidx14, align 8
50  br label %for.inc
51
52for.inc:
53  %inc = add nsw i32 %j3.0, 1
54  br label %imperf_nest_1_loop_j
55
56for.end:
57  br label %for.inc15
58
59for.inc15:
60  %inc16 = add nsw i32 %i2.0, 1
61  br label %imperf_nest_1_loop_i
62
63for.end17:
64  ret void
65}
66
67; Test an imperfect 2-dim loop nest of the form:
68;   for (int i = 0; i < nx; ++i) {
69;     for (int j = 0; j < ny; ++j)
70;       y[j][i] = x[i] + j;
71;     y[0][i] += i;
72;   }
73
74define void @imperf_nest_2(i32 signext %nx, i32 signext %ny) {
75; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_2_loop_i, Loops: ( imperf_nest_2_loop_i imperf_nest_2_loop_j )
76entry:
77  %0 = zext i32 %ny to i64
78  %1 = zext i32 %nx to i64
79  %2 = mul nuw i64 %0, %1
80  %vla = alloca double, i64 %2, align 8
81  %3 = zext i32 %ny to i64
82  %vla1 = alloca double, i64 %3, align 8
83  br label %imperf_nest_2_loop_i
84
85imperf_nest_2_loop_i:
86  %i2.0 = phi i32 [ 0, %entry ], [ %inc17, %for.inc16 ]
87  %cmp = icmp slt i32 %i2.0, %nx
88  br i1 %cmp, label %for.body, label %for.end18
89
90for.body:
91  br label %imperf_nest_2_loop_j
92
93imperf_nest_2_loop_j:
94  %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
95  %cmp5 = icmp slt i32 %j3.0, %ny
96  br i1 %cmp5, label %for.body6, label %for.end
97
98for.body6:
99  %idxprom = sext i32 %i2.0 to i64
100  %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
101  %4 = load double, double* %arrayidx, align 8
102  %conv = sitofp i32 %j3.0 to double
103  %add = fadd double %4, %conv
104  %idxprom7 = sext i32 %j3.0 to i64
105  %5 = mul nsw i64 %idxprom7, %1
106  %arrayidx8 = getelementptr inbounds double, double* %vla, i64 %5
107  %idxprom9 = sext i32 %i2.0 to i64
108  %arrayidx10 = getelementptr inbounds double, double* %arrayidx8, i64 %idxprom9
109  store double %add, double* %arrayidx10, align 8
110  br label %for.inc
111
112for.inc:
113  %inc = add nsw i32 %j3.0, 1
114  br label %imperf_nest_2_loop_j
115
116for.end:
117  %conv11 = sitofp i32 %i2.0 to double
118  %6 = mul nsw i64 0, %1
119  %arrayidx12 = getelementptr inbounds double, double* %vla, i64 %6
120  %idxprom13 = sext i32 %i2.0 to i64
121  %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13
122  %7 = load double, double* %arrayidx14, align 8
123  %add15 = fadd double %7, %conv11
124  store double %add15, double* %arrayidx14, align 8
125  br label %for.inc16
126
127for.inc16:
128  %inc17 = add nsw i32 %i2.0, 1
129  br label %imperf_nest_2_loop_i
130
131for.end18:
132  ret void
133}
134
135; Test an imperfect 2-dim loop nest of the form:
136;   for (i = 0; i < nx; ++i) {
137;     for (j = 0; j < ny-nk; ++j)
138;       y[i][j] = x[i] + j;
139;     for (j = ny-nk; j < ny; ++j)
140;       y[i][j] = x[i] - j;
141;   }
142
143define void @imperf_nest_3(i32 signext %nx, i32 signext %ny, i32 signext %nk) {
144; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_3_loop_i, Loops: ( imperf_nest_3_loop_i imperf_nest_3_loop_j imperf_nest_3_loop_k )
145entry:
146  %0 = zext i32 %nx to i64
147  %1 = zext i32 %ny to i64
148  %2 = mul nuw i64 %0, %1
149  %vla = alloca double, i64 %2, align 8
150  %3 = zext i32 %ny to i64
151  %vla1 = alloca double, i64 %3, align 8
152  br label %imperf_nest_3_loop_i
153
154imperf_nest_3_loop_i:                                         ; preds = %for.inc25, %entry
155  %i.0 = phi i32 [ 0, %entry ], [ %inc26, %for.inc25 ]
156  %cmp = icmp slt i32 %i.0, %nx
157  br i1 %cmp, label %for.body, label %for.end27
158
159for.body:                                         ; preds = %for.cond
160  br label %imperf_nest_3_loop_j
161
162imperf_nest_3_loop_j:                                        ; preds = %for.inc, %for.body
163  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
164  %sub = sub nsw i32 %ny, %nk
165  %cmp3 = icmp slt i32 %j.0, %sub
166  br i1 %cmp3, label %for.body4, label %for.end
167
168for.body4:                                        ; preds = %imperf_nest_3_loop_j
169  %idxprom = sext i32 %i.0 to i64
170  %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
171  %4 = load double, double* %arrayidx, align 8
172  %conv = sitofp i32 %j.0 to double
173  %add = fadd double %4, %conv
174  %idxprom5 = sext i32 %i.0 to i64
175  %5 = mul nsw i64 %idxprom5, %1
176  %arrayidx6 = getelementptr inbounds double, double* %vla, i64 %5
177  %idxprom7 = sext i32 %j.0 to i64
178  %arrayidx8 = getelementptr inbounds double, double* %arrayidx6, i64 %idxprom7
179  store double %add, double* %arrayidx8, align 8
180  br label %for.inc
181
182for.inc:                                          ; preds = %for.body4
183  %inc = add nsw i32 %j.0, 1
184  br label %imperf_nest_3_loop_j
185
186for.end:                                          ; preds = %imperf_nest_3_loop_j
187  %sub9 = sub nsw i32 %ny, %nk
188  br label %imperf_nest_3_loop_k
189
190imperf_nest_3_loop_k:                                       ; preds = %for.inc22, %for.end
191  %j.1 = phi i32 [ %sub9, %for.end ], [ %inc23, %for.inc22 ]
192  %cmp11 = icmp slt i32 %j.1, %ny
193  br i1 %cmp11, label %for.body13, label %for.end24
194
195for.body13:                                       ; preds = %imperf_nest_3_loop_k
196  %idxprom14 = sext i32 %i.0 to i64
197  %arrayidx15 = getelementptr inbounds double, double* %vla1, i64 %idxprom14
198  %6 = load double, double* %arrayidx15, align 8
199  %conv16 = sitofp i32 %j.1 to double
200  %sub17 = fsub double %6, %conv16
201  %idxprom18 = sext i32 %i.0 to i64
202  %7 = mul nsw i64 %idxprom18, %1
203  %arrayidx19 = getelementptr inbounds double, double* %vla, i64 %7
204  %idxprom20 = sext i32 %j.1 to i64
205  %arrayidx21 = getelementptr inbounds double, double* %arrayidx19, i64 %idxprom20
206  store double %sub17, double* %arrayidx21, align 8
207  br label %for.inc22
208
209for.inc22:                                        ; preds = %for.body13
210  %inc23 = add nsw i32 %j.1, 1
211  br label %imperf_nest_3_loop_k
212
213for.end24:                                        ; preds = %imperf_nest_3_loop_k
214  br label %for.inc25
215
216for.inc25:                                        ; preds = %for.end24
217  %inc26 = add nsw i32 %i.0, 1
218  br label %imperf_nest_3_loop_i
219
220for.end27:                                        ; preds = %for.cond
221  ret void
222}
223
224; Test an imperfect loop nest of the form:
225;   for (i = 0; i < nx; ++i) {
226;     for (j = 0; j < ny-nk; ++j)
227;       for (k = 0; k < nk; ++k)
228;         y[i][j][k] = x[i+j] + k;
229;     for (j = ny-nk; j < ny; ++j)
230;       y[i][j][0] = x[i] - j;
231;   }
232
233define void @imperf_nest_4(i32 signext %nx, i32 signext %ny, i32 signext %nk) {
234; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_4_loop_j, Loops: ( imperf_nest_4_loop_j imperf_nest_4_loop_k )
235; CHECK-LABEL: IsPerfect=false, Depth=3, OutermostLoop: imperf_nest_4_loop_i, Loops: ( imperf_nest_4_loop_i imperf_nest_4_loop_j imperf_nest_4_loop_j2 imperf_nest_4_loop_k )
236entry:
237  %0 = zext i32 %nx to i64
238  %1 = zext i32 %ny to i64
239  %2 = zext i32 %nk to i64
240  %3 = mul nuw i64 %0, %1
241  %4 = mul nuw i64 %3, %2
242  %vla = alloca double, i64 %4, align 8
243  %5 = zext i32 %ny to i64
244  %vla1 = alloca double, i64 %5, align 8
245  %cmp5 = icmp slt i32 0, %nx
246  br i1 %cmp5, label %imperf_nest_4_loop_i.lr.ph, label %for.end37
247
248imperf_nest_4_loop_i.lr.ph:
249  br label %imperf_nest_4_loop_i
250
251imperf_nest_4_loop_i:
252  %i.0 = phi i32 [ 0, %imperf_nest_4_loop_i.lr.ph ], [ %inc36, %for.inc35 ]
253  %sub2 = sub nsw i32 %ny, %nk
254  %cmp33 = icmp slt i32 0, %sub2
255  br i1 %cmp33, label %imperf_nest_4_loop_j.lr.ph, label %for.end17
256
257imperf_nest_4_loop_j.lr.ph:
258  br label %imperf_nest_4_loop_j
259
260imperf_nest_4_loop_j:
261  %j.0 = phi i32 [ 0, %imperf_nest_4_loop_j.lr.ph ], [ %inc16, %for.inc15 ]
262  %cmp61 = icmp slt i32 0, %nk
263  br i1 %cmp61, label %imperf_nest_4_loop_k.lr.ph, label %for.end
264
265imperf_nest_4_loop_k.lr.ph:
266  br label %imperf_nest_4_loop_k
267
268imperf_nest_4_loop_k:
269  %k.0 = phi i32 [ 0, %imperf_nest_4_loop_k.lr.ph ], [ %inc, %for.inc ]
270  %add = add nsw i32 %i.0, %j.0
271  %idxprom = sext i32 %add to i64
272  %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom
273  %6 = load double, double* %arrayidx, align 8
274  %conv = sitofp i32 %k.0 to double
275  %add8 = fadd double %6, %conv
276  %idxprom9 = sext i32 %i.0 to i64
277  %7 = mul nuw i64 %1, %2
278  %8 = mul nsw i64 %idxprom9, %7
279  %arrayidx10 = getelementptr inbounds double, double* %vla, i64 %8
280  %idxprom11 = sext i32 %j.0 to i64
281  %9 = mul nsw i64 %idxprom11, %2
282  %arrayidx12 = getelementptr inbounds double, double* %arrayidx10, i64 %9
283  %idxprom13 = sext i32 %k.0 to i64
284  %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13
285  store double %add8, double* %arrayidx14, align 8
286  br label %for.inc
287
288for.inc:
289  %inc = add nsw i32 %k.0, 1
290  %cmp6 = icmp slt i32 %inc, %nk
291  br i1 %cmp6, label %imperf_nest_4_loop_k, label %for.cond5.for.end_crit_edge
292
293for.cond5.for.end_crit_edge:
294  br label %for.end
295
296for.end:
297  br label %for.inc15
298
299for.inc15:
300  %inc16 = add nsw i32 %j.0, 1
301  %sub = sub nsw i32 %ny, %nk
302  %cmp3 = icmp slt i32 %inc16, %sub
303  br i1 %cmp3, label %imperf_nest_4_loop_j, label %for.cond2.for.end17_crit_edge
304
305for.cond2.for.end17_crit_edge:
306  br label %for.end17
307
308for.end17:
309  %sub18 = sub nsw i32 %ny, %nk
310  %cmp204 = icmp slt i32 %sub18, %ny
311  br i1 %cmp204, label %imperf_nest_4_loop_j2.lr.ph, label %for.end34
312
313imperf_nest_4_loop_j2.lr.ph:
314  br label %imperf_nest_4_loop_j2
315
316imperf_nest_4_loop_j2:
317  %j.1 = phi i32 [ %sub18, %imperf_nest_4_loop_j2.lr.ph ], [ %inc33, %for.inc32 ]
318  %idxprom23 = sext i32 %i.0 to i64
319  %arrayidx24 = getelementptr inbounds double, double* %vla1, i64 %idxprom23
320  %10 = load double, double* %arrayidx24, align 8
321  %conv25 = sitofp i32 %j.1 to double
322  %sub26 = fsub double %10, %conv25
323  %idxprom27 = sext i32 %i.0 to i64
324  %idxprom29 = sext i32 %j.1 to i64
325  %11 = mul nsw i64 %idxprom29, %2
326  %12 = mul nuw i64 %1, %2
327  %13 = mul nsw i64 %idxprom27, %12
328  %arrayidx28 = getelementptr inbounds double, double* %vla, i64 %13
329  %arrayidx30 = getelementptr inbounds double, double* %arrayidx28, i64 %11
330  %arrayidx31 = getelementptr inbounds double, double* %arrayidx30, i64 0
331  store double %sub26, double* %arrayidx31, align 8
332  br label %for.inc32
333
334for.inc32:
335  %inc33 = add nsw i32 %j.1, 1
336  %cmp20 = icmp slt i32 %inc33, %ny
337  br i1 %cmp20, label %imperf_nest_4_loop_j2, label %for.cond19.for.end34_crit_edge
338
339for.cond19.for.end34_crit_edge:
340  br label %for.end34
341
342for.end34:
343  br label %for.inc35
344
345for.inc35:
346  %inc36 = add nsw i32 %i.0, 1
347  %cmp = icmp slt i32 %inc36, %nx
348  br i1 %cmp, label %imperf_nest_4_loop_i, label %for.cond.for.end37_crit_edge
349
350for.cond.for.end37_crit_edge:
351  br label %for.end37
352
353for.end37:
354  ret void
355}
356
357; Test an imperfect loop nest of the form:
358;   for (int i = 0; i < nx; ++i)
359;     if (i > 5) {
360;       for (int j = 0; j < ny; ++j)
361;         y[j][i] = x[i][j] + j;
362;     }
363
364define void @imperf_nest_5(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
365; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_5_loop_i, Loops: ( imperf_nest_5_loop_i imperf_nest_5_loop_j )
366entry:
367  %cmp2 = icmp slt i32 0, %nx
368  br i1 %cmp2, label %imperf_nest_5_loop_i.lr.ph, label %for.end13
369
370imperf_nest_5_loop_i.lr.ph:
371  br label %imperf_nest_5_loop_i
372
373imperf_nest_5_loop_i:
374  %i.0 = phi i32 [ 0, %imperf_nest_5_loop_i.lr.ph ], [ %inc12, %for.inc11 ]
375  %cmp1 = icmp sgt i32 %i.0, 5
376  br i1 %cmp1, label %if.then, label %if.end
377
378if.then:
379  %cmp31 = icmp slt i32 0, %ny
380  br i1 %cmp31, label %imperf_nest_5_loop_j.lr.ph, label %for.end
381
382imperf_nest_5_loop_j.lr.ph:
383  br label %imperf_nest_5_loop_j
384
385imperf_nest_5_loop_j:
386  %j.0 = phi i32 [ 0, %imperf_nest_5_loop_j.lr.ph ], [ %inc, %for.inc ]
387  %idxprom = sext i32 %i.0 to i64
388  %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
389  %0 = load i32*, i32** %arrayidx, align 8
390  %idxprom5 = sext i32 %j.0 to i64
391  %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
392  %1 = load i32, i32* %arrayidx6, align 4
393  %add = add nsw i32 %1, %j.0
394  %idxprom7 = sext i32 %j.0 to i64
395  %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
396  %2 = load i32*, i32** %arrayidx8, align 8
397  %idxprom9 = sext i32 %i.0 to i64
398  %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
399  store i32 %add, i32* %arrayidx10, align 4
400  br label %for.inc
401
402for.inc:
403  %inc = add nsw i32 %j.0, 1
404  %cmp3 = icmp slt i32 %inc, %ny
405  br i1 %cmp3, label %imperf_nest_5_loop_j, label %for.cond2.for.end_crit_edge
406
407for.cond2.for.end_crit_edge:
408  br label %for.end
409
410for.end:
411  br label %if.end
412
413if.end:
414  br label %for.inc11
415
416for.inc11:
417  %inc12 = add nsw i32 %i.0, 1
418  %cmp = icmp slt i32 %inc12, %nx
419  br i1 %cmp, label %imperf_nest_5_loop_i, label %for.cond.for.end13_crit_edge
420
421for.cond.for.end13_crit_edge:
422  br label %for.end13
423
424for.end13:
425  ret void
426}
427
428; Test an imperfect loop nest of the form:
429;   for (int i = 0; i < nx; ++i)
430;     if (i > 5) { // user branch
431;       for (int j = 1; j <= 5; j+=2)
432;         y[j][i] = x[i][j] + j;
433;     }
434
435define void @imperf_nest_6(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) {
436;    CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_6_loop_i, Loops: ( imperf_nest_6_loop_i imperf_nest_6_loop_j )
437entry:
438  %cmp2 = icmp slt i32 0, %nx
439  br i1 %cmp2, label %imperf_nest_6_loop_i.lr.ph, label %for.end13
440
441imperf_nest_6_loop_i.lr.ph:
442  br label %imperf_nest_6_loop_i
443
444imperf_nest_6_loop_i:
445  %i.0 = phi i32 [ 0, %imperf_nest_6_loop_i.lr.ph ], [ %inc12, %for.inc11 ]
446  %cmp1 = icmp sgt i32 %i.0, 5
447  br i1 %cmp1, label %imperf_nest_6_loop_j.lr.ph, label %if.end
448
449imperf_nest_6_loop_j.lr.ph:
450  br label %imperf_nest_6_loop_j
451
452imperf_nest_6_loop_j:
453  %j.0 = phi i32 [ 1, %imperf_nest_6_loop_j.lr.ph ], [ %inc, %for.inc ]
454  %idxprom = sext i32 %i.0 to i64
455  %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom
456  %0 = load i32*, i32** %arrayidx, align 8
457  %idxprom5 = sext i32 %j.0 to i64
458  %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5
459  %1 = load i32, i32* %arrayidx6, align 4
460  %add = add nsw i32 %1, %j.0
461  %idxprom7 = sext i32 %j.0 to i64
462  %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7
463  %2 = load i32*, i32** %arrayidx8, align 8
464  %idxprom9 = sext i32 %i.0 to i64
465  %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9
466  store i32 %add, i32* %arrayidx10, align 4
467  br label %for.inc
468
469for.inc:
470  %inc = add nsw i32 %j.0, 2
471  %cmp3 = icmp sle i32 %inc, 5
472  br i1 %cmp3, label %imperf_nest_6_loop_j, label %for.cond2.for.end_crit_edge
473
474for.cond2.for.end_crit_edge:
475  br label %for.end
476
477for.end:
478  br label %if.end
479
480if.end:
481  br label %for.inc11
482
483for.inc11:
484  %inc12 = add nsw i32 %i.0, 1
485  %cmp = icmp slt i32 %inc12, %nx
486  br i1 %cmp, label %imperf_nest_6_loop_i, label %for.cond.for.end13_crit_edge
487
488for.cond.for.end13_crit_edge:
489  br label %for.end13
490
491for.end13:
492  ret void
493}
494