diff options
Diffstat (limited to 'backend/lib')
5 files changed, 246 insertions, 196 deletions
diff --git a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp index a868b0e..0d68cc3 100644 --- a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp +++ b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp @@ -1,6 +1,7 @@ // SPDX-License-Identifier: GPL-3.0-or-later #include "RISCV.h" +#include "RISCVImmediateMaterialization.h" #include "RISCVRegisterBankInfo.h" #include "rcc/CodeGen/GenericOpcodes.h" #include "rcc/CodeGen/GlobalISel/InstructionSelector.h" @@ -96,12 +97,6 @@ operandType(const MachineFunction &Function, const MachineInstr &Instruction, st return *Info->get().Bank; } -[[nodiscard]] bool fitsSigned(std::int64_t Value, std::uint32_t Bits) noexcept { - const std::int64_t Minimum = -(std::int64_t{1} << (Bits - 1U)); - const std::int64_t Maximum = (std::int64_t{1} << (Bits - 1U)) - 1; - return Value >= Minimum && Value <= Maximum; -} - [[nodiscard]] std::optional<std::uint64_t> memoryAccessBytes(const MachineInstr &Instruction) noexcept { if (Instruction.memOperands().size() != 1) @@ -645,6 +640,34 @@ private: } [[nodiscard]] Expected<MachineInstr *> + buildImmediateOnlyAfter(MachineIRBuilder &Builder, MachineInstr &Anchor, InstructionOpcode Opcode, + Register Def, std::int64_t Value) const { + auto Point = Builder.setInsertPointAfter(Anchor); + if (!Point) + return std::unexpected(Point.error()); + auto RegisterConstraints = + constrainBuilderRegisters(Builder.function(), Builder.target(), {Def}); + if (!RegisterConstraints) + return std::unexpected(RegisterConstraints.error()); + auto Pending = Builder.buildInstr(instructionOpcode(Opcode)); + if (!Pending) + return std::unexpected(Pending.error()); + auto DefResult = Pending->addDef(Def); + if (!DefResult) + return std::unexpected(DefResult.error()); + auto ImmediateResult = Pending->addImmediate(Value); + if (!ImmediateResult) + return std::unexpected(ImmediateResult.error()); + auto Built = Pending->build(); + if (!Built) + return std::unexpected(Built.error()); + auto Constraint = constrainSelectedInstruction(**Built, Builder.function(), Builder.target()); + if (!Constraint) + return std::unexpected(Constraint.error()); + return *Built; + } + + [[nodiscard]] Expected<MachineInstr *> buildImmediateBefore(MachineIRBuilder &Builder, MachineInstr &Anchor, InstructionOpcode Opcode, Register Def, Register Source, std::int64_t Value) const { auto Point = Builder.setInsertPointBefore(Anchor); @@ -2435,137 +2458,75 @@ private: if (!DestinationConstraint) return std::unexpected(DestinationConstraint.error()); const std::int64_t Value = *ImmediateValue; - const std::uint32_t ImmediateTargetFlags = ImmediateOperand->targetFlags(); - const bool IsWord = Type->isCategoryNeutralScalar() && Type->scalarBitWidth() <= 32; - const InstructionOpcode AddImmediate = - IsWord ? InstructionOpcode::ADDIW : InstructionOpcode::ADDI; - const InstructionOpcode ShiftLeftImmediate = - IsWord ? InstructionOpcode::SLLIW : InstructionOpcode::SLLI; - if (fitsSigned(Value, 12)) { - auto Zero = physicalRegister(PhysicalRegisterID::X0); - if (!Zero) - return std::unexpected(Zero.error()); + auto Zero = physicalRegister(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + if (Value == 0) { + auto EraseImmediate = Instruction.eraseOperand(1); + if (!EraseImmediate) + return std::unexpected(EraseImmediate.error()); auto Source = insertPhysicalRegister(Instruction, 1, *Zero, RegisterOperandFlag::Use); if (!Source) return std::unexpected(Source.error()); - auto EraseImmediate = Instruction.eraseOperand(2); - if (!EraseImmediate) - return std::unexpected(EraseImmediate.error()); - auto NormalizeImmediate = - Instruction.insertOperand(2, MachineOperand::immediate(Value, ImmediateTargetFlags)); - if (!NormalizeImmediate) - return std::unexpected(NormalizeImmediate.error()); - return Instruction.setOpcode(instructionOpcode(AddImmediate)); + return Instruction.setOpcode(opcode(GenericOpcode::COPY)); } - // Recursively decompose the value into signed 12-bit chunks. The - // quotient is computed from an unsigned bit pattern with explicit sign - // extension so both INT64_MIN and INT64_MAX remain well-defined. - std::uint64_t Remaining = static_cast<std::uint64_t>(Value); - std::vector<std::int64_t> Digits; - while (!fitsSigned(std::bit_cast<std::int64_t>(Remaining), 12)) { - const std::uint64_t LowBits = Remaining & 0xFFFU; - std::int64_t Digit = static_cast<std::int64_t>(LowBits); - if (Digit >= 0x800) - Digit -= 0x1000; - Digits.push_back(Digit); - - const std::uint64_t Adjusted = Remaining - static_cast<std::uint64_t>(Digit); - std::uint64_t Quotient = Adjusted >> 12U; - if ((Remaining & (std::uint64_t{1} << 63U)) != 0) - Quotient |= ~std::uint64_t{0} << 52U; - Remaining = Quotient; + ImmediateMaterializationSequence Sequence = + generateRV64IntegerMaterialization(Value, Subtarget.features()); + if (Sequence.empty()) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V integer materialization produced an empty sequence"); + } + Register Current = Destination; + if (Sequence.size() != 1) { + auto Temporary = createTemporary(Function, *Type, Target); + if (!Temporary) + return std::unexpected(Temporary.error()); + Current = *Temporary; } - const std::int64_t Base = std::bit_cast<std::int64_t>(Remaining); - auto Temporary = createTemporary(Function, *Type, Target); - if (!Temporary) - return std::unexpected(Temporary.error()); - auto *Parent = Instruction.parent(); - if (Parent == nullptr) - return makeUnexpected(ErrorCode::VerificationError, - "RISC-V constant selection received a detached instruction"); - auto SetOpcode = Instruction.setOpcode(instructionOpcode(AddImmediate)); - if (!SetOpcode) - return std::unexpected(SetOpcode.error()); - auto SetDestination = Instruction.operandAt(0)->setRegister(*Temporary); - if (!SetDestination) - return std::unexpected(SetDestination.error()); - auto EraseImmediate = Instruction.eraseOperand(1); - if (!EraseImmediate) - return std::unexpected(EraseImmediate.error()); - auto Zero = physicalRegister(PhysicalRegisterID::X0); - if (!Zero) - return std::unexpected(Zero.error()); - auto AddSource = insertPhysicalRegister(Instruction, 1, *Zero, RegisterOperandFlag::Use); - if (!AddSource) - return std::unexpected(AddSource.error()); - auto AddBase = appendImmediate(Instruction, Base); - if (!AddBase) - return std::unexpected(AddBase.error()); + const auto SelectHead = [&](const ImmediateMaterializationInstruction &Step, + Register Definition) -> Expected<void> { + auto SetOpcode = Instruction.setOpcode(instructionOpcode(Step.Opcode)); + if (!SetOpcode) + return std::unexpected(SetOpcode.error()); + auto SetDestination = Instruction.operandAt(0)->setRegister(Definition); + if (!SetDestination) + return std::unexpected(SetDestination.error()); + auto EraseImmediate = Instruction.eraseOperand(1); + if (!EraseImmediate) + return std::unexpected(EraseImmediate.error()); + if (Step.OperandKind == ImmediateMaterializationOperandKind::Immediate) + return Instruction.addOperand(MachineOperand::immediate(Step.Immediate)); + auto Source = insertPhysicalRegister(Instruction, 1, *Zero, RegisterOperandFlag::Use); + if (!Source) + return std::unexpected(Source.error()); + return Instruction.addOperand(MachineOperand::immediate(Step.Immediate)); + }; + auto Head = SelectHead(Sequence.front(), Current); + if (!Head) + return std::unexpected(Head.error()); MachineIRBuilder Builder(Function, Target); - auto InsertPoint = Builder.setInsertPointAfter(Instruction); - if (!InsertPoint) - return std::unexpected(InsertPoint.error()); - - Register Current = *Temporary; - for (std::size_t Reverse = Digits.size(); Reverse != 0; --Reverse) { - const std::size_t Index = Reverse - 1U; - auto ShiftResult = createTemporary(Function, *Type, Target); - if (!ShiftResult) - return std::unexpected(ShiftResult.error()); - auto Shift = Builder.buildInstr(instructionOpcode(ShiftLeftImmediate)); - if (!Shift) - return std::unexpected(Shift.error()); - auto ShiftDef = Shift->addDef(*ShiftResult); - if (!ShiftDef) - return std::unexpected(ShiftDef.error()); - auto ShiftUse = Shift->addUse(Current); - if (!ShiftUse) - return std::unexpected(ShiftUse.error()); - auto ShiftAmount = Shift->addImmediate(12); - if (!ShiftAmount) - return std::unexpected(ShiftAmount.error()); - auto BuiltShift = Shift->build(); - if (!BuiltShift) - return std::unexpected(BuiltShift.error()); - auto ShiftConstraint = constrainSelectedInstruction(**BuiltShift, Function, Target); - if (!ShiftConstraint) - return std::unexpected(ShiftConstraint.error()); - - const bool IsFinal = Index == 0; - Register AddDestination; - if (IsFinal) { - AddDestination = Destination; - } else { - auto AddTemporary = createTemporary(Function, *Type, Target); - if (!AddTemporary) - return std::unexpected(AddTemporary.error()); - AddDestination = *AddTemporary; + MachineInstr *Anchor = &Instruction; + for (std::size_t Index = 1; Index < Sequence.size(); ++Index) { + const bool IsFinal = Index + 1U == Sequence.size(); + Register Next = Destination; + if (!IsFinal) { + auto Temporary = createTemporary(Function, *Type, Target); + if (!Temporary) + return std::unexpected(Temporary.error()); + Next = *Temporary; } - auto Add = Builder.setInsertPointAfter(**BuiltShift); - if (!Add) - return std::unexpected(Add.error()); - auto AddInstruction = Builder.buildInstr(instructionOpcode(AddImmediate)); - if (!AddInstruction) - return std::unexpected(AddInstruction.error()); - auto AddDef = AddInstruction->addDef(AddDestination); - if (!AddDef) - return std::unexpected(AddDef.error()); - auto AddUse = AddInstruction->addUse(*ShiftResult); - if (!AddUse) - return std::unexpected(AddUse.error()); - auto AddImmediateResult = AddInstruction->addImmediate(Digits[Index]); - if (!AddImmediateResult) - return std::unexpected(AddImmediateResult.error()); - auto BuiltAdd = AddInstruction->build(); - if (!BuiltAdd) - return std::unexpected(BuiltAdd.error()); - auto AddConstraint = constrainSelectedInstruction(**BuiltAdd, Function, Target); - if (!AddConstraint) - return std::unexpected(AddConstraint.error()); - Current = AddDestination; + const ImmediateMaterializationInstruction &Step = Sequence[Index]; + Expected<MachineInstr *> Built = + Step.OperandKind == ImmediateMaterializationOperandKind::Immediate + ? buildImmediateOnlyAfter(Builder, *Anchor, Step.Opcode, Next, Step.Immediate) + : buildImmediateAfter(Builder, *Anchor, Step.Opcode, Next, Current, Step.Immediate); + if (!Built) + return std::unexpected(Built.error()); + Anchor = *Built; + Current = Next; } return {}; } diff --git a/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp b/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp index 6e4bb76..5d0be47 100644 --- a/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp +++ b/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp @@ -1261,7 +1261,7 @@ Expected<void> RISCVLegalizerInfo::legalizeCustom(LegalizerHelper &Helper, if (Immediate != nullptr && Type && Type->isCategoryNeutralScalar() && Type->scalarBitWidth() == 64) { auto Value = signedImmediate(*Immediate); - if (Value && shouldUseRV64IntegerConstantPool(*Value)) { + if (Value && shouldUseRV64IntegerConstantPool(*Value, Subtarget.features())) { Helper.Observer.changingInstr(Instruction); auto Lowered = lowerConstantToPool(Instruction, Function, Target); if (!Lowered) diff --git a/backend/lib/Target/RISCV/RISCV.rccdesc b/backend/lib/Target/RISCV/RISCV.rccdesc index 4896229..832e8c1 100644 --- a/backend/lib/Target/RISCV/RISCV.rccdesc +++ b/backend/lib/Target/RISCV/RISCV.rccdesc @@ -446,7 +446,7 @@ named_operands: immediate_predicates: - { id: 1, symbol: SIMM12, name: simm12, kind: signed, bits: 12 } - - { id: 2, symbol: SIMM20, name: simm20, kind: signed, bits: 20 } + - { id: 2, symbol: UIMM20, name: uimm20, kind: unsigned, bits: 20 } - { id: 3, symbol: UIMM5, name: uimm5, kind: unsigned, bits: 5 } - { id: 4, symbol: UIMM6, name: uimm6, kind: unsigned, bits: 6 } - { id: 5, symbol: UIMM12, name: uimm12, kind: unsigned, bits: 12 } @@ -538,7 +538,7 @@ instructions: encoding: 5175 operands: - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, name: RD } - - { kinds: [immediate, constant_pool_index, jump_table_index, global_symbol, external_symbol, block_address, mc_symbol], immediate_predicate: SIMM20, allowed_target_flags: 32, name: IMM } + - { kinds: [immediate, constant_pool_index, jump_table_index, global_symbol, external_symbol, block_address, mc_symbol], immediate_predicate: UIMM20, allowed_target_flags: 32, name: IMM } num_explicit_defs: 1 flags: [produces_code, rematerializable] scheduling_class: ALU @@ -552,7 +552,7 @@ instructions: encoding: 5143 operands: - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, name: RD } - - { kinds: [immediate, basic_block, global_symbol, external_symbol, mc_symbol], immediate_predicate: SIMM20, allowed_target_flags: 3, name: IMM } + - { kinds: [immediate, basic_block, global_symbol, external_symbol, mc_symbol], immediate_predicate: UIMM20, allowed_target_flags: 3, name: IMM } num_explicit_defs: 1 flags: [produces_code] scheduling_class: ALU 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 <algorithm> +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVSubtarget.h" + #include <bit> #include <cstddef> #include <cstdint> -#include <limits> #include <optional> +#include <utility> 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<std::int64_t>(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<std::int64_t>(Value); } -[[nodiscard]] std::size_t baseBuildCost(std::int64_t Value) noexcept { - const std::uint64_t Bits = static_cast<std::uint64_t>(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<std::uint64_t>(Value); if (fitsSigned(Value, 32)) { - const std::uint64_t High20 = ((Bits + 0x800U) >> 12U) & 0xFFFFFU; + const std::int64_t High20 = static_cast<std::int64_t>(((Bits + 0x800U) >> 12U) & 0xFFFFFU); const std::int64_t Low12 = signExtend(Bits, 12); - return static_cast<std::size_t>(High20 != 0) + - static_cast<std::size_t>(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<std::uint64_t>(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<std::uint64_t>(Low12); std::int64_t Remaining = std::bit_cast<std::int64_t>(WithoutLow12); - std::uint32_t Shift = 0; + std::uint32_t ShiftAmount = 0; if (!fitsSigned(Remaining, 32)) { - Shift = static_cast<std::uint32_t>(std::countr_zero(WithoutLow12)); - Remaining >>= Shift; - - if (Shift > 12 && !fitsSigned(Remaining, 12)) { - const std::int64_t WithLUILowBits = - std::bit_cast<std::int64_t>(static_cast<std::uint64_t>(Remaining) << 12U); - if (fitsSigned(WithLUILowBits, 32)) { - Shift -= 12; - Remaining = WithLUILowBits; + ShiftAmount = static_cast<std::uint32_t>(std::countr_zero(WithoutLow12)); + Remaining = arithmeticShiftRight(WithoutLow12, ShiftAmount); + if (ShiftAmount > 12 && !fitsSigned(Remaining, 12)) { + const std::int64_t ShiftedRemaining = + std::bit_cast<std::int64_t>(std::bit_cast<std::uint64_t>(Remaining) << 12U); + if (fitsSigned(ShiftedRemaining, 32)) { + ShiftAmount -= 12; + Remaining = ShiftedRemaining; } } } - return baseBuildCost(Remaining) + static_cast<std::size_t>(Shift != 0) + - static_cast<std::size_t>(Low12 != 0); + generateBaseSequence(Remaining, Sequence); + if (ShiftAmount != 0) { + appendImmediate(Sequence, InstructionOpcode::SLLI, static_cast<std::int64_t>(ShiftAmount), + ImmediateMaterializationOperandKind::RegisterImmediate); + } + if (Low12 != 0) { + appendImmediate(Sequence, InstructionOpcode::ADDI, Low12, + ImmediateMaterializationOperandKind::RegisterImmediate); + } } -[[nodiscard]] std::optional<std::size_t> 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::uint32_t>(std::countl_zero(Value)); - const std::uint64_t Shifted = Value << LeadingZeros; - const std::uint64_t LowMask = (std::uint64_t{1} << LeadingZeros) - 1U; - std::optional<std::size_t> Best; - for (const std::uint64_t Candidate : {Shifted | LowMask, Shifted}) { - const std::size_t Cost = baseBuildCost(std::bit_cast<std::int64_t>(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<std::uint64_t>(Value); + const std::uint32_t LeadingZeros = static_cast<std::uint32_t>(std::countl_zero(Bits)); + const std::uint64_t Shifted = Bits << LeadingZeros; + const auto Consider = [&](std::uint64_t Candidate) { + ImmediateMaterializationSequence Temporary; + generateBaseSequence(std::bit_cast<std::int64_t>(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<std::int64_t>(LeadingZeros), + ImmediateMaterializationOperandKind::RegisterImmediate); + Sequence = std::move(Temporary); + }; + + Consider(Shifted | trailingBitMask(LeadingZeros)); + Consider(Shifted & ~trailingBitMask(LeadingZeros)); } -[[nodiscard]] std::optional<std::size_t> twoRegisterBuildCost(std::int64_t Value) noexcept { - const std::uint64_t Bits = static_cast<std::uint64_t>(Value); +[[nodiscard]] std::optional<std::size_t> +twoRegisterBuildCost(std::int64_t Value, const RISCVSubtargetFeatures &Features) { + const std::uint64_t Bits = std::bit_cast<std::uint64_t>(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::uint32_t>(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<std::uint64_t>(Low) << Shift)) + const std::uint32_t ShiftAmount = HighZeros - LowZeros; + if (ShiftAmount >= 64 || HighContribution != (static_cast<std::uint64_t>(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<std::uint64_t>(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<std::uint64_t>(Value); + if ((Bits & 0xFFFU) != 0 && (Bits & 1U) == 0 && Result.size() >= 2) { const std::uint32_t TrailingZeros = static_cast<std::uint32_t>(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<std::int64_t>(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<std::int64_t>(0x800U - (Bits & 0xFFFU)); - const std::uint64_t AdjustedBits = Bits - static_cast<std::uint64_t>(LastAdd); - Best = std::min(Best, baseBuildCost(std::bit_cast<std::int64_t>(AdjustedBits)) + 1U); + const std::int64_t AdjustedValue = + std::bit_cast<std::int64_t>(Bits - static_cast<std::uint64_t>(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<std::int64_t>(~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; } diff --git a/backend/lib/Target/RISCV/RISCVImmediateMaterialization.h b/backend/lib/Target/RISCV/RISCVImmediateMaterialization.h index e38f752..4d58ec2 100644 --- a/backend/lib/Target/RISCV/RISCVImmediateMaterialization.h +++ b/backend/lib/Target/RISCV/RISCVImmediateMaterialization.h @@ -5,15 +5,38 @@ #include <cstddef> #include <cstdint> +#include <vector> namespace rcc::riscv { +enum class InstructionOpcode : std::uint32_t; +class RISCVSubtargetFeatures; + +enum class ImmediateMaterializationOperandKind : std::uint8_t { + Immediate, + RegisterImmediate, +}; + +struct ImmediateMaterializationInstruction final { + InstructionOpcode Opcode; + std::int64_t Immediate = 0; + ImmediateMaterializationOperandKind OperandKind = + ImmediateMaterializationOperandKind::RegisterImmediate; +}; + +using ImmediateMaterializationSequence = std::vector<ImmediateMaterializationInstruction>; + inline constexpr std::size_t DefaultRV64IntegerBuildCost = 5; -[[nodiscard]] std::size_t estimateRV64IntegerBuildCost(std::int64_t Value) noexcept; +[[nodiscard]] ImmediateMaterializationSequence +generateRV64IntegerMaterialization(std::int64_t Value, const RISCVSubtargetFeatures &Features); + +[[nodiscard]] std::size_t estimateRV64IntegerBuildCost(std::int64_t Value, + const RISCVSubtargetFeatures &Features); -[[nodiscard]] bool shouldUseRV64IntegerConstantPool( - std::int64_t Value, std::size_t MaximumBuildCost = DefaultRV64IntegerBuildCost) noexcept; +[[nodiscard]] bool +shouldUseRV64IntegerConstantPool(std::int64_t Value, const RISCVSubtargetFeatures &Features, + std::size_t MaximumBuildCost = DefaultRV64IntegerBuildCost); } // namespace rcc::riscv |