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  // Conservative answer: empty set
242  return getEmpty(BitWidth);
243 
244  case Instruction::Add: {
245  if (Unsigned)
246  return getNonEmpty(APInt::getNullValue(BitWidth),
247  -Other.getUnsignedMax());
248 
249  APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
250  APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
251  return getNonEmpty(
252  SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal,
253  SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal);
254  }
255 
256  case Instruction::Sub: {
257  if (Unsigned)
258  return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth));
259 
260  APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
261  APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
262  return getNonEmpty(
263  SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal,
264  SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal);
265  }
266 
267  case Instruction::Mul:
268  if (Unsigned)
269  return makeExactMulNUWRegion(Other.getUnsignedMax());
270 
271  return makeExactMulNSWRegion(Other.getSignedMin())
273  }
274 }
275 
277  const APInt &Other,
278  unsigned NoWrapKind) {
279  // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
280  // "for all" and "for any" coincide in this case.
281  return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind);
282 }
283 
285  return Lower == Upper && Lower.isMaxValue();
286 }
287 
289  return Lower == Upper && Lower.isMinValue();
290 }
291 
293  return Lower.ugt(Upper) && !Upper.isNullValue();
294 }
295 
297  return Lower.ugt(Upper);
298 }
299 
301  return Lower.sgt(Upper) && !Upper.isMinSignedValue();
302 }
303 
305  return Lower.sgt(Upper);
306 }
307 
308 bool
310  assert(getBitWidth() == Other.getBitWidth());
311  if (isFullSet())
312  return false;
313  if (Other.isFullSet())
314  return true;
315  return (Upper - Lower).ult(Other.Upper - Other.Lower);
316 }
317 
318 bool
319 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
320  assert(MaxSize && "MaxSize can't be 0.");
321  // If this a full set, we need special handling to avoid needing an extra bit
322  // to represent the size.
323  if (isFullSet())
324  return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
325 
326  return (Upper - Lower).ugt(MaxSize);
327 }
328 
330  // Empty set is all negative, full set is not.
331  if (isEmptySet())
332  return true;
333  if (isFullSet())
334  return false;
335 
336  return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
337 }
338 
340  // Empty and full set are automatically treated correctly.
341  return !isSignWrappedSet() && Lower.isNonNegative();
342 }
343 
345  if (isFullSet() || isUpperWrapped())
347  return getUpper() - 1;
348 }
349 
351  if (isFullSet() || isWrappedSet())
353  return getLower();
354 }
355 
357  if (isFullSet() || isUpperSignWrapped())
359  return getUpper() - 1;
360 }
361 
363  if (isFullSet() || isSignWrappedSet())
365  return getLower();
366 }
367 
368 bool ConstantRange::contains(const APInt &V) const {
369  if (Lower == Upper)
370  return isFullSet();
371 
372  if (!isUpperWrapped())
373  return Lower.ule(V) && V.ult(Upper);
374  return Lower.ule(V) || V.ult(Upper);
375 }
376 
378  if (isFullSet() || Other.isEmptySet()) return true;
379  if (isEmptySet() || Other.isFullSet()) return false;
380 
381  if (!isUpperWrapped()) {
382  if (Other.isUpperWrapped())
383  return false;
384 
385  return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
386  }
387 
388  if (!Other.isUpperWrapped())
389  return Other.getUpper().ule(Upper) ||
390  Lower.ule(Other.getLower());
391 
392  return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
393 }
394 
396  assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
397  // If the set is empty or full, don't modify the endpoints.
398  if (Lower == Upper)
399  return *this;
400  return ConstantRange(Lower - Val, Upper - Val);
401 }
402 
404  return intersectWith(CR.inverse());
405 }
406 
408  const ConstantRange &CR1, const ConstantRange &CR2,
410  if (Type == ConstantRange::Unsigned) {
411  if (!CR1.isWrappedSet() && CR2.isWrappedSet())
412  return CR1;
413  if (CR1.isWrappedSet() && !CR2.isWrappedSet())
414  return CR2;
415  } else if (Type == ConstantRange::Signed) {
416  if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
417  return CR1;
418  if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
419  return CR2;
420  }
421 
422  if (CR1.isSizeStrictlySmallerThan(CR2))
423  return CR1;
424  return CR2;
425 }
426 
428  PreferredRangeType Type) const {
429  assert(getBitWidth() == CR.getBitWidth() &&
430  "ConstantRange types don't agree!");
431 
432  // Handle common cases.
433  if ( isEmptySet() || CR.isFullSet()) return *this;
434  if (CR.isEmptySet() || isFullSet()) return CR;
435 
436  if (!isUpperWrapped() && CR.isUpperWrapped())
437  return CR.intersectWith(*this, Type);
438 
439  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
440  if (Lower.ult(CR.Lower)) {
441  // L---U : this
442  // L---U : CR
443  if (Upper.ule(CR.Lower))
444  return getEmpty();
445 
446  // L---U : this
447  // L---U : CR
448  if (Upper.ult(CR.Upper))
449  return ConstantRange(CR.Lower, Upper);
450 
451  // L-------U : this
452  // L---U : CR
453  return CR;
454  }
455  // L---U : this
456  // L-------U : CR
457  if (Upper.ult(CR.Upper))
458  return *this;
459 
460  // L-----U : this
461  // L-----U : CR
462  if (Lower.ult(CR.Upper))
463  return ConstantRange(Lower, CR.Upper);
464 
465  // L---U : this
466  // L---U : CR
467  return getEmpty();
468  }
469 
470  if (isUpperWrapped() && !CR.isUpperWrapped()) {
471  if (CR.Lower.ult(Upper)) {
472  // ------U L--- : this
473  // L--U : CR
474  if (CR.Upper.ult(Upper))
475  return CR;
476 
477  // ------U L--- : this
478  // L------U : CR
479  if (CR.Upper.ule(Lower))
480  return ConstantRange(CR.Lower, Upper);
481 
482  // ------U L--- : this
483  // L----------U : CR
484  return getPreferredRange(*this, CR, Type);
485  }
486  if (CR.Lower.ult(Lower)) {
487  // --U L---- : this
488  // L--U : CR
489  if (CR.Upper.ule(Lower))
490  return getEmpty();
491 
492  // --U L---- : this
493  // L------U : CR
494  return ConstantRange(Lower, CR.Upper);
495  }
496 
497  // --U L------ : this
498  // L--U : CR
499  return CR;
500  }
501 
502  if (CR.Upper.ult(Upper)) {
503  // ------U L-- : this
504  // --U L------ : CR
505  if (CR.Lower.ult(Upper))
506  return getPreferredRange(*this, CR, Type);
507 
508  // ----U L-- : this
509  // --U L---- : CR
510  if (CR.Lower.ult(Lower))
511  return ConstantRange(Lower, CR.Upper);
512 
513  // ----U L---- : this
514  // --U L-- : CR
515  return CR;
516  }
517  if (CR.Upper.ule(Lower)) {
518  // --U L-- : this
519  // ----U L---- : CR
520  if (CR.Lower.ult(Lower))
521  return *this;
522 
523  // --U L---- : this
524  // ----U L-- : CR
525  return ConstantRange(CR.Lower, Upper);
526  }
527 
528  // --U L------ : this
529  // ------U L-- : CR
530  return getPreferredRange(*this, CR, Type);
531 }
532 
534  PreferredRangeType Type) const {
535  assert(getBitWidth() == CR.getBitWidth() &&
536  "ConstantRange types don't agree!");
537 
538  if ( isFullSet() || CR.isEmptySet()) return *this;
539  if (CR.isFullSet() || isEmptySet()) return CR;
540 
541  if (!isUpperWrapped() && CR.isUpperWrapped())
542  return CR.unionWith(*this, Type);
543 
544  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
545  // L---U and L---U : this
546  // L---U L---U : CR
547  // result in one of
548  // L---------U
549  // -----U L-----
550  if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower))
551  return getPreferredRange(
552  ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
553 
554  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
555  APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
556 
557  if (L.isNullValue() && U.isNullValue())
558  return getFull();
559 
560  return ConstantRange(std::move(L), std::move(U));
561  }
562 
563  if (!CR.isUpperWrapped()) {
564  // ------U L----- and ------U L----- : this
565  // L--U L--U : CR
566  if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
567  return *this;
568 
569  // ------U L----- : this
570  // L---------U : CR
571  if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
572  return getFull();
573 
574  // ----U L---- : this
575  // L---U : CR
576  // results in one of
577  // ----------U L----
578  // ----U L----------
579  if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower))
580  return getPreferredRange(
581  ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
582 
583  // ----U L----- : this
584  // L----U : CR
585  if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))
586  return ConstantRange(CR.Lower, Upper);
587 
588  // ------U L---- : this
589  // L-----U : CR
590  assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
591  "ConstantRange::unionWith missed a case with one range wrapped");
592  return ConstantRange(Lower, CR.Upper);
593  }
594 
595  // ------U L---- and ------U L---- : this
596  // -U L----------- and ------------U L : CR
597  if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
598  return getFull();
599 
600  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
601  APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
602 
603  return ConstantRange(std::move(L), std::move(U));
604 }
605 
607  uint32_t ResultBitWidth) const {
608  switch (CastOp) {
609  default:
610  llvm_unreachable("unsupported cast type");
611  case Instruction::Trunc:
612  return truncate(ResultBitWidth);
613  case Instruction::SExt:
614  return signExtend(ResultBitWidth);
615  case Instruction::ZExt:
616  return zeroExtend(ResultBitWidth);
617  case Instruction::BitCast:
618  return *this;
619  case Instruction::FPToUI:
620  case Instruction::FPToSI:
621  if (getBitWidth() == ResultBitWidth)
622  return *this;
623  else
624  return getFull();
625  case Instruction::UIToFP: {
626  // TODO: use input range if available
627  auto BW = getBitWidth();
628  APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
629  APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
630  return ConstantRange(std::move(Min), std::move(Max));
631  }
632  case Instruction::SIToFP: {
633  // TODO: use input range if available
634  auto BW = getBitWidth();
635  APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
636  APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
637  return ConstantRange(std::move(SMin), std::move(SMax));
638  }
639  case Instruction::FPTrunc:
640  case Instruction::FPExt:
641  case Instruction::IntToPtr:
642  case Instruction::PtrToInt:
643  case Instruction::AddrSpaceCast:
644  // Conservatively return getFull set.
645  return getFull();
646  };
647 }
648 
650  if (isEmptySet()) return getEmpty(DstTySize);
651 
652  unsigned SrcTySize = getBitWidth();
653  assert(SrcTySize < DstTySize && "Not a value extension");
654  if (isFullSet() || isUpperWrapped()) {
655  // Change into [0, 1 << src bit width)
656  APInt LowerExt(DstTySize, 0);
657  if (!Upper) // special case: [X, 0) -- not really wrapping around
658  LowerExt = Lower.zext(DstTySize);
659  return ConstantRange(std::move(LowerExt),
660  APInt::getOneBitSet(DstTySize, SrcTySize));
661  }
662 
663  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
664 }
665 
667  if (isEmptySet()) return getEmpty(DstTySize);
668 
669  unsigned SrcTySize = getBitWidth();
670  assert(SrcTySize < DstTySize && "Not a value extension");
671 
672  // special case: [X, INT_MIN) -- not really wrapping around
673  if (Upper.isMinSignedValue())
674  return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
675 
676  if (isFullSet() || isSignWrappedSet()) {
677  return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
678  APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
679  }
680 
681  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
682 }
683 
685  assert(getBitWidth() > DstTySize && "Not a value truncation");
686  if (isEmptySet())
687  return getEmpty(DstTySize);
688  if (isFullSet())
689  return getFull(DstTySize);
690 
691  APInt LowerDiv(Lower), UpperDiv(Upper);
692  ConstantRange Union(DstTySize, /*isFullSet=*/false);
693 
694  // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
695  // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
696  // then we do the union with [MaxValue, Upper)
697  if (isUpperWrapped()) {
698  // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
699  // truncated range.
700  if (Upper.getActiveBits() > DstTySize ||
701  Upper.countTrailingOnes() == DstTySize)
702  return getFull(DstTySize);
703 
704  Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
705  UpperDiv.setAllBits();
706 
707  // Union covers the MaxValue case, so return if the remaining range is just
708  // MaxValue(DstTy).
709  if (LowerDiv == UpperDiv)
710  return Union;
711  }
712 
713  // Chop off the most significant bits that are past the destination bitwidth.
714  if (LowerDiv.getActiveBits() > DstTySize) {
715  // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
716  APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
717  LowerDiv -= Adjust;
718  UpperDiv -= Adjust;
719  }
720 
721  unsigned UpperDivWidth = UpperDiv.getActiveBits();
722  if (UpperDivWidth <= DstTySize)
723  return ConstantRange(LowerDiv.trunc(DstTySize),
724  UpperDiv.trunc(DstTySize)).unionWith(Union);
725 
726  // The truncated value wraps around. Check if we can do better than fullset.
727  if (UpperDivWidth == DstTySize + 1) {
728  // Clear the MSB so that UpperDiv wraps around.
729  UpperDiv.clearBit(DstTySize);
730  if (UpperDiv.ult(LowerDiv))
731  return ConstantRange(LowerDiv.trunc(DstTySize),
732  UpperDiv.trunc(DstTySize)).unionWith(Union);
733  }
734 
735  return getFull(DstTySize);
736 }
737 
739  unsigned SrcTySize = getBitWidth();
740  if (SrcTySize > DstTySize)
741  return truncate(DstTySize);
742  if (SrcTySize < DstTySize)
743  return zeroExtend(DstTySize);
744  return *this;
745 }
746 
748  unsigned SrcTySize = getBitWidth();
749  if (SrcTySize > DstTySize)
750  return truncate(DstTySize);
751  if (SrcTySize < DstTySize)
752  return signExtend(DstTySize);
753  return *this;
754 }
755 
757  const ConstantRange &Other) const {
758  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
759 
760  switch (BinOp) {
761  case Instruction::Add:
762  return add(Other);
763  case Instruction::Sub:
764  return sub(Other);
765  case Instruction::Mul:
766  return multiply(Other);
767  case Instruction::UDiv:
768  return udiv(Other);
769  case Instruction::URem:
770  return urem(Other);
771  case Instruction::SRem:
772  return srem(Other);
773  case Instruction::Shl:
774  return shl(Other);
775  case Instruction::LShr:
776  return lshr(Other);
777  case Instruction::AShr:
778  return ashr(Other);
779  case Instruction::And:
780  return binaryAnd(Other);
781  case Instruction::Or:
782  return binaryOr(Other);
783  // Note: floating point operations applied to abstract ranges are just
784  // ideal integer operations with a lossy representation
785  case Instruction::FAdd:
786  return add(Other);
787  case Instruction::FSub:
788  return sub(Other);
789  case Instruction::FMul:
790  return multiply(Other);
791  default:
792  // Conservatively return getFull set.
793  return getFull();
794  }
795 }
796 
799  if (isEmptySet() || Other.isEmptySet())
800  return getEmpty();
801  if (isFullSet() || Other.isFullSet())
802  return getFull();
803 
804  APInt NewLower = getLower() + Other.getLower();
805  APInt NewUpper = getUpper() + Other.getUpper() - 1;
806  if (NewLower == NewUpper)
807  return getFull();
808 
809  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
810  if (X.isSizeStrictlySmallerThan(*this) ||
811  X.isSizeStrictlySmallerThan(Other))
812  // We've wrapped, therefore, full set.
813  return getFull();
814  return X;
815 }
816 
818  // Calculate the subset of this range such that "X + Other" is
819  // guaranteed not to wrap (overflow) for all X in this subset.
820  auto NSWRange = ConstantRange::makeExactNoWrapRegion(
822  auto NSWConstrainedRange = intersectWith(NSWRange);
823 
824  return NSWConstrainedRange.add(ConstantRange(Other));
825 }
826 
829  if (isEmptySet() || Other.isEmptySet())
830  return getEmpty();
831  if (isFullSet() || Other.isFullSet())
832  return getFull();
833 
834  APInt NewLower = getLower() - Other.getUpper() + 1;
835  APInt NewUpper = getUpper() - Other.getLower();
836  if (NewLower == NewUpper)
837  return getFull();
838 
839  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
840  if (X.isSizeStrictlySmallerThan(*this) ||
841  X.isSizeStrictlySmallerThan(Other))
842  // We've wrapped, therefore, full set.
843  return getFull();
844  return X;
845 }
846 
849  // TODO: If either operand is a single element and the multiply is known to
850  // be non-wrapping, round the result min and max value to the appropriate
851  // multiple of that element. If wrapping is possible, at least adjust the
852  // range according to the greatest power-of-two factor of the single element.
853 
854  if (isEmptySet() || Other.isEmptySet())
855  return getEmpty();
856 
857  // Multiplication is signedness-independent. However different ranges can be
858  // obtained depending on how the input ranges are treated. These different
859  // ranges are all conservatively correct, but one might be better than the
860  // other. We calculate two ranges; one treating the inputs as unsigned
861  // and the other signed, then return the smallest of these ranges.
862 
863  // Unsigned range first.
864  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
865  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
866  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
867  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
868 
869  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
870  this_max * Other_max + 1);
871  ConstantRange UR = Result_zext.truncate(getBitWidth());
872 
873  // If the unsigned range doesn't wrap, and isn't negative then it's a range
874  // from one positive number to another which is as good as we can generate.
875  // In this case, skip the extra work of generating signed ranges which aren't
876  // going to be better than this range.
877  if (!UR.isUpperWrapped() &&
878  (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
879  return UR;
880 
881  // Now the signed range. Because we could be dealing with negative numbers
882  // here, the lower bound is the smallest of the cartesian product of the
883  // lower and upper ranges; for example:
884  // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
885  // Similarly for the upper bound, swapping min for max.
886 
887  this_min = getSignedMin().sext(getBitWidth() * 2);
888  this_max = getSignedMax().sext(getBitWidth() * 2);
889  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
890  Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
891 
892  auto L = {this_min * Other_min, this_min * Other_max,
893  this_max * Other_min, this_max * Other_max};
894  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
895  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
896  ConstantRange SR = Result_sext.truncate(getBitWidth());
897 
898  return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
899 }
900 
903  // X smax Y is: range(smax(X_smin, Y_smin),
904  // smax(X_smax, Y_smax))
905  if (isEmptySet() || Other.isEmptySet())
906  return getEmpty();
907  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
908  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
909  return getNonEmpty(std::move(NewL), std::move(NewU));
910 }
911 
914  // X umax Y is: range(umax(X_umin, Y_umin),
915  // umax(X_umax, Y_umax))
916  if (isEmptySet() || Other.isEmptySet())
917  return getEmpty();
919  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
920  return getNonEmpty(std::move(NewL), std::move(NewU));
921 }
922 
925  // X smin Y is: range(smin(X_smin, Y_smin),
926  // smin(X_smax, Y_smax))
927  if (isEmptySet() || Other.isEmptySet())
928  return getEmpty();
929  APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
930  APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
931  return getNonEmpty(std::move(NewL), std::move(NewU));
932 }
933 
936  // X umin Y is: range(umin(X_umin, Y_umin),
937  // umin(X_umax, Y_umax))
938  if (isEmptySet() || Other.isEmptySet())
939  return getEmpty();
941  APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
942  return getNonEmpty(std::move(NewL), std::move(NewU));
943 }
944 
947  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
948  return getEmpty();
949 
951 
952  APInt RHS_umin = RHS.getUnsignedMin();
953  if (RHS_umin.isNullValue()) {
954  // We want the lowest value in RHS excluding zero. Usually that would be 1
955  // except for a range in the form of [X, 1) in which case it would be X.
956  if (RHS.getUpper() == 1)
957  RHS_umin = RHS.getLower();
958  else
959  RHS_umin = 1;
960  }
961 
962  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
963  return getNonEmpty(std::move(Lower), std::move(Upper));
964 }
965 
967  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
968  return getEmpty();
969 
970  // L % R for L < R is L.
971  if (getUnsignedMax().ult(RHS.getUnsignedMin()))
972  return *this;
973 
974  // L % R is <= L and < R.
975  APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
976  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
977 }
978 
980  if (isEmptySet() || RHS.isEmptySet())
981  return getEmpty();
982 
983  ConstantRange AbsRHS = RHS.abs();
984  APInt MinAbsRHS = AbsRHS.getUnsignedMin();
985  APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
986 
987  // Modulus by zero is UB.
988  if (MaxAbsRHS.isNullValue())
989  return getEmpty();
990 
991  if (MinAbsRHS.isNullValue())
992  ++MinAbsRHS;
993 
994  APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
995 
996  if (MinLHS.isNonNegative()) {
997  // L % R for L < R is L.
998  if (MaxLHS.ult(MinAbsRHS))
999  return *this;
1000 
1001  // L % R is <= L and < R.
1002  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1003  return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(Upper));
1004  }
1005 
1006  // Same basic logic as above, but the result is negative.
1007  if (MaxLHS.isNegative()) {
1008  if (MinLHS.ugt(-MinAbsRHS))
1009  return *this;
1010 
1011  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1012  return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1013  }
1014 
1015  // LHS range crosses zero.
1016  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1017  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1018  return ConstantRange(std::move(Lower), std::move(Upper));
1019 }
1020 
1023  if (isEmptySet() || Other.isEmptySet())
1024  return getEmpty();
1025 
1026  // TODO: replace this with something less conservative
1027 
1029  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
1030 }
1031 
1034  if (isEmptySet() || Other.isEmptySet())
1035  return getEmpty();
1036 
1037  // TODO: replace this with something less conservative
1038 
1040  return getNonEmpty(std::move(umax), APInt::getNullValue(getBitWidth()));
1041 }
1042 
1045  if (isEmptySet() || Other.isEmptySet())
1046  return getEmpty();
1047 
1048  APInt max = getUnsignedMax();
1049  APInt Other_umax = Other.getUnsignedMax();
1050 
1051  // If we are shifting by maximum amount of
1052  // zero return return the original range.
1053  if (Other_umax.isNullValue())
1054  return *this;
1055  // there's overflow!
1056  if (Other_umax.ugt(max.countLeadingZeros()))
1057  return getFull();
1058 
1059  // FIXME: implement the other tricky cases
1060 
1061  APInt min = getUnsignedMin();
1062  min <<= Other.getUnsignedMin();
1063  max <<= Other_umax;
1064 
1065  return ConstantRange(std::move(min), std::move(max) + 1);
1066 }
1067 
1070  if (isEmptySet() || Other.isEmptySet())
1071  return getEmpty();
1072 
1073  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1074  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1075  return getNonEmpty(std::move(min), std::move(max));
1076 }
1077 
1080  if (isEmptySet() || Other.isEmptySet())
1081  return getEmpty();
1082 
1083  // May straddle zero, so handle both positive and negative cases.
1084  // 'PosMax' is the upper bound of the result of the ashr
1085  // operation, when Upper of the LHS of ashr is a non-negative.
1086  // number. Since ashr of a non-negative number will result in a
1087  // smaller number, the Upper value of LHS is shifted right with
1088  // the minimum value of 'Other' instead of the maximum value.
1089  APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1090 
1091  // 'PosMin' is the lower bound of the result of the ashr
1092  // operation, when Lower of the LHS is a non-negative number.
1093  // Since ashr of a non-negative number will result in a smaller
1094  // number, the Lower value of LHS is shifted right with the
1095  // maximum value of 'Other'.
1096  APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1097 
1098  // 'NegMax' is the upper bound of the result of the ashr
1099  // operation, when Upper of the LHS of ashr is a negative number.
1100  // Since 'ashr' of a negative number will result in a bigger
1101  // number, the Upper value of LHS is shifted right with the
1102  // maximum value of 'Other'.
1103  APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1104 
1105  // 'NegMin' is the lower bound of the result of the ashr
1106  // operation, when Lower of the LHS of ashr is a negative number.
1107  // Since 'ashr' of a negative number will result in a bigger
1108  // number, the Lower value of LHS is shifted right with the
1109  // minimum value of 'Other'.
1110  APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1111 
1112  APInt max, min;
1113  if (getSignedMin().isNonNegative()) {
1114  // Upper and Lower of LHS are non-negative.
1115  min = PosMin;
1116  max = PosMax;
1117  } else if (getSignedMax().isNegative()) {
1118  // Upper and Lower of LHS are negative.
1119  min = NegMin;
1120  max = NegMax;
1121  } else {
1122  // Upper is non-negative and Lower is negative.
1123  min = NegMin;
1124  max = PosMax;
1125  }
1126  return getNonEmpty(std::move(min), std::move(max));
1127 }
1128 
1130  if (isEmptySet() || Other.isEmptySet())
1131  return getEmpty();
1132 
1133  APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());
1134  APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;
1135  return getNonEmpty(std::move(NewL), std::move(NewU));
1136 }
1137 
1139  if (isEmptySet() || Other.isEmptySet())
1140  return getEmpty();
1141 
1142  APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());
1143  APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;
1144  return getNonEmpty(std::move(NewL), std::move(NewU));
1145 }
1146 
1148  if (isEmptySet() || Other.isEmptySet())
1149  return getEmpty();
1150 
1151  APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());
1152  APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;
1153  return getNonEmpty(std::move(NewL), std::move(NewU));
1154 }
1155 
1157  if (isEmptySet() || Other.isEmptySet())
1158  return getEmpty();
1159 
1160  APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
1161  APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
1162  return getNonEmpty(std::move(NewL), std::move(NewU));
1163 }
1164 
1166  if (isFullSet())
1167  return getEmpty();
1168  if (isEmptySet())
1169  return getFull();
1170  return ConstantRange(Upper, Lower);
1171 }
1172 
1174  if (isEmptySet())
1175  return getEmpty();
1176 
1177  if (isSignWrappedSet()) {
1178  APInt Lo;
1179  // Check whether the range crosses zero.
1180  if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1182  else
1183  Lo = APIntOps::umin(Lower, -Upper + 1);
1184 
1185  // SignedMin is included in the result range.
1187  }
1188 
1189  APInt SMin = getSignedMin(), SMax = getSignedMax();
1190 
1191  // All non-negative.
1192  if (SMin.isNonNegative())
1193  return *this;
1194 
1195  // All negative.
1196  if (SMax.isNegative())
1197  return ConstantRange(-SMax, -SMin + 1);
1198 
1199  // Range crosses zero.
1201  APIntOps::umax(-SMin, SMax) + 1);
1202 }
1203 
1205  const ConstantRange &Other) const {
1206  if (isEmptySet() || Other.isEmptySet())
1208 
1209  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1210  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1211 
1212  // a u+ b overflows iff a u> ~b.
1213  if (Min.ugt(~OtherMin))
1215  if (Max.ugt(~OtherMax))
1218 }
1219 
1221  const ConstantRange &Other) const {
1222  if (isEmptySet() || Other.isEmptySet())
1224 
1225  APInt Min = getSignedMin(), Max = getSignedMax();
1226  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1227 
1230 
1231  // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1232  // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1233  if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1234  Min.sgt(SignedMax - OtherMin))
1236  if (Max.isNegative() && OtherMax.isNegative() &&
1237  Max.slt(SignedMin - OtherMax))
1239 
1240  if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1241  Max.sgt(SignedMax - OtherMax))
1243  if (Min.isNegative() && OtherMin.isNegative() &&
1244  Min.slt(SignedMin - OtherMin))
1246 
1248 }
1249 
1251  const ConstantRange &Other) const {
1252  if (isEmptySet() || Other.isEmptySet())
1254 
1255  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1256  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1257 
1258  // a u- b overflows iff a u< b.
1259  if (Max.ult(OtherMin))
1261  if (Min.ult(OtherMax))
1264 }
1265 
1267  const ConstantRange &Other) const {
1268  if (isEmptySet() || Other.isEmptySet())
1270 
1271  APInt Min = getSignedMin(), Max = getSignedMax();
1272  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1273 
1276 
1277  // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
1278  // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
1279  if (Min.isNonNegative() && OtherMax.isNegative() &&
1280  Min.sgt(SignedMax + OtherMax))
1282  if (Max.isNegative() && OtherMin.isNonNegative() &&
1283  Max.slt(SignedMin + OtherMin))
1285 
1286  if (Max.isNonNegative() && OtherMin.isNegative() &&
1287  Max.sgt(SignedMax + OtherMin))
1289  if (Min.isNegative() && OtherMax.isNonNegative() &&
1290  Min.slt(SignedMin + OtherMax))
1292 
1294 }
1295 
1297  const ConstantRange &Other) const {
1298  if (isEmptySet() || Other.isEmptySet())
1300 
1301  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1302  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1303  bool Overflow;
1304 
1305  (void) Min.umul_ov(OtherMin, Overflow);
1306  if (Overflow)
1308 
1309  (void) Max.umul_ov(OtherMax, Overflow);
1310  if (Overflow)
1312 
1314 }
1315 
1317  if (isFullSet())
1318  OS << "full-set";
1319  else if (isEmptySet())
1320  OS << "empty-set";
1321  else
1322  OS << "[" << Lower << "," << Upper << ")";
1323 }
1324 
1325 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1327  print(dbgs());
1328 }
1329 #endif
1330 
1332  const unsigned NumRanges = Ranges.getNumOperands() / 2;
1333  assert(NumRanges >= 1 && "Must have at least one range!");
1334  assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1335 
1336  auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1337  auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1338 
1339  ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1340 
1341  for (unsigned i = 1; i < NumRanges; ++i) {
1342  auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1343  auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1344 
1345  // Note: unionWith will potentially create a range that contains values not
1346  // contained in any of the original N ranges.
1347  CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1348  }
1349 
1350  return CR;
1351 }
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
ConstantRange addWithNoSignedWrap(const APInt &Other) const
Return a new range representing the possible values resulting from a known NSW addition of a value in...
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:735
OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const
Return whether unsigned add of the two ranges always/never overflows.
unsigned less than
Definition: InstrTypes.h:734
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:808
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:851
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
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:709
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
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:736
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:738
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:739
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:733
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:732
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:737
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...