aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/DominatorInternals.h87
-rw-r--r--include/llvm/Analysis/Dominators.h24
-rw-r--r--lib/VMCore/Dominators.cpp82
3 files changed, 106 insertions, 87 deletions
diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h
index 3486b77d77..d1d696c3ff 100644
--- a/include/llvm/Analysis/DominatorInternals.h
+++ b/include/llvm/Analysis/DominatorInternals.h
@@ -303,6 +303,93 @@ void Calculate(DominatorTreeBase<typename GraphT::NodeType>& DT, Function& F) {
DT.DFSInfoValid = false;
}
+// NewBB is split and now it has one successor. Update dominator tree to
+// reflect this change.
+template<class NodeT, class GraphT>
+void Split(DominatorTreeBase<typename GraphT::NodeType>& 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<typename GraphT::NodeType*> PredBlocks;
+ for (typename GraphTraits<Inverse<NodeT> >::ChildIteratorType PI =
+ GraphTraits<Inverse<NodeT> >::child_begin(NewBB),
+ PE = GraphTraits<Inverse<NodeT> >::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<Inverse<NodeT> >::ChildIteratorType PI =
+ GraphTraits<Inverse<NodeT> >::child_begin(NewBBSucc),
+ E = GraphTraits<Inverse<NodeT> >::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<Inverse<NodeT> >::ChildIteratorType PI =
+ GraphTraits<Inverse<NodeT> >::child_begin(NewBBSucc),
+ E = GraphTraits<Inverse<NodeT> >::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 3d674e7d81..1fd32c956e 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -160,6 +160,10 @@ typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
/// DominatorTree - Calculate the immediate dominator tree for a function.
///
+template<class N, class GraphT>
+void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType* NewBB);
+
template<class NodeT>
class DominatorTreeBase : public DominatorBase<NodeT> {
protected:
@@ -467,6 +471,21 @@ protected:
friend void Calculate(DominatorTreeBase<typename GraphT::NodeType>& DT,
Function& F);
+ template<class N, class GraphT>
+ friend void Split(DominatorTreeBase<typename GraphT::NodeType>& 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<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB);
+ else
+ Split<NodeT*, GraphTraits<NodeT*> >(*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 a9900fe1a7..b909a0014c 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -56,88 +56,6 @@ char DominatorTree::ID = 0;
static RegisterPass<DominatorTree>
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<BasicBlock*> 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...
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-24 15:28:45 +0000