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