X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FSupport%2FIntegersSubsetMapping.h;h=cab18dce159b9e6a4375c7db68af931628d0c08b;hb=118f194966d20460c2b1653e06c601e4b66c9b3f;hp=667980296d4a1cf2ea1cdd5f0d5e97f440287e50;hpb=9ccc83e7f70e63b746cbc7eef9fb06022e758677;p=oota-llvm.git

diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h
index 667980296d4..cab18dce159 100644
--- a/include/llvm/Support/IntegersSubsetMapping.h
+++ b/include/llvm/Support/IntegersSubsetMapping.h
@@ -58,16 +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 SingleNumbersOnly;
+  bool Sorted;
   
   bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
     return LItem->first.getHigh() >= RItem->first.getLow();
@@ -85,6 +91,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,
@@ -227,48 +245,6 @@ protected:
     bool isLOpened() { return State == L_OPENED; }
     bool isROpened() { return State == R_OPENED; }
   };
-  
-  void diff_single_numbers(self *LExclude, self *Intersection, self *RExclude,
-                               const self& RHS) {
-    
-    CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
-    CaseItemConstIt el = Items.end(), er = RHS.Items.end();
-    while (L != el && R != er) {
-      const Cluster &LCluster = *L;
-      const RangeEx &LRange = LCluster.first;
-      const Cluster &RCluster = *R;
-      const RangeEx &RRange = RCluster.first;
-      
-      if (LRange.getLow() < RRange.getLow()) {
-        if (LExclude)
-          LExclude->add(LRange.getLow(), LCluster.second);
-        ++L;
-      } else if (LRange.getLow() > RRange.getLow()) {
-        if (RExclude)
-          RExclude->add(RRange.getLow(), RCluster.second);
-        ++R;
-      } else {
-        if (Intersection)
-          Intersection->add(LRange.getLow(), LCluster.second);
-        ++L;
-        ++R;
-      }
-    }
-    
-    if (L != Items.end()) {
-      if (LExclude)
-        do {
-            LExclude->add(L->first, L->second);
-            ++L;
-        } while (L != Items.end());
-    } else if (R != RHS.Items.end()) {
-      if (RExclude)
-        do {
-          RExclude->add(R->first, R->second);
-          ++R;
-        } while (R != RHS.Items.end());
-    }
-  }  
 
 public:
   
@@ -282,7 +258,9 @@ public:
   typedef std::list<Case> Cases;
   typedef typename Cases::iterator CasesIt;
   
-  IntegersSubsetMapping() : SingleNumbersOnly(true) {}
+  IntegersSubsetMapping() {
+    Sorted = false;
+  }
   
   bool verify() {
     RangeIterator DummyErrItem;
@@ -292,6 +270,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 +311,7 @@ public:
   void optimize() {
     if (Items.size() < 2)
       return;
+    sort();
     CaseItems OldItems = Items;
     Items.clear();
     const IntTy *Low = &OldItems.begin()->first.getLow();
@@ -356,6 +336,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,9 +356,8 @@ public:
     add(REx, S);
   }   
   void add(const RangeEx &R, SuccessorClass *S = 0) {
-    Items.insert(std::make_pair(R, S));
-    if (!R.isSingleNumber())
-      SingleNumbersOnly = false;
+    Items.push_back(std::make_pair(R, S));
+    Sorted = false;
   }  
   
   /// Adds all ranges and values from given ranges set to the current
@@ -389,9 +370,7 @@ public:
   }
   
   void add(self& RHS) {
-    Items.insert(RHS.Items.begin(), RHS.Items.end());
-    if (!RHS.SingleNumbersOnly)
-      SingleNumbersOnly = false;
+    Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
   }
   
   void add(self& RHS, SuccessorClass *S) {
@@ -442,16 +421,10 @@ public:
   void diff(self *LExclude, self *Intersection, self *RExclude,
                              const self& RHS) {
     
-    if (SingleNumbersOnly && RHS.SingleNumbersOnly) {
-      diff_single_numbers(LExclude, Intersection, RExclude, RHS);
-      return;
-    }
-    
     DiffStateMachine Machine(LExclude, Intersection, RExclude);
     
     CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
-    CaseItemConstIt el = Items.end(), er = RHS.Items.end();
-    while (L != el && R != er) {
+    while (L != Items.end() && R != RHS.Items.end()) {
       const Cluster &LCluster = *L;
       const RangeEx &LRange = LCluster.first;
       const Cluster &RCluster = *R;
@@ -471,35 +444,6 @@ public:
         continue;
       }
 
-      if (LRange.isSingleNumber() && RRange.isSingleNumber()) {
-        Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
-        Machine.onLRClose(LRange.getLow());
-        ++L;
-        ++R;
-        continue;
-      }
-      
-      if (LRange.isSingleNumber()) {
-        Machine.onLOpen(LRange.getLow(), LCluster.second);
-        Machine.onLClose(LRange.getLow());
-        ++L;
-        while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
-          Machine.onLOpen(LRange.getLow(), LCluster.second);
-          Machine.onLClose(LRange.getLow());
-          ++L;
-        }
-        continue;
-      } else if (RRange.isSingleNumber()) {
-        Machine.onROpen(R->first.getLow(), R->second);
-        Machine.onRClose(R->first.getHigh());
-        ++R;
-        while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
-          Machine.onROpen(R->first.getLow(), R->second);
-          Machine.onRClose(R->first.getHigh());
-          ++R;
-        }
-        continue;
-      } else
       if (LRange.getLow() < RRange.getLow()) {
         // May be opened in previous iteration.
         if (!Machine.isLOpened())