From 1ff4fb953820c823ae8d5035c75bf43bf85e9c3c Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sat, 15 Aug 2026 04:23:23 +0800 Subject: [RISCV][GlobalISel] Legalize scalar bit count operations --- .../lib/CodeGen/GlobalISel/GISelValueTracking.cpp | 199 +++++++++++++++++++++ 1 file changed, 199 insertions(+) (limited to 'backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp') diff --git a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp index f6a0a87..6e045b0 100644 --- a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp +++ b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp @@ -55,6 +55,73 @@ namespace { return Left.bitwiseAnd(Right); } +[[nodiscard]] Expected addMasks(const APInt &Left, const APInt &Right) { + if (Left.bitWidth() == 0 || Left.bitWidth() != Right.bitWidth()) + return makeUnexpected(ErrorCode::InvalidArgument, + "known-bits add operands must have the same nonzero width"); + std::vector Words(Left.words().size(), 0); + unsigned __int128 Carry = 0; + for (std::size_t Index = 0; Index != Words.size(); ++Index) { + const unsigned __int128 Sum = static_cast(Left.word(Index)) + + static_cast(Right.word(Index)) + Carry; + Words[Index] = static_cast(Sum); + Carry = Sum >> 64U; + } + return APInt::create(Left.bitWidth(), Words); +} + +struct MaskProduct final { + APInt Value; + bool Overflow = false; +}; + +[[nodiscard]] Expected multiplyMasks(const APInt &Left, const APInt &Right) { + if (Left.bitWidth() == 0 || Left.bitWidth() != Right.bitWidth()) + return makeUnexpected(ErrorCode::InvalidArgument, + "known-bits multiply operands must have the same nonzero width"); + + const std::size_t WordCount = Left.words().size(); + std::vector Product(WordCount * 2U, 0); + for (std::size_t LeftIndex = 0; LeftIndex != WordCount; ++LeftIndex) { + for (std::size_t RightIndex = 0; RightIndex != WordCount; ++RightIndex) { + const std::size_t ProductIndex = LeftIndex + RightIndex; + const unsigned __int128 Partial = static_cast(Left.word(LeftIndex)) * + static_cast(Right.word(RightIndex)); + unsigned __int128 Sum = static_cast(Product[ProductIndex]) + + static_cast(Partial); + Product[ProductIndex] = static_cast(Sum); + unsigned __int128 Carry = (Partial >> 64U) + (Sum >> 64U); + for (std::size_t Index = ProductIndex + 1U; Carry != 0 && Index != Product.size(); ++Index) { + Sum = static_cast(Product[Index]) + static_cast(Carry); + Product[Index] = static_cast(Sum); + Carry = (Carry >> 64U) + (Sum >> 64U); + } + } + } + + bool Overflow = false; + for (std::size_t Index = WordCount; Index != Product.size(); ++Index) + Overflow |= Product[Index] != 0; + const std::uint32_t HighBits = Left.bitWidth() % 64U; + if (HighBits != 0) { + const std::uint64_t HighMask = (std::uint64_t{1} << HighBits) - 1U; + Overflow |= (Product[WordCount - 1U] & ~HighMask) != 0; + Product[WordCount - 1U] &= HighMask; + } + Product.resize(WordCount); + auto Value = APInt::create(Left.bitWidth(), Product); + if (!Value) + return std::unexpected(Value.error()); + return MaskProduct{.Value = std::move(*Value), .Overflow = Overflow}; +} + +[[nodiscard]] std::uint32_t countTrailingOnes(const APInt &Value) noexcept { + std::uint32_t Count = 0; + while (Count != Value.bitWidth() && Value.testBit(Count)) + ++Count; + return Count; +} + [[nodiscard]] Expected constantAtWidth(const APInt &Value, std::uint32_t BitWidth) { return resizeMask(Value, BitWidth); } @@ -325,6 +392,138 @@ Expected GISelValueTracking::getKnownBits(Registe return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; } + if (Opcode == GenericOpcode::G_ADD) { + const auto Right = registerOperand(*Definition, 2); + if (!Right) + return Unknown; + auto LeftBits = getKnownBits(*Source, Depth + 1U); + if (!LeftBits) + return std::unexpected(LeftBits.error()); + auto RightBits = getKnownBits(*Right, Depth + 1U); + if (!RightBits) + return std::unexpected(RightBits.error()); + + auto LeftMaximum = LeftBits->Zero.bitwiseNot(); + if (!LeftMaximum) + return std::unexpected(LeftMaximum.error()); + auto RightMaximum = RightBits->Zero.bitwiseNot(); + if (!RightMaximum) + return std::unexpected(RightMaximum.error()); + auto PossibleSumZero = addMasks(*LeftMaximum, *RightMaximum); + if (!PossibleSumZero) + return std::unexpected(PossibleSumZero.error()); + auto PossibleSumOne = addMasks(LeftBits->One, RightBits->One); + if (!PossibleSumOne) + return std::unexpected(PossibleSumOne.error()); + + auto CarryKnownZero = PossibleSumZero->bitwiseXor(LeftBits->Zero); + if (!CarryKnownZero) + return std::unexpected(CarryKnownZero.error()); + CarryKnownZero = CarryKnownZero->bitwiseXor(RightBits->Zero); + if (!CarryKnownZero) + return std::unexpected(CarryKnownZero.error()); + CarryKnownZero = CarryKnownZero->bitwiseNot(); + if (!CarryKnownZero) + return std::unexpected(CarryKnownZero.error()); + auto CarryKnownOne = PossibleSumOne->bitwiseXor(LeftBits->One); + if (!CarryKnownOne) + return std::unexpected(CarryKnownOne.error()); + CarryKnownOne = CarryKnownOne->bitwiseXor(RightBits->One); + if (!CarryKnownOne) + return std::unexpected(CarryKnownOne.error()); + + auto LeftKnown = mergeMasks(LeftBits->Zero, LeftBits->One); + if (!LeftKnown) + return std::unexpected(LeftKnown.error()); + auto RightKnown = mergeMasks(RightBits->Zero, RightBits->One); + if (!RightKnown) + return std::unexpected(RightKnown.error()); + auto CarryKnown = mergeMasks(*CarryKnownZero, *CarryKnownOne); + if (!CarryKnown) + return std::unexpected(CarryKnown.error()); + auto Known = intersectMasks(*LeftKnown, *RightKnown); + if (!Known) + return std::unexpected(Known.error()); + Known = intersectMasks(*Known, *CarryKnown); + if (!Known) + return std::unexpected(Known.error()); + + auto NotPossibleSumZero = PossibleSumZero->bitwiseNot(); + if (!NotPossibleSumZero) + return std::unexpected(NotPossibleSumZero.error()); + auto KnownZero = intersectMasks(*NotPossibleSumZero, *Known); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = intersectMasks(*PossibleSumOne, *Known); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + + if (Opcode == GenericOpcode::G_MUL) { + const auto Right = registerOperand(*Definition, 2); + if (!Right) + return Unknown; + auto LeftBits = getKnownBits(*Source, Depth + 1U); + if (!LeftBits) + return std::unexpected(LeftBits.error()); + auto RightBits = getKnownBits(*Right, Depth + 1U); + if (!RightBits) + return std::unexpected(RightBits.error()); + + auto LeftMaximum = LeftBits->Zero.bitwiseNot(); + if (!LeftMaximum) + return std::unexpected(LeftMaximum.error()); + auto RightMaximum = RightBits->Zero.bitwiseNot(); + if (!RightMaximum) + return std::unexpected(RightMaximum.error()); + auto MaximumProduct = multiplyMasks(*LeftMaximum, *RightMaximum); + if (!MaximumProduct) + return std::unexpected(MaximumProduct.error()); + const std::uint32_t LeadingZeroes = + MaximumProduct->Overflow + ? 0 + : BitWidth - static_cast(MaximumProduct->Value.activeBitWidth()); + + auto LeftKnown = mergeMasks(LeftBits->Zero, LeftBits->One); + if (!LeftKnown) + return std::unexpected(LeftKnown.error()); + auto RightKnown = mergeMasks(RightBits->Zero, RightBits->One); + if (!RightKnown) + return std::unexpected(RightKnown.error()); + const std::uint32_t LeftTrailingKnown = countTrailingOnes(*LeftKnown); + const std::uint32_t RightTrailingKnown = countTrailingOnes(*RightKnown); + const std::uint32_t LeftTrailingZeroes = countTrailingOnes(LeftBits->Zero); + const std::uint32_t RightTrailingZeroes = countTrailingOnes(RightBits->Zero); + const std::uint32_t TrailingZeroes = LeftTrailingZeroes + RightTrailingZeroes; + const std::uint32_t SmallestOperand = + std::min(LeftTrailingKnown - LeftTrailingZeroes, RightTrailingKnown - RightTrailingZeroes); + const std::uint32_t ResultBitsKnown = std::min(SmallestOperand + TrailingZeroes, BitWidth); + + auto BottomKnown = multiplyMasks(LeftBits->One, RightBits->One); + if (!BottomKnown) + return std::unexpected(BottomKnown.error()); + auto LowMask = APInt::getLowBitsSet(BitWidth, ResultBitsKnown); + if (!LowMask) + return std::unexpected(LowMask.error()); + auto NotBottomKnown = BottomKnown->Value.bitwiseNot(); + if (!NotBottomKnown) + return std::unexpected(NotBottomKnown.error()); + auto KnownZero = intersectMasks(*NotBottomKnown, *LowMask); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto HighZero = highBitsMask(BitWidth, BitWidth - LeadingZeroes); + if (!HighZero) + return std::unexpected(HighZero.error()); + KnownZero = mergeMasks(*KnownZero, *HighZero); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = intersectMasks(BottomKnown->Value, *LowMask); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + if (Opcode == GenericOpcode::G_SHL || Opcode == GenericOpcode::G_LSHR || Opcode == GenericOpcode::G_ASHR) { const auto AmountReg = registerOperand(*Definition, 2); -- cgit v1.2.3