1; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
2
3; CHECK-LABEL: irce: in function test_01: constrained Loop at depth 1 containing:
4; CHECK-LABEL: irce: in function test_02: constrained Loop at depth 1 containing:
5; CHECK-NOT: irce: in function test_03: constrained Loop
6; CHECK-NOT: irce: in function test_04: constrained Loop
7; CHECK-LABEL: irce: in function test_05: constrained Loop at depth 1 containing:
8
9; This test used to demonstrate a miscompile: the outer loop's IV iterates in
10; range of [2, 400) and the range check is done against value 331. Due to a bug
11; in range intersection IRCE manages to eliminate the range check without
12; inserting a postloop, which is incorrect. We treat the range of this test as
13; an unsigned range and are able to intersect ranges correctly and insert a
14; postloop.
15
16define void @test_01() {
17
18; CHECK-LABEL: test_01
19; CHECK-NOT:     preloop
20; CHECK:         range_check_block:                                ; preds = %inner_loop
21; CHECK-NEXT:      %range_check = icmp slt i32 %iv, 331
22; CHECK-NEXT:      br i1 true, label %loop_latch
23; CHECK:         loop_latch:
24; CHECK-NEXT:      %iv_next = add i32 %iv, 1
25; CHECK-NEXT:      %loop_cond = icmp ult i32 %iv_next, 400
26; CHECK-NEXT:      [[COND:%[^ ]+]] = icmp ult i32 %iv_next, 331
27; CHECK-NEXT:      br i1 [[COND]], label %loop_header, label %main.exit.selector
28; CHECK:         main.exit.selector:                               ; preds = %loop_latch
29; CHECK-NEXT:      %iv_next.lcssa = phi i32 [ %iv_next, %loop_latch ]
30; CHECK-NEXT:      %iv.lcssa = phi i32 [ %iv, %loop_latch ]
31; CHECK-NEXT:      [[MES_COND:%[^ ]+]] = icmp ult i32 %iv_next.lcssa, 400
32; CHECK-NEXT:      br i1 [[MES_COND]], label %main.pseudo.exit, label %exit
33; CHECK:         loop_latch.postloop:                              ; preds = %range_check_block.postloop
34; CHECK-NEXT:      %iv_next.postloop = add i32 %iv.postloop, 1
35; CHECK-NEXT:      %loop_cond.postloop = icmp ult i32 %iv_next.postloop, 400
36; CHECK-NEXT:      br i1 %loop_cond.postloop, label %loop_header.postloop, label %exit.loopexit
37
38entry:
39  br label %loop_header
40
41loop_header:                            ; preds = %loop_latch, %entry
42  %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
43  %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
44  %tmp2 = icmp sgt i32 %iv.prev, -1
45  br i1 %tmp2, label %loop_header.split.us, label %exit
46
47loop_header.split.us:                   ; preds = %loop_header
48  br label %inner_loop
49
50inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
51  %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
52  %inner_iv_next = add nuw nsw i32 %inner_iv, 1
53  %inner_cond = icmp ult i32 %inner_iv_next, 31
54  br i1 %inner_cond, label %inner_loop, label %range_check_block
55
56exit:                                            ; preds = %loop_latch, %loop_header
57  ret void
58
59range_check_block:                                          ; preds = %inner_loop
60  %range_check = icmp slt i32 %iv, 331
61  br i1 %range_check, label %loop_latch, label %deopt
62
63loop_latch:                                         ; preds = %range_check_block
64  %iv_next = add i32 %iv, 1
65  %loop_cond = icmp ult i32 %iv_next, 400
66  br i1 %loop_cond, label %loop_header, label %exit
67
68deopt:                                          ; preds = %range_check_block
69  ret void
70}
71
72; Similar to test_01, but here the range check is done against 450. No postloop
73; is required.
74
75define void @test_02() {
76
77; CHECK-LABEL: test_02
78; CHECK-NOT:     preloop
79; CHECK-NOT:     postloop
80; CHECK:         range_check_block:                                ; preds = %inner_loop
81; CHECK-NEXT:      %range_check = icmp slt i32 %iv, 450
82; CHECK-NEXT:      br i1 true, label %loop_latch
83; CHECK:         loop_latch:                                       ; preds = %range_check_block
84; CHECK-NEXT:      %iv_next = add i32 %iv, 1
85; CHECK-NEXT:      %loop_cond = icmp ult i32 %iv_next, 400
86; CHECK-NEXT:      br i1 %loop_cond, label %loop_header, label %exit
87
88entry:
89  br label %loop_header
90
91loop_header:                            ; preds = %loop_latch, %entry
92  %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
93  %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
94  %tmp2 = icmp sgt i32 %iv.prev, -1
95  br i1 %tmp2, label %loop_header.split.us, label %exit
96
97loop_header.split.us:                   ; preds = %loop_header
98  br label %inner_loop
99
100inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
101  %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
102  %inner_iv_next = add nuw nsw i32 %inner_iv, 1
103  %inner_cond = icmp ult i32 %inner_iv_next, 31
104  br i1 %inner_cond, label %inner_loop, label %range_check_block
105
106exit:                                            ; preds = %loop_latch, %loop_header
107  ret void
108
109range_check_block:                                          ; preds = %inner_loop
110  %range_check = icmp slt i32 %iv, 450
111  br i1 %range_check, label %loop_latch, label %deopt
112
113loop_latch:                                         ; preds = %range_check_block
114  %iv_next = add i32 %iv, 1
115  %loop_cond = icmp ult i32 %iv_next, 400
116  br i1 %loop_cond, label %loop_header, label %exit
117
118deopt:                                          ; preds = %range_check_block
119  ret void
120}
121
122; Range check is made against 0, so the safe iteration range is empty. IRCE
123; should not apply.
124
125define void @test_03() {
126
127; CHECK-LABEL: test_03
128
129entry:
130  br label %loop_header
131
132loop_header:                            ; preds = %loop_latch, %entry
133  %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
134  %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
135  %tmp2 = icmp sgt i32 %iv.prev, -1
136  br i1 %tmp2, label %loop_header.split.us, label %exit
137
138loop_header.split.us:                   ; preds = %loop_header
139  br label %inner_loop
140
141inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
142  %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
143  %inner_iv_next = add nuw nsw i32 %inner_iv, 1
144  %inner_cond = icmp ult i32 %inner_iv_next, 31
145  br i1 %inner_cond, label %inner_loop, label %range_check_block
146
147exit:                                            ; preds = %loop_latch, %loop_header
148  ret void
149
150range_check_block:                                          ; preds = %inner_loop
151  %range_check = icmp slt i32 %iv, 0
152  br i1 %range_check, label %loop_latch, label %deopt
153
154loop_latch:                                         ; preds = %range_check_block
155  %iv_next = add i32 %iv, 1
156  %loop_cond = icmp ult i32 %iv_next, 400
157  br i1 %loop_cond, label %loop_header, label %exit
158
159deopt:                                          ; preds = %range_check_block
160  ret void
161}
162
163; We do not know whether %n is positive or negative, so we prohibit IRCE in
164; order to avoid incorrect intersection of signed and unsigned ranges.
165
166define void @test_04(i32* %p) {
167
168; CHECK-LABEL: test_04
169
170entry:
171  %n = load i32, i32* %p
172  br label %loop_header
173
174loop_header:                            ; preds = %loop_latch, %entry
175  %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
176  %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
177  %tmp2 = icmp sgt i32 %iv.prev, -1
178  br i1 %tmp2, label %loop_header.split.us, label %exit
179
180loop_header.split.us:                   ; preds = %loop_header
181  br label %inner_loop
182
183inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
184  %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
185  %inner_iv_next = add nuw nsw i32 %inner_iv, 1
186  %inner_cond = icmp ult i32 %inner_iv_next, 31
187  br i1 %inner_cond, label %inner_loop, label %range_check_block
188
189exit:                                            ; preds = %loop_latch, %loop_header
190  ret void
191
192range_check_block:                                          ; preds = %inner_loop
193  %range_check = icmp slt i32 %iv, %n
194  br i1 %range_check, label %loop_latch, label %deopt
195
196loop_latch:                                         ; preds = %range_check_block
197  %iv_next = add i32 %iv, 1
198  %loop_cond = icmp ult i32 %iv_next, 400
199  br i1 %loop_cond, label %loop_header, label %exit
200
201deopt:                                          ; preds = %range_check_block
202  ret void
203}
204
205; Same as test_04, but range guarantees that %n is positive. So we can safely
206; intersect ranges (with insertion of postloop).
207
208define void @test_05(i32* %p) {
209
210; CHECK-LABEL: test_05
211; CHECK-NOT:     preloop
212; CHECK:         entry:
213; CHECK-NEXT:      %n = load i32, i32* %p, !range !6
214; CHECK-NEXT:      [[CMP_1:%[^ ]+]] = icmp ugt i32 %n, 2
215; CHECK-NEXT:      %exit.mainloop.at = select i1 [[CMP_1]], i32 %n, i32 2
216; CHECK-NEXT:      [[CMP_2:%[^ ]+]] = icmp ult i32 2, %exit.mainloop.at
217; CHECK-NEXT:      br i1 [[CMP_2]], label %loop_header.preheader, label %main.pseudo.exit
218; CHECK:         range_check_block:                                ; preds = %inner_loop
219; CHECK-NEXT:      %range_check = icmp slt i32 %iv, %n
220; CHECK-NEXT:      br i1 true, label %loop_latch, label %deopt.loopexit2
221; CHECK:         loop_latch:                                       ; preds = %range_check_block
222; CHECK-NEXT:      %iv_next = add i32 %iv, 1
223; CHECK-NEXT:      %loop_cond = icmp ult i32 %iv_next, 400
224; CHECK-NEXT:      [[COND:%[^ ]+]] = icmp ult i32 %iv_next, %exit.mainloop.at
225; CHECK-NEXT:      br i1 [[COND]], label %loop_header, label %main.exit.selector
226; CHECK:         main.exit.selector:                               ; preds = %loop_latch
227; CHECK-NEXT:      %iv_next.lcssa = phi i32 [ %iv_next, %loop_latch ]
228; CHECK-NEXT:      %iv.lcssa = phi i32 [ %iv, %loop_latch ]
229; CHECK-NEXT:      [[MES_COND:%[^ ]+]] = icmp ult i32 %iv_next.lcssa, 400
230; CHECK-NEXT:      br i1 [[MES_COND]], label %main.pseudo.exit, label %exit
231; CHECK:         loop_latch.postloop:                              ; preds = %range_check_block.postloop
232; CHECK-NEXT:      %iv_next.postloop = add i32 %iv.postloop, 1
233; CHECK-NEXT:      %loop_cond.postloop = icmp ult i32 %iv_next.postloop, 400
234; CHECK-NEXT:      br i1 %loop_cond.postloop, label %loop_header.postloop, label %exit.loopexit
235
236entry:
237  %n = load i32, i32* %p, !range !0
238  br label %loop_header
239
240loop_header:                            ; preds = %loop_latch, %entry
241  %iv = phi i32 [ 2, %entry ], [ %iv_next, %loop_latch ]
242  %iv.prev = phi i32 [ 1, %entry ], [ %iv, %loop_latch ]
243  %tmp2 = icmp sgt i32 %iv.prev, -1
244  br i1 %tmp2, label %loop_header.split.us, label %exit
245
246loop_header.split.us:                   ; preds = %loop_header
247  br label %inner_loop
248
249inner_loop:                                   ; preds = %inner_loop, %loop_header.split.us
250  %inner_iv = phi i32 [ 1, %loop_header.split.us ], [ %inner_iv_next, %inner_loop ]
251  %inner_iv_next = add nuw nsw i32 %inner_iv, 1
252  %inner_cond = icmp ult i32 %inner_iv_next, 31
253  br i1 %inner_cond, label %inner_loop, label %range_check_block
254
255exit:                                            ; preds = %loop_latch, %loop_header
256  ret void
257
258range_check_block:                                          ; preds = %inner_loop
259  %range_check = icmp slt i32 %iv, %n
260  br i1 %range_check, label %loop_latch, label %deopt
261
262loop_latch:                                         ; preds = %range_check_block
263  %iv_next = add i32 %iv, 1
264  %loop_cond = icmp ult i32 %iv_next, 400
265  br i1 %loop_cond, label %loop_header, label %exit
266
267deopt:                                          ; preds = %range_check_block
268  ret void
269}
270
271!0 = !{i32 0, i32 50}
272