LLVM  10.0.0svn
ConstantRange.cpp
Go to the documentation of this file.
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"
34 #include "llvm/Support/KnownBits.h"
36 #include <algorithm>
37 #include <cassert>
38 #include <cstdint>
39 
40 using namespace llvm;
41 
43  : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
44  Upper(Lower) {}
45 
47  : Lower(std::move(V)), Upper(Lower + 1) {}
48 
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 
58  bool IsSigned) {
59  assert(!Known.hasConflict() && "Expected valid KnownBits");
60 
61  if (Known.isUnknown())
62  return getFull(Known.getBitWidth());
63 
64  // For unsigned ranges, or signed ranges with known sign bit, create a simple
65  // range between the smallest and largest possible value.
66  if (!IsSigned || Known.isNegative() || Known.isNonNegative())
67  return ConstantRange(Known.One, ~Known.Zero + 1);
68 
69  // If we don't know the sign bit, pick the lower bound as a negative number
70  // and the upper bound as a non-negative one.
71  APInt Lower = Known.One, Upper = ~Known.Zero;
72  Lower.setSignBit();
73  Upper.clearSignBit();
74  return ConstantRange(Lower, Upper + 1);
75 }
76 
78  const ConstantRange &CR) {
79  if (CR.isEmptySet())
80  return CR;
81 
82  uint32_t W = CR.getBitWidth();
83  switch (Pred) {
84  default:
85  llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
86  case CmpInst::ICMP_EQ:
87  return CR;
88  case CmpInst::ICMP_NE:
89  if (CR.isSingleElement())
90  return ConstantRange(CR.getUpper(), CR.getLower());
91  return getFull(W);
92  case CmpInst::ICMP_ULT: {
93  APInt UMax(CR.getUnsignedMax());
94  if (UMax.isMinValue())
95  return getEmpty(W);
96  return ConstantRange(APInt::getMinValue(W), std::move(UMax));
97  }
98  case CmpInst::ICMP_SLT: {
99  APInt SMax(CR.getSignedMax());
100  if (SMax.isMinSignedValue())
101  return getEmpty(W);
102  return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
103  }
104  case CmpInst::ICMP_ULE:
105  return getNonEmpty(APInt::getMinValue(W), CR.getUnsignedMax() + 1);
106  case CmpInst::ICMP_SLE:
108  case CmpInst::ICMP_UGT: {
109  APInt UMin(CR.getUnsignedMin());
110  if (UMin.isMaxValue())
111  return getEmpty(W);
112  return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
113  }
114  case CmpInst::ICMP_SGT: {
115  APInt SMin(CR.getSignedMin());
116  if (SMin.isMaxSignedValue())
117  return getEmpty(W);
118  return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
119  }
120  case CmpInst::ICMP_UGE:
122  case CmpInst::ICMP_SGE:
124  }
125 }
126 
128  const ConstantRange &CR) {
129  // Follows from De-Morgan's laws:
130  //
131  // ~(~A union ~B) == A intersect B.
132  //
134  .inverse();
135 }
136 
138  const APInt &C) {
139  // Computes the exact range that is equal to both the constant ranges returned
140  // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
141  // when RHS is a singleton such as an APInt and so the assert is valid.
142  // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
143  // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
144  //
146  return makeAllowedICmpRegion(Pred, C);
147 }
148 
150  APInt &RHS) const {
151  bool Success = false;
152 
153  if (isFullSet() || isEmptySet()) {
155  RHS = APInt(getBitWidth(), 0);
156  Success = true;
157  } else if (auto *OnlyElt = getSingleElement()) {
158  Pred = CmpInst::ICMP_EQ;
159  RHS = *OnlyElt;
160  Success = true;
161  } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
162  Pred = CmpInst::ICMP_NE;
163  RHS = *OnlyMissingElt;
164  Success = true;
165  } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
166  Pred =
168  RHS = getUpper();
169  Success = true;
170  } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
171  Pred =
173  RHS = getLower();
174  Success = true;
175  }
176 
177  assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
178  "Bad result!");
179 
180  return Success;
181 }
182 
183 /// Exact mul nuw region for single element RHS.
185  unsigned BitWidth = V.getBitWidth();
186  if (V == 0)
187  return ConstantRange::getFull(V.getBitWidth());
188 
193  APInt::Rounding::DOWN) + 1);
194 }
195 
196 /// Exact mul nsw region for single element RHS.
198  // Handle special case for 0, -1 and 1. See the last for reason why we
199  // specialize -1 and 1.
200  unsigned BitWidth = V.getBitWidth();
201  if (V == 0 || V.isOneValue())
202  return ConstantRange::getFull(BitWidth);
203 
204  APInt MinValue = APInt::getSignedMinValue(BitWidth);
205  APInt MaxValue = APInt::getSignedMaxValue(BitWidth);
206  // e.g. Returning [-127, 127], represented as [-127, -128).
207  if (V.isAllOnesValue())
208  return ConstantRange(-MaxValue, MinValue);
209 
210  APInt Lower, Upper;
211  if (V.isNegative()) {
212  Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP);
213  Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN);
214  } else {
215  Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP);
216  Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN);
217  }
218  // ConstantRange ctor take a half inclusive interval [Lower, Upper + 1).
219  // Upper + 1 is guaranteed not to overflow, because |divisor| > 1. 0, -1,
220  // and 1 are already handled as special cases.
221  return ConstantRange(Lower, Upper + 1);
222 }
223 
226  const ConstantRange &Other,
227  unsigned NoWrapKind) {
228  using OBO = OverflowingBinaryOperator;
229 
230  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
231 
232  assert((NoWrapKind == OBO::NoSignedWrap ||
233  NoWrapKind == OBO::NoUnsignedWrap) &&
234  "NoWrapKind invalid!");
235 
236  bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
237  unsigned BitWidth = Other.getBitWidth();
238 
239  switch (BinOp) {
240  default:
241  llvm_unreachable("Unsupported binary op");
242 
243  case Instruction::Add: {
244  if (Unsigned)
245  return getNonEmpty(APInt::getNullValue(BitWidth),
246  -Other.getUnsignedMax());
247 
248  APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
249  APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
250  return getNonEmpty(
251  SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal,
252  SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal);
253  }
254 
255  case Instruction::Sub: {
256  if (Unsigned)
257  return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth));
258 
259  APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
260  APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
261  return getNonEmpty(
262  SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal,
263  SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal);
264  }
265 
266  case Instruction::Mul:
267  if (Unsigned)
268  return makeExactMulNUWRegion(Other.getUnsignedMax());
269 
270  return makeExactMulNSWRegion(Other.getSignedMin())
272  }
273 }
274 
276  const APInt &Other,
277  unsigned NoWrapKind) {
278  // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
279  // "for all" and "for any" coincide in this case.
280  return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind);
281 }
282 
284  return Lower == Upper && Lower.isMaxValue();
285 }
286 
288  return Lower == Upper && Lower.isMinValue();
289 }
290 
292  return Lower.ugt(Upper) && !Upper.isNullValue();
293 }
294 
296  return Lower.ugt(Upper);
297 }
298 
300  return Lower.sgt(Upper) && !Upper.isMinSignedValue();
301 }
302 
304  return Lower.sgt(Upper);
305 }
306 
307 bool
309  assert(getBitWidth() == Other.getBitWidth());
310  if (isFullSet())
311  return false;
312  if (Other.isFullSet())
313  return true;
314  return (Upper - Lower).ult(Other.Upper - Other.Lower);
315 }
316 
317 bool
318 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
319  assert(MaxSize && "MaxSize can't be 0.");
320  // If this a full set, we need special handling to avoid needing an extra bit
321  // to represent the size.
322  if (isFullSet())
323  return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
324 
325  return (Upper - Lower).ugt(MaxSize);
326 }
327 
329  // Empty set is all negative, full set is not.
330  if (isEmptySet())
331  return true;
332  if (isFullSet())
333  return false;
334 
335  return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
336 }
337 
339  // Empty and full set are automatically treated correctly.
340  return !isSignWrappedSet() && Lower.isNonNegative();
341 }
342 
344  if (isFullSet() || isUpperWrapped())
346  return getUpper() - 1;
347 }
348 
350  if (isFullSet() || isWrappedSet())
352  return getLower();
353 }
354 
356  if (isFullSet() || isUpperSignWrapped())
358  return getUpper() - 1;
359 }
360 
362  if (isFullSet() || isSignWrappedSet())
364  return getLower();
365 }
366 
367 bool ConstantRange::contains(const APInt &V) const {
368  if (Lower == Upper)
369  return isFullSet();
370 
371  if (!isUpperWrapped())
372  return Lower.ule(V) && V.ult(Upper);
373  return Lower.ule(V) || V.ult(Upper);
374 }
375 
377  if (isFullSet() || Other.isEmptySet()) return true;
378  if (isEmptySet() || Other.isFullSet()) return false;
379 
380  if (!isUpperWrapped()) {
381  if (Other.isUpperWrapped())
382  return false;
383 
384  return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
385  }
386 
387  if (!Other.isUpperWrapped())
388  return Other.getUpper().ule(Upper) ||
389  Lower.ule(Other.getLower());
390 
391  return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
392 }
393 
395  assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
396  // If the set is empty or full, don't modify the endpoints.
397  if (Lower == Upper)
398  return *this;
399  return ConstantRange(Lower - Val, Upper - Val);
400 }
401 
403  return intersectWith(CR.inverse());
404 }
405 
407  const ConstantRange &CR1, const ConstantRange &CR2,
409  if (Type == ConstantRange::Unsigned) {
410  if (!CR1.isWrappedSet() && CR2.isWrappedSet())
411  return CR1;
412  if (CR1.isWrappedSet() && !CR2.isWrappedSet())
413  return CR2;
414  } else if (Type == ConstantRange::Signed) {
415  if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
416  return CR1;
417  if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
418  return CR2;
419  }
420 
421  if (CR1.isSizeStrictlySmallerThan(CR2))
422  return CR1;
423  return CR2;
424 }
425 
427  PreferredRangeType Type) 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 (!isUpperWrapped() && CR.isUpperWrapped())
436  return CR.intersectWith(*this, Type);
437 
438  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
439  if (Lower.ult(CR.Lower)) {
440  // L---U : this
441  // L---U : CR
442  if (Upper.ule(CR.Lower))
443  return getEmpty();
444 
445  // L---U : this
446  // L---U : CR
447  if (Upper.ult(CR.Upper))
448  return ConstantRange(CR.Lower, Upper);
449 
450  // L-------U : this
451  // L---U : CR
452  return CR;
453  }
454  // L---U : this
455  // L-------U : CR
456  if (Upper.ult(CR.Upper))
457  return *this;
458 
459  // L-----U : this
460  // L-----U : CR
461  if (Lower.ult(CR.Upper))
462  return ConstantRange(Lower, CR.Upper);
463 
464  // L---U : this
465  // L---U : CR
466  return getEmpty();
467  }
468 
469  if (isUpperWrapped() && !CR.isUpperWrapped()) {
470  if (CR.Lower.ult(Upper)) {
471  // ------U L--- : this
472  // L--U : CR
473  if (CR.Upper.ult(Upper))
474  return CR;
475 
476  // ------U L--- : this
477  // L------U : CR
478  if (CR.Upper.ule(Lower))
479  return ConstantRange(CR.Lower, Upper);
480 
481  // ------U L--- : this
482  // L----------U : CR
483  return getPreferredRange(*this, CR, Type);
484  }
485  if (CR.Lower.ult(Lower)) {
486  // --U L---- : this
487  // L--U : CR
488  if (CR.Upper.ule(Lower))
489  return getEmpty();
490 
491  // --U L---- : this
492  // L------U : CR
493  return ConstantRange(Lower, CR.Upper);
494  }
495 
496  // --U L------ : this
497  // L--U : CR
498  return CR;
499  }
500 
501  if (CR.Upper.ult(Upper)) {
502  // ------U L-- : this
503  // --U L------ : CR
504  if (CR.Lower.ult(Upper))
505  return getPreferredRange(*this, CR, Type);
506 
507  // ----U L-- : this
508  // --U L---- : CR
509  if (CR.Lower.ult(Lower))
510  return ConstantRange(Lower, CR.Upper);
511 
512  // ----U L---- : this
513  // --U L-- : CR
514  return CR;
515  }
516  if (CR.Upper.ule(Lower)) {
517  // --U L-- : this
518  // ----U L---- : CR
519  if (CR.Lower.ult(Lower))
520  return *this;
521 
522  // --U L---- : this
523  // ----U L-- : CR
524  return ConstantRange(CR.Lower, Upper);
525  }
526 
527  // --U L------ : this
528  // ------U L-- : CR
529  return getPreferredRange(*this, CR, Type);
530 }
531 
533  PreferredRangeType Type) const {
534  assert(getBitWidth() == CR.getBitWidth() &&
535  "ConstantRange types don't agree!");
536 
537  if ( isFullSet() || CR.isEmptySet()) return *this;
538  if (CR.isFullSet() || isEmptySet()) return CR;
539 
540  if (!isUpperWrapped() && CR.isUpperWrapped())
541  return CR.unionWith(*this, Type);
542 
543  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
544  // L---U and L---U : this
545  // L---U L---U : CR
546  // result in one of
547  // L---------U
548  // -----U L-----
549  if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower))
550  return getPreferredRange(
551  ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
552 
553  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
554  APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
555 
556  if (L.isNullValue() && U.isNullValue())
557  return getFull();
558 
559  return ConstantRange(std::move(L), std::move(U));
560  }
561 
562  if (!CR.isUpperWrapped()) {
563  // ------U L----- and ------U L----- : this
564  // L--U L--U : CR
565  if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
566  return *this;
567 
568  // ------U L----- : this
569  // L---------U : CR
570  if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
571  return getFull();
572 
573  // ----U L---- : this
574  // L---U : CR
575  // results in one of
576  // ----------U L----
577  // ----U L----------
578  if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower))
579  return getPreferredRange(
580  ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
581 
582  // ----U L----- : this
583  // L----U : CR
584  if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))
585  return ConstantRange(CR.Lower, Upper);
586 
587  // ------U L---- : this
588  // L-----U : CR
589  assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
590  "ConstantRange::unionWith missed a case with one range wrapped");
591  return ConstantRange(Lower, CR.Upper);
592  }
593 
594  // ------U L---- and ------U L---- : this
595  // -U L----------- and ------------U L : CR
596  if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
597  return getFull();
598 
599  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
600  APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
601 
602  return ConstantRange(std::move(L), std::move(U));
603 }
604 
606  uint32_t ResultBitWidth) const {
607  switch (CastOp) {
608  default:
609  llvm_unreachable("unsupported cast type");
610  case Instruction::Trunc:
611  return truncate(ResultBitWidth);
612  case Instruction::SExt:
613  return signExtend(ResultBitWidth);
614  case Instruction::ZExt:
615  return zeroExtend(ResultBitWidth);
616  case Instruction::BitCast:
617  return *this;
618  case Instruction::FPToUI:
619  case Instruction::FPToSI:
620  if (getBitWidth() == ResultBitWidth)
621  return *this;
622  else
623  return getFull();
624  case Instruction::UIToFP: {
625  // TODO: use input range if available
626  auto BW = getBitWidth();
627  APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
628  APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
629  return ConstantRange(std::move(Min), std::move(Max));
630  }
631  case Instruction::SIToFP: {
632  // TODO: use input range if available
633  auto BW = getBitWidth();
634  APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
635  APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
636  return ConstantRange(std::move(SMin), std::move(SMax));
637  }
638  case Instruction::FPTrunc:
639  case Instruction::FPExt:
640  case Instruction::IntToPtr:
641  case Instruction::PtrToInt:
642  case Instruction::AddrSpaceCast:
643  // Conservatively return getFull set.
644  return getFull();
645  };
646 }
647 
649  if (isEmptySet()) return getEmpty(DstTySize);
650 
651  unsigned SrcTySize = getBitWidth();
652  assert(SrcTySize < DstTySize && "Not a value extension");
653  if (isFullSet() || isUpperWrapped()) {
654  // Change into [0, 1 << src bit width)
655  APInt LowerExt(DstTySize, 0);
656  if (!Upper) // special case: [X, 0) -- not really wrapping around
657  LowerExt = Lower.zext(DstTySize);
658  return ConstantRange(std::move(LowerExt),
659  APInt::getOneBitSet(DstTySize, SrcTySize));
660  }
661 
662  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
663 }
664 
666  if (isEmptySet()) return getEmpty(DstTySize);
667 
668  unsigned SrcTySize = getBitWidth();
669  assert(SrcTySize < DstTySize && "Not a value extension");
670 
671  // special case: [X, INT_MIN) -- not really wrapping around
672  if (Upper.isMinSignedValue())
673  return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
674 
675  if (isFullSet() || isSignWrappedSet()) {
676  return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
677  APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
678  }
679 
680  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
681 }
682 
684  assert(getBitWidth() > DstTySize && "Not a value truncation");
685  if (isEmptySet())
686  return getEmpty(DstTySize);
687  if (isFullSet())
688  return getFull(DstTySize);
689 
690  APInt LowerDiv(Lower), UpperDiv(Upper);
691  ConstantRange Union(DstTySize, /*isFullSet=*/false);
692 
693  // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
694  // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
695  // then we do the union with [MaxValue, Upper)
696  if (isUpperWrapped()) {
697  // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
698  // truncated range.
699  if (Upper.getActiveBits() > DstTySize ||
700  Upper.countTrailingOnes() == DstTySize)
701  return getFull(DstTySize);
702 
703  Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
704  UpperDiv.setAllBits();
705 
706  // Union covers the MaxValue case, so return if the remaining range is just
707  // MaxValue(DstTy).
708  if (LowerDiv == UpperDiv)
709  return Union;
710  }
711 
712  // Chop off the most significant bits that are past the destination bitwidth.
713  if (LowerDiv.getActiveBits() > DstTySize) {
714  // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
715  APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
716  LowerDiv -= Adjust;
717  UpperDiv -= Adjust;
718  }
719 
720  unsigned UpperDivWidth = UpperDiv.getActiveBits();
721  if (UpperDivWidth <= DstTySize)
722  return ConstantRange(LowerDiv.trunc(DstTySize),
723  UpperDiv.trunc(DstTySize)).unionWith(Union);
724 
725  // The truncated value wraps around. Check if we can do better than fullset.
726  if (UpperDivWidth == DstTySize + 1) {
727  // Clear the MSB so that UpperDiv wraps around.
728  UpperDiv.clearBit(DstTySize);
729  if (UpperDiv.ult(LowerDiv))
730  return ConstantRange(LowerDiv.trunc(DstTySize),
731  UpperDiv.trunc(DstTySize)).unionWith(Union);
732  }
733 
734  return getFull(DstTySize);
735 }
736 
738  unsigned SrcTySize = getBitWidth();
739  if (SrcTySize > DstTySize)
740  return truncate(DstTySize);
741  if (SrcTySize < DstTySize)
742  return zeroExtend(DstTySize);
743  return *this;
744 }
745 
747  unsigned SrcTySize = getBitWidth();
748  if (SrcTySize > DstTySize)
749  return truncate(DstTySize);
750  if (SrcTySize < DstTySize)
751  return signExtend(DstTySize);
752  return *this;
753 }
754 
756  const ConstantRange &Other) const {
757  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
758 
759  switch (BinOp) {
760  case Instruction::Add:
761  return add(Other);
762  case Instruction::Sub:
763  return sub(Other);
764  case Instruction::Mul:
765  return multiply(Other);
766  case Instruction::UDiv:
767  return udiv(Other);
768  case Instruction::SDiv:
769  return sdiv(Other);
770  case Instruction::URem:
771  return urem(Other);
772  case Instruction::SRem:
773  return srem(Other);
774  case Instruction::Shl:
775  return shl(Other);
776  case Instruction::LShr:
777  return lshr(Other);
778  case Instruction::AShr:
779  return ashr(Other);
780  case Instruction::And:
781  return binaryAnd(Other);
782  case Instruction::Or:
783  return binaryOr(Other);
784  // Note: floating point operations applied to abstract ranges are just
785  // ideal integer operations with a lossy representation
786  case Instruction::FAdd:
787  return add(Other);
788  case Instruction::FSub:
789  return sub(Other);
790  case Instruction::FMul:
791  return multiply(Other);
792  default:
793  // Conservatively return getFull set.
794  return getFull();
795  }
796 }
797 
800  if (isEmptySet() || Other.isEmptySet())
801  return getEmpty();
802  if (isFullSet() || Other.isFullSet())
803  return getFull();
804 
805  APInt NewLower = getLower() + Other.getLower();
806  APInt NewUpper = getUpper() + Other.getUpper() - 1;
807  if (NewLower == NewUpper)
808  return getFull();
809 
810  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
811  if (X.isSizeStrictlySmallerThan(*this) ||
812  X.isSizeStrictlySmallerThan(Other))
813  // We've wrapped, therefore, full set.
814  return getFull();
815  return X;
816 }
817 
819  unsigned NoWrapKind,
820  PreferredRangeType RangeType) const {
821  // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
822  // (X is from this, and Y is from Other)
823  if (isEmptySet() || Other.isEmptySet())
824  return getEmpty();
825  if (isFullSet() && Other.isFullSet())
826  return getFull();
827 
828  using OBO = OverflowingBinaryOperator;
829  ConstantRange Result = add(Other);
830 
831  auto addWithNoUnsignedWrap = [this](const ConstantRange &Other) {
832  APInt LMin = getUnsignedMin(), LMax = getUnsignedMax();
833  APInt RMin = Other.getUnsignedMin(), RMax = Other.getUnsignedMax();
834  bool Overflow;
835  APInt NewMin = LMin.uadd_ov(RMin, Overflow);
836  if (Overflow)
837  return getEmpty();
838  APInt NewMax = LMax.uadd_sat(RMax);
839  return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1);
840  };
841 
842  auto addWithNoSignedWrap = [this](const ConstantRange &Other) {
843  APInt LMin = getSignedMin(), LMax = getSignedMax();
844  APInt RMin = Other.getSignedMin(), RMax = Other.getSignedMax();
845  if (LMin.isNonNegative()) {
846  bool Overflow;
847  APInt Temp = LMin.sadd_ov(RMin, Overflow);
848  if (Overflow)
849  return getEmpty();
850  }
851  if (LMax.isNegative()) {
852  bool Overflow;
853  APInt Temp = LMax.sadd_ov(RMax, Overflow);
854  if (Overflow)
855  return getEmpty();
856  }
857  APInt NewMin = LMin.sadd_sat(RMin);
858  APInt NewMax = LMax.sadd_sat(RMax);
859  return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1);
860  };
861 
862  if (NoWrapKind & OBO::NoSignedWrap)
863  Result = Result.intersectWith(addWithNoSignedWrap(Other), RangeType);
864  if (NoWrapKind & OBO::NoUnsignedWrap)
865  Result = Result.intersectWith(addWithNoUnsignedWrap(Other), RangeType);
866  return Result;
867 }
868 
871  if (isEmptySet() || Other.isEmptySet())
872  return getEmpty();
873  if (isFullSet() || Other.isFullSet())
874  return getFull();
875 
876  APInt NewLower = getLower() - Other.getUpper() + 1;
877  APInt NewUpper = getUpper() - Other.getLower();
878  if (NewLower == NewUpper)
879  return getFull();
880 
881  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
882  if (X.isSizeStrictlySmallerThan(*this) ||
883  X.isSizeStrictlySmallerThan(Other))
884  // We've wrapped, therefore, full set.
885  return getFull();
886  return X;
887 }
888 
891  // TODO: If either operand is a single element and the multiply is known to
892  // be non-wrapping, round the result min and max value to the appropriate
893  // multiple of that element. If wrapping is possible, at least adjust the
894  // range according to the greatest power-of-two factor of the single element.
895 
896  if (isEmptySet() || Other.isEmptySet())
897  return getEmpty();
898 
899  // Multiplication is signedness-independent. However different ranges can be
900  // obtained depending on how the input ranges are treated. These different
901  // ranges are all conservatively correct, but one might be better than the
902  // other. We calculate two ranges; one treating the inputs as unsigned
903  // and the other signed, then return the smallest of these ranges.
904 
905  // Unsigned range first.
906  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
907  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
908  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
909  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
910 
911  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
912  this_max * Other_max + 1);
913  ConstantRange UR = Result_zext.truncate(getBitWidth());
914 
915  // If the unsigned range doesn't wrap, and isn't negative then it's a range
916  // from one positive number to another which is as good as we can generate.
917  // In this case, skip the extra work of generating signed ranges which aren't
918  // going to be better than this range.
919  if (!UR.isUpperWrapped() &&
920  (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
921  return UR;
922 
923  // Now the signed range. Because we could be dealing with negative numbers
924  // here, the lower bound is the smallest of the cartesian product of the
925  // lower and upper ranges; for example:
926  // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
927  // Similarly for the upper bound, swapping min for max.
928 
929  this_min = getSignedMin().sext(getBitWidth() * 2);
930  this_max = getSignedMax().sext(getBitWidth() * 2);
931  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
932  Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
933 
934  auto L = {this_min * Other_min, this_min * Other_max,
935  this_max * Other_min, this_max * Other_max};
936  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
937  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
938  ConstantRange SR = Result_sext.truncate(getBitWidth());
939 
940  return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
941 }
942 
945  // X smax Y is: range(smax(X_smin, Y_smin),
946  // smax(X_smax, Y_smax))
947  if (isEmptySet() || Other.isEmptySet())
948  return getEmpty();
949  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
950  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
951  return getNonEmpty(std::move(NewL), std::move(NewU));
952 }
953 
956  // X umax Y is: range(umax(X_umin, Y_umin),
957  // umax(X_umax, Y_umax))
958  if (isEmptySet() || Other.isEmptySet())
959  return getEmpty();
961  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
962  return getNonEmpty(std::move(NewL), std::move(NewU));
963 }
964 
967  // X smin Y is: range(smin(X_smin, Y_smin),
968  // smin(X_smax, Y_smax))
969  if (isEmptySet() || Other.isEmptySet())
970  return getEmpty();
971  APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
972  APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
973  return getNonEmpty(std::move(NewL), std::move(NewU));
974 }
975 
978  // X umin Y is: range(umin(X_umin, Y_umin),
979  // umin(X_umax, Y_umax))
980  if (isEmptySet() || Other.isEmptySet())
981  return getEmpty();
983  APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
984  return getNonEmpty(std::move(NewL), std::move(NewU));
985 }
986 
989  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
990  return getEmpty();
991 
993 
994  APInt RHS_umin = RHS.getUnsignedMin();
995  if (RHS_umin.isNullValue()) {
996  // We want the lowest value in RHS excluding zero. Usually that would be 1
997  // except for a range in the form of [X, 1) in which case it would be X.
998  if (RHS.getUpper() == 1)
999  RHS_umin = RHS.getLower();
1000  else
1001  RHS_umin = 1;
1002  }
1003 
1004  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
1005  return getNonEmpty(std::move(Lower), std::move(Upper));
1006 }
1007 
1009  // We split up the LHS and RHS into positive and negative components
1010  // and then also compute the positive and negative components of the result
1011  // separately by combining division results with the appropriate signs.
1014  ConstantRange PosFilter(APInt(getBitWidth(), 1), SignedMin);
1015  ConstantRange NegFilter(SignedMin, Zero);
1016  ConstantRange PosL = intersectWith(PosFilter);
1017  ConstantRange NegL = intersectWith(NegFilter);
1018  ConstantRange PosR = RHS.intersectWith(PosFilter);
1019  ConstantRange NegR = RHS.intersectWith(NegFilter);
1020 
1021  ConstantRange PosRes = getEmpty();
1022  if (!PosL.isEmptySet() && !PosR.isEmptySet())
1023  // pos / pos = pos.
1024  PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),
1025  (PosL.Upper - 1).sdiv(PosR.Lower) + 1);
1026 
1027  if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1028  // neg / neg = pos.
1029  //
1030  // We need to deal with one tricky case here: SignedMin / -1 is UB on the
1031  // IR level, so we'll want to exclude this case when calculating bounds.
1032  // (For APInts the operation is well-defined and yields SignedMin.) We
1033  // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1034  APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);
1035  if (NegL.Lower.isMinSignedValue() && NegR.Upper.isNullValue()) {
1036  // Remove -1 from the LHS. Skip if it's the only element, as this would
1037  // leave us with an empty set.
1038  if (!NegR.Lower.isAllOnesValue()) {
1039  APInt AdjNegRUpper;
1040  if (RHS.Lower.isAllOnesValue())
1041  // Negative part of [-1, X] without -1 is [SignedMin, X].
1042  AdjNegRUpper = RHS.Upper;
1043  else
1044  // [X, -1] without -1 is [X, -2].
1045  AdjNegRUpper = NegR.Upper - 1;
1046 
1047  PosRes = PosRes.unionWith(
1048  ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
1049  }
1050 
1051  // Remove SignedMin from the RHS. Skip if it's the only element, as this
1052  // would leave us with an empty set.
1053  if (NegL.Upper != SignedMin + 1) {
1054  APInt AdjNegLLower;
1055  if (Upper == SignedMin + 1)
1056  // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1057  AdjNegLLower = Lower;
1058  else
1059  // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1060  AdjNegLLower = NegL.Lower + 1;
1061 
1062  PosRes = PosRes.unionWith(
1063  ConstantRange(std::move(Lo),
1064  AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
1065  }
1066  } else {
1067  PosRes = PosRes.unionWith(
1068  ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
1069  }
1070  }
1071 
1072  ConstantRange NegRes = getEmpty();
1073  if (!PosL.isEmptySet() && !NegR.isEmptySet())
1074  // pos / neg = neg.
1075  NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
1076  PosL.Lower.sdiv(NegR.Lower) + 1);
1077 
1078  if (!NegL.isEmptySet() && !PosR.isEmptySet())
1079  // neg / pos = neg.
1080  NegRes = NegRes.unionWith(
1081  ConstantRange(NegL.Lower.sdiv(PosR.Lower),
1082  (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));
1083 
1084  // Prefer a non-wrapping signed range here.
1085  ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed);
1086 
1087  // Preserve the zero that we dropped when splitting the LHS by sign.
1088  if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1089  Res = Res.unionWith(ConstantRange(Zero));
1090  return Res;
1091 }
1092 
1094  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
1095  return getEmpty();
1096 
1097  // L % R for L < R is L.
1098  if (getUnsignedMax().ult(RHS.getUnsignedMin()))
1099  return *this;
1100 
1101  // L % R is <= L and < R.
1102  APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
1103  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
1104 }
1105 
1107  if (isEmptySet() || RHS.isEmptySet())
1108  return getEmpty();
1109 
1110  ConstantRange AbsRHS = RHS.abs();
1111  APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1112  APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1113 
1114  // Modulus by zero is UB.
1115  if (MaxAbsRHS.isNullValue())
1116  return getEmpty();
1117 
1118  if (MinAbsRHS.isNullValue())
1119  ++MinAbsRHS;
1120 
1121  APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1122 
1123  if (MinLHS.isNonNegative()) {
1124  // L % R for L < R is L.
1125  if (MaxLHS.ult(MinAbsRHS))
1126  return *this;
1127 
1128  // L % R is <= L and < R.
1129  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1130  return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(Upper));
1131  }
1132 
1133  // Same basic logic as above, but the result is negative.
1134  if (MaxLHS.isNegative()) {
1135  if (MinLHS.ugt(-MinAbsRHS))
1136  return *this;
1137 
1138  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1139  return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1140  }
1141 
1142  // LHS range crosses zero.
1143  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1144  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1145  return ConstantRange(std::move(Lower), std::move(Upper));
1146 }
1147 
1150  if (isEmptySet() || Other.isEmptySet())
1151  return getEmpty();
1152 
1153  // TODO: replace this with something less conservative
1154 
1156  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
1157 }
1158 
1161  if (isEmptySet() || Other.isEmptySet())
1162  return getEmpty();
1163 
1164  // TODO: replace this with something less conservative
1165 
1167  return getNonEmpty(std::move(umax), APInt::getNullValue(getBitWidth()));
1168 }
1169 
1172  if (isEmptySet() || Other.isEmptySet())
1173  return getEmpty();
1174 
1175  APInt max = getUnsignedMax();
1176  APInt Other_umax = Other.getUnsignedMax();
1177 
1178  // If we are shifting by maximum amount of
1179  // zero return return the original range.
1180  if (Other_umax.isNullValue())
1181  return *this;
1182  // there's overflow!
1183  if (Other_umax.ugt(max.countLeadingZeros()))
1184  return getFull();
1185 
1186  // FIXME: implement the other tricky cases
1187 
1188  APInt min = getUnsignedMin();
1189  min <<= Other.getUnsignedMin();
1190  max <<= Other_umax;
1191 
1192  return ConstantRange(std::move(min), std::move(max) + 1);
1193 }
1194 
1197  if (isEmptySet() || Other.isEmptySet())
1198  return getEmpty();
1199 
1200  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1201  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1202  return getNonEmpty(std::move(min), std::move(max));
1203 }
1204 
1207  if (isEmptySet() || Other.isEmptySet())
1208  return getEmpty();
1209 
1210  // May straddle zero, so handle both positive and negative cases.
1211  // 'PosMax' is the upper bound of the result of the ashr
1212  // operation, when Upper of the LHS of ashr is a non-negative.
1213  // number. Since ashr of a non-negative number will result in a
1214  // smaller number, the Upper value of LHS is shifted right with
1215  // the minimum value of 'Other' instead of the maximum value.
1216  APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1217 
1218  // 'PosMin' is the lower bound of the result of the ashr
1219  // operation, when Lower of the LHS is a non-negative number.
1220  // Since ashr of a non-negative number will result in a smaller
1221  // number, the Lower value of LHS is shifted right with the
1222  // maximum value of 'Other'.
1223  APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1224 
1225  // 'NegMax' is the upper bound of the result of the ashr
1226  // operation, when Upper of the LHS of ashr is a negative number.
1227  // Since 'ashr' of a negative number will result in a bigger
1228  // number, the Upper value of LHS is shifted right with the
1229  // maximum value of 'Other'.
1230  APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1231 
1232  // 'NegMin' is the lower bound of the result of the ashr
1233  // operation, when Lower of the LHS of ashr is a negative number.
1234  // Since 'ashr' of a negative number will result in a bigger
1235  // number, the Lower value of LHS is shifted right with the
1236  // minimum value of 'Other'.
1237  APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1238 
1239  APInt max, min;
1240  if (getSignedMin().isNonNegative()) {
1241  // Upper and Lower of LHS are non-negative.
1242  min = PosMin;
1243  max = PosMax;
1244  } else if (getSignedMax().isNegative()) {
1245  // Upper and Lower of LHS are negative.
1246  min = NegMin;
1247  max = NegMax;
1248  } else {
1249  // Upper is non-negative and Lower is negative.
1250  min = NegMin;
1251  max = PosMax;
1252  }
1253  return getNonEmpty(std::move(min), std::move(max));
1254 }
1255 
1257  if (isEmptySet() || Other.isEmptySet())
1258  return getEmpty();
1259 
1260  APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());
1261  APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;
1262  return getNonEmpty(std::move(NewL), std::move(NewU));
1263 }
1264 
1266  if (isEmptySet() || Other.isEmptySet())
1267  return getEmpty();
1268 
1269  APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());
1270  APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;
1271  return getNonEmpty(std::move(NewL), std::move(NewU));
1272 }
1273 
1275  if (isEmptySet() || Other.isEmptySet())
1276  return getEmpty();
1277 
1278  APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());
1279  APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;
1280  return getNonEmpty(std::move(NewL), std::move(NewU));
1281 }
1282 
1284  if (isEmptySet() || Other.isEmptySet())
1285  return getEmpty();
1286 
1287  APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
1288  APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
1289  return getNonEmpty(std::move(NewL), std::move(NewU));
1290 }
1291 
1293  if (isFullSet())
1294  return getEmpty();
1295  if (isEmptySet())
1296  return getFull();
1297  return ConstantRange(Upper, Lower);
1298 }
1299 
1301  if (isEmptySet())
1302  return getEmpty();
1303 
1304  if (isSignWrappedSet()) {
1305  APInt Lo;
1306  // Check whether the range crosses zero.
1307  if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1309  else
1310  Lo = APIntOps::umin(Lower, -Upper + 1);
1311 
1312  // SignedMin is included in the result range.
1314  }
1315 
1316  APInt SMin = getSignedMin(), SMax = getSignedMax();
1317 
1318  // All non-negative.
1319  if (SMin.isNonNegative())
1320  return *this;
1321 
1322  // All negative.
1323  if (SMax.isNegative())
1324  return ConstantRange(-SMax, -SMin + 1);
1325 
1326  // Range crosses zero.
1328  APIntOps::umax(-SMin, SMax) + 1);
1329 }
1330 
1332  const ConstantRange &Other) const {
1333  if (isEmptySet() || Other.isEmptySet())
1335 
1336  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1337  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1338 
1339  // a u+ b overflows high iff a u> ~b.
1340  if (Min.ugt(~OtherMin))
1342  if (Max.ugt(~OtherMax))
1345 }
1346 
1348  const ConstantRange &Other) const {
1349  if (isEmptySet() || Other.isEmptySet())
1351 
1352  APInt Min = getSignedMin(), Max = getSignedMax();
1353  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1354 
1357 
1358  // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1359  // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1360  if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1361  Min.sgt(SignedMax - OtherMin))
1363  if (Max.isNegative() && OtherMax.isNegative() &&
1364  Max.slt(SignedMin - OtherMax))
1366 
1367  if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1368  Max.sgt(SignedMax - OtherMax))
1370  if (Min.isNegative() && OtherMin.isNegative() &&
1371  Min.slt(SignedMin - OtherMin))
1373 
1375 }
1376 
1378  const ConstantRange &Other) const {
1379  if (isEmptySet() || Other.isEmptySet())
1381 
1382  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1383  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1384 
1385  // a u- b overflows low iff a u< b.
1386  if (Max.ult(OtherMin))
1388  if (Min.ult(OtherMax))
1391 }
1392 
1394  const ConstantRange &Other) const {
1395  if (isEmptySet() || Other.isEmptySet())
1397 
1398  APInt Min = getSignedMin(), Max = getSignedMax();
1399  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1400 
1403 
1404  // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
1405  // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
1406  if (Min.isNonNegative() && OtherMax.isNegative() &&
1407  Min.sgt(SignedMax + OtherMax))
1409  if (Max.isNegative() && OtherMin.isNonNegative() &&
1410  Max.slt(SignedMin + OtherMin))
1412 
1413  if (Max.isNonNegative() && OtherMin.isNegative() &&
1414  Max.sgt(SignedMax + OtherMin))
1416  if (Min.isNegative() && OtherMax.isNonNegative() &&
1417  Min.slt(SignedMin + OtherMax))
1419 
1421 }
1422 
1424  const ConstantRange &Other) const {
1425  if (isEmptySet() || Other.isEmptySet())
1427 
1428  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1429  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1430  bool Overflow;
1431 
1432  (void) Min.umul_ov(OtherMin, Overflow);
1433  if (Overflow)
1435 
1436  (void) Max.umul_ov(OtherMax, Overflow);
1437  if (Overflow)
1439 
1441 }
1442 
1444  if (isFullSet())
1445  OS << "full-set";
1446  else if (isEmptySet())
1447  OS << "empty-set";
1448  else
1449  OS << "[" << Lower << "," << Upper << ")";
1450 }
1451 
1452 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1454  print(dbgs());
1455 }
1456 #endif
1457 
1459  const unsigned NumRanges = Ranges.getNumOperands() / 2;
1460  assert(NumRanges >= 1 && "Must have at least one range!");
1461  assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1462 
1463  auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1464  auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1465 
1466  ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1467 
1468  for (unsigned i = 1; i < NumRanges; ++i) {
1469  auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1470  auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1471 
1472  // Note: unionWith will potentially create a range that contains values not
1473  // contained in any of the original N ranges.
1474  CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1475  }
1476 
1477  return CR;
1478 }
ConstantRange(uint32_t BitWidth, bool isFullSet)
Initialize a full or empty set for the specified bit width.
uint64_t CallInst * C
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1412
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:888
APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
Definition: APInt.cpp:2752
bool isUpperSignWrapped() const
Return true if the (exclusive) upper bound wraps around the signed domain.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const APInt & getUpper() const
Return the upper value for this range.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:484
Always overflows in the direction of signed/unsigned min value.
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition: APInt.cpp:1647
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:46
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:912
APInt uadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2023
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1203
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1576
This file contains the declarations for metadata subclasses.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:647
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
ConstantRange lshr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a logical right shift of a value i...
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:953
unsigned less or equal
Definition: InstrTypes.h:758
OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const
Return whether unsigned add of the two ranges always/never overflows.
unsigned less than
Definition: InstrTypes.h:757
ConstantRange truncate(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
bool sgt(const APInt &RHS) const
Signed greather than comparison.
Definition: APInt.h:1273
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:865
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1389
ConstantRange ashr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a arithmetic right shift of a valu...
Metadata node.
Definition: Metadata.h:863
ConstantRange udiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned division of a value in...
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
OverflowResult signedAddMayOverflow(const ConstantRange &Other) const
Return whether signed add of the two ranges always/never overflows.
static ConstantRange makeExactMulNSWRegion(const APInt &V)
Exact mul nsw region for single element RHS.
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A sign-divided by B, rounded by the given rounding mode.
Definition: APInt.cpp:2770
void print(raw_ostream &OS) const
Print out the bounds to a stream.
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:39
uint64_t High
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:534
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1517
bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
Definition: BitVector.h:937
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:831
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:368
APInt zextOrSelf(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:946
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
This file implements a class to represent arbitrary precision integral constant values and operations...
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2118
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1541
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2113
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
Definition: ConstantRange.h:84
int getMaxValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the maximum value of an extendable operand.
OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const
Return whether unsigned mul of the two ranges always/never overflows.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1461
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Get a value with upper bits starting at loBit set.
Definition: APInt.h:623
OverflowResult
Represents whether an operation on the given constant range is known to always or never overflow...
bool isAllNegative() const
Return true if all values in this range are negative.
void dump() const
Allow printing from a debugger easily.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
The operation itself must be expressed in terms of simpler actions on this target.
Definition: LegalizerInfo.h:72
bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the largest range such that all values in the returned range satisfy the given predicate with...
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:95
bool isSizeStrictlySmallerThan(const ConstantRange &CR) const
Compare set size of this range with the range CR.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:635
ConstantRange usub_sat(const ConstantRange &Other) const
Perform an unsigned saturating subtraction of two constant ranges.
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:363
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:395
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
Definition: APInt.h:390
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1184
ConstantRange sadd_sat(const ConstantRange &Other) const
Perform a signed saturating addition of two constant ranges.
bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isOneValue() const
Determine if this is a value of 1.
Definition: APInt.h:410
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:587
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from an addition with wrap type NoWrapK...
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:442
Always overflows in the direction of signed/unsigned max value.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
bool isBinaryOp() const
Definition: Instruction.h:130
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl...
Definition: Operator.h:66
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type. ...
void clearSignBit()
Set the sign bit to 0.
Definition: APInt.h:1478
ConstantRange sdiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed division of a value in th...
static ConstantRange makeExactMulNUWRegion(const APInt &V)
Exact mul nuw region for single element RHS.
OverflowResult signedSubMayOverflow(const ConstantRange &Other) const
Return whether signed sub of the two ranges always/never overflows.
APInt uadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1938
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
APInt ssub_sat(const APInt &RHS) const
Definition: APInt.cpp:2032
OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const
Return whether unsigned sub of the two ranges always/never overflows.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:970
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
signed greater than
Definition: InstrTypes.h:759
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2123
bool isEmptySet() const
Return true if this set contains no members.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:946
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
This class represents a range of values.
Definition: ConstantRange.h:47
signed less than
Definition: InstrTypes.h:761
ConstantRange uadd_sat(const ConstantRange &Other) const
Perform an unsigned saturating addition of two constant ranges.
ConstantRange smin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed minimum of a value in thi...
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:541
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1292
ConstantRange binaryOr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-or of a value in this ran...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1654
signed less or equal
Definition: InstrTypes.h:762
Class for arbitrary precision integers.
Definition: APInt.h:69
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1222
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2128
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:529
const APInt * getSingleMissingElement() const
If this set contains all but a single element, return it, otherwise return null.
ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
bool isUnknown() const
Returns true if we don&#39;t know any bits.
Definition: KnownBits.h:62
#define Success
ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
Definition: APInt.h:1254
ConstantRange ssub_sat(const ConstantRange &Other) const
Perform a signed saturating subtraction of two constant ranges.
unsigned greater or equal
Definition: InstrTypes.h:756
ConstantRange abs() const
Calculate absolute value range.
const APInt & getLower() const
Return the lower value for this range.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1973
bool isSingleElement() const
Return true if this set contains exactly one member.
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:544
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1931
static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
ConstantRange srem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed remainder operation of a ...
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
ConstantRange multiply(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a multiplication of a value in thi...
ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
APInt usub_sat(const APInt &RHS) const
Definition: APInt.cpp:2042
unsigned greater than
Definition: InstrTypes.h:755
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:98
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
Definition: APInt.h:1604
ConstantRange shl(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a left shift of a value in this ra...
static APInt getNullValue(unsigned numBits)
Get the &#39;0&#39; value.
Definition: APInt.h:568
APInt sadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2013
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
static ConstantRange getPreferredRange(const ConstantRange &CR1, const ConstantRange &CR2, ConstantRange::PreferredRangeType Type)
APInt sextOrSelf(unsigned width) const
Sign extend or truncate to width.
Definition: APInt.cpp:952
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:405
signed greater or equal
Definition: InstrTypes.h:760
ConstantRange binaryAnd(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-and of a value in this ra...