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