contrib/llvm/lib/IR/ConstantRange.cpp

   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 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
  42     : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
  43       Upper(Lower) {}
  44
  45 ConstantRange::ConstantRange(APInt V)
  46     : Lower(std::move(V)), Upper(Lower + 1) {}
  47
  48 ConstantRange::ConstantRange(APInt L, APInt U)
  49     : Lower(std::move(L)), Upper(std::move(U)) {
  50   assert(Lower.getBitWidth() == Upper.getBitWidth() &&
  51          "ConstantRange with unequal bit widths");
  52   assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
  53          "Lower == Upper, but they aren't min or max value!");
  54 }
  55
  56 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
  57                                                    const ConstantRange &CR) {
  58   if (CR.isEmptySet())
  59     return CR;
  60
  61   uint32_t W = CR.getBitWidth();
  62   switch (Pred) {
  63   default:
  64     llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
  65   case CmpInst::ICMP_EQ:
  66     return CR;
  67   case CmpInst::ICMP_NE:
  68     if (CR.isSingleElement())
  69       return ConstantRange(CR.getUpper(), CR.getLower());
  70     return ConstantRange(W);
  71   case CmpInst::ICMP_ULT: {
  72     APInt UMax(CR.getUnsignedMax());
  73     if (UMax.isMinValue())
  74       return ConstantRange(W, /* empty */ false);
  75     return ConstantRange(APInt::getMinValue(W), std::move(UMax));
  76   }
  77   case CmpInst::ICMP_SLT: {
  78     APInt SMax(CR.getSignedMax());
  79     if (SMax.isMinSignedValue())
  80       return ConstantRange(W, /* empty */ false);
  81     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
  82   }
  83   case CmpInst::ICMP_ULE: {
  84     APInt UMax(CR.getUnsignedMax());
  85     if (UMax.isMaxValue())
  86       return ConstantRange(W);
  87     return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
  88   }
  89   case CmpInst::ICMP_SLE: {
  90     APInt SMax(CR.getSignedMax());
  91     if (SMax.isMaxSignedValue())
  92       return ConstantRange(W);
  93     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
  94   }
  95   case CmpInst::ICMP_UGT: {
  96     APInt UMin(CR.getUnsignedMin());
  97     if (UMin.isMaxValue())
  98       return ConstantRange(W, /* empty */ false);
  99     return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
 100   }
 101   case CmpInst::ICMP_SGT: {
 102     APInt SMin(CR.getSignedMin());
 103     if (SMin.isMaxSignedValue())
 104       return ConstantRange(W, /* empty */ false);
 105     return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
 106   }
 107   case CmpInst::ICMP_UGE: {
 108     APInt UMin(CR.getUnsignedMin());
 109     if (UMin.isMinValue())
 110       return ConstantRange(W);
 111     return ConstantRange(std::move(UMin), APInt::getNullValue(W));
 112   }
 113   case CmpInst::ICMP_SGE: {
 114     APInt SMin(CR.getSignedMin());
 115     if (SMin.isMinSignedValue())
 116       return ConstantRange(W);
 117     return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
 118   }
 119   }
 120 }
 121
 122 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   return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
 129       .inverse();
 130 }
 131
 132 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   return makeAllowedICmpRegion(Pred, C);
 142 }
 143
 144 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
 145                                       APInt &RHS) const {
 146   bool Success = false;
 147
 148   if (isFullSet() || isEmptySet()) {
 149     Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
 150     RHS = APInt(getBitWidth(), 0);
 151     Success = true;
 152   } else if (auto *OnlyElt = getSingleElement()) {
 153     Pred = CmpInst::ICMP_EQ;
 154     RHS = *OnlyElt;
 155     Success = true;
 156   } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
 157     Pred = CmpInst::ICMP_NE;
 158     RHS = *OnlyMissingElt;
 159     Success = true;
 160   } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
 161     Pred =
 162         getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
 163     RHS = getUpper();
 164     Success = true;
 165   } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
 166     Pred =
 167         getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
 168     RHS = getLower();
 169     Success = true;
 170   }
 171
 172   assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
 173          "Bad result!");
 174
 175   return Success;
 176 }
 177
 178 ConstantRange
 179 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       [](const ConstantRange &CR0, const ConstantRange &CR1) {
 190     return CR0.inverse().unionWith(CR1.inverse()).inverse();
 191   };
 192
 193   assert(BinOp >= Instruction::BinaryOpsBegin &&
 194          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
 195
 196   assert((NoWrapKind == OBO::NoSignedWrap ||
 197           NoWrapKind == OBO::NoUnsignedWrap ||
 198           NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
 199          "NoWrapKind invalid!");
 200
 201   unsigned BitWidth = Other.getBitWidth();
 202   if (BinOp != Instruction::Add)
 203     // Conservative answer: empty set
 204     return ConstantRange(BitWidth, false);
 205
 206   if (auto *C = Other.getSingleElement())
 207     if (C->isNullValue())
 208       // Full set: nothing signed / unsigned wraps when added to 0.
 209       return ConstantRange(BitWidth);
 210
 211   ConstantRange Result(BitWidth);
 212
 213   if (NoWrapKind & OBO::NoUnsignedWrap)
 214     Result =
 215         SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
 216                                               -Other.getUnsignedMax()));
 217
 218   if (NoWrapKind & OBO::NoSignedWrap) {
 219     const APInt &SignedMin = Other.getSignedMin();
 220     const APInt &SignedMax = Other.getSignedMax();
 221
 222     if (SignedMax.isStrictlyPositive())
 223       Result = SubsetIntersect(
 224           Result,
 225           ConstantRange(APInt::getSignedMinValue(BitWidth),
 226                         APInt::getSignedMinValue(BitWidth) - SignedMax));
 227
 228     if (SignedMin.isNegative())
 229       Result = SubsetIntersect(
 230           Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
 231                                 APInt::getSignedMinValue(BitWidth)));
 232   }
 233
 234   return Result;
 235 }
 236
 237 bool ConstantRange::isFullSet() const {
 238   return Lower == Upper && Lower.isMaxValue();
 239 }
 240
 241 bool ConstantRange::isEmptySet() const {
 242   return Lower == Upper && Lower.isMinValue();
 243 }
 244
 245 bool ConstantRange::isWrappedSet() const {
 246   return Lower.ugt(Upper);
 247 }
 248
 249 bool ConstantRange::isSignWrappedSet() const {
 250   return contains(APInt::getSignedMaxValue(getBitWidth())) &&
 251          contains(APInt::getSignedMinValue(getBitWidth()));
 252 }
 253
 254 APInt ConstantRange::getSetSize() const {
 255   if (isFullSet())
 256     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
 257
 258   // This is also correct for wrapped sets.
 259   return (Upper - Lower).zext(getBitWidth()+1);
 260 }
 261
 262 bool
 263 ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
 264   assert(getBitWidth() == Other.getBitWidth());
 265   if (isFullSet())
 266     return false;
 267   if (Other.isFullSet())
 268     return true;
 269   return (Upper - Lower).ult(Other.Upper - Other.Lower);
 270 }
 271
 272 bool
 273 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   if (isFullSet())
 278     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
 279
 280   return (Upper - Lower).ugt(MaxSize);
 281 }
 282
 283 APInt ConstantRange::getUnsignedMax() const {
 284   if (isFullSet() || isWrappedSet())
 285     return APInt::getMaxValue(getBitWidth());
 286   return getUpper() - 1;
 287 }
 288
 289 APInt ConstantRange::getUnsignedMin() const {
 290   if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
 291     return APInt::getMinValue(getBitWidth());
 292   return getLower();
 293 }
 294
 295 APInt ConstantRange::getSignedMax() const {
 296   if (isFullSet() || Lower.sgt(Upper))
 297     return APInt::getSignedMaxValue(getBitWidth());
 298   return getUpper() - 1;
 299 }
 300
 301 APInt ConstantRange::getSignedMin() const {
 302   if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
 303     return APInt::getSignedMinValue(getBitWidth());
 304   return getLower();
 305 }
 306
 307 bool ConstantRange::contains(const APInt &V) const {
 308   if (Lower == Upper)
 309     return isFullSet();
 310
 311   if (!isWrappedSet())
 312     return Lower.ule(V) && V.ult(Upper);
 313   return Lower.ule(V) || V.ult(Upper);
 314 }
 315
 316 bool ConstantRange::contains(const ConstantRange &Other) const {
 317   if (isFullSet() || Other.isEmptySet()) return true;
 318   if (isEmptySet() || Other.isFullSet()) return false;
 319
 320   if (!isWrappedSet()) {
 321     if (Other.isWrappedSet())
 322       return false;
 323
 324     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
 325   }
 326
 327   if (!Other.isWrappedSet())
 328     return Other.getUpper().ule(Upper) ||
 329            Lower.ule(Other.getLower());
 330
 331   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
 332 }
 333
 334 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   if (Lower == Upper)
 338     return *this;
 339   return ConstantRange(Lower - Val, Upper - Val);
 340 }
 341
 342 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
 343   return intersectWith(CR.inverse());
 344 }
 345
 346 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
 347   assert(getBitWidth() == CR.getBitWidth() &&
 348          "ConstantRange types don't agree!");
 349
 350   // Handle common cases.
 351   if (   isEmptySet() || CR.isFullSet()) return *this;
 352   if (CR.isEmptySet() ||    isFullSet()) return CR;
 353
 354   if (!isWrappedSet() && CR.isWrappedSet())
 355     return CR.intersectWith(*this);
 356
 357   if (!isWrappedSet() && !CR.isWrappedSet()) {
 358     if (Lower.ult(CR.Lower)) {
 359       if (Upper.ule(CR.Lower))
 360         return ConstantRange(getBitWidth(), false);
 361
 362       if (Upper.ult(CR.Upper))
 363         return ConstantRange(CR.Lower, Upper);
 364
 365       return CR;
 366     }
 367     if (Upper.ult(CR.Upper))
 368       return *this;
 369
 370     if (Lower.ult(CR.Upper))
 371       return ConstantRange(Lower, CR.Upper);
 372
 373     return ConstantRange(getBitWidth(), false);
 374   }
 375
 376   if (isWrappedSet() && !CR.isWrappedSet()) {
 377     if (CR.Lower.ult(Upper)) {
 378       if (CR.Upper.ult(Upper))
 379         return CR;
 380
 381       if (CR.Upper.ule(Lower))
 382         return ConstantRange(CR.Lower, Upper);
 383
 384       if (isSizeStrictlySmallerThan(CR))
 385         return *this;
 386       return CR;
 387     }
 388     if (CR.Lower.ult(Lower)) {
 389       if (CR.Upper.ule(Lower))
 390         return ConstantRange(getBitWidth(), false);
 391
 392       return ConstantRange(Lower, CR.Upper);
 393     }
 394     return CR;
 395   }
 396
 397   if (CR.Upper.ult(Upper)) {
 398     if (CR.Lower.ult(Upper)) {
 399       if (isSizeStrictlySmallerThan(CR))
 400         return *this;
 401       return CR;
 402     }
 403
 404     if (CR.Lower.ult(Lower))
 405       return ConstantRange(Lower, CR.Upper);
 406
 407     return CR;
 408   }
 409   if (CR.Upper.ule(Lower)) {
 410     if (CR.Lower.ult(Lower))
 411       return *this;
 412
 413     return ConstantRange(CR.Lower, Upper);
 414   }
 415   if (isSizeStrictlySmallerThan(CR))
 416     return *this;
 417   return CR;
 418 }
 419
 420 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 421   assert(getBitWidth() == CR.getBitWidth() &&
 422          "ConstantRange types don't agree!");
 423
 424   if (   isFullSet() || CR.isEmptySet()) return *this;
 425   if (CR.isFullSet() ||    isEmptySet()) return CR;
 426
 427   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
 428
 429   if (!isWrappedSet() && !CR.isWrappedSet()) {
 430     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
 431       // If the two ranges are disjoint, find the smaller gap and bridge it.
 432       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
 433       if (d1.ult(d2))
 434         return ConstantRange(Lower, CR.Upper);
 435       return ConstantRange(CR.Lower, Upper);
 436     }
 437
 438     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
 439     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
 440
 441     if (L.isNullValue() && U.isNullValue())
 442       return ConstantRange(getBitWidth());
 443
 444     return ConstantRange(std::move(L), std::move(U));
 445   }
 446
 447   if (!CR.isWrappedSet()) {
 448     // ------U   L-----  and  ------U   L----- : this
 449     //   L--U                            L--U  : CR
 450     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
 451       return *this;
 452
 453     // ------U   L----- : this
 454     //    L---------U   : CR
 455     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
 456       return ConstantRange(getBitWidth());
 457
 458     // ----U       L---- : this
 459     //       L---U       : CR
 460     //    <d1>  <d2>
 461     if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
 462       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
 463       if (d1.ult(d2))
 464         return ConstantRange(Lower, CR.Upper);
 465       return ConstantRange(CR.Lower, Upper);
 466     }
 467
 468     // ----U     L----- : this
 469     //        L----U    : CR
 470     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
 471       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     return ConstantRange(Lower, CR.Upper);
 478   }
 479
 480   // ------U    L----  and  ------U    L---- : this
 481   // -U  L-----------  and  ------------U  L : CR
 482   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
 483     return ConstantRange(getBitWidth());
 484
 485   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
 486   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
 487
 488   return ConstantRange(std::move(L), std::move(U));
 489 }
 490
 491 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
 492                                     uint32_t ResultBitWidth) const {
 493   switch (CastOp) {
 494   default:
 495     llvm_unreachable("unsupported cast type");
 496   case Instruction::Trunc:
 497     return truncate(ResultBitWidth);
 498   case Instruction::SExt:
 499     return signExtend(ResultBitWidth);
 500   case Instruction::ZExt:
 501     return zeroExtend(ResultBitWidth);
 502   case Instruction::BitCast:
 503     return *this;
 504   case Instruction::FPToUI:
 505   case Instruction::FPToSI:
 506     if (getBitWidth() == ResultBitWidth)
 507       return *this;
 508     else
 509       return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 510   case Instruction::UIToFP: {
 511     // TODO: use input range if available
 512     auto BW = getBitWidth();
 513     APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
 514     APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
 515     return ConstantRange(std::move(Min), std::move(Max));
 516   }
 517   case Instruction::SIToFP: {
 518     // TODO: use input range if available
 519     auto BW = getBitWidth();
 520     APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
 521     APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
 522     return ConstantRange(std::move(SMin), std::move(SMax));
 523   }
 524   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     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 531   };
 532 }
 533
 534 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
 535   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
 536
 537   unsigned SrcTySize = getBitWidth();
 538   assert(SrcTySize < DstTySize && "Not a value extension");
 539   if (isFullSet() || isWrappedSet()) {
 540     // Change into [0, 1 << src bit width)
 541     APInt LowerExt(DstTySize, 0);
 542     if (!Upper) // special case: [X, 0) -- not really wrapping around
 543       LowerExt = Lower.zext(DstTySize);
 544     return ConstantRange(std::move(LowerExt),
 545                          APInt::getOneBitSet(DstTySize, SrcTySize));
 546   }
 547
 548   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
 549 }
 550
 551 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
 552   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
 553
 554   unsigned SrcTySize = getBitWidth();
 555   assert(SrcTySize < DstTySize && "Not a value extension");
 556
 557   // special case: [X, INT_MIN) -- not really wrapping around
 558   if (Upper.isMinSignedValue())
 559     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
 560
 561   if (isFullSet() || isSignWrappedSet()) {
 562     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
 563                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
 564   }
 565
 566   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
 567 }
 568
 569 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
 570   assert(getBitWidth() > DstTySize && "Not a value truncation");
 571   if (isEmptySet())
 572     return ConstantRange(DstTySize, /*isFullSet=*/false);
 573   if (isFullSet())
 574     return ConstantRange(DstTySize, /*isFullSet=*/true);
 575
 576   APInt LowerDiv(Lower), UpperDiv(Upper);
 577   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   if (isWrappedSet()) {
 583     // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
 584     // truncated range.
 585     if (Upper.getActiveBits() > DstTySize ||
 586         Upper.countTrailingOnes() == DstTySize)
 587       return ConstantRange(DstTySize, /*isFullSet=*/true);
 588
 589     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
 590     UpperDiv.setAllBits();
 591
 592     // Union covers the MaxValue case, so return if the remaining range is just
 593     // MaxValue(DstTy).
 594     if (LowerDiv == UpperDiv)
 595       return Union;
 596   }
 597
 598   // Chop off the most significant bits that are past the destination bitwidth.
 599   if (LowerDiv.getActiveBits() > DstTySize) {
 600     // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
 601     APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
 602     LowerDiv -= Adjust;
 603     UpperDiv -= Adjust;
 604   }
 605
 606   unsigned UpperDivWidth = UpperDiv.getActiveBits();
 607   if (UpperDivWidth <= DstTySize)
 608     return ConstantRange(LowerDiv.trunc(DstTySize),
 609                          UpperDiv.trunc(DstTySize)).unionWith(Union);
 610
 611   // The truncated value wraps around. Check if we can do better than fullset.
 612   if (UpperDivWidth == DstTySize + 1) {
 613     // Clear the MSB so that UpperDiv wraps around.
 614     UpperDiv.clearBit(DstTySize);
 615     if (UpperDiv.ult(LowerDiv))
 616       return ConstantRange(LowerDiv.trunc(DstTySize),
 617                            UpperDiv.trunc(DstTySize)).unionWith(Union);
 618   }
 619
 620   return ConstantRange(DstTySize, /*isFullSet=*/true);
 621 }
 622
 623 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
 624   unsigned SrcTySize = getBitWidth();
 625   if (SrcTySize > DstTySize)
 626     return truncate(DstTySize);
 627   if (SrcTySize < DstTySize)
 628     return zeroExtend(DstTySize);
 629   return *this;
 630 }
 631
 632 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
 633   unsigned SrcTySize = getBitWidth();
 634   if (SrcTySize > DstTySize)
 635     return truncate(DstTySize);
 636   if (SrcTySize < DstTySize)
 637     return signExtend(DstTySize);
 638   return *this;
 639 }
 640
 641 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   switch (BinOp) {
 647   case Instruction::Add:
 648     return add(Other);
 649   case Instruction::Sub:
 650     return sub(Other);
 651   case Instruction::Mul:
 652     return multiply(Other);
 653   case Instruction::UDiv:
 654     return udiv(Other);
 655   case Instruction::Shl:
 656     return shl(Other);
 657   case Instruction::LShr:
 658     return lshr(Other);
 659   case Instruction::And:
 660     return binaryAnd(Other);
 661   case Instruction::Or:
 662     return binaryOr(Other);
 663   // Note: floating point operations applied to abstract ranges are just
 664   // ideal integer operations with a lossy representation
 665   case Instruction::FAdd:
 666     return add(Other);
 667   case Instruction::FSub:
 668     return sub(Other);
 669   case Instruction::FMul:
 670     return multiply(Other);
 671   default:
 672     // Conservatively return full set.
 673     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 674   }
 675 }
 676
 677 ConstantRange
 678 ConstantRange::add(const ConstantRange &Other) const {
 679   if (isEmptySet() || Other.isEmptySet())
 680     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 681   if (isFullSet() || Other.isFullSet())
 682     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 683
 684   APInt NewLower = getLower() + Other.getLower();
 685   APInt NewUpper = getUpper() + Other.getUpper() - 1;
 686   if (NewLower == NewUpper)
 687     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 688
 689   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
 690   if (X.isSizeStrictlySmallerThan(*this) ||
 691       X.isSizeStrictlySmallerThan(Other))
 692     // We've wrapped, therefore, full set.
 693     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 694   return X;
 695 }
 696
 697 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                                       ConstantRange(Other),
 704                                       OverflowingBinaryOperator::NoSignedWrap);
 705   auto NSWConstrainedRange = intersectWith(NSWRange);
 706
 707   return NSWConstrainedRange.add(ConstantRange(Other));
 708 }
 709
 710 ConstantRange
 711 ConstantRange::sub(const ConstantRange &Other) const {
 712   if (isEmptySet() || Other.isEmptySet())
 713     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 714   if (isFullSet() || Other.isFullSet())
 715     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 716
 717   APInt NewLower = getLower() - Other.getUpper() + 1;
 718   APInt NewUpper = getUpper() - Other.getLower();
 719   if (NewLower == NewUpper)
 720     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 721
 722   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
 723   if (X.isSizeStrictlySmallerThan(*this) ||
 724       X.isSizeStrictlySmallerThan(Other))
 725     // We've wrapped, therefore, full set.
 726     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 727   return X;
 728 }
 729
 730 ConstantRange
 731 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   if (isEmptySet() || Other.isEmptySet())
 738     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   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
 748   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
 749   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
 750   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
 751
 752   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
 753                                             this_max * Other_max + 1);
 754   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   if (!UR.isWrappedSet() &&
 761       (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   this_min = getSignedMin().sext(getBitWidth() * 2);
 771   this_max = getSignedMax().sext(getBitWidth() * 2);
 772   Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
 773   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
 774
 775   auto L = {this_min * Other_min, this_min * Other_max,
 776             this_max * Other_min, this_max * Other_max};
 777   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
 778   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
 779   ConstantRange SR = Result_sext.truncate(getBitWidth());
 780
 781   return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
 782 }
 783
 784 ConstantRange
 785 ConstantRange::smax(const ConstantRange &Other) const {
 786   // X smax Y is: range(smax(X_smin, Y_smin),
 787   //                    smax(X_smax, Y_smax))
 788   if (isEmptySet() || Other.isEmptySet())
 789     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 790   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
 791   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
 792   if (NewU == NewL)
 793     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 794   return ConstantRange(std::move(NewL), std::move(NewU));
 795 }
 796
 797 ConstantRange
 798 ConstantRange::umax(const ConstantRange &Other) const {
 799   // X umax Y is: range(umax(X_umin, Y_umin),
 800   //                    umax(X_umax, Y_umax))
 801   if (isEmptySet() || Other.isEmptySet())
 802     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 803   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
 804   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
 805   if (NewU == NewL)
 806     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 807   return ConstantRange(std::move(NewL), std::move(NewU));
 808 }
 809
 810 ConstantRange
 811 ConstantRange::smin(const ConstantRange &Other) const {
 812   // X smin Y is: range(smin(X_smin, Y_smin),
 813   //                    smin(X_smax, Y_smax))
 814   if (isEmptySet() || Other.isEmptySet())
 815     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 816   APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
 817   APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
 818   if (NewU == NewL)
 819     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 820   return ConstantRange(std::move(NewL), std::move(NewU));
 821 }
 822
 823 ConstantRange
 824 ConstantRange::umin(const ConstantRange &Other) const {
 825   // X umin Y is: range(umin(X_umin, Y_umin),
 826   //                    umin(X_umax, Y_umax))
 827   if (isEmptySet() || Other.isEmptySet())
 828     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 829   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
 830   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
 831   if (NewU == NewL)
 832     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 833   return ConstantRange(std::move(NewL), std::move(NewU));
 834 }
 835
 836 ConstantRange
 837 ConstantRange::udiv(const ConstantRange &RHS) const {
 838   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
 839     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 840   if (RHS.isFullSet())
 841     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 842
 843   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
 844
 845   APInt RHS_umin = RHS.getUnsignedMin();
 846   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     if (RHS.getUpper() == 1)
 850       RHS_umin = RHS.getLower();
 851     else
 852       RHS_umin = 1;
 853   }
 854
 855   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   if (Lower == Upper)
 860     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 861
 862   return ConstantRange(std::move(Lower), std::move(Upper));
 863 }
 864
 865 ConstantRange
 866 ConstantRange::binaryAnd(const ConstantRange &Other) const {
 867   if (isEmptySet() || Other.isEmptySet())
 868     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 869
 870   // TODO: replace this with something less conservative
 871
 872   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
 873   if (umin.isAllOnesValue())
 874     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 875   return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
 876 }
 877
 878 ConstantRange
 879 ConstantRange::binaryOr(const ConstantRange &Other) const {
 880   if (isEmptySet() || Other.isEmptySet())
 881     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 882
 883   // TODO: replace this with something less conservative
 884
 885   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
 886   if (umax.isNullValue())
 887     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 888   return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
 889 }
 890
 891 ConstantRange
 892 ConstantRange::shl(const ConstantRange &Other) const {
 893   if (isEmptySet() || Other.isEmptySet())
 894     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 895
 896   APInt max = getUnsignedMax();
 897   APInt Other_umax = Other.getUnsignedMax();
 898
 899   // there's overflow!
 900   if (Other_umax.uge(max.countLeadingZeros()))
 901     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 902
 903   // FIXME: implement the other tricky cases
 904
 905   APInt min = getUnsignedMin();
 906   min <<= Other.getUnsignedMin();
 907   max <<= Other_umax;
 908
 909   return ConstantRange(std::move(min), std::move(max) + 1);
 910 }
 911
 912 ConstantRange
 913 ConstantRange::lshr(const ConstantRange &Other) const {
 914   if (isEmptySet() || Other.isEmptySet())
 915     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 916
 917   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
 918   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
 919   if (min == max)
 920     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 921
 922   return ConstantRange(std::move(min), std::move(max));
 923 }
 924
 925 ConstantRange ConstantRange::inverse() const {
 926   if (isFullSet())
 927     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 928   if (isEmptySet())
 929     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 930   return ConstantRange(Upper, Lower);
 931 }
 932
 933 void ConstantRange::print(raw_ostream &OS) const {
 934   if (isFullSet())
 935     OS << "full-set";
 936   else if (isEmptySet())
 937     OS << "empty-set";
 938   else
 939     OS << "[" << Lower << "," << Upper << ")";
 940 }
 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 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
 949   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   auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
 954   auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
 955
 956   ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
 957
 958   for (unsigned i = 1; i < NumRanges; ++i) {
 959     auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
 960     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     CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
 965   }
 966
 967   return CR;
 968 }