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-05-20 00:06:23 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/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     8257970 : ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
      43             :     : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
      44    18056593 :       Upper(Lower) {}
      45             : 
      46     3999972 : ConstantRange::ConstantRange(APInt V)
      47     7999944 :     : Lower(std::move(V)), Upper(Lower + 1) {}
      48             : 
      49     6954050 : 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     6954050 : }
      56             : 
      57      890477 : ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
      58             :                                                    const ConstantRange &CR) {
      59      890477 :   if (CR.isEmptySet())
      60           0 :     return CR;
      61             : 
      62             :   uint32_t W = CR.getBitWidth();
      63      890477 :   switch (Pred) {
      64           0 :   default:
      65           0 :     llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
      66      238027 :   case CmpInst::ICMP_EQ:
      67      238027 :     return CR;
      68             :   case CmpInst::ICMP_NE:
      69      124215 :     if (CR.isSingleElement())
      70      367299 :       return ConstantRange(CR.getUpper(), CR.getLower());
      71        1782 :     return ConstantRange(W);
      72      159855 :   case CmpInst::ICMP_ULT: {
      73      159855 :     APInt UMax(CR.getUnsignedMax());
      74      159855 :     if (UMax.isMinValue())
      75         949 :       return ConstantRange(W, /* empty */ false);
      76      476718 :     return ConstantRange(APInt::getMinValue(W), std::move(UMax));
      77             :   }
      78       61335 :   case CmpInst::ICMP_SLT: {
      79       61335 :     APInt SMax(CR.getSignedMax());
      80       61335 :     if (SMax.isMinSignedValue())
      81         831 :       return ConstantRange(W, /* empty */ false);
      82      181512 :     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
      83             :   }
      84       28325 :   case CmpInst::ICMP_ULE: {
      85       28325 :     APInt UMax(CR.getUnsignedMax());
      86       28325 :     if (UMax.isMaxValue())
      87        1461 :       return ConstantRange(W);
      88      107456 :     return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
      89             :   }
      90       30689 :   case CmpInst::ICMP_SLE: {
      91       30689 :     APInt SMax(CR.getSignedMax());
      92       30689 :     if (SMax.isMaxSignedValue())
      93         386 :       return ConstantRange(W);
      94      121212 :     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
      95             :   }
      96       99246 :   case CmpInst::ICMP_UGT: {
      97       99246 :     APInt UMin(CR.getUnsignedMin());
      98       99246 :     if (UMin.isMaxValue())
      99        1691 :       return ConstantRange(W, /* empty */ false);
     100      487775 :     return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
     101             :   }
     102       89300 :   case CmpInst::ICMP_SGT: {
     103       89300 :     APInt SMin(CR.getSignedMin());
     104       89300 :     if (SMin.isMaxSignedValue())
     105         939 :       return ConstantRange(W, /* empty */ false);
     106      441805 :     return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
     107             :   }
     108       26838 :   case CmpInst::ICMP_UGE: {
     109       26838 :     APInt UMin(CR.getUnsignedMin());
     110       26838 :     if (UMin.isMinValue())
     111        3155 :       return ConstantRange(W);
     112       94732 :     return ConstantRange(std::move(UMin), APInt::getNullValue(W));
     113             :   }
     114       32647 :   case CmpInst::ICMP_SGE: {
     115       32647 :     APInt SMin(CR.getSignedMin());
     116       32647 :     if (SMin.isMinSignedValue())
     117        2059 :       return ConstantRange(W);
     118      122352 :     return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
     119             :   }
     120             :   }
     121             : }
     122             : 
     123      227426 : 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      454852 :   return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
     130      454852 :       .inverse();
     131             : }
     132             : 
     133      499507 : 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      999014 :   return makeAllowedICmpRegion(Pred, C);
     143             : }
     144             : 
     145      128299 : bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
     146             :                                       APInt &RHS) const {
     147             :   bool Success = false;
     148             : 
     149      128299 :   if (isFullSet() || isEmptySet()) {
     150           4 :     Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
     151           2 :     RHS = APInt(getBitWidth(), 0);
     152             :     Success = true;
     153      128297 :   } else if (auto *OnlyElt = getSingleElement()) {
     154         725 :     Pred = CmpInst::ICMP_EQ;
     155         725 :     RHS = *OnlyElt;
     156             :     Success = true;
     157      127572 :   } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
     158       21335 :     Pred = CmpInst::ICMP_NE;
     159       21335 :     RHS = *OnlyMissingElt;
     160             :     Success = true;
     161      190020 :   } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
     162       64582 :     Pred =
     163       64582 :         getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
     164       64582 :     RHS = getUpper();
     165             :     Success = true;
     166       57392 :   } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
     167       41650 :     Pred =
     168       41650 :         getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
     169       41650 :     RHS = getLower();
     170             :     Success = true;
     171             :   }
     172             : 
     173             :   assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
     174             :          "Bad result!");
     175             : 
     176      128299 :   return Success;
     177             : }
     178             : 
     179             : ConstantRange
     180     2904359 : 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     1295389 :       [](const ConstantRange &CR0, const ConstantRange &CR1) {
     191     2590778 :     return CR0.inverse().unionWith(CR1.inverse()).inverse();
     192     2590778 :   };
     193             : 
     194             :   assert(BinOp >= Instruction::BinaryOpsBegin &&
     195             :          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
     196             : 
     197             :   assert((NoWrapKind == OBO::NoSignedWrap ||
     198             :           NoWrapKind == OBO::NoUnsignedWrap ||
     199             :           NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
     200             :          "NoWrapKind invalid!");
     201             : 
     202             :   unsigned BitWidth = Other.getBitWidth();
     203     5808718 :   ConstantRange Result(BitWidth);
     204             : 
     205     2904359 :   switch (BinOp) {
     206           0 :   default:
     207             :     // Conservative answer: empty set
     208           0 :     return ConstantRange(BitWidth, false);
     209             : 
     210     2904251 :   case Instruction::Add:
     211     2904251 :     if (auto *C = Other.getSingleElement())
     212     2903163 :       if (C->isNullValue())
     213             :         // Full set: nothing signed / unsigned wraps when added to 0.
     214     1609423 :         return ConstantRange(BitWidth);
     215     1294828 :     if (NoWrapKind & OBO::NoUnsignedWrap)
     216      764611 :       Result =
     217     2293833 :           SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
     218     2293833 :                                                 -Other.getUnsignedMax()));
     219     1294828 :     if (NoWrapKind & OBO::NoSignedWrap) {
     220      530228 :       const APInt &SignedMin = Other.getSignedMin();
     221      530228 :       const APInt &SignedMax = Other.getSignedMax();
     222      530228 :       if (SignedMax.isStrictlyPositive())
     223      332530 :         Result = SubsetIntersect(
     224             :             Result,
     225      997590 :             ConstantRange(APInt::getSignedMinValue(BitWidth),
     226      997590 :                           APInt::getSignedMinValue(BitWidth) - SignedMax));
     227     1060456 :       if (SignedMin.isNegative())
     228      198130 :         Result = SubsetIntersect(
     229             :             Result,
     230      990650 :             ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
     231      396260 :                           APInt::getSignedMinValue(BitWidth)));
     232             :     }
     233             :     return Result;
     234             : 
     235         108 :   case Instruction::Sub:
     236         108 :     if (auto *C = Other.getSingleElement())
     237          31 :       if (C->isNullValue())
     238             :         // Full set: nothing signed / unsigned wraps when subtracting 0.
     239           6 :         return ConstantRange(BitWidth);
     240         102 :     if (NoWrapKind & OBO::NoUnsignedWrap)
     241          86 :       Result =
     242         258 :           SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(),
     243         172 :                                                 APInt::getMinValue(BitWidth)));
     244         102 :     if (NoWrapKind & OBO::NoSignedWrap) {
     245          27 :       const APInt &SignedMin = Other.getSignedMin();
     246          27 :       const APInt &SignedMax = Other.getSignedMax();
     247          27 :       if (SignedMax.isStrictlyPositive())
     248          17 :         Result = SubsetIntersect(
     249             :             Result,
     250          85 :             ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax,
     251          34 :                           APInt::getSignedMinValue(BitWidth)));
     252          54 :       if (SignedMin.isNegative())
     253          15 :         Result = SubsetIntersect(
     254             :             Result,
     255          45 :             ConstantRange(APInt::getSignedMinValue(BitWidth),
     256          45 :                           APInt::getSignedMinValue(BitWidth) + SignedMin));
     257             :     }
     258             :     return Result;
     259             :   }
     260             : }
     261             : 
     262    24360052 : bool ConstantRange::isFullSet() const {
     263    55785371 :   return Lower == Upper && Lower.isMaxValue();
     264             : }
     265             : 
     266    14562814 : bool ConstantRange::isEmptySet() const {
     267    32721096 :   return Lower == Upper && Lower.isMinValue();
     268             : }
     269             : 
     270     7956078 : bool ConstantRange::isWrappedSet() const {
     271    15912156 :   return Lower.ugt(Upper);
     272             : }
     273             : 
     274        4021 : bool ConstantRange::isSignWrappedSet() const {
     275       10427 :   return contains(APInt::getSignedMaxValue(getBitWidth())) &&
     276       12084 :          contains(APInt::getSignedMinValue(getBitWidth()));
     277             : }
     278             : 
     279           6 : APInt ConstantRange::getSetSize() const {
     280           6 :   if (isFullSet())
     281           1 :     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
     282             : 
     283             :   // This is also correct for wrapped sets.
     284          20 :   return (Upper - Lower).zext(getBitWidth()+1);
     285             : }
     286             : 
     287             : bool
     288      256168 : ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
     289             :   assert(getBitWidth() == Other.getBitWidth());
     290      256168 :   if (isFullSet())
     291             :     return false;
     292      169337 :   if (Other.isFullSet())
     293             :     return true;
     294     1015686 :   return (Upper - Lower).ult(Other.Upper - Other.Lower);
     295             : }
     296             : 
     297             : bool
     298      113999 : ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
     299             :   assert(MaxSize && "MaxSize can't be 0.");
     300             :   // If this a full set, we need special handling to avoid needing an extra bit
     301             :   // to represent the size.
     302      113999 :   if (isFullSet())
     303          32 :     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
     304             : 
     305      455932 :   return (Upper - Lower).ugt(MaxSize);
     306             : }
     307             : 
     308     2176096 : APInt ConstantRange::getUnsignedMax() const {
     309     2176096 :   if (isFullSet() || isWrappedSet())
     310             :     return APInt::getMaxValue(getBitWidth());
     311     1838666 :   return getUpper() - 1;
     312             : }
     313             : 
     314      611449 : APInt ConstantRange::getUnsignedMin() const {
     315      685626 :   if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
     316      119863 :     return APInt::getMinValue(getBitWidth());
     317             :   return getLower();
     318             : }
     319             : 
     320     1135955 : APInt ConstantRange::getSignedMax() const {
     321     2166775 :   if (isFullSet() || Lower.sgt(Upper))
     322      121995 :     return APInt::getSignedMaxValue(getBitWidth());
     323     1013960 :   return getUpper() - 1;
     324             : }
     325             : 
     326     3135257 : APInt ConstantRange::getSignedMin() const {
     327     5993485 :   if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
     328      300903 :     return APInt::getSignedMinValue(getBitWidth());
     329             :   return getLower();
     330             : }
     331             : 
     332      393301 : bool ConstantRange::contains(const APInt &V) const {
     333      786602 :   if (Lower == Upper)
     334         612 :     return isFullSet();
     335             : 
     336      392689 :   if (!isWrappedSet())
     337      649435 :     return Lower.ule(V) && V.ult(Upper);
     338       94277 :   return Lower.ule(V) || V.ult(Upper);
     339             : }
     340             : 
     341     3317774 : bool ConstantRange::contains(const ConstantRange &Other) const {
     342     3317774 :   if (isFullSet() || Other.isEmptySet()) return true;
     343     1704451 :   if (isEmptySet() || Other.isFullSet()) return false;
     344             : 
     345     1271067 :   if (!isWrappedSet()) {
     346      730580 :     if (Other.isWrappedSet())
     347             :       return false;
     348             : 
     349     2334030 :     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
     350             :   }
     351             : 
     352      540487 :   if (!Other.isWrappedSet())
     353      879783 :     return Other.getUpper().ule(Upper) ||
     354      207651 :            Lower.ule(Other.getLower());
     355             : 
     356      542634 :   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
     357             : }
     358             : 
     359       25682 : ConstantRange ConstantRange::subtract(const APInt &Val) const {
     360             :   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
     361             :   // If the set is empty or full, don't modify the endpoints.
     362       51364 :   if (Lower == Upper) 
     363         137 :     return *this;
     364      127725 :   return ConstantRange(Lower - Val, Upper - Val);
     365             : }
     366             : 
     367       18795 : ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
     368       18795 :   return intersectWith(CR.inverse());
     369             : }
     370             : 
     371      836142 : ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
     372             :   assert(getBitWidth() == CR.getBitWidth() && 
     373             :          "ConstantRange types don't agree!");
     374             : 
     375             :   // Handle common cases.
     376      836142 :   if (   isEmptySet() || CR.isFullSet()) return *this;
     377      840733 :   if (CR.isEmptySet() ||    isFullSet()) return CR;
     378             : 
     379      574119 :   if (!isWrappedSet() && CR.isWrappedSet())
     380       23349 :     return CR.intersectWith(*this);
     381             : 
     382      527421 :   if (!isWrappedSet() && !CR.isWrappedSet()) {
     383      393842 :     if (Lower.ult(CR.Lower)) {
     384       20138 :       if (Upper.ule(CR.Lower))
     385          22 :         return ConstantRange(getBitWidth(), false);
     386             : 
     387       20094 :       if (Upper.ult(CR.Upper))
     388        2595 :         return ConstantRange(CR.Lower, Upper);
     389             : 
     390        9182 :       return CR;
     391             :     }
     392      373704 :     if (Upper.ult(CR.Upper))
     393        1297 :       return *this;
     394             : 
     395      185555 :     if (Lower.ult(CR.Upper))
     396      556467 :       return ConstantRange(Lower, CR.Upper);
     397             : 
     398          66 :     return ConstantRange(getBitWidth(), false);
     399             :   }
     400             : 
     401      267158 :   if (isWrappedSet() && !CR.isWrappedSet()) {
     402      151626 :     if (CR.Lower.ult(Upper)) {
     403       92622 :       if (CR.Upper.ult(Upper))
     404       18962 :         return CR;
     405             : 
     406       54698 :       if (CR.Upper.ule(Lower))
     407       50388 :         return ConstantRange(CR.Lower, Upper);
     408             : 
     409       10553 :       if (isSizeStrictlySmallerThan(CR))
     410        5509 :         return *this;
     411        5044 :       return CR;
     412             :     }
     413       59004 :     if (CR.Lower.ult(Lower)) {
     414       49962 :       if (CR.Upper.ule(Lower))
     415          90 :         return ConstantRange(getBitWidth(), false);
     416             : 
     417       74673 :       return ConstantRange(Lower, CR.Upper);
     418             :     }
     419        4521 :     return CR;
     420             :   }
     421             : 
     422      115532 :   if (CR.Upper.ult(Upper)) {
     423       63612 :     if (CR.Lower.ult(Upper)) {
     424        9615 :       if (isSizeStrictlySmallerThan(CR))
     425          18 :         return *this;
     426        9597 :       return CR;
     427             :     }
     428             : 
     429       44382 :     if (CR.Lower.ult(Lower))
     430        8166 :       return ConstantRange(Lower, CR.Upper);
     431             : 
     432       19469 :     return CR;
     433             :   }
     434       51920 :   if (CR.Upper.ule(Lower)) {
     435       33292 :     if (CR.Lower.ult(Lower))
     436          85 :       return *this;
     437             : 
     438       49683 :     return ConstantRange(CR.Lower, Upper);
     439             :   }
     440        9314 :   if (isSizeStrictlySmallerThan(CR))
     441         222 :     return *this;
     442        9092 :   return CR;
     443             : }
     444             : 
     445     1617598 : ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
     446             :   assert(getBitWidth() == CR.getBitWidth() && 
     447             :          "ConstantRange types don't agree!");
     448             : 
     449     1617598 :   if (   isFullSet() || CR.isEmptySet()) return *this;
     450     2858826 :   if (CR.isFullSet() ||    isEmptySet()) return CR;
     451             : 
     452      423941 :   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
     453             : 
     454      261476 :   if (!isWrappedSet() && !CR.isWrappedSet()) {
     455      263989 :     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
     456             :       // If the two ranges are disjoint, find the smaller gap and bridge it.
     457        2550 :       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
     458         850 :       if (d1.ult(d2))
     459         978 :         return ConstantRange(Lower, CR.Upper);
     460        1572 :       return ConstantRange(CR.Lower, Upper);
     461             :     }
     462             : 
     463       87317 :     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
     464      436585 :     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
     465             : 
     466      137615 :     if (L.isNullValue() && U.isNullValue())
     467           0 :       return ConstantRange(getBitWidth());
     468             : 
     469      261951 :     return ConstantRange(std::move(L), std::move(U));
     470             :   }
     471             : 
     472       85142 :   if (!CR.isWrappedSet()) {
     473             :     // ------U   L-----  and  ------U   L----- : this
     474             :     //   L--U                            L--U  : CR
     475      166293 :     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
     476        1328 :       return *this;
     477             : 
     478             :     // ------U   L----- : this
     479             :     //    L---------U   : CR
     480       82940 :     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
     481       28285 :       return ConstantRange(getBitWidth());
     482             : 
     483             :     // ----U       L---- : this
     484             :     //       L---U       : CR
     485             :     //    <d1>  <d2>
     486       52241 :     if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
     487       52118 :       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
     488       26059 :       if (d1.ult(d2))
     489         450 :         return ConstantRange(Lower, CR.Upper);
     490       77727 :       return ConstantRange(CR.Lower, Upper);
     491             :     }
     492             : 
     493             :     // ----U     L----- : this
     494             :     //        L----U    : CR
     495         123 :     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
     496          36 :       return ConstantRange(CR.Lower, Upper);
     497             : 
     498             :     // ------U    L---- : this
     499             :     //    L-----U       : CR
     500             :     assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
     501             :            "ConstantRange::unionWith missed a case with one range wrapped");
     502         297 :     return ConstantRange(Lower, CR.Upper);
     503             :   }
     504             : 
     505             :   // ------U    L----  and  ------U    L---- : this
     506             :   // -U  L-----------  and  ------------U  L : CR
     507       88043 :   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
     508          73 :     return ConstantRange(getBitWidth());
     509             : 
     510       29286 :   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
     511       29286 :   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
     512             : 
     513       87858 :   return ConstantRange(std::move(L), std::move(U));
     514             : }
     515             : 
     516        1848 : ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
     517             :                                     uint32_t ResultBitWidth) const {
     518        1848 :   switch (CastOp) {
     519           0 :   default:
     520           0 :     llvm_unreachable("unsupported cast type");
     521         397 :   case Instruction::Trunc:
     522         397 :     return truncate(ResultBitWidth);
     523          46 :   case Instruction::SExt:
     524          46 :     return signExtend(ResultBitWidth);
     525        1290 :   case Instruction::ZExt:
     526        1290 :     return zeroExtend(ResultBitWidth);
     527          17 :   case Instruction::BitCast:
     528          17 :     return *this;
     529             :   case Instruction::FPToUI:
     530             :   case Instruction::FPToSI:
     531          50 :     if (getBitWidth() == ResultBitWidth)
     532          50 :       return *this;
     533             :     else
     534           0 :       return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     535             :   case Instruction::UIToFP: {
     536             :     // TODO: use input range if available
     537             :     auto BW = getBitWidth();
     538          82 :     APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
     539          82 :     APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
     540         123 :     return ConstantRange(std::move(Min), std::move(Max));
     541             :   }
     542             :   case Instruction::SIToFP: {
     543             :     // TODO: use input range if available
     544             :     auto BW = getBitWidth();
     545          14 :     APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
     546          14 :     APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
     547          21 :     return ConstantRange(std::move(SMin), std::move(SMax));
     548             :   }
     549             :   case Instruction::FPTrunc:
     550             :   case Instruction::FPExt:
     551             :   case Instruction::IntToPtr:
     552             :   case Instruction::PtrToInt:
     553             :   case Instruction::AddrSpaceCast:
     554             :     // Conservatively return full set.
     555           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     556             :   };
     557             : }
     558             : 
     559       30151 : ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
     560       30151 :   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
     561             : 
     562             :   unsigned SrcTySize = getBitWidth();
     563             :   assert(SrcTySize < DstTySize && "Not a value extension");
     564       30150 :   if (isFullSet() || isWrappedSet()) {
     565             :     // Change into [0, 1 << src bit width)
     566             :     APInt LowerExt(DstTySize, 0);
     567       42320 :     if (!Upper) // special case: [X, 0) -- not really wrapping around
     568          30 :       LowerExt = Lower.zext(DstTySize);
     569             :     return ConstantRange(std::move(LowerExt),
     570       84640 :                          APInt::getOneBitSet(DstTySize, SrcTySize));
     571             :   }
     572             : 
     573       26970 :   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
     574             : }
     575             : 
     576       15572 : ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
     577       15572 :   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
     578             : 
     579             :   unsigned SrcTySize = getBitWidth();
     580             :   assert(SrcTySize < DstTySize && "Not a value extension");
     581             : 
     582             :   // special case: [X, INT_MIN) -- not really wrapping around
     583       15571 :   if (Upper.isMinSignedValue())
     584          99 :     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
     585             : 
     586       15538 :   if (isFullSet() || isSignWrappedSet()) {
     587       28122 :     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
     588       56244 :                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
     589             :   }
     590             : 
     591        4431 :   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
     592             : }
     593             : 
     594      210117 : ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
     595             :   assert(getBitWidth() > DstTySize && "Not a value truncation");
     596      210117 :   if (isEmptySet())
     597           1 :     return ConstantRange(DstTySize, /*isFullSet=*/false);
     598      210116 :   if (isFullSet())
     599        2880 :     return ConstantRange(DstTySize, /*isFullSet=*/true);
     600             : 
     601      414472 :   APInt LowerDiv(Lower), UpperDiv(Upper);
     602      414472 :   ConstantRange Union(DstTySize, /*isFullSet=*/false);
     603             : 
     604             :   // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
     605             :   // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
     606             :   // then we do the union with [MaxValue, Upper)
     607      207236 :   if (isWrappedSet()) {
     608             :     // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
     609             :     // truncated range.
     610      140660 :     if (Upper.getActiveBits() > DstTySize ||
     611             :         Upper.countTrailingOnes() == DstTySize)
     612       31627 :       return ConstantRange(DstTySize, /*isFullSet=*/true);
     613             : 
     614      215244 :     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
     615       53811 :     UpperDiv.setAllBits();
     616             : 
     617             :     // Union covers the MaxValue case, so return if the remaining range is just
     618             :     // MaxValue(DstTy).
     619       53811 :     if (LowerDiv == UpperDiv)
     620             :       return Union;
     621             :   }
     622             : 
     623             :   // Chop off the most significant bits that are past the destination bitwidth.
     624      174692 :   if (LowerDiv.getActiveBits() > DstTySize) {
     625             :     // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
     626      108078 :     APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
     627       54039 :     LowerDiv -= Adjust;
     628       54039 :     UpperDiv -= Adjust;
     629             :   }
     630             : 
     631             :   unsigned UpperDivWidth = UpperDiv.getActiveBits();
     632      174692 :   if (UpperDivWidth <= DstTySize)
     633      252573 :     return ConstantRange(LowerDiv.trunc(DstTySize),
     634      252573 :                          UpperDiv.trunc(DstTySize)).unionWith(Union);
     635             : 
     636             :   // The truncated value wraps around. Check if we can do better than fullset.
     637       90501 :   if (UpperDivWidth == DstTySize + 1) {
     638             :     // Clear the MSB so that UpperDiv wraps around.
     639             :     UpperDiv.clearBit(DstTySize);
     640        4287 :     if (UpperDiv.ult(LowerDiv))
     641          66 :       return ConstantRange(LowerDiv.trunc(DstTySize),
     642          66 :                            UpperDiv.trunc(DstTySize)).unionWith(Union);
     643             :   }
     644             : 
     645       90479 :   return ConstantRange(DstTySize, /*isFullSet=*/true);
     646             : }
     647             : 
     648        1696 : ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
     649             :   unsigned SrcTySize = getBitWidth();
     650        1696 :   if (SrcTySize > DstTySize)
     651          31 :     return truncate(DstTySize);
     652        1665 :   if (SrcTySize < DstTySize)
     653         167 :     return zeroExtend(DstTySize);
     654        1498 :   return *this;
     655             : }
     656             : 
     657         301 : ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
     658             :   unsigned SrcTySize = getBitWidth();
     659         301 :   if (SrcTySize > DstTySize)
     660           1 :     return truncate(DstTySize);
     661         300 :   if (SrcTySize < DstTySize)
     662          55 :     return signExtend(DstTySize);
     663         245 :   return *this;
     664             : }
     665             : 
     666       11069 : ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
     667             :                                       const ConstantRange &Other) const {
     668             :   assert(BinOp >= Instruction::BinaryOpsBegin &&
     669             :          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
     670             : 
     671       11069 :   switch (BinOp) {
     672        8515 :   case Instruction::Add:
     673        8515 :     return add(Other);
     674           1 :   case Instruction::Sub:
     675           1 :     return sub(Other);
     676         278 :   case Instruction::Mul:
     677         278 :     return multiply(Other);
     678          93 :   case Instruction::UDiv:
     679          93 :     return udiv(Other);
     680         447 :   case Instruction::Shl:
     681         447 :     return shl(Other);
     682         687 :   case Instruction::LShr:
     683         687 :     return lshr(Other);
     684         580 :   case Instruction::AShr:
     685         580 :     return ashr(Other);
     686         303 :   case Instruction::And:
     687         303 :     return binaryAnd(Other);
     688         136 :   case Instruction::Or:
     689         136 :     return binaryOr(Other);
     690             :   // Note: floating point operations applied to abstract ranges are just
     691             :   // ideal integer operations with a lossy representation
     692          17 :   case Instruction::FAdd:
     693          17 :     return add(Other);
     694           4 :   case Instruction::FSub:
     695           4 :     return sub(Other);
     696           8 :   case Instruction::FMul:
     697           8 :     return multiply(Other);
     698             :   default:
     699             :     // Conservatively return full set.
     700           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     701             :   }
     702             : }
     703             : 
     704             : ConstantRange
     705      728036 : ConstantRange::add(const ConstantRange &Other) const {
     706      728036 :   if (isEmptySet() || Other.isEmptySet())
     707           8 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     708      728028 :   if (isFullSet() || Other.isFullSet())
     709      645215 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     710             : 
     711       82813 :   APInt NewLower = getLower() + Other.getLower();
     712      165626 :   APInt NewUpper = getUpper() + Other.getUpper() - 1;
     713       82813 :   if (NewLower == NewUpper)
     714          15 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     715             : 
     716      331192 :   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
     717      138367 :   if (X.isSizeStrictlySmallerThan(*this) ||
     718       55569 :       X.isSizeStrictlySmallerThan(Other))
     719             :     // We've wrapped, therefore, full set.
     720       27229 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     721             :   return X;
     722             : }
     723             : 
     724          28 : ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
     725             :   // Calculate the subset of this range such that "X + Other" is
     726             :   // guaranteed not to wrap (overflow) for all X in this subset.
     727             :   // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
     728             :   // passing a single element range.
     729             :   auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
     730          84 :                                       ConstantRange(Other),
     731          56 :                                       OverflowingBinaryOperator::NoSignedWrap);
     732          56 :   auto NSWConstrainedRange = intersectWith(NSWRange);
     733             : 
     734          84 :   return NSWConstrainedRange.add(ConstantRange(Other));
     735             : }
     736             : 
     737             : ConstantRange
     738          20 : ConstantRange::sub(const ConstantRange &Other) const {
     739          20 :   if (isEmptySet() || Other.isEmptySet())
     740           6 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     741          14 :   if (isFullSet() || Other.isFullSet())
     742           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     743             : 
     744          18 :   APInt NewLower = getLower() - Other.getUpper() + 1;
     745           9 :   APInt NewUpper = getUpper() - Other.getLower();
     746           9 :   if (NewLower == NewUpper)
     747           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     748             : 
     749          36 :   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
     750          18 :   if (X.isSizeStrictlySmallerThan(*this) ||
     751           9 :       X.isSizeStrictlySmallerThan(Other))
     752             :     // We've wrapped, therefore, full set.
     753           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     754             :   return X;
     755             : }
     756             : 
     757             : ConstantRange
     758      116296 : ConstantRange::multiply(const ConstantRange &Other) const {
     759             :   // TODO: If either operand is a single element and the multiply is known to
     760             :   // be non-wrapping, round the result min and max value to the appropriate
     761             :   // multiple of that element. If wrapping is possible, at least adjust the
     762             :   // range according to the greatest power-of-two factor of the single element.
     763             : 
     764      116296 :   if (isEmptySet() || Other.isEmptySet())
     765           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     766             : 
     767             :   // Multiplication is signedness-independent. However different ranges can be
     768             :   // obtained depending on how the input ranges are treated. These different
     769             :   // ranges are all conservatively correct, but one might be better than the
     770             :   // other. We calculate two ranges; one treating the inputs as unsigned
     771             :   // and the other signed, then return the smallest of these ranges.
     772             : 
     773             :   // Unsigned range first.
     774      348873 :   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
     775      348873 :   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
     776      348873 :   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
     777      348873 :   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
     778             : 
     779      232582 :   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
     780      581455 :                                             this_max * Other_max + 1);
     781      232582 :   ConstantRange UR = Result_zext.truncate(getBitWidth());
     782             : 
     783             :   // If the unsigned range doesn't wrap, and isn't negative then it's a range
     784             :   // from one positive number to another which is as good as we can generate.
     785             :   // In this case, skip the extra work of generating signed ranges which aren't
     786             :   // going to be better than this range.
     787      232569 :   if (!UR.isWrappedSet() &&
     788       88439 :       (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
     789             :     return UR;
     790             : 
     791             :   // Now the signed range. Because we could be dealing with negative numbers
     792             :   // here, the lower bound is the smallest of the cartesian product of the
     793             :   // lower and upper ranges; for example:
     794             :   //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
     795             :   // Similarly for the upper bound, swapping min for max.
     796             : 
     797      353204 :   this_min = getSignedMin().sext(getBitWidth() * 2);
     798      353204 :   this_max = getSignedMax().sext(getBitWidth() * 2);
     799      353204 :   Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
     800      353204 :   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
     801             :   
     802       88301 :   auto L = {this_min * Other_min, this_min * Other_max,
     803      529806 :             this_max * Other_min, this_max * Other_max};
     804             :   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
     805      529806 :   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
     806      176602 :   ConstantRange SR = Result_sext.truncate(getBitWidth());
     807             : 
     808       88301 :   return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
     809             : }
     810             : 
     811             : ConstantRange
     812        4855 : ConstantRange::smax(const ConstantRange &Other) const {
     813             :   // X smax Y is: range(smax(X_smin, Y_smin),
     814             :   //                    smax(X_smax, Y_smax))
     815        4855 :   if (isEmptySet() || Other.isEmptySet())
     816           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     817       14550 :   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
     818       19400 :   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
     819        4850 :   if (NewU == NewL)
     820         575 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     821       12825 :   return ConstantRange(std::move(NewL), std::move(NewU));
     822             : }
     823             : 
     824             : ConstantRange
     825        1431 : ConstantRange::umax(const ConstantRange &Other) const {
     826             :   // X umax Y is: range(umax(X_umin, Y_umin),
     827             :   //                    umax(X_umax, Y_umax))
     828        1431 :   if (isEmptySet() || Other.isEmptySet())
     829           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     830        4278 :   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
     831        5704 :   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
     832        1426 :   if (NewU == NewL)
     833         503 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     834        2769 :   return ConstantRange(std::move(NewL), std::move(NewU));
     835             : }
     836             : 
     837             : ConstantRange
     838          17 : ConstantRange::smin(const ConstantRange &Other) const {
     839             :   // X smin Y is: range(smin(X_smin, Y_smin),
     840             :   //                    smin(X_smax, Y_smax))
     841          17 :   if (isEmptySet() || Other.isEmptySet())
     842           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     843          36 :   APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
     844          48 :   APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
     845          12 :   if (NewU == NewL)
     846           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     847          27 :   return ConstantRange(std::move(NewL), std::move(NewU));
     848             : }
     849             : 
     850             : ConstantRange
     851          91 : ConstantRange::umin(const ConstantRange &Other) const {
     852             :   // X umin Y is: range(umin(X_umin, Y_umin),
     853             :   //                    umin(X_umax, Y_umax))
     854          91 :   if (isEmptySet() || Other.isEmptySet())
     855           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     856         258 :   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
     857         344 :   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
     858          86 :   if (NewU == NewL)
     859           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     860         249 :   return ConstantRange(std::move(NewL), std::move(NewU));
     861             : }
     862             : 
     863             : ConstantRange
     864        6380 : ConstantRange::udiv(const ConstantRange &RHS) const {
     865       19135 :   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
     866           7 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     867        6373 :   if (RHS.isFullSet())
     868         495 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     869             : 
     870       17634 :   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
     871             : 
     872        5878 :   APInt RHS_umin = RHS.getUnsignedMin();
     873        5878 :   if (RHS_umin.isNullValue()) {
     874             :     // We want the lowest value in RHS excluding zero. Usually that would be 1
     875             :     // except for a range in the form of [X, 1) in which case it would be X.
     876         120 :     if (RHS.getUpper() == 1)
     877           0 :       RHS_umin = RHS.getLower();
     878             :     else
     879         120 :       RHS_umin = 1;
     880             :   }
     881             : 
     882       17634 :   APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
     883             : 
     884             :   // If the LHS is Full and the RHS is a wrapped interval containing 1 then
     885             :   // this could occur.
     886        5878 :   if (Lower == Upper)
     887          73 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     888             : 
     889       17415 :   return ConstantRange(std::move(Lower), std::move(Upper));
     890             : }
     891             : 
     892             : ConstantRange
     893         303 : ConstantRange::binaryAnd(const ConstantRange &Other) const {
     894         303 :   if (isEmptySet() || Other.isEmptySet())
     895           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     896             : 
     897             :   // TODO: replace this with something less conservative
     898             : 
     899         909 :   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
     900         303 :   if (umin.isAllOnesValue())
     901           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     902        1212 :   return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
     903             : }
     904             : 
     905             : ConstantRange
     906         136 : ConstantRange::binaryOr(const ConstantRange &Other) const {
     907         136 :   if (isEmptySet() || Other.isEmptySet())
     908           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     909             : 
     910             :   // TODO: replace this with something less conservative
     911             : 
     912         408 :   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
     913         136 :   if (umax.isNullValue())
     914           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     915         532 :   return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
     916             : }
     917             : 
     918             : ConstantRange
     919         462 : ConstantRange::shl(const ConstantRange &Other) const {
     920         462 :   if (isEmptySet() || Other.isEmptySet())
     921           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     922             : 
     923         457 :   APInt max = getUnsignedMax();
     924         457 :   APInt Other_umax = Other.getUnsignedMax();
     925             : 
     926             :   // there's overflow!
     927         914 :   if (Other_umax.uge(max.countLeadingZeros()))
     928         195 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     929             : 
     930             :   // FIXME: implement the other tricky cases
     931             : 
     932         262 :   APInt min = getUnsignedMin();
     933         524 :   min <<= Other.getUnsignedMin();
     934         262 :   max <<= Other_umax;
     935             : 
     936        1048 :   return ConstantRange(std::move(min), std::move(max) + 1);
     937             : }
     938             : 
     939             : ConstantRange
     940         702 : ConstantRange::lshr(const ConstantRange &Other) const {
     941         702 :   if (isEmptySet() || Other.isEmptySet())
     942           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     943             : 
     944        2788 :   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
     945        2091 :   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
     946         697 :   if (min == max)
     947           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     948             : 
     949        2082 :   return ConstantRange(std::move(min), std::move(max));
     950             : }
     951             : 
     952             : ConstantRange
     953         597 : ConstantRange::ashr(const ConstantRange &Other) const {
     954         597 :   if (isEmptySet() || Other.isEmptySet())
     955           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     956             : 
     957             :   // May straddle zero, so handle both positive and negative cases.
     958             :   // 'PosMax' is the upper bound of the result of the ashr
     959             :   // operation, when Upper of the LHS of ashr is a non-negative.
     960             :   // number. Since ashr of a non-negative number will result in a
     961             :   // smaller number, the Upper value of LHS is shifted right with
     962             :   // the minimum value of 'Other' instead of the maximum value.
     963        2368 :   APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
     964             : 
     965             :   // 'PosMin' is the lower bound of the result of the ashr
     966             :   // operation, when Lower of the LHS is a non-negative number.
     967             :   // Since ashr of a non-negative number will result in a smaller
     968             :   // number, the Lower value of LHS is shifted right with the
     969             :   // maximum value of 'Other'.
     970        1776 :   APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
     971             : 
     972             :   // 'NegMax' is the upper bound of the result of the ashr
     973             :   // operation, when Upper of the LHS of ashr is a negative number.
     974             :   // Since 'ashr' of a negative number will result in a bigger
     975             :   // number, the Upper value of LHS is shifted right with the
     976             :   // maximum value of 'Other'.
     977        2368 :   APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
     978             : 
     979             :   // 'NegMin' is the lower bound of the result of the ashr
     980             :   // operation, when Lower of the LHS of ashr is a negative number.
     981             :   // Since 'ashr' of a negative number will result in a bigger
     982             :   // number, the Lower value of LHS is shifted right with the
     983             :   // minimum value of 'Other'.
     984        1776 :   APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
     985             : 
     986             :   APInt max, min;
     987        1184 :   if (getSignedMin().isNonNegative()) {
     988             :     // Upper and Lower of LHS are non-negative.
     989          43 :     min = PosMin;
     990          43 :     max = PosMax;
     991        1098 :   } else if (getSignedMax().isNegative()) {
     992             :     // Upper and Lower of LHS are negative.
     993           1 :     min = NegMin;
     994           1 :     max = NegMax;
     995             :   } else {
     996             :     // Upper is non-negative and Lower is negative.
     997         548 :     min = NegMin;
     998         548 :     max = PosMax;
     999             :   }
    1000         592 :   if (min == max)
    1001           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
    1002             : 
    1003        1767 :   return ConstantRange(std::move(min), std::move(max));
    1004             : }
    1005             : 
    1006     4335895 : ConstantRange ConstantRange::inverse() const {
    1007     4335895 :   if (isFullSet())
    1008     1309435 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
    1009     3026460 :   if (isEmptySet())
    1010        3923 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
    1011    15112685 :   return ConstantRange(Upper, Lower);
    1012             : }
    1013             : 
    1014        4252 : void ConstantRange::print(raw_ostream &OS) const {
    1015        4252 :   if (isFullSet())
    1016        2064 :     OS << "full-set";
    1017        2188 :   else if (isEmptySet())
    1018           2 :     OS << "empty-set";
    1019             :   else
    1020        6558 :     OS << "[" << Lower << "," << Upper << ")";
    1021        4252 : }
    1022             : 
    1023             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    1024             : LLVM_DUMP_METHOD void ConstantRange::dump() const {
    1025             :   print(dbgs());
    1026             : }
    1027             : #endif
    1028             : 
    1029       71099 : ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
    1030       71099 :   const unsigned NumRanges = Ranges.getNumOperands() / 2;
    1031             :   assert(NumRanges >= 1 && "Must have at least one range!");
    1032             :   assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
    1033             : 
    1034             :   auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
    1035             :   auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
    1036             : 
    1037      213297 :   ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
    1038             : 
    1039       71115 :   for (unsigned i = 1; i < NumRanges; ++i) {
    1040           8 :     auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
    1041           8 :     auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
    1042             : 
    1043             :     // Note: unionWith will potentially create a range that contains values not
    1044             :     // contained in any of the original N ranges.
    1045          24 :     CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
    1046             :   }
    1047             : 
    1048       71099 :   return CR;
    1049             : }

Generated by: LCOV version 1.13