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-NOT: 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
11; UGT condition for increasing loop.
12define void @test_01(i32* %arr, i32* %a_len_ptr) #0 {
13
14; CHECK: test_01(
15; CHECK:        entry:
16; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0
17; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
18; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
19; CHECK:        loop:
20; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
21; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
22; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
23; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
24; CHECK-NOT:    loop.preloop:
25; CHECK:        loop.postloop:
26; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
27; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
28; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
29; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
30
31entry:
32  %len = load i32, i32* %a_len_ptr, !range !0
33  br label %loop
34
35loop:
36  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
37  %idx.next = add nsw nuw i32 %idx, 1
38  %abc = icmp ult i32 %idx, %len
39  br i1 %abc, label %in.bounds, label %out.of.bounds
40
41in.bounds:
42  %addr = getelementptr i32, i32* %arr, i32 %idx
43  store i32 0, i32* %addr
44  %next = icmp ugt i32 %idx.next, 100
45  br i1 %next, label %exit, label %loop
46
47out.of.bounds:
48  ret void
49
50exit:
51  ret void
52}
53
54; UGT condition for decreasing loop.
55define void @test_02(i32* %arr, i32* %a_len_ptr) #0 {
56
57; CHECK: test_02(
58; CHECK:        entry:
59; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, align 4, !range !0
60; CHECK-NEXT:     [[UMIN:%[^ ]+]] = call i32 @llvm.umax.i32(i32 %len, i32 1)
61; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
62; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 100, %exit.preloop.at
63; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
64; CHECK:        mainloop:
65; CHECK-NEXT:     br label %loop
66; CHECK:        loop:
67; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
68; CHECK-NEXT:     %idx.next = add i32 %idx, -1
69; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len
70; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
71; CHECK-NOT:    loop.postloop:
72; CHECK:        loop.preloop:
73; CHECK-NEXT:     %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ 100, %loop.preloop.preheader ]
74; CHECK-NEXT:     %idx.next.preloop = add i32 %idx.preloop, -1
75; CHECK-NEXT:     %abc.preloop = icmp ult i32 %idx.preloop, %len
76; CHECK-NEXT:     br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
77
78entry:
79  %len = load i32, i32* %a_len_ptr, !range !0
80  br label %loop
81
82loop:
83  %idx = phi i32 [ 100, %entry ], [ %idx.next, %in.bounds ]
84  %idx.next = add i32 %idx, -1
85  %abc = icmp ult i32 %idx, %len
86  br i1 %abc, label %in.bounds, label %out.of.bounds
87
88in.bounds:
89  %addr = getelementptr i32, i32* %arr, i32 %idx
90  store i32 0, i32* %addr
91  %next = icmp ugt i32 %idx.next, 0
92  br i1 %next, label %loop, label %exit
93
94out.of.bounds:
95  ret void
96
97exit:
98  ret void
99}
100
101; Check SINT_MAX + 1, test is similar to test_01.
102define void @test_03(i32* %arr, i32* %a_len_ptr) #0 {
103
104; CHECK: test_03(
105; CHECK:        entry:
106; CHECK-NEXT:     %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0
107; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at
108; CHECK-NEXT:     br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit
109; CHECK:        loop:
110; CHECK-NEXT:     %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ]
111; CHECK-NEXT:     %idx.next = add nuw nsw i32 %idx, 1
112; CHECK-NEXT:     %abc = icmp ult i32 %idx, %exit.mainloop.at
113; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
114; CHECK-NOT:    loop.preloop:
115; CHECK:        loop.postloop:
116; CHECK-NEXT:     %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ]
117; CHECK-NEXT:     %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1
118; CHECK-NEXT:     %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at
119; CHECK-NEXT:     br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit
120
121entry:
122  %len = load i32, i32* %a_len_ptr, !range !0
123  br label %loop
124
125loop:
126  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
127  %idx.next = add nsw nuw i32 %idx, 1
128  %abc = icmp ult i32 %idx, %len
129  br i1 %abc, label %in.bounds, label %out.of.bounds
130
131in.bounds:
132  %addr = getelementptr i32, i32* %arr, i32 %idx
133  store i32 0, i32* %addr
134  %next = icmp ugt i32 %idx.next, 2147483648
135  br i1 %next, label %exit, label %loop
136
137out.of.bounds:
138  ret void
139
140exit:
141  ret void
142}
143
144; Check SINT_MAX + 1, test is similar to test_02.
145define void @test_04(i32* %arr, i32* %a_len_ptr) #0 {
146
147; CHECK: test_04(
148; CHECK:        entry:
149; CHECK-NEXT:     %len = load i32, i32* %a_len_ptr, align 4, !range !0
150; CHECK-NEXT:     [[UMIN:%[^ ]+]] = call i32 @llvm.umax.i32(i32 %len, i32 1)
151; CHECK-NEXT:     %exit.preloop.at = add nsw i32 [[UMIN]], -1
152; CHECK-NEXT:     [[COND2:%[^ ]+]] = icmp ugt i32 -2147483648, %exit.preloop.at
153; CHECK-NEXT:     br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit
154; CHECK:        mainloop:
155; CHECK-NEXT:     br label %loop
156; CHECK:        loop:
157; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
158; CHECK-NEXT:     %idx.next = add i32 %idx, -1
159; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len
160; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
161; CHECK-NOT:    loop.postloop:
162; CHECK:        loop.preloop:
163; CHECK-NEXT:     %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ -2147483648, %loop.preloop.preheader ]
164; CHECK-NEXT:     %idx.next.preloop = add i32 %idx.preloop, -1
165; CHECK-NEXT:     %abc.preloop = icmp ult i32 %idx.preloop, %len
166; CHECK-NEXT:     br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
167
168entry:
169  %len = load i32, i32* %a_len_ptr, !range !0
170  br label %loop
171
172loop:
173  %idx = phi i32 [ 2147483648, %entry ], [ %idx.next, %in.bounds ]
174  %idx.next = add i32 %idx, -1
175  %abc = icmp ult i32 %idx, %len
176  br i1 %abc, label %in.bounds, label %out.of.bounds
177
178in.bounds:
179  %addr = getelementptr i32, i32* %arr, i32 %idx
180  store i32 0, i32* %addr
181  %next = icmp ugt i32 %idx.next, 0
182  br i1 %next, label %loop, label %exit
183
184out.of.bounds:
185  ret void
186
187exit:
188  ret void
189}
190
191; Increasing loop, UINT_MAX. Negative test: we cannot add 1 to UINT_MAX.
192define void @test_05(i32* %arr, i32* %a_len_ptr) #0 {
193
194; CHECK: test_05(
195; CHECK-NOT:    loop.preloop:
196; CHECK-NOT:    loop.postloop:
197
198entry:
199  %len = load i32, i32* %a_len_ptr, !range !0
200  br label %loop
201
202loop:
203  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
204  %idx.next = add nsw nuw i32 %idx, 1
205  %abc = icmp ult i32 %idx, %len
206  br i1 %abc, label %in.bounds, label %out.of.bounds
207
208in.bounds:
209  %addr = getelementptr i32, i32* %arr, i32 %idx
210  store i32 0, i32* %addr
211  %next = icmp ugt i32 %idx.next, 4294967295
212  br i1 %next, label %exit, label %loop
213
214out.of.bounds:
215  ret void
216
217exit:
218  ret void
219}
220
221; Decreasing loop, UINT_MAX. Positive test.
222define void @test_06(i32* %arr, i32* %a_len_ptr) #0 {
223
224; CHECK: test_06(
225; CHECK:        mainloop:
226; CHECK-NEXT:     br label %loop
227; CHECK:        loop:
228; CHECK-NEXT:     %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ]
229; CHECK-NEXT:     %idx.next = add nuw i32 %idx, -1
230; CHECK-NEXT:     %abc = icmp ult i32 %idx, %len
231; CHECK-NEXT:     br i1 true, label %in.bounds, label %out.of.bounds.loopexit1
232; CHECK-NOT:    loop.postloop:
233; CHECK:        loop.preloop:
234; CHECK-NEXT:     %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ -1, %loop.preloop.preheader ]
235; CHECK-NEXT:     %idx.next.preloop = add nuw i32 %idx.preloop, -1
236; CHECK-NEXT:     %abc.preloop = icmp ult i32 %idx.preloop, %len
237; CHECK-NEXT:     br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit
238
239entry:
240  %len = load i32, i32* %a_len_ptr, !range !0
241  br label %loop
242
243loop:
244  %idx = phi i32 [ 4294967295, %entry ], [ %idx.next, %in.bounds ]
245  %idx.next = add nuw i32 %idx, -1
246  %abc = icmp ult i32 %idx, %len
247  br i1 %abc, label %in.bounds, label %out.of.bounds
248
249in.bounds:
250  %addr = getelementptr i32, i32* %arr, i32 %idx
251  store i32 0, i32* %addr
252  %next = icmp ugt i32 %idx.next, 0
253  br i1 %next, label %loop, label %exit
254
255out.of.bounds:
256  ret void
257
258exit:
259  ret void
260}
261
262!0 = !{i32 0, i32 50}
263