LLVM  9.0.0svn
ConstantRange.cpp
Go to the documentation of this file.
1 //===- ConstantRange.cpp - ConstantRange implementation -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Represent a range of possible values that may occur when the program is run
10 // for an integral value. This keeps track of a lower and upper bound for the
11 // constant, which MAY wrap around the end of the numeric range. To do this, it
12 // keeps track of a [lower, upper) bound, which specifies an interval just like
13 // STL iterators. When used with boolean values, the following are important
14 // ranges (other integral ranges use min/max values for special range values):
15 //
16 // [F, F) = {} = Empty set
17 // [T, F) = {T}
18 // [F, T) = {F}
19 // [T, T) = {F, T} = Full set
20 //
21 //===----------------------------------------------------------------------===//
22 
23 #include "llvm/ADT/APInt.h"
24 #include "llvm/Config/llvm-config.h"
25 #include "llvm/IR/ConstantRange.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Metadata.h"
30 #include "llvm/IR/Operator.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/KnownBits.h"
36 #include <algorithm>
37 #include <cassert>
38 #include <cstdint>
39 
40 using namespace llvm;
41 
43  : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
44  Upper(Lower) {}
45 
47  : Lower(std::move(V)), Upper(Lower + 1) {}
48 
50  : Lower(std::move(L)), Upper(std::move(U)) {
51  assert(Lower.getBitWidth() == Upper.getBitWidth() &&
52  "ConstantRange with unequal bit widths");
53  assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
54  "Lower == Upper, but they aren't min or max value!");
55 }
56 
58  bool IsSigned) {
59  assert(!Known.hasConflict() && "Expected valid KnownBits");
60 
61  if (Known.isUnknown())
62  return getFull(Known.getBitWidth());
63 
64  // For unsigned ranges, or signed ranges with known sign bit, create a simple
65  // range between the smallest and largest possible value.
66  if (!IsSigned || Known.isNegative() || Known.isNonNegative())
67  return ConstantRange(Known.One, ~Known.Zero + 1);
68 
69  // If we don't know the sign bit, pick the lower bound as a negative number
70  // and the upper bound as a non-negative one.
71  APInt Lower = Known.One, Upper = ~Known.Zero;
72  Lower.setSignBit();
73  Upper.clearSignBit();
74  return ConstantRange(Lower, Upper + 1);
75 }
76 
78  const ConstantRange &CR) {
79  if (CR.isEmptySet())
80  return CR;
81 
82  uint32_t W = CR.getBitWidth();
83  switch (Pred) {
84  default:
85  llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
86  case CmpInst::ICMP_EQ:
87  return CR;
88  case CmpInst::ICMP_NE:
89  if (CR.isSingleElement())
90  return ConstantRange(CR.getUpper(), CR.getLower());
91  return getFull(W);
92  case CmpInst::ICMP_ULT: {
93  APInt UMax(CR.getUnsignedMax());
94  if (UMax.isMinValue())
95  return getEmpty(W);
96  return ConstantRange(APInt::getMinValue(W), std::move(UMax));
97  }
98  case CmpInst::ICMP_SLT: {
99  APInt SMax(CR.getSignedMax());
100  if (SMax.isMinSignedValue())
101  return getEmpty(W);
102  return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
103  }
104  case CmpInst::ICMP_ULE: {
105  APInt UMax(CR.getUnsignedMax());
106  if (UMax.isMaxValue())
107  return getFull(W);
108  return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
109  }
110  case CmpInst::ICMP_SLE: {
111  APInt SMax(CR.getSignedMax());
112  if (SMax.isMaxSignedValue())
113  return getFull(W);
114  return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
115  }
116  case CmpInst::ICMP_UGT: {
117  APInt UMin(CR.getUnsignedMin());
118  if (UMin.isMaxValue())
119  return getEmpty(W);
120  return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
121  }
122  case CmpInst::ICMP_SGT: {
123  APInt SMin(CR.getSignedMin());
124  if (SMin.isMaxSignedValue())
125  return getEmpty(W);
126  return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
127  }
128  case CmpInst::ICMP_UGE: {
129  APInt UMin(CR.getUnsignedMin());
130  if (UMin.isMinValue())
131  return getFull(W);
132  return ConstantRange(std::move(UMin), APInt::getNullValue(W));
133  }
134  case CmpInst::ICMP_SGE: {
135  APInt SMin(CR.getSignedMin());
136  if (SMin.isMinSignedValue())
137  return getFull(W);
138  return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
139  }
140  }
141 }
142 
144  const ConstantRange &CR) {
145  // Follows from De-Morgan's laws:
146  //
147  // ~(~A union ~B) == A intersect B.
148  //
150  .inverse();
151 }
152 
154  const APInt &C) {
155  // Computes the exact range that is equal to both the constant ranges returned
156  // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
157  // when RHS is a singleton such as an APInt and so the assert is valid.
158  // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
159  // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
160  //
162  return makeAllowedICmpRegion(Pred, C);
163 }
164 
166  APInt &RHS) const {
167  bool Success = false;
168 
169  if (isFullSet() || isEmptySet()) {
171  RHS = APInt(getBitWidth(), 0);
172  Success = true;
173  } else if (auto *OnlyElt = getSingleElement()) {
174  Pred = CmpInst::ICMP_EQ;
175  RHS = *OnlyElt;
176  Success = true;
177  } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
178  Pred = CmpInst::ICMP_NE;
179  RHS = *OnlyMissingElt;
180  Success = true;
181  } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
182  Pred =
184  RHS = getUpper();
185  Success = true;
186  } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
187  Pred =
189  RHS = getLower();
190  Success = true;
191  }
192 
193  assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
194  "Bad result!");
195 
196  return Success;
197 }
198 
201  const ConstantRange &Other,
202  unsigned NoWrapKind) {
203  using OBO = OverflowingBinaryOperator;
204 
205  // Computes the intersection of CR0 and CR1. It is different from
206  // intersectWith in that the ConstantRange returned will only contain elements
207  // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
208  // not, of both X and Y).
209  auto SubsetIntersect =
210  [](const ConstantRange &CR0, const ConstantRange &CR1) {
211  return CR0.inverse().unionWith(CR1.inverse()).inverse();
212  };
213 
214  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
215 
216  assert((NoWrapKind == OBO::NoSignedWrap ||
217  NoWrapKind == OBO::NoUnsignedWrap) &&
218  "NoWrapKind invalid!");
219 
220  unsigned BitWidth = Other.getBitWidth();
221  ConstantRange Result(BitWidth, /* full */ true);
222 
223  switch (BinOp) {
224  default:
225  // Conservative answer: empty set
226  return getEmpty(BitWidth);
227 
228  case Instruction::Add:
229  if (auto *C = Other.getSingleElement())
230  if (C->isNullValue())
231  // Full set: nothing signed / unsigned wraps when added to 0.
232  return getFull(BitWidth);
233 
234  if (NoWrapKind == OBO::NoUnsignedWrap)
235  return ConstantRange(APInt::getNullValue(BitWidth),
236  -Other.getUnsignedMax());
237 
238  if (NoWrapKind == OBO::NoSignedWrap) {
239  const APInt &SignedMin = Other.getSignedMin();
240  const APInt &SignedMax = Other.getSignedMax();
241  if (SignedMax.isStrictlyPositive())
242  Result = SubsetIntersect(
243  Result,
245  APInt::getSignedMinValue(BitWidth) - SignedMax));
246  if (SignedMin.isNegative())
247  Result = SubsetIntersect(
248  Result,
249  ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
250  APInt::getSignedMinValue(BitWidth)));
251  }
252  return Result;
253 
254  case Instruction::Sub:
255  if (auto *C = Other.getSingleElement())
256  if (C->isNullValue())
257  // Full set: nothing signed / unsigned wraps when subtracting 0.
258  return getFull(BitWidth);
259 
260  if (NoWrapKind == OBO::NoUnsignedWrap)
261  return ConstantRange(Other.getUnsignedMax(),
262  APInt::getMinValue(BitWidth));
263 
264  if (NoWrapKind == OBO::NoSignedWrap) {
265  const APInt &SignedMin = Other.getSignedMin();
266  const APInt &SignedMax = Other.getSignedMax();
267  if (SignedMax.isStrictlyPositive())
268  Result = SubsetIntersect(
269  Result,
270  ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax,
271  APInt::getSignedMinValue(BitWidth)));
272  if (SignedMin.isNegative())
273  Result = SubsetIntersect(
274  Result,
276  APInt::getSignedMinValue(BitWidth) + SignedMin));
277  }
278  return Result;
279 
280  case Instruction::Mul: {
281  // Equivalent to calling makeGuaranteedNoWrapRegion() on [V, V+1).
282  const bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
283  const auto makeSingleValueRegion = [Unsigned,
284  BitWidth](APInt V) -> ConstantRange {
285  // Handle special case for 0, -1 and 1. See the last for reason why we
286  // specialize -1 and 1.
287  if (V == 0 || V.isOneValue())
288  return getFull(BitWidth);
289 
290  APInt MinValue, MaxValue;
291  if (Unsigned) {
292  MinValue = APInt::getMinValue(BitWidth);
293  MaxValue = APInt::getMaxValue(BitWidth);
294  } else {
295  MinValue = APInt::getSignedMinValue(BitWidth);
296  MaxValue = APInt::getSignedMaxValue(BitWidth);
297  }
298  // e.g. Returning [-127, 127], represented as [-127, -128).
299  if (!Unsigned && V.isAllOnesValue())
300  return ConstantRange(-MaxValue, MinValue);
301 
302  APInt Lower, Upper;
303  if (!Unsigned && V.isNegative()) {
304  Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP);
305  Upper = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::DOWN);
306  } else if (Unsigned) {
307  Lower = APIntOps::RoundingUDiv(MinValue, V, APInt::Rounding::UP);
308  Upper = APIntOps::RoundingUDiv(MaxValue, V, APInt::Rounding::DOWN);
309  } else {
310  Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP);
311  Upper = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::DOWN);
312  }
313  // ConstantRange ctor take a half inclusive interval [Lower, Upper + 1).
314  // Upper + 1 is guanranteed not to overflow, because |divisor| > 1. 0, -1,
315  // and 1 are already handled as special cases.
316  return ConstantRange(Lower, Upper + 1);
317  };
318 
319  if (Unsigned)
320  return makeSingleValueRegion(Other.getUnsignedMax());
321 
322  return SubsetIntersect(makeSingleValueRegion(Other.getSignedMin()),
323  makeSingleValueRegion(Other.getSignedMax()));
324  }
325  }
326 }
327 
329  return Lower == Upper && Lower.isMaxValue();
330 }
331 
333  return Lower == Upper && Lower.isMinValue();
334 }
335 
337  return Lower.ugt(Upper) && !Upper.isNullValue();
338 }
339 
341  return Lower.ugt(Upper);
342 }
343 
345  return Lower.sgt(Upper) && !Upper.isMinSignedValue();
346 }
347 
349  return Lower.sgt(Upper);
350 }
351 
352 bool
354  assert(getBitWidth() == Other.getBitWidth());
355  if (isFullSet())
356  return false;
357  if (Other.isFullSet())
358  return true;
359  return (Upper - Lower).ult(Other.Upper - Other.Lower);
360 }
361 
362 bool
363 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
364  assert(MaxSize && "MaxSize can't be 0.");
365  // If this a full set, we need special handling to avoid needing an extra bit
366  // to represent the size.
367  if (isFullSet())
368  return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
369 
370  return (Upper - Lower).ugt(MaxSize);
371 }
372 
374  // Empty set is all negative, full set is not.
375  if (isEmptySet())
376  return true;
377  if (isFullSet())
378  return false;
379 
380  return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
381 }
382 
384  // Empty and full set are automatically treated correctly.
385  return !isSignWrappedSet() && Lower.isNonNegative();
386 }
387 
389  if (isFullSet() || isUpperWrapped())
391  return getUpper() - 1;
392 }
393 
395  if (isFullSet() || isWrappedSet())
397  return getLower();
398 }
399 
401  if (isFullSet() || isUpperSignWrapped())
403  return getUpper() - 1;
404 }
405 
407  if (isFullSet() || isSignWrappedSet())
409  return getLower();
410 }
411 
412 bool ConstantRange::contains(const APInt &V) const {
413  if (Lower == Upper)
414  return isFullSet();
415 
416  if (!isUpperWrapped())
417  return Lower.ule(V) && V.ult(Upper);
418  return Lower.ule(V) || V.ult(Upper);
419 }
420 
422  if (isFullSet() || Other.isEmptySet()) return true;
423  if (isEmptySet() || Other.isFullSet()) return false;
424 
425  if (!isUpperWrapped()) {
426  if (Other.isUpperWrapped())
427  return false;
428 
429  return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
430  }
431 
432  if (!Other.isUpperWrapped())
433  return Other.getUpper().ule(Upper) ||
434  Lower.ule(Other.getLower());
435 
436  return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
437 }
438 
440  assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
441  // If the set is empty or full, don't modify the endpoints.
442  if (Lower == Upper)
443  return *this;
444  return ConstantRange(Lower - Val, Upper - Val);
445 }
446 
448  return intersectWith(CR.inverse());
449 }
450 
452  const ConstantRange &CR1, const ConstantRange &CR2,
454  if (Type == ConstantRange::Unsigned) {
455  if (!CR1.isWrappedSet() && CR2.isWrappedSet())
456  return CR1;
457  if (CR1.isWrappedSet() && !CR2.isWrappedSet())
458  return CR2;
459  } else if (Type == ConstantRange::Signed) {
460  if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
461  return CR1;
462  if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
463  return CR2;
464  }
465 
466  if (CR1.isSizeStrictlySmallerThan(CR2))
467  return CR1;
468  return CR2;
469 }
470 
472  PreferredRangeType Type) const {
473  assert(getBitWidth() == CR.getBitWidth() &&
474  "ConstantRange types don't agree!");
475 
476  // Handle common cases.
477  if ( isEmptySet() || CR.isFullSet()) return *this;
478  if (CR.isEmptySet() || isFullSet()) return CR;
479 
480  if (!isUpperWrapped() && CR.isUpperWrapped())
481  return CR.intersectWith(*this, Type);
482 
483  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
484  if (Lower.ult(CR.Lower)) {
485  // L---U : this
486  // L---U : CR
487  if (Upper.ule(CR.Lower))
488  return getEmpty();
489 
490  // L---U : this
491  // L---U : CR
492  if (Upper.ult(CR.Upper))
493  return ConstantRange(CR.Lower, Upper);
494 
495  // L-------U : this
496  // L---U : CR
497  return CR;
498  }
499  // L---U : this
500  // L-------U : CR
501  if (Upper.ult(CR.Upper))
502  return *this;
503 
504  // L-----U : this
505  // L-----U : CR
506  if (Lower.ult(CR.Upper))
507  return ConstantRange(Lower, CR.Upper);
508 
509  // L---U : this
510  // L---U : CR
511  return getEmpty();
512  }
513 
514  if (isUpperWrapped() && !CR.isUpperWrapped()) {
515  if (CR.Lower.ult(Upper)) {
516  // ------U L--- : this
517  // L--U : CR
518  if (CR.Upper.ult(Upper))
519  return CR;
520 
521  // ------U L--- : this
522  // L------U : CR
523  if (CR.Upper.ule(Lower))
524  return ConstantRange(CR.Lower, Upper);
525 
526  // ------U L--- : this
527  // L----------U : CR
528  return getPreferredRange(*this, CR, Type);
529  }
530  if (CR.Lower.ult(Lower)) {
531  // --U L---- : this
532  // L--U : CR
533  if (CR.Upper.ule(Lower))
534  return getEmpty();
535 
536  // --U L---- : this
537  // L------U : CR
538  return ConstantRange(Lower, CR.Upper);
539  }
540 
541  // --U L------ : this
542  // L--U : CR
543  return CR;
544  }
545 
546  if (CR.Upper.ult(Upper)) {
547  // ------U L-- : this
548  // --U L------ : CR
549  if (CR.Lower.ult(Upper))
550  return getPreferredRange(*this, CR, Type);
551 
552  // ----U L-- : this
553  // --U L---- : CR
554  if (CR.Lower.ult(Lower))
555  return ConstantRange(Lower, CR.Upper);
556 
557  // ----U L---- : this
558  // --U L-- : CR
559  return CR;
560  }
561  if (CR.Upper.ule(Lower)) {
562  // --U L-- : this
563  // ----U L---- : CR
564  if (CR.Lower.ult(Lower))
565  return *this;
566 
567  // --U L---- : this
568  // ----U L-- : CR
569  return ConstantRange(CR.Lower, Upper);
570  }
571 
572  // --U L------ : this
573  // ------U L-- : CR
574  return getPreferredRange(*this, CR, Type);
575 }
576 
578  PreferredRangeType Type) const {
579  assert(getBitWidth() == CR.getBitWidth() &&
580  "ConstantRange types don't agree!");
581 
582  if ( isFullSet() || CR.isEmptySet()) return *this;
583  if (CR.isFullSet() || isEmptySet()) return CR;
584 
585  if (!isUpperWrapped() && CR.isUpperWrapped())
586  return CR.unionWith(*this, Type);
587 
588  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
589  // L---U and L---U : this
590  // L---U L---U : CR
591  // result in one of
592  // L---------U
593  // -----U L-----
594  if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower))
595  return getPreferredRange(
596  ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
597 
598  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
599  APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
600 
601  if (L.isNullValue() && U.isNullValue())
602  return getFull();
603 
604  return ConstantRange(std::move(L), std::move(U));
605  }
606 
607  if (!CR.isUpperWrapped()) {
608  // ------U L----- and ------U L----- : this
609  // L--U L--U : CR
610  if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
611  return *this;
612 
613  // ------U L----- : this
614  // L---------U : CR
615  if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
616  return getFull();
617 
618  // ----U L---- : this
619  // L---U : CR
620  // results in one of
621  // ----------U L----
622  // ----U L----------
623  if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower))
624  return getPreferredRange(
625  ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
626 
627  // ----U L----- : this
628  // L----U : CR
629  if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))
630  return ConstantRange(CR.Lower, Upper);
631 
632  // ------U L---- : this
633  // L-----U : CR
634  assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
635  "ConstantRange::unionWith missed a case with one range wrapped");
636  return ConstantRange(Lower, CR.Upper);
637  }
638 
639  // ------U L---- and ------U L---- : this
640  // -U L----------- and ------------U L : CR
641  if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
642  return getFull();
643 
644  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
645  APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
646 
647  return ConstantRange(std::move(L), std::move(U));
648 }
649 
651  uint32_t ResultBitWidth) const {
652  switch (CastOp) {
653  default:
654  llvm_unreachable("unsupported cast type");
655  case Instruction::Trunc:
656  return truncate(ResultBitWidth);
657  case Instruction::SExt:
658  return signExtend(ResultBitWidth);
659  case Instruction::ZExt:
660  return zeroExtend(ResultBitWidth);
661  case Instruction::BitCast:
662  return *this;
663  case Instruction::FPToUI:
664  case Instruction::FPToSI:
665  if (getBitWidth() == ResultBitWidth)
666  return *this;
667  else
668  return getFull();
669  case Instruction::UIToFP: {
670  // TODO: use input range if available
671  auto BW = getBitWidth();
672  APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
673  APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
674  return ConstantRange(std::move(Min), std::move(Max));
675  }
676  case Instruction::SIToFP: {
677  // TODO: use input range if available
678  auto BW = getBitWidth();
679  APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
680  APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
681  return ConstantRange(std::move(SMin), std::move(SMax));
682  }
683  case Instruction::FPTrunc:
684  case Instruction::FPExt:
685  case Instruction::IntToPtr:
686  case Instruction::PtrToInt:
687  case Instruction::AddrSpaceCast:
688  // Conservatively return getFull set.
689  return getFull();
690  };
691 }
692 
694  if (isEmptySet()) return getEmpty(DstTySize);
695 
696  unsigned SrcTySize = getBitWidth();
697  assert(SrcTySize < DstTySize && "Not a value extension");
698  if (isFullSet() || isUpperWrapped()) {
699  // Change into [0, 1 << src bit width)
700  APInt LowerExt(DstTySize, 0);
701  if (!Upper) // special case: [X, 0) -- not really wrapping around
702  LowerExt = Lower.zext(DstTySize);
703  return ConstantRange(std::move(LowerExt),
704  APInt::getOneBitSet(DstTySize, SrcTySize));
705  }
706 
707  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
708 }
709 
711  if (isEmptySet()) return getEmpty(DstTySize);
712 
713  unsigned SrcTySize = getBitWidth();
714  assert(SrcTySize < DstTySize && "Not a value extension");
715 
716  // special case: [X, INT_MIN) -- not really wrapping around
717  if (Upper.isMinSignedValue())
718  return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
719 
720  if (isFullSet() || isSignWrappedSet()) {
721  return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
722  APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
723  }
724 
725  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
726 }
727 
729  assert(getBitWidth() > DstTySize && "Not a value truncation");
730  if (isEmptySet())
731  return getEmpty(DstTySize);
732  if (isFullSet())
733  return getFull(DstTySize);
734 
735  APInt LowerDiv(Lower), UpperDiv(Upper);
736  ConstantRange Union(DstTySize, /*isFullSet=*/false);
737 
738  // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
739  // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
740  // then we do the union with [MaxValue, Upper)
741  if (isUpperWrapped()) {
742  // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
743  // truncated range.
744  if (Upper.getActiveBits() > DstTySize ||
745  Upper.countTrailingOnes() == DstTySize)
746  return getFull(DstTySize);
747 
748  Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
749  UpperDiv.setAllBits();
750 
751  // Union covers the MaxValue case, so return if the remaining range is just
752  // MaxValue(DstTy).
753  if (LowerDiv == UpperDiv)
754  return Union;
755  }
756 
757  // Chop off the most significant bits that are past the destination bitwidth.
758  if (LowerDiv.getActiveBits() > DstTySize) {
759  // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
760  APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
761  LowerDiv -= Adjust;
762  UpperDiv -= Adjust;
763  }
764 
765  unsigned UpperDivWidth = UpperDiv.getActiveBits();
766  if (UpperDivWidth <= DstTySize)
767  return ConstantRange(LowerDiv.trunc(DstTySize),
768  UpperDiv.trunc(DstTySize)).unionWith(Union);
769 
770  // The truncated value wraps around. Check if we can do better than fullset.
771  if (UpperDivWidth == DstTySize + 1) {
772  // Clear the MSB so that UpperDiv wraps around.
773  UpperDiv.clearBit(DstTySize);
774  if (UpperDiv.ult(LowerDiv))
775  return ConstantRange(LowerDiv.trunc(DstTySize),
776  UpperDiv.trunc(DstTySize)).unionWith(Union);
777  }
778 
779  return getFull(DstTySize);
780 }
781 
783  unsigned SrcTySize = getBitWidth();
784  if (SrcTySize > DstTySize)
785  return truncate(DstTySize);
786  if (SrcTySize < DstTySize)
787  return zeroExtend(DstTySize);
788  return *this;
789 }
790 
792  unsigned SrcTySize = getBitWidth();
793  if (SrcTySize > DstTySize)
794  return truncate(DstTySize);
795  if (SrcTySize < DstTySize)
796  return signExtend(DstTySize);
797  return *this;
798 }
799 
801  const ConstantRange &Other) const {
802  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
803 
804  switch (BinOp) {
805  case Instruction::Add:
806  return add(Other);
807  case Instruction::Sub:
808  return sub(Other);
809  case Instruction::Mul:
810  return multiply(Other);
811  case Instruction::UDiv:
812  return udiv(Other);
813  case Instruction::Shl:
814  return shl(Other);
815  case Instruction::LShr:
816  return lshr(Other);
817  case Instruction::AShr:
818  return ashr(Other);
819  case Instruction::And:
820  return binaryAnd(Other);
821  case Instruction::Or:
822  return binaryOr(Other);
823  // Note: floating point operations applied to abstract ranges are just
824  // ideal integer operations with a lossy representation
825  case Instruction::FAdd:
826  return add(Other);
827  case Instruction::FSub:
828  return sub(Other);
829  case Instruction::FMul:
830  return multiply(Other);
831  default:
832  // Conservatively return getFull set.
833  return getFull();
834  }
835 }
836 
839  if (isEmptySet() || Other.isEmptySet())
840  return getEmpty();
841  if (isFullSet() || Other.isFullSet())
842  return getFull();
843 
844  APInt NewLower = getLower() + Other.getLower();
845  APInt NewUpper = getUpper() + Other.getUpper() - 1;
846  if (NewLower == NewUpper)
847  return getFull();
848 
849  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
850  if (X.isSizeStrictlySmallerThan(*this) ||
851  X.isSizeStrictlySmallerThan(Other))
852  // We've wrapped, therefore, full set.
853  return getFull();
854  return X;
855 }
856 
858  // Calculate the subset of this range such that "X + Other" is
859  // guaranteed not to wrap (overflow) for all X in this subset.
860  // makeGuaranteedNoWrapRegion will produce an exact NSW range.
862  ConstantRange(Other),
864  auto NSWConstrainedRange = intersectWith(NSWRange);
865 
866  return NSWConstrainedRange.add(ConstantRange(Other));
867 }
868 
871  if (isEmptySet() || Other.isEmptySet())
872  return getEmpty();
873  if (isFullSet() || Other.isFullSet())
874  return getFull();
875 
876  APInt NewLower = getLower() - Other.getUpper() + 1;
877  APInt NewUpper = getUpper() - Other.getLower();
878  if (NewLower == NewUpper)
879  return getFull();
880 
881  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
882  if (X.isSizeStrictlySmallerThan(*this) ||
883  X.isSizeStrictlySmallerThan(Other))
884  // We've wrapped, therefore, full set.
885  return getFull();
886  return X;
887 }
888 
891  // TODO: If either operand is a single element and the multiply is known to
892  // be non-wrapping, round the result min and max value to the appropriate
893  // multiple of that element. If wrapping is possible, at least adjust the
894  // range according to the greatest power-of-two factor of the single element.
895 
896  if (isEmptySet() || Other.isEmptySet())
897  return getEmpty();
898 
899  // Multiplication is signedness-independent. However different ranges can be
900  // obtained depending on how the input ranges are treated. These different
901  // ranges are all conservatively correct, but one might be better than the
902  // other. We calculate two ranges; one treating the inputs as unsigned
903  // and the other signed, then return the smallest of these ranges.
904 
905  // Unsigned range first.
906  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
907  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
908  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
909  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
910 
911  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
912  this_max * Other_max + 1);
913  ConstantRange UR = Result_zext.truncate(getBitWidth());
914 
915  // If the unsigned range doesn't wrap, and isn't negative then it's a range
916  // from one positive number to another which is as good as we can generate.
917  // In this case, skip the extra work of generating signed ranges which aren't
918  // going to be better than this range.
919  if (!UR.isUpperWrapped() &&
920  (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
921  return UR;
922 
923  // Now the signed range. Because we could be dealing with negative numbers
924  // here, the lower bound is the smallest of the cartesian product of the
925  // lower and upper ranges; for example:
926  // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
927  // Similarly for the upper bound, swapping min for max.
928 
929  this_min = getSignedMin().sext(getBitWidth() * 2);
930  this_max = getSignedMax().sext(getBitWidth() * 2);
931  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
932  Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
933 
934  auto L = {this_min * Other_min, this_min * Other_max,
935  this_max * Other_min, this_max * Other_max};
936  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
937  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
938  ConstantRange SR = Result_sext.truncate(getBitWidth());
939 
940  return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
941 }
942 
945  // X smax Y is: range(smax(X_smin, Y_smin),
946  // smax(X_smax, Y_smax))
947  if (isEmptySet() || Other.isEmptySet())
948  return getEmpty();
949  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
950  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
951  if (NewU == NewL)
952  return getFull();
953  return ConstantRange(std::move(NewL), std::move(NewU));
954 }
955 
958  // X umax Y is: range(umax(X_umin, Y_umin),
959  // umax(X_umax, Y_umax))
960  if (isEmptySet() || Other.isEmptySet())
961  return getEmpty();
963  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
964  if (NewU == NewL)
965  return getFull();
966  return ConstantRange(std::move(NewL), std::move(NewU));
967 }
968 
971  // X smin Y is: range(smin(X_smin, Y_smin),
972  // smin(X_smax, Y_smax))
973  if (isEmptySet() || Other.isEmptySet())
974  return getEmpty();
975  APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
976  APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
977  if (NewU == NewL)
978  return getFull();
979  return ConstantRange(std::move(NewL), std::move(NewU));
980 }
981 
984  // X umin Y is: range(umin(X_umin, Y_umin),
985  // umin(X_umax, Y_umax))
986  if (isEmptySet() || Other.isEmptySet())
987  return getEmpty();
989  APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
990  if (NewU == NewL)
991  return getFull();
992  return ConstantRange(std::move(NewL), std::move(NewU));
993 }
994 
997  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
998  return getEmpty();
999  if (RHS.isFullSet())
1000  return getFull();
1001 
1003 
1004  APInt RHS_umin = RHS.getUnsignedMin();
1005  if (RHS_umin.isNullValue()) {
1006  // We want the lowest value in RHS excluding zero. Usually that would be 1
1007  // except for a range in the form of [X, 1) in which case it would be X.
1008  if (RHS.getUpper() == 1)
1009  RHS_umin = RHS.getLower();
1010  else
1011  RHS_umin = 1;
1012  }
1013 
1014  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
1015 
1016  // If the LHS is Full and the RHS is a wrapped interval containing 1 then
1017  // this could occur.
1018  if (Lower == Upper)
1019  return getFull();
1020 
1021  return ConstantRange(std::move(Lower), std::move(Upper));
1022 }
1023 
1026  if (isEmptySet() || Other.isEmptySet())
1027  return getEmpty();
1028 
1029  // TODO: replace this with something less conservative
1030 
1032  if (umin.isAllOnesValue())
1033  return getFull();
1034  return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
1035 }
1036 
1039  if (isEmptySet() || Other.isEmptySet())
1040  return getEmpty();
1041 
1042  // TODO: replace this with something less conservative
1043 
1045  if (umax.isNullValue())
1046  return getFull();
1047  return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
1048 }
1049 
1052  if (isEmptySet() || Other.isEmptySet())
1053  return getEmpty();
1054 
1055  APInt max = getUnsignedMax();
1056  APInt Other_umax = Other.getUnsignedMax();
1057 
1058  // If we are shifting by maximum amount of
1059  // zero return return the original range.
1060  if (Other_umax.isNullValue())
1061  return *this;
1062  // there's overflow!
1063  if (Other_umax.ugt(max.countLeadingZeros()))
1064  return getFull();
1065 
1066  // FIXME: implement the other tricky cases
1067 
1068  APInt min = getUnsignedMin();
1069  min <<= Other.getUnsignedMin();
1070  max <<= Other_umax;
1071 
1072  return ConstantRange(std::move(min), std::move(max) + 1);
1073 }
1074 
1077  if (isEmptySet() || Other.isEmptySet())
1078  return getEmpty();
1079 
1080  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1081  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1082  if (min == max)
1083  return getFull();
1084 
1085  return ConstantRange(std::move(min), std::move(max));
1086 }
1087 
1090  if (isEmptySet() || Other.isEmptySet())
1091  return getEmpty();
1092 
1093  // May straddle zero, so handle both positive and negative cases.
1094  // 'PosMax' is the upper bound of the result of the ashr
1095  // operation, when Upper of the LHS of ashr is a non-negative.
1096  // number. Since ashr of a non-negative number will result in a
1097  // smaller number, the Upper value of LHS is shifted right with
1098  // the minimum value of 'Other' instead of the maximum value.
1099  APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1100 
1101  // 'PosMin' is the lower bound of the result of the ashr
1102  // operation, when Lower of the LHS is a non-negative number.
1103  // Since ashr of a non-negative number will result in a smaller
1104  // number, the Lower value of LHS is shifted right with the
1105  // maximum value of 'Other'.
1106  APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1107 
1108  // 'NegMax' is the upper bound of the result of the ashr
1109  // operation, when Upper of the LHS of ashr is a negative number.
1110  // Since 'ashr' of a negative number will result in a bigger
1111  // number, the Upper value of LHS is shifted right with the
1112  // maximum value of 'Other'.
1113  APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1114 
1115  // 'NegMin' is the lower bound of the result of the ashr
1116  // operation, when Lower of the LHS of ashr is a negative number.
1117  // Since 'ashr' of a negative number will result in a bigger
1118  // number, the Lower value of LHS is shifted right with the
1119  // minimum value of 'Other'.
1120  APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1121 
1122  APInt max, min;
1123  if (getSignedMin().isNonNegative()) {
1124  // Upper and Lower of LHS are non-negative.
1125  min = PosMin;
1126  max = PosMax;
1127  } else if (getSignedMax().isNegative()) {
1128  // Upper and Lower of LHS are negative.
1129  min = NegMin;
1130  max = NegMax;
1131  } else {
1132  // Upper is non-negative and Lower is negative.
1133  min = NegMin;
1134  max = PosMax;
1135  }
1136  if (min == max)
1137  return getFull();
1138 
1139  return ConstantRange(std::move(min), std::move(max));
1140 }
1141 
1143  if (isFullSet())
1144  return getEmpty();
1145  if (isEmptySet())
1146  return getFull();
1147  return ConstantRange(Upper, Lower);
1148 }
1149 
1151  const ConstantRange &Other) const {
1152  if (isEmptySet() || Other.isEmptySet())
1154 
1155  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1156  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1157 
1158  // a u+ b overflows iff a u> ~b.
1159  if (Min.ugt(~OtherMin))
1161  if (Max.ugt(~OtherMax))
1164 }
1165 
1167  const ConstantRange &Other) const {
1168  if (isEmptySet() || Other.isEmptySet())
1170 
1171  APInt Min = getSignedMin(), Max = getSignedMax();
1172  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1173 
1176 
1177  // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1178  // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1179  if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1180  Min.sgt(SignedMax - OtherMin))
1182  if (Max.isNegative() && OtherMax.isNegative() &&
1183  Max.slt(SignedMin - OtherMax))
1185 
1186  if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1187  Max.sgt(SignedMax - OtherMax))
1189  if (Min.isNegative() && OtherMin.isNegative() &&
1190  Min.slt(SignedMin - OtherMin))
1192 
1194 }
1195 
1197  const ConstantRange &Other) const {
1198  if (isEmptySet() || Other.isEmptySet())
1200 
1201  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1202  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1203 
1204  // a u- b overflows iff a u< b.
1205  if (Max.ult(OtherMin))
1207  if (Min.ult(OtherMax))
1210 }
1211 
1213  const ConstantRange &Other) const {
1214  if (isEmptySet() || Other.isEmptySet())
1216 
1217  APInt Min = getSignedMin(), Max = getSignedMax();
1218  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1219 
1222 
1223  // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
1224  // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
1225  if (Min.isNonNegative() && OtherMax.isNegative() &&
1226  Min.sgt(SignedMax + OtherMax))
1228  if (Max.isNegative() && OtherMin.isNonNegative() &&
1229  Max.slt(SignedMin + OtherMin))
1231 
1232  if (Max.isNonNegative() && OtherMin.isNegative() &&
1233  Max.sgt(SignedMax + OtherMin))
1235  if (Min.isNegative() && OtherMax.isNonNegative() &&
1236  Min.slt(SignedMin + OtherMax))
1238 
1240 }
1241 
1243  const ConstantRange &Other) const {
1244  if (isEmptySet() || Other.isEmptySet())
1246 
1247  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1248  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1249  bool Overflow;
1250 
1251  (void) Min.umul_ov(OtherMin, Overflow);
1252  if (Overflow)
1254 
1255  (void) Max.umul_ov(OtherMax, Overflow);
1256  if (Overflow)
1258 
1260 }
1261 
1263  if (isFullSet())
1264  OS << "full-set";
1265  else if (isEmptySet())
1266  OS << "empty-set";
1267  else
1268  OS << "[" << Lower << "," << Upper << ")";
1269 }
1270 
1271 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1273  print(dbgs());
1274 }
1275 #endif
1276 
1278  const unsigned NumRanges = Ranges.getNumOperands() / 2;
1279  assert(NumRanges >= 1 && "Must have at least one range!");
1280  assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1281 
1282  auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1283  auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1284 
1285  ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1286 
1287  for (unsigned i = 1; i < NumRanges; ++i) {
1288  auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1289  auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1290 
1291  // Note: unionWith will potentially create a range that contains values not
1292  // contained in any of the original N ranges.
1293  CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1294  }
1295 
1296  return CR;
1297 }
ConstantRange(uint32_t BitWidth, bool isFullSet)
Initialize a full or empty set for the specified bit width.
uint64_t CallInst * C
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1412
Type
MessagePack types as defined in the standard, with the exception of Integer being divided into a sign...
Definition: MsgPackReader.h:48
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:833
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
Definition: APInt.cpp:2688
bool isUpperSignWrapped() const
Return true if the (exclusive) upper bound wraps around the signed domain.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const APInt & getUpper() const
Return the upper value for this range.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
ConstantRange addWithNoSignedWrap(const APInt &Other) const
Return a new range representing the possible values resulting from a known NSW addition of a value in...
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:46
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:857
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1203
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1519
This file contains the declarations for metadata subclasses.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:647
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
ConstantRange lshr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a logical right shift of a value i...
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
unsigned less or equal
Definition: InstrTypes.h:672
OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const
Return whether unsigned add of the two ranges always/never overflows.
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...
bool sgt(const APInt &RHS) const
Signed greather than comparison.
Definition: APInt.h:1273
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:810
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1389
ConstantRange ashr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a arithmetic right shift of a valu...
Metadata node.
Definition: Metadata.h:863
ConstantRange udiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned division of a value in...
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
OverflowResult signedAddMayOverflow(const ConstantRange &Other) const
Return whether signed add of the two ranges always/never overflows.
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A sign-divided by B, rounded by the given rounding mode.
Definition: APInt.cpp:2706
void print(raw_ostream &OS) const
Print out the bounds to a stream.
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:39
uint64_t High
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:534
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1508
bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
Definition: BitVector.h:937
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h: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:849
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.
OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const
Return whether unsigned mul of the two ranges always/never overflows.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1461
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Get a value with upper bits starting at loBit set.
Definition: APInt.h:623
OverflowResult
Represents whether an operation on the given constant range is known to always or never overflow...
bool isAllNegative() const
Return true if all values in this range are negative.
void dump() const
Allow printing from a debugger easily.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
The operation itself must be expressed in terms of simpler actions on this target.
Definition: LegalizerInfo.h:72
bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the largest range such that all values in the returned range satisfy the given predicate with...
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:95
bool isSizeStrictlySmallerThan(const ConstantRange &CR) const
Compare set size of this range with the range CR.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:635
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:363
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:395
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
Definition: APInt.h:390
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1184
bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:587
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:442
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h: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. ...
void clearSignBit()
Set the sign bit to 0.
Definition: APInt.h:1471
OverflowResult signedSubMayOverflow(const ConstantRange &Other) const
Return whether signed sub of the two ranges always/never overflows.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const
Return whether unsigned sub of the two ranges always/never overflows.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:970
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
signed greater than
Definition: InstrTypes.h: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:47
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...
bool isUnknown() const
Returns true if we don&#39;t know any bits.
Definition: KnownBits.h:62
#define Success
ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
Definition: APInt.h:1254
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")
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1916
bool isSingleElement() const
Return true if this set contains exactly one member.
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Return the exact range containing all X such that "X BinOpC Y" is guaranteed not to wrap (overflow) f...
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
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
ConstantRange multiply(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a multiplication of a value in thi...
ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
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
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:98
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
Definition: APInt.h:1595
ConstantRange shl(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a left shift of a value in this ra...
static APInt getNullValue(unsigned numBits)
Get the &#39;0&#39; value.
Definition: APInt.h:568
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
static ConstantRange getPreferredRange(const ConstantRange &CR1, const ConstantRange &CR2, ConstantRange::PreferredRangeType Type)
APInt sextOrSelf(unsigned width) const
Sign extend or truncate to width.
Definition: APInt.cpp:897
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:405
signed greater or equal
Definition: InstrTypes.h: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...