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 template <class ImplTy>
  29 class IntItemBase {
  30 protected:
  31   ImplTy Implementation;
  32   typedef IntItemBase<ImplTy> self;
  33 public:
  34
  35   IntItemBase() {}
  36
  37   IntItemBase(const ImplTy &impl) : Implementation(impl) {}
  38
  39   // implicit
  40   IntItemBase(const APInt& src) : Implementation(src) {}
  41
  42   operator const APInt&() const {
  43     return (const APInt&)Implementation;
  44   }
  45   bool operator<(const self& RHS) const {
  46     return ((const APInt&)*this).ult(RHS);
  47   }
  48   bool operator==(const self& RHS) const {
  49     return (const APInt&)*this == (const APInt&)RHS;
  50   }
  51   bool operator!=(const self& RHS) const {
  52     return (const APInt&)*this != (const APInt&)RHS;
  53   }
  54   self& operator=(const ImplTy& RHS) {
  55     Implementation = RHS;
  56     return *this;
  57   }
  58   const APInt* operator->() const {
  59     return &((const APInt&)Implementation);
  60   }
  61   const APInt& operator*() const {
  62     return ((const APInt&)Implementation);
  63   }
  64   // FIXME: Hack. Will removed.
  65   ImplTy& getImplementation() {
  66     return Implementation;
  67   }
  68 };
  69
  70 class IntItemConstantIntImpl {
  71   const ConstantInt *ConstantIntVal;
  72 public:
  73   IntItemConstantIntImpl() : ConstantIntVal(0) {}
  74   IntItemConstantIntImpl(const ConstantInt *Val) : ConstantIntVal(Val) {}
  75   IntItemConstantIntImpl(LLVMContext &Ctx, const APInt& src) {
  76     ConstantIntVal = cast<ConstantInt>(ConstantInt::get(Ctx, src));
  77   }
  78   explicit IntItemConstantIntImpl(const APInt& src) {
  79     ConstantIntVal =
  80         cast<ConstantInt>(ConstantInt::get(llvm::getGlobalContext(), src));
  81   }
  82   operator const APInt&() const {
  83     return ConstantIntVal->getValue();
  84   }
  85   operator const ConstantInt*() {
  86     return ConstantIntVal;
  87   }
  88 };
  89
  90 class IntItem : public IntItemBase<IntItemConstantIntImpl> {
  91   typedef IntItemBase<IntItemConstantIntImpl> ParentTy;
  92   IntItem(const IntItemConstantIntImpl& Impl) : ParentTy(Impl) {}
  93 public:
  94
  95   IntItem() {}
  96
  97   // implicit
  98   IntItem(const APInt& src) : ParentTy(src) {}
  99
 100   static IntItem fromConstantInt(const ConstantInt *V) {
 101     IntItemConstantIntImpl Impl(V);
 102     return IntItem(Impl);
 103   }
 104   static IntItem fromType(Type* Ty, const APInt& V) {
 105     ConstantInt *C = cast<ConstantInt>(ConstantInt::get(Ty, V));
 106     return fromConstantInt(C);
 107   }
 108   ConstantInt *toConstantInt() {
 109     return const_cast<ConstantInt*>((const ConstantInt*)Implementation);
 110   }
 111 };
 112
 113 // TODO: it should be a class in next commit.
 114 struct IntRange {
 115
 116     IntItem Low;
 117     IntItem High;
 118     bool IsEmpty : 1;
 119     bool IsSingleNumber : 1;
 120 // TODO:
 121 // public:
 122
 123     typedef std::pair<IntRange, IntRange> SubRes;
 124
 125     IntRange() : IsEmpty(true) {}
 126     IntRange(const IntRange &RHS) :
 127       Low(RHS.Low), High(RHS.High), IsEmpty(false), IsSingleNumber(false) {}
 128     IntRange(const IntItem &C) :
 129       Low(C), High(C), IsEmpty(false), IsSingleNumber(true) {}
 130     IntRange(const IntItem &L, const IntItem &H) : Low(L), High(H),
 131         IsEmpty(false), IsSingleNumber(false) {}
 132
 133     bool isEmpty() const { return IsEmpty; }
 134     bool isSingleNumber() const { return IsSingleNumber; }
 135
 136     const IntItem& getLow() {
 137       assert(!IsEmpty && "Range is empty.");
 138       return Low;
 139     }
 140     const IntItem& getHigh() {
 141       assert(!IsEmpty && "Range is empty.");
 142       return High;
 143     }
 144
 145     bool operator<(const IntRange &RHS) const {
 146       assert(!IsEmpty && "Left range is empty.");
 147       assert(!RHS.IsEmpty && "Right range is empty.");
 148       if (Low->getBitWidth() == RHS.Low->getBitWidth()) {
 149         if (Low->eq(RHS.Low)) {
 150           if (High->ult(RHS.High))
 151             return true;
 152           return false;
 153         }
 154         if (Low->ult(RHS.Low))
 155           return true;
 156         return false;
 157       } else
 158         return Low->getBitWidth() < RHS.Low->getBitWidth();
 159     }
 160
 161     bool operator==(const IntRange &RHS) const {
 162       assert(!IsEmpty && "Left range is empty.");
 163       assert(!RHS.IsEmpty && "Right range is empty.");
 164       if (Low->getBitWidth() != RHS.Low->getBitWidth())
 165         return false;
 166       return Low == RHS.Low && High == RHS.High;
 167     }
 168
 169     bool operator!=(const IntRange &RHS) const {
 170       return !operator ==(RHS);
 171     }
 172
 173     static bool LessBySize(const IntRange &LHS, const IntRange &RHS) {
 174       assert(LHS.Low->getBitWidth() == RHS.Low->getBitWidth() &&
 175           "This type of comparison requires equal bit width for LHS and RHS");
 176       APInt LSize = *LHS.High - *LHS.Low;
 177       APInt RSize = *RHS.High - *RHS.Low;
 178       return LSize.ult(RSize);
 179     }
 180
 181     bool isInRange(const APInt &IntVal) const {
 182       assert(!IsEmpty && "Range is empty.");
 183       if (IntVal.getBitWidth() != Low->getBitWidth())
 184         return false;
 185       return IntVal.uge(Low) && IntVal.ule(High);
 186     }
 187
 188     SubRes sub(const IntRange &RHS) const {
 189       SubRes Res;
 190
 191       // RHS is either more global and includes this range or
 192       // if it doesn't intersected with this range.
 193       if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
 194
 195         // If RHS more global (it is enough to check
 196         // only one border in this case.
 197         if (RHS.isInRange(Low))
 198           return std::make_pair(IntRange(Low, High), IntRange());
 199
 200         return Res;
 201       }
 202
 203       if (Low->ult(RHS.Low)) {
 204         Res.first.Low = Low;
 205         APInt NewHigh = RHS.Low;
 206         --NewHigh;
 207         Res.first.High = NewHigh;
 208       }
 209       if (High->ugt(RHS.High)) {
 210         APInt NewLow = RHS.High;
 211         ++NewLow;
 212         Res.second.Low = NewLow;
 213         Res.second.High = High;
 214       }
 215       return Res;
 216     }
 217   };
 218
 219 //===----------------------------------------------------------------------===//
 220 /// ConstantRangesSet - class that implements constant set of ranges.
 221 /// It is a wrapper for some real "holder" class (currently ConstantArray).
 222 /// It contains functions, that allows to parse "holder" like a set of ranges.
 223 /// Note: It is assumed that "holder" is inherited from Constant object.
 224 ///       ConstantRangesSet may be converted to and from Constant* pointer.
 225 ///
 226 class IntegersSubset {
 227   Constant *Array;
 228 public:
 229
 230   bool IsWide;
 231
 232   // implicit
 233   IntegersSubset(Constant *V) : Array(V) {
 234     ArrayType *ArrTy = cast<ArrayType>(Array->getType());
 235     VectorType *VecTy = cast<VectorType>(ArrTy->getElementType());
 236     IntegerType *IntTy = cast<IntegerType>(VecTy->getElementType());
 237     IsWide = IntTy->getBitWidth() > 64;
 238   }
 239
 240   operator Constant*() { return Array; }
 241   operator const Constant*() const { return Array; }
 242   Constant *operator->() { return Array; }
 243   const Constant *operator->() const { return Array; }
 244
 245   typedef IntRange Range;
 246
 247   /// Checks is the given constant satisfies this case. Returns
 248   /// true if it equals to one of contained values or belongs to the one of
 249   /// contained ranges.
 250   bool isSatisfies(const IntItem &CheckingVal) const {
 251     for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
 252       const Constant *CV = Array->getAggregateElement(i);
 253       unsigned VecSize = cast<VectorType>(CV->getType())->getNumElements();
 254       switch (VecSize) {
 255       case 1:
 256         if (cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue() ==
 257             CheckingVal)
 258           return true;
 259         break;
 260       case 2: {
 261         const APInt &Lo =
 262             cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue();
 263         const APInt &Hi =
 264             cast<const ConstantInt>(CV->getAggregateElement(1))->getValue();
 265         if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal))
 266           return true;
 267       }
 268         break;
 269       default:
 270         assert(0 && "Only pairs and single numbers are allowed here.");
 271         break;
 272       }
 273     }
 274     return false;
 275   }
 276
 277   /// Returns set's item with given index.
 278   Range getItem(unsigned idx) {
 279     Constant *CV = Array->getAggregateElement(idx);
 280     unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
 281     switch (NumEls) {
 282     case 1:
 283       return Range(IntItem::fromConstantInt(
 284                     cast<ConstantInt>(CV->getAggregateElement(0U))));
 285     case 2:
 286       return Range(IntItem::fromConstantInt(
 287                      cast<ConstantInt>(CV->getAggregateElement(0U))),
 288                    IntItem::fromConstantInt(
 289                      cast<ConstantInt>(CV->getAggregateElement(1U))));
 290     default:
 291       assert(0 && "Only pairs and single numbers are allowed here.");
 292       return Range();
 293     }
 294   }
 295
 296   const Range getItem(unsigned idx) const {
 297     const Constant *CV = Array->getAggregateElement(idx);
 298
 299     unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
 300     switch (NumEls) {
 301     case 1:
 302       return Range(IntItem::fromConstantInt(
 303                      cast<ConstantInt>(CV->getAggregateElement(0U))),
 304                    IntItem::fromConstantInt(cast<ConstantInt>(
 305                      cast<ConstantInt>(CV->getAggregateElement(0U)))));
 306     case 2:
 307       return Range(IntItem::fromConstantInt(
 308                      cast<ConstantInt>(CV->getAggregateElement(0U))),
 309                    IntItem::fromConstantInt(
 310                    cast<ConstantInt>(CV->getAggregateElement(1))));
 311     default:
 312       assert(0 && "Only pairs and single numbers are allowed here.");
 313       return Range();
 314     }
 315   }
 316
 317   /// Return number of items (ranges) stored in set.
 318   unsigned getNumItems() const {
 319     return cast<ArrayType>(Array->getType())->getNumElements();
 320   }
 321
 322   bool isWideNumberFormat() const { return IsWide; }
 323
 324   bool isSingleNumber(unsigned idx) const {
 325     Constant *CV = Array->getAggregateElement(idx);
 326     return cast<VectorType>(CV->getType())->getNumElements() == 1;
 327   }
 328
 329   /// Returns set the size, that equals number of all values + sizes of all
 330   /// ranges.
 331   /// Ranges set is considered as flat numbers collection.
 332   /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
 333   ///       for range [<0>, <1>, <5>] the size will 3
 334   unsigned getSize() const {
 335     APInt sz(getItem(0).Low->getBitWidth(), 0);
 336     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
 337       const APInt &Low = getItem(i).Low;
 338       const APInt &High = getItem(i).High;
 339       const APInt &S = High - Low;
 340       sz += S;
 341     }
 342     return sz.getZExtValue();
 343   }
 344
 345   /// Allows to access single value even if it belongs to some range.
 346   /// Ranges set is considered as flat numbers collection.
 347   /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
 348   /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
 349   APInt getSingleValue(unsigned idx) const {
 350     APInt sz(getItem(0).Low->getBitWidth(), 0);
 351     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
 352       const APInt &Low = getItem(i).Low;
 353       const APInt &High = getItem(i).High;
 354       const APInt& S = High - Low;
 355       APInt oldSz = sz;
 356       sz += S;
 357       if (oldSz.uge(i) && sz.ult(i)) {
 358         APInt Res = Low;
 359         APInt Offset(oldSz.getBitWidth(), i);
 360         Offset -= oldSz;
 361         Res += Offset;
 362         return Res;
 363       }
 364     }
 365     assert(0 && "Index exceeds high border.");
 366     return sz;
 367   }
 368 };
 369
 370 }
 371
 372 #endif /* CONSTANTRANGESSET_H_ */