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/ADT/APInt.h"
25 #include "llvm/Config/llvm-config.h"
26 #include "llvm/IR/ConstantRange.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/InstrTypes.h"
29 #include "llvm/IR/Instruction.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/Operator.h"
32 #include "llvm/Support/Compiler.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/ErrorHandling.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include <algorithm>
37 #include <cassert>
38 #include <cstdint>
39 
40 using namespace llvm;
41 
42 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
43     : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
44       Upper(Lower) {}
45 
46 ConstantRange::ConstantRange(APInt V)
47     : Lower(std::move(V)), Upper(Lower + 1) {}
48 
49 ConstantRange::ConstantRange(APInt L, APInt U)
50     : Lower(std::move(L)), Upper(std::move(U)) {
51   assert(Lower.getBitWidth() == Upper.getBitWidth() &&
52          "ConstantRange with unequal bit widths");
53   assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
54          "Lower == Upper, but they aren't min or max value!");
55 }
56 
57 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
58                                                    const ConstantRange &CR) {
59   if (CR.isEmptySet())
60     return CR;
61 
62   uint32_t W = CR.getBitWidth();
63   switch (Pred) {
64   default:
65     llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
66   case CmpInst::ICMP_EQ:
67     return CR;
68   case CmpInst::ICMP_NE:
69     if (CR.isSingleElement())
70       return ConstantRange(CR.getUpper(), CR.getLower());
71     return ConstantRange(W);
72   case CmpInst::ICMP_ULT: {
73     APInt UMax(CR.getUnsignedMax());
74     if (UMax.isMinValue())
75       return ConstantRange(W, /* empty */ false);
76     return ConstantRange(APInt::getMinValue(W), std::move(UMax));
77   }
78   case CmpInst::ICMP_SLT: {
79     APInt SMax(CR.getSignedMax());
80     if (SMax.isMinSignedValue())
81       return ConstantRange(W, /* empty */ false);
82     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
83   }
84   case CmpInst::ICMP_ULE: {
85     APInt UMax(CR.getUnsignedMax());
86     if (UMax.isMaxValue())
87       return ConstantRange(W);
88     return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
89   }
90   case CmpInst::ICMP_SLE: {
91     APInt SMax(CR.getSignedMax());
92     if (SMax.isMaxSignedValue())
93       return ConstantRange(W);
94     return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
95   }
96   case CmpInst::ICMP_UGT: {
97     APInt UMin(CR.getUnsignedMin());
98     if (UMin.isMaxValue())
99       return ConstantRange(W, /* empty */ false);
100     return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
101   }
102   case CmpInst::ICMP_SGT: {
103     APInt SMin(CR.getSignedMin());
104     if (SMin.isMaxSignedValue())
105       return ConstantRange(W, /* empty */ false);
106     return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
107   }
108   case CmpInst::ICMP_UGE: {
109     APInt UMin(CR.getUnsignedMin());
110     if (UMin.isMinValue())
111       return ConstantRange(W);
112     return ConstantRange(std::move(UMin), APInt::getNullValue(W));
113   }
114   case CmpInst::ICMP_SGE: {
115     APInt SMin(CR.getSignedMin());
116     if (SMin.isMinSignedValue())
117       return ConstantRange(W);
118     return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
119   }
120   }
121 }
122 
123 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
124                                                       const ConstantRange &CR) {
125   // Follows from De-Morgan's laws:
126   //
127   // ~(~A union ~B) == A intersect B.
128   //
129   return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
130       .inverse();
131 }
132 
133 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
134                                                  const APInt &C) {
135   // Computes the exact range that is equal to both the constant ranges returned
136   // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
137   // when RHS is a singleton such as an APInt and so the assert is valid.
138   // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
139   // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
140   //
141   assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
142   return makeAllowedICmpRegion(Pred, C);
143 }
144 
145 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
146                                       APInt &RHS) const {
147   bool Success = false;
148 
149   if (isFullSet() || isEmptySet()) {
150     Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
151     RHS = APInt(getBitWidth(), 0);
152     Success = true;
153   } else if (auto *OnlyElt = getSingleElement()) {
154     Pred = CmpInst::ICMP_EQ;
155     RHS = *OnlyElt;
156     Success = true;
157   } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
158     Pred = CmpInst::ICMP_NE;
159     RHS = *OnlyMissingElt;
160     Success = true;
161   } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
162     Pred =
163         getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
164     RHS = getUpper();
165     Success = true;
166   } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
167     Pred =
168         getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
169     RHS = getLower();
170     Success = true;
171   }
172 
173   assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
174          "Bad result!");
175 
176   return Success;
177 }
178 
179 ConstantRange
180 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
181                                           const ConstantRange &Other,
182                                           unsigned NoWrapKind) {
183   using OBO = OverflowingBinaryOperator;
184 
185   // Computes the intersection of CR0 and CR1.  It is different from
186   // intersectWith in that the ConstantRange returned will only contain elements
187   // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
188   // not, of both X and Y).
189   auto SubsetIntersect =
190       [](const ConstantRange &CR0, const ConstantRange &CR1) {
191     return CR0.inverse().unionWith(CR1.inverse()).inverse();
192   };
193 
194   assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
195 
196   assert((NoWrapKind == OBO::NoSignedWrap ||
197           NoWrapKind == OBO::NoUnsignedWrap ||
198           NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
199          "NoWrapKind invalid!");
200 
201   unsigned BitWidth = Other.getBitWidth();
202   ConstantRange Result(BitWidth);
203 
204   switch (BinOp) {
205   default:
206     // Conservative answer: empty set
207     return ConstantRange(BitWidth, false);
208 
209   case Instruction::Add:
210     if (auto *C = Other.getSingleElement())
211       if (C->isNullValue())
212         // Full set: nothing signed / unsigned wraps when added to 0.
213         return ConstantRange(BitWidth);
214     if (NoWrapKind & OBO::NoUnsignedWrap)
215       Result =
216           SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
217                                                 -Other.getUnsignedMax()));
218     if (NoWrapKind & OBO::NoSignedWrap) {
219       const APInt &SignedMin = Other.getSignedMin();
220       const APInt &SignedMax = Other.getSignedMax();
221       if (SignedMax.isStrictlyPositive())
222         Result = SubsetIntersect(
223             Result,
224             ConstantRange(APInt::getSignedMinValue(BitWidth),
225                           APInt::getSignedMinValue(BitWidth) - SignedMax));
226       if (SignedMin.isNegative())
227         Result = SubsetIntersect(
228             Result,
229             ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
230                           APInt::getSignedMinValue(BitWidth)));
231     }
232     return Result;
233 
234   case Instruction::Sub:
235     if (auto *C = Other.getSingleElement())
236       if (C->isNullValue())
237         // Full set: nothing signed / unsigned wraps when subtracting 0.
238         return ConstantRange(BitWidth);
239     if (NoWrapKind & OBO::NoUnsignedWrap)
240       Result =
241           SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(),
242                                                 APInt::getMinValue(BitWidth)));
243     if (NoWrapKind & OBO::NoSignedWrap) {
244       const APInt &SignedMin = Other.getSignedMin();
245       const APInt &SignedMax = Other.getSignedMax();
246       if (SignedMax.isStrictlyPositive())
247         Result = SubsetIntersect(
248             Result,
249             ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax,
250                           APInt::getSignedMinValue(BitWidth)));
251       if (SignedMin.isNegative())
252         Result = SubsetIntersect(
253             Result,
254             ConstantRange(APInt::getSignedMinValue(BitWidth),
255                           APInt::getSignedMinValue(BitWidth) + SignedMin));
256     }
257     return Result;
258   case Instruction::Mul: {
259     if (NoWrapKind == (OBO::NoSignedWrap | OBO::NoUnsignedWrap)) {
260       return SubsetIntersect(
261           makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoSignedWrap),
262           makeGuaranteedNoWrapRegion(BinOp, Other, OBO::NoUnsignedWrap));
263     }
264 
265     // Equivalent to calling makeGuaranteedNoWrapRegion() on [V, V+1).
266     const bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
267     const auto makeSingleValueRegion = [Unsigned,
268                                         BitWidth](APInt V) -> ConstantRange {
269       // Handle special case for 0, -1 and 1. See the last for reason why we
270       // specialize -1 and 1.
271       if (V == 0 || V.isOneValue())
272         return ConstantRange(BitWidth, true);
273 
274       APInt MinValue, MaxValue;
275       if (Unsigned) {
276         MinValue = APInt::getMinValue(BitWidth);
277         MaxValue = APInt::getMaxValue(BitWidth);
278       } else {
279         MinValue = APInt::getSignedMinValue(BitWidth);
280         MaxValue = APInt::getSignedMaxValue(BitWidth);
281       }
282       // e.g. Returning [-127, 127], represented as [-127, -128).
283       if (!Unsigned && V.isAllOnesValue())
284         return ConstantRange(-MaxValue, MinValue);
285 
286       APInt Lower, Upper;
287       if (!Unsigned && V.isNegative()) {
288         Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP);
289         Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN);
290       } else if (Unsigned) {
291         Lower = APIntOps::RoundingUDiv(MinValue, V, APInt::Rounding::UP);
292         Upper = APIntOps::RoundingUDiv(MaxValue, V, APInt::Rounding::DOWN);
293       } else {
294         Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP);
295         Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN);
296       }
297       if (Unsigned) {
298         Lower = Lower.zextOrSelf(BitWidth);
299         Upper = Upper.zextOrSelf(BitWidth);
300       } else {
301         Lower = Lower.sextOrSelf(BitWidth);
302         Upper = Upper.sextOrSelf(BitWidth);
303       }
304       // ConstantRange ctor take a half inclusive interval [Lower, Upper + 1).
305       // Upper + 1 is guanranteed not to overflow, because |divisor| > 1. 0, -1,
306       // and 1 are already handled as special cases.
307       return ConstantRange(Lower, Upper + 1);
308     };
309 
310     if (Unsigned)
311       return makeSingleValueRegion(Other.getUnsignedMax());
312 
313     return SubsetIntersect(makeSingleValueRegion(Other.getSignedMin()),
314                            makeSingleValueRegion(Other.getSignedMax()));
315   }
316   }
317 }
318 
319 bool ConstantRange::isFullSet() const {
320   return Lower == Upper && Lower.isMaxValue();
321 }
322 
323 bool ConstantRange::isEmptySet() const {
324   return Lower == Upper && Lower.isMinValue();
325 }
326 
327 bool ConstantRange::isWrappedSet() const {
328   return Lower.ugt(Upper);
329 }
330 
331 bool ConstantRange::isSignWrappedSet() const {
332   return contains(APInt::getSignedMaxValue(getBitWidth())) &&
333          contains(APInt::getSignedMinValue(getBitWidth()));
334 }
335 
336 APInt ConstantRange::getSetSize() const {
337   if (isFullSet())
338     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
339 
340   // This is also correct for wrapped sets.
341   return (Upper - Lower).zext(getBitWidth()+1);
342 }
343 
344 bool
345 ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
346   assert(getBitWidth() == Other.getBitWidth());
347   if (isFullSet())
348     return false;
349   if (Other.isFullSet())
350     return true;
351   return (Upper - Lower).ult(Other.Upper - Other.Lower);
352 }
353 
354 bool
355 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
356   assert(MaxSize && "MaxSize can't be 0.");
357   // If this a full set, we need special handling to avoid needing an extra bit
358   // to represent the size.
359   if (isFullSet())
360     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
361 
362   return (Upper - Lower).ugt(MaxSize);
363 }
364 
365 APInt ConstantRange::getUnsignedMax() const {
366   if (isFullSet() || isWrappedSet())
367     return APInt::getMaxValue(getBitWidth());
368   return getUpper() - 1;
369 }
370 
371 APInt ConstantRange::getUnsignedMin() const {
372   if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
373     return APInt::getMinValue(getBitWidth());
374   return getLower();
375 }
376 
377 APInt ConstantRange::getSignedMax() const {
378   if (isFullSet() || Lower.sgt(Upper))
379     return APInt::getSignedMaxValue(getBitWidth());
380   return getUpper() - 1;
381 }
382 
383 APInt ConstantRange::getSignedMin() const {
384   if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
385     return APInt::getSignedMinValue(getBitWidth());
386   return getLower();
387 }
388 
389 bool ConstantRange::contains(const APInt &V) const {
390   if (Lower == Upper)
391     return isFullSet();
392 
393   if (!isWrappedSet())
394     return Lower.ule(V) && V.ult(Upper);
395   return Lower.ule(V) || V.ult(Upper);
396 }
397 
398 bool ConstantRange::contains(const ConstantRange &Other) const {
399   if (isFullSet() || Other.isEmptySet()) return true;
400   if (isEmptySet() || Other.isFullSet()) return false;
401 
402   if (!isWrappedSet()) {
403     if (Other.isWrappedSet())
404       return false;
405 
406     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
407   }
408 
409   if (!Other.isWrappedSet())
410     return Other.getUpper().ule(Upper) ||
411            Lower.ule(Other.getLower());
412 
413   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
414 }
415 
416 ConstantRange ConstantRange::subtract(const APInt &Val) const {
417   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
418   // If the set is empty or full, don't modify the endpoints.
419   if (Lower == Upper)
420     return *this;
421   return ConstantRange(Lower - Val, Upper - Val);
422 }
423 
424 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
425   return intersectWith(CR.inverse());
426 }
427 
428 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
429   assert(getBitWidth() == CR.getBitWidth() &&
430          "ConstantRange types don't agree!");
431 
432   // Handle common cases.
433   if (   isEmptySet() || CR.isFullSet()) return *this;
434   if (CR.isEmptySet() ||    isFullSet()) return CR;
435 
436   if (!isWrappedSet() && CR.isWrappedSet())
437     return CR.intersectWith(*this);
438 
439   if (!isWrappedSet() && !CR.isWrappedSet()) {
440     if (Lower.ult(CR.Lower)) {
441       if (Upper.ule(CR.Lower))
442         return ConstantRange(getBitWidth(), false);
443 
444       if (Upper.ult(CR.Upper))
445         return ConstantRange(CR.Lower, Upper);
446 
447       return CR;
448     }
449     if (Upper.ult(CR.Upper))
450       return *this;
451 
452     if (Lower.ult(CR.Upper))
453       return ConstantRange(Lower, CR.Upper);
454 
455     return ConstantRange(getBitWidth(), false);
456   }
457 
458   if (isWrappedSet() && !CR.isWrappedSet()) {
459     if (CR.Lower.ult(Upper)) {
460       if (CR.Upper.ult(Upper))
461         return CR;
462 
463       if (CR.Upper.ule(Lower))
464         return ConstantRange(CR.Lower, Upper);
465 
466       if (isSizeStrictlySmallerThan(CR))
467         return *this;
468       return CR;
469     }
470     if (CR.Lower.ult(Lower)) {
471       if (CR.Upper.ule(Lower))
472         return ConstantRange(getBitWidth(), false);
473 
474       return ConstantRange(Lower, CR.Upper);
475     }
476     return CR;
477   }
478 
479   if (CR.Upper.ult(Upper)) {
480     if (CR.Lower.ult(Upper)) {
481       if (isSizeStrictlySmallerThan(CR))
482         return *this;
483       return CR;
484     }
485 
486     if (CR.Lower.ult(Lower))
487       return ConstantRange(Lower, CR.Upper);
488 
489     return CR;
490   }
491   if (CR.Upper.ule(Lower)) {
492     if (CR.Lower.ult(Lower))
493       return *this;
494 
495     return ConstantRange(CR.Lower, Upper);
496   }
497   if (isSizeStrictlySmallerThan(CR))
498     return *this;
499   return CR;
500 }
501 
502 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
503   assert(getBitWidth() == CR.getBitWidth() &&
504          "ConstantRange types don't agree!");
505 
506   if (   isFullSet() || CR.isEmptySet()) return *this;
507   if (CR.isFullSet() ||    isEmptySet()) return CR;
508 
509   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
510 
511   if (!isWrappedSet() && !CR.isWrappedSet()) {
512     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
513       // If the two ranges are disjoint, find the smaller gap and bridge it.
514       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
515       if (d1.ult(d2))
516         return ConstantRange(Lower, CR.Upper);
517       return ConstantRange(CR.Lower, Upper);
518     }
519 
520     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
521     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
522 
523     if (L.isNullValue() && U.isNullValue())
524       return ConstantRange(getBitWidth());
525 
526     return ConstantRange(std::move(L), std::move(U));
527   }
528 
529   if (!CR.isWrappedSet()) {
530     // ------U   L-----  and  ------U   L----- : this
531     //   L--U                            L--U  : CR
532     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
533       return *this;
534 
535     // ------U   L----- : this
536     //    L---------U   : CR
537     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
538       return ConstantRange(getBitWidth());
539 
540     // ----U       L---- : this
541     //       L---U       : CR
542     //    <d1>  <d2>
543     if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
544       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
545       if (d1.ult(d2))
546         return ConstantRange(Lower, CR.Upper);
547       return ConstantRange(CR.Lower, Upper);
548     }
549 
550     // ----U     L----- : this
551     //        L----U    : CR
552     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
553       return ConstantRange(CR.Lower, Upper);
554 
555     // ------U    L---- : this
556     //    L-----U       : CR
557     assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
558            "ConstantRange::unionWith missed a case with one range wrapped");
559     return ConstantRange(Lower, CR.Upper);
560   }
561 
562   // ------U    L----  and  ------U    L---- : this
563   // -U  L-----------  and  ------------U  L : CR
564   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
565     return ConstantRange(getBitWidth());
566 
567   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
568   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
569 
570   return ConstantRange(std::move(L), std::move(U));
571 }
572 
573 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
574                                     uint32_t ResultBitWidth) const {
575   switch (CastOp) {
576   default:
577     llvm_unreachable("unsupported cast type");
578   case Instruction::Trunc:
579     return truncate(ResultBitWidth);
580   case Instruction::SExt:
581     return signExtend(ResultBitWidth);
582   case Instruction::ZExt:
583     return zeroExtend(ResultBitWidth);
584   case Instruction::BitCast:
585     return *this;
586   case Instruction::FPToUI:
587   case Instruction::FPToSI:
588     if (getBitWidth() == ResultBitWidth)
589       return *this;
590     else
591       return ConstantRange(getBitWidth(), /*isFullSet=*/true);
592   case Instruction::UIToFP: {
593     // TODO: use input range if available
594     auto BW = getBitWidth();
595     APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
596     APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
597     return ConstantRange(std::move(Min), std::move(Max));
598   }
599   case Instruction::SIToFP: {
600     // TODO: use input range if available
601     auto BW = getBitWidth();
602     APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
603     APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
604     return ConstantRange(std::move(SMin), std::move(SMax));
605   }
606   case Instruction::FPTrunc:
607   case Instruction::FPExt:
608   case Instruction::IntToPtr:
609   case Instruction::PtrToInt:
610   case Instruction::AddrSpaceCast:
611     // Conservatively return full set.
612     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
613   };
614 }
615 
616 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
617   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
618 
619   unsigned SrcTySize = getBitWidth();
620   assert(SrcTySize < DstTySize && "Not a value extension");
621   if (isFullSet() || isWrappedSet()) {
622     // Change into [0, 1 << src bit width)
623     APInt LowerExt(DstTySize, 0);
624     if (!Upper) // special case: [X, 0) -- not really wrapping around
625       LowerExt = Lower.zext(DstTySize);
626     return ConstantRange(std::move(LowerExt),
627                          APInt::getOneBitSet(DstTySize, SrcTySize));
628   }
629 
630   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
631 }
632 
633 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
634   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
635 
636   unsigned SrcTySize = getBitWidth();
637   assert(SrcTySize < DstTySize && "Not a value extension");
638 
639   // special case: [X, INT_MIN) -- not really wrapping around
640   if (Upper.isMinSignedValue())
641     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
642 
643   if (isFullSet() || isSignWrappedSet()) {
644     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
645                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
646   }
647 
648   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
649 }
650 
651 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
652   assert(getBitWidth() > DstTySize && "Not a value truncation");
653   if (isEmptySet())
654     return ConstantRange(DstTySize, /*isFullSet=*/false);
655   if (isFullSet())
656     return ConstantRange(DstTySize, /*isFullSet=*/true);
657 
658   APInt LowerDiv(Lower), UpperDiv(Upper);
659   ConstantRange Union(DstTySize, /*isFullSet=*/false);
660 
661   // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
662   // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
663   // then we do the union with [MaxValue, Upper)
664   if (isWrappedSet()) {
665     // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
666     // truncated range.
667     if (Upper.getActiveBits() > DstTySize ||
668         Upper.countTrailingOnes() == DstTySize)
669       return ConstantRange(DstTySize, /*isFullSet=*/true);
670 
671     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
672     UpperDiv.setAllBits();
673 
674     // Union covers the MaxValue case, so return if the remaining range is just
675     // MaxValue(DstTy).
676     if (LowerDiv == UpperDiv)
677       return Union;
678   }
679 
680   // Chop off the most significant bits that are past the destination bitwidth.
681   if (LowerDiv.getActiveBits() > DstTySize) {
682     // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
683     APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
684     LowerDiv -= Adjust;
685     UpperDiv -= Adjust;
686   }
687 
688   unsigned UpperDivWidth = UpperDiv.getActiveBits();
689   if (UpperDivWidth <= DstTySize)
690     return ConstantRange(LowerDiv.trunc(DstTySize),
691                          UpperDiv.trunc(DstTySize)).unionWith(Union);
692 
693   // The truncated value wraps around. Check if we can do better than fullset.
694   if (UpperDivWidth == DstTySize + 1) {
695     // Clear the MSB so that UpperDiv wraps around.
696     UpperDiv.clearBit(DstTySize);
697     if (UpperDiv.ult(LowerDiv))
698       return ConstantRange(LowerDiv.trunc(DstTySize),
699                            UpperDiv.trunc(DstTySize)).unionWith(Union);
700   }
701 
702   return ConstantRange(DstTySize, /*isFullSet=*/true);
703 }
704 
705 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
706   unsigned SrcTySize = getBitWidth();
707   if (SrcTySize > DstTySize)
708     return truncate(DstTySize);
709   if (SrcTySize < DstTySize)
710     return zeroExtend(DstTySize);
711   return *this;
712 }
713 
714 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
715   unsigned SrcTySize = getBitWidth();
716   if (SrcTySize > DstTySize)
717     return truncate(DstTySize);
718   if (SrcTySize < DstTySize)
719     return signExtend(DstTySize);
720   return *this;
721 }
722 
723 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
724                                       const ConstantRange &Other) const {
725   assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
726 
727   switch (BinOp) {
728   case Instruction::Add:
729     return add(Other);
730   case Instruction::Sub:
731     return sub(Other);
732   case Instruction::Mul:
733     return multiply(Other);
734   case Instruction::UDiv:
735     return udiv(Other);
736   case Instruction::Shl:
737     return shl(Other);
738   case Instruction::LShr:
739     return lshr(Other);
740   case Instruction::AShr:
741     return ashr(Other);
742   case Instruction::And:
743     return binaryAnd(Other);
744   case Instruction::Or:
745     return binaryOr(Other);
746   // Note: floating point operations applied to abstract ranges are just
747   // ideal integer operations with a lossy representation
748   case Instruction::FAdd:
749     return add(Other);
750   case Instruction::FSub:
751     return sub(Other);
752   case Instruction::FMul:
753     return multiply(Other);
754   default:
755     // Conservatively return full set.
756     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
757   }
758 }
759 
760 ConstantRange
761 ConstantRange::add(const ConstantRange &Other) const {
762   if (isEmptySet() || Other.isEmptySet())
763     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
764   if (isFullSet() || Other.isFullSet())
765     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
766 
767   APInt NewLower = getLower() + Other.getLower();
768   APInt NewUpper = getUpper() + Other.getUpper() - 1;
769   if (NewLower == NewUpper)
770     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
771 
772   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
773   if (X.isSizeStrictlySmallerThan(*this) ||
774       X.isSizeStrictlySmallerThan(Other))
775     // We've wrapped, therefore, full set.
776     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
777   return X;
778 }
779 
780 ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
781   // Calculate the subset of this range such that "X + Other" is
782   // guaranteed not to wrap (overflow) for all X in this subset.
783   // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
784   // passing a single element range.
785   auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
786                                       ConstantRange(Other),
787                                       OverflowingBinaryOperator::NoSignedWrap);
788   auto NSWConstrainedRange = intersectWith(NSWRange);
789 
790   return NSWConstrainedRange.add(ConstantRange(Other));
791 }
792 
793 ConstantRange
794 ConstantRange::sub(const ConstantRange &Other) const {
795   if (isEmptySet() || Other.isEmptySet())
796     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
797   if (isFullSet() || Other.isFullSet())
798     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
799 
800   APInt NewLower = getLower() - Other.getUpper() + 1;
801   APInt NewUpper = getUpper() - Other.getLower();
802   if (NewLower == NewUpper)
803     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
804 
805   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
806   if (X.isSizeStrictlySmallerThan(*this) ||
807       X.isSizeStrictlySmallerThan(Other))
808     // We've wrapped, therefore, full set.
809     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
810   return X;
811 }
812 
813 ConstantRange
814 ConstantRange::multiply(const ConstantRange &Other) const {
815   // TODO: If either operand is a single element and the multiply is known to
816   // be non-wrapping, round the result min and max value to the appropriate
817   // multiple of that element. If wrapping is possible, at least adjust the
818   // range according to the greatest power-of-two factor of the single element.
819 
820   if (isEmptySet() || Other.isEmptySet())
821     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
822 
823   // Multiplication is signedness-independent. However different ranges can be
824   // obtained depending on how the input ranges are treated. These different
825   // ranges are all conservatively correct, but one might be better than the
826   // other. We calculate two ranges; one treating the inputs as unsigned
827   // and the other signed, then return the smallest of these ranges.
828 
829   // Unsigned range first.
830   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
831   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
832   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
833   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
834 
835   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
836                                             this_max * Other_max + 1);
837   ConstantRange UR = Result_zext.truncate(getBitWidth());
838 
839   // If the unsigned range doesn't wrap, and isn't negative then it's a range
840   // from one positive number to another which is as good as we can generate.
841   // In this case, skip the extra work of generating signed ranges which aren't
842   // going to be better than this range.
843   if (!UR.isWrappedSet() &&
844       (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
845     return UR;
846 
847   // Now the signed range. Because we could be dealing with negative numbers
848   // here, the lower bound is the smallest of the cartesian product of the
849   // lower and upper ranges; for example:
850   //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
851   // Similarly for the upper bound, swapping min for max.
852 
853   this_min = getSignedMin().sext(getBitWidth() * 2);
854   this_max = getSignedMax().sext(getBitWidth() * 2);
855   Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
856   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
857 
858   auto L = {this_min * Other_min, this_min * Other_max,
859             this_max * Other_min, this_max * Other_max};
860   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
861   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
862   ConstantRange SR = Result_sext.truncate(getBitWidth());
863 
864   return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
865 }
866 
867 ConstantRange
868 ConstantRange::smax(const ConstantRange &Other) const {
869   // X smax Y is: range(smax(X_smin, Y_smin),
870   //                    smax(X_smax, Y_smax))
871   if (isEmptySet() || Other.isEmptySet())
872     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
873   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
874   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
875   if (NewU == NewL)
876     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
877   return ConstantRange(std::move(NewL), std::move(NewU));
878 }
879 
880 ConstantRange
881 ConstantRange::umax(const ConstantRange &Other) const {
882   // X umax Y is: range(umax(X_umin, Y_umin),
883   //                    umax(X_umax, Y_umax))
884   if (isEmptySet() || Other.isEmptySet())
885     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
886   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
887   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
888   if (NewU == NewL)
889     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
890   return ConstantRange(std::move(NewL), std::move(NewU));
891 }
892 
893 ConstantRange
894 ConstantRange::smin(const ConstantRange &Other) const {
895   // X smin Y is: range(smin(X_smin, Y_smin),
896   //                    smin(X_smax, Y_smax))
897   if (isEmptySet() || Other.isEmptySet())
898     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
899   APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
900   APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
901   if (NewU == NewL)
902     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
903   return ConstantRange(std::move(NewL), std::move(NewU));
904 }
905 
906 ConstantRange
907 ConstantRange::umin(const ConstantRange &Other) const {
908   // X umin Y is: range(umin(X_umin, Y_umin),
909   //                    umin(X_umax, Y_umax))
910   if (isEmptySet() || Other.isEmptySet())
911     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
912   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
913   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
914   if (NewU == NewL)
915     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
916   return ConstantRange(std::move(NewL), std::move(NewU));
917 }
918 
919 ConstantRange
920 ConstantRange::udiv(const ConstantRange &RHS) const {
921   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
922     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
923   if (RHS.isFullSet())
924     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
925 
926   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
927 
928   APInt RHS_umin = RHS.getUnsignedMin();
929   if (RHS_umin.isNullValue()) {
930     // We want the lowest value in RHS excluding zero. Usually that would be 1
931     // except for a range in the form of [X, 1) in which case it would be X.
932     if (RHS.getUpper() == 1)
933       RHS_umin = RHS.getLower();
934     else
935       RHS_umin = 1;
936   }
937 
938   APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
939 
940   // If the LHS is Full and the RHS is a wrapped interval containing 1 then
941   // this could occur.
942   if (Lower == Upper)
943     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
944 
945   return ConstantRange(std::move(Lower), std::move(Upper));
946 }
947 
948 ConstantRange
949 ConstantRange::binaryAnd(const ConstantRange &Other) const {
950   if (isEmptySet() || Other.isEmptySet())
951     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
952 
953   // TODO: replace this with something less conservative
954 
955   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
956   if (umin.isAllOnesValue())
957     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
958   return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
959 }
960 
961 ConstantRange
962 ConstantRange::binaryOr(const ConstantRange &Other) const {
963   if (isEmptySet() || Other.isEmptySet())
964     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
965 
966   // TODO: replace this with something less conservative
967 
968   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
969   if (umax.isNullValue())
970     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
971   return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
972 }
973 
974 ConstantRange
975 ConstantRange::shl(const ConstantRange &Other) const {
976   if (isEmptySet() || Other.isEmptySet())
977     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
978 
979   APInt max = getUnsignedMax();
980   APInt Other_umax = Other.getUnsignedMax();
981 
982   // there's overflow!
983   if (Other_umax.uge(max.countLeadingZeros()))
984     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
985 
986   // FIXME: implement the other tricky cases
987 
988   APInt min = getUnsignedMin();
989   min <<= Other.getUnsignedMin();
990   max <<= Other_umax;
991 
992   return ConstantRange(std::move(min), std::move(max) + 1);
993 }
994 
995 ConstantRange
996 ConstantRange::lshr(const ConstantRange &Other) const {
997   if (isEmptySet() || Other.isEmptySet())
998     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
999 
1000   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1001   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1002   if (min == max)
1003     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1004 
1005   return ConstantRange(std::move(min), std::move(max));
1006 }
1007 
1008 ConstantRange
1009 ConstantRange::ashr(const ConstantRange &Other) const {
1010   if (isEmptySet() || Other.isEmptySet())
1011     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
1012 
1013   // May straddle zero, so handle both positive and negative cases.
1014   // 'PosMax' is the upper bound of the result of the ashr
1015   // operation, when Upper of the LHS of ashr is a non-negative.
1016   // number. Since ashr of a non-negative number will result in a
1017   // smaller number, the Upper value of LHS is shifted right with
1018   // the minimum value of 'Other' instead of the maximum value.
1019   APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1020 
1021   // 'PosMin' is the lower bound of the result of the ashr
1022   // operation, when Lower of the LHS is a non-negative number.
1023   // Since ashr of a non-negative number will result in a smaller
1024   // number, the Lower value of LHS is shifted right with the
1025   // maximum value of 'Other'.
1026   APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1027 
1028   // 'NegMax' is the upper bound of the result of the ashr
1029   // operation, when Upper of the LHS of ashr is a negative number.
1030   // Since 'ashr' of a negative number will result in a bigger
1031   // number, the Upper value of LHS is shifted right with the
1032   // maximum value of 'Other'.
1033   APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1034 
1035   // 'NegMin' is the lower bound of the result of the ashr
1036   // operation, when Lower of the LHS of ashr is a negative number.
1037   // Since 'ashr' of a negative number will result in a bigger
1038   // number, the Lower value of LHS is shifted right with the
1039   // minimum value of 'Other'.
1040   APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1041 
1042   APInt max, min;
1043   if (getSignedMin().isNonNegative()) {
1044     // Upper and Lower of LHS are non-negative.
1045     min = PosMin;
1046     max = PosMax;
1047   } else if (getSignedMax().isNegative()) {
1048     // Upper and Lower of LHS are negative.
1049     min = NegMin;
1050     max = NegMax;
1051   } else {
1052     // Upper is non-negative and Lower is negative.
1053     min = NegMin;
1054     max = PosMax;
1055   }
1056   if (min == max)
1057     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1058 
1059   return ConstantRange(std::move(min), std::move(max));
1060 }
1061 
1062 ConstantRange ConstantRange::inverse() const {
1063   if (isFullSet())
1064     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
1065   if (isEmptySet())
1066     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1067   return ConstantRange(Upper, Lower);
1068 }
1069 
1070 void ConstantRange::print(raw_ostream &OS) const {
1071   if (isFullSet())
1072     OS << "full-set";
1073   else if (isEmptySet())
1074     OS << "empty-set";
1075   else
1076     OS << "[" << Lower << "," << Upper << ")";
1077 }
1078 
1079 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1080 LLVM_DUMP_METHOD void ConstantRange::dump() const {
1081   print(dbgs());
1082 }
1083 #endif
1084 
1085 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
1086   const unsigned NumRanges = Ranges.getNumOperands() / 2;
1087   assert(NumRanges >= 1 && "Must have at least one range!");
1088   assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1089 
1090   auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1091   auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1092 
1093   ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1094 
1095   for (unsigned i = 1; i < NumRanges; ++i) {
1096     auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1097     auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1098 
1099     // Note: unionWith will potentially create a range that contains values not
1100     // contained in any of the original N ranges.
1101     CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1102   }
1103 
1104   return CR;
1105 }
1106