From 03859a465585d5e9dd256c7a0a2855219dc79ed3 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sat, 15 Aug 2026 23:22:46 +0800 Subject: [RISCV][GlobalISel] Match LLVM constant materialization --- .../Target/RISCV/RISCVImmediateMaterialization.cpp | 190 ++++++++++++++------- 1 file changed, 128 insertions(+), 62 deletions(-) (limited to 'backend/lib/Target/RISCV/RISCVImmediateMaterialization.cpp') diff --git a/backend/lib/Target/RISCV/RISCVImmediateMaterialization.cpp b/backend/lib/Target/RISCV/RISCVImmediateMaterialization.cpp index d25a609..a3ed5ac 100644 --- a/backend/lib/Target/RISCV/RISCVImmediateMaterialization.cpp +++ b/backend/lib/Target/RISCV/RISCVImmediateMaterialization.cpp @@ -2,12 +2,14 @@ #include "RISCVImmediateMaterialization.h" -#include +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVSubtarget.h" + #include #include #include -#include #include +#include namespace rcc::riscv { namespace { @@ -19,6 +21,8 @@ namespace { } [[nodiscard]] constexpr std::int64_t signExtend(std::uint64_t Value, std::uint32_t Bits) noexcept { + if (Bits == 64) + return std::bit_cast(Value); const std::uint64_t Mask = (std::uint64_t{1} << Bits) - 1U; const std::uint64_t Sign = std::uint64_t{1} << (Bits - 1U); Value &= Mask; @@ -27,57 +31,93 @@ namespace { return std::bit_cast(Value); } -[[nodiscard]] std::size_t baseBuildCost(std::int64_t Value) noexcept { - const std::uint64_t Bits = static_cast(Value); +[[nodiscard]] constexpr std::uint64_t trailingBitMask(std::uint32_t Bits) noexcept { + return Bits == 64 ? ~std::uint64_t{0} : (std::uint64_t{1} << Bits) - 1U; +} + +[[nodiscard]] constexpr std::int64_t arithmeticShiftRight(std::uint64_t Value, + std::uint32_t Amount) noexcept { + return signExtend(Value >> Amount, 64U - Amount); +} + +void appendImmediate(ImmediateMaterializationSequence &Sequence, InstructionOpcode Opcode, + std::int64_t Immediate, ImmediateMaterializationOperandKind OperandKind) { + Sequence.push_back({.Opcode = Opcode, .Immediate = Immediate, .OperandKind = OperandKind}); +} + +void generateBaseSequence(std::int64_t Value, ImmediateMaterializationSequence &Sequence) { + const std::uint64_t Bits = std::bit_cast(Value); if (fitsSigned(Value, 32)) { - const std::uint64_t High20 = ((Bits + 0x800U) >> 12U) & 0xFFFFFU; + const std::int64_t High20 = static_cast(((Bits + 0x800U) >> 12U) & 0xFFFFFU); const std::int64_t Low12 = signExtend(Bits, 12); - return static_cast(High20 != 0) + - static_cast(Low12 != 0 || High20 == 0); + if (High20 != 0) { + appendImmediate(Sequence, InstructionOpcode::LUI, High20, + ImmediateMaterializationOperandKind::Immediate); + } + if (Low12 != 0 || High20 == 0) { + InstructionOpcode AddOpcode = InstructionOpcode::ADDI; + if (High20 != 0) { + const std::int64_t LUIResult = signExtend(static_cast(High20) << 12U, 32); + if (!fitsSigned(LUIResult + Low12, 32)) + AddOpcode = InstructionOpcode::ADDIW; + } + appendImmediate(Sequence, AddOpcode, Low12, + ImmediateMaterializationOperandKind::RegisterImmediate); + } + return; } const std::int64_t Low12 = signExtend(Bits, 12); const std::uint64_t WithoutLow12 = Bits - static_cast(Low12); std::int64_t Remaining = std::bit_cast(WithoutLow12); - std::uint32_t Shift = 0; + std::uint32_t ShiftAmount = 0; if (!fitsSigned(Remaining, 32)) { - Shift = static_cast(std::countr_zero(WithoutLow12)); - Remaining >>= Shift; - - if (Shift > 12 && !fitsSigned(Remaining, 12)) { - const std::int64_t WithLUILowBits = - std::bit_cast(static_cast(Remaining) << 12U); - if (fitsSigned(WithLUILowBits, 32)) { - Shift -= 12; - Remaining = WithLUILowBits; + ShiftAmount = static_cast(std::countr_zero(WithoutLow12)); + Remaining = arithmeticShiftRight(WithoutLow12, ShiftAmount); + if (ShiftAmount > 12 && !fitsSigned(Remaining, 12)) { + const std::int64_t ShiftedRemaining = + std::bit_cast(std::bit_cast(Remaining) << 12U); + if (fitsSigned(ShiftedRemaining, 32)) { + ShiftAmount -= 12; + Remaining = ShiftedRemaining; } } } - return baseBuildCost(Remaining) + static_cast(Shift != 0) + - static_cast(Low12 != 0); + generateBaseSequence(Remaining, Sequence); + if (ShiftAmount != 0) { + appendImmediate(Sequence, InstructionOpcode::SLLI, static_cast(ShiftAmount), + ImmediateMaterializationOperandKind::RegisterImmediate); + } + if (Low12 != 0) { + appendImmediate(Sequence, InstructionOpcode::ADDI, Low12, + ImmediateMaterializationOperandKind::RegisterImmediate); + } } -[[nodiscard]] std::optional leadingZeroBuildCost(std::uint64_t Value) noexcept { - if (Value == 0 || (Value & (std::uint64_t{1} << 63U)) != 0) - return std::nullopt; - - const std::uint32_t LeadingZeros = static_cast(std::countl_zero(Value)); - const std::uint64_t Shifted = Value << LeadingZeros; - const std::uint64_t LowMask = (std::uint64_t{1} << LeadingZeros) - 1U; - std::optional Best; - for (const std::uint64_t Candidate : {Shifted | LowMask, Shifted}) { - const std::size_t Cost = baseBuildCost(std::bit_cast(Candidate)); - if (Cost >= 8) - continue; - const std::size_t WithShift = Cost + 1U; - Best = Best ? std::min(*Best, WithShift) : WithShift; - } - return Best; +void considerLeadingZeroSequence(std::int64_t Value, ImmediateMaterializationSequence &Sequence) { + const std::uint64_t Bits = std::bit_cast(Value); + const std::uint32_t LeadingZeros = static_cast(std::countl_zero(Bits)); + const std::uint64_t Shifted = Bits << LeadingZeros; + const auto Consider = [&](std::uint64_t Candidate) { + ImmediateMaterializationSequence Temporary; + generateBaseSequence(std::bit_cast(Candidate), Temporary); + const bool Improves = Temporary.size() + 1U < Sequence.size(); + const bool InitializesSequence = Sequence.empty() && Temporary.size() < 8; + if (!Improves && !InitializesSequence) + return; + appendImmediate(Temporary, InstructionOpcode::SRLI, static_cast(LeadingZeros), + ImmediateMaterializationOperandKind::RegisterImmediate); + Sequence = std::move(Temporary); + }; + + Consider(Shifted | trailingBitMask(LeadingZeros)); + Consider(Shifted & ~trailingBitMask(LeadingZeros)); } -[[nodiscard]] std::optional twoRegisterBuildCost(std::int64_t Value) noexcept { - const std::uint64_t Bits = static_cast(Value); +[[nodiscard]] std::optional +twoRegisterBuildCost(std::int64_t Value, const RISCVSubtargetFeatures &Features) { + const std::uint64_t Bits = std::bit_cast(Value); const std::int64_t Low = signExtend(Bits, 32); if (Low == 0) return std::nullopt; @@ -90,49 +130,75 @@ namespace { const std::uint32_t HighZeros = static_cast(std::countr_zero(HighContribution)); if (LowZeros >= 32 || HighZeros < 32 || HighZeros < LowZeros) return std::nullopt; - const std::uint32_t Shift = HighZeros - LowZeros; - if (Shift >= 64 || HighContribution != (static_cast(Low) << Shift)) + const std::uint32_t ShiftAmount = HighZeros - LowZeros; + if (ShiftAmount >= 64 || HighContribution != (static_cast(Low) << ShiftAmount)) { return std::nullopt; - return estimateRV64IntegerBuildCost(Low) + 2U; + } + return generateRV64IntegerMaterialization(Low, Features).size() + 2U; } } // namespace -std::size_t estimateRV64IntegerBuildCost(std::int64_t Value) noexcept { - const std::uint64_t Bits = static_cast(Value); - std::size_t Best = baseBuildCost(Value); +ImmediateMaterializationSequence +generateRV64IntegerMaterialization(std::int64_t Value, const RISCVSubtargetFeatures &Features) { + ImmediateMaterializationSequence Result; + generateBaseSequence(Value, Result); - if ((Bits & 0xFFFU) != 0 && (Bits & 1U) == 0 && Best >= 2) { + const std::uint64_t Bits = std::bit_cast(Value); + if ((Bits & 0xFFFU) != 0 && (Bits & 1U) == 0 && Result.size() >= 2) { const std::uint32_t TrailingZeros = static_cast(std::countr_zero(Bits)); - const std::int64_t Shifted = Value >> TrailingZeros; - const std::size_t Candidate = baseBuildCost(Shifted) + 1U; - if (Candidate < Best || fitsSigned(Shifted, 6)) - Best = Candidate; + const std::int64_t ShiftedValue = arithmeticShiftRight(Bits, TrailingZeros); + ImmediateMaterializationSequence Temporary; + generateBaseSequence(ShiftedValue, Temporary); + const bool PreferCompressibleShift = + fitsSigned(ShiftedValue, 6) && !Features.has(RISCVSubtargetOption::FusionLUIAddImmediate); + if (Temporary.size() + 1U < Result.size() || PreferCompressibleShift) { + appendImmediate(Temporary, InstructionOpcode::SLLI, static_cast(TrailingZeros), + ImmediateMaterializationOperandKind::RegisterImmediate); + Result = std::move(Temporary); + } } - if (Best <= 2) - return Best; + + if (Result.size() <= 2) + return Result; if ((Bits & 0xFFFU) != 0 && (Bits & 0x1800U) == 0x1000U) { const std::int64_t LastAdd = -static_cast(0x800U - (Bits & 0xFFFU)); - const std::uint64_t AdjustedBits = Bits - static_cast(LastAdd); - Best = std::min(Best, baseBuildCost(std::bit_cast(AdjustedBits)) + 1U); + const std::int64_t AdjustedValue = + std::bit_cast(Bits - static_cast(LastAdd)); + ImmediateMaterializationSequence Temporary; + generateBaseSequence(AdjustedValue, Temporary); + if (Temporary.size() + 1U < Result.size()) { + appendImmediate(Temporary, InstructionOpcode::ADDI, LastAdd, + ImmediateMaterializationOperandKind::RegisterImmediate); + Result = std::move(Temporary); + } } - if (Value > 0 && Best > 2) { - if (const auto Candidate = leadingZeroBuildCost(Bits); Candidate && *Candidate < Best) - Best = *Candidate; - } else if (Value < 0 && Best > 3) { - if (const auto Candidate = leadingZeroBuildCost(~Bits); Candidate && *Candidate + 1U < Best) { - Best = *Candidate + 1U; + if (Value > 0 && Result.size() > 2) { + considerLeadingZeroSequence(Value, Result); + } else if (Value < 0 && Result.size() > 3) { + ImmediateMaterializationSequence Temporary; + considerLeadingZeroSequence(std::bit_cast(~Bits), Temporary); + if (!Temporary.empty() && Temporary.size() + 1U < Result.size()) { + appendImmediate(Temporary, InstructionOpcode::XORI, -1, + ImmediateMaterializationOperandKind::RegisterImmediate); + Result = std::move(Temporary); } } - return Best; + return Result; +} + +std::size_t estimateRV64IntegerBuildCost(std::int64_t Value, + const RISCVSubtargetFeatures &Features) { + return generateRV64IntegerMaterialization(Value, Features).size(); } -bool shouldUseRV64IntegerConstantPool(std::int64_t Value, std::size_t MaximumBuildCost) noexcept { - if (fitsSigned(Value, 32) || estimateRV64IntegerBuildCost(Value) <= MaximumBuildCost) +bool shouldUseRV64IntegerConstantPool(std::int64_t Value, const RISCVSubtargetFeatures &Features, + std::size_t MaximumBuildCost) { + if (fitsSigned(Value, 32) || estimateRV64IntegerBuildCost(Value, Features) <= MaximumBuildCost) return false; - const auto TwoRegisterCost = twoRegisterBuildCost(Value); + const auto TwoRegisterCost = twoRegisterBuildCost(Value, Features); return !TwoRegisterCost || *TwoRegisterCost > MaximumBuildCost; } -- cgit v1.2.3