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. 466define i32 @test_05a(i32 %a, i32* %bp) { 467; CHECK-LABEL: @test_05a( 468; CHECK-NEXT: entry: 469; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 470; CHECK-NEXT: br label [[OUTER:%.*]] 471; CHECK: outer: 472; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 473; CHECK-NEXT: br label [[INNER:%.*]] 474; CHECK: inner: 475; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 476; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 477; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 478; CHECK: inner.1: 479; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 480; CHECK: inner.backedge: 481; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 482; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 483; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 484; CHECK: outer.backedge: 485; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 486; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 487; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 488; CHECK: side.exit: 489; CHECK-NEXT: ret i32 0 490; CHECK: exit: 491; CHECK-NEXT: ret i32 1 492; 493entry: 494 %b = load i32, i32* %bp, !range !0 495 br label %outer 496 497outer: 498 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 499 br label %inner 500 501 502inner: 503 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 504 %unsigned_cond = icmp ult i32 %iv, %b 505 br i1 %unsigned_cond, label %inner.1, label %side.exit 506 507inner.1: 508 %signed_cond = icmp slt i32 %iv, %b 509 br i1 %signed_cond, label %inner.backedge, label %side.exit 510 511inner.backedge: 512 %iv.next = add nuw nsw i32 %iv, 1 513 %inner.loop.cond = call i1 @cond() 514 br i1 %inner.loop.cond, label %inner, label %outer.backedge 515 516outer.backedge: 517 %outer.loop.cond = call i1 @cond() 518 br i1 %outer.loop.cond, label %outer, label %exit 519 520side.exit: 521 ret i32 0 522 523exit: 524 ret i32 1 525} 526 527; Similar to test_05a, but inverted 2nd condition. 528define i32 @test_05b(i32 %a, i32* %bp) { 529; CHECK-LABEL: @test_05b( 530; CHECK-NEXT: entry: 531; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 532; CHECK-NEXT: br label [[OUTER:%.*]] 533; CHECK: outer: 534; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 535; CHECK-NEXT: br label [[INNER:%.*]] 536; CHECK: inner: 537; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 538; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 539; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 540; CHECK: inner.1: 541; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 542; CHECK: inner.backedge: 543; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 544; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 545; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 546; CHECK: outer.backedge: 547; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 548; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 549; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 550; CHECK: side.exit: 551; CHECK-NEXT: ret i32 0 552; CHECK: exit: 553; CHECK-NEXT: ret i32 1 554; 555entry: 556 %b = load i32, i32* %bp, !range !0 557 br label %outer 558 559outer: 560 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 561 br label %inner 562 563 564inner: 565 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 566 %unsigned_cond = icmp ult i32 %iv, %b 567 br i1 %unsigned_cond, label %inner.1, label %side.exit 568 569inner.1: 570 %signed_cond = icmp sgt i32 %b, %iv 571 br i1 %signed_cond, label %inner.backedge, label %side.exit 572 573inner.backedge: 574 %iv.next = add nuw nsw i32 %iv, 1 575 %inner.loop.cond = call i1 @cond() 576 br i1 %inner.loop.cond, label %inner, label %outer.backedge 577 578outer.backedge: 579 %outer.loop.cond = call i1 @cond() 580 br i1 %outer.loop.cond, label %outer, label %exit 581 582side.exit: 583 ret i32 0 584 585exit: 586 ret i32 1 587} 588 589; We should prove implication: iv <s b, b <s 0 => iv <u b. 590define i32 @test_05c(i32 %a, i32* %bp) { 591; CHECK-LABEL: @test_05c( 592; CHECK-NEXT: entry: 593; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1:![0-9]+]] 594; CHECK-NEXT: br label [[OUTER:%.*]] 595; CHECK: outer: 596; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 597; CHECK-NEXT: br label [[INNER:%.*]] 598; CHECK: inner: 599; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 600; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 601; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 602; CHECK: inner.1: 603; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 604; CHECK: inner.backedge: 605; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 606; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 607; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 608; CHECK: outer.backedge: 609; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 610; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 611; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 612; CHECK: side.exit: 613; CHECK-NEXT: ret i32 0 614; CHECK: exit: 615; CHECK-NEXT: ret i32 1 616; 617entry: 618 %b = load i32, i32* %bp, !range !1 619 br label %outer 620 621outer: 622 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 623 br label %inner 624 625 626inner: 627 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 628 %signed_cond = icmp slt i32 %iv, %b 629 br i1 %signed_cond, label %inner.1, label %side.exit 630 631inner.1: 632 %unsigned_cond = icmp ult i32 %iv, %b 633 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 634 635inner.backedge: 636 %iv.next = add nuw nsw i32 %iv, 1 637 %inner.loop.cond = call i1 @cond() 638 br i1 %inner.loop.cond, label %inner, label %outer.backedge 639 640outer.backedge: 641 %outer.loop.cond = call i1 @cond() 642 br i1 %outer.loop.cond, label %outer, label %exit 643 644side.exit: 645 ret i32 0 646 647exit: 648 ret i32 1 649} 650 651; Same as test_05c, but 2nd condition reversed. 652define i32 @test_05d(i32 %a, i32* %bp) { 653; CHECK-LABEL: @test_05d( 654; CHECK-NEXT: entry: 655; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]] 656; CHECK-NEXT: br label [[OUTER:%.*]] 657; CHECK: outer: 658; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 659; CHECK-NEXT: br label [[INNER:%.*]] 660; CHECK: inner: 661; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 662; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 663; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 664; CHECK: inner.1: 665; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 666; CHECK: inner.backedge: 667; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 668; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 669; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 670; CHECK: outer.backedge: 671; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 672; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 673; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 674; CHECK: side.exit: 675; CHECK-NEXT: ret i32 0 676; CHECK: exit: 677; CHECK-NEXT: ret i32 1 678; 679entry: 680 %b = load i32, i32* %bp, !range !1 681 br label %outer 682 683outer: 684 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 685 br label %inner 686 687 688inner: 689 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 690 %signed_cond = icmp slt i32 %iv, %b 691 br i1 %signed_cond, label %inner.1, label %side.exit 692 693inner.1: 694 %unsigned_cond = icmp ugt i32 %b, %iv 695 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 696 697inner.backedge: 698 %iv.next = add nuw nsw i32 %iv, 1 699 %inner.loop.cond = call i1 @cond() 700 br i1 %inner.loop.cond, label %inner, label %outer.backedge 701 702outer.backedge: 703 %outer.loop.cond = call i1 @cond() 704 br i1 %outer.loop.cond, label %outer, label %exit 705 706side.exit: 707 ret i32 0 708 709exit: 710 ret i32 1 711} 712 713 714; Same as test_05a, but 1st condition inverted. 715define i32 @test_05e(i32 %a, i32* %bp) { 716; CHECK-LABEL: @test_05e( 717; CHECK-NEXT: entry: 718; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 719; CHECK-NEXT: br label [[OUTER:%.*]] 720; CHECK: outer: 721; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 722; CHECK-NEXT: br label [[INNER:%.*]] 723; CHECK: inner: 724; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 725; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ugt i32 [[B]], [[IV]] 726; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 727; CHECK: inner.1: 728; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 729; CHECK: inner.backedge: 730; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 731; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 732; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 733; CHECK: outer.backedge: 734; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 735; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 736; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 737; CHECK: side.exit: 738; CHECK-NEXT: ret i32 0 739; CHECK: exit: 740; CHECK-NEXT: ret i32 1 741; 742entry: 743 %b = load i32, i32* %bp, !range !0 744 br label %outer 745 746outer: 747 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 748 br label %inner 749 750 751inner: 752 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 753 %unsigned_cond = icmp ugt i32 %b, %iv 754 br i1 %unsigned_cond, label %inner.1, label %side.exit 755 756inner.1: 757 %signed_cond = icmp slt i32 %iv, %b 758 br i1 %signed_cond, label %inner.backedge, label %side.exit 759 760inner.backedge: 761 %iv.next = add nuw nsw i32 %iv, 1 762 %inner.loop.cond = call i1 @cond() 763 br i1 %inner.loop.cond, label %inner, label %outer.backedge 764 765outer.backedge: 766 %outer.loop.cond = call i1 @cond() 767 br i1 %outer.loop.cond, label %outer, label %exit 768 769side.exit: 770 ret i32 0 771 772exit: 773 ret i32 1 774} 775 776; Same as test_05b, but 1st condition inverted. 777define i32 @test_05f(i32 %a, i32* %bp) { 778; CHECK-LABEL: @test_05f( 779; CHECK-NEXT: entry: 780; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 781; CHECK-NEXT: br label [[OUTER:%.*]] 782; CHECK: outer: 783; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 784; CHECK-NEXT: br label [[INNER:%.*]] 785; CHECK: inner: 786; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 787; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ugt i32 [[B]], [[IV]] 788; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 789; CHECK: inner.1: 790; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 791; CHECK: inner.backedge: 792; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 793; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 794; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 795; CHECK: outer.backedge: 796; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 797; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 798; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 799; CHECK: side.exit: 800; CHECK-NEXT: ret i32 0 801; CHECK: exit: 802; CHECK-NEXT: ret i32 1 803; 804entry: 805 %b = load i32, i32* %bp, !range !0 806 br label %outer 807 808outer: 809 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 810 br label %inner 811 812 813inner: 814 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 815 %unsigned_cond = icmp ugt i32 %b, %iv 816 br i1 %unsigned_cond, label %inner.1, label %side.exit 817 818inner.1: 819 %signed_cond = icmp sgt i32 %b, %iv 820 br i1 %signed_cond, label %inner.backedge, label %side.exit 821 822inner.backedge: 823 %iv.next = add nuw nsw i32 %iv, 1 824 %inner.loop.cond = call i1 @cond() 825 br i1 %inner.loop.cond, label %inner, label %outer.backedge 826 827outer.backedge: 828 %outer.loop.cond = call i1 @cond() 829 br i1 %outer.loop.cond, label %outer, label %exit 830 831side.exit: 832 ret i32 0 833 834exit: 835 ret i32 1 836} 837 838; Same as test_05c, but 1st condition inverted. 839define i32 @test_05g(i32 %a, i32* %bp) { 840; CHECK-LABEL: @test_05g( 841; CHECK-NEXT: entry: 842; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]] 843; CHECK-NEXT: br label [[OUTER:%.*]] 844; CHECK: outer: 845; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 846; CHECK-NEXT: br label [[INNER:%.*]] 847; CHECK: inner: 848; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 849; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]] 850; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 851; CHECK: inner.1: 852; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 853; CHECK: inner.backedge: 854; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 855; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 856; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 857; CHECK: outer.backedge: 858; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 859; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 860; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 861; CHECK: side.exit: 862; CHECK-NEXT: ret i32 0 863; CHECK: exit: 864; CHECK-NEXT: ret i32 1 865; 866entry: 867 %b = load i32, i32* %bp, !range !1 868 br label %outer 869 870outer: 871 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 872 br label %inner 873 874 875inner: 876 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 877 %signed_cond = icmp sgt i32 %b, %iv 878 br i1 %signed_cond, label %inner.1, label %side.exit 879 880inner.1: 881 %unsigned_cond = icmp ult i32 %iv, %b 882 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 883 884inner.backedge: 885 %iv.next = add nuw nsw i32 %iv, 1 886 %inner.loop.cond = call i1 @cond() 887 br i1 %inner.loop.cond, label %inner, label %outer.backedge 888 889outer.backedge: 890 %outer.loop.cond = call i1 @cond() 891 br i1 %outer.loop.cond, label %outer, label %exit 892 893side.exit: 894 ret i32 0 895 896exit: 897 ret i32 1 898} 899 900; Same as test_05d, but 1st condition inverted. 901define i32 @test_05h(i32 %a, i32* %bp) { 902; CHECK-LABEL: @test_05h( 903; CHECK-NEXT: entry: 904; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG1]] 905; CHECK-NEXT: br label [[OUTER:%.*]] 906; CHECK: outer: 907; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_BACKEDGE:%.*]] ] 908; CHECK-NEXT: br label [[INNER:%.*]] 909; CHECK: inner: 910; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 911; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp sgt i32 [[B]], [[IV]] 912; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 913; CHECK: inner.1: 914; CHECK-NEXT: br i1 true, label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 915; CHECK: inner.backedge: 916; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 917; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 918; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 919; CHECK: outer.backedge: 920; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 921; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 922; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 923; CHECK: side.exit: 924; CHECK-NEXT: ret i32 0 925; CHECK: exit: 926; CHECK-NEXT: ret i32 1 927; 928entry: 929 %b = load i32, i32* %bp, !range !1 930 br label %outer 931 932outer: 933 %outer.iv = phi i32 [0, %entry], [%iv.next, %outer.backedge] 934 br label %inner 935 936 937inner: 938 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 939 %signed_cond = icmp sgt i32 %b, %iv 940 br i1 %signed_cond, label %inner.1, label %side.exit 941 942inner.1: 943 %unsigned_cond = icmp ugt i32 %b, %iv 944 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 945 946inner.backedge: 947 %iv.next = add nuw nsw i32 %iv, 1 948 %inner.loop.cond = call i1 @cond() 949 br i1 %inner.loop.cond, label %inner, label %outer.backedge 950 951outer.backedge: 952 %outer.loop.cond = call i1 @cond() 953 br i1 %outer.loop.cond, label %outer, label %exit 954 955side.exit: 956 ret i32 0 957 958exit: 959 ret i32 1 960} 961 962; Same as test_02, but non-negativity of %b is known without context. 963; FIXME: We can remove 2nd check in loop. 964define i32 @test_06(i32 %a, i32* %bp) { 965; CHECK-LABEL: @test_06( 966; CHECK-NEXT: entry: 967; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 968; CHECK-NEXT: br label [[OUTER:%.*]] 969; CHECK: outer: 970; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ] 971; CHECK-NEXT: br label [[INNER:%.*]] 972; CHECK: inner: 973; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[OUTER_IV]], [[OUTER]] ], [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ] 974; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 975; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 976; CHECK: inner.1: 977; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 978; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 979; CHECK: inner.backedge: 980; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 981; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 982; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE]] 983; CHECK: outer.backedge: 984; CHECK-NEXT: [[OUTER_MERGE]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 985; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 986; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 987; CHECK: side.exit: 988; CHECK-NEXT: ret i32 0 989; CHECK: exit: 990; CHECK-NEXT: ret i32 1 991; 992entry: 993 %b = load i32, i32* %bp, !range !0 994 br label %outer 995 996outer: 997 %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge] 998 br label %inner 999 1000 1001inner: 1002 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 1003 %signed_cond = icmp slt i32 %iv, %b 1004 br i1 %signed_cond, label %inner.1, label %side.exit 1005 1006inner.1: 1007 %unsigned_cond = icmp ult i32 %iv, %b 1008 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 1009 1010inner.backedge: 1011 %iv.next = add nuw nsw i32 %iv, 1 1012 %inner.loop.cond = call i1 @cond() 1013 br i1 %inner.loop.cond, label %inner, label %outer.backedge 1014 1015outer.backedge: 1016 %outer.merge = phi i32 [%iv.next, %inner.backedge] 1017 %outer.loop.cond = call i1 @cond() 1018 br i1 %outer.loop.cond, label %outer, label %exit 1019 1020side.exit: 1021 ret i32 0 1022 1023exit: 1024 ret i32 1 1025} 1026 1027; Same as test_03, but non-negativity of %b is known without context. 1028; FIXME: We can remove 2nd check in loop. 1029define i32 @test_07(i32 %a, i32* %bp) { 1030; CHECK-LABEL: @test_07( 1031; CHECK-NEXT: entry: 1032; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 1033; CHECK-NEXT: br label [[OUTER:%.*]] 1034; CHECK: outer: 1035; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ] 1036; CHECK-NEXT: [[OUTER_COND_1:%.*]] = call i1 @cond() 1037; CHECK-NEXT: br i1 [[OUTER_COND_1]], label [[INNER_PREHEADER:%.*]], label [[NO_INNER:%.*]] 1038; CHECK: inner.preheader: 1039; CHECK-NEXT: br label [[INNER:%.*]] 1040; CHECK: no_inner: 1041; CHECK-NEXT: [[OUTER_COND_2:%.*]] = call i1 @cond() 1042; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 1043; CHECK: inner: 1044; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ], [ [[OUTER_IV]], [[INNER_PREHEADER]] ] 1045; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 1046; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 1047; CHECK: inner.1: 1048; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 1049; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 1050; CHECK: inner.backedge: 1051; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 1052; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 1053; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]] 1054; CHECK: outer.backedge.loopexit: 1055; CHECK-NEXT: [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 1056; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 1057; CHECK: outer.backedge: 1058; CHECK-NEXT: [[OUTER_MERGE]] = phi i32 [ [[OUTER_IV]], [[NO_INNER]] ], [ [[IV_NEXT_LCSSA]], [[OUTER_BACKEDGE_LOOPEXIT]] ] 1059; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 1060; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 1061; CHECK: side.exit: 1062; CHECK-NEXT: ret i32 0 1063; CHECK: exit: 1064; CHECK-NEXT: ret i32 1 1065; 1066entry: 1067 %b = load i32, i32* %bp, !range !0 1068 br label %outer 1069 1070outer: 1071 %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge] 1072 %outer_cond_1 = call i1 @cond() 1073 br i1 %outer_cond_1, label %inner, label %no_inner 1074 1075no_inner: 1076 %outer_cond_2 = call i1 @cond() 1077 br label %outer.backedge 1078 1079inner: 1080 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 1081 %signed_cond = icmp slt i32 %iv, %b 1082 br i1 %signed_cond, label %inner.1, label %side.exit 1083 1084inner.1: 1085 %unsigned_cond = icmp ult i32 %iv, %b 1086 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 1087 1088inner.backedge: 1089 %iv.next = add nuw nsw i32 %iv, 1 1090 %inner.loop.cond = call i1 @cond() 1091 br i1 %inner.loop.cond, label %inner, label %outer.backedge 1092 1093outer.backedge: 1094 %outer.merge = phi i32 [%outer.iv, %no_inner], [%iv.next, %inner.backedge] 1095 %outer.loop.cond = call i1 @cond() 1096 br i1 %outer.loop.cond, label %outer, label %exit 1097 1098side.exit: 1099 ret i32 0 1100 1101exit: 1102 ret i32 1 1103} 1104 1105; Same as test_04, but non-negativity of %b is known without context. 1106; FIXME: We can remove 2nd check in loop. 1107define i32 @test_08(i32 %a, i32* %bp) { 1108; CHECK-LABEL: @test_08( 1109; CHECK-NEXT: entry: 1110; CHECK-NEXT: [[B:%.*]] = load i32, i32* [[BP:%.*]], align 4, !range [[RNG0]] 1111; CHECK-NEXT: br label [[OUTER:%.*]] 1112; CHECK: outer: 1113; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_MERGE:%.*]], [[OUTER_BACKEDGE:%.*]] ] 1114; CHECK-NEXT: [[OUTER_COND_1:%.*]] = call i1 @cond() 1115; CHECK-NEXT: br i1 [[OUTER_COND_1]], label [[INNER_PREHEADER:%.*]], label [[NO_INNER:%.*]] 1116; CHECK: inner.preheader: 1117; CHECK-NEXT: br label [[INNER:%.*]] 1118; CHECK: no_inner: 1119; CHECK-NEXT: [[OUTER_COND_2:%.*]] = call i1 @cond() 1120; CHECK-NEXT: br i1 [[OUTER_COND_2]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] 1121; CHECK: if.true: 1122; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[A:%.*]], i32 [[OUTER_IV]]) 1123; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 1124; CHECK: if.false: 1125; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 1126; CHECK: inner: 1127; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[INNER_BACKEDGE:%.*]] ], [ [[OUTER_IV]], [[INNER_PREHEADER]] ] 1128; CHECK-NEXT: [[SIGNED_COND:%.*]] = icmp slt i32 [[IV]], [[B]] 1129; CHECK-NEXT: br i1 [[SIGNED_COND]], label [[INNER_1:%.*]], label [[SIDE_EXIT:%.*]] 1130; CHECK: inner.1: 1131; CHECK-NEXT: [[UNSIGNED_COND:%.*]] = icmp ult i32 [[IV]], [[B]] 1132; CHECK-NEXT: br i1 [[UNSIGNED_COND]], label [[INNER_BACKEDGE]], label [[SIDE_EXIT]] 1133; CHECK: inner.backedge: 1134; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 1135; CHECK-NEXT: [[INNER_LOOP_COND:%.*]] = call i1 @cond() 1136; CHECK-NEXT: br i1 [[INNER_LOOP_COND]], label [[INNER]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]] 1137; CHECK: outer.backedge.loopexit: 1138; CHECK-NEXT: [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[INNER_BACKEDGE]] ] 1139; CHECK-NEXT: br label [[OUTER_BACKEDGE]] 1140; CHECK: outer.backedge: 1141; CHECK-NEXT: [[OUTER_MERGE]] = phi i32 [ [[SMAX]], [[IF_TRUE]] ], [ [[OUTER_IV]], [[IF_FALSE]] ], [ [[IV_NEXT_LCSSA]], [[OUTER_BACKEDGE_LOOPEXIT]] ] 1142; CHECK-NEXT: [[OUTER_LOOP_COND:%.*]] = call i1 @cond() 1143; CHECK-NEXT: br i1 [[OUTER_LOOP_COND]], label [[OUTER]], label [[EXIT:%.*]] 1144; CHECK: side.exit: 1145; CHECK-NEXT: ret i32 0 1146; CHECK: exit: 1147; CHECK-NEXT: ret i32 1 1148; 1149entry: 1150 %b = load i32, i32* %bp, !range !0 1151 br label %outer 1152 1153outer: 1154 %outer.iv = phi i32 [0, %entry], [%outer.merge, %outer.backedge] 1155 %outer_cond_1 = call i1 @cond() 1156 br i1 %outer_cond_1, label %inner, label %no_inner 1157 1158no_inner: 1159 %outer_cond_2 = call i1 @cond() 1160 br i1 %outer_cond_2, label %if.true, label %if.false 1161 1162if.true: 1163 %smax = call i32 @llvm.smax.i32(i32 %a, i32 %outer.iv) 1164 br label %outer.backedge 1165 1166if.false: 1167 br label %outer.backedge 1168 1169inner: 1170 %iv = phi i32 [%outer.iv, %outer], [%iv.next, %inner.backedge] 1171 %signed_cond = icmp slt i32 %iv, %b 1172 br i1 %signed_cond, label %inner.1, label %side.exit 1173 1174inner.1: 1175 %unsigned_cond = icmp ult i32 %iv, %b 1176 br i1 %unsigned_cond, label %inner.backedge, label %side.exit 1177 1178inner.backedge: 1179 %iv.next = add nuw nsw i32 %iv, 1 1180 %inner.loop.cond = call i1 @cond() 1181 br i1 %inner.loop.cond, label %inner, label %outer.backedge 1182 1183outer.backedge: 1184 %outer.merge = phi i32 [%smax, %if.true], [%outer.iv, %if.false], [%iv.next, %inner.backedge] 1185 %outer.loop.cond = call i1 @cond() 1186 br i1 %outer.loop.cond, label %outer, label %exit 1187 1188side.exit: 1189 ret i32 0 1190 1191exit: 1192 ret i32 1 1193} 1194 1195!0 = !{i32 0, i32 2147483647} 1196!1 = !{i32 -2147483648, i32 0} 1197