LLVM  9.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  // Calculate the subset of this range such that "X + Other" is
820  // guaranteed not to wrap (overflow) for all X in this subset.
821  auto NSWRange = ConstantRange::makeExactNoWrapRegion(
823  auto NSWConstrainedRange = intersectWith(NSWRange);
824 
825  return NSWConstrainedRange.add(ConstantRange(Other));
826 }
827 
830  if (isEmptySet() || Other.isEmptySet())
831  return getEmpty();
832  if (isFullSet() || Other.isFullSet())
833  return getFull();
834 
835  APInt NewLower = getLower() - Other.getUpper() + 1;
836  APInt NewUpper = getUpper() - Other.getLower();
837  if (NewLower == NewUpper)
838  return getFull();
839 
840  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
841  if (X.isSizeStrictlySmallerThan(*this) ||
842  X.isSizeStrictlySmallerThan(Other))
843  // We've wrapped, therefore, full set.
844  return getFull();
845  return X;
846 }
847 
850  // TODO: If either operand is a single element and the multiply is known to
851  // be non-wrapping, round the result min and max value to the appropriate
852  // multiple of that element. If wrapping is possible, at least adjust the
853  // range according to the greatest power-of-two factor of the single element.
854 
855  if (isEmptySet() || Other.isEmptySet())
856  return getEmpty();
857 
858  // Multiplication is signedness-independent. However different ranges can be
859  // obtained depending on how the input ranges are treated. These different
860  // ranges are all conservatively correct, but one might be better than the
861  // other. We calculate two ranges; one treating the inputs as unsigned
862  // and the other signed, then return the smallest of these ranges.
863 
864  // Unsigned range first.
865  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
866  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
867  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
868  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
869 
870  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
871  this_max * Other_max + 1);
872  ConstantRange UR = Result_zext.truncate(getBitWidth());
873 
874  // If the unsigned range doesn't wrap, and isn't negative then it's a range
875  // from one positive number to another which is as good as we can generate.
876  // In this case, skip the extra work of generating signed ranges which aren't
877  // going to be better than this range.
878  if (!UR.isUpperWrapped() &&
879  (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
880  return UR;
881 
882  // Now the signed range. Because we could be dealing with negative numbers
883  // here, the lower bound is the smallest of the cartesian product of the
884  // lower and upper ranges; for example:
885  // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
886  // Similarly for the upper bound, swapping min for max.
887 
888  this_min = getSignedMin().sext(getBitWidth() * 2);
889  this_max = getSignedMax().sext(getBitWidth() * 2);
890  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
891  Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
892 
893  auto L = {this_min * Other_min, this_min * Other_max,
894  this_max * Other_min, this_max * Other_max};
895  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
896  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
897  ConstantRange SR = Result_sext.truncate(getBitWidth());
898 
899  return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
900 }
901 
904  // X smax Y is: range(smax(X_smin, Y_smin),
905  // smax(X_smax, Y_smax))
906  if (isEmptySet() || Other.isEmptySet())
907  return getEmpty();
908  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
909  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
910  return getNonEmpty(std::move(NewL), std::move(NewU));
911 }
912 
915  // X umax Y is: range(umax(X_umin, Y_umin),
916  // umax(X_umax, Y_umax))
917  if (isEmptySet() || Other.isEmptySet())
918  return getEmpty();
920  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
921  return getNonEmpty(std::move(NewL), std::move(NewU));
922 }
923 
926  // X smin Y is: range(smin(X_smin, Y_smin),
927  // smin(X_smax, Y_smax))
928  if (isEmptySet() || Other.isEmptySet())
929  return getEmpty();
930  APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
931  APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
932  return getNonEmpty(std::move(NewL), std::move(NewU));
933 }
934 
937  // X umin Y is: range(umin(X_umin, Y_umin),
938  // umin(X_umax, Y_umax))
939  if (isEmptySet() || Other.isEmptySet())
940  return getEmpty();
942  APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
943  return getNonEmpty(std::move(NewL), std::move(NewU));
944 }
945 
948  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
949  return getEmpty();
950 
952 
953  APInt RHS_umin = RHS.getUnsignedMin();
954  if (RHS_umin.isNullValue()) {
955  // We want the lowest value in RHS excluding zero. Usually that would be 1
956  // except for a range in the form of [X, 1) in which case it would be X.
957  if (RHS.getUpper() == 1)
958  RHS_umin = RHS.getLower();
959  else
960  RHS_umin = 1;
961  }
962 
963  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
964  return getNonEmpty(std::move(Lower), std::move(Upper));
965 }
966 
968  // We split up the LHS and RHS into positive and negative components
969  // and then also compute the positive and negative components of the result
970  // separately by combining division results with the appropriate signs.
973  ConstantRange PosFilter(APInt(getBitWidth(), 1), SignedMin);
974  ConstantRange NegFilter(SignedMin, Zero);
975  ConstantRange PosL = intersectWith(PosFilter);
976  ConstantRange NegL = intersectWith(NegFilter);
977  ConstantRange PosR = RHS.intersectWith(PosFilter);
978  ConstantRange NegR = RHS.intersectWith(NegFilter);
979 
980  ConstantRange PosRes = getEmpty();
981  if (!PosL.isEmptySet() && !PosR.isEmptySet())
982  // pos / pos = pos.
983  PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),
984  (PosL.Upper - 1).sdiv(PosR.Lower) + 1);
985 
986  if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
987  // neg / neg = pos.
988  //
989  // We need to deal with one tricky case here: SignedMin / -1 is UB on the
990  // IR level, so we'll want to exclude this case when calculating bounds.
991  // (For APInts the operation is well-defined and yields SignedMin.) We
992  // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
993  APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);
994  if (NegL.Lower.isMinSignedValue() && NegR.Upper.isNullValue()) {
995  // Remove -1 from the LHS. Skip if it's the only element, as this would
996  // leave us with an empty set.
997  if (!NegR.Lower.isAllOnesValue()) {
998  APInt AdjNegRUpper;
999  if (RHS.Lower.isAllOnesValue())
1000  // Negative part of [-1, X] without -1 is [SignedMin, X].
1001  AdjNegRUpper = RHS.Upper;
1002  else
1003  // [X, -1] without -1 is [X, -2].
1004  AdjNegRUpper = NegR.Upper - 1;
1005 
1006  PosRes = PosRes.unionWith(
1007  ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
1008  }
1009 
1010  // Remove SignedMin from the RHS. Skip if it's the only element, as this
1011  // would leave us with an empty set.
1012  if (NegL.Upper != SignedMin + 1) {
1013  APInt AdjNegLLower;
1014  if (Upper == SignedMin + 1)
1015  // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1016  AdjNegLLower = Lower;
1017  else
1018  // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1019  AdjNegLLower = NegL.Lower + 1;
1020 
1021  PosRes = PosRes.unionWith(
1022  ConstantRange(std::move(Lo),
1023  AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
1024  }
1025  } else {
1026  PosRes = PosRes.unionWith(
1027  ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
1028  }
1029  }
1030 
1031  ConstantRange NegRes = getEmpty();
1032  if (!PosL.isEmptySet() && !NegR.isEmptySet())
1033  // pos / neg = neg.
1034  NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
1035  PosL.Lower.sdiv(NegR.Lower) + 1);
1036 
1037  if (!NegL.isEmptySet() && !PosR.isEmptySet())
1038  // neg / pos = neg.
1039  NegRes = NegRes.unionWith(
1040  ConstantRange(NegL.Lower.sdiv(PosR.Lower),
1041  (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));
1042 
1043  // Prefer a non-wrapping signed range here.
1044  ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed);
1045 
1046  // Preserve the zero that we dropped when splitting the LHS by sign.
1047  if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1048  Res = Res.unionWith(ConstantRange(Zero));
1049  return Res;
1050 }
1051 
1053  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
1054  return getEmpty();
1055 
1056  // L % R for L < R is L.
1057  if (getUnsignedMax().ult(RHS.getUnsignedMin()))
1058  return *this;
1059 
1060  // L % R is <= L and < R.
1061  APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
1062  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
1063 }
1064 
1066  if (isEmptySet() || RHS.isEmptySet())
1067  return getEmpty();
1068 
1069  ConstantRange AbsRHS = RHS.abs();
1070  APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1071  APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1072 
1073  // Modulus by zero is UB.
1074  if (MaxAbsRHS.isNullValue())
1075  return getEmpty();
1076 
1077  if (MinAbsRHS.isNullValue())
1078  ++MinAbsRHS;
1079 
1080  APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1081 
1082  if (MinLHS.isNonNegative()) {
1083  // L % R for L < R is L.
1084  if (MaxLHS.ult(MinAbsRHS))
1085  return *this;
1086 
1087  // L % R is <= L and < R.
1088  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1089  return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(Upper));
1090  }
1091 
1092  // Same basic logic as above, but the result is negative.
1093  if (MaxLHS.isNegative()) {
1094  if (MinLHS.ugt(-MinAbsRHS))
1095  return *this;
1096 
1097  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1098  return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1099  }
1100 
1101  // LHS range crosses zero.
1102  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1103  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1104  return ConstantRange(std::move(Lower), std::move(Upper));
1105 }
1106 
1109  if (isEmptySet() || Other.isEmptySet())
1110  return getEmpty();
1111 
1112  // TODO: replace this with something less conservative
1113 
1115  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
1116 }
1117 
1120  if (isEmptySet() || Other.isEmptySet())
1121  return getEmpty();
1122 
1123  // TODO: replace this with something less conservative
1124 
1126  return getNonEmpty(std::move(umax), APInt::getNullValue(getBitWidth()));
1127 }
1128 
1131  if (isEmptySet() || Other.isEmptySet())
1132  return getEmpty();
1133 
1134  APInt max = getUnsignedMax();
1135  APInt Other_umax = Other.getUnsignedMax();
1136 
1137  // If we are shifting by maximum amount of
1138  // zero return return the original range.
1139  if (Other_umax.isNullValue())
1140  return *this;
1141  // there's overflow!
1142  if (Other_umax.ugt(max.countLeadingZeros()))
1143  return getFull();
1144 
1145  // FIXME: implement the other tricky cases
1146 
1147  APInt min = getUnsignedMin();
1148  min <<= Other.getUnsignedMin();
1149  max <<= Other_umax;
1150 
1151  return ConstantRange(std::move(min), std::move(max) + 1);
1152 }
1153 
1156  if (isEmptySet() || Other.isEmptySet())
1157  return getEmpty();
1158 
1159  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1160  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1161  return getNonEmpty(std::move(min), std::move(max));
1162 }
1163 
1166  if (isEmptySet() || Other.isEmptySet())
1167  return getEmpty();
1168 
1169  // May straddle zero, so handle both positive and negative cases.
1170  // 'PosMax' is the upper bound of the result of the ashr
1171  // operation, when Upper of the LHS of ashr is a non-negative.
1172  // number. Since ashr of a non-negative number will result in a
1173  // smaller number, the Upper value of LHS is shifted right with
1174  // the minimum value of 'Other' instead of the maximum value.
1175  APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1176 
1177  // 'PosMin' is the lower bound of the result of the ashr
1178  // operation, when Lower of the LHS is a non-negative number.
1179  // Since ashr of a non-negative number will result in a smaller
1180  // number, the Lower value of LHS is shifted right with the
1181  // maximum value of 'Other'.
1182  APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1183 
1184  // 'NegMax' is the upper bound of the result of the ashr
1185  // operation, when Upper of the LHS of ashr is a negative number.
1186  // Since 'ashr' of a negative number will result in a bigger
1187  // number, the Upper value of LHS is shifted right with the
1188  // maximum value of 'Other'.
1189  APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1190 
1191  // 'NegMin' is the lower bound of the result of the ashr
1192  // operation, when Lower of the LHS of ashr is a negative number.
1193  // Since 'ashr' of a negative number will result in a bigger
1194  // number, the Lower value of LHS is shifted right with the
1195  // minimum value of 'Other'.
1196  APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1197 
1198  APInt max, min;
1199  if (getSignedMin().isNonNegative()) {
1200  // Upper and Lower of LHS are non-negative.
1201  min = PosMin;
1202  max = PosMax;
1203  } else if (getSignedMax().isNegative()) {
1204  // Upper and Lower of LHS are negative.
1205  min = NegMin;
1206  max = NegMax;
1207  } else {
1208  // Upper is non-negative and Lower is negative.
1209  min = NegMin;
1210  max = PosMax;
1211  }
1212  return getNonEmpty(std::move(min), std::move(max));
1213 }
1214 
1216  if (isEmptySet() || Other.isEmptySet())
1217  return getEmpty();
1218 
1219  APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());
1220  APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;
1221  return getNonEmpty(std::move(NewL), std::move(NewU));
1222 }
1223 
1225  if (isEmptySet() || Other.isEmptySet())
1226  return getEmpty();
1227 
1228  APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());
1229  APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;
1230  return getNonEmpty(std::move(NewL), std::move(NewU));
1231 }
1232 
1234  if (isEmptySet() || Other.isEmptySet())
1235  return getEmpty();
1236 
1237  APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());
1238  APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;
1239  return getNonEmpty(std::move(NewL), std::move(NewU));
1240 }
1241 
1243  if (isEmptySet() || Other.isEmptySet())
1244  return getEmpty();
1245 
1246  APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
1247  APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
1248  return getNonEmpty(std::move(NewL), std::move(NewU));
1249 }
1250 
1252  if (isFullSet())
1253  return getEmpty();
1254  if (isEmptySet())
1255  return getFull();
1256  return ConstantRange(Upper, Lower);
1257 }
1258 
1260  if (isEmptySet())
1261  return getEmpty();
1262 
1263  if (isSignWrappedSet()) {
1264  APInt Lo;
1265  // Check whether the range crosses zero.
1266  if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1268  else
1269  Lo = APIntOps::umin(Lower, -Upper + 1);
1270 
1271  // SignedMin is included in the result range.
1273  }
1274 
1275  APInt SMin = getSignedMin(), SMax = getSignedMax();
1276 
1277  // All non-negative.
1278  if (SMin.isNonNegative())
1279  return *this;
1280 
1281  // All negative.
1282  if (SMax.isNegative())
1283  return ConstantRange(-SMax, -SMin + 1);
1284 
1285  // Range crosses zero.
1287  APIntOps::umax(-SMin, SMax) + 1);
1288 }
1289 
1291  const ConstantRange &Other) const {
1292  if (isEmptySet() || Other.isEmptySet())
1294 
1295  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1296  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1297 
1298  // a u+ b overflows high iff a u> ~b.
1299  if (Min.ugt(~OtherMin))
1301  if (Max.ugt(~OtherMax))
1304 }
1305 
1307  const ConstantRange &Other) const {
1308  if (isEmptySet() || Other.isEmptySet())
1310 
1311  APInt Min = getSignedMin(), Max = getSignedMax();
1312  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1313 
1316 
1317  // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1318  // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1319  if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1320  Min.sgt(SignedMax - OtherMin))
1322  if (Max.isNegative() && OtherMax.isNegative() &&
1323  Max.slt(SignedMin - OtherMax))
1325 
1326  if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1327  Max.sgt(SignedMax - OtherMax))
1329  if (Min.isNegative() && OtherMin.isNegative() &&
1330  Min.slt(SignedMin - OtherMin))
1332 
1334 }
1335 
1337  const ConstantRange &Other) const {
1338  if (isEmptySet() || Other.isEmptySet())
1340 
1341  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1342  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1343 
1344  // a u- b overflows low iff a u< b.
1345  if (Max.ult(OtherMin))
1347  if (Min.ult(OtherMax))
1350 }
1351 
1353  const ConstantRange &Other) const {
1354  if (isEmptySet() || Other.isEmptySet())
1356 
1357  APInt Min = getSignedMin(), Max = getSignedMax();
1358  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1359 
1362 
1363  // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
1364  // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
1365  if (Min.isNonNegative() && OtherMax.isNegative() &&
1366  Min.sgt(SignedMax + OtherMax))
1368  if (Max.isNegative() && OtherMin.isNonNegative() &&
1369  Max.slt(SignedMin + OtherMin))
1371 
1372  if (Max.isNonNegative() && OtherMin.isNegative() &&
1373  Max.sgt(SignedMax + OtherMin))
1375  if (Min.isNegative() && OtherMax.isNonNegative() &&
1376  Min.slt(SignedMin + OtherMax))
1378 
1380 }
1381 
1383  const ConstantRange &Other) const {
1384  if (isEmptySet() || Other.isEmptySet())
1386 
1387  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1388  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1389  bool Overflow;
1390 
1391  (void) Min.umul_ov(OtherMin, Overflow);
1392  if (Overflow)
1394 
1395  (void) Max.umul_ov(OtherMax, Overflow);
1396  if (Overflow)
1398 
1400 }
1401 
1403  if (isFullSet())
1404  OS << "full-set";
1405  else if (isEmptySet())
1406  OS << "empty-set";
1407  else
1408  OS << "[" << Lower << "," << Upper << ")";
1409 }
1410 
1411 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1413  print(dbgs());
1414 }
1415 #endif
1416 
1418  const unsigned NumRanges = Ranges.getNumOperands() / 2;
1419  assert(NumRanges >= 1 && "Must have at least one range!");
1420  assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1421 
1422  auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1423  auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1424 
1425  ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1426 
1427  for (unsigned i = 1; i < NumRanges; ++i) {
1428  auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1429  auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1430 
1431  // Note: unionWith will potentially create a range that contains values not
1432  // contained in any of the original N ranges.
1433  CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1434  }
1435 
1436  return CR;
1437 }
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
Type
MessagePack types as defined in the standard, with the exception of Integer being divided into a sign...
Definition: MsgPackReader.h:48
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:833
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
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:2695
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:473
Always overflows in the direction of signed/unsigned min value.
ConstantRange addWithNoSignedWrap(const APInt &Other) const
Return a new range representing the possible values resulting from a known NSW addition of a value in...
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition: APInt.cpp:1590
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:857
APInt uadd_sat(const APInt &RHS) const
Definition: APInt.cpp:1966
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:1519
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.
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:810
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:2713
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:1508
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:891
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.
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:870
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:2109
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1532
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2104
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:45
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.
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:1471
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 getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
APInt ssub_sat(const APInt &RHS) const
Definition: APInt.cpp:1975
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:2114
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...
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:1645
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:2119
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:1916
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
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:1985
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:1595
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:1956
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:897
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...