lib/Support/ConstantRange.cpp

   1 //===-- ConstantRange.cpp - ConstantRange implementation ------------------===//
   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 // 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/raw_ostream.h"
  26 using namespace llvm;
  27
  28 /// Initialize a full (the default) or empty set for the specified type.
  29 ///
  30 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) {
  31   if (Full)
  32     Lower = Upper = APInt::getMaxValue(BitWidth);
  33   else
  34     Lower = Upper = APInt::getMinValue(BitWidth);
  35 }
  36
  37 /// Initialize a range to hold the single specified value.
  38 ///
  39 ConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) {}
  40
  41 ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
  42   Lower(L), Upper(U) {
  43   assert(L.getBitWidth() == U.getBitWidth() &&
  44          "ConstantRange with unequal bit widths");
  45   assert((L != U || (L.isMaxValue() || L.isMinValue())) &&
  46          "Lower == Upper, but they aren't min or max value!");
  47 }
  48
  49 /// isFullSet - Return true if this set contains all of the elements possible
  50 /// for this data-type
  51 bool ConstantRange::isFullSet() const {
  52   return Lower == Upper && Lower.isMaxValue();
  53 }
  54
  55 /// isEmptySet - Return true if this set contains no members.
  56 ///
  57 bool ConstantRange::isEmptySet() const {
  58   return Lower == Upper && Lower.isMinValue();
  59 }
  60
  61 /// isWrappedSet - Return true if this set wraps around the top of the range,
  62 /// for example: [100, 8)
  63 ///
  64 bool ConstantRange::isWrappedSet() const {
  65   return Lower.ugt(Upper);
  66 }
  67
  68 /// getSetSize - Return the number of elements in this set.
  69 ///
  70 APInt ConstantRange::getSetSize() const {
  71   if (isEmptySet())
  72     return APInt(getBitWidth(), 0);
  73   if (getBitWidth() == 1) {
  74     if (Lower != Upper)  // One of T or F in the set...
  75       return APInt(2, 1);
  76     return APInt(2, 2);      // Must be full set...
  77   }
  78
  79   // Simply subtract the bounds...
  80   return Upper - Lower;
  81 }
  82
  83 /// getUnsignedMax - Return the largest unsigned value contained in the
  84 /// ConstantRange.
  85 ///
  86 APInt ConstantRange::getUnsignedMax() const {
  87   if (isFullSet() || isWrappedSet())
  88     return APInt::getMaxValue(getBitWidth());
  89   else
  90     return getUpper() - 1;
  91 }
  92
  93 /// getUnsignedMin - Return the smallest unsigned value contained in the
  94 /// ConstantRange.
  95 ///
  96 APInt ConstantRange::getUnsignedMin() const {
  97   if (isFullSet() || (isWrappedSet() && getUpper() != 0))
  98     return APInt::getMinValue(getBitWidth());
  99   else
 100     return getLower();
 101 }
 102
 103 /// getSignedMax - Return the largest signed value contained in the
 104 /// ConstantRange.
 105 ///
 106 APInt ConstantRange::getSignedMax() const {
 107   APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
 108   if (!isWrappedSet()) {
 109     if (getLower().sle(getUpper() - 1))
 110       return getUpper() - 1;
 111     else
 112       return SignedMax;
 113   } else {
 114     if ((getUpper() - 1).slt(getLower())) {
 115       if (getLower() != SignedMax)
 116         return SignedMax;
 117       else
 118         return getUpper() - 1;
 119     } else {
 120       return getUpper() - 1;
 121     }
 122   }
 123 }
 124
 125 /// getSignedMin - Return the smallest signed value contained in the
 126 /// ConstantRange.
 127 ///
 128 APInt ConstantRange::getSignedMin() const {
 129   APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
 130   if (!isWrappedSet()) {
 131     if (getLower().sle(getUpper() - 1))
 132       return getLower();
 133     else
 134       return SignedMin;
 135   } else {
 136     if ((getUpper() - 1).slt(getLower())) {
 137       if (getUpper() != SignedMin)
 138         return SignedMin;
 139       else
 140         return getLower();
 141     } else {
 142       return getLower();
 143     }
 144   }
 145 }
 146
 147 /// contains - Return true if the specified value is in the set.
 148 ///
 149 bool ConstantRange::contains(const APInt &V) const {
 150   if (Lower == Upper)
 151     return isFullSet();
 152
 153   if (!isWrappedSet())
 154     return Lower.ule(V) && V.ult(Upper);
 155   else
 156     return Lower.ule(V) || V.ult(Upper);
 157 }
 158
 159 /// subtract - Subtract the specified constant from the endpoints of this
 160 /// constant range.
 161 ConstantRange ConstantRange::subtract(const APInt &Val) const {
 162   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
 163   // If the set is empty or full, don't modify the endpoints.
 164   if (Lower == Upper)
 165     return *this;
 166   return ConstantRange(Lower - Val, Upper - Val);
 167 }
 168
 169
 170 // intersect1Wrapped - This helper function is used to intersect two ranges when
 171 // it is known that LHS is wrapped and RHS isn't.
 172 //
 173 ConstantRange
 174 ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
 175                                  const ConstantRange &RHS) {
 176   assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
 177
 178   // Check to see if we overlap on the Left side of RHS...
 179   //
 180   if (RHS.Lower.ult(LHS.Upper)) {
 181     // We do overlap on the left side of RHS, see if we overlap on the right of
 182     // RHS...
 183     if (RHS.Upper.ugt(LHS.Lower)) {
 184       // Ok, the result overlaps on both the left and right sides.  See if the
 185       // resultant interval will be smaller if we wrap or not...
 186       //
 187       if (LHS.getSetSize().ult(RHS.getSetSize()))
 188         return LHS;
 189       else
 190         return RHS;
 191
 192     } else {
 193       // No overlap on the right, just on the left.
 194       return ConstantRange(RHS.Lower, LHS.Upper);
 195     }
 196   } else {
 197     // We don't overlap on the left side of RHS, see if we overlap on the right
 198     // of RHS...
 199     if (RHS.Upper.ugt(LHS.Lower)) {
 200       // Simple overlap...
 201       return ConstantRange(LHS.Lower, RHS.Upper);
 202     } else {
 203       // No overlap...
 204       return ConstantRange(LHS.getBitWidth(), false);
 205     }
 206   }
 207 }
 208
 209 /// intersectWith - Return the range that results from the intersection of this
 210 /// range with another range.
 211 ///
 212 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
 213   assert(getBitWidth() == CR.getBitWidth() &&
 214          "ConstantRange types don't agree!");
 215   // Handle common special cases
 216   if (isEmptySet() || CR.isFullSet())
 217     return *this;
 218   if (isFullSet()  || CR.isEmptySet())
 219     return CR;
 220
 221   if (!isWrappedSet()) {
 222     if (!CR.isWrappedSet()) {
 223       APInt L = APIntOps::umax(Lower, CR.Lower);
 224       APInt U = APIntOps::umin(Upper, CR.Upper);
 225
 226       if (L.ult(U)) // If range isn't empty...
 227         return ConstantRange(L, U);
 228       else
 229         return ConstantRange(getBitWidth(), false);// Otherwise, empty set
 230     } else
 231       return intersect1Wrapped(CR, *this);
 232   } else {   // We know "this" is wrapped...
 233     if (!CR.isWrappedSet())
 234       return intersect1Wrapped(*this, CR);
 235     else {
 236       // Both ranges are wrapped...
 237       APInt L = APIntOps::umax(Lower, CR.Lower);
 238       APInt U = APIntOps::umin(Upper, CR.Upper);
 239       return ConstantRange(L, U);
 240     }
 241   }
 242   return *this;
 243 }
 244
 245 /// maximalIntersectWith - Return the range that results from the intersection
 246 /// of this range with another range.  The resultant range is guaranteed to
 247 /// include all elements contained in both input ranges, and to have the
 248 /// smallest possible set size that does so.  Because there may be two
 249 /// intersections with the same set size, A.maximalIntersectWith(B) might not
 250 /// be equal to B.maximalIntersect(A).
 251 ConstantRange
 252 ConstantRange::maximalIntersectWith(const ConstantRange &CR) const {
 253   assert(getBitWidth() == CR.getBitWidth() &&
 254          "ConstantRange types don't agree!");
 255
 256   // Handle common cases.
 257   if (   isEmptySet() || CR.isFullSet()) return *this;
 258   if (CR.isEmptySet() ||    isFullSet()) return CR;
 259
 260   if (!isWrappedSet() && CR.isWrappedSet())
 261     return CR.maximalIntersectWith(*this);
 262
 263   if (!isWrappedSet() && !CR.isWrappedSet()) {
 264     if (Lower.ult(CR.Lower)) {
 265       if (Upper.ule(CR.Lower))
 266         return ConstantRange(getBitWidth(), false);
 267
 268       if (Upper.ult(CR.Upper))
 269         return ConstantRange(CR.Lower, Upper);
 270
 271       return CR;
 272     } else {
 273       if (Upper.ult(CR.Upper))
 274         return *this;
 275
 276       if (Lower.ult(CR.Upper))
 277         return ConstantRange(Lower, CR.Upper);
 278
 279       return ConstantRange(getBitWidth(), false);
 280     }
 281   }
 282
 283   if (isWrappedSet() && !CR.isWrappedSet()) {
 284     if (CR.Lower.ult(Upper)) {
 285       if (CR.Upper.ult(Upper))
 286         return CR;
 287
 288       if (CR.Upper.ult(Lower))
 289         return ConstantRange(CR.Lower, Upper);
 290
 291       if (getSetSize().ult(CR.getSetSize()))
 292         return *this;
 293       else
 294         return CR;
 295     } else if (CR.Lower.ult(Lower)) {
 296       if (CR.Upper.ule(Lower))
 297         return ConstantRange(getBitWidth(), false);
 298
 299       return ConstantRange(Lower, CR.Upper);
 300     }
 301     return CR;
 302   }
 303
 304   if (CR.Upper.ult(Upper)) {
 305     if (CR.Lower.ult(Upper)) {
 306       if (getSetSize().ult(CR.getSetSize()))
 307         return *this;
 308       else
 309         return CR;
 310     }
 311
 312     if (CR.Lower.ult(Lower))
 313       return ConstantRange(Lower, CR.Upper);
 314
 315     return CR;
 316   } else if (CR.Upper.ult(Lower)) {
 317     if (CR.Lower.ult(Lower))
 318       return *this;
 319
 320     return ConstantRange(CR.Lower, Upper);
 321   }
 322   if (getSetSize().ult(CR.getSetSize()))
 323     return *this;
 324   else
 325     return CR;
 326 }
 327
 328
 329 /// unionWith - Return the range that results from the union of this range with
 330 /// another range.  The resultant range is guaranteed to include the elements of
 331 /// both sets, but may contain more.  For example, [3, 9) union [12,15) is
 332 /// [3, 15), which includes 9, 10, and 11, which were not included in either
 333 /// set before.
 334 ///
 335 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 336   assert(getBitWidth() == CR.getBitWidth() &&
 337          "ConstantRange types don't agree!");
 338
 339   if (   isFullSet() || CR.isEmptySet()) return *this;
 340   if (CR.isFullSet() ||    isEmptySet()) return CR;
 341
 342   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
 343
 344   APInt L = Lower, U = Upper;
 345
 346   if (!isWrappedSet() && !CR.isWrappedSet()) {
 347     if (CR.Lower.ult(L))
 348       L = CR.Lower;
 349
 350     if (CR.Upper.ugt(U))
 351       U = CR.Upper;
 352   }
 353
 354   if (isWrappedSet() && !CR.isWrappedSet()) {
 355     if ((CR.Lower.ult(Upper) && CR.Upper.ult(Upper)) ||
 356         (CR.Lower.ugt(Lower) && CR.Upper.ugt(Lower))) {
 357       return *this;
 358     }
 359
 360     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) {
 361       return ConstantRange(getBitWidth());
 362     }
 363
 364     if (CR.Lower.ule(Upper) && CR.Upper.ule(Lower)) {
 365       APInt d1 = CR.Upper - Upper, d2 = Lower - CR.Upper;
 366       if (d1.ult(d2)) {
 367         U = CR.Upper;
 368       } else {
 369         L = CR.Upper;
 370       }
 371     }
 372
 373     if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) {
 374       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
 375       if (d1.ult(d2)) {
 376         U = CR.Lower + 1;
 377       } else {
 378         L = CR.Upper - 1;
 379       }
 380     }
 381
 382     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) {
 383       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Lower;
 384
 385       if (d1.ult(d2)) {
 386         U = CR.Lower + 1;
 387       } else {
 388         L = CR.Lower;
 389       }
 390     }
 391   }
 392
 393   if (isWrappedSet() && CR.isWrappedSet()) {
 394     if (Lower.ult(CR.Upper) || CR.Lower.ult(Upper))
 395       return ConstantRange(getBitWidth());
 396
 397     if (CR.Upper.ugt(U)) {
 398       U = CR.Upper;
 399     }
 400
 401     if (CR.Lower.ult(L)) {
 402       L = CR.Lower;
 403     }
 404
 405     if (L == U) return ConstantRange(getBitWidth());
 406   }
 407
 408   return ConstantRange(L, U);
 409 }
 410
 411 /// zeroExtend - Return a new range in the specified integer type, which must
 412 /// be strictly larger than the current type.  The returned range will
 413 /// correspond to the possible range of values as if the source range had been
 414 /// zero extended.
 415 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
 416   unsigned SrcTySize = getBitWidth();
 417   assert(SrcTySize < DstTySize && "Not a value extension");
 418   if (isFullSet())
 419     // Change a source full set into [0, 1 << 8*numbytes)
 420     return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize));
 421
 422   APInt L = Lower; L.zext(DstTySize);
 423   APInt U = Upper; U.zext(DstTySize);
 424   return ConstantRange(L, U);
 425 }
 426
 427 /// signExtend - Return a new range in the specified integer type, which must
 428 /// be strictly larger than the current type.  The returned range will
 429 /// correspond to the possible range of values as if the source range had been
 430 /// sign extended.
 431 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
 432   unsigned SrcTySize = getBitWidth();
 433   assert(SrcTySize < DstTySize && "Not a value extension");
 434   if (isFullSet()) {
 435     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
 436                          APInt::getLowBitsSet(DstTySize, SrcTySize-1));
 437   }
 438
 439   APInt L = Lower; L.sext(DstTySize);
 440   APInt U = Upper; U.sext(DstTySize);
 441   return ConstantRange(L, U);
 442 }
 443
 444 /// truncate - Return a new range in the specified integer type, which must be
 445 /// strictly smaller than the current type.  The returned range will
 446 /// correspond to the possible range of values as if the source range had been
 447 /// truncated to the specified type.
 448 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
 449   unsigned SrcTySize = getBitWidth();
 450   assert(SrcTySize > DstTySize && "Not a value truncation");
 451   APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize));
 452   if (isFullSet() || getSetSize().ugt(Size))
 453     return ConstantRange(DstTySize);
 454
 455   APInt L = Lower; L.trunc(DstTySize);
 456   APInt U = Upper; U.trunc(DstTySize);
 457   return ConstantRange(L, U);
 458 }
 459
 460 ConstantRange
 461 ConstantRange::add(const ConstantRange &Other) const {
 462   if (isEmptySet() || Other.isEmptySet())
 463     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 464
 465   APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
 466   APInt NewLower = getLower() + Other.getLower();
 467   APInt NewUpper = getUpper() + Other.getUpper() - 1;
 468   if (NewLower == NewUpper)
 469     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 470
 471   ConstantRange X = ConstantRange(NewLower, NewUpper);
 472   if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
 473     // We've wrapped, therefore, full set.
 474     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 475
 476   return X;
 477 }
 478
 479 ConstantRange
 480 ConstantRange::multiply(const ConstantRange &Other) const {
 481   // TODO: Implement multiply.
 482   return ConstantRange(getBitWidth(),
 483                        !(isEmptySet() || Other.isEmptySet()));
 484 }
 485
 486 ConstantRange
 487 ConstantRange::smax(const ConstantRange &Other) const {
 488   // X smax Y is: range(smax(X_smin, Y_smin),
 489   //                    smax(X_smax, Y_smax))
 490   if (isEmptySet() || Other.isEmptySet())
 491     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 492   if (isFullSet() || Other.isFullSet())
 493     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 494   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
 495   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
 496   if (NewU == NewL)
 497     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 498   return ConstantRange(NewL, NewU);
 499 }
 500
 501 ConstantRange
 502 ConstantRange::umax(const ConstantRange &Other) const {
 503   // X umax Y is: range(umax(X_umin, Y_umin),
 504   //                    umax(X_umax, Y_umax))
 505   if (isEmptySet() || Other.isEmptySet())
 506     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 507   if (isFullSet() || Other.isFullSet())
 508     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 509   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
 510   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
 511   if (NewU == NewL)
 512     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 513   return ConstantRange(NewL, NewU);
 514 }
 515
 516 ConstantRange
 517 ConstantRange::udiv(const ConstantRange &Other) const {
 518   // TODO: Implement udiv.
 519   return ConstantRange(getBitWidth(),
 520                        !(isEmptySet() || Other.isEmptySet()));
 521 }
 522
 523 /// print - Print out the bounds to a stream...
 524 ///
 525 void ConstantRange::print(raw_ostream &OS) const {
 526   OS << "[" << Lower << "," << Upper << ")";
 527 }
 528
 529 /// dump - Allow printing from a debugger easily...
 530 ///
 531 void ConstantRange::dump() const {
 532   print(errs());
 533 }
 534
 535 std::ostream &llvm::operator<<(std::ostream &o,
 536                                const ConstantRange &CR) {
 537   raw_os_ostream OS(o);
 538   OS << CR;
 539   return o;
 540 }