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