1 //===-- llvm/IntegersSubset.h - The subset of integers ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
16 //===----------------------------------------------------------------------===//
18 #ifndef CONSTANTRANGESSET_H_
19 #define CONSTANTRANGESSET_H_
21 #include "llvm/Constants.h"
22 #include "llvm/DerivedTypes.h"
23 #include "llvm/LLVMContext.h"
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
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.
38 // The set of macros that allows to propagate APInt operators to the IntItem.
40 #define INT_ITEM_DEFINE_COMPARISON(op,func) \
41 bool operator op (const APInt& RHS) const { \
42 return getAPIntValue().func(RHS); \
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)); \
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)); \
59 #define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \
60 IntItem& operator op (const APInt& RHS) {\
61 APInt res = getAPIntValue();\
63 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
64 ConstantIntVal = cast<ConstantInt>(NewVal); \
68 #define INT_ITEM_DEFINE_PREINCDEC(op) \
69 IntItem& operator op () { \
70 APInt res = getAPIntValue(); \
72 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
73 ConstantIntVal = cast<ConstantInt>(NewVal); \
77 #define INT_ITEM_DEFINE_POSTINCDEC(op) \
78 IntItem& operator op (int) { \
79 APInt res = getAPIntValue();\
81 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
82 OldConstantIntVal = ConstantIntVal; \
83 ConstantIntVal = cast<ConstantInt>(NewVal); \
84 return IntItem(OldConstantIntVal); \
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); \
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 {
105 operator const APInt&() const {
106 return getAPIntValue();
109 // Propagate APInt operators.
111 // /,/=,>>,>>= are not implemented in APInt.
112 // <<= is implemented for unsigned RHS, but not implemented for APInt RHS.
114 INT_ITEM_DEFINE_COMPARISON(<, ult)
115 INT_ITEM_DEFINE_COMPARISON(>, ugt)
116 INT_ITEM_DEFINE_COMPARISON(<=, ule)
117 INT_ITEM_DEFINE_COMPARISON(>=, uge)
119 INT_ITEM_DEFINE_COMPARISON(==, eq)
120 INT_ITEM_DEFINE_OP_STANDARD_INT(bool,==,uint64_t)
122 INT_ITEM_DEFINE_COMPARISON(!=, ne)
123 INT_ITEM_DEFINE_OP_STANDARD_INT(bool,!=,uint64_t)
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(|)
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(|=)
143 // Special case for <<=
144 IntItem& operator <<= (unsigned RHS) {
145 APInt res = getAPIntValue();
147 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res);
148 ConstantIntVal = cast<ConstantInt>(NewVal);
152 INT_ITEM_DEFINE_UNARY_OP(-)
153 INT_ITEM_DEFINE_UNARY_OP(~)
155 INT_ITEM_DEFINE_PREINCDEC(++)
156 INT_ITEM_DEFINE_PREINCDEC(--)
158 // The set of workarounds, since currently we use ConstantInt implemented
161 static IntItem fromConstantInt(const ConstantInt *V) {
164 static IntItem fromType(Type* Ty, const APInt& V) {
165 ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
166 return fromConstantInt(C);
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);
173 ConstantInt *toConstantInt() const {
174 return ConstantIntVal;
178 template<class IntType>
184 bool IsSingleNumber : 1;
187 typedef IntRange<IntType> self;
188 typedef std::pair<self, self> SubRes;
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) {}
197 IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
198 IsEmpty(false), IsSingleNumber(Low == High) {}
200 bool isEmpty() const { return IsEmpty; }
201 bool isSingleNumber() const { return IsSingleNumber; }
203 const IntType& getLow() const {
204 assert(!IsEmpty && "Range is empty.");
207 const IntType& getHigh() const {
208 assert(!IsEmpty && "Range is empty.");
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) {
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;
231 bool operator!=(const self &RHS) const {
232 return !operator ==(RHS);
235 static bool LessBySize(const self &LHS, const self &RHS) {
236 return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
239 bool isInRange(const IntType &IntVal) const {
240 assert(!IsEmpty && "Range is empty.");
241 return IntVal >= Low && IntVal <= High;
244 SubRes sub(const self &RHS) const {
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)) {
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());
261 IntType NewHigh = RHS.Low;
263 Res.first.High = NewHigh;
265 if (High > RHS.High) {
266 IntType NewLow = RHS.High;
268 Res.second.Low = NewLow;
269 Res.second.High = High;
275 //===----------------------------------------------------------------------===//
276 /// IntegersSubsetGeneric - class that implements the subset of integers. It
277 /// consists from ranges and single numbers.
278 template <class IntTy>
279 class IntegersSubsetGeneric {
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;
291 typedef IntegersSubsetGeneric<IntTy> self;
295 FlatCollectionTy FlatCollection;
296 RangeLinksTy RangeLinks;
299 bool IsSingleNumbersOnly;
303 template<class RangesCollectionTy>
304 explicit IntegersSubsetGeneric(const RangesCollectionTy& Links) {
305 assert(Links.size() && "Empty ranges are not allowed.");
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;
321 RangeLink.second = &FlatCollection.back();
322 RangeLinks.push_back(RangeLink);
324 IsSingleNumber = IsSingleNumbersOnly && RangeLinks.size() == 1;
327 IntegersSubsetGeneric(const self& RHS) {
331 self& operator=(const self& RHS) {
332 FlatCollection.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();
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);
346 IsSingleNumber = RHS.IsSingleNumber;
347 IsSingleNumbersOnly = RHS.IsSingleNumbersOnly;
351 typedef IntRange<IntTy> Range;
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 {
358 return FlatCollection.front() == CheckingVal;
359 if (IsSingleNumbersOnly)
360 return std::find(FlatCollection.begin(),
361 FlatCollection.end(),
362 CheckingVal) != FlatCollection.end();
364 for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
365 if (RangeLinks[i].first == RangeLinks[i].second) {
366 if (*RangeLinks[i].first == CheckingVal)
368 } else if (*RangeLinks[i].first <= CheckingVal &&
369 *RangeLinks[i].second >= CheckingVal)
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);
381 return Range(*Link.first);
384 /// Return number of items (ranges) stored in set.
385 unsigned getNumItems() const {
386 return RangeLinks.size();
389 /// Returns true if whole subset contains single element.
390 bool isSingleNumber() const {
391 return IsSingleNumber;
394 /// Returns true if whole subset contains only single numbers, no ranges.
395 bool isSingleNumbersOnly() const {
396 return IsSingleNumbersOnly;
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;
405 /// Returns set the size, that equals number of all values + sizes of all
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;
418 return sz.getZExtValue();
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;
435 APInt Offset(oldSz.getBitWidth(), idx);
441 assert(0 && "Index exceeds high border.");
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];
454 //===----------------------------------------------------------------------===//
455 /// IntegersSubset - currently is extension of IntegersSubsetGeneric
456 /// that also supports conversion to/from Constant* object.
457 class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
459 typedef IntegersSubsetGeneric<IntItem> ParentTy;
463 static unsigned getNumItemsFromConstant(Constant *C) {
464 return cast<ArrayType>(C->getType())->getNumElements();
467 static Range getItemFromConstant(Constant *C, unsigned idx) {
468 const Constant *CV = C->getAggregateElement(idx);
470 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
473 return Range(IntItem::fromConstantInt(
474 cast<ConstantInt>(CV->getAggregateElement(0U))),
475 IntItem::fromConstantInt(cast<ConstantInt>(
476 cast<ConstantInt>(CV->getAggregateElement(0U)))));
478 return Range(IntItem::fromConstantInt(
479 cast<ConstantInt>(CV->getAggregateElement(0U))),
480 IntItem::fromConstantInt(
481 cast<ConstantInt>(CV->getAggregateElement(1))));
483 assert(0 && "Only pairs and single numbers are allowed here.");
488 std::vector<Range> rangesFromConstant(Constant *C) {
489 unsigned NumItems = getNumItemsFromConstant(C);
490 std::vector<Range> r;
492 for (unsigned i = 0, e = NumItems; i != e; ++i)
493 r.push_back(getItemFromConstant(C, i));
499 explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
502 IntegersSubset(const IntegersSubset& RHS) :
503 ParentTy(*(const ParentTy *)&RHS), // FIXME: tweak for msvc.
504 Holder(RHS.Holder) {}
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) {
513 std::vector<Constant*> r;
514 if (R.isSingleNumber()) {
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());
522 r.push_back(R.getLow().toConstantInt());
524 Constant *CV = ConstantVector::get(r);
528 ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
529 Holder = ConstantArray::get(ArrTy, Elts);
532 operator Constant*() { return Holder; }
533 operator const Constant*() const { return Holder; }
534 Constant *operator->() { return Holder; }
535 const Constant *operator->() const { return Holder; }
540 #endif /* CONSTANTRANGESSET_H_ */