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   ConstantRange Result(BitWidth);
 203
 204   switch (BinOp) {
 205   default:
 206     // Conservative answer: empty set
 207     return ConstantRange(BitWidth, false);
 208
 209   case Instruction::Add:
 210     if (auto *C = Other.getSingleElement())
 211       if (C->isNullValue())
 212         // Full set: nothing signed / unsigned wraps when added to 0.
 213         return ConstantRange(BitWidth);
 214     if (NoWrapKind & OBO::NoUnsignedWrap)
 215       Result =
 216           SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
 217                                                 -Other.getUnsignedMax()));
 218     if (NoWrapKind & OBO::NoSignedWrap) {
 219       const APInt &SignedMin = Other.getSignedMin();
 220       const APInt &SignedMax = Other.getSignedMax();
 221       if (SignedMax.isStrictlyPositive())
 222         Result = SubsetIntersect(
 223             Result,
 224             ConstantRange(APInt::getSignedMinValue(BitWidth),
 225                           APInt::getSignedMinValue(BitWidth) - SignedMax));
 226       if (SignedMin.isNegative())
 227         Result = SubsetIntersect(
 228             Result,
 229             ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
 230                           APInt::getSignedMinValue(BitWidth)));
 231     }
 232     return Result;
 233
 234   case Instruction::Sub:
 235     if (auto *C = Other.getSingleElement())
 236       if (C->isNullValue())
 237         // Full set: nothing signed / unsigned wraps when subtracting 0.
 238         return ConstantRange(BitWidth);
 239     if (NoWrapKind & OBO::NoUnsignedWrap)
 240       Result =
 241           SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(),
 242                                                 APInt::getMinValue(BitWidth)));
 243     if (NoWrapKind & OBO::NoSignedWrap) {
 244       const APInt &SignedMin = Other.getSignedMin();
 245       const APInt &SignedMax = Other.getSignedMax();
 246       if (SignedMax.isStrictlyPositive())
 247         Result = SubsetIntersect(
 248             Result,
 249             ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax,
 250                           APInt::getSignedMinValue(BitWidth)));
 251       if (SignedMin.isNegative())
 252         Result = SubsetIntersect(
 253             Result,
 254             ConstantRange(APInt::getSignedMinValue(BitWidth),
 255                           APInt::getSignedMinValue(BitWidth) + SignedMin));
 256     }
 257     return Result;
 258   }
 259 }
 260
 261 bool ConstantRange::isFullSet() const {
 262   return Lower == Upper && Lower.isMaxValue();
 263 }
 264
 265 bool ConstantRange::isEmptySet() const {
 266   return Lower == Upper && Lower.isMinValue();
 267 }
 268
 269 bool ConstantRange::isWrappedSet() const {
 270   return Lower.ugt(Upper);
 271 }
 272
 273 bool ConstantRange::isSignWrappedSet() const {
 274   return contains(APInt::getSignedMaxValue(getBitWidth())) &&
 275          contains(APInt::getSignedMinValue(getBitWidth()));
 276 }
 277
 278 APInt ConstantRange::getSetSize() const {
 279   if (isFullSet())
 280     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
 281
 282   // This is also correct for wrapped sets.
 283   return (Upper - Lower).zext(getBitWidth()+1);
 284 }
 285
 286 bool
 287 ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
 288   assert(getBitWidth() == Other.getBitWidth());
 289   if (isFullSet())
 290     return false;
 291   if (Other.isFullSet())
 292     return true;
 293   return (Upper - Lower).ult(Other.Upper - Other.Lower);
 294 }
 295
 296 bool
 297 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
 298   assert(MaxSize && "MaxSize can't be 0.");
 299   // If this a full set, we need special handling to avoid needing an extra bit
 300   // to represent the size.
 301   if (isFullSet())
 302     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
 303
 304   return (Upper - Lower).ugt(MaxSize);
 305 }
 306
 307 APInt ConstantRange::getUnsignedMax() const {
 308   if (isFullSet() || isWrappedSet())
 309     return APInt::getMaxValue(getBitWidth());
 310   return getUpper() - 1;
 311 }
 312
 313 APInt ConstantRange::getUnsignedMin() const {
 314   if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
 315     return APInt::getMinValue(getBitWidth());
 316   return getLower();
 317 }
 318
 319 APInt ConstantRange::getSignedMax() const {
 320   if (isFullSet() || Lower.sgt(Upper))
 321     return APInt::getSignedMaxValue(getBitWidth());
 322   return getUpper() - 1;
 323 }
 324
 325 APInt ConstantRange::getSignedMin() const {
 326   if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
 327     return APInt::getSignedMinValue(getBitWidth());
 328   return getLower();
 329 }
 330
 331 bool ConstantRange::contains(const APInt &V) const {
 332   if (Lower == Upper)
 333     return isFullSet();
 334
 335   if (!isWrappedSet())
 336     return Lower.ule(V) && V.ult(Upper);
 337   return Lower.ule(V) || V.ult(Upper);
 338 }
 339
 340 bool ConstantRange::contains(const ConstantRange &Other) const {
 341   if (isFullSet() || Other.isEmptySet()) return true;
 342   if (isEmptySet() || Other.isFullSet()) return false;
 343
 344   if (!isWrappedSet()) {
 345     if (Other.isWrappedSet())
 346       return false;
 347
 348     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
 349   }
 350
 351   if (!Other.isWrappedSet())
 352     return Other.getUpper().ule(Upper) ||
 353            Lower.ule(Other.getLower());
 354
 355   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
 356 }
 357
 358 ConstantRange ConstantRange::subtract(const APInt &Val) const {
 359   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
 360   // If the set is empty or full, don't modify the endpoints.
 361   if (Lower == Upper)
 362     return *this;
 363   return ConstantRange(Lower - Val, Upper - Val);
 364 }
 365
 366 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
 367   return intersectWith(CR.inverse());
 368 }
 369
 370 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
 371   assert(getBitWidth() == CR.getBitWidth() &&
 372          "ConstantRange types don't agree!");
 373
 374   // Handle common cases.
 375   if (   isEmptySet() || CR.isFullSet()) return *this;
 376   if (CR.isEmptySet() ||    isFullSet()) return CR;
 377
 378   if (!isWrappedSet() && CR.isWrappedSet())
 379     return CR.intersectWith(*this);
 380
 381   if (!isWrappedSet() && !CR.isWrappedSet()) {
 382     if (Lower.ult(CR.Lower)) {
 383       if (Upper.ule(CR.Lower))
 384         return ConstantRange(getBitWidth(), false);
 385
 386       if (Upper.ult(CR.Upper))
 387         return ConstantRange(CR.Lower, Upper);
 388
 389       return CR;
 390     }
 391     if (Upper.ult(CR.Upper))
 392       return *this;
 393
 394     if (Lower.ult(CR.Upper))
 395       return ConstantRange(Lower, CR.Upper);
 396
 397     return ConstantRange(getBitWidth(), false);
 398   }
 399
 400   if (isWrappedSet() && !CR.isWrappedSet()) {
 401     if (CR.Lower.ult(Upper)) {
 402       if (CR.Upper.ult(Upper))
 403         return CR;
 404
 405       if (CR.Upper.ule(Lower))
 406         return ConstantRange(CR.Lower, Upper);
 407
 408       if (isSizeStrictlySmallerThan(CR))
 409         return *this;
 410       return CR;
 411     }
 412     if (CR.Lower.ult(Lower)) {
 413       if (CR.Upper.ule(Lower))
 414         return ConstantRange(getBitWidth(), false);
 415
 416       return ConstantRange(Lower, CR.Upper);
 417     }
 418     return CR;
 419   }
 420
 421   if (CR.Upper.ult(Upper)) {
 422     if (CR.Lower.ult(Upper)) {
 423       if (isSizeStrictlySmallerThan(CR))
 424         return *this;
 425       return CR;
 426     }
 427
 428     if (CR.Lower.ult(Lower))
 429       return ConstantRange(Lower, CR.Upper);
 430
 431     return CR;
 432   }
 433   if (CR.Upper.ule(Lower)) {
 434     if (CR.Lower.ult(Lower))
 435       return *this;
 436
 437     return ConstantRange(CR.Lower, Upper);
 438   }
 439   if (isSizeStrictlySmallerThan(CR))
 440     return *this;
 441   return CR;
 442 }
 443
 444 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
 445   assert(getBitWidth() == CR.getBitWidth() &&
 446          "ConstantRange types don't agree!");
 447
 448   if (   isFullSet() || CR.isEmptySet()) return *this;
 449   if (CR.isFullSet() ||    isEmptySet()) return CR;
 450
 451   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
 452
 453   if (!isWrappedSet() && !CR.isWrappedSet()) {
 454     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
 455       // If the two ranges are disjoint, find the smaller gap and bridge it.
 456       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
 457       if (d1.ult(d2))
 458         return ConstantRange(Lower, CR.Upper);
 459       return ConstantRange(CR.Lower, Upper);
 460     }
 461
 462     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
 463     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
 464
 465     if (L.isNullValue() && U.isNullValue())
 466       return ConstantRange(getBitWidth());
 467
 468     return ConstantRange(std::move(L), std::move(U));
 469   }
 470
 471   if (!CR.isWrappedSet()) {
 472     // ------U   L-----  and  ------U   L----- : this
 473     //   L--U                            L--U  : CR
 474     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
 475       return *this;
 476
 477     // ------U   L----- : this
 478     //    L---------U   : CR
 479     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
 480       return ConstantRange(getBitWidth());
 481
 482     // ----U       L---- : this
 483     //       L---U       : CR
 484     //    <d1>  <d2>
 485     if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
 486       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
 487       if (d1.ult(d2))
 488         return ConstantRange(Lower, CR.Upper);
 489       return ConstantRange(CR.Lower, Upper);
 490     }
 491
 492     // ----U     L----- : this
 493     //        L----U    : CR
 494     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
 495       return ConstantRange(CR.Lower, Upper);
 496
 497     // ------U    L---- : this
 498     //    L-----U       : CR
 499     assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
 500            "ConstantRange::unionWith missed a case with one range wrapped");
 501     return ConstantRange(Lower, CR.Upper);
 502   }
 503
 504   // ------U    L----  and  ------U    L---- : this
 505   // -U  L-----------  and  ------------U  L : CR
 506   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
 507     return ConstantRange(getBitWidth());
 508
 509   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
 510   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
 511
 512   return ConstantRange(std::move(L), std::move(U));
 513 }
 514
 515 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
 516                                     uint32_t ResultBitWidth) const {
 517   switch (CastOp) {
 518   default:
 519     llvm_unreachable("unsupported cast type");
 520   case Instruction::Trunc:
 521     return truncate(ResultBitWidth);
 522   case Instruction::SExt:
 523     return signExtend(ResultBitWidth);
 524   case Instruction::ZExt:
 525     return zeroExtend(ResultBitWidth);
 526   case Instruction::BitCast:
 527     return *this;
 528   case Instruction::FPToUI:
 529   case Instruction::FPToSI:
 530     if (getBitWidth() == ResultBitWidth)
 531       return *this;
 532     else
 533       return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 534   case Instruction::UIToFP: {
 535     // TODO: use input range if available
 536     auto BW = getBitWidth();
 537     APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
 538     APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
 539     return ConstantRange(std::move(Min), std::move(Max));
 540   }
 541   case Instruction::SIToFP: {
 542     // TODO: use input range if available
 543     auto BW = getBitWidth();
 544     APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
 545     APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
 546     return ConstantRange(std::move(SMin), std::move(SMax));
 547   }
 548   case Instruction::FPTrunc:
 549   case Instruction::FPExt:
 550   case Instruction::IntToPtr:
 551   case Instruction::PtrToInt:
 552   case Instruction::AddrSpaceCast:
 553     // Conservatively return full set.
 554     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 555   };
 556 }
 557
 558 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
 559   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
 560
 561   unsigned SrcTySize = getBitWidth();
 562   assert(SrcTySize < DstTySize && "Not a value extension");
 563   if (isFullSet() || isWrappedSet()) {
 564     // Change into [0, 1 << src bit width)
 565     APInt LowerExt(DstTySize, 0);
 566     if (!Upper) // special case: [X, 0) -- not really wrapping around
 567       LowerExt = Lower.zext(DstTySize);
 568     return ConstantRange(std::move(LowerExt),
 569                          APInt::getOneBitSet(DstTySize, SrcTySize));
 570   }
 571
 572   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
 573 }
 574
 575 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
 576   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
 577
 578   unsigned SrcTySize = getBitWidth();
 579   assert(SrcTySize < DstTySize && "Not a value extension");
 580
 581   // special case: [X, INT_MIN) -- not really wrapping around
 582   if (Upper.isMinSignedValue())
 583     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
 584
 585   if (isFullSet() || isSignWrappedSet()) {
 586     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
 587                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
 588   }
 589
 590   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
 591 }
 592
 593 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
 594   assert(getBitWidth() > DstTySize && "Not a value truncation");
 595   if (isEmptySet())
 596     return ConstantRange(DstTySize, /*isFullSet=*/false);
 597   if (isFullSet())
 598     return ConstantRange(DstTySize, /*isFullSet=*/true);
 599
 600   APInt LowerDiv(Lower), UpperDiv(Upper);
 601   ConstantRange Union(DstTySize, /*isFullSet=*/false);
 602
 603   // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
 604   // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
 605   // then we do the union with [MaxValue, Upper)
 606   if (isWrappedSet()) {
 607     // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
 608     // truncated range.
 609     if (Upper.getActiveBits() > DstTySize ||
 610         Upper.countTrailingOnes() == DstTySize)
 611       return ConstantRange(DstTySize, /*isFullSet=*/true);
 612
 613     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
 614     UpperDiv.setAllBits();
 615
 616     // Union covers the MaxValue case, so return if the remaining range is just
 617     // MaxValue(DstTy).
 618     if (LowerDiv == UpperDiv)
 619       return Union;
 620   }
 621
 622   // Chop off the most significant bits that are past the destination bitwidth.
 623   if (LowerDiv.getActiveBits() > DstTySize) {
 624     // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
 625     APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
 626     LowerDiv -= Adjust;
 627     UpperDiv -= Adjust;
 628   }
 629
 630   unsigned UpperDivWidth = UpperDiv.getActiveBits();
 631   if (UpperDivWidth <= DstTySize)
 632     return ConstantRange(LowerDiv.trunc(DstTySize),
 633                          UpperDiv.trunc(DstTySize)).unionWith(Union);
 634
 635   // The truncated value wraps around. Check if we can do better than fullset.
 636   if (UpperDivWidth == DstTySize + 1) {
 637     // Clear the MSB so that UpperDiv wraps around.
 638     UpperDiv.clearBit(DstTySize);
 639     if (UpperDiv.ult(LowerDiv))
 640       return ConstantRange(LowerDiv.trunc(DstTySize),
 641                            UpperDiv.trunc(DstTySize)).unionWith(Union);
 642   }
 643
 644   return ConstantRange(DstTySize, /*isFullSet=*/true);
 645 }
 646
 647 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
 648   unsigned SrcTySize = getBitWidth();
 649   if (SrcTySize > DstTySize)
 650     return truncate(DstTySize);
 651   if (SrcTySize < DstTySize)
 652     return zeroExtend(DstTySize);
 653   return *this;
 654 }
 655
 656 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
 657   unsigned SrcTySize = getBitWidth();
 658   if (SrcTySize > DstTySize)
 659     return truncate(DstTySize);
 660   if (SrcTySize < DstTySize)
 661     return signExtend(DstTySize);
 662   return *this;
 663 }
 664
 665 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
 666                                       const ConstantRange &Other) const {
 667   assert(BinOp >= Instruction::BinaryOpsBegin &&
 668          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
 669
 670   switch (BinOp) {
 671   case Instruction::Add:
 672     return add(Other);
 673   case Instruction::Sub:
 674     return sub(Other);
 675   case Instruction::Mul:
 676     return multiply(Other);
 677   case Instruction::UDiv:
 678     return udiv(Other);
 679   case Instruction::Shl:
 680     return shl(Other);
 681   case Instruction::LShr:
 682     return lshr(Other);
 683   case Instruction::AShr:
 684     return ashr(Other);
 685   case Instruction::And:
 686     return binaryAnd(Other);
 687   case Instruction::Or:
 688     return binaryOr(Other);
 689   // Note: floating point operations applied to abstract ranges are just
 690   // ideal integer operations with a lossy representation
 691   case Instruction::FAdd:
 692     return add(Other);
 693   case Instruction::FSub:
 694     return sub(Other);
 695   case Instruction::FMul:
 696     return multiply(Other);
 697   default:
 698     // Conservatively return full set.
 699     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 700   }
 701 }
 702
 703 ConstantRange
 704 ConstantRange::add(const ConstantRange &Other) const {
 705   if (isEmptySet() || Other.isEmptySet())
 706     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 707   if (isFullSet() || Other.isFullSet())
 708     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 709
 710   APInt NewLower = getLower() + Other.getLower();
 711   APInt NewUpper = getUpper() + Other.getUpper() - 1;
 712   if (NewLower == NewUpper)
 713     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 714
 715   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
 716   if (X.isSizeStrictlySmallerThan(*this) ||
 717       X.isSizeStrictlySmallerThan(Other))
 718     // We've wrapped, therefore, full set.
 719     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 720   return X;
 721 }
 722
 723 ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
 724   // Calculate the subset of this range such that "X + Other" is
 725   // guaranteed not to wrap (overflow) for all X in this subset.
 726   // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
 727   // passing a single element range.
 728   auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
 729                                       ConstantRange(Other),
 730                                       OverflowingBinaryOperator::NoSignedWrap);
 731   auto NSWConstrainedRange = intersectWith(NSWRange);
 732
 733   return NSWConstrainedRange.add(ConstantRange(Other));
 734 }
 735
 736 ConstantRange
 737 ConstantRange::sub(const ConstantRange &Other) const {
 738   if (isEmptySet() || Other.isEmptySet())
 739     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 740   if (isFullSet() || Other.isFullSet())
 741     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 742
 743   APInt NewLower = getLower() - Other.getUpper() + 1;
 744   APInt NewUpper = getUpper() - Other.getLower();
 745   if (NewLower == NewUpper)
 746     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 747
 748   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
 749   if (X.isSizeStrictlySmallerThan(*this) ||
 750       X.isSizeStrictlySmallerThan(Other))
 751     // We've wrapped, therefore, full set.
 752     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 753   return X;
 754 }
 755
 756 ConstantRange
 757 ConstantRange::multiply(const ConstantRange &Other) const {
 758   // TODO: If either operand is a single element and the multiply is known to
 759   // be non-wrapping, round the result min and max value to the appropriate
 760   // multiple of that element. If wrapping is possible, at least adjust the
 761   // range according to the greatest power-of-two factor of the single element.
 762
 763   if (isEmptySet() || Other.isEmptySet())
 764     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 765
 766   // Multiplication is signedness-independent. However different ranges can be
 767   // obtained depending on how the input ranges are treated. These different
 768   // ranges are all conservatively correct, but one might be better than the
 769   // other. We calculate two ranges; one treating the inputs as unsigned
 770   // and the other signed, then return the smallest of these ranges.
 771
 772   // Unsigned range first.
 773   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
 774   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
 775   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
 776   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
 777
 778   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
 779                                             this_max * Other_max + 1);
 780   ConstantRange UR = Result_zext.truncate(getBitWidth());
 781
 782   // If the unsigned range doesn't wrap, and isn't negative then it's a range
 783   // from one positive number to another which is as good as we can generate.
 784   // In this case, skip the extra work of generating signed ranges which aren't
 785   // going to be better than this range.
 786   if (!UR.isWrappedSet() &&
 787       (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
 788     return UR;
 789
 790   // Now the signed range. Because we could be dealing with negative numbers
 791   // here, the lower bound is the smallest of the cartesian product of the
 792   // lower and upper ranges; for example:
 793   //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
 794   // Similarly for the upper bound, swapping min for max.
 795
 796   this_min = getSignedMin().sext(getBitWidth() * 2);
 797   this_max = getSignedMax().sext(getBitWidth() * 2);
 798   Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
 799   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
 800
 801   auto L = {this_min * Other_min, this_min * Other_max,
 802             this_max * Other_min, this_max * Other_max};
 803   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
 804   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
 805   ConstantRange SR = Result_sext.truncate(getBitWidth());
 806
 807   return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
 808 }
 809
 810 ConstantRange
 811 ConstantRange::smax(const ConstantRange &Other) const {
 812   // X smax Y is: range(smax(X_smin, Y_smin),
 813   //                    smax(X_smax, Y_smax))
 814   if (isEmptySet() || Other.isEmptySet())
 815     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 816   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
 817   APInt NewU = APIntOps::smax(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::umax(const ConstantRange &Other) const {
 825   // X umax Y is: range(umax(X_umin, Y_umin),
 826   //                    umax(X_umax, Y_umax))
 827   if (isEmptySet() || Other.isEmptySet())
 828     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 829   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
 830   APInt NewU = APIntOps::umax(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::smin(const ConstantRange &Other) const {
 838   // X smin Y is: range(smin(X_smin, Y_smin),
 839   //                    smin(X_smax, Y_smax))
 840   if (isEmptySet() || Other.isEmptySet())
 841     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 842   APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
 843   APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
 844   if (NewU == NewL)
 845     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 846   return ConstantRange(std::move(NewL), std::move(NewU));
 847 }
 848
 849 ConstantRange
 850 ConstantRange::umin(const ConstantRange &Other) const {
 851   // X umin Y is: range(umin(X_umin, Y_umin),
 852   //                    umin(X_umax, Y_umax))
 853   if (isEmptySet() || Other.isEmptySet())
 854     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 855   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
 856   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
 857   if (NewU == NewL)
 858     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 859   return ConstantRange(std::move(NewL), std::move(NewU));
 860 }
 861
 862 ConstantRange
 863 ConstantRange::udiv(const ConstantRange &RHS) const {
 864   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
 865     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 866   if (RHS.isFullSet())
 867     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 868
 869   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
 870
 871   APInt RHS_umin = RHS.getUnsignedMin();
 872   if (RHS_umin.isNullValue()) {
 873     // We want the lowest value in RHS excluding zero. Usually that would be 1
 874     // except for a range in the form of [X, 1) in which case it would be X.
 875     if (RHS.getUpper() == 1)
 876       RHS_umin = RHS.getLower();
 877     else
 878       RHS_umin = 1;
 879   }
 880
 881   APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
 882
 883   // If the LHS is Full and the RHS is a wrapped interval containing 1 then
 884   // this could occur.
 885   if (Lower == Upper)
 886     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 887
 888   return ConstantRange(std::move(Lower), std::move(Upper));
 889 }
 890
 891 ConstantRange
 892 ConstantRange::binaryAnd(const ConstantRange &Other) const {
 893   if (isEmptySet() || Other.isEmptySet())
 894     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 895
 896   // TODO: replace this with something less conservative
 897
 898   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
 899   if (umin.isAllOnesValue())
 900     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 901   return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
 902 }
 903
 904 ConstantRange
 905 ConstantRange::binaryOr(const ConstantRange &Other) const {
 906   if (isEmptySet() || Other.isEmptySet())
 907     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 908
 909   // TODO: replace this with something less conservative
 910
 911   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
 912   if (umax.isNullValue())
 913     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 914   return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
 915 }
 916
 917 ConstantRange
 918 ConstantRange::shl(const ConstantRange &Other) const {
 919   if (isEmptySet() || Other.isEmptySet())
 920     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 921
 922   APInt max = getUnsignedMax();
 923   APInt Other_umax = Other.getUnsignedMax();
 924
 925   // there's overflow!
 926   if (Other_umax.uge(max.countLeadingZeros()))
 927     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 928
 929   // FIXME: implement the other tricky cases
 930
 931   APInt min = getUnsignedMin();
 932   min <<= Other.getUnsignedMin();
 933   max <<= Other_umax;
 934
 935   return ConstantRange(std::move(min), std::move(max) + 1);
 936 }
 937
 938 ConstantRange
 939 ConstantRange::lshr(const ConstantRange &Other) const {
 940   if (isEmptySet() || Other.isEmptySet())
 941     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 942
 943   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
 944   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
 945   if (min == max)
 946     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
 947
 948   return ConstantRange(std::move(min), std::move(max));
 949 }
 950
 951 ConstantRange
 952 ConstantRange::ashr(const ConstantRange &Other) const {
 953   if (isEmptySet() || Other.isEmptySet())
 954     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
 955
 956   // May straddle zero, so handle both positive and negative cases.
 957   // 'PosMax' is the upper bound of the result of the ashr
 958   // operation, when Upper of the LHS of ashr is a non-negative.
 959   // number. Since ashr of a non-negative number will result in a
 960   // smaller number, the Upper value of LHS is shifted right with
 961   // the minimum value of 'Other' instead of the maximum value.
 962   APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
 963
 964   // 'PosMin' is the lower bound of the result of the ashr
 965   // operation, when Lower of the LHS is a non-negative number.
 966   // Since ashr of a non-negative number will result in a smaller
 967   // number, the Lower value of LHS is shifted right with the
 968   // maximum value of 'Other'.
 969   APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
 970
 971   // 'NegMax' is the upper bound of the result of the ashr
 972   // operation, when Upper of the LHS of ashr is a negative number.
 973   // Since 'ashr' of a negative number will result in a bigger
 974   // number, the Upper value of LHS is shifted right with the
 975   // maximum value of 'Other'.
 976   APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
 977
 978   // 'NegMin' is the lower bound of the result of the ashr
 979   // operation, when Lower of the LHS of ashr is a negative number.
 980   // Since 'ashr' of a negative number will result in a bigger
 981   // number, the Lower value of LHS is shifted right with the
 982   // minimum value of 'Other'.
 983   APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
 984
 985   APInt max, min;
 986   if (getSignedMin().isNonNegative()) {
 987     // Upper and Lower of LHS are non-negative.
 988     min = PosMin;
 989     max = PosMax;
 990   } else if (getSignedMax().isNegative()) {
 991     // Upper and Lower of LHS are negative.
 992     min = NegMin;
 993     max = NegMax;
 994   } else {
 995     // Upper is non-negative and Lower is negative.
 996     min = NegMin;
 997     max = PosMax;
 998   }
 999   if (min == max)
1000     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1001
1002   return ConstantRange(std::move(min), std::move(max));
1003 }
1004
1005 ConstantRange ConstantRange::inverse() const {
1006   if (isFullSet())
1007     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
1008   if (isEmptySet())
1009     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1010   return ConstantRange(Upper, Lower);
1011 }
1012
1013 void ConstantRange::print(raw_ostream &OS) const {
1014   if (isFullSet())
1015     OS << "full-set";
1016   else if (isEmptySet())
1017     OS << "empty-set";
1018   else
1019     OS << "[" << Lower << "," << Upper << ")";
1020 }
1021
1022 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1023 LLVM_DUMP_METHOD void ConstantRange::dump() const {
1024   print(dbgs());
1025 }
1026 #endif
1027
1028 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
1029   const unsigned NumRanges = Ranges.getNumOperands() / 2;
1030   assert(NumRanges >= 1 && "Must have at least one range!");
1031   assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1032
1033   auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1034   auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1035
1036   ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1037
1038   for (unsigned i = 1; i < NumRanges; ++i) {
1039     auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1040     auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1041
1042     // Note: unionWith will potentially create a range that contains values not
1043     // contained in any of the original N ranges.
1044     CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1045   }
1046
1047   return CR;
1048 }