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/Constants.h"
25 #include "llvm/Support/ConstantRange.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/Instructions.h"
31 /// Initialize a full (the default) or empty set for the specified type.
33 ConstantRange::ConstantRange(uint32_t BitWidth
, bool Full
) {
35 Lower
= Upper
= APInt::getMaxValue(BitWidth
);
37 Lower
= Upper
= APInt::getMinValue(BitWidth
);
40 /// Initialize a range to hold the single specified value.
42 ConstantRange::ConstantRange(const APInt
&V
) : Lower(V
), Upper(V
+ 1) {}
44 ConstantRange::ConstantRange(const APInt
&L
, const APInt
&U
) :
46 assert(L
.getBitWidth() == U
.getBitWidth() &&
47 "ConstantRange with unequal bit widths");
48 assert((L
!= U
|| (L
.isMaxValue() || L
.isMinValue())) &&
49 "Lower == Upper, but they aren't min or max value!");
52 ConstantRange
ConstantRange::makeICmpRegion(unsigned Pred
,
53 const ConstantRange
&CR
) {
54 uint32_t W
= CR
.getBitWidth();
56 default: assert(!"Invalid ICmp predicate to makeICmpRegion()");
57 case ICmpInst::ICMP_EQ
:
59 case ICmpInst::ICMP_NE
:
60 if (CR
.isSingleElement())
61 return ConstantRange(CR
.getUpper(), CR
.getLower());
62 return ConstantRange(W
);
63 case ICmpInst::ICMP_ULT
:
64 return ConstantRange(APInt::getMinValue(W
), CR
.getUnsignedMax());
65 case ICmpInst::ICMP_SLT
:
66 return ConstantRange(APInt::getSignedMinValue(W
), CR
.getSignedMax());
67 case ICmpInst::ICMP_ULE
: {
68 APInt
UMax(CR
.getUnsignedMax());
69 if (UMax
.isMaxValue())
70 return ConstantRange(W
);
71 return ConstantRange(APInt::getMinValue(W
), UMax
+ 1);
73 case ICmpInst::ICMP_SLE
: {
74 APInt
SMax(CR
.getSignedMax());
75 if (SMax
.isMaxSignedValue() || (SMax
+1).isMaxSignedValue())
76 return ConstantRange(W
);
77 return ConstantRange(APInt::getSignedMinValue(W
), SMax
+ 1);
79 case ICmpInst::ICMP_UGT
:
80 return ConstantRange(CR
.getUnsignedMin() + 1, APInt::getNullValue(W
));
81 case ICmpInst::ICMP_SGT
:
82 return ConstantRange(CR
.getSignedMin() + 1,
83 APInt::getSignedMinValue(W
));
84 case ICmpInst::ICMP_UGE
: {
85 APInt
UMin(CR
.getUnsignedMin());
86 if (UMin
.isMinValue())
87 return ConstantRange(W
);
88 return ConstantRange(UMin
, APInt::getNullValue(W
));
90 case ICmpInst::ICMP_SGE
: {
91 APInt
SMin(CR
.getSignedMin());
92 if (SMin
.isMinSignedValue())
93 return ConstantRange(W
);
94 return ConstantRange(SMin
, APInt::getSignedMinValue(W
));
99 /// isFullSet - Return true if this set contains all of the elements possible
100 /// for this data-type
101 bool ConstantRange::isFullSet() const {
102 return Lower
== Upper
&& Lower
.isMaxValue();
105 /// isEmptySet - Return true if this set contains no members.
107 bool ConstantRange::isEmptySet() const {
108 return Lower
== Upper
&& Lower
.isMinValue();
111 /// isWrappedSet - Return true if this set wraps around the top of the range,
112 /// for example: [100, 8)
114 bool ConstantRange::isWrappedSet() const {
115 return Lower
.ugt(Upper
);
118 /// getSetSize - Return the number of elements in this set.
120 APInt
ConstantRange::getSetSize() const {
122 return APInt(getBitWidth(), 0);
123 if (getBitWidth() == 1) {
124 if (Lower
!= Upper
) // One of T or F in the set...
126 return APInt(2, 2); // Must be full set...
129 // Simply subtract the bounds...
130 return Upper
- Lower
;
133 /// getUnsignedMax - Return the largest unsigned value contained in the
136 APInt
ConstantRange::getUnsignedMax() const {
137 if (isFullSet() || isWrappedSet())
138 return APInt::getMaxValue(getBitWidth());
140 return getUpper() - 1;
143 /// getUnsignedMin - Return the smallest unsigned value contained in the
146 APInt
ConstantRange::getUnsignedMin() const {
147 if (isFullSet() || (isWrappedSet() && getUpper() != 0))
148 return APInt::getMinValue(getBitWidth());
153 /// getSignedMax - Return the largest signed value contained in the
156 APInt
ConstantRange::getSignedMax() const {
157 APInt
SignedMax(APInt::getSignedMaxValue(getBitWidth()));
158 if (!isWrappedSet()) {
159 if (getLower().sle(getUpper() - 1))
160 return getUpper() - 1;
164 if (getLower().isNegative() == getUpper().isNegative())
167 return getUpper() - 1;
171 /// getSignedMin - Return the smallest signed value contained in the
174 APInt
ConstantRange::getSignedMin() const {
175 APInt
SignedMin(APInt::getSignedMinValue(getBitWidth()));
176 if (!isWrappedSet()) {
177 if (getLower().sle(getUpper() - 1))
182 if ((getUpper() - 1).slt(getLower())) {
183 if (getUpper() != SignedMin
)
193 /// contains - Return true if the specified value is in the set.
195 bool ConstantRange::contains(const APInt
&V
) const {
200 return Lower
.ule(V
) && V
.ult(Upper
);
202 return Lower
.ule(V
) || V
.ult(Upper
);
205 /// contains - Return true if the argument is a subset of this range.
206 /// Two equal sets contain each other. The empty set contained by all other
209 bool ConstantRange::contains(const ConstantRange
&Other
) const {
210 if (isFullSet() || Other
.isEmptySet()) return true;
211 if (isEmptySet() || Other
.isFullSet()) return false;
213 if (!isWrappedSet()) {
214 if (Other
.isWrappedSet())
217 return Lower
.ule(Other
.getLower()) && Other
.getUpper().ule(Upper
);
220 if (!Other
.isWrappedSet())
221 return Other
.getUpper().ule(Upper
) ||
222 Lower
.ule(Other
.getLower());
224 return Other
.getUpper().ule(Upper
) && Lower
.ule(Other
.getLower());
227 /// subtract - Subtract the specified constant from the endpoints of this
229 ConstantRange
ConstantRange::subtract(const APInt
&Val
) const {
230 assert(Val
.getBitWidth() == getBitWidth() && "Wrong bit width");
231 // If the set is empty or full, don't modify the endpoints.
234 return ConstantRange(Lower
- Val
, Upper
- Val
);
237 /// intersectWith - Return the range that results from the intersection of this
238 /// range with another range. The resultant range is guaranteed to include all
239 /// elements contained in both input ranges, and to have the smallest possible
240 /// set size that does so. Because there may be two intersections with the
241 /// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
242 ConstantRange
ConstantRange::intersectWith(const ConstantRange
&CR
) const {
243 assert(getBitWidth() == CR
.getBitWidth() &&
244 "ConstantRange types don't agree!");
246 // Handle common cases.
247 if ( isEmptySet() || CR
.isFullSet()) return *this;
248 if (CR
.isEmptySet() || isFullSet()) return CR
;
250 if (!isWrappedSet() && CR
.isWrappedSet())
251 return CR
.intersectWith(*this);
253 if (!isWrappedSet() && !CR
.isWrappedSet()) {
254 if (Lower
.ult(CR
.Lower
)) {
255 if (Upper
.ule(CR
.Lower
))
256 return ConstantRange(getBitWidth(), false);
258 if (Upper
.ult(CR
.Upper
))
259 return ConstantRange(CR
.Lower
, Upper
);
263 if (Upper
.ult(CR
.Upper
))
266 if (Lower
.ult(CR
.Upper
))
267 return ConstantRange(Lower
, CR
.Upper
);
269 return ConstantRange(getBitWidth(), false);
273 if (isWrappedSet() && !CR
.isWrappedSet()) {
274 if (CR
.Lower
.ult(Upper
)) {
275 if (CR
.Upper
.ult(Upper
))
278 if (CR
.Upper
.ult(Lower
))
279 return ConstantRange(CR
.Lower
, Upper
);
281 if (getSetSize().ult(CR
.getSetSize()))
285 } else if (CR
.Lower
.ult(Lower
)) {
286 if (CR
.Upper
.ule(Lower
))
287 return ConstantRange(getBitWidth(), false);
289 return ConstantRange(Lower
, CR
.Upper
);
294 if (CR
.Upper
.ult(Upper
)) {
295 if (CR
.Lower
.ult(Upper
)) {
296 if (getSetSize().ult(CR
.getSetSize()))
302 if (CR
.Lower
.ult(Lower
))
303 return ConstantRange(Lower
, CR
.Upper
);
306 } else if (CR
.Upper
.ult(Lower
)) {
307 if (CR
.Lower
.ult(Lower
))
310 return ConstantRange(CR
.Lower
, Upper
);
312 if (getSetSize().ult(CR
.getSetSize()))
319 /// unionWith - Return the range that results from the union of this range with
320 /// another range. The resultant range is guaranteed to include the elements of
321 /// both sets, but may contain more. For example, [3, 9) union [12,15) is
322 /// [3, 15), which includes 9, 10, and 11, which were not included in either
325 ConstantRange
ConstantRange::unionWith(const ConstantRange
&CR
) const {
326 assert(getBitWidth() == CR
.getBitWidth() &&
327 "ConstantRange types don't agree!");
329 if ( isFullSet() || CR
.isEmptySet()) return *this;
330 if (CR
.isFullSet() || isEmptySet()) return CR
;
332 if (!isWrappedSet() && CR
.isWrappedSet()) return CR
.unionWith(*this);
334 if (!isWrappedSet() && !CR
.isWrappedSet()) {
335 if (CR
.Upper
.ult(Lower
) || Upper
.ult(CR
.Lower
)) {
336 // If the two ranges are disjoint, find the smaller gap and bridge it.
337 APInt d1
= CR
.Lower
- Upper
, d2
= Lower
- CR
.Upper
;
339 return ConstantRange(Lower
, CR
.Upper
);
341 return ConstantRange(CR
.Lower
, Upper
);
344 APInt L
= Lower
, U
= Upper
;
347 if ((CR
.Upper
- 1).ugt(U
- 1))
350 if (L
== 0 && U
== 0)
351 return ConstantRange(getBitWidth());
353 return ConstantRange(L
, U
);
356 if (!CR
.isWrappedSet()) {
357 // ------U L----- and ------U L----- : this
359 if (CR
.Upper
.ule(Upper
) || CR
.Lower
.uge(Lower
))
362 // ------U L----- : this
364 if (CR
.Lower
.ule(Upper
) && Lower
.ule(CR
.Upper
))
365 return ConstantRange(getBitWidth());
367 // ----U L---- : this
370 if (Upper
.ule(CR
.Lower
) && CR
.Upper
.ule(Lower
)) {
371 APInt d1
= CR
.Lower
- Upper
, d2
= Lower
- CR
.Upper
;
373 return ConstantRange(Lower
, CR
.Upper
);
375 return ConstantRange(CR
.Lower
, Upper
);
378 // ----U L----- : this
380 if (Upper
.ult(CR
.Lower
) && Lower
.ult(CR
.Upper
))
381 return ConstantRange(CR
.Lower
, Upper
);
383 // ------U L---- : this
385 if (CR
.Lower
.ult(Upper
) && CR
.Upper
.ult(Lower
))
386 return ConstantRange(Lower
, CR
.Upper
);
389 assert(isWrappedSet() && CR
.isWrappedSet() &&
390 "ConstantRange::unionWith missed wrapped union unwrapped case");
392 // ------U L---- and ------U L---- : this
393 // -U L----------- and ------------U L : CR
394 if (CR
.Lower
.ule(Upper
) || Lower
.ule(CR
.Upper
))
395 return ConstantRange(getBitWidth());
397 APInt L
= Lower
, U
= Upper
;
403 return ConstantRange(L
, U
);
406 /// zeroExtend - Return a new range in the specified integer type, which must
407 /// be strictly larger than the current type. The returned range will
408 /// correspond to the possible range of values as if the source range had been
410 ConstantRange
ConstantRange::zeroExtend(uint32_t DstTySize
) const {
411 unsigned SrcTySize
= getBitWidth();
412 assert(SrcTySize
< DstTySize
&& "Not a value extension");
414 // Change a source full set into [0, 1 << 8*numbytes)
415 return ConstantRange(APInt(DstTySize
,0), APInt(DstTySize
,1).shl(SrcTySize
));
417 APInt L
= Lower
; L
.zext(DstTySize
);
418 APInt U
= Upper
; U
.zext(DstTySize
);
419 return ConstantRange(L
, U
);
422 /// signExtend - Return a new range in the specified integer type, which must
423 /// be strictly larger than the current type. The returned range will
424 /// correspond to the possible range of values as if the source range had been
426 ConstantRange
ConstantRange::signExtend(uint32_t DstTySize
) const {
427 unsigned SrcTySize
= getBitWidth();
428 assert(SrcTySize
< DstTySize
&& "Not a value extension");
430 return ConstantRange(APInt::getHighBitsSet(DstTySize
,DstTySize
-SrcTySize
+1),
431 APInt::getLowBitsSet(DstTySize
, SrcTySize
-1) + 1);
434 APInt L
= Lower
; L
.sext(DstTySize
);
435 APInt U
= Upper
; U
.sext(DstTySize
);
436 return ConstantRange(L
, U
);
439 /// truncate - Return a new range in the specified integer type, which must be
440 /// strictly smaller than the current type. The returned range will
441 /// correspond to the possible range of values as if the source range had been
442 /// truncated to the specified type.
443 ConstantRange
ConstantRange::truncate(uint32_t DstTySize
) const {
444 unsigned SrcTySize
= getBitWidth();
445 assert(SrcTySize
> DstTySize
&& "Not a value truncation");
446 APInt
Size(APInt::getLowBitsSet(SrcTySize
, DstTySize
));
447 if (isFullSet() || getSetSize().ugt(Size
))
448 return ConstantRange(DstTySize
, /*isFullSet=*/true);
450 APInt L
= Lower
; L
.trunc(DstTySize
);
451 APInt U
= Upper
; U
.trunc(DstTySize
);
452 return ConstantRange(L
, U
);
455 /// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
456 /// value is zero extended, truncated, or left alone to make it that width.
457 ConstantRange
ConstantRange::zextOrTrunc(uint32_t DstTySize
) const {
458 unsigned SrcTySize
= getBitWidth();
459 if (SrcTySize
> DstTySize
)
460 return truncate(DstTySize
);
461 else if (SrcTySize
< DstTySize
)
462 return zeroExtend(DstTySize
);
467 /// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
468 /// value is sign extended, truncated, or left alone to make it that width.
469 ConstantRange
ConstantRange::sextOrTrunc(uint32_t DstTySize
) const {
470 unsigned SrcTySize
= getBitWidth();
471 if (SrcTySize
> DstTySize
)
472 return truncate(DstTySize
);
473 else if (SrcTySize
< DstTySize
)
474 return signExtend(DstTySize
);
480 ConstantRange::add(const ConstantRange
&Other
) const {
481 if (isEmptySet() || Other
.isEmptySet())
482 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
483 if (isFullSet() || Other
.isFullSet())
484 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
486 APInt Spread_X
= getSetSize(), Spread_Y
= Other
.getSetSize();
487 APInt NewLower
= getLower() + Other
.getLower();
488 APInt NewUpper
= getUpper() + Other
.getUpper() - 1;
489 if (NewLower
== NewUpper
)
490 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
492 ConstantRange X
= ConstantRange(NewLower
, NewUpper
);
493 if (X
.getSetSize().ult(Spread_X
) || X
.getSetSize().ult(Spread_Y
))
494 // We've wrapped, therefore, full set.
495 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
501 ConstantRange::sub(const ConstantRange
&Other
) const {
502 if (isEmptySet() || Other
.isEmptySet())
503 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
504 if (isFullSet() || Other
.isFullSet())
505 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
507 APInt Spread_X
= getSetSize(), Spread_Y
= Other
.getSetSize();
508 APInt NewLower
= getLower() - Other
.getLower();
509 APInt NewUpper
= getUpper() - Other
.getUpper() + 1;
510 if (NewLower
== NewUpper
)
511 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
513 ConstantRange X
= ConstantRange(NewLower
, NewUpper
);
514 if (X
.getSetSize().ult(Spread_X
) || X
.getSetSize().ult(Spread_Y
))
515 // We've wrapped, therefore, full set.
516 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
522 ConstantRange::multiply(const ConstantRange
&Other
) const {
523 // TODO: If either operand is a single element and the multiply is known to
524 // be non-wrapping, round the result min and max value to the appropriate
525 // multiple of that element. If wrapping is possible, at least adjust the
526 // range according to the greatest power-of-two factor of the single element.
528 if (isEmptySet() || Other
.isEmptySet())
529 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
530 if (isFullSet() || Other
.isFullSet())
531 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
533 APInt this_min
= getUnsignedMin().zext(getBitWidth() * 2);
534 APInt this_max
= getUnsignedMax().zext(getBitWidth() * 2);
535 APInt Other_min
= Other
.getUnsignedMin().zext(getBitWidth() * 2);
536 APInt Other_max
= Other
.getUnsignedMax().zext(getBitWidth() * 2);
538 ConstantRange Result_zext
= ConstantRange(this_min
* Other_min
,
539 this_max
* Other_max
+ 1);
540 return Result_zext
.truncate(getBitWidth());
544 ConstantRange::smax(const ConstantRange
&Other
) const {
545 // X smax Y is: range(smax(X_smin, Y_smin),
546 // smax(X_smax, Y_smax))
547 if (isEmptySet() || Other
.isEmptySet())
548 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
549 APInt NewL
= APIntOps::smax(getSignedMin(), Other
.getSignedMin());
550 APInt NewU
= APIntOps::smax(getSignedMax(), Other
.getSignedMax()) + 1;
552 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
553 return ConstantRange(NewL
, NewU
);
557 ConstantRange::umax(const ConstantRange
&Other
) const {
558 // X umax Y is: range(umax(X_umin, Y_umin),
559 // umax(X_umax, Y_umax))
560 if (isEmptySet() || Other
.isEmptySet())
561 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
562 APInt NewL
= APIntOps::umax(getUnsignedMin(), Other
.getUnsignedMin());
563 APInt NewU
= APIntOps::umax(getUnsignedMax(), Other
.getUnsignedMax()) + 1;
565 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
566 return ConstantRange(NewL
, NewU
);
570 ConstantRange::udiv(const ConstantRange
&RHS
) const {
571 if (isEmptySet() || RHS
.isEmptySet() || RHS
.getUnsignedMax() == 0)
572 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
574 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
576 APInt Lower
= getUnsignedMin().udiv(RHS
.getUnsignedMax());
578 APInt RHS_umin
= RHS
.getUnsignedMin();
580 // We want the lowest value in RHS excluding zero. Usually that would be 1
581 // except for a range in the form of [X, 1) in which case it would be X.
582 if (RHS
.getUpper() == 1)
583 RHS_umin
= RHS
.getLower();
585 RHS_umin
= APInt(getBitWidth(), 1);
588 APInt Upper
= getUnsignedMax().udiv(RHS_umin
) + 1;
590 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
593 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
595 return ConstantRange(Lower
, Upper
);
599 ConstantRange::shl(const ConstantRange
&Other
) const {
600 if (isEmptySet() || Other
.isEmptySet())
601 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
603 APInt min
= getUnsignedMin().shl(Other
.getUnsignedMin());
604 APInt max
= getUnsignedMax().shl(Other
.getUnsignedMax());
606 // there's no overflow!
607 APInt
Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
608 if (Zeros
.ugt(Other
.getUnsignedMax()))
609 return ConstantRange(min
, max
+ 1);
611 // FIXME: implement the other tricky cases
612 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
616 ConstantRange::lshr(const ConstantRange
&Other
) const {
617 if (isEmptySet() || Other
.isEmptySet())
618 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
620 APInt max
= getUnsignedMax().lshr(Other
.getUnsignedMin());
621 APInt min
= getUnsignedMin().lshr(Other
.getUnsignedMax());
623 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
625 return ConstantRange(min
, max
+ 1);
628 ConstantRange
ConstantRange::inverse() const {
630 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
631 } else if (isEmptySet()) {
632 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
634 return ConstantRange(Upper
, Lower
);
637 /// print - Print out the bounds to a stream...
639 void ConstantRange::print(raw_ostream
&OS
) const {
642 else if (isEmptySet())
645 OS
<< "[" << Lower
<< "," << Upper
<< ")";
648 /// dump - Allow printing from a debugger easily...
650 void ConstantRange::dump() const {