LCOV - code coverage report
Current view: top level - lib/IR - ConstantRange.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 508 526 96.6 %
Date: 2017-09-14 15:23:50 Functions: 49 49 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    12361640 : ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
      42             :     : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
      43    25951622 :       Upper(Lower) {}
      44             : 
      45     3213157 : ConstantRange::ConstantRange(APInt V)
      46    16065785 :     : Lower(std::move(V)), Upper(Lower + 1) {}
      47             : 
      48     5587376 : ConstantRange::ConstantRange(APInt L, APInt U)
      49    16762128 :     : 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     5587376 : }
      55             : 
      56      732237 : ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
      57             :                                                    const ConstantRange &CR) {
      58      732237 :   if (CR.isEmptySet())
      59           0 :     return CR;
      60             : 
      61      732237 :   uint32_t W = CR.getBitWidth();
      62      732237 :   switch (Pred) {
      63           0 :   default:
      64           0 :     llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
      65      196421 :   case CmpInst::ICMP_EQ:
      66      196421 :     return CR;
      67      117661 :   case CmpInst::ICMP_NE:
      68      117661 :     if (CR.isSingleElement())
      69      694380 :       return ConstantRange(CR.getUpper(), CR.getLower());
      70        1931 :     return ConstantRange(W);
      71      137772 :   case CmpInst::ICMP_ULT: {
      72      275544 :     APInt UMax(CR.getUnsignedMax());
      73      137772 :     if (UMax.isMinValue())
      74          48 :       return ConstantRange(W, /* empty */ false);
      75      550896 :     return ConstantRange(APInt::getMinValue(W), std::move(UMax));
      76             :   }
      77       47663 :   case CmpInst::ICMP_SLT: {
      78       95326 :     APInt SMax(CR.getSignedMax());
      79       47663 :     if (SMax.isMinSignedValue())
      80           2 :       return ConstantRange(W, /* empty */ false);
      81      190644 :     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
      82             :   }
      83       28145 :   case CmpInst::ICMP_ULE: {
      84       56290 :     APInt UMax(CR.getUnsignedMax());
      85       28145 :     if (UMax.isMaxValue())
      86        1378 :       return ConstantRange(W);
      87      160602 :     return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
      88             :   }
      89       19016 :   case CmpInst::ICMP_SLE: {
      90       38032 :     APInt SMax(CR.getSignedMax());
      91       19016 :     if (SMax.isMaxSignedValue())
      92         341 :       return ConstantRange(W);
      93      112050 :     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
      94             :   }
      95       83805 :   case CmpInst::ICMP_UGT: {
      96      167610 :     APInt UMin(CR.getUnsignedMin());
      97       83805 :     if (UMin.isMaxValue())
      98         167 :       return ConstantRange(W, /* empty */ false);
      99      501828 :     return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
     100             :   }
     101       54058 :   case CmpInst::ICMP_SGT: {
     102      108116 :     APInt SMin(CR.getSignedMin());
     103       54058 :     if (SMin.isMaxSignedValue())
     104           4 :       return ConstantRange(W, /* empty */ false);
     105      324324 :     return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
     106             :   }
     107       22314 :   case CmpInst::ICMP_UGE: {
     108       44628 :     APInt UMin(CR.getUnsignedMin());
     109       22314 :     if (UMin.isMinValue())
     110        3047 :       return ConstantRange(W);
     111       77068 :     return ConstantRange(std::move(UMin), APInt::getNullValue(W));
     112             :   }
     113       25382 :   case CmpInst::ICMP_SGE: {
     114       50764 :     APInt SMin(CR.getSignedMin());
     115       25382 :     if (SMin.isMinSignedValue())
     116        1846 :       return ConstantRange(W);
     117       94144 :     return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
     118             :   }
     119             :   }
     120             : }
     121             : 
     122      138138 : 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      276276 :   return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
     129      276276 :       .inverse();
     130             : }
     131             : 
     132      434139 : 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      868278 :   return makeAllowedICmpRegion(Pred, C);
     142             : }
     143             : 
     144       94959 : bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
     145             :                                       APInt &RHS) const {
     146       94959 :   bool Success = false;
     147             : 
     148       94959 :   if (isFullSet() || isEmptySet()) {
     149           4 :     Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
     150           8 :     RHS = APInt(getBitWidth(), 0);
     151           2 :     Success = true;
     152       94957 :   } else if (auto *OnlyElt = getSingleElement()) {
     153         619 :     Pred = CmpInst::ICMP_EQ;
     154         619 :     RHS = *OnlyElt;
     155         619 :     Success = true;
     156       94338 :   } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
     157       18571 :     Pred = CmpInst::ICMP_NE;
     158       18571 :     RHS = *OnlyMissingElt;
     159       18571 :     Success = true;
     160      134764 :   } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
     161       51000 :     Pred =
     162       51000 :         getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
     163       51000 :     RHS = getUpper();
     164       51000 :     Success = true;
     165       45819 :   } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
     166       24762 :     Pred =
     167       24762 :         getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
     168       24762 :     RHS = getLower();
     169       24762 :     Success = true;
     170             :   }
     171             : 
     172             :   assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
     173             :          "Bad result!");
     174             : 
     175       94959 :   return Success;
     176             : }
     177             : 
     178             : ConstantRange
     179     2271151 : 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     1055173 :       [](const ConstantRange &CR0, const ConstantRange &CR1) {
     190     2110346 :     return CR0.inverse().unionWith(CR1.inverse()).inverse();
     191     2110346 :   };
     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     2271151 :   unsigned BitWidth = Other.getBitWidth();
     202     2271151 :   if (BinOp != Instruction::Add)
     203             :     // Conservative answer: empty set
     204           0 :     return ConstantRange(BitWidth, false);
     205             : 
     206     2271151 :   if (auto *C = Other.getSingleElement())
     207     2270045 :     if (C->isNullValue())
     208             :       // Full set: nothing signed / unsigned wraps when added to 0.
     209     1216507 :       return ConstantRange(BitWidth);
     210             : 
     211     2109288 :   ConstantRange Result(BitWidth);
     212             : 
     213     1054644 :   if (NoWrapKind & OBO::NoUnsignedWrap)
     214      610235 :     Result =
     215     1830705 :         SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
     216     2440940 :                                               -Other.getUnsignedMax()));
     217             : 
     218     1054644 :   if (NoWrapKind & OBO::NoSignedWrap) {
     219      444419 :     const APInt &SignedMin = Other.getSignedMin();
     220      888838 :     const APInt &SignedMax = Other.getSignedMax();
     221             : 
     222      444419 :     if (SignedMax.isStrictlyPositive())
     223      314003 :       Result = SubsetIntersect(
     224             :           Result,
     225      942009 :           ConstantRange(APInt::getSignedMinValue(BitWidth),
     226     1256012 :                         APInt::getSignedMinValue(BitWidth) - SignedMax));
     227             : 
     228      888838 :     if (SignedMin.isNegative())
     229      130935 :       Result = SubsetIntersect(
     230      654675 :           Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
     231      261870 :                                 APInt::getSignedMinValue(BitWidth)));
     232             :   }
     233             : 
     234     1054644 :   return Result;
     235             : }
     236             : 
     237    18726175 : bool ConstantRange::isFullSet() const {
     238    42520690 :   return Lower == Upper && Lower.isMaxValue();
     239             : }
     240             : 
     241    10858459 : bool ConstantRange::isEmptySet() const {
     242    23627959 :   return Lower == Upper && Lower.isMinValue();
     243             : }
     244             : 
     245     6469709 : bool ConstantRange::isWrappedSet() const {
     246    12939418 :   return Lower.ugt(Upper);
     247             : }
     248             : 
     249        3077 : bool ConstantRange::isSignWrappedSet() const {
     250       11015 :   return contains(APInt::getSignedMaxValue(getBitWidth())) &&
     251        9250 :          contains(APInt::getSignedMinValue(getBitWidth()));
     252             : }
     253             : 
     254           6 : APInt ConstantRange::getSetSize() const {
     255           6 :   if (isFullSet())
     256           2 :     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
     257             : 
     258             :   // This is also correct for wrapped sets.
     259          30 :   return (Upper - Lower).zext(getBitWidth()+1);
     260             : }
     261             : 
     262             : bool
     263      193069 : ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
     264             :   assert(getBitWidth() == Other.getBitWidth());
     265      193069 :   if (isFullSet())
     266             :     return false;
     267      125178 :   if (Other.isFullSet())
     268             :     return true;
     269     1251260 :   return (Upper - Lower).ult(Other.Upper - Other.Lower);
     270             : }
     271             : 
     272             : bool
     273      106853 : ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
     274             :   assert(MaxSize && "MaxSize can't be 0.");
     275             :   // If this a full set, we need special handling to avoid needing an extra bit
     276             :   // to represent the size.
     277      106853 :   if (isFullSet())
     278          48 :     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
     279             : 
     280      534185 :   return (Upper - Lower).ugt(MaxSize);
     281             : }
     282             : 
     283     1763453 : APInt ConstantRange::getUnsignedMax() const {
     284     1763453 :   if (isFullSet() || isWrappedSet())
     285      250084 :     return APInt::getMaxValue(getBitWidth());
     286     6053476 :   return getUpper() - 1;
     287             : }
     288             : 
     289      493753 : APInt ConstantRange::getUnsignedMin() const {
     290      595267 :   if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
     291       95916 :     return APInt::getMinValue(getBitWidth());
     292      397837 :   return getLower();
     293             : }
     294             : 
     295      926016 : APInt ConstantRange::getSignedMax() const {
     296     1772316 :   if (isFullSet() || Lower.sgt(Upper))
     297       91001 :     return APInt::getSignedMaxValue(getBitWidth());
     298     3340060 :   return getUpper() - 1;
     299             : }
     300             : 
     301     2140433 : APInt ConstantRange::getSignedMin() const {
     302     4076804 :   if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
     303      217062 :     return APInt::getSignedMinValue(getBitWidth());
     304     1923371 :   return getLower();
     305             : }
     306             : 
     307      321621 : bool ConstantRange::contains(const APInt &V) const {
     308      643242 :   if (Lower == Upper)
     309         475 :     return isFullSet();
     310             : 
     311      321146 :   if (!isWrappedSet())
     312      811439 :     return Lower.ule(V) && V.ult(Upper);
     313      119369 :   return Lower.ule(V) || V.ult(Upper);
     314             : }
     315             : 
     316     2585453 : bool ConstantRange::contains(const ConstantRange &Other) const {
     317     2585453 :   if (isFullSet() || Other.isEmptySet()) return true;
     318     1368946 :   if (isEmptySet() || Other.isFullSet()) return false;
     319             : 
     320     1060526 :   if (!isWrappedSet()) {
     321      598170 :     if (Other.isWrappedSet())
     322             :       return false;
     323             : 
     324     2439540 :     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
     325             :   }
     326             : 
     327      462356 :   if (!Other.isWrappedSet())
     328      833224 :     return Other.getUpper().ule(Upper) ||
     329      627420 :            Lower.ule(Other.getLower());
     330             : 
     331      501320 :   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
     332             : }
     333             : 
     334       21166 : ConstantRange ConstantRange::subtract(const APInt &Val) const {
     335             :   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
     336             :   // If the set is empty or full, don't modify the endpoints.
     337       42332 :   if (Lower == Upper) 
     338         221 :     return *this;
     339      188505 :   return ConstantRange(Lower - Val, Upper - Val);
     340             : }
     341             : 
     342       20738 : ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
     343       20738 :   return intersectWith(CR.inverse());
     344             : }
     345             : 
     346      652289 : ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
     347             :   assert(getBitWidth() == CR.getBitWidth() && 
     348             :          "ConstantRange types don't agree!");
     349             : 
     350             :   // Handle common cases.
     351      652289 :   if (   isEmptySet() || CR.isFullSet()) return *this;
     352      689911 :   if (CR.isEmptySet() ||    isFullSet()) return CR;
     353             : 
     354      447441 :   if (!isWrappedSet() && CR.isWrappedSet())
     355       21674 :     return CR.intersectWith(*this);
     356             : 
     357      404093 :   if (!isWrappedSet() && !CR.isWrappedSet()) {
     358      289672 :     if (Lower.ult(CR.Lower)) {
     359       19498 :       if (Upper.ule(CR.Lower))
     360          21 :         return ConstantRange(getBitWidth(), false);
     361             : 
     362       19456 :       if (Upper.ult(CR.Upper))
     363        8130 :         return ConstantRange(CR.Lower, Upper);
     364             : 
     365        8102 :       return CR;
     366             :     }
     367      270174 :     if (Upper.ult(CR.Upper))
     368        1148 :       return *this;
     369             : 
     370      267878 :     if (Lower.ult(CR.Upper))
     371      669395 :       return ConstantRange(Lower, CR.Upper);
     372             : 
     373          60 :     return ConstantRange(getBitWidth(), false);
     374             :   }
     375             : 
     376      228842 :   if (isWrappedSet() && !CR.isWrappedSet()) {
     377      137746 :     if (CR.Lower.ult(Upper)) {
     378       79674 :       if (CR.Upper.ult(Upper))
     379       16569 :         return CR;
     380             : 
     381       46536 :       if (CR.Upper.ule(Lower))
     382       75410 :         return ConstantRange(CR.Lower, Upper);
     383             : 
     384        8186 :       if (isSizeStrictlySmallerThan(CR))
     385        4139 :         return *this;
     386        4047 :       return CR;
     387             :     }
     388       58072 :     if (CR.Lower.ult(Lower)) {
     389       49970 :       if (CR.Upper.ule(Lower))
     390          77 :         return ConstantRange(getBitWidth(), false);
     391             : 
     392      124540 :       return ConstantRange(Lower, CR.Upper);
     393             :     }
     394        4051 :     return CR;
     395             :   }
     396             : 
     397       91096 :   if (CR.Upper.ult(Upper)) {
     398       54010 :     if (CR.Lower.ult(Upper)) {
     399        7974 :       if (isSizeStrictlySmallerThan(CR))
     400          18 :         return *this;
     401        7956 :       return CR;
     402             :     }
     403             : 
     404       38062 :     if (CR.Lower.ult(Lower))
     405       13290 :       return ConstantRange(Lower, CR.Upper);
     406             : 
     407       16373 :     return CR;
     408             :   }
     409       37086 :   if (CR.Upper.ule(Lower)) {
     410       26800 :     if (CR.Lower.ult(Lower))
     411          97 :       return *this;
     412             : 
     413       66515 :     return ConstantRange(CR.Lower, Upper);
     414             :   }
     415        5143 :   if (isSizeStrictlySmallerThan(CR))
     416         270 :     return *this;
     417        4873 :   return CR;
     418             : }
     419             : 
     420     1294680 : ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
     421             :   assert(getBitWidth() == CR.getBitWidth() && 
     422             :          "ConstantRange types don't agree!");
     423             : 
     424     1294680 :   if (   isFullSet() || CR.isEmptySet()) return *this;
     425     2290498 :   if (CR.isFullSet() ||    isEmptySet()) return CR;
     426             : 
     427      332078 :   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
     428             : 
     429      215744 :   if (!isWrappedSet() && !CR.isWrappedSet()) {
     430      226076 :     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
     431             :       // If the two ranges are disjoint, find the smaller gap and bridge it.
     432        8235 :       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
     433         915 :       if (d1.ult(d2))
     434        2020 :         return ConstantRange(Lower, CR.Upper);
     435        2555 :       return ConstantRange(CR.Lower, Upper);
     436             :     }
     437             : 
     438      223839 :     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
     439      895356 :     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
     440             : 
     441      120575 :     if (L.isNullValue() && U.isNullValue())
     442           0 :       return ConstantRange(getBitWidth());
     443             : 
     444      373065 :     return ConstantRange(std::move(L), std::move(U));
     445             :   }
     446             : 
     447       64688 :   if (!CR.isWrappedSet()) {
     448             :     // ------U   L-----  and  ------U   L----- : this
     449             :     //   L--U                            L--U  : CR
     450      120293 :     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
     451         912 :       return *this;
     452             : 
     453             :     // ------U   L----- : this
     454             :     //    L---------U   : CR
     455      117410 :     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
     456       19092 :       return ConstantRange(getBitWidth());
     457             : 
     458             :     // ----U       L---- : this
     459             :     //       L---U       : CR
     460             :     //    <d1>  <d2>
     461       81240 :     if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
     462      182439 :       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
     463       20271 :       if (d1.ult(d2))
     464         865 :         return ConstantRange(Lower, CR.Upper);
     465      100490 :       return ConstantRange(CR.Lower, Upper);
     466             :     }
     467             : 
     468             :     // ----U     L----- : this
     469             :     //        L----U    : CR
     470          90 :     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
     471          60 :       return ConstantRange(CR.Lower, Upper);
     472             : 
     473             :     // ------U    L---- : this
     474             :     //    L-----U       : CR
     475             :     assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
     476             :            "ConstantRange::unionWith missed a case with one range wrapped");
     477         270 :     return ConstantRange(Lower, CR.Upper);
     478             :   }
     479             : 
     480             :   // ------U    L----  and  ------U    L---- : this
     481             :   // -U  L-----------  and  ------------U  L : CR
     482       72991 :   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
     483          71 :     return ConstantRange(getBitWidth());
     484             : 
     485       72828 :   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
     486       97104 :   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
     487             : 
     488      121380 :   return ConstantRange(std::move(L), std::move(U));
     489             : }
     490             : 
     491        1855 : ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
     492             :                                     uint32_t ResultBitWidth) const {
     493        1855 :   switch (CastOp) {
     494           0 :   default:
     495           0 :     llvm_unreachable("unsupported cast type");
     496         295 :   case Instruction::Trunc:
     497         295 :     return truncate(ResultBitWidth);
     498          45 :   case Instruction::SExt:
     499          45 :     return signExtend(ResultBitWidth);
     500        1191 :   case Instruction::ZExt:
     501        1191 :     return zeroExtend(ResultBitWidth);
     502         225 :   case Instruction::BitCast:
     503         225 :     return *this;
     504          51 :   case Instruction::FPToUI:
     505             :   case Instruction::FPToSI:
     506          51 :     if (getBitWidth() == ResultBitWidth)
     507          51 :       return *this;
     508             :     else
     509           0 :       return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     510          41 :   case Instruction::UIToFP: {
     511             :     // TODO: use input range if available
     512          41 :     auto BW = getBitWidth();
     513         123 :     APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
     514         123 :     APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
     515         205 :     return ConstantRange(std::move(Min), std::move(Max));
     516             :   }
     517           7 :   case Instruction::SIToFP: {
     518             :     // TODO: use input range if available
     519           7 :     auto BW = getBitWidth();
     520          21 :     APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
     521          21 :     APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
     522          35 :     return ConstantRange(std::move(SMin), std::move(SMax));
     523             :   }
     524           0 :   case Instruction::FPTrunc:
     525             :   case Instruction::FPExt:
     526             :   case Instruction::IntToPtr:
     527             :   case Instruction::PtrToInt:
     528             :   case Instruction::AddrSpaceCast:
     529             :     // Conservatively return full set.
     530           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     531             :   };
     532             : }
     533             : 
     534       25684 : ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
     535       25684 :   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
     536             : 
     537       25683 :   unsigned SrcTySize = getBitWidth();
     538             :   assert(SrcTySize < DstTySize && "Not a value extension");
     539       25683 :   if (isFullSet() || isWrappedSet()) {
     540             :     // Change into [0, 1 << src bit width)
     541       36710 :     APInt LowerExt(DstTySize, 0);
     542       36710 :     if (!Upper) // special case: [X, 0) -- not really wrapping around
     543          39 :       LowerExt = Lower.zext(DstTySize);
     544       18355 :     return ConstantRange(std::move(LowerExt),
     545       73420 :                          APInt::getOneBitSet(DstTySize, SrcTySize));
     546             :   }
     547             : 
     548       21984 :   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
     549             : }
     550             : 
     551       14613 : ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
     552       14613 :   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
     553             : 
     554       14612 :   unsigned SrcTySize = getBitWidth();
     555             :   assert(SrcTySize < DstTySize && "Not a value extension");
     556             : 
     557             :   // special case: [X, INT_MIN) -- not really wrapping around
     558       14612 :   if (Upper.isMinSignedValue())
     559          63 :     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
     560             : 
     561       14591 :   if (isFullSet() || isSignWrappedSet()) {
     562       26898 :     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
     563       67245 :                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
     564             :   }
     565             : 
     566        3426 :   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
     567             : }
     568             : 
     569      165581 : ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
     570             :   assert(getBitWidth() > DstTySize && "Not a value truncation");
     571      165581 :   if (isEmptySet())
     572           1 :     return ConstantRange(DstTySize, /*isFullSet=*/false);
     573      165580 :   if (isFullSet())
     574        2235 :     return ConstantRange(DstTySize, /*isFullSet=*/true);
     575             : 
     576      653380 :   APInt LowerDiv(Lower), UpperDiv(Upper);
     577      326690 :   ConstantRange Union(DstTySize, /*isFullSet=*/false);
     578             : 
     579             :   // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
     580             :   // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
     581             :   // then we do the union with [MaxValue, Upper)
     582      163345 :   if (isWrappedSet()) {
     583             :     // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
     584             :     // truncated range.
     585      173345 :     if (Upper.getActiveBits() > DstTySize ||
     586       78730 :         Upper.countTrailingOnes() == DstTySize)
     587       28782 :       return ConstantRange(DstTySize, /*isFullSet=*/true);
     588             : 
     589      152832 :     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
     590       38208 :     UpperDiv.setAllBits();
     591             : 
     592             :     // Union covers the MaxValue case, so return if the remaining range is just
     593             :     // MaxValue(DstTy).
     594       38208 :     if (LowerDiv == UpperDiv)
     595             :       return Union;
     596             :   }
     597             : 
     598             :   // Chop off the most significant bits that are past the destination bitwidth.
     599      133857 :   if (LowerDiv.getActiveBits() > DstTySize) {
     600             :     // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
     601      153156 :     APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
     602       38289 :     LowerDiv -= Adjust;
     603       38289 :     UpperDiv -= Adjust;
     604             :   }
     605             : 
     606      133857 :   unsigned UpperDivWidth = UpperDiv.getActiveBits();
     607      133857 :   if (UpperDivWidth <= DstTySize)
     608      190299 :     return ConstantRange(LowerDiv.trunc(DstTySize),
     609      190299 :                          UpperDiv.trunc(DstTySize)).unionWith(Union);
     610             : 
     611             :   // The truncated value wraps around. Check if we can do better than fullset.
     612       70424 :   if (UpperDivWidth == DstTySize + 1) {
     613             :     // Clear the MSB so that UpperDiv wraps around.
     614        3247 :     UpperDiv.clearBit(DstTySize);
     615        3247 :     if (UpperDiv.ult(LowerDiv))
     616          54 :       return ConstantRange(LowerDiv.trunc(DstTySize),
     617          54 :                            UpperDiv.trunc(DstTySize)).unionWith(Union);
     618             :   }
     619             : 
     620       70406 :   return ConstantRange(DstTySize, /*isFullSet=*/true);
     621             : }
     622             : 
     623        1159 : ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
     624        1159 :   unsigned SrcTySize = getBitWidth();
     625        1159 :   if (SrcTySize > DstTySize)
     626          17 :     return truncate(DstTySize);
     627        1142 :   if (SrcTySize < DstTySize)
     628         147 :     return zeroExtend(DstTySize);
     629         995 :   return *this;
     630             : }
     631             : 
     632         262 : ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
     633         262 :   unsigned SrcTySize = getBitWidth();
     634         262 :   if (SrcTySize > DstTySize)
     635           1 :     return truncate(DstTySize);
     636         261 :   if (SrcTySize < DstTySize)
     637          54 :     return signExtend(DstTySize);
     638         207 :   return *this;
     639             : }
     640             : 
     641       11839 : ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
     642             :                                       const ConstantRange &Other) const {
     643             :   assert(BinOp >= Instruction::BinaryOpsBegin &&
     644             :          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
     645             : 
     646       11839 :   switch (BinOp) {
     647        9965 :   case Instruction::Add:
     648        9965 :     return add(Other);
     649           1 :   case Instruction::Sub:
     650           1 :     return sub(Other);
     651         146 :   case Instruction::Mul:
     652         146 :     return multiply(Other);
     653         146 :   case Instruction::UDiv:
     654         146 :     return udiv(Other);
     655         502 :   case Instruction::Shl:
     656         502 :     return shl(Other);
     657         545 :   case Instruction::LShr:
     658         545 :     return lshr(Other);
     659         315 :   case Instruction::And:
     660         315 :     return binaryAnd(Other);
     661         190 :   case Instruction::Or:
     662         190 :     return binaryOr(Other);
     663             :   // Note: floating point operations applied to abstract ranges are just
     664             :   // ideal integer operations with a lossy representation
     665          17 :   case Instruction::FAdd:
     666          17 :     return add(Other);
     667           4 :   case Instruction::FSub:
     668           4 :     return sub(Other);
     669           8 :   case Instruction::FMul:
     670           8 :     return multiply(Other);
     671           0 :   default:
     672             :     // Conservatively return full set.
     673           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     674             :   }
     675             : }
     676             : 
     677             : ConstantRange
     678      124001 : ConstantRange::add(const ConstantRange &Other) const {
     679      124001 :   if (isEmptySet() || Other.isEmptySet())
     680           8 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     681      123993 :   if (isFullSet() || Other.isFullSet())
     682       59524 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     683             : 
     684      322345 :   APInt NewLower = getLower() + Other.getLower();
     685      515752 :   APInt NewUpper = getUpper() + Other.getUpper() - 1;
     686       64469 :   if (NewLower == NewUpper)
     687          38 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     688             : 
     689      386586 :   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
     690      103231 :   if (X.isSizeStrictlySmallerThan(*this) ||
     691       38800 :       X.isSizeStrictlySmallerThan(Other))
     692             :     // We've wrapped, therefore, full set.
     693       25631 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     694             :   return X;
     695             : }
     696             : 
     697          28 : ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
     698             :   // Calculate the subset of this range such that "X + Other" is
     699             :   // guaranteed not to wrap (overflow) for all X in this subset.
     700             :   // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
     701             :   // passing a single element range.
     702             :   auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
     703          84 :                                       ConstantRange(Other),
     704          56 :                                       OverflowingBinaryOperator::NoSignedWrap);
     705          56 :   auto NSWConstrainedRange = intersectWith(NSWRange);
     706             : 
     707          84 :   return NSWConstrainedRange.add(ConstantRange(Other));
     708             : }
     709             : 
     710             : ConstantRange
     711          20 : ConstantRange::sub(const ConstantRange &Other) const {
     712          20 :   if (isEmptySet() || Other.isEmptySet())
     713           6 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     714          14 :   if (isFullSet() || Other.isFullSet())
     715           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     716             : 
     717          63 :   APInt NewLower = getLower() - Other.getUpper() + 1;
     718          54 :   APInt NewUpper = getUpper() - Other.getLower();
     719           9 :   if (NewLower == NewUpper)
     720           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     721             : 
     722          54 :   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
     723          18 :   if (X.isSizeStrictlySmallerThan(*this) ||
     724           9 :       X.isSizeStrictlySmallerThan(Other))
     725             :     // We've wrapped, therefore, full set.
     726           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     727             :   return X;
     728             : }
     729             : 
     730             : ConstantRange
     731       93296 : ConstantRange::multiply(const ConstantRange &Other) const {
     732             :   // TODO: If either operand is a single element and the multiply is known to
     733             :   // be non-wrapping, round the result min and max value to the appropriate
     734             :   // multiple of that element. If wrapping is possible, at least adjust the
     735             :   // range according to the greatest power-of-two factor of the single element.
     736             : 
     737       93296 :   if (isEmptySet() || Other.isEmptySet())
     738           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     739             : 
     740             :   // Multiplication is signedness-independent. However different ranges can be
     741             :   // obtained depending on how the input ranges are treated. These different
     742             :   // ranges are all conservatively correct, but one might be better than the
     743             :   // other. We calculate two ranges; one treating the inputs as unsigned
     744             :   // and the other signed, then return the smallest of these ranges.
     745             : 
     746             :   // Unsigned range first.
     747      279873 :   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
     748      373164 :   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
     749      373164 :   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
     750      373164 :   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
     751             : 
     752      186582 :   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
     753      559746 :                                             this_max * Other_max + 1);
     754      186582 :   ConstantRange UR = Result_zext.truncate(getBitWidth());
     755             : 
     756             :   // If the unsigned range doesn't wrap, and isn't negative then it's a range
     757             :   // from one positive number to another which is as good as we can generate.
     758             :   // In this case, skip the extra work of generating signed ranges which aren't
     759             :   // going to be better than this range.
     760      186569 :   if (!UR.isWrappedSet() &&
     761      255060 :       (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
     762             :     return UR;
     763             : 
     764             :   // Now the signed range. Because we could be dealing with negative numbers
     765             :   // here, the lower bound is the smallest of the cartesian product of the
     766             :   // lower and upper ranges; for example:
     767             :   //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
     768             :   // Similarly for the upper bound, swapping min for max.
     769             : 
     770      342585 :   this_min = getSignedMin().sext(getBitWidth() * 2);
     771      342585 :   this_max = getSignedMax().sext(getBitWidth() * 2);
     772      342585 :   Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
     773      342585 :   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
     774             :   
     775       68517 :   auto L = {this_min * Other_min, this_min * Other_max,
     776      411102 :             this_max * Other_min, this_max * Other_max};
     777      411102 :   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
     778      411102 :   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
     779      137034 :   ConstantRange SR = Result_sext.truncate(getBitWidth());
     780             : 
     781       68517 :   return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
     782             : }
     783             : 
     784             : ConstantRange
     785        4169 : ConstantRange::smax(const ConstantRange &Other) const {
     786             :   // X smax Y is: range(smax(X_smin, Y_smin),
     787             :   //                    smax(X_smax, Y_smax))
     788        4169 :   if (isEmptySet() || Other.isEmptySet())
     789           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     790       20820 :   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
     791       33312 :   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
     792        4164 :   if (NewU == NewL)
     793         396 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     794       18840 :   return ConstantRange(std::move(NewL), std::move(NewU));
     795             : }
     796             : 
     797             : ConstantRange
     798        1020 : ConstantRange::umax(const ConstantRange &Other) const {
     799             :   // X umax Y is: range(umax(X_umin, Y_umin),
     800             :   //                    umax(X_umax, Y_umax))
     801        1020 :   if (isEmptySet() || Other.isEmptySet())
     802           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     803        5075 :   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
     804        8120 :   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
     805        1015 :   if (NewU == NewL)
     806         401 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     807        3070 :   return ConstantRange(std::move(NewL), std::move(NewU));
     808             : }
     809             : 
     810             : ConstantRange
     811          19 : ConstantRange::smin(const ConstantRange &Other) const {
     812             :   // X smin Y is: range(smin(X_smin, Y_smin),
     813             :   //                    smin(X_smax, Y_smax))
     814          19 :   if (isEmptySet() || Other.isEmptySet())
     815           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     816          70 :   APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
     817         112 :   APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
     818          14 :   if (NewU == NewL)
     819           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     820          55 :   return ConstantRange(std::move(NewL), std::move(NewU));
     821             : }
     822             : 
     823             : ConstantRange
     824          50 : ConstantRange::umin(const ConstantRange &Other) const {
     825             :   // X umin Y is: range(umin(X_umin, Y_umin),
     826             :   //                    umin(X_umax, Y_umax))
     827          50 :   if (isEmptySet() || Other.isEmptySet())
     828           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     829         225 :   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
     830         360 :   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
     831          45 :   if (NewU == NewL)
     832           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     833         210 :   return ConstantRange(std::move(NewL), std::move(NewU));
     834             : }
     835             : 
     836             : ConstantRange
     837        3702 : ConstantRange::udiv(const ConstantRange &RHS) const {
     838       11101 :   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
     839           7 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     840        3695 :   if (RHS.isFullSet())
     841         301 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     842             : 
     843       10182 :   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
     844             : 
     845        6788 :   APInt RHS_umin = RHS.getUnsignedMin();
     846        3394 :   if (RHS_umin.isNullValue()) {
     847             :     // We want the lowest value in RHS excluding zero. Usually that would be 1
     848             :     // except for a range in the form of [X, 1) in which case it would be X.
     849          43 :     if (RHS.getUpper() == 1)
     850           0 :       RHS_umin = RHS.getLower();
     851             :     else
     852          43 :       RHS_umin = 1;
     853             :   }
     854             : 
     855       16970 :   APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
     856             : 
     857             :   // If the LHS is Full and the RHS is a wrapped interval containing 1 then
     858             :   // this could occur.
     859        3394 :   if (Lower == Upper)
     860          54 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     861             : 
     862       16700 :   return ConstantRange(std::move(Lower), std::move(Upper));
     863             : }
     864             : 
     865             : ConstantRange
     866         315 : ConstantRange::binaryAnd(const ConstantRange &Other) const {
     867         315 :   if (isEmptySet() || Other.isEmptySet())
     868           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     869             : 
     870             :   // TODO: replace this with something less conservative
     871             : 
     872        1575 :   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
     873         315 :   if (umin.isAllOnesValue())
     874           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     875        2205 :   return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
     876             : }
     877             : 
     878             : ConstantRange
     879         190 : ConstantRange::binaryOr(const ConstantRange &Other) const {
     880         190 :   if (isEmptySet() || Other.isEmptySet())
     881           0 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     882             : 
     883             :   // TODO: replace this with something less conservative
     884             : 
     885         950 :   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
     886         190 :   if (umax.isNullValue())
     887           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     888         748 :   return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
     889             : }
     890             : 
     891             : ConstantRange
     892         517 : ConstantRange::shl(const ConstantRange &Other) const {
     893         517 :   if (isEmptySet() || Other.isEmptySet())
     894           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     895             : 
     896         512 :   APInt max = getUnsignedMax();
     897        1024 :   APInt Other_umax = Other.getUnsignedMax();
     898             : 
     899             :   // there's overflow!
     900        1024 :   if (Other_umax.uge(max.countLeadingZeros()))
     901         222 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     902             : 
     903             :   // FIXME: implement the other tricky cases
     904             : 
     905         290 :   APInt min = getUnsignedMin();
     906         580 :   min <<= Other.getUnsignedMin();
     907         290 :   max <<= Other_umax;
     908             : 
     909        2030 :   return ConstantRange(std::move(min), std::move(max) + 1);
     910             : }
     911             : 
     912             : ConstantRange
     913         560 : ConstantRange::lshr(const ConstantRange &Other) const {
     914         560 :   if (isEmptySet() || Other.isEmptySet())
     915           5 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     916             : 
     917        2775 :   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
     918        2220 :   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
     919         555 :   if (min == max)
     920           3 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     921             : 
     922        2760 :   return ConstantRange(std::move(min), std::move(max));
     923             : }
     924             : 
     925     3516366 : ConstantRange ConstantRange::inverse() const {
     926     3516366 :   if (isFullSet())
     927     1063052 :     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
     928     2453314 :   if (isEmptySet())
     929          21 :     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
     930    12266465 :   return ConstantRange(Upper, Lower);
     931             : }
     932             : 
     933        3968 : void ConstantRange::print(raw_ostream &OS) const {
     934        3968 :   if (isFullSet())
     935        1916 :     OS << "full-set";
     936        2052 :   else if (isEmptySet())
     937           2 :     OS << "empty-set";
     938             :   else
     939        6150 :     OS << "[" << Lower << "," << Upper << ")";
     940        3968 : }
     941             : 
     942             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     943             : LLVM_DUMP_METHOD void ConstantRange::dump() const {
     944             :   print(dbgs());
     945             : }
     946             : #endif
     947             : 
     948       65348 : ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
     949       65348 :   const unsigned NumRanges = Ranges.getNumOperands() / 2;
     950             :   assert(NumRanges >= 1 && "Must have at least one range!");
     951             :   assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
     952             : 
     953      130696 :   auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
     954      130696 :   auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
     955             : 
     956      392088 :   ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
     957             : 
     958       65356 :   for (unsigned i = 1; i < NumRanges; ++i) {
     959          24 :     auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
     960          24 :     auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
     961             : 
     962             :     // Note: unionWith will potentially create a range that contains values not
     963             :     // contained in any of the original N ranges.
     964          48 :     CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
     965             :   }
     966             : 
     967       65348 :   return CR;
     968             : }

Generated by: LCOV version 1.13