include/llvm/Support/IntegersSubset.h

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