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 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 (unsigned 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   unsigned 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 (unsigned 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 */