Home | History | Annotate | Download | only in Support 
      1 //===-- llvm/IntegersSubset.h - The subset of integers ----------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 /// @file
     11 /// This file contains class that implements constant set of ranges:
     12 /// [<Low0,High0>,...,<LowN,HighN>]. Initially, this class was created for
     13 /// SwitchInst and was used for case value representation that may contain
     14 /// multiple ranges for a single successor.
     15 //
     16 //===----------------------------------------------------------------------===//
     17 
     18 #ifndef CONSTANTRANGESSET_H_
     19 #define CONSTANTRANGESSET_H_
     20 
     21 #include <list>
     22 
     23 #include "llvm/Constants.h"
     24 #include "llvm/DerivedTypes.h"
     25 #include "llvm/LLVMContext.h"
     26 
     27 namespace llvm {
     28 
     29   // The IntItem is a wrapper for APInt.
     30   // 1. It determines sign of integer, it allows to use
     31   //    comparison operators >,<,>=,<=, and as result we got shorter and cleaner
     32   //    constructions.
     33   // 2. It helps to implement PR1255 (case ranges) as a series of small patches.
     34   // 3. Currently we can interpret IntItem both as ConstantInt and as APInt.
     35   //    It allows to provide SwitchInst methods that works with ConstantInt for
     36   //    non-updated passes. And it allows to use APInt interface for new methods.
     37   // 4. IntItem can be easily replaced with APInt.
     38 
     39   // The set of macros that allows to propagate APInt operators to the IntItem.
     40 
     41 #define INT_ITEM_DEFINE_COMPARISON(op,func) \
     42   bool operator op (const APInt& RHS) const { \
     43     return getAPIntValue().func(RHS); \
     44   }
     45 
     46 #define INT_ITEM_DEFINE_UNARY_OP(op) \
     47   IntItem operator op () const { \
     48     APInt res = op(getAPIntValue()); \
     49     Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
     50     return IntItem(cast<ConstantInt>(NewVal)); \
     51   }
     52 
     53 #define INT_ITEM_DEFINE_BINARY_OP(op) \
     54   IntItem operator op (const APInt& RHS) const { \
     55     APInt res = getAPIntValue() op RHS; \
     56     Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
     57     return IntItem(cast<ConstantInt>(NewVal)); \
     58   }
     59 
     60 #define INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(op) \
     61   IntItem& operator op (const APInt& RHS) {\
     62     APInt res = getAPIntValue();\
     63     res op RHS; \
     64     Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
     65     ConstantIntVal = cast<ConstantInt>(NewVal); \
     66     return *this; \
     67   }
     68 
     69 #define INT_ITEM_DEFINE_PREINCDEC(op) \
     70     IntItem& operator op () { \
     71       APInt res = getAPIntValue(); \
     72       op(res); \
     73       Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
     74       ConstantIntVal = cast<ConstantInt>(NewVal); \
     75       return *this; \
     76     }
     77 
     78 #define INT_ITEM_DEFINE_POSTINCDEC(op) \
     79     IntItem& operator op (int) { \
     80       APInt res = getAPIntValue();\
     81       op(res); \
     82       Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res); \
     83       OldConstantIntVal = ConstantIntVal; \
     84       ConstantIntVal = cast<ConstantInt>(NewVal); \
     85       return IntItem(OldConstantIntVal); \
     86     }
     87 
     88 #define INT_ITEM_DEFINE_OP_STANDARD_INT(RetTy, op, IntTy) \
     89   RetTy operator op (IntTy RHS) const { \
     90     return (*this) op APInt(getAPIntValue().getBitWidth(), RHS); \
     91   }
     92 
     93 class IntItem {
     94   ConstantInt *ConstantIntVal;
     95   const APInt* APIntVal;
     96   IntItem(const ConstantInt *V) :
     97     ConstantIntVal(const_cast<ConstantInt*>(V)),
     98     APIntVal(&ConstantIntVal->getValue()){}
     99   const APInt& getAPIntValue() const {
    100     return *APIntVal;
    101   }
    102 public:
    103 
    104   IntItem() {}
    105 
    106   operator const APInt&() const {
    107     return getAPIntValue();
    108   }
    109 
    110   // Propagate APInt operators.
    111   // Note, that
    112   // /,/=,>>,>>= are not implemented in APInt.
    113   // <<= is implemented for unsigned RHS, but not implemented for APInt RHS.
    114 
    115   INT_ITEM_DEFINE_COMPARISON(<, ult)
    116   INT_ITEM_DEFINE_COMPARISON(>, ugt)
    117   INT_ITEM_DEFINE_COMPARISON(<=, ule)
    118   INT_ITEM_DEFINE_COMPARISON(>=, uge)
    119 
    120   INT_ITEM_DEFINE_COMPARISON(==, eq)
    121   INT_ITEM_DEFINE_OP_STANDARD_INT(bool,==,uint64_t)
    122 
    123   INT_ITEM_DEFINE_COMPARISON(!=, ne)
    124   INT_ITEM_DEFINE_OP_STANDARD_INT(bool,!=,uint64_t)
    125 
    126   INT_ITEM_DEFINE_BINARY_OP(*)
    127   INT_ITEM_DEFINE_BINARY_OP(+)
    128   INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,+,uint64_t)
    129   INT_ITEM_DEFINE_BINARY_OP(-)
    130   INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,-,uint64_t)
    131   INT_ITEM_DEFINE_BINARY_OP(<<)
    132   INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,<<,unsigned)
    133   INT_ITEM_DEFINE_BINARY_OP(&)
    134   INT_ITEM_DEFINE_BINARY_OP(^)
    135   INT_ITEM_DEFINE_BINARY_OP(|)
    136 
    137   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(*=)
    138   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(+=)
    139   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(-=)
    140   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(&=)
    141   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(^=)
    142   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(|=)
    143 
    144   // Special case for <<=
    145   IntItem& operator <<= (unsigned RHS) {
    146     APInt res = getAPIntValue();
    147     res <<= RHS;
    148     Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res);
    149     ConstantIntVal = cast<ConstantInt>(NewVal);
    150     return *this;
    151   }
    152 
    153   INT_ITEM_DEFINE_UNARY_OP(-)
    154   INT_ITEM_DEFINE_UNARY_OP(~)
    155 
    156   INT_ITEM_DEFINE_PREINCDEC(++)
    157   INT_ITEM_DEFINE_PREINCDEC(--)
    158 
    159   // The set of workarounds, since currently we use ConstantInt implemented
    160   // integer.
    161 
    162   static IntItem fromConstantInt(const ConstantInt *V) {
    163     return IntItem(V);
    164   }
    165   static IntItem fromType(Type* Ty, const APInt& V) {
    166     ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
    167     return fromConstantInt(C);
    168   }
    169   static IntItem withImplLikeThis(const IntItem& LikeThis, const APInt& V) {
    170     ConstantInt *C = cast<ConstantInt>(ConstantInt::get(
    171         LikeThis.ConstantIntVal->getContext(), V));
    172     return fromConstantInt(C);
    173   }
    174   ConstantInt *toConstantInt() const {
    175     return ConstantIntVal;
    176   }
    177 };
    178 
    179 template<class IntType>
    180 class IntRange {
    181 protected:
    182     IntType Low;
    183     IntType High;
    184     bool IsEmpty : 1;
    185     bool IsSingleNumber : 1;
    186 
    187 public:
    188     typedef IntRange<IntType> self;
    189     typedef std::pair<self, self> SubRes;
    190 
    191     IntRange() : IsEmpty(true) {}
    192     IntRange(const self &RHS) :
    193       Low(RHS.Low), High(RHS.High),
    194       IsEmpty(RHS.IsEmpty), IsSingleNumber(RHS.IsSingleNumber) {}
    195     IntRange(const IntType &C) :
    196       Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
    197 
    198     IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
    199       IsEmpty(false), IsSingleNumber(Low == High) {}
    200 
    201     bool isEmpty() const { return IsEmpty; }
    202     bool isSingleNumber() const { return IsSingleNumber; }
    203 
    204     const IntType& getLow() const {
    205       assert(!IsEmpty && "Range is empty.");
    206       return Low;
    207     }
    208     const IntType& getHigh() const {
    209       assert(!IsEmpty && "Range is empty.");
    210       return High;
    211     }
    212 
    213     bool operator<(const self &RHS) const {
    214       assert(!IsEmpty && "Left range is empty.");
    215       assert(!RHS.IsEmpty && "Right range is empty.");
    216       if (Low == RHS.Low) {
    217         if (High > RHS.High)
    218           return true;
    219         return false;
    220       }
    221       if (Low < RHS.Low)
    222         return true;
    223       return false;
    224     }
    225 
    226     bool operator==(const self &RHS) const {
    227       assert(!IsEmpty && "Left range is empty.");
    228       assert(!RHS.IsEmpty && "Right range is empty.");
    229       return Low == RHS.Low && High == RHS.High;
    230     }
    231 
    232     bool operator!=(const self &RHS) const {
    233       return !operator ==(RHS);
    234     }
    235 
    236     static bool LessBySize(const self &LHS, const self &RHS) {
    237       return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
    238     }
    239 
    240     bool isInRange(const IntType &IntVal) const {
    241       assert(!IsEmpty && "Range is empty.");
    242       return IntVal >= Low && IntVal <= High;
    243     }
    244 
    245     SubRes sub(const self &RHS) const {
    246       SubRes Res;
    247 
    248       // RHS is either more global and includes this range or
    249       // if it doesn't intersected with this range.
    250       if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
    251 
    252         // If RHS more global (it is enough to check
    253         // only one border in this case.
    254         if (RHS.isInRange(Low))
    255           return std::make_pair(self(Low, High), self());
    256 
    257         return Res;
    258       }
    259 
    260       if (Low < RHS.Low) {
    261         Res.first.Low = Low;
    262         IntType NewHigh = RHS.Low;
    263         --NewHigh;
    264         Res.first.High = NewHigh;
    265       }
    266       if (High > RHS.High) {
    267         IntType NewLow = RHS.High;
    268         ++NewLow;
    269         Res.second.Low = NewLow;
    270         Res.second.High = High;
    271       }
    272       return Res;
    273     }
    274   };
    275 
    276 //===----------------------------------------------------------------------===//
    277 /// IntegersSubsetGeneric - class that implements the subset of integers. It
    278 /// consists from ranges and single numbers.
    279 template <class IntTy>
    280 class IntegersSubsetGeneric {
    281 public:
    282   // Use Chris Lattner idea, that was initially described here:
    283   // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120213/136954.html
    284   // In short, for more compact memory consumption we can store flat
    285   // numbers collection, and define range as pair of indices.
    286   // In that case we can safe some memory on 32 bit machines.
    287   typedef std::vector<IntTy> FlatCollectionTy;
    288   typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
    289   typedef std::vector<RangeLinkTy> RangeLinksTy;
    290   typedef typename RangeLinksTy::const_iterator RangeLinksConstIt;
    291 
    292   typedef IntegersSubsetGeneric<IntTy> self;
    293 
    294 protected:
    295 
    296   FlatCollectionTy FlatCollection;
    297   RangeLinksTy RangeLinks;
    298 
    299   bool IsSingleNumber;
    300   bool IsSingleNumbersOnly;
    301 
    302 public:
    303 
    304   template<class RangesCollectionTy>
    305   explicit IntegersSubsetGeneric(const RangesCollectionTy& Links) {
    306     assert(Links.size() && "Empty ranges are not allowed.");
    307 
    308     // In case of big set of single numbers consumes additional RAM space,
    309     // but allows to avoid additional reallocation.
    310     FlatCollection.reserve(Links.size() * 2);
    311     RangeLinks.reserve(Links.size());
    312     IsSingleNumbersOnly = true;
    313     for (typename RangesCollectionTy::const_iterator i = Links.begin(),
    314          e = Links.end(); i != e; ++i) {
    315       RangeLinkTy RangeLink;
    316       FlatCollection.push_back(i->getLow());
    317       RangeLink.first = &FlatCollection.back();
    318       if (i->getLow() != i->getHigh()) {
    319         FlatCollection.push_back(i->getHigh());
    320         IsSingleNumbersOnly = false;
    321       }
    322       RangeLink.second = &FlatCollection.back();
    323       RangeLinks.push_back(RangeLink);
    324     }
    325     IsSingleNumber = IsSingleNumbersOnly && RangeLinks.size() == 1;
    326   }
    327 
    328   IntegersSubsetGeneric(const self& RHS) {
    329     *this = RHS;
    330   }
    331 
    332   self& operator=(const self& RHS) {
    333     FlatCollection.clear();
    334     RangeLinks.clear();
    335     FlatCollection.reserve(RHS.RangeLinks.size() * 2);
    336     RangeLinks.reserve(RHS.RangeLinks.size());
    337     for (RangeLinksConstIt i = RHS.RangeLinks.begin(), e = RHS.RangeLinks.end();
    338          i != e; ++i) {
    339       RangeLinkTy RangeLink;
    340       FlatCollection.push_back(*(i->first));
    341       RangeLink.first = &FlatCollection.back();
    342       if (i->first != i->second)
    343         FlatCollection.push_back(*(i->second));
    344       RangeLink.second = &FlatCollection.back();
    345       RangeLinks.push_back(RangeLink);
    346     }
    347     IsSingleNumber = RHS.IsSingleNumber;
    348     IsSingleNumbersOnly = RHS.IsSingleNumbersOnly;
    349     return *this;
    350   }
    351 
    352   typedef IntRange<IntTy> Range;
    353 
    354   /// Checks is the given constant satisfies this case. Returns
    355   /// true if it equals to one of contained values or belongs to the one of
    356   /// contained ranges.
    357   bool isSatisfies(const IntTy &CheckingVal) const {
    358     if (IsSingleNumber)
    359       return FlatCollection.front() == CheckingVal;
    360     if (IsSingleNumbersOnly)
    361       return std::find(FlatCollection.begin(),
    362                        FlatCollection.end(),
    363                        CheckingVal) != FlatCollection.end();
    364 
    365     for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
    366       if (RangeLinks[i].first == RangeLinks[i].second) {
    367         if (*RangeLinks[i].first == CheckingVal)
    368           return true;
    369       } else if (*RangeLinks[i].first <= CheckingVal &&
    370                  *RangeLinks[i].second >= CheckingVal)
    371         return true;
    372     }
    373     return false;
    374   }
    375 
    376   /// Returns set's item with given index.
    377   Range getItem(unsigned idx) const {
    378     const RangeLinkTy &Link = RangeLinks[idx];
    379     if (Link.first != Link.second)
    380       return Range(*Link.first, *Link.second);
    381     else
    382       return Range(*Link.first);
    383   }
    384 
    385   /// Return number of items (ranges) stored in set.
    386   unsigned getNumItems() const {
    387     return RangeLinks.size();
    388   }
    389 
    390   /// Returns true if whole subset contains single element.
    391   bool isSingleNumber() const {
    392     return IsSingleNumber;
    393   }
    394 
    395   /// Returns true if whole subset contains only single numbers, no ranges.
    396   bool isSingleNumbersOnly() const {
    397     return IsSingleNumbersOnly;
    398   }
    399 
    400   /// Does the same like getItem(idx).isSingleNumber(), but
    401   /// works faster, since we avoid creation of temporary range object.
    402   bool isSingleNumber(unsigned idx) const {
    403     return RangeLinks[idx].first == RangeLinks[idx].second;
    404   }
    405 
    406   /// Returns set the size, that equals number of all values + sizes of all
    407   /// ranges.
    408   /// Ranges set is considered as flat numbers collection.
    409   /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
    410   ///       for range [<0>, <1>, <5>] the size will 3
    411   unsigned getSize() const {
    412     APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
    413     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
    414       const APInt &Low = getItem(i).getLow();
    415       const APInt &High = getItem(i).getHigh();
    416       APInt S = High - Low + 1;
    417       sz += S;
    418     }
    419     return sz.getZExtValue();
    420   }
    421 
    422   /// Allows to access single value even if it belongs to some range.
    423   /// Ranges set is considered as flat numbers collection.
    424   /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
    425   /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
    426   APInt getSingleValue(unsigned idx) const {
    427     APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
    428     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
    429       const APInt &Low = getItem(i).getLow();
    430       const APInt &High = getItem(i).getHigh();
    431       APInt S = High - Low + 1;
    432       APInt oldSz = sz;
    433       sz += S;
    434       if (sz.ugt(idx)) {
    435         APInt Res = Low;
    436         APInt Offset(oldSz.getBitWidth(), idx);
    437         Offset -= oldSz;
    438         Res += Offset;
    439         return Res;
    440       }
    441     }
    442     assert(0 && "Index exceeds high border.");
    443     return sz;
    444   }
    445 
    446   /// Does the same as getSingleValue, but works only if subset contains
    447   /// single numbers only.
    448   const IntTy& getSingleNumber(unsigned idx) const {
    449     assert(IsSingleNumbersOnly && "This method works properly if subset "
    450                                   "contains single numbers only.");
    451     return FlatCollection[idx];
    452   }
    453 };
    454 
    455 //===----------------------------------------------------------------------===//
    456 /// IntegersSubset - currently is extension of IntegersSubsetGeneric
    457 /// that also supports conversion to/from Constant* object.
    458 class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
    459 
    460   typedef IntegersSubsetGeneric<IntItem> ParentTy;
    461 
    462   Constant *Holder;
    463 
    464   static unsigned getNumItemsFromConstant(Constant *C) {
    465     return cast<ArrayType>(C->getType())->getNumElements();
    466   }
    467 
    468   static Range getItemFromConstant(Constant *C, unsigned idx) {
    469     const Constant *CV = C->getAggregateElement(idx);
    470 
    471     unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
    472     switch (NumEls) {
    473     case 1:
    474       return Range(IntItem::fromConstantInt(
    475                      cast<ConstantInt>(CV->getAggregateElement(0U))),
    476                    IntItem::fromConstantInt(cast<ConstantInt>(
    477                      cast<ConstantInt>(CV->getAggregateElement(0U)))));
    478     case 2:
    479       return Range(IntItem::fromConstantInt(
    480                      cast<ConstantInt>(CV->getAggregateElement(0U))),
    481                    IntItem::fromConstantInt(
    482                    cast<ConstantInt>(CV->getAggregateElement(1))));
    483     default:
    484       assert(0 && "Only pairs and single numbers are allowed here.");
    485       return Range();
    486     }
    487   }
    488 
    489   std::vector<Range> rangesFromConstant(Constant *C) {
    490     unsigned NumItems = getNumItemsFromConstant(C);
    491     std::vector<Range> r;
    492     r.reserve(NumItems);
    493     for (unsigned i = 0, e = NumItems; i != e; ++i)
    494       r.push_back(getItemFromConstant(C, i));
    495     return r;
    496   }
    497 
    498 public:
    499 
    500   explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
    501                           Holder(C) {}
    502 
    503   IntegersSubset(const IntegersSubset& RHS) :
    504     ParentTy(*(const ParentTy *)&RHS), // FIXME: tweak for msvc.
    505     Holder(RHS.Holder) {}
    506 
    507   template<class RangesCollectionTy>
    508   explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) {
    509     std::vector<Constant*> Elts;
    510     Elts.reserve(Src.size());
    511     for (typename RangesCollectionTy::const_iterator i = Src.begin(),
    512          e = Src.end(); i != e; ++i) {
    513       const Range &R = *i;
    514       std::vector<Constant*> r;
    515       if (R.isSingleNumber()) {
    516         r.reserve(2);
    517         // FIXME: Since currently we have ConstantInt based numbers
    518         // use hack-conversion of IntItem to ConstantInt
    519         r.push_back(R.getLow().toConstantInt());
    520         r.push_back(R.getHigh().toConstantInt());
    521       } else {
    522         r.reserve(1);
    523         r.push_back(R.getLow().toConstantInt());
    524       }
    525       Constant *CV = ConstantVector::get(r);
    526       Elts.push_back(CV);
    527     }
    528     ArrayType *ArrTy =
    529         ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
    530     Holder = ConstantArray::get(ArrTy, Elts);
    531   }
    532 
    533   operator Constant*() { return Holder; }
    534   operator const Constant*() const { return Holder; }
    535   Constant *operator->() { return Holder; }
    536   const Constant *operator->() const { return Holder; }
    537 };
    538 
    539 }
    540 
    541 #endif /* CONSTANTRANGESSET_H_ */
    542