LLVM 17.0.0git
ConstantRange.cpp
Go to the documentation of this file.
1//===- ConstantRange.cpp - ConstantRange implementation -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Represent a range of possible values that may occur when the program is run
10// for an integral value. This keeps track of a lower and upper bound for the
11// constant, which MAY wrap around the end of the numeric range. To do this, it
12// keeps track of a [lower, upper) bound, which specifies an interval just like
13// STL iterators. When used with boolean values, the following are important
14// ranges (other integral ranges use min/max values for special range values):
15//
16// [F, F) = {} = Empty set
17// [T, F) = {T}
18// [F, T) = {F}
19// [T, T) = {F, T} = Full set
20//
21//===----------------------------------------------------------------------===//
22
23#include "llvm/ADT/APInt.h"
24#include "llvm/Config/llvm-config.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/InstrTypes.h"
28#include "llvm/IR/Instruction.h"
29#include "llvm/IR/Intrinsics.h"
30#include "llvm/IR/Metadata.h"
31#include "llvm/IR/Operator.h"
33#include "llvm/Support/Debug.h"
37#include <algorithm>
38#include <cassert>
39#include <cstdint>
40#include <optional>
41
42using namespace llvm;
43
45 : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
46 Upper(Lower) {}
47
49 : Lower(std::move(V)), Upper(Lower + 1) {}
50
52 : Lower(std::move(L)), Upper(std::move(U)) {
53 assert(Lower.getBitWidth() == Upper.getBitWidth() &&
54 "ConstantRange with unequal bit widths");
55 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
56 "Lower == Upper, but they aren't min or max value!");
57}
58
60 bool IsSigned) {
61 assert(!Known.hasConflict() && "Expected valid KnownBits");
62
63 if (Known.isUnknown())
64 return getFull(Known.getBitWidth());
65
66 // For unsigned ranges, or signed ranges with known sign bit, create a simple
67 // range between the smallest and largest possible value.
68 if (!IsSigned || Known.isNegative() || Known.isNonNegative())
69 return ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1);
70
71 // If we don't know the sign bit, pick the lower bound as a negative number
72 // and the upper bound as a non-negative one.
73 APInt Lower = Known.getMinValue(), Upper = Known.getMaxValue();
74 Lower.setSignBit();
75 Upper.clearSignBit();
76 return ConstantRange(Lower, Upper + 1);
77}
78
80 // TODO: We could return conflicting known bits here, but consumers are
81 // likely not prepared for that.
82 if (isEmptySet())
83 return KnownBits(getBitWidth());
84
85 // We can only retain the top bits that are the same between min and max.
86 APInt Min = getUnsignedMin();
87 APInt Max = getUnsignedMax();
89 if (std::optional<unsigned> DifferentBit =
91 Known.Zero.clearLowBits(*DifferentBit + 1);
92 Known.One.clearLowBits(*DifferentBit + 1);
93 }
94 return Known;
95}
96
98 const ConstantRange &CR) {
99 if (CR.isEmptySet())
100 return CR;
101
102 uint32_t W = CR.getBitWidth();
103 switch (Pred) {
104 default:
105 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
106 case CmpInst::ICMP_EQ:
107 return CR;
108 case CmpInst::ICMP_NE:
109 if (CR.isSingleElement())
110 return ConstantRange(CR.getUpper(), CR.getLower());
111 return getFull(W);
112 case CmpInst::ICMP_ULT: {
114 if (UMax.isMinValue())
115 return getEmpty(W);
116 return ConstantRange(APInt::getMinValue(W), std::move(UMax));
117 }
118 case CmpInst::ICMP_SLT: {
119 APInt SMax(CR.getSignedMax());
120 if (SMax.isMinSignedValue())
121 return getEmpty(W);
122 return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
123 }
125 return getNonEmpty(APInt::getMinValue(W), CR.getUnsignedMax() + 1);
128 case CmpInst::ICMP_UGT: {
130 if (UMin.isMaxValue())
131 return getEmpty(W);
132 return ConstantRange(std::move(UMin) + 1, APInt::getZero(W));
133 }
134 case CmpInst::ICMP_SGT: {
135 APInt SMin(CR.getSignedMin());
136 if (SMin.isMaxSignedValue())
137 return getEmpty(W);
138 return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
139 }
144 }
145}
146
148 const ConstantRange &CR) {
149 // Follows from De-Morgan's laws:
150 //
151 // ~(~A union ~B) == A intersect B.
152 //
154 .inverse();
155}
156
158 const APInt &C) {
159 // Computes the exact range that is equal to both the constant ranges returned
160 // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
161 // when RHS is a singleton such as an APInt and so the assert is valid.
162 // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
163 // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
164 //
166 return makeAllowedICmpRegion(Pred, C);
167}
168
170 const ConstantRange &CR1, const ConstantRange &CR2) {
171 if (CR1.isEmptySet() || CR2.isEmptySet())
172 return true;
173
174 return (CR1.isAllNonNegative() && CR2.isAllNonNegative()) ||
175 (CR1.isAllNegative() && CR2.isAllNegative());
176}
177
179 const ConstantRange &CR1, const ConstantRange &CR2) {
180 if (CR1.isEmptySet() || CR2.isEmptySet())
181 return true;
182
183 return (CR1.isAllNonNegative() && CR2.isAllNegative()) ||
184 (CR1.isAllNegative() && CR2.isAllNonNegative());
185}
186
188 CmpInst::Predicate Pred, const ConstantRange &CR1,
189 const ConstantRange &CR2) {
191 "Only for relational integer predicates!");
192
193 CmpInst::Predicate FlippedSignednessPred =
195
197 return FlippedSignednessPred;
198
200 return CmpInst::getInversePredicate(FlippedSignednessPred);
201
203}
204
206 APInt &RHS, APInt &Offset) const {
207 Offset = APInt(getBitWidth(), 0);
208 if (isFullSet() || isEmptySet()) {
210 RHS = APInt(getBitWidth(), 0);
211 } else if (auto *OnlyElt = getSingleElement()) {
212 Pred = CmpInst::ICMP_EQ;
213 RHS = *OnlyElt;
214 } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
215 Pred = CmpInst::ICMP_NE;
216 RHS = *OnlyMissingElt;
217 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
218 Pred =
220 RHS = getUpper();
221 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
222 Pred =
224 RHS = getLower();
225 } else {
226 Pred = CmpInst::ICMP_ULT;
227 RHS = getUpper() - getLower();
228 Offset = -getLower();
229 }
230
232 "Bad result!");
233}
234
236 APInt &RHS) const {
239 return Offset.isZero();
240}
241
243 const ConstantRange &Other) const {
244 return makeSatisfyingICmpRegion(Pred, Other).contains(*this);
245}
246
247/// Exact mul nuw region for single element RHS.
249 unsigned BitWidth = V.getBitWidth();
250 if (V == 0)
251 return ConstantRange::getFull(V.getBitWidth());
252
258}
259
260/// Exact mul nsw region for single element RHS.
262 // Handle 0 and -1 separately to avoid division by zero or overflow.
263 unsigned BitWidth = V.getBitWidth();
264 if (V == 0)
265 return ConstantRange::getFull(BitWidth);
266
269 // e.g. Returning [-127, 127], represented as [-127, -128).
270 if (V.isAllOnes())
271 return ConstantRange(-MaxValue, MinValue);
272
274 if (V.isNegative()) {
277 } else {
280 }
282}
283
286 const ConstantRange &Other,
287 unsigned NoWrapKind) {
288 using OBO = OverflowingBinaryOperator;
289
290 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
291
292 assert((NoWrapKind == OBO::NoSignedWrap ||
293 NoWrapKind == OBO::NoUnsignedWrap) &&
294 "NoWrapKind invalid!");
295
296 bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
297 unsigned BitWidth = Other.getBitWidth();
298
299 switch (BinOp) {
300 default:
301 llvm_unreachable("Unsupported binary op");
302
303 case Instruction::Add: {
304 if (Unsigned)
305 return getNonEmpty(APInt::getZero(BitWidth), -Other.getUnsignedMax());
306
308 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
309 return getNonEmpty(
310 SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal,
311 SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal);
312 }
313
314 case Instruction::Sub: {
315 if (Unsigned)
316 return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth));
317
319 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
320 return getNonEmpty(
321 SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal,
322 SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal);
323 }
324
325 case Instruction::Mul:
326 if (Unsigned)
327 return makeExactMulNUWRegion(Other.getUnsignedMax());
328
329 return makeExactMulNSWRegion(Other.getSignedMin())
330 .intersectWith(makeExactMulNSWRegion(Other.getSignedMax()));
331
332 case Instruction::Shl: {
333 // For given range of shift amounts, if we ignore all illegal shift amounts
334 // (that always produce poison), what shift amount range is left?
335 ConstantRange ShAmt = Other.intersectWith(
337 if (ShAmt.isEmptySet()) {
338 // If the entire range of shift amounts is already poison-producing,
339 // then we can freely add more poison-producing flags ontop of that.
340 return getFull(BitWidth);
341 }
342 // There are some legal shift amounts, we can compute conservatively-correct
343 // range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax
344 // to be at most bitwidth-1, which results in most conservative range.
345 APInt ShAmtUMax = ShAmt.getUnsignedMax();
346 if (Unsigned)
348 APInt::getMaxValue(BitWidth).lshr(ShAmtUMax) + 1);
350 APInt::getSignedMaxValue(BitWidth).ashr(ShAmtUMax) + 1);
351 }
352 }
353}
354
356 const APInt &Other,
357 unsigned NoWrapKind) {
358 // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
359 // "for all" and "for any" coincide in this case.
360 return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind);
361}
362
364 return Lower == Upper && Lower.isMaxValue();
365}
366
368 return Lower == Upper && Lower.isMinValue();
369}
370
372 return Lower.ugt(Upper) && !Upper.isZero();
373}
374
376 return Lower.ugt(Upper);
377}
378
380 return Lower.sgt(Upper) && !Upper.isMinSignedValue();
381}
382
384 return Lower.sgt(Upper);
385}
386
387bool
389 assert(getBitWidth() == Other.getBitWidth());
390 if (isFullSet())
391 return false;
392 if (Other.isFullSet())
393 return true;
394 return (Upper - Lower).ult(Other.Upper - Other.Lower);
395}
396
397bool
399 // If this a full set, we need special handling to avoid needing an extra bit
400 // to represent the size.
401 if (isFullSet())
402 return MaxSize == 0 || APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
403
404 return (Upper - Lower).ugt(MaxSize);
405}
406
408 // Empty set is all negative, full set is not.
409 if (isEmptySet())
410 return true;
411 if (isFullSet())
412 return false;
413
414 return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
415}
416
418 // Empty and full set are automatically treated correctly.
419 return !isSignWrappedSet() && Lower.isNonNegative();
420}
421
423 if (isFullSet() || isUpperWrapped())
425 return getUpper() - 1;
426}
427
429 if (isFullSet() || isWrappedSet())
431 return getLower();
432}
433
435 if (isFullSet() || isUpperSignWrapped())
437 return getUpper() - 1;
438}
439
441 if (isFullSet() || isSignWrappedSet())
443 return getLower();
444}
445
446bool ConstantRange::contains(const APInt &V) const {
447 if (Lower == Upper)
448 return isFullSet();
449
450 if (!isUpperWrapped())
451 return Lower.ule(V) && V.ult(Upper);
452 return Lower.ule(V) || V.ult(Upper);
453}
454
456 if (isFullSet() || Other.isEmptySet()) return true;
457 if (isEmptySet() || Other.isFullSet()) return false;
458
459 if (!isUpperWrapped()) {
460 if (Other.isUpperWrapped())
461 return false;
462
463 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
464 }
465
466 if (!Other.isUpperWrapped())
467 return Other.getUpper().ule(Upper) ||
468 Lower.ule(Other.getLower());
469
470 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
471}
472
474 if (isEmptySet())
475 return 0;
476
477 return getUnsignedMax().getActiveBits();
478}
479
481 if (isEmptySet())
482 return 0;
483
484 return std::max(getSignedMin().getMinSignedBits(),
486}
487
489 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
490 // If the set is empty or full, don't modify the endpoints.
491 if (Lower == Upper)
492 return *this;
493 return ConstantRange(Lower - Val, Upper - Val);
494}
495
497 return intersectWith(CR.inverse());
498}
499
501 const ConstantRange &CR1, const ConstantRange &CR2,
504 if (!CR1.isWrappedSet() && CR2.isWrappedSet())
505 return CR1;
506 if (CR1.isWrappedSet() && !CR2.isWrappedSet())
507 return CR2;
508 } else if (Type == ConstantRange::Signed) {
509 if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
510 return CR1;
511 if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
512 return CR2;
513 }
514
515 if (CR1.isSizeStrictlySmallerThan(CR2))
516 return CR1;
517 return CR2;
518}
519
521 PreferredRangeType Type) const {
522 assert(getBitWidth() == CR.getBitWidth() &&
523 "ConstantRange types don't agree!");
524
525 // Handle common cases.
526 if ( isEmptySet() || CR.isFullSet()) return *this;
527 if (CR.isEmptySet() || isFullSet()) return CR;
528
529 if (!isUpperWrapped() && CR.isUpperWrapped())
530 return CR.intersectWith(*this, Type);
531
532 if (!isUpperWrapped() && !CR.isUpperWrapped()) {
533 if (Lower.ult(CR.Lower)) {
534 // L---U : this
535 // L---U : CR
536 if (Upper.ule(CR.Lower))
537 return getEmpty();
538
539 // L---U : this
540 // L---U : CR
541 if (Upper.ult(CR.Upper))
542 return ConstantRange(CR.Lower, Upper);
543
544 // L-------U : this
545 // L---U : CR
546 return CR;
547 }
548 // L---U : this
549 // L-------U : CR
550 if (Upper.ult(CR.Upper))
551 return *this;
552
553 // L-----U : this
554 // L-----U : CR
555 if (Lower.ult(CR.Upper))
556 return ConstantRange(Lower, CR.Upper);
557
558 // L---U : this
559 // L---U : CR
560 return getEmpty();
561 }
562
563 if (isUpperWrapped() && !CR.isUpperWrapped()) {
564 if (CR.Lower.ult(Upper)) {
565 // ------U L--- : this
566 // L--U : CR
567 if (CR.Upper.ult(Upper))
568 return CR;
569
570 // ------U L--- : this
571 // L------U : CR
572 if (CR.Upper.ule(Lower))
573 return ConstantRange(CR.Lower, Upper);
574
575 // ------U L--- : this
576 // L----------U : CR
577 return getPreferredRange(*this, CR, Type);
578 }
579 if (CR.Lower.ult(Lower)) {
580 // --U L---- : this
581 // L--U : CR
582 if (CR.Upper.ule(Lower))
583 return getEmpty();
584
585 // --U L---- : this
586 // L------U : CR
587 return ConstantRange(Lower, CR.Upper);
588 }
589
590 // --U L------ : this
591 // L--U : CR
592 return CR;
593 }
594
595 if (CR.Upper.ult(Upper)) {
596 // ------U L-- : this
597 // --U L------ : CR
598 if (CR.Lower.ult(Upper))
599 return getPreferredRange(*this, CR, Type);
600
601 // ----U L-- : this
602 // --U L---- : CR
603 if (CR.Lower.ult(Lower))
604 return ConstantRange(Lower, CR.Upper);
605
606 // ----U L---- : this
607 // --U L-- : CR
608 return CR;
609 }
610 if (CR.Upper.ule(Lower)) {
611 // --U L-- : this
612 // ----U L---- : CR
613 if (CR.Lower.ult(Lower))
614 return *this;
615
616 // --U L---- : this
617 // ----U L-- : CR
618 return ConstantRange(CR.Lower, Upper);
619 }
620
621 // --U L------ : this
622 // ------U L-- : CR
623 return getPreferredRange(*this, CR, Type);
624}
625
627 PreferredRangeType Type) const {
628 assert(getBitWidth() == CR.getBitWidth() &&
629 "ConstantRange types don't agree!");
630
631 if ( isFullSet() || CR.isEmptySet()) return *this;
632 if (CR.isFullSet() || isEmptySet()) return CR;
633
634 if (!isUpperWrapped() && CR.isUpperWrapped())
635 return CR.unionWith(*this, Type);
636
637 if (!isUpperWrapped() && !CR.isUpperWrapped()) {
638 // L---U and L---U : this
639 // L---U L---U : CR
640 // result in one of
641 // L---------U
642 // -----U L-----
643 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower))
644 return getPreferredRange(
645 ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
646
647 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
648 APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
649
650 if (L.isZero() && U.isZero())
651 return getFull();
652
653 return ConstantRange(std::move(L), std::move(U));
654 }
655
656 if (!CR.isUpperWrapped()) {
657 // ------U L----- and ------U L----- : this
658 // L--U L--U : CR
659 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
660 return *this;
661
662 // ------U L----- : this
663 // L---------U : CR
664 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
665 return getFull();
666
667 // ----U L---- : this
668 // L---U : CR
669 // results in one of
670 // ----------U L----
671 // ----U L----------
672 if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower))
673 return getPreferredRange(
674 ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
675
676 // ----U L----- : this
677 // L----U : CR
678 if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))
679 return ConstantRange(CR.Lower, Upper);
680
681 // ------U L---- : this
682 // L-----U : CR
683 assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
684 "ConstantRange::unionWith missed a case with one range wrapped");
685 return ConstantRange(Lower, CR.Upper);
686 }
687
688 // ------U L---- and ------U L---- : this
689 // -U L----------- and ------------U L : CR
690 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
691 return getFull();
692
693 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
694 APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
695
696 return ConstantRange(std::move(L), std::move(U));
697}
698
699std::optional<ConstantRange>
701 // TODO: This can be implemented more efficiently.
702 ConstantRange Result = intersectWith(CR);
703 if (Result == inverse().unionWith(CR.inverse()).inverse())
704 return Result;
705 return std::nullopt;
706}
707
708std::optional<ConstantRange>
710 // TODO: This can be implemented more efficiently.
711 ConstantRange Result = unionWith(CR);
712 if (Result == inverse().intersectWith(CR.inverse()).inverse())
713 return Result;
714 return std::nullopt;
715}
716
718 uint32_t ResultBitWidth) const {
719 switch (CastOp) {
720 default:
721 llvm_unreachable("unsupported cast type");
722 case Instruction::Trunc:
723 return truncate(ResultBitWidth);
724 case Instruction::SExt:
725 return signExtend(ResultBitWidth);
726 case Instruction::ZExt:
727 return zeroExtend(ResultBitWidth);
728 case Instruction::BitCast:
729 return *this;
730 case Instruction::FPToUI:
731 case Instruction::FPToSI:
732 if (getBitWidth() == ResultBitWidth)
733 return *this;
734 else
735 return getFull(ResultBitWidth);
736 case Instruction::UIToFP: {
737 // TODO: use input range if available
738 auto BW = getBitWidth();
739 APInt Min = APInt::getMinValue(BW);
740 APInt Max = APInt::getMaxValue(BW);
741 if (ResultBitWidth > BW) {
742 Min = Min.zext(ResultBitWidth);
743 Max = Max.zext(ResultBitWidth);
744 }
745 return ConstantRange(std::move(Min), std::move(Max));
746 }
747 case Instruction::SIToFP: {
748 // TODO: use input range if available
749 auto BW = getBitWidth();
752 if (ResultBitWidth > BW) {
753 SMin = SMin.sext(ResultBitWidth);
754 SMax = SMax.sext(ResultBitWidth);
755 }
756 return ConstantRange(std::move(SMin), std::move(SMax));
757 }
758 case Instruction::FPTrunc:
759 case Instruction::FPExt:
760 case Instruction::IntToPtr:
761 case Instruction::PtrToInt:
762 case Instruction::AddrSpaceCast:
763 // Conservatively return getFull set.
764 return getFull(ResultBitWidth);
765 };
766}
767
769 if (isEmptySet()) return getEmpty(DstTySize);
770
771 unsigned SrcTySize = getBitWidth();
772 assert(SrcTySize < DstTySize && "Not a value extension");
773 if (isFullSet() || isUpperWrapped()) {
774 // Change into [0, 1 << src bit width)
775 APInt LowerExt(DstTySize, 0);
776 if (!Upper) // special case: [X, 0) -- not really wrapping around
777 LowerExt = Lower.zext(DstTySize);
778 return ConstantRange(std::move(LowerExt),
779 APInt::getOneBitSet(DstTySize, SrcTySize));
780 }
781
782 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
783}
784
786 if (isEmptySet()) return getEmpty(DstTySize);
787
788 unsigned SrcTySize = getBitWidth();
789 assert(SrcTySize < DstTySize && "Not a value extension");
790
791 // special case: [X, INT_MIN) -- not really wrapping around
792 if (Upper.isMinSignedValue())
793 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
794
795 if (isFullSet() || isSignWrappedSet()) {
796 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
797 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
798 }
799
800 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
801}
802
804 assert(getBitWidth() > DstTySize && "Not a value truncation");
805 if (isEmptySet())
806 return getEmpty(DstTySize);
807 if (isFullSet())
808 return getFull(DstTySize);
809
810 APInt LowerDiv(Lower), UpperDiv(Upper);
811 ConstantRange Union(DstTySize, /*isFullSet=*/false);
812
813 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
814 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
815 // then we do the union with [MaxValue, Upper)
816 if (isUpperWrapped()) {
817 // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
818 // truncated range.
819 if (Upper.getActiveBits() > DstTySize ||
820 Upper.countTrailingOnes() == DstTySize)
821 return getFull(DstTySize);
822
823 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
824 UpperDiv.setAllBits();
825
826 // Union covers the MaxValue case, so return if the remaining range is just
827 // MaxValue(DstTy).
828 if (LowerDiv == UpperDiv)
829 return Union;
830 }
831
832 // Chop off the most significant bits that are past the destination bitwidth.
833 if (LowerDiv.getActiveBits() > DstTySize) {
834 // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
835 APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
836 LowerDiv -= Adjust;
837 UpperDiv -= Adjust;
838 }
839
840 unsigned UpperDivWidth = UpperDiv.getActiveBits();
841 if (UpperDivWidth <= DstTySize)
842 return ConstantRange(LowerDiv.trunc(DstTySize),
843 UpperDiv.trunc(DstTySize)).unionWith(Union);
844
845 // The truncated value wraps around. Check if we can do better than fullset.
846 if (UpperDivWidth == DstTySize + 1) {
847 // Clear the MSB so that UpperDiv wraps around.
848 UpperDiv.clearBit(DstTySize);
849 if (UpperDiv.ult(LowerDiv))
850 return ConstantRange(LowerDiv.trunc(DstTySize),
851 UpperDiv.trunc(DstTySize)).unionWith(Union);
852 }
853
854 return getFull(DstTySize);
855}
856
858 unsigned SrcTySize = getBitWidth();
859 if (SrcTySize > DstTySize)
860 return truncate(DstTySize);
861 if (SrcTySize < DstTySize)
862 return zeroExtend(DstTySize);
863 return *this;
864}
865
867 unsigned SrcTySize = getBitWidth();
868 if (SrcTySize > DstTySize)
869 return truncate(DstTySize);
870 if (SrcTySize < DstTySize)
871 return signExtend(DstTySize);
872 return *this;
873}
874
876 const ConstantRange &Other) const {
877 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
878
879 switch (BinOp) {
880 case Instruction::Add:
881 return add(Other);
882 case Instruction::Sub:
883 return sub(Other);
884 case Instruction::Mul:
885 return multiply(Other);
886 case Instruction::UDiv:
887 return udiv(Other);
888 case Instruction::SDiv:
889 return sdiv(Other);
890 case Instruction::URem:
891 return urem(Other);
892 case Instruction::SRem:
893 return srem(Other);
894 case Instruction::Shl:
895 return shl(Other);
896 case Instruction::LShr:
897 return lshr(Other);
898 case Instruction::AShr:
899 return ashr(Other);
900 case Instruction::And:
901 return binaryAnd(Other);
902 case Instruction::Or:
903 return binaryOr(Other);
904 case Instruction::Xor:
905 return binaryXor(Other);
906 // Note: floating point operations applied to abstract ranges are just
907 // ideal integer operations with a lossy representation
908 case Instruction::FAdd:
909 return add(Other);
910 case Instruction::FSub:
911 return sub(Other);
912 case Instruction::FMul:
913 return multiply(Other);
914 default:
915 // Conservatively return getFull set.
916 return getFull();
917 }
918}
919
921 const ConstantRange &Other,
922 unsigned NoWrapKind) const {
923 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
924
925 switch (BinOp) {
926 case Instruction::Add:
927 return addWithNoWrap(Other, NoWrapKind);
928 case Instruction::Sub:
929 return subWithNoWrap(Other, NoWrapKind);
930 default:
931 // Don't know about this Overflowing Binary Operation.
932 // Conservatively fallback to plain binop handling.
933 return binaryOp(BinOp, Other);
934 }
935}
936
938 switch (IntrinsicID) {
939 case Intrinsic::uadd_sat:
940 case Intrinsic::usub_sat:
941 case Intrinsic::sadd_sat:
942 case Intrinsic::ssub_sat:
943 case Intrinsic::umin:
944 case Intrinsic::umax:
945 case Intrinsic::smin:
946 case Intrinsic::smax:
947 case Intrinsic::abs:
948 return true;
949 default:
950 return false;
951 }
952}
953
956 switch (IntrinsicID) {
957 case Intrinsic::uadd_sat:
958 return Ops[0].uadd_sat(Ops[1]);
959 case Intrinsic::usub_sat:
960 return Ops[0].usub_sat(Ops[1]);
961 case Intrinsic::sadd_sat:
962 return Ops[0].sadd_sat(Ops[1]);
963 case Intrinsic::ssub_sat:
964 return Ops[0].ssub_sat(Ops[1]);
965 case Intrinsic::umin:
966 return Ops[0].umin(Ops[1]);
967 case Intrinsic::umax:
968 return Ops[0].umax(Ops[1]);
969 case Intrinsic::smin:
970 return Ops[0].smin(Ops[1]);
971 case Intrinsic::smax:
972 return Ops[0].smax(Ops[1]);
973 case Intrinsic::abs: {
974 const APInt *IntMinIsPoison = Ops[1].getSingleElement();
975 assert(IntMinIsPoison && "Must be known (immarg)");
976 assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean");
977 return Ops[0].abs(IntMinIsPoison->getBoolValue());
978 }
979 default:
980 assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported");
981 llvm_unreachable("Unsupported intrinsic");
982 }
983}
984
987 if (isEmptySet() || Other.isEmptySet())
988 return getEmpty();
989 if (isFullSet() || Other.isFullSet())
990 return getFull();
991
992 APInt NewLower = getLower() + Other.getLower();
993 APInt NewUpper = getUpper() + Other.getUpper() - 1;
994 if (NewLower == NewUpper)
995 return getFull();
996
997 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
998 if (X.isSizeStrictlySmallerThan(*this) ||
999 X.isSizeStrictlySmallerThan(Other))
1000 // We've wrapped, therefore, full set.
1001 return getFull();
1002 return X;
1003}
1004
1006 unsigned NoWrapKind,
1007 PreferredRangeType RangeType) const {
1008 // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
1009 // (X is from this, and Y is from Other)
1010 if (isEmptySet() || Other.isEmptySet())
1011 return getEmpty();
1012 if (isFullSet() && Other.isFullSet())
1013 return getFull();
1014
1015 using OBO = OverflowingBinaryOperator;
1016 ConstantRange Result = add(Other);
1017
1018 // If an overflow happens for every value pair in these two constant ranges,
1019 // we must return Empty set. In this case, we get that for free, because we
1020 // get lucky that intersection of add() with uadd_sat()/sadd_sat() results
1021 // in an empty set.
1022
1023 if (NoWrapKind & OBO::NoSignedWrap)
1024 Result = Result.intersectWith(sadd_sat(Other), RangeType);
1025
1026 if (NoWrapKind & OBO::NoUnsignedWrap)
1027 Result = Result.intersectWith(uadd_sat(Other), RangeType);
1028
1029 return Result;
1030}
1031
1034 if (isEmptySet() || Other.isEmptySet())
1035 return getEmpty();
1036 if (isFullSet() || Other.isFullSet())
1037 return getFull();
1038
1039 APInt NewLower = getLower() - Other.getUpper() + 1;
1040 APInt NewUpper = getUpper() - Other.getLower();
1041 if (NewLower == NewUpper)
1042 return getFull();
1043
1044 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1045 if (X.isSizeStrictlySmallerThan(*this) ||
1046 X.isSizeStrictlySmallerThan(Other))
1047 // We've wrapped, therefore, full set.
1048 return getFull();
1049 return X;
1050}
1051
1053 unsigned NoWrapKind,
1054 PreferredRangeType RangeType) const {
1055 // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).
1056 // (X is from this, and Y is from Other)
1057 if (isEmptySet() || Other.isEmptySet())
1058 return getEmpty();
1059 if (isFullSet() && Other.isFullSet())
1060 return getFull();
1061
1062 using OBO = OverflowingBinaryOperator;
1063 ConstantRange Result = sub(Other);
1064
1065 // If an overflow happens for every value pair in these two constant ranges,
1066 // we must return Empty set. In signed case, we get that for free, because we
1067 // get lucky that intersection of sub() with ssub_sat() results in an
1068 // empty set. But for unsigned we must perform the overflow check manually.
1069
1070 if (NoWrapKind & OBO::NoSignedWrap)
1071 Result = Result.intersectWith(ssub_sat(Other), RangeType);
1072
1073 if (NoWrapKind & OBO::NoUnsignedWrap) {
1074 if (getUnsignedMax().ult(Other.getUnsignedMin()))
1075 return getEmpty(); // Always overflows.
1076 Result = Result.intersectWith(usub_sat(Other), RangeType);
1077 }
1078
1079 return Result;
1080}
1081
1084 // TODO: If either operand is a single element and the multiply is known to
1085 // be non-wrapping, round the result min and max value to the appropriate
1086 // multiple of that element. If wrapping is possible, at least adjust the
1087 // range according to the greatest power-of-two factor of the single element.
1088
1089 if (isEmptySet() || Other.isEmptySet())
1090 return getEmpty();
1091
1092 // Multiplication is signedness-independent. However different ranges can be
1093 // obtained depending on how the input ranges are treated. These different
1094 // ranges are all conservatively correct, but one might be better than the
1095 // other. We calculate two ranges; one treating the inputs as unsigned
1096 // and the other signed, then return the smallest of these ranges.
1097
1098 // Unsigned range first.
1099 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
1100 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
1101 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
1102 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
1103
1104 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
1105 this_max * Other_max + 1);
1106 ConstantRange UR = Result_zext.truncate(getBitWidth());
1107
1108 // If the unsigned range doesn't wrap, and isn't negative then it's a range
1109 // from one positive number to another which is as good as we can generate.
1110 // In this case, skip the extra work of generating signed ranges which aren't
1111 // going to be better than this range.
1112 if (!UR.isUpperWrapped() &&
1114 return UR;
1115
1116 // Now the signed range. Because we could be dealing with negative numbers
1117 // here, the lower bound is the smallest of the cartesian product of the
1118 // lower and upper ranges; for example:
1119 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1120 // Similarly for the upper bound, swapping min for max.
1121
1122 this_min = getSignedMin().sext(getBitWidth() * 2);
1123 this_max = getSignedMax().sext(getBitWidth() * 2);
1124 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
1125 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
1126
1127 auto L = {this_min * Other_min, this_min * Other_max,
1128 this_max * Other_min, this_max * Other_max};
1129 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1130 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
1131 ConstantRange SR = Result_sext.truncate(getBitWidth());
1132
1133 return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
1134}
1135
1137 if (isEmptySet() || Other.isEmptySet())
1138 return getEmpty();
1139
1140 APInt Min = getSignedMin();
1141 APInt Max = getSignedMax();
1142 APInt OtherMin = Other.getSignedMin();
1143 APInt OtherMax = Other.getSignedMax();
1144
1145 bool O1, O2, O3, O4;
1146 auto Muls = {Min.smul_ov(OtherMin, O1), Min.smul_ov(OtherMax, O2),
1147 Max.smul_ov(OtherMin, O3), Max.smul_ov(OtherMax, O4)};
1148 if (O1 || O2 || O3 || O4)
1149 return getFull();
1150
1151 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1152 return getNonEmpty(std::min(Muls, Compare), std::max(Muls, Compare) + 1);
1153}
1154
1157 // X smax Y is: range(smax(X_smin, Y_smin),
1158 // smax(X_smax, Y_smax))
1159 if (isEmptySet() || Other.isEmptySet())
1160 return getEmpty();
1161 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
1162 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
1163 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1164 if (isSignWrappedSet() || Other.isSignWrappedSet())
1165 return Res.intersectWith(unionWith(Other, Signed), Signed);
1166 return Res;
1167}
1168
1171 // X umax Y is: range(umax(X_umin, Y_umin),
1172 // umax(X_umax, Y_umax))
1173 if (isEmptySet() || Other.isEmptySet())
1174 return getEmpty();
1175 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
1176 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1177 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1178 if (isWrappedSet() || Other.isWrappedSet())
1180 return Res;
1181}
1182
1185 // X smin Y is: range(smin(X_smin, Y_smin),
1186 // smin(X_smax, Y_smax))
1187 if (isEmptySet() || Other.isEmptySet())
1188 return getEmpty();
1189 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
1190 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
1191 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1192 if (isSignWrappedSet() || Other.isSignWrappedSet())
1193 return Res.intersectWith(unionWith(Other, Signed), Signed);
1194 return Res;
1195}
1196
1199 // X umin Y is: range(umin(X_umin, Y_umin),
1200 // umin(X_umax, Y_umax))
1201 if (isEmptySet() || Other.isEmptySet())
1202 return getEmpty();
1203 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
1204 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1205 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1206 if (isWrappedSet() || Other.isWrappedSet())
1208 return Res;
1209}
1210
1213 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1214 return getEmpty();
1215
1216 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
1217
1218 APInt RHS_umin = RHS.getUnsignedMin();
1219 if (RHS_umin.isZero()) {
1220 // We want the lowest value in RHS excluding zero. Usually that would be 1
1221 // except for a range in the form of [X, 1) in which case it would be X.
1222 if (RHS.getUpper() == 1)
1223 RHS_umin = RHS.getLower();
1224 else
1225 RHS_umin = 1;
1226 }
1227
1228 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
1229 return getNonEmpty(std::move(Lower), std::move(Upper));
1230}
1231
1233 // We split up the LHS and RHS into positive and negative components
1234 // and then also compute the positive and negative components of the result
1235 // separately by combining division results with the appropriate signs.
1238 // There are no positive 1-bit values. The 1 would get interpreted as -1.
1239 ConstantRange PosFilter =
1240 getBitWidth() == 1 ? getEmpty()
1241 : ConstantRange(APInt(getBitWidth(), 1), SignedMin);
1242 ConstantRange NegFilter(SignedMin, Zero);
1243 ConstantRange PosL = intersectWith(PosFilter);
1244 ConstantRange NegL = intersectWith(NegFilter);
1245 ConstantRange PosR = RHS.intersectWith(PosFilter);
1246 ConstantRange NegR = RHS.intersectWith(NegFilter);
1247
1248 ConstantRange PosRes = getEmpty();
1249 if (!PosL.isEmptySet() && !PosR.isEmptySet())
1250 // pos / pos = pos.
1251 PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),
1252 (PosL.Upper - 1).sdiv(PosR.Lower) + 1);
1253
1254 if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1255 // neg / neg = pos.
1256 //
1257 // We need to deal with one tricky case here: SignedMin / -1 is UB on the
1258 // IR level, so we'll want to exclude this case when calculating bounds.
1259 // (For APInts the operation is well-defined and yields SignedMin.) We
1260 // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1261 APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);
1262 if (NegL.Lower.isMinSignedValue() && NegR.Upper.isZero()) {
1263 // Remove -1 from the LHS. Skip if it's the only element, as this would
1264 // leave us with an empty set.
1265 if (!NegR.Lower.isAllOnes()) {
1266 APInt AdjNegRUpper;
1267 if (RHS.Lower.isAllOnes())
1268 // Negative part of [-1, X] without -1 is [SignedMin, X].
1269 AdjNegRUpper = RHS.Upper;
1270 else
1271 // [X, -1] without -1 is [X, -2].
1272 AdjNegRUpper = NegR.Upper - 1;
1273
1274 PosRes = PosRes.unionWith(
1275 ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
1276 }
1277
1278 // Remove SignedMin from the RHS. Skip if it's the only element, as this
1279 // would leave us with an empty set.
1280 if (NegL.Upper != SignedMin + 1) {
1281 APInt AdjNegLLower;
1282 if (Upper == SignedMin + 1)
1283 // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1284 AdjNegLLower = Lower;
1285 else
1286 // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1287 AdjNegLLower = NegL.Lower + 1;
1288
1289 PosRes = PosRes.unionWith(
1290 ConstantRange(std::move(Lo),
1291 AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
1292 }
1293 } else {
1294 PosRes = PosRes.unionWith(
1295 ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
1296 }
1297 }
1298
1299 ConstantRange NegRes = getEmpty();
1300 if (!PosL.isEmptySet() && !NegR.isEmptySet())
1301 // pos / neg = neg.
1302 NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
1303 PosL.Lower.sdiv(NegR.Lower) + 1);
1304
1305 if (!NegL.isEmptySet() && !PosR.isEmptySet())
1306 // neg / pos = neg.
1307 NegRes = NegRes.unionWith(
1308 ConstantRange(NegL.Lower.sdiv(PosR.Lower),
1309 (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));
1310
1311 // Prefer a non-wrapping signed range here.
1313
1314 // Preserve the zero that we dropped when splitting the LHS by sign.
1315 if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1316 Res = Res.unionWith(ConstantRange(Zero));
1317 return Res;
1318}
1319
1321 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1322 return getEmpty();
1323
1324 if (const APInt *RHSInt = RHS.getSingleElement()) {
1325 // UREM by null is UB.
1326 if (RHSInt->isZero())
1327 return getEmpty();
1328 // Use APInt's implementation of UREM for single element ranges.
1329 if (const APInt *LHSInt = getSingleElement())
1330 return {LHSInt->urem(*RHSInt)};
1331 }
1332
1333 // L % R for L < R is L.
1334 if (getUnsignedMax().ult(RHS.getUnsignedMin()))
1335 return *this;
1336
1337 // L % R is <= L and < R.
1338 APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
1339 return getNonEmpty(APInt::getZero(getBitWidth()), std::move(Upper));
1340}
1341
1343 if (isEmptySet() || RHS.isEmptySet())
1344 return getEmpty();
1345
1346 if (const APInt *RHSInt = RHS.getSingleElement()) {
1347 // SREM by null is UB.
1348 if (RHSInt->isZero())
1349 return getEmpty();
1350 // Use APInt's implementation of SREM for single element ranges.
1351 if (const APInt *LHSInt = getSingleElement())
1352 return {LHSInt->srem(*RHSInt)};
1353 }
1354
1355 ConstantRange AbsRHS = RHS.abs();
1356 APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1357 APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1358
1359 // Modulus by zero is UB.
1360 if (MaxAbsRHS.isZero())
1361 return getEmpty();
1362
1363 if (MinAbsRHS.isZero())
1364 ++MinAbsRHS;
1365
1366 APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1367
1368 if (MinLHS.isNonNegative()) {
1369 // L % R for L < R is L.
1370 if (MaxLHS.ult(MinAbsRHS))
1371 return *this;
1372
1373 // L % R is <= L and < R.
1374 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1375 return ConstantRange(APInt::getZero(getBitWidth()), std::move(Upper));
1376 }
1377
1378 // Same basic logic as above, but the result is negative.
1379 if (MaxLHS.isNegative()) {
1380 if (MinLHS.ugt(-MinAbsRHS))
1381 return *this;
1382
1383 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1384 return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1385 }
1386
1387 // LHS range crosses zero.
1388 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1389 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1390 return ConstantRange(std::move(Lower), std::move(Upper));
1391}
1392
1395}
1396
1398 if (isEmptySet() || Other.isEmptySet())
1399 return getEmpty();
1400
1401 ConstantRange KnownBitsRange =
1402 fromKnownBits(toKnownBits() & Other.toKnownBits(), false);
1403 ConstantRange UMinUMaxRange =
1405 APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()) + 1);
1406 return KnownBitsRange.intersectWith(UMinUMaxRange);
1407}
1408
1410 if (isEmptySet() || Other.isEmptySet())
1411 return getEmpty();
1412
1413 ConstantRange KnownBitsRange =
1414 fromKnownBits(toKnownBits() | Other.toKnownBits(), false);
1415 // Upper wrapped range.
1416 ConstantRange UMaxUMinRange =
1417 getNonEmpty(APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()),
1419 return KnownBitsRange.intersectWith(UMaxUMinRange);
1420}
1421
1423 if (isEmptySet() || Other.isEmptySet())
1424 return getEmpty();
1425
1426 // Use APInt's implementation of XOR for single element ranges.
1427 if (isSingleElement() && Other.isSingleElement())
1428 return {*getSingleElement() ^ *Other.getSingleElement()};
1429
1430 // Special-case binary complement, since we can give a precise answer.
1431 if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes())
1432 return binaryNot();
1433 if (isSingleElement() && getSingleElement()->isAllOnes())
1434 return Other.binaryNot();
1435
1436 return fromKnownBits(toKnownBits() ^ Other.toKnownBits(), /*IsSigned*/false);
1437}
1438
1441 if (isEmptySet() || Other.isEmptySet())
1442 return getEmpty();
1443
1444 APInt Min = getUnsignedMin();
1445 APInt Max = getUnsignedMax();
1446 if (const APInt *RHS = Other.getSingleElement()) {
1447 unsigned BW = getBitWidth();
1448 if (RHS->uge(BW))
1449 return getEmpty();
1450
1451 unsigned EqualLeadingBits = (Min ^ Max).countLeadingZeros();
1452 if (RHS->ule(EqualLeadingBits))
1453 return getNonEmpty(Min << *RHS, (Max << *RHS) + 1);
1454
1455 return getNonEmpty(APInt::getZero(BW),
1456 APInt::getBitsSetFrom(BW, RHS->getZExtValue()) + 1);
1457 }
1458
1459 APInt OtherMax = Other.getUnsignedMax();
1460
1461 // There's overflow!
1462 if (OtherMax.ugt(Max.countLeadingZeros()))
1463 return getFull();
1464
1465 // FIXME: implement the other tricky cases
1466
1467 Min <<= Other.getUnsignedMin();
1468 Max <<= OtherMax;
1469
1470 return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1);
1471}
1472
1475 if (isEmptySet() || Other.isEmptySet())
1476 return getEmpty();
1477
1478 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1479 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1480 return getNonEmpty(std::move(min), std::move(max));
1481}
1482
1485 if (isEmptySet() || Other.isEmptySet())
1486 return getEmpty();
1487
1488 // May straddle zero, so handle both positive and negative cases.
1489 // 'PosMax' is the upper bound of the result of the ashr
1490 // operation, when Upper of the LHS of ashr is a non-negative.
1491 // number. Since ashr of a non-negative number will result in a
1492 // smaller number, the Upper value of LHS is shifted right with
1493 // the minimum value of 'Other' instead of the maximum value.
1494 APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1495
1496 // 'PosMin' is the lower bound of the result of the ashr
1497 // operation, when Lower of the LHS is a non-negative number.
1498 // Since ashr of a non-negative number will result in a smaller
1499 // number, the Lower value of LHS is shifted right with the
1500 // maximum value of 'Other'.
1501 APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1502
1503 // 'NegMax' is the upper bound of the result of the ashr
1504 // operation, when Upper of the LHS of ashr is a negative number.
1505 // Since 'ashr' of a negative number will result in a bigger
1506 // number, the Upper value of LHS is shifted right with the
1507 // maximum value of 'Other'.
1508 APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1509
1510 // 'NegMin' is the lower bound of the result of the ashr
1511 // operation, when Lower of the LHS of ashr is a negative number.
1512 // Since 'ashr' of a negative number will result in a bigger
1513 // number, the Lower value of LHS is shifted right with the
1514 // minimum value of 'Other'.
1515 APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1516
1517 APInt max, min;
1518 if (getSignedMin().isNonNegative()) {
1519 // Upper and Lower of LHS are non-negative.
1520 min = PosMin;
1521 max = PosMax;
1522 } else if (getSignedMax().isNegative()) {
1523 // Upper and Lower of LHS are negative.
1524 min = NegMin;
1525 max = NegMax;
1526 } else {
1527 // Upper is non-negative and Lower is negative.
1528 min = NegMin;
1529 max = PosMax;
1530 }
1531 return getNonEmpty(std::move(min), std::move(max));
1532}
1533
1535 if (isEmptySet() || Other.isEmptySet())
1536 return getEmpty();
1537
1538 APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());
1539 APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;
1540 return getNonEmpty(std::move(NewL), std::move(NewU));
1541}
1542
1544 if (isEmptySet() || Other.isEmptySet())
1545 return getEmpty();
1546
1547 APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());
1548 APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;
1549 return getNonEmpty(std::move(NewL), std::move(NewU));
1550}
1551
1553 if (isEmptySet() || Other.isEmptySet())
1554 return getEmpty();
1555
1556 APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());
1557 APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;
1558 return getNonEmpty(std::move(NewL), std::move(NewU));
1559}
1560
1562 if (isEmptySet() || Other.isEmptySet())
1563 return getEmpty();
1564
1565 APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
1566 APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
1567 return getNonEmpty(std::move(NewL), std::move(NewU));
1568}
1569
1571 if (isEmptySet() || Other.isEmptySet())
1572 return getEmpty();
1573
1574 APInt NewL = getUnsignedMin().umul_sat(Other.getUnsignedMin());
1575 APInt NewU = getUnsignedMax().umul_sat(Other.getUnsignedMax()) + 1;
1576 return getNonEmpty(std::move(NewL), std::move(NewU));
1577}
1578
1580 if (isEmptySet() || Other.isEmptySet())
1581 return getEmpty();
1582
1583 // Because we could be dealing with negative numbers here, the lower bound is
1584 // the smallest of the cartesian product of the lower and upper ranges;
1585 // for example:
1586 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1587 // Similarly for the upper bound, swapping min for max.
1588
1589 APInt Min = getSignedMin();
1590 APInt Max = getSignedMax();
1591 APInt OtherMin = Other.getSignedMin();
1592 APInt OtherMax = Other.getSignedMax();
1593
1594 auto L = {Min.smul_sat(OtherMin), Min.smul_sat(OtherMax),
1595 Max.smul_sat(OtherMin), Max.smul_sat(OtherMax)};
1596 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1597 return getNonEmpty(std::min(L, Compare), std::max(L, Compare) + 1);
1598}
1599
1601 if (isEmptySet() || Other.isEmptySet())
1602 return getEmpty();
1603
1604 APInt NewL = getUnsignedMin().ushl_sat(Other.getUnsignedMin());
1605 APInt NewU = getUnsignedMax().ushl_sat(Other.getUnsignedMax()) + 1;
1606 return getNonEmpty(std::move(NewL), std::move(NewU));
1607}
1608
1610 if (isEmptySet() || Other.isEmptySet())
1611 return getEmpty();
1612
1613 APInt Min = getSignedMin(), Max = getSignedMax();
1614 APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax();
1615 APInt NewL = Min.sshl_sat(Min.isNonNegative() ? ShAmtMin : ShAmtMax);
1616 APInt NewU = Max.sshl_sat(Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;
1617 return getNonEmpty(std::move(NewL), std::move(NewU));
1618}
1619
1621 if (isFullSet())
1622 return getEmpty();
1623 if (isEmptySet())
1624 return getFull();
1625 return ConstantRange(Upper, Lower);
1626}
1627
1628ConstantRange ConstantRange::abs(bool IntMinIsPoison) const {
1629 if (isEmptySet())
1630 return getEmpty();
1631
1632 if (isSignWrappedSet()) {
1633 APInt Lo;
1634 // Check whether the range crosses zero.
1635 if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1637 else
1638 Lo = APIntOps::umin(Lower, -Upper + 1);
1639
1640 // If SignedMin is not poison, then it is included in the result range.
1641 if (IntMinIsPoison)
1643 else
1645 }
1646
1648
1649 // Skip SignedMin if it is poison.
1650 if (IntMinIsPoison && SMin.isMinSignedValue()) {
1651 // The range may become empty if it *only* contains SignedMin.
1652 if (SMax.isMinSignedValue())
1653 return getEmpty();
1654 ++SMin;
1655 }
1656
1657 // All non-negative.
1658 if (SMin.isNonNegative())
1659 return ConstantRange(SMin, SMax + 1);
1660
1661 // All negative.
1662 if (SMax.isNegative())
1663 return ConstantRange(-SMax, -SMin + 1);
1664
1665 // Range crosses zero.
1667 APIntOps::umax(-SMin, SMax) + 1);
1668}
1669
1671 const ConstantRange &Other) const {
1672 if (isEmptySet() || Other.isEmptySet())
1674
1675 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1676 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1677
1678 // a u+ b overflows high iff a u> ~b.
1679 if (Min.ugt(~OtherMin))
1681 if (Max.ugt(~OtherMax))
1684}
1685
1687 const ConstantRange &Other) const {
1688 if (isEmptySet() || Other.isEmptySet())
1690
1691 APInt Min = getSignedMin(), Max = getSignedMax();
1692 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1693
1696
1697 // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1698 // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1699 if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1700 Min.sgt(SignedMax - OtherMin))
1702 if (Max.isNegative() && OtherMax.isNegative() &&
1703 Max.slt(SignedMin - OtherMax))
1705
1706 if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1707 Max.sgt(SignedMax - OtherMax))
1709 if (Min.isNegative() && OtherMin.isNegative() &&
1710 Min.slt(SignedMin - OtherMin))
1712
1714}
1715
1717 const ConstantRange &Other) const {
1718 if (isEmptySet() || Other.isEmptySet())
1720
1721 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1722 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1723
1724 // a u- b overflows low iff a u< b.
1725 if (Max.ult(OtherMin))
1727 if (Min.ult(OtherMax))
1730}
1731
1733 const ConstantRange &Other) const {
1734 if (isEmptySet() || Other.isEmptySet())
1736
1737 APInt Min = getSignedMin(), Max = getSignedMax();
1738 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1739
1742
1743 // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
1744 // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
1745 if (Min.isNonNegative() && OtherMax.isNegative() &&
1746 Min.sgt(SignedMax + OtherMax))
1748 if (Max.isNegative() && OtherMin.isNonNegative() &&
1749 Max.slt(SignedMin + OtherMin))
1751
1752 if (Max.isNonNegative() && OtherMin.isNegative() &&
1753 Max.sgt(SignedMax + OtherMin))
1755 if (Min.isNegative() && OtherMax.isNonNegative() &&
1756 Min.slt(SignedMin + OtherMax))
1758
1760}
1761
1763 const ConstantRange &Other) const {
1764 if (isEmptySet() || Other.isEmptySet())
1766
1767 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1768 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1769 bool Overflow;
1770
1771 (void) Min.umul_ov(OtherMin, Overflow);
1772 if (Overflow)
1774
1775 (void) Max.umul_ov(OtherMax, Overflow);
1776 if (Overflow)
1778
1780}
1781
1783 if (isFullSet())
1784 OS << "full-set";
1785 else if (isEmptySet())
1786 OS << "empty-set";
1787 else
1788 OS << "[" << Lower << "," << Upper << ")";
1789}
1790
1791#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1793 print(dbgs());
1794}
1795#endif
1796
1798 const unsigned NumRanges = Ranges.getNumOperands() / 2;
1799 assert(NumRanges >= 1 && "Must have at least one range!");
1800 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1801
1802 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1803 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1804
1805 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1806
1807 for (unsigned i = 1; i < NumRanges; ++i) {
1808 auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1809 auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1810
1811 // Note: unionWith will potentially create a range that contains values not
1812 // contained in any of the original N ranges.
1813 CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1814 }
1815
1816 return CR;
1817}
This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
static ConstantRange makeExactMulNUWRegion(const APInt &V)
Exact mul nuw region for single element RHS.
static ConstantRange makeExactMulNSWRegion(const APInt &V)
Exact mul nsw region for single element RHS.
static ConstantRange getPreferredRange(const ConstantRange &CR1, const ConstantRange &CR2, ConstantRange::PreferredRangeType Type)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file contains the declarations for metadata subclasses.
uint64_t High
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Class for arbitrary precision integers.
Definition: APInt.h:75
APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1969
APInt usub_sat(const APInt &RHS) const
Definition: APInt.cpp:2038
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1571
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1385
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:973
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:415
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1463
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:898
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:186
APInt smul_sat(const APInt &RHS) const
Definition: APInt.cpp:2047
APInt sadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2009
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1179
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:354
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1160
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:366
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1439
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1089
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:409
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:196
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:312
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition: APInt.cpp:1642
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
APInt sshl_sat(const APInt &RHS) const
Definition: APInt.cpp:2069
APInt ushl_sat(const APInt &RHS) const
Definition: APInt.cpp:2079
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
Definition: APInt.h:339
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
Definition: APInt.h:1395
APInt uadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2019
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:815
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1297
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:459
APInt smul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1958
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:317
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1128
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:946
APInt umul_sat(const APInt &RHS) const
Definition: APInt.cpp:2060
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:289
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1108
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:279
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:177
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1607
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:269
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:222
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:839
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1199
void clearSignBit()
Set the sign bit to 0.
Definition: APInt.h:1402
APInt ssub_sat(const APInt &RHS) const
Definition: APInt.cpp:2028
bool isMaxValue() const
Determine if this is the largest unsigned value.
Definition: APInt.h:391
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:747
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:748
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:742
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:741
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:745
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
@ ICMP_EQ
equal
Definition: InstrTypes.h:739
@ ICMP_NE
not equal
Definition: InstrTypes.h:740
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:746
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:744
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:832
Predicate getFlippedSignednessPredicate()
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->Failed assert.
Definition: InstrTypes.h:1000
bool isIntPredicate() const
Definition: InstrTypes.h:826
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
Definition: InstrTypes.h:953
This class represents a range of values.
Definition: ConstantRange.h:47
ConstantRange multiply(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a multiplication of a value in thi...
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 isUpperSignWrapped() const
Return true if the (exclusive) upper bound wraps around the signed domain.
unsigned getActiveBits() const
Compute the maximal number of active bits needed to represent every value in this range.
ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
std::optional< ConstantRange > exactUnionWith(const ConstantRange &CR) const
Union the two ranges and return the result if it can be represented exactly, otherwise return std::nu...
bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
ConstantRange umul_sat(const ConstantRange &Other) const
Perform an unsigned saturating multiplication of two constant ranges.
static CmpInst::Predicate getEquivalentPredWithFlippedSignedness(CmpInst::Predicate Pred, const ConstantRange &CR1, const ConstantRange &CR2)
If the comparison between constant ranges this and Other is insensitive to the signedness of the comp...
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
ConstantRange binaryXor(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-xor of a value in this ra...
const APInt * getSingleMissingElement() const
If this set contains all but a single element, return it, otherwise return null.
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
const APInt & getLower() const
Return the lower value for this range.
OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const
Return whether unsigned sub of the two ranges always/never overflows.
bool isAllNegative() const
Return true if all values in this range are negative.
ConstantRange truncate(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const
Return whether unsigned add of the two ranges always/never overflows.
ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
ConstantRange sshl_sat(const ConstantRange &Other) const
Perform a signed saturating left shift of this constant range by a value in Other.
ConstantRange smul_fast(const ConstantRange &Other) const
Return range of possible values for a signed multiplication of this and Other.
ConstantRange lshr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a logical right shift of a value i...
KnownBits toKnownBits() const
Return known bits for values in this range.
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...
ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
ConstantRange srem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed remainder operation of a ...
bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other? NOTE: false does not mean that inverse pr...
ConstantRange sadd_sat(const ConstantRange &Other) const
Perform a signed saturating addition of two constant ranges.
ConstantRange ushl_sat(const ConstantRange &Other) const
Perform an unsigned saturating left shift of this constant range by a value in Other.
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
void dump() const
Allow printing from a debugger easily.
bool isEmptySet() const
Return true if this set contains no members.
ConstantRange smul_sat(const ConstantRange &Other) const
Perform a signed saturating multiplication of two constant ranges.
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...
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 isSignWrappedSet() const
Return true if this set wraps around the signed domain.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
ConstantRange abs(bool IntMinIsPoison=false) const
Calculate absolute value range.
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
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 isWrappedSet() const
Return true if this set wraps around the unsigned domain.
ConstantRange usub_sat(const ConstantRange &Other) const
Perform an unsigned saturating subtraction of two constant ranges.
ConstantRange uadd_sat(const ConstantRange &Other) const
Perform an unsigned saturating addition of two constant ranges.
ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind) const
Return a new range representing the possible values resulting from an application of the specified ov...
void print(raw_ostream &OS) const
Print out the bounds to a stream.
ConstantRange(uint32_t BitWidth, bool isFullSet)
Initialize a full or empty set for the specified bit width.
OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const
Return whether unsigned mul of the two ranges always/never overflows.
ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from an subtraction with wrap type NoWr...
bool isSingleElement() const
Return true if this set contains exactly one member.
ConstantRange ssub_sat(const ConstantRange &Other) const
Perform a signed saturating subtraction of two constant ranges.
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
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...
ConstantRange sdiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed division of a value in th...
const APInt & getUpper() const
Return the upper value for this range.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
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...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
std::optional< ConstantRange > exactIntersectWith(const ConstantRange &CR) const
Intersect the two ranges and return the result if it can be represented exactly, otherwise return std...
ConstantRange ashr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a arithmetic right shift of a valu...
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...
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
static bool areInsensitiveToSignednessOfInvertedICmpPredicate(const ConstantRange &CR1, const ConstantRange &CR2)
Return true iff CR1 ult CR2 is equivalent to CR1 sge CR2.
OverflowResult signedAddMayOverflow(const ConstantRange &Other) const
Return whether signed add of the two ranges always/never overflows.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from an addition with wrap type NoWrapK...
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
OverflowResult
Represents whether an operation on the given constant range is known to always or never overflow.
@ AlwaysOverflowsHigh
Always overflows in the direction of signed/unsigned max value.
@ AlwaysOverflowsLow
Always overflows in the direction of signed/unsigned min value.
@ MayOverflow
May or may not overflow.
static bool areInsensitiveToSignednessOfICmpPredicate(const ConstantRange &CR1, const ConstantRange &CR2)
Return true iff CR1 ult CR2 is equivalent to CR1 slt CR2.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
Definition: ConstantRange.h:84
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
ConstantRange smin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed minimum of a value in thi...
ConstantRange udiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned division of a value in...
unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
ConstantRange binaryNot() const
Return a new range representing the possible values resulting from a binary-xor of a value in this ra...
ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
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...
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...
OverflowResult signedSubMayOverflow(const ConstantRange &Other) const
Return whether signed sub of the two ranges always/never overflows.
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
bool isSizeStrictlySmallerThan(const ConstantRange &CR) const
Compare set size of this range with the range CR.
bool isBinaryOp() const
Definition: Instruction.h:173
Metadata node.
Definition: Metadata.h:943
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition: Operator.h:75
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::optional< unsigned > GetMostSignificantDifferentBit(const APInt &A, const APInt &B)
Compare two values, and if they are different, return the position of the most significant bit that i...
Definition: APInt.cpp:2953
APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
Definition: APInt.cpp:2714
APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A sign-divided by B, rounded by the given rounding mode.
Definition: APInt.cpp:2732
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2175
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2180
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2185
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2190
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
@ Offset
Definition: DWP.cpp:406
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ UMin
Unisgned integer min implemented in terms of select(cmp()).
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1862
unsigned countLeadingZeros(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
Definition: MathExtras.h:81
Definition: BitVector.h:851
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
Definition: KnownBits.h:310
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
bool isUnknown() const
Returns true if we don't know any bits.
Definition: KnownBits.h:63
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:47
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:40
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
Definition: KnownBits.h:136
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
Definition: KnownBits.h:120
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:96