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 template <class ImplTy>
31 ImplTy Implementation;
32 typedef IntItemBase<ImplTy> self;
37 IntItemBase(const ImplTy &impl) : Implementation(impl) {}
40 IntItemBase(const APInt& src) : Implementation(src) {}
42 operator const APInt&() const {
43 return (const APInt&)Implementation;
45 bool operator<(const self& RHS) const {
46 return ((const APInt&)*this).ult(RHS);
48 bool operator==(const self& RHS) const {
49 return (const APInt&)*this == (const APInt&)RHS;
51 bool operator!=(const self& RHS) const {
52 return (const APInt&)*this != (const APInt&)RHS;
54 self& operator=(const ImplTy& RHS) {
58 const APInt* operator->() const {
59 return &((const APInt&)Implementation);
61 const APInt& operator*() const {
62 return ((const APInt&)Implementation);
64 // FIXME: Hack. Will removed.
65 ImplTy& getImplementation() {
66 return Implementation;
70 class IntItemConstantIntImpl {
71 const ConstantInt *ConstantIntVal;
73 IntItemConstantIntImpl() : ConstantIntVal(0) {}
74 IntItemConstantIntImpl(const ConstantInt *Val) : ConstantIntVal(Val) {}
75 IntItemConstantIntImpl(LLVMContext &Ctx, const APInt& src) {
76 ConstantIntVal = cast<ConstantInt>(ConstantInt::get(Ctx, src));
78 explicit IntItemConstantIntImpl(const APInt& src) {
80 cast<ConstantInt>(ConstantInt::get(llvm::getGlobalContext(), src));
82 operator const APInt&() const {
83 return ConstantIntVal->getValue();
85 operator const ConstantInt*() {
86 return ConstantIntVal;
90 class IntItem : public IntItemBase<IntItemConstantIntImpl> {
91 typedef IntItemBase<IntItemConstantIntImpl> ParentTy;
92 IntItem(const IntItemConstantIntImpl& Impl) : ParentTy(Impl) {}
98 IntItem(const APInt& src) : ParentTy(src) {}
100 static IntItem fromConstantInt(const ConstantInt *V) {
101 IntItemConstantIntImpl Impl(V);
102 return IntItem(Impl);
104 static IntItem fromType(Type* Ty, const APInt& V) {
105 ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
106 return fromConstantInt(C);
108 ConstantInt *toConstantInt() {
109 return const_cast<ConstantInt*>((const ConstantInt*)Implementation);
113 // TODO: it should be a class in next commit.
119 bool IsSingleNumber : 1;
123 typedef std::pair<IntRange, IntRange> SubRes;
125 IntRange() : IsEmpty(true) {}
126 IntRange(const IntRange &RHS) :
127 Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
128 IntRange(const IntItem &C) :
129 Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
130 IntRange(const IntItem &L, const IntItem &H) : Low(L), High(H),
131 IsEmpty(false), IsSingleNumber(false) {}
133 bool isEmpty() const { return IsEmpty; }
134 bool isSingleNumber() const { return IsSingleNumber; }
136 const IntItem& getLow() {
137 assert(!IsEmpty && "Range is empty.");
140 const IntItem& getHigh() {
141 assert(!IsEmpty && "Range is empty.");
145 bool operator<(const IntRange &RHS) const {
146 assert(!IsEmpty && "Left range is empty.");
147 assert(!RHS.IsEmpty && "Right range is empty.");
148 if (Low->getBitWidth() == RHS.Low->getBitWidth()) {
149 if (Low->eq(RHS.Low)) {
150 if (High->ult(RHS.High))
154 if (Low->ult(RHS.Low))
158 return Low->getBitWidth() < RHS.Low->getBitWidth();
161 bool operator==(const IntRange &RHS) const {
162 assert(!IsEmpty && "Left range is empty.");
163 assert(!RHS.IsEmpty && "Right range is empty.");
164 if (Low->getBitWidth() != RHS.Low->getBitWidth())
166 return Low == RHS.Low && High == RHS.High;
169 bool operator!=(const IntRange &RHS) const {
170 return !operator ==(RHS);
173 static bool LessBySize(const IntRange &LHS, const IntRange &RHS) {
174 assert(LHS.Low->getBitWidth() == RHS.Low->getBitWidth() &&
175 "This type of comparison requires equal bit width for LHS and RHS");
176 APInt LSize = *LHS.High - *LHS.Low;
177 APInt RSize = *RHS.High - *RHS.Low;
178 return LSize.ult(RSize);
181 bool isInRange(const APInt &IntVal) const {
182 assert(!IsEmpty && "Range is empty.");
183 if (IntVal.getBitWidth() != Low->getBitWidth())
185 return IntVal.uge(Low) && IntVal.ule(High);
188 SubRes sub(const IntRange &RHS) const {
191 // RHS is either more global and includes this range or
192 // if it doesn't intersected with this range.
193 if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
195 // If RHS more global (it is enough to check
196 // only one border in this case.
197 if (RHS.isInRange(Low))
198 return std::make_pair(IntRange(Low, High), IntRange());
203 if (Low->ult(RHS.Low)) {
205 APInt NewHigh = RHS.Low;
207 Res.first.High = NewHigh;
209 if (High->ugt(RHS.High)) {
210 APInt NewLow = RHS.High;
212 Res.second.Low = NewLow;
213 Res.second.High = High;
219 //===----------------------------------------------------------------------===//
220 /// ConstantRangesSet - class that implements constant set of ranges.
221 /// It is a wrapper for some real "holder" class (currently ConstantArray).
222 /// It contains functions, that allows to parse "holder" like a set of ranges.
223 /// Note: It is assumed that "holder" is inherited from Constant object.
224 /// ConstantRangesSet may be converted to and from Constant* pointer.
226 class ConstantRangesSet {
233 ConstantRangesSet(Constant *V) : Array(V) {
234 ArrayType *ArrTy = cast<ArrayType>(Array->getType());
235 VectorType *VecTy = cast<VectorType>(ArrTy->getElementType());
236 IntegerType *IntTy = cast<IntegerType>(VecTy->getElementType());
237 IsWide = IntTy->getBitWidth() > 64;
240 operator Constant*() { return Array; }
241 operator const Constant*() const { return Array; }
242 Constant *operator->() { return Array; }
243 const Constant *operator->() const { return Array; }
245 typedef IntRange Range;
247 /// Checks is the given constant satisfies this case. Returns
248 /// true if it equals to one of contained values or belongs to the one of
249 /// contained ranges.
250 bool isSatisfies(const IntItem &CheckingVal) const {
251 for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
252 const Constant *CV = Array->getAggregateElement(i);
253 unsigned VecSize = cast<VectorType>(CV->getType())->getNumElements();
256 if (cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue() ==
262 cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue();
264 cast<const ConstantInt>(CV->getAggregateElement(1))->getValue();
265 if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal))
270 assert(0 && "Only pairs and single numbers are allowed here.");
277 /// Returns set's item with given index.
278 Range getItem(unsigned idx) {
279 Constant *CV = Array->getAggregateElement(idx);
280 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
283 return Range(IntItem::fromConstantInt(
284 cast<ConstantInt>(CV->getAggregateElement(0U))));
286 return Range(IntItem::fromConstantInt(
287 cast<ConstantInt>(CV->getAggregateElement(0U))),
288 IntItem::fromConstantInt(
289 cast<ConstantInt>(CV->getAggregateElement(1U))));
291 assert(0 && "Only pairs and single numbers are allowed here.");
296 const Range getItem(unsigned idx) const {
297 const Constant *CV = Array->getAggregateElement(idx);
299 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
302 return Range(IntItem::fromConstantInt(
303 cast<ConstantInt>(CV->getAggregateElement(0U))),
304 IntItem::fromConstantInt(cast<ConstantInt>(
305 cast<ConstantInt>(CV->getAggregateElement(0U)))));
307 return Range(IntItem::fromConstantInt(
308 cast<ConstantInt>(CV->getAggregateElement(0U))),
309 IntItem::fromConstantInt(
310 cast<ConstantInt>(CV->getAggregateElement(1))));
312 assert(0 && "Only pairs and single numbers are allowed here.");
317 /// Return number of items (ranges) stored in set.
318 unsigned getNumItems() const {
319 return cast<ArrayType>(Array->getType())->getNumElements();
322 bool isWideNumberFormat() const { return IsWide; }
324 bool isSingleNumber(unsigned idx) const {
325 Constant *CV = Array->getAggregateElement(idx);
326 return cast<VectorType>(CV->getType())->getNumElements() == 1;
329 /// Returns set the size, that equals number of all values + sizes of all
331 /// Ranges set is considered as flat numbers collection.
332 /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
333 /// for range [<0>, <1>, <5>] the size will 3
334 unsigned getSize() const {
335 APInt sz(getItem(0).Low->getBitWidth(), 0);
336 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
337 const APInt &Low = getItem(i).Low;
338 const APInt &High = getItem(i).High;
339 const APInt &S = High - Low;
342 return sz.getZExtValue();
345 /// Allows to access single value even if it belongs to some range.
346 /// Ranges set is considered as flat numbers collection.
347 /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
348 /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
349 APInt getSingleValue(unsigned idx) const {
350 APInt sz(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 if (oldSz.uge(i) && sz.ult(i)) {
359 APInt Offset(oldSz.getBitWidth(), i);
365 assert(0 && "Index exceeds high border.");
372 #endif /* CONSTANTRANGESSET_H_ */