contrib/llvm/lib/IR/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/IR/Instruction.h"
  25 #include "llvm/IR/InstrTypes.h"
  26 #include "llvm/IR/Operator.h"
  27 #include "llvm/IR/ConstantRange.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 using namespace llvm;
  31
  32 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
  33     : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
  34       Upper(Lower) {}
  35
  36 ConstantRange::ConstantRange(APInt V)
  37     : Lower(std::move(V)), Upper(Lower + 1) {}
  38
  39 ConstantRange::ConstantRange(APInt L, APInt U)
  40     : Lower(std::move(L)), Upper(std::move(U)) {
  41   assert(Lower.getBitWidth() == Upper.getBitWidth() &&
  42          "ConstantRange with unequal bit widths");
  43   assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
  44          "Lower == Upper, but they aren't min or max value!");
  45 }
  46
  47 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
  48                                                    const ConstantRange &CR) {
  49   if (CR.isEmptySet())
  50     return CR;
  51
  52   uint32_t W = CR.getBitWidth();
  53   switch (Pred) {
  54   default:
  55     llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
  56   case CmpInst::ICMP_EQ:
  57     return CR;
  58   case CmpInst::ICMP_NE:
  59     if (CR.isSingleElement())
  60       return ConstantRange(CR.getUpper(), CR.getLower());
  61     return ConstantRange(W);
  62   case CmpInst::ICMP_ULT: {
  63     APInt UMax(CR.getUnsignedMax());
  64     if (UMax.isMinValue())
  65       return ConstantRange(W, /* empty */ false);
  66     return ConstantRange(APInt::getMinValue(W), std::move(UMax));
  67   }
  68   case CmpInst::ICMP_SLT: {
  69     APInt SMax(CR.getSignedMax());
  70     if (SMax.isMinSignedValue())
  71       return ConstantRange(W, /* empty */ false);
  72     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
  73   }
  74   case CmpInst::ICMP_ULE: {
  75     APInt UMax(CR.getUnsignedMax());
  76     if (UMax.isMaxValue())
  77       return ConstantRange(W);
  78     return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
  79   }
  80   case CmpInst::ICMP_SLE: {
  81     APInt SMax(CR.getSignedMax());
  82     if (SMax.isMaxSignedValue())
  83       return ConstantRange(W);
  84     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
  85   }
  86   case CmpInst::ICMP_UGT: {
  87     APInt UMin(CR.getUnsignedMin());
  88     if (UMin.isMaxValue())
  89       return ConstantRange(W, /* empty */ false);
  90     return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
  91   }
  92   case CmpInst::ICMP_SGT: {
  93     APInt SMin(CR.getSignedMin());
  94     if (SMin.isMaxSignedValue())
  95       return ConstantRange(W, /* empty */ false);
  96     return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
  97   }
  98   case CmpInst::ICMP_UGE: {
  99     APInt UMin(CR.getUnsignedMin());
 100     if (UMin.isMinValue())
 101       return ConstantRange(W);
 102     return ConstantRange(std::move(UMin), APInt::getNullValue(W));
 103   }
 104   case CmpInst::ICMP_SGE: {
 105     APInt SMin(CR.getSignedMin());
 106     if (SMin.isMinSignedValue())
 107       return ConstantRange(W);
 108     return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
 109   }
 110   }
 111 }
 112
 113 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
 114                                                       const ConstantRange &CR) {
 115   // Follows from De-Morgan's laws:
 116   //
 117   // ~(~A union ~B) == A intersect B.
 118   //
 119   return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
 120       .inverse();
 121 }
 122
 123 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
 124                                                  const APInt &C) {
 125   // Computes the exact range that is equal to both the constant ranges returned
 126   // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
 127   // when RHS is a singleton such as an APInt and so the assert is valid.
 128   // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
 129   // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
 130   //
 131   assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
 132   return makeAllowedICmpRegion(Pred, C);
 133 }
 134
 135 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
 136                                       APInt &RHS) const {
 137   bool Success = false;
 138
 139   if (isFullSet() || isEmptySet()) {
 140     Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
 141     RHS = APInt(getBitWidth(), 0);
 142     Success = true;
 143   } else if (auto *OnlyElt = getSingleElement()) {
 144     Pred = CmpInst::ICMP_EQ;
 145     RHS = *OnlyElt;
 146     Success = true;
 147   } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
 148     Pred = CmpInst::ICMP_NE;
 149     RHS = *OnlyMissingElt;
 150     Success = true;
 151   } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
 152     Pred =
 153         getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
 154     RHS = getUpper();
 155     Success = true;
 156   } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
 157     Pred =
 158         getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
 159     RHS = getLower();
 160     Success = true;
 161   }
 162
 163   assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
 164          "Bad result!");
 165
 166   return Success;
 167 }
 168
 169 ConstantRange
 170 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
 171                                           const ConstantRange &Other,
 172                                           unsigned NoWrapKind) {
 173   typedef OverflowingBinaryOperator OBO;
 174
 175   // Computes the intersection of CR0 and CR1.  It is different from
 176   // intersectWith in that the ConstantRange returned will only contain elements
 177   // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
 178   // not, of both X and Y).
 179   auto SubsetIntersect =
 180       [](const ConstantRange &CR0, const ConstantRange &CR1) {
 181     return CR0.inverse().unionWith(CR1.inverse()).inverse();
 182   };
 183
 184   assert(BinOp >= Instruction::BinaryOpsBegin &&
 185          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
 186
 187   assert((NoWrapKind == OBO::NoSignedWrap ||
 188           NoWrapKind == OBO::NoUnsignedWrap ||
 189           NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
 190          "NoWrapKind invalid!");
 191
 192   unsigned BitWidth = Other.getBitWidth();
 193   if (BinOp != Instruction::Add)
 194     // Conservative answer: empty set
 195     return ConstantRange(BitWidth, false);
 196
 197   if (auto *C = Other.getSingleElement())
 198     if (C->isNullValue())
 199       // Full set: nothing signed / unsigned wraps when added to 0.
 200       return ConstantRange(BitWidth);
 201
 202   ConstantRange Result(BitWidth);
 203
 204   if (NoWrapKind & OBO::NoUnsignedWrap)
 205     Result =
 206         SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
 207                                               -Other.getUnsignedMax()));
 208
 209   if (NoWrapKind & OBO::NoSignedWrap) {
 210     const APInt &SignedMin = Other.getSignedMin();
 211     const APInt &SignedMax = Other.getSignedMax();
 212
 213     if (SignedMax.isStrictlyPositive())
 214       Result = SubsetIntersect(
 215           Result,
 216           ConstantRange(APInt::getSignedMinValue(BitWidth),
 217                         APInt::getSignedMinValue(BitWidth) - SignedMax));
 218
 219     if (SignedMin.isNegative())
 220       Result = SubsetIntersect(
 221           Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
 222                                 APInt::getSignedMinValue(BitWidth)));
 223   }
 224
 225   return Result;
 226 }
 227
 228 bool ConstantRange::isFullSet() const {
 229   return Lower == Upper && Lower.isMaxValue();
 230 }
 231
 232 bool ConstantRange::isEmptySet() const {
 233   return Lower == Upper && Lower.isMinValue();
 234 }
 235
 236 bool ConstantRange::isWrappedSet() const {
 237   return Lower.ugt(Upper);
 238 }
 239
 240 bool ConstantRange::isSignWrappedSet() const {
 241   return contains(APInt::getSignedMaxValue(getBitWidth())) &&
 242          contains(APInt::getSignedMinValue(getBitWidth()));
 243 }
 244
 245 APInt ConstantRange::getSetSize() const {
 246   if (isFullSet())
 247     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
 248
 249   // This is also correct for wrapped sets.
 250   return (Upper - Lower).zext(getBitWidth()+1);
 251 }
 252
 253 bool
 254 ConstantRange::isSizeStrictlySmallerThanOf(const ConstantRange &Other) const {
 255   assert(getBitWidth() == Other.getBitWidth());
 256   if (isFullSet())
 257     return false;
 258   if (Other.isFullSet())
 259     return true;
 260   return (Upper - Lower).ult(Other.Upper - Other.Lower);
 261 }
 262
 263 APInt ConstantRange::getUnsignedMax() const {
 264   if (isFullSet() || isWrappedSet())
 265     return APInt::getMaxValue(getBitWidth());
 266   return getUpper() - 1;
 267 }
 268
 269 APInt ConstantRange::getUnsignedMin() const {
 270   if (isFullSet() || (isWrappedSet() && getUpper() != 0))
 271     return APInt::getMinValue(getBitWidth());
 272   return getLower();
 273 }
 274
 275 APInt ConstantRange::getSignedMax() const {
 276   if (!isWrappedSet()) {
 277     APInt UpperMinusOne = getUpper() - 1;
 278     if (getLower().sle(UpperMinusOne))
 279       return UpperMinusOne;
 280     return APInt::getSignedMaxValue(getBitWidth());
 281   }
 282   if (getLower().isNegative() == getUpper().isNegative())
 283     return APInt::getSignedMaxValue(getBitWidth());
 284   return getUpper() - 1;
 285 }
 286
 287 APInt ConstantRange::getSignedMin() const {
 288   if (!isWrappedSet()) {
 289     if (getLower().sle(getUpper() - 1))
 290       return getLower();
 291     return APInt::getSignedMinValue(getBitWidth());
 292   }
 293   if ((getUpper() - 1).slt(getLower())) {
 294     if (!getUpper().isMinSignedValue())
 295       return APInt::getSignedMinValue(getBitWidth());
 296   }
 297   return getLower();
 298 }
 299
 300 bool ConstantRange::contains(const APInt &V) const {
 301   if (Lower == Upper)
 302     return isFullSet();
 303
 304   if (!isWrappedSet())
 305     return Lower.ule(V) && V.ult(Upper);
 306   return Lower.ule(V) || V.ult(Upper);
 307 }
 308
 309 bool ConstantRange::contains(const ConstantRange &Other) const {
 310   if (isFullSet() || Other.isEmptySet()) return true;
 311   if (isEmptySet() || Other.isFullSet()) return false;
 312
 313   if (!isWrappedSet()) {
 314     if (Other.isWrappedSet())
 315       return false;
 316
 317     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
 318   }
 319
 320   if (!Other.isWrappedSet())
 321     return Other.getUpper().ule(Upper) ||
 322            Lower.ule(Other.getLower());
 323
 324   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
 325 }
 326
 327 ConstantRange ConstantRange::subtract(const APInt &Val) const {
 328   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
 329   // If the set is empty or full, don't modify the endpoints.
 330   if (Lower == Upper)
 331     return *this;
 332   return ConstantRange(Lower - Val, Upper - Val);
 333 }
 334
 335 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
 336   return intersectWith(CR.inverse());
 337 }
 338
 339 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
 340   assert(getBitWidth() == CR.getBitWidth() &&
 341          "ConstantRange types don't agree!");
 342
 343   // Handle common cases.
 344   if (   isEmptySet() || CR.isFullSet()) return *this;
 345   if (CR.isEmptySet() ||    isFullSet()) return CR;
 346
 347   if (!isWrappedSet() && CR.isWrappedSet())
 348     return CR.intersectWith(*this);
 349
 350   if (!isWrappedSet() && !CR.isWrappedSet()) {
 351     if (Lower.ult(CR.Lower)) {
 352       if (Upper.ule(CR.Lower))
 353         return ConstantRange(getBitWidth(), false);
 354
 355       if (Upper.ult(CR.Upper))
 356         return ConstantRange(CR.Lower, Upper);
 357
 358       return CR;
 359     }
 360     if (Upper.ult(CR.Upper))
 361       return *this;
 362
 363     if (Lower.ult(CR.Upper))
 364       return ConstantRange(Lower, CR.Upper);
 365
 366     return ConstantRange(getBitWidth(), false);
 367   }
 368
 369   if (isWrappedSet() && !CR.isWrappedSet()) {
 370     if (CR.Lower.ult(Upper)) {
 371       if (CR.Upper.ult(Upper))
 372         return CR;
 373
 374       if (CR.Upper.ule(Lower))
 375         return ConstantRange(CR.Lower, Upper);
 376
 377       if (isSizeStrictlySmallerThanOf(CR))
 378         return *this;
 379       return CR;
 380     }
 381     if (CR.Lower.ult(Lower)) {
 382       if (CR.Upper.ule(Lower))
 383         return ConstantRange(getBitWidth(), false);
 384
 385       return ConstantRange(Lower, CR.Upper);
 386     }
 387     return CR;
 388   }
 389
 390   if (CR.Upper.ult(Upper)) {
 391     if (CR.Lower.ult(Upper)) {
 392       if (isSizeStrictlySmallerThanOf(CR))
 393         return *this;
 394       return CR;
 395     }
 396
 397     if (CR.Lower.ult(Lower))
 398       return ConstantRange(Lower, CR.Upper);
 399
 400     return CR;
 401   }
 402   if (CR.Upper.ule(Lower)) {
 403     if (CR.Lower.ult(Lower))
 404       return *this;
 405
 406     return ConstantRange(CR.Lower, Upper);
 407   }
 408   if (isSizeStrictlySmallerThanOf(CR))
 409     return *this;
 410   return CR;
 411 }
 412
 413 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 414   assert(getBitWidth() == CR.getBitWidth() &&
 415          "ConstantRange types don't agree!");
 416
 417   if (   isFullSet() || CR.isEmptySet()) return *this;
 418   if (CR.isFullSet() ||    isEmptySet()) return CR;
 419
 420   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
 421
 422   if (!isWrappedSet() && !CR.isWrappedSet()) {
 423     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
 424       // If the two ranges are disjoint, find the smaller gap and bridge it.
 425       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
 426       if (d1.ult(d2))
 427         return ConstantRange(Lower, CR.Upper);
 428       return ConstantRange(CR.Lower, Upper);
 429     }
 430
 431     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
 432     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
 433
 434     if (L == 0 && U == 0)
 435       return ConstantRange(getBitWidth());
 436
 437     return ConstantRange(std::move(L), std::move(U));
 438   }
 439
 440   if (!CR.isWrappedSet()) {
 441     // ------U   L-----  and  ------U   L----- : this
 442     //   L--U                            L--U  : CR
 443     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
 444       return *this;
 445
 446     // ------U   L----- : this
 447     //    L---------U   : CR
 448     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
 449       return ConstantRange(getBitWidth());
 450
 451     // ----U       L---- : this
 452     //       L---U       : CR
 453     //    <d1>  <d2>
 454     if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
 455       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
 456       if (d1.ult(d2))
 457         return ConstantRange(Lower, CR.Upper);
 458       return ConstantRange(CR.Lower, Upper);
 459     }
 460
 461     // ----U     L----- : this
 462     //        L----U    : CR
 463     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
 464       return ConstantRange(CR.Lower, Upper);
 465
 466     // ------U    L---- : this
 467     //    L-----U       : CR
 468     assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
 469            "ConstantRange::unionWith missed a case with one range wrapped");
 470     return ConstantRange(Lower, CR.Upper);
 471   }
 472
 473   // ------U    L----  and  ------U    L---- : this
 474   // -U  L-----------  and  ------------U  L : CR
 475   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
 476     return ConstantRange(getBitWidth());
 477
 478   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
 479   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
 480
 481   return ConstantRange(std::move(L), std::move(U));
 482 }
 483
 484 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
 485                                     uint32_t ResultBitWidth) const {
 486   switch (CastOp) {
 487   default:
 488     llvm_unreachable("unsupported cast type");
 489   case Instruction::Trunc:
 490     return truncate(ResultBitWidth);
 491   case Instruction::SExt:
 492     return signExtend(ResultBitWidth);
 493   case Instruction::ZExt:
 494     return zeroExtend(ResultBitWidth);
 495   case Instruction::BitCast:
 496     return *this;
 497   case Instruction::FPToUI:
 498   case Instruction::FPToSI:
 499     if (getBitWidth() == ResultBitWidth)
 500       return *this;
 501     else
 502       return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 503   case Instruction::UIToFP: {
 504     // TODO: use input range if available
 505     auto BW = getBitWidth();
 506     APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
 507     APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
 508     return ConstantRange(std::move(Min), std::move(Max));
 509   }
 510   case Instruction::SIToFP: {
 511     // TODO: use input range if available
 512     auto BW = getBitWidth();
 513     APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
 514     APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
 515     return ConstantRange(std::move(SMin), std::move(SMax));
 516   }
 517   case Instruction::FPTrunc:
 518   case Instruction::FPExt:
 519   case Instruction::IntToPtr:
 520   case Instruction::PtrToInt:
 521   case Instruction::AddrSpaceCast:
 522     // Conservatively return full set.
 523     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 524   };
 525 }
 526
 527 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
 528   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
 529
 530   unsigned SrcTySize = getBitWidth();
 531   assert(SrcTySize < DstTySize && "Not a value extension");
 532   if (isFullSet() || isWrappedSet()) {
 533     // Change into [0, 1 << src bit width)
 534     APInt LowerExt(DstTySize, 0);
 535     if (!Upper) // special case: [X, 0) -- not really wrapping around
 536       LowerExt = Lower.zext(DstTySize);
 537     return ConstantRange(std::move(LowerExt),
 538                          APInt::getOneBitSet(DstTySize, SrcTySize));
 539   }
 540
 541   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
 542 }
 543
 544 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
 545   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
 546
 547   unsigned SrcTySize = getBitWidth();
 548   assert(SrcTySize < DstTySize && "Not a value extension");
 549
 550   // special case: [X, INT_MIN) -- not really wrapping around
 551   if (Upper.isMinSignedValue())
 552     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
 553
 554   if (isFullSet() || isSignWrappedSet()) {
 555     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
 556                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
 557   }
 558
 559   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
 560 }
 561
 562 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
 563   assert(getBitWidth() > DstTySize && "Not a value truncation");
 564   if (isEmptySet())
 565     return ConstantRange(DstTySize, /*isFullSet=*/false);
 566   if (isFullSet())
 567     return ConstantRange(DstTySize, /*isFullSet=*/true);
 568
 569   APInt MaxValue = APInt::getLowBitsSet(getBitWidth(), DstTySize);
 570   APInt MaxBitValue = APInt::getOneBitSet(getBitWidth(), DstTySize);
 571
 572   APInt LowerDiv(Lower), UpperDiv(Upper);
 573   ConstantRange Union(DstTySize, /*isFullSet=*/false);
 574
 575   // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
 576   // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
 577   // then we do the union with [MaxValue, Upper)
 578   if (isWrappedSet()) {
 579     // If Upper is greater than Max Value, it covers the whole truncated range.
 580     if (Upper.uge(MaxValue))
 581       return ConstantRange(DstTySize, /*isFullSet=*/true);
 582
 583     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
 584     UpperDiv.setAllBits();
 585
 586     // Union covers the MaxValue case, so return if the remaining range is just
 587     // MaxValue.
 588     if (LowerDiv == UpperDiv)
 589       return Union;
 590   }
 591
 592   // Chop off the most significant bits that are past the destination bitwidth.
 593   if (LowerDiv.uge(MaxValue)) {
 594     APInt Div(getBitWidth(), 0);
 595     APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
 596     UpperDiv -= MaxBitValue * Div;
 597   }
 598
 599   if (UpperDiv.ule(MaxValue))
 600     return ConstantRange(LowerDiv.trunc(DstTySize),
 601                          UpperDiv.trunc(DstTySize)).unionWith(Union);
 602
 603   // The truncated value wraps around. Check if we can do better than fullset.
 604   UpperDiv -= MaxBitValue;
 605   if (UpperDiv.ult(LowerDiv))
 606     return ConstantRange(LowerDiv.trunc(DstTySize),
 607                          UpperDiv.trunc(DstTySize)).unionWith(Union);
 608
 609   return ConstantRange(DstTySize, /*isFullSet=*/true);
 610 }
 611
 612 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
 613   unsigned SrcTySize = getBitWidth();
 614   if (SrcTySize > DstTySize)
 615     return truncate(DstTySize);
 616   if (SrcTySize < DstTySize)
 617     return zeroExtend(DstTySize);
 618   return *this;
 619 }
 620
 621 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
 622   unsigned SrcTySize = getBitWidth();
 623   if (SrcTySize > DstTySize)
 624     return truncate(DstTySize);
 625   if (SrcTySize < DstTySize)
 626     return signExtend(DstTySize);
 627   return *this;
 628 }
 629
 630 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
 631                                       const ConstantRange &Other) const {
 632   assert(BinOp >= Instruction::BinaryOpsBegin &&
 633          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
 634
 635   switch (BinOp) {
 636   case Instruction::Add:
 637     return add(Other);
 638   case Instruction::Sub:
 639     return sub(Other);
 640   case Instruction::Mul:
 641     return multiply(Other);
 642   case Instruction::UDiv:
 643     return udiv(Other);
 644   case Instruction::Shl:
 645     return shl(Other);
 646   case Instruction::LShr:
 647     return lshr(Other);
 648   case Instruction::And:
 649     return binaryAnd(Other);
 650   case Instruction::Or:
 651     return binaryOr(Other);
 652   // Note: floating point operations applied to abstract ranges are just
 653   // ideal integer operations with a lossy representation
 654   case Instruction::FAdd:
 655     return add(Other);
 656   case Instruction::FSub:
 657     return sub(Other);
 658   case Instruction::FMul:
 659     return multiply(Other);
 660   default:
 661     // Conservatively return full set.
 662     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 663   }
 664 }
 665
 666 ConstantRange
 667 ConstantRange::add(const ConstantRange &Other) const {
 668   if (isEmptySet() || Other.isEmptySet())
 669     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 670   if (isFullSet() || Other.isFullSet())
 671     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 672
 673   APInt NewLower = getLower() + Other.getLower();
 674   APInt NewUpper = getUpper() + Other.getUpper() - 1;
 675   if (NewLower == NewUpper)
 676     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 677
 678   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
 679   if (X.isSizeStrictlySmallerThanOf(*this) ||
 680       X.isSizeStrictlySmallerThanOf(Other))
 681     // We've wrapped, therefore, full set.
 682     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 683   return X;
 684 }
 685
 686 ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
 687   // Calculate the subset of this range such that "X + Other" is
 688   // guaranteed not to wrap (overflow) for all X in this subset.
 689   // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
 690   // passing a single element range.
 691   auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
 692                                       ConstantRange(Other),
 693                                       OverflowingBinaryOperator::NoSignedWrap);
 694   auto NSWConstrainedRange = intersectWith(NSWRange);
 695
 696   return NSWConstrainedRange.add(ConstantRange(Other));
 697 }
 698
 699 ConstantRange
 700 ConstantRange::sub(const ConstantRange &Other) const {
 701   if (isEmptySet() || Other.isEmptySet())
 702     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 703   if (isFullSet() || Other.isFullSet())
 704     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 705
 706   APInt NewLower = getLower() - Other.getUpper() + 1;
 707   APInt NewUpper = getUpper() - Other.getLower();
 708   if (NewLower == NewUpper)
 709     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 710
 711   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
 712   if (X.isSizeStrictlySmallerThanOf(*this) ||
 713       X.isSizeStrictlySmallerThanOf(Other))
 714     // We've wrapped, therefore, full set.
 715     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 716   return X;
 717 }
 718
 719 ConstantRange
 720 ConstantRange::multiply(const ConstantRange &Other) const {
 721   // TODO: If either operand is a single element and the multiply is known to
 722   // be non-wrapping, round the result min and max value to the appropriate
 723   // multiple of that element. If wrapping is possible, at least adjust the
 724   // range according to the greatest power-of-two factor of the single element.
 725
 726   if (isEmptySet() || Other.isEmptySet())
 727     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 728
 729   // Multiplication is signedness-independent. However different ranges can be
 730   // obtained depending on how the input ranges are treated. These different
 731   // ranges are all conservatively correct, but one might be better than the
 732   // other. We calculate two ranges; one treating the inputs as unsigned
 733   // and the other signed, then return the smallest of these ranges.
 734
 735   // Unsigned range first.
 736   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
 737   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
 738   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
 739   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
 740
 741   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
 742                                             this_max * Other_max + 1);
 743   ConstantRange UR = Result_zext.truncate(getBitWidth());
 744
 745   // If the unsigned range doesn't wrap, and isn't negative then it's a range
 746   // from one positive number to another which is as good as we can generate.
 747   // In this case, skip the extra work of generating signed ranges which aren't
 748   // going to be better than this range.
 749   if (!UR.isWrappedSet() && UR.getLower().isNonNegative())
 750     return UR;
 751
 752   // Now the signed range. Because we could be dealing with negative numbers
 753   // here, the lower bound is the smallest of the cartesian product of the
 754   // lower and upper ranges; for example:
 755   //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
 756   // Similarly for the upper bound, swapping min for max.
 757
 758   this_min = getSignedMin().sext(getBitWidth() * 2);
 759   this_max = getSignedMax().sext(getBitWidth() * 2);
 760   Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
 761   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
 762
 763   auto L = {this_min * Other_min, this_min * Other_max,
 764             this_max * Other_min, this_max * Other_max};
 765   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
 766   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
 767   ConstantRange SR = Result_sext.truncate(getBitWidth());
 768
 769   return UR.isSizeStrictlySmallerThanOf(SR) ? UR : SR;
 770 }
 771
 772 ConstantRange
 773 ConstantRange::smax(const ConstantRange &Other) const {
 774   // X smax Y is: range(smax(X_smin, Y_smin),
 775   //                    smax(X_smax, Y_smax))
 776   if (isEmptySet() || Other.isEmptySet())
 777     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 778   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
 779   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
 780   if (NewU == NewL)
 781     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 782   return ConstantRange(std::move(NewL), std::move(NewU));
 783 }
 784
 785 ConstantRange
 786 ConstantRange::umax(const ConstantRange &Other) const {
 787   // X umax Y is: range(umax(X_umin, Y_umin),
 788   //                    umax(X_umax, Y_umax))
 789   if (isEmptySet() || Other.isEmptySet())
 790     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 791   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
 792   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
 793   if (NewU == NewL)
 794     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 795   return ConstantRange(std::move(NewL), std::move(NewU));
 796 }
 797
 798 ConstantRange
 799 ConstantRange::smin(const ConstantRange &Other) const {
 800   // X smin Y is: range(smin(X_smin, Y_smin),
 801   //                    smin(X_smax, Y_smax))
 802   if (isEmptySet() || Other.isEmptySet())
 803     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 804   APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
 805   APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
 806   if (NewU == NewL)
 807     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 808   return ConstantRange(std::move(NewL), std::move(NewU));
 809 }
 810
 811 ConstantRange
 812 ConstantRange::umin(const ConstantRange &Other) const {
 813   // X umin Y is: range(umin(X_umin, Y_umin),
 814   //                    umin(X_umax, Y_umax))
 815   if (isEmptySet() || Other.isEmptySet())
 816     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 817   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
 818   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
 819   if (NewU == NewL)
 820     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 821   return ConstantRange(std::move(NewL), std::move(NewU));
 822 }
 823
 824 ConstantRange
 825 ConstantRange::udiv(const ConstantRange &RHS) const {
 826   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
 827     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 828   if (RHS.isFullSet())
 829     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 830
 831   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
 832
 833   APInt RHS_umin = RHS.getUnsignedMin();
 834   if (RHS_umin == 0) {
 835     // We want the lowest value in RHS excluding zero. Usually that would be 1
 836     // except for a range in the form of [X, 1) in which case it would be X.
 837     if (RHS.getUpper() == 1)
 838       RHS_umin = RHS.getLower();
 839     else
 840       RHS_umin = 1;
 841   }
 842
 843   APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
 844
 845   // If the LHS is Full and the RHS is a wrapped interval containing 1 then
 846   // this could occur.
 847   if (Lower == Upper)
 848     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 849
 850   return ConstantRange(std::move(Lower), std::move(Upper));
 851 }
 852
 853 ConstantRange
 854 ConstantRange::binaryAnd(const ConstantRange &Other) const {
 855   if (isEmptySet() || Other.isEmptySet())
 856     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 857
 858   // TODO: replace this with something less conservative
 859
 860   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
 861   if (umin.isAllOnesValue())
 862     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 863   return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
 864 }
 865
 866 ConstantRange
 867 ConstantRange::binaryOr(const ConstantRange &Other) const {
 868   if (isEmptySet() || Other.isEmptySet())
 869     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 870
 871   // TODO: replace this with something less conservative
 872
 873   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
 874   if (umax.isNullValue())
 875     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 876   return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
 877 }
 878
 879 ConstantRange
 880 ConstantRange::shl(const ConstantRange &Other) const {
 881   if (isEmptySet() || Other.isEmptySet())
 882     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 883
 884   APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
 885   APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
 886
 887   // there's no overflow!
 888   APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
 889   if (Zeros.ugt(Other.getUnsignedMax()))
 890     return ConstantRange(std::move(min), std::move(max) + 1);
 891
 892   // FIXME: implement the other tricky cases
 893   return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 894 }
 895
 896 ConstantRange
 897 ConstantRange::lshr(const ConstantRange &Other) const {
 898   if (isEmptySet() || Other.isEmptySet())
 899     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 900
 901   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
 902   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
 903   if (min == max + 1)
 904     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 905
 906   return ConstantRange(std::move(min), std::move(max) + 1);
 907 }
 908
 909 ConstantRange ConstantRange::inverse() const {
 910   if (isFullSet())
 911     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 912   if (isEmptySet())
 913     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 914   return ConstantRange(Upper, Lower);
 915 }
 916
 917 void ConstantRange::print(raw_ostream &OS) const {
 918   if (isFullSet())
 919     OS << "full-set";
 920   else if (isEmptySet())
 921     OS << "empty-set";
 922   else
 923     OS << "[" << Lower << "," << Upper << ")";
 924 }
 925
 926 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 927 LLVM_DUMP_METHOD void ConstantRange::dump() const {
 928   print(dbgs());
 929 }
 930 #endif
 931
 932 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
 933   const unsigned NumRanges = Ranges.getNumOperands() / 2;
 934   assert(NumRanges >= 1 && "Must have at least one range!");
 935   assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
 936
 937   auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
 938   auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
 939
 940   ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
 941
 942   for (unsigned i = 1; i < NumRanges; ++i) {
 943     auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
 944     auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
 945
 946     // Note: unionWith will potentially create a range that contains values not
 947     // contained in any of the original N ranges.
 948     CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
 949   }
 950
 951   return CR;
 952 }