1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -indvars -S | FileCheck %s
3; RUN: opt < %s -passes=indvars -S | FileCheck %s
4
5declare i1 @cond()
6declare i32 @llvm.smax.i32(i32, i32)
7
8; FIXME: In all tests in this file, signed_cond is equivalent to unsigned_cond, and therefore
9; one of the checks in the inner loop can be removed. The key to proving it is to prove that
10; %iv starts from something that is non-negative and only goes up. The positivity of its start
11; follows from the fact that %outer.iv also starts from somethign non-negative and only goes
12; up or remains same between iterations.
13define i32 @test_01(i32 %a, i32 %b) {
14; CHECK-LABEL: @test_01(
15; CHECK-NEXT:  entry:
16; CHECK-NEXT:    [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0
17; CHECK-NEXT:    br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]]
18; CHECK:       outer.preheader:
19; CHECK-NEXT:    br label [[OUTER:%.*]]
20; CHECK:       outer:
21; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ]
22; CHECK-NEXT:    br label [[INNER:%.*]]
23; CHECK:       inner:
24; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
25; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
26; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
27; CHECK:       inner.1:
28; CHECK-NEXT:    [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
29; CHECK-NEXT:    br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
30; CHECK:       inner.backedge:
31; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
32; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
33; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
34; CHECK:       outer.backedge:
35; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
36; CHECK-NEXT:    [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
37; CHECK-NEXT:    br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
38; CHECK:       failure:
39; CHECK-NEXT:    unreachable
40; CHECK:       side.exit:
41; CHECK-NEXT:    ret i32 0
42; CHECK:       exit:
43; CHECK-NEXT:    ret i32 1
44;
45entry:
46  %b_is_non_negative = icmp sge i32 %b, 0
47  br i1 %b_is_non_negative, label %outer, label %failure
48
49outer:
50  %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge]
51  br label %inner
52
53
54inner:
55  %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge]
56  %signed_cond = icmp slt i32 %iv, %b
57  br i1 %signed_cond, label %inner.1, label %side.exit
58
59inner.1:
60  %unsigned_cond = icmp ult i32 %iv, %b
61  br i1 %unsigned_cond, label %inner.backedge, label %side.exit
62
63inner.backedge:
64  %iv.next = add nuw nsw i32 %iv, 1
65  %inner.loop.cond = call i1 @cond()
66  br i1 %inner.loop.cond, label %inner, label %outer.backedge
67
68outer.backedge:
69  %outer.loop.cond = call i1 @cond()
70  br i1 %outer.loop.cond, label %outer, label %exit
71
72failure:
73  unreachable
74
75side.exit:
76  ret i32 0
77
78exit:
79  ret i32 1
80}
81
82; FIXME: iv <u b, b >=s 0 --> iv <s b. We should be able to remove the 2nd check.
83define i32 @test_01a(i32 %a, i32 %b) {
84; CHECK-LABEL: @test_01a(
85; CHECK-NEXT:  entry:
86; CHECK-NEXT:    [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0
87; CHECK-NEXT:    br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]]
88; CHECK:       outer.preheader:
89; CHECK-NEXT:    br label [[OUTER:%.*]]
90; CHECK:       outer:
91; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ]
92; CHECK-NEXT:    br label [[INNER:%.*]]
93; CHECK:       inner:
94; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
95; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
96; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
97; CHECK:       inner.1:
98; CHECK-NEXT:    [[UNSIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
99; CHECK-NEXT:    br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
100; CHECK:       inner.backedge:
101; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
102; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
103; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
104; CHECK:       outer.backedge:
105; CHECK-NEXT:    [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
106; CHECK-NEXT:    [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
107; CHECK-NEXT:    br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
108; CHECK:       failure:
109; CHECK-NEXT:    unreachable
110; CHECK:       side.exit:
111; CHECK-NEXT:    ret i32 0
112; CHECK:       exit:
113; CHECK-NEXT:    ret i32 1
114;
115entry:
116  %b_is_non_negative = icmp sge i32 %b, 0
117  br i1 %b_is_non_negative, label %outer, label %failure
118
119outer:
120  %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge]
121  br label %inner
122
123
124inner:
125  %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge]
126  %signed_cond = icmp ult i32 %iv, %b
127  br i1 %signed_cond, label %inner.1, label %side.exit
128
129inner.1:
130  %unsigned_cond = icmp slt i32 %iv, %b
131  br i1 %unsigned_cond, label %inner.backedge, label %side.exit
132
133inner.backedge:
134  %iv.next = add nuw nsw i32 %iv, 1
135  %inner.loop.cond = call i1 @cond()
136  br i1 %inner.loop.cond, label %inner, label %outer.backedge
137
138outer.backedge:
139  %outer.loop.cond = call i1 @cond()
140  br i1 %outer.loop.cond, label %outer, label %exit
141
142failure:
143  unreachable
144
145side.exit:
146  ret i32 0
147
148exit:
149  ret i32 1
150}
151
152define i32 @test_02(i32 %a, i32 %b) {
153; CHECK-LABEL: @test_02(
154; CHECK-NEXT:  entry:
155; CHECK-NEXT:    [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0
156; CHECK-NEXT:    br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]]
157; CHECK:       outer.preheader:
158; CHECK-NEXT:    br label [[OUTER:%.*]]
159; CHECK:       outer:
160; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ]
161; CHECK-NEXT:    br label [[INNER:%.*]]
162; CHECK:       inner:
163; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ]
164; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
165; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
166; CHECK:       inner.1:
167; CHECK-NEXT:    [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
168; CHECK-NEXT:    br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
169; CHECK:       inner.backedge:
170; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
171; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
172; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]]
173; CHECK:       outer.backedge:
174; CHECK-NEXT:    [[OUTER_MERGE]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
175; CHECK-NEXT:    [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
176; CHECK-NEXT:    br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
177; CHECK:       failure:
178; CHECK-NEXT:    unreachable
179; CHECK:       side.exit:
180; CHECK-NEXT:    ret i32 0
181; CHECK:       exit:
182; CHECK-NEXT:    ret i32 1
183;
184entry:
185  %b_is_non_negative = icmp sge i32 %b, 0
186  br i1 %b_is_non_negative, label %outer, label %failure
187
188outer:
189  %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge]
190  br label %inner
191
192
193inner:
194  %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge]
195  %signed_cond = icmp slt i32 %iv, %b
196  br i1 %signed_cond, label %inner.1, label %side.exit
197
198inner.1:
199  %unsigned_cond = icmp ult i32 %iv, %b
200  br i1 %unsigned_cond, label %inner.backedge, label %side.exit
201
202inner.backedge:
203  %iv.next = add nuw nsw i32 %iv, 1
204  %inner.loop.cond = call i1 @cond()
205  br i1 %inner.loop.cond, label %inner, label %outer.backedge
206
207outer.backedge:
208  %outer.merge = phi i32 [%iv.next, %inner.backedge]
209  %outer.loop.cond = call i1 @cond()
210  br i1 %outer.loop.cond, label %outer, label %exit
211
212failure:
213  unreachable
214
215side.exit:
216  ret i32 0
217
218exit:
219  ret i32 1
220}
221
222define i32 @test_03(i32 %a, i32 %b) {
223; CHECK-LABEL: @test_03(
224; CHECK-NEXT:  entry:
225; CHECK-NEXT:    [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0
226; CHECK-NEXT:    br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]]
227; CHECK:       outer.preheader:
228; CHECK-NEXT:    br label [[OUTER:%.*]]
229; CHECK:       outer:
230; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ]
231; CHECK-NEXT:    [[OUTER_COND_1:%.*]] = call i1 @cond()
232; CHECK-NEXT:    br i1 [[OUTER_COND_1]], label [[INNER_PREHEADER:%.*]], label [[NO_INNER:%.*]]
233; CHECK:       inner.preheader:
234; CHECK-NEXT:    br label [[INNER:%.*]]
235; CHECK:       no_inner:
236; CHECK-NEXT:    [[OUTER_COND_2:%.*]] = call i1 @cond()
237; CHECK-NEXT:    br label [[OUTER_BACKEDGE]]
238; CHECK:       inner:
239; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ], [ [[OUTER_IV]], [[INNER_PREHEADER]] ]
240; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
241; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
242; CHECK:       inner.1:
243; CHECK-NEXT:    [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
244; CHECK-NEXT:    br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
245; CHECK:       inner.backedge:
246; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
247; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
248; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]]
249; CHECK:       outer.backedge.loopexit:
250; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
251; CHECK-NEXT:    br label [[OUTER_BACKEDGE]]
252; CHECK:       outer.backedge:
253; CHECK-NEXT:    [[OUTER_MERGE]] = phi i32 [ [[OUTER_IV]], [[NO_INNER]] ], [ [[IV_NEXT_LCSSA]], [[OUTER_BACKEDGE_LOOPEXIT]] ]
254; CHECK-NEXT:    [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
255; CHECK-NEXT:    br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
256; CHECK:       failure:
257; CHECK-NEXT:    unreachable
258; CHECK:       side.exit:
259; CHECK-NEXT:    ret i32 0
260; CHECK:       exit:
261; CHECK-NEXT:    ret i32 1
262;
263entry:
264  %b_is_non_negative = icmp sge i32 %b, 0
265  br i1 %b_is_non_negative, label %outer, label %failure
266
267outer:
268  %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge]
269  %outer_cond_1 = call i1 @cond()
270  br i1 %outer_cond_1, label %inner, label %no_inner
271
272no_inner:
273  %outer_cond_2 = call i1 @cond()
274  br label %outer.backedge
275
276inner:
277  %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge]
278  %signed_cond = icmp slt i32 %iv, %b
279  br i1 %signed_cond, label %inner.1, label %side.exit
280
281inner.1:
282  %unsigned_cond = icmp ult i32 %iv, %b
283  br i1 %unsigned_cond, label %inner.backedge, label %side.exit
284
285inner.backedge:
286  %iv.next = add nuw nsw i32 %iv, 1
287  %inner.loop.cond = call i1 @cond()
288  br i1 %inner.loop.cond, label %inner, label %outer.backedge
289
290outer.backedge:
291  %outer.merge = phi i32 [%outer.iv, %no_inner], [%iv.next, %inner.backedge]
292  %outer.loop.cond = call i1 @cond()
293  br i1 %outer.loop.cond, label %outer, label %exit
294
295failure:
296  unreachable
297
298side.exit:
299  ret i32 0
300
301exit:
302  ret i32 1
303}
304
305define i32 @test_04(i32 %a, i32 %b) {
306; CHECK-LABEL: @test_04(
307; CHECK-NEXT:  entry:
308; CHECK-NEXT:    [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0
309; CHECK-NEXT:    br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]]
310; CHECK:       outer.preheader:
311; CHECK-NEXT:    br label [[OUTER:%.*]]
312; CHECK:       outer:
313; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i32 [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ]
314; CHECK-NEXT:    [[OUTER_COND_1:%.*]] = call i1 @cond()
315; CHECK-NEXT:    br i1 [[OUTER_COND_1]], label [[INNER_PREHEADER:%.*]], label [[NO_INNER:%.*]]
316; CHECK:       inner.preheader:
317; CHECK-NEXT:    br label [[INNER:%.*]]
318; CHECK:       no_inner:
319; CHECK-NEXT:    [[OUTER_COND_2:%.*]] = call i1 @cond()
320; CHECK-NEXT:    br i1 [[OUTER_COND_2]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
321; CHECK:       if.true:
322; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[A:%.*]], i32 [[OUTER_IV]])
323; CHECK-NEXT:    br label [[OUTER_BACKEDGE]]
324; CHECK:       if.false:
325; CHECK-NEXT:    br label [[OUTER_BACKEDGE]]
326; CHECK:       inner:
327; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ], [ [[OUTER_IV]], [[INNER_PREHEADER]] ]
328; CHECK-NEXT:    [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]]
329; CHECK-NEXT:    br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]]
330; CHECK:       inner.1:
331; CHECK-NEXT:    [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]]
332; CHECK-NEXT:    br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]]
333; CHECK:       inner.backedge:
334; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
335; CHECK-NEXT:    [[INNER_LOOP_COND:%.*]] = call i1 @cond()
336; CHECK-NEXT:    br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]]
337; CHECK:       outer.backedge.loopexit:
338; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ]
339; CHECK-NEXT:    br label [[OUTER_BACKEDGE]]
340; CHECK:       outer.backedge:
341; CHECK-NEXT:    [[OUTER_MERGE]] = phi i32 [ [[SMAX]], [[IF_TRUE]] ], [ [[OUTER_IV]], [[IF_FALSE]] ], [ [[IV_NEXT_LCSSA]], [[OUTER_BACKEDGE_LOOPEXIT]] ]
342; CHECK-NEXT:    [[OUTER_LOOP_COND:%.*]] = call i1 @cond()
343; CHECK-NEXT:    br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]]
344; CHECK:       failure:
345; CHECK-NEXT:    unreachable
346; CHECK:       side.exit:
347; CHECK-NEXT:    ret i32 0
348; CHECK:       exit:
349; CHECK-NEXT:    ret i32 1
350;
351entry:
352  %b_is_non_negative = icmp sge i32 %b, 0
353  br i1 %b_is_non_negative, label %outer, label %failure
354
355outer:
356  %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge]
357  %outer_cond_1 = call i1 @cond()
358  br i1 %outer_cond_1, label %inner, label %no_inner
359
360no_inner:
361  %outer_cond_2 = call i1 @cond()
362  br i1 %outer_cond_2, label %if.true, label %if.false
363
364if.true:
365  %smax = call i32 @llvm.smax.i32(i32 %a, i32 %outer.iv)
366  br label %outer.backedge
367
368if.false:
369  br label %outer.backedge
370
371inner:
372  %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge]
373  %signed_cond = icmp slt i32 %iv, %b
374  br i1 %signed_cond, label %inner.1, label %side.exit
375
376inner.1:
377  %unsigned_cond = icmp ult i32 %iv, %b
378  br i1 %unsigned_cond, label %inner.backedge, label %side.exit
379
380inner.backedge:
381  %iv.next = add nuw nsw i32 %iv, 1
382  %inner.loop.cond = call i1 @cond()
383  br i1 %inner.loop.cond, label %inner, label %outer.backedge
384
385outer.backedge:
386  %outer.merge = phi i32 [%smax, %if.true], [%outer.iv, %if.false], [%iv.next, %inner.backedge]
387  %outer.loop.cond = call i1 @cond()
388  br i1 %outer.loop.cond, label %outer, label %exit
389
390failure:
391  unreachable
392
393side.exit:
394  ret i32 0
395
396exit:
397  ret i32 1
398}
399