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_
22 #include "llvm/Constants.h"
23 #include "llvm/DerivedTypes.h"
24 #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 ConstantIntVal->getValue().func(RHS); \
45 #define INT_ITEM_DEFINE_UNARY_OP(op) \
46 IntItem operator op () const { \
47 APInt res = op(ConstantIntVal->getValue()); \
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 = ConstantIntVal->getValue() 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 = ConstantIntVal->getValue();\
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 = ConstantIntVal->getValue(); \
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 = ConstantIntVal->getValue();\
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(ConstantIntVal->getValue().getBitWidth(), RHS); \
93 ConstantInt *ConstantIntVal;
94 IntItem(const ConstantInt *V) : ConstantIntVal(const_cast<ConstantInt*>(V)) {}
99 operator const APInt&() const {
100 return (const APInt&)ConstantIntVal->getValue();
103 // Propogate APInt operators.
105 // /,/=,>>,>>= are not implemented in APInt.
106 // <<= is implemented for unsigned RHS, but not implemented for APInt RHS.
108 INT_ITEM_DEFINE_COMPARISON(<, ult)
109 INT_ITEM_DEFINE_COMPARISON(>, ugt)
110 INT_ITEM_DEFINE_COMPARISON(<=, ule)
111 INT_ITEM_DEFINE_COMPARISON(>=, uge)
112 INT_ITEM_DEFINE_COMPARISON(==, eq)
113 INT_ITEM_DEFINE_COMPARISON(!=, ne)
115 INT_ITEM_DEFINE_BINARY_OP(*)
116 INT_ITEM_DEFINE_BINARY_OP(+)
117 INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,+,uint64_t)
118 INT_ITEM_DEFINE_BINARY_OP(-)
119 INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,-,uint64_t)
120 INT_ITEM_DEFINE_BINARY_OP(<<)
121 INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,<<,unsigned)
122 INT_ITEM_DEFINE_BINARY_OP(&)
123 INT_ITEM_DEFINE_BINARY_OP(^)
124 INT_ITEM_DEFINE_BINARY_OP(|)
126 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(*=)
127 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(+=)
128 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(-=)
129 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(&=)
130 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(^=)
131 INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(|=)
133 // Special case for <<=
134 IntItem& operator <<= (unsigned RHS) {
135 APInt res = ConstantIntVal->getValue();
137 Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res);
138 ConstantIntVal = cast<ConstantInt>(NewVal);
142 INT_ITEM_DEFINE_UNARY_OP(-)
143 INT_ITEM_DEFINE_UNARY_OP(~)
145 INT_ITEM_DEFINE_PREINCDEC(++)
146 INT_ITEM_DEFINE_PREINCDEC(--)
148 // The set of workarounds, since currently we use ConstantInt implemented
151 static IntItem fromConstantInt(const ConstantInt *V) {
154 static IntItem fromType(Type* Ty, const APInt& V) {
155 ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
156 return fromConstantInt(C);
158 static IntItem withImplLikeThis(const IntItem& LikeThis, const APInt& V) {
159 ConstantInt *C = cast<ConstantInt>(ConstantInt::get(
160 LikeThis.ConstantIntVal->getContext(), V));
161 return fromConstantInt(C);
163 ConstantInt *toConstantInt() {
164 return ConstantIntVal;
168 // TODO: it should be a class in next commit.
174 bool IsSingleNumber : 1;
178 typedef std::pair<IntRange, IntRange> SubRes;
180 IntRange() : IsEmpty(true) {}
181 IntRange(const IntRange &RHS) :
182 Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
183 IntRange(const IntItem &C) :
184 Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
185 IntRange(const IntItem &L, const IntItem &H) : Low(L), High(H),
186 IsEmpty(false), IsSingleNumber(false) {}
188 bool isEmpty() const { return IsEmpty; }
189 bool isSingleNumber() const { return IsSingleNumber; }
191 const IntItem& getLow() {
192 assert(!IsEmpty && "Range is empty.");
195 const IntItem& getHigh() {
196 assert(!IsEmpty && "Range is empty.");
200 bool operator<(const IntRange &RHS) const {
201 assert(!IsEmpty && "Left range is empty.");
202 assert(!RHS.IsEmpty && "Right range is empty.");
203 if (Low == RHS.Low) {
213 bool operator==(const IntRange &RHS) const {
214 assert(!IsEmpty && "Left range is empty.");
215 assert(!RHS.IsEmpty && "Right range is empty.");
216 return Low == RHS.Low && High == RHS.High;
219 bool operator!=(const IntRange &RHS) const {
220 return !operator ==(RHS);
223 static bool LessBySize(const IntRange &LHS, const IntRange &RHS) {
224 return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
227 bool isInRange(const IntItem &IntVal) const {
228 assert(!IsEmpty && "Range is empty.");
229 return IntVal >= Low && IntVal <= High;
232 SubRes sub(const IntRange &RHS) const {
235 // RHS is either more global and includes this range or
236 // if it doesn't intersected with this range.
237 if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
239 // If RHS more global (it is enough to check
240 // only one border in this case.
241 if (RHS.isInRange(Low))
242 return std::make_pair(IntRange(Low, High), IntRange());
249 IntItem NewHigh = RHS.Low;
251 Res.first.High = NewHigh;
253 if (High > RHS.High) {
254 IntItem NewLow = RHS.High;
256 Res.second.Low = NewLow;
257 Res.second.High = High;
263 //===----------------------------------------------------------------------===//
264 /// ConstantRangesSet - class that implements constant set of ranges.
265 /// It is a wrapper for some real "holder" class (currently ConstantArray).
266 /// It contains functions, that allows to parse "holder" like a set of ranges.
267 /// Note: It is assumed that "holder" is inherited from Constant object.
268 /// ConstantRangesSet may be converted to and from Constant* pointer.
270 class IntegersSubset {
277 IntegersSubset(Constant *V) : Array(V) {
278 ArrayType *ArrTy = cast<ArrayType>(Array->getType());
279 VectorType *VecTy = cast<VectorType>(ArrTy->getElementType());
280 IntegerType *IntTy = cast<IntegerType>(VecTy->getElementType());
281 IsWide = IntTy->getBitWidth() > 64;
284 operator Constant*() { return Array; }
285 operator const Constant*() const { return Array; }
286 Constant *operator->() { return Array; }
287 const Constant *operator->() const { return Array; }
289 typedef IntRange Range;
291 /// Checks is the given constant satisfies this case. Returns
292 /// true if it equals to one of contained values or belongs to the one of
293 /// contained ranges.
294 bool isSatisfies(const IntItem &CheckingVal) const {
295 for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
296 const Constant *CV = Array->getAggregateElement(i);
297 unsigned VecSize = cast<VectorType>(CV->getType())->getNumElements();
300 if (cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue() ==
306 cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue();
308 cast<const ConstantInt>(CV->getAggregateElement(1))->getValue();
309 if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal))
314 assert(0 && "Only pairs and single numbers are allowed here.");
321 /// Returns set's item with given index.
322 Range getItem(unsigned idx) {
323 Constant *CV = Array->getAggregateElement(idx);
324 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
327 return Range(IntItem::fromConstantInt(
328 cast<ConstantInt>(CV->getAggregateElement(0U))));
330 return Range(IntItem::fromConstantInt(
331 cast<ConstantInt>(CV->getAggregateElement(0U))),
332 IntItem::fromConstantInt(
333 cast<ConstantInt>(CV->getAggregateElement(1U))));
335 assert(0 && "Only pairs and single numbers are allowed here.");
340 const Range getItem(unsigned idx) const {
341 const Constant *CV = Array->getAggregateElement(idx);
343 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
346 return Range(IntItem::fromConstantInt(
347 cast<ConstantInt>(CV->getAggregateElement(0U))),
348 IntItem::fromConstantInt(cast<ConstantInt>(
349 cast<ConstantInt>(CV->getAggregateElement(0U)))));
351 return Range(IntItem::fromConstantInt(
352 cast<ConstantInt>(CV->getAggregateElement(0U))),
353 IntItem::fromConstantInt(
354 cast<ConstantInt>(CV->getAggregateElement(1))));
356 assert(0 && "Only pairs and single numbers are allowed here.");
361 /// Return number of items (ranges) stored in set.
362 unsigned getNumItems() const {
363 return cast<ArrayType>(Array->getType())->getNumElements();
366 bool isWideNumberFormat() const { return IsWide; }
368 bool isSingleNumber(unsigned idx) const {
369 Constant *CV = Array->getAggregateElement(idx);
370 return cast<VectorType>(CV->getType())->getNumElements() == 1;
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).Low).getBitWidth(), 0);
380 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
381 const APInt &Low = getItem(i).Low;
382 const APInt &High = getItem(i).High;
383 const APInt &S = High - Low;
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).Low).getBitWidth(), 0);
395 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
396 const APInt &Low = getItem(i).Low;
397 const APInt &High = getItem(i).High;
398 const APInt& S = High - Low;
401 if (oldSz.uge(i) && sz.ult(i)) {
403 APInt Offset(oldSz.getBitWidth(), i);
409 assert(0 && "Index exceeds high border.");
416 #endif /* CONSTANTRANGESSET_H_ */