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/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(BinOp >= Instruction::BinaryOpsBegin &&
194          BinOp < Instruction::BinaryOpsEnd && "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   }
259 }
260 
261 bool ConstantRange::isFullSet() const {
262   return Lower == Upper && Lower.isMaxValue();
263 }
264 
265 bool ConstantRange::isEmptySet() const {
266   return Lower == Upper && Lower.isMinValue();
267 }
268 
269 bool ConstantRange::isWrappedSet() const {
270   return Lower.ugt(Upper);
271 }
272 
273 bool ConstantRange::isSignWrappedSet() const {
274   return contains(APInt::getSignedMaxValue(getBitWidth())) &&
275          contains(APInt::getSignedMinValue(getBitWidth()));
276 }
277 
278 APInt ConstantRange::getSetSize() const {
279   if (isFullSet())
280     return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
281 
282   // This is also correct for wrapped sets.
283   return (Upper - Lower).zext(getBitWidth()+1);
284 }
285 
286 bool
287 ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
288   assert(getBitWidth() == Other.getBitWidth());
289   if (isFullSet())
290     return false;
291   if (Other.isFullSet())
292     return true;
293   return (Upper - Lower).ult(Other.Upper - Other.Lower);
294 }
295 
296 bool
297 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
298   assert(MaxSize && "MaxSize can't be 0.");
299   // If this a full set, we need special handling to avoid needing an extra bit
300   // to represent the size.
301   if (isFullSet())
302     return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
303 
304   return (Upper - Lower).ugt(MaxSize);
305 }
306 
307 APInt ConstantRange::getUnsignedMax() const {
308   if (isFullSet() || isWrappedSet())
309     return APInt::getMaxValue(getBitWidth());
310   return getUpper() - 1;
311 }
312 
313 APInt ConstantRange::getUnsignedMin() const {
314   if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
315     return APInt::getMinValue(getBitWidth());
316   return getLower();
317 }
318 
319 APInt ConstantRange::getSignedMax() const {
320   if (isFullSet() || Lower.sgt(Upper))
321     return APInt::getSignedMaxValue(getBitWidth());
322   return getUpper() - 1;
323 }
324 
325 APInt ConstantRange::getSignedMin() const {
326   if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
327     return APInt::getSignedMinValue(getBitWidth());
328   return getLower();
329 }
330 
331 bool ConstantRange::contains(const APInt &V) const {
332   if (Lower == Upper)
333     return isFullSet();
334 
335   if (!isWrappedSet())
336     return Lower.ule(V) && V.ult(Upper);
337   return Lower.ule(V) || V.ult(Upper);
338 }
339 
340 bool ConstantRange::contains(const ConstantRange &Other) const {
341   if (isFullSet() || Other.isEmptySet()) return true;
342   if (isEmptySet() || Other.isFullSet()) return false;
343 
344   if (!isWrappedSet()) {
345     if (Other.isWrappedSet())
346       return false;
347 
348     return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
349   }
350 
351   if (!Other.isWrappedSet())
352     return Other.getUpper().ule(Upper) ||
353            Lower.ule(Other.getLower());
354 
355   return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
356 }
357 
358 ConstantRange ConstantRange::subtract(const APInt &Val) const {
359   assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
360   // If the set is empty or full, don't modify the endpoints.
361   if (Lower == Upper)
362     return *this;
363   return ConstantRange(Lower - Val, Upper - Val);
364 }
365 
366 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
367   return intersectWith(CR.inverse());
368 }
369 
370 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
371   assert(getBitWidth() == CR.getBitWidth() &&
372          "ConstantRange types don't agree!");
373 
374   // Handle common cases.
375   if (   isEmptySet() || CR.isFullSet()) return *this;
376   if (CR.isEmptySet() ||    isFullSet()) return CR;
377 
378   if (!isWrappedSet() && CR.isWrappedSet())
379     return CR.intersectWith(*this);
380 
381   if (!isWrappedSet() && !CR.isWrappedSet()) {
382     if (Lower.ult(CR.Lower)) {
383       if (Upper.ule(CR.Lower))
384         return ConstantRange(getBitWidth(), false);
385 
386       if (Upper.ult(CR.Upper))
387         return ConstantRange(CR.Lower, Upper);
388 
389       return CR;
390     }
391     if (Upper.ult(CR.Upper))
392       return *this;
393 
394     if (Lower.ult(CR.Upper))
395       return ConstantRange(Lower, CR.Upper);
396 
397     return ConstantRange(getBitWidth(), false);
398   }
399 
400   if (isWrappedSet() && !CR.isWrappedSet()) {
401     if (CR.Lower.ult(Upper)) {
402       if (CR.Upper.ult(Upper))
403         return CR;
404 
405       if (CR.Upper.ule(Lower))
406         return ConstantRange(CR.Lower, Upper);
407 
408       if (isSizeStrictlySmallerThan(CR))
409         return *this;
410       return CR;
411     }
412     if (CR.Lower.ult(Lower)) {
413       if (CR.Upper.ule(Lower))
414         return ConstantRange(getBitWidth(), false);
415 
416       return ConstantRange(Lower, CR.Upper);
417     }
418     return CR;
419   }
420 
421   if (CR.Upper.ult(Upper)) {
422     if (CR.Lower.ult(Upper)) {
423       if (isSizeStrictlySmallerThan(CR))
424         return *this;
425       return CR;
426     }
427 
428     if (CR.Lower.ult(Lower))
429       return ConstantRange(Lower, CR.Upper);
430 
431     return CR;
432   }
433   if (CR.Upper.ule(Lower)) {
434     if (CR.Lower.ult(Lower))
435       return *this;
436 
437     return ConstantRange(CR.Lower, Upper);
438   }
439   if (isSizeStrictlySmallerThan(CR))
440     return *this;
441   return CR;
442 }
443 
444 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
445   assert(getBitWidth() == CR.getBitWidth() &&
446          "ConstantRange types don't agree!");
447 
448   if (   isFullSet() || CR.isEmptySet()) return *this;
449   if (CR.isFullSet() ||    isEmptySet()) return CR;
450 
451   if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
452 
453   if (!isWrappedSet() && !CR.isWrappedSet()) {
454     if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
455       // If the two ranges are disjoint, find the smaller gap and bridge it.
456       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
457       if (d1.ult(d2))
458         return ConstantRange(Lower, CR.Upper);
459       return ConstantRange(CR.Lower, Upper);
460     }
461 
462     APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
463     APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
464 
465     if (L.isNullValue() && U.isNullValue())
466       return ConstantRange(getBitWidth());
467 
468     return ConstantRange(std::move(L), std::move(U));
469   }
470 
471   if (!CR.isWrappedSet()) {
472     // ------U   L-----  and  ------U   L----- : this
473     //   L--U                            L--U  : CR
474     if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
475       return *this;
476 
477     // ------U   L----- : this
478     //    L---------U   : CR
479     if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
480       return ConstantRange(getBitWidth());
481 
482     // ----U       L---- : this
483     //       L---U       : CR
484     //    <d1>  <d2>
485     if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
486       APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
487       if (d1.ult(d2))
488         return ConstantRange(Lower, CR.Upper);
489       return ConstantRange(CR.Lower, Upper);
490     }
491 
492     // ----U     L----- : this
493     //        L----U    : CR
494     if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
495       return ConstantRange(CR.Lower, Upper);
496 
497     // ------U    L---- : this
498     //    L-----U       : CR
499     assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
500            "ConstantRange::unionWith missed a case with one range wrapped");
501     return ConstantRange(Lower, CR.Upper);
502   }
503 
504   // ------U    L----  and  ------U    L---- : this
505   // -U  L-----------  and  ------------U  L : CR
506   if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
507     return ConstantRange(getBitWidth());
508 
509   APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
510   APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
511 
512   return ConstantRange(std::move(L), std::move(U));
513 }
514 
515 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
516                                     uint32_t ResultBitWidth) const {
517   switch (CastOp) {
518   default:
519     llvm_unreachable("unsupported cast type");
520   case Instruction::Trunc:
521     return truncate(ResultBitWidth);
522   case Instruction::SExt:
523     return signExtend(ResultBitWidth);
524   case Instruction::ZExt:
525     return zeroExtend(ResultBitWidth);
526   case Instruction::BitCast:
527     return *this;
528   case Instruction::FPToUI:
529   case Instruction::FPToSI:
530     if (getBitWidth() == ResultBitWidth)
531       return *this;
532     else
533       return ConstantRange(getBitWidth(), /*isFullSet=*/true);
534   case Instruction::UIToFP: {
535     // TODO: use input range if available
536     auto BW = getBitWidth();
537     APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
538     APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
539     return ConstantRange(std::move(Min), std::move(Max));
540   }
541   case Instruction::SIToFP: {
542     // TODO: use input range if available
543     auto BW = getBitWidth();
544     APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
545     APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
546     return ConstantRange(std::move(SMin), std::move(SMax));
547   }
548   case Instruction::FPTrunc:
549   case Instruction::FPExt:
550   case Instruction::IntToPtr:
551   case Instruction::PtrToInt:
552   case Instruction::AddrSpaceCast:
553     // Conservatively return full set.
554     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
555   };
556 }
557 
558 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
559   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
560 
561   unsigned SrcTySize = getBitWidth();
562   assert(SrcTySize < DstTySize && "Not a value extension");
563   if (isFullSet() || isWrappedSet()) {
564     // Change into [0, 1 << src bit width)
565     APInt LowerExt(DstTySize, 0);
566     if (!Upper) // special case: [X, 0) -- not really wrapping around
567       LowerExt = Lower.zext(DstTySize);
568     return ConstantRange(std::move(LowerExt),
569                          APInt::getOneBitSet(DstTySize, SrcTySize));
570   }
571 
572   return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
573 }
574 
575 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
576   if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
577 
578   unsigned SrcTySize = getBitWidth();
579   assert(SrcTySize < DstTySize && "Not a value extension");
580 
581   // special case: [X, INT_MIN) -- not really wrapping around
582   if (Upper.isMinSignedValue())
583     return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
584 
585   if (isFullSet() || isSignWrappedSet()) {
586     return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
587                          APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
588   }
589 
590   return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
591 }
592 
593 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
594   assert(getBitWidth() > DstTySize && "Not a value truncation");
595   if (isEmptySet())
596     return ConstantRange(DstTySize, /*isFullSet=*/false);
597   if (isFullSet())
598     return ConstantRange(DstTySize, /*isFullSet=*/true);
599 
600   APInt LowerDiv(Lower), UpperDiv(Upper);
601   ConstantRange Union(DstTySize, /*isFullSet=*/false);
602 
603   // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
604   // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
605   // then we do the union with [MaxValue, Upper)
606   if (isWrappedSet()) {
607     // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
608     // truncated range.
609     if (Upper.getActiveBits() > DstTySize ||
610         Upper.countTrailingOnes() == DstTySize)
611       return ConstantRange(DstTySize, /*isFullSet=*/true);
612 
613     Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
614     UpperDiv.setAllBits();
615 
616     // Union covers the MaxValue case, so return if the remaining range is just
617     // MaxValue(DstTy).
618     if (LowerDiv == UpperDiv)
619       return Union;
620   }
621 
622   // Chop off the most significant bits that are past the destination bitwidth.
623   if (LowerDiv.getActiveBits() > DstTySize) {
624     // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
625     APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
626     LowerDiv -= Adjust;
627     UpperDiv -= Adjust;
628   }
629 
630   unsigned UpperDivWidth = UpperDiv.getActiveBits();
631   if (UpperDivWidth <= DstTySize)
632     return ConstantRange(LowerDiv.trunc(DstTySize),
633                          UpperDiv.trunc(DstTySize)).unionWith(Union);
634 
635   // The truncated value wraps around. Check if we can do better than fullset.
636   if (UpperDivWidth == DstTySize + 1) {
637     // Clear the MSB so that UpperDiv wraps around.
638     UpperDiv.clearBit(DstTySize);
639     if (UpperDiv.ult(LowerDiv))
640       return ConstantRange(LowerDiv.trunc(DstTySize),
641                            UpperDiv.trunc(DstTySize)).unionWith(Union);
642   }
643 
644   return ConstantRange(DstTySize, /*isFullSet=*/true);
645 }
646 
647 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
648   unsigned SrcTySize = getBitWidth();
649   if (SrcTySize > DstTySize)
650     return truncate(DstTySize);
651   if (SrcTySize < DstTySize)
652     return zeroExtend(DstTySize);
653   return *this;
654 }
655 
656 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
657   unsigned SrcTySize = getBitWidth();
658   if (SrcTySize > DstTySize)
659     return truncate(DstTySize);
660   if (SrcTySize < DstTySize)
661     return signExtend(DstTySize);
662   return *this;
663 }
664 
665 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
666                                       const ConstantRange &Other) const {
667   assert(BinOp >= Instruction::BinaryOpsBegin &&
668          BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
669 
670   switch (BinOp) {
671   case Instruction::Add:
672     return add(Other);
673   case Instruction::Sub:
674     return sub(Other);
675   case Instruction::Mul:
676     return multiply(Other);
677   case Instruction::UDiv:
678     return udiv(Other);
679   case Instruction::Shl:
680     return shl(Other);
681   case Instruction::LShr:
682     return lshr(Other);
683   case Instruction::And:
684     return binaryAnd(Other);
685   case Instruction::Or:
686     return binaryOr(Other);
687   // Note: floating point operations applied to abstract ranges are just
688   // ideal integer operations with a lossy representation
689   case Instruction::FAdd:
690     return add(Other);
691   case Instruction::FSub:
692     return sub(Other);
693   case Instruction::FMul:
694     return multiply(Other);
695   default:
696     // Conservatively return full set.
697     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
698   }
699 }
700 
701 ConstantRange
702 ConstantRange::add(const ConstantRange &Other) const {
703   if (isEmptySet() || Other.isEmptySet())
704     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
705   if (isFullSet() || Other.isFullSet())
706     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
707 
708   APInt NewLower = getLower() + Other.getLower();
709   APInt NewUpper = getUpper() + Other.getUpper() - 1;
710   if (NewLower == NewUpper)
711     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
712 
713   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
714   if (X.isSizeStrictlySmallerThan(*this) ||
715       X.isSizeStrictlySmallerThan(Other))
716     // We've wrapped, therefore, full set.
717     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
718   return X;
719 }
720 
721 ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
722   // Calculate the subset of this range such that "X + Other" is
723   // guaranteed not to wrap (overflow) for all X in this subset.
724   // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
725   // passing a single element range.
726   auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
727                                       ConstantRange(Other),
728                                       OverflowingBinaryOperator::NoSignedWrap);
729   auto NSWConstrainedRange = intersectWith(NSWRange);
730 
731   return NSWConstrainedRange.add(ConstantRange(Other));
732 }
733 
734 ConstantRange
735 ConstantRange::sub(const ConstantRange &Other) const {
736   if (isEmptySet() || Other.isEmptySet())
737     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
738   if (isFullSet() || Other.isFullSet())
739     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
740 
741   APInt NewLower = getLower() - Other.getUpper() + 1;
742   APInt NewUpper = getUpper() - Other.getLower();
743   if (NewLower == NewUpper)
744     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
745 
746   ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
747   if (X.isSizeStrictlySmallerThan(*this) ||
748       X.isSizeStrictlySmallerThan(Other))
749     // We've wrapped, therefore, full set.
750     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
751   return X;
752 }
753 
754 ConstantRange
755 ConstantRange::multiply(const ConstantRange &Other) const {
756   // TODO: If either operand is a single element and the multiply is known to
757   // be non-wrapping, round the result min and max value to the appropriate
758   // multiple of that element. If wrapping is possible, at least adjust the
759   // range according to the greatest power-of-two factor of the single element.
760 
761   if (isEmptySet() || Other.isEmptySet())
762     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
763 
764   // Multiplication is signedness-independent. However different ranges can be
765   // obtained depending on how the input ranges are treated. These different
766   // ranges are all conservatively correct, but one might be better than the
767   // other. We calculate two ranges; one treating the inputs as unsigned
768   // and the other signed, then return the smallest of these ranges.
769 
770   // Unsigned range first.
771   APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
772   APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
773   APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
774   APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
775 
776   ConstantRange Result_zext = ConstantRange(this_min * Other_min,
777                                             this_max * Other_max + 1);
778   ConstantRange UR = Result_zext.truncate(getBitWidth());
779 
780   // If the unsigned range doesn't wrap, and isn't negative then it's a range
781   // from one positive number to another which is as good as we can generate.
782   // In this case, skip the extra work of generating signed ranges which aren't
783   // going to be better than this range.
784   if (!UR.isWrappedSet() &&
785       (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
786     return UR;
787 
788   // Now the signed range. Because we could be dealing with negative numbers
789   // here, the lower bound is the smallest of the cartesian product of the
790   // lower and upper ranges; for example:
791   //   [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
792   // Similarly for the upper bound, swapping min for max.
793 
794   this_min = getSignedMin().sext(getBitWidth() * 2);
795   this_max = getSignedMax().sext(getBitWidth() * 2);
796   Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
797   Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
798 
799   auto L = {this_min * Other_min, this_min * Other_max,
800             this_max * Other_min, this_max * Other_max};
801   auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
802   ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
803   ConstantRange SR = Result_sext.truncate(getBitWidth());
804 
805   return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
806 }
807 
808 ConstantRange
809 ConstantRange::smax(const ConstantRange &Other) const {
810   // X smax Y is: range(smax(X_smin, Y_smin),
811   //                    smax(X_smax, Y_smax))
812   if (isEmptySet() || Other.isEmptySet())
813     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
814   APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
815   APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
816   if (NewU == NewL)
817     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
818   return ConstantRange(std::move(NewL), std::move(NewU));
819 }
820 
821 ConstantRange
822 ConstantRange::umax(const ConstantRange &Other) const {
823   // X umax Y is: range(umax(X_umin, Y_umin),
824   //                    umax(X_umax, Y_umax))
825   if (isEmptySet() || Other.isEmptySet())
826     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
827   APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
828   APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
829   if (NewU == NewL)
830     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
831   return ConstantRange(std::move(NewL), std::move(NewU));
832 }
833 
834 ConstantRange
835 ConstantRange::smin(const ConstantRange &Other) const {
836   // X smin Y is: range(smin(X_smin, Y_smin),
837   //                    smin(X_smax, Y_smax))
838   if (isEmptySet() || Other.isEmptySet())
839     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
840   APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
841   APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
842   if (NewU == NewL)
843     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
844   return ConstantRange(std::move(NewL), std::move(NewU));
845 }
846 
847 ConstantRange
848 ConstantRange::umin(const ConstantRange &Other) const {
849   // X umin Y is: range(umin(X_umin, Y_umin),
850   //                    umin(X_umax, Y_umax))
851   if (isEmptySet() || Other.isEmptySet())
852     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
853   APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
854   APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
855   if (NewU == NewL)
856     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
857   return ConstantRange(std::move(NewL), std::move(NewU));
858 }
859 
860 ConstantRange
861 ConstantRange::udiv(const ConstantRange &RHS) const {
862   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
863     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
864   if (RHS.isFullSet())
865     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
866 
867   APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
868 
869   APInt RHS_umin = RHS.getUnsignedMin();
870   if (RHS_umin.isNullValue()) {
871     // We want the lowest value in RHS excluding zero. Usually that would be 1
872     // except for a range in the form of [X, 1) in which case it would be X.
873     if (RHS.getUpper() == 1)
874       RHS_umin = RHS.getLower();
875     else
876       RHS_umin = 1;
877   }
878 
879   APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
880 
881   // If the LHS is Full and the RHS is a wrapped interval containing 1 then
882   // this could occur.
883   if (Lower == Upper)
884     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
885 
886   return ConstantRange(std::move(Lower), std::move(Upper));
887 }
888 
889 ConstantRange
890 ConstantRange::binaryAnd(const ConstantRange &Other) const {
891   if (isEmptySet() || Other.isEmptySet())
892     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
893 
894   // TODO: replace this with something less conservative
895 
896   APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
897   if (umin.isAllOnesValue())
898     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
899   return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
900 }
901 
902 ConstantRange
903 ConstantRange::binaryOr(const ConstantRange &Other) const {
904   if (isEmptySet() || Other.isEmptySet())
905     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
906 
907   // TODO: replace this with something less conservative
908 
909   APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
910   if (umax.isNullValue())
911     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
912   return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
913 }
914 
915 ConstantRange
916 ConstantRange::shl(const ConstantRange &Other) const {
917   if (isEmptySet() || Other.isEmptySet())
918     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
919 
920   APInt max = getUnsignedMax();
921   APInt Other_umax = Other.getUnsignedMax();
922 
923   // there's overflow!
924   if (Other_umax.uge(max.countLeadingZeros()))
925     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
926 
927   // FIXME: implement the other tricky cases
928 
929   APInt min = getUnsignedMin();
930   min <<= Other.getUnsignedMin();
931   max <<= Other_umax;
932 
933   return ConstantRange(std::move(min), std::move(max) + 1);
934 }
935 
936 ConstantRange
937 ConstantRange::lshr(const ConstantRange &Other) const {
938   if (isEmptySet() || Other.isEmptySet())
939     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
940 
941   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
942   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
943   if (min == max)
944     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
945 
946   return ConstantRange(std::move(min), std::move(max));
947 }
948 
949 ConstantRange ConstantRange::inverse() const {
950   if (isFullSet())
951     return ConstantRange(getBitWidth(), /*isFullSet=*/false);
952   if (isEmptySet())
953     return ConstantRange(getBitWidth(), /*isFullSet=*/true);
954   return ConstantRange(Upper, Lower);
955 }
956 
957 void ConstantRange::print(raw_ostream &OS) const {
958   if (isFullSet())
959     OS << "full-set";
960   else if (isEmptySet())
961     OS << "empty-set";
962   else
963     OS << "[" << Lower << "," << Upper << ")";
964 }
965 
966 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
967 LLVM_DUMP_METHOD void ConstantRange::dump() const {
968   print(dbgs());
969 }
970 #endif
971 
972 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
973   const unsigned NumRanges = Ranges.getNumOperands() / 2;
974   assert(NumRanges >= 1 && "Must have at least one range!");
975   assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
976 
977   auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
978   auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
979 
980   ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
981 
982   for (unsigned i = 1; i < NumRanges; ++i) {
983     auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
984     auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
985 
986     // Note: unionWith will potentially create a range that contains values not
987     // contained in any of the original N ranges.
988     CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
989   }
990 
991   return CR;
992 }
993