aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/Support/EquivalenceClasses.h84
-rw-r--r--include/llvm/ADT/EquivalenceClasses.h84
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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-01 20:00:07 +0000