Author: lattner
Date: Sat Aug 4 18:48:07 2007
New Revision: 40826
URL: http://llvm.org/viewvc/llvm-project?rev=40826&view=rev
Log:
switch the DomTreeNodes and IDoms maps in idom/postidom to a
DenseMap instead of an std::map. This speeds up postdomtree
by about 25% and domtree by about 23%. It also speeds up clients,
for example, domfrontier by 11%, mem2reg by 4% and ADCE by 6%.
Modified:
llvm/trunk/include/llvm/Analysis/Dominators.h
llvm/trunk/include/llvm/Analysis/PostDominators.h
llvm/trunk/lib/Analysis/PostDominators.cpp
llvm/trunk/lib/VMCore/Dominators.cpp
Modified: llvm/trunk/include/llvm/Analysis/Dominators.h
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/Dominators.h?rev=40826&r1=40825&r2=40826&view=diff
==============================================================================
--- llvm/trunk/include/llvm/Analysis/Dominators.h (original)
+++ llvm/trunk/include/llvm/Analysis/Dominators.h Sat Aug 4 18:48:07 2007
@@ -23,6 +23,7 @@
#include "llvm/Pass.h"
#include <set>
+#include "llvm/ADT/DenseMap.h"
namespace llvm {
@@ -103,7 +104,7 @@
protected:
void reset();
- typedef std::map<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
+ typedef DenseMap<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
DomTreeNodeMapType DomTreeNodes;
DomTreeNode *RootNode;
@@ -120,7 +121,7 @@
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 @@
/// 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 @@
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;
+ }
};
//===-------------------------------------
Modified: llvm/trunk/include/llvm/Analysis/PostDominators.h
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Analysis/PostDominators.h?rev=40826&r1=40825&r2=40826&view=diff
==============================================================================
--- llvm/trunk/include/llvm/Analysis/PostDominators.h (original)
+++ llvm/trunk/include/llvm/Analysis/PostDominators.h Sat Aug 4 18:48:07 2007
@@ -45,7 +45,7 @@
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;
}
};
Modified: llvm/trunk/lib/Analysis/PostDominators.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/PostDominators.cpp?rev=40826&r1=40825&r2=40826&view=diff
==============================================================================
--- llvm/trunk/lib/Analysis/PostDominators.cpp (original)
+++ llvm/trunk/lib/Analysis/PostDominators.cpp Sat Aug 4 18:48:07 2007
@@ -28,7 +28,7 @@
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 @@
// 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);
Modified: llvm/trunk/lib/VMCore/Dominators.cpp
URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/VMCore/Dominators.cpp?rev=40826&r1=40825&r2=40826&view=diff
==============================================================================
--- llvm/trunk/lib/VMCore/Dominators.cpp (original)
+++ llvm/trunk/lib/VMCore/Dominators.cpp Sat Aug 4 18:48:07 2007
@@ -212,8 +212,7 @@
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 @@
}
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 @@
// 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 @@
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)
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
