-//===-- 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.
//
//===----------------------------------------------------------------------===//
#ifndef CONSTANTRANGESSET_H_
#define CONSTANTRANGESSET_H_
+#include <list>
+
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/LLVMContext.h"
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.
- INT_ITEM_DEFINE_COMPARISON(<, ult);
- INT_ITEM_DEFINE_COMPARISON(>, ugt);
- INT_ITEM_DEFINE_COMPARISON(<=, ule);
- INT_ITEM_DEFINE_COMPARISON(>=, uge);
- INT_ITEM_DEFINE_COMPARISON(==, eq);
- INT_ITEM_DEFINE_COMPARISON(!=, ne);
-
- INT_ITEM_DEFINE_BINARY_OP(*);
- INT_ITEM_DEFINE_BINARY_OP(+);
- INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,+,uint64_t);
- INT_ITEM_DEFINE_BINARY_OP(-);
- INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,-,uint64_t);
- INT_ITEM_DEFINE_BINARY_OP(<<);
- INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,<<,unsigned);
- INT_ITEM_DEFINE_BINARY_OP(&);
- INT_ITEM_DEFINE_BINARY_OP(^);
- INT_ITEM_DEFINE_BINARY_OP(|);
-
- INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(*=);
- INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(+=);
- INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(-=);
- INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(&=);
- INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(^=);
- INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(|=);
+ INT_ITEM_DEFINE_COMPARISON(<, ult)
+ INT_ITEM_DEFINE_COMPARISON(>, ugt)
+ INT_ITEM_DEFINE_COMPARISON(<=, ule)
+ INT_ITEM_DEFINE_COMPARISON(>=, uge)
+
+ INT_ITEM_DEFINE_COMPARISON(==, eq)
+ INT_ITEM_DEFINE_OP_STANDARD_INT(bool,==,uint64_t)
+
+ INT_ITEM_DEFINE_COMPARISON(!=, ne)
+ INT_ITEM_DEFINE_OP_STANDARD_INT(bool,!=,uint64_t)
+
+ INT_ITEM_DEFINE_BINARY_OP(*)
+ INT_ITEM_DEFINE_BINARY_OP(+)
+ INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,+,uint64_t)
+ INT_ITEM_DEFINE_BINARY_OP(-)
+ INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,-,uint64_t)
+ INT_ITEM_DEFINE_BINARY_OP(<<)
+ INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,<<,unsigned)
+ INT_ITEM_DEFINE_BINARY_OP(&)
+ INT_ITEM_DEFINE_BINARY_OP(^)
+ INT_ITEM_DEFINE_BINARY_OP(|)
+
+ INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(*=)
+ INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(+=)
+ INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(-=)
+ INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(&=)
+ INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(^=)
+ INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(|=)
// Special case for <<=
IntItem& operator <<= (unsigned RHS) {
return *this;
}
- INT_ITEM_DEFINE_UNARY_OP(-);
- INT_ITEM_DEFINE_UNARY_OP(~);
+ INT_ITEM_DEFINE_UNARY_OP(-)
+ INT_ITEM_DEFINE_UNARY_OP(~)
- INT_ITEM_DEFINE_PREINCDEC(++);
- INT_ITEM_DEFINE_PREINCDEC(--);
+ INT_ITEM_DEFINE_PREINCDEC(++)
+ INT_ITEM_DEFINE_PREINCDEC(--)
// The set of workarounds, since currently we use ConstantInt implemented
// integer.
LikeThis.ConstantIntVal->getContext(), V));
return fromConstantInt(C);
}
- ConstantInt *toConstantInt() {
+ ConstantInt *toConstantInt() const {
return ConstantIntVal;
}
};
-// TODO: it should be a class in next commit.
-struct IntRange {
-
- IntItem Low;
- IntItem High;
+template<class IntType>
+class IntRange {
+protected:
+ IntType Low;
+ IntType High;
bool IsEmpty : 1;
bool IsSingleNumber : 1;
-// TODO:
-// public:
-
- typedef std::pair<IntRange, IntRange> SubRes;
+
+public:
+ typedef IntRange<IntType> self;
+ typedef std::pair<self, self> SubRes;
IntRange() : IsEmpty(true) {}
- IntRange(const IntRange &RHS) :
- Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
- IntRange(const IntItem &C) :
+ IntRange(const self &RHS) :
+ 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 IntItem &L, const IntItem &H) : Low(L), High(H),
- IsEmpty(false), IsSingleNumber(false) {}
+
+ IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
+ IsEmpty(false), IsSingleNumber(Low == High) {}
bool isEmpty() const { return IsEmpty; }
bool isSingleNumber() const { return IsSingleNumber; }
- const IntItem& getLow() {
+ const IntType& getLow() const {
assert(!IsEmpty && "Range is empty.");
return Low;
}
- const IntItem& getHigh() {
+ const IntType& getHigh() const {
assert(!IsEmpty && "Range is empty.");
return High;
}
- bool operator<(const IntRange &RHS) const {
+ bool operator<(const self &RHS) const {
assert(!IsEmpty && "Left range is empty.");
assert(!RHS.IsEmpty && "Right range is empty.");
if (Low == RHS.Low) {
return false;
}
- bool operator==(const IntRange &RHS) const {
+ bool operator==(const self &RHS) const {
assert(!IsEmpty && "Left range is empty.");
assert(!RHS.IsEmpty && "Right range is empty.");
return Low == RHS.Low && High == RHS.High;
}
- bool operator!=(const IntRange &RHS) const {
+ bool operator!=(const self &RHS) const {
return !operator ==(RHS);
}
- static bool LessBySize(const IntRange &LHS, const IntRange &RHS) {
+ static bool LessBySize(const self &LHS, const self &RHS) {
return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
}
- bool isInRange(const IntItem &IntVal) const {
+ bool isInRange(const IntType &IntVal) const {
assert(!IsEmpty && "Range is empty.");
return IntVal >= Low && IntVal <= High;
}
- SubRes sub(const IntRange &RHS) const {
+ SubRes sub(const self &RHS) const {
SubRes Res;
// RHS is either more global and includes this range or
// If RHS more global (it is enough to check
// only one border in this case.
if (RHS.isInRange(Low))
- return std::make_pair(IntRange(Low, High), IntRange());
+ return std::make_pair(self(Low, High), self());
return Res;
}
if (Low < RHS.Low) {
Res.first.Low = Low;
- IntItem NewHigh = RHS.Low;
+ IntType NewHigh = RHS.Low;
--NewHigh;
Res.first.High = NewHigh;
}
if (High > RHS.High) {
- IntItem NewLow = RHS.High;
+ IntType NewLow = RHS.High;
++NewLow;
Res.second.Low = NewLow;
Res.second.High = High;
};
//===----------------------------------------------------------------------===//
-/// ConstantRangesSet - class that implements constant set of ranges.
-/// It is a wrapper for some real "holder" class (currently ConstantArray).
-/// It contains functions, that allows to parse "holder" like a set of ranges.
-/// Note: It is assumed that "holder" is inherited from Constant object.
-/// ConstantRangesSet may be converted to and from Constant* pointer.
-///
-class IntegersSubset {
- Constant *Array;
+/// IntegersSubsetGeneric - class that implements the subset of integers. It
+/// consists from ranges and single numbers.
+template <class IntTy>
+class IntegersSubsetGeneric {
+public:
+ // Use Chris Lattner idea, that was initially described here:
+ // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120213/136954.html
+ // In short, for more compact memory consumption we can store flat
+ // numbers collection, and define range as pair of indices.
+ // In that case we can safe some memory on 32 bit machines.
+ typedef std::list<IntTy> FlatCollectionTy;
+ typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
+ typedef SmallVector<RangeLinkTy, 64> RangeLinksTy;
+ typedef typename RangeLinksTy::const_iterator RangeLinksConstIt;
+
+ typedef IntegersSubsetGeneric<IntTy> self;
+
+protected:
+
+ FlatCollectionTy FlatCollection;
+ RangeLinksTy RangeLinks;
+
public:
- bool IsWide;
+ template<class RangesCollectionTy>
+ 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->getLow());
+ RangeLink.first = &FlatCollection.back();
+ if (i->getLow() != i->getHigh())
+ FlatCollection.push_back(i->getHigh());
+ RangeLink.second = &FlatCollection.back();
+ RangeLinks.push_back(RangeLink);
+ }
+ }
- // implicit
- IntegersSubset(Constant *V) : Array(V) {
- ArrayType *ArrTy = cast<ArrayType>(Array->getType());
- VectorType *VecTy = cast<VectorType>(ArrTy->getElementType());
- IntegerType *IntTy = cast<IntegerType>(VecTy->getElementType());
- IsWide = IntTy->getBitWidth() > 64;
+ IntegersSubsetGeneric(const self& RHS) {
+ *this = RHS;
}
- operator Constant*() { return Array; }
- operator const Constant*() const { return Array; }
- Constant *operator->() { return Array; }
- const Constant *operator->() const { return Array; }
+ 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->first != i->second)
+ FlatCollection.push_back(*(i->second));
+ RangeLink.second = &FlatCollection.back();
+ RangeLinks.push_back(RangeLink);
+ }
+ return *this;
+ }
- typedef IntRange Range;
+ typedef IntRange<IntTy> Range;
/// Checks is the given constant satisfies this case. Returns
/// true if it equals to one of contained values or belongs to the one of
/// contained ranges.
- bool isSatisfies(const IntItem &CheckingVal) const {
+ bool isSatisfies(const IntTy &CheckingVal) const {
for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
- const Constant *CV = Array->getAggregateElement(i);
- unsigned VecSize = cast<VectorType>(CV->getType())->getNumElements();
- switch (VecSize) {
- case 1:
- if (cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue() ==
- CheckingVal)
- return true;
- break;
- case 2: {
- const APInt &Lo =
- cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue();
- const APInt &Hi =
- cast<const ConstantInt>(CV->getAggregateElement(1))->getValue();
- if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal))
+ if (RangeLinks[i].first == RangeLinks[i].second) {
+ if (*RangeLinks[i].first == CheckingVal)
return true;
- }
- break;
- default:
- assert(0 && "Only pairs and single numbers are allowed here.");
- break;
- }
+ } else if (*RangeLinks[i].first <= CheckingVal &&
+ *RangeLinks[i].second >= CheckingVal)
+ return true;
}
return false;
}
/// Returns set's item with given index.
- Range getItem(unsigned idx) {
- Constant *CV = Array->getAggregateElement(idx);
- unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
- switch (NumEls) {
- case 1:
- return Range(IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(0U))));
- case 2:
- return Range(IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(0U))),
- IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(1U))));
- default:
- assert(0 && "Only pairs and single numbers are allowed here.");
- return Range();
- }
- }
-
- const Range getItem(unsigned idx) const {
- const Constant *CV = Array->getAggregateElement(idx);
-
- unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
- switch (NumEls) {
- case 1:
- return Range(IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(0U))),
- IntItem::fromConstantInt(cast<ConstantInt>(
- cast<ConstantInt>(CV->getAggregateElement(0U)))));
- case 2:
- return Range(IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(0U))),
- IntItem::fromConstantInt(
- cast<ConstantInt>(CV->getAggregateElement(1))));
- default:
- assert(0 && "Only pairs and single numbers are allowed here.");
- return Range();
- }
- }
+ Range getItem(unsigned idx) const {
+ const RangeLinkTy &Link = RangeLinks[idx];
+ if (Link.first != Link.second)
+ return Range(*Link.first, *Link.second);
+ else
+ return Range(*Link.first);
+ }
/// Return number of items (ranges) stored in set.
unsigned getNumItems() const {
- return cast<ArrayType>(Array->getType())->getNumElements();
+ return RangeLinks.size();
}
- bool isWideNumberFormat() const { return IsWide; }
-
+ /// 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 {
- Constant *CV = Array->getAggregateElement(idx);
- return cast<VectorType>(CV->getType())->getNumElements() == 1;
+ return RangeLinks[idx].first == RangeLinks[idx].second;
}
/// Returns set the size, that equals number of all values + sizes of all
/// 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 - currently is extension of IntegersSubsetGeneric
+/// that also supports conversion to/from Constant* object.
+class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
+
+ typedef IntegersSubsetGeneric<IntItem> ParentTy;
+
+ Constant *Holder;
+
+ static unsigned getNumItemsFromConstant(Constant *C) {
+ return cast<ArrayType>(C->getType())->getNumElements();
+ }
+
+ static Range getItemFromConstant(Constant *C, unsigned idx) {
+ const Constant *CV = C->getAggregateElement(idx);
+
+ unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
+ switch (NumEls) {
+ case 1:
+ return Range(IntItem::fromConstantInt(
+ cast<ConstantInt>(CV->getAggregateElement(0U))),
+ IntItem::fromConstantInt(cast<ConstantInt>(
+ cast<ConstantInt>(CV->getAggregateElement(0U)))));
+ case 2:
+ return Range(IntItem::fromConstantInt(
+ cast<ConstantInt>(CV->getAggregateElement(0U))),
+ IntItem::fromConstantInt(
+ cast<ConstantInt>(CV->getAggregateElement(1))));
+ default:
+ assert(0 && "Only pairs and single numbers are allowed here.");
+ return Range();
+ }
+ }
+
+ std::vector<Range> rangesFromConstant(Constant *C) {
+ unsigned NumItems = getNumItemsFromConstant(C);
+ std::vector<Range> r;
+ r.reserve(NumItems);
+ for (unsigned i = 0, e = NumItems; i != e; ++i)
+ r.push_back(getItemFromConstant(C, i));
+ return r;
+ }
+
+public:
+
+ IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
+ Holder(C) {}
+
+ template<class RangesCollectionTy>
+ 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.isSingleNumber()) {
+ r.reserve(2);
+ // FIXME: Since currently we have ConstantInt based numbers
+ // use hack-conversion of IntItem to ConstantInt
+ r.push_back(R.getLow().toConstantInt());
+ r.push_back(R.getHigh().toConstantInt());
+ } else {
+ r.reserve(1);
+ r.push_back(R.getLow().toConstantInt());
+ }
+ Constant *CV = ConstantVector::get(r);
+ Elts.push_back(CV);
+ }
+ ArrayType *ArrTy =
+ ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
+ Holder = ConstantArray::get(ArrTy, Elts);
+ }
+
+ operator Constant*() { return Holder; }
+ operator const Constant*() const { return Holder; }
+ Constant *operator->() { return Holder; }
+ const Constant *operator->() const { return Holder; }
+};
+
}
#endif /* CONSTANTRANGESSET_H_ */
projects / oota-llvm.git / blobdiff