1193323Sed//===-- ConstantRange.cpp - ConstantRange implementation ------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// Represent a range of possible values that may occur when the program is run 11193323Sed// for an integral value. This keeps track of a lower and upper bound for the 12193323Sed// constant, which MAY wrap around the end of the numeric range. To do this, it 13193323Sed// keeps track of a [lower, upper) bound, which specifies an interval just like 14193323Sed// STL iterators. When used with boolean values, the following are important 15193323Sed// ranges (other integral ranges use min/max values for special range values): 16193323Sed// 17193323Sed// [F, F) = {} = Empty set 18193323Sed// [T, F) = {T} 19193323Sed// [F, T) = {F} 20193323Sed// [T, T) = {F, T} = Full set 21193323Sed// 22193323Sed//===----------------------------------------------------------------------===// 23193323Sed 24252723Sdim#include "llvm/IR/InstrTypes.h" 25193323Sed#include "llvm/Support/ConstantRange.h" 26202375Srdivacky#include "llvm/Support/Debug.h" 27193323Sed#include "llvm/Support/raw_ostream.h" 28193323Sedusing namespace llvm; 29193323Sed 30193323Sed/// Initialize a full (the default) or empty set for the specified type. 31193323Sed/// 32198090SrdivackyConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { 33193323Sed if (Full) 34193323Sed Lower = Upper = APInt::getMaxValue(BitWidth); 35193323Sed else 36193323Sed Lower = Upper = APInt::getMinValue(BitWidth); 37193323Sed} 38193323Sed 39193323Sed/// Initialize a range to hold the single specified value. 40193323Sed/// 41263509SdimConstantRange::ConstantRange(APIntMoveTy V) 42263509Sdim : Lower(llvm_move(V)), Upper(Lower + 1) {} 43193323Sed 44263509SdimConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U) 45263509Sdim : Lower(llvm_move(L)), Upper(llvm_move(U)) { 46263509Sdim assert(Lower.getBitWidth() == Upper.getBitWidth() && 47193323Sed "ConstantRange with unequal bit widths"); 48263509Sdim assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && 49193323Sed "Lower == Upper, but they aren't min or max value!"); 50193323Sed} 51193323Sed 52198090SrdivackyConstantRange ConstantRange::makeICmpRegion(unsigned Pred, 53198090Srdivacky const ConstantRange &CR) { 54218893Sdim if (CR.isEmptySet()) 55218893Sdim return CR; 56218893Sdim 57198090Srdivacky uint32_t W = CR.getBitWidth(); 58198090Srdivacky switch (Pred) { 59235633Sdim default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()"); 60226890Sdim case CmpInst::ICMP_EQ: 61198090Srdivacky return CR; 62226890Sdim case CmpInst::ICMP_NE: 63198090Srdivacky if (CR.isSingleElement()) 64198090Srdivacky return ConstantRange(CR.getUpper(), CR.getLower()); 65198090Srdivacky return ConstantRange(W); 66226890Sdim case CmpInst::ICMP_ULT: { 67218893Sdim APInt UMax(CR.getUnsignedMax()); 68218893Sdim if (UMax.isMinValue()) 69218893Sdim return ConstantRange(W, /* empty */ false); 70218893Sdim return ConstantRange(APInt::getMinValue(W), UMax); 71218893Sdim } 72226890Sdim case CmpInst::ICMP_SLT: { 73218893Sdim APInt SMax(CR.getSignedMax()); 74218893Sdim if (SMax.isMinSignedValue()) 75218893Sdim return ConstantRange(W, /* empty */ false); 76218893Sdim return ConstantRange(APInt::getSignedMinValue(W), SMax); 77218893Sdim } 78226890Sdim case CmpInst::ICMP_ULE: { 79198090Srdivacky APInt UMax(CR.getUnsignedMax()); 80198090Srdivacky if (UMax.isMaxValue()) 81198090Srdivacky return ConstantRange(W); 82198090Srdivacky return ConstantRange(APInt::getMinValue(W), UMax + 1); 83198090Srdivacky } 84226890Sdim case CmpInst::ICMP_SLE: { 85198090Srdivacky APInt SMax(CR.getSignedMax()); 86218893Sdim if (SMax.isMaxSignedValue()) 87198090Srdivacky return ConstantRange(W); 88198090Srdivacky return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); 89198090Srdivacky } 90226890Sdim case CmpInst::ICMP_UGT: { 91218893Sdim APInt UMin(CR.getUnsignedMin()); 92218893Sdim if (UMin.isMaxValue()) 93218893Sdim return ConstantRange(W, /* empty */ false); 94218893Sdim return ConstantRange(UMin + 1, APInt::getNullValue(W)); 95218893Sdim } 96226890Sdim case CmpInst::ICMP_SGT: { 97218893Sdim APInt SMin(CR.getSignedMin()); 98218893Sdim if (SMin.isMaxSignedValue()) 99218893Sdim return ConstantRange(W, /* empty */ false); 100218893Sdim return ConstantRange(SMin + 1, APInt::getSignedMinValue(W)); 101218893Sdim } 102226890Sdim case CmpInst::ICMP_UGE: { 103198090Srdivacky APInt UMin(CR.getUnsignedMin()); 104198090Srdivacky if (UMin.isMinValue()) 105198090Srdivacky return ConstantRange(W); 106198090Srdivacky return ConstantRange(UMin, APInt::getNullValue(W)); 107198090Srdivacky } 108226890Sdim case CmpInst::ICMP_SGE: { 109198090Srdivacky APInt SMin(CR.getSignedMin()); 110198090Srdivacky if (SMin.isMinSignedValue()) 111198090Srdivacky return ConstantRange(W); 112198090Srdivacky return ConstantRange(SMin, APInt::getSignedMinValue(W)); 113198090Srdivacky } 114198090Srdivacky } 115198090Srdivacky} 116198090Srdivacky 117193323Sed/// isFullSet - Return true if this set contains all of the elements possible 118193323Sed/// for this data-type 119193323Sedbool ConstantRange::isFullSet() const { 120193323Sed return Lower == Upper && Lower.isMaxValue(); 121193323Sed} 122193323Sed 123193323Sed/// isEmptySet - Return true if this set contains no members. 124193323Sed/// 125193323Sedbool ConstantRange::isEmptySet() const { 126193323Sed return Lower == Upper && Lower.isMinValue(); 127193323Sed} 128193323Sed 129193323Sed/// isWrappedSet - Return true if this set wraps around the top of the range, 130193323Sed/// for example: [100, 8) 131193323Sed/// 132193323Sedbool ConstantRange::isWrappedSet() const { 133193323Sed return Lower.ugt(Upper); 134193323Sed} 135193323Sed 136218893Sdim/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of 137218893Sdim/// its bitwidth, for example: i8 [120, 140). 138218893Sdim/// 139218893Sdimbool ConstantRange::isSignWrappedSet() const { 140218893Sdim return contains(APInt::getSignedMaxValue(getBitWidth())) && 141218893Sdim contains(APInt::getSignedMinValue(getBitWidth())); 142218893Sdim} 143218893Sdim 144193323Sed/// getSetSize - Return the number of elements in this set. 145193323Sed/// 146193323SedAPInt ConstantRange::getSetSize() const { 147245431Sdim if (isFullSet()) { 148245431Sdim APInt Size(getBitWidth()+1, 0); 149245431Sdim Size.setBit(getBitWidth()); 150245431Sdim return Size; 151193323Sed } 152193323Sed 153245431Sdim // This is also correct for wrapped sets. 154245431Sdim return (Upper - Lower).zext(getBitWidth()+1); 155193323Sed} 156193323Sed 157193323Sed/// getUnsignedMax - Return the largest unsigned value contained in the 158193323Sed/// ConstantRange. 159193323Sed/// 160193323SedAPInt ConstantRange::getUnsignedMax() const { 161193323Sed if (isFullSet() || isWrappedSet()) 162193323Sed return APInt::getMaxValue(getBitWidth()); 163235633Sdim return getUpper() - 1; 164193323Sed} 165193323Sed 166193323Sed/// getUnsignedMin - Return the smallest unsigned value contained in the 167193323Sed/// ConstantRange. 168193323Sed/// 169193323SedAPInt ConstantRange::getUnsignedMin() const { 170193323Sed if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 171193323Sed return APInt::getMinValue(getBitWidth()); 172235633Sdim return getLower(); 173193323Sed} 174193323Sed 175193323Sed/// getSignedMax - Return the largest signed value contained in the 176193323Sed/// ConstantRange. 177193323Sed/// 178193323SedAPInt ConstantRange::getSignedMax() const { 179193323Sed APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 180193323Sed if (!isWrappedSet()) { 181193323Sed if (getLower().sle(getUpper() - 1)) 182193323Sed return getUpper() - 1; 183235633Sdim return SignedMax; 184193323Sed } 185235633Sdim if (getLower().isNegative() == getUpper().isNegative()) 186235633Sdim return SignedMax; 187235633Sdim return getUpper() - 1; 188193323Sed} 189193323Sed 190193323Sed/// getSignedMin - Return the smallest signed value contained in the 191193323Sed/// ConstantRange. 192193323Sed/// 193193323SedAPInt ConstantRange::getSignedMin() const { 194193323Sed APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 195193323Sed if (!isWrappedSet()) { 196193323Sed if (getLower().sle(getUpper() - 1)) 197193323Sed return getLower(); 198235633Sdim return SignedMin; 199235633Sdim } 200235633Sdim if ((getUpper() - 1).slt(getLower())) { 201235633Sdim if (getUpper() != SignedMin) 202193323Sed return SignedMin; 203193323Sed } 204235633Sdim return getLower(); 205193323Sed} 206193323Sed 207193323Sed/// contains - Return true if the specified value is in the set. 208193323Sed/// 209193323Sedbool ConstantRange::contains(const APInt &V) const { 210193323Sed if (Lower == Upper) 211193323Sed return isFullSet(); 212193323Sed 213193323Sed if (!isWrappedSet()) 214193323Sed return Lower.ule(V) && V.ult(Upper); 215235633Sdim return Lower.ule(V) || V.ult(Upper); 216193323Sed} 217193323Sed 218198090Srdivacky/// contains - Return true if the argument is a subset of this range. 219212904Sdim/// Two equal sets contain each other. The empty set contained by all other 220212904Sdim/// sets. 221198090Srdivacky/// 222198090Srdivackybool ConstantRange::contains(const ConstantRange &Other) const { 223212904Sdim if (isFullSet() || Other.isEmptySet()) return true; 224212904Sdim if (isEmptySet() || Other.isFullSet()) return false; 225198090Srdivacky 226198090Srdivacky if (!isWrappedSet()) { 227198090Srdivacky if (Other.isWrappedSet()) 228198090Srdivacky return false; 229198090Srdivacky 230198090Srdivacky return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 231198090Srdivacky } 232198090Srdivacky 233198090Srdivacky if (!Other.isWrappedSet()) 234198090Srdivacky return Other.getUpper().ule(Upper) || 235198090Srdivacky Lower.ule(Other.getLower()); 236198090Srdivacky 237198090Srdivacky return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 238198090Srdivacky} 239198090Srdivacky 240193323Sed/// subtract - Subtract the specified constant from the endpoints of this 241193323Sed/// constant range. 242193323SedConstantRange ConstantRange::subtract(const APInt &Val) const { 243193323Sed assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 244193323Sed // If the set is empty or full, don't modify the endpoints. 245193323Sed if (Lower == Upper) 246193323Sed return *this; 247193323Sed return ConstantRange(Lower - Val, Upper - Val); 248193323Sed} 249193323Sed 250245431Sdim/// \brief Subtract the specified range from this range (aka relative complement 251245431Sdim/// of the sets). 252245431SdimConstantRange ConstantRange::difference(const ConstantRange &CR) const { 253245431Sdim return intersectWith(CR.inverse()); 254245431Sdim} 255245431Sdim 256193323Sed/// intersectWith - Return the range that results from the intersection of this 257198090Srdivacky/// range with another range. The resultant range is guaranteed to include all 258198090Srdivacky/// elements contained in both input ranges, and to have the smallest possible 259198090Srdivacky/// set size that does so. Because there may be two intersections with the 260198090Srdivacky/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 261193323SedConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 262193323Sed assert(getBitWidth() == CR.getBitWidth() && 263193323Sed "ConstantRange types don't agree!"); 264193323Sed 265193323Sed // Handle common cases. 266193323Sed if ( isEmptySet() || CR.isFullSet()) return *this; 267193323Sed if (CR.isEmptySet() || isFullSet()) return CR; 268193323Sed 269193323Sed if (!isWrappedSet() && CR.isWrappedSet()) 270198090Srdivacky return CR.intersectWith(*this); 271193323Sed 272193323Sed if (!isWrappedSet() && !CR.isWrappedSet()) { 273193323Sed if (Lower.ult(CR.Lower)) { 274193323Sed if (Upper.ule(CR.Lower)) 275193323Sed return ConstantRange(getBitWidth(), false); 276193323Sed 277193323Sed if (Upper.ult(CR.Upper)) 278193323Sed return ConstantRange(CR.Lower, Upper); 279193323Sed 280193323Sed return CR; 281235633Sdim } 282235633Sdim if (Upper.ult(CR.Upper)) 283235633Sdim return *this; 284193323Sed 285235633Sdim if (Lower.ult(CR.Upper)) 286235633Sdim return ConstantRange(Lower, CR.Upper); 287193323Sed 288235633Sdim return ConstantRange(getBitWidth(), false); 289193323Sed } 290193323Sed 291193323Sed if (isWrappedSet() && !CR.isWrappedSet()) { 292193323Sed if (CR.Lower.ult(Upper)) { 293193323Sed if (CR.Upper.ult(Upper)) 294193323Sed return CR; 295193323Sed 296245431Sdim if (CR.Upper.ule(Lower)) 297193323Sed return ConstantRange(CR.Lower, Upper); 298193323Sed 299193323Sed if (getSetSize().ult(CR.getSetSize())) 300193323Sed return *this; 301235633Sdim return CR; 302235633Sdim } 303235633Sdim if (CR.Lower.ult(Lower)) { 304193323Sed if (CR.Upper.ule(Lower)) 305193323Sed return ConstantRange(getBitWidth(), false); 306193323Sed 307193323Sed return ConstantRange(Lower, CR.Upper); 308193323Sed } 309193323Sed return CR; 310193323Sed } 311193323Sed 312193323Sed if (CR.Upper.ult(Upper)) { 313193323Sed if (CR.Lower.ult(Upper)) { 314193323Sed if (getSetSize().ult(CR.getSetSize())) 315193323Sed return *this; 316235633Sdim return CR; 317193323Sed } 318193323Sed 319193323Sed if (CR.Lower.ult(Lower)) 320193323Sed return ConstantRange(Lower, CR.Upper); 321193323Sed 322193323Sed return CR; 323235633Sdim } 324245431Sdim if (CR.Upper.ule(Lower)) { 325193323Sed if (CR.Lower.ult(Lower)) 326193323Sed return *this; 327193323Sed 328193323Sed return ConstantRange(CR.Lower, Upper); 329193323Sed } 330193323Sed if (getSetSize().ult(CR.getSetSize())) 331193323Sed return *this; 332235633Sdim return CR; 333193323Sed} 334193323Sed 335193323Sed 336193323Sed/// unionWith - Return the range that results from the union of this range with 337193323Sed/// another range. The resultant range is guaranteed to include the elements of 338193323Sed/// both sets, but may contain more. For example, [3, 9) union [12,15) is 339193323Sed/// [3, 15), which includes 9, 10, and 11, which were not included in either 340193323Sed/// set before. 341193323Sed/// 342193323SedConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 343193323Sed assert(getBitWidth() == CR.getBitWidth() && 344193323Sed "ConstantRange types don't agree!"); 345193323Sed 346193323Sed if ( isFullSet() || CR.isEmptySet()) return *this; 347193323Sed if (CR.isFullSet() || isEmptySet()) return CR; 348193323Sed 349193323Sed if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 350193323Sed 351198090Srdivacky if (!isWrappedSet() && !CR.isWrappedSet()) { 352198090Srdivacky if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 353198090Srdivacky // If the two ranges are disjoint, find the smaller gap and bridge it. 354198090Srdivacky APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 355198090Srdivacky if (d1.ult(d2)) 356198090Srdivacky return ConstantRange(Lower, CR.Upper); 357235633Sdim return ConstantRange(CR.Lower, Upper); 358198090Srdivacky } 359193323Sed 360198090Srdivacky APInt L = Lower, U = Upper; 361193323Sed if (CR.Lower.ult(L)) 362193323Sed L = CR.Lower; 363198090Srdivacky if ((CR.Upper - 1).ugt(U - 1)) 364198090Srdivacky U = CR.Upper; 365193323Sed 366198090Srdivacky if (L == 0 && U == 0) 367198090Srdivacky return ConstantRange(getBitWidth()); 368198090Srdivacky 369198090Srdivacky return ConstantRange(L, U); 370193323Sed } 371193323Sed 372198090Srdivacky if (!CR.isWrappedSet()) { 373198090Srdivacky // ------U L----- and ------U L----- : this 374198090Srdivacky // L--U L--U : CR 375198090Srdivacky if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 376193323Sed return *this; 377193323Sed 378198090Srdivacky // ------U L----- : this 379198090Srdivacky // L---------U : CR 380198090Srdivacky if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 381193323Sed return ConstantRange(getBitWidth()); 382193323Sed 383198090Srdivacky // ----U L---- : this 384198090Srdivacky // L---U : CR 385198090Srdivacky // <d1> <d2> 386198090Srdivacky if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 387193323Sed APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 388198090Srdivacky if (d1.ult(d2)) 389198090Srdivacky return ConstantRange(Lower, CR.Upper); 390235633Sdim return ConstantRange(CR.Lower, Upper); 391193323Sed } 392193323Sed 393198090Srdivacky // ----U L----- : this 394198090Srdivacky // L----U : CR 395198090Srdivacky if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 396198090Srdivacky return ConstantRange(CR.Lower, Upper); 397193323Sed 398198090Srdivacky // ------U L---- : this 399198090Srdivacky // L-----U : CR 400235633Sdim assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && 401235633Sdim "ConstantRange::unionWith missed a case with one range wrapped"); 402235633Sdim return ConstantRange(Lower, CR.Upper); 403193323Sed } 404193323Sed 405198090Srdivacky // ------U L---- and ------U L---- : this 406198090Srdivacky // -U L----------- and ------------U L : CR 407198090Srdivacky if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 408198090Srdivacky return ConstantRange(getBitWidth()); 409193323Sed 410198090Srdivacky APInt L = Lower, U = Upper; 411198090Srdivacky if (CR.Upper.ugt(U)) 412198090Srdivacky U = CR.Upper; 413198090Srdivacky if (CR.Lower.ult(L)) 414198090Srdivacky L = CR.Lower; 415193323Sed 416193323Sed return ConstantRange(L, U); 417193323Sed} 418193323Sed 419193323Sed/// zeroExtend - Return a new range in the specified integer type, which must 420193323Sed/// be strictly larger than the current type. The returned range will 421193323Sed/// correspond to the possible range of values as if the source range had been 422193323Sed/// zero extended. 423193323SedConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 424218893Sdim if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 425218893Sdim 426193323Sed unsigned SrcTySize = getBitWidth(); 427193323Sed assert(SrcTySize < DstTySize && "Not a value extension"); 428245431Sdim if (isFullSet() || isWrappedSet()) { 429218893Sdim // Change into [0, 1 << src bit width) 430245431Sdim APInt LowerExt(DstTySize, 0); 431245431Sdim if (!Upper) // special case: [X, 0) -- not really wrapping around 432245431Sdim LowerExt = Lower.zext(DstTySize); 433263509Sdim return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize)); 434245431Sdim } 435193323Sed 436218893Sdim return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); 437193323Sed} 438193323Sed 439193323Sed/// signExtend - Return a new range in the specified integer type, which must 440193323Sed/// be strictly larger than the current type. The returned range will 441193323Sed/// correspond to the possible range of values as if the source range had been 442193323Sed/// sign extended. 443193323SedConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 444218893Sdim if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 445218893Sdim 446193323Sed unsigned SrcTySize = getBitWidth(); 447193323Sed assert(SrcTySize < DstTySize && "Not a value extension"); 448263509Sdim 449263509Sdim // special case: [X, INT_MIN) -- not really wrapping around 450263509Sdim if (Upper.isMinSignedValue()) 451263509Sdim return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize)); 452263509Sdim 453218893Sdim if (isFullSet() || isSignWrappedSet()) { 454193323Sed return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 455198090Srdivacky APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 456193323Sed } 457193323Sed 458218893Sdim return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); 459193323Sed} 460193323Sed 461193323Sed/// truncate - Return a new range in the specified integer type, which must be 462193323Sed/// strictly smaller than the current type. The returned range will 463193323Sed/// correspond to the possible range of values as if the source range had been 464193323Sed/// truncated to the specified type. 465193323SedConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 466235633Sdim assert(getBitWidth() > DstTySize && "Not a value truncation"); 467245431Sdim if (isEmptySet()) 468245431Sdim return ConstantRange(DstTySize, /*isFullSet=*/false); 469245431Sdim if (isFullSet()) 470212904Sdim return ConstantRange(DstTySize, /*isFullSet=*/true); 471193323Sed 472245431Sdim APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth()); 473245431Sdim APInt MaxBitValue(getBitWidth(), 0); 474245431Sdim MaxBitValue.setBit(DstTySize); 475245431Sdim 476245431Sdim APInt LowerDiv(Lower), UpperDiv(Upper); 477245431Sdim ConstantRange Union(DstTySize, /*isFullSet=*/false); 478245431Sdim 479245431Sdim // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] 480245431Sdim // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and 481245431Sdim // then we do the union with [MaxValue, Upper) 482245431Sdim if (isWrappedSet()) { 483245431Sdim // if Upper is greater than Max Value, it covers the whole truncated range. 484245431Sdim if (Upper.uge(MaxValue)) 485245431Sdim return ConstantRange(DstTySize, /*isFullSet=*/true); 486245431Sdim 487245431Sdim Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); 488245431Sdim UpperDiv = APInt::getMaxValue(getBitWidth()); 489245431Sdim 490245431Sdim // Union covers the MaxValue case, so return if the remaining range is just 491245431Sdim // MaxValue. 492245431Sdim if (LowerDiv == UpperDiv) 493245431Sdim return Union; 494245431Sdim } 495245431Sdim 496245431Sdim // Chop off the most significant bits that are past the destination bitwidth. 497245431Sdim if (LowerDiv.uge(MaxValue)) { 498245431Sdim APInt Div(getBitWidth(), 0); 499245431Sdim APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv); 500245431Sdim UpperDiv = UpperDiv - MaxBitValue * Div; 501245431Sdim } 502245431Sdim 503245431Sdim if (UpperDiv.ule(MaxValue)) 504245431Sdim return ConstantRange(LowerDiv.trunc(DstTySize), 505245431Sdim UpperDiv.trunc(DstTySize)).unionWith(Union); 506245431Sdim 507245431Sdim // The truncated value wrapps around. Check if we can do better than fullset. 508245431Sdim APInt UpperModulo = UpperDiv - MaxBitValue; 509245431Sdim if (UpperModulo.ult(LowerDiv)) 510245431Sdim return ConstantRange(LowerDiv.trunc(DstTySize), 511245431Sdim UpperModulo.trunc(DstTySize)).unionWith(Union); 512245431Sdim 513245431Sdim return ConstantRange(DstTySize, /*isFullSet=*/true); 514193323Sed} 515193323Sed 516199481Srdivacky/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 517199481Srdivacky/// value is zero extended, truncated, or left alone to make it that width. 518199481SrdivackyConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 519199481Srdivacky unsigned SrcTySize = getBitWidth(); 520199481Srdivacky if (SrcTySize > DstTySize) 521199481Srdivacky return truncate(DstTySize); 522235633Sdim if (SrcTySize < DstTySize) 523199481Srdivacky return zeroExtend(DstTySize); 524235633Sdim return *this; 525199481Srdivacky} 526199481Srdivacky 527199481Srdivacky/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 528199481Srdivacky/// value is sign extended, truncated, or left alone to make it that width. 529199481SrdivackyConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 530199481Srdivacky unsigned SrcTySize = getBitWidth(); 531199481Srdivacky if (SrcTySize > DstTySize) 532199481Srdivacky return truncate(DstTySize); 533235633Sdim if (SrcTySize < DstTySize) 534199481Srdivacky return signExtend(DstTySize); 535235633Sdim return *this; 536199481Srdivacky} 537199481Srdivacky 538198090SrdivackyConstantRange 539198090SrdivackyConstantRange::add(const ConstantRange &Other) const { 540198090Srdivacky if (isEmptySet() || Other.isEmptySet()) 541198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 542198090Srdivacky if (isFullSet() || Other.isFullSet()) 543198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 544198090Srdivacky 545198090Srdivacky APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 546198090Srdivacky APInt NewLower = getLower() + Other.getLower(); 547198090Srdivacky APInt NewUpper = getUpper() + Other.getUpper() - 1; 548198090Srdivacky if (NewLower == NewUpper) 549198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 550198090Srdivacky 551198090Srdivacky ConstantRange X = ConstantRange(NewLower, NewUpper); 552198090Srdivacky if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 553198090Srdivacky // We've wrapped, therefore, full set. 554198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 555198090Srdivacky 556198090Srdivacky return X; 557198090Srdivacky} 558198090Srdivacky 559198090SrdivackyConstantRange 560212904SdimConstantRange::sub(const ConstantRange &Other) const { 561212904Sdim if (isEmptySet() || Other.isEmptySet()) 562212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/false); 563212904Sdim if (isFullSet() || Other.isFullSet()) 564212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/true); 565212904Sdim 566212904Sdim APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 567224145Sdim APInt NewLower = getLower() - Other.getUpper() + 1; 568224145Sdim APInt NewUpper = getUpper() - Other.getLower(); 569212904Sdim if (NewLower == NewUpper) 570212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/true); 571212904Sdim 572212904Sdim ConstantRange X = ConstantRange(NewLower, NewUpper); 573212904Sdim if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 574212904Sdim // We've wrapped, therefore, full set. 575212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/true); 576212904Sdim 577212904Sdim return X; 578212904Sdim} 579212904Sdim 580212904SdimConstantRange 581198090SrdivackyConstantRange::multiply(const ConstantRange &Other) const { 582203954Srdivacky // TODO: If either operand is a single element and the multiply is known to 583203954Srdivacky // be non-wrapping, round the result min and max value to the appropriate 584203954Srdivacky // multiple of that element. If wrapping is possible, at least adjust the 585203954Srdivacky // range according to the greatest power-of-two factor of the single element. 586203954Srdivacky 587198090Srdivacky if (isEmptySet() || Other.isEmptySet()) 588198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 589198090Srdivacky 590198090Srdivacky APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 591198090Srdivacky APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 592198090Srdivacky APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 593198090Srdivacky APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 594198090Srdivacky 595198090Srdivacky ConstantRange Result_zext = ConstantRange(this_min * Other_min, 596198090Srdivacky this_max * Other_max + 1); 597198090Srdivacky return Result_zext.truncate(getBitWidth()); 598198090Srdivacky} 599198090Srdivacky 600198090SrdivackyConstantRange 601198090SrdivackyConstantRange::smax(const ConstantRange &Other) const { 602198090Srdivacky // X smax Y is: range(smax(X_smin, Y_smin), 603198090Srdivacky // smax(X_smax, Y_smax)) 604198090Srdivacky if (isEmptySet() || Other.isEmptySet()) 605198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 606198090Srdivacky APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 607198090Srdivacky APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 608198090Srdivacky if (NewU == NewL) 609198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 610198090Srdivacky return ConstantRange(NewL, NewU); 611198090Srdivacky} 612198090Srdivacky 613198090SrdivackyConstantRange 614198090SrdivackyConstantRange::umax(const ConstantRange &Other) const { 615198090Srdivacky // X umax Y is: range(umax(X_umin, Y_umin), 616198090Srdivacky // umax(X_umax, Y_umax)) 617198090Srdivacky if (isEmptySet() || Other.isEmptySet()) 618198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 619198090Srdivacky APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 620198090Srdivacky APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 621198090Srdivacky if (NewU == NewL) 622198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 623198090Srdivacky return ConstantRange(NewL, NewU); 624198090Srdivacky} 625198090Srdivacky 626198090SrdivackyConstantRange 627198090SrdivackyConstantRange::udiv(const ConstantRange &RHS) const { 628198090Srdivacky if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 629198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/false); 630198090Srdivacky if (RHS.isFullSet()) 631198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 632198090Srdivacky 633198090Srdivacky APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 634198090Srdivacky 635198090Srdivacky APInt RHS_umin = RHS.getUnsignedMin(); 636198090Srdivacky if (RHS_umin == 0) { 637198090Srdivacky // We want the lowest value in RHS excluding zero. Usually that would be 1 638198090Srdivacky // except for a range in the form of [X, 1) in which case it would be X. 639198090Srdivacky if (RHS.getUpper() == 1) 640198090Srdivacky RHS_umin = RHS.getLower(); 641198090Srdivacky else 642198090Srdivacky RHS_umin = APInt(getBitWidth(), 1); 643198090Srdivacky } 644198090Srdivacky 645198090Srdivacky APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 646198090Srdivacky 647198090Srdivacky // If the LHS is Full and the RHS is a wrapped interval containing 1 then 648198090Srdivacky // this could occur. 649198090Srdivacky if (Lower == Upper) 650198090Srdivacky return ConstantRange(getBitWidth(), /*isFullSet=*/true); 651198090Srdivacky 652198090Srdivacky return ConstantRange(Lower, Upper); 653198090Srdivacky} 654198090Srdivacky 655199481SrdivackyConstantRange 656218893SdimConstantRange::binaryAnd(const ConstantRange &Other) const { 657218893Sdim if (isEmptySet() || Other.isEmptySet()) 658218893Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/false); 659218893Sdim 660218893Sdim // TODO: replace this with something less conservative 661218893Sdim 662218893Sdim APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); 663218893Sdim if (umin.isAllOnesValue()) 664218893Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/true); 665218893Sdim return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1); 666218893Sdim} 667218893Sdim 668218893SdimConstantRange 669218893SdimConstantRange::binaryOr(const ConstantRange &Other) const { 670218893Sdim if (isEmptySet() || Other.isEmptySet()) 671218893Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/false); 672218893Sdim 673218893Sdim // TODO: replace this with something less conservative 674218893Sdim 675218893Sdim APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 676218893Sdim if (umax.isMinValue()) 677218893Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/true); 678218893Sdim return ConstantRange(umax, APInt::getNullValue(getBitWidth())); 679218893Sdim} 680218893Sdim 681218893SdimConstantRange 682212904SdimConstantRange::shl(const ConstantRange &Other) const { 683212904Sdim if (isEmptySet() || Other.isEmptySet()) 684212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/false); 685199481Srdivacky 686212904Sdim APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); 687212904Sdim APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); 688199481Srdivacky 689199481Srdivacky // there's no overflow! 690199481Srdivacky APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 691212904Sdim if (Zeros.ugt(Other.getUnsignedMax())) 692212904Sdim return ConstantRange(min, max + 1); 693199481Srdivacky 694199481Srdivacky // FIXME: implement the other tricky cases 695212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/true); 696199481Srdivacky} 697199481Srdivacky 698199481SrdivackyConstantRange 699212904SdimConstantRange::lshr(const ConstantRange &Other) const { 700212904Sdim if (isEmptySet() || Other.isEmptySet()) 701212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/false); 702212904Sdim 703212904Sdim APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()); 704212904Sdim APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); 705212904Sdim if (min == max + 1) 706212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/true); 707199481Srdivacky 708212904Sdim return ConstantRange(min, max + 1); 709199481Srdivacky} 710199481Srdivacky 711212904SdimConstantRange ConstantRange::inverse() const { 712235633Sdim if (isFullSet()) 713212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/false); 714235633Sdim if (isEmptySet()) 715212904Sdim return ConstantRange(getBitWidth(), /*isFullSet=*/true); 716212904Sdim return ConstantRange(Upper, Lower); 717199481Srdivacky} 718199481Srdivacky 719193323Sed/// print - Print out the bounds to a stream... 720193323Sed/// 721193323Sedvoid ConstantRange::print(raw_ostream &OS) const { 722203954Srdivacky if (isFullSet()) 723203954Srdivacky OS << "full-set"; 724203954Srdivacky else if (isEmptySet()) 725203954Srdivacky OS << "empty-set"; 726203954Srdivacky else 727203954Srdivacky OS << "[" << Lower << "," << Upper << ")"; 728193323Sed} 729193323Sed 730193323Sed/// dump - Allow printing from a debugger easily... 731193323Sed/// 732193323Sedvoid ConstantRange::dump() const { 733202375Srdivacky print(dbgs()); 734193323Sed} 735