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