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(ptr %len.ptr) { 11; CHECK-LABEL: @trivial.case( 12; CHECK-NEXT: entry: 13; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[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, ptr %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, ptr %len.ptr) { 74; CHECK-LABEL: @unknown.start( 75; CHECK-NEXT: entry: 76; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[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 nuw nsw 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, ptr %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(ptr %len.ptr, ptr %sibling.len.ptr) { 140; CHECK-LABEL: @start.from.sibling.iv( 141; CHECK-NEXT: entry: 142; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]] 143; CHECK-NEXT: [[SIBLING_LEN:%.*]] = load i32, ptr [[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 nsw 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, ptr %len.ptr, !range !0 182 %sibling.len = load i32, ptr %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(ptr %len.ptr, ptr %sibling.len.ptr) { 230; CHECK-LABEL: @start.from.sibling.iv.wide( 231; CHECK-NEXT: entry: 232; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]] 233; CHECK-NEXT: [[SIBLING_LEN:%.*]] = load i32, ptr [[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 nsw 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, ptr %len.ptr, !range !0 273 %sibling.len = load i32, ptr %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. 323; TODO: When we check against IV_START, for some reason we then cannot infer nuw for IV.next. 324; It was possible while checking against IV. Missing inference logic somewhere. 325define i32 @start.from.sibling.iv.wide.cycled.phis(ptr %len.ptr, ptr %sibling.len.ptr) { 326; CHECK-LABEL: @start.from.sibling.iv.wide.cycled.phis( 327; CHECK-NEXT: entry: 328; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]] 329; CHECK-NEXT: [[SIBLING_LEN:%.*]] = load i32, ptr [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]] 330; CHECK-NEXT: [[SIBLING_LEN_WIDE:%.*]] = zext i32 [[SIBLING_LEN]] to i64 331; CHECK-NEXT: br label [[SIBLING_LOOP:%.*]] 332; CHECK: sibling.loop: 333; CHECK-NEXT: [[SIBLING_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ] 334; CHECK-NEXT: [[SIBLING_RC:%.*]] = icmp ult i64 [[SIBLING_IV]], [[SIBLING_LEN_WIDE]] 335; CHECK-NEXT: br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]] 336; CHECK: sibling.backedge: 337; CHECK-NEXT: [[SIBLING_IV_NEXT]] = add nuw nsw i64 [[SIBLING_IV]], 1 338; CHECK-NEXT: [[SIBLING_COND:%.*]] = call i1 @cond() 339; CHECK-NEXT: br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[OUTER_LOOP_PREHEADER:%.*]] 340; CHECK: outer.loop.preheader: 341; CHECK-NEXT: [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ] 342; CHECK-NEXT: [[SIBLING_IV_NEXT_TRUNC:%.*]] = trunc i64 [[SIBLING_IV_NEXT_LCSSA]] to i32 343; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] 344; CHECK: outer.loop: 345; CHECK-NEXT: [[IV_START:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_TRUNC]], [[OUTER_LOOP_PREHEADER]] ], [ [[IV_NEXT_LCSSA:%.*]], [[OUTER_LOOP_BACKEDGE:%.*]] ] 346; CHECK-NEXT: br label [[PREHEADER:%.*]] 347; CHECK: preheader: 348; CHECK-NEXT: br label [[LOOP:%.*]] 349; CHECK: loop: 350; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] 351; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]] 352; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] 353; CHECK: signed.passed: 354; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV_START]], [[LEN]] 355; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] 356; CHECK: backedge: 357; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], 1 358; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() 359; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_BACKEDGE]] 360; CHECK: outer.loop.backedge: 361; CHECK-NEXT: [[IV_NEXT_LCSSA]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ] 362; CHECK-NEXT: [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ] 363; CHECK-NEXT: [[OUTER_COND:%.*]] = call i1 @cond() 364; CHECK-NEXT: br i1 [[OUTER_COND]], label [[OUTER_LOOP]], label [[DONE:%.*]] 365; CHECK: failed.signed: 366; CHECK-NEXT: call void @fail(i32 1) 367; CHECK-NEXT: unreachable 368; CHECK: failed.unsigned: 369; CHECK-NEXT: call void @fail(i32 2) 370; CHECK-NEXT: unreachable 371; CHECK: failed.sibling: 372; CHECK-NEXT: call void @fail(i32 3) 373; CHECK-NEXT: unreachable 374; CHECK: done: 375; CHECK-NEXT: [[IV_LCSSA2_LCSSA:%.*]] = phi i32 [ [[IV_LCSSA2]], [[OUTER_LOOP_BACKEDGE]] ] 376; CHECK-NEXT: ret i32 [[IV_LCSSA2_LCSSA]] 377; 378entry: 379 %len = load i32, ptr %len.ptr, !range !0 380 %sibling.len = load i32, ptr %sibling.len.ptr, !range !0 381 %sibling.len.wide = zext i32 %sibling.len to i64 382 br label %sibling.loop 383 384sibling.loop: 385 %sibling.iv = phi i64 [0, %entry], [%sibling.iv.next, %sibling.backedge] 386 %sibling.rc = icmp ult i64 %sibling.iv, %sibling.len.wide 387 br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling 388 389sibling.backedge: 390 %sibling.iv.next = add nuw nsw i64 %sibling.iv, 1 391 %sibling.cond = call i1 @cond() 392 br i1 %sibling.cond, label %sibling.loop, label %outer.loop.preheader 393 394outer.loop.preheader: 395 %sibling.iv.next.trunc = trunc i64 %sibling.iv.next to i32 396 br label %outer.loop 397 398outer.loop: 399 %iv.start = phi i32 [%sibling.iv.next.trunc, %outer.loop.preheader], [%iv.next, %outer.loop.backedge] 400 br label %preheader 401 402preheader: 403 br label %loop 404 405loop: 406 %iv = phi i32 [%iv.start, %preheader], [%iv.next, %backedge] 407 %signed.cmp = icmp slt i32 %iv, %len 408 br i1 %signed.cmp, label %signed.passed, label %failed.signed 409 410signed.passed: 411 %unsigned.cmp = icmp ult i32 %iv, %len 412 br i1 %unsigned.cmp, label %backedge, label %failed.unsigned 413 414backedge: 415 %iv.next = add i32 %iv, 1 416 %cond = call i1 @cond() 417 br i1 %cond, label %loop, label %outer.loop.backedge 418 419 420outer.loop.backedge: 421 %outer.cond = call i1 @cond() 422 br i1 %outer.cond, label %outer.loop, label %done 423 424failed.signed: 425 call void @fail(i32 1) 426 unreachable 427 428failed.unsigned: 429 call void @fail(i32 2) 430 unreachable 431 432failed.sibling: 433 call void @fail(i32 3) 434 unreachable 435 436done: 437 ret i32 %iv 438} 439 440 441; Even more complex version of previous one (more sophisticated cycled phis). 442; TODO: remove unsigned comparison by proving non-negativity of iv.start. 443define i32 @start.from.sibling.iv.wide.cycled.phis.complex.phis(ptr %len.ptr, ptr %sibling.len.ptr, i32 %some.random.value) { 444; CHECK-LABEL: @start.from.sibling.iv.wide.cycled.phis.complex.phis( 445; CHECK-NEXT: entry: 446; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[LEN_PTR:%.*]], align 4, !range [[RNG0]] 447; CHECK-NEXT: [[SIBLING_LEN:%.*]] = load i32, ptr [[SIBLING_LEN_PTR:%.*]], align 4, !range [[RNG0]] 448; CHECK-NEXT: [[SIBLING_LEN_WIDE:%.*]] = zext i32 [[SIBLING_LEN]] to i64 449; CHECK-NEXT: br label [[SIBLING_LOOP:%.*]] 450; CHECK: sibling.loop: 451; CHECK-NEXT: [[SIBLING_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[SIBLING_IV_NEXT:%.*]], [[SIBLING_BACKEDGE:%.*]] ] 452; CHECK-NEXT: [[SIBLING_RC:%.*]] = icmp ult i64 [[SIBLING_IV]], [[SIBLING_LEN_WIDE]] 453; CHECK-NEXT: br i1 [[SIBLING_RC]], label [[SIBLING_BACKEDGE]], label [[FAILED_SIBLING:%.*]] 454; CHECK: sibling.backedge: 455; CHECK-NEXT: [[SIBLING_IV_NEXT]] = add nuw nsw i64 [[SIBLING_IV]], 1 456; CHECK-NEXT: [[SIBLING_COND:%.*]] = call i1 @cond() 457; CHECK-NEXT: br i1 [[SIBLING_COND]], label [[SIBLING_LOOP]], label [[OUTER_LOOP_PREHEADER:%.*]] 458; CHECK: outer.loop.preheader: 459; CHECK-NEXT: [[SIBLING_IV_NEXT_LCSSA:%.*]] = phi i64 [ [[SIBLING_IV_NEXT]], [[SIBLING_BACKEDGE]] ] 460; CHECK-NEXT: [[SIBLING_IV_NEXT_TRUNC:%.*]] = trunc i64 [[SIBLING_IV_NEXT_LCSSA]] to i32 461; CHECK-NEXT: br label [[OUTER_LOOP:%.*]] 462; CHECK: outer.loop: 463; CHECK-NEXT: [[IV_START:%.*]] = phi i32 [ [[SIBLING_IV_NEXT_TRUNC]], [[OUTER_LOOP_PREHEADER]] ], [ [[IV_START_UPDATED:%.*]], [[OUTER_LOOP_BACKEDGE:%.*]] ] 464; CHECK-NEXT: br label [[PREHEADER:%.*]] 465; CHECK: preheader: 466; CHECK-NEXT: br label [[LOOP:%.*]] 467; CHECK: loop: 468; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_START]], [[PREHEADER]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] 469; CHECK-NEXT: [[SIGNED_CMP:%.*]] = icmp slt i32 [[IV]], [[LEN]] 470; CHECK-NEXT: br i1 [[SIGNED_CMP]], label [[SIGNED_PASSED:%.*]], label [[FAILED_SIGNED:%.*]] 471; CHECK: signed.passed: 472; CHECK-NEXT: [[UNSIGNED_CMP:%.*]] = icmp ult i32 [[IV_START]], [[LEN]] 473; CHECK-NEXT: br i1 [[UNSIGNED_CMP]], label [[BACKEDGE]], label [[FAILED_UNSIGNED:%.*]] 474; CHECK: backedge: 475; CHECK-NEXT: [[IV_NEXT]] = add nsw i32 [[IV]], 1 476; CHECK-NEXT: [[COND:%.*]] = call i1 @cond() 477; CHECK-NEXT: br i1 [[COND]], label [[LOOP]], label [[OUTER_LOOP_SELECTION:%.*]] 478; CHECK: outer.loop.selection: 479; CHECK-NEXT: [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ] 480; CHECK-NEXT: [[IV_LCSSA2:%.*]] = phi i32 [ [[IV]], [[BACKEDGE]] ] 481; CHECK-NEXT: [[SWITCH_COND:%.*]] = call i32 @switch.cond() 482; CHECK-NEXT: switch i32 [[SWITCH_COND]], label [[TAKE_SAME:%.*]] [ 483; CHECK-NEXT: i32 1, label [[TAKE_INCREMENT:%.*]] 484; CHECK-NEXT: i32 2, label [[TAKE_SMAX:%.*]] 485; CHECK-NEXT: ] 486; CHECK: take.same: 487; CHECK-NEXT: br label [[OUTER_LOOP_BACKEDGE]] 488; CHECK: take.increment: 489; CHECK-NEXT: br label [[OUTER_LOOP_BACKEDGE]] 490; CHECK: take.smax: 491; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[IV_START]], i32 [[SOME_RANDOM_VALUE:%.*]]) 492; CHECK-NEXT: br label [[OUTER_LOOP_BACKEDGE]] 493; CHECK: outer.loop.backedge: 494; CHECK-NEXT: [[IV_START_UPDATED]] = phi i32 [ [[IV_START]], [[TAKE_SAME]] ], [ [[IV_NEXT_LCSSA]], [[TAKE_INCREMENT]] ], [ [[SMAX]], [[TAKE_SMAX]] ] 495; CHECK-NEXT: [[OUTER_COND:%.*]] = call i1 @cond() 496; CHECK-NEXT: br i1 [[OUTER_COND]], label [[OUTER_LOOP]], label [[DONE:%.*]] 497; CHECK: failed.signed: 498; CHECK-NEXT: call void @fail(i32 1) 499; CHECK-NEXT: unreachable 500; CHECK: failed.unsigned: 501; CHECK-NEXT: call void @fail(i32 2) 502; CHECK-NEXT: unreachable 503; CHECK: failed.sibling: 504; CHECK-NEXT: call void @fail(i32 3) 505; CHECK-NEXT: unreachable 506; CHECK: done: 507; CHECK-NEXT: [[IV_LCSSA2_LCSSA:%.*]] = phi i32 [ [[IV_LCSSA2]], [[OUTER_LOOP_BACKEDGE]] ] 508; CHECK-NEXT: ret i32 [[IV_LCSSA2_LCSSA]] 509; 510entry: 511 %len = load i32, ptr %len.ptr, !range !0 512 %sibling.len = load i32, ptr %sibling.len.ptr, !range !0 513 %sibling.len.wide = zext i32 %sibling.len to i64 514 br label %sibling.loop 515 516sibling.loop: 517 %sibling.iv = phi i64 [0, %entry], [%sibling.iv.next, %sibling.backedge] 518 %sibling.rc = icmp ult i64 %sibling.iv, %sibling.len.wide 519 br i1 %sibling.rc, label %sibling.backedge, label %failed.sibling 520 521sibling.backedge: 522 %sibling.iv.next = add nuw nsw i64 %sibling.iv, 1 523 %sibling.cond = call i1 @cond() 524 br i1 %sibling.cond, label %sibling.loop, label %outer.loop.preheader 525 526outer.loop.preheader: 527 %sibling.iv.next.trunc = trunc i64 %sibling.iv.next to i32 528 br label %outer.loop 529 530outer.loop: 531 %iv.start = phi i32 [%sibling.iv.next.trunc, %outer.loop.preheader], [%iv.start.updated, %outer.loop.backedge] 532 br label %preheader 533 534preheader: 535 br label %loop 536 537loop: 538 %iv = phi i32 [%iv.start, %preheader], [%iv.next, %backedge] 539 %signed.cmp = icmp slt i32 %iv, %len 540 br i1 %signed.cmp, label %signed.passed, label %failed.signed 541 542signed.passed: 543 %unsigned.cmp = icmp ult i32 %iv, %len 544 br i1 %unsigned.cmp, label %backedge, label %failed.unsigned 545 546backedge: 547 %iv.next = add i32 %iv, 1 548 %cond = call i1 @cond() 549 br i1 %cond, label %loop, label %outer.loop.selection 550 551outer.loop.selection: 552 %switch.cond = call i32 @switch.cond() 553 switch i32 %switch.cond, label %take.same 554 [ 555 i32 1, label %take.increment 556 i32 2, label %take.smax 557 ] 558 559take.same: 560 br label %outer.loop.backedge 561 562take.increment: 563 br label %outer.loop.backedge 564 565take.smax: 566 %smax = call i32 @llvm.smax.i32(i32 %iv.start, i32 %some.random.value) 567 br label %outer.loop.backedge 568 569outer.loop.backedge: 570 %iv.start.updated = phi i32 [%iv.start, %take.same], 571 [%iv.next, %take.increment], 572 [%smax, %take.smax] 573 %outer.cond = call i1 @cond() 574 br i1 %outer.cond, label %outer.loop, label %done 575 576failed.signed: 577 call void @fail(i32 1) 578 unreachable 579 580failed.unsigned: 581 call void @fail(i32 2) 582 unreachable 583 584failed.sibling: 585 call void @fail(i32 3) 586 unreachable 587 588done: 589 ret i32 %iv 590} 591 592!0 = !{ i32 0, i32 2147483646 } 593