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