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