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"
27 class ConstantRangesSet;
29 template <bool IsReadonly> struct CRSConstantTypes {
30 typedef ConstantInt ConstantIntTy;
31 typedef ConstantRangesSet ConstantRangesSetTy;
35 struct CRSConstantTypes<true> {
36 typedef const ConstantInt ConstantIntTy;
37 typedef const ConstantRangesSet ConstantRangesSetTy;
40 //===----------------------------------------------------------------------===//
41 /// ConstantRangesSet - class that implements constant set of ranges.
42 /// It is a wrapper for some real "holder" class (currently ConstantArray).
43 /// It contains functions, that allows to parse "holder" like a set of ranges.
44 /// Note: It is assumed that "holder" is inherited from Constant object.
45 /// ConstantRangesSet may be converted to and from Constant* pointer.
47 class ConstantRangesSet {
52 ConstantRangesSet(Constant *V) : Array(V) {}
54 operator Constant*() { return Array; }
55 operator const Constant*() const { return Array; }
56 Constant *operator->() { return Array; }
57 const Constant *operator->() const { return Array; }
59 template <bool IsReadonly>
62 typedef typename CRSConstantTypes<IsReadonly>::ConstantIntTy ConstantIntTy;
63 typedef std::pair<RangeT, RangeT> SubRes;
68 RangeT() : Low(0), High(0) {}
69 RangeT(const RangeT<false> &RHS) : Low(RHS.Low), High(RHS.High) {}
70 RangeT(ConstantIntTy *C) : Low(C), High(C) {}
71 RangeT(ConstantIntTy *L, ConstantIntTy *H) : Low(L), High(H) {}
73 bool operator<(const RangeT &RHS) const {
74 assert(Low && High && "Case range is not initialized.");
75 assert(RHS.Low && RHS.High && "Right case range is not initialized.");
76 const APInt &LowInt = Low->getValue();
77 const APInt &HighInt = High->getValue();
78 const APInt &RHSLowInt = RHS.Low->getValue();
79 const APInt &RHSHighInt = RHS.High->getValue();
80 if (LowInt.getBitWidth() == RHSLowInt.getBitWidth()) {
81 if (LowInt.eq(RHSLowInt)) {
82 if (HighInt.ult(RHSHighInt))
86 if (LowInt.ult(RHSLowInt))
90 return LowInt.getBitWidth() < RHSLowInt.getBitWidth();
93 bool operator==(const RangeT &RHS) const {
94 assert(Low && High && "Case range is not initialized.");
95 assert(RHS.Low && RHS.High && "Right case range is not initialized.");
96 if (Low->getValue().getBitWidth() != RHS.Low->getValue().getBitWidth())
98 return Low->getValue() == RHS.Low->getValue() &&
99 High->getValue() == RHS.High->getValue();
102 bool operator!=(const RangeT &RHS) const {
103 return !operator ==(RHS);
106 static bool LessBySize(const RangeT &LHS, const RangeT &RHS) {
107 assert(LHS.Low->getBitWidth() == RHS.Low->getBitWidth() &&
108 "This type of comparison requires equal bit width for LHS and RHS");
109 APInt LSize = LHS.High->getValue() - LHS.Low->getValue();
110 APInt RSize = RHS.High->getValue() - RHS.Low->getValue();;
111 return LSize.ult(RSize);
114 bool isInRange(const APInt &IntVal) const {
115 assert(Low && High && "Case range is not initialized.");
116 if (IntVal.getBitWidth() != Low->getValue().getBitWidth())
118 return IntVal.uge(Low->getValue()) && IntVal.ule(High->getValue());
121 bool isInRange(const ConstantIntTy *CI) const {
122 const APInt& IntVal = CI->getValue();
123 return isInRange(IntVal);
126 SubRes sub(const RangeT &RHS) const {
129 // RHS is either more global and includes this range or
130 // if it doesn't intersected with this range.
131 if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
133 // If RHS more global (it is enough to check
134 // only one border in this case.
135 if (RHS.isInRange(Low))
136 return std::make_pair(RangeT(Low, High), RangeT());
141 const APInt& LoInt = Low->getValue();
142 const APInt& HiInt = High->getValue();
143 APInt RHSLoInt = RHS.Low->getValue();
144 APInt RHSHiInt = RHS.High->getValue();
145 if (LoInt.ult(RHSLoInt)) {
147 Res.first.High = ConstantIntTy::get(RHS.Low->getContext(), --RHSLoInt);
149 if (HiInt.ugt(RHSHiInt)) {
150 Res.second.Low = ConstantIntTy::get(RHS.High->getContext(), ++RHSHiInt);
151 Res.second.High = High;
157 typedef RangeT<false> Range;
159 /// Checks is the given constant satisfies this case. Returns
160 /// true if it equals to one of contained values or belongs to the one of
161 /// contained ranges.
162 bool isSatisfies(const ConstantInt *C) const {
163 const APInt &CheckingVal = C->getValue();
164 for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
165 const Constant *CV = Array->getAggregateElement(i);
166 unsigned VecSize = cast<VectorType>(CV->getType())->getNumElements();
169 if (cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue() ==
175 cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue();
177 cast<const ConstantInt>(CV->getAggregateElement(1))->getValue();
178 if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal))
183 assert(0 && "Only pairs and single numbers are allowed here.");
190 /// Returns set's item with given index.
191 Range getItem(unsigned idx) {
192 Constant *CV = Array->getAggregateElement(idx);
193 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
196 return Range(cast<ConstantInt>(CV->getAggregateElement(0U)),
197 cast<ConstantInt>(CV->getAggregateElement(0U)));
199 return Range(cast<ConstantInt>(CV->getAggregateElement(0U)),
200 cast<ConstantInt>(CV->getAggregateElement(1)));
202 assert(0 && "Only pairs and single numbers are allowed here.");
207 const Range getItem(unsigned idx) const {
208 const Constant *CV = Array->getAggregateElement(idx);
210 unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
213 return Range(cast<ConstantInt>(
214 const_cast<Constant*>(CV->getAggregateElement(0U))),
216 const_cast<Constant*>(CV->getAggregateElement(0U))));
218 return Range(cast<ConstantInt>(
219 const_cast<Constant*>(CV->getAggregateElement(0U))),
221 const_cast<Constant*>(CV->getAggregateElement(1))));
223 assert(0 && "Only pairs and single numbers are allowed here.");
228 /// Return number of items (ranges) stored in set.
229 unsigned getNumItems() const {
230 return cast<ArrayType>(Array->getType())->getNumElements();
233 /// Returns set the size, that equals number of all values + sizes of all
235 /// Ranges set is considered as flat numbers collection.
236 /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
237 /// for range [<0>, <1>, <5>] the size will 3
238 unsigned getSize() const {
239 APInt sz(getItem(0).Low->getBitWidth(), 0);
240 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
241 const APInt &S = getItem(i).High->getValue() - getItem(i).Low->getValue();
244 return sz.getZExtValue();
247 /// Allows to access single value even if it belongs to some range.
248 /// Ranges set is considered as flat numbers collection.
249 /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
250 /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
251 APInt getSingleValue(unsigned idx) const {
252 APInt sz(getItem(0).Low->getBitWidth(), 0);
253 for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
254 const APInt& S = getItem(i).High->getValue() - getItem(i).Low->getValue();
257 if (oldSz.uge(i) && sz.ult(i)) {
258 APInt Res = getItem(i).Low->getValue();
259 APInt Offset(oldSz.getBitWidth(), i);
265 assert(0 && "Index exceeds high border.");
272 #endif /* CONSTANTRANGESSET_H_ */