llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -passes=indvars -S < %s | FileCheck %s
   3
   4 declare i1 @cond()
   5
   6 ; Range check here can be turned into invariant check.
   7 define i32 @test_simple_case(i32 %start, i32 %len) {
   8 ; CHECK-LABEL: @test_simple_case(
   9 ; CHECK-NEXT:  entry:
  10 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
  11 ; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
  12 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  13 ; CHECK:       loop:
  14 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
  15 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
  16 ; CHECK-NEXT:    br i1 [[ZERO_CHECK]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
  17 ; CHECK:       range_check_block:
  18 ; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
  19 ; CHECK:       backedge:
  20 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
  21 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
  22 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
  23 ; CHECK:       done:
  24 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
  25 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
  26 ; CHECK:       failed_1:
  27 ; CHECK-NEXT:    ret i32 -1
  28 ; CHECK:       failed_2:
  29 ; CHECK-NEXT:    ret i32 -2
  30 ;
  31 entry:
  32   br label %loop
  33
  34 loop:
  35   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
  36   %zero_check = icmp ne i32 %iv, 0
  37   br i1 %zero_check, label %range_check_block, label %failed_1
  38
  39 range_check_block:
  40   %iv.minus.1 = add i32 %iv, -1
  41   %range_check = icmp ult i32 %iv.minus.1, %len
  42   br i1 %range_check, label %backedge, label %failed_2
  43
  44 backedge:
  45   %iv.next = add i32 %iv, -1
  46   %loop_cond = call i1 @cond()
  47   br i1 %loop_cond, label %done, label %loop
  48
  49 done:
  50   ret i32 %iv
  51
  52 failed_1:
  53   ret i32 -1
  54
  55 failed_2:
  56   ret i32 -2
  57 }
  58
  59 ; This example is equivalent to @test_simple_case, with only difference that
  60 ; both checks are littered with extra irrelevant conditions. We should be able
  61 ; to replace it with invariant despite this fact.
  62 ; https://alive2.llvm.org/ce/z/G4iW8c
  63 define i32 @test_litter_conditions(i32 %start, i32 %len) {
  64 ; CHECK-LABEL: @test_litter_conditions(
  65 ; CHECK-NEXT:  entry:
  66 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
  67 ; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
  68 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  69 ; CHECK:       loop:
  70 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
  71 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
  72 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
  73 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
  74 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
  75 ; CHECK:       range_check_block:
  76 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
  77 ; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]]
  78 ; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
  79 ; CHECK:       backedge:
  80 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
  81 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
  82 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
  83 ; CHECK:       done:
  84 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
  85 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
  86 ; CHECK:       failed_1:
  87 ; CHECK-NEXT:    ret i32 -1
  88 ; CHECK:       failed_2:
  89 ; CHECK-NEXT:    ret i32 -2
  90 ;
  91 entry:
  92   br label %loop
  93
  94 loop:
  95   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
  96   %zero_check = icmp ne i32 %iv, 0
  97   %fake_1 = call i1 @cond()
  98   %and_1 = and i1 %zero_check, %fake_1
  99   br i1 %and_1, label %range_check_block, label %failed_1
 100
 101 range_check_block:
 102   %iv.minus.1 = add i32 %iv, -1
 103   %range_check = icmp ult i32 %iv.minus.1, %len
 104   %fake_2 = call i1 @cond()
 105   %and_2 = and i1 %range_check, %fake_2
 106   br i1 %and_2, label %backedge, label %failed_2
 107
 108 backedge:
 109   %iv.next = add i32 %iv, -1
 110   %loop_cond = call i1 @cond()
 111   br i1 %loop_cond, label %done, label %loop
 112
 113 done:
 114   ret i32 %iv
 115
 116 failed_1:
 117   ret i32 -1
 118
 119 failed_2:
 120   ret i32 -2
 121 }
 122
 123 ; Same as test_litter_conditions, but swapped exit block branches
 124 ; and exit condition expressed by OR. Still optimizable.
 125 define i32 @test_litter_conditions_inverse(i32 %start, i32 %len) {
 126 ; CHECK-LABEL: @test_litter_conditions_inverse(
 127 ; CHECK-NEXT:  entry:
 128 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 129 ; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 130 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 131 ; CHECK:       loop:
 132 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 133 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 134 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 135 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 136 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 137 ; CHECK:       range_check_block:
 138 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
 139 ; CHECK-NEXT:    [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], [[FAKE_2]]
 140 ; CHECK-NEXT:    br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 141 ; CHECK:       backedge:
 142 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 143 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 144 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 145 ; CHECK:       done:
 146 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 147 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 148 ; CHECK:       failed_1:
 149 ; CHECK-NEXT:    ret i32 -1
 150 ; CHECK:       failed_2:
 151 ; CHECK-NEXT:    ret i32 -2
 152 ;
 153 entry:
 154   br label %loop
 155
 156 loop:
 157   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 158   %zero_check = icmp ne i32 %iv, 0
 159   %fake_1 = call i1 @cond()
 160   %and_1 = and i1 %zero_check, %fake_1
 161   br i1 %and_1, label %range_check_block, label %failed_1
 162
 163 range_check_block:
 164   %iv.minus.1 = add i32 %iv, -1
 165   %range_check_failed = icmp uge i32 %iv.minus.1, %len
 166   %fake_2 = call i1 @cond()
 167   %or_2 = or i1 %range_check_failed, %fake_2
 168   br i1 %or_2, label %failed_2, label %backedge
 169
 170 backedge:
 171   %iv.next = add i32 %iv, -1
 172   %loop_cond = call i1 @cond()
 173   br i1 %loop_cond, label %done, label %loop
 174
 175 done:
 176   ret i32 %iv
 177
 178 failed_1:
 179   ret i32 -1
 180
 181 failed_2:
 182   ret i32 -2
 183 }
 184
 185 define i32 @test_litter_conditions_01(i32 %start, i32 %len) {
 186 ; CHECK-LABEL: @test_litter_conditions_01(
 187 ; CHECK-NEXT:  entry:
 188 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 189 ; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 190 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 191 ; CHECK:       loop:
 192 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 193 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 194 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 195 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 196 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 197 ; CHECK:       range_check_block:
 198 ; CHECK-NEXT:    br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 199 ; CHECK:       backedge:
 200 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 201 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 202 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 203 ; CHECK:       done:
 204 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 205 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 206 ; CHECK:       failed_1:
 207 ; CHECK-NEXT:    ret i32 -1
 208 ; CHECK:       failed_2:
 209 ; CHECK-NEXT:    ret i32 -2
 210 ;
 211 entry:
 212   br label %loop
 213
 214 loop:
 215   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 216   %zero_check = icmp ne i32 %iv, 0
 217   %fake_1 = call i1 @cond()
 218   %and_1 = and i1 %zero_check, %fake_1
 219   br i1 %and_1, label %range_check_block, label %failed_1
 220
 221 range_check_block:
 222   %iv.minus.1 = add i32 %iv, -1
 223   %range_check = icmp ult i32 %iv.minus.1, %len
 224   br i1 %range_check, label %backedge, label %failed_2
 225
 226 backedge:
 227   %iv.next = add i32 %iv, -1
 228   %loop_cond = call i1 @cond()
 229   br i1 %loop_cond, label %done, label %loop
 230
 231 done:
 232   ret i32 %iv
 233
 234 failed_1:
 235   ret i32 -1
 236
 237 failed_2:
 238   ret i32 -2
 239 }
 240
 241 ; Same as test_litter_conditions_01, but swapped exit block branches
 242 ; and condition expressed by OR. Still optimizable.
 243 define i32 @test_litter_conditions_01_inverse(i32 %start, i32 %len) {
 244 ; CHECK-LABEL: @test_litter_conditions_01_inverse(
 245 ; CHECK-NEXT:  entry:
 246 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 247 ; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 248 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 249 ; CHECK:       loop:
 250 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 251 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 252 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 253 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 254 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 255 ; CHECK:       range_check_block:
 256 ; CHECK-NEXT:    br i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 257 ; CHECK:       backedge:
 258 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 259 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 260 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 261 ; CHECK:       done:
 262 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 263 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 264 ; CHECK:       failed_1:
 265 ; CHECK-NEXT:    ret i32 -1
 266 ; CHECK:       failed_2:
 267 ; CHECK-NEXT:    ret i32 -2
 268 ;
 269 entry:
 270   br label %loop
 271
 272 loop:
 273   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 274   %zero_check = icmp ne i32 %iv, 0
 275   %fake_1 = call i1 @cond()
 276   %and_1 = and i1 %zero_check, %fake_1
 277   br i1 %and_1, label %range_check_block, label %failed_1
 278
 279 range_check_block:
 280   %iv.minus.1 = add i32 %iv, -1
 281   %range_check_failed = icmp uge i32 %iv.minus.1, %len
 282   br i1 %range_check_failed, label %failed_2, label %backedge
 283
 284 backedge:
 285   %iv.next = add i32 %iv, -1
 286   %loop_cond = call i1 @cond()
 287   br i1 %loop_cond, label %done, label %loop
 288
 289 done:
 290   ret i32 %iv
 291
 292 failed_1:
 293   ret i32 -1
 294
 295 failed_2:
 296   ret i32 -2
 297 }
 298
 299 ; TODO: Simplified version 2 of test_litter_conditions.
 300 define i32 @test_litter_conditions_02(i32 %start, i32 %len) {
 301 ; CHECK-LABEL: @test_litter_conditions_02(
 302 ; CHECK-NEXT:  entry:
 303 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 304 ; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 305 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 306 ; CHECK:       loop:
 307 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 308 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 309 ; CHECK-NEXT:    br i1 [[ZERO_CHECK]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 310 ; CHECK:       range_check_block:
 311 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
 312 ; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]]
 313 ; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 314 ; CHECK:       backedge:
 315 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 316 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 317 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 318 ; CHECK:       done:
 319 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 320 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 321 ; CHECK:       failed_1:
 322 ; CHECK-NEXT:    ret i32 -1
 323 ; CHECK:       failed_2:
 324 ; CHECK-NEXT:    ret i32 -2
 325 ;
 326 entry:
 327   br label %loop
 328
 329 loop:
 330   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 331   %zero_check = icmp ne i32 %iv, 0
 332   br i1 %zero_check, label %range_check_block, label %failed_1
 333
 334 range_check_block:
 335   %iv.minus.1 = add i32 %iv, -1
 336   %range_check = icmp ult i32 %iv.minus.1, %len
 337   %fake_2 = call i1 @cond()
 338   %and_2 = and i1 %range_check, %fake_2
 339   br i1 %and_2, label %backedge, label %failed_2
 340
 341 backedge:
 342   %iv.next = add i32 %iv, -1
 343   %loop_cond = call i1 @cond()
 344   br i1 %loop_cond, label %done, label %loop
 345
 346 done:
 347   ret i32 %iv
 348
 349 failed_1:
 350   ret i32 -1
 351
 352 failed_2:
 353   ret i32 -2
 354 }
 355
 356 ; Same as test_litter_conditions_02, but swapped exit block branches,
 357 ; and condition is expressed as OR. Still optimizable.
 358 define i32 @test_litter_conditions_02_inverse(i32 %start, i32 %len) {
 359 ; CHECK-LABEL: @test_litter_conditions_02_inverse(
 360 ; CHECK-NEXT:  entry:
 361 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 362 ; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 363 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 364 ; CHECK:       loop:
 365 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 366 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 367 ; CHECK-NEXT:    br i1 [[ZERO_CHECK]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 368 ; CHECK:       range_check_block:
 369 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
 370 ; CHECK-NEXT:    [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], [[FAKE_2]]
 371 ; CHECK-NEXT:    br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 372 ; CHECK:       backedge:
 373 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 374 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 375 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 376 ; CHECK:       done:
 377 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 378 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 379 ; CHECK:       failed_1:
 380 ; CHECK-NEXT:    ret i32 -1
 381 ; CHECK:       failed_2:
 382 ; CHECK-NEXT:    ret i32 -2
 383 ;
 384 entry:
 385   br label %loop
 386
 387 loop:
 388   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 389   %zero_check = icmp ne i32 %iv, 0
 390   br i1 %zero_check, label %range_check_block, label %failed_1
 391
 392 range_check_block:
 393   %iv.minus.1 = add i32 %iv, -1
 394   %range_check_failed = icmp uge i32 %iv.minus.1, %len
 395   %fake_2 = call i1 @cond()
 396   %or_2 = or i1 %range_check_failed, %fake_2
 397   br i1 %or_2, label %failed_2, label %backedge
 398
 399 backedge:
 400   %iv.next = add i32 %iv, -1
 401   %loop_cond = call i1 @cond()
 402   br i1 %loop_cond, label %done, label %loop
 403
 404 done:
 405   ret i32 %iv
 406
 407 failed_1:
 408   ret i32 -1
 409
 410 failed_2:
 411   ret i32 -2
 412 }
 413
 414 ; Same as @test_litter_conditions, but all conditions are computed in
 415 ; header block. Make sure we infer fact from the right context.
 416 ; https://alive2.llvm.org/ce/z/JiD-Pw
 417 define i32 @test_litter_conditions_bad_context(i32 %start, i32 %len) {
 418 ; CHECK-LABEL: @test_litter_conditions_bad_context(
 419 ; CHECK-NEXT:  entry:
 420 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 421 ; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 422 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 423 ; CHECK:       loop:
 424 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 425 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 426 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 427 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 428 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
 429 ; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]]
 430 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 431 ; CHECK:       range_check_block:
 432 ; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 433 ; CHECK:       backedge:
 434 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 435 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 436 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 437 ; CHECK:       done:
 438 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 439 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 440 ; CHECK:       failed_1:
 441 ; CHECK-NEXT:    ret i32 -1
 442 ; CHECK:       failed_2:
 443 ; CHECK-NEXT:    ret i32 -2
 444 ;
 445 entry:
 446   br label %loop
 447
 448 loop:
 449   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 450   %zero_check = icmp ne i32 %iv, 0
 451   %fake_1 = call i1 @cond()
 452   %and_1 = and i1 %zero_check, %fake_1
 453   %iv.minus.1 = add i32 %iv, -1
 454   %range_check = icmp ult i32 %iv.minus.1, %len
 455   %fake_2 = call i1 @cond()
 456   %and_2 = and i1 %range_check, %fake_2
 457   br i1 %and_1, label %range_check_block, label %failed_1
 458
 459 range_check_block:
 460   br i1 %and_2, label %backedge, label %failed_2
 461
 462 backedge:
 463   %iv.next = add i32 %iv, -1
 464   %loop_cond = call i1 @cond()
 465   br i1 %loop_cond, label %done, label %loop
 466
 467 done:
 468   ret i32 %iv
 469
 470 failed_1:
 471   ret i32 -1
 472
 473 failed_2:
 474   ret i32 -2
 475 }
 476
 477 ; Same as @test_litter_conditions_bad_context, but swapped exit block branches,
 478 ; and conditions expressed as OR. Still optimizable.
 479 define i32 @test_litter_conditions_bad_context_inverse(i32 %start, i32 %len) {
 480 ; CHECK-LABEL: @test_litter_conditions_bad_context_inverse(
 481 ; CHECK-NEXT:  entry:
 482 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 483 ; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 484 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 485 ; CHECK:       loop:
 486 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 487 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 488 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 489 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 490 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
 491 ; CHECK-NEXT:    [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], [[FAKE_2]]
 492 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 493 ; CHECK:       range_check_block:
 494 ; CHECK-NEXT:    br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 495 ; CHECK:       backedge:
 496 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 497 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 498 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 499 ; CHECK:       done:
 500 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 501 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 502 ; CHECK:       failed_1:
 503 ; CHECK-NEXT:    ret i32 -1
 504 ; CHECK:       failed_2:
 505 ; CHECK-NEXT:    ret i32 -2
 506 ;
 507 entry:
 508   br label %loop
 509
 510 loop:
 511   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 512   %zero_check = icmp ne i32 %iv, 0
 513   %fake_1 = call i1 @cond()
 514   %and_1 = and i1 %zero_check, %fake_1
 515   %iv.minus.1 = add i32 %iv, -1
 516   %range_check_failed = icmp uge i32 %iv.minus.1, %len
 517   %fake_2 = call i1 @cond()
 518   %or_2 = or i1 %range_check_failed, %fake_2
 519   br i1 %and_1, label %range_check_block, label %failed_1
 520
 521 range_check_block:
 522   br i1 %or_2, label %failed_2, label %backedge
 523
 524 backedge:
 525   %iv.next = add i32 %iv, -1
 526   %loop_cond = call i1 @cond()
 527   br i1 %loop_cond, label %done, label %loop
 528
 529 done:
 530   ret i32 %iv
 531
 532 failed_1:
 533   ret i32 -1
 534
 535 failed_2:
 536   ret i32 -2
 537 }
 538
 539 ; This test is equivalent to @test_simple_case, with only difference
 540 ; that both checks are merged together into one 'and' check. This
 541 ; should not prevent turning the range check into invariant.
 542 ; https://alive2.llvm.org/ce/z/G-2ERB
 543 define i32 @test_and_conditions(i32 %start, i32 %len) {
 544 ; CHECK-LABEL: @test_and_conditions(
 545 ; CHECK-NEXT:  entry:
 546 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 547 ; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 548 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 549 ; CHECK:       loop:
 550 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 551 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 552 ; CHECK-NEXT:    [[BOTH_CHECKS:%.*]] = and i1 [[ZERO_CHECK]], [[RANGE_CHECK_FIRST_ITER]]
 553 ; CHECK-NEXT:    br i1 [[BOTH_CHECKS]], label [[BACKEDGE]], label [[FAILED:%.*]]
 554 ; CHECK:       backedge:
 555 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 556 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 557 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 558 ; CHECK:       done:
 559 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 560 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
 561 ; CHECK:       failed:
 562 ; CHECK-NEXT:    ret i32 -3
 563 ;
 564 entry:
 565   br label %loop
 566
 567 loop:
 568   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 569   %zero_check = icmp ne i32 %iv, 0
 570   %iv.minus.1 = add i32 %iv, -1
 571   %range_check = icmp ult i32 %iv.minus.1, %len
 572   %both_checks = and i1 %zero_check, %range_check
 573   br i1 %both_checks, label %backedge, label %failed
 574
 575 backedge:
 576   %iv.next = add i32 %iv, -1
 577   %loop_cond = call i1 @cond()
 578   br i1 %loop_cond, label %done, label %loop
 579
 580 done:
 581   ret i32 %iv
 582
 583 failed:
 584   ret i32 -3
 585 }
 586
 587 ; Same as test_and_conditions, but swapped exit block branches,
 588 ; and condition is expressed as OR. Still optimizable.
 589 define i32 @test_and_conditions_inverse(i32 %start, i32 %len) {
 590 ; CHECK-LABEL: @test_and_conditions_inverse(
 591 ; CHECK-NEXT:  entry:
 592 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 593 ; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 594 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 595 ; CHECK:       loop:
 596 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 597 ; CHECK-NEXT:    [[ZERO_CHECK_FAILED:%.*]] = icmp eq i32 [[IV]], 0
 598 ; CHECK-NEXT:    [[EITHER_CHECK:%.*]] = or i1 [[ZERO_CHECK_FAILED]], [[RANGE_CHECK_FAILED_FIRST_ITER]]
 599 ; CHECK-NEXT:    br i1 [[EITHER_CHECK]], label [[FAILED:%.*]], label [[BACKEDGE]]
 600 ; CHECK:       backedge:
 601 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 602 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 603 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 604 ; CHECK:       done:
 605 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 606 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
 607 ; CHECK:       failed:
 608 ; CHECK-NEXT:    ret i32 -3
 609 ;
 610 entry:
 611   br label %loop
 612
 613 loop:
 614   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 615   %zero_check_failed = icmp eq i32 %iv, 0
 616   %iv.minus.1 = add i32 %iv, -1
 617   %range_check_failed = icmp uge i32 %iv.minus.1, %len
 618   %either_check = or i1 %zero_check_failed, %range_check_failed
 619   br i1 %either_check, label %failed, label %backedge
 620
 621 backedge:
 622   %iv.next = add i32 %iv, -1
 623   %loop_cond = call i1 @cond()
 624   br i1 %loop_cond, label %done, label %loop
 625
 626 done:
 627   ret i32 %iv
 628
 629 failed:
 630   ret i32 -3
 631 }
 632
 633 ; Same as test_litter_conditions, but with logical AND.
 634 define i32 @test_litter_conditions_logical_and(i32 %start, i32 %len) {
 635 ; CHECK-LABEL: @test_litter_conditions_logical_and(
 636 ; CHECK-NEXT:  entry:
 637 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 638 ; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 639 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 640 ; CHECK:       loop:
 641 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 642 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 643 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 644 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 645 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 646 ; CHECK:       range_check_block:
 647 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
 648 ; CHECK-NEXT:    [[AND_2:%.*]] = select i1 [[RANGE_CHECK_FIRST_ITER]], i1 [[FAKE_2]], i1 false
 649 ; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 650 ; CHECK:       backedge:
 651 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 652 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 653 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 654 ; CHECK:       done:
 655 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 656 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 657 ; CHECK:       failed_1:
 658 ; CHECK-NEXT:    ret i32 -1
 659 ; CHECK:       failed_2:
 660 ; CHECK-NEXT:    ret i32 -2
 661 ;
 662 entry:
 663   br label %loop
 664
 665 loop:
 666   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 667   %zero_check = icmp ne i32 %iv, 0
 668   %fake_1 = call i1 @cond()
 669   %and_1 = and i1 %zero_check, %fake_1
 670   br i1 %and_1, label %range_check_block, label %failed_1
 671
 672 range_check_block:
 673   %iv.minus.1 = add i32 %iv, -1
 674   %range_check = icmp ult i32 %iv.minus.1, %len
 675   %fake_2 = call i1 @cond()
 676   %and_2 = select i1 %range_check, i1 %fake_2, i1 false
 677   br i1 %and_2, label %backedge, label %failed_2
 678
 679 backedge:
 680   %iv.next = add i32 %iv, -1
 681   %loop_cond = call i1 @cond()
 682   br i1 %loop_cond, label %done, label %loop
 683
 684 done:
 685   ret i32 %iv
 686
 687 failed_1:
 688   ret i32 -1
 689
 690 failed_2:
 691   ret i32 -2
 692 }
 693
 694 ; Same as test_litter_conditions_inverse, but with logical OR.
 695 define i32 @test_litter_conditions_inverse_logical_or(i32 %start, i32 %len) {
 696 ; CHECK-LABEL: @test_litter_conditions_inverse_logical_or(
 697 ; CHECK-NEXT:  entry:
 698 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 699 ; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 700 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 701 ; CHECK:       loop:
 702 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 703 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 704 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 705 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 706 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 707 ; CHECK:       range_check_block:
 708 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
 709 ; CHECK-NEXT:    [[OR_2:%.*]] = select i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], i1 true, i1 [[FAKE_2]]
 710 ; CHECK-NEXT:    br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]]
 711 ; CHECK:       backedge:
 712 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 713 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 714 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 715 ; CHECK:       done:
 716 ; CHECK-NEXT:    [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 717 ; CHECK-NEXT:    ret i32 [[IV_LCSSA2]]
 718 ; CHECK:       failed_1:
 719 ; CHECK-NEXT:    ret i32 -1
 720 ; CHECK:       failed_2:
 721 ; CHECK-NEXT:    ret i32 -2
 722 ;
 723 entry:
 724   br label %loop
 725
 726 loop:
 727   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 728   %zero_check = icmp ne i32 %iv, 0
 729   %fake_1 = call i1 @cond()
 730   %and_1 = and i1 %zero_check, %fake_1
 731   br i1 %and_1, label %range_check_block, label %failed_1
 732
 733 range_check_block:
 734   %iv.minus.1 = add i32 %iv, -1
 735   %range_check_failed = icmp uge i32 %iv.minus.1, %len
 736   %fake_2 = call i1 @cond()
 737   %or_2 = select i1 %range_check_failed, i1 true, i1 %fake_2
 738   br i1 %or_2, label %failed_2, label %backedge
 739
 740 backedge:
 741   %iv.next = add i32 %iv, -1
 742   %loop_cond = call i1 @cond()
 743   br i1 %loop_cond, label %done, label %loop
 744
 745 done:
 746   ret i32 %iv
 747
 748 failed_1:
 749   ret i32 -1
 750
 751 failed_2:
 752   ret i32 -2
 753 }
 754
 755 ; Same as test_and_conditions, but with logical AND.
 756 define i32 @test_and_conditions_logical_and(i32 %start, i32 %len) {
 757 ; CHECK-LABEL: @test_and_conditions_logical_and(
 758 ; CHECK-NEXT:  entry:
 759 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 760 ; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 761 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 762 ; CHECK:       loop:
 763 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 764 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 765 ; CHECK-NEXT:    [[BOTH_CHECKS:%.*]] = select i1 [[ZERO_CHECK]], i1 [[RANGE_CHECK_FIRST_ITER]], i1 false
 766 ; CHECK-NEXT:    br i1 [[BOTH_CHECKS]], label [[BACKEDGE]], label [[FAILED:%.*]]
 767 ; CHECK:       backedge:
 768 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 769 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 770 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 771 ; CHECK:       done:
 772 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 773 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
 774 ; CHECK:       failed:
 775 ; CHECK-NEXT:    ret i32 -3
 776 ;
 777 entry:
 778   br label %loop
 779
 780 loop:
 781   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 782   %zero_check = icmp ne i32 %iv, 0
 783   %iv.minus.1 = add i32 %iv, -1
 784   %range_check = icmp ult i32 %iv.minus.1, %len
 785   %both_checks = select i1 %zero_check, i1 %range_check, i1 false
 786   br i1 %both_checks, label %backedge, label %failed
 787
 788 backedge:
 789   %iv.next = add i32 %iv, -1
 790   %loop_cond = call i1 @cond()
 791   br i1 %loop_cond, label %done, label %loop
 792
 793 done:
 794   ret i32 %iv
 795
 796 failed:
 797   ret i32 -3
 798 }
 799
 800 ; Same as test_and_conditions_inverse, but with logical OR.
 801 define i32 @test_and_conditions_inverse_logical_or(i32 %start, i32 %len) {
 802 ; CHECK-LABEL: @test_and_conditions_inverse_logical_or(
 803 ; CHECK-NEXT:  entry:
 804 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 805 ; CHECK-NEXT:    [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]]
 806 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 807 ; CHECK:       loop:
 808 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 809 ; CHECK-NEXT:    [[ZERO_CHECK_FAILED:%.*]] = icmp eq i32 [[IV]], 0
 810 ; CHECK-NEXT:    [[EITHER_CHECK:%.*]] = select i1 [[ZERO_CHECK_FAILED]], i1 true, i1 [[RANGE_CHECK_FAILED_FIRST_ITER]]
 811 ; CHECK-NEXT:    br i1 [[EITHER_CHECK]], label [[FAILED:%.*]], label [[BACKEDGE]]
 812 ; CHECK:       backedge:
 813 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 814 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 815 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 816 ; CHECK:       done:
 817 ; CHECK-NEXT:    [[IV_LCSSA1:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 818 ; CHECK-NEXT:    ret i32 [[IV_LCSSA1]]
 819 ; CHECK:       failed:
 820 ; CHECK-NEXT:    ret i32 -3
 821 ;
 822 entry:
 823   br label %loop
 824
 825 loop:
 826   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 827   %zero_check_failed = icmp eq i32 %iv, 0
 828   %iv.minus.1 = add i32 %iv, -1
 829   %range_check_failed = icmp uge i32 %iv.minus.1, %len
 830   %either_check = select i1 %zero_check_failed, i1 true, i1 %range_check_failed
 831   br i1 %either_check, label %failed, label %backedge
 832
 833 backedge:
 834   %iv.next = add i32 %iv, -1
 835   %loop_cond = call i1 @cond()
 836   br i1 %loop_cond, label %done, label %loop
 837
 838 done:
 839   ret i32 %iv
 840
 841 failed:
 842   ret i32 -3
 843 }
 844
 845 ; Same as test_litter_conditions, but an extra check with known exact exit count is preventing the opt.
 846 define i32 @test_litter_conditions_constant(i32 %start, i32 %len) {
 847 ; CHECK-LABEL: @test_litter_conditions_constant(
 848 ; CHECK-NEXT:  entry:
 849 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], -1
 850 ; CHECK-NEXT:    [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]]
 851 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 852 ; CHECK:       loop:
 853 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 854 ; CHECK-NEXT:    [[CANONICAL_IV:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[CANONICAL_IV_NEXT:%.*]], [[BACKEDGE]] ]
 855 ; CHECK-NEXT:    [[CONSTANT_CHECK:%.*]] = icmp ult i32 [[CANONICAL_IV]], 65635
 856 ; CHECK-NEXT:    br i1 [[CONSTANT_CHECK]], label [[CONSTANT_CHECK_PASSED:%.*]], label [[CONSTANT_CHECK_FAILED:%.*]]
 857 ; CHECK:       constant_check_passed:
 858 ; CHECK-NEXT:    [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0
 859 ; CHECK-NEXT:    [[FAKE_1:%.*]] = call i1 @cond()
 860 ; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]]
 861 ; CHECK-NEXT:    br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]]
 862 ; CHECK:       range_check_block:
 863 ; CHECK-NEXT:    [[FAKE_2:%.*]] = call i1 @cond()
 864 ; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]]
 865 ; CHECK-NEXT:    br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]]
 866 ; CHECK:       backedge:
 867 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 868 ; CHECK-NEXT:    [[CANONICAL_IV_NEXT]] = add nuw nsw i32 [[CANONICAL_IV]], 1
 869 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = call i1 @cond()
 870 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[DONE:%.*]], label [[LOOP]]
 871 ; CHECK:       done:
 872 ; CHECK-NEXT:    [[IV_LCSSA3:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ]
 873 ; CHECK-NEXT:    ret i32 [[IV_LCSSA3]]
 874 ; CHECK:       failed_1:
 875 ; CHECK-NEXT:    ret i32 -1
 876 ; CHECK:       failed_2:
 877 ; CHECK-NEXT:    ret i32 -2
 878 ; CHECK:       constant_check_failed:
 879 ; CHECK-NEXT:    ret i32 -3
 880 ;
 881 entry:
 882   br label %loop
 883
 884 loop:
 885   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
 886   %canonical_iv = phi i32 [0, %entry], [%canonical_iv.next, %backedge]
 887   %constant_check = icmp ult i32 %canonical_iv, 65635
 888   br i1 %constant_check, label %constant_check_passed, label %constant_check_failed
 889
 890 constant_check_passed:
 891   %zero_check = icmp ne i32 %iv, 0
 892   %fake_1 = call i1 @cond()
 893   %and_1 = and i1 %zero_check, %fake_1
 894   br i1 %and_1, label %range_check_block, label %failed_1
 895
 896 range_check_block:
 897   %iv.minus.1 = add i32 %iv, -1
 898   %range_check = icmp ult i32 %iv.minus.1, %len
 899   %fake_2 = call i1 @cond()
 900   %and_2 = and i1 %range_check, %fake_2
 901   br i1 %and_2, label %backedge, label %failed_2
 902
 903 backedge:
 904   %iv.next = add i32 %iv, -1
 905   %canonical_iv.next = add i32 %canonical_iv, 1
 906   %loop_cond = call i1 @cond()
 907   br i1 %loop_cond, label %done, label %loop
 908
 909 done:
 910   ret i32 %iv
 911
 912 failed_1:
 913   ret i32 -1
 914
 915 failed_2:
 916   ret i32 -2
 917
 918 constant_check_failed:
 919   ret i32 -3
 920 }
 921
 922 ; TODO: the backedge is predicated by iv.next <u len. It means that starting the
 923 ; 2nd iteration, iv <u len is a known fact. We can replace %check with
 924 ; %check.first.iter = icmp ult i32 0, %len.
 925 define i32 @test_predicated_backedge_no_side_exit(i32 %len) {
 926 ; CHECK-LABEL: @test_predicated_backedge_no_side_exit(
 927 ; CHECK-NEXT:  entry:
 928 ; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[LEN:%.*]], i32 1)
 929 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[UMAX]], -1
 930 ; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[LEN]], i32 [[TMP0]])
 931 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i32 [[LEN]], [[UMIN]]
 932 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 933 ; CHECK:       loop:
 934 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 935 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
 936 ; CHECK-NEXT:    br i1 [[TMP1]], label [[BACKEDGE]], label [[FAILED:%.*]]
 937 ; CHECK:       backedge:
 938 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LEN]]
 939 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 940 ; CHECK:       exit:
 941 ; CHECK-NEXT:    [[IV_NEXT_LCSSA1:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
 942 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA1]]
 943 ; CHECK:       failed:
 944 ; CHECK-NEXT:    ret i32 -1
 945 ;
 946 entry:
 947   br label %loop
 948
 949 loop:
 950   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
 951   %iv.next = add i32 %iv, 1
 952   %check = icmp ult i32 %iv, %len
 953   br i1 %check, label %backedge, label %failed
 954
 955 backedge:
 956   %loop.cond = icmp ult i32 %iv.next, %len
 957   br i1 %loop.cond, label %loop, label %exit
 958
 959 exit:
 960   ret i32 %iv.next
 961
 962 failed:
 963   ret i32 -1
 964 }
 965
 966 ; TODO: the backedge is predicated by iv.next <u len. It means that starting the
 967 ; 2nd iteration, iv <u len is a known fact. We can replace %check with
 968 ; %check.first.iter = icmp ult i32 0, %len.
 969 define i32 @test_predicated_backedge_with_side_exit(i32 %len) {
 970 ; CHECK-LABEL: @test_predicated_backedge_with_side_exit(
 971 ; CHECK-NEXT:  entry:
 972 ; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[LEN:%.*]], i32 1)
 973 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 974 ; CHECK:       loop:
 975 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 976 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
 977 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp ult i32 [[IV]], [[LEN]]
 978 ; CHECK-NEXT:    br i1 [[CHECK]], label [[INNER_BLOCK:%.*]], label [[FAILED:%.*]]
 979 ; CHECK:       inner_block:
 980 ; CHECK-NEXT:    [[COND_1:%.*]] = call i1 @cond()
 981 ; CHECK-NEXT:    br i1 [[COND_1]], label [[BACKEDGE]], label [[FAILED]]
 982 ; CHECK:       backedge:
 983 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LEN]]
 984 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 985 ; CHECK:       exit:
 986 ; CHECK-NEXT:    ret i32 [[UMAX]]
 987 ; CHECK:       failed:
 988 ; CHECK-NEXT:    ret i32 -1
 989 ;
 990 entry:
 991   br label %loop
 992
 993 loop:
 994   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
 995   %iv.next = add i32 %iv, 1
 996   %check = icmp ult i32 %iv, %len
 997   br i1 %check, label %inner_block, label %failed
 998
 999 inner_block:
1000   %cond_1 = call i1 @cond()
1001   br i1 %cond_1, label %backedge, label %failed
1002
1003 backedge:
1004   %loop.cond = icmp ult i32 %iv.next, %len
1005   br i1 %loop.cond, label %loop, label %exit
1006
1007 exit:
1008   ret i32 %iv.next
1009
1010 failed:
1011   ret i32 -1
1012 }
1013
1014 ; TODO: the backedge is predicated by iv.next <u len. It means that starting the
1015 ; 2nd iteration, iv <u len is a known fact. We can replace %check with
1016 ; %check.first.iter = icmp ult i32 %start, %len.
1017 define i32 @test_predicated_backedge_with_side_exit_unknown_start(i32 %start, i32 %len) {
1018 ; CHECK-LABEL: @test_predicated_backedge_with_side_exit_unknown_start(
1019 ; CHECK-NEXT:  entry:
1020 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[START:%.*]], 1
1021 ; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[LEN:%.*]], i32 [[TMP0]])
1022 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1023 ; CHECK:       loop:
1024 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
1025 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
1026 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp ult i32 [[IV]], [[LEN]]
1027 ; CHECK-NEXT:    br i1 [[CHECK]], label [[INNER_BLOCK:%.*]], label [[FAILED:%.*]]
1028 ; CHECK:       inner_block:
1029 ; CHECK-NEXT:    [[COND_1:%.*]] = call i1 @cond()
1030 ; CHECK-NEXT:    br i1 [[COND_1]], label [[BACKEDGE]], label [[FAILED]]
1031 ; CHECK:       backedge:
1032 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ult i32 [[IV_NEXT]], [[LEN]]
1033 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
1034 ; CHECK:       exit:
1035 ; CHECK-NEXT:    ret i32 [[UMAX]]
1036 ; CHECK:       failed:
1037 ; CHECK-NEXT:    ret i32 -1
1038 ;
1039 entry:
1040   br label %loop
1041
1042 loop:
1043   %iv = phi i32 [%start, %entry], [%iv.next, %backedge]
1044   %iv.next = add i32 %iv, 1
1045   %check = icmp ult i32 %iv, %len
1046   br i1 %check, label %inner_block, label %failed
1047
1048 inner_block:
1049   %cond_1 = call i1 @cond()
1050   br i1 %cond_1, label %backedge, label %failed
1051
1052 backedge:
1053   %loop.cond = icmp ult i32 %iv.next, %len
1054   br i1 %loop.cond, label %loop, label %exit
1055
1056 exit:
1057   ret i32 %iv.next
1058
1059 failed:
1060   ret i32 -1
1061 }