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/Support/ConstantRange.h"
25 #include "llvm/Support/raw_ostream.h"
28 /// Initialize a range to hold the single specified value.
30 ConstantRangeBase::ConstantRangeBase(const APInt & V)
31 : Lower(V), Upper(V + 1) {}
33 ConstantRangeBase::ConstantRangeBase(const APInt &L, const APInt &U)
34 : Lower(L), Upper(U) {
35 assert(L.getBitWidth() == U.getBitWidth() &&
36 "ConstantRange with unequal bit widths");
39 /// print - Print out the bounds to a stream...
41 void ConstantRangeBase::print(raw_ostream &OS) const {
42 OS << "[" << Lower << "," << Upper << ")";
45 /// dump - Allow printing from a debugger easily...
47 void ConstantRangeBase::dump() const {
51 std::ostream &llvm::operator<<(std::ostream &o,
52 const ConstantRangeBase &CR) {
58 /// Initialize a full (the default) or empty set for the specified type.
60 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) :
61 ConstantRangeBase(APInt(BitWidth, 0), APInt(BitWidth, 0)) {
63 Lower = Upper = APInt::getMaxValue(BitWidth);
65 Lower = Upper = APInt::getMinValue(BitWidth);
68 /// Initialize a range to hold the single specified value.
70 ConstantRange::ConstantRange(const APInt & V) : ConstantRangeBase(V) {}
72 ConstantRange::ConstantRange(const APInt &L, const APInt &U)
73 : ConstantRangeBase(L, U) {
74 assert((L != U || (L.isMaxValue() || L.isMinValue())) &&
75 "Lower == Upper, but they aren't min or max value!");
78 /// isFullSet - Return true if this set contains all of the elements possible
79 /// for this data-type
80 bool ConstantRange::isFullSet() const {
81 return Lower == Upper && Lower.isMaxValue();
84 /// isEmptySet - Return true if this set contains no members.
86 bool ConstantRange::isEmptySet() const {
87 return Lower == Upper && Lower.isMinValue();
90 /// isWrappedSet - Return true if this set wraps around the top of the range,
91 /// for example: [100, 8)
93 bool ConstantRange::isWrappedSet() const {
94 return Lower.ugt(Upper);
97 /// getSetSize - Return the number of elements in this set.
99 APInt ConstantRange::getSetSize() const {
101 return APInt(getBitWidth(), 0);
102 if (getBitWidth() == 1) {
103 if (Lower != Upper) // One of T or F in the set...
105 return APInt(2, 2); // Must be full set...
108 // Simply subtract the bounds...
109 return Upper - Lower;
112 /// getUnsignedMax - Return the largest unsigned value contained in the
115 APInt ConstantRange::getUnsignedMax() const {
116 if (isFullSet() || isWrappedSet())
117 return APInt::getMaxValue(getBitWidth());
119 return getUpper() - 1;
122 /// getUnsignedMin - Return the smallest unsigned value contained in the
125 APInt ConstantRange::getUnsignedMin() const {
126 if (isFullSet() || (isWrappedSet() && getUpper() != 0))
127 return APInt::getMinValue(getBitWidth());
132 /// getSignedMax - Return the largest signed value contained in the
135 APInt ConstantRange::getSignedMax() const {
136 APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
137 if (!isWrappedSet()) {
138 if (getLower().sle(getUpper() - 1))
139 return getUpper() - 1;
143 if ((getUpper() - 1).slt(getLower())) {
144 if (getLower() != SignedMax)
147 return getUpper() - 1;
149 return getUpper() - 1;
154 /// getSignedMin - Return the smallest signed value contained in the
157 APInt ConstantRange::getSignedMin() const {
158 APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
159 if (!isWrappedSet()) {
160 if (getLower().sle(getUpper() - 1))
165 if ((getUpper() - 1).slt(getLower())) {
166 if (getUpper() != SignedMin)
176 /// contains - Return true if the specified value is in the set.
178 bool ConstantRange::contains(const APInt &V) const {
183 return Lower.ule(V) && V.ult(Upper);
185 return Lower.ule(V) || V.ult(Upper);
188 /// subtract - Subtract the specified constant from the endpoints of this
190 ConstantRange ConstantRange::subtract(const APInt &Val) const {
191 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
192 // If the set is empty or full, don't modify the endpoints.
195 return ConstantRange(Lower - Val, Upper - Val);
199 // intersect1Wrapped - This helper function is used to intersect two ranges when
200 // it is known that LHS is wrapped and RHS isn't.
203 ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
204 const ConstantRange &RHS) {
205 assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
207 // Check to see if we overlap on the Left side of RHS...
209 if (RHS.Lower.ult(LHS.Upper)) {
210 // We do overlap on the left side of RHS, see if we overlap on the right of
212 if (RHS.Upper.ugt(LHS.Lower)) {
213 // Ok, the result overlaps on both the left and right sides. See if the
214 // resultant interval will be smaller if we wrap or not...
216 if (LHS.getSetSize().ult(RHS.getSetSize()))
222 // No overlap on the right, just on the left.
223 return ConstantRange(RHS.Lower, LHS.Upper);
226 // We don't overlap on the left side of RHS, see if we overlap on the right
228 if (RHS.Upper.ugt(LHS.Lower)) {
230 return ConstantRange(LHS.Lower, RHS.Upper);
233 return ConstantRange(LHS.getBitWidth(), false);
238 /// intersectWith - Return the range that results from the intersection of this
239 /// range with another range.
241 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
242 assert(getBitWidth() == CR.getBitWidth() &&
243 "ConstantRange types don't agree!");
244 // Handle common special cases
245 if (isEmptySet() || CR.isFullSet())
247 if (isFullSet() || CR.isEmptySet())
250 if (!isWrappedSet()) {
251 if (!CR.isWrappedSet()) {
252 APInt L = APIntOps::umax(Lower, CR.Lower);
253 APInt U = APIntOps::umin(Upper, CR.Upper);
255 if (L.ult(U)) // If range isn't empty...
256 return ConstantRange(L, U);
258 return ConstantRange(getBitWidth(), false);// Otherwise, empty set
260 return intersect1Wrapped(CR, *this);
261 } else { // We know "this" is wrapped...
262 if (!CR.isWrappedSet())
263 return intersect1Wrapped(*this, CR);
265 // Both ranges are wrapped...
266 APInt L = APIntOps::umax(Lower, CR.Lower);
267 APInt U = APIntOps::umin(Upper, CR.Upper);
268 return ConstantRange(L, U);
274 /// maximalIntersectWith - Return the range that results from the intersection
275 /// of this range with another range. The resultant range is guaranteed to
276 /// include all elements contained in both input ranges, and to have the
277 /// smallest possible set size that does so. Because there may be two
278 /// intersections with the same set size, A.maximalIntersectWith(B) might not
279 /// be equal to B.maximalIntersect(A).
281 ConstantRange::maximalIntersectWith(const ConstantRange &CR) const {
282 assert(getBitWidth() == CR.getBitWidth() &&
283 "ConstantRange types don't agree!");
285 // Handle common cases.
286 if ( isEmptySet() || CR.isFullSet()) return *this;
287 if (CR.isEmptySet() || isFullSet()) return CR;
289 if (!isWrappedSet() && CR.isWrappedSet())
290 return CR.maximalIntersectWith(*this);
292 if (!isWrappedSet() && !CR.isWrappedSet()) {
293 if (Lower.ult(CR.Lower)) {
294 if (Upper.ule(CR.Lower))
295 return ConstantRange(getBitWidth(), false);
297 if (Upper.ult(CR.Upper))
298 return ConstantRange(CR.Lower, Upper);
302 if (Upper.ult(CR.Upper))
305 if (Lower.ult(CR.Upper))
306 return ConstantRange(Lower, CR.Upper);
308 return ConstantRange(getBitWidth(), false);
312 if (isWrappedSet() && !CR.isWrappedSet()) {
313 if (CR.Lower.ult(Upper)) {
314 if (CR.Upper.ult(Upper))
317 if (CR.Upper.ult(Lower))
318 return ConstantRange(CR.Lower, Upper);
320 if (getSetSize().ult(CR.getSetSize()))
324 } else if (CR.Lower.ult(Lower)) {
325 if (CR.Upper.ule(Lower))
326 return ConstantRange(getBitWidth(), false);
328 return ConstantRange(Lower, CR.Upper);
333 if (CR.Upper.ult(Upper)) {
334 if (CR.Lower.ult(Upper)) {
335 if (getSetSize().ult(CR.getSetSize()))
341 if (CR.Lower.ult(Lower))
342 return ConstantRange(Lower, CR.Upper);
345 } else if (CR.Upper.ult(Lower)) {
346 if (CR.Lower.ult(Lower))
349 return ConstantRange(CR.Lower, Upper);
351 if (getSetSize().ult(CR.getSetSize()))
358 /// unionWith - Return the range that results from the union of this range with
359 /// another range. The resultant range is guaranteed to include the elements of
360 /// both sets, but may contain more. For example, [3, 9) union [12,15) is
361 /// [3, 15), which includes 9, 10, and 11, which were not included in either
364 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
365 assert(getBitWidth() == CR.getBitWidth() &&
366 "ConstantRange types don't agree!");
368 if ( isFullSet() || CR.isEmptySet()) return *this;
369 if (CR.isFullSet() || isEmptySet()) return CR;
371 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
373 APInt L = Lower, U = Upper;
375 if (!isWrappedSet() && !CR.isWrappedSet()) {
383 if (isWrappedSet() && !CR.isWrappedSet()) {
384 if ((CR.Lower.ult(Upper) && CR.Upper.ult(Upper)) ||
385 (CR.Lower.ugt(Lower) && CR.Upper.ugt(Lower))) {
389 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper)) {
390 return ConstantRange(getBitWidth());
393 if (CR.Lower.ule(Upper) && CR.Upper.ule(Lower)) {
394 APInt d1 = CR.Upper - Upper, d2 = Lower - CR.Upper;
402 if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower)) {
403 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
411 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper)) {
412 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Lower;
422 if (isWrappedSet() && CR.isWrappedSet()) {
423 if (Lower.ult(CR.Upper) || CR.Lower.ult(Upper))
424 return ConstantRange(getBitWidth());
426 if (CR.Upper.ugt(U)) {
430 if (CR.Lower.ult(L)) {
434 if (L == U) return ConstantRange(getBitWidth());
437 return ConstantRange(L, U);
440 /// zeroExtend - Return a new range in the specified integer type, which must
441 /// be strictly larger than the current type. The returned range will
442 /// correspond to the possible range of values as if the source range had been
444 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
445 unsigned SrcTySize = getBitWidth();
446 assert(SrcTySize < DstTySize && "Not a value extension");
448 // Change a source full set into [0, 1 << 8*numbytes)
449 return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize));
451 APInt L = Lower; L.zext(DstTySize);
452 APInt U = Upper; U.zext(DstTySize);
453 return ConstantRange(L, U);
456 /// signExtend - Return a new range in the specified integer type, which must
457 /// be strictly larger than the current type. The returned range will
458 /// correspond to the possible range of values as if the source range had been
460 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
461 unsigned SrcTySize = getBitWidth();
462 assert(SrcTySize < DstTySize && "Not a value extension");
464 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
465 APInt::getLowBitsSet(DstTySize, SrcTySize-1));
468 APInt L = Lower; L.sext(DstTySize);
469 APInt U = Upper; U.sext(DstTySize);
470 return ConstantRange(L, U);
473 /// truncate - Return a new range in the specified integer type, which must be
474 /// strictly smaller than the current type. The returned range will
475 /// correspond to the possible range of values as if the source range had been
476 /// truncated to the specified type.
477 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
478 unsigned SrcTySize = getBitWidth();
479 assert(SrcTySize > DstTySize && "Not a value truncation");
480 APInt Size(APInt::getLowBitsSet(SrcTySize, DstTySize));
481 if (isFullSet() || getSetSize().ugt(Size))
482 return ConstantRange(DstTySize);
484 APInt L = Lower; L.trunc(DstTySize);
485 APInt U = Upper; U.trunc(DstTySize);
486 return ConstantRange(L, U);
490 ConstantRange::add(const ConstantRange &Other) const {
491 if (isEmptySet() || Other.isEmptySet())
492 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
494 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
495 APInt NewLower = getLower() + Other.getLower();
496 APInt NewUpper = getUpper() + Other.getUpper() - 1;
497 if (NewLower == NewUpper)
498 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
500 ConstantRange X = ConstantRange(NewLower, NewUpper);
501 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
502 // We've wrapped, therefore, full set.
503 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
509 ConstantRange::multiply(const ConstantRange &Other) const {
510 // TODO: Implement multiply.
511 return ConstantRange(getBitWidth(),
512 !(isEmptySet() || Other.isEmptySet()));
516 ConstantRange::smax(const ConstantRange &Other) const {
517 // TODO: Implement smax.
518 return ConstantRange(getBitWidth(),
519 !(isEmptySet() || Other.isEmptySet()));
523 ConstantRange::umax(const ConstantRange &Other) const {
524 // X umax Y is: range(umax(X_umin, Y_umin),
525 // umax(X_umax, Y_umax))
526 if (isEmptySet() || Other.isEmptySet())
527 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
528 if (isFullSet() || Other.isFullSet())
529 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
530 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
531 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
533 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
534 return ConstantRange(NewL, NewU);
538 ConstantRange::udiv(const ConstantRange &Other) const {
539 // TODO: Implement udiv.
540 return ConstantRange(getBitWidth(),
541 !(isEmptySet() || Other.isEmptySet()));
544 /// Initialize a full (the default) or empty set for the specified type.
546 ConstantSignedRange::ConstantSignedRange(uint32_t BitWidth, bool Full) :
547 ConstantRangeBase(APInt(BitWidth, 0), APInt(BitWidth, 0)) {
549 Lower = Upper = APInt::getSignedMaxValue(BitWidth);
551 Lower = Upper = APInt::getSignedMinValue(BitWidth);
554 /// Initialize a range to hold the single specified value.
556 ConstantSignedRange::ConstantSignedRange(const APInt & V)
557 : ConstantRangeBase(V) {}
559 ConstantSignedRange::ConstantSignedRange(const APInt &L, const APInt &U)
560 : ConstantRangeBase(L, U) {
561 assert((L != U || (L.isMaxSignedValue() || L.isMinSignedValue())) &&
562 "Lower == Upper, but they aren't min or max value!");
565 /// isFullSet - Return true if this set contains all of the elements possible
566 /// for this data-type
567 bool ConstantSignedRange::isFullSet() const {
568 return Lower == Upper && Lower.isMaxSignedValue();
571 /// isEmptySet - Return true if this set contains no members.
573 bool ConstantSignedRange::isEmptySet() const {
574 return Lower == Upper && Lower.isMinSignedValue();
577 /// isWrappedSet - Return true if this set wraps around the top of the range,
578 /// for example: [100, 8)
580 bool ConstantSignedRange::isWrappedSet() const {
581 return Lower.sgt(Upper);
584 /// getSetSize - Return the number of elements in this set.
586 APInt ConstantSignedRange::getSetSize() const {
588 return APInt(getBitWidth(), 0);
589 if (getBitWidth() == 1) {
590 if (Lower != Upper) // One of T or F in the set...
592 return APInt(2, 2); // Must be full set...
595 // Simply subtract the bounds...
596 return Upper - Lower;
599 /// getSignedMax - Return the largest signed value contained in the
600 /// ConstantSignedRange.
602 APInt ConstantSignedRange::getSignedMax() const {
603 if (isFullSet() || isWrappedSet())
604 return APInt::getSignedMaxValue(getBitWidth());
606 return getUpper() - 1;
609 /// getSignedMin - Return the smallest signed value contained in the
610 /// ConstantSignedRange.
612 APInt ConstantSignedRange::getSignedMin() const {
613 if (isFullSet() || (isWrappedSet() &&
614 getUpper() != APInt::getSignedMinValue(getBitWidth())))
615 return APInt::getSignedMinValue(getBitWidth());
620 /// getUnsignedMax - Return the largest unsigned value contained in the
621 /// ConstantSignedRange.
623 APInt ConstantSignedRange::getUnsignedMax() const {
624 APInt UnsignedMax(APInt::getMaxValue(getBitWidth()));
625 if (!isWrappedSet()) {
626 if (getLower().ule(getUpper() - 1))
627 return getUpper() - 1;
631 if ((getUpper() - 1).ult(getLower())) {
632 if (getLower() != UnsignedMax)
635 return getUpper() - 1;
637 return getUpper() - 1;
642 /// getUnsignedMin - Return the smallest unsigned value contained in the
643 /// ConstantSignedRange.
645 APInt ConstantSignedRange::getUnsignedMin() const {
646 APInt UnsignedMin(APInt::getMinValue(getBitWidth()));
647 if (!isWrappedSet()) {
648 if (getLower().ule(getUpper() - 1))
653 if ((getUpper() - 1).ult(getLower())) {
654 if (getUpper() != UnsignedMin)
664 /// contains - Return true if the specified value is in the set.
666 bool ConstantSignedRange::contains(const APInt &V) const {
671 return Lower.sle(V) && V.slt(Upper);
673 return Lower.sle(V) || V.slt(Upper);
676 /// subtract - Subtract the specified constant from the endpoints of this
678 ConstantSignedRange ConstantSignedRange::subtract(const APInt &Val) const {
679 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
680 // If the set is empty or full, don't modify the endpoints.
683 return ConstantSignedRange(Lower - Val, Upper - Val);
687 // intersect1Wrapped - This helper function is used to intersect two ranges when
688 // it is known that LHS is wrapped and RHS isn't.
691 ConstantSignedRange::intersect1Wrapped(const ConstantSignedRange &LHS,
692 const ConstantSignedRange &RHS) {
693 assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
695 // Check to see if we overlap on the Left side of RHS...
697 if (RHS.Lower.slt(LHS.Upper)) {
698 // We do overlap on the left side of RHS, see if we overlap on the right of
700 if (RHS.Upper.sgt(LHS.Lower)) {
701 // Ok, the result overlaps on both the left and right sides. See if the
702 // resultant interval will be smaller if we wrap or not...
704 if (LHS.getSetSize().ult(RHS.getSetSize()))
710 // No overlap on the right, just on the left.
711 return ConstantSignedRange(RHS.Lower, LHS.Upper);
714 // We don't overlap on the left side of RHS, see if we overlap on the right
716 if (RHS.Upper.sgt(LHS.Lower)) {
718 return ConstantSignedRange(LHS.Lower, RHS.Upper);
721 return ConstantSignedRange(LHS.getBitWidth(), false);
726 /// intersectWith - Return the range that results from the intersection of this
727 /// range with another range.
730 ConstantSignedRange::intersectWith(const ConstantSignedRange &CR) const {
731 assert(getBitWidth() == CR.getBitWidth() &&
732 "ConstantSignedRange types don't agree!");
733 // Handle common special cases
734 if (isEmptySet() || CR.isFullSet())
736 if (isFullSet() || CR.isEmptySet())
739 if (!isWrappedSet()) {
740 if (!CR.isWrappedSet()) {
741 APInt L = APIntOps::smax(Lower, CR.Lower);
742 APInt U = APIntOps::smin(Upper, CR.Upper);
744 if (L.slt(U)) // If range isn't empty...
745 return ConstantSignedRange(L, U);
747 return ConstantSignedRange(getBitWidth(), false);// Otherwise, empty set
749 return intersect1Wrapped(CR, *this);
750 } else { // We know "this" is wrapped...
751 if (!CR.isWrappedSet())
752 return intersect1Wrapped(*this, CR);
754 // Both ranges are wrapped...
755 APInt L = APIntOps::smax(Lower, CR.Lower);
756 APInt U = APIntOps::smin(Upper, CR.Upper);
757 return ConstantSignedRange(L, U);
763 /// maximalIntersectWith - Return the range that results from the intersection
764 /// of this range with another range. The resultant range is guaranteed to
765 /// include all elements contained in both input ranges, and to have the
766 /// smallest possible set size that does so. Because there may be two
767 /// intersections with the same set size, A.maximalIntersectWith(B) might not
768 /// be equal to B.maximalIntersect(A).
770 ConstantSignedRange::maximalIntersectWith(const ConstantSignedRange &CR) const {
771 assert(getBitWidth() == CR.getBitWidth() &&
772 "ConstantSignedRange types don't agree!");
774 // Handle common cases.
775 if ( isEmptySet() || CR.isFullSet()) return *this;
776 if (CR.isEmptySet() || isFullSet()) return CR;
778 if (!isWrappedSet() && CR.isWrappedSet())
779 return CR.maximalIntersectWith(*this);
781 if (!isWrappedSet() && !CR.isWrappedSet()) {
782 if (Lower.slt(CR.Lower)) {
783 if (Upper.sle(CR.Lower))
784 return ConstantSignedRange(getBitWidth(), false);
786 if (Upper.slt(CR.Upper))
787 return ConstantSignedRange(CR.Lower, Upper);
791 if (Upper.slt(CR.Upper))
794 if (Lower.slt(CR.Upper))
795 return ConstantSignedRange(Lower, CR.Upper);
797 return ConstantSignedRange(getBitWidth(), false);
801 if (isWrappedSet() && !CR.isWrappedSet()) {
802 if (CR.Lower.slt(Upper)) {
803 if (CR.Upper.slt(Upper))
806 if (CR.Upper.slt(Lower))
807 return ConstantSignedRange(CR.Lower, Upper);
809 if (getSetSize().ult(CR.getSetSize()))
813 } else if (CR.Lower.slt(Lower)) {
814 if (CR.Upper.sle(Lower))
815 return ConstantSignedRange(getBitWidth(), false);
817 return ConstantSignedRange(Lower, CR.Upper);
822 if (CR.Upper.slt(Upper)) {
823 if (CR.Lower.slt(Upper)) {
824 if (getSetSize().ult(CR.getSetSize()))
830 if (CR.Lower.slt(Lower))
831 return ConstantSignedRange(Lower, CR.Upper);
834 } else if (CR.Upper.slt(Lower)) {
835 if (CR.Lower.slt(Lower))
838 return ConstantSignedRange(CR.Lower, Upper);
840 if (getSetSize().ult(CR.getSetSize()))
847 /// unionWith - Return the range that results from the union of this range with
848 /// another range. The resultant range is guaranteed to include the elements of
849 /// both sets, but may contain more. For example, [3, 9) union [12,15) is
850 /// [3, 15), which includes 9, 10, and 11, which were not included in either
854 ConstantSignedRange::unionWith(const ConstantSignedRange &CR) const {
855 assert(getBitWidth() == CR.getBitWidth() &&
856 "ConstantSignedRange types don't agree!");
858 if ( isFullSet() || CR.isEmptySet()) return *this;
859 if (CR.isFullSet() || isEmptySet()) return CR;
861 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
863 APInt L = Lower, U = Upper;
865 if (!isWrappedSet() && !CR.isWrappedSet()) {
873 if (isWrappedSet() && !CR.isWrappedSet()) {
874 if ((CR.Lower.slt(Upper) && CR.Upper.slt(Upper)) ||
875 (CR.Lower.sgt(Lower) && CR.Upper.sgt(Lower))) {
879 if (CR.Lower.sle(Upper) && Lower.sle(CR.Upper)) {
880 return ConstantSignedRange(getBitWidth());
883 if (CR.Lower.sle(Upper) && CR.Upper.sle(Lower)) {
884 APInt d1 = CR.Upper - Upper, d2 = Lower - CR.Upper;
892 if (Upper.slt(CR.Lower) && CR.Upper.slt(Lower)) {
893 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
901 if (Upper.slt(CR.Lower) && Lower.slt(CR.Upper)) {
902 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Lower;
912 if (isWrappedSet() && CR.isWrappedSet()) {
913 if (Lower.slt(CR.Upper) || CR.Lower.slt(Upper))
914 return ConstantSignedRange(getBitWidth());
916 if (CR.Upper.sgt(U)) {
920 if (CR.Lower.slt(L)) {
924 if (L == U) return ConstantSignedRange(getBitWidth());
927 return ConstantSignedRange(L, U);
930 /// zeroExtend - Return a new range in the specified integer type, which must
931 /// be strictly larger than the current type. The returned range will
932 /// correspond to the possible range of values as if the source range had been
934 ConstantSignedRange ConstantSignedRange::zeroExtend(uint32_t DstTySize) const {
935 unsigned SrcTySize = getBitWidth();
936 assert(SrcTySize < DstTySize && "Not a value extension");
938 return ConstantSignedRange(SrcTySize, /*isFullSet=*/false);
940 // Change a source full set into [0, 1 << 8*numbytes)
941 return ConstantSignedRange(APInt(DstTySize,0),
942 APInt(DstTySize,1).shl(SrcTySize));
945 if (Lower.isNegative() && !Upper.isNegative()) {
946 L = APInt(SrcTySize, 0);
947 U = APInt::getSignedMinValue(SrcTySize);
954 return ConstantSignedRange(L, U);
957 /// signExtend - Return a new range in the specified integer type, which must
958 /// be strictly larger than the current type. The returned range will
959 /// correspond to the possible range of values as if the source range had been
961 ConstantSignedRange ConstantSignedRange::signExtend(uint32_t DstTySize) const {
962 unsigned SrcTySize = getBitWidth();
963 assert(SrcTySize < DstTySize && "Not a value extension");
965 return ConstantSignedRange(SrcTySize, /*isFullSet=*/false);
967 return ConstantSignedRange(APInt(getSignedMin()).sext(DstTySize),
968 APInt(getSignedMax()).sext(DstTySize)+1);
970 APInt L = Lower; L.sext(DstTySize);
971 APInt U = Upper; U.sext(DstTySize);
972 return ConstantSignedRange(L, U);
975 /// truncate - Return a new range in the specified integer type, which must be
976 /// strictly smaller than the current type. The returned range will
977 /// correspond to the possible range of values as if the source range had been
978 /// truncated to the specified type.
979 ConstantSignedRange ConstantSignedRange::truncate(uint32_t DstTySize) const {
980 // TODO: Implement truncate.
981 return ConstantSignedRange(DstTySize, !isEmptySet());
985 ConstantSignedRange::add(const ConstantSignedRange &Other) const {
986 // TODO: Implement add.
987 return ConstantSignedRange(getBitWidth(),
988 !(isEmptySet() || Other.isEmptySet()));
992 ConstantSignedRange::multiply(const ConstantSignedRange &Other) const {
993 // TODO: Implement multiply.
994 return ConstantSignedRange(getBitWidth(),
995 !(isEmptySet() || Other.isEmptySet()));
999 ConstantSignedRange::smax(const ConstantSignedRange &Other) const {
1000 // X smax Y is: range(smax(X_smin, Y_smin),
1001 // smax(X_smax, Y_smax))
1002 if (isEmptySet() || Other.isEmptySet())
1003 return ConstantSignedRange(getBitWidth(), /*isFullSet=*/false);
1004 if (isFullSet() || Other.isFullSet())
1005 return ConstantSignedRange(getBitWidth(), /*isFullSet=*/true);
1006 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
1007 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
1009 return ConstantSignedRange(getBitWidth(), /*isFullSet=*/true);
1010 return ConstantSignedRange(NewL, NewU);
1014 ConstantSignedRange::umax(const ConstantSignedRange &Other) const {
1015 // TODO: Implement umax.
1016 return ConstantSignedRange(getBitWidth(),
1017 !(isEmptySet() || Other.isEmptySet()));
1021 ConstantSignedRange::udiv(const ConstantSignedRange &Other) const {
1022 // TODO: Implement udiv.
1023 return ConstantSignedRange(getBitWidth(),
1024 !(isEmptySet() || Other.isEmptySet()));