From 0aa32d5d0ff6cd65b6cff957858a79e2d2a614bd Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Tue, 29 May 2012 12:26:47 +0000 Subject: ConstantRangesSet renamed to IntegersSubset. CRSBuilder renamed to IntegersSubsetMapping. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157612 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 372 ++++++++++++++++++++++++++++++++++ 1 file changed, 372 insertions(+) create mode 100644 include/llvm/Support/IntegersSubset.h (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h new file mode 100644 index 0000000..894b104 --- /dev/null +++ b/include/llvm/Support/IntegersSubset.h @@ -0,0 +1,372 @@ +//===-- llvm/ConstantRangesSet.h - The constant set of ranges ---*- 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: +/// [,...,]. Mainly, this set is used by SwitchInst and +/// represents case value that may contain multiple ranges for a single +/// successor. +/// +// +//===----------------------------------------------------------------------===// + +#ifndef CONSTANTRANGESSET_H_ +#define CONSTANTRANGESSET_H_ + +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/LLVMContext.h" + +namespace llvm { + +template +class IntItemBase { +protected: + ImplTy Implementation; + typedef IntItemBase self; +public: + + IntItemBase() {} + + IntItemBase(const ImplTy &impl) : Implementation(impl) {} + + // implicit + IntItemBase(const APInt& src) : Implementation(src) {} + + operator const APInt&() const { + return (const APInt&)Implementation; + } + bool operator<(const self& RHS) const { + return ((const APInt&)*this).ult(RHS); + } + bool operator==(const self& RHS) const { + return (const APInt&)*this == (const APInt&)RHS; + } + bool operator!=(const self& RHS) const { + return (const APInt&)*this != (const APInt&)RHS; + } + self& operator=(const ImplTy& RHS) { + Implementation = RHS; + return *this; + } + const APInt* operator->() const { + return &((const APInt&)Implementation); + } + const APInt& operator*() const { + return ((const APInt&)Implementation); + } + // FIXME: Hack. Will removed. + ImplTy& getImplementation() { + return Implementation; + } +}; + +class IntItemConstantIntImpl { + const ConstantInt *ConstantIntVal; +public: + IntItemConstantIntImpl() : ConstantIntVal(0) {} + IntItemConstantIntImpl(const ConstantInt *Val) : ConstantIntVal(Val) {} + IntItemConstantIntImpl(LLVMContext &Ctx, const APInt& src) { + ConstantIntVal = cast(ConstantInt::get(Ctx, src)); + } + explicit IntItemConstantIntImpl(const APInt& src) { + ConstantIntVal = + cast(ConstantInt::get(llvm::getGlobalContext(), src)); + } + operator const APInt&() const { + return ConstantIntVal->getValue(); + } + operator const ConstantInt*() { + return ConstantIntVal; + } +}; + +class IntItem : public IntItemBase { + typedef IntItemBase ParentTy; + IntItem(const IntItemConstantIntImpl& Impl) : ParentTy(Impl) {} +public: + + IntItem() {} + + // implicit + IntItem(const APInt& src) : ParentTy(src) {} + + static IntItem fromConstantInt(const ConstantInt *V) { + IntItemConstantIntImpl Impl(V); + return IntItem(Impl); + } + static IntItem fromType(Type* Ty, const APInt& V) { + ConstantInt *C = cast(ConstantInt::get(Ty, V)); + return fromConstantInt(C); + } + ConstantInt *toConstantInt() { + return const_cast((const ConstantInt*)Implementation); + } +}; + +// TODO: it should be a class in next commit. +struct IntRange { + + IntItem Low; + IntItem High; + bool IsEmpty : 1; + bool IsSingleNumber : 1; +// TODO: +// public: + + typedef std::pair SubRes; + + IntRange() : IsEmpty(true) {} + IntRange(const IntRange &RHS) : + Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {} + IntRange(const IntItem &C) : + Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {} + IntRange(const IntItem &L, const IntItem &H) : Low(L), High(H), + IsEmpty(false), IsSingleNumber(false) {} + + bool isEmpty() const { return IsEmpty; } + bool isSingleNumber() const { return IsSingleNumber; } + + const IntItem& getLow() { + assert(!IsEmpty && "Range is empty."); + return Low; + } + const IntItem& getHigh() { + assert(!IsEmpty && "Range is empty."); + return High; + } + + bool operator<(const IntRange &RHS) const { + assert(!IsEmpty && "Left range is empty."); + assert(!RHS.IsEmpty && "Right range is empty."); + if (Low->getBitWidth() == RHS.Low->getBitWidth()) { + if (Low->eq(RHS.Low)) { + if (High->ult(RHS.High)) + return true; + return false; + } + if (Low->ult(RHS.Low)) + return true; + return false; + } else + return Low->getBitWidth() < RHS.Low->getBitWidth(); + } + + bool operator==(const IntRange &RHS) const { + assert(!IsEmpty && "Left range is empty."); + assert(!RHS.IsEmpty && "Right range is empty."); + if (Low->getBitWidth() != RHS.Low->getBitWidth()) + return false; + return Low == RHS.Low && High == RHS.High; + } + + bool operator!=(const IntRange &RHS) const { + return !operator ==(RHS); + } + + static bool LessBySize(const IntRange &LHS, const IntRange &RHS) { + assert(LHS.Low->getBitWidth() == RHS.Low->getBitWidth() && + "This type of comparison requires equal bit width for LHS and RHS"); + APInt LSize = *LHS.High - *LHS.Low; + APInt RSize = *RHS.High - *RHS.Low; + return LSize.ult(RSize); + } + + bool isInRange(const APInt &IntVal) const { + assert(!IsEmpty && "Range is empty."); + if (IntVal.getBitWidth() != Low->getBitWidth()) + return false; + return IntVal.uge(Low) && IntVal.ule(High); + } + + SubRes sub(const IntRange &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(IntRange(Low, High), IntRange()); + + return Res; + } + + if (Low->ult(RHS.Low)) { + Res.first.Low = Low; + APInt NewHigh = RHS.Low; + --NewHigh; + Res.first.High = NewHigh; + } + if (High->ugt(RHS.High)) { + APInt NewLow = RHS.High; + ++NewLow; + Res.second.Low = NewLow; + Res.second.High = High; + } + return Res; + } + }; + +//===----------------------------------------------------------------------===// +/// 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; +public: + + bool IsWide; + + // implicit + IntegersSubset(Constant *V) : Array(V) { + ArrayType *ArrTy = cast(Array->getType()); + VectorType *VecTy = cast(ArrTy->getElementType()); + IntegerType *IntTy = cast(VecTy->getElementType()); + IsWide = IntTy->getBitWidth() > 64; + } + + operator Constant*() { return Array; } + operator const Constant*() const { return Array; } + Constant *operator->() { return Array; } + const Constant *operator->() const { return Array; } + + typedef IntRange 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 { + for (unsigned i = 0, e = getNumItems(); i < e; ++i) { + const Constant *CV = Array->getAggregateElement(i); + unsigned VecSize = cast(CV->getType())->getNumElements(); + switch (VecSize) { + case 1: + if (cast(CV->getAggregateElement(0U))->getValue() == + CheckingVal) + return true; + break; + case 2: { + const APInt &Lo = + cast(CV->getAggregateElement(0U))->getValue(); + const APInt &Hi = + cast(CV->getAggregateElement(1))->getValue(); + if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal)) + return true; + } + break; + default: + assert(0 && "Only pairs and single numbers are allowed here."); + break; + } + } + return false; + } + + /// Returns set's item with given index. + Range getItem(unsigned idx) { + Constant *CV = Array->getAggregateElement(idx); + unsigned NumEls = cast(CV->getType())->getNumElements(); + switch (NumEls) { + case 1: + return Range(IntItem::fromConstantInt( + cast(CV->getAggregateElement(0U)))); + case 2: + return Range(IntItem::fromConstantInt( + cast(CV->getAggregateElement(0U))), + IntItem::fromConstantInt( + cast(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(CV->getType())->getNumElements(); + switch (NumEls) { + case 1: + return Range(IntItem::fromConstantInt( + cast(CV->getAggregateElement(0U))), + IntItem::fromConstantInt(cast( + cast(CV->getAggregateElement(0U))))); + case 2: + return Range(IntItem::fromConstantInt( + cast(CV->getAggregateElement(0U))), + IntItem::fromConstantInt( + cast(CV->getAggregateElement(1)))); + default: + assert(0 && "Only pairs and single numbers are allowed here."); + return Range(); + } + } + + /// Return number of items (ranges) stored in set. + unsigned getNumItems() const { + return cast(Array->getType())->getNumElements(); + } + + bool isWideNumberFormat() const { return IsWide; } + + bool isSingleNumber(unsigned idx) const { + Constant *CV = Array->getAggregateElement(idx); + return cast(CV->getType())->getNumElements() == 1; + } + + /// 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(getItem(0).Low->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; + 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(getItem(0).Low->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; + APInt oldSz = sz; + sz += S; + if (oldSz.uge(i) && sz.ult(i)) { + APInt Res = Low; + APInt Offset(oldSz.getBitWidth(), i); + Offset -= oldSz; + Res += Offset; + return Res; + } + } + assert(0 && "Index exceeds high border."); + return sz; + } +}; + +} + +#endif /* CONSTANTRANGESSET_H_ */ -- cgit v1.1 From f8d14c4ca3874890cfd8867d9557efca9511c98f Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Fri, 1 Jun 2012 10:06:14 +0000 Subject: PR1255: case ranges. IntItem cleanup. IntItemBase, IntItemConstantIntImp and IntItem merged into IntItem. All arithmetic operators was propogated from APInt. Also added comparison operators <,>,<=,>=. Currently you will find set of macros that propogates operators from APInt to IntItem in the beginning of IntegerSubset. Note that THESE MACROS WILL REMOVED after all passes will case-ranges compatible. Also note that these macros much smaller pain that something like this: if (V->getValue().ugt(AnotherV->getValue()) { ... } These changes made IntItem full featured integer object. It allows to make IntegerSubset class generic (move out all ConstantInt references inside and add unit-tests) in next commits. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157810 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 222 ++++++++++++++++++++-------------- 1 file changed, 133 insertions(+), 89 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 894b104..b0cfd85 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -25,88 +25,143 @@ namespace llvm { -template -class IntItemBase { -protected: - ImplTy Implementation; - typedef IntItemBase self; -public: - - IntItemBase() {} - - IntItemBase(const ImplTy &impl) : Implementation(impl) {} + // 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. - // implicit - IntItemBase(const APInt& src) : Implementation(src) {} - - operator const APInt&() const { - return (const APInt&)Implementation; + // 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 ConstantIntVal->getValue().func(RHS); \ } - bool operator<(const self& RHS) const { - return ((const APInt&)*this).ult(RHS); + +#define INT_ITEM_DEFINE_UNARY_OP(op) \ + IntItem operator op () const { \ + APInt res = op(ConstantIntVal->getValue()); \ + Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ + return IntItem(cast(NewVal)); \ } - bool operator==(const self& RHS) const { - return (const APInt&)*this == (const APInt&)RHS; + +#define INT_ITEM_DEFINE_BINARY_OP(op) \ + IntItem operator op (const APInt& RHS) const { \ + APInt res = ConstantIntVal->getValue() op RHS; \ + Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ + return IntItem(cast(NewVal)); \ } - bool operator!=(const self& RHS) const { - return (const APInt&)*this != (const APInt&)RHS; + +#define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \ + IntItem& operator op (const APInt& RHS) {\ + APInt res = ConstantIntVal->getValue();\ + res op RHS; \ + Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ + ConstantIntVal = cast(NewVal); \ + return *this; \ } - self& operator=(const ImplTy& RHS) { - Implementation = RHS; - return *this; - } - const APInt* operator->() const { - return &((const APInt&)Implementation); - } - const APInt& operator*() const { - return ((const APInt&)Implementation); - } - // FIXME: Hack. Will removed. - ImplTy& getImplementation() { - return Implementation; - } -}; - -class IntItemConstantIntImpl { - const ConstantInt *ConstantIntVal; -public: - IntItemConstantIntImpl() : ConstantIntVal(0) {} - IntItemConstantIntImpl(const ConstantInt *Val) : ConstantIntVal(Val) {} - IntItemConstantIntImpl(LLVMContext &Ctx, const APInt& src) { - ConstantIntVal = cast(ConstantInt::get(Ctx, src)); - } - explicit IntItemConstantIntImpl(const APInt& src) { - ConstantIntVal = - cast(ConstantInt::get(llvm::getGlobalContext(), src)); - } - operator const APInt&() const { - return ConstantIntVal->getValue(); + +#define INT_ITEM_DEFINE_PREINCDEC(op) \ + IntItem& operator op () { \ + APInt res = ConstantIntVal->getValue(); \ + op(res); \ + Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ + ConstantIntVal = cast(NewVal); \ + return *this; \ + } + +#define INT_ITEM_DEFINE_POSTINCDEC(op) \ + IntItem& operator op (int) { \ + APInt res = ConstantIntVal->getValue();\ + op(res); \ + Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ + OldConstantIntVal = ConstantIntVal; \ + ConstantIntVal = cast(NewVal); \ + return IntItem(OldConstantIntVal); \ + } + +#define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \ + RetTy operator op (IntTy RHS) const { \ + return (*this) op APInt(ConstantIntVal->getValue().getBitWidth(), RHS); \ } - operator const ConstantInt*() { - return ConstantIntVal; - } -}; -class IntItem : public IntItemBase { - typedef IntItemBase ParentTy; - IntItem(const IntItemConstantIntImpl& Impl) : ParentTy(Impl) {} +class IntItem { + ConstantInt *ConstantIntVal; + IntItem(const ConstantInt *V) : ConstantIntVal(const_cast(V)) {} public: IntItem() {} - // implicit - IntItem(const APInt& src) : ParentTy(src) {} + operator const APInt&() const { + return (const APInt&)ConstantIntVal->getValue(); + } + + // Propogate 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(|=); + + // Special case for <<= + IntItem& operator <<= (unsigned RHS) { + APInt res = ConstantIntVal->getValue(); + res <<= RHS; + Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); + ConstantIntVal = cast(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) { - IntItemConstantIntImpl Impl(V); - return IntItem(Impl); + return IntItem(V); } static IntItem fromType(Type* Ty, const APInt& V) { ConstantInt *C = cast(ConstantInt::get(Ty, V)); return fromConstantInt(C); } + static IntItem withImplLikeThis(const IntItem& LikeThis, const APInt& V) { + ConstantInt *C = cast(ConstantInt::get( + LikeThis.ConstantIntVal->getContext(), V)); + return fromConstantInt(C); + } ConstantInt *toConstantInt() { - return const_cast((const ConstantInt*)Implementation); + return ConstantIntVal; } }; @@ -145,24 +200,19 @@ struct IntRange { bool operator<(const IntRange &RHS) const { assert(!IsEmpty && "Left range is empty."); assert(!RHS.IsEmpty && "Right range is empty."); - if (Low->getBitWidth() == RHS.Low->getBitWidth()) { - if (Low->eq(RHS.Low)) { - if (High->ult(RHS.High)) - return true; - return false; - } - if (Low->ult(RHS.Low)) + if (Low == RHS.Low) { + if (High > RHS.High) return true; return false; - } else - return Low->getBitWidth() < RHS.Low->getBitWidth(); + } + if (Low < RHS.Low) + return true; + return false; } bool operator==(const IntRange &RHS) const { assert(!IsEmpty && "Left range is empty."); assert(!RHS.IsEmpty && "Right range is empty."); - if (Low->getBitWidth() != RHS.Low->getBitWidth()) - return false; return Low == RHS.Low && High == RHS.High; } @@ -171,18 +221,12 @@ struct IntRange { } static bool LessBySize(const IntRange &LHS, const IntRange &RHS) { - assert(LHS.Low->getBitWidth() == RHS.Low->getBitWidth() && - "This type of comparison requires equal bit width for LHS and RHS"); - APInt LSize = *LHS.High - *LHS.Low; - APInt RSize = *RHS.High - *RHS.Low; - return LSize.ult(RSize); + return (LHS.High - LHS.Low) < (RHS.High - RHS.Low); } - bool isInRange(const APInt &IntVal) const { + bool isInRange(const IntItem &IntVal) const { assert(!IsEmpty && "Range is empty."); - if (IntVal.getBitWidth() != Low->getBitWidth()) - return false; - return IntVal.uge(Low) && IntVal.ule(High); + return IntVal >= Low && IntVal <= High; } SubRes sub(const IntRange &RHS) const { @@ -200,14 +244,14 @@ struct IntRange { return Res; } - if (Low->ult(RHS.Low)) { + if (Low < RHS.Low) { Res.first.Low = Low; - APInt NewHigh = RHS.Low; + IntItem NewHigh = RHS.Low; --NewHigh; Res.first.High = NewHigh; } - if (High->ugt(RHS.High)) { - APInt NewLow = RHS.High; + if (High > RHS.High) { + IntItem NewLow = RHS.High; ++NewLow; Res.second.Low = NewLow; Res.second.High = High; @@ -332,7 +376,7 @@ public: /// 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(getItem(0).Low->getBitWidth(), 0); + APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0); for (unsigned i = 0, e = getNumItems(); i != e; ++i) { const APInt &Low = getItem(i).Low; const APInt &High = getItem(i).High; @@ -347,7 +391,7 @@ public: /// [<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(getItem(0).Low->getBitWidth(), 0); + APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0); for (unsigned i = 0, e = getNumItems(); i != e; ++i) { const APInt &Low = getItem(i).Low; const APInt &High = getItem(i).High; -- cgit v1.1 From b778179b86e930a07ce06a9018396ae434540360 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Fri, 1 Jun 2012 15:40:53 +0000 Subject: Remove noisy semicolons. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157814 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 52 +++++++++++++++++------------------ 1 file changed, 26 insertions(+), 26 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index b0cfd85..95110ea 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -105,30 +105,30 @@ public: // /,/=,>>,>>= 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_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_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_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) { @@ -139,11 +139,11 @@ public: 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. -- cgit v1.1 From 6bb5c0074dc4cede2ad8efd420ec91288f91b012 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Fri, 1 Jun 2012 16:17:57 +0000 Subject: PR1255: case ranges. IntegersSubset devided into IntegersSubsetGeneric and into IntegersSubset itself. The first has no references to ConstantInt and works with IntItem only. IntegersSubsetMapping also made generic. Here added second template parameter "IntegersSubsetTy" that allows to use on of two IntegersSubset types described below. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157815 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 217 +++++++++++++++++++++------------- 1 file changed, 133 insertions(+), 84 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 95110ea..ee797b9 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -19,6 +19,8 @@ #ifndef CONSTANTRANGESSET_H_ #define CONSTANTRANGESSET_H_ +#include + #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" #include "llvm/LLVMContext.h" @@ -109,8 +111,12 @@ public: 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(+) @@ -160,7 +166,7 @@ public: LikeThis.ConstantIntVal->getContext(), V)); return fromConstantInt(C); } - ConstantInt *toConstantInt() { + ConstantInt *toConstantInt() const { return ConstantIntVal; } }; @@ -261,30 +267,41 @@ struct IntRange { }; //===----------------------------------------------------------------------===// -/// 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. +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 FlatCollectionTy; + typedef std::pair RangeLinkTy; + typedef SmallVector RangeLinksTy; + typedef RangeLinksTy::iterator RangeLinksConstIt; - bool IsWide; +protected: - // implicit - IntegersSubset(Constant *V) : Array(V) { - ArrayType *ArrTy = cast(Array->getType()); - VectorType *VecTy = cast(ArrTy->getElementType()); - IntegerType *IntTy = cast(VecTy->getElementType()); - IsWide = IntTy->getBitWidth() > 64; - } + FlatCollectionTy FlatCollection; + RangeLinksTy RangeLinks; - operator Constant*() { return Array; } - operator const Constant*() const { return Array; } - Constant *operator->() { return Array; } - const Constant *operator->() const { return Array; } +public: + + template + 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); + RangeLink.first = &FlatCollection.back(); + if (i->Low != i->High) + FlatCollection.push_back(i->High); + RangeLink.second = &FlatCollection.back(); + RangeLinks.push_back(RangeLink); + } + } typedef IntRange Range; @@ -293,81 +310,33 @@ public: /// contained ranges. bool isSatisfies(const IntItem &CheckingVal) const { for (unsigned i = 0, e = getNumItems(); i < e; ++i) { - const Constant *CV = Array->getAggregateElement(i); - unsigned VecSize = cast(CV->getType())->getNumElements(); - switch (VecSize) { - case 1: - if (cast(CV->getAggregateElement(0U))->getValue() == - CheckingVal) - return true; - break; - case 2: { - const APInt &Lo = - cast(CV->getAggregateElement(0U))->getValue(); - const APInt &Hi = - cast(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(CV->getType())->getNumElements(); - switch (NumEls) { - case 1: - return Range(IntItem::fromConstantInt( - cast(CV->getAggregateElement(0U)))); - case 2: - return Range(IntItem::fromConstantInt( - cast(CV->getAggregateElement(0U))), - IntItem::fromConstantInt( - cast(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(CV->getType())->getNumElements(); - switch (NumEls) { - case 1: - return Range(IntItem::fromConstantInt( - cast(CV->getAggregateElement(0U))), - IntItem::fromConstantInt(cast( - cast(CV->getAggregateElement(0U))))); - case 2: - return Range(IntItem::fromConstantInt( - cast(CV->getAggregateElement(0U))), - IntItem::fromConstantInt( - cast(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(Array->getType())->getNumElements(); + return RangeLinks.size(); } - bool isWideNumberFormat() const { return IsWide; } - bool isSingleNumber(unsigned idx) const { - Constant *CV = Array->getAggregateElement(idx); - return cast(CV->getType())->getNumElements() == 1; + return RangeLinks.size() == 1 && + RangeLinks[0].first == RangeLinks[0].second; } /// Returns set the size, that equals number of all values + sizes of all @@ -411,6 +380,86 @@ public: } }; +//===----------------------------------------------------------------------===// +/// IntegersSubset - currenly is extension of IntegersSubsetGeneric +/// that also supports conversion to/from Constant* object. +class IntegersSubset : public IntegersSubsetGeneric { + Constant *Holder; + + static unsigned getNumItemsFromConstant(Constant *C) { + return cast(C->getType())->getNumElements(); + } + + static Range getItemFromConstant(Constant *C, unsigned idx) { + const Constant *CV = C->getAggregateElement(idx); + + unsigned NumEls = cast(CV->getType())->getNumElements(); + switch (NumEls) { + case 1: + return Range(IntItem::fromConstantInt( + cast(CV->getAggregateElement(0U))), + IntItem::fromConstantInt(cast( + cast(CV->getAggregateElement(0U))))); + case 2: + return Range(IntItem::fromConstantInt( + cast(CV->getAggregateElement(0U))), + IntItem::fromConstantInt( + cast(CV->getAggregateElement(1)))); + default: + assert(0 && "Only pairs and single numbers are allowed here."); + return Range(); + } + } + + std::vector rangesFromConstant(Constant *C) { + unsigned NumItems = getNumItemsFromConstant(C); + std::vector 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) : IntegersSubsetGeneric(rangesFromConstant(C)), + Holder(C) {} + + // implicit + template + IntegersSubset(const RangesCollectionTy& Src) : + IntegersSubsetGeneric(Src) { + + std::vector 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 r; + if (R.Low != R.High) { + 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()); + } else { + r.reserve(1); + r.push_back(R.Low.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_ */ -- cgit v1.1 From 4319a552ac98137d511341905711293d541f15e7 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Sat, 2 Jun 2012 07:26:00 +0000 Subject: PR1255: case ranges. IntegersSubsetGeneric, IntegersSubsetMapping: added IntTy template parameter, that allows use either APInt or IntItem. This change allows to write unittest for these classes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157880 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 52 ++++++++++++++++++----------------- 1 file changed, 27 insertions(+), 25 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index ee797b9..0295d2a 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -171,39 +171,40 @@ public: } }; -// TODO: it should be a class in next commit. +template struct IntRange { - IntItem Low; - IntItem High; + typedef IntRange self; + IntType Low; + IntType High; bool IsEmpty : 1; bool IsSingleNumber : 1; // TODO: // public: - typedef std::pair SubRes; + typedef std::pair SubRes; IntRange() : IsEmpty(true) {} - IntRange(const IntRange &RHS) : + IntRange(const self &RHS) : Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {} - IntRange(const IntItem &C) : + IntRange(const IntType &C) : Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {} - IntRange(const IntItem &L, const IntItem &H) : Low(L), High(H), + IntRange(const IntType &L, const IntType &H) : Low(L), High(H), IsEmpty(false), IsSingleNumber(false) {} bool isEmpty() const { return IsEmpty; } bool isSingleNumber() const { return IsSingleNumber; } - const IntItem& getLow() { + const IntType& getLow() { assert(!IsEmpty && "Range is empty."); return Low; } - const IntItem& getHigh() { + const IntType& getHigh() { 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) { @@ -216,26 +217,26 @@ struct IntRange { 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 @@ -245,19 +246,19 @@ struct IntRange { // 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; @@ -269,6 +270,7 @@ struct IntRange { //===----------------------------------------------------------------------===// /// IntegersSubsetGeneric - class that implements the subset of integers. It /// consists from ranges and single numbers. +template class IntegersSubsetGeneric { public: // Use Chris Lattner idea, that was initially described here: @@ -276,10 +278,10 @@ public: // 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 FlatCollectionTy; - typedef std::pair RangeLinkTy; + typedef std::list FlatCollectionTy; + typedef std::pair RangeLinkTy; typedef SmallVector RangeLinksTy; - typedef RangeLinksTy::iterator RangeLinksConstIt; + typedef typename RangeLinksTy::iterator RangeLinksConstIt; protected: @@ -303,12 +305,12 @@ public: } } - typedef IntRange Range; + typedef IntRange 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) { if (RangeLinks[i].first == RangeLinks[i].second) { if (*RangeLinks[i].first == CheckingVal) @@ -381,9 +383,9 @@ public: }; //===----------------------------------------------------------------------===// -/// IntegersSubset - currenly is extension of IntegersSubsetGeneric +/// IntegersSubset - currently is extension of IntegersSubsetGeneric /// that also supports conversion to/from Constant* object. -class IntegersSubset : public IntegersSubsetGeneric { +class IntegersSubset : public IntegersSubsetGeneric { Constant *Holder; static unsigned getNumItemsFromConstant(Constant *C) { -- cgit v1.1 From e2c53188ea8b01ca3d91b91c42faa5aa07ba4b70 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Sat, 2 Jun 2012 07:44:19 +0000 Subject: Small fix due to buildbot failures on mingw32. Fixed call of parent constructor for case when parent is template. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157881 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 0295d2a..ea3a8ae 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -386,6 +386,9 @@ public: /// IntegersSubset - currently is extension of IntegersSubsetGeneric /// that also supports conversion to/from Constant* object. class IntegersSubset : public IntegersSubsetGeneric { + + typedef IntegersSubsetGeneric ParentTy; + Constant *Holder; static unsigned getNumItemsFromConstant(Constant *C) { @@ -424,7 +427,7 @@ class IntegersSubset : public IntegersSubsetGeneric { public: - IntegersSubset(Constant *C) : IntegersSubsetGeneric(rangesFromConstant(C)), + IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), Holder(C) {} // implicit -- cgit v1.1 From 4524dd7518288f3d49bcaf31cff27cb82462c79c Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Sat, 2 Jun 2012 08:03:34 +0000 Subject: Additional change for 157881. Forget to fix another IntegerSubset constructor. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157882 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index ea3a8ae..b6ffe1b 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -432,9 +432,7 @@ public: // implicit template - IntegersSubset(const RangesCollectionTy& Src) : - IntegersSubsetGeneric(Src) { - + IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) { std::vector Elts; Elts.reserve(Src.size()); for (typename RangesCollectionTy::const_iterator i = Src.begin(), -- cgit v1.1 From 43eb31bfae470b33bab9a6764b98b5e8a0beeda5 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Sat, 2 Jun 2012 09:42:43 +0000 Subject: PR1255: case ranges. IntRange converted from struct to class. So main change everywhere is replacement of ".Low/High" with ".getLow/getHigh()" git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157884 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 56 +++++++++++++++++++---------------- 1 file changed, 31 insertions(+), 25 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index b6ffe1b..7f903cc 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -172,34 +172,33 @@ public: }; template -struct IntRange { - - typedef IntRange self; +class IntRange { +protected: IntType Low; IntType High; bool IsEmpty : 1; bool IsSingleNumber : 1; -// TODO: -// public: - + +public: + typedef IntRange self; typedef std::pair SubRes; IntRange() : IsEmpty(true) {} - IntRange(const self &RHS) : - Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {} + 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; } @@ -296,10 +295,10 @@ public: 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->Low != i->High) - FlatCollection.push_back(i->High); + if (i->getLow() != i->getHigh()) + FlatCollection.push_back(i->getHigh()); RangeLink.second = &FlatCollection.back(); RangeLinks.push_back(RangeLink); } @@ -336,10 +335,17 @@ public: 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. @@ -347,10 +353,10 @@ public: /// 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 &Low = getItem(i).getLow(); + const APInt &High = getItem(i).getHigh(); const APInt &S = High - Low; sz += S; } @@ -362,10 +368,10 @@ public: /// [<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 &Low = getItem(i).getLow(); + const APInt &High = getItem(i).getHigh(); const APInt& S = High - Low; APInt oldSz = sz; sz += S; @@ -439,15 +445,15 @@ public: e = Src.end(); i != e; ++i) { const Range &R = *i; std::vector 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); -- cgit v1.1 From d9b0b025612992a0b724eeca8bdf10b1d7a5c355 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Sat, 2 Jun 2012 10:20:22 +0000 Subject: Fix typos found by http://github.com/lyda/misspell-check git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157885 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 7f903cc..ac4eb97 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -102,7 +102,7 @@ public: 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. -- cgit v1.1 From 31219d2cec17dca632b6d047a15e86dc92b76e18 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Sat, 2 Jun 2012 13:47:12 +0000 Subject: Added unittests for IntegersSubset and IntegersSubsetMapping. - Fixed IntegersSubsetGeneric copy/assignment behaviour. - Fixed IntegersSubsetGeneric::getSize/getSingleValue methods. - Fixed IntegersSubsetGeneric::verify method. Also IntegersSubset.h and IntegersSubsetMapping.h headers was fixed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157887 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 45 +++++++++++++++++++++++++---------- 1 file changed, 33 insertions(+), 12 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index ac4eb97..998cc73 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -1,4 +1,4 @@ -//===-- llvm/ConstantRangesSet.h - The constant set of ranges ---*- C++ -*-===// +//===-- llvm/IntegersSubset.h - The subset of integers ----------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -9,10 +9,9 @@ // /// @file /// This file contains class that implements constant set of ranges: -/// [,...,]. Mainly, this set is used by SwitchInst and -/// represents case value that may contain multiple ranges for a single -/// successor. -/// +/// [,...,]. Initially, this class was created for +/// SwitchInst and was used for case value representation that may contain +/// multiple ranges for a single successor. // //===----------------------------------------------------------------------===// @@ -280,7 +279,9 @@ public: typedef std::list FlatCollectionTy; typedef std::pair RangeLinkTy; typedef SmallVector RangeLinksTy; - typedef typename RangeLinksTy::iterator RangeLinksConstIt; + typedef typename RangeLinksTy::const_iterator RangeLinksConstIt; + + typedef IntegersSubsetGeneric self; protected: @@ -304,6 +305,26 @@ public: } } + 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->first != i->second) + FlatCollection.push_back(*(i->second)); + RangeLink.second = &FlatCollection.back(); + RangeLinks.push_back(RangeLink); + } + return *this; + } + typedef IntRange Range; /// Checks is the given constant satisfies this case. Returns @@ -314,8 +335,8 @@ public: 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; @@ -357,7 +378,7 @@ public: for (unsigned i = 0, e = getNumItems(); i != e; ++i) { const APInt &Low = getItem(i).getLow(); const APInt &High = getItem(i).getHigh(); - const APInt &S = High - Low; + APInt S = High - Low + 1; sz += S; } return sz.getZExtValue(); @@ -372,12 +393,12 @@ public: for (unsigned i = 0, e = getNumItems(); i != e; ++i) { const APInt &Low = getItem(i).getLow(); const APInt &High = getItem(i).getHigh(); - const APInt& S = High - Low; + 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; -- cgit v1.1 From 13776d3fc80e3d5936ecba3a3dc0b20299cf0b6e Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi Date: Sun, 3 Jun 2012 15:42:12 +0000 Subject: IntRange: Restore the copy constuctor explicitly to appase buildbot. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157901 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 998cc73..add0c90 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -183,7 +183,9 @@ public: typedef std::pair 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) {} -- cgit v1.1 From 20cb4919cd01967b11b0b468fd43167b263ed028 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Tue, 5 Jun 2012 07:43:08 +0000 Subject: IntegersSubsetMapping: Changed type of Items collection: from std::vector to std::list. Also some small fixes made in IntegersSubset.h, IntegersSubsetMapping.h and IntegersSubsetTest.cpp. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157987 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index add0c90..2ceeea5 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -293,7 +293,7 @@ protected: public: template - 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) { @@ -459,9 +459,8 @@ public: IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), Holder(C) {} - // implicit template - IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) { + explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) { std::vector Elts; Elts.reserve(Src.size()); for (typename RangesCollectionTy::const_iterator i = Src.begin(), -- cgit v1.1 From 7351256208c9ff2cb7b5bdcf4427229abe2a50a8 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Fri, 22 Jun 2012 07:35:13 +0000 Subject: Performance optimizations: - SwitchInst: case values stored separately from Operands List. It allows to make faster access to individual case value numbers or ranges. - Optimized IntItem, added APInt value caching. - Optimized IntegersSubsetGeneric: added optimizations for cases when subset is single number or when subset consists from single numbers only. On my machine these optimizations gave about 4-6% of compile-time improvement. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158979 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 79 ++++++++++++++++++++++++++--------- 1 file changed, 60 insertions(+), 19 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 2ceeea5..69c94a3 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -40,26 +40,26 @@ namespace llvm { #define INT_ITEM_DEFINE_COMPARISON(op,func) \ bool operator op (const APInt& RHS) const { \ - return ConstantIntVal->getValue().func(RHS); \ + return getAPIntValue().func(RHS); \ } #define INT_ITEM_DEFINE_UNARY_OP(op) \ IntItem operator op () const { \ - APInt res = op(ConstantIntVal->getValue()); \ + APInt res = op(getAPIntValue()); \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ return IntItem(cast(NewVal)); \ } #define INT_ITEM_DEFINE_BINARY_OP(op) \ IntItem operator op (const APInt& RHS) const { \ - APInt res = ConstantIntVal->getValue() op RHS; \ + APInt res = getAPIntValue() op RHS; \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ return IntItem(cast(NewVal)); \ } #define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \ IntItem& operator op (const APInt& RHS) {\ - APInt res = ConstantIntVal->getValue();\ + APInt res = getAPIntValue();\ res op RHS; \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ ConstantIntVal = cast(NewVal); \ @@ -68,7 +68,7 @@ namespace llvm { #define INT_ITEM_DEFINE_PREINCDEC(op) \ IntItem& operator op () { \ - APInt res = ConstantIntVal->getValue(); \ + APInt res = getAPIntValue(); \ op(res); \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ ConstantIntVal = cast(NewVal); \ @@ -77,7 +77,7 @@ namespace llvm { #define INT_ITEM_DEFINE_POSTINCDEC(op) \ IntItem& operator op (int) { \ - APInt res = ConstantIntVal->getValue();\ + APInt res = getAPIntValue();\ op(res); \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ OldConstantIntVal = ConstantIntVal; \ @@ -87,18 +87,24 @@ namespace llvm { #define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \ RetTy operator op (IntTy RHS) const { \ - return (*this) op APInt(ConstantIntVal->getValue().getBitWidth(), RHS); \ + return (*this) op APInt(getAPIntValue().getBitWidth(), RHS); \ } class IntItem { ConstantInt *ConstantIntVal; - IntItem(const ConstantInt *V) : ConstantIntVal(const_cast(V)) {} + const APInt* APIntVal; + IntItem(const ConstantInt *V) : + ConstantIntVal(const_cast(V)), + APIntVal(&ConstantIntVal->getValue()){} + const APInt& getAPIntValue() const { + return *APIntVal; + } public: IntItem() {} operator const APInt&() const { - return (const APInt&)ConstantIntVal->getValue(); + return getAPIntValue(); } // Propagate APInt operators. @@ -137,7 +143,7 @@ public: // Special case for <<= IntItem& operator <<= (unsigned RHS) { - APInt res = ConstantIntVal->getValue(); + APInt res = getAPIntValue(); res <<= RHS; Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); ConstantIntVal = cast(NewVal); @@ -278,9 +284,9 @@ public: // 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 FlatCollectionTy; + typedef std::vector FlatCollectionTy; typedef std::pair RangeLinkTy; - typedef SmallVector RangeLinksTy; + typedef std::vector RangeLinksTy; typedef typename RangeLinksTy::const_iterator RangeLinksConstIt; typedef IntegersSubsetGeneric self; @@ -290,21 +296,33 @@ protected: FlatCollectionTy FlatCollection; RangeLinksTy RangeLinks; + bool IsSingleNumber; + bool IsSingleNumbersOnly; + public: template 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()) + 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) { @@ -314,6 +332,8 @@ public: 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; @@ -324,6 +344,8 @@ public: RangeLink.second = &FlatCollection.back(); RangeLinks.push_back(RangeLink); } + IsSingleNumber = RHS.IsSingleNumber; + IsSingleNumbersOnly = RHS.IsSingleNumbersOnly; return *this; } @@ -333,6 +355,13 @@ public: /// 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 (unsigned i = 0, e = getNumItems(); i < e; ++i) { if (RangeLinks[i].first == RangeLinks[i].second) { if (*RangeLinks[i].first == CheckingVal) @@ -360,8 +389,12 @@ public: /// Returns true if whole subset contains single element. bool isSingleNumber() const { - return RangeLinks.size() == 1 && - RangeLinks[0].first == RangeLinks[0].second; + 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 @@ -385,7 +418,7 @@ public: } 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] @@ -409,6 +442,14 @@ public: 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]; + } }; //===----------------------------------------------------------------------===// @@ -455,9 +496,9 @@ class IntegersSubset : public IntegersSubsetGeneric { } public: - - IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), - Holder(C) {} + + explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), + Holder(C) {} template explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) { -- cgit v1.1 From 37eeb058a30200101836d82098542d3d2fc4f3d5 Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Fri, 22 Jun 2012 10:35:06 +0000 Subject: Revert commit 158979 (dyatkovskiy) since it is causing several buildbots to fail. Original commit message: Performance optimizations: - SwitchInst: case values stored separately from Operands List. It allows to make faster access to individual case value numbers or ranges. - Optimized IntItem, added APInt value caching. - Optimized IntegersSubsetGeneric: added optimizations for cases when subset is single number or when subset consists from single numbers only. On my machine these optimizations gave about 4-6% of compile-time improvement. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158986 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 79 +++++++++-------------------------- 1 file changed, 19 insertions(+), 60 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 69c94a3..2ceeea5 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -40,26 +40,26 @@ namespace llvm { #define INT_ITEM_DEFINE_COMPARISON(op,func) \ bool operator op (const APInt& RHS) const { \ - return getAPIntValue().func(RHS); \ + return ConstantIntVal->getValue().func(RHS); \ } #define INT_ITEM_DEFINE_UNARY_OP(op) \ IntItem operator op () const { \ - APInt res = op(getAPIntValue()); \ + APInt res = op(ConstantIntVal->getValue()); \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ return IntItem(cast(NewVal)); \ } #define INT_ITEM_DEFINE_BINARY_OP(op) \ IntItem operator op (const APInt& RHS) const { \ - APInt res = getAPIntValue() op RHS; \ + APInt res = ConstantIntVal->getValue() op RHS; \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ return IntItem(cast(NewVal)); \ } #define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \ IntItem& operator op (const APInt& RHS) {\ - APInt res = getAPIntValue();\ + APInt res = ConstantIntVal->getValue();\ res op RHS; \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ ConstantIntVal = cast(NewVal); \ @@ -68,7 +68,7 @@ namespace llvm { #define INT_ITEM_DEFINE_PREINCDEC(op) \ IntItem& operator op () { \ - APInt res = getAPIntValue(); \ + APInt res = ConstantIntVal->getValue(); \ op(res); \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ ConstantIntVal = cast(NewVal); \ @@ -77,7 +77,7 @@ namespace llvm { #define INT_ITEM_DEFINE_POSTINCDEC(op) \ IntItem& operator op (int) { \ - APInt res = getAPIntValue();\ + APInt res = ConstantIntVal->getValue();\ op(res); \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ OldConstantIntVal = ConstantIntVal; \ @@ -87,24 +87,18 @@ namespace llvm { #define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \ RetTy operator op (IntTy RHS) const { \ - return (*this) op APInt(getAPIntValue().getBitWidth(), RHS); \ + return (*this) op APInt(ConstantIntVal->getValue().getBitWidth(), RHS); \ } class IntItem { ConstantInt *ConstantIntVal; - const APInt* APIntVal; - IntItem(const ConstantInt *V) : - ConstantIntVal(const_cast(V)), - APIntVal(&ConstantIntVal->getValue()){} - const APInt& getAPIntValue() const { - return *APIntVal; - } + IntItem(const ConstantInt *V) : ConstantIntVal(const_cast(V)) {} public: IntItem() {} operator const APInt&() const { - return getAPIntValue(); + return (const APInt&)ConstantIntVal->getValue(); } // Propagate APInt operators. @@ -143,7 +137,7 @@ public: // Special case for <<= IntItem& operator <<= (unsigned RHS) { - APInt res = getAPIntValue(); + APInt res = ConstantIntVal->getValue(); res <<= RHS; Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); ConstantIntVal = cast(NewVal); @@ -284,9 +278,9 @@ public: // 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 FlatCollectionTy; + typedef std::list FlatCollectionTy; typedef std::pair RangeLinkTy; - typedef std::vector RangeLinksTy; + typedef SmallVector RangeLinksTy; typedef typename RangeLinksTy::const_iterator RangeLinksConstIt; typedef IntegersSubsetGeneric self; @@ -296,33 +290,21 @@ protected: FlatCollectionTy FlatCollection; RangeLinksTy RangeLinks; - bool IsSingleNumber; - bool IsSingleNumbersOnly; - public: template 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()) { + 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) { @@ -332,8 +314,6 @@ public: 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; @@ -344,8 +324,6 @@ public: RangeLink.second = &FlatCollection.back(); RangeLinks.push_back(RangeLink); } - IsSingleNumber = RHS.IsSingleNumber; - IsSingleNumbersOnly = RHS.IsSingleNumbersOnly; return *this; } @@ -355,13 +333,6 @@ public: /// 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 (unsigned i = 0, e = getNumItems(); i < e; ++i) { if (RangeLinks[i].first == RangeLinks[i].second) { if (*RangeLinks[i].first == CheckingVal) @@ -389,12 +360,8 @@ public: /// 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; + return RangeLinks.size() == 1 && + RangeLinks[0].first == RangeLinks[0].second; } /// Does the same like getItem(idx).isSingleNumber(), but @@ -418,7 +385,7 @@ public: } 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] @@ -442,14 +409,6 @@ public: 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]; - } }; //===----------------------------------------------------------------------===// @@ -496,9 +455,9 @@ class IntegersSubset : public IntegersSubsetGeneric { } public: - - explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), - Holder(C) {} + + IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), + Holder(C) {} template explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) { -- cgit v1.1 From 43c3a4a7e76920c5646e473b72620acc7eb4ca5a Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Fri, 22 Jun 2012 14:53:30 +0000 Subject: Fixed r158979. Original message: Performance optimizations: - SwitchInst: case values stored separately from Operands List. It allows to make faster access to individual case value numbers or ranges. - Optimized IntItem, added APInt value caching. - Optimized IntegersSubsetGeneric: added optimizations for cases when subset is single number or when subset consists from single numbers only. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158997 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 79 ++++++++++++++++++++++++++--------- 1 file changed, 60 insertions(+), 19 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 2ceeea5..69c94a3 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -40,26 +40,26 @@ namespace llvm { #define INT_ITEM_DEFINE_COMPARISON(op,func) \ bool operator op (const APInt& RHS) const { \ - return ConstantIntVal->getValue().func(RHS); \ + return getAPIntValue().func(RHS); \ } #define INT_ITEM_DEFINE_UNARY_OP(op) \ IntItem operator op () const { \ - APInt res = op(ConstantIntVal->getValue()); \ + APInt res = op(getAPIntValue()); \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ return IntItem(cast(NewVal)); \ } #define INT_ITEM_DEFINE_BINARY_OP(op) \ IntItem operator op (const APInt& RHS) const { \ - APInt res = ConstantIntVal->getValue() op RHS; \ + APInt res = getAPIntValue() op RHS; \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ return IntItem(cast(NewVal)); \ } #define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \ IntItem& operator op (const APInt& RHS) {\ - APInt res = ConstantIntVal->getValue();\ + APInt res = getAPIntValue();\ res op RHS; \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ ConstantIntVal = cast(NewVal); \ @@ -68,7 +68,7 @@ namespace llvm { #define INT_ITEM_DEFINE_PREINCDEC(op) \ IntItem& operator op () { \ - APInt res = ConstantIntVal->getValue(); \ + APInt res = getAPIntValue(); \ op(res); \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ ConstantIntVal = cast(NewVal); \ @@ -77,7 +77,7 @@ namespace llvm { #define INT_ITEM_DEFINE_POSTINCDEC(op) \ IntItem& operator op (int) { \ - APInt res = ConstantIntVal->getValue();\ + APInt res = getAPIntValue();\ op(res); \ Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ OldConstantIntVal = ConstantIntVal; \ @@ -87,18 +87,24 @@ namespace llvm { #define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \ RetTy operator op (IntTy RHS) const { \ - return (*this) op APInt(ConstantIntVal->getValue().getBitWidth(), RHS); \ + return (*this) op APInt(getAPIntValue().getBitWidth(), RHS); \ } class IntItem { ConstantInt *ConstantIntVal; - IntItem(const ConstantInt *V) : ConstantIntVal(const_cast(V)) {} + const APInt* APIntVal; + IntItem(const ConstantInt *V) : + ConstantIntVal(const_cast(V)), + APIntVal(&ConstantIntVal->getValue()){} + const APInt& getAPIntValue() const { + return *APIntVal; + } public: IntItem() {} operator const APInt&() const { - return (const APInt&)ConstantIntVal->getValue(); + return getAPIntValue(); } // Propagate APInt operators. @@ -137,7 +143,7 @@ public: // Special case for <<= IntItem& operator <<= (unsigned RHS) { - APInt res = ConstantIntVal->getValue(); + APInt res = getAPIntValue(); res <<= RHS; Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); ConstantIntVal = cast(NewVal); @@ -278,9 +284,9 @@ public: // 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 FlatCollectionTy; + typedef std::vector FlatCollectionTy; typedef std::pair RangeLinkTy; - typedef SmallVector RangeLinksTy; + typedef std::vector RangeLinksTy; typedef typename RangeLinksTy::const_iterator RangeLinksConstIt; typedef IntegersSubsetGeneric self; @@ -290,21 +296,33 @@ protected: FlatCollectionTy FlatCollection; RangeLinksTy RangeLinks; + bool IsSingleNumber; + bool IsSingleNumbersOnly; + public: template 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()) + 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) { @@ -314,6 +332,8 @@ public: 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; @@ -324,6 +344,8 @@ public: RangeLink.second = &FlatCollection.back(); RangeLinks.push_back(RangeLink); } + IsSingleNumber = RHS.IsSingleNumber; + IsSingleNumbersOnly = RHS.IsSingleNumbersOnly; return *this; } @@ -333,6 +355,13 @@ public: /// 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 (unsigned i = 0, e = getNumItems(); i < e; ++i) { if (RangeLinks[i].first == RangeLinks[i].second) { if (*RangeLinks[i].first == CheckingVal) @@ -360,8 +389,12 @@ public: /// Returns true if whole subset contains single element. bool isSingleNumber() const { - return RangeLinks.size() == 1 && - RangeLinks[0].first == RangeLinks[0].second; + 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 @@ -385,7 +418,7 @@ public: } 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] @@ -409,6 +442,14 @@ public: 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]; + } }; //===----------------------------------------------------------------------===// @@ -455,9 +496,9 @@ class IntegersSubset : public IntegersSubsetGeneric { } public: - - IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), - Holder(C) {} + + explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), + Holder(C) {} template explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) { -- cgit v1.1 From 19dc8e374a8fd86878ee8f34ff07a8c4645b075f Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi Date: Sun, 24 Jun 2012 03:48:47 +0000 Subject: llvm/Support/IntegersSubset.h: Fix whitespace. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159100 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 184 +++++++++++++++++----------------- 1 file changed, 92 insertions(+), 92 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 69c94a3..376b256 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -25,7 +25,7 @@ #include "llvm/LLVMContext.h" 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 @@ -33,30 +33,30 @@ namespace llvm { // 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. + // 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. + + // 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(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(NewVal)); \ } - + #define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \ IntItem& operator op (const APInt& RHS) {\ APInt res = getAPIntValue();\ @@ -64,8 +64,8 @@ namespace llvm { Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ ConstantIntVal = cast(NewVal); \ return *this; \ - } - + } + #define INT_ITEM_DEFINE_PREINCDEC(op) \ IntItem& operator op () { \ APInt res = getAPIntValue(); \ @@ -73,7 +73,7 @@ namespace llvm { Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \ ConstantIntVal = cast(NewVal); \ return *this; \ - } + } #define INT_ITEM_DEFINE_POSTINCDEC(op) \ IntItem& operator op (int) { \ @@ -83,12 +83,12 @@ namespace llvm { OldConstantIntVal = ConstantIntVal; \ ConstantIntVal = cast(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; @@ -100,29 +100,29 @@ class IntItem { 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) @@ -133,32 +133,32 @@ public: 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(NewVal); - return *this; + 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); } @@ -185,22 +185,22 @@ protected: bool IsSingleNumber : 1; public: - typedef IntRange self; + typedef IntRange self; typedef std::pair 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; @@ -209,7 +209,7 @@ public: 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."); @@ -226,37 +226,37 @@ public: 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; + return Low == RHS.Low && High == RHS.High; } - + bool operator!=(const self &RHS) const { - return !operator ==(RHS); + 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; - } - + 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 std::make_pair(self(Low, High), self()); + return Res; } - + if (Low < RHS.Low) { Res.first.Low = Low; IntType NewHigh = RHS.Low; @@ -269,9 +269,9 @@ public: Res.second.Low = NewLow; Res.second.High = High; } - return Res; + return Res; } - }; + }; //===----------------------------------------------------------------------===// /// IntegersSubsetGeneric - class that implements the subset of integers. It @@ -288,27 +288,27 @@ public: typedef std::pair RangeLinkTy; typedef std::vector RangeLinksTy; typedef typename RangeLinksTy::const_iterator RangeLinksConstIt; - + typedef IntegersSubsetGeneric self; - + protected: - + FlatCollectionTy FlatCollection; RangeLinksTy RangeLinks; - + bool IsSingleNumber; bool IsSingleNumbersOnly; - + public: - + template 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()); + RangeLinks.reserve(Links.size()); IsSingleNumbersOnly = true; for (typename RangesCollectionTy::const_iterator i = Links.begin(), e = Links.end(); i != e; ++i) { @@ -324,11 +324,11 @@ public: } IsSingleNumber = IsSingleNumbersOnly && RangeLinks.size() == 1; } - + IntegersSubsetGeneric(const self& RHS) { *this = RHS; } - + self& operator=(const self& RHS) { FlatCollection.clear(); RangeLinks.clear(); @@ -348,9 +348,9 @@ public: IsSingleNumbersOnly = RHS.IsSingleNumbersOnly; return *this; } - + typedef IntRange 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. @@ -361,18 +361,18 @@ public: 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) + *RangeLinks[i].second >= CheckingVal) return true; } - return false; + return false; } - + /// Returns set's item with given index. Range getItem(unsigned idx) const { const RangeLinkTy &Link = RangeLinks[idx]; @@ -380,29 +380,29 @@ public: return Range(*Link.first, *Link.second); else return Range(*Link.first); - } - + } + /// Return number of items (ranges) stored in set. unsigned 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. + /// 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. @@ -416,18 +416,18 @@ public: APInt S = High - Low + 1; sz += S; } - return sz.getZExtValue(); + 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] + /// [<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(); + const APInt &High = getItem(i).getHigh(); APInt S = High - Low + 1; APInt oldSz = sz; sz += S; @@ -440,9 +440,9 @@ public: } } assert(0 && "Index exceeds high border."); - return sz; + return sz; } - + /// Does the same as getSingleValue, but works only if subset contains /// single numbers only. const IntTy& getSingleNumber(unsigned idx) const { @@ -450,24 +450,24 @@ public: "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 { - + typedef IntegersSubsetGeneric ParentTy; - + Constant *Holder; - + static unsigned getNumItemsFromConstant(Constant *C) { return cast(C->getType())->getNumElements(); } - + static Range getItemFromConstant(Constant *C, unsigned idx) { const Constant *CV = C->getAggregateElement(idx); - + unsigned NumEls = cast(CV->getType())->getNumElements(); switch (NumEls) { case 1: @@ -483,9 +483,9 @@ class IntegersSubset : public IntegersSubsetGeneric { default: assert(0 && "Only pairs and single numbers are allowed here."); return Range(); - } - } - + } + } + std::vector rangesFromConstant(Constant *C) { unsigned NumItems = getNumItemsFromConstant(C); std::vector r; @@ -494,12 +494,12 @@ class IntegersSubset : public IntegersSubsetGeneric { r.push_back(getItemFromConstant(C, i)); return r; } - + public: explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)), Holder(C) {} - + template explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) { std::vector Elts; @@ -519,18 +519,18 @@ public: r.push_back(R.getLow().toConstantInt()); } Constant *CV = ConstantVector::get(r); - Elts.push_back(CV); + Elts.push_back(CV); } ArrayType *ArrTy = ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size()); - Holder = ConstantArray::get(ArrTy, Elts); + 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; } -}; +}; } -- cgit v1.1 From 653bbb494bd4c9737c6efa76b6176f6ede89a391 Mon Sep 17 00:00:00 2001 From: NAKAMURA Takumi Date: Sun, 24 Jun 2012 03:48:53 +0000 Subject: llvm/Support/IntegersSubset.h: Add a copy constructor on IntegersSubset to appease msvc. msvc mis-infers ParentTy(RHS) to (const RangesCollectionTy &). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159101 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 376b256..bb9e769 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -500,6 +500,10 @@ 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 explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) { std::vector Elts; -- cgit v1.1 From b2833d9dcba88c6f0520cad760619200adc0442c Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Mon, 2 Jul 2012 13:02:18 +0000 Subject: IntRange: - Changed isSingleNumber method behaviour. Now this flag is calculated on demand. IntegersSubsetMapping - Optimized diff operation. - Replaced type of Items field from std::list with std::map. - Added new methods: bool isOverlapped(self &RHS) void add(self& RHS, SuccessorClass *S) void detachCase(self& NewMapping, SuccessorClass *Succ) void removeCase(SuccessorClass *Succ) SuccessorClass *findSuccessor(const IntTy& Val) const IntTy* getCaseSingleNumber(SuccessorClass *Succ) IntegersSubsetTest - DiffTest: Added checks for successors. SimplifyCFG Updated SwitchInst usage (now it is case-ragnes compatible) for - SimplifyEqualityComparisonWithOnlyPredecessor - FoldValueComparisonIntoPredecessors git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159527 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 36 +++++++++++++++++++++++++++-------- 1 file changed, 28 insertions(+), 8 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index bb9e769..06df793 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -182,7 +182,12 @@ protected: IntType Low; IntType High; bool IsEmpty : 1; - bool IsSingleNumber : 1; + enum Type { + SINGLE_NUMBER, + RANGE, + UNKNOWN + }; + Type RangeType; public: typedef IntRange self; @@ -191,15 +196,30 @@ public: IntRange() : IsEmpty(true) {} IntRange(const self &RHS) : Low(RHS.Low), High(RHS.High), - IsEmpty(RHS.IsEmpty), IsSingleNumber(RHS.IsSingleNumber) {} + IsEmpty(RHS.IsEmpty), RangeType(RHS.RangeType) {} IntRange(const IntType &C) : - Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {} + Low(C), High(C), IsEmpty(false), RangeType(SINGLE_NUMBER) {} IntRange(const IntType &L, const IntType &H) : Low(L), High(H), - IsEmpty(false), IsSingleNumber(Low == High) {} + IsEmpty(false), RangeType(UNKNOWN) {} bool isEmpty() const { return IsEmpty; } - bool isSingleNumber() const { return IsSingleNumber; } + bool isSingleNumber() const { + switch (RangeType) { + case SINGLE_NUMBER: + return true; + case RANGE: + return false; + case UNKNOWN: + default: + if (Low == High) { + const_cast(RangeType) = SINGLE_NUMBER; + return true; + } + const_cast(RangeType) = RANGE; + return false; + } + } const IntType& getLow() const { assert(!IsEmpty && "Range is empty."); @@ -213,13 +233,13 @@ public: bool operator<(const self &RHS) const { assert(!IsEmpty && "Left range is empty."); assert(!RHS.IsEmpty && "Right range is empty."); + if (Low < RHS.Low) + return true; if (Low == RHS.Low) { if (High > RHS.High) return true; return false; } - if (Low < RHS.Low) - return true; return false; } @@ -512,7 +532,7 @@ public: e = Src.end(); i != e; ++i) { const Range &R = *i; std::vector r; - if (R.isSingleNumber()) { + if (!R.isSingleNumber()) { r.reserve(2); // FIXME: Since currently we have ConstantInt based numbers // use hack-conversion of IntItem to ConstantInt -- cgit v1.1 From dbd0f69e546bbf29e4bebb5618acb321365dd4f5 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Mon, 2 Jul 2012 14:10:46 +0000 Subject: IntRange, fixed warning in isSingleNumber method git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159532 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 06df793..e52a2f3 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -210,8 +210,7 @@ public: return true; case RANGE: return false; - case UNKNOWN: - default: + default: // UNKNOWN if (Low == High) { const_cast(RangeType) = SINGLE_NUMBER; return true; -- cgit v1.1 From 7c3a65c7edceb3a013cf49d376c3bc016eb871bf Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Mon, 2 Jul 2012 17:42:46 +0000 Subject: Fixed switch in IntRange::isSingleNumber method. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159540 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index e52a2f3..35e2dad 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -210,7 +210,7 @@ public: return true; case RANGE: return false; - default: // UNKNOWN + case UNKNOWN: if (Low == High) { const_cast(RangeType) = SINGLE_NUMBER; return true; @@ -218,6 +218,8 @@ public: const_cast(RangeType) = RANGE; return false; } + assert(!"Unknown state?!"); + return false; } const IntType& getLow() const { -- cgit v1.1 From ebcaa3cd97bf48c4c56dcf9aab5e9a7df85969ed Mon Sep 17 00:00:00 2001 From: David Blaikie Date: Mon, 2 Jul 2012 21:00:00 +0000 Subject: Fix -Wstring-conversion warning. Patch by Matt Beaumont-Gay. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159583 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 35e2dad..4d76fab 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -218,8 +218,7 @@ public: const_cast(RangeType) = RANGE; return false; } - assert(!"Unknown state?!"); - return false; + llvm_unreachable("Unknown state?!"); } const IntType& getLow() const { -- cgit v1.1 From c723eb1aef817d47feec620933ee1ec6005cdd14 Mon Sep 17 00:00:00 2001 From: Eric Christopher Date: Mon, 2 Jul 2012 23:22:21 +0000 Subject: Revert "IntRange:" as it appears to be breaking self hosting. This reverts commit b2833d9dcba88c6f0520cad760619200adc0442c. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159618 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubset.h | 36 ++++++++--------------------------- 1 file changed, 8 insertions(+), 28 deletions(-) (limited to 'include/llvm/Support/IntegersSubset.h') diff --git a/include/llvm/Support/IntegersSubset.h b/include/llvm/Support/IntegersSubset.h index 4d76fab..bb9e769 100644 --- a/include/llvm/Support/IntegersSubset.h +++ b/include/llvm/Support/IntegersSubset.h @@ -182,12 +182,7 @@ protected: IntType Low; IntType High; bool IsEmpty : 1; - enum Type { - SINGLE_NUMBER, - RANGE, - UNKNOWN - }; - Type RangeType; + bool IsSingleNumber : 1; public: typedef IntRange self; @@ -196,30 +191,15 @@ public: IntRange() : IsEmpty(true) {} IntRange(const self &RHS) : Low(RHS.Low), High(RHS.High), - IsEmpty(RHS.IsEmpty), RangeType(RHS.RangeType) {} + IsEmpty(RHS.IsEmpty), IsSingleNumber(RHS.IsSingleNumber) {} IntRange(const IntType &C) : - Low(C), High(C), IsEmpty(false), RangeType(SINGLE_NUMBER) {} + Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {} IntRange(const IntType &L, const IntType &H) : Low(L), High(H), - IsEmpty(false), RangeType(UNKNOWN) {} + IsEmpty(false), IsSingleNumber(Low == High) {} bool isEmpty() const { return IsEmpty; } - bool isSingleNumber() const { - switch (RangeType) { - case SINGLE_NUMBER: - return true; - case RANGE: - return false; - case UNKNOWN: - if (Low == High) { - const_cast(RangeType) = SINGLE_NUMBER; - return true; - } - const_cast(RangeType) = RANGE; - return false; - } - llvm_unreachable("Unknown state?!"); - } + bool isSingleNumber() const { return IsSingleNumber; } const IntType& getLow() const { assert(!IsEmpty && "Range is empty."); @@ -233,13 +213,13 @@ public: bool operator<(const self &RHS) const { assert(!IsEmpty && "Left range is empty."); assert(!RHS.IsEmpty && "Right range is empty."); - if (Low < RHS.Low) - return true; if (Low == RHS.Low) { if (High > RHS.High) return true; return false; } + if (Low < RHS.Low) + return true; return false; } @@ -532,7 +512,7 @@ public: e = Src.end(); i != e; ++i) { const Range &R = *i; std::vector r; - if (!R.isSingleNumber()) { + if (R.isSingleNumber()) { r.reserve(2); // FIXME: Since currently we have ConstantInt based numbers // use hack-conversion of IntItem to ConstantInt -- cgit v1.1