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/Support/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(llvm_move(V)), Upper(Lower + 1) {}
43
44ConstantRange::ConstantRange(APIntMoveTy L, APIntMoveTy U)
45    : Lower(llvm_move(L)), Upper(llvm_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 (isEmptySet())
148    return APInt(getBitWidth()+1, 0);
149
150  if (isFullSet()) {
151    APInt Size(getBitWidth()+1, 0);
152    Size.setBit(getBitWidth());
153    return Size;
154  }
155
156  // This is also correct for wrapped sets.
157  return (Upper - Lower).zext(getBitWidth()+1);
158}
159
160/// getUnsignedMax - Return the largest unsigned value contained in the
161/// ConstantRange.
162///
163APInt ConstantRange::getUnsignedMax() const {
164  if (isFullSet() || isWrappedSet())
165    return APInt::getMaxValue(getBitWidth());
166  return getUpper() - 1;
167}
168
169/// getUnsignedMin - Return the smallest unsigned value contained in the
170/// ConstantRange.
171///
172APInt ConstantRange::getUnsignedMin() const {
173  if (isFullSet() || (isWrappedSet() && getUpper() != 0))
174    return APInt::getMinValue(getBitWidth());
175  return getLower();
176}
177
178/// getSignedMax - Return the largest signed value contained in the
179/// ConstantRange.
180///
181APInt ConstantRange::getSignedMax() const {
182  APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
183  if (!isWrappedSet()) {
184    if (getLower().sle(getUpper() - 1))
185      return getUpper() - 1;
186    return SignedMax;
187  }
188  if (getLower().isNegative() == getUpper().isNegative())
189    return SignedMax;
190  return getUpper() - 1;
191}
192
193/// getSignedMin - Return the smallest signed value contained in the
194/// ConstantRange.
195///
196APInt ConstantRange::getSignedMin() const {
197  APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
198  if (!isWrappedSet()) {
199    if (getLower().sle(getUpper() - 1))
200      return getLower();
201    return SignedMin;
202  }
203  if ((getUpper() - 1).slt(getLower())) {
204    if (getUpper() != SignedMin)
205      return SignedMin;
206  }
207  return getLower();
208}
209
210/// contains - Return true if the specified value is in the set.
211///
212bool ConstantRange::contains(const APInt &V) const {
213  if (Lower == Upper)
214    return isFullSet();
215
216  if (!isWrappedSet())
217    return Lower.ule(V) && V.ult(Upper);
218  return Lower.ule(V) || V.ult(Upper);
219}
220
221/// contains - Return true if the argument is a subset of this range.
222/// Two equal sets contain each other. The empty set contained by all other
223/// sets.
224///
225bool ConstantRange::contains(const ConstantRange &Other) const {
226  if (isFullSet() || Other.isEmptySet()) return true;
227  if (isEmptySet() || Other.isFullSet()) return false;
228
229  if (!isWrappedSet()) {
230    if (Other.isWrappedSet())
231      return false;
232
233    return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
234  }
235
236  if (!Other.isWrappedSet())
237    return Other.getUpper().ule(Upper) ||
238           Lower.ule(Other.getLower());
239
240  return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
241}
242
243/// subtract - Subtract the specified constant from the endpoints of this
244/// constant range.
245ConstantRange ConstantRange::subtract(const APInt &Val) const {
246  assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
247  // If the set is empty or full, don't modify the endpoints.
248  if (Lower == Upper)
249    return *this;
250  return ConstantRange(Lower - Val, Upper - Val);
251}
252
253/// \brief Subtract the specified range from this range (aka relative complement
254/// of the sets).
255ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
256  return intersectWith(CR.inverse());
257}
258
259/// intersectWith - Return the range that results from the intersection of this
260/// range with another range.  The resultant range is guaranteed to include all
261/// elements contained in both input ranges, and to have the smallest possible
262/// set size that does so.  Because there may be two intersections with the
263/// same set size, A.intersectWith(B) might not be equal to B.intersectWith(A).
264ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
265  assert(getBitWidth() == CR.getBitWidth() &&
266         "ConstantRange types don't agree!");
267
268  // Handle common cases.
269  if (   isEmptySet() || CR.isFullSet()) return *this;
270  if (CR.isEmptySet() ||    isFullSet()) return CR;
271
272  if (!isWrappedSet() && CR.isWrappedSet())
273    return CR.intersectWith(*this);
274
275  if (!isWrappedSet() && !CR.isWrappedSet()) {
276    if (Lower.ult(CR.Lower)) {
277      if (Upper.ule(CR.Lower))
278        return ConstantRange(getBitWidth(), false);
279
280      if (Upper.ult(CR.Upper))
281        return ConstantRange(CR.Lower, Upper);
282
283      return CR;
284    }
285    if (Upper.ult(CR.Upper))
286      return *this;
287
288    if (Lower.ult(CR.Upper))
289      return ConstantRange(Lower, CR.Upper);
290
291    return ConstantRange(getBitWidth(), false);
292  }
293
294  if (isWrappedSet() && !CR.isWrappedSet()) {
295    if (CR.Lower.ult(Upper)) {
296      if (CR.Upper.ult(Upper))
297        return CR;
298
299      if (CR.Upper.ule(Lower))
300        return ConstantRange(CR.Lower, Upper);
301
302      if (getSetSize().ult(CR.getSetSize()))
303        return *this;
304      return CR;
305    }
306    if (CR.Lower.ult(Lower)) {
307      if (CR.Upper.ule(Lower))
308        return ConstantRange(getBitWidth(), false);
309
310      return ConstantRange(Lower, CR.Upper);
311    }
312    return CR;
313  }
314
315  if (CR.Upper.ult(Upper)) {
316    if (CR.Lower.ult(Upper)) {
317      if (getSetSize().ult(CR.getSetSize()))
318        return *this;
319      return CR;
320    }
321
322    if (CR.Lower.ult(Lower))
323      return ConstantRange(Lower, CR.Upper);
324
325    return CR;
326  }
327  if (CR.Upper.ule(Lower)) {
328    if (CR.Lower.ult(Lower))
329      return *this;
330
331    return ConstantRange(CR.Lower, Upper);
332  }
333  if (getSetSize().ult(CR.getSetSize()))
334    return *this;
335  return CR;
336}
337
338
339/// unionWith - Return the range that results from the union of this range with
340/// another range.  The resultant range is guaranteed to include the elements of
341/// both sets, but may contain more.  For example, [3, 9) union [12,15) is
342/// [3, 15), which includes 9, 10, and 11, which were not included in either
343/// set before.
344///
345ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
346  assert(getBitWidth() == CR.getBitWidth() &&
347         "ConstantRange types don't agree!");
348
349  if (   isFullSet() || CR.isEmptySet()) return *this;
350  if (CR.isFullSet() ||    isEmptySet()) return CR;
351
352  if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
353
354  if (!isWrappedSet() && !CR.isWrappedSet()) {
355    if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
356      // If the two ranges are disjoint, find the smaller gap and bridge it.
357      APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
358      if (d1.ult(d2))
359        return ConstantRange(Lower, CR.Upper);
360      return ConstantRange(CR.Lower, Upper);
361    }
362
363    APInt L = Lower, U = Upper;
364    if (CR.Lower.ult(L))
365      L = CR.Lower;
366    if ((CR.Upper - 1).ugt(U - 1))
367      U = CR.Upper;
368
369    if (L == 0 && U == 0)
370      return ConstantRange(getBitWidth());
371
372    return ConstantRange(L, U);
373  }
374
375  if (!CR.isWrappedSet()) {
376    // ------U   L-----  and  ------U   L----- : this
377    //   L--U                            L--U  : CR
378    if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
379      return *this;
380
381    // ------U   L----- : this
382    //    L---------U   : CR
383    if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
384      return ConstantRange(getBitWidth());
385
386    // ----U       L---- : this
387    //       L---U       : CR
388    //    <d1>  <d2>
389    if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
390      APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
391      if (d1.ult(d2))
392        return ConstantRange(Lower, CR.Upper);
393      return ConstantRange(CR.Lower, Upper);
394    }
395
396    // ----U     L----- : this
397    //        L----U    : CR
398    if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
399      return ConstantRange(CR.Lower, Upper);
400
401    // ------U    L---- : this
402    //    L-----U       : CR
403    assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
404           "ConstantRange::unionWith missed a case with one range wrapped");
405    return ConstantRange(Lower, CR.Upper);
406  }
407
408  // ------U    L----  and  ------U    L---- : this
409  // -U  L-----------  and  ------------U  L : CR
410  if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
411    return ConstantRange(getBitWidth());
412
413  APInt L = Lower, U = Upper;
414  if (CR.Upper.ugt(U))
415    U = CR.Upper;
416  if (CR.Lower.ult(L))
417    L = CR.Lower;
418
419  return ConstantRange(L, U);
420}
421
422/// zeroExtend - 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
425/// zero extended.
426ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
427  if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
428
429  unsigned SrcTySize = getBitWidth();
430  assert(SrcTySize < DstTySize && "Not a value extension");
431  if (isFullSet() || isWrappedSet()) {
432    // Change into [0, 1 << src bit width)
433    APInt LowerExt(DstTySize, 0);
434    if (!Upper) // special case: [X, 0) -- not really wrapping around
435      LowerExt = Lower.zext(DstTySize);
436    return ConstantRange(LowerExt, APInt::getOneBitSet(DstTySize, SrcTySize));
437  }
438
439  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
440}
441
442/// signExtend - Return a new range in the specified integer type, which must
443/// be strictly larger than the current type.  The returned range will
444/// correspond to the possible range of values as if the source range had been
445/// sign extended.
446ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
447  if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
448
449  unsigned SrcTySize = getBitWidth();
450  assert(SrcTySize < DstTySize && "Not a value extension");
451  if (isFullSet() || isSignWrappedSet()) {
452    return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
453                         APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
454  }
455
456  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
457}
458
459/// truncate - Return a new range in the specified integer type, which must be
460/// strictly smaller than the current type.  The returned range will
461/// correspond to the possible range of values as if the source range had been
462/// truncated to the specified type.
463ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
464  assert(getBitWidth() > DstTySize && "Not a value truncation");
465  if (isEmptySet())
466    return ConstantRange(DstTySize, /*isFullSet=*/false);
467  if (isFullSet())
468    return ConstantRange(DstTySize, /*isFullSet=*/true);
469
470  APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth());
471  APInt MaxBitValue(getBitWidth(), 0);
472  MaxBitValue.setBit(DstTySize);
473
474  APInt LowerDiv(Lower), UpperDiv(Upper);
475  ConstantRange Union(DstTySize, /*isFullSet=*/false);
476
477  // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
478  // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
479  // then we do the union with [MaxValue, Upper)
480  if (isWrappedSet()) {
481    // if Upper is greater than Max Value, it covers the whole truncated range.
482    if (Upper.uge(MaxValue))
483      return ConstantRange(DstTySize, /*isFullSet=*/true);
484
485    Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
486    UpperDiv = APInt::getMaxValue(getBitWidth());
487
488    // Union covers the MaxValue case, so return if the remaining range is just
489    // MaxValue.
490    if (LowerDiv == UpperDiv)
491      return Union;
492  }
493
494  // Chop off the most significant bits that are past the destination bitwidth.
495  if (LowerDiv.uge(MaxValue)) {
496    APInt Div(getBitWidth(), 0);
497    APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
498    UpperDiv = UpperDiv - MaxBitValue * Div;
499  }
500
501  if (UpperDiv.ule(MaxValue))
502    return ConstantRange(LowerDiv.trunc(DstTySize),
503                         UpperDiv.trunc(DstTySize)).unionWith(Union);
504
505  // The truncated value wrapps around. Check if we can do better than fullset.
506  APInt UpperModulo = UpperDiv - MaxBitValue;
507  if (UpperModulo.ult(LowerDiv))
508    return ConstantRange(LowerDiv.trunc(DstTySize),
509                         UpperModulo.trunc(DstTySize)).unionWith(Union);
510
511  return ConstantRange(DstTySize, /*isFullSet=*/true);
512}
513
514/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
515/// value is zero extended, truncated, or left alone to make it that width.
516ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
517  unsigned SrcTySize = getBitWidth();
518  if (SrcTySize > DstTySize)
519    return truncate(DstTySize);
520  if (SrcTySize < DstTySize)
521    return zeroExtend(DstTySize);
522  return *this;
523}
524
525/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
526/// value is sign extended, truncated, or left alone to make it that width.
527ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
528  unsigned SrcTySize = getBitWidth();
529  if (SrcTySize > DstTySize)
530    return truncate(DstTySize);
531  if (SrcTySize < DstTySize)
532    return signExtend(DstTySize);
533  return *this;
534}
535
536ConstantRange
537ConstantRange::add(const ConstantRange &Other) const {
538  if (isEmptySet() || Other.isEmptySet())
539    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
540  if (isFullSet() || Other.isFullSet())
541    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
542
543  APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
544  APInt NewLower = getLower() + Other.getLower();
545  APInt NewUpper = getUpper() + Other.getUpper() - 1;
546  if (NewLower == NewUpper)
547    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
548
549  ConstantRange X = ConstantRange(NewLower, NewUpper);
550  if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
551    // We've wrapped, therefore, full set.
552    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
553
554  return X;
555}
556
557ConstantRange
558ConstantRange::sub(const ConstantRange &Other) const {
559  if (isEmptySet() || Other.isEmptySet())
560    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
561  if (isFullSet() || Other.isFullSet())
562    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
563
564  APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
565  APInt NewLower = getLower() - Other.getUpper() + 1;
566  APInt NewUpper = getUpper() - Other.getLower();
567  if (NewLower == NewUpper)
568    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
569
570  ConstantRange X = ConstantRange(NewLower, NewUpper);
571  if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
572    // We've wrapped, therefore, full set.
573    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
574
575  return X;
576}
577
578ConstantRange
579ConstantRange::multiply(const ConstantRange &Other) const {
580  // TODO: If either operand is a single element and the multiply is known to
581  // be non-wrapping, round the result min and max value to the appropriate
582  // multiple of that element. If wrapping is possible, at least adjust the
583  // range according to the greatest power-of-two factor of the single element.
584
585  if (isEmptySet() || Other.isEmptySet())
586    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
587
588  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
589  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
590  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
591  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
592
593  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
594                                            this_max * Other_max + 1);
595  return Result_zext.truncate(getBitWidth());
596}
597
598ConstantRange
599ConstantRange::smax(const ConstantRange &Other) const {
600  // X smax Y is: range(smax(X_smin, Y_smin),
601  //                    smax(X_smax, Y_smax))
602  if (isEmptySet() || Other.isEmptySet())
603    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
604  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
605  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
606  if (NewU == NewL)
607    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
608  return ConstantRange(NewL, NewU);
609}
610
611ConstantRange
612ConstantRange::umax(const ConstantRange &Other) const {
613  // X umax Y is: range(umax(X_umin, Y_umin),
614  //                    umax(X_umax, Y_umax))
615  if (isEmptySet() || Other.isEmptySet())
616    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
617  APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
618  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
619  if (NewU == NewL)
620    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
621  return ConstantRange(NewL, NewU);
622}
623
624ConstantRange
625ConstantRange::udiv(const ConstantRange &RHS) const {
626  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
627    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
628  if (RHS.isFullSet())
629    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
630
631  APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
632
633  APInt RHS_umin = RHS.getUnsignedMin();
634  if (RHS_umin == 0) {
635    // We want the lowest value in RHS excluding zero. Usually that would be 1
636    // except for a range in the form of [X, 1) in which case it would be X.
637    if (RHS.getUpper() == 1)
638      RHS_umin = RHS.getLower();
639    else
640      RHS_umin = APInt(getBitWidth(), 1);
641  }
642
643  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
644
645  // If the LHS is Full and the RHS is a wrapped interval containing 1 then
646  // this could occur.
647  if (Lower == Upper)
648    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
649
650  return ConstantRange(Lower, Upper);
651}
652
653ConstantRange
654ConstantRange::binaryAnd(const ConstantRange &Other) const {
655  if (isEmptySet() || Other.isEmptySet())
656    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
657
658  // TODO: replace this with something less conservative
659
660  APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
661  if (umin.isAllOnesValue())
662    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
663  return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
664}
665
666ConstantRange
667ConstantRange::binaryOr(const ConstantRange &Other) const {
668  if (isEmptySet() || Other.isEmptySet())
669    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
670
671  // TODO: replace this with something less conservative
672
673  APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
674  if (umax.isMinValue())
675    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
676  return ConstantRange(umax, APInt::getNullValue(getBitWidth()));
677}
678
679ConstantRange
680ConstantRange::shl(const ConstantRange &Other) const {
681  if (isEmptySet() || Other.isEmptySet())
682    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
683
684  APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
685  APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
686
687  // there's no overflow!
688  APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
689  if (Zeros.ugt(Other.getUnsignedMax()))
690    return ConstantRange(min, max + 1);
691
692  // FIXME: implement the other tricky cases
693  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
694}
695
696ConstantRange
697ConstantRange::lshr(const ConstantRange &Other) const {
698  if (isEmptySet() || Other.isEmptySet())
699    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
700
701  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
702  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
703  if (min == max + 1)
704    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
705
706  return ConstantRange(min, max + 1);
707}
708
709ConstantRange ConstantRange::inverse() const {
710  if (isFullSet())
711    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
712  if (isEmptySet())
713    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
714  return ConstantRange(Upper, Lower);
715}
716
717/// print - Print out the bounds to a stream...
718///
719void ConstantRange::print(raw_ostream &OS) const {
720  if (isFullSet())
721    OS << "full-set";
722  else if (isEmptySet())
723    OS << "empty-set";
724  else
725    OS << "[" << Lower << "," << Upper << ")";
726}
727
728/// dump - Allow printing from a debugger easily...
729///
730void ConstantRange::dump() const {
731  print(dbgs());
732}
733