IntegersSubsetMapping.h revision 9ccc83e7f70e63b746cbc7eef9fb06022e758677 
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::map<RangeEx, SuccessorClass*> 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  CaseItems Items;
70  bool SingleNumbersOnly;
71
72  bool isIntersected(CaseItemIt& LItem, CaseItemIt& RItem) {
73    return LItem->first.getHigh() >= RItem->first.getLow();
74  }
75
76  bool isJoinable(CaseItemIt& LItem, CaseItemIt& RItem) {
77    if (LItem->second != RItem->second) {
78      assert(!isIntersected(LItem, RItem) &&
79             "Intersected items with different successors!");
80      return false;
81    }
82    APInt RLow = RItem->first.getLow();
83    if (RLow != APInt::getNullValue(RLow.getBitWidth()))
84      --RLow;
85    return LItem->first.getHigh() >= RLow;
86  }
87
88  enum DiffProcessState {
89    L_OPENED,
90    INTERSECT_OPENED,
91    R_OPENED,
92    ALL_IS_CLOSED
93  };
94
95  class DiffStateMachine {
96
97    DiffProcessState State;
98    IntTy OpenPt;
99    SuccessorClass *CurrentLSuccessor;
100    SuccessorClass *CurrentRSuccessor;
101
102    self *LeftMapping;
103    self *IntersectionMapping;
104    self *RightMapping;
105
106  public:
107
108    typedef
109      IntegersSubsetMapping<SuccessorClass, IntegersSubsetTy, IntTy> MappingTy;
110
111    DiffStateMachine(MappingTy *L,
112                                 MappingTy *Intersection,
113                                 MappingTy *R) :
114                                 State(ALL_IS_CLOSED),
115                                 LeftMapping(L),
116                                 IntersectionMapping(Intersection),
117                                 RightMapping(R)
118                                 {}
119
120    void onLOpen(const IntTy &Pt, SuccessorClass *S) {
121      switch (State) {
122      case R_OPENED:
123        if (Pt > OpenPt/*Don't add empty ranges.*/ && RightMapping)
124          RightMapping->add(OpenPt, Pt-1, CurrentRSuccessor);
125        State = INTERSECT_OPENED;
126        break;
127      case ALL_IS_CLOSED:
128        State = L_OPENED;
129        break;
130      default:
131        assert(0 && "Got unexpected point.");
132        break;
133      }
134      CurrentLSuccessor = S;
135      OpenPt = Pt;
136    }
137
138    void onLClose(const IntTy &Pt) {
139      switch (State) {
140      case L_OPENED:
141        assert(Pt >= OpenPt &&
142               "Subset is not sorted or contains overlapped ranges");
143        if (LeftMapping)
144          LeftMapping->add(OpenPt, Pt, CurrentLSuccessor);
145        State = ALL_IS_CLOSED;
146        break;
147      case INTERSECT_OPENED:
148        if (IntersectionMapping)
149          IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
150        OpenPt = Pt + 1;
151        State = R_OPENED;
152        break;
153      default:
154        assert(0 && "Got unexpected point.");
155        break;
156      }
157    }
158
159    void onROpen(const IntTy &Pt, SuccessorClass *S) {
160      switch (State) {
161      case L_OPENED:
162        if (Pt > OpenPt && LeftMapping)
163          LeftMapping->add(OpenPt, Pt-1, CurrentLSuccessor);
164        State = INTERSECT_OPENED;
165        break;
166      case ALL_IS_CLOSED:
167        State = R_OPENED;
168        break;
169      default:
170        assert(0 && "Got unexpected point.");
171        break;
172      }
173      CurrentRSuccessor = S;
174      OpenPt = Pt;
175    }
176
177    void onRClose(const IntTy &Pt) {
178      switch (State) {
179      case R_OPENED:
180        assert(Pt >= OpenPt &&
181               "Subset is not sorted or contains overlapped ranges");
182        if (RightMapping)
183          RightMapping->add(OpenPt, Pt, CurrentRSuccessor);
184        State = ALL_IS_CLOSED;
185        break;
186      case INTERSECT_OPENED:
187        if (IntersectionMapping)
188          IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
189        OpenPt = Pt + 1;
190        State = L_OPENED;
191        break;
192      default:
193        assert(0 && "Got unexpected point.");
194        break;
195      }
196    }
197
198    void onLROpen(const IntTy &Pt,
199                  SuccessorClass *LS,
200                  SuccessorClass *RS) {
201      switch (State) {
202      case ALL_IS_CLOSED:
203        State = INTERSECT_OPENED;
204        break;
205      default:
206        assert(0 && "Got unexpected point.");
207        break;
208      }
209      CurrentLSuccessor = LS;
210      CurrentRSuccessor = RS;
211      OpenPt = Pt;
212    }
213
214    void onLRClose(const IntTy &Pt) {
215      switch (State) {
216      case INTERSECT_OPENED:
217        if (IntersectionMapping)
218          IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor);
219        State = ALL_IS_CLOSED;
220        break;
221      default:
222        assert(0 && "Got unexpected point.");
223        break;
224      }
225    }
226
227    bool isLOpened() { return State == L_OPENED; }
228    bool isROpened() { return State == R_OPENED; }
229  };
230
231  void diff_single_numbers(self *LExclude, self *Intersection, self *RExclude,
232                               const self& RHS) {
233
234    CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
235    CaseItemConstIt el = Items.end(), er = RHS.Items.end();
236    while (L != el && R != er) {
237      const Cluster &LCluster = *L;
238      const RangeEx &LRange = LCluster.first;
239      const Cluster &RCluster = *R;
240      const RangeEx &RRange = RCluster.first;
241
242      if (LRange.getLow() < RRange.getLow()) {
243        if (LExclude)
244          LExclude->add(LRange.getLow(), LCluster.second);
245        ++L;
246      } else if (LRange.getLow() > RRange.getLow()) {
247        if (RExclude)
248          RExclude->add(RRange.getLow(), RCluster.second);
249        ++R;
250      } else {
251        if (Intersection)
252          Intersection->add(LRange.getLow(), LCluster.second);
253        ++L;
254        ++R;
255      }
256    }
257
258    if (L != Items.end()) {
259      if (LExclude)
260        do {
261            LExclude->add(L->first, L->second);
262            ++L;
263        } while (L != Items.end());
264    } else if (R != RHS.Items.end()) {
265      if (RExclude)
266        do {
267          RExclude->add(R->first, R->second);
268          ++R;
269        } while (R != RHS.Items.end());
270    }
271  }
272
273public:
274
275  // Don't public CaseItems itself. Don't allow edit the Items directly.
276  // Just present the user way to iterate over the internal collection
277  // sharing iterator, begin() and end(). Editing should be controlled by
278  // factory.
279  typedef CaseItemIt RangeIterator;
280
281  typedef std::pair<SuccessorClass*, IntegersSubsetTy> Case;
282  typedef std::list<Case> Cases;
283  typedef typename Cases::iterator CasesIt;
284
285  IntegersSubsetMapping() : SingleNumbersOnly(true) {}
286
287  bool verify() {
288    RangeIterator DummyErrItem;
289    return verify(DummyErrItem);
290  }
291
292  bool verify(RangeIterator& errItem) {
293    if (Items.empty())
294      return true;
295    for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
296         j != e; i = j++) {
297      if (isIntersected(i, j) && i->second != j->second) {
298        errItem = j;
299        return false;
300      }
301    }
302    return true;
303  }
304
305  bool isOverlapped(self &RHS) {
306    if (Items.empty() || RHS.empty())
307      return true;
308
309    for (CaseItemIt L = Items.begin(), R = RHS.Items.begin(),
310         el = Items.end(), er = RHS.Items.end(); L != el && R != er;) {
311
312      const RangeTy &LRange = L->first;
313      const RangeTy &RRange = R->first;
314
315      if (LRange.getLow() > RRange.getLow()) {
316        if (RRange.isSingleNumber() || LRange.getLow() > RRange.getHigh())
317          ++R;
318        else
319          return true;
320      } else if (LRange.getLow() < RRange.getLow()) {
321        if (LRange.isSingleNumber() || LRange.getHigh() < RRange.getLow())
322          ++L;
323        else
324          return true;
325      } else // iRange.getLow() == jRange.getLow()
326        return true;
327    }
328    return false;
329  }
330
331
332  void optimize() {
333    if (Items.size() < 2)
334      return;
335    CaseItems OldItems = Items;
336    Items.clear();
337    const IntTy *Low = &OldItems.begin()->first.getLow();
338    const IntTy *High = &OldItems.begin()->first.getHigh();
339    unsigned Weight = 1;
340    SuccessorClass *Successor = OldItems.begin()->second;
341    for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
342         j != e; i = j++) {
343      if (isJoinable(i, j)) {
344        const IntTy *CurHigh = &j->first.getHigh();
345        ++Weight;
346        if (*CurHigh > *High)
347          High = CurHigh;
348      } else {
349        RangeEx R(*Low, *High, Weight);
350        add(R, Successor);
351        Low = &j->first.getLow();
352        High = &j->first.getHigh();
353        Weight = 1;
354        Successor = j->second;
355      }
356    }
357    RangeEx R(*Low, *High, Weight);
358    add(R, Successor);
359  }
360
361  /// Adds a constant value.
362  void add(const IntTy &C, SuccessorClass *S = 0) {
363    RangeTy R(C);
364    add(R, S);
365  }
366
367  /// Adds a range.
368  void add(const IntTy &Low, const IntTy &High, SuccessorClass *S = 0) {
369    RangeTy R(Low, High);
370    add(R, S);
371  }
372  void add(const RangeTy &R, SuccessorClass *S = 0) {
373    RangeEx REx = R;
374    add(REx, S);
375  }
376  void add(const RangeEx &R, SuccessorClass *S = 0) {
377    Items.insert(std::make_pair(R, S));
378    if (!R.isSingleNumber())
379      SingleNumbersOnly = false;
380  }
381
382  /// Adds all ranges and values from given ranges set to the current
383  /// mapping.
384  void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
385    for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
386      RangeTy R = CRS.getItem(i);
387      add(R, S);
388    }
389  }
390
391  void add(self& RHS) {
392    Items.insert(RHS.Items.begin(), RHS.Items.end());
393    if (!RHS.SingleNumbersOnly)
394      SingleNumbersOnly = false;
395  }
396
397  void add(self& RHS, SuccessorClass *S) {
398    for (CaseItemIt i = RHS.Items.begin(), e = RHS.Items.end(); i != e; ++i)
399      add(i->first, S);
400  }
401
402  void add(const RangesCollection& RHS, SuccessorClass *S = 0) {
403    for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i)
404      add(*i, S);
405  }
406
407  /// Removes items from set.
408  void removeItem(RangeIterator i) { Items.erase(i); }
409
410  /// Moves whole case from current mapping to the NewMapping object.
411  void detachCase(self& NewMapping, SuccessorClass *Succ) {
412    for (CaseItemIt i = Items.begin(); i != Items.end();)
413      if (i->second == Succ) {
414        NewMapping.add(i->first, i->second);
415        Items.erase(i++);
416      } else
417        ++i;
418  }
419
420  /// Removes all clusters for given successor.
421  void removeCase(SuccessorClass *Succ) {
422    for (CaseItemIt i = Items.begin(); i != Items.end();)
423      if (i->second == Succ) {
424        Items.erase(i++);
425      } else
426        ++i;
427  }
428
429  /// Find successor that satisfies given value.
430  SuccessorClass *findSuccessor(const IntTy& Val) {
431    for (CaseItemIt i = Items.begin(); i != Items.end(); ++i) {
432      if (i->first.isInRange(Val))
433        return i->second;
434    }
435    return 0;
436  }
437
438  /// Calculates the difference between this mapping and RHS.
439  /// THIS without RHS is placed into LExclude,
440  /// RHS without THIS is placed into RExclude,
441  /// THIS intersect RHS is placed into Intersection.
442  void diff(self *LExclude, self *Intersection, self *RExclude,
443                             const self& RHS) {
444
445    if (SingleNumbersOnly && RHS.SingleNumbersOnly) {
446      diff_single_numbers(LExclude, Intersection, RExclude, RHS);
447      return;
448    }
449
450    DiffStateMachine Machine(LExclude, Intersection, RExclude);
451
452    CaseItemConstIt L = Items.begin(), R = RHS.Items.begin();
453    CaseItemConstIt el = Items.end(), er = RHS.Items.end();
454    while (L != el && R != er) {
455      const Cluster &LCluster = *L;
456      const RangeEx &LRange = LCluster.first;
457      const Cluster &RCluster = *R;
458      const RangeEx &RRange = RCluster.first;
459
460      if (LRange.getHigh() < RRange.getLow()) {
461        Machine.onLOpen(LRange.getLow(), LCluster.second);
462        Machine.onLClose(LRange.getHigh());
463        ++L;
464        continue;
465      }
466
467      if (LRange.getLow() > RRange.getHigh()) {
468        Machine.onROpen(RRange.getLow(), RCluster.second);
469        Machine.onRClose(RRange.getHigh());
470        ++R;
471        continue;
472      }
473
474      if (LRange.isSingleNumber() && RRange.isSingleNumber()) {
475        Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
476        Machine.onLRClose(LRange.getLow());
477        ++L;
478        ++R;
479        continue;
480      }
481
482      if (LRange.isSingleNumber()) {
483        Machine.onLOpen(LRange.getLow(), LCluster.second);
484        Machine.onLClose(LRange.getLow());
485        ++L;
486        while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
487          Machine.onLOpen(LRange.getLow(), LCluster.second);
488          Machine.onLClose(LRange.getLow());
489          ++L;
490        }
491        continue;
492      } else if (RRange.isSingleNumber()) {
493        Machine.onROpen(R->first.getLow(), R->second);
494        Machine.onRClose(R->first.getHigh());
495        ++R;
496        while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
497          Machine.onROpen(R->first.getLow(), R->second);
498          Machine.onRClose(R->first.getHigh());
499          ++R;
500        }
501        continue;
502      } else
503      if (LRange.getLow() < RRange.getLow()) {
504        // May be opened in previous iteration.
505        if (!Machine.isLOpened())
506          Machine.onLOpen(LRange.getLow(), LCluster.second);
507        Machine.onROpen(RRange.getLow(), RCluster.second);
508      }
509      else if (RRange.getLow() < LRange.getLow()) {
510        if (!Machine.isROpened())
511          Machine.onROpen(RRange.getLow(), RCluster.second);
512        Machine.onLOpen(LRange.getLow(), LCluster.second);
513      }
514      else
515        Machine.onLROpen(LRange.getLow(), LCluster.second, RCluster.second);
516
517      if (LRange.getHigh() < RRange.getHigh()) {
518        Machine.onLClose(LRange.getHigh());
519        ++L;
520        while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) {
521          Machine.onLOpen(L->first.getLow(), L->second);
522          Machine.onLClose(L->first.getHigh());
523          ++L;
524        }
525      }
526      else if (RRange.getHigh() < LRange.getHigh()) {
527        Machine.onRClose(RRange.getHigh());
528        ++R;
529        while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) {
530          Machine.onROpen(R->first.getLow(), R->second);
531          Machine.onRClose(R->first.getHigh());
532          ++R;
533        }
534      }
535      else {
536        Machine.onLRClose(LRange.getHigh());
537        ++L;
538        ++R;
539      }
540    }
541
542    if (L != Items.end()) {
543      if (Machine.isLOpened()) {
544        Machine.onLClose(L->first.getHigh());
545        ++L;
546      }
547      if (LExclude)
548        while (L != Items.end()) {
549          LExclude->add(L->first, L->second);
550          ++L;
551        }
552    } else if (R != RHS.Items.end()) {
553      if (Machine.isROpened()) {
554        Machine.onRClose(R->first.getHigh());
555        ++R;
556      }
557      if (RExclude)
558        while (R != RHS.Items.end()) {
559          RExclude->add(R->first, R->second);
560          ++R;
561        }
562    }
563  }
564
565  /// Builds the finalized case objects.
566  void getCases(Cases& TheCases, bool PreventMerging = false) {
567    //FIXME: PreventMerging is a temporary parameter.
568    //Currently a set of passes is still knows nothing about
569    //switches with case ranges, and if these passes meet switch
570    //with complex case that crashs the application.
571    if (PreventMerging) {
572      for (RangeIterator i = this->begin(); i != this->end(); ++i) {
573        RangesCollection SingleRange;
574        SingleRange.push_back(i->first);
575        TheCases.push_back(std::make_pair(i->second,
576                                          IntegersSubsetTy(SingleRange)));
577      }
578      return;
579    }
580    CRSMap TheCRSMap;
581    for (RangeIterator i = this->begin(); i != this->end(); ++i)
582      TheCRSMap[i->second].push_back(i->first);
583    for (CRSMapIt i = TheCRSMap.begin(), e = TheCRSMap.end(); i != e; ++i)
584      TheCases.push_back(std::make_pair(i->first, IntegersSubsetTy(i->second)));
585  }
586
587  /// Builds the finalized case objects ignoring successor values, as though
588  /// all ranges belongs to the same successor.
589  IntegersSubsetTy getCase() {
590    RangesCollection Ranges;
591    for (RangeIterator i = this->begin(); i != this->end(); ++i)
592      Ranges.push_back(i->first);
593    return IntegersSubsetTy(Ranges);
594  }
595
596  /// Returns pointer to value of case if it is single-numbered or 0
597  /// in another case.
598  const IntTy* getCaseSingleNumber(SuccessorClass *Succ) {
599    const IntTy* Res = 0;
600    for (CaseItemIt i = Items.begin(); i != Items.end(); ++i)
601      if (i->second == Succ) {
602        if (!i->first.isSingleNumber())
603          return 0;
604        if (Res)
605          return 0;
606        else
607          Res = &(i->first.getLow());
608      }
609    return Res;
610  }
611
612  /// Returns true if there is no ranges and values inside.
613  bool empty() const { return Items.empty(); }
614
615  void clear() {
616    Items.clear();
617    // Don't reset Sorted flag:
618    // 1. For empty mapping it matters nothing.
619    // 2. After first item will added Sorted flag will cleared.
620  }
621
622  // Returns number of clusters
623  unsigned size() const {
624    return Items.size();
625  }
626
627  RangeIterator begin() { return Items.begin(); }
628  RangeIterator end() { return Items.end(); }
629};
630
631class BasicBlock;
632typedef IntegersSubsetMapping<BasicBlock> IntegersSubsetToBB;
633
634}
635
636#endif /* CRSBUILDER_H_ */
637