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/Instruction.h" 25 #include "llvm/IR/InstrTypes.h" 26 #include "llvm/IR/Operator.h" 27 #include "llvm/IR/ConstantRange.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/raw_ostream.h" 30 using namespace llvm; 31 32 /// Initialize a full (the default) or empty set for the specified type. 33 /// 34 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) { 35 if (Full) 36 Lower = Upper = APInt::getMaxValue(BitWidth); 37 else 38 Lower = Upper = APInt::getMinValue(BitWidth); 39 } 40 41 /// Initialize a range to hold the single specified value. 42 /// 43 ConstantRange::ConstantRange(APIntMoveTy V) 44 : Lower(std::move(V)), Upper(Lower + 1) {} 45 46 ConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U) 47 : Lower(std::move(L)), Upper(std::move(U)) { 48 assert(Lower.getBitWidth() == Upper.getBitWidth() && 49 "ConstantRange with unequal bit widths"); 50 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && 51 "Lower == Upper, but they aren't min or max value!"); 52 } 53 54 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred, 55 const ConstantRange &CR) { 56 if (CR.isEmptySet()) 57 return CR; 58 59 uint32_t W = CR.getBitWidth(); 60 switch (Pred) { 61 default: 62 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()"); 63 case CmpInst::ICMP_EQ: 64 return CR; 65 case CmpInst::ICMP_NE: 66 if (CR.isSingleElement()) 67 return ConstantRange(CR.getUpper(), CR.getLower()); 68 return ConstantRange(W); 69 case CmpInst::ICMP_ULT: { 70 APInt UMax(CR.getUnsignedMax()); 71 if (UMax.isMinValue()) 72 return ConstantRange(W, /* empty */ false); 73 return ConstantRange(APInt::getMinValue(W), UMax); 74 } 75 case CmpInst::ICMP_SLT: { 76 APInt SMax(CR.getSignedMax()); 77 if (SMax.isMinSignedValue()) 78 return ConstantRange(W, /* empty */ false); 79 return ConstantRange(APInt::getSignedMinValue(W), SMax); 80 } 81 case CmpInst::ICMP_ULE: { 82 APInt UMax(CR.getUnsignedMax()); 83 if (UMax.isMaxValue()) 84 return ConstantRange(W); 85 return ConstantRange(APInt::getMinValue(W), UMax + 1); 86 } 87 case CmpInst::ICMP_SLE: { 88 APInt SMax(CR.getSignedMax()); 89 if (SMax.isMaxSignedValue()) 90 return ConstantRange(W); 91 return ConstantRange(APInt::getSignedMinValue(W), SMax + 1); 92 } 93 case CmpInst::ICMP_UGT: { 94 APInt UMin(CR.getUnsignedMin()); 95 if (UMin.isMaxValue()) 96 return ConstantRange(W, /* empty */ false); 97 return ConstantRange(UMin + 1, APInt::getNullValue(W)); 98 } 99 case CmpInst::ICMP_SGT: { 100 APInt SMin(CR.getSignedMin()); 101 if (SMin.isMaxSignedValue()) 102 return ConstantRange(W, /* empty */ false); 103 return ConstantRange(SMin + 1, APInt::getSignedMinValue(W)); 104 } 105 case CmpInst::ICMP_UGE: { 106 APInt UMin(CR.getUnsignedMin()); 107 if (UMin.isMinValue()) 108 return ConstantRange(W); 109 return ConstantRange(UMin, APInt::getNullValue(W)); 110 } 111 case CmpInst::ICMP_SGE: { 112 APInt SMin(CR.getSignedMin()); 113 if (SMin.isMinSignedValue()) 114 return ConstantRange(W); 115 return ConstantRange(SMin, APInt::getSignedMinValue(W)); 116 } 117 } 118 } 119 120 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred, 121 const ConstantRange &CR) { 122 // Follows from De-Morgan's laws: 123 // 124 // ~(~A union ~B) == A intersect B. 125 // 126 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR) 127 .inverse(); 128 } 129 130 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred, 131 const APInt &C) { 132 // Computes the exact range that is equal to both the constant ranges returned 133 // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true 134 // when RHS is a singleton such as an APInt and so the assert is valid. 135 // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion 136 // returns [0,4) but makeSatisfyICmpRegion returns [0,2). 137 // 138 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C)); 139 return makeAllowedICmpRegion(Pred, C); 140 } 141 142 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred, 143 APInt &RHS) const { 144 bool Success = false; 145 146 if (isFullSet() || isEmptySet()) { 147 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE; 148 RHS = APInt(getBitWidth(), 0); 149 Success = true; 150 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) { 151 Pred = 152 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT; 153 RHS = getUpper(); 154 Success = true; 155 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) { 156 Pred = 157 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE; 158 RHS = getLower(); 159 Success = true; 160 } 161 162 assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) && 163 "Bad result!"); 164 165 return Success; 166 } 167 168 ConstantRange 169 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, 170 const ConstantRange &Other, 171 unsigned NoWrapKind) { 172 typedef OverflowingBinaryOperator OBO; 173 174 // Computes the intersection of CR0 and CR1. It is different from 175 // intersectWith in that the ConstantRange returned will only contain elements 176 // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or 177 // not, of both X and Y). 178 auto SubsetIntersect = 179 [](const ConstantRange &CR0, const ConstantRange &CR1) { 180 return CR0.inverse().unionWith(CR1.inverse()).inverse(); 181 }; 182 183 assert(BinOp >= Instruction::BinaryOpsBegin && 184 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!"); 185 186 assert((NoWrapKind == OBO::NoSignedWrap || 187 NoWrapKind == OBO::NoUnsignedWrap || 188 NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) && 189 "NoWrapKind invalid!"); 190 191 unsigned BitWidth = Other.getBitWidth(); 192 if (BinOp != Instruction::Add) 193 // Conservative answer: empty set 194 return ConstantRange(BitWidth, false); 195 196 if (auto *C = Other.getSingleElement()) 197 if (C->isMinValue()) 198 // Full set: nothing signed / unsigned wraps when added to 0. 199 return ConstantRange(BitWidth); 200 201 ConstantRange Result(BitWidth); 202 203 if (NoWrapKind & OBO::NoUnsignedWrap) 204 Result = 205 SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth), 206 -Other.getUnsignedMax())); 207 208 if (NoWrapKind & OBO::NoSignedWrap) { 209 APInt SignedMin = Other.getSignedMin(); 210 APInt SignedMax = Other.getSignedMax(); 211 212 if (SignedMax.isStrictlyPositive()) 213 Result = SubsetIntersect( 214 Result, 215 ConstantRange(APInt::getSignedMinValue(BitWidth), 216 APInt::getSignedMinValue(BitWidth) - SignedMax)); 217 218 if (SignedMin.isNegative()) 219 Result = SubsetIntersect( 220 Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin, 221 APInt::getSignedMinValue(BitWidth))); 222 } 223 224 return Result; 225 } 226 227 /// isFullSet - Return true if this set contains all of the elements possible 228 /// for this data-type 229 bool ConstantRange::isFullSet() const { 230 return Lower == Upper && Lower.isMaxValue(); 231 } 232 233 /// isEmptySet - Return true if this set contains no members. 234 /// 235 bool ConstantRange::isEmptySet() const { 236 return Lower == Upper && Lower.isMinValue(); 237 } 238 239 /// isWrappedSet - Return true if this set wraps around the top of the range, 240 /// for example: [100, 8) 241 /// 242 bool ConstantRange::isWrappedSet() const { 243 return Lower.ugt(Upper); 244 } 245 246 /// isSignWrappedSet - Return true if this set wraps around the INT_MIN of 247 /// its bitwidth, for example: i8 [120, 140). 248 /// 249 bool ConstantRange::isSignWrappedSet() const { 250 return contains(APInt::getSignedMaxValue(getBitWidth())) && 251 contains(APInt::getSignedMinValue(getBitWidth())); 252 } 253 254 /// getSetSize - Return the number of elements in this set. 255 /// 256 APInt ConstantRange::getSetSize() const { 257 if (isFullSet()) { 258 APInt Size(getBitWidth()+1, 0); 259 Size.setBit(getBitWidth()); 260 return Size; 261 } 262 263 // This is also correct for wrapped sets. 264 return (Upper - Lower).zext(getBitWidth()+1); 265 } 266 267 /// getUnsignedMax - Return the largest unsigned value contained in the 268 /// ConstantRange. 269 /// 270 APInt ConstantRange::getUnsignedMax() const { 271 if (isFullSet() || isWrappedSet()) 272 return APInt::getMaxValue(getBitWidth()); 273 return getUpper() - 1; 274 } 275 276 /// getUnsignedMin - Return the smallest unsigned value contained in the 277 /// ConstantRange. 278 /// 279 APInt ConstantRange::getUnsignedMin() const { 280 if (isFullSet() || (isWrappedSet() && getUpper() != 0)) 281 return APInt::getMinValue(getBitWidth()); 282 return getLower(); 283 } 284 285 /// getSignedMax - Return the largest signed value contained in the 286 /// ConstantRange. 287 /// 288 APInt ConstantRange::getSignedMax() const { 289 APInt SignedMax(APInt::getSignedMaxValue(getBitWidth())); 290 if (!isWrappedSet()) { 291 if (getLower().sle(getUpper() - 1)) 292 return getUpper() - 1; 293 return SignedMax; 294 } 295 if (getLower().isNegative() == getUpper().isNegative()) 296 return SignedMax; 297 return getUpper() - 1; 298 } 299 300 /// getSignedMin - Return the smallest signed value contained in the 301 /// ConstantRange. 302 /// 303 APInt ConstantRange::getSignedMin() const { 304 APInt SignedMin(APInt::getSignedMinValue(getBitWidth())); 305 if (!isWrappedSet()) { 306 if (getLower().sle(getUpper() - 1)) 307 return getLower(); 308 return SignedMin; 309 } 310 if ((getUpper() - 1).slt(getLower())) { 311 if (getUpper() != SignedMin) 312 return SignedMin; 313 } 314 return getLower(); 315 } 316 317 /// contains - Return true if the specified value is in the set. 318 /// 319 bool ConstantRange::contains(const APInt &V) const { 320 if (Lower == Upper) 321 return isFullSet(); 322 323 if (!isWrappedSet()) 324 return Lower.ule(V) && V.ult(Upper); 325 return Lower.ule(V) || V.ult(Upper); 326 } 327 328 /// contains - Return true if the argument is a subset of this range. 329 /// Two equal sets contain each other. The empty set contained by all other 330 /// sets. 331 /// 332 bool ConstantRange::contains(const ConstantRange &Other) const { 333 if (isFullSet() || Other.isEmptySet()) return true; 334 if (isEmptySet() || Other.isFullSet()) return false; 335 336 if (!isWrappedSet()) { 337 if (Other.isWrappedSet()) 338 return false; 339 340 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 341 } 342 343 if (!Other.isWrappedSet()) 344 return Other.getUpper().ule(Upper) || 345 Lower.ule(Other.getLower()); 346 347 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 348 } 349 350 /// subtract - Subtract the specified constant from the endpoints of this 351 /// constant range. 352 ConstantRange ConstantRange::subtract(const APInt &Val) const { 353 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 354 // If the set is empty or full, don't modify the endpoints. 355 if (Lower == Upper) 356 return *this; 357 return ConstantRange(Lower - Val, Upper - Val); 358 } 359 360 /// \brief Subtract the specified range from this range (aka relative complement 361 /// of the sets). 362 ConstantRange ConstantRange::difference(const ConstantRange &CR) const { 363 return intersectWith(CR.inverse()); 364 } 365 366 /// intersectWith - Return the range that results from the intersection of this 367 /// range with another range. The resultant range is guaranteed to include all 368 /// elements contained in both input ranges, and to have the smallest possible 369 /// set size that does so. Because there may be two intersections with the 370 /// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A). 371 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const { 372 assert(getBitWidth() == CR.getBitWidth() && 373 "ConstantRange types don't agree!"); 374 375 // Handle common cases. 376 if ( isEmptySet() || CR.isFullSet()) return *this; 377 if (CR.isEmptySet() || isFullSet()) return CR; 378 379 if (!isWrappedSet() && CR.isWrappedSet()) 380 return CR.intersectWith(*this); 381 382 if (!isWrappedSet() && !CR.isWrappedSet()) { 383 if (Lower.ult(CR.Lower)) { 384 if (Upper.ule(CR.Lower)) 385 return ConstantRange(getBitWidth(), false); 386 387 if (Upper.ult(CR.Upper)) 388 return ConstantRange(CR.Lower, Upper); 389 390 return CR; 391 } 392 if (Upper.ult(CR.Upper)) 393 return *this; 394 395 if (Lower.ult(CR.Upper)) 396 return ConstantRange(Lower, CR.Upper); 397 398 return ConstantRange(getBitWidth(), false); 399 } 400 401 if (isWrappedSet() && !CR.isWrappedSet()) { 402 if (CR.Lower.ult(Upper)) { 403 if (CR.Upper.ult(Upper)) 404 return CR; 405 406 if (CR.Upper.ule(Lower)) 407 return ConstantRange(CR.Lower, Upper); 408 409 if (getSetSize().ult(CR.getSetSize())) 410 return *this; 411 return CR; 412 } 413 if (CR.Lower.ult(Lower)) { 414 if (CR.Upper.ule(Lower)) 415 return ConstantRange(getBitWidth(), false); 416 417 return ConstantRange(Lower, CR.Upper); 418 } 419 return CR; 420 } 421 422 if (CR.Upper.ult(Upper)) { 423 if (CR.Lower.ult(Upper)) { 424 if (getSetSize().ult(CR.getSetSize())) 425 return *this; 426 return CR; 427 } 428 429 if (CR.Lower.ult(Lower)) 430 return ConstantRange(Lower, CR.Upper); 431 432 return CR; 433 } 434 if (CR.Upper.ule(Lower)) { 435 if (CR.Lower.ult(Lower)) 436 return *this; 437 438 return ConstantRange(CR.Lower, Upper); 439 } 440 if (getSetSize().ult(CR.getSetSize())) 441 return *this; 442 return CR; 443 } 444 445 446 /// unionWith - Return the range that results from the union of this range with 447 /// another range. The resultant range is guaranteed to include the elements of 448 /// both sets, but may contain more. For example, [3, 9) union [12,15) is 449 /// [3, 15), which includes 9, 10, and 11, which were not included in either 450 /// set before. 451 /// 452 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { 453 assert(getBitWidth() == CR.getBitWidth() && 454 "ConstantRange types don't agree!"); 455 456 if ( isFullSet() || CR.isEmptySet()) return *this; 457 if (CR.isFullSet() || isEmptySet()) return CR; 458 459 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this); 460 461 if (!isWrappedSet() && !CR.isWrappedSet()) { 462 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) { 463 // If the two ranges are disjoint, find the smaller gap and bridge it. 464 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 465 if (d1.ult(d2)) 466 return ConstantRange(Lower, CR.Upper); 467 return ConstantRange(CR.Lower, Upper); 468 } 469 470 APInt L = Lower, U = Upper; 471 if (CR.Lower.ult(L)) 472 L = CR.Lower; 473 if ((CR.Upper - 1).ugt(U - 1)) 474 U = CR.Upper; 475 476 if (L == 0 && U == 0) 477 return ConstantRange(getBitWidth()); 478 479 return ConstantRange(L, U); 480 } 481 482 if (!CR.isWrappedSet()) { 483 // ------U L----- and ------U L----- : this 484 // L--U L--U : CR 485 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 486 return *this; 487 488 // ------U L----- : this 489 // L---------U : CR 490 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 491 return ConstantRange(getBitWidth()); 492 493 // ----U L---- : this 494 // L---U : CR 495 // <d1> <d2> 496 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) { 497 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper; 498 if (d1.ult(d2)) 499 return ConstantRange(Lower, CR.Upper); 500 return ConstantRange(CR.Lower, Upper); 501 } 502 503 // ----U L----- : this 504 // L----U : CR 505 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) 506 return ConstantRange(CR.Lower, Upper); 507 508 // ------U L---- : this 509 // L-----U : CR 510 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) && 511 "ConstantRange::unionWith missed a case with one range wrapped"); 512 return ConstantRange(Lower, CR.Upper); 513 } 514 515 // ------U L---- and ------U L---- : this 516 // -U L----------- and ------------U L : CR 517 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 518 return ConstantRange(getBitWidth()); 519 520 APInt L = Lower, U = Upper; 521 if (CR.Upper.ugt(U)) 522 U = CR.Upper; 523 if (CR.Lower.ult(L)) 524 L = CR.Lower; 525 526 return ConstantRange(L, U); 527 } 528 529 /// zeroExtend - Return a new range in the specified integer type, which must 530 /// be strictly larger than the current type. The returned range will 531 /// correspond to the possible range of values as if the source range had been 532 /// zero extended. 533 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 534 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 535 536 unsigned SrcTySize = getBitWidth(); 537 assert(SrcTySize < DstTySize && "Not a value extension"); 538 if (isFullSet() || isWrappedSet()) { 539 // Change into [0, 1 << src bit width) 540 APInt LowerExt(DstTySize, 0); 541 if (!Upper) // special case: [X, 0) -- not really wrapping around 542 LowerExt = Lower.zext(DstTySize); 543 return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize)); 544 } 545 546 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); 547 } 548 549 /// signExtend - Return a new range in the specified integer type, which must 550 /// be strictly larger than the current type. The returned range will 551 /// correspond to the possible range of values as if the source range had been 552 /// sign extended. 553 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 554 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false); 555 556 unsigned SrcTySize = getBitWidth(); 557 assert(SrcTySize < DstTySize && "Not a value extension"); 558 559 // special case: [X, INT_MIN) -- not really wrapping around 560 if (Upper.isMinSignedValue()) 561 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize)); 562 563 if (isFullSet() || isSignWrappedSet()) { 564 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 565 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 566 } 567 568 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); 569 } 570 571 /// truncate - Return a new range in the specified integer type, which must be 572 /// strictly smaller than the current type. The returned range will 573 /// correspond to the possible range of values as if the source range had been 574 /// truncated to the specified type. 575 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 576 assert(getBitWidth() > DstTySize && "Not a value truncation"); 577 if (isEmptySet()) 578 return ConstantRange(DstTySize, /*isFullSet=*/false); 579 if (isFullSet()) 580 return ConstantRange(DstTySize, /*isFullSet=*/true); 581 582 APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth()); 583 APInt MaxBitValue(getBitWidth(), 0); 584 MaxBitValue.setBit(DstTySize); 585 586 APInt LowerDiv(Lower), UpperDiv(Upper); 587 ConstantRange Union(DstTySize, /*isFullSet=*/false); 588 589 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] 590 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and 591 // then we do the union with [MaxValue, Upper) 592 if (isWrappedSet()) { 593 // If Upper is greater than Max Value, it covers the whole truncated range. 594 if (Upper.uge(MaxValue)) 595 return ConstantRange(DstTySize, /*isFullSet=*/true); 596 597 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); 598 UpperDiv = APInt::getMaxValue(getBitWidth()); 599 600 // Union covers the MaxValue case, so return if the remaining range is just 601 // MaxValue. 602 if (LowerDiv == UpperDiv) 603 return Union; 604 } 605 606 // Chop off the most significant bits that are past the destination bitwidth. 607 if (LowerDiv.uge(MaxValue)) { 608 APInt Div(getBitWidth(), 0); 609 APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv); 610 UpperDiv = UpperDiv - MaxBitValue * Div; 611 } 612 613 if (UpperDiv.ule(MaxValue)) 614 return ConstantRange(LowerDiv.trunc(DstTySize), 615 UpperDiv.trunc(DstTySize)).unionWith(Union); 616 617 // The truncated value wraps around. Check if we can do better than fullset. 618 APInt UpperModulo = UpperDiv - MaxBitValue; 619 if (UpperModulo.ult(LowerDiv)) 620 return ConstantRange(LowerDiv.trunc(DstTySize), 621 UpperModulo.trunc(DstTySize)).unionWith(Union); 622 623 return ConstantRange(DstTySize, /*isFullSet=*/true); 624 } 625 626 /// zextOrTrunc - make this range have the bit width given by \p DstTySize. The 627 /// value is zero extended, truncated, or left alone to make it that width. 628 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 629 unsigned SrcTySize = getBitWidth(); 630 if (SrcTySize > DstTySize) 631 return truncate(DstTySize); 632 if (SrcTySize < DstTySize) 633 return zeroExtend(DstTySize); 634 return *this; 635 } 636 637 /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The 638 /// value is sign extended, truncated, or left alone to make it that width. 639 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 640 unsigned SrcTySize = getBitWidth(); 641 if (SrcTySize > DstTySize) 642 return truncate(DstTySize); 643 if (SrcTySize < DstTySize) 644 return signExtend(DstTySize); 645 return *this; 646 } 647 648 ConstantRange 649 ConstantRange::add(const ConstantRange &Other) const { 650 if (isEmptySet() || Other.isEmptySet()) 651 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 652 if (isFullSet() || Other.isFullSet()) 653 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 654 655 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 656 APInt NewLower = getLower() + Other.getLower(); 657 APInt NewUpper = getUpper() + Other.getUpper() - 1; 658 if (NewLower == NewUpper) 659 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 660 661 ConstantRange X = ConstantRange(NewLower, NewUpper); 662 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 663 // We've wrapped, therefore, full set. 664 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 665 666 return X; 667 } 668 669 ConstantRange 670 ConstantRange::sub(const ConstantRange &Other) const { 671 if (isEmptySet() || Other.isEmptySet()) 672 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 673 if (isFullSet() || Other.isFullSet()) 674 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 675 676 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize(); 677 APInt NewLower = getLower() - Other.getUpper() + 1; 678 APInt NewUpper = getUpper() - Other.getLower(); 679 if (NewLower == NewUpper) 680 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 681 682 ConstantRange X = ConstantRange(NewLower, NewUpper); 683 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y)) 684 // We've wrapped, therefore, full set. 685 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 686 687 return X; 688 } 689 690 ConstantRange 691 ConstantRange::multiply(const ConstantRange &Other) const { 692 // TODO: If either operand is a single element and the multiply is known to 693 // be non-wrapping, round the result min and max value to the appropriate 694 // multiple of that element. If wrapping is possible, at least adjust the 695 // range according to the greatest power-of-two factor of the single element. 696 697 if (isEmptySet() || Other.isEmptySet()) 698 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 699 700 // Multiplication is signedness-independent. However different ranges can be 701 // obtained depending on how the input ranges are treated. These different 702 // ranges are all conservatively correct, but one might be better than the 703 // other. We calculate two ranges; one treating the inputs as unsigned 704 // and the other signed, then return the smallest of these ranges. 705 706 // Unsigned range first. 707 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 708 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 709 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 710 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 711 712 ConstantRange Result_zext = ConstantRange(this_min * Other_min, 713 this_max * Other_max + 1); 714 ConstantRange UR = Result_zext.truncate(getBitWidth()); 715 716 // If the unsigned range doesn't wrap, and isn't negative then it's a range 717 // from one positive number to another which is as good as we can generate. 718 // In this case, skip the extra work of generating signed ranges which aren't 719 // going to be better than this range. 720 if (!UR.isWrappedSet() && UR.getLower().isNonNegative()) 721 return UR; 722 723 // Now the signed range. Because we could be dealing with negative numbers 724 // here, the lower bound is the smallest of the cartesian product of the 725 // lower and upper ranges; for example: 726 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6. 727 // Similarly for the upper bound, swapping min for max. 728 729 this_min = getSignedMin().sext(getBitWidth() * 2); 730 this_max = getSignedMax().sext(getBitWidth() * 2); 731 Other_min = Other.getSignedMin().sext(getBitWidth() * 2); 732 Other_max = Other.getSignedMax().sext(getBitWidth() * 2); 733 734 auto L = {this_min * Other_min, this_min * Other_max, 735 this_max * Other_min, this_max * Other_max}; 736 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); }; 737 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1); 738 ConstantRange SR = Result_sext.truncate(getBitWidth()); 739 740 return UR.getSetSize().ult(SR.getSetSize()) ? UR : SR; 741 } 742 743 ConstantRange 744 ConstantRange::smax(const ConstantRange &Other) const { 745 // X smax Y is: range(smax(X_smin, Y_smin), 746 // smax(X_smax, Y_smax)) 747 if (isEmptySet() || Other.isEmptySet()) 748 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 749 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 750 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 751 if (NewU == NewL) 752 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 753 return ConstantRange(NewL, NewU); 754 } 755 756 ConstantRange 757 ConstantRange::umax(const ConstantRange &Other) const { 758 // X umax Y is: range(umax(X_umin, Y_umin), 759 // umax(X_umax, Y_umax)) 760 if (isEmptySet() || Other.isEmptySet()) 761 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 762 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 763 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 764 if (NewU == NewL) 765 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 766 return ConstantRange(NewL, NewU); 767 } 768 769 ConstantRange 770 ConstantRange::smin(const ConstantRange &Other) const { 771 // X smin Y is: range(smin(X_smin, Y_smin), 772 // smin(X_smax, Y_smax)) 773 if (isEmptySet() || Other.isEmptySet()) 774 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 775 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin()); 776 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1; 777 if (NewU == NewL) 778 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 779 return ConstantRange(NewL, NewU); 780 } 781 782 ConstantRange 783 ConstantRange::umin(const ConstantRange &Other) const { 784 // X umin Y is: range(umin(X_umin, Y_umin), 785 // umin(X_umax, Y_umax)) 786 if (isEmptySet() || Other.isEmptySet()) 787 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 788 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin()); 789 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1; 790 if (NewU == NewL) 791 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 792 return ConstantRange(NewL, NewU); 793 } 794 795 ConstantRange 796 ConstantRange::udiv(const ConstantRange &RHS) const { 797 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0) 798 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 799 if (RHS.isFullSet()) 800 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 801 802 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 803 804 APInt RHS_umin = RHS.getUnsignedMin(); 805 if (RHS_umin == 0) { 806 // We want the lowest value in RHS excluding zero. Usually that would be 1 807 // except for a range in the form of [X, 1) in which case it would be X. 808 if (RHS.getUpper() == 1) 809 RHS_umin = RHS.getLower(); 810 else 811 RHS_umin = APInt(getBitWidth(), 1); 812 } 813 814 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 815 816 // If the LHS is Full and the RHS is a wrapped interval containing 1 then 817 // this could occur. 818 if (Lower == Upper) 819 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 820 821 return ConstantRange(Lower, Upper); 822 } 823 824 ConstantRange 825 ConstantRange::binaryAnd(const ConstantRange &Other) const { 826 if (isEmptySet() || Other.isEmptySet()) 827 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 828 829 // TODO: replace this with something less conservative 830 831 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()); 832 if (umin.isAllOnesValue()) 833 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 834 return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1); 835 } 836 837 ConstantRange 838 ConstantRange::binaryOr(const ConstantRange &Other) const { 839 if (isEmptySet() || Other.isEmptySet()) 840 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 841 842 // TODO: replace this with something less conservative 843 844 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 845 if (umax.isMinValue()) 846 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 847 return ConstantRange(umax, APInt::getNullValue(getBitWidth())); 848 } 849 850 ConstantRange 851 ConstantRange::shl(const ConstantRange &Other) const { 852 if (isEmptySet() || Other.isEmptySet()) 853 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 854 855 APInt min = getUnsignedMin().shl(Other.getUnsignedMin()); 856 APInt max = getUnsignedMax().shl(Other.getUnsignedMax()); 857 858 // there's no overflow! 859 APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros()); 860 if (Zeros.ugt(Other.getUnsignedMax())) 861 return ConstantRange(min, max + 1); 862 863 // FIXME: implement the other tricky cases 864 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 865 } 866 867 ConstantRange 868 ConstantRange::lshr(const ConstantRange &Other) const { 869 if (isEmptySet() || Other.isEmptySet()) 870 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 871 872 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()); 873 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); 874 if (min == max + 1) 875 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 876 877 return ConstantRange(min, max + 1); 878 } 879 880 ConstantRange ConstantRange::inverse() const { 881 if (isFullSet()) 882 return ConstantRange(getBitWidth(), /*isFullSet=*/false); 883 if (isEmptySet()) 884 return ConstantRange(getBitWidth(), /*isFullSet=*/true); 885 return ConstantRange(Upper, Lower); 886 } 887 888 /// print - Print out the bounds to a stream... 889 /// 890 void ConstantRange::print(raw_ostream &OS) const { 891 if (isFullSet()) 892 OS << "full-set"; 893 else if (isEmptySet()) 894 OS << "empty-set"; 895 else 896 OS << "[" << Lower << "," << Upper << ")"; 897 } 898 899 /// dump - Allow printing from a debugger easily... 900 /// 901 LLVM_DUMP_METHOD void ConstantRange::dump() const { 902 print(dbgs()); 903 } 904
