-//===-- llvm/ConstantRangesSet.h - The constant set of ranges ---*- C++ -*-===//
+//===-- llvm/IntegersSubset.h - The subset of integers ----------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
//
/// @file
/// This file contains class that implements constant set of ranges:
-/// [<Low0,High0>,...,<LowN,HighN>]. Mainly, this set is used by SwitchInst and
-/// represents case value that may contain multiple ranges for a single
-/// successor.
-///
+/// [<Low0,High0>,...,<LowN,HighN>]. Initially, this class was created for
+/// SwitchInst and was used for case value representation that may contain
+/// multiple ranges for a single successor.
//
//===----------------------------------------------------------------------===//
return (const APInt&)ConstantIntVal->getValue();
}
- // Propogate APInt operators.
+ // Propagate APInt operators.
// Note, that
// /,/=,>>,>>= are not implemented in APInt.
// <<= is implemented for unsigned RHS, but not implemented for APInt RHS.
};
template<class IntType>
-struct IntRange {
-
- typedef IntRange<IntType> self;
+class IntRange {
+protected:
IntType Low;
IntType High;
bool IsEmpty : 1;
bool IsSingleNumber : 1;
-// TODO:
-// public:
-
+
+public:
+ typedef IntRange<IntType> self;
typedef std::pair<self, self> SubRes;
IntRange() : IsEmpty(true) {}
IntRange(const self &RHS) :
- Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
+ Low(RHS.Low), High(RHS.High),
+ IsEmpty(RHS.IsEmpty), IsSingleNumber(RHS.IsSingleNumber) {}
IntRange(const IntType &C) :
Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
+
IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
- IsEmpty(false), IsSingleNumber(false) {}
+ IsEmpty(false), IsSingleNumber(Low == High) {}
bool isEmpty() const { return IsEmpty; }
bool isSingleNumber() const { return IsSingleNumber; }
- const IntType& getLow() {
+ const IntType& getLow() const {
assert(!IsEmpty && "Range is empty.");
return Low;
}
- const IntType& getHigh() {
+ const IntType& getHigh() const {
assert(!IsEmpty && "Range is empty.");
return High;
}
typedef std::list<IntTy> FlatCollectionTy;
typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
typedef SmallVector<RangeLinkTy, 64> RangeLinksTy;
- typedef typename RangeLinksTy::iterator RangeLinksConstIt;
+ typedef typename RangeLinksTy::const_iterator RangeLinksConstIt;
+
+ typedef IntegersSubsetGeneric<IntTy> self;
protected:
public:
template<class RangesCollectionTy>
- IntegersSubsetGeneric(const RangesCollectionTy& Links) {
+ explicit IntegersSubsetGeneric(const RangesCollectionTy& Links) {
assert(Links.size() && "Empty ranges are not allowed.");
for (typename RangesCollectionTy::const_iterator i = Links.begin(),
e = Links.end(); i != e; ++i) {
RangeLinkTy RangeLink;
- FlatCollection.push_back(i->Low);
+ FlatCollection.push_back(i->getLow());
+ RangeLink.first = &FlatCollection.back();
+ if (i->getLow() != i->getHigh())
+ FlatCollection.push_back(i->getHigh());
+ RangeLink.second = &FlatCollection.back();
+ RangeLinks.push_back(RangeLink);
+ }
+ }
+
+ IntegersSubsetGeneric(const self& RHS) {
+ *this = RHS;
+ }
+
+ self& operator=(const self& RHS) {
+ FlatCollection.clear();
+ RangeLinks.clear();
+ for (RangeLinksConstIt i = RHS.RangeLinks.begin(), e = RHS.RangeLinks.end();
+ i != e; ++i) {
+ RangeLinkTy RangeLink;
+ FlatCollection.push_back(*(i->first));
RangeLink.first = &FlatCollection.back();
- if (i->Low != i->High)
- FlatCollection.push_back(i->High);
+ if (i->first != i->second)
+ FlatCollection.push_back(*(i->second));
RangeLink.second = &FlatCollection.back();
RangeLinks.push_back(RangeLink);
}
+ return *this;
}
typedef IntRange<IntTy> Range;
if (RangeLinks[i].first == RangeLinks[i].second) {
if (*RangeLinks[i].first == CheckingVal)
return true;
- } else if (*RangeLinks[i].first >= CheckingVal &&
- *RangeLinks[i].second <= CheckingVal)
+ } else if (*RangeLinks[i].first <= CheckingVal &&
+ *RangeLinks[i].second >= CheckingVal)
return true;
}
return false;
return RangeLinks.size();
}
- bool isSingleNumber(unsigned idx) const {
+ /// Returns true if whole subset contains single element.
+ bool isSingleNumber() const {
return RangeLinks.size() == 1 &&
RangeLinks[0].first == RangeLinks[0].second;
}
+
+ /// Does the same like getItem(idx).isSingleNumber(), but
+ /// works faster, since we avoid creation of temporary range object.
+ bool isSingleNumber(unsigned idx) const {
+ return RangeLinks[idx].first == RangeLinks[idx].second;
+ }
/// Returns set the size, that equals number of all values + sizes of all
/// ranges.
/// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
/// for range [<0>, <1>, <5>] the size will 3
unsigned getSize() const {
- APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0);
+ APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
- const APInt &Low = getItem(i).Low;
- const APInt &High = getItem(i).High;
- const APInt &S = High - Low;
+ const APInt &Low = getItem(i).getLow();
+ const APInt &High = getItem(i).getHigh();
+ APInt S = High - Low + 1;
sz += S;
}
return sz.getZExtValue();
/// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
/// For range [<1>, <4,8>] getSingleValue(3) returns 6.
APInt getSingleValue(unsigned idx) const {
- APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0);
+ APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
- const APInt &Low = getItem(i).Low;
- const APInt &High = getItem(i).High;
- const APInt& S = High - Low;
+ const APInt &Low = getItem(i).getLow();
+ const APInt &High = getItem(i).getHigh();
+ APInt S = High - Low + 1;
APInt oldSz = sz;
sz += S;
- if (oldSz.uge(i) && sz.ult(i)) {
+ if (sz.ugt(idx)) {
APInt Res = Low;
- APInt Offset(oldSz.getBitWidth(), i);
+ APInt Offset(oldSz.getBitWidth(), idx);
Offset -= oldSz;
Res += Offset;
return Res;
IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
Holder(C) {}
- // implicit
template<class RangesCollectionTy>
- IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) {
+ explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) {
std::vector<Constant*> Elts;
Elts.reserve(Src.size());
for (typename RangesCollectionTy::const_iterator i = Src.begin(),
e = Src.end(); i != e; ++i) {
const Range &R = *i;
std::vector<Constant*> r;
- if (R.Low != R.High) {
+ if (R.isSingleNumber()) {
r.reserve(2);
// FIXME: Since currently we have ConstantInt based numbers
// use hack-conversion of IntItem to ConstantInt
- r.push_back(R.Low.toConstantInt());
- r.push_back(R.High.toConstantInt());
+ r.push_back(R.getLow().toConstantInt());
+ r.push_back(R.getHigh().toConstantInt());
} else {
r.reserve(1);
- r.push_back(R.Low.toConstantInt());
+ r.push_back(R.getLow().toConstantInt());
}
Constant *CV = ConstantVector::get(r);
Elts.push_back(CV);