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%.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40826 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 9 insertions, 8 deletions

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index f0b4672..0740f72 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 091925e..5841da3 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;
   }
 };