LLVM  16.0.0git
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/Intrinsics.h"
30 #include "llvm/IR/Metadata.h"
31 #include "llvm/IR/Operator.h"
32 #include "llvm/Support/Compiler.h"
33 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/KnownBits.h"
37 #include <algorithm>
38 #include <cassert>
39 #include <cstdint>
40 
41 using namespace llvm;
42 
44  : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
45  Upper(Lower) {}
46 
48  : Lower(std::move(V)), Upper(Lower + 1) {}
49 
51  : Lower(std::move(L)), Upper(std::move(U)) {
52  assert(Lower.getBitWidth() == Upper.getBitWidth() &&
53  "ConstantRange with unequal bit widths");
54  assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
55  "Lower == Upper, but they aren't min or max value!");
56 }
57 
59  bool IsSigned) {
60  assert(!Known.hasConflict() && "Expected valid KnownBits");
61 
62  if (Known.isUnknown())
63  return getFull(Known.getBitWidth());
64 
65  // For unsigned ranges, or signed ranges with known sign bit, create a simple
66  // range between the smallest and largest possible value.
67  if (!IsSigned || Known.isNegative() || Known.isNonNegative())
68  return ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1);
69 
70  // If we don't know the sign bit, pick the lower bound as a negative number
71  // and the upper bound as a non-negative one.
72  APInt Lower = Known.getMinValue(), Upper = Known.getMaxValue();
73  Lower.setSignBit();
74  Upper.clearSignBit();
75  return ConstantRange(Lower, Upper + 1);
76 }
77 
79  // TODO: We could return conflicting known bits here, but consumers are
80  // likely not prepared for that.
81  if (isEmptySet())
82  return KnownBits(getBitWidth());
83 
84  // We can only retain the top bits that are the same between min and max.
85  APInt Min = getUnsignedMin();
86  APInt Max = getUnsignedMax();
88  if (Optional<unsigned> DifferentBit =
90  Known.Zero.clearLowBits(*DifferentBit + 1);
91  Known.One.clearLowBits(*DifferentBit + 1);
92  }
93  return Known;
94 }
95 
97  const ConstantRange &CR) {
98  if (CR.isEmptySet())
99  return CR;
100 
101  uint32_t W = CR.getBitWidth();
102  switch (Pred) {
103  default:
104  llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
105  case CmpInst::ICMP_EQ:
106  return CR;
107  case CmpInst::ICMP_NE:
108  if (CR.isSingleElement())
109  return ConstantRange(CR.getUpper(), CR.getLower());
110  return getFull(W);
111  case CmpInst::ICMP_ULT: {
112  APInt UMax(CR.getUnsignedMax());
113  if (UMax.isMinValue())
114  return getEmpty(W);
116  }
117  case CmpInst::ICMP_SLT: {
118  APInt SMax(CR.getSignedMax());
119  if (SMax.isMinSignedValue())
120  return getEmpty(W);
122  }
123  case CmpInst::ICMP_ULE:
124  return getNonEmpty(APInt::getMinValue(W), CR.getUnsignedMax() + 1);
125  case CmpInst::ICMP_SLE:
127  case CmpInst::ICMP_UGT: {
128  APInt UMin(CR.getUnsignedMin());
129  if (UMin.isMaxValue())
130  return getEmpty(W);
132  }
133  case CmpInst::ICMP_SGT: {
134  APInt SMin(CR.getSignedMin());
135  if (SMin.isMaxSignedValue())
136  return getEmpty(W);
138  }
139  case CmpInst::ICMP_UGE:
141  case CmpInst::ICMP_SGE:
143  }
144 }
145 
147  const ConstantRange &CR) {
148  // Follows from De-Morgan's laws:
149  //
150  // ~(~A union ~B) == A intersect B.
151  //
153  .inverse();
154 }
155 
157  const APInt &C) {
158  // Computes the exact range that is equal to both the constant ranges returned
159  // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
160  // when RHS is a singleton such as an APInt and so the assert is valid.
161  // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
162  // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
163  //
165  return makeAllowedICmpRegion(Pred, C);
166 }
167 
169  const ConstantRange &CR1, const ConstantRange &CR2) {
170  if (CR1.isEmptySet() || CR2.isEmptySet())
171  return true;
172 
173  return (CR1.isAllNonNegative() && CR2.isAllNonNegative()) ||
174  (CR1.isAllNegative() && CR2.isAllNegative());
175 }
176 
178  const ConstantRange &CR1, const ConstantRange &CR2) {
179  if (CR1.isEmptySet() || CR2.isEmptySet())
180  return true;
181 
182  return (CR1.isAllNonNegative() && CR2.isAllNegative()) ||
183  (CR1.isAllNegative() && CR2.isAllNonNegative());
184 }
185 
187  CmpInst::Predicate Pred, const ConstantRange &CR1,
188  const ConstantRange &CR2) {
190  "Only for relational integer predicates!");
191 
192  CmpInst::Predicate FlippedSignednessPred =
194 
196  return FlippedSignednessPred;
197 
199  return CmpInst::getInversePredicate(FlippedSignednessPred);
200 
201  return CmpInst::Predicate::BAD_ICMP_PREDICATE;
202 }
203 
205  APInt &RHS, APInt &Offset) const {
206  Offset = APInt(getBitWidth(), 0);
207  if (isFullSet() || isEmptySet()) {
209  RHS = APInt(getBitWidth(), 0);
210  } else if (auto *OnlyElt = getSingleElement()) {
211  Pred = CmpInst::ICMP_EQ;
212  RHS = *OnlyElt;
213  } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
214  Pred = CmpInst::ICMP_NE;
215  RHS = *OnlyMissingElt;
216  } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
217  Pred =
219  RHS = getUpper();
220  } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
221  Pred =
223  RHS = getLower();
224  } else {
225  Pred = CmpInst::ICMP_ULT;
226  RHS = getUpper() - getLower();
227  Offset = -getLower();
228  }
229 
230  assert(ConstantRange::makeExactICmpRegion(Pred, RHS) == add(Offset) &&
231  "Bad result!");
232 }
233 
235  APInt &RHS) const {
236  APInt Offset;
237  getEquivalentICmp(Pred, RHS, Offset);
238  return Offset.isZero();
239 }
240 
242  const ConstantRange &Other) const {
243  return makeSatisfyingICmpRegion(Pred, Other).contains(*this);
244 }
245 
246 /// Exact mul nuw region for single element RHS.
248  unsigned BitWidth = V.getBitWidth();
249  if (V == 0)
250  return ConstantRange::getFull(V.getBitWidth());
251 
256  APInt::Rounding::DOWN) + 1);
257 }
258 
259 /// Exact mul nsw region for single element RHS.
261  // Handle special case for 0, -1 and 1. See the last for reason why we
262  // specialize -1 and 1.
263  unsigned BitWidth = V.getBitWidth();
264  if (V == 0 || V.isOne())
265  return ConstantRange::getFull(BitWidth);
266 
269  // e.g. Returning [-127, 127], represented as [-127, -128).
270  if (V.isAllOnes())
271  return ConstantRange(-MaxValue, MinValue);
272 
273  APInt Lower, Upper;
274  if (V.isNegative()) {
275  Lower = APIntOps::RoundingSDiv(MaxValue, V, APInt::Rounding::UP);
277  } else {
278  Lower = APIntOps::RoundingSDiv(MinValue, V, APInt::Rounding::UP);
280  }
281  // ConstantRange ctor take a half inclusive interval [Lower, Upper + 1).
282  // Upper + 1 is guaranteed not to overflow, because |divisor| > 1. 0, -1,
283  // and 1 are already handled as special cases.
284  return ConstantRange(Lower, Upper + 1);
285 }
286 
289  const ConstantRange &Other,
290  unsigned NoWrapKind) {
291  using OBO = OverflowingBinaryOperator;
292 
293  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
294 
295  assert((NoWrapKind == OBO::NoSignedWrap ||
296  NoWrapKind == OBO::NoUnsignedWrap) &&
297  "NoWrapKind invalid!");
298 
299  bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
300  unsigned BitWidth = Other.getBitWidth();
301 
302  switch (BinOp) {
303  default:
304  llvm_unreachable("Unsupported binary op");
305 
306  case Instruction::Add: {
307  if (Unsigned)
308  return getNonEmpty(APInt::getZero(BitWidth), -Other.getUnsignedMax());
309 
310  APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
311  APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
312  return getNonEmpty(
313  SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal,
314  SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal);
315  }
316 
317  case Instruction::Sub: {
318  if (Unsigned)
319  return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth));
320 
321  APInt SignedMinVal = APInt::getSignedMinValue(BitWidth);
322  APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
323  return getNonEmpty(
324  SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal,
325  SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal);
326  }
327 
328  case Instruction::Mul:
329  if (Unsigned)
330  return makeExactMulNUWRegion(Other.getUnsignedMax());
331 
332  return makeExactMulNSWRegion(Other.getSignedMin())
333  .intersectWith(makeExactMulNSWRegion(Other.getSignedMax()));
334 
335  case Instruction::Shl: {
336  // For given range of shift amounts, if we ignore all illegal shift amounts
337  // (that always produce poison), what shift amount range is left?
338  ConstantRange ShAmt = Other.intersectWith(
339  ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, (BitWidth - 1) + 1)));
340  if (ShAmt.isEmptySet()) {
341  // If the entire range of shift amounts is already poison-producing,
342  // then we can freely add more poison-producing flags ontop of that.
343  return getFull(BitWidth);
344  }
345  // There are some legal shift amounts, we can compute conservatively-correct
346  // range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax
347  // to be at most bitwidth-1, which results in most conservative range.
348  APInt ShAmtUMax = ShAmt.getUnsignedMax();
349  if (Unsigned)
351  APInt::getMaxValue(BitWidth).lshr(ShAmtUMax) + 1);
353  APInt::getSignedMaxValue(BitWidth).ashr(ShAmtUMax) + 1);
354  }
355  }
356 }
357 
359  const APInt &Other,
360  unsigned NoWrapKind) {
361  // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
362  // "for all" and "for any" coincide in this case.
363  return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind);
364 }
365 
367  return Lower == Upper && Lower.isMaxValue();
368 }
369 
371  return Lower == Upper && Lower.isMinValue();
372 }
373 
375  return Lower.ugt(Upper) && !Upper.isZero();
376 }
377 
379  return Lower.ugt(Upper);
380 }
381 
383  return Lower.sgt(Upper) && !Upper.isMinSignedValue();
384 }
385 
387  return Lower.sgt(Upper);
388 }
389 
390 bool
392  assert(getBitWidth() == Other.getBitWidth());
393  if (isFullSet())
394  return false;
395  if (Other.isFullSet())
396  return true;
397  return (Upper - Lower).ult(Other.Upper - Other.Lower);
398 }
399 
400 bool
402  // If this a full set, we need special handling to avoid needing an extra bit
403  // to represent the size.
404  if (isFullSet())
405  return MaxSize == 0 || APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
406 
407  return (Upper - Lower).ugt(MaxSize);
408 }
409 
411  // Empty set is all negative, full set is not.
412  if (isEmptySet())
413  return true;
414  if (isFullSet())
415  return false;
416 
417  return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
418 }
419 
421  // Empty and full set are automatically treated correctly.
422  return !isSignWrappedSet() && Lower.isNonNegative();
423 }
424 
426  if (isFullSet() || isUpperWrapped())
428  return getUpper() - 1;
429 }
430 
432  if (isFullSet() || isWrappedSet())
434  return getLower();
435 }
436 
438  if (isFullSet() || isUpperSignWrapped())
440  return getUpper() - 1;
441 }
442 
444  if (isFullSet() || isSignWrappedSet())
446  return getLower();
447 }
448 
449 bool ConstantRange::contains(const APInt &V) const {
450  if (Lower == Upper)
451  return isFullSet();
452 
453  if (!isUpperWrapped())
454  return Lower.ule(V) && V.ult(Upper);
455  return Lower.ule(V) || V.ult(Upper);
456 }
457 
458 bool ConstantRange::contains(const ConstantRange &Other) const {
459  if (isFullSet() || Other.isEmptySet()) return true;
460  if (isEmptySet() || Other.isFullSet()) return false;
461 
462  if (!isUpperWrapped()) {
463  if (Other.isUpperWrapped())
464  return false;
465 
466  return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
467  }
468 
469  if (!Other.isUpperWrapped())
470  return Other.getUpper().ule(Upper) ||
471  Lower.ule(Other.getLower());
472 
473  return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
474 }
475 
477  if (isEmptySet())
478  return 0;
479 
480  return getUnsignedMax().getActiveBits();
481 }
482 
484  if (isEmptySet())
485  return 0;
486 
489 }
490 
492  assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
493  // If the set is empty or full, don't modify the endpoints.
494  if (Lower == Upper)
495  return *this;
496  return ConstantRange(Lower - Val, Upper - Val);
497 }
498 
500  return intersectWith(CR.inverse());
501 }
502 
504  const ConstantRange &CR1, const ConstantRange &CR2,
506  if (Type == ConstantRange::Unsigned) {
507  if (!CR1.isWrappedSet() && CR2.isWrappedSet())
508  return CR1;
509  if (CR1.isWrappedSet() && !CR2.isWrappedSet())
510  return CR2;
511  } else if (Type == ConstantRange::Signed) {
512  if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
513  return CR1;
514  if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
515  return CR2;
516  }
517 
518  if (CR1.isSizeStrictlySmallerThan(CR2))
519  return CR1;
520  return CR2;
521 }
522 
524  PreferredRangeType Type) const {
525  assert(getBitWidth() == CR.getBitWidth() &&
526  "ConstantRange types don't agree!");
527 
528  // Handle common cases.
529  if ( isEmptySet() || CR.isFullSet()) return *this;
530  if (CR.isEmptySet() || isFullSet()) return CR;
531 
532  if (!isUpperWrapped() && CR.isUpperWrapped())
533  return CR.intersectWith(*this, Type);
534 
535  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
536  if (Lower.ult(CR.Lower)) {
537  // L---U : this
538  // L---U : CR
539  if (Upper.ule(CR.Lower))
540  return getEmpty();
541 
542  // L---U : this
543  // L---U : CR
544  if (Upper.ult(CR.Upper))
545  return ConstantRange(CR.Lower, Upper);
546 
547  // L-------U : this
548  // L---U : CR
549  return CR;
550  }
551  // L---U : this
552  // L-------U : CR
553  if (Upper.ult(CR.Upper))
554  return *this;
555 
556  // L-----U : this
557  // L-----U : CR
558  if (Lower.ult(CR.Upper))
559  return ConstantRange(Lower, CR.Upper);
560 
561  // L---U : this
562  // L---U : CR
563  return getEmpty();
564  }
565 
566  if (isUpperWrapped() && !CR.isUpperWrapped()) {
567  if (CR.Lower.ult(Upper)) {
568  // ------U L--- : this
569  // L--U : CR
570  if (CR.Upper.ult(Upper))
571  return CR;
572 
573  // ------U L--- : this
574  // L------U : CR
575  if (CR.Upper.ule(Lower))
576  return ConstantRange(CR.Lower, Upper);
577 
578  // ------U L--- : this
579  // L----------U : CR
580  return getPreferredRange(*this, CR, Type);
581  }
582  if (CR.Lower.ult(Lower)) {
583  // --U L---- : this
584  // L--U : CR
585  if (CR.Upper.ule(Lower))
586  return getEmpty();
587 
588  // --U L---- : this
589  // L------U : CR
590  return ConstantRange(Lower, CR.Upper);
591  }
592 
593  // --U L------ : this
594  // L--U : CR
595  return CR;
596  }
597 
598  if (CR.Upper.ult(Upper)) {
599  // ------U L-- : this
600  // --U L------ : CR
601  if (CR.Lower.ult(Upper))
602  return getPreferredRange(*this, CR, Type);
603 
604  // ----U L-- : this
605  // --U L---- : CR
606  if (CR.Lower.ult(Lower))
607  return ConstantRange(Lower, CR.Upper);
608 
609  // ----U L---- : this
610  // --U L-- : CR
611  return CR;
612  }
613  if (CR.Upper.ule(Lower)) {
614  // --U L-- : this
615  // ----U L---- : CR
616  if (CR.Lower.ult(Lower))
617  return *this;
618 
619  // --U L---- : this
620  // ----U L-- : CR
621  return ConstantRange(CR.Lower, Upper);
622  }
623 
624  // --U L------ : this
625  // ------U L-- : CR
626  return getPreferredRange(*this, CR, Type);
627 }
628 
630  PreferredRangeType Type) const {
631  assert(getBitWidth() == CR.getBitWidth() &&
632  "ConstantRange types don't agree!");
633 
634  if ( isFullSet() || CR.isEmptySet()) return *this;
635  if (CR.isFullSet() || isEmptySet()) return CR;
636 
637  if (!isUpperWrapped() && CR.isUpperWrapped())
638  return CR.unionWith(*this, Type);
639 
640  if (!isUpperWrapped() && !CR.isUpperWrapped()) {
641  // L---U and L---U : this
642  // L---U L---U : CR
643  // result in one of
644  // L---------U
645  // -----U L-----
646  if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower))
647  return getPreferredRange(
648  ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
649 
650  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
651  APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
652 
653  if (L.isZero() && U.isZero())
654  return getFull();
655 
656  return ConstantRange(std::move(L), std::move(U));
657  }
658 
659  if (!CR.isUpperWrapped()) {
660  // ------U L----- and ------U L----- : this
661  // L--U L--U : CR
662  if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
663  return *this;
664 
665  // ------U L----- : this
666  // L---------U : CR
667  if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
668  return getFull();
669 
670  // ----U L---- : this
671  // L---U : CR
672  // results in one of
673  // ----------U L----
674  // ----U L----------
675  if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower))
676  return getPreferredRange(
677  ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
678 
679  // ----U L----- : this
680  // L----U : CR
681  if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))
682  return ConstantRange(CR.Lower, Upper);
683 
684  // ------U L---- : this
685  // L-----U : CR
686  assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
687  "ConstantRange::unionWith missed a case with one range wrapped");
688  return ConstantRange(Lower, CR.Upper);
689  }
690 
691  // ------U L---- and ------U L---- : this
692  // -U L----------- and ------------U L : CR
693  if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
694  return getFull();
695 
696  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
697  APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
698 
699  return ConstantRange(std::move(L), std::move(U));
700 }
701 
704  // TODO: This can be implemented more efficiently.
705  ConstantRange Result = intersectWith(CR);
706  if (Result == inverse().unionWith(CR.inverse()).inverse())
707  return Result;
708  return std::nullopt;
709 }
710 
713  // TODO: This can be implemented more efficiently.
714  ConstantRange Result = unionWith(CR);
715  if (Result == inverse().intersectWith(CR.inverse()).inverse())
716  return Result;
717  return std::nullopt;
718 }
719 
721  uint32_t ResultBitWidth) const {
722  switch (CastOp) {
723  default:
724  llvm_unreachable("unsupported cast type");
725  case Instruction::Trunc:
726  return truncate(ResultBitWidth);
727  case Instruction::SExt:
728  return signExtend(ResultBitWidth);
729  case Instruction::ZExt:
730  return zeroExtend(ResultBitWidth);
731  case Instruction::BitCast:
732  return *this;
733  case Instruction::FPToUI:
734  case Instruction::FPToSI:
735  if (getBitWidth() == ResultBitWidth)
736  return *this;
737  else
738  return getFull(ResultBitWidth);
739  case Instruction::UIToFP: {
740  // TODO: use input range if available
741  auto BW = getBitWidth();
742  APInt Min = APInt::getMinValue(BW);
743  APInt Max = APInt::getMaxValue(BW);
744  if (ResultBitWidth > BW) {
745  Min = Min.zext(ResultBitWidth);
746  Max = Max.zext(ResultBitWidth);
747  }
748  return ConstantRange(std::move(Min), std::move(Max));
749  }
750  case Instruction::SIToFP: {
751  // TODO: use input range if available
752  auto BW = getBitWidth();
755  if (ResultBitWidth > BW) {
756  SMin = SMin.sext(ResultBitWidth);
757  SMax = SMax.sext(ResultBitWidth);
758  }
760  }
761  case Instruction::FPTrunc:
762  case Instruction::FPExt:
763  case Instruction::IntToPtr:
764  case Instruction::PtrToInt:
765  case Instruction::AddrSpaceCast:
766  // Conservatively return getFull set.
767  return getFull(ResultBitWidth);
768  };
769 }
770 
772  if (isEmptySet()) return getEmpty(DstTySize);
773 
774  unsigned SrcTySize = getBitWidth();
775  assert(SrcTySize < DstTySize && "Not a value extension");
776  if (isFullSet() || isUpperWrapped()) {
777  // Change into [0, 1 << src bit width)
778  APInt LowerExt(DstTySize, 0);
779  if (!Upper) // special case: [X, 0) -- not really wrapping around
780  LowerExt = Lower.zext(DstTySize);
781  return ConstantRange(std::move(LowerExt),
782  APInt::getOneBitSet(DstTySize, SrcTySize));
783  }
784 
785  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
786 }
787 
789  if (isEmptySet()) return getEmpty(DstTySize);
790 
791  unsigned SrcTySize = getBitWidth();
792  assert(SrcTySize < DstTySize && "Not a value extension");
793 
794  // special case: [X, INT_MIN) -- not really wrapping around
795  if (Upper.isMinSignedValue())
796  return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
797 
798  if (isFullSet() || isSignWrappedSet()) {
799  return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
800  APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
801  }
802 
803  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
804 }
805 
807  assert(getBitWidth() > DstTySize && "Not a value truncation");
808  if (isEmptySet())
809  return getEmpty(DstTySize);
810  if (isFullSet())
811  return getFull(DstTySize);
812 
813  APInt LowerDiv(Lower), UpperDiv(Upper);
814  ConstantRange Union(DstTySize, /*isFullSet=*/false);
815 
816  // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
817  // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
818  // then we do the union with [MaxValue, Upper)
819  if (isUpperWrapped()) {
820  // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
821  // truncated range.
822  if (Upper.getActiveBits() > DstTySize ||
823  Upper.countTrailingOnes() == DstTySize)
824  return getFull(DstTySize);
825 
826  Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
827  UpperDiv.setAllBits();
828 
829  // Union covers the MaxValue case, so return if the remaining range is just
830  // MaxValue(DstTy).
831  if (LowerDiv == UpperDiv)
832  return Union;
833  }
834 
835  // Chop off the most significant bits that are past the destination bitwidth.
836  if (LowerDiv.getActiveBits() > DstTySize) {
837  // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
838  APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
839  LowerDiv -= Adjust;
840  UpperDiv -= Adjust;
841  }
842 
843  unsigned UpperDivWidth = UpperDiv.getActiveBits();
844  if (UpperDivWidth <= DstTySize)
845  return ConstantRange(LowerDiv.trunc(DstTySize),
846  UpperDiv.trunc(DstTySize)).unionWith(Union);
847 
848  // The truncated value wraps around. Check if we can do better than fullset.
849  if (UpperDivWidth == DstTySize + 1) {
850  // Clear the MSB so that UpperDiv wraps around.
851  UpperDiv.clearBit(DstTySize);
852  if (UpperDiv.ult(LowerDiv))
853  return ConstantRange(LowerDiv.trunc(DstTySize),
854  UpperDiv.trunc(DstTySize)).unionWith(Union);
855  }
856 
857  return getFull(DstTySize);
858 }
859 
861  unsigned SrcTySize = getBitWidth();
862  if (SrcTySize > DstTySize)
863  return truncate(DstTySize);
864  if (SrcTySize < DstTySize)
865  return zeroExtend(DstTySize);
866  return *this;
867 }
868 
870  unsigned SrcTySize = getBitWidth();
871  if (SrcTySize > DstTySize)
872  return truncate(DstTySize);
873  if (SrcTySize < DstTySize)
874  return signExtend(DstTySize);
875  return *this;
876 }
877 
879  const ConstantRange &Other) const {
880  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
881 
882  switch (BinOp) {
883  case Instruction::Add:
884  return add(Other);
885  case Instruction::Sub:
886  return sub(Other);
887  case Instruction::Mul:
888  return multiply(Other);
889  case Instruction::UDiv:
890  return udiv(Other);
891  case Instruction::SDiv:
892  return sdiv(Other);
893  case Instruction::URem:
894  return urem(Other);
895  case Instruction::SRem:
896  return srem(Other);
897  case Instruction::Shl:
898  return shl(Other);
899  case Instruction::LShr:
900  return lshr(Other);
901  case Instruction::AShr:
902  return ashr(Other);
903  case Instruction::And:
904  return binaryAnd(Other);
905  case Instruction::Or:
906  return binaryOr(Other);
907  case Instruction::Xor:
908  return binaryXor(Other);
909  // Note: floating point operations applied to abstract ranges are just
910  // ideal integer operations with a lossy representation
911  case Instruction::FAdd:
912  return add(Other);
913  case Instruction::FSub:
914  return sub(Other);
915  case Instruction::FMul:
916  return multiply(Other);
917  default:
918  // Conservatively return getFull set.
919  return getFull();
920  }
921 }
922 
924  const ConstantRange &Other,
925  unsigned NoWrapKind) const {
926  assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
927 
928  switch (BinOp) {
929  case Instruction::Add:
930  return addWithNoWrap(Other, NoWrapKind);
931  case Instruction::Sub:
932  return subWithNoWrap(Other, NoWrapKind);
933  default:
934  // Don't know about this Overflowing Binary Operation.
935  // Conservatively fallback to plain binop handling.
936  return binaryOp(BinOp, Other);
937  }
938 }
939 
941  switch (IntrinsicID) {
942  case Intrinsic::uadd_sat:
943  case Intrinsic::usub_sat:
944  case Intrinsic::sadd_sat:
945  case Intrinsic::ssub_sat:
946  case Intrinsic::umin:
947  case Intrinsic::umax:
948  case Intrinsic::smin:
949  case Intrinsic::smax:
950  case Intrinsic::abs:
951  return true;
952  default:
953  return false;
954  }
955 }
956 
959  switch (IntrinsicID) {
960  case Intrinsic::uadd_sat:
961  return Ops[0].uadd_sat(Ops[1]);
962  case Intrinsic::usub_sat:
963  return Ops[0].usub_sat(Ops[1]);
964  case Intrinsic::sadd_sat:
965  return Ops[0].sadd_sat(Ops[1]);
966  case Intrinsic::ssub_sat:
967  return Ops[0].ssub_sat(Ops[1]);
968  case Intrinsic::umin:
969  return Ops[0].umin(Ops[1]);
970  case Intrinsic::umax:
971  return Ops[0].umax(Ops[1]);
972  case Intrinsic::smin:
973  return Ops[0].smin(Ops[1]);
974  case Intrinsic::smax:
975  return Ops[0].smax(Ops[1]);
976  case Intrinsic::abs: {
977  const APInt *IntMinIsPoison = Ops[1].getSingleElement();
978  assert(IntMinIsPoison && "Must be known (immarg)");
979  assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean");
980  return Ops[0].abs(IntMinIsPoison->getBoolValue());
981  }
982  default:
983  assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported");
984  llvm_unreachable("Unsupported intrinsic");
985  }
986 }
987 
989 ConstantRange::add(const ConstantRange &Other) const {
990  if (isEmptySet() || Other.isEmptySet())
991  return getEmpty();
992  if (isFullSet() || Other.isFullSet())
993  return getFull();
994 
995  APInt NewLower = getLower() + Other.getLower();
996  APInt NewUpper = getUpper() + Other.getUpper() - 1;
997  if (NewLower == NewUpper)
998  return getFull();
999 
1000  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1001  if (X.isSizeStrictlySmallerThan(*this) ||
1002  X.isSizeStrictlySmallerThan(Other))
1003  // We've wrapped, therefore, full set.
1004  return getFull();
1005  return X;
1006 }
1007 
1009  unsigned NoWrapKind,
1010  PreferredRangeType RangeType) const {
1011  // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
1012  // (X is from this, and Y is from Other)
1013  if (isEmptySet() || Other.isEmptySet())
1014  return getEmpty();
1015  if (isFullSet() && Other.isFullSet())
1016  return getFull();
1017 
1018  using OBO = OverflowingBinaryOperator;
1019  ConstantRange Result = add(Other);
1020 
1021  // If an overflow happens for every value pair in these two constant ranges,
1022  // we must return Empty set. In this case, we get that for free, because we
1023  // get lucky that intersection of add() with uadd_sat()/sadd_sat() results
1024  // in an empty set.
1025 
1026  if (NoWrapKind & OBO::NoSignedWrap)
1027  Result = Result.intersectWith(sadd_sat(Other), RangeType);
1028 
1029  if (NoWrapKind & OBO::NoUnsignedWrap)
1030  Result = Result.intersectWith(uadd_sat(Other), RangeType);
1031 
1032  return Result;
1033 }
1034 
1036 ConstantRange::sub(const ConstantRange &Other) const {
1037  if (isEmptySet() || Other.isEmptySet())
1038  return getEmpty();
1039  if (isFullSet() || Other.isFullSet())
1040  return getFull();
1041 
1042  APInt NewLower = getLower() - Other.getUpper() + 1;
1043  APInt NewUpper = getUpper() - Other.getLower();
1044  if (NewLower == NewUpper)
1045  return getFull();
1046 
1047  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1048  if (X.isSizeStrictlySmallerThan(*this) ||
1049  X.isSizeStrictlySmallerThan(Other))
1050  // We've wrapped, therefore, full set.
1051  return getFull();
1052  return X;
1053 }
1054 
1056  unsigned NoWrapKind,
1057  PreferredRangeType RangeType) const {
1058  // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).
1059  // (X is from this, and Y is from Other)
1060  if (isEmptySet() || Other.isEmptySet())
1061  return getEmpty();
1062  if (isFullSet() && Other.isFullSet())
1063  return getFull();
1064 
1065  using OBO = OverflowingBinaryOperator;
1066  ConstantRange Result = sub(Other);
1067 
1068  // If an overflow happens for every value pair in these two constant ranges,
1069  // we must return Empty set. In signed case, we get that for free, because we
1070  // get lucky that intersection of sub() with ssub_sat() results in an
1071  // empty set. But for unsigned we must perform the overflow check manually.
1072 
1073  if (NoWrapKind & OBO::NoSignedWrap)
1074  Result = Result.intersectWith(ssub_sat(Other), RangeType);
1075 
1076  if (NoWrapKind & OBO::NoUnsignedWrap) {
1077  if (getUnsignedMax().ult(Other.getUnsignedMin()))
1078  return getEmpty(); // Always overflows.
1079  Result = Result.intersectWith(usub_sat(Other), RangeType);
1080  }
1081 
1082  return Result;
1083 }
1084 
1087  // TODO: If either operand is a single element and the multiply is known to
1088  // be non-wrapping, round the result min and max value to the appropriate
1089  // multiple of that element. If wrapping is possible, at least adjust the
1090  // range according to the greatest power-of-two factor of the single element.
1091 
1092  if (isEmptySet() || Other.isEmptySet())
1093  return getEmpty();
1094 
1095  // Multiplication is signedness-independent. However different ranges can be
1096  // obtained depending on how the input ranges are treated. These different
1097  // ranges are all conservatively correct, but one might be better than the
1098  // other. We calculate two ranges; one treating the inputs as unsigned
1099  // and the other signed, then return the smallest of these ranges.
1100 
1101  // Unsigned range first.
1102  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
1103  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
1104  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
1105  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
1106 
1107  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
1108  this_max * Other_max + 1);
1109  ConstantRange UR = Result_zext.truncate(getBitWidth());
1110 
1111  // If the unsigned range doesn't wrap, and isn't negative then it's a range
1112  // from one positive number to another which is as good as we can generate.
1113  // In this case, skip the extra work of generating signed ranges which aren't
1114  // going to be better than this range.
1115  if (!UR.isUpperWrapped() &&
1116  (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
1117  return UR;
1118 
1119  // Now the signed range. Because we could be dealing with negative numbers
1120  // here, the lower bound is the smallest of the cartesian product of the
1121  // lower and upper ranges; for example:
1122  // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1123  // Similarly for the upper bound, swapping min for max.
1124 
1125  this_min = getSignedMin().sext(getBitWidth() * 2);
1126  this_max = getSignedMax().sext(getBitWidth() * 2);
1127  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
1128  Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
1129 
1130  auto L = {this_min * Other_min, this_min * Other_max,
1131  this_max * Other_min, this_max * Other_max};
1132  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1133  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
1134  ConstantRange SR = Result_sext.truncate(getBitWidth());
1135 
1136  return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
1137 }
1138 
1140  if (isEmptySet() || Other.isEmptySet())
1141  return getEmpty();
1142 
1143  APInt Min = getSignedMin();
1144  APInt Max = getSignedMax();
1145  APInt OtherMin = Other.getSignedMin();
1146  APInt OtherMax = Other.getSignedMax();
1147 
1148  bool O1, O2, O3, O4;
1149  auto Muls = {Min.smul_ov(OtherMin, O1), Min.smul_ov(OtherMax, O2),
1150  Max.smul_ov(OtherMin, O3), Max.smul_ov(OtherMax, O4)};
1151  if (O1 || O2 || O3 || O4)
1152  return getFull();
1153 
1154  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1155  return getNonEmpty(std::min(Muls, Compare), std::max(Muls, Compare) + 1);
1156 }
1157 
1159 ConstantRange::smax(const ConstantRange &Other) const {
1160  // X smax Y is: range(smax(X_smin, Y_smin),
1161  // smax(X_smax, Y_smax))
1162  if (isEmptySet() || Other.isEmptySet())
1163  return getEmpty();
1164  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
1165  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
1166  ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1167  if (isSignWrappedSet() || Other.isSignWrappedSet())
1168  return Res.intersectWith(unionWith(Other, Signed), Signed);
1169  return Res;
1170 }
1171 
1173 ConstantRange::umax(const ConstantRange &Other) const {
1174  // X umax Y is: range(umax(X_umin, Y_umin),
1175  // umax(X_umax, Y_umax))
1176  if (isEmptySet() || Other.isEmptySet())
1177  return getEmpty();
1178  APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
1179  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1180  ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1181  if (isWrappedSet() || Other.isWrappedSet())
1183  return Res;
1184 }
1185 
1187 ConstantRange::smin(const ConstantRange &Other) const {
1188  // X smin Y is: range(smin(X_smin, Y_smin),
1189  // smin(X_smax, Y_smax))
1190  if (isEmptySet() || Other.isEmptySet())
1191  return getEmpty();
1192  APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
1193  APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
1194  ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1195  if (isSignWrappedSet() || Other.isSignWrappedSet())
1196  return Res.intersectWith(unionWith(Other, Signed), Signed);
1197  return Res;
1198 }
1199 
1201 ConstantRange::umin(const ConstantRange &Other) const {
1202  // X umin Y is: range(umin(X_umin, Y_umin),
1203  // umin(X_umax, Y_umax))
1204  if (isEmptySet() || Other.isEmptySet())
1205  return getEmpty();
1206  APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
1207  APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1208  ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1209  if (isWrappedSet() || Other.isWrappedSet())
1211  return Res;
1212 }
1213 
1216  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1217  return getEmpty();
1218 
1219  APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
1220 
1221  APInt RHS_umin = RHS.getUnsignedMin();
1222  if (RHS_umin.isZero()) {
1223  // We want the lowest value in RHS excluding zero. Usually that would be 1
1224  // except for a range in the form of [X, 1) in which case it would be X.
1225  if (RHS.getUpper() == 1)
1226  RHS_umin = RHS.getLower();
1227  else
1228  RHS_umin = 1;
1229  }
1230 
1231  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
1232  return getNonEmpty(std::move(Lower), std::move(Upper));
1233 }
1234 
1236  // We split up the LHS and RHS into positive and negative components
1237  // and then also compute the positive and negative components of the result
1238  // separately by combining division results with the appropriate signs.
1239  APInt Zero = APInt::getZero(getBitWidth());
1241  // There are no positive 1-bit values. The 1 would get interpreted as -1.
1242  ConstantRange PosFilter =
1243  getBitWidth() == 1 ? getEmpty()
1244  : ConstantRange(APInt(getBitWidth(), 1), SignedMin);
1245  ConstantRange NegFilter(SignedMin, Zero);
1246  ConstantRange PosL = intersectWith(PosFilter);
1247  ConstantRange NegL = intersectWith(NegFilter);
1248  ConstantRange PosR = RHS.intersectWith(PosFilter);
1249  ConstantRange NegR = RHS.intersectWith(NegFilter);
1250 
1251  ConstantRange PosRes = getEmpty();
1252  if (!PosL.isEmptySet() && !PosR.isEmptySet())
1253  // pos / pos = pos.
1254  PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),
1255  (PosL.Upper - 1).sdiv(PosR.Lower) + 1);
1256 
1257  if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1258  // neg / neg = pos.
1259  //
1260  // We need to deal with one tricky case here: SignedMin / -1 is UB on the
1261  // IR level, so we'll want to exclude this case when calculating bounds.
1262  // (For APInts the operation is well-defined and yields SignedMin.) We
1263  // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1264  APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);
1265  if (NegL.Lower.isMinSignedValue() && NegR.Upper.isZero()) {
1266  // Remove -1 from the LHS. Skip if it's the only element, as this would
1267  // leave us with an empty set.
1268  if (!NegR.Lower.isAllOnes()) {
1269  APInt AdjNegRUpper;
1270  if (RHS.Lower.isAllOnes())
1271  // Negative part of [-1, X] without -1 is [SignedMin, X].
1272  AdjNegRUpper = RHS.Upper;
1273  else
1274  // [X, -1] without -1 is [X, -2].
1275  AdjNegRUpper = NegR.Upper - 1;
1276 
1277  PosRes = PosRes.unionWith(
1278  ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
1279  }
1280 
1281  // Remove SignedMin from the RHS. Skip if it's the only element, as this
1282  // would leave us with an empty set.
1283  if (NegL.Upper != SignedMin + 1) {
1284  APInt AdjNegLLower;
1285  if (Upper == SignedMin + 1)
1286  // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1287  AdjNegLLower = Lower;
1288  else
1289  // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1290  AdjNegLLower = NegL.Lower + 1;
1291 
1292  PosRes = PosRes.unionWith(
1294  AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
1295  }
1296  } else {
1297  PosRes = PosRes.unionWith(
1298  ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
1299  }
1300  }
1301 
1302  ConstantRange NegRes = getEmpty();
1303  if (!PosL.isEmptySet() && !NegR.isEmptySet())
1304  // pos / neg = neg.
1305  NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
1306  PosL.Lower.sdiv(NegR.Lower) + 1);
1307 
1308  if (!NegL.isEmptySet() && !PosR.isEmptySet())
1309  // neg / pos = neg.
1310  NegRes = NegRes.unionWith(
1311  ConstantRange(NegL.Lower.sdiv(PosR.Lower),
1312  (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));
1313 
1314  // Prefer a non-wrapping signed range here.
1315  ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed);
1316 
1317  // Preserve the zero that we dropped when splitting the LHS by sign.
1318  if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1319  Res = Res.unionWith(ConstantRange(Zero));
1320  return Res;
1321 }
1322 
1324  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1325  return getEmpty();
1326 
1327  if (const APInt *RHSInt = RHS.getSingleElement()) {
1328  // UREM by null is UB.
1329  if (RHSInt->isZero())
1330  return getEmpty();
1331  // Use APInt's implementation of UREM for single element ranges.
1332  if (const APInt *LHSInt = getSingleElement())
1333  return {LHSInt->urem(*RHSInt)};
1334  }
1335 
1336  // L % R for L < R is L.
1337  if (getUnsignedMax().ult(RHS.getUnsignedMin()))
1338  return *this;
1339 
1340  // L % R is <= L and < R.
1341  APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
1343 }
1344 
1346  if (isEmptySet() || RHS.isEmptySet())
1347  return getEmpty();
1348 
1349  if (const APInt *RHSInt = RHS.getSingleElement()) {
1350  // SREM by null is UB.
1351  if (RHSInt->isZero())
1352  return getEmpty();
1353  // Use APInt's implementation of SREM for single element ranges.
1354  if (const APInt *LHSInt = getSingleElement())
1355  return {LHSInt->srem(*RHSInt)};
1356  }
1357 
1358  ConstantRange AbsRHS = RHS.abs();
1359  APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1360  APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1361 
1362  // Modulus by zero is UB.
1363  if (MaxAbsRHS.isZero())
1364  return getEmpty();
1365 
1366  if (MinAbsRHS.isZero())
1367  ++MinAbsRHS;
1368 
1369  APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1370 
1371  if (MinLHS.isNonNegative()) {
1372  // L % R for L < R is L.
1373  if (MaxLHS.ult(MinAbsRHS))
1374  return *this;
1375 
1376  // L % R is <= L and < R.
1377  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1379  }
1380 
1381  // Same basic logic as above, but the result is negative.
1382  if (MaxLHS.isNegative()) {
1383  if (MinLHS.ugt(-MinAbsRHS))
1384  return *this;
1385 
1386  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1387  return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1388  }
1389 
1390  // LHS range crosses zero.
1391  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1392  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1393  return ConstantRange(std::move(Lower), std::move(Upper));
1394 }
1395 
1397  return ConstantRange(APInt::getAllOnes(getBitWidth())).sub(*this);
1398 }
1399 
1401  if (isEmptySet() || Other.isEmptySet())
1402  return getEmpty();
1403 
1404  ConstantRange KnownBitsRange =
1405  fromKnownBits(toKnownBits() & Other.toKnownBits(), false);
1406  ConstantRange UMinUMaxRange =
1408  APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()) + 1);
1409  return KnownBitsRange.intersectWith(UMinUMaxRange);
1410 }
1411 
1413  if (isEmptySet() || Other.isEmptySet())
1414  return getEmpty();
1415 
1416  ConstantRange KnownBitsRange =
1417  fromKnownBits(toKnownBits() | Other.toKnownBits(), false);
1418  // Upper wrapped range.
1419  ConstantRange UMaxUMinRange =
1420  getNonEmpty(APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()),
1422  return KnownBitsRange.intersectWith(UMaxUMinRange);
1423 }
1424 
1426  if (isEmptySet() || Other.isEmptySet())
1427  return getEmpty();
1428 
1429  // Use APInt's implementation of XOR for single element ranges.
1430  if (isSingleElement() && Other.isSingleElement())
1431  return {*getSingleElement() ^ *Other.getSingleElement()};
1432 
1433  // Special-case binary complement, since we can give a precise answer.
1434  if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes())
1435  return binaryNot();
1436  if (isSingleElement() && getSingleElement()->isAllOnes())
1437  return Other.binaryNot();
1438 
1439  return fromKnownBits(toKnownBits() ^ Other.toKnownBits(), /*IsSigned*/false);
1440 }
1441 
1443 ConstantRange::shl(const ConstantRange &Other) const {
1444  if (isEmptySet() || Other.isEmptySet())
1445  return getEmpty();
1446 
1447  APInt Min = getUnsignedMin();
1448  APInt Max = getUnsignedMax();
1449  if (const APInt *RHS = Other.getSingleElement()) {
1450  unsigned BW = getBitWidth();
1451  if (RHS->uge(BW))
1452  return getEmpty();
1453 
1454  unsigned EqualLeadingBits = (Min ^ Max).countLeadingZeros();
1455  if (RHS->ule(EqualLeadingBits))
1456  return getNonEmpty(Min << *RHS, (Max << *RHS) + 1);
1457 
1458  return getNonEmpty(APInt::getZero(BW),
1459  APInt::getBitsSetFrom(BW, RHS->getZExtValue()) + 1);
1460  }
1461 
1462  APInt OtherMax = Other.getUnsignedMax();
1463 
1464  // There's overflow!
1465  if (OtherMax.ugt(Max.countLeadingZeros()))
1466  return getFull();
1467 
1468  // FIXME: implement the other tricky cases
1469 
1470  Min <<= Other.getUnsignedMin();
1471  Max <<= OtherMax;
1472 
1473  return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1);
1474 }
1475 
1477 ConstantRange::lshr(const ConstantRange &Other) const {
1478  if (isEmptySet() || Other.isEmptySet())
1479  return getEmpty();
1480 
1481  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1482  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1483  return getNonEmpty(std::move(min), std::move(max));
1484 }
1485 
1487 ConstantRange::ashr(const ConstantRange &Other) const {
1488  if (isEmptySet() || Other.isEmptySet())
1489  return getEmpty();
1490 
1491  // May straddle zero, so handle both positive and negative cases.
1492  // 'PosMax' is the upper bound of the result of the ashr
1493  // operation, when Upper of the LHS of ashr is a non-negative.
1494  // number. Since ashr of a non-negative number will result in a
1495  // smaller number, the Upper value of LHS is shifted right with
1496  // the minimum value of 'Other' instead of the maximum value.
1497  APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1498 
1499  // 'PosMin' is the lower bound of the result of the ashr
1500  // operation, when Lower of the LHS is a non-negative number.
1501  // Since ashr of a non-negative number will result in a smaller
1502  // number, the Lower value of LHS is shifted right with the
1503  // maximum value of 'Other'.
1504  APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1505 
1506  // 'NegMax' is the upper bound of the result of the ashr
1507  // operation, when Upper of the LHS of ashr is a negative number.
1508  // Since 'ashr' of a negative number will result in a bigger
1509  // number, the Upper value of LHS is shifted right with the
1510  // maximum value of 'Other'.
1511  APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1512 
1513  // 'NegMin' is the lower bound of the result of the ashr
1514  // operation, when Lower of the LHS of ashr is a negative number.
1515  // Since 'ashr' of a negative number will result in a bigger
1516  // number, the Lower value of LHS is shifted right with the
1517  // minimum value of 'Other'.
1518  APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1519 
1520  APInt max, min;
1521  if (getSignedMin().isNonNegative()) {
1522  // Upper and Lower of LHS are non-negative.
1523  min = PosMin;
1524  max = PosMax;
1525  } else if (getSignedMax().isNegative()) {
1526  // Upper and Lower of LHS are negative.
1527  min = NegMin;
1528  max = NegMax;
1529  } else {
1530  // Upper is non-negative and Lower is negative.
1531  min = NegMin;
1532  max = PosMax;
1533  }
1534  return getNonEmpty(std::move(min), std::move(max));
1535 }
1536 
1538  if (isEmptySet() || Other.isEmptySet())
1539  return getEmpty();
1540 
1541  APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());
1542  APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;
1543  return getNonEmpty(std::move(NewL), std::move(NewU));
1544 }
1545 
1547  if (isEmptySet() || Other.isEmptySet())
1548  return getEmpty();
1549 
1550  APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());
1551  APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;
1552  return getNonEmpty(std::move(NewL), std::move(NewU));
1553 }
1554 
1556  if (isEmptySet() || Other.isEmptySet())
1557  return getEmpty();
1558 
1559  APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());
1560  APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;
1561  return getNonEmpty(std::move(NewL), std::move(NewU));
1562 }
1563 
1565  if (isEmptySet() || Other.isEmptySet())
1566  return getEmpty();
1567 
1568  APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
1569  APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
1570  return getNonEmpty(std::move(NewL), std::move(NewU));
1571 }
1572 
1574  if (isEmptySet() || Other.isEmptySet())
1575  return getEmpty();
1576 
1577  APInt NewL = getUnsignedMin().umul_sat(Other.getUnsignedMin());
1578  APInt NewU = getUnsignedMax().umul_sat(Other.getUnsignedMax()) + 1;
1579  return getNonEmpty(std::move(NewL), std::move(NewU));
1580 }
1581 
1583  if (isEmptySet() || Other.isEmptySet())
1584  return getEmpty();
1585 
1586  // Because we could be dealing with negative numbers here, the lower bound is
1587  // the smallest of the cartesian product of the lower and upper ranges;
1588  // for example:
1589  // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1590  // Similarly for the upper bound, swapping min for max.
1591 
1592  APInt Min = getSignedMin();
1593  APInt Max = getSignedMax();
1594  APInt OtherMin = Other.getSignedMin();
1595  APInt OtherMax = Other.getSignedMax();
1596 
1597  auto L = {Min.smul_sat(OtherMin), Min.smul_sat(OtherMax),
1598  Max.smul_sat(OtherMin), Max.smul_sat(OtherMax)};
1599  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1600  return getNonEmpty(std::min(L, Compare), std::max(L, Compare) + 1);
1601 }
1602 
1604  if (isEmptySet() || Other.isEmptySet())
1605  return getEmpty();
1606 
1607  APInt NewL = getUnsignedMin().ushl_sat(Other.getUnsignedMin());
1608  APInt NewU = getUnsignedMax().ushl_sat(Other.getUnsignedMax()) + 1;
1609  return getNonEmpty(std::move(NewL), std::move(NewU));
1610 }
1611 
1613  if (isEmptySet() || Other.isEmptySet())
1614  return getEmpty();
1615 
1616  APInt Min = getSignedMin(), Max = getSignedMax();
1617  APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax();
1618  APInt NewL = Min.sshl_sat(Min.isNonNegative() ? ShAmtMin : ShAmtMax);
1619  APInt NewU = Max.sshl_sat(Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;
1620  return getNonEmpty(std::move(NewL), std::move(NewU));
1621 }
1622 
1624  if (isFullSet())
1625  return getEmpty();
1626  if (isEmptySet())
1627  return getFull();
1628  return ConstantRange(Upper, Lower);
1629 }
1630 
1631 ConstantRange ConstantRange::abs(bool IntMinIsPoison) const {
1632  if (isEmptySet())
1633  return getEmpty();
1634 
1635  if (isSignWrappedSet()) {
1636  APInt Lo;
1637  // Check whether the range crosses zero.
1638  if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1639  Lo = APInt::getZero(getBitWidth());
1640  else
1641  Lo = APIntOps::umin(Lower, -Upper + 1);
1642 
1643  // If SignedMin is not poison, then it is included in the result range.
1644  if (IntMinIsPoison)
1646  else
1648  }
1649 
1651 
1652  // Skip SignedMin if it is poison.
1653  if (IntMinIsPoison && SMin.isMinSignedValue()) {
1654  // The range may become empty if it *only* contains SignedMin.
1655  if (SMax.isMinSignedValue())
1656  return getEmpty();
1657  ++SMin;
1658  }
1659 
1660  // All non-negative.
1661  if (SMin.isNonNegative())
1662  return *this;
1663 
1664  // All negative.
1665  if (SMax.isNegative())
1666  return ConstantRange(-SMax, -SMin + 1);
1667 
1668  // Range crosses zero.
1670  APIntOps::umax(-SMin, SMax) + 1);
1671 }
1672 
1674  const ConstantRange &Other) const {
1675  if (isEmptySet() || Other.isEmptySet())
1677 
1678  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1679  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1680 
1681  // a u+ b overflows high iff a u> ~b.
1682  if (Min.ugt(~OtherMin))
1684  if (Max.ugt(~OtherMax))
1687 }
1688 
1690  const ConstantRange &Other) const {
1691  if (isEmptySet() || Other.isEmptySet())
1693 
1694  APInt Min = getSignedMin(), Max = getSignedMax();
1695  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1696 
1699 
1700  // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1701  // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1702  if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1703  Min.sgt(SignedMax - OtherMin))
1705  if (Max.isNegative() && OtherMax.isNegative() &&
1706  Max.slt(SignedMin - OtherMax))
1708 
1709  if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1710  Max.sgt(SignedMax - OtherMax))
1712  if (Min.isNegative() && OtherMin.isNegative() &&
1713  Min.slt(SignedMin - OtherMin))
1715 
1717 }
1718 
1720  const ConstantRange &Other) const {
1721  if (isEmptySet() || Other.isEmptySet())
1723 
1724  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1725  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1726 
1727  // a u- b overflows low iff a u< b.
1728  if (Max.ult(OtherMin))
1730  if (Min.ult(OtherMax))
1733 }
1734 
1736  const ConstantRange &Other) const {
1737  if (isEmptySet() || Other.isEmptySet())
1739 
1740  APInt Min = getSignedMin(), Max = getSignedMax();
1741  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1742 
1745 
1746  // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
1747  // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
1748  if (Min.isNonNegative() && OtherMax.isNegative() &&
1749  Min.sgt(SignedMax + OtherMax))
1751  if (Max.isNegative() && OtherMin.isNonNegative() &&
1752  Max.slt(SignedMin + OtherMin))
1754 
1755  if (Max.isNonNegative() && OtherMin.isNegative() &&
1756  Max.sgt(SignedMax + OtherMin))
1758  if (Min.isNegative() && OtherMax.isNonNegative() &&
1759  Min.slt(SignedMin + OtherMax))
1761 
1763 }
1764 
1766  const ConstantRange &Other) const {
1767  if (isEmptySet() || Other.isEmptySet())
1769 
1770  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1771  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1772  bool Overflow;
1773 
1774  (void) Min.umul_ov(OtherMin, Overflow);
1775  if (Overflow)
1777 
1778  (void) Max.umul_ov(OtherMax, Overflow);
1779  if (Overflow)
1781 
1783 }
1784 
1786  if (isFullSet())
1787  OS << "full-set";
1788  else if (isEmptySet())
1789  OS << "empty-set";
1790  else
1791  OS << "[" << Lower << "," << Upper << ")";
1792 }
1793 
1794 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1796  print(dbgs());
1797 }
1798 #endif
1799 
1801  const unsigned NumRanges = Ranges.getNumOperands() / 2;
1802  assert(NumRanges >= 1 && "Must have at least one range!");
1803  assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1804 
1805  auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1806  auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1807 
1808  ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1809 
1810  for (unsigned i = 1; i < NumRanges; ++i) {
1811  auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1812  auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1813 
1814  // Note: unionWith will potentially create a range that contains values not
1815  // contained in any of the original N ranges.
1816  CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1817  }
1818 
1819  return CR;
1820 }
llvm::ConstantRange::isFullSet
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
Definition: ConstantRange.cpp:366
i
i
Definition: README.txt:29
llvm::APInt::isStrictlyPositive
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
Definition: APInt.h:339
llvm::ConstantRange::signExtend
ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
Definition: ConstantRange.cpp:788
llvm::ConstantRange::binaryOr
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...
Definition: ConstantRange.cpp:1412
llvm::APInt::setAllBits
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1289
Signed
@ Signed
Definition: NVPTXISelLowering.cpp:4715
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::ConstantRange::OverflowResult::AlwaysOverflowsLow
@ AlwaysOverflowsLow
Always overflows in the direction of signed/unsigned min value.
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::ConstantRange::ushl_sat
ConstantRange ushl_sat(const ConstantRange &Other) const
Perform an unsigned saturating left shift of this constant range by a value in Other.
Definition: ConstantRange.cpp:1603
llvm::HexPrintStyle::Upper
@ Upper
llvm::ConstantRange::binaryAnd
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...
Definition: ConstantRange.cpp:1400
Metadata.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::ConstantRange::sdiv
ConstantRange sdiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed division of a value in th...
Definition: ConstantRange.cpp:1235
llvm::ConstantRange::sub
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
Definition: ConstantRange.cpp:1036
llvm::ConstantRange::dump
void dump() const
Allow printing from a debugger easily.
Definition: ConstantRange.cpp:1795
llvm::KnownBits::getMinValue
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
Definition: KnownBits.h:120
llvm::ConstantRange::umul_sat
ConstantRange umul_sat(const ConstantRange &Other) const
Perform an unsigned saturating multiplication of two constant ranges.
Definition: ConstantRange.cpp:1573
llvm::APInt::ule
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1120
llvm::ConstantRange::udiv
ConstantRange udiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned division of a value in...
Definition: ConstantRange.cpp:1215
llvm::KnownBits::Zero
APInt Zero
Definition: KnownBits.h:24
llvm::ConstantRange::ssub_sat
ConstantRange ssub_sat(const ConstantRange &Other) const
Perform a signed saturating subtraction of two constant ranges.
Definition: ConstantRange.cpp:1564
High
uint64_t High
Definition: NVVMIntrRange.cpp:61
llvm::CmpInst::getFlippedSignednessPredicate
Predicate getFlippedSignednessPredicate()
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->Failed assert.
Definition: InstrTypes.h:991
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:266
llvm::KnownBits::isUnknown
bool isUnknown() const
Returns true if we don't know any bits.
Definition: KnownBits.h:63
llvm::APInt::getMinValue
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:196
llvm::ConstantRange::OverflowResult::AlwaysOverflowsHigh
@ AlwaysOverflowsHigh
Always overflows in the direction of signed/unsigned max value.
ErrorHandling.h
llvm::APInt::getMaxValue
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
llvm::ConstantRange::isUpperSignWrapped
bool isUpperSignWrapped() const
Return true if the (exclusive) upper bound wraps around the signed domain.
Definition: ConstantRange.cpp:386
llvm::ConstantRange::isAllNonNegative
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
Definition: ConstantRange.cpp:420
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:834
llvm::APInt::isOne
bool isOne() const
Determine if this is a value of 1.
Definition: APInt.h:371
llvm::ConstantRange::getEquivalentICmp
bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
Definition: ConstantRange.cpp:234
llvm::ConstantRange::exactIntersectWith
Optional< ConstantRange > exactIntersectWith(const ConstantRange &CR) const
Intersect the two ranges and return the result if it can be represented exactly, otherwise return Non...
Definition: ConstantRange.cpp:703
APInt.h
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:747
llvm::APInt::getSignedMaxValue
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1431
llvm::ConstantRange::isSignWrappedSet
bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
Definition: ConstantRange.cpp:382
llvm::ConstantRange::uadd_sat
ConstantRange uadd_sat(const ConstantRange &Other) const
Perform an unsigned saturating addition of two constant ranges.
Definition: ConstantRange.cpp:1537
llvm::APInt::ugt
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1152
llvm::ConstantRange::multiply
ConstantRange multiply(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a multiplication of a value in thi...
Definition: ConstantRange.cpp:1086
llvm::Optional< unsigned >
llvm::ConstantRange::shl
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...
Definition: ConstantRange.cpp:1443
Operator.h
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:750
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::ConstantRange::sshl_sat
ConstantRange sshl_sat(const ConstantRange &Other) const
Perform a signed saturating left shift of this constant range by a value in Other.
Definition: ConstantRange.cpp:1612
llvm::APInt::lshr
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:832
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::getConstantRangeFromMetadata
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Definition: ConstantRange.cpp:1800
llvm::RecurKind::SMin
@ SMin
Signed integer min implemented in terms of select(cmp()).
llvm::APIntOps::GetMostSignificantDifferentBit
Optional< unsigned > GetMostSignificantDifferentBit(const APInt &A, const APInt &B)
Compare two values, and if they are different, return the position of the most significant bit that i...
Definition: APInt.cpp:2964
llvm::APInt::Rounding::UP
@ UP
llvm::ConstantRange::unsignedAddMayOverflow
OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const
Return whether unsigned add of the two ranges always/never overflows.
Definition: ConstantRange.cpp:1673
llvm::APInt::isMinValue
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:402
llvm::APInt::getZero
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:177
llvm::ConstantRange::makeAllowedICmpRegion
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...
Definition: ConstantRange.cpp:96
llvm::ConstantRange::isIntrinsicSupported
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
Definition: ConstantRange.cpp:940
llvm::APIntOps::umin
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2157
llvm::ConstantRange::OverflowResult
OverflowResult
Represents whether an operation on the given constant range is known to always or never overflow.
Definition: ConstantRange.h:530
getPreferredRange
static ConstantRange getPreferredRange(const ConstantRange &CR1, const ConstantRange &CR2, ConstantRange::PreferredRangeType Type)
Definition: ConstantRange.cpp:503
KnownBits.h
llvm::ConstantRange::binaryOp
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...
Definition: ConstantRange.cpp:878
llvm::ConstantRange::signedSubMayOverflow
OverflowResult signedSubMayOverflow(const ConstantRange &Other) const
Return whether signed sub of the two ranges always/never overflows.
Definition: ConstantRange.cpp:1735
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ConstantRange::Signed
@ Signed
Definition: ConstantRange.h:319
Instruction.h
llvm::APInt::umul_ov
APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1969
llvm::APInt::uge
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1191
llvm::KnownBits::isNonNegative
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
llvm::APInt::isNonNegative
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:317
llvm::APInt::isNegative
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:312
llvm::ConstantRange::binaryXor
ConstantRange binaryXor(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-xor of a value in this ra...
Definition: ConstantRange.cpp:1425
Constants.h
llvm::APInt::isZero
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:359
llvm::ConstantRange::isWrappedSet
bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
Definition: ConstantRange.cpp:374
llvm::ConstantRange::areInsensitiveToSignednessOfICmpPredicate
static bool areInsensitiveToSignednessOfICmpPredicate(const ConstantRange &CR1, const ConstantRange &CR2)
Return true iff CR1 ult CR2 is equivalent to CR1 slt CR2.
Definition: ConstantRange.cpp:168
llvm::ConstantRange::getUnsignedMin
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:431
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::APInt::usub_sat
APInt usub_sat(const APInt &RHS) const
Definition: APInt.cpp:2038
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:746
InstrTypes.h
llvm::ConstantRange::PreferredRangeType
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
Definition: ConstantRange.h:319
llvm::KnownBits::One
APInt One
Definition: KnownBits.h:25
llvm::ConstantRange::isSingleElement
bool isSingleElement() const
Return true if this set contains exactly one member.
Definition: ConstantRange.h:261
llvm::ConstantRange::abs
ConstantRange abs(bool IntMinIsPoison=false) const
Calculate absolute value range.
Definition: ConstantRange.cpp:1631
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
llvm::KnownBits::hasConflict
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:47
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::ConstantRange::makeGuaranteedNoWrapRegion
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
Definition: ConstantRange.cpp:288
llvm::ConstantRange::srem
ConstantRange srem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed remainder operation of a ...
Definition: ConstantRange.cpp:1345
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:807
llvm::ConstantRange::getUnsignedMax
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:425
llvm::APInt::isAllOnes
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:347
llvm::ConstantRange::exactUnionWith
Optional< ConstantRange > exactUnionWith(const ConstantRange &CR) const
Union the two ranges and return the result if it can be represented exactly, otherwise return None.
Definition: ConstantRange.cpp:712
llvm::ConstantRange::lshr
ConstantRange lshr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a logical right shift of a value i...
Definition: ConstantRange.cpp:1477
llvm::ConstantRange::isUpperWrapped
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
Definition: ConstantRange.cpp:378
llvm::ConstantRange::unionWith
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
Definition: ConstantRange.cpp:629
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::APInt::getHighBitsSet
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:279
llvm::ThreadPriority::Low
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
llvm::APInt::smul_sat
APInt smul_sat(const APInt &RHS) const
Definition: APInt.cpp:2047
llvm::ConstantRange::Unsigned
@ Unsigned
Definition: ConstantRange.h:319
llvm::KnownBits::isNegative
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:96
llvm::ConstantRange::add
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
Definition: ConstantRange.cpp:989
llvm::ConstantRange::isSizeLargerThan
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
Definition: ConstantRange.cpp:401
llvm::ConstantRange::smul_fast
ConstantRange smul_fast(const ConstantRange &Other) const
Return range of possible values for a signed multiplication of this and Other.
Definition: ConstantRange.cpp:1139
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::RecurKind::UMin
@ UMin
Unisgned integer min implemented in terms of select(cmp()).
llvm::ConstantRange::intrinsic
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
Definition: ConstantRange.cpp:957
llvm::APInt::ashr
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:808
llvm::ConstantRange::overflowingBinaryOp
ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind) const
Return a new range representing the possible values resulting from an application of the specified ov...
Definition: ConstantRange.cpp:923
llvm::APInt::getOneBitSet
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:222
llvm::ConstantRange::castOp
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...
Definition: ConstantRange.cpp:720
llvm::ConstantRange::isAllNegative
bool isAllNegative() const
Return true if all values in this range are negative.
Definition: ConstantRange.cpp:410
llvm::ConstantRange::zeroExtend
ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
Definition: ConstantRange.cpp:771
llvm::APInt::slt
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1100
llvm::ConstantRange::inverse
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
Definition: ConstantRange.cpp:1623
llvm::ConstantRange::getBitWidth
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
Definition: ConstantRange.h:204
llvm::APInt::sdiv
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition: APInt.cpp:1642
uint64_t
llvm::ConstantRange::getSignedMin
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:443
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::APInt::clearLowBits
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
Definition: APInt.h:1387
llvm::ConstantRange::zextOrTrunc
ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
Definition: ConstantRange.cpp:860
llvm::KnownBits::getMaxValue
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
Definition: KnownBits.h:136
llvm::ConstantRange::getEquivalentPredWithFlippedSignedness
static CmpInst::Predicate getEquivalentPredWithFlippedSignedness(CmpInst::Predicate Pred, const ConstantRange &CR1, const ConstantRange &CR2)
If the comparison between constant ranges this and Other is insensitive to the signedness of the comp...
Definition: ConstantRange.cpp:186
llvm::ConstantRange::smul_sat
ConstantRange smul_sat(const ConstantRange &Other) const
Perform a signed saturating multiplication of two constant ranges.
Definition: ConstantRange.cpp:1582
llvm::APInt::getBoolValue
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:452
llvm::ConstantRange::addWithNoWrap
ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from an addition with wrap type NoWrapK...
Definition: ConstantRange.cpp:1008
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1861
llvm::ConstantRange::truncate
ConstantRange truncate(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
Definition: ConstantRange.cpp:806
llvm::ConstantRange::sadd_sat
ConstantRange sadd_sat(const ConstantRange &Other) const
Perform a signed saturating addition of two constant ranges.
Definition: ConstantRange.cpp:1546
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:744
llvm::Instruction::isBinaryOp
bool isBinaryOp() const
Definition: Instruction.h:174
llvm::ConstantRange::unsignedMulMayOverflow
OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const
Return whether unsigned mul of the two ranges always/never overflows.
Definition: ConstantRange.cpp:1765
llvm::ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate
static bool areInsensitiveToSignednessOfInvertedICmpPredicate(const ConstantRange &CR1, const ConstantRange &CR2)
Return true iff CR1 ult CR2 is equivalent to CR1 sge CR2.
Definition: ConstantRange.cpp:177
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
llvm::ConstantRange::smax
ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
Definition: ConstantRange.cpp:1159
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::ConstantRange::getSingleElement
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
Definition: ConstantRange.h:246
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:749
llvm::CmpInst::isIntPredicate
bool isIntPredicate() const
Definition: InstrTypes.h:828
Compare
QP Compare Ordered outs ins xscmpudp No builtin are required Or llvm fcmp order unorder compare DP QP Compare builtin are required DP Compare
Definition: README_P9.txt:309
llvm::APIntOps::smin
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2147
llvm::RecurKind::UMax
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::APInt::sshl_sat
APInt sshl_sat(const APInt &RHS) const
Definition: APInt.cpp:2069
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
uint32_t
makeExactMulNSWRegion
static ConstantRange makeExactMulNSWRegion(const APInt &V)
Exact mul nsw region for single element RHS.
Definition: ConstantRange.cpp:260
Compiler.h
llvm::ConstantRange::umax
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
Definition: ConstantRange.cpp:1173
llvm::APInt::ushl_sat
APInt ushl_sat(const APInt &RHS) const
Definition: APInt.cpp:2079
ConstantRange.h
llvm::APIntOps::RoundingSDiv
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:2743
llvm::ConstantRange::ConstantRange
ConstantRange(uint32_t BitWidth, bool isFullSet)
Initialize a full or empty set for the specified bit width.
Definition: ConstantRange.cpp:43
llvm::OverflowingBinaryOperator
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition: Operator.h:72
llvm::APInt::umul_sat
APInt umul_sat(const APInt &RHS) const
Definition: APInt.cpp:2060
llvm::APInt::ult
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1081
llvm::APInt::udiv
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1571
llvm::APInt::clearBit
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1377
llvm::APInt::zext
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:973
llvm::APInt::Rounding::DOWN
@ DOWN
llvm::ConstantRange::isSizeStrictlySmallerThan
bool isSizeStrictlySmallerThan(const ConstantRange &CR) const
Compare set size of this range with the range CR.
Definition: ConstantRange.cpp:391
llvm::CmpInst::isRelational
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
Definition: InstrTypes.h:944
llvm::APInt::ssub_sat
APInt ssub_sat(const APInt &RHS) const
Definition: APInt.cpp:2028
llvm::ConstantRange::difference
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
Definition: ConstantRange.cpp:499
llvm::APIntOps::umax
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2162
llvm::ConstantRange::getSignedMax
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:437
llvm::ConstantRange::getLower
const APInt & getLower() const
Return the lower value for this range.
Definition: ConstantRange.h:198
llvm::APInt::uadd_sat
APInt uadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2019
std
Definition: BitVector.h:851
llvm::APInt::trunc
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:898
llvm::KnownBits
Definition: KnownBits.h:23
llvm::APInt::isMinSignedValue
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:408
llvm::APInt::clearSignBit
void clearSignBit()
Set the sign bit to 0.
Definition: APInt.h:1394
llvm::ConstantRange::smin
ConstantRange smin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed minimum of a value in thi...
Definition: ConstantRange.cpp:1187
llvm::ConstantRange::getMinSignedBits
unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
Definition: ConstantRange.cpp:483
llvm::ConstantRange::subWithNoWrap
ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from an subtraction with wrap type NoWr...
Definition: ConstantRange.cpp:1055
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::APInt::smul_ov
APInt smul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1958
llvm::ConstantRange::getActiveBits
unsigned getActiveBits() const
Compute the maximal number of active bits needed to represent every value in this range.
Definition: ConstantRange.cpp:476
llvm::ConstantRange::contains
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
Definition: ConstantRange.cpp:449
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:748
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::countLeadingZeros
unsigned countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the most significant bit to the least stopping at the first 1.
Definition: MathExtras.h:220
llvm::ConstantRange::getSingleMissingElement
const APInt * getSingleMissingElement() const
If this set contains all but a single element, return it, otherwise return null.
Definition: ConstantRange.h:254
llvm::APInt::getSignedMinValue
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
llvm::ConstantRange
This class represents a range of values.
Definition: ConstantRange.h:47
llvm::APInt::sext
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:946
llvm::ConstantRange::urem
ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
Definition: ConstantRange.cpp:1323
llvm::ConstantRange::getNonEmpty
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
Definition: ConstantRange.h:84
llvm::ConstantRange::toKnownBits
KnownBits toKnownBits() const
Return known bits for values in this range.
Definition: ConstantRange.cpp:78
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:793
llvm::ConstantRange::binaryNot
ConstantRange binaryNot() const
Return a new range representing the possible values resulting from a binary-xor of a value in this ra...
Definition: ConstantRange.cpp:1396
llvm::HexagonMCInstrInfo::getMaxValue
int getMaxValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the maximum value of an extendable operand.
Definition: HexagonMCInstrInfo.cpp:353
llvm::ConstantRange::ashr
ConstantRange ashr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a arithmetic right shift of a valu...
Definition: ConstantRange.cpp:1487
llvm::ConstantRange::intersectWith
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
Definition: ConstantRange.cpp:523
llvm::APInt::isMaxValue
bool isMaxValue() const
Determine if this is the largest unsigned value.
Definition: APInt.h:384
llvm::ConstantRange::fromKnownBits
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
Definition: ConstantRange.cpp:58
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:743
llvm::ConstantRange::signedAddMayOverflow
OverflowResult signedAddMayOverflow(const ConstantRange &Other) const
Return whether signed add of the two ranges always/never overflows.
Definition: ConstantRange.cpp:1689
llvm::APInt::countTrailingOnes
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1579
llvm::APInt::getActiveBits
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1455
llvm::ConstantRange::print
void print(raw_ostream &OS) const
Print out the bounds to a stream.
Definition: ConstantRange.cpp:1785
llvm::KnownBits::makeConstant
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
Definition: KnownBits.h:310
llvm::ConstantRange::icmp
bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other? NOTE: false does not mean that inverse pr...
Definition: ConstantRange.cpp:241
llvm::ConstantRange::usub_sat
ConstantRange usub_sat(const ConstantRange &Other) const
Perform an unsigned saturating subtraction of two constant ranges.
Definition: ConstantRange.cpp:1555
makeExactMulNUWRegion
static ConstantRange makeExactMulNUWRegion(const APInt &V)
Exact mul nuw region for single element RHS.
Definition: ConstantRange.cpp:247
llvm::ConstantRange::OverflowResult::NeverOverflows
@ NeverOverflows
Never overflows.
llvm::ConstantRange::makeExactICmpRegion
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...
Definition: ConstantRange.cpp:156
llvm::HexagonMCInstrInfo::getMinValue
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
Definition: HexagonMCInstrInfo.cpp:364
llvm::ConstantRange::unsignedSubMayOverflow
OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const
Return whether unsigned sub of the two ranges always/never overflows.
Definition: ConstantRange.cpp:1719
llvm::APInt::sgt
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1171
llvm::APInt::sadd_sat
APInt sadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2009
llvm::APIntOps::RoundingUDiv
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:2725
llvm::APInt::getLowBitsSet
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:289
llvm::ConstantRange::subtract
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
Definition: ConstantRange.cpp:491
llvm::ConstantRange::makeSatisfyingICmpRegion
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...
Definition: ConstantRange.cpp:146
llvm::KnownBits::getBitWidth
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:40
llvm::APInt::getBitsSetFrom
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:269
llvm::ConstantRange::isEmptySet
bool isEmptySet() const
Return true if this set contains no members.
Definition: ConstantRange.cpp:370
llvm::ConstantRange::sextOrTrunc
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
Definition: ConstantRange.cpp:869
raw_ostream.h
llvm::abs
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1297
llvm::ConstantRange::getUpper
const APInt & getUpper() const
Return the upper value for this range.
Definition: ConstantRange.h:201
llvm::RecurKind::SMax
@ SMax
Signed integer max implemented in terms of select(cmp()).
isNonNegative
static bool isNonNegative(Value *V, LazyValueInfo *LVI, Instruction *CxtI)
Definition: CorrelatedValuePropagation.cpp:695
Debug.h
llvm::APIntOps::smax
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2152
llvm::ConstantRange::umin
ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
Definition: ConstantRange.cpp:1201
llvm::ConstantRange::OverflowResult::MayOverflow
@ MayOverflow
May or may not overflow.
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1251
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:39
llvm::ConstantRange::makeExactNoWrapRegion
static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
Definition: ConstantRange.cpp:358