lib/Support/ConstantRange.cpp

   1 //===-- ConstantRange.cpp - ConstantRange implementation ------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Represent a range of possible values that may occur when the program is run
  11 // for an integral value.  This keeps track of a lower and upper bound for the
  12 // constant, which MAY wrap around the end of the numeric range.  To do this, it
  13 // keeps track of a [lower, upper) bound, which specifies an interval just like
  14 // STL iterators.  When used with boolean values, the following are important
  15 // ranges (other integral ranges use min/max values for special range values):
  16 //
  17 //  [F, F) = {}     = Empty set
  18 //  [T, F) = {T}
  19 //  [F, T) = {F}
  20 //  [T, T) = {F, T} = Full set
  21 //
  22 //===----------------------------------------------------------------------===//
  23
  24 #include "llvm/Support/ConstantRange.h"
  25 #include "llvm/Support/Streams.h"
  26 #include <ostream>
  27 using namespace llvm;
  28
  29 /// Initialize a full (the default) or empty set for the specified type.
  30 ///
  31 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) :
  32   Lower(BitWidth, 0), Upper(BitWidth, 0) {
  33   if (Full)
  34     Lower = Upper = APInt::getMaxValue(BitWidth);
  35   else
  36     Lower = Upper = APInt::getMinValue(BitWidth);
  37 }
  38
  39 /// Initialize a range to hold the single specified value.
  40 ///
  41 ConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) { }
  42
  43 ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
  44   Lower(L), Upper(U) {
  45   assert(L.getBitWidth() == U.getBitWidth() &&
  46          "ConstantRange with unequal bit widths");
  47   uint32_t BitWidth = L.getBitWidth();
  48   assert((L != U || (L == APInt::getMaxValue(BitWidth) ||
  49                      L == APInt::getMinValue(BitWidth))) &&
  50          "Lower == Upper, but they aren't min or max value!");
  51 }
  52
  53 /// isFullSet - Return true if this set contains all of the elements possible
  54 /// for this data-type
  55 bool ConstantRange::isFullSet() const {
  56   return Lower == Upper && Lower == APInt::getMaxValue(getBitWidth());
  57 }
  58
  59 /// isEmptySet - Return true if this set contains no members.
  60 ///
  61 bool ConstantRange::isEmptySet() const {
  62   return Lower == Upper && Lower == APInt::getMinValue(getBitWidth());
  63 }
  64
  65 /// isWrappedSet - Return true if this set wraps around the top of the range,
  66 /// for example: [100, 8)
  67 ///
  68 bool ConstantRange::isWrappedSet() const {
  69   return Lower.ugt(Upper);
  70 }
  71
  72 /// getSetSize - Return the number of elements in this set.
  73 ///
  74 APInt ConstantRange::getSetSize() const {
  75   if (isEmptySet())
  76     return APInt(getBitWidth(), 0);
  77   if (getBitWidth() == 1) {
  78     if (Lower != Upper)  // One of T or F in the set...
  79       return APInt(2, 1);
  80     return APInt(2, 2);      // Must be full set...
  81   }
  82
  83   // Simply subtract the bounds...
  84   return Upper - Lower;
  85 }
  86
  87 /// contains - Return true if the specified value is in the set.
  88 ///
  89 bool ConstantRange::contains(const APInt &V) const {
  90   if (Lower == Upper)
  91     return isFullSet();
  92
  93   if (!isWrappedSet())
  94     return Lower.ule(V) && V.ult(Upper);
  95   else
  96     return Lower.ule(V) || V.ult(Upper);
  97 }
  98
  99 /// subtract - Subtract the specified constant from the endpoints of this
 100 /// constant range.
 101 ConstantRange ConstantRange::subtract(const APInt &Val) const {
 102   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
 103   // If the set is empty or full, don't modify the endpoints.
 104   if (Lower == Upper)
 105     return *this;
 106   return ConstantRange(Lower - Val, Upper - Val);
 107 }
 108
 109
 110 // intersect1Wrapped - This helper function is used to intersect two ranges when
 111 // it is known that LHS is wrapped and RHS isn't.
 112 //
 113 ConstantRange
 114 ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
 115                                  const ConstantRange &RHS) {
 116   assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
 117
 118   // Check to see if we overlap on the Left side of RHS...
 119   //
 120   if (RHS.Lower.ult(LHS.Upper)) {
 121     // We do overlap on the left side of RHS, see if we overlap on the right of
 122     // RHS...
 123     if (RHS.Upper.ugt(LHS.Lower)) {
 124       // Ok, the result overlaps on both the left and right sides.  See if the
 125       // resultant interval will be smaller if we wrap or not...
 126       //
 127       if (LHS.getSetSize().ult(RHS.getSetSize()))
 128         return LHS;
 129       else
 130         return RHS;
 131
 132     } else {
 133       // No overlap on the right, just on the left.
 134       return ConstantRange(RHS.Lower, LHS.Upper);
 135     }
 136   } else {
 137     // We don't overlap on the left side of RHS, see if we overlap on the right
 138     // of RHS...
 139     if (RHS.Upper.ugt(LHS.Lower)) {
 140       // Simple overlap...
 141       return ConstantRange(LHS.Lower, RHS.Upper);
 142     } else {
 143       // No overlap...
 144       return ConstantRange(LHS.getBitWidth(), false);
 145     }
 146   }
 147 }
 148
 149 /// intersectWith - Return the range that results from the intersection of this
 150 /// range with another range.
 151 ///
 152 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
 153   assert(getBitWidth() == CR.getBitWidth() &&
 154          "ConstantRange types don't agree!");
 155   // Handle common special cases
 156   if (isEmptySet() || CR.isFullSet())
 157     return *this;
 158   if (isFullSet()  || CR.isEmptySet())
 159     return CR;
 160
 161   if (!isWrappedSet()) {
 162     if (!CR.isWrappedSet()) {
 163       using namespace APIntOps;
 164       APInt L = umax(Lower, CR.Lower);
 165       APInt U = umin(Upper, CR.Upper);
 166
 167       if (L.ult(U)) // If range isn't empty...
 168         return ConstantRange(L, U);
 169       else
 170         return ConstantRange(getBitWidth(), false);// Otherwise, empty set
 171     } else
 172       return intersect1Wrapped(CR, *this);
 173   } else {   // We know "this" is wrapped...
 174     if (!CR.isWrappedSet())
 175       return intersect1Wrapped(*this, CR);
 176     else {
 177       // Both ranges are wrapped...
 178       using namespace APIntOps;
 179       APInt L = umax(Lower, CR.Lower);
 180       APInt U = umin(Upper, CR.Upper);
 181       return ConstantRange(L, U);
 182     }
 183   }
 184   return *this;
 185 }
 186
 187 /// unionWith - Return the range that results from the union of this range with
 188 /// another range.  The resultant range is guaranteed to include the elements of
 189 /// both sets, but may contain more.  For example, [3, 9) union [12,15) is [3,
 190 /// 15), which includes 9, 10, and 11, which were not included in either set
 191 /// before.
 192 ///
 193 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 194   assert(getBitWidth() == CR.getBitWidth() &&
 195          "ConstantRange types don't agree!");
 196
 197   assert(0 && "Range union not implemented yet!");
 198
 199   return *this;
 200 }
 201
 202 /// zeroExtend - Return a new range in the specified integer type, which must
 203 /// be strictly larger than the current type.  The returned range will
 204 /// correspond to the possible range of values as if the source range had been
 205 /// zero extended.
 206 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
 207   unsigned SrcTySize = getBitWidth();
 208   assert(SrcTySize < DstTySize && "Not a value extension");
 209   if (isFullSet())
 210     // Change a source full set into [0, 1 << 8*numbytes)
 211     return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize));
 212
 213   APInt L = Lower; L.zext(DstTySize);
 214   APInt U = Upper; U.zext(DstTySize);
 215   return ConstantRange(L, U);
 216 }
 217
 218 /// truncate - Return a new range in the specified integer type, which must be
 219 /// strictly smaller than the current type.  The returned range will
 220 /// correspond to the possible range of values as if the source range had been
 221 /// truncated to the specified type.
 222 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
 223   unsigned SrcTySize = getBitWidth();
 224   assert(SrcTySize > DstTySize && "Not a value truncation");
 225   APInt Size = APInt::getMaxValue(DstTySize).zext(SrcTySize);
 226   if (isFullSet() || getSetSize().ugt(Size))
 227     return ConstantRange(DstTySize);
 228
 229   APInt L = Lower; L.trunc(DstTySize);
 230   APInt U = Upper; U.trunc(DstTySize);
 231   return ConstantRange(L, U);
 232 }
 233
 234 /// print - Print out the bounds to a stream...
 235 ///
 236 void ConstantRange::print(std::ostream &OS) const {
 237   OS << "[" << Lower.toStringSigned(10) << ","
 238             << Upper.toStringSigned(10) << " )";
 239 }
 240
 241 /// dump - Allow printing from a debugger easily...
 242 ///
 243 void ConstantRange::dump() const {
 244   print(cerr);
 245 }