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