From 05d2318fbde7b603bd6de690f18d48e0ef44d81d Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Wed, 17 Oct 2007 02:03:17 +0000 Subject: [PATCH] Move splitBlock into DomTreeBase from DomTree. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43059 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/DominatorInternals.h | 87 ++++++++++++++++++++++ include/llvm/Analysis/Dominators.h | 24 ++++-- lib/VMCore/Dominators.cpp | 82 -------------------- 3 files changed, 106 insertions(+), 87 deletions(-) diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index 3486b77d77b..d1d696c3ffa 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -303,6 +303,93 @@ void Calculate(DominatorTreeBase& DT, Function& F) { DT.DFSInfoValid = false; } +// NewBB is split and now it has one successor. Update dominator tree to +// reflect this change. +template +void Split(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); + + std::vector PredBlocks; + for (typename GraphTraits >::ChildIteratorType PI = + GraphTraits >::child_begin(NewBB), + PE = GraphTraits >::child_end(NewBB); PI != PE; ++PI) + PredBlocks.push_back(*PI); + + assert(!PredBlocks.empty() && "No predblocks??"); + + // The newly inserted basic block will dominate existing basic blocks iff the + // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate + // the non-pred blocks, then they all must be the same block! + // + bool NewBBDominatesNewBBSucc = true; + { + typename GraphT::NodeType* OnePred = PredBlocks[0]; + unsigned i = 1, e = PredBlocks.size(); + for (i = 1; !DT.isReachableFromEntry(OnePred); ++i) { + assert(i != e && "Didn't find reachable pred?"); + OnePred = PredBlocks[i]; + } + + for (; i != e; ++i) + if (PredBlocks[i] != OnePred && DT.isReachableFromEntry(OnePred)) { + NewBBDominatesNewBBSucc = false; + break; + } + + if (NewBBDominatesNewBBSucc) + for (typename GraphTraits >::ChildIteratorType PI = + GraphTraits >::child_begin(NewBBSucc), + E = GraphTraits >::child_end(NewBBSucc); PI != E; ++PI) + if (*PI != NewBB && !DT.dominates(NewBBSucc, *PI)) { + NewBBDominatesNewBBSucc = false; + break; + } + } + + // The other scenario where the new block can dominate its successors are when + // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc + // already. + if (!NewBBDominatesNewBBSucc) { + NewBBDominatesNewBBSucc = true; + for (typename GraphTraits >::ChildIteratorType PI = + GraphTraits >::child_begin(NewBBSucc), + E = GraphTraits >::child_end(NewBBSucc); PI != E; ++PI) + if (*PI != NewBB && !DT.dominates(NewBBSucc, *PI)) { + NewBBDominatesNewBBSucc = false; + break; + } + } + + // Find NewBB's immediate dominator and create new dominator tree node for + // NewBB. + BasicBlock *NewBBIDom = 0; + unsigned i = 0; + for (i = 0; i < PredBlocks.size(); ++i) + if (DT.isReachableFromEntry(PredBlocks[i])) { + NewBBIDom = PredBlocks[i]; + break; + } + assert(i != PredBlocks.size() && "No reachable preds?"); + for (i = i + 1; i < PredBlocks.size(); ++i) { + if (DT.isReachableFromEntry(PredBlocks[i])) + NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); + } + assert(NewBBIDom && "No immediate dominator found??"); + + // Create the new dominator tree node... and set the idom of NewBB. + DomTreeNode *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) { + DomTreeNode *NewBBSuccNode = DT.getNode(NewBBSucc); + DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); + } +} + } #endif diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 3d674e7d818..1fd32c956e7 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -160,6 +160,10 @@ typedef DomTreeNodeBase MachineDomTreeNode; /// DominatorTree - Calculate the immediate dominator tree for a function. /// +template +void Split(DominatorTreeBase& DT, + typename GraphT::NodeType* NewBB); + template class DominatorTreeBase : public DominatorBase { protected: @@ -467,6 +471,21 @@ protected: friend void Calculate(DominatorTreeBase& DT, Function& F); + template + friend void Split(DominatorTreeBase& DT, + typename GraphT::NodeType* NewBB); + +public: + /// splitBlock - BB is split and now it has one successor. Update dominator + /// tree to reflect this change. + void splitBlock(NodeT* NewBB) { + if (this->IsPostDominators) + Split, GraphTraits > >(*this, NewBB); + else + Split >(*this, NewBB); + } + +protected: /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking /// dominator tree in dfs order. void updateDFSNumbers() { @@ -547,11 +566,6 @@ public: virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); } - - /// splitBlock - /// BB is split and now it has one successor. Update dominator tree to - /// reflect this change. - void splitBlock(BasicBlock *BB); }; //===------------------------------------- diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index a9900fe1a73..b909a0014cd 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -56,88 +56,6 @@ char DominatorTree::ID = 0; static RegisterPass E("domtree", "Dominator Tree Construction", true); -// NewBB is split and now it has one successor. Update dominator tree to -// reflect this change. -void DominatorTree::splitBlock(BasicBlock *NewBB) { - assert(NewBB->getTerminator()->getNumSuccessors() == 1 - && "NewBB should have a single successor!"); - BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); - - std::vector PredBlocks; - for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); - PI != PE; ++PI) - PredBlocks.push_back(*PI); - - assert(!PredBlocks.empty() && "No predblocks??"); - - // The newly inserted basic block will dominate existing basic blocks iff the - // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate - // the non-pred blocks, then they all must be the same block! - // - bool NewBBDominatesNewBBSucc = true; - { - BasicBlock *OnePred = PredBlocks[0]; - unsigned i = 1, e = PredBlocks.size(); - for (i = 1; !isReachableFromEntry(OnePred); ++i) { - assert(i != e && "Didn't find reachable pred?"); - OnePred = PredBlocks[i]; - } - - for (; i != e; ++i) - if (PredBlocks[i] != OnePred && isReachableFromEntry(OnePred)) { - NewBBDominatesNewBBSucc = false; - break; - } - - if (NewBBDominatesNewBBSucc) - for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); - PI != E; ++PI) - if (*PI != NewBB && !dominates(NewBBSucc, *PI)) { - NewBBDominatesNewBBSucc = false; - break; - } - } - - // The other scenario where the new block can dominate its successors are when - // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc - // already. - if (!NewBBDominatesNewBBSucc) { - NewBBDominatesNewBBSucc = true; - for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); - PI != E; ++PI) - if (*PI != NewBB && !dominates(NewBBSucc, *PI)) { - NewBBDominatesNewBBSucc = false; - break; - } - } - - // Find NewBB's immediate dominator and create new dominator tree node for - // NewBB. - BasicBlock *NewBBIDom = 0; - unsigned i = 0; - for (i = 0; i < PredBlocks.size(); ++i) - if (isReachableFromEntry(PredBlocks[i])) { - NewBBIDom = PredBlocks[i]; - break; - } - assert(i != PredBlocks.size() && "No reachable preds?"); - for (i = i + 1; i < PredBlocks.size(); ++i) { - if (isReachableFromEntry(PredBlocks[i])) - NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); - } - assert(NewBBIDom && "No immediate dominator found??"); - - // Create the new dominator tree node... and set the idom of NewBB. - DomTreeNode *NewBBNode = 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) { - DomTreeNode *NewBBSuccNode = getNode(NewBBSucc); - changeImmediateDominator(NewBBSuccNode, NewBBNode); - } -} - bool DominatorTree::runOnFunction(Function &F) { reset(); // Reset from the last time we were run... -- 2.34.1