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/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"
32 /// Initialize a full (the default) or empty set for the specified type.
34 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) {
36 Lower = Upper = APInt::getMaxValue(BitWidth);
38 Lower = Upper = APInt::getMinValue(BitWidth);
41 /// Initialize a range to hold the single specified value.
43 ConstantRange::ConstantRange(APIntMoveTy V)
44 : Lower(std::move(V)), Upper(Lower + 1) {}
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!");
54 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
55 const ConstantRange &CR) {
59 uint32_t W = CR.getBitWidth();
62 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
63 case CmpInst::ICMP_EQ:
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);
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);
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);
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);
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));
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));
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));
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));
120 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
121 const ConstantRange &CR) {
122 // Follows from De-Morgan's laws:
124 // ~(~A union ~B) == A intersect B.
126 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
130 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
132 // Computes the exact range that is equal to both the constant ranges returned
133 // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
134 // when RHS is a singleton such as an APInt and so the assert is valid.
135 // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
136 // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
138 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
139 return makeAllowedICmpRegion(Pred, C);
142 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
144 bool Success = false;
146 if (isFullSet() || isEmptySet()) {
147 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
148 RHS = APInt(getBitWidth(), 0);
150 } else if (auto *OnlyElt = getSingleElement()) {
151 Pred = CmpInst::ICMP_EQ;
154 } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
155 Pred = CmpInst::ICMP_NE;
156 RHS = *OnlyMissingElt;
158 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
160 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
163 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
165 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
170 assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
177 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
178 const ConstantRange &Other,
179 unsigned NoWrapKind) {
180 typedef OverflowingBinaryOperator OBO;
182 // Computes the intersection of CR0 and CR1. It is different from
183 // intersectWith in that the ConstantRange returned will only contain elements
184 // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
185 // not, of both X and Y).
186 auto SubsetIntersect =
187 [](const ConstantRange &CR0, const ConstantRange &CR1) {
188 return CR0.inverse().unionWith(CR1.inverse()).inverse();
191 assert(BinOp >= Instruction::BinaryOpsBegin &&
192 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
194 assert((NoWrapKind == OBO::NoSignedWrap ||
195 NoWrapKind == OBO::NoUnsignedWrap ||
196 NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
197 "NoWrapKind invalid!");
199 unsigned BitWidth = Other.getBitWidth();
200 if (BinOp != Instruction::Add)
201 // Conservative answer: empty set
202 return ConstantRange(BitWidth, false);
204 if (auto *C = Other.getSingleElement())
206 // Full set: nothing signed / unsigned wraps when added to 0.
207 return ConstantRange(BitWidth);
209 ConstantRange Result(BitWidth);
211 if (NoWrapKind & OBO::NoUnsignedWrap)
213 SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
214 -Other.getUnsignedMax()));
216 if (NoWrapKind & OBO::NoSignedWrap) {
217 APInt SignedMin = Other.getSignedMin();
218 APInt SignedMax = Other.getSignedMax();
220 if (SignedMax.isStrictlyPositive())
221 Result = SubsetIntersect(
223 ConstantRange(APInt::getSignedMinValue(BitWidth),
224 APInt::getSignedMinValue(BitWidth) - SignedMax));
226 if (SignedMin.isNegative())
227 Result = SubsetIntersect(
228 Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
229 APInt::getSignedMinValue(BitWidth)));
235 /// isFullSet - Return true if this set contains all of the elements possible
236 /// for this data-type
237 bool ConstantRange::isFullSet() const {
238 return Lower == Upper && Lower.isMaxValue();
241 /// isEmptySet - Return true if this set contains no members.
243 bool ConstantRange::isEmptySet() const {
244 return Lower == Upper && Lower.isMinValue();
247 /// isWrappedSet - Return true if this set wraps around the top of the range,
248 /// for example: [100, 8)
250 bool ConstantRange::isWrappedSet() const {
251 return Lower.ugt(Upper);
254 /// isSignWrappedSet - Return true if this set wraps around the INT_MIN of
255 /// its bitwidth, for example: i8 [120, 140).
257 bool ConstantRange::isSignWrappedSet() const {
258 return contains(APInt::getSignedMaxValue(getBitWidth())) &&
259 contains(APInt::getSignedMinValue(getBitWidth()));
262 /// getSetSize - Return the number of elements in this set.
264 APInt ConstantRange::getSetSize() const {
266 APInt Size(getBitWidth()+1, 0);
267 Size.setBit(getBitWidth());
271 // This is also correct for wrapped sets.
272 return (Upper - Lower).zext(getBitWidth()+1);
275 /// getUnsignedMax - Return the largest unsigned value contained in the
278 APInt ConstantRange::getUnsignedMax() const {
279 if (isFullSet() || isWrappedSet())
280 return APInt::getMaxValue(getBitWidth());
281 return getUpper() - 1;
284 /// getUnsignedMin - Return the smallest unsigned value contained in the
287 APInt ConstantRange::getUnsignedMin() const {
288 if (isFullSet() || (isWrappedSet() && getUpper() != 0))
289 return APInt::getMinValue(getBitWidth());
293 /// getSignedMax - Return the largest signed value contained in the
296 APInt ConstantRange::getSignedMax() const {
297 APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
298 if (!isWrappedSet()) {
299 if (getLower().sle(getUpper() - 1))
300 return getUpper() - 1;
303 if (getLower().isNegative() == getUpper().isNegative())
305 return getUpper() - 1;
308 /// getSignedMin - Return the smallest signed value contained in the
311 APInt ConstantRange::getSignedMin() const {
312 APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
313 if (!isWrappedSet()) {
314 if (getLower().sle(getUpper() - 1))
318 if ((getUpper() - 1).slt(getLower())) {
319 if (getUpper() != SignedMin)
325 /// contains - Return true if the specified value is in the set.
327 bool ConstantRange::contains(const APInt &V) const {
332 return Lower.ule(V) && V.ult(Upper);
333 return Lower.ule(V) || V.ult(Upper);
336 /// contains - Return true if the argument is a subset of this range.
337 /// Two equal sets contain each other. The empty set contained by all other
340 bool ConstantRange::contains(const ConstantRange &Other) const {
341 if (isFullSet() || Other.isEmptySet()) return true;
342 if (isEmptySet() || Other.isFullSet()) return false;
344 if (!isWrappedSet()) {
345 if (Other.isWrappedSet())
348 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
351 if (!Other.isWrappedSet())
352 return Other.getUpper().ule(Upper) ||
353 Lower.ule(Other.getLower());
355 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
358 /// subtract - Subtract the specified constant from the endpoints of this
360 ConstantRange ConstantRange::subtract(const APInt &Val) const {
361 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
362 // If the set is empty or full, don't modify the endpoints.
365 return ConstantRange(Lower - Val, Upper - Val);
368 /// \brief Subtract the specified range from this range (aka relative complement
370 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
371 return intersectWith(CR.inverse());
374 /// intersectWith - Return the range that results from the intersection of this
375 /// range with another range. The resultant range is guaranteed to include all
376 /// elements contained in both input ranges, and to have the smallest possible
377 /// set size that does so. Because there may be two intersections with the
378 /// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
379 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
380 assert(getBitWidth() == CR.getBitWidth() &&
381 "ConstantRange types don't agree!");
383 // Handle common cases.
384 if ( isEmptySet() || CR.isFullSet()) return *this;
385 if (CR.isEmptySet() || isFullSet()) return CR;
387 if (!isWrappedSet() && CR.isWrappedSet())
388 return CR.intersectWith(*this);
390 if (!isWrappedSet() && !CR.isWrappedSet()) {
391 if (Lower.ult(CR.Lower)) {
392 if (Upper.ule(CR.Lower))
393 return ConstantRange(getBitWidth(), false);
395 if (Upper.ult(CR.Upper))
396 return ConstantRange(CR.Lower, Upper);
400 if (Upper.ult(CR.Upper))
403 if (Lower.ult(CR.Upper))
404 return ConstantRange(Lower, CR.Upper);
406 return ConstantRange(getBitWidth(), false);
409 if (isWrappedSet() && !CR.isWrappedSet()) {
410 if (CR.Lower.ult(Upper)) {
411 if (CR.Upper.ult(Upper))
414 if (CR.Upper.ule(Lower))
415 return ConstantRange(CR.Lower, Upper);
417 if (getSetSize().ult(CR.getSetSize()))
421 if (CR.Lower.ult(Lower)) {
422 if (CR.Upper.ule(Lower))
423 return ConstantRange(getBitWidth(), false);
425 return ConstantRange(Lower, CR.Upper);
430 if (CR.Upper.ult(Upper)) {
431 if (CR.Lower.ult(Upper)) {
432 if (getSetSize().ult(CR.getSetSize()))
437 if (CR.Lower.ult(Lower))
438 return ConstantRange(Lower, CR.Upper);
442 if (CR.Upper.ule(Lower)) {
443 if (CR.Lower.ult(Lower))
446 return ConstantRange(CR.Lower, Upper);
448 if (getSetSize().ult(CR.getSetSize()))
454 /// unionWith - Return the range that results from the union of this range with
455 /// another range. The resultant range is guaranteed to include the elements of
456 /// both sets, but may contain more. For example, [3, 9) union [12,15) is
457 /// [3, 15), which includes 9, 10, and 11, which were not included in either
460 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
461 assert(getBitWidth() == CR.getBitWidth() &&
462 "ConstantRange types don't agree!");
464 if ( isFullSet() || CR.isEmptySet()) return *this;
465 if (CR.isFullSet() || isEmptySet()) return CR;
467 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
469 if (!isWrappedSet() && !CR.isWrappedSet()) {
470 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
471 // If the two ranges are disjoint, find the smaller gap and bridge it.
472 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
474 return ConstantRange(Lower, CR.Upper);
475 return ConstantRange(CR.Lower, Upper);
478 APInt L = Lower, U = Upper;
481 if ((CR.Upper - 1).ugt(U - 1))
484 if (L == 0 && U == 0)
485 return ConstantRange(getBitWidth());
487 return ConstantRange(L, U);
490 if (!CR.isWrappedSet()) {
491 // ------U L----- and ------U L----- : this
493 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
496 // ------U L----- : this
498 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
499 return ConstantRange(getBitWidth());
501 // ----U L---- : this
504 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
505 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
507 return ConstantRange(Lower, CR.Upper);
508 return ConstantRange(CR.Lower, Upper);
511 // ----U L----- : this
513 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
514 return ConstantRange(CR.Lower, Upper);
516 // ------U L---- : this
518 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
519 "ConstantRange::unionWith missed a case with one range wrapped");
520 return ConstantRange(Lower, CR.Upper);
523 // ------U L---- and ------U L---- : this
524 // -U L----------- and ------------U L : CR
525 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
526 return ConstantRange(getBitWidth());
528 APInt L = Lower, U = Upper;
534 return ConstantRange(L, U);
537 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
538 uint32_t ResultBitWidth) const {
541 llvm_unreachable("unsupported cast type");
542 case Instruction::Trunc:
543 return truncate(ResultBitWidth);
544 case Instruction::SExt:
545 return signExtend(ResultBitWidth);
546 case Instruction::ZExt:
547 return zeroExtend(ResultBitWidth);
548 case Instruction::BitCast:
550 case Instruction::FPToUI:
551 case Instruction::FPToSI:
552 if (getBitWidth() == ResultBitWidth)
555 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
556 case Instruction::UIToFP: {
557 // TODO: use input range if available
558 auto BW = getBitWidth();
559 APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
560 APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
561 return ConstantRange(Min, Max);
563 case Instruction::SIToFP: {
564 // TODO: use input range if available
565 auto BW = getBitWidth();
566 APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
567 APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
568 return ConstantRange(SMin, SMax);
570 case Instruction::FPTrunc:
571 case Instruction::FPExt:
572 case Instruction::IntToPtr:
573 case Instruction::PtrToInt:
574 case Instruction::AddrSpaceCast:
575 // Conservatively return full set.
576 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
580 /// zeroExtend - Return a new range in the specified integer type, which must
581 /// be strictly larger than the current type. The returned range will
582 /// correspond to the possible range of values as if the source range had been
584 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
585 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
587 unsigned SrcTySize = getBitWidth();
588 assert(SrcTySize < DstTySize && "Not a value extension");
589 if (isFullSet() || isWrappedSet()) {
590 // Change into [0, 1 << src bit width)
591 APInt LowerExt(DstTySize, 0);
592 if (!Upper) // special case: [X, 0) -- not really wrapping around
593 LowerExt = Lower.zext(DstTySize);
594 return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize));
597 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
600 /// signExtend - Return a new range in the specified integer type, which must
601 /// be strictly larger than the current type. The returned range will
602 /// correspond to the possible range of values as if the source range had been
604 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
605 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
607 unsigned SrcTySize = getBitWidth();
608 assert(SrcTySize < DstTySize && "Not a value extension");
610 // special case: [X, INT_MIN) -- not really wrapping around
611 if (Upper.isMinSignedValue())
612 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
614 if (isFullSet() || isSignWrappedSet()) {
615 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
616 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
619 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
622 /// truncate - Return a new range in the specified integer type, which must be
623 /// strictly smaller than the current type. The returned range will
624 /// correspond to the possible range of values as if the source range had been
625 /// truncated to the specified type.
626 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
627 assert(getBitWidth() > DstTySize && "Not a value truncation");
629 return ConstantRange(DstTySize, /*isFullSet=*/false);
631 return ConstantRange(DstTySize, /*isFullSet=*/true);
633 APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth());
634 APInt MaxBitValue(getBitWidth(), 0);
635 MaxBitValue.setBit(DstTySize);
637 APInt LowerDiv(Lower), UpperDiv(Upper);
638 ConstantRange Union(DstTySize, /*isFullSet=*/false);
640 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
641 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
642 // then we do the union with [MaxValue, Upper)
643 if (isWrappedSet()) {
644 // If Upper is greater than Max Value, it covers the whole truncated range.
645 if (Upper.uge(MaxValue))
646 return ConstantRange(DstTySize, /*isFullSet=*/true);
648 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
649 UpperDiv = APInt::getMaxValue(getBitWidth());
651 // Union covers the MaxValue case, so return if the remaining range is just
653 if (LowerDiv == UpperDiv)
657 // Chop off the most significant bits that are past the destination bitwidth.
658 if (LowerDiv.uge(MaxValue)) {
659 APInt Div(getBitWidth(), 0);
660 APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
661 UpperDiv = UpperDiv - MaxBitValue * Div;
664 if (UpperDiv.ule(MaxValue))
665 return ConstantRange(LowerDiv.trunc(DstTySize),
666 UpperDiv.trunc(DstTySize)).unionWith(Union);
668 // The truncated value wraps around. Check if we can do better than fullset.
669 APInt UpperModulo = UpperDiv - MaxBitValue;
670 if (UpperModulo.ult(LowerDiv))
671 return ConstantRange(LowerDiv.trunc(DstTySize),
672 UpperModulo.trunc(DstTySize)).unionWith(Union);
674 return ConstantRange(DstTySize, /*isFullSet=*/true);
677 /// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
678 /// value is zero extended, truncated, or left alone to make it that width.
679 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
680 unsigned SrcTySize = getBitWidth();
681 if (SrcTySize > DstTySize)
682 return truncate(DstTySize);
683 if (SrcTySize < DstTySize)
684 return zeroExtend(DstTySize);
688 /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
689 /// value is sign extended, truncated, or left alone to make it that width.
690 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
691 unsigned SrcTySize = getBitWidth();
692 if (SrcTySize > DstTySize)
693 return truncate(DstTySize);
694 if (SrcTySize < DstTySize)
695 return signExtend(DstTySize);
699 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
700 const ConstantRange &Other) const {
701 assert(BinOp >= Instruction::BinaryOpsBegin &&
702 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
705 case Instruction::Add:
707 case Instruction::Sub:
709 case Instruction::Mul:
710 return multiply(Other);
711 case Instruction::UDiv:
713 case Instruction::Shl:
715 case Instruction::LShr:
717 case Instruction::And:
718 return binaryAnd(Other);
719 case Instruction::Or:
720 return binaryOr(Other);
721 // Note: floating point operations applied to abstract ranges are just
722 // ideal integer operations with a lossy representation
723 case Instruction::FAdd:
725 case Instruction::FSub:
727 case Instruction::FMul:
728 return multiply(Other);
730 // Conservatively return full set.
731 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
736 ConstantRange::add(const ConstantRange &Other) const {
737 if (isEmptySet() || Other.isEmptySet())
738 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
739 if (isFullSet() || Other.isFullSet())
740 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
742 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
743 APInt NewLower = getLower() + Other.getLower();
744 APInt NewUpper = getUpper() + Other.getUpper() - 1;
745 if (NewLower == NewUpper)
746 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
748 ConstantRange X = ConstantRange(NewLower, NewUpper);
749 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
750 // We've wrapped, therefore, full set.
751 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
756 ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
757 // Calculate the subset of this range such that "X + Other" is
758 // guaranteed not to wrap (overflow) for all X in this subset.
759 // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
760 // passing a single element range.
761 auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
762 ConstantRange(Other),
763 OverflowingBinaryOperator::NoSignedWrap);
764 auto NSWConstrainedRange = intersectWith(NSWRange);
766 return NSWConstrainedRange.add(ConstantRange(Other));
770 ConstantRange::sub(const ConstantRange &Other) const {
771 if (isEmptySet() || Other.isEmptySet())
772 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
773 if (isFullSet() || Other.isFullSet())
774 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
776 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
777 APInt NewLower = getLower() - Other.getUpper() + 1;
778 APInt NewUpper = getUpper() - Other.getLower();
779 if (NewLower == NewUpper)
780 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
782 ConstantRange X = ConstantRange(NewLower, NewUpper);
783 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
784 // We've wrapped, therefore, full set.
785 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
791 ConstantRange::multiply(const ConstantRange &Other) const {
792 // TODO: If either operand is a single element and the multiply is known to
793 // be non-wrapping, round the result min and max value to the appropriate
794 // multiple of that element. If wrapping is possible, at least adjust the
795 // range according to the greatest power-of-two factor of the single element.
797 if (isEmptySet() || Other.isEmptySet())
798 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
800 // Multiplication is signedness-independent. However different ranges can be
801 // obtained depending on how the input ranges are treated. These different
802 // ranges are all conservatively correct, but one might be better than the
803 // other. We calculate two ranges; one treating the inputs as unsigned
804 // and the other signed, then return the smallest of these ranges.
806 // Unsigned range first.
807 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
808 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
809 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
810 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
812 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
813 this_max * Other_max + 1);
814 ConstantRange UR = Result_zext.truncate(getBitWidth());
816 // If the unsigned range doesn't wrap, and isn't negative then it's a range
817 // from one positive number to another which is as good as we can generate.
818 // In this case, skip the extra work of generating signed ranges which aren't
819 // going to be better than this range.
820 if (!UR.isWrappedSet() && UR.getLower().isNonNegative())
823 // Now the signed range. Because we could be dealing with negative numbers
824 // here, the lower bound is the smallest of the cartesian product of the
825 // lower and upper ranges; for example:
826 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
827 // Similarly for the upper bound, swapping min for max.
829 this_min = getSignedMin().sext(getBitWidth() * 2);
830 this_max = getSignedMax().sext(getBitWidth() * 2);
831 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
832 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
834 auto L = {this_min * Other_min, this_min * Other_max,
835 this_max * Other_min, this_max * Other_max};
836 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
837 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
838 ConstantRange SR = Result_sext.truncate(getBitWidth());
840 return UR.getSetSize().ult(SR.getSetSize()) ? UR : SR;
844 ConstantRange::smax(const ConstantRange &Other) const {
845 // X smax Y is: range(smax(X_smin, Y_smin),
846 // smax(X_smax, Y_smax))
847 if (isEmptySet() || Other.isEmptySet())
848 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
849 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
850 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
852 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
853 return ConstantRange(NewL, NewU);
857 ConstantRange::umax(const ConstantRange &Other) const {
858 // X umax Y is: range(umax(X_umin, Y_umin),
859 // umax(X_umax, Y_umax))
860 if (isEmptySet() || Other.isEmptySet())
861 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
862 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
863 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
865 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
866 return ConstantRange(NewL, NewU);
870 ConstantRange::smin(const ConstantRange &Other) const {
871 // X smin Y is: range(smin(X_smin, Y_smin),
872 // smin(X_smax, Y_smax))
873 if (isEmptySet() || Other.isEmptySet())
874 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
875 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
876 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
878 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
879 return ConstantRange(NewL, NewU);
883 ConstantRange::umin(const ConstantRange &Other) const {
884 // X umin Y is: range(umin(X_umin, Y_umin),
885 // umin(X_umax, Y_umax))
886 if (isEmptySet() || Other.isEmptySet())
887 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
888 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
889 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
891 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
892 return ConstantRange(NewL, NewU);
896 ConstantRange::udiv(const ConstantRange &RHS) const {
897 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
898 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
900 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
902 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
904 APInt RHS_umin = RHS.getUnsignedMin();
906 // We want the lowest value in RHS excluding zero. Usually that would be 1
907 // except for a range in the form of [X, 1) in which case it would be X.
908 if (RHS.getUpper() == 1)
909 RHS_umin = RHS.getLower();
911 RHS_umin = APInt(getBitWidth(), 1);
914 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
916 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
919 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
921 return ConstantRange(Lower, Upper);
925 ConstantRange::binaryAnd(const ConstantRange &Other) const {
926 if (isEmptySet() || Other.isEmptySet())
927 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
929 // TODO: replace this with something less conservative
931 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
932 if (umin.isAllOnesValue())
933 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
934 return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
938 ConstantRange::binaryOr(const ConstantRange &Other) const {
939 if (isEmptySet() || Other.isEmptySet())
940 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
942 // TODO: replace this with something less conservative
944 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
945 if (umax.isMinValue())
946 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
947 return ConstantRange(umax, APInt::getNullValue(getBitWidth()));
951 ConstantRange::shl(const ConstantRange &Other) const {
952 if (isEmptySet() || Other.isEmptySet())
953 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
955 APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
956 APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
958 // there's no overflow!
959 APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
960 if (Zeros.ugt(Other.getUnsignedMax()))
961 return ConstantRange(min, max + 1);
963 // FIXME: implement the other tricky cases
964 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
968 ConstantRange::lshr(const ConstantRange &Other) const {
969 if (isEmptySet() || Other.isEmptySet())
970 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
972 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
973 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
975 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
977 return ConstantRange(min, max + 1);
980 ConstantRange ConstantRange::inverse() const {
982 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
984 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
985 return ConstantRange(Upper, Lower);
988 /// print - Print out the bounds to a stream...
990 void ConstantRange::print(raw_ostream &OS) const {
993 else if (isEmptySet())
996 OS << "[" << Lower << "," << Upper << ")";
999 /// dump - Allow printing from a debugger easily...
1001 LLVM_DUMP_METHOD void ConstantRange::dump() const {
1005 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
1006 const unsigned NumRanges = Ranges.getNumOperands() / 2;
1007 assert(NumRanges >= 1 && "Must have at least one range!");
1008 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1010 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1011 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1013 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1015 for (unsigned i = 1; i < NumRanges; ++i) {
1016 auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1017 auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1019 // Note: unionWith will potentially create a range that contains values not
1020 // contained in any of the original N ranges.
1021 CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));