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_
23 #include "llvm/Constants.h"
24 #include "llvm/DerivedTypes.h"
25 #include "llvm/LLVMContext.h"
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
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.
39 // The set of macros that allows to propagate APInt operators to the IntItem.
41 #define INT_ITEM_DEFINE_COMPARISON(op,func) \
42 bool operator op (const APInt& RHS) const { \
43 return ConstantIntVal->getValue().func(RHS); \
46 #define INT_ITEM_DEFINE_UNARY_OP(op) \
47 IntItem operator op () const { \
48 APInt res = op(ConstantIntVal->getValue()); \
49 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
50 return IntItem(cast<ConstantInt>(NewVal)); \
53 #define INT_ITEM_DEFINE_BINARY_OP(op) \
54 IntItem operator op (const APInt& RHS) const { \
55 APInt res = ConstantIntVal->getValue() op RHS; \
56 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
57 return IntItem(cast<ConstantInt>(NewVal)); \
60 #define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \
61 IntItem& operator op (const APInt& RHS) {\
62 APInt res = ConstantIntVal->getValue();\
64 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
65 ConstantIntVal = cast<ConstantInt>(NewVal); \
69 #define INT_ITEM_DEFINE_PREINCDEC(op) \
70 IntItem& operator op () { \
71 APInt res = ConstantIntVal->getValue(); \
73 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
74 ConstantIntVal = cast<ConstantInt>(NewVal); \
78 #define INT_ITEM_DEFINE_POSTINCDEC(op) \
79 IntItem& operator op (int) { \
80 APInt res = ConstantIntVal->getValue();\
82 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
83 OldConstantIntVal = ConstantIntVal; \
84 ConstantIntVal = cast<ConstantInt>(NewVal); \
85 return IntItem(OldConstantIntVal); \
88 #define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \
89 RetTy operator op (IntTy RHS) const { \
90 return (*this) op APInt(ConstantIntVal->getValue().getBitWidth(), RHS); \
94 ConstantInt *ConstantIntVal;
95 IntItem(const ConstantInt *V) : ConstantIntVal(const_cast<ConstantInt*>(V)) {}
100 operator const APInt&() const {
101 return (const APInt&)ConstantIntVal->getValue();
104 // Propagate APInt operators.
106 // /,/=,>>,>>= are not implemented in APInt.
107 // <<= is implemented for unsigned RHS, but not implemented for APInt RHS.
109 INT_ITEM_DEFINE_COMPARISON(<, ult)
110 INT_ITEM_DEFINE_COMPARISON(>, ugt)
111 INT_ITEM_DEFINE_COMPARISON(<=, ule)
112 INT_ITEM_DEFINE_COMPARISON(>=, uge)
114 INT_ITEM_DEFINE_COMPARISON(==, eq)
115 INT_ITEM_DEFINE_OP_STANDARD_INT(bool,==,uint64_t)
117 INT_ITEM_DEFINE_COMPARISON(!=, ne)
118 INT_ITEM_DEFINE_OP_STANDARD_INT(bool,!=,uint64_t)
120 INT_ITEM_DEFINE_BINARY_OP(*)
121 INT_ITEM_DEFINE_BINARY_OP(+)
122 INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,+,uint64_t)
123 INT_ITEM_DEFINE_BINARY_OP(-)
124 INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,-,uint64_t)
125 INT_ITEM_DEFINE_BINARY_OP(<<)
126 INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,<<,unsigned)
127 INT_ITEM_DEFINE_BINARY_OP(&)
128 INT_ITEM_DEFINE_BINARY_OP(^)
129 INT_ITEM_DEFINE_BINARY_OP(|)
131 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(*=)
132 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(+=)
133 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(-=)
134 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(&=)
135 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(^=)
136 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(|=)
138 // Special case for <<=
139 IntItem& operator <<= (unsigned RHS) {
140 APInt res = ConstantIntVal->getValue();
142 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res);
143 ConstantIntVal = cast<ConstantInt>(NewVal);
147 INT_ITEM_DEFINE_UNARY_OP(-)
148 INT_ITEM_DEFINE_UNARY_OP(~)
150 INT_ITEM_DEFINE_PREINCDEC(++)
151 INT_ITEM_DEFINE_PREINCDEC(--)
153 // The set of workarounds, since currently we use ConstantInt implemented
156 static IntItem fromConstantInt(const ConstantInt *V) {
159 static IntItem fromType(Type* Ty, const APInt& V) {
160 ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
161 return fromConstantInt(C);
163 static IntItem withImplLikeThis(const IntItem& LikeThis, const APInt& V) {
164 ConstantInt *C = cast<ConstantInt>(ConstantInt::get(
165 LikeThis.ConstantIntVal->getContext(), V));
166 return fromConstantInt(C);
168 ConstantInt *toConstantInt() const {
169 return ConstantIntVal;
173 template<class IntType>
179 bool IsSingleNumber : 1;
182 typedef IntRange<IntType> self;
183 typedef std::pair<self, self> SubRes;
185 IntRange() : IsEmpty(true) {}
186 IntRange(const self &RHS) :
187 Low(RHS.Low), High(RHS.High),
188 IsEmpty(RHS.IsEmpty), IsSingleNumber(RHS.IsSingleNumber) {}
189 IntRange(const IntType &C) :
190 Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
192 IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
193 IsEmpty(false), IsSingleNumber(Low == High) {}
195 bool isEmpty() const { return IsEmpty; }
196 bool isSingleNumber() const { return IsSingleNumber; }
198 const IntType& getLow() const {
199 assert(!IsEmpty && "Range is empty.");
202 const IntType& getHigh() const {
203 assert(!IsEmpty && "Range is empty.");
207 bool operator<(const self &RHS) const {
208 assert(!IsEmpty && "Left range is empty.");
209 assert(!RHS.IsEmpty && "Right range is empty.");
210 if (Low == RHS.Low) {
220 bool operator==(const self &RHS) const {
221 assert(!IsEmpty && "Left range is empty.");
222 assert(!RHS.IsEmpty && "Right range is empty.");
223 return Low == RHS.Low && High == RHS.High;
226 bool operator!=(const self &RHS) const {
227 return !operator ==(RHS);
230 static bool LessBySize(const self &LHS, const self &RHS) {
231 return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
234 bool isInRange(const IntType &IntVal) const {
235 assert(!IsEmpty && "Range is empty.");
236 return IntVal >= Low && IntVal <= High;
239 SubRes sub(const self &RHS) const {
242 // RHS is either more global and includes this range or
243 // if it doesn't intersected with this range.
244 if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
246 // If RHS more global (it is enough to check
247 // only one border in this case.
248 if (RHS.isInRange(Low))
249 return std::make_pair(self(Low, High), self());
256 IntType NewHigh = RHS.Low;
258 Res.first.High = NewHigh;
260 if (High > RHS.High) {
261 IntType NewLow = RHS.High;
263 Res.second.Low = NewLow;
264 Res.second.High = High;
270 //===----------------------------------------------------------------------===//
271 /// IntegersSubsetGeneric - class that implements the subset of integers. It
272 /// consists from ranges and single numbers.
273 template <class IntTy>
274 class IntegersSubsetGeneric {
276 // Use Chris Lattner idea, that was initially described here:
277 // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120213/136954.html
278 // In short, for more compact memory consumption we can store flat
279 // numbers collection, and define range as pair of indices.
280 // In that case we can safe some memory on 32 bit machines.
281 typedef std::list<IntTy> FlatCollectionTy;
282 typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
283 typedef SmallVector<RangeLinkTy, 64> RangeLinksTy;
284 typedef typename RangeLinksTy::const_iterator RangeLinksConstIt;
286 typedef IntegersSubsetGeneric<IntTy> self;
290 FlatCollectionTy FlatCollection;
291 RangeLinksTy RangeLinks;
295 template<class RangesCollectionTy>
296 explicit IntegersSubsetGeneric(const RangesCollectionTy& Links) {
297 assert(Links.size() && "Empty ranges are not allowed.");
298 for (typename RangesCollectionTy::const_iterator i = Links.begin(),
299 e = Links.end(); i != e; ++i) {
300 RangeLinkTy RangeLink;
301 FlatCollection.push_back(i->getLow());
302 RangeLink.first = &FlatCollection.back();
303 if (i->getLow() != i->getHigh())
304 FlatCollection.push_back(i->getHigh());
305 RangeLink.second = &FlatCollection.back();
306 RangeLinks.push_back(RangeLink);
310 IntegersSubsetGeneric(const self& RHS) {
314 self& operator=(const self& RHS) {
315 FlatCollection.clear();
317 for (RangeLinksConstIt i = RHS.RangeLinks.begin(), e = RHS.RangeLinks.end();
319 RangeLinkTy RangeLink;
320 FlatCollection.push_back(*(i->first));
321 RangeLink.first = &FlatCollection.back();
322 if (i->first != i->second)
323 FlatCollection.push_back(*(i->second));
324 RangeLink.second = &FlatCollection.back();
325 RangeLinks.push_back(RangeLink);
330 typedef IntRange<IntTy> Range;
332 /// Checks is the given constant satisfies this case. Returns
333 /// true if it equals to one of contained values or belongs to the one of
334 /// contained ranges.
335 bool isSatisfies(const IntTy &CheckingVal) const {
336 for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
337 if (RangeLinks[i].first == RangeLinks[i].second) {
338 if (*RangeLinks[i].first == CheckingVal)
340 } else if (*RangeLinks[i].first <= CheckingVal &&
341 *RangeLinks[i].second >= CheckingVal)
347 /// Returns set's item with given index.
348 Range getItem(unsigned idx) const {
349 const RangeLinkTy &Link = RangeLinks[idx];
350 if (Link.first != Link.second)
351 return Range(*Link.first, *Link.second);
353 return Range(*Link.first);
356 /// Return number of items (ranges) stored in set.
357 unsigned getNumItems() const {
358 return RangeLinks.size();
361 /// Returns true if whole subset contains single element.
362 bool isSingleNumber() const {
363 return RangeLinks.size() == 1 &&
364 RangeLinks[0].first == RangeLinks[0].second;
367 /// Does the same like getItem(idx).isSingleNumber(), but
368 /// works faster, since we avoid creation of temporary range object.
369 bool isSingleNumber(unsigned idx) const {
370 return RangeLinks[idx].first == RangeLinks[idx].second;
373 /// Returns set the size, that equals number of all values + sizes of all
375 /// Ranges set is considered as flat numbers collection.
376 /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
377 /// for range [<0>, <1>, <5>] the size will 3
378 unsigned getSize() const {
379 APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
380 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
381 const APInt &Low = getItem(i).getLow();
382 const APInt &High = getItem(i).getHigh();
383 APInt S = High - Low + 1;
386 return sz.getZExtValue();
389 /// Allows to access single value even if it belongs to some range.
390 /// Ranges set is considered as flat numbers collection.
391 /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
392 /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
393 APInt getSingleValue(unsigned idx) const {
394 APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
395 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
396 const APInt &Low = getItem(i).getLow();
397 const APInt &High = getItem(i).getHigh();
398 APInt S = High - Low + 1;
403 APInt Offset(oldSz.getBitWidth(), idx);
409 assert(0 && "Index exceeds high border.");
414 //===----------------------------------------------------------------------===//
415 /// IntegersSubset - currently is extension of IntegersSubsetGeneric
416 /// that also supports conversion to/from Constant* object.
417 class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
419 typedef IntegersSubsetGeneric<IntItem> ParentTy;
423 static unsigned getNumItemsFromConstant(Constant *C) {
424 return cast<ArrayType>(C->getType())->getNumElements();
427 static Range getItemFromConstant(Constant *C, unsigned idx) {
428 const Constant *CV = C->getAggregateElement(idx);
430 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
433 return Range(IntItem::fromConstantInt(
434 cast<ConstantInt>(CV->getAggregateElement(0U))),
435 IntItem::fromConstantInt(cast<ConstantInt>(
436 cast<ConstantInt>(CV->getAggregateElement(0U)))));
438 return Range(IntItem::fromConstantInt(
439 cast<ConstantInt>(CV->getAggregateElement(0U))),
440 IntItem::fromConstantInt(
441 cast<ConstantInt>(CV->getAggregateElement(1))));
443 assert(0 && "Only pairs and single numbers are allowed here.");
448 std::vector<Range> rangesFromConstant(Constant *C) {
449 unsigned NumItems = getNumItemsFromConstant(C);
450 std::vector<Range> r;
452 for (unsigned i = 0, e = NumItems; i != e; ++i)
453 r.push_back(getItemFromConstant(C, i));
459 IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
462 template<class RangesCollectionTy>
463 explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) {
464 std::vector<Constant*> Elts;
465 Elts.reserve(Src.size());
466 for (typename RangesCollectionTy::const_iterator i = Src.begin(),
467 e = Src.end(); i != e; ++i) {
469 std::vector<Constant*> r;
470 if (R.isSingleNumber()) {
472 // FIXME: Since currently we have ConstantInt based numbers
473 // use hack-conversion of IntItem to ConstantInt
474 r.push_back(R.getLow().toConstantInt());
475 r.push_back(R.getHigh().toConstantInt());
478 r.push_back(R.getLow().toConstantInt());
480 Constant *CV = ConstantVector::get(r);
484 ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
485 Holder = ConstantArray::get(ArrTy, Elts);
488 operator Constant*() { return Holder; }
489 operator const Constant*() const { return Holder; }
490 Constant *operator->() { return Holder; }
491 const Constant *operator->() const { return Holder; }
496 #endif /* CONSTANTRANGESSET_H_ */