diff options
Diffstat (limited to 'backend/lib/Target/RISCV/RISCVInstrInfo.cpp')
| -rw-r--r-- | backend/lib/Target/RISCV/RISCVInstrInfo.cpp | 1441 |
1 files changed, 1441 insertions, 0 deletions
diff --git a/backend/lib/Target/RISCV/RISCVInstrInfo.cpp b/backend/lib/Target/RISCV/RISCVInstrInfo.cpp new file mode 100644 index 0000000..6e356a6 --- /dev/null +++ b/backend/lib/Target/RISCV/RISCVInstrInfo.cpp @@ -0,0 +1,1441 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "RISCVInstrInfo.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVRegisters.h" +#include "rcc/Target/RISCV/RISCVTarget.h" + +#include <algorithm> +#include <array> +#include <charconv> +#include <cstddef> +#include <cstdint> +#include <limits> +#include <optional> +#include <string> +#include <utility> +#include <vector> + +namespace rcc::riscv { +namespace { + +constexpr std::uint32_t PCRelativeHighFlag = 2; +constexpr std::uint32_t PCRelativeLowFlag = 4; + +[[nodiscard]] bool isAsmSpace(char Value) noexcept { + return Value == ' ' || Value == '\t' || Value == '\r' || Value == '\f' || Value == '\v'; +} + +[[nodiscard]] std::string_view trimAsmSpace(std::string_view Text) noexcept { + while (!Text.empty() && isAsmSpace(Text.front())) + Text.remove_prefix(1); + while (!Text.empty() && isAsmSpace(Text.back())) + Text.remove_suffix(1); + return Text; +} + +[[nodiscard]] Expected<std::uint32_t> inlineAsmSize(const MachineInstr &Instruction) { + const MachineOperand *Operand = Instruction.operandAt(0); + const auto *Symbol = Operand == nullptr ? nullptr : Operand->getIf<ExternalSymbolOperand>(); + if (Symbol == nullptr) + return makeUnexpected(ErrorCode::VerificationError, "RISC-V INLINEASM has no assembly text"); + + std::uint64_t Size = 0; + std::string_view Remaining = Symbol->Name; + while (!Remaining.empty()) { + const std::size_t Separator = Remaining.find_first_of("\n;"); + std::string_view Statement = trimAsmSpace(Remaining.substr(0, Separator)); + Remaining = + Separator == std::string_view::npos ? std::string_view{} : Remaining.substr(Separator + 1U); + if (Statement.empty() || Statement.front() == '#') + continue; + + std::uint64_t StatementSize = 4; + constexpr std::string_view SpaceDirective = ".space"; + if (Statement.starts_with(SpaceDirective) && (Statement.size() == SpaceDirective.size() || + isAsmSpace(Statement[SpaceDirective.size()]))) { + std::string_view Argument = trimAsmSpace(Statement.substr(SpaceDirective.size())); + std::int64_t Count = 0; + const auto Parsed = + std::from_chars(Argument.data(), Argument.data() + Argument.size(), Count); + if (Parsed.ec == std::errc{}) { + std::string_view Trailing( + Parsed.ptr, static_cast<std::size_t>(Argument.data() + Argument.size() - Parsed.ptr)); + Trailing = trimAsmSpace(Trailing); + if (Trailing.empty() || Trailing.front() == '#') + StatementSize = Count < 0 ? 0 : static_cast<std::uint64_t>(Count); + } + } + if (StatementSize > std::numeric_limits<std::uint32_t>::max() - Size) + return makeUnexpected(ErrorCode::VerificationError, "RISC-V INLINEASM size overflowed"); + Size += StatementSize; + } + return static_cast<std::uint32_t>(Size); +} + +[[nodiscard]] bool isConditionalBranch(Opcode Value) noexcept { + return Value == instructionOpcode(InstructionOpcode::BEQ) || + Value == instructionOpcode(InstructionOpcode::BNE) || + Value == instructionOpcode(InstructionOpcode::BLT) || + Value == instructionOpcode(InstructionOpcode::BGE) || + Value == instructionOpcode(InstructionOpcode::BLTU) || + Value == instructionOpcode(InstructionOpcode::BGEU) || + Value == instructionOpcode(InstructionOpcode::C_BEQZ) || + Value == instructionOpcode(InstructionOpcode::C_BNEZ); +} + +[[nodiscard]] std::optional<Opcode> reversedOpcode(Opcode Value) noexcept { + constexpr std::array<std::pair<InstructionOpcode, InstructionOpcode>, 4> Pairs = {{ + {InstructionOpcode::BEQ, InstructionOpcode::BNE}, + {InstructionOpcode::BLT, InstructionOpcode::BGE}, + {InstructionOpcode::BLTU, InstructionOpcode::BGEU}, + {InstructionOpcode::C_BEQZ, InstructionOpcode::C_BNEZ}, + }}; + for (const auto &[Left, Right] : Pairs) { + if (Value == instructionOpcode(Left)) + return instructionOpcode(Right); + if (Value == instructionOpcode(Right)) + return instructionOpcode(Left); + } + return std::nullopt; +} + +[[nodiscard]] bool isZeroRegister(const MachineOperand *Operand) noexcept { + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>(); + const std::optional<PhysicalRegister> Physical = + Reg == nullptr ? std::nullopt : Reg->physicalRegister(); + return Physical && Physical->number() == static_cast<std::uint32_t>(PhysicalRegisterID::X0); +} + +[[nodiscard]] bool sameRegister(const MachineOperand *Left, const MachineOperand *Right) noexcept { + const Register *LeftReg = Left == nullptr ? nullptr : Left->getIf<Register>(); + const Register *RightReg = Right == nullptr ? nullptr : Right->getIf<Register>(); + return LeftReg != nullptr && RightReg != nullptr && *LeftReg == *RightReg && + Left->subReg() == Right->subReg(); +} + +[[nodiscard]] bool isPhysicalRegister(const MachineOperand *Operand, + PhysicalRegisterID Expected) noexcept { + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>(); + const std::optional<PhysicalRegister> Physical = + Reg == nullptr ? std::nullopt : Reg->physicalRegister(); + return Physical && Physical->number() == static_cast<std::uint32_t>(Expected); +} + +[[nodiscard]] Expected<void> swapRegisters(MachineOperand &Left, MachineOperand &Right) { + const Register *LeftReg = Left.getIf<Register>(); + const Register *RightReg = Right.getIf<Register>(); + if (LeftReg == nullptr || RightReg == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "register swap requires two registers"); + const Register LeftValue = *LeftReg; + const Register RightValue = *RightReg; + const RegisterOperandFlags LeftFlags = Left.registerFlags(); + const RegisterOperandFlags RightFlags = Right.registerFlags(); + const SubRegIndex LeftSubReg = Left.subReg(); + const SubRegIndex RightSubReg = Right.subReg(); + const std::uint32_t LeftTargetFlags = Left.targetFlags(); + const std::uint32_t RightTargetFlags = Right.targetFlags(); + auto SetLeft = Left.setRegister(RightValue); + if (!SetLeft) + return std::unexpected(SetLeft.error()); + auto SetRight = Right.setRegister(LeftValue); + if (!SetRight) + return std::unexpected(SetRight.error()); + SetLeft = Left.setRegisterFlags(RightFlags); + if (!SetLeft) + return std::unexpected(SetLeft.error()); + SetRight = Right.setRegisterFlags(LeftFlags); + if (!SetRight) + return std::unexpected(SetRight.error()); + SetLeft = Left.setSubReg(RightSubReg); + if (!SetLeft) + return std::unexpected(SetLeft.error()); + SetRight = Right.setSubReg(LeftSubReg); + if (!SetRight) + return std::unexpected(SetRight.error()); + Left.setTargetFlags(RightTargetFlags); + Right.setTargetFlags(LeftTargetFlags); + return {}; +} + +[[nodiscard]] bool isUnconditionalBranch(const MachineInstr &Instruction) noexcept { + if (Instruction.opcode() == instructionOpcode(InstructionOpcode::C_J) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::PseudoBR)) { + return true; + } + return Instruction.opcode() == instructionOpcode(InstructionOpcode::JAL) && + isZeroRegister(Instruction.operandAt(0)); +} + +[[nodiscard]] std::size_t branchTargetIndex(Opcode Value) noexcept { + if (Value == instructionOpcode(InstructionOpcode::C_J) || + Value == instructionOpcode(InstructionOpcode::PseudoBR)) { + return 0; + } + if (Value == instructionOpcode(InstructionOpcode::C_BEQZ) || + Value == instructionOpcode(InstructionOpcode::C_BNEZ)) { + return 1; + } + if (Value == instructionOpcode(InstructionOpcode::JAL)) + return 1; + return 2; +} + +[[nodiscard]] Expected<MachineBasicBlock *> directTarget(MachineInstr &Instruction) { + if (!isConditionalBranch(Instruction.opcode()) && + Instruction.opcode() != instructionOpcode(InstructionOpcode::JAL) && + Instruction.opcode() != instructionOpcode(InstructionOpcode::C_J) && + Instruction.opcode() != instructionOpcode(InstructionOpcode::PseudoBR)) { + return static_cast<MachineBasicBlock *>(nullptr); + } + MachineOperand *Operand = Instruction.operandAt(branchTargetIndex(Instruction.opcode())); + const BasicBlockOperand *Block = + Operand == nullptr ? nullptr : Operand->getIf<BasicBlockOperand>(); + if (Block == nullptr || Block->Block == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V direct branch has no basic-block target"); + } + return Block->Block; +} + +[[nodiscard]] Expected<void> setDirectTarget(MachineInstr &Instruction, + MachineBasicBlock &TargetBlock) { + MachineOperand *Operand = Instruction.operandAt(branchTargetIndex(Instruction.opcode())); + if (Operand == nullptr || Operand->kind() != MachineOperand::Kind::BasicBlock) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V direct branch has no mutable basic-block target"); + } + return Operand->setBasicBlock(TargetBlock); +} + +[[nodiscard]] Expected<MachineInstr *> +buildJAL(MachineFunction &Function, const TargetDescription &Target, MachineBasicBlock &Block, + MachineInstr *Before, PhysicalRegister Destination, MachineBasicBlock &TargetBlock) { + MachineIRBuilder Builder(Function, Target); + Expected<void> Point = + Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(instructionOpcode(InstructionOpcode::JAL)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Register::fromPhysical(Destination)); + if (!Def) + return std::unexpected(Def.error()); + auto TargetOperand = Pending->addBasicBlock(TargetBlock); + if (!TargetOperand) + return std::unexpected(TargetOperand.error()); + return Pending->build(); +} + +[[nodiscard]] Expected<void> copySourceIdentity(const MachineInstr &Source, + MachineInstr &Destination) { + if (Source.sourceLocation()) + Destination.setSourceLocation(*Source.sourceLocation()); + if (Source.debugLocation()) { + auto Debug = Destination.setDebugLocation(*Source.debugLocation()); + if (!Debug) + return std::unexpected(Debug.error()); + } + if (Source.origin()) + Destination.setOrigin(*Source.origin()); + return {}; +} + +[[nodiscard]] Expected<void> copyTrailingAnnotations(const MachineInstr &Source, + MachineInstr &Destination) { + if (Source.debugInstrNumber() != 0) { + auto DebugNumber = Destination.setDebugInstrNumber(Source.debugInstrNumber()); + if (!DebugNumber) + return std::unexpected(DebugNumber.error()); + } + if (Source.postInstrSymbol()) { + auto Symbol = Destination.setPostInstrSymbol(std::string(*Source.postInstrSymbol())); + if (!Symbol) + return std::unexpected(Symbol.error()); + } + if (Source.heapAllocMarker()) { + auto Marker = Destination.setHeapAllocMarker(*Source.heapAllocMarker()); + if (!Marker) + return std::unexpected(Marker.error()); + } + if (Source.pcSections()) { + auto Sections = Destination.setPCSections(*Source.pcSections()); + if (!Sections) + return std::unexpected(Sections.error()); + } + if (Source.mmra()) { + auto Metadata = Destination.setMMRA(*Source.mmra()); + if (!Metadata) + return std::unexpected(Metadata.error()); + } + if (Source.cfiType()) { + auto Type = Destination.setCFIType(*Source.cfiType()); + if (!Type) + return std::unexpected(Type.error()); + } + if (Source.deactivationSymbol()) { + auto Symbol = Destination.setDeactivationSymbol(std::string(*Source.deactivationSymbol())); + if (!Symbol) + return std::unexpected(Symbol.error()); + } + return {}; +} + +[[nodiscard]] Expected<void> copySingleInstructionAnnotations(const MachineInstr &Source, + MachineInstr &Destination) { + Destination.setFlags(Source.flags()); + auto Identity = copySourceIdentity(Source, Destination); + if (!Identity) + return std::unexpected(Identity.error()); + if (Source.preInstrSymbol()) { + auto Symbol = Destination.setPreInstrSymbol(std::string(*Source.preInstrSymbol())); + if (!Symbol) + return std::unexpected(Symbol.error()); + } + return copyTrailingAnnotations(Source, Destination); +} + +[[nodiscard]] bool isZeroPhysicalRegister(PhysicalRegister Reg) noexcept { + return Reg.number() == static_cast<std::uint32_t>(PhysicalRegisterID::X0); +} + +[[nodiscard]] Expected<PhysicalRegister> +selectLongBranchScratch(const MachineInstr &Instruction, const MachineBasicBlock &TargetBlock, + const MachineFunction &Function, const TargetDescription &Target) { + const MachineOperand *DestinationOperand = Instruction.operandAt(0); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + const std::optional<PhysicalRegister> DestinationPhysical = + Destination == nullptr ? std::nullopt : Destination->physicalRegister(); + if (!DestinationPhysical) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V long JAL has no physical destination"); + } + if (!isZeroPhysicalRegister(*DestinationPhysical)) + return *DestinationPhysical; + + const auto GPRClass = + RegisterClassID::fromValue(static_cast<std::uint32_t>(RegisterClass::GPR_NX0)); + const RegisterClassDesc *Candidates = Target.registers().registerClass(GPRClass); + if (Candidates == nullptr) { + return makeUnexpected(ErrorCode::InternalError, "RISC-V target has no nonzero GPR class"); + } + for (const PhysicalRegister Candidate : Candidates->AllocationOrder) { + if (Target.registers().isReservedRegister(Candidate) || + Function.registerInfo().isReserved(Candidate)) { + continue; + } + const bool LiveAtTarget = + std::ranges::any_of(TargetBlock.liveIns(), [&](const MachineBasicBlockLiveIn &LiveIn) { + return Target.registers().regsOverlap(Candidate, LiveIn.PhysReg); + }); + if (!LiveAtTarget) + return Candidate; + } + return makeUnexpected(ErrorCode::BranchRelaxationFailed, + "RISC-V long branch has no dead physical scratch register"); +} + +[[nodiscard]] Expected<bool> expandCompressedBranch(MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) { + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "compressed branch is not linked"); + auto TargetBlock = directTarget(Instruction); + if (!TargetBlock) + return std::unexpected(TargetBlock.error()); + MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPointBefore(Instruction); + if (!Point) + return std::unexpected(Point.error()); + + if (Instruction.opcode() == instructionOpcode(InstructionOpcode::C_J)) { + auto Zero = physicalRegister(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + auto Replacement = buildJAL(Function, Target, *Block, &Instruction, *Zero, **TargetBlock); + if (!Replacement) + return std::unexpected(Replacement.error()); + auto Annotations = copySingleInstructionAnnotations(Instruction, **Replacement); + if (!Annotations) + return std::unexpected(Annotations.error()); + auto Removed = Instruction.eraseFromParent(); + if (!Removed) + return std::unexpected(Removed.error()); + return true; + } + + const MachineOperand *SourceOperand = Instruction.operandAt(0); + const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>(); + if (Source == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "compressed conditional branch has no source register"); + auto Zero = physicalRegister(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + const InstructionOpcode Expanded = + Instruction.opcode() == instructionOpcode(InstructionOpcode::C_BEQZ) ? InstructionOpcode::BEQ + : InstructionOpcode::BNE; + auto Pending = Builder.buildInstr(instructionOpcode(Expanded)); + if (!Pending) + return std::unexpected(Pending.error()); + auto First = Pending->addUse(*Source); + if (!First) + return std::unexpected(First.error()); + auto Second = Pending->addUse(Register::fromPhysical(*Zero)); + if (!Second) + return std::unexpected(Second.error()); + auto Destination = Pending->addBasicBlock(**TargetBlock); + if (!Destination) + return std::unexpected(Destination.error()); + auto Replacement = Pending->build(); + if (!Replacement) + return std::unexpected(Replacement.error()); + auto Annotations = copySingleInstructionAnnotations(Instruction, **Replacement); + if (!Annotations) + return std::unexpected(Annotations.error()); + auto Removed = Instruction.eraseFromParent(); + if (!Removed) + return std::unexpected(Removed.error()); + return true; +} + +[[nodiscard]] Expected<bool> relaxConditionalBranch(MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) { + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "conditional branch is not linked"); + auto TrueTarget = directTarget(Instruction); + if (!TrueTarget) + return std::unexpected(TrueTarget.error()); + MachineInstr *Following = Instruction.next(); + if (Following != nullptr && isUnconditionalBranch(*Following)) { + auto FalseTarget = directTarget(*Following); + if (!FalseTarget) + return std::unexpected(FalseTarget.error()); + if (*FalseTarget == *TrueTarget) { + auto Removed = Instruction.eraseFromParent(); + if (!Removed) + return std::unexpected(Removed.error()); + return true; + } + } + MachineBasicBlock *FalseTarget = Block->next(); + if (FalseTarget == nullptr || FalseTarget == *TrueTarget || + std::ranges::none_of(Block->successors(), [FalseTarget](const MachineSuccessor &Successor) { + return Successor.Block == FalseTarget; + })) { + return makeUnexpected(ErrorCode::BranchRelaxationFailed, + "RISC-V conditional relaxation requires its false edge as fallthrough"); + } + + auto Reversed = reversedOpcode(Instruction.opcode()); + if (!Reversed) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V conditional branch cannot be inverted"); + auto SetOpcode = Instruction.setOpcode(*Reversed); + if (!SetOpcode) + return std::unexpected(SetOpcode.error()); + auto SetTarget = setDirectTarget(Instruction, *FalseTarget); + if (!SetTarget) + return std::unexpected(SetTarget.error()); + + if (Following != nullptr && isUnconditionalBranch(*Following)) { + auto Retargeted = setDirectTarget(*Following, **TrueTarget); + if (!Retargeted) + return std::unexpected(Retargeted.error()); + return true; + } + auto Zero = physicalRegister(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPointAfter(Instruction); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(instructionOpcode(InstructionOpcode::JAL)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Register::fromPhysical(*Zero)); + if (!Def) + return std::unexpected(Def.error()); + auto Destination = Pending->addBasicBlock(**TrueTarget); + if (!Destination) + return std::unexpected(Destination.error()); + auto LongJump = Pending->build(); + if (!LongJump) + return std::unexpected(LongJump.error()); + auto Identity = copySourceIdentity(Instruction, **LongJump); + if (!Identity) + return std::unexpected(Identity.error()); + MachineInstrFlags OriginalFlags = Instruction.flags(); + const bool HadBundledSuccessor = OriginalFlags.has(MachineInstrFlag::BundledWithSucc); + OriginalFlags.set(MachineInstrFlag::BundledWithSucc); + Instruction.setFlags(OriginalFlags); + MachineInstrFlags LongFlags; + LongFlags.set(MachineInstrFlag::BundledWithPred); + if (HadBundledSuccessor) + LongFlags.set(MachineInstrFlag::BundledWithSucc); + if (OriginalFlags.has(MachineInstrFlag::NoMerge)) + LongFlags.set(MachineInstrFlag::NoMerge); + (*LongJump)->setFlags(LongFlags); + return true; +} + +[[nodiscard]] Expected<bool> relaxJAL(MachineInstr &Instruction, std::int64_t Offset, + MachineFunction &Function, const TargetDescription &Target) { + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "RISC-V JAL is not linked"); + if (Offset < std::numeric_limits<std::int32_t>::min() || + Offset > std::numeric_limits<std::int32_t>::max()) { + return makeUnexpected(ErrorCode::BranchRelaxationFailed, + "RISC-V PC-relative long branch exceeds the signed 32-bit range"); + } + auto DestinationBlock = directTarget(Instruction); + if (!DestinationBlock) + return std::unexpected(DestinationBlock.error()); + const MachineOperand *DestinationOperand = Instruction.operandAt(0); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + if (Destination == nullptr || !Destination->isPhysical()) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V long JAL requires a physical destination register"); + } + auto Scratch = selectLongBranchScratch(Instruction, **DestinationBlock, Function, Target); + if (!Scratch) + return std::unexpected(Scratch.error()); + const std::string Anchor = Instruction.preInstrSymbol() + ? std::string(*Instruction.preInstrSymbol()) + : ".Lrcc_long_" + std::to_string(Function.stableID().value()) + + "_" + std::to_string(Instruction.stableID().value()); + const MachineInstrFlags OriginalFlags = Instruction.flags(); + + MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPointBefore(Instruction); + if (!Point) + return std::unexpected(Point.error()); + auto HighPending = Builder.buildInstr(instructionOpcode(InstructionOpcode::AUIPC)); + if (!HighPending) + return std::unexpected(HighPending.error()); + auto HighDef = HighPending->addDef(Register::fromPhysical(*Scratch)); + if (!HighDef) + return std::unexpected(HighDef.error()); + auto HighTarget = HighPending->addBasicBlock(**DestinationBlock, PCRelativeHighFlag); + if (!HighTarget) + return std::unexpected(HighTarget.error()); + auto High = HighPending->build(); + if (!High) + return std::unexpected(High.error()); + auto HighSymbol = (*High)->setPreInstrSymbol(Anchor); + if (!HighSymbol) + return std::unexpected(HighSymbol.error()); + auto HighIdentity = copySourceIdentity(Instruction, **High); + if (!HighIdentity) + return std::unexpected(HighIdentity.error()); + + auto LowPending = Builder.buildInstr(instructionOpcode(InstructionOpcode::JALR)); + if (!LowPending) + return std::unexpected(LowPending.error()); + auto LowDef = LowPending->addDef(*Destination); + if (!LowDef) + return std::unexpected(LowDef.error()); + auto LowBase = LowPending->addUse(Register::fromPhysical(*Scratch)); + if (!LowBase) + return std::unexpected(LowBase.error()); + auto LowSymbol = LowPending->addMCSymbol(Anchor, 0, PCRelativeLowFlag); + if (!LowSymbol) + return std::unexpected(LowSymbol.error()); + auto Low = LowPending->build(); + if (!Low) + return std::unexpected(Low.error()); + auto LowIdentity = copySourceIdentity(Instruction, **Low); + if (!LowIdentity) + return std::unexpected(LowIdentity.error()); + auto LowAnnotations = copyTrailingAnnotations(Instruction, **Low); + if (!LowAnnotations) + return std::unexpected(LowAnnotations.error()); + + MachineInstrFlags HighFlags; + if (OriginalFlags.has(MachineInstrFlag::BundledWithPred)) + HighFlags.set(MachineInstrFlag::BundledWithPred); + HighFlags.set(MachineInstrFlag::BundledWithSucc); + if (OriginalFlags.has(MachineInstrFlag::NoMerge)) + HighFlags.set(MachineInstrFlag::NoMerge); + (*High)->setFlags(HighFlags); + MachineInstrFlags LowFlags = OriginalFlags; + LowFlags.clear(MachineInstrFlag::BundledWithPred); + LowFlags.set(MachineInstrFlag::BundledWithPred); + (*Low)->setFlags(LowFlags); + auto Removed = Instruction.eraseFromParent(); + if (!Removed) + return std::unexpected(Removed.error()); + return true; +} + +[[nodiscard]] bool loadImmediate(const MachineInstr *Instruction, std::int64_t &Immediate) { + if (Instruction == nullptr || + Instruction->opcode() != instructionOpcode(InstructionOpcode::ADDI) || + !isPhysicalRegister(Instruction->operandAt(1), PhysicalRegisterID::X0)) { + return false; + } + const auto *Value = Instruction->operandAt(2) == nullptr + ? nullptr + : Instruction->operandAt(2)->getIf<std::int64_t>(); + if (Value == nullptr) + return false; + Immediate = *Value; + return true; +} + +[[nodiscard]] bool loadImmediateSource(const MachineRegisterInfo &Registers, + const MachineOperand &Operand, std::int64_t &Immediate) { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr) + return false; + if (const std::optional<PhysicalRegister> Physical = Reg->physicalRegister()) { + if (Physical->number() != static_cast<std::uint32_t>(PhysicalRegisterID::X0)) + return false; + Immediate = 0; + return true; + } + return Reg->isVirtual() && loadImmediate(Registers.getVRegDef(*Reg), Immediate); +} + +[[nodiscard]] std::optional<BranchConditionCode> branchCondition(Opcode Value) noexcept { + if (Value == instructionOpcode(InstructionOpcode::BEQ)) + return BranchConditionCode::Equal; + if (Value == instructionOpcode(InstructionOpcode::BNE)) + return BranchConditionCode::NotEqual; + if (Value == instructionOpcode(InstructionOpcode::BLT)) + return BranchConditionCode::SignedLessThan; + if (Value == instructionOpcode(InstructionOpcode::BGE)) + return BranchConditionCode::SignedGreaterEqual; + if (Value == instructionOpcode(InstructionOpcode::BLTU)) + return BranchConditionCode::UnsignedLessThan; + if (Value == instructionOpcode(InstructionOpcode::BGEU)) + return BranchConditionCode::UnsignedGreaterEqual; + return std::nullopt; +} + +[[nodiscard]] bool evaluateBranch(BranchConditionCode Condition, std::int64_t Left, + std::int64_t Right) noexcept { + switch (Condition) { + case BranchConditionCode::Equal: + return Left == Right; + case BranchConditionCode::NotEqual: + return Left != Right; + case BranchConditionCode::SignedLessThan: + return Left < Right; + case BranchConditionCode::SignedGreaterEqual: + return Left >= Right; + case BranchConditionCode::UnsignedLessThan: + return static_cast<std::uint64_t>(Left) < static_cast<std::uint64_t>(Right); + case BranchConditionCode::UnsignedGreaterEqual: + return static_cast<std::uint64_t>(Left) >= static_cast<std::uint64_t>(Right); + } + return false; +} + +[[nodiscard]] Expected<void> setRegisterUse(MachineOperand &Operand, Register Reg) { + auto Changed = Operand.setRegister(Reg); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = Operand.setRegisterFlags({RegisterOperandFlag::Use}); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = Operand.setSubReg({}); + if (!Changed) + return std::unexpected(Changed.error()); + Operand.setTargetFlags(0); + return {}; +} + +[[nodiscard]] Expected<void> copyRegisterUse(MachineOperand &Destination, + const MachineOperand &Source) { + const Register *Reg = Source.getIf<Register>(); + if (Reg == nullptr || !Source.isUse()) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V branch optimization requires register uses"); + auto Changed = Destination.setRegister(*Reg); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = Destination.setRegisterFlags(Source.registerFlags()); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = Destination.setSubReg(Source.subReg()); + if (!Changed) + return std::unexpected(Changed.error()); + Destination.setTargetFlags(Source.targetFlags()); + return {}; +} + +[[nodiscard]] Expected<void> clearKillFlags(MachineRegisterInfo &Registers, Register Reg) { + for (MachineOperand &Operand : Registers.useOperands(Reg)) { + RegisterOperandFlags Flags = Operand.registerFlags(); + if (!Flags.has(RegisterOperandFlag::Kill)) + continue; + Flags.clear(RegisterOperandFlag::Kill); + auto Changed = Operand.setRegisterFlags(Flags); + if (!Changed) + return std::unexpected(Changed.error()); + } + return {}; +} + +class RISCVInstrInfo final : public TargetInstrInfo { +public: + [[nodiscard]] Expected<MachineBranchAnalysis> + analyzeBranch(MachineBasicBlock &Block, MachineFunction &Function, + const TargetDescription &Target) const override { + if (&Block.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch analysis references another function"); + std::vector<MachineInstr *> Terminators; + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V branch analysis encountered an unknown opcode"); + if (Descriptor->Flags.has(InstructionFlag::Terminator)) + Terminators.push_back(Instruction); + } + + MachineBranchAnalysis Result; + if (Terminators.empty()) + return Result; + if (Terminators.size() > 2) { + Result.HasUnanalyzableTerminator = true; + return Result; + } + MachineInstr *First = Terminators.front(); + if (isConditionalBranch(First->opcode())) { + auto TrueTarget = directTarget(*First); + if (!TrueTarget) + return std::unexpected(TrueTarget.error()); + Result.Conditional = First; + Result.TrueTarget = *TrueTarget; + if (Terminators.size() == 2) { + MachineInstr *Second = Terminators.back(); + if (!isUnconditionalBranch(*Second)) { + Result.HasUnanalyzableTerminator = true; + return Result; + } + auto FalseTarget = directTarget(*Second); + if (!FalseTarget) + return std::unexpected(FalseTarget.error()); + Result.Unconditional = Second; + Result.FalseTarget = *FalseTarget; + } else { + for (const MachineSuccessor &Successor : Block.successors()) { + if (Successor.Block == nullptr || Successor.Block == Result.TrueTarget) + continue; + if (Result.FalseTarget != nullptr) { + Result.HasUnanalyzableTerminator = true; + return Result; + } + Result.FalseTarget = Successor.Block; + } + if (Result.FalseTarget == nullptr) + Result.FalseTarget = Block.next(); + } + return Result; + } + if (Terminators.size() == 1 && isUnconditionalBranch(*First)) { + auto TargetBlock = directTarget(*First); + if (!TargetBlock) + return std::unexpected(TargetBlock.error()); + Result.Unconditional = First; + Result.TrueTarget = *TargetBlock; + return Result; + } + Result.HasUnanalyzableTerminator = true; + return Result; + } + + [[nodiscard]] Expected<void> reverseBranchCondition(MachineInstr &Branch, + MachineBasicBlock &NewTarget, + MachineFunction &Function, + const TargetDescription &) const override { + if (&Branch.function() != &Function || &NewTarget.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch reversal references another function"); + const std::optional<Opcode> Reversed = reversedOpcode(Branch.opcode()); + if (!Reversed) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch opcode has no inverse condition"); + auto OpcodeResult = Branch.setOpcode(*Reversed); + if (!OpcodeResult) + return std::unexpected(OpcodeResult.error()); + return setDirectTarget(Branch, NewTarget); + } + + [[nodiscard]] Expected<void> removeBranch(MachineInstr &Branch, MachineFunction &Function, + const TargetDescription &) const override { + if (&Branch.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch removal references another function"); + return Branch.eraseFromParent(); + } + + [[nodiscard]] Expected<bool> rewriteBranchTarget(MachineBasicBlock &Block, + MachineBasicBlock &OldTarget, + MachineBasicBlock &NewTarget, + MachineFunction &Function, + const TargetDescription &) const override { + if (&Block.function() != &Function || &OldTarget.function() != &Function || + &NewTarget.function() != &Function) { + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch rewrite references another function"); + } + bool Changed = false; + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (!isConditionalBranch(Instruction->opcode()) && !isUnconditionalBranch(*Instruction)) { + continue; + } + auto CurrentTarget = directTarget(*Instruction); + if (!CurrentTarget) + return std::unexpected(CurrentTarget.error()); + if (*CurrentTarget != &OldTarget) + continue; + auto Rewritten = setDirectTarget(*Instruction, NewTarget); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + Changed = true; + } + return Changed; + } + + [[nodiscard]] Expected<MachineInstr *> + insertBranch(MachineBasicBlock &Block, MachineBasicBlock &TargetBlock, MachineFunction &Function, + const TargetDescription &Target) const override { + if (&Block.function() != &Function || &TargetBlock.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch insertion references another function"); + auto Zero = physicalRegister(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + return buildJAL(Function, Target, Block, nullptr, *Zero, TargetBlock); + } + + [[nodiscard]] Expected<bool> isFallthroughEdge(const MachineBasicBlock &From, + const MachineBasicBlock &To, + const MachineFunction &Function, + const TargetDescription &Target) const override { + if (&From.function() != &Function || &To.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V fallthrough query references another machine function"); + if (From.next() != &To || + std::ranges::none_of(From.successors(), [&To](const MachineSuccessor &Successor) { + return Successor.Block == &To; + })) { + return false; + } + + bool CanFallThrough = true; + for (const MachineInstr *Instruction = From.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V fallthrough analysis encountered an unknown opcode"); + if (Descriptor->Flags.has(InstructionFlag::Terminator)) + CanFallThrough = isConditionalBranch(Instruction->opcode()); + } + return CanFallThrough; + } + + [[nodiscard]] Expected<void> validateCopy(Register Destination, SubRegIndex DestinationSubReg, + Register Source, SubRegIndex SourceSubReg, + const MachineFunction &Function, + const TargetDescription &Target) const override { + if (Destination.isNoRegister() || Source.isNoRegister()) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V COPY requires two nonzero registers"); + if (DestinationSubReg.value() != 0 || SourceSubReg.value() != 0) + return makeUnexpected(ErrorCode::Unsupported, "RV64GC does not model register subindices"); + + auto DestinationShape = copyShape(Destination, Function, Target); + if (!DestinationShape) + return std::unexpected(DestinationShape.error()); + auto SourceShape = copyShape(Source, Function, Target); + if (!SourceShape) + return std::unexpected(SourceShape.error()); + if (DestinationShape->Bank == SourceShape->Bank) { + if (DestinationShape->Width && SourceShape->Width && + DestinationShape->Width != SourceShape->Width) + return makeUnexpected(ErrorCode::Unsupported, + "RISC-V same-bank COPY has incompatible register widths"); + return {}; + } + + const RegisterBankID GPR = + RegisterBankID::fromValue(static_cast<std::uint32_t>(RegisterBank::GPR)); + const RegisterBankID FPR = + RegisterBankID::fromValue(static_cast<std::uint32_t>(RegisterBank::FPR)); + const bool IsCrossBankMove = (DestinationShape->Bank == GPR && SourceShape->Bank == FPR) || + (DestinationShape->Bank == FPR && SourceShape->Bank == GPR); + if (!IsCrossBankMove) + return makeUnexpected(ErrorCode::Unsupported, + "RISC-V COPY crosses unsupported register banks"); + const auto SupportedWidth = [](std::optional<std::uint32_t> Width) { + return !Width || *Width == 32 || *Width == 64; + }; + if (!SupportedWidth(DestinationShape->Width) || !SupportedWidth(SourceShape->Width)) + return makeUnexpected(ErrorCode::Unsupported, + "RISC-V GPR/FPR COPY requires 32-bit or 64-bit values"); + return {}; + } + + [[nodiscard]] std::optional<MachineCopyOperands> + getCopyOperands(MachineInstr &Instruction) const noexcept override { + auto Pair = [&Instruction](std::size_t Destination, + std::size_t Source) -> std::optional<MachineCopyOperands> { + MachineOperand *DestinationOperand = Instruction.operandAt(Destination); + MachineOperand *SourceOperand = Instruction.operandAt(Source); + return DestinationOperand != nullptr && SourceOperand != nullptr + ? std::optional<MachineCopyOperands>{MachineCopyOperands{DestinationOperand, + SourceOperand}} + : std::nullopt; + }; + if (Instruction.opcode() == opcode(GenericOpcode::COPY)) + return Pair(0, 1); + if (Instruction.opcode() == instructionOpcode(InstructionOpcode::ADD) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::OR) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::XOR)) { + if (isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) + return Pair(0, 2); + if (isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0)) + return Pair(0, 1); + } + if (Instruction.opcode() == instructionOpcode(InstructionOpcode::ADDI)) { + const auto *Immediate = Instruction.operandAt(2) == nullptr + ? nullptr + : Instruction.operandAt(2)->getIf<std::int64_t>(); + if (Immediate != nullptr && *Immediate == 0) + return Pair(0, 1); + } + if (Instruction.opcode() == instructionOpcode(InstructionOpcode::SUB) && + isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0)) { + return Pair(0, 1); + } + if (Instruction.opcode() == instructionOpcode(InstructionOpcode::SH1ADD) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::SH1ADD_UW) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::SH2ADD) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::SH2ADD_UW) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::SH3ADD) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::SH3ADD_UW)) { + if (isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) + return Pair(0, 2); + } + if (Instruction.opcode() == instructionOpcode(InstructionOpcode::FSGNJ_D) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::FSGNJ_S)) { + if (sameRegister(Instruction.operandAt(1), Instruction.operandAt(2))) + return Pair(0, 1); + } + return std::nullopt; + } + + [[nodiscard]] Expected<bool> simplifyInstruction(MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &) const override { + if (&Instruction.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V instruction simplification references another function"); + auto SetOpcode = [&Instruction](InstructionOpcode NewOpcode) -> Expected<bool> { + auto Result = Instruction.setOpcode(instructionOpcode(NewOpcode)); + if (!Result) + return std::unexpected(Result.error()); + return true; + }; + auto SetZeroImmediate = [&Instruction, &SetOpcode]( + std::size_t Index, InstructionOpcode NewOpcode) -> Expected<bool> { + MachineOperand *Operand = Instruction.operandAt(Index); + if (Operand == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V simplification has no source operand"); + auto Changed = Operand->changeToImmediate(0); + if (!Changed) + return std::unexpected(Changed.error()); + return SetOpcode(NewOpcode); + }; + const Opcode Value = Instruction.opcode(); + if (Value == instructionOpcode(InstructionOpcode::ADD) || + Value == instructionOpcode(InstructionOpcode::OR) || + Value == instructionOpcode(InstructionOpcode::XOR)) { + if (isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) { + auto Swapped = swapRegisters(*Instruction.operandAt(1), *Instruction.operandAt(2)); + if (!Swapped) + return std::unexpected(Swapped.error()); + } + if (isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0)) + return SetZeroImmediate(2, InstructionOpcode::ADDI); + if (Value == instructionOpcode(InstructionOpcode::XOR) && + sameRegister(Instruction.operandAt(1), Instruction.operandAt(2))) { + auto Zero = physicalRegister(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + auto SetSource = Instruction.operandAt(1)->setRegister(Register::fromPhysical(*Zero)); + if (!SetSource) + return std::unexpected(SetSource.error()); + return SetZeroImmediate(2, InstructionOpcode::ADDI); + } + return false; + } + if ((Value == instructionOpcode(InstructionOpcode::ORI) || + Value == instructionOpcode(InstructionOpcode::XORI)) && + isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) { + return SetOpcode(InstructionOpcode::ADDI); + } + if (Value == instructionOpcode(InstructionOpcode::SUB) && + isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0)) { + return SetZeroImmediate(2, InstructionOpcode::ADDI); + } + if (Value == instructionOpcode(InstructionOpcode::SUBW) && + isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0)) { + return SetZeroImmediate(2, InstructionOpcode::ADDIW); + } + if (Value == instructionOpcode(InstructionOpcode::ADDW)) { + if (isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) { + auto Swapped = swapRegisters(*Instruction.operandAt(1), *Instruction.operandAt(2)); + if (!Swapped) + return std::unexpected(Swapped.error()); + } + if (isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0)) + return SetZeroImmediate(2, InstructionOpcode::ADDIW); + return false; + } + if (Value == instructionOpcode(InstructionOpcode::SH1ADD) || + Value == instructionOpcode(InstructionOpcode::SH1ADD_UW) || + Value == instructionOpcode(InstructionOpcode::SH2ADD) || + Value == instructionOpcode(InstructionOpcode::SH2ADD_UW) || + Value == instructionOpcode(InstructionOpcode::SH3ADD) || + Value == instructionOpcode(InstructionOpcode::SH3ADD_UW)) { + if (isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) { + auto Removed = Instruction.eraseOperand(1); + if (!Removed) + return std::unexpected(Removed.error()); + Removed = Instruction.addOperand(MachineOperand::immediate(0)); + if (!Removed) + return std::unexpected(Removed.error()); + return SetOpcode(InstructionOpcode::ADDI); + } + if (isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0)) { + const bool IsUnsignedWord = Value == instructionOpcode(InstructionOpcode::SH1ADD_UW) || + Value == instructionOpcode(InstructionOpcode::SH2ADD_UW) || + Value == instructionOpcode(InstructionOpcode::SH3ADD_UW); + const std::int64_t Shift = Value == instructionOpcode(InstructionOpcode::SH1ADD) || + Value == instructionOpcode(InstructionOpcode::SH1ADD_UW) + ? 1 + : Value == instructionOpcode(InstructionOpcode::SH2ADD) || + Value == instructionOpcode(InstructionOpcode::SH2ADD_UW) + ? 2 + : 3; + auto Removed = Instruction.eraseOperand(2); + if (!Removed) + return std::unexpected(Removed.error()); + Removed = Instruction.addOperand(MachineOperand::immediate(Shift)); + if (!Removed) + return std::unexpected(Removed.error()); + return SetOpcode(IsUnsignedWord ? InstructionOpcode::SLLI_UW : InstructionOpcode::SLLI); + } + return false; + } + if (Value == instructionOpcode(InstructionOpcode::AND) || + Value == instructionOpcode(InstructionOpcode::MUL) || + Value == instructionOpcode(InstructionOpcode::MULH) || + Value == instructionOpcode(InstructionOpcode::MULHSU) || + Value == instructionOpcode(InstructionOpcode::MULHU) || + Value == instructionOpcode(InstructionOpcode::MULW)) { + if (!isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0) && + !isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0)) { + return false; + } + auto Zero = physicalRegister(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + auto SetSource = Instruction.operandAt(1)->setRegister(Register::fromPhysical(*Zero)); + if (!SetSource) + return std::unexpected(SetSource.error()); + return SetZeroImmediate(2, InstructionOpcode::ADDI); + } + if (Value == instructionOpcode(InstructionOpcode::ANDI) && + isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) { + MachineOperand *Immediate = Instruction.operandAt(2); + if (Immediate == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V ANDI simplification has no immediate operand"); + auto SetImmediate = Immediate->setImmediate(0); + if (!SetImmediate) + return std::unexpected(SetImmediate.error()); + return SetOpcode(InstructionOpcode::ADDI); + } + if (Value == instructionOpcode(InstructionOpcode::SLL) || + Value == instructionOpcode(InstructionOpcode::SRL) || + Value == instructionOpcode(InstructionOpcode::SRA)) { + if (isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0) || + isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0)) { + return SetZeroImmediate(2, InstructionOpcode::ADDI); + } + return false; + } + if ((Value == instructionOpcode(InstructionOpcode::SLLW) || + Value == instructionOpcode(InstructionOpcode::SRLW) || + Value == instructionOpcode(InstructionOpcode::SRAW)) && + isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) { + return SetZeroImmediate(2, InstructionOpcode::ADDI); + } + if ((Value == instructionOpcode(InstructionOpcode::SLLI) || + Value == instructionOpcode(InstructionOpcode::SRLI) || + Value == instructionOpcode(InstructionOpcode::SRAI) || + Value == instructionOpcode(InstructionOpcode::SLLIW) || + Value == instructionOpcode(InstructionOpcode::SRLIW) || + Value == instructionOpcode(InstructionOpcode::SRAIW) || + Value == instructionOpcode(InstructionOpcode::SLLI_UW)) && + isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) { + MachineOperand *Immediate = Instruction.operandAt(2); + if (Immediate == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V shift simplification has no immediate operand"); + auto SetImmediate = Immediate->setImmediate(0); + if (!SetImmediate) + return std::unexpected(SetImmediate.error()); + return SetOpcode(InstructionOpcode::ADDI); + } + if (Value == instructionOpcode(InstructionOpcode::SLTU) || + Value == instructionOpcode(InstructionOpcode::ADD_UW)) { + const bool LeftZero = isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0); + const bool RightZero = isPhysicalRegister(Instruction.operandAt(2), PhysicalRegisterID::X0); + if (LeftZero && RightZero) + return SetZeroImmediate(2, InstructionOpcode::ADDI); + if (Value == instructionOpcode(InstructionOpcode::ADD_UW) && LeftZero) { + auto Removed = Instruction.eraseOperand(1); + if (!Removed) + return std::unexpected(Removed.error()); + Removed = Instruction.addOperand(MachineOperand::immediate(0)); + if (!Removed) + return std::unexpected(Removed.error()); + return SetOpcode(InstructionOpcode::ADDI); + } + return false; + } + if (Value == instructionOpcode(InstructionOpcode::SLTIU) && + isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) { + MachineOperand *Immediate = Instruction.operandAt(2); + const auto *ImmediateValue = + Immediate == nullptr ? nullptr : Immediate->getIf<std::int64_t>(); + if (ImmediateValue == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V SLTIU simplification has no immediate operand"); + const std::int64_t Result = *ImmediateValue != 0 ? 1 : 0; + auto SetImmediate = Immediate->setImmediate(Result); + if (!SetImmediate) + return std::unexpected(SetImmediate.error()); + return SetOpcode(InstructionOpcode::ADDI); + } + if ((Value == instructionOpcode(InstructionOpcode::SEXT_H) || + Value == instructionOpcode(InstructionOpcode::SEXT_B) || + Value == instructionOpcode(InstructionOpcode::ZEXT_H_RV32) || + Value == instructionOpcode(InstructionOpcode::ZEXT_H_RV64)) && + isPhysicalRegister(Instruction.operandAt(1), PhysicalRegisterID::X0)) { + auto Added = Instruction.addOperand(MachineOperand::immediate(0)); + if (!Added) + return std::unexpected(Added.error()); + return SetOpcode(InstructionOpcode::ADDI); + } + if ((Value == instructionOpcode(InstructionOpcode::MIN) || + Value == instructionOpcode(InstructionOpcode::MINU) || + Value == instructionOpcode(InstructionOpcode::MAX) || + Value == instructionOpcode(InstructionOpcode::MAXU)) && + sameRegister(Instruction.operandAt(1), Instruction.operandAt(2))) { + return SetZeroImmediate(2, InstructionOpcode::ADDI); + } + if ((Value == instructionOpcode(InstructionOpcode::BEQ) || + Value == instructionOpcode(InstructionOpcode::BNE)) && + isPhysicalRegister(Instruction.operandAt(0), PhysicalRegisterID::X0)) { + auto Swapped = swapRegisters(*Instruction.operandAt(0), *Instruction.operandAt(1)); + if (!Swapped) + return std::unexpected(Swapped.error()); + return true; + } + if ((Value == instructionOpcode(InstructionOpcode::BLTU) || + Value == instructionOpcode(InstructionOpcode::BGEU)) && + isPhysicalRegister(Instruction.operandAt(0), PhysicalRegisterID::X0)) { + auto Swapped = swapRegisters(*Instruction.operandAt(0), *Instruction.operandAt(1)); + if (!Swapped) + return std::unexpected(Swapped.error()); + return SetOpcode(Value == instructionOpcode(InstructionOpcode::BLTU) + ? InstructionOpcode::BNE + : InstructionOpcode::BEQ); + } + return false; + } + + [[nodiscard]] Expected<bool> optimizeCondBranch(MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &) const override { + if (&Instruction.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch optimization references another function"); + const auto Condition = branchCondition(Instruction.opcode()); + if (!Condition) + return false; + MachineOperand *Left = Instruction.operandAt(0); + MachineOperand *Right = Instruction.operandAt(1); + if (Left == nullptr || Right == nullptr || Instruction.operandAt(2) == nullptr || + Instruction.operandAt(2)->getIf<BasicBlockOperand>() == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V conditional branch has malformed operands"); + } + + MachineRegisterInfo &Registers = Function.registerInfo(); + std::int64_t LeftConstant = 0; + std::int64_t RightConstant = 0; + if (loadImmediateSource(Registers, *Left, LeftConstant) && + loadImmediateSource(Registers, *Right, RightConstant)) { + const InstructionOpcode NewOpcode = evaluateBranch(*Condition, LeftConstant, RightConstant) + ? InstructionOpcode::BEQ + : InstructionOpcode::BNE; + auto Zero = physicalRegister(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + auto Changed = Instruction.setOpcode(instructionOpcode(NewOpcode)); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = setRegisterUse(*Left, Register::fromPhysical(*Zero)); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = setRegisterUse(*Right, Register::fromPhysical(*Zero)); + if (!Changed) + return std::unexpected(Changed.error()); + return true; + } + + const bool IsEquality = + *Condition == BranchConditionCode::Equal || *Condition == BranchConditionCode::NotEqual; + if (IsEquality) + return false; + const bool IsSigned = *Condition == BranchConditionCode::SignedLessThan || + *Condition == BranchConditionCode::SignedGreaterEqual; + const auto SearchConstant = [&Instruction](std::int64_t Value) -> Register { + for (MachineInstr *Candidate = Instruction.previous(); Candidate != nullptr; + Candidate = Candidate->previous()) { + std::int64_t CandidateValue = 0; + if (!loadImmediate(Candidate, CandidateValue) || CandidateValue != Value) + continue; + const MachineOperand *Definition = Candidate->operandAt(0); + const Register *Reg = Definition == nullptr ? nullptr : Definition->getIf<Register>(); + if (Reg != nullptr && Reg->isVirtual()) + return *Reg; + } + return {}; + }; + const std::optional<Opcode> NewOpcode = reversedOpcode(Instruction.opcode()); + if (!NewOpcode) + return false; + + const Register *LeftReg = Left->getIf<Register>(); + if (loadImmediateSource(Registers, *Left, LeftConstant) && LeftConstant != 0 && + LeftReg != nullptr && LeftReg->isVirtual() && Registers.hasOneUse(*LeftReg, false) && + (IsSigned || LeftConstant != -1)) { + const Register Replacement = SearchConstant(LeftConstant + 1); + if (!Replacement.isNoRegister()) { + MachineOperand SavedRight = Right->cloneDetached(); + auto Changed = Instruction.setOpcode(*NewOpcode); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = copyRegisterUse(*Left, SavedRight); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = setRegisterUse(*Right, Replacement); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = clearKillFlags(Registers, Replacement); + if (!Changed) + return std::unexpected(Changed.error()); + return true; + } + } + + const Register *RightReg = Right->getIf<Register>(); + if (loadImmediateSource(Registers, *Right, RightConstant) && RightConstant != 0 && + RightReg != nullptr && RightReg->isVirtual() && Registers.hasOneUse(*RightReg, false)) { + const Register Replacement = SearchConstant(RightConstant - 1); + if (!Replacement.isNoRegister()) { + MachineOperand SavedLeft = Left->cloneDetached(); + auto Changed = Instruction.setOpcode(*NewOpcode); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = setRegisterUse(*Left, Replacement); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = copyRegisterUse(*Right, SavedLeft); + if (!Changed) + return std::unexpected(Changed.error()); + Changed = clearKillFlags(Registers, Replacement); + if (!Changed) + return std::unexpected(Changed.error()); + return true; + } + } + return false; + } + + [[nodiscard]] Expected<std::uint32_t> + instructionSize(const MachineInstr &Instruction, const MachineFunction &, + const TargetDescription &Target) const override { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V instruction-size query encountered an unknown opcode"); + if (!Descriptor->Flags.has(InstructionFlag::ProducesCode)) + return 0; + if (Instruction.opcode() == opcode(GenericOpcode::INLINEASM) || + Instruction.opcode() == opcode(GenericOpcode::INLINEASM_BR)) { + return inlineAsmSize(Instruction); + } + if (Descriptor->SizeInBytes != 0) + return Descriptor->SizeInBytes; + const auto Category = + std::ranges::find_if(encodingCategories(), [Descriptor](const EncodingCategoryInfo &Info) { + return Info.ID == Descriptor->EncodingCategory; + }); + if (Category == encodingCategories().end() || Category->SizeInBytes == 0) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V producing instruction has no exact encoding size"); + return Category->SizeInBytes; + } + + [[nodiscard]] Expected<MachineBasicBlock *> + branchTarget(MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &) const override { + if (&Instruction.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch target query references another function"); + return directTarget(Instruction); + } + + [[nodiscard]] Expected<std::optional<bool>> + evaluateBranchCondition(const MachineInstr &Instruction, const MachineFunction &Function, + const TargetDescription &) const override { + if (&Instruction.function() != &Function) { + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch evaluation references another function"); + } + const Opcode Value = Instruction.opcode(); + if (!isConditionalBranch(Value)) + return std::optional<bool>{}; + if (Value == instructionOpcode(InstructionOpcode::C_BEQZ) || + Value == instructionOpcode(InstructionOpcode::C_BNEZ)) { + if (!isZeroRegister(Instruction.operandAt(0))) + return std::optional<bool>{}; + return std::optional<bool>{Value == instructionOpcode(InstructionOpcode::C_BEQZ)}; + } + if (!sameRegister(Instruction.operandAt(0), Instruction.operandAt(1))) + return std::optional<bool>{}; + if (Value == instructionOpcode(InstructionOpcode::BEQ) || + Value == instructionOpcode(InstructionOpcode::BGE) || + Value == instructionOpcode(InstructionOpcode::BGEU)) { + return std::optional<bool>{true}; + } + return std::optional<bool>{false}; + } + + [[nodiscard]] bool isBranchOffsetInRange(const MachineInstr &Instruction, + std::int64_t Offset) const noexcept override { + if ((Offset & 1) != 0) + return false; + const Opcode Value = Instruction.opcode(); + if (Value == instructionOpcode(InstructionOpcode::C_BEQZ) || + Value == instructionOpcode(InstructionOpcode::C_BNEZ)) { + return Offset >= -256 && Offset <= 254; + } + if (Value == instructionOpcode(InstructionOpcode::C_J)) + return Offset >= -2048 && Offset <= 2046; + if (isConditionalBranch(Value)) + return Offset >= -4096 && Offset <= 4094; + if (Value == instructionOpcode(InstructionOpcode::JAL) || + Value == instructionOpcode(InstructionOpcode::PseudoBR)) { + return Offset >= -1048576 && Offset <= 1048574; + } + return true; + } + + [[nodiscard]] Expected<bool> relaxBranch(MachineInstr &Instruction, std::int64_t Offset, + MachineFunction &Function, + const TargetDescription &Target) const override { + if (&Instruction.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch relaxation references another function"); + if (Instruction.opcode() == instructionOpcode(InstructionOpcode::C_J) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::C_BEQZ) || + Instruction.opcode() == instructionOpcode(InstructionOpcode::C_BNEZ)) { + return expandCompressedBranch(Instruction, Function, Target); + } + if (isConditionalBranch(Instruction.opcode())) + return relaxConditionalBranch(Instruction, Function, Target); + if (Instruction.opcode() == instructionOpcode(InstructionOpcode::JAL)) + return relaxJAL(Instruction, Offset, Function, Target); + return false; + } + +private: + struct CopyShape final { + RegisterBankID Bank; + std::optional<std::uint32_t> Width; + }; + + [[nodiscard]] static Expected<CopyShape> copyShape(Register Reg, const MachineFunction &Function, + const TargetDescription &Target) { + if (Reg.isVirtual()) { + auto Info = Function.registerInfo().virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + const std::optional<RegisterBankID> &Bank = Info->get().Bank; + const std::optional<RegisterClassID> &RegClass = Info->get().RegClass; + if (!Bank || !RegClass) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V COPY virtual register is not fully constrained"); + const RegisterClassDesc *Class = Target.registers().registerClass(*RegClass); + if (Class == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V COPY references an unknown register class"); + return CopyShape{*Bank, Class->SizeInBits}; + } + + const std::optional<PhysicalRegister> Physical = Reg.physicalRegister(); + if (!Physical || !Target.registers().isKnownPhysicalRegister(*Physical)) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V COPY references an unknown physical register"); + for (const RegisterBankDesc &Bank : Target.registers().registerBanks()) { + if (Target.registers().bankContainsRegister(Bank.ID, *Physical)) + return CopyShape{Bank.ID, std::nullopt}; + } + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V physical register is not assigned to a register bank"); + } +}; + +} // namespace + +const TargetInstrInfo &instrInfo() noexcept { + static const RISCVInstrInfo Value; + return Value; +} + +} // namespace rcc::riscv |