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