508 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=loop-deletion -verify-dom-info --pass-remarks-output=%t --pass-remarks-filter=loop-delete -S | FileCheck %s3; RUN: cat %t | FileCheck %s --check-prefix=REMARKS4 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 target7; 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 void20;21; REMARKS-LABEL: Function: test122; REMARKS: Loop deleted because it never executes23entry:24 br i1 true, label %return, label %bb25 26bb:27 %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ]28 %t0 = add i64 %x.0, 129 %t1 = icmp slt i64 %x.0, %n30 %t3 = icmp sgt i64 %x.0, %m31 %t4 = and i1 %t1, %t332 br i1 true, label %bb, label %return33 34return:35 ret void36}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]], 149; 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 void55;56entry:57 br i1 true, label %return, label %bb58 59bb:60 %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb ]61 %t0 = add i64 %x.0, 162 %t1 = icmp slt i64 %x.0, %n63 %t3 = icmp sgt i64 %x.0, %m64 %t4 = and i1 %t1, %t365 br label %bb66 67return:68 ret void69}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 values73; from different exiting paths and we can74; 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: test389; REMARKS: Loop deleted because it never executes90entry:91 br i1 false, label %bb, label %return92 93bb:94 %x.0 = phi i64 [ 0, %entry ], [ %t0, %bb3 ]95 %t0 = add i64 %x.0, 196 %t1 = icmp slt i64 %x.0, %n97 br i1 %t1, label %bb2, label %return98 99bb2:100 %t2 = icmp slt i64 %x.0, %m101 %unused1 = udiv i64 42, %maybe_zero102 br i1 %t2, label %bb3, label %return103 104bb3:105 %t3 = icmp slt i64 %x.0, %m106 %unused2 = sdiv i64 42, %maybe_zero107 br i1 %t3, label %bb, label %return108 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.lcssa113}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]], 1130; 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 void138;139entry:140 br i1 %cond, label %looppred1, label %looppred2141 142looppred1:143 br i1 true, label %return, label %bb144 145looppred2:146 br i1 false, label %return, label %bb147 148bb:149 %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ]150 %t0 = add i64 %x.0, 1151 %t1 = icmp slt i64 %x.0, %n152 %t3 = icmp sgt i64 %x.0, %m153 %t4 = and i1 %t1, %t3154 br i1 true, label %bb, label %return155 156return:157 ret void158}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 void176;177; REMARKS-LABEL: Function: test5178; REMARKS: Loop deleted because it never executes179entry:180 br i1 %cond, label %looppred1, label %looppred2181 182looppred1:183 br i1 true, label %return, label %bb184 185looppred2:186 br i1 true, label %return, label %bb187 188bb:189 %x.0 = phi i64 [ 0, %looppred1 ], [ 1, %looppred2 ], [ %t0, %bb ]190 %t0 = add i64 %x.0, 1191 %t1 = icmp slt i64 %x.0, %n192 %t3 = icmp sgt i64 %x.0, %m193 %t4 = and i1 %t1, %t3194 br i1 true, label %bb, label %return195 196return:197 ret void198}199 200; Don't delete this infinite loop because the loop201; 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]], 1211; 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 void217;218entry:219 br i1 true, label %bb, label %bb220 221bb:222 %x.0 = phi i64 [ 0, %entry ], [ 0, %entry ], [ %t0, %bb ]223 %t0 = add i64 %x.0, 1224 %t1 = icmp slt i64 %x.0, %n225 %t3 = icmp sgt i64 %x.0, %m226 %t4 = and i1 %t1, %t3227 br i1 true, label %bb, label %return228 229return:230 ret void231}232 233declare i64 @foo(i64)234; The loop L2 is never executed and is a subloop, with an235; 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]], 42253; 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: test7259; REMARKS: Loop deleted because it never executes260entry:261 br label %L1262 263L1:264 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ]265 br i1 true, label %L1Latch, label %L2266 267L2:268 %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]269 %x.next = add i64 %x, 1270 %y.L2 = call i64 @foo(i64 %x.next)271 %cond = icmp slt i64 %x.next, %n272 br i1 %cond, label %L2, label %L1Latch273 274L1Latch:275 %y = phi i64 [ %y.next, %L1 ], [ %y.L2, %L2 ]276 %y.add = add i64 %y, %n277 %cond2 = icmp eq i64 %y.add, 42278 br i1 %cond2, label %exit, label %L1279 280exit:281 ret i64 %y.add282}283 284 285; Show recursive deletion of loops. Since we start with subloops and progress outward286; to parent loop, we first delete the loop L2. Now loop L1 becomes a non-loop since it's backedge287; 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 void294;295; REMARKS-LABEL: Function: test8296; REMARKS: Loop deleted because it never executes297entry:298 br label %L1299 300L1:301 br i1 true, label %exit, label %L2302 303L2:304 %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]305 %x.next = add i64 %x, 1306 %y.L2 = call i64 @foo(i64 %x.next)307 %cond = icmp slt i64 %x.next, %n308 br i1 %cond, label %L2, label %L1309 310exit:311 ret void312}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 void323;324; REMARKS-LABEL: Function: test9325; REMARKS: Loop deleted because it never executes326entry:327 br label %L1328 329L1:330 br i1 true, label %exit, label %L2331 332L2:333 %x = phi i64 [ 0, %L1 ], [ %x.next, %L2 ]334 %x.next = add i64 %x, 1335 %y.L2 = call i64 @foo(i64 %x.next)336 %cond = icmp slt i64 %x.next, %n337 br i1 %cond, label %L2, label %L3338 339L3:340 %cond2 = icmp slt i64 %y.L2, %n341 br i1 %cond2, label %L3, label %L1342 343exit:344 ret void345}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 not349; 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 void356;357entry:358 br label %L1359 360L1:361 br i1 true, label %exit, label %L2362 363L2:364 %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ]365 %x.next = add i64 %x, 1366 %y.L2 = call i64 @foo(i64 %x.next)367 %cond = icmp slt i64 %x.next, %n368 br i1 %cond, label %L1, label %L3369 370L3:371 %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ]372 %y.L3.next = add i64 %y.L3, 1373 %dummy = call i64 @foo(i64 %y.L3.next)374 %cond2 = icmp slt i64 %y.L3, %n375 br i1 %cond2, label %L3, label %L2376 377exit:378 ret void379}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 is383; deleted.384; In the next iteration, since L2 is never executed and has no subloops, we delete385; 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 void392;393; REMARKS-LABEL: Function: test11394; REMARKS: Loop deleted because it is invariant395; REMARKS-LABEL: Function: test11396; REMARKS: Loop deleted because it never executes397; REMARKS-LABEL: Function: test11398; REMARKS: Loop deleted because it is invariant399entry:400 br label %L1401 402L1:403 br i1 true, label %exit, label %L2404 405L2:406 %x = phi i64 [ 0, %L1 ], [ %x.next, %L3 ]407 %x.next = add i64 %x, 1408 %y.L2 = call i64 @foo(i64 %x.next)409 %cond = icmp slt i64 %x.next, %n410 br i1 %cond, label %L1, label %L3411 412L3:413 %y.L3 = phi i64 [ %y.L2, %L2 ], [ %y.L3.next, %L3 ]414 %y.L3.next = add i64 %y.L3, 1415 %cond2 = icmp slt i64 %y.L3, %n416 br i1 %cond2, label %L3, label %L2417 418exit:419 ret void420}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 42432; CHECK: exit:433; CHECK-NEXT: [[Y_PHI:%.*]] = phi i64 [ poison, [[L1_PREHEADER]] ]434; CHECK-NEXT: ret i64 [[Y_PHI]]435;436; REMARKS-LABEL: Function: test12437; REMARKS: Loop deleted because it never executes438 439entry:440 br i1 true, label %exit1, label %L1441 442exit1:443 ret i64 42444 445L1: ; preds = %L1Latch, %entry446 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ]447 br i1 true, label %L1Latch, label %exit448 449L1Latch: ; preds = %L1450 %y = phi i64 [ %y.next, %L1 ]451 %y.add = add i64 %y, %n452 %cond2 = icmp eq i64 %y.add, 42453 switch i64 %n, label %L1 [454 i64 10, label %exit455 i64 20, label %exit456 ]457 458exit: ; preds = %L1Latch, %L1Latch459 %y.phi = phi i64 [ 10, %L1Latch ], [ 10, %L1Latch ], [ %y.next, %L1]460 ret i64 %y.phi461}462 463; multiple edges to exit block from the same exiting blocks464define 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 42472; CHECK: exit:473; CHECK-NEXT: [[Y_PHI:%.*]] = phi i64 [ poison, [[L1_PREHEADER]] ]474; CHECK-NEXT: ret i64 [[Y_PHI]]475;476; REMARKS-LABEL: Function: test13477; REMARKS: Loop deleted because it never executes478 479entry:480 br i1 true, label %exit1, label %L1481 482exit1:483 ret i64 42484 485L1: ; preds = %L1Latch, %entry486 %y.next = phi i64 [ 0, %entry ], [ %y.add, %L1Latch ]487 br i1 true, label %L1Block, label %exit488 489L1Block: ; preds = %L1490 %y = phi i64 [ %y.next, %L1 ]491 %y.add = add i64 %y, %n492 %cond2 = icmp eq i64 %y.add, 42493 switch i64 %n, label %L1Latch [494 i64 10, label %exit495 i64 20, label %exit496 ]497 498L1Latch:499 switch i64 %n, label %L1 [500 i64 30, label %exit501 i64 40, label %exit502 ]503 504exit: ; preds = %L1Block, %L1, %L1Latch505 %y.phi = phi i64 [ 10, %L1Block ], [ 10, %L1Block ], [ %y.next, %L1 ], [ 30, %L1Latch ], [ 30, %L1Latch ]506 ret i64 %y.phi507}508