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 onRLOpen(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 onRLClose(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
 303   IntegersSubsetMapping() {
 304     Sorted = false;
 305     SingleNumbersOnly = true;
 306   }
 307
 308   bool verify(RangeIterator& errItem) {
 309     if (Items.empty())
 310       return true;
 311     sort();
 312     for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
 313          j != e; i = j++) {
 314       if (isIntersected(i, j) && i->second != j->second) {
 315         errItem = j;
 316         return false;
 317       }
 318     }
 319     return true;
 320   }
 321
 322   void optimize() {
 323     if (Items.size() < 2)
 324       return;
 325     sort();
 326     CaseItems OldItems = Items;
 327     Items.clear();
 328     const IntTy *Low = &OldItems.begin()->first.getLow();
 329     const IntTy *High = &OldItems.begin()->first.getHigh();
 330     unsigned Weight = 1;
 331     SuccessorClass *Successor = OldItems.begin()->second;
 332     for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
 333          j != e; i = j++) {
 334       if (isJoinable(i, j)) {
 335         const IntTy *CurHigh = &j->first.getHigh();
 336         ++Weight;
 337         if (*CurHigh > *High)
 338           High = CurHigh;
 339       } else {
 340         RangeEx R(*Low, *High, Weight);
 341         add(R, Successor);
 342         Low = &j->first.getLow();
 343         High = &j->first.getHigh();
 344         Weight = 1;
 345         Successor = j->second;
 346       }
 347     }
 348     RangeEx R(*Low, *High, Weight);
 349     add(R, Successor);
 350     // We recollected the Items, but we kept it sorted.
 351     Sorted = true;
 352   }
 353
 354   /// Adds a constant value.
 355   void add(const IntTy &C, SuccessorClass *S = 0) {
 356     RangeTy R(C);
 357     add(R, S);
 358   }
 359
 360   /// Adds a range.
 361   void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
 362     RangeTy R(Low, High);
 363     add(R, S);
 364   }
 365   void add(const RangeTy &R, SuccessorClass *S = 0) {
 366     RangeEx REx = R;
 367     add(REx, S);
 368   }
 369   void add(const RangeEx &R, SuccessorClass *S = 0) {
 370     Items.push_back(std::make_pair(R, S));
 371     if (!R.isSingleNumber())
 372       SingleNumbersOnly = false;
 373   }
 374
 375   /// Adds all ranges and values from given ranges set to the current
 376   /// mapping.
 377   void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
 378     for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
 379       RangeTy R = CRS.getItem(i);
 380       add(R, S);
 381     }
 382   }
 383
 384   void add(self& RHS) {
 385     Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
 386     if (!RHS.SingleNumbersOnly)
 387       SingleNumbersOnly = false;
 388   }
 389
 390   void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
 391     for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
 392       add(*i, S);
 393   }
 394
 395   /// Removes items from set.
 396   void removeItem(RangeIterator i) { Items.erase(i); }
 397
 398   /// Calculates the difference between this mapping and RHS.
 399   /// THIS without RHS is placed into LExclude,
 400   /// RHS without THIS is placed into RExclude,
 401   /// THIS intersect RHS is placed into Intersection.
 402   void diff(self *LExclude, self *Intersection, self *RExclude,
 403                              const self& RHS) {
 404
 405     if (SingleNumbersOnly && RHS.SingleNumbersOnly) {
 406       diff_single_numbers(LExclude, Intersection, RExclude, RHS);
 407       return;
 408     }
 409
 410     DiffStateMachine Machine(LExclude, Intersection, RExclude);
 411
 412     CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
 413     CaseItemConstIt el = Items.end(), er = RHS.Items.end();
 414     while (L != el && R != er) {
 415       const Cluster &LCluster = *L;
 416       const RangeEx &LRange = LCluster.first;
 417       const Cluster &RCluster = *R;
 418       const RangeEx &RRange = RCluster.first;
 419
 420       if (LRange.getHigh() < RRange.getLow()) {
 421         Machine.onLOpen(LRange.getLow(), LCluster.second);
 422         Machine.onLClose(LRange.getHigh());
 423         ++L;
 424         continue;
 425       }
 426
 427       if (LRange.getLow() > RRange.getHigh()) {
 428         Machine.onROpen(RRange.getLow(), RCluster.second);
 429         Machine.onRClose(RRange.getHigh());
 430         ++R;
 431         continue;
 432       }
 433
 434       if (LRange.isSingleNumber() && RRange.isSingleNumber()) {
 435         Machine.onRLOpen(LRange.getLow(), LCluster.second, RCluster.second);
 436         Machine.onRLClose(LRange.getLow());
 437         ++L;
 438         ++R;
 439         continue;
 440       }
 441
 442       if (LRange.isSingleNumber()) {
 443         Machine.onLOpen(LRange.getLow(), LCluster.second);
 444         Machine.onLClose(LRange.getLow());
 445         ++L;
 446         while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
 447           Machine.onLOpen(LRange.getLow(), LCluster.second);
 448           Machine.onLClose(LRange.getLow());
 449           ++L;
 450         }
 451         continue;
 452       } else if (RRange.isSingleNumber()) {
 453         Machine.onROpen(R->first.getLow(), R->second);
 454         Machine.onRClose(R->first.getHigh());
 455         ++R;
 456         while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
 457           Machine.onROpen(R->first.getLow(), R->second);
 458           Machine.onRClose(R->first.getHigh());
 459           ++R;
 460         }
 461         continue;
 462       } else
 463       if (LRange.getLow() < RRange.getLow()) {
 464         // May be opened in previous iteration.
 465         if (!Machine.isLOpened())
 466           Machine.onLOpen(LRange.getLow(), LCluster.second);
 467         Machine.onROpen(RRange.getLow(), RCluster.second);
 468       }
 469       else if (RRange.getLow() < LRange.getLow()) {
 470         if (!Machine.isROpened())
 471           Machine.onROpen(RRange.getLow(), RCluster.second);
 472         Machine.onLOpen(LRange.getLow(), LCluster.second);
 473       }
 474       else
 475         Machine.onRLOpen(LRange.getLow(), LCluster.second, RCluster.second);
 476
 477       if (LRange.getHigh() < RRange.getHigh()) {
 478         Machine.onLClose(LRange.getHigh());
 479         ++L;
 480         while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
 481           Machine.onLOpen(L->first.getLow(), L->second);
 482           Machine.onLClose(L->first.getHigh());
 483           ++L;
 484         }
 485       }
 486       else if (RRange.getHigh() < LRange.getHigh()) {
 487         Machine.onRClose(RRange.getHigh());
 488         ++R;
 489         while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
 490           Machine.onROpen(R->first.getLow(), R->second);
 491           Machine.onRClose(R->first.getHigh());
 492           ++R;
 493         }
 494       }
 495       else {
 496         Machine.onRLClose(LRange.getHigh());
 497         ++L;
 498         ++R;
 499       }
 500     }
 501
 502     if (L != Items.end()) {
 503       if (Machine.isLOpened()) {
 504         Machine.onLClose(L->first.getHigh());
 505         ++L;
 506       }
 507       if (LExclude)
 508         while (L != Items.end()) {
 509           LExclude->add(L->first, L->second);
 510           ++L;
 511         }
 512     } else if (R != RHS.Items.end()) {
 513       if (Machine.isROpened()) {
 514         Machine.onRClose(R->first.getHigh());
 515         ++R;
 516       }
 517       if (RExclude)
 518         while (R != RHS.Items.end()) {
 519           RExclude->add(R->first, R->second);
 520           ++R;
 521         }
 522     }
 523   }
 524
 525   /// Builds the finalized case objects.
 526   void getCases(Cases& TheCases) {
 527     CRSMap TheCRSMap;
 528     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 529       TheCRSMap[i->second].push_back(i->first);
 530     for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
 531       TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
 532   }
 533
 534   /// Builds the finalized case objects ignoring successor values, as though
 535   /// all ranges belongs to the same successor.
 536   IntegersSubsetTy getCase() {
 537     RangesCollection Ranges;
 538     for (RangeIterator i = this->begin(); i != this->end(); ++i)
 539       Ranges.push_back(i->first);
 540     return IntegersSubsetTy(Ranges);
 541   }
 542
 543   /// Returns true if there is no ranges and values inside.
 544   bool empty() const { return Items.empty(); }
 545
 546   void clear() {
 547     Items.clear();
 548     // Don't reset Sorted flag:
 549     // 1. For empty mapping it matters nothing.
 550     // 2. After first item will added Sorted flag will cleared.
 551   }
 552
 553   // Returns number of clusters
 554   unsigned size() const {
 555     return Items.size();
 556   }
 557
 558   RangeIterator begin() { return Items.begin(); }
 559   RangeIterator end() { return Items.end(); }
 560 };
 561
 562 class BasicBlock;
 563 typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
 564
 565 }
 566
 567 #endif /* CRSBUILDER_H_ */