llvm/test/Transforms/IndVarSimplify/X86/loop-invariant-conditions.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -S -passes=indvars -indvars-predicate-loops=0 %s | FileCheck %s
   3 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   4 target triple = "x86_64-unknown-linux-gnu"
   5
   6 define void @test1(i64 %start) {
   7 ; CHECK-LABEL: @test1(
   8 ; CHECK-NEXT:  entry:
   9 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  10 ; CHECK:       loop:
  11 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[START:%.*]], -1
  12 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
  13 ; CHECK:       for.end:
  14 ; CHECK-NEXT:    ret void
  15 ;
  16 entry:
  17   br label %loop
  18
  19 loop:
  20   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
  21   %indvars.iv.next = add nsw i64 %indvars.iv, 1
  22   %cmp1 = icmp slt i64 %indvars.iv, -1
  23   br i1 %cmp1, label %for.end, label %loop
  24
  25 for.end:                                          ; preds = %if.end, %entry
  26   ret void
  27 }
  28
  29 define void @test1.next(i64 %start) {
  30 ; CHECK-LABEL: @test1.next(
  31 ; CHECK-NEXT:  entry:
  32 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[START:%.*]], 1
  33 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  34 ; CHECK:       loop:
  35 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[TMP0]], 0
  36 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
  37 ; CHECK:       for.end:
  38 ; CHECK-NEXT:    ret void
  39 ;
  40 entry:
  41   br label %loop
  42
  43 loop:
  44   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
  45   %indvars.iv.next = add nsw i64 %indvars.iv, 1
  46   %cmp1 = icmp slt i64 %indvars.iv.next, 0
  47   br i1 %cmp1, label %for.end, label %loop
  48
  49 for.end:                                          ; preds = %if.end, %entry
  50   ret void
  51 }
  52
  53 define void @test2(i64 %start) {
  54 ; CHECK-LABEL: @test2(
  55 ; CHECK-NEXT:  entry:
  56 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  57 ; CHECK:       loop:
  58 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sle i64 [[START:%.*]], -1
  59 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
  60 ; CHECK:       for.end:
  61 ; CHECK-NEXT:    ret void
  62 ;
  63 entry:
  64   br label %loop
  65
  66 loop:
  67   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
  68   %indvars.iv.next = add nsw i64 %indvars.iv, 1
  69   %cmp1 = icmp sle i64 %indvars.iv, -1
  70   br i1 %cmp1, label %for.end, label %loop
  71
  72 for.end:                                          ; preds = %if.end, %entry
  73   ret void
  74 }
  75
  76 define void @test2.next(i64 %start) {
  77 ; CHECK-LABEL: @test2.next(
  78 ; CHECK-NEXT:  entry:
  79 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[START:%.*]], 1
  80 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  81 ; CHECK:       loop:
  82 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sle i64 [[TMP0]], 0
  83 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
  84 ; CHECK:       for.end:
  85 ; CHECK-NEXT:    ret void
  86 ;
  87 entry:
  88   br label %loop
  89
  90 loop:
  91   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
  92   %indvars.iv.next = add nsw i64 %indvars.iv, 1
  93   %cmp1 = icmp sle i64 %indvars.iv.next, 0
  94   br i1 %cmp1, label %for.end, label %loop
  95
  96 for.end:                                          ; preds = %if.end, %entry
  97   ret void
  98 }
  99
 100 ; As long as the test dominates the backedge, we're good
 101 define void @test3(i64 %start) {
 102 ; CHECK-LABEL: @test3(
 103 ; CHECK-NEXT:  entry:
 104 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 105 ; CHECK:       loop:
 106 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 107 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 108 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 109 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[FOR_END:%.*]]
 110 ; CHECK:       backedge:
 111 ; CHECK-NEXT:    call void @foo()
 112 ; CHECK-NEXT:    br i1 false, label [[FOR_END]], label [[LOOP]]
 113 ; CHECK:       for.end:
 114 ; CHECK-NEXT:    ret void
 115 ;
 116 entry:
 117   br label %loop
 118
 119 loop:
 120   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 121   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 122   %cmp = icmp eq i64 %indvars.iv.next, 25
 123   br i1 %cmp, label %backedge, label %for.end
 124
 125 backedge:
 126   ; prevent flattening, needed to make sure we're testing what we intend
 127   call void @foo()
 128   %cmp1 = icmp slt i64 %indvars.iv, -1
 129   br i1 %cmp1, label %for.end, label %loop
 130
 131 for.end:                                          ; preds = %if.end, %entry
 132   ret void
 133 }
 134
 135 define void @test3.next(i64 %start) {
 136 ; CHECK-LABEL: @test3.next(
 137 ; CHECK-NEXT:  entry:
 138 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 139 ; CHECK:       loop:
 140 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 141 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 142 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 143 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[FOR_END:%.*]]
 144 ; CHECK:       backedge:
 145 ; CHECK-NEXT:    call void @foo()
 146 ; CHECK-NEXT:    br i1 false, label [[FOR_END]], label [[LOOP]]
 147 ; CHECK:       for.end:
 148 ; CHECK-NEXT:    ret void
 149 ;
 150 entry:
 151   br label %loop
 152
 153 loop:
 154   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 155   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 156   %cmp = icmp eq i64 %indvars.iv.next, 25
 157   br i1 %cmp, label %backedge, label %for.end
 158
 159 backedge:
 160   ; prevent flattening, needed to make sure we're testing what we intend
 161   call void @foo()
 162   %cmp1 = icmp slt i64 %indvars.iv.next, 0
 163   br i1 %cmp1, label %for.end, label %loop
 164
 165 for.end:                                          ; preds = %if.end, %entry
 166   ret void
 167 }
 168
 169
 170 define void @test4(i64 %start) {
 171 ; CHECK-LABEL: @test4(
 172 ; CHECK-NEXT:  entry:
 173 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 174 ; CHECK:       loop:
 175 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 176 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 177 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 178 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[FOR_END:%.*]]
 179 ; CHECK:       backedge:
 180 ; CHECK-NEXT:    call void @foo()
 181 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[FOR_END]]
 182 ; CHECK:       for.end:
 183 ; CHECK-NEXT:    ret void
 184 ;
 185 entry:
 186   br label %loop
 187
 188 loop:
 189   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 190   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 191   %cmp = icmp eq i64 %indvars.iv.next, 25
 192   br i1 %cmp, label %backedge, label %for.end
 193
 194 backedge:
 195   ; prevent flattening, needed to make sure we're testing what we intend
 196   call void @foo()
 197   %cmp1 = icmp sgt i64 %indvars.iv, -1
 198   br i1 %cmp1, label %loop, label %for.end
 199
 200 for.end:                                          ; preds = %if.end, %entry
 201   ret void
 202 }
 203
 204 define void @test4.next(i64 %start) {
 205 ; CHECK-LABEL: @test4.next(
 206 ; CHECK-NEXT:  entry:
 207 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 208 ; CHECK:       loop:
 209 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 210 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 211 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 212 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[FOR_END:%.*]]
 213 ; CHECK:       backedge:
 214 ; CHECK-NEXT:    call void @foo()
 215 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[FOR_END]]
 216 ; CHECK:       for.end:
 217 ; CHECK-NEXT:    ret void
 218 ;
 219 entry:
 220   br label %loop
 221
 222 loop:
 223   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 224   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 225   %cmp = icmp eq i64 %indvars.iv.next, 25
 226   br i1 %cmp, label %backedge, label %for.end
 227
 228 backedge:
 229   ; prevent flattening, needed to make sure we're testing what we intend
 230   call void @foo()
 231   %cmp1 = icmp sgt i64 %indvars.iv.next, 0
 232   br i1 %cmp1, label %loop, label %for.end
 233
 234 for.end:                                          ; preds = %if.end, %entry
 235   ret void
 236 }
 237
 238 define void @test5(i64 %start) {
 239 ; CHECK-LABEL: @test5(
 240 ; CHECK-NEXT:  entry:
 241 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 242 ; CHECK:       loop:
 243 ; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw i64 [[START:%.*]], 1
 244 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 245 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
 246 ; CHECK:       backedge:
 247 ; CHECK-NEXT:    call void @foo()
 248 ; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[FOR_END]]
 249 ; CHECK:       for.end:
 250 ; CHECK-NEXT:    ret void
 251 ;
 252 entry:
 253   br label %loop
 254
 255 loop:
 256   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 257   %indvars.iv.next = add nuw i64 %indvars.iv, 1
 258   %cmp = icmp eq i64 %indvars.iv.next, 25
 259   br i1 %cmp, label %backedge, label %for.end
 260
 261 backedge:
 262   ; prevent flattening, needed to make sure we're testing what we intend
 263   call void @foo()
 264   %cmp1 = icmp ugt i64 %indvars.iv, 100
 265   br i1 %cmp1, label %loop, label %for.end
 266
 267 for.end:                                          ; preds = %if.end, %entry
 268   ret void
 269 }
 270
 271 define void @test5.next(i64 %start) {
 272 ; CHECK-LABEL: @test5.next(
 273 ; CHECK-NEXT:  entry:
 274 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 275 ; CHECK:       loop:
 276 ; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw i64 [[START:%.*]], 1
 277 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 278 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
 279 ; CHECK:       backedge:
 280 ; CHECK-NEXT:    call void @foo()
 281 ; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[FOR_END]]
 282 ; CHECK:       for.end:
 283 ; CHECK-NEXT:    ret void
 284 ;
 285 entry:
 286   br label %loop
 287
 288 loop:
 289   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 290   %indvars.iv.next = add nuw i64 %indvars.iv, 1
 291   %cmp = icmp eq i64 %indvars.iv.next, 25
 292   br i1 %cmp, label %backedge, label %for.end
 293
 294 backedge:
 295   ; prevent flattening, needed to make sure we're testing what we intend
 296   call void @foo()
 297   %cmp1 = icmp ugt i64 %indvars.iv.next, 101
 298   br i1 %cmp1, label %loop, label %for.end
 299
 300 for.end:                                          ; preds = %if.end, %entry
 301   ret void
 302 }
 303
 304
 305 define void @test6(i64 %start) {
 306 ; CHECK-LABEL: @test6(
 307 ; CHECK-NEXT:  entry:
 308 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 309 ; CHECK:       loop:
 310 ; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw i64 [[START:%.*]], 1
 311 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 312 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
 313 ; CHECK:       backedge:
 314 ; CHECK-NEXT:    call void @foo()
 315 ; CHECK-NEXT:    br i1 true, label [[FOR_END]], label [[LOOP]]
 316 ; CHECK:       for.end:
 317 ; CHECK-NEXT:    ret void
 318 ;
 319 entry:
 320   br label %loop
 321
 322 loop:
 323   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 324   %indvars.iv.next = add nuw i64 %indvars.iv, 1
 325   %cmp = icmp eq i64 %indvars.iv.next, 25
 326   br i1 %cmp, label %backedge, label %for.end
 327
 328 backedge:
 329   ; prevent flattening, needed to make sure we're testing what we intend
 330   call void @foo()
 331   %cmp1 = icmp ult i64 %indvars.iv, 100
 332   br i1 %cmp1, label %for.end, label %loop
 333
 334 for.end:                                          ; preds = %if.end, %entry
 335   ret void
 336 }
 337
 338 define void @test6.next(i64 %start) {
 339 ; CHECK-LABEL: @test6.next(
 340 ; CHECK-NEXT:  entry:
 341 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 342 ; CHECK:       loop:
 343 ; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw i64 [[START:%.*]], 1
 344 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 345 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
 346 ; CHECK:       backedge:
 347 ; CHECK-NEXT:    call void @foo()
 348 ; CHECK-NEXT:    br i1 true, label [[FOR_END]], label [[LOOP]]
 349 ; CHECK:       for.end:
 350 ; CHECK-NEXT:    ret void
 351 ;
 352 entry:
 353   br label %loop
 354
 355 loop:
 356   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 357   %indvars.iv.next = add nuw i64 %indvars.iv, 1
 358   %cmp = icmp eq i64 %indvars.iv.next, 25
 359   br i1 %cmp, label %backedge, label %for.end
 360
 361 backedge:
 362   ; prevent flattening, needed to make sure we're testing what we intend
 363   call void @foo()
 364   %cmp1 = icmp ult i64 %indvars.iv.next, 101
 365   br i1 %cmp1, label %for.end, label %loop
 366
 367 for.end:                                          ; preds = %if.end, %entry
 368   ret void
 369 }
 370
 371 define void @test7(i64 %start, ptr %inc_ptr) {
 372 ; CHECK-LABEL: @test7(
 373 ; CHECK-NEXT:  entry:
 374 ; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG0:![0-9]+]]
 375 ; CHECK-NEXT:    [[OK:%.*]] = icmp sge i64 [[INC]], 0
 376 ; CHECK-NEXT:    br i1 [[OK]], label [[LOOP_PREHEADER:%.*]], label [[FOR_END:%.*]]
 377 ; CHECK:       loop.preheader:
 378 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 379 ; CHECK:       loop:
 380 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[START:%.*]], -1
 381 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END_LOOPEXIT:%.*]], label [[LOOP]]
 382 ; CHECK:       for.end.loopexit:
 383 ; CHECK-NEXT:    br label [[FOR_END]]
 384 ; CHECK:       for.end:
 385 ; CHECK-NEXT:    ret void
 386 ;
 387 entry:
 388   %inc = load i64, ptr %inc_ptr, !range !0
 389   %ok = icmp sge i64 %inc, 0
 390   br i1 %ok, label %loop, label %for.end
 391
 392 loop:
 393   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
 394   %indvars.iv.next = add nsw i64 %indvars.iv, %inc
 395   %cmp1 = icmp slt i64 %indvars.iv, -1
 396   br i1 %cmp1, label %for.end, label %loop
 397
 398 for.end:                                          ; preds = %if.end, %entry
 399   ret void
 400 }
 401
 402 define void @test7.next(i64 %start, ptr %inc_ptr) {
 403 ; CHECK-LABEL: @test7.next(
 404 ; CHECK-NEXT:  entry:
 405 ; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG0]]
 406 ; CHECK-NEXT:    [[OK:%.*]] = icmp sge i64 [[INC]], 0
 407 ; CHECK-NEXT:    br i1 [[OK]], label [[LOOP_PREHEADER:%.*]], label [[FOR_END:%.*]]
 408 ; CHECK:       loop.preheader:
 409 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[INC]], [[START:%.*]]
 410 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 411 ; CHECK:       loop:
 412 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[TMP0]], 0
 413 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END_LOOPEXIT:%.*]], label [[LOOP]]
 414 ; CHECK:       for.end.loopexit:
 415 ; CHECK-NEXT:    br label [[FOR_END]]
 416 ; CHECK:       for.end:
 417 ; CHECK-NEXT:    ret void
 418 ;
 419 entry:
 420   %inc = load i64, ptr %inc_ptr, !range !0
 421   %ok = icmp sge i64 %inc, 0
 422   br i1 %ok, label %loop, label %for.end
 423
 424 loop:
 425   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
 426   %indvars.iv.next = add nsw i64 %indvars.iv, %inc
 427   %cmp1 = icmp slt i64 %indvars.iv.next, 0
 428   br i1 %cmp1, label %for.end, label %loop
 429
 430 for.end:                                          ; preds = %if.end, %entry
 431   ret void
 432 }
 433
 434 ; Negative test - we can't show that the internal branch executes, so we can't
 435 ; fold the test to a loop invariant one.
 436 define void @test1_neg(i64 %start) {
 437 ; CHECK-LABEL: @test1_neg(
 438 ; CHECK-NEXT:  entry:
 439 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 440 ; CHECK:       loop:
 441 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 442 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 443 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 444 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[SKIP:%.*]]
 445 ; CHECK:       skip:
 446 ; CHECK-NEXT:    call void @foo()
 447 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
 448 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[BACKEDGE]]
 449 ; CHECK:       backedge:
 450 ; CHECK-NEXT:    call void @foo()
 451 ; CHECK-NEXT:    br label [[LOOP]]
 452 ; CHECK:       for.end:
 453 ; CHECK-NEXT:    ret void
 454 ;
 455 entry:
 456   br label %loop
 457
 458 loop:
 459   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 460   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 461   %cmp = icmp eq i64 %indvars.iv.next, 25
 462   br i1 %cmp, label %backedge, label %skip
 463 skip:
 464   ; prevent flattening, needed to make sure we're testing what we intend
 465   call void @foo()
 466   %cmp1 = icmp slt i64 %indvars.iv, -1
 467   br i1 %cmp1, label %for.end, label %backedge
 468 backedge:
 469   ; prevent flattening, needed to make sure we're testing what we intend
 470   call void @foo()
 471   br label %loop
 472
 473 for.end:                                          ; preds = %if.end, %entry
 474   ret void
 475 }
 476
 477 ; Slightly subtle version of @test4 where the icmp dominates the backedge,
 478 ; but the exit branch doesn't.
 479 define void @test2_neg(i64 %start) {
 480 ; CHECK-LABEL: @test2_neg(
 481 ; CHECK-NEXT:  entry:
 482 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 483 ; CHECK:       loop:
 484 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 485 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 486 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 487 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
 488 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE]], label [[SKIP:%.*]]
 489 ; CHECK:       skip:
 490 ; CHECK-NEXT:    call void @foo()
 491 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[BACKEDGE]]
 492 ; CHECK:       backedge:
 493 ; CHECK-NEXT:    call void @foo()
 494 ; CHECK-NEXT:    br label [[LOOP]]
 495 ; CHECK:       for.end:
 496 ; CHECK-NEXT:    ret void
 497 ;
 498 entry:
 499   br label %loop
 500
 501 loop:
 502   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 503   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 504   %cmp = icmp eq i64 %indvars.iv.next, 25
 505   %cmp1 = icmp slt i64 %indvars.iv, -1
 506   br i1 %cmp, label %backedge, label %skip
 507 skip:
 508   ; prevent flattening, needed to make sure we're testing what we intend
 509   call void @foo()
 510   br i1 %cmp1, label %for.end, label %backedge
 511 backedge:
 512   ; prevent flattening, needed to make sure we're testing what we intend
 513   call void @foo()
 514   br label %loop
 515
 516 for.end:                                          ; preds = %if.end, %entry
 517   ret void
 518 }
 519
 520 ; The branch has to exit the loop if the condition is true
 521 define void @test3_neg(i64 %start) {
 522 ; CHECK-LABEL: @test3_neg(
 523 ; CHECK-NEXT:  entry:
 524 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 525 ; CHECK:       loop:
 526 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
 527 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 528 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
 529 ; CHECK-NEXT:    br i1 [[CMP1]], label [[LOOP]], label [[FOR_END:%.*]]
 530 ; CHECK:       for.end:
 531 ; CHECK-NEXT:    ret void
 532 ;
 533 entry:
 534   br label %loop
 535
 536 loop:
 537   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
 538   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 539   %cmp1 = icmp slt i64 %indvars.iv, -1
 540   br i1 %cmp1, label %loop, label %for.end
 541
 542 for.end:                                          ; preds = %if.end, %entry
 543   ret void
 544 }
 545
 546 define void @test4_neg(i64 %start) {
 547 ; CHECK-LABEL: @test4_neg(
 548 ; CHECK-NEXT:  entry:
 549 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 550 ; CHECK:       loop:
 551 ; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nsw i64 [[START:%.*]], 1
 552 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 25
 553 ; CHECK-NEXT:    br i1 [[CMP]], label [[BACKEDGE:%.*]], label [[FOR_END:%.*]]
 554 ; CHECK:       backedge:
 555 ; CHECK-NEXT:    call void @foo()
 556 ; CHECK-NEXT:    br i1 true, label [[FOR_END]], label [[LOOP]]
 557 ; CHECK:       for.end:
 558 ; CHECK-NEXT:    ret void
 559 ;
 560 entry:
 561   br label %loop
 562
 563 loop:
 564   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 565   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 566   %cmp = icmp eq i64 %indvars.iv.next, 25
 567   br i1 %cmp, label %backedge, label %for.end
 568
 569 backedge:
 570   ; prevent flattening, needed to make sure we're testing what we intend
 571   call void @foo()
 572   %cmp1 = icmp sgt i64 %indvars.iv, -1
 573
 574 ; %cmp1 can be made loop invariant only if the branch below goes to
 575 ; %the header when %cmp1 is true.
 576   br i1 %cmp1, label %for.end, label %loop
 577
 578 for.end:                                          ; preds = %if.end, %entry
 579   ret void
 580 }
 581
 582 define void @test5_neg(i64 %start, i64 %inc) {
 583 ; CHECK-LABEL: @test5_neg(
 584 ; CHECK-NEXT:  entry:
 585 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 586 ; CHECK:       loop:
 587 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
 588 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], [[INC:%.*]]
 589 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
 590 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
 591 ; CHECK:       for.end:
 592 ; CHECK-NEXT:    ret void
 593 ;
 594 entry:
 595   br label %loop
 596
 597 loop:
 598   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
 599   %indvars.iv.next = add nsw i64 %indvars.iv, %inc
 600   %cmp1 = icmp slt i64 %indvars.iv, -1
 601   br i1 %cmp1, label %for.end, label %loop
 602
 603 for.end:                                          ; preds = %if.end, %entry
 604   ret void
 605 }
 606
 607 define void @test8(i64 %start, ptr %inc_ptr) {
 608 ; CHECK-LABEL: @test8(
 609 ; CHECK-NEXT:  entry:
 610 ; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG1:![0-9]+]]
 611 ; CHECK-NEXT:    [[OK:%.*]] = icmp sge i64 [[INC]], 0
 612 ; CHECK-NEXT:    br i1 [[OK]], label [[LOOP_PREHEADER:%.*]], label [[FOR_END:%.*]]
 613 ; CHECK:       loop.preheader:
 614 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 615 ; CHECK:       loop:
 616 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ [[START:%.*]], [[LOOP_PREHEADER]] ]
 617 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], [[INC]]
 618 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[INDVARS_IV]], -1
 619 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END_LOOPEXIT:%.*]], label [[LOOP]]
 620 ; CHECK:       for.end.loopexit:
 621 ; CHECK-NEXT:    br label [[FOR_END]]
 622 ; CHECK:       for.end:
 623 ; CHECK-NEXT:    ret void
 624 ;
 625 entry:
 626   %inc = load i64, ptr %inc_ptr, !range !1
 627   %ok = icmp sge i64 %inc, 0
 628   br i1 %ok, label %loop, label %for.end
 629
 630 loop:
 631   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
 632   %indvars.iv.next = add nsw i64 %indvars.iv, %inc
 633   %cmp1 = icmp slt i64 %indvars.iv, -1
 634   br i1 %cmp1, label %for.end, label %loop
 635
 636 for.end:                                          ; preds = %if.end, %entry
 637   ret void
 638 }
 639
 640 ; check to handle loops without preheaders, but invariant operands
 641 ; (we handle this today by inserting a preheader)
 642 define void @test9(i1 %cnd, i64 %start) {
 643 ; CHECK-LABEL: @test9(
 644 ; CHECK-NEXT:  entry:
 645 ; CHECK-NEXT:    br i1 [[CND:%.*]], label [[ENTRY1:%.*]], label [[ENTRY2:%.*]]
 646 ; CHECK:       entry1:
 647 ; CHECK-NEXT:    br label [[LOOP_PREHEADER:%.*]]
 648 ; CHECK:       entry2:
 649 ; CHECK-NEXT:    br label [[LOOP_PREHEADER]]
 650 ; CHECK:       loop.preheader:
 651 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 652 ; CHECK:       loop:
 653 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i64 [[START:%.*]], -1
 654 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_END:%.*]], label [[LOOP]]
 655 ; CHECK:       for.end:
 656 ; CHECK-NEXT:    ret void
 657 ;
 658 entry:
 659   br i1 %cnd, label %entry1, label %entry2
 660 entry1:
 661   br label %loop
 662 entry2:
 663   br label %loop
 664 loop:
 665   %indvars.iv = phi i64 [ %start, %entry1 ],[ %start, %entry2 ], [ %indvars.iv.next, %loop ]
 666   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 667   %cmp1 = icmp slt i64 %indvars.iv, -1
 668   br i1 %cmp1, label %for.end, label %loop
 669
 670 for.end:                                          ; preds = %if.end, %entry
 671   ret void
 672 }
 673
 674 declare void @use(i1 %x)
 675
 676 ; check that we handle conditions with loop invariant operands which
 677 ; *aren't* in the header - this is a very rare and fragile case where
 678 ; we have a "loop" which is known to run exactly one iteration but
 679 ; haven't yet simplified the uses of the IV
 680 define void @test10() {
 681 ; CHECK-LABEL: @test10(
 682 ; CHECK-NEXT:  entry:
 683 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 684 ; CHECK:       loop:
 685 ; CHECK-NEXT:    br i1 false, label [[LEFT:%.*]], label [[RIGHT:%.*]]
 686 ; CHECK:       left:
 687 ; CHECK-NEXT:    br label [[LATCH:%.*]]
 688 ; CHECK:       right:
 689 ; CHECK-NEXT:    br label [[LATCH]]
 690 ; CHECK:       latch:
 691 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 -1, undef
 692 ; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[LOOP]]
 693 ; CHECK:       exit:
 694 ; CHECK-NEXT:    [[CMP_LCSSA:%.*]] = phi i1 [ [[CMP]], [[LATCH]] ]
 695 ; CHECK-NEXT:    call void @use(i1 [[CMP_LCSSA]])
 696 ; CHECK-NEXT:    ret void
 697 ;
 698 entry:
 699   br label %loop
 700
 701 loop:
 702   %phi1 = phi i32 [ %phi2, %latch ], [ 0, %entry ]
 703   %dec = add i32 %phi1, -1
 704   br i1 false, label %left, label %right
 705
 706 left:
 707   br label %latch
 708
 709 right:
 710   br label %latch
 711
 712 latch:
 713   %phi2 = phi i32 [ %phi1, %left ], [ %dec, %right ]
 714   %cmp = icmp slt i32 %phi2, undef
 715   br i1 true, label %exit, label %loop
 716
 717 exit:
 718   call void @use(i1 %cmp)
 719   ret void
 720 }
 721
 722 ; check that we can figure out that iv.next > 1 from the facts that iv >= 0 and
 723 ; iv.start != 0.
 724 define void @test11(ptr %inc_ptr) {
 725 ; CHECK-LABEL: @test11(
 726 ; CHECK-NEXT:  entry:
 727 ; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG0]]
 728 ; CHECK-NEXT:    [[NE_COND:%.*]] = icmp ne i64 [[INC]], 0
 729 ; CHECK-NEXT:    br i1 [[NE_COND]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 730 ; CHECK:       loop.preheader:
 731 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 732 ; CHECK:       loop:
 733 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[INC]], [[LOOP_PREHEADER]] ]
 734 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
 735 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 736 ; CHECK:       if.true:
 737 ; CHECK-NEXT:    br label [[BACKEDGE]]
 738 ; CHECK:       if.false:
 739 ; CHECK-NEXT:    br label [[BACKEDGE]]
 740 ; CHECK:       backedge:
 741 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], 201
 742 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
 743 ; CHECK:       exit.loopexit:
 744 ; CHECK-NEXT:    br label [[EXIT]]
 745 ; CHECK:       exit:
 746 ; CHECK-NEXT:    ret void
 747 ;
 748 entry:
 749   %inc = load i64, ptr %inc_ptr, !range !0
 750   %ne.cond = icmp ne i64 %inc, 0
 751   br i1 %ne.cond, label %loop, label %exit
 752
 753 loop:
 754   %iv = phi i64 [ %inc, %entry ], [ %iv.next, %backedge ]
 755   %iv.next = add i64 %iv, 1
 756   %brcond = icmp sgt i64 %iv.next, 1
 757   br i1 %brcond, label %if.true, label %if.false
 758
 759 if.true:
 760   br label %backedge
 761
 762 if.false:
 763   br label %backedge
 764
 765 backedge:
 766   %loopcond = icmp slt i64 %iv, 200
 767   br i1 %loopcond, label %loop, label %exit
 768
 769 exit:
 770   ret void
 771 }
 772
 773 ; check that we can prove that a recurrency is greater than another recurrency
 774 ; in the same loop, with the same step, and with smaller starting value.
 775 define void @test12(ptr %inc_ptr) {
 776 ; CHECK-LABEL: @test12(
 777 ; CHECK-NEXT:  entry:
 778 ; CHECK-NEXT:    [[INC:%.*]] = load i64, ptr [[INC_PTR:%.*]], align 8, !range [[RNG0]]
 779 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 780 ; CHECK:       loop:
 781 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ [[INC]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 782 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
 783 ; CHECK-NEXT:    br i1 true, label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 784 ; CHECK:       if.true:
 785 ; CHECK-NEXT:    br label [[BACKEDGE]]
 786 ; CHECK:       if.false:
 787 ; CHECK-NEXT:    br label [[BACKEDGE]]
 788 ; CHECK:       backedge:
 789 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], 201
 790 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
 791 ; CHECK:       exit:
 792 ; CHECK-NEXT:    ret void
 793 ;
 794 entry:
 795   %inc = load i64, ptr %inc_ptr, !range !0
 796   %inc.minus.1 = sub i64 %inc, 1
 797   br label %loop
 798
 799 loop:
 800   %iv = phi i64 [ %inc, %entry ], [ %iv.next, %backedge ]
 801   %iv.minus.1 = phi i64 [ %inc.minus.1, %entry ], [ %iv.minus.1.next, %backedge ]
 802   %iv.next = add i64 %iv, 1
 803   %iv.minus.1.next = add i64 %iv.minus.1, 1
 804   %brcond = icmp sgt i64 %iv.next, %iv.minus.1.next
 805   br i1 %brcond, label %if.true, label %if.false
 806
 807 if.true:
 808   br label %backedge
 809
 810 if.false:
 811   br label %backedge
 812
 813 backedge:
 814   %loopcond = icmp slt i64 %iv, 200
 815   br i1 %loopcond, label %loop, label %exit
 816
 817 exit:
 818   ret void
 819 }
 820
 821 !0 = !{i64 0, i64 100}
 822 !1 = !{i64 -1, i64 100}
 823
 824 declare void @foo()