1//===-- ConstantRange.cpp - ConstantRange implementation ------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
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
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"
28using namespace llvm;
29
30/// Initialize a full (the default) or empty set for the specified type.
31///
32ConstantRange::ConstantRange(uint32_t BitWidth, bool Full) {
33  if (Full)
34    Lower = Upper = APInt::getMaxValue(BitWidth);
35  else
36    Lower = Upper = APInt::getMinValue(BitWidth);
37}
38
39/// Initialize a range to hold the single specified value.
40///
41ConstantRange::ConstantRange(APIntMoveTy V)
42    : Lower(std::move(V)), Upper(Lower + 1) {}
43
44ConstantRange::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!");
50}
51
52ConstantRange ConstantRange::makeICmpRegion(unsigned Pred,
53                                            const ConstantRange &CR) {
54  if (CR.isEmptySet())
55    return CR;
56
57  uint32_t W = CR.getBitWidth();
58  switch (Pred) {
59    default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()");
60    case CmpInst::ICMP_EQ:
61      return CR;
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);
71    }
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);
77    }
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);
83    }
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);
89    }
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));
95    }
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));
101    }
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));
107    }
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));
113    }
114  }
115}
116
117/// isFullSet - Return true if this set contains all of the elements possible
118/// for this data-type
119bool ConstantRange::isFullSet() const {
120  return Lower == Upper && Lower.isMaxValue();
121}
122
123/// isEmptySet - Return true if this set contains no members.
124///
125bool ConstantRange::isEmptySet() const {
126  return Lower == Upper && Lower.isMinValue();
127}
128
129/// isWrappedSet - Return true if this set wraps around the top of the range,
130/// for example: [100, 8)
131///
132bool ConstantRange::isWrappedSet() const {
133  return Lower.ugt(Upper);
134}
135
136/// isSignWrappedSet - Return true if this set wraps around the INT_MIN of
137/// its bitwidth, for example: i8 [120, 140).
138///
139bool ConstantRange::isSignWrappedSet() const {
140  return contains(APInt::getSignedMaxValue(getBitWidth())) &&
141         contains(APInt::getSignedMinValue(getBitWidth()));
142}
143
144/// getSetSize - Return the number of elements in this set.
145///
146APInt ConstantRange::getSetSize() const {
147  if (isFullSet()) {
148    APInt Size(getBitWidth()+1, 0);
149    Size.setBit(getBitWidth());
150    return Size;
151  }
152
153  // This is also correct for wrapped sets.
154  return (Upper - Lower).zext(getBitWidth()+1);
155}
156
157/// getUnsignedMax - Return the largest unsigned value contained in the
158/// ConstantRange.
159///
160APInt ConstantRange::getUnsignedMax() const {
161  if (isFullSet() || isWrappedSet())
162    return APInt::getMaxValue(getBitWidth());
163  return getUpper() - 1;
164}
165
166/// getUnsignedMin - Return the smallest unsigned value contained in the
167/// ConstantRange.
168///
169APInt ConstantRange::getUnsignedMin() const {
170  if (isFullSet() || (isWrappedSet() && getUpper() != 0))
171    return APInt::getMinValue(getBitWidth());
172  return getLower();
173}
174
175/// getSignedMax - Return the largest signed value contained in the
176/// ConstantRange.
177///
178APInt ConstantRange::getSignedMax() const {
179  APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
180  if (!isWrappedSet()) {
181    if (getLower().sle(getUpper() - 1))
182      return getUpper() - 1;
183    return SignedMax;
184  }
185  if (getLower().isNegative() == getUpper().isNegative())
186    return SignedMax;
187  return getUpper() - 1;
188}
189
190/// getSignedMin - Return the smallest signed value contained in the
191/// ConstantRange.
192///
193APInt ConstantRange::getSignedMin() const {
194  APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
195  if (!isWrappedSet()) {
196    if (getLower().sle(getUpper() - 1))
197      return getLower();
198    return SignedMin;
199  }
200  if ((getUpper() - 1).slt(getLower())) {
201    if (getUpper() != SignedMin)
202      return SignedMin;
203  }
204  return getLower();
205}
206
207/// contains - Return true if the specified value is in the set.
208///
209bool ConstantRange::contains(const APInt &V) const {
210  if (Lower == Upper)
211    return isFullSet();
212
213  if (!isWrappedSet())
214    return Lower.ule(V) && V.ult(Upper);
215  return Lower.ule(V) || V.ult(Upper);
216}
217
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
220/// sets.
221///
222bool ConstantRange::contains(const ConstantRange &Other) const {
223  if (isFullSet() || Other.isEmptySet()) return true;
224  if (isEmptySet() || Other.isFullSet()) return false;
225
226  if (!isWrappedSet()) {
227    if (Other.isWrappedSet())
228      return false;
229
230    return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
231  }
232
233  if (!Other.isWrappedSet())
234    return Other.getUpper().ule(Upper) ||
235           Lower.ule(Other.getLower());
236
237  return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
238}
239
240/// subtract - Subtract the specified constant from the endpoints of this
241/// constant range.
242ConstantRange 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.
245  if (Lower == Upper)
246    return *this;
247  return ConstantRange(Lower - Val, Upper - Val);
248}
249
250/// \brief Subtract the specified range from this range (aka relative complement
251/// of the sets).
252ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
253  return intersectWith(CR.inverse());
254}
255
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).
261ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
262  assert(getBitWidth() == CR.getBitWidth() &&
263         "ConstantRange types don't agree!");
264
265  // Handle common cases.
266  if (   isEmptySet() || CR.isFullSet()) return *this;
267  if (CR.isEmptySet() ||    isFullSet()) return CR;
268
269  if (!isWrappedSet() && CR.isWrappedSet())
270    return CR.intersectWith(*this);
271
272  if (!isWrappedSet() && !CR.isWrappedSet()) {
273    if (Lower.ult(CR.Lower)) {
274      if (Upper.ule(CR.Lower))
275        return ConstantRange(getBitWidth(), false);
276
277      if (Upper.ult(CR.Upper))
278        return ConstantRange(CR.Lower, Upper);
279
280      return CR;
281    }
282    if (Upper.ult(CR.Upper))
283      return *this;
284
285    if (Lower.ult(CR.Upper))
286      return ConstantRange(Lower, CR.Upper);
287
288    return ConstantRange(getBitWidth(), false);
289  }
290
291  if (isWrappedSet() && !CR.isWrappedSet()) {
292    if (CR.Lower.ult(Upper)) {
293      if (CR.Upper.ult(Upper))
294        return CR;
295
296      if (CR.Upper.ule(Lower))
297        return ConstantRange(CR.Lower, Upper);
298
299      if (getSetSize().ult(CR.getSetSize()))
300        return *this;
301      return CR;
302    }
303    if (CR.Lower.ult(Lower)) {
304      if (CR.Upper.ule(Lower))
305        return ConstantRange(getBitWidth(), false);
306
307      return ConstantRange(Lower, CR.Upper);
308    }
309    return CR;
310  }
311
312  if (CR.Upper.ult(Upper)) {
313    if (CR.Lower.ult(Upper)) {
314      if (getSetSize().ult(CR.getSetSize()))
315        return *this;
316      return CR;
317    }
318
319    if (CR.Lower.ult(Lower))
320      return ConstantRange(Lower, CR.Upper);
321
322    return CR;
323  }
324  if (CR.Upper.ule(Lower)) {
325    if (CR.Lower.ult(Lower))
326      return *this;
327
328    return ConstantRange(CR.Lower, Upper);
329  }
330  if (getSetSize().ult(CR.getSetSize()))
331    return *this;
332  return CR;
333}
334
335
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
340/// set before.
341///
342ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
343  assert(getBitWidth() == CR.getBitWidth() &&
344         "ConstantRange types don't agree!");
345
346  if (   isFullSet() || CR.isEmptySet()) return *this;
347  if (CR.isFullSet() ||    isEmptySet()) return CR;
348
349  if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
350
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;
355      if (d1.ult(d2))
356        return ConstantRange(Lower, CR.Upper);
357      return ConstantRange(CR.Lower, Upper);
358    }
359
360    APInt L = Lower, U = Upper;
361    if (CR.Lower.ult(L))
362      L = CR.Lower;
363    if ((CR.Upper - 1).ugt(U - 1))
364      U = CR.Upper;
365
366    if (L == 0 && U == 0)
367      return ConstantRange(getBitWidth());
368
369    return ConstantRange(L, U);
370  }
371
372  if (!CR.isWrappedSet()) {
373    // ------U   L-----  and  ------U   L----- : this
374    //   L--U                            L--U  : CR
375    if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
376      return *this;
377
378    // ------U   L----- : this
379    //    L---------U   : CR
380    if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
381      return ConstantRange(getBitWidth());
382
383    // ----U       L---- : this
384    //       L---U       : CR
385    //    <d1>  <d2>
386    if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
387      APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
388      if (d1.ult(d2))
389        return ConstantRange(Lower, CR.Upper);
390      return ConstantRange(CR.Lower, Upper);
391    }
392
393    // ----U     L----- : this
394    //        L----U    : CR
395    if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
396      return ConstantRange(CR.Lower, Upper);
397
398    // ------U    L---- : this
399    //    L-----U       : CR
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);
403  }
404
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());
409
410  APInt L = Lower, U = Upper;
411  if (CR.Upper.ugt(U))
412    U = CR.Upper;
413  if (CR.Lower.ult(L))
414    L = CR.Lower;
415
416  return ConstantRange(L, U);
417}
418
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
422/// zero extended.
423ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
424  if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
425
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));
434  }
435
436  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
437}
438
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
442/// sign extended.
443ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
444  if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
445
446  unsigned SrcTySize = getBitWidth();
447  assert(SrcTySize < DstTySize && "Not a value extension");
448
449  // special case: [X, INT_MIN) -- not really wrapping around
450  if (Upper.isMinSignedValue())
451    return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
452
453  if (isFullSet() || isSignWrappedSet()) {
454    return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
455                         APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
456  }
457
458  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
459}
460
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.
465ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
466  assert(getBitWidth() > DstTySize && "Not a value truncation");
467  if (isEmptySet())
468    return ConstantRange(DstTySize, /*isFullSet=*/false);
469  if (isFullSet())
470    return ConstantRange(DstTySize, /*isFullSet=*/true);
471
472  APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth());
473  APInt MaxBitValue(getBitWidth(), 0);
474  MaxBitValue.setBit(DstTySize);
475
476  APInt LowerDiv(Lower), UpperDiv(Upper);
477  ConstantRange Union(DstTySize, /*isFullSet=*/false);
478
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);
486
487    Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
488    UpperDiv = APInt::getMaxValue(getBitWidth());
489
490    // Union covers the MaxValue case, so return if the remaining range is just
491    // MaxValue.
492    if (LowerDiv == UpperDiv)
493      return Union;
494  }
495
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;
501  }
502
503  if (UpperDiv.ule(MaxValue))
504    return ConstantRange(LowerDiv.trunc(DstTySize),
505                         UpperDiv.trunc(DstTySize)).unionWith(Union);
506
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);
512
513  return ConstantRange(DstTySize, /*isFullSet=*/true);
514}
515
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.
518ConstantRange 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);
524  return *this;
525}
526
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.
529ConstantRange 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);
535  return *this;
536}
537
538ConstantRange
539ConstantRange::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);
544
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);
550
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);
555
556  return X;
557}
558
559ConstantRange
560ConstantRange::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);
565
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);
571
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);
576
577  return X;
578}
579
580ConstantRange
581ConstantRange::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.
586
587  if (isEmptySet() || Other.isEmptySet())
588    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
589
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);
594
595  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
596                                            this_max * Other_max + 1);
597  return Result_zext.truncate(getBitWidth());
598}
599
600ConstantRange
601ConstantRange::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;
608  if (NewU == NewL)
609    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
610  return ConstantRange(NewL, NewU);
611}
612
613ConstantRange
614ConstantRange::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;
621  if (NewU == NewL)
622    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
623  return ConstantRange(NewL, NewU);
624}
625
626ConstantRange
627ConstantRange::udiv(const ConstantRange &RHS) const {
628  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
629    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
630  if (RHS.isFullSet())
631    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
632
633  APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
634
635  APInt RHS_umin = RHS.getUnsignedMin();
636  if (RHS_umin == 0) {
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();
641    else
642      RHS_umin = APInt(getBitWidth(), 1);
643  }
644
645  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
646
647  // If the LHS is Full and the RHS is a wrapped interval containing 1 then
648  // this could occur.
649  if (Lower == Upper)
650    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
651
652  return ConstantRange(Lower, Upper);
653}
654
655ConstantRange
656ConstantRange::binaryAnd(const ConstantRange &Other) const {
657  if (isEmptySet() || Other.isEmptySet())
658    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
659
660  // TODO: replace this with something less conservative
661
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);
666}
667
668ConstantRange
669ConstantRange::binaryOr(const ConstantRange &Other) const {
670  if (isEmptySet() || Other.isEmptySet())
671    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
672
673  // TODO: replace this with something less conservative
674
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()));
679}
680
681ConstantRange
682ConstantRange::shl(const ConstantRange &Other) const {
683  if (isEmptySet() || Other.isEmptySet())
684    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
685
686  APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
687  APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
688
689  // there's no overflow!
690  APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
691  if (Zeros.ugt(Other.getUnsignedMax()))
692    return ConstantRange(min, max + 1);
693
694  // FIXME: implement the other tricky cases
695  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
696}
697
698ConstantRange
699ConstantRange::lshr(const ConstantRange &Other) const {
700  if (isEmptySet() || Other.isEmptySet())
701    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
702
703  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
704  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
705  if (min == max + 1)
706    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
707
708  return ConstantRange(min, max + 1);
709}
710
711ConstantRange ConstantRange::inverse() const {
712  if (isFullSet())
713    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
714  if (isEmptySet())
715    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
716  return ConstantRange(Upper, Lower);
717}
718
719/// print - Print out the bounds to a stream...
720///
721void ConstantRange::print(raw_ostream &OS) const {
722  if (isFullSet())
723    OS << "full-set";
724  else if (isEmptySet())
725    OS << "empty-set";
726  else
727    OS << "[" << Lower << "," << Upper << ")";
728}
729
730/// dump - Allow printing from a debugger easily...
731///
732void ConstantRange::dump() const {
733  print(dbgs());
734}
735