1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -indvars -S | FileCheck %s 3; RUN: opt < %s -passes=indvars -S | FileCheck %s 4 5declare i1 @cond() 6declare i32 @llvm.smax.i32(i32, i32) 7 8; FIXME: In all tests in this file, signed_cond is equivalent to unsigned_cond, and therefore 9; one of the checks in the inner loop can be removed. The key to proving it is to prove that 10; %iv starts from something that is non-negative and only goes up. The positivity of its start 11; follows from the fact that %outer.iv also starts from somethign non-negative and only goes 12; up or remains same between iterations. 13define i32 @test_01(i32 %a, i32 %b) { 14; CHECK-LABEL: @test_01( 15; CHECK-NEXT: entry: 16; CHECK-NEXT: [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0 17; CHECK-NEXT: br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]] 18; CHECK: outer.preheader: 19; CHECK-NEXT: br label [[OUTER:%.*]] 20; CHECK: outer: 21; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ] 22; CHECK-NEXT: br label [[INNER:%.*]] 23; CHECK: inner: 24; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 25; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 26; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 27; CHECK: inner.1: 28; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 29; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 30; CHECK: inner.backedge: 31; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 32; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 33; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 34; CHECK: outer.backedge: 35; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 36; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 37; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 38; CHECK: failure: 39; CHECK-NEXT: unreachable 40; CHECK: side.exit: 41; CHECK-NEXT: ret i32 0 42; CHECK: exit: 43; CHECK-NEXT: ret i32 1 44; 45entry: 46 %b_is_non_negative = icmp sge i32 %b, 0 47 br i1 %b_is_non_negative, label %outer, label %failure 48 49outer: 50 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 51 br label %inner 52 53 54inner: 55 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 56 %signed_cond = icmp slt i32 %iv, %b 57 br i1 %signed_cond, label %inner.1, label %side.exit 58 59inner.1: 60 %unsigned_cond = icmp ult i32 %iv, %b 61 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 62 63inner.backedge: 64 %iv.next = add nuw nsw i32 %iv, 1 65 %inner.loop.cond = call i1 @cond() 66 br i1 %inner.loop.cond, label %inner, label %outer.backedge 67 68outer.backedge: 69 %outer.loop.cond = call i1 @cond() 70 br i1 %outer.loop.cond, label %outer, label %exit 71 72failure: 73 unreachable 74 75side.exit: 76 ret i32 0 77 78exit: 79 ret i32 1 80} 81 82; FIXME: iv <u b, b >=s 0 --> iv <s b. We should be able to remove the 2nd check. 83define i32 @test_01a(i32 %a, i32 %b) { 84; CHECK-LABEL: @test_01a( 85; CHECK-NEXT: entry: 86; CHECK-NEXT: [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0 87; CHECK-NEXT: br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]] 88; CHECK: outer.preheader: 89; CHECK-NEXT: br label [[OUTER:%.*]] 90; CHECK: outer: 91; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ] 92; CHECK-NEXT: br label [[INNER:%.*]] 93; CHECK: inner: 94; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 95; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 96; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 97; CHECK: inner.1: 98; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 99; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 100; CHECK: inner.backedge: 101; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 102; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 103; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 104; CHECK: outer.backedge: 105; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 106; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 107; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 108; CHECK: failure: 109; CHECK-NEXT: unreachable 110; CHECK: side.exit: 111; CHECK-NEXT: ret i32 0 112; CHECK: exit: 113; CHECK-NEXT: ret i32 1 114; 115entry: 116 %b_is_non_negative = icmp sge i32 %b, 0 117 br i1 %b_is_non_negative, label %outer, label %failure 118 119outer: 120 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 121 br label %inner 122 123 124inner: 125 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 126 %signed_cond = icmp ult i32 %iv, %b 127 br i1 %signed_cond, label %inner.1, label %side.exit 128 129inner.1: 130 %unsigned_cond = icmp slt i32 %iv, %b 131 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 132 133inner.backedge: 134 %iv.next = add nuw nsw i32 %iv, 1 135 %inner.loop.cond = call i1 @cond() 136 br i1 %inner.loop.cond, label %inner, label %outer.backedge 137 138outer.backedge: 139 %outer.loop.cond = call i1 @cond() 140 br i1 %outer.loop.cond, label %outer, label %exit 141 142failure: 143 unreachable 144 145side.exit: 146 ret i32 0 147 148exit: 149 ret i32 1 150} 151 152define i32 @test_02(i32 %a, i32 %b) { 153; CHECK-LABEL: @test_02( 154; CHECK-NEXT: entry: 155; CHECK-NEXT: [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0 156; CHECK-NEXT: br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]] 157; CHECK: outer.preheader: 158; CHECK-NEXT: br label [[OUTER:%.*]] 159; CHECK: outer: 160; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ] 161; CHECK-NEXT: br label [[INNER:%.*]] 162; CHECK: inner: 163; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 164; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 165; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 166; CHECK: inner.1: 167; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 168; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 169; CHECK: inner.backedge: 170; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 171; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 172; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 173; CHECK: outer.backedge: 174; CHECK-NEXT: [[OUTER_MERGE]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 175; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 176; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 177; CHECK: failure: 178; CHECK-NEXT: unreachable 179; CHECK: side.exit: 180; CHECK-NEXT: ret i32 0 181; CHECK: exit: 182; CHECK-NEXT: ret i32 1 183; 184entry: 185 %b_is_non_negative = icmp sge i32 %b, 0 186 br i1 %b_is_non_negative, label %outer, label %failure 187 188outer: 189 %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge] 190 br label %inner 191 192 193inner: 194 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 195 %signed_cond = icmp slt i32 %iv, %b 196 br i1 %signed_cond, label %inner.1, label %side.exit 197 198inner.1: 199 %unsigned_cond = icmp ult i32 %iv, %b 200 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 201 202inner.backedge: 203 %iv.next = add nuw nsw i32 %iv, 1 204 %inner.loop.cond = call i1 @cond() 205 br i1 %inner.loop.cond, label %inner, label %outer.backedge 206 207outer.backedge: 208 %outer.merge = phi i32 [%iv.next, %inner.backedge] 209 %outer.loop.cond = call i1 @cond() 210 br i1 %outer.loop.cond, label %outer, label %exit 211 212failure: 213 unreachable 214 215side.exit: 216 ret i32 0 217 218exit: 219 ret i32 1 220} 221 222define i32 @test_03(i32 %a, i32 %b) { 223; CHECK-LABEL: @test_03( 224; CHECK-NEXT: entry: 225; CHECK-NEXT: [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0 226; CHECK-NEXT: br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]] 227; CHECK: outer.preheader: 228; CHECK-NEXT: br label [[OUTER:%.*]] 229; CHECK: outer: 230; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ] 231; CHECK-NEXT: [[OUTER_COND_1:%.*]] = call i1 @cond() 232; CHECK-NEXT: br i1 [[OUTER_COND_1]], label [[INNER_PREHEADER:%.*]], label [[NO_INNER:%.*]] 233; CHECK: inner.preheader: 234; CHECK-NEXT: br label [[INNER:%.*]] 235; CHECK: no_inner: 236; CHECK-NEXT: [[OUTER_COND_2:%.*]] = call i1 @cond() 237; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 238; CHECK: inner: 239; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ], [ [[OUTER_IV]], [[INNER_PREHEADER]] ] 240; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 241; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 242; CHECK: inner.1: 243; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 244; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 245; CHECK: inner.backedge: 246; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 247; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 248; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]] 249; CHECK: outer.backedge.loopexit: 250; CHECK-NEXT: [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 251; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 252; CHECK: outer.backedge: 253; CHECK-NEXT: [[OUTER_MERGE]] = phi i32 [ [[OUTER_IV]], [[NO_INNER]] ], [ [[IV_NEXT_LCSSA]], [[OUTER_BACKEDGE_LOOPEXIT]] ] 254; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 255; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 256; CHECK: failure: 257; CHECK-NEXT: unreachable 258; CHECK: side.exit: 259; CHECK-NEXT: ret i32 0 260; CHECK: exit: 261; CHECK-NEXT: ret i32 1 262; 263entry: 264 %b_is_non_negative = icmp sge i32 %b, 0 265 br i1 %b_is_non_negative, label %outer, label %failure 266 267outer: 268 %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge] 269 %outer_cond_1 = call i1 @cond() 270 br i1 %outer_cond_1, label %inner, label %no_inner 271 272no_inner: 273 %outer_cond_2 = call i1 @cond() 274 br label %outer.backedge 275 276inner: 277 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 278 %signed_cond = icmp slt i32 %iv, %b 279 br i1 %signed_cond, label %inner.1, label %side.exit 280 281inner.1: 282 %unsigned_cond = icmp ult i32 %iv, %b 283 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 284 285inner.backedge: 286 %iv.next = add nuw nsw i32 %iv, 1 287 %inner.loop.cond = call i1 @cond() 288 br i1 %inner.loop.cond, label %inner, label %outer.backedge 289 290outer.backedge: 291 %outer.merge = phi i32 [%outer.iv, %no_inner], [%iv.next, %inner.backedge] 292 %outer.loop.cond = call i1 @cond() 293 br i1 %outer.loop.cond, label %outer, label %exit 294 295failure: 296 unreachable 297 298side.exit: 299 ret i32 0 300 301exit: 302 ret i32 1 303} 304 305define i32 @test_04(i32 %a, i32 %b) { 306; CHECK-LABEL: @test_04( 307; CHECK-NEXT: entry: 308; CHECK-NEXT: [[B_IS_NON_NEGATIVE:%.*]] = icmp sge i32 [[B:%.*]], 0 309; CHECK-NEXT: br i1 [[B_IS_NON_NEGATIVE]], label [[OUTER_PREHEADER:%.*]], label [[FAILURE:%.*]] 310; CHECK: outer.preheader: 311; CHECK-NEXT: br label [[OUTER:%.*]] 312; CHECK: outer: 313; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ], [ 0, [[OUTER_PREHEADER]] ] 314; CHECK-NEXT: [[OUTER_COND_1:%.*]] = call i1 @cond() 315; CHECK-NEXT: br i1 [[OUTER_COND_1]], label [[INNER_PREHEADER:%.*]], label [[NO_INNER:%.*]] 316; CHECK: inner.preheader: 317; CHECK-NEXT: br label [[INNER:%.*]] 318; CHECK: no_inner: 319; CHECK-NEXT: [[OUTER_COND_2:%.*]] = call i1 @cond() 320; CHECK-NEXT: br i1 [[OUTER_COND_2]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] 321; CHECK: if.true: 322; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[A:%.*]], i32 [[OUTER_IV]]) 323; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 324; CHECK: if.false: 325; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 326; CHECK: inner: 327; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ], [ [[OUTER_IV]], [[INNER_PREHEADER]] ] 328; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 329; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 330; CHECK: inner.1: 331; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 332; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 333; CHECK: inner.backedge: 334; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 335; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 336; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]] 337; CHECK: outer.backedge.loopexit: 338; CHECK-NEXT: [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 339; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 340; CHECK: outer.backedge: 341; CHECK-NEXT: [[OUTER_MERGE]] = phi i32 [ [[SMAX]], [[IF_TRUE]] ], [ [[OUTER_IV]], [[IF_FALSE]] ], [ [[IV_NEXT_LCSSA]], [[OUTER_BACKEDGE_LOOPEXIT]] ] 342; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 343; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 344; CHECK: failure: 345; CHECK-NEXT: unreachable 346; CHECK: side.exit: 347; CHECK-NEXT: ret i32 0 348; CHECK: exit: 349; CHECK-NEXT: ret i32 1 350; 351entry: 352 %b_is_non_negative = icmp sge i32 %b, 0 353 br i1 %b_is_non_negative, label %outer, label %failure 354 355outer: 356 %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge] 357 %outer_cond_1 = call i1 @cond() 358 br i1 %outer_cond_1, label %inner, label %no_inner 359 360no_inner: 361 %outer_cond_2 = call i1 @cond() 362 br i1 %outer_cond_2, label %if.true, label %if.false 363 364if.true: 365 %smax = call i32 @llvm.smax.i32(i32 %a, i32 %outer.iv) 366 br label %outer.backedge 367 368if.false: 369 br label %outer.backedge 370 371inner: 372 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 373 %signed_cond = icmp slt i32 %iv, %b 374 br i1 %signed_cond, label %inner.1, label %side.exit 375 376inner.1: 377 %unsigned_cond = icmp ult i32 %iv, %b 378 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 379 380inner.backedge: 381 %iv.next = add nuw nsw i32 %iv, 1 382 %inner.loop.cond = call i1 @cond() 383 br i1 %inner.loop.cond, label %inner, label %outer.backedge 384 385outer.backedge: 386 %outer.merge = phi i32 [%smax, %if.true], [%outer.iv, %if.false], [%iv.next, %inner.backedge] 387 %outer.loop.cond = call i1 @cond() 388 br i1 %outer.loop.cond, label %outer, label %exit 389 390failure: 391 unreachable 392 393side.exit: 394 ret i32 0 395 396exit: 397 ret i32 1 398} 399 400; Same as test_01, but non-negativity of %b is known without context. 401; FIXME: We can remove 2nd check in loop. 402define i32 @test_05(i32 %a, i32* %bp) { 403; CHECK-LABEL: @test_05( 404; CHECK-NEXT: entry: 405; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0:![0-9]+]] 406; CHECK-NEXT: br label [[OUTER:%.*]] 407; CHECK: outer: 408; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 409; CHECK-NEXT: br label [[INNER:%.*]] 410; CHECK: inner: 411; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 412; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 413; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 414; CHECK: inner.1: 415; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 416; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 417; CHECK: inner.backedge: 418; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 419; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 420; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 421; CHECK: outer.backedge: 422; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 423; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 424; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 425; CHECK: side.exit: 426; CHECK-NEXT: ret i32 0 427; CHECK: exit: 428; CHECK-NEXT: ret i32 1 429; 430entry: 431 %b = load i32, i32* %bp, !range !0 432 br label %outer 433 434outer: 435 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 436 br label %inner 437 438 439inner: 440 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 441 %signed_cond = icmp slt i32 %iv, %b 442 br i1 %signed_cond, label %inner.1, label %side.exit 443 444inner.1: 445 %unsigned_cond = icmp ult i32 %iv, %b 446 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 447 448inner.backedge: 449 %iv.next = add nuw nsw i32 %iv, 1 450 %inner.loop.cond = call i1 @cond() 451 br i1 %inner.loop.cond, label %inner, label %outer.backedge 452 453outer.backedge: 454 %outer.loop.cond = call i1 @cond() 455 br i1 %outer.loop.cond, label %outer, label %exit 456 457side.exit: 458 ret i32 0 459 460exit: 461 ret i32 1 462} 463 464 465; Same as test_01a, but non-negativity of %b is known without context. 466; FIXME: We can remove 2nd check in loop. 467define i32 @test_05a(i32 %a, i32* %bp) { 468; CHECK-LABEL: @test_05a( 469; CHECK-NEXT: entry: 470; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 471; CHECK-NEXT: br label [[OUTER:%.*]] 472; CHECK: outer: 473; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 474; CHECK-NEXT: br label [[INNER:%.*]] 475; CHECK: inner: 476; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 477; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 478; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 479; CHECK: inner.1: 480; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 481; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 482; CHECK: inner.backedge: 483; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 484; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 485; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 486; CHECK: outer.backedge: 487; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 488; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 489; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 490; CHECK: side.exit: 491; CHECK-NEXT: ret i32 0 492; CHECK: exit: 493; CHECK-NEXT: ret i32 1 494; 495entry: 496 %b = load i32, i32* %bp, !range !0 497 br label %outer 498 499outer: 500 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 501 br label %inner 502 503 504inner: 505 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 506 %signed_cond = icmp ult i32 %iv, %b 507 br i1 %signed_cond, label %inner.1, label %side.exit 508 509inner.1: 510 %unsigned_cond = icmp slt i32 %iv, %b 511 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 512 513inner.backedge: 514 %iv.next = add nuw nsw i32 %iv, 1 515 %inner.loop.cond = call i1 @cond() 516 br i1 %inner.loop.cond, label %inner, label %outer.backedge 517 518outer.backedge: 519 %outer.loop.cond = call i1 @cond() 520 br i1 %outer.loop.cond, label %outer, label %exit 521 522side.exit: 523 ret i32 0 524 525exit: 526 ret i32 1 527} 528 529; Same as test_02, but non-negativity of %b is known without context. 530; FIXME: We can remove 2nd check in loop. 531define i32 @test_06(i32 %a, i32* %bp) { 532; CHECK-LABEL: @test_06( 533; CHECK-NEXT: entry: 534; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 535; CHECK-NEXT: br label [[OUTER:%.*]] 536; CHECK: outer: 537; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ] 538; CHECK-NEXT: br label [[INNER:%.*]] 539; CHECK: inner: 540; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 541; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 542; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 543; CHECK: inner.1: 544; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 545; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 546; CHECK: inner.backedge: 547; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 548; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 549; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 550; CHECK: outer.backedge: 551; CHECK-NEXT: [[OUTER_MERGE]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 552; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 553; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 554; CHECK: side.exit: 555; CHECK-NEXT: ret i32 0 556; CHECK: exit: 557; CHECK-NEXT: ret i32 1 558; 559entry: 560 %b = load i32, i32* %bp, !range !0 561 br label %outer 562 563outer: 564 %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge] 565 br label %inner 566 567 568inner: 569 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 570 %signed_cond = icmp slt i32 %iv, %b 571 br i1 %signed_cond, label %inner.1, label %side.exit 572 573inner.1: 574 %unsigned_cond = icmp ult i32 %iv, %b 575 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 576 577inner.backedge: 578 %iv.next = add nuw nsw i32 %iv, 1 579 %inner.loop.cond = call i1 @cond() 580 br i1 %inner.loop.cond, label %inner, label %outer.backedge 581 582outer.backedge: 583 %outer.merge = phi i32 [%iv.next, %inner.backedge] 584 %outer.loop.cond = call i1 @cond() 585 br i1 %outer.loop.cond, label %outer, label %exit 586 587side.exit: 588 ret i32 0 589 590exit: 591 ret i32 1 592} 593 594; Same as test_03, but non-negativity of %b is known without context. 595; FIXME: We can remove 2nd check in loop. 596define i32 @test_07(i32 %a, i32* %bp) { 597; CHECK-LABEL: @test_07( 598; CHECK-NEXT: entry: 599; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 600; CHECK-NEXT: br label [[OUTER:%.*]] 601; CHECK: outer: 602; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ] 603; CHECK-NEXT: [[OUTER_COND_1:%.*]] = call i1 @cond() 604; CHECK-NEXT: br i1 [[OUTER_COND_1]], label [[INNER_PREHEADER:%.*]], label [[NO_INNER:%.*]] 605; CHECK: inner.preheader: 606; CHECK-NEXT: br label [[INNER:%.*]] 607; CHECK: no_inner: 608; CHECK-NEXT: [[OUTER_COND_2:%.*]] = call i1 @cond() 609; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 610; CHECK: inner: 611; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ], [ [[OUTER_IV]], [[INNER_PREHEADER]] ] 612; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 613; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 614; CHECK: inner.1: 615; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 616; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 617; CHECK: inner.backedge: 618; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 619; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 620; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]] 621; CHECK: outer.backedge.loopexit: 622; CHECK-NEXT: [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 623; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 624; CHECK: outer.backedge: 625; CHECK-NEXT: [[OUTER_MERGE]] = phi i32 [ [[OUTER_IV]], [[NO_INNER]] ], [ [[IV_NEXT_LCSSA]], [[OUTER_BACKEDGE_LOOPEXIT]] ] 626; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 627; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 628; CHECK: side.exit: 629; CHECK-NEXT: ret i32 0 630; CHECK: exit: 631; CHECK-NEXT: ret i32 1 632; 633entry: 634 %b = load i32, i32* %bp, !range !0 635 br label %outer 636 637outer: 638 %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge] 639 %outer_cond_1 = call i1 @cond() 640 br i1 %outer_cond_1, label %inner, label %no_inner 641 642no_inner: 643 %outer_cond_2 = call i1 @cond() 644 br label %outer.backedge 645 646inner: 647 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 648 %signed_cond = icmp slt i32 %iv, %b 649 br i1 %signed_cond, label %inner.1, label %side.exit 650 651inner.1: 652 %unsigned_cond = icmp ult i32 %iv, %b 653 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 654 655inner.backedge: 656 %iv.next = add nuw nsw i32 %iv, 1 657 %inner.loop.cond = call i1 @cond() 658 br i1 %inner.loop.cond, label %inner, label %outer.backedge 659 660outer.backedge: 661 %outer.merge = phi i32 [%outer.iv, %no_inner], [%iv.next, %inner.backedge] 662 %outer.loop.cond = call i1 @cond() 663 br i1 %outer.loop.cond, label %outer, label %exit 664 665side.exit: 666 ret i32 0 667 668exit: 669 ret i32 1 670} 671 672; Same as test_04, but non-negativity of %b is known without context. 673; FIXME: We can remove 2nd check in loop. 674define i32 @test_08(i32 %a, i32* %bp) { 675; CHECK-LABEL: @test_08( 676; CHECK-NEXT: entry: 677; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 678; CHECK-NEXT: br label [[OUTER:%.*]] 679; CHECK: outer: 680; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ] 681; CHECK-NEXT: [[OUTER_COND_1:%.*]] = call i1 @cond() 682; CHECK-NEXT: br i1 [[OUTER_COND_1]], label [[INNER_PREHEADER:%.*]], label [[NO_INNER:%.*]] 683; CHECK: inner.preheader: 684; CHECK-NEXT: br label [[INNER:%.*]] 685; CHECK: no_inner: 686; CHECK-NEXT: [[OUTER_COND_2:%.*]] = call i1 @cond() 687; CHECK-NEXT: br i1 [[OUTER_COND_2]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] 688; CHECK: if.true: 689; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[A:%.*]], i32 [[OUTER_IV]]) 690; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 691; CHECK: if.false: 692; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 693; CHECK: inner: 694; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ], [ [[OUTER_IV]], [[INNER_PREHEADER]] ] 695; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 696; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 697; CHECK: inner.1: 698; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 699; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 700; CHECK: inner.backedge: 701; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 702; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 703; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]] 704; CHECK: outer.backedge.loopexit: 705; CHECK-NEXT: [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 706; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 707; CHECK: outer.backedge: 708; CHECK-NEXT: [[OUTER_MERGE]] = phi i32 [ [[SMAX]], [[IF_TRUE]] ], [ [[OUTER_IV]], [[IF_FALSE]] ], [ [[IV_NEXT_LCSSA]], [[OUTER_BACKEDGE_LOOPEXIT]] ] 709; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 710; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 711; CHECK: side.exit: 712; CHECK-NEXT: ret i32 0 713; CHECK: exit: 714; CHECK-NEXT: ret i32 1 715; 716entry: 717 %b = load i32, i32* %bp, !range !0 718 br label %outer 719 720outer: 721 %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge] 722 %outer_cond_1 = call i1 @cond() 723 br i1 %outer_cond_1, label %inner, label %no_inner 724 725no_inner: 726 %outer_cond_2 = call i1 @cond() 727 br i1 %outer_cond_2, label %if.true, label %if.false 728 729if.true: 730 %smax = call i32 @llvm.smax.i32(i32 %a, i32 %outer.iv) 731 br label %outer.backedge 732 733if.false: 734 br label %outer.backedge 735 736inner: 737 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 738 %signed_cond = icmp slt i32 %iv, %b 739 br i1 %signed_cond, label %inner.1, label %side.exit 740 741inner.1: 742 %unsigned_cond = icmp ult i32 %iv, %b 743 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 744 745inner.backedge: 746 %iv.next = add nuw nsw i32 %iv, 1 747 %inner.loop.cond = call i1 @cond() 748 br i1 %inner.loop.cond, label %inner, label %outer.backedge 749 750outer.backedge: 751 %outer.merge = phi i32 [%smax, %if.true], [%outer.iv, %if.false], [%iv.next, %inner.backedge] 752 %outer.loop.cond = call i1 @cond() 753 br i1 %outer.loop.cond, label %outer, label %exit 754 755side.exit: 756 ret i32 0 757 758exit: 759 ret i32 1 760} 761 762!0 = !{i32 0, i32 2147483647} 763