LLVM 19.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 default:
992 // Don't know about this Overflowing Binary Operation.
993 // Conservatively fallback to plain binop handling.
994 return binaryOp(BinOp, Other);
995 }
996}
997
999 switch (IntrinsicID) {
1000 case Intrinsic::uadd_sat:
1001 case Intrinsic::usub_sat:
1002 case Intrinsic::sadd_sat:
1003 case Intrinsic::ssub_sat:
1004 case Intrinsic::umin:
1005 case Intrinsic::umax:
1006 case Intrinsic::smin:
1007 case Intrinsic::smax:
1008 case Intrinsic::abs:
1009 case Intrinsic::ctlz:
1010 case Intrinsic::cttz:
1011 case Intrinsic::ctpop:
1012 return true;
1013 default:
1014 return false;
1015 }
1016}
1017
1020 switch (IntrinsicID) {
1021 case Intrinsic::uadd_sat:
1022 return Ops[0].uadd_sat(Ops[1]);
1023 case Intrinsic::usub_sat:
1024 return Ops[0].usub_sat(Ops[1]);
1025 case Intrinsic::sadd_sat:
1026 return Ops[0].sadd_sat(Ops[1]);
1027 case Intrinsic::ssub_sat:
1028 return Ops[0].ssub_sat(Ops[1]);
1029 case Intrinsic::umin:
1030 return Ops[0].umin(Ops[1]);
1031 case Intrinsic::umax:
1032 return Ops[0].umax(Ops[1]);
1033 case Intrinsic::smin:
1034 return Ops[0].smin(Ops[1]);
1035 case Intrinsic::smax:
1036 return Ops[0].smax(Ops[1]);
1037 case Intrinsic::abs: {
1038 const APInt *IntMinIsPoison = Ops[1].getSingleElement();
1039 assert(IntMinIsPoison && "Must be known (immarg)");
1040 assert(IntMinIsPoison->getBitWidth() == 1 && "Must be boolean");
1041 return Ops[0].abs(IntMinIsPoison->getBoolValue());
1042 }
1043 case Intrinsic::ctlz: {
1044 const APInt *ZeroIsPoison = Ops[1].getSingleElement();
1045 assert(ZeroIsPoison && "Must be known (immarg)");
1046 assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
1047 return Ops[0].ctlz(ZeroIsPoison->getBoolValue());
1048 }
1049 case Intrinsic::cttz: {
1050 const APInt *ZeroIsPoison = Ops[1].getSingleElement();
1051 assert(ZeroIsPoison && "Must be known (immarg)");
1052 assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean");
1053 return Ops[0].cttz(ZeroIsPoison->getBoolValue());
1054 }
1055 case Intrinsic::ctpop:
1056 return Ops[0].ctpop();
1057 default:
1058 assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported");
1059 llvm_unreachable("Unsupported intrinsic");
1060 }
1061}
1062
1065 if (isEmptySet() || Other.isEmptySet())
1066 return getEmpty();
1067 if (isFullSet() || Other.isFullSet())
1068 return getFull();
1069
1070 APInt NewLower = getLower() + Other.getLower();
1071 APInt NewUpper = getUpper() + Other.getUpper() - 1;
1072 if (NewLower == NewUpper)
1073 return getFull();
1074
1075 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1076 if (X.isSizeStrictlySmallerThan(*this) ||
1077 X.isSizeStrictlySmallerThan(Other))
1078 // We've wrapped, therefore, full set.
1079 return getFull();
1080 return X;
1081}
1082
1084 unsigned NoWrapKind,
1085 PreferredRangeType RangeType) const {
1086 // Calculate the range for "X + Y" which is guaranteed not to wrap(overflow).
1087 // (X is from this, and Y is from Other)
1088 if (isEmptySet() || Other.isEmptySet())
1089 return getEmpty();
1090 if (isFullSet() && Other.isFullSet())
1091 return getFull();
1092
1093 using OBO = OverflowingBinaryOperator;
1094 ConstantRange Result = add(Other);
1095
1096 // If an overflow happens for every value pair in these two constant ranges,
1097 // we must return Empty set. In this case, we get that for free, because we
1098 // get lucky that intersection of add() with uadd_sat()/sadd_sat() results
1099 // in an empty set.
1100
1101 if (NoWrapKind & OBO::NoSignedWrap)
1102 Result = Result.intersectWith(sadd_sat(Other), RangeType);
1103
1104 if (NoWrapKind & OBO::NoUnsignedWrap)
1105 Result = Result.intersectWith(uadd_sat(Other), RangeType);
1106
1107 return Result;
1108}
1109
1112 if (isEmptySet() || Other.isEmptySet())
1113 return getEmpty();
1114 if (isFullSet() || Other.isFullSet())
1115 return getFull();
1116
1117 APInt NewLower = getLower() - Other.getUpper() + 1;
1118 APInt NewUpper = getUpper() - Other.getLower();
1119 if (NewLower == NewUpper)
1120 return getFull();
1121
1122 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
1123 if (X.isSizeStrictlySmallerThan(*this) ||
1124 X.isSizeStrictlySmallerThan(Other))
1125 // We've wrapped, therefore, full set.
1126 return getFull();
1127 return X;
1128}
1129
1131 unsigned NoWrapKind,
1132 PreferredRangeType RangeType) const {
1133 // Calculate the range for "X - Y" which is guaranteed not to wrap(overflow).
1134 // (X is from this, and Y is from Other)
1135 if (isEmptySet() || Other.isEmptySet())
1136 return getEmpty();
1137 if (isFullSet() && Other.isFullSet())
1138 return getFull();
1139
1140 using OBO = OverflowingBinaryOperator;
1141 ConstantRange Result = sub(Other);
1142
1143 // If an overflow happens for every value pair in these two constant ranges,
1144 // we must return Empty set. In signed case, we get that for free, because we
1145 // get lucky that intersection of sub() with ssub_sat() results in an
1146 // empty set. But for unsigned we must perform the overflow check manually.
1147
1148 if (NoWrapKind & OBO::NoSignedWrap)
1149 Result = Result.intersectWith(ssub_sat(Other), RangeType);
1150
1151 if (NoWrapKind & OBO::NoUnsignedWrap) {
1152 if (getUnsignedMax().ult(Other.getUnsignedMin()))
1153 return getEmpty(); // Always overflows.
1154 Result = Result.intersectWith(usub_sat(Other), RangeType);
1155 }
1156
1157 return Result;
1158}
1159
1162 // TODO: If either operand is a single element and the multiply is known to
1163 // be non-wrapping, round the result min and max value to the appropriate
1164 // multiple of that element. If wrapping is possible, at least adjust the
1165 // range according to the greatest power-of-two factor of the single element.
1166
1167 if (isEmptySet() || Other.isEmptySet())
1168 return getEmpty();
1169
1170 if (const APInt *C = getSingleElement()) {
1171 if (C->isOne())
1172 return Other;
1173 if (C->isAllOnes())
1175 }
1176
1177 if (const APInt *C = Other.getSingleElement()) {
1178 if (C->isOne())
1179 return *this;
1180 if (C->isAllOnes())
1181 return ConstantRange(APInt::getZero(getBitWidth())).sub(*this);
1182 }
1183
1184 // Multiplication is signedness-independent. However different ranges can be
1185 // obtained depending on how the input ranges are treated. These different
1186 // ranges are all conservatively correct, but one might be better than the
1187 // other. We calculate two ranges; one treating the inputs as unsigned
1188 // and the other signed, then return the smallest of these ranges.
1189
1190 // Unsigned range first.
1191 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
1192 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
1193 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
1194 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
1195
1196 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
1197 this_max * Other_max + 1);
1198 ConstantRange UR = Result_zext.truncate(getBitWidth());
1199
1200 // If the unsigned range doesn't wrap, and isn't negative then it's a range
1201 // from one positive number to another which is as good as we can generate.
1202 // In this case, skip the extra work of generating signed ranges which aren't
1203 // going to be better than this range.
1204 if (!UR.isUpperWrapped() &&
1206 return UR;
1207
1208 // Now the signed range. Because we could be dealing with negative numbers
1209 // here, the lower bound is the smallest of the cartesian product of the
1210 // lower and upper ranges; for example:
1211 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1212 // Similarly for the upper bound, swapping min for max.
1213
1214 this_min = getSignedMin().sext(getBitWidth() * 2);
1215 this_max = getSignedMax().sext(getBitWidth() * 2);
1216 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
1217 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
1218
1219 auto L = {this_min * Other_min, this_min * Other_max,
1220 this_max * Other_min, this_max * Other_max};
1221 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1222 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
1223 ConstantRange SR = Result_sext.truncate(getBitWidth());
1224
1225 return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
1226}
1227
1230 unsigned NoWrapKind,
1231 PreferredRangeType RangeType) const {
1232 if (isEmptySet() || Other.isEmptySet())
1233 return getEmpty();
1234 if (isFullSet() && Other.isFullSet())
1235 return getFull();
1236
1237 ConstantRange Result = multiply(Other);
1238
1240 Result = Result.intersectWith(smul_sat(Other), RangeType);
1241
1243 Result = Result.intersectWith(umul_sat(Other), RangeType);
1244
1245 return Result;
1246}
1247
1249 if (isEmptySet() || Other.isEmptySet())
1250 return getEmpty();
1251
1252 APInt Min = getSignedMin();
1253 APInt Max = getSignedMax();
1254 APInt OtherMin = Other.getSignedMin();
1255 APInt OtherMax = Other.getSignedMax();
1256
1257 bool O1, O2, O3, O4;
1258 auto Muls = {Min.smul_ov(OtherMin, O1), Min.smul_ov(OtherMax, O2),
1259 Max.smul_ov(OtherMin, O3), Max.smul_ov(OtherMax, O4)};
1260 if (O1 || O2 || O3 || O4)
1261 return getFull();
1262
1263 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1264 return getNonEmpty(std::min(Muls, Compare), std::max(Muls, Compare) + 1);
1265}
1266
1269 // X smax Y is: range(smax(X_smin, Y_smin),
1270 // smax(X_smax, Y_smax))
1271 if (isEmptySet() || Other.isEmptySet())
1272 return getEmpty();
1273 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
1274 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
1275 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1276 if (isSignWrappedSet() || Other.isSignWrappedSet())
1277 return Res.intersectWith(unionWith(Other, Signed), Signed);
1278 return Res;
1279}
1280
1283 // X umax Y is: range(umax(X_umin, Y_umin),
1284 // umax(X_umax, Y_umax))
1285 if (isEmptySet() || Other.isEmptySet())
1286 return getEmpty();
1287 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
1288 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1289 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1290 if (isWrappedSet() || Other.isWrappedSet())
1292 return Res;
1293}
1294
1297 // X smin Y is: range(smin(X_smin, Y_smin),
1298 // smin(X_smax, Y_smax))
1299 if (isEmptySet() || Other.isEmptySet())
1300 return getEmpty();
1301 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
1302 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
1303 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1304 if (isSignWrappedSet() || Other.isSignWrappedSet())
1305 return Res.intersectWith(unionWith(Other, Signed), Signed);
1306 return Res;
1307}
1308
1311 // X umin Y is: range(umin(X_umin, Y_umin),
1312 // umin(X_umax, Y_umax))
1313 if (isEmptySet() || Other.isEmptySet())
1314 return getEmpty();
1315 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
1316 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
1317 ConstantRange Res = getNonEmpty(std::move(NewL), std::move(NewU));
1318 if (isWrappedSet() || Other.isWrappedSet())
1320 return Res;
1321}
1322
1325 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1326 return getEmpty();
1327
1328 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
1329
1330 APInt RHS_umin = RHS.getUnsignedMin();
1331 if (RHS_umin.isZero()) {
1332 // We want the lowest value in RHS excluding zero. Usually that would be 1
1333 // except for a range in the form of [X, 1) in which case it would be X.
1334 if (RHS.getUpper() == 1)
1335 RHS_umin = RHS.getLower();
1336 else
1337 RHS_umin = 1;
1338 }
1339
1340 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
1341 return getNonEmpty(std::move(Lower), std::move(Upper));
1342}
1343
1345 // We split up the LHS and RHS into positive and negative components
1346 // and then also compute the positive and negative components of the result
1347 // separately by combining division results with the appropriate signs.
1350 // There are no positive 1-bit values. The 1 would get interpreted as -1.
1351 ConstantRange PosFilter =
1352 getBitWidth() == 1 ? getEmpty()
1353 : ConstantRange(APInt(getBitWidth(), 1), SignedMin);
1354 ConstantRange NegFilter(SignedMin, Zero);
1355 ConstantRange PosL = intersectWith(PosFilter);
1356 ConstantRange NegL = intersectWith(NegFilter);
1357 ConstantRange PosR = RHS.intersectWith(PosFilter);
1358 ConstantRange NegR = RHS.intersectWith(NegFilter);
1359
1360 ConstantRange PosRes = getEmpty();
1361 if (!PosL.isEmptySet() && !PosR.isEmptySet())
1362 // pos / pos = pos.
1363 PosRes = ConstantRange(PosL.Lower.sdiv(PosR.Upper - 1),
1364 (PosL.Upper - 1).sdiv(PosR.Lower) + 1);
1365
1366 if (!NegL.isEmptySet() && !NegR.isEmptySet()) {
1367 // neg / neg = pos.
1368 //
1369 // We need to deal with one tricky case here: SignedMin / -1 is UB on the
1370 // IR level, so we'll want to exclude this case when calculating bounds.
1371 // (For APInts the operation is well-defined and yields SignedMin.) We
1372 // handle this by dropping either SignedMin from the LHS or -1 from the RHS.
1373 APInt Lo = (NegL.Upper - 1).sdiv(NegR.Lower);
1374 if (NegL.Lower.isMinSignedValue() && NegR.Upper.isZero()) {
1375 // Remove -1 from the LHS. Skip if it's the only element, as this would
1376 // leave us with an empty set.
1377 if (!NegR.Lower.isAllOnes()) {
1378 APInt AdjNegRUpper;
1379 if (RHS.Lower.isAllOnes())
1380 // Negative part of [-1, X] without -1 is [SignedMin, X].
1381 AdjNegRUpper = RHS.Upper;
1382 else
1383 // [X, -1] without -1 is [X, -2].
1384 AdjNegRUpper = NegR.Upper - 1;
1385
1386 PosRes = PosRes.unionWith(
1387 ConstantRange(Lo, NegL.Lower.sdiv(AdjNegRUpper - 1) + 1));
1388 }
1389
1390 // Remove SignedMin from the RHS. Skip if it's the only element, as this
1391 // would leave us with an empty set.
1392 if (NegL.Upper != SignedMin + 1) {
1393 APInt AdjNegLLower;
1394 if (Upper == SignedMin + 1)
1395 // Negative part of [X, SignedMin] without SignedMin is [X, -1].
1396 AdjNegLLower = Lower;
1397 else
1398 // [SignedMin, X] without SignedMin is [SignedMin + 1, X].
1399 AdjNegLLower = NegL.Lower + 1;
1400
1401 PosRes = PosRes.unionWith(
1402 ConstantRange(std::move(Lo),
1403 AdjNegLLower.sdiv(NegR.Upper - 1) + 1));
1404 }
1405 } else {
1406 PosRes = PosRes.unionWith(
1407 ConstantRange(std::move(Lo), NegL.Lower.sdiv(NegR.Upper - 1) + 1));
1408 }
1409 }
1410
1411 ConstantRange NegRes = getEmpty();
1412 if (!PosL.isEmptySet() && !NegR.isEmptySet())
1413 // pos / neg = neg.
1414 NegRes = ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
1415 PosL.Lower.sdiv(NegR.Lower) + 1);
1416
1417 if (!NegL.isEmptySet() && !PosR.isEmptySet())
1418 // neg / pos = neg.
1419 NegRes = NegRes.unionWith(
1420 ConstantRange(NegL.Lower.sdiv(PosR.Lower),
1421 (NegL.Upper - 1).sdiv(PosR.Upper - 1) + 1));
1422
1423 // Prefer a non-wrapping signed range here.
1425
1426 // Preserve the zero that we dropped when splitting the LHS by sign.
1427 if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
1428 Res = Res.unionWith(ConstantRange(Zero));
1429 return Res;
1430}
1431
1433 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isZero())
1434 return getEmpty();
1435
1436 if (const APInt *RHSInt = RHS.getSingleElement()) {
1437 // UREM by null is UB.
1438 if (RHSInt->isZero())
1439 return getEmpty();
1440 // Use APInt's implementation of UREM for single element ranges.
1441 if (const APInt *LHSInt = getSingleElement())
1442 return {LHSInt->urem(*RHSInt)};
1443 }
1444
1445 // L % R for L < R is L.
1446 if (getUnsignedMax().ult(RHS.getUnsignedMin()))
1447 return *this;
1448
1449 // L % R is <= L and < R.
1450 APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
1451 return getNonEmpty(APInt::getZero(getBitWidth()), std::move(Upper));
1452}
1453
1455 if (isEmptySet() || RHS.isEmptySet())
1456 return getEmpty();
1457
1458 if (const APInt *RHSInt = RHS.getSingleElement()) {
1459 // SREM by null is UB.
1460 if (RHSInt->isZero())
1461 return getEmpty();
1462 // Use APInt's implementation of SREM for single element ranges.
1463 if (const APInt *LHSInt = getSingleElement())
1464 return {LHSInt->srem(*RHSInt)};
1465 }
1466
1467 ConstantRange AbsRHS = RHS.abs();
1468 APInt MinAbsRHS = AbsRHS.getUnsignedMin();
1469 APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
1470
1471 // Modulus by zero is UB.
1472 if (MaxAbsRHS.isZero())
1473 return getEmpty();
1474
1475 if (MinAbsRHS.isZero())
1476 ++MinAbsRHS;
1477
1478 APInt MinLHS = getSignedMin(), MaxLHS = getSignedMax();
1479
1480 if (MinLHS.isNonNegative()) {
1481 // L % R for L < R is L.
1482 if (MaxLHS.ult(MinAbsRHS))
1483 return *this;
1484
1485 // L % R is <= L and < R.
1486 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1487 return ConstantRange(APInt::getZero(getBitWidth()), std::move(Upper));
1488 }
1489
1490 // Same basic logic as above, but the result is negative.
1491 if (MaxLHS.isNegative()) {
1492 if (MinLHS.ugt(-MinAbsRHS))
1493 return *this;
1494
1495 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1496 return ConstantRange(std::move(Lower), APInt(getBitWidth(), 1));
1497 }
1498
1499 // LHS range crosses zero.
1500 APInt Lower = APIntOps::umax(MinLHS, -MaxAbsRHS + 1);
1501 APInt Upper = APIntOps::umin(MaxLHS, MaxAbsRHS - 1) + 1;
1502 return ConstantRange(std::move(Lower), std::move(Upper));
1503}
1504
1507}
1508
1510 if (isEmptySet() || Other.isEmptySet())
1511 return getEmpty();
1512
1513 ConstantRange KnownBitsRange =
1514 fromKnownBits(toKnownBits() & Other.toKnownBits(), false);
1515 ConstantRange UMinUMaxRange =
1517 APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax()) + 1);
1518 return KnownBitsRange.intersectWith(UMinUMaxRange);
1519}
1520
1522 if (isEmptySet() || Other.isEmptySet())
1523 return getEmpty();
1524
1525 ConstantRange KnownBitsRange =
1526 fromKnownBits(toKnownBits() | Other.toKnownBits(), false);
1527 // Upper wrapped range.
1528 ConstantRange UMaxUMinRange =
1529 getNonEmpty(APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin()),
1531 return KnownBitsRange.intersectWith(UMaxUMinRange);
1532}
1533
1535 if (isEmptySet() || Other.isEmptySet())
1536 return getEmpty();
1537
1538 // Use APInt's implementation of XOR for single element ranges.
1539 if (isSingleElement() && Other.isSingleElement())
1540 return {*getSingleElement() ^ *Other.getSingleElement()};
1541
1542 // Special-case binary complement, since we can give a precise answer.
1543 if (Other.isSingleElement() && Other.getSingleElement()->isAllOnes())
1544 return binaryNot();
1545 if (isSingleElement() && getSingleElement()->isAllOnes())
1546 return Other.binaryNot();
1547
1548 KnownBits LHSKnown = toKnownBits();
1549 KnownBits RHSKnown = Other.toKnownBits();
1550 KnownBits Known = LHSKnown ^ RHSKnown;
1551 ConstantRange CR = fromKnownBits(Known, /*IsSigned*/ false);
1552 // Typically the following code doesn't improve the result if BW = 1.
1553 if (getBitWidth() == 1)
1554 return CR;
1555
1556 // If LHS is known to be the subset of RHS, treat LHS ^ RHS as RHS -nuw/nsw
1557 // LHS. If RHS is known to be the subset of LHS, treat LHS ^ RHS as LHS
1558 // -nuw/nsw RHS.
1559 if ((~LHSKnown.Zero).isSubsetOf(RHSKnown.One))
1561 else if ((~RHSKnown.Zero).isSubsetOf(LHSKnown.One))
1562 CR = CR.intersectWith(this->sub(Other), PreferredRangeType::Unsigned);
1563 return CR;
1564}
1565
1568 if (isEmptySet() || Other.isEmptySet())
1569 return getEmpty();
1570
1571 APInt Min = getUnsignedMin();
1572 APInt Max = getUnsignedMax();
1573 if (const APInt *RHS = Other.getSingleElement()) {
1574 unsigned BW = getBitWidth();
1575 if (RHS->uge(BW))
1576 return getEmpty();
1577
1578 unsigned EqualLeadingBits = (Min ^ Max).countl_zero();
1579 if (RHS->ule(EqualLeadingBits))
1580 return getNonEmpty(Min << *RHS, (Max << *RHS) + 1);
1581
1582 return getNonEmpty(APInt::getZero(BW),
1583 APInt::getBitsSetFrom(BW, RHS->getZExtValue()) + 1);
1584 }
1585
1586 APInt OtherMax = Other.getUnsignedMax();
1587 if (isAllNegative() && OtherMax.ule(Min.countl_one())) {
1588 // For negative numbers, if the shift does not overflow in a signed sense,
1589 // a larger shift will make the number smaller.
1590 Max <<= Other.getUnsignedMin();
1591 Min <<= OtherMax;
1592 return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1);
1593 }
1594
1595 // There's overflow!
1596 if (OtherMax.ugt(Max.countl_zero()))
1597 return getFull();
1598
1599 // FIXME: implement the other tricky cases
1600
1601 Min <<= Other.getUnsignedMin();
1602 Max <<= OtherMax;
1603
1604 return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1);
1605}
1606
1609 if (isEmptySet() || Other.isEmptySet())
1610 return getEmpty();
1611
1612 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
1613 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
1614 return getNonEmpty(std::move(min), std::move(max));
1615}
1616
1619 if (isEmptySet() || Other.isEmptySet())
1620 return getEmpty();
1621
1622 // May straddle zero, so handle both positive and negative cases.
1623 // 'PosMax' is the upper bound of the result of the ashr
1624 // operation, when Upper of the LHS of ashr is a non-negative.
1625 // number. Since ashr of a non-negative number will result in a
1626 // smaller number, the Upper value of LHS is shifted right with
1627 // the minimum value of 'Other' instead of the maximum value.
1628 APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
1629
1630 // 'PosMin' is the lower bound of the result of the ashr
1631 // operation, when Lower of the LHS is a non-negative number.
1632 // Since ashr of a non-negative number will result in a smaller
1633 // number, the Lower value of LHS is shifted right with the
1634 // maximum value of 'Other'.
1635 APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
1636
1637 // 'NegMax' is the upper bound of the result of the ashr
1638 // operation, when Upper of the LHS of ashr is a negative number.
1639 // Since 'ashr' of a negative number will result in a bigger
1640 // number, the Upper value of LHS is shifted right with the
1641 // maximum value of 'Other'.
1642 APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
1643
1644 // 'NegMin' is the lower bound of the result of the ashr
1645 // operation, when Lower of the LHS of ashr is a negative number.
1646 // Since 'ashr' of a negative number will result in a bigger
1647 // number, the Lower value of LHS is shifted right with the
1648 // minimum value of 'Other'.
1649 APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
1650
1651 APInt max, min;
1652 if (getSignedMin().isNonNegative()) {
1653 // Upper and Lower of LHS are non-negative.
1654 min = PosMin;
1655 max = PosMax;
1656 } else if (getSignedMax().isNegative()) {
1657 // Upper and Lower of LHS are negative.
1658 min = NegMin;
1659 max = NegMax;
1660 } else {
1661 // Upper is non-negative and Lower is negative.
1662 min = NegMin;
1663 max = PosMax;
1664 }
1665 return getNonEmpty(std::move(min), std::move(max));
1666}
1667
1669 if (isEmptySet() || Other.isEmptySet())
1670 return getEmpty();
1671
1672 APInt NewL = getUnsignedMin().uadd_sat(Other.getUnsignedMin());
1673 APInt NewU = getUnsignedMax().uadd_sat(Other.getUnsignedMax()) + 1;
1674 return getNonEmpty(std::move(NewL), std::move(NewU));
1675}
1676
1678 if (isEmptySet() || Other.isEmptySet())
1679 return getEmpty();
1680
1681 APInt NewL = getSignedMin().sadd_sat(Other.getSignedMin());
1682 APInt NewU = getSignedMax().sadd_sat(Other.getSignedMax()) + 1;
1683 return getNonEmpty(std::move(NewL), std::move(NewU));
1684}
1685
1687 if (isEmptySet() || Other.isEmptySet())
1688 return getEmpty();
1689
1690 APInt NewL = getUnsignedMin().usub_sat(Other.getUnsignedMax());
1691 APInt NewU = getUnsignedMax().usub_sat(Other.getUnsignedMin()) + 1;
1692 return getNonEmpty(std::move(NewL), std::move(NewU));
1693}
1694
1696 if (isEmptySet() || Other.isEmptySet())
1697 return getEmpty();
1698
1699 APInt NewL = getSignedMin().ssub_sat(Other.getSignedMax());
1700 APInt NewU = getSignedMax().ssub_sat(Other.getSignedMin()) + 1;
1701 return getNonEmpty(std::move(NewL), std::move(NewU));
1702}
1703
1705 if (isEmptySet() || Other.isEmptySet())
1706 return getEmpty();
1707
1708 APInt NewL = getUnsignedMin().umul_sat(Other.getUnsignedMin());
1709 APInt NewU = getUnsignedMax().umul_sat(Other.getUnsignedMax()) + 1;
1710 return getNonEmpty(std::move(NewL), std::move(NewU));
1711}
1712
1714 if (isEmptySet() || Other.isEmptySet())
1715 return getEmpty();
1716
1717 // Because we could be dealing with negative numbers here, the lower bound is
1718 // the smallest of the cartesian product of the lower and upper ranges;
1719 // for example:
1720 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
1721 // Similarly for the upper bound, swapping min for max.
1722
1723 APInt Min = getSignedMin();
1724 APInt Max = getSignedMax();
1725 APInt OtherMin = Other.getSignedMin();
1726 APInt OtherMax = Other.getSignedMax();
1727
1728 auto L = {Min.smul_sat(OtherMin), Min.smul_sat(OtherMax),
1729 Max.smul_sat(OtherMin), Max.smul_sat(OtherMax)};
1730 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
1731 return getNonEmpty(std::min(L, Compare), std::max(L, Compare) + 1);
1732}
1733
1735 if (isEmptySet() || Other.isEmptySet())
1736 return getEmpty();
1737
1738 APInt NewL = getUnsignedMin().ushl_sat(Other.getUnsignedMin());
1739 APInt NewU = getUnsignedMax().ushl_sat(Other.getUnsignedMax()) + 1;
1740 return getNonEmpty(std::move(NewL), std::move(NewU));
1741}
1742
1744 if (isEmptySet() || Other.isEmptySet())
1745 return getEmpty();
1746
1747 APInt Min = getSignedMin(), Max = getSignedMax();
1748 APInt ShAmtMin = Other.getUnsignedMin(), ShAmtMax = Other.getUnsignedMax();
1749 APInt NewL = Min.sshl_sat(Min.isNonNegative() ? ShAmtMin : ShAmtMax);
1750 APInt NewU = Max.sshl_sat(Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;
1751 return getNonEmpty(std::move(NewL), std::move(NewU));
1752}
1753
1755 if (isFullSet())
1756 return getEmpty();
1757 if (isEmptySet())
1758 return getFull();
1759 return ConstantRange(Upper, Lower);
1760}
1761
1762ConstantRange ConstantRange::abs(bool IntMinIsPoison) const {
1763 if (isEmptySet())
1764 return getEmpty();
1765
1766 if (isSignWrappedSet()) {
1767 APInt Lo;
1768 // Check whether the range crosses zero.
1769 if (Upper.isStrictlyPositive() || !Lower.isStrictlyPositive())
1771 else
1772 Lo = APIntOps::umin(Lower, -Upper + 1);
1773
1774 // If SignedMin is not poison, then it is included in the result range.
1775 if (IntMinIsPoison)
1777 else
1779 }
1780
1782
1783 // Skip SignedMin if it is poison.
1784 if (IntMinIsPoison && SMin.isMinSignedValue()) {
1785 // The range may become empty if it *only* contains SignedMin.
1786 if (SMax.isMinSignedValue())
1787 return getEmpty();
1788 ++SMin;
1789 }
1790
1791 // All non-negative.
1792 if (SMin.isNonNegative())
1793 return ConstantRange(SMin, SMax + 1);
1794
1795 // All negative.
1796 if (SMax.isNegative())
1797 return ConstantRange(-SMax, -SMin + 1);
1798
1799 // Range crosses zero.
1801 APIntOps::umax(-SMin, SMax) + 1);
1802}
1803
1804ConstantRange ConstantRange::ctlz(bool ZeroIsPoison) const {
1805 if (isEmptySet())
1806 return getEmpty();
1807
1809 if (ZeroIsPoison && contains(Zero)) {
1810 // ZeroIsPoison is set, and zero is contained. We discern three cases, in
1811 // which a zero can appear:
1812 // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
1813 // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
1814 // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
1815
1816 if (getLower().isZero()) {
1817 if ((getUpper() - 1).isZero()) {
1818 // We have in input interval of kind [0, 1). In this case we cannot
1819 // really help but return empty-set.
1820 return getEmpty();
1821 }
1822
1823 // Compute the resulting range by excluding zero from Lower.
1824 return ConstantRange(
1825 APInt(getBitWidth(), (getUpper() - 1).countl_zero()),
1826 APInt(getBitWidth(), (getLower() + 1).countl_zero() + 1));
1827 } else if ((getUpper() - 1).isZero()) {
1828 // Compute the resulting range by excluding zero from Upper.
1829 return ConstantRange(Zero,
1831 } else {
1832 return ConstantRange(Zero, APInt(getBitWidth(), getBitWidth()));
1833 }
1834 }
1835
1836 // Zero is either safe or not in the range. The output range is composed by
1837 // the result of countLeadingZero of the two extremes.
1840}
1841
1843 const APInt &Upper) {
1844 assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
1845 "Unexpected wrapped set.");
1846 assert(Lower != Upper && "Unexpected empty set.");
1847 unsigned BitWidth = Lower.getBitWidth();
1848 if (Lower + 1 == Upper)
1849 return ConstantRange(APInt(BitWidth, Lower.countr_zero()));
1850 if (Lower.isZero())
1852 APInt(BitWidth, BitWidth + 1));
1853
1854 // Calculate longest common prefix.
1855 unsigned LCPLength = (Lower ^ (Upper - 1)).countl_zero();
1856 // If Lower is {LCP, 000...}, the maximum is Lower.countr_zero().
1857 // Otherwise, the maximum is BitWidth - LCPLength - 1 ({LCP, 100...}).
1858 return ConstantRange(
1861 std::max(BitWidth - LCPLength - 1, Lower.countr_zero()) + 1));
1862}
1863
1864ConstantRange ConstantRange::cttz(bool ZeroIsPoison) const {
1865 if (isEmptySet())
1866 return getEmpty();
1867
1868 unsigned BitWidth = getBitWidth();
1870 if (ZeroIsPoison && contains(Zero)) {
1871 // ZeroIsPoison is set, and zero is contained. We discern three cases, in
1872 // which a zero can appear:
1873 // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc.
1874 // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc.
1875 // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc.
1876
1877 if (Lower.isZero()) {
1878 if (Upper == 1) {
1879 // We have in input interval of kind [0, 1). In this case we cannot
1880 // really help but return empty-set.
1881 return getEmpty();
1882 }
1883
1884 // Compute the resulting range by excluding zero from Lower.
1886 } else if (Upper == 1) {
1887 // Compute the resulting range by excluding zero from Upper.
1888 return getUnsignedCountTrailingZerosRange(Lower, Zero);
1889 } else {
1891 ConstantRange CR2 =
1893 return CR1.unionWith(CR2);
1894 }
1895 }
1896
1897 if (isFullSet())
1898 return getNonEmpty(Zero, APInt(BitWidth, BitWidth + 1));
1899 if (!isWrappedSet())
1900 return getUnsignedCountTrailingZerosRange(Lower, Upper);
1901 // The range is wrapped. We decompose it into two ranges, [0, Upper) and
1902 // [Lower, 0).
1903 // Handle [Lower, 0)
1905 // Handle [0, Upper)
1907 return CR1.unionWith(CR2);
1908}
1909
1911 const APInt &Upper) {
1912 assert(!ConstantRange(Lower, Upper).isWrappedSet() &&
1913 "Unexpected wrapped set.");
1914 assert(Lower != Upper && "Unexpected empty set.");
1915 unsigned BitWidth = Lower.getBitWidth();
1916 if (Lower + 1 == Upper)
1917 return ConstantRange(APInt(BitWidth, Lower.popcount()));
1918
1919 APInt Max = Upper - 1;
1920 // Calculate longest common prefix.
1921 unsigned LCPLength = (Lower ^ Max).countl_zero();
1922 unsigned LCPPopCount = Lower.getHiBits(LCPLength).popcount();
1923 // If Lower is {LCP, 000...}, the minimum is the popcount of LCP.
1924 // Otherwise, the minimum is the popcount of LCP + 1.
1925 unsigned MinBits =
1926 LCPPopCount + (Lower.countr_zero() < BitWidth - LCPLength ? 1 : 0);
1927 // If Max is {LCP, 111...}, the maximum is the popcount of LCP + (BitWidth -
1928 // length of LCP).
1929 // Otherwise, the minimum is the popcount of LCP + (BitWidth -
1930 // length of LCP - 1).
1931 unsigned MaxBits = LCPPopCount + (BitWidth - LCPLength) -
1932 (Max.countr_one() < BitWidth - LCPLength ? 1 : 0);
1933 return ConstantRange(APInt(BitWidth, MinBits), APInt(BitWidth, MaxBits + 1));
1934}
1935
1937 if (isEmptySet())
1938 return getEmpty();
1939
1940 unsigned BitWidth = getBitWidth();
1942 if (isFullSet())
1943 return getNonEmpty(Zero, APInt(BitWidth, BitWidth + 1));
1944 if (!isWrappedSet())
1945 return getUnsignedPopCountRange(Lower, Upper);
1946 // The range is wrapped. We decompose it into two ranges, [0, Upper) and
1947 // [Lower, 0).
1948 // Handle [Lower, 0) == [Lower, Max]
1950 APInt(BitWidth, BitWidth + 1));
1951 // Handle [0, Upper)
1952 ConstantRange CR2 = getUnsignedPopCountRange(Zero, Upper);
1953 return CR1.unionWith(CR2);
1954}
1955
1957 const ConstantRange &Other) const {
1958 if (isEmptySet() || Other.isEmptySet())
1960
1961 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
1962 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
1963
1964 // a u+ b overflows high iff a u> ~b.
1965 if (Min.ugt(~OtherMin))
1967 if (Max.ugt(~OtherMax))
1970}
1971
1973 const ConstantRange &Other) const {
1974 if (isEmptySet() || Other.isEmptySet())
1976
1977 APInt Min = getSignedMin(), Max = getSignedMax();
1978 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
1979
1982
1983 // a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b.
1984 // a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b.
1985 if (Min.isNonNegative() && OtherMin.isNonNegative() &&
1986 Min.sgt(SignedMax - OtherMin))
1988 if (Max.isNegative() && OtherMax.isNegative() &&
1989 Max.slt(SignedMin - OtherMax))
1991
1992 if (Max.isNonNegative() && OtherMax.isNonNegative() &&
1993 Max.sgt(SignedMax - OtherMax))
1995 if (Min.isNegative() && OtherMin.isNegative() &&
1996 Min.slt(SignedMin - OtherMin))
1998
2000}
2001
2003 const ConstantRange &Other) const {
2004 if (isEmptySet() || Other.isEmptySet())
2006
2007 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2008 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2009
2010 // a u- b overflows low iff a u< b.
2011 if (Max.ult(OtherMin))
2013 if (Min.ult(OtherMax))
2016}
2017
2019 const ConstantRange &Other) const {
2020 if (isEmptySet() || Other.isEmptySet())
2022
2023 APInt Min = getSignedMin(), Max = getSignedMax();
2024 APInt OtherMin = Other.getSignedMin(), OtherMax = Other.getSignedMax();
2025
2028
2029 // a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b.
2030 // a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b.
2031 if (Min.isNonNegative() && OtherMax.isNegative() &&
2032 Min.sgt(SignedMax + OtherMax))
2034 if (Max.isNegative() && OtherMin.isNonNegative() &&
2035 Max.slt(SignedMin + OtherMin))
2037
2038 if (Max.isNonNegative() && OtherMin.isNegative() &&
2039 Max.sgt(SignedMax + OtherMin))
2041 if (Min.isNegative() && OtherMax.isNonNegative() &&
2042 Min.slt(SignedMin + OtherMax))
2044
2046}
2047
2049 const ConstantRange &Other) const {
2050 if (isEmptySet() || Other.isEmptySet())
2052
2053 APInt Min = getUnsignedMin(), Max = getUnsignedMax();
2054 APInt OtherMin = Other.getUnsignedMin(), OtherMax = Other.getUnsignedMax();
2055 bool Overflow;
2056
2057 (void) Min.umul_ov(OtherMin, Overflow);
2058 if (Overflow)
2060
2061 (void) Max.umul_ov(OtherMax, Overflow);
2062 if (Overflow)
2064
2066}
2067
2069 if (isFullSet())
2070 OS << "full-set";
2071 else if (isEmptySet())
2072 OS << "empty-set";
2073 else
2074 OS << "[" << Lower << "," << Upper << ")";
2075}
2076
2077#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2079 print(dbgs());
2080}
2081#endif
2082
2084 const unsigned NumRanges = Ranges.getNumOperands() / 2;
2085 assert(NumRanges >= 1 && "Must have at least one range!");
2086 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
2087
2088 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
2089 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
2090
2091 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
2092
2093 for (unsigned i = 1; i < NumRanges; ++i) {
2094 auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
2095 auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
2096
2097 // Note: unionWith will potentially create a range that contains values not
2098 // contained in any of the original N ranges.
2099 CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
2100 }
2101
2102 return CR;
2103}
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 getUnsignedPopCountRange(const APInt &Lower, const APInt &Upper)
static ConstantRange makeExactMulNUWRegion(const APInt &V)
Exact mul nuw region for single element RHS.
static ConstantRange makeExactMulNSWRegion(const APInt &V)
Exact mul nsw region for single element RHS.
static ConstantRange getPreferredRange(const ConstantRange &CR1, const ConstantRange &CR2, ConstantRange::PreferredRangeType Type)
static ConstantRange getUnsignedCountTrailingZerosRange(const APInt &Lower, const APInt &Upper)
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:528
This file contains the declarations for metadata subclasses.
uint64_t High
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
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:214
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition: APInt.h:1387
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:981
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:403
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1472
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:186
APInt smul_sat(const APInt &RHS) const
Definition: APInt.cpp:2034
APInt sadd_sat(const APInt &RHS) const
Definition: APInt.cpp:1996
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition: APInt.h:1181
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:351
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1162
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:360
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1448
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1091
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:189
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:397
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:196
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:309
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:1146
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:199
APInt sshl_sat(const APInt &RHS) const
Definition: APInt.cpp:2056
APInt ushl_sat(const APInt &RHS) const
Definition: APInt.cpp:2070
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
Definition: APInt.h:336
unsigned countl_one() const
Count the number of leading one bits.
Definition: APInt.h:1574
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
Definition: APInt.h:1397
APInt uadd_sat(const APInt &RHS) const
Definition: APInt.cpp:2006
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:807
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1299
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:451
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:314
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1130
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:954
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:286
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1110
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:276
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
Definition: APInt.h:180
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition: APInt.h:1217
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:266
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:219
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:831
unsigned countr_one() const
Count the number of trailing one bits.
Definition: APInt.h:1615
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1201
void clearSignBit()
Set the sign bit to 0.
Definition: APInt.h:1411
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:379
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 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:1067
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:2197
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2202
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition: APInt.h:2207
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
Definition: APInt.h:2212
@ 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:1849
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