brintos / llvm-project-archived public Read only

1//===- ConstantRange.cpp - ConstantRange implementation -------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Represent a range of possible values that may occur when the program is run10// for an integral value.  This keeps track of a lower and upper bound for the11// constant, which MAY wrap around the end of the numeric range.  To do this, it12// keeps track of a [lower, upper) bound, which specifies an interval just like13// STL iterators.  When used with boolean values, the following are important14// ranges (other integral ranges use min/max values for special range values):15//16//  [F, F) = {}     = Empty set17//  [T, F) = {T}18//  [F, T) = {F}19//  [T, T) = {F, T} = Full set20//21//===----------------------------------------------------------------------===//22 23#include "llvm/IR/ConstantRange.h"24#include "llvm/ADT/APInt.h"25#include "llvm/Config/llvm-config.h"26#include "llvm/IR/Constants.h"27#include "llvm/IR/InstrTypes.h"28#include "llvm/IR/Instruction.h"29#include "llvm/IR/Instructions.h"30#include "llvm/IR/Intrinsics.h"31#include "llvm/IR/Metadata.h"32#include "llvm/IR/Operator.h"33#include "llvm/Support/Compiler.h"34#include "llvm/Support/Debug.h"35#include "llvm/Support/ErrorHandling.h"36#include "llvm/Support/KnownBits.h"37#include "llvm/Support/raw_ostream.h"38#include <algorithm>39#include <cassert>40#include <cstdint>41#include <optional>42 43using namespace llvm;44 45ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)46    : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),47      Upper(Lower) {}48 49ConstantRange::ConstantRange(APInt V)50    : Lower(std::move(V)), Upper(Lower + 1) {}51 52ConstantRange::ConstantRange(APInt L, APInt U)53    : Lower(std::move(L)), Upper(std::move(U)) {54  assert(Lower.getBitWidth() == Upper.getBitWidth() &&55         "ConstantRange with unequal bit widths");56  assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&57         "Lower == Upper, but they aren't min or max value!");58}59 60ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known,61                                           bool IsSigned) {62  if (Known.hasConflict())63    return getEmpty(Known.getBitWidth());64  if (Known.isUnknown())65    return getFull(Known.getBitWidth());66 67  // For unsigned ranges, or signed ranges with known sign bit, create a simple68  // range between the smallest and largest possible value.69  if (!IsSigned || Known.isNegative() || Known.isNonNegative())70    return ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1);71 72  // If we don't know the sign bit, pick the lower bound as a negative number73  // and the upper bound as a non-negative one.74  APInt Lower = Known.getMinValue(), Upper = Known.getMaxValue();75  Lower.setSignBit();76  Upper.clearSignBit();77  return ConstantRange(Lower, Upper + 1);78}79 80KnownBits ConstantRange::toKnownBits() const {81  // TODO: We could return conflicting known bits here, but consumers are82  // likely not prepared for that.83  if (isEmptySet())84    return KnownBits(getBitWidth());85 86  // We can only retain the top bits that are the same between min and max.87  APInt Min = getUnsignedMin();88  APInt Max = getUnsignedMax();89  KnownBits Known = KnownBits::makeConstant(Min);90  if (std::optional<unsigned> DifferentBit =91          APIntOps::GetMostSignificantDifferentBit(Min, Max)) {92    Known.Zero.clearLowBits(*DifferentBit + 1);93    Known.One.clearLowBits(*DifferentBit + 1);94  }95  return Known;96}97 98std::pair<ConstantRange, ConstantRange> ConstantRange::splitPosNeg() const {99  uint32_t BW = getBitWidth();100  APInt Zero = APInt::getZero(BW), One = APInt(BW, 1);101  APInt SignedMin = APInt::getSignedMinValue(BW);102  // There are no positive 1-bit values. The 1 would get interpreted as -1.103  ConstantRange PosFilter =104      BW == 1 ? getEmpty() : ConstantRange(One, SignedMin);105  ConstantRange NegFilter(SignedMin, Zero);106  return {intersectWith(PosFilter), intersectWith(NegFilter)};107}108 109ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,110                                                   const ConstantRange &CR) {111  if (CR.isEmptySet())112    return CR;113 114  uint32_t W = CR.getBitWidth();115  switch (Pred) {116  default:117    llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");118  case CmpInst::ICMP_EQ:119    return CR;120  case CmpInst::ICMP_NE:121    if (CR.isSingleElement())122      return ConstantRange(CR.getUpper(), CR.getLower());123    return getFull(W);124  case CmpInst::ICMP_ULT: {125    APInt UMax(CR.getUnsignedMax());126    if (UMax.isMinValue())127      return getEmpty(W);128    return ConstantRange(APInt::getMinValue(W), std::move(UMax));129  }130  case CmpInst::ICMP_SLT: {131    APInt SMax(CR.getSignedMax());132    if (SMax.isMinSignedValue())133      return getEmpty(W);134    return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));135  }136  case CmpInst::ICMP_ULE:137    return getNonEmpty(APInt::getMinValue(W), CR.getUnsignedMax() + 1);138  case CmpInst::ICMP_SLE:139    return getNonEmpty(APInt::getSignedMinValue(W), CR.getSignedMax() + 1);140  case CmpInst::ICMP_UGT: {141    APInt UMin(CR.getUnsignedMin());142    if (UMin.isMaxValue())143      return getEmpty(W);144    return ConstantRange(std::move(UMin) + 1, APInt::getZero(W));145  }146  case CmpInst::ICMP_SGT: {147    APInt SMin(CR.getSignedMin());148    if (SMin.isMaxSignedValue())149      return getEmpty(W);150    return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));151  }152  case CmpInst::ICMP_UGE:153    return getNonEmpty(CR.getUnsignedMin(), APInt::getZero(W));154  case CmpInst::ICMP_SGE:155    return getNonEmpty(CR.getSignedMin(), APInt::getSignedMinValue(W));156  }157}158 159ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,160                                                      const ConstantRange &CR) {161  // Follows from De-Morgan's laws:162  //163  // ~(~A union ~B) == A intersect B.164  //165  return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)166      .inverse();167}168 169ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,170                                                 const APInt &C) {171  // Computes the exact range that is equal to both the constant ranges returned172  // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true173  // when RHS is a singleton such as an APInt. However for non-singleton RHS,174  // for example ult [2,5) makeAllowedICmpRegion returns [0,4) but175  // makeSatisfyICmpRegion returns [0,2).176  //177  return makeAllowedICmpRegion(Pred, C);178}179 180bool ConstantRange::areInsensitiveToSignednessOfICmpPredicate(181    const ConstantRange &CR1, const ConstantRange &CR2) {182  if (CR1.isEmptySet() || CR2.isEmptySet())183    return true;184 185  return (CR1.isAllNonNegative() && CR2.isAllNonNegative()) ||186         (CR1.isAllNegative() && CR2.isAllNegative());187}188 189bool ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate(190    const ConstantRange &CR1, const ConstantRange &CR2) {191  if (CR1.isEmptySet() || CR2.isEmptySet())192    return true;193 194  return (CR1.isAllNonNegative() && CR2.isAllNegative()) ||195         (CR1.isAllNegative() && CR2.isAllNonNegative());196}197 198CmpInst::Predicate ConstantRange::getEquivalentPredWithFlippedSignedness(199    CmpInst::Predicate Pred, const ConstantRange &CR1,200    const ConstantRange &CR2) {201  assert(CmpInst::isIntPredicate(Pred) && CmpInst::isRelational(Pred) &&202         "Only for relational integer predicates!");203 204  CmpInst::Predicate FlippedSignednessPred =205      ICmpInst::getFlippedSignednessPredicate(Pred);206 207  if (areInsensitiveToSignednessOfICmpPredicate(CR1, CR2))208    return FlippedSignednessPred;209 210  if (areInsensitiveToSignednessOfInvertedICmpPredicate(CR1, CR2))211    return CmpInst::getInversePredicate(FlippedSignednessPred);212 213  return CmpInst::Predicate::BAD_ICMP_PREDICATE;214}215 216void ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,217                                      APInt &RHS, APInt &Offset) const {218  Offset = APInt(getBitWidth(), 0);219  if (isFullSet() || isEmptySet()) {220    Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;221    RHS = APInt(getBitWidth(), 0);222  } else if (auto *OnlyElt = getSingleElement()) {223    Pred = CmpInst::ICMP_EQ;224    RHS = *OnlyElt;225  } else if (auto *OnlyMissingElt = getSingleMissingElement()) {226    Pred = CmpInst::ICMP_NE;227    RHS = *OnlyMissingElt;228  } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {229    Pred =230        getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;231    RHS = getUpper();232  } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {233    Pred =234        getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;235    RHS = getLower();236  } else {237    Pred = CmpInst::ICMP_ULT;238    RHS = getUpper() - getLower();239    Offset = -getLower();240  }241 242  assert(ConstantRange::makeExactICmpRegion(Pred, RHS) == add(Offset) &&243         "Bad result!");244}245 246bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,247                                      APInt &RHS) const {248  APInt Offset;249  getEquivalentICmp(Pred, RHS, Offset);250  return Offset.isZero();251}252 253bool ConstantRange::icmp(CmpInst::Predicate Pred,254                         const ConstantRange &Other) const {255  if (isEmptySet() || Other.isEmptySet())256    return true;257 258  switch (Pred) {259  case CmpInst::ICMP_EQ:260    if (const APInt *L = getSingleElement())261      if (const APInt *R = Other.getSingleElement())262        return *L == *R;263    return false;264  case CmpInst::ICMP_NE:265    return inverse().contains(Other);266  case CmpInst::ICMP_ULT:267    return getUnsignedMax().ult(Other.getUnsignedMin());268  case CmpInst::ICMP_ULE:269    return getUnsignedMax().ule(Other.getUnsignedMin());270  case CmpInst::ICMP_UGT:271    return getUnsignedMin().ugt(Other.getUnsignedMax());272  case CmpInst::ICMP_UGE:273    return getUnsignedMin().uge(Other.getUnsignedMax());274  case CmpInst::ICMP_SLT:275    return getSignedMax().slt(Other.getSignedMin());276  case CmpInst::ICMP_SLE:277    return getSignedMax().sle(Other.getSignedMin());278  case CmpInst::ICMP_SGT:279    return getSignedMin().sgt(Other.getSignedMax());280  case CmpInst::ICMP_SGE:281    return getSignedMin().sge(Other.getSignedMax());282  default:283    llvm_unreachable("Invalid ICmp predicate");284  }285}286 287/// Exact mul nuw region for single element RHS.288static ConstantRange makeExactMulNUWRegion(const APInt &V) {289  unsigned BitWidth = V.getBitWidth();290  if (V == 0)291    return ConstantRange::getFull(V.getBitWidth());292 293  return ConstantRange::getNonEmpty(294      APIntOps::RoundingUDiv(APInt::getMinValue(BitWidth), V,295                             APInt::Rounding::UP),296      APIntOps::RoundingUDiv(APInt::getMaxValue(BitWidth), V,297                             APInt::Rounding::DOWN) + 1);298}299 300/// Exact mul nsw region for single element RHS.301static ConstantRange makeExactMulNSWRegion(const APInt &V) {302  // Handle 0 and -1 separately to avoid division by zero or overflow.303  unsigned BitWidth = V.getBitWidth();304  if (V == 0)305    return ConstantRange::getFull(BitWidth);306 307  APInt MinValue = APInt::getSignedMinValue(BitWidth);308  APInt MaxValue = APInt::getSignedMaxValue(BitWidth);309  // e.g. Returning [-127, 127], represented as [-127, -128).310  if (V.isAllOnes())311    return ConstantRange(-MaxValue, MinValue);312 313  APInt Lower, Upper;314  if (V.isNegative()) {315    Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP);316    Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN);317  } else {318    Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP);319    Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN);320  }321  return ConstantRange::getNonEmpty(Lower, Upper + 1);322}323 324ConstantRange325ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,326                                          const ConstantRange &Other,327                                          unsigned NoWrapKind) {328  using OBO = OverflowingBinaryOperator;329 330  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");331 332  assert((NoWrapKind == OBO::NoSignedWrap ||333          NoWrapKind == OBO::NoUnsignedWrap) &&334         "NoWrapKind invalid!");335 336  bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;337  unsigned BitWidth = Other.getBitWidth();338 339  switch (BinOp) {340  default:341    llvm_unreachable("Unsupported binary op");342 343  case Instruction::Add: {344    if (Unsigned)345      return getNonEmpty(APInt::getZero(BitWidth), -Other.getUnsignedMax());346 347    APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);348    APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();349    return getNonEmpty(350        SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal,351        SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal);352  }353 354  case Instruction::Sub: {355    if (Unsigned)356      return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth));357 358    APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);359    APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();360    return getNonEmpty(361        SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal,362        SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal);363  }364 365  case Instruction::Mul:366    if (Unsigned)367      return makeExactMulNUWRegion(Other.getUnsignedMax());368 369    // Avoid one makeExactMulNSWRegion() call for the common case of constants.370    if (const APInt *C = Other.getSingleElement())371      return makeExactMulNSWRegion(*C);372 373    return makeExactMulNSWRegion(Other.getSignedMin())374        .intersectWith(makeExactMulNSWRegion(Other.getSignedMax()));375 376  case Instruction::Shl: {377    // For given range of shift amounts, if we ignore all illegal shift amounts378    // (that always produce poison), what shift amount range is left?379    ConstantRange ShAmt = Other.intersectWith(380        ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, (BitWidth - 1) + 1)));381    if (ShAmt.isEmptySet()) {382      // If the entire range of shift amounts is already poison-producing,383      // then we can freely add more poison-producing flags ontop of that.384      return getFull(BitWidth);385    }386    // There are some legal shift amounts, we can compute conservatively-correct387    // range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax388    // to be at most bitwidth-1, which results in most conservative range.389    APInt ShAmtUMax = ShAmt.getUnsignedMax();390    if (Unsigned)391      return getNonEmpty(APInt::getZero(BitWidth),392                         APInt::getMaxValue(BitWidth).lshr(ShAmtUMax) + 1);393    return getNonEmpty(APInt::getSignedMinValue(BitWidth).ashr(ShAmtUMax),394                       APInt::getSignedMaxValue(BitWidth).ashr(ShAmtUMax) + 1);395  }396  }397}398 399ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp,400                                                   const APInt &Other,401                                                   unsigned NoWrapKind) {402  // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as403  // "for all" and "for any" coincide in this case.404  return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind);405}406 407ConstantRange ConstantRange::makeMaskNotEqualRange(const APInt &Mask,408                                                   const APInt &C) {409  unsigned BitWidth = Mask.getBitWidth();410 411  if ((Mask & C) != C)412    return getFull(BitWidth);413 414  if (Mask.isZero())415    return getEmpty(BitWidth);416 417  // If (Val & Mask) != C, constrained to the non-equality being418  // satisfiable, then the value must be larger than the lowest set bit of419  // Mask, offset by constant C.420  return ConstantRange::getNonEmpty(421      APInt::getOneBitSet(BitWidth, Mask.countr_zero()) + C, C);422}423 424bool ConstantRange::isFullSet() const {425  return Lower == Upper && Lower.isMaxValue();426}427 428bool ConstantRange::isEmptySet() const {429  return Lower == Upper && Lower.isMinValue();430}431 432bool ConstantRange::isWrappedSet() const {433  return Lower.ugt(Upper) && !Upper.isZero();434}435 436bool ConstantRange::isUpperWrapped() const {437  return Lower.ugt(Upper);438}439 440bool ConstantRange::isSignWrappedSet() const {441  return Lower.sgt(Upper) && !Upper.isMinSignedValue();442}443 444bool ConstantRange::isUpperSignWrapped() const {445  return Lower.sgt(Upper);446}447 448bool449ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {450  assert(getBitWidth() == Other.getBitWidth());451  if (isFullSet())452    return false;453  if (Other.isFullSet())454    return true;455  return (Upper - Lower).ult(Other.Upper - Other.Lower);456}457 458bool459ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {460  // If this a full set, we need special handling to avoid needing an extra bit461  // to represent the size.462  if (isFullSet())463    return MaxSize == 0 || APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);464 465  return (Upper - Lower).ugt(MaxSize);466}467 468bool ConstantRange::isAllNegative() const {469  // Empty set is all negative, full set is not.470  if (isEmptySet())471    return true;472  if (isFullSet())473    return false;474 475  return !isUpperSignWrapped() && !Upper.isStrictlyPositive();476}477 478bool ConstantRange::isAllNonNegative() const {479  // Empty and full set are automatically treated correctly.480  return !isSignWrappedSet() && Lower.isNonNegative();481}482 483bool ConstantRange::isAllPositive() const {484  // Empty set is all positive, full set is not.485  if (isEmptySet())486    return true;487  if (isFullSet())488    return false;489 490  return !isSignWrappedSet() && Lower.isStrictlyPositive();491}492 493APInt ConstantRange::getUnsignedMax() const {494  if (isFullSet() || isUpperWrapped())495    return APInt::getMaxValue(getBitWidth());496  return getUpper() - 1;497}498 499APInt ConstantRange::getUnsignedMin() const {500  if (isFullSet() || isWrappedSet())501    return APInt::getMinValue(getBitWidth());502  return getLower();503}504 505APInt ConstantRange::getSignedMax() const {506  if (isFullSet() || isUpperSignWrapped())507    return APInt::getSignedMaxValue(getBitWidth());508  return getUpper() - 1;509}510 511APInt ConstantRange::getSignedMin() const {512  if (isFullSet() || isSignWrappedSet())513    return APInt::getSignedMinValue(getBitWidth());514  return getLower();515}516 517bool ConstantRange::contains(const APInt &V) const {518  if (Lower == Upper)519    return isFullSet();520 521  if (!isUpperWrapped())522    return Lower.ule(V) && V.ult(Upper);523  return Lower.ule(V) || V.ult(Upper);524}525 526bool ConstantRange::contains(const ConstantRange &Other) const {527  if (isFullSet() || Other.isEmptySet()) return true;528  if (isEmptySet() || Other.isFullSet()) return false;529 530  if (!isUpperWrapped()) {531    if (Other.isUpperWrapped())532      return false;533 534    return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);535  }536 537  if (!Other.isUpperWrapped())538    return Other.getUpper().ule(Upper) ||539           Lower.ule(Other.getLower());540 541  return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());542}543 544unsigned ConstantRange::getActiveBits() const {545  if (isEmptySet())546    return 0;547 548  return getUnsignedMax().getActiveBits();549}550 551unsigned ConstantRange::getMinSignedBits() const {552  if (isEmptySet())553    return 0;554 555  return std::max(getSignedMin().getSignificantBits(),556                  getSignedMax().getSignificantBits());557}558 559ConstantRange ConstantRange::subtract(const APInt &Val) const {560  assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");561  // If the set is empty or full, don't modify the endpoints.562  if (Lower == Upper)563    return *this;564  return ConstantRange(Lower - Val, Upper - Val);565}566 567ConstantRange ConstantRange::difference(const ConstantRange &CR) const {568  return intersectWith(CR.inverse());569}570 571static ConstantRange getPreferredRange(572    const ConstantRange &CR1, const ConstantRange &CR2,573    ConstantRange::PreferredRangeType Type) {574  if (Type == ConstantRange::Unsigned) {575    if (!CR1.isWrappedSet() && CR2.isWrappedSet())576      return CR1;577    if (CR1.isWrappedSet() && !CR2.isWrappedSet())578      return CR2;579  } else if (Type == ConstantRange::Signed) {580    if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())581      return CR1;582    if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())583      return CR2;584  }585 586  if (CR1.isSizeStrictlySmallerThan(CR2))587    return CR1;588  return CR2;589}590 591ConstantRange ConstantRange::intersectWith(const ConstantRange &CR,592                                           PreferredRangeType Type) const {593  assert(getBitWidth() == CR.getBitWidth() &&594         "ConstantRange types don't agree!");595 596  // Handle common cases.597  if (   isEmptySet() || CR.isFullSet()) return *this;598  if (CR.isEmptySet() ||    isFullSet()) return CR;599 600  if (!isUpperWrapped() && CR.isUpperWrapped())601    return CR.intersectWith(*this, Type);602 603  if (!isUpperWrapped() && !CR.isUpperWrapped()) {604    if (Lower.ult(CR.Lower)) {605      // L---U       : this606      //       L---U : CR607      if (Upper.ule(CR.Lower))608        return getEmpty();609 610      // L---U       : this611      //   L---U     : CR612      if (Upper.ult(CR.Upper))613        return ConstantRange(CR.Lower, Upper);614 615      // L-------U   : this616      //   L---U     : CR617      return CR;618    }619    //   L---U     : this620    // L-------U   : CR621    if (Upper.ult(CR.Upper))622      return *this;623 624    //   L-----U   : this625    // L-----U     : CR626    if (Lower.ult(CR.Upper))627      return ConstantRange(Lower, CR.Upper);628 629    //       L---U : this630    // L---U       : CR631    return getEmpty();632  }633 634  if (isUpperWrapped() && !CR.isUpperWrapped()) {635    if (CR.Lower.ult(Upper)) {636      // ------U   L--- : this637      //  L--U          : CR638      if (CR.Upper.ult(Upper))639        return CR;640 641      // ------U   L--- : this642      //  L------U      : CR643      if (CR.Upper.ule(Lower))644        return ConstantRange(CR.Lower, Upper);645 646      // ------U   L--- : this647      //  L----------U  : CR648      return getPreferredRange(*this, CR, Type);649    }650    if (CR.Lower.ult(Lower)) {651      // --U      L---- : this652      //     L--U       : CR653      if (CR.Upper.ule(Lower))654        return getEmpty();655 656      // --U      L---- : this657      //     L------U   : CR658      return ConstantRange(Lower, CR.Upper);659    }660 661    // --U  L------ : this662    //        L--U  : CR663    return CR;664  }665 666  if (CR.Upper.ult(Upper)) {667    // ------U L-- : this668    // --U L------ : CR669    if (CR.Lower.ult(Upper))670      return getPreferredRange(*this, CR, Type);671 672    // ----U   L-- : this673    // --U   L---- : CR674    if (CR.Lower.ult(Lower))675      return ConstantRange(Lower, CR.Upper);676 677    // ----U L---- : this678    // --U     L-- : CR679    return CR;680  }681  if (CR.Upper.ule(Lower)) {682    // --U     L-- : this683    // ----U L---- : CR684    if (CR.Lower.ult(Lower))685      return *this;686 687    // --U   L---- : this688    // ----U   L-- : CR689    return ConstantRange(CR.Lower, Upper);690  }691 692  // --U L------ : this693  // ------U L-- : CR694  return getPreferredRange(*this, CR, Type);695}696 697ConstantRange ConstantRange::unionWith(const ConstantRange &CR,698                                       PreferredRangeType Type) const {699  assert(getBitWidth() == CR.getBitWidth() &&700         "ConstantRange types don't agree!");701 702  if (   isFullSet() || CR.isEmptySet()) return *this;703  if (CR.isFullSet() ||    isEmptySet()) return CR;704 705  if (!isUpperWrapped() && CR.isUpperWrapped())706    return CR.unionWith(*this, Type);707 708  if (!isUpperWrapped() && !CR.isUpperWrapped()) {709    //        L---U  and  L---U        : this710    //  L---U                   L---U  : CR711    // result in one of712    //  L---------U713    // -----U L-----714    if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower))715      return getPreferredRange(716          ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);717 718    APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;719    APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;720 721    if (L.isZero() && U.isZero())722      return getFull();723 724    return ConstantRange(std::move(L), std::move(U));725  }726 727  if (!CR.isUpperWrapped()) {728    // ------U   L-----  and  ------U   L----- : this729    //   L--U                            L--U  : CR730    if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))731      return *this;732 733    // ------U   L----- : this734    //    L---------U   : CR735    if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))736      return getFull();737 738    // ----U       L---- : this739    //       L---U       : CR740    // results in one of741    // ----------U L----742    // ----U L----------743    if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower))744      return getPreferredRange(745          ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);746 747    // ----U     L----- : this748    //        L----U    : CR749    if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))750      return ConstantRange(CR.Lower, Upper);751 752    // ------U    L---- : this753    //    L-----U       : CR754    assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&755           "ConstantRange::unionWith missed a case with one range wrapped");756    return ConstantRange(Lower, CR.Upper);757  }758 759  // ------U    L----  and  ------U    L---- : this760  // -U  L-----------  and  ------------U  L : CR761  if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))762    return getFull();763 764  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;765  APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;766 767  return ConstantRange(std::move(L), std::move(U));768}769 770std::optional<ConstantRange>771ConstantRange::exactIntersectWith(const ConstantRange &CR) const {772  // TODO: This can be implemented more efficiently.773  ConstantRange Result = intersectWith(CR);774  if (Result == inverse().unionWith(CR.inverse()).inverse())775    return Result;776  return std::nullopt;777}778 779std::optional<ConstantRange>780ConstantRange::exactUnionWith(const ConstantRange &CR) const {781  // TODO: This can be implemented more efficiently.782  ConstantRange Result = unionWith(CR);783  if (Result == inverse().intersectWith(CR.inverse()).inverse())784    return Result;785  return std::nullopt;786}787 788ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,789                                    uint32_t ResultBitWidth) const {790  switch (CastOp) {791  default:792    llvm_unreachable("unsupported cast type");793  case Instruction::Trunc:794    return truncate(ResultBitWidth);795  case Instruction::SExt:796    return signExtend(ResultBitWidth);797  case Instruction::ZExt:798    return zeroExtend(ResultBitWidth);799  case Instruction::BitCast:800    return *this;801  case Instruction::FPToUI:802  case Instruction::FPToSI:803    if (getBitWidth() == ResultBitWidth)804      return *this;805    else806      return getFull(ResultBitWidth);807  case Instruction::UIToFP: {808    // TODO: use input range if available809    auto BW = getBitWidth();810    APInt Min = APInt::getMinValue(BW);811    APInt Max = APInt::getMaxValue(BW);812    if (ResultBitWidth > BW) {813      Min = Min.zext(ResultBitWidth);814      Max = Max.zext(ResultBitWidth);815    }816    return getNonEmpty(std::move(Min), std::move(Max) + 1);817  }818  case Instruction::SIToFP: {819    // TODO: use input range if available820    auto BW = getBitWidth();821    APInt SMin = APInt::getSignedMinValue(BW);822    APInt SMax = APInt::getSignedMaxValue(BW);823    if (ResultBitWidth > BW) {824      SMin = SMin.sext(ResultBitWidth);825      SMax = SMax.sext(ResultBitWidth);826    }827    return getNonEmpty(std::move(SMin), std::move(SMax) + 1);828  }829  case Instruction::FPTrunc:830  case Instruction::FPExt:831  case Instruction::IntToPtr:832  case Instruction::PtrToAddr:833  case Instruction::PtrToInt:834  case Instruction::AddrSpaceCast:835    // Conservatively return getFull set.836    return getFull(ResultBitWidth);837  };838}839 840ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {841  if (isEmptySet()) return getEmpty(DstTySize);842 843  unsigned SrcTySize = getBitWidth();844  if (DstTySize == SrcTySize)845    return *this;846  assert(SrcTySize < DstTySize && "Not a value extension");847  if (isFullSet() || isUpperWrapped()) {848    // Change into [0, 1 << src bit width)849    APInt LowerExt(DstTySize, 0);850    if (!Upper) // special case: [X, 0) -- not really wrapping around851      LowerExt = Lower.zext(DstTySize);852    return ConstantRange(std::move(LowerExt),853                         APInt::getOneBitSet(DstTySize, SrcTySize));854  }855 856  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));857}858 859ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {860  if (isEmptySet()) return getEmpty(DstTySize);861 862  unsigned SrcTySize = getBitWidth();863  if (DstTySize == SrcTySize)864    return *this;865  assert(SrcTySize < DstTySize && "Not a value extension");866 867  // special case: [X, INT_MIN) -- not really wrapping around868  if (Upper.isMinSignedValue())869    return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));870 871  if (isFullSet() || isSignWrappedSet()) {872    return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),873                         APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);874  }875 876  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));877}878 879ConstantRange ConstantRange::truncate(uint32_t DstTySize,880                                      unsigned NoWrapKind) const {881  if (DstTySize == getBitWidth())882    return *this;883  assert(getBitWidth() > DstTySize && "Not a value truncation");884  if (isEmptySet())885    return getEmpty(DstTySize);886  if (isFullSet())887    return getFull(DstTySize);888 889  APInt LowerDiv(Lower), UpperDiv(Upper);890  ConstantRange Union(DstTySize, /*isFullSet=*/false);891 892  // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]893  // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and894  // then we do the union with [MaxValue, Upper)895  if (isUpperWrapped()) {896    // If Upper is greater than MaxValue(DstTy), it covers the whole truncated897    // range.898    if (Upper.getActiveBits() > DstTySize)899      return getFull(DstTySize);900 901    // For nuw the two parts are: [0, Upper) \/ [Lower, MaxValue(DstTy)]902    if (NoWrapKind & TruncInst::NoUnsignedWrap) {903      Union = ConstantRange(APInt::getZero(DstTySize), Upper.trunc(DstTySize));904      UpperDiv = APInt::getOneBitSet(getBitWidth(), DstTySize);905    } else {906      // If Upper is equal to MaxValue(DstTy), it covers the whole truncated907      // range.908      if (Upper.countr_one() == DstTySize)909        return getFull(DstTySize);910      Union =911          ConstantRange(APInt::getMaxValue(DstTySize), Upper.trunc(DstTySize));912      UpperDiv.setAllBits();913      // Union covers the MaxValue case, so return if the remaining range is914      // just MaxValue(DstTy).915      if (LowerDiv == UpperDiv)916        return Union;917    }918  }919 920  // Chop off the most significant bits that are past the destination bitwidth.921  if (LowerDiv.getActiveBits() > DstTySize) {922    // For trunc nuw if LowerDiv is greater than MaxValue(DstTy), the range is923    // outside the whole truncated range.924    if (NoWrapKind & TruncInst::NoUnsignedWrap)925      return Union;926    // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.927    APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);928    LowerDiv -= Adjust;929    UpperDiv -= Adjust;930  }931 932  unsigned UpperDivWidth = UpperDiv.getActiveBits();933  if (UpperDivWidth <= DstTySize)934    return ConstantRange(LowerDiv.trunc(DstTySize),935                         UpperDiv.trunc(DstTySize)).unionWith(Union);936 937  if (!LowerDiv.isZero() && NoWrapKind & TruncInst::NoUnsignedWrap)938    return ConstantRange(LowerDiv.trunc(DstTySize), APInt::getZero(DstTySize))939        .unionWith(Union);940 941  // The truncated value wraps around. Check if we can do better than fullset.942  if (UpperDivWidth == DstTySize + 1) {943    // Clear the MSB so that UpperDiv wraps around.944    UpperDiv.clearBit(DstTySize);945    if (UpperDiv.ult(LowerDiv))946      return ConstantRange(LowerDiv.trunc(DstTySize),947                           UpperDiv.trunc(DstTySize)).unionWith(Union);948  }949 950  return getFull(DstTySize);951}952 953ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {954  unsigned SrcTySize = getBitWidth();955  if (SrcTySize > DstTySize)956    return truncate(DstTySize);957  if (SrcTySize < DstTySize)958    return zeroExtend(DstTySize);959  return *this;960}961 962ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {963  unsigned SrcTySize = getBitWidth();964  if (SrcTySize > DstTySize)965    return truncate(DstTySize);966  if (SrcTySize < DstTySize)967    return signExtend(DstTySize);968  return *this;969}970 971ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,972                                      const ConstantRange &Other) const {973  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");974 975  switch (BinOp) {976  case Instruction::Add:977    return add(Other);978  case Instruction::Sub:979    return sub(Other);980  case Instruction::Mul:981    return multiply(Other);982  case Instruction::UDiv:983    return udiv(Other);984  case Instruction::SDiv:985    return sdiv(Other);986  case Instruction::URem:987    return urem(Other);988  case Instruction::SRem:989    return srem(Other);990  case Instruction::Shl:991    return shl(Other);992  case Instruction::LShr:993    return lshr(Other);994  case Instruction::AShr:995    return ashr(Other);996  case Instruction::And:997    return binaryAnd(Other);998  case Instruction::Or:999    return binaryOr(Other);1000  case Instruction::Xor:1001    return binaryXor(Other);1002  // Note: floating point operations applied to abstract ranges are just1003  // ideal integer operations with a lossy representation1004  case Instruction::FAdd:1005    return add(Other);1006  case Instruction::FSub:1007    return sub(Other);1008  case Instruction::FMul:1009    return multiply(Other);1010  default:1011    // Conservatively return getFull set.1012    return getFull();1013  }1014}1015 1016ConstantRange ConstantRange::overflowingBinaryOp(Instruction::BinaryOps BinOp,1017                                                 const ConstantRange &Other,1018                                                 unsigned NoWrapKind) const {1019  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");1020 1021  switch (BinOp) {1022  case Instruction::Add:1023    return addWithNoWrap(Other, NoWrapKind);1024  case Instruction::Sub:1025    return subWithNoWrap(Other, NoWrapKind);1026  case Instruction::Mul:1027    return multiplyWithNoWrap(Other, NoWrapKind);1028  case Instruction::Shl:1029    return shlWithNoWrap(Other, NoWrapKind);1030  default:1031    // Don't know about this Overflowing Binary Operation.1032    // Conservatively fallback to plain binop handling.1033    return binaryOp(BinOp, Other);1034  }1035}1036 1037bool ConstantRange::isIntrinsicSupported(Intrinsic::ID IntrinsicID) {1038  switch (IntrinsicID) {1039  case Intrinsic::uadd_sat:1040  case Intrinsic::usub_sat:1041  case Intrinsic::sadd_sat:1042  case Intrinsic::ssub_sat:1043  case Intrinsic::umin:1044  case Intrinsic::umax:1045  case Intrinsic::smin:1046  case Intrinsic::smax:1047  case Intrinsic::abs:1048  case Intrinsic::ctlz:1049  case Intrinsic::cttz:1050  case Intrinsic::ctpop:1051    return true;1052  default:1053    return false;1054  }1055}1056 1057ConstantRange ConstantRange::intrinsic(Intrinsic::ID IntrinsicID,1058                                       ArrayRef<ConstantRange> Ops) {1059  switch (IntrinsicID) {1060  case Intrinsic::uadd_sat:1061    return Ops[0].uadd_sat(Ops[1]);1062  case Intrinsic::usub_sat:1063    return Ops[0].usub_sat(Ops[1]);1064  case Intrinsic::sadd_sat:1065    return Ops[0].sadd_sat(Ops[1]);1066  case Intrinsic::ssub_sat:1067    return Ops[0].ssub_sat(Ops[1]);1068  case Intrinsic::umin:1069    return Ops[0].umin(Ops[1]);1070  case Intrinsic::umax:1071    return Ops[0].umax(Ops[1]);1072  case Intrinsic::smin:1073    return Ops[0].smin(Ops[1]);1074  case Intrinsic::smax:1075    return Ops[0].smax(Ops[1]);1076  case Intrinsic::abs: {1077    const APInt *IntMinIsPoison = Ops[1].getSingleElement();1078    assert(IntMinIsPoison && "Must be known (immarg)");1079    assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean");1080    return Ops[0].abs(IntMinIsPoison->getBoolValue());1081  }1082  case Intrinsic::ctlz: {1083    const APInt *ZeroIsPoison = Ops[1].getSingleElement();1084    assert(ZeroIsPoison && "Must be known (immarg)");1085    assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");1086    return Ops[0].ctlz(ZeroIsPoison->getBoolValue());1087  }1088  case Intrinsic::cttz: {1089    const APInt *ZeroIsPoison = Ops[1].getSingleElement();1090    assert(ZeroIsPoison && "Must be known (immarg)");1091    assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");1092    return Ops[0].cttz(ZeroIsPoison->getBoolValue());1093  }1094  case Intrinsic::ctpop:1095    return Ops[0].ctpop();1096  default:1097    assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported");1098    llvm_unreachable("Unsupported intrinsic");1099  }1100}1101 1102ConstantRange1103ConstantRange::add(const ConstantRange &Other) const {1104  if (isEmptySet() || Other.isEmptySet())1105    return getEmpty();1106  if (isFullSet() || Other.isFullSet())1107    return getFull();1108 1109  APInt NewLower = getLower() + Other.getLower();1110  APInt NewUpper = getUpper() + Other.getUpper() - 1;1111  if (NewLower == NewUpper)1112    return getFull();1113 1114  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));1115  if (X.isSizeStrictlySmallerThan(*this) ||1116      X.isSizeStrictlySmallerThan(Other))1117    // We've wrapped, therefore, full set.1118    return getFull();1119  return X;1120}1121 1122ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other,1123                                           unsigned NoWrapKind,1124                                           PreferredRangeType RangeType) const {1125  // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).1126  // (X is from this, and Y is from Other)1127  if (isEmptySet() || Other.isEmptySet())1128    return getEmpty();1129  if (isFullSet() && Other.isFullSet())1130    return getFull();1131 1132  using OBO = OverflowingBinaryOperator;1133  ConstantRange Result = add(Other);1134 1135  // If an overflow happens for every value pair in these two constant ranges,1136  // we must return Empty set. In this case, we get that for free, because we1137  // get lucky that intersection of add() with uadd_sat()/sadd_sat() results1138  // in an empty set.1139 1140  if (NoWrapKind & OBO::NoSignedWrap)1141    Result = Result.intersectWith(sadd_sat(Other), RangeType);1142 1143  if (NoWrapKind & OBO::NoUnsignedWrap)1144    Result = Result.intersectWith(uadd_sat(Other), RangeType);1145 1146  return Result;1147}1148 1149ConstantRange1150ConstantRange::sub(const ConstantRange &Other) const {1151  if (isEmptySet() || Other.isEmptySet())1152    return getEmpty();1153  if (isFullSet() || Other.isFullSet())1154    return getFull();1155 1156  APInt NewLower = getLower() - Other.getUpper() + 1;1157  APInt NewUpper = getUpper() - Other.getLower();1158  if (NewLower == NewUpper)1159    return getFull();1160 1161  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));1162  if (X.isSizeStrictlySmallerThan(*this) ||1163      X.isSizeStrictlySmallerThan(Other))1164    // We've wrapped, therefore, full set.1165    return getFull();1166  return X;1167}1168 1169ConstantRange ConstantRange::subWithNoWrap(const ConstantRange &Other,1170                                           unsigned NoWrapKind,1171                                           PreferredRangeType RangeType) const {1172  // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).1173  // (X is from this, and Y is from Other)1174  if (isEmptySet() || Other.isEmptySet())1175    return getEmpty();1176  if (isFullSet() && Other.isFullSet())1177    return getFull();1178 1179  using OBO = OverflowingBinaryOperator;1180  ConstantRange Result = sub(Other);1181 1182  // If an overflow happens for every value pair in these two constant ranges,1183  // we must return Empty set. In signed case, we get that for free, because we1184  // get lucky that intersection of sub() with ssub_sat() results in an1185  // empty set. But for unsigned we must perform the overflow check manually.1186 1187  if (NoWrapKind & OBO::NoSignedWrap)1188    Result = Result.intersectWith(ssub_sat(Other), RangeType);1189 1190  if (NoWrapKind & OBO::NoUnsignedWrap) {1191    if (getUnsignedMax().ult(Other.getUnsignedMin()))1192      return getEmpty(); // Always overflows.1193    Result = Result.intersectWith(usub_sat(Other), RangeType);1194  }1195 1196  return Result;1197}1198 1199ConstantRange1200ConstantRange::multiply(const ConstantRange &Other) const {1201  // TODO: If either operand is a single element and the multiply is known to1202  // be non-wrapping, round the result min and max value to the appropriate1203  // multiple of that element. If wrapping is possible, at least adjust the1204  // range according to the greatest power-of-two factor of the single element.1205 1206  if (isEmptySet() || Other.isEmptySet())1207    return getEmpty();1208 1209  if (const APInt *C = getSingleElement()) {1210    if (C->isOne())1211      return Other;1212    if (C->isAllOnes())1213      return ConstantRange(APInt::getZero(getBitWidth())).sub(Other);1214  }1215 1216  if (const APInt *C = Other.getSingleElement()) {1217    if (C->isOne())1218      return *this;1219    if (C->isAllOnes())1220      return ConstantRange(APInt::getZero(getBitWidth())).sub(*this);1221  }1222 1223  // Multiplication is signedness-independent. However different ranges can be1224  // obtained depending on how the input ranges are treated. These different1225  // ranges are all conservatively correct, but one might be better than the1226  // other. We calculate two ranges; one treating the inputs as unsigned1227  // and the other signed, then return the smallest of these ranges.1228 1229  // Unsigned range first.1230  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);1231  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);1232  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);1233  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);1234 1235  ConstantRange Result_zext = ConstantRange(this_min * Other_min,1236                                            this_max * Other_max + 1);1237  ConstantRange UR = Result_zext.truncate(getBitWidth());1238 1239  // If the unsigned range doesn't wrap, and isn't negative then it's a range1240  // from one positive number to another which is as good as we can generate.1241  // In this case, skip the extra work of generating signed ranges which aren't1242  // going to be better than this range.1243  if (!UR.isUpperWrapped() &&1244      (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))1245    return UR;1246 1247  // Now the signed range. Because we could be dealing with negative numbers1248  // here, the lower bound is the smallest of the cartesian product of the1249  // lower and upper ranges; for example:1250  //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.1251  // Similarly for the upper bound, swapping min for max.1252 1253  this_min = getSignedMin().sext(getBitWidth() * 2);1254  this_max = getSignedMax().sext(getBitWidth() * 2);1255  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);1256  Other_max = Other.getSignedMax().sext(getBitWidth() * 2);1257 1258  auto L = {this_min * Other_min, this_min * Other_max,1259            this_max * Other_min, this_max * Other_max};1260  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };1261  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);1262  ConstantRange SR = Result_sext.truncate(getBitWidth());1263 1264  return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;1265}1266 1267ConstantRange1268ConstantRange::multiplyWithNoWrap(const ConstantRange &Other,1269                                  unsigned NoWrapKind,1270                                  PreferredRangeType RangeType) const {1271  if (isEmptySet() || Other.isEmptySet())1272    return getEmpty();1273  if (isFullSet() && Other.isFullSet())1274    return getFull();1275 1276  ConstantRange Result = multiply(Other);1277 1278  if (NoWrapKind & OverflowingBinaryOperator::NoSignedWrap)1279    Result = Result.intersectWith(smul_sat(Other), RangeType);1280 1281  if (NoWrapKind & OverflowingBinaryOperator::NoUnsignedWrap)1282    Result = Result.intersectWith(umul_sat(Other), RangeType);1283 1284  // mul nsw nuw X, Y s>= 0 if X s> 1 or Y s> 11285  if ((NoWrapKind == (OverflowingBinaryOperator::NoSignedWrap |1286                      OverflowingBinaryOperator::NoUnsignedWrap)) &&1287      !Result.isAllNonNegative()) {1288    if (getSignedMin().sgt(1) || Other.getSignedMin().sgt(1))1289      Result = Result.intersectWith(1290          getNonEmpty(APInt::getZero(getBitWidth()),1291                      APInt::getSignedMinValue(getBitWidth())),1292          RangeType);1293  }1294 1295  return Result;1296}1297 1298ConstantRange ConstantRange::smul_fast(const ConstantRange &Other) const {1299  if (isEmptySet() || Other.isEmptySet())1300    return getEmpty();1301 1302  APInt Min = getSignedMin();1303  APInt Max = getSignedMax();1304  APInt OtherMin = Other.getSignedMin();1305  APInt OtherMax = Other.getSignedMax();1306 1307  bool O1, O2, O3, O4;1308  auto Muls = {Min.smul_ov(OtherMin, O1), Min.smul_ov(OtherMax, O2),1309               Max.smul_ov(OtherMin, O3), Max.smul_ov(OtherMax, O4)};1310  if (O1 || O2 || O3 || O4)1311    return getFull();1312 1313  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };1314  return getNonEmpty(std::min(Muls, Compare), std::max(Muls, Compare) + 1);1315}1316 1317ConstantRange1318ConstantRange::smax(const ConstantRange &Other) const {1319  // X smax Y is: range(smax(X_smin, Y_smin),1320  //                    smax(X_smax, Y_smax))1321  if (isEmptySet() || Other.isEmptySet())1322    return getEmpty();1323  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());1324  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;1325  ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));1326  if (isSignWrappedSet() || Other.isSignWrappedSet())1327    return Res.intersectWith(unionWith(Other, Signed), Signed);1328  return Res;1329}1330 1331ConstantRange1332ConstantRange::umax(const ConstantRange &Other) const {1333  // X umax Y is: range(umax(X_umin, Y_umin),1334  //                    umax(X_umax, Y_umax))1335  if (isEmptySet() || Other.isEmptySet())1336    return getEmpty();1337  APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());1338  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;1339  ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));1340  if (isWrappedSet() || Other.isWrappedSet())1341    return Res.intersectWith(unionWith(Other, Unsigned), Unsigned);1342  return Res;1343}1344 1345ConstantRange1346ConstantRange::smin(const ConstantRange &Other) const {1347  // X smin Y is: range(smin(X_smin, Y_smin),1348  //                    smin(X_smax, Y_smax))1349  if (isEmptySet() || Other.isEmptySet())1350    return getEmpty();1351  APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());1352  APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;1353  ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));1354  if (isSignWrappedSet() || Other.isSignWrappedSet())1355    return Res.intersectWith(unionWith(Other, Signed), Signed);1356  return Res;1357}1358 1359ConstantRange1360ConstantRange::umin(const ConstantRange &Other) const {1361  // X umin Y is: range(umin(X_umin, Y_umin),1362  //                    umin(X_umax, Y_umax))1363  if (isEmptySet() || Other.isEmptySet())1364    return getEmpty();1365  APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());1366  APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;1367  ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));1368  if (isWrappedSet() || Other.isWrappedSet())1369    return Res.intersectWith(unionWith(Other, Unsigned), Unsigned);1370  return Res;1371}1372 1373ConstantRange1374ConstantRange::udiv(const ConstantRange &RHS) const {1375  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())1376    return getEmpty();1377 1378  APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());1379 1380  APInt RHS_umin = RHS.getUnsignedMin();1381  if (RHS_umin.isZero()) {1382    // We want the lowest value in RHS excluding zero. Usually that would be 11383    // except for a range in the form of [X, 1) in which case it would be X.1384    if (RHS.getUpper() == 1)1385      RHS_umin = RHS.getLower();1386    else1387      RHS_umin = 1;1388  }1389 1390  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;1391  return getNonEmpty(std::move(Lower), std::move(Upper));1392}1393 1394ConstantRange ConstantRange::sdiv(const ConstantRange &RHS) const {1395  APInt Zero = APInt::getZero(getBitWidth());1396  APInt SignedMin = APInt::getSignedMinValue(getBitWidth());1397 1398  // We split up the LHS and RHS into positive and negative components1399  // and then also compute the positive and negative components of the result1400  // separately by combining division results with the appropriate signs.1401  auto [PosL, NegL] = splitPosNeg();1402  auto [PosR, NegR] = RHS.splitPosNeg();1403 1404  ConstantRange PosRes = getEmpty();1405  if (!PosL.isEmptySet() && !PosR.isEmptySet())1406    // pos / pos = pos.1407    PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),1408                           (PosL.Upper - 1).sdiv(PosR.Lower) + 1);1409 1410  if (!NegL.isEmptySet() && !NegR.isEmptySet()) {1411    // neg / neg = pos.1412    //1413    // We need to deal with one tricky case here: SignedMin / -1 is UB on the1414    // IR level, so we'll want to exclude this case when calculating bounds.1415    // (For APInts the operation is well-defined and yields SignedMin.) We1416    // handle this by dropping either SignedMin from the LHS or -1 from the RHS.1417    APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);1418    if (NegL.Lower.isMinSignedValue() && NegR.Upper.isZero()) {1419      // Remove -1 from the LHS. Skip if it's the only element, as this would1420      // leave us with an empty set.1421      if (!NegR.Lower.isAllOnes()) {1422        APInt AdjNegRUpper;1423        if (RHS.Lower.isAllOnes())1424          // Negative part of [-1, X] without -1 is [SignedMin, X].1425          AdjNegRUpper = RHS.Upper;1426        else1427          // [X, -1] without -1 is [X, -2].1428          AdjNegRUpper = NegR.Upper - 1;1429 1430        PosRes = PosRes.unionWith(1431            ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));1432      }1433 1434      // Remove SignedMin from the RHS. Skip if it's the only element, as this1435      // would leave us with an empty set.1436      if (NegL.Upper != SignedMin + 1) {1437        APInt AdjNegLLower;1438        if (Upper == SignedMin + 1)1439          // Negative part of [X, SignedMin] without SignedMin is [X, -1].1440          AdjNegLLower = Lower;1441        else1442          // [SignedMin, X] without SignedMin is [SignedMin + 1, X].1443          AdjNegLLower = NegL.Lower + 1;1444 1445        PosRes = PosRes.unionWith(1446            ConstantRange(std::move(Lo),1447                          AdjNegLLower.sdiv(NegR.Upper - 1) + 1));1448      }1449    } else {1450      PosRes = PosRes.unionWith(1451          ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));1452    }1453  }1454 1455  ConstantRange NegRes = getEmpty();1456  if (!PosL.isEmptySet() && !NegR.isEmptySet())1457    // pos / neg = neg.1458    NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),1459                           PosL.Lower.sdiv(NegR.Lower) + 1);1460 1461  if (!NegL.isEmptySet() && !PosR.isEmptySet())1462    // neg / pos = neg.1463    NegRes = NegRes.unionWith(1464        ConstantRange(NegL.Lower.sdiv(PosR.Lower),1465                      (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));1466 1467  // Prefer a non-wrapping signed range here.1468  ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed);1469 1470  // Preserve the zero that we dropped when splitting the LHS by sign.1471  if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))1472    Res = Res.unionWith(ConstantRange(Zero));1473  return Res;1474}1475 1476ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {1477  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())1478    return getEmpty();1479 1480  if (const APInt *RHSInt = RHS.getSingleElement()) {1481    // UREM by null is UB.1482    if (RHSInt->isZero())1483      return getEmpty();1484    // Use APInt's implementation of UREM for single element ranges.1485    if (const APInt *LHSInt = getSingleElement())1486      return {LHSInt->urem(*RHSInt)};1487  }1488 1489  // L % R for L < R is L.1490  if (getUnsignedMax().ult(RHS.getUnsignedMin()))1491    return *this;1492 1493  // L % R is <= L and < R.1494  APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;1495  return getNonEmpty(APInt::getZero(getBitWidth()), std::move(Upper));1496}1497 1498ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {1499  if (isEmptySet() || RHS.isEmptySet())1500    return getEmpty();1501 1502  if (const APInt *RHSInt = RHS.getSingleElement()) {1503    // SREM by null is UB.1504    if (RHSInt->isZero())1505      return getEmpty();1506    // Use APInt's implementation of SREM for single element ranges.1507    if (const APInt *LHSInt = getSingleElement())1508      return {LHSInt->srem(*RHSInt)};1509  }1510 1511  ConstantRange AbsRHS = RHS.abs();1512  APInt MinAbsRHS = AbsRHS.getUnsignedMin();1513  APInt MaxAbsRHS = AbsRHS.getUnsignedMax();1514 1515  // Modulus by zero is UB.1516  if (MaxAbsRHS.isZero())1517    return getEmpty();1518 1519  if (MinAbsRHS.isZero())1520    ++MinAbsRHS;1521 1522  APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();1523 1524  if (MinLHS.isNonNegative()) {1525    // L % R for L < R is L.1526    if (MaxLHS.ult(MinAbsRHS))1527      return *this;1528 1529    // L % R is <= L and < R.1530    APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;1531    return ConstantRange(APInt::getZero(getBitWidth()), std::move(Upper));1532  }1533 1534  // Same basic logic as above, but the result is negative.1535  if (MaxLHS.isNegative()) {1536    if (MinLHS.ugt(-MinAbsRHS))1537      return *this;1538 1539    APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);1540    return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));1541  }1542 1543  // LHS range crosses zero.1544  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);1545  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;1546  return ConstantRange(std::move(Lower), std::move(Upper));1547}1548 1549ConstantRange ConstantRange::binaryNot() const {1550  return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);1551}1552 1553/// Estimate the 'bit-masked AND' operation's lower bound.1554///1555/// E.g., given two ranges as follows (single quotes are separators and1556/// have no meaning here),1557///1558///   LHS = [10'00101'1,  ; LLo1559///          10'10000'0]  ; LHi1560///   RHS = [10'11111'0,  ; RLo1561///          10'11111'1]  ; RHi1562///1563/// we know that the higher 2 bits of the result is always 10; and we also1564/// notice that RHS[1:6] are always 1, so the result[1:6] cannot be less than1565/// LHS[1:6] (i.e., 00101). Thus, the lower bound is 10'00101'0.1566///1567/// The algorithm is as follows,1568/// 1. we first calculate a mask to find the higher common bits by1569///       Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo));1570///       Mask = clear all non-leading-ones bits in Mask;1571///    in the example, the Mask is set to 11'00000'0;1572/// 2. calculate a new mask by setting all common leading bits to 1 in RHS, and1573///    keeping the longest leading ones (i.e., 11'11111'0 in the example);1574/// 3. return (LLo & new mask) as the lower bound;1575/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower1576///    bound with the larger one.1577static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS,1578                                            const ConstantRange &RHS) {1579  auto BitWidth = LHS.getBitWidth();1580  // If either is full set or unsigned wrapped, then the range must contain '0'1581  // which leads the lower bound to 0.1582  if ((LHS.isFullSet() || RHS.isFullSet()) ||1583      (LHS.isWrappedSet() || RHS.isWrappedSet()))1584    return APInt::getZero(BitWidth);1585 1586  auto LLo = LHS.getLower();1587  auto LHi = LHS.getUpper() - 1;1588  auto RLo = RHS.getLower();1589  auto RHi = RHS.getUpper() - 1;1590 1591  // Calculate the mask for the higher common bits.1592  auto Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo));1593  unsigned LeadingOnes = Mask.countLeadingOnes();1594  Mask.clearLowBits(BitWidth - LeadingOnes);1595 1596  auto estimateBound = [BitWidth, &Mask](APInt ALo, const APInt &BLo,1597                                         const APInt &BHi) {1598    unsigned LeadingOnes = ((BLo & BHi) | Mask).countLeadingOnes();1599    unsigned StartBit = BitWidth - LeadingOnes;1600    ALo.clearLowBits(StartBit);1601    return ALo;1602  };1603 1604  auto LowerBoundByLHS = estimateBound(LLo, RLo, RHi);1605  auto LowerBoundByRHS = estimateBound(RLo, LLo, LHi);1606 1607  return APIntOps::umax(LowerBoundByLHS, LowerBoundByRHS);1608}1609 1610ConstantRange ConstantRange::binaryAnd(const ConstantRange &Other) const {1611  if (isEmptySet() || Other.isEmptySet())1612    return getEmpty();1613 1614  ConstantRange KnownBitsRange =1615      fromKnownBits(toKnownBits() & Other.toKnownBits(), false);1616  auto LowerBound = estimateBitMaskedAndLowerBound(*this, Other);1617  ConstantRange UMinUMaxRange = getNonEmpty(1618      LowerBound, APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()) + 1);1619  return KnownBitsRange.intersectWith(UMinUMaxRange);1620}1621 1622ConstantRange ConstantRange::binaryOr(const ConstantRange &Other) const {1623  if (isEmptySet() || Other.isEmptySet())1624    return getEmpty();1625 1626  ConstantRange KnownBitsRange =1627      fromKnownBits(toKnownBits() | Other.toKnownBits(), false);1628 1629  //      ~a & ~b    >= x1630  // <=>  ~(~a & ~b) <= ~x1631  // <=>  a | b      <= ~x1632  // <=>  a | b      <  ~x + 1 = -x1633  // thus, UpperBound(a | b) == -LowerBound(~a & ~b)1634  auto UpperBound =1635      -estimateBitMaskedAndLowerBound(binaryNot(), Other.binaryNot());1636  // Upper wrapped range.1637  ConstantRange UMaxUMinRange = getNonEmpty(1638      APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()), UpperBound);1639  return KnownBitsRange.intersectWith(UMaxUMinRange);1640}1641 1642ConstantRange ConstantRange::binaryXor(const ConstantRange &Other) const {1643  if (isEmptySet() || Other.isEmptySet())1644    return getEmpty();1645 1646  // Use APInt's implementation of XOR for single element ranges.1647  if (isSingleElement() && Other.isSingleElement())1648    return {*getSingleElement() ^ *Other.getSingleElement()};1649 1650  // Special-case binary complement, since we can give a precise answer.1651  if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes())1652    return binaryNot();1653  if (isSingleElement() && getSingleElement()->isAllOnes())1654    return Other.binaryNot();1655 1656  KnownBits LHSKnown = toKnownBits();1657  KnownBits RHSKnown = Other.toKnownBits();1658  KnownBits Known = LHSKnown ^ RHSKnown;1659  ConstantRange CR = fromKnownBits(Known, /*IsSigned*/ false);1660  // Typically the following code doesn't improve the result if BW = 1.1661  if (getBitWidth() == 1)1662    return CR;1663 1664  // If LHS is known to be the subset of RHS, treat LHS ^ RHS as RHS -nuw/nsw1665  // LHS. If RHS is known to be the subset of LHS, treat LHS ^ RHS as LHS1666  // -nuw/nsw RHS.1667  if ((~LHSKnown.Zero).isSubsetOf(RHSKnown.One))1668    CR = CR.intersectWith(Other.sub(*this), PreferredRangeType::Unsigned);1669  else if ((~RHSKnown.Zero).isSubsetOf(LHSKnown.One))1670    CR = CR.intersectWith(this->sub(Other), PreferredRangeType::Unsigned);1671  return CR;1672}1673 1674ConstantRange1675ConstantRange::shl(const ConstantRange &Other) const {1676  if (isEmptySet() || Other.isEmptySet())1677    return getEmpty();1678 1679  APInt Min = getUnsignedMin();1680  APInt Max = getUnsignedMax();1681  if (const APInt *RHS = Other.getSingleElement()) {1682    unsigned BW = getBitWidth();1683    if (RHS->uge(BW))1684      return getEmpty();1685 1686    unsigned EqualLeadingBits = (Min ^ Max).countl_zero();1687    if (RHS->ule(EqualLeadingBits))1688      return getNonEmpty(Min << *RHS, (Max << *RHS) + 1);1689 1690    return getNonEmpty(APInt::getZero(BW),1691                       APInt::getBitsSetFrom(BW, RHS->getZExtValue()) + 1);1692  }1693 1694  APInt OtherMax = Other.getUnsignedMax();1695  if (isAllNegative() && OtherMax.ule(Min.countl_one())) {1696    // For negative numbers, if the shift does not overflow in a signed sense,1697    // a larger shift will make the number smaller.1698    Max <<= Other.getUnsignedMin();1699    Min <<= OtherMax;1700    return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1);1701  }1702 1703  // There's overflow!1704  if (OtherMax.ugt(Max.countl_zero()))1705    return getFull();1706 1707  // FIXME: implement the other tricky cases1708 1709  Min <<= Other.getUnsignedMin();1710  Max <<= OtherMax;1711 1712  return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1);1713}1714 1715static ConstantRange computeShlNUW(const ConstantRange &LHS,1716                                   const ConstantRange &RHS) {1717  unsigned BitWidth = LHS.getBitWidth();1718  bool Overflow;1719  APInt LHSMin = LHS.getUnsignedMin();1720  unsigned RHSMin = RHS.getUnsignedMin().getLimitedValue(BitWidth);1721  APInt MinShl = LHSMin.ushl_ov(RHSMin, Overflow);1722  if (Overflow)1723    return ConstantRange::getEmpty(BitWidth);1724  APInt LHSMax = LHS.getUnsignedMax();1725  unsigned RHSMax = RHS.getUnsignedMax().getLimitedValue(BitWidth);1726  APInt MaxShl = MinShl;1727  unsigned MaxShAmt = LHSMax.countLeadingZeros();1728  if (RHSMin <= MaxShAmt)1729    MaxShl = LHSMax << std::min(RHSMax, MaxShAmt);1730  RHSMin = std::max(RHSMin, MaxShAmt + 1);1731  RHSMax = std::min(RHSMax, LHSMin.countLeadingZeros());1732  if (RHSMin <= RHSMax)1733    MaxShl = APIntOps::umax(MaxShl,1734                            APInt::getHighBitsSet(BitWidth, BitWidth - RHSMin));1735  return ConstantRange::getNonEmpty(MinShl, MaxShl + 1);1736}1737 1738static ConstantRange computeShlNSWWithNNegLHS(const APInt &LHSMin,1739                                              const APInt &LHSMax,1740                                              unsigned RHSMin,1741                                              unsigned RHSMax) {1742  unsigned BitWidth = LHSMin.getBitWidth();1743  bool Overflow;1744  APInt MinShl = LHSMin.sshl_ov(RHSMin, Overflow);1745  if (Overflow)1746    return ConstantRange::getEmpty(BitWidth);1747  APInt MaxShl = MinShl;1748  unsigned MaxShAmt = LHSMax.countLeadingZeros() - 1;1749  if (RHSMin <= MaxShAmt)1750    MaxShl = LHSMax << std::min(RHSMax, MaxShAmt);1751  RHSMin = std::max(RHSMin, MaxShAmt + 1);1752  RHSMax = std::min(RHSMax, LHSMin.countLeadingZeros() - 1);1753  if (RHSMin <= RHSMax)1754    MaxShl = APIntOps::umax(MaxShl,1755                            APInt::getBitsSet(BitWidth, RHSMin, BitWidth - 1));1756  return ConstantRange::getNonEmpty(MinShl, MaxShl + 1);1757}1758 1759static ConstantRange computeShlNSWWithNegLHS(const APInt &LHSMin,1760                                             const APInt &LHSMax,1761                                             unsigned RHSMin, unsigned RHSMax) {1762  unsigned BitWidth = LHSMin.getBitWidth();1763  bool Overflow;1764  APInt MaxShl = LHSMax.sshl_ov(RHSMin, Overflow);1765  if (Overflow)1766    return ConstantRange::getEmpty(BitWidth);1767  APInt MinShl = MaxShl;1768  unsigned MaxShAmt = LHSMin.countLeadingOnes() - 1;1769  if (RHSMin <= MaxShAmt)1770    MinShl = LHSMin.shl(std::min(RHSMax, MaxShAmt));1771  RHSMin = std::max(RHSMin, MaxShAmt + 1);1772  RHSMax = std::min(RHSMax, LHSMax.countLeadingOnes() - 1);1773  if (RHSMin <= RHSMax)1774    MinShl = APInt::getSignMask(BitWidth);1775  return ConstantRange::getNonEmpty(MinShl, MaxShl + 1);1776}1777 1778static ConstantRange computeShlNSW(const ConstantRange &LHS,1779                                   const ConstantRange &RHS) {1780  unsigned BitWidth = LHS.getBitWidth();1781  unsigned RHSMin = RHS.getUnsignedMin().getLimitedValue(BitWidth);1782  unsigned RHSMax = RHS.getUnsignedMax().getLimitedValue(BitWidth);1783  APInt LHSMin = LHS.getSignedMin();1784  APInt LHSMax = LHS.getSignedMax();1785  if (LHSMin.isNonNegative())1786    return computeShlNSWWithNNegLHS(LHSMin, LHSMax, RHSMin, RHSMax);1787  else if (LHSMax.isNegative())1788    return computeShlNSWWithNegLHS(LHSMin, LHSMax, RHSMin, RHSMax);1789  return computeShlNSWWithNNegLHS(APInt::getZero(BitWidth), LHSMax, RHSMin,1790                                  RHSMax)1791      .unionWith(computeShlNSWWithNegLHS(LHSMin, APInt::getAllOnes(BitWidth),1792                                         RHSMin, RHSMax),1793                 ConstantRange::Signed);1794}1795 1796ConstantRange ConstantRange::shlWithNoWrap(const ConstantRange &Other,1797                                           unsigned NoWrapKind,1798                                           PreferredRangeType RangeType) const {1799  if (isEmptySet() || Other.isEmptySet())1800    return getEmpty();1801 1802  switch (NoWrapKind) {1803  case 0:1804    return shl(Other);1805  case OverflowingBinaryOperator::NoSignedWrap:1806    return computeShlNSW(*this, Other);1807  case OverflowingBinaryOperator::NoUnsignedWrap:1808    return computeShlNUW(*this, Other);1809  case OverflowingBinaryOperator::NoSignedWrap |1810      OverflowingBinaryOperator::NoUnsignedWrap:1811    return computeShlNSW(*this, Other)1812        .intersectWith(computeShlNUW(*this, Other), RangeType);1813  default:1814    llvm_unreachable("Invalid NoWrapKind");1815  }1816}1817 1818ConstantRange1819ConstantRange::lshr(const ConstantRange &Other) const {1820  if (isEmptySet() || Other.isEmptySet())1821    return getEmpty();1822 1823  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;1824  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());1825  return getNonEmpty(std::move(min), std::move(max));1826}1827 1828ConstantRange1829ConstantRange::ashr(const ConstantRange &Other) const {1830  if (isEmptySet() || Other.isEmptySet())1831    return getEmpty();1832 1833  // May straddle zero, so handle both positive and negative cases.1834  // 'PosMax' is the upper bound of the result of the ashr1835  // operation, when Upper of the LHS of ashr is a non-negative.1836  // number. Since ashr of a non-negative number will result in a1837  // smaller number, the Upper value of LHS is shifted right with1838  // the minimum value of 'Other' instead of the maximum value.1839  APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;1840 1841  // 'PosMin' is the lower bound of the result of the ashr1842  // operation, when Lower of the LHS is a non-negative number.1843  // Since ashr of a non-negative number will result in a smaller1844  // number, the Lower value of LHS is shifted right with the1845  // maximum value of 'Other'.1846  APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());1847 1848  // 'NegMax' is the upper bound of the result of the ashr1849  // operation, when Upper of the LHS of ashr is a negative number.1850  // Since 'ashr' of a negative number will result in a bigger1851  // number, the Upper value of LHS is shifted right with the1852  // maximum value of 'Other'.1853  APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;1854 1855  // 'NegMin' is the lower bound of the result of the ashr1856  // operation, when Lower of the LHS of ashr is a negative number.1857  // Since 'ashr' of a negative number will result in a bigger1858  // number, the Lower value of LHS is shifted right with the1859  // minimum value of 'Other'.1860  APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());1861 1862  APInt max, min;1863  if (getSignedMin().isNonNegative()) {1864    // Upper and Lower of LHS are non-negative.1865    min = PosMin;1866    max = PosMax;1867  } else if (getSignedMax().isNegative()) {1868    // Upper and Lower of LHS are negative.1869    min = NegMin;1870    max = NegMax;1871  } else {1872    // Upper is non-negative and Lower is negative.1873    min = NegMin;1874    max = PosMax;1875  }1876  return getNonEmpty(std::move(min), std::move(max));1877}1878 1879ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const {1880  if (isEmptySet() || Other.isEmptySet())1881    return getEmpty();1882 1883  APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());1884  APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;1885  return getNonEmpty(std::move(NewL), std::move(NewU));1886}1887 1888ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const {1889  if (isEmptySet() || Other.isEmptySet())1890    return getEmpty();1891 1892  APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());1893  APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;1894  return getNonEmpty(std::move(NewL), std::move(NewU));1895}1896 1897ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const {1898  if (isEmptySet() || Other.isEmptySet())1899    return getEmpty();1900 1901  APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());1902  APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;1903  return getNonEmpty(std::move(NewL), std::move(NewU));1904}1905 1906ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const {1907  if (isEmptySet() || Other.isEmptySet())1908    return getEmpty();1909 1910  APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());1911  APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;1912  return getNonEmpty(std::move(NewL), std::move(NewU));1913}1914 1915ConstantRange ConstantRange::umul_sat(const ConstantRange &Other) const {1916  if (isEmptySet() || Other.isEmptySet())1917    return getEmpty();1918 1919  APInt NewL = getUnsignedMin().umul_sat(Other.getUnsignedMin());1920  APInt NewU = getUnsignedMax().umul_sat(Other.getUnsignedMax()) + 1;1921  return getNonEmpty(std::move(NewL), std::move(NewU));1922}1923 1924ConstantRange ConstantRange::smul_sat(const ConstantRange &Other) const {1925  if (isEmptySet() || Other.isEmptySet())1926    return getEmpty();1927 1928  // Because we could be dealing with negative numbers here, the lower bound is1929  // the smallest of the cartesian product of the lower and upper ranges;1930  // for example:1931  //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.1932  // Similarly for the upper bound, swapping min for max.1933 1934  APInt Min = getSignedMin();1935  APInt Max = getSignedMax();1936  APInt OtherMin = Other.getSignedMin();1937  APInt OtherMax = Other.getSignedMax();1938 1939  auto L = {Min.smul_sat(OtherMin), Min.smul_sat(OtherMax),1940            Max.smul_sat(OtherMin), Max.smul_sat(OtherMax)};1941  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };1942  return getNonEmpty(std::min(L, Compare), std::max(L, Compare) + 1);1943}1944 1945ConstantRange ConstantRange::ushl_sat(const ConstantRange &Other) const {1946  if (isEmptySet() || Other.isEmptySet())1947    return getEmpty();1948 1949  APInt NewL = getUnsignedMin().ushl_sat(Other.getUnsignedMin());1950  APInt NewU = getUnsignedMax().ushl_sat(Other.getUnsignedMax()) + 1;1951  return getNonEmpty(std::move(NewL), std::move(NewU));1952}1953 1954ConstantRange ConstantRange::sshl_sat(const ConstantRange &Other) const {1955  if (isEmptySet() || Other.isEmptySet())1956    return getEmpty();1957 1958  APInt Min = getSignedMin(), Max = getSignedMax();1959  APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax();1960  APInt NewL = Min.sshl_sat(Min.isNonNegative() ? ShAmtMin : ShAmtMax);1961  APInt NewU = Max.sshl_sat(Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;1962  return getNonEmpty(std::move(NewL), std::move(NewU));1963}1964 1965ConstantRange ConstantRange::inverse() const {1966  if (isFullSet())1967    return getEmpty();1968  if (isEmptySet())1969    return getFull();1970  return ConstantRange(Upper, Lower);1971}1972 1973ConstantRange ConstantRange::abs(bool IntMinIsPoison) const {1974  if (isEmptySet())1975    return getEmpty();1976 1977  if (isSignWrappedSet()) {1978    APInt Lo;1979    // Check whether the range crosses zero.1980    if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())1981      Lo = APInt::getZero(getBitWidth());1982    else1983      Lo = APIntOps::umin(Lower, -Upper + 1);1984 1985    // If SignedMin is not poison, then it is included in the result range.1986    if (IntMinIsPoison)1987      return ConstantRange(Lo, APInt::getSignedMinValue(getBitWidth()));1988    else1989      return ConstantRange(Lo, APInt::getSignedMinValue(getBitWidth()) + 1);1990  }1991 1992  APInt SMin = getSignedMin(), SMax = getSignedMax();1993 1994  // Skip SignedMin if it is poison.1995  if (IntMinIsPoison && SMin.isMinSignedValue()) {1996    // The range may become empty if it *only* contains SignedMin.1997    if (SMax.isMinSignedValue())1998      return getEmpty();1999    ++SMin;2000  }2001 2002  // All non-negative.2003  if (SMin.isNonNegative())2004    return ConstantRange(SMin, SMax + 1);2005 2006  // All negative.2007  if (SMax.isNegative())2008    return ConstantRange(-SMax, -SMin + 1);2009 2010  // Range crosses zero.2011  return ConstantRange::getNonEmpty(APInt::getZero(getBitWidth()),2012                                    APIntOps::umax(-SMin, SMax) + 1);2013}2014 2015ConstantRange ConstantRange::ctlz(bool ZeroIsPoison) const {2016  if (isEmptySet())2017    return getEmpty();2018 2019  APInt Zero = APInt::getZero(getBitWidth());2020  if (ZeroIsPoison && contains(Zero)) {2021    // ZeroIsPoison is set, and zero is contained. We discern three cases, in2022    // which a zero can appear:2023    // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.2024    // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.2025    // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.2026 2027    if (getLower().isZero()) {2028      if ((getUpper() - 1).isZero()) {2029        // We have in input interval of kind [0, 1). In this case we cannot2030        // really help but return empty-set.2031        return getEmpty();2032      }2033 2034      // Compute the resulting range by excluding zero from Lower.2035      return ConstantRange(2036          APInt(getBitWidth(), (getUpper() - 1).countl_zero()),2037          APInt(getBitWidth(), (getLower() + 1).countl_zero() + 1));2038    } else if ((getUpper() - 1).isZero()) {2039      // Compute the resulting range by excluding zero from Upper.2040      return ConstantRange(Zero,2041                           APInt(getBitWidth(), getLower().countl_zero() + 1));2042    } else {2043      return ConstantRange(Zero, APInt(getBitWidth(), getBitWidth()));2044    }2045  }2046 2047  // Zero is either safe or not in the range. The output range is composed by2048  // the result of countLeadingZero of the two extremes.2049  return getNonEmpty(APInt(getBitWidth(), getUnsignedMax().countl_zero()),2050                     APInt(getBitWidth(), getUnsignedMin().countl_zero()) + 1);2051}2052 2053static ConstantRange getUnsignedCountTrailingZerosRange(const APInt &Lower,2054                                                        const APInt &Upper) {2055  assert(!ConstantRange(Lower, Upper).isWrappedSet() &&2056         "Unexpected wrapped set.");2057  assert(Lower != Upper && "Unexpected empty set.");2058  unsigned BitWidth = Lower.getBitWidth();2059  if (Lower + 1 == Upper)2060    return ConstantRange(APInt(BitWidth, Lower.countr_zero()));2061  if (Lower.isZero())2062    return ConstantRange(APInt::getZero(BitWidth),2063                         APInt(BitWidth, BitWidth + 1));2064 2065  // Calculate longest common prefix.2066  unsigned LCPLength = (Lower ^ (Upper - 1)).countl_zero();2067  // If Lower is {LCP, 000...}, the maximum is Lower.countr_zero().2068  // Otherwise, the maximum is BitWidth - LCPLength - 1 ({LCP, 100...}).2069  return ConstantRange(2070      APInt::getZero(BitWidth),2071      APInt(BitWidth,2072            std::max(BitWidth - LCPLength - 1, Lower.countr_zero()) + 1));2073}2074 2075ConstantRange ConstantRange::cttz(bool ZeroIsPoison) const {2076  if (isEmptySet())2077    return getEmpty();2078 2079  unsigned BitWidth = getBitWidth();2080  APInt Zero = APInt::getZero(BitWidth);2081  if (ZeroIsPoison && contains(Zero)) {2082    // ZeroIsPoison is set, and zero is contained. We discern three cases, in2083    // which a zero can appear:2084    // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.2085    // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.2086    // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.2087 2088    if (Lower.isZero()) {2089      if (Upper == 1) {2090        // We have in input interval of kind [0, 1). In this case we cannot2091        // really help but return empty-set.2092        return getEmpty();2093      }2094 2095      // Compute the resulting range by excluding zero from Lower.2096      return getUnsignedCountTrailingZerosRange(APInt(BitWidth, 1), Upper);2097    } else if (Upper == 1) {2098      // Compute the resulting range by excluding zero from Upper.2099      return getUnsignedCountTrailingZerosRange(Lower, Zero);2100    } else {2101      ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Zero);2102      ConstantRange CR2 =2103          getUnsignedCountTrailingZerosRange(APInt(BitWidth, 1), Upper);2104      return CR1.unionWith(CR2);2105    }2106  }2107 2108  if (isFullSet())2109    return getNonEmpty(Zero, APInt(BitWidth, BitWidth) + 1);2110  if (!isWrappedSet())2111    return getUnsignedCountTrailingZerosRange(Lower, Upper);2112  // The range is wrapped. We decompose it into two ranges, [0, Upper) and2113  // [Lower, 0).2114  // Handle [Lower, 0)2115  ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Zero);2116  // Handle [0, Upper)2117  ConstantRange CR2 = getUnsignedCountTrailingZerosRange(Zero, Upper);2118  return CR1.unionWith(CR2);2119}2120 2121static ConstantRange getUnsignedPopCountRange(const APInt &Lower,2122                                              const APInt &Upper) {2123  assert(!ConstantRange(Lower, Upper).isWrappedSet() &&2124         "Unexpected wrapped set.");2125  assert(Lower != Upper && "Unexpected empty set.");2126  unsigned BitWidth = Lower.getBitWidth();2127  if (Lower + 1 == Upper)2128    return ConstantRange(APInt(BitWidth, Lower.popcount()));2129 2130  APInt Max = Upper - 1;2131  // Calculate longest common prefix.2132  unsigned LCPLength = (Lower ^ Max).countl_zero();2133  unsigned LCPPopCount = Lower.getHiBits(LCPLength).popcount();2134  // If Lower is {LCP, 000...}, the minimum is the popcount of LCP.2135  // Otherwise, the minimum is the popcount of LCP + 1.2136  unsigned MinBits =2137      LCPPopCount + (Lower.countr_zero() < BitWidth - LCPLength ? 1 : 0);2138  // If Max is {LCP, 111...}, the maximum is the popcount of LCP + (BitWidth -2139  // length of LCP).2140  // Otherwise, the minimum is the popcount of LCP + (BitWidth -2141  // length of LCP - 1).2142  unsigned MaxBits = LCPPopCount + (BitWidth - LCPLength) -2143                     (Max.countr_one() < BitWidth - LCPLength ? 1 : 0);2144  return ConstantRange(APInt(BitWidth, MinBits), APInt(BitWidth, MaxBits + 1));2145}2146 2147ConstantRange ConstantRange::ctpop() const {2148  if (isEmptySet())2149    return getEmpty();2150 2151  unsigned BitWidth = getBitWidth();2152  APInt Zero = APInt::getZero(BitWidth);2153  if (isFullSet())2154    return getNonEmpty(Zero, APInt(BitWidth, BitWidth) + 1);2155  if (!isWrappedSet())2156    return getUnsignedPopCountRange(Lower, Upper);2157  // The range is wrapped. We decompose it into two ranges, [0, Upper) and2158  // [Lower, 0).2159  // Handle [Lower, 0) == [Lower, Max]2160  ConstantRange CR1 = ConstantRange(APInt(BitWidth, Lower.countl_one()),2161                                    APInt(BitWidth, BitWidth + 1));2162  // Handle [0, Upper)2163  ConstantRange CR2 = getUnsignedPopCountRange(Zero, Upper);2164  return CR1.unionWith(CR2);2165}2166 2167ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow(2168    const ConstantRange &Other) const {2169  if (isEmptySet() || Other.isEmptySet())2170    return OverflowResult::MayOverflow;2171 2172  APInt Min = getUnsignedMin(), Max = getUnsignedMax();2173  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();2174 2175  // a u+ b overflows high iff a u> ~b.2176  if (Min.ugt(~OtherMin))2177    return OverflowResult::AlwaysOverflowsHigh;2178  if (Max.ugt(~OtherMax))2179    return OverflowResult::MayOverflow;2180  return OverflowResult::NeverOverflows;2181}2182 2183ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow(2184    const ConstantRange &Other) const {2185  if (isEmptySet() || Other.isEmptySet())2186    return OverflowResult::MayOverflow;2187 2188  APInt Min = getSignedMin(), Max = getSignedMax();2189  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();2190 2191  APInt SignedMin = APInt::getSignedMinValue(getBitWidth());2192  APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());2193 2194  // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.2195  // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.2196  if (Min.isNonNegative() && OtherMin.isNonNegative() &&2197      Min.sgt(SignedMax - OtherMin))2198    return OverflowResult::AlwaysOverflowsHigh;2199  if (Max.isNegative() && OtherMax.isNegative() &&2200      Max.slt(SignedMin - OtherMax))2201    return OverflowResult::AlwaysOverflowsLow;2202 2203  if (Max.isNonNegative() && OtherMax.isNonNegative() &&2204      Max.sgt(SignedMax - OtherMax))2205    return OverflowResult::MayOverflow;2206  if (Min.isNegative() && OtherMin.isNegative() &&2207      Min.slt(SignedMin - OtherMin))2208    return OverflowResult::MayOverflow;2209 2210  return OverflowResult::NeverOverflows;2211}2212 2213ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow(2214    const ConstantRange &Other) const {2215  if (isEmptySet() || Other.isEmptySet())2216    return OverflowResult::MayOverflow;2217 2218  APInt Min = getUnsignedMin(), Max = getUnsignedMax();2219  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();2220 2221  // a u- b overflows low iff a u< b.2222  if (Max.ult(OtherMin))2223    return OverflowResult::AlwaysOverflowsLow;2224  if (Min.ult(OtherMax))2225    return OverflowResult::MayOverflow;2226  return OverflowResult::NeverOverflows;2227}2228 2229ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow(2230    const ConstantRange &Other) const {2231  if (isEmptySet() || Other.isEmptySet())2232    return OverflowResult::MayOverflow;2233 2234  APInt Min = getSignedMin(), Max = getSignedMax();2235  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();2236 2237  APInt SignedMin = APInt::getSignedMinValue(getBitWidth());2238  APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());2239 2240  // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.2241  // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.2242  if (Min.isNonNegative() && OtherMax.isNegative() &&2243      Min.sgt(SignedMax + OtherMax))2244    return OverflowResult::AlwaysOverflowsHigh;2245  if (Max.isNegative() && OtherMin.isNonNegative() &&2246      Max.slt(SignedMin + OtherMin))2247    return OverflowResult::AlwaysOverflowsLow;2248 2249  if (Max.isNonNegative() && OtherMin.isNegative() &&2250      Max.sgt(SignedMax + OtherMin))2251    return OverflowResult::MayOverflow;2252  if (Min.isNegative() && OtherMax.isNonNegative() &&2253      Min.slt(SignedMin + OtherMax))2254    return OverflowResult::MayOverflow;2255 2256  return OverflowResult::NeverOverflows;2257}2258 2259ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow(2260    const ConstantRange &Other) const {2261  if (isEmptySet() || Other.isEmptySet())2262    return OverflowResult::MayOverflow;2263 2264  APInt Min = getUnsignedMin(), Max = getUnsignedMax();2265  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();2266  bool Overflow;2267 2268  (void) Min.umul_ov(OtherMin, Overflow);2269  if (Overflow)2270    return OverflowResult::AlwaysOverflowsHigh;2271 2272  (void) Max.umul_ov(OtherMax, Overflow);2273  if (Overflow)2274    return OverflowResult::MayOverflow;2275 2276  return OverflowResult::NeverOverflows;2277}2278 2279void ConstantRange::print(raw_ostream &OS) const {2280  if (isFullSet())2281    OS << "full-set";2282  else if (isEmptySet())2283    OS << "empty-set";2284  else2285    OS << "[" << Lower << "," << Upper << ")";2286}2287 2288#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2289LLVM_DUMP_METHOD void ConstantRange::dump() const {2290  print(dbgs());2291}2292#endif2293 2294ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {2295  const unsigned NumRanges = Ranges.getNumOperands() / 2;2296  assert(NumRanges >= 1 && "Must have at least one range!");2297  assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");2298 2299  auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));2300  auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));2301 2302  ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());2303 2304  for (unsigned i = 1; i < NumRanges; ++i) {2305    auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));2306    auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));2307 2308    // Note: unionWith will potentially create a range that contains values not2309    // contained in any of the original N ranges.2310    CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));2311  }2312 2313  return CR;2314}2315