1 //===-- llvm/ConstantRangesSet.h - The constant set of ranges ---*- 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>]. Mainly, this set is used by SwitchInst and
13 /// represents case value that may contain multiple ranges for a single
17 //===----------------------------------------------------------------------===//
19 #ifndef CONSTANTRANGESSET_H_
20 #define CONSTANTRANGESSET_H_
24 #include "llvm/Constants.h"
25 #include "llvm/DerivedTypes.h"
26 #include "llvm/LLVMContext.h"
30 // The IntItem is a wrapper for APInt.
31 // 1. It determines sign of integer, it allows to use
32 // comparison operators >,<,>=,<=, and as result we got shorter and cleaner
34 // 2. It helps to implement PR1255 (case ranges) as a series of small patches.
35 // 3. Currently we can interpret IntItem both as ConstantInt and as APInt.
36 // It allows to provide SwitchInst methods that works with ConstantInt for
37 // non-updated passes. And it allows to use APInt interface for new methods.
38 // 4. IntItem can be easily replaced with APInt.
40 // The set of macros that allows to propagate APInt operators to the IntItem.
42 #define INT_ITEM_DEFINE_COMPARISON(op,func) \
43 bool operator op (const APInt& RHS) const { \
44 return ConstantIntVal->getValue().func(RHS); \
47 #define INT_ITEM_DEFINE_UNARY_OP(op) \
48 IntItem operator op () const { \
49 APInt res = op(ConstantIntVal->getValue()); \
50 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
51 return IntItem(cast<ConstantInt>(NewVal)); \
54 #define INT_ITEM_DEFINE_BINARY_OP(op) \
55 IntItem operator op (const APInt& RHS) const { \
56 APInt res = ConstantIntVal->getValue() op RHS; \
57 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
58 return IntItem(cast<ConstantInt>(NewVal)); \
61 #define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \
62 IntItem& operator op (const APInt& RHS) {\
63 APInt res = ConstantIntVal->getValue();\
65 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
66 ConstantIntVal = cast<ConstantInt>(NewVal); \
70 #define INT_ITEM_DEFINE_PREINCDEC(op) \
71 IntItem& operator op () { \
72 APInt res = ConstantIntVal->getValue(); \
74 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
75 ConstantIntVal = cast<ConstantInt>(NewVal); \
79 #define INT_ITEM_DEFINE_POSTINCDEC(op) \
80 IntItem& operator op (int) { \
81 APInt res = ConstantIntVal->getValue();\
83 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
84 OldConstantIntVal = ConstantIntVal; \
85 ConstantIntVal = cast<ConstantInt>(NewVal); \
86 return IntItem(OldConstantIntVal); \
89 #define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \
90 RetTy operator op (IntTy RHS) const { \
91 return (*this) op APInt(ConstantIntVal->getValue().getBitWidth(), RHS); \
95 ConstantInt *ConstantIntVal;
96 IntItem(const ConstantInt *V) : ConstantIntVal(const_cast<ConstantInt*>(V)) {}
101 operator const APInt&() const {
102 return (const APInt&)ConstantIntVal->getValue();
105 // Propogate APInt operators.
107 // /,/=,>>,>>= are not implemented in APInt.
108 // <<= is implemented for unsigned RHS, but not implemented for APInt RHS.
110 INT_ITEM_DEFINE_COMPARISON(<, ult)
111 INT_ITEM_DEFINE_COMPARISON(>, ugt)
112 INT_ITEM_DEFINE_COMPARISON(<=, ule)
113 INT_ITEM_DEFINE_COMPARISON(>=, uge)
115 INT_ITEM_DEFINE_COMPARISON(==, eq)
116 INT_ITEM_DEFINE_OP_STANDARD_INT(bool,==,uint64_t)
118 INT_ITEM_DEFINE_COMPARISON(!=, ne)
119 INT_ITEM_DEFINE_OP_STANDARD_INT(bool,!=,uint64_t)
121 INT_ITEM_DEFINE_BINARY_OP(*)
122 INT_ITEM_DEFINE_BINARY_OP(+)
123 INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,+,uint64_t)
124 INT_ITEM_DEFINE_BINARY_OP(-)
125 INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,-,uint64_t)
126 INT_ITEM_DEFINE_BINARY_OP(<<)
127 INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,<<,unsigned)
128 INT_ITEM_DEFINE_BINARY_OP(&)
129 INT_ITEM_DEFINE_BINARY_OP(^)
130 INT_ITEM_DEFINE_BINARY_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(^=)
137 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(|=)
139 // Special case for <<=
140 IntItem& operator <<= (unsigned RHS) {
141 APInt res = ConstantIntVal->getValue();
143 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res);
144 ConstantIntVal = cast<ConstantInt>(NewVal);
148 INT_ITEM_DEFINE_UNARY_OP(-)
149 INT_ITEM_DEFINE_UNARY_OP(~)
151 INT_ITEM_DEFINE_PREINCDEC(++)
152 INT_ITEM_DEFINE_PREINCDEC(--)
154 // The set of workarounds, since currently we use ConstantInt implemented
157 static IntItem fromConstantInt(const ConstantInt *V) {
160 static IntItem fromType(Type* Ty, const APInt& V) {
161 ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
162 return fromConstantInt(C);
164 static IntItem withImplLikeThis(const IntItem& LikeThis, const APInt& V) {
165 ConstantInt *C = cast<ConstantInt>(ConstantInt::get(
166 LikeThis.ConstantIntVal->getContext(), V));
167 return fromConstantInt(C);
169 ConstantInt *toConstantInt() const {
170 return ConstantIntVal;
174 template<class IntType>
180 bool IsSingleNumber : 1;
183 typedef IntRange<IntType> self;
184 typedef std::pair<self, self> SubRes;
186 IntRange() : IsEmpty(true) {}
188 IntRange(const IntType &C) :
189 Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
191 IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
192 IsEmpty(false), IsSingleNumber(Low == High) {}
194 bool isEmpty() const { return IsEmpty; }
195 bool isSingleNumber() const { return IsSingleNumber; }
197 const IntType& getLow() const {
198 assert(!IsEmpty && "Range is empty.");
201 const IntType& getHigh() const {
202 assert(!IsEmpty && "Range is empty.");
206 bool operator<(const self &RHS) const {
207 assert(!IsEmpty && "Left range is empty.");
208 assert(!RHS.IsEmpty && "Right range is empty.");
209 if (Low == RHS.Low) {
219 bool operator==(const self &RHS) const {
220 assert(!IsEmpty && "Left range is empty.");
221 assert(!RHS.IsEmpty && "Right range is empty.");
222 return Low == RHS.Low && High == RHS.High;
225 bool operator!=(const self &RHS) const {
226 return !operator ==(RHS);
229 static bool LessBySize(const self &LHS, const self &RHS) {
230 return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
233 bool isInRange(const IntType &IntVal) const {
234 assert(!IsEmpty && "Range is empty.");
235 return IntVal >= Low && IntVal <= High;
238 SubRes sub(const self &RHS) const {
241 // RHS is either more global and includes this range or
242 // if it doesn't intersected with this range.
243 if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
245 // If RHS more global (it is enough to check
246 // only one border in this case.
247 if (RHS.isInRange(Low))
248 return std::make_pair(self(Low, High), self());
255 IntType NewHigh = RHS.Low;
257 Res.first.High = NewHigh;
259 if (High > RHS.High) {
260 IntType NewLow = RHS.High;
262 Res.second.Low = NewLow;
263 Res.second.High = High;
269 //===----------------------------------------------------------------------===//
270 /// IntegersSubsetGeneric - class that implements the subset of integers. It
271 /// consists from ranges and single numbers.
272 template <class IntTy>
273 class IntegersSubsetGeneric {
275 // Use Chris Lattner idea, that was initially described here:
276 // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120213/136954.html
277 // In short, for more compact memory consumption we can store flat
278 // numbers collection, and define range as pair of indices.
279 // In that case we can safe some memory on 32 bit machines.
280 typedef std::list<IntTy> FlatCollectionTy;
281 typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
282 typedef SmallVector<RangeLinkTy, 64> RangeLinksTy;
283 typedef typename RangeLinksTy::iterator RangeLinksConstIt;
287 FlatCollectionTy FlatCollection;
288 RangeLinksTy RangeLinks;
292 template<class RangesCollectionTy>
293 IntegersSubsetGeneric(const RangesCollectionTy& Links) {
294 assert(Links.size() && "Empty ranges are not allowed.");
295 for (typename RangesCollectionTy::const_iterator i = Links.begin(),
296 e = Links.end(); i != e; ++i) {
297 RangeLinkTy RangeLink;
298 FlatCollection.push_back(i->getLow());
299 RangeLink.first = &FlatCollection.back();
300 if (i->getLow() != i->getHigh())
301 FlatCollection.push_back(i->getHigh());
302 RangeLink.second = &FlatCollection.back();
303 RangeLinks.push_back(RangeLink);
307 typedef IntRange<IntTy> Range;
309 /// Checks is the given constant satisfies this case. Returns
310 /// true if it equals to one of contained values or belongs to the one of
311 /// contained ranges.
312 bool isSatisfies(const IntTy &CheckingVal) const {
313 for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
314 if (RangeLinks[i].first == RangeLinks[i].second) {
315 if (*RangeLinks[i].first == CheckingVal)
317 } else if (*RangeLinks[i].first >= CheckingVal &&
318 *RangeLinks[i].second <= CheckingVal)
324 /// Returns set's item with given index.
325 Range getItem(unsigned idx) const {
326 const RangeLinkTy &Link = RangeLinks[idx];
327 if (Link.first != Link.second)
328 return Range(*Link.first, *Link.second);
330 return Range(*Link.first);
333 /// Return number of items (ranges) stored in set.
334 unsigned getNumItems() const {
335 return RangeLinks.size();
338 /// Returns true if whole subset contains single element.
339 bool isSingleNumber() const {
340 return RangeLinks.size() == 1 &&
341 RangeLinks[0].first == RangeLinks[0].second;
344 /// Does the same like getItem(idx).isSingleNumber(), but
345 /// works faster, since we avoid creation of temporary range object.
346 bool isSingleNumber(unsigned idx) const {
347 return RangeLinks[idx].first == RangeLinks[idx].second;
350 /// Returns set the size, that equals number of all values + sizes of all
352 /// Ranges set is considered as flat numbers collection.
353 /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
354 /// for range [<0>, <1>, <5>] the size will 3
355 unsigned getSize() const {
356 APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
357 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
358 const APInt &Low = getItem(i).getLow();
359 const APInt &High = getItem(i).getHigh();
360 const APInt &S = High - Low;
363 return sz.getZExtValue();
366 /// Allows to access single value even if it belongs to some range.
367 /// Ranges set is considered as flat numbers collection.
368 /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
369 /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
370 APInt getSingleValue(unsigned idx) const {
371 APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
372 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
373 const APInt &Low = getItem(i).getLow();
374 const APInt &High = getItem(i).getHigh();
375 const APInt& S = High - Low;
378 if (oldSz.uge(i) && sz.ult(i)) {
380 APInt Offset(oldSz.getBitWidth(), i);
386 assert(0 && "Index exceeds high border.");
391 //===----------------------------------------------------------------------===//
392 /// IntegersSubset - currently is extension of IntegersSubsetGeneric
393 /// that also supports conversion to/from Constant* object.
394 class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
396 typedef IntegersSubsetGeneric<IntItem> ParentTy;
400 static unsigned getNumItemsFromConstant(Constant *C) {
401 return cast<ArrayType>(C->getType())->getNumElements();
404 static Range getItemFromConstant(Constant *C, unsigned idx) {
405 const Constant *CV = C->getAggregateElement(idx);
407 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
410 return Range(IntItem::fromConstantInt(
411 cast<ConstantInt>(CV->getAggregateElement(0U))),
412 IntItem::fromConstantInt(cast<ConstantInt>(
413 cast<ConstantInt>(CV->getAggregateElement(0U)))));
415 return Range(IntItem::fromConstantInt(
416 cast<ConstantInt>(CV->getAggregateElement(0U))),
417 IntItem::fromConstantInt(
418 cast<ConstantInt>(CV->getAggregateElement(1))));
420 assert(0 && "Only pairs and single numbers are allowed here.");
425 std::vector<Range> rangesFromConstant(Constant *C) {
426 unsigned NumItems = getNumItemsFromConstant(C);
427 std::vector<Range> r;
429 for (unsigned i = 0, e = NumItems; i != e; ++i)
430 r.push_back(getItemFromConstant(C, i));
436 IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
440 template<class RangesCollectionTy>
441 IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) {
442 std::vector<Constant*> Elts;
443 Elts.reserve(Src.size());
444 for (typename RangesCollectionTy::const_iterator i = Src.begin(),
445 e = Src.end(); i != e; ++i) {
447 std::vector<Constant*> r;
448 if (R.isSingleNumber()) {
450 // FIXME: Since currently we have ConstantInt based numbers
451 // use hack-conversion of IntItem to ConstantInt
452 r.push_back(R.getLow().toConstantInt());
453 r.push_back(R.getHigh().toConstantInt());
456 r.push_back(R.getLow().toConstantInt());
458 Constant *CV = ConstantVector::get(r);
462 ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
463 Holder = ConstantArray::get(ArrTy, Elts);
466 operator Constant*() { return Holder; }
467 operator const Constant*() const { return Holder; }
468 Constant *operator->() { return Holder; }
469 const Constant *operator->() const { return Holder; }
474 #endif /* CONSTANTRANGESSET_H_ */