1; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -irce-allow-narrow-latch=true -S < %s 2>&1 | FileCheck %s
2; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,irce' -irce-allow-narrow-latch=true -S < %s 2>&1 | FileCheck %s
3
4; Check that we can remove trivially non-failing range check.
5define i32 @test_increasing_slt_slt_wide_simple_no_postloop() {
6
7; CHECK-LABEL: @test_increasing_slt_slt_wide_simple_no_postloop(
8; CHECK-NOT:   preloop
9; CHECK-NOT:   postloop
10; CHECK:       loop:
11; CHECK:       br i1 true, label %backedge, label %check_failed
12
13entry:
14  br label %loop
15
16loop:
17  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
18  %rc = icmp slt i64 %iv, 100
19  br i1 %rc, label %backedge, label %check_failed
20
21backedge:
22  %iv.next = add i64 %iv, 1
23  %narrow.iv = trunc i64 %iv.next to i32
24  %latch.cond = icmp slt i32 %narrow.iv, 100
25  br i1 %latch.cond, label %loop, label %exit
26
27exit:
28  ret i32 %narrow.iv
29
30check_failed:
31  ret i32 -1
32}
33
34; This range check fails on the last iteration, so it needs a postloop.
35define i32 @test_increasing_slt_slt_wide_simple_postloop() {
36
37; CHECK-LABEL: @test_increasing_slt_slt_wide_simple_postloop(
38; CHECK-NOT:   preloop
39; CHECK:       loop:
40; CHECK:       br i1 true, label %backedge, label %check_failed
41; CHECK:       backedge
42; CHECK:       [[COND:%[^ ]+]] = icmp slt i64 %wide.narrow.iv, 99
43; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
44; CHECK:       postloop
45
46entry:
47  br label %loop
48
49loop:
50  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
51  %rc = icmp slt i64 %iv, 99
52  br i1 %rc, label %backedge, label %check_failed
53
54backedge:
55  %iv.next = add i64 %iv, 1
56  %narrow.iv = trunc i64 %iv.next to i32
57  %latch.cond = icmp slt i32 %narrow.iv, 100
58  br i1 %latch.cond, label %loop, label %exit
59
60exit:
61  ret i32 %narrow.iv
62
63check_failed:
64  ret i32 -1
65}
66
67; General case. If both %N and %M are non-negative, we do not need a preloop.
68define i32 @test_increasing_slt_slt_wide_non-negative(i32* %n_ptr, i64* %m_ptr) {
69
70; CHECK-LABEL: @test_increasing_slt_slt_wide_non-negative(
71; CHECK-NOT:   preloop
72; CHECK:       loop:
73; CHECK:       br i1 true, label %backedge, label %check_failed
74; CHECK:       backedge
75; CHECK:       [[COND:%[^ ]+]] = icmp slt i64 %wide.narrow.iv, %exit.mainloop.at
76; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
77; CHECK:       postloop
78
79entry:
80  %N = load i32, i32* %n_ptr, !range !2
81  %M = load i64, i64* %m_ptr, !range !1
82  br label %loop
83
84loop:
85  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
86  %rc = icmp slt i64 %iv, %M
87  br i1 %rc, label %backedge, label %check_failed
88
89backedge:
90  %iv.next = add i64 %iv, 1
91  %narrow.iv = trunc i64 %iv.next to i32
92  %latch.cond = icmp slt i32 %narrow.iv, %N
93  br i1 %latch.cond, label %loop, label %exit
94
95exit:
96  ret i32 %narrow.iv
97
98check_failed:
99  ret i32 -1
100}
101
102; General case. Even though %M may be negative, we do not need a preloop because
103; we make a non-negativity runtime check against M and do not go to main loop if
104; M was negative.
105define i32 @test_increasing_slt_slt_wide_general(i32* %n_ptr, i64* %m_ptr) {
106
107; CHECK-LABEL: @test_increasing_slt_slt_wide_general(
108; CHECK-NOT:   preloop
109; CHECK:       loop:
110; CHECK:       br i1 true, label %backedge, label %check_failed
111; CHECK:       backedge
112; CHECK:       [[COND:%[^ ]+]] = icmp slt i64
113; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
114; CHECK:       postloop
115
116entry:
117  %N = load i32, i32* %n_ptr, !range !2
118  %M = load i64, i64* %m_ptr
119  br label %loop
120
121loop:
122  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
123  %rc = icmp slt i64 %iv, %M
124  br i1 %rc, label %backedge, label %check_failed
125
126backedge:
127  %iv.next = add i64 %iv, 1
128  %narrow.iv = trunc i64 %iv.next to i32
129  %latch.cond = icmp slt i32 %narrow.iv, %N
130  br i1 %latch.cond, label %loop, label %exit
131
132exit:
133  ret i32 %narrow.iv
134
135check_failed:
136  ret i32 -1
137}
138
139; General case with preloop.
140define i32 @test_increasing_slt_slt_wide_general_preloop(i32* %n_ptr, i64* %m_ptr) {
141
142; CHECK-LABEL: @test_increasing_slt_slt_wide_general_preloop(
143; CHECK:       loop:
144; CHECK:       br i1 true, label %backedge, label %check_failed
145; CHECK:       backedge
146; CHECK:       [[COND:%[^ ]+]] = icmp slt i64
147; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
148; CHECK:       preloop
149; CHECK:       postloop
150
151entry:
152  %N = load i32, i32* %n_ptr, !range !2
153  %M = load i64, i64* %m_ptr
154  br label %loop
155
156loop:
157  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
158  %rc = icmp slt i64 %iv, %M
159  br i1 %rc, label %backedge, label %check_failed
160
161backedge:
162  %iv.next = add i64 %iv, 1
163  %narrow.iv = trunc i64 %iv to i32
164  %latch.cond = icmp slt i32 %narrow.iv, %N
165  br i1 %latch.cond, label %loop, label %exit
166
167exit:
168  ret i32 %narrow.iv
169
170check_failed:
171  ret i32 -1
172}
173
174; Same as above, multiple checks.
175define i32 @test_increasing_slt_slt_wide_multiple_checks(i32* %n_ptr, i64* %m1_ptr, i64* %m2_ptr, i64* %m3_ptr, i64* %m4_ptr) {
176; CHECK-LABEL: @test_increasing_slt_slt_wide_multiple_checks(
177; CHECK-NOT:   preloop
178; CHECK:       loop:
179; CHECK:       %c1 = and i1 true, true
180; CHECK:       %c2 = and i1 %c1, true
181; CHECK:       %rc = and i1 %c2, true
182; CHECK:       br i1 %rc, label %backedge, label %check_failed.loopexit
183; CHECK:       backedge
184; CHECK:       [[COND:%[^ ]+]] = icmp slt i64
185; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
186; CHECK:       postloop
187
188entry:
189  %N = load i32, i32* %n_ptr, !range !2
190  %M1 = load i64, i64* %m1_ptr
191  %M2 = load i64, i64* %m2_ptr
192  %M3 = load i64, i64* %m3_ptr
193  %M4 = load i64, i64* %m4_ptr
194  br label %loop
195
196loop:
197  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
198  %rc1 = icmp slt i64 %iv, %M1
199  %rc2 = icmp slt i64 %iv, %M2
200  %rc3 = icmp slt i64 %iv, %M3
201  %rc4 = icmp slt i64 %iv, %M4
202  %c1 = and i1 %rc1, %rc2
203  %c2 = and i1 %c1, %rc3
204  %rc = and i1 %c2, %rc4
205  br i1 %rc, label %backedge, label %check_failed
206
207backedge:
208  %iv.next = add i64 %iv, 1
209  %narrow.iv = trunc i64 %iv.next to i32
210  %latch.cond = icmp slt i32 %narrow.iv, %N
211  br i1 %latch.cond, label %loop, label %exit
212
213exit:
214  ret i32 %narrow.iv
215
216check_failed:
217  ret i32 -1
218}
219
220; Wide IV against narrow range check. We don't currently support it.
221define i32 @test_increasing_slt_slt_wide_simple_negtest_narrow_rc() {
222
223; CHECK-LABEL: @test_increasing_slt_slt_wide_simple_negtest_narrow_rc(
224; CHECK-NOT:   i1 true
225; CHECK-NOT:   main
226
227entry:
228  br label %loop
229
230loop:
231  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
232  %narrow.iv = trunc i64 %iv to i32
233  %rc = icmp slt i32 %narrow.iv, 101
234  br i1 %rc, label %backedge, label %check_failed
235
236backedge:
237  %iv.next = add i64 %iv, 1
238  %latch.cond = icmp slt i64 %iv, 100
239  br i1 %latch.cond, label %loop, label %exit
240
241exit:
242  ret i32 %narrow.iv
243
244check_failed:
245  ret i32 -1
246}
247
248; Check that we can remove trivially non-failing range check.
249define i32 @test_increasing_ult_ult_wide_simple_no_postloop() {
250
251; CHECK-LABEL: @test_increasing_ult_ult_wide_simple_no_postloop(
252; CHECK-NOT:   preloop
253; CHECK-NOT:   postloop
254; CHECK:       loop:
255; CHECK:       br i1 true, label %backedge, label %check_failed
256
257entry:
258  br label %loop
259
260loop:
261  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
262  %rc = icmp ult i64 %iv, 100
263  br i1 %rc, label %backedge, label %check_failed
264
265backedge:
266  %iv.next = add i64 %iv, 1
267  %narrow.iv = trunc i64 %iv.next to i32
268  %latch.cond = icmp ult i32 %narrow.iv, 100
269  br i1 %latch.cond, label %loop, label %exit
270
271exit:
272  ret i32 %narrow.iv
273
274check_failed:
275  ret i32 -1
276}
277
278; This range check fails on the last iteration, so it needs a postloop.
279define i32 @test_increasing_ult_ult_wide_simple_postloop() {
280
281; CHECK-LABEL: @test_increasing_ult_ult_wide_simple_postloop(
282; CHECK-NOT:   preloop
283; CHECK:       loop:
284; CHECK:       br i1 true, label %backedge, label %check_failed
285; CHECK:       backedge
286; CHECK:       [[COND:%[^ ]+]] = icmp ult i64 %wide.narrow.iv, 99
287; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
288; CHECK:       postloop
289
290entry:
291  br label %loop
292
293loop:
294  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
295  %rc = icmp ult i64 %iv, 99
296  br i1 %rc, label %backedge, label %check_failed
297
298backedge:
299  %iv.next = add i64 %iv, 1
300  %narrow.iv = trunc i64 %iv.next to i32
301  %latch.cond = icmp ult i32 %narrow.iv, 100
302  br i1 %latch.cond, label %loop, label %exit
303
304exit:
305  ret i32 %narrow.iv
306
307check_failed:
308  ret i32 -1
309}
310
311; General case. If both %N and %M are non-negative, we do not need a preloop.
312define i32 @test_increasing_ult_ult_wide_non-negative(i32* %n_ptr, i64* %m_ptr) {
313
314; CHECK-LABEL: @test_increasing_ult_ult_wide_non-negative(
315; CHECK-NOT:   preloop
316; CHECK:       loop:
317; CHECK:       br i1 true, label %backedge, label %check_failed
318; CHECK:       backedge
319; CHECK:       [[COND:%[^ ]+]] = icmp ult i64 %wide.narrow.iv, %exit.mainloop.at
320; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
321; CHECK:       postloop
322
323entry:
324  %N = load i32, i32* %n_ptr, !range !2
325  %M = load i64, i64* %m_ptr, !range !1
326  br label %loop
327
328loop:
329  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
330  %rc = icmp ult i64 %iv, %M
331  br i1 %rc, label %backedge, label %check_failed
332
333backedge:
334  %iv.next = add i64 %iv, 1
335  %narrow.iv = trunc i64 %iv.next to i32
336  %latch.cond = icmp ult i32 %narrow.iv, %N
337  br i1 %latch.cond, label %loop, label %exit
338
339exit:
340  ret i32 %narrow.iv
341
342check_failed:
343  ret i32 -1
344}
345
346; General case. Even though %M may be negative, we do not need a preloop because
347; we make a non-negativity runtime check against M and do not go to main loop if
348; M was negative.
349define i32 @test_increasing_ult_ult_wide_general(i32* %n_ptr, i64* %m_ptr) {
350
351; CHECK-LABEL: @test_increasing_ult_ult_wide_general(
352; CHECK-NOT:   preloop
353; CHECK:       loop:
354; CHECK:       br i1 true, label %backedge, label %check_failed
355; CHECK:       backedge
356; CHECK:       [[COND:%[^ ]+]] = icmp ult i64
357; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
358; CHECK:       postloop
359
360entry:
361  %N = load i32, i32* %n_ptr, !range !2
362  %M = load i64, i64* %m_ptr
363  br label %loop
364
365loop:
366  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
367  %rc = icmp ult i64 %iv, %M
368  br i1 %rc, label %backedge, label %check_failed
369
370backedge:
371  %iv.next = add i64 %iv, 1
372  %narrow.iv = trunc i64 %iv.next to i32
373  %latch.cond = icmp ult i32 %narrow.iv, %N
374  br i1 %latch.cond, label %loop, label %exit
375
376exit:
377  ret i32 %narrow.iv
378
379check_failed:
380  ret i32 -1
381}
382
383; Same as above, multiple checks.
384define i32 @test_increasing_ult_ult_wide_multiple_checks(i32* %n_ptr, i64* %m1_ptr, i64* %m2_ptr, i64* %m3_ptr, i64* %m4_ptr) {
385; CHECK-LABEL: @test_increasing_ult_ult_wide_multiple_checks(
386; CHECK-NOT:   preloop
387; CHECK:       loop:
388; CHECK:       %c1 = and i1 true, true
389; CHECK:       %c2 = and i1 %c1, true
390; CHECK:       %rc = and i1 %c2, true
391; CHECK:       br i1 %rc, label %backedge, label %check_failed.loopexit
392; CHECK:       backedge
393; CHECK:       [[COND:%[^ ]+]] = icmp ult i64
394; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
395; CHECK:       postloop
396
397entry:
398  %N = load i32, i32* %n_ptr, !range !2
399  %M1 = load i64, i64* %m1_ptr
400  %M2 = load i64, i64* %m2_ptr
401  %M3 = load i64, i64* %m3_ptr
402  %M4 = load i64, i64* %m4_ptr
403  br label %loop
404
405loop:
406  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
407  %rc1 = icmp ult i64 %iv, %M1
408  %rc2 = icmp ult i64 %iv, %M2
409  %rc3 = icmp ult i64 %iv, %M3
410  %rc4 = icmp ult i64 %iv, %M4
411  %c1 = and i1 %rc1, %rc2
412  %c2 = and i1 %c1, %rc3
413  %rc = and i1 %c2, %rc4
414  br i1 %rc, label %backedge, label %check_failed
415
416backedge:
417  %iv.next = add i64 %iv, 1
418  %narrow.iv = trunc i64 %iv.next to i32
419  %latch.cond = icmp ult i32 %narrow.iv, %N
420  br i1 %latch.cond, label %loop, label %exit
421
422exit:
423  ret i32 %narrow.iv
424
425check_failed:
426  ret i32 -1
427}
428
429; Wide IV against narrow range check. We don't currently support it.
430define i32 @test_increasing_ult_ult_wide_simple_negtest_narrow_rc() {
431
432; CHECK-LABEL: @test_increasing_ult_ult_wide_simple_negtest_narrow_rc(
433; CHECK-NOT:   i1 true
434; CHECK-NOT:   main
435
436entry:
437  br label %loop
438
439loop:
440  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
441  %narrow.iv = trunc i64 %iv to i32
442  %rc = icmp ult i32 %narrow.iv, 101
443  br i1 %rc, label %backedge, label %check_failed
444
445backedge:
446  %iv.next = add i64 %iv, 1
447  %latch.cond = icmp ult i64 %iv, 100
448  br i1 %latch.cond, label %loop, label %exit
449
450exit:
451  ret i32 %narrow.iv
452
453check_failed:
454  ret i32 -1
455}
456
457!0 = !{i32 0, i32 2147483647}
458!1 = !{i64 0, i64 9223372036854775807}
459!2 = !{i32 1, i32 2147483647}
460