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/InstrTypes.h"
25 #include "llvm/Support/ConstantRange.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
30 /// Initialize a full (the default) or empty set for the specified type.
32 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) {
34 Lower = Upper = APInt::getMaxValue(BitWidth);
36 Lower = Upper = APInt::getMinValue(BitWidth);
39 /// Initialize a range to hold the single specified value.
41 ConstantRange::ConstantRange(APIntMoveTy V)
42 : Lower(llvm_move(V)), Upper(Lower + 1) {}
44 ConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U)
45 : Lower(llvm_move(L)), Upper(llvm_move(U)) {
46 assert(Lower.getBitWidth() == Upper.getBitWidth() &&
47 "ConstantRange with unequal bit widths");
48 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
49 "Lower == Upper, but they aren't min or max value!");
52 ConstantRange ConstantRange::makeICmpRegion(unsigned Pred,
53 const ConstantRange &CR) {
57 uint32_t W = CR.getBitWidth();
59 default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()");
60 case CmpInst::ICMP_EQ:
62 case CmpInst::ICMP_NE:
63 if (CR.isSingleElement())
64 return ConstantRange(CR.getUpper(), CR.getLower());
65 return ConstantRange(W);
66 case CmpInst::ICMP_ULT: {
67 APInt UMax(CR.getUnsignedMax());
68 if (UMax.isMinValue())
69 return ConstantRange(W, /* empty */ false);
70 return ConstantRange(APInt::getMinValue(W), UMax);
72 case CmpInst::ICMP_SLT: {
73 APInt SMax(CR.getSignedMax());
74 if (SMax.isMinSignedValue())
75 return ConstantRange(W, /* empty */ false);
76 return ConstantRange(APInt::getSignedMinValue(W), SMax);
78 case CmpInst::ICMP_ULE: {
79 APInt UMax(CR.getUnsignedMax());
80 if (UMax.isMaxValue())
81 return ConstantRange(W);
82 return ConstantRange(APInt::getMinValue(W), UMax + 1);
84 case CmpInst::ICMP_SLE: {
85 APInt SMax(CR.getSignedMax());
86 if (SMax.isMaxSignedValue())
87 return ConstantRange(W);
88 return ConstantRange(APInt::getSignedMinValue(W), SMax + 1);
90 case CmpInst::ICMP_UGT: {
91 APInt UMin(CR.getUnsignedMin());
92 if (UMin.isMaxValue())
93 return ConstantRange(W, /* empty */ false);
94 return ConstantRange(UMin + 1, APInt::getNullValue(W));
96 case CmpInst::ICMP_SGT: {
97 APInt SMin(CR.getSignedMin());
98 if (SMin.isMaxSignedValue())
99 return ConstantRange(W, /* empty */ false);
100 return ConstantRange(SMin + 1, APInt::getSignedMinValue(W));
102 case CmpInst::ICMP_UGE: {
103 APInt UMin(CR.getUnsignedMin());
104 if (UMin.isMinValue())
105 return ConstantRange(W);
106 return ConstantRange(UMin, APInt::getNullValue(W));
108 case CmpInst::ICMP_SGE: {
109 APInt SMin(CR.getSignedMin());
110 if (SMin.isMinSignedValue())
111 return ConstantRange(W);
112 return ConstantRange(SMin, APInt::getSignedMinValue(W));
117 /// isFullSet - Return true if this set contains all of the elements possible
118 /// for this data-type
119 bool ConstantRange::isFullSet() const {
120 return Lower == Upper && Lower.isMaxValue();
123 /// isEmptySet - Return true if this set contains no members.
125 bool ConstantRange::isEmptySet() const {
126 return Lower == Upper && Lower.isMinValue();
129 /// isWrappedSet - Return true if this set wraps around the top of the range,
130 /// for example: [100, 8)
132 bool ConstantRange::isWrappedSet() const {
133 return Lower.ugt(Upper);
136 /// isSignWrappedSet - Return true if this set wraps around the INT_MIN of
137 /// its bitwidth, for example: i8 [120, 140).
139 bool ConstantRange::isSignWrappedSet() const {
140 return contains(APInt::getSignedMaxValue(getBitWidth())) &&
141 contains(APInt::getSignedMinValue(getBitWidth()));
144 /// getSetSize - Return the number of elements in this set.
146 APInt ConstantRange::getSetSize() const {
148 APInt Size(getBitWidth()+1, 0);
149 Size.setBit(getBitWidth());
153 // This is also correct for wrapped sets.
154 return (Upper - Lower).zext(getBitWidth()+1);
157 /// getUnsignedMax - Return the largest unsigned value contained in the
160 APInt ConstantRange::getUnsignedMax() const {
161 if (isFullSet() || isWrappedSet())
162 return APInt::getMaxValue(getBitWidth());
163 return getUpper() - 1;
166 /// getUnsignedMin - Return the smallest unsigned value contained in the
169 APInt ConstantRange::getUnsignedMin() const {
170 if (isFullSet() || (isWrappedSet() && getUpper() != 0))
171 return APInt::getMinValue(getBitWidth());
175 /// getSignedMax - Return the largest signed value contained in the
178 APInt ConstantRange::getSignedMax() const {
179 APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
180 if (!isWrappedSet()) {
181 if (getLower().sle(getUpper() - 1))
182 return getUpper() - 1;
185 if (getLower().isNegative() == getUpper().isNegative())
187 return getUpper() - 1;
190 /// getSignedMin - Return the smallest signed value contained in the
193 APInt ConstantRange::getSignedMin() const {
194 APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
195 if (!isWrappedSet()) {
196 if (getLower().sle(getUpper() - 1))
200 if ((getUpper() - 1).slt(getLower())) {
201 if (getUpper() != SignedMin)
207 /// contains - Return true if the specified value is in the set.
209 bool ConstantRange::contains(const APInt &V) const {
214 return Lower.ule(V) && V.ult(Upper);
215 return Lower.ule(V) || V.ult(Upper);
218 /// contains - Return true if the argument is a subset of this range.
219 /// Two equal sets contain each other. The empty set contained by all other
222 bool ConstantRange::contains(const ConstantRange &Other) const {
223 if (isFullSet() || Other.isEmptySet()) return true;
224 if (isEmptySet() || Other.isFullSet()) return false;
226 if (!isWrappedSet()) {
227 if (Other.isWrappedSet())
230 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
233 if (!Other.isWrappedSet())
234 return Other.getUpper().ule(Upper) ||
235 Lower.ule(Other.getLower());
237 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
240 /// subtract - Subtract the specified constant from the endpoints of this
242 ConstantRange ConstantRange::subtract(const APInt &Val) const {
243 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
244 // If the set is empty or full, don't modify the endpoints.
247 return ConstantRange(Lower - Val, Upper - Val);
250 /// \brief Subtract the specified range from this range (aka relative complement
252 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
253 return intersectWith(CR.inverse());
256 /// intersectWith - Return the range that results from the intersection of this
257 /// range with another range. The resultant range is guaranteed to include all
258 /// elements contained in both input ranges, and to have the smallest possible
259 /// set size that does so. Because there may be two intersections with the
260 /// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
261 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
262 assert(getBitWidth() == CR.getBitWidth() &&
263 "ConstantRange types don't agree!");
265 // Handle common cases.
266 if ( isEmptySet() || CR.isFullSet()) return *this;
267 if (CR.isEmptySet() || isFullSet()) return CR;
269 if (!isWrappedSet() && CR.isWrappedSet())
270 return CR.intersectWith(*this);
272 if (!isWrappedSet() && !CR.isWrappedSet()) {
273 if (Lower.ult(CR.Lower)) {
274 if (Upper.ule(CR.Lower))
275 return ConstantRange(getBitWidth(), false);
277 if (Upper.ult(CR.Upper))
278 return ConstantRange(CR.Lower, Upper);
282 if (Upper.ult(CR.Upper))
285 if (Lower.ult(CR.Upper))
286 return ConstantRange(Lower, CR.Upper);
288 return ConstantRange(getBitWidth(), false);
291 if (isWrappedSet() && !CR.isWrappedSet()) {
292 if (CR.Lower.ult(Upper)) {
293 if (CR.Upper.ult(Upper))
296 if (CR.Upper.ule(Lower))
297 return ConstantRange(CR.Lower, Upper);
299 if (getSetSize().ult(CR.getSetSize()))
303 if (CR.Lower.ult(Lower)) {
304 if (CR.Upper.ule(Lower))
305 return ConstantRange(getBitWidth(), false);
307 return ConstantRange(Lower, CR.Upper);
312 if (CR.Upper.ult(Upper)) {
313 if (CR.Lower.ult(Upper)) {
314 if (getSetSize().ult(CR.getSetSize()))
319 if (CR.Lower.ult(Lower))
320 return ConstantRange(Lower, CR.Upper);
324 if (CR.Upper.ule(Lower)) {
325 if (CR.Lower.ult(Lower))
328 return ConstantRange(CR.Lower, Upper);
330 if (getSetSize().ult(CR.getSetSize()))
336 /// unionWith - Return the range that results from the union of this range with
337 /// another range. The resultant range is guaranteed to include the elements of
338 /// both sets, but may contain more. For example, [3, 9) union [12,15) is
339 /// [3, 15), which includes 9, 10, and 11, which were not included in either
342 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
343 assert(getBitWidth() == CR.getBitWidth() &&
344 "ConstantRange types don't agree!");
346 if ( isFullSet() || CR.isEmptySet()) return *this;
347 if (CR.isFullSet() || isEmptySet()) return CR;
349 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
351 if (!isWrappedSet() && !CR.isWrappedSet()) {
352 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
353 // If the two ranges are disjoint, find the smaller gap and bridge it.
354 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
356 return ConstantRange(Lower, CR.Upper);
357 return ConstantRange(CR.Lower, Upper);
360 APInt L = Lower, U = Upper;
363 if ((CR.Upper - 1).ugt(U - 1))
366 if (L == 0 && U == 0)
367 return ConstantRange(getBitWidth());
369 return ConstantRange(L, U);
372 if (!CR.isWrappedSet()) {
373 // ------U L----- and ------U L----- : this
375 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
378 // ------U L----- : this
380 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
381 return ConstantRange(getBitWidth());
383 // ----U L---- : this
386 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
387 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
389 return ConstantRange(Lower, CR.Upper);
390 return ConstantRange(CR.Lower, Upper);
393 // ----U L----- : this
395 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
396 return ConstantRange(CR.Lower, Upper);
398 // ------U L---- : this
400 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
401 "ConstantRange::unionWith missed a case with one range wrapped");
402 return ConstantRange(Lower, CR.Upper);
405 // ------U L---- and ------U L---- : this
406 // -U L----------- and ------------U L : CR
407 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
408 return ConstantRange(getBitWidth());
410 APInt L = Lower, U = Upper;
416 return ConstantRange(L, U);
419 /// zeroExtend - Return a new range in the specified integer type, which must
420 /// be strictly larger than the current type. The returned range will
421 /// correspond to the possible range of values as if the source range had been
423 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
424 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
426 unsigned SrcTySize = getBitWidth();
427 assert(SrcTySize < DstTySize && "Not a value extension");
428 if (isFullSet() || isWrappedSet()) {
429 // Change into [0, 1 << src bit width)
430 APInt LowerExt(DstTySize, 0);
431 if (!Upper) // special case: [X, 0) -- not really wrapping around
432 LowerExt = Lower.zext(DstTySize);
433 return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize));
436 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
439 /// signExtend - Return a new range in the specified integer type, which must
440 /// be strictly larger than the current type. The returned range will
441 /// correspond to the possible range of values as if the source range had been
443 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
444 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
446 unsigned SrcTySize = getBitWidth();
447 assert(SrcTySize < DstTySize && "Not a value extension");
448 if (isFullSet() || isSignWrappedSet()) {
449 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
450 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
453 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
456 /// truncate - Return a new range in the specified integer type, which must be
457 /// strictly smaller than the current type. The returned range will
458 /// correspond to the possible range of values as if the source range had been
459 /// truncated to the specified type.
460 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
461 assert(getBitWidth() > DstTySize && "Not a value truncation");
463 return ConstantRange(DstTySize, /*isFullSet=*/false);
465 return ConstantRange(DstTySize, /*isFullSet=*/true);
467 APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth());
468 APInt MaxBitValue(getBitWidth(), 0);
469 MaxBitValue.setBit(DstTySize);
471 APInt LowerDiv(Lower), UpperDiv(Upper);
472 ConstantRange Union(DstTySize, /*isFullSet=*/false);
474 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
475 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
476 // then we do the union with [MaxValue, Upper)
477 if (isWrappedSet()) {
478 // if Upper is greater than Max Value, it covers the whole truncated range.
479 if (Upper.uge(MaxValue))
480 return ConstantRange(DstTySize, /*isFullSet=*/true);
482 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
483 UpperDiv = APInt::getMaxValue(getBitWidth());
485 // Union covers the MaxValue case, so return if the remaining range is just
487 if (LowerDiv == UpperDiv)
491 // Chop off the most significant bits that are past the destination bitwidth.
492 if (LowerDiv.uge(MaxValue)) {
493 APInt Div(getBitWidth(), 0);
494 APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
495 UpperDiv = UpperDiv - MaxBitValue * Div;
498 if (UpperDiv.ule(MaxValue))
499 return ConstantRange(LowerDiv.trunc(DstTySize),
500 UpperDiv.trunc(DstTySize)).unionWith(Union);
502 // The truncated value wrapps around. Check if we can do better than fullset.
503 APInt UpperModulo = UpperDiv - MaxBitValue;
504 if (UpperModulo.ult(LowerDiv))
505 return ConstantRange(LowerDiv.trunc(DstTySize),
506 UpperModulo.trunc(DstTySize)).unionWith(Union);
508 return ConstantRange(DstTySize, /*isFullSet=*/true);
511 /// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
512 /// value is zero extended, truncated, or left alone to make it that width.
513 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
514 unsigned SrcTySize = getBitWidth();
515 if (SrcTySize > DstTySize)
516 return truncate(DstTySize);
517 if (SrcTySize < DstTySize)
518 return zeroExtend(DstTySize);
522 /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
523 /// value is sign extended, truncated, or left alone to make it that width.
524 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
525 unsigned SrcTySize = getBitWidth();
526 if (SrcTySize > DstTySize)
527 return truncate(DstTySize);
528 if (SrcTySize < DstTySize)
529 return signExtend(DstTySize);
534 ConstantRange::add(const ConstantRange &Other) const {
535 if (isEmptySet() || Other.isEmptySet())
536 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
537 if (isFullSet() || Other.isFullSet())
538 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
540 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
541 APInt NewLower = getLower() + Other.getLower();
542 APInt NewUpper = getUpper() + Other.getUpper() - 1;
543 if (NewLower == NewUpper)
544 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
546 ConstantRange X = ConstantRange(NewLower, NewUpper);
547 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
548 // We've wrapped, therefore, full set.
549 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
555 ConstantRange::sub(const ConstantRange &Other) const {
556 if (isEmptySet() || Other.isEmptySet())
557 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
558 if (isFullSet() || Other.isFullSet())
559 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
561 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
562 APInt NewLower = getLower() - Other.getUpper() + 1;
563 APInt NewUpper = getUpper() - Other.getLower();
564 if (NewLower == NewUpper)
565 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
567 ConstantRange X = ConstantRange(NewLower, NewUpper);
568 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
569 // We've wrapped, therefore, full set.
570 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
576 ConstantRange::multiply(const ConstantRange &Other) const {
577 // TODO: If either operand is a single element and the multiply is known to
578 // be non-wrapping, round the result min and max value to the appropriate
579 // multiple of that element. If wrapping is possible, at least adjust the
580 // range according to the greatest power-of-two factor of the single element.
582 if (isEmptySet() || Other.isEmptySet())
583 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
585 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
586 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
587 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
588 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
590 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
591 this_max * Other_max + 1);
592 return Result_zext.truncate(getBitWidth());
596 ConstantRange::smax(const ConstantRange &Other) const {
597 // X smax Y is: range(smax(X_smin, Y_smin),
598 // smax(X_smax, Y_smax))
599 if (isEmptySet() || Other.isEmptySet())
600 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
601 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
602 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
604 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
605 return ConstantRange(NewL, NewU);
609 ConstantRange::umax(const ConstantRange &Other) const {
610 // X umax Y is: range(umax(X_umin, Y_umin),
611 // umax(X_umax, Y_umax))
612 if (isEmptySet() || Other.isEmptySet())
613 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
614 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
615 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
617 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
618 return ConstantRange(NewL, NewU);
622 ConstantRange::udiv(const ConstantRange &RHS) const {
623 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
624 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
626 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
628 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
630 APInt RHS_umin = RHS.getUnsignedMin();
632 // We want the lowest value in RHS excluding zero. Usually that would be 1
633 // except for a range in the form of [X, 1) in which case it would be X.
634 if (RHS.getUpper() == 1)
635 RHS_umin = RHS.getLower();
637 RHS_umin = APInt(getBitWidth(), 1);
640 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
642 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
645 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
647 return ConstantRange(Lower, Upper);
651 ConstantRange::binaryAnd(const ConstantRange &Other) const {
652 if (isEmptySet() || Other.isEmptySet())
653 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
655 // TODO: replace this with something less conservative
657 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
658 if (umin.isAllOnesValue())
659 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
660 return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
664 ConstantRange::binaryOr(const ConstantRange &Other) const {
665 if (isEmptySet() || Other.isEmptySet())
666 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
668 // TODO: replace this with something less conservative
670 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
671 if (umax.isMinValue())
672 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
673 return ConstantRange(umax, APInt::getNullValue(getBitWidth()));
677 ConstantRange::shl(const ConstantRange &Other) const {
678 if (isEmptySet() || Other.isEmptySet())
679 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
681 APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
682 APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
684 // there's no overflow!
685 APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
686 if (Zeros.ugt(Other.getUnsignedMax()))
687 return ConstantRange(min, max + 1);
689 // FIXME: implement the other tricky cases
690 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
694 ConstantRange::lshr(const ConstantRange &Other) const {
695 if (isEmptySet() || Other.isEmptySet())
696 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
698 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
699 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
701 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
703 return ConstantRange(min, max + 1);
706 ConstantRange ConstantRange::inverse() const {
708 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
710 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
711 return ConstantRange(Upper, Lower);
714 /// print - Print out the bounds to a stream...
716 void ConstantRange::print(raw_ostream &OS) const {
719 else if (isEmptySet())
722 OS << "[" << Lower << "," << Upper << ")";
725 /// dump - Allow printing from a debugger easily...
727 void ConstantRange::dump() const {