1; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
2; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,irce' -S < %s 2>&1 | FileCheck %s
3
4; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
5; CHECK: irce: in function test_02: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
6; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
7; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
8; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
9; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
10; CHECK-NOT: irce: in function test_07: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
11; CHECK: irce: in function test_08: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
12; CHECK-NOT: irce: in function test_09: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
13
14; ULT condition for increasing loop.
15define void @test_01(i32* %arr, i32* %a_len_ptr) #0 {
16
17; CHECK:      test_01
18; CHECK:        entry:
19; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0
20; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
21; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
22; CHECK:        loop:
23; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
24; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
25; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
26; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
27; CHECK-NOT:    loop.preloop:
28; CHECK:        loop.postloop:
29; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
30; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
31; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
32; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
33
34entry:
35  %len = load i32, i32* %a_len_ptr, !range !0
36  br label %loop
37
38loop:
39  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
40  %idx.next = add nsw nuw i32 %idx, 1
41  %abc = icmp ult i32 %idx, %len
42  br i1 %abc, label %in.bounds, label %out.of.bounds
43
44in.bounds:
45  %addr = getelementptr i32, i32* %arr, i32 %idx
46  store i32 0, i32* %addr
47  %next = icmp ult i32 %idx.next, 100
48  br i1 %next, label %loop, label %exit
49
50out.of.bounds:
51  ret void
52
53exit:
54  ret void
55}
56
57; ULT condition for decreasing loops.
58define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
59
60; CHECK: test_02(
61; CHECK:        entry:
62; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, align 4, !range !0
63; CHECK-NEXT:     [[UMIN:%[^ ]+]] = call i32 @llvm.umax.i32(i32 %len, i32 1)
64; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
65; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 100, %exit.preloop.at
66; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
67; CHECK:        mainloop:
68; CHECK-NEXT:     br label %loop
69; CHECK:        loop:
70; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
71; CHECK-NEXT:     %idx.next = add i32 %idx, -1
72; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len
73; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
74; CHECK-NOT:    loop.postloop:
75; CHECK:        loop.preloop:
76; CHECK-NEXT:     %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ 100, %loop.preloop.preheader ]
77; CHECK-NEXT:     %idx.next.preloop = add i32 %idx.preloop, -1
78; CHECK-NEXT:     %abc.preloop = icmp ult i32 %idx.preloop, %len
79; CHECK-NEXT:     br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
80
81entry:
82  %len = load i32, i32* %a_len_ptr, !range !0
83  br label %loop
84
85loop:
86  %idx = phi i32 [ 100, %entry ], [ %idx.next, %in.bounds ]
87  %idx.next = add i32 %idx, -1
88  %abc = icmp ult i32 %idx, %len
89  br i1 %abc, label %in.bounds, label %out.of.bounds
90
91in.bounds:
92  %addr = getelementptr i32, i32* %arr, i32 %idx
93  store i32 0, i32* %addr
94  %next = icmp ult i32 %idx.next, 1
95  br i1 %next, label %exit, label %loop
96
97out.of.bounds:
98  ret void
99
100exit:
101  ret void
102}
103
104; Check SINT_MAX.
105define void @test_03(i32* %arr, i32* %a_len_ptr) #0 {
106
107; CHECK:      test_03
108; CHECK:        entry:
109; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0
110; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
111; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
112; CHECK:        loop:
113; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
114; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
115; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
116; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
117; CHECK-NOT:    loop.preloop:
118; CHECK:        loop.postloop:
119; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
120; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
121; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
122; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
123
124entry:
125  %len = load i32, i32* %a_len_ptr, !range !0
126  br label %loop
127
128loop:
129  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
130  %idx.next = add nsw nuw i32 %idx, 1
131  %abc = icmp ult i32 %idx, %len
132  br i1 %abc, label %in.bounds, label %out.of.bounds
133
134in.bounds:
135  %addr = getelementptr i32, i32* %arr, i32 %idx
136  store i32 0, i32* %addr
137  %next = icmp ult i32 %idx.next, 2147483647
138  br i1 %next, label %loop, label %exit
139
140out.of.bounds:
141  ret void
142
143exit:
144  ret void
145}
146
147; Check SINT_MAX + 1, test is similar to test_01.
148define void @test_04(i32* %arr, i32* %a_len_ptr) #0 {
149
150; CHECK:      test_04
151; CHECK:        entry:
152; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0
153; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
154; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
155; CHECK:        loop:
156; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
157; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
158; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
159; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
160; CHECK-NOT:    loop.preloop:
161; CHECK:        loop.postloop:
162; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
163; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
164; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
165; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
166
167entry:
168  %len = load i32, i32* %a_len_ptr, !range !0
169  br label %loop
170
171loop:
172  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
173  %idx.next = add nsw nuw i32 %idx, 1
174  %abc = icmp ult i32 %idx, %len
175  br i1 %abc, label %in.bounds, label %out.of.bounds
176
177in.bounds:
178  %addr = getelementptr i32, i32* %arr, i32 %idx
179  store i32 0, i32* %addr
180  %next = icmp ult i32 %idx.next, 2147483648
181  br i1 %next, label %loop, label %exit
182
183out.of.bounds:
184  ret void
185
186exit:
187  ret void
188}
189
190; Check SINT_MAX + 1, test is similar to test_02.
191define void @test_05(i32* %arr, i32* %a_len_ptr) #0 {
192; CHECK: test_05(
193; CHECK:        entry:
194; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, align 4, !range !0
195; CHECK-NEXT:     [[UMIN:%[^ ]+]] = call i32 @llvm.umax.i32(i32 %len, i32 1)
196; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
197; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 -2147483648, %exit.preloop.at
198; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
199; CHECK:        mainloop:
200; CHECK-NEXT:     br label %loop
201; CHECK:        loop:
202; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
203; CHECK-NEXT:     %idx.next = add i32 %idx, -1
204; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len
205; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
206; CHECK-NOT:    loop.postloop:
207; CHECK:        loop.preloop:
208; CHECK-NEXT:     %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ -2147483648, %loop.preloop.preheader ]
209; CHECK-NEXT:     %idx.next.preloop = add i32 %idx.preloop, -1
210; CHECK-NEXT:     %abc.preloop = icmp ult i32 %idx.preloop, %len
211; CHECK-NEXT:     br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
212
213entry:
214  %len = load i32, i32* %a_len_ptr, !range !0
215  br label %loop
216
217loop:
218  %idx = phi i32 [ 2147483648, %entry ], [ %idx.next, %in.bounds ]
219  %idx.next = add i32 %idx, -1
220  %abc = icmp ult i32 %idx, %len
221  br i1 %abc, label %in.bounds, label %out.of.bounds
222
223in.bounds:
224  %addr = getelementptr i32, i32* %arr, i32 %idx
225  store i32 0, i32* %addr
226  %next = icmp ult i32 %idx.next, 1
227  br i1 %next, label %exit, label %loop
228
229out.of.bounds:
230  ret void
231
232exit:
233  ret void
234}
235
236; Increasing loop, UINT_MAX. Positive test.
237define void @test_06(i32* %arr, i32* %a_len_ptr) #0 {
238
239; CHECK:      test_06
240; CHECK:        entry:
241; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0
242; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
243; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
244; CHECK:        loop:
245; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
246; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
247; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
248; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
249; CHECK-NOT:    loop.preloop:
250; CHECK:        loop.postloop:
251; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
252; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
253; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
254; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
255
256entry:
257  %len = load i32, i32* %a_len_ptr, !range !0
258  br label %loop
259
260loop:
261  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
262  %idx.next = add nsw nuw i32 %idx, 1
263  %abc = icmp ult i32 %idx, %len
264  br i1 %abc, label %in.bounds, label %out.of.bounds
265
266in.bounds:
267  %addr = getelementptr i32, i32* %arr, i32 %idx
268  store i32 0, i32* %addr
269  %next = icmp ult i32 %idx.next, 4294967295
270  br i1 %next, label %loop, label %exit
271
272out.of.bounds:
273  ret void
274
275exit:
276  ret void
277}
278
279; Decreasing loop, UINT_MAX. Negative test: we cannot substract -1 from 0.
280define void @test_07(i32* %arr, i32* %a_len_ptr) #0 {
281
282; CHECK: test_07(
283; CHECK-NOT:    loop.preloop:
284; CHECK-NOT:    loop.postloop:
285
286entry:
287  %len = load i32, i32* %a_len_ptr, !range !0
288  br label %loop
289
290loop:
291  %idx = phi i32 [ 4294967295, %entry ], [ %idx.next, %in.bounds ]
292  %idx.next = add nuw i32 %idx, -1
293  %abc = icmp ult i32 %idx, %len
294  br i1 %abc, label %in.bounds, label %out.of.bounds
295
296in.bounds:
297  %addr = getelementptr i32, i32* %arr, i32 %idx
298  store i32 0, i32* %addr
299  %next = icmp ult i32 %idx.next, 0
300  br i1 %next, label %exit, label %loop
301
302out.of.bounds:
303  ret void
304
305exit:
306  ret void
307}
308
309; Unsigned walking through signed border is allowed.
310; Iteration space [0; UINT_MAX - 99), the fact that SINT_MAX is within this
311; range does not prevent us from performing IRCE.
312
313define void @test_08(i32* %arr, i32* %a_len_ptr) #0 {
314
315; CHECK:      test_08
316; CHECK:        entry:
317; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0
318; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
319; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
320; CHECK:        loop:
321; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
322; CHECK-NEXT:     %idx.next = add i32 %idx, 1
323; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
324; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
325; CHECK-NOT:    loop.preloop:
326; CHECK:        loop.postloop:
327; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
328; CHECK-NEXT:     %idx.next.postloop = add i32 %idx.postloop, 1
329; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
330; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
331
332entry:
333  %len = load i32, i32* %a_len_ptr, !range !0
334  br label %loop
335
336loop:
337  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
338  %idx.next = add i32 %idx, 1
339  %abc = icmp ult i32 %idx, %len
340  br i1 %abc, label %in.bounds, label %out.of.bounds
341
342in.bounds:
343  %addr = getelementptr i32, i32* %arr, i32 %idx
344  store i32 0, i32* %addr
345  %next = icmp ult i32 %idx.next, -100
346  br i1 %next, label %loop, label %exit
347
348out.of.bounds:
349  ret void
350
351exit:
352  ret void
353}
354
355; Walking through the border of unsigned range is not allowed
356; (iteration space [-100; 100)). Negative test.
357
358define void @test_09(i32* %arr, i32* %a_len_ptr) #0 {
359
360; CHECK:      test_09
361; CHECK-NOT:  preloop
362; CHECK-NOT:  postloop
363; CHECK-NOT:  br i1 false
364; CHECK-NOT:  br i1 true
365
366entry:
367  %len = load i32, i32* %a_len_ptr, !range !0
368  br label %loop
369
370loop:
371  %idx = phi i32 [ -100, %entry ], [ %idx.next, %in.bounds ]
372  %idx.next = add i32 %idx, 1
373  %abc = icmp ult i32 %idx, %len
374  br i1 %abc, label %in.bounds, label %out.of.bounds
375
376in.bounds:
377  %addr = getelementptr i32, i32* %arr, i32 %idx
378  store i32 0, i32* %addr
379  %next = icmp ult i32 %idx.next, 100
380  br i1 %next, label %loop, label %exit
381
382out.of.bounds:
383  ret void
384
385exit:
386  ret void
387}
388
389!0 = !{i32 0, i32 50}
390