include/llvm/Support/IntegersSubsetMapping.h

   1 //===- CRSBuilder.h - ConstantRangesSet Builder -----------------*- 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 /// CRSBuilder allows to build and parse ConstantRangesSet objects.
  12 /// There is such features like add/remove range, or combine
  13 /// Two ConstantRangesSet object with neighboring ranges merging.
  14 /// Set IsReadonly=true if you want to operate with "const ConstantInt" and
  15 /// "const ConstantRangesSet" objects.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #ifndef CRSBUILDER_H_
  20 #define CRSBUILDER_H_
  21
  22 #include "llvm/Support/IntegersSubset.h"
  23 #include <list>
  24 #include <map>
  25 #include <vector>
  26
  27 namespace llvm {
  28
  29 template <class SuccessorClass>
  30 class IntegersSubsetMapping {
  31 public:
  32
  33   typedef IntegersSubset::Range RangeTy;
  34
  35   struct RangeEx : public RangeTy {
  36     typedef IntegersSubset::Range RangeTy;
  37     RangeEx() : Weight(1) {}
  38     RangeEx(const RangeTy &R) : RangeTy(R.Low, R.High), Weight(1) {}
  39     RangeEx(const IntItem &C) : RangeTy(C), Weight(1) {}
  40     RangeEx(const IntItem &L, const IntItem &H) : RangeTy(L, H), Weight(1) {}
  41     RangeEx(const IntItem &L, const IntItem &H, unsigned W) :
  42       RangeTy(L, H), Weight(W) {}
  43     unsigned Weight;
  44   };
  45
  46   typedef std::pair<RangeEx, SuccessorClass*> Cluster;
  47
  48 protected:
  49
  50   typedef std::vector<Cluster> CaseItems;
  51   typedef typename CaseItems::iterator CaseItemIt;
  52   typedef typename CaseItems::const_iterator CaseItemConstIt;
  53
  54   typedef std::list<RangeTy> RangesCollection;
  55   typedef typename RangesCollection::iterator RangesCollectionIt;
  56
  57   typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
  58   typedef typename CRSMap::iterator CRSMapIt;
  59
  60   struct ClustersCmp {
  61     bool operator()(const Cluster &C1, const Cluster &C2) {
  62       return C1.first < C2.first;
  63     }
  64   };
  65
  66   CaseItems Items;
  67   bool Sorted;
  68
  69   bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
  70     return LItem->first.High >= RItem->first.Low;
  71   }
  72
  73   bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
  74     if (LItem->second != RItem->second) {
  75       assert(!isIntersected(LItem, RItem) &&
  76              "Intersected items with different successors!");
  77       return false;
  78     }
  79     APInt RLow = RItem->first.Low;
  80     if (RLow != APInt::getNullValue(RLow.getBitWidth()))
  81       --RLow;
  82     return LItem->first.High >= RLow;
  83   }
  84
  85   void sort() {
  86     if (!Sorted) {
  87       std::sort(Items.begin(), Items.end(), ClustersCmp());
  88       Sorted = true;
  89     }
  90   }
  91
  92   IntegersSubset getCase(RangesCollection& Src) {
  93     std::vector<Constant*> Elts;
  94     Elts.reserve(Src.size());
  95     for (RangesCollectionIt i = Src.begin(), e = Src.end(); i != e; ++i) {
  96       RangeTy &R = *i;
  97       std::vector<Constant*> r;
  98       if (R.isSingleNumber()) {
  99         r.reserve(2);
 100         // FIXME: Since currently we have ConstantInt based numbers
 101         // use hack-conversion of IntItem to ConstantInt
 102         r.push_back(R.Low.toConstantInt());
 103         r.push_back(R.High.toConstantInt());
 104       } else {
 105         r.reserve(1);
 106         r.push_back(R.Low.toConstantInt());
 107       }
 108       Constant *CV = ConstantVector::get(r);
 109       Elts.push_back(CV);
 110     }
 111     ArrayType *ArrTy =
 112         ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
 113     Constant *Array = ConstantArray::get(ArrTy, Elts);
 114     return IntegersSubset(Array);
 115   }
 116
 117 public:
 118
 119   // Don't public CaseItems itself. Don't allow edit the Items directly.
 120   // Just present the user way to iterate over the internal collection
 121   // sharing iterator, begin() and end(). Editing should be controlled by
 122   // factory.
 123   typedef CaseItemIt RangeIterator;
 124
 125   typedef std::pair<SuccessorClass*, IntegersSubset> Case;
 126   typedef std::list<Case> Cases;
 127
 128   IntegersSubsetMapping() {
 129     Items.reserve(32);
 130     Sorted = false;
 131   }
 132
 133   bool verify(RangeIterator& errItem) {
 134     if (Items.empty())
 135       return true;
 136     sort();
 137     for (CaseItemIt i = Items.begin(), j = i+1, e = Items.end();
 138          j != e; i = j++) {
 139       if (isIntersected(j, i) && j->second != i->second) {
 140         errItem = j;
 141         return false;
 142       }
 143     }
 144     return true;
 145   }
 146
 147   void optimize() {
 148     if (Items.size() < 2)
 149       return;
 150     sort();
 151     CaseItems OldItems = Items;
 152     Items.clear();
 153     IntItem *Low = &OldItems.begin()->first.Low;
 154     IntItem *High = &OldItems.begin()->first.High;
 155     unsigned Weight = 1;
 156     SuccessorClass *Successor = OldItems.begin()->second;
 157     for (CaseItemIt i = OldItems.begin(), j = i+1, e = OldItems.end();
 158         j != e; i = j++) {
 159       if (isJoinable(i, j)) {
 160         IntItem *CurHigh = &j->first.High;
 161         ++Weight;
 162         if (*CurHigh > *High)
 163           High = CurHigh;
 164       } else {
 165         RangeEx R(*Low, *High, Weight);
 166         add(R, Successor);
 167         Low = &j->first.Low;
 168         High = &j->first.High;
 169         Weight = 1;
 170         Successor = j->second;
 171       }
 172     }
 173     RangeEx R(*Low, *High, Weight);
 174     add(R, Successor);
 175     // We recollected the Items, but we kept it sorted.
 176     Sorted = true;
 177   }
 178
 179   /// Adds a constant value.
 180   void add(const IntItem &C, SuccessorClass *S = 0) {
 181     RangeTy R(C);
 182     add(R, S);
 183   }
 184
 185   /// Adds a range.
 186   void add(const IntItem &Low, const IntItem &High, SuccessorClass *S = 0) {
 187     RangeTy R(Low, High);
 188     add(R, S);
 189   }
 190   void add(const RangeTy &R, SuccessorClass *S = 0) {
 191     RangeEx REx = R;
 192     add(REx, S);
 193   }
 194   void add(const RangeEx &R, SuccessorClass *S = 0) {
 195     Items.push_back(std::make_pair(R, S));
 196     Sorted = false;
 197   }
 198
 199   /// Adds all ranges and values from given ranges set to the current
 200   /// CRSBuilder object.
 201   void add(const IntegersSubset &CRS, SuccessorClass *S = 0) {
 202     for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
 203       RangeTy R = CRS.getItem(i);
 204       add(R, S);
 205     }
 206   }
 207
 208   /// Removes items from set.
 209   void removeItem(RangeIterator i) { Items.erase(i); }
 210
 211   /// Builds the finalized case objects.
 212   void getCases(Cases& TheCases) {
 213     CRSMap TheCRSMap;
 214     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 215       TheCRSMap[i->second].push_back(i->first);
 216     for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
 217       TheCases.push_back(std::make_pair(i->first, getCase(i->second)));
 218   }
 219
 220   /// Builds the finalized case objects ignoring successor values, as though
 221   /// all ranges belongs to the same successor.
 222   IntegersSubset getCase() {
 223     RangesCollection Ranges;
 224     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 225       Ranges.push_back(i->first);
 226     return getCase(Ranges);
 227   }
 228
 229   /// Returns true if there is no ranges and values inside.
 230   bool empty() const { return Items.empty(); }
 231
 232   RangeIterator begin() { return Items.begin(); }
 233   RangeIterator end() { return Items.end(); }
 234 };
 235
 236 class BasicBlock;
 237 typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
 238
 239 }
 240
 241 #endif /* CRSBUILDER_H_ */