1 //===- ConstantRange.cpp - ConstantRange implementation -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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):
17 // [F, F) = {} = Empty set
20 // [T, T) = {F, T} = Full set
22 //===----------------------------------------------------------------------===//
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"
33 #include "llvm/Support/ErrorHandling.h"
34 #include "llvm/Support/raw_ostream.h"
41 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
42 : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
45 ConstantRange::ConstantRange(APInt V)
46 : Lower(std::move(V)), Upper(Lower + 1) {}
48 ConstantRange::ConstantRange(APInt L, APInt U)
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!");
56 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
57 const ConstantRange &CR) {
61 uint32_t W = CR.getBitWidth();
64 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
65 case CmpInst::ICMP_EQ:
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));
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));
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);
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);
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));
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));
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));
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));
122 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
123 const ConstantRange &CR) {
124 // Follows from De-Morgan's laws:
126 // ~(~A union ~B) == A intersect B.
128 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
132 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
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).
140 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
141 return makeAllowedICmpRegion(Pred, C);
144 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
146 bool Success = false;
148 if (isFullSet() || isEmptySet()) {
149 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
150 RHS = APInt(getBitWidth(), 0);
152 } else if (auto *OnlyElt = getSingleElement()) {
153 Pred = CmpInst::ICMP_EQ;
156 } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
157 Pred = CmpInst::ICMP_NE;
158 RHS = *OnlyMissingElt;
160 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
162 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
165 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
167 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
172 assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
179 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
180 const ConstantRange &Other,
181 unsigned NoWrapKind) {
182 using OBO = OverflowingBinaryOperator;
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();
193 assert(BinOp >= Instruction::BinaryOpsBegin &&
194 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
196 assert((NoWrapKind == OBO::NoSignedWrap ||
197 NoWrapKind == OBO::NoUnsignedWrap ||
198 NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
199 "NoWrapKind invalid!");
201 unsigned BitWidth = Other.getBitWidth();
202 ConstantRange Result(BitWidth);
206 // Conservative answer: empty set
207 return ConstantRange(BitWidth, false);
209 case Instruction::Add:
210 if (auto *C = Other.getSingleElement())
211 if (C->isNullValue())
212 // Full set: nothing signed / unsigned wraps when added to 0.
213 return ConstantRange(BitWidth);
214 if (NoWrapKind & OBO::NoUnsignedWrap)
216 SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
217 -Other.getUnsignedMax()));
218 if (NoWrapKind & OBO::NoSignedWrap) {
219 const APInt &SignedMin = Other.getSignedMin();
220 const APInt &SignedMax = Other.getSignedMax();
221 if (SignedMax.isStrictlyPositive())
222 Result = SubsetIntersect(
224 ConstantRange(APInt::getSignedMinValue(BitWidth),
225 APInt::getSignedMinValue(BitWidth) - SignedMax));
226 if (SignedMin.isNegative())
227 Result = SubsetIntersect(
229 ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
230 APInt::getSignedMinValue(BitWidth)));
234 case Instruction::Sub:
235 if (auto *C = Other.getSingleElement())
236 if (C->isNullValue())
237 // Full set: nothing signed / unsigned wraps when subtracting 0.
238 return ConstantRange(BitWidth);
239 if (NoWrapKind & OBO::NoUnsignedWrap)
241 SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(),
242 APInt::getMinValue(BitWidth)));
243 if (NoWrapKind & OBO::NoSignedWrap) {
244 const APInt &SignedMin = Other.getSignedMin();
245 const APInt &SignedMax = Other.getSignedMax();
246 if (SignedMax.isStrictlyPositive())
247 Result = SubsetIntersect(
249 ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax,
250 APInt::getSignedMinValue(BitWidth)));
251 if (SignedMin.isNegative())
252 Result = SubsetIntersect(
254 ConstantRange(APInt::getSignedMinValue(BitWidth),
255 APInt::getSignedMinValue(BitWidth) + SignedMin));
261 bool ConstantRange::isFullSet() const {
262 return Lower == Upper && Lower.isMaxValue();
265 bool ConstantRange::isEmptySet() const {
266 return Lower == Upper && Lower.isMinValue();
269 bool ConstantRange::isWrappedSet() const {
270 return Lower.ugt(Upper);
273 bool ConstantRange::isSignWrappedSet() const {
274 return contains(APInt::getSignedMaxValue(getBitWidth())) &&
275 contains(APInt::getSignedMinValue(getBitWidth()));
278 APInt ConstantRange::getSetSize() const {
280 return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
282 // This is also correct for wrapped sets.
283 return (Upper - Lower).zext(getBitWidth()+1);
287 ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
288 assert(getBitWidth() == Other.getBitWidth());
291 if (Other.isFullSet())
293 return (Upper - Lower).ult(Other.Upper - Other.Lower);
297 ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
298 assert(MaxSize && "MaxSize can't be 0.");
299 // If this a full set, we need special handling to avoid needing an extra bit
300 // to represent the size.
302 return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
304 return (Upper - Lower).ugt(MaxSize);
307 APInt ConstantRange::getUnsignedMax() const {
308 if (isFullSet() || isWrappedSet())
309 return APInt::getMaxValue(getBitWidth());
310 return getUpper() - 1;
313 APInt ConstantRange::getUnsignedMin() const {
314 if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
315 return APInt::getMinValue(getBitWidth());
319 APInt ConstantRange::getSignedMax() const {
320 if (isFullSet() || Lower.sgt(Upper))
321 return APInt::getSignedMaxValue(getBitWidth());
322 return getUpper() - 1;
325 APInt ConstantRange::getSignedMin() const {
326 if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
327 return APInt::getSignedMinValue(getBitWidth());
331 bool ConstantRange::contains(const APInt &V) const {
336 return Lower.ule(V) && V.ult(Upper);
337 return Lower.ule(V) || V.ult(Upper);
340 bool ConstantRange::contains(const ConstantRange &Other) const {
341 if (isFullSet() || Other.isEmptySet()) return true;
342 if (isEmptySet() || Other.isFullSet()) return false;
344 if (!isWrappedSet()) {
345 if (Other.isWrappedSet())
348 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
351 if (!Other.isWrappedSet())
352 return Other.getUpper().ule(Upper) ||
353 Lower.ule(Other.getLower());
355 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
358 ConstantRange ConstantRange::subtract(const APInt &Val) const {
359 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
360 // If the set is empty or full, don't modify the endpoints.
363 return ConstantRange(Lower - Val, Upper - Val);
366 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
367 return intersectWith(CR.inverse());
370 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
371 assert(getBitWidth() == CR.getBitWidth() &&
372 "ConstantRange types don't agree!");
374 // Handle common cases.
375 if ( isEmptySet() || CR.isFullSet()) return *this;
376 if (CR.isEmptySet() || isFullSet()) return CR;
378 if (!isWrappedSet() && CR.isWrappedSet())
379 return CR.intersectWith(*this);
381 if (!isWrappedSet() && !CR.isWrappedSet()) {
382 if (Lower.ult(CR.Lower)) {
383 if (Upper.ule(CR.Lower))
384 return ConstantRange(getBitWidth(), false);
386 if (Upper.ult(CR.Upper))
387 return ConstantRange(CR.Lower, Upper);
391 if (Upper.ult(CR.Upper))
394 if (Lower.ult(CR.Upper))
395 return ConstantRange(Lower, CR.Upper);
397 return ConstantRange(getBitWidth(), false);
400 if (isWrappedSet() && !CR.isWrappedSet()) {
401 if (CR.Lower.ult(Upper)) {
402 if (CR.Upper.ult(Upper))
405 if (CR.Upper.ule(Lower))
406 return ConstantRange(CR.Lower, Upper);
408 if (isSizeStrictlySmallerThan(CR))
412 if (CR.Lower.ult(Lower)) {
413 if (CR.Upper.ule(Lower))
414 return ConstantRange(getBitWidth(), false);
416 return ConstantRange(Lower, CR.Upper);
421 if (CR.Upper.ult(Upper)) {
422 if (CR.Lower.ult(Upper)) {
423 if (isSizeStrictlySmallerThan(CR))
428 if (CR.Lower.ult(Lower))
429 return ConstantRange(Lower, CR.Upper);
433 if (CR.Upper.ule(Lower)) {
434 if (CR.Lower.ult(Lower))
437 return ConstantRange(CR.Lower, Upper);
439 if (isSizeStrictlySmallerThan(CR))
444 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
445 assert(getBitWidth() == CR.getBitWidth() &&
446 "ConstantRange types don't agree!");
448 if ( isFullSet() || CR.isEmptySet()) return *this;
449 if (CR.isFullSet() || isEmptySet()) return CR;
451 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
453 if (!isWrappedSet() && !CR.isWrappedSet()) {
454 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
455 // If the two ranges are disjoint, find the smaller gap and bridge it.
456 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
458 return ConstantRange(Lower, CR.Upper);
459 return ConstantRange(CR.Lower, Upper);
462 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
463 APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
465 if (L.isNullValue() && U.isNullValue())
466 return ConstantRange(getBitWidth());
468 return ConstantRange(std::move(L), std::move(U));
471 if (!CR.isWrappedSet()) {
472 // ------U L----- and ------U L----- : this
474 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
477 // ------U L----- : this
479 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
480 return ConstantRange(getBitWidth());
482 // ----U L---- : this
485 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
486 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
488 return ConstantRange(Lower, CR.Upper);
489 return ConstantRange(CR.Lower, Upper);
492 // ----U L----- : this
494 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
495 return ConstantRange(CR.Lower, Upper);
497 // ------U L---- : this
499 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
500 "ConstantRange::unionWith missed a case with one range wrapped");
501 return ConstantRange(Lower, CR.Upper);
504 // ------U L---- and ------U L---- : this
505 // -U L----------- and ------------U L : CR
506 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
507 return ConstantRange(getBitWidth());
509 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
510 APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
512 return ConstantRange(std::move(L), std::move(U));
515 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
516 uint32_t ResultBitWidth) const {
519 llvm_unreachable("unsupported cast type");
520 case Instruction::Trunc:
521 return truncate(ResultBitWidth);
522 case Instruction::SExt:
523 return signExtend(ResultBitWidth);
524 case Instruction::ZExt:
525 return zeroExtend(ResultBitWidth);
526 case Instruction::BitCast:
528 case Instruction::FPToUI:
529 case Instruction::FPToSI:
530 if (getBitWidth() == ResultBitWidth)
533 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
534 case Instruction::UIToFP: {
535 // TODO: use input range if available
536 auto BW = getBitWidth();
537 APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
538 APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
539 return ConstantRange(std::move(Min), std::move(Max));
541 case Instruction::SIToFP: {
542 // TODO: use input range if available
543 auto BW = getBitWidth();
544 APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
545 APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
546 return ConstantRange(std::move(SMin), std::move(SMax));
548 case Instruction::FPTrunc:
549 case Instruction::FPExt:
550 case Instruction::IntToPtr:
551 case Instruction::PtrToInt:
552 case Instruction::AddrSpaceCast:
553 // Conservatively return full set.
554 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
558 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
559 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
561 unsigned SrcTySize = getBitWidth();
562 assert(SrcTySize < DstTySize && "Not a value extension");
563 if (isFullSet() || isWrappedSet()) {
564 // Change into [0, 1 << src bit width)
565 APInt LowerExt(DstTySize, 0);
566 if (!Upper) // special case: [X, 0) -- not really wrapping around
567 LowerExt = Lower.zext(DstTySize);
568 return ConstantRange(std::move(LowerExt),
569 APInt::getOneBitSet(DstTySize, SrcTySize));
572 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
575 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
576 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
578 unsigned SrcTySize = getBitWidth();
579 assert(SrcTySize < DstTySize && "Not a value extension");
581 // special case: [X, INT_MIN) -- not really wrapping around
582 if (Upper.isMinSignedValue())
583 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
585 if (isFullSet() || isSignWrappedSet()) {
586 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
587 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
590 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
593 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
594 assert(getBitWidth() > DstTySize && "Not a value truncation");
596 return ConstantRange(DstTySize, /*isFullSet=*/false);
598 return ConstantRange(DstTySize, /*isFullSet=*/true);
600 APInt LowerDiv(Lower), UpperDiv(Upper);
601 ConstantRange Union(DstTySize, /*isFullSet=*/false);
603 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
604 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
605 // then we do the union with [MaxValue, Upper)
606 if (isWrappedSet()) {
607 // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
609 if (Upper.getActiveBits() > DstTySize ||
610 Upper.countTrailingOnes() == DstTySize)
611 return ConstantRange(DstTySize, /*isFullSet=*/true);
613 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
614 UpperDiv.setAllBits();
616 // Union covers the MaxValue case, so return if the remaining range is just
618 if (LowerDiv == UpperDiv)
622 // Chop off the most significant bits that are past the destination bitwidth.
623 if (LowerDiv.getActiveBits() > DstTySize) {
624 // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
625 APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
630 unsigned UpperDivWidth = UpperDiv.getActiveBits();
631 if (UpperDivWidth <= DstTySize)
632 return ConstantRange(LowerDiv.trunc(DstTySize),
633 UpperDiv.trunc(DstTySize)).unionWith(Union);
635 // The truncated value wraps around. Check if we can do better than fullset.
636 if (UpperDivWidth == DstTySize + 1) {
637 // Clear the MSB so that UpperDiv wraps around.
638 UpperDiv.clearBit(DstTySize);
639 if (UpperDiv.ult(LowerDiv))
640 return ConstantRange(LowerDiv.trunc(DstTySize),
641 UpperDiv.trunc(DstTySize)).unionWith(Union);
644 return ConstantRange(DstTySize, /*isFullSet=*/true);
647 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
648 unsigned SrcTySize = getBitWidth();
649 if (SrcTySize > DstTySize)
650 return truncate(DstTySize);
651 if (SrcTySize < DstTySize)
652 return zeroExtend(DstTySize);
656 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
657 unsigned SrcTySize = getBitWidth();
658 if (SrcTySize > DstTySize)
659 return truncate(DstTySize);
660 if (SrcTySize < DstTySize)
661 return signExtend(DstTySize);
665 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
666 const ConstantRange &Other) const {
667 assert(BinOp >= Instruction::BinaryOpsBegin &&
668 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
671 case Instruction::Add:
673 case Instruction::Sub:
675 case Instruction::Mul:
676 return multiply(Other);
677 case Instruction::UDiv:
679 case Instruction::Shl:
681 case Instruction::LShr:
683 case Instruction::AShr:
685 case Instruction::And:
686 return binaryAnd(Other);
687 case Instruction::Or:
688 return binaryOr(Other);
689 // Note: floating point operations applied to abstract ranges are just
690 // ideal integer operations with a lossy representation
691 case Instruction::FAdd:
693 case Instruction::FSub:
695 case Instruction::FMul:
696 return multiply(Other);
698 // Conservatively return full set.
699 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
704 ConstantRange::add(const ConstantRange &Other) const {
705 if (isEmptySet() || Other.isEmptySet())
706 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
707 if (isFullSet() || Other.isFullSet())
708 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
710 APInt NewLower = getLower() + Other.getLower();
711 APInt NewUpper = getUpper() + Other.getUpper() - 1;
712 if (NewLower == NewUpper)
713 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
715 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
716 if (X.isSizeStrictlySmallerThan(*this) ||
717 X.isSizeStrictlySmallerThan(Other))
718 // We've wrapped, therefore, full set.
719 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
723 ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
724 // Calculate the subset of this range such that "X + Other" is
725 // guaranteed not to wrap (overflow) for all X in this subset.
726 // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
727 // passing a single element range.
728 auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
729 ConstantRange(Other),
730 OverflowingBinaryOperator::NoSignedWrap);
731 auto NSWConstrainedRange = intersectWith(NSWRange);
733 return NSWConstrainedRange.add(ConstantRange(Other));
737 ConstantRange::sub(const ConstantRange &Other) const {
738 if (isEmptySet() || Other.isEmptySet())
739 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
740 if (isFullSet() || Other.isFullSet())
741 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
743 APInt NewLower = getLower() - Other.getUpper() + 1;
744 APInt NewUpper = getUpper() - Other.getLower();
745 if (NewLower == NewUpper)
746 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
748 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
749 if (X.isSizeStrictlySmallerThan(*this) ||
750 X.isSizeStrictlySmallerThan(Other))
751 // We've wrapped, therefore, full set.
752 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
757 ConstantRange::multiply(const ConstantRange &Other) const {
758 // TODO: If either operand is a single element and the multiply is known to
759 // be non-wrapping, round the result min and max value to the appropriate
760 // multiple of that element. If wrapping is possible, at least adjust the
761 // range according to the greatest power-of-two factor of the single element.
763 if (isEmptySet() || Other.isEmptySet())
764 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
766 // Multiplication is signedness-independent. However different ranges can be
767 // obtained depending on how the input ranges are treated. These different
768 // ranges are all conservatively correct, but one might be better than the
769 // other. We calculate two ranges; one treating the inputs as unsigned
770 // and the other signed, then return the smallest of these ranges.
772 // Unsigned range first.
773 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
774 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
775 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
776 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
778 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
779 this_max * Other_max + 1);
780 ConstantRange UR = Result_zext.truncate(getBitWidth());
782 // If the unsigned range doesn't wrap, and isn't negative then it's a range
783 // from one positive number to another which is as good as we can generate.
784 // In this case, skip the extra work of generating signed ranges which aren't
785 // going to be better than this range.
786 if (!UR.isWrappedSet() &&
787 (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
790 // Now the signed range. Because we could be dealing with negative numbers
791 // here, the lower bound is the smallest of the cartesian product of the
792 // lower and upper ranges; for example:
793 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
794 // Similarly for the upper bound, swapping min for max.
796 this_min = getSignedMin().sext(getBitWidth() * 2);
797 this_max = getSignedMax().sext(getBitWidth() * 2);
798 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
799 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
801 auto L = {this_min * Other_min, this_min * Other_max,
802 this_max * Other_min, this_max * Other_max};
803 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
804 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
805 ConstantRange SR = Result_sext.truncate(getBitWidth());
807 return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
811 ConstantRange::smax(const ConstantRange &Other) const {
812 // X smax Y is: range(smax(X_smin, Y_smin),
813 // smax(X_smax, Y_smax))
814 if (isEmptySet() || Other.isEmptySet())
815 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
816 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
817 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
819 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
820 return ConstantRange(std::move(NewL), std::move(NewU));
824 ConstantRange::umax(const ConstantRange &Other) const {
825 // X umax Y is: range(umax(X_umin, Y_umin),
826 // umax(X_umax, Y_umax))
827 if (isEmptySet() || Other.isEmptySet())
828 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
829 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
830 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
832 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
833 return ConstantRange(std::move(NewL), std::move(NewU));
837 ConstantRange::smin(const ConstantRange &Other) const {
838 // X smin Y is: range(smin(X_smin, Y_smin),
839 // smin(X_smax, Y_smax))
840 if (isEmptySet() || Other.isEmptySet())
841 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
842 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
843 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
845 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
846 return ConstantRange(std::move(NewL), std::move(NewU));
850 ConstantRange::umin(const ConstantRange &Other) const {
851 // X umin Y is: range(umin(X_umin, Y_umin),
852 // umin(X_umax, Y_umax))
853 if (isEmptySet() || Other.isEmptySet())
854 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
855 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
856 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
858 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
859 return ConstantRange(std::move(NewL), std::move(NewU));
863 ConstantRange::udiv(const ConstantRange &RHS) const {
864 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
865 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
867 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
869 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
871 APInt RHS_umin = RHS.getUnsignedMin();
872 if (RHS_umin.isNullValue()) {
873 // We want the lowest value in RHS excluding zero. Usually that would be 1
874 // except for a range in the form of [X, 1) in which case it would be X.
875 if (RHS.getUpper() == 1)
876 RHS_umin = RHS.getLower();
881 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
883 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
886 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
888 return ConstantRange(std::move(Lower), std::move(Upper));
892 ConstantRange::binaryAnd(const ConstantRange &Other) const {
893 if (isEmptySet() || Other.isEmptySet())
894 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
896 // TODO: replace this with something less conservative
898 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
899 if (umin.isAllOnesValue())
900 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
901 return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
905 ConstantRange::binaryOr(const ConstantRange &Other) const {
906 if (isEmptySet() || Other.isEmptySet())
907 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
909 // TODO: replace this with something less conservative
911 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
912 if (umax.isNullValue())
913 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
914 return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
918 ConstantRange::shl(const ConstantRange &Other) const {
919 if (isEmptySet() || Other.isEmptySet())
920 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
922 APInt max = getUnsignedMax();
923 APInt Other_umax = Other.getUnsignedMax();
926 if (Other_umax.uge(max.countLeadingZeros()))
927 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
929 // FIXME: implement the other tricky cases
931 APInt min = getUnsignedMin();
932 min <<= Other.getUnsignedMin();
935 return ConstantRange(std::move(min), std::move(max) + 1);
939 ConstantRange::lshr(const ConstantRange &Other) const {
940 if (isEmptySet() || Other.isEmptySet())
941 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
943 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
944 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
946 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
948 return ConstantRange(std::move(min), std::move(max));
952 ConstantRange::ashr(const ConstantRange &Other) const {
953 if (isEmptySet() || Other.isEmptySet())
954 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
956 // May straddle zero, so handle both positive and negative cases.
957 // 'PosMax' is the upper bound of the result of the ashr
958 // operation, when Upper of the LHS of ashr is a non-negative.
959 // number. Since ashr of a non-negative number will result in a
960 // smaller number, the Upper value of LHS is shifted right with
961 // the minimum value of 'Other' instead of the maximum value.
962 APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
964 // 'PosMin' is the lower bound of the result of the ashr
965 // operation, when Lower of the LHS is a non-negative number.
966 // Since ashr of a non-negative number will result in a smaller
967 // number, the Lower value of LHS is shifted right with the
968 // maximum value of 'Other'.
969 APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
971 // 'NegMax' is the upper bound of the result of the ashr
972 // operation, when Upper of the LHS of ashr is a negative number.
973 // Since 'ashr' of a negative number will result in a bigger
974 // number, the Upper value of LHS is shifted right with the
975 // maximum value of 'Other'.
976 APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
978 // 'NegMin' is the lower bound of the result of the ashr
979 // operation, when Lower of the LHS of ashr is a negative number.
980 // Since 'ashr' of a negative number will result in a bigger
981 // number, the Lower value of LHS is shifted right with the
982 // minimum value of 'Other'.
983 APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
986 if (getSignedMin().isNonNegative()) {
987 // Upper and Lower of LHS are non-negative.
990 } else if (getSignedMax().isNegative()) {
991 // Upper and Lower of LHS are negative.
995 // Upper is non-negative and Lower is negative.
1000 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1002 return ConstantRange(std::move(min), std::move(max));
1005 ConstantRange ConstantRange::inverse() const {
1007 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
1009 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1010 return ConstantRange(Upper, Lower);
1013 void ConstantRange::print(raw_ostream &OS) const {
1016 else if (isEmptySet())
1019 OS << "[" << Lower << "," << Upper << ")";
1022 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1023 LLVM_DUMP_METHOD void ConstantRange::dump() const {
1028 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
1029 const unsigned NumRanges = Ranges.getNumOperands() / 2;
1030 assert(NumRanges >= 1 && "Must have at least one range!");
1031 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1033 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1034 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1036 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1038 for (unsigned i = 1; i < NumRanges; ++i) {
1039 auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1040 auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1042 // Note: unionWith will potentially create a range that contains values not
1043 // contained in any of the original N ranges.
1044 CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));