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