1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=indvars -S | FileCheck %s 3 4declare void @fail(i32) 5declare i1 @cond() 6declare i32 @switch.cond() 7declare i32 @llvm.smax.i32(i32 %a, i32 %b) 8 9; Unsigned comparison here is redundant and can be safely deleted. 10define i32 @trivial.case(i32* %len.ptr) { 11; CHECK-LABEL: @trivial.case( 12; CHECK-NEXT: entry: 13; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0:![0-9]+]] 14; CHECK-NEXT: br label [[PREHEADER:%.*]] 15; CHECK: preheader: 16; CHECK-NEXT: br label [[LOOP:%.*]] 17; CHECK: loop: 18; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] 19; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]] 20; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] 21; CHECK: signed.passed: 22; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] 23; CHECK: backedge: 24; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 25; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() 26; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]] 27; CHECK: failed.signed: 28; CHECK-NEXT: call void @fail(i32 1) 29; CHECK-NEXT: unreachable 30; CHECK: failed.unsigned: 31; CHECK-NEXT: call void @fail(i32 2) 32; CHECK-NEXT: unreachable 33; CHECK: done: 34; CHECK-NEXT: [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ] 35; CHECK-NEXT: ret i32 [[IV_LCSSA2]] 36; 37entry: 38 %len = load i32, i32* %len.ptr, !range !0 39 br label %preheader 40 41preheader: 42 br label %loop 43 44loop: 45 %iv = phi i32 [0, %preheader], [%iv.next, %backedge] 46 %signed.cmp = icmp slt i32 %iv, %len 47 br i1 %signed.cmp, label %signed.passed, label %failed.signed 48 49signed.passed: 50 %unsigned.cmp = icmp ult i32 %iv, %len 51 br i1 %unsigned.cmp, label %backedge, label %failed.unsigned 52 53backedge: 54 %iv.next = add i32 %iv, 1 55 %cond = call i1 @cond() 56 br i1 %cond, label %loop, label %done 57 58failed.signed: 59 call void @fail(i32 1) 60 unreachable 61 62failed.unsigned: 63 call void @fail(i32 2) 64 unreachable 65 66done: 67 ret i32 %iv 68} 69 70; TODO: The 2nd check can be made invariant. 71; slt and ult checks are equivalent. When IV is negative, slt check will pass and ult will 72; fail. Because IV is incrementing, this will fail on 1st iteration or never. 73define i32 @unknown.start(i32 %start, i32* %len.ptr) { 74; CHECK-LABEL: @unknown.start( 75; CHECK-NEXT: entry: 76; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]] 77; CHECK-NEXT: br label [[PREHEADER:%.*]] 78; CHECK: preheader: 79; CHECK-NEXT: br label [[LOOP:%.*]] 80; CHECK: loop: 81; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] 82; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]] 83; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] 84; CHECK: signed.passed: 85; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]] 86; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] 87; CHECK: backedge: 88; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 89; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() 90; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]] 91; CHECK: failed.signed: 92; CHECK-NEXT: call void @fail(i32 1) 93; CHECK-NEXT: unreachable 94; CHECK: failed.unsigned: 95; CHECK-NEXT: call void @fail(i32 2) 96; CHECK-NEXT: unreachable 97; CHECK: done: 98; CHECK-NEXT: [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ] 99; CHECK-NEXT: ret i32 [[IV_LCSSA2]] 100; 101entry: 102 %len = load i32, i32* %len.ptr, !range !0 103 br label %preheader 104 105preheader: 106 br label %loop 107 108loop: 109 %iv = phi i32 [%start, %preheader], [%iv.next, %backedge] 110 %signed.cmp = icmp slt i32 %iv, %len 111 br i1 %signed.cmp, label %signed.passed, label %failed.signed 112 113signed.passed: 114 %unsigned.cmp = icmp ult i32 %iv, %len 115 br i1 %unsigned.cmp, label %backedge, label %failed.unsigned 116 117backedge: 118 %iv.next = add i32 %iv, 1 119 %cond = call i1 @cond() 120 br i1 %cond, label %loop, label %done 121 122failed.signed: 123 call void @fail(i32 1) 124 unreachable 125 126failed.unsigned: 127 call void @fail(i32 2) 128 unreachable 129 130done: 131 ret i32 %iv 132} 133 134 135; TODO: We should be able to prove that: 136; - %sibling.iv.next is non-negative; 137; - therefore, %iv is non-negative; 138; - therefore, unsigned check can be removed. 139define i32 @start.from.sibling.iv(i32* %len.ptr, i32* %sibling.len.ptr) { 140; CHECK-LABEL: @start.from.sibling.iv( 141; CHECK-NEXT: entry: 142; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]] 143; CHECK-NEXT: [[SIBLING_LEN:%.*]] = load i32, i32* [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]] 144; CHECK-NEXT: br label [[SIBLING_LOOP:%.*]] 145; CHECK: sibling.loop: 146; CHECK-NEXT: [[SIBLING_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ] 147; CHECK-NEXT: [[SIBLING_RC:%.*]] = icmp ult i32 [[SIBLING_IV]], [[SIBLING_LEN]] 148; CHECK-NEXT: br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]] 149; CHECK: sibling.backedge: 150; CHECK-NEXT: [[SIBLING_IV_NEXT]] = add nuw nsw i32 [[SIBLING_IV]], 1 151; CHECK-NEXT: [[SIBLING_COND:%.*]] = call i1 @cond() 152; CHECK-NEXT: br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[PREHEADER:%.*]] 153; CHECK: preheader: 154; CHECK-NEXT: [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i32 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ] 155; CHECK-NEXT: br label [[LOOP:%.*]] 156; CHECK: loop: 157; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_LCSSA]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] 158; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]] 159; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] 160; CHECK: signed.passed: 161; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]] 162; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] 163; CHECK: backedge: 164; CHECK-NEXT: [[IV_NEXT]] = add nuw i32 [[IV]], 1 165; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() 166; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]] 167; CHECK: failed.signed: 168; CHECK-NEXT: call void @fail(i32 1) 169; CHECK-NEXT: unreachable 170; CHECK: failed.unsigned: 171; CHECK-NEXT: call void @fail(i32 2) 172; CHECK-NEXT: unreachable 173; CHECK: failed.sibling: 174; CHECK-NEXT: call void @fail(i32 3) 175; CHECK-NEXT: unreachable 176; CHECK: done: 177; CHECK-NEXT: [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ] 178; CHECK-NEXT: ret i32 [[IV_LCSSA2]] 179; 180entry: 181 %len = load i32, i32* %len.ptr, !range !0 182 %sibling.len = load i32, i32* %sibling.len.ptr, !range !0 183 br label %sibling.loop 184 185sibling.loop: 186 %sibling.iv = phi i32 [0, %entry], [%sibling.iv.next, %sibling.backedge] 187 %sibling.rc = icmp ult i32 %sibling.iv, %sibling.len 188 br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling 189 190sibling.backedge: 191 %sibling.iv.next = add nuw nsw i32 %sibling.iv, 1 192 %sibling.cond = call i1 @cond() 193 br i1 %sibling.cond, label %sibling.loop, label %preheader 194 195preheader: 196 br label %loop 197 198loop: 199 %iv = phi i32 [%sibling.iv.next, %preheader], [%iv.next, %backedge] 200 %signed.cmp = icmp slt i32 %iv, %len 201 br i1 %signed.cmp, label %signed.passed, label %failed.signed 202 203signed.passed: 204 %unsigned.cmp = icmp ult i32 %iv, %len 205 br i1 %unsigned.cmp, label %backedge, label %failed.unsigned 206 207backedge: 208 %iv.next = add i32 %iv, 1 209 %cond = call i1 @cond() 210 br i1 %cond, label %loop, label %done 211 212failed.signed: 213 call void @fail(i32 1) 214 unreachable 215 216failed.unsigned: 217 call void @fail(i32 2) 218 unreachable 219 220failed.sibling: 221 call void @fail(i32 3) 222 unreachable 223 224done: 225 ret i32 %iv 226} 227 228; Same as above, but the sibling loop is now wide. We can eliminate the unsigned comparison here. 229define i32 @start.from.sibling.iv.wide(i32* %len.ptr, i32* %sibling.len.ptr) { 230; CHECK-LABEL: @start.from.sibling.iv.wide( 231; CHECK-NEXT: entry: 232; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]] 233; CHECK-NEXT: [[SIBLING_LEN:%.*]] = load i32, i32* [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]] 234; CHECK-NEXT: [[SIBLING_LEN_WIDE:%.*]] = zext i32 [[SIBLING_LEN]] to i64 235; CHECK-NEXT: br label [[SIBLING_LOOP:%.*]] 236; CHECK: sibling.loop: 237; CHECK-NEXT: [[SIBLING_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ] 238; CHECK-NEXT: [[SIBLING_RC:%.*]] = icmp ult i64 [[SIBLING_IV]], [[SIBLING_LEN_WIDE]] 239; CHECK-NEXT: br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]] 240; CHECK: sibling.backedge: 241; CHECK-NEXT: [[SIBLING_IV_NEXT]] = add nuw nsw i64 [[SIBLING_IV]], 1 242; CHECK-NEXT: [[SIBLING_COND:%.*]] = call i1 @cond() 243; CHECK-NEXT: br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[PREHEADER:%.*]] 244; CHECK: preheader: 245; CHECK-NEXT: [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ] 246; CHECK-NEXT: [[SIBLING_IV_NEXT_TRUNC:%.*]] = trunc i64 [[SIBLING_IV_NEXT_LCSSA]] to i32 247; CHECK-NEXT: br label [[LOOP:%.*]] 248; CHECK: loop: 249; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_TRUNC]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] 250; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]] 251; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] 252; CHECK: signed.passed: 253; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] 254; CHECK: backedge: 255; CHECK-NEXT: [[IV_NEXT]] = add nuw i32 [[IV]], 1 256; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() 257; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[DONE:%.*]] 258; CHECK: failed.signed: 259; CHECK-NEXT: call void @fail(i32 1) 260; CHECK-NEXT: unreachable 261; CHECK: failed.unsigned: 262; CHECK-NEXT: call void @fail(i32 2) 263; CHECK-NEXT: unreachable 264; CHECK: failed.sibling: 265; CHECK-NEXT: call void @fail(i32 3) 266; CHECK-NEXT: unreachable 267; CHECK: done: 268; CHECK-NEXT: [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ] 269; CHECK-NEXT: ret i32 [[IV_LCSSA2]] 270; 271entry: 272 %len = load i32, i32* %len.ptr, !range !0 273 %sibling.len = load i32, i32* %sibling.len.ptr, !range !0 274 %sibling.len.wide = zext i32 %sibling.len to i64 275 br label %sibling.loop 276 277sibling.loop: 278 %sibling.iv = phi i64 [0, %entry], [%sibling.iv.next, %sibling.backedge] 279 %sibling.rc = icmp ult i64 %sibling.iv, %sibling.len.wide 280 br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling 281 282sibling.backedge: 283 %sibling.iv.next = add nuw nsw i64 %sibling.iv, 1 284 %sibling.cond = call i1 @cond() 285 br i1 %sibling.cond, label %sibling.loop, label %preheader 286 287preheader: 288 %sibling.iv.next.trunc = trunc i64 %sibling.iv.next to i32 289 br label %loop 290 291loop: 292 %iv = phi i32 [%sibling.iv.next.trunc, %preheader], [%iv.next, %backedge] 293 %signed.cmp = icmp slt i32 %iv, %len 294 br i1 %signed.cmp, label %signed.passed, label %failed.signed 295 296signed.passed: 297 %unsigned.cmp = icmp ult i32 %iv, %len 298 br i1 %unsigned.cmp, label %backedge, label %failed.unsigned 299 300backedge: 301 %iv.next = add i32 %iv, 1 302 %cond = call i1 @cond() 303 br i1 %cond, label %loop, label %done 304 305failed.signed: 306 call void @fail(i32 1) 307 unreachable 308 309failed.unsigned: 310 call void @fail(i32 2) 311 unreachable 312 313failed.sibling: 314 call void @fail(i32 3) 315 unreachable 316 317done: 318 ret i32 %iv 319} 320 321; Slightly more complex version of previous one (cycled phis). 322; TODO: remove unsigned comparison by proving non-negativity of iv.start. 323define i32 @start.from.sibling.iv.wide.cycled.phis(i32* %len.ptr, i32* %sibling.len.ptr) { 324; CHECK-LABEL: @start.from.sibling.iv.wide.cycled.phis( 325; CHECK-NEXT: entry: 326; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]] 327; CHECK-NEXT: [[SIBLING_LEN:%.*]] = load i32, i32* [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]] 328; CHECK-NEXT: [[SIBLING_LEN_WIDE:%.*]] = zext i32 [[SIBLING_LEN]] to i64 329; CHECK-NEXT: br label [[SIBLING_LOOP:%.*]] 330; CHECK: sibling.loop: 331; CHECK-NEXT: [[SIBLING_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ] 332; CHECK-NEXT: [[SIBLING_RC:%.*]] = icmp ult i64 [[SIBLING_IV]], [[SIBLING_LEN_WIDE]] 333; CHECK-NEXT: br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]] 334; CHECK: sibling.backedge: 335; CHECK-NEXT: [[SIBLING_IV_NEXT]] = add nuw nsw i64 [[SIBLING_IV]], 1 336; CHECK-NEXT: [[SIBLING_COND:%.*]] = call i1 @cond() 337; CHECK-NEXT: br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[OUTER_LOOP_PREHEADER:%.*]] 338; CHECK: outer.loop.preheader: 339; CHECK-NEXT: [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ] 340; CHECK-NEXT: [[SIBLING_IV_NEXT_TRUNC:%.*]] = trunc i64 [[SIBLING_IV_NEXT_LCSSA]] to i32 341; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] 342; CHECK: outer.loop: 343; CHECK-NEXT: [[IV_START:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_TRUNC]], [[OUTER_LOOP_PREHEADER]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_LOOP_BACKEDGE:%.*]] ] 344; CHECK-NEXT: br label [[PREHEADER:%.*]] 345; CHECK: preheader: 346; CHECK-NEXT: br label [[LOOP:%.*]] 347; CHECK: loop: 348; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] 349; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]] 350; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] 351; CHECK: signed.passed: 352; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]] 353; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] 354; CHECK: backedge: 355; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 356; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() 357; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_BACKEDGE]] 358; CHECK: outer.loop.backedge: 359; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ] 360; CHECK-NEXT: [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ] 361; CHECK-NEXT: [[OUTER_COND:%.*]] = call i1 @cond() 362; CHECK-NEXT: br i1 [[OUTER_COND]], label [[OUTER_LOOP]], label [[DONE:%.*]] 363; CHECK: failed.signed: 364; CHECK-NEXT: call void @fail(i32 1) 365; CHECK-NEXT: unreachable 366; CHECK: failed.unsigned: 367; CHECK-NEXT: call void @fail(i32 2) 368; CHECK-NEXT: unreachable 369; CHECK: failed.sibling: 370; CHECK-NEXT: call void @fail(i32 3) 371; CHECK-NEXT: unreachable 372; CHECK: done: 373; CHECK-NEXT: [[IV_LCSSA2_LCSSA:%.*]] = phi i32 [ [[IV_LCSSA2]], [[OUTER_LOOP_BACKEDGE]] ] 374; CHECK-NEXT: ret i32 [[IV_LCSSA2_LCSSA]] 375; 376entry: 377 %len = load i32, i32* %len.ptr, !range !0 378 %sibling.len = load i32, i32* %sibling.len.ptr, !range !0 379 %sibling.len.wide = zext i32 %sibling.len to i64 380 br label %sibling.loop 381 382sibling.loop: 383 %sibling.iv = phi i64 [0, %entry], [%sibling.iv.next, %sibling.backedge] 384 %sibling.rc = icmp ult i64 %sibling.iv, %sibling.len.wide 385 br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling 386 387sibling.backedge: 388 %sibling.iv.next = add nuw nsw i64 %sibling.iv, 1 389 %sibling.cond = call i1 @cond() 390 br i1 %sibling.cond, label %sibling.loop, label %outer.loop.preheader 391 392outer.loop.preheader: 393 %sibling.iv.next.trunc = trunc i64 %sibling.iv.next to i32 394 br label %outer.loop 395 396outer.loop: 397 %iv.start = phi i32 [%sibling.iv.next.trunc, %outer.loop.preheader], [%iv.next, %outer.loop.backedge] 398 br label %preheader 399 400preheader: 401 br label %loop 402 403loop: 404 %iv = phi i32 [%iv.start, %preheader], [%iv.next, %backedge] 405 %signed.cmp = icmp slt i32 %iv, %len 406 br i1 %signed.cmp, label %signed.passed, label %failed.signed 407 408signed.passed: 409 %unsigned.cmp = icmp ult i32 %iv, %len 410 br i1 %unsigned.cmp, label %backedge, label %failed.unsigned 411 412backedge: 413 %iv.next = add i32 %iv, 1 414 %cond = call i1 @cond() 415 br i1 %cond, label %loop, label %outer.loop.backedge 416 417 418outer.loop.backedge: 419 %outer.cond = call i1 @cond() 420 br i1 %outer.cond, label %outer.loop, label %done 421 422failed.signed: 423 call void @fail(i32 1) 424 unreachable 425 426failed.unsigned: 427 call void @fail(i32 2) 428 unreachable 429 430failed.sibling: 431 call void @fail(i32 3) 432 unreachable 433 434done: 435 ret i32 %iv 436} 437 438 439; Even more complex version of previous one (more sophisticated cycled phis). 440; TODO: remove unsigned comparison by proving non-negativity of iv.start. 441define i32 @start.from.sibling.iv.wide.cycled.phis.complex.phis(i32* %len.ptr, i32* %sibling.len.ptr, i32 %some.random.value) { 442; CHECK-LABEL: @start.from.sibling.iv.wide.cycled.phis.complex.phis( 443; CHECK-NEXT: entry: 444; CHECK-NEXT: [[LEN:%.*]] = load i32, i32* [[LEN_PTR:%.*]], align 4, !range [[RNG0]] 445; CHECK-NEXT: [[SIBLING_LEN:%.*]] = load i32, i32* [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]] 446; CHECK-NEXT: [[SIBLING_LEN_WIDE:%.*]] = zext i32 [[SIBLING_LEN]] to i64 447; CHECK-NEXT: br label [[SIBLING_LOOP:%.*]] 448; CHECK: sibling.loop: 449; CHECK-NEXT: [[SIBLING_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ] 450; CHECK-NEXT: [[SIBLING_RC:%.*]] = icmp ult i64 [[SIBLING_IV]], [[SIBLING_LEN_WIDE]] 451; CHECK-NEXT: br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]] 452; CHECK: sibling.backedge: 453; CHECK-NEXT: [[SIBLING_IV_NEXT]] = add nuw nsw i64 [[SIBLING_IV]], 1 454; CHECK-NEXT: [[SIBLING_COND:%.*]] = call i1 @cond() 455; CHECK-NEXT: br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[OUTER_LOOP_PREHEADER:%.*]] 456; CHECK: outer.loop.preheader: 457; CHECK-NEXT: [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ] 458; CHECK-NEXT: [[SIBLING_IV_NEXT_TRUNC:%.*]] = trunc i64 [[SIBLING_IV_NEXT_LCSSA]] to i32 459; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] 460; CHECK: outer.loop: 461; CHECK-NEXT: [[IV_START:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_TRUNC]], [[OUTER_LOOP_PREHEADER]] ], [ [[IV_START_UPDATED:%.*]], [[OUTER_LOOP_BACKEDGE:%.*]] ] 462; CHECK-NEXT: br label [[PREHEADER:%.*]] 463; CHECK: preheader: 464; CHECK-NEXT: br label [[LOOP:%.*]] 465; CHECK: loop: 466; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] 467; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]] 468; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] 469; CHECK: signed.passed: 470; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV]], [[LEN]] 471; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] 472; CHECK: backedge: 473; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 474; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() 475; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_SELECTION:%.*]] 476; CHECK: outer.loop.selection: 477; CHECK-NEXT: [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ] 478; CHECK-NEXT: [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ] 479; CHECK-NEXT: [[SWITCH_COND:%.*]] = call i32 @switch.cond() 480; CHECK-NEXT: switch i32 [[SWITCH_COND]], label [[TAKE_SAME:%.*]] [ 481; CHECK-NEXT: i32 1, label [[TAKE_INCREMENT:%.*]] 482; CHECK-NEXT: i32 2, label [[TAKE_SMAX:%.*]] 483; CHECK-NEXT: ] 484; CHECK: take.same: 485; CHECK-NEXT: br label [[OUTER_LOOP_BACKEDGE]] 486; CHECK: take.increment: 487; CHECK-NEXT: br label [[OUTER_LOOP_BACKEDGE]] 488; CHECK: take.smax: 489; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[IV_START]], i32 [[SOME_RANDOM_VALUE:%.*]]) 490; CHECK-NEXT: br label [[OUTER_LOOP_BACKEDGE]] 491; CHECK: outer.loop.backedge: 492; CHECK-NEXT: [[IV_START_UPDATED]] = phi i32 [ [[IV_START]], [[TAKE_SAME]] ], [ [[IV_NEXT_LCSSA]], [[TAKE_INCREMENT]] ], [ [[SMAX]], [[TAKE_SMAX]] ] 493; CHECK-NEXT: [[OUTER_COND:%.*]] = call i1 @cond() 494; CHECK-NEXT: br i1 [[OUTER_COND]], label [[OUTER_LOOP]], label [[DONE:%.*]] 495; CHECK: failed.signed: 496; CHECK-NEXT: call void @fail(i32 1) 497; CHECK-NEXT: unreachable 498; CHECK: failed.unsigned: 499; CHECK-NEXT: call void @fail(i32 2) 500; CHECK-NEXT: unreachable 501; CHECK: failed.sibling: 502; CHECK-NEXT: call void @fail(i32 3) 503; CHECK-NEXT: unreachable 504; CHECK: done: 505; CHECK-NEXT: [[IV_LCSSA2_LCSSA:%.*]] = phi i32 [ [[IV_LCSSA2]], [[OUTER_LOOP_BACKEDGE]] ] 506; CHECK-NEXT: ret i32 [[IV_LCSSA2_LCSSA]] 507; 508entry: 509 %len = load i32, i32* %len.ptr, !range !0 510 %sibling.len = load i32, i32* %sibling.len.ptr, !range !0 511 %sibling.len.wide = zext i32 %sibling.len to i64 512 br label %sibling.loop 513 514sibling.loop: 515 %sibling.iv = phi i64 [0, %entry], [%sibling.iv.next, %sibling.backedge] 516 %sibling.rc = icmp ult i64 %sibling.iv, %sibling.len.wide 517 br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling 518 519sibling.backedge: 520 %sibling.iv.next = add nuw nsw i64 %sibling.iv, 1 521 %sibling.cond = call i1 @cond() 522 br i1 %sibling.cond, label %sibling.loop, label %outer.loop.preheader 523 524outer.loop.preheader: 525 %sibling.iv.next.trunc = trunc i64 %sibling.iv.next to i32 526 br label %outer.loop 527 528outer.loop: 529 %iv.start = phi i32 [%sibling.iv.next.trunc, %outer.loop.preheader], [%iv.start.updated, %outer.loop.backedge] 530 br label %preheader 531 532preheader: 533 br label %loop 534 535loop: 536 %iv = phi i32 [%iv.start, %preheader], [%iv.next, %backedge] 537 %signed.cmp = icmp slt i32 %iv, %len 538 br i1 %signed.cmp, label %signed.passed, label %failed.signed 539 540signed.passed: 541 %unsigned.cmp = icmp ult i32 %iv, %len 542 br i1 %unsigned.cmp, label %backedge, label %failed.unsigned 543 544backedge: 545 %iv.next = add i32 %iv, 1 546 %cond = call i1 @cond() 547 br i1 %cond, label %loop, label %outer.loop.selection 548 549outer.loop.selection: 550 %switch.cond = call i32 @switch.cond() 551 switch i32 %switch.cond, label %take.same 552 [ 553 i32 1, label %take.increment 554 i32 2, label %take.smax 555 ] 556 557take.same: 558 br label %outer.loop.backedge 559 560take.increment: 561 br label %outer.loop.backedge 562 563take.smax: 564 %smax = call i32 @llvm.smax.i32(i32 %iv.start, i32 %some.random.value) 565 br label %outer.loop.backedge 566 567outer.loop.backedge: 568 %iv.start.updated = phi i32 [%iv.start, %take.same], 569 [%iv.next, %take.increment], 570 [%smax, %take.smax] 571 %outer.cond = call i1 @cond() 572 br i1 %outer.cond, label %outer.loop, label %done 573 574failed.signed: 575 call void @fail(i32 1) 576 unreachable 577 578failed.unsigned: 579 call void @fail(i32 2) 580 unreachable 581 582failed.sibling: 583 call void @fail(i32 3) 584 unreachable 585 586done: 587 ret i32 %iv 588} 589 590!0 = !{ i32 0, i32 2147483646 } 591