1 //===-- ConstantRange.cpp - ConstantRange implementation ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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/Constants.h"
26 #include "llvm/Instruction.h"
27 #include "llvm/Instructions.h"
28 #include "llvm/Type.h"
29 #include "llvm/DerivedTypes.h"
30 #include "llvm/Support/Streams.h"
34 /// Initialize a full (the default) or empty set for the specified type.
36 ConstantRange::ConstantRange(const Type *Ty, bool Full) :
37 Lower(cast<IntegerType>(Ty)->getBitWidth(), 0),
38 Upper(cast<IntegerType>(Ty)->getBitWidth(), 0) {
39 uint32_t BitWidth = cast<IntegerType>(Ty)->getBitWidth();
41 Lower = Upper = APInt::getMaxValue(BitWidth);
43 Lower = Upper = APInt::getMinValue(BitWidth);
46 /// Initialize a range to hold the single specified value.
48 ConstantRange::ConstantRange(const APInt & V) : Lower(V), Upper(V + 1) { }
50 ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
52 assert(L.getBitWidth() == U.getBitWidth() &&
53 "ConstantRange with unequal bit widths");
54 uint32_t BitWidth = L.getBitWidth();
55 assert((L != U || (L == APInt::getMaxValue(BitWidth) ||
56 L == APInt::getMinValue(BitWidth))) &&
57 "Lower == Upper, but they aren't min or max value!");
60 /// Initialize a set of values that all satisfy the condition with C.
62 ConstantRange::ConstantRange(unsigned short ICmpOpcode, const APInt &C)
63 : Lower(C.getBitWidth(), 0), Upper(C.getBitWidth(), 0) {
64 uint32_t BitWidth = C.getBitWidth();
66 default: assert(0 && "Invalid ICmp opcode to ConstantRange ctor!");
67 case ICmpInst::ICMP_EQ: Lower = C; Upper = C + 1; return;
68 case ICmpInst::ICMP_NE: Upper = C; Lower = C + 1; return;
69 case ICmpInst::ICMP_ULT:
70 Lower = APInt::getMinValue(BitWidth);
73 case ICmpInst::ICMP_SLT:
74 Lower = APInt::getSignedMinValue(BitWidth);
77 case ICmpInst::ICMP_UGT:
79 Upper = APInt::getMinValue(BitWidth); // Min = Next(Max)
81 case ICmpInst::ICMP_SGT:
83 Upper = APInt::getSignedMinValue(BitWidth); // Min = Next(Max)
85 case ICmpInst::ICMP_ULE:
86 Lower = APInt::getMinValue(BitWidth);
89 case ICmpInst::ICMP_SLE:
90 Lower = APInt::getSignedMinValue(BitWidth);
93 case ICmpInst::ICMP_UGE:
95 Upper = APInt::getMinValue(BitWidth); // Min = Next(Max)
97 case ICmpInst::ICMP_SGE:
99 Upper = APInt::getSignedMinValue(BitWidth); // Min = Next(Max)
104 /// getType - Return the LLVM data type of this range.
106 const Type *ConstantRange::getType() const {
107 return IntegerType::get(Lower.getBitWidth());
110 ConstantInt *ConstantRange::getLower() const {
111 return ConstantInt::get(getType(), Lower);
114 ConstantInt *ConstantRange::getUpper() const {
115 return ConstantInt::get(getType(), Upper);
118 /// isFullSet - Return true if this set contains all of the elements possible
119 /// for this data-type
120 bool ConstantRange::isFullSet() const {
121 return Lower == Upper && Lower == APInt::getMaxValue(Lower.getBitWidth());
124 /// isEmptySet - Return true if this set contains no members.
126 bool ConstantRange::isEmptySet() const {
127 return Lower == Upper && Lower == APInt::getMinValue(Lower.getBitWidth());
130 /// isWrappedSet - Return true if this set wraps around the top of the range,
131 /// for example: [100, 8)
133 bool ConstantRange::isWrappedSet(bool isSigned) const {
135 return Lower.sgt(Upper);
136 return Lower.ugt(Upper);
139 /// getSingleElement - If this set contains a single element, return it,
140 /// otherwise return null.
141 ConstantInt *ConstantRange::getSingleElement() const {
142 if (Upper == Lower + 1) // Is it a single element range?
143 return ConstantInt::get(getType(), Lower);
147 /// getSetSize - Return the number of elements in this set.
149 APInt ConstantRange::getSetSize() const {
151 return APInt(Lower.getBitWidth(), 0);
152 if (getType() == Type::Int1Ty) {
153 if (Lower != Upper) // One of T or F in the set...
154 return APInt(Lower.getBitWidth(), 1);
155 return APInt(Lower.getBitWidth(), 2); // Must be full set...
158 // Simply subtract the bounds...
159 return Upper - Lower;
162 /// contains - Return true if the specified value is in the set.
164 bool ConstantRange::contains(ConstantInt *Val, bool isSigned) const {
165 if (Lower == Upper) {
171 const APInt &V = Val->getValue();
172 if (!isWrappedSet(isSigned))
174 return Lower.sle(V) && V.slt(Upper);
176 return Lower.ule(V) && V.ult(Upper);
178 return Lower.sle(V) || V.slt(Upper);
180 return Lower.ule(V) || V.ult(Upper);
183 /// subtract - Subtract the specified constant from the endpoints of this
185 ConstantRange ConstantRange::subtract(ConstantInt *CI) const {
186 assert(CI->getType() == getType() &&
187 "Cannot subtract from different type range or non-integer!");
188 // If the set is empty or full, don't modify the endpoints.
192 const APInt &Val = CI->getValue();
193 return ConstantRange(Lower - Val, Upper - Val);
197 // intersect1Wrapped - This helper function is used to intersect two ranges when
198 // it is known that LHS is wrapped and RHS isn't.
201 ConstantRange::intersect1Wrapped(const ConstantRange &LHS,
202 const ConstantRange &RHS, bool isSigned) {
203 assert(LHS.isWrappedSet(isSigned) && !RHS.isWrappedSet(isSigned));
205 // Check to see if we overlap on the Left side of RHS...
207 bool LT = (isSigned ? RHS.Lower.slt(LHS.Upper) : RHS.Lower.ult(LHS.Upper));
208 bool GT = (isSigned ? RHS.Upper.sgt(LHS.Lower) : RHS.Upper.ugt(LHS.Lower));
210 // We do overlap on the left side of RHS, see if we overlap on the right of
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
230 return ConstantRange(LHS.Lower, RHS.Upper);
233 return ConstantRange(LHS.getType(), 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,
242 bool isSigned) const {
243 assert(getType() == CR.getType() && "ConstantRange types don't agree!");
244 // Handle common special cases
245 if (isEmptySet() || CR.isFullSet())
247 if (isFullSet() || CR.isEmptySet())
250 if (!isWrappedSet(isSigned)) {
251 if (!CR.isWrappedSet(isSigned)) {
252 using namespace APIntOps;
253 APInt L = isSigned ? smax(Lower, CR.Lower) : umax(Lower, CR.Lower);
254 APInt U = isSigned ? smin(Upper, CR.Upper) : umin(Upper, CR.Upper);
256 if (isSigned ? L.slt(U) : L.ult(U)) // If range isn't empty...
257 return ConstantRange(L, U);
259 return ConstantRange(getType(), false); // Otherwise, return empty set
261 return intersect1Wrapped(CR, *this, isSigned);
262 } else { // We know "this" is wrapped...
263 if (!CR.isWrappedSet(isSigned))
264 return intersect1Wrapped(*this, CR, isSigned);
266 // Both ranges are wrapped...
267 using namespace APIntOps;
268 APInt L = isSigned ? smax(Lower, CR.Lower) : umax(Lower, CR.Lower);
269 APInt U = isSigned ? smin(Upper, CR.Upper) : umin(Upper, CR.Upper);
270 return ConstantRange(L, U);
276 /// unionWith - Return the range that results from the union of this range with
277 /// another range. The resultant range is guaranteed to include the elements of
278 /// both sets, but may contain more. For example, [3, 9) union [12,15) is [3,
279 /// 15), which includes 9, 10, and 11, which were not included in either set
282 ConstantRange ConstantRange::unionWith(const ConstantRange &CR,
283 bool isSigned) const {
284 assert(getType() == CR.getType() && "ConstantRange types don't agree!");
286 assert(0 && "Range union not implemented yet!");
291 /// zeroExtend - Return a new range in the specified integer type, which must
292 /// be strictly larger than the current type. The returned range will
293 /// correspond to the possible range of values as if the source range had been
295 ConstantRange ConstantRange::zeroExtend(const Type *Ty) const {
296 unsigned SrcTySize = Lower.getBitWidth();
297 unsigned DstTySize = Ty->getPrimitiveSizeInBits();
298 assert(SrcTySize < DstTySize && "Not a value extension");
300 // Change a source full set into [0, 1 << 8*numbytes)
301 return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize));
303 APInt L = Lower; L.zext(DstTySize);
304 APInt U = Upper; U.zext(DstTySize);
305 return ConstantRange(L, U);
308 /// truncate - Return a new range in the specified integer type, which must be
309 /// strictly smaller than the current type. The returned range will
310 /// correspond to the possible range of values as if the source range had been
311 /// truncated to the specified type.
312 ConstantRange ConstantRange::truncate(const Type *Ty) const {
313 unsigned SrcTySize = Lower.getBitWidth();
314 unsigned DstTySize = Ty->getPrimitiveSizeInBits();
315 assert(SrcTySize > DstTySize && "Not a value truncation");
316 APInt Size = APInt::getMaxValue(DstTySize).zext(SrcTySize);
317 if (isFullSet() || getSetSize().ugt(Size))
318 return ConstantRange(getType());
320 APInt L = Lower; L.trunc(DstTySize);
321 APInt U = Upper; U.trunc(DstTySize);
322 return ConstantRange(L, U);
325 /// print - Print out the bounds to a stream...
327 void ConstantRange::print(std::ostream &OS) const {
328 OS << "[" << Lower.toStringSigned(10) << ","
329 << Upper.toStringSigned(10) << " )";
332 /// dump - Allow printing from a debugger easily...
334 void ConstantRange::dump() const {