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/Instruction.h"
  26 #include "llvm/Instructions.h"
  27 #include "llvm/Type.h"
  28 #include "llvm/DerivedTypes.h"
  29 #include "llvm/Support/Streams.h"
  30 #include <ostream>
  31 using namespace llvm;
  32
  33 /// Initialize a full (the default) or empty set for the specified type.
  34 ///
  35 ConstantRange::ConstantRange(const Type *Ty, bool Full) :
  36   Lower(cast<IntegerType>(Ty)->getBitWidth(), 0),
  37   Upper(cast<IntegerType>(Ty)->getBitWidth(), 0) {
  38   uint32_t BitWidth = cast<IntegerType>(Ty)->getBitWidth();
  39   if (Full)
  40     Lower = Upper = APInt::getMaxValue(BitWidth);
  41   else
  42     Lower = Upper = APInt::getMinValue(BitWidth);
  43 }
  44
  45 /// Initialize a range to hold the single specified value.
  46 ///
  47 ConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) { }
  48
  49 ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
  50   Lower(L), Upper(U) {
  51   assert(L.getBitWidth() == U.getBitWidth() &&
  52          "ConstantRange with unequal bit widths");
  53   uint32_t BitWidth = L.getBitWidth();
  54   assert((L != U || (L == APInt::getMaxValue(BitWidth) ||
  55                      L == APInt::getMinValue(BitWidth))) &&
  56          "Lower == Upper, but they aren't min or max value!");
  57 }
  58
  59 /// Initialize a set of values that all satisfy the condition with C.
  60 ///
  61 ConstantRange::ConstantRange(unsigned short ICmpOpcode, const APInt &C)
  62   : Lower(C.getBitWidth(), 0), Upper(C.getBitWidth(), 0) {
  63   uint32_t BitWidth = C.getBitWidth();
  64   switch (ICmpOpcode) {
  65   default: assert(0 && "Invalid ICmp opcode to ConstantRange ctor!");
  66   case ICmpInst::ICMP_EQ: Lower = C; Upper = C + 1; return;
  67   case ICmpInst::ICMP_NE: Upper = C; Lower = C + 1; return;
  68   case ICmpInst::ICMP_ULT:
  69     Lower = APInt::getMinValue(BitWidth);
  70     Upper = C;
  71     return;
  72   case ICmpInst::ICMP_SLT:
  73     Lower = APInt::getSignedMinValue(BitWidth);
  74     Upper = C;
  75     return;
  76   case ICmpInst::ICMP_UGT:
  77     Lower = C + 1;
  78     Upper = APInt::getMinValue(BitWidth);        // Min = Next(Max)
  79     return;
  80   case ICmpInst::ICMP_SGT:
  81     Lower = C + 1;
  82     Upper = APInt::getSignedMinValue(BitWidth);  // Min = Next(Max)
  83     return;
  84   case ICmpInst::ICMP_ULE:
  85     Lower = APInt::getMinValue(BitWidth);
  86     Upper = C + 1;
  87     return;
  88   case ICmpInst::ICMP_SLE:
  89     Lower = APInt::getSignedMinValue(BitWidth);
  90     Upper = C + 1;
  91     return;
  92   case ICmpInst::ICMP_UGE:
  93     Lower = C;
  94     Upper = APInt::getMinValue(BitWidth);        // Min = Next(Max)
  95     return;
  96   case ICmpInst::ICMP_SGE:
  97     Lower = C;
  98     Upper = APInt::getSignedMinValue(BitWidth);  // Min = Next(Max)
  99     return;
 100   }
 101 }
 102
 103 /// getType - Return the LLVM data type of this range.
 104 ///
 105 const Type *ConstantRange::getType() const {
 106   return IntegerType::get(Lower.getBitWidth());
 107 }
 108
 109 /// isFullSet - Return true if this set contains all of the elements possible
 110 /// for this data-type
 111 bool ConstantRange::isFullSet() const {
 112   return Lower == Upper && Lower == APInt::getMaxValue(Lower.getBitWidth());
 113 }
 114
 115 /// isEmptySet - Return true if this set contains no members.
 116 ///
 117 bool ConstantRange::isEmptySet() const {
 118   return Lower == Upper && Lower == APInt::getMinValue(Lower.getBitWidth());
 119 }
 120
 121 /// isWrappedSet - Return true if this set wraps around the top of the range,
 122 /// for example: [100, 8)
 123 ///
 124 bool ConstantRange::isWrappedSet(bool isSigned) const {
 125   if (isSigned)
 126     return Lower.sgt(Upper);
 127   return Lower.ugt(Upper);
 128 }
 129
 130 /// getSetSize - Return the number of elements in this set.
 131 ///
 132 APInt ConstantRange::getSetSize() const {
 133   if (isEmptySet())
 134     return APInt(Lower.getBitWidth(), 0);
 135   if (getType() == Type::Int1Ty) {
 136     if (Lower != Upper)  // One of T or F in the set...
 137       return APInt(Lower.getBitWidth(), 1);
 138     return APInt(Lower.getBitWidth(), 2);      // Must be full set...
 139   }
 140
 141   // Simply subtract the bounds...
 142   return Upper - Lower;
 143 }
 144
 145 /// contains - Return true if the specified value is in the set.
 146 ///
 147 bool ConstantRange::contains(const APInt &V, bool isSigned) const {
 148   if (Lower == Upper) {
 149     if (isFullSet())
 150       return true;
 151     return false;
 152   }
 153
 154   if (!isWrappedSet(isSigned))
 155     if (isSigned)
 156       return Lower.sle(V) && V.slt(Upper);
 157     else
 158       return Lower.ule(V) && V.ult(Upper);
 159   if (isSigned)
 160     return Lower.sle(V) || V.slt(Upper);
 161   else
 162     return Lower.ule(V) || V.ult(Upper);
 163 }
 164
 165 /// subtract - Subtract the specified constant from the endpoints of this
 166 /// constant range.
 167 ConstantRange ConstantRange::subtract(const APInt &Val) const {
 168   assert(Val.getBitWidth() == Lower.getBitWidth() && "Wrong bit width");
 169   // If the set is empty or full, don't modify the endpoints.
 170   if (Lower == Upper)
 171     return *this;
 172   return ConstantRange(Lower - Val, Upper - Val);
 173 }
 174
 175
 176 // intersect1Wrapped - This helper function is used to intersect two ranges when
 177 // it is known that LHS is wrapped and RHS isn't.
 178 //
 179 ConstantRange
 180 ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
 181                                  const ConstantRange &RHS, bool isSigned) {
 182   assert(LHS.isWrappedSet(isSigned) && !RHS.isWrappedSet(isSigned));
 183
 184   // Check to see if we overlap on the Left side of RHS...
 185   //
 186   bool LT = (isSigned ? RHS.Lower.slt(LHS.Upper) : RHS.Lower.ult(LHS.Upper));
 187   bool GT = (isSigned ? RHS.Upper.sgt(LHS.Lower) : RHS.Upper.ugt(LHS.Lower));
 188   if (LT) {
 189     // We do overlap on the left side of RHS, see if we overlap on the right of
 190     // RHS...
 191     if (GT) {
 192       // Ok, the result overlaps on both the left and right sides.  See if the
 193       // resultant interval will be smaller if we wrap or not...
 194       //
 195       if (LHS.getSetSize().ult(RHS.getSetSize()))
 196         return LHS;
 197       else
 198         return RHS;
 199
 200     } else {
 201       // No overlap on the right, just on the left.
 202       return ConstantRange(RHS.Lower, LHS.Upper);
 203     }
 204   } else {
 205     // We don't overlap on the left side of RHS, see if we overlap on the right
 206     // of RHS...
 207     if (GT) {
 208       // Simple overlap...
 209       return ConstantRange(LHS.Lower, RHS.Upper);
 210     } else {
 211       // No overlap...
 212       return ConstantRange(LHS.getType(), false);
 213     }
 214   }
 215 }
 216
 217 /// intersectWith - Return the range that results from the intersection of this
 218 /// range with another range.
 219 ///
 220 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR,
 221                                            bool isSigned) const {
 222   assert(getType() == CR.getType() && "ConstantRange types don't agree!");
 223   // Handle common special cases
 224   if (isEmptySet() || CR.isFullSet())
 225     return *this;
 226   if (isFullSet()  || CR.isEmptySet())
 227     return CR;
 228
 229   if (!isWrappedSet(isSigned)) {
 230     if (!CR.isWrappedSet(isSigned)) {
 231       using namespace APIntOps;
 232       APInt L = isSigned ? smax(Lower, CR.Lower) : umax(Lower, CR.Lower);
 233       APInt U = isSigned ? smin(Upper, CR.Upper) : umin(Upper, CR.Upper);
 234
 235       if (isSigned ? L.slt(U) : L.ult(U)) // If range isn't empty...
 236         return ConstantRange(L, U);
 237       else
 238         return ConstantRange(getType(), false);  // Otherwise, return empty set
 239     } else
 240       return intersect1Wrapped(CR, *this, isSigned);
 241   } else {   // We know "this" is wrapped...
 242     if (!CR.isWrappedSet(isSigned))
 243       return intersect1Wrapped(*this, CR, isSigned);
 244     else {
 245       // Both ranges are wrapped...
 246       using namespace APIntOps;
 247       APInt L = isSigned ? smax(Lower, CR.Lower) : umax(Lower, CR.Lower);
 248       APInt U = isSigned ? smin(Upper, CR.Upper) : umin(Upper, CR.Upper);
 249       return ConstantRange(L, U);
 250     }
 251   }
 252   return *this;
 253 }
 254
 255 /// unionWith - Return the range that results from the union of this range with
 256 /// another range.  The resultant range is guaranteed to include the elements of
 257 /// both sets, but may contain more.  For example, [3, 9) union [12,15) is [3,
 258 /// 15), which includes 9, 10, and 11, which were not included in either set
 259 /// before.
 260 ///
 261 ConstantRange ConstantRange::unionWith(const ConstantRange &CR,
 262                                        bool isSigned) const {
 263   assert(getType() == CR.getType() && "ConstantRange types don't agree!");
 264
 265   assert(0 && "Range union not implemented yet!");
 266
 267   return *this;
 268 }
 269
 270 /// zeroExtend - Return a new range in the specified integer type, which must
 271 /// be strictly larger than the current type.  The returned range will
 272 /// correspond to the possible range of values as if the source range had been
 273 /// zero extended.
 274 ConstantRange ConstantRange::zeroExtend(const Type *Ty) const {
 275   unsigned SrcTySize = Lower.getBitWidth();
 276   unsigned DstTySize = Ty->getPrimitiveSizeInBits();
 277   assert(SrcTySize < DstTySize && "Not a value extension");
 278   if (isFullSet())
 279     // Change a source full set into [0, 1 << 8*numbytes)
 280     return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize));
 281
 282   APInt L = Lower; L.zext(DstTySize);
 283   APInt U = Upper; U.zext(DstTySize);
 284   return ConstantRange(L, U);
 285 }
 286
 287 /// truncate - Return a new range in the specified integer type, which must be
 288 /// strictly smaller than the current type.  The returned range will
 289 /// correspond to the possible range of values as if the source range had been
 290 /// truncated to the specified type.
 291 ConstantRange ConstantRange::truncate(const Type *Ty) const {
 292   unsigned SrcTySize = Lower.getBitWidth();
 293   unsigned DstTySize = Ty->getPrimitiveSizeInBits();
 294   assert(SrcTySize > DstTySize && "Not a value truncation");
 295   APInt Size = APInt::getMaxValue(DstTySize).zext(SrcTySize);
 296   if (isFullSet() || getSetSize().ugt(Size))
 297     return ConstantRange(getType());
 298
 299   APInt L = Lower; L.trunc(DstTySize);
 300   APInt U = Upper; U.trunc(DstTySize);
 301   return ConstantRange(L, U);
 302 }
 303
 304 /// print - Print out the bounds to a stream...
 305 ///
 306 void ConstantRange::print(std::ostream &OS) const {
 307   OS << "[" << Lower.toStringSigned(10) << ","
 308             << Upper.toStringSigned(10) << " )";
 309 }
 310
 311 /// dump - Allow printing from a debugger easily...
 312 ///
 313 void ConstantRange::dump() const {
 314   print(cerr);
 315 }