summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/Dominators.h15
-rw-r--r--include/llvm/Analysis/PostDominators.h2
-rw-r--r--lib/Analysis/PostDominators.cpp13
-rw-r--r--lib/VMCore/Dominators.cpp29
4 files changed, 31 insertions, 28 deletions
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index f0b4672431..0740f729f2 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -23,6 +23,7 @@
#include "llvm/Pass.h"
#include <set>
+#include "llvm/ADT/DenseMap.h"
namespace llvm {
@@ -103,7 +104,7 @@ class DominatorTreeBase : public DominatorBase {
protected:
void reset();
- typedef std::map<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
+ typedef DenseMap<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
DomTreeNodeMapType DomTreeNodes;
DomTreeNode *RootNode;
@@ -120,7 +121,7 @@ protected:
InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
};
- std::map<BasicBlock*, BasicBlock*> IDoms;
+ DenseMap<BasicBlock*, BasicBlock*> IDoms;
// Vertex - Map the DFS number to the BasicBlock*
std::vector<BasicBlock*> Vertex;
@@ -141,8 +142,8 @@ protected:
/// block. This is the same as using operator[] on this class.
///
inline DomTreeNode *getNode(BasicBlock *BB) const {
- DomTreeNodeMapType::const_iterator i = DomTreeNodes.find(BB);
- return (i != DomTreeNodes.end()) ? i->second : 0;
+ DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
+ return I != DomTreeNodes.end() ? I->second : 0;
}
inline DomTreeNode *operator[](BasicBlock *BB) const {
@@ -302,9 +303,9 @@ private:
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;
- }
+ DenseMap<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 091925ecc5..5841da3fcf 100644
--- a/include/llvm/Analysis/PostDominators.h
+++ b/include/llvm/Analysis/PostDominators.h
@@ -45,7 +45,7 @@ private:
void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
inline BasicBlock *getIDom(BasicBlock *BB) const {
- std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
+ DenseMap<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
return I != IDoms.end() ? I->second : 0;
}
};
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index 1188cff030..e3169a5c83 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -28,7 +28,7 @@ static RegisterPass<PostDominatorTree>
F("postdomtree", "Post-Dominator Tree Construction", true);
unsigned PostDominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo,
- unsigned N) {
+ unsigned N) {
std::vector<std::pair<BasicBlock *, InfoRec *> > workStack;
std::set<BasicBlock *> visited;
workStack.push_back(std::make_pair(V, &VInfo));
@@ -111,13 +111,18 @@ 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.
- for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
- if (succ_begin(I) == succ_end(I)) {
- Instruction *Insn = I->getTerminator();
+ for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
+ TerminatorInst *Insn = I->getTerminator();
+ if (Insn->getNumSuccessors() == 0) {
// Unreachable block is not a root node.
if (!isa<UnreachableInst>(Insn))
Roots.push_back(I);
}
+
+ // Prepopulate maps so that we don't get iterator invalidation issues later.
+ IDoms[I] = 0;
+ DomTreeNodes[I] = 0;
+ }
Vertex.push_back(0);
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 91b422c704..9b36e1de63 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -212,8 +212,7 @@ void DominatorTree::Compress(BasicBlock *VIn) {
std::vector<BasicBlock *> Work;
std::set<BasicBlock *> Visited;
- InfoRec &VInInfo = Info[VIn];
- BasicBlock *VInAncestor = VInInfo.Ancestor;
+ BasicBlock *VInAncestor = Info[VIn].Ancestor;
InfoRec &VInVAInfo = Info[VInAncestor];
if (VInVAInfo.Ancestor != 0)
@@ -233,7 +232,7 @@ void DominatorTree::Compress(BasicBlock *VIn) {
}
Work.pop_back();
- // Update VINfo based on Ancestor info
+ // Update VInfo based on Ancestor info
if (VAInfo.Ancestor == 0)
continue;
BasicBlock *VAncestorLabel = VAInfo.Label;
@@ -366,17 +365,16 @@ void DominatorTree::calculate(Function& F) {
// 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.
- DomTreeNode *&BBNode = DomTreeNodes[I];
- if (!BBNode) { // Haven't calculated this node yet?
- // Get or calculate the node for the immediate dominator
- DomTreeNode *IDomNode = getNodeForBlock(ImmDom);
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- DomTreeNode *C = new DomTreeNode(I, IDomNode);
- DomTreeNodes[I] = C;
- BBNode = IDomNode->addChild(C);
- }
+ DomTreeNode *BBNode = DomTreeNodes[I];
+ if (BBNode) continue; // Haven't calculated this node yet?
+
+ // Get or calculate the node for the immediate dominator
+ DomTreeNode *IDomNode = getNodeForBlock(ImmDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ DomTreeNode *C = new DomTreeNode(I, IDomNode);
+ DomTreeNodes[I] = IDomNode->addChild(C);
}
// Free temporary memory used to construct idom's
@@ -387,8 +385,7 @@ void DominatorTree::calculate(Function& F) {
updateDFSNumbers();
}
-void DominatorTreeBase::updateDFSNumbers()
-{
+void DominatorTreeBase::updateDFSNumbers() {
int dfsnum = 0;
// Iterate over all nodes in depth first order.
for (unsigned i = 0, e = Roots.size(); i != e; ++i)
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-30 02:29:52 +0000