1 //===- IntegersSubsetMapping.h - Mapping subset ==> Successor ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
18 //===----------------------------------------------------------------------===//
23 #include "llvm/Support/IntegersSubset.h"
30 template <class SuccessorClass,
31 class IntegersSubsetTy = IntegersSubset,
32 class IntTy = IntItem>
33 class IntegersSubsetMapping {
36 typedef IntRange<IntTy> RangeTy;
38 struct RangeEx : public RangeTy {
39 RangeEx() : Weight(1) {}
40 RangeEx(const RangeTy &R) : RangeTy(R), Weight(1) {}
41 RangeEx(const IntTy &C) : RangeTy(C), Weight(1) {}
42 RangeEx(const IntTy &L, const IntTy &H) : RangeTy(L, H), Weight(1) {}
43 RangeEx(const IntTy &L, const IntTy &H, unsigned W) :
44 RangeTy(L, H), Weight(W) {}
48 typedef std::pair<RangeEx, SuccessorClass*> Cluster;
52 typedef std::list<Cluster> CaseItems;
53 typedef typename CaseItems::iterator CaseItemIt;
54 typedef typename CaseItems::const_iterator CaseItemConstIt;
56 typedef std::list<RangeTy> RangesCollection;
57 typedef typename RangesCollection::iterator RangesCollectionIt;
59 // TODO: Change unclean CRS prefixes to SubsetMap for example.
60 typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
61 typedef typename CRSMap::iterator CRSMapIt;
64 bool operator()(const Cluster &C1, const Cluster &C2) {
65 return C1.first < C2.first;
69 struct ClusterLefterThan {
70 bool operator()(const Cluster &C, const RangeTy &R) {
71 return C.first.getHigh() < R.getLow();
78 bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
79 return LItem->first.getHigh() >= RItem->first.getLow();
82 bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
83 if (LItem->second != RItem->second) {
84 assert(!isIntersected(LItem, RItem) &&
85 "Intersected items with different successors!");
88 APInt RLow = RItem->first.getLow();
89 if (RLow != APInt::getNullValue(RLow.getBitWidth()))
91 return LItem->first.getHigh() >= RLow;
96 std::vector<Cluster> clustersVector;
97 clustersVector.reserve(Items.size());
98 clustersVector.insert(clustersVector.begin(), Items.begin(), Items.end());
99 std::sort(clustersVector.begin(), clustersVector.end(), ClustersCmp());
101 Items.insert(Items.begin(), clustersVector.begin(), clustersVector.end());
106 void exclude(CaseItemIt &beginIt, RangeTy &R) {
108 std::list<CaseItemIt> ToBeErased;
110 CaseItemIt endIt = Items.end();
112 std::lower_bound(beginIt, Items.end(), R, ClusterLefterThan());
117 if (It->first.getLow() < R.getLow())
118 Items.insert(It, std::make_pair(
119 RangeTy(It->first.getLow(), R.getLow()-1),
123 ToBeErased.push_back(It++);
124 while (It != endIt && It->first.getLow() <= R.getHigh());
128 CaseItemIt &LastRemoved = *(--ToBeErased.end());
129 if (LastRemoved->first.getHigh() > R.getHigh())
130 beginIt = Items.insert(LastRemoved, std::make_pair(
131 RangeTy(R.getHigh() + 1, LastRemoved->first.getHigh()),
135 for (typename std::list<CaseItemIt>::iterator i = ToBeErased.begin(),
136 e = ToBeErased.end(); i != e; ++i)
142 // Don't public CaseItems itself. Don't allow edit the Items directly.
143 // Just present the user way to iterate over the internal collection
144 // sharing iterator, begin() and end(). Editing should be controlled by
146 typedef CaseItemIt RangeIterator;
148 typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
149 typedef std::list<Case> Cases;
151 IntegersSubsetMapping() {
155 bool verify(RangeIterator& errItem) {
159 for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
161 if (isIntersected(i, j) && i->second != j->second) {
170 if (Items.size() < 2)
173 CaseItems OldItems = Items;
175 const IntTy *Low = &OldItems.begin()->first.getLow();
176 const IntTy *High = &OldItems.begin()->first.getHigh();
178 SuccessorClass *Successor = OldItems.begin()->second;
179 for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
181 if (isJoinable(i, j)) {
182 const IntTy *CurHigh = &j->first.getHigh();
184 if (*CurHigh > *High)
187 RangeEx R(*Low, *High, Weight);
189 Low = &j->first.getLow();
190 High = &j->first.getHigh();
192 Successor = j->second;
195 RangeEx R(*Low, *High, Weight);
197 // We recollected the Items, but we kept it sorted.
201 /// Adds a constant value.
202 void add(const IntTy &C, SuccessorClass *S = 0) {
208 void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
209 RangeTy R(Low, High);
212 void add(const RangeTy &R, SuccessorClass *S = 0) {
216 void add(const RangeEx &R, SuccessorClass *S = 0) {
217 Items.push_back(std::make_pair(R, S));
221 /// Adds all ranges and values from given ranges set to the current
223 void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
224 for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
225 RangeTy R = CRS.getItem(i);
230 /// Removes items from set.
231 void removeItem(RangeIterator i) { Items.erase(i); }
233 // Excludes RHS subset from current mapping. RHS should consists of non
234 // overlapped ranges only and sorted from left to the right.
235 // method will have unpredictional behaviour in another case.
236 void exclude(IntegersSubsetTy &RHS) {
237 CaseItemIt startIt = begin();
238 for (unsigned i = 0, e = RHS.getNumItems();
239 i != e && startIt != end(); ++i) {
240 RangeTy R = RHS.getItem(i);
245 /// Builds the finalized case objects.
246 void getCases(Cases& TheCases) {
248 for (RangeIterator i = this->begin(); i != this->end(); ++i)
249 TheCRSMap[i->second].push_back(i->first);
250 for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
251 TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
254 /// Builds the finalized case objects ignoring successor values, as though
255 /// all ranges belongs to the same successor.
256 IntegersSubsetTy getCase() {
257 RangesCollection Ranges;
258 for (RangeIterator i = this->begin(); i != this->end(); ++i)
259 Ranges.push_back(i->first);
260 return IntegersSubsetTy(Ranges);
263 /// Returns true if there is no ranges and values inside.
264 bool empty() const { return Items.empty(); }
268 // Don't reset Sorted flag:
269 // 1. For empty mapping it matters nothing.
270 // 2. After first item will added Sorted flag will cleared.
273 RangeIterator begin() { return Items.begin(); }
274 RangeIterator end() { return Items.end(); }
278 typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
282 #endif /* CRSBUILDER_H_ */