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