contrib/llvm/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 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 */