lib/IR/ConstantRange.cpp

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