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 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     enum Type {
 186       SINGLE_NUMBER,
 187       RANGE,
 188       UNKNOWN
 189     };
 190     Type RangeType;
 191
 192 public:
 193     typedef IntRange<IntType> self;
 194     typedef std::pair<self, self> SubRes;
 195
 196     IntRange() : IsEmpty(true) {}
 197     IntRange(const self &RHS) :
 198       Low(RHS.Low), High(RHS.High),
 199       IsEmpty(RHS.IsEmpty), RangeType(RHS.RangeType) {}
 200     IntRange(const IntType &C) :
 201       Low(C), High(C), IsEmpty(false), RangeType(SINGLE_NUMBER) {}
 202
 203     IntRange(const IntType &L, const IntType &H) : Low(L), High(H),
 204       IsEmpty(false), RangeType(UNKNOWN) {}
 205
 206     bool isEmpty() const { return IsEmpty; }
 207     bool isSingleNumber() const {
 208       switch (RangeType) {
 209       case SINGLE_NUMBER:
 210         return true;
 211       case RANGE:
 212         return false;
 213       case UNKNOWN:
 214         if (Low == High) {
 215           const_cast<Type&>(RangeType) = SINGLE_NUMBER;
 216           return true;
 217         }
 218         const_cast<Type&>(RangeType) = RANGE;
 219         return false;
 220       }
 221       assert(!"Unknown state?!");
 222       return false;
 223     }
 224
 225     const IntType& getLow() const {
 226       assert(!IsEmpty && "Range is empty.");
 227       return Low;
 228     }
 229     const IntType& getHigh() const {
 230       assert(!IsEmpty && "Range is empty.");
 231       return High;
 232     }
 233
 234     bool operator<(const self &RHS) const {
 235       assert(!IsEmpty && "Left range is empty.");
 236       assert(!RHS.IsEmpty && "Right range is empty.");
 237       if (Low < RHS.Low)
 238         return true;
 239       if (Low == RHS.Low) {
 240         if (High > RHS.High)
 241           return true;
 242         return false;
 243       }
 244       return false;
 245     }
 246
 247     bool operator==(const self &RHS) const {
 248       assert(!IsEmpty && "Left range is empty.");
 249       assert(!RHS.IsEmpty && "Right range is empty.");
 250       return Low == RHS.Low && High == RHS.High;
 251     }
 252
 253     bool operator!=(const self &RHS) const {
 254       return !operator ==(RHS);
 255     }
 256
 257     static bool LessBySize(const self &LHS, const self &RHS) {
 258       return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
 259     }
 260
 261     bool isInRange(const IntType &IntVal) const {
 262       assert(!IsEmpty && "Range is empty.");
 263       return IntVal >= Low && IntVal <= High;
 264     }
 265
 266     SubRes sub(const self &RHS) const {
 267       SubRes Res;
 268
 269       // RHS is either more global and includes this range or
 270       // if it doesn't intersected with this range.
 271       if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
 272
 273         // If RHS more global (it is enough to check
 274         // only one border in this case.
 275         if (RHS.isInRange(Low))
 276           return std::make_pair(self(Low, High), self());
 277
 278         return Res;
 279       }
 280
 281       if (Low < RHS.Low) {
 282         Res.first.Low = Low;
 283         IntType NewHigh = RHS.Low;
 284         --NewHigh;
 285         Res.first.High = NewHigh;
 286       }
 287       if (High > RHS.High) {
 288         IntType NewLow = RHS.High;
 289         ++NewLow;
 290         Res.second.Low = NewLow;
 291         Res.second.High = High;
 292       }
 293       return Res;
 294     }
 295   };
 296
 297 //===----------------------------------------------------------------------===//
 298 /// IntegersSubsetGeneric - class that implements the subset of integers. It
 299 /// consists from ranges and single numbers.
 300 template <class IntTy>
 301 class IntegersSubsetGeneric {
 302 public:
 303   // Use Chris Lattner idea, that was initially described here:
 304   // http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120213/136954.html
 305   // In short, for more compact memory consumption we can store flat
 306   // numbers collection, and define range as pair of indices.
 307   // In that case we can safe some memory on 32 bit machines.
 308   typedef std::vector<IntTy> FlatCollectionTy;
 309   typedef std::pair<IntTy*, IntTy*> RangeLinkTy;
 310   typedef std::vector<RangeLinkTy> RangeLinksTy;
 311   typedef typename RangeLinksTy::const_iterator RangeLinksConstIt;
 312
 313   typedef IntegersSubsetGeneric<IntTy> self;
 314
 315 protected:
 316
 317   FlatCollectionTy FlatCollection;
 318   RangeLinksTy RangeLinks;
 319
 320   bool IsSingleNumber;
 321   bool IsSingleNumbersOnly;
 322
 323 public:
 324
 325   template<class RangesCollectionTy>
 326   explicit IntegersSubsetGeneric(const RangesCollectionTy& Links) {
 327     assert(Links.size() && "Empty ranges are not allowed.");
 328
 329     // In case of big set of single numbers consumes additional RAM space,
 330     // but allows to avoid additional reallocation.
 331     FlatCollection.reserve(Links.size() * 2);
 332     RangeLinks.reserve(Links.size());
 333     IsSingleNumbersOnly = true;
 334     for (typename RangesCollectionTy::const_iterator i = Links.begin(),
 335          e = Links.end(); i != e; ++i) {
 336       RangeLinkTy RangeLink;
 337       FlatCollection.push_back(i->getLow());
 338       RangeLink.first = &FlatCollection.back();
 339       if (i->getLow() != i->getHigh()) {
 340         FlatCollection.push_back(i->getHigh());
 341         IsSingleNumbersOnly = false;
 342       }
 343       RangeLink.second = &FlatCollection.back();
 344       RangeLinks.push_back(RangeLink);
 345     }
 346     IsSingleNumber = IsSingleNumbersOnly && RangeLinks.size() == 1;
 347   }
 348
 349   IntegersSubsetGeneric(const self& RHS) {
 350     *this = RHS;
 351   }
 352
 353   self& operator=(const self& RHS) {
 354     FlatCollection.clear();
 355     RangeLinks.clear();
 356     FlatCollection.reserve(RHS.RangeLinks.size() * 2);
 357     RangeLinks.reserve(RHS.RangeLinks.size());
 358     for (RangeLinksConstIt i = RHS.RangeLinks.begin(), e = RHS.RangeLinks.end();
 359          i != e; ++i) {
 360       RangeLinkTy RangeLink;
 361       FlatCollection.push_back(*(i->first));
 362       RangeLink.first = &FlatCollection.back();
 363       if (i->first != i->second)
 364         FlatCollection.push_back(*(i->second));
 365       RangeLink.second = &FlatCollection.back();
 366       RangeLinks.push_back(RangeLink);
 367     }
 368     IsSingleNumber = RHS.IsSingleNumber;
 369     IsSingleNumbersOnly = RHS.IsSingleNumbersOnly;
 370     return *this;
 371   }
 372
 373   typedef IntRange<IntTy> Range;
 374
 375   /// Checks is the given constant satisfies this case. Returns
 376   /// true if it equals to one of contained values or belongs to the one of
 377   /// contained ranges.
 378   bool isSatisfies(const IntTy &CheckingVal) const {
 379     if (IsSingleNumber)
 380       return FlatCollection.front() == CheckingVal;
 381     if (IsSingleNumbersOnly)
 382       return std::find(FlatCollection.begin(),
 383                        FlatCollection.end(),
 384                        CheckingVal) != FlatCollection.end();
 385
 386     for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
 387       if (RangeLinks[i].first == RangeLinks[i].second) {
 388         if (*RangeLinks[i].first == CheckingVal)
 389           return true;
 390       } else if (*RangeLinks[i].first <= CheckingVal &&
 391                  *RangeLinks[i].second >= CheckingVal)
 392         return true;
 393     }
 394     return false;
 395   }
 396
 397   /// Returns set's item with given index.
 398   Range getItem(unsigned idx) const {
 399     const RangeLinkTy &Link = RangeLinks[idx];
 400     if (Link.first != Link.second)
 401       return Range(*Link.first, *Link.second);
 402     else
 403       return Range(*Link.first);
 404   }
 405
 406   /// Return number of items (ranges) stored in set.
 407   unsigned getNumItems() const {
 408     return RangeLinks.size();
 409   }
 410
 411   /// Returns true if whole subset contains single element.
 412   bool isSingleNumber() const {
 413     return IsSingleNumber;
 414   }
 415
 416   /// Returns true if whole subset contains only single numbers, no ranges.
 417   bool isSingleNumbersOnly() const {
 418     return IsSingleNumbersOnly;
 419   }
 420
 421   /// Does the same like getItem(idx).isSingleNumber(), but
 422   /// works faster, since we avoid creation of temporary range object.
 423   bool isSingleNumber(unsigned idx) const {
 424     return RangeLinks[idx].first == RangeLinks[idx].second;
 425   }
 426
 427   /// Returns set the size, that equals number of all values + sizes of all
 428   /// ranges.
 429   /// Ranges set is considered as flat numbers collection.
 430   /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
 431   ///       for range [<0>, <1>, <5>] the size will 3
 432   unsigned getSize() const {
 433     APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
 434     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
 435       const APInt &Low = getItem(i).getLow();
 436       const APInt &High = getItem(i).getHigh();
 437       APInt S = High - Low + 1;
 438       sz += S;
 439     }
 440     return sz.getZExtValue();
 441   }
 442
 443   /// Allows to access single value even if it belongs to some range.
 444   /// Ranges set is considered as flat numbers collection.
 445   /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
 446   /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
 447   APInt getSingleValue(unsigned idx) const {
 448     APInt sz(((const APInt&)getItem(0).getLow()).getBitWidth(), 0);
 449     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
 450       const APInt &Low = getItem(i).getLow();
 451       const APInt &High = getItem(i).getHigh();
 452       APInt S = High - Low + 1;
 453       APInt oldSz = sz;
 454       sz += S;
 455       if (sz.ugt(idx)) {
 456         APInt Res = Low;
 457         APInt Offset(oldSz.getBitWidth(), idx);
 458         Offset -= oldSz;
 459         Res += Offset;
 460         return Res;
 461       }
 462     }
 463     assert(0 && "Index exceeds high border.");
 464     return sz;
 465   }
 466
 467   /// Does the same as getSingleValue, but works only if subset contains
 468   /// single numbers only.
 469   const IntTy& getSingleNumber(unsigned idx) const {
 470     assert(IsSingleNumbersOnly && "This method works properly if subset "
 471                                   "contains single numbers only.");
 472     return FlatCollection[idx];
 473   }
 474 };
 475
 476 //===----------------------------------------------------------------------===//
 477 /// IntegersSubset - currently is extension of IntegersSubsetGeneric
 478 /// that also supports conversion to/from Constant* object.
 479 class IntegersSubset : public IntegersSubsetGeneric<IntItem> {
 480
 481   typedef IntegersSubsetGeneric<IntItem> ParentTy;
 482
 483   Constant *Holder;
 484
 485   static unsigned getNumItemsFromConstant(Constant *C) {
 486     return cast<ArrayType>(C->getType())->getNumElements();
 487   }
 488
 489   static Range getItemFromConstant(Constant *C, unsigned idx) {
 490     const Constant *CV = C->getAggregateElement(idx);
 491
 492     unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
 493     switch (NumEls) {
 494     case 1:
 495       return Range(IntItem::fromConstantInt(
 496                      cast<ConstantInt>(CV->getAggregateElement(0U))),
 497                    IntItem::fromConstantInt(cast<ConstantInt>(
 498                      cast<ConstantInt>(CV->getAggregateElement(0U)))));
 499     case 2:
 500       return Range(IntItem::fromConstantInt(
 501                      cast<ConstantInt>(CV->getAggregateElement(0U))),
 502                    IntItem::fromConstantInt(
 503                    cast<ConstantInt>(CV->getAggregateElement(1))));
 504     default:
 505       assert(0 && "Only pairs and single numbers are allowed here.");
 506       return Range();
 507     }
 508   }
 509
 510   std::vector<Range> rangesFromConstant(Constant *C) {
 511     unsigned NumItems = getNumItemsFromConstant(C);
 512     std::vector<Range> r;
 513     r.reserve(NumItems);
 514     for (unsigned i = 0, e = NumItems; i != e; ++i)
 515       r.push_back(getItemFromConstant(C, i));
 516     return r;
 517   }
 518
 519 public:
 520
 521   explicit IntegersSubset(Constant *C) : ParentTy(rangesFromConstant(C)),
 522                           Holder(C) {}
 523
 524   IntegersSubset(const IntegersSubset& RHS) :
 525     ParentTy(*(const ParentTy *)&RHS), // FIXME: tweak for msvc.
 526     Holder(RHS.Holder) {}
 527
 528   template<class RangesCollectionTy>
 529   explicit IntegersSubset(const RangesCollectionTy& Src) : ParentTy(Src) {
 530     std::vector<Constant*> Elts;
 531     Elts.reserve(Src.size());
 532     for (typename RangesCollectionTy::const_iterator i = Src.begin(),
 533          e = Src.end(); i != e; ++i) {
 534       const Range &R = *i;
 535       std::vector<Constant*> r;
 536       if (!R.isSingleNumber()) {
 537         r.reserve(2);
 538         // FIXME: Since currently we have ConstantInt based numbers
 539         // use hack-conversion of IntItem to ConstantInt
 540         r.push_back(R.getLow().toConstantInt());
 541         r.push_back(R.getHigh().toConstantInt());
 542       } else {
 543         r.reserve(1);
 544         r.push_back(R.getLow().toConstantInt());
 545       }
 546       Constant *CV = ConstantVector::get(r);
 547       Elts.push_back(CV);
 548     }
 549     ArrayType *ArrTy =
 550         ArrayType::get(Elts.front()->getType(), (uint64_t)Elts.size());
 551     Holder = ConstantArray::get(ArrTy, Elts);
 552   }
 553
 554   operator Constant*() { return Holder; }
 555   operator const Constant*() const { return Holder; }
 556   Constant *operator->() { return Holder; }
 557   const Constant *operator->() const { return Holder; }
 558 };
 559
 560 }
 561
 562 #endif /* CONSTANTRANGESSET_H_ */