diff options
Diffstat (limited to 'include/llvm/Support/IntegersSubset.h')
| -rw-r--r-- | include/llvm/Support/IntegersSubset.h | 540 |
1 files changed, 0 insertions, 540 deletions
diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h deleted file mode 100644 index 64b79ee..0000000 --- a/include/llvm/Support/IntegersSubset.h +++ /dev/null @@ -1,540 +0,0 @@ -//===-- llvm/IntegersSubset.h - The subset of integers ----------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -/// @file -/// This file contains class that implements constant set of ranges: -/// [<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 LLVM_SUPPORT_INTEGERSSUBSET_H -#define LLVM_SUPPORT_INTEGERSSUBSET_H - -#include "llvm/IR/Constants.h" -#include "llvm/IR/DerivedTypes.h" -#include "llvm/IR/LLVMContext.h" -#include <list> - -namespace llvm { - - // The IntItem is a wrapper for APInt. - // 1. It determines sign of integer, it allows to use - // comparison operators >,<,>=,<=, and as result we got shorter and cleaner - // constructions. - // 2. It helps to implement PR1255 (case ranges) as a series of small patches. - // 3. Currently we can interpret IntItem both as ConstantInt and as APInt. - // It allows to provide SwitchInst methods that works with ConstantInt for - // non-updated passes. And it allows to use APInt interface for new methods. - // 4. IntItem can be easily replaced with APInt. - - // The set of macros that allows to propagate APInt operators to the IntItem. - -#define INT_ITEM_DEFINE_COMPARISON(op,func) \ - bool operator op (const APInt& RHS) const { \ - return getAPIntValue().func(RHS); \ - } - -#define INT_ITEM_DEFINE_UNARY_OP(op) \ - IntItem operator op () const { \ - APInt res = op(getAPIntValue()); \ - Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ - return IntItem(cast<ConstantInt>(NewVal)); \ - } - -#define INT_ITEM_DEFINE_BINARY_OP(op) \ - IntItem operator op (const APInt& RHS) const { \ - APInt res = getAPIntValue() op RHS; \ - Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ - return IntItem(cast<ConstantInt>(NewVal)); \ - } - -#define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \ - IntItem& operator op (const APInt& RHS) {\ - APInt res = getAPIntValue();\ - res op RHS; \ - Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ - ConstantIntVal = cast<ConstantInt>(NewVal); \ - return *this; \ - } - -#define INT_ITEM_DEFINE_PREINCDEC(op) \ - IntItem& operator op () { \ - APInt res = getAPIntValue(); \ - op(res); \ - Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ - ConstantIntVal = cast<ConstantInt>(NewVal); \ - return *this; \ - } - -#define INT_ITEM_DEFINE_POSTINCDEC(op) \ - IntItem& operator op (int) { \ - APInt res = getAPIntValue();\ - op(res); \ - Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ - OldConstantIntVal = ConstantIntVal; \ - ConstantIntVal = cast<ConstantInt>(NewVal); \ - return IntItem(OldConstantIntVal); \ - } - -#define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \ - RetTy operator op (IntTy RHS) const { \ - return (*this) op APInt(getAPIntValue().getBitWidth(), RHS); \ - } - -class IntItem { - ConstantInt *ConstantIntVal; - const APInt* APIntVal; - IntItem(const ConstantInt *V) : - ConstantIntVal(const_cast<ConstantInt*>(V)), - APIntVal(&ConstantIntVal->getValue()){} - const APInt& getAPIntValue() const { - return *APIntVal; - } -public: - - IntItem() {} - - operator const APInt&() const { - return getAPIntValue(); - } - - // 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_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) { - APInt res = getAPIntValue(); - res <<= RHS; - Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); - ConstantIntVal = cast<ConstantInt>(NewVal); - return *this; - } - - INT_ITEM_DEFINE_UNARY_OP(-) - INT_ITEM_DEFINE_UNARY_OP(~) - - INT_ITEM_DEFINE_PREINCDEC(++) - INT_ITEM_DEFINE_PREINCDEC(--) - - // The set of workarounds, since currently we use ConstantInt implemented - // integer. - - static IntItem fromConstantInt(const ConstantInt *V) { - return IntItem(V); - } - static IntItem fromType(Type* Ty, const APInt& V) { - ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V)); - return fromConstantInt(C); - } - static IntItem withImplLikeThis(const IntItem& LikeThis, const APInt& V) { - ConstantInt *C = cast<ConstantInt>(ConstantInt::get( - LikeThis.ConstantIntVal->getContext(), V)); - return fromConstantInt(C); - } - ConstantInt *toConstantInt() const { - return ConstantIntVal; - } -}; - -template<class IntType> -class IntRange { -protected: - IntType Low; - IntType High; - bool IsEmpty : 1; - bool IsSingleNumber : 1; - -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(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(Low == High) {} - - bool isEmpty() const { return IsEmpty; } - bool isSingleNumber() const { return IsSingleNumber; } - - const IntType& getLow() const { - assert(!IsEmpty && "Range is empty."); - return Low; - } - const IntType& getHigh() const { - assert(!IsEmpty && "Range is empty."); - return High; - } - - bool operator<(const self &RHS) const { - assert(!IsEmpty && "Left range is empty."); - assert(!RHS.IsEmpty && "Right range is empty."); - if (Low == RHS.Low) { - if (High > RHS.High) - return true; - return false; - } - if (Low < RHS.Low) - return true; - return false; - } - - 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 self &RHS) const { - return !operator ==(RHS); - } - - static bool LessBySize(const self &LHS, const self &RHS) { - return (LHS.High - LHS.Low) < (RHS.High - RHS.Low); - } - - bool isInRange(const IntType &IntVal) const { - assert(!IsEmpty && "Range is empty."); - return IntVal >= Low && IntVal <= High; - } - - SubRes sub(const self &RHS) const { - SubRes Res; - - // RHS is either more global and includes this range or - // if it doesn't intersected with this range. - if (!isInRange(RHS.Low) && !isInRange(RHS.High)) { - - // If RHS more global (it is enough to check - // only one border in this case. - if (RHS.isInRange(Low)) - return std::make_pair(self(Low, High), self()); - - return Res; - } - - if (Low < RHS.Low) { - Res.first.Low = Low; - IntType NewHigh = RHS.Low; - --NewHigh; - Res.first.High = NewHigh; - } - if (High > RHS.High) { - IntType NewLow = RHS.High; - ++NewLow; - Res.second.Low = NewLow; - Res.second.High = High; - } - return Res; - } - }; - -//===----------------------------------------------------------------------===// -/// 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::vector<IntTy> FlatCollectionTy; - typedef std::pair<IntTy*, IntTy*> RangeLinkTy; - typedef std::vector<RangeLinkTy> RangeLinksTy; - typedef typename RangeLinksTy::const_iterator RangeLinksConstIt; - - typedef IntegersSubsetGeneric<IntTy> self; - -protected: - - FlatCollectionTy FlatCollection; - RangeLinksTy RangeLinks; - - bool IsSingleNumber; - bool IsSingleNumbersOnly; - -public: - - template<class RangesCollectionTy> - explicit IntegersSubsetGeneric(const RangesCollectionTy& Links) { - assert(Links.size() && "Empty ranges are not allowed."); - - // In case of big set of single numbers consumes additional RAM space, - // but allows to avoid additional reallocation. - FlatCollection.reserve(Links.size() * 2); - RangeLinks.reserve(Links.size()); - IsSingleNumbersOnly = true; - 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()); - IsSingleNumbersOnly = false; - } - RangeLink.second = &FlatCollection.back(); - RangeLinks.push_back(RangeLink); - } - IsSingleNumber = IsSingleNumbersOnly && RangeLinks.size() == 1; - } - - IntegersSubsetGeneric(const self& RHS) { - *this = RHS; - } - - self& operator=(const self& RHS) { - FlatCollection.clear(); - RangeLinks.clear(); - FlatCollection.reserve(RHS.RangeLinks.size() * 2); - RangeLinks.reserve(RHS.RangeLinks.size()); - 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); - } - IsSingleNumber = RHS.IsSingleNumber; - IsSingleNumbersOnly = RHS.IsSingleNumbersOnly; - return *this; - } - - 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 IntTy &CheckingVal) const { - if (IsSingleNumber) - return FlatCollection.front() == CheckingVal; - if (IsSingleNumbersOnly) - return std::find(FlatCollection.begin(), - FlatCollection.end(), - CheckingVal) != FlatCollection.end(); - - for (size_t i = 0, e = getNumItems(); i < e; ++i) { - if (RangeLinks[i].first == RangeLinks[i].second) { - if (*RangeLinks[i].first == CheckingVal) - return true; - } 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) 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. - size_t getNumItems() const { - return RangeLinks.size(); - } - - /// Returns true if whole subset contains single element. - bool isSingleNumber() const { - return IsSingleNumber; - } - - /// Returns true if whole subset contains only single numbers, no ranges. - bool isSingleNumbersOnly() const { - return IsSingleNumbersOnly; - } - - /// 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. - /// Ranges set is considered as flat numbers collection. - /// 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).getLow()).getBitWidth(), 0); - for (size_t i = 0, e = getNumItems(); i != e; ++i) { - const APInt Low = getItem(i).getLow(); - const APInt High = getItem(i).getHigh(); - APInt S = High - Low + 1; - sz += S; - } - return sz.getZExtValue(); - } - - /// Allows to access single value even if it belongs to some range. - /// Ranges set is considered as flat numbers collection. - /// [<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).getLow()).getBitWidth(), 0); - for (unsigned i = 0, e = getNumItems(); i != e; ++i) { - const APInt Low = getItem(i).getLow(); - const APInt High = getItem(i).getHigh(); - APInt S = High - Low + 1; - APInt oldSz = sz; - sz += S; - if (sz.ugt(idx)) { - APInt Res = Low; - APInt Offset(oldSz.getBitWidth(), idx); - Offset -= oldSz; - Res += Offset; - return Res; - } - } - assert(0 && "Index exceeds high border."); - return sz; - } - - /// Does the same as getSingleValue, but works only if subset contains - /// single numbers only. - const IntTy& getSingleNumber(unsigned idx) const { - assert(IsSingleNumbersOnly && "This method works properly if subset " - "contains single numbers only."); - return FlatCollection[idx]; - } -}; - -//===----------------------------------------------------------------------===// -/// 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: - - explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), - Holder(C) {} - - IntegersSubset(const IntegersSubset& RHS) : - ParentTy(*(const ParentTy *)&RHS), // FIXME: tweak for msvc. - Holder(RHS.Holder) {} - - 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 /* CLLVM_SUPPORT_INTEGERSSUBSET_H */ |