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