1//===-- llvm/IntegersSubset.h - The subset of integers ----------*- 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/// This file contains class that implements constant set of ranges:
12/// [<Low0,High0>,...,<LowN,HighN>]. Initially, this class was created for
13/// SwitchInst and was used for case value representation that may contain
14/// multiple ranges for a single successor.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef CONSTANTRANGESSET_H_
19#define CONSTANTRANGESSET_H_
20
21#include <list>
22
23#include "llvm/Constants.h"
24#include "llvm/DerivedTypes.h"
25#include "llvm/LLVMContext.h"
26
27namespace llvm {
28
29  // The IntItem is a wrapper for APInt.
30  // 1. It determines sign of integer, it allows to use
31  //    comparison operators >,<,>=,<=, and as result we got shorter and cleaner
32  //    constructions.
33  // 2. It helps to implement PR1255 (case ranges) as a series of small patches.
34  // 3. Currently we can interpret IntItem both as ConstantInt and as APInt.
35  //    It allows to provide SwitchInst methods that works with ConstantInt for
36  //    non-updated passes. And it allows to use APInt interface for new methods.
37  // 4. IntItem can be easily replaced with APInt.
38
39  // The set of macros that allows to propagate APInt operators to the IntItem.
40
41#define INT_ITEM_DEFINE_COMPARISON(op,func) \
42  bool operator op (const APInt& RHS) const { \
43    return getAPIntValue().func(RHS); \
44  }
45
46#define INT_ITEM_DEFINE_UNARY_OP(op) \
47  IntItem operator op () const { \
48    APInt res = op(getAPIntValue()); \
49    Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
50    return IntItem(cast<ConstantInt>(NewVal)); \
51  }
52
53#define INT_ITEM_DEFINE_BINARY_OP(op) \
54  IntItem operator op (const APInt& RHS) const { \
55    APInt res = getAPIntValue() op RHS; \
56    Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
57    return IntItem(cast<ConstantInt>(NewVal)); \
58  }
59
60#define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \
61  IntItem& operator op (const APInt& RHS) {\
62    APInt res = getAPIntValue();\
63    res op RHS; \
64    Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
65    ConstantIntVal = cast<ConstantInt>(NewVal); \
66    return *this; \
67  }
68
69#define INT_ITEM_DEFINE_PREINCDEC(op) \
70    IntItem& operator op () { \
71      APInt res = getAPIntValue(); \
72      op(res); \
73      Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
74      ConstantIntVal = cast<ConstantInt>(NewVal); \
75      return *this; \
76    }
77
78#define INT_ITEM_DEFINE_POSTINCDEC(op) \
79    IntItem& operator op (int) { \
80      APInt res = getAPIntValue();\
81      op(res); \
82      Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
83      OldConstantIntVal = ConstantIntVal; \
84      ConstantIntVal = cast<ConstantInt>(NewVal); \
85      return IntItem(OldConstantIntVal); \
86    }
87
88#define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \
89  RetTy operator op (IntTy RHS) const { \
90    return (*this) op APInt(getAPIntValue().getBitWidth(), RHS); \
91  }
92
93class IntItem {
94  ConstantInt *ConstantIntVal;
95  const APInt* APIntVal;
96  IntItem(const ConstantInt *V) :
97    ConstantIntVal(const_cast<ConstantInt*>(V)),
98    APIntVal(&ConstantIntVal->getValue()){}
99  const APInt& getAPIntValue() const {
100    return *APIntVal;
101  }
102public:
103
104  IntItem() {}
105
106  operator const APInt&() const {
107    return getAPIntValue();
108  }
109
110  // Propagate APInt operators.
111  // Note, that
112  // /,/=,>>,>>= are not implemented in APInt.
113  // <<= is implemented for unsigned RHS, but not implemented for APInt RHS.
114
115  INT_ITEM_DEFINE_COMPARISON(<, ult)
116  INT_ITEM_DEFINE_COMPARISON(>, ugt)
117  INT_ITEM_DEFINE_COMPARISON(<=, ule)
118  INT_ITEM_DEFINE_COMPARISON(>=, uge)
119
120  INT_ITEM_DEFINE_COMPARISON(==, eq)
121  INT_ITEM_DEFINE_OP_STANDARD_INT(bool,==,uint64_t)
122
123  INT_ITEM_DEFINE_COMPARISON(!=, ne)
124  INT_ITEM_DEFINE_OP_STANDARD_INT(bool,!=,uint64_t)
125
126  INT_ITEM_DEFINE_BINARY_OP(*)
127  INT_ITEM_DEFINE_BINARY_OP(+)
128  INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,+,uint64_t)
129  INT_ITEM_DEFINE_BINARY_OP(-)
130  INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,-,uint64_t)
131  INT_ITEM_DEFINE_BINARY_OP(<<)
132  INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,<<,unsigned)
133  INT_ITEM_DEFINE_BINARY_OP(&)
134  INT_ITEM_DEFINE_BINARY_OP(^)
135  INT_ITEM_DEFINE_BINARY_OP(|)
136
137  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(*=)
138  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(+=)
139  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(-=)
140  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(&=)
141  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(^=)
142  INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(|=)
143
144  // Special case for <<=
145  IntItem& operator <<= (unsigned RHS) {
146    APInt res = getAPIntValue();
147    res <<= RHS;
148    Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res);
149    ConstantIntVal = cast<ConstantInt>(NewVal);
150    return *this;
151  }
152
153  INT_ITEM_DEFINE_UNARY_OP(-)
154  INT_ITEM_DEFINE_UNARY_OP(~)
155
156  INT_ITEM_DEFINE_PREINCDEC(++)
157  INT_ITEM_DEFINE_PREINCDEC(--)
158
159  // The set of workarounds, since currently we use ConstantInt implemented
160  // integer.
161
162  static IntItem fromConstantInt(const ConstantInt *V) {
163    return IntItem(V);
164  }
165  static IntItem fromType(Type* Ty, const APInt& V) {
166    ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
167    return fromConstantInt(C);
168  }
169  static IntItem withImplLikeThis(const IntItem& LikeThis, const APInt& V) {
170    ConstantInt *C = cast<ConstantInt>(ConstantInt::get(
171        LikeThis.ConstantIntVal->getContext(), V));
172    return fromConstantInt(C);
173  }
174  ConstantInt *toConstantInt() const {
175    return ConstantIntVal;
176  }
177};
178
179template<class IntType>
180class IntRange {
181protected:
182    IntType Low;
183    IntType High;
184    bool IsEmpty : 1;
185    bool IsSingleNumber : 1;
186
187public:
188    typedef IntRange<IntType> self;
189    typedef std::pair<self, self> SubRes;
190
191    IntRange() : IsEmpty(true) {}
192    IntRange(const self &RHS) :
193      Low(RHS.Low), High(RHS.High),
194      IsEmpty(RHS.IsEmpty), IsSingleNumber(RHS.IsSingleNumber) {}
195    IntRange(const IntType &C) :
196      Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
197
198    IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
199      IsEmpty(false), IsSingleNumber(Low == High) {}
200
201    bool isEmpty() const { return IsEmpty; }
202    bool isSingleNumber() const { return IsSingleNumber; }
203
204    const IntType& getLow() const {
205      assert(!IsEmpty && "Range is empty.");
206      return Low;
207    }
208    const IntType& getHigh() const {
209      assert(!IsEmpty && "Range is empty.");
210      return High;
211    }
212
213    bool operator<(const self &RHS) const {
214      assert(!IsEmpty && "Left range is empty.");
215      assert(!RHS.IsEmpty && "Right range is empty.");
216      if (Low == RHS.Low) {
217        if (High > RHS.High)
218          return true;
219        return false;
220      }
221      if (Low < RHS.Low)
222        return true;
223      return false;
224    }
225
226    bool operator==(const self &RHS) const {
227      assert(!IsEmpty && "Left range is empty.");
228      assert(!RHS.IsEmpty && "Right range is empty.");
229      return Low == RHS.Low && High == RHS.High;
230    }
231
232    bool operator!=(const self &RHS) const {
233      return !operator ==(RHS);
234    }
235
236    static bool LessBySize(const self &LHS, const self &RHS) {
237      return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
238    }
239
240    bool isInRange(const IntType &IntVal) const {
241      assert(!IsEmpty && "Range is empty.");
242      return IntVal >= Low && IntVal <= High;
243    }
244
245    SubRes sub(const self &RHS) const {
246      SubRes Res;
247
248      // RHS is either more global and includes this range or
249      // if it doesn't intersected with this range.
250      if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
251
252        // If RHS more global (it is enough to check
253        // only one border in this case.
254        if (RHS.isInRange(Low))
255          return std::make_pair(self(Low, High), self());
256
257        return Res;
258      }
259
260      if (Low < RHS.Low) {
261        Res.first.Low = Low;
262        IntType NewHigh = RHS.Low;
263        --NewHigh;
264        Res.first.High = NewHigh;
265      }
266      if (High > RHS.High) {
267        IntType NewLow = RHS.High;
268        ++NewLow;
269        Res.second.Low = NewLow;
270        Res.second.High = High;
271      }
272      return Res;
273    }
274  };
275
276//===----------------------------------------------------------------------===//
277/// IntegersSubsetGeneric - class that implements the subset of integers. It
278/// consists from ranges and single numbers.
279template <class IntTy>
280class IntegersSubsetGeneric {
281public:
282  // Use Chris Lattner idea, that was initially described here:
283  // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120213/136954.html
284  // In short, for more compact memory consumption we can store flat
285  // numbers collection, and define range as pair of indices.
286  // In that case we can safe some memory on 32 bit machines.
287  typedef std::vector<IntTy> FlatCollectionTy;
288  typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
289  typedef std::vector<RangeLinkTy> RangeLinksTy;
290  typedef typename RangeLinksTy::const_iterator RangeLinksConstIt;
291
292  typedef IntegersSubsetGeneric<IntTy> self;
293
294protected:
295
296  FlatCollectionTy FlatCollection;
297  RangeLinksTy RangeLinks;
298
299  bool IsSingleNumber;
300  bool IsSingleNumbersOnly;
301
302public:
303
304  template<class RangesCollectionTy>
305  explicit IntegersSubsetGeneric(const RangesCollectionTy& Links) {
306    assert(Links.size() && "Empty ranges are not allowed.");
307
308    // In case of big set of single numbers consumes additional RAM space,
309    // but allows to avoid additional reallocation.
310    FlatCollection.reserve(Links.size() * 2);
311    RangeLinks.reserve(Links.size());
312    IsSingleNumbersOnly = true;
313    for (typename RangesCollectionTy::const_iterator i = Links.begin(),
314         e = Links.end(); i != e; ++i) {
315      RangeLinkTy RangeLink;
316      FlatCollection.push_back(i->getLow());
317      RangeLink.first = &FlatCollection.back();
318      if (i->getLow() != i->getHigh()) {
319        FlatCollection.push_back(i->getHigh());
320        IsSingleNumbersOnly = false;
321      }
322      RangeLink.second = &FlatCollection.back();
323      RangeLinks.push_back(RangeLink);
324    }
325    IsSingleNumber = IsSingleNumbersOnly && RangeLinks.size() == 1;
326  }
327
328  IntegersSubsetGeneric(const self& RHS) {
329    *this = RHS;
330  }
331
332  self& operator=(const self& RHS) {
333    FlatCollection.clear();
334    RangeLinks.clear();
335    FlatCollection.reserve(RHS.RangeLinks.size() * 2);
336    RangeLinks.reserve(RHS.RangeLinks.size());
337    for (RangeLinksConstIt i = RHS.RangeLinks.begin(), e = RHS.RangeLinks.end();
338         i != e; ++i) {
339      RangeLinkTy RangeLink;
340      FlatCollection.push_back(*(i->first));
341      RangeLink.first = &FlatCollection.back();
342      if (i->first != i->second)
343        FlatCollection.push_back(*(i->second));
344      RangeLink.second = &FlatCollection.back();
345      RangeLinks.push_back(RangeLink);
346    }
347    IsSingleNumber = RHS.IsSingleNumber;
348    IsSingleNumbersOnly = RHS.IsSingleNumbersOnly;
349    return *this;
350  }
351
352  typedef IntRange<IntTy> Range;
353
354  /// Checks is the given constant satisfies this case. Returns
355  /// true if it equals to one of contained values or belongs to the one of
356  /// contained ranges.
357  bool isSatisfies(const IntTy &CheckingVal) const {
358    if (IsSingleNumber)
359      return FlatCollection.front() == CheckingVal;
360    if (IsSingleNumbersOnly)
361      return std::find(FlatCollection.begin(),
362                       FlatCollection.end(),
363                       CheckingVal) != FlatCollection.end();
364
365    for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
366      if (RangeLinks[i].first == RangeLinks[i].second) {
367        if (*RangeLinks[i].first == CheckingVal)
368          return true;
369      } else if (*RangeLinks[i].first <= CheckingVal &&
370                 *RangeLinks[i].second >= CheckingVal)
371        return true;
372    }
373    return false;
374  }
375
376  /// Returns set's item with given index.
377  Range getItem(unsigned idx) const {
378    const RangeLinkTy &Link = RangeLinks[idx];
379    if (Link.first != Link.second)
380      return Range(*Link.first, *Link.second);
381    else
382      return Range(*Link.first);
383  }
384
385  /// Return number of items (ranges) stored in set.
386  unsigned getNumItems() const {
387    return RangeLinks.size();
388  }
389
390  /// Returns true if whole subset contains single element.
391  bool isSingleNumber() const {
392    return IsSingleNumber;
393  }
394
395  /// Returns true if whole subset contains only single numbers, no ranges.
396  bool isSingleNumbersOnly() const {
397    return IsSingleNumbersOnly;
398  }
399
400  /// Does the same like getItem(idx).isSingleNumber(), but
401  /// works faster, since we avoid creation of temporary range object.
402  bool isSingleNumber(unsigned idx) const {
403    return RangeLinks[idx].first == RangeLinks[idx].second;
404  }
405
406  /// Returns set the size, that equals number of all values + sizes of all
407  /// ranges.
408  /// Ranges set is considered as flat numbers collection.
409  /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
410  ///       for range [<0>, <1>, <5>] the size will 3
411  unsigned getSize() const {
412    APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
413    for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
414      const APInt &Low = getItem(i).getLow();
415      const APInt &High = getItem(i).getHigh();
416      APInt S = High - Low + 1;
417      sz += S;
418    }
419    return sz.getZExtValue();
420  }
421
422  /// Allows to access single value even if it belongs to some range.
423  /// Ranges set is considered as flat numbers collection.
424  /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
425  /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
426  APInt getSingleValue(unsigned idx) const {
427    APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
428    for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
429      const APInt &Low = getItem(i).getLow();
430      const APInt &High = getItem(i).getHigh();
431      APInt S = High - Low + 1;
432      APInt oldSz = sz;
433      sz += S;
434      if (sz.ugt(idx)) {
435        APInt Res = Low;
436        APInt Offset(oldSz.getBitWidth(), idx);
437        Offset -= oldSz;
438        Res += Offset;
439        return Res;
440      }
441    }
442    assert(0 && "Index exceeds high border.");
443    return sz;
444  }
445
446  /// Does the same as getSingleValue, but works only if subset contains
447  /// single numbers only.
448  const IntTy& getSingleNumber(unsigned idx) const {
449    assert(IsSingleNumbersOnly && "This method works properly if subset "
450                                  "contains single numbers only.");
451    return FlatCollection[idx];
452  }
453};
454
455//===----------------------------------------------------------------------===//
456/// IntegersSubset - currently is extension of IntegersSubsetGeneric
457/// that also supports conversion to/from Constant* object.
458class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
459
460  typedef IntegersSubsetGeneric<IntItem> ParentTy;
461
462  Constant *Holder;
463
464  static unsigned getNumItemsFromConstant(Constant *C) {
465    return cast<ArrayType>(C->getType())->getNumElements();
466  }
467
468  static Range getItemFromConstant(Constant *C, unsigned idx) {
469    const Constant *CV = C->getAggregateElement(idx);
470
471    unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
472    switch (NumEls) {
473    case 1:
474      return Range(IntItem::fromConstantInt(
475                     cast<ConstantInt>(CV->getAggregateElement(0U))),
476                   IntItem::fromConstantInt(cast<ConstantInt>(
477                     cast<ConstantInt>(CV->getAggregateElement(0U)))));
478    case 2:
479      return Range(IntItem::fromConstantInt(
480                     cast<ConstantInt>(CV->getAggregateElement(0U))),
481                   IntItem::fromConstantInt(
482                   cast<ConstantInt>(CV->getAggregateElement(1))));
483    default:
484      assert(0 && "Only pairs and single numbers are allowed here.");
485      return Range();
486    }
487  }
488
489  std::vector<Range> rangesFromConstant(Constant *C) {
490    unsigned NumItems = getNumItemsFromConstant(C);
491    std::vector<Range> r;
492    r.reserve(NumItems);
493    for (unsigned i = 0, e = NumItems; i != e; ++i)
494      r.push_back(getItemFromConstant(C, i));
495    return r;
496  }
497
498public:
499
500  explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
501                          Holder(C) {}
502
503  IntegersSubset(const IntegersSubset& RHS) :
504    ParentTy(*(const ParentTy *)&RHS), // FIXME: tweak for msvc.
505    Holder(RHS.Holder) {}
506
507  template<class RangesCollectionTy>
508  explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) {
509    std::vector<Constant*> Elts;
510    Elts.reserve(Src.size());
511    for (typename RangesCollectionTy::const_iterator i = Src.begin(),
512         e = Src.end(); i != e; ++i) {
513      const Range &R = *i;
514      std::vector<Constant*> r;
515      if (R.isSingleNumber()) {
516        r.reserve(2);
517        // FIXME: Since currently we have ConstantInt based numbers
518        // use hack-conversion of IntItem to ConstantInt
519        r.push_back(R.getLow().toConstantInt());
520        r.push_back(R.getHigh().toConstantInt());
521      } else {
522        r.reserve(1);
523        r.push_back(R.getLow().toConstantInt());
524      }
525      Constant *CV = ConstantVector::get(r);
526      Elts.push_back(CV);
527    }
528    ArrayType *ArrTy =
529        ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
530    Holder = ConstantArray::get(ArrTy, Elts);
531  }
532
533  operator Constant*() { return Holder; }
534  operator const Constant*() const { return Holder; }
535  Constant *operator->() { return Holder; }
536  const Constant *operator->() const { return Holder; }
537};
538
539}
540
541#endif /* CONSTANTRANGESSET_H_ */
542