Reverted r156659, due to probable performance regressions, DenseMap should be used here:

  IntegersSubsetMapping
  - Replaced type of Items field from std::list with std::map. In neares future I'll test it with DenseMap and do the correspond replacement
    if possible.



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

1 files changed, 30 insertions, 4 deletions

diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h
index 667980296d..7ba3ba1798 100644
--- a/include/llvm/Support/IntegersSubsetMapping.h
+++ b/include/llvm/Support/IntegersSubsetMapping.h
@@ -58,15 +58,22 @@ public:
   
 protected:
 
-  typedef std::map<RangeEx, SuccessorClass*> CaseItems;
+  typedef std::list<Cluster> CaseItems;
   typedef typename CaseItems::iterator CaseItemIt;
   typedef typename CaseItems::const_iterator CaseItemConstIt;
   
   // TODO: Change unclean CRS prefixes to SubsetMap for example.
   typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
   typedef typename CRSMap::iterator CRSMapIt;
+
+  struct ClustersCmp {
+    bool operator()(const Cluster &C1, const Cluster &C2) {
+      return C1.first < C2.first;
+    }
+  };
   
   CaseItems Items;
+  bool Sorted;
   bool SingleNumbersOnly;
   
   bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
@@ -85,6 +92,18 @@ protected:
     return LItem->first.getHigh() >= RLow;
   }
   
+  void sort() {
+    if (!Sorted) {
+      std::vector<Cluster> clustersVector;
+      clustersVector.reserve(Items.size());
+      clustersVector.insert(clustersVector.begin(), Items.begin(), Items.end());
+      std::sort(clustersVector.begin(), clustersVector.end(), ClustersCmp());
+      Items.clear();
+      Items.insert(Items.begin(), clustersVector.begin(), clustersVector.end());
+      Sorted = true;
+    }
+  }
+  
   enum DiffProcessState {
     L_OPENED,
     INTERSECT_OPENED,
@@ -282,7 +301,10 @@ public:
   typedef std::list<Case> Cases;
   typedef typename Cases::iterator CasesIt;
   
-  IntegersSubsetMapping() : SingleNumbersOnly(true) {}
+  IntegersSubsetMapping() {
+    Sorted = false;
+    SingleNumbersOnly = true;
+  }
   
   bool verify() {
     RangeIterator DummyErrItem;
@@ -292,6 +314,7 @@ public:
   bool verify(RangeIterator& errItem) {
     if (Items.empty())
       return true;
+    sort();
     for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
          j != e; i = j++) {
       if (isIntersected(i, j) && i->second != j->second) {
@@ -332,6 +355,7 @@ public:
   void optimize() {
     if (Items.size() < 2)
       return;
+    sort();
     CaseItems OldItems = Items;
     Items.clear();
     const IntTy *Low = &OldItems.begin()->first.getLow();
@@ -356,6 +380,8 @@ public:
     }
     RangeEx R(*Low, *High, Weight);
     add(R, Successor);
+    // We recollected the Items, but we kept it sorted.
+    Sorted = true;
   }
   
   /// Adds a constant value.
@@ -374,7 +400,7 @@ public:
     add(REx, S);
   }   
   void add(const RangeEx &R, SuccessorClass *S = 0) {
-    Items.insert(std::make_pair(R, S));
+    Items.push_back(std::make_pair(R, S));
     if (!R.isSingleNumber())
       SingleNumbersOnly = false;
   }  
@@ -389,7 +415,7 @@ public:
   }
   
   void add(self& RHS) {
-    Items.insert(RHS.Items.begin(), RHS.Items.end());
+    Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
     if (!RHS.SingleNumbersOnly)
       SingleNumbersOnly = false;
   }