1 //===- ConstantRange.cpp - ConstantRange implementation -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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):
17 // [F, F) = {} = Empty set
20 // [T, T) = {F, T} = Full set
22 //===----------------------------------------------------------------------===//
24 #include "llvm/ADT/APInt.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/Metadata.h"
30 #include "llvm/IR/Operator.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Support/ErrorHandling.h"
34 #include "llvm/Support/raw_ostream.h"
41 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
42 : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
45 ConstantRange::ConstantRange(APInt V)
46 : Lower(std::move(V)), Upper(Lower + 1) {}
48 ConstantRange::ConstantRange(APInt L, APInt U)
49 : Lower(std::move(L)), Upper(std::move(U)) {
50 assert(Lower.getBitWidth() == Upper.getBitWidth() &&
51 "ConstantRange with unequal bit widths");
52 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
53 "Lower == Upper, but they aren't min or max value!");
56 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
57 const ConstantRange &CR) {
61 uint32_t W = CR.getBitWidth();
64 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
65 case CmpInst::ICMP_EQ:
67 case CmpInst::ICMP_NE:
68 if (CR.isSingleElement())
69 return ConstantRange(CR.getUpper(), CR.getLower());
70 return ConstantRange(W);
71 case CmpInst::ICMP_ULT: {
72 APInt UMax(CR.getUnsignedMax());
73 if (UMax.isMinValue())
74 return ConstantRange(W, /* empty */ false);
75 return ConstantRange(APInt::getMinValue(W), std::move(UMax));
77 case CmpInst::ICMP_SLT: {
78 APInt SMax(CR.getSignedMax());
79 if (SMax.isMinSignedValue())
80 return ConstantRange(W, /* empty */ false);
81 return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
83 case CmpInst::ICMP_ULE: {
84 APInt UMax(CR.getUnsignedMax());
85 if (UMax.isMaxValue())
86 return ConstantRange(W);
87 return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
89 case CmpInst::ICMP_SLE: {
90 APInt SMax(CR.getSignedMax());
91 if (SMax.isMaxSignedValue())
92 return ConstantRange(W);
93 return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
95 case CmpInst::ICMP_UGT: {
96 APInt UMin(CR.getUnsignedMin());
97 if (UMin.isMaxValue())
98 return ConstantRange(W, /* empty */ false);
99 return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
101 case CmpInst::ICMP_SGT: {
102 APInt SMin(CR.getSignedMin());
103 if (SMin.isMaxSignedValue())
104 return ConstantRange(W, /* empty */ false);
105 return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
107 case CmpInst::ICMP_UGE: {
108 APInt UMin(CR.getUnsignedMin());
109 if (UMin.isMinValue())
110 return ConstantRange(W);
111 return ConstantRange(std::move(UMin), APInt::getNullValue(W));
113 case CmpInst::ICMP_SGE: {
114 APInt SMin(CR.getSignedMin());
115 if (SMin.isMinSignedValue())
116 return ConstantRange(W);
117 return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
122 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
123 const ConstantRange &CR) {
124 // Follows from De-Morgan's laws:
126 // ~(~A union ~B) == A intersect B.
128 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
132 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
134 // Computes the exact range that is equal to both the constant ranges returned
135 // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
136 // when RHS is a singleton such as an APInt and so the assert is valid.
137 // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
138 // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
140 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
141 return makeAllowedICmpRegion(Pred, C);
144 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
146 bool Success = false;
148 if (isFullSet() || isEmptySet()) {
149 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
150 RHS = APInt(getBitWidth(), 0);
152 } else if (auto *OnlyElt = getSingleElement()) {
153 Pred = CmpInst::ICMP_EQ;
156 } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
157 Pred = CmpInst::ICMP_NE;
158 RHS = *OnlyMissingElt;
160 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
162 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
165 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
167 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
172 assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
179 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
180 const ConstantRange &Other,
181 unsigned NoWrapKind) {
182 using OBO = OverflowingBinaryOperator;
184 // Computes the intersection of CR0 and CR1. It is different from
185 // intersectWith in that the ConstantRange returned will only contain elements
186 // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
187 // not, of both X and Y).
188 auto SubsetIntersect =
189 [](const ConstantRange &CR0, const ConstantRange &CR1) {
190 return CR0.inverse().unionWith(CR1.inverse()).inverse();
193 assert(BinOp >= Instruction::BinaryOpsBegin &&
194 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
196 assert((NoWrapKind == OBO::NoSignedWrap ||
197 NoWrapKind == OBO::NoUnsignedWrap ||
198 NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
199 "NoWrapKind invalid!");
201 unsigned BitWidth = Other.getBitWidth();
202 if (BinOp != Instruction::Add)
203 // Conservative answer: empty set
204 return ConstantRange(BitWidth, false);
206 if (auto *C = Other.getSingleElement())
207 if (C->isNullValue())
208 // Full set: nothing signed / unsigned wraps when added to 0.
209 return ConstantRange(BitWidth);
211 ConstantRange Result(BitWidth);
213 if (NoWrapKind & OBO::NoUnsignedWrap)
215 SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
216 -Other.getUnsignedMax()));
218 if (NoWrapKind & OBO::NoSignedWrap) {
219 const APInt &SignedMin = Other.getSignedMin();
220 const APInt &SignedMax = Other.getSignedMax();
222 if (SignedMax.isStrictlyPositive())
223 Result = SubsetIntersect(
225 ConstantRange(APInt::getSignedMinValue(BitWidth),
226 APInt::getSignedMinValue(BitWidth) - SignedMax));
228 if (SignedMin.isNegative())
229 Result = SubsetIntersect(
230 Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
231 APInt::getSignedMinValue(BitWidth)));
237 bool ConstantRange::isFullSet() const {
238 return Lower == Upper && Lower.isMaxValue();
241 bool ConstantRange::isEmptySet() const {
242 return Lower == Upper && Lower.isMinValue();
245 bool ConstantRange::isWrappedSet() const {
246 return Lower.ugt(Upper);
249 bool ConstantRange::isSignWrappedSet() const {
250 return contains(APInt::getSignedMaxValue(getBitWidth())) &&
251 contains(APInt::getSignedMinValue(getBitWidth()));
254 APInt ConstantRange::getSetSize() const {
256 return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
258 // This is also correct for wrapped sets.
259 return (Upper - Lower).zext(getBitWidth()+1);
263 ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
264 assert(getBitWidth() == Other.getBitWidth());
267 if (Other.isFullSet())
269 return (Upper - Lower).ult(Other.Upper - Other.Lower);
273 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
274 assert(MaxSize && "MaxSize can't be 0.");
275 // If this a full set, we need special handling to avoid needing an extra bit
276 // to represent the size.
278 return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
280 return (Upper - Lower).ugt(MaxSize);
283 APInt ConstantRange::getUnsignedMax() const {
284 if (isFullSet() || isWrappedSet())
285 return APInt::getMaxValue(getBitWidth());
286 return getUpper() - 1;
289 APInt ConstantRange::getUnsignedMin() const {
290 if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
291 return APInt::getMinValue(getBitWidth());
295 APInt ConstantRange::getSignedMax() const {
296 if (isFullSet() || Lower.sgt(Upper))
297 return APInt::getSignedMaxValue(getBitWidth());
298 return getUpper() - 1;
301 APInt ConstantRange::getSignedMin() const {
302 if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
303 return APInt::getSignedMinValue(getBitWidth());
307 bool ConstantRange::contains(const APInt &V) const {
312 return Lower.ule(V) && V.ult(Upper);
313 return Lower.ule(V) || V.ult(Upper);
316 bool ConstantRange::contains(const ConstantRange &Other) const {
317 if (isFullSet() || Other.isEmptySet()) return true;
318 if (isEmptySet() || Other.isFullSet()) return false;
320 if (!isWrappedSet()) {
321 if (Other.isWrappedSet())
324 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
327 if (!Other.isWrappedSet())
328 return Other.getUpper().ule(Upper) ||
329 Lower.ule(Other.getLower());
331 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
334 ConstantRange ConstantRange::subtract(const APInt &Val) const {
335 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
336 // If the set is empty or full, don't modify the endpoints.
339 return ConstantRange(Lower - Val, Upper - Val);
342 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
343 return intersectWith(CR.inverse());
346 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
347 assert(getBitWidth() == CR.getBitWidth() &&
348 "ConstantRange types don't agree!");
350 // Handle common cases.
351 if ( isEmptySet() || CR.isFullSet()) return *this;
352 if (CR.isEmptySet() || isFullSet()) return CR;
354 if (!isWrappedSet() && CR.isWrappedSet())
355 return CR.intersectWith(*this);
357 if (!isWrappedSet() && !CR.isWrappedSet()) {
358 if (Lower.ult(CR.Lower)) {
359 if (Upper.ule(CR.Lower))
360 return ConstantRange(getBitWidth(), false);
362 if (Upper.ult(CR.Upper))
363 return ConstantRange(CR.Lower, Upper);
367 if (Upper.ult(CR.Upper))
370 if (Lower.ult(CR.Upper))
371 return ConstantRange(Lower, CR.Upper);
373 return ConstantRange(getBitWidth(), false);
376 if (isWrappedSet() && !CR.isWrappedSet()) {
377 if (CR.Lower.ult(Upper)) {
378 if (CR.Upper.ult(Upper))
381 if (CR.Upper.ule(Lower))
382 return ConstantRange(CR.Lower, Upper);
384 if (isSizeStrictlySmallerThan(CR))
388 if (CR.Lower.ult(Lower)) {
389 if (CR.Upper.ule(Lower))
390 return ConstantRange(getBitWidth(), false);
392 return ConstantRange(Lower, CR.Upper);
397 if (CR.Upper.ult(Upper)) {
398 if (CR.Lower.ult(Upper)) {
399 if (isSizeStrictlySmallerThan(CR))
404 if (CR.Lower.ult(Lower))
405 return ConstantRange(Lower, CR.Upper);
409 if (CR.Upper.ule(Lower)) {
410 if (CR.Lower.ult(Lower))
413 return ConstantRange(CR.Lower, Upper);
415 if (isSizeStrictlySmallerThan(CR))
420 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
421 assert(getBitWidth() == CR.getBitWidth() &&
422 "ConstantRange types don't agree!");
424 if ( isFullSet() || CR.isEmptySet()) return *this;
425 if (CR.isFullSet() || isEmptySet()) return CR;
427 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
429 if (!isWrappedSet() && !CR.isWrappedSet()) {
430 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
431 // If the two ranges are disjoint, find the smaller gap and bridge it.
432 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
434 return ConstantRange(Lower, CR.Upper);
435 return ConstantRange(CR.Lower, Upper);
438 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
439 APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
441 if (L.isNullValue() && U.isNullValue())
442 return ConstantRange(getBitWidth());
444 return ConstantRange(std::move(L), std::move(U));
447 if (!CR.isWrappedSet()) {
448 // ------U L----- and ------U L----- : this
450 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
453 // ------U L----- : this
455 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
456 return ConstantRange(getBitWidth());
458 // ----U L---- : this
461 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
462 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
464 return ConstantRange(Lower, CR.Upper);
465 return ConstantRange(CR.Lower, Upper);
468 // ----U L----- : this
470 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
471 return ConstantRange(CR.Lower, Upper);
473 // ------U L---- : this
475 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
476 "ConstantRange::unionWith missed a case with one range wrapped");
477 return ConstantRange(Lower, CR.Upper);
480 // ------U L---- and ------U L---- : this
481 // -U L----------- and ------------U L : CR
482 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
483 return ConstantRange(getBitWidth());
485 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
486 APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
488 return ConstantRange(std::move(L), std::move(U));
491 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
492 uint32_t ResultBitWidth) const {
495 llvm_unreachable("unsupported cast type");
496 case Instruction::Trunc:
497 return truncate(ResultBitWidth);
498 case Instruction::SExt:
499 return signExtend(ResultBitWidth);
500 case Instruction::ZExt:
501 return zeroExtend(ResultBitWidth);
502 case Instruction::BitCast:
504 case Instruction::FPToUI:
505 case Instruction::FPToSI:
506 if (getBitWidth() == ResultBitWidth)
509 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
510 case Instruction::UIToFP: {
511 // TODO: use input range if available
512 auto BW = getBitWidth();
513 APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
514 APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
515 return ConstantRange(std::move(Min), std::move(Max));
517 case Instruction::SIToFP: {
518 // TODO: use input range if available
519 auto BW = getBitWidth();
520 APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
521 APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
522 return ConstantRange(std::move(SMin), std::move(SMax));
524 case Instruction::FPTrunc:
525 case Instruction::FPExt:
526 case Instruction::IntToPtr:
527 case Instruction::PtrToInt:
528 case Instruction::AddrSpaceCast:
529 // Conservatively return full set.
530 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
534 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
535 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
537 unsigned SrcTySize = getBitWidth();
538 assert(SrcTySize < DstTySize && "Not a value extension");
539 if (isFullSet() || isWrappedSet()) {
540 // Change into [0, 1 << src bit width)
541 APInt LowerExt(DstTySize, 0);
542 if (!Upper) // special case: [X, 0) -- not really wrapping around
543 LowerExt = Lower.zext(DstTySize);
544 return ConstantRange(std::move(LowerExt),
545 APInt::getOneBitSet(DstTySize, SrcTySize));
548 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
551 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
552 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
554 unsigned SrcTySize = getBitWidth();
555 assert(SrcTySize < DstTySize && "Not a value extension");
557 // special case: [X, INT_MIN) -- not really wrapping around
558 if (Upper.isMinSignedValue())
559 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
561 if (isFullSet() || isSignWrappedSet()) {
562 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
563 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
566 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
569 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
570 assert(getBitWidth() > DstTySize && "Not a value truncation");
572 return ConstantRange(DstTySize, /*isFullSet=*/false);
574 return ConstantRange(DstTySize, /*isFullSet=*/true);
576 APInt LowerDiv(Lower), UpperDiv(Upper);
577 ConstantRange Union(DstTySize, /*isFullSet=*/false);
579 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
580 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
581 // then we do the union with [MaxValue, Upper)
582 if (isWrappedSet()) {
583 // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
585 if (Upper.getActiveBits() > DstTySize ||
586 Upper.countTrailingOnes() == DstTySize)
587 return ConstantRange(DstTySize, /*isFullSet=*/true);
589 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
590 UpperDiv.setAllBits();
592 // Union covers the MaxValue case, so return if the remaining range is just
594 if (LowerDiv == UpperDiv)
598 // Chop off the most significant bits that are past the destination bitwidth.
599 if (LowerDiv.getActiveBits() > DstTySize) {
600 // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
601 APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
606 unsigned UpperDivWidth = UpperDiv.getActiveBits();
607 if (UpperDivWidth <= DstTySize)
608 return ConstantRange(LowerDiv.trunc(DstTySize),
609 UpperDiv.trunc(DstTySize)).unionWith(Union);
611 // The truncated value wraps around. Check if we can do better than fullset.
612 if (UpperDivWidth == DstTySize + 1) {
613 // Clear the MSB so that UpperDiv wraps around.
614 UpperDiv.clearBit(DstTySize);
615 if (UpperDiv.ult(LowerDiv))
616 return ConstantRange(LowerDiv.trunc(DstTySize),
617 UpperDiv.trunc(DstTySize)).unionWith(Union);
620 return ConstantRange(DstTySize, /*isFullSet=*/true);
623 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
624 unsigned SrcTySize = getBitWidth();
625 if (SrcTySize > DstTySize)
626 return truncate(DstTySize);
627 if (SrcTySize < DstTySize)
628 return zeroExtend(DstTySize);
632 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
633 unsigned SrcTySize = getBitWidth();
634 if (SrcTySize > DstTySize)
635 return truncate(DstTySize);
636 if (SrcTySize < DstTySize)
637 return signExtend(DstTySize);
641 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
642 const ConstantRange &Other) const {
643 assert(BinOp >= Instruction::BinaryOpsBegin &&
644 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
647 case Instruction::Add:
649 case Instruction::Sub:
651 case Instruction::Mul:
652 return multiply(Other);
653 case Instruction::UDiv:
655 case Instruction::Shl:
657 case Instruction::LShr:
659 case Instruction::And:
660 return binaryAnd(Other);
661 case Instruction::Or:
662 return binaryOr(Other);
663 // Note: floating point operations applied to abstract ranges are just
664 // ideal integer operations with a lossy representation
665 case Instruction::FAdd:
667 case Instruction::FSub:
669 case Instruction::FMul:
670 return multiply(Other);
672 // Conservatively return full set.
673 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
678 ConstantRange::add(const ConstantRange &Other) const {
679 if (isEmptySet() || Other.isEmptySet())
680 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
681 if (isFullSet() || Other.isFullSet())
682 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
684 APInt NewLower = getLower() + Other.getLower();
685 APInt NewUpper = getUpper() + Other.getUpper() - 1;
686 if (NewLower == NewUpper)
687 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
689 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
690 if (X.isSizeStrictlySmallerThan(*this) ||
691 X.isSizeStrictlySmallerThan(Other))
692 // We've wrapped, therefore, full set.
693 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
697 ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
698 // Calculate the subset of this range such that "X + Other" is
699 // guaranteed not to wrap (overflow) for all X in this subset.
700 // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
701 // passing a single element range.
702 auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
703 ConstantRange(Other),
704 OverflowingBinaryOperator::NoSignedWrap);
705 auto NSWConstrainedRange = intersectWith(NSWRange);
707 return NSWConstrainedRange.add(ConstantRange(Other));
711 ConstantRange::sub(const ConstantRange &Other) const {
712 if (isEmptySet() || Other.isEmptySet())
713 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
714 if (isFullSet() || Other.isFullSet())
715 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
717 APInt NewLower = getLower() - Other.getUpper() + 1;
718 APInt NewUpper = getUpper() - Other.getLower();
719 if (NewLower == NewUpper)
720 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
722 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
723 if (X.isSizeStrictlySmallerThan(*this) ||
724 X.isSizeStrictlySmallerThan(Other))
725 // We've wrapped, therefore, full set.
726 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
731 ConstantRange::multiply(const ConstantRange &Other) const {
732 // TODO: If either operand is a single element and the multiply is known to
733 // be non-wrapping, round the result min and max value to the appropriate
734 // multiple of that element. If wrapping is possible, at least adjust the
735 // range according to the greatest power-of-two factor of the single element.
737 if (isEmptySet() || Other.isEmptySet())
738 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
740 // Multiplication is signedness-independent. However different ranges can be
741 // obtained depending on how the input ranges are treated. These different
742 // ranges are all conservatively correct, but one might be better than the
743 // other. We calculate two ranges; one treating the inputs as unsigned
744 // and the other signed, then return the smallest of these ranges.
746 // Unsigned range first.
747 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
748 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
749 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
750 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
752 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
753 this_max * Other_max + 1);
754 ConstantRange UR = Result_zext.truncate(getBitWidth());
756 // If the unsigned range doesn't wrap, and isn't negative then it's a range
757 // from one positive number to another which is as good as we can generate.
758 // In this case, skip the extra work of generating signed ranges which aren't
759 // going to be better than this range.
760 if (!UR.isWrappedSet() &&
761 (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
764 // Now the signed range. Because we could be dealing with negative numbers
765 // here, the lower bound is the smallest of the cartesian product of the
766 // lower and upper ranges; for example:
767 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
768 // Similarly for the upper bound, swapping min for max.
770 this_min = getSignedMin().sext(getBitWidth() * 2);
771 this_max = getSignedMax().sext(getBitWidth() * 2);
772 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
773 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
775 auto L = {this_min * Other_min, this_min * Other_max,
776 this_max * Other_min, this_max * Other_max};
777 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
778 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
779 ConstantRange SR = Result_sext.truncate(getBitWidth());
781 return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
785 ConstantRange::smax(const ConstantRange &Other) const {
786 // X smax Y is: range(smax(X_smin, Y_smin),
787 // smax(X_smax, Y_smax))
788 if (isEmptySet() || Other.isEmptySet())
789 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
790 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
791 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
793 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
794 return ConstantRange(std::move(NewL), std::move(NewU));
798 ConstantRange::umax(const ConstantRange &Other) const {
799 // X umax Y is: range(umax(X_umin, Y_umin),
800 // umax(X_umax, Y_umax))
801 if (isEmptySet() || Other.isEmptySet())
802 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
803 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
804 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
806 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
807 return ConstantRange(std::move(NewL), std::move(NewU));
811 ConstantRange::smin(const ConstantRange &Other) const {
812 // X smin Y is: range(smin(X_smin, Y_smin),
813 // smin(X_smax, Y_smax))
814 if (isEmptySet() || Other.isEmptySet())
815 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
816 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
817 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
819 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
820 return ConstantRange(std::move(NewL), std::move(NewU));
824 ConstantRange::umin(const ConstantRange &Other) const {
825 // X umin Y is: range(umin(X_umin, Y_umin),
826 // umin(X_umax, Y_umax))
827 if (isEmptySet() || Other.isEmptySet())
828 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
829 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
830 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
832 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
833 return ConstantRange(std::move(NewL), std::move(NewU));
837 ConstantRange::udiv(const ConstantRange &RHS) const {
838 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
839 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
841 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
843 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
845 APInt RHS_umin = RHS.getUnsignedMin();
846 if (RHS_umin.isNullValue()) {
847 // We want the lowest value in RHS excluding zero. Usually that would be 1
848 // except for a range in the form of [X, 1) in which case it would be X.
849 if (RHS.getUpper() == 1)
850 RHS_umin = RHS.getLower();
855 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
857 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
860 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
862 return ConstantRange(std::move(Lower), std::move(Upper));
866 ConstantRange::binaryAnd(const ConstantRange &Other) const {
867 if (isEmptySet() || Other.isEmptySet())
868 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
870 // TODO: replace this with something less conservative
872 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
873 if (umin.isAllOnesValue())
874 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
875 return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
879 ConstantRange::binaryOr(const ConstantRange &Other) const {
880 if (isEmptySet() || Other.isEmptySet())
881 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
883 // TODO: replace this with something less conservative
885 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
886 if (umax.isNullValue())
887 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
888 return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
892 ConstantRange::shl(const ConstantRange &Other) const {
893 if (isEmptySet() || Other.isEmptySet())
894 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
896 APInt max = getUnsignedMax();
897 APInt Other_umax = Other.getUnsignedMax();
900 if (Other_umax.uge(max.countLeadingZeros()))
901 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
903 // FIXME: implement the other tricky cases
905 APInt min = getUnsignedMin();
906 min <<= Other.getUnsignedMin();
909 return ConstantRange(std::move(min), std::move(max) + 1);
913 ConstantRange::lshr(const ConstantRange &Other) const {
914 if (isEmptySet() || Other.isEmptySet())
915 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
917 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
918 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
920 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
922 return ConstantRange(std::move(min), std::move(max));
925 ConstantRange ConstantRange::inverse() const {
927 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
929 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
930 return ConstantRange(Upper, Lower);
933 void ConstantRange::print(raw_ostream &OS) const {
936 else if (isEmptySet())
939 OS << "[" << Lower << "," << Upper << ")";
942 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
943 LLVM_DUMP_METHOD void ConstantRange::dump() const {
948 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
949 const unsigned NumRanges = Ranges.getNumOperands() / 2;
950 assert(NumRanges >= 1 && "Must have at least one range!");
951 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
953 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
954 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
956 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
958 for (unsigned i = 1; i < NumRanges; ++i) {
959 auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
960 auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
962 // Note: unionWith will potentially create a range that contains values not
963 // contained in any of the original N ranges.
964 CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));