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 // TODO: it should be a class in next commit.
180 bool IsSingleNumber : 1;
184 typedef std::pair<IntRange, IntRange> SubRes;
186 IntRange() : IsEmpty(true) {}
187 IntRange(const IntRange &RHS) :
188 Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
189 IntRange(const IntItem &C) :
190 Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
191 IntRange(const IntItem &L, const IntItem &H) : Low(L), High(H),
192 IsEmpty(false), IsSingleNumber(false) {}
194 bool isEmpty() const { return IsEmpty; }
195 bool isSingleNumber() const { return IsSingleNumber; }
197 const IntItem& getLow() {
198 assert(!IsEmpty && "Range is empty.");
201 const IntItem& getHigh() {
202 assert(!IsEmpty && "Range is empty.");
206 bool operator<(const IntRange &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 IntRange &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 IntRange &RHS) const {
226 return !operator ==(RHS);
229 static bool LessBySize(const IntRange &LHS, const IntRange &RHS) {
230 return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
233 bool isInRange(const IntItem &IntVal) const {
234 assert(!IsEmpty && "Range is empty.");
235 return IntVal >= Low && IntVal <= High;
238 SubRes sub(const IntRange &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(IntRange(Low, High), IntRange());
255 IntItem NewHigh = RHS.Low;
257 Res.first.High = NewHigh;
259 if (High > RHS.High) {
260 IntItem 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 class IntegersSubsetGeneric {
274 // Use Chris Lattner idea, that was initially described here:
275 // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120213/136954.html
276 // In short, for more compact memory consumption we can store flat
277 // numbers collection, and define range as pair of indices.
278 // In that case we can safe some memory on 32 bit machines.
279 typedef std::list<IntItem> FlatCollectionTy;
280 typedef std::pair<IntItem*, IntItem*> RangeLinkTy;
281 typedef SmallVector<RangeLinkTy, 64> RangeLinksTy;
282 typedef RangeLinksTy::iterator RangeLinksConstIt;
286 FlatCollectionTy FlatCollection;
287 RangeLinksTy RangeLinks;
291 template<class RangesCollectionTy>
292 IntegersSubsetGeneric(const RangesCollectionTy& Links) {
293 assert(Links.size() && "Empty ranges are not allowed.");
294 for (typename RangesCollectionTy::const_iterator i = Links.begin(),
295 e = Links.end(); i != e; ++i) {
296 RangeLinkTy RangeLink;
297 FlatCollection.push_back(i->Low);
298 RangeLink.first = &FlatCollection.back();
299 if (i->Low != i->High)
300 FlatCollection.push_back(i->High);
301 RangeLink.second = &FlatCollection.back();
302 RangeLinks.push_back(RangeLink);
306 typedef IntRange Range;
308 /// Checks is the given constant satisfies this case. Returns
309 /// true if it equals to one of contained values or belongs to the one of
310 /// contained ranges.
311 bool isSatisfies(const IntItem &CheckingVal) const {
312 for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
313 if (RangeLinks[i].first == RangeLinks[i].second) {
314 if (*RangeLinks[i].first == CheckingVal)
316 } else if (*RangeLinks[i].first >= CheckingVal &&
317 *RangeLinks[i].second <= CheckingVal)
323 /// Returns set's item with given index.
324 Range getItem(unsigned idx) const {
325 const RangeLinkTy &Link = RangeLinks[idx];
326 if (Link.first != Link.second)
327 return Range(*Link.first, *Link.second);
329 return Range(*Link.first);
332 /// Return number of items (ranges) stored in set.
333 unsigned getNumItems() const {
334 return RangeLinks.size();
337 bool isSingleNumber(unsigned idx) const {
338 return RangeLinks.size() == 1 &&
339 RangeLinks[0].first == RangeLinks[0].second;
342 /// Returns set the size, that equals number of all values + sizes of all
344 /// Ranges set is considered as flat numbers collection.
345 /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
346 /// for range [<0>, <1>, <5>] the size will 3
347 unsigned getSize() const {
348 APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0);
349 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
350 const APInt &Low = getItem(i).Low;
351 const APInt &High = getItem(i).High;
352 const APInt &S = High - Low;
355 return sz.getZExtValue();
358 /// Allows to access single value even if it belongs to some range.
359 /// Ranges set is considered as flat numbers collection.
360 /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
361 /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
362 APInt getSingleValue(unsigned idx) const {
363 APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0);
364 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
365 const APInt &Low = getItem(i).Low;
366 const APInt &High = getItem(i).High;
367 const APInt& S = High - Low;
370 if (oldSz.uge(i) && sz.ult(i)) {
372 APInt Offset(oldSz.getBitWidth(), i);
378 assert(0 && "Index exceeds high border.");
383 //===----------------------------------------------------------------------===//
384 /// IntegersSubset - currenly is extension of IntegersSubsetGeneric
385 /// that also supports conversion to/from Constant* object.
386 class IntegersSubset : public IntegersSubsetGeneric {
389 static unsigned getNumItemsFromConstant(Constant *C) {
390 return cast<ArrayType>(C->getType())->getNumElements();
393 static Range getItemFromConstant(Constant *C, unsigned idx) {
394 const Constant *CV = C->getAggregateElement(idx);
396 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
399 return Range(IntItem::fromConstantInt(
400 cast<ConstantInt>(CV->getAggregateElement(0U))),
401 IntItem::fromConstantInt(cast<ConstantInt>(
402 cast<ConstantInt>(CV->getAggregateElement(0U)))));
404 return Range(IntItem::fromConstantInt(
405 cast<ConstantInt>(CV->getAggregateElement(0U))),
406 IntItem::fromConstantInt(
407 cast<ConstantInt>(CV->getAggregateElement(1))));
409 assert(0 && "Only pairs and single numbers are allowed here.");
414 std::vector<Range> rangesFromConstant(Constant *C) {
415 unsigned NumItems = getNumItemsFromConstant(C);
416 std::vector<Range> r;
418 for (unsigned i = 0, e = NumItems; i != e; ++i)
419 r.push_back(getItemFromConstant(C, i));
425 IntegersSubset(Constant *C) : IntegersSubsetGeneric(rangesFromConstant(C)),
429 template<class RangesCollectionTy>
430 IntegersSubset(const RangesCollectionTy& Src) :
431 IntegersSubsetGeneric(Src) {
433 std::vector<Constant*> Elts;
434 Elts.reserve(Src.size());
435 for (typename RangesCollectionTy::const_iterator i = Src.begin(),
436 e = Src.end(); i != e; ++i) {
438 std::vector<Constant*> r;
439 if (R.Low != R.High) {
441 // FIXME: Since currently we have ConstantInt based numbers
442 // use hack-conversion of IntItem to ConstantInt
443 r.push_back(R.Low.toConstantInt());
444 r.push_back(R.High.toConstantInt());
447 r.push_back(R.Low.toConstantInt());
449 Constant *CV = ConstantVector::get(r);
453 ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
454 Holder = ConstantArray::get(ArrTy, Elts);
457 operator Constant*() { return Holder; }
458 operator const Constant*() const { return Holder; }
459 Constant *operator->() { return Holder; }
460 const Constant *operator->() const { return Holder; }
465 #endif /* CONSTANTRANGESSET_H_ */