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/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(const APInt &V) : Lower(V), Upper(V + 1) {}
42
43ConstantRange::ConstantRange(const APInt &L, const APInt &U) :
44  Lower(L), Upper(U) {
45  assert(L.getBitWidth() == U.getBitWidth() &&
46         "ConstantRange with unequal bit widths");
47  assert((L != U || (L.isMaxValue() || L.isMinValue())) &&
48         "Lower == Upper, but they aren't min or max value!");
49}
50
51ConstantRange ConstantRange::makeICmpRegion(unsigned Pred,
52                                            const ConstantRange &CR) {
53  if (CR.isEmptySet())
54    return CR;
55
56  uint32_t W = CR.getBitWidth();
57  switch (Pred) {
58    default: llvm_unreachable("Invalid ICmp predicate to makeICmpRegion()");
59    case CmpInst::ICMP_EQ:
60      return CR;
61    case CmpInst::ICMP_NE:
62      if (CR.isSingleElement())
63        return ConstantRange(CR.getUpper(), CR.getLower());
64      return ConstantRange(W);
65    case CmpInst::ICMP_ULT: {
66      APInt UMax(CR.getUnsignedMax());
67      if (UMax.isMinValue())
68        return ConstantRange(W, /* empty */ false);
69      return ConstantRange(APInt::getMinValue(W), UMax);
70    }
71    case CmpInst::ICMP_SLT: {
72      APInt SMax(CR.getSignedMax());
73      if (SMax.isMinSignedValue())
74        return ConstantRange(W, /* empty */ false);
75      return ConstantRange(APInt::getSignedMinValue(W), SMax);
76    }
77    case CmpInst::ICMP_ULE: {
78      APInt UMax(CR.getUnsignedMax());
79      if (UMax.isMaxValue())
80        return ConstantRange(W);
81      return ConstantRange(APInt::getMinValue(W), UMax + 1);
82    }
83    case CmpInst::ICMP_SLE: {
84      APInt SMax(CR.getSignedMax());
85      if (SMax.isMaxSignedValue())
86        return ConstantRange(W);
87      return ConstantRange(APInt::getSignedMinValue(W), SMax + 1);
88    }
89    case CmpInst::ICMP_UGT: {
90      APInt UMin(CR.getUnsignedMin());
91      if (UMin.isMaxValue())
92        return ConstantRange(W, /* empty */ false);
93      return ConstantRange(UMin + 1, APInt::getNullValue(W));
94    }
95    case CmpInst::ICMP_SGT: {
96      APInt SMin(CR.getSignedMin());
97      if (SMin.isMaxSignedValue())
98        return ConstantRange(W, /* empty */ false);
99      return ConstantRange(SMin + 1, APInt::getSignedMinValue(W));
100    }
101    case CmpInst::ICMP_UGE: {
102      APInt UMin(CR.getUnsignedMin());
103      if (UMin.isMinValue())
104        return ConstantRange(W);
105      return ConstantRange(UMin, APInt::getNullValue(W));
106    }
107    case CmpInst::ICMP_SGE: {
108      APInt SMin(CR.getSignedMin());
109      if (SMin.isMinSignedValue())
110        return ConstantRange(W);
111      return ConstantRange(SMin, APInt::getSignedMinValue(W));
112    }
113  }
114}
115
116/// isFullSet - Return true if this set contains all of the elements possible
117/// for this data-type
118bool ConstantRange::isFullSet() const {
119  return Lower == Upper && Lower.isMaxValue();
120}
121
122/// isEmptySet - Return true if this set contains no members.
123///
124bool ConstantRange::isEmptySet() const {
125  return Lower == Upper && Lower.isMinValue();
126}
127
128/// isWrappedSet - Return true if this set wraps around the top of the range,
129/// for example: [100, 8)
130///
131bool ConstantRange::isWrappedSet() const {
132  return Lower.ugt(Upper);
133}
134
135/// 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
143/// getSetSize - Return the number of elements in this set.
144///
145APInt ConstantRange::getSetSize() const {
146  if (isEmptySet())
147    return APInt(getBitWidth()+1, 0);
148
149  if (isFullSet()) {
150    APInt Size(getBitWidth()+1, 0);
151    Size.setBit(getBitWidth());
152    return Size;
153  }
154
155  // This is also correct for wrapped sets.
156  return (Upper - Lower).zext(getBitWidth()+1);
157}
158
159/// 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());
165  return getUpper() - 1;
166}
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());
174  return getLower();
175}
176
177/// getSignedMax - Return the largest signed value contained in the
178/// ConstantRange.
179///
180APInt ConstantRange::getSignedMax() const {
181  APInt SignedMax(APInt::getSignedMaxValue(getBitWidth()));
182  if (!isWrappedSet()) {
183    if (getLower().sle(getUpper() - 1))
184      return getUpper() - 1;
185    return SignedMax;
186  }
187  if (getLower().isNegative() == getUpper().isNegative())
188    return SignedMax;
189  return getUpper() - 1;
190}
191
192/// getSignedMin - Return the smallest signed value contained in the
193/// ConstantRange.
194///
195APInt ConstantRange::getSignedMin() const {
196  APInt SignedMin(APInt::getSignedMinValue(getBitWidth()));
197  if (!isWrappedSet()) {
198    if (getLower().sle(getUpper() - 1))
199      return getLower();
200    return SignedMin;
201  }
202  if ((getUpper() - 1).slt(getLower())) {
203    if (getUpper() != SignedMin)
204      return SignedMin;
205  }
206  return getLower();
207}
208
209/// contains - Return true if the specified value is in the set.
210///
211bool ConstantRange::contains(const APInt &V) const {
212  if (Lower == Upper)
213    return isFullSet();
214
215  if (!isWrappedSet())
216    return Lower.ule(V) && V.ult(Upper);
217  return Lower.ule(V) || V.ult(Upper);
218}
219
220/// contains - Return true if the argument is a subset of this range.
221/// Two equal sets contain each other. The empty set contained by all other
222/// sets.
223///
224bool ConstantRange::contains(const ConstantRange &Other) const {
225  if (isFullSet() || Other.isEmptySet()) return true;
226  if (isEmptySet() || Other.isFullSet()) return false;
227
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
242/// subtract - Subtract the specified constant from the endpoints of this
243/// constant range.
244ConstantRange ConstantRange::subtract(const APInt &Val) const {
245  assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
246  // If the set is empty or full, don't modify the endpoints.
247  if (Lower == Upper)
248    return *this;
249  return ConstantRange(Lower - Val, Upper - Val);
250}
251
252/// \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
258/// intersectWith - Return the range that results from the intersection of this
259/// 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).
263ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
264  assert(getBitWidth() == CR.getBitWidth() &&
265         "ConstantRange types don't agree!");
266
267  // Handle common cases.
268  if (   isEmptySet() || CR.isFullSet()) return *this;
269  if (CR.isEmptySet() ||    isFullSet()) return CR;
270
271  if (!isWrappedSet() && CR.isWrappedSet())
272    return CR.intersectWith(*this);
273
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;
283    }
284    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);
291  }
292
293  if (isWrappedSet() && !CR.isWrappedSet()) {
294    if (CR.Lower.ult(Upper)) {
295      if (CR.Upper.ult(Upper))
296        return CR;
297
298      if (CR.Upper.ule(Lower))
299        return ConstantRange(CR.Lower, Upper);
300
301      if (getSetSize().ult(CR.getSetSize()))
302        return *this;
303      return CR;
304    }
305    if (CR.Lower.ult(Lower)) {
306      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;
318      return CR;
319    }
320
321    if (CR.Lower.ult(Lower))
322      return ConstantRange(Lower, CR.Upper);
323
324    return CR;
325  }
326  if (CR.Upper.ule(Lower)) {
327    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;
334  return CR;
335}
336
337
338/// unionWith - Return the range that results from the union of this range with
339/// another range.  The resultant range is guaranteed to include the elements of
340/// 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.
343///
344ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
345  assert(getBitWidth() == CR.getBitWidth() &&
346         "ConstantRange types don't agree!");
347
348  if (   isFullSet() || CR.isEmptySet()) return *this;
349  if (CR.isFullSet() ||    isEmptySet()) return CR;
350
351  if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
352
353  if (!isWrappedSet() && !CR.isWrappedSet()) {
354    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);
359      return ConstantRange(CR.Lower, Upper);
360    }
361
362    APInt L = Lower, U = Upper;
363    if (CR.Lower.ult(L))
364      L = CR.Lower;
365    if ((CR.Upper - 1).ugt(U - 1))
366      U = CR.Upper;
367
368    if (L == 0 && U == 0)
369      return ConstantRange(getBitWidth());
370
371    return ConstantRange(L, U);
372  }
373
374  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))
378      return *this;
379
380    // ------U   L----- : this
381    //    L---------U   : CR
382    if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
383      return ConstantRange(getBitWidth());
384
385    // ----U       L---- : this
386    //       L---U       : CR
387    //    <d1>  <d2>
388    if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
389      APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
390      if (d1.ult(d2))
391        return ConstantRange(Lower, CR.Upper);
392      return ConstantRange(CR.Lower, Upper);
393    }
394
395    // ----U     L----- : this
396    //        L----U    : CR
397    if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
398      return ConstantRange(CR.Lower, Upper);
399
400    // ------U    L---- : this
401    //    L-----U       : CR
402    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);
405  }
406
407  // ------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());
411
412  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;
417
418  return ConstantRange(L, U);
419}
420
421/// zeroExtend - Return a new range in the specified integer type, which must
422/// be strictly larger than the current type.  The returned range will
423/// correspond to the possible range of values as if the source range had been
424/// zero extended.
425ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
426  if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
427
428  unsigned SrcTySize = getBitWidth();
429  assert(SrcTySize < DstTySize && "Not a value extension");
430  if (isFullSet() || isWrappedSet()) {
431    // Change into [0, 1 << src bit width)
432    APInt LowerExt(DstTySize, 0);
433    if (!Upper) // special case: [X, 0) -- not really wrapping around
434      LowerExt = Lower.zext(DstTySize);
435    return ConstantRange(LowerExt, APInt(DstTySize, 1).shl(SrcTySize));
436  }
437
438  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
439}
440
441/// signExtend - Return a new range in the specified integer type, which must
442/// be strictly larger than the current type.  The returned range will
443/// correspond to the possible range of values as if the source range had been
444/// sign extended.
445ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
446  if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
447
448  unsigned SrcTySize = getBitWidth();
449  assert(SrcTySize < DstTySize && "Not a value extension");
450  if (isFullSet() || isSignWrappedSet()) {
451    return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
452                         APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
453  }
454
455  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
456}
457
458/// truncate - Return a new range in the specified integer type, which must be
459/// strictly smaller than the current type.  The returned range will
460/// correspond to the possible range of values as if the source range had been
461/// truncated to the specified type.
462ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
463  assert(getBitWidth() > DstTySize && "Not a value truncation");
464  if (isEmptySet())
465    return ConstantRange(DstTySize, /*isFullSet=*/false);
466  if (isFullSet())
467    return ConstantRange(DstTySize, /*isFullSet=*/true);
468
469  APInt MaxValue = APInt::getMaxValue(DstTySize).zext(getBitWidth());
470  APInt MaxBitValue(getBitWidth(), 0);
471  MaxBitValue.setBit(DstTySize);
472
473  APInt LowerDiv(Lower), UpperDiv(Upper);
474  ConstantRange Union(DstTySize, /*isFullSet=*/false);
475
476  // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
477  // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
478  // then we do the union with [MaxValue, Upper)
479  if (isWrappedSet()) {
480    // if Upper is greater than Max Value, it covers the whole truncated range.
481    if (Upper.uge(MaxValue))
482      return ConstantRange(DstTySize, /*isFullSet=*/true);
483
484    Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
485    UpperDiv = APInt::getMaxValue(getBitWidth());
486
487    // Union covers the MaxValue case, so return if the remaining range is just
488    // MaxValue.
489    if (LowerDiv == UpperDiv)
490      return Union;
491  }
492
493  // Chop off the most significant bits that are past the destination bitwidth.
494  if (LowerDiv.uge(MaxValue)) {
495    APInt Div(getBitWidth(), 0);
496    APInt::udivrem(LowerDiv, MaxBitValue, Div, LowerDiv);
497    UpperDiv = UpperDiv - MaxBitValue * Div;
498  }
499
500  if (UpperDiv.ule(MaxValue))
501    return ConstantRange(LowerDiv.trunc(DstTySize),
502                         UpperDiv.trunc(DstTySize)).unionWith(Union);
503
504  // The truncated value wrapps around. Check if we can do better than fullset.
505  APInt UpperModulo = UpperDiv - MaxBitValue;
506  if (UpperModulo.ult(LowerDiv))
507    return ConstantRange(LowerDiv.trunc(DstTySize),
508                         UpperModulo.trunc(DstTySize)).unionWith(Union);
509
510  return ConstantRange(DstTySize, /*isFullSet=*/true);
511}
512
513/// zextOrTrunc - make this range have the bit width given by \p DstTySize. The
514/// value is zero extended, truncated, or left alone to make it that width.
515ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
516  unsigned SrcTySize = getBitWidth();
517  if (SrcTySize > DstTySize)
518    return truncate(DstTySize);
519  if (SrcTySize < DstTySize)
520    return zeroExtend(DstTySize);
521  return *this;
522}
523
524/// sextOrTrunc - make this range have the bit width given by \p DstTySize. The
525/// value is sign extended, truncated, or left alone to make it that width.
526ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
527  unsigned SrcTySize = getBitWidth();
528  if (SrcTySize > DstTySize)
529    return truncate(DstTySize);
530  if (SrcTySize < DstTySize)
531    return signExtend(DstTySize);
532  return *this;
533}
534
535ConstantRange
536ConstantRange::add(const ConstantRange &Other) const {
537  if (isEmptySet() || Other.isEmptySet())
538    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
539  if (isFullSet() || Other.isFullSet())
540    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
541
542  APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
543  APInt NewLower = getLower() + Other.getLower();
544  APInt NewUpper = getUpper() + Other.getUpper() - 1;
545  if (NewLower == NewUpper)
546    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
547
548  ConstantRange X = ConstantRange(NewLower, NewUpper);
549  if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
550    // We've wrapped, therefore, full set.
551    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
552
553  return X;
554}
555
556ConstantRange
557ConstantRange::sub(const ConstantRange &Other) const {
558  if (isEmptySet() || Other.isEmptySet())
559    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
560  if (isFullSet() || Other.isFullSet())
561    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
562
563  APInt Spread_X = getSetSize(), Spread_Y = Other.getSetSize();
564  APInt NewLower = getLower() - Other.getUpper() + 1;
565  APInt NewUpper = getUpper() - Other.getLower();
566  if (NewLower == NewUpper)
567    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
568
569  ConstantRange X = ConstantRange(NewLower, NewUpper);
570  if (X.getSetSize().ult(Spread_X) || X.getSetSize().ult(Spread_Y))
571    // We've wrapped, therefore, full set.
572    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
573
574  return X;
575}
576
577ConstantRange
578ConstantRange::multiply(const ConstantRange &Other) const {
579  // TODO: If either operand is a single element and the multiply is known to
580  // be non-wrapping, round the result min and max value to the appropriate
581  // multiple of that element. If wrapping is possible, at least adjust the
582  // range according to the greatest power-of-two factor of the single element.
583
584  if (isEmptySet() || Other.isEmptySet())
585    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
586
587  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
588  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
589  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
590  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
591
592  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
593                                            this_max * Other_max + 1);
594  return Result_zext.truncate(getBitWidth());
595}
596
597ConstantRange
598ConstantRange::smax(const ConstantRange &Other) const {
599  // X smax Y is: range(smax(X_smin, Y_smin),
600  //                    smax(X_smax, Y_smax))
601  if (isEmptySet() || Other.isEmptySet())
602    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
603  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
604  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
605  if (NewU == NewL)
606    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
607  return ConstantRange(NewL, NewU);
608}
609
610ConstantRange
611ConstantRange::umax(const ConstantRange &Other) const {
612  // X umax Y is: range(umax(X_umin, Y_umin),
613  //                    umax(X_umax, Y_umax))
614  if (isEmptySet() || Other.isEmptySet())
615    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
616  APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
617  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
618  if (NewU == NewL)
619    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
620  return ConstantRange(NewL, NewU);
621}
622
623ConstantRange
624ConstantRange::udiv(const ConstantRange &RHS) const {
625  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax() == 0)
626    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
627  if (RHS.isFullSet())
628    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
629
630  APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
631
632  APInt RHS_umin = RHS.getUnsignedMin();
633  if (RHS_umin == 0) {
634    // We want the lowest value in RHS excluding zero. Usually that would be 1
635    // except for a range in the form of [X, 1) in which case it would be X.
636    if (RHS.getUpper() == 1)
637      RHS_umin = RHS.getLower();
638    else
639      RHS_umin = APInt(getBitWidth(), 1);
640  }
641
642  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
643
644  // If the LHS is Full and the RHS is a wrapped interval containing 1 then
645  // this could occur.
646  if (Lower == Upper)
647    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
648
649  return ConstantRange(Lower, Upper);
650}
651
652ConstantRange
653ConstantRange::binaryAnd(const ConstantRange &Other) const {
654  if (isEmptySet() || Other.isEmptySet())
655    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
656
657  // TODO: replace this with something less conservative
658
659  APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
660  if (umin.isAllOnesValue())
661    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
662  return ConstantRange(APInt::getNullValue(getBitWidth()), umin + 1);
663}
664
665ConstantRange
666ConstantRange::binaryOr(const ConstantRange &Other) const {
667  if (isEmptySet() || Other.isEmptySet())
668    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
669
670  // TODO: replace this with something less conservative
671
672  APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
673  if (umax.isMinValue())
674    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
675  return ConstantRange(umax, APInt::getNullValue(getBitWidth()));
676}
677
678ConstantRange
679ConstantRange::shl(const ConstantRange &Other) const {
680  if (isEmptySet() || Other.isEmptySet())
681    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
682
683  APInt min = getUnsignedMin().shl(Other.getUnsignedMin());
684  APInt max = getUnsignedMax().shl(Other.getUnsignedMax());
685
686  // there's no overflow!
687  APInt Zeros(getBitWidth(), getUnsignedMax().countLeadingZeros());
688  if (Zeros.ugt(Other.getUnsignedMax()))
689    return ConstantRange(min, max + 1);
690
691  // FIXME: implement the other tricky cases
692  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
693}
694
695ConstantRange
696ConstantRange::lshr(const ConstantRange &Other) const {
697  if (isEmptySet() || Other.isEmptySet())
698    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
699
700  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin());
701  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
702  if (min == max + 1)
703    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
704
705  return ConstantRange(min, max + 1);
706}
707
708ConstantRange ConstantRange::inverse() const {
709  if (isFullSet())
710    return ConstantRange(getBitWidth(), /*isFullSet=*/false);
711  if (isEmptySet())
712    return ConstantRange(getBitWidth(), /*isFullSet=*/true);
713  return ConstantRange(Upper, Lower);
714}
715
716/// print - Print out the bounds to a stream...
717///
718void ConstantRange::print(raw_ostream &OS) const {
719  if (isFullSet())
720    OS << "full-set";
721  else if (isEmptySet())
722    OS << "empty-set";
723  else
724    OS << "[" << Lower << "," << Upper << ")";
725}
726
727/// dump - Allow printing from a debugger easily...
728///
729void ConstantRange::dump() const {
730  print(dbgs());
731}
732