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