Lines Matching full:lhs
30 static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS,
33 APInt PossibleSumZero = LHS.getMaxValue() + RHS.getMaxValue() + !CarryZero;
34 APInt PossibleSumOne = LHS.getMinValue() + RHS.getMinValue() + CarryOne;
37 APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
38 APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
41 APInt LHSKnownUnion = LHS.Zero | LHS.One;
54 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) {
57 LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue());
61 const KnownBits &LHS,
63 unsigned BitWidth = LHS.getBitWidth();
67 if (LHS.isUnknown() && RHS.isUnknown())
70 if (!LHS.isUnknown() && !RHS.isUnknown()) {
72 // Sum = LHS + RHS + 0
73 KnownOut = ::computeForAddCarry(LHS, RHS, /*CarryZero=*/true,
76 // Sum = LHS + ~RHS + 1
79 KnownOut = ::computeForAddCarry(LHS, NotRHS, /*CarryZero=*/false,
88 APInt MinVal = LHS.getMinValue().uadd_sat(RHS.getMinValue());
100 APInt MaxVal = LHS.getMaxValue().usub_sat(RHS.getMinValue());
118 MinVal = LHS.getSignedMinValue().sadd_sat(RHS.getSignedMinValue());
119 MaxVal = LHS.getSignedMaxValue().sadd_sat(RHS.getSignedMaxValue());
122 MinVal = LHS.getSignedMinValue().ssub_sat(RHS.getSignedMaxValue());
123 MaxVal = LHS.getSignedMaxValue().ssub_sat(RHS.getSignedMinValue());
146 KnownBits KnownBits::computeForSubBorrow(const KnownBits &LHS, KnownBits RHS,
150 // LHS - RHS = LHS + ~RHS + 1
153 return ::computeForAddCarry(LHS, RHS,
187 KnownBits KnownBits::umax(const KnownBits &LHS, const KnownBits &RHS) {
188 // If we can prove that LHS >= RHS then use LHS as the result. Likewise for
192 if (LHS.getMinValue().uge(RHS.getMaxValue()))
193 return LHS;
194 if (RHS.getMinValue().uge(LHS.getMaxValue()))
197 // If the result of the umax is LHS then it must be greater than or equal to
200 KnownBits L = LHS.makeGE(RHS.getMinValue());
201 KnownBits R = RHS.makeGE(LHS.getMinValue());
205 KnownBits KnownBits::umin(const KnownBits &LHS, const KnownBits &RHS) {
208 return Flip(umax(Flip(LHS), Flip(RHS)));
211 KnownBits KnownBits::smax(const KnownBits &LHS, const KnownBits &RHS) {
212 return flipSignBit(umax(flipSignBit(LHS), flipSignBit(RHS)));
215 KnownBits KnownBits::smin(const KnownBits &LHS, const KnownBits &RHS) {
225 return Flip(umax(Flip(LHS), Flip(RHS)));
228 KnownBits KnownBits::abdu(const KnownBits &LHS, const KnownBits &RHS) {
229 // If we know which argument is larger, return (sub LHS, RHS) or
230 // (sub RHS, LHS) directly.
231 if (LHS.getMinValue().uge(RHS.getMaxValue()))
232 return computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, LHS,
234 if (RHS.getMinValue().uge(LHS.getMaxValue()))
236 LHS);
239 // Find the common bits between (sub nuw LHS, RHS) and (sub nuw RHS, LHS).
241 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, LHS, RHS);
243 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, RHS, LHS);
247 KnownBits KnownBits::abds(KnownBits LHS, KnownBits RHS) {
248 // If we know which argument is larger, return (sub LHS, RHS) or
249 // (sub RHS, LHS) directly.
250 if (LHS.getSignedMinValue().sge(RHS.getSignedMaxValue()))
251 return computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, LHS,
253 if (RHS.getSignedMinValue().sge(LHS.getSignedMaxValue()))
255 LHS);
263 unsigned SignBitPosition = LHS.getBitWidth() - 1;
264 for (auto Arg : {&LHS, &RHS}) {
270 // Find the common bits between (sub nuw LHS, RHS) and (sub nuw RHS, LHS).
272 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, LHS, RHS);
274 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, RHS, LHS);
285 KnownBits KnownBits::shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW,
287 unsigned BitWidth = LHS.getBitWidth();
288 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {
291 Known.Zero = LHS.Zero.ushl_ov(ShiftAmt, ShiftedOutZero);
293 Known.One = LHS.One.ushl_ov(ShiftAmt, ShiftedOutOne);
309 // Fast path for a common case when LHS is completely unknown.
314 if (LHS.isUnknown()) {
325 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros() - 1);
327 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros());
331 std::max(LHS.countMaxLeadingZeros(), LHS.countMaxLeadingOnes()) - 1);
336 Known.Zero.setLowBits(LHS.countMinTrailingZeros());
337 if (LHS.isAllOnes())
340 if (LHS.isNonNegative())
342 if (LHS.isNegative())
359 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
370 KnownBits KnownBits::lshr(const KnownBits &LHS, const KnownBits &RHS,
372 unsigned BitWidth = LHS.getBitWidth();
373 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {
374 KnownBits Known = LHS;
382 // Fast path for a common case when LHS is completely unknown.
387 if (LHS.isUnknown()) {
396 // If exact, bound MaxShiftAmount to first known 1 in LHS.
398 unsigned FirstOne = LHS.countMaxTrailingZeros();
417 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
428 KnownBits KnownBits::ashr(const KnownBits &LHS, const KnownBits &RHS,
430 unsigned BitWidth = LHS.getBitWidth();
431 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {
432 KnownBits Known = LHS;
438 // Fast path for a common case when LHS is completely unknown.
443 if (LHS.isUnknown()) {
456 // If exact, bound MaxShiftAmount to first known 1 in LHS.
458 unsigned FirstOne = LHS.countMaxTrailingZeros();
477 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
488 std::optional<bool> KnownBits::eq(const KnownBits &LHS, const KnownBits &RHS) {
489 if (LHS.isConstant() && RHS.isConstant())
490 return std::optional<bool>(LHS.getConstant() == RHS.getConstant());
491 if (LHS.One.intersects(RHS.Zero) || RHS.One.intersects(LHS.Zero))
496 std::optional<bool> KnownBits::ne(const KnownBits &LHS, const KnownBits &RHS) {
497 if (std::optional<bool> KnownEQ = eq(LHS, RHS))
502 std::optional<bool> KnownBits::ugt(const KnownBits &LHS, const KnownBits &RHS) {
503 // LHS >u RHS -> false if umax(LHS) <= umax(RHS)
504 if (LHS.getMaxValue().ule(RHS.getMinValue()))
506 // LHS >u RHS -> true if umin(LHS) > umax(RHS)
507 if (LHS.getMinValue().ugt(RHS.getMaxValue()))
512 std::optional<bool> KnownBits::uge(const KnownBits &LHS, const KnownBits &RHS) {
513 if (std::optional<bool> IsUGT = ugt(RHS, LHS))
518 std::optional<bool> KnownBits::ult(const KnownBits &LHS, const KnownBits &RHS) {
519 return ugt(RHS, LHS);
522 std::optional<bool> KnownBits::ule(const KnownBits &LHS, const KnownBits &RHS) {
523 return uge(RHS, LHS);
526 std::optional<bool> KnownBits::sgt(const KnownBits &LHS, const KnownBits &RHS) {
527 // LHS >s RHS -> false if smax(LHS) <= smax(RHS)
528 if (LHS.getSignedMaxValue().sle(RHS.getSignedMinValue()))
530 // LHS >s RHS -> true if smin(LHS) > smax(RHS)
531 if (LHS.getSignedMinValue().sgt(RHS.getSignedMaxValue()))
536 std::optional<bool> KnownBits::sge(const KnownBits &LHS, const KnownBits &RHS) {
537 if (std::optional<bool> KnownSGT = sgt(RHS, LHS))
542 std::optional<bool> KnownBits::slt(const KnownBits &LHS, const KnownBits &RHS) {
543 return sgt(RHS, LHS);
546 std::optional<bool> KnownBits::sle(const KnownBits &LHS, const KnownBits &RHS) {
547 return sge(RHS, LHS);
609 const KnownBits &LHS,
613 unsigned BitWidth = LHS.getBitWidth();
624 if (Add && ((LHS.isNegative() && RHS.isNonNegative()) ||
625 (LHS.isNonNegative() && RHS.isNegative())))
627 else if (!Add && (((LHS.isNegative() && RHS.isNegative()) ||
628 (LHS.isNonNegative() && RHS.isNonNegative()))))
633 KnownBits UnsignedLHS = LHS;
635 // Get version of LHS/RHS with clearer signbit. This allows us to detect
637 // using the actual known signbits of LHS/RHS, we can figure out which
651 if (LHS.isNonNegative() && RHS.isNonNegative())
657 if (LHS.isNegative() && RHS.isNegative())
661 if (LHS.isNegative() || RHS.isNegative())
663 if (LHS.isNonNegative() || RHS.isNonNegative())
670 if (LHS.isNegative() && RHS.isNonNegative())
676 if (LHS.isNonNegative() && RHS.isNegative())
680 if (LHS.isNegative() || RHS.isNonNegative())
682 if (LHS.isNonNegative() || RHS.isNegative())
692 (void)LHS.getMaxValue().uadd_ov(RHS.getMaxValue(), Of);
696 (void)LHS.getMinValue().uadd_ov(RHS.getMinValue(), Of);
703 (void)LHS.getMinValue().usub_ov(RHS.getMaxValue(), Of);
707 (void)LHS.getMaxValue().usub_ov(RHS.getMinValue(), Of);
714 /*NUW=*/!Signed, LHS, RHS);
727 assert(!LHS.isSignUnknown() &&
729 C = LHS.isNegative() ? APInt::getSignedMinValue(BitWidth)
765 KnownBits KnownBits::sadd_sat(const KnownBits &LHS, const KnownBits &RHS) {
766 return computeForSatAddSub(/*Add*/ true, /*Signed*/ true, LHS, RHS);
768 KnownBits KnownBits::ssub_sat(const KnownBits &LHS, const KnownBits &RHS) {
769 return computeForSatAddSub(/*Add*/ false, /*Signed*/ true, LHS, RHS);
771 KnownBits KnownBits::uadd_sat(const KnownBits &LHS, const KnownBits &RHS) {
772 return computeForSatAddSub(/*Add*/ true, /*Signed*/ false, LHS, RHS);
774 KnownBits KnownBits::usub_sat(const KnownBits &LHS, const KnownBits &RHS) {
775 return computeForSatAddSub(/*Add*/ false, /*Signed*/ false, LHS, RHS);
778 static KnownBits avgComputeU(KnownBits LHS, KnownBits RHS, bool IsCeil) {
779 unsigned BitWidth = LHS.getBitWidth();
780 LHS = LHS.zext(BitWidth + 1);
782 LHS =
783 computeForAddCarry(LHS, RHS, /*CarryZero*/ !IsCeil, /*CarryOne*/ IsCeil);
784 LHS = LHS.extractBits(BitWidth, 1);
785 return LHS;
788 KnownBits KnownBits::avgFloorS(const KnownBits &LHS, const KnownBits &RHS) {
789 return flipSignBit(avgFloorU(flipSignBit(LHS), flipSignBit(RHS)));
792 KnownBits KnownBits::avgFloorU(const KnownBits &LHS, const KnownBits &RHS) {
793 return avgComputeU(LHS, RHS, /*IsCeil=*/false);
796 KnownBits KnownBits::avgCeilS(const KnownBits &LHS, const KnownBits &RHS) {
797 return flipSignBit(avgCeilU(flipSignBit(LHS), flipSignBit(RHS)));
800 KnownBits KnownBits::avgCeilU(const KnownBits &LHS, const KnownBits &RHS) {
801 return avgComputeU(LHS, RHS, /*IsCeil=*/true);
804 KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS,
806 unsigned BitWidth = LHS.getBitWidth();
808 assert((!NoUndefSelfMultiply || LHS == RHS) &&
816 APInt UMaxLHS = LHS.getMaxValue();
867 const APInt &Bottom0 = LHS.One;
872 unsigned TrailBitsKnown0 = (LHS.Zero | LHS.One).countr_one();
874 unsigned TrailZero0 = LHS.countMinTrailingZeros();
901 KnownBits KnownBits::mulhs(const KnownBits &LHS, const KnownBits &RHS) {
902 unsigned BitWidth = LHS.getBitWidth();
904 KnownBits WideLHS = LHS.sext(2 * BitWidth);
909 KnownBits KnownBits::mulhu(const KnownBits &LHS, const KnownBits &RHS) {
910 unsigned BitWidth = LHS.getBitWidth();
912 KnownBits WideLHS = LHS.zext(2 * BitWidth);
917 static KnownBits divComputeLowBit(KnownBits Known, const KnownBits &LHS,
923 // If LHS is Odd, the result is Odd no matter what.
926 if (LHS.One[0])
930 (int)LHS.countMinTrailingZeros() - (int)RHS.countMaxTrailingZeros();
932 (int)LHS.countMaxTrailingZeros() - (int)RHS.countMinTrailingZeros();
953 KnownBits KnownBits::sdiv(const KnownBits &LHS, const KnownBits &RHS,
956 if (LHS.isNonNegative() && RHS.isNonNegative())
957 return udiv(LHS, RHS, Exact);
959 unsigned BitWidth = LHS.getBitWidth();
962 if (LHS.isZero() || RHS.isZero()) {
970 if (LHS.isNegative() && RHS.isNegative()) {
973 APInt Num = LHS.getSignedMinValue();
979 } else if (LHS.isNegative() && RHS.isNonNegative()) {
980 // Result is negative if Exact OR -LHS u>= RHS.
981 if (Exact || (-LHS.getSignedMaxValue()).uge(RHS.getSignedMaxValue())) {
983 APInt Num = LHS.getSignedMinValue();
986 } else if (LHS.isStrictlyPositive() && RHS.isNegative()) {
987 // Result is negative if Exact OR LHS u>= -RHS.
988 if (Exact || LHS.getSignedMinValue().uge(-RHS.getSignedMinValue())) {
990 APInt Num = LHS.getSignedMaxValue();
1005 Known = divComputeLowBit(Known, LHS, RHS, Exact);
1009 KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS,
1011 unsigned BitWidth = LHS.getBitWidth();
1014 if (LHS.isZero() || RHS.isZero()) {
1025 APInt MaxNum = LHS.getMaxValue();
1031 Known = divComputeLowBit(Known, LHS, RHS, Exact);
1036 KnownBits KnownBits::remGetLowBits(const KnownBits &LHS, const KnownBits &RHS) {
1037 unsigned BitWidth = LHS.getBitWidth();
1042 APInt OnesMask = LHS.One & Mask;
1043 APInt ZerosMask = LHS.Zero & Mask;
1049 KnownBits KnownBits::urem(const KnownBits &LHS, const KnownBits &RHS) {
1050 KnownBits Known = remGetLowBits(LHS, RHS);
1061 std::max(LHS.countMinLeadingZeros(), RHS.countMinLeadingZeros());
1066 KnownBits KnownBits::srem(const KnownBits &LHS, const KnownBits &RHS) {
1067 KnownBits Known = remGetLowBits(LHS, RHS);
1073 if (LHS.isNonNegative() || LowBits.isSubsetOf(LHS.Zero))
1078 if (LHS.isNegative() && LowBits.intersects(LHS.One))
1083 // The sign bit is the LHS's sign bit, except when the result of the
1086 if (LHS.isNegative() && Known.isNonZero())
1088 std::max(LHS.countMinLeadingOnes(), RHS.countMinSignBits()));
1089 else if (LHS.isNonNegative())
1091 std::max(LHS.countMinLeadingZeros(), RHS.countMinSignBits()));