#ifndef CONSTANTRANGESSET_H_
#define CONSTANTRANGESSET_H_
#include <list>
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/LLVMContext.h"
namespace llvm {
#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();
}
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(|=)
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(--)
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;
if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
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;
}
};
template <class IntTy>
class IntegersSubsetGeneric {
public:
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.");
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;
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 (unsigned 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;
}
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);
}
unsigned getNumItems() const {
return RangeLinks.size();
}
bool isSingleNumber() const {
return IsSingleNumber;
}
bool isSingleNumbersOnly() const {
return IsSingleNumbersOnly;
}
bool isSingleNumber(unsigned idx) const {
return RangeLinks[idx].first == RangeLinks[idx].second;
}
unsigned getSize() 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;
sz += S;
}
return sz.getZExtValue();
}
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;
}
const IntTy& getSingleNumber(unsigned idx) const {
assert(IsSingleNumbersOnly && "This method works properly if subset "
"contains single numbers only.");
return FlatCollection[idx];
}
};
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), 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);
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