llvm/test/Transforms/IndVarSimplify/eliminate-comparison.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -indvars -S < %s | FileCheck %s
   3
   4 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
   6 @X = external global [0 x double]
   7
   8 ; Indvars should be able to simplify simple comparisons involving
   9 ; induction variables.
  10
  11 define void @foo(i64 %n, i32* nocapture %p) nounwind {
  12 ; CHECK-LABEL: @foo(
  13 ; CHECK-NEXT:  entry:
  14 ; CHECK-NEXT:    [[CMP9:%.*]] = icmp sgt i64 [[N:%.*]], 0
  15 ; CHECK-NEXT:    br i1 [[CMP9]], label [[PRE:%.*]], label [[RETURN:%.*]]
  16 ; CHECK:       pre:
  17 ; CHECK-NEXT:    [[T3:%.*]] = load i32, i32* [[P:%.*]], align 4
  18 ; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp ne i32 [[T3]], 0
  19 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  20 ; CHECK:       loop:
  21 ; CHECK-NEXT:    [[I:%.*]] = phi i64 [ 0, [[PRE]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
  22 ; CHECK-NEXT:    [[COND:%.*]] = and i1 [[TOBOOL_NOT]], true
  23 ; CHECK-NEXT:    br i1 [[COND]], label [[IF_THEN:%.*]], label [[FOR_INC]]
  24 ; CHECK:       if.then:
  25 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr [0 x double], [0 x double]* @X, i64 0, i64 [[I]]
  26 ; CHECK-NEXT:    store double 3.200000e+00, double* [[ARRAYIDX]], align 8
  27 ; CHECK-NEXT:    br label [[FOR_INC]]
  28 ; CHECK:       for.inc:
  29 ; CHECK-NEXT:    [[INC]] = add nuw nsw i64 [[I]], 1
  30 ; CHECK-NEXT:    [[EXITCOND1:%.*]] = icmp eq i64 [[INC]], [[N]]
  31 ; CHECK-NEXT:    br i1 [[EXITCOND1]], label [[RETURN_LOOPEXIT:%.*]], label [[LOOP]]
  32 ; CHECK:       return.loopexit:
  33 ; CHECK-NEXT:    br label [[RETURN]]
  34 ; CHECK:       return:
  35 ; CHECK-NEXT:    ret void
  36 ;
  37 entry:
  38   %cmp9 = icmp sgt i64 %n, 0
  39   br i1 %cmp9, label %pre, label %return
  40
  41 pre:
  42   %t3 = load i32, i32* %p
  43   %tobool.not = icmp ne i32 %t3, 0
  44   br label %loop
  45
  46 loop:
  47   %i = phi i64 [ 0, %pre ], [ %inc, %for.inc ]
  48   %cmp6 = icmp slt i64 %i, %n
  49   %cond = and i1 %tobool.not, %cmp6
  50   br i1 %cond, label %if.then, label %for.inc
  51
  52 if.then:
  53   %arrayidx = getelementptr [0 x double], [0 x double]* @X, i64 0, i64 %i
  54   store double 3.200000e+00, double* %arrayidx
  55   br label %for.inc
  56
  57 for.inc:
  58   %inc = add nsw i64 %i, 1
  59   %exitcond = icmp sge i64 %inc, %n
  60   br i1 %exitcond, label %return, label %loop
  61
  62 return:
  63   ret void
  64 }
  65
  66 ; Don't eliminate an icmp that's contributing to the loop exit test though.
  67
  68 define i32 @_ZNK4llvm5APInt3ultERKS0_(i32 %tmp2.i1, i64** %tmp65, i64** %tmp73, i64** %tmp82, i64** %tmp90) {
  69 ; CHECK-LABEL: @_ZNK4llvm5APInt3ultERKS0_(
  70 ; CHECK-NEXT:  entry:
  71 ; CHECK-NEXT:    br label [[BB18:%.*]]
  72 ; CHECK:       bb13:
  73 ; CHECK-NEXT:    [[TMP66:%.*]] = load i64*, i64** [[TMP65:%.*]], align 4
  74 ; CHECK-NEXT:    [[TMP68:%.*]] = getelementptr inbounds i64, i64* [[TMP66]], i32 [[I:%.*]]
  75 ; CHECK-NEXT:    [[TMP69:%.*]] = load i64, i64* [[TMP68]], align 4
  76 ; CHECK-NEXT:    [[TMP74:%.*]] = load i64*, i64** [[TMP73:%.*]], align 4
  77 ; CHECK-NEXT:    [[TMP76:%.*]] = getelementptr inbounds i64, i64* [[TMP74]], i32 [[I]]
  78 ; CHECK-NEXT:    [[TMP77:%.*]] = load i64, i64* [[TMP76]], align 4
  79 ; CHECK-NEXT:    [[TMP78:%.*]] = icmp ugt i64 [[TMP69]], [[TMP77]]
  80 ; CHECK-NEXT:    br i1 [[TMP78]], label [[BB20_LOOPEXIT:%.*]], label [[BB15:%.*]]
  81 ; CHECK:       bb15:
  82 ; CHECK-NEXT:    [[TMP83:%.*]] = load i64*, i64** [[TMP82:%.*]], align 4
  83 ; CHECK-NEXT:    [[TMP85:%.*]] = getelementptr inbounds i64, i64* [[TMP83]], i32 [[I]]
  84 ; CHECK-NEXT:    [[TMP86:%.*]] = load i64, i64* [[TMP85]], align 4
  85 ; CHECK-NEXT:    [[TMP91:%.*]] = load i64*, i64** [[TMP90:%.*]], align 4
  86 ; CHECK-NEXT:    [[TMP93:%.*]] = getelementptr inbounds i64, i64* [[TMP91]], i32 [[I]]
  87 ; CHECK-NEXT:    [[TMP94:%.*]] = load i64, i64* [[TMP93]], align 4
  88 ; CHECK-NEXT:    [[TMP95:%.*]] = icmp ult i64 [[TMP86]], [[TMP94]]
  89 ; CHECK-NEXT:    br i1 [[TMP95]], label [[BB20_LOOPEXIT]], label [[BB17:%.*]]
  90 ; CHECK:       bb17:
  91 ; CHECK-NEXT:    [[TMP97:%.*]] = add nsw i32 [[I]], -1
  92 ; CHECK-NEXT:    br label [[BB18]]
  93 ; CHECK:       bb18:
  94 ; CHECK-NEXT:    [[I]] = phi i32 [ [[TMP2_I1:%.*]], [[ENTRY:%.*]] ], [ [[TMP97]], [[BB17]] ]
  95 ; CHECK-NEXT:    [[TMP99:%.*]] = icmp sgt i32 [[I]], -1
  96 ; CHECK-NEXT:    br i1 [[TMP99]], label [[BB13:%.*]], label [[BB20_LOOPEXIT]]
  97 ; CHECK:       bb20.loopexit:
  98 ; CHECK-NEXT:    [[TMP_0_PH:%.*]] = phi i32 [ 0, [[BB18]] ], [ 1, [[BB15]] ], [ 0, [[BB13]] ]
  99 ; CHECK-NEXT:    ret i32 [[TMP_0_PH]]
 100 ;
 101 entry:
 102   br label %bb18
 103
 104 bb13:
 105   %tmp66 = load i64*, i64** %tmp65, align 4
 106   %tmp68 = getelementptr inbounds i64, i64* %tmp66, i32 %i
 107   %tmp69 = load i64, i64* %tmp68, align 4
 108   %tmp74 = load i64*, i64** %tmp73, align 4
 109   %tmp76 = getelementptr inbounds i64, i64* %tmp74, i32 %i
 110   %tmp77 = load i64, i64* %tmp76, align 4
 111   %tmp78 = icmp ugt i64 %tmp69, %tmp77
 112   br i1 %tmp78, label %bb20.loopexit, label %bb15
 113
 114 bb15:
 115   %tmp83 = load i64*, i64** %tmp82, align 4
 116   %tmp85 = getelementptr inbounds i64, i64* %tmp83, i32 %i
 117   %tmp86 = load i64, i64* %tmp85, align 4
 118   %tmp91 = load i64*, i64** %tmp90, align 4
 119   %tmp93 = getelementptr inbounds i64, i64* %tmp91, i32 %i
 120   %tmp94 = load i64, i64* %tmp93, align 4
 121   %tmp95 = icmp ult i64 %tmp86, %tmp94
 122   br i1 %tmp95, label %bb20.loopexit, label %bb17
 123
 124 bb17:
 125   %tmp97 = add nsw i32 %i, -1
 126   br label %bb18
 127
 128 bb18:
 129   %i = phi i32 [ %tmp2.i1, %entry ], [ %tmp97, %bb17 ]
 130   %tmp99 = icmp sgt i32 %i, -1
 131   br i1 %tmp99, label %bb13, label %bb20.loopexit
 132
 133 bb20.loopexit:
 134   %tmp.0.ph = phi i32 [ 0, %bb18 ], [ 1, %bb15 ], [ 0, %bb13 ]
 135   ret i32 %tmp.0.ph
 136 }
 137
 138 ; Indvars should eliminate the icmp here.
 139
 140
 141 define void @func_10() nounwind {
 142 ; CHECK-LABEL: @func_10(
 143 ; CHECK-NEXT:  entry:
 144 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 145 ; CHECK:       loop:
 146 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
 147 ; CHECK-NEXT:    store i64 [[INDVARS_IV]], i64* null, align 8
 148 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 149 ; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[RETURN:%.*]]
 150 ; CHECK:       return:
 151 ; CHECK-NEXT:    ret void
 152 ;
 153 entry:
 154   br label %loop
 155
 156 loop:
 157   %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 158   %t0 = icmp slt i32 %i, 0
 159   %t1 = zext i1 %t0 to i32
 160   %t2 = add i32 %t1, %i
 161   %u3 = zext i32 %t2 to i64
 162   store i64 %u3, i64* null
 163   %i.next = add i32 %i, 1
 164   br i1 undef, label %loop, label %return
 165
 166 return:
 167   ret void
 168 }
 169
 170 ; PR14432
 171 ; Indvars should not turn the second loop into an infinite one.
 172
 173
 174 define i32 @func_11() nounwind uwtable {
 175 ; CHECK-LABEL: @func_11(
 176 ; CHECK-NEXT:  entry:
 177 ; CHECK-NEXT:    br label [[FORCOND:%.*]]
 178 ; CHECK:       forcond:
 179 ; CHECK-NEXT:    br i1 false, label [[NOASSERT:%.*]], label [[FORCOND38_PREHEADER:%.*]]
 180 ; CHECK:       forcond38.preheader:
 181 ; CHECK-NEXT:    br label [[FORCOND38:%.*]]
 182 ; CHECK:       noassert:
 183 ; CHECK-NEXT:    br i1 true, label [[FORCOND]], label [[ASSERT33:%.*]]
 184 ; CHECK:       assert33:
 185 ; CHECK-NEXT:    tail call void @llvm.trap()
 186 ; CHECK-NEXT:    unreachable
 187 ; CHECK:       forcond38:
 188 ; CHECK-NEXT:    br i1 false, label [[NOASSERT68:%.*]], label [[UNROLLEDEND:%.*]]
 189 ; CHECK:       noassert68:
 190 ; CHECK-NEXT:    br i1 true, label [[FORCOND38]], label [[ASSERT77:%.*]]
 191 ; CHECK:       assert77:
 192 ; CHECK-NEXT:    tail call void @llvm.trap()
 193 ; CHECK-NEXT:    unreachable
 194 ; CHECK:       unrolledend:
 195 ; CHECK-NEXT:    ret i32 0
 196 ;
 197 entry:
 198   br label %forcond
 199
 200 forcond:                                          ; preds = %noassert, %entry
 201   %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
 202   %tmp5 = icmp slt i32 %__key6.0, 10
 203   br i1 %tmp5, label %noassert, label %forcond38.preheader
 204
 205 forcond38.preheader:                              ; preds = %forcond
 206   br label %forcond38
 207
 208 noassert:                                         ; preds = %forbody
 209   %tmp13 = sdiv i32 -32768, %__key6.0
 210   %tmp2936 = shl i32 %tmp13, 24
 211   %sext23 = shl i32 %tmp13, 24
 212   %tmp32 = icmp eq i32 %tmp2936, %sext23
 213   %tmp37 = add i32 %__key6.0, 1
 214   br i1 %tmp32, label %forcond, label %assert33
 215
 216 assert33:                                         ; preds = %noassert
 217   tail call void @llvm.trap()
 218   unreachable
 219
 220 forcond38:                                        ; preds = %noassert68, %forcond38.preheader
 221   %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ]
 222   %tmp46 = icmp slt i32 %__key8.0, 10
 223   br i1 %tmp46, label %noassert68, label %unrolledend
 224
 225 noassert68:                                       ; preds = %forbody39
 226   %tmp57 = sdiv i32 -32768, %__key8.0
 227   %sext34 = shl i32 %tmp57, 16
 228   %sext21 = shl i32 %tmp57, 16
 229   %tmp76 = icmp eq i32 %sext34, %sext21
 230   %tmp81 = add i32 %__key8.0, 1
 231   br i1 %tmp76, label %forcond38, label %assert77
 232
 233 assert77:                                         ; preds = %noassert68
 234   tail call void @llvm.trap()
 235   unreachable
 236
 237 unrolledend:                                      ; preds = %forcond38
 238   ret i32 0
 239 }
 240
 241 define i32 @func_11_flipped() nounwind uwtable {
 242 ; CHECK-LABEL: @func_11_flipped(
 243 ; CHECK-NEXT:  entry:
 244 ; CHECK-NEXT:    br label [[FORCOND:%.*]]
 245 ; CHECK:       forcond:
 246 ; CHECK-NEXT:    br i1 true, label [[FORCOND38_PREHEADER:%.*]], label [[NOASSERT:%.*]]
 247 ; CHECK:       forcond38.preheader:
 248 ; CHECK-NEXT:    br label [[FORCOND38:%.*]]
 249 ; CHECK:       noassert:
 250 ; CHECK-NEXT:    br i1 true, label [[FORCOND]], label [[ASSERT33:%.*]]
 251 ; CHECK:       assert33:
 252 ; CHECK-NEXT:    tail call void @llvm.trap()
 253 ; CHECK-NEXT:    unreachable
 254 ; CHECK:       forcond38:
 255 ; CHECK-NEXT:    br i1 false, label [[NOASSERT68:%.*]], label [[UNROLLEDEND:%.*]]
 256 ; CHECK:       noassert68:
 257 ; CHECK-NEXT:    br i1 true, label [[FORCOND38]], label [[ASSERT77:%.*]]
 258 ; CHECK:       assert77:
 259 ; CHECK-NEXT:    tail call void @llvm.trap()
 260 ; CHECK-NEXT:    unreachable
 261 ; CHECK:       unrolledend:
 262 ; CHECK-NEXT:    ret i32 0
 263 ;
 264 entry:
 265   br label %forcond
 266
 267 forcond:                                          ; preds = %noassert, %entry
 268   %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
 269   %tmp5 = icmp sge i32 %__key6.0, 10
 270   br i1 %tmp5, label %forcond38.preheader, label %noassert
 271
 272 forcond38.preheader:                              ; preds = %forcond
 273   br label %forcond38
 274
 275 noassert:                                         ; preds = %forbody
 276   %tmp13 = sdiv i32 -32768, %__key6.0
 277   %tmp2936 = shl i32 %tmp13, 24
 278   %sext23 = shl i32 %tmp13, 24
 279   %tmp32 = icmp eq i32 %tmp2936, %sext23
 280   %tmp37 = add i32 %__key6.0, 1
 281   br i1 %tmp32, label %forcond, label %assert33
 282
 283 assert33:                                         ; preds = %noassert
 284   tail call void @llvm.trap()
 285   unreachable
 286
 287 forcond38:                                        ; preds = %noassert68, %forcond38.preheader
 288   %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ]
 289   %tmp46 = icmp slt i32 %__key8.0, 10
 290   br i1 %tmp46, label %noassert68, label %unrolledend
 291
 292 noassert68:                                       ; preds = %forbody39
 293   %tmp57 = sdiv i32 -32768, %__key8.0
 294   %sext34 = shl i32 %tmp57, 16
 295   %sext21 = shl i32 %tmp57, 16
 296   %tmp76 = icmp eq i32 %sext34, %sext21
 297   %tmp81 = add i32 %__key8.0, 1
 298   br i1 %tmp76, label %forcond38, label %assert77
 299
 300 assert77:                                         ; preds = %noassert68
 301   tail call void @llvm.trap()
 302   unreachable
 303
 304 unrolledend:                                      ; preds = %forcond38
 305   ret i32 0
 306 }
 307
 308 declare void @llvm.trap() noreturn nounwind
 309
 310 ; In this case the second loop only has a single iteration, fold the header away
 311 define i32 @func_12() nounwind uwtable {
 312 ; CHECK-LABEL: @func_12(
 313 ; CHECK-NEXT:  entry:
 314 ; CHECK-NEXT:    br label [[FORCOND:%.*]]
 315 ; CHECK:       forcond:
 316 ; CHECK-NEXT:    br i1 false, label [[NOASSERT:%.*]], label [[FORCOND38_PREHEADER:%.*]]
 317 ; CHECK:       forcond38.preheader:
 318 ; CHECK-NEXT:    br label [[FORCOND38:%.*]]
 319 ; CHECK:       noassert:
 320 ; CHECK-NEXT:    br i1 true, label [[FORCOND]], label [[ASSERT33:%.*]]
 321 ; CHECK:       assert33:
 322 ; CHECK-NEXT:    tail call void @llvm.trap()
 323 ; CHECK-NEXT:    unreachable
 324 ; CHECK:       forcond38:
 325 ; CHECK-NEXT:    br i1 true, label [[NOASSERT68:%.*]], label [[UNROLLEDEND:%.*]]
 326 ; CHECK:       noassert68:
 327 ; CHECK-NEXT:    br i1 false, label [[FORCOND38]], label [[ASSERT77:%.*]]
 328 ; CHECK:       assert77:
 329 ; CHECK-NEXT:    tail call void @llvm.trap()
 330 ; CHECK-NEXT:    unreachable
 331 ; CHECK:       unrolledend:
 332 ; CHECK-NEXT:    ret i32 0
 333 ;
 334 entry:
 335   br label %forcond
 336
 337 forcond:                                          ; preds = %noassert, %entry
 338   %__key6.0 = phi i32 [ 2, %entry ], [ %tmp37, %noassert ]
 339   %tmp5 = icmp slt i32 %__key6.0, 10
 340   br i1 %tmp5, label %noassert, label %forcond38.preheader
 341
 342 forcond38.preheader:                              ; preds = %forcond
 343   br label %forcond38
 344
 345 noassert:                                         ; preds = %forbody
 346   %tmp13 = sdiv i32 -32768, %__key6.0
 347   %tmp2936 = shl i32 %tmp13, 24
 348   %sext23 = shl i32 %tmp13, 24
 349   %tmp32 = icmp eq i32 %tmp2936, %sext23
 350   %tmp37 = add i32 %__key6.0, 1
 351   br i1 %tmp32, label %forcond, label %assert33
 352
 353 assert33:                                         ; preds = %noassert
 354   tail call void @llvm.trap()
 355   unreachable
 356
 357 forcond38:                                        ; preds = %noassert68, %forcond38.preheader
 358   %__key8.0 = phi i32 [ %tmp81, %noassert68 ], [ 2, %forcond38.preheader ]
 359   %tmp46 = icmp slt i32 %__key8.0, 10
 360   br i1 %tmp46, label %noassert68, label %unrolledend
 361
 362 noassert68:                                       ; preds = %forbody39
 363   %tmp57 = sdiv i32 -32768, %__key8.0
 364   %sext34 = shl i32 %tmp57, 16
 365   %sext21 = shl i32 %tmp57, 16
 366   %tmp76 = icmp ne i32 %sext34, %sext21
 367   %tmp81 = add i32 %__key8.0, 1
 368   br i1 %tmp76, label %forcond38, label %assert77
 369
 370 assert77:                                         ; preds = %noassert68
 371   tail call void @llvm.trap()
 372   unreachable
 373
 374 unrolledend:                                      ; preds = %forcond38
 375   ret i32 0
 376 }
 377
 378 declare void @side_effect()
 379
 380 define void @func_13(i32* %len.ptr) {
 381 ; CHECK-LABEL: @func_13(
 382 ; CHECK-NEXT:  entry:
 383 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0:![0-9]+]]
 384 ; CHECK-NEXT:    [[LEN_IS_ZERO:%.*]] = icmp eq i32 [[LEN]], 0
 385 ; CHECK-NEXT:    br i1 [[LEN_IS_ZERO]], label [[LEAVE:%.*]], label [[LOOP_PREHEADER:%.*]]
 386 ; CHECK:       loop.preheader:
 387 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 388 ; CHECK:       loop:
 389 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 390 ; CHECK-NEXT:    call void @side_effect()
 391 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 392 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 393 ; CHECK:       be:
 394 ; CHECK-NEXT:    call void @side_effect()
 395 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LEN]]
 396 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 397 ; CHECK:       leave.loopexit:
 398 ; CHECK-NEXT:    br label [[LEAVE]]
 399 ; CHECK:       leave:
 400 ; CHECK-NEXT:    ret void
 401 ;
 402 entry:
 403   %len = load i32, i32* %len.ptr, !range !0
 404   %len.sub.1 = add i32 %len, -1
 405   %len.is.zero = icmp eq i32 %len, 0
 406   br i1 %len.is.zero, label %leave, label %loop
 407
 408 loop:
 409   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
 410   call void @side_effect()
 411   %iv.inc = add i32 %iv, 1
 412   %iv.cmp = icmp ult i32 %iv, %len
 413   br i1 %iv.cmp, label %be, label %leave
 414
 415 be:
 416   call void @side_effect()
 417   %be.cond = icmp ult i32 %iv, %len.sub.1
 418   br i1 %be.cond, label %loop, label %leave
 419
 420 leave:
 421   ret void
 422 }
 423
 424 define void @func_14(i32* %len.ptr) {
 425 ; CHECK-LABEL: @func_14(
 426 ; CHECK-NEXT:  entry:
 427 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
 428 ; CHECK-NEXT:    [[LEN_IS_ZERO:%.*]] = icmp eq i32 [[LEN]], 0
 429 ; CHECK-NEXT:    [[LEN_IS_INT_MIN:%.*]] = icmp eq i32 [[LEN]], -2147483648
 430 ; CHECK-NEXT:    [[NO_ENTRY:%.*]] = or i1 [[LEN_IS_ZERO]], [[LEN_IS_INT_MIN]]
 431 ; CHECK-NEXT:    br i1 [[NO_ENTRY]], label [[LEAVE:%.*]], label [[LOOP_PREHEADER:%.*]]
 432 ; CHECK:       loop.preheader:
 433 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 434 ; CHECK:       loop:
 435 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 436 ; CHECK-NEXT:    call void @side_effect()
 437 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 438 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 439 ; CHECK:       be:
 440 ; CHECK-NEXT:    call void @side_effect()
 441 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LEN]]
 442 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 443 ; CHECK:       leave.loopexit:
 444 ; CHECK-NEXT:    br label [[LEAVE]]
 445 ; CHECK:       leave:
 446 ; CHECK-NEXT:    ret void
 447 ;
 448 entry:
 449   %len = load i32, i32* %len.ptr, !range !0
 450   %len.sub.1 = add i32 %len, -1
 451   %len.is.zero = icmp eq i32 %len, 0
 452   %len.is.int_min = icmp eq i32 %len, 2147483648
 453   %no.entry = or i1 %len.is.zero, %len.is.int_min
 454   br i1 %no.entry, label %leave, label %loop
 455
 456 loop:
 457   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
 458   call void @side_effect()
 459   %iv.inc = add i32 %iv, 1
 460   %iv.cmp = icmp slt i32 %iv, %len
 461   br i1 %iv.cmp, label %be, label %leave
 462
 463 be:
 464   call void @side_effect()
 465   %be.cond = icmp slt i32 %iv, %len.sub.1
 466   br i1 %be.cond, label %loop, label %leave
 467
 468 leave:
 469   ret void
 470 }
 471
 472 define void @func_15(i32* %len.ptr) {
 473 ; CHECK-LABEL: @func_15(
 474 ; CHECK-NEXT:  entry:
 475 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
 476 ; CHECK-NEXT:    [[LEN_ADD_1:%.*]] = add i32 [[LEN]], 1
 477 ; CHECK-NEXT:    [[LEN_ADD_1_IS_ZERO:%.*]] = icmp eq i32 [[LEN_ADD_1]], 0
 478 ; CHECK-NEXT:    br i1 [[LEN_ADD_1_IS_ZERO]], label [[LEAVE:%.*]], label [[LOOP_PREHEADER:%.*]]
 479 ; CHECK:       loop.preheader:
 480 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 481 ; CHECK:       loop:
 482 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 483 ; CHECK-NEXT:    call void @side_effect()
 484 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 485 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 486 ; CHECK:       be:
 487 ; CHECK-NEXT:    call void @side_effect()
 488 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LEN_ADD_1]]
 489 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 490 ; CHECK:       leave.loopexit:
 491 ; CHECK-NEXT:    br label [[LEAVE]]
 492 ; CHECK:       leave:
 493 ; CHECK-NEXT:    ret void
 494 ;
 495 entry:
 496   %len = load i32, i32* %len.ptr, !range !0
 497   %len.add.1 = add i32 %len, 1
 498   %len.add.1.is.zero = icmp eq i32 %len.add.1, 0
 499   br i1 %len.add.1.is.zero, label %leave, label %loop
 500
 501 loop:
 502   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
 503   call void @side_effect()
 504   %iv.inc = add i32 %iv, 1
 505   %iv.cmp = icmp ult i32 %iv, %len.add.1
 506   br i1 %iv.cmp, label %be, label %leave
 507
 508 be:
 509   call void @side_effect()
 510   %be.cond = icmp ult i32 %iv, %len
 511   br i1 %be.cond, label %loop, label %leave
 512
 513 leave:
 514   ret void
 515 }
 516
 517 define void @func_16(i32* %len.ptr) {
 518 ; CHECK-LABEL: @func_16(
 519 ; CHECK-NEXT:  entry:
 520 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]]
 521 ; CHECK-NEXT:    [[LEN_ADD_5:%.*]] = add i32 [[LEN]], 5
 522 ; CHECK-NEXT:    [[ENTRY_COND_0:%.*]] = icmp slt i32 [[LEN]], 2147483643
 523 ; CHECK-NEXT:    [[ENTRY_COND_1:%.*]] = icmp slt i32 4, [[LEN_ADD_5]]
 524 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = and i1 [[ENTRY_COND_0]], [[ENTRY_COND_1]]
 525 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 526 ; CHECK:       loop.preheader:
 527 ; CHECK-NEXT:    [[TMP0:%.*]] = add nuw nsw i32 [[LEN]], 1
 528 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 529 ; CHECK:       loop:
 530 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 531 ; CHECK-NEXT:    call void @side_effect()
 532 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 533 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 534 ; CHECK:       be:
 535 ; CHECK-NEXT:    call void @side_effect()
 536 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[TMP0]]
 537 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 538 ; CHECK:       leave.loopexit:
 539 ; CHECK-NEXT:    br label [[LEAVE]]
 540 ; CHECK:       leave:
 541 ; CHECK-NEXT:    ret void
 542 ;
 543 entry:
 544   %len = load i32, i32* %len.ptr, !range !0
 545   %len.add.5 = add i32 %len, 5
 546   %entry.cond.0 = icmp slt i32 %len, 2147483643
 547   %entry.cond.1 = icmp slt i32 4, %len.add.5
 548   %entry.cond = and i1 %entry.cond.0, %entry.cond.1
 549   br i1 %entry.cond, label %loop, label %leave
 550
 551 loop:
 552   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
 553   call void @side_effect()
 554   %iv.inc = add i32 %iv, 1
 555   %iv.add.4 = add i32 %iv, 4
 556   %iv.cmp = icmp slt i32 %iv.add.4, %len.add.5
 557   br i1 %iv.cmp, label %be, label %leave
 558
 559 be:
 560   call void @side_effect()
 561   %be.cond = icmp slt i32 %iv, %len
 562   br i1 %be.cond, label %loop, label %leave
 563
 564 leave:
 565   ret void
 566 }
 567
 568 define void @func_17(i32* %len.ptr) {
 569 ; CHECK-LABEL: @func_17(
 570 ; CHECK-NEXT:  entry:
 571 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4
 572 ; CHECK-NEXT:    [[LEN_ADD_5:%.*]] = add i32 [[LEN]], -5
 573 ; CHECK-NEXT:    [[ENTRY_COND_0:%.*]] = icmp slt i32 [[LEN]], -2147483643
 574 ; CHECK-NEXT:    [[ENTRY_COND_1:%.*]] = icmp slt i32 -6, [[LEN_ADD_5]]
 575 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = and i1 [[ENTRY_COND_0]], [[ENTRY_COND_1]]
 576 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 577 ; CHECK:       loop.preheader:
 578 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LEN]], i32 0)
 579 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[SMAX]], -5
 580 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 581 ; CHECK:       loop:
 582 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ -6, [[LOOP_PREHEADER]] ]
 583 ; CHECK-NEXT:    call void @side_effect()
 584 ; CHECK-NEXT:    [[IV_INC]] = add nsw i32 [[IV]], 1
 585 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 586 ; CHECK:       be:
 587 ; CHECK-NEXT:    call void @side_effect()
 588 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[TMP0]]
 589 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 590 ; CHECK:       leave.loopexit:
 591 ; CHECK-NEXT:    br label [[LEAVE]]
 592 ; CHECK:       leave:
 593 ; CHECK-NEXT:    ret void
 594 ;
 595 entry:
 596   %len = load i32, i32* %len.ptr
 597   %len.add.5 = add i32 %len, -5
 598   %entry.cond.0 = icmp slt i32 %len, 2147483653 ;; 2147483653 == INT_MIN - (-5)
 599   %entry.cond.1 = icmp slt i32 -6, %len.add.5
 600   %entry.cond = and i1 %entry.cond.0, %entry.cond.1
 601   br i1 %entry.cond, label %loop, label %leave
 602
 603 loop:
 604   %iv.2 = phi i32 [ 0, %entry ], [ %iv.2.inc, %be ]
 605   %iv = phi i32 [ -6, %entry ], [ %iv.inc, %be ]
 606   call void @side_effect()
 607   %iv.inc = add i32 %iv, 1
 608   %iv.2.inc = add i32 %iv.2, 1
 609   %iv.cmp = icmp slt i32 %iv, %len.add.5
 610
 611 ; Deduces {-5,+,1} s< (-5 + %len) from {0,+,1} < %len
 612 ; since %len s< INT_MIN - (-5) from the entry condition
 613   br i1 %iv.cmp, label %be, label %leave
 614
 615 be:
 616   call void @side_effect()
 617   %be.cond = icmp slt i32 %iv.2, %len
 618   br i1 %be.cond, label %loop, label %leave
 619
 620 leave:
 621   ret void
 622 }
 623
 624 define i1 @func_18(i16* %tmp20, i32* %len.addr) {
 625 ; CHECK-LABEL: @func_18(
 626 ; CHECK-NEXT:  entry:
 627 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, i32* [[LEN_ADDR:%.*]], align 4, !range [[RNG0]]
 628 ; CHECK-NEXT:    [[TMP18:%.*]] = icmp eq i32 [[LEN]], 0
 629 ; CHECK-NEXT:    br i1 [[TMP18]], label [[BB2:%.*]], label [[BB0_PREHEADER:%.*]]
 630 ; CHECK:       bb0.preheader:
 631 ; CHECK-NEXT:    br label [[BB0:%.*]]
 632 ; CHECK:       bb0:
 633 ; CHECK-NEXT:    [[VAR_0_IN:%.*]] = phi i32 [ [[VAR_0:%.*]], [[BB1:%.*]] ], [ [[LEN]], [[BB0_PREHEADER]] ]
 634 ; CHECK-NEXT:    [[VAR_1:%.*]] = phi i32 [ [[TMP30:%.*]], [[BB1]] ], [ 0, [[BB0_PREHEADER]] ]
 635 ; CHECK-NEXT:    [[VAR_0]] = add nsw i32 [[VAR_0_IN]], -1
 636 ; CHECK-NEXT:    br i1 true, label [[STAY:%.*]], label [[BB2_LOOPEXIT:%.*]]
 637 ; CHECK:       stay:
 638 ; CHECK-NEXT:    [[TMP25:%.*]] = getelementptr inbounds i16, i16* [[TMP20:%.*]], i32 [[VAR_1]]
 639 ; CHECK-NEXT:    [[TMP26:%.*]] = load i16, i16* [[TMP25]], align 2
 640 ; CHECK-NEXT:    [[TMP29:%.*]] = icmp eq i16 [[TMP26]], 0
 641 ; CHECK-NEXT:    br i1 [[TMP29]], label [[BB1]], label [[BB2_LOOPEXIT]]
 642 ; CHECK:       bb1:
 643 ; CHECK-NEXT:    [[TMP30]] = add nuw i32 [[VAR_1]], 1
 644 ; CHECK-NEXT:    [[TMP31:%.*]] = icmp eq i32 [[VAR_0]], 0
 645 ; CHECK-NEXT:    br i1 [[TMP31]], label [[BB3:%.*]], label [[BB0]]
 646 ; CHECK:       bb2.loopexit:
 647 ; CHECK-NEXT:    br label [[BB2]]
 648 ; CHECK:       bb2:
 649 ; CHECK-NEXT:    ret i1 false
 650 ; CHECK:       bb3:
 651 ; CHECK-NEXT:    ret i1 true
 652 ;
 653 entry:
 654   %len = load i32, i32* %len.addr, !range !0
 655   %tmp18 = icmp eq i32 %len, 0
 656   br i1 %tmp18, label %bb2, label %bb0.preheader
 657
 658 bb0.preheader:
 659   br label %bb0
 660
 661 bb0:
 662   %var_0.in = phi i32 [ %var_0, %bb1 ], [ %len, %bb0.preheader ]
 663   %var_1 = phi i32 [ %tmp30, %bb1 ], [ 0, %bb0.preheader ]
 664   %var_0 = add nsw i32 %var_0.in, -1
 665   %tmp23 = icmp ult i32 %var_1, %len
 666   br i1 %tmp23, label %stay, label %bb2
 667
 668 stay:
 669   %tmp25 = getelementptr inbounds i16, i16* %tmp20, i32 %var_1
 670   %tmp26 = load i16, i16* %tmp25
 671   %tmp29 = icmp eq i16 %tmp26, 0
 672   br i1 %tmp29, label %bb1, label %bb2
 673
 674 bb1:
 675   %tmp30 = add i32 %var_1, 1
 676   %tmp31 = icmp eq i32 %var_0, 0
 677   br i1 %tmp31, label %bb3, label %bb0
 678
 679 bb2:
 680   ret i1 false
 681
 682 bb3:
 683   ret i1 true
 684 }
 685
 686 define void @func_19(i32* %length.ptr) {
 687 ; CHECK-LABEL: @func_19(
 688 ; CHECK-NEXT:  entry:
 689 ; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4, !range [[RNG0]]
 690 ; CHECK-NEXT:    [[LENGTH_IS_NONZERO:%.*]] = icmp ne i32 [[LENGTH]], 0
 691 ; CHECK-NEXT:    br i1 [[LENGTH_IS_NONZERO]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 692 ; CHECK:       loop.preheader:
 693 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 694 ; CHECK:       loop:
 695 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 696 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 697 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 698 ; CHECK:       be:
 699 ; CHECK-NEXT:    call void @side_effect()
 700 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LENGTH]]
 701 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 702 ; CHECK:       leave.loopexit:
 703 ; CHECK-NEXT:    br label [[LEAVE]]
 704 ; CHECK:       leave:
 705 ; CHECK-NEXT:    ret void
 706 ;
 707 entry:
 708   %length = load i32, i32* %length.ptr, !range !0
 709   %length.is.nonzero = icmp ne i32 %length, 0
 710   br i1 %length.is.nonzero, label %loop, label %leave
 711
 712 loop:
 713   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
 714   %iv.inc = add i32 %iv, 1
 715   %range.check = icmp ult i32 %iv, %length
 716   br i1 %range.check, label %be, label %leave
 717
 718 be:
 719   call void @side_effect()
 720   %be.cond = icmp slt i32 %iv.inc, %length
 721   br i1 %be.cond, label %loop, label %leave
 722
 723 leave:
 724   ret void
 725 }
 726
 727 ; Like @func_19, but %length is no longer provably positive, so
 728 ; %range.check cannot be proved to be always true.
 729 define void @func_20(i32* %length.ptr) {
 730 ; CHECK-LABEL: @func_20(
 731 ; CHECK-NEXT:  entry:
 732 ; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4
 733 ; CHECK-NEXT:    [[LENGTH_IS_NONZERO:%.*]] = icmp ne i32 [[LENGTH]], 0
 734 ; CHECK-NEXT:    br i1 [[LENGTH_IS_NONZERO]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 735 ; CHECK:       loop.preheader:
 736 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LENGTH]], i32 1)
 737 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 738 ; CHECK:       loop:
 739 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 740 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 741 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV]], [[LENGTH]]
 742 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 743 ; CHECK:       be:
 744 ; CHECK-NEXT:    call void @side_effect()
 745 ; CHECK-NEXT:    [[EXITCOND1:%.*]] = icmp ne i32 [[IV_INC]], [[SMAX]]
 746 ; CHECK-NEXT:    br i1 [[EXITCOND1]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 747 ; CHECK:       leave.loopexit:
 748 ; CHECK-NEXT:    br label [[LEAVE]]
 749 ; CHECK:       leave:
 750 ; CHECK-NEXT:    ret void
 751 ;
 752 entry:
 753   %length = load i32, i32* %length.ptr
 754   %length.is.nonzero = icmp ne i32 %length, 0
 755   br i1 %length.is.nonzero, label %loop, label %leave
 756
 757 loop:
 758   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
 759   %iv.inc = add i32 %iv, 1
 760   %range.check = icmp ult i32 %iv, %length
 761   br i1 %range.check, label %be, label %leave
 762
 763 be:
 764   call void @side_effect()
 765   %be.cond = icmp slt i32 %iv.inc, %length
 766   br i1 %be.cond, label %loop, label %leave
 767
 768 leave:
 769   ret void
 770 }
 771
 772 ; This checks that the backedge condition, (I + 1) < Length - 1 implies
 773 ; (I + 1) < Length
 774 define void @func_21(i32* %length.ptr) {
 775 ; CHECK-LABEL: @func_21(
 776 ; CHECK-NEXT:  entry:
 777 ; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4, !range [[RNG0]]
 778 ; CHECK-NEXT:    [[LIM:%.*]] = sub i32 [[LENGTH]], 1
 779 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp sgt i32 [[LENGTH]], 1
 780 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 781 ; CHECK:       loop.preheader:
 782 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 783 ; CHECK:       loop:
 784 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 785 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 786 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 787 ; CHECK:       be:
 788 ; CHECK-NEXT:    call void @side_effect()
 789 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LIM]]
 790 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 791 ; CHECK:       leave.loopexit:
 792 ; CHECK-NEXT:    br label [[LEAVE]]
 793 ; CHECK:       leave:
 794 ; CHECK-NEXT:    ret void
 795 ;
 796 entry:
 797   %length = load i32, i32* %length.ptr, !range !0
 798   %lim = sub i32 %length, 1
 799   %entry.cond = icmp sgt i32 %length, 1
 800   br i1 %entry.cond, label %loop, label %leave
 801
 802 loop:
 803   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
 804   %iv.inc = add i32 %iv, 1
 805   %range.check = icmp slt i32 %iv, %length
 806   br i1 %range.check, label %be, label %leave
 807
 808 be:
 809   call void @side_effect()
 810   %be.cond = icmp slt i32 %iv.inc, %lim
 811   br i1 %be.cond, label %loop, label %leave
 812
 813 leave:
 814   ret void
 815 }
 816
 817 ; This checks that the backedge condition, (I + 1) < Length - 1 implies
 818 ; (I + 1) < Length
 819 define void @func_22(i32* %length.ptr) {
 820 ; CHECK-LABEL: @func_22(
 821 ; CHECK-NEXT:  entry:
 822 ; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4, !range [[RNG0]]
 823 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp sgt i32 [[LENGTH]], 1
 824 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 825 ; CHECK:       loop.preheader:
 826 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 827 ; CHECK:       loop:
 828 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
 829 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 830 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 831 ; CHECK:       be:
 832 ; CHECK-NEXT:    call void @side_effect()
 833 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LENGTH]]
 834 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 835 ; CHECK:       leave.loopexit:
 836 ; CHECK-NEXT:    br label [[LEAVE]]
 837 ; CHECK:       leave:
 838 ; CHECK-NEXT:    ret void
 839 ;
 840 entry:
 841   %length = load i32, i32* %length.ptr, !range !0
 842   %lim = sub i32 %length, 1
 843   %entry.cond = icmp sgt i32 %length, 1
 844   br i1 %entry.cond, label %loop, label %leave
 845
 846 loop:
 847   %iv = phi i32 [ 0, %entry ], [ %iv.inc, %be ]
 848   %iv.inc = add i32 %iv, 1
 849   %range.check = icmp sle i32 %iv, %length
 850   br i1 %range.check, label %be, label %leave
 851
 852 be:
 853   call void @side_effect()
 854   %be.cond = icmp sle i32 %iv.inc, %lim
 855   br i1 %be.cond, label %loop, label %leave
 856
 857 leave:
 858   ret void
 859 }
 860
 861 define void @func_23(i32* %length.ptr) {
 862 ; CHECK-LABEL: @func_23(
 863 ; CHECK-NEXT:  entry:
 864 ; CHECK-NEXT:    [[LENGTH:%.*]] = load i32, i32* [[LENGTH_PTR:%.*]], align 4, !range [[RNG0]]
 865 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp ult i32 4, [[LENGTH]]
 866 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 867 ; CHECK:       loop.preheader:
 868 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 869 ; CHECK:       loop:
 870 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_INC:%.*]], [[BE:%.*]] ], [ 4, [[LOOP_PREHEADER]] ]
 871 ; CHECK-NEXT:    [[IV_INC]] = add nuw nsw i32 [[IV]], 1
 872 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 873 ; CHECK:       be:
 874 ; CHECK-NEXT:    call void @side_effect()
 875 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_INC]], [[LENGTH]]
 876 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 877 ; CHECK:       leave.loopexit:
 878 ; CHECK-NEXT:    br label [[LEAVE]]
 879 ; CHECK:       leave:
 880 ; CHECK-NEXT:    ret void
 881 ;
 882 entry:
 883   %length = load i32, i32* %length.ptr, !range !0
 884   %entry.cond = icmp ult i32 4, %length
 885   br i1 %entry.cond, label %loop, label %leave
 886
 887 loop:
 888   %iv = phi i32 [ 4, %entry ], [ %iv.inc, %be ]
 889   %iv.inc = add i32 %iv, 1
 890   %range.check = icmp slt i32 %iv, %length
 891   br i1 %range.check, label %be, label %leave
 892
 893 be:
 894   call void @side_effect()
 895   %be.cond = icmp slt i32 %iv.inc, %length
 896   br i1 %be.cond, label %loop, label %leave
 897
 898 leave:
 899   ret void
 900 }
 901
 902 define void @func_24(i32* %init.ptr) {
 903 ; CHECK-LABEL: @func_24(
 904 ; CHECK-NEXT:  entry:
 905 ; CHECK-NEXT:    [[INIT:%.*]] = load i32, i32* [[INIT_PTR:%.*]], align 4, !range [[RNG0]]
 906 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp ugt i32 [[INIT]], 4
 907 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 908 ; CHECK:       loop.preheader:
 909 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 910 ; CHECK:       loop:
 911 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_DEC:%.*]], [[BE:%.*]] ], [ [[INIT]], [[LOOP_PREHEADER]] ]
 912 ; CHECK-NEXT:    [[IV_DEC]] = add nsw i32 [[IV]], -1
 913 ; CHECK-NEXT:    br i1 true, label [[BE]], label [[LEAVE_LOOPEXIT:%.*]]
 914 ; CHECK:       be:
 915 ; CHECK-NEXT:    call void @side_effect()
 916 ; CHECK-NEXT:    [[BE_COND:%.*]] = icmp sgt i32 [[IV_DEC]], 4
 917 ; CHECK-NEXT:    br i1 [[BE_COND]], label [[LOOP]], label [[LEAVE_LOOPEXIT]]
 918 ; CHECK:       leave.loopexit:
 919 ; CHECK-NEXT:    br label [[LEAVE]]
 920 ; CHECK:       leave:
 921 ; CHECK-NEXT:    ret void
 922 ;
 923 entry:
 924   %init = load i32, i32* %init.ptr, !range !0
 925   %entry.cond = icmp ugt i32 %init, 4
 926   br i1 %entry.cond, label %loop, label %leave
 927
 928 loop:
 929   %iv = phi i32 [ %init, %entry ], [ %iv.dec, %be ]
 930   %iv.dec = add i32 %iv, -1
 931   %range.check = icmp sgt i32 %iv, 4
 932   br i1 %range.check, label %be, label %leave
 933
 934 be:
 935   call void @side_effect()
 936   %be.cond = icmp sgt i32 %iv.dec, 4
 937   br i1 %be.cond, label %loop, label %leave
 938
 939 leave:
 940   ret void
 941 }
 942
 943 declare i1 @cond_func()
 944
 945 define i32 @func_25(i32 %start) {
 946 ; CHECK-LABEL: @func_25(
 947 ; CHECK-NEXT:  entry:
 948 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 949 ; CHECK:       loop:
 950 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 951 ; CHECK-NEXT:    [[C1:%.*]] = icmp ne i32 [[IV]], 0
 952 ; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
 953 ; CHECK:       checked.1:
 954 ; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
 955 ; CHECK:       checked.2:
 956 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
 957 ; CHECK:       backedge:
 958 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
 959 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
 960 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 961 ; CHECK:       fail:
 962 ; CHECK-NEXT:    unreachable
 963 ; CHECK:       exit:
 964 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 965 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
 966 ;
 967 entry:
 968   br label %loop
 969
 970 loop:
 971   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 972   %c1 = icmp ne i32 %iv, 0
 973   br i1 %c1, label %checked.1, label %fail
 974
 975 checked.1:
 976   %c2 = icmp ne i32 %iv, 0
 977   br i1 %c2, label %checked.2, label %fail
 978
 979 checked.2:
 980   %c3 = icmp ne i32 %iv, 0
 981   br i1 %c3, label %backedge, label %fail
 982
 983 backedge:
 984   %iv.next = add i32 %iv, 758394
 985   %loop.cond = call i1 @cond_func()
 986   br i1 %loop.cond, label %loop, label %exit
 987
 988 fail:
 989   unreachable
 990
 991 exit:
 992   ret i32 %iv
 993 }
 994
 995 define i32 @func_26(i32 %start) {
 996 ; CHECK-LABEL: @func_26(
 997 ; CHECK-NEXT:  entry:
 998 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 999 ; CHECK:       loop:
1000 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
1001 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[IV]], 0
1002 ; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
1003 ; CHECK:       checked.1:
1004 ; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
1005 ; CHECK:       checked.2:
1006 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
1007 ; CHECK:       backedge:
1008 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
1009 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
1010 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
1011 ; CHECK:       fail:
1012 ; CHECK-NEXT:    unreachable
1013 ; CHECK:       exit:
1014 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
1015 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
1016 ;
1017 entry:
1018   br label %loop
1019
1020 loop:
1021   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
1022   %c1 = icmp slt i32 %iv, 0
1023   br i1 %c1, label %checked.1, label %fail
1024
1025 checked.1:
1026   %c2 = icmp slt i32 %iv, 1
1027   br i1 %c2, label %checked.2, label %fail
1028
1029 checked.2:
1030   %c3 = icmp slt i32 %iv, 2
1031   br i1 %c3, label %backedge, label %fail
1032
1033 backedge:
1034   %iv.next = add i32 %iv, 758394
1035   %loop.cond = call i1 @cond_func()
1036   br i1 %loop.cond, label %loop, label %exit
1037
1038 fail:
1039   unreachable
1040
1041 exit:
1042   ret i32 %iv
1043 }
1044
1045 define i32 @func_27(i32 %start) {
1046 ; CHECK-LABEL: @func_27(
1047 ; CHECK-NEXT:  entry:
1048 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1049 ; CHECK:       loop:
1050 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
1051 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[IV]], 2
1052 ; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[IV]], 1
1053 ; CHECK-NEXT:    [[C3:%.*]] = icmp slt i32 [[IV]], 0
1054 ; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
1055 ; CHECK:       checked.1:
1056 ; CHECK-NEXT:    br i1 [[C2]], label [[CHECKED_2:%.*]], label [[FAIL]]
1057 ; CHECK:       checked.2:
1058 ; CHECK-NEXT:    br i1 [[C3]], label [[BACKEDGE]], label [[FAIL]]
1059 ; CHECK:       backedge:
1060 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
1061 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
1062 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
1063 ; CHECK:       fail:
1064 ; CHECK-NEXT:    unreachable
1065 ; CHECK:       exit:
1066 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
1067 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
1068 ;
1069 entry:
1070   br label %loop
1071
1072 loop:
1073   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
1074   %c1 = icmp slt i32 %iv, 2
1075   %c2 = icmp slt i32 %iv, 1
1076   %c3 = icmp slt i32 %iv, 0
1077   br i1 %c1, label %checked.1, label %fail
1078
1079 checked.1:
1080   br i1 %c2, label %checked.2, label %fail
1081
1082 checked.2:
1083   br i1 %c3, label %backedge, label %fail
1084
1085 backedge:
1086   %iv.next = add i32 %iv, 758394
1087   %loop.cond = call i1 @cond_func()
1088   br i1 %loop.cond, label %loop, label %exit
1089
1090 fail:
1091   unreachable
1092
1093 exit:
1094   ret i32 %iv
1095 }
1096
1097 define i32 @func_28(i32 %start) {
1098 ; CHECK-LABEL: @func_28(
1099 ; CHECK-NEXT:  entry:
1100 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1101 ; CHECK:       loop:
1102 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
1103 ; CHECK-NEXT:    [[C1:%.*]] = icmp ne i32 [[IV]], 0
1104 ; CHECK-NEXT:    br i1 [[C1]], label [[CHECKED_1:%.*]], label [[FAIL:%.*]]
1105 ; CHECK:       checked.1:
1106 ; CHECK-NEXT:    br i1 true, label [[CHECKED_2:%.*]], label [[FAIL]]
1107 ; CHECK:       checked.2:
1108 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL]]
1109 ; CHECK:       backedge:
1110 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 758394
1111 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond_func()
1112 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
1113 ; CHECK:       fail:
1114 ; CHECK-NEXT:    unreachable
1115 ; CHECK:       exit:
1116 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
1117 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
1118 ;
1119 entry:
1120   br label %loop
1121
1122 loop:
1123   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
1124   %c1 = icmp ne i32 %iv, 0
1125   %c2 = icmp ne i32 %iv, 0
1126   %c3 = icmp ne i32 %iv, 0
1127   br i1 %c1, label %checked.1, label %fail
1128
1129 checked.1:
1130   br i1 %c2, label %checked.2, label %fail
1131
1132 checked.2:
1133   br i1 %c3, label %backedge, label %fail
1134
1135 backedge:
1136   %iv.next = add i32 %iv, 758394
1137   %loop.cond = call i1 @cond_func()
1138   br i1 %loop.cond, label %loop, label %exit
1139
1140 fail:
1141   unreachable
1142
1143 exit:
1144   ret i32 %iv
1145 }
1146
1147 !0 = !{i32 0, i32 2147483647}