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