1; RUN: opt -indvars -S < %s | FileCheck %s
2
3target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
4
5@X = external global [0 x double]
6
7; Indvars should be able to simplify simple comparisons involving
8; induction variables.
9
10; CHECK-LABEL: @foo(
11; CHECK: %cond = and i1 %tobool.not, true
12
13define void @foo(i64 %n, i32* nocapture %p) nounwind {
14entry:
15  %cmp9 = icmp sgt i64 %n, 0
16  br i1 %cmp9, label %pre, label %return
17
18pre:
19  %t3 = load i32, i32* %p
20  %tobool.not = icmp ne i32 %t3, 0
21  br label %loop
22
23loop:
24  %i = phi i64 [ 0, %pre ], [ %inc, %for.inc ]
25  %cmp6 = icmp slt i64 %i, %n
26  %cond = and i1 %tobool.not, %cmp6
27  br i1 %cond, label %if.then, label %for.inc
28
29if.then:
30  %arrayidx = getelementptr [0 x double], [0 x double]* @X, i64 0, i64 %i
31  store double 3.200000e+00, double* %arrayidx
32  br label %for.inc
33
34for.inc:
35  %inc = add nsw i64 %i, 1
36  %exitcond = icmp sge i64 %inc, %n
37  br i1 %exitcond, label %return, label %loop
38
39return:
40  ret void
41}
42
43; Don't eliminate an icmp that's contributing to the loop exit test though.
44
45; CHECK-LABEL: @_ZNK4llvm5APInt3ultERKS0_(
46; CHECK: %tmp99 = icmp sgt i32 %i, -1
47
48define i32 @_ZNK4llvm5APInt3ultERKS0_(i32 %tmp2.i1, i64** %tmp65, i64** %tmp73, i64** %tmp82, i64** %tmp90) {
49entry:
50  br label %bb18
51
52bb13:
53  %tmp66 = load i64*, i64** %tmp65, align 4
54  %tmp68 = getelementptr inbounds i64, i64* %tmp66, i32 %i
55  %tmp69 = load i64, i64* %tmp68, align 4
56  %tmp74 = load i64*, i64** %tmp73, align 4
57  %tmp76 = getelementptr inbounds i64, i64* %tmp74, i32 %i
58  %tmp77 = load i64, i64* %tmp76, align 4
59  %tmp78 = icmp ugt i64 %tmp69, %tmp77
60  br i1 %tmp78, label %bb20.loopexit, label %bb15
61
62bb15:
63  %tmp83 = load i64*, i64** %tmp82, align 4
64  %tmp85 = getelementptr inbounds i64, i64* %tmp83, i32 %i
65  %tmp86 = load i64, i64* %tmp85, align 4
66  %tmp91 = load i64*, i64** %tmp90, align 4
67  %tmp93 = getelementptr inbounds i64, i64* %tmp91, i32 %i
68  %tmp94 = load i64, i64* %tmp93, align 4
69  %tmp95 = icmp ult i64 %tmp86, %tmp94
70  br i1 %tmp95, label %bb20.loopexit, label %bb17
71
72bb17:
73  %tmp97 = add nsw i32 %i, -1
74  br label %bb18
75
76bb18:
77  %i = phi i32 [ %tmp2.i1, %entry ], [ %tmp97, %bb17 ]
78  %tmp99 = icmp sgt i32 %i, -1
79  br i1 %tmp99, label %bb13, label %bb20.loopexit
80
81bb20.loopexit:
82  %tmp.0.ph = phi i32 [ 0, %bb18 ], [ 1, %bb15 ], [ 0, %bb13 ]
83  ret i32 %tmp.0.ph
84}
85
86; Indvars should eliminate the icmp here.
87
88; CHECK-LABEL: @func_10(
89; CHECK-NOT: icmp
90; CHECK: ret void
91
92define void @func_10() nounwind {
93entry:
94  br label %loop
95
96loop:
97  %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
98  %t0 = icmp slt i32 %i, 0
99  %t1 = zext i1 %t0 to i32
100  %t2 = add i32 %t1, %i
101  %u3 = zext i32 %t2 to i64
102  store i64 %u3, i64* null
103  %i.next = add i32 %i, 1
104  br i1 undef, label %loop, label %return
105
106return:
107  ret void
108}
109
110; PR14432
111; Indvars should not turn the second loop into an infinite one.
112
113; CHECK-LABEL: @func_11(
114; CHECK: %tmp5 = icmp ult i32 %__key6.0, 10
115; CHECK-NOT: br i1 true, label %noassert68, label %unrolledend
116
117define i32 @func_11() nounwind uwtable {
118entry:
119  br label %forcond
120
121forcond:                                          ; preds = %noassert, %entry
122  %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
123  %tmp5 = icmp slt i32 %__key6.0, 10
124  br i1 %tmp5, label %noassert, label %forcond38.preheader
125
126forcond38.preheader:                              ; preds = %forcond
127  br label %forcond38
128
129noassert:                                         ; preds = %forbody
130  %tmp13 = sdiv i32 -32768, %__key6.0
131  %tmp2936 = shl i32 %tmp13, 24
132  %sext23 = shl i32 %tmp13, 24
133  %tmp32 = icmp eq i32 %tmp2936, %sext23
134  %tmp37 = add i32 %__key6.0, 1
135  br i1 %tmp32, label %forcond, label %assert33
136
137assert33:                                         ; preds = %noassert
138  tail call void @llvm.trap()
139  unreachable
140
141forcond38:                                        ; preds = %noassert68, %forcond38.preheader
142  %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ]
143  %tmp46 = icmp slt i32 %__key8.0, 10
144  br i1 %tmp46, label %noassert68, label %unrolledend
145
146noassert68:                                       ; preds = %forbody39
147  %tmp57 = sdiv i32 -32768, %__key8.0
148  %sext34 = shl i32 %tmp57, 16
149  %sext21 = shl i32 %tmp57, 16
150  %tmp76 = icmp eq i32 %sext34, %sext21
151  %tmp81 = add i32 %__key8.0, 1
152  br i1 %tmp76, label %forcond38, label %assert77
153
154assert77:                                         ; preds = %noassert68
155  tail call void @llvm.trap()
156  unreachable
157
158unrolledend:                                      ; preds = %forcond38
159  ret i32 0
160}
161
162declare void @llvm.trap() noreturn nounwind
163
164; In this case the second loop only has a single iteration, fold the header away
165; CHECK-LABEL: @func_12(
166; CHECK: %tmp5 = icmp ult i32 %__key6.0, 10
167; CHECK: br i1 true, label %noassert68, label %unrolledend
168define i32 @func_12() nounwind uwtable {
169entry:
170  br label %forcond
171
172forcond:                                          ; preds = %noassert, %entry
173  %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
174  %tmp5 = icmp slt i32 %__key6.0, 10
175  br i1 %tmp5, label %noassert, label %forcond38.preheader
176
177forcond38.preheader:                              ; preds = %forcond
178  br label %forcond38
179
180noassert:                                         ; preds = %forbody
181  %tmp13 = sdiv i32 -32768, %__key6.0
182  %tmp2936 = shl i32 %tmp13, 24
183  %sext23 = shl i32 %tmp13, 24
184  %tmp32 = icmp eq i32 %tmp2936, %sext23
185  %tmp37 = add i32 %__key6.0, 1
186  br i1 %tmp32, label %forcond, label %assert33
187
188assert33:                                         ; preds = %noassert
189  tail call void @llvm.trap()
190  unreachable
191
192forcond38:                                        ; preds = %noassert68, %forcond38.preheader
193  %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ]
194  %tmp46 = icmp slt i32 %__key8.0, 10
195  br i1 %tmp46, label %noassert68, label %unrolledend
196
197noassert68:                                       ; preds = %forbody39
198  %tmp57 = sdiv i32 -32768, %__key8.0
199  %sext34 = shl i32 %tmp57, 16
200  %sext21 = shl i32 %tmp57, 16
201  %tmp76 = icmp ne i32 %sext34, %sext21
202  %tmp81 = add i32 %__key8.0, 1
203  br i1 %tmp76, label %forcond38, label %assert77
204
205assert77:                                         ; preds = %noassert68
206  tail call void @llvm.trap()
207  unreachable
208
209unrolledend:                                      ; preds = %forcond38
210  ret i32 0
211}
212
213declare void @side_effect()
214
215define void @func_13(i32* %len.ptr) {
216; CHECK-LABEL: @func_13(
217 entry:
218  %len = load i32, i32* %len.ptr, !range !0
219  %len.sub.1 = add i32 %len, -1
220  %len.is.zero = icmp eq i32 %len, 0
221  br i1 %len.is.zero, label %leave, label %loop
222
223 loop:
224; CHECK: loop:
225  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
226  call void @side_effect()
227  %iv.inc = add i32 %iv, 1
228  %iv.cmp = icmp ult i32 %iv, %len
229  br i1 %iv.cmp, label %be, label %leave
230; CHECK: br i1 true, label %be, label %leave
231
232 be:
233  call void @side_effect()
234  %be.cond = icmp ult i32 %iv, %len.sub.1
235  br i1 %be.cond, label %loop, label %leave
236
237 leave:
238  ret void
239}
240
241define void @func_14(i32* %len.ptr) {
242; CHECK-LABEL: @func_14(
243 entry:
244  %len = load i32, i32* %len.ptr, !range !0
245  %len.sub.1 = add i32 %len, -1
246  %len.is.zero = icmp eq i32 %len, 0
247  %len.is.int_min = icmp eq i32 %len, 2147483648
248  %no.entry = or i1 %len.is.zero, %len.is.int_min
249  br i1 %no.entry, label %leave, label %loop
250
251 loop:
252; CHECK: loop:
253  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
254  call void @side_effect()
255  %iv.inc = add i32 %iv, 1
256  %iv.cmp = icmp slt i32 %iv, %len
257  br i1 %iv.cmp, label %be, label %leave
258; CHECK: br i1 true, label %be, label %leave
259
260 be:
261  call void @side_effect()
262  %be.cond = icmp slt i32 %iv, %len.sub.1
263  br i1 %be.cond, label %loop, label %leave
264
265 leave:
266  ret void
267}
268
269define void @func_15(i32* %len.ptr) {
270; CHECK-LABEL: @func_15(
271 entry:
272  %len = load i32, i32* %len.ptr, !range !0
273  %len.add.1 = add i32 %len, 1
274  %len.add.1.is.zero = icmp eq i32 %len.add.1, 0
275  br i1 %len.add.1.is.zero, label %leave, label %loop
276
277 loop:
278; CHECK: loop:
279  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
280  call void @side_effect()
281  %iv.inc = add i32 %iv, 1
282  %iv.cmp = icmp ult i32 %iv, %len.add.1
283  br i1 %iv.cmp, label %be, label %leave
284; CHECK: br i1 true, label %be, label %leave
285
286 be:
287  call void @side_effect()
288  %be.cond = icmp ult i32 %iv, %len
289  br i1 %be.cond, label %loop, label %leave
290
291 leave:
292  ret void
293}
294
295define void @func_16(i32* %len.ptr) {
296; CHECK-LABEL: @func_16(
297 entry:
298  %len = load i32, i32* %len.ptr, !range !0
299  %len.add.5 = add i32 %len, 5
300  %entry.cond.0 = icmp slt i32 %len, 2147483643
301  %entry.cond.1 = icmp slt i32 4, %len.add.5
302  %entry.cond = and i1 %entry.cond.0, %entry.cond.1
303  br i1 %entry.cond, label %loop, label %leave
304
305 loop:
306; CHECK: loop:
307  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
308  call void @side_effect()
309  %iv.inc = add i32 %iv, 1
310  %iv.add.4 = add i32 %iv, 4
311  %iv.cmp = icmp slt i32 %iv.add.4, %len.add.5
312  br i1 %iv.cmp, label %be, label %leave
313; CHECK: br i1 true, label %be, label %leave
314
315 be:
316  call void @side_effect()
317  %be.cond = icmp slt i32 %iv, %len
318  br i1 %be.cond, label %loop, label %leave
319
320 leave:
321  ret void
322}
323
324define void @func_17(i32* %len.ptr) {
325; CHECK-LABEL: @func_17(
326 entry:
327  %len = load i32, i32* %len.ptr
328  %len.add.5 = add i32 %len, -5
329  %entry.cond.0 = icmp slt i32 %len, 2147483653 ;; 2147483653 == INT_MIN - (-5)
330  %entry.cond.1 = icmp slt i32 -6, %len.add.5
331  %entry.cond = and i1 %entry.cond.0, %entry.cond.1
332  br i1 %entry.cond, label %loop, label %leave
333
334 loop:
335; CHECK: loop:
336  %iv.2 = phi i32 [ 0, %entry ], [ %iv.2.inc, %be ]
337  %iv = phi i32 [ -6, %entry ], [ %iv.inc, %be ]
338  call void @side_effect()
339  %iv.inc = add i32 %iv, 1
340  %iv.2.inc = add i32 %iv.2, 1
341  %iv.cmp = icmp slt i32 %iv, %len.add.5
342
343; Deduces {-5,+,1} s< (-5 + %len) from {0,+,1} < %len
344; since %len s< INT_MIN - (-5) from the entry condition
345
346; CHECK: br i1 true, label %be, label %leave
347  br i1 %iv.cmp, label %be, label %leave
348
349 be:
350; CHECK: be:
351  call void @side_effect()
352  %be.cond = icmp slt i32 %iv.2, %len
353  br i1 %be.cond, label %loop, label %leave
354
355 leave:
356  ret void
357}
358
359define i1 @func_18(i16* %tmp20, i32* %len.addr) {
360; CHECK-LABEL: @func_18(
361entry:
362  %len = load i32, i32* %len.addr, !range !0
363  %tmp18 = icmp eq i32 %len, 0
364  br i1 %tmp18, label %bb2, label %bb0.preheader
365
366bb0.preheader:
367  br label %bb0
368
369bb0:
370; CHECK: bb0:
371  %var_0.in = phi i32 [ %var_0, %bb1 ], [ %len, %bb0.preheader ]
372  %var_1 = phi i32 [ %tmp30, %bb1 ], [ 0, %bb0.preheader ]
373  %var_0 = add nsw i32 %var_0.in, -1
374  %tmp23 = icmp ult i32 %var_1, %len
375; CHECK: br i1 true, label %stay, label %bb2.loopexit
376  br i1 %tmp23, label %stay, label %bb2
377
378stay:
379; CHECK: stay:
380  %tmp25 = getelementptr inbounds i16, i16* %tmp20, i32 %var_1
381  %tmp26 = load i16, i16* %tmp25
382  %tmp29 = icmp eq i16 %tmp26, 0
383  br i1 %tmp29, label %bb1, label %bb2
384
385bb1:
386  %tmp30 = add i32 %var_1, 1
387  %tmp31 = icmp eq i32 %var_0, 0
388  br i1 %tmp31, label %bb3, label %bb0
389
390bb2:
391  ret i1 false
392
393bb3:
394  ret i1 true
395}
396
397define void @func_19(i32* %length.ptr) {
398; CHECK-LABEL: @func_19(
399 entry:
400  %length = load i32, i32* %length.ptr, !range !0
401  %length.is.nonzero = icmp ne i32 %length, 0
402  br i1 %length.is.nonzero, label %loop, label %leave
403
404 loop:
405; CHECK: loop:
406  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
407  %iv.inc = add i32 %iv, 1
408  %range.check = icmp ult i32 %iv, %length
409  br i1 %range.check, label %be, label %leave
410; CHECK:   br i1 true, label %be, label %leave.loopexit
411; CHECK: be:
412
413 be:
414  call void @side_effect()
415  %be.cond = icmp slt i32 %iv.inc, %length
416  br i1 %be.cond, label %loop, label %leave
417
418 leave:
419  ret void
420}
421
422define void @func_20(i32* %length.ptr) {
423; Like @func_19, but %length is no longer provably positive, so
424; %range.check cannot be proved to be always true.
425
426; CHECK-LABEL: @func_20(
427 entry:
428  %length = load i32, i32* %length.ptr
429  %length.is.nonzero = icmp ne i32 %length, 0
430  br i1 %length.is.nonzero, label %loop, label %leave
431
432 loop:
433; CHECK: loop:
434  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
435  %iv.inc = add i32 %iv, 1
436  %range.check = icmp ult i32 %iv, %length
437  br i1 %range.check, label %be, label %leave
438; CHECK:   br i1 %range.check, label %be, label %leave.loopexit
439; CHECK: be:
440
441 be:
442  call void @side_effect()
443  %be.cond = icmp slt i32 %iv.inc, %length
444  br i1 %be.cond, label %loop, label %leave
445
446 leave:
447  ret void
448}
449
450define void @func_21(i32* %length.ptr) {
451; CHECK-LABEL: @func_21(
452
453; This checks that the backedge condition, (I + 1) < Length - 1 implies
454; (I + 1) < Length
455 entry:
456  %length = load i32, i32* %length.ptr, !range !0
457  %lim = sub i32 %length, 1
458  %entry.cond = icmp sgt i32 %length, 1
459  br i1 %entry.cond, label %loop, label %leave
460
461 loop:
462; CHECK: loop:
463  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
464  %iv.inc = add i32 %iv, 1
465  %range.check = icmp slt i32 %iv, %length
466  br i1 %range.check, label %be, label %leave
467; CHECK:   br i1 true, label %be, label %leave.loopexit
468; CHECK: be:
469
470 be:
471  call void @side_effect()
472  %be.cond = icmp slt i32 %iv.inc, %lim
473  br i1 %be.cond, label %loop, label %leave
474
475 leave:
476  ret void
477}
478
479define void @func_22(i32* %length.ptr) {
480; CHECK-LABEL: @func_22(
481
482; This checks that the backedge condition, (I + 1) < Length - 1 implies
483; (I + 1) < Length
484 entry:
485  %length = load i32, i32* %length.ptr, !range !0
486  %lim = sub i32 %length, 1
487  %entry.cond = icmp sgt i32 %length, 1
488  br i1 %entry.cond, label %loop, label %leave
489
490 loop:
491; CHECK: loop:
492  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
493  %iv.inc = add i32 %iv, 1
494  %range.check = icmp sle i32 %iv, %length
495  br i1 %range.check, label %be, label %leave
496; CHECK:   br i1 true, label %be, label %leave.loopexit
497; CHECK: be:
498
499 be:
500  call void @side_effect()
501  %be.cond = icmp sle i32 %iv.inc, %lim
502  br i1 %be.cond, label %loop, label %leave
503
504 leave:
505  ret void
506}
507
508define void @func_23(i32* %length.ptr) {
509; CHECK-LABEL: @func_23(
510 entry:
511  %length = load i32, i32* %length.ptr, !range !0
512  %entry.cond = icmp ult i32 4, %length
513  br i1 %entry.cond, label %loop, label %leave
514
515 loop:
516; CHECK: loop:
517  %iv = phi i32 [ 4, %entry ], [ %iv.inc, %be ]
518  %iv.inc = add i32 %iv, 1
519  %range.check = icmp slt i32 %iv, %length
520  br i1 %range.check, label %be, label %leave
521; CHECK:   br i1 true, label %be, label %leave.loopexit
522; CHECK: be:
523
524 be:
525  call void @side_effect()
526  %be.cond = icmp slt i32 %iv.inc, %length
527  br i1 %be.cond, label %loop, label %leave
528
529 leave:
530  ret void
531}
532
533define void @func_24(i32* %init.ptr) {
534; CHECK-LABEL: @func_24(
535 entry:
536  %init = load i32, i32* %init.ptr, !range !0
537  %entry.cond = icmp ugt i32 %init, 4
538  br i1 %entry.cond, label %loop, label %leave
539
540 loop:
541; CHECK: loop:
542  %iv = phi i32 [ %init, %entry ], [ %iv.dec, %be ]
543  %iv.dec = add i32 %iv, -1
544  %range.check = icmp sgt i32 %iv, 4
545  br i1 %range.check, label %be, label %leave
546; CHECK:   br i1 true, label %be, label %leave.loopexit
547; CHECK: be:
548
549 be:
550  call void @side_effect()
551  %be.cond = icmp sgt i32 %iv.dec, 4
552  br i1 %be.cond, label %loop, label %leave
553
554 leave:
555  ret void
556}
557
558
559!0 = !{i32 0, i32 2147483647}
560