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   bool SingleNumbersOnly;
  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   void diff_single_numbers(self *LExclude, self *Intersection, self *RExclude,
 251                                const self& RHS) {
 252
 253     CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
 254     CaseItemConstIt el = Items.end(), er = RHS.Items.end();
 255     while (L != el && R != er) {
 256       const Cluster &LCluster = *L;
 257       const RangeEx &LRange = LCluster.first;
 258       const Cluster &RCluster = *R;
 259       const RangeEx &RRange = RCluster.first;
 260
 261       if (LRange.getLow() < RRange.getLow()) {
 262         if (LExclude)
 263           LExclude->add(LRange.getLow(), LCluster.second);
 264         ++L;
 265       } else if (LRange.getLow() > RRange.getLow()) {
 266         if (RExclude)
 267           RExclude->add(RRange.getLow(), RCluster.second);
 268         ++R;
 269       } else {
 270         if (Intersection)
 271           Intersection->add(LRange.getLow(), LCluster.second);
 272         ++L;
 273         ++R;
 274       }
 275     }
 276
 277     if (L != Items.end()) {
 278       if (LExclude)
 279         do {
 280             LExclude->add(L->first, L->second);
 281             ++L;
 282         } while (L != Items.end());
 283     } else if (R != RHS.Items.end()) {
 284       if (RExclude)
 285         do {
 286           RExclude->add(R->first, R->second);
 287           ++R;
 288         } while (R != RHS.Items.end());
 289     }
 290   }
 291
 292 public:
 293
 294   // Don't public CaseItems itself. Don't allow edit the Items directly.
 295   // Just present the user way to iterate over the internal collection
 296   // sharing iterator, begin() and end(). Editing should be controlled by
 297   // factory.
 298   typedef CaseItemIt RangeIterator;
 299
 300   typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
 301   typedef std::list<Case> Cases;
 302   typedef typename Cases::iterator CasesIt;
 303
 304   IntegersSubsetMapping() {
 305     Sorted = false;
 306     SingleNumbersOnly = true;
 307   }
 308
 309   bool verify() {
 310     RangeIterator DummyErrItem;
 311     return verify(DummyErrItem);
 312   }
 313
 314   bool verify(RangeIterator& errItem) {
 315     if (Items.empty())
 316       return true;
 317     sort();
 318     for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
 319          j != e; i = j++) {
 320       if (isIntersected(i, j) && i->second != j->second) {
 321         errItem = j;
 322         return false;
 323       }
 324     }
 325     return true;
 326   }
 327
 328   bool isOverlapped(self &RHS) {
 329     if (Items.empty() || RHS.empty())
 330       return true;
 331
 332     for (CaseItemIt L = Items.begin(), R = RHS.Items.begin(),
 333          el = Items.end(), er = RHS.Items.end(); L != el && R != er;) {
 334
 335       const RangeTy &LRange = L->first;
 336       const RangeTy &RRange = R->first;
 337
 338       if (LRange.getLow() > RRange.getLow()) {
 339         if (RRange.isSingleNumber() || LRange.getLow() > RRange.getHigh())
 340           ++R;
 341         else
 342           return true;
 343       } else if (LRange.getLow() < RRange.getLow()) {
 344         if (LRange.isSingleNumber() || LRange.getHigh() < RRange.getLow())
 345           ++L;
 346         else
 347           return true;
 348       } else // iRange.getLow() == jRange.getLow()
 349         return true;
 350     }
 351     return false;
 352   }
 353
 354
 355   void optimize() {
 356     if (Items.size() < 2)
 357       return;
 358     sort();
 359     CaseItems OldItems = Items;
 360     Items.clear();
 361     const IntTy *Low = &OldItems.begin()->first.getLow();
 362     const IntTy *High = &OldItems.begin()->first.getHigh();
 363     unsigned Weight = 1;
 364     SuccessorClass *Successor = OldItems.begin()->second;
 365     for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
 366          j != e; i = j++) {
 367       if (isJoinable(i, j)) {
 368         const IntTy *CurHigh = &j->first.getHigh();
 369         ++Weight;
 370         if (*CurHigh > *High)
 371           High = CurHigh;
 372       } else {
 373         RangeEx R(*Low, *High, Weight);
 374         add(R, Successor);
 375         Low = &j->first.getLow();
 376         High = &j->first.getHigh();
 377         Weight = 1;
 378         Successor = j->second;
 379       }
 380     }
 381     RangeEx R(*Low, *High, Weight);
 382     add(R, Successor);
 383     // We recollected the Items, but we kept it sorted.
 384     Sorted = true;
 385   }
 386
 387   /// Adds a constant value.
 388   void add(const IntTy &C, SuccessorClass *S = 0) {
 389     RangeTy R(C);
 390     add(R, S);
 391   }
 392
 393   /// Adds a range.
 394   void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
 395     RangeTy R(Low, High);
 396     add(R, S);
 397   }
 398   void add(const RangeTy &R, SuccessorClass *S = 0) {
 399     RangeEx REx = R;
 400     add(REx, S);
 401   }
 402   void add(const RangeEx &R, SuccessorClass *S = 0) {
 403     Items.push_back(std::make_pair(R, S));
 404     if (!R.isSingleNumber())
 405       SingleNumbersOnly = false;
 406   }
 407
 408   /// Adds all ranges and values from given ranges set to the current
 409   /// mapping.
 410   void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
 411     for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
 412       RangeTy R = CRS.getItem(i);
 413       add(R, S);
 414     }
 415   }
 416
 417   void add(self& RHS) {
 418     Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
 419     if (!RHS.SingleNumbersOnly)
 420       SingleNumbersOnly = false;
 421   }
 422
 423   void add(self& RHS, SuccessorClass *S) {
 424     for (CaseItemIt i = RHS.Items.begin(), e = RHS.Items.end(); i != e; ++i)
 425       add(i->first, S);
 426   }
 427
 428   void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
 429     for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
 430       add(*i, S);
 431   }
 432
 433   /// Removes items from set.
 434   void removeItem(RangeIterator i) { Items.erase(i); }
 435
 436   /// Moves whole case from current mapping to the NewMapping object.
 437   void detachCase(self& NewMapping, SuccessorClass *Succ) {
 438     for (CaseItemIt i = Items.begin(); i != Items.end();)
 439       if (i->second == Succ) {
 440         NewMapping.add(i->first, i->second);
 441         Items.erase(i++);
 442       } else
 443         ++i;
 444   }
 445
 446   /// Removes all clusters for given successor.
 447   void removeCase(SuccessorClass *Succ) {
 448     for (CaseItemIt i = Items.begin(); i != Items.end();)
 449       if (i->second == Succ) {
 450         Items.erase(i++);
 451       } else
 452         ++i;
 453   }
 454
 455   /// Find successor that satisfies given value.
 456   SuccessorClass *findSuccessor(const IntTy& Val) {
 457     for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) {
 458       if (i->first.isInRange(Val))
 459         return i->second;
 460     }
 461     return 0;
 462   }
 463
 464   /// Calculates the difference between this mapping and RHS.
 465   /// THIS without RHS is placed into LExclude,
 466   /// RHS without THIS is placed into RExclude,
 467   /// THIS intersect RHS is placed into Intersection.
 468   void diff(self *LExclude, self *Intersection, self *RExclude,
 469                              const self& RHS) {
 470
 471     if (SingleNumbersOnly && RHS.SingleNumbersOnly) {
 472       diff_single_numbers(LExclude, Intersection, RExclude, RHS);
 473       return;
 474     }
 475
 476     DiffStateMachine Machine(LExclude, Intersection, RExclude);
 477
 478     CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
 479     CaseItemConstIt el = Items.end(), er = RHS.Items.end();
 480     while (L != el && R != er) {
 481       const Cluster &LCluster = *L;
 482       const RangeEx &LRange = LCluster.first;
 483       const Cluster &RCluster = *R;
 484       const RangeEx &RRange = RCluster.first;
 485
 486       if (LRange.getHigh() < RRange.getLow()) {
 487         Machine.onLOpen(LRange.getLow(), LCluster.second);
 488         Machine.onLClose(LRange.getHigh());
 489         ++L;
 490         continue;
 491       }
 492
 493       if (LRange.getLow() > RRange.getHigh()) {
 494         Machine.onROpen(RRange.getLow(), RCluster.second);
 495         Machine.onRClose(RRange.getHigh());
 496         ++R;
 497         continue;
 498       }
 499
 500       if (LRange.isSingleNumber() && RRange.isSingleNumber()) {
 501         Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
 502         Machine.onLRClose(LRange.getLow());
 503         ++L;
 504         ++R;
 505         continue;
 506       }
 507
 508       if (LRange.isSingleNumber()) {
 509         Machine.onLOpen(LRange.getLow(), LCluster.second);
 510         Machine.onLClose(LRange.getLow());
 511         ++L;
 512         while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
 513           Machine.onLOpen(LRange.getLow(), LCluster.second);
 514           Machine.onLClose(LRange.getLow());
 515           ++L;
 516         }
 517         continue;
 518       } else if (RRange.isSingleNumber()) {
 519         Machine.onROpen(R->first.getLow(), R->second);
 520         Machine.onRClose(R->first.getHigh());
 521         ++R;
 522         while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
 523           Machine.onROpen(R->first.getLow(), R->second);
 524           Machine.onRClose(R->first.getHigh());
 525           ++R;
 526         }
 527         continue;
 528       } else
 529       if (LRange.getLow() < RRange.getLow()) {
 530         // May be opened in previous iteration.
 531         if (!Machine.isLOpened())
 532           Machine.onLOpen(LRange.getLow(), LCluster.second);
 533         Machine.onROpen(RRange.getLow(), RCluster.second);
 534       }
 535       else if (RRange.getLow() < LRange.getLow()) {
 536         if (!Machine.isROpened())
 537           Machine.onROpen(RRange.getLow(), RCluster.second);
 538         Machine.onLOpen(LRange.getLow(), LCluster.second);
 539       }
 540       else
 541         Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
 542
 543       if (LRange.getHigh() < RRange.getHigh()) {
 544         Machine.onLClose(LRange.getHigh());
 545         ++L;
 546         while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
 547           Machine.onLOpen(L->first.getLow(), L->second);
 548           Machine.onLClose(L->first.getHigh());
 549           ++L;
 550         }
 551       }
 552       else if (RRange.getHigh() < LRange.getHigh()) {
 553         Machine.onRClose(RRange.getHigh());
 554         ++R;
 555         while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
 556           Machine.onROpen(R->first.getLow(), R->second);
 557           Machine.onRClose(R->first.getHigh());
 558           ++R;
 559         }
 560       }
 561       else {
 562         Machine.onLRClose(LRange.getHigh());
 563         ++L;
 564         ++R;
 565       }
 566     }
 567
 568     if (L != Items.end()) {
 569       if (Machine.isLOpened()) {
 570         Machine.onLClose(L->first.getHigh());
 571         ++L;
 572       }
 573       if (LExclude)
 574         while (L != Items.end()) {
 575           LExclude->add(L->first, L->second);
 576           ++L;
 577         }
 578     } else if (R != RHS.Items.end()) {
 579       if (Machine.isROpened()) {
 580         Machine.onRClose(R->first.getHigh());
 581         ++R;
 582       }
 583       if (RExclude)
 584         while (R != RHS.Items.end()) {
 585           RExclude->add(R->first, R->second);
 586           ++R;
 587         }
 588     }
 589   }
 590
 591   /// Builds the finalized case objects.
 592   void getCases(Cases& TheCases, bool PreventMerging = false) {
 593     //FIXME: PreventMerging is a temporary parameter.
 594     //Currently a set of passes is still knows nothing about
 595     //switches with case ranges, and if these passes meet switch
 596     //with complex case that crashs the application.
 597     if (PreventMerging) {
 598       for (RangeIterator i = this->begin(); i != this->end(); ++i) {
 599         RangesCollection SingleRange;
 600         SingleRange.push_back(i->first);
 601         TheCases.push_back(std::make_pair(i->second,
 602                                           IntegersSubsetTy(SingleRange)));
 603       }
 604       return;
 605     }
 606     CRSMap TheCRSMap;
 607     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 608       TheCRSMap[i->second].push_back(i->first);
 609     for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
 610       TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
 611   }
 612
 613   /// Builds the finalized case objects ignoring successor values, as though
 614   /// all ranges belongs to the same successor.
 615   IntegersSubsetTy getCase() {
 616     RangesCollection Ranges;
 617     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 618       Ranges.push_back(i->first);
 619     return IntegersSubsetTy(Ranges);
 620   }
 621
 622   /// Returns pointer to value of case if it is single-numbered or 0
 623   /// in another case.
 624   const IntTy* getCaseSingleNumber(SuccessorClass *Succ) {
 625     const IntTy* Res = 0;
 626     for (CaseItemIt i = Items.begin(); i != Items.end(); ++i)
 627       if (i->second == Succ) {
 628         if (!i->first.isSingleNumber())
 629           return 0;
 630         if (Res)
 631           return 0;
 632         else
 633           Res = &(i->first.getLow());
 634       }
 635     return Res;
 636   }
 637
 638   /// Returns true if there is no ranges and values inside.
 639   bool empty() const { return Items.empty(); }
 640
 641   void clear() {
 642     Items.clear();
 643     // Don't reset Sorted flag:
 644     // 1. For empty mapping it matters nothing.
 645     // 2. After first item will added Sorted flag will cleared.
 646   }
 647
 648   // Returns number of clusters
 649   unsigned size() const {
 650     return Items.size();
 651   }
 652
 653   RangeIterator begin() { return Items.begin(); }
 654   RangeIterator end() { return Items.end(); }
 655 };
 656
 657 class BasicBlock;
 658 typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
 659
 660 }
 661
 662 #endif /* CRSBUILDER_H_ */