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 IntegersSubsetTy = IntegersSubset,
  31           class IntTy = IntItem>
  32 class IntegersSubsetMapping {
  33 public:
  34
  35   typedef IntRange<IntTy> RangeTy;
  36
  37   struct RangeEx : public RangeTy {
  38     RangeEx() : Weight(1) {}
  39     RangeEx(const RangeTy &R) : RangeTy(R), Weight(1) {}
  40     RangeEx(const IntTy &C) : RangeTy(C), Weight(1) {}
  41     RangeEx(const IntTy &L, const IntTy &H) : RangeTy(L, H), Weight(1) {}
  42     RangeEx(const IntTy &L, const IntTy &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   typedef std::list<RangeTy> RangesCollection;
  56   typedef typename RangesCollection::iterator RangesCollectionIt;
  57
  58   typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
  59   typedef typename CRSMap::iterator CRSMapIt;
  60
  61   struct ClustersCmp {
  62     bool operator()(const Cluster &C1, const Cluster &C2) {
  63       return C1.first < C2.first;
  64     }
  65   };
  66
  67   CaseItems Items;
  68   bool Sorted;
  69
  70   bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
  71     return LItem->first.getHigh() >= RItem->first.getLow();
  72   }
  73
  74   bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
  75     if (LItem->second != RItem->second) {
  76       assert(!isIntersected(LItem, RItem) &&
  77              "Intersected items with different successors!");
  78       return false;
  79     }
  80     APInt RLow = RItem->first.getLow();
  81     if (RLow != APInt::getNullValue(RLow.getBitWidth()))
  82       --RLow;
  83     return LItem->first.getHigh() >= RLow;
  84   }
  85
  86   void sort() {
  87     if (!Sorted) {
  88       std::sort(Items.begin(), Items.end(), ClustersCmp());
  89       Sorted = true;
  90     }
  91   }
  92
  93 public:
  94
  95   // Don't public CaseItems itself. Don't allow edit the Items directly.
  96   // Just present the user way to iterate over the internal collection
  97   // sharing iterator, begin() and end(). Editing should be controlled by
  98   // factory.
  99   typedef CaseItemIt RangeIterator;
 100
 101   typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
 102   typedef std::list<Case> Cases;
 103
 104   IntegersSubsetMapping() {
 105     Items.reserve(32);
 106     Sorted = false;
 107   }
 108
 109   bool verify(RangeIterator& errItem) {
 110     if (Items.empty())
 111       return true;
 112     sort();
 113     for (CaseItemIt i = Items.begin(), j = i+1, e = Items.end();
 114          j != e; i = j++) {
 115       if (isIntersected(j, i) && j->second != i->second) {
 116         errItem = j;
 117         return false;
 118       }
 119     }
 120     return true;
 121   }
 122
 123   void optimize() {
 124     if (Items.size() < 2)
 125       return;
 126     sort();
 127     CaseItems OldItems = Items;
 128     Items.clear();
 129     const IntTy *Low = &OldItems.begin()->first.getLow();
 130     const IntTy *High = &OldItems.begin()->first.getHigh();
 131     unsigned Weight = 1;
 132     SuccessorClass *Successor = OldItems.begin()->second;
 133     for (CaseItemIt i = OldItems.begin(), j = i+1, e = OldItems.end();
 134         j != e; i = j++) {
 135       if (isJoinable(i, j)) {
 136         const IntTy *CurHigh = &j->first.getHigh();
 137         ++Weight;
 138         if (*CurHigh > *High)
 139           High = CurHigh;
 140       } else {
 141         RangeEx R(*Low, *High, Weight);
 142         add(R, Successor);
 143         Low = &j->first.getLow();
 144         High = &j->first.getHigh();
 145         Weight = 1;
 146         Successor = j->second;
 147       }
 148     }
 149     RangeEx R(*Low, *High, Weight);
 150     add(R, Successor);
 151     // We recollected the Items, but we kept it sorted.
 152     Sorted = true;
 153   }
 154
 155   /// Adds a constant value.
 156   void add(const IntTy &C, SuccessorClass *S = 0) {
 157     RangeTy R(C);
 158     add(R, S);
 159   }
 160
 161   /// Adds a range.
 162   void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
 163     RangeTy R(Low, High);
 164     add(R, S);
 165   }
 166   void add(const RangeTy &R, SuccessorClass *S = 0) {
 167     RangeEx REx = R;
 168     add(REx, S);
 169   }
 170   void add(const RangeEx &R, SuccessorClass *S = 0) {
 171     Items.push_back(std::make_pair(R, S));
 172     Sorted = false;
 173   }
 174
 175   /// Adds all ranges and values from given ranges set to the current
 176   /// CRSBuilder object.
 177   void add(const IntegersSubset &CRS, SuccessorClass *S = 0) {
 178     for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
 179       RangeTy R = CRS.getItem(i);
 180       add(R, S);
 181     }
 182   }
 183
 184   /// Removes items from set.
 185   void removeItem(RangeIterator i) { Items.erase(i); }
 186
 187   /// Builds the finalized case objects.
 188   void getCases(Cases& TheCases) {
 189     CRSMap TheCRSMap;
 190     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 191       TheCRSMap[i->second].push_back(i->first);
 192     for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
 193       TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
 194   }
 195
 196   /// Builds the finalized case objects ignoring successor values, as though
 197   /// all ranges belongs to the same successor.
 198   IntegersSubset getCase() {
 199     RangesCollection Ranges;
 200     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 201       Ranges.push_back(i->first);
 202     return IntegersSubsetTy(Ranges);
 203   }
 204
 205   /// Returns true if there is no ranges and values inside.
 206   bool empty() const { return Items.empty(); }
 207
 208   RangeIterator begin() { return Items.begin(); }
 209   RangeIterator end() { return Items.end(); }
 210 };
 211
 212 class BasicBlock;
 213 typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
 214
 215 }
 216
 217 #endif /* CRSBUILDER_H_ */