Factor the code for collecting IV users out of LSR into an IVUsers class,

[oota-llvm.git] / include / llvm / Analysis / Dominators.h

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 86a0457df9fe2ade069b8284c1365e9e66261308..35cdb246518dd2dc67239d5d3a2913938e120bb4 100644 (file)
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -24,7 +24,6 @@
 #include "llvm/Pass.h"
 #include "llvm/BasicBlock.h"
 #include "llvm/Function.h"
-#include "llvm/Instruction.h"
 #include "llvm/Instructions.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/GraphTraits.h"
@@ -94,7 +93,7 @@ public:
   const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
     return Children;
   }
-  
+
   DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
     : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
   
@@ -106,7 +105,29 @@ public:
   size_t getNumChildren() const {
     return Children.size();
   }
+
+  void clearAllChildren() {
+    Children.clear();
+  }
   
+  bool compare(DomTreeNodeBase<NodeT> *Other) {
+    if (getNumChildren() != Other->getNumChildren())
+      return true;
+
+    SmallPtrSet<NodeT *, 4> OtherChildren;
+    for(iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
+      NodeT *Nd = (*I)->getBlock();
+      OtherChildren.insert(Nd);
+    }
+
+    for(iterator I = begin(), E = end(); I != E; ++I) {
+      NodeT *N = (*I)->getBlock();
+      if (OtherChildren.count(N) == 0)
+        return true;
+    }
+    return false;
+  }
+
   void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
     assert(IDom && "No immediate dominator?");
     if (IDom != NewIDom) {
@@ -312,36 +333,26 @@ public:
   /// dominator tree base. Otherwise return true.
   bool compare(DominatorTreeBase &Other) const {
 
-    // Collect nodes.
+    const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
+    if (DomTreeNodes.size() != OtherDomTreeNodes.size())
+      return true;
+
     SmallPtrSet<const NodeT *,4> MyBBs;
     for (typename DomTreeNodeMapType::const_iterator 
            I = this->DomTreeNodes.begin(),
            E = this->DomTreeNodes.end(); I != E; ++I) {
-      const NodeT *BB = I->first;
-      MyBBs.insert(BB);
-    }
-
-    SmallPtrSet<const NodeT *,4> OtherBBs;
-    const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
-    for (typename DomTreeNodeMapType::const_iterator 
-           I = OtherDomTreeNodes.begin(),
-           E = OtherDomTreeNodes.end(); I != E; ++I) {
-      const NodeT *BB = I->first;
-      OtherBBs.insert(BB);
-    }
-
-    if (OtherBBs.size() != MyBBs.size())
-      return true;
+      NodeT *BB = I->first;
+      typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB);
+      if (OI == OtherDomTreeNodes.end())
+        return true;
 
-    // Compare node sets.
-    for (typename SmallPtrSet<const NodeT *,4>::const_iterator I = MyBBs.begin(),
-           E = MyBBs.end(); I != E; ++I) {
-      const NodeT *BB = *I;
-      if (OtherBBs.erase(BB) == 0)
+      DomTreeNodeBase<NodeT>* MyNd = I->second;
+      DomTreeNodeBase<NodeT>* OtherNd = OI->second;
+      
+      if (MyNd->compare(OtherNd))
         return true;
     }
-    if (!OtherBBs.empty())
-      return true;
+
     return false;
   }
 
@@ -708,7 +719,7 @@ public:
   static char ID; // Pass ID, replacement for typeid
   DominatorTreeBase<BasicBlock>* DT;
   
-  DominatorTree() : FunctionPass(intptr_t(&ID)) {
+  DominatorTree() : FunctionPass(&ID) {
     DT = new DominatorTreeBase<BasicBlock>(false);
   }
   
@@ -899,7 +910,7 @@ protected:
   const bool IsPostDominators;
   
 public:
-  DominanceFrontierBase(intptr_t ID, bool isPostDom) 
+  DominanceFrontierBase(void *ID, bool isPostDom) 
     : FunctionPass(ID), IsPostDominators(isPostDom) {}
 
   /// getRoots -  Return the root blocks of the current CFG.  This may include
@@ -1018,7 +1029,7 @@ class DominanceFrontier : public DominanceFrontierBase {
 public:
   static char ID; // Pass ID, replacement for typeid
   DominanceFrontier() : 
-    DominanceFrontierBase(intptr_t(&ID), false) {}
+    DominanceFrontierBase(&ID, false) {}
 
   BasicBlock *getRoot() const {
     assert(Roots.size() == 1 && "Should always have entry node!");