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