blob: a3f2297596374b5f6a212b986aad12f9a2ae9624 [file] [log] [blame]
Chris Lattner645e00d2002-09-01 23:53:36 +00001//===-- ConstantRange.cpp - ConstantRange implementation ------------------===//
Misha Brukmanfd939082005-04-21 23:48:37 +00002//
John Criswellb576c942003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukmanfd939082005-04-21 23:48:37 +00007//
John Criswellb576c942003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattner645e00d2002-09-01 23:53:36 +00009//
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):
16//
17// [F, F) = {} = Empty set
18// [T, F) = {T}
19// [F, T) = {F}
20// [T, T) = {F, T} = Full set
21//
22//===----------------------------------------------------------------------===//
23
Frits van Bommela09d5142011-07-27 15:20:06 +000024#include "llvm/InstrTypes.h"
Chris Lattner645e00d2002-09-01 23:53:36 +000025#include "llvm/Support/ConstantRange.h"
David Greene7fd5fb42010-01-05 01:28:32 +000026#include "llvm/Support/Debug.h"
Chris Lattner944fac72008-08-23 22:23:09 +000027#include "llvm/Support/raw_ostream.h"
Chris Lattner2cdd21c2003-12-14 21:35:53 +000028using namespace llvm;
Brian Gaeked0fde302003-11-11 22:41:34 +000029
Chris Lattner645e00d2002-09-01 23:53:36 +000030/// Initialize a full (the default) or empty set for the specified type.
31///
Dan Gohman38b06442009-07-09 23:16:10 +000032ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) {
Chris Lattner645e00d2002-09-01 23:53:36 +000033 if (Full)
Reid Spencer663e7112007-02-28 17:36:23 +000034 Lower = Upper = APInt::getMaxValue(BitWidth);
Chris Lattner645e00d2002-09-01 23:53:36 +000035 else
Reid Spencer663e7112007-02-28 17:36:23 +000036 Lower = Upper = APInt::getMinValue(BitWidth);
Chris Lattner645e00d2002-09-01 23:53:36 +000037}
38
Chris Lattnerfc33d302004-03-30 00:20:08 +000039/// Initialize a range to hold the single specified value.
40///
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +000041ConstantRange::ConstantRange(const APInt &V) : Lower(V), Upper(V + 1) {}
Chris Lattner645e00d2002-09-01 23:53:36 +000042
Dan Gohman38b06442009-07-09 23:16:10 +000043ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
44 Lower(L), Upper(U) {
45 assert(L.getBitWidth() == U.getBitWidth() &&
46 "ConstantRange with unequal bit widths");
Zhou Shengc125c002007-04-26 16:42:07 +000047 assert((L != U || (L.isMaxValue() || L.isMinValue())) &&
Reid Spencer663e7112007-02-28 17:36:23 +000048 "Lower == Upper, but they aren't min or max value!");
49}
50
Nick Lewyckybf8c7f02009-07-11 06:15:39 +000051ConstantRange ConstantRange::makeICmpRegion(unsigned Pred,
52 const ConstantRange &CR) {
Nick Lewyckyf2d7b7c2010-09-28 18:18:36 +000053 if (CR.isEmptySet())
54 return CR;
55
Nick Lewyckybf8c7f02009-07-11 06:15:39 +000056 uint32_t W = CR.getBitWidth();
57 switch (Pred) {
Craig Topper85814382012-02-07 05:05:23 +000058 default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()");
Frits van Bommela09d5142011-07-27 15:20:06 +000059 case CmpInst::ICMP_EQ:
Nick Lewyckyf067a232009-07-11 17:04:01 +000060 return CR;
Frits van Bommela09d5142011-07-27 15:20:06 +000061 case CmpInst::ICMP_NE:
Nick Lewyckybf8c7f02009-07-11 06:15:39 +000062 if (CR.isSingleElement())
63 return ConstantRange(CR.getUpper(), CR.getLower());
64 return ConstantRange(W);
Frits van Bommela09d5142011-07-27 15:20:06 +000065 case CmpInst::ICMP_ULT: {
Nick Lewyckyf2d7b7c2010-09-28 18:18:36 +000066 APInt UMax(CR.getUnsignedMax());
67 if (UMax.isMinValue())
68 return ConstantRange(W, /* empty */ false);
69 return ConstantRange(APInt::getMinValue(W), UMax);
70 }
Frits van Bommela09d5142011-07-27 15:20:06 +000071 case CmpInst::ICMP_SLT: {
Nick Lewyckyf2d7b7c2010-09-28 18:18:36 +000072 APInt SMax(CR.getSignedMax());
73 if (SMax.isMinSignedValue())
74 return ConstantRange(W, /* empty */ false);
75 return ConstantRange(APInt::getSignedMinValue(W), SMax);
76 }
Frits van Bommela09d5142011-07-27 15:20:06 +000077 case CmpInst::ICMP_ULE: {
Nick Lewyckybf8c7f02009-07-11 06:15:39 +000078 APInt UMax(CR.getUnsignedMax());
79 if (UMax.isMaxValue())
80 return ConstantRange(W);
81 return ConstantRange(APInt::getMinValue(W), UMax + 1);
82 }
Frits van Bommela09d5142011-07-27 15:20:06 +000083 case CmpInst::ICMP_SLE: {
Nick Lewyckybf8c7f02009-07-11 06:15:39 +000084 APInt SMax(CR.getSignedMax());
Nick Lewyckyf2d7b7c2010-09-28 18:18:36 +000085 if (SMax.isMaxSignedValue())
Nick Lewyckybf8c7f02009-07-11 06:15:39 +000086 return ConstantRange(W);
87 return ConstantRange(APInt::getSignedMinValue(W), SMax + 1);
88 }
Frits van Bommela09d5142011-07-27 15:20:06 +000089 case CmpInst::ICMP_UGT: {
Nick Lewyckyf2d7b7c2010-09-28 18:18:36 +000090 APInt UMin(CR.getUnsignedMin());
91 if (UMin.isMaxValue())
92 return ConstantRange(W, /* empty */ false);
93 return ConstantRange(UMin + 1, APInt::getNullValue(W));
94 }
Frits van Bommela09d5142011-07-27 15:20:06 +000095 case CmpInst::ICMP_SGT: {
Nick Lewyckyf2d7b7c2010-09-28 18:18:36 +000096 APInt SMin(CR.getSignedMin());
97 if (SMin.isMaxSignedValue())
98 return ConstantRange(W, /* empty */ false);
99 return ConstantRange(SMin + 1, APInt::getSignedMinValue(W));
100 }
Frits van Bommela09d5142011-07-27 15:20:06 +0000101 case CmpInst::ICMP_UGE: {
Nick Lewyckybf8c7f02009-07-11 06:15:39 +0000102 APInt UMin(CR.getUnsignedMin());
103 if (UMin.isMinValue())
104 return ConstantRange(W);
105 return ConstantRange(UMin, APInt::getNullValue(W));
106 }
Frits van Bommela09d5142011-07-27 15:20:06 +0000107 case CmpInst::ICMP_SGE: {
Nick Lewyckybf8c7f02009-07-11 06:15:39 +0000108 APInt SMin(CR.getSignedMin());
109 if (SMin.isMinSignedValue())
110 return ConstantRange(W);
111 return ConstantRange(SMin, APInt::getSignedMinValue(W));
112 }
113 }
114}
115
Chris Lattner645e00d2002-09-01 23:53:36 +0000116/// isFullSet - Return true if this set contains all of the elements possible
117/// for this data-type
118bool ConstantRange::isFullSet() const {
Zhou Shengc125c002007-04-26 16:42:07 +0000119 return Lower == Upper && Lower.isMaxValue();
Chris Lattner645e00d2002-09-01 23:53:36 +0000120}
Misha Brukmanfd939082005-04-21 23:48:37 +0000121
Chris Lattner645e00d2002-09-01 23:53:36 +0000122/// isEmptySet - Return true if this set contains no members.
123///
124bool ConstantRange::isEmptySet() const {
Zhou Shengc125c002007-04-26 16:42:07 +0000125 return Lower == Upper && Lower.isMinValue();
Chris Lattner645e00d2002-09-01 23:53:36 +0000126}
127
128/// isWrappedSet - Return true if this set wraps around the top of the range,
129/// for example: [100, 8)
130///
Reid Spencera6e8a952007-03-01 07:54:15 +0000131bool ConstantRange::isWrappedSet() const {
Reid Spencer663e7112007-02-28 17:36:23 +0000132 return Lower.ugt(Upper);
Chris Lattner645e00d2002-09-01 23:53:36 +0000133}
134
Nick Lewycky32cda112010-09-06 23:52:49 +0000135/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of
136/// its bitwidth, for example: i8 [120, 140).
137///
138bool ConstantRange::isSignWrappedSet() const {
139 return contains(APInt::getSignedMaxValue(getBitWidth())) &&
140 contains(APInt::getSignedMinValue(getBitWidth()));
141}
142
Chris Lattner645e00d2002-09-01 23:53:36 +0000143/// getSetSize - Return the number of elements in this set.
144///
Reid Spencer663e7112007-02-28 17:36:23 +0000145APInt ConstantRange::getSetSize() const {
Nuno Lopes367308f2012-07-16 18:08:12 +0000146 if (isEmptySet())
147 return APInt(getBitWidth()+1, 0);
148
Nuno Lopes5d2fada2012-07-17 15:43:59 +0000149 if (isFullSet()) {
150 APInt Size(getBitWidth()+1, 0);
151 Size.setBit(getBitWidth());
152 return Size;
Chris Lattner645e00d2002-09-01 23:53:36 +0000153 }
Misha Brukmanfd939082005-04-21 23:48:37 +0000154
Nuno Lopes5d2fada2012-07-17 15:43:59 +0000155 // This is also correct for wrapped sets.
Nuno Lopes367308f2012-07-16 18:08:12 +0000156 return (Upper - Lower).zext(getBitWidth()+1);
Chris Lattner645e00d2002-09-01 23:53:36 +0000157}
158
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000159/// getUnsignedMax - Return the largest unsigned value contained in the
160/// ConstantRange.
161///
162APInt ConstantRange::getUnsignedMax() const {
163 if (isFullSet() || isWrappedSet())
164 return APInt::getMaxValue(getBitWidth());
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000165 return getUpper() - 1;
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000166}
167
168/// getUnsignedMin - Return the smallest unsigned value contained in the
169/// ConstantRange.
170///
171APInt ConstantRange::getUnsignedMin() const {
172 if (isFullSet() || (isWrappedSet() && getUpper() != 0))
173 return APInt::getMinValue(getBitWidth());
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000174 return getLower();
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000175}
176
177/// getSignedMax - Return the largest signed value contained in the
178/// ConstantRange.
179///
180APInt ConstantRange::getSignedMax() const {
Zhou Shengdaacf222007-04-13 05:57:32 +0000181 APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000182 if (!isWrappedSet()) {
Nick Lewyckyae5eb7a2007-06-09 04:20:33 +0000183 if (getLower().sle(getUpper() - 1))
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000184 return getUpper() - 1;
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000185 return SignedMax;
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000186 }
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000187 if (getLower().isNegative() == getUpper().isNegative())
188 return SignedMax;
189 return getUpper() - 1;
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000190}
191
192/// getSignedMin - Return the smallest signed value contained in the
193/// ConstantRange.
194///
195APInt ConstantRange::getSignedMin() const {
Zhou Shengdaacf222007-04-13 05:57:32 +0000196 APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000197 if (!isWrappedSet()) {
Nick Lewyckyae5eb7a2007-06-09 04:20:33 +0000198 if (getLower().sle(getUpper() - 1))
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000199 return getLower();
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000200 return SignedMin;
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000201 }
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000202 if ((getUpper() - 1).slt(getLower())) {
203 if (getUpper() != SignedMin)
204 return SignedMin;
205 }
206 return getLower();
Nick Lewycky3400e6a2007-03-10 15:54:12 +0000207}
208
Chris Lattnerfc33d302004-03-30 00:20:08 +0000209/// contains - Return true if the specified value is in the set.
210///
Reid Spencera6e8a952007-03-01 07:54:15 +0000211bool ConstantRange::contains(const APInt &V) const {
212 if (Lower == Upper)
213 return isFullSet();
Chris Lattner645e00d2002-09-01 23:53:36 +0000214
Reid Spencera6e8a952007-03-01 07:54:15 +0000215 if (!isWrappedSet())
216 return Lower.ule(V) && V.ult(Upper);
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000217 return Lower.ule(V) || V.ult(Upper);
Chris Lattnerfc33d302004-03-30 00:20:08 +0000218}
219
Nick Lewyckybf8c7f02009-07-11 06:15:39 +0000220/// contains - Return true if the argument is a subset of this range.
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000221/// Two equal sets contain each other. The empty set contained by all other
222/// sets.
Nick Lewyckybf8c7f02009-07-11 06:15:39 +0000223///
224bool ConstantRange::contains(const ConstantRange &Other) const {
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000225 if (isFullSet() || Other.isEmptySet()) return true;
226 if (isEmptySet() || Other.isFullSet()) return false;
Nick Lewyckybf8c7f02009-07-11 06:15:39 +0000227
228 if (!isWrappedSet()) {
229 if (Other.isWrappedSet())
230 return false;
231
232 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
233 }
234
235 if (!Other.isWrappedSet())
236 return Other.getUpper().ule(Upper) ||
237 Lower.ule(Other.getLower());
238
239 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
240}
241
Chris Lattnerfc33d302004-03-30 00:20:08 +0000242/// subtract - Subtract the specified constant from the endpoints of this
243/// constant range.
Reid Spencer581b0d42007-02-28 19:57:34 +0000244ConstantRange ConstantRange::subtract(const APInt &Val) const {
Reid Spencerbb626a62007-02-28 22:02:48 +0000245 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
Chris Lattnerfc33d302004-03-30 00:20:08 +0000246 // If the set is empty or full, don't modify the endpoints.
Reid Spencer663e7112007-02-28 17:36:23 +0000247 if (Lower == Upper)
248 return *this;
Reid Spencer663e7112007-02-28 17:36:23 +0000249 return ConstantRange(Lower - Val, Upper - Val);
Chris Lattnerfc33d302004-03-30 00:20:08 +0000250}
Chris Lattner645e00d2002-09-01 23:53:36 +0000251
Nuno Lopes62d7afa2012-06-28 16:10:13 +0000252/// \brief Subtract the specified range from this range (aka relative complement
253/// of the sets).
254ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
255 return intersectWith(CR.inverse());
256}
257
Nick Lewycky3e051642007-02-11 00:58:49 +0000258/// intersectWith - Return the range that results from the intersection of this
Nick Lewycky3a4a8842009-07-18 06:34:42 +0000259/// range with another range. The resultant range is guaranteed to include all
260/// elements contained in both input ranges, and to have the smallest possible
261/// set size that does so. Because there may be two intersections with the
262/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
Reid Spencera6e8a952007-03-01 07:54:15 +0000263ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
Reid Spencerbb626a62007-02-28 22:02:48 +0000264 assert(getBitWidth() == CR.getBitWidth() &&
265 "ConstantRange types don't agree!");
Nick Lewycky377b1192007-07-14 02:51:34 +0000266
267 // Handle common cases.
268 if ( isEmptySet() || CR.isFullSet()) return *this;
269 if (CR.isEmptySet() || isFullSet()) return CR;
270
271 if (!isWrappedSet() && CR.isWrappedSet())
Nick Lewycky3a4a8842009-07-18 06:34:42 +0000272 return CR.intersectWith(*this);
Nick Lewycky377b1192007-07-14 02:51:34 +0000273
274 if (!isWrappedSet() && !CR.isWrappedSet()) {
275 if (Lower.ult(CR.Lower)) {
276 if (Upper.ule(CR.Lower))
277 return ConstantRange(getBitWidth(), false);
278
279 if (Upper.ult(CR.Upper))
280 return ConstantRange(CR.Lower, Upper);
281
282 return CR;
Nick Lewycky377b1192007-07-14 02:51:34 +0000283 }
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000284 if (Upper.ult(CR.Upper))
285 return *this;
286
287 if (Lower.ult(CR.Upper))
288 return ConstantRange(Lower, CR.Upper);
289
290 return ConstantRange(getBitWidth(), false);
Nick Lewycky377b1192007-07-14 02:51:34 +0000291 }
292
293 if (isWrappedSet() && !CR.isWrappedSet()) {
294 if (CR.Lower.ult(Upper)) {
295 if (CR.Upper.ult(Upper))
296 return CR;
297
Nuno Lopesfbb7a732012-05-18 00:14:36 +0000298 if (CR.Upper.ule(Lower))
Nick Lewycky377b1192007-07-14 02:51:34 +0000299 return ConstantRange(CR.Lower, Upper);
300
301 if (getSetSize().ult(CR.getSetSize()))
302 return *this;
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000303 return CR;
304 }
305 if (CR.Lower.ult(Lower)) {
Nick Lewycky377b1192007-07-14 02:51:34 +0000306 if (CR.Upper.ule(Lower))
307 return ConstantRange(getBitWidth(), false);
308
309 return ConstantRange(Lower, CR.Upper);
310 }
311 return CR;
312 }
313
314 if (CR.Upper.ult(Upper)) {
315 if (CR.Lower.ult(Upper)) {
316 if (getSetSize().ult(CR.getSetSize()))
317 return *this;
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000318 return CR;
Nick Lewycky377b1192007-07-14 02:51:34 +0000319 }
320
321 if (CR.Lower.ult(Lower))
322 return ConstantRange(Lower, CR.Upper);
323
324 return CR;
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000325 }
Nuno Lopes532516a2012-06-28 00:59:33 +0000326 if (CR.Upper.ule(Lower)) {
Nick Lewycky377b1192007-07-14 02:51:34 +0000327 if (CR.Lower.ult(Lower))
328 return *this;
329
330 return ConstantRange(CR.Lower, Upper);
331 }
332 if (getSetSize().ult(CR.getSetSize()))
333 return *this;
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000334 return CR;
Nick Lewycky377b1192007-07-14 02:51:34 +0000335}
336
337
Nick Lewycky3e051642007-02-11 00:58:49 +0000338/// unionWith - Return the range that results from the union of this range with
Chris Lattner645e00d2002-09-01 23:53:36 +0000339/// another range. The resultant range is guaranteed to include the elements of
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000340/// both sets, but may contain more. For example, [3, 9) union [12,15) is
341/// [3, 15), which includes 9, 10, and 11, which were not included in either
342/// set before.
Chris Lattner645e00d2002-09-01 23:53:36 +0000343///
Reid Spencera6e8a952007-03-01 07:54:15 +0000344ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
Reid Spencerbb626a62007-02-28 22:02:48 +0000345 assert(getBitWidth() == CR.getBitWidth() &&
346 "ConstantRange types don't agree!");
Chris Lattner645e00d2002-09-01 23:53:36 +0000347
Nick Lewyckyc6a28fc2007-03-02 03:33:05 +0000348 if ( isFullSet() || CR.isEmptySet()) return *this;
349 if (CR.isFullSet() || isEmptySet()) return CR;
Chris Lattner645e00d2002-09-01 23:53:36 +0000350
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000351 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
352
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000353 if (!isWrappedSet() && !CR.isWrappedSet()) {
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000354 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
355 // If the two ranges are disjoint, find the smaller gap and bridge it.
356 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
357 if (d1.ult(d2))
358 return ConstantRange(Lower, CR.Upper);
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000359 return ConstantRange(CR.Lower, Upper);
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000360 }
361
362 APInt L = Lower, U = Upper;
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000363 if (CR.Lower.ult(L))
364 L = CR.Lower;
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000365 if ((CR.Upper - 1).ugt(U - 1))
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000366 U = CR.Upper;
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000367
368 if (L == 0 && U == 0)
369 return ConstantRange(getBitWidth());
370
371 return ConstantRange(L, U);
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000372 }
373
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000374 if (!CR.isWrappedSet()) {
375 // ------U L----- and ------U L----- : this
376 // L--U L--U : CR
377 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000378 return *this;
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000379
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000380 // ------U L----- : this
381 // L---------U : CR
382 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000383 return ConstantRange(getBitWidth());
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000384
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000385 // ----U L---- : this
386 // L---U : CR
387 // <d1> <d2>
388 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000389 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000390 if (d1.ult(d2))
391 return ConstantRange(Lower, CR.Upper);
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000392 return ConstantRange(CR.Lower, Upper);
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000393 }
394
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000395 // ----U L----- : this
396 // L----U : CR
397 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
398 return ConstantRange(CR.Lower, Upper);
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000399
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000400 // ------U L---- : this
401 // L-----U : CR
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000402 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
403 "ConstantRange::unionWith missed a case with one range wrapped");
404 return ConstantRange(Lower, CR.Upper);
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000405 }
406
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000407 // ------U L---- and ------U L---- : this
408 // -U L----------- and ------------U L : CR
409 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
410 return ConstantRange(getBitWidth());
Nick Lewycky9babd0e2007-04-01 03:47:44 +0000411
Nick Lewycky7e7dc452009-07-19 03:44:35 +0000412 APInt L = Lower, U = Upper;
413 if (CR.Upper.ugt(U))
414 U = CR.Upper;
415 if (CR.Lower.ult(L))
416 L = CR.Lower;
Nick Lewyckyc6a28fc2007-03-02 03:33:05 +0000417
418 return ConstantRange(L, U);
Chris Lattner645e00d2002-09-01 23:53:36 +0000419}
Chris Lattner96f9d722002-09-02 00:18:22 +0000420
Chris Lattnerfc33d302004-03-30 00:20:08 +0000421/// zeroExtend - Return a new range in the specified integer type, which must
422/// be strictly larger than the current type. The returned range will
Reid Spencere4d87aa2006-12-23 06:05:41 +0000423/// correspond to the possible range of values as if the source range had been
Chris Lattnerfc33d302004-03-30 00:20:08 +0000424/// zero extended.
Reid Spencerbb626a62007-02-28 22:02:48 +0000425ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
Nick Lewycky32cda112010-09-06 23:52:49 +0000426 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
427
Reid Spencerbb626a62007-02-28 22:02:48 +0000428 unsigned SrcTySize = getBitWidth();
Reid Spencer663e7112007-02-28 17:36:23 +0000429 assert(SrcTySize < DstTySize && "Not a value extension");
Nick Lewycky32cda112010-09-06 23:52:49 +0000430 if (isFullSet() || isWrappedSet())
431 // Change into [0, 1 << src bit width)
Reid Spencerdc5c1592007-02-28 18:57:32 +0000432 return ConstantRange(APInt(DstTySize,0), APInt(DstTySize,1).shl(SrcTySize));
Chris Lattnerfc33d302004-03-30 00:20:08 +0000433
Jay Foad40f8f622010-12-07 08:25:19 +0000434 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
Chris Lattnerfc33d302004-03-30 00:20:08 +0000435}
436
Nick Lewyckye32157c2007-04-07 15:41:33 +0000437/// signExtend - Return a new range in the specified integer type, which must
438/// be strictly larger than the current type. The returned range will
439/// correspond to the possible range of values as if the source range had been
440/// sign extended.
441ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
Nick Lewycky32cda112010-09-06 23:52:49 +0000442 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
443
Nick Lewyckye32157c2007-04-07 15:41:33 +0000444 unsigned SrcTySize = getBitWidth();
445 assert(SrcTySize < DstTySize && "Not a value extension");
Nick Lewycky32cda112010-09-06 23:52:49 +0000446 if (isFullSet() || isSignWrappedSet()) {
Nick Lewyckye32157c2007-04-07 15:41:33 +0000447 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
Nick Lewyckyff84de72009-07-13 04:17:23 +0000448 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
Nick Lewyckye32157c2007-04-07 15:41:33 +0000449 }
450
Jay Foad40f8f622010-12-07 08:25:19 +0000451 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
Nick Lewyckye32157c2007-04-07 15:41:33 +0000452}
453
Chris Lattnerfc33d302004-03-30 00:20:08 +0000454/// truncate - Return a new range in the specified integer type, which must be
455/// strictly smaller than the current type. The returned range will
Reid Spencere4d87aa2006-12-23 06:05:41 +0000456/// correspond to the possible range of values as if the source range had been
Chris Lattnerfc33d302004-03-30 00:20:08 +0000457/// truncated to the specified type.
Reid Spencerbb626a62007-02-28 22:02:48 +0000458ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
Benjamin Kramerb3ff49e2011-11-24 17:24:33 +0000459 assert(getBitWidth() > DstTySize && "Not a value truncation");
Nuno Lopes55c9ecb2012-07-19 16:27:45 +0000460 if (isEmptySet())
461 return ConstantRange(DstTySize, /*isFullSet=*/false);
462 if (isFullSet())
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000463 return ConstantRange(DstTySize, /*isFullSet=*/true);
Chris Lattnerfc33d302004-03-30 00:20:08 +0000464
Nuno Lopes55c9ecb2012-07-19 16:27:45 +0000465 APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth());
466 APInt MaxBitValue(getBitWidth(), 0);
467 MaxBitValue.setBit(DstTySize);
468
469 APInt LowerDiv(Lower), UpperDiv(Upper);
470 ConstantRange Union(DstTySize, /*isFullSet=*/false);
471
472 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
473 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
474 // then we do the union with [MaxValue, Upper)
475 if (isWrappedSet()) {
476 // if Upper is greater than Max Value, it covers the whole truncated range.
477 if (Upper.uge(MaxValue))
478 return ConstantRange(DstTySize, /*isFullSet=*/true);
479
480 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
481 UpperDiv = APInt::getMaxValue(getBitWidth());
482
483 // Union covers the MaxValue case, so return if the remaining range is just
484 // MaxValue.
485 if (LowerDiv == UpperDiv)
486 return Union;
487 }
488
489 // Chop off the most significant bits that are past the destination bitwidth.
490 if (LowerDiv.uge(MaxValue)) {
491 APInt Div(getBitWidth(), 0);
492 APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
493 UpperDiv = UpperDiv - MaxBitValue * Div;
494 }
495
496 if (UpperDiv.ule(MaxValue))
497 return ConstantRange(LowerDiv.trunc(DstTySize),
498 UpperDiv.trunc(DstTySize)).unionWith(Union);
499
500 // The truncated value wrapps around. Check if we can do better than fullset.
501 APInt UpperModulo = UpperDiv - MaxBitValue;
502 if (UpperModulo.ult(LowerDiv))
503 return ConstantRange(LowerDiv.trunc(DstTySize),
504 UpperModulo.trunc(DstTySize)).unionWith(Union);
505
506 return ConstantRange(DstTySize, /*isFullSet=*/true);
Chris Lattnerfc33d302004-03-30 00:20:08 +0000507}
508
Nuno Lopes95a3be02009-11-09 15:36:28 +0000509/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
510/// value is zero extended, truncated, or left alone to make it that width.
511ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
512 unsigned SrcTySize = getBitWidth();
513 if (SrcTySize > DstTySize)
514 return truncate(DstTySize);
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000515 if (SrcTySize < DstTySize)
Nuno Lopes95a3be02009-11-09 15:36:28 +0000516 return zeroExtend(DstTySize);
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000517 return *this;
Nuno Lopes95a3be02009-11-09 15:36:28 +0000518}
519
520/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
521/// value is sign extended, truncated, or left alone to make it that width.
522ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
523 unsigned SrcTySize = getBitWidth();
524 if (SrcTySize > DstTySize)
525 return truncate(DstTySize);
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000526 if (SrcTySize < DstTySize)
Nuno Lopes95a3be02009-11-09 15:36:28 +0000527 return signExtend(DstTySize);
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000528 return *this;
Nuno Lopes95a3be02009-11-09 15:36:28 +0000529}
530
Dan Gohmana3755d82009-07-09 22:07:27 +0000531ConstantRange
532ConstantRange::add(const ConstantRange &Other) const {
533 if (isEmptySet() || Other.isEmptySet())
534 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Nick Lewyckycf9e07d2009-07-13 02:49:08 +0000535 if (isFullSet() || Other.isFullSet())
536 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Dan Gohmana3755d82009-07-09 22:07:27 +0000537
538 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
539 APInt NewLower = getLower() + Other.getLower();
540 APInt NewUpper = getUpper() + Other.getUpper() - 1;
541 if (NewLower == NewUpper)
542 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
543
544 ConstantRange X = ConstantRange(NewLower, NewUpper);
545 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
546 // We've wrapped, therefore, full set.
547 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
548
549 return X;
Chris Lattner96f9d722002-09-02 00:18:22 +0000550}
551
Dan Gohmana3755d82009-07-09 22:07:27 +0000552ConstantRange
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000553ConstantRange::sub(const ConstantRange &Other) const {
554 if (isEmptySet() || Other.isEmptySet())
555 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
556 if (isFullSet() || Other.isFullSet())
557 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
558
559 APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
Nick Lewyckye6240e82011-06-22 21:13:46 +0000560 APInt NewLower = getLower() - Other.getUpper() + 1;
561 APInt NewUpper = getUpper() - Other.getLower();
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000562 if (NewLower == NewUpper)
563 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
564
565 ConstantRange X = ConstantRange(NewLower, NewUpper);
566 if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
567 // We've wrapped, therefore, full set.
568 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
569
570 return X;
571}
572
573ConstantRange
Dan Gohmana3755d82009-07-09 22:07:27 +0000574ConstantRange::multiply(const ConstantRange &Other) const {
Dan Gohman8dcc58e2010-01-26 15:56:18 +0000575 // TODO: If either operand is a single element and the multiply is known to
576 // be non-wrapping, round the result min and max value to the appropriate
577 // multiple of that element. If wrapping is possible, at least adjust the
578 // range according to the greatest power-of-two factor of the single element.
Dan Gohman153f1eb2010-01-26 04:13:15 +0000579
Nick Lewycky2ff893f2009-07-12 02:19:05 +0000580 if (isEmptySet() || Other.isEmptySet())
581 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Nuno Lopes7e733ea2012-07-16 20:47:16 +0000582
Nick Lewyckyf1db1202009-07-13 03:27:41 +0000583 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
584 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
585 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
586 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
Nick Lewycky2ff893f2009-07-12 02:19:05 +0000587
Nick Lewyckyf1db1202009-07-13 03:27:41 +0000588 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
589 this_max * Other_max + 1);
Nick Lewycky2ff893f2009-07-12 02:19:05 +0000590 return Result_zext.truncate(getBitWidth());
Dan Gohmana3755d82009-07-09 22:07:27 +0000591}
592
593ConstantRange
594ConstantRange::smax(const ConstantRange &Other) const {
Dan Gohman38b06442009-07-09 23:16:10 +0000595 // X smax Y is: range(smax(X_smin, Y_smin),
596 // smax(X_smax, Y_smax))
597 if (isEmptySet() || Other.isEmptySet())
598 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Dan Gohman38b06442009-07-09 23:16:10 +0000599 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
600 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
601 if (NewU == NewL)
602 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
603 return ConstantRange(NewL, NewU);
Dan Gohmana3755d82009-07-09 22:07:27 +0000604}
605
606ConstantRange
607ConstantRange::umax(const ConstantRange &Other) const {
608 // X umax Y is: range(umax(X_umin, Y_umin),
609 // umax(X_umax, Y_umax))
610 if (isEmptySet() || Other.isEmptySet())
611 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Dan Gohmana3755d82009-07-09 22:07:27 +0000612 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
613 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
614 if (NewU == NewL)
615 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
616 return ConstantRange(NewL, NewU);
617}
618
619ConstantRange
Nick Lewycky956daf02009-07-12 05:18:18 +0000620ConstantRange::udiv(const ConstantRange &RHS) const {
621 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
622 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
623 if (RHS.isFullSet())
624 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
625
626 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
627
628 APInt RHS_umin = RHS.getUnsignedMin();
629 if (RHS_umin == 0) {
630 // We want the lowest value in RHS excluding zero. Usually that would be 1
631 // except for a range in the form of [X, 1) in which case it would be X.
632 if (RHS.getUpper() == 1)
633 RHS_umin = RHS.getLower();
634 else
635 RHS_umin = APInt(getBitWidth(), 1);
636 }
637
638 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
639
640 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
641 // this could occur.
642 if (Lower == Upper)
643 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
644
645 return ConstantRange(Lower, Upper);
Dan Gohmana3755d82009-07-09 22:07:27 +0000646}
647
Nuno Lopes34e992d2009-11-12 14:53:53 +0000648ConstantRange
Nick Lewycky198381e2010-09-07 05:39:02 +0000649ConstantRange::binaryAnd(const ConstantRange &Other) const {
650 if (isEmptySet() || Other.isEmptySet())
651 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
652
653 // TODO: replace this with something less conservative
654
655 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
656 if (umin.isAllOnesValue())
657 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
658 return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
659}
660
661ConstantRange
662ConstantRange::binaryOr(const ConstantRange &Other) const {
663 if (isEmptySet() || Other.isEmptySet())
664 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
665
666 // TODO: replace this with something less conservative
667
668 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
669 if (umax.isMinValue())
670 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
671 return ConstantRange(umax, APInt::getNullValue(getBitWidth()));
672}
673
674ConstantRange
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000675ConstantRange::shl(const ConstantRange &Other) const {
676 if (isEmptySet() || Other.isEmptySet())
677 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Nuno Lopes34e992d2009-11-12 14:53:53 +0000678
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000679 APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
680 APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
Nuno Lopes34e992d2009-11-12 14:53:53 +0000681
682 // there's no overflow!
Nuno Lopes44591452009-11-12 15:10:33 +0000683 APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000684 if (Zeros.ugt(Other.getUnsignedMax()))
685 return ConstantRange(min, max + 1);
Nuno Lopes34e992d2009-11-12 14:53:53 +0000686
687 // FIXME: implement the other tricky cases
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000688 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Nuno Lopes34e992d2009-11-12 14:53:53 +0000689}
690
691ConstantRange
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000692ConstantRange::lshr(const ConstantRange &Other) const {
693 if (isEmptySet() || Other.isEmptySet())
694 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Nuno Lopes34e992d2009-11-12 14:53:53 +0000695
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000696 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
697 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
698 if (min == max + 1)
699 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
700
701 return ConstantRange(min, max + 1);
Nuno Lopes34e992d2009-11-12 14:53:53 +0000702}
703
Owen Anderson9773e452010-08-07 05:47:46 +0000704ConstantRange ConstantRange::inverse() const {
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000705 if (isFullSet())
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000706 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Nick Lewycky48a09ae2012-01-03 20:33:00 +0000707 if (isEmptySet())
Nick Lewycky7f9ef4b2010-08-11 22:04:36 +0000708 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Owen Anderson9773e452010-08-07 05:47:46 +0000709 return ConstantRange(Upper, Lower);
710}
711
Dan Gohman38b06442009-07-09 23:16:10 +0000712/// print - Print out the bounds to a stream...
Chris Lattner96f9d722002-09-02 00:18:22 +0000713///
Dan Gohman38b06442009-07-09 23:16:10 +0000714void ConstantRange::print(raw_ostream &OS) const {
Dan Gohmandf6d5e02010-01-26 04:12:55 +0000715 if (isFullSet())
716 OS << "full-set";
717 else if (isEmptySet())
718 OS << "empty-set";
719 else
720 OS << "[" << Lower << "," << Upper << ")";
Dan Gohmana3755d82009-07-09 22:07:27 +0000721}
722
Dan Gohman38b06442009-07-09 23:16:10 +0000723/// dump - Allow printing from a debugger easily...
Dan Gohmana3755d82009-07-09 22:07:27 +0000724///
Dan Gohman38b06442009-07-09 23:16:10 +0000725void ConstantRange::dump() const {
David Greene7fd5fb42010-01-05 01:28:32 +0000726 print(dbgs());
Dan Gohmana3755d82009-07-09 22:07:27 +0000727}