X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FSupport%2FIntegersSubsetMapping.h;h=cab18dce159b9e6a4375c7db68af931628d0c08b;hb=118f194966d20460c2b1653e06c601e4b66c9b3f;hp=b630119aea894a5e857d9d0bca21c4615d57d381;hpb=43eb31bfae470b33bab9a6764b98b5e8a0beeda5;p=oota-llvm.git diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h index b630119aea8..cab18dce159 100644 --- a/include/llvm/Support/IntegersSubsetMapping.h +++ b/include/llvm/Support/IntegersSubsetMapping.h @@ -1,4 +1,4 @@ -//===- CRSBuilder.h - ConstantRangesSet Builder -----------------*- C++ -*-===// +//===- IntegersSubsetMapping.h - Mapping subset ==> Successor ---*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -8,11 +8,12 @@ //===----------------------------------------------------------------------===// // /// @file -/// CRSBuilder allows to build and parse ConstantRangesSet objects. -/// There is such features like add/remove range, or combine -/// Two ConstantRangesSet object with neighboring ranges merging. -/// Set IsReadonly=true if you want to operate with "const ConstantInt" and -/// "const ConstantRangesSet" objects. +/// IntegersSubsetMapping is mapping from A to B, where +/// Items in A is subsets of integers, +/// Items in B some pointers (Successors). +/// If user which to add another subset for successor that is already +/// exists in mapping, IntegersSubsetMapping merges existing subset with +/// added one. // //===----------------------------------------------------------------------===// @@ -30,6 +31,10 @@ template class IntegersSubsetMapping { + // FIXME: To much similar iterators typedefs, similar names. + // - Rename RangeIterator to the cluster iterator. + // - Remove unused "add" methods. + // - Class contents needs cleaning. public: typedef IntRange RangeTy; @@ -46,15 +51,18 @@ public: typedef std::pair Cluster; + typedef std::list RangesCollection; + typedef typename RangesCollection::iterator RangesCollectionIt; + typedef typename RangesCollection::const_iterator RangesCollectionConstIt; + typedef IntegersSubsetMapping self; + protected: - typedef std::vector CaseItems; + typedef std::list CaseItems; typedef typename CaseItems::iterator CaseItemIt; typedef typename CaseItems::const_iterator CaseItemConstIt; - typedef std::list RangesCollection; - typedef typename RangesCollection::iterator RangesCollectionIt; - + // TODO: Change unclean CRS prefixes to SubsetMap for example. typedef std::map CRSMap; typedef typename CRSMap::iterator CRSMapIt; @@ -85,11 +93,159 @@ protected: void sort() { if (!Sorted) { - std::sort(Items.begin(), Items.end(), ClustersCmp()); + std::vector clustersVector; + clustersVector.reserve(Items.size()); + clustersVector.insert(clustersVector.begin(), Items.begin(), Items.end()); + std::sort(clustersVector.begin(), clustersVector.end(), ClustersCmp()); + Items.clear(); + Items.insert(Items.begin(), clustersVector.begin(), clustersVector.end()); Sorted = true; } } + enum DiffProcessState { + L_OPENED, + INTERSECT_OPENED, + R_OPENED, + ALL_IS_CLOSED + }; + + class DiffStateMachine { + + DiffProcessState State; + IntTy OpenPt; + SuccessorClass *CurrentLSuccessor; + SuccessorClass *CurrentRSuccessor; + + self *LeftMapping; + self *IntersectionMapping; + self *RightMapping; + + public: + + typedef + IntegersSubsetMapping MappingTy; + + DiffStateMachine(MappingTy *L, + MappingTy *Intersection, + MappingTy *R) : + State(ALL_IS_CLOSED), + LeftMapping(L), + IntersectionMapping(Intersection), + RightMapping(R) + {} + + void onLOpen(const IntTy &Pt, SuccessorClass *S) { + switch (State) { + case R_OPENED: + if (Pt > OpenPt/*Don't add empty ranges.*/ && RightMapping) + RightMapping->add(OpenPt, Pt-1, CurrentRSuccessor); + State = INTERSECT_OPENED; + break; + case ALL_IS_CLOSED: + State = L_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + CurrentLSuccessor = S; + OpenPt = Pt; + } + + void onLClose(const IntTy &Pt) { + switch (State) { + case L_OPENED: + assert(Pt >= OpenPt && + "Subset is not sorted or contains overlapped ranges"); + if (LeftMapping) + LeftMapping->add(OpenPt, Pt, CurrentLSuccessor); + State = ALL_IS_CLOSED; + break; + case INTERSECT_OPENED: + if (IntersectionMapping) + IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor); + OpenPt = Pt + 1; + State = R_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + } + + void onROpen(const IntTy &Pt, SuccessorClass *S) { + switch (State) { + case L_OPENED: + if (Pt > OpenPt && LeftMapping) + LeftMapping->add(OpenPt, Pt-1, CurrentLSuccessor); + State = INTERSECT_OPENED; + break; + case ALL_IS_CLOSED: + State = R_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + CurrentRSuccessor = S; + OpenPt = Pt; + } + + void onRClose(const IntTy &Pt) { + switch (State) { + case R_OPENED: + assert(Pt >= OpenPt && + "Subset is not sorted or contains overlapped ranges"); + if (RightMapping) + RightMapping->add(OpenPt, Pt, CurrentRSuccessor); + State = ALL_IS_CLOSED; + break; + case INTERSECT_OPENED: + if (IntersectionMapping) + IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor); + OpenPt = Pt + 1; + State = L_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + } + + void onLROpen(const IntTy &Pt, + SuccessorClass *LS, + SuccessorClass *RS) { + switch (State) { + case ALL_IS_CLOSED: + State = INTERSECT_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + CurrentLSuccessor = LS; + CurrentRSuccessor = RS; + OpenPt = Pt; + } + + void onLRClose(const IntTy &Pt) { + switch (State) { + case INTERSECT_OPENED: + if (IntersectionMapping) + IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor); + State = ALL_IS_CLOSED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + } + + bool isLOpened() { return State == L_OPENED; } + bool isROpened() { return State == R_OPENED; } + }; + public: // Don't public CaseItems itself. Don't allow edit the Items directly. @@ -100,25 +256,57 @@ public: typedef std::pair Case; typedef std::list Cases; + typedef typename Cases::iterator CasesIt; IntegersSubsetMapping() { - Items.reserve(32); Sorted = false; } + bool verify() { + RangeIterator DummyErrItem; + return verify(DummyErrItem); + } + bool verify(RangeIterator& errItem) { if (Items.empty()) return true; sort(); - for (CaseItemIt i = Items.begin(), j = i+1, e = Items.end(); + for (CaseItemIt j = Items.begin(), i = j++, e = Items.end(); j != e; i = j++) { - if (isIntersected(j, i) && j->second != i->second) { + if (isIntersected(i, j) && i->second != j->second) { errItem = j; return false; } } return true; } + + bool isOverlapped(self &RHS) { + if (Items.empty() || RHS.empty()) + return true; + + for (CaseItemIt L = Items.begin(), R = RHS.Items.begin(), + el = Items.end(), er = RHS.Items.end(); L != el && R != er;) { + + const RangeTy &LRange = L->first; + const RangeTy &RRange = R->first; + + if (LRange.getLow() > RRange.getLow()) { + if (RRange.isSingleNumber() || LRange.getLow() > RRange.getHigh()) + ++R; + else + return true; + } else if (LRange.getLow() < RRange.getLow()) { + if (LRange.isSingleNumber() || LRange.getHigh() < RRange.getLow()) + ++L; + else + return true; + } else // iRange.getLow() == jRange.getLow() + return true; + } + return false; + } + void optimize() { if (Items.size() < 2) @@ -130,8 +318,8 @@ public: const IntTy *High = &OldItems.begin()->first.getHigh(); unsigned Weight = 1; SuccessorClass *Successor = OldItems.begin()->second; - for (CaseItemIt i = OldItems.begin(), j = i+1, e = OldItems.end(); - j != e; i = j++) { + for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end(); + j != e; i = j++) { if (isJoinable(i, j)) { const IntTy *CurHigh = &j->first.getHigh(); ++Weight; @@ -173,19 +361,166 @@ public: } /// Adds all ranges and values from given ranges set to the current - /// CRSBuilder object. - void add(const IntegersSubset &CRS, SuccessorClass *S = 0) { + /// mapping. + void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) { for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) { RangeTy R = CRS.getItem(i); add(R, S); } } + void add(self& RHS) { + Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end()); + } + + void add(self& RHS, SuccessorClass *S) { + for (CaseItemIt i = RHS.Items.begin(), e = RHS.Items.end(); i != e; ++i) + add(i->first, S); + } + + void add(const RangesCollection& RHS, SuccessorClass *S = 0) { + for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i) + add(*i, S); + } + /// Removes items from set. void removeItem(RangeIterator i) { Items.erase(i); } + /// Moves whole case from current mapping to the NewMapping object. + void detachCase(self& NewMapping, SuccessorClass *Succ) { + for (CaseItemIt i = Items.begin(); i != Items.end();) + if (i->second == Succ) { + NewMapping.add(i->first, i->second); + Items.erase(i++); + } else + ++i; + } + + /// Removes all clusters for given successor. + void removeCase(SuccessorClass *Succ) { + for (CaseItemIt i = Items.begin(); i != Items.end();) + if (i->second == Succ) { + Items.erase(i++); + } else + ++i; + } + + /// Find successor that satisfies given value. + SuccessorClass *findSuccessor(const IntTy& Val) { + for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) { + if (i->first.isInRange(Val)) + return i->second; + } + return 0; + } + + /// Calculates the difference between this mapping and RHS. + /// THIS without RHS is placed into LExclude, + /// RHS without THIS is placed into RExclude, + /// THIS intersect RHS is placed into Intersection. + void diff(self *LExclude, self *Intersection, self *RExclude, + const self& RHS) { + + DiffStateMachine Machine(LExclude, Intersection, RExclude); + + CaseItemConstIt L = Items.begin(), R = RHS.Items.begin(); + while (L != Items.end() && R != RHS.Items.end()) { + const Cluster &LCluster = *L; + const RangeEx &LRange = LCluster.first; + const Cluster &RCluster = *R; + const RangeEx &RRange = RCluster.first; + + if (LRange.getHigh() < RRange.getLow()) { + Machine.onLOpen(LRange.getLow(), LCluster.second); + Machine.onLClose(LRange.getHigh()); + ++L; + continue; + } + + if (LRange.getLow() > RRange.getHigh()) { + Machine.onROpen(RRange.getLow(), RCluster.second); + Machine.onRClose(RRange.getHigh()); + ++R; + continue; + } + + if (LRange.getLow() < RRange.getLow()) { + // May be opened in previous iteration. + if (!Machine.isLOpened()) + Machine.onLOpen(LRange.getLow(), LCluster.second); + Machine.onROpen(RRange.getLow(), RCluster.second); + } + else if (RRange.getLow() < LRange.getLow()) { + if (!Machine.isROpened()) + Machine.onROpen(RRange.getLow(), RCluster.second); + Machine.onLOpen(LRange.getLow(), LCluster.second); + } + else + Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second); + + if (LRange.getHigh() < RRange.getHigh()) { + Machine.onLClose(LRange.getHigh()); + ++L; + while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) { + Machine.onLOpen(L->first.getLow(), L->second); + Machine.onLClose(L->first.getHigh()); + ++L; + } + } + else if (RRange.getHigh() < LRange.getHigh()) { + Machine.onRClose(RRange.getHigh()); + ++R; + while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) { + Machine.onROpen(R->first.getLow(), R->second); + Machine.onRClose(R->first.getHigh()); + ++R; + } + } + else { + Machine.onLRClose(LRange.getHigh()); + ++L; + ++R; + } + } + + if (L != Items.end()) { + if (Machine.isLOpened()) { + Machine.onLClose(L->first.getHigh()); + ++L; + } + if (LExclude) + while (L != Items.end()) { + LExclude->add(L->first, L->second); + ++L; + } + } else if (R != RHS.Items.end()) { + if (Machine.isROpened()) { + Machine.onRClose(R->first.getHigh()); + ++R; + } + if (RExclude) + while (R != RHS.Items.end()) { + RExclude->add(R->first, R->second); + ++R; + } + } + } + /// Builds the finalized case objects. - void getCases(Cases& TheCases) { + void getCases(Cases& TheCases, bool PreventMerging = false) { + //FIXME: PreventMerging is a temporary parameter. + //Currently a set of passes is still knows nothing about + //switches with case ranges, and if these passes meet switch + //with complex case that crashs the application. + if (PreventMerging) { + for (RangeIterator i = this->begin(); i != this->end(); ++i) { + RangesCollection SingleRange; + SingleRange.push_back(i->first); + TheCases.push_back(std::make_pair(i->second, + IntegersSubsetTy(SingleRange))); + } + return; + } CRSMap TheCRSMap; for (RangeIterator i = this->begin(); i != this->end(); ++i) TheCRSMap[i->second].push_back(i->first); @@ -195,16 +530,44 @@ public: /// Builds the finalized case objects ignoring successor values, as though /// all ranges belongs to the same successor. - IntegersSubset getCase() { + IntegersSubsetTy getCase() { RangesCollection Ranges; for (RangeIterator i = this->begin(); i != this->end(); ++i) Ranges.push_back(i->first); return IntegersSubsetTy(Ranges); } + /// Returns pointer to value of case if it is single-numbered or 0 + /// in another case. + const IntTy* getCaseSingleNumber(SuccessorClass *Succ) { + const IntTy* Res = 0; + for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) + if (i->second == Succ) { + if (!i->first.isSingleNumber()) + return 0; + if (Res) + return 0; + else + Res = &(i->first.getLow()); + } + return Res; + } + /// Returns true if there is no ranges and values inside. bool empty() const { return Items.empty(); } + void clear() { + Items.clear(); + // Don't reset Sorted flag: + // 1. For empty mapping it matters nothing. + // 2. After first item will added Sorted flag will cleared. + } + + // Returns number of clusters + unsigned size() const { + return Items.size(); + } + RangeIterator begin() { return Items.begin(); } RangeIterator end() { return Items.end(); } };