1; RUN: opt -verify-loop-info -irce -S < %s | FileCheck %s
2; RUN: opt -verify-loop-info -passes='require<branch-prob>,irce' -S < %s | FileCheck %s
3
4define void @decrementing_loop(i32 *%arr, i32 *%a_len_ptr, i32 %n) {
5 entry:
6  %len = load i32, i32* %a_len_ptr, !range !0
7  %first.itr.check = icmp sgt i32 %n, 0
8  %start = sub i32 %n, 1
9  br i1 %first.itr.check, label %loop, label %exit
10
11 loop:
12  %idx = phi i32 [ %start, %entry ] , [ %idx.dec, %in.bounds ]
13  %idx.dec = sub i32 %idx, 1
14  %abc.high = icmp slt i32 %idx, %len
15  %abc.low = icmp sge i32 %idx, 0
16  %abc = and i1 %abc.low, %abc.high
17  br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
18
19 in.bounds:
20  %addr = getelementptr i32, i32* %arr, i32 %idx
21  store i32 0, i32* %addr
22  %next = icmp sgt i32 %idx.dec, -1
23  br i1 %next, label %loop, label %exit
24
25 out.of.bounds:
26  ret void
27
28 exit:
29  ret void
30
31; CHECK: loop.preheader:
32; CHECK:   [[len_hiclamp_cmp:[^ ]+]] = icmp slt i32 %len, %n
33; CHECK:   [[len_hiclamp:[^ ]+]] = select i1 [[len_hiclamp_cmp]], i32 %len, i32 %n
34; CHECK:   [[not_exit_preloop_at_cmp:[^ ]+]] = icmp sgt i32 [[len_hiclamp]], 0
35; CHECK:   [[not_exit_preloop_at:[^ ]+]] = select i1 [[not_exit_preloop_at_cmp]], i32 [[len_hiclamp]], i32 0
36; CHECK:   %exit.preloop.at = add nsw i32 [[not_exit_preloop_at]], -1
37}
38
39; Make sure that we can eliminate the range check when the loop looks like:
40; for (i = len.a - 1; i >= 0; --i)
41;   b[i] = a[i];
42define void @test_01(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {
43
44; CHECK-LABEL: test_01
45; CHECK:       mainloop:
46; CHECK-NEXT:    br label %loop
47; CHECK:       loop:
48; CHECK:         %rc = and i1 true, true
49; CHECK:       loop.preloop:
50
51 entry:
52  %len.a = load i32, i32* %a_len_ptr, !range !0
53  %len.b = load i32, i32* %b_len_ptr, !range !0
54  %first.itr.check = icmp ne i32 %len.a, 0
55  br i1 %first.itr.check, label %loop, label %exit
56
57 loop:
58  %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]
59  %idx.next = sub i32 %idx, 1
60  %rca = icmp ult i32 %idx.next, %len.a
61  %rcb = icmp ult i32 %idx.next, %len.b
62  %rc = and i1 %rca, %rcb
63  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
64
65 in.bounds:
66  %el.a = getelementptr i32, i32* %a, i32 %idx.next
67  %el.b = getelementptr i32, i32* %b, i32 %idx.next
68  %v = load i32, i32* %el.a
69  store i32 %v, i32* %el.b
70  %loop.cond = icmp slt i32 %idx, 2
71  br i1 %loop.cond, label %exit, label %loop
72
73 out.of.bounds:
74  ret void
75
76 exit:
77  ret void
78}
79
80; Same as test_01, but the latch condition is unsigned
81define void @test_02(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {
82
83; CHECK-LABEL: test_02
84; CHECK:       mainloop:
85; CHECK-NEXT:    br label %loop
86; CHECK:       loop:
87; CHECK:         %rc = and i1 true, true
88; CHECK:       loop.preloop:
89
90 entry:
91  %len.a = load i32, i32* %a_len_ptr, !range !0
92  %len.b = load i32, i32* %b_len_ptr, !range !0
93  %first.itr.check = icmp ne i32 %len.a, 0
94  br i1 %first.itr.check, label %loop, label %exit
95
96 loop:
97  %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]
98  %idx.next = sub i32 %idx, 1
99  %rca = icmp ult i32 %idx.next, %len.a
100  %rcb = icmp ult i32 %idx.next, %len.b
101  %rc = and i1 %rca, %rcb
102  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
103
104 in.bounds:
105  %el.a = getelementptr i32, i32* %a, i32 %idx.next
106  %el.b = getelementptr i32, i32* %b, i32 %idx.next
107  %v = load i32, i32* %el.a
108  store i32 %v, i32* %el.b
109  %loop.cond = icmp ult i32 %idx, 2
110  br i1 %loop.cond, label %exit, label %loop
111
112 out.of.bounds:
113  ret void
114
115 exit:
116  ret void
117}
118
119; Check that we can figure out that IV is non-negative via implication through
120; Phi node.
121define void @test_03(i32* %a, i32* %a_len_ptr, i1 %cond) {
122
123; CHECK-LABEL: test_03
124; CHECK:       mainloop:
125; CHECK-NEXT:    br label %loop
126; CHECK:       loop:
127; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
128; CHECK:       loop.preloop:
129
130 entry:
131  %len.a = load i32, i32* %a_len_ptr, !range !0
132  %len.minus.one = sub nsw i32 %len.a, 1
133  %len.minus.two = sub nsw i32 %len.a, 2
134  br i1 %cond, label %if.true, label %if.false
135
136if.true:
137  br label %merge
138
139if.false:
140  br label %merge
141
142merge:
143  %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
144  %first.itr.check = icmp sgt i32 %len.a, 3
145  br i1 %first.itr.check, label %loop, label %exit
146
147loop:
148  %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
149  %idx.next = sub i32 %idx, 1
150  %rc = icmp ult i32 %idx.next, %len.a
151  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
152
153in.bounds:
154  %el.a = getelementptr i32, i32* %a, i32 %idx.next
155  %v = load i32, i32* %el.a
156  %loop.cond = icmp slt i32 %idx, 2
157  br i1 %loop.cond, label %exit, label %loop
158
159out.of.bounds:
160  ret void
161
162exit:
163  ret void
164}
165
166; Check that we can figure out that IV is non-negative via implication through
167; two Phi nodes.
168define void @test_04(i32* %a, i32* %a_len_ptr, i1 %cond) {
169
170; CHECK-LABEL: test_04
171; CHECK:       mainloop:
172; CHECK-NEXT:    br label %loop
173; CHECK:       loop:
174; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
175; CHECK:       loop.preloop:
176
177 entry:
178  %len.a = load i32, i32* %a_len_ptr, !range !0
179  %len.minus.one = sub nsw i32 %len.a, 1
180  %len.plus.one = add nsw i32 %len.a, 1
181  %len.minus.two = sub nsw i32 %len.a, 2
182  br i1 %cond, label %if.true, label %if.false
183
184if.true:
185  br label %merge
186
187if.false:
188  br label %merge
189
190merge:
191  %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
192  %len.phi = phi i32 [ %len.a, %if.true ], [ %len.plus.one, %if.false ]
193  %first.itr.check = icmp sgt i32 %len.a, 3
194  br i1 %first.itr.check, label %loop, label %exit
195
196loop:
197  %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
198  %idx.next = sub i32 %idx, 1
199  %rc = icmp ult i32 %idx.next, %len.phi
200  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
201
202in.bounds:
203  %el.a = getelementptr i32, i32* %a, i32 %idx.next
204  %v = load i32, i32* %el.a
205  %loop.cond = icmp slt i32 %idx, 2
206  br i1 %loop.cond, label %exit, label %loop
207
208out.of.bounds:
209  ret void
210
211exit:
212  ret void
213}
214
215; Check that we can figure out that IV is non-negative via implication through
216; two Phi nodes, one being AddRec.
217define void @test_05(i32* %a, i32* %a_len_ptr, i1 %cond) {
218
219; CHECK-LABEL: test_05
220; CHECK:       mainloop:
221; CHECK-NEXT:    br label %loop
222; CHECK:       loop:
223; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
224; CHECK:       loop.preloop:
225
226 entry:
227  %len.a = load i32, i32* %a_len_ptr, !range !0
228  %len.minus.one = sub nsw i32 %len.a, 1
229  %len.plus.one = add nsw i32 %len.a, 1
230  %len.minus.two = sub nsw i32 %len.a, 2
231  br label %merge
232
233merge:
234  %starting.value = phi i32 [ %len.minus.two, %entry ], [ %len.minus.one, %merge ]
235  %len.phi = phi i32 [ %len.a, %entry ], [ %len.phi.next, %merge ]
236  %len.phi.next = add nsw i32 %len.phi, 1
237  br i1 true, label %first.iter.check, label %merge
238
239first.iter.check:
240  %first.itr.check = icmp sgt i32 %len.a, 3
241  br i1 %first.itr.check, label %loop, label %exit
242
243loop:
244  %idx = phi i32 [ %starting.value, %first.iter.check ] , [ %idx.next, %in.bounds ]
245  %idx.next = sub i32 %idx, 1
246  %rc = icmp ult i32 %idx.next, %len.phi
247  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1
248
249in.bounds:
250  %el.a = getelementptr i32, i32* %a, i32 %idx.next
251  %v = load i32, i32* %el.a
252  %loop.cond = icmp slt i32 %idx, 2
253  br i1 %loop.cond, label %exit, label %loop
254
255out.of.bounds:
256  ret void
257
258exit:
259  ret void
260}
261
262!0 = !{i32 0, i32 2147483647}
263!1 = !{!"branch_weights", i32 64, i32 4}
264