LLVM  6.0.0svn
ConstantRange.cpp
Go to the documentation of this file.
1 //===- ConstantRange.cpp - ConstantRange implementation -------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Represent a range of possible values that may occur when the program is run
11 // for an integral value. This keeps track of a lower and upper bound for the
12 // constant, which MAY wrap around the end of the numeric range. To do this, it
13 // keeps track of a [lower, upper) bound, which specifies an interval just like
14 // STL iterators. When used with boolean values, the following are important
15 // ranges (other integral ranges use min/max values for special range values):
16 //
17 // [F, F) = {} = Empty set
18 // [T, F) = {T}
19 // [F, T) = {F}
20 // [T, T) = {F, T} = Full set
21 //
22 //===----------------------------------------------------------------------===//
23 
24 #include "llvm/ADT/APInt.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"
35 #include <algorithm>
36 #include <cassert>
37 #include <cstdint>
38 
39 using namespace llvm;
40 
42  : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
43  Upper(Lower) {}
44 
46  : Lower(std::move(V)), Upper(Lower + 1) {}
47 
49  : Lower(std::move(L)), Upper(std::move(U)) {
50  assert(Lower.getBitWidth() == Upper.getBitWidth() &&
51  "ConstantRange with unequal bit widths");
52  assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
53  "Lower == Upper, but they aren't min or max value!");
54 }
55 
57  const ConstantRange &CR) {
58  if (CR.isEmptySet())
59  return CR;
60 
61  uint32_t W = CR.getBitWidth();
62  switch (Pred) {
63  default:
64  llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
65  case CmpInst::ICMP_EQ:
66  return CR;
67  case CmpInst::ICMP_NE:
68  if (CR.isSingleElement())
69  return ConstantRange(CR.getUpper(), CR.getLower());
70  return ConstantRange(W);
71  case CmpInst::ICMP_ULT: {
72  APInt UMax(CR.getUnsignedMax());
73  if (UMax.isMinValue())
74  return ConstantRange(W, /* empty */ false);
75  return ConstantRange(APInt::getMinValue(W), std::move(UMax));
76  }
77  case CmpInst::ICMP_SLT: {
78  APInt SMax(CR.getSignedMax());
79  if (SMax.isMinSignedValue())
80  return ConstantRange(W, /* empty */ false);
81  return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
82  }
83  case CmpInst::ICMP_ULE: {
84  APInt UMax(CR.getUnsignedMax());
85  if (UMax.isMaxValue())
86  return ConstantRange(W);
87  return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
88  }
89  case CmpInst::ICMP_SLE: {
90  APInt SMax(CR.getSignedMax());
91  if (SMax.isMaxSignedValue())
92  return ConstantRange(W);
93  return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
94  }
95  case CmpInst::ICMP_UGT: {
96  APInt UMin(CR.getUnsignedMin());
97  if (UMin.isMaxValue())
98  return ConstantRange(W, /* empty */ false);
99  return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
100  }
101  case CmpInst::ICMP_SGT: {
102  APInt SMin(CR.getSignedMin());
103  if (SMin.isMaxSignedValue())
104  return ConstantRange(W, /* empty */ false);
105  return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
106  }
107  case CmpInst::ICMP_UGE: {
108  APInt UMin(CR.getUnsignedMin());
109  if (UMin.isMinValue())
110  return ConstantRange(W);
111  return ConstantRange(std::move(UMin), APInt::getNullValue(W));
112  }
113  case CmpInst::ICMP_SGE: {
114  APInt SMin(CR.getSignedMin());
115  if (SMin.isMinSignedValue())
116  return ConstantRange(W);
117  return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
118  }
119  }
120 }
121 
123  const ConstantRange &CR) {
124  // Follows from De-Morgan's laws:
125  //
126  // ~(~A union ~B) == A intersect B.
127  //
129  .inverse();
130 }
131 
133  const APInt &C) {
134  // Computes the exact range that is equal to both the constant ranges returned
135  // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
136  // when RHS is a singleton such as an APInt and so the assert is valid.
137  // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
138  // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
139  //
141  return makeAllowedICmpRegion(Pred, C);
142 }
143 
145  APInt &RHS) const {
146  bool Success = false;
147 
148  if (isFullSet() || isEmptySet()) {
150  RHS = APInt(getBitWidth(), 0);
151  Success = true;
152  } else if (auto *OnlyElt = getSingleElement()) {
153  Pred = CmpInst::ICMP_EQ;
154  RHS = *OnlyElt;
155  Success = true;
156  } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
157  Pred = CmpInst::ICMP_NE;
158  RHS = *OnlyMissingElt;
159  Success = true;
160  } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
161  Pred =
163  RHS = getUpper();
164  Success = true;
165  } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
166  Pred =
168  RHS = getLower();
169  Success = true;
170  }
171 
172  assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
173  "Bad result!");
174 
175  return Success;
176 }
177 
180  const ConstantRange &Other,
181  unsigned NoWrapKind) {
182  using OBO = OverflowingBinaryOperator;
183 
184  // Computes the intersection of CR0 and CR1. It is different from
185  // intersectWith in that the ConstantRange returned will only contain elements
186  // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
187  // not, of both X and Y).
188  auto SubsetIntersect =
189  [](const ConstantRange &CR0, const ConstantRange &CR1) {
190  return CR0.inverse().unionWith(CR1.inverse()).inverse();
191  };
192 
193  assert(BinOp >= Instruction::BinaryOpsBegin &&
194  BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
195 
196  assert((NoWrapKind == OBO::NoSignedWrap ||
197  NoWrapKind == OBO::NoUnsignedWrap ||
198  NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
199  "NoWrapKind invalid!");
200 
201  unsigned BitWidth = Other.getBitWidth();
202  if (BinOp != Instruction::Add)
203  // Conservative answer: empty set
204  return ConstantRange(BitWidth, false);
205 
206  if (auto *C = Other.getSingleElement())
207  if (C->isNullValue())
208  // Full set: nothing signed / unsigned wraps when added to 0.
209  return ConstantRange(BitWidth);
210 
211  ConstantRange Result(BitWidth);
212 
213  if (NoWrapKind & OBO::NoUnsignedWrap)
214  Result =
215  SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
216  -Other.getUnsignedMax()));
217 
218  if (NoWrapKind & OBO::NoSignedWrap) {
219  const APInt &SignedMin = Other.getSignedMin();
220  const APInt &SignedMax = Other.getSignedMax();
221 
222  if (SignedMax.isStrictlyPositive())
223  Result = SubsetIntersect(
224  Result,
226  APInt::getSignedMinValue(BitWidth) - SignedMax));
227 
228  if (SignedMin.isNegative())
229  Result = SubsetIntersect(
230  Result, ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
231  APInt::getSignedMinValue(BitWidth)));
232  }
233 
234  return Result;
235 }
236 
238  return Lower == Upper && Lower.isMaxValue();
239 }
240 
242  return Lower == Upper && Lower.isMinValue();
243 }
244 
246  return Lower.ugt(Upper);
247 }
248 
252 }
253 
255  if (isFullSet())
257 
258  // This is also correct for wrapped sets.
259  return (Upper - Lower).zext(getBitWidth()+1);
260 }
261 
262 bool
264  assert(getBitWidth() == Other.getBitWidth());
265  if (isFullSet())
266  return false;
267  if (Other.isFullSet())
268  return true;
269  return (Upper - Lower).ult(Other.Upper - Other.Lower);
270 }
271 
272 bool
273 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
274  assert(MaxSize && "MaxSize can't be 0.");
275  // If this a full set, we need special handling to avoid needing an extra bit
276  // to represent the size.
277  if (isFullSet())
278  return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
279 
280  return (Upper - Lower).ugt(MaxSize);
281 }
282 
284  if (isFullSet() || isWrappedSet())
286  return getUpper() - 1;
287 }
288 
290  if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
292  return getLower();
293 }
294 
296  if (isFullSet() || Lower.sgt(Upper))
298  return getUpper() - 1;
299 }
300 
302  if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
304  return getLower();
305 }
306 
307 bool ConstantRange::contains(const APInt &V) const {
308  if (Lower == Upper)
309  return isFullSet();
310 
311  if (!isWrappedSet())
312  return Lower.ule(V) && V.ult(Upper);
313  return Lower.ule(V) || V.ult(Upper);
314 }
315 
317  if (isFullSet() || Other.isEmptySet()) return true;
318  if (isEmptySet() || Other.isFullSet()) return false;
319 
320  if (!isWrappedSet()) {
321  if (Other.isWrappedSet())
322  return false;
323 
324  return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
325  }
326 
327  if (!Other.isWrappedSet())
328  return Other.getUpper().ule(Upper) ||
329  Lower.ule(Other.getLower());
330 
331  return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
332 }
333 
335  assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
336  // If the set is empty or full, don't modify the endpoints.
337  if (Lower == Upper)
338  return *this;
339  return ConstantRange(Lower - Val, Upper - Val);
340 }
341 
343  return intersectWith(CR.inverse());
344 }
345 
347  assert(getBitWidth() == CR.getBitWidth() &&
348  "ConstantRange types don't agree!");
349 
350  // Handle common cases.
351  if ( isEmptySet() || CR.isFullSet()) return *this;
352  if (CR.isEmptySet() || isFullSet()) return CR;
353 
354  if (!isWrappedSet() && CR.isWrappedSet())
355  return CR.intersectWith(*this);
356 
357  if (!isWrappedSet() && !CR.isWrappedSet()) {
358  if (Lower.ult(CR.Lower)) {
359  if (Upper.ule(CR.Lower))
360  return ConstantRange(getBitWidth(), false);
361 
362  if (Upper.ult(CR.Upper))
363  return ConstantRange(CR.Lower, Upper);
364 
365  return CR;
366  }
367  if (Upper.ult(CR.Upper))
368  return *this;
369 
370  if (Lower.ult(CR.Upper))
371  return ConstantRange(Lower, CR.Upper);
372 
373  return ConstantRange(getBitWidth(), false);
374  }
375 
376  if (isWrappedSet() && !CR.isWrappedSet()) {
377  if (CR.Lower.ult(Upper)) {
378  if (CR.Upper.ult(Upper))
379  return CR;
380 
381  if (CR.Upper.ule(Lower))
382  return ConstantRange(CR.Lower, Upper);
383 
385  return *this;
386  return CR;
387  }
388  if (CR.Lower.ult(Lower)) {
389  if (CR.Upper.ule(Lower))
390  return ConstantRange(getBitWidth(), false);
391 
392  return ConstantRange(Lower, CR.Upper);
393  }
394  return CR;
395  }
396 
397  if (CR.Upper.ult(Upper)) {
398  if (CR.Lower.ult(Upper)) {
400  return *this;
401  return CR;
402  }
403 
404  if (CR.Lower.ult(Lower))
405  return ConstantRange(Lower, CR.Upper);
406 
407  return CR;
408  }
409  if (CR.Upper.ule(Lower)) {
410  if (CR.Lower.ult(Lower))
411  return *this;
412 
413  return ConstantRange(CR.Lower, Upper);
414  }
416  return *this;
417  return CR;
418 }
419 
421  assert(getBitWidth() == CR.getBitWidth() &&
422  "ConstantRange types don't agree!");
423 
424  if ( isFullSet() || CR.isEmptySet()) return *this;
425  if (CR.isFullSet() || isEmptySet()) return CR;
426 
427  if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
428 
429  if (!isWrappedSet() && !CR.isWrappedSet()) {
430  if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
431  // If the two ranges are disjoint, find the smaller gap and bridge it.
432  APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
433  if (d1.ult(d2))
434  return ConstantRange(Lower, CR.Upper);
435  return ConstantRange(CR.Lower, Upper);
436  }
437 
438  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
439  APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
440 
441  if (L.isNullValue() && U.isNullValue())
442  return ConstantRange(getBitWidth());
443 
444  return ConstantRange(std::move(L), std::move(U));
445  }
446 
447  if (!CR.isWrappedSet()) {
448  // ------U L----- and ------U L----- : this
449  // L--U L--U : CR
450  if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
451  return *this;
452 
453  // ------U L----- : this
454  // L---------U : CR
455  if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
456  return ConstantRange(getBitWidth());
457 
458  // ----U L---- : this
459  // L---U : CR
460  // <d1> <d2>
461  if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
462  APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
463  if (d1.ult(d2))
464  return ConstantRange(Lower, CR.Upper);
465  return ConstantRange(CR.Lower, Upper);
466  }
467 
468  // ----U L----- : this
469  // L----U : CR
470  if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
471  return ConstantRange(CR.Lower, Upper);
472 
473  // ------U L---- : this
474  // L-----U : CR
475  assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
476  "ConstantRange::unionWith missed a case with one range wrapped");
477  return ConstantRange(Lower, CR.Upper);
478  }
479 
480  // ------U L---- and ------U L---- : this
481  // -U L----------- and ------------U L : CR
482  if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
483  return ConstantRange(getBitWidth());
484 
485  APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
486  APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
487 
488  return ConstantRange(std::move(L), std::move(U));
489 }
490 
492  uint32_t ResultBitWidth) const {
493  switch (CastOp) {
494  default:
495  llvm_unreachable("unsupported cast type");
496  case Instruction::Trunc:
497  return truncate(ResultBitWidth);
498  case Instruction::SExt:
499  return signExtend(ResultBitWidth);
500  case Instruction::ZExt:
501  return zeroExtend(ResultBitWidth);
502  case Instruction::BitCast:
503  return *this;
504  case Instruction::FPToUI:
505  case Instruction::FPToSI:
506  if (getBitWidth() == ResultBitWidth)
507  return *this;
508  else
509  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
510  case Instruction::UIToFP: {
511  // TODO: use input range if available
512  auto BW = getBitWidth();
513  APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
514  APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
515  return ConstantRange(std::move(Min), std::move(Max));
516  }
517  case Instruction::SIToFP: {
518  // TODO: use input range if available
519  auto BW = getBitWidth();
520  APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
521  APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
522  return ConstantRange(std::move(SMin), std::move(SMax));
523  }
524  case Instruction::FPTrunc:
525  case Instruction::FPExt:
526  case Instruction::IntToPtr:
527  case Instruction::PtrToInt:
528  case Instruction::AddrSpaceCast:
529  // Conservatively return full set.
530  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
531  };
532 }
533 
535  if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
536 
537  unsigned SrcTySize = getBitWidth();
538  assert(SrcTySize < DstTySize && "Not a value extension");
539  if (isFullSet() || isWrappedSet()) {
540  // Change into [0, 1 << src bit width)
541  APInt LowerExt(DstTySize, 0);
542  if (!Upper) // special case: [X, 0) -- not really wrapping around
543  LowerExt = Lower.zext(DstTySize);
544  return ConstantRange(std::move(LowerExt),
545  APInt::getOneBitSet(DstTySize, SrcTySize));
546  }
547 
548  return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
549 }
550 
552  if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
553 
554  unsigned SrcTySize = getBitWidth();
555  assert(SrcTySize < DstTySize && "Not a value extension");
556 
557  // special case: [X, INT_MIN) -- not really wrapping around
558  if (Upper.isMinSignedValue())
559  return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
560 
561  if (isFullSet() || isSignWrappedSet()) {
562  return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
563  APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
564  }
565 
566  return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
567 }
568 
570  assert(getBitWidth() > DstTySize && "Not a value truncation");
571  if (isEmptySet())
572  return ConstantRange(DstTySize, /*isFullSet=*/false);
573  if (isFullSet())
574  return ConstantRange(DstTySize, /*isFullSet=*/true);
575 
576  APInt LowerDiv(Lower), UpperDiv(Upper);
577  ConstantRange Union(DstTySize, /*isFullSet=*/false);
578 
579  // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
580  // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
581  // then we do the union with [MaxValue, Upper)
582  if (isWrappedSet()) {
583  // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
584  // truncated range.
585  if (Upper.getActiveBits() > DstTySize ||
586  Upper.countTrailingOnes() == DstTySize)
587  return ConstantRange(DstTySize, /*isFullSet=*/true);
588 
589  Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
590  UpperDiv.setAllBits();
591 
592  // Union covers the MaxValue case, so return if the remaining range is just
593  // MaxValue(DstTy).
594  if (LowerDiv == UpperDiv)
595  return Union;
596  }
597 
598  // Chop off the most significant bits that are past the destination bitwidth.
599  if (LowerDiv.getActiveBits() > DstTySize) {
600  // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
601  APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
602  LowerDiv -= Adjust;
603  UpperDiv -= Adjust;
604  }
605 
606  unsigned UpperDivWidth = UpperDiv.getActiveBits();
607  if (UpperDivWidth <= DstTySize)
608  return ConstantRange(LowerDiv.trunc(DstTySize),
609  UpperDiv.trunc(DstTySize)).unionWith(Union);
610 
611  // The truncated value wraps around. Check if we can do better than fullset.
612  if (UpperDivWidth == DstTySize + 1) {
613  // Clear the MSB so that UpperDiv wraps around.
614  UpperDiv.clearBit(DstTySize);
615  if (UpperDiv.ult(LowerDiv))
616  return ConstantRange(LowerDiv.trunc(DstTySize),
617  UpperDiv.trunc(DstTySize)).unionWith(Union);
618  }
619 
620  return ConstantRange(DstTySize, /*isFullSet=*/true);
621 }
622 
624  unsigned SrcTySize = getBitWidth();
625  if (SrcTySize > DstTySize)
626  return truncate(DstTySize);
627  if (SrcTySize < DstTySize)
628  return zeroExtend(DstTySize);
629  return *this;
630 }
631 
633  unsigned SrcTySize = getBitWidth();
634  if (SrcTySize > DstTySize)
635  return truncate(DstTySize);
636  if (SrcTySize < DstTySize)
637  return signExtend(DstTySize);
638  return *this;
639 }
640 
642  const ConstantRange &Other) const {
643  assert(BinOp >= Instruction::BinaryOpsBegin &&
644  BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
645 
646  switch (BinOp) {
647  case Instruction::Add:
648  return add(Other);
649  case Instruction::Sub:
650  return sub(Other);
651  case Instruction::Mul:
652  return multiply(Other);
653  case Instruction::UDiv:
654  return udiv(Other);
655  case Instruction::Shl:
656  return shl(Other);
657  case Instruction::LShr:
658  return lshr(Other);
659  case Instruction::And:
660  return binaryAnd(Other);
661  case Instruction::Or:
662  return binaryOr(Other);
663  // Note: floating point operations applied to abstract ranges are just
664  // ideal integer operations with a lossy representation
665  case Instruction::FAdd:
666  return add(Other);
667  case Instruction::FSub:
668  return sub(Other);
669  case Instruction::FMul:
670  return multiply(Other);
671  default:
672  // Conservatively return full set.
673  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
674  }
675 }
676 
679  if (isEmptySet() || Other.isEmptySet())
680  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
681  if (isFullSet() || Other.isFullSet())
682  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
683 
684  APInt NewLower = getLower() + Other.getLower();
685  APInt NewUpper = getUpper() + Other.getUpper() - 1;
686  if (NewLower == NewUpper)
687  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
688 
689  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
690  if (X.isSizeStrictlySmallerThan(*this) ||
691  X.isSizeStrictlySmallerThan(Other))
692  // We've wrapped, therefore, full set.
693  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
694  return X;
695 }
696 
698  // Calculate the subset of this range such that "X + Other" is
699  // guaranteed not to wrap (overflow) for all X in this subset.
700  // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
701  // passing a single element range.
703  ConstantRange(Other),
705  auto NSWConstrainedRange = intersectWith(NSWRange);
706 
707  return NSWConstrainedRange.add(ConstantRange(Other));
708 }
709 
712  if (isEmptySet() || Other.isEmptySet())
713  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
714  if (isFullSet() || Other.isFullSet())
715  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
716 
717  APInt NewLower = getLower() - Other.getUpper() + 1;
718  APInt NewUpper = getUpper() - Other.getLower();
719  if (NewLower == NewUpper)
720  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
721 
722  ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
723  if (X.isSizeStrictlySmallerThan(*this) ||
724  X.isSizeStrictlySmallerThan(Other))
725  // We've wrapped, therefore, full set.
726  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
727  return X;
728 }
729 
732  // TODO: If either operand is a single element and the multiply is known to
733  // be non-wrapping, round the result min and max value to the appropriate
734  // multiple of that element. If wrapping is possible, at least adjust the
735  // range according to the greatest power-of-two factor of the single element.
736 
737  if (isEmptySet() || Other.isEmptySet())
738  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
739 
740  // Multiplication is signedness-independent. However different ranges can be
741  // obtained depending on how the input ranges are treated. These different
742  // ranges are all conservatively correct, but one might be better than the
743  // other. We calculate two ranges; one treating the inputs as unsigned
744  // and the other signed, then return the smallest of these ranges.
745 
746  // Unsigned range first.
747  APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
748  APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
749  APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
750  APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
751 
752  ConstantRange Result_zext = ConstantRange(this_min * Other_min,
753  this_max * Other_max + 1);
754  ConstantRange UR = Result_zext.truncate(getBitWidth());
755 
756  // If the unsigned range doesn't wrap, and isn't negative then it's a range
757  // from one positive number to another which is as good as we can generate.
758  // In this case, skip the extra work of generating signed ranges which aren't
759  // going to be better than this range.
760  if (!UR.isWrappedSet() &&
761  (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
762  return UR;
763 
764  // Now the signed range. Because we could be dealing with negative numbers
765  // here, the lower bound is the smallest of the cartesian product of the
766  // lower and upper ranges; for example:
767  // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
768  // Similarly for the upper bound, swapping min for max.
769 
770  this_min = getSignedMin().sext(getBitWidth() * 2);
771  this_max = getSignedMax().sext(getBitWidth() * 2);
772  Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
773  Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
774 
775  auto L = {this_min * Other_min, this_min * Other_max,
776  this_max * Other_min, this_max * Other_max};
777  auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
778  ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
779  ConstantRange SR = Result_sext.truncate(getBitWidth());
780 
781  return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
782 }
783 
786  // X smax Y is: range(smax(X_smin, Y_smin),
787  // smax(X_smax, Y_smax))
788  if (isEmptySet() || Other.isEmptySet())
789  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
790  APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
791  APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
792  if (NewU == NewL)
793  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
794  return ConstantRange(std::move(NewL), std::move(NewU));
795 }
796 
799  // X umax Y is: range(umax(X_umin, Y_umin),
800  // umax(X_umax, Y_umax))
801  if (isEmptySet() || Other.isEmptySet())
802  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
804  APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
805  if (NewU == NewL)
806  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
807  return ConstantRange(std::move(NewL), std::move(NewU));
808 }
809 
812  // X smin Y is: range(smin(X_smin, Y_smin),
813  // smin(X_smax, Y_smax))
814  if (isEmptySet() || Other.isEmptySet())
815  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
816  APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
817  APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
818  if (NewU == NewL)
819  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
820  return ConstantRange(std::move(NewL), std::move(NewU));
821 }
822 
825  // X umin Y is: range(umin(X_umin, Y_umin),
826  // umin(X_umax, Y_umax))
827  if (isEmptySet() || Other.isEmptySet())
828  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
830  APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
831  if (NewU == NewL)
832  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
833  return ConstantRange(std::move(NewL), std::move(NewU));
834 }
835 
838  if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
839  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
840  if (RHS.isFullSet())
841  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
842 
843  APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
844 
845  APInt RHS_umin = RHS.getUnsignedMin();
846  if (RHS_umin.isNullValue()) {
847  // We want the lowest value in RHS excluding zero. Usually that would be 1
848  // except for a range in the form of [X, 1) in which case it would be X.
849  if (RHS.getUpper() == 1)
850  RHS_umin = RHS.getLower();
851  else
852  RHS_umin = 1;
853  }
854 
855  APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
856 
857  // If the LHS is Full and the RHS is a wrapped interval containing 1 then
858  // this could occur.
859  if (Lower == Upper)
860  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
861 
862  return ConstantRange(std::move(Lower), std::move(Upper));
863 }
864 
867  if (isEmptySet() || Other.isEmptySet())
868  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
869 
870  // TODO: replace this with something less conservative
871 
873  if (umin.isAllOnesValue())
874  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
875  return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
876 }
877 
880  if (isEmptySet() || Other.isEmptySet())
881  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
882 
883  // TODO: replace this with something less conservative
884 
886  if (umax.isNullValue())
887  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
888  return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
889 }
890 
893  if (isEmptySet() || Other.isEmptySet())
894  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
895 
897  APInt Other_umax = Other.getUnsignedMax();
898 
899  // there's overflow!
900  if (Other_umax.uge(max.countLeadingZeros()))
901  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
902 
903  // FIXME: implement the other tricky cases
904 
905  APInt min = getUnsignedMin();
906  min <<= Other.getUnsignedMin();
907  max <<= Other_umax;
908 
909  return ConstantRange(std::move(min), std::move(max) + 1);
910 }
911 
914  if (isEmptySet() || Other.isEmptySet())
915  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
916 
917  APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
918  APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
919  if (min == max)
920  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
921 
922  return ConstantRange(std::move(min), std::move(max));
923 }
924 
926  if (isFullSet())
927  return ConstantRange(getBitWidth(), /*isFullSet=*/false);
928  if (isEmptySet())
929  return ConstantRange(getBitWidth(), /*isFullSet=*/true);
930  return ConstantRange(Upper, Lower);
931 }
932 
934  if (isFullSet())
935  OS << "full-set";
936  else if (isEmptySet())
937  OS << "empty-set";
938  else
939  OS << "[" << Lower << "," << Upper << ")";
940 }
941 
942 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
944  print(dbgs());
945 }
946 #endif
947 
949  const unsigned NumRanges = Ranges.getNumOperands() / 2;
950  assert(NumRanges >= 1 && "Must have at least one range!");
951  assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
952 
953  auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
954  auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
955 
956  ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
957 
958  for (unsigned i = 1; i < NumRanges; ++i) {
959  auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
960  auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
961 
962  // Note: unionWith will potentially create a range that contains values not
963  // contained in any of the original N ranges.
964  CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
965  }
966 
967  return CR;
968 }
uint64_t CallInst * C
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:841
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
ConstantRange unionWith(const ConstantRange &CR) const
Return the range that results from the union of this range with another range.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:449
ConstantRange addWithNoSignedWrap(const APInt &Other) const
Return a new range representing the possible values resulting from a known NSW addition of a value in...
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:865
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1183
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1519
This file contains the declarations for metadata subclasses.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:641
bool isSizeLargerThan(uint64_t MaxSize) const
ConstantRange lshr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a logical right shift of a value i...
unsigned less or equal
Definition: InstrTypes.h:879
unsigned less than
Definition: InstrTypes.h:878
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:1253
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:818
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1369
Metadata node.
Definition: Metadata.h:862
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:1067
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...
void print(raw_ostream &OS) const
Print out the bounds to a stream.
uint64_t High
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:528
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1488
bool isWrappedSet() const
Return true if this set wraps around the top of the range.
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:920
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:951
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:362
APInt zextOrSelf(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:899
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:736
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:2089
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1512
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2084
int getMaxValue(MCInstrInfo const &MCII, MCInst const &MCI)
Return the maximum value of an extendable operand.
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1441
ConstantRange intersectWith(const ConstantRange &CR) const
Return the range that results from the intersection of this range with another range.
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Get a value with upper bits starting at loBit set.
Definition: APInt.h:617
APInt getSetSize() const
Return the number of elements in this set.
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...
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 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:629
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:357
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:389
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:384
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
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:1164
bool isSignWrappedSet() const
Return true if this set wraps around the INT_MIN of its bitwidth.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:581
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:436
ConstantRange(uint32_t BitWidth, bool isFullSet=true)
Initialize a full (the default) or empty set for the specified bit width.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:853
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl...
Definition: Operator.h:67
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. ...
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
#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:959
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
signed greater than
Definition: InstrTypes.h:880
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2094
bool isEmptySet() const
Return true if this set contains no members.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
This class represents a range of values.
Definition: ConstantRange.h:47
signed less than
Definition: InstrTypes.h:882
bool isMaxValue() const
Determine if this is the largest unsigned value.
Definition: APInt.h:414
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:535
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1272
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:1625
signed less or equal
Definition: InstrTypes.h:883
Class for arbitrary precision integers.
Definition: APInt.h:69
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1202
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2099
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:523
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...
#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:1234
unsigned greater or equal
Definition: InstrTypes.h:877
const APInt & getLower() const
Return the lower value for this range.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:430
bool isSingleElement() const
Return true if this set contains exactly one member.
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Return the largest range containing all X such that "X BinOpC 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:538
ConstantRange multiply(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a multiplication of a value in thi...
ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
unsigned greater than
Definition: InstrTypes.h:876
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
Definition: APInt.h:1575
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:562
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1073
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...
APInt sextOrSelf(unsigned width) const
Sign extend or truncate to width.
Definition: APInt.cpp:905
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:399
signed greater or equal
Definition: InstrTypes.h:881
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...