test/Transforms/IndVarSimplify/eliminate-comparison.ll

   1 ; RUN: opt -indvars -S < %s | FileCheck %s
   2
   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"
   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
  13 define void @foo(i64 %n, i32* nocapture %p) nounwind {
  14 entry:
  15   %cmp9 = icmp sgt i64 %n, 0
  16   br i1 %cmp9, label %pre, label %return
  17
  18 pre:
  19   %t3 = load i32, i32* %p
  20   %tobool.not = icmp ne i32 %t3, 0
  21   br label %loop
  22
  23 loop:
  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
  29 if.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
  34 for.inc:
  35   %inc = add nsw i64 %i, 1
  36   %exitcond = icmp sge i64 %inc, %n
  37   br i1 %exitcond, label %return, label %loop
  38
  39 return:
  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
  48 define i32 @_ZNK4llvm5APInt3ultERKS0_(i32 %tmp2.i1, i64** %tmp65, i64** %tmp73, i64** %tmp82, i64** %tmp90) {
  49 entry:
  50   br label %bb18
  51
  52 bb13:
  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
  62 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
  71
  72 bb17:
  73   %tmp97 = add nsw i32 %i, -1
  74   br label %bb18
  75
  76 bb18:
  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
  81 bb20.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
  92 define void @func_10() nounwind {
  93 entry:
  94   br label %loop
  95
  96 loop:
  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
 106 return:
 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 slt i32 %__key6.0, 10
 115 ; CHECK-NOT: br i1 true, label %noassert68, label %unrolledend
 116
 117 define i32 @func_11() nounwind uwtable {
 118 entry:
 119   br label %forcond
 120
 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
 125
 126 forcond38.preheader:                              ; preds = %forcond
 127   br label %forcond38
 128
 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
 136
 137 assert33:                                         ; preds = %noassert
 138   tail call void @llvm.trap()
 139   unreachable
 140
 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
 145
 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
 153
 154 assert77:                                         ; preds = %noassert68
 155   tail call void @llvm.trap()
 156   unreachable
 157
 158 unrolledend:                                      ; preds = %forcond38
 159   ret i32 0
 160 }
 161
 162 declare 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 slt i32 %__key6.0, 10
 167 ; CHECK: br i1 true, label %noassert68, label %unrolledend
 168 define i32 @func_12() nounwind uwtable {
 169 entry:
 170   br label %forcond
 171
 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
 176
 177 forcond38.preheader:                              ; preds = %forcond
 178   br label %forcond38
 179
 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
 187
 188 assert33:                                         ; preds = %noassert
 189   tail call void @llvm.trap()
 190   unreachable
 191
 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
 196
 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
 204
 205 assert77:                                         ; preds = %noassert68
 206   tail call void @llvm.trap()
 207   unreachable
 208
 209 unrolledend:                                      ; preds = %forcond38
 210   ret i32 0
 211 }
 212
 213 declare void @side_effect()
 214
 215 define 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
 241 define 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
 269 define 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
 295 define 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
 324 define 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
 359 define i1 @func_18(i16* %tmp20, i32* %len.addr) {
 360 ; CHECK-LABEL: @func_18(
 361 entry:
 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
 366 bb0.preheader:
 367   br label %bb0
 368
 369 bb0:
 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
 378 stay:
 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
 385 bb1:
 386   %tmp30 = add i32 %var_1, 1
 387   %tmp31 = icmp eq i32 %var_0, 0
 388   br i1 %tmp31, label %bb3, label %bb0
 389
 390 bb2:
 391   ret i1 false
 392
 393 bb3:
 394   ret i1 true
 395 }
 396
 397 define 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
 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.
 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
 450 define 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
 479 define 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
 508 define 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
 533 define 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}