LLVM  10.0.0svn
ConstantRange.cpp
Go to the documentation of this file.
1 //===- ConstantRange.cpp - ConstantRange implementation -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Represent a range of possible values that may occur when the program is run
10 // for an integral value. This keeps track of a lower and upper bound for the
11 // constant, which MAY wrap around the end of the numeric range. To do this, it
12 // keeps track of a [lower, upper) bound, which specifies an interval just like
13 // STL iterators. When used with boolean values, the following are important
14 // ranges (other integral ranges use min/max values for special range values):
15 //
16 // [F, F) = {} = Empty set
17 // [T, F) = {T}
18 // [F, T) = {F}
19 // [T, T) = {F, T} = Full set
20 //
21 //===----------------------------------------------------------------------===//
22 
23 #include "llvm/ADT/APInt.h"
24 #include "llvm/Config/llvm-config.h"
25 #include "llvm/IR/ConstantRange.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Metadata.h"
30 #include "llvm/IR/Operator.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/KnownBits.h"
36 #include <algorithm>
37 #include <cassert>
38 #include <cstdint>
39 
40 using namespace llvm;
41 
43  : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
44  Upper(Lower) {}
45 
47  : Lower(std::move(V)), Upper(Lower + 1) {}
48 
50  : Lower(std::move(L)), Upper(std::move(U)) {
51  assert(Lower.getBitWidth() == Upper.getBitWidth() &&
52  "ConstantRange with unequal bit widths");
53  assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
54  "Lower == Upper, but they aren't min or max value!");
55 }
56 
58  bool IsSigned) {
59  assert(!Known.hasConflict() && "Expected valid KnownBits");
60 
61  if (Known.isUnknown())
62  return getFull(Known.getBitWidth());
63 
64  // For unsigned ranges, or signed ranges with known sign bit, create a simple
65  // range between the smallest and largest possible value.
66  if (!IsSigned || Known.isNegative() || Known.isNonNegative())
67  return ConstantRange(Known.One, ~Known.Zero + 1);
68 
69  // If we don't know the sign bit, pick the lower bound as a negative number
70  // and the upper bound as a non-negative one.
71  APInt Lower = Known.One, Upper = ~Known.Zero;
72  Lower.setSignBit();
73  Upper.clearSignBit();
74  return ConstantRange(Lower, Upper + 1);
75 }
76 
78  const ConstantRange &CR) {
79  if (CR.isEmptySet())
80  return CR;
81 
82  uint32_t W = CR.getBitWidth();
83  switch (Pred) {
84  default:
85  llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
86  case CmpInst::ICMP_EQ:
87  return CR;
88  case CmpInst::ICMP_NE:
89  if (CR.isSingleElement())
90  return ConstantRange(CR.getUpper(), CR.getLower());
91  return getFull(W);
92  case CmpInst::ICMP_ULT: {
93  APInt UMax(CR.getUnsignedMax());
94  if (UMax.isMinValue())
95  return getEmpty(W);
96  return ConstantRange(APInt::getMinValue(W), std::move(UMax));
97  }
98  case CmpInst::ICMP_SLT: {
99  APInt SMax(CR.getSignedMax());
100  if (SMax.isMinSignedValue())
101  return getEmpty(W);
102  return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
103  }
104  case CmpInst::ICMP_ULE:
105  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();
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();
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  // Note: floating point operations applied to abstract ranges are just
806  // ideal integer operations with a lossy representation
807  case Instruction::FAdd:
808  return add(Other);
809  case Instruction::FSub:
810  return sub(Other);
811  case Instruction::FMul:
812  return multiply(Other);
813  default:
814  // Conservatively return getFull set.
815  return getFull();
816  }
817 }
818 
821  if (isEmptySet() || Other.isEmptySet())
822  return getEmpty();
823  if (isFullSet() || Other.isFullSet())
824  return getFull();
825 
826  APInt NewLower = getLower() + Other.getLower();
827  APInt NewUpper = getUpper() + Other.getUpper() - 1;
828  if (NewLower == NewUpper)
829  return getFull();
830 
831  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
832  if (X.isSizeStrictlySmallerThan(*this) ||
833  X.isSizeStrictlySmallerThan(Other))
834  // We've wrapped, therefore, full set.
835  return getFull();
836  return X;
837 }
838 
840  unsigned NoWrapKind,
841  PreferredRangeType RangeType) const {
842  // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
843  // (X is from this, and Y is from Other)
844  if (isEmptySet() || Other.isEmptySet())
845  return getEmpty();
846  if (isFullSet() && Other.isFullSet())
847  return getFull();
848 
849  using OBO = OverflowingBinaryOperator;
850  ConstantRange Result = add(Other);
851 
852  auto addWithNoUnsignedWrap = [this](const ConstantRange &Other) {
853  APInt LMin = getUnsignedMin(), LMax = getUnsignedMax();
854  APInt RMin = Other.getUnsignedMin(), RMax = Other.getUnsignedMax();
855  bool Overflow;
856  APInt NewMin = LMin.uadd_ov(RMin, Overflow);
857  if (Overflow)
858  return getEmpty();
859  APInt NewMax = LMax.uadd_sat(RMax);
860  return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1);
861  };
862 
863  auto addWithNoSignedWrap = [this](const ConstantRange &Other) {
864  APInt LMin = getSignedMin(), LMax = getSignedMax();
865  APInt RMin = Other.getSignedMin(), RMax = Other.getSignedMax();
866  if (LMin.isNonNegative()) {
867  bool Overflow;
868  APInt Temp = LMin.sadd_ov(RMin, Overflow);
869  if (Overflow)
870  return getEmpty();
871  }
872  if (LMax.isNegative()) {
873  bool Overflow;
874  APInt Temp = LMax.sadd_ov(RMax, Overflow);
875  if (Overflow)
876  return getEmpty();
877  }
878  APInt NewMin = LMin.sadd_sat(RMin);
879  APInt NewMax = LMax.sadd_sat(RMax);
880  return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1);
881  };
882 
883  if (NoWrapKind & OBO::NoSignedWrap)
884  Result = Result.intersectWith(addWithNoSignedWrap(Other), RangeType);
885  if (NoWrapKind & OBO::NoUnsignedWrap)
886  Result = Result.intersectWith(addWithNoUnsignedWrap(Other), RangeType);
887  return Result;
888 }
889 
892  if (isEmptySet() || Other.isEmptySet())
893  return getEmpty();
894  if (isFullSet() || Other.isFullSet())
895  return getFull();
896 
897  APInt NewLower = getLower() - Other.getUpper() + 1;
898  APInt NewUpper = getUpper() - Other.getLower();
899  if (NewLower == NewUpper)
900  return getFull();
901 
902  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
903  if (X.isSizeStrictlySmallerThan(*this) ||
904  X.isSizeStrictlySmallerThan(Other))
905  // We've wrapped, therefore, full set.
906  return getFull();
907  return X;
908 }
909 
912  // TODO: If either operand is a single element and the multiply is known to
913  // be non-wrapping, round the result min and max value to the appropriate
914  // multiple of that element. If wrapping is possible, at least adjust the
915  // range according to the greatest power-of-two factor of the single element.
916 
917  if (isEmptySet() || Other.isEmptySet())
918  return getEmpty();
919 
920  // Multiplication is signedness-independent. However different ranges can be
921  // obtained depending on how the input ranges are treated. These different
922  // ranges are all conservatively correct, but one might be better than the
923  // other. We calculate two ranges; one treating the inputs as unsigned
924  // and the other signed, then return the smallest of these ranges.
925 
926  // Unsigned range first.
927  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
928  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
929  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
930  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
931 
932  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
933  this_max * Other_max + 1);
934  ConstantRange UR = Result_zext.truncate(getBitWidth());
935 
936  // If the unsigned range doesn't wrap, and isn't negative then it's a range
937  // from one positive number to another which is as good as we can generate.
938  // In this case, skip the extra work of generating signed ranges which aren't
939  // going to be better than this range.
940  if (!UR.isUpperWrapped() &&
941  (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
942  return UR;
943 
944  // Now the signed range. Because we could be dealing with negative numbers
945  // here, the lower bound is the smallest of the cartesian product of the
946  // lower and upper ranges; for example:
947  // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
948  // Similarly for the upper bound, swapping min for max.
949 
950  this_min = getSignedMin().sext(getBitWidth() * 2);
951  this_max = getSignedMax().sext(getBitWidth() * 2);
952  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
953  Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
954 
955  auto L = {this_min * Other_min, this_min * Other_max,
956  this_max * Other_min, this_max * Other_max};
957  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
958  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
959  ConstantRange SR = Result_sext.truncate(getBitWidth());
960 
961  return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
962 }
963 
966  // X smax Y is: range(smax(X_smin, Y_smin),
967  // smax(X_smax, Y_smax))
968  if (isEmptySet() || Other.isEmptySet())
969  return getEmpty();
970  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
971  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
972  return getNonEmpty(std::move(NewL), std::move(NewU));
973 }
974 
977  // X umax Y is: range(umax(X_umin, Y_umin),
978  // umax(X_umax, Y_umax))
979  if (isEmptySet() || Other.isEmptySet())
980  return getEmpty();
982  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
983  return getNonEmpty(std::move(NewL), std::move(NewU));
984 }
985 
988  // X smin Y is: range(smin(X_smin, Y_smin),
989  // smin(X_smax, Y_smax))
990  if (isEmptySet() || Other.isEmptySet())
991  return getEmpty();
992  APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
993  APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
994  return getNonEmpty(std::move(NewL), std::move(NewU));
995 }
996 
999  // X umin Y is: range(umin(X_umin, Y_umin),
1000  // umin(X_umax, Y_umax))
1001  if (isEmptySet() || Other.isEmptySet())
1002  return getEmpty();
1004  APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1005  return getNonEmpty(std::move(NewL), std::move(NewU));
1006 }
1007 
1010  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
1011  return getEmpty();
1012 
1014 
1015  APInt RHS_umin = RHS.getUnsignedMin();
1016  if (RHS_umin.isNullValue()) {
1017  // We want the lowest value in RHS excluding zero. Usually that would be 1
1018  // except for a range in the form of [X, 1) in which case it would be X.
1019  if (RHS.getUpper() == 1)
1020  RHS_umin = RHS.getLower();
1021  else
1022  RHS_umin = 1;
1023  }
1024 
1025  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
1026  return getNonEmpty(std::move(Lower), std::move(Upper));
1027 }
1028 
1030  // We split up the LHS and RHS into positive and negative components
1031  // and then also compute the positive and negative components of the result
1032  // separately by combining division results with the appropriate signs.
1035  ConstantRange PosFilter(APInt(getBitWidth(), 1), SignedMin);
1036  ConstantRange NegFilter(SignedMin, Zero);
1037  ConstantRange PosL = intersectWith(PosFilter);
1038  ConstantRange NegL = intersectWith(NegFilter);
1039  ConstantRange PosR = RHS.intersectWith(PosFilter);
1040  ConstantRange NegR = RHS.intersectWith(NegFilter);
1041 
1042  ConstantRange PosRes = getEmpty();
1043  if (!PosL.isEmptySet() && !PosR.isEmptySet())
1044  // pos / pos = pos.
1045  PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),
1046  (PosL.Upper - 1).sdiv(PosR.Lower) + 1);
1047 
1048  if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1049  // neg / neg = pos.
1050  //
1051  // We need to deal with one tricky case here: SignedMin / -1 is UB on the
1052  // IR level, so we'll want to exclude this case when calculating bounds.
1053  // (For APInts the operation is well-defined and yields SignedMin.) We
1054  // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1055  APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);
1056  if (NegL.Lower.isMinSignedValue() && NegR.Upper.isNullValue()) {
1057  // Remove -1 from the LHS. Skip if it's the only element, as this would
1058  // leave us with an empty set.
1059  if (!NegR.Lower.isAllOnesValue()) {
1060  APInt AdjNegRUpper;
1061  if (RHS.Lower.isAllOnesValue())
1062  // Negative part of [-1, X] without -1 is [SignedMin, X].
1063  AdjNegRUpper = RHS.Upper;
1064  else
1065  // [X, -1] without -1 is [X, -2].
1066  AdjNegRUpper = NegR.Upper - 1;
1067 
1068  PosRes = PosRes.unionWith(
1069  ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
1070  }
1071 
1072  // Remove SignedMin from the RHS. Skip if it's the only element, as this
1073  // would leave us with an empty set.
1074  if (NegL.Upper != SignedMin + 1) {
1075  APInt AdjNegLLower;
1076  if (Upper == SignedMin + 1)
1077  // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1078  AdjNegLLower = Lower;
1079  else
1080  // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1081  AdjNegLLower = NegL.Lower + 1;
1082 
1083  PosRes = PosRes.unionWith(
1084  ConstantRange(std::move(Lo),
1085  AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
1086  }
1087  } else {
1088  PosRes = PosRes.unionWith(
1089  ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
1090  }
1091  }
1092 
1093  ConstantRange NegRes = getEmpty();
1094  if (!PosL.isEmptySet() && !NegR.isEmptySet())
1095  // pos / neg = neg.
1096  NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
1097  PosL.Lower.sdiv(NegR.Lower) + 1);
1098 
1099  if (!NegL.isEmptySet() && !PosR.isEmptySet())
1100  // neg / pos = neg.
1101  NegRes = NegRes.unionWith(
1102  ConstantRange(NegL.Lower.sdiv(PosR.Lower),
1103  (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));
1104 
1105  // Prefer a non-wrapping signed range here.
1106  ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed);
1107 
1108  // Preserve the zero that we dropped when splitting the LHS by sign.
1109  if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1110  Res = Res.unionWith(ConstantRange(Zero));
1111  return Res;
1112 }
1113 
1115  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
1116  return getEmpty();
1117 
1118  // L % R for L < R is L.
1119  if (getUnsignedMax().ult(RHS.getUnsignedMin()))
1120  return *this;
1121 
1122  // L % R is <= L and < R.
1123  APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
1124  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
1125 }
1126 
1128  if (isEmptySet() || RHS.isEmptySet())
1129  return getEmpty();
1130 
1131  ConstantRange AbsRHS = RHS.abs();
1132  APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1133  APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1134 
1135  // Modulus by zero is UB.
1136  if (MaxAbsRHS.isNullValue())
1137  return getEmpty();
1138 
1139  if (MinAbsRHS.isNullValue())
1140  ++MinAbsRHS;
1141 
1142  APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1143 
1144  if (MinLHS.isNonNegative()) {
1145  // L % R for L < R is L.
1146  if (MaxLHS.ult(MinAbsRHS))
1147  return *this;
1148 
1149  // L % R is <= L and < R.
1150  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1151  return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(Upper));
1152  }
1153 
1154  // Same basic logic as above, but the result is negative.
1155  if (MaxLHS.isNegative()) {
1156  if (MinLHS.ugt(-MinAbsRHS))
1157  return *this;
1158 
1159  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1160  return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1161  }
1162 
1163  // LHS range crosses zero.
1164  APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1165  APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1166  return ConstantRange(std::move(Lower), std::move(Upper));
1167 }
1168 
1171  if (isEmptySet() || Other.isEmptySet())
1172  return getEmpty();
1173 
1174  // TODO: replace this with something less conservative
1175 
1177  return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
1178 }
1179 
1182  if (isEmptySet() || Other.isEmptySet())
1183  return getEmpty();
1184 
1185  // TODO: replace this with something less conservative
1186 
1188  return getNonEmpty(std::move(umax), APInt::getNullValue(getBitWidth()));
1189 }
1190 
1193  if (isEmptySet() || Other.isEmptySet())
1194  return getEmpty();
1195 
1196  APInt max = getUnsignedMax();
1197  APInt Other_umax = Other.getUnsignedMax();
1198 
1199  // If we are shifting by maximum amount of
1200  // zero return return the original range.
1201  if (Other_umax.isNullValue())
1202  return *this;
1203  // there's overflow!
1204  if (Other_umax.ugt(max.countLeadingZeros()))
1205  return getFull();
1206 
1207  // FIXME: implement the other tricky cases
1208 
1209  APInt min = getUnsignedMin();
1210  min <<= Other.getUnsignedMin();
1211  max <<= Other_umax;
1212 
1213  return ConstantRange(std::move(min), std::move(max) + 1);
1214 }
1215 
1218  if (isEmptySet() || Other.isEmptySet())
1219  return getEmpty();
1220 
1221  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1222  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1223  return getNonEmpty(std::move(min), std::move(max));
1224 }
1225 
1228  if (isEmptySet() || Other.isEmptySet())
1229  return getEmpty();
1230 
1231  // May straddle zero, so handle both positive and negative cases.
1232  // 'PosMax' is the upper bound of the result of the ashr
1233  // operation, when Upper of the LHS of ashr is a non-negative.
1234  // number. Since ashr of a non-negative number will result in a
1235  // smaller number, the Upper value of LHS is shifted right with
1236  // the minimum value of 'Other' instead of the maximum value.
1237  APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1238 
1239  // 'PosMin' is the lower bound of the result of the ashr
1240  // operation, when Lower of the LHS is a non-negative number.
1241  // Since ashr of a non-negative number will result in a smaller
1242  // number, the Lower value of LHS is shifted right with the
1243  // maximum value of 'Other'.
1244  APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1245 
1246  // 'NegMax' is the upper bound of the result of the ashr
1247  // operation, when Upper of the LHS of ashr is a negative number.
1248  // Since 'ashr' of a negative number will result in a bigger
1249  // number, the Upper value of LHS is shifted right with the
1250  // maximum value of 'Other'.
1251  APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1252 
1253  // 'NegMin' is the lower bound of the result of the ashr
1254  // operation, when Lower of the LHS of ashr is a negative number.
1255  // Since 'ashr' of a negative number will result in a bigger
1256  // number, the Lower value of LHS is shifted right with the
1257  // minimum value of 'Other'.
1258  APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1259 
1260  APInt max, min;
1261  if (getSignedMin().isNonNegative()) {
1262  // Upper and Lower of LHS are non-negative.
1263  min = PosMin;
1264  max = PosMax;
1265  } else if (getSignedMax().isNegative()) {
1266  // Upper and Lower of LHS are negative.
1267  min = NegMin;
1268  max = NegMax;
1269  } else {
1270  // Upper is non-negative and Lower is negative.
1271  min = NegMin;
1272  max = PosMax;
1273  }
1274  return getNonEmpty(std::move(min), std::move(max));
1275 }
1276 
1278  if (isEmptySet() || Other.isEmptySet())
1279  return getEmpty();
1280 
1281  APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());
1282  APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;
1283  return getNonEmpty(std::move(NewL), std::move(NewU));
1284 }
1285 
1287  if (isEmptySet() || Other.isEmptySet())
1288  return getEmpty();
1289 
1290  APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());
1291  APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;
1292  return getNonEmpty(std::move(NewL), std::move(NewU));
1293 }
1294 
1296  if (isEmptySet() || Other.isEmptySet())
1297  return getEmpty();
1298 
1299  APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());
1300  APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;
1301  return getNonEmpty(std::move(NewL), std::move(NewU));
1302 }
1303 
1305  if (isEmptySet() || Other.isEmptySet())
1306  return getEmpty();
1307 
1308  APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
1309  APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
1310  return getNonEmpty(std::move(NewL), std::move(NewU));
1311 }
1312 
1314  if (isFullSet())
1315  return getEmpty();
1316  if (isEmptySet())
1317  return getFull();
1318  return ConstantRange(Upper, Lower);
1319 }
1320 
1322  if (isEmptySet())
1323  return getEmpty();
1324 
1325  if (isSignWrappedSet()) {
1326  APInt Lo;
1327  // Check whether the range crosses zero.
1328  if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1330  else
1331  Lo = APIntOps::umin(Lower, -Upper + 1);
1332 
1333  // SignedMin is included in the result range.
1335  }
1336 
1337  APInt SMin = getSignedMin(), SMax = getSignedMax();
1338 
1339  // All non-negative.
1340  if (SMin.isNonNegative())
1341  return *this;
1342 
1343  // All negative.
1344  if (SMax.isNegative())
1345  return ConstantRange(-SMax, -SMin + 1);
1346 
1347  // Range crosses zero.
1349  APIntOps::umax(-SMin, SMax) + 1);
1350 }
1351 
1353  const ConstantRange &Other) const {
1354  if (isEmptySet() || Other.isEmptySet())
1356 
1357  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1358  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1359 
1360  // a u+ b overflows high iff a u> ~b.
1361  if (Min.ugt(~OtherMin))
1363  if (Max.ugt(~OtherMax))
1366 }
1367 
1369  const ConstantRange &Other) const {
1370  if (isEmptySet() || Other.isEmptySet())
1372 
1373  APInt Min = getSignedMin(), Max = getSignedMax();
1374  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1375 
1378 
1379  // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1380  // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1381  if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1382  Min.sgt(SignedMax - OtherMin))
1384  if (Max.isNegative() && OtherMax.isNegative() &&
1385  Max.slt(SignedMin - OtherMax))
1387 
1388  if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1389  Max.sgt(SignedMax - OtherMax))
1391  if (Min.isNegative() && OtherMin.isNegative() &&
1392  Min.slt(SignedMin - OtherMin))
1394 
1396 }
1397 
1399  const ConstantRange &Other) const {
1400  if (isEmptySet() || Other.isEmptySet())
1402 
1403  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1404  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1405 
1406  // a u- b overflows low iff a u< b.
1407  if (Max.ult(OtherMin))
1409  if (Min.ult(OtherMax))
1412 }
1413 
1415  const ConstantRange &Other) const {
1416  if (isEmptySet() || Other.isEmptySet())
1418 
1419  APInt Min = getSignedMin(), Max = getSignedMax();
1420  APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1421 
1424 
1425  // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
1426  // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
1427  if (Min.isNonNegative() && OtherMax.isNegative() &&
1428  Min.sgt(SignedMax + OtherMax))
1430  if (Max.isNegative() && OtherMin.isNonNegative() &&
1431  Max.slt(SignedMin + OtherMin))
1433 
1434  if (Max.isNonNegative() && OtherMin.isNegative() &&
1435  Max.sgt(SignedMax + OtherMin))
1437  if (Min.isNegative() && OtherMax.isNonNegative() &&
1438  Min.slt(SignedMin + OtherMax))
1440 
1442 }
1443 
1445  const ConstantRange &Other) const {
1446  if (isEmptySet() || Other.isEmptySet())
1448 
1449  APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1450  APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1451  bool Overflow;
1452 
1453  (void) Min.umul_ov(OtherMin, Overflow);
1454  if (Overflow)
1456 
1457  (void) Max.umul_ov(OtherMax, Overflow);
1458  if (Overflow)
1460 
1462 }
1463 
1465  if (isFullSet())
1466  OS << "full-set";
1467  else if (isEmptySet())
1468  OS << "empty-set";
1469  else
1470  OS << "[" << Lower << "," << Upper << ")";
1471 }
1472 
1473 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1475  print(dbgs());
1476 }
1477 #endif
1478 
1480  const unsigned NumRanges = Ranges.getNumOperands() / 2;
1481  assert(NumRanges >= 1 && "Must have at least one range!");
1482  assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1483 
1484  auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1485  auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1486 
1487  ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1488 
1489  for (unsigned i = 1; i < NumRanges; ++i) {
1490  auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1491  auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1492 
1493  // Note: unionWith will potentially create a range that contains values not
1494  // contained in any of the original N ranges.
1495  CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1496  }
1497 
1498  return CR;
1499 }
ConstantRange(uint32_t BitWidth, bool isFullSet)
Initialize a full or empty set for the specified bit width.
uint64_t CallInst * C
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1412
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:888
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:2752
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:484
Always overflows in the direction of signed/unsigned min value.
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition: APInt.cpp:1647
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:46
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:912
APInt uadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2023
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1203
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1576
This file contains the declarations for metadata subclasses.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:647
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
ConstantRange lshr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a logical right shift of a value i...
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:953
unsigned less or equal
Definition: InstrTypes.h:758
OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const
Return whether unsigned add of the two ranges always/never overflows.
unsigned less than
Definition: InstrTypes.h:757
ConstantRange truncate(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
bool sgt(const APInt &RHS) const
Signed greather than comparison.
Definition: APInt.h:1273
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:865
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1389
ConstantRange ashr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a arithmetic right shift of a valu...
Metadata node.
Definition: Metadata.h:863
ConstantRange udiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned division of a value in...
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1068
OverflowResult signedAddMayOverflow(const ConstantRange &Other) const
Return whether signed add of the two ranges always/never overflows.
static ConstantRange 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...
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:2770
void print(raw_ostream &OS) const
Print out the bounds to a stream.
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:39
uint64_t High
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:534
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1517
bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
Definition: BitVector.h:937
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:831
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:946
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:2118
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1541
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2113
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.
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1461
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Get a value with upper bits starting at loBit set.
Definition: APInt.h:623
OverflowResult
Represents whether an operation on the given constant range is known to always or never overflow...
bool isAllNegative() const
Return true if all values in this range are negative.
void dump() const
Allow printing from a debugger easily.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
The operation itself must be expressed in terms of simpler actions on this target.
Definition: LegalizerInfo.h:72
bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the largest range such that all values in the returned range satisfy the given predicate with...
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:95
bool isSizeStrictlySmallerThan(const ConstantRange &CR) const
Compare set size of this range with the range CR.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:635
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:395
int getMinValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the minimum value of an extendable operand.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
Definition: APInt.h:390
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h: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:1184
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...
bool isOneValue() const
Determine if this is a value of 1.
Definition: APInt.h:410
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:587
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
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:442
Always overflows in the direction of signed/unsigned max value.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
bool isBinaryOp() const
Definition: Instruction.h:130
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl...
Definition: Operator.h:66
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type. ...
void clearSignBit()
Set the sign bit to 0.
Definition: APInt.h:1478
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.
APInt uadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1938
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
APInt ssub_sat(const APInt &RHS) const
Definition: APInt.cpp:2032
OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const
Return whether unsigned sub of the two ranges always/never overflows.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:970
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
signed greater than
Definition: InstrTypes.h:759
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2123
bool isEmptySet() const
Return true if this set contains no members.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:946
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
This class represents a range of values.
Definition: ConstantRange.h:47
signed less than
Definition: InstrTypes.h:761
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:541
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1292
ConstantRange binaryOr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-or of a value in this ran...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1654
signed less or equal
Definition: InstrTypes.h:762
Class for arbitrary precision integers.
Definition: APInt.h:69
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1222
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2128
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:529
const APInt * getSingleMissingElement() const
If this set contains all but a single element, return it, otherwise return null.
ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
bool isUnknown() const
Returns true if we don&#39;t know any bits.
Definition: KnownBits.h:62
#define Success
ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
Definition: APInt.h:1254
ConstantRange ssub_sat(const ConstantRange &Other) const
Perform a signed saturating subtraction of two constant ranges.
unsigned greater or equal
Definition: InstrTypes.h:756
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:1973
bool isSingleElement() const
Return true if this set contains exactly one member.
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
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:544
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1931
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:45
APInt usub_sat(const APInt &RHS) const
Definition: APInt.cpp:2042
unsigned greater than
Definition: InstrTypes.h:755
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:98
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
Definition: APInt.h:1604
ConstantRange shl(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a left shift of a value in this ra...
static APInt getNullValue(unsigned numBits)
Get the &#39;0&#39; value.
Definition: APInt.h:568
APInt sadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2013
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1074
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
static ConstantRange getPreferredRange(const ConstantRange &CR1, const ConstantRange &CR2, ConstantRange::PreferredRangeType Type)
APInt sextOrSelf(unsigned width) const
Sign extend or truncate to width.
Definition: APInt.cpp:952
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:405
signed greater or equal
Definition: InstrTypes.h:760
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...