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>
177 typedef IntRange<IntType> self;
181 bool IsSingleNumber : 1;
185 typedef std::pair<self, self> SubRes;
187 IntRange() : IsEmpty(true) {}
188 IntRange(const self &RHS) :
189 Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
190 IntRange(const IntType &C) :
191 Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
192 IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
193 IsEmpty(false), IsSingleNumber(false) {}
195 bool isEmpty() const { return IsEmpty; }
196 bool isSingleNumber() const { return IsSingleNumber; }
198 const IntType& getLow() {
199 assert(!IsEmpty && "Range is empty.");
202 const IntType& getHigh() {
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::iterator RangeLinksConstIt;
288 FlatCollectionTy FlatCollection;
289 RangeLinksTy RangeLinks;
293 template<class RangesCollectionTy>
294 IntegersSubsetGeneric(const RangesCollectionTy& Links) {
295 assert(Links.size() && "Empty ranges are not allowed.");
296 for (typename RangesCollectionTy::const_iterator i = Links.begin(),
297 e = Links.end(); i != e; ++i) {
298 RangeLinkTy RangeLink;
299 FlatCollection.push_back(i->Low);
300 RangeLink.first = &FlatCollection.back();
301 if (i->Low != i->High)
302 FlatCollection.push_back(i->High);
303 RangeLink.second = &FlatCollection.back();
304 RangeLinks.push_back(RangeLink);
308 typedef IntRange<IntTy> Range;
310 /// Checks is the given constant satisfies this case. Returns
311 /// true if it equals to one of contained values or belongs to the one of
312 /// contained ranges.
313 bool isSatisfies(const IntTy &CheckingVal) const {
314 for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
315 if (RangeLinks[i].first == RangeLinks[i].second) {
316 if (*RangeLinks[i].first == CheckingVal)
318 } else if (*RangeLinks[i].first >= CheckingVal &&
319 *RangeLinks[i].second <= CheckingVal)
325 /// Returns set's item with given index.
326 Range getItem(unsigned idx) const {
327 const RangeLinkTy &Link = RangeLinks[idx];
328 if (Link.first != Link.second)
329 return Range(*Link.first, *Link.second);
331 return Range(*Link.first);
334 /// Return number of items (ranges) stored in set.
335 unsigned getNumItems() const {
336 return RangeLinks.size();
339 bool isSingleNumber(unsigned idx) const {
340 return RangeLinks.size() == 1 &&
341 RangeLinks[0].first == RangeLinks[0].second;
344 /// Returns set the size, that equals number of all values + sizes of all
346 /// Ranges set is considered as flat numbers collection.
347 /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
348 /// for range [<0>, <1>, <5>] the size will 3
349 unsigned getSize() const {
350 APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0);
351 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
352 const APInt &Low = getItem(i).Low;
353 const APInt &High = getItem(i).High;
354 const APInt &S = High - Low;
357 return sz.getZExtValue();
360 /// Allows to access single value even if it belongs to some range.
361 /// Ranges set is considered as flat numbers collection.
362 /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
363 /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
364 APInt getSingleValue(unsigned idx) const {
365 APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0);
366 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
367 const APInt &Low = getItem(i).Low;
368 const APInt &High = getItem(i).High;
369 const APInt& S = High - Low;
372 if (oldSz.uge(i) && sz.ult(i)) {
374 APInt Offset(oldSz.getBitWidth(), i);
380 assert(0 && "Index exceeds high border.");
385 //===----------------------------------------------------------------------===//
386 /// IntegersSubset - currently is extension of IntegersSubsetGeneric
387 /// that also supports conversion to/from Constant* object.
388 class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
391 static unsigned getNumItemsFromConstant(Constant *C) {
392 return cast<ArrayType>(C->getType())->getNumElements();
395 static Range getItemFromConstant(Constant *C, unsigned idx) {
396 const Constant *CV = C->getAggregateElement(idx);
398 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
401 return Range(IntItem::fromConstantInt(
402 cast<ConstantInt>(CV->getAggregateElement(0U))),
403 IntItem::fromConstantInt(cast<ConstantInt>(
404 cast<ConstantInt>(CV->getAggregateElement(0U)))));
406 return Range(IntItem::fromConstantInt(
407 cast<ConstantInt>(CV->getAggregateElement(0U))),
408 IntItem::fromConstantInt(
409 cast<ConstantInt>(CV->getAggregateElement(1))));
411 assert(0 && "Only pairs and single numbers are allowed here.");
416 std::vector<Range> rangesFromConstant(Constant *C) {
417 unsigned NumItems = getNumItemsFromConstant(C);
418 std::vector<Range> r;
420 for (unsigned i = 0, e = NumItems; i != e; ++i)
421 r.push_back(getItemFromConstant(C, i));
427 IntegersSubset(Constant *C) : IntegersSubsetGeneric(rangesFromConstant(C)),
431 template<class RangesCollectionTy>
432 IntegersSubset(const RangesCollectionTy& Src) :
433 IntegersSubsetGeneric(Src) {
435 std::vector<Constant*> Elts;
436 Elts.reserve(Src.size());
437 for (typename RangesCollectionTy::const_iterator i = Src.begin(),
438 e = Src.end(); i != e; ++i) {
440 std::vector<Constant*> r;
441 if (R.Low != R.High) {
443 // FIXME: Since currently we have ConstantInt based numbers
444 // use hack-conversion of IntItem to ConstantInt
445 r.push_back(R.Low.toConstantInt());
446 r.push_back(R.High.toConstantInt());
449 r.push_back(R.Low.toConstantInt());
451 Constant *CV = ConstantVector::get(r);
455 ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
456 Holder = ConstantArray::get(ArrTy, Elts);
459 operator Constant*() { return Holder; }
460 operator const Constant*() const { return Holder; }
461 Constant *operator->() { return Holder; }
462 const Constant *operator->() const { return Holder; }
467 #endif /* CONSTANTRANGESSET_H_ */