Remember the set of leaders. Also compute on demand and cache the equiv

class for each leader.   Finally, rename Elem2ECLeaderMap to Elem2LeaderMap
(most of the changed lines are only due to the latter).


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

2 files changed, 104 insertions, 64 deletions

diff --git a/include/Support/EquivalenceClasses.h b/include/Support/EquivalenceClasses.h
index 46e626b69b..127183614b 100644
--- a/include/Support/EquivalenceClasses.h
+++ b/include/Support/EquivalenceClasses.h
@@ -18,6 +18,7 @@
 #define SUPPORT_EQUIVALENCECLASSES_H
 
 #include <map>
+#include <set>
 #include <vector>
 
 namespace llvm {
@@ -26,69 +27,88 @@ template <class ElemTy>
 class EquivalenceClasses {
   // Maps each element to the element that is the leader of its 
   // equivalence class.
-  std::map<ElemTy, ElemTy> Elem2ECLeaderMap;
+  std::map<ElemTy, ElemTy> Elem2LeaderMap;
   
+  // Maintains the set of leaders
+  std::set<ElemTy> LeaderSet;
+
+  // Caches the equivalence class for each leader
+  std::map<ElemTy, std::set<ElemTy> > LeaderToEqClassMap;
+
   // Make Element2 the leader of the union of classes Element1 and Element2
   // Element1 and Element2 are presumed to be leaders of their respective
   // equivalence classes.
   void attach(ElemTy Element1, ElemTy Element2) {
     for (typename std::map<ElemTy, ElemTy>::iterator ElemI = 
-	   Elem2ECLeaderMap.begin(), ElemE = Elem2ECLeaderMap.end(); 
+	   Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end(); 
 	 ElemI != ElemE; ++ElemI) {
       if (ElemI->second == Element1)
-	Elem2ECLeaderMap[ElemI->first] = Element2;
+	Elem2LeaderMap[ElemI->first] = Element2;
     }
   }
 
 public:
-  
-  void addElement (ElemTy NewElement) {
-    if (Elem2ECLeaderMap.find(NewElement) == Elem2ECLeaderMap.end())
-      Elem2ECLeaderMap[NewElement] = NewElement;
+  // If an element has not yet in any class, make it a separate new class.
+  // Return the leader of the class containing the element.
+  ElemTy addElement (ElemTy NewElement) {
+    typename std::map<ElemTy, ElemTy>::iterator ElemI = 
+      Elem2LeaderMap.find(NewElement);
+    if (ElemI == Elem2LeaderMap.end()) {
+      Elem2LeaderMap[NewElement] = NewElement;
+      LeaderSet.insert(NewElement);
+      return NewElement;
+    }
+    else
+      return ElemI->second;
   }
   
-  ElemTy findClass(ElemTy Element) {
-    if (Elem2ECLeaderMap.find(Element) == Elem2ECLeaderMap.end())
-      return 0;
-    else 
-      return Elem2ECLeaderMap[Element];
+  ElemTy findClass(ElemTy Element) const {
+    typename std::map<ElemTy, ElemTy>::const_iterator I =
+      Elem2LeaderMap.find(Element);
+    return (I == Elem2LeaderMap.end())? (ElemTy) 0 : I->second;
   }
 
   /// Attach the set with Element1 to the set with Element2 adding Element1 and
   /// Element2 to the set of equivalence classes if they are not there already.
   /// Implication: Make Element1 the element in the smaller set.
+  /// Take Leader[Element1] out of the set of leaders.
   void unionSetsWith(ElemTy Element1, ElemTy Element2) {
     // If either Element1 or Element2 does not already exist, include it
-    if (Elem2ECLeaderMap.find(Element1) == Elem2ECLeaderMap.end())
-      Elem2ECLeaderMap[Element1] = Element1;
-    if (Elem2ECLeaderMap.find(Element2) == Elem2ECLeaderMap.end())
-      Elem2ECLeaderMap[Element2] = Element2;
-
-    attach(Elem2ECLeaderMap[Element1], Elem2ECLeaderMap[Element2]);
+    const ElemTy& leader1 = addElement(Element1);
+    const ElemTy& leader2 = addElement(Element2);
+    assert(leader1 != (ElemTy) 0 && leader2 != (ElemTy) 0);
+    if (leader1 != leader2) {
+      attach(leader1, leader2);
+      LeaderSet.erase(leader1);
+    }
   }
   
-  // Returns a vector containing all the elements in the equivalent class
+  // Returns a vector containing all the elements in the equivalence class
   // including Element1
-  std::vector<ElemTy> getEqClass(ElemTy Element1) {
-    std::vector<ElemTy> EqClass;
+  const std::set<ElemTy> & getEqClass(ElemTy Element1) {
+    assert(Elem2LeaderMap.find(Element1) != Elem2LeaderMap.end());
+    const ElemTy classLeader = Elem2LeaderMap[Element1];
     
-    if (Elem2ECLeaderMap.find(EqClass) == Elem2ECLeaderMap.end())
-      return EqClass;
+    std::set<ElemTy> & EqClass = LeaderToEqClassMap[classLeader];
     
-    ElemTy classLeader = Elem2ECLeaderMap[Element1];
-    for (typename std::map<ElemTy, ElemTy>::iterator ElemI = 
-	   Elem2ECLeaderMap.begin(), ElemE = Elem2ECLeaderMap.end(); 
-	 ElemI != ElemE; ++ElemI) {
-      if (ElemI->second == classLeader)
-	EqClass.push_back(ElemI->first);
+    // If the EqClass vector is empty, it has not been computed yet: do it now
+    if (EqClass.empty()) {
+      for (typename std::map<ElemTy, ElemTy>::iterator
+             ElemI = Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end(); 
+           ElemI != ElemE; ++ElemI)
+        if (ElemI->second == classLeader)
+          EqClass.insert(ElemI->first);
+      assert(! EqClass.empty());        // must at least include the leader
     }
     
     return EqClass;
   }
 
-  std::map<ElemTy, ElemTy>& getLeaderMap() {
-    return Elem2ECLeaderMap ;
-  }
+        std::set<ElemTy>& getLeaderSet()       { return LeaderSet; }
+  const std::set<ElemTy>& getLeaderSet() const { return LeaderSet; }
+
+        std::map<ElemTy, ElemTy>& getLeaderMap()       { return Elem2LeaderMap;}
+  const std::map<ElemTy, ElemTy>& getLeaderMap() const { return Elem2LeaderMap;}
 };
 
 } // End llvm namespace
diff --git a/include/llvm/ADT/EquivalenceClasses.h b/include/llvm/ADT/EquivalenceClasses.h
index 46e626b69b..127183614b 100644
--- a/include/llvm/ADT/EquivalenceClasses.h
+++ b/include/llvm/ADT/EquivalenceClasses.h
@@ -18,6 +18,7 @@
 #define SUPPORT_EQUIVALENCECLASSES_H
 
 #include <map>
+#include <set>
 #include <vector>
 
 namespace llvm {
@@ -26,69 +27,88 @@ template <class ElemTy>
 class EquivalenceClasses {
   // Maps each element to the element that is the leader of its 
   // equivalence class.
-  std::map<ElemTy, ElemTy> Elem2ECLeaderMap;
+  std::map<ElemTy, ElemTy> Elem2LeaderMap;
   
+  // Maintains the set of leaders
+  std::set<ElemTy> LeaderSet;
+
+  // Caches the equivalence class for each leader
+  std::map<ElemTy, std::set<ElemTy> > LeaderToEqClassMap;
+
   // Make Element2 the leader of the union of classes Element1 and Element2
   // Element1 and Element2 are presumed to be leaders of their respective
   // equivalence classes.
   void attach(ElemTy Element1, ElemTy Element2) {
     for (typename std::map<ElemTy, ElemTy>::iterator ElemI = 
-	   Elem2ECLeaderMap.begin(), ElemE = Elem2ECLeaderMap.end(); 
+	   Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end(); 
 	 ElemI != ElemE; ++ElemI) {
       if (ElemI->second == Element1)
-	Elem2ECLeaderMap[ElemI->first] = Element2;
+	Elem2LeaderMap[ElemI->first] = Element2;
     }
   }
 
 public:
-  
-  void addElement (ElemTy NewElement) {
-    if (Elem2ECLeaderMap.find(NewElement) == Elem2ECLeaderMap.end())
-      Elem2ECLeaderMap[NewElement] = NewElement;
+  // If an element has not yet in any class, make it a separate new class.
+  // Return the leader of the class containing the element.
+  ElemTy addElement (ElemTy NewElement) {
+    typename std::map<ElemTy, ElemTy>::iterator ElemI = 
+      Elem2LeaderMap.find(NewElement);
+    if (ElemI == Elem2LeaderMap.end()) {
+      Elem2LeaderMap[NewElement] = NewElement;
+      LeaderSet.insert(NewElement);
+      return NewElement;
+    }
+    else
+      return ElemI->second;
   }
   
-  ElemTy findClass(ElemTy Element) {
-    if (Elem2ECLeaderMap.find(Element) == Elem2ECLeaderMap.end())
-      return 0;
-    else 
-      return Elem2ECLeaderMap[Element];
+  ElemTy findClass(ElemTy Element) const {
+    typename std::map<ElemTy, ElemTy>::const_iterator I =
+      Elem2LeaderMap.find(Element);
+    return (I == Elem2LeaderMap.end())? (ElemTy) 0 : I->second;
   }
 
   /// Attach the set with Element1 to the set with Element2 adding Element1 and
   /// Element2 to the set of equivalence classes if they are not there already.
   /// Implication: Make Element1 the element in the smaller set.
+  /// Take Leader[Element1] out of the set of leaders.
   void unionSetsWith(ElemTy Element1, ElemTy Element2) {
     // If either Element1 or Element2 does not already exist, include it
-    if (Elem2ECLeaderMap.find(Element1) == Elem2ECLeaderMap.end())
-      Elem2ECLeaderMap[Element1] = Element1;
-    if (Elem2ECLeaderMap.find(Element2) == Elem2ECLeaderMap.end())
-      Elem2ECLeaderMap[Element2] = Element2;
-
-    attach(Elem2ECLeaderMap[Element1], Elem2ECLeaderMap[Element2]);
+    const ElemTy& leader1 = addElement(Element1);
+    const ElemTy& leader2 = addElement(Element2);
+    assert(leader1 != (ElemTy) 0 && leader2 != (ElemTy) 0);
+    if (leader1 != leader2) {
+      attach(leader1, leader2);
+      LeaderSet.erase(leader1);
+    }
   }
   
-  // Returns a vector containing all the elements in the equivalent class
+  // Returns a vector containing all the elements in the equivalence class
   // including Element1
-  std::vector<ElemTy> getEqClass(ElemTy Element1) {
-    std::vector<ElemTy> EqClass;
+  const std::set<ElemTy> & getEqClass(ElemTy Element1) {
+    assert(Elem2LeaderMap.find(Element1) != Elem2LeaderMap.end());
+    const ElemTy classLeader = Elem2LeaderMap[Element1];
     
-    if (Elem2ECLeaderMap.find(EqClass) == Elem2ECLeaderMap.end())
-      return EqClass;
+    std::set<ElemTy> & EqClass = LeaderToEqClassMap[classLeader];
     
-    ElemTy classLeader = Elem2ECLeaderMap[Element1];
-    for (typename std::map<ElemTy, ElemTy>::iterator ElemI = 
-	   Elem2ECLeaderMap.begin(), ElemE = Elem2ECLeaderMap.end(); 
-	 ElemI != ElemE; ++ElemI) {
-      if (ElemI->second == classLeader)
-	EqClass.push_back(ElemI->first);
+    // If the EqClass vector is empty, it has not been computed yet: do it now
+    if (EqClass.empty()) {
+      for (typename std::map<ElemTy, ElemTy>::iterator
+             ElemI = Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end(); 
+           ElemI != ElemE; ++ElemI)
+        if (ElemI->second == classLeader)
+          EqClass.insert(ElemI->first);
+      assert(! EqClass.empty());        // must at least include the leader
     }
     
     return EqClass;
   }
 
-  std::map<ElemTy, ElemTy>& getLeaderMap() {
-    return Elem2ECLeaderMap ;
-  }
+        std::set<ElemTy>& getLeaderSet()       { return LeaderSet; }
+  const std::set<ElemTy>& getLeaderSet() const { return LeaderSet; }
+
+        std::map<ElemTy, ElemTy>& getLeaderMap()       { return Elem2LeaderMap;}
+  const std::map<ElemTy, ElemTy>& getLeaderMap() const { return Elem2LeaderMap;}
 };
 
 } // End llvm namespace