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/IR/InstrTypes.h" 25#include "llvm/Support/ConstantRange.h" 26#include "llvm/Support/Debug.h" 27#include "llvm/Support/raw_ostream.h" 28using namespace llvm; 29 30/// Initialize a full (the default) or empty set for the specified type. 31/// 32ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { 33 if (Full) 34 Lower = Upper = APInt::getMaxValue(BitWidth); 35 else 36 Lower = Upper = APInt::getMinValue(BitWidth); 37} 38 39/// Initialize a range to hold the single specified value. 40/// 41ConstantRange::ConstantRange(APIntMoveTy V) 42 : Lower(llvm_move(V)), Upper(Lower + 1) {} 43 44ConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U) 45 : Lower(llvm_move(L)), Upper(llvm_move(U)) { 46 assert(Lower.getBitWidth() == Upper.getBitWidth() && 47 "ConstantRange with unequal bit widths"); 48 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && 49 "Lower == Upper, but they aren't min or max value!"); 50} 51 52ConstantRange ConstantRange::makeICmpRegion(unsigned Pred, 53 const ConstantRange &CR) { 54 if (CR.isEmptySet()) 55 return CR; 56 57 uint32_t W = CR.getBitWidth(); 58 switch (Pred) { 59 default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()"); 60 case CmpInst::ICMP_EQ: 61 return CR; 62 case CmpInst::ICMP_NE: 63 if (CR.isSingleElement()) 64 return ConstantRange(CR.getUpper(), CR.getLower()); 65 return ConstantRange(W); 66 case CmpInst::ICMP_ULT: { 67 APInt UMax(CR.getUnsignedMax()); 68 if (UMax.isMinValue()) 69 return ConstantRange(W, /* empty */ false); 70 return ConstantRange(APInt::getMinValue(W), UMax); 71 } 72 case CmpInst::ICMP_SLT: { 73 APInt SMax(CR.getSignedMax()); 74 if (SMax.isMinSignedValue()) 75 return ConstantRange(W, /* empty */ false); 76 return ConstantRange(APInt::getSignedMinValue(W), SMax); 77 } 78 case CmpInst::ICMP_ULE: { 79 APInt UMax(CR.getUnsignedMax()); 80 if (UMax.isMaxValue()) 81 return ConstantRange(W); 82 return ConstantRange(APInt::getMinValue(W), UMax + 1); 83 } 84 case CmpInst::ICMP_SLE: { 85 APInt SMax(CR.getSignedMax()); 86 if (SMax.isMaxSignedValue()) 87 return ConstantRange(W); 88 return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); 89 } 90 case CmpInst::ICMP_UGT: { 91 APInt UMin(CR.getUnsignedMin()); 92 if (UMin.isMaxValue()) 93 return ConstantRange(W, /* empty */ false); 94 return ConstantRange(UMin + 1, APInt::getNullValue(W)); 95 } 96 case CmpInst::ICMP_SGT: { 97 APInt SMin(CR.getSignedMin()); 98 if (SMin.isMaxSignedValue()) 99 return ConstantRange(W, /* empty */ false); 100 return ConstantRange(SMin + 1, APInt::getSignedMinValue(W)); 101 } 102 case CmpInst::ICMP_UGE: { 103 APInt UMin(CR.getUnsignedMin()); 104 if (UMin.isMinValue()) 105 return ConstantRange(W); 106 return ConstantRange(UMin, APInt::getNullValue(W)); 107 } 108 case CmpInst::ICMP_SGE: { 109 APInt SMin(CR.getSignedMin()); 110 if (SMin.isMinSignedValue()) 111 return ConstantRange(W); 112 return ConstantRange(SMin, APInt::getSignedMinValue(W)); 113 } 114 } 115} 116 117/// isFullSet - Return true if this set contains all of the elements possible 118/// for this data-type 119bool ConstantRange::isFullSet() const { 120 return Lower == Upper && Lower.isMaxValue(); 121} 122 123/// isEmptySet - Return true if this set contains no members. 124/// 125bool ConstantRange::isEmptySet() const { 126 return Lower == Upper && Lower.isMinValue(); 127} 128 129/// isWrappedSet - Return true if this set wraps around the top of the range, 130/// for example: [100, 8) 131/// 132bool ConstantRange::isWrappedSet() const { 133 return Lower.ugt(Upper); 134} 135 136/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of 137/// its bitwidth, for example: i8 [120, 140). 138/// 139bool ConstantRange::isSignWrappedSet() const { 140 return contains(APInt::getSignedMaxValue(getBitWidth())) && 141 contains(APInt::getSignedMinValue(getBitWidth())); 142} 143 144/// getSetSize - Return the number of elements in this set. 145/// 146APInt ConstantRange::getSetSize() const { 147 if (isEmptySet()) 148 return APInt(getBitWidth()+1, 0); 149 150 if (isFullSet()) { 151 APInt Size(getBitWidth()+1, 0); 152 Size.setBit(getBitWidth()); 153 return Size; 154 } 155 156 // This is also correct for wrapped sets. 157 return (Upper - Lower).zext(getBitWidth()+1); 158} 159 160/// getUnsignedMax - Return the largest unsigned value contained in the 161/// ConstantRange. 162/// 163APInt ConstantRange::getUnsignedMax() const { 164 if (isFullSet() || isWrappedSet()) 165 return APInt::getMaxValue(getBitWidth()); 166 return getUpper() - 1; 167} 168 169/// getUnsignedMin - Return the smallest unsigned value contained in the 170/// ConstantRange. 171/// 172APInt ConstantRange::getUnsignedMin() const { 173 if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 174 return APInt::getMinValue(getBitWidth()); 175 return getLower(); 176} 177 178/// getSignedMax - Return the largest signed value contained in the 179/// ConstantRange. 180/// 181APInt ConstantRange::getSignedMax() const { 182 APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 183 if (!isWrappedSet()) { 184 if (getLower().sle(getUpper() - 1)) 185 return getUpper() - 1; 186 return SignedMax; 187 } 188 if (getLower().isNegative() == getUpper().isNegative()) 189 return SignedMax; 190 return getUpper() - 1; 191} 192 193/// getSignedMin - Return the smallest signed value contained in the 194/// ConstantRange. 195/// 196APInt ConstantRange::getSignedMin() const { 197 APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 198 if (!isWrappedSet()) { 199 if (getLower().sle(getUpper() - 1)) 200 return getLower(); 201 return SignedMin; 202 } 203 if ((getUpper() - 1).slt(getLower())) { 204 if (getUpper() != SignedMin) 205 return SignedMin; 206 } 207 return getLower(); 208} 209 210/// contains - Return true if the specified value is in the set. 211/// 212bool ConstantRange::contains(const APInt &V) const { 213 if (Lower == Upper) 214 return isFullSet(); 215 216 if (!isWrappedSet()) 217 return Lower.ule(V) && V.ult(Upper); 218 return Lower.ule(V) || V.ult(Upper); 219} 220 221/// contains - Return true if the argument is a subset of this range. 222/// Two equal sets contain each other. The empty set contained by all other 223/// sets. 224/// 225bool ConstantRange::contains(const ConstantRange &Other) const { 226 if (isFullSet() || Other.isEmptySet()) return true; 227 if (isEmptySet() || Other.isFullSet()) return false; 228 229 if (!isWrappedSet()) { 230 if (Other.isWrappedSet()) 231 return false; 232 233 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 234 } 235 236 if (!Other.isWrappedSet()) 237 return Other.getUpper().ule(Upper) || 238 Lower.ule(Other.getLower()); 239 240 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 241} 242 243/// subtract - Subtract the specified constant from the endpoints of this 244/// constant range. 245ConstantRange ConstantRange::subtract(const APInt &Val) const { 246 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 247 // If the set is empty or full, don't modify the endpoints. 248 if (Lower == Upper) 249 return *this; 250 return ConstantRange(Lower - Val, Upper - Val); 251} 252 253/// \brief Subtract the specified range from this range (aka relative complement 254/// of the sets). 255ConstantRange ConstantRange::difference(const ConstantRange &CR) const { 256 return intersectWith(CR.inverse()); 257} 258 259/// intersectWith - Return the range that results from the intersection of this 260/// range with another range. The resultant range is guaranteed to include all 261/// elements contained in both input ranges, and to have the smallest possible 262/// set size that does so. Because there may be two intersections with the 263/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 264ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 265 assert(getBitWidth() == CR.getBitWidth() && 266 "ConstantRange types don't agree!"); 267 268 // Handle common cases. 269 if ( isEmptySet() || CR.isFullSet()) return *this; 270 if (CR.isEmptySet() || isFullSet()) return CR; 271 272 if (!isWrappedSet() && CR.isWrappedSet()) 273 return CR.intersectWith(*this); 274 275 if (!isWrappedSet() && !CR.isWrappedSet()) { 276 if (Lower.ult(CR.Lower)) { 277 if (Upper.ule(CR.Lower)) 278 return ConstantRange(getBitWidth(), false); 279 280 if (Upper.ult(CR.Upper)) 281 return ConstantRange(CR.Lower, Upper); 282 283 return CR; 284 } 285 if (Upper.ult(CR.Upper)) 286 return *this; 287 288 if (Lower.ult(CR.Upper)) 289 return ConstantRange(Lower, CR.Upper); 290 291 return ConstantRange(getBitWidth(), false); 292 } 293 294 if (isWrappedSet() && !CR.isWrappedSet()) { 295 if (CR.Lower.ult(Upper)) { 296 if (CR.Upper.ult(Upper)) 297 return CR; 298 299 if (CR.Upper.ule(Lower)) 300 return ConstantRange(CR.Lower, Upper); 301 302 if (getSetSize().ult(CR.getSetSize())) 303 return *this; 304 return CR; 305 } 306 if (CR.Lower.ult(Lower)) { 307 if (CR.Upper.ule(Lower)) 308 return ConstantRange(getBitWidth(), false); 309 310 return ConstantRange(Lower, CR.Upper); 311 } 312 return CR; 313 } 314 315 if (CR.Upper.ult(Upper)) { 316 if (CR.Lower.ult(Upper)) { 317 if (getSetSize().ult(CR.getSetSize())) 318 return *this; 319 return CR; 320 } 321 322 if (CR.Lower.ult(Lower)) 323 return ConstantRange(Lower, CR.Upper); 324 325 return CR; 326 } 327 if (CR.Upper.ule(Lower)) { 328 if (CR.Lower.ult(Lower)) 329 return *this; 330 331 return ConstantRange(CR.Lower, Upper); 332 } 333 if (getSetSize().ult(CR.getSetSize())) 334 return *this; 335 return CR; 336} 337 338 339/// unionWith - Return the range that results from the union of this range with 340/// another range. The resultant range is guaranteed to include the elements of 341/// both sets, but may contain more. For example, [3, 9) union [12,15) is 342/// [3, 15), which includes 9, 10, and 11, which were not included in either 343/// set before. 344/// 345ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 346 assert(getBitWidth() == CR.getBitWidth() && 347 "ConstantRange types don't agree!"); 348 349 if ( isFullSet() || CR.isEmptySet()) return *this; 350 if (CR.isFullSet() || isEmptySet()) return CR; 351 352 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 353 354 if (!isWrappedSet() && !CR.isWrappedSet()) { 355 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 356 // If the two ranges are disjoint, find the smaller gap and bridge it. 357 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 358 if (d1.ult(d2)) 359 return ConstantRange(Lower, CR.Upper); 360 return ConstantRange(CR.Lower, Upper); 361 } 362 363 APInt L = Lower, U = Upper; 364 if (CR.Lower.ult(L)) 365 L = CR.Lower; 366 if ((CR.Upper - 1).ugt(U - 1)) 367 U = CR.Upper; 368 369 if (L == 0 && U == 0) 370 return ConstantRange(getBitWidth()); 371 372 return ConstantRange(L, U); 373 } 374 375 if (!CR.isWrappedSet()) { 376 // ------U L----- and ------U L----- : this 377 // L--U L--U : CR 378 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 379 return *this; 380 381 // ------U L----- : this 382 // L---------U : CR 383 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 384 return ConstantRange(getBitWidth()); 385 386 // ----U L---- : this 387 // L---U : CR 388 // <d1> <d2> 389 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 390 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 391 if (d1.ult(d2)) 392 return ConstantRange(Lower, CR.Upper); 393 return ConstantRange(CR.Lower, Upper); 394 } 395 396 // ----U L----- : this 397 // L----U : CR 398 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 399 return ConstantRange(CR.Lower, Upper); 400 401 // ------U L---- : this 402 // L-----U : CR 403 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && 404 "ConstantRange::unionWith missed a case with one range wrapped"); 405 return ConstantRange(Lower, CR.Upper); 406 } 407 408 // ------U L---- and ------U L---- : this 409 // -U L----------- and ------------U L : CR 410 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 411 return ConstantRange(getBitWidth()); 412 413 APInt L = Lower, U = Upper; 414 if (CR.Upper.ugt(U)) 415 U = CR.Upper; 416 if (CR.Lower.ult(L)) 417 L = CR.Lower; 418 419 return ConstantRange(L, U); 420} 421 422/// zeroExtend - Return a new range in the specified integer type, which must 423/// be strictly larger than the current type. The returned range will 424/// correspond to the possible range of values as if the source range had been 425/// zero extended. 426ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 427 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 428 429 unsigned SrcTySize = getBitWidth(); 430 assert(SrcTySize < DstTySize && "Not a value extension"); 431 if (isFullSet() || isWrappedSet()) { 432 // Change into [0, 1 << src bit width) 433 APInt LowerExt(DstTySize, 0); 434 if (!Upper) // special case: [X, 0) -- not really wrapping around 435 LowerExt = Lower.zext(DstTySize); 436 return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize)); 437 } 438 439 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); 440} 441 442/// signExtend - Return a new range in the specified integer type, which must 443/// be strictly larger than the current type. The returned range will 444/// correspond to the possible range of values as if the source range had been 445/// sign extended. 446ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 447 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 448 449 unsigned SrcTySize = getBitWidth(); 450 assert(SrcTySize < DstTySize && "Not a value extension"); 451 if (isFullSet() || isSignWrappedSet()) { 452 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 453 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 454 } 455 456 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); 457} 458 459/// truncate - Return a new range in the specified integer type, which must be 460/// strictly smaller than the current type. The returned range will 461/// correspond to the possible range of values as if the source range had been 462/// truncated to the specified type. 463ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 464 assert(getBitWidth() > DstTySize && "Not a value truncation"); 465 if (isEmptySet()) 466 return ConstantRange(DstTySize, /*isFullSet=*/false); 467 if (isFullSet()) 468 return ConstantRange(DstTySize, /*isFullSet=*/true); 469 470 APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth()); 471 APInt MaxBitValue(getBitWidth(), 0); 472 MaxBitValue.setBit(DstTySize); 473 474 APInt LowerDiv(Lower), UpperDiv(Upper); 475 ConstantRange Union(DstTySize, /*isFullSet=*/false); 476 477 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] 478 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and 479 // then we do the union with [MaxValue, Upper) 480 if (isWrappedSet()) { 481 // if Upper is greater than Max Value, it covers the whole truncated range. 482 if (Upper.uge(MaxValue)) 483 return ConstantRange(DstTySize, /*isFullSet=*/true); 484 485 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); 486 UpperDiv = APInt::getMaxValue(getBitWidth()); 487 488 // Union covers the MaxValue case, so return if the remaining range is just 489 // MaxValue. 490 if (LowerDiv == UpperDiv) 491 return Union; 492 } 493 494 // Chop off the most significant bits that are past the destination bitwidth. 495 if (LowerDiv.uge(MaxValue)) { 496 APInt Div(getBitWidth(), 0); 497 APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv); 498 UpperDiv = UpperDiv - MaxBitValue * Div; 499 } 500 501 if (UpperDiv.ule(MaxValue)) 502 return ConstantRange(LowerDiv.trunc(DstTySize), 503 UpperDiv.trunc(DstTySize)).unionWith(Union); 504 505 // The truncated value wrapps around. Check if we can do better than fullset. 506 APInt UpperModulo = UpperDiv - MaxBitValue; 507 if (UpperModulo.ult(LowerDiv)) 508 return ConstantRange(LowerDiv.trunc(DstTySize), 509 UpperModulo.trunc(DstTySize)).unionWith(Union); 510 511 return ConstantRange(DstTySize, /*isFullSet=*/true); 512} 513 514/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 515/// value is zero extended, truncated, or left alone to make it that width. 516ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 517 unsigned SrcTySize = getBitWidth(); 518 if (SrcTySize > DstTySize) 519 return truncate(DstTySize); 520 if (SrcTySize < DstTySize) 521 return zeroExtend(DstTySize); 522 return *this; 523} 524 525/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 526/// value is sign extended, truncated, or left alone to make it that width. 527ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 528 unsigned SrcTySize = getBitWidth(); 529 if (SrcTySize > DstTySize) 530 return truncate(DstTySize); 531 if (SrcTySize < DstTySize) 532 return signExtend(DstTySize); 533 return *this; 534} 535 536ConstantRange 537ConstantRange::add(const ConstantRange &Other) const { 538 if (isEmptySet() || Other.isEmptySet()) 539 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 540 if (isFullSet() || Other.isFullSet()) 541 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 542 543 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 544 APInt NewLower = getLower() + Other.getLower(); 545 APInt NewUpper = getUpper() + Other.getUpper() - 1; 546 if (NewLower == NewUpper) 547 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 548 549 ConstantRange X = ConstantRange(NewLower, NewUpper); 550 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 551 // We've wrapped, therefore, full set. 552 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 553 554 return X; 555} 556 557ConstantRange 558ConstantRange::sub(const ConstantRange &Other) const { 559 if (isEmptySet() || Other.isEmptySet()) 560 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 561 if (isFullSet() || Other.isFullSet()) 562 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 563 564 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 565 APInt NewLower = getLower() - Other.getUpper() + 1; 566 APInt NewUpper = getUpper() - Other.getLower(); 567 if (NewLower == NewUpper) 568 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 569 570 ConstantRange X = ConstantRange(NewLower, NewUpper); 571 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 572 // We've wrapped, therefore, full set. 573 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 574 575 return X; 576} 577 578ConstantRange 579ConstantRange::multiply(const ConstantRange &Other) const { 580 // TODO: If either operand is a single element and the multiply is known to 581 // be non-wrapping, round the result min and max value to the appropriate 582 // multiple of that element. If wrapping is possible, at least adjust the 583 // range according to the greatest power-of-two factor of the single element. 584 585 if (isEmptySet() || Other.isEmptySet()) 586 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 587 588 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 589 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 590 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 591 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 592 593 ConstantRange Result_zext = ConstantRange(this_min * Other_min, 594 this_max * Other_max + 1); 595 return Result_zext.truncate(getBitWidth()); 596} 597 598ConstantRange 599ConstantRange::smax(const ConstantRange &Other) const { 600 // X smax Y is: range(smax(X_smin, Y_smin), 601 // smax(X_smax, Y_smax)) 602 if (isEmptySet() || Other.isEmptySet()) 603 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 604 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 605 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 606 if (NewU == NewL) 607 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 608 return ConstantRange(NewL, NewU); 609} 610 611ConstantRange 612ConstantRange::umax(const ConstantRange &Other) const { 613 // X umax Y is: range(umax(X_umin, Y_umin), 614 // umax(X_umax, Y_umax)) 615 if (isEmptySet() || Other.isEmptySet()) 616 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 617 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 618 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 619 if (NewU == NewL) 620 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 621 return ConstantRange(NewL, NewU); 622} 623 624ConstantRange 625ConstantRange::udiv(const ConstantRange &RHS) const { 626 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 627 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 628 if (RHS.isFullSet()) 629 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 630 631 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 632 633 APInt RHS_umin = RHS.getUnsignedMin(); 634 if (RHS_umin == 0) { 635 // We want the lowest value in RHS excluding zero. Usually that would be 1 636 // except for a range in the form of [X, 1) in which case it would be X. 637 if (RHS.getUpper() == 1) 638 RHS_umin = RHS.getLower(); 639 else 640 RHS_umin = APInt(getBitWidth(), 1); 641 } 642 643 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 644 645 // If the LHS is Full and the RHS is a wrapped interval containing 1 then 646 // this could occur. 647 if (Lower == Upper) 648 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 649 650 return ConstantRange(Lower, Upper); 651} 652 653ConstantRange 654ConstantRange::binaryAnd(const ConstantRange &Other) const { 655 if (isEmptySet() || Other.isEmptySet()) 656 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 657 658 // TODO: replace this with something less conservative 659 660 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); 661 if (umin.isAllOnesValue()) 662 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 663 return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1); 664} 665 666ConstantRange 667ConstantRange::binaryOr(const ConstantRange &Other) const { 668 if (isEmptySet() || Other.isEmptySet()) 669 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 670 671 // TODO: replace this with something less conservative 672 673 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 674 if (umax.isMinValue()) 675 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 676 return ConstantRange(umax, APInt::getNullValue(getBitWidth())); 677} 678 679ConstantRange 680ConstantRange::shl(const ConstantRange &Other) const { 681 if (isEmptySet() || Other.isEmptySet()) 682 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 683 684 APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); 685 APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); 686 687 // there's no overflow! 688 APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 689 if (Zeros.ugt(Other.getUnsignedMax())) 690 return ConstantRange(min, max + 1); 691 692 // FIXME: implement the other tricky cases 693 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 694} 695 696ConstantRange 697ConstantRange::lshr(const ConstantRange &Other) const { 698 if (isEmptySet() || Other.isEmptySet()) 699 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 700 701 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()); 702 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); 703 if (min == max + 1) 704 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 705 706 return ConstantRange(min, max + 1); 707} 708 709ConstantRange ConstantRange::inverse() const { 710 if (isFullSet()) 711 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 712 if (isEmptySet()) 713 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 714 return ConstantRange(Upper, Lower); 715} 716 717/// print - Print out the bounds to a stream... 718/// 719void ConstantRange::print(raw_ostream &OS) const { 720 if (isFullSet()) 721 OS << "full-set"; 722 else if (isEmptySet()) 723 OS << "empty-set"; 724 else 725 OS << "[" << Lower << "," << Upper << ")"; 726} 727 728/// dump - Allow printing from a debugger easily... 729/// 730void ConstantRange::dump() const { 731 print(dbgs()); 732} 733