• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1; RUN: opt -analyze -scalar-evolution -S < %s | FileCheck %s
2
3; Every combination of
4;  - starting at 0, 1, or %x
5;  - steping by 1 or 2
6;  - stopping at %n or %n*2
7;  - using nsw, or not
8
9; Some of these represent missed opportunities.
10
11; CHECK: Determining loop execution counts for: @foo
12; CHECK: Loop %loop: backedge-taken count is (-1 + %n)
13; CHECK: Loop %loop: max backedge-taken count is 6
14define void @foo(i4 %n) {
15entry:
16  %s = icmp sgt i4 %n, 0
17  br i1 %s, label %loop, label %exit
18loop:
19  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
20  %i.next = add i4 %i, 1
21  %t = icmp slt i4 %i.next, %n
22  br i1 %t, label %loop, label %exit
23exit:
24  ret void
25}
26
27; CHECK: Determining loop execution counts for: @step2
28; CHECK: Loop %loop: Unpredictable backedge-taken count.
29; CHECK: Loop %loop: Unpredictable max backedge-taken count.
30define void @step2(i4 %n) {
31entry:
32  %s = icmp sgt i4 %n, 0
33  br i1 %s, label %loop, label %exit
34loop:
35  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
36  %i.next = add i4 %i, 2
37  %t = icmp slt i4 %i.next, %n
38  br i1 %t, label %loop, label %exit
39exit:
40  ret void
41}
42
43; CHECK: Determining loop execution counts for: @start1
44; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n))
45; CHECK: Loop %loop: max backedge-taken count is 5
46define void @start1(i4 %n) {
47entry:
48  %s = icmp sgt i4 %n, 0
49  br i1 %s, label %loop, label %exit
50loop:
51  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
52  %i.next = add i4 %i, 1
53  %t = icmp slt i4 %i.next, %n
54  br i1 %t, label %loop, label %exit
55exit:
56  ret void
57}
58
59; CHECK: Determining loop execution counts for: @start1_step2
60; CHECK: Loop %loop: Unpredictable backedge-taken count.
61; CHECK: Loop %loop: Unpredictable max backedge-taken count.
62define void @start1_step2(i4 %n) {
63entry:
64  %s = icmp sgt i4 %n, 0
65  br i1 %s, label %loop, label %exit
66loop:
67  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
68  %i.next = add i4 %i, 2
69  %t = icmp slt i4 %i.next, %n
70  br i1 %t, label %loop, label %exit
71exit:
72  ret void
73}
74
75; CHECK: Determining loop execution counts for: @startx
76; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))
77; CHECK: Loop %loop: max backedge-taken count is -1
78define void @startx(i4 %n, i4 %x) {
79entry:
80  %s = icmp sgt i4 %n, 0
81  br i1 %s, label %loop, label %exit
82loop:
83  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
84  %i.next = add i4 %i, 1
85  %t = icmp slt i4 %i.next, %n
86  br i1 %t, label %loop, label %exit
87exit:
88  ret void
89}
90
91; CHECK: Determining loop execution counts for: @startx_step2
92; CHECK: Loop %loop: Unpredictable backedge-taken count.
93; CHECK: Loop %loop: Unpredictable max backedge-taken count.
94define void @startx_step2(i4 %n, i4 %x) {
95entry:
96  %s = icmp sgt i4 %n, 0
97  br i1 %s, label %loop, label %exit
98loop:
99  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
100  %i.next = add i4 %i, 2
101  %t = icmp slt i4 %i.next, %n
102  br i1 %t, label %loop, label %exit
103exit:
104  ret void
105}
106
107; CHECK: Determining loop execution counts for: @nsw
108; CHECK: Loop %loop: backedge-taken count is (-1 + %n)
109; CHECK: Loop %loop: max backedge-taken count is 6
110define void @nsw(i4 %n) {
111entry:
112  %s = icmp sgt i4 %n, 0
113  br i1 %s, label %loop, label %exit
114loop:
115  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
116  %i.next = add nsw i4 %i, 1
117  %t = icmp slt i4 %i.next, %n
118  br i1 %t, label %loop, label %exit
119exit:
120  ret void
121}
122
123; If %n is INT4_MAX, %i.next will wrap. The nsw bit says that the
124; result is undefined. Therefore, after the loop's second iteration,
125; we are free to assume that the loop exits. This is valid because:
126; (a) %i.next is a poison value after the second iteration, which can
127; also be considered an undef value.
128; (b) the return instruction enacts a side effect that is control
129; dependent on the poison value.
130;
131; CHECK-LABEL: nsw_step2
132; CHECK: Determining loop execution counts for: @nsw_step2
133; CHECK: Loop %loop: backedge-taken count is ((-1 + %n) /u 2)
134; CHECK: Loop %loop: max backedge-taken count is 2
135define void @nsw_step2(i4 %n) {
136entry:
137  %s = icmp sgt i4 %n, 0
138  br i1 %s, label %loop, label %exit
139loop:
140  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
141  %i.next = add nsw i4 %i, 2
142  %t = icmp slt i4 %i.next, %n
143  br i1 %t, label %loop, label %exit
144exit:
145  ret void
146}
147
148; CHECK-LABEL: nsw_start1
149; CHECK: Determining loop execution counts for: @nsw_start1
150; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax %n))
151; CHECK: Loop %loop: max backedge-taken count is 5
152define void @nsw_start1(i4 %n) {
153entry:
154  %s = icmp sgt i4 %n, 0
155  br i1 %s, label %loop, label %exit
156loop:
157  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
158  %i.next = add nsw i4 %i, 1
159  %t = icmp slt i4 %i.next, %n
160  br i1 %t, label %loop, label %exit
161exit:
162  ret void
163}
164
165; CHECK: Determining loop execution counts for: @nsw_start1_step2
166; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax %n)) /u 2)
167; CHECK: Loop %loop: max backedge-taken count is 2
168define void @nsw_start1_step2(i4 %n) {
169entry:
170  %s = icmp sgt i4 %n, 0
171  br i1 %s, label %loop, label %exit
172loop:
173  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
174  %i.next = add nsw i4 %i, 2
175  %t = icmp slt i4 %i.next, %n
176  br i1 %t, label %loop, label %exit
177exit:
178  ret void
179}
180
181; CHECK: Determining loop execution counts for: @nsw_startx
182; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))
183; CHECK: Loop %loop: max backedge-taken count is -1
184define void @nsw_startx(i4 %n, i4 %x) {
185entry:
186  %s = icmp sgt i4 %n, 0
187  br i1 %s, label %loop, label %exit
188loop:
189  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
190  %i.next = add nsw i4 %i, 1
191  %t = icmp slt i4 %i.next, %n
192  br i1 %t, label %loop, label %exit
193exit:
194  ret void
195}
196
197; CHECK: Determining loop execution counts for: @nsw_startx_step2
198; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax %n)) /u 2)
199; CHECK: Loop %loop: max backedge-taken count is 7
200define void @nsw_startx_step2(i4 %n, i4 %x) {
201entry:
202  %s = icmp sgt i4 %n, 0
203  br i1 %s, label %loop, label %exit
204loop:
205  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
206  %i.next = add nsw i4 %i, 2
207  %t = icmp slt i4 %i.next, %n
208  br i1 %t, label %loop, label %exit
209exit:
210  ret void
211}
212
213; CHECK: Determining loop execution counts for: @even
214; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n))
215; CHECK: Loop %loop: max backedge-taken count is 5
216define void @even(i4 %n) {
217entry:
218  %m = shl i4 %n, 1
219  %s = icmp sgt i4 %m, 0
220  br i1 %s, label %loop, label %exit
221loop:
222  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
223  %i.next = add i4 %i, 1
224  %t = icmp slt i4 %i.next, %m
225  br i1 %t, label %loop, label %exit
226exit:
227  ret void
228}
229
230; CHECK: Determining loop execution counts for: @even_step2
231; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2)
232; CHECK: Loop %loop: max backedge-taken count is 2
233define void @even_step2(i4 %n) {
234entry:
235  %m = shl i4 %n, 1
236  %s = icmp sgt i4 %m, 0
237  br i1 %s, label %loop, label %exit
238loop:
239  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
240  %i.next = add i4 %i, 2
241  %t = icmp slt i4 %i.next, %m
242  br i1 %t, label %loop, label %exit
243exit:
244  ret void
245}
246
247; CHECK: Determining loop execution counts for: @even_start1
248; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n)))
249; CHECK: Loop %loop: max backedge-taken count is 4
250define void @even_start1(i4 %n) {
251entry:
252  %m = shl i4 %n, 1
253  %s = icmp sgt i4 %m, 0
254  br i1 %s, label %loop, label %exit
255loop:
256  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
257  %i.next = add i4 %i, 1
258  %t = icmp slt i4 %i.next, %m
259  br i1 %t, label %loop, label %exit
260exit:
261  ret void
262}
263
264; CHECK: Determining loop execution counts for: @even_start1_step2
265; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2)
266; CHECK: Loop %loop: max backedge-taken count is 2
267define void @even_start1_step2(i4 %n) {
268entry:
269  %m = shl i4 %n, 1
270  %s = icmp sgt i4 %m, 0
271  br i1 %s, label %loop, label %exit
272loop:
273  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
274  %i.next = add i4 %i, 2
275  %t = icmp slt i4 %i.next, %m
276  br i1 %t, label %loop, label %exit
277exit:
278  ret void
279}
280
281; CHECK: Determining loop execution counts for: @even_startx
282; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))
283; CHECK: Loop %loop: max backedge-taken count is -2
284define void @even_startx(i4 %n, i4 %x) {
285entry:
286  %m = shl i4 %n, 1
287  %s = icmp sgt i4 %m, 0
288  br i1 %s, label %loop, label %exit
289loop:
290  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
291  %i.next = add i4 %i, 1
292  %t = icmp slt i4 %i.next, %m
293  br i1 %t, label %loop, label %exit
294exit:
295  ret void
296}
297
298; CHECK: Determining loop execution counts for: @even_startx_step2
299; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)
300; CHECK: Loop %loop: max backedge-taken count is 7
301define void @even_startx_step2(i4 %n, i4 %x) {
302entry:
303  %m = shl i4 %n, 1
304  %s = icmp sgt i4 %m, 0
305  br i1 %s, label %loop, label %exit
306loop:
307  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
308  %i.next = add i4 %i, 2
309  %t = icmp slt i4 %i.next, %m
310  br i1 %t, label %loop, label %exit
311exit:
312  ret void
313}
314
315; CHECK: Determining loop execution counts for: @even_nsw
316; CHECK: Loop %loop: backedge-taken count is (-1 + (2 * %n))
317; CHECK: Loop %loop: max backedge-taken count is 5
318define void @even_nsw(i4 %n) {
319entry:
320  %m = shl i4 %n, 1
321  %s = icmp sgt i4 %m, 0
322  br i1 %s, label %loop, label %exit
323loop:
324  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
325  %i.next = add nsw i4 %i, 1
326  %t = icmp slt i4 %i.next, %m
327  br i1 %t, label %loop, label %exit
328exit:
329  ret void
330}
331
332; CHECK: Determining loop execution counts for: @even_nsw_step2
333; CHECK: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2)
334; CHECK: Loop %loop: max backedge-taken count is 2
335define void @even_nsw_step2(i4 %n) {
336entry:
337  %m = shl i4 %n, 1
338  %s = icmp sgt i4 %m, 0
339  br i1 %s, label %loop, label %exit
340loop:
341  %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]
342  %i.next = add nsw i4 %i, 2
343  %t = icmp slt i4 %i.next, %m
344  br i1 %t, label %loop, label %exit
345exit:
346  ret void
347}
348
349; CHECK: Determining loop execution counts for: @even_nsw_start1
350; CHECK: Loop %loop: backedge-taken count is (-2 + (2 smax (2 * %n)))
351; CHECK: Loop %loop: max backedge-taken count is 4
352define void @even_nsw_start1(i4 %n) {
353entry:
354  %m = shl i4 %n, 1
355  %s = icmp sgt i4 %m, 0
356  br i1 %s, label %loop, label %exit
357loop:
358  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
359  %i.next = add nsw i4 %i, 1
360  %t = icmp slt i4 %i.next, %m
361  br i1 %t, label %loop, label %exit
362exit:
363  ret void
364}
365
366; CHECK: Determining loop execution counts for: @even_nsw_start1_step2
367; CHECK: Loop %loop: backedge-taken count is ((-2 + (3 smax (2 * %n))) /u 2)
368; CHECK: Loop %loop: max backedge-taken count is 2
369define void @even_nsw_start1_step2(i4 %n) {
370entry:
371  %m = shl i4 %n, 1
372  %s = icmp sgt i4 %m, 0
373  br i1 %s, label %loop, label %exit
374loop:
375  %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]
376  %i.next = add nsw i4 %i, 2
377  %t = icmp slt i4 %i.next, %m
378  br i1 %t, label %loop, label %exit
379exit:
380  ret void
381}
382
383; CHECK: Determining loop execution counts for: @even_nsw_startx
384; CHECK: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))
385; CHECK: Loop %loop: max backedge-taken count is -2
386define void @even_nsw_startx(i4 %n, i4 %x) {
387entry:
388  %m = shl i4 %n, 1
389  %s = icmp sgt i4 %m, 0
390  br i1 %s, label %loop, label %exit
391loop:
392  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
393  %i.next = add nsw i4 %i, 1
394  %t = icmp slt i4 %i.next, %m
395  br i1 %t, label %loop, label %exit
396exit:
397  ret void
398}
399
400; CHECK: Determining loop execution counts for: @even_nsw_startx_step2
401; CHECK: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)
402; CHECK: Loop %loop: max backedge-taken count is 7
403define void @even_nsw_startx_step2(i4 %n, i4 %x) {
404entry:
405  %m = shl i4 %n, 1
406  %s = icmp sgt i4 %m, 0
407  br i1 %s, label %loop, label %exit
408loop:
409  %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]
410  %i.next = add nsw i4 %i, 2
411  %t = icmp slt i4 %i.next, %m
412  br i1 %t, label %loop, label %exit
413exit:
414  ret void
415}
416