1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -indvars -S < %s | FileCheck %s
3
4define void @ult(i64 %n, i64 %m) {
5; CHECK-LABEL: @ult(
6; CHECK-NEXT:  entry:
7; CHECK-NEXT:    [[CMP0:%.*]] = icmp ult i64 [[N:%.*]], [[M:%.*]]
8; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
9; CHECK:       loop.preheader:
10; CHECK-NEXT:    br label [[LOOP:%.*]]
11; CHECK:       loop:
12; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
13; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
14; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i64 [[IV]], [[N]]
15; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
16; CHECK:       latch:
17; CHECK-NEXT:    call void @side_effect()
18; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[EXIT_LOOPEXIT]]
19; CHECK:       exit.loopexit:
20; CHECK-NEXT:    br label [[EXIT]]
21; CHECK:       exit:
22; CHECK-NEXT:    ret void
23;
24entry:
25  %cmp0 = icmp ult i64 %n, %m
26  br i1 %cmp0, label %loop, label %exit
27loop:
28  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
29  %iv.next = add i64 %iv, 1
30  %cmp1 = icmp ult i64 %iv, %n
31  br i1 %cmp1, label %latch, label %exit
32latch:
33  call void @side_effect()
34  %cmp2 = icmp ult i64 %iv, %m
35  br i1 %cmp2, label %loop, label %exit
36exit:
37  ret void
38}
39
40define void @ugt(i64 %n, i64 %m) {
41; CHECK-LABEL: @ugt(
42; CHECK-NEXT:  entry:
43; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i64 [[N:%.*]], [[M:%.*]]
44; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
45; CHECK:       loop.preheader:
46; CHECK-NEXT:    br label [[LOOP:%.*]]
47; CHECK:       loop:
48; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
49; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
50; CHECK-NEXT:    br i1 true, label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
51; CHECK:       latch:
52; CHECK-NEXT:    call void @side_effect()
53; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[IV]], [[M]]
54; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]]
55; CHECK:       exit.loopexit:
56; CHECK-NEXT:    br label [[EXIT]]
57; CHECK:       exit:
58; CHECK-NEXT:    ret void
59;
60entry:
61  %cmp0 = icmp ugt i64 %n, %m
62  br i1 %cmp0, label %loop, label %exit
63loop:
64  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
65  %iv.next = add i64 %iv, 1
66  %cmp1 = icmp ult i64 %iv, %n
67  br i1 %cmp1, label %latch, label %exit
68latch:
69  call void @side_effect()
70  %cmp2 = icmp ult i64 %iv, %m
71  br i1 %cmp2, label %loop, label %exit
72exit:
73  ret void
74}
75
76define void @ule(i64 %n, i64 %m) {
77; CHECK-LABEL: @ule(
78; CHECK-NEXT:  entry:
79; CHECK-NEXT:    [[CMP0:%.*]] = icmp ule i64 [[N:%.*]], [[M:%.*]]
80; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
81; CHECK:       loop.preheader:
82; CHECK-NEXT:    br label [[LOOP:%.*]]
83; CHECK:       loop:
84; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
85; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
86; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i64 [[IV]], [[N]]
87; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
88; CHECK:       latch:
89; CHECK-NEXT:    call void @side_effect()
90; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[IV]], [[M]]
91; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]]
92; CHECK:       exit.loopexit:
93; CHECK-NEXT:    br label [[EXIT]]
94; CHECK:       exit:
95; CHECK-NEXT:    ret void
96;
97entry:
98  %cmp0 = icmp ule i64 %n, %m
99  br i1 %cmp0, label %loop, label %exit
100loop:
101  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
102  %iv.next = add i64 %iv, 1
103  %cmp1 = icmp ult i64 %iv, %n
104  br i1 %cmp1, label %latch, label %exit
105latch:
106  call void @side_effect()
107  %cmp2 = icmp ult i64 %iv, %m
108  br i1 %cmp2, label %loop, label %exit
109exit:
110  ret void
111}
112
113define void @uge(i64 %n, i64 %m) {
114; CHECK-LABEL: @uge(
115; CHECK-NEXT:  entry:
116; CHECK-NEXT:    [[CMP0:%.*]] = icmp uge i64 [[N:%.*]], [[M:%.*]]
117; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
118; CHECK:       loop.preheader:
119; CHECK-NEXT:    br label [[LOOP:%.*]]
120; CHECK:       loop:
121; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
122; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
123; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i64 [[IV]], [[N]]
124; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
125; CHECK:       latch:
126; CHECK-NEXT:    call void @side_effect()
127; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[IV]], [[M]]
128; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]]
129; CHECK:       exit.loopexit:
130; CHECK-NEXT:    br label [[EXIT]]
131; CHECK:       exit:
132; CHECK-NEXT:    ret void
133;
134entry:
135  %cmp0 = icmp uge i64 %n, %m
136  br i1 %cmp0, label %loop, label %exit
137loop:
138  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
139  %iv.next = add i64 %iv, 1
140  %cmp1 = icmp ult i64 %iv, %n
141  br i1 %cmp1, label %latch, label %exit
142latch:
143  call void @side_effect()
144  %cmp2 = icmp ult i64 %iv, %m
145  br i1 %cmp2, label %loop, label %exit
146exit:
147  ret void
148}
149
150
151define void @ult_const_max(i64 %n) {
152; CHECK-LABEL: @ult_const_max(
153; CHECK-NEXT:  entry:
154; CHECK-NEXT:    [[CMP0:%.*]] = icmp ult i64 [[N:%.*]], 20
155; CHECK-NEXT:    br i1 [[CMP0]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
156; CHECK:       loop.preheader:
157; CHECK-NEXT:    br label [[LOOP:%.*]]
158; CHECK:       loop:
159; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
160; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
161; CHECK-NEXT:    br i1 true, label [[LATCH]], label [[EXIT_LOOPEXIT:%.*]]
162; CHECK:       latch:
163; CHECK-NEXT:    call void @side_effect()
164; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[IV]], [[N]]
165; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP]], label [[EXIT_LOOPEXIT]]
166; CHECK:       exit.loopexit:
167; CHECK-NEXT:    br label [[EXIT]]
168; CHECK:       exit:
169; CHECK-NEXT:    ret void
170;
171entry:
172  %cmp0 = icmp ult i64 %n, 20
173  br i1 %cmp0, label %loop, label %exit
174loop:
175  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
176  %iv.next = add i64 %iv, 1
177  %udiv = udiv i64 %iv, 10
178  %cmp1 = icmp ult i64 %udiv, 2
179  br i1 %cmp1, label %latch, label %exit
180latch:
181  call void @side_effect()
182  %cmp2 = icmp ult i64 %iv, %n
183  br i1 %cmp2, label %loop, label %exit
184exit:
185  ret void
186}
187
188define void @mixed_width(i32 %len) {
189; CHECK-LABEL: @mixed_width(
190; CHECK-NEXT:  entry:
191; CHECK-NEXT:    [[LEN_ZEXT:%.*]] = zext i32 [[LEN:%.*]] to i64
192; CHECK-NEXT:    br label [[LOOP:%.*]]
193; CHECK:       loop:
194; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
195; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
196; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i64 [[IV]], [[LEN_ZEXT]]
197; CHECK-NEXT:    br i1 [[CMP1]], label [[BACKEDGE]], label [[EXIT:%.*]]
198; CHECK:       backedge:
199; CHECK-NEXT:    call void @side_effect()
200; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[EXIT]]
201; CHECK:       exit:
202; CHECK-NEXT:    ret void
203;
204entry:
205  %len.zext = zext i32 %len to i64
206  br label %loop
207loop:
208  %iv = phi i64 [0, %entry], [%iv.next, %backedge]
209  %iv2 = phi i32 [0, %entry], [%iv2.next, %backedge]
210  %iv.next = add i64 %iv, 1
211  %iv2.next = add i32 %iv2, 1
212  %cmp1 = icmp ult i64 %iv, %len.zext
213  br i1 %cmp1, label %backedge, label %exit
214
215backedge:
216  call void @side_effect()
217  %cmp2 = icmp ult i32 %iv2, %len
218  br i1 %cmp2, label %loop, label %exit
219exit:
220  ret void
221}
222
223define void @many_exits([100 x i64] %len) {
224entry:
225  br label %loop
226loop:
227  %iv = phi i64 [0, %entry], [%iv.next, %backedge]
228  %len0 = extractvalue [100 x i64] %len, 0
229  %early0 = icmp eq i64 %iv, %len0
230  call void @side_effect()
231  br i1 %early0, label %exit, label %cont0
232cont0:
233  %len1 = extractvalue [100 x i64] %len, 1
234  %early1 = icmp eq i64 %iv, %len1
235  call void @side_effect()
236  br i1 %early1, label %exit, label %cont1
237cont1:
238  %len2 = extractvalue [100 x i64] %len, 2
239  %early2 = icmp eq i64 %iv, %len2
240  call void @side_effect()
241  br i1 %early2, label %exit, label %cont2
242cont2:
243  %len3 = extractvalue [100 x i64] %len, 3
244  %early3 = icmp eq i64 %iv, %len3
245  call void @side_effect()
246  br i1 %early3, label %exit, label %cont3
247cont3:
248  %len4 = extractvalue [100 x i64] %len, 4
249  %early4 = icmp eq i64 %iv, %len4
250  call void @side_effect()
251  br i1 %early4, label %exit, label %cont4
252cont4:
253  %len5 = extractvalue [100 x i64] %len, 5
254  %early5 = icmp eq i64 %iv, %len5
255  call void @side_effect()
256  br i1 %early5, label %exit, label %cont5
257cont5:
258  %len6 = extractvalue [100 x i64] %len, 6
259  %early6 = icmp eq i64 %iv, %len6
260  call void @side_effect()
261  br i1 %early6, label %exit, label %cont6
262cont6:
263  %len7 = extractvalue [100 x i64] %len, 7
264  %early7 = icmp eq i64 %iv, %len7
265  call void @side_effect()
266  br i1 %early7, label %exit, label %cont7
267cont7:
268  %len8 = extractvalue [100 x i64] %len, 8
269  %early8 = icmp eq i64 %iv, %len8
270  call void @side_effect()
271  br i1 %early8, label %exit, label %cont8
272cont8:
273  %len9 = extractvalue [100 x i64] %len, 9
274  %early9 = icmp eq i64 %iv, %len9
275  call void @side_effect()
276  br i1 %early9, label %exit, label %cont9
277cont9:
278  %len10 = extractvalue [100 x i64] %len, 10
279  %early10 = icmp eq i64 %iv, %len10
280  call void @side_effect()
281  br i1 %early10, label %exit, label %cont10
282cont10:
283  %len11 = extractvalue [100 x i64] %len, 11
284  %early11 = icmp eq i64 %iv, %len11
285  call void @side_effect()
286  br i1 %early11, label %exit, label %cont11
287cont11:
288  %len12 = extractvalue [100 x i64] %len, 12
289  %early12 = icmp eq i64 %iv, %len12
290  call void @side_effect()
291  br i1 %early12, label %exit, label %cont12
292cont12:
293  %len13 = extractvalue [100 x i64] %len, 13
294  %early13 = icmp eq i64 %iv, %len13
295  call void @side_effect()
296  br i1 %early13, label %exit, label %cont13
297cont13:
298  %len14 = extractvalue [100 x i64] %len, 14
299  %early14 = icmp eq i64 %iv, %len14
300  call void @side_effect()
301  br i1 %early14, label %exit, label %cont14
302cont14:
303  %len15 = extractvalue [100 x i64] %len, 15
304  %early15 = icmp eq i64 %iv, %len15
305  call void @side_effect()
306  br i1 %early15, label %exit, label %cont15
307cont15:
308  %len16 = extractvalue [100 x i64] %len, 16
309  %early16 = icmp eq i64 %iv, %len16
310  call void @side_effect()
311  br i1 %early16, label %exit, label %cont16
312cont16:
313  %len17 = extractvalue [100 x i64] %len, 17
314  %early17 = icmp eq i64 %iv, %len17
315  call void @side_effect()
316  br i1 %early17, label %exit, label %cont17
317cont17:
318  %len18 = extractvalue [100 x i64] %len, 18
319  %early18 = icmp eq i64 %iv, %len18
320  call void @side_effect()
321  br i1 %early18, label %exit, label %cont18
322cont18:
323  %len19 = extractvalue [100 x i64] %len, 19
324  %early19 = icmp eq i64 %iv, %len19
325  call void @side_effect()
326  br i1 %early19, label %exit, label %cont19
327cont19:
328  %len20 = extractvalue [100 x i64] %len, 20
329  %early20 = icmp eq i64 %iv, %len20
330  call void @side_effect()
331  br i1 %early20, label %exit, label %cont20
332cont20:
333  %len21 = extractvalue [100 x i64] %len, 21
334  %early21 = icmp eq i64 %iv, %len21
335  call void @side_effect()
336  br i1 %early21, label %exit, label %cont21
337cont21:
338  %len22 = extractvalue [100 x i64] %len, 22
339  %early22 = icmp eq i64 %iv, %len22
340  call void @side_effect()
341  br i1 %early22, label %exit, label %cont22
342cont22:
343  %len23 = extractvalue [100 x i64] %len, 23
344  %early23 = icmp eq i64 %iv, %len23
345  call void @side_effect()
346  br i1 %early23, label %exit, label %cont23
347cont23:
348  %len24 = extractvalue [100 x i64] %len, 24
349  %early24 = icmp eq i64 %iv, %len24
350  call void @side_effect()
351  br i1 %early24, label %exit, label %cont24
352cont24:
353  %len25 = extractvalue [100 x i64] %len, 25
354  %early25 = icmp eq i64 %iv, %len25
355  call void @side_effect()
356  br i1 %early25, label %exit, label %cont25
357cont25:
358  %len26 = extractvalue [100 x i64] %len, 26
359  %early26 = icmp eq i64 %iv, %len26
360  call void @side_effect()
361  br i1 %early26, label %exit, label %cont26
362cont26:
363  %len27 = extractvalue [100 x i64] %len, 27
364  %early27 = icmp eq i64 %iv, %len27
365  call void @side_effect()
366  br i1 %early27, label %exit, label %cont27
367cont27:
368  %len28 = extractvalue [100 x i64] %len, 28
369  %early28 = icmp eq i64 %iv, %len28
370  call void @side_effect()
371  br i1 %early28, label %exit, label %cont28
372cont28:
373  %len29 = extractvalue [100 x i64] %len, 29
374  %early29 = icmp eq i64 %iv, %len29
375  call void @side_effect()
376  br i1 %early29, label %exit, label %cont29
377cont29:
378  %len30 = extractvalue [100 x i64] %len, 30
379  %early30 = icmp eq i64 %iv, %len30
380  call void @side_effect()
381  br i1 %early30, label %exit, label %cont30
382cont30:
383  %len31 = extractvalue [100 x i64] %len, 31
384  %early31 = icmp eq i64 %iv, %len31
385  call void @side_effect()
386  br i1 %early31, label %exit, label %cont31
387cont31:
388  %len32 = extractvalue [100 x i64] %len, 32
389  %early32 = icmp eq i64 %iv, %len32
390  call void @side_effect()
391  br i1 %early32, label %exit, label %cont32
392cont32:
393  %len33 = extractvalue [100 x i64] %len, 33
394  %early33 = icmp eq i64 %iv, %len33
395  call void @side_effect()
396  br i1 %early33, label %exit, label %cont33
397cont33:
398  %len34 = extractvalue [100 x i64] %len, 34
399  %early34 = icmp eq i64 %iv, %len34
400  call void @side_effect()
401  br i1 %early34, label %exit, label %cont34
402cont34:
403  %len35 = extractvalue [100 x i64] %len, 35
404  %early35 = icmp eq i64 %iv, %len35
405  call void @side_effect()
406  br i1 %early35, label %exit, label %cont35
407cont35:
408  %len36 = extractvalue [100 x i64] %len, 36
409  %early36 = icmp eq i64 %iv, %len36
410  call void @side_effect()
411  br i1 %early36, label %exit, label %cont36
412cont36:
413  %len37 = extractvalue [100 x i64] %len, 37
414  %early37 = icmp eq i64 %iv, %len37
415  call void @side_effect()
416  br i1 %early37, label %exit, label %cont37
417cont37:
418  %len38 = extractvalue [100 x i64] %len, 38
419  %early38 = icmp eq i64 %iv, %len38
420  call void @side_effect()
421  br i1 %early38, label %exit, label %cont38
422cont38:
423  %len39 = extractvalue [100 x i64] %len, 39
424  %early39 = icmp eq i64 %iv, %len39
425  call void @side_effect()
426  br i1 %early39, label %exit, label %cont39
427cont39:
428  br label %backedge
429backedge:
430  call void @side_effect()
431  %cmp2 = icmp ult i64 %iv, 999
432  %iv.next = add i64 %iv, 1
433  br i1 %cmp2, label %loop, label %exit
434exit:
435  ret void
436}
437
438declare void @side_effect()
439
440; The exit condition %outer.cond.1 depends on a phi in %inner. Make sure we do
441; not incorrectly determine %x.lcssa <= -1.
442define i32 @exit_cond_depends_on_inner_loop() {
443; CHECK-LABEL: @exit_cond_depends_on_inner_loop(
444; CHECK-NEXT:  entry:
445; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
446; CHECK:       outer.header:
447; CHECK-NEXT:    [[IV_OUTER:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_OUTER_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
448; CHECK-NEXT:    br label [[INNER:%.*]]
449; CHECK:       inner:
450; CHECK-NEXT:    [[X:%.*]] = phi i32 [ -1, [[OUTER_HEADER]] ], [ [[CALL:%.*]], [[INNER]] ]
451; CHECK-NEXT:    [[CALL]] = call i32 @match()
452; CHECK-NEXT:    [[INNER_COND:%.*]] = icmp sgt i32 [[CALL]], -1
453; CHECK-NEXT:    br i1 [[INNER_COND]], label [[INNER]], label [[OUTER_EXITING_1:%.*]]
454; CHECK:       outer.exiting.1:
455; CHECK-NEXT:    [[X_LCSSA:%.*]] = phi i32 [ [[X]], [[INNER]] ]
456; CHECK-NEXT:    [[OUTER_COND_1:%.*]] = icmp sgt i32 [[X_LCSSA]], -1
457; CHECK-NEXT:    br i1 [[OUTER_COND_1]], label [[EXIT:%.*]], label [[OUTER_LATCH]]
458; CHECK:       outer.latch:
459; CHECK-NEXT:    [[IV_OUTER_NEXT]] = add nuw nsw i32 [[IV_OUTER]], 1
460; CHECK-NEXT:    [[OUTER_COND_2:%.*]] = icmp ult i32 [[IV_OUTER]], 100
461; CHECK-NEXT:    br i1 [[OUTER_COND_2]], label [[OUTER_HEADER]], label [[EXIT]]
462; CHECK:       exit:
463; CHECK-NEXT:    [[X_RES:%.*]] = phi i32 [ [[X_LCSSA]], [[OUTER_EXITING_1]] ], [ -1, [[OUTER_LATCH]] ]
464; CHECK-NEXT:    ret i32 [[X_RES]]
465;
466entry:
467  br label %outer.header
468
469outer.header:
470  %iv.outer = phi i32 [ 0, %entry ], [ %iv.outer.next , %outer.latch ]
471  br label %inner
472
473inner:
474  %x = phi i32 [ -1, %outer.header ], [ %call, %inner ]
475  %call = call i32 @match()
476  %inner.cond = icmp sgt i32 %call, -1
477  br i1 %inner.cond, label %inner, label %outer.exiting.1
478
479outer.exiting.1:
480  %x.lcssa = phi i32 [ %x, %inner ]
481  %outer.cond.1 = icmp sgt i32 %x.lcssa, -1
482  br i1 %outer.cond.1, label %exit, label %outer.latch
483
484outer.latch:
485  %iv.outer.next = add nuw nsw i32 %iv.outer, 1
486  %outer.cond.2 = icmp ult i32 %iv.outer, 100
487  br i1 %outer.cond.2, label %outer.header, label %exit
488
489exit:
490  %x.res = phi i32 [ %x.lcssa, %outer.exiting.1 ], [ -1, %outer.latch ]
491  ret i32 %x.res
492}
493
494declare i32 @match()
495