include/llvm/Support/IntegersSubsetMapping.h

   1 //===- IntegersSubsetMapping.h - Mapping subset ==> Successor ---*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// @file
  11 /// IntegersSubsetMapping is mapping from A to B, where
  12 /// Items in A is subsets of integers,
  13 /// Items in B some pointers (Successors).
  14 /// If user which to add another subset for successor that is already
  15 /// exists in mapping, IntegersSubsetMapping merges existing subset with
  16 /// added one.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #ifndef CRSBUILDER_H_
  21 #define CRSBUILDER_H_
  22
  23 #include "llvm/Support/IntegersSubset.h"
  24 #include <list>
  25 #include <map>
  26 #include <vector>
  27
  28 namespace llvm {
  29
  30 template <class SuccessorClass,
  31           class IntegersSubsetTy = IntegersSubset,
  32           class IntTy = IntItem>
  33 class IntegersSubsetMapping {
  34 public:
  35
  36   typedef IntRange<IntTy> RangeTy;
  37
  38   struct RangeEx : public RangeTy {
  39     RangeEx() : Weight(1) {}
  40     RangeEx(const RangeTy &R) : RangeTy(R), Weight(1) {}
  41     RangeEx(const IntTy &C) : RangeTy(C), Weight(1) {}
  42     RangeEx(const IntTy &L, const IntTy &H) : RangeTy(L, H), Weight(1) {}
  43     RangeEx(const IntTy &L, const IntTy &H, unsigned W) :
  44       RangeTy(L, H), Weight(W) {}
  45     unsigned Weight;
  46   };
  47
  48   typedef std::pair<RangeEx, SuccessorClass*> Cluster;
  49
  50 protected:
  51
  52   typedef std::list<Cluster> CaseItems;
  53   typedef typename CaseItems::iterator CaseItemIt;
  54   typedef typename CaseItems::const_iterator CaseItemConstIt;
  55
  56   typedef std::list<RangeTy> RangesCollection;
  57   typedef typename RangesCollection::iterator RangesCollectionIt;
  58
  59   // TODO: Change unclean CRS prefixes to SubsetMap for example.
  60   typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
  61   typedef typename CRSMap::iterator CRSMapIt;
  62
  63   struct ClustersCmp {
  64     bool operator()(const Cluster &C1, const Cluster &C2) {
  65       return C1.first < C2.first;
  66     }
  67   };
  68
  69   struct ClusterLefterThan {
  70     bool operator()(const Cluster &C, const RangeTy &R) {
  71       return C.first.getHigh() < R.getLow();
  72     }
  73   };
  74
  75   CaseItems Items;
  76   bool Sorted;
  77
  78   bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
  79     return LItem->first.getHigh() >= RItem->first.getLow();
  80   }
  81
  82   bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
  83     if (LItem->second != RItem->second) {
  84       assert(!isIntersected(LItem, RItem) &&
  85              "Intersected items with different successors!");
  86       return false;
  87     }
  88     APInt RLow = RItem->first.getLow();
  89     if (RLow != APInt::getNullValue(RLow.getBitWidth()))
  90       --RLow;
  91     return LItem->first.getHigh() >= RLow;
  92   }
  93
  94   void sort() {
  95     if (!Sorted) {
  96       std::vector<Cluster> clustersVector;
  97       clustersVector.reserve(Items.size());
  98       clustersVector.insert(clustersVector.begin(), Items.begin(), Items.end());
  99       std::sort(clustersVector.begin(), clustersVector.end(), ClustersCmp());
 100       Items.clear();
 101       Items.insert(Items.begin(), clustersVector.begin(), clustersVector.end());
 102       Sorted = true;
 103     }
 104   }
 105
 106   void exclude(CaseItemIt &beginIt, RangeTy &R) {
 107
 108     std::list<CaseItemIt> ToBeErased;
 109
 110     CaseItemIt endIt = Items.end();
 111     CaseItemIt It =
 112           std::lower_bound(beginIt, Items.end(), R, ClusterLefterThan());
 113
 114     if (It == endIt)
 115       return;
 116
 117     if (It->first.getLow() < R.getLow())
 118       Items.insert(It, std::make_pair(
 119           RangeTy(It->first.getLow(), R.getLow()-1),
 120           It->second));
 121
 122     do
 123     ToBeErased.push_back(It++);
 124     while (It != endIt && It->first.getLow() <= R.getHigh());
 125
 126     beginIt = It;
 127
 128     CaseItemIt &LastRemoved = *(--ToBeErased.end());
 129     if (LastRemoved->first.getHigh() > R.getHigh())
 130       beginIt = Items.insert(LastRemoved, std::make_pair(
 131           RangeTy(R.getHigh() + 1, LastRemoved->first.getHigh()),
 132           LastRemoved->second
 133           ));
 134
 135     for (typename std::list<CaseItemIt>::iterator i = ToBeErased.begin(),
 136          e = ToBeErased.end(); i != e; ++i)
 137       Items.erase(*i);
 138   }
 139
 140 public:
 141
 142   // Don't public CaseItems itself. Don't allow edit the Items directly.
 143   // Just present the user way to iterate over the internal collection
 144   // sharing iterator, begin() and end(). Editing should be controlled by
 145   // factory.
 146   typedef CaseItemIt RangeIterator;
 147
 148   typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
 149   typedef std::list<Case> Cases;
 150
 151   IntegersSubsetMapping() {
 152     Sorted = false;
 153   }
 154
 155   bool verify(RangeIterator& errItem) {
 156     if (Items.empty())
 157       return true;
 158     sort();
 159     for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
 160          j != e; i = j++) {
 161       if (isIntersected(i, j) && i->second != j->second) {
 162         errItem = j;
 163         return false;
 164       }
 165     }
 166     return true;
 167   }
 168
 169   void optimize() {
 170     if (Items.size() < 2)
 171       return;
 172     sort();
 173     CaseItems OldItems = Items;
 174     Items.clear();
 175     const IntTy *Low = &OldItems.begin()->first.getLow();
 176     const IntTy *High = &OldItems.begin()->first.getHigh();
 177     unsigned Weight = 1;
 178     SuccessorClass *Successor = OldItems.begin()->second;
 179     for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
 180          j != e; i = j++) {
 181       if (isJoinable(i, j)) {
 182         const IntTy *CurHigh = &j->first.getHigh();
 183         ++Weight;
 184         if (*CurHigh > *High)
 185           High = CurHigh;
 186       } else {
 187         RangeEx R(*Low, *High, Weight);
 188         add(R, Successor);
 189         Low = &j->first.getLow();
 190         High = &j->first.getHigh();
 191         Weight = 1;
 192         Successor = j->second;
 193       }
 194     }
 195     RangeEx R(*Low, *High, Weight);
 196     add(R, Successor);
 197     // We recollected the Items, but we kept it sorted.
 198     Sorted = true;
 199   }
 200
 201   /// Adds a constant value.
 202   void add(const IntTy &C, SuccessorClass *S = 0) {
 203     RangeTy R(C);
 204     add(R, S);
 205   }
 206
 207   /// Adds a range.
 208   void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
 209     RangeTy R(Low, High);
 210     add(R, S);
 211   }
 212   void add(const RangeTy &R, SuccessorClass *S = 0) {
 213     RangeEx REx = R;
 214     add(REx, S);
 215   }
 216   void add(const RangeEx &R, SuccessorClass *S = 0) {
 217     Items.push_back(std::make_pair(R, S));
 218     Sorted = false;
 219   }
 220
 221   /// Adds all ranges and values from given ranges set to the current
 222   /// mapping.
 223   void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
 224     for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
 225       RangeTy R = CRS.getItem(i);
 226       add(R, S);
 227     }
 228   }
 229
 230   /// Removes items from set.
 231   void removeItem(RangeIterator i) { Items.erase(i); }
 232
 233   // Excludes RHS subset from current mapping. RHS should consists of non
 234   // overlapped ranges only and sorted from left to the right.
 235   // method will have unpredictional behaviour in another case.
 236   void exclude(IntegersSubsetTy &RHS) {
 237     CaseItemIt startIt = begin();
 238     for (unsigned i = 0, e = RHS.getNumItems();
 239          i != e && startIt != end(); ++i) {
 240       RangeTy R = RHS.getItem(i);
 241       exclude(startIt, R);
 242     }
 243   }
 244
 245   /// Builds the finalized case objects.
 246   void getCases(Cases& TheCases) {
 247     CRSMap TheCRSMap;
 248     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 249       TheCRSMap[i->second].push_back(i->first);
 250     for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
 251       TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
 252   }
 253
 254   /// Builds the finalized case objects ignoring successor values, as though
 255   /// all ranges belongs to the same successor.
 256   IntegersSubsetTy getCase() {
 257     RangesCollection Ranges;
 258     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 259       Ranges.push_back(i->first);
 260     return IntegersSubsetTy(Ranges);
 261   }
 262
 263   /// Returns true if there is no ranges and values inside.
 264   bool empty() const { return Items.empty(); }
 265
 266   void clear() {
 267     Items.clear();
 268     // Don't reset Sorted flag:
 269     // 1. For empty mapping it matters nothing.
 270     // 2. After first item will added Sorted flag will cleared.
 271   }
 272
 273   RangeIterator begin() { return Items.begin(); }
 274   RangeIterator end() { return Items.end(); }
 275 };
 276
 277 class BasicBlock;
 278 typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
 279
 280 }
 281
 282 #endif /* CRSBUILDER_H_ */