diff --git a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h --- a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -179,6 +179,13 @@ } }; +/// When a loop exit edge is split, LCSSA form may require new PHIs in the new +/// exit block. This function inserts the new PHIs, as needed. Preds is a list +/// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is +/// the old loop exit, now the successor of SplitBB. +void createPHIsForSplitLoopExit(ArrayRef Preds, + BasicBlock *SplitBB, BasicBlock *DestBB); + /// If this edge is a critical edge, insert a new node to split the critical /// edge. This will update the analyses passed in through the option struct. /// This returns the new block if the edge was split, null otherwise. @@ -200,6 +207,13 @@ CriticalEdgeSplittingOptions(), const Twine &BBName = ""); +/// If it is known that an edge is critical, SplitKnownCriticalEdge can be +/// called directly, rather than calling SplitCriticalEdge first. +BasicBlock *SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, + const CriticalEdgeSplittingOptions &Options = + CriticalEdgeSplittingOptions(), + const Twine &BBName = ""); + inline BasicBlock * SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, const CriticalEdgeSplittingOptions &Options = @@ -253,6 +267,23 @@ MemorySSAUpdater *MSSAU = nullptr, const Twine &BBName = ""); +/// Sets the unwind edge of an instruction to a particular successor. +void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ); + +/// Replaces all uses of OldPred with the NewPred block in all PHINodes in a +/// block. +void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, + BasicBlock *NewPred, PHINode *Until = nullptr); + +/// Split the edge connect the specficed blocks in the case that \p Succ is an +/// Exception Handling Block +BasicBlock *ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, + LandingPadInst *OriginalPad = nullptr, + PHINode *LandingPadReplacement = nullptr, + const CriticalEdgeSplittingOptions &Options = + CriticalEdgeSplittingOptions(), + const Twine &BBName = ""); + /// Split the specified block at the specified instruction. /// /// If \p Before is true, splitBlockBefore handles the block diff --git a/llvm/lib/Transforms/Coroutines/CoroFrame.cpp b/llvm/lib/Transforms/Coroutines/CoroFrame.cpp --- a/llvm/lib/Transforms/Coroutines/CoroFrame.cpp +++ b/llvm/lib/Transforms/Coroutines/CoroFrame.cpp @@ -1358,77 +1358,6 @@ return FramePtr; } -// Sets the unwind edge of an instruction to a particular successor. -static void setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) { - if (auto *II = dyn_cast(TI)) - II->setUnwindDest(Succ); - else if (auto *CS = dyn_cast(TI)) - CS->setUnwindDest(Succ); - else if (auto *CR = dyn_cast(TI)) - CR->setUnwindDest(Succ); - else - llvm_unreachable("unexpected terminator instruction"); -} - -// Replaces all uses of OldPred with the NewPred block in all PHINodes in a -// block. -static void updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, - BasicBlock *NewPred, PHINode *Until = nullptr) { - unsigned BBIdx = 0; - for (BasicBlock::iterator I = DestBB->begin(); isa(I); ++I) { - PHINode *PN = cast(I); - - // We manually update the LandingPadReplacement PHINode and it is the last - // PHI Node. So, if we find it, we are done. - if (Until == PN) - break; - - // Reuse the previous value of BBIdx if it lines up. In cases where we - // have multiple phi nodes with *lots* of predecessors, this is a speed - // win because we don't have to scan the PHI looking for TIBB. This - // happens because the BB list of PHI nodes are usually in the same - // order. - if (PN->getIncomingBlock(BBIdx) != OldPred) - BBIdx = PN->getBasicBlockIndex(OldPred); - - assert(BBIdx != (unsigned)-1 && "Invalid PHI Index!"); - PN->setIncomingBlock(BBIdx, NewPred); - } -} - -// Uses SplitEdge unless the successor block is an EHPad, in which case do EH -// specific handling. -static BasicBlock *ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, - LandingPadInst *OriginalPad, - PHINode *LandingPadReplacement) { - auto *PadInst = Succ->getFirstNonPHI(); - if (!LandingPadReplacement && !PadInst->isEHPad()) - return SplitEdge(BB, Succ); - - auto *NewBB = BasicBlock::Create(BB->getContext(), "", BB->getParent(), Succ); - setUnwindEdgeTo(BB->getTerminator(), NewBB); - updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement); - - if (LandingPadReplacement) { - auto *NewLP = OriginalPad->clone(); - auto *Terminator = BranchInst::Create(Succ, NewBB); - NewLP->insertBefore(Terminator); - LandingPadReplacement->addIncoming(NewLP, NewBB); - return NewBB; - } - Value *ParentPad = nullptr; - if (auto *FuncletPad = dyn_cast(PadInst)) - ParentPad = FuncletPad->getParentPad(); - else if (auto *CatchSwitch = dyn_cast(PadInst)) - ParentPad = CatchSwitch->getParentPad(); - else - llvm_unreachable("handling for other EHPads not implemented yet"); - - auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, "", NewBB); - CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB); - return NewBB; -} - // Moves the values in the PHIs in SuccBB that correspong to PredBB into a new // PHI in InsertedBB. static void movePHIValuesToInsertedBlock(BasicBlock *SuccBB, diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -501,13 +501,20 @@ const Twine &BBName) { unsigned SuccNum = GetSuccessorNumber(BB, Succ); - // If this is a critical edge, let SplitCriticalEdge do it. Instruction *LatchTerm = BB->getTerminator(); - if (SplitCriticalEdge( - LatchTerm, SuccNum, - CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA(), - BBName)) - return LatchTerm->getSuccessor(SuccNum); + + CriticalEdgeSplittingOptions Options = + CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA(); + + if ((isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges))) { + // If it is a critical edge, and the succesor is an exception block, handle + // the split edge logic in this specific function + if (Succ->isEHPad()) + return ehAwareSplitEdge(BB, Succ, nullptr, nullptr, Options, BBName); + + // If this is a critical edge, let SplitKnownCriticalEdge do it. + return SplitKnownCriticalEdge(LatchTerm, SuccNum, Options, BBName); + } // If the edge isn't critical, then BB has a single successor or Succ has a // single pred. Split the block. @@ -527,6 +534,218 @@ return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU, BBName); } +void llvm::setUnwindEdgeTo(Instruction *TI, BasicBlock *Succ) { + if (auto *II = dyn_cast(TI)) + II->setUnwindDest(Succ); + else if (auto *CS = dyn_cast(TI)) + CS->setUnwindDest(Succ); + else if (auto *CR = dyn_cast(TI)) + CR->setUnwindDest(Succ); + else + llvm_unreachable("unexpected terminator instruction"); +} + +void llvm::updatePhiNodes(BasicBlock *DestBB, BasicBlock *OldPred, + BasicBlock *NewPred, PHINode *Until) { + int BBIdx = 0; + for (PHINode &PN : DestBB->phis()) { + // We manually update the LandingPadReplacement PHINode and it is the last + // PHI Node. So, if we find it, we are done. + if (Until == &PN) + break; + + // Reuse the previous value of BBIdx if it lines up. In cases where we + // have multiple phi nodes with *lots* of predecessors, this is a speed + // win because we don't have to scan the PHI looking for TIBB. This + // happens because the BB list of PHI nodes are usually in the same + // order. + if (PN.getIncomingBlock(BBIdx) != OldPred) + BBIdx = PN.getBasicBlockIndex(OldPred); + + assert(BBIdx != -1 && "Invalid PHI Index!"); + PN.setIncomingBlock(BBIdx, NewPred); + } +} + +BasicBlock *llvm::ehAwareSplitEdge(BasicBlock *BB, BasicBlock *Succ, + LandingPadInst *OriginalPad, + PHINode *LandingPadReplacement, + const CriticalEdgeSplittingOptions &Options, + const Twine &BBName) { + + auto *PadInst = Succ->getFirstNonPHI(); + if (!LandingPadReplacement && !PadInst->isEHPad()) + return SplitEdge(BB, Succ, Options.DT, Options.LI, Options.MSSAU, BBName); + + auto *LI = Options.LI; + SmallVector LoopPreds; + // Check if extra modifications will be required to preserve loop-simplify + // form after splitting. If it would require splitting blocks with IndirectBr + // terminators, bail out if preserving loop-simplify form is requested. + if (Options.PreserveLoopSimplify && LI) { + if (Loop *BBLoop = LI->getLoopFor(BB)) { + + // The only way that we can break LoopSimplify form by splitting a + // critical edge is when there exists some edge from BBLoop to Succ *and* + // the only edge into Succ from outside of BBLoop is that of NewBB after + // the split. If the first isn't true, then LoopSimplify still holds, + // NewBB is the new exit block and it has no non-loop predecessors. If the + // second isn't true, then Succ was not in LoopSimplify form prior to + // the split as it had a non-loop predecessor. In both of these cases, + // the predecessor must be directly in BBLoop, not in a subloop, or again + // LoopSimplify doesn't hold. + for (BasicBlock *P : predecessors(Succ)) { + if (P == BB) + continue; // The new block is known. + if (LI->getLoopFor(P) != BBLoop) { + // Loop is not in LoopSimplify form, no need to re simplify after + // splitting edge. + LoopPreds.clear(); + break; + } + LoopPreds.push_back(P); + } + // Loop-simplify form can be preserved, if we can split all in-loop + // predecessors. + if (any_of(LoopPreds, [](BasicBlock *Pred) { + return isa(Pred->getTerminator()); + })) { + return nullptr; + } + } + } + + auto *NewBB = + BasicBlock::Create(BB->getContext(), BBName, BB->getParent(), Succ); + setUnwindEdgeTo(BB->getTerminator(), NewBB); + updatePhiNodes(Succ, BB, NewBB, LandingPadReplacement); + + if (LandingPadReplacement) { + auto *NewLP = OriginalPad->clone(); + auto *Terminator = BranchInst::Create(Succ, NewBB); + NewLP->insertBefore(Terminator); + LandingPadReplacement->addIncoming(NewLP, NewBB); + } else { + Value *ParentPad = nullptr; + if (auto *FuncletPad = dyn_cast(PadInst)) + ParentPad = FuncletPad->getParentPad(); + else if (auto *CatchSwitch = dyn_cast(PadInst)) + ParentPad = CatchSwitch->getParentPad(); + else if (auto *CleanupPad = dyn_cast(PadInst)) + ParentPad = CleanupPad->getParentPad(); + else if (auto *LandingPad = dyn_cast(PadInst)) + ParentPad = LandingPad->getParent(); + else + llvm_unreachable("handling for other EHPads not implemented yet"); + + auto *NewCleanupPad = CleanupPadInst::Create(ParentPad, {}, BBName, NewBB); + CleanupReturnInst::Create(NewCleanupPad, Succ, NewBB); + } + + auto *DT = Options.DT; + auto *MSSAU = Options.MSSAU; + if (!DT && !LI) + return NewBB; + + if (DT) { + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); + SmallVector Updates; + + Updates.push_back({DominatorTree::Insert, BB, NewBB}); + Updates.push_back({DominatorTree::Insert, NewBB, Succ}); + Updates.push_back({DominatorTree::Delete, BB, Succ}); + + DTU.applyUpdates(Updates); + DTU.flush(); + + if (MSSAU) { + MSSAU->applyUpdates(Updates, *DT); + if (VerifyMemorySSA) + MSSAU->getMemorySSA()->verifyMemorySSA(); + } + } + + if (LI) { + if (Loop *BBLoop = LI->getLoopFor(BB)) { + // If one or the other blocks were not in a loop, the new block is not + // either, and thus LI doesn't need to be updated. + if (Loop *SuccLoop = LI->getLoopFor(Succ)) { + if (BBLoop == SuccLoop) { + // Both in the same loop, the NewBB joins loop. + SuccLoop->addBasicBlockToLoop(NewBB, *LI); + } else if (BBLoop->contains(SuccLoop)) { + // Edge from an outer loop to an inner loop. Add to the outer loop. + BBLoop->addBasicBlockToLoop(NewBB, *LI); + } else if (SuccLoop->contains(BBLoop)) { + // Edge from an inner loop to an outer loop. Add to the outer loop. + SuccLoop->addBasicBlockToLoop(NewBB, *LI); + } else { + // Edge from two loops with no containment relation. Because these + // are natural loops, we know that the destination block must be the + // header of its loop (adding a branch into a loop elsewhere would + // create an irreducible loop). + assert(SuccLoop->getHeader() == Succ && + "Should not create irreducible loops!"); + if (Loop *P = SuccLoop->getParentLoop()) + P->addBasicBlockToLoop(NewBB, *LI); + } + } + + // If BB is in a loop and Succ is outside of that loop, we may need to + // update LoopSimplify form and LCSSA form. + if (!BBLoop->contains(Succ)) { + assert(!BBLoop->contains(NewBB) && + "Split point for loop exit is contained in loop!"); + + // Update LCSSA form in the newly created exit block. + if (Options.PreserveLCSSA) { + createPHIsForSplitLoopExit(BB, NewBB, Succ); + } + + if (!LoopPreds.empty()) { + BasicBlock *NewExitBB = SplitBlockPredecessors( + Succ, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA); + if (Options.PreserveLCSSA) + createPHIsForSplitLoopExit(LoopPreds, NewExitBB, Succ); + } + } + } + } + + return NewBB; +} + +void llvm::createPHIsForSplitLoopExit(ArrayRef Preds, + BasicBlock *SplitBB, BasicBlock *DestBB) { + // SplitBB shouldn't have anything non-trivial in it yet. + assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || + SplitBB->isLandingPad()) && + "SplitBB has non-PHI nodes!"); + + // For each PHI in the destination block. + for (PHINode &PN : DestBB->phis()) { + int Idx = PN.getBasicBlockIndex(SplitBB); + assert(Idx >= 0 && "Invalid Block Index"); + Value *V = PN.getIncomingValue(Idx); + + // If the input is a PHI which already satisfies LCSSA, don't create + // a new one. + if (const PHINode *VP = dyn_cast(V)) + if (VP->getParent() == SplitBB) + continue; + + // Otherwise a new PHI is needed. Create one and populate it. + PHINode *NewPN = PHINode::Create( + PN.getType(), Preds.size(), "split", + SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator()); + for (BasicBlock *BB : Preds) + NewPN->addIncoming(V, BB); + + // Update the original PHI. + PN.setIncomingValue(Idx, NewPN); + } +} + unsigned llvm::SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options) { diff --git a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp --- a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -100,46 +100,19 @@ // Implementation of the external critical edge manipulation functions //===----------------------------------------------------------------------===// -/// When a loop exit edge is split, LCSSA form may require new PHIs in the new -/// exit block. This function inserts the new PHIs, as needed. Preds is a list -/// of preds inside the loop, SplitBB is the new loop exit block, and DestBB is -/// the old loop exit, now the successor of SplitBB. -static void createPHIsForSplitLoopExit(ArrayRef Preds, - BasicBlock *SplitBB, - BasicBlock *DestBB) { - // SplitBB shouldn't have anything non-trivial in it yet. - assert((SplitBB->getFirstNonPHI() == SplitBB->getTerminator() || - SplitBB->isLandingPad()) && "SplitBB has non-PHI nodes!"); - - // For each PHI in the destination block. - for (PHINode &PN : DestBB->phis()) { - unsigned Idx = PN.getBasicBlockIndex(SplitBB); - Value *V = PN.getIncomingValue(Idx); - - // If the input is a PHI which already satisfies LCSSA, don't create - // a new one. - if (const PHINode *VP = dyn_cast(V)) - if (VP->getParent() == SplitBB) - continue; - - // Otherwise a new PHI is needed. Create one and populate it. - PHINode *NewPN = PHINode::Create( - PN.getType(), Preds.size(), "split", - SplitBB->isLandingPad() ? &SplitBB->front() : SplitBB->getTerminator()); - for (unsigned i = 0, e = Preds.size(); i != e; ++i) - NewPN->addIncoming(V, Preds[i]); - - // Update the original PHI. - PN.setIncomingValue(Idx, NewPN); - } -} - BasicBlock *llvm::SplitCriticalEdge(Instruction *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options, const Twine &BBName) { if (!isCriticalEdge(TI, SuccNum, Options.MergeIdenticalEdges)) return nullptr; + return SplitKnownCriticalEdge(TI, SuccNum, Options, BBName); +} + +BasicBlock * +llvm::SplitKnownCriticalEdge(Instruction *TI, unsigned SuccNum, + const CriticalEdgeSplittingOptions &Options, + const Twine &BBName) { assert(!isa(TI) && "Cannot split critical edge from IndirectBrInst"); diff --git a/llvm/unittests/Transforms/Utils/BasicBlockUtilsTest.cpp b/llvm/unittests/Transforms/Utils/BasicBlockUtilsTest.cpp --- a/llvm/unittests/Transforms/Utils/BasicBlockUtilsTest.cpp +++ b/llvm/unittests/Transforms/Utils/BasicBlockUtilsTest.cpp @@ -11,6 +11,7 @@ #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BranchProbabilityInfo.h" +#include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSAUpdater.h" @@ -21,6 +22,7 @@ #include "llvm/IR/Dominators.h" #include "llvm/IR/LLVMContext.h" #include "llvm/Support/SourceMgr.h" +#include "llvm/Transforms/Utils/BreakCriticalEdges.h" #include "gtest/gtest.h" using namespace llvm; @@ -220,6 +222,92 @@ EXPECT_TRUE(BBFlag); } +TEST(BasicBlockUtils, SplitEdge_ex4) { + LLVMContext C; + std::unique_ptr M = parseIR( + C, "define void @bar(i32 %cond) personality i8 0 {\n" + "entry:\n" + " switch i32 %cond, label %exit [\n" + " i32 -1, label %continue\n" + " i32 0, label %continue\n" + " i32 1, label %continue_alt\n" + " i32 2, label %continue_alt\n" + " ]\n" + "exit:\n" + " ret void\n" + "continue:\n" + " invoke void @sink() to label %normal unwind label %exception\n" + "continue_alt:\n" + " invoke void @sink_alt() to label %normal unwind label %exception\n" + "exception:\n" + " %cleanup = landingpad i8 cleanup\n" + " br label %trivial-eh-handler\n" + "trivial-eh-handler:\n" + " call void @sideeffect(i32 1)\n" + " br label %normal\n" + "normal:\n" + " call void @sideeffect(i32 0)\n" + " ret void\n" + "}\n" + "\n" + "declare void @sideeffect(i32)\n" + "declare void @sink() cold\n" + "declare void @sink_alt() cold\n"); + + Function *F = M->getFunction("bar"); + + DominatorTree DT(*F); + + LoopInfo LI(DT); + + TargetLibraryInfoImpl TLII; + TargetLibraryInfo TLI(TLII); + + AAResults AA(TLI); + + MemorySSA MSSA(*F, &AA, &DT); + MemorySSAUpdater MSSAU(&MSSA); + + BasicBlock *SrcBlock; + BasicBlock *DestBlock; + + SrcBlock = getBasicBlockByName(*F, "continue"); + DestBlock = getBasicBlockByName(*F, "exception"); + + unsigned SuccNum = GetSuccessorNumber(SrcBlock, DestBlock); + Instruction *LatchTerm = SrcBlock->getTerminator(); + + const CriticalEdgeSplittingOptions Options = + CriticalEdgeSplittingOptions(&DT, &LI, &MSSAU); + + // Check that the following edge is both critical and the destination block is + // an exception block. These must be handled differently by SplitEdge + bool CriticalEdge = + isCriticalEdge(LatchTerm, SuccNum, Options.MergeIdenticalEdges); + EXPECT_TRUE(CriticalEdge); + + bool Ehpad = DestBlock->isEHPad(); + EXPECT_TRUE(Ehpad); + + BasicBlock *NewBB = SplitEdge(SrcBlock, DestBlock, &DT, &LI, &MSSAU, ""); + + MSSA.verifyMemorySSA(); + EXPECT_TRUE(DT.verify()); + EXPECT_NE(NewBB, nullptr); + EXPECT_EQ(NewBB->getSinglePredecessor(), SrcBlock); + EXPECT_EQ(NewBB, SrcBlock->getTerminator()->getSuccessor(SuccNum)); + EXPECT_EQ(NewBB->getParent(), F); + + bool BBFlag = false; + for (BasicBlock &BB : *F) { + if (BB.getName() == NewBB->getName()) { + BBFlag = true; + break; + } + } + EXPECT_TRUE(BBFlag); +} + TEST(BasicBlockUtils, splitBasicBlockBefore_ex1) { LLVMContext C; std::unique_ptr M = parseIR(C, "define void @foo() {\n"