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 {
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.
40 typedef IntRange<IntTy> RangeTy;
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) {}
52 typedef std::pair<RangeEx, SuccessorClass*> Cluster;
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;
61 typedef std::list<Cluster> CaseItems;
62 typedef typename CaseItems::iterator CaseItemIt;
63 typedef typename CaseItems::const_iterator CaseItemConstIt;
65 // TODO: Change unclean CRS prefixes to SubsetMap for example.
66 typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
67 typedef typename CRSMap::iterator CRSMapIt;
70 bool operator()(const Cluster &C1, const Cluster &C2) {
71 return C1.first < C2.first;
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 enum DiffProcessState {
113 class DiffStateMachine {
115 DiffProcessState State;
117 SuccessorClass *CurrentLSuccessor;
118 SuccessorClass *CurrentRSuccessor;
121 self *IntersectionMapping;
127 IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> MappingTy;
129 DiffStateMachine(MappingTy *L,
130 MappingTy *Intersection,
132 State(ALL_IS_CLOSED),
134 IntersectionMapping(Intersection),
138 void onLOpen(const IntTy &Pt, SuccessorClass *S) {
141 if (Pt > OpenPt/*Don't add empty ranges.*/ && RightMapping)
142 RightMapping->add(OpenPt, Pt-1, CurrentRSuccessor);
143 State = INTERSECT_OPENED;
149 assert(0 && "Got unexpected point.");
152 CurrentLSuccessor = S;
156 void onLClose(const IntTy &Pt) {
159 assert(Pt >= OpenPt &&
160 "Subset is not sorted or contains overlapped ranges");
162 LeftMapping->add(OpenPt, Pt, CurrentLSuccessor);
163 State = ALL_IS_CLOSED;
165 case INTERSECT_OPENED:
166 if (IntersectionMapping)
167 IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
172 assert(0 && "Got unexpected point.");
177 void onROpen(const IntTy &Pt, SuccessorClass *S) {
180 if (Pt > OpenPt && LeftMapping)
181 LeftMapping->add(OpenPt, Pt-1, CurrentLSuccessor);
182 State = INTERSECT_OPENED;
188 assert(0 && "Got unexpected point.");
191 CurrentRSuccessor = S;
195 void onRClose(const IntTy &Pt) {
198 assert(Pt >= OpenPt &&
199 "Subset is not sorted or contains overlapped ranges");
201 RightMapping->add(OpenPt, Pt, CurrentRSuccessor);
202 State = ALL_IS_CLOSED;
204 case INTERSECT_OPENED:
205 if (IntersectionMapping)
206 IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
211 assert(0 && "Got unexpected point.");
216 void onLROpen(const IntTy &Pt,
218 SuccessorClass *RS) {
221 State = INTERSECT_OPENED;
224 assert(0 && "Got unexpected point.");
227 CurrentLSuccessor = LS;
228 CurrentRSuccessor = RS;
232 void onLRClose(const IntTy &Pt) {
234 case INTERSECT_OPENED:
235 if (IntersectionMapping)
236 IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
237 State = ALL_IS_CLOSED;
240 assert(0 && "Got unexpected point.");
245 bool isLOpened() { return State == L_OPENED; }
246 bool isROpened() { return State == R_OPENED; }
251 // Don't public CaseItems itself. Don't allow edit the Items directly.
252 // Just present the user way to iterate over the internal collection
253 // sharing iterator, begin() and end(). Editing should be controlled by
255 typedef CaseItemIt RangeIterator;
257 typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
258 typedef std::list<Case> Cases;
259 typedef typename Cases::iterator CasesIt;
261 IntegersSubsetMapping() {
266 RangeIterator DummyErrItem;
267 return verify(DummyErrItem);
270 bool verify(RangeIterator& errItem) {
274 for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
276 if (isIntersected(i, j) && i->second != j->second) {
284 bool isOverlapped(self &RHS) {
285 if (Items.empty() || RHS.empty())
288 for (CaseItemIt L = Items.begin(), R = RHS.Items.begin(),
289 el = Items.end(), er = RHS.Items.end(); L != el && R != er;) {
291 const RangeTy &LRange = L->first;
292 const RangeTy &RRange = R->first;
294 if (LRange.getLow() > RRange.getLow()) {
295 if (RRange.isSingleNumber() || LRange.getLow() > RRange.getHigh())
299 } else if (LRange.getLow() < RRange.getLow()) {
300 if (LRange.isSingleNumber() || LRange.getHigh() < RRange.getLow())
304 } else // iRange.getLow() == jRange.getLow()
312 if (Items.size() < 2)
315 CaseItems OldItems = Items;
317 const IntTy *Low = &OldItems.begin()->first.getLow();
318 const IntTy *High = &OldItems.begin()->first.getHigh();
320 SuccessorClass *Successor = OldItems.begin()->second;
321 for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
323 if (isJoinable(i, j)) {
324 const IntTy *CurHigh = &j->first.getHigh();
326 if (*CurHigh > *High)
329 RangeEx R(*Low, *High, Weight);
331 Low = &j->first.getLow();
332 High = &j->first.getHigh();
334 Successor = j->second;
337 RangeEx R(*Low, *High, Weight);
339 // We recollected the Items, but we kept it sorted.
343 /// Adds a constant value.
344 void add(const IntTy &C, SuccessorClass *S = 0) {
350 void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
351 RangeTy R(Low, High);
354 void add(const RangeTy &R, SuccessorClass *S = 0) {
358 void add(const RangeEx &R, SuccessorClass *S = 0) {
359 Items.push_back(std::make_pair(R, S));
363 /// Adds all ranges and values from given ranges set to the current
365 void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
366 for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
367 RangeTy R = CRS.getItem(i);
372 void add(self& RHS) {
373 Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
376 void add(self& RHS, SuccessorClass *S) {
377 for (CaseItemIt i = RHS.Items.begin(), e = RHS.Items.end(); i != e; ++i)
381 void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
382 for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
386 /// Removes items from set.
387 void removeItem(RangeIterator i) { Items.erase(i); }
389 /// Moves whole case from current mapping to the NewMapping object.
390 void detachCase(self& NewMapping, SuccessorClass *Succ) {
391 for (CaseItemIt i = Items.begin(); i != Items.end();)
392 if (i->second == Succ) {
393 NewMapping.add(i->first, i->second);
399 /// Removes all clusters for given successor.
400 void removeCase(SuccessorClass *Succ) {
401 for (CaseItemIt i = Items.begin(); i != Items.end();)
402 if (i->second == Succ) {
408 /// Find successor that satisfies given value.
409 SuccessorClass *findSuccessor(const IntTy& Val) {
410 for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) {
411 if (i->first.isInRange(Val))
417 /// Calculates the difference between this mapping and RHS.
418 /// THIS without RHS is placed into LExclude,
419 /// RHS without THIS is placed into RExclude,
420 /// THIS intersect RHS is placed into Intersection.
421 void diff(self *LExclude, self *Intersection, self *RExclude,
424 DiffStateMachine Machine(LExclude, Intersection, RExclude);
426 CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
427 while (L != Items.end() && R != RHS.Items.end()) {
428 const Cluster &LCluster = *L;
429 const RangeEx &LRange = LCluster.first;
430 const Cluster &RCluster = *R;
431 const RangeEx &RRange = RCluster.first;
433 if (LRange.getHigh() < RRange.getLow()) {
434 Machine.onLOpen(LRange.getLow(), LCluster.second);
435 Machine.onLClose(LRange.getHigh());
440 if (LRange.getLow() > RRange.getHigh()) {
441 Machine.onROpen(RRange.getLow(), RCluster.second);
442 Machine.onRClose(RRange.getHigh());
447 if (LRange.getLow() < RRange.getLow()) {
448 // May be opened in previous iteration.
449 if (!Machine.isLOpened())
450 Machine.onLOpen(LRange.getLow(), LCluster.second);
451 Machine.onROpen(RRange.getLow(), RCluster.second);
453 else if (RRange.getLow() < LRange.getLow()) {
454 if (!Machine.isROpened())
455 Machine.onROpen(RRange.getLow(), RCluster.second);
456 Machine.onLOpen(LRange.getLow(), LCluster.second);
459 Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
461 if (LRange.getHigh() < RRange.getHigh()) {
462 Machine.onLClose(LRange.getHigh());
464 while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
465 Machine.onLOpen(L->first.getLow(), L->second);
466 Machine.onLClose(L->first.getHigh());
470 else if (RRange.getHigh() < LRange.getHigh()) {
471 Machine.onRClose(RRange.getHigh());
473 while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
474 Machine.onROpen(R->first.getLow(), R->second);
475 Machine.onRClose(R->first.getHigh());
480 Machine.onLRClose(LRange.getHigh());
486 if (L != Items.end()) {
487 if (Machine.isLOpened()) {
488 Machine.onLClose(L->first.getHigh());
492 while (L != Items.end()) {
493 LExclude->add(L->first, L->second);
496 } else if (R != RHS.Items.end()) {
497 if (Machine.isROpened()) {
498 Machine.onRClose(R->first.getHigh());
502 while (R != RHS.Items.end()) {
503 RExclude->add(R->first, R->second);
509 /// Builds the finalized case objects.
510 void getCases(Cases& TheCases, bool PreventMerging = false) {
511 //FIXME: PreventMerging is a temporary parameter.
512 //Currently a set of passes is still knows nothing about
513 //switches with case ranges, and if these passes meet switch
514 //with complex case that crashs the application.
515 if (PreventMerging) {
516 for (RangeIterator i = this->begin(); i != this->end(); ++i) {
517 RangesCollection SingleRange;
518 SingleRange.push_back(i->first);
519 TheCases.push_back(std::make_pair(i->second,
520 IntegersSubsetTy(SingleRange)));
525 for (RangeIterator i = this->begin(); i != this->end(); ++i)
526 TheCRSMap[i->second].push_back(i->first);
527 for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
528 TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
531 /// Builds the finalized case objects ignoring successor values, as though
532 /// all ranges belongs to the same successor.
533 IntegersSubsetTy getCase() {
534 RangesCollection Ranges;
535 for (RangeIterator i = this->begin(); i != this->end(); ++i)
536 Ranges.push_back(i->first);
537 return IntegersSubsetTy(Ranges);
540 /// Returns pointer to value of case if it is single-numbered or 0
542 const IntTy* getCaseSingleNumber(SuccessorClass *Succ) {
543 const IntTy* Res = 0;
544 for (CaseItemIt i = Items.begin(); i != Items.end(); ++i)
545 if (i->second == Succ) {
546 if (!i->first.isSingleNumber())
551 Res = &(i->first.getLow());
556 /// Returns true if there is no ranges and values inside.
557 bool empty() const { return Items.empty(); }
561 // Don't reset Sorted flag:
562 // 1. For empty mapping it matters nothing.
563 // 2. After first item will added Sorted flag will cleared.
566 // Returns number of clusters
567 unsigned size() const {
571 RangeIterator begin() { return Items.begin(); }
572 RangeIterator end() { return Items.end(); }
576 typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
580 #endif /* CRSBUILDER_H_ */