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,25 @@ return false; } -static bool tryToSplitOnPHIPredicatedArgument(CallSite CS, DominatorTree *DT) { +using PredsWithCondsTy = SmallVector, 2>; + +// Check if any of the arguments in CS are predicated on a PHI node and return +// the set of predecessors we should use for splitting +static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(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) { +// Checks if any of the arguments in CS are predicated in a predecessor and +// returns a list of predecessors with the conditions that hold on their edges +// to CS. +static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallSite CS) { auto Preds = getTwoPredecessors(CS.getInstruction()->getParent()); if (Preds[0] == Preds[1]) - return false; + return {}; SmallVector, 2> PredsCS; for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) { @@ -464,22 +468,31 @@ if (all_of(PredsCS, [](const std::pair &P) { return P.second.empty(); })) - return false; + return {}; - splitCallSite(CS, PredsCS, DT); - return true; + return PredsCS; } static bool tryToSplitCallSite(CallSite CS, TargetTransformInfo &TTI, - DominatorTree *DT) { + DomTreeUpdater &DTU) { + // Check if we can split the call site. if (!CS.arg_size() || !canSplitCallSite(CS, TTI)) return false; - return tryToSplitOnPredicatedArgument(CS, DT) || - tryToSplitOnPHIPredicatedArgument(CS, DT); + + auto PredsWithConds = shouldSplitOnPredicatedArgument(CS); + if (PredsWithConds.empty()) + PredsWithConds = shouldSplitOnPHIPredicatedArgument(CS); + if (PredsWithConds.empty()) + return false; + + splitCallSite(CS, PredsWithConds, DTU); + return true; } static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree *DT) { + + DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy); bool Changed = false; for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) { BasicBlock &BB = *BI++; @@ -503,7 +516,7 @@ // Check if such path is possible before attempting the splitting. bool IsMustTail = CS.isMustTailCall(); - Changed |= tryToSplitCallSite(CS, TTI, DT); + Changed |= tryToSplitCallSite(CS, TTI, 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 @@ -2654,28 +2654,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,12 @@ /// 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) { + + assert(count(successors(PredBB), BB) == 1 && + "There must be a single edge between PredBB and BB!"); // 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 +809,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" @@ -224,9 +225,11 @@ Instruction *SubInst = cast(Builder2.CreateSub(MulInst, V)); Builder2.CreateRetVoid(); + // Dummy DTU ValueToValueMapTy Mapping; - - auto Split = DuplicateInstructionsInSplitBetween(BB2, BB1, SubInst, Mapping); + DomTreeUpdater DTU(DomTreeUpdater::UpdateStrategy::Lazy); + auto Split = + DuplicateInstructionsInSplitBetween(BB2, BB1, SubInst, Mapping, DTU); EXPECT_TRUE(Split); EXPECT_EQ(Mapping.size(), 2u); @@ -271,9 +274,11 @@ Instruction *SubInst = cast(Builder2.CreateSub(MulInst, V)); Builder2.CreateBr(BB2); + // Dummy DTU + DomTreeUpdater DTU(DomTreeUpdater::UpdateStrategy::Lazy); ValueToValueMapTy Mapping; - - 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); @@ -322,9 +327,11 @@ Instruction *SubInst = cast(Builder2.CreateSub(MulInst, V)); Builder2.CreateBr(BB2); + // Dummy DTU + DomTreeUpdater DTU(DomTreeUpdater::UpdateStrategy::Lazy); ValueToValueMapTy Mapping; - - auto Split = DuplicateInstructionsInSplitBetween(BB2, BB2, SubInst, Mapping); + auto Split = + DuplicateInstructionsInSplitBetween(BB2, BB2, SubInst, Mapping, DTU); EXPECT_TRUE(Split); EXPECT_EQ(Mapping.size(), 2u);