ConstantRange.cpp revision 272461
1250837Ssjg//===-- ConstantRange.cpp - ConstantRange implementation ------------------===// 2236769Sobrien// 3236769Sobrien// The LLVM Compiler Infrastructure 4236769Sobrien// 5236769Sobrien// This file is distributed under the University of Illinois Open Source 6236769Sobrien// License. See LICENSE.TXT for details. 7236769Sobrien// 8236769Sobrien//===----------------------------------------------------------------------===// 9236769Sobrien// 10236769Sobrien// Represent a range of possible values that may occur when the program is run 11236769Sobrien// for an integral value. This keeps track of a lower and upper bound for the 12236769Sobrien// constant, which MAY wrap around the end of the numeric range. To do this, it 13236769Sobrien// keeps track of a [lower, upper) bound, which specifies an interval just like 14236769Sobrien// STL iterators. When used with boolean values, the following are important 15236769Sobrien// ranges (other integral ranges use min/max values for special range values): 16236769Sobrien// 17236769Sobrien// [F, F) = {} = Empty set 18236769Sobrien// [T, F) = {T} 19236769Sobrien// [F, T) = {F} 20236769Sobrien// [T, T) = {F, T} = Full set 21236769Sobrien// 22236769Sobrien//===----------------------------------------------------------------------===// 23236769Sobrien 24236769Sobrien#include "llvm/IR/InstrTypes.h" 25236769Sobrien#include "llvm/Support/ConstantRange.h" 26236769Sobrien#include "llvm/Support/Debug.h" 27236769Sobrien#include "llvm/Support/raw_ostream.h" 28236769Sobrienusing namespace llvm; 29236769Sobrien 30236769Sobrien/// Initialize a full (the default) or empty set for the specified type. 31236769Sobrien/// 32236769SobrienConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { 33236769Sobrien if (Full) 34236769Sobrien Lower = Upper = APInt::getMaxValue(BitWidth); 35236769Sobrien else 36236769Sobrien Lower = Upper = APInt::getMinValue(BitWidth); 37236769Sobrien} 38236769Sobrien 39236769Sobrien/// Initialize a range to hold the single specified value. 40236769Sobrien/// 41236769SobrienConstantRange::ConstantRange(APIntMoveTy V) 42236769Sobrien : Lower(llvm_move(V)), Upper(Lower + 1) {} 43236769Sobrien 44236769SobrienConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U) 45236769Sobrien : Lower(llvm_move(L)), Upper(llvm_move(U)) { 46236769Sobrien assert(Lower.getBitWidth() == Upper.getBitWidth() && 47236769Sobrien "ConstantRange with unequal bit widths"); 48236769Sobrien assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && 49236769Sobrien "Lower == Upper, but they aren't min or max value!"); 50236769Sobrien} 51236769Sobrien 52236769SobrienConstantRange ConstantRange::makeICmpRegion(unsigned Pred, 53236769Sobrien const ConstantRange &CR) { 54236769Sobrien if (CR.isEmptySet()) 55236769Sobrien return CR; 56236769Sobrien 57236769Sobrien uint32_t W = CR.getBitWidth(); 58236769Sobrien switch (Pred) { 59236769Sobrien default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()"); 60236769Sobrien case CmpInst::ICMP_EQ: 61236769Sobrien return CR; 62236769Sobrien case CmpInst::ICMP_NE: 63236769Sobrien if (CR.isSingleElement()) 64236769Sobrien return ConstantRange(CR.getUpper(), CR.getLower()); 65236769Sobrien return ConstantRange(W); 66236769Sobrien case CmpInst::ICMP_ULT: { 67236769Sobrien APInt UMax(CR.getUnsignedMax()); 68236769Sobrien if (UMax.isMinValue()) 69236769Sobrien return ConstantRange(W, /* empty */ false); 70236769Sobrien return ConstantRange(APInt::getMinValue(W), UMax); 71236769Sobrien } 72250837Ssjg case CmpInst::ICMP_SLT: { 73236769Sobrien APInt SMax(CR.getSignedMax()); 74236769Sobrien if (SMax.isMinSignedValue()) 75236769Sobrien return ConstantRange(W, /* empty */ false); 76236769Sobrien return ConstantRange(APInt::getSignedMinValue(W), SMax); 77236769Sobrien } 78236769Sobrien case CmpInst::ICMP_ULE: { 79250837Ssjg APInt UMax(CR.getUnsignedMax()); 80236769Sobrien if (UMax.isMaxValue()) 81236769Sobrien return ConstantRange(W); 82236769Sobrien return ConstantRange(APInt::getMinValue(W), UMax + 1); 83236769Sobrien } 84236769Sobrien case CmpInst::ICMP_SLE: { 85236769Sobrien APInt SMax(CR.getSignedMax()); 86236769Sobrien if (SMax.isMaxSignedValue()) 87236769Sobrien return ConstantRange(W); 88236769Sobrien return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); 89236769Sobrien } 90236769Sobrien case CmpInst::ICMP_UGT: { 91236769Sobrien APInt UMin(CR.getUnsignedMin()); 92236769Sobrien if (UMin.isMaxValue()) 93236769Sobrien return ConstantRange(W, /* empty */ false); 94236769Sobrien return ConstantRange(UMin + 1, APInt::getNullValue(W)); 95236769Sobrien } 96236769Sobrien case CmpInst::ICMP_SGT: { 97236769Sobrien APInt SMin(CR.getSignedMin()); 98236769Sobrien if (SMin.isMaxSignedValue()) 99236769Sobrien return ConstantRange(W, /* empty */ false); 100236769Sobrien return ConstantRange(SMin + 1, APInt::getSignedMinValue(W)); 101236769Sobrien } 102236769Sobrien case CmpInst::ICMP_UGE: { 103236769Sobrien APInt UMin(CR.getUnsignedMin()); 104236769Sobrien if (UMin.isMinValue()) 105236769Sobrien return ConstantRange(W); 106236769Sobrien return ConstantRange(UMin, APInt::getNullValue(W)); 107236769Sobrien } 108236769Sobrien case CmpInst::ICMP_SGE: { 109236769Sobrien APInt SMin(CR.getSignedMin()); 110236769Sobrien if (SMin.isMinSignedValue()) 111236769Sobrien return ConstantRange(W); 112236769Sobrien return ConstantRange(SMin, APInt::getSignedMinValue(W)); 113236769Sobrien } 114236769Sobrien } 115236769Sobrien} 116236769Sobrien 117236769Sobrien/// isFullSet - Return true if this set contains all of the elements possible 118236769Sobrien/// for this data-type 119236769Sobrienbool ConstantRange::isFullSet() const { 120236769Sobrien return Lower == Upper && Lower.isMaxValue(); 121236769Sobrien} 122236769Sobrien 123236769Sobrien/// isEmptySet - Return true if this set contains no members. 124236769Sobrien/// 125236769Sobrienbool ConstantRange::isEmptySet() const { 126236769Sobrien return Lower == Upper && Lower.isMinValue(); 127236769Sobrien} 128236769Sobrien 129236769Sobrien/// isWrappedSet - Return true if this set wraps around the top of the range, 130236769Sobrien/// for example: [100, 8) 131236769Sobrien/// 132236769Sobrienbool ConstantRange::isWrappedSet() const { 133236769Sobrien return Lower.ugt(Upper); 134236769Sobrien} 135236769Sobrien 136236769Sobrien/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of 137236769Sobrien/// its bitwidth, for example: i8 [120, 140). 138236769Sobrien/// 139236769Sobrienbool ConstantRange::isSignWrappedSet() const { 140236769Sobrien return contains(APInt::getSignedMaxValue(getBitWidth())) && 141236769Sobrien contains(APInt::getSignedMinValue(getBitWidth())); 142236769Sobrien} 143236769Sobrien 144236769Sobrien/// getSetSize - Return the number of elements in this set. 145236769Sobrien/// 146236769SobrienAPInt ConstantRange::getSetSize() const { 147236769Sobrien if (isFullSet()) { 148236769Sobrien APInt Size(getBitWidth()+1, 0); 149236769Sobrien Size.setBit(getBitWidth()); 150236769Sobrien return Size; 151236769Sobrien } 152236769Sobrien 153236769Sobrien // This is also correct for wrapped sets. 154236769Sobrien return (Upper - Lower).zext(getBitWidth()+1); 155236769Sobrien} 156236769Sobrien 157236769Sobrien/// getUnsignedMax - Return the largest unsigned value contained in the 158236769Sobrien/// ConstantRange. 159236769Sobrien/// 160236769SobrienAPInt ConstantRange::getUnsignedMax() const { 161236769Sobrien if (isFullSet() || isWrappedSet()) 162236769Sobrien return APInt::getMaxValue(getBitWidth()); 163236769Sobrien return getUpper() - 1; 164236769Sobrien} 165236769Sobrien 166236769Sobrien/// getUnsignedMin - Return the smallest unsigned value contained in the 167236769Sobrien/// ConstantRange. 168236769Sobrien/// 169236769SobrienAPInt ConstantRange::getUnsignedMin() const { 170236769Sobrien if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 171236769Sobrien return APInt::getMinValue(getBitWidth()); 172236769Sobrien return getLower(); 173236769Sobrien} 174236769Sobrien 175236769Sobrien/// getSignedMax - Return the largest signed value contained in the 176236769Sobrien/// ConstantRange. 177236769Sobrien/// 178236769SobrienAPInt ConstantRange::getSignedMax() const { 179236769Sobrien APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 180236769Sobrien if (!isWrappedSet()) { 181236769Sobrien if (getLower().sle(getUpper() - 1)) 182236769Sobrien return getUpper() - 1; 183236769Sobrien return SignedMax; 184236769Sobrien } 185236769Sobrien if (getLower().isNegative() == getUpper().isNegative()) 186236769Sobrien return SignedMax; 187236769Sobrien return getUpper() - 1; 188236769Sobrien} 189236769Sobrien 190236769Sobrien/// getSignedMin - Return the smallest signed value contained in the 191236769Sobrien/// ConstantRange. 192236769Sobrien/// 193236769SobrienAPInt ConstantRange::getSignedMin() const { 194236769Sobrien APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 195236769Sobrien if (!isWrappedSet()) { 196236769Sobrien if (getLower().sle(getUpper() - 1)) 197236769Sobrien return getLower(); 198236769Sobrien return SignedMin; 199236769Sobrien } 200236769Sobrien if ((getUpper() - 1).slt(getLower())) { 201236769Sobrien if (getUpper() != SignedMin) 202236769Sobrien return SignedMin; 203236769Sobrien } 204236769Sobrien return getLower(); 205236769Sobrien} 206236769Sobrien 207236769Sobrien/// contains - Return true if the specified value is in the set. 208236769Sobrien/// 209236769Sobrienbool ConstantRange::contains(const APInt &V) const { 210236769Sobrien if (Lower == Upper) 211236769Sobrien return isFullSet(); 212236769Sobrien 213236769Sobrien if (!isWrappedSet()) 214236769Sobrien return Lower.ule(V) && V.ult(Upper); 215236769Sobrien return Lower.ule(V) || V.ult(Upper); 216236769Sobrien} 217236769Sobrien 218236769Sobrien/// contains - Return true if the argument is a subset of this range. 219236769Sobrien/// Two equal sets contain each other. The empty set contained by all other 220236769Sobrien/// sets. 221236769Sobrien/// 222236769Sobrienbool ConstantRange::contains(const ConstantRange &Other) const { 223236769Sobrien if (isFullSet() || Other.isEmptySet()) return true; 224236769Sobrien if (isEmptySet() || Other.isFullSet()) return false; 225236769Sobrien 226236769Sobrien if (!isWrappedSet()) { 227236769Sobrien if (Other.isWrappedSet()) 228236769Sobrien return false; 229236769Sobrien 230236769Sobrien return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 231236769Sobrien } 232236769Sobrien 233236769Sobrien if (!Other.isWrappedSet()) 234236769Sobrien return Other.getUpper().ule(Upper) || 235236769Sobrien Lower.ule(Other.getLower()); 236236769Sobrien 237236769Sobrien return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 238236769Sobrien} 239236769Sobrien 240236769Sobrien/// subtract - Subtract the specified constant from the endpoints of this 241236769Sobrien/// constant range. 242236769SobrienConstantRange ConstantRange::subtract(const APInt &Val) const { 243236769Sobrien assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 244236769Sobrien // If the set is empty or full, don't modify the endpoints. 245236769Sobrien if (Lower == Upper) 246236769Sobrien return *this; 247236769Sobrien return ConstantRange(Lower - Val, Upper - Val); 248236769Sobrien} 249236769Sobrien 250236769Sobrien/// \brief Subtract the specified range from this range (aka relative complement 251236769Sobrien/// of the sets). 252236769SobrienConstantRange ConstantRange::difference(const ConstantRange &CR) const { 253236769Sobrien return intersectWith(CR.inverse()); 254236769Sobrien} 255236769Sobrien 256236769Sobrien/// intersectWith - Return the range that results from the intersection of this 257236769Sobrien/// range with another range. The resultant range is guaranteed to include all 258236769Sobrien/// elements contained in both input ranges, and to have the smallest possible 259236769Sobrien/// set size that does so. Because there may be two intersections with the 260236769Sobrien/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 261236769SobrienConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 262236769Sobrien assert(getBitWidth() == CR.getBitWidth() && 263236769Sobrien "ConstantRange types don't agree!"); 264236769Sobrien 265236769Sobrien // Handle common cases. 266236769Sobrien if ( isEmptySet() || CR.isFullSet()) return *this; 267236769Sobrien if (CR.isEmptySet() || isFullSet()) return CR; 268236769Sobrien 269236769Sobrien if (!isWrappedSet() && CR.isWrappedSet()) 270236769Sobrien return CR.intersectWith(*this); 271236769Sobrien 272236769Sobrien if (!isWrappedSet() && !CR.isWrappedSet()) { 273236769Sobrien if (Lower.ult(CR.Lower)) { 274236769Sobrien if (Upper.ule(CR.Lower)) 275236769Sobrien return ConstantRange(getBitWidth(), false); 276236769Sobrien 277236769Sobrien if (Upper.ult(CR.Upper)) 278236769Sobrien return ConstantRange(CR.Lower, Upper); 279236769Sobrien 280236769Sobrien return CR; 281236769Sobrien } 282236769Sobrien if (Upper.ult(CR.Upper)) 283236769Sobrien return *this; 284236769Sobrien 285236769Sobrien if (Lower.ult(CR.Upper)) 286236769Sobrien return ConstantRange(Lower, CR.Upper); 287236769Sobrien 288236769Sobrien return ConstantRange(getBitWidth(), false); 289236769Sobrien } 290236769Sobrien 291236769Sobrien if (isWrappedSet() && !CR.isWrappedSet()) { 292236769Sobrien if (CR.Lower.ult(Upper)) { 293236769Sobrien if (CR.Upper.ult(Upper)) 294236769Sobrien return CR; 295236769Sobrien 296236769Sobrien if (CR.Upper.ule(Lower)) 297236769Sobrien return ConstantRange(CR.Lower, Upper); 298236769Sobrien 299236769Sobrien if (getSetSize().ult(CR.getSetSize())) 300236769Sobrien return *this; 301236769Sobrien return CR; 302236769Sobrien } 303236769Sobrien if (CR.Lower.ult(Lower)) { 304236769Sobrien if (CR.Upper.ule(Lower)) 305236769Sobrien return ConstantRange(getBitWidth(), false); 306236769Sobrien 307236769Sobrien return ConstantRange(Lower, CR.Upper); 308236769Sobrien } 309236769Sobrien return CR; 310236769Sobrien } 311236769Sobrien 312236769Sobrien if (CR.Upper.ult(Upper)) { 313236769Sobrien if (CR.Lower.ult(Upper)) { 314236769Sobrien if (getSetSize().ult(CR.getSetSize())) 315236769Sobrien return *this; 316236769Sobrien return CR; 317236769Sobrien } 318236769Sobrien 319236769Sobrien if (CR.Lower.ult(Lower)) 320236769Sobrien return ConstantRange(Lower, CR.Upper); 321236769Sobrien 322236769Sobrien return CR; 323236769Sobrien } 324236769Sobrien if (CR.Upper.ule(Lower)) { 325236769Sobrien if (CR.Lower.ult(Lower)) 326236769Sobrien return *this; 327236769Sobrien 328236769Sobrien return ConstantRange(CR.Lower, Upper); 329236769Sobrien } 330236769Sobrien if (getSetSize().ult(CR.getSetSize())) 331236769Sobrien return *this; 332236769Sobrien return CR; 333236769Sobrien} 334236769Sobrien 335236769Sobrien 336236769Sobrien/// unionWith - Return the range that results from the union of this range with 337236769Sobrien/// another range. The resultant range is guaranteed to include the elements of 338236769Sobrien/// both sets, but may contain more. For example, [3, 9) union [12,15) is 339236769Sobrien/// [3, 15), which includes 9, 10, and 11, which were not included in either 340236769Sobrien/// set before. 341236769Sobrien/// 342236769SobrienConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 343236769Sobrien assert(getBitWidth() == CR.getBitWidth() && 344236769Sobrien "ConstantRange types don't agree!"); 345236769Sobrien 346236769Sobrien if ( isFullSet() || CR.isEmptySet()) return *this; 347236769Sobrien if (CR.isFullSet() || isEmptySet()) return CR; 348236769Sobrien 349236769Sobrien if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 350236769Sobrien 351236769Sobrien if (!isWrappedSet() && !CR.isWrappedSet()) { 352236769Sobrien if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 353236769Sobrien // If the two ranges are disjoint, find the smaller gap and bridge it. 354236769Sobrien APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 355236769Sobrien if (d1.ult(d2)) 356236769Sobrien return ConstantRange(Lower, CR.Upper); 357236769Sobrien return ConstantRange(CR.Lower, Upper); 358236769Sobrien } 359236769Sobrien 360236769Sobrien APInt L = Lower, U = Upper; 361236769Sobrien if (CR.Lower.ult(L)) 362236769Sobrien L = CR.Lower; 363236769Sobrien if ((CR.Upper - 1).ugt(U - 1)) 364236769Sobrien U = CR.Upper; 365236769Sobrien 366236769Sobrien if (L == 0 && U == 0) 367236769Sobrien return ConstantRange(getBitWidth()); 368236769Sobrien 369236769Sobrien return ConstantRange(L, U); 370236769Sobrien } 371236769Sobrien 372236769Sobrien if (!CR.isWrappedSet()) { 373236769Sobrien // ------U L----- and ------U L----- : this 374236769Sobrien // L--U L--U : CR 375236769Sobrien if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 376236769Sobrien return *this; 377236769Sobrien 378236769Sobrien // ------U L----- : this 379236769Sobrien // L---------U : CR 380236769Sobrien if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 381236769Sobrien return ConstantRange(getBitWidth()); 382236769Sobrien 383236769Sobrien // ----U L---- : this 384236769Sobrien // L---U : CR 385236769Sobrien // <d1> <d2> 386236769Sobrien if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 387236769Sobrien APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 388236769Sobrien if (d1.ult(d2)) 389236769Sobrien return ConstantRange(Lower, CR.Upper); 390236769Sobrien return ConstantRange(CR.Lower, Upper); 391236769Sobrien } 392236769Sobrien 393236769Sobrien // ----U L----- : this 394236769Sobrien // L----U : CR 395236769Sobrien if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 396236769Sobrien return ConstantRange(CR.Lower, Upper); 397236769Sobrien 398236769Sobrien // ------U L---- : this 399236769Sobrien // L-----U : CR 400236769Sobrien assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && 401236769Sobrien "ConstantRange::unionWith missed a case with one range wrapped"); 402236769Sobrien return ConstantRange(Lower, CR.Upper); 403236769Sobrien } 404236769Sobrien 405236769Sobrien // ------U L---- and ------U L---- : this 406236769Sobrien // -U L----------- and ------------U L : CR 407236769Sobrien if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 408236769Sobrien return ConstantRange(getBitWidth()); 409236769Sobrien 410236769Sobrien APInt L = Lower, U = Upper; 411236769Sobrien if (CR.Upper.ugt(U)) 412236769Sobrien U = CR.Upper; 413236769Sobrien if (CR.Lower.ult(L)) 414236769Sobrien L = CR.Lower; 415236769Sobrien 416236769Sobrien return ConstantRange(L, U); 417236769Sobrien} 418236769Sobrien 419236769Sobrien/// zeroExtend - Return a new range in the specified integer type, which must 420236769Sobrien/// be strictly larger than the current type. The returned range will 421236769Sobrien/// correspond to the possible range of values as if the source range had been 422236769Sobrien/// zero extended. 423236769SobrienConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 424236769Sobrien if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 425236769Sobrien 426236769Sobrien unsigned SrcTySize = getBitWidth(); 427236769Sobrien assert(SrcTySize < DstTySize && "Not a value extension"); 428236769Sobrien if (isFullSet() || isWrappedSet()) { 429236769Sobrien // Change into [0, 1 << src bit width) 430236769Sobrien APInt LowerExt(DstTySize, 0); 431236769Sobrien if (!Upper) // special case: [X, 0) -- not really wrapping around 432236769Sobrien LowerExt = Lower.zext(DstTySize); 433236769Sobrien return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize)); 434236769Sobrien } 435236769Sobrien 436236769Sobrien return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); 437236769Sobrien} 438236769Sobrien 439236769Sobrien/// signExtend - Return a new range in the specified integer type, which must 440236769Sobrien/// be strictly larger than the current type. The returned range will 441236769Sobrien/// correspond to the possible range of values as if the source range had been 442236769Sobrien/// sign extended. 443236769SobrienConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 444236769Sobrien if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 445236769Sobrien 446236769Sobrien unsigned SrcTySize = getBitWidth(); 447236769Sobrien assert(SrcTySize < DstTySize && "Not a value extension"); 448236769Sobrien 449236769Sobrien // special case: [X, INT_MIN) -- not really wrapping around 450236769Sobrien if (Upper.isMinSignedValue()) 451236769Sobrien return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize)); 452236769Sobrien 453236769Sobrien if (isFullSet() || isSignWrappedSet()) { 454236769Sobrien return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 455236769Sobrien APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 456236769Sobrien } 457236769Sobrien 458236769Sobrien return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); 459236769Sobrien} 460236769Sobrien 461236769Sobrien/// truncate - Return a new range in the specified integer type, which must be 462236769Sobrien/// strictly smaller than the current type. The returned range will 463236769Sobrien/// correspond to the possible range of values as if the source range had been 464236769Sobrien/// truncated to the specified type. 465236769SobrienConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 466236769Sobrien assert(getBitWidth() > DstTySize && "Not a value truncation"); 467236769Sobrien if (isEmptySet()) 468236769Sobrien return ConstantRange(DstTySize, /*isFullSet=*/false); 469236769Sobrien if (isFullSet()) 470236769Sobrien return ConstantRange(DstTySize, /*isFullSet=*/true); 471236769Sobrien 472236769Sobrien APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth()); 473236769Sobrien APInt MaxBitValue(getBitWidth(), 0); 474236769Sobrien MaxBitValue.setBit(DstTySize); 475236769Sobrien 476236769Sobrien APInt LowerDiv(Lower), UpperDiv(Upper); 477236769Sobrien ConstantRange Union(DstTySize, /*isFullSet=*/false); 478236769Sobrien 479236769Sobrien // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] 480236769Sobrien // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and 481236769Sobrien // then we do the union with [MaxValue, Upper) 482236769Sobrien if (isWrappedSet()) { 483236769Sobrien // if Upper is greater than Max Value, it covers the whole truncated range. 484236769Sobrien if (Upper.uge(MaxValue)) 485236769Sobrien return ConstantRange(DstTySize, /*isFullSet=*/true); 486236769Sobrien 487236769Sobrien Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); 488236769Sobrien UpperDiv = APInt::getMaxValue(getBitWidth()); 489236769Sobrien 490236769Sobrien // Union covers the MaxValue case, so return if the remaining range is just 491236769Sobrien // MaxValue. 492236769Sobrien if (LowerDiv == UpperDiv) 493236769Sobrien return Union; 494236769Sobrien } 495236769Sobrien 496236769Sobrien // Chop off the most significant bits that are past the destination bitwidth. 497236769Sobrien if (LowerDiv.uge(MaxValue)) { 498236769Sobrien APInt Div(getBitWidth(), 0); 499236769Sobrien APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv); 500236769Sobrien UpperDiv = UpperDiv - MaxBitValue * Div; 501236769Sobrien } 502236769Sobrien 503236769Sobrien if (UpperDiv.ule(MaxValue)) 504236769Sobrien return ConstantRange(LowerDiv.trunc(DstTySize), 505236769Sobrien UpperDiv.trunc(DstTySize)).unionWith(Union); 506236769Sobrien 507236769Sobrien // The truncated value wrapps around. Check if we can do better than fullset. 508236769Sobrien APInt UpperModulo = UpperDiv - MaxBitValue; 509236769Sobrien if (UpperModulo.ult(LowerDiv)) 510236769Sobrien return ConstantRange(LowerDiv.trunc(DstTySize), 511236769Sobrien UpperModulo.trunc(DstTySize)).unionWith(Union); 512236769Sobrien 513236769Sobrien return ConstantRange(DstTySize, /*isFullSet=*/true); 514236769Sobrien} 515236769Sobrien 516236769Sobrien/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 517236769Sobrien/// value is zero extended, truncated, or left alone to make it that width. 518236769SobrienConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 519236769Sobrien unsigned SrcTySize = getBitWidth(); 520236769Sobrien if (SrcTySize > DstTySize) 521236769Sobrien return truncate(DstTySize); 522236769Sobrien if (SrcTySize < DstTySize) 523236769Sobrien return zeroExtend(DstTySize); 524236769Sobrien return *this; 525236769Sobrien} 526236769Sobrien 527236769Sobrien/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 528236769Sobrien/// value is sign extended, truncated, or left alone to make it that width. 529236769SobrienConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 530236769Sobrien unsigned SrcTySize = getBitWidth(); 531236769Sobrien if (SrcTySize > DstTySize) 532236769Sobrien return truncate(DstTySize); 533236769Sobrien if (SrcTySize < DstTySize) 534236769Sobrien return signExtend(DstTySize); 535236769Sobrien return *this; 536236769Sobrien} 537236769Sobrien 538236769SobrienConstantRange 539236769SobrienConstantRange::add(const ConstantRange &Other) const { 540236769Sobrien if (isEmptySet() || Other.isEmptySet()) 541236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 542236769Sobrien if (isFullSet() || Other.isFullSet()) 543236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 544236769Sobrien 545236769Sobrien APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 546236769Sobrien APInt NewLower = getLower() + Other.getLower(); 547236769Sobrien APInt NewUpper = getUpper() + Other.getUpper() - 1; 548236769Sobrien if (NewLower == NewUpper) 549236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 550236769Sobrien 551236769Sobrien ConstantRange X = ConstantRange(NewLower, NewUpper); 552236769Sobrien if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 553236769Sobrien // We've wrapped, therefore, full set. 554236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 555236769Sobrien 556236769Sobrien return X; 557236769Sobrien} 558236769Sobrien 559236769SobrienConstantRange 560236769SobrienConstantRange::sub(const ConstantRange &Other) const { 561236769Sobrien if (isEmptySet() || Other.isEmptySet()) 562236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 563236769Sobrien if (isFullSet() || Other.isFullSet()) 564236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 565236769Sobrien 566236769Sobrien APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 567236769Sobrien APInt NewLower = getLower() - Other.getUpper() + 1; 568236769Sobrien APInt NewUpper = getUpper() - Other.getLower(); 569236769Sobrien if (NewLower == NewUpper) 570236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 571236769Sobrien 572236769Sobrien ConstantRange X = ConstantRange(NewLower, NewUpper); 573236769Sobrien if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 574236769Sobrien // We've wrapped, therefore, full set. 575236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 576236769Sobrien 577236769Sobrien return X; 578236769Sobrien} 579236769Sobrien 580236769SobrienConstantRange 581236769SobrienConstantRange::multiply(const ConstantRange &Other) const { 582236769Sobrien // TODO: If either operand is a single element and the multiply is known to 583236769Sobrien // be non-wrapping, round the result min and max value to the appropriate 584236769Sobrien // multiple of that element. If wrapping is possible, at least adjust the 585236769Sobrien // range according to the greatest power-of-two factor of the single element. 586236769Sobrien 587236769Sobrien if (isEmptySet() || Other.isEmptySet()) 588236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 589236769Sobrien 590236769Sobrien APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 591236769Sobrien APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 592236769Sobrien APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 593236769Sobrien APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 594236769Sobrien 595236769Sobrien ConstantRange Result_zext = ConstantRange(this_min * Other_min, 596236769Sobrien this_max * Other_max + 1); 597236769Sobrien return Result_zext.truncate(getBitWidth()); 598236769Sobrien} 599236769Sobrien 600236769SobrienConstantRange 601236769SobrienConstantRange::smax(const ConstantRange &Other) const { 602236769Sobrien // X smax Y is: range(smax(X_smin, Y_smin), 603236769Sobrien // smax(X_smax, Y_smax)) 604236769Sobrien if (isEmptySet() || Other.isEmptySet()) 605236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 606236769Sobrien APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 607236769Sobrien APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 608236769Sobrien if (NewU == NewL) 609236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 610236769Sobrien return ConstantRange(NewL, NewU); 611236769Sobrien} 612236769Sobrien 613236769SobrienConstantRange 614236769SobrienConstantRange::umax(const ConstantRange &Other) const { 615236769Sobrien // X umax Y is: range(umax(X_umin, Y_umin), 616236769Sobrien // umax(X_umax, Y_umax)) 617236769Sobrien if (isEmptySet() || Other.isEmptySet()) 618236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 619236769Sobrien APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 620236769Sobrien APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 621236769Sobrien if (NewU == NewL) 622236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 623236769Sobrien return ConstantRange(NewL, NewU); 624236769Sobrien} 625236769Sobrien 626236769SobrienConstantRange 627236769SobrienConstantRange::udiv(const ConstantRange &RHS) const { 628236769Sobrien if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 629236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 630236769Sobrien if (RHS.isFullSet()) 631236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 632236769Sobrien 633236769Sobrien APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 634236769Sobrien 635236769Sobrien APInt RHS_umin = RHS.getUnsignedMin(); 636236769Sobrien if (RHS_umin == 0) { 637236769Sobrien // We want the lowest value in RHS excluding zero. Usually that would be 1 638236769Sobrien // except for a range in the form of [X, 1) in which case it would be X. 639236769Sobrien if (RHS.getUpper() == 1) 640236769Sobrien RHS_umin = RHS.getLower(); 641236769Sobrien else 642236769Sobrien RHS_umin = APInt(getBitWidth(), 1); 643236769Sobrien } 644236769Sobrien 645236769Sobrien APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 646236769Sobrien 647236769Sobrien // If the LHS is Full and the RHS is a wrapped interval containing 1 then 648236769Sobrien // this could occur. 649236769Sobrien if (Lower == Upper) 650236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 651236769Sobrien 652236769Sobrien return ConstantRange(Lower, Upper); 653236769Sobrien} 654236769Sobrien 655236769SobrienConstantRange 656236769SobrienConstantRange::binaryAnd(const ConstantRange &Other) const { 657236769Sobrien if (isEmptySet() || Other.isEmptySet()) 658236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 659236769Sobrien 660236769Sobrien // TODO: replace this with something less conservative 661236769Sobrien 662236769Sobrien APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); 663236769Sobrien if (umin.isAllOnesValue()) 664236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 665236769Sobrien return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1); 666236769Sobrien} 667236769Sobrien 668236769SobrienConstantRange 669236769SobrienConstantRange::binaryOr(const ConstantRange &Other) const { 670236769Sobrien if (isEmptySet() || Other.isEmptySet()) 671236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 672236769Sobrien 673236769Sobrien // TODO: replace this with something less conservative 674236769Sobrien 675236769Sobrien APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 676236769Sobrien if (umax.isMinValue()) 677236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 678236769Sobrien return ConstantRange(umax, APInt::getNullValue(getBitWidth())); 679236769Sobrien} 680236769Sobrien 681236769SobrienConstantRange 682236769SobrienConstantRange::shl(const ConstantRange &Other) const { 683236769Sobrien if (isEmptySet() || Other.isEmptySet()) 684236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 685236769Sobrien 686236769Sobrien APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); 687236769Sobrien APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); 688236769Sobrien 689236769Sobrien // there's no overflow! 690236769Sobrien APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 691236769Sobrien if (Zeros.ugt(Other.getUnsignedMax())) 692236769Sobrien return ConstantRange(min, max + 1); 693236769Sobrien 694236769Sobrien // FIXME: implement the other tricky cases 695236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 696236769Sobrien} 697236769Sobrien 698236769SobrienConstantRange 699236769SobrienConstantRange::lshr(const ConstantRange &Other) const { 700236769Sobrien if (isEmptySet() || Other.isEmptySet()) 701236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 702236769Sobrien 703236769Sobrien APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()); 704236769Sobrien APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); 705236769Sobrien if (min == max + 1) 706236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 707236769Sobrien 708236769Sobrien return ConstantRange(min, max + 1); 709236769Sobrien} 710236769Sobrien 711236769SobrienConstantRange ConstantRange::inverse() const { 712236769Sobrien if (isFullSet()) 713236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/false); 714236769Sobrien if (isEmptySet()) 715236769Sobrien return ConstantRange(getBitWidth(), /*isFullSet=*/true); 716236769Sobrien return ConstantRange(Upper, Lower); 717236769Sobrien} 718236769Sobrien 719236769Sobrien/// print - Print out the bounds to a stream... 720236769Sobrien/// 721236769Sobrienvoid ConstantRange::print(raw_ostream &OS) const { 722236769Sobrien if (isFullSet()) 723236769Sobrien OS << "full-set"; 724236769Sobrien else if (isEmptySet()) 725236769Sobrien OS << "empty-set"; 726236769Sobrien else 727236769Sobrien OS << "[" << Lower << "," << Upper << ")"; 728236769Sobrien} 729236769Sobrien 730236769Sobrien/// dump - Allow printing from a debugger easily... 731236769Sobrien/// 732236769Sobrienvoid ConstantRange::dump() const { 733236769Sobrien print(dbgs()); 734236769Sobrien} 735236769Sobrien