• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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"
28 using namespace llvm;
29 
30 /// Initialize a full (the default) or empty set for the specified type.
31 ///
ConstantRange(uint32_t BitWidth,bool Full)32 ConstantRange::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 ///
ConstantRange(APIntMoveTy V)41 ConstantRange::ConstantRange(APIntMoveTy V)
42     : Lower(llvm_move(V)), Upper(Lower + 1) {}
43 
ConstantRange(APIntMoveTy L,APIntMoveTy U)44 ConstantRange::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 
makeICmpRegion(unsigned Pred,const ConstantRange & CR)52 ConstantRange 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
isFullSet() const119 bool ConstantRange::isFullSet() const {
120   return Lower == Upper && Lower.isMaxValue();
121 }
122 
123 /// isEmptySet - Return true if this set contains no members.
124 ///
isEmptySet() const125 bool 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 ///
isWrappedSet() const132 bool 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 ///
isSignWrappedSet() const139 bool 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 ///
getSetSize() const146 APInt 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 ///
getUnsignedMax() const163 APInt 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 ///
getUnsignedMin() const172 APInt 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 ///
getSignedMax() const181 APInt 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 ///
getSignedMin() const196 APInt 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 ///
contains(const APInt & V) const212 bool 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 ///
contains(const ConstantRange & Other) const225 bool 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.
subtract(const APInt & Val) const245 ConstantRange 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).
difference(const ConstantRange & CR) const255 ConstantRange 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).
intersectWith(const ConstantRange & CR) const264 ConstantRange 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 ///
unionWith(const ConstantRange & CR) const345 ConstantRange 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.
zeroExtend(uint32_t DstTySize) const426 ConstantRange 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.
signExtend(uint32_t DstTySize) const446 ConstantRange 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.
truncate(uint32_t DstTySize) const463 ConstantRange 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.
zextOrTrunc(uint32_t DstTySize) const516 ConstantRange 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.
sextOrTrunc(uint32_t DstTySize) const527 ConstantRange 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 
536 ConstantRange
add(const ConstantRange & Other) const537 ConstantRange::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 
557 ConstantRange
sub(const ConstantRange & Other) const558 ConstantRange::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 
578 ConstantRange
multiply(const ConstantRange & Other) const579 ConstantRange::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 
598 ConstantRange
smax(const ConstantRange & Other) const599 ConstantRange::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 
611 ConstantRange
umax(const ConstantRange & Other) const612 ConstantRange::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 
624 ConstantRange
udiv(const ConstantRange & RHS) const625 ConstantRange::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 
653 ConstantRange
binaryAnd(const ConstantRange & Other) const654 ConstantRange::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 
666 ConstantRange
binaryOr(const ConstantRange & Other) const667 ConstantRange::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 
679 ConstantRange
shl(const ConstantRange & Other) const680 ConstantRange::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 
696 ConstantRange
lshr(const ConstantRange & Other) const697 ConstantRange::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 
inverse() const709 ConstantRange 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 ///
print(raw_ostream & OS) const719 void 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 ///
dump() const730 void ConstantRange::dump() const {
731   print(dbgs());
732 }
733