1 ; RUN: opt -indvars -S < %s | FileCheck %s
3 target 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"
5 @X = external global [0 x double]
7 ; Indvars should be able to simplify simple comparisons involving
11 ; CHECK: %cond = and i1 %tobool.not, true
13 define void @foo(i64 %n, i32* nocapture %p) nounwind {
15 %cmp9 = icmp sgt i64 %n, 0
16 br i1 %cmp9, label %pre, label %return
19 %t3 = load i32, i32* %p
20 %tobool.not = icmp ne i32 %t3, 0
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
30 %arrayidx = getelementptr [0 x double], [0 x double]* @X, i64 0, i64 %i
31 store double 3.200000e+00, double* %arrayidx
35 %inc = add nsw i64 %i, 1
36 %exitcond = icmp sge i64 %inc, %n
37 br i1 %exitcond, label %return, label %loop
43 ; Don't eliminate an icmp that's contributing to the loop exit test though.
45 ; CHECK-LABEL: @_ZNK4llvm5APInt3ultERKS0_(
46 ; CHECK: %tmp99 = icmp sgt i32 %i, -1
48 define i32 @_ZNK4llvm5APInt3ultERKS0_(i32 %tmp2.i1, i64** %tmp65, i64** %tmp73, i64** %tmp82, i64** %tmp90) {
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
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
73 %tmp97 = add nsw i32 %i, -1
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
82 %tmp.0.ph = phi i32 [ 0, %bb18 ], [ 1, %bb15 ], [ 0, %bb13 ]
86 ; Indvars should eliminate the icmp here.
88 ; CHECK-LABEL: @func_10(
92 define void @func_10() nounwind {
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
111 ; Indvars should not turn the second loop into an infinite one.
113 ; CHECK-LABEL: @func_11(
114 ; CHECK: %tmp5 = icmp slt i32 %__key6.0, 10
115 ; CHECK-NOT: br i1 true, label %noassert68, label %unrolledend
117 define i32 @func_11() nounwind uwtable {
121 forcond: ; 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
126 forcond38.preheader: ; preds = %forcond
129 noassert: ; 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
137 assert33: ; preds = %noassert
138 tail call void @llvm.trap()
141 forcond38: ; 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
146 noassert68: ; 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
154 assert77: ; preds = %noassert68
155 tail call void @llvm.trap()
158 unrolledend: ; preds = %forcond38
162 declare void @llvm.trap() noreturn nounwind
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 slt i32 %__key6.0, 10
167 ; CHECK: br i1 true, label %noassert68, label %unrolledend
168 define i32 @func_12() nounwind uwtable {
172 forcond: ; 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
177 forcond38.preheader: ; preds = %forcond
180 noassert: ; 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
188 assert33: ; preds = %noassert
189 tail call void @llvm.trap()
192 forcond38: ; 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
197 noassert68: ; 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
205 assert77: ; preds = %noassert68
206 tail call void @llvm.trap()
209 unrolledend: ; preds = %forcond38
213 declare void @side_effect()
215 define void @func_13(i32* %len.ptr) {
216 ; CHECK-LABEL: @func_13(
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
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
233 call void @side_effect()
234 %be.cond = icmp ult i32 %iv, %len.sub.1
235 br i1 %be.cond, label %loop, label %leave
241 define void @func_14(i32* %len.ptr) {
242 ; CHECK-LABEL: @func_14(
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
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
261 call void @side_effect()
262 %be.cond = icmp slt i32 %iv, %len.sub.1
263 br i1 %be.cond, label %loop, label %leave
269 define void @func_15(i32* %len.ptr) {
270 ; CHECK-LABEL: @func_15(
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
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
287 call void @side_effect()
288 %be.cond = icmp ult i32 %iv, %len
289 br i1 %be.cond, label %loop, label %leave
295 define void @func_16(i32* %len.ptr) {
296 ; CHECK-LABEL: @func_16(
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
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
316 call void @side_effect()
317 %be.cond = icmp slt i32 %iv, %len
318 br i1 %be.cond, label %loop, label %leave
324 define void @func_17(i32* %len.ptr) {
325 ; CHECK-LABEL: @func_17(
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
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
343 ; Deduces {-5,+,1} s< (-5 + %len) from {0,+,1} < %len
344 ; since %len s< INT_MIN - (-5) from the entry condition
346 ; CHECK: br i1 true, label %be, label %leave
347 br i1 %iv.cmp, label %be, label %leave
351 call void @side_effect()
352 %be.cond = icmp slt i32 %iv.2, %len
353 br i1 %be.cond, label %loop, label %leave
359 define i1 @func_18(i16* %tmp20, i32* %len.addr) {
360 ; CHECK-LABEL: @func_18(
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
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
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
386 %tmp30 = add i32 %var_1, 1
387 %tmp31 = icmp eq i32 %var_0, 0
388 br i1 %tmp31, label %bb3, label %bb0
397 define void @func_19(i32* %length.ptr) {
398 ; CHECK-LABEL: @func_19(
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
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
414 call void @side_effect()
415 %be.cond = icmp slt i32 %iv.inc, %length
416 br i1 %be.cond, label %loop, label %leave
422 define 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.
426 ; CHECK-LABEL: @func_20(
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
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
442 call void @side_effect()
443 %be.cond = icmp slt i32 %iv.inc, %length
444 br i1 %be.cond, label %loop, label %leave
450 define void @func_21(i32* %length.ptr, i32 %init) {
451 ; Like @func_19, but it is no longer possible to prove %iv's start
452 ; value is positive without doing some control flow analysis.
454 ; CHECK-LABEL: @func_21(
456 %length = load i32, i32* %length.ptr, !range !0
457 %length.is.nonzero = icmp ne i32 %length, 0
458 %init.is.positive = icmp sgt i32 %init, 0
459 %entry.cond = and i1 %length.is.nonzero, %init.is.positive
460 br i1 %length.is.nonzero, label %loop, label %leave
464 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
465 %iv.inc = add i32 %iv, 1
466 %range.check = icmp ult i32 %iv, %length
467 br i1 %range.check, label %be, label %leave
468 ; CHECK: br i1 true, label %be, label %leave.loopexit
472 call void @side_effect()
473 %be.cond = icmp slt i32 %iv.inc, %length
474 br i1 %be.cond, label %loop, label %leave
480 define void @func_22(i32* %length.ptr) {
481 ; CHECK-LABEL: @func_22(
483 ; This checks that the backedge condition, (I + 1) < Length - 1 implies
486 %length = load i32, i32* %length.ptr, !range !0
487 %lim = sub i32 %length, 1
488 %entry.cond = icmp sgt i32 %length, 1
489 br i1 %entry.cond, label %loop, label %leave
493 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
494 %iv.inc = add i32 %iv, 1
495 %range.check = icmp slt i32 %iv, %length
496 br i1 %range.check, label %be, label %leave
497 ; CHECK: br i1 true, label %be, label %leave.loopexit
501 call void @side_effect()
502 %be.cond = icmp slt i32 %iv.inc, %lim
503 br i1 %be.cond, label %loop, label %leave
509 define void @func_23(i32* %length.ptr) {
510 ; CHECK-LABEL: @func_23(
512 ; This checks that the backedge condition, (I + 1) < Length - 1 implies
515 %length = load i32, i32* %length.ptr, !range !0
516 %lim = sub i32 %length, 1
517 %entry.cond = icmp sgt i32 %length, 1
518 br i1 %entry.cond, label %loop, label %leave
522 %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
523 %iv.inc = add i32 %iv, 1
524 %range.check = icmp sle i32 %iv, %length
525 br i1 %range.check, label %be, label %leave
526 ; CHECK: br i1 true, label %be, label %leave.loopexit
530 call void @side_effect()
531 %be.cond = icmp sle i32 %iv.inc, %lim
532 br i1 %be.cond, label %loop, label %leave
538 define void @func_24(i32* %length.ptr) {
539 ; CHECK-LABEL: @func_24(
541 %length = load i32, i32* %length.ptr, !range !0
542 %entry.cond = icmp ult i32 4, %length
543 br i1 %entry.cond, label %loop, label %leave
547 %iv = phi i32 [ 4, %entry ], [ %iv.inc, %be ]
548 %iv.inc = add i32 %iv, 1
549 %range.check = icmp slt i32 %iv, %length
550 br i1 %range.check, label %be, label %leave
551 ; CHECK: br i1 true, label %be, label %leave.loopexit
555 call void @side_effect()
556 %be.cond = icmp slt i32 %iv.inc, %length
557 br i1 %be.cond, label %loop, label %leave
563 define void @func_25(i32* %init.ptr) {
564 ; CHECK-LABEL: @func_25(
566 %init = load i32, i32* %init.ptr, !range !0
567 %entry.cond = icmp ugt i32 %init, 4
568 br i1 %entry.cond, label %loop, label %leave
572 %iv = phi i32 [ %init, %entry ], [ %iv.dec, %be ]
573 %iv.dec = add i32 %iv, -1
574 %range.check = icmp sgt i32 %iv, 4
575 br i1 %range.check, label %be, label %leave
576 ; CHECK: br i1 true, label %be, label %leave.loopexit
580 call void @side_effect()
581 %be.cond = icmp sgt i32 %iv.dec, 4
582 br i1 %be.cond, label %loop, label %leave
589 !0 = !{i32 0, i32 2147483647}