Index: include/llvm/Transforms/Utils/Cloning.h =================================================================== --- include/llvm/Transforms/Utils/Cloning.h +++ include/llvm/Transforms/Utils/Cloning.h @@ -47,6 +47,7 @@ class Module; class ProfileSummaryInfo; class ReturnInst; +class DomTreeUpdater; /// Return an exact copy of the specified module std::unique_ptr CloneModule(const Module &M); @@ -262,11 +263,12 @@ /// we replace them with the uses of corresponding Phi inputs. ValueMapping /// is used to map the original instructions from BB to their newly-created /// copies. Returns the split block. -BasicBlock * -DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, - Instruction *StopAt, - ValueToValueMapTy &ValueMapping, - DominatorTree *DT = nullptr); +BasicBlock *DuplicateInstructionsInSplitBetween(BasicBlock *BB, + BasicBlock *PredBB, + Instruction *StopAt, + ValueToValueMapTy &ValueMapping, + DomTreeUpdater &DTU); + } // end namespace llvm #endif // LLVM_TRANSFORMS_UTILS_CLONING_H Index: lib/Transforms/Scalar/CallSiteSplitting.cpp =================================================================== --- lib/Transforms/Scalar/CallSiteSplitting.cpp +++ lib/Transforms/Scalar/CallSiteSplitting.cpp @@ -302,7 +302,7 @@ static void splitCallSite( CallSite CS, const SmallVectorImpl> &Preds, - DominatorTree &DT) { + DomTreeUpdater &DTU) { Instruction *Instr = CS.getInstruction(); BasicBlock *TailBB = Instr->getParent(); bool IsMustTailCall = CS.isMustTailCall(); @@ -327,7 +327,7 @@ BasicBlock *PredBB = Preds[i].first; BasicBlock *SplitBlock = DuplicateInstructionsInSplitBetween( TailBB, PredBB, &*std::next(Instr->getIterator()), ValueToValueMaps[i], - &DT); + DTU); assert(SplitBlock && "Unexpected new basic block split."); Instruction *NewCI = @@ -369,7 +369,7 @@ Splits[i]->getTerminator()->eraseFromParent(); // Erase the tail block once done with musttail patching - TailBB->eraseFromParent(); + DTU.deleteBB(TailBB); return; } @@ -438,21 +438,21 @@ return false; } -static bool tryToSplitOnPHIPredicatedArgument(CallSite CS, DominatorTree &DT) { +using PredsWithCondsTy = SmallVector, 2>; + +static PredsWithCondsTy tryToSplitOnPHIPredicatedArgument(CallSite CS) { if (!isPredicatedOnPHI(CS)) - return false; + return {}; auto Preds = getTwoPredecessors(CS.getInstruction()->getParent()); - SmallVector, 2> PredsCS = { - {Preds[0], {}}, {Preds[1], {}}}; - splitCallSite(CS, PredsCS, DT); - return true; + return {{Preds[0], {}}, {Preds[1], {}}}; } -static bool tryToSplitOnPredicatedArgument(CallSite CS, DominatorTree &DT) { +static PredsWithCondsTy tryToSplitOnPredicatedArgument(CallSite CS, + DominatorTree &DT) { auto Preds = getTwoPredecessors(CS.getInstruction()->getParent()); if (Preds[0] == Preds[1]) - return false; + return {}; // We can stop recording conditions once we reached the immediate dominator // for the block containing the call site. Conditions in predecessors of the @@ -461,7 +461,7 @@ auto *CSDTNode = DT.getNode(CS.getInstruction()->getParent()); BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr; - SmallVector, 2> PredsCS; + PredsWithCondsTy PredsCS; for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) { ConditionsTy Conditions; // Record condition on edge BB(CS) <- Pred @@ -474,7 +474,7 @@ if (all_of(PredsCS, [](const std::pair &P) { return P.second.empty(); })) - return false; + return {}; // Record common conditions starting from StopAt. Those conditions hold for // all paths to CS. Adding them gives the inliner a better chance at inlining @@ -488,21 +488,28 @@ CommonConditions.end()); } - splitCallSite(CS, PredsCS, DT); - return true; + return PredsCS; } static bool tryToSplitCallSite(CallSite CS, TargetTransformInfo &TTI, - DominatorTree &DT) { + DominatorTree &DT, DomTreeUpdater &DTU) { if (!CS.arg_size() || !canSplitCallSite(CS, TTI)) return false; - return tryToSplitOnPredicatedArgument(CS, DT) || - tryToSplitOnPHIPredicatedArgument(CS, DT); + + auto PredsWithConds = tryToSplitOnPredicatedArgument(CS, DT); + if (PredsWithConds.empty()) + PredsWithConds = tryToSplitOnPHIPredicatedArgument(CS); + if (PredsWithConds.empty()) + return false; + + splitCallSite(CS, PredsWithConds, DTU); + return true; } static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT) { bool Changed = false; + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) { BasicBlock &BB = *BI++; auto II = BB.getFirstNonPHIOrDbg()->getIterator(); @@ -525,7 +532,7 @@ // Check if such path is possible before attempting the splitting. bool IsMustTail = CS.isMustTailCall(); - Changed |= tryToSplitCallSite(CS, TTI, DT); + Changed |= tryToSplitCallSite(CS, TTI, DT, DTU); // There're no interesting instructions after this. The call site // itself might have been erased on splitting. Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -2655,28 +2655,16 @@ // Duplicate all instructions before the guard and the guard itself to the // branch where implication is not proved. BasicBlock *GuardedBlock = DuplicateInstructionsInSplitBetween( - BB, PredGuardedBlock, AfterGuard, GuardedMapping); + BB, PredGuardedBlock, AfterGuard, GuardedMapping, *DTU); assert(GuardedBlock && "Could not create the guarded block?"); // Duplicate all instructions before the guard in the unguarded branch. // Since we have successfully duplicated the guarded block and this block // has fewer instructions, we expect it to succeed. BasicBlock *UnguardedBlock = DuplicateInstructionsInSplitBetween( - BB, PredUnguardedBlock, Guard, UnguardedMapping); + BB, PredUnguardedBlock, Guard, UnguardedMapping, *DTU); assert(UnguardedBlock && "Could not create the unguarded block?"); LLVM_DEBUG(dbgs() << "Moved guard " << *Guard << " to block " << GuardedBlock->getName() << "\n"); - // DuplicateInstructionsInSplitBetween inserts a new block "BB.split" between - // PredBB and BB. We need to perform two inserts and one delete for each of - // the above calls to update Dominators. - DTU->applyUpdates( - {// Guarded block split. - {DominatorTree::Delete, PredGuardedBlock, BB}, - {DominatorTree::Insert, PredGuardedBlock, GuardedBlock}, - {DominatorTree::Insert, GuardedBlock, BB}, - // Unguarded block split. - {DominatorTree::Delete, PredUnguardedBlock, BB}, - {DominatorTree::Insert, PredUnguardedBlock, UnguardedBlock}, - {DominatorTree::Insert, UnguardedBlock, BB}}); // Some instructions before the guard may still have uses. For them, we need // to create Phi nodes merging their copies in both guarded and unguarded // branches. Those instructions that have no uses can be just removed. Index: lib/Transforms/Utils/CloneFunction.cpp =================================================================== --- lib/Transforms/Utils/CloneFunction.cpp +++ lib/Transforms/Utils/CloneFunction.cpp @@ -18,11 +18,11 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" -#include "llvm/Transforms/Utils/Local.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DebugInfo.h" #include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/DomTreeUpdater.h" #include "llvm/IR/Function.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/Instructions.h" @@ -32,6 +32,7 @@ #include "llvm/IR/Module.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Cloning.h" +#include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/ValueMapper.h" #include using namespace llvm; @@ -795,11 +796,9 @@ /// Duplicate non-Phi instructions from the beginning of block up to /// StopAt instruction into a split block between BB and its predecessor. -BasicBlock * -llvm::DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, - Instruction *StopAt, - ValueToValueMapTy &ValueMapping, - DominatorTree *DT) { +BasicBlock *llvm::DuplicateInstructionsInSplitBetween( + BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, + ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU) { // We are going to have to map operands from the original BB block to the new // copy of the block 'NewBB'. If there are PHI nodes in BB, evaluate them to // account for entry from PredBB. @@ -807,10 +806,16 @@ for (; PHINode *PN = dyn_cast(BI); ++BI) ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB); - BasicBlock *NewBB = SplitEdge(PredBB, BB, DT); + BasicBlock *NewBB = SplitEdge(PredBB, BB); NewBB->setName(PredBB->getName() + ".split"); Instruction *NewTerm = NewBB->getTerminator(); + // FIXME: SplitEdge does not yet take a DTU, so we include the split edge + // in the update set here. + DTU.applyUpdates({{DominatorTree::Delete, PredBB, BB}, + {DominatorTree::Insert, PredBB, NewBB}, + {DominatorTree::Insert, NewBB, BB}}); + // Clone the non-phi instructions of BB into NewBB, keeping track of the // mapping and using it to remap operands in the cloned instructions. // Stop once we see the terminator too. This covers the case where BB's Index: test/Transforms/CallSiteSplitting/musttail.ll =================================================================== --- test/Transforms/CallSiteSplitting/musttail.ll +++ test/Transforms/CallSiteSplitting/musttail.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -callsite-splitting -S | FileCheck %s +; RUN: opt < %s -callsite-splitting -verify-dom-info -S | FileCheck %s ;CHECK-LABEL: @caller ;CHECK-LABEL: Top.split: Index: unittests/Transforms/Utils/CloningTest.cpp =================================================================== --- unittests/Transforms/Utils/CloningTest.cpp +++ unittests/Transforms/Utils/CloningTest.cpp @@ -14,6 +14,7 @@ #include "llvm/IR/Constant.h" #include "llvm/IR/DIBuilder.h" #include "llvm/IR/DebugInfo.h" +#include "llvm/IR/DomTreeUpdater.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstIterator.h" @@ -225,8 +226,10 @@ Builder2.CreateRetVoid(); ValueToValueMapTy Mapping; + DomTreeUpdater DTU(DomTreeUpdater::UpdateStrategy::Lazy); - auto Split = DuplicateInstructionsInSplitBetween(BB2, BB1, SubInst, Mapping); + auto Split = + DuplicateInstructionsInSplitBetween(BB2, BB1, SubInst, Mapping, DTU); EXPECT_TRUE(Split); EXPECT_EQ(Mapping.size(), 2u); @@ -272,8 +275,10 @@ Builder2.CreateBr(BB2); ValueToValueMapTy Mapping; + DomTreeUpdater DTU(DomTreeUpdater::UpdateStrategy::Lazy); - auto Split = DuplicateInstructionsInSplitBetween(BB2, BB2, BB2->getTerminator(), Mapping); + auto Split = DuplicateInstructionsInSplitBetween( + BB2, BB2, BB2->getTerminator(), Mapping, DTU); EXPECT_TRUE(Split); EXPECT_EQ(Mapping.size(), 3u); @@ -323,8 +328,10 @@ Builder2.CreateBr(BB2); ValueToValueMapTy Mapping; + DomTreeUpdater DTU(DomTreeUpdater::UpdateStrategy::Lazy); - auto Split = DuplicateInstructionsInSplitBetween(BB2, BB2, SubInst, Mapping); + auto Split = + DuplicateInstructionsInSplitBetween(BB2, BB2, SubInst, Mapping, DTU); EXPECT_TRUE(Split); EXPECT_EQ(Mapping.size(), 2u);