LCOV - code coverage report
Current view: top level - lib/IR - ConstantRange.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 552 568 97.2 %
Date: 2018-07-13 00:08:38 Functions: 51 51 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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     8552530 : ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
      43             :     : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
      44    18679941 :       Upper(Lower) {}
      45             : 
      46     4112723 : ConstantRange::ConstantRange(APInt V)
      47     8225446 :     : Lower(std::move(V)), Upper(Lower + 1) {}
      48             : 
      49     7195516 : 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     7195516 : }
      56             : 
      57      894600 : ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
      58             :                                                    const ConstantRange &CR) {
      59      894600 :   if (CR.isEmptySet())
      60           0 :     return CR;
      61             : 
      62             :   uint32_t W = CR.getBitWidth();
      63      894600 :   switch (Pred) {
      64           0 :   default:
      65           0 :     llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
      66      236654 :   case CmpInst::ICMP_EQ:
      67      236654 :     return CR;
      68             :   case CmpInst::ICMP_NE:
      69      126910 :     if (CR.isSingleElement())
      70      375318 :       return ConstantRange(CR.getUpper(), CR.getLower());
      71        1804 :     return ConstantRange(W);
      72      156835 :   case CmpInst::ICMP_ULT: {
      73      156835 :     APInt UMax(CR.getUnsignedMax());
      74      156835 :     if (UMax.isMinValue())
      75         995 :       return ConstantRange(W, /* empty */ false);
      76      467520 :     return ConstantRange(APInt::getMinValue(W), std::move(UMax));
      77             :   }
      78       64013 :   case CmpInst::ICMP_SLT: {
      79       64013 :     APInt SMax(CR.getSignedMax());
      80       64013 :     if (SMax.isMinSignedValue())
      81         861 :       return ConstantRange(W, /* empty */ false);
      82      189456 :     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
      83             :   }
      84       28356 :   case CmpInst::ICMP_ULE: {
      85       28356 :     APInt UMax(CR.getUnsignedMax());
      86       28356 :     if (UMax.isMaxValue())
      87        1478 :       return ConstantRange(W);
      88      107512 :     return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
      89             :   }
      90       31976 :   case CmpInst::ICMP_SLE: {
      91       31976 :     APInt SMax(CR.getSignedMax());
      92       31976 :     if (SMax.isMaxSignedValue())
      93         457 :       return ConstantRange(W);
      94      126076 :     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
      95             :   }
      96       97368 :   case CmpInst::ICMP_UGT: {
      97       97368 :     APInt UMin(CR.getUnsignedMin());
      98       97368 :     if (UMin.isMaxValue())
      99        1704 :       return ConstantRange(W, /* empty */ false);
     100      478320 :     return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
     101             :   }
     102       92014 :   case CmpInst::ICMP_SGT: {
     103       92014 :     APInt SMin(CR.getSignedMin());
     104       92014 :     if (SMin.isMaxSignedValue())
     105         957 :       return ConstantRange(W, /* empty */ false);
     106      455285 :     return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
     107             :   }
     108       25984 :   case CmpInst::ICMP_UGE: {
     109       25984 :     APInt UMin(CR.getUnsignedMin());
     110       25984 :     if (UMin.isMinValue())
     111        3270 :       return ConstantRange(W);
     112       90856 :     return ConstantRange(std::move(UMin), APInt::getNullValue(W));
     113             :   }
     114       34490 :   case CmpInst::ICMP_SGE: {
     115       34490 :     APInt SMin(CR.getSignedMin());
     116       34490 :     if (SMin.isMinSignedValue())
     117        2101 :       return ConstantRange(W);
     118      129556 :     return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
     119             :   }
     120             :   }
     121             : }
     122             : 
     123      223513 : 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      447026 :   return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
     130      447026 :       .inverse();
     131             : }
     132             : 
     133      505076 : 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     1010152 :   return makeAllowedICmpRegion(Pred, C);
     143             : }
     144             : 
     145      125805 : bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
     146             :                                       APInt &RHS) const {
     147             :   bool Success = false;
     148             : 
     149      125805 :   if (isFullSet() || isEmptySet()) {
     150           4 :     Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
     151           2 :     RHS = APInt(getBitWidth(), 0);
     152             :     Success = true;
     153      125803 :   } else if (auto *OnlyElt = getSingleElement()) {
     154         734 :     Pred = CmpInst::ICMP_EQ;
     155         734 :     RHS = *OnlyElt;
     156             :     Success = true;
     157      125069 :   } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
     158       21826 :     Pred = CmpInst::ICMP_NE;
     159       21826 :     RHS = *OnlyMissingElt;
     160             :     Success = true;
     161      182369 :   } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
     162       65229 :     Pred =
     163       65229 :         getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
     164       65229 :     RHS = getUpper();
     165             :     Success = true;
     166       48955 :   } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
     167       38009 :     Pred =
     168       38009 :         getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
     169       38009 :     RHS = getLower();
     170             :     Success = true;
     171             :   }
     172             : 
     173             :   assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
     174             :          "Bad result!");
     175             : 
     176      125805 :   return Success;
     177             : }
     178             : 
     179             : ConstantRange
     180     3038246 : 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     1309581 :       [](const ConstantRange &CR0, const ConstantRange &CR1) {
     191     2619162 :     return CR0.inverse().unionWith(CR1.inverse()).inverse();
     192     2619162 :   };
     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     6076492 :   ConstantRange Result(BitWidth);
     203             : 
     204     3038246 :   switch (BinOp) {
     205           0 :   default:
     206             :     // Conservative answer: empty set
     207           0 :     return ConstantRange(BitWidth, false);
     208             : 
     209     2971065 :   case Instruction::Add:
     210     2971065 :     if (auto *C = Other.getSingleElement())
     211     2969869 :       if (C->isNullValue())
     212             :         // Full set: nothing signed / unsigned wraps when added to 0.
     213     1662851 :         return ConstantRange(BitWidth);
     214     1308214 :     if (NoWrapKind & OBO::NoUnsignedWrap)
     215      772057 :       Result =
     216     2316171 :           SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
     217     2316171 :                                                 -Other.getUnsignedMax()));
     218     1308214 :     if (NoWrapKind & OBO::NoSignedWrap) {
     219      536168 :       const APInt &SignedMin = Other.getSignedMin();
     220      536168 :       const APInt &SignedMax = Other.getSignedMax();
     221      536168 :       if (SignedMax.isStrictlyPositive())
     222      336436 :         Result = SubsetIntersect(
     223             :             Result,
     224     1009308 :             ConstantRange(APInt::getSignedMinValue(BitWidth),
     225     1009308 :                           APInt::getSignedMinValue(BitWidth) - SignedMax));
     226     1072336 :       if (SignedMin.isNegative())
     227      200201 :         Result = SubsetIntersect(
     228             :             Result,
     229     1001005 :             ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
     230      400402 :                           APInt::getSignedMinValue(BitWidth)));
     231             :     }
     232             :     return Result;
     233             : 
     234         108 :   case Instruction::Sub:
     235         108 :     if (auto *C = Other.getSingleElement())
     236          31 :       if (C->isNullValue())
     237             :         // Full set: nothing signed / unsigned wraps when subtracting 0.
     238           6 :         return ConstantRange(BitWidth);
     239         102 :     if (NoWrapKind & OBO::NoUnsignedWrap)
     240          86 :       Result =
     241         258 :           SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(),
     242         172 :                                                 APInt::getMinValue(BitWidth)));
     243         102 :     if (NoWrapKind & OBO::NoSignedWrap) {
     244          27 :       const APInt &SignedMin = Other.getSignedMin();
     245          27 :       const APInt &SignedMax = Other.getSignedMax();
     246          27 :       if (SignedMax.isStrictlyPositive())
     247          17 :         Result = SubsetIntersect(
     248             :             Result,
     249          85 :             ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax,
     250          34 :                           APInt::getSignedMinValue(BitWidth)));
     251          54 :       if (SignedMin.isNegative())
     252          15 :         Result = SubsetIntersect(
     253             :             Result,
     254          45 :             ConstantRange(APInt::getSignedMinValue(BitWidth),
     255          45 :                           APInt::getSignedMinValue(BitWidth) + SignedMin));
     256             :     }
     257             :     return Result;
     258       67073 :   case Instruction::Mul: {
     259       67073 :     if (NoWrapKind == (OBO::NoSignedWrap | OBO::NoUnsignedWrap)) {
     260             :       return SubsetIntersect(
     261         512 :           makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoSignedWrap),
     262         768 :           makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoUnsignedWrap));
     263             :     }
     264             : 
     265             :     // Equivalent to calling makeGuaranteedNoWrapRegion() on [V, V+1).
     266       66817 :     const bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
     267             :     const auto makeSingleValueRegion = [Unsigned,
     268      538520 :                                         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      134652 :       if (V == 0 || V.isOneValue())
     272          18 :         return ConstantRange(BitWidth, true);
     273             : 
     274             :       APInt MinValue, MaxValue;
     275       67312 :       if (Unsigned) {
     276      132588 :         MinValue = APInt::getMinValue(BitWidth);
     277       66294 :         MaxValue = APInt::getMaxValue(BitWidth);
     278             :       } else {
     279        2036 :         MinValue = APInt::getSignedMinValue(BitWidth);
     280        2036 :         MaxValue = APInt::getSignedMaxValue(BitWidth);
     281             :       }
     282             :       // e.g. Returning [-127, 127], represented as [-127, -128).
     283       68330 :       if (!Unsigned && V.isAllOnesValue())
     284          16 :         return ConstantRange(-MaxValue, MinValue);
     285             : 
     286             :       APInt Lower, Upper;
     287       69336 :       if (!Unsigned && V.isNegative()) {
     288        1018 :         Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP);
     289        1018 :         Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN);
     290       66799 :       } else if (Unsigned) {
     291      132588 :         Lower = APIntOps::RoundingUDiv(MinValue, V, APInt::Rounding::UP);
     292      132588 :         Upper = APIntOps::RoundingUDiv(MaxValue, V, APInt::Rounding::DOWN);
     293             :       } else {
     294        1010 :         Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP);
     295        1010 :         Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN);
     296             :       }
     297       67308 :       if (Unsigned) {
     298      132588 :         Lower = Lower.zextOrSelf(BitWidth);
     299      132588 :         Upper = Upper.zextOrSelf(BitWidth);
     300             :       } else {
     301        2028 :         Lower = Lower.sextOrSelf(BitWidth);
     302        2028 :         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      269232 :       return ConstantRange(Lower, Upper + 1);
     308       66817 :     };
     309             : 
     310       66817 :     if (Unsigned)
     311      132608 :       return makeSingleValueRegion(Other.getUnsignedMax());
     312             : 
     313        1539 :     return SubsetIntersect(makeSingleValueRegion(Other.getSignedMin()),
     314        2052 :                            makeSingleValueRegion(Other.getSignedMax()));
     315             :   }
     316             :   }
     317             : }
     318             : 
     319    24910292 : bool ConstantRange::isFullSet() const {
     320    57080911 :   return Lower == Upper && Lower.isMaxValue();
     321             : }
     322             : 
     323    14818195 : bool ConstantRange::isEmptySet() const {
     324    33306568 :   return Lower == Upper && Lower.isMinValue();
     325             : }
     326             : 
     327     8337704 : bool ConstantRange::isWrappedSet() const {
     328    16675408 :   return Lower.ugt(Upper);
     329             : }
     330             : 
     331        4125 : bool ConstantRange::isSignWrappedSet() const {
     332       10703 :   return contains(APInt::getSignedMaxValue(getBitWidth())) &&
     333       12396 :          contains(APInt::getSignedMinValue(getBitWidth()));
     334             : }
     335             : 
     336           6 : APInt ConstantRange::getSetSize() const {
     337           6 :   if (isFullSet())
     338           1 :     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
     339             : 
     340             :   // This is also correct for wrapped sets.
     341          20 :   return (Upper - Lower).zext(getBitWidth()+1);
     342             : }
     343             : 
     344             : bool
     345      268555 : ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
     346             :   assert(getBitWidth() == Other.getBitWidth());
     347      268555 :   if (isFullSet())
     348             :     return false;
     349      173153 :   if (Other.isFullSet())
     350             :     return true;
     351     1038582 :   return (Upper - Lower).ult(Other.Upper - Other.Lower);
     352             : }
     353             : 
     354             : bool
     355      116340 : 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      116340 :   if (isFullSet())
     360          36 :     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
     361             : 
     362      465288 :   return (Upper - Lower).ugt(MaxSize);
     363             : }
     364             : 
     365     2287626 : APInt ConstantRange::getUnsignedMax() const {
     366     2287626 :   if (isFullSet() || isWrappedSet())
     367             :     return APInt::getMaxValue(getBitWidth());
     368     1929479 :   return getUpper() - 1;
     369             : }
     370             : 
     371      638306 : APInt ConstantRange::getUnsignedMin() const {
     372      719167 :   if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
     373      131091 :     return APInt::getMinValue(getBitWidth());
     374             :   return getLower();
     375             : }
     376             : 
     377     1168705 : APInt ConstantRange::getSignedMax() const {
     378     2223866 :   if (isFullSet() || Lower.sgt(Upper))
     379      131517 :     return APInt::getSignedMaxValue(getBitWidth());
     380     1037188 :   return getUpper() - 1;
     381             : }
     382             : 
     383     3218582 : APInt ConstantRange::getSignedMin() const {
     384     6144585 :   if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
     385      318196 :     return APInt::getSignedMinValue(getBitWidth());
     386             :   return getLower();
     387             : }
     388             : 
     389      588010 : bool ConstantRange::contains(const APInt &V) const {
     390     1176020 :   if (Lower == Upper)
     391        2245 :     return isFullSet();
     392             : 
     393      585765 :   if (!isWrappedSet())
     394      905539 :     return Lower.ule(V) && V.ult(Upper);
     395      224705 :   return Lower.ule(V) || V.ult(Upper);
     396             : }
     397             : 
     398     3383980 : bool ConstantRange::contains(const ConstantRange &Other) const {
     399     3383980 :   if (isFullSet() || Other.isEmptySet()) return true;
     400     1717136 :   if (isEmptySet() || Other.isFullSet()) return false;
     401             : 
     402     1273032 :   if (!isWrappedSet()) {
     403      734890 :     if (Other.isWrappedSet())
     404             :       return false;
     405             : 
     406     2350224 :     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
     407             :   }
     408             : 
     409      538142 :   if (!Other.isWrappedSet())
     410      872833 :     return Other.getUpper().ule(Upper) ||
     411      206387 :            Lower.ule(Other.getLower());
     412             : 
     413      544366 :   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
     414             : }
     415             : 
     416       25877 : 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       51754 :   if (Lower == Upper)
     420         137 :     return *this;
     421      128700 :   return ConstantRange(Lower - Val, Upper - Val);
     422             : }
     423             : 
     424       19276 : ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
     425       19276 :   return intersectWith(CR.inverse());
     426             : }
     427             : 
     428      866760 : ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
     429             :   assert(getBitWidth() == CR.getBitWidth() &&
     430             :          "ConstantRange types don't agree!");
     431             : 
     432             :   // Handle common cases.
     433      866760 :   if (   isEmptySet() || CR.isFullSet()) return *this;
     434      869141 :   if (CR.isEmptySet() ||    isFullSet()) return CR;
     435             : 
     436      580226 :   if (!isWrappedSet() && CR.isWrappedSet())
     437       23793 :     return CR.intersectWith(*this);
     438             : 
     439      532640 :   if (!isWrappedSet() && !CR.isWrappedSet()) {
     440      397800 :     if (Lower.ult(CR.Lower)) {
     441       19372 :       if (Upper.ule(CR.Lower))
     442          22 :         return ConstantRange(getBitWidth(), false);
     443             : 
     444       19328 :       if (Upper.ult(CR.Upper))
     445        2595 :         return ConstantRange(CR.Lower, Upper);
     446             : 
     447        8799 :       return CR;
     448             :     }
     449      378428 :     if (Upper.ult(CR.Upper))
     450        1350 :       return *this;
     451             : 
     452      187864 :     if (Lower.ult(CR.Upper))
     453      563391 :       return ConstantRange(Lower, CR.Upper);
     454             : 
     455          67 :     return ConstantRange(getBitWidth(), false);
     456             :   }
     457             : 
     458      269680 :   if (isWrappedSet() && !CR.isWrappedSet()) {
     459      153836 :     if (CR.Lower.ult(Upper)) {
     460       93516 :       if (CR.Upper.ult(Upper))
     461       18892 :         return CR;
     462             : 
     463       55732 :       if (CR.Upper.ule(Lower))
     464       50916 :         return ConstantRange(CR.Lower, Upper);
     465             : 
     466       10894 :       if (isSizeStrictlySmallerThan(CR))
     467        5629 :         return *this;
     468        5265 :       return CR;
     469             :     }
     470       60320 :     if (CR.Lower.ult(Lower)) {
     471       50846 :       if (CR.Upper.ule(Lower))
     472          88 :         return ConstantRange(getBitWidth(), false);
     473             : 
     474       76005 :       return ConstantRange(Lower, CR.Upper);
     475             :     }
     476        4737 :     return CR;
     477             :   }
     478             : 
     479      115844 :   if (CR.Upper.ult(Upper)) {
     480       63990 :     if (CR.Lower.ult(Upper)) {
     481        9803 :       if (isSizeStrictlySmallerThan(CR))
     482          18 :         return *this;
     483        9785 :       return CR;
     484             :     }
     485             : 
     486       44384 :     if (CR.Lower.ult(Lower))
     487        8184 :       return ConstantRange(Lower, CR.Upper);
     488             : 
     489       19464 :     return CR;
     490             :   }
     491       51854 :   if (CR.Upper.ule(Lower)) {
     492       32790 :     if (CR.Lower.ult(Lower))
     493          85 :       return *this;
     494             : 
     495       48930 :     return ConstantRange(CR.Lower, Upper);
     496             :   }
     497        9532 :   if (isSizeStrictlySmallerThan(CR))
     498         222 :     return *this;
     499        9310 :   return CR;
     500             : }
     501             : 
     502     1646339 : ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
     503             :   assert(getBitWidth() == CR.getBitWidth() &&
     504             :          "ConstantRange types don't agree!");
     505             : 
     506     1646339 :   if (   isFullSet() || CR.isEmptySet()) return *this;
     507     2896325 :   if (CR.isFullSet() ||    isEmptySet()) return CR;
     508             : 
     509      441667 :   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
     510             : 
     511      265669 :   if (!isWrappedSet() && !CR.isWrappedSet()) {
     512      263768 :     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
     513             :       // If the two ranges are disjoint, find the smaller gap and bridge it.
     514        2547 :       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
     515         849 :       if (d1.ult(d2))
     516         969 :         return ConstantRange(Lower, CR.Upper);
     517        1578 :       return ConstantRange(CR.Lower, Upper);
     518             :     }
     519             : 
     520       87245 :     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
     521      436225 :     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
     522             : 
     523      138320 :     if (L.isNullValue() && U.isNullValue())
     524           0 :       return ConstantRange(getBitWidth());
     525             : 
     526      261735 :     return ConstantRange(std::move(L), std::move(U));
     527             :   }
     528             : 
     529       89481 :   if (!CR.isWrappedSet()) {
     530             :     // ------U   L-----  and  ------U   L----- : this
     531             :     //   L--U                            L--U  : CR
     532      179884 :     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
     533        1485 :       return *this;
     534             : 
     535             :     // ------U   L----- : this
     536             :     //    L---------U   : CR
     537       90069 :     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
     538       31028 :       return ConstantRange(getBitWidth());
     539             : 
     540             :     // ----U       L---- : this
     541             :     //       L---U       : CR
     542             :     //    <d1>  <d2>
     543       55517 :     if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
     544       55138 :       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
     545       27569 :       if (d1.ult(d2))
     546         447 :         return ConstantRange(Lower, CR.Upper);
     547       82260 :       return ConstantRange(CR.Lower, Upper);
     548             :     }
     549             : 
     550             :     // ----U     L----- : this
     551             :     //        L----U    : CR
     552         379 :     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
     553         414 :       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         309 :     return ConstantRange(Lower, CR.Upper);
     560             :   }
     561             : 
     562             :   // ------U    L----  and  ------U    L---- : this
     563             :   // -U  L-----------  and  ------------U  L : CR
     564       87440 :   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
     565          73 :     return ConstantRange(getBitWidth());
     566             : 
     567       29085 :   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
     568       29085 :   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
     569             : 
     570       87255 :   return ConstantRange(std::move(L), std::move(U));
     571             : }
     572             : 
     573        1824 : ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
     574             :                                     uint32_t ResultBitWidth) const {
     575        1824 :   switch (CastOp) {
     576           0 :   default:
     577           0 :     llvm_unreachable("unsupported cast type");
     578         363 :   case Instruction::Trunc:
     579         363 :     return truncate(ResultBitWidth);
     580          46 :   case Instruction::SExt:
     581          46 :     return signExtend(ResultBitWidth);
     582        1300 :   case Instruction::ZExt:
     583        1300 :     return zeroExtend(ResultBitWidth);
     584          17 :   case Instruction::BitCast:
     585          17 :     return *this;
     586             :   case Instruction::FPToUI:
     587             :   case Instruction::FPToSI:
     588          50 :     if (getBitWidth() == ResultBitWidth)
     589          50 :       return *this;
     590             :     else
     591           0 :       return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     592             :   case Instruction::UIToFP: {
     593             :     // TODO: use input range if available
     594             :     auto BW = getBitWidth();
     595          82 :     APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
     596          82 :     APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
     597         123 :     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          14 :     APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
     603          14 :     APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
     604          21 :     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           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     613             :   };
     614             : }
     615             : 
     616       32989 : ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
     617       32989 :   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
     618             : 
     619             :   unsigned SrcTySize = getBitWidth();
     620             :   assert(SrcTySize < DstTySize && "Not a value extension");
     621       32988 :   if (isFullSet() || isWrappedSet()) {
     622             :     // Change into [0, 1 << src bit width)
     623             :     APInt LowerExt(DstTySize, 0);
     624       48602 :     if (!Upper) // special case: [X, 0) -- not really wrapping around
     625          44 :       LowerExt = Lower.zext(DstTySize);
     626             :     return ConstantRange(std::move(LowerExt),
     627       97204 :                          APInt::getOneBitSet(DstTySize, SrcTySize));
     628             :   }
     629             : 
     630       26061 :   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
     631             : }
     632             : 
     633       16307 : ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
     634       16307 :   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       16306 :   if (Upper.isMinSignedValue())
     641          90 :     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
     642             : 
     643       16276 :   if (isFullSet() || isSignWrappedSet()) {
     644       29534 :     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
     645       59068 :                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
     646             :   }
     647             : 
     648        4527 :   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
     649             : }
     650             : 
     651      231717 : ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
     652             :   assert(getBitWidth() > DstTySize && "Not a value truncation");
     653      231717 :   if (isEmptySet())
     654           1 :     return ConstantRange(DstTySize, /*isFullSet=*/false);
     655      231716 :   if (isFullSet())
     656        3139 :     return ConstantRange(DstTySize, /*isFullSet=*/true);
     657             : 
     658      457154 :   APInt LowerDiv(Lower), UpperDiv(Upper);
     659      457154 :   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      228577 :   if (isWrappedSet()) {
     665             :     // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
     666             :     // truncated range.
     667      154146 :     if (Upper.getActiveBits() > DstTySize ||
     668             :         Upper.countTrailingOnes() == DstTySize)
     669       35282 :       return ConstantRange(DstTySize, /*isFullSet=*/true);
     670             : 
     671      234884 :     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
     672       58721 :     UpperDiv.setAllBits();
     673             : 
     674             :     // Union covers the MaxValue case, so return if the remaining range is just
     675             :     // MaxValue(DstTy).
     676       58721 :     if (LowerDiv == UpperDiv)
     677             :       return Union;
     678             :   }
     679             : 
     680             :   // Chop off the most significant bits that are past the destination bitwidth.
     681      191706 :   if (LowerDiv.getActiveBits() > DstTySize) {
     682             :     // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
     683      116628 :     APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
     684       58314 :     LowerDiv -= Adjust;
     685       58314 :     UpperDiv -= Adjust;
     686             :   }
     687             : 
     688             :   unsigned UpperDivWidth = UpperDiv.getActiveBits();
     689      191706 :   if (UpperDivWidth <= DstTySize)
     690      277971 :     return ConstantRange(LowerDiv.trunc(DstTySize),
     691      277971 :                          UpperDiv.trunc(DstTySize)).unionWith(Union);
     692             : 
     693             :   // The truncated value wraps around. Check if we can do better than fullset.
     694       99049 :   if (UpperDivWidth == DstTySize + 1) {
     695             :     // Clear the MSB so that UpperDiv wraps around.
     696             :     UpperDiv.clearBit(DstTySize);
     697        5117 :     if (UpperDiv.ult(LowerDiv))
     698          54 :       return ConstantRange(LowerDiv.trunc(DstTySize),
     699          54 :                            UpperDiv.trunc(DstTySize)).unionWith(Union);
     700             :   }
     701             : 
     702       99031 :   return ConstantRange(DstTySize, /*isFullSet=*/true);
     703             : }
     704             : 
     705        1498 : ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
     706             :   unsigned SrcTySize = getBitWidth();
     707        1498 :   if (SrcTySize > DstTySize)
     708          25 :     return truncate(DstTySize);
     709        1473 :   if (SrcTySize < DstTySize)
     710         161 :     return zeroExtend(DstTySize);
     711        1312 :   return *this;
     712             : }
     713             : 
     714         382 : ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
     715             :   unsigned SrcTySize = getBitWidth();
     716         382 :   if (SrcTySize > DstTySize)
     717           1 :     return truncate(DstTySize);
     718         381 :   if (SrcTySize < DstTySize)
     719          55 :     return signExtend(DstTySize);
     720         326 :   return *this;
     721             : }
     722             : 
     723       11393 : ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
     724             :                                       const ConstantRange &Other) const {
     725             :   assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
     726             : 
     727       11393 :   switch (BinOp) {
     728        8806 :   case Instruction::Add:
     729        8806 :     return add(Other);
     730           1 :   case Instruction::Sub:
     731           1 :     return sub(Other);
     732         278 :   case Instruction::Mul:
     733         278 :     return multiply(Other);
     734          93 :   case Instruction::UDiv:
     735          93 :     return udiv(Other);
     736         457 :   case Instruction::Shl:
     737         457 :     return shl(Other);
     738         691 :   case Instruction::LShr:
     739         691 :     return lshr(Other);
     740         609 :   case Instruction::AShr:
     741         609 :     return ashr(Other);
     742         293 :   case Instruction::And:
     743         293 :     return binaryAnd(Other);
     744         136 :   case Instruction::Or:
     745         136 :     return binaryOr(Other);
     746             :   // Note: floating point operations applied to abstract ranges are just
     747             :   // ideal integer operations with a lossy representation
     748          17 :   case Instruction::FAdd:
     749          17 :     return add(Other);
     750           4 :   case Instruction::FSub:
     751           4 :     return sub(Other);
     752           8 :   case Instruction::FMul:
     753           8 :     return multiply(Other);
     754             :   default:
     755             :     // Conservatively return full set.
     756           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     757             :   }
     758             : }
     759             : 
     760             : ConstantRange
     761      734451 : ConstantRange::add(const ConstantRange &Other) const {
     762      734451 :   if (isEmptySet() || Other.isEmptySet())
     763           8 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     764      734443 :   if (isFullSet() || Other.isFullSet())
     765      650135 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     766             : 
     767       84308 :   APInt NewLower = getLower() + Other.getLower();
     768      168616 :   APInt NewUpper = getUpper() + Other.getUpper() - 1;
     769       84308 :   if (NewLower == NewUpper)
     770          51 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     771             : 
     772      337028 :   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
     773      140163 :   if (X.isSizeStrictlySmallerThan(*this) ||
     774       55906 :       X.isSizeStrictlySmallerThan(Other))
     775             :     // We've wrapped, therefore, full set.
     776       28351 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     777             :   return X;
     778             : }
     779             : 
     780          28 : 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          84 :                                       ConstantRange(Other),
     787          56 :                                       OverflowingBinaryOperator::NoSignedWrap);
     788          56 :   auto NSWConstrainedRange = intersectWith(NSWRange);
     789             : 
     790          84 :   return NSWConstrainedRange.add(ConstantRange(Other));
     791             : }
     792             : 
     793             : ConstantRange
     794          20 : ConstantRange::sub(const ConstantRange &Other) const {
     795          20 :   if (isEmptySet() || Other.isEmptySet())
     796           6 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     797          14 :   if (isFullSet() || Other.isFullSet())
     798           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     799             : 
     800          18 :   APInt NewLower = getLower() - Other.getUpper() + 1;
     801           9 :   APInt NewUpper = getUpper() - Other.getLower();
     802           9 :   if (NewLower == NewUpper)
     803           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     804             : 
     805          36 :   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
     806          18 :   if (X.isSizeStrictlySmallerThan(*this) ||
     807           9 :       X.isSizeStrictlySmallerThan(Other))
     808             :     // We've wrapped, therefore, full set.
     809           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     810             :   return X;
     811             : }
     812             : 
     813             : ConstantRange
     814      126700 : 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      126700 :   if (isEmptySet() || Other.isEmptySet())
     821           5 :     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      380085 :   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
     831      380085 :   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
     832      380085 :   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
     833      380085 :   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
     834             : 
     835      253390 :   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
     836      633475 :                                             this_max * Other_max + 1);
     837      253390 :   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      253377 :   if (!UR.isWrappedSet() &&
     844       98283 :       (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      392580 :   this_min = getSignedMin().sext(getBitWidth() * 2);
     854      392580 :   this_max = getSignedMax().sext(getBitWidth() * 2);
     855      392580 :   Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
     856      392580 :   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
     857             : 
     858       98145 :   auto L = {this_min * Other_min, this_min * Other_max,
     859      588870 :             this_max * Other_min, this_max * Other_max};
     860             :   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
     861      588870 :   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
     862      196290 :   ConstantRange SR = Result_sext.truncate(getBitWidth());
     863             : 
     864       98145 :   return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
     865             : }
     866             : 
     867             : ConstantRange
     868        5211 : ConstantRange::smax(const ConstantRange &Other) const {
     869             :   // X smax Y is: range(smax(X_smin, Y_smin),
     870             :   //                    smax(X_smax, Y_smax))
     871        5211 :   if (isEmptySet() || Other.isEmptySet())
     872           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     873       15618 :   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
     874       20824 :   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
     875        5206 :   if (NewU == NewL)
     876         589 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     877       13851 :   return ConstantRange(std::move(NewL), std::move(NewU));
     878             : }
     879             : 
     880             : ConstantRange
     881        1479 : ConstantRange::umax(const ConstantRange &Other) const {
     882             :   // X umax Y is: range(umax(X_umin, Y_umin),
     883             :   //                    umax(X_umax, Y_umax))
     884        1479 :   if (isEmptySet() || Other.isEmptySet())
     885           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     886        4422 :   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
     887        5896 :   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
     888        1474 :   if (NewU == NewL)
     889         537 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     890        2811 :   return ConstantRange(std::move(NewL), std::move(NewU));
     891             : }
     892             : 
     893             : ConstantRange
     894          17 : ConstantRange::smin(const ConstantRange &Other) const {
     895             :   // X smin Y is: range(smin(X_smin, Y_smin),
     896             :   //                    smin(X_smax, Y_smax))
     897          17 :   if (isEmptySet() || Other.isEmptySet())
     898           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     899          36 :   APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
     900          48 :   APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
     901          12 :   if (NewU == NewL)
     902           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     903          27 :   return ConstantRange(std::move(NewL), std::move(NewU));
     904             : }
     905             : 
     906             : ConstantRange
     907          93 : ConstantRange::umin(const ConstantRange &Other) const {
     908             :   // X umin Y is: range(umin(X_umin, Y_umin),
     909             :   //                    umin(X_umax, Y_umax))
     910          93 :   if (isEmptySet() || Other.isEmptySet())
     911           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     912         264 :   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
     913         352 :   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
     914          88 :   if (NewU == NewL)
     915           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     916         255 :   return ConstantRange(std::move(NewL), std::move(NewU));
     917             : }
     918             : 
     919             : ConstantRange
     920       10877 : ConstantRange::udiv(const ConstantRange &RHS) const {
     921       32626 :   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
     922           7 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     923       10870 :   if (RHS.isFullSet())
     924        1857 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     925             : 
     926       27039 :   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
     927             : 
     928        9013 :   APInt RHS_umin = RHS.getUnsignedMin();
     929        9013 :   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         524 :     if (RHS.getUpper() == 1)
     933         112 :       RHS_umin = RHS.getLower();
     934             :     else
     935         412 :       RHS_umin = 1;
     936             :   }
     937             : 
     938       27039 :   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        9013 :   if (Lower == Upper)
     943         192 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     944             : 
     945       26463 :   return ConstantRange(std::move(Lower), std::move(Upper));
     946             : }
     947             : 
     948             : ConstantRange
     949         293 : ConstantRange::binaryAnd(const ConstantRange &Other) const {
     950         293 :   if (isEmptySet() || Other.isEmptySet())
     951           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     952             : 
     953             :   // TODO: replace this with something less conservative
     954             : 
     955         879 :   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
     956         293 :   if (umin.isAllOnesValue())
     957           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     958        1172 :   return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
     959             : }
     960             : 
     961             : ConstantRange
     962         136 : ConstantRange::binaryOr(const ConstantRange &Other) const {
     963         136 :   if (isEmptySet() || Other.isEmptySet())
     964           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     965             : 
     966             :   // TODO: replace this with something less conservative
     967             : 
     968         408 :   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
     969         136 :   if (umax.isNullValue())
     970           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     971         532 :   return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
     972             : }
     973             : 
     974             : ConstantRange
     975         472 : ConstantRange::shl(const ConstantRange &Other) const {
     976         472 :   if (isEmptySet() || Other.isEmptySet())
     977           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     978             : 
     979         467 :   APInt max = getUnsignedMax();
     980         467 :   APInt Other_umax = Other.getUnsignedMax();
     981             : 
     982             :   // there's overflow!
     983         934 :   if (Other_umax.uge(max.countLeadingZeros()))
     984         195 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     985             : 
     986             :   // FIXME: implement the other tricky cases
     987             : 
     988         272 :   APInt min = getUnsignedMin();
     989         544 :   min <<= Other.getUnsignedMin();
     990         272 :   max <<= Other_umax;
     991             : 
     992        1088 :   return ConstantRange(std::move(min), std::move(max) + 1);
     993             : }
     994             : 
     995             : ConstantRange
     996         706 : ConstantRange::lshr(const ConstantRange &Other) const {
     997         706 :   if (isEmptySet() || Other.isEmptySet())
     998           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     999             : 
    1000        2804 :   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
    1001        2103 :   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
    1002         701 :   if (min == max)
    1003           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
    1004             : 
    1005        2094 :   return ConstantRange(std::move(min), std::move(max));
    1006             : }
    1007             : 
    1008             : ConstantRange
    1009         626 : ConstantRange::ashr(const ConstantRange &Other) const {
    1010         626 :   if (isEmptySet() || Other.isEmptySet())
    1011           5 :     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        2484 :   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        1863 :   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        2484 :   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        1863 :   APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
    1041             : 
    1042             :   APInt max, min;
    1043        1242 :   if (getSignedMin().isNonNegative()) {
    1044             :     // Upper and Lower of LHS are non-negative.
    1045          43 :     min = PosMin;
    1046          43 :     max = PosMax;
    1047        1156 :   } else if (getSignedMax().isNegative()) {
    1048             :     // Upper and Lower of LHS are negative.
    1049           1 :     min = NegMin;
    1050           1 :     max = NegMax;
    1051             :   } else {
    1052             :     // Upper is non-negative and Lower is negative.
    1053         577 :     min = NegMin;
    1054         577 :     max = PosMax;
    1055             :   }
    1056         621 :   if (min == max)
    1057           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
    1058             : 
    1059        1854 :   return ConstantRange(std::move(min), std::move(max));
    1060             : }
    1061             : 
    1062     4378971 : ConstantRange ConstantRange::inverse() const {
    1063     4378971 :   if (isFullSet())
    1064     1321357 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
    1065     3057614 :   if (isEmptySet())
    1066        4024 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
    1067    15267950 :   return ConstantRange(Upper, Lower);
    1068             : }
    1069             : 
    1070        4588 : void ConstantRange::print(raw_ostream &OS) const {
    1071        4588 :   if (isFullSet())
    1072        2203 :     OS << "full-set";
    1073        2385 :   else if (isEmptySet())
    1074           2 :     OS << "empty-set";
    1075             :   else
    1076        7149 :     OS << "[" << Lower << "," << Upper << ")";
    1077        4588 : }
    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       71544 : ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
    1086       71544 :   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      214632 :   ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
    1094             : 
    1095       71560 :   for (unsigned i = 1; i < NumRanges; ++i) {
    1096           8 :     auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
    1097           8 :     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          24 :     CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
    1102             :   }
    1103             : 
    1104       71544 :   return CR;
    1105             : }

Generated by: LCOV version 1.13