1 //===- ConstantRange.cpp - ConstantRange implementation -------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Represent a range of possible values that may occur when the program is run 10 // for an integral value. This keeps track of a lower and upper bound for the 11 // constant, which MAY wrap around the end of the numeric range. To do this, it 12 // keeps track of a [lower, upper) bound, which specifies an interval just like 13 // STL iterators. When used with boolean values, the following are important 14 // ranges (other integral ranges use min/max values for special range values): 15 // 16 // [F, F) = {} = Empty set 17 // [T, F) = {T} 18 // [F, T) = {F} 19 // [T, T) = {F, T} = Full set 20 // 21 //===----------------------------------------------------------------------===// 22 23 #include "llvm/ADT/APInt.h" 24 #include "llvm/Config/llvm-config.h" 25 #include "llvm/IR/ConstantRange.h" 26 #include "llvm/IR/Constants.h" 27 #include "llvm/IR/InstrTypes.h" 28 #include "llvm/IR/Instruction.h" 29 #include "llvm/IR/Intrinsics.h" 30 #include "llvm/IR/Metadata.h" 31 #include "llvm/IR/Operator.h" 32 #include "llvm/Support/Compiler.h" 33 #include "llvm/Support/Debug.h" 34 #include "llvm/Support/ErrorHandling.h" 35 #include "llvm/Support/KnownBits.h" 36 #include "llvm/Support/raw_ostream.h" 37 #include <algorithm> 38 #include <cassert> 39 #include <cstdint> 40 41 using namespace llvm; 42 43 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) 44 : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)), 45 Upper(Lower) {} 46 47 ConstantRange::ConstantRange(APInt V) 48 : Lower(std::move(V)), Upper(Lower + 1) {} 49 50 ConstantRange::ConstantRange(APInt L, APInt U) 51 : Lower(std::move(L)), Upper(std::move(U)) { 52 assert(Lower.getBitWidth() == Upper.getBitWidth() && 53 "ConstantRange with unequal bit widths"); 54 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) && 55 "Lower == Upper, but they aren't min or max value!"); 56 } 57 58 ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known, 59 bool IsSigned) { 60 assert(!Known.hasConflict() && "Expected valid KnownBits"); 61 62 if (Known.isUnknown()) 63 return getFull(Known.getBitWidth()); 64 65 // For unsigned ranges, or signed ranges with known sign bit, create a simple 66 // range between the smallest and largest possible value. 67 if (!IsSigned || Known.isNegative() || Known.isNonNegative()) 68 return ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1); 69 70 // If we don't know the sign bit, pick the lower bound as a negative number 71 // and the upper bound as a non-negative one. 72 APInt Lower = Known.getMinValue(), Upper = Known.getMaxValue(); 73 Lower.setSignBit(); 74 Upper.clearSignBit(); 75 return ConstantRange(Lower, Upper + 1); 76 } 77 78 KnownBits ConstantRange::toKnownBits() const { 79 // TODO: We could return conflicting known bits here, but consumers are 80 // likely not prepared for that. 81 if (isEmptySet()) 82 return KnownBits(getBitWidth()); 83 84 // We can only retain the top bits that are the same between min and max. 85 APInt Min = getUnsignedMin(); 86 APInt Max = getUnsignedMax(); 87 KnownBits Known = KnownBits::makeConstant(Min); 88 if (Optional<unsigned> DifferentBit = 89 APIntOps::GetMostSignificantDifferentBit(Min, Max)) { 90 Known.Zero.clearLowBits(*DifferentBit + 1); 91 Known.One.clearLowBits(*DifferentBit + 1); 92 } 93 return Known; 94 } 95 96 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred, 97 const ConstantRange &CR) { 98 if (CR.isEmptySet()) 99 return CR; 100 101 uint32_t W = CR.getBitWidth(); 102 switch (Pred) { 103 default: 104 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()"); 105 case CmpInst::ICMP_EQ: 106 return CR; 107 case CmpInst::ICMP_NE: 108 if (CR.isSingleElement()) 109 return ConstantRange(CR.getUpper(), CR.getLower()); 110 return getFull(W); 111 case CmpInst::ICMP_ULT: { 112 APInt UMax(CR.getUnsignedMax()); 113 if (UMax.isMinValue()) 114 return getEmpty(W); 115 return ConstantRange(APInt::getMinValue(W), std::move(UMax)); 116 } 117 case CmpInst::ICMP_SLT: { 118 APInt SMax(CR.getSignedMax()); 119 if (SMax.isMinSignedValue()) 120 return getEmpty(W); 121 return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax)); 122 } 123 case CmpInst::ICMP_ULE: 124 return getNonEmpty(APInt::getMinValue(W), CR.getUnsignedMax() + 1); 125 case CmpInst::ICMP_SLE: 126 return getNonEmpty(APInt::getSignedMinValue(W), CR.getSignedMax() + 1); 127 case CmpInst::ICMP_UGT: { 128 APInt UMin(CR.getUnsignedMin()); 129 if (UMin.isMaxValue()) 130 return getEmpty(W); 131 return ConstantRange(std::move(UMin) + 1, APInt::getZero(W)); 132 } 133 case CmpInst::ICMP_SGT: { 134 APInt SMin(CR.getSignedMin()); 135 if (SMin.isMaxSignedValue()) 136 return getEmpty(W); 137 return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W)); 138 } 139 case CmpInst::ICMP_UGE: 140 return getNonEmpty(CR.getUnsignedMin(), APInt::getZero(W)); 141 case CmpInst::ICMP_SGE: 142 return getNonEmpty(CR.getSignedMin(), APInt::getSignedMinValue(W)); 143 } 144 } 145 146 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred, 147 const ConstantRange &CR) { 148 // Follows from De-Morgan's laws: 149 // 150 // ~(~A union ~B) == A intersect B. 151 // 152 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR) 153 .inverse(); 154 } 155 156 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred, 157 const APInt &C) { 158 // Computes the exact range that is equal to both the constant ranges returned 159 // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true 160 // when RHS is a singleton such as an APInt and so the assert is valid. 161 // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion 162 // returns [0,4) but makeSatisfyICmpRegion returns [0,2). 163 // 164 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C)); 165 return makeAllowedICmpRegion(Pred, C); 166 } 167 168 bool ConstantRange::areInsensitiveToSignednessOfICmpPredicate( 169 const ConstantRange &CR1, const ConstantRange &CR2) { 170 if (CR1.isEmptySet() || CR2.isEmptySet()) 171 return true; 172 173 return (CR1.isAllNonNegative() && CR2.isAllNonNegative()) || 174 (CR1.isAllNegative() && CR2.isAllNegative()); 175 } 176 177 bool ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate( 178 const ConstantRange &CR1, const ConstantRange &CR2) { 179 if (CR1.isEmptySet() || CR2.isEmptySet()) 180 return true; 181 182 return (CR1.isAllNonNegative() && CR2.isAllNegative()) || 183 (CR1.isAllNegative() && CR2.isAllNonNegative()); 184 } 185 186 CmpInst::Predicate ConstantRange::getEquivalentPredWithFlippedSignedness( 187 CmpInst::Predicate Pred, const ConstantRange &CR1, 188 const ConstantRange &CR2) { 189 assert(CmpInst::isIntPredicate(Pred) && CmpInst::isRelational(Pred) && 190 "Only for relational integer predicates!"); 191 192 CmpInst::Predicate FlippedSignednessPred = 193 CmpInst::getFlippedSignednessPredicate(Pred); 194 195 if (areInsensitiveToSignednessOfICmpPredicate(CR1, CR2)) 196 return FlippedSignednessPred; 197 198 if (areInsensitiveToSignednessOfInvertedICmpPredicate(CR1, CR2)) 199 return CmpInst::getInversePredicate(FlippedSignednessPred); 200 201 return CmpInst::Predicate::BAD_ICMP_PREDICATE; 202 } 203 204 void ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred, 205 APInt &RHS, APInt &Offset) const { 206 Offset = APInt(getBitWidth(), 0); 207 if (isFullSet() || isEmptySet()) { 208 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE; 209 RHS = APInt(getBitWidth(), 0); 210 } else if (auto *OnlyElt = getSingleElement()) { 211 Pred = CmpInst::ICMP_EQ; 212 RHS = *OnlyElt; 213 } else if (auto *OnlyMissingElt = getSingleMissingElement()) { 214 Pred = CmpInst::ICMP_NE; 215 RHS = *OnlyMissingElt; 216 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) { 217 Pred = 218 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT; 219 RHS = getUpper(); 220 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) { 221 Pred = 222 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE; 223 RHS = getLower(); 224 } else { 225 Pred = CmpInst::ICMP_ULT; 226 RHS = getUpper() - getLower(); 227 Offset = -getLower(); 228 } 229 230 assert(ConstantRange::makeExactICmpRegion(Pred, RHS) == add(Offset) && 231 "Bad result!"); 232 } 233 234 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred, 235 APInt &RHS) const { 236 APInt Offset; 237 getEquivalentICmp(Pred, RHS, Offset); 238 return Offset.isZero(); 239 } 240 241 bool ConstantRange::icmp(CmpInst::Predicate Pred, 242 const ConstantRange &Other) const { 243 return makeSatisfyingICmpRegion(Pred, Other).contains(*this); 244 } 245 246 /// Exact mul nuw region for single element RHS. 247 static ConstantRange makeExactMulNUWRegion(const APInt &V) { 248 unsigned BitWidth = V.getBitWidth(); 249 if (V == 0) 250 return ConstantRange::getFull(V.getBitWidth()); 251 252 return ConstantRange::getNonEmpty( 253 APIntOps::RoundingUDiv(APInt::getMinValue(BitWidth), V, 254 APInt::Rounding::UP), 255 APIntOps::RoundingUDiv(APInt::getMaxValue(BitWidth), V, 256 APInt::Rounding::DOWN) + 1); 257 } 258 259 /// Exact mul nsw region for single element RHS. 260 static ConstantRange makeExactMulNSWRegion(const APInt &V) { 261 // Handle special case for 0, -1 and 1. See the last for reason why we 262 // specialize -1 and 1. 263 unsigned BitWidth = V.getBitWidth(); 264 if (V == 0 || V.isOne()) 265 return ConstantRange::getFull(BitWidth); 266 267 APInt MinValue = APInt::getSignedMinValue(BitWidth); 268 APInt MaxValue = APInt::getSignedMaxValue(BitWidth); 269 // e.g. Returning [-127, 127], represented as [-127, -128). 270 if (V.isAllOnes()) 271 return ConstantRange(-MaxValue, MinValue); 272 273 APInt Lower, Upper; 274 if (V.isNegative()) { 275 Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP); 276 Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN); 277 } else { 278 Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP); 279 Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN); 280 } 281 // ConstantRange ctor take a half inclusive interval [Lower, Upper + 1). 282 // Upper + 1 is guaranteed not to overflow, because |divisor| > 1. 0, -1, 283 // and 1 are already handled as special cases. 284 return ConstantRange(Lower, Upper + 1); 285 } 286 287 ConstantRange 288 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, 289 const ConstantRange &Other, 290 unsigned NoWrapKind) { 291 using OBO = OverflowingBinaryOperator; 292 293 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!"); 294 295 assert((NoWrapKind == OBO::NoSignedWrap || 296 NoWrapKind == OBO::NoUnsignedWrap) && 297 "NoWrapKind invalid!"); 298 299 bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap; 300 unsigned BitWidth = Other.getBitWidth(); 301 302 switch (BinOp) { 303 default: 304 llvm_unreachable("Unsupported binary op"); 305 306 case Instruction::Add: { 307 if (Unsigned) 308 return getNonEmpty(APInt::getZero(BitWidth), -Other.getUnsignedMax()); 309 310 APInt SignedMinVal = APInt::getSignedMinValue(BitWidth); 311 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax(); 312 return getNonEmpty( 313 SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal, 314 SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal); 315 } 316 317 case Instruction::Sub: { 318 if (Unsigned) 319 return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth)); 320 321 APInt SignedMinVal = APInt::getSignedMinValue(BitWidth); 322 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax(); 323 return getNonEmpty( 324 SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal, 325 SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal); 326 } 327 328 case Instruction::Mul: 329 if (Unsigned) 330 return makeExactMulNUWRegion(Other.getUnsignedMax()); 331 332 return makeExactMulNSWRegion(Other.getSignedMin()) 333 .intersectWith(makeExactMulNSWRegion(Other.getSignedMax())); 334 335 case Instruction::Shl: { 336 // For given range of shift amounts, if we ignore all illegal shift amounts 337 // (that always produce poison), what shift amount range is left? 338 ConstantRange ShAmt = Other.intersectWith( 339 ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, (BitWidth - 1) + 1))); 340 if (ShAmt.isEmptySet()) { 341 // If the entire range of shift amounts is already poison-producing, 342 // then we can freely add more poison-producing flags ontop of that. 343 return getFull(BitWidth); 344 } 345 // There are some legal shift amounts, we can compute conservatively-correct 346 // range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax 347 // to be at most bitwidth-1, which results in most conservative range. 348 APInt ShAmtUMax = ShAmt.getUnsignedMax(); 349 if (Unsigned) 350 return getNonEmpty(APInt::getZero(BitWidth), 351 APInt::getMaxValue(BitWidth).lshr(ShAmtUMax) + 1); 352 return getNonEmpty(APInt::getSignedMinValue(BitWidth).ashr(ShAmtUMax), 353 APInt::getSignedMaxValue(BitWidth).ashr(ShAmtUMax) + 1); 354 } 355 } 356 } 357 358 ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp, 359 const APInt &Other, 360 unsigned NoWrapKind) { 361 // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as 362 // "for all" and "for any" coincide in this case. 363 return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind); 364 } 365 366 bool ConstantRange::isFullSet() const { 367 return Lower == Upper && Lower.isMaxValue(); 368 } 369 370 bool ConstantRange::isEmptySet() const { 371 return Lower == Upper && Lower.isMinValue(); 372 } 373 374 bool ConstantRange::isWrappedSet() const { 375 return Lower.ugt(Upper) && !Upper.isZero(); 376 } 377 378 bool ConstantRange::isUpperWrapped() const { 379 return Lower.ugt(Upper); 380 } 381 382 bool ConstantRange::isSignWrappedSet() const { 383 return Lower.sgt(Upper) && !Upper.isMinSignedValue(); 384 } 385 386 bool ConstantRange::isUpperSignWrapped() const { 387 return Lower.sgt(Upper); 388 } 389 390 bool 391 ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const { 392 assert(getBitWidth() == Other.getBitWidth()); 393 if (isFullSet()) 394 return false; 395 if (Other.isFullSet()) 396 return true; 397 return (Upper - Lower).ult(Other.Upper - Other.Lower); 398 } 399 400 bool 401 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const { 402 // If this a full set, we need special handling to avoid needing an extra bit 403 // to represent the size. 404 if (isFullSet()) 405 return MaxSize == 0 || APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1); 406 407 return (Upper - Lower).ugt(MaxSize); 408 } 409 410 bool ConstantRange::isAllNegative() const { 411 // Empty set is all negative, full set is not. 412 if (isEmptySet()) 413 return true; 414 if (isFullSet()) 415 return false; 416 417 return !isUpperSignWrapped() && !Upper.isStrictlyPositive(); 418 } 419 420 bool ConstantRange::isAllNonNegative() const { 421 // Empty and full set are automatically treated correctly. 422 return !isSignWrappedSet() && Lower.isNonNegative(); 423 } 424 425 APInt ConstantRange::getUnsignedMax() const { 426 if (isFullSet() || isUpperWrapped()) 427 return APInt::getMaxValue(getBitWidth()); 428 return getUpper() - 1; 429 } 430 431 APInt ConstantRange::getUnsignedMin() const { 432 if (isFullSet() || isWrappedSet()) 433 return APInt::getMinValue(getBitWidth()); 434 return getLower(); 435 } 436 437 APInt ConstantRange::getSignedMax() const { 438 if (isFullSet() || isUpperSignWrapped()) 439 return APInt::getSignedMaxValue(getBitWidth()); 440 return getUpper() - 1; 441 } 442 443 APInt ConstantRange::getSignedMin() const { 444 if (isFullSet() || isSignWrappedSet()) 445 return APInt::getSignedMinValue(getBitWidth()); 446 return getLower(); 447 } 448 449 bool ConstantRange::contains(const APInt &V) const { 450 if (Lower == Upper) 451 return isFullSet(); 452 453 if (!isUpperWrapped()) 454 return Lower.ule(V) && V.ult(Upper); 455 return Lower.ule(V) || V.ult(Upper); 456 } 457 458 bool ConstantRange::contains(const ConstantRange &Other) const { 459 if (isFullSet() || Other.isEmptySet()) return true; 460 if (isEmptySet() || Other.isFullSet()) return false; 461 462 if (!isUpperWrapped()) { 463 if (Other.isUpperWrapped()) 464 return false; 465 466 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper); 467 } 468 469 if (!Other.isUpperWrapped()) 470 return Other.getUpper().ule(Upper) || 471 Lower.ule(Other.getLower()); 472 473 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower()); 474 } 475 476 unsigned ConstantRange::getActiveBits() const { 477 if (isEmptySet()) 478 return 0; 479 480 return getUnsignedMax().getActiveBits(); 481 } 482 483 unsigned ConstantRange::getMinSignedBits() const { 484 if (isEmptySet()) 485 return 0; 486 487 return std::max(getSignedMin().getMinSignedBits(), 488 getSignedMax().getMinSignedBits()); 489 } 490 491 ConstantRange ConstantRange::subtract(const APInt &Val) const { 492 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width"); 493 // If the set is empty or full, don't modify the endpoints. 494 if (Lower == Upper) 495 return *this; 496 return ConstantRange(Lower - Val, Upper - Val); 497 } 498 499 ConstantRange ConstantRange::difference(const ConstantRange &CR) const { 500 return intersectWith(CR.inverse()); 501 } 502 503 static ConstantRange getPreferredRange( 504 const ConstantRange &CR1, const ConstantRange &CR2, 505 ConstantRange::PreferredRangeType Type) { 506 if (Type == ConstantRange::Unsigned) { 507 if (!CR1.isWrappedSet() && CR2.isWrappedSet()) 508 return CR1; 509 if (CR1.isWrappedSet() && !CR2.isWrappedSet()) 510 return CR2; 511 } else if (Type == ConstantRange::Signed) { 512 if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet()) 513 return CR1; 514 if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet()) 515 return CR2; 516 } 517 518 if (CR1.isSizeStrictlySmallerThan(CR2)) 519 return CR1; 520 return CR2; 521 } 522 523 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR, 524 PreferredRangeType Type) const { 525 assert(getBitWidth() == CR.getBitWidth() && 526 "ConstantRange types don't agree!"); 527 528 // Handle common cases. 529 if ( isEmptySet() || CR.isFullSet()) return *this; 530 if (CR.isEmptySet() || isFullSet()) return CR; 531 532 if (!isUpperWrapped() && CR.isUpperWrapped()) 533 return CR.intersectWith(*this, Type); 534 535 if (!isUpperWrapped() && !CR.isUpperWrapped()) { 536 if (Lower.ult(CR.Lower)) { 537 // L---U : this 538 // L---U : CR 539 if (Upper.ule(CR.Lower)) 540 return getEmpty(); 541 542 // L---U : this 543 // L---U : CR 544 if (Upper.ult(CR.Upper)) 545 return ConstantRange(CR.Lower, Upper); 546 547 // L-------U : this 548 // L---U : CR 549 return CR; 550 } 551 // L---U : this 552 // L-------U : CR 553 if (Upper.ult(CR.Upper)) 554 return *this; 555 556 // L-----U : this 557 // L-----U : CR 558 if (Lower.ult(CR.Upper)) 559 return ConstantRange(Lower, CR.Upper); 560 561 // L---U : this 562 // L---U : CR 563 return getEmpty(); 564 } 565 566 if (isUpperWrapped() && !CR.isUpperWrapped()) { 567 if (CR.Lower.ult(Upper)) { 568 // ------U L--- : this 569 // L--U : CR 570 if (CR.Upper.ult(Upper)) 571 return CR; 572 573 // ------U L--- : this 574 // L------U : CR 575 if (CR.Upper.ule(Lower)) 576 return ConstantRange(CR.Lower, Upper); 577 578 // ------U L--- : this 579 // L----------U : CR 580 return getPreferredRange(*this, CR, Type); 581 } 582 if (CR.Lower.ult(Lower)) { 583 // --U L---- : this 584 // L--U : CR 585 if (CR.Upper.ule(Lower)) 586 return getEmpty(); 587 588 // --U L---- : this 589 // L------U : CR 590 return ConstantRange(Lower, CR.Upper); 591 } 592 593 // --U L------ : this 594 // L--U : CR 595 return CR; 596 } 597 598 if (CR.Upper.ult(Upper)) { 599 // ------U L-- : this 600 // --U L------ : CR 601 if (CR.Lower.ult(Upper)) 602 return getPreferredRange(*this, CR, Type); 603 604 // ----U L-- : this 605 // --U L---- : CR 606 if (CR.Lower.ult(Lower)) 607 return ConstantRange(Lower, CR.Upper); 608 609 // ----U L---- : this 610 // --U L-- : CR 611 return CR; 612 } 613 if (CR.Upper.ule(Lower)) { 614 // --U L-- : this 615 // ----U L---- : CR 616 if (CR.Lower.ult(Lower)) 617 return *this; 618 619 // --U L---- : this 620 // ----U L-- : CR 621 return ConstantRange(CR.Lower, Upper); 622 } 623 624 // --U L------ : this 625 // ------U L-- : CR 626 return getPreferredRange(*this, CR, Type); 627 } 628 629 ConstantRange ConstantRange::unionWith(const ConstantRange &CR, 630 PreferredRangeType Type) const { 631 assert(getBitWidth() == CR.getBitWidth() && 632 "ConstantRange types don't agree!"); 633 634 if ( isFullSet() || CR.isEmptySet()) return *this; 635 if (CR.isFullSet() || isEmptySet()) return CR; 636 637 if (!isUpperWrapped() && CR.isUpperWrapped()) 638 return CR.unionWith(*this, Type); 639 640 if (!isUpperWrapped() && !CR.isUpperWrapped()) { 641 // L---U and L---U : this 642 // L---U L---U : CR 643 // result in one of 644 // L---------U 645 // -----U L----- 646 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) 647 return getPreferredRange( 648 ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type); 649 650 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower; 651 APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper; 652 653 if (L.isZero() && U.isZero()) 654 return getFull(); 655 656 return ConstantRange(std::move(L), std::move(U)); 657 } 658 659 if (!CR.isUpperWrapped()) { 660 // ------U L----- and ------U L----- : this 661 // L--U L--U : CR 662 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower)) 663 return *this; 664 665 // ------U L----- : this 666 // L---------U : CR 667 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) 668 return getFull(); 669 670 // ----U L---- : this 671 // L---U : CR 672 // results in one of 673 // ----------U L---- 674 // ----U L---------- 675 if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) 676 return getPreferredRange( 677 ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type); 678 679 // ----U L----- : this 680 // L----U : CR 681 if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper)) 682 return ConstantRange(CR.Lower, Upper); 683 684 // ------U L---- : this 685 // L-----U : CR 686 assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) && 687 "ConstantRange::unionWith missed a case with one range wrapped"); 688 return ConstantRange(Lower, CR.Upper); 689 } 690 691 // ------U L---- and ------U L---- : this 692 // -U L----------- and ------------U L : CR 693 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper)) 694 return getFull(); 695 696 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower; 697 APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper; 698 699 return ConstantRange(std::move(L), std::move(U)); 700 } 701 702 Optional<ConstantRange> 703 ConstantRange::exactIntersectWith(const ConstantRange &CR) const { 704 // TODO: This can be implemented more efficiently. 705 ConstantRange Result = intersectWith(CR); 706 if (Result == inverse().unionWith(CR.inverse()).inverse()) 707 return Result; 708 return None; 709 } 710 711 Optional<ConstantRange> 712 ConstantRange::exactUnionWith(const ConstantRange &CR) const { 713 // TODO: This can be implemented more efficiently. 714 ConstantRange Result = unionWith(CR); 715 if (Result == inverse().intersectWith(CR.inverse()).inverse()) 716 return Result; 717 return None; 718 } 719 720 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp, 721 uint32_t ResultBitWidth) const { 722 switch (CastOp) { 723 default: 724 llvm_unreachable("unsupported cast type"); 725 case Instruction::Trunc: 726 return truncate(ResultBitWidth); 727 case Instruction::SExt: 728 return signExtend(ResultBitWidth); 729 case Instruction::ZExt: 730 return zeroExtend(ResultBitWidth); 731 case Instruction::BitCast: 732 return *this; 733 case Instruction::FPToUI: 734 case Instruction::FPToSI: 735 if (getBitWidth() == ResultBitWidth) 736 return *this; 737 else 738 return getFull(ResultBitWidth); 739 case Instruction::UIToFP: { 740 // TODO: use input range if available 741 auto BW = getBitWidth(); 742 APInt Min = APInt::getMinValue(BW); 743 APInt Max = APInt::getMaxValue(BW); 744 if (ResultBitWidth > BW) { 745 Min = Min.zext(ResultBitWidth); 746 Max = Max.zext(ResultBitWidth); 747 } 748 return ConstantRange(std::move(Min), std::move(Max)); 749 } 750 case Instruction::SIToFP: { 751 // TODO: use input range if available 752 auto BW = getBitWidth(); 753 APInt SMin = APInt::getSignedMinValue(BW); 754 APInt SMax = APInt::getSignedMaxValue(BW); 755 if (ResultBitWidth > BW) { 756 SMin = SMin.sext(ResultBitWidth); 757 SMax = SMax.sext(ResultBitWidth); 758 } 759 return ConstantRange(std::move(SMin), std::move(SMax)); 760 } 761 case Instruction::FPTrunc: 762 case Instruction::FPExt: 763 case Instruction::IntToPtr: 764 case Instruction::PtrToInt: 765 case Instruction::AddrSpaceCast: 766 // Conservatively return getFull set. 767 return getFull(ResultBitWidth); 768 }; 769 } 770 771 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const { 772 if (isEmptySet()) return getEmpty(DstTySize); 773 774 unsigned SrcTySize = getBitWidth(); 775 assert(SrcTySize < DstTySize && "Not a value extension"); 776 if (isFullSet() || isUpperWrapped()) { 777 // Change into [0, 1 << src bit width) 778 APInt LowerExt(DstTySize, 0); 779 if (!Upper) // special case: [X, 0) -- not really wrapping around 780 LowerExt = Lower.zext(DstTySize); 781 return ConstantRange(std::move(LowerExt), 782 APInt::getOneBitSet(DstTySize, SrcTySize)); 783 } 784 785 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize)); 786 } 787 788 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const { 789 if (isEmptySet()) return getEmpty(DstTySize); 790 791 unsigned SrcTySize = getBitWidth(); 792 assert(SrcTySize < DstTySize && "Not a value extension"); 793 794 // special case: [X, INT_MIN) -- not really wrapping around 795 if (Upper.isMinSignedValue()) 796 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize)); 797 798 if (isFullSet() || isSignWrappedSet()) { 799 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1), 800 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1); 801 } 802 803 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize)); 804 } 805 806 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const { 807 assert(getBitWidth() > DstTySize && "Not a value truncation"); 808 if (isEmptySet()) 809 return getEmpty(DstTySize); 810 if (isFullSet()) 811 return getFull(DstTySize); 812 813 APInt LowerDiv(Lower), UpperDiv(Upper); 814 ConstantRange Union(DstTySize, /*isFullSet=*/false); 815 816 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] 817 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and 818 // then we do the union with [MaxValue, Upper) 819 if (isUpperWrapped()) { 820 // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole 821 // truncated range. 822 if (Upper.getActiveBits() > DstTySize || 823 Upper.countTrailingOnes() == DstTySize) 824 return getFull(DstTySize); 825 826 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize)); 827 UpperDiv.setAllBits(); 828 829 // Union covers the MaxValue case, so return if the remaining range is just 830 // MaxValue(DstTy). 831 if (LowerDiv == UpperDiv) 832 return Union; 833 } 834 835 // Chop off the most significant bits that are past the destination bitwidth. 836 if (LowerDiv.getActiveBits() > DstTySize) { 837 // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv. 838 APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize); 839 LowerDiv -= Adjust; 840 UpperDiv -= Adjust; 841 } 842 843 unsigned UpperDivWidth = UpperDiv.getActiveBits(); 844 if (UpperDivWidth <= DstTySize) 845 return ConstantRange(LowerDiv.trunc(DstTySize), 846 UpperDiv.trunc(DstTySize)).unionWith(Union); 847 848 // The truncated value wraps around. Check if we can do better than fullset. 849 if (UpperDivWidth == DstTySize + 1) { 850 // Clear the MSB so that UpperDiv wraps around. 851 UpperDiv.clearBit(DstTySize); 852 if (UpperDiv.ult(LowerDiv)) 853 return ConstantRange(LowerDiv.trunc(DstTySize), 854 UpperDiv.trunc(DstTySize)).unionWith(Union); 855 } 856 857 return getFull(DstTySize); 858 } 859 860 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const { 861 unsigned SrcTySize = getBitWidth(); 862 if (SrcTySize > DstTySize) 863 return truncate(DstTySize); 864 if (SrcTySize < DstTySize) 865 return zeroExtend(DstTySize); 866 return *this; 867 } 868 869 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { 870 unsigned SrcTySize = getBitWidth(); 871 if (SrcTySize > DstTySize) 872 return truncate(DstTySize); 873 if (SrcTySize < DstTySize) 874 return signExtend(DstTySize); 875 return *this; 876 } 877 878 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp, 879 const ConstantRange &Other) const { 880 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!"); 881 882 switch (BinOp) { 883 case Instruction::Add: 884 return add(Other); 885 case Instruction::Sub: 886 return sub(Other); 887 case Instruction::Mul: 888 return multiply(Other); 889 case Instruction::UDiv: 890 return udiv(Other); 891 case Instruction::SDiv: 892 return sdiv(Other); 893 case Instruction::URem: 894 return urem(Other); 895 case Instruction::SRem: 896 return srem(Other); 897 case Instruction::Shl: 898 return shl(Other); 899 case Instruction::LShr: 900 return lshr(Other); 901 case Instruction::AShr: 902 return ashr(Other); 903 case Instruction::And: 904 return binaryAnd(Other); 905 case Instruction::Or: 906 return binaryOr(Other); 907 case Instruction::Xor: 908 return binaryXor(Other); 909 // Note: floating point operations applied to abstract ranges are just 910 // ideal integer operations with a lossy representation 911 case Instruction::FAdd: 912 return add(Other); 913 case Instruction::FSub: 914 return sub(Other); 915 case Instruction::FMul: 916 return multiply(Other); 917 default: 918 // Conservatively return getFull set. 919 return getFull(); 920 } 921 } 922 923 ConstantRange ConstantRange::overflowingBinaryOp(Instruction::BinaryOps BinOp, 924 const ConstantRange &Other, 925 unsigned NoWrapKind) const { 926 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!"); 927 928 switch (BinOp) { 929 case Instruction::Add: 930 return addWithNoWrap(Other, NoWrapKind); 931 case Instruction::Sub: 932 return subWithNoWrap(Other, NoWrapKind); 933 default: 934 // Don't know about this Overflowing Binary Operation. 935 // Conservatively fallback to plain binop handling. 936 return binaryOp(BinOp, Other); 937 } 938 } 939 940 bool ConstantRange::isIntrinsicSupported(Intrinsic::ID IntrinsicID) { 941 switch (IntrinsicID) { 942 case Intrinsic::uadd_sat: 943 case Intrinsic::usub_sat: 944 case Intrinsic::sadd_sat: 945 case Intrinsic::ssub_sat: 946 case Intrinsic::umin: 947 case Intrinsic::umax: 948 case Intrinsic::smin: 949 case Intrinsic::smax: 950 case Intrinsic::abs: 951 return true; 952 default: 953 return false; 954 } 955 } 956 957 ConstantRange ConstantRange::intrinsic(Intrinsic::ID IntrinsicID, 958 ArrayRef<ConstantRange> Ops) { 959 switch (IntrinsicID) { 960 case Intrinsic::uadd_sat: 961 return Ops[0].uadd_sat(Ops[1]); 962 case Intrinsic::usub_sat: 963 return Ops[0].usub_sat(Ops[1]); 964 case Intrinsic::sadd_sat: 965 return Ops[0].sadd_sat(Ops[1]); 966 case Intrinsic::ssub_sat: 967 return Ops[0].ssub_sat(Ops[1]); 968 case Intrinsic::umin: 969 return Ops[0].umin(Ops[1]); 970 case Intrinsic::umax: 971 return Ops[0].umax(Ops[1]); 972 case Intrinsic::smin: 973 return Ops[0].smin(Ops[1]); 974 case Intrinsic::smax: 975 return Ops[0].smax(Ops[1]); 976 case Intrinsic::abs: { 977 const APInt *IntMinIsPoison = Ops[1].getSingleElement(); 978 assert(IntMinIsPoison && "Must be known (immarg)"); 979 assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean"); 980 return Ops[0].abs(IntMinIsPoison->getBoolValue()); 981 } 982 default: 983 assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported"); 984 llvm_unreachable("Unsupported intrinsic"); 985 } 986 } 987 988 ConstantRange 989 ConstantRange::add(const ConstantRange &Other) const { 990 if (isEmptySet() || Other.isEmptySet()) 991 return getEmpty(); 992 if (isFullSet() || Other.isFullSet()) 993 return getFull(); 994 995 APInt NewLower = getLower() + Other.getLower(); 996 APInt NewUpper = getUpper() + Other.getUpper() - 1; 997 if (NewLower == NewUpper) 998 return getFull(); 999 1000 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper)); 1001 if (X.isSizeStrictlySmallerThan(*this) || 1002 X.isSizeStrictlySmallerThan(Other)) 1003 // We've wrapped, therefore, full set. 1004 return getFull(); 1005 return X; 1006 } 1007 1008 ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other, 1009 unsigned NoWrapKind, 1010 PreferredRangeType RangeType) const { 1011 // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow). 1012 // (X is from this, and Y is from Other) 1013 if (isEmptySet() || Other.isEmptySet()) 1014 return getEmpty(); 1015 if (isFullSet() && Other.isFullSet()) 1016 return getFull(); 1017 1018 using OBO = OverflowingBinaryOperator; 1019 ConstantRange Result = add(Other); 1020 1021 // If an overflow happens for every value pair in these two constant ranges, 1022 // we must return Empty set. In this case, we get that for free, because we 1023 // get lucky that intersection of add() with uadd_sat()/sadd_sat() results 1024 // in an empty set. 1025 1026 if (NoWrapKind & OBO::NoSignedWrap) 1027 Result = Result.intersectWith(sadd_sat(Other), RangeType); 1028 1029 if (NoWrapKind & OBO::NoUnsignedWrap) 1030 Result = Result.intersectWith(uadd_sat(Other), RangeType); 1031 1032 return Result; 1033 } 1034 1035 ConstantRange 1036 ConstantRange::sub(const ConstantRange &Other) const { 1037 if (isEmptySet() || Other.isEmptySet()) 1038 return getEmpty(); 1039 if (isFullSet() || Other.isFullSet()) 1040 return getFull(); 1041 1042 APInt NewLower = getLower() - Other.getUpper() + 1; 1043 APInt NewUpper = getUpper() - Other.getLower(); 1044 if (NewLower == NewUpper) 1045 return getFull(); 1046 1047 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper)); 1048 if (X.isSizeStrictlySmallerThan(*this) || 1049 X.isSizeStrictlySmallerThan(Other)) 1050 // We've wrapped, therefore, full set. 1051 return getFull(); 1052 return X; 1053 } 1054 1055 ConstantRange ConstantRange::subWithNoWrap(const ConstantRange &Other, 1056 unsigned NoWrapKind, 1057 PreferredRangeType RangeType) const { 1058 // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow). 1059 // (X is from this, and Y is from Other) 1060 if (isEmptySet() || Other.isEmptySet()) 1061 return getEmpty(); 1062 if (isFullSet() && Other.isFullSet()) 1063 return getFull(); 1064 1065 using OBO = OverflowingBinaryOperator; 1066 ConstantRange Result = sub(Other); 1067 1068 // If an overflow happens for every value pair in these two constant ranges, 1069 // we must return Empty set. In signed case, we get that for free, because we 1070 // get lucky that intersection of sub() with ssub_sat() results in an 1071 // empty set. But for unsigned we must perform the overflow check manually. 1072 1073 if (NoWrapKind & OBO::NoSignedWrap) 1074 Result = Result.intersectWith(ssub_sat(Other), RangeType); 1075 1076 if (NoWrapKind & OBO::NoUnsignedWrap) { 1077 if (getUnsignedMax().ult(Other.getUnsignedMin())) 1078 return getEmpty(); // Always overflows. 1079 Result = Result.intersectWith(usub_sat(Other), RangeType); 1080 } 1081 1082 return Result; 1083 } 1084 1085 ConstantRange 1086 ConstantRange::multiply(const ConstantRange &Other) const { 1087 // TODO: If either operand is a single element and the multiply is known to 1088 // be non-wrapping, round the result min and max value to the appropriate 1089 // multiple of that element. If wrapping is possible, at least adjust the 1090 // range according to the greatest power-of-two factor of the single element. 1091 1092 if (isEmptySet() || Other.isEmptySet()) 1093 return getEmpty(); 1094 1095 // Multiplication is signedness-independent. However different ranges can be 1096 // obtained depending on how the input ranges are treated. These different 1097 // ranges are all conservatively correct, but one might be better than the 1098 // other. We calculate two ranges; one treating the inputs as unsigned 1099 // and the other signed, then return the smallest of these ranges. 1100 1101 // Unsigned range first. 1102 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2); 1103 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2); 1104 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2); 1105 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2); 1106 1107 ConstantRange Result_zext = ConstantRange(this_min * Other_min, 1108 this_max * Other_max + 1); 1109 ConstantRange UR = Result_zext.truncate(getBitWidth()); 1110 1111 // If the unsigned range doesn't wrap, and isn't negative then it's a range 1112 // from one positive number to another which is as good as we can generate. 1113 // In this case, skip the extra work of generating signed ranges which aren't 1114 // going to be better than this range. 1115 if (!UR.isUpperWrapped() && 1116 (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue())) 1117 return UR; 1118 1119 // Now the signed range. Because we could be dealing with negative numbers 1120 // here, the lower bound is the smallest of the cartesian product of the 1121 // lower and upper ranges; for example: 1122 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6. 1123 // Similarly for the upper bound, swapping min for max. 1124 1125 this_min = getSignedMin().sext(getBitWidth() * 2); 1126 this_max = getSignedMax().sext(getBitWidth() * 2); 1127 Other_min = Other.getSignedMin().sext(getBitWidth() * 2); 1128 Other_max = Other.getSignedMax().sext(getBitWidth() * 2); 1129 1130 auto L = {this_min * Other_min, this_min * Other_max, 1131 this_max * Other_min, this_max * Other_max}; 1132 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); }; 1133 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1); 1134 ConstantRange SR = Result_sext.truncate(getBitWidth()); 1135 1136 return UR.isSizeStrictlySmallerThan(SR) ? UR : SR; 1137 } 1138 1139 ConstantRange ConstantRange::smul_fast(const ConstantRange &Other) const { 1140 if (isEmptySet() || Other.isEmptySet()) 1141 return getEmpty(); 1142 1143 APInt Min = getSignedMin(); 1144 APInt Max = getSignedMax(); 1145 APInt OtherMin = Other.getSignedMin(); 1146 APInt OtherMax = Other.getSignedMax(); 1147 1148 bool O1, O2, O3, O4; 1149 auto Muls = {Min.smul_ov(OtherMin, O1), Min.smul_ov(OtherMax, O2), 1150 Max.smul_ov(OtherMin, O3), Max.smul_ov(OtherMax, O4)}; 1151 if (O1 || O2 || O3 || O4) 1152 return getFull(); 1153 1154 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); }; 1155 return getNonEmpty(std::min(Muls, Compare), std::max(Muls, Compare) + 1); 1156 } 1157 1158 ConstantRange 1159 ConstantRange::smax(const ConstantRange &Other) const { 1160 // X smax Y is: range(smax(X_smin, Y_smin), 1161 // smax(X_smax, Y_smax)) 1162 if (isEmptySet() || Other.isEmptySet()) 1163 return getEmpty(); 1164 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin()); 1165 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1; 1166 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU)); 1167 if (isSignWrappedSet() || Other.isSignWrappedSet()) 1168 return Res.intersectWith(unionWith(Other, Signed), Signed); 1169 return Res; 1170 } 1171 1172 ConstantRange 1173 ConstantRange::umax(const ConstantRange &Other) const { 1174 // X umax Y is: range(umax(X_umin, Y_umin), 1175 // umax(X_umax, Y_umax)) 1176 if (isEmptySet() || Other.isEmptySet()) 1177 return getEmpty(); 1178 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()); 1179 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1; 1180 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU)); 1181 if (isWrappedSet() || Other.isWrappedSet()) 1182 return Res.intersectWith(unionWith(Other, Unsigned), Unsigned); 1183 return Res; 1184 } 1185 1186 ConstantRange 1187 ConstantRange::smin(const ConstantRange &Other) const { 1188 // X smin Y is: range(smin(X_smin, Y_smin), 1189 // smin(X_smax, Y_smax)) 1190 if (isEmptySet() || Other.isEmptySet()) 1191 return getEmpty(); 1192 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin()); 1193 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1; 1194 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU)); 1195 if (isSignWrappedSet() || Other.isSignWrappedSet()) 1196 return Res.intersectWith(unionWith(Other, Signed), Signed); 1197 return Res; 1198 } 1199 1200 ConstantRange 1201 ConstantRange::umin(const ConstantRange &Other) const { 1202 // X umin Y is: range(umin(X_umin, Y_umin), 1203 // umin(X_umax, Y_umax)) 1204 if (isEmptySet() || Other.isEmptySet()) 1205 return getEmpty(); 1206 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin()); 1207 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1; 1208 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU)); 1209 if (isWrappedSet() || Other.isWrappedSet()) 1210 return Res.intersectWith(unionWith(Other, Unsigned), Unsigned); 1211 return Res; 1212 } 1213 1214 ConstantRange 1215 ConstantRange::udiv(const ConstantRange &RHS) const { 1216 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero()) 1217 return getEmpty(); 1218 1219 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax()); 1220 1221 APInt RHS_umin = RHS.getUnsignedMin(); 1222 if (RHS_umin.isZero()) { 1223 // We want the lowest value in RHS excluding zero. Usually that would be 1 1224 // except for a range in the form of [X, 1) in which case it would be X. 1225 if (RHS.getUpper() == 1) 1226 RHS_umin = RHS.getLower(); 1227 else 1228 RHS_umin = 1; 1229 } 1230 1231 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1; 1232 return getNonEmpty(std::move(Lower), std::move(Upper)); 1233 } 1234 1235 ConstantRange ConstantRange::sdiv(const ConstantRange &RHS) const { 1236 // We split up the LHS and RHS into positive and negative components 1237 // and then also compute the positive and negative components of the result 1238 // separately by combining division results with the appropriate signs. 1239 APInt Zero = APInt::getZero(getBitWidth()); 1240 APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); 1241 // There are no positive 1-bit values. The 1 would get interpreted as -1. 1242 ConstantRange PosFilter = 1243 getBitWidth() == 1 ? getEmpty() 1244 : ConstantRange(APInt(getBitWidth(), 1), SignedMin); 1245 ConstantRange NegFilter(SignedMin, Zero); 1246 ConstantRange PosL = intersectWith(PosFilter); 1247 ConstantRange NegL = intersectWith(NegFilter); 1248 ConstantRange PosR = RHS.intersectWith(PosFilter); 1249 ConstantRange NegR = RHS.intersectWith(NegFilter); 1250 1251 ConstantRange PosRes = getEmpty(); 1252 if (!PosL.isEmptySet() && !PosR.isEmptySet()) 1253 // pos / pos = pos. 1254 PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1), 1255 (PosL.Upper - 1).sdiv(PosR.Lower) + 1); 1256 1257 if (!NegL.isEmptySet() && !NegR.isEmptySet()) { 1258 // neg / neg = pos. 1259 // 1260 // We need to deal with one tricky case here: SignedMin / -1 is UB on the 1261 // IR level, so we'll want to exclude this case when calculating bounds. 1262 // (For APInts the operation is well-defined and yields SignedMin.) We 1263 // handle this by dropping either SignedMin from the LHS or -1 from the RHS. 1264 APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower); 1265 if (NegL.Lower.isMinSignedValue() && NegR.Upper.isZero()) { 1266 // Remove -1 from the LHS. Skip if it's the only element, as this would 1267 // leave us with an empty set. 1268 if (!NegR.Lower.isAllOnes()) { 1269 APInt AdjNegRUpper; 1270 if (RHS.Lower.isAllOnes()) 1271 // Negative part of [-1, X] without -1 is [SignedMin, X]. 1272 AdjNegRUpper = RHS.Upper; 1273 else 1274 // [X, -1] without -1 is [X, -2]. 1275 AdjNegRUpper = NegR.Upper - 1; 1276 1277 PosRes = PosRes.unionWith( 1278 ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1)); 1279 } 1280 1281 // Remove SignedMin from the RHS. Skip if it's the only element, as this 1282 // would leave us with an empty set. 1283 if (NegL.Upper != SignedMin + 1) { 1284 APInt AdjNegLLower; 1285 if (Upper == SignedMin + 1) 1286 // Negative part of [X, SignedMin] without SignedMin is [X, -1]. 1287 AdjNegLLower = Lower; 1288 else 1289 // [SignedMin, X] without SignedMin is [SignedMin + 1, X]. 1290 AdjNegLLower = NegL.Lower + 1; 1291 1292 PosRes = PosRes.unionWith( 1293 ConstantRange(std::move(Lo), 1294 AdjNegLLower.sdiv(NegR.Upper - 1) + 1)); 1295 } 1296 } else { 1297 PosRes = PosRes.unionWith( 1298 ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1)); 1299 } 1300 } 1301 1302 ConstantRange NegRes = getEmpty(); 1303 if (!PosL.isEmptySet() && !NegR.isEmptySet()) 1304 // pos / neg = neg. 1305 NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1), 1306 PosL.Lower.sdiv(NegR.Lower) + 1); 1307 1308 if (!NegL.isEmptySet() && !PosR.isEmptySet()) 1309 // neg / pos = neg. 1310 NegRes = NegRes.unionWith( 1311 ConstantRange(NegL.Lower.sdiv(PosR.Lower), 1312 (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1)); 1313 1314 // Prefer a non-wrapping signed range here. 1315 ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed); 1316 1317 // Preserve the zero that we dropped when splitting the LHS by sign. 1318 if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet())) 1319 Res = Res.unionWith(ConstantRange(Zero)); 1320 return Res; 1321 } 1322 1323 ConstantRange ConstantRange::urem(const ConstantRange &RHS) const { 1324 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero()) 1325 return getEmpty(); 1326 1327 if (const APInt *RHSInt = RHS.getSingleElement()) { 1328 // UREM by null is UB. 1329 if (RHSInt->isZero()) 1330 return getEmpty(); 1331 // Use APInt's implementation of UREM for single element ranges. 1332 if (const APInt *LHSInt = getSingleElement()) 1333 return {LHSInt->urem(*RHSInt)}; 1334 } 1335 1336 // L % R for L < R is L. 1337 if (getUnsignedMax().ult(RHS.getUnsignedMin())) 1338 return *this; 1339 1340 // L % R is <= L and < R. 1341 APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1; 1342 return getNonEmpty(APInt::getZero(getBitWidth()), std::move(Upper)); 1343 } 1344 1345 ConstantRange ConstantRange::srem(const ConstantRange &RHS) const { 1346 if (isEmptySet() || RHS.isEmptySet()) 1347 return getEmpty(); 1348 1349 if (const APInt *RHSInt = RHS.getSingleElement()) { 1350 // SREM by null is UB. 1351 if (RHSInt->isZero()) 1352 return getEmpty(); 1353 // Use APInt's implementation of SREM for single element ranges. 1354 if (const APInt *LHSInt = getSingleElement()) 1355 return {LHSInt->srem(*RHSInt)}; 1356 } 1357 1358 ConstantRange AbsRHS = RHS.abs(); 1359 APInt MinAbsRHS = AbsRHS.getUnsignedMin(); 1360 APInt MaxAbsRHS = AbsRHS.getUnsignedMax(); 1361 1362 // Modulus by zero is UB. 1363 if (MaxAbsRHS.isZero()) 1364 return getEmpty(); 1365 1366 if (MinAbsRHS.isZero()) 1367 ++MinAbsRHS; 1368 1369 APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax(); 1370 1371 if (MinLHS.isNonNegative()) { 1372 // L % R for L < R is L. 1373 if (MaxLHS.ult(MinAbsRHS)) 1374 return *this; 1375 1376 // L % R is <= L and < R. 1377 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1; 1378 return ConstantRange(APInt::getZero(getBitWidth()), std::move(Upper)); 1379 } 1380 1381 // Same basic logic as above, but the result is negative. 1382 if (MaxLHS.isNegative()) { 1383 if (MinLHS.ugt(-MinAbsRHS)) 1384 return *this; 1385 1386 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1); 1387 return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1)); 1388 } 1389 1390 // LHS range crosses zero. 1391 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1); 1392 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1; 1393 return ConstantRange(std::move(Lower), std::move(Upper)); 1394 } 1395 1396 ConstantRange ConstantRange::binaryNot() const { 1397 return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this); 1398 } 1399 1400 ConstantRange ConstantRange::binaryAnd(const ConstantRange &Other) const { 1401 if (isEmptySet() || Other.isEmptySet()) 1402 return getEmpty(); 1403 1404 ConstantRange KnownBitsRange = 1405 fromKnownBits(toKnownBits() & Other.toKnownBits(), false); 1406 ConstantRange UMinUMaxRange = 1407 getNonEmpty(APInt::getZero(getBitWidth()), 1408 APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()) + 1); 1409 return KnownBitsRange.intersectWith(UMinUMaxRange); 1410 } 1411 1412 ConstantRange ConstantRange::binaryOr(const ConstantRange &Other) const { 1413 if (isEmptySet() || Other.isEmptySet()) 1414 return getEmpty(); 1415 1416 ConstantRange KnownBitsRange = 1417 fromKnownBits(toKnownBits() | Other.toKnownBits(), false); 1418 // Upper wrapped range. 1419 ConstantRange UMaxUMinRange = 1420 getNonEmpty(APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()), 1421 APInt::getZero(getBitWidth())); 1422 return KnownBitsRange.intersectWith(UMaxUMinRange); 1423 } 1424 1425 ConstantRange ConstantRange::binaryXor(const ConstantRange &Other) const { 1426 if (isEmptySet() || Other.isEmptySet()) 1427 return getEmpty(); 1428 1429 // Use APInt's implementation of XOR for single element ranges. 1430 if (isSingleElement() && Other.isSingleElement()) 1431 return {*getSingleElement() ^ *Other.getSingleElement()}; 1432 1433 // Special-case binary complement, since we can give a precise answer. 1434 if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes()) 1435 return binaryNot(); 1436 if (isSingleElement() && getSingleElement()->isAllOnes()) 1437 return Other.binaryNot(); 1438 1439 return fromKnownBits(toKnownBits() ^ Other.toKnownBits(), /*IsSigned*/false); 1440 } 1441 1442 ConstantRange 1443 ConstantRange::shl(const ConstantRange &Other) const { 1444 if (isEmptySet() || Other.isEmptySet()) 1445 return getEmpty(); 1446 1447 APInt Min = getUnsignedMin(); 1448 APInt Max = getUnsignedMax(); 1449 if (const APInt *RHS = Other.getSingleElement()) { 1450 unsigned BW = getBitWidth(); 1451 if (RHS->uge(BW)) 1452 return getEmpty(); 1453 1454 unsigned EqualLeadingBits = (Min ^ Max).countLeadingZeros(); 1455 if (RHS->ule(EqualLeadingBits)) 1456 return getNonEmpty(Min << *RHS, (Max << *RHS) + 1); 1457 1458 return getNonEmpty(APInt::getZero(BW), 1459 APInt::getBitsSetFrom(BW, RHS->getZExtValue()) + 1); 1460 } 1461 1462 APInt OtherMax = Other.getUnsignedMax(); 1463 1464 // There's overflow! 1465 if (OtherMax.ugt(Max.countLeadingZeros())) 1466 return getFull(); 1467 1468 // FIXME: implement the other tricky cases 1469 1470 Min <<= Other.getUnsignedMin(); 1471 Max <<= OtherMax; 1472 1473 return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1); 1474 } 1475 1476 ConstantRange 1477 ConstantRange::lshr(const ConstantRange &Other) const { 1478 if (isEmptySet() || Other.isEmptySet()) 1479 return getEmpty(); 1480 1481 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1; 1482 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax()); 1483 return getNonEmpty(std::move(min), std::move(max)); 1484 } 1485 1486 ConstantRange 1487 ConstantRange::ashr(const ConstantRange &Other) const { 1488 if (isEmptySet() || Other.isEmptySet()) 1489 return getEmpty(); 1490 1491 // May straddle zero, so handle both positive and negative cases. 1492 // 'PosMax' is the upper bound of the result of the ashr 1493 // operation, when Upper of the LHS of ashr is a non-negative. 1494 // number. Since ashr of a non-negative number will result in a 1495 // smaller number, the Upper value of LHS is shifted right with 1496 // the minimum value of 'Other' instead of the maximum value. 1497 APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1; 1498 1499 // 'PosMin' is the lower bound of the result of the ashr 1500 // operation, when Lower of the LHS is a non-negative number. 1501 // Since ashr of a non-negative number will result in a smaller 1502 // number, the Lower value of LHS is shifted right with the 1503 // maximum value of 'Other'. 1504 APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax()); 1505 1506 // 'NegMax' is the upper bound of the result of the ashr 1507 // operation, when Upper of the LHS of ashr is a negative number. 1508 // Since 'ashr' of a negative number will result in a bigger 1509 // number, the Upper value of LHS is shifted right with the 1510 // maximum value of 'Other'. 1511 APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1; 1512 1513 // 'NegMin' is the lower bound of the result of the ashr 1514 // operation, when Lower of the LHS of ashr is a negative number. 1515 // Since 'ashr' of a negative number will result in a bigger 1516 // number, the Lower value of LHS is shifted right with the 1517 // minimum value of 'Other'. 1518 APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin()); 1519 1520 APInt max, min; 1521 if (getSignedMin().isNonNegative()) { 1522 // Upper and Lower of LHS are non-negative. 1523 min = PosMin; 1524 max = PosMax; 1525 } else if (getSignedMax().isNegative()) { 1526 // Upper and Lower of LHS are negative. 1527 min = NegMin; 1528 max = NegMax; 1529 } else { 1530 // Upper is non-negative and Lower is negative. 1531 min = NegMin; 1532 max = PosMax; 1533 } 1534 return getNonEmpty(std::move(min), std::move(max)); 1535 } 1536 1537 ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const { 1538 if (isEmptySet() || Other.isEmptySet()) 1539 return getEmpty(); 1540 1541 APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin()); 1542 APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1; 1543 return getNonEmpty(std::move(NewL), std::move(NewU)); 1544 } 1545 1546 ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const { 1547 if (isEmptySet() || Other.isEmptySet()) 1548 return getEmpty(); 1549 1550 APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin()); 1551 APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1; 1552 return getNonEmpty(std::move(NewL), std::move(NewU)); 1553 } 1554 1555 ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const { 1556 if (isEmptySet() || Other.isEmptySet()) 1557 return getEmpty(); 1558 1559 APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax()); 1560 APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1; 1561 return getNonEmpty(std::move(NewL), std::move(NewU)); 1562 } 1563 1564 ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const { 1565 if (isEmptySet() || Other.isEmptySet()) 1566 return getEmpty(); 1567 1568 APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax()); 1569 APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1; 1570 return getNonEmpty(std::move(NewL), std::move(NewU)); 1571 } 1572 1573 ConstantRange ConstantRange::umul_sat(const ConstantRange &Other) const { 1574 if (isEmptySet() || Other.isEmptySet()) 1575 return getEmpty(); 1576 1577 APInt NewL = getUnsignedMin().umul_sat(Other.getUnsignedMin()); 1578 APInt NewU = getUnsignedMax().umul_sat(Other.getUnsignedMax()) + 1; 1579 return getNonEmpty(std::move(NewL), std::move(NewU)); 1580 } 1581 1582 ConstantRange ConstantRange::smul_sat(const ConstantRange &Other) const { 1583 if (isEmptySet() || Other.isEmptySet()) 1584 return getEmpty(); 1585 1586 // Because we could be dealing with negative numbers here, the lower bound is 1587 // the smallest of the cartesian product of the lower and upper ranges; 1588 // for example: 1589 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6. 1590 // Similarly for the upper bound, swapping min for max. 1591 1592 APInt Min = getSignedMin(); 1593 APInt Max = getSignedMax(); 1594 APInt OtherMin = Other.getSignedMin(); 1595 APInt OtherMax = Other.getSignedMax(); 1596 1597 auto L = {Min.smul_sat(OtherMin), Min.smul_sat(OtherMax), 1598 Max.smul_sat(OtherMin), Max.smul_sat(OtherMax)}; 1599 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); }; 1600 return getNonEmpty(std::min(L, Compare), std::max(L, Compare) + 1); 1601 } 1602 1603 ConstantRange ConstantRange::ushl_sat(const ConstantRange &Other) const { 1604 if (isEmptySet() || Other.isEmptySet()) 1605 return getEmpty(); 1606 1607 APInt NewL = getUnsignedMin().ushl_sat(Other.getUnsignedMin()); 1608 APInt NewU = getUnsignedMax().ushl_sat(Other.getUnsignedMax()) + 1; 1609 return getNonEmpty(std::move(NewL), std::move(NewU)); 1610 } 1611 1612 ConstantRange ConstantRange::sshl_sat(const ConstantRange &Other) const { 1613 if (isEmptySet() || Other.isEmptySet()) 1614 return getEmpty(); 1615 1616 APInt Min = getSignedMin(), Max = getSignedMax(); 1617 APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax(); 1618 APInt NewL = Min.sshl_sat(Min.isNonNegative() ? ShAmtMin : ShAmtMax); 1619 APInt NewU = Max.sshl_sat(Max.isNegative() ? ShAmtMin : ShAmtMax) + 1; 1620 return getNonEmpty(std::move(NewL), std::move(NewU)); 1621 } 1622 1623 ConstantRange ConstantRange::inverse() const { 1624 if (isFullSet()) 1625 return getEmpty(); 1626 if (isEmptySet()) 1627 return getFull(); 1628 return ConstantRange(Upper, Lower); 1629 } 1630 1631 ConstantRange ConstantRange::abs(bool IntMinIsPoison) const { 1632 if (isEmptySet()) 1633 return getEmpty(); 1634 1635 if (isSignWrappedSet()) { 1636 APInt Lo; 1637 // Check whether the range crosses zero. 1638 if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive()) 1639 Lo = APInt::getZero(getBitWidth()); 1640 else 1641 Lo = APIntOps::umin(Lower, -Upper + 1); 1642 1643 // If SignedMin is not poison, then it is included in the result range. 1644 if (IntMinIsPoison) 1645 return ConstantRange(Lo, APInt::getSignedMinValue(getBitWidth())); 1646 else 1647 return ConstantRange(Lo, APInt::getSignedMinValue(getBitWidth()) + 1); 1648 } 1649 1650 APInt SMin = getSignedMin(), SMax = getSignedMax(); 1651 1652 // Skip SignedMin if it is poison. 1653 if (IntMinIsPoison && SMin.isMinSignedValue()) { 1654 // The range may become empty if it *only* contains SignedMin. 1655 if (SMax.isMinSignedValue()) 1656 return getEmpty(); 1657 ++SMin; 1658 } 1659 1660 // All non-negative. 1661 if (SMin.isNonNegative()) 1662 return *this; 1663 1664 // All negative. 1665 if (SMax.isNegative()) 1666 return ConstantRange(-SMax, -SMin + 1); 1667 1668 // Range crosses zero. 1669 return ConstantRange(APInt::getZero(getBitWidth()), 1670 APIntOps::umax(-SMin, SMax) + 1); 1671 } 1672 1673 ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow( 1674 const ConstantRange &Other) const { 1675 if (isEmptySet() || Other.isEmptySet()) 1676 return OverflowResult::MayOverflow; 1677 1678 APInt Min = getUnsignedMin(), Max = getUnsignedMax(); 1679 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax(); 1680 1681 // a u+ b overflows high iff a u> ~b. 1682 if (Min.ugt(~OtherMin)) 1683 return OverflowResult::AlwaysOverflowsHigh; 1684 if (Max.ugt(~OtherMax)) 1685 return OverflowResult::MayOverflow; 1686 return OverflowResult::NeverOverflows; 1687 } 1688 1689 ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow( 1690 const ConstantRange &Other) const { 1691 if (isEmptySet() || Other.isEmptySet()) 1692 return OverflowResult::MayOverflow; 1693 1694 APInt Min = getSignedMin(), Max = getSignedMax(); 1695 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax(); 1696 1697 APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); 1698 APInt SignedMax = APInt::getSignedMaxValue(getBitWidth()); 1699 1700 // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b. 1701 // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b. 1702 if (Min.isNonNegative() && OtherMin.isNonNegative() && 1703 Min.sgt(SignedMax - OtherMin)) 1704 return OverflowResult::AlwaysOverflowsHigh; 1705 if (Max.isNegative() && OtherMax.isNegative() && 1706 Max.slt(SignedMin - OtherMax)) 1707 return OverflowResult::AlwaysOverflowsLow; 1708 1709 if (Max.isNonNegative() && OtherMax.isNonNegative() && 1710 Max.sgt(SignedMax - OtherMax)) 1711 return OverflowResult::MayOverflow; 1712 if (Min.isNegative() && OtherMin.isNegative() && 1713 Min.slt(SignedMin - OtherMin)) 1714 return OverflowResult::MayOverflow; 1715 1716 return OverflowResult::NeverOverflows; 1717 } 1718 1719 ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow( 1720 const ConstantRange &Other) const { 1721 if (isEmptySet() || Other.isEmptySet()) 1722 return OverflowResult::MayOverflow; 1723 1724 APInt Min = getUnsignedMin(), Max = getUnsignedMax(); 1725 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax(); 1726 1727 // a u- b overflows low iff a u< b. 1728 if (Max.ult(OtherMin)) 1729 return OverflowResult::AlwaysOverflowsLow; 1730 if (Min.ult(OtherMax)) 1731 return OverflowResult::MayOverflow; 1732 return OverflowResult::NeverOverflows; 1733 } 1734 1735 ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow( 1736 const ConstantRange &Other) const { 1737 if (isEmptySet() || Other.isEmptySet()) 1738 return OverflowResult::MayOverflow; 1739 1740 APInt Min = getSignedMin(), Max = getSignedMax(); 1741 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax(); 1742 1743 APInt SignedMin = APInt::getSignedMinValue(getBitWidth()); 1744 APInt SignedMax = APInt::getSignedMaxValue(getBitWidth()); 1745 1746 // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b. 1747 // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b. 1748 if (Min.isNonNegative() && OtherMax.isNegative() && 1749 Min.sgt(SignedMax + OtherMax)) 1750 return OverflowResult::AlwaysOverflowsHigh; 1751 if (Max.isNegative() && OtherMin.isNonNegative() && 1752 Max.slt(SignedMin + OtherMin)) 1753 return OverflowResult::AlwaysOverflowsLow; 1754 1755 if (Max.isNonNegative() && OtherMin.isNegative() && 1756 Max.sgt(SignedMax + OtherMin)) 1757 return OverflowResult::MayOverflow; 1758 if (Min.isNegative() && OtherMax.isNonNegative() && 1759 Min.slt(SignedMin + OtherMax)) 1760 return OverflowResult::MayOverflow; 1761 1762 return OverflowResult::NeverOverflows; 1763 } 1764 1765 ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow( 1766 const ConstantRange &Other) const { 1767 if (isEmptySet() || Other.isEmptySet()) 1768 return OverflowResult::MayOverflow; 1769 1770 APInt Min = getUnsignedMin(), Max = getUnsignedMax(); 1771 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax(); 1772 bool Overflow; 1773 1774 (void) Min.umul_ov(OtherMin, Overflow); 1775 if (Overflow) 1776 return OverflowResult::AlwaysOverflowsHigh; 1777 1778 (void) Max.umul_ov(OtherMax, Overflow); 1779 if (Overflow) 1780 return OverflowResult::MayOverflow; 1781 1782 return OverflowResult::NeverOverflows; 1783 } 1784 1785 void ConstantRange::print(raw_ostream &OS) const { 1786 if (isFullSet()) 1787 OS << "full-set"; 1788 else if (isEmptySet()) 1789 OS << "empty-set"; 1790 else 1791 OS << "[" << Lower << "," << Upper << ")"; 1792 } 1793 1794 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1795 LLVM_DUMP_METHOD void ConstantRange::dump() const { 1796 print(dbgs()); 1797 } 1798 #endif 1799 1800 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) { 1801 const unsigned NumRanges = Ranges.getNumOperands() / 2; 1802 assert(NumRanges >= 1 && "Must have at least one range!"); 1803 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs"); 1804 1805 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0)); 1806 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1)); 1807 1808 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue()); 1809 1810 for (unsigned i = 1; i < NumRanges; ++i) { 1811 auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0)); 1812 auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1)); 1813 1814 // Note: unionWith will potentially create a range that contains values not 1815 // contained in any of the original N ranges. 1816 CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue())); 1817 } 1818 1819 return CR; 1820 } 1821