1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -passes=indvars -S < %s | FileCheck %s 3 4declare i1 @cond() 5 6; Range check here can be turned into invariant check. 7define 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; 31entry: 32 br label %loop 33 34loop: 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 39range_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 44backedge: 45 %iv.next = add i32 %iv, -1 46 %loop_cond = call i1 @cond() 47 br i1 %loop_cond, label %done, label %loop 48 49done: 50 ret i32 %iv 51 52failed_1: 53 ret i32 -1 54 55failed_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 63define 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; 91entry: 92 br label %loop 93 94loop: 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 101range_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 108backedge: 109 %iv.next = add i32 %iv, -1 110 %loop_cond = call i1 @cond() 111 br i1 %loop_cond, label %done, label %loop 112 113done: 114 ret i32 %iv 115 116failed_1: 117 ret i32 -1 118 119failed_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. 125define 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; 153entry: 154 br label %loop 155 156loop: 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 163range_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 170backedge: 171 %iv.next = add i32 %iv, -1 172 %loop_cond = call i1 @cond() 173 br i1 %loop_cond, label %done, label %loop 174 175done: 176 ret i32 %iv 177 178failed_1: 179 ret i32 -1 180 181failed_2: 182 ret i32 -2 183} 184 185define 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; 211entry: 212 br label %loop 213 214loop: 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 221range_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 226backedge: 227 %iv.next = add i32 %iv, -1 228 %loop_cond = call i1 @cond() 229 br i1 %loop_cond, label %done, label %loop 230 231done: 232 ret i32 %iv 233 234failed_1: 235 ret i32 -1 236 237failed_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. 243define 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; 269entry: 270 br label %loop 271 272loop: 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 279range_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 284backedge: 285 %iv.next = add i32 %iv, -1 286 %loop_cond = call i1 @cond() 287 br i1 %loop_cond, label %done, label %loop 288 289done: 290 ret i32 %iv 291 292failed_1: 293 ret i32 -1 294 295failed_2: 296 ret i32 -2 297} 298 299; TODO: Simplified version 2 of test_litter_conditions. 300define 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; 326entry: 327 br label %loop 328 329loop: 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 334range_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 341backedge: 342 %iv.next = add i32 %iv, -1 343 %loop_cond = call i1 @cond() 344 br i1 %loop_cond, label %done, label %loop 345 346done: 347 ret i32 %iv 348 349failed_1: 350 ret i32 -1 351 352failed_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. 358define 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; 384entry: 385 br label %loop 386 387loop: 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 392range_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 399backedge: 400 %iv.next = add i32 %iv, -1 401 %loop_cond = call i1 @cond() 402 br i1 %loop_cond, label %done, label %loop 403 404done: 405 ret i32 %iv 406 407failed_1: 408 ret i32 -1 409 410failed_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 417define 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; 445entry: 446 br label %loop 447 448loop: 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 459range_check_block: 460 br i1 %and_2, label %backedge, label %failed_2 461 462backedge: 463 %iv.next = add i32 %iv, -1 464 %loop_cond = call i1 @cond() 465 br i1 %loop_cond, label %done, label %loop 466 467done: 468 ret i32 %iv 469 470failed_1: 471 ret i32 -1 472 473failed_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. 479define 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; 507entry: 508 br label %loop 509 510loop: 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 521range_check_block: 522 br i1 %or_2, label %failed_2, label %backedge 523 524backedge: 525 %iv.next = add i32 %iv, -1 526 %loop_cond = call i1 @cond() 527 br i1 %loop_cond, label %done, label %loop 528 529done: 530 ret i32 %iv 531 532failed_1: 533 ret i32 -1 534 535failed_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 543define 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; 564entry: 565 br label %loop 566 567loop: 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 575backedge: 576 %iv.next = add i32 %iv, -1 577 %loop_cond = call i1 @cond() 578 br i1 %loop_cond, label %done, label %loop 579 580done: 581 ret i32 %iv 582 583failed: 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. 589define 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; 610entry: 611 br label %loop 612 613loop: 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 621backedge: 622 %iv.next = add i32 %iv, -1 623 %loop_cond = call i1 @cond() 624 br i1 %loop_cond, label %done, label %loop 625 626done: 627 ret i32 %iv 628 629failed: 630 ret i32 -3 631} 632 633; Same as test_litter_conditions, but with logical AND. 634define 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; 662entry: 663 br label %loop 664 665loop: 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 672range_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 679backedge: 680 %iv.next = add i32 %iv, -1 681 %loop_cond = call i1 @cond() 682 br i1 %loop_cond, label %done, label %loop 683 684done: 685 ret i32 %iv 686 687failed_1: 688 ret i32 -1 689 690failed_2: 691 ret i32 -2 692} 693 694; Same as test_litter_conditions_inverse, but with logical OR. 695define 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; 723entry: 724 br label %loop 725 726loop: 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 733range_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 740backedge: 741 %iv.next = add i32 %iv, -1 742 %loop_cond = call i1 @cond() 743 br i1 %loop_cond, label %done, label %loop 744 745done: 746 ret i32 %iv 747 748failed_1: 749 ret i32 -1 750 751failed_2: 752 ret i32 -2 753} 754 755; Same as test_and_conditions, but with logical AND. 756define 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; 777entry: 778 br label %loop 779 780loop: 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 788backedge: 789 %iv.next = add i32 %iv, -1 790 %loop_cond = call i1 @cond() 791 br i1 %loop_cond, label %done, label %loop 792 793done: 794 ret i32 %iv 795 796failed: 797 ret i32 -3 798} 799 800; Same as test_and_conditions_inverse, but with logical OR. 801define 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; 822entry: 823 br label %loop 824 825loop: 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 833backedge: 834 %iv.next = add i32 %iv, -1 835 %loop_cond = call i1 @cond() 836 br i1 %loop_cond, label %done, label %loop 837 838done: 839 ret i32 %iv 840 841failed: 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. 846define 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; 881entry: 882 br label %loop 883 884loop: 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 890constant_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 896range_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 903backedge: 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 909done: 910 ret i32 %iv 911 912failed_1: 913 ret i32 -1 914 915failed_2: 916 ret i32 -2 917 918constant_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. 925define 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; 946entry: 947 br label %loop 948 949loop: 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 955backedge: 956 %loop.cond = icmp ult i32 %iv.next, %len 957 br i1 %loop.cond, label %loop, label %exit 958 959exit: 960 ret i32 %iv.next 961 962failed: 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. 969define 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; 990entry: 991 br label %loop 992 993loop: 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 999inner_block: 1000 %cond_1 = call i1 @cond() 1001 br i1 %cond_1, label %backedge, label %failed 1002 1003backedge: 1004 %loop.cond = icmp ult i32 %iv.next, %len 1005 br i1 %loop.cond, label %loop, label %exit 1006 1007exit: 1008 ret i32 %iv.next 1009 1010failed: 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. 1017define 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; 1039entry: 1040 br label %loop 1041 1042loop: 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 1048inner_block: 1049 %cond_1 = call i1 @cond() 1050 br i1 %cond_1, label %backedge, label %failed 1051 1052backedge: 1053 %loop.cond = icmp ult i32 %iv.next, %len 1054 br i1 %loop.cond, label %loop, label %exit 1055 1056exit: 1057 ret i32 %iv.next 1058 1059failed: 1060 ret i32 -1 1061} 1062