Remove ImmediateDominator analysis. The same information can be obtained from DomTree. A lot of code for
constructing ImmediateDominator is now folded into DomTree construction.
This is part of the ongoing work for PR217.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36063 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 6826b94..c948a5f 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -8,13 +8,11 @@
//===----------------------------------------------------------------------===//
//
// This file defines the following classes:
-// 1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
-// and their immediate dominator.
-// 2. DominatorTree: Represent the ImmediateDominator as an explicit tree
+// 1. DominatorTree: Represent the ImmediateDominator as an explicit tree
// structure.
-// 3. ETForest: Efficient data structure for dominance comparisons and
+// 2. ETForest: Efficient data structure for dominance comparisons and
// nearest-common-ancestor queries.
-// 4. DominanceFrontier: Calculate and hold the dominance frontier for a
+// 3. DominanceFrontier: Calculate and hold the dominance frontier for a
// function.
//
// These data structures are listed in increasing order of complexity. It
@@ -58,123 +56,6 @@
bool isPostDominator() const { return IsPostDominators; }
};
-
-//===----------------------------------------------------------------------===//
-/// ImmediateDominators - Calculate the immediate dominator for each node in a
-/// function.
-///
-class ImmediateDominatorsBase : public DominatorBase {
-protected:
- struct InfoRec {
- unsigned Semi;
- unsigned Size;
- BasicBlock *Label, *Parent, *Child, *Ancestor;
-
- std::vector<BasicBlock*> Bucket;
-
- InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
- };
-
- std::map<BasicBlock*, BasicBlock*> IDoms;
-
- // Vertex - Map the DFS number to the BasicBlock*
- std::vector<BasicBlock*> Vertex;
-
- // Info - Collection of information used during the computation of idoms.
- std::map<BasicBlock*, InfoRec> Info;
-public:
- ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
-
- virtual void releaseMemory() { IDoms.clear(); }
-
- // Accessor interface:
- typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
- typedef IDomMapType::const_iterator const_iterator;
- inline const_iterator begin() const { return IDoms.begin(); }
- inline const_iterator end() const { return IDoms.end(); }
- inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
-
- /// operator[] - Return the idom for the specified basic block. The start
- /// node returns null, because it does not have an immediate dominator.
- ///
- inline BasicBlock *operator[](BasicBlock *BB) const {
- return get(BB);
- }
-
- /// dominates - Return true if A dominates B.
- ///
- bool dominates(BasicBlock *A, BasicBlock *B) const;
-
- /// properlyDominates - Return true if A dominates B and A != B.
- ///
- bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
- return A != B || properlyDominates(A, B);
- }
-
- /// get() - Synonym for operator[].
- ///
- inline BasicBlock *get(BasicBlock *BB) const {
- std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
- return I != IDoms.end() ? I->second : 0;
- }
-
- //===--------------------------------------------------------------------===//
- // API to update Immediate(Post)Dominators information based on modifications
- // to the CFG...
-
- /// addNewBlock - Add a new block to the CFG, with the specified immediate
- /// dominator.
- ///
- void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
- assert(get(BB) == 0 && "BasicBlock already in idom info!");
- IDoms[BB] = IDom;
- }
-
- /// setImmediateDominator - Update the immediate dominator information to
- /// change the current immediate dominator for the specified block to another
- /// block. This method requires that BB already have an IDom, otherwise just
- /// use addNewBlock.
- ///
- void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
- assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
- IDoms[BB] = NewIDom;
- }
-
- /// print - Convert to human readable form
- ///
- virtual void print(std::ostream &OS, const Module* = 0) const;
- void print(std::ostream *OS, const Module* M = 0) const {
- if (OS) print(*OS, M);
- }
-};
-
-//===-------------------------------------
-/// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase
-/// that is used to compute a normal immediate dominator set.
-///
-class ImmediateDominators : public ImmediateDominatorsBase {
-public:
- ImmediateDominators() : ImmediateDominatorsBase(false) {}
-
- BasicBlock *getRoot() const {
- assert(Roots.size() == 1 && "Should always have entry node!");
- return Roots[0];
- }
-
- virtual bool runOnFunction(Function &F);
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
- }
-
-private:
- unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
- void Compress(BasicBlock *V, InfoRec &VInfo);
- BasicBlock *Eval(BasicBlock *v);
- void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
-};
-
-
//===----------------------------------------------------------------------===//
/// DominatorTree - Calculate the immediate dominator tree for a function.
///
@@ -187,6 +68,25 @@
typedef std::map<BasicBlock*, Node*> NodeMapType;
Node *RootNode;
+
+ struct InfoRec {
+ unsigned Semi;
+ unsigned Size;
+ BasicBlock *Label, *Parent, *Child, *Ancestor;
+
+ std::vector<BasicBlock*> Bucket;
+
+ InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
+ };
+
+ std::map<BasicBlock*, BasicBlock*> IDoms;
+
+ // Vertex - Map the DFS number to the BasicBlock*
+ std::vector<BasicBlock*> Vertex;
+
+ // Info - Collection of information used during the computation of idoms.
+ std::map<BasicBlock*, InfoRec> Info;
+
public:
class Node {
friend class DominatorTree;
@@ -313,21 +213,22 @@
return Roots[0];
}
- virtual bool runOnFunction(Function &F) {
- reset(); // Reset from the last time we were run...
- ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
- Roots = ID.getRoots();
- calculate(ID);
- return false;
- }
+ virtual bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequired<ImmediateDominators>();
}
private:
- void calculate(const ImmediateDominators &ID);
+ void calculate(Function& F);
Node *getNodeForBlock(BasicBlock *BB);
+ unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
+ void Compress(BasicBlock *V, InfoRec &VInfo);
+ BasicBlock *Eval(BasicBlock *v);
+ void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
+ inline BasicBlock *getIDom(BasicBlock *BB) const {
+ std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
+ return I != IDoms.end() ? I->second : 0;
+ }
};
//===-------------------------------------
diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h
index aea9013..4997f93 100644
--- a/include/llvm/Analysis/PostDominators.h
+++ b/include/llvm/Analysis/PostDominators.h
@@ -18,26 +18,6 @@
namespace llvm {
-//===-------------------------------------
-/// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
-/// that is used to compute a normal immediate dominator set.
-///
-struct ImmediatePostDominators : public ImmediateDominatorsBase {
- ImmediatePostDominators() : ImmediateDominatorsBase(false) {}
-
- virtual bool runOnFunction(Function &F);
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
- }
-
-private:
- unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
- void Compress(BasicBlock *V, InfoRec &VInfo);
- BasicBlock *Eval(BasicBlock *v);
- void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
-};
-
/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
/// compute the a post-dominator tree.
///
@@ -46,19 +26,25 @@
virtual bool runOnFunction(Function &F) {
reset(); // Reset from the last time we were run...
- ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>();
- Roots = IPD.getRoots();
- calculate(IPD);
+ calculate(F);
return false;
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequired<ImmediatePostDominators>();
}
private:
- void calculate(const ImmediatePostDominators &IPD);
+ void calculate(Function &F);
Node *getNodeForBlock(BasicBlock *BB);
+ unsigned DFSPass(BasicBlock *V, InfoRec &VInfo,unsigned N);
+ void Compress(BasicBlock *V, InfoRec &VInfo);
+ BasicBlock *Eval(BasicBlock *V);
+ void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
+
+ inline BasicBlock *getIDom(BasicBlock *BB) const {
+ std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
+ return I != IDoms.end() ? I->second : 0;
+ }
};
@@ -69,18 +55,18 @@
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequired<ImmediatePostDominators>();
+ AU.addRequired<PostDominatorTree>();
}
virtual bool runOnFunction(Function &F) {
reset(); // Reset from the last time we were run...
- ImmediatePostDominators &ID = getAnalysis<ImmediatePostDominators>();
- Roots = ID.getRoots();
- calculate(ID);
+ PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
+ Roots = DT.getRoots();
+ calculate(DT);
return false;
}
- void calculate(const ImmediatePostDominators &ID);
+ void calculate(const PostDominatorTree &DT);
ETNode *getNodeForBlock(BasicBlock *BB);
};
diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h
index 7481c82..f13104b 100644
--- a/include/llvm/LinkAllPasses.h
+++ b/include/llvm/LinkAllPasses.h
@@ -113,7 +113,6 @@
(void) llvm::createCodeGenPreparePass();
(void)new llvm::IntervalPartition();
- (void)new llvm::ImmediateDominators();
(void)new llvm::FindUsedTypes();
(void)new llvm::ScalarEvolution();
((llvm::Function*)0)->viewCFGOnly();
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index 2439940..7351ed7 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -19,13 +19,13 @@
using namespace llvm;
//===----------------------------------------------------------------------===//
-// ImmediatePostDominators Implementation
+// PostDominatorTree Implementation
//===----------------------------------------------------------------------===//
-static RegisterPass<ImmediatePostDominators>
-D("postidom", "Immediate Post-Dominators Construction", true);
+static RegisterPass<PostDominatorTree>
+F("postdomtree", "Post-Dominator Tree Construction", true);
-unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
+unsigned PostDominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo,
unsigned N) {
std::vector<std::pair<BasicBlock *, InfoRec *> > workStack;
std::set<BasicBlock *> visited;
@@ -73,7 +73,7 @@
return N;
}
-void ImmediatePostDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
+void PostDominatorTree::Compress(BasicBlock *V, InfoRec &VInfo) {
BasicBlock *VAncestor = VInfo.Ancestor;
InfoRec &VAInfo = Info[VAncestor];
if (VAInfo.Ancestor == 0)
@@ -89,7 +89,7 @@
VInfo.Ancestor = VAInfo.Ancestor;
}
-BasicBlock *ImmediatePostDominators::Eval(BasicBlock *V) {
+BasicBlock *PostDominatorTree::Eval(BasicBlock *V) {
InfoRec &VInfo = Info[V];
// Higher-complexity but faster implementation
@@ -99,16 +99,13 @@
return VInfo.Label;
}
-void ImmediatePostDominators::Link(BasicBlock *V, BasicBlock *W,
+void PostDominatorTree::Link(BasicBlock *V, BasicBlock *W,
InfoRec &WInfo) {
// Higher-complexity but faster implementation
WInfo.Ancestor = V;
}
-bool ImmediatePostDominators::runOnFunction(Function &F) {
- IDoms.clear(); // Reset from the last time we were run...
- Roots.clear();
-
+void PostDominatorTree::calculate(Function &F) {
// Step #0: Scan the function looking for the root nodes of the post-dominance
// relationships. These blocks, which have no successors, end with return and
// unwind instructions.
@@ -159,35 +156,6 @@
WIDom = IDoms[WIDom];
}
- // Free temporary memory used to construct idom's
- Info.clear();
- std::vector<BasicBlock*>().swap(Vertex);
-
- return false;
-}
-
-//===----------------------------------------------------------------------===//
-// PostDominatorTree Implementation
-//===----------------------------------------------------------------------===//
-
-static RegisterPass<PostDominatorTree>
-F("postdomtree", "Post-Dominator Tree Construction", true);
-
-DominatorTreeBase::Node *PostDominatorTree::getNodeForBlock(BasicBlock *BB) {
- Node *&BBNode = Nodes[BB];
- if (BBNode) return BBNode;
-
- // Haven't calculated this node yet? Get or calculate the node for the
- // immediate postdominator.
- BasicBlock *IPDom = getAnalysis<ImmediatePostDominators>()[BB];
- Node *IPDomNode = getNodeForBlock(IPDom);
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- return BBNode = IPDomNode->addChild(new Node(BB, IPDomNode));
-}
-
-void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) {
if (Roots.empty()) return;
// Add a node for the root. This node might be the actual root, if there is
@@ -196,10 +164,9 @@
BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0;
Nodes[Root] = RootNode = new Node(Root, 0);
- Function *F = Roots[0]->getParent();
// Loop over all of the reachable blocks in the function...
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
- if (BasicBlock *ImmPostDom = IPD.get(I)) { // Reachable block.
+ for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
+ if (BasicBlock *ImmPostDom = getIDom(I)) { // Reachable block.
Node *&BBNode = Nodes[I];
if (!BBNode) { // Haven't calculated this node yet?
// Get or calculate the node for the immediate dominator
@@ -210,6 +177,26 @@
BBNode = IPDomNode->addChild(new Node(I, IPDomNode));
}
}
+
+ // Free temporary memory used to construct idom's
+ IDoms.clear();
+ Info.clear();
+ std::vector<BasicBlock*>().swap(Vertex);
+}
+
+
+DominatorTreeBase::Node *PostDominatorTree::getNodeForBlock(BasicBlock *BB) {
+ Node *&BBNode = Nodes[BB];
+ if (BBNode) return BBNode;
+
+ // Haven't calculated this node yet? Get or calculate the node for the
+ // immediate postdominator.
+ BasicBlock *IPDom = getIDom(BB);
+ Node *IPDomNode = getNodeForBlock(IPDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ return BBNode = IPDomNode->addChild(new Node(BB, IPDomNode));
}
//===----------------------------------------------------------------------===//
@@ -225,13 +212,15 @@
// Haven't calculated this node yet? Get or calculate the node for the
// immediate dominator.
- BasicBlock *IDom = getAnalysis<ImmediatePostDominators>()[BB];
+ PostDominatorTree::Node *node = getAnalysis<PostDominatorTree>().getNode(BB);
// If we are unreachable, we may not have an immediate dominator.
- if (!IDom)
+ if (!node)
+ return 0;
+ else if (!node->getIDom())
return BBNode = new ETNode(BB);
else {
- ETNode *IDomNode = getNodeForBlock(IDom);
+ ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock());
// Add a new tree node for this BasicBlock, and link it as a child of
// IDomNode
@@ -241,7 +230,7 @@
}
}
-void PostETForest::calculate(const ImmediatePostDominators &ID) {
+void PostETForest::calculate(const PostDominatorTree &DT) {
for (unsigned i = 0, e = Roots.size(); i != e; ++i)
Nodes[Roots[i]] = new ETNode(Roots[i]); // Add a node for the root
@@ -253,9 +242,9 @@
ETNode *&BBNode = Nodes[BB];
if (!BBNode) {
ETNode *IDomNode = NULL;
-
- if (ID.get(BB))
- IDomNode = getNodeForBlock(ID.get(BB));
+ PostDominatorTree::Node *node = DT.getNode(BB);
+ if (node && node->getIDom())
+ IDomNode = getNodeForBlock(node->getIDom()->getBlock());
// Add a new ETNode for this BasicBlock, and set it's parent
// to it's immediate dominator.
diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index 332ddfa..38cfd91 100644
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -154,7 +154,6 @@
AU.addPreservedID(LoopSimplifyID);
AU.addPreserved<LoopInfo>();
AU.addPreserved<ETForest>();
- AU.addPreserved<ImmediateDominators>();
AU.addPreserved<DominanceFrontier>();
AU.addPreserved<DominatorTree>();
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index 2f91e57..2cf2ecd 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -38,7 +38,6 @@
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<ETForest>();
- AU.addPreserved<ImmediateDominators>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<DominanceFrontier>();
AU.addPreserved<LoopInfo>();
@@ -196,29 +195,6 @@
if (NewBBDominatesDestBB)
EF->setImmediateDominator(DestBB, NewBB);
}
-
- // Should we update ImmediateDominator information?
- if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) {
- // Only do this if TIBB is reachable.
- if (ID->get(TIBB) || &TIBB->getParent()->getEntryBlock() == TIBB) {
- // TIBB is the new immediate dominator for NewBB.
- ID->addNewBlock(NewBB, TIBB);
-
- // If NewBBDominatesDestBB hasn't been computed yet, do so with ID.
- if (!OtherPreds.empty()) {
- while (!OtherPreds.empty() && NewBBDominatesDestBB) {
- NewBBDominatesDestBB = ID->dominates(DestBB, OtherPreds.back());
- OtherPreds.pop_back();
- }
- OtherPreds.clear();
- }
-
- // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it
- // doesn't dominate anything.
- if (NewBBDominatesDestBB)
- ID->setImmediateDominator(DestBB, NewBB);
- }
- }
// Should we update DominatorTree information?
if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) {
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 7599168..7d34b95 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -68,7 +68,6 @@
AU.addRequired<ETForest>();
AU.addPreserved<LoopInfo>();
- AU.addPreserved<ImmediateDominators>();
AU.addPreserved<ETForest>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<DominanceFrontier>();
@@ -749,31 +748,6 @@
}
BasicBlock *NewBBIDom = 0;
-
- // Update immediate dominator information if we have it.
- if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) {
- unsigned i = 0;
- for (i = 0; i < PredBlocks.size(); ++i)
- if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i])) {
- NewBBIDom = PredBlocks[i];
- break;
- }
- assert(i != PredBlocks.size() && "No reachable preds?");
- for (i = i + 1; i < PredBlocks.size(); ++i) {
- if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i]))
- NewBBIDom = ETF.nearestCommonDominator(NewBBIDom, PredBlocks[i]);
- }
- assert(NewBBIDom && "No immediate dominator found??");
-
- // Set the immediate dominator now...
- ID->addNewBlock(NewBB, NewBBIDom);
-
- // If NewBB strictly dominates other blocks, we need to update their idom's
- // now. The only block that need adjustment is the NewBBSucc block, whose
- // idom should currently be set to PredBlocks[0].
- if (NewBBDominatesNewBBSucc)
- ID->setImmediateDominator(NewBBSucc, NewBB);
- }
// Update DominatorTree information if it is active.
if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 0959b07..9685ed9 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -24,11 +24,24 @@
#include <algorithm>
using namespace llvm;
+namespace llvm {
+static std::ostream &operator<<(std::ostream &o,
+ const std::set<BasicBlock*> &BBs) {
+ for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
+ I != E; ++I)
+ if (*I)
+ WriteAsOperand(o, *I, false);
+ else
+ o << " <<exit node>>";
+ return o;
+}
+}
+
//===----------------------------------------------------------------------===//
-// ImmediateDominators Implementation
+// DominatorTree Implementation
//===----------------------------------------------------------------------===//
//
-// Immediate Dominators construction - This pass constructs immediate dominator
+// DominatorTree construction - This pass constructs immediate dominator
// information for a flow-graph based on the algorithm described in this
// document:
//
@@ -45,10 +58,10 @@
//
//===----------------------------------------------------------------------===//
-static RegisterPass<ImmediateDominators>
-C("idom", "Immediate Dominators Construction", true);
+static RegisterPass<DominatorTree>
+E("domtree", "Dominator Tree Construction", true);
-unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
+unsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo,
unsigned N) {
// This is more understandable as a recursive algorithm, but we can't use the
// recursive algorithm due to stack depth issues. Keep it here for
@@ -110,7 +123,7 @@
return N;
}
-void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
+void DominatorTree::Compress(BasicBlock *V, InfoRec &VInfo) {
BasicBlock *VAncestor = VInfo.Ancestor;
InfoRec &VAInfo = Info[VAncestor];
if (VAInfo.Ancestor == 0)
@@ -126,7 +139,7 @@
VInfo.Ancestor = VAInfo.Ancestor;
}
-BasicBlock *ImmediateDominators::Eval(BasicBlock *V) {
+BasicBlock *DominatorTree::Eval(BasicBlock *V) {
InfoRec &VInfo = Info[V];
#if !BALANCE_IDOM_TREE
// Higher-complexity but faster implementation
@@ -149,7 +162,7 @@
#endif
}
-void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
+void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
#if !BALANCE_IDOM_TREE
// Higher-complexity but faster implementation
WInfo.Ancestor = V;
@@ -196,13 +209,10 @@
#endif
}
-
-
-bool ImmediateDominators::runOnFunction(Function &F) {
- IDoms.clear(); // Reset from the last time we were run...
- BasicBlock *Root = &F.getEntryBlock();
- Roots.clear();
- Roots.push_back(Root);
+void DominatorTree::calculate(Function& F) {
+ BasicBlock* Root = Roots[0];
+
+ Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
Vertex.push_back(0);
@@ -247,65 +257,34 @@
WIDom = IDoms[WIDom];
}
+ // Loop over all of the reachable blocks in the function...
+ for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
+ if (BasicBlock *ImmDom = getIDom(I)) { // Reachable block.
+ Node *&BBNode = Nodes[I];
+ if (!BBNode) { // Haven't calculated this node yet?
+ // Get or calculate the node for the immediate dominator
+ Node *IDomNode = getNodeForBlock(ImmDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ BBNode = IDomNode->addChild(new Node(I, IDomNode));
+ }
+ }
+
// Free temporary memory used to construct idom's
Info.clear();
+ IDoms.clear();
std::vector<BasicBlock*>().swap(Vertex);
-
- return false;
}
-/// dominates - Return true if A dominates B.
-///
-bool ImmediateDominatorsBase::dominates(BasicBlock *A, BasicBlock *B) const {
- assert(A && B && "Null pointers?");
-
- // Walk up the dominator tree from B to determine if A dom B.
- while (A != B && B)
- B = get(B);
- return A == B;
-}
-
-void ImmediateDominatorsBase::print(std::ostream &o, const Module* ) const {
- Function *F = getRoots()[0]->getParent();
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
- o << " Immediate Dominator For Basic Block:";
- WriteAsOperand(o, I, false);
- o << " is:";
- if (BasicBlock *ID = get(I))
- WriteAsOperand(o, ID, false);
- else
- o << " <<exit node>>";
- o << "\n";
- }
- o << "\n";
-}
-
-namespace llvm {
-static std::ostream &operator<<(std::ostream &o,
- const std::set<BasicBlock*> &BBs) {
- for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
- I != E; ++I)
- if (*I)
- WriteAsOperand(o, *I, false);
- else
- o << " <<exit node>>";
- return o;
-}
-}
-
-//===----------------------------------------------------------------------===//
-// DominatorTree Implementation
-//===----------------------------------------------------------------------===//
-
-static RegisterPass<DominatorTree>
-E("domtree", "Dominator Tree Construction", true);
-
// DominatorTreeBase::reset - Free all of the tree node memory.
//
void DominatorTreeBase::reset() {
for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
delete I->second;
Nodes.clear();
+ IDoms.clear();
+ Roots.clear();
RootNode = 0;
}
@@ -331,7 +310,7 @@
// Haven't calculated this node yet? Get or calculate the node for the
// immediate dominator.
- BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
+ BasicBlock *IDom = getIDom(BB);
Node *IDomNode = getNodeForBlock(IDom);
// Add a new tree node for this BasicBlock, and link it as a child of
@@ -339,27 +318,6 @@
return BBNode = IDomNode->addChild(new Node(BB, IDomNode));
}
-void DominatorTree::calculate(const ImmediateDominators &ID) {
- assert(Roots.size() == 1 && "DominatorTree should have 1 root block!");
- BasicBlock *Root = Roots[0];
- Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
-
- Function *F = Root->getParent();
- // Loop over all of the reachable blocks in the function...
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
- if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block.
- Node *&BBNode = Nodes[I];
- if (!BBNode) { // Haven't calculated this node yet?
- // Get or calculate the node for the immediate dominator
- Node *IDomNode = getNodeForBlock(ImmDom);
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- BBNode = IDomNode->addChild(new Node(I, IDomNode));
- }
- }
-}
-
static std::ostream &operator<<(std::ostream &o,
const DominatorTreeBase::Node *Node) {
if (Node->getBlock())
@@ -383,6 +341,12 @@
PrintDomTree(getRootNode(), o, 1);
}
+bool DominatorTree::runOnFunction(Function &F) {
+ reset(); // Reset from the last time we were run...
+ Roots.push_back(&F.getEntryBlock());
+ calculate(F);
+ return false;
+}
//===----------------------------------------------------------------------===//
// DominanceFrontier Implementation