LCOV - code coverage report
Current view: top level - lib/IR - ConstantRange.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 517 534 96.8 %
Date: 2018-02-19 03:08:00 Functions: 50 50 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/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     7121658 : ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
      42             :     : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
      43    15620567 :       Upper(Lower) {}
      44             : 
      45     3755882 : ConstantRange::ConstantRange(APInt V)
      46     7511764 :     : Lower(std::move(V)), Upper(Lower + 1) {}
      47             : 
      48     6246280 : 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     6246280 : }
      55             : 
      56      851185 : ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
      57             :                                                    const ConstantRange &CR) {
      58      851185 :   if (CR.isEmptySet())
      59           0 :     return CR;
      60             : 
      61             :   uint32_t W = CR.getBitWidth();
      62      851185 :   switch (Pred) {
      63           0 :   default:
      64           0 :     llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
      65      232510 :   case CmpInst::ICMP_EQ:
      66      232510 :     return CR;
      67             :   case CmpInst::ICMP_NE:
      68      120741 :     if (CR.isSingleElement())
      69      357003 :       return ConstantRange(CR.getUpper(), CR.getLower());
      70        1740 :     return ConstantRange(W);
      71      155857 :   case CmpInst::ICMP_ULT: {
      72      155857 :     APInt UMax(CR.getUnsignedMax());
      73      155857 :     if (UMax.isMinValue())
      74         849 :       return ConstantRange(W, /* empty */ false);
      75      465024 :     return ConstantRange(APInt::getMinValue(W), std::move(UMax));
      76             :   }
      77       54252 :   case CmpInst::ICMP_SLT: {
      78       54252 :     APInt SMax(CR.getSignedMax());
      79       54252 :     if (SMax.isMinSignedValue())
      80         779 :       return ConstantRange(W, /* empty */ false);
      81      160419 :     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
      82             :   }
      83       29168 :   case CmpInst::ICMP_ULE: {
      84       29168 :     APInt UMax(CR.getUnsignedMax());
      85       29168 :     if (UMax.isMaxValue())
      86        1312 :       return ConstantRange(W);
      87      111424 :     return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
      88             :   }
      89       23968 :   case CmpInst::ICMP_SLE: {
      90       23968 :     APInt SMax(CR.getSignedMax());
      91       23968 :     if (SMax.isMaxSignedValue())
      92         339 :       return ConstantRange(W);
      93       94516 :     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
      94             :   }
      95       97744 :   case CmpInst::ICMP_UGT: {
      96       97744 :     APInt UMin(CR.getUnsignedMin());
      97       97744 :     if (UMin.isMaxValue())
      98        1632 :       return ConstantRange(W, /* empty */ false);
      99      480560 :     return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
     100             :   }
     101       80295 :   case CmpInst::ICMP_SGT: {
     102       80295 :     APInt SMin(CR.getSignedMin());
     103       80295 :     if (SMin.isMaxSignedValue())
     104        1166 :       return ConstantRange(W, /* empty */ false);
     105      395645 :     return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
     106             :   }
     107       26909 :   case CmpInst::ICMP_UGE: {
     108       26909 :     APInt UMin(CR.getUnsignedMin());
     109       26909 :     if (UMin.isMinValue())
     110        2984 :       return ConstantRange(W);
     111       95700 :     return ConstantRange(std::move(UMin), APInt::getNullValue(W));
     112             :   }
     113       29741 :   case CmpInst::ICMP_SGE: {
     114       29741 :     APInt SMin(CR.getSignedMin());
     115       29741 :     if (SMin.isMinSignedValue())
     116        1877 :       return ConstantRange(W);
     117      111456 :     return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
     118             :   }
     119             :   }
     120             : }
     121             : 
     122      203575 : 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      407150 :   return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
     129      407150 :       .inverse();
     130             : }
     131             : 
     132      486596 : 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      973192 :   return makeAllowedICmpRegion(Pred, C);
     142             : }
     143             : 
     144      116893 : bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
     145             :                                       APInt &RHS) const {
     146             :   bool Success = false;
     147             : 
     148      116893 :   if (isFullSet() || isEmptySet()) {
     149           4 :     Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
     150           2 :     RHS = APInt(getBitWidth(), 0);
     151             :     Success = true;
     152      116891 :   } else if (auto *OnlyElt = getSingleElement()) {
     153         660 :     Pred = CmpInst::ICMP_EQ;
     154         660 :     RHS = *OnlyElt;
     155             :     Success = true;
     156      116231 :   } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
     157       21366 :     Pred = CmpInst::ICMP_NE;
     158       21366 :     RHS = *OnlyMissingElt;
     159             :     Success = true;
     160      170203 :   } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
     161       60643 :     Pred =
     162       60643 :         getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
     163       60643 :     RHS = getUpper();
     164             :     Success = true;
     165       48714 :   } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
     166       34217 :     Pred =
     167       34217 :         getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
     168       34217 :     RHS = getLower();
     169             :     Success = true;
     170             :   }
     171             : 
     172             :   assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
     173             :          "Bad result!");
     174             : 
     175      116893 :   return Success;
     176             : }
     177             : 
     178             : ConstantRange
     179     2731844 : 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     1172280 :       [](const ConstantRange &CR0, const ConstantRange &CR1) {
     190     2344560 :     return CR0.inverse().unionWith(CR1.inverse()).inverse();
     191     2344560 :   };
     192             : 
     193             :   assert(BinOp >= Instruction::BinaryOpsBegin &&
     194             :          BinOp < Instruction::BinaryOpsEnd && "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     5463688 :   ConstantRange Result(BitWidth);
     203             : 
     204     2731844 :   switch (BinOp) {
     205           0 :   default:
     206             :     // Conservative answer: empty set
     207           0 :     return ConstantRange(BitWidth, false);
     208             : 
     209     2731736 :   case Instruction::Add:
     210     2731736 :     if (auto *C = Other.getSingleElement())
     211     2730668 :       if (C->isNullValue())
     212             :         // Full set: nothing signed / unsigned wraps when added to 0.
     213     1560007 :         return ConstantRange(BitWidth);
     214     1171729 :     if (NoWrapKind & OBO::NoUnsignedWrap)
     215      673474 :       Result =
     216     2020422 :           SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
     217     2020422 :                                                 -Other.getUnsignedMax()));
     218     1171729 :     if (NoWrapKind & OBO::NoSignedWrap) {
     219      498266 :       const APInt &SignedMin = Other.getSignedMin();
     220      498266 :       const APInt &SignedMax = Other.getSignedMax();
     221      498266 :       if (SignedMax.isStrictlyPositive())
     222      337972 :         Result = SubsetIntersect(
     223             :             Result,
     224     1013916 :             ConstantRange(APInt::getSignedMinValue(BitWidth),
     225     1013916 :                           APInt::getSignedMinValue(BitWidth) - SignedMax));
     226      996532 :       if (SignedMin.isNegative())
     227      160716 :         Result = SubsetIntersect(
     228             :             Result,
     229      803580 :             ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
     230      321432 :                           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             :   }
     259             : }
     260             : 
     261    21376101 : bool ConstantRange::isFullSet() const {
     262    48731965 :   return Lower == Upper && Lower.isMaxValue();
     263             : }
     264             : 
     265    12199590 : bool ConstantRange::isEmptySet() const {
     266    26617388 :   return Lower == Upper && Lower.isMinValue();
     267             : }
     268             : 
     269     7153324 : bool ConstantRange::isWrappedSet() const {
     270    14306648 :   return Lower.ugt(Upper);
     271             : }
     272             : 
     273        3796 : bool ConstantRange::isSignWrappedSet() const {
     274        9858 :   return contains(APInt::getSignedMaxValue(getBitWidth())) &&
     275       11407 :          contains(APInt::getSignedMinValue(getBitWidth()));
     276             : }
     277             : 
     278           6 : APInt ConstantRange::getSetSize() const {
     279           6 :   if (isFullSet())
     280           1 :     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
     281             : 
     282             :   // This is also correct for wrapped sets.
     283          20 :   return (Upper - Lower).zext(getBitWidth()+1);
     284             : }
     285             : 
     286             : bool
     287      219799 : ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
     288             :   assert(getBitWidth() == Other.getBitWidth());
     289      219799 :   if (isFullSet())
     290             :     return false;
     291      142512 :   if (Other.isFullSet())
     292             :     return true;
     293      854760 :   return (Upper - Lower).ult(Other.Upper - Other.Lower);
     294             : }
     295             : 
     296             : bool
     297      112399 : ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
     298             :   assert(MaxSize && "MaxSize can't be 0.");
     299             :   // If this a full set, we need special handling to avoid needing an extra bit
     300             :   // to represent the size.
     301      112399 :   if (isFullSet())
     302          32 :     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
     303             : 
     304      449532 :   return (Upper - Lower).ugt(MaxSize);
     305             : }
     306             : 
     307     2010724 : APInt ConstantRange::getUnsignedMax() const {
     308     2010724 :   if (isFullSet() || isWrappedSet())
     309             :     return APInt::getMaxValue(getBitWidth());
     310     1710296 :   return getUpper() - 1;
     311             : }
     312             : 
     313      577851 : APInt ConstantRange::getUnsignedMin() const {
     314      640586 :   if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
     315      110080 :     return APInt::getMinValue(getBitWidth());
     316             :   return getLower();
     317             : }
     318             : 
     319     1042151 : APInt ConstantRange::getSignedMax() const {
     320     1985154 :   if (isFullSet() || Lower.sgt(Upper))
     321      113983 :     return APInt::getSignedMaxValue(getBitWidth());
     322      928168 :   return getUpper() - 1;
     323             : }
     324             : 
     325     2521403 : APInt ConstantRange::getSignedMin() const {
     326     4791164 :   if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
     327      268006 :     return APInt::getSignedMinValue(getBitWidth());
     328             :   return getLower();
     329             : }
     330             : 
     331      360795 : bool ConstantRange::contains(const APInt &V) const {
     332      721590 :   if (Lower == Upper)
     333         610 :     return isFullSet();
     334             : 
     335      360185 :   if (!isWrappedSet())
     336      594250 :     return Lower.ule(V) && V.ult(Upper);
     337       89031 :   return Lower.ule(V) || V.ult(Upper);
     338             : }
     339             : 
     340     3121778 : bool ConstantRange::contains(const ConstantRange &Other) const {
     341     3121778 :   if (isFullSet() || Other.isEmptySet()) return true;
     342     1557746 :   if (isEmptySet() || Other.isFullSet()) return false;
     343             : 
     344     1158086 :   if (!isWrappedSet()) {
     345      648139 :     if (Other.isWrappedSet())
     346             :       return false;
     347             : 
     348     2063006 :     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
     349             :   }
     350             : 
     351      509947 :   if (!Other.isWrappedSet())
     352      898557 :     return Other.getUpper().ule(Upper) ||
     353      224177 :            Lower.ule(Other.getLower());
     354             : 
     355      467409 :   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
     356             : }
     357             : 
     358       24764 : ConstantRange ConstantRange::subtract(const APInt &Val) const {
     359             :   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
     360             :   // If the set is empty or full, don't modify the endpoints.
     361       49528 :   if (Lower == Upper) 
     362         135 :     return *this;
     363      123145 :   return ConstantRange(Lower - Val, Upper - Val);
     364             : }
     365             : 
     366       20272 : ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
     367       20272 :   return intersectWith(CR.inverse());
     368             : }
     369             : 
     370      719002 : ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
     371             :   assert(getBitWidth() == CR.getBitWidth() && 
     372             :          "ConstantRange types don't agree!");
     373             : 
     374             :   // Handle common cases.
     375      719002 :   if (   isEmptySet() || CR.isFullSet()) return *this;
     376      748638 :   if (CR.isEmptySet() ||    isFullSet()) return CR;
     377             : 
     378      468251 :   if (!isWrappedSet() && CR.isWrappedSet())
     379       23290 :     return CR.intersectWith(*this);
     380             : 
     381      421671 :   if (!isWrappedSet() && !CR.isWrappedSet()) {
     382      301342 :     if (Lower.ult(CR.Lower)) {
     383       19034 :       if (Upper.ule(CR.Lower))
     384          22 :         return ConstantRange(getBitWidth(), false);
     385             : 
     386       18990 :       if (Upper.ult(CR.Upper))
     387        3489 :         return ConstantRange(CR.Lower, Upper);
     388             : 
     389        8332 :       return CR;
     390             :     }
     391      282308 :     if (Upper.ult(CR.Upper))
     392        1199 :       return *this;
     393             : 
     394      139955 :     if (Lower.ult(CR.Upper))
     395      419685 :       return ConstantRange(Lower, CR.Upper);
     396             : 
     397          60 :     return ConstantRange(getBitWidth(), false);
     398             :   }
     399             : 
     400      240658 :   if (isWrappedSet() && !CR.isWrappedSet()) {
     401      142876 :     if (CR.Lower.ult(Upper)) {
     402       86764 :       if (CR.Upper.ult(Upper))
     403       17991 :         return CR;
     404             : 
     405       50782 :       if (CR.Upper.ule(Lower))
     406       47631 :         return ConstantRange(CR.Lower, Upper);
     407             : 
     408        9514 :       if (isSizeStrictlySmallerThan(CR))
     409        4872 :         return *this;
     410        4642 :       return CR;
     411             :     }
     412       56112 :     if (CR.Lower.ult(Lower)) {
     413       47766 :       if (CR.Upper.ule(Lower))
     414          78 :         return ConstantRange(getBitWidth(), false);
     415             : 
     416       71415 :       return ConstantRange(Lower, CR.Upper);
     417             :     }
     418        4173 :     return CR;
     419             :   }
     420             : 
     421       97782 :   if (CR.Upper.ult(Upper)) {
     422       57468 :     if (CR.Lower.ult(Upper)) {
     423        8513 :       if (isSizeStrictlySmallerThan(CR))
     424          18 :         return *this;
     425        8495 :       return CR;
     426             :     }
     427             : 
     428       40442 :     if (CR.Lower.ult(Lower))
     429        8166 :       return ConstantRange(Lower, CR.Upper);
     430             : 
     431       17499 :     return CR;
     432             :   }
     433       40314 :   if (CR.Upper.ule(Lower)) {
     434       29646 :     if (CR.Lower.ult(Lower))
     435          81 :       return *this;
     436             : 
     437       44226 :     return ConstantRange(CR.Lower, Upper);
     438             :   }
     439        5334 :   if (isSizeStrictlySmallerThan(CR))
     440         222 :     return *this;
     441        5112 :   return CR;
     442             : }
     443             : 
     444     1440595 : ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
     445             :   assert(getBitWidth() == CR.getBitWidth() && 
     446             :          "ConstantRange types don't agree!");
     447             : 
     448     1440595 :   if (   isFullSet() || CR.isEmptySet()) return *this;
     449     2544206 :   if (CR.isFullSet() ||    isEmptySet()) return CR;
     450             : 
     451      369417 :   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
     452             : 
     453      230568 :   if (!isWrappedSet() && !CR.isWrappedSet()) {
     454      233021 :     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
     455             :       // If the two ranges are disjoint, find the smaller gap and bridge it.
     456        1866 :       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
     457         622 :       if (d1.ult(d2))
     458         789 :         return ConstantRange(Lower, CR.Upper);
     459        1077 :       return ConstantRange(CR.Lower, Upper);
     460             :     }
     461             : 
     462       77167 :     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
     463      385835 :     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
     464             : 
     465      123116 :     if (L.isNullValue() && U.isNullValue())
     466           0 :       return ConstantRange(getBitWidth());
     467             : 
     468      231501 :     return ConstantRange(std::move(L), std::move(U));
     469             :   }
     470             : 
     471       74990 :   if (!CR.isWrappedSet()) {
     472             :     // ------U   L-----  and  ------U   L----- : this
     473             :     //   L--U                            L--U  : CR
     474      142424 :     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
     475         873 :       return *this;
     476             : 
     477             :     // ------U   L----- : this
     478             :     //    L---------U   : CR
     479       71079 :     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
     480       24097 :       return ConstantRange(getBitWidth());
     481             : 
     482             :     // ----U       L---- : this
     483             :     //       L---U       : CR
     484             :     //    <d1>  <d2>
     485       45376 :     if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
     486       45286 :       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
     487       22643 :       if (d1.ult(d2))
     488         417 :         return ConstantRange(Lower, CR.Upper);
     489       67512 :       return ConstantRange(CR.Lower, Upper);
     490             :     }
     491             : 
     492             :     // ----U     L----- : this
     493             :     //        L----U    : CR
     494          90 :     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
     495          36 :       return ConstantRange(CR.Lower, Upper);
     496             : 
     497             :     // ------U    L---- : this
     498             :     //    L-----U       : CR
     499             :     assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
     500             :            "ConstantRange::unionWith missed a case with one range wrapped");
     501         198 :     return ConstantRange(Lower, CR.Upper);
     502             :   }
     503             : 
     504             :   // ------U    L----  and  ------U    L---- : this
     505             :   // -U  L-----------  and  ------------U  L : CR
     506       81863 :   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
     507          59 :     return ConstantRange(getBitWidth());
     508             : 
     509       27240 :   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
     510       27240 :   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
     511             : 
     512       81720 :   return ConstantRange(std::move(L), std::move(U));
     513             : }
     514             : 
     515        1592 : ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
     516             :                                     uint32_t ResultBitWidth) const {
     517        1592 :   switch (CastOp) {
     518           0 :   default:
     519           0 :     llvm_unreachable("unsupported cast type");
     520         212 :   case Instruction::Trunc:
     521         212 :     return truncate(ResultBitWidth);
     522          46 :   case Instruction::SExt:
     523          46 :     return signExtend(ResultBitWidth);
     524        1219 :   case Instruction::ZExt:
     525        1219 :     return zeroExtend(ResultBitWidth);
     526          17 :   case Instruction::BitCast:
     527          17 :     return *this;
     528             :   case Instruction::FPToUI:
     529             :   case Instruction::FPToSI:
     530          50 :     if (getBitWidth() == ResultBitWidth)
     531          50 :       return *this;
     532             :     else
     533           0 :       return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     534             :   case Instruction::UIToFP: {
     535             :     // TODO: use input range if available
     536             :     auto BW = getBitWidth();
     537          82 :     APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
     538          82 :     APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
     539         123 :     return ConstantRange(std::move(Min), std::move(Max));
     540             :   }
     541             :   case Instruction::SIToFP: {
     542             :     // TODO: use input range if available
     543             :     auto BW = getBitWidth();
     544          14 :     APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
     545          14 :     APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
     546          21 :     return ConstantRange(std::move(SMin), std::move(SMax));
     547             :   }
     548             :   case Instruction::FPTrunc:
     549             :   case Instruction::FPExt:
     550             :   case Instruction::IntToPtr:
     551             :   case Instruction::PtrToInt:
     552             :   case Instruction::AddrSpaceCast:
     553             :     // Conservatively return full set.
     554           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     555             :   };
     556             : }
     557             : 
     558       28603 : ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
     559       28603 :   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
     560             : 
     561             :   unsigned SrcTySize = getBitWidth();
     562             :   assert(SrcTySize < DstTySize && "Not a value extension");
     563       28602 :   if (isFullSet() || isWrappedSet()) {
     564             :     // Change into [0, 1 << src bit width)
     565             :     APInt LowerExt(DstTySize, 0);
     566       40320 :     if (!Upper) // special case: [X, 0) -- not really wrapping around
     567          26 :       LowerExt = Lower.zext(DstTySize);
     568             :     return ConstantRange(std::move(LowerExt),
     569       80640 :                          APInt::getOneBitSet(DstTySize, SrcTySize));
     570             :   }
     571             : 
     572       25326 :   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
     573             : }
     574             : 
     575       15774 : ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
     576       15774 :   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
     577             : 
     578             :   unsigned SrcTySize = getBitWidth();
     579             :   assert(SrcTySize < DstTySize && "Not a value extension");
     580             : 
     581             :   // special case: [X, INT_MIN) -- not really wrapping around
     582       15773 :   if (Upper.isMinSignedValue())
     583          99 :     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
     584             : 
     585       15740 :   if (isFullSet() || isSignWrappedSet()) {
     586       28726 :     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
     587       57452 :                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
     588             :   }
     589             : 
     590        4131 :   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
     591             : }
     592             : 
     593      187901 : ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
     594             :   assert(getBitWidth() > DstTySize && "Not a value truncation");
     595      187901 :   if (isEmptySet())
     596           1 :     return ConstantRange(DstTySize, /*isFullSet=*/false);
     597      187900 :   if (isFullSet())
     598        2427 :     return ConstantRange(DstTySize, /*isFullSet=*/true);
     599             : 
     600      370946 :   APInt LowerDiv(Lower), UpperDiv(Upper);
     601      370946 :   ConstantRange Union(DstTySize, /*isFullSet=*/false);
     602             : 
     603             :   // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
     604             :   // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
     605             :   // then we do the union with [MaxValue, Upper)
     606      185473 :   if (isWrappedSet()) {
     607             :     // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
     608             :     // truncated range.
     609      123497 :     if (Upper.getActiveBits() > DstTySize ||
     610             :         Upper.countTrailingOnes() == DstTySize)
     611       30016 :       return ConstantRange(DstTySize, /*isFullSet=*/true);
     612             : 
     613      184632 :     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
     614       46158 :     UpperDiv.setAllBits();
     615             : 
     616             :     // Union covers the MaxValue case, so return if the remaining range is just
     617             :     // MaxValue(DstTy).
     618       46158 :     if (LowerDiv == UpperDiv)
     619             :       return Union;
     620             :   }
     621             : 
     622             :   // Chop off the most significant bits that are past the destination bitwidth.
     623      154727 :   if (LowerDiv.getActiveBits() > DstTySize) {
     624             :     // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
     625       92814 :     APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
     626       46407 :     LowerDiv -= Adjust;
     627       46407 :     UpperDiv -= Adjust;
     628             :   }
     629             : 
     630             :   unsigned UpperDivWidth = UpperDiv.getActiveBits();
     631      154727 :   if (UpperDivWidth <= DstTySize)
     632      222435 :     return ConstantRange(LowerDiv.trunc(DstTySize),
     633      222435 :                          UpperDiv.trunc(DstTySize)).unionWith(Union);
     634             : 
     635             :   // The truncated value wraps around. Check if we can do better than fullset.
     636       80582 :   if (UpperDivWidth == DstTySize + 1) {
     637             :     // Clear the MSB so that UpperDiv wraps around.
     638             :     UpperDiv.clearBit(DstTySize);
     639        3617 :     if (UpperDiv.ult(LowerDiv))
     640          54 :       return ConstantRange(LowerDiv.trunc(DstTySize),
     641          54 :                            UpperDiv.trunc(DstTySize)).unionWith(Union);
     642             :   }
     643             : 
     644       80564 :   return ConstantRange(DstTySize, /*isFullSet=*/true);
     645             : }
     646             : 
     647        1541 : ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
     648             :   unsigned SrcTySize = getBitWidth();
     649        1541 :   if (SrcTySize > DstTySize)
     650          24 :     return truncate(DstTySize);
     651        1517 :   if (SrcTySize < DstTySize)
     652         168 :     return zeroExtend(DstTySize);
     653        1349 :   return *this;
     654             : }
     655             : 
     656         289 : ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
     657             :   unsigned SrcTySize = getBitWidth();
     658         289 :   if (SrcTySize > DstTySize)
     659           1 :     return truncate(DstTySize);
     660         288 :   if (SrcTySize < DstTySize)
     661          54 :     return signExtend(DstTySize);
     662         234 :   return *this;
     663             : }
     664             : 
     665       10486 : ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
     666             :                                       const ConstantRange &Other) const {
     667             :   assert(BinOp >= Instruction::BinaryOpsBegin &&
     668             :          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
     669             : 
     670       10486 :   switch (BinOp) {
     671        8321 :   case Instruction::Add:
     672        8321 :     return add(Other);
     673           1 :   case Instruction::Sub:
     674           1 :     return sub(Other);
     675         138 :   case Instruction::Mul:
     676         138 :     return multiply(Other);
     677          87 :   case Instruction::UDiv:
     678          87 :     return udiv(Other);
     679         436 :   case Instruction::Shl:
     680         436 :     return shl(Other);
     681         522 :   case Instruction::LShr:
     682         522 :     return lshr(Other);
     683         545 :   case Instruction::AShr:
     684         545 :     return ashr(Other);
     685         279 :   case Instruction::And:
     686         279 :     return binaryAnd(Other);
     687         128 :   case Instruction::Or:
     688         128 :     return binaryOr(Other);
     689             :   // Note: floating point operations applied to abstract ranges are just
     690             :   // ideal integer operations with a lossy representation
     691          17 :   case Instruction::FAdd:
     692          17 :     return add(Other);
     693           4 :   case Instruction::FSub:
     694           4 :     return sub(Other);
     695           8 :   case Instruction::FMul:
     696           8 :     return multiply(Other);
     697             :   default:
     698             :     // Conservatively return full set.
     699           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     700             :   }
     701             : }
     702             : 
     703             : ConstantRange
     704      146752 : ConstantRange::add(const ConstantRange &Other) const {
     705      146752 :   if (isEmptySet() || Other.isEmptySet())
     706           8 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     707      146744 :   if (isFullSet() || Other.isFullSet())
     708       74376 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     709             : 
     710       72368 :   APInt NewLower = getLower() + Other.getLower();
     711      144736 :   APInt NewUpper = getUpper() + Other.getUpper() - 1;
     712       72368 :   if (NewLower == NewUpper)
     713          42 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     714             : 
     715      289304 :   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
     716      118162 :   if (X.isSizeStrictlySmallerThan(*this) ||
     717       45836 :       X.isSizeStrictlySmallerThan(Other))
     718             :     // We've wrapped, therefore, full set.
     719       26490 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     720             :   return X;
     721             : }
     722             : 
     723          28 : ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
     724             :   // Calculate the subset of this range such that "X + Other" is
     725             :   // guaranteed not to wrap (overflow) for all X in this subset.
     726             :   // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
     727             :   // passing a single element range.
     728             :   auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
     729          84 :                                       ConstantRange(Other),
     730          56 :                                       OverflowingBinaryOperator::NoSignedWrap);
     731          56 :   auto NSWConstrainedRange = intersectWith(NSWRange);
     732             : 
     733          84 :   return NSWConstrainedRange.add(ConstantRange(Other));
     734             : }
     735             : 
     736             : ConstantRange
     737          20 : ConstantRange::sub(const ConstantRange &Other) const {
     738          20 :   if (isEmptySet() || Other.isEmptySet())
     739           6 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     740          14 :   if (isFullSet() || Other.isFullSet())
     741           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     742             : 
     743          18 :   APInt NewLower = getLower() - Other.getUpper() + 1;
     744           9 :   APInt NewUpper = getUpper() - Other.getLower();
     745           9 :   if (NewLower == NewUpper)
     746           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     747             : 
     748          36 :   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
     749          18 :   if (X.isSizeStrictlySmallerThan(*this) ||
     750           9 :       X.isSizeStrictlySmallerThan(Other))
     751             :     // We've wrapped, therefore, full set.
     752           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     753             :   return X;
     754             : }
     755             : 
     756             : ConstantRange
     757      105025 : ConstantRange::multiply(const ConstantRange &Other) const {
     758             :   // TODO: If either operand is a single element and the multiply is known to
     759             :   // be non-wrapping, round the result min and max value to the appropriate
     760             :   // multiple of that element. If wrapping is possible, at least adjust the
     761             :   // range according to the greatest power-of-two factor of the single element.
     762             : 
     763      105025 :   if (isEmptySet() || Other.isEmptySet())
     764           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     765             : 
     766             :   // Multiplication is signedness-independent. However different ranges can be
     767             :   // obtained depending on how the input ranges are treated. These different
     768             :   // ranges are all conservatively correct, but one might be better than the
     769             :   // other. We calculate two ranges; one treating the inputs as unsigned
     770             :   // and the other signed, then return the smallest of these ranges.
     771             : 
     772             :   // Unsigned range first.
     773      315060 :   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
     774      315060 :   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
     775      315060 :   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
     776      315060 :   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
     777             : 
     778      210040 :   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
     779      525100 :                                             this_max * Other_max + 1);
     780      210040 :   ConstantRange UR = Result_zext.truncate(getBitWidth());
     781             : 
     782             :   // If the unsigned range doesn't wrap, and isn't negative then it's a range
     783             :   // from one positive number to another which is as good as we can generate.
     784             :   // In this case, skip the extra work of generating signed ranges which aren't
     785             :   // going to be better than this range.
     786      210027 :   if (!UR.isWrappedSet() &&
     787       78311 :       (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
     788             :     return UR;
     789             : 
     790             :   // Now the signed range. Because we could be dealing with negative numbers
     791             :   // here, the lower bound is the smallest of the cartesian product of the
     792             :   // lower and upper ranges; for example:
     793             :   //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
     794             :   // Similarly for the upper bound, swapping min for max.
     795             : 
     796      313032 :   this_min = getSignedMin().sext(getBitWidth() * 2);
     797      313032 :   this_max = getSignedMax().sext(getBitWidth() * 2);
     798      313032 :   Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
     799      313032 :   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
     800             :   
     801       78258 :   auto L = {this_min * Other_min, this_min * Other_max,
     802      469548 :             this_max * Other_min, this_max * Other_max};
     803             :   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
     804      469548 :   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
     805      156516 :   ConstantRange SR = Result_sext.truncate(getBitWidth());
     806             : 
     807       78258 :   return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
     808             : }
     809             : 
     810             : ConstantRange
     811        4397 : ConstantRange::smax(const ConstantRange &Other) const {
     812             :   // X smax Y is: range(smax(X_smin, Y_smin),
     813             :   //                    smax(X_smax, Y_smax))
     814        4397 :   if (isEmptySet() || Other.isEmptySet())
     815           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     816       13176 :   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
     817       17568 :   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
     818        4392 :   if (NewU == NewL)
     819         440 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     820       11856 :   return ConstantRange(std::move(NewL), std::move(NewU));
     821             : }
     822             : 
     823             : ConstantRange
     824        1267 : ConstantRange::umax(const ConstantRange &Other) const {
     825             :   // X umax Y is: range(umax(X_umin, Y_umin),
     826             :   //                    umax(X_umax, Y_umax))
     827        1267 :   if (isEmptySet() || Other.isEmptySet())
     828           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     829        3786 :   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
     830        5048 :   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
     831        1262 :   if (NewU == NewL)
     832         446 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     833        2448 :   return ConstantRange(std::move(NewL), std::move(NewU));
     834             : }
     835             : 
     836             : ConstantRange
     837          17 : ConstantRange::smin(const ConstantRange &Other) const {
     838             :   // X smin Y is: range(smin(X_smin, Y_smin),
     839             :   //                    smin(X_smax, Y_smax))
     840          17 :   if (isEmptySet() || Other.isEmptySet())
     841           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     842          36 :   APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
     843          48 :   APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
     844          12 :   if (NewU == NewL)
     845           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     846          27 :   return ConstantRange(std::move(NewL), std::move(NewU));
     847             : }
     848             : 
     849             : ConstantRange
     850          93 : ConstantRange::umin(const ConstantRange &Other) const {
     851             :   // X umin Y is: range(umin(X_umin, Y_umin),
     852             :   //                    umin(X_umax, Y_umax))
     853          93 :   if (isEmptySet() || Other.isEmptySet())
     854           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     855         264 :   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
     856         352 :   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
     857          88 :   if (NewU == NewL)
     858           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     859         255 :   return ConstantRange(std::move(NewL), std::move(NewU));
     860             : }
     861             : 
     862             : ConstantRange
     863        5237 : ConstantRange::udiv(const ConstantRange &RHS) const {
     864       15706 :   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
     865           7 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     866        5230 :   if (RHS.isFullSet())
     867         458 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     868             : 
     869       14316 :   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
     870             : 
     871        4772 :   APInt RHS_umin = RHS.getUnsignedMin();
     872        4772 :   if (RHS_umin.isNullValue()) {
     873             :     // We want the lowest value in RHS excluding zero. Usually that would be 1
     874             :     // except for a range in the form of [X, 1) in which case it would be X.
     875         102 :     if (RHS.getUpper() == 1)
     876           0 :       RHS_umin = RHS.getLower();
     877             :     else
     878         102 :       RHS_umin = 1;
     879             :   }
     880             : 
     881       14316 :   APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
     882             : 
     883             :   // If the LHS is Full and the RHS is a wrapped interval containing 1 then
     884             :   // this could occur.
     885        4772 :   if (Lower == Upper)
     886          77 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     887             : 
     888       14085 :   return ConstantRange(std::move(Lower), std::move(Upper));
     889             : }
     890             : 
     891             : ConstantRange
     892         279 : ConstantRange::binaryAnd(const ConstantRange &Other) const {
     893         279 :   if (isEmptySet() || Other.isEmptySet())
     894           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     895             : 
     896             :   // TODO: replace this with something less conservative
     897             : 
     898         837 :   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
     899         279 :   if (umin.isAllOnesValue())
     900           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     901        1116 :   return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
     902             : }
     903             : 
     904             : ConstantRange
     905         128 : ConstantRange::binaryOr(const ConstantRange &Other) const {
     906         128 :   if (isEmptySet() || Other.isEmptySet())
     907           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     908             : 
     909             :   // TODO: replace this with something less conservative
     910             : 
     911         384 :   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
     912         128 :   if (umax.isNullValue())
     913           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     914         500 :   return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
     915             : }
     916             : 
     917             : ConstantRange
     918         451 : ConstantRange::shl(const ConstantRange &Other) const {
     919         451 :   if (isEmptySet() || Other.isEmptySet())
     920           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     921             : 
     922         446 :   APInt max = getUnsignedMax();
     923         446 :   APInt Other_umax = Other.getUnsignedMax();
     924             : 
     925             :   // there's overflow!
     926         892 :   if (Other_umax.uge(max.countLeadingZeros()))
     927         184 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     928             : 
     929             :   // FIXME: implement the other tricky cases
     930             : 
     931         262 :   APInt min = getUnsignedMin();
     932         524 :   min <<= Other.getUnsignedMin();
     933         262 :   max <<= Other_umax;
     934             : 
     935        1048 :   return ConstantRange(std::move(min), std::move(max) + 1);
     936             : }
     937             : 
     938             : ConstantRange
     939         537 : ConstantRange::lshr(const ConstantRange &Other) const {
     940         537 :   if (isEmptySet() || Other.isEmptySet())
     941           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     942             : 
     943        2128 :   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
     944        1596 :   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
     945         532 :   if (min == max)
     946           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     947             : 
     948        1587 :   return ConstantRange(std::move(min), std::move(max));
     949             : }
     950             : 
     951             : ConstantRange
     952         562 : ConstantRange::ashr(const ConstantRange &Other) const {
     953         562 :   if (isEmptySet() || Other.isEmptySet())
     954           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     955             : 
     956             :   // May straddle zero, so handle both positive and negative cases.
     957             :   // 'PosMax' is the upper bound of the result of the ashr
     958             :   // operation, when Upper of the LHS of ashr is a non-negative.
     959             :   // number. Since ashr of a non-negative number will result in a
     960             :   // smaller number, the Upper value of LHS is shifted right with
     961             :   // the minimum value of 'Other' instead of the maximum value.
     962        2228 :   APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
     963             : 
     964             :   // 'PosMin' is the lower bound of the result of the ashr
     965             :   // operation, when Lower of the LHS is a non-negative number.
     966             :   // Since ashr of a non-negative number will result in a smaller
     967             :   // number, the Lower value of LHS is shifted right with the
     968             :   // maximum value of 'Other'.
     969        1671 :   APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
     970             : 
     971             :   // 'NegMax' is the upper bound of the result of the ashr
     972             :   // operation, when Upper of the LHS of ashr is a negative number.
     973             :   // Since 'ashr' of a negative number will result in a bigger
     974             :   // number, the Upper value of LHS is shifted right with the
     975             :   // maximum value of 'Other'.
     976        2228 :   APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
     977             : 
     978             :   // 'NegMin' is the lower bound of the result of the ashr
     979             :   // operation, when Lower of the LHS of ashr is a negative number.
     980             :   // Since 'ashr' of a negative number will result in a bigger
     981             :   // number, the Lower value of LHS is shifted right with the
     982             :   // minimum value of 'Other'.
     983        1671 :   APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
     984             : 
     985             :   APInt max, min;
     986        1114 :   if (getSignedMin().isNonNegative()) {
     987             :     // Upper and Lower of LHS are non-negative.
     988          43 :     min = PosMin;
     989          43 :     max = PosMax;
     990        1028 :   } else if (getSignedMax().isNegative()) {
     991             :     // Upper and Lower of LHS are negative.
     992           1 :     min = NegMin;
     993           1 :     max = NegMax;
     994             :   } else {
     995             :     // Upper is non-negative and Lower is negative.
     996         513 :     min = NegMin;
     997         513 :     max = PosMax;
     998             :   }
     999         557 :   if (min == max)
    1000           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
    1001             : 
    1002        1662 :   return ConstantRange(std::move(min), std::move(max));
    1003             : }
    1004             : 
    1005     3942886 : ConstantRange ConstantRange::inverse() const {
    1006     3942886 :   if (isFullSet())
    1007     1185506 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
    1008     2757380 :   if (isEmptySet())
    1009        4048 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
    1010    13766660 :   return ConstantRange(Upper, Lower);
    1011             : }
    1012             : 
    1013        4216 : void ConstantRange::print(raw_ostream &OS) const {
    1014        4216 :   if (isFullSet())
    1015        2072 :     OS << "full-set";
    1016        2144 :   else if (isEmptySet())
    1017           2 :     OS << "empty-set";
    1018             :   else
    1019        6426 :     OS << "[" << Lower << "," << Upper << ")";
    1020        4216 : }
    1021             : 
    1022             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    1023             : LLVM_DUMP_METHOD void ConstantRange::dump() const {
    1024             :   print(dbgs());
    1025             : }
    1026             : #endif
    1027             : 
    1028       69741 : ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
    1029       69741 :   const unsigned NumRanges = Ranges.getNumOperands() / 2;
    1030             :   assert(NumRanges >= 1 && "Must have at least one range!");
    1031             :   assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
    1032             : 
    1033             :   auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
    1034             :   auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
    1035             : 
    1036      209223 :   ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
    1037             : 
    1038       69757 :   for (unsigned i = 1; i < NumRanges; ++i) {
    1039           8 :     auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
    1040           8 :     auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
    1041             : 
    1042             :     // Note: unionWith will potentially create a range that contains values not
    1043             :     // contained in any of the original N ranges.
    1044          24 :     CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
    1045             :   }
    1046             : 
    1047       69741 :   return CR;
    1048             : }

Generated by: LCOV version 1.13