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 "llvm/Constants.h"
  23 #include "llvm/DerivedTypes.h"
  24 #include "llvm/LLVMContext.h"
  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 ConstantIntVal->getValue().func(RHS); \
  43   }
  44
  45 #define INT_ITEM_DEFINE_UNARY_OP(op) \
  46   IntItem operator op () const { \
  47     APInt res = op(ConstantIntVal->getValue()); \
  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 = ConstantIntVal->getValue() 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 = ConstantIntVal->getValue();\
  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 = ConstantIntVal->getValue(); \
  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 = ConstantIntVal->getValue();\
  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(ConstantIntVal->getValue().getBitWidth(), RHS); \
  90   }
  91
  92 class IntItem {
  93   ConstantInt *ConstantIntVal;
  94   IntItem(const ConstantInt *V) : ConstantIntVal(const_cast<ConstantInt*>(V)) {}
  95 public:
  96
  97   IntItem() {}
  98
  99   operator const APInt&() const {
 100     return (const APInt&)ConstantIntVal->getValue();
 101   }
 102
 103   // Propogate APInt operators.
 104   // Note, that
 105   // /,/=,>>,>>= are not implemented in APInt.
 106   // <<= is implemented for unsigned RHS, but not implemented for APInt RHS.
 107
 108   INT_ITEM_DEFINE_COMPARISON(<, ult);
 109   INT_ITEM_DEFINE_COMPARISON(>, ugt);
 110   INT_ITEM_DEFINE_COMPARISON(<=, ule);
 111   INT_ITEM_DEFINE_COMPARISON(>=, uge);
 112   INT_ITEM_DEFINE_COMPARISON(==, eq);
 113   INT_ITEM_DEFINE_COMPARISON(!=, ne);
 114
 115   INT_ITEM_DEFINE_BINARY_OP(*);
 116   INT_ITEM_DEFINE_BINARY_OP(+);
 117   INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,+,uint64_t);
 118   INT_ITEM_DEFINE_BINARY_OP(-);
 119   INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,-,uint64_t);
 120   INT_ITEM_DEFINE_BINARY_OP(<<);
 121   INT_ITEM_DEFINE_OP_STANDARD_INT(IntItem,<<,unsigned);
 122   INT_ITEM_DEFINE_BINARY_OP(&);
 123   INT_ITEM_DEFINE_BINARY_OP(^);
 124   INT_ITEM_DEFINE_BINARY_OP(|);
 125
 126   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(*=);
 127   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(+=);
 128   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(-=);
 129   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(&=);
 130   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(^=);
 131   INT_ITEM_DEFINE_ASSIGNMENT_BY_OP(|=);
 132
 133   // Special case for <<=
 134   IntItem& operator <<= (unsigned RHS) {
 135     APInt res = ConstantIntVal->getValue();
 136     res <<= RHS;
 137     Constant *NewVal = ConstantInt::get(ConstantIntVal->getContext(), res);
 138     ConstantIntVal = cast<ConstantInt>(NewVal);
 139     return *this;
 140   }
 141
 142   INT_ITEM_DEFINE_UNARY_OP(-);
 143   INT_ITEM_DEFINE_UNARY_OP(~);
 144
 145   INT_ITEM_DEFINE_PREINCDEC(++);
 146   INT_ITEM_DEFINE_PREINCDEC(--);
 147
 148   // The set of workarounds, since currently we use ConstantInt implemented
 149   // integer.
 150
 151   static IntItem fromConstantInt(const ConstantInt *V) {
 152     return IntItem(V);
 153   }
 154   static IntItem fromType(Type* Ty, const APInt& V) {
 155     ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
 156     return fromConstantInt(C);
 157   }
 158   static IntItem withImplLikeThis(const IntItem& LikeThis, const APInt& V) {
 159     ConstantInt *C = cast<ConstantInt>(ConstantInt::get(
 160         LikeThis.ConstantIntVal->getContext(), V));
 161     return fromConstantInt(C);
 162   }
 163   ConstantInt *toConstantInt() {
 164     return ConstantIntVal;
 165   }
 166 };
 167
 168 // TODO: it should be a class in next commit.
 169 struct IntRange {
 170
 171     IntItem Low;
 172     IntItem High;
 173     bool IsEmpty : 1;
 174     bool IsSingleNumber : 1;
 175 // TODO:
 176 // public:
 177
 178     typedef std::pair<IntRange, IntRange> SubRes;
 179
 180     IntRange() : IsEmpty(true) {}
 181     IntRange(const IntRange &RHS) :
 182       Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
 183     IntRange(const IntItem &C) :
 184       Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
 185     IntRange(const IntItem &L, const IntItem &H) : Low(L), High(H),
 186         IsEmpty(false), IsSingleNumber(false) {}
 187
 188     bool isEmpty() const { return IsEmpty; }
 189     bool isSingleNumber() const { return IsSingleNumber; }
 190
 191     const IntItem& getLow() {
 192       assert(!IsEmpty && "Range is empty.");
 193       return Low;
 194     }
 195     const IntItem& getHigh() {
 196       assert(!IsEmpty && "Range is empty.");
 197       return High;
 198     }
 199
 200     bool operator<(const IntRange &RHS) const {
 201       assert(!IsEmpty && "Left range is empty.");
 202       assert(!RHS.IsEmpty && "Right range is empty.");
 203       if (Low == RHS.Low) {
 204         if (High > RHS.High)
 205           return true;
 206         return false;
 207       }
 208       if (Low < RHS.Low)
 209         return true;
 210       return false;
 211     }
 212
 213     bool operator==(const IntRange &RHS) const {
 214       assert(!IsEmpty && "Left range is empty.");
 215       assert(!RHS.IsEmpty && "Right range is empty.");
 216       return Low == RHS.Low && High == RHS.High;
 217     }
 218
 219     bool operator!=(const IntRange &RHS) const {
 220       return !operator ==(RHS);
 221     }
 222
 223     static bool LessBySize(const IntRange &LHS, const IntRange &RHS) {
 224       return (LHS.High - LHS.Low) < (RHS.High - RHS.Low);
 225     }
 226
 227     bool isInRange(const IntItem &IntVal) const {
 228       assert(!IsEmpty && "Range is empty.");
 229       return IntVal >= Low && IntVal <= High;
 230     }
 231
 232     SubRes sub(const IntRange &RHS) const {
 233       SubRes Res;
 234
 235       // RHS is either more global and includes this range or
 236       // if it doesn't intersected with this range.
 237       if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
 238
 239         // If RHS more global (it is enough to check
 240         // only one border in this case.
 241         if (RHS.isInRange(Low))
 242           return std::make_pair(IntRange(Low, High), IntRange());
 243
 244         return Res;
 245       }
 246
 247       if (Low < RHS.Low) {
 248         Res.first.Low = Low;
 249         IntItem NewHigh = RHS.Low;
 250         --NewHigh;
 251         Res.first.High = NewHigh;
 252       }
 253       if (High > RHS.High) {
 254         IntItem NewLow = RHS.High;
 255         ++NewLow;
 256         Res.second.Low = NewLow;
 257         Res.second.High = High;
 258       }
 259       return Res;
 260     }
 261   };
 262
 263 //===----------------------------------------------------------------------===//
 264 /// ConstantRangesSet - class that implements constant set of ranges.
 265 /// It is a wrapper for some real "holder" class (currently ConstantArray).
 266 /// It contains functions, that allows to parse "holder" like a set of ranges.
 267 /// Note: It is assumed that "holder" is inherited from Constant object.
 268 ///       ConstantRangesSet may be converted to and from Constant* pointer.
 269 ///
 270 class IntegersSubset {
 271   Constant *Array;
 272 public:
 273
 274   bool IsWide;
 275
 276   // implicit
 277   IntegersSubset(Constant *V) : Array(V) {
 278     ArrayType *ArrTy = cast<ArrayType>(Array->getType());
 279     VectorType *VecTy = cast<VectorType>(ArrTy->getElementType());
 280     IntegerType *IntTy = cast<IntegerType>(VecTy->getElementType());
 281     IsWide = IntTy->getBitWidth() > 64;
 282   }
 283
 284   operator Constant*() { return Array; }
 285   operator const Constant*() const { return Array; }
 286   Constant *operator->() { return Array; }
 287   const Constant *operator->() const { return Array; }
 288
 289   typedef IntRange Range;
 290
 291   /// Checks is the given constant satisfies this case. Returns
 292   /// true if it equals to one of contained values or belongs to the one of
 293   /// contained ranges.
 294   bool isSatisfies(const IntItem &CheckingVal) const {
 295     for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
 296       const Constant *CV = Array->getAggregateElement(i);
 297       unsigned VecSize = cast<VectorType>(CV->getType())->getNumElements();
 298       switch (VecSize) {
 299       case 1:
 300         if (cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue() ==
 301             CheckingVal)
 302           return true;
 303         break;
 304       case 2: {
 305         const APInt &Lo =
 306             cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue();
 307         const APInt &Hi =
 308             cast<const ConstantInt>(CV->getAggregateElement(1))->getValue();
 309         if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal))
 310           return true;
 311       }
 312         break;
 313       default:
 314         assert(0 && "Only pairs and single numbers are allowed here.");
 315         break;
 316       }
 317     }
 318     return false;
 319   }
 320
 321   /// Returns set's item with given index.
 322   Range getItem(unsigned idx) {
 323     Constant *CV = Array->getAggregateElement(idx);
 324     unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
 325     switch (NumEls) {
 326     case 1:
 327       return Range(IntItem::fromConstantInt(
 328                     cast<ConstantInt>(CV->getAggregateElement(0U))));
 329     case 2:
 330       return Range(IntItem::fromConstantInt(
 331                      cast<ConstantInt>(CV->getAggregateElement(0U))),
 332                    IntItem::fromConstantInt(
 333                      cast<ConstantInt>(CV->getAggregateElement(1U))));
 334     default:
 335       assert(0 && "Only pairs and single numbers are allowed here.");
 336       return Range();
 337     }
 338   }
 339
 340   const Range getItem(unsigned idx) const {
 341     const Constant *CV = Array->getAggregateElement(idx);
 342
 343     unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
 344     switch (NumEls) {
 345     case 1:
 346       return Range(IntItem::fromConstantInt(
 347                      cast<ConstantInt>(CV->getAggregateElement(0U))),
 348                    IntItem::fromConstantInt(cast<ConstantInt>(
 349                      cast<ConstantInt>(CV->getAggregateElement(0U)))));
 350     case 2:
 351       return Range(IntItem::fromConstantInt(
 352                      cast<ConstantInt>(CV->getAggregateElement(0U))),
 353                    IntItem::fromConstantInt(
 354                    cast<ConstantInt>(CV->getAggregateElement(1))));
 355     default:
 356       assert(0 && "Only pairs and single numbers are allowed here.");
 357       return Range();
 358     }
 359   }
 360
 361   /// Return number of items (ranges) stored in set.
 362   unsigned getNumItems() const {
 363     return cast<ArrayType>(Array->getType())->getNumElements();
 364   }
 365
 366   bool isWideNumberFormat() const { return IsWide; }
 367
 368   bool isSingleNumber(unsigned idx) const {
 369     Constant *CV = Array->getAggregateElement(idx);
 370     return cast<VectorType>(CV->getType())->getNumElements() == 1;
 371   }
 372
 373   /// Returns set the size, that equals number of all values + sizes of all
 374   /// ranges.
 375   /// Ranges set is considered as flat numbers collection.
 376   /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
 377   ///       for range [<0>, <1>, <5>] the size will 3
 378   unsigned getSize() const {
 379     APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0);
 380     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
 381       const APInt &Low = getItem(i).Low;
 382       const APInt &High = getItem(i).High;
 383       const APInt &S = High - Low;
 384       sz += S;
 385     }
 386     return sz.getZExtValue();
 387   }
 388
 389   /// Allows to access single value even if it belongs to some range.
 390   /// Ranges set is considered as flat numbers collection.
 391   /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
 392   /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
 393   APInt getSingleValue(unsigned idx) const {
 394     APInt sz(((const APInt&)getItem(0).Low).getBitWidth(), 0);
 395     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
 396       const APInt &Low = getItem(i).Low;
 397       const APInt &High = getItem(i).High;
 398       const APInt& S = High - Low;
 399       APInt oldSz = sz;
 400       sz += S;
 401       if (oldSz.uge(i) && sz.ult(i)) {
 402         APInt Res = Low;
 403         APInt Offset(oldSz.getBitWidth(), i);
 404         Offset -= oldSz;
 405         Res += Offset;
 406         return Res;
 407       }
 408     }
 409     assert(0 && "Index exceeds high border.");
 410     return sz;
 411   }
 412 };
 413
 414 }
 415
 416 #endif /* CONSTANTRANGESSET_H_ */