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