1; RUN: opt -verify-loop-info -irce-print-changed-loops -irce < %s 2>&1 | FileCheck %s
2; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,loop(irce)' < %s 2>&1 | FileCheck %s
3
4; This test checks if we update the LoopInfo correctly in the presence
5; of parents, uncles and cousins.
6
7; Function Attrs: alwaysinline
8define void @inner_loop(i32* %arr, i32* %a_len_ptr, i32 %n) #0 {
9; CHECK: irce: in function inner_loop: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
10
11entry:
12  %len = load i32, i32* %a_len_ptr, !range !0
13  %first.itr.check = icmp sgt i32 %n, 0
14  br i1 %first.itr.check, label %loop, label %exit
15
16loop:                                             ; preds = %in.bounds, %entry
17  %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
18  %idx.next = add i32 %idx, 1
19  %abc = icmp slt i32 %idx, %len
20  br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1
21
22in.bounds:                                        ; preds = %loop
23  %addr = getelementptr i32, i32* %arr, i32 %idx
24  store i32 0, i32* %addr
25  %next = icmp slt i32 %idx.next, %n
26  br i1 %next, label %loop, label %exit
27
28out.of.bounds:                                    ; preds = %loop
29  ret void
30
31exit:                                             ; preds = %in.bounds, %entry
32  ret void
33}
34
35; Function Attrs: alwaysinline
36define void @with_parent(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count) #0 {
37; CHECK: irce: in function with_parent: constrained Loop at depth 2 containing: %loop.i<header><exiting>,%in.bounds.i<latch><exiting>
38
39entry:
40  br label %loop
41
42loop:                                             ; preds = %inner_loop.exit, %entry
43  %idx = phi i32 [ 0, %entry ], [ %idx.next, %inner_loop.exit ]
44  %idx.next = add i32 %idx, 1
45  %next = icmp ult i32 %idx.next, %parent.count
46  %len.i = load i32, i32* %a_len_ptr, !range !0
47  %first.itr.check.i = icmp sgt i32 %n, 0
48  br i1 %first.itr.check.i, label %loop.i, label %exit.i
49
50loop.i:                                           ; preds = %in.bounds.i, %loop
51  %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %in.bounds.i ]
52  %idx.next.i = add i32 %idx.i, 1
53  %abc.i = icmp slt i32 %idx.i, %len.i
54  br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i, !prof !1
55
56in.bounds.i:                                      ; preds = %loop.i
57  %addr.i = getelementptr i32, i32* %arr, i32 %idx.i
58  store i32 0, i32* %addr.i
59  %next.i = icmp slt i32 %idx.next.i, %n
60  br i1 %next.i, label %loop.i, label %exit.i
61
62out.of.bounds.i:                                  ; preds = %loop.i
63  br label %inner_loop.exit
64
65exit.i:                                           ; preds = %in.bounds.i, %loop
66  br label %inner_loop.exit
67
68inner_loop.exit:                                  ; preds = %exit.i, %out.of.bounds.i
69  br i1 %next, label %loop, label %exit
70
71exit:                                             ; preds = %inner_loop.exit
72  ret void
73}
74
75; Function Attrs: alwaysinline
76define void @with_grandparent(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count, i32 %grandparent.count) #0 {
77; CHECK: irce: in function with_grandparent: constrained Loop at depth 3 containing: %loop.i.i<header><exiting>,%in.bounds.i.i<latch><exiting>
78
79entry:
80  br label %loop
81
82loop:                                             ; preds = %with_parent.exit, %entry
83  %idx = phi i32 [ 0, %entry ], [ %idx.next, %with_parent.exit ]
84  %idx.next = add i32 %idx, 1
85  %next = icmp ult i32 %idx.next, %grandparent.count
86  br label %loop.i
87
88loop.i:                                           ; preds = %inner_loop.exit.i, %loop
89  %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %inner_loop.exit.i ]
90  %idx.next.i = add i32 %idx.i, 1
91  %next.i = icmp ult i32 %idx.next.i, %parent.count
92  %len.i.i = load i32, i32* %a_len_ptr, !range !0
93  %first.itr.check.i.i = icmp sgt i32 %n, 0
94  br i1 %first.itr.check.i.i, label %loop.i.i, label %exit.i.i
95
96loop.i.i:                                         ; preds = %in.bounds.i.i, %loop.i
97  %idx.i.i = phi i32 [ 0, %loop.i ], [ %idx.next.i.i, %in.bounds.i.i ]
98  %idx.next.i.i = add i32 %idx.i.i, 1
99  %abc.i.i = icmp slt i32 %idx.i.i, %len.i.i
100  br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i, !prof !1
101
102in.bounds.i.i:                                    ; preds = %loop.i.i
103  %addr.i.i = getelementptr i32, i32* %arr, i32 %idx.i.i
104  store i32 0, i32* %addr.i.i
105  %next.i.i = icmp slt i32 %idx.next.i.i, %n
106  br i1 %next.i.i, label %loop.i.i, label %exit.i.i
107
108out.of.bounds.i.i:                                ; preds = %loop.i.i
109  br label %inner_loop.exit.i
110
111exit.i.i:                                         ; preds = %in.bounds.i.i, %loop.i
112  br label %inner_loop.exit.i
113
114inner_loop.exit.i:                                ; preds = %exit.i.i, %out.of.bounds.i.i
115  br i1 %next.i, label %loop.i, label %with_parent.exit
116
117with_parent.exit:                                 ; preds = %inner_loop.exit.i
118  br i1 %next, label %loop, label %exit
119
120exit:                                             ; preds = %with_parent.exit
121  ret void
122}
123
124; Function Attrs: alwaysinline
125define void @with_sibling(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count) #0 {
126; CHECK: irce: in function with_sibling: constrained Loop at depth 2 containing: %loop.i<header><exiting>,%in.bounds.i<latch><exiting>
127; CHECK: irce: in function with_sibling: constrained Loop at depth 2 containing: %loop.i6<header><exiting>,%in.bounds.i9<latch><exiting>
128
129entry:
130  br label %loop
131
132loop:                                             ; preds = %inner_loop.exit12, %entry
133  %idx = phi i32 [ 0, %entry ], [ %idx.next, %inner_loop.exit12 ]
134  %idx.next = add i32 %idx, 1
135  %next = icmp ult i32 %idx.next, %parent.count
136  %len.i = load i32, i32* %a_len_ptr, !range !0
137  %first.itr.check.i = icmp sgt i32 %n, 0
138  br i1 %first.itr.check.i, label %loop.i, label %exit.i
139
140loop.i:                                           ; preds = %in.bounds.i, %loop
141  %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %in.bounds.i ]
142  %idx.next.i = add i32 %idx.i, 1
143  %abc.i = icmp slt i32 %idx.i, %len.i
144  br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i, !prof !1
145
146in.bounds.i:                                      ; preds = %loop.i
147  %addr.i = getelementptr i32, i32* %arr, i32 %idx.i
148  store i32 0, i32* %addr.i
149  %next.i = icmp slt i32 %idx.next.i, %n
150  br i1 %next.i, label %loop.i, label %exit.i
151
152out.of.bounds.i:                                  ; preds = %loop.i
153  br label %inner_loop.exit
154
155exit.i:                                           ; preds = %in.bounds.i, %loop
156  br label %inner_loop.exit
157
158inner_loop.exit:                                  ; preds = %exit.i, %out.of.bounds.i
159  %len.i1 = load i32, i32* %a_len_ptr, !range !0
160  %first.itr.check.i2 = icmp sgt i32 %n, 0
161  br i1 %first.itr.check.i2, label %loop.i6, label %exit.i11
162
163loop.i6:                                          ; preds = %in.bounds.i9, %inner_loop.exit
164  %idx.i3 = phi i32 [ 0, %inner_loop.exit ], [ %idx.next.i4, %in.bounds.i9 ]
165  %idx.next.i4 = add i32 %idx.i3, 1
166  %abc.i5 = icmp slt i32 %idx.i3, %len.i1
167  br i1 %abc.i5, label %in.bounds.i9, label %out.of.bounds.i10, !prof !1
168
169in.bounds.i9:                                     ; preds = %loop.i6
170  %addr.i7 = getelementptr i32, i32* %arr, i32 %idx.i3
171  store i32 0, i32* %addr.i7
172  %next.i8 = icmp slt i32 %idx.next.i4, %n
173  br i1 %next.i8, label %loop.i6, label %exit.i11
174
175out.of.bounds.i10:                                ; preds = %loop.i6
176  br label %inner_loop.exit12
177
178exit.i11:                                         ; preds = %in.bounds.i9, %inner_loop.exit
179  br label %inner_loop.exit12
180
181inner_loop.exit12:                                ; preds = %exit.i11, %out.of.bounds.i10
182  br i1 %next, label %loop, label %exit
183
184exit:                                             ; preds = %inner_loop.exit12
185  ret void
186}
187
188; Function Attrs: alwaysinline
189define void @with_cousin(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count, i32 %grandparent.count) #0 {
190; CHECK: irce: in function with_cousin: constrained Loop at depth 3 containing: %loop.i.i<header><exiting>,%in.bounds.i.i<latch><exiting>
191; CHECK: irce: in function with_cousin: constrained Loop at depth 3 containing: %loop.i.i10<header><exiting>,%in.bounds.i.i13<latch><exiting>
192
193entry:
194  br label %loop
195
196loop:                                             ; preds = %with_parent.exit17, %entry
197  %idx = phi i32 [ 0, %entry ], [ %idx.next, %with_parent.exit17 ]
198  %idx.next = add i32 %idx, 1
199  %next = icmp ult i32 %idx.next, %grandparent.count
200  br label %loop.i
201
202loop.i:                                           ; preds = %inner_loop.exit.i, %loop
203  %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %inner_loop.exit.i ]
204  %idx.next.i = add i32 %idx.i, 1
205  %next.i = icmp ult i32 %idx.next.i, %parent.count
206  %len.i.i = load i32, i32* %a_len_ptr, !range !0
207  %first.itr.check.i.i = icmp sgt i32 %n, 0
208  br i1 %first.itr.check.i.i, label %loop.i.i, label %exit.i.i
209
210loop.i.i:                                         ; preds = %in.bounds.i.i, %loop.i
211  %idx.i.i = phi i32 [ 0, %loop.i ], [ %idx.next.i.i, %in.bounds.i.i ]
212  %idx.next.i.i = add i32 %idx.i.i, 1
213  %abc.i.i = icmp slt i32 %idx.i.i, %len.i.i
214  br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i, !prof !1
215
216in.bounds.i.i:                                    ; preds = %loop.i.i
217  %addr.i.i = getelementptr i32, i32* %arr, i32 %idx.i.i
218  store i32 0, i32* %addr.i.i
219  %next.i.i = icmp slt i32 %idx.next.i.i, %n
220  br i1 %next.i.i, label %loop.i.i, label %exit.i.i
221
222out.of.bounds.i.i:                                ; preds = %loop.i.i
223  br label %inner_loop.exit.i
224
225exit.i.i:                                         ; preds = %in.bounds.i.i, %loop.i
226  br label %inner_loop.exit.i
227
228inner_loop.exit.i:                                ; preds = %exit.i.i, %out.of.bounds.i.i
229  br i1 %next.i, label %loop.i, label %with_parent.exit
230
231with_parent.exit:                                 ; preds = %inner_loop.exit.i
232  br label %loop.i6
233
234loop.i6:                                          ; preds = %inner_loop.exit.i16, %with_parent.exit
235  %idx.i1 = phi i32 [ 0, %with_parent.exit ], [ %idx.next.i2, %inner_loop.exit.i16 ]
236  %idx.next.i2 = add i32 %idx.i1, 1
237  %next.i3 = icmp ult i32 %idx.next.i2, %parent.count
238  %len.i.i4 = load i32, i32* %a_len_ptr, !range !0
239  %first.itr.check.i.i5 = icmp sgt i32 %n, 0
240  br i1 %first.itr.check.i.i5, label %loop.i.i10, label %exit.i.i15
241
242loop.i.i10:                                       ; preds = %in.bounds.i.i13, %loop.i6
243  %idx.i.i7 = phi i32 [ 0, %loop.i6 ], [ %idx.next.i.i8, %in.bounds.i.i13 ]
244  %idx.next.i.i8 = add i32 %idx.i.i7, 1
245  %abc.i.i9 = icmp slt i32 %idx.i.i7, %len.i.i4
246  br i1 %abc.i.i9, label %in.bounds.i.i13, label %out.of.bounds.i.i14, !prof !1
247
248in.bounds.i.i13:                                  ; preds = %loop.i.i10
249  %addr.i.i11 = getelementptr i32, i32* %arr, i32 %idx.i.i7
250  store i32 0, i32* %addr.i.i11
251  %next.i.i12 = icmp slt i32 %idx.next.i.i8, %n
252  br i1 %next.i.i12, label %loop.i.i10, label %exit.i.i15
253
254out.of.bounds.i.i14:                              ; preds = %loop.i.i10
255  br label %inner_loop.exit.i16
256
257exit.i.i15:                                       ; preds = %in.bounds.i.i13, %loop.i6
258  br label %inner_loop.exit.i16
259
260inner_loop.exit.i16:                              ; preds = %exit.i.i15, %out.of.bounds.i.i14
261  br i1 %next.i3, label %loop.i6, label %with_parent.exit17
262
263with_parent.exit17:                               ; preds = %inner_loop.exit.i16
264  br i1 %next, label %loop, label %exit
265
266exit:                                             ; preds = %with_parent.exit17
267  ret void
268}
269
270; Function Attrs: alwaysinline
271define void @with_uncle(i32* %arr, i32* %a_len_ptr, i32 %n, i32 %parent.count, i32 %grandparent.count) #0 {
272; CHECK: irce: in function with_uncle: constrained Loop at depth 2 containing: %loop.i<header><exiting>,%in.bounds.i<latch><exiting>
273; CHECK: irce: in function with_uncle: constrained Loop at depth 3 containing: %loop.i.i<header><exiting>,%in.bounds.i.i<latch><exiting>
274
275entry:
276  br label %loop
277
278loop:                                             ; preds = %with_parent.exit, %entry
279  %idx = phi i32 [ 0, %entry ], [ %idx.next, %with_parent.exit ]
280  %idx.next = add i32 %idx, 1
281  %next = icmp ult i32 %idx.next, %grandparent.count
282  %len.i = load i32, i32* %a_len_ptr, !range !0
283  %first.itr.check.i = icmp sgt i32 %n, 0
284  br i1 %first.itr.check.i, label %loop.i, label %exit.i
285
286loop.i:                                           ; preds = %in.bounds.i, %loop
287  %idx.i = phi i32 [ 0, %loop ], [ %idx.next.i, %in.bounds.i ]
288  %idx.next.i = add i32 %idx.i, 1
289  %abc.i = icmp slt i32 %idx.i, %len.i
290  br i1 %abc.i, label %in.bounds.i, label %out.of.bounds.i, !prof !1
291
292in.bounds.i:                                      ; preds = %loop.i
293  %addr.i = getelementptr i32, i32* %arr, i32 %idx.i
294  store i32 0, i32* %addr.i
295  %next.i = icmp slt i32 %idx.next.i, %n
296  br i1 %next.i, label %loop.i, label %exit.i
297
298out.of.bounds.i:                                  ; preds = %loop.i
299  br label %inner_loop.exit
300
301exit.i:                                           ; preds = %in.bounds.i, %loop
302  br label %inner_loop.exit
303
304inner_loop.exit:                                  ; preds = %exit.i, %out.of.bounds.i
305  br label %loop.i4
306
307loop.i4:                                          ; preds = %inner_loop.exit.i, %inner_loop.exit
308  %idx.i1 = phi i32 [ 0, %inner_loop.exit ], [ %idx.next.i2, %inner_loop.exit.i ]
309  %idx.next.i2 = add i32 %idx.i1, 1
310  %next.i3 = icmp ult i32 %idx.next.i2, %parent.count
311  %len.i.i = load i32, i32* %a_len_ptr, !range !0
312  %first.itr.check.i.i = icmp sgt i32 %n, 0
313  br i1 %first.itr.check.i.i, label %loop.i.i, label %exit.i.i
314
315loop.i.i:                                         ; preds = %in.bounds.i.i, %loop.i4
316  %idx.i.i = phi i32 [ 0, %loop.i4 ], [ %idx.next.i.i, %in.bounds.i.i ]
317  %idx.next.i.i = add i32 %idx.i.i, 1
318  %abc.i.i = icmp slt i32 %idx.i.i, %len.i.i
319  br i1 %abc.i.i, label %in.bounds.i.i, label %out.of.bounds.i.i, !prof !1
320
321in.bounds.i.i:                                    ; preds = %loop.i.i
322  %addr.i.i = getelementptr i32, i32* %arr, i32 %idx.i.i
323  store i32 0, i32* %addr.i.i
324  %next.i.i = icmp slt i32 %idx.next.i.i, %n
325  br i1 %next.i.i, label %loop.i.i, label %exit.i.i
326
327out.of.bounds.i.i:                                ; preds = %loop.i.i
328  br label %inner_loop.exit.i
329
330exit.i.i:                                         ; preds = %in.bounds.i.i, %loop.i4
331  br label %inner_loop.exit.i
332
333inner_loop.exit.i:                                ; preds = %exit.i.i, %out.of.bounds.i.i
334  br i1 %next.i3, label %loop.i4, label %with_parent.exit
335
336with_parent.exit:                                 ; preds = %inner_loop.exit.i
337  br i1 %next, label %loop, label %exit
338
339exit:                                             ; preds = %with_parent.exit
340  ret void
341}
342
343attributes #0 = { alwaysinline }
344
345!0 = !{i32 0, i32 2147483647}
346!1 = !{!"branch_weights", i32 64, i32 4}
347