X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FSupport%2FIntegersSubsetMapping.h;h=7635d5e9122160c575078604ce599b4f5dcb582a;hb=a5bf44b0b396e8b9ae0db5c62c05ac6618aab5d3;hp=667980296d4a1cf2ea1cdd5f0d5e97f440287e50;hpb=9ccc83e7f70e63b746cbc7eef9fb06022e758677;p=oota-llvm.git diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h index 667980296d4..7635d5e9122 100644 --- a/include/llvm/Support/IntegersSubsetMapping.h +++ b/include/llvm/Support/IntegersSubsetMapping.h @@ -42,6 +42,7 @@ public: struct RangeEx : public RangeTy { RangeEx() : Weight(1) {} RangeEx(const RangeTy &R) : RangeTy(R), Weight(1) {} + RangeEx(const RangeTy &R, unsigned W) : RangeTy(R), Weight(W) {} RangeEx(const IntTy &C) : RangeTy(C), Weight(1) {} RangeEx(const IntTy &L, const IntTy &H) : RangeTy(L, H), Weight(1) {} RangeEx(const IntTy &L, const IntTy &H, unsigned W) : @@ -58,16 +59,22 @@ public: protected: - typedef std::map CaseItems; + typedef std::list CaseItems; typedef typename CaseItems::iterator CaseItemIt; typedef typename CaseItems::const_iterator CaseItemConstIt; // TODO: Change unclean CRS prefixes to SubsetMap for example. typedef std::map CRSMap; typedef typename CRSMap::iterator CRSMapIt; + + struct ClustersCmp { + bool operator()(const Cluster &C1, const Cluster &C2) { + return C1.first < C2.first; + } + }; CaseItems Items; - bool SingleNumbersOnly; + bool Sorted; bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) { return LItem->first.getHigh() >= RItem->first.getLow(); @@ -85,6 +92,18 @@ protected: return LItem->first.getHigh() >= RLow; } + void sort() { + if (!Sorted) { + 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, @@ -227,48 +246,6 @@ protected: bool isLOpened() { return State == L_OPENED; } bool isROpened() { return State == R_OPENED; } }; - - void diff_single_numbers(self *LExclude, self *Intersection, self *RExclude, - const self& RHS) { - - CaseItemConstIt L = Items.begin(), R = RHS.Items.begin(); - CaseItemConstIt el = Items.end(), er = RHS.Items.end(); - while (L != el && R != er) { - const Cluster &LCluster = *L; - const RangeEx &LRange = LCluster.first; - const Cluster &RCluster = *R; - const RangeEx &RRange = RCluster.first; - - if (LRange.getLow() < RRange.getLow()) { - if (LExclude) - LExclude->add(LRange.getLow(), LCluster.second); - ++L; - } else if (LRange.getLow() > RRange.getLow()) { - if (RExclude) - RExclude->add(RRange.getLow(), RCluster.second); - ++R; - } else { - if (Intersection) - Intersection->add(LRange.getLow(), LCluster.second); - ++L; - ++R; - } - } - - if (L != Items.end()) { - if (LExclude) - do { - LExclude->add(L->first, L->second); - ++L; - } while (L != Items.end()); - } else if (R != RHS.Items.end()) { - if (RExclude) - do { - RExclude->add(R->first, R->second); - ++R; - } while (R != RHS.Items.end()); - } - } public: @@ -282,7 +259,9 @@ public: typedef std::list Cases; typedef typename Cases::iterator CasesIt; - IntegersSubsetMapping() : SingleNumbersOnly(true) {} + IntegersSubsetMapping() { + Sorted = false; + } bool verify() { RangeIterator DummyErrItem; @@ -292,6 +271,7 @@ public: bool verify(RangeIterator& errItem) { if (Items.empty()) return true; + sort(); for (CaseItemIt j = Items.begin(), i = j++, e = Items.end(); j != e; i = j++) { if (isIntersected(i, j) && i->second != j->second) { @@ -332,17 +312,18 @@ public: void optimize() { if (Items.size() < 2) return; + sort(); CaseItems OldItems = Items; Items.clear(); const IntTy *Low = &OldItems.begin()->first.getLow(); const IntTy *High = &OldItems.begin()->first.getHigh(); - unsigned Weight = 1; + unsigned Weight = OldItems.begin()->first.Weight; SuccessorClass *Successor = OldItems.begin()->second; 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; + Weight += j->first.Weight; if (*CurHigh > *High) High = CurHigh; } else { @@ -350,12 +331,14 @@ public: add(R, Successor); Low = &j->first.getLow(); High = &j->first.getHigh(); - Weight = 1; + Weight = j->first.Weight; Successor = j->second; } } RangeEx R(*Low, *High, Weight); add(R, Successor); + // We recollected the Items, but we kept it sorted. + Sorted = true; } /// Adds a constant value. @@ -374,24 +357,28 @@ public: add(REx, S); } void add(const RangeEx &R, SuccessorClass *S = 0) { - Items.insert(std::make_pair(R, S)); - if (!R.isSingleNumber()) - SingleNumbersOnly = false; + Items.push_back(std::make_pair(R, S)); + Sorted = false; } /// Adds all ranges and values from given ranges set to the current /// mapping. - void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) { + void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0, + unsigned Weight = 0) { + unsigned ItemWeight = 1; + if (Weight) + // Weight is associated with CRS, for now we perform a division to + // get the weight for each item. + ItemWeight = Weight / CRS.getNumItems(); for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) { RangeTy R = CRS.getItem(i); - add(R, S); + RangeEx REx(R, ItemWeight); + add(REx, S); } } void add(self& RHS) { - Items.insert(RHS.Items.begin(), RHS.Items.end()); - if (!RHS.SingleNumbersOnly) - SingleNumbersOnly = false; + Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end()); } void add(self& RHS, SuccessorClass *S) { @@ -442,16 +429,10 @@ public: void diff(self *LExclude, self *Intersection, self *RExclude, const self& RHS) { - if (SingleNumbersOnly && RHS.SingleNumbersOnly) { - diff_single_numbers(LExclude, Intersection, RExclude, RHS); - return; - } - DiffStateMachine Machine(LExclude, Intersection, RExclude); CaseItemConstIt L = Items.begin(), R = RHS.Items.begin(); - CaseItemConstIt el = Items.end(), er = RHS.Items.end(); - while (L != el && R != er) { + while (L != Items.end() && R != RHS.Items.end()) { const Cluster &LCluster = *L; const RangeEx &LRange = LCluster.first; const Cluster &RCluster = *R; @@ -471,35 +452,6 @@ public: continue; } - if (LRange.isSingleNumber() && RRange.isSingleNumber()) { - Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second); - Machine.onLRClose(LRange.getLow()); - ++L; - ++R; - continue; - } - - if (LRange.isSingleNumber()) { - Machine.onLOpen(LRange.getLow(), LCluster.second); - Machine.onLClose(LRange.getLow()); - ++L; - while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) { - Machine.onLOpen(LRange.getLow(), LCluster.second); - Machine.onLClose(LRange.getLow()); - ++L; - } - continue; - } else if (RRange.isSingleNumber()) { - Machine.onROpen(R->first.getLow(), R->second); - Machine.onRClose(R->first.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; - } - continue; - } else if (LRange.getLow() < RRange.getLow()) { // May be opened in previous iteration. if (!Machine.isLOpened())