1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
3
4target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
5
6declare void @use(ptr)
7declare i1 @cond()
8
9define void @test_monotonic_ptr_iv_inc_1_different_element_types_1_chain_of_2_exit_condition_unrelated_condition_in_header(ptr %start, i16 %len, i16 %x) {
10; CHECK-LABEL: @test_monotonic_ptr_iv_inc_1_different_element_types_1_chain_of_2_exit_condition_unrelated_condition_in_header(
11; CHECK-NEXT:  entry:
12; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[START:%.*]], i16 [[LEN:%.*]]
13; CHECK-NEXT:    [[LEN_NEG:%.*]] = icmp slt i16 [[LEN]], 0
14; CHECK-NEXT:    br i1 [[LEN_NEG]], label [[EXIT:%.*]], label [[LOOP_PH:%.*]]
15; CHECK:       loop.ph:
16; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
17; CHECK:       loop.header:
18; CHECK-NEXT:    [[PTR_IV:%.*]] = phi ptr [ [[START]], [[LOOP_PH]] ], [ [[PTR_IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
19; CHECK-NEXT:    [[C_0:%.*]] = icmp eq i16 [[X:%.*]], 1
20; CHECK-NEXT:    br i1 [[C_0]], label [[EXIT]], label [[THEN:%.*]]
21; CHECK:       then:
22; CHECK-NEXT:    [[C_1:%.*]] = icmp eq ptr [[PTR_IV]], [[UPPER]]
23; CHECK-NEXT:    br i1 [[C_1]], label [[EXIT]], label [[FOR_BODY:%.*]]
24; CHECK:       for.body:
25; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond()
26; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_NEXT:%.*]], label [[EXIT]]
27; CHECK:       loop.next:
28; CHECK-NEXT:    [[T_1:%.*]] = icmp uge ptr [[PTR_IV]], [[START]]
29; CHECK-NEXT:    [[T_2:%.*]] = icmp ult ptr [[PTR_IV]], [[UPPER]]
30; CHECK-NEXT:    [[AND:%.*]] = and i1 [[T_1]], [[T_2]]
31; CHECK-NEXT:    br i1 [[AND]], label [[LOOP_LATCH]], label [[EXIT]]
32; CHECK:       loop.latch:
33; CHECK-NEXT:    call void @use(ptr [[PTR_IV]])
34; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i8, ptr [[PTR_IV]], i16 1
35; CHECK-NEXT:    br label [[LOOP_HEADER]]
36; CHECK:       exit:
37; CHECK-NEXT:    ret void
38;
39entry:
40  %upper = getelementptr inbounds i32, ptr %start, i16 %len
41  %len.neg = icmp slt i16 %len, 0
42  br i1 %len.neg, label %exit, label %loop.ph
43
44loop.ph:
45  br label %loop.header
46
47loop.header:
48  %ptr.iv = phi ptr [ %start, %loop.ph ], [ %ptr.iv.next, %loop.latch ]
49  %c.0 = icmp eq i16 %x, 1
50  br i1 %c.0, label %exit, label %then
51
52then:
53  %c.1 = icmp eq ptr %ptr.iv, %upper
54  br i1 %c.1, label %exit, label %for.body
55
56for.body:
57  %c.2 = call i1 @cond()
58  br i1 %c.2, label %loop.next, label %exit
59
60loop.next:
61  %t.1 = icmp uge ptr %ptr.iv, %start
62  %t.2 = icmp ult ptr %ptr.iv, %upper
63  %and = and i1 %t.1, %t.2
64  br i1 %and, label %loop.latch, label %exit
65
66loop.latch:
67  call void @use(ptr %ptr.iv)
68  %ptr.iv.next = getelementptr inbounds i8, ptr %ptr.iv, i16 1
69  br label %loop.header
70
71exit:
72  ret void
73}
74
75define void @test_monotonic_ptr_iv_inc_1_different_element_types_1_chain_of_3_exit_condition_unrelated_condition_in_header(ptr %start, i16 %len, i16 %x) {
76; CHECK-LABEL: @test_monotonic_ptr_iv_inc_1_different_element_types_1_chain_of_3_exit_condition_unrelated_condition_in_header(
77; CHECK-NEXT:  entry:
78; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[START:%.*]], i16 [[LEN:%.*]]
79; CHECK-NEXT:    [[LEN_NEG:%.*]] = icmp slt i16 [[LEN]], 0
80; CHECK-NEXT:    br i1 [[LEN_NEG]], label [[EXIT:%.*]], label [[LOOP_PH:%.*]]
81; CHECK:       loop.ph:
82; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
83; CHECK:       loop.header:
84; CHECK-NEXT:    [[PTR_IV:%.*]] = phi ptr [ [[START]], [[LOOP_PH]] ], [ [[PTR_IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
85; CHECK-NEXT:    [[C_0:%.*]] = icmp eq i16 [[X:%.*]], 1
86; CHECK-NEXT:    br i1 [[C_0]], label [[EXIT]], label [[THEN_1:%.*]]
87; CHECK:       then.1:
88; CHECK-NEXT:    [[C_00:%.*]] = icmp ult i16 [[X]], 100
89; CHECK-NEXT:    br i1 [[C_0]], label [[EXIT]], label [[THEN_2:%.*]]
90; CHECK:       then.2:
91; CHECK-NEXT:    [[C_1:%.*]] = icmp eq ptr [[PTR_IV]], [[UPPER]]
92; CHECK-NEXT:    br i1 [[C_1]], label [[EXIT]], label [[FOR_BODY:%.*]]
93; CHECK:       for.body:
94; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond()
95; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_NEXT:%.*]], label [[EXIT]]
96; CHECK:       loop.next:
97; CHECK-NEXT:    [[T_1:%.*]] = icmp uge ptr [[PTR_IV]], [[START]]
98; CHECK-NEXT:    [[T_2:%.*]] = icmp ult ptr [[PTR_IV]], [[UPPER]]
99; CHECK-NEXT:    [[AND:%.*]] = and i1 [[T_1]], [[T_2]]
100; CHECK-NEXT:    br i1 [[AND]], label [[LOOP_LATCH]], label [[EXIT]]
101; CHECK:       loop.latch:
102; CHECK-NEXT:    call void @use(ptr [[PTR_IV]])
103; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i8, ptr [[PTR_IV]], i16 1
104; CHECK-NEXT:    br label [[LOOP_HEADER]]
105; CHECK:       exit:
106; CHECK-NEXT:    ret void
107;
108entry:
109  %upper = getelementptr inbounds i32, ptr %start, i16 %len
110  %len.neg = icmp slt i16 %len, 0
111  br i1 %len.neg, label %exit, label %loop.ph
112
113loop.ph:
114  br label %loop.header
115
116loop.header:
117  %ptr.iv = phi ptr [ %start, %loop.ph ], [ %ptr.iv.next, %loop.latch ]
118  %c.0 = icmp eq i16 %x, 1
119  br i1 %c.0, label %exit, label %then.1
120
121then.1:
122  %c.00 = icmp ult i16 %x, 100
123  br i1 %c.0, label %exit, label %then.2
124
125then.2:
126  %c.1 = icmp eq ptr %ptr.iv, %upper
127  br i1 %c.1, label %exit, label %for.body
128
129for.body:
130  %c.2 = call i1 @cond()
131  br i1 %c.2, label %loop.next, label %exit
132
133loop.next:
134  %t.1 = icmp uge ptr %ptr.iv, %start
135  %t.2 = icmp ult ptr %ptr.iv, %upper
136  %and = and i1 %t.1, %t.2
137  br i1 %and, label %loop.latch, label %exit
138
139loop.latch:
140  call void @use(ptr %ptr.iv)
141  %ptr.iv.next = getelementptr inbounds i8, ptr %ptr.iv, i16 1
142  br label %loop.header
143
144exit:
145  ret void
146}
147
148define void @test_monotonic_ptr_iv_inc_1_different_element_types_1_chain_of_2_exit_conditions_with_slt_in_header(ptr %start, i16 %len, i16 %x) {
149; CHECK-LABEL: @test_monotonic_ptr_iv_inc_1_different_element_types_1_chain_of_2_exit_conditions_with_slt_in_header(
150; CHECK-NEXT:  entry:
151; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[START:%.*]], i16 [[LEN:%.*]]
152; CHECK-NEXT:    br label [[LOOP_PH:%.*]]
153; CHECK:       loop.ph:
154; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
155; CHECK:       loop.header:
156; CHECK-NEXT:    [[PTR_IV:%.*]] = phi ptr [ [[START]], [[LOOP_PH]] ], [ [[PTR_IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
157; CHECK-NEXT:    [[LEN_NEG:%.*]] = icmp slt i16 [[LEN]], 0
158; CHECK-NEXT:    br i1 [[LEN_NEG]], label [[EXIT:%.*]], label [[THEN:%.*]]
159; CHECK:       then:
160; CHECK-NEXT:    [[C_1:%.*]] = icmp eq ptr [[PTR_IV]], [[UPPER]]
161; CHECK-NEXT:    br i1 [[C_1]], label [[EXIT]], label [[FOR_BODY:%.*]]
162; CHECK:       for.body:
163; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond()
164; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_NEXT:%.*]], label [[EXIT]]
165; CHECK:       loop.next:
166; CHECK-NEXT:    [[T_1:%.*]] = icmp uge ptr [[PTR_IV]], [[START]]
167; CHECK-NEXT:    [[T_2:%.*]] = icmp ult ptr [[PTR_IV]], [[UPPER]]
168; CHECK-NEXT:    [[AND:%.*]] = and i1 [[T_1]], [[T_2]]
169; CHECK-NEXT:    br i1 [[AND]], label [[LOOP_LATCH]], label [[EXIT]]
170; CHECK:       loop.latch:
171; CHECK-NEXT:    call void @use(ptr [[PTR_IV]])
172; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i8, ptr [[PTR_IV]], i16 1
173; CHECK-NEXT:    br label [[LOOP_HEADER]]
174; CHECK:       exit:
175; CHECK-NEXT:    ret void
176;
177entry:
178  %upper = getelementptr inbounds i32, ptr %start, i16 %len
179  br label %loop.ph
180
181loop.ph:
182  br label %loop.header
183
184loop.header:
185  %ptr.iv = phi ptr [ %start, %loop.ph ], [ %ptr.iv.next, %loop.latch ]
186  %len.neg = icmp slt i16 %len, 0
187  br i1 %len.neg, label %exit, label %then
188
189then:
190  %c.1 = icmp eq ptr %ptr.iv, %upper
191  br i1 %c.1, label %exit, label %for.body
192
193for.body:
194  %c.2 = call i1 @cond()
195  br i1 %c.2, label %loop.next, label %exit
196
197loop.next:
198  %t.1 = icmp uge ptr %ptr.iv, %start
199  %t.2 = icmp ult ptr %ptr.iv, %upper
200  %and = and i1 %t.1, %t.2
201  br i1 %and, label %loop.latch, label %exit
202
203loop.latch:
204  call void @use(ptr %ptr.iv)
205  %ptr.iv.next = getelementptr inbounds i8, ptr %ptr.iv, i16 1
206  br label %loop.header
207
208exit:
209  ret void
210}
211
212define void @test_header_not_exiting(ptr %start, i16 %len, i16 %x) {
213; CHECK-LABEL: @test_header_not_exiting(
214; CHECK-NEXT:  entry:
215; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[START:%.*]], i16 [[LEN:%.*]]
216; CHECK-NEXT:    br label [[LOOP_PH:%.*]]
217; CHECK:       loop.ph:
218; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
219; CHECK:       loop.header:
220; CHECK-NEXT:    [[PTR_IV:%.*]] = phi ptr [ [[START]], [[LOOP_PH]] ], [ [[PTR_IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
221; CHECK-NEXT:    [[LEN_NEG:%.*]] = icmp slt i16 [[LEN]], 0
222; CHECK-NEXT:    br i1 [[LEN_NEG]], label [[THEN:%.*]], label [[FOR_BODY:%.*]]
223; CHECK:       then:
224; CHECK-NEXT:    [[C_1:%.*]] = icmp eq ptr [[PTR_IV]], [[UPPER]]
225; CHECK-NEXT:    br i1 [[C_1]], label [[EXIT:%.*]], label [[FOR_BODY]]
226; CHECK:       for.body:
227; CHECK-NEXT:    [[C_2:%.*]] = call i1 @cond()
228; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_NEXT:%.*]], label [[EXIT]]
229; CHECK:       loop.next:
230; CHECK-NEXT:    [[T_1:%.*]] = icmp uge ptr [[PTR_IV]], [[START]]
231; CHECK-NEXT:    [[T_2:%.*]] = icmp ult ptr [[PTR_IV]], [[UPPER]]
232; CHECK-NEXT:    [[AND:%.*]] = and i1 [[T_1]], [[T_2]]
233; CHECK-NEXT:    br i1 [[AND]], label [[LOOP_LATCH]], label [[EXIT]]
234; CHECK:       loop.latch:
235; CHECK-NEXT:    call void @use(ptr [[PTR_IV]])
236; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i8, ptr [[PTR_IV]], i16 1
237; CHECK-NEXT:    br label [[LOOP_HEADER]]
238; CHECK:       exit:
239; CHECK-NEXT:    ret void
240;
241entry:
242  %upper = getelementptr inbounds i32, ptr %start, i16 %len
243  br label %loop.ph
244
245loop.ph:
246  br label %loop.header
247
248loop.header:
249  %ptr.iv = phi ptr [ %start, %loop.ph ], [ %ptr.iv.next, %loop.latch ]
250  %len.neg = icmp slt i16 %len, 0
251  br i1 %len.neg, label %then, label %for.body
252
253then:
254  %c.1 = icmp eq ptr %ptr.iv, %upper
255  br i1 %c.1, label %exit, label %for.body
256
257for.body:
258  %c.2 = call i1 @cond()
259  br i1 %c.2, label %loop.next, label %exit
260
261loop.next:
262  %t.1 = icmp uge ptr %ptr.iv, %start
263  %t.2 = icmp ult ptr %ptr.iv, %upper
264  %and = and i1 %t.1, %t.2
265  br i1 %and, label %loop.latch, label %exit
266
267loop.latch:
268  call void @use(ptr %ptr.iv)
269  %ptr.iv.next = getelementptr inbounds i8, ptr %ptr.iv, i16 1
270  br label %loop.header
271
272exit:
273  ret void
274}
275
276declare void @foo()
277
278define i32 @test_latch_exiting1(i32 %N) {
279; CHECK-LABEL: @test_latch_exiting1(
280; CHECK-NEXT:  entry:
281; CHECK-NEXT:    br label [[LOOP:%.*]]
282; CHECK:       loop:
283; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
284; CHECK-NEXT:    call void @foo()
285; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
286; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32 [[IV]], [[N:%.*]]
287; CHECK-NEXT:    br i1 [[EC]], label [[EXIT_1:%.*]], label [[LOOP]]
288; CHECK:       exit.1:
289; CHECK-NEXT:    ret i32 10
290;
291entry:
292  br label %loop
293
294loop:
295  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
296  call void @foo()
297  %iv.next = add i32 %iv, 1
298  %ec = icmp eq i32 %iv, %N
299  br i1 %ec, label %exit.1, label %loop
300
301exit.1:
302  ret i32 10
303}
304
305define i32 @test_latch_exiting2(i1 %c, i32 %N) {
306; CHECK-LABEL: @test_latch_exiting2(
307; CHECK-NEXT:  entry:
308; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
309; CHECK:       loop.header:
310; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
311; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP_LATCH]], label [[EXIT_1:%.*]]
312; CHECK:       loop.latch:
313; CHECK-NEXT:    call void @foo()
314; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
315; CHECK-NEXT:    [[EC:%.*]] = icmp eq i32 [[IV]], [[N:%.*]]
316; CHECK-NEXT:    br i1 [[EC]], label [[EXIT_2:%.*]], label [[LOOP_HEADER]]
317; CHECK:       exit.1:
318; CHECK-NEXT:    ret i32 10
319; CHECK:       exit.2:
320; CHECK-NEXT:    ret i32 0
321;
322entry:
323  br label %loop.header
324
325loop.header:
326  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ]
327  br i1 %c, label %loop.latch, label %exit.1
328
329loop.latch:
330  call void @foo()
331  %iv.next = add i32 %iv, 1
332  %ec = icmp eq i32 %iv, %N
333  br i1 %ec, label %exit.2, label %loop.header
334
335exit.1:
336  ret i32 10
337
338exit.2:
339  ret i32 0
340}
341