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