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 range to hold the single specified value.
  29 ///
  30 ConstantRangeBase::ConstantRangeBase(const APInt & V)
  31   : Lower(V), Upper(V + 1) {}
  32
  33 ConstantRangeBase::ConstantRangeBase(const APInt &L, const APInt &U)
  34   : Lower(L), Upper(U) {
  35   assert(L.getBitWidth() == U.getBitWidth() &&
  36          "ConstantRange with unequal bit widths");
  37 }
  38
  39 /// print - Print out the bounds to a stream...
  40 ///
  41 void ConstantRangeBase::print(raw_ostream &OS) const {
  42   OS << "[" << Lower << "," << Upper << ")";
  43 }
  44
  45 /// dump - Allow printing from a debugger easily...
  46 ///
  47 void ConstantRangeBase::dump() const {
  48   print(errs());
  49 }
  50
  51 std::ostream &llvm::operator<<(std::ostream &o,
  52                                const ConstantRangeBase &CR) {
  53   raw_os_ostream OS(o);
  54   OS << CR;
  55   return o;
  56 }
  57
  58 /// Initialize a full (the default) or empty set for the specified type.
  59 ///
  60 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) :
  61   ConstantRangeBase(APInt(BitWidth, 0), APInt(BitWidth, 0)) {
  62   if (Full)
  63     Lower = Upper = APInt::getMaxValue(BitWidth);
  64   else
  65     Lower = Upper = APInt::getMinValue(BitWidth);
  66 }
  67
  68 /// Initialize a range to hold the single specified value.
  69 ///
  70 ConstantRange::ConstantRange(const APInt & V) : ConstantRangeBase(V) {}
  71
  72 ConstantRange::ConstantRange(const APInt &L, const APInt &U)
  73   : ConstantRangeBase(L, U) {
  74   assert((L != U || (L.isMaxValue() || L.isMinValue())) &&
  75          "Lower == Upper, but they aren't min or max value!");
  76 }
  77
  78 /// isFullSet - Return true if this set contains all of the elements possible
  79 /// for this data-type
  80 bool ConstantRange::isFullSet() const {
  81   return Lower == Upper && Lower.isMaxValue();
  82 }
  83
  84 /// isEmptySet - Return true if this set contains no members.
  85 ///
  86 bool ConstantRange::isEmptySet() const {
  87   return Lower == Upper && Lower.isMinValue();
  88 }
  89
  90 /// isWrappedSet - Return true if this set wraps around the top of the range,
  91 /// for example: [100, 8)
  92 ///
  93 bool ConstantRange::isWrappedSet() const {
  94   return Lower.ugt(Upper);
  95 }
  96
  97 /// getSetSize - Return the number of elements in this set.
  98 ///
  99 APInt ConstantRange::getSetSize() const {
 100   if (isEmptySet())
 101     return APInt(getBitWidth(), 0);
 102   if (getBitWidth() == 1) {
 103     if (Lower != Upper)  // One of T or F in the set...
 104       return APInt(2, 1);
 105     return APInt(2, 2);      // Must be full set...
 106   }
 107
 108   // Simply subtract the bounds...
 109   return Upper - Lower;
 110 }
 111
 112 /// getUnsignedMax - Return the largest unsigned value contained in the
 113 /// ConstantRange.
 114 ///
 115 APInt ConstantRange::getUnsignedMax() const {
 116   if (isFullSet() || isWrappedSet())
 117     return APInt::getMaxValue(getBitWidth());
 118   else
 119     return getUpper() - 1;
 120 }
 121
 122 /// getUnsignedMin - Return the smallest unsigned value contained in the
 123 /// ConstantRange.
 124 ///
 125 APInt ConstantRange::getUnsignedMin() const {
 126   if (isFullSet() || (isWrappedSet() && getUpper() != 0))
 127     return APInt::getMinValue(getBitWidth());
 128   else
 129     return getLower();
 130 }
 131
 132 /// getSignedMax - Return the largest signed value contained in the
 133 /// ConstantRange.
 134 ///
 135 APInt ConstantRange::getSignedMax() const {
 136   APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
 137   if (!isWrappedSet()) {
 138     if (getLower().sle(getUpper() - 1))
 139       return getUpper() - 1;
 140     else
 141       return SignedMax;
 142   } else {
 143     if ((getUpper() - 1).slt(getLower())) {
 144       if (getLower() != SignedMax)
 145         return SignedMax;
 146       else
 147         return getUpper() - 1;
 148     } else {
 149       return getUpper() - 1;
 150     }
 151   }
 152 }
 153
 154 /// getSignedMin - Return the smallest signed value contained in the
 155 /// ConstantRange.
 156 ///
 157 APInt ConstantRange::getSignedMin() const {
 158   APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
 159   if (!isWrappedSet()) {
 160     if (getLower().sle(getUpper() - 1))
 161       return getLower();
 162     else
 163       return SignedMin;
 164   } else {
 165     if ((getUpper() - 1).slt(getLower())) {
 166       if (getUpper() != SignedMin)
 167         return SignedMin;
 168       else
 169         return getLower();
 170     } else {
 171       return getLower();
 172     }
 173   }
 174 }
 175
 176 /// contains - Return true if the specified value is in the set.
 177 ///
 178 bool ConstantRange::contains(const APInt &V) const {
 179   if (Lower == Upper)
 180     return isFullSet();
 181
 182   if (!isWrappedSet())
 183     return Lower.ule(V) && V.ult(Upper);
 184   else
 185     return Lower.ule(V) || V.ult(Upper);
 186 }
 187
 188 /// subtract - Subtract the specified constant from the endpoints of this
 189 /// constant range.
 190 ConstantRange ConstantRange::subtract(const APInt &Val) const {
 191   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
 192   // If the set is empty or full, don't modify the endpoints.
 193   if (Lower == Upper)
 194     return *this;
 195   return ConstantRange(Lower - Val, Upper - Val);
 196 }
 197
 198
 199 // intersect1Wrapped - This helper function is used to intersect two ranges when
 200 // it is known that LHS is wrapped and RHS isn't.
 201 //
 202 ConstantRange
 203 ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
 204                                  const ConstantRange &RHS) {
 205   assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
 206
 207   // Check to see if we overlap on the Left side of RHS...
 208   //
 209   if (RHS.Lower.ult(LHS.Upper)) {
 210     // We do overlap on the left side of RHS, see if we overlap on the right of
 211     // RHS...
 212     if (RHS.Upper.ugt(LHS.Lower)) {
 213       // Ok, the result overlaps on both the left and right sides.  See if the
 214       // resultant interval will be smaller if we wrap or not...
 215       //
 216       if (LHS.getSetSize().ult(RHS.getSetSize()))
 217         return LHS;
 218       else
 219         return RHS;
 220
 221     } else {
 222       // No overlap on the right, just on the left.
 223       return ConstantRange(RHS.Lower, LHS.Upper);
 224     }
 225   } else {
 226     // We don't overlap on the left side of RHS, see if we overlap on the right
 227     // of RHS...
 228     if (RHS.Upper.ugt(LHS.Lower)) {
 229       // Simple overlap...
 230       return ConstantRange(LHS.Lower, RHS.Upper);
 231     } else {
 232       // No overlap...
 233       return ConstantRange(LHS.getBitWidth(), false);
 234     }
 235   }
 236 }
 237
 238 /// intersectWith - Return the range that results from the intersection of this
 239 /// range with another range.
 240 ///
 241 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
 242   assert(getBitWidth() == CR.getBitWidth() &&
 243          "ConstantRange types don't agree!");
 244   // Handle common special cases
 245   if (isEmptySet() || CR.isFullSet())
 246     return *this;
 247   if (isFullSet()  || CR.isEmptySet())
 248     return CR;
 249
 250   if (!isWrappedSet()) {
 251     if (!CR.isWrappedSet()) {
 252       APInt L = APIntOps::umax(Lower, CR.Lower);
 253       APInt U = APIntOps::umin(Upper, CR.Upper);
 254
 255       if (L.ult(U)) // If range isn't empty...
 256         return ConstantRange(L, U);
 257       else
 258         return ConstantRange(getBitWidth(), false);// Otherwise, empty set
 259     } else
 260       return intersect1Wrapped(CR, *this);
 261   } else {   // We know "this" is wrapped...
 262     if (!CR.isWrappedSet())
 263       return intersect1Wrapped(*this, CR);
 264     else {
 265       // Both ranges are wrapped...
 266       APInt L = APIntOps::umax(Lower, CR.Lower);
 267       APInt U = APIntOps::umin(Upper, CR.Upper);
 268       return ConstantRange(L, U);
 269     }
 270   }
 271   return *this;
 272 }
 273
 274 /// maximalIntersectWith - Return the range that results from the intersection
 275 /// of this range with another range.  The resultant range is guaranteed to
 276 /// include all elements contained in both input ranges, and to have the
 277 /// smallest possible set size that does so.  Because there may be two
 278 /// intersections with the same set size, A.maximalIntersectWith(B) might not
 279 /// be equal to B.maximalIntersect(A).
 280 ConstantRange
 281 ConstantRange::maximalIntersectWith(const ConstantRange &CR) const {
 282   assert(getBitWidth() == CR.getBitWidth() &&
 283          "ConstantRange types don't agree!");
 284
 285   // Handle common cases.
 286   if (   isEmptySet() || CR.isFullSet()) return *this;
 287   if (CR.isEmptySet() ||    isFullSet()) return CR;
 288
 289   if (!isWrappedSet() && CR.isWrappedSet())
 290     return CR.maximalIntersectWith(*this);
 291
 292   if (!isWrappedSet() && !CR.isWrappedSet()) {
 293     if (Lower.ult(CR.Lower)) {
 294       if (Upper.ule(CR.Lower))
 295         return ConstantRange(getBitWidth(), false);
 296
 297       if (Upper.ult(CR.Upper))
 298         return ConstantRange(CR.Lower, Upper);
 299
 300       return CR;
 301     } else {
 302       if (Upper.ult(CR.Upper))
 303         return *this;
 304
 305       if (Lower.ult(CR.Upper))
 306         return ConstantRange(Lower, CR.Upper);
 307
 308       return ConstantRange(getBitWidth(), false);
 309     }
 310   }
 311
 312   if (isWrappedSet() && !CR.isWrappedSet()) {
 313     if (CR.Lower.ult(Upper)) {
 314       if (CR.Upper.ult(Upper))
 315         return CR;
 316
 317       if (CR.Upper.ult(Lower))
 318         return ConstantRange(CR.Lower, Upper);
 319
 320       if (getSetSize().ult(CR.getSetSize()))
 321         return *this;
 322       else
 323         return CR;
 324     } else if (CR.Lower.ult(Lower)) {
 325       if (CR.Upper.ule(Lower))
 326         return ConstantRange(getBitWidth(), false);
 327
 328       return ConstantRange(Lower, CR.Upper);
 329     }
 330     return CR;
 331   }
 332
 333   if (CR.Upper.ult(Upper)) {
 334     if (CR.Lower.ult(Upper)) {
 335       if (getSetSize().ult(CR.getSetSize()))
 336         return *this;
 337       else
 338         return CR;
 339     }
 340
 341     if (CR.Lower.ult(Lower))
 342       return ConstantRange(Lower, CR.Upper);
 343
 344     return CR;
 345   } else if (CR.Upper.ult(Lower)) {
 346     if (CR.Lower.ult(Lower))
 347       return *this;
 348
 349     return ConstantRange(CR.Lower, Upper);
 350   }
 351   if (getSetSize().ult(CR.getSetSize()))
 352     return *this;
 353   else
 354     return CR;
 355 }
 356
 357
 358 /// unionWith - Return the range that results from the union of this range with
 359 /// another range.  The resultant range is guaranteed to include the elements of
 360 /// both sets, but may contain more.  For example, [3, 9) union [12,15) is
 361 /// [3, 15), which includes 9, 10, and 11, which were not included in either
 362 /// set before.
 363 ///
 364 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 365   assert(getBitWidth() == CR.getBitWidth() &&
 366          "ConstantRange types don't agree!");
 367
 368   if (   isFullSet() || CR.isEmptySet()) return *this;
 369   if (CR.isFullSet() ||    isEmptySet()) return CR;
 370
 371   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
 372
 373   APInt L = Lower, U = Upper;
 374
 375   if (!isWrappedSet() && !CR.isWrappedSet()) {
 376     if (CR.Lower.ult(L))
 377       L = CR.Lower;
 378
 379     if (CR.Upper.ugt(U))
 380       U = CR.Upper;
 381   }
 382
 383   if (isWrappedSet() && !CR.isWrappedSet()) {
 384     if ((CR.Lower.ult(Upper) && CR.Upper.ult(Upper)) ||
 385         (CR.Lower.ugt(Lower) && CR.Upper.ugt(Lower))) {
 386       return *this;
 387     }
 388
 389     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) {
 390       return ConstantRange(getBitWidth());
 391     }
 392
 393     if (CR.Lower.ule(Upper) && CR.Upper.ule(Lower)) {
 394       APInt d1 = CR.Upper - Upper, d2 = Lower - CR.Upper;
 395       if (d1.ult(d2)) {
 396         U = CR.Upper;
 397       } else {
 398         L = CR.Upper;
 399       }
 400     }
 401
 402     if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) {
 403       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
 404       if (d1.ult(d2)) {
 405         U = CR.Lower + 1;
 406       } else {
 407         L = CR.Upper - 1;
 408       }
 409     }
 410
 411     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) {
 412       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Lower;
 413
 414       if (d1.ult(d2)) {
 415         U = CR.Lower + 1;
 416       } else {
 417         L = CR.Lower;
 418       }
 419     }
 420   }
 421
 422   if (isWrappedSet() && CR.isWrappedSet()) {
 423     if (Lower.ult(CR.Upper) || CR.Lower.ult(Upper))
 424       return ConstantRange(getBitWidth());
 425
 426     if (CR.Upper.ugt(U)) {
 427       U = CR.Upper;
 428     }
 429
 430     if (CR.Lower.ult(L)) {
 431       L = CR.Lower;
 432     }
 433
 434     if (L == U) return ConstantRange(getBitWidth());
 435   }
 436
 437   return ConstantRange(L, U);
 438 }
 439
 440 /// zeroExtend - Return a new range in the specified integer type, which must
 441 /// be strictly larger than the current type.  The returned range will
 442 /// correspond to the possible range of values as if the source range had been
 443 /// zero extended.
 444 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
 445   unsigned SrcTySize = getBitWidth();
 446   assert(SrcTySize < DstTySize && "Not a value extension");
 447   if (isFullSet())
 448     // Change a source full set into [0, 1 << 8*numbytes)
 449     return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize));
 450
 451   APInt L = Lower; L.zext(DstTySize);
 452   APInt U = Upper; U.zext(DstTySize);
 453   return ConstantRange(L, U);
 454 }
 455
 456 /// signExtend - Return a new range in the specified integer type, which must
 457 /// be strictly larger than the current type.  The returned range will
 458 /// correspond to the possible range of values as if the source range had been
 459 /// sign extended.
 460 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
 461   unsigned SrcTySize = getBitWidth();
 462   assert(SrcTySize < DstTySize && "Not a value extension");
 463   if (isFullSet()) {
 464     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
 465                          APInt::getLowBitsSet(DstTySize, SrcTySize-1));
 466   }
 467
 468   APInt L = Lower; L.sext(DstTySize);
 469   APInt U = Upper; U.sext(DstTySize);
 470   return ConstantRange(L, U);
 471 }
 472
 473 /// truncate - Return a new range in the specified integer type, which must be
 474 /// strictly smaller than the current type.  The returned range will
 475 /// correspond to the possible range of values as if the source range had been
 476 /// truncated to the specified type.
 477 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
 478   unsigned SrcTySize = getBitWidth();
 479   assert(SrcTySize > DstTySize && "Not a value truncation");
 480   APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize));
 481   if (isFullSet() || getSetSize().ugt(Size))
 482     return ConstantRange(DstTySize);
 483
 484   APInt L = Lower; L.trunc(DstTySize);
 485   APInt U = Upper; U.trunc(DstTySize);
 486   return ConstantRange(L, U);
 487 }
 488
 489 ConstantRange
 490 ConstantRange::add(const ConstantRange &Other) const {
 491   if (isEmptySet() || Other.isEmptySet())
 492     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 493
 494   APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
 495   APInt NewLower = getLower() + Other.getLower();
 496   APInt NewUpper = getUpper() + Other.getUpper() - 1;
 497   if (NewLower == NewUpper)
 498     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 499
 500   ConstantRange X = ConstantRange(NewLower, NewUpper);
 501   if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
 502     // We've wrapped, therefore, full set.
 503     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 504
 505   return X;
 506 }
 507
 508 ConstantRange
 509 ConstantRange::multiply(const ConstantRange &Other) const {
 510   // TODO: Implement multiply.
 511   return ConstantRange(getBitWidth(),
 512                        !(isEmptySet() || Other.isEmptySet()));
 513 }
 514
 515 ConstantRange
 516 ConstantRange::smax(const ConstantRange &Other) const {
 517   // TODO: Implement smax.
 518   return ConstantRange(getBitWidth(),
 519                        !(isEmptySet() || Other.isEmptySet()));
 520 }
 521
 522 ConstantRange
 523 ConstantRange::umax(const ConstantRange &Other) const {
 524   // X umax Y is: range(umax(X_umin, Y_umin),
 525   //                    umax(X_umax, Y_umax))
 526   if (isEmptySet() || Other.isEmptySet())
 527     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 528   if (isFullSet() || Other.isFullSet())
 529     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 530   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
 531   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
 532   if (NewU == NewL)
 533     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 534   return ConstantRange(NewL, NewU);
 535 }
 536
 537 ConstantRange
 538 ConstantRange::udiv(const ConstantRange &Other) const {
 539   // TODO: Implement udiv.
 540   return ConstantRange(getBitWidth(),
 541                        !(isEmptySet() || Other.isEmptySet()));
 542 }
 543
 544 /// Initialize a full (the default) or empty set for the specified type.
 545 ///
 546 ConstantSignedRange::ConstantSignedRange(uint32_t BitWidth, bool Full) :
 547   ConstantRangeBase(APInt(BitWidth, 0), APInt(BitWidth, 0)) {
 548   if (Full)
 549     Lower = Upper = APInt::getSignedMaxValue(BitWidth);
 550   else
 551     Lower = Upper = APInt::getSignedMinValue(BitWidth);
 552 }
 553
 554 /// Initialize a range to hold the single specified value.
 555 ///
 556 ConstantSignedRange::ConstantSignedRange(const APInt & V)
 557   : ConstantRangeBase(V) {}
 558
 559 ConstantSignedRange::ConstantSignedRange(const APInt &L, const APInt &U)
 560   : ConstantRangeBase(L, U) {
 561   assert((L != U || (L.isMaxSignedValue() || L.isMinSignedValue())) &&
 562          "Lower == Upper, but they aren't min or max value!");
 563 }
 564
 565 /// isFullSet - Return true if this set contains all of the elements possible
 566 /// for this data-type
 567 bool ConstantSignedRange::isFullSet() const {
 568   return Lower == Upper && Lower.isMaxSignedValue();
 569 }
 570
 571 /// isEmptySet - Return true if this set contains no members.
 572 ///
 573 bool ConstantSignedRange::isEmptySet() const {
 574   return Lower == Upper && Lower.isMinSignedValue();
 575 }
 576
 577 /// isWrappedSet - Return true if this set wraps around the top of the range,
 578 /// for example: [100, 8)
 579 ///
 580 bool ConstantSignedRange::isWrappedSet() const {
 581   return Lower.sgt(Upper);
 582 }
 583
 584 /// getSetSize - Return the number of elements in this set.
 585 ///
 586 APInt ConstantSignedRange::getSetSize() const {
 587   if (isEmptySet())
 588     return APInt(getBitWidth(), 0);
 589   if (getBitWidth() == 1) {
 590     if (Lower != Upper)  // One of T or F in the set...
 591       return APInt(2, 1);
 592     return APInt(2, 2);      // Must be full set...
 593   }
 594
 595   // Simply subtract the bounds...
 596   return Upper - Lower;
 597 }
 598
 599 /// getSignedMax - Return the largest signed value contained in the
 600 /// ConstantSignedRange.
 601 ///
 602 APInt ConstantSignedRange::getSignedMax() const {
 603   if (isFullSet() || isWrappedSet())
 604     return APInt::getSignedMaxValue(getBitWidth());
 605   else
 606     return getUpper() - 1;
 607 }
 608
 609 /// getSignedMin - Return the smallest signed value contained in the
 610 /// ConstantSignedRange.
 611 ///
 612 APInt ConstantSignedRange::getSignedMin() const {
 613   if (isFullSet() || (isWrappedSet() &&
 614                       getUpper() != APInt::getSignedMinValue(getBitWidth())))
 615     return APInt::getSignedMinValue(getBitWidth());
 616   else
 617     return getLower();
 618 }
 619
 620 /// getUnsignedMax - Return the largest unsigned value contained in the
 621 /// ConstantSignedRange.
 622 ///
 623 APInt ConstantSignedRange::getUnsignedMax() const {
 624   APInt UnsignedMax(APInt::getMaxValue(getBitWidth()));
 625   if (!isWrappedSet()) {
 626     if (getLower().ule(getUpper() - 1))
 627       return getUpper() - 1;
 628     else
 629       return UnsignedMax;
 630   } else {
 631     if ((getUpper() - 1).ult(getLower())) {
 632       if (getLower() != UnsignedMax)
 633         return UnsignedMax;
 634       else
 635         return getUpper() - 1;
 636     } else {
 637       return getUpper() - 1;
 638     }
 639   }
 640 }
 641
 642 /// getUnsignedMin - Return the smallest unsigned value contained in the
 643 /// ConstantSignedRange.
 644 ///
 645 APInt ConstantSignedRange::getUnsignedMin() const {
 646   APInt UnsignedMin(APInt::getMinValue(getBitWidth()));
 647   if (!isWrappedSet()) {
 648     if (getLower().ule(getUpper() - 1))
 649       return getLower();
 650     else
 651       return UnsignedMin;
 652   } else {
 653     if ((getUpper() - 1).ult(getLower())) {
 654       if (getUpper() != UnsignedMin)
 655         return UnsignedMin;
 656       else
 657         return getLower();
 658     } else {
 659       return getLower();
 660     }
 661   }
 662 }
 663
 664 /// contains - Return true if the specified value is in the set.
 665 ///
 666 bool ConstantSignedRange::contains(const APInt &V) const {
 667   if (Lower == Upper)
 668     return isFullSet();
 669
 670   if (!isWrappedSet())
 671     return Lower.sle(V) && V.slt(Upper);
 672   else
 673     return Lower.sle(V) || V.slt(Upper);
 674 }
 675
 676 /// subtract - Subtract the specified constant from the endpoints of this
 677 /// constant range.
 678 ConstantSignedRange ConstantSignedRange::subtract(const APInt &Val) const {
 679   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
 680   // If the set is empty or full, don't modify the endpoints.
 681   if (Lower == Upper)
 682     return *this;
 683   return ConstantSignedRange(Lower - Val, Upper - Val);
 684 }
 685
 686
 687 // intersect1Wrapped - This helper function is used to intersect two ranges when
 688 // it is known that LHS is wrapped and RHS isn't.
 689 //
 690 ConstantSignedRange
 691 ConstantSignedRange::intersect1Wrapped(const ConstantSignedRange &LHS,
 692                                  const ConstantSignedRange &RHS) {
 693   assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
 694
 695   // Check to see if we overlap on the Left side of RHS...
 696   //
 697   if (RHS.Lower.slt(LHS.Upper)) {
 698     // We do overlap on the left side of RHS, see if we overlap on the right of
 699     // RHS...
 700     if (RHS.Upper.sgt(LHS.Lower)) {
 701       // Ok, the result overlaps on both the left and right sides.  See if the
 702       // resultant interval will be smaller if we wrap or not...
 703       //
 704       if (LHS.getSetSize().ult(RHS.getSetSize()))
 705         return LHS;
 706       else
 707         return RHS;
 708
 709     } else {
 710       // No overlap on the right, just on the left.
 711       return ConstantSignedRange(RHS.Lower, LHS.Upper);
 712     }
 713   } else {
 714     // We don't overlap on the left side of RHS, see if we overlap on the right
 715     // of RHS...
 716     if (RHS.Upper.sgt(LHS.Lower)) {
 717       // Simple overlap...
 718       return ConstantSignedRange(LHS.Lower, RHS.Upper);
 719     } else {
 720       // No overlap...
 721       return ConstantSignedRange(LHS.getBitWidth(), false);
 722     }
 723   }
 724 }
 725
 726 /// intersectWith - Return the range that results from the intersection of this
 727 /// range with another range.
 728 ///
 729 ConstantSignedRange
 730 ConstantSignedRange::intersectWith(const ConstantSignedRange &CR) const {
 731   assert(getBitWidth() == CR.getBitWidth() &&
 732          "ConstantSignedRange types don't agree!");
 733   // Handle common special cases
 734   if (isEmptySet() || CR.isFullSet())
 735     return *this;
 736   if (isFullSet()  || CR.isEmptySet())
 737     return CR;
 738
 739   if (!isWrappedSet()) {
 740     if (!CR.isWrappedSet()) {
 741       APInt L = APIntOps::smax(Lower, CR.Lower);
 742       APInt U = APIntOps::smin(Upper, CR.Upper);
 743
 744       if (L.slt(U)) // If range isn't empty...
 745         return ConstantSignedRange(L, U);
 746       else
 747         return ConstantSignedRange(getBitWidth(), false);// Otherwise, empty set
 748     } else
 749       return intersect1Wrapped(CR, *this);
 750   } else {   // We know "this" is wrapped...
 751     if (!CR.isWrappedSet())
 752       return intersect1Wrapped(*this, CR);
 753     else {
 754       // Both ranges are wrapped...
 755       APInt L = APIntOps::smax(Lower, CR.Lower);
 756       APInt U = APIntOps::smin(Upper, CR.Upper);
 757       return ConstantSignedRange(L, U);
 758     }
 759   }
 760   return *this;
 761 }
 762
 763 /// maximalIntersectWith - Return the range that results from the intersection
 764 /// of this range with another range.  The resultant range is guaranteed to
 765 /// include all elements contained in both input ranges, and to have the
 766 /// smallest possible set size that does so.  Because there may be two
 767 /// intersections with the same set size, A.maximalIntersectWith(B) might not
 768 /// be equal to B.maximalIntersect(A).
 769 ConstantSignedRange
 770 ConstantSignedRange::maximalIntersectWith(const ConstantSignedRange &CR) const {
 771   assert(getBitWidth() == CR.getBitWidth() &&
 772          "ConstantSignedRange types don't agree!");
 773
 774   // Handle common cases.
 775   if (   isEmptySet() || CR.isFullSet()) return *this;
 776   if (CR.isEmptySet() ||    isFullSet()) return CR;
 777
 778   if (!isWrappedSet() && CR.isWrappedSet())
 779     return CR.maximalIntersectWith(*this);
 780
 781   if (!isWrappedSet() && !CR.isWrappedSet()) {
 782     if (Lower.slt(CR.Lower)) {
 783       if (Upper.sle(CR.Lower))
 784         return ConstantSignedRange(getBitWidth(), false);
 785
 786       if (Upper.slt(CR.Upper))
 787         return ConstantSignedRange(CR.Lower, Upper);
 788
 789       return CR;
 790     } else {
 791       if (Upper.slt(CR.Upper))
 792         return *this;
 793
 794       if (Lower.slt(CR.Upper))
 795         return ConstantSignedRange(Lower, CR.Upper);
 796
 797       return ConstantSignedRange(getBitWidth(), false);
 798     }
 799   }
 800
 801   if (isWrappedSet() && !CR.isWrappedSet()) {
 802     if (CR.Lower.slt(Upper)) {
 803       if (CR.Upper.slt(Upper))
 804         return CR;
 805
 806       if (CR.Upper.slt(Lower))
 807         return ConstantSignedRange(CR.Lower, Upper);
 808
 809       if (getSetSize().ult(CR.getSetSize()))
 810         return *this;
 811       else
 812         return CR;
 813     } else if (CR.Lower.slt(Lower)) {
 814       if (CR.Upper.sle(Lower))
 815         return ConstantSignedRange(getBitWidth(), false);
 816
 817       return ConstantSignedRange(Lower, CR.Upper);
 818     }
 819     return CR;
 820   }
 821
 822   if (CR.Upper.slt(Upper)) {
 823     if (CR.Lower.slt(Upper)) {
 824       if (getSetSize().ult(CR.getSetSize()))
 825         return *this;
 826       else
 827         return CR;
 828     }
 829
 830     if (CR.Lower.slt(Lower))
 831       return ConstantSignedRange(Lower, CR.Upper);
 832
 833     return CR;
 834   } else if (CR.Upper.slt(Lower)) {
 835     if (CR.Lower.slt(Lower))
 836       return *this;
 837
 838     return ConstantSignedRange(CR.Lower, Upper);
 839   }
 840   if (getSetSize().ult(CR.getSetSize()))
 841     return *this;
 842   else
 843     return CR;
 844 }
 845
 846
 847 /// unionWith - Return the range that results from the union of this range with
 848 /// another range.  The resultant range is guaranteed to include the elements of
 849 /// both sets, but may contain more.  For example, [3, 9) union [12,15) is
 850 /// [3, 15), which includes 9, 10, and 11, which were not included in either
 851 /// set before.
 852 ///
 853 ConstantSignedRange
 854 ConstantSignedRange::unionWith(const ConstantSignedRange &CR) const {
 855   assert(getBitWidth() == CR.getBitWidth() &&
 856          "ConstantSignedRange types don't agree!");
 857
 858   if (   isFullSet() || CR.isEmptySet()) return *this;
 859   if (CR.isFullSet() ||    isEmptySet()) return CR;
 860
 861   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
 862
 863   APInt L = Lower, U = Upper;
 864
 865   if (!isWrappedSet() && !CR.isWrappedSet()) {
 866     if (CR.Lower.slt(L))
 867       L = CR.Lower;
 868
 869     if (CR.Upper.sgt(U))
 870       U = CR.Upper;
 871   }
 872
 873   if (isWrappedSet() && !CR.isWrappedSet()) {
 874     if ((CR.Lower.slt(Upper) && CR.Upper.slt(Upper)) ||
 875         (CR.Lower.sgt(Lower) && CR.Upper.sgt(Lower))) {
 876       return *this;
 877     }
 878
 879     if (CR.Lower.sle(Upper) && Lower.sle(CR.Upper)) {
 880       return ConstantSignedRange(getBitWidth());
 881     }
 882
 883     if (CR.Lower.sle(Upper) && CR.Upper.sle(Lower)) {
 884       APInt d1 = CR.Upper - Upper, d2 = Lower - CR.Upper;
 885       if (d1.slt(d2)) {
 886         U = CR.Upper;
 887       } else {
 888         L = CR.Upper;
 889       }
 890     }
 891
 892     if (Upper.slt(CR.Lower) && CR.Upper.slt(Lower)) {
 893       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
 894       if (d1.slt(d2)) {
 895         U = CR.Lower + 1;
 896       } else {
 897         L = CR.Upper - 1;
 898       }
 899     }
 900
 901     if (Upper.slt(CR.Lower) && Lower.slt(CR.Upper)) {
 902       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Lower;
 903
 904       if (d1.slt(d2)) {
 905         U = CR.Lower + 1;
 906       } else {
 907         L = CR.Lower;
 908       }
 909     }
 910   }
 911
 912   if (isWrappedSet() && CR.isWrappedSet()) {
 913     if (Lower.slt(CR.Upper) || CR.Lower.slt(Upper))
 914       return ConstantSignedRange(getBitWidth());
 915
 916     if (CR.Upper.sgt(U)) {
 917       U = CR.Upper;
 918     }
 919
 920     if (CR.Lower.slt(L)) {
 921       L = CR.Lower;
 922     }
 923
 924     if (L == U) return ConstantSignedRange(getBitWidth());
 925   }
 926
 927   return ConstantSignedRange(L, U);
 928 }
 929
 930 /// zeroExtend - Return a new range in the specified integer type, which must
 931 /// be strictly larger than the current type.  The returned range will
 932 /// correspond to the possible range of values as if the source range had been
 933 /// zero extended.
 934 ConstantSignedRange ConstantSignedRange::zeroExtend(uint32_t DstTySize) const {
 935   unsigned SrcTySize = getBitWidth();
 936   assert(SrcTySize < DstTySize && "Not a value extension");
 937   if (isEmptySet())
 938     return ConstantSignedRange(SrcTySize, /*isFullSet=*/false);
 939   if (isFullSet())
 940     // Change a source full set into [0, 1 << 8*numbytes)
 941     return ConstantSignedRange(APInt(DstTySize,0),
 942                                APInt(DstTySize,1).shl(SrcTySize));
 943
 944   APInt L, U;
 945   if (Lower.isNegative() && !Upper.isNegative()) {
 946     L = APInt(SrcTySize, 0);
 947     U = APInt::getSignedMinValue(SrcTySize);
 948   } else {
 949     L = Lower;
 950     U = Upper;
 951   }
 952   L.zext(DstTySize);
 953   U.zext(DstTySize);
 954   return ConstantSignedRange(L, U);
 955 }
 956
 957 /// signExtend - Return a new range in the specified integer type, which must
 958 /// be strictly larger than the current type.  The returned range will
 959 /// correspond to the possible range of values as if the source range had been
 960 /// sign extended.
 961 ConstantSignedRange ConstantSignedRange::signExtend(uint32_t DstTySize) const {
 962   unsigned SrcTySize = getBitWidth();
 963   assert(SrcTySize < DstTySize && "Not a value extension");
 964   if (isEmptySet())
 965     return ConstantSignedRange(SrcTySize, /*isFullSet=*/false);
 966   if (isFullSet())
 967     return ConstantSignedRange(APInt(getSignedMin()).sext(DstTySize),
 968                                APInt(getSignedMax()).sext(DstTySize)+1);
 969
 970   APInt L = Lower; L.sext(DstTySize);
 971   APInt U = Upper; U.sext(DstTySize);
 972   return ConstantSignedRange(L, U);
 973 }
 974
 975 /// truncate - Return a new range in the specified integer type, which must be
 976 /// strictly smaller than the current type.  The returned range will
 977 /// correspond to the possible range of values as if the source range had been
 978 /// truncated to the specified type.
 979 ConstantSignedRange ConstantSignedRange::truncate(uint32_t DstTySize) const {
 980   // TODO: Implement truncate.
 981   return ConstantSignedRange(DstTySize, !isEmptySet());
 982 }
 983
 984 ConstantSignedRange
 985 ConstantSignedRange::add(const ConstantSignedRange &Other) const {
 986   // TODO: Implement add.
 987   return ConstantSignedRange(getBitWidth(),
 988                              !(isEmptySet() || Other.isEmptySet()));
 989 }
 990
 991 ConstantSignedRange
 992 ConstantSignedRange::multiply(const ConstantSignedRange &Other) const {
 993   // TODO: Implement multiply.
 994   return ConstantSignedRange(getBitWidth(),
 995                              !(isEmptySet() || Other.isEmptySet()));
 996 }
 997
 998 ConstantSignedRange
 999 ConstantSignedRange::smax(const ConstantSignedRange &Other) const {
1000   // X smax Y is: range(smax(X_smin, Y_smin),
1001   //                    smax(X_smax, Y_smax))
1002   if (isEmptySet() || Other.isEmptySet())
1003     return ConstantSignedRange(getBitWidth(), /*isFullSet=*/false);
1004   if (isFullSet() || Other.isFullSet())
1005     return ConstantSignedRange(getBitWidth(), /*isFullSet=*/true);
1006   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
1007   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
1008   if (NewU == NewL)
1009     return ConstantSignedRange(getBitWidth(), /*isFullSet=*/true);
1010   return ConstantSignedRange(NewL, NewU);
1011 }
1012
1013 ConstantSignedRange
1014 ConstantSignedRange::umax(const ConstantSignedRange &Other) const {
1015   // TODO: Implement umax.
1016   return ConstantSignedRange(getBitWidth(),
1017                              !(isEmptySet() || Other.isEmptySet()));
1018 }
1019
1020 ConstantSignedRange
1021 ConstantSignedRange::udiv(const ConstantSignedRange &Other) const {
1022   // TODO: Implement udiv.
1023   return ConstantSignedRange(getBitWidth(),
1024                              !(isEmptySet() || Other.isEmptySet()));
1025 }