X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FSupport%2FIntegersSubsetMapping.h;h=7635d5e9122160c575078604ce599b4f5dcb582a;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=458adbe22231380232154c31368a003ee929f25d;hpb=181e0bdafaf33524a9a7f082caf5459615f4ab30;p=oota-llvm.git

diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h
index 458adbe2223..7635d5e9122 100644
--- a/include/llvm/Support/IntegersSubsetMapping.h
+++ b/include/llvm/Support/IntegersSubsetMapping.h
@@ -42,6 +42,7 @@ public:
   struct RangeEx : public RangeTy {
     RangeEx() : Weight(1) {}
     RangeEx(const RangeTy &R) : RangeTy(R), Weight(1) {}
+    RangeEx(const RangeTy &R, unsigned W) : RangeTy(R), Weight(W) {}
     RangeEx(const IntTy &C) : RangeTy(C), Weight(1) {}
     RangeEx(const IntTy &L, const IntTy &H) : RangeTy(L, H), Weight(1) {}
     RangeEx(const IntTy &L, const IntTy &H, unsigned W) :
@@ -74,7 +75,6 @@ protected:
   
   CaseItems Items;
   bool Sorted;
-  bool SingleNumbersOnly;
   
   bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
     return LItem->first.getHigh() >= RItem->first.getLow();
@@ -214,7 +214,7 @@ protected:
       }
     }
     
-    void onRLOpen(const IntTy &Pt,
+    void onLROpen(const IntTy &Pt,
                   SuccessorClass *LS,
                   SuccessorClass *RS) {
       switch (State) {
@@ -230,7 +230,7 @@ protected:
       OpenPt = Pt;        
     }
     
-    void onRLClose(const IntTy &Pt) {
+    void onLRClose(const IntTy &Pt) {
       switch (State) {
       case INTERSECT_OPENED:
         if (IntersectionMapping)
@@ -246,48 +246,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:
   
@@ -299,10 +257,15 @@ public:
   
   typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
   typedef std::list<Case> Cases;
+  typedef typename Cases::iterator CasesIt;
   
   IntegersSubsetMapping() {
     Sorted = false;
-    SingleNumbersOnly = true;
+  }
+  
+  bool verify() {
+    RangeIterator DummyErrItem;
+    return verify(DummyErrItem);
   }
   
   bool verify(RangeIterator& errItem) {
@@ -318,6 +281,33 @@ public:
     }
     return true;
   }
+
+  bool isOverlapped(self &RHS) {
+    if (Items.empty() || RHS.empty())
+      return true;
+    
+    for (CaseItemIt L = Items.begin(), R = RHS.Items.begin(),
+         el = Items.end(), er = RHS.Items.end(); L != el && R != er;) {
+      
+      const RangeTy &LRange = L->first;
+      const RangeTy &RRange = R->first;
+      
+      if (LRange.getLow() > RRange.getLow()) {
+        if (RRange.isSingleNumber() || LRange.getLow() > RRange.getHigh())
+          ++R;
+        else
+          return true;
+      } else if (LRange.getLow() < RRange.getLow()) {
+        if (LRange.isSingleNumber() || LRange.getHigh() < RRange.getLow())
+          ++L;
+        else
+          return true;
+      } else // iRange.getLow() == jRange.getLow() 
+        return true;
+    }
+    return false;
+  }
+   
   
   void optimize() {
     if (Items.size() < 2)
@@ -327,13 +317,13 @@ public:
     Items.clear();
     const IntTy *Low = &OldItems.begin()->first.getLow();
     const IntTy *High = &OldItems.begin()->first.getHigh();
-    unsigned Weight = 1;
+    unsigned Weight = OldItems.begin()->first.Weight;
     SuccessorClass *Successor = OldItems.begin()->second;
     for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
          j != e; i = j++) {
       if (isJoinable(i, j)) {
         const IntTy *CurHigh = &j->first.getHigh();
-        ++Weight;
+        Weight += j->first.Weight;
         if (*CurHigh > *High)
           High = CurHigh;
       } else {
@@ -341,7 +331,7 @@ public:
         add(R, Successor);
         Low = &j->first.getLow();
         High = &j->first.getHigh(); 
-        Weight = 1;
+        Weight = j->first.Weight;
         Successor = j->second;
       }
     }
@@ -368,25 +358,34 @@ public:
   }   
   void add(const RangeEx &R, SuccessorClass *S = 0) {
     Items.push_back(std::make_pair(R, S));
-    if (!R.isSingleNumber())
-      SingleNumbersOnly = false;
+    Sorted = false;
   }  
   
   /// Adds all ranges and values from given ranges set to the current
   /// mapping.
-  void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
+  void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0,
+           unsigned Weight = 0) {
+    unsigned ItemWeight = 1;
+    if (Weight)
+      // Weight is associated with CRS, for now we perform a division to
+      // get the weight for each item.
+      ItemWeight = Weight / CRS.getNumItems();
     for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
       RangeTy R = CRS.getItem(i);
-      add(R, S);
+      RangeEx REx(R, ItemWeight);
+      add(REx, S);
     }
   }
   
   void add(self& RHS) {
     Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
-    if (!RHS.SingleNumbersOnly)
-      SingleNumbersOnly = false;
   }
   
+  void add(self& RHS, SuccessorClass *S) {
+    for (CaseItemIt i = RHS.Items.begin(), e = RHS.Items.end(); i != e; ++i)
+      add(i->first, S);
+  }  
+  
   void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
     for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
       add(*i, S);
@@ -395,6 +394,34 @@ public:
   /// Removes items from set.
   void removeItem(RangeIterator i) { Items.erase(i); }
   
+  /// Moves whole case from current mapping to the NewMapping object.
+  void detachCase(self& NewMapping, SuccessorClass *Succ) {
+    for (CaseItemIt i = Items.begin(); i != Items.end();)
+      if (i->second == Succ) {
+        NewMapping.add(i->first, i->second);
+        Items.erase(i++);
+      } else
+        ++i;
+  }
+  
+  /// Removes all clusters for given successor.
+  void removeCase(SuccessorClass *Succ) {
+    for (CaseItemIt i = Items.begin(); i != Items.end();)
+      if (i->second == Succ) {
+        Items.erase(i++);
+      } else
+        ++i;
+  }  
+  
+  /// Find successor that satisfies given value.
+  SuccessorClass *findSuccessor(const IntTy& Val) {
+    for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) {
+      if (i->first.isInRange(Val))
+        return i->second;
+    }
+    return 0;
+  }  
+  
   /// Calculates the difference between this mapping and RHS.
   /// THIS without RHS is placed into LExclude,
   /// RHS without THIS is placed into RExclude,
@@ -402,16 +429,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;
@@ -431,35 +452,6 @@ public:
         continue;
       }
 
-      if (LRange.isSingleNumber() && RRange.isSingleNumber()) {
-        Machine.onRLOpen(LRange.getLow(), LCluster.second, RCluster.second);
-        Machine.onRLClose(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())
@@ -472,7 +464,7 @@ public:
         Machine.onLOpen(LRange.getLow(), LCluster.second);
       }
       else
-        Machine.onRLOpen(LRange.getLow(), LCluster.second, RCluster.second);
+        Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
       
       if (LRange.getHigh() < RRange.getHigh()) {
         Machine.onLClose(LRange.getHigh());
@@ -493,7 +485,7 @@ public:
         }
       }
       else {
-        Machine.onRLClose(LRange.getHigh());
+        Machine.onLRClose(LRange.getHigh());
         ++L;
         ++R;
       }
@@ -523,7 +515,20 @@ public:
   }  
   
   /// Builds the finalized case objects.
-  void getCases(Cases& TheCases) {
+  void getCases(Cases& TheCases, bool PreventMerging = false) {
+    //FIXME: PreventMerging is a temporary parameter.
+    //Currently a set of passes is still knows nothing about
+    //switches with case ranges, and if these passes meet switch
+    //with complex case that crashs the application.
+    if (PreventMerging) {
+      for (RangeIterator i = this->begin(); i != this->end(); ++i) {
+        RangesCollection SingleRange;
+        SingleRange.push_back(i->first);
+        TheCases.push_back(std::make_pair(i->second,
+                                          IntegersSubsetTy(SingleRange)));
+      }
+      return;
+    }
     CRSMap TheCRSMap;
     for (RangeIterator i = this->begin(); i != this->end(); ++i)
       TheCRSMap[i->second].push_back(i->first);
@@ -540,6 +545,22 @@ public:
     return IntegersSubsetTy(Ranges);
   }  
   
+  /// Returns pointer to value of case if it is single-numbered or 0
+  /// in another case.
+  const IntTy* getCaseSingleNumber(SuccessorClass *Succ) {
+    const IntTy* Res = 0;
+    for (CaseItemIt i = Items.begin(); i != Items.end(); ++i)
+      if (i->second == Succ) {
+        if (!i->first.isSingleNumber())
+          return 0;
+        if (Res)
+          return 0;
+        else 
+          Res = &(i->first.getLow());
+      }
+    return Res;
+  }  
+  
   /// Returns true if there is no ranges and values inside.
   bool empty() const { return Items.empty(); }