LLVM 20.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 if (Known.hasConflict())
62 return getEmpty(Known.getBitWidth());
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 if (isEmptySet() || Other.isEmptySet())
245 return true;
246
247 switch (Pred) {
248 case CmpInst::ICMP_EQ:
249 if (const APInt *L = getSingleElement())
250 if (const APInt *R = Other.getSingleElement())
251 return *L == *R;
252 return false;
253 case CmpInst::ICMP_NE:
254 return inverse().contains(Other);
256 return getUnsignedMax().ult(Other.getUnsignedMin());
258 return getUnsignedMax().ule(Other.getUnsignedMin());
260 return getUnsignedMin().ugt(Other.getUnsignedMax());
262 return getUnsignedMin().uge(Other.getUnsignedMax());
264 return getSignedMax().slt(Other.getSignedMin());
266 return getSignedMax().sle(Other.getSignedMin());
268 return getSignedMin().sgt(Other.getSignedMax());
270 return getSignedMin().sge(Other.getSignedMax());
271 default:
272 llvm_unreachable("Invalid ICmp predicate");
273 }
274}
275
276/// Exact mul nuw region for single element RHS.
278 unsigned BitWidth = V.getBitWidth();
279 if (V == 0)
280 return ConstantRange::getFull(V.getBitWidth());
281
287}
288
289/// Exact mul nsw region for single element RHS.
291 // Handle 0 and -1 separately to avoid division by zero or overflow.
292 unsigned BitWidth = V.getBitWidth();
293 if (V == 0)
294 return ConstantRange::getFull(BitWidth);
295
298 // e.g. Returning [-127, 127], represented as [-127, -128).
299 if (V.isAllOnes())
300 return ConstantRange(-MaxValue, MinValue);
301
303 if (V.isNegative()) {
306 } else {
309 }
311}
312
315 const ConstantRange &Other,
316 unsigned NoWrapKind) {
317 using OBO = OverflowingBinaryOperator;
318
319 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
320
321 assert((NoWrapKind == OBO::NoSignedWrap ||
322 NoWrapKind == OBO::NoUnsignedWrap) &&
323 "NoWrapKind invalid!");
324
325 bool Unsigned = NoWrapKind == OBO::NoUnsignedWrap;
326 unsigned BitWidth = Other.getBitWidth();
327
328 switch (BinOp) {
329 default:
330 llvm_unreachable("Unsupported binary op");
331
332 case Instruction::Add: {
333 if (Unsigned)
334 return getNonEmpty(APInt::getZero(BitWidth), -Other.getUnsignedMax());
335
337 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
338 return getNonEmpty(
339 SMin.isNegative() ? SignedMinVal - SMin : SignedMinVal,
340 SMax.isStrictlyPositive() ? SignedMinVal - SMax : SignedMinVal);
341 }
342
343 case Instruction::Sub: {
344 if (Unsigned)
345 return getNonEmpty(Other.getUnsignedMax(), APInt::getMinValue(BitWidth));
346
348 APInt SMin = Other.getSignedMin(), SMax = Other.getSignedMax();
349 return getNonEmpty(
350 SMax.isStrictlyPositive() ? SignedMinVal + SMax : SignedMinVal,
351 SMin.isNegative() ? SignedMinVal + SMin : SignedMinVal);
352 }
353
354 case Instruction::Mul:
355 if (Unsigned)
356 return makeExactMulNUWRegion(Other.getUnsignedMax());
357
358 // Avoid one makeExactMulNSWRegion() call for the common case of constants.
359 if (const APInt *C = Other.getSingleElement())
360 return makeExactMulNSWRegion(*C);
361
362 return makeExactMulNSWRegion(Other.getSignedMin())
363 .intersectWith(makeExactMulNSWRegion(Other.getSignedMax()));
364
365 case Instruction::Shl: {
366 // For given range of shift amounts, if we ignore all illegal shift amounts
367 // (that always produce poison), what shift amount range is left?
368 ConstantRange ShAmt = Other.intersectWith(
370 if (ShAmt.isEmptySet()) {
371 // If the entire range of shift amounts is already poison-producing,
372 // then we can freely add more poison-producing flags ontop of that.
373 return getFull(BitWidth);
374 }
375 // There are some legal shift amounts, we can compute conservatively-correct
376 // range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax
377 // to be at most bitwidth-1, which results in most conservative range.
378 APInt ShAmtUMax = ShAmt.getUnsignedMax();
379 if (Unsigned)
381 APInt::getMaxValue(BitWidth).lshr(ShAmtUMax) + 1);
383 APInt::getSignedMaxValue(BitWidth).ashr(ShAmtUMax) + 1);
384 }
385 }
386}
387
389 const APInt &Other,
390 unsigned NoWrapKind) {
391 // makeGuaranteedNoWrapRegion() is exact for single-element ranges, as
392 // "for all" and "for any" coincide in this case.
393 return makeGuaranteedNoWrapRegion(BinOp, ConstantRange(Other), NoWrapKind);
394}
395
397 const APInt &C) {
398 unsigned BitWidth = Mask.getBitWidth();
399
400 if ((Mask & C) != C)
401 return getFull(BitWidth);
402
403 if (Mask.isZero())
404 return getEmpty(BitWidth);
405
406 // If (Val & Mask) != C, constrained to the non-equality being
407 // satisfiable, then the value must be larger than the lowest set bit of
408 // Mask, offset by constant C.
410 APInt::getOneBitSet(BitWidth, Mask.countr_zero()) + C, C);
411}
412
414 return Lower == Upper && Lower.isMaxValue();
415}
416
418 return Lower == Upper && Lower.isMinValue();
419}
420
422 return Lower.ugt(Upper) && !Upper.isZero();
423}
424
426 return Lower.ugt(Upper);
427}
428
430 return Lower.sgt(Upper) && !Upper.isMinSignedValue();
431}
432
434 return Lower.sgt(Upper);
435}
436
437bool
439 assert(getBitWidth() == Other.getBitWidth());
440 if (isFullSet())
441 return false;
442 if (Other.isFullSet())
443 return true;
444 return (Upper - Lower).ult(Other.Upper - Other.Lower);
445}
446
447bool
449 // If this a full set, we need special handling to avoid needing an extra bit
450 // to represent the size.
451 if (isFullSet())
452 return MaxSize == 0 || APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
453
454 return (Upper - Lower).ugt(MaxSize);
455}
456
458 // Empty set is all negative, full set is not.
459 if (isEmptySet())
460 return true;
461 if (isFullSet())
462 return false;
463
464 return !isUpperSignWrapped() && !Upper.isStrictlyPositive();
465}
466
468 // Empty and full set are automatically treated correctly.
469 return !isSignWrappedSet() && Lower.isNonNegative();
470}
471
473 // Empty set is all positive, full set is not.
474 if (isEmptySet())
475 return true;
476 if (isFullSet())
477 return false;
478
479 return !isSignWrappedSet() && Lower.isStrictlyPositive();
480}
481
483 if (isFullSet() || isUpperWrapped())
485 return getUpper() - 1;
486}
487
489 if (isFullSet() || isWrappedSet())
491 return getLower();
492}
493
495 if (isFullSet() || isUpperSignWrapped())
497 return getUpper() - 1;
498}
499
501 if (isFullSet() || isSignWrappedSet())
503 return getLower();
504}
505
506bool ConstantRange::contains(const APInt &V) const {
507 if (Lower == Upper)
508 return isFullSet();
509
510 if (!isUpperWrapped())
511 return Lower.ule(V) && V.ult(Upper);
512 return Lower.ule(V) || V.ult(Upper);
513}
514
516 if (isFullSet() || Other.isEmptySet()) return true;
517 if (isEmptySet() || Other.isFullSet()) return false;
518
519 if (!isUpperWrapped()) {
520 if (Other.isUpperWrapped())
521 return false;
522
523 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
524 }
525
526 if (!Other.isUpperWrapped())
527 return Other.getUpper().ule(Upper) ||
528 Lower.ule(Other.getLower());
529
530 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
531}
532
534 if (isEmptySet())
535 return 0;
536
537 return getUnsignedMax().getActiveBits();
538}
539
541 if (isEmptySet())
542 return 0;
543
544 return std::max(getSignedMin().getSignificantBits(),
545 getSignedMax().getSignificantBits());
546}
547
549 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
550 // If the set is empty or full, don't modify the endpoints.
551 if (Lower == Upper)
552 return *this;
553 return ConstantRange(Lower - Val, Upper - Val);
554}
555
557 return intersectWith(CR.inverse());
558}
559
561 const ConstantRange &CR1, const ConstantRange &CR2,
564 if (!CR1.isWrappedSet() && CR2.isWrappedSet())
565 return CR1;
566 if (CR1.isWrappedSet() && !CR2.isWrappedSet())
567 return CR2;
568 } else if (Type == ConstantRange::Signed) {
569 if (!CR1.isSignWrappedSet() && CR2.isSignWrappedSet())
570 return CR1;
571 if (CR1.isSignWrappedSet() && !CR2.isSignWrappedSet())
572 return CR2;
573 }
574
575 if (CR1.isSizeStrictlySmallerThan(CR2))
576 return CR1;
577 return CR2;
578}
579
581 PreferredRangeType Type) const {
582 assert(getBitWidth() == CR.getBitWidth() &&
583 "ConstantRange types don't agree!");
584
585 // Handle common cases.
586 if ( isEmptySet() || CR.isFullSet()) return *this;
587 if (CR.isEmptySet() || isFullSet()) return CR;
588
589 if (!isUpperWrapped() && CR.isUpperWrapped())
590 return CR.intersectWith(*this, Type);
591
592 if (!isUpperWrapped() && !CR.isUpperWrapped()) {
593 if (Lower.ult(CR.Lower)) {
594 // L---U : this
595 // L---U : CR
596 if (Upper.ule(CR.Lower))
597 return getEmpty();
598
599 // L---U : this
600 // L---U : CR
601 if (Upper.ult(CR.Upper))
602 return ConstantRange(CR.Lower, Upper);
603
604 // L-------U : this
605 // L---U : CR
606 return CR;
607 }
608 // L---U : this
609 // L-------U : CR
610 if (Upper.ult(CR.Upper))
611 return *this;
612
613 // L-----U : this
614 // L-----U : CR
615 if (Lower.ult(CR.Upper))
616 return ConstantRange(Lower, CR.Upper);
617
618 // L---U : this
619 // L---U : CR
620 return getEmpty();
621 }
622
623 if (isUpperWrapped() && !CR.isUpperWrapped()) {
624 if (CR.Lower.ult(Upper)) {
625 // ------U L--- : this
626 // L--U : CR
627 if (CR.Upper.ult(Upper))
628 return CR;
629
630 // ------U L--- : this
631 // L------U : CR
632 if (CR.Upper.ule(Lower))
633 return ConstantRange(CR.Lower, Upper);
634
635 // ------U L--- : this
636 // L----------U : CR
637 return getPreferredRange(*this, CR, Type);
638 }
639 if (CR.Lower.ult(Lower)) {
640 // --U L---- : this
641 // L--U : CR
642 if (CR.Upper.ule(Lower))
643 return getEmpty();
644
645 // --U L---- : this
646 // L------U : CR
647 return ConstantRange(Lower, CR.Upper);
648 }
649
650 // --U L------ : this
651 // L--U : CR
652 return CR;
653 }
654
655 if (CR.Upper.ult(Upper)) {
656 // ------U L-- : this
657 // --U L------ : CR
658 if (CR.Lower.ult(Upper))
659 return getPreferredRange(*this, CR, Type);
660
661 // ----U L-- : this
662 // --U L---- : CR
663 if (CR.Lower.ult(Lower))
664 return ConstantRange(Lower, CR.Upper);
665
666 // ----U L---- : this
667 // --U L-- : CR
668 return CR;
669 }
670 if (CR.Upper.ule(Lower)) {
671 // --U L-- : this
672 // ----U L---- : CR
673 if (CR.Lower.ult(Lower))
674 return *this;
675
676 // --U L---- : this
677 // ----U L-- : CR
678 return ConstantRange(CR.Lower, Upper);
679 }
680
681 // --U L------ : this
682 // ------U L-- : CR
683 return getPreferredRange(*this, CR, Type);
684}
685
687 PreferredRangeType Type) const {
688 assert(getBitWidth() == CR.getBitWidth() &&
689 "ConstantRange types don't agree!");
690
691 if ( isFullSet() || CR.isEmptySet()) return *this;
692 if (CR.isFullSet() || isEmptySet()) return CR;
693
694 if (!isUpperWrapped() && CR.isUpperWrapped())
695 return CR.unionWith(*this, Type);
696
697 if (!isUpperWrapped() && !CR.isUpperWrapped()) {
698 // L---U and L---U : this
699 // L---U L---U : CR
700 // result in one of
701 // L---------U
702 // -----U L-----
703 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower))
704 return getPreferredRange(
705 ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
706
707 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
708 APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
709
710 if (L.isZero() && U.isZero())
711 return getFull();
712
713 return ConstantRange(std::move(L), std::move(U));
714 }
715
716 if (!CR.isUpperWrapped()) {
717 // ------U L----- and ------U L----- : this
718 // L--U L--U : CR
719 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
720 return *this;
721
722 // ------U L----- : this
723 // L---------U : CR
724 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
725 return getFull();
726
727 // ----U L---- : this
728 // L---U : CR
729 // results in one of
730 // ----------U L----
731 // ----U L----------
732 if (Upper.ult(CR.Lower) && CR.Upper.ult(Lower))
733 return getPreferredRange(
734 ConstantRange(Lower, CR.Upper), ConstantRange(CR.Lower, Upper), Type);
735
736 // ----U L----- : this
737 // L----U : CR
738 if (Upper.ult(CR.Lower) && Lower.ule(CR.Upper))
739 return ConstantRange(CR.Lower, Upper);
740
741 // ------U L---- : this
742 // L-----U : CR
743 assert(CR.Lower.ule(Upper) && CR.Upper.ult(Lower) &&
744 "ConstantRange::unionWith missed a case with one range wrapped");
745 return ConstantRange(Lower, CR.Upper);
746 }
747
748 // ------U L---- and ------U L---- : this
749 // -U L----------- and ------------U L : CR
750 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
751 return getFull();
752
753 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
754 APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
755
756 return ConstantRange(std::move(L), std::move(U));
757}
758
759std::optional<ConstantRange>
761 // TODO: This can be implemented more efficiently.
762 ConstantRange Result = intersectWith(CR);
763 if (Result == inverse().unionWith(CR.inverse()).inverse())
764 return Result;
765 return std::nullopt;
766}
767
768std::optional<ConstantRange>
770 // TODO: This can be implemented more efficiently.
771 ConstantRange Result = unionWith(CR);
772 if (Result == inverse().intersectWith(CR.inverse()).inverse())
773 return Result;
774 return std::nullopt;
775}
776
778 uint32_t ResultBitWidth) const {
779 switch (CastOp) {
780 default:
781 llvm_unreachable("unsupported cast type");
782 case Instruction::Trunc:
783 return truncate(ResultBitWidth);
784 case Instruction::SExt:
785 return signExtend(ResultBitWidth);
786 case Instruction::ZExt:
787 return zeroExtend(ResultBitWidth);
788 case Instruction::BitCast:
789 return *this;
790 case Instruction::FPToUI:
791 case Instruction::FPToSI:
792 if (getBitWidth() == ResultBitWidth)
793 return *this;
794 else
795 return getFull(ResultBitWidth);
796 case Instruction::UIToFP: {
797 // TODO: use input range if available
798 auto BW = getBitWidth();
799 APInt Min = APInt::getMinValue(BW);
800 APInt Max = APInt::getMaxValue(BW);
801 if (ResultBitWidth > BW) {
802 Min = Min.zext(ResultBitWidth);
803 Max = Max.zext(ResultBitWidth);
804 }
805 return getNonEmpty(std::move(Min), std::move(Max) + 1);
806 }
807 case Instruction::SIToFP: {
808 // TODO: use input range if available
809 auto BW = getBitWidth();
812 if (ResultBitWidth > BW) {
813 SMin = SMin.sext(ResultBitWidth);
814 SMax = SMax.sext(ResultBitWidth);
815 }
816 return getNonEmpty(std::move(SMin), std::move(SMax) + 1);
817 }
818 case Instruction::FPTrunc:
819 case Instruction::FPExt:
820 case Instruction::IntToPtr:
821 case Instruction::PtrToInt:
822 case Instruction::AddrSpaceCast:
823 // Conservatively return getFull set.
824 return getFull(ResultBitWidth);
825 };
826}
827
829 if (isEmptySet()) return getEmpty(DstTySize);
830
831 unsigned SrcTySize = getBitWidth();
832 assert(SrcTySize < DstTySize && "Not a value extension");
833 if (isFullSet() || isUpperWrapped()) {
834 // Change into [0, 1 << src bit width)
835 APInt LowerExt(DstTySize, 0);
836 if (!Upper) // special case: [X, 0) -- not really wrapping around
837 LowerExt = Lower.zext(DstTySize);
838 return ConstantRange(std::move(LowerExt),
839 APInt::getOneBitSet(DstTySize, SrcTySize));
840 }
841
842 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
843}
844
846 if (isEmptySet()) return getEmpty(DstTySize);
847
848 unsigned SrcTySize = getBitWidth();
849 assert(SrcTySize < DstTySize && "Not a value extension");
850
851 // special case: [X, INT_MIN) -- not really wrapping around
852 if (Upper.isMinSignedValue())
853 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
854
855 if (isFullSet() || isSignWrappedSet()) {
856 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
857 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
858 }
859
860 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
861}
862
864 assert(getBitWidth() > DstTySize && "Not a value truncation");
865 if (isEmptySet())
866 return getEmpty(DstTySize);
867 if (isFullSet())
868 return getFull(DstTySize);
869
870 APInt LowerDiv(Lower), UpperDiv(Upper);
871 ConstantRange Union(DstTySize, /*isFullSet=*/false);
872
873 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
874 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
875 // then we do the union with [MaxValue, Upper)
876 if (isUpperWrapped()) {
877 // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
878 // truncated range.
879 if (Upper.getActiveBits() > DstTySize || Upper.countr_one() == DstTySize)
880 return getFull(DstTySize);
881
882 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
883 UpperDiv.setAllBits();
884
885 // Union covers the MaxValue case, so return if the remaining range is just
886 // MaxValue(DstTy).
887 if (LowerDiv == UpperDiv)
888 return Union;
889 }
890
891 // Chop off the most significant bits that are past the destination bitwidth.
892 if (LowerDiv.getActiveBits() > DstTySize) {
893 // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
894 APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
895 LowerDiv -= Adjust;
896 UpperDiv -= Adjust;
897 }
898
899 unsigned UpperDivWidth = UpperDiv.getActiveBits();
900 if (UpperDivWidth <= DstTySize)
901 return ConstantRange(LowerDiv.trunc(DstTySize),
902 UpperDiv.trunc(DstTySize)).unionWith(Union);
903
904 // The truncated value wraps around. Check if we can do better than fullset.
905 if (UpperDivWidth == DstTySize + 1) {
906 // Clear the MSB so that UpperDiv wraps around.
907 UpperDiv.clearBit(DstTySize);
908 if (UpperDiv.ult(LowerDiv))
909 return ConstantRange(LowerDiv.trunc(DstTySize),
910 UpperDiv.trunc(DstTySize)).unionWith(Union);
911 }
912
913 return getFull(DstTySize);
914}
915
917 unsigned SrcTySize = getBitWidth();
918 if (SrcTySize > DstTySize)
919 return truncate(DstTySize);
920 if (SrcTySize < DstTySize)
921 return zeroExtend(DstTySize);
922 return *this;
923}
924
926 unsigned SrcTySize = getBitWidth();
927 if (SrcTySize > DstTySize)
928 return truncate(DstTySize);
929 if (SrcTySize < DstTySize)
930 return signExtend(DstTySize);
931 return *this;
932}
933
935 const ConstantRange &Other) const {
936 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
937
938 switch (BinOp) {
939 case Instruction::Add:
940 return add(Other);
941 case Instruction::Sub:
942 return sub(Other);
943 case Instruction::Mul:
944 return multiply(Other);
945 case Instruction::UDiv:
946 return udiv(Other);
947 case Instruction::SDiv:
948 return sdiv(Other);
949 case Instruction::URem:
950 return urem(Other);
951 case Instruction::SRem:
952 return srem(Other);
953 case Instruction::Shl:
954 return shl(Other);
955 case Instruction::LShr:
956 return lshr(Other);
957 case Instruction::AShr:
958 return ashr(Other);
959 case Instruction::And:
960 return binaryAnd(Other);
961 case Instruction::Or:
962 return binaryOr(Other);
963 case Instruction::Xor:
964 return binaryXor(Other);
965 // Note: floating point operations applied to abstract ranges are just
966 // ideal integer operations with a lossy representation
967 case Instruction::FAdd:
968 return add(Other);
969 case Instruction::FSub:
970 return sub(Other);
971 case Instruction::FMul:
972 return multiply(Other);
973 default:
974 // Conservatively return getFull set.
975 return getFull();
976 }
977}
978
980 const ConstantRange &Other,
981 unsigned NoWrapKind) const {
982 assert(Instruction::isBinaryOp(BinOp) && "Binary operators only!");
983
984 switch (BinOp) {
985 case Instruction::Add:
986 return addWithNoWrap(Other, NoWrapKind);
987 case Instruction::Sub:
988 return subWithNoWrap(Other, NoWrapKind);
989 case Instruction::Mul:
990 return multiplyWithNoWrap(Other, NoWrapKind);
991 case Instruction::Shl:
992 return shlWithNoWrap(Other, NoWrapKind);
993 default:
994 // Don't know about this Overflowing Binary Operation.
995 // Conservatively fallback to plain binop handling.
996 return binaryOp(BinOp, Other);
997 }
998}
999
1001 switch (IntrinsicID) {
1002 case Intrinsic::uadd_sat:
1003 case Intrinsic::usub_sat:
1004 case Intrinsic::sadd_sat:
1005 case Intrinsic::ssub_sat:
1006 case Intrinsic::umin:
1007 case Intrinsic::umax:
1008 case Intrinsic::smin:
1009 case Intrinsic::smax:
1010 case Intrinsic::abs:
1011 case Intrinsic::ctlz:
1012 case Intrinsic::cttz:
1013 case Intrinsic::ctpop:
1014 return true;
1015 default:
1016 return false;
1017 }
1018}
1019
1022 switch (IntrinsicID) {
1023 case Intrinsic::uadd_sat:
1024 return Ops[0].uadd_sat(Ops[1]);
1025 case Intrinsic::usub_sat:
1026 return Ops[0].usub_sat(Ops[1]);
1027 case Intrinsic::sadd_sat:
1028 return Ops[0].sadd_sat(Ops[1]);
1029 case Intrinsic::ssub_sat:
1030 return Ops[0].ssub_sat(Ops[1]);
1031 case Intrinsic::umin:
1032 return Ops[0].umin(Ops[1]);
1033 case Intrinsic::umax:
1034 return Ops[0].umax(Ops[1]);
1035 case Intrinsic::smin:
1036 return Ops[0].smin(Ops[1]);
1037 case Intrinsic::smax:
1038 return Ops[0].smax(Ops[1]);
1039 case Intrinsic::abs: {
1040 const APInt *IntMinIsPoison = Ops[1].getSingleElement();
1041 assert(IntMinIsPoison && "Must be known (immarg)");
1042 assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean");
1043 return Ops[0].abs(IntMinIsPoison->getBoolValue());
1044 }
1045 case Intrinsic::ctlz: {
1046 const APInt *ZeroIsPoison = Ops[1].getSingleElement();
1047 assert(ZeroIsPoison && "Must be known (immarg)");
1048 assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
1049 return Ops[0].ctlz(ZeroIsPoison->getBoolValue());
1050 }
1051 case Intrinsic::cttz: {
1052 const APInt *ZeroIsPoison = Ops[1].getSingleElement();
1053 assert(ZeroIsPoison && "Must be known (immarg)");
1054 assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
1055 return Ops[0].cttz(ZeroIsPoison->getBoolValue());
1056 }
1057 case Intrinsic::ctpop:
1058 return Ops[0].ctpop();
1059 default:
1060 assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported");
1061 llvm_unreachable("Unsupported intrinsic");
1062 }
1063}
1064
1067 if (isEmptySet() || Other.isEmptySet())
1068 return getEmpty();
1069 if (isFullSet() || Other.isFullSet())
1070 return getFull();
1071
1072 APInt NewLower = getLower() + Other.getLower();
1073 APInt NewUpper = getUpper() + Other.getUpper() - 1;
1074 if (NewLower == NewUpper)
1075 return getFull();
1076
1077 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1078 if (X.isSizeStrictlySmallerThan(*this) ||
1079 X.isSizeStrictlySmallerThan(Other))
1080 // We've wrapped, therefore, full set.
1081 return getFull();
1082 return X;
1083}
1084
1086 unsigned NoWrapKind,
1087 PreferredRangeType RangeType) const {
1088 // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
1089 // (X is from this, and Y is from Other)
1090 if (isEmptySet() || Other.isEmptySet())
1091 return getEmpty();
1092 if (isFullSet() && Other.isFullSet())
1093 return getFull();
1094
1095 using OBO = OverflowingBinaryOperator;
1096 ConstantRange Result = add(Other);
1097
1098 // If an overflow happens for every value pair in these two constant ranges,
1099 // we must return Empty set. In this case, we get that for free, because we
1100 // get lucky that intersection of add() with uadd_sat()/sadd_sat() results
1101 // in an empty set.
1102
1103 if (NoWrapKind & OBO::NoSignedWrap)
1104 Result = Result.intersectWith(sadd_sat(Other), RangeType);
1105
1106 if (NoWrapKind & OBO::NoUnsignedWrap)
1107 Result = Result.intersectWith(uadd_sat(Other), RangeType);
1108
1109 return Result;
1110}
1111
1114 if (isEmptySet() || Other.isEmptySet())
1115 return getEmpty();
1116 if (isFullSet() || Other.isFullSet())
1117 return getFull();
1118
1119 APInt NewLower = getLower() - Other.getUpper() + 1;
1120 APInt NewUpper = getUpper() - Other.getLower();
1121 if (NewLower == NewUpper)
1122 return getFull();
1123
1124 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1125 if (X.isSizeStrictlySmallerThan(*this) ||
1126 X.isSizeStrictlySmallerThan(Other))
1127 // We've wrapped, therefore, full set.
1128 return getFull();
1129 return X;
1130}
1131
1133 unsigned NoWrapKind,
1134 PreferredRangeType RangeType) const {
1135 // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).
1136 // (X is from this, and Y is from Other)
1137 if (isEmptySet() || Other.isEmptySet())
1138 return getEmpty();
1139 if (isFullSet() && Other.isFullSet())
1140 return getFull();
1141
1142 using OBO = OverflowingBinaryOperator;
1143 ConstantRange Result = sub(Other);
1144
1145 // If an overflow happens for every value pair in these two constant ranges,
1146 // we must return Empty set. In signed case, we get that for free, because we
1147 // get lucky that intersection of sub() with ssub_sat() results in an
1148 // empty set. But for unsigned we must perform the overflow check manually.
1149
1150 if (NoWrapKind & OBO::NoSignedWrap)
1151 Result = Result.intersectWith(ssub_sat(Other), RangeType);
1152
1153 if (NoWrapKind & OBO::NoUnsignedWrap) {
1154 if (getUnsignedMax().ult(Other.getUnsignedMin()))
1155 return getEmpty(); // Always overflows.
1156 Result = Result.intersectWith(usub_sat(Other), RangeType);
1157 }
1158
1159 return Result;
1160}
1161
1164 // TODO: If either operand is a single element and the multiply is known to
1165 // be non-wrapping, round the result min and max value to the appropriate
1166 // multiple of that element. If wrapping is possible, at least adjust the
1167 // range according to the greatest power-of-two factor of the single element.
1168
1169 if (isEmptySet() || Other.isEmptySet())
1170 return getEmpty();
1171
1172 if (const APInt *C = getSingleElement()) {
1173 if (C->isOne())
1174 return Other;
1175 if (C->isAllOnes())
1177 }
1178
1179 if (const APInt *C = Other.getSingleElement()) {
1180 if (C->isOne())
1181 return *this;
1182 if (C->isAllOnes())
1183 return ConstantRange(APInt::getZero(getBitWidth())).sub(*this);
1184 }
1185
1186 // Multiplication is signedness-independent. However different ranges can be
1187 // obtained depending on how the input ranges are treated. These different
1188 // ranges are all conservatively correct, but one might be better than the
1189 // other. We calculate two ranges; one treating the inputs as unsigned
1190 // and the other signed, then return the smallest of these ranges.
1191
1192 // Unsigned range first.
1193 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
1194 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
1195 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
1196 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
1197
1198 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
1199 this_max * Other_max + 1);
1200 ConstantRange UR = Result_zext.truncate(getBitWidth());
1201
1202 // If the unsigned range doesn't wrap, and isn't negative then it's a range
1203 // from one positive number to another which is as good as we can generate.
1204 // In this case, skip the extra work of generating signed ranges which aren't
1205 // going to be better than this range.
1206 if (!UR.isUpperWrapped() &&
1208 return UR;
1209
1210 // Now the signed range. Because we could be dealing with negative numbers
1211 // here, the lower bound is the smallest of the cartesian product of the
1212 // lower and upper ranges; for example:
1213 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1214 // Similarly for the upper bound, swapping min for max.
1215
1216 this_min = getSignedMin().sext(getBitWidth() * 2);
1217 this_max = getSignedMax().sext(getBitWidth() * 2);
1218 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
1219 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
1220
1221 auto L = {this_min * Other_min, this_min * Other_max,
1222 this_max * Other_min, this_max * Other_max};
1223 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1224 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
1225 ConstantRange SR = Result_sext.truncate(getBitWidth());
1226
1227 return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
1228}
1229
1232 unsigned NoWrapKind,
1233 PreferredRangeType RangeType) const {
1234 if (isEmptySet() || Other.isEmptySet())
1235 return getEmpty();
1236 if (isFullSet() && Other.isFullSet())
1237 return getFull();
1238
1239 ConstantRange Result = multiply(Other);
1240
1242 Result = Result.intersectWith(smul_sat(Other), RangeType);
1243
1245 Result = Result.intersectWith(umul_sat(Other), RangeType);
1246
1247 // mul nsw nuw X, Y s>= 0 if X s> 1 or Y s> 1
1248 if ((NoWrapKind == (OverflowingBinaryOperator::NoSignedWrap |
1250 !Result.isAllNonNegative()) {
1251 if (getSignedMin().sgt(1) || Other.getSignedMin().sgt(1))
1252 Result = Result.intersectWith(
1255 RangeType);
1256 }
1257
1258 return Result;
1259}
1260
1262 if (isEmptySet() || Other.isEmptySet())
1263 return getEmpty();
1264
1265 APInt Min = getSignedMin();
1266 APInt Max = getSignedMax();
1267 APInt OtherMin = Other.getSignedMin();
1268 APInt OtherMax = Other.getSignedMax();
1269
1270 bool O1, O2, O3, O4;
1271 auto Muls = {Min.smul_ov(OtherMin, O1), Min.smul_ov(OtherMax, O2),
1272 Max.smul_ov(OtherMin, O3), Max.smul_ov(OtherMax, O4)};
1273 if (O1 || O2 || O3 || O4)
1274 return getFull();
1275
1276 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1277 return getNonEmpty(std::min(Muls, Compare), std::max(Muls, Compare) + 1);
1278}
1279
1282 // X smax Y is: range(smax(X_smin, Y_smin),
1283 // smax(X_smax, Y_smax))
1284 if (isEmptySet() || Other.isEmptySet())
1285 return getEmpty();
1286 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
1287 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
1288 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1289 if (isSignWrappedSet() || Other.isSignWrappedSet())
1290 return Res.intersectWith(unionWith(Other, Signed), Signed);
1291 return Res;
1292}
1293
1296 // X umax Y is: range(umax(X_umin, Y_umin),
1297 // umax(X_umax, Y_umax))
1298 if (isEmptySet() || Other.isEmptySet())
1299 return getEmpty();
1300 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
1301 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1302 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1303 if (isWrappedSet() || Other.isWrappedSet())
1305 return Res;
1306}
1307
1310 // X smin Y is: range(smin(X_smin, Y_smin),
1311 // smin(X_smax, Y_smax))
1312 if (isEmptySet() || Other.isEmptySet())
1313 return getEmpty();
1314 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
1315 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
1316 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1317 if (isSignWrappedSet() || Other.isSignWrappedSet())
1318 return Res.intersectWith(unionWith(Other, Signed), Signed);
1319 return Res;
1320}
1321
1324 // X umin Y is: range(umin(X_umin, Y_umin),
1325 // umin(X_umax, Y_umax))
1326 if (isEmptySet() || Other.isEmptySet())
1327 return getEmpty();
1328 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
1329 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1330 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1331 if (isWrappedSet() || Other.isWrappedSet())
1333 return Res;
1334}
1335
1338 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1339 return getEmpty();
1340
1341 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
1342
1343 APInt RHS_umin = RHS.getUnsignedMin();
1344 if (RHS_umin.isZero()) {
1345 // We want the lowest value in RHS excluding zero. Usually that would be 1
1346 // except for a range in the form of [X, 1) in which case it would be X.
1347 if (RHS.getUpper() == 1)
1348 RHS_umin = RHS.getLower();
1349 else
1350 RHS_umin = 1;
1351 }
1352
1353 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
1354 return getNonEmpty(std::move(Lower), std::move(Upper));
1355}
1356
1358 // We split up the LHS and RHS into positive and negative components
1359 // and then also compute the positive and negative components of the result
1360 // separately by combining division results with the appropriate signs.
1363 // There are no positive 1-bit values. The 1 would get interpreted as -1.
1364 ConstantRange PosFilter =
1365 getBitWidth() == 1 ? getEmpty()
1366 : ConstantRange(APInt(getBitWidth(), 1), SignedMin);
1367 ConstantRange NegFilter(SignedMin, Zero);
1368 ConstantRange PosL = intersectWith(PosFilter);
1369 ConstantRange NegL = intersectWith(NegFilter);
1370 ConstantRange PosR = RHS.intersectWith(PosFilter);
1371 ConstantRange NegR = RHS.intersectWith(NegFilter);
1372
1373 ConstantRange PosRes = getEmpty();
1374 if (!PosL.isEmptySet() && !PosR.isEmptySet())
1375 // pos / pos = pos.
1376 PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),
1377 (PosL.Upper - 1).sdiv(PosR.Lower) + 1);
1378
1379 if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1380 // neg / neg = pos.
1381 //
1382 // We need to deal with one tricky case here: SignedMin / -1 is UB on the
1383 // IR level, so we'll want to exclude this case when calculating bounds.
1384 // (For APInts the operation is well-defined and yields SignedMin.) We
1385 // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1386 APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);
1387 if (NegL.Lower.isMinSignedValue() && NegR.Upper.isZero()) {
1388 // Remove -1 from the LHS. Skip if it's the only element, as this would
1389 // leave us with an empty set.
1390 if (!NegR.Lower.isAllOnes()) {
1391 APInt AdjNegRUpper;
1392 if (RHS.Lower.isAllOnes())
1393 // Negative part of [-1, X] without -1 is [SignedMin, X].
1394 AdjNegRUpper = RHS.Upper;
1395 else
1396 // [X, -1] without -1 is [X, -2].
1397 AdjNegRUpper = NegR.Upper - 1;
1398
1399 PosRes = PosRes.unionWith(
1400 ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
1401 }
1402
1403 // Remove SignedMin from the RHS. Skip if it's the only element, as this
1404 // would leave us with an empty set.
1405 if (NegL.Upper != SignedMin + 1) {
1406 APInt AdjNegLLower;
1407 if (Upper == SignedMin + 1)
1408 // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1409 AdjNegLLower = Lower;
1410 else
1411 // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1412 AdjNegLLower = NegL.Lower + 1;
1413
1414 PosRes = PosRes.unionWith(
1415 ConstantRange(std::move(Lo),
1416 AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
1417 }
1418 } else {
1419 PosRes = PosRes.unionWith(
1420 ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
1421 }
1422 }
1423
1424 ConstantRange NegRes = getEmpty();
1425 if (!PosL.isEmptySet() && !NegR.isEmptySet())
1426 // pos / neg = neg.
1427 NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
1428 PosL.Lower.sdiv(NegR.Lower) + 1);
1429
1430 if (!NegL.isEmptySet() && !PosR.isEmptySet())
1431 // neg / pos = neg.
1432 NegRes = NegRes.unionWith(
1433 ConstantRange(NegL.Lower.sdiv(PosR.Lower),
1434 (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));
1435
1436 // Prefer a non-wrapping signed range here.
1438
1439 // Preserve the zero that we dropped when splitting the LHS by sign.
1440 if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1441 Res = Res.unionWith(ConstantRange(Zero));
1442 return Res;
1443}
1444
1446 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1447 return getEmpty();
1448
1449 if (const APInt *RHSInt = RHS.getSingleElement()) {
1450 // UREM by null is UB.
1451 if (RHSInt->isZero())
1452 return getEmpty();
1453 // Use APInt's implementation of UREM for single element ranges.
1454 if (const APInt *LHSInt = getSingleElement())
1455 return {LHSInt->urem(*RHSInt)};
1456 }
1457
1458 // L % R for L < R is L.
1459 if (getUnsignedMax().ult(RHS.getUnsignedMin()))
1460 return *this;
1461
1462 // L % R is <= L and < R.
1463 APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
1464 return getNonEmpty(APInt::getZero(getBitWidth()), std::move(Upper));
1465}
1466
1468 if (isEmptySet() || RHS.isEmptySet())
1469 return getEmpty();
1470
1471 if (const APInt *RHSInt = RHS.getSingleElement()) {
1472 // SREM by null is UB.
1473 if (RHSInt->isZero())
1474 return getEmpty();
1475 // Use APInt's implementation of SREM for single element ranges.
1476 if (const APInt *LHSInt = getSingleElement())
1477 return {LHSInt->srem(*RHSInt)};
1478 }
1479
1480 ConstantRange AbsRHS = RHS.abs();
1481 APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1482 APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1483
1484 // Modulus by zero is UB.
1485 if (MaxAbsRHS.isZero())
1486 return getEmpty();
1487
1488 if (MinAbsRHS.isZero())
1489 ++MinAbsRHS;
1490
1491 APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1492
1493 if (MinLHS.isNonNegative()) {
1494 // L % R for L < R is L.
1495 if (MaxLHS.ult(MinAbsRHS))
1496 return *this;
1497
1498 // L % R is <= L and < R.
1499 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1500 return ConstantRange(APInt::getZero(getBitWidth()), std::move(Upper));
1501 }
1502
1503 // Same basic logic as above, but the result is negative.
1504 if (MaxLHS.isNegative()) {
1505 if (MinLHS.ugt(-MinAbsRHS))
1506 return *this;
1507
1508 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1509 return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1510 }
1511
1512 // LHS range crosses zero.
1513 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1514 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1515 return ConstantRange(std::move(Lower), std::move(Upper));
1516}
1517
1520}
1521
1523 if (isEmptySet() || Other.isEmptySet())
1524 return getEmpty();
1525
1526 ConstantRange KnownBitsRange =
1527 fromKnownBits(toKnownBits() & Other.toKnownBits(), false);
1528 ConstantRange UMinUMaxRange =
1530 APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()) + 1);
1531 return KnownBitsRange.intersectWith(UMinUMaxRange);
1532}
1533
1535 if (isEmptySet() || Other.isEmptySet())
1536 return getEmpty();
1537
1538 ConstantRange KnownBitsRange =
1539 fromKnownBits(toKnownBits() | Other.toKnownBits(), false);
1540 // Upper wrapped range.
1541 ConstantRange UMaxUMinRange =
1542 getNonEmpty(APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()),
1544 return KnownBitsRange.intersectWith(UMaxUMinRange);
1545}
1546
1548 if (isEmptySet() || Other.isEmptySet())
1549 return getEmpty();
1550
1551 // Use APInt's implementation of XOR for single element ranges.
1552 if (isSingleElement() && Other.isSingleElement())
1553 return {*getSingleElement() ^ *Other.getSingleElement()};
1554
1555 // Special-case binary complement, since we can give a precise answer.
1556 if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes())
1557 return binaryNot();
1558 if (isSingleElement() && getSingleElement()->isAllOnes())
1559 return Other.binaryNot();
1560
1561 KnownBits LHSKnown = toKnownBits();
1562 KnownBits RHSKnown = Other.toKnownBits();
1563 KnownBits Known = LHSKnown ^ RHSKnown;
1564 ConstantRange CR = fromKnownBits(Known, /*IsSigned*/ false);
1565 // Typically the following code doesn't improve the result if BW = 1.
1566 if (getBitWidth() == 1)
1567 return CR;
1568
1569 // If LHS is known to be the subset of RHS, treat LHS ^ RHS as RHS -nuw/nsw
1570 // LHS. If RHS is known to be the subset of LHS, treat LHS ^ RHS as LHS
1571 // -nuw/nsw RHS.
1572 if ((~LHSKnown.Zero).isSubsetOf(RHSKnown.One))
1574 else if ((~RHSKnown.Zero).isSubsetOf(LHSKnown.One))
1575 CR = CR.intersectWith(this->sub(Other), PreferredRangeType::Unsigned);
1576 return CR;
1577}
1578
1581 if (isEmptySet() || Other.isEmptySet())
1582 return getEmpty();
1583
1584 APInt Min = getUnsignedMin();
1585 APInt Max = getUnsignedMax();
1586 if (const APInt *RHS = Other.getSingleElement()) {
1587 unsigned BW = getBitWidth();
1588 if (RHS->uge(BW))
1589 return getEmpty();
1590
1591 unsigned EqualLeadingBits = (Min ^ Max).countl_zero();
1592 if (RHS->ule(EqualLeadingBits))
1593 return getNonEmpty(Min << *RHS, (Max << *RHS) + 1);
1594
1595 return getNonEmpty(APInt::getZero(BW),
1596 APInt::getBitsSetFrom(BW, RHS->getZExtValue()) + 1);
1597 }
1598
1599 APInt OtherMax = Other.getUnsignedMax();
1600 if (isAllNegative() && OtherMax.ule(Min.countl_one())) {
1601 // For negative numbers, if the shift does not overflow in a signed sense,
1602 // a larger shift will make the number smaller.
1603 Max <<= Other.getUnsignedMin();
1604 Min <<= OtherMax;
1605 return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1);
1606 }
1607
1608 // There's overflow!
1609 if (OtherMax.ugt(Max.countl_zero()))
1610 return getFull();
1611
1612 // FIXME: implement the other tricky cases
1613
1614 Min <<= Other.getUnsignedMin();
1615 Max <<= OtherMax;
1616
1617 return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1);
1618}
1619
1621 const ConstantRange &RHS) {
1622 unsigned BitWidth = LHS.getBitWidth();
1623 bool Overflow;
1624 APInt LHSMin = LHS.getUnsignedMin();
1625 unsigned RHSMin = RHS.getUnsignedMin().getLimitedValue(BitWidth);
1626 APInt MinShl = LHSMin.ushl_ov(RHSMin, Overflow);
1627 if (Overflow)
1628 return ConstantRange::getEmpty(BitWidth);
1629 APInt LHSMax = LHS.getUnsignedMax();
1630 unsigned RHSMax = RHS.getUnsignedMax().getLimitedValue(BitWidth);
1631 APInt MaxShl = MinShl;
1632 unsigned MaxShAmt = LHSMax.countLeadingZeros();
1633 if (RHSMin <= MaxShAmt)
1634 MaxShl = LHSMax << std::min(RHSMax, MaxShAmt);
1635 RHSMin = std::max(RHSMin, MaxShAmt + 1);
1636 RHSMax = std::min(RHSMax, LHSMin.countLeadingZeros());
1637 if (RHSMin <= RHSMax)
1638 MaxShl = APIntOps::umax(MaxShl,
1640 return ConstantRange::getNonEmpty(MinShl, MaxShl + 1);
1641}
1642
1644 const APInt &LHSMax,
1645 unsigned RHSMin,
1646 unsigned RHSMax) {
1647 unsigned BitWidth = LHSMin.getBitWidth();
1648 bool Overflow;
1649 APInt MinShl = LHSMin.sshl_ov(RHSMin, Overflow);
1650 if (Overflow)
1651 return ConstantRange::getEmpty(BitWidth);
1652 APInt MaxShl = MinShl;
1653 unsigned MaxShAmt = LHSMax.countLeadingZeros() - 1;
1654 if (RHSMin <= MaxShAmt)
1655 MaxShl = LHSMax << std::min(RHSMax, MaxShAmt);
1656 RHSMin = std::max(RHSMin, MaxShAmt + 1);
1657 RHSMax = std::min(RHSMax, LHSMin.countLeadingZeros() - 1);
1658 if (RHSMin <= RHSMax)
1659 MaxShl = APIntOps::umax(MaxShl,
1660 APInt::getBitsSet(BitWidth, RHSMin, BitWidth - 1));
1661 return ConstantRange::getNonEmpty(MinShl, MaxShl + 1);
1662}
1663
1665 const APInt &LHSMax,
1666 unsigned RHSMin, unsigned RHSMax) {
1667 unsigned BitWidth = LHSMin.getBitWidth();
1668 bool Overflow;
1669 APInt MaxShl = LHSMax.sshl_ov(RHSMin, Overflow);
1670 if (Overflow)
1671 return ConstantRange::getEmpty(BitWidth);
1672 APInt MinShl = MaxShl;
1673 unsigned MaxShAmt = LHSMin.countLeadingOnes() - 1;
1674 if (RHSMin <= MaxShAmt)
1675 MinShl = LHSMin.shl(std::min(RHSMax, MaxShAmt));
1676 RHSMin = std::max(RHSMin, MaxShAmt + 1);
1677 RHSMax = std::min(RHSMax, LHSMax.countLeadingOnes() - 1);
1678 if (RHSMin <= RHSMax)
1679 MinShl = APInt::getSignMask(BitWidth);
1680 return ConstantRange::getNonEmpty(MinShl, MaxShl + 1);
1681}
1682
1684 const ConstantRange &RHS) {
1685 unsigned BitWidth = LHS.getBitWidth();
1686 unsigned RHSMin = RHS.getUnsignedMin().getLimitedValue(BitWidth);
1687 unsigned RHSMax = RHS.getUnsignedMax().getLimitedValue(BitWidth);
1688 APInt LHSMin = LHS.getSignedMin();
1689 APInt LHSMax = LHS.getSignedMax();
1690 if (LHSMin.isNonNegative())
1691 return computeShlNSWWithNNegLHS(LHSMin, LHSMax, RHSMin, RHSMax);
1692 else if (LHSMax.isNegative())
1693 return computeShlNSWWithNegLHS(LHSMin, LHSMax, RHSMin, RHSMax);
1694 return computeShlNSWWithNNegLHS(APInt::getZero(BitWidth), LHSMax, RHSMin,
1695 RHSMax)
1697 RHSMin, RHSMax),
1699}
1700
1702 unsigned NoWrapKind,
1703 PreferredRangeType RangeType) const {
1704 if (isEmptySet() || Other.isEmptySet())
1705 return getEmpty();
1706
1707 switch (NoWrapKind) {
1708 case 0:
1709 return shl(Other);
1711 return computeShlNSW(*this, Other);
1713 return computeShlNUW(*this, Other);
1716 return computeShlNSW(*this, Other)
1717 .intersectWith(computeShlNUW(*this, Other), RangeType);
1718 default:
1719 llvm_unreachable("Invalid NoWrapKind");
1720 }
1721}
1722
1725 if (isEmptySet() || Other.isEmptySet())
1726 return getEmpty();
1727
1728 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1729 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1730 return getNonEmpty(std::move(min), std::move(max));
1731}
1732
1735 if (isEmptySet() || Other.isEmptySet())
1736 return getEmpty();
1737
1738 // May straddle zero, so handle both positive and negative cases.
1739 // 'PosMax' is the upper bound of the result of the ashr
1740 // operation, when Upper of the LHS of ashr is a non-negative.
1741 // number. Since ashr of a non-negative number will result in a
1742 // smaller number, the Upper value of LHS is shifted right with
1743 // the minimum value of 'Other' instead of the maximum value.
1744 APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1745
1746 // 'PosMin' is the lower bound of the result of the ashr
1747 // operation, when Lower of the LHS is a non-negative number.
1748 // Since ashr of a non-negative number will result in a smaller
1749 // number, the Lower value of LHS is shifted right with the
1750 // maximum value of 'Other'.
1751 APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1752
1753 // 'NegMax' is the upper bound of the result of the ashr
1754 // operation, when Upper of the LHS of ashr is a negative number.
1755 // Since 'ashr' of a negative number will result in a bigger
1756 // number, the Upper value of LHS is shifted right with the
1757 // maximum value of 'Other'.
1758 APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1759
1760 // 'NegMin' is the lower bound of the result of the ashr
1761 // operation, when Lower of the LHS of ashr is a negative number.
1762 // Since 'ashr' of a negative number will result in a bigger
1763 // number, the Lower value of LHS is shifted right with the
1764 // minimum value of 'Other'.
1765 APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1766
1767 APInt max, min;
1768 if (getSignedMin().isNonNegative()) {
1769 // Upper and Lower of LHS are non-negative.
1770 min = PosMin;
1771 max = PosMax;
1772 } else if (getSignedMax().isNegative()) {
1773 // Upper and Lower of LHS are negative.
1774 min = NegMin;
1775 max = NegMax;
1776 } else {
1777 // Upper is non-negative and Lower is negative.
1778 min = NegMin;
1779 max = PosMax;
1780 }
1781 return getNonEmpty(std::move(min), std::move(max));
1782}
1783
1785 if (isEmptySet() || Other.isEmptySet())
1786 return getEmpty();
1787
1788 APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());
1789 APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;
1790 return getNonEmpty(std::move(NewL), std::move(NewU));
1791}
1792
1794 if (isEmptySet() || Other.isEmptySet())
1795 return getEmpty();
1796
1797 APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());
1798 APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;
1799 return getNonEmpty(std::move(NewL), std::move(NewU));
1800}
1801
1803 if (isEmptySet() || Other.isEmptySet())
1804 return getEmpty();
1805
1806 APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());
1807 APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;
1808 return getNonEmpty(std::move(NewL), std::move(NewU));
1809}
1810
1812 if (isEmptySet() || Other.isEmptySet())
1813 return getEmpty();
1814
1815 APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
1816 APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
1817 return getNonEmpty(std::move(NewL), std::move(NewU));
1818}
1819
1821 if (isEmptySet() || Other.isEmptySet())
1822 return getEmpty();
1823
1824 APInt NewL = getUnsignedMin().umul_sat(Other.getUnsignedMin());
1825 APInt NewU = getUnsignedMax().umul_sat(Other.getUnsignedMax()) + 1;
1826 return getNonEmpty(std::move(NewL), std::move(NewU));
1827}
1828
1830 if (isEmptySet() || Other.isEmptySet())
1831 return getEmpty();
1832
1833 // Because we could be dealing with negative numbers here, the lower bound is
1834 // the smallest of the cartesian product of the lower and upper ranges;
1835 // for example:
1836 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1837 // Similarly for the upper bound, swapping min for max.
1838
1839 APInt Min = getSignedMin();
1840 APInt Max = getSignedMax();
1841 APInt OtherMin = Other.getSignedMin();
1842 APInt OtherMax = Other.getSignedMax();
1843
1844 auto L = {Min.smul_sat(OtherMin), Min.smul_sat(OtherMax),
1845 Max.smul_sat(OtherMin), Max.smul_sat(OtherMax)};
1846 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1847 return getNonEmpty(std::min(L, Compare), std::max(L, Compare) + 1);
1848}
1849
1851 if (isEmptySet() || Other.isEmptySet())
1852 return getEmpty();
1853
1854 APInt NewL = getUnsignedMin().ushl_sat(Other.getUnsignedMin());
1855 APInt NewU = getUnsignedMax().ushl_sat(Other.getUnsignedMax()) + 1;
1856 return getNonEmpty(std::move(NewL), std::move(NewU));
1857}
1858
1860 if (isEmptySet() || Other.isEmptySet())
1861 return getEmpty();
1862
1863 APInt Min = getSignedMin(), Max = getSignedMax();
1864 APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax();
1865 APInt NewL = Min.sshl_sat(Min.isNonNegative() ? ShAmtMin : ShAmtMax);
1866 APInt NewU = Max.sshl_sat(Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;
1867 return getNonEmpty(std::move(NewL), std::move(NewU));
1868}
1869
1871 if (isFullSet())
1872 return getEmpty();
1873 if (isEmptySet())
1874 return getFull();
1875 return ConstantRange(Upper, Lower);
1876}
1877
1878ConstantRange ConstantRange::abs(bool IntMinIsPoison) const {
1879 if (isEmptySet())
1880 return getEmpty();
1881
1882 if (isSignWrappedSet()) {
1883 APInt Lo;
1884 // Check whether the range crosses zero.
1885 if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1887 else
1888 Lo = APIntOps::umin(Lower, -Upper + 1);
1889
1890 // If SignedMin is not poison, then it is included in the result range.
1891 if (IntMinIsPoison)
1893 else
1895 }
1896
1898
1899 // Skip SignedMin if it is poison.
1900 if (IntMinIsPoison && SMin.isMinSignedValue()) {
1901 // The range may become empty if it *only* contains SignedMin.
1902 if (SMax.isMinSignedValue())
1903 return getEmpty();
1904 ++SMin;
1905 }
1906
1907 // All non-negative.
1908 if (SMin.isNonNegative())
1909 return ConstantRange(SMin, SMax + 1);
1910
1911 // All negative.
1912 if (SMax.isNegative())
1913 return ConstantRange(-SMax, -SMin + 1);
1914
1915 // Range crosses zero.
1917 APIntOps::umax(-SMin, SMax) + 1);
1918}
1919
1920ConstantRange ConstantRange::ctlz(bool ZeroIsPoison) const {
1921 if (isEmptySet())
1922 return getEmpty();
1923
1925 if (ZeroIsPoison && contains(Zero)) {
1926 // ZeroIsPoison is set, and zero is contained. We discern three cases, in
1927 // which a zero can appear:
1928 // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
1929 // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
1930 // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
1931
1932 if (getLower().isZero()) {
1933 if ((getUpper() - 1).isZero()) {
1934 // We have in input interval of kind [0, 1). In this case we cannot
1935 // really help but return empty-set.
1936 return getEmpty();
1937 }
1938
1939 // Compute the resulting range by excluding zero from Lower.
1940 return ConstantRange(
1941 APInt(getBitWidth(), (getUpper() - 1).countl_zero()),
1942 APInt(getBitWidth(), (getLower() + 1).countl_zero() + 1));
1943 } else if ((getUpper() - 1).isZero()) {
1944 // Compute the resulting range by excluding zero from Upper.
1945 return ConstantRange(Zero,
1947 } else {
1948 return ConstantRange(Zero, APInt(getBitWidth(), getBitWidth()));
1949 }
1950 }
1951
1952 // Zero is either safe or not in the range. The output range is composed by
1953 // the result of countLeadingZero of the two extremes.
1956}
1957
1959 const APInt &Upper) {
1960 assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
1961 "Unexpected wrapped set.");
1962 assert(Lower != Upper && "Unexpected empty set.");
1963 unsigned BitWidth = Lower.getBitWidth();
1964 if (Lower + 1 == Upper)
1965 return ConstantRange(APInt(BitWidth, Lower.countr_zero()));
1966 if (Lower.isZero())
1968 APInt(BitWidth, BitWidth + 1));
1969
1970 // Calculate longest common prefix.
1971 unsigned LCPLength = (Lower ^ (Upper - 1)).countl_zero();
1972 // If Lower is {LCP, 000...}, the maximum is Lower.countr_zero().
1973 // Otherwise, the maximum is BitWidth - LCPLength - 1 ({LCP, 100...}).
1974 return ConstantRange(
1977 std::max(BitWidth - LCPLength - 1, Lower.countr_zero()) + 1));
1978}
1979
1980ConstantRange ConstantRange::cttz(bool ZeroIsPoison) const {
1981 if (isEmptySet())
1982 return getEmpty();
1983
1984 unsigned BitWidth = getBitWidth();
1986 if (ZeroIsPoison && contains(Zero)) {
1987 // ZeroIsPoison is set, and zero is contained. We discern three cases, in
1988 // which a zero can appear:
1989 // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
1990 // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
1991 // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
1992
1993 if (Lower.isZero()) {
1994 if (Upper == 1) {
1995 // We have in input interval of kind [0, 1). In this case we cannot
1996 // really help but return empty-set.
1997 return getEmpty();
1998 }
1999
2000 // Compute the resulting range by excluding zero from Lower.
2002 } else if (Upper == 1) {
2003 // Compute the resulting range by excluding zero from Upper.
2004 return getUnsignedCountTrailingZerosRange(Lower, Zero);
2005 } else {
2007 ConstantRange CR2 =
2009 return CR1.unionWith(CR2);
2010 }
2011 }
2012
2013 if (isFullSet())
2014 return getNonEmpty(Zero, APInt(BitWidth, BitWidth + 1));
2015 if (!isWrappedSet())
2016 return getUnsignedCountTrailingZerosRange(Lower, Upper);
2017 // The range is wrapped. We decompose it into two ranges, [0, Upper) and
2018 // [Lower, 0).
2019 // Handle [Lower, 0)
2021 // Handle [0, Upper)
2023 return CR1.unionWith(CR2);
2024}
2025
2027 const APInt &Upper) {
2028 assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
2029 "Unexpected wrapped set.");
2030 assert(Lower != Upper && "Unexpected empty set.");
2031 unsigned BitWidth = Lower.getBitWidth();
2032 if (Lower + 1 == Upper)
2033 return ConstantRange(APInt(BitWidth, Lower.popcount()));
2034
2035 APInt Max = Upper - 1;
2036 // Calculate longest common prefix.
2037 unsigned LCPLength = (Lower ^ Max).countl_zero();
2038 unsigned LCPPopCount = Lower.getHiBits(LCPLength).popcount();
2039 // If Lower is {LCP, 000...}, the minimum is the popcount of LCP.
2040 // Otherwise, the minimum is the popcount of LCP + 1.
2041 unsigned MinBits =
2042 LCPPopCount + (Lower.countr_zero() < BitWidth - LCPLength ? 1 : 0);
2043 // If Max is {LCP, 111...}, the maximum is the popcount of LCP + (BitWidth -
2044 // length of LCP).
2045 // Otherwise, the minimum is the popcount of LCP + (BitWidth -
2046 // length of LCP - 1).
2047 unsigned MaxBits = LCPPopCount + (BitWidth - LCPLength) -
2048 (Max.countr_one() < BitWidth - LCPLength ? 1 : 0);
2049 return ConstantRange(APInt(BitWidth, MinBits), APInt(BitWidth, MaxBits + 1));
2050}
2051
2053 if (isEmptySet())
2054 return getEmpty();
2055
2056 unsigned BitWidth = getBitWidth();
2058 if (isFullSet())
2059 return getNonEmpty(Zero, APInt(BitWidth, BitWidth + 1));
2060 if (!isWrappedSet())
2061 return getUnsignedPopCountRange(Lower, Upper);
2062 // The range is wrapped. We decompose it into two ranges, [0, Upper) and
2063 // [Lower, 0).
2064 // Handle [Lower, 0) == [Lower, Max]
2066 APInt(BitWidth, BitWidth + 1));
2067 // Handle [0, Upper)
2068 ConstantRange CR2 = getUnsignedPopCountRange(Zero, Upper);
2069 return CR1.unionWith(CR2);
2070}
2071
2073 const ConstantRange &Other) const {
2074 if (isEmptySet() || Other.isEmptySet())
2076
2077 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2078 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2079
2080 // a u+ b overflows high iff a u> ~b.
2081 if (Min.ugt(~OtherMin))
2083 if (Max.ugt(~OtherMax))
2086}
2087
2089 const ConstantRange &Other) const {
2090 if (isEmptySet() || Other.isEmptySet())
2092
2093 APInt Min = getSignedMin(), Max = getSignedMax();
2094 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
2095
2098
2099 // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
2100 // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
2101 if (Min.isNonNegative() && OtherMin.isNonNegative() &&
2102 Min.sgt(SignedMax - OtherMin))
2104 if (Max.isNegative() && OtherMax.isNegative() &&
2105 Max.slt(SignedMin - OtherMax))
2107
2108 if (Max.isNonNegative() && OtherMax.isNonNegative() &&
2109 Max.sgt(SignedMax - OtherMax))
2111 if (Min.isNegative() && OtherMin.isNegative() &&
2112 Min.slt(SignedMin - OtherMin))
2114
2116}
2117
2119 const ConstantRange &Other) const {
2120 if (isEmptySet() || Other.isEmptySet())
2122
2123 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2124 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2125
2126 // a u- b overflows low iff a u< b.
2127 if (Max.ult(OtherMin))
2129 if (Min.ult(OtherMax))
2132}
2133
2135 const ConstantRange &Other) const {
2136 if (isEmptySet() || Other.isEmptySet())
2138
2139 APInt Min = getSignedMin(), Max = getSignedMax();
2140 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
2141
2144
2145 // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
2146 // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
2147 if (Min.isNonNegative() && OtherMax.isNegative() &&
2148 Min.sgt(SignedMax + OtherMax))
2150 if (Max.isNegative() && OtherMin.isNonNegative() &&
2151 Max.slt(SignedMin + OtherMin))
2153
2154 if (Max.isNonNegative() && OtherMin.isNegative() &&
2155 Max.sgt(SignedMax + OtherMin))
2157 if (Min.isNegative() && OtherMax.isNonNegative() &&
2158 Min.slt(SignedMin + OtherMax))
2160
2162}
2163
2165 const ConstantRange &Other) const {
2166 if (isEmptySet() || Other.isEmptySet())
2168
2169 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2170 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2171 bool Overflow;
2172
2173 (void) Min.umul_ov(OtherMin, Overflow);
2174 if (Overflow)
2176
2177 (void) Max.umul_ov(OtherMax, Overflow);
2178 if (Overflow)
2180
2182}
2183
2185 if (isFullSet())
2186 OS << "full-set";
2187 else if (isEmptySet())
2188 OS << "empty-set";
2189 else
2190 OS << "[" << Lower << "," << Upper << ")";
2191}
2192
2193#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2195 print(dbgs());
2196}
2197#endif
2198
2200 const unsigned NumRanges = Ranges.getNumOperands() / 2;
2201 assert(NumRanges >= 1 && "Must have at least one range!");
2202 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
2203
2204 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
2205 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
2206
2207 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
2208
2209 for (unsigned i = 1; i < NumRanges; ++i) {
2210 auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
2211 auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
2212
2213 // Note: unionWith will potentially create a range that contains values not
2214 // contained in any of the original N ranges.
2215 CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
2216 }
2217
2218 return CR;
2219}
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:537
static ConstantRange computeShlNUW(const ConstantRange &LHS, const ConstantRange &RHS)
static ConstantRange getUnsignedPopCountRange(const APInt &Lower, const APInt &Upper)
static ConstantRange computeShlNSW(const ConstantRange &LHS, const ConstantRange &RHS)
static ConstantRange makeExactMulNUWRegion(const APInt &V)
Exact mul nuw region for single element RHS.
static ConstantRange computeShlNSWWithNNegLHS(const APInt &LHSMin, const APInt &LHSMax, unsigned RHSMin, unsigned RHSMax)
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)
static ConstantRange getUnsignedCountTrailingZerosRange(const APInt &Lower, const APInt &Upper)
static ConstantRange computeShlNSWWithNegLHS(const APInt &LHSMin, const APInt &LHSMax, unsigned RHSMin, unsigned RHSMax)
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")
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:512
This file contains the declarations for metadata subclasses.
uint64_t High
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:78
APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1941
APInt usub_sat(const APInt &RHS) const
Definition: APInt.cpp:2025
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1543
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:212
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:981
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:207
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:401
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1470
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:906
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:184
APInt sshl_ov(const APInt &Amt, bool &Overflow) const
Definition: APInt.cpp:1958
APInt smul_sat(const APInt &RHS) const
Definition: APInt.cpp:2034
unsigned countLeadingOnes() const
Definition: APInt.h:1581
APInt sadd_sat(const APInt &RHS) const
Definition: APInt.cpp:1996
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:349
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1160
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit)
Get a value with a block of bits set.
Definition: APInt.h:236
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:358
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1446
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:187
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:395
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:194
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:307
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition: APInt.cpp:1614
bool sle(const APInt &RHS) const
Signed less or equal comparison.
Definition: APInt.h:1144
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:197
APInt sshl_sat(const APInt &RHS) const
Definition: APInt.cpp:2056
APInt ushl_sat(const APInt &RHS) const
Definition: APInt.cpp:2070
APInt ushl_ov(const APInt &Amt, bool &Overflow) const
Definition: APInt.cpp:1975
unsigned countLeadingZeros() const
Definition: APInt.h:1563
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
Definition: APInt.h:334
unsigned countl_one() const
Count the number of leading one bits.
Definition: APInt.h:1572
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
Definition: APInt.h:1395
APInt uadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2006
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:805
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1297
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:449
APInt smul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1930
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:312
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:954
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:851
APInt umul_sat(const APInt &RHS) const
Definition: APInt.cpp:2047
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:284
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:274
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:178
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition: APInt.h:1215
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:264
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:217
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:829
unsigned countr_one() const
Count the number of trailing one bits.
Definition: APInt.h:1613
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:1409
APInt ssub_sat(const APInt &RHS) const
Definition: APInt.cpp:2015
bool isMaxValue() const
Determine if this is the largest unsigned value.
Definition: APInt.h:377
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:757
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:786
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:787
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:781
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:780
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:784
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:782
@ ICMP_EQ
equal
Definition: InstrTypes.h:778
@ ICMP_NE
not equal
Definition: InstrTypes.h:779
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:785
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:783
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:871
Predicate getFlippedSignednessPredicate()
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->Failed assert.
Definition: InstrTypes.h:1050
bool isIntPredicate() const
Definition: InstrTypes.h:865
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
Definition: InstrTypes.h:1003
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.
bool isAllPositive() const
Return true if all values in this range are positive.
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 shlWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from a left shift with wrap type NoWrap...
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 ConstantRange makeMaskNotEqualRange(const APInt &Mask, const APInt &C)
Initialize a range containing all values X that satisfy (X & Mask) != C.
static bool areInsensitiveToSignednessOfICmpPredicate(const ConstantRange &CR1, const ConstantRange &CR2)
Return true iff CR1 ult CR2 is equivalent to CR1 slt CR2.
ConstantRange cttz(bool ZeroIsPoison=false) const
Calculate cttz range.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
Definition: ConstantRange.h:84
ConstantRange ctpop() const
Calculate ctpop range.
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 ctlz(bool ZeroIsPoison=false) const
Calculate ctlz range.
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.
ConstantRange multiplyWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from a multiplication with wrap type No...
bool isBinaryOp() const
Definition: Instruction.h:279
Metadata node.
Definition: Metadata.h:1069
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition: Operator.h:77
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:2971
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:2732
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:2750
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2195
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2200
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2205
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2210
@ 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
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
@ Offset
Definition: DWP.cpp:480
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
Definition: bit.h:281
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
@ Other
Any other memory.
@ UMin
Unsigned 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()).
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
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:1856
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
Definition: KnownBits.h:290
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:97
bool isUnknown() const
Returns true if we don't know any bits.
Definition: KnownBits.h:62
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:134
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
Definition: KnownBits.h:118
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:94