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::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");
449 // special case: [X, INT_MIN) -- not really wrapping around
450 if (Upper
.isMinSignedValue())
451 return ConstantRange(Lower
.sext(DstTySize
), Upper
.zext(DstTySize
));
453 if (isFullSet() || isSignWrappedSet()) {
454 return ConstantRange(APInt::getHighBitsSet(DstTySize
,DstTySize
-SrcTySize
+1),
455 APInt::getLowBitsSet(DstTySize
, SrcTySize
-1) + 1);
458 return ConstantRange(Lower
.sext(DstTySize
), Upper
.sext(DstTySize
));
461 /// truncate - Return a new range in the specified integer type, which must be
462 /// strictly smaller than the current type. The returned range will
463 /// correspond to the possible range of values as if the source range had been
464 /// truncated to the specified type.
465 ConstantRange
ConstantRange::truncate(uint32_t DstTySize
) const {
466 assert(getBitWidth() > DstTySize
&& "Not a value truncation");
468 return ConstantRange(DstTySize
, /*isFullSet=*/false);
470 return ConstantRange(DstTySize
, /*isFullSet=*/true);
472 APInt MaxValue
= APInt::getMaxValue(DstTySize
).zext(getBitWidth());
473 APInt
MaxBitValue(getBitWidth(), 0);
474 MaxBitValue
.setBit(DstTySize
);
476 APInt
LowerDiv(Lower
), UpperDiv(Upper
);
477 ConstantRange
Union(DstTySize
, /*isFullSet=*/false);
479 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
480 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
481 // then we do the union with [MaxValue, Upper)
482 if (isWrappedSet()) {
483 // if Upper is greater than Max Value, it covers the whole truncated range.
484 if (Upper
.uge(MaxValue
))
485 return ConstantRange(DstTySize
, /*isFullSet=*/true);
487 Union
= ConstantRange(APInt::getMaxValue(DstTySize
),Upper
.trunc(DstTySize
));
488 UpperDiv
= APInt::getMaxValue(getBitWidth());
490 // Union covers the MaxValue case, so return if the remaining range is just
492 if (LowerDiv
== UpperDiv
)
496 // Chop off the most significant bits that are past the destination bitwidth.
497 if (LowerDiv
.uge(MaxValue
)) {
498 APInt
Div(getBitWidth(), 0);
499 APInt::udivrem(LowerDiv
, MaxBitValue
, Div
, LowerDiv
);
500 UpperDiv
= UpperDiv
- MaxBitValue
* Div
;
503 if (UpperDiv
.ule(MaxValue
))
504 return ConstantRange(LowerDiv
.trunc(DstTySize
),
505 UpperDiv
.trunc(DstTySize
)).unionWith(Union
);
507 // The truncated value wrapps around. Check if we can do better than fullset.
508 APInt UpperModulo
= UpperDiv
- MaxBitValue
;
509 if (UpperModulo
.ult(LowerDiv
))
510 return ConstantRange(LowerDiv
.trunc(DstTySize
),
511 UpperModulo
.trunc(DstTySize
)).unionWith(Union
);
513 return ConstantRange(DstTySize
, /*isFullSet=*/true);
516 /// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
517 /// value is zero extended, truncated, or left alone to make it that width.
518 ConstantRange
ConstantRange::zextOrTrunc(uint32_t DstTySize
) const {
519 unsigned SrcTySize
= getBitWidth();
520 if (SrcTySize
> DstTySize
)
521 return truncate(DstTySize
);
522 if (SrcTySize
< DstTySize
)
523 return zeroExtend(DstTySize
);
527 /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
528 /// value is sign extended, truncated, or left alone to make it that width.
529 ConstantRange
ConstantRange::sextOrTrunc(uint32_t DstTySize
) const {
530 unsigned SrcTySize
= getBitWidth();
531 if (SrcTySize
> DstTySize
)
532 return truncate(DstTySize
);
533 if (SrcTySize
< DstTySize
)
534 return signExtend(DstTySize
);
539 ConstantRange::add(const ConstantRange
&Other
) const {
540 if (isEmptySet() || Other
.isEmptySet())
541 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
542 if (isFullSet() || Other
.isFullSet())
543 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
545 APInt Spread_X
= getSetSize(), Spread_Y
= Other
.getSetSize();
546 APInt NewLower
= getLower() + Other
.getLower();
547 APInt NewUpper
= getUpper() + Other
.getUpper() - 1;
548 if (NewLower
== NewUpper
)
549 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
551 ConstantRange X
= ConstantRange(NewLower
, NewUpper
);
552 if (X
.getSetSize().ult(Spread_X
) || X
.getSetSize().ult(Spread_Y
))
553 // We've wrapped, therefore, full set.
554 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
560 ConstantRange::sub(const ConstantRange
&Other
) const {
561 if (isEmptySet() || Other
.isEmptySet())
562 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
563 if (isFullSet() || Other
.isFullSet())
564 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
566 APInt Spread_X
= getSetSize(), Spread_Y
= Other
.getSetSize();
567 APInt NewLower
= getLower() - Other
.getUpper() + 1;
568 APInt NewUpper
= getUpper() - Other
.getLower();
569 if (NewLower
== NewUpper
)
570 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
572 ConstantRange X
= ConstantRange(NewLower
, NewUpper
);
573 if (X
.getSetSize().ult(Spread_X
) || X
.getSetSize().ult(Spread_Y
))
574 // We've wrapped, therefore, full set.
575 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
581 ConstantRange::multiply(const ConstantRange
&Other
) const {
582 // TODO: If either operand is a single element and the multiply is known to
583 // be non-wrapping, round the result min and max value to the appropriate
584 // multiple of that element. If wrapping is possible, at least adjust the
585 // range according to the greatest power-of-two factor of the single element.
587 if (isEmptySet() || Other
.isEmptySet())
588 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
590 APInt this_min
= getUnsignedMin().zext(getBitWidth() * 2);
591 APInt this_max
= getUnsignedMax().zext(getBitWidth() * 2);
592 APInt Other_min
= Other
.getUnsignedMin().zext(getBitWidth() * 2);
593 APInt Other_max
= Other
.getUnsignedMax().zext(getBitWidth() * 2);
595 ConstantRange Result_zext
= ConstantRange(this_min
* Other_min
,
596 this_max
* Other_max
+ 1);
597 return Result_zext
.truncate(getBitWidth());
601 ConstantRange::smax(const ConstantRange
&Other
) const {
602 // X smax Y is: range(smax(X_smin, Y_smin),
603 // smax(X_smax, Y_smax))
604 if (isEmptySet() || Other
.isEmptySet())
605 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
606 APInt NewL
= APIntOps::smax(getSignedMin(), Other
.getSignedMin());
607 APInt NewU
= APIntOps::smax(getSignedMax(), Other
.getSignedMax()) + 1;
609 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
610 return ConstantRange(NewL
, NewU
);
614 ConstantRange::umax(const ConstantRange
&Other
) const {
615 // X umax Y is: range(umax(X_umin, Y_umin),
616 // umax(X_umax, Y_umax))
617 if (isEmptySet() || Other
.isEmptySet())
618 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
619 APInt NewL
= APIntOps::umax(getUnsignedMin(), Other
.getUnsignedMin());
620 APInt NewU
= APIntOps::umax(getUnsignedMax(), Other
.getUnsignedMax()) + 1;
622 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
623 return ConstantRange(NewL
, NewU
);
627 ConstantRange::udiv(const ConstantRange
&RHS
) const {
628 if (isEmptySet() || RHS
.isEmptySet() || RHS
.getUnsignedMax() == 0)
629 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
631 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
633 APInt Lower
= getUnsignedMin().udiv(RHS
.getUnsignedMax());
635 APInt RHS_umin
= RHS
.getUnsignedMin();
637 // We want the lowest value in RHS excluding zero. Usually that would be 1
638 // except for a range in the form of [X, 1) in which case it would be X.
639 if (RHS
.getUpper() == 1)
640 RHS_umin
= RHS
.getLower();
642 RHS_umin
= APInt(getBitWidth(), 1);
645 APInt Upper
= getUnsignedMax().udiv(RHS_umin
) + 1;
647 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
650 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
652 return ConstantRange(Lower
, Upper
);
656 ConstantRange::binaryAnd(const ConstantRange
&Other
) const {
657 if (isEmptySet() || Other
.isEmptySet())
658 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
660 // TODO: replace this with something less conservative
662 APInt umin
= APIntOps::umin(Other
.getUnsignedMax(), getUnsignedMax());
663 if (umin
.isAllOnesValue())
664 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
665 return ConstantRange(APInt::getNullValue(getBitWidth()), umin
+ 1);
669 ConstantRange::binaryOr(const ConstantRange
&Other
) const {
670 if (isEmptySet() || Other
.isEmptySet())
671 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
673 // TODO: replace this with something less conservative
675 APInt umax
= APIntOps::umax(getUnsignedMin(), Other
.getUnsignedMin());
676 if (umax
.isMinValue())
677 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
678 return ConstantRange(umax
, APInt::getNullValue(getBitWidth()));
682 ConstantRange::shl(const ConstantRange
&Other
) const {
683 if (isEmptySet() || Other
.isEmptySet())
684 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
686 APInt min
= getUnsignedMin().shl(Other
.getUnsignedMin());
687 APInt max
= getUnsignedMax().shl(Other
.getUnsignedMax());
689 // there's no overflow!
690 APInt
Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
691 if (Zeros
.ugt(Other
.getUnsignedMax()))
692 return ConstantRange(min
, max
+ 1);
694 // FIXME: implement the other tricky cases
695 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
699 ConstantRange::lshr(const ConstantRange
&Other
) const {
700 if (isEmptySet() || Other
.isEmptySet())
701 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
703 APInt max
= getUnsignedMax().lshr(Other
.getUnsignedMin());
704 APInt min
= getUnsignedMin().lshr(Other
.getUnsignedMax());
706 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
708 return ConstantRange(min
, max
+ 1);
711 ConstantRange
ConstantRange::inverse() const {
713 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
715 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
716 return ConstantRange(Upper
, Lower
);
719 /// print - Print out the bounds to a stream...
721 void ConstantRange::print(raw_ostream
&OS
) const {
724 else if (isEmptySet())
727 OS
<< "[" << Lower
<< "," << Upper
<< ")";
730 /// dump - Allow printing from a debugger easily...
732 void ConstantRange::dump() const {