Home | History | Annotate | Download | only in Support 
      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 LLVM_SUPPORT_INTEGERSSUBSETMAPPING_H
     21 #define LLVM_SUPPORT_INTEGERSSUBSETMAPPING_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   // FIXME: To much similar iterators typedefs, similar names.
     35   //        - Rename RangeIterator to the cluster iterator.
     36   //        - Remove unused "add" methods.
     37   //        - Class contents needs cleaning.
     38 public:
     39 
     40   typedef IntRange<IntTy> RangeTy;
     41 
     42   struct RangeEx : public RangeTy {
     43     RangeEx() : Weight(1) {}
     44     RangeEx(const RangeTy &R) : RangeTy(R), Weight(1) {}
     45     RangeEx(const RangeTy &R, unsigned W) : RangeTy(R), Weight(W) {}
     46     RangeEx(const IntTy &C) : RangeTy(C), Weight(1) {}
     47     RangeEx(const IntTy &L, const IntTy &H) : RangeTy(L, H), Weight(1) {}
     48     RangeEx(const IntTy &L, const IntTy &H, unsigned W) :
     49       RangeTy(L, H), Weight(W) {}
     50     unsigned Weight;
     51   };
     52 
     53   typedef std::pair<RangeEx, SuccessorClass*> Cluster;
     54 
     55   typedef std::list<RangeTy> RangesCollection;
     56   typedef typename RangesCollection::iterator RangesCollectionIt;
     57   typedef typename RangesCollection::const_iterator RangesCollectionConstIt;
     58   typedef IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> self;
     59 
     60 protected:
     61 
     62   typedef std::list<Cluster> CaseItems;
     63   typedef typename CaseItems::iterator CaseItemIt;
     64   typedef typename CaseItems::const_iterator CaseItemConstIt;
     65 
     66   // TODO: Change unclean CRS prefixes to SubsetMap for example.
     67   typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
     68   typedef typename CRSMap::iterator CRSMapIt;
     69 
     70   struct ClustersCmp {
     71     bool operator()(const Cluster &C1, const Cluster &C2) {
     72       return C1.first < C2.first;
     73     }
     74   };
     75 
     76   CaseItems Items;
     77   bool Sorted;
     78 
     79   bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
     80     return LItem->first.getHigh() >= RItem->first.getLow();
     81   }
     82 
     83   bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
     84     if (LItem->second != RItem->second) {
     85       assert(!isIntersected(LItem, RItem) &&
     86              "Intersected items with different successors!");
     87       return false;
     88     }
     89     APInt RLow = RItem->first.getLow();
     90     if (RLow != APInt::getNullValue(RLow.getBitWidth()))
     91       --RLow;
     92     return LItem->first.getHigh() >= RLow;
     93   }
     94 
     95   void sort() {
     96     if (!Sorted) {
     97       std::vector<Cluster> clustersVector;
     98       clustersVector.reserve(Items.size());
     99       clustersVector.insert(clustersVector.begin(), Items.begin(), Items.end());
    100       std::sort(clustersVector.begin(), clustersVector.end(), ClustersCmp());
    101       Items.clear();
    102       Items.insert(Items.begin(), clustersVector.begin(), clustersVector.end());
    103       Sorted = true;
    104     }
    105   }
    106 
    107   enum DiffProcessState {
    108     L_OPENED,
    109     INTERSECT_OPENED,
    110     R_OPENED,
    111     ALL_IS_CLOSED
    112   };
    113 
    114   class DiffStateMachine {
    115 
    116     DiffProcessState State;
    117     IntTy OpenPt;
    118     SuccessorClass *CurrentLSuccessor;
    119     SuccessorClass *CurrentRSuccessor;
    120 
    121     self *LeftMapping;
    122     self *IntersectionMapping;
    123     self *RightMapping;
    124 
    125   public:
    126 
    127     typedef
    128       IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> MappingTy;
    129 
    130     DiffStateMachine(MappingTy *L,
    131                                  MappingTy *Intersection,
    132                                  MappingTy *R) :
    133                                  State(ALL_IS_CLOSED),
    134                                  LeftMapping(L),
    135                                  IntersectionMapping(Intersection),
    136                                  RightMapping(R)
    137                                  {}
    138 
    139     void onLOpen(const IntTy &Pt, SuccessorClass *S) {
    140       switch (State) {
    141       case R_OPENED:
    142         if (Pt > OpenPt/*Don't add empty ranges.*/ && RightMapping)
    143           RightMapping->add(OpenPt, Pt-1, CurrentRSuccessor);
    144         State = INTERSECT_OPENED;
    145         break;
    146       case ALL_IS_CLOSED:
    147         State = L_OPENED;
    148         break;
    149       default:
    150         assert(0 && "Got unexpected point.");
    151         break;
    152       }
    153       CurrentLSuccessor = S;
    154       OpenPt = Pt;
    155     }
    156 
    157     void onLClose(const IntTy &Pt) {
    158       switch (State) {
    159       case L_OPENED:
    160         assert(Pt >= OpenPt &&
    161                "Subset is not sorted or contains overlapped ranges");
    162         if (LeftMapping)
    163           LeftMapping->add(OpenPt, Pt, CurrentLSuccessor);
    164         State = ALL_IS_CLOSED;
    165         break;
    166       case INTERSECT_OPENED:
    167         if (IntersectionMapping)
    168           IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
    169         OpenPt = Pt + 1;
    170         State = R_OPENED;
    171         break;
    172       default:
    173         assert(0 && "Got unexpected point.");
    174         break;
    175       }
    176     }
    177 
    178     void onROpen(const IntTy &Pt, SuccessorClass *S) {
    179       switch (State) {
    180       case L_OPENED:
    181         if (Pt > OpenPt && LeftMapping)
    182           LeftMapping->add(OpenPt, Pt-1, CurrentLSuccessor);
    183         State = INTERSECT_OPENED;
    184         break;
    185       case ALL_IS_CLOSED:
    186         State = R_OPENED;
    187         break;
    188       default:
    189         assert(0 && "Got unexpected point.");
    190         break;
    191       }
    192       CurrentRSuccessor = S;
    193       OpenPt = Pt;
    194     }
    195 
    196     void onRClose(const IntTy &Pt) {
    197       switch (State) {
    198       case R_OPENED:
    199         assert(Pt >= OpenPt &&
    200                "Subset is not sorted or contains overlapped ranges");
    201         if (RightMapping)
    202           RightMapping->add(OpenPt, Pt, CurrentRSuccessor);
    203         State = ALL_IS_CLOSED;
    204         break;
    205       case INTERSECT_OPENED:
    206         if (IntersectionMapping)
    207           IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
    208         OpenPt = Pt + 1;
    209         State = L_OPENED;
    210         break;
    211       default:
    212         assert(0 && "Got unexpected point.");
    213         break;
    214       }
    215     }
    216 
    217     void onLROpen(const IntTy &Pt,
    218                   SuccessorClass *LS,
    219                   SuccessorClass *RS) {
    220       switch (State) {
    221       case ALL_IS_CLOSED:
    222         State = INTERSECT_OPENED;
    223         break;
    224       default:
    225         assert(0 && "Got unexpected point.");
    226         break;
    227       }
    228       CurrentLSuccessor = LS;
    229       CurrentRSuccessor = RS;
    230       OpenPt = Pt;
    231     }
    232 
    233     void onLRClose(const IntTy &Pt) {
    234       switch (State) {
    235       case INTERSECT_OPENED:
    236         if (IntersectionMapping)
    237           IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
    238         State = ALL_IS_CLOSED;
    239         break;
    240       default:
    241         assert(0 && "Got unexpected point.");
    242         break;
    243       }
    244     }
    245 
    246     bool isLOpened() { return State == L_OPENED; }
    247     bool isROpened() { return State == R_OPENED; }
    248   };
    249 
    250 public:
    251 
    252   // Don't public CaseItems itself. Don't allow edit the Items directly.
    253   // Just present the user way to iterate over the internal collection
    254   // sharing iterator, begin() and end(). Editing should be controlled by
    255   // factory.
    256   typedef CaseItemIt RangeIterator;
    257 
    258   typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
    259   typedef std::list<Case> Cases;
    260   typedef typename Cases::iterator CasesIt;
    261 
    262   IntegersSubsetMapping() {
    263     Sorted = false;
    264   }
    265 
    266   bool verify() {
    267     RangeIterator DummyErrItem;
    268     return verify(DummyErrItem);
    269   }
    270 
    271   bool verify(RangeIterator& errItem) {
    272     if (Items.empty())
    273       return true;
    274     sort();
    275     for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
    276          j != e; i = j++) {
    277       if (isIntersected(i, j) && i->second != j->second) {
    278         errItem = j;
    279         return false;
    280       }
    281     }
    282     return true;
    283   }
    284 
    285   bool isOverlapped(self &RHS) {
    286     if (Items.empty() || RHS.empty())
    287       return true;
    288 
    289     for (CaseItemIt L = Items.begin(), R = RHS.Items.begin(),
    290          el = Items.end(), er = RHS.Items.end(); L != el && R != er;) {
    291 
    292       const RangeTy &LRange = L->first;
    293       const RangeTy &RRange = R->first;
    294 
    295       if (LRange.getLow() > RRange.getLow()) {
    296         if (RRange.isSingleNumber() || LRange.getLow() > RRange.getHigh())
    297           ++R;
    298         else
    299           return true;
    300       } else if (LRange.getLow() < RRange.getLow()) {
    301         if (LRange.isSingleNumber() || LRange.getHigh() < RRange.getLow())
    302           ++L;
    303         else
    304           return true;
    305       } else // iRange.getLow() == jRange.getLow()
    306         return true;
    307     }
    308     return false;
    309   }
    310 
    311 
    312   void optimize() {
    313     if (Items.size() < 2)
    314       return;
    315     sort();
    316     CaseItems OldItems = Items;
    317     Items.clear();
    318     const IntTy *Low = &OldItems.begin()->first.getLow();
    319     const IntTy *High = &OldItems.begin()->first.getHigh();
    320     unsigned Weight = OldItems.begin()->first.Weight;
    321     SuccessorClass *Successor = OldItems.begin()->second;
    322     for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
    323          j != e; i = j++) {
    324       if (isJoinable(i, j)) {
    325         const IntTy *CurHigh = &j->first.getHigh();
    326         Weight += j->first.Weight;
    327         if (*CurHigh > *High)
    328           High = CurHigh;
    329       } else {
    330         RangeEx R(*Low, *High, Weight);
    331         add(R, Successor);
    332         Low = &j->first.getLow();
    333         High = &j->first.getHigh();
    334         Weight = j->first.Weight;
    335         Successor = j->second;
    336       }
    337     }
    338     RangeEx R(*Low, *High, Weight);
    339     add(R, Successor);
    340     // We recollected the Items, but we kept it sorted.
    341     Sorted = true;
    342   }
    343 
    344   /// Adds a constant value.
    345   void add(const IntTy &C, SuccessorClass *S = 0) {
    346     RangeTy R(C);
    347     add(R, S);
    348   }
    349 
    350   /// Adds a range.
    351   void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
    352     RangeTy R(Low, High);
    353     add(R, S);
    354   }
    355   void add(const RangeTy &R, SuccessorClass *S = 0) {
    356     RangeEx REx = R;
    357     add(REx, S);
    358   }
    359   void add(const RangeEx &R, SuccessorClass *S = 0) {
    360     Items.push_back(std::make_pair(R, S));
    361     Sorted = false;
    362   }
    363 
    364   /// Adds all ranges and values from given ranges set to the current
    365   /// mapping.
    366   void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0,
    367            unsigned Weight = 0) {
    368     unsigned ItemWeight = 1;
    369     if (Weight)
    370       // Weight is associated with CRS, for now we perform a division to
    371       // get the weight for each item.
    372       ItemWeight = Weight / CRS.getNumItems();
    373     for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
    374       RangeTy R = CRS.getItem(i);
    375       RangeEx REx(R, ItemWeight);
    376       add(REx, S);
    377     }
    378   }
    379 
    380   void add(self& RHS) {
    381     Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
    382   }
    383 
    384   void add(self& RHS, SuccessorClass *S) {
    385     for (CaseItemIt i = RHS.Items.begin(), e = RHS.Items.end(); i != e; ++i)
    386       add(i->first, S);
    387   }
    388 
    389   void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
    390     for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
    391       add(*i, S);
    392   }
    393 
    394   /// Removes items from set.
    395   void removeItem(RangeIterator i) { Items.erase(i); }
    396 
    397   /// Moves whole case from current mapping to the NewMapping object.
    398   void detachCase(self& NewMapping, SuccessorClass *Succ) {
    399     for (CaseItemIt i = Items.begin(); i != Items.end();)
    400       if (i->second == Succ) {
    401         NewMapping.add(i->first, i->second);
    402         Items.erase(i++);
    403       } else
    404         ++i;
    405   }
    406 
    407   /// Removes all clusters for given successor.
    408   void removeCase(SuccessorClass *Succ) {
    409     for (CaseItemIt i = Items.begin(); i != Items.end();)
    410       if (i->second == Succ) {
    411         Items.erase(i++);
    412       } else
    413         ++i;
    414   }
    415 
    416   /// Find successor that satisfies given value.
    417   SuccessorClass *findSuccessor(const IntTy& Val) {
    418     for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) {
    419       if (i->first.isInRange(Val))
    420         return i->second;
    421     }
    422     return 0;
    423   }
    424 
    425   /// Calculates the difference between this mapping and RHS.
    426   /// THIS without RHS is placed into LExclude,
    427   /// RHS without THIS is placed into RExclude,
    428   /// THIS intersect RHS is placed into Intersection.
    429   void diff(self *LExclude, self *Intersection, self *RExclude,
    430                              const self& RHS) {
    431 
    432     DiffStateMachine Machine(LExclude, Intersection, RExclude);
    433 
    434     CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
    435     while (L != Items.end() && R != RHS.Items.end()) {
    436       const Cluster &LCluster = *L;
    437       const RangeEx &LRange = LCluster.first;
    438       const Cluster &RCluster = *R;
    439       const RangeEx &RRange = RCluster.first;
    440 
    441       if (LRange.getHigh() < RRange.getLow()) {
    442         Machine.onLOpen(LRange.getLow(), LCluster.second);
    443         Machine.onLClose(LRange.getHigh());
    444         ++L;
    445         continue;
    446       }
    447 
    448       if (LRange.getLow() > RRange.getHigh()) {
    449         Machine.onROpen(RRange.getLow(), RCluster.second);
    450         Machine.onRClose(RRange.getHigh());
    451         ++R;
    452         continue;
    453       }
    454 
    455       if (LRange.getLow() < RRange.getLow()) {
    456         // May be opened in previous iteration.
    457         if (!Machine.isLOpened())
    458           Machine.onLOpen(LRange.getLow(), LCluster.second);
    459         Machine.onROpen(RRange.getLow(), RCluster.second);
    460       }
    461       else if (RRange.getLow() < LRange.getLow()) {
    462         if (!Machine.isROpened())
    463           Machine.onROpen(RRange.getLow(), RCluster.second);
    464         Machine.onLOpen(LRange.getLow(), LCluster.second);
    465       }
    466       else
    467         Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
    468 
    469       if (LRange.getHigh() < RRange.getHigh()) {
    470         Machine.onLClose(LRange.getHigh());
    471         ++L;
    472         while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
    473           Machine.onLOpen(L->first.getLow(), L->second);
    474           Machine.onLClose(L->first.getHigh());
    475           ++L;
    476         }
    477       }
    478       else if (RRange.getHigh() < LRange.getHigh()) {
    479         Machine.onRClose(RRange.getHigh());
    480         ++R;
    481         while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
    482           Machine.onROpen(R->first.getLow(), R->second);
    483           Machine.onRClose(R->first.getHigh());
    484           ++R;
    485         }
    486       }
    487       else {
    488         Machine.onLRClose(LRange.getHigh());
    489         ++L;
    490         ++R;
    491       }
    492     }
    493 
    494     if (L != Items.end()) {
    495       if (Machine.isLOpened()) {
    496         Machine.onLClose(L->first.getHigh());
    497         ++L;
    498       }
    499       if (LExclude)
    500         while (L != Items.end()) {
    501           LExclude->add(L->first, L->second);
    502           ++L;
    503         }
    504     } else if (R != RHS.Items.end()) {
    505       if (Machine.isROpened()) {
    506         Machine.onRClose(R->first.getHigh());
    507         ++R;
    508       }
    509       if (RExclude)
    510         while (R != RHS.Items.end()) {
    511           RExclude->add(R->first, R->second);
    512           ++R;
    513         }
    514     }
    515   }
    516 
    517   /// Builds the finalized case objects.
    518   void getCases(Cases& TheCases, bool PreventMerging = false) {
    519     //FIXME: PreventMerging is a temporary parameter.
    520     //Currently a set of passes is still knows nothing about
    521     //switches with case ranges, and if these passes meet switch
    522     //with complex case that crashs the application.
    523     if (PreventMerging) {
    524       for (RangeIterator i = this->begin(); i != this->end(); ++i) {
    525         RangesCollection SingleRange;
    526         SingleRange.push_back(i->first);
    527         TheCases.push_back(std::make_pair(i->second,
    528                                           IntegersSubsetTy(SingleRange)));
    529       }
    530       return;
    531     }
    532     CRSMap TheCRSMap;
    533     for (RangeIterator i = this->begin(); i != this->end(); ++i)
    534       TheCRSMap[i->second].push_back(i->first);
    535     for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
    536       TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
    537   }
    538 
    539   /// Builds the finalized case objects ignoring successor values, as though
    540   /// all ranges belongs to the same successor.
    541   IntegersSubsetTy getCase() {
    542     RangesCollection Ranges;
    543     for (RangeIterator i = this->begin(); i != this->end(); ++i)
    544       Ranges.push_back(i->first);
    545     return IntegersSubsetTy(Ranges);
    546   }
    547 
    548   /// Returns pointer to value of case if it is single-numbered or 0
    549   /// in another case.
    550   const IntTy* getCaseSingleNumber(SuccessorClass *Succ) {
    551     const IntTy* Res = 0;
    552     for (CaseItemIt i = Items.begin(); i != Items.end(); ++i)
    553       if (i->second == Succ) {
    554         if (!i->first.isSingleNumber())
    555           return 0;
    556         if (Res)
    557           return 0;
    558         else
    559           Res = &(i->first.getLow());
    560       }
    561     return Res;
    562   }
    563 
    564   /// Returns true if there is no ranges and values inside.
    565   bool empty() const { return Items.empty(); }
    566 
    567   void clear() {
    568     Items.clear();
    569     // Don't reset Sorted flag:
    570     // 1. For empty mapping it matters nothing.
    571     // 2. After first item will added Sorted flag will cleared.
    572   }
    573 
    574   // Returns number of clusters
    575   unsigned size() const {
    576     return Items.size();
    577   }
    578 
    579   RangeIterator begin() { return Items.begin(); }
    580   RangeIterator end() { return Items.end(); }
    581 };
    582 
    583 class BasicBlock;
    584 typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
    585 
    586 }
    587 
    588 #endif /* LLVM_SUPPORT_INTEGERSSUBSETMAPPING_CRSBUILDER_H */
    589