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