IntegersSubsetMapping.h revision 66d79cefcb742bdbfef8823ac8491a7ebc4af5a7 
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 CRSBUILDER_H_
21#define CRSBUILDER_H_
22
23#include "llvm/Support/IntegersSubset.h"
24#include <list>
25#include <map>
26#include <vector>
27
28namespace llvm {
29
30template <class SuccessorClass,
31          class IntegersSubsetTy = IntegersSubset,
32          class IntTy = IntItem>
33class 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.
38public:
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 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) {}
49    unsigned Weight;
50  };
51
52  typedef std::pair<RangeEx, SuccessorClass*> Cluster;
53
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;
58
59protected:
60
61  typedef std::list<Cluster> CaseItems;
62  typedef typename CaseItems::iterator CaseItemIt;
63  typedef typename CaseItems::const_iterator CaseItemConstIt;
64
65  // TODO: Change unclean CRS prefixes to SubsetMap for example.
66  typedef std::map<SuccessorClass*, RangesCollection > CRSMap;
67  typedef typename CRSMap::iterator CRSMapIt;
68
69  struct ClustersCmp {
70    bool operator()(const Cluster &C1, const Cluster &C2) {
71      return C1.first < C2.first;
72    }
73  };
74
75  CaseItems Items;
76  bool Sorted;
77  bool SingleNumbersOnly;
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  void diff_single_numbers(self *LExclude, self *Intersection, self *RExclude,
251                               const self& RHS) {
252
253    CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
254    CaseItemConstIt el = Items.end(), er = RHS.Items.end();
255    while (L != el && R != er) {
256      const Cluster &LCluster = *L;
257      const RangeEx &LRange = LCluster.first;
258      const Cluster &RCluster = *R;
259      const RangeEx &RRange = RCluster.first;
260
261      if (LRange.getLow() < RRange.getLow()) {
262        if (LExclude)
263          LExclude->add(LRange.getLow(), LCluster.second);
264        ++L;
265      } else if (LRange.getLow() > RRange.getLow()) {
266        if (RExclude)
267          RExclude->add(RRange.getLow(), RCluster.second);
268        ++R;
269      } else {
270        if (Intersection)
271          Intersection->add(LRange.getLow(), LCluster.second);
272        ++L;
273        ++R;
274      }
275    }
276
277    if (L != Items.end()) {
278      if (LExclude)
279        do {
280            LExclude->add(L->first, L->second);
281            ++L;
282        } while (L != Items.end());
283    } else if (R != RHS.Items.end()) {
284      if (RExclude)
285        do {
286          RExclude->add(R->first, R->second);
287          ++R;
288        } while (R != RHS.Items.end());
289    }
290  }
291
292public:
293
294  // Don't public CaseItems itself. Don't allow edit the Items directly.
295  // Just present the user way to iterate over the internal collection
296  // sharing iterator, begin() and end(). Editing should be controlled by
297  // factory.
298  typedef CaseItemIt RangeIterator;
299
300  typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
301  typedef std::list<Case> Cases;
302  typedef typename Cases::iterator CasesIt;
303
304  IntegersSubsetMapping() {
305    Sorted = false;
306    SingleNumbersOnly = true;
307  }
308
309  bool verify() {
310    RangeIterator DummyErrItem;
311    return verify(DummyErrItem);
312  }
313
314  bool verify(RangeIterator& errItem) {
315    if (Items.empty())
316      return true;
317    sort();
318    for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
319         j != e; i = j++) {
320      if (isIntersected(i, j) && i->second != j->second) {
321        errItem = j;
322        return false;
323      }
324    }
325    return true;
326  }
327
328  bool isOverlapped(self &RHS) {
329    if (Items.empty() || RHS.empty())
330      return true;
331
332    for (CaseItemIt L = Items.begin(), R = RHS.Items.begin(),
333         el = Items.end(), er = RHS.Items.end(); L != el && R != er;) {
334
335      const RangeTy &LRange = L->first;
336      const RangeTy &RRange = R->first;
337
338      if (LRange.getLow() > RRange.getLow()) {
339        if (RRange.isSingleNumber() || LRange.getLow() > RRange.getHigh())
340          ++R;
341        else
342          return true;
343      } else if (LRange.getLow() < RRange.getLow()) {
344        if (LRange.isSingleNumber() || LRange.getHigh() < RRange.getLow())
345          ++L;
346        else
347          return true;
348      } else // iRange.getLow() == jRange.getLow()
349        return true;
350    }
351    return false;
352  }
353
354
355  void optimize() {
356    if (Items.size() < 2)
357      return;
358    sort();
359    CaseItems OldItems = Items;
360    Items.clear();
361    const IntTy *Low = &OldItems.begin()->first.getLow();
362    const IntTy *High = &OldItems.begin()->first.getHigh();
363    unsigned Weight = 1;
364    SuccessorClass *Successor = OldItems.begin()->second;
365    for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
366         j != e; i = j++) {
367      if (isJoinable(i, j)) {
368        const IntTy *CurHigh = &j->first.getHigh();
369        ++Weight;
370        if (*CurHigh > *High)
371          High = CurHigh;
372      } else {
373        RangeEx R(*Low, *High, Weight);
374        add(R, Successor);
375        Low = &j->first.getLow();
376        High = &j->first.getHigh();
377        Weight = 1;
378        Successor = j->second;
379      }
380    }
381    RangeEx R(*Low, *High, Weight);
382    add(R, Successor);
383    // We recollected the Items, but we kept it sorted.
384    Sorted = true;
385  }
386
387  /// Adds a constant value.
388  void add(const IntTy &C, SuccessorClass *S = 0) {
389    RangeTy R(C);
390    add(R, S);
391  }
392
393  /// Adds a range.
394  void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
395    RangeTy R(Low, High);
396    add(R, S);
397  }
398  void add(const RangeTy &R, SuccessorClass *S = 0) {
399    RangeEx REx = R;
400    add(REx, S);
401  }
402  void add(const RangeEx &R, SuccessorClass *S = 0) {
403    Items.push_back(std::make_pair(R, S));
404    if (!R.isSingleNumber())
405      SingleNumbersOnly = false;
406  }
407
408  /// Adds all ranges and values from given ranges set to the current
409  /// mapping.
410  void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
411    for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
412      RangeTy R = CRS.getItem(i);
413      add(R, S);
414    }
415  }
416
417  void add(self& RHS) {
418    Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end());
419    if (!RHS.SingleNumbersOnly)
420      SingleNumbersOnly = false;
421  }
422
423  void add(self& RHS, SuccessorClass *S) {
424    for (CaseItemIt i = RHS.Items.begin(), e = RHS.Items.end(); i != e; ++i)
425      add(i->first, S);
426  }
427
428  void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
429    for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
430      add(*i, S);
431  }
432
433  /// Removes items from set.
434  void removeItem(RangeIterator i) { Items.erase(i); }
435
436  /// Moves whole case from current mapping to the NewMapping object.
437  void detachCase(self& NewMapping, SuccessorClass *Succ) {
438    for (CaseItemIt i = Items.begin(); i != Items.end();)
439      if (i->second == Succ) {
440        NewMapping.add(i->first, i->second);
441        Items.erase(i++);
442      } else
443        ++i;
444  }
445
446  /// Removes all clusters for given successor.
447  void removeCase(SuccessorClass *Succ) {
448    for (CaseItemIt i = Items.begin(); i != Items.end();)
449      if (i->second == Succ) {
450        Items.erase(i++);
451      } else
452        ++i;
453  }
454
455  /// Find successor that satisfies given value.
456  SuccessorClass *findSuccessor(const IntTy& Val) {
457    for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) {
458      if (i->first.isInRange(Val))
459        return i->second;
460    }
461    return 0;
462  }
463
464  /// Calculates the difference between this mapping and RHS.
465  /// THIS without RHS is placed into LExclude,
466  /// RHS without THIS is placed into RExclude,
467  /// THIS intersect RHS is placed into Intersection.
468  void diff(self *LExclude, self *Intersection, self *RExclude,
469                             const self& RHS) {
470
471    if (SingleNumbersOnly && RHS.SingleNumbersOnly) {
472      diff_single_numbers(LExclude, Intersection, RExclude, RHS);
473      return;
474    }
475
476    DiffStateMachine Machine(LExclude, Intersection, RExclude);
477
478    CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
479    CaseItemConstIt el = Items.end(), er = RHS.Items.end();
480    while (L != el && R != er) {
481      const Cluster &LCluster = *L;
482      const RangeEx &LRange = LCluster.first;
483      const Cluster &RCluster = *R;
484      const RangeEx &RRange = RCluster.first;
485
486      if (LRange.getHigh() < RRange.getLow()) {
487        Machine.onLOpen(LRange.getLow(), LCluster.second);
488        Machine.onLClose(LRange.getHigh());
489        ++L;
490        continue;
491      }
492
493      if (LRange.getLow() > RRange.getHigh()) {
494        Machine.onROpen(RRange.getLow(), RCluster.second);
495        Machine.onRClose(RRange.getHigh());
496        ++R;
497        continue;
498      }
499
500      if (LRange.isSingleNumber() && RRange.isSingleNumber()) {
501        Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
502        Machine.onLRClose(LRange.getLow());
503        ++L;
504        ++R;
505        continue;
506      }
507
508      if (LRange.isSingleNumber()) {
509        Machine.onLOpen(LRange.getLow(), LCluster.second);
510        Machine.onLClose(LRange.getLow());
511        ++L;
512        while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
513          Machine.onLOpen(LRange.getLow(), LCluster.second);
514          Machine.onLClose(LRange.getLow());
515          ++L;
516        }
517        continue;
518      } else if (RRange.isSingleNumber()) {
519        Machine.onROpen(R->first.getLow(), R->second);
520        Machine.onRClose(R->first.getHigh());
521        ++R;
522        while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
523          Machine.onROpen(R->first.getLow(), R->second);
524          Machine.onRClose(R->first.getHigh());
525          ++R;
526        }
527        continue;
528      } else
529      if (LRange.getLow() < RRange.getLow()) {
530        // May be opened in previous iteration.
531        if (!Machine.isLOpened())
532          Machine.onLOpen(LRange.getLow(), LCluster.second);
533        Machine.onROpen(RRange.getLow(), RCluster.second);
534      }
535      else if (RRange.getLow() < LRange.getLow()) {
536        if (!Machine.isROpened())
537          Machine.onROpen(RRange.getLow(), RCluster.second);
538        Machine.onLOpen(LRange.getLow(), LCluster.second);
539      }
540      else
541        Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
542
543      if (LRange.getHigh() < RRange.getHigh()) {
544        Machine.onLClose(LRange.getHigh());
545        ++L;
546        while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
547          Machine.onLOpen(L->first.getLow(), L->second);
548          Machine.onLClose(L->first.getHigh());
549          ++L;
550        }
551      }
552      else if (RRange.getHigh() < LRange.getHigh()) {
553        Machine.onRClose(RRange.getHigh());
554        ++R;
555        while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
556          Machine.onROpen(R->first.getLow(), R->second);
557          Machine.onRClose(R->first.getHigh());
558          ++R;
559        }
560      }
561      else {
562        Machine.onLRClose(LRange.getHigh());
563        ++L;
564        ++R;
565      }
566    }
567
568    if (L != Items.end()) {
569      if (Machine.isLOpened()) {
570        Machine.onLClose(L->first.getHigh());
571        ++L;
572      }
573      if (LExclude)
574        while (L != Items.end()) {
575          LExclude->add(L->first, L->second);
576          ++L;
577        }
578    } else if (R != RHS.Items.end()) {
579      if (Machine.isROpened()) {
580        Machine.onRClose(R->first.getHigh());
581        ++R;
582      }
583      if (RExclude)
584        while (R != RHS.Items.end()) {
585          RExclude->add(R->first, R->second);
586          ++R;
587        }
588    }
589  }
590
591  /// Builds the finalized case objects.
592  void getCases(Cases& TheCases, bool PreventMerging = false) {
593    //FIXME: PreventMerging is a temporary parameter.
594    //Currently a set of passes is still knows nothing about
595    //switches with case ranges, and if these passes meet switch
596    //with complex case that crashs the application.
597    if (PreventMerging) {
598      for (RangeIterator i = this->begin(); i != this->end(); ++i) {
599        RangesCollection SingleRange;
600        SingleRange.push_back(i->first);
601        TheCases.push_back(std::make_pair(i->second,
602                                          IntegersSubsetTy(SingleRange)));
603      }
604      return;
605    }
606    CRSMap TheCRSMap;
607    for (RangeIterator i = this->begin(); i != this->end(); ++i)
608      TheCRSMap[i->second].push_back(i->first);
609    for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
610      TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
611  }
612
613  /// Builds the finalized case objects ignoring successor values, as though
614  /// all ranges belongs to the same successor.
615  IntegersSubsetTy getCase() {
616    RangesCollection Ranges;
617    for (RangeIterator i = this->begin(); i != this->end(); ++i)
618      Ranges.push_back(i->first);
619    return IntegersSubsetTy(Ranges);
620  }
621
622  /// Returns pointer to value of case if it is single-numbered or 0
623  /// in another case.
624  const IntTy* getCaseSingleNumber(SuccessorClass *Succ) {
625    const IntTy* Res = 0;
626    for (CaseItemIt i = Items.begin(); i != Items.end(); ++i)
627      if (i->second == Succ) {
628        if (!i->first.isSingleNumber())
629          return 0;
630        if (Res)
631          return 0;
632        else
633          Res = &(i->first.getLow());
634      }
635    return Res;
636  }
637
638  /// Returns true if there is no ranges and values inside.
639  bool empty() const { return Items.empty(); }
640
641  void clear() {
642    Items.clear();
643    // Don't reset Sorted flag:
644    // 1. For empty mapping it matters nothing.
645    // 2. After first item will added Sorted flag will cleared.
646  }
647
648  // Returns number of clusters
649  unsigned size() const {
650    return Items.size();
651  }
652
653  RangeIterator begin() { return Items.begin(); }
654  RangeIterator end() { return Items.end(); }
655};
656
657class BasicBlock;
658typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
659
660}
661
662#endif /* CRSBUILDER_H_ */
663