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/IR/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(std::move(V)), Upper(Lower + 1) {}
44 ConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U)
45 : Lower(std::move(L)), Upper(std::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::makeAllowedICmpRegion(CmpInst::Predicate Pred,
53 const ConstantRange &CR) {
57 uint32_t W = CR.getBitWidth();
60 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
61 case CmpInst::ICMP_EQ:
63 case CmpInst::ICMP_NE:
64 if (CR.isSingleElement())
65 return ConstantRange(CR.getUpper(), CR.getLower());
66 return ConstantRange(W);
67 case CmpInst::ICMP_ULT: {
68 APInt UMax(CR.getUnsignedMax());
69 if (UMax.isMinValue())
70 return ConstantRange(W, /* empty */ false);
71 return ConstantRange(APInt::getMinValue(W), UMax);
73 case CmpInst::ICMP_SLT: {
74 APInt SMax(CR.getSignedMax());
75 if (SMax.isMinSignedValue())
76 return ConstantRange(W, /* empty */ false);
77 return ConstantRange(APInt::getSignedMinValue(W), SMax);
79 case CmpInst::ICMP_ULE: {
80 APInt UMax(CR.getUnsignedMax());
81 if (UMax.isMaxValue())
82 return ConstantRange(W);
83 return ConstantRange(APInt::getMinValue(W), UMax + 1);
85 case CmpInst::ICMP_SLE: {
86 APInt SMax(CR.getSignedMax());
87 if (SMax.isMaxSignedValue())
88 return ConstantRange(W);
89 return ConstantRange(APInt::getSignedMinValue(W), SMax + 1);
91 case CmpInst::ICMP_UGT: {
92 APInt UMin(CR.getUnsignedMin());
93 if (UMin.isMaxValue())
94 return ConstantRange(W, /* empty */ false);
95 return ConstantRange(UMin + 1, APInt::getNullValue(W));
97 case CmpInst::ICMP_SGT: {
98 APInt SMin(CR.getSignedMin());
99 if (SMin.isMaxSignedValue())
100 return ConstantRange(W, /* empty */ false);
101 return ConstantRange(SMin + 1, APInt::getSignedMinValue(W));
103 case CmpInst::ICMP_UGE: {
104 APInt UMin(CR.getUnsignedMin());
105 if (UMin.isMinValue())
106 return ConstantRange(W);
107 return ConstantRange(UMin, APInt::getNullValue(W));
109 case CmpInst::ICMP_SGE: {
110 APInt SMin(CR.getSignedMin());
111 if (SMin.isMinSignedValue())
112 return ConstantRange(W);
113 return ConstantRange(SMin, APInt::getSignedMinValue(W));
118 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
119 const ConstantRange &CR) {
120 // Follows from De-Morgan's laws:
122 // ~(~A union ~B) == A intersect B.
124 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
128 /// isFullSet - Return true if this set contains all of the elements possible
129 /// for this data-type
130 bool ConstantRange::isFullSet() const {
131 return Lower == Upper && Lower.isMaxValue();
134 /// isEmptySet - Return true if this set contains no members.
136 bool ConstantRange::isEmptySet() const {
137 return Lower == Upper && Lower.isMinValue();
140 /// isWrappedSet - Return true if this set wraps around the top of the range,
141 /// for example: [100, 8)
143 bool ConstantRange::isWrappedSet() const {
144 return Lower.ugt(Upper);
147 /// isSignWrappedSet - Return true if this set wraps around the INT_MIN of
148 /// its bitwidth, for example: i8 [120, 140).
150 bool ConstantRange::isSignWrappedSet() const {
151 return contains(APInt::getSignedMaxValue(getBitWidth())) &&
152 contains(APInt::getSignedMinValue(getBitWidth()));
155 /// getSetSize - Return the number of elements in this set.
157 APInt ConstantRange::getSetSize() const {
159 APInt Size(getBitWidth()+1, 0);
160 Size.setBit(getBitWidth());
164 // This is also correct for wrapped sets.
165 return (Upper - Lower).zext(getBitWidth()+1);
168 /// getUnsignedMax - Return the largest unsigned value contained in the
171 APInt ConstantRange::getUnsignedMax() const {
172 if (isFullSet() || isWrappedSet())
173 return APInt::getMaxValue(getBitWidth());
174 return getUpper() - 1;
177 /// getUnsignedMin - Return the smallest unsigned value contained in the
180 APInt ConstantRange::getUnsignedMin() const {
181 if (isFullSet() || (isWrappedSet() && getUpper() != 0))
182 return APInt::getMinValue(getBitWidth());
186 /// getSignedMax - Return the largest signed value contained in the
189 APInt ConstantRange::getSignedMax() const {
190 APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
191 if (!isWrappedSet()) {
192 if (getLower().sle(getUpper() - 1))
193 return getUpper() - 1;
196 if (getLower().isNegative() == getUpper().isNegative())
198 return getUpper() - 1;
201 /// getSignedMin - Return the smallest signed value contained in the
204 APInt ConstantRange::getSignedMin() const {
205 APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
206 if (!isWrappedSet()) {
207 if (getLower().sle(getUpper() - 1))
211 if ((getUpper() - 1).slt(getLower())) {
212 if (getUpper() != SignedMin)
218 /// contains - Return true if the specified value is in the set.
220 bool ConstantRange::contains(const APInt &V) const {
225 return Lower.ule(V) && V.ult(Upper);
226 return Lower.ule(V) || V.ult(Upper);
229 /// contains - Return true if the argument is a subset of this range.
230 /// Two equal sets contain each other. The empty set contained by all other
233 bool ConstantRange::contains(const ConstantRange &Other) const {
234 if (isFullSet() || Other.isEmptySet()) return true;
235 if (isEmptySet() || Other.isFullSet()) return false;
237 if (!isWrappedSet()) {
238 if (Other.isWrappedSet())
241 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
244 if (!Other.isWrappedSet())
245 return Other.getUpper().ule(Upper) ||
246 Lower.ule(Other.getLower());
248 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
251 /// subtract - Subtract the specified constant from the endpoints of this
253 ConstantRange ConstantRange::subtract(const APInt &Val) const {
254 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
255 // If the set is empty or full, don't modify the endpoints.
258 return ConstantRange(Lower - Val, Upper - Val);
261 /// \brief Subtract the specified range from this range (aka relative complement
263 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
264 return intersectWith(CR.inverse());
267 /// intersectWith - Return the range that results from the intersection of this
268 /// range with another range. The resultant range is guaranteed to include all
269 /// elements contained in both input ranges, and to have the smallest possible
270 /// set size that does so. Because there may be two intersections with the
271 /// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
272 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
273 assert(getBitWidth() == CR.getBitWidth() &&
274 "ConstantRange types don't agree!");
276 // Handle common cases.
277 if ( isEmptySet() || CR.isFullSet()) return *this;
278 if (CR.isEmptySet() || isFullSet()) return CR;
280 if (!isWrappedSet() && CR.isWrappedSet())
281 return CR.intersectWith(*this);
283 if (!isWrappedSet() && !CR.isWrappedSet()) {
284 if (Lower.ult(CR.Lower)) {
285 if (Upper.ule(CR.Lower))
286 return ConstantRange(getBitWidth(), false);
288 if (Upper.ult(CR.Upper))
289 return ConstantRange(CR.Lower, Upper);
293 if (Upper.ult(CR.Upper))
296 if (Lower.ult(CR.Upper))
297 return ConstantRange(Lower, CR.Upper);
299 return ConstantRange(getBitWidth(), false);
302 if (isWrappedSet() && !CR.isWrappedSet()) {
303 if (CR.Lower.ult(Upper)) {
304 if (CR.Upper.ult(Upper))
307 if (CR.Upper.ule(Lower))
308 return ConstantRange(CR.Lower, Upper);
310 if (getSetSize().ult(CR.getSetSize()))
314 if (CR.Lower.ult(Lower)) {
315 if (CR.Upper.ule(Lower))
316 return ConstantRange(getBitWidth(), false);
318 return ConstantRange(Lower, CR.Upper);
323 if (CR.Upper.ult(Upper)) {
324 if (CR.Lower.ult(Upper)) {
325 if (getSetSize().ult(CR.getSetSize()))
330 if (CR.Lower.ult(Lower))
331 return ConstantRange(Lower, CR.Upper);
335 if (CR.Upper.ule(Lower)) {
336 if (CR.Lower.ult(Lower))
339 return ConstantRange(CR.Lower, Upper);
341 if (getSetSize().ult(CR.getSetSize()))
347 /// unionWith - Return the range that results from the union of this range with
348 /// another range. The resultant range is guaranteed to include the elements of
349 /// both sets, but may contain more. For example, [3, 9) union [12,15) is
350 /// [3, 15), which includes 9, 10, and 11, which were not included in either
353 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
354 assert(getBitWidth() == CR.getBitWidth() &&
355 "ConstantRange types don't agree!");
357 if ( isFullSet() || CR.isEmptySet()) return *this;
358 if (CR.isFullSet() || isEmptySet()) return CR;
360 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
362 if (!isWrappedSet() && !CR.isWrappedSet()) {
363 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
364 // If the two ranges are disjoint, find the smaller gap and bridge it.
365 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
367 return ConstantRange(Lower, CR.Upper);
368 return ConstantRange(CR.Lower, Upper);
371 APInt L = Lower, U = Upper;
374 if ((CR.Upper - 1).ugt(U - 1))
377 if (L == 0 && U == 0)
378 return ConstantRange(getBitWidth());
380 return ConstantRange(L, U);
383 if (!CR.isWrappedSet()) {
384 // ------U L----- and ------U L----- : this
386 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
389 // ------U L----- : this
391 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
392 return ConstantRange(getBitWidth());
394 // ----U L---- : this
397 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
398 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
400 return ConstantRange(Lower, CR.Upper);
401 return ConstantRange(CR.Lower, Upper);
404 // ----U L----- : this
406 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
407 return ConstantRange(CR.Lower, Upper);
409 // ------U L---- : this
411 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
412 "ConstantRange::unionWith missed a case with one range wrapped");
413 return ConstantRange(Lower, CR.Upper);
416 // ------U L---- and ------U L---- : this
417 // -U L----------- and ------------U L : CR
418 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
419 return ConstantRange(getBitWidth());
421 APInt L = Lower, U = Upper;
427 return ConstantRange(L, U);
430 /// zeroExtend - Return a new range in the specified integer type, which must
431 /// be strictly larger than the current type. The returned range will
432 /// correspond to the possible range of values as if the source range had been
434 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
435 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
437 unsigned SrcTySize = getBitWidth();
438 assert(SrcTySize < DstTySize && "Not a value extension");
439 if (isFullSet() || isWrappedSet()) {
440 // Change into [0, 1 << src bit width)
441 APInt LowerExt(DstTySize, 0);
442 if (!Upper) // special case: [X, 0) -- not really wrapping around
443 LowerExt = Lower.zext(DstTySize);
444 return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize));
447 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
450 /// signExtend - Return a new range in the specified integer type, which must
451 /// be strictly larger than the current type. The returned range will
452 /// correspond to the possible range of values as if the source range had been
454 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
455 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
457 unsigned SrcTySize = getBitWidth();
458 assert(SrcTySize < DstTySize && "Not a value extension");
460 // special case: [X, INT_MIN) -- not really wrapping around
461 if (Upper.isMinSignedValue())
462 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
464 if (isFullSet() || isSignWrappedSet()) {
465 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
466 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
469 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
472 /// truncate - Return a new range in the specified integer type, which must be
473 /// strictly smaller than the current type. The returned range will
474 /// correspond to the possible range of values as if the source range had been
475 /// truncated to the specified type.
476 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
477 assert(getBitWidth() > DstTySize && "Not a value truncation");
479 return ConstantRange(DstTySize, /*isFullSet=*/false);
481 return ConstantRange(DstTySize, /*isFullSet=*/true);
483 APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth());
484 APInt MaxBitValue(getBitWidth(), 0);
485 MaxBitValue.setBit(DstTySize);
487 APInt LowerDiv(Lower), UpperDiv(Upper);
488 ConstantRange Union(DstTySize, /*isFullSet=*/false);
490 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
491 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
492 // then we do the union with [MaxValue, Upper)
493 if (isWrappedSet()) {
494 // if Upper is greater than Max Value, it covers the whole truncated range.
495 if (Upper.uge(MaxValue))
496 return ConstantRange(DstTySize, /*isFullSet=*/true);
498 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
499 UpperDiv = APInt::getMaxValue(getBitWidth());
501 // Union covers the MaxValue case, so return if the remaining range is just
503 if (LowerDiv == UpperDiv)
507 // Chop off the most significant bits that are past the destination bitwidth.
508 if (LowerDiv.uge(MaxValue)) {
509 APInt Div(getBitWidth(), 0);
510 APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
511 UpperDiv = UpperDiv - MaxBitValue * Div;
514 if (UpperDiv.ule(MaxValue))
515 return ConstantRange(LowerDiv.trunc(DstTySize),
516 UpperDiv.trunc(DstTySize)).unionWith(Union);
518 // The truncated value wrapps around. Check if we can do better than fullset.
519 APInt UpperModulo = UpperDiv - MaxBitValue;
520 if (UpperModulo.ult(LowerDiv))
521 return ConstantRange(LowerDiv.trunc(DstTySize),
522 UpperModulo.trunc(DstTySize)).unionWith(Union);
524 return ConstantRange(DstTySize, /*isFullSet=*/true);
527 /// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
528 /// value is zero extended, truncated, or left alone to make it that width.
529 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
530 unsigned SrcTySize = getBitWidth();
531 if (SrcTySize > DstTySize)
532 return truncate(DstTySize);
533 if (SrcTySize < DstTySize)
534 return zeroExtend(DstTySize);
538 /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
539 /// value is sign extended, truncated, or left alone to make it that width.
540 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
541 unsigned SrcTySize = getBitWidth();
542 if (SrcTySize > DstTySize)
543 return truncate(DstTySize);
544 if (SrcTySize < DstTySize)
545 return signExtend(DstTySize);
550 ConstantRange::add(const ConstantRange &Other) const {
551 if (isEmptySet() || Other.isEmptySet())
552 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
553 if (isFullSet() || Other.isFullSet())
554 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
556 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
557 APInt NewLower = getLower() + Other.getLower();
558 APInt NewUpper = getUpper() + Other.getUpper() - 1;
559 if (NewLower == NewUpper)
560 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
562 ConstantRange X = ConstantRange(NewLower, NewUpper);
563 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
564 // We've wrapped, therefore, full set.
565 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
571 ConstantRange::sub(const ConstantRange &Other) const {
572 if (isEmptySet() || Other.isEmptySet())
573 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
574 if (isFullSet() || Other.isFullSet())
575 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
577 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
578 APInt NewLower = getLower() - Other.getUpper() + 1;
579 APInt NewUpper = getUpper() - Other.getLower();
580 if (NewLower == NewUpper)
581 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
583 ConstantRange X = ConstantRange(NewLower, NewUpper);
584 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
585 // We've wrapped, therefore, full set.
586 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
592 ConstantRange::multiply(const ConstantRange &Other) const {
593 // TODO: If either operand is a single element and the multiply is known to
594 // be non-wrapping, round the result min and max value to the appropriate
595 // multiple of that element. If wrapping is possible, at least adjust the
596 // range according to the greatest power-of-two factor of the single element.
598 if (isEmptySet() || Other.isEmptySet())
599 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
601 // Multiplication is signedness-independent. However different ranges can be
602 // obtained depending on how the input ranges are treated. These different
603 // ranges are all conservatively correct, but one might be better than the
604 // other. We calculate two ranges; one treating the inputs as unsigned
605 // and the other signed, then return the smallest of these ranges.
607 // Unsigned range first.
608 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
609 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
610 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
611 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
613 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
614 this_max * Other_max + 1);
615 ConstantRange UR = Result_zext.truncate(getBitWidth());
617 // Now the signed range. Because we could be dealing with negative numbers
618 // here, the lower bound is the smallest of the cartesian product of the
619 // lower and upper ranges; for example:
620 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
621 // Similarly for the upper bound, swapping min for max.
623 this_min = getSignedMin().sext(getBitWidth() * 2);
624 this_max = getSignedMax().sext(getBitWidth() * 2);
625 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
626 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
628 auto L = {this_min * Other_min, this_min * Other_max,
629 this_max * Other_min, this_max * Other_max};
630 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
631 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
632 ConstantRange SR = Result_sext.truncate(getBitWidth());
634 return UR.getSetSize().ult(SR.getSetSize()) ? UR : SR;
638 ConstantRange::smax(const ConstantRange &Other) const {
639 // X smax Y is: range(smax(X_smin, Y_smin),
640 // smax(X_smax, Y_smax))
641 if (isEmptySet() || Other.isEmptySet())
642 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
643 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
644 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
646 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
647 return ConstantRange(NewL, NewU);
651 ConstantRange::umax(const ConstantRange &Other) const {
652 // X umax Y is: range(umax(X_umin, Y_umin),
653 // umax(X_umax, Y_umax))
654 if (isEmptySet() || Other.isEmptySet())
655 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
656 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
657 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
659 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
660 return ConstantRange(NewL, NewU);
664 ConstantRange::udiv(const ConstantRange &RHS) const {
665 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
666 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
668 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
670 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
672 APInt RHS_umin = RHS.getUnsignedMin();
674 // We want the lowest value in RHS excluding zero. Usually that would be 1
675 // except for a range in the form of [X, 1) in which case it would be X.
676 if (RHS.getUpper() == 1)
677 RHS_umin = RHS.getLower();
679 RHS_umin = APInt(getBitWidth(), 1);
682 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
684 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
687 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
689 return ConstantRange(Lower, Upper);
693 ConstantRange::binaryAnd(const ConstantRange &Other) const {
694 if (isEmptySet() || Other.isEmptySet())
695 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
697 // TODO: replace this with something less conservative
699 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
700 if (umin.isAllOnesValue())
701 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
702 return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
706 ConstantRange::binaryOr(const ConstantRange &Other) const {
707 if (isEmptySet() || Other.isEmptySet())
708 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
710 // TODO: replace this with something less conservative
712 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
713 if (umax.isMinValue())
714 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
715 return ConstantRange(umax, APInt::getNullValue(getBitWidth()));
719 ConstantRange::shl(const ConstantRange &Other) const {
720 if (isEmptySet() || Other.isEmptySet())
721 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
723 APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
724 APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
726 // there's no overflow!
727 APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
728 if (Zeros.ugt(Other.getUnsignedMax()))
729 return ConstantRange(min, max + 1);
731 // FIXME: implement the other tricky cases
732 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
736 ConstantRange::lshr(const ConstantRange &Other) const {
737 if (isEmptySet() || Other.isEmptySet())
738 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
740 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
741 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
743 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
745 return ConstantRange(min, max + 1);
748 ConstantRange ConstantRange::inverse() const {
750 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
752 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
753 return ConstantRange(Upper, Lower);
756 /// print - Print out the bounds to a stream...
758 void ConstantRange::print(raw_ostream &OS) const {
761 else if (isEmptySet())
764 OS << "[" << Lower << "," << Upper << ")";
767 /// dump - Allow printing from a debugger easily...
769 void ConstantRange::dump() const {