xref: /llvm-project/llvm/test/Transforms/IndVarSimplify/X86/loop-invariant-conditions.ll (revision a7f35d54eef95e308ed13af5f46dbfc6c559cb9b)
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -S -passes=indvars -indvars-predicate-loops=0 %s | FileCheck %s
3target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
4target triple = "x86_64-unknown-linux-gnu"
5
6define void @test1(i64 %start) {
7; CHECK-LABEL: @test1(
8; CHECK-NEXT:  entry:
9; CHECK-NEXT:    br label [[LOOP:%.*]]
10; CHECK:       loop:
11; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[START:%.*]], -1
12; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
13; CHECK:       for.end:
14; CHECK-NEXT:    ret void
15;
16entry:
17  br label %loop
18
19loop:
20  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
21  %indvars.iv.next = add nsw i64 %indvars.iv, 1
22  %cmp1 = icmp slt i64 %indvars.iv, -1
23  br i1 %cmp1, label %for.end, label %loop
24
25for.end:                                          ; preds = %if.end, %entry
26  ret void
27}
28
29define void @test1.next(i64 %start) {
30; CHECK-LABEL: @test1.next(
31; CHECK-NEXT:  entry:
32; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[START:%.*]], 1
33; CHECK-NEXT:    br label [[LOOP:%.*]]
34; CHECK:       loop:
35; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[TMP0]], 0
36; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
37; CHECK:       for.end:
38; CHECK-NEXT:    ret void
39;
40entry:
41  br label %loop
42
43loop:
44  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
45  %indvars.iv.next = add nsw i64 %indvars.iv, 1
46  %cmp1 = icmp slt i64 %indvars.iv.next, 0
47  br i1 %cmp1, label %for.end, label %loop
48
49for.end:                                          ; preds = %if.end, %entry
50  ret void
51}
52
53define void @test2(i64 %start) {
54; CHECK-LABEL: @test2(
55; CHECK-NEXT:  entry:
56; CHECK-NEXT:    br label [[LOOP:%.*]]
57; CHECK:       loop:
58; CHECK-NEXT:    [[CMP1:%.*]] = icmp sle i64 [[START:%.*]], -1
59; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
60; CHECK:       for.end:
61; CHECK-NEXT:    ret void
62;
63entry:
64  br label %loop
65
66loop:
67  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
68  %indvars.iv.next = add nsw i64 %indvars.iv, 1
69  %cmp1 = icmp sle i64 %indvars.iv, -1
70  br i1 %cmp1, label %for.end, label %loop
71
72for.end:                                          ; preds = %if.end, %entry
73  ret void
74}
75
76define void @test2.next(i64 %start) {
77; CHECK-LABEL: @test2.next(
78; CHECK-NEXT:  entry:
79; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[START:%.*]], 1
80; CHECK-NEXT:    br label [[LOOP:%.*]]
81; CHECK:       loop:
82; CHECK-NEXT:    [[CMP1:%.*]] = icmp sle i64 [[TMP0]], 0
83; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
84; CHECK:       for.end:
85; CHECK-NEXT:    ret void
86;
87entry:
88  br label %loop
89
90loop:
91  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
92  %indvars.iv.next = add nsw i64 %indvars.iv, 1
93  %cmp1 = icmp sle i64 %indvars.iv.next, 0
94  br i1 %cmp1, label %for.end, label %loop
95
96for.end:                                          ; preds = %if.end, %entry
97  ret void
98}
99
100; As long as the test dominates the backedge, we're good
101define void @test3(i64 %start) {
102; CHECK-LABEL: @test3(
103; CHECK-NEXT:  entry:
104; CHECK-NEXT:    br label [[LOOP:%.*]]
105; CHECK:       loop:
106; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
107; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
108; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
109; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[FOR_END:%.*]]
110; CHECK:       backedge:
111; CHECK-NEXT:    call void @foo()
112; CHECK-NEXT:    br i1 false, label [[FOR_END]], label [[LOOP]]
113; CHECK:       for.end:
114; CHECK-NEXT:    ret void
115;
116entry:
117  br label %loop
118
119loop:
120  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
121  %indvars.iv.next = add nsw i64 %indvars.iv, 1
122  %cmp = icmp eq i64 %indvars.iv.next, 25
123  br i1 %cmp, label %backedge, label %for.end
124
125backedge:
126  ; prevent flattening, needed to make sure we're testing what we intend
127  call void @foo()
128  %cmp1 = icmp slt i64 %indvars.iv, -1
129  br i1 %cmp1, label %for.end, label %loop
130
131for.end:                                          ; preds = %if.end, %entry
132  ret void
133}
134
135define void @test3.next(i64 %start) {
136; CHECK-LABEL: @test3.next(
137; CHECK-NEXT:  entry:
138; CHECK-NEXT:    br label [[LOOP:%.*]]
139; CHECK:       loop:
140; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
141; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
142; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
143; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[FOR_END:%.*]]
144; CHECK:       backedge:
145; CHECK-NEXT:    call void @foo()
146; CHECK-NEXT:    br i1 false, label [[FOR_END]], label [[LOOP]]
147; CHECK:       for.end:
148; CHECK-NEXT:    ret void
149;
150entry:
151  br label %loop
152
153loop:
154  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
155  %indvars.iv.next = add nsw i64 %indvars.iv, 1
156  %cmp = icmp eq i64 %indvars.iv.next, 25
157  br i1 %cmp, label %backedge, label %for.end
158
159backedge:
160  ; prevent flattening, needed to make sure we're testing what we intend
161  call void @foo()
162  %cmp1 = icmp slt i64 %indvars.iv.next, 0
163  br i1 %cmp1, label %for.end, label %loop
164
165for.end:                                          ; preds = %if.end, %entry
166  ret void
167}
168
169
170define void @test4(i64 %start) {
171; CHECK-LABEL: @test4(
172; CHECK-NEXT:  entry:
173; CHECK-NEXT:    br label [[LOOP:%.*]]
174; CHECK:       loop:
175; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
176; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
177; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
178; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[FOR_END:%.*]]
179; CHECK:       backedge:
180; CHECK-NEXT:    call void @foo()
181; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[FOR_END]]
182; CHECK:       for.end:
183; CHECK-NEXT:    ret void
184;
185entry:
186  br label %loop
187
188loop:
189  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
190  %indvars.iv.next = add nsw i64 %indvars.iv, 1
191  %cmp = icmp eq i64 %indvars.iv.next, 25
192  br i1 %cmp, label %backedge, label %for.end
193
194backedge:
195  ; prevent flattening, needed to make sure we're testing what we intend
196  call void @foo()
197  %cmp1 = icmp sgt i64 %indvars.iv, -1
198  br i1 %cmp1, label %loop, label %for.end
199
200for.end:                                          ; preds = %if.end, %entry
201  ret void
202}
203
204define void @test4.next(i64 %start) {
205; CHECK-LABEL: @test4.next(
206; CHECK-NEXT:  entry:
207; CHECK-NEXT:    br label [[LOOP:%.*]]
208; CHECK:       loop:
209; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
210; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
211; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
212; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[FOR_END:%.*]]
213; CHECK:       backedge:
214; CHECK-NEXT:    call void @foo()
215; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[FOR_END]]
216; CHECK:       for.end:
217; CHECK-NEXT:    ret void
218;
219entry:
220  br label %loop
221
222loop:
223  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
224  %indvars.iv.next = add nsw i64 %indvars.iv, 1
225  %cmp = icmp eq i64 %indvars.iv.next, 25
226  br i1 %cmp, label %backedge, label %for.end
227
228backedge:
229  ; prevent flattening, needed to make sure we're testing what we intend
230  call void @foo()
231  %cmp1 = icmp sgt i64 %indvars.iv.next, 0
232  br i1 %cmp1, label %loop, label %for.end
233
234for.end:                                          ; preds = %if.end, %entry
235  ret void
236}
237
238define void @test5(i64 %start) {
239; CHECK-LABEL: @test5(
240; CHECK-NEXT:  entry:
241; CHECK-NEXT:    br label [[LOOP:%.*]]
242; CHECK:       loop:
243; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw i64 [[START:%.*]], 1
244; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
245; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
246; CHECK:       backedge:
247; CHECK-NEXT:    call void @foo()
248; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[FOR_END]]
249; CHECK:       for.end:
250; CHECK-NEXT:    ret void
251;
252entry:
253  br label %loop
254
255loop:
256  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
257  %indvars.iv.next = add nuw i64 %indvars.iv, 1
258  %cmp = icmp eq i64 %indvars.iv.next, 25
259  br i1 %cmp, label %backedge, label %for.end
260
261backedge:
262  ; prevent flattening, needed to make sure we're testing what we intend
263  call void @foo()
264  %cmp1 = icmp ugt i64 %indvars.iv, 100
265  br i1 %cmp1, label %loop, label %for.end
266
267for.end:                                          ; preds = %if.end, %entry
268  ret void
269}
270
271define void @test5.next(i64 %start) {
272; CHECK-LABEL: @test5.next(
273; CHECK-NEXT:  entry:
274; CHECK-NEXT:    br label [[LOOP:%.*]]
275; CHECK:       loop:
276; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw i64 [[START:%.*]], 1
277; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
278; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
279; CHECK:       backedge:
280; CHECK-NEXT:    call void @foo()
281; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[FOR_END]]
282; CHECK:       for.end:
283; CHECK-NEXT:    ret void
284;
285entry:
286  br label %loop
287
288loop:
289  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
290  %indvars.iv.next = add nuw i64 %indvars.iv, 1
291  %cmp = icmp eq i64 %indvars.iv.next, 25
292  br i1 %cmp, label %backedge, label %for.end
293
294backedge:
295  ; prevent flattening, needed to make sure we're testing what we intend
296  call void @foo()
297  %cmp1 = icmp ugt i64 %indvars.iv.next, 101
298  br i1 %cmp1, label %loop, label %for.end
299
300for.end:                                          ; preds = %if.end, %entry
301  ret void
302}
303
304
305define void @test6(i64 %start) {
306; CHECK-LABEL: @test6(
307; CHECK-NEXT:  entry:
308; CHECK-NEXT:    br label [[LOOP:%.*]]
309; CHECK:       loop:
310; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw i64 [[START:%.*]], 1
311; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
312; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
313; CHECK:       backedge:
314; CHECK-NEXT:    call void @foo()
315; CHECK-NEXT:    br i1 true, label [[FOR_END]], label [[LOOP]]
316; CHECK:       for.end:
317; CHECK-NEXT:    ret void
318;
319entry:
320  br label %loop
321
322loop:
323  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
324  %indvars.iv.next = add nuw i64 %indvars.iv, 1
325  %cmp = icmp eq i64 %indvars.iv.next, 25
326  br i1 %cmp, label %backedge, label %for.end
327
328backedge:
329  ; prevent flattening, needed to make sure we're testing what we intend
330  call void @foo()
331  %cmp1 = icmp ult i64 %indvars.iv, 100
332  br i1 %cmp1, label %for.end, label %loop
333
334for.end:                                          ; preds = %if.end, %entry
335  ret void
336}
337
338define void @test6.next(i64 %start) {
339; CHECK-LABEL: @test6.next(
340; CHECK-NEXT:  entry:
341; CHECK-NEXT:    br label [[LOOP:%.*]]
342; CHECK:       loop:
343; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw i64 [[START:%.*]], 1
344; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
345; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
346; CHECK:       backedge:
347; CHECK-NEXT:    call void @foo()
348; CHECK-NEXT:    br i1 true, label [[FOR_END]], label [[LOOP]]
349; CHECK:       for.end:
350; CHECK-NEXT:    ret void
351;
352entry:
353  br label %loop
354
355loop:
356  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
357  %indvars.iv.next = add nuw i64 %indvars.iv, 1
358  %cmp = icmp eq i64 %indvars.iv.next, 25
359  br i1 %cmp, label %backedge, label %for.end
360
361backedge:
362  ; prevent flattening, needed to make sure we're testing what we intend
363  call void @foo()
364  %cmp1 = icmp ult i64 %indvars.iv.next, 101
365  br i1 %cmp1, label %for.end, label %loop
366
367for.end:                                          ; preds = %if.end, %entry
368  ret void
369}
370
371define void @test7(i64 %start, ptr %inc_ptr) {
372; CHECK-LABEL: @test7(
373; CHECK-NEXT:  entry:
374; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG0:![0-9]+]]
375; CHECK-NEXT:    [[OK:%.*]] = icmp sge i64 [[INC]], 0
376; CHECK-NEXT:    br i1 [[OK]], label [[LOOP_PREHEADER:%.*]], label [[FOR_END:%.*]]
377; CHECK:       loop.preheader:
378; CHECK-NEXT:    br label [[LOOP:%.*]]
379; CHECK:       loop:
380; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[START:%.*]], -1
381; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END_LOOPEXIT:%.*]], label [[LOOP]]
382; CHECK:       for.end.loopexit:
383; CHECK-NEXT:    br label [[FOR_END]]
384; CHECK:       for.end:
385; CHECK-NEXT:    ret void
386;
387entry:
388  %inc = load i64, ptr %inc_ptr, !range !0
389  %ok = icmp sge i64 %inc, 0
390  br i1 %ok, label %loop, label %for.end
391
392loop:
393  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
394  %indvars.iv.next = add nsw i64 %indvars.iv, %inc
395  %cmp1 = icmp slt i64 %indvars.iv, -1
396  br i1 %cmp1, label %for.end, label %loop
397
398for.end:                                          ; preds = %if.end, %entry
399  ret void
400}
401
402define void @test7.next(i64 %start, ptr %inc_ptr) {
403; CHECK-LABEL: @test7.next(
404; CHECK-NEXT:  entry:
405; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG0]]
406; CHECK-NEXT:    [[OK:%.*]] = icmp sge i64 [[INC]], 0
407; CHECK-NEXT:    br i1 [[OK]], label [[LOOP_PREHEADER:%.*]], label [[FOR_END:%.*]]
408; CHECK:       loop.preheader:
409; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INC]], [[START:%.*]]
410; CHECK-NEXT:    br label [[LOOP:%.*]]
411; CHECK:       loop:
412; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[TMP0]], 0
413; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END_LOOPEXIT:%.*]], label [[LOOP]]
414; CHECK:       for.end.loopexit:
415; CHECK-NEXT:    br label [[FOR_END]]
416; CHECK:       for.end:
417; CHECK-NEXT:    ret void
418;
419entry:
420  %inc = load i64, ptr %inc_ptr, !range !0
421  %ok = icmp sge i64 %inc, 0
422  br i1 %ok, label %loop, label %for.end
423
424loop:
425  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
426  %indvars.iv.next = add nsw i64 %indvars.iv, %inc
427  %cmp1 = icmp slt i64 %indvars.iv.next, 0
428  br i1 %cmp1, label %for.end, label %loop
429
430for.end:                                          ; preds = %if.end, %entry
431  ret void
432}
433
434; Negative test - we can't show that the internal branch executes, so we can't
435; fold the test to a loop invariant one.
436define void @test1_neg(i64 %start) {
437; CHECK-LABEL: @test1_neg(
438; CHECK-NEXT:  entry:
439; CHECK-NEXT:    br label [[LOOP:%.*]]
440; CHECK:       loop:
441; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
442; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
443; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
444; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[SKIP:%.*]]
445; CHECK:       skip:
446; CHECK-NEXT:    call void @foo()
447; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
448; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[BACKEDGE]]
449; CHECK:       backedge:
450; CHECK-NEXT:    call void @foo()
451; CHECK-NEXT:    br label [[LOOP]]
452; CHECK:       for.end:
453; CHECK-NEXT:    ret void
454;
455entry:
456  br label %loop
457
458loop:
459  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
460  %indvars.iv.next = add nsw i64 %indvars.iv, 1
461  %cmp = icmp eq i64 %indvars.iv.next, 25
462  br i1 %cmp, label %backedge, label %skip
463skip:
464  ; prevent flattening, needed to make sure we're testing what we intend
465  call void @foo()
466  %cmp1 = icmp slt i64 %indvars.iv, -1
467  br i1 %cmp1, label %for.end, label %backedge
468backedge:
469  ; prevent flattening, needed to make sure we're testing what we intend
470  call void @foo()
471  br label %loop
472
473for.end:                                          ; preds = %if.end, %entry
474  ret void
475}
476
477; Slightly subtle version of @test4 where the icmp dominates the backedge,
478; but the exit branch doesn't.
479define void @test2_neg(i64 %start) {
480; CHECK-LABEL: @test2_neg(
481; CHECK-NEXT:  entry:
482; CHECK-NEXT:    br label [[LOOP:%.*]]
483; CHECK:       loop:
484; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
485; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
486; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
487; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
488; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[SKIP:%.*]]
489; CHECK:       skip:
490; CHECK-NEXT:    call void @foo()
491; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[BACKEDGE]]
492; CHECK:       backedge:
493; CHECK-NEXT:    call void @foo()
494; CHECK-NEXT:    br label [[LOOP]]
495; CHECK:       for.end:
496; CHECK-NEXT:    ret void
497;
498entry:
499  br label %loop
500
501loop:
502  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
503  %indvars.iv.next = add nsw i64 %indvars.iv, 1
504  %cmp = icmp eq i64 %indvars.iv.next, 25
505  %cmp1 = icmp slt i64 %indvars.iv, -1
506  br i1 %cmp, label %backedge, label %skip
507skip:
508  ; prevent flattening, needed to make sure we're testing what we intend
509  call void @foo()
510  br i1 %cmp1, label %for.end, label %backedge
511backedge:
512  ; prevent flattening, needed to make sure we're testing what we intend
513  call void @foo()
514  br label %loop
515
516for.end:                                          ; preds = %if.end, %entry
517  ret void
518}
519
520; The branch has to exit the loop if the condition is true
521define void @test3_neg(i64 %start) {
522; CHECK-LABEL: @test3_neg(
523; CHECK-NEXT:  entry:
524; CHECK-NEXT:    br label [[LOOP:%.*]]
525; CHECK:       loop:
526; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
527; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
528; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
529; CHECK-NEXT:    br i1 [[CMP1]], label [[LOOP]], label [[FOR_END:%.*]]
530; CHECK:       for.end:
531; CHECK-NEXT:    ret void
532;
533entry:
534  br label %loop
535
536loop:
537  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
538  %indvars.iv.next = add nsw i64 %indvars.iv, 1
539  %cmp1 = icmp slt i64 %indvars.iv, -1
540  br i1 %cmp1, label %loop, label %for.end
541
542for.end:                                          ; preds = %if.end, %entry
543  ret void
544}
545
546define void @test4_neg(i64 %start) {
547; CHECK-LABEL: @test4_neg(
548; CHECK-NEXT:  entry:
549; CHECK-NEXT:    br label [[LOOP:%.*]]
550; CHECK:       loop:
551; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nsw i64 [[START:%.*]], 1
552; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
553; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
554; CHECK:       backedge:
555; CHECK-NEXT:    call void @foo()
556; CHECK-NEXT:    br i1 true, label [[FOR_END]], label [[LOOP]]
557; CHECK:       for.end:
558; CHECK-NEXT:    ret void
559;
560entry:
561  br label %loop
562
563loop:
564  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
565  %indvars.iv.next = add nsw i64 %indvars.iv, 1
566  %cmp = icmp eq i64 %indvars.iv.next, 25
567  br i1 %cmp, label %backedge, label %for.end
568
569backedge:
570  ; prevent flattening, needed to make sure we're testing what we intend
571  call void @foo()
572  %cmp1 = icmp sgt i64 %indvars.iv, -1
573
574; %cmp1 can be made loop invariant only if the branch below goes to
575; %the header when %cmp1 is true.
576  br i1 %cmp1, label %for.end, label %loop
577
578for.end:                                          ; preds = %if.end, %entry
579  ret void
580}
581
582define void @test5_neg(i64 %start, i64 %inc) {
583; CHECK-LABEL: @test5_neg(
584; CHECK-NEXT:  entry:
585; CHECK-NEXT:    br label [[LOOP:%.*]]
586; CHECK:       loop:
587; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
588; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], [[INC:%.*]]
589; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
590; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
591; CHECK:       for.end:
592; CHECK-NEXT:    ret void
593;
594entry:
595  br label %loop
596
597loop:
598  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
599  %indvars.iv.next = add nsw i64 %indvars.iv, %inc
600  %cmp1 = icmp slt i64 %indvars.iv, -1
601  br i1 %cmp1, label %for.end, label %loop
602
603for.end:                                          ; preds = %if.end, %entry
604  ret void
605}
606
607define void @test8(i64 %start, ptr %inc_ptr) {
608; CHECK-LABEL: @test8(
609; CHECK-NEXT:  entry:
610; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG1:![0-9]+]]
611; CHECK-NEXT:    [[OK:%.*]] = icmp sge i64 [[INC]], 0
612; CHECK-NEXT:    br i1 [[OK]], label [[LOOP_PREHEADER:%.*]], label [[FOR_END:%.*]]
613; CHECK:       loop.preheader:
614; CHECK-NEXT:    br label [[LOOP:%.*]]
615; CHECK:       loop:
616; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ [[START:%.*]], [[LOOP_PREHEADER]] ]
617; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], [[INC]]
618; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
619; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END_LOOPEXIT:%.*]], label [[LOOP]]
620; CHECK:       for.end.loopexit:
621; CHECK-NEXT:    br label [[FOR_END]]
622; CHECK:       for.end:
623; CHECK-NEXT:    ret void
624;
625entry:
626  %inc = load i64, ptr %inc_ptr, !range !1
627  %ok = icmp sge i64 %inc, 0
628  br i1 %ok, label %loop, label %for.end
629
630loop:
631  %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
632  %indvars.iv.next = add nsw i64 %indvars.iv, %inc
633  %cmp1 = icmp slt i64 %indvars.iv, -1
634  br i1 %cmp1, label %for.end, label %loop
635
636for.end:                                          ; preds = %if.end, %entry
637  ret void
638}
639
640; check to handle loops without preheaders, but invariant operands
641; (we handle this today by inserting a preheader)
642define void @test9(i1 %cnd, i64 %start) {
643; CHECK-LABEL: @test9(
644; CHECK-NEXT:  entry:
645; CHECK-NEXT:    br i1 [[CND:%.*]], label [[ENTRY1:%.*]], label [[ENTRY2:%.*]]
646; CHECK:       entry1:
647; CHECK-NEXT:    br label [[LOOP_PREHEADER:%.*]]
648; CHECK:       entry2:
649; CHECK-NEXT:    br label [[LOOP_PREHEADER]]
650; CHECK:       loop.preheader:
651; CHECK-NEXT:    br label [[LOOP:%.*]]
652; CHECK:       loop:
653; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[START:%.*]], -1
654; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
655; CHECK:       for.end:
656; CHECK-NEXT:    ret void
657;
658entry:
659  br i1 %cnd, label %entry1, label %entry2
660entry1:
661  br label %loop
662entry2:
663  br label %loop
664loop:
665  %indvars.iv = phi i64 [ %start, %entry1 ],[ %start, %entry2 ], [ %indvars.iv.next, %loop ]
666  %indvars.iv.next = add nsw i64 %indvars.iv, 1
667  %cmp1 = icmp slt i64 %indvars.iv, -1
668  br i1 %cmp1, label %for.end, label %loop
669
670for.end:                                          ; preds = %if.end, %entry
671  ret void
672}
673
674declare void @use(i1 %x)
675
676; check that we handle conditions with loop invariant operands which
677; *aren't* in the header - this is a very rare and fragile case where
678; we have a "loop" which is known to run exactly one iteration but
679; haven't yet simplified the uses of the IV
680define void @test10() {
681; CHECK-LABEL: @test10(
682; CHECK-NEXT:  entry:
683; CHECK-NEXT:    br label [[LOOP:%.*]]
684; CHECK:       loop:
685; CHECK-NEXT:    br i1 false, label [[LEFT:%.*]], label [[RIGHT:%.*]]
686; CHECK:       left:
687; CHECK-NEXT:    br label [[LATCH:%.*]]
688; CHECK:       right:
689; CHECK-NEXT:    br label [[LATCH]]
690; CHECK:       latch:
691; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 -1, undef
692; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[LOOP]]
693; CHECK:       exit:
694; CHECK-NEXT:    [[CMP_LCSSA:%.*]] = phi i1 [ [[CMP]], [[LATCH]] ]
695; CHECK-NEXT:    call void @use(i1 [[CMP_LCSSA]])
696; CHECK-NEXT:    ret void
697;
698entry:
699  br label %loop
700
701loop:
702  %phi1 = phi i32 [ %phi2, %latch ], [ 0, %entry ]
703  %dec = add i32 %phi1, -1
704  br i1 false, label %left, label %right
705
706left:
707  br label %latch
708
709right:
710  br label %latch
711
712latch:
713  %phi2 = phi i32 [ %phi1, %left ], [ %dec, %right ]
714  %cmp = icmp slt i32 %phi2, undef
715  br i1 true, label %exit, label %loop
716
717exit:
718  call void @use(i1 %cmp)
719  ret void
720}
721
722; check that we can figure out that iv.next > 1 from the facts that iv >= 0 and
723; iv.start != 0.
724define void @test11(ptr %inc_ptr) {
725; CHECK-LABEL: @test11(
726; CHECK-NEXT:  entry:
727; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG0]]
728; CHECK-NEXT:    [[NE_COND:%.*]] = icmp ne i64 [[INC]], 0
729; CHECK-NEXT:    br i1 [[NE_COND]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
730; CHECK:       loop.preheader:
731; CHECK-NEXT:    br label [[LOOP:%.*]]
732; CHECK:       loop:
733; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[INC]], [[LOOP_PREHEADER]] ]
734; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
735; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
736; CHECK:       if.true:
737; CHECK-NEXT:    br label [[BACKEDGE]]
738; CHECK:       if.false:
739; CHECK-NEXT:    br label [[BACKEDGE]]
740; CHECK:       backedge:
741; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], 201
742; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
743; CHECK:       exit.loopexit:
744; CHECK-NEXT:    br label [[EXIT]]
745; CHECK:       exit:
746; CHECK-NEXT:    ret void
747;
748entry:
749  %inc = load i64, ptr %inc_ptr, !range !0
750  %ne.cond = icmp ne i64 %inc, 0
751  br i1 %ne.cond, label %loop, label %exit
752
753loop:
754  %iv = phi i64 [ %inc, %entry ], [ %iv.next, %backedge ]
755  %iv.next = add i64 %iv, 1
756  %brcond = icmp sgt i64 %iv.next, 1
757  br i1 %brcond, label %if.true, label %if.false
758
759if.true:
760  br label %backedge
761
762if.false:
763  br label %backedge
764
765backedge:
766  %loopcond = icmp slt i64 %iv, 200
767  br i1 %loopcond, label %loop, label %exit
768
769exit:
770  ret void
771}
772
773; check that we can prove that a recurrency is greater than another recurrency
774; in the same loop, with the same step, and with smaller starting value.
775define void @test12(ptr %inc_ptr) {
776; CHECK-LABEL: @test12(
777; CHECK-NEXT:  entry:
778; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG0]]
779; CHECK-NEXT:    br label [[LOOP:%.*]]
780; CHECK:       loop:
781; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[INC]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
782; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
783; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
784; CHECK:       if.true:
785; CHECK-NEXT:    br label [[BACKEDGE]]
786; CHECK:       if.false:
787; CHECK-NEXT:    br label [[BACKEDGE]]
788; CHECK:       backedge:
789; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], 201
790; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
791; CHECK:       exit:
792; CHECK-NEXT:    ret void
793;
794entry:
795  %inc = load i64, ptr %inc_ptr, !range !0
796  %inc.minus.1 = sub i64 %inc, 1
797  br label %loop
798
799loop:
800  %iv = phi i64 [ %inc, %entry ], [ %iv.next, %backedge ]
801  %iv.minus.1 = phi i64 [ %inc.minus.1, %entry ], [ %iv.minus.1.next, %backedge ]
802  %iv.next = add i64 %iv, 1
803  %iv.minus.1.next = add i64 %iv.minus.1, 1
804  %brcond = icmp sgt i64 %iv.next, %iv.minus.1.next
805  br i1 %brcond, label %if.true, label %if.false
806
807if.true:
808  br label %backedge
809
810if.false:
811  br label %backedge
812
813backedge:
814  %loopcond = icmp slt i64 %iv, 200
815  br i1 %loopcond, label %loop, label %exit
816
817exit:
818  ret void
819}
820
821!0 = !{i64 0, i64 100}
822!1 = !{i64 -1, i64 100}
823
824declare void @foo()
825