1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=loop-deletion -verify-dom-info --pass-remarks-output=%t --pass-remarks-filter=loop-delete -S | FileCheck %s 3; RUN: cat %t | FileCheck %s --check-prefix=REMARKS 4 5; Checking that we can delete loops that are never executed. 6; We do not change the constant conditional branch statement (where the not-taken target 7; is the loop) to an unconditional one. 8 9; delete the infinite loop because it is never executed. 10define void @test1(i64 %n, i64 %m) nounwind { 11; CHECK-LABEL: @test1( 12; CHECK-NEXT: entry: 13; CHECK-NEXT: br i1 true, label [[RETURN:%.*]], label [[BB_PREHEADER:%.*]] 14; CHECK: bb.preheader: 15; CHECK-NEXT: br label [[RETURN_LOOPEXIT:%.*]] 16; CHECK: return.loopexit: 17; CHECK-NEXT: br label [[RETURN]] 18; CHECK: return: 19; CHECK-NEXT: ret void 20; 21; REMARKS-LABEL: Function: test1 22; REMARKS: Loop deleted because it never executes 23entry: 24 br i1 true, label %return, label %bb 25 26bb: 27 %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ] 28 %t0 = add i64 %x.0, 1 29 %t1 = icmp slt i64 %x.0, %n 30 %t3 = icmp sgt i64 %x.0, %m 31 %t4 = and i1 %t1, %t3 32 br i1 true, label %bb, label %return 33 34return: 35 ret void 36} 37 38; FIXME: We can delete this infinite loop. Currently we do not, 39; because the infinite loop has no exit block. 40define void @test2(i64 %n, i64 %m) nounwind { 41; CHECK-LABEL: @test2( 42; CHECK-NEXT: entry: 43; CHECK-NEXT: br i1 true, label [[RETURN:%.*]], label [[BB_PREHEADER:%.*]] 44; CHECK: bb.preheader: 45; CHECK-NEXT: br label [[BB:%.*]] 46; CHECK: bb: 47; CHECK-NEXT: [[X_0:%.*]] = phi i64 [ [[T0:%.*]], [[BB]] ], [ 0, [[BB_PREHEADER]] ] 48; CHECK-NEXT: [[T0]] = add i64 [[X_0]], 1 49; CHECK-NEXT: [[T1:%.*]] = icmp slt i64 [[X_0]], [[N:%.*]] 50; CHECK-NEXT: [[T3:%.*]] = icmp sgt i64 [[X_0]], [[M:%.*]] 51; CHECK-NEXT: [[T4:%.*]] = and i1 [[T1]], [[T3]] 52; CHECK-NEXT: br label [[BB]] 53; CHECK: return: 54; CHECK-NEXT: ret void 55; 56entry: 57 br i1 true, label %return, label %bb 58 59bb: 60 %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ] 61 %t0 = add i64 %x.0, 1 62 %t1 = icmp slt i64 %x.0, %n 63 %t3 = icmp sgt i64 %x.0, %m 64 %t4 = and i1 %t1, %t3 65 br label %bb 66 67return: 68 ret void 69} 70 71; There are multiple exiting blocks and a single exit block. 72; Since it is a never executed loop, we do not care about the values 73; from different exiting paths and we can 74; delete the loop. 75define i64 @test3(i64 %n, i64 %m, i64 %maybe_zero) nounwind { 76; CHECK-LABEL: @test3( 77; CHECK-NEXT: entry: 78; CHECK-NEXT: br i1 false, label [[BB_PREHEADER:%.*]], label [[RETURN:%.*]] 79; CHECK: bb.preheader: 80; CHECK-NEXT: br label [[RETURN_LOOPEXIT:%.*]] 81; CHECK: return.loopexit: 82; CHECK-NEXT: [[X_LCSSA_PH:%.*]] = phi i64 [ poison, [[BB_PREHEADER]] ] 83; CHECK-NEXT: br label [[RETURN]] 84; CHECK: return: 85; CHECK-NEXT: [[X_LCSSA:%.*]] = phi i64 [ 20, [[ENTRY:%.*]] ], [ [[X_LCSSA_PH]], [[RETURN_LOOPEXIT]] ] 86; CHECK-NEXT: ret i64 [[X_LCSSA]] 87; 88; REMARKS-LABEL: Function: test3 89; REMARKS: Loop deleted because it never executes 90entry: 91 br i1 false, label %bb, label %return 92 93bb: 94 %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb3 ] 95 %t0 = add i64 %x.0, 1 96 %t1 = icmp slt i64 %x.0, %n 97 br i1 %t1, label %bb2, label %return 98 99bb2: 100 %t2 = icmp slt i64 %x.0, %m 101 %unused1 = udiv i64 42, %maybe_zero 102 br i1 %t2, label %bb3, label %return 103 104bb3: 105 %t3 = icmp slt i64 %x.0, %m 106 %unused2 = sdiv i64 42, %maybe_zero 107 br i1 %t3, label %bb, label %return 108 109return: 110; the only valid value fo x.lcssa is 20. 111 %x.lcssa = phi i64 [ 12, %bb ], [ 14, %bb2 ], [ 16, %bb3 ], [20, %entry ] 112 ret i64 %x.lcssa 113} 114 115; Cannot delete the loop, since it may be executed at runtime. 116define void @test4(i64 %n, i64 %m, i1 %cond) { 117; CHECK-LABEL: @test4( 118; CHECK-NEXT: entry: 119; CHECK-NEXT: br i1 [[COND:%.*]], label [[LOOPPRED1:%.*]], label [[LOOPPRED2:%.*]] 120; CHECK: looppred1: 121; CHECK-NEXT: br i1 true, label [[RETURN:%.*]], label [[BB_PREHEADER:%.*]] 122; CHECK: looppred2: 123; CHECK-NEXT: br i1 false, label [[RETURN]], label [[BB_PREHEADER]] 124; CHECK: bb.preheader: 125; CHECK-NEXT: [[X_0_PH:%.*]] = phi i64 [ 1, [[LOOPPRED2]] ], [ 0, [[LOOPPRED1]] ] 126; CHECK-NEXT: br label [[BB:%.*]] 127; CHECK: bb: 128; CHECK-NEXT: [[X_0:%.*]] = phi i64 [ [[T0:%.*]], [[BB]] ], [ [[X_0_PH]], [[BB_PREHEADER]] ] 129; CHECK-NEXT: [[T0]] = add i64 [[X_0]], 1 130; CHECK-NEXT: [[T1:%.*]] = icmp slt i64 [[X_0]], [[N:%.*]] 131; CHECK-NEXT: [[T3:%.*]] = icmp sgt i64 [[X_0]], [[M:%.*]] 132; CHECK-NEXT: [[T4:%.*]] = and i1 [[T1]], [[T3]] 133; CHECK-NEXT: br i1 true, label [[BB]], label [[RETURN_LOOPEXIT:%.*]] 134; CHECK: return.loopexit: 135; CHECK-NEXT: br label [[RETURN]] 136; CHECK: return: 137; CHECK-NEXT: ret void 138; 139entry: 140 br i1 %cond, label %looppred1, label %looppred2 141 142looppred1: 143 br i1 true, label %return, label %bb 144 145looppred2: 146 br i1 false, label %return, label %bb 147 148bb: 149 %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ] 150 %t0 = add i64 %x.0, 1 151 %t1 = icmp slt i64 %x.0, %n 152 %t3 = icmp sgt i64 %x.0, %m 153 %t4 = and i1 %t1, %t3 154 br i1 true, label %bb, label %return 155 156return: 157 ret void 158} 159 160; multiple constant conditional branches with loop not-taken in all cases. 161define void @test5(i64 %n, i64 %m, i1 %cond) nounwind { 162; CHECK-LABEL: @test5( 163; CHECK-NEXT: entry: 164; CHECK-NEXT: br i1 [[COND:%.*]], label [[LOOPPRED1:%.*]], label [[LOOPPRED2:%.*]] 165; CHECK: looppred1: 166; CHECK-NEXT: br i1 true, label [[RETURN:%.*]], label [[BB_PREHEADER:%.*]] 167; CHECK: looppred2: 168; CHECK-NEXT: br i1 true, label [[RETURN]], label [[BB_PREHEADER]] 169; CHECK: bb.preheader: 170; CHECK-NEXT: [[X_0_PH:%.*]] = phi i64 [ 1, [[LOOPPRED2]] ], [ 0, [[LOOPPRED1]] ] 171; CHECK-NEXT: br label [[RETURN_LOOPEXIT:%.*]] 172; CHECK: return.loopexit: 173; CHECK-NEXT: br label [[RETURN]] 174; CHECK: return: 175; CHECK-NEXT: ret void 176; 177; REMARKS-LABEL: Function: test5 178; REMARKS: Loop deleted because it never executes 179entry: 180 br i1 %cond, label %looppred1, label %looppred2 181 182looppred1: 183 br i1 true, label %return, label %bb 184 185looppred2: 186 br i1 true, label %return, label %bb 187 188bb: 189 %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ] 190 %t0 = add i64 %x.0, 1 191 %t1 = icmp slt i64 %x.0, %n 192 %t3 = icmp sgt i64 %x.0, %m 193 %t4 = and i1 %t1, %t3 194 br i1 true, label %bb, label %return 195 196return: 197 ret void 198} 199 200; Don't delete this infinite loop because the loop 201; is executable at runtime. 202define void @test6(i64 %n, i64 %m) nounwind { 203; CHECK-LABEL: @test6( 204; CHECK-NEXT: entry: 205; CHECK-NEXT: br i1 true, label [[BB_PREHEADER:%.*]], label [[BB_PREHEADER]] 206; CHECK: bb.preheader: 207; CHECK-NEXT: br label [[BB:%.*]] 208; CHECK: bb: 209; CHECK-NEXT: [[X_0:%.*]] = phi i64 [ [[T0:%.*]], [[BB]] ], [ 0, [[BB_PREHEADER]] ] 210; CHECK-NEXT: [[T0]] = add i64 [[X_0]], 1 211; CHECK-NEXT: [[T1:%.*]] = icmp slt i64 [[X_0]], [[N:%.*]] 212; CHECK-NEXT: [[T3:%.*]] = icmp sgt i64 [[X_0]], [[M:%.*]] 213; CHECK-NEXT: [[T4:%.*]] = and i1 [[T1]], [[T3]] 214; CHECK-NEXT: br i1 true, label [[BB]], label [[RETURN:%.*]] 215; CHECK: return: 216; CHECK-NEXT: ret void 217; 218entry: 219 br i1 true, label %bb, label %bb 220 221bb: 222 %x.0 = phi i64 [ 0, %entry ], [ 0, %entry ], [ %t0, %bb ] 223 %t0 = add i64 %x.0, 1 224 %t1 = icmp slt i64 %x.0, %n 225 %t3 = icmp sgt i64 %x.0, %m 226 %t4 = and i1 %t1, %t3 227 br i1 true, label %bb, label %return 228 229return: 230 ret void 231} 232 233declare i64 @foo(i64) 234; The loop L2 is never executed and is a subloop, with an 235; exit block that branches back to parent loop. 236; Here we can delete loop L2, while L1 still exists. 237define i64 @test7(i64 %n) { 238; CHECK-LABEL: @test7( 239; CHECK-NEXT: entry: 240; CHECK-NEXT: br label [[L1:%.*]] 241; CHECK: L1: 242; CHECK-NEXT: [[Y_NEXT:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[Y_ADD:%.*]], [[L1LATCH:%.*]] ] 243; CHECK-NEXT: br i1 true, label [[L1LATCH]], label [[L2_PREHEADER:%.*]] 244; CHECK: L2.preheader: 245; CHECK-NEXT: br label [[L1LATCH_LOOPEXIT:%.*]] 246; CHECK: L1Latch.loopexit: 247; CHECK-NEXT: [[Y_L2_LCSSA:%.*]] = phi i64 [ poison, [[L2_PREHEADER]] ] 248; CHECK-NEXT: br label [[L1LATCH]] 249; CHECK: L1Latch: 250; CHECK-NEXT: [[Y:%.*]] = phi i64 [ [[Y_NEXT]], [[L1]] ], [ [[Y_L2_LCSSA]], [[L1LATCH_LOOPEXIT]] ] 251; CHECK-NEXT: [[Y_ADD]] = add i64 [[Y]], [[N:%.*]] 252; CHECK-NEXT: [[COND2:%.*]] = icmp eq i64 [[Y_ADD]], 42 253; CHECK-NEXT: br i1 [[COND2]], label [[EXIT:%.*]], label [[L1]] 254; CHECK: exit: 255; CHECK-NEXT: [[Y_ADD_LCSSA:%.*]] = phi i64 [ [[Y_ADD]], [[L1LATCH]] ] 256; CHECK-NEXT: ret i64 [[Y_ADD_LCSSA]] 257; 258; REMARKS-LABEL: Function: test7 259; REMARKS: Loop deleted because it never executes 260entry: 261 br label %L1 262 263L1: 264 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ] 265 br i1 true, label %L1Latch, label %L2 266 267L2: 268 %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ] 269 %x.next = add i64 %x, 1 270 %y.L2 = call i64 @foo(i64 %x.next) 271 %cond = icmp slt i64 %x.next, %n 272 br i1 %cond, label %L2, label %L1Latch 273 274L1Latch: 275 %y = phi i64 [ %y.next, %L1 ], [ %y.L2, %L2 ] 276 %y.add = add i64 %y, %n 277 %cond2 = icmp eq i64 %y.add, 42 278 br i1 %cond2, label %exit, label %L1 279 280exit: 281 ret i64 %y.add 282} 283 284 285; Show recursive deletion of loops. Since we start with subloops and progress outward 286; to parent loop, we first delete the loop L2. Now loop L1 becomes a non-loop since it's backedge 287; from L2's preheader to L1's exit block is never taken. So, L1 gets deleted as well. 288define void @test8(i64 %n) { 289; CHECK-LABEL: @test8( 290; CHECK-NEXT: entry: 291; CHECK-NEXT: br label [[EXIT:%.*]] 292; CHECK: exit: 293; CHECK-NEXT: ret void 294; 295; REMARKS-LABEL: Function: test8 296; REMARKS: Loop deleted because it never executes 297entry: 298 br label %L1 299 300L1: 301 br i1 true, label %exit, label %L2 302 303L2: 304 %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ] 305 %x.next = add i64 %x, 1 306 %y.L2 = call i64 @foo(i64 %x.next) 307 %cond = icmp slt i64 %x.next, %n 308 br i1 %cond, label %L2, label %L1 309 310exit: 311 ret void 312} 313 314 315; Delete a loop (L2) which has subloop (L3). 316; Here we delete loop L2, but leave L3 as is. 317define void @test9(i64 %n) { 318; CHECK-LABEL: @test9( 319; CHECK-NEXT: entry: 320; CHECK-NEXT: br label [[EXIT:%.*]] 321; CHECK: exit: 322; CHECK-NEXT: ret void 323; 324; REMARKS-LABEL: Function: test9 325; REMARKS: Loop deleted because it never executes 326entry: 327 br label %L1 328 329L1: 330 br i1 true, label %exit, label %L2 331 332L2: 333 %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ] 334 %x.next = add i64 %x, 1 335 %y.L2 = call i64 @foo(i64 %x.next) 336 %cond = icmp slt i64 %x.next, %n 337 br i1 %cond, label %L2, label %L3 338 339L3: 340 %cond2 = icmp slt i64 %y.L2, %n 341 br i1 %cond2, label %L3, label %L1 342 343exit: 344 ret void 345} 346 347; We cannot delete L3 because of call within it. 348; Since L3 is not deleted, and entirely contained within L2, L2 is also not 349; deleted. 350define void @test10(i64 %n) { 351; CHECK-LABEL: @test10( 352; CHECK-NEXT: entry: 353; CHECK-NEXT: br label [[EXIT:%.*]] 354; CHECK: exit: 355; CHECK-NEXT: ret void 356; 357entry: 358 br label %L1 359 360L1: 361 br i1 true, label %exit, label %L2 362 363L2: 364 %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ] 365 %x.next = add i64 %x, 1 366 %y.L2 = call i64 @foo(i64 %x.next) 367 %cond = icmp slt i64 %x.next, %n 368 br i1 %cond, label %L1, label %L3 369 370L3: 371 %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ] 372 %y.L3.next = add i64 %y.L3, 1 373 %dummy = call i64 @foo(i64 %y.L3.next) 374 %cond2 = icmp slt i64 %y.L3, %n 375 br i1 %cond2, label %L3, label %L2 376 377exit: 378 ret void 379} 380 381; same as test10, but L3 does not contain call. 382; So, in the first iteration, all statements of L3 are made invariant, and L3 is 383; deleted. 384; In the next iteration, since L2 is never executed and has no subloops, we delete 385; L2 as well. Finally, the outermost loop L1 is deleted. 386define void @test11(i64 %n) { 387; CHECK-LABEL: @test11( 388; CHECK-NEXT: entry: 389; CHECK-NEXT: br label [[EXIT:%.*]] 390; CHECK: exit: 391; CHECK-NEXT: ret void 392; 393; REMARKS-LABEL: Function: test11 394; REMARKS: Loop deleted because it is invariant 395; REMARKS-LABEL: Function: test11 396; REMARKS: Loop deleted because it never executes 397; REMARKS-LABEL: Function: test11 398; REMARKS: Loop deleted because it is invariant 399entry: 400 br label %L1 401 402L1: 403 br i1 true, label %exit, label %L2 404 405L2: 406 %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ] 407 %x.next = add i64 %x, 1 408 %y.L2 = call i64 @foo(i64 %x.next) 409 %cond = icmp slt i64 %x.next, %n 410 br i1 %cond, label %L1, label %L3 411 412L3: 413 %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ] 414 %y.L3.next = add i64 %y.L3, 1 415 %cond2 = icmp slt i64 %y.L3, %n 416 br i1 %cond2, label %L3, label %L2 417 418exit: 419 ret void 420} 421 422 423; 2 edges from a single exiting block to the exit block. 424define i64 @test12(i64 %n){ 425; CHECK-LABEL: @test12( 426; CHECK-NEXT: entry: 427; CHECK-NEXT: br i1 true, label [[EXIT1:%.*]], label [[L1_PREHEADER:%.*]] 428; CHECK: L1.preheader: 429; CHECK-NEXT: br label [[EXIT:%.*]] 430; CHECK: exit1: 431; CHECK-NEXT: ret i64 42 432; CHECK: exit: 433; CHECK-NEXT: [[Y_PHI:%.*]] = phi i64 [ poison, [[L1_PREHEADER]] ] 434; CHECK-NEXT: ret i64 [[Y_PHI]] 435; 436; REMARKS-LABEL: Function: test12 437; REMARKS: Loop deleted because it never executes 438 439entry: 440 br i1 true, label %exit1, label %L1 441 442exit1: 443 ret i64 42 444 445L1: ; preds = %L1Latch, %entry 446 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ] 447 br i1 true, label %L1Latch, label %exit 448 449L1Latch: ; preds = %L1 450 %y = phi i64 [ %y.next, %L1 ] 451 %y.add = add i64 %y, %n 452 %cond2 = icmp eq i64 %y.add, 42 453 switch i64 %n, label %L1 [ 454 i64 10, label %exit 455 i64 20, label %exit 456 ] 457 458exit: ; preds = %L1Latch, %L1Latch 459 %y.phi = phi i64 [ 10, %L1Latch ], [ 10, %L1Latch ], [ %y.next, %L1] 460 ret i64 %y.phi 461} 462 463; multiple edges to exit block from the same exiting blocks 464define i64 @test13(i64 %n) { 465; CHECK-LABEL: @test13( 466; CHECK-NEXT: entry: 467; CHECK-NEXT: br i1 true, label [[EXIT1:%.*]], label [[L1_PREHEADER:%.*]] 468; CHECK: L1.preheader: 469; CHECK-NEXT: br label [[EXIT:%.*]] 470; CHECK: exit1: 471; CHECK-NEXT: ret i64 42 472; CHECK: exit: 473; CHECK-NEXT: [[Y_PHI:%.*]] = phi i64 [ poison, [[L1_PREHEADER]] ] 474; CHECK-NEXT: ret i64 [[Y_PHI]] 475; 476; REMARKS-LABEL: Function: test13 477; REMARKS: Loop deleted because it never executes 478 479entry: 480 br i1 true, label %exit1, label %L1 481 482exit1: 483 ret i64 42 484 485L1: ; preds = %L1Latch, %entry 486 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ] 487 br i1 true, label %L1Block, label %exit 488 489L1Block: ; preds = %L1 490 %y = phi i64 [ %y.next, %L1 ] 491 %y.add = add i64 %y, %n 492 %cond2 = icmp eq i64 %y.add, 42 493 switch i64 %n, label %L1Latch [ 494 i64 10, label %exit 495 i64 20, label %exit 496 ] 497 498L1Latch: 499 switch i64 %n, label %L1 [ 500 i64 30, label %exit 501 i64 40, label %exit 502 ] 503 504exit: ; preds = %L1Block, %L1, %L1Latch 505 %y.phi = phi i64 [ 10, %L1Block ], [ 10, %L1Block ], [ %y.next, %L1 ], [ 30, %L1Latch ], [ 30, %L1Latch ] 506 ret i64 %y.phi 507} 508