diff options
Diffstat (limited to 'llvm')
3 files changed, 1243 insertions, 3 deletions
diff --git a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp index 8c9bd7e72b3..9c9ed2a02e3 100644 --- a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp +++ b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp @@ -1,4 +1,4 @@ -//===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===// +///===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===// // // The LLVM Compiler Infrastructure // @@ -239,6 +239,76 @@ static void rewritePHINodesForExitAndUnswitchedBlocks(BasicBlock &ExitBB, } } +/// Hoist the current loop up to the innermost loop containing a remaining exit. +/// +/// Because we've removed an exit from the loop, we may have changed the set of +/// loops reachable and need to move the current loop up the loop nest or even +/// to an entirely separate nest. +static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader, + DominatorTree &DT, LoopInfo &LI) { + // If the loop is already at the top level, we can't hoist it anywhere. + Loop *OldParentL = L.getParentLoop(); + if (!OldParentL) + return; + + SmallVector<BasicBlock *, 4> Exits; + L.getExitBlocks(Exits); + Loop *NewParentL = nullptr; + for (auto *ExitBB : Exits) + if (Loop *ExitL = LI.getLoopFor(ExitBB)) + if (!NewParentL || NewParentL->contains(ExitL)) + NewParentL = ExitL; + + if (NewParentL == OldParentL) + return; + + // The new parent loop (if different) should always contain the old one. + if (NewParentL) + assert(NewParentL->contains(OldParentL) && + "Can only hoist this loop up the nest!"); + + // The preheader will need to move with the body of this loop. However, + // because it isn't in this loop we also need to update the primary loop map. + assert(OldParentL == LI.getLoopFor(&Preheader) && + "Parent loop of this loop should contain this loop's preheader!"); + LI.changeLoopFor(&Preheader, NewParentL); + + // Remove this loop from its old parent. + OldParentL->removeChildLoop(&L); + + // Add the loop either to the new parent or as a top-level loop. + if (NewParentL) + NewParentL->addChildLoop(&L); + else + LI.addTopLevelLoop(&L); + + // Remove this loops blocks from the old parent and every other loop up the + // nest until reaching the new parent. Also update all of these + // no-longer-containing loops to reflect the nesting change. + for (Loop *OldContainingL = OldParentL; OldContainingL != NewParentL; + OldContainingL = OldContainingL->getParentLoop()) { + llvm::erase_if(OldContainingL->getBlocksVector(), + [&](const BasicBlock *BB) { + return BB == &Preheader || L.contains(BB); + }); + + OldContainingL->getBlocksSet().erase(&Preheader); + for (BasicBlock *BB : L.blocks()) + OldContainingL->getBlocksSet().erase(BB); + + // Because we just hoisted a loop out of this one, we have essentially + // created new exit paths from it. That means we need to form LCSSA PHI + // nodes for values used in the no-longer-nested loop. + formLCSSA(*OldContainingL, DT, &LI, nullptr); + + // We shouldn't need to form dedicated exits because the exit introduced + // here is the (just split by unswitching) preheader. As such, it is + // necessarily dedicated. + assert(OldContainingL->hasDedicatedExits() && + "Unexpected predecessor of hoisted loop preheader!"); + } +} + /// Unswitch a trivial branch if the condition is loop invariant. /// /// This routine should only be called when loop code leading to the branch has @@ -405,6 +475,11 @@ static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT, for (Value *Invariant : Invariants) replaceLoopInvariantUses(L, Invariant, *Replacement); + // If this was full unswitching, we may have changed the nesting relationship + // for this loop so hoist it to its correct parent if needed. + if (FullUnswitch) + hoistLoopToNewParent(L, *NewPH, DT, LI); + ++NumTrivial; ++NumBranches; return true; @@ -632,8 +707,12 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT, DTUpdates.push_back({DT.Insert, OldPH, UnswitchedBB}); } DT.applyUpdates(DTUpdates); - assert(DT.verify(DominatorTree::VerificationLevel::Fast)); + + // We may have changed the nesting relationship for this loop so hoist it to + // its correct parent if needed. + hoistLoopToNewParent(L, *NewPH, DT, LI); + ++NumTrivial; ++NumSwitches; return true; diff --git a/llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll b/llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll index a463cb68a07..bcf9fa81678 100644 --- a/llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll +++ b/llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll @@ -9,6 +9,9 @@ declare void @d() declare void @sink1(i32) declare void @sink2(i32) +declare i1 @cond() +declare i32 @cond.i32() + ; Negative test: we cannot unswitch convergent calls. define void @test_no_unswitch_convergent(i1* %ptr, i1 %cond) { ; CHECK-LABEL: @test_no_unswitch_convergent( @@ -2961,4 +2964,621 @@ loop_exit: ret i32 0 ; CHECK: loop_exit: ; CHECK-NEXT: ret i32 0 -}
\ No newline at end of file +} + +; Unswitch will not actually change the loop nest from: +; A < B < C +define void @hoist_inner_loop0() { +; CHECK-LABEL: define void @hoist_inner_loop0( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: br label %b.header + +b.header: + %v1 = call i1 @cond() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]] +; +; CHECK: [[B_HEADER_SPLIT_US]]: +; CHECK-NEXT: br label %[[C_HEADER_US:.*]] +; +; CHECK: [[C_HEADER_US]]: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %[[B_LATCH_SPLIT_US:.*]] +; +; CHECK: [[B_LATCH_SPLIT_US]]: +; CHECK-NEXT: br label %b.latch +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: br label %c.header + +c.header: + call void @c() + br i1 %v1, label %b.latch, label %c.latch +; CHECK: c.header: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %c.latch + +c.latch: + %v2 = call i1 @cond() + br i1 %v2, label %c.header, label %b.latch +; CHECK: c.latch: +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %c.header, label %[[B_LATCH_SPLIT:.*]] + +b.latch: + %v3 = call i1 @cond() + br i1 %v3, label %b.header, label %a.latch +; CHECK: [[B_LATCH_SPLIT]]: +; CHECK-NEXT: br label %b.latch +; +; CHECK: b.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %b.header, label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Unswitch will transform the loop nest from: +; A < B < C +; into +; A < (B, C) +define void @hoist_inner_loop1(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop1( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + %v1 = call i1 @cond() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]] +; +; CHECK: [[B_HEADER_SPLIT_US]]: +; CHECK-NEXT: br label %[[C_HEADER_US:.*]] +; +; CHECK: [[C_HEADER_US]]: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %[[B_LATCH_US:.*]] +; +; CHECK: [[B_LATCH_US]]: +; CHECK-NEXT: br label %b.latch +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] +; CHECK-NEXT: br label %c.header + +c.header: + call void @c() + br i1 %v1, label %b.latch, label %c.latch +; CHECK: c.header: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %c.latch + +c.latch: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %c.header, label %a.exit.c +; CHECK: c.latch: +; CHECK-NEXT: store i32 %x.a, i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %c.header, label %a.exit.c + +b.latch: + %v3 = call i1 @cond() + br i1 %v3, label %b.header, label %a.exit.b +; CHECK: b.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %b.header, label %a.exit.b + +a.exit.c: + br label %a.latch +; CHECK: a.exit.c +; CHECK-NEXT: br label %a.latch + +a.exit.b: + br label %a.latch +; CHECK: a.exit.b: +; CHECK-NEXT: br label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Unswitch will transform the loop nest from: +; A < B < C +; into +; (A < B), C +define void @hoist_inner_loop2(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop2( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + %v1 = call i1 @cond() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]] +; +; CHECK: [[B_HEADER_SPLIT_US]]: +; CHECK-NEXT: br label %[[C_HEADER_US:.*]] +; +; CHECK: [[C_HEADER_US]]: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %[[B_LATCH_US:.*]] +; +; CHECK: [[B_LATCH_US]]: +; CHECK-NEXT: br label %b.latch +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ] +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] +; CHECK-NEXT: br label %c.header + +c.header: + call void @c() + br i1 %v1, label %b.latch, label %c.latch +; CHECK: c.header: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %c.latch + +c.latch: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %c.header, label %exit +; CHECK: c.latch: +; CHECK-NEXT: store i32 %[[X_A_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %c.header, label %exit + +b.latch: + %v3 = call i1 @cond() + br i1 %v3, label %b.header, label %a.latch +; CHECK: b.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %b.header, label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop. +; Unswitch will transform the loop nest from: +; A < B < C < D +; into +; (A < B), (C < D) +define void @hoist_inner_loop3(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop3( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + %v1 = call i1 @cond() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %[[B_HEADER_SPLIT_US:.*]], label %[[B_HEADER_SPLIT:.*]] +; +; CHECK: [[B_HEADER_SPLIT_US]]: +; CHECK-NEXT: br label %[[C_HEADER_US:.*]] +; +; CHECK: [[C_HEADER_US]]: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %[[B_LATCH_US:.*]] +; +; CHECK: [[B_LATCH_US]]: +; CHECK-NEXT: br label %b.latch +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ] +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] +; CHECK-NEXT: br label %c.header + +c.header: + call void @c() + br i1 %v1, label %b.latch, label %c.body +; CHECK: c.header: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %c.body + +c.body: + %x.c = load i32, i32* %ptr + br label %d.header +; CHECK: c.body: +; CHECK-NEXT: %x.c = load i32, i32* %ptr +; CHECK-NEXT: br label %d.header + +d.header: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + store i32 %x.c, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %d.header, label %c.latch +; CHECK: d.header: +; CHECK-NEXT: store i32 %[[X_A_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %x.c, i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %d.header, label %c.latch + +c.latch: + %v3 = call i1 @cond() + br i1 %v3, label %c.header, label %exit +; CHECK: c.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %c.header, label %exit + +b.latch: + %v4 = call i1 @cond() + br i1 %v4, label %b.header, label %a.latch +; CHECK: b.latch: +; CHECK-NEXT: %v4 = call i1 @cond() +; CHECK-NEXT: br i1 %v4, label %b.header, label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; This test is designed to exercise checking multiple remaining exits from the +; loop being unswitched. +; Unswitch will transform the loop nest from: +; A < B < C < D +; into +; A < B < (C, D) +define void @hoist_inner_loop4() { +; CHECK-LABEL: define void @hoist_inner_loop4( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: br label %b.header + +b.header: + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: br label %c.header + +c.header: + %v1 = call i1 @cond() + br label %d.header +; CHECK: c.header: +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]] +; +; CHECK: [[C_HEADER_SPLIT_US]]: +; CHECK-NEXT: br label %[[D_HEADER_US:.*]] +; +; CHECK: [[D_HEADER_US]]: +; CHECK-NEXT: call void @d() +; CHECK-NEXT: br label %[[C_LATCH_US:.*]] +; +; CHECK: [[C_LATCH_US]]: +; CHECK-NEXT: br label %c.latch +; +; CHECK: [[C_HEADER_SPLIT]]: +; CHECK-NEXT: br label %d.header + +d.header: + call void @d() + br i1 %v1, label %c.latch, label %d.exiting1 +; CHECK: d.header: +; CHECK-NEXT: call void @d() +; CHECK-NEXT: br label %d.exiting1 + +d.exiting1: + %v2 = call i1 @cond() + br i1 %v2, label %d.exiting2, label %a.latch +; CHECK: d.exiting1: +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %d.exiting2, label %a.latch + +d.exiting2: + %v3 = call i1 @cond() + br i1 %v3, label %d.exiting3, label %loopexit.d +; CHECK: d.exiting2: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %d.exiting3, label %loopexit.d + +d.exiting3: + %v4 = call i1 @cond() + br i1 %v4, label %d.latch, label %b.latch +; CHECK: d.exiting3: +; CHECK-NEXT: %v4 = call i1 @cond() +; CHECK-NEXT: br i1 %v4, label %d.latch, label %b.latch + +d.latch: + br label %d.header +; CHECK: d.latch: +; CHECK-NEXT: br label %d.header + +c.latch: + %v5 = call i1 @cond() + br i1 %v5, label %c.header, label %loopexit.c +; CHECK: c.latch: +; CHECK-NEXT: %v5 = call i1 @cond() +; CHECK-NEXT: br i1 %v5, label %c.header, label %loopexit.c + +b.latch: + br label %b.header +; CHECK: b.latch: +; CHECK-NEXT: br label %b.header + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +loopexit.d: + br label %exit +; CHECK: loopexit.d: +; CHECK-NEXT: br label %exit + +loopexit.c: + br label %exit +; CHECK: loopexit.c: +; CHECK-NEXT: br label %exit + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Unswitch will transform the loop nest from: +; A < B < C < D +; into +; A < ((B < C), D) +define void @hoist_inner_loop5(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop5( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: br label %c.header + +c.header: + %x.c = load i32, i32* %ptr + %v1 = call i1 @cond() + br label %d.header +; CHECK: c.header: +; CHECK-NEXT: %x.c = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %[[C_HEADER_SPLIT_US:.*]], label %[[C_HEADER_SPLIT:.*]] +; +; CHECK: [[C_HEADER_SPLIT_US]]: +; CHECK-NEXT: br label %[[D_HEADER_US:.*]] +; +; CHECK: [[D_HEADER_US]]: +; CHECK-NEXT: call void @d() +; CHECK-NEXT: br label %[[C_LATCH_US:.*]] +; +; CHECK: [[C_LATCH_US]]: +; CHECK-NEXT: br label %c.latch +; +; CHECK: [[C_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ] +; CHECK-NEXT: %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ] +; CHECK-NEXT: br label %d.header + +d.header: + call void @d() + br i1 %v1, label %c.latch, label %d.latch +; CHECK: d.header: +; CHECK-NEXT: call void @d() +; CHECK-NEXT: br label %d.latch + +d.latch: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + store i32 %x.c, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %d.header, label %a.latch +; CHECK: d.latch: +; CHECK-NEXT: store i32 %x.a, i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %[[X_C_LCSSA]], i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %d.header, label %a.latch + +c.latch: + %v3 = call i1 @cond() + br i1 %v3, label %c.header, label %b.latch +; CHECK: c.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %c.header, label %b.latch + +b.latch: + br label %b.header +; CHECK: b.latch: +; CHECK-NEXT: br label %b.header + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +define void @hoist_inner_loop_switch(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop_switch( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + %v1 = call i32 @cond.i32() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i32 @cond.i32() +; CHECK-NEXT: switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [ +; CHECK-NEXT: i32 1, label %[[B_HEADER_SPLIT_US:.*]] +; CHECK-NEXT: i32 2, label %[[B_HEADER_SPLIT_US]] +; CHECK-NEXT: i32 3, label %[[B_HEADER_SPLIT_US]] +; CHECK-NEXT: ] +; +; CHECK: [[B_HEADER_SPLIT_US]]: +; CHECK-NEXT: br label %[[C_HEADER_US:.*]] +; +; CHECK: [[C_HEADER_US]]: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %[[B_LATCH_US:.*]] +; +; CHECK: [[B_LATCH_US]]: +; CHECK-NEXT: br label %b.latch +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ] +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] +; CHECK-NEXT: br label %c.header + +c.header: + call void @c() + switch i32 %v1, label %c.latch [ + i32 1, label %b.latch + i32 2, label %b.latch + i32 3, label %b.latch + ] +; CHECK: c.header: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %c.latch + +c.latch: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %c.header, label %exit +; CHECK: c.latch: +; CHECK-NEXT: store i32 %[[X_A_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %c.header, label %exit + +b.latch: + %v3 = call i1 @cond() + br i1 %v3, label %b.header, label %a.latch +; CHECK: b.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %b.header, label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} diff --git a/llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll b/llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll index 572d2b6cf83..6b36a8a5cde 100644 --- a/llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll +++ b/llvm/test/Transforms/SimpleLoopUnswitch/trivial-unswitch.ll @@ -2,6 +2,9 @@ declare void @some_func() noreturn +declare i1 @cond() +declare i32 @cond.i32() + ; This test contains two trivial unswitch condition in one loop. ; LoopUnswitch pass should be able to unswitch the second one ; after unswitching the first one. @@ -619,3 +622,541 @@ loop_exit: ; CHECK-NEXT: %[[LCSSA_SPLIT:.*]] = phi i32 [ %x, %entry ], [ %[[LCSSA]], %loop_exit ] ; CHECK-NEXT: ret i32 %[[LCSSA_SPLIT]] } + +; Unswitch will not actually change the loop nest from: +; A < B < C +define void @hoist_inner_loop0() { +; CHECK-LABEL: define void @hoist_inner_loop0( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: br label %b.header + +b.header: + %v1 = call i1 @cond() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %[[B_LATCH_SPLIT:.*]], label %[[B_HEADER_SPLIT:.*]] +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: br label %c.header + +c.header: + br i1 %v1, label %b.latch, label %c.latch +; CHECK: c.header: +; CHECK-NEXT: br label %c.latch + +c.latch: + %v2 = call i1 @cond() + br i1 %v2, label %c.header, label %b.latch +; CHECK: c.latch: +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %c.header, label %b.latch + +b.latch: + %v3 = call i1 @cond() + br i1 %v3, label %b.header, label %a.latch +; CHECK: b.latch: +; CHECK-NEXT: br label %[[B_LATCH_SPLIT]] +; +; CHECK: [[B_LATCH_SPLIT]]: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %b.header, label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Unswitch will transform the loop nest from: +; A < B < C +; into +; A < (B, C) +define void @hoist_inner_loop1(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop1( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + %v1 = call i1 @cond() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]] +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] +; CHECK-NEXT: br label %c.header + +c.header: + br i1 %v1, label %b.latch, label %c.latch +; CHECK: c.header: +; CHECK-NEXT: br label %c.latch + +c.latch: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %c.header, label %a.exit.c +; CHECK: c.latch: +; CHECK-NEXT: store i32 %x.a, i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %c.header, label %a.exit.c + +b.latch: + %v3 = call i1 @cond() + br i1 %v3, label %b.header, label %a.exit.b +; CHECK: b.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %b.header, label %a.exit.b + +a.exit.c: + br label %a.latch +; CHECK: a.exit.c +; CHECK-NEXT: br label %a.latch + +a.exit.b: + br label %a.latch +; CHECK: a.exit.b: +; CHECK-NEXT: br label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Unswitch will transform the loop nest from: +; A < B < C +; into +; (A < B), C +define void @hoist_inner_loop2(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop2( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + %v1 = call i1 @cond() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]] +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ] +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] +; CHECK-NEXT: br label %c.header + +c.header: + br i1 %v1, label %b.latch, label %c.latch +; CHECK: c.header: +; CHECK-NEXT: br label %c.latch + +c.latch: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %c.header, label %exit +; CHECK: c.latch: +; CHECK-NEXT: store i32 %[[X_A_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %c.header, label %exit + +b.latch: + %v3 = call i1 @cond() + br i1 %v3, label %b.header, label %a.latch +; CHECK: b.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %b.header, label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Same as @hoist_inner_loop2 but with a nested loop inside the hoisted loop. +; Unswitch will transform the loop nest from: +; A < B < C < D +; into +; (A < B), (C < D) +define void @hoist_inner_loop3(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop3( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + %v1 = call i1 @cond() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %b.latch, label %[[B_HEADER_SPLIT:.*]] +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ] +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] +; CHECK-NEXT: br label %c.header + +c.header: + br i1 %v1, label %b.latch, label %c.body +; CHECK: c.header: +; CHECK-NEXT: br label %c.body + +c.body: + %x.c = load i32, i32* %ptr + br label %d.header +; CHECK: c.body: +; CHECK-NEXT: %x.c = load i32, i32* %ptr +; CHECK-NEXT: br label %d.header + +d.header: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + store i32 %x.c, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %d.header, label %c.latch +; CHECK: d.header: +; CHECK-NEXT: store i32 %[[X_A_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %x.c, i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %d.header, label %c.latch + +c.latch: + %v3 = call i1 @cond() + br i1 %v3, label %c.header, label %exit +; CHECK: c.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %c.header, label %exit + +b.latch: + %v4 = call i1 @cond() + br i1 %v4, label %b.header, label %a.latch +; CHECK: b.latch: +; CHECK-NEXT: %v4 = call i1 @cond() +; CHECK-NEXT: br i1 %v4, label %b.header, label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; This test is designed to exercise checking multiple remaining exits from the +; loop being unswitched. +; Unswitch will transform the loop nest from: +; A < B < C < D +; into +; A < B < (C, D) +define void @hoist_inner_loop4() { +; CHECK-LABEL: define void @hoist_inner_loop4( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: br label %b.header + +b.header: + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: br label %c.header + +c.header: + %v1 = call i1 @cond() + br label %d.header +; CHECK: c.header: +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %[[C_HEADER_SPLIT:.*]], label %c.latch +; +; CHECK: [[C_HEADER_SPLIT]]: +; CHECK-NEXT: br label %d.header + +d.header: + br i1 %v1, label %d.exiting1, label %c.latch +; CHECK: d.header: +; CHECK-NEXT: br label %d.exiting1 + +d.exiting1: + %v2 = call i1 @cond() + br i1 %v2, label %d.exiting2, label %a.latch +; CHECK: d.exiting1: +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %d.exiting2, label %a.latch + +d.exiting2: + %v3 = call i1 @cond() + br i1 %v3, label %d.exiting3, label %loopexit.d +; CHECK: d.exiting2: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %d.exiting3, label %loopexit.d + +d.exiting3: + %v4 = call i1 @cond() + br i1 %v4, label %d.latch, label %b.latch +; CHECK: d.exiting3: +; CHECK-NEXT: %v4 = call i1 @cond() +; CHECK-NEXT: br i1 %v4, label %d.latch, label %b.latch + +d.latch: + br label %d.header +; CHECK: d.latch: +; CHECK-NEXT: br label %d.header + +c.latch: + %v5 = call i1 @cond() + br i1 %v5, label %c.header, label %loopexit.c +; CHECK: c.latch: +; CHECK-NEXT: %v5 = call i1 @cond() +; CHECK-NEXT: br i1 %v5, label %c.header, label %loopexit.c + +b.latch: + br label %b.header +; CHECK: b.latch: +; CHECK-NEXT: br label %b.header + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +loopexit.d: + br label %exit +; CHECK: loopexit.d: +; CHECK-NEXT: br label %exit + +loopexit.c: + br label %exit +; CHECK: loopexit.c: +; CHECK-NEXT: br label %exit + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Unswitch will transform the loop nest from: +; A < B < C < D +; into +; A < ((B < C), D) +define void @hoist_inner_loop5(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop5( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: br label %c.header + +c.header: + %x.c = load i32, i32* %ptr + %v1 = call i1 @cond() + br label %d.header +; CHECK: c.header: +; CHECK-NEXT: %x.c = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i1 @cond() +; CHECK-NEXT: br i1 %v1, label %c.latch, label %[[C_HEADER_SPLIT:.*]] +; +; CHECK: [[C_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %c.header ] +; CHECK-NEXT: %[[X_C_LCSSA:.*]] = phi i32 [ %x.c, %c.header ] +; CHECK-NEXT: br label %d.header + +d.header: + br i1 %v1, label %c.latch, label %d.latch +; CHECK: d.header: +; CHECK-NEXT: br label %d.latch + +d.latch: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + store i32 %x.c, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %d.header, label %a.latch +; CHECK: d.latch: +; CHECK-NEXT: store i32 %x.a, i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %[[X_C_LCSSA]], i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %d.header, label %a.latch + +c.latch: + %v3 = call i1 @cond() + br i1 %v3, label %c.header, label %b.latch +; CHECK: c.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %c.header, label %b.latch + +b.latch: + br label %b.header +; CHECK: b.latch: +; CHECK-NEXT: br label %b.header + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Same as `@hoist_inner_loop2` but using a switch. +; Unswitch will transform the loop nest from: +; A < B < C +; into +; (A < B), C +define void @hoist_inner_loop_switch(i32* %ptr) { +; CHECK-LABEL: define void @hoist_inner_loop_switch( +entry: + br label %a.header +; CHECK: entry: +; CHECK-NEXT: br label %a.header + +a.header: + %x.a = load i32, i32* %ptr + br label %b.header +; CHECK: a.header: +; CHECK-NEXT: %x.a = load i32, i32* %ptr +; CHECK-NEXT: br label %b.header + +b.header: + %x.b = load i32, i32* %ptr + %v1 = call i32 @cond.i32() + br label %c.header +; CHECK: b.header: +; CHECK-NEXT: %x.b = load i32, i32* %ptr +; CHECK-NEXT: %v1 = call i32 @cond.i32() +; CHECK-NEXT: switch i32 %v1, label %[[B_HEADER_SPLIT:.*]] [ +; CHECK-NEXT: i32 1, label %b.latch +; CHECK-NEXT: i32 2, label %b.latch +; CHECK-NEXT: i32 3, label %b.latch +; CHECK-NEXT: ] +; +; CHECK: [[B_HEADER_SPLIT]]: +; CHECK-NEXT: %[[X_A_LCSSA:.*]] = phi i32 [ %x.a, %b.header ] +; CHECK-NEXT: %[[X_B_LCSSA:.*]] = phi i32 [ %x.b, %b.header ] +; CHECK-NEXT: br label %c.header + +c.header: + switch i32 %v1, label %c.latch [ + i32 1, label %b.latch + i32 2, label %b.latch + i32 3, label %b.latch + ] +; CHECK: c.header: +; CHECK-NEXT: br label %c.latch + +c.latch: + ; Use values from other loops to check LCSSA form. + store i32 %x.a, i32* %ptr + store i32 %x.b, i32* %ptr + %v2 = call i1 @cond() + br i1 %v2, label %c.header, label %exit +; CHECK: c.latch: +; CHECK-NEXT: store i32 %[[X_A_LCSSA]], i32* %ptr +; CHECK-NEXT: store i32 %[[X_B_LCSSA]], i32* %ptr +; CHECK-NEXT: %v2 = call i1 @cond() +; CHECK-NEXT: br i1 %v2, label %c.header, label %exit + +b.latch: + %v3 = call i1 @cond() + br i1 %v3, label %b.header, label %a.latch +; CHECK: b.latch: +; CHECK-NEXT: %v3 = call i1 @cond() +; CHECK-NEXT: br i1 %v3, label %b.header, label %a.latch + +a.latch: + br label %a.header +; CHECK: a.latch: +; CHECK-NEXT: br label %a.header + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} |
