Index: include/llvm/CodeGen/MachineDominators.h =================================================================== --- include/llvm/CodeGen/MachineDominators.h +++ include/llvm/CodeGen/MachineDominators.h @@ -200,11 +200,11 @@ DT->eraseNode(BB); } - /// splitBlock - BB is split and now it has one successor. Update dominator - /// tree to reflect this change. - inline void splitBlock(MachineBasicBlock* NewBB) { + /// splitBlockUpward - BB is split and now it has one successor. Update + /// dominator tree to reflect this change. + inline void splitBlockUpward(MachineBasicBlock* NewBB) { applySplitCriticalEdges(); - DT->splitBlock(NewBB); + DT->splitBlockUpward(NewBB); } /// isReachableFromEntry - Return true if A is dominated by the entry Index: include/llvm/Support/GenericDomTree.h =================================================================== --- include/llvm/Support/GenericDomTree.h +++ include/llvm/Support/GenericDomTree.h @@ -21,6 +21,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" @@ -179,6 +180,46 @@ void Calculate(DominatorTreeBase::NodeType> &DT, FuncT &F); +template class DominatedAndPrunedTraversal { + typedef typename GraphT::NodeType NodeTy; + + DominatorTreeBase &DT; + DomTreeNodeBase *Parent; + NodeTy *PrunedBlock; + SmallPtrSet Visited; + +public: + DominatedAndPrunedTraversal(DominatorTreeBase &D, + DomTreeNodeBase *N, NodeTy *PrunedBlock) + : DT(D), Parent(N), PrunedBlock(PrunedBlock) {} + + bool preVisit(const NodeTy *From, const NodeTy *To) { + if (To == PrunedBlock) + return false; + DomTreeNodeBase *N = DT.getNode(const_cast(To)); + if (!DT.dominates(Parent, N)) + return false; + return Visited.insert(To).second; + } + void postVisit(const NodeTy *) {} +}; + +/// Specialize po_iterator_storage. +template +class po_iterator_storage, true> { + typedef typename GraphT::NodeType NodeTy; + + DominatedAndPrunedTraversal &DAPT; + +public: + po_iterator_storage(DominatedAndPrunedTraversal &T) : DAPT(T) {} + + bool insertEdge(const NodeTy *From, const NodeTy *To) { + return DAPT.preVisit(From, To); + } + void finishPostorder(const NodeTy *N) { DAPT.postVisit(N); } +}; + /// \brief Core dominator tree base class. /// /// This class is a generic template over graph nodes. It is instantiated for @@ -190,8 +231,8 @@ bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, const DomTreeNodeBase *B) const { assert(A != B); - assert(isReachableFromEntry(B)); - assert(isReachableFromEntry(A)); + assert(isDominatedByRoot(B)); + assert(isDominatedByRoot(A)); const DomTreeNodeBase *IDom; while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B) @@ -247,15 +288,52 @@ SlowQueries = 0; } - // NewBB is split and now it has one successor. Update dominator tree to - // reflect this change. + // NewBB is split upward and now it has the original BB as its single + // successor. Update dominator tree to reflect this change. + // + // By `upward`, the original block + // + // | | | | + // | | | | + // +---v---v---v---v---+ + // | | + // | OrigBB | + // | | + // +---+---+---+---+---+ + // | | | | + // v v v v + // + // + // is split into + // + // + // | | | | + // | | | | + // | | +-----v------v------+ + // | | | | + // | | | NewBB | + // | | | | + // | | +---------+---------+ + // | | | + // | | | + // | | /--------/ + // | | | + // | | | + // +---v----v----v-----+ + // | | + // | OrigBB | + // | | + // +---+---+---+---+---+ + // | | | | + // v v v v + // template - void Split(DominatorTreeBase &DT, - typename GraphT::NodeType *NewBB) { + void splitUpward(DominatorTreeBase &DT, + typename GraphT::NodeType *NewBB) { assert(std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1 && "NewBB should have a single successor!"); - typename GraphT::NodeType *NewBBSucc = *GraphT::child_begin(NewBB); + typename GraphT::NodeType *OrigBB = *GraphT::child_begin(NewBB); std::vector PredBlocks; typedef GraphTraits> InvTraits; @@ -267,15 +345,15 @@ assert(!PredBlocks.empty() && "No predblocks?"); - bool NewBBDominatesNewBBSucc = true; + bool NewBBDominatesOrigBB = true; for (typename InvTraits::ChildIteratorType - PI = InvTraits::child_begin(NewBBSucc), - E = InvTraits::child_end(NewBBSucc); + PI = InvTraits::child_begin(OrigBB), + E = InvTraits::child_end(OrigBB); PI != E; ++PI) { typename InvTraits::NodeType *ND = *PI; - if (ND != NewBB && !DT.dominates(NewBBSucc, ND) && - DT.isReachableFromEntry(ND)) { - NewBBDominatesNewBBSucc = false; + if (ND != NewBB && !DT.dominates(OrigBB, ND) && + DT.isDominatedByRoot(DT.getNode(ND))) { + NewBBDominatesOrigBB = false; break; } } @@ -285,7 +363,7 @@ NodeT *NewBBIDom = nullptr; unsigned i = 0; for (i = 0; i < PredBlocks.size(); ++i) - if (DT.isReachableFromEntry(PredBlocks[i])) { + if (DT.isDominatedByRoot(DT.getNode(PredBlocks[i]))) { NewBBIDom = PredBlocks[i]; break; } @@ -297,7 +375,7 @@ return; for (i = i + 1; i < PredBlocks.size(); ++i) { - if (DT.isReachableFromEntry(PredBlocks[i])) + if (DT.isDominatedByRoot(DT.getNode(PredBlocks[i]))) NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); } @@ -305,13 +383,84 @@ DomTreeNodeBase *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom); // If NewBB strictly dominates other blocks, then it is now the immediate - // dominator of NewBBSucc. Update the dominator tree as appropriate. - if (NewBBDominatesNewBBSucc) { - DomTreeNodeBase *NewBBSuccNode = DT.getNode(NewBBSucc); - DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); + // dominator of OrigBB. Update the dominator tree as appropriate. + if (NewBBDominatesOrigBB) { + DomTreeNodeBase *OrigBBNode = DT.getNode(OrigBB); + DT.changeImmediateDominator(OrigBBNode, NewBBNode); } } + // NewBB is split downward and now it has the original BB as its single + // predecessor. Update dominator tree to reflect this change. + // + // By `downward`, the original block + // + // | | | | + // | | | | + // +---v---v---v---v---+ + // | | + // | OrigBB | + // | | + // +---+---+---+---+---+ + // | | | | + // v v v v + // + // + // is split into + // + // + // | | | | + // | | | | + // +---v---v---v---v---+ + // | | + // | OrigBB | + // | | + // +---+----+----+-----+ + // | | | + // | | | + // | | \--------\ + // | | | + // | | | + // | | +---------v---------+ + // | | | | + // | | | NewBB | + // | | | | + // | | +-----+------+------+ + // | | | | + // v v v v + // + template + void splitDownward(DominatorTreeBase &DT, + typename GraphT::NodeType *NewBB) { + typedef GraphTraits> InvGraphT; + assert(std::distance(InvGraphT::child_begin(NewBB), + InvGraphT::child_end(NewBB)) == 1 && + "NewBB should have a single predecessor!"); + typename InvGraphT::NodeType *OrigBB = *InvGraphT::child_begin(NewBB); + + auto OrigNode = DT.getNode(OrigBB); + // Skip node not reachable. + if (!OrigNode) return; + + // Collect original child blocks of OrigBB. + SmallPtrSet OrigChildBBs; + for (auto I = OrigNode->begin(), E = OrigNode->end(); I != E; ++I) + OrigChildBBs.insert((*I)->getBlock()); + + // Add NewBB with OrigBB as its immediate dominator since NewBB has a + // single predecessor. + DT.addNewBlock(NewBB, OrigBB); + + // Prune original child blocks. + DominatedAndPrunedTraversal DAPT(DT, OrigNode, NewBB); + for (auto I : post_order_ext(OrigBB, DAPT)) + OrigChildBBs.erase(I); + // Re-parent the remaining blocks, which are only reachable from the split + // NewBB. + for (auto I : OrigChildBBs) + DT.changeImmediateDominator(I, NewBB); + } + public: explicit DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom), DFSInfoValid(false), SlowQueries(0) {} @@ -429,10 +578,10 @@ bool isReachableFromEntry(const NodeT *A) const { assert(!this->isPostDominator() && "This is not implemented for post dominators"); - return isReachableFromEntry(getNode(const_cast(A))); + return isDominatedByRoot(getNode(const_cast(A))); } - bool isReachableFromEntry(const DomTreeNodeBase *A) const { return A; } + bool isDominatedByRoot(const DomTreeNodeBase *A) const { return A; } /// dominates - Returns true iff A dominates B. Note that this is not a /// constant time operation! @@ -444,11 +593,11 @@ return true; // An unreachable node is dominated by anything. - if (!isReachableFromEntry(B)) + if (!isDominatedByRoot(B)) return true; // And dominates nothing. - if (!isReachableFromEntry(A)) + if (!isDominatedByRoot(A)) return false; // Compare the result of the tree walk and the dfs numbers, if expensive @@ -600,14 +749,24 @@ DomTreeNodes.erase(BB); } - /// splitBlock - BB is split and now it has one successor. Update dominator - /// tree to reflect this change. - void splitBlock(NodeT *NewBB) { + /// splitBlockUpward - BB is split upward and now it has one successor. + /// Update dominator tree to reflect this change. + void splitBlockUpward(NodeT *NewBB) { + if (this->IsPostDominators) + this->splitDownward, GraphTraits>>( + *this, NewBB); + else + this->splitUpward>(*this, NewBB); + } + + /// splitBlockDownward - BB is split downward and now it has one successor. + /// Update dominator tree to reflect this change. + void splitBlockDownward(NodeT *NewBB) { if (this->IsPostDominators) - this->Split, GraphTraits>>(*this, - NewBB); + this->splitUpward, GraphTraits>>(*this, + NewBB); else - this->Split>(*this, NewBB); + this->splitDownward>(*this, NewBB); } /// print - Convert to human readable form Index: lib/Transforms/Utils/BasicBlockUtils.cpp =================================================================== --- lib/Transforms/Utils/BasicBlockUtils.cpp +++ lib/Transforms/Utils/BasicBlockUtils.cpp @@ -319,7 +319,7 @@ bool PreserveLCSSA, bool &HasLoopExit) { // Update dominator tree if available. if (DT) - DT->splitBlock(NewBB); + DT->splitBlockUpward(NewBB); // The rest of the logic is only relevant for updating the loop structures. if (!LI) Index: lib/Transforms/Utils/CodeExtractor.cpp =================================================================== --- lib/Transforms/Utils/CodeExtractor.cpp +++ lib/Transforms/Utils/CodeExtractor.cpp @@ -225,7 +225,7 @@ // Okay, update dominator sets. The blocks that dominate the new one are the // blocks that dominate TIBB plus the new block itself. if (DT) - DT->splitBlock(NewBB); + DT->splitBlockUpward(NewBB); // Okay, now we need to adjust the PHI nodes and any branches from within the // region to go to the new header block instead of the old header block. Index: lib/Transforms/Utils/LoopSimplify.cpp =================================================================== --- lib/Transforms/Utils/LoopSimplify.cpp +++ lib/Transforms/Utils/LoopSimplify.cpp @@ -464,7 +464,7 @@ L->addBasicBlockToLoop(BEBlock, *LI); // Update dominator information - DT->splitBlock(BEBlock); + DT->splitBlockUpward(BEBlock); return BEBlock; } Index: lib/Transforms/Vectorize/SLPVectorizer.cpp =================================================================== --- lib/Transforms/Vectorize/SLPVectorizer.cpp +++ lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -2691,7 +2691,7 @@ CSEWorkList.reserve(CSEBlocks.size()); for (BasicBlock *BB : CSEBlocks) if (DomTreeNode *N = DT->getNode(BB)) { - assert(DT->isReachableFromEntry(N)); + assert(DT->isDominatedByRoot(N)); CSEWorkList.push_back(N); } Index: unittests/IR/DominatorTreeTest.cpp =================================================================== --- unittests/IR/DominatorTreeTest.cpp +++ unittests/IR/DominatorTreeTest.cpp @@ -22,6 +22,7 @@ namespace llvm { void initializeDPassPass(PassRegistry&); + void initializeSplitTestPass(PassRegistry&); namespace { struct DPass : public FunctionPass { @@ -250,6 +251,55 @@ Passes.add(P); Passes.run(*M); } + + struct SplitTest : public FunctionPass { + typedef std::function + CallbackFuncTy; + + CallbackFuncTy Callback; + + explicit SplitTest(CallbackFuncTy Callback = nullptr) + : FunctionPass(ID), Callback(Callback) { + initializeSplitTestPass(*PassRegistry::getPassRegistry()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + } + + bool runOnFunction(Function &F) override { + DominatorTree *DT = + &getAnalysis().getDomTree(); + PostDominatorTree *PDT = &getAnalysis(); + + bool NeedVerifyDom = false; + bool NeedVerifyPostDom = false; + bool Changed = Callback(this, F, NeedVerifyDom, NeedVerifyPostDom); + + EXPECT_TRUE(!NeedVerifyDom || !verifyDominatorTree(F, DT)); + EXPECT_TRUE(!NeedVerifyPostDom || !verifyDominatorTree(F, PDT->DT)); + + return Changed; + } + + bool verifyDominatorTree(Function &F, + DominatorTreeBase *DT) { + DominatorTreeBase OtherDT(DT->isPostDominator()); + OtherDT.recalculate(F); + return DT->compare(OtherDT); + } + + static char ID; + }; + + char SplitTest::ID = 0; + + std::unique_ptr loadModule(const char *ModuleString) { + LLVMContext &C = getGlobalContext(); + SMDiagnostic Err; + return parseAssemblyString(ModuleString, Err, C); + } } } @@ -257,3 +307,114 @@ INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false) + +INITIALIZE_PASS_BEGIN(SplitTest, "split-test-pass", "split-test-pass", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) +INITIALIZE_PASS_END(SplitTest, "split-test-pass", "split-test-pass", false, false) + +TEST(DominatorTree, SplitUp) { + std::unique_ptr M = loadModule( + "define void @t0() {\n" + "entry:\n" + " br i1 undef, label %bb0, label %exit\n" + "bb0:\n" + " br i1 undef, label %bb1, label %bb2\n" + "bb1:\n" + " br label %exit\n" + "bb2:\n" + " br label %exit\n" + "exit:\n" + " ret void\n" + "}\n"); + Function *t0 = M->getFunction("t0"); + SplitTest *P = new SplitTest([t0](Pass *P, Function &F, + bool &NeedVerifyDom, + bool &NeedVerifyPostDom) -> bool { + if (t0 != &F) + return false; + Function::iterator FI = F.begin(); + + /* Entry */ FI++; + /* BB0 */ FI++; + BasicBlock *BB1 = &*FI++; + BasicBlock *BB2 = &*FI++; + BasicBlock *Exit = &*FI++; + + BasicBlock *Joint = BasicBlock::Create(F.getContext(), "joint", &F, Exit); + BranchInst::Create(Exit, Joint); + + BB1->getTerminator()->setSuccessor(0, Joint); + BB2->getTerminator()->setSuccessor(0, Joint); + + if (auto DTWP = P->getAnalysisIfAvailable()) { + DominatorTree &DT = DTWP->getDomTree(); + DT.splitBlockUpward(Joint); + NeedVerifyDom = true; + } + + if (auto PDT = P->getAnalysisIfAvailable()) { + PDT->DT->splitBlockUpward(Joint); + NeedVerifyPostDom = true; + } + + return true; + }); + legacy::PassManager PM; + PM.add(P); + PM.run(*M); +} + +TEST(DominatorTree, SplitDown) { + std::unique_ptr M = loadModule( + "define void @t0() {\n" + "entry:\n" + " indirectbr i8* undef, [label %bb0, label %bb1, label %bb2]\n" + "bb0:\n" + " br i1 undef, label %bb3, label %bb4\n" + "bb1:\n" + " br label %exit\n" + "bb2:\n" + " br label %exit\n" + "bb3:\n" + " br label %exit\n" + "bb4:\n" + " br i1 undef, label %exit, label %bb1\n" + "exit:\n" + " ret void\n" + "}\n"); + Function *t0 = M->getFunction("t0"); + SplitTest *P = new SplitTest([t0](Pass *P, Function &F, + bool &NeedVerifyDom, + bool &NeedVerifyPostDom) -> bool { + if (t0 != &F) + return false; + + Function::iterator FI = F.begin(); + BasicBlock *Entry = &*FI++; + BasicBlock *BB0 = &*FI++; + BasicBlock *BB1 = &*FI++; + BasicBlock *BB2 = &*FI++; + BasicBlock *Split = BasicBlock::Create(F.getContext(), "split", &F, BB0); + BranchInst::Create(BB1, BB2, ConstantInt::getTrue(F.getContext()), Split); + + Entry->getTerminator()->eraseFromParent(); + BranchInst::Create(BB0, Split, ConstantInt::getTrue(F.getContext()), Entry); + + if (auto DTWP = P->getAnalysisIfAvailable()) { + DominatorTree &DT = DTWP->getDomTree(); + DT.splitBlockDownward(Split); + NeedVerifyDom = true; + } + + if (auto PDT = P->getAnalysisIfAvailable()) { + PDT->DT->splitBlockDownward(Split); + NeedVerifyPostDom = true; + } + + return true; + }); + legacy::PassManager PM; + PM.add(P); + PM.run(*M); +}