include/llvm/ConstantRangesSet.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
  25 namespace llvm {
  26
  27 class ConstantRangesSet;
  28
  29 template <bool IsReadonly> struct CRSConstantTypes {
  30   typedef ConstantInt ConstantIntTy;
  31   typedef ConstantRangesSet ConstantRangesSetTy;
  32 };
  33
  34 template <>
  35 struct CRSConstantTypes<true> {
  36   typedef const ConstantInt ConstantIntTy;
  37   typedef const ConstantRangesSet ConstantRangesSetTy;
  38 };
  39
  40 //===----------------------------------------------------------------------===//
  41 /// ConstantRangesSet - class that implements constant set of ranges.
  42 /// It is a wrapper for some real "holder" class (currently ConstantArray).
  43 /// It contains functions, that allows to parse "holder" like a set of ranges.
  44 /// Note: It is assumed that "holder" is inherited from Constant object.
  45 ///       ConstantRangesSet may be converted to and from Constant* pointer.
  46 ///
  47 class ConstantRangesSet {
  48   Constant *Array;
  49 public:
  50
  51   // implicit
  52   ConstantRangesSet(Constant *V) : Array(V) {}
  53
  54   operator Constant*() { return Array; }
  55   operator const Constant*() const { return Array; }
  56   Constant *operator->() { return Array; }
  57   const Constant *operator->() const { return Array; }
  58
  59   template <bool IsReadonly>
  60   struct RangeT {
  61
  62     typedef typename CRSConstantTypes<IsReadonly>::ConstantIntTy ConstantIntTy;
  63     typedef std::pair<RangeT, RangeT> SubRes;
  64
  65     ConstantIntTy *Low;
  66     ConstantIntTy *High;
  67
  68     RangeT() : Low(0), High(0) {}
  69     RangeT(const RangeT<false> &RHS) : Low(RHS.Low), High(RHS.High) {}
  70     RangeT(ConstantIntTy *C) : Low(C), High(C) {}
  71     RangeT(ConstantIntTy *L, ConstantIntTy *H) : Low(L), High(H) {}
  72
  73     bool operator<(const RangeT &RHS) const {
  74       assert(Low && High && "Case range is not initialized.");
  75       assert(RHS.Low && RHS.High && "Right case range is not initialized.");
  76       const APInt &LowInt = Low->getValue();
  77       const APInt &HighInt = High->getValue();
  78       const APInt &RHSLowInt = RHS.Low->getValue();
  79       const APInt &RHSHighInt = RHS.High->getValue();
  80       if (LowInt.getBitWidth() == RHSLowInt.getBitWidth()) {
  81         if (LowInt.eq(RHSLowInt)) {
  82           if (HighInt.ult(RHSHighInt))
  83             return true;
  84           return false;
  85         }
  86         if (LowInt.ult(RHSLowInt))
  87           return true;
  88         return false;
  89       } else
  90         return LowInt.getBitWidth() < RHSLowInt.getBitWidth();
  91     }
  92
  93     bool operator==(const RangeT &RHS) const {
  94       assert(Low && High && "Case range is not initialized.");
  95       assert(RHS.Low && RHS.High && "Right case range is not initialized.");
  96       if (Low->getValue().getBitWidth() != RHS.Low->getValue().getBitWidth())
  97         return false;
  98       return Low->getValue() == RHS.Low->getValue() &&
  99              High->getValue() == RHS.High->getValue();
 100     }
 101
 102     bool operator!=(const RangeT &RHS) const {
 103       return !operator ==(RHS);
 104     }
 105
 106     static bool LessBySize(const RangeT &LHS, const RangeT &RHS) {
 107       assert(LHS.Low->getBitWidth() == RHS.Low->getBitWidth() &&
 108           "This type of comparison requires equal bit width for LHS and RHS");
 109       APInt LSize = LHS.High->getValue() - LHS.Low->getValue();
 110       APInt RSize = RHS.High->getValue() - RHS.Low->getValue();;
 111       return LSize.ult(RSize);
 112     }
 113
 114     bool isInRange(const APInt &IntVal) const {
 115       assert(Low && High && "Case range is not initialized.");
 116       if (IntVal.getBitWidth() != Low->getValue().getBitWidth())
 117         return false;
 118       return IntVal.uge(Low->getValue()) && IntVal.ule(High->getValue());
 119     }
 120
 121     bool isInRange(const ConstantIntTy *CI) const {
 122       const APInt& IntVal = CI->getValue();
 123       return isInRange(IntVal);
 124     }
 125
 126     SubRes sub(const RangeT &RHS) const {
 127       SubRes Res;
 128
 129       // RHS is either more global and includes this range or
 130       // if it doesn't intersected with this range.
 131       if (!isInRange(RHS.Low) && !isInRange(RHS.High)) {
 132
 133         // If RHS more global (it is enough to check
 134         // only one border in this case.
 135         if (RHS.isInRange(Low))
 136           return std::make_pair(RangeT(Low, High), RangeT());
 137
 138         return Res;
 139       }
 140
 141       const APInt& LoInt = Low->getValue();
 142       const APInt& HiInt = High->getValue();
 143       APInt RHSLoInt = RHS.Low->getValue();
 144       APInt RHSHiInt = RHS.High->getValue();
 145       if (LoInt.ult(RHSLoInt)) {
 146         Res.first.Low = Low;
 147         Res.first.High = ConstantIntTy::get(RHS.Low->getContext(), --RHSLoInt);
 148       }
 149       if (HiInt.ugt(RHSHiInt)) {
 150         Res.second.Low = ConstantIntTy::get(RHS.High->getContext(), ++RHSHiInt);
 151         Res.second.High = High;
 152       }
 153       return Res;
 154     }
 155   };
 156
 157   typedef RangeT<false> Range;
 158
 159   /// Checks is the given constant satisfies this case. Returns
 160   /// true if it equals to one of contained values or belongs to the one of
 161   /// contained ranges.
 162   bool isSatisfies(const ConstantInt *C) const {
 163     const APInt &CheckingVal = C->getValue();
 164     for (unsigned i = 0, e = getNumItems(); i < e; ++i) {
 165       const Constant *CV = Array->getAggregateElement(i);
 166       unsigned VecSize = cast<VectorType>(CV->getType())->getNumElements();
 167       switch (VecSize) {
 168       case 1:
 169         if (cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue() ==
 170             CheckingVal)
 171           return true;
 172         break;
 173       case 2: {
 174         const APInt &Lo =
 175             cast<const ConstantInt>(CV->getAggregateElement(0U))->getValue();
 176         const APInt &Hi =
 177             cast<const ConstantInt>(CV->getAggregateElement(1))->getValue();
 178         if (Lo.uge(CheckingVal) && Hi.ule(CheckingVal))
 179           return true;
 180       }
 181         break;
 182       default:
 183         assert(0 && "Only pairs and single numbers are allowed here.");
 184         break;
 185       }
 186     }
 187     return false;
 188   }
 189
 190   /// Returns set's item with given index.
 191   Range getItem(unsigned idx) {
 192     Constant *CV = Array->getAggregateElement(idx);
 193     unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
 194     switch (NumEls) {
 195     case 1:
 196       return Range(cast<ConstantInt>(CV->getAggregateElement(0U)),
 197                    cast<ConstantInt>(CV->getAggregateElement(0U)));
 198     case 2:
 199       return Range(cast<ConstantInt>(CV->getAggregateElement(0U)),
 200                    cast<ConstantInt>(CV->getAggregateElement(1)));
 201     default:
 202       assert(0 && "Only pairs and single numbers are allowed here.");
 203       return Range();
 204     }
 205   }
 206
 207   const Range getItem(unsigned idx) const {
 208     const Constant *CV = Array->getAggregateElement(idx);
 209
 210     unsigned NumEls = cast<VectorType>(CV->getType())->getNumElements();
 211     switch (NumEls) {
 212     case 1:
 213       return Range(cast<ConstantInt>(
 214                      const_cast<Constant*>(CV->getAggregateElement(0U))),
 215                    cast<ConstantInt>(
 216                      const_cast<Constant*>(CV->getAggregateElement(0U))));
 217     case 2:
 218       return Range(cast<ConstantInt>(
 219                      const_cast<Constant*>(CV->getAggregateElement(0U))),
 220                    cast<ConstantInt>(
 221                      const_cast<Constant*>(CV->getAggregateElement(1))));
 222     default:
 223       assert(0 && "Only pairs and single numbers are allowed here.");
 224       return Range();
 225     }
 226   }
 227
 228   /// Return number of items (ranges) stored in set.
 229   unsigned getNumItems() const {
 230     return cast<ArrayType>(Array->getType())->getNumElements();
 231   }
 232
 233   /// Returns set the size, that equals number of all values + sizes of all
 234   /// ranges.
 235   /// Ranges set is considered as flat numbers collection.
 236   /// E.g.: for range [<0>, <1>, <4,8>] the size will 7;
 237   ///       for range [<0>, <1>, <5>] the size will 3
 238   unsigned getSize() const {
 239     APInt sz(getItem(0).Low->getBitWidth(), 0);
 240     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
 241       const APInt &S = getItem(i).High->getValue() - getItem(i).Low->getValue();
 242       sz += S;
 243     }
 244     return sz.getZExtValue();
 245   }
 246
 247   /// Allows to access single value even if it belongs to some range.
 248   /// Ranges set is considered as flat numbers collection.
 249   /// [<1>, <4,8>] is considered as [1,4,5,6,7,8]
 250   /// For range [<1>, <4,8>] getSingleValue(3) returns 6.
 251   APInt getSingleValue(unsigned idx) const {
 252     APInt sz(getItem(0).Low->getBitWidth(), 0);
 253     for (unsigned i = 0, e = getNumItems(); i != e; ++i) {
 254       const APInt& S = getItem(i).High->getValue() - getItem(i).Low->getValue();
 255       APInt oldSz = sz;
 256       sz += S;
 257       if (oldSz.uge(i) && sz.ult(i)) {
 258         APInt Res = getItem(i).Low->getValue();
 259         APInt Offset(oldSz.getBitWidth(), i);
 260         Offset -= oldSz;
 261         Res += Offset;
 262         return Res;
 263       }
 264     }
 265     assert(0 && "Index exceeds high border.");
 266     return sz;
 267   }
 268 };
 269
 270 }
 271
 272 #endif /* CONSTANTRANGESSET_H_ */