include/llvm/Support/IntegersSubset.h

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