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

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