[InstCombine] Signed saturation tests. NFC
[llvm-complete.git] / lib / IR / ConstantRange.cpp
blob642bf0f39342b5ada4155111b4595a3a6e1c7587
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):
16 // [F, F) = {} = Empty set
17 // [T, F) = {T}
18 // [F, T) = {F}
19 // [T, T) = {F, T} = Full set
21 //===----------------------------------------------------------------------===//
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"
33 #include "llvm/Support/ErrorHandling.h"
34 #include "llvm/Support/KnownBits.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include <algorithm>
37 #include <cassert>
38 #include <cstdint>
40 using namespace llvm;
42 ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
43 : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
44 Upper(Lower) {}
46 ConstantRange::ConstantRange(APInt V)
47 : Lower(std::move(V)), Upper(Lower + 1) {}
49 ConstantRange::ConstantRange(APInt L, APInt U)
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!");
57 ConstantRange ConstantRange::fromKnownBits(const KnownBits &Known,
58 bool IsSigned) {
59 assert(!Known.hasConflict() && "Expected valid KnownBits");
61 if (Known.isUnknown())
62 return getFull(Known.getBitWidth());
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);
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);
77 ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
78 const ConstantRange &CR) {
79 if (CR.isEmptySet())
80 return CR;
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));
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));
104 case CmpInst::ICMP_ULE:
105 return getNonEmpty(APInt::getMinValue(W), CR.getUnsignedMax() + 1);
106 case CmpInst::ICMP_SLE:
107 return getNonEmpty(APInt::getSignedMinValue(W), CR.getSignedMax() + 1);
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));
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));
120 case CmpInst::ICMP_UGE:
121 return getNonEmpty(CR.getUnsignedMin(), APInt::getNullValue(W));
122 case CmpInst::ICMP_SGE:
123 return getNonEmpty(CR.getSignedMin(), APInt::getSignedMinValue(W));
127 ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
128 const ConstantRange &CR) {
129 // Follows from De-Morgan's laws:
131 // ~(~A union ~B) == A intersect B.
133 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
134 .inverse();
137 ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
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).
145 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
146 return makeAllowedICmpRegion(Pred, C);
149 bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
150 APInt &RHS) const {
151 bool Success = false;
153 if (isFullSet() || isEmptySet()) {
154 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
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 =
167 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
168 RHS = getUpper();
169 Success = true;
170 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
171 Pred =
172 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
173 RHS = getLower();
174 Success = true;
177 assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
178 "Bad result!");
180 return Success;
183 /// Exact mul nuw region for single element RHS.
184 static ConstantRange makeExactMulNUWRegion(const APInt &V) {
185 unsigned BitWidth = V.getBitWidth();
186 if (V == 0)
187 return ConstantRange::getFull(V.getBitWidth());
189 return ConstantRange::getNonEmpty(
190 APIntOps::RoundingUDiv(APInt::getMinValue(BitWidth), V,
191 APInt::Rounding::UP),
192 APIntOps::RoundingUDiv(APInt::getMaxValue(BitWidth), V,
193 APInt::Rounding::DOWN) + 1);
196 /// Exact mul nsw region for single element RHS.
197 static ConstantRange makeExactMulNSWRegion(const APInt &V) {
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);
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);
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);
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);
224 ConstantRange
225 ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
226 const ConstantRange &Other,
227 unsigned NoWrapKind) {
228 using OBO = OverflowingBinaryOperator;
230 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
232 assert((NoWrapKind == OBO::NoSignedWrap ||
233 NoWrapKind == OBO::NoUnsignedWrap) &&
234 "NoWrapKind invalid!");
236 bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
237 unsigned BitWidth = Other.getBitWidth();
239 switch (BinOp) {
240 default:
241 llvm_unreachable("Unsupported binary op");
243 case Instruction::Add: {
244 if (Unsigned)
245 return getNonEmpty(APInt::getNullValue(BitWidth),
246 -Other.getUnsignedMax());
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);
255 case Instruction::Sub: {
256 if (Unsigned)
257 return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth));
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);
266 case Instruction::Mul:
267 if (Unsigned)
268 return makeExactMulNUWRegion(Other.getUnsignedMax());
270 return makeExactMulNSWRegion(Other.getSignedMin())
271 .intersectWith(makeExactMulNSWRegion(Other.getSignedMax()));
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);
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);
296 ConstantRange ConstantRange::makeExactNoWrapRegion(Instruction::BinaryOps BinOp,
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);
304 bool ConstantRange::isFullSet() const {
305 return Lower == Upper && Lower.isMaxValue();
308 bool ConstantRange::isEmptySet() const {
309 return Lower == Upper && Lower.isMinValue();
312 bool ConstantRange::isWrappedSet() const {
313 return Lower.ugt(Upper) && !Upper.isNullValue();
316 bool ConstantRange::isUpperWrapped() const {
317 return Lower.ugt(Upper);
320 bool ConstantRange::isSignWrappedSet() const {
321 return Lower.sgt(Upper) && !Upper.isMinSignedValue();
324 bool ConstantRange::isUpperSignWrapped() const {
325 return Lower.sgt(Upper);
328 bool
329 ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
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);
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);
346 return (Upper - Lower).ugt(MaxSize);
349 bool ConstantRange::isAllNegative() const {
350 // Empty set is all negative, full set is not.
351 if (isEmptySet())
352 return true;
353 if (isFullSet())
354 return false;
356 return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
359 bool ConstantRange::isAllNonNegative() const {
360 // Empty and full set are automatically treated correctly.
361 return !isSignWrappedSet() && Lower.isNonNegative();
364 APInt ConstantRange::getUnsignedMax() const {
365 if (isFullSet() || isUpperWrapped())
366 return APInt::getMaxValue(getBitWidth());
367 return getUpper() - 1;
370 APInt ConstantRange::getUnsignedMin() const {
371 if (isFullSet() || isWrappedSet())
372 return APInt::getMinValue(getBitWidth());
373 return getLower();
376 APInt ConstantRange::getSignedMax() const {
377 if (isFullSet() || isUpperSignWrapped())
378 return APInt::getSignedMaxValue(getBitWidth());
379 return getUpper() - 1;
382 APInt ConstantRange::getSignedMin() const {
383 if (isFullSet() || isSignWrappedSet())
384 return APInt::getSignedMinValue(getBitWidth());
385 return getLower();
388 bool ConstantRange::contains(const APInt &V) const {
389 if (Lower == Upper)
390 return isFullSet();
392 if (!isUpperWrapped())
393 return Lower.ule(V) && V.ult(Upper);
394 return Lower.ule(V) || V.ult(Upper);
397 bool ConstantRange::contains(const ConstantRange &Other) const {
398 if (isFullSet() || Other.isEmptySet()) return true;
399 if (isEmptySet() || Other.isFullSet()) return false;
401 if (!isUpperWrapped()) {
402 if (Other.isUpperWrapped())
403 return false;
405 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
408 if (!Other.isUpperWrapped())
409 return Other.getUpper().ule(Upper) ||
410 Lower.ule(Other.getLower());
412 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
415 ConstantRange ConstantRange::subtract(const APInt &Val) const {
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);
423 ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
424 return intersectWith(CR.inverse());
427 static ConstantRange getPreferredRange(
428 const ConstantRange &CR1, const ConstantRange &CR2,
429 ConstantRange::PreferredRangeType Type) {
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;
442 if (CR1.isSizeStrictlySmallerThan(CR2))
443 return CR1;
444 return CR2;
447 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR,
448 PreferredRangeType Type) const {
449 assert(getBitWidth() == CR.getBitWidth() &&
450 "ConstantRange types don't agree!");
452 // Handle common cases.
453 if ( isEmptySet() || CR.isFullSet()) return *this;
454 if (CR.isEmptySet() || isFullSet()) return CR;
456 if (!isUpperWrapped() && CR.isUpperWrapped())
457 return CR.intersectWith(*this, Type);
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();
466 // L---U : this
467 // L---U : CR
468 if (Upper.ult(CR.Upper))
469 return ConstantRange(CR.Lower, Upper);
471 // L-------U : this
472 // L---U : CR
473 return CR;
475 // L---U : this
476 // L-------U : CR
477 if (Upper.ult(CR.Upper))
478 return *this;
480 // L-----U : this
481 // L-----U : CR
482 if (Lower.ult(CR.Upper))
483 return ConstantRange(Lower, CR.Upper);
485 // L---U : this
486 // L---U : CR
487 return getEmpty();
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;
497 // ------U L--- : this
498 // L------U : CR
499 if (CR.Upper.ule(Lower))
500 return ConstantRange(CR.Lower, Upper);
502 // ------U L--- : this
503 // L----------U : CR
504 return getPreferredRange(*this, CR, Type);
506 if (CR.Lower.ult(Lower)) {
507 // --U L---- : this
508 // L--U : CR
509 if (CR.Upper.ule(Lower))
510 return getEmpty();
512 // --U L---- : this
513 // L------U : CR
514 return ConstantRange(Lower, CR.Upper);
517 // --U L------ : this
518 // L--U : CR
519 return CR;
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);
528 // ----U L-- : this
529 // --U L---- : CR
530 if (CR.Lower.ult(Lower))
531 return ConstantRange(Lower, CR.Upper);
533 // ----U L---- : this
534 // --U L-- : CR
535 return CR;
537 if (CR.Upper.ule(Lower)) {
538 // --U L-- : this
539 // ----U L---- : CR
540 if (CR.Lower.ult(Lower))
541 return *this;
543 // --U L---- : this
544 // ----U L-- : CR
545 return ConstantRange(CR.Lower, Upper);
548 // --U L------ : this
549 // ------U L-- : CR
550 return getPreferredRange(*this, CR, Type);
553 ConstantRange ConstantRange::unionWith(const ConstantRange &CR,
554 PreferredRangeType Type) const {
555 assert(getBitWidth() == CR.getBitWidth() &&
556 "ConstantRange types don't agree!");
558 if ( isFullSet() || CR.isEmptySet()) return *this;
559 if (CR.isFullSet() || isEmptySet()) return CR;
561 if (!isUpperWrapped() && CR.isUpperWrapped())
562 return CR.unionWith(*this, Type);
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);
574 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
575 APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
577 if (L.isNullValue() && U.isNullValue())
578 return getFull();
580 return ConstantRange(std::move(L), std::move(U));
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;
589 // ------U L----- : this
590 // L---------U : CR
591 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
592 return getFull();
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);
603 // ----U L----- : this
604 // L----U : CR
605 if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))
606 return ConstantRange(CR.Lower, Upper);
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);
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();
620 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
621 APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
623 return ConstantRange(std::move(L), std::move(U));
626 ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
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));
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));
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();
669 ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
670 if (isEmptySet()) return getEmpty(DstTySize);
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));
683 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
686 ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
687 if (isEmptySet()) return getEmpty(DstTySize);
689 unsigned SrcTySize = getBitWidth();
690 assert(SrcTySize < DstTySize && "Not a value extension");
692 // special case: [X, INT_MIN) -- not really wrapping around
693 if (Upper.isMinSignedValue())
694 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
696 if (isFullSet() || isSignWrappedSet()) {
697 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
698 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
701 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
704 ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
705 assert(getBitWidth() > DstTySize && "Not a value truncation");
706 if (isEmptySet())
707 return getEmpty(DstTySize);
708 if (isFullSet())
709 return getFull(DstTySize);
711 APInt LowerDiv(Lower), UpperDiv(Upper);
712 ConstantRange Union(DstTySize, /*isFullSet=*/false);
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);
724 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
725 UpperDiv.setAllBits();
727 // Union covers the MaxValue case, so return if the remaining range is just
728 // MaxValue(DstTy).
729 if (LowerDiv == UpperDiv)
730 return Union;
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;
741 unsigned UpperDivWidth = UpperDiv.getActiveBits();
742 if (UpperDivWidth <= DstTySize)
743 return ConstantRange(LowerDiv.trunc(DstTySize),
744 UpperDiv.trunc(DstTySize)).unionWith(Union);
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);
755 return getFull(DstTySize);
758 ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
759 unsigned SrcTySize = getBitWidth();
760 if (SrcTySize > DstTySize)
761 return truncate(DstTySize);
762 if (SrcTySize < DstTySize)
763 return zeroExtend(DstTySize);
764 return *this;
767 ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
768 unsigned SrcTySize = getBitWidth();
769 if (SrcTySize > DstTySize)
770 return truncate(DstTySize);
771 if (SrcTySize < DstTySize)
772 return signExtend(DstTySize);
773 return *this;
776 ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
777 const ConstantRange &Other) const {
778 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
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();
819 ConstantRange
820 ConstantRange::add(const ConstantRange &Other) const {
821 if (isEmptySet() || Other.isEmptySet())
822 return getEmpty();
823 if (isFullSet() || Other.isFullSet())
824 return getFull();
826 APInt NewLower = getLower() + Other.getLower();
827 APInt NewUpper = getUpper() + Other.getUpper() - 1;
828 if (NewLower == NewUpper)
829 return getFull();
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;
839 ConstantRange ConstantRange::addWithNoWrap(const ConstantRange &Other,
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();
849 using OBO = OverflowingBinaryOperator;
850 ConstantRange Result = add(Other);
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);
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();
872 if (LMax.isNegative()) {
873 bool Overflow;
874 APInt Temp = LMax.sadd_ov(RMax, Overflow);
875 if (Overflow)
876 return getEmpty();
878 APInt NewMin = LMin.sadd_sat(RMin);
879 APInt NewMax = LMax.sadd_sat(RMax);
880 return getNonEmpty(std::move(NewMin), std::move(NewMax) + 1);
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;
890 ConstantRange
891 ConstantRange::sub(const ConstantRange &Other) const {
892 if (isEmptySet() || Other.isEmptySet())
893 return getEmpty();
894 if (isFullSet() || Other.isFullSet())
895 return getFull();
897 APInt NewLower = getLower() - Other.getUpper() + 1;
898 APInt NewUpper = getUpper() - Other.getLower();
899 if (NewLower == NewUpper)
900 return getFull();
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;
910 ConstantRange
911 ConstantRange::multiply(const ConstantRange &Other) const {
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.
917 if (isEmptySet() || Other.isEmptySet())
918 return getEmpty();
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.
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);
932 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
933 this_max * Other_max + 1);
934 ConstantRange UR = Result_zext.truncate(getBitWidth());
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;
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.
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);
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());
961 return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
964 ConstantRange
965 ConstantRange::smax(const ConstantRange &Other) const {
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));
975 ConstantRange
976 ConstantRange::umax(const ConstantRange &Other) const {
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();
981 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
982 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
983 return getNonEmpty(std::move(NewL), std::move(NewU));
986 ConstantRange
987 ConstantRange::smin(const ConstantRange &Other) const {
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));
997 ConstantRange
998 ConstantRange::umin(const ConstantRange &Other) const {
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();
1003 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
1004 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1005 return getNonEmpty(std::move(NewL), std::move(NewU));
1008 ConstantRange
1009 ConstantRange::udiv(const ConstantRange &RHS) const {
1010 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
1011 return getEmpty();
1013 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
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;
1025 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
1026 return getNonEmpty(std::move(Lower), std::move(Upper));
1029 ConstantRange ConstantRange::sdiv(const ConstantRange &RHS) const {
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.
1033 APInt Zero = APInt::getNullValue(getBitWidth());
1034 APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
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);
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);
1048 if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1049 // neg / neg = pos.
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;
1068 PosRes = PosRes.unionWith(
1069 ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
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;
1083 PosRes = PosRes.unionWith(
1084 ConstantRange(std::move(Lo),
1085 AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
1087 } else {
1088 PosRes = PosRes.unionWith(
1089 ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
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);
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));
1105 // Prefer a non-wrapping signed range here.
1106 ConstantRange Res = NegRes.unionWith(PosRes, PreferredRangeType::Signed);
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;
1114 ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
1115 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
1116 return getEmpty();
1118 // L % R for L < R is L.
1119 if (getUnsignedMax().ult(RHS.getUnsignedMin()))
1120 return *this;
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));
1127 ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {
1128 if (isEmptySet() || RHS.isEmptySet())
1129 return getEmpty();
1131 ConstantRange AbsRHS = RHS.abs();
1132 APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1133 APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1135 // Modulus by zero is UB.
1136 if (MaxAbsRHS.isNullValue())
1137 return getEmpty();
1139 if (MinAbsRHS.isNullValue())
1140 ++MinAbsRHS;
1142 APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1144 if (MinLHS.isNonNegative()) {
1145 // L % R for L < R is L.
1146 if (MaxLHS.ult(MinAbsRHS))
1147 return *this;
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));
1154 // Same basic logic as above, but the result is negative.
1155 if (MaxLHS.isNegative()) {
1156 if (MinLHS.ugt(-MinAbsRHS))
1157 return *this;
1159 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1160 return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
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));
1169 ConstantRange
1170 ConstantRange::binaryAnd(const ConstantRange &Other) const {
1171 if (isEmptySet() || Other.isEmptySet())
1172 return getEmpty();
1174 // TODO: replace this with something less conservative
1176 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
1177 return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
1180 ConstantRange
1181 ConstantRange::binaryOr(const ConstantRange &Other) const {
1182 if (isEmptySet() || Other.isEmptySet())
1183 return getEmpty();
1185 // TODO: replace this with something less conservative
1187 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
1188 return getNonEmpty(std::move(umax), APInt::getNullValue(getBitWidth()));
1191 ConstantRange
1192 ConstantRange::shl(const ConstantRange &Other) const {
1193 if (isEmptySet() || Other.isEmptySet())
1194 return getEmpty();
1196 APInt max = getUnsignedMax();
1197 APInt Other_umax = Other.getUnsignedMax();
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();
1207 // FIXME: implement the other tricky cases
1209 APInt min = getUnsignedMin();
1210 min <<= Other.getUnsignedMin();
1211 max <<= Other_umax;
1213 return ConstantRange(std::move(min), std::move(max) + 1);
1216 ConstantRange
1217 ConstantRange::lshr(const ConstantRange &Other) const {
1218 if (isEmptySet() || Other.isEmptySet())
1219 return getEmpty();
1221 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1222 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1223 return getNonEmpty(std::move(min), std::move(max));
1226 ConstantRange
1227 ConstantRange::ashr(const ConstantRange &Other) const {
1228 if (isEmptySet() || Other.isEmptySet())
1229 return getEmpty();
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;
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());
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;
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());
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;
1274 return getNonEmpty(std::move(min), std::move(max));
1277 ConstantRange ConstantRange::uadd_sat(const ConstantRange &Other) const {
1278 if (isEmptySet() || Other.isEmptySet())
1279 return getEmpty();
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));
1286 ConstantRange ConstantRange::sadd_sat(const ConstantRange &Other) const {
1287 if (isEmptySet() || Other.isEmptySet())
1288 return getEmpty();
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));
1295 ConstantRange ConstantRange::usub_sat(const ConstantRange &Other) const {
1296 if (isEmptySet() || Other.isEmptySet())
1297 return getEmpty();
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));
1304 ConstantRange ConstantRange::ssub_sat(const ConstantRange &Other) const {
1305 if (isEmptySet() || Other.isEmptySet())
1306 return getEmpty();
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));
1313 ConstantRange ConstantRange::inverse() const {
1314 if (isFullSet())
1315 return getEmpty();
1316 if (isEmptySet())
1317 return getFull();
1318 return ConstantRange(Upper, Lower);
1321 ConstantRange ConstantRange::abs() const {
1322 if (isEmptySet())
1323 return getEmpty();
1325 if (isSignWrappedSet()) {
1326 APInt Lo;
1327 // Check whether the range crosses zero.
1328 if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1329 Lo = APInt::getNullValue(getBitWidth());
1330 else
1331 Lo = APIntOps::umin(Lower, -Upper + 1);
1333 // SignedMin is included in the result range.
1334 return ConstantRange(Lo, APInt::getSignedMinValue(getBitWidth()) + 1);
1337 APInt SMin = getSignedMin(), SMax = getSignedMax();
1339 // All non-negative.
1340 if (SMin.isNonNegative())
1341 return *this;
1343 // All negative.
1344 if (SMax.isNegative())
1345 return ConstantRange(-SMax, -SMin + 1);
1347 // Range crosses zero.
1348 return ConstantRange(APInt::getNullValue(getBitWidth()),
1349 APIntOps::umax(-SMin, SMax) + 1);
1352 ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow(
1353 const ConstantRange &Other) const {
1354 if (isEmptySet() || Other.isEmptySet())
1355 return OverflowResult::MayOverflow;
1357 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1358 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1360 // a u+ b overflows high iff a u> ~b.
1361 if (Min.ugt(~OtherMin))
1362 return OverflowResult::AlwaysOverflowsHigh;
1363 if (Max.ugt(~OtherMax))
1364 return OverflowResult::MayOverflow;
1365 return OverflowResult::NeverOverflows;
1368 ConstantRange::OverflowResult ConstantRange::signedAddMayOverflow(
1369 const ConstantRange &Other) const {
1370 if (isEmptySet() || Other.isEmptySet())
1371 return OverflowResult::MayOverflow;
1373 APInt Min = getSignedMin(), Max = getSignedMax();
1374 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1376 APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
1377 APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());
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))
1383 return OverflowResult::AlwaysOverflowsHigh;
1384 if (Max.isNegative() && OtherMax.isNegative() &&
1385 Max.slt(SignedMin - OtherMax))
1386 return OverflowResult::AlwaysOverflowsLow;
1388 if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1389 Max.sgt(SignedMax - OtherMax))
1390 return OverflowResult::MayOverflow;
1391 if (Min.isNegative() && OtherMin.isNegative() &&
1392 Min.slt(SignedMin - OtherMin))
1393 return OverflowResult::MayOverflow;
1395 return OverflowResult::NeverOverflows;
1398 ConstantRange::OverflowResult ConstantRange::unsignedSubMayOverflow(
1399 const ConstantRange &Other) const {
1400 if (isEmptySet() || Other.isEmptySet())
1401 return OverflowResult::MayOverflow;
1403 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1404 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1406 // a u- b overflows low iff a u< b.
1407 if (Max.ult(OtherMin))
1408 return OverflowResult::AlwaysOverflowsLow;
1409 if (Min.ult(OtherMax))
1410 return OverflowResult::MayOverflow;
1411 return OverflowResult::NeverOverflows;
1414 ConstantRange::OverflowResult ConstantRange::signedSubMayOverflow(
1415 const ConstantRange &Other) const {
1416 if (isEmptySet() || Other.isEmptySet())
1417 return OverflowResult::MayOverflow;
1419 APInt Min = getSignedMin(), Max = getSignedMax();
1420 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1422 APInt SignedMin = APInt::getSignedMinValue(getBitWidth());
1423 APInt SignedMax = APInt::getSignedMaxValue(getBitWidth());
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))
1429 return OverflowResult::AlwaysOverflowsHigh;
1430 if (Max.isNegative() && OtherMin.isNonNegative() &&
1431 Max.slt(SignedMin + OtherMin))
1432 return OverflowResult::AlwaysOverflowsLow;
1434 if (Max.isNonNegative() && OtherMin.isNegative() &&
1435 Max.sgt(SignedMax + OtherMin))
1436 return OverflowResult::MayOverflow;
1437 if (Min.isNegative() && OtherMax.isNonNegative() &&
1438 Min.slt(SignedMin + OtherMax))
1439 return OverflowResult::MayOverflow;
1441 return OverflowResult::NeverOverflows;
1444 ConstantRange::OverflowResult ConstantRange::unsignedMulMayOverflow(
1445 const ConstantRange &Other) const {
1446 if (isEmptySet() || Other.isEmptySet())
1447 return OverflowResult::MayOverflow;
1449 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1450 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1451 bool Overflow;
1453 (void) Min.umul_ov(OtherMin, Overflow);
1454 if (Overflow)
1455 return OverflowResult::AlwaysOverflowsHigh;
1457 (void) Max.umul_ov(OtherMax, Overflow);
1458 if (Overflow)
1459 return OverflowResult::MayOverflow;
1461 return OverflowResult::NeverOverflows;
1464 void ConstantRange::print(raw_ostream &OS) const {
1465 if (isFullSet())
1466 OS << "full-set";
1467 else if (isEmptySet())
1468 OS << "empty-set";
1469 else
1470 OS << "[" << Lower << "," << Upper << ")";
1473 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1474 LLVM_DUMP_METHOD void ConstantRange::dump() const {
1475 print(dbgs());
1477 #endif
1479 ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
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");
1484 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1485 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1487 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
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));
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()));
1498 return CR;