diff options
Diffstat (limited to 'backend')
22 files changed, 3594 insertions, 56 deletions
diff --git a/backend/include/rcc/CodeGen/InstructionDescriptor.h b/backend/include/rcc/CodeGen/InstructionDescriptor.h index 7cf598d..ca2c5cf 100644 --- a/backend/include/rcc/CodeGen/InstructionDescriptor.h +++ b/backend/include/rcc/CodeGen/InstructionDescriptor.h @@ -226,6 +226,7 @@ struct OperandDescriptor final { bool Optional = false; bool VariadicGroup = false; bool AllowSubReg = false; + bool AllowAnyTargetFlags = false; std::optional<NamedOperandID> Name; std::optional<TargetOperandTypeID> TargetOperandType; std::uint32_t AllowedTargetFlags = 0; diff --git a/backend/include/rcc/CodeGen/MachineCFGUpdater.h b/backend/include/rcc/CodeGen/MachineCFGUpdater.h index 4359538..70fb9aa 100644 --- a/backend/include/rcc/CodeGen/MachineCFGUpdater.h +++ b/backend/include/rcc/CodeGen/MachineCFGUpdater.h @@ -10,6 +10,7 @@ namespace rcc { class MachineBasicBlock; class MachineFunction; +class MachineInstr; class MachineCFGUpdater final { public: @@ -22,11 +23,16 @@ public: [[nodiscard]] Expected<void> replaceSuccessor(MachineBasicBlock &From, MachineBasicBlock &OldTarget, MachineBasicBlock &NewTarget); + [[nodiscard]] Expected<void> splitEdge(MachineBasicBlock &From, MachineBasicBlock &To, + MachineBasicBlock &EdgeBlock); [[nodiscard]] Expected<void> updateBranchProbability(MachineBasicBlock &From, MachineBasicBlock &To, BranchProbability Probability); [[nodiscard]] Expected<void> transferSuccessors(MachineBasicBlock &From, MachineBasicBlock &To); [[nodiscard]] Expected<void> disconnectBlock(MachineBasicBlock &Block); + [[nodiscard]] Expected<MachineBasicBlock *> splitBlock(MachineBasicBlock &Block, + MachineInstr &SplitBefore); + [[nodiscard]] Expected<void> deleteBlock(MachineBasicBlock &Block); private: [[nodiscard]] Expected<void> verifyOwnership(const MachineBasicBlock &Block) const; diff --git a/backend/include/rcc/CodeGen/MachineOperand.h b/backend/include/rcc/CodeGen/MachineOperand.h index b8a6dcc..31ad7e4 100644 --- a/backend/include/rcc/CodeGen/MachineOperand.h +++ b/backend/include/rcc/CodeGen/MachineOperand.h @@ -449,6 +449,7 @@ public: [[nodiscard]] Expected<void> setRegister(Register Reg); [[nodiscard]] Expected<void> setRegisterFlags(RegisterOperandFlags Flags); [[nodiscard]] Expected<void> setSubReg(SubRegIndex SubReg); + [[nodiscard]] Expected<void> setBasicBlock(MachineBasicBlock &Block); [[nodiscard]] std::optional<std::size_t> tiedOperandIndex() const noexcept { return TiedOperandIndex; diff --git a/backend/include/rcc/CodeGen/MachineSSAExit.h b/backend/include/rcc/CodeGen/MachineSSAExit.h new file mode 100644 index 0000000..d98c0b9 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineSSAExit.h @@ -0,0 +1,49 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINESSAEXIT_H +#define RCC_CODEGEN_MACHINESSAEXIT_H + +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/TargetCodeGen.h" + +namespace rcc { + +class PHIEliminationPass final : public MachineFunctionPass { +public: + PHIEliminationPass() noexcept = default; + explicit PHIEliminationPass(const TargetSSAInfo &Info) noexcept : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses); + + const TargetSSAInfo *Info = nullptr; +}; + +class TwoAddressRewritePass final : public MachineFunctionPass { +public: + TwoAddressRewritePass() noexcept = default; + explicit TwoAddressRewritePass(const TargetSSAInfo &Info) noexcept : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses); + + const TargetSSAInfo *Info = nullptr; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINESSAEXIT_H diff --git a/backend/include/rcc/CodeGen/TargetCodeGen.h b/backend/include/rcc/CodeGen/TargetCodeGen.h index b1be1f6..f2aac5d 100644 --- a/backend/include/rcc/CodeGen/TargetCodeGen.h +++ b/backend/include/rcc/CodeGen/TargetCodeGen.h @@ -7,12 +7,14 @@ #include "rcc/CodeGen/Register.h" #include "rcc/Support/Error.h" +#include <cstddef> #include <cstdint> #include <optional> namespace rcc { class MachineFunction; +class MachineBasicBlock; class MachineInstr; class MachineRegisterInfo; class TargetDescription; @@ -89,6 +91,38 @@ public: } }; +class TargetSSAInfo { +public: + virtual ~TargetSSAInfo() = default; + + [[nodiscard]] virtual Expected<bool> isFallthroughEdge(const MachineBasicBlock &From, + const MachineBasicBlock &To, + const MachineFunction &Function, + const TargetDescription &Target) const = 0; + + [[nodiscard]] virtual Expected<bool> + rewriteBranchTarget(MachineBasicBlock &Block, MachineBasicBlock &OldTarget, + MachineBasicBlock &NewTarget, MachineFunction &Function, + const TargetDescription &Target) const = 0; + + [[nodiscard]] virtual Expected<void> + insertUnconditionalBranch(MachineBasicBlock &Block, MachineBasicBlock &Target, + MachineFunction &Function, + const TargetDescription &TargetDescription) const = 0; + + [[nodiscard]] virtual Expected<void> validateCopy(Register Destination, + SubRegIndex DestinationSubReg, Register Source, + SubRegIndex SourceSubReg, + const MachineFunction &Function, + const TargetDescription &Target) const = 0; + + [[nodiscard]] virtual Expected<bool> tryConvertToThreeAddress(MachineInstr &, std::size_t, + std::size_t, MachineFunction &, + const TargetDescription &) const { + return false; + } +}; + } // namespace rcc #endif // RCC_CODEGEN_TARGETCODEGEN_H diff --git a/backend/include/rcc/CodeGen/TargetDescription.h b/backend/include/rcc/CodeGen/TargetDescription.h index c2a4133..7e41a58 100644 --- a/backend/include/rcc/CodeGen/TargetDescription.h +++ b/backend/include/rcc/CodeGen/TargetDescription.h @@ -72,6 +72,9 @@ public: std::span<const MachineMemOperand *const> MemOperands) const; [[nodiscard]] Expected<void> validateInstruction(const MachineInstr &Instruction, const MachineRegisterInfo &RegInfo) const; + [[nodiscard]] Expected<void> validateTieCompatibility(const MachineOperand &Def, + const MachineOperand &Use, + const MachineRegisterInfo &RegInfo) const; [[nodiscard]] Expected<void> validateCFIInfo(const MachineCFIInfo &Info) const; [[nodiscard]] Expected<void> validateFrameInfo(const MachineFrameInfo &Info) const; [[nodiscard]] Expected<void> validateRegisterInfo(const MachineRegisterInfo &RegInfo) const; @@ -95,10 +98,6 @@ private: const VirtualRegisterInfo &Info) const; [[nodiscard]] std::optional<RegisterClassID> effectiveRegisterClass(const MachineOperand &Operand, const MachineRegisterInfo &RegInfo) const; - [[nodiscard]] Expected<void> validateTieCompatibility(const MachineOperand &Def, - const MachineOperand &Use, - const MachineRegisterInfo &RegInfo) const; - InstructionSet Instructions; TargetRegisterInfo Registers; TargetMIRTextInfo MIRText; diff --git a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h index b06f20d..4db60f7 100644 --- a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h +++ b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h @@ -10,6 +10,7 @@ namespace rcc::riscv { [[nodiscard]] const TargetLegalizerInfo &legalizerInfo() noexcept; [[nodiscard]] const TargetRegisterBankInfo ®isterBankInfo() noexcept; [[nodiscard]] const TargetInstructionSelector &instructionSelector() noexcept; +[[nodiscard]] const TargetSSAInfo &ssaInfo() noexcept; } // namespace rcc::riscv diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index f2c81f2..5cff572 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -29,6 +29,7 @@ set( MachinePass.cpp MachinePipelinePasses.cpp MachineRegisterInfo.cpp + MachineSSAExit.cpp MachineVerifier.cpp MachineFunctionProperties.cpp MachineFunctionRecords.cpp @@ -71,6 +72,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePipelinePasses.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetCodeGen.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineSSAExit.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineVerifier.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionRecords.h" @@ -141,6 +143,7 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp" @@ -182,6 +185,7 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp" diff --git a/backend/lib/CodeGen/GenericOpcodes.cpp b/backend/lib/CodeGen/GenericOpcodes.cpp index 0b0e0fe..1394507 100644 --- a/backend/lib/CodeGen/GenericOpcodes.cpp +++ b/backend/lib/CodeGen/GenericOpcodes.cpp @@ -102,7 +102,7 @@ using GO = GenericOpcode; OperandDescriptor Result; Result.Kinds = {MachineOperand::Kind::Register}; Result.RegisterRole = Role; - Result.TypeConstraint = OperandTypeConstraint{std::move(Kinds), Group}; + Result.TypeConstraint = OperandTypeConstraint{Kinds, Group}; return Result; } @@ -146,6 +146,11 @@ using GO = GenericOpcode; return Descriptor; } +[[nodiscard]] OperandDescriptor registeredTargetFlags(OperandDescriptor Descriptor) { + Descriptor.AllowAnyTargetFlags = true; + return Descriptor; +} + class DescriptorRegistry final { public: DescriptorRegistry() { @@ -158,7 +163,7 @@ public: #undef RCC_CORE_OPCODE } - void configure(std::initializer_list<GO> Opcodes, std::vector<OperandDescriptor> Operands, + void configure(std::initializer_list<GO> Opcodes, const std::vector<OperandDescriptor> &Operands, std::size_t NumDefs, std::initializer_list<InstructionFlag> Flags = {}, bool Variadic = false, std::size_t MinimumRepetitions = 0, bool RequiresMemoryOperands = false, PseudoOwner Owner = PseudoOwner::None, @@ -322,9 +327,10 @@ private: auto Info = RegInfo.virtualRegisterInfo(*Reg); if (!Info) return std::unexpected(Info.error()); - if (!Info->get().Type) + const std::optional<LLT> &Type = Info->get().Type; + if (!Type) return semanticError("generic virtual register is missing its LLT"); - Types[Index] = *Info->get().Type; + Types[Index] = Type.value(); } const auto TypeAt = [&Types](std::size_t Index) -> LLT { return *Types[Index]; }; @@ -773,7 +779,7 @@ private: } case GO::G_INTRINSIC_FPTRUNC_ROUND: { const auto Rounding = plainImmediate(Operands[2]); - if (!Rounding || !((*Rounding >= 0 && *Rounding <= 4) || *Rounding == 7)) + if (!Rounding || *Rounding < 0 || (*Rounding > 4 && *Rounding != 7)) return semanticError("floating truncation rounding mode is invalid"); return VerifyWidthChange(false); } @@ -980,14 +986,17 @@ private: void configureCoreOpcodes(DescriptorRegistry &Registry) { const auto RegDef = untypedRegister(RegisterOperandRole::Def); const auto RegUse = untypedRegister(RegisterOperandRole::Use); + const auto TransferDef = registeredTargetFlags(RegDef); + const auto TransferUse = registeredTargetFlags(RegUse); const auto Any = anyOperand(); const auto VariadicAny = repeated(Any); const auto VariadicUse = repeated(RegUse); - Registry.configure({GO::PHI}, - {RegDef, VariadicUse, repeated(kind(MachineOperand::Kind::BasicBlock))}, 1, - {InstructionFlag::Phi}, true, 1, false, PseudoOwner::PhiElimination, - PipelineStage::SSAEliminated); + Registry.configure( + {GO::PHI}, + {TransferDef, repeated(TransferUse), repeated(kind(MachineOperand::Kind::BasicBlock))}, 1, + {InstructionFlag::Phi}, true, 1, false, PseudoOwner::PhiElimination, + PipelineStage::SSAEliminated); Registry.configure({GO::INLINEASM}, {VariadicAny}, 0, {InstructionFlag::ProducesCode, InstructionFlag::TerminalEmission, InstructionFlag::UnmodeledSideEffects}, @@ -1004,10 +1013,11 @@ void configureCoreOpcodes(DescriptorRegistry &Registry) { Registry.configure({GO::KILL}, {VariadicUse}, 0, {InstructionFlag::Meta}, true); Registry.configure({GO::EXTRACT_SUBREG}, {RegDef, RegUse, immediate()}, 1, {}, false, 0, false, PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized); - Registry.configure({GO::INSERT_SUBREG}, {RegDef, RegUse, RegUse, immediate()}, 1, {}, false, 0, - false, PseudoOwner::TwoAddressRewrite, PipelineStage::TiedOpsRewritten); + Registry.configure({GO::INSERT_SUBREG}, {TransferDef, TransferUse, TransferUse, immediate()}, 1, + {}, false, 0, false, PseudoOwner::TwoAddressRewrite, + PipelineStage::TiedOpsRewritten); Registry.tie(GO::INSERT_SUBREG, 0, 1); - Registry.configure({GO::IMPLICIT_DEF}, {RegDef}, 1, + Registry.configure({GO::IMPLICIT_DEF}, {TransferDef}, 1, {InstructionFlag::Meta, InstructionFlag::Rematerializable}); Registry.configure({GO::INIT_UNDEF}, {RegDef}, 1, {}, false, 0, false, PseudoOwner::RegisterAllocator, PipelineStage::RegisterAllocated); @@ -1019,10 +1029,10 @@ void configureCoreOpcodes(DescriptorRegistry &Registry) { {VariadicAny}, 0, {InstructionFlag::Meta}, true); Registry.configure({GO::DBG_LABEL}, {kind(MachineOperand::Kind::Metadata)}, 0, {InstructionFlag::Meta}); - Registry.configure({GO::REG_SEQUENCE}, {RegDef, repeated(RegUse), repeated(immediate())}, 1, {}, - true, 1, false, PseudoOwner::TwoAddressRewrite, - PipelineStage::TiedOpsRewritten); - Registry.configure({GO::COPY}, {RegDef, RegUse}, 1, {}, false, 0, false, + Registry.configure({GO::REG_SEQUENCE}, + {TransferDef, repeated(TransferUse), repeated(immediate())}, 1, {}, true, 1, + false, PseudoOwner::TwoAddressRewrite, PipelineStage::TiedOpsRewritten); + Registry.configure({GO::COPY}, {TransferDef, TransferUse}, 1, {}, false, 0, false, PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized); Registry.configure({GO::COPY_LANEMASK}, {RegDef, RegUse, kind(MachineOperand::Kind::LaneMask)}, 1, {}, false, 0, false, PseudoOwner::PostRAExpansion, @@ -1170,10 +1180,13 @@ void configureGenericOpcodes(DescriptorRegistry &Registry) { InstructionFlag::Commutable); Registry.configure({GO::G_SDIVREM, GO::G_UDIVREM}, {IntDef0, IntDef0, IntUse0, IntUse0}, 2); - Registry.configure({GO::G_IMPLICIT_DEF}, {AnyDef0}, 1); - Registry.configure({GO::G_PHI}, - {AnyDef0, repeated(AnyUse0), repeated(kind(MachineOperand::Kind::BasicBlock))}, - 1, {InstructionFlag::Phi}, true, 1); + const auto TransferDef0 = registeredTargetFlags(AnyDef0); + const auto TransferUse0 = registeredTargetFlags(AnyUse0); + Registry.configure({GO::G_IMPLICIT_DEF}, {TransferDef0}, 1); + Registry.configure( + {GO::G_PHI}, + {TransferDef0, repeated(TransferUse0), repeated(kind(MachineOperand::Kind::BasicBlock))}, 1, + {InstructionFlag::Phi}, true, 1); Registry.configure({GO::G_FRAME_INDEX}, {ScalarPointerDef0, kind(MachineOperand::Kind::FrameIndex)}, 1); Registry.configure({GO::G_GLOBAL_VALUE}, diff --git a/backend/lib/CodeGen/InstructionDescriptor.cpp b/backend/lib/CodeGen/InstructionDescriptor.cpp index 57400d6..5aec744 100644 --- a/backend/lib/CodeGen/InstructionDescriptor.cpp +++ b/backend/lib/CodeGen/InstructionDescriptor.cpp @@ -420,11 +420,12 @@ Expected<void> InstructionSet::validateExplicitOperands(const InstructionDescrip auto Info = RegInfo.virtualRegisterInfo(*Reg); if (!Info) return std::unexpected(Info.error()); - if (!Info->get().Type) { + const std::optional<LLT> &RegisterType = Info->get().Type; + if (!RegisterType) { return makeUnexpected(ErrorCode::VerificationError, "typed instruction operand virtual register has no LLT"); } - const LLT Type = *Info->get().Type; + const LLT Type = RegisterType.value(); if (!OperandDesc.TypeConstraint->Kinds.contains(Type.kind())) { return makeUnexpected(ErrorCode::VerificationError, "instruction operand LLT kind is not permitted by its descriptor"); @@ -587,7 +588,8 @@ Expected<void> InstructionSet::validateOperand(const OperandDescriptor &Descript return makeUnexpected(ErrorCode::VerificationError, "instruction operand kind does not match its descriptor"); } - if ((Operand.targetFlags() & ~Descriptor.AllowedTargetFlags) != 0) { + if (!Descriptor.AllowAnyTargetFlags && + (Operand.targetFlags() & ~Descriptor.AllowedTargetFlags) != 0) { return makeUnexpected(ErrorCode::VerificationError, "instruction operand uses unregistered target flags"); } diff --git a/backend/lib/CodeGen/MachineCFGUpdater.cpp b/backend/lib/CodeGen/MachineCFGUpdater.cpp index c78e318..4aacdf5 100644 --- a/backend/lib/CodeGen/MachineCFGUpdater.cpp +++ b/backend/lib/CodeGen/MachineCFGUpdater.cpp @@ -2,18 +2,108 @@ #include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/GenericOpcodes.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" #include <algorithm> #include <cstddef> #include <optional> +#include <span> #include <utility> #include <vector> namespace rcc { namespace { +struct PhiIncomingEdit final { + MachineInstr *Phi = nullptr; + std::size_t ValueIndex = 0; +}; + +[[nodiscard]] bool isKnownPhi(const MachineInstr &Instruction) noexcept { + return Instruction.opcode() == opcode(GenericOpcode::PHI) || + Instruction.opcode() == opcode(GenericOpcode::G_PHI); +} + +[[nodiscard]] bool containsKnownPhi(const MachineBasicBlock &Block) noexcept { + for (const MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (isKnownPhi(*Instruction)) + return true; + } + return false; +} + +[[nodiscard]] Expected<std::vector<PhiIncomingEdit>> +collectPhiIncomingEdits(MachineBasicBlock &Block, const MachineBasicBlock &Predecessor) { + std::vector<PhiIncomingEdit> Result; + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (!isKnownPhi(*Instruction)) + continue; + if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "CFG update encountered a malformed PHI instruction"); + } + + std::optional<std::size_t> Match; + for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) { + const MachineOperand *Value = Instruction->operandAt(Index); + const MachineOperand *BlockOperand = Instruction->operandAt(Index + 1U); + const Register *Reg = Value == nullptr ? nullptr : Value->getIf<Register>(); + const BasicBlockOperand *Incoming = + BlockOperand == nullptr ? nullptr : BlockOperand->getIf<BasicBlockOperand>(); + if (Reg == nullptr || Incoming == nullptr || Incoming->Block == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "CFG update encountered malformed PHI incoming operands"); + } + if (Incoming->Block != &Predecessor) + continue; + if (Match) { + return makeUnexpected(ErrorCode::VerificationError, + "CFG update encountered duplicate PHI incoming blocks"); + } + Match = Index; + } + if (!Match) { + return makeUnexpected(ErrorCode::VerificationError, + "CFG edge has no corresponding PHI incoming value"); + } + Result.push_back(PhiIncomingEdit{Instruction, *Match}); + } + return Result; +} + +[[nodiscard]] Expected<void> erasePhiIncoming(std::span<const PhiIncomingEdit> Edits) { + for (const PhiIncomingEdit &Edit : Edits) { + auto BlockErased = Edit.Phi->eraseOperand(Edit.ValueIndex + 1U); + if (!BlockErased) + return std::unexpected(BlockErased.error()); + auto ValueErased = Edit.Phi->eraseOperand(Edit.ValueIndex); + if (!ValueErased) + return std::unexpected(ValueErased.error()); + } + return {}; +} + +[[nodiscard]] Expected<void> rewritePhiIncoming(std::span<const PhiIncomingEdit> Edits, + MachineBasicBlock &NewPredecessor) { + for (const PhiIncomingEdit &Edit : Edits) { + MachineOperand *BlockOperand = Edit.Phi->operandAt(Edit.ValueIndex + 1U); + if (BlockOperand == nullptr) { + return makeUnexpected(ErrorCode::InternalError, + "PHI incoming operand disappeared during CFG update"); + } + auto Rewritten = BlockOperand->setBasicBlock(NewPredecessor); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + } + return {}; +} + [[nodiscard]] std::optional<std::size_t> findSuccessorIndex(const MachineBasicBlock &From, const MachineBasicBlock &To) { const auto Successors = From.successors(); @@ -24,6 +114,39 @@ namespace { return std::nullopt; } +[[nodiscard]] Expected<void> validateOutgoingEdges(MachineBasicBlock &From) { + for (const MachineSuccessor &Successor : From.successors()) { + if (Successor.Block == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "CFG successor is null"); + } + if (std::ranges::find(Successor.Block->predecessors(), &From) == + Successor.Block->predecessors().end()) { + return makeUnexpected(ErrorCode::VerificationError, + "CFG successor has no reciprocal predecessor"); + } + auto PhiEdits = collectPhiIncomingEdits(*Successor.Block, From); + if (!PhiEdits) + return std::unexpected(PhiEdits.error()); + } + return {}; +} + +[[nodiscard]] Expected<void> validateIncomingEdges(MachineBasicBlock &To) { + for (MachineBasicBlock *Predecessor : To.predecessors()) { + if (Predecessor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "CFG predecessor is null"); + } + if (!findSuccessorIndex(*Predecessor, To)) { + return makeUnexpected(ErrorCode::VerificationError, + "CFG predecessor has no reciprocal successor"); + } + auto PhiEdits = collectPhiIncomingEdits(To, *Predecessor); + if (!PhiEdits) + return std::unexpected(PhiEdits.error()); + } + return {}; +} + } // namespace Expected<void> MachineCFGUpdater::verifyOwnership(const MachineBasicBlock &Block) const { @@ -50,6 +173,15 @@ Expected<void> MachineCFGUpdater::addSuccessor(MachineBasicBlock &From, MachineB return {}; } + if (containsKnownPhi(To)) { + auto PhiEdits = collectPhiIncomingEdits(To, From); + if (!PhiEdits) { + return makeUnexpected( + ErrorCode::InvalidArgument, + "adding a predecessor to a PHI block requires explicit incoming values"); + } + } + From.Successors.push_back(MachineSuccessor{&To, Probability}); if (std::ranges::find(To.Predecessors, &From) == To.Predecessors.end()) To.Predecessors.push_back(&From); @@ -68,13 +200,20 @@ Expected<void> MachineCFGUpdater::removeSuccessor(MachineBasicBlock &From, Machi if (!Successor) { return makeUnexpected(ErrorCode::InvalidArgument, "CFG successor edge is not present"); } - From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Successor)); - const auto Predecessor = std::ranges::find(To.Predecessors, &From); if (Predecessor == To.Predecessors.end()) { return makeUnexpected(ErrorCode::VerificationError, "CFG successor has no reciprocal predecessor"); } + + auto PhiEdits = collectPhiIncomingEdits(To, From); + if (!PhiEdits) + return std::unexpected(PhiEdits.error()); + auto PhiResult = erasePhiIncoming(*PhiEdits); + if (!PhiResult) + return std::unexpected(PhiResult.error()); + + From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Successor)); To.Predecessors.erase(Predecessor); return {}; } @@ -101,18 +240,95 @@ Expected<void> MachineCFGUpdater::replaceSuccessor(MachineBasicBlock &From, } const BranchProbability Probability = From.Successors[*Existing].Probability; - auto RemoveResult = removeSuccessor(From, OldTarget); - if (!RemoveResult) - return std::unexpected(RemoveResult.error()); - auto AddResult = addSuccessor(From, NewTarget, Probability); - if (!AddResult) { - auto RestoreResult = addSuccessor(From, OldTarget, Probability); - if (!RestoreResult) { - return makeUnexpected(ErrorCode::InternalError, - "failed to restore CFG edge after replacement failure"); + const auto OldPredecessor = std::ranges::find(OldTarget.Predecessors, &From); + if (OldPredecessor == OldTarget.Predecessors.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "replaced CFG successor has no reciprocal predecessor"); + } + auto OldPhiEdits = collectPhiIncomingEdits(OldTarget, From); + if (!OldPhiEdits) + return std::unexpected(OldPhiEdits.error()); + + const auto NewEdge = findSuccessorIndex(From, NewTarget); + const auto NewPredecessor = std::ranges::find(NewTarget.Predecessors, &From); + if (NewEdge) { + if (NewPredecessor == NewTarget.Predecessors.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "replacement target has no reciprocal predecessor"); + } + auto NewPhiEdits = collectPhiIncomingEdits(NewTarget, From); + if (!NewPhiEdits) + return std::unexpected(NewPhiEdits.error()); + } else { + if (NewPredecessor != NewTarget.Predecessors.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "replacement target has a predecessor without a reciprocal edge"); + } + if (containsKnownPhi(NewTarget)) { + auto NewPhiEdits = collectPhiIncomingEdits(NewTarget, From); + if (!NewPhiEdits) { + return makeUnexpected( + ErrorCode::InvalidArgument, + "redirecting an edge to a PHI block requires explicit incoming values"); + } } - return std::unexpected(AddResult.error()); } + auto PhiResult = erasePhiIncoming(*OldPhiEdits); + if (!PhiResult) + return std::unexpected(PhiResult.error()); + OldTarget.Predecessors.erase(OldPredecessor); + if (NewEdge) { + From.Successors[*NewEdge].Probability = + From.Successors[*NewEdge].Probability.saturatingAdd(Probability); + From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Existing)); + } else { + From.Successors[*Existing].Block = &NewTarget; + if (std::ranges::find(NewTarget.Predecessors, &From) == NewTarget.Predecessors.end()) + NewTarget.Predecessors.push_back(&From); + } + return {}; +} + +Expected<void> MachineCFGUpdater::splitEdge(MachineBasicBlock &From, MachineBasicBlock &To, + MachineBasicBlock &EdgeBlock) { + auto FromOwnership = verifyOwnership(From); + if (!FromOwnership) + return std::unexpected(FromOwnership.error()); + auto ToOwnership = verifyOwnership(To); + if (!ToOwnership) + return std::unexpected(ToOwnership.error()); + auto EdgeOwnership = verifyOwnership(EdgeBlock); + if (!EdgeOwnership) + return std::unexpected(EdgeOwnership.error()); + if (&From == &To || &From == &EdgeBlock || &To == &EdgeBlock) { + return makeUnexpected(ErrorCode::InvalidArgument, + "edge split requires three distinct basic blocks"); + } + if (!EdgeBlock.isLinked() || EdgeBlock.firstInstruction() != nullptr || + !EdgeBlock.predecessors().empty() || !EdgeBlock.successors().empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "edge split block must be linked, empty, and disconnected"); + } + + const auto Successor = findSuccessorIndex(From, To); + if (!Successor) + return makeUnexpected(ErrorCode::InvalidArgument, "split CFG edge is not present"); + auto Predecessor = std::ranges::find(To.Predecessors, &From); + if (Predecessor == To.Predecessors.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "split CFG edge has no reciprocal predecessor"); + } + auto PhiEdits = collectPhiIncomingEdits(To, From); + if (!PhiEdits) + return std::unexpected(PhiEdits.error()); + + auto PhiResult = rewritePhiIncoming(*PhiEdits, EdgeBlock); + if (!PhiResult) + return std::unexpected(PhiResult.error()); + From.Successors[*Successor].Block = &EdgeBlock; + *Predecessor = &EdgeBlock; + EdgeBlock.Predecessors.push_back(&From); + EdgeBlock.Successors.push_back(MachineSuccessor{&To, BranchProbability::one()}); return {}; } @@ -145,15 +361,67 @@ Expected<void> MachineCFGUpdater::transferSuccessors(MachineBasicBlock &From, if (&From == &To) return {}; - const std::vector<MachineSuccessor> Successors = From.Successors; - for (const MachineSuccessor &Successor : Successors) { - auto RemoveResult = removeSuccessor(From, *Successor.Block); - if (!RemoveResult) - return std::unexpected(RemoveResult.error()); - auto AddResult = addSuccessor(To, *Successor.Block, Successor.Probability); - if (!AddResult) - return std::unexpected(AddResult.error()); + struct Transfer final { + MachineSuccessor Successor; + std::vector<PhiIncomingEdit> PhiEdits; + bool MergeExisting = false; + }; + std::vector<Transfer> Transfers; + Transfers.reserve(From.Successors.size()); + for (const MachineSuccessor &Successor : From.Successors) { + if (Successor.Block == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "transferred CFG successor is null"); + } + if (std::ranges::find(Successor.Block->Predecessors, &From) == + Successor.Block->Predecessors.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "transferred CFG successor has no reciprocal predecessor"); + } + auto PhiEdits = collectPhiIncomingEdits(*Successor.Block, From); + if (!PhiEdits) + return std::unexpected(PhiEdits.error()); + const bool MergeExisting = findSuccessorIndex(To, *Successor.Block).has_value(); + const auto ToPredecessor = std::ranges::find(Successor.Block->Predecessors, &To); + if (MergeExisting) { + if (ToPredecessor == Successor.Block->Predecessors.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "transfer target edge has no reciprocal predecessor"); + } + auto ExistingPhiEdits = collectPhiIncomingEdits(*Successor.Block, To); + if (!ExistingPhiEdits) + return std::unexpected(ExistingPhiEdits.error()); + } else if (ToPredecessor != Successor.Block->Predecessors.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "transfer target is a predecessor without a reciprocal edge"); + } + Transfers.push_back(Transfer{Successor, std::move(*PhiEdits), MergeExisting}); } + + for (Transfer &TransferValue : Transfers) { + MachineBasicBlock &Successor = *TransferValue.Successor.Block; + auto OldPredecessor = std::ranges::find(Successor.Predecessors, &From); + if (TransferValue.MergeExisting) { + auto PhiResult = erasePhiIncoming(TransferValue.PhiEdits); + if (!PhiResult) + return std::unexpected(PhiResult.error()); + Successor.Predecessors.erase(OldPredecessor); + const std::optional<std::size_t> Existing = findSuccessorIndex(To, Successor); + if (!Existing) { + return makeUnexpected(ErrorCode::InternalError, + "preflighted transfer target edge disappeared"); + } + To.Successors[Existing.value()].Probability = + To.Successors[Existing.value()].Probability.saturatingAdd( + TransferValue.Successor.Probability); + } else { + auto PhiResult = rewritePhiIncoming(TransferValue.PhiEdits, To); + if (!PhiResult) + return std::unexpected(PhiResult.error()); + *OldPredecessor = &To; + To.Successors.push_back(TransferValue.Successor); + } + } + From.Successors.clear(); return {}; } @@ -162,6 +430,13 @@ Expected<void> MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) { if (!Ownership) return std::unexpected(Ownership.error()); + auto Outgoing = validateOutgoingEdges(Block); + if (!Outgoing) + return std::unexpected(Outgoing.error()); + auto Incoming = validateIncomingEdges(Block); + if (!Incoming) + return std::unexpected(Incoming.error()); + const std::vector<MachineSuccessor> Successors = Block.Successors; for (const MachineSuccessor &Successor : Successors) { auto Result = removeSuccessor(Block, *Successor.Block); @@ -178,4 +453,70 @@ Expected<void> MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) { return {}; } +Expected<MachineBasicBlock *> MachineCFGUpdater::splitBlock(MachineBasicBlock &Block, + MachineInstr &SplitBefore) { + auto Ownership = verifyOwnership(Block); + if (!Ownership) + return std::unexpected(Ownership.error()); + if (!Block.isLinked() || SplitBefore.parent() != &Block) { + return makeUnexpected(ErrorCode::InvalidArgument, + "split point is not linked to the requested basic block"); + } + bool MovesPhi = false; + for (const MachineInstr *Instruction = &SplitBefore; Instruction != nullptr; + Instruction = Instruction->next()) { + MovesPhi |= isKnownPhi(*Instruction); + } + if (MovesPhi) { + return makeUnexpected(ErrorCode::InvalidArgument, + "a basic block cannot be split inside its PHI region"); + } + + auto Outgoing = validateOutgoingEdges(Block); + if (!Outgoing) + return std::unexpected(Outgoing.error()); + + auto NewBlockResult = Function->createBasicBlock(); + if (!NewBlockResult) + return std::unexpected(NewBlockResult.error()); + MachineBasicBlock *NewBlock = *NewBlockResult; + Expected<void> Inserted = Block.next() == nullptr + ? Function->appendBlock(*NewBlock) + : Function->insertBlockBefore(*Block.next(), *NewBlock); + if (!Inserted) + return std::unexpected(Inserted.error()); + + MachineInstr *Instruction = &SplitBefore; + while (Instruction != nullptr) { + MachineInstr *Next = Instruction->next(); + auto Removed = Block.removeInstruction(*Instruction); + if (!Removed) + return std::unexpected(Removed.error()); + auto Appended = NewBlock->appendInstruction(*Instruction); + if (!Appended) + return std::unexpected(Appended.error()); + Instruction = Next; + } + + auto Transferred = transferSuccessors(Block, *NewBlock); + if (!Transferred) + return std::unexpected(Transferred.error()); + auto Connected = addSuccessor(Block, *NewBlock, BranchProbability::one()); + if (!Connected) + return std::unexpected(Connected.error()); + return NewBlock; +} + +Expected<void> MachineCFGUpdater::deleteBlock(MachineBasicBlock &Block) { + auto Ownership = verifyOwnership(Block); + if (!Ownership) + return std::unexpected(Ownership.error()); + if (!Block.isLinked()) + return makeUnexpected(ErrorCode::InvalidArgument, "deleted CFG block is not linked"); + auto Disconnected = disconnectBlock(Block); + if (!Disconnected) + return std::unexpected(Disconnected.error()); + return Function->removeBlock(Block); +} + } // namespace rcc diff --git a/backend/lib/CodeGen/MachineOperand.cpp b/backend/lib/CodeGen/MachineOperand.cpp index ae46505..43a4f91 100644 --- a/backend/lib/CodeGen/MachineOperand.cpp +++ b/backend/lib/CodeGen/MachineOperand.cpp @@ -2,6 +2,7 @@ #include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineRegisterInfo.h" @@ -172,8 +173,7 @@ std::string IntegerImmediate::toUnsignedDecimal() const { return "0"; std::vector<std::uint64_t> Remaining = Words; std::string Digits; - while (!std::ranges::all_of(Remaining, - [](std::uint64_t Word) { return Word == 0; })) { + while (!std::ranges::all_of(Remaining, [](std::uint64_t Word) { return Word == 0; })) { unsigned __int128 Remainder = 0; for (auto Iterator = Remaining.rbegin(); Iterator != Remaining.rend(); ++Iterator) { const unsigned __int128 Dividend = (Remainder << 64U) | *Iterator; @@ -537,6 +537,17 @@ Expected<void> MachineOperand::setSubReg(SubRegIndex SubReg) { return {}; } +Expected<void> MachineOperand::setBasicBlock(MachineBasicBlock &Block) { + if (OperandKind != Kind::BasicBlock) + return makeUnexpected(ErrorCode::InvalidArgument, + "setBasicBlock requires a basic-block operand"); + if (Parent != nullptr && &Block.function() != &Parent->function()) + return makeUnexpected(ErrorCode::InvalidArgument, + "basic-block operand references another machine function"); + std::get<BasicBlockOperand>(Storage).Block = &Block; + return {}; +} + MachineOperand MachineOperand::cloneDetached() const { MachineOperand Result(OperandKind, Storage, TargetFlags); Result.RegFlags = RegFlags; diff --git a/backend/lib/CodeGen/MachineSSAExit.cpp b/backend/lib/CodeGen/MachineSSAExit.cpp new file mode 100644 index 0000000..e77bb2a --- /dev/null +++ b/backend/lib/CodeGen/MachineSSAExit.cpp @@ -0,0 +1,1090 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineSSAExit.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineFunctionCloner.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 <algorithm> +#include <cstddef> +#include <cstdint> +#include <limits> +#include <optional> +#include <ranges> +#include <string> +#include <unordered_map> +#include <unordered_set> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +struct EdgeKey final { + const MachineBasicBlock *From = nullptr; + const MachineBasicBlock *To = nullptr; + + friend bool operator==(const EdgeKey &, const EdgeKey &) noexcept = default; +}; + +struct EdgeKeyHash final { + [[nodiscard]] std::size_t operator()(const EdgeKey &Key) const noexcept { + const std::size_t FromHash = std::hash<const MachineBasicBlock *>{}(Key.From); + const std::size_t ToHash = std::hash<const MachineBasicBlock *>{}(Key.To); + return FromHash ^ (ToHash << 1U); + } +}; + +struct RegisterValue final { + Register Reg; + SubRegIndex SubReg; + RegisterOperandFlags Flags; + std::uint32_t TargetFlags = 0; +}; + +struct PhiIncoming final { + RegisterValue Value; + MachineBasicBlock *Predecessor = nullptr; + bool IsUndef = false; +}; + +struct PhiPlan final { + MachineInstr *Instruction = nullptr; + RegisterValue Destination; + Register FreshIncoming; + std::vector<PhiIncoming> IncomingValues; +}; + +[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) { + Prefix.append(Source.message()); + return Error(Source.code(), std::move(Prefix)); +} + +[[nodiscard]] Expected<void> requireProperties(const MachineFunction &Function, + const MachinePassContract &Contract) { + const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties()); + if (Missing.empty()) + return {}; + return makeUnexpected(ErrorCode::VerificationError, + Contract.Name + " requires properties: " + Missing.toString()); +} + +[[nodiscard]] bool isPhi(const MachineInstr &Instruction, const TargetDescription &Target) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Phi); +} + +[[nodiscard]] bool isMeta(const MachineInstr &Instruction, const TargetDescription &Target) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Meta); +} + +[[nodiscard]] MachineInstr *firstTerminator(MachineBasicBlock &Block, + const TargetDescription &Target) { + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator)) + return Instruction; + } + return nullptr; +} + +[[nodiscard]] MachineInstr *firstCodeAfterPhiRegion(MachineBasicBlock &Block, + const TargetDescription &Target) { + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (!isPhi(*Instruction, Target) && !isMeta(*Instruction, Target)) + return Instruction; + } + return nullptr; +} + +[[nodiscard]] RegisterOperandFlags generatedDefFlags(RegisterOperandFlags Original) noexcept { + RegisterOperandFlags Result; + if (Original.has(RegisterOperandFlag::Undef)) + Result.set(RegisterOperandFlag::Undef); + return Result; +} + +[[nodiscard]] Expected<void> copyDebugLocation(MachineInstrBuilder &Builder, + const MachineInstr *Source) { + if (Source == nullptr || !Source->debugLocation()) + return {}; + return Builder.setDebugLocation(*Source->debugLocation()); +} + +[[nodiscard]] Expected<Register> cloneRegisterConstraints(MachineFunction &Function, + Register Source) { + if (!Source.isVirtual()) { + return makeUnexpected(ErrorCode::VerificationError, + "SSA deconstruction requires a virtual PHI destination"); + } + auto SourceInfo = Function.registerInfo().virtualRegisterInfo(Source); + if (!SourceInfo) + return std::unexpected(SourceInfo.error()); + const VirtualRegisterInfo Info = SourceInfo->get(); + + auto Fresh = Function.registerInfo().createVirtualRegister(); + if (!Fresh) + return std::unexpected(Fresh.error()); + if (Info.Type) { + auto SetType = Function.registerInfo().setType(*Fresh, *Info.Type); + if (!SetType) + return std::unexpected(SetType.error()); + } + if (Info.Bank) { + auto SetBank = Function.registerInfo().setRegisterBank(*Fresh, *Info.Bank); + if (!SetBank) + return std::unexpected(SetBank.error()); + } + if (Info.RegClass) { + auto SetClass = Function.registerInfo().setRegisterClass(*Fresh, *Info.RegClass); + if (!SetClass) + return std::unexpected(SetClass.error()); + } + for (const PhysicalRegister Hint : Info.AllocationHints) { + auto AddedHint = Function.registerInfo().addAllocationHint(*Fresh, Hint); + if (!AddedHint) + return std::unexpected(AddedHint.error()); + } + if (Info.TargetFlags != 0) { + auto SetFlags = Function.registerInfo().setTargetRegisterFlags(*Fresh, Info.TargetFlags); + if (!SetFlags) + return std::unexpected(SetFlags.error()); + } + return *Fresh; +} + +[[nodiscard]] Expected<MachineInstr *> +buildCopy(MachineFunction &Function, const TargetDescription &Target, + const TargetSSAInfo &TargetInfo, MachineBasicBlock &Block, MachineInstr *Before, + RegisterValue Destination, RegisterValue Source, const MachineInstr *DebugSource) { + auto Legality = TargetInfo.validateCopy(Destination.Reg, Destination.SubReg, Source.Reg, + Source.SubReg, Function, Target); + if (!Legality) + return std::unexpected(prefixedError(Legality.error(), "illegal COPY: ")); + + MachineIRBuilder Builder(Function, Target); + auto Point = + Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(opcode(GenericOpcode::COPY)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Destination.Reg, generatedDefFlags(Destination.Flags), + Destination.SubReg, Destination.TargetFlags); + if (!Def) + return std::unexpected(Def.error()); + auto Use = Pending->addUse(Source.Reg, {}, Source.SubReg, Source.TargetFlags); + if (!Use) + return std::unexpected(Use.error()); + auto Debug = copyDebugLocation(*Pending, DebugSource); + if (!Debug) + return std::unexpected(Debug.error()); + return Pending->build(); +} + +[[nodiscard]] Expected<MachineInstr *> +buildImplicitDef(MachineFunction &Function, const TargetDescription &Target, + MachineBasicBlock &Block, MachineInstr *Before, RegisterValue Destination, + const MachineInstr *DebugSource) { + MachineIRBuilder Builder(Function, Target); + auto Point = + Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(opcode(GenericOpcode::IMPLICIT_DEF)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Destination.Reg, generatedDefFlags(Destination.Flags), + Destination.SubReg, Destination.TargetFlags); + if (!Def) + return std::unexpected(Def.error()); + auto Debug = copyDebugLocation(*Pending, DebugSource); + if (!Debug) + return std::unexpected(Debug.error()); + return Pending->build(); +} + +[[nodiscard]] bool isImplicitlyUndef(const MachineFunction &Function, + const MachineOperand &Operand) { + if (Operand.registerFlags().has(RegisterOperandFlag::Undef)) + return true; + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || Reg->isNoRegister()) + return true; + if (!Reg->isVirtual()) + return false; + const MachineOperand *Definition = Function.registerInfo().getUniqueVRegDef(*Reg); + if (Definition == nullptr || Definition->parent() == nullptr) + return false; + if (Definition->subReg().value() != 0 && Definition->subReg() != Operand.subReg()) + return false; + const Opcode DefinitionOpcode = Definition->parent()->opcode(); + return DefinitionOpcode == opcode(GenericOpcode::IMPLICIT_DEF) || + DefinitionOpcode == opcode(GenericOpcode::G_IMPLICIT_DEF) || + Definition->registerFlags().has(RegisterOperandFlag::Undef); +} + +[[nodiscard]] Expected<void> validatePhiValue(const MachineFunction &Function, + const TargetDescription &Target, + const MachineOperand &Destination, + const MachineOperand &Source) { + const Register *DestinationReg = Destination.getIf<Register>(); + const Register *SourceReg = Source.getIf<Register>(); + if (DestinationReg == nullptr || SourceReg == nullptr) + return makeUnexpected(ErrorCode::VerificationError, "PHI operands must name registers"); + if (SourceReg->isNoRegister()) + return {}; + + if (DestinationReg->isVirtual() && SourceReg->isVirtual()) { + auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(*DestinationReg); + if (!DestinationInfo) + return std::unexpected(DestinationInfo.error()); + auto SourceInfo = Function.registerInfo().virtualRegisterInfo(*SourceReg); + if (!SourceInfo) + return std::unexpected(SourceInfo.error()); + if (DestinationInfo->get().Type && SourceInfo->get().Type && + DestinationInfo->get().Type != SourceInfo->get().Type) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI destination and incoming value types do not match"); + } + } + return Target.validateTieCompatibility(Destination, Source, Function.registerInfo()); +} + +[[nodiscard]] Expected<std::vector<PhiPlan>> collectPhiPlans(MachineBasicBlock &Block, + MachineFunction &Function, + const TargetDescription &Target) { + std::vector<PhiPlan> Plans; + bool SawCode = false; + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI elimination encountered an unknown opcode"); + } + if (Instruction->opcode() == opcode(GenericOpcode::G_PHI)) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI elimination requires G_PHI to be selected to PHI"); + } + if (!Descriptor->Flags.has(InstructionFlag::Phi)) { + SawCode |= !Descriptor->Flags.has(InstructionFlag::Meta); + continue; + } + if (SawCode) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI instruction appears after the leading PHI/meta region"); + } + if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI must contain a destination and incoming value/block pairs"); + } + + MachineOperand *DestinationOperand = Instruction->operandAt(0); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + if (Destination == nullptr || !Destination->isVirtual() || !DestinationOperand->isDef() || + DestinationOperand->isUse() || DestinationOperand->isImplicit()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI destination must be an explicit virtual-register definition"); + } + + PhiPlan Plan; + Plan.Instruction = Instruction; + Plan.Destination = + RegisterValue{*Destination, DestinationOperand->subReg(), + DestinationOperand->registerFlags(), DestinationOperand->targetFlags()}; + std::unordered_set<MachineBasicBlock *> SeenPredecessors; + for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) { + MachineOperand *SourceOperand = Instruction->operandAt(Index); + MachineOperand *BlockOperand = Instruction->operandAt(Index + 1U); + const Register *Source = + SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>(); + const BasicBlockOperand *IncomingBlock = + BlockOperand == nullptr ? nullptr : BlockOperand->getIf<BasicBlockOperand>(); + if (Source == nullptr || SourceOperand == nullptr || !SourceOperand->isUse() || + SourceOperand->isDef() || SourceOperand->isImplicit() || IncomingBlock == nullptr || + IncomingBlock->Block == nullptr || BlockOperand->isImplicit()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming operands must be explicit register/block pairs"); + } + if (std::ranges::find(Block.predecessors(), IncomingBlock->Block) == + Block.predecessors().end()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming block is not a CFG predecessor"); + } + if (!SeenPredecessors.insert(IncomingBlock->Block).second) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI contains duplicate incoming predecessors"); + } + auto Compatibility = validatePhiValue(Function, Target, *DestinationOperand, *SourceOperand); + if (!Compatibility) + return std::unexpected(Compatibility.error()); + Plan.IncomingValues.push_back( + PhiIncoming{RegisterValue{*Source, SourceOperand->subReg(), + SourceOperand->registerFlags(), SourceOperand->targetFlags()}, + IncomingBlock->Block, isImplicitlyUndef(Function, *SourceOperand)}); + } + if (SeenPredecessors.size() != Block.predecessors().size()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming blocks do not exactly cover CFG predecessors"); + } + Plans.push_back(std::move(Plan)); + } + return Plans; +} + +[[nodiscard]] Expected<void> copyLiveIns(const MachineBasicBlock &Source, + MachineBasicBlock &Destination) { + for (const MachineBasicBlockLiveIn &LiveIn : Source.liveIns()) { + auto Added = Destination.addLiveIn(LiveIn.PhysReg, LiveIn.Lanes); + if (!Added) + return std::unexpected(Added.error()); + } + return {}; +} + +[[nodiscard]] Expected<void> ensurePhysicalLiveIn(MachineBasicBlock &Block, PhysicalRegister Reg, + const TargetDescription &Target) { + const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Reg); + if (Description == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming value references an unknown physical register"); + } + LaneMask Required; + for (const RegisterUnitLane &Unit : Description->Units) + Required = Required | Unit.Lanes; + if (Required.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming physical register has no addressable lanes"); + } + + for (const MachineBasicBlockLiveIn &LiveIn : Block.liveIns()) { + if (LiveIn.PhysReg != Reg) + continue; + if (LiveIn.Lanes.contains(Required)) + return {}; + const LaneMask Combined = LiveIn.Lanes | Required; + auto Removed = Block.removeLiveIn(Reg); + if (!Removed) + return std::unexpected(Removed.error()); + return Block.addLiveIn(Reg, Combined); + } + return Block.addLiveIn(Reg, Required); +} + +[[nodiscard]] Expected<MachineBasicBlock *> +placePhiCopiesOnEdge(MachineFunction &Function, const TargetDescription &Target, + const TargetSSAInfo &TargetInfo, MachineBasicBlock &From, + MachineBasicBlock &To, + std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> &Cache, + MachinePassResult &PassResult) { + if (From.successors().size() <= 1) + return &From; + + const EdgeKey Key{&From, &To}; + if (const auto Existing = Cache.find(Key); Existing != Cache.end()) + return Existing->second; + if (std::ranges::none_of(From.successors(), [&To](const MachineSuccessor &Successor) { + return Successor.Block == &To; + })) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming predecessor has no edge to its successor"); + } + + auto SourceFallthrough = TargetInfo.isFallthroughEdge(From, To, Function, Target); + if (!SourceFallthrough) + return std::unexpected(SourceFallthrough.error()); + + MachineBasicBlock *LayoutPredecessor = To.previous(); + if (LayoutPredecessor != nullptr && LayoutPredecessor != &From) { + auto OtherFallthrough = TargetInfo.isFallthroughEdge(*LayoutPredecessor, To, Function, Target); + if (!OtherFallthrough) + return std::unexpected(OtherFallthrough.error()); + if (*OtherFallthrough) { + auto Branch = TargetInfo.insertUnconditionalBranch(*LayoutPredecessor, To, Function, Target); + if (!Branch) + return std::unexpected(Branch.error()); + PassResult.Changed = true; + PassResult.Changes.add(MachinePassChange::Instructions); + } + } + + auto EdgeBlockResult = Function.createBasicBlock(); + if (!EdgeBlockResult) + return std::unexpected(EdgeBlockResult.error()); + MachineBasicBlock *EdgeBlock = *EdgeBlockResult; + auto Inserted = Function.insertBlockBefore(To, *EdgeBlock); + if (!Inserted) + return std::unexpected(Inserted.error()); + + auto Rewritten = TargetInfo.rewriteBranchTarget(From, To, *EdgeBlock, Function, Target); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + if (!*Rewritten && !*SourceFallthrough) { + return makeUnexpected(ErrorCode::Unsupported, + "PHI elimination cannot split an indirect or unmodeled CFG edge"); + } + + auto Split = Function.cfgUpdater().splitEdge(From, To, *EdgeBlock); + if (!Split) + return std::unexpected(Split.error()); + auto LiveIns = copyLiveIns(To, *EdgeBlock); + if (!LiveIns) + return std::unexpected(LiveIns.error()); + auto Branch = TargetInfo.insertUnconditionalBranch(*EdgeBlock, To, Function, Target); + if (!Branch) + return std::unexpected(Branch.error()); + + Cache.emplace(Key, EdgeBlock); + PassResult.Changed = true; + PassResult.Changes.add(MachinePassChange::CFG); + PassResult.Changes.add(MachinePassChange::BlockLayout); + PassResult.Changes.add(MachinePassChange::Instructions); + if (*Rewritten) + PassResult.Changes.add(MachinePassChange::Operands); + return EdgeBlock; +} + +[[nodiscard]] Expected<bool> clearStaleLivenessFlags(MachineFunction &Function) { + bool Changed = false; + for (MachineInstr *Instruction : Function.allInstructions()) { + if (Instruction->parent() == nullptr) + continue; + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isRegister()) + continue; + RegisterOperandFlags Flags = Operand->registerFlags(); + const bool HadStaleFlag = + Flags.has(RegisterOperandFlag::Kill) || Flags.has(RegisterOperandFlag::Dead); + if (!HadStaleFlag) + continue; + Flags.clear(RegisterOperandFlag::Kill); + Flags.clear(RegisterOperandFlag::Dead); + auto Updated = Operand->setRegisterFlags(Flags); + if (!Updated) + return std::unexpected(Updated.error()); + Changed = true; + } + } + return Changed; +} + +[[nodiscard]] Expected<SubRegIndex> subRegIndex(const MachineOperand &Operand, + const TargetDescription &Target) { + std::uint64_t Value = 0; + if (const auto *Immediate = Operand.getIf<std::int64_t>(); Immediate != nullptr) { + if (*Immediate <= 0) + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo requires a positive subregister index"); + Value = static_cast<std::uint64_t>(*Immediate); + } else if (const auto *WideImmediate = Operand.getIf<IntegerImmediateOperand>(); + WideImmediate != nullptr) { + if (WideImmediate->Value.isNegative() || WideImmediate->Value.bitWidth() > 64) + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo index does not fit an unsigned integer"); + Value = WideImmediate->Value.words().front(); + } else { + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo is missing its immediate index"); + } + if (Value == 0 || Value > std::numeric_limits<std::uint32_t>::max()) { + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo index is outside the supported range"); + } + const SubRegIndex Result = SubRegIndex::fromValue(static_cast<std::uint32_t>(Value)); + if (Target.registers().subRegIndex(Result) == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo references an unknown target index"); + } + return Result; +} + +[[nodiscard]] Expected<SubRegIndex> composeSubReg(SubRegIndex Outer, SubRegIndex Inner, + const TargetDescription &Target) { + if (Outer.value() == 0) + return Inner; + if (Inner.value() == 0) + return Outer; + const auto Composed = Target.registers().composeSubRegIndices(Outer, Inner); + if (!Composed) { + return makeUnexpected(ErrorCode::Unsupported, + "target cannot compose the requested subregister indices"); + } + return *Composed; +} + +[[nodiscard]] Expected<void> removeInstruction(MachineInstr &Instruction) { + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "rewritten instruction is not linked"); + return Block->removeInstruction(Instruction); +} + +[[nodiscard]] Expected<void> expandRegSequence(MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &Target, + const TargetSSAInfo &TargetInfo) { + if (Instruction.operandCount() < 3 || (Instruction.operandCount() - 1U) % 2U != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "REG_SEQUENCE requires a destination and source/subregister pairs"); + } + MachineOperand *DestinationOperand = Instruction.operandAt(0); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + if (Destination == nullptr || Destination->isNoRegister() || !DestinationOperand->isDef()) { + return makeUnexpected(ErrorCode::VerificationError, + "REG_SEQUENCE requires a register destination definition"); + } + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "REG_SEQUENCE is not linked to a block"); + + RegisterValue DestinationValue{*Destination, DestinationOperand->subReg(), + DestinationOperand->registerFlags(), + DestinationOperand->targetFlags()}; + auto Initial = + buildImplicitDef(Function, Target, *Block, &Instruction, DestinationValue, &Instruction); + if (!Initial) + return std::unexpected(Initial.error()); + + for (std::size_t Index = 1; Index < Instruction.operandCount(); Index += 2U) { + MachineOperand *SourceOperand = Instruction.operandAt(Index); + MachineOperand *IndexOperand = Instruction.operandAt(Index + 1U); + const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>(); + if (Source == nullptr || SourceOperand == nullptr || !SourceOperand->isUse() || + IndexOperand == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "REG_SEQUENCE contains a malformed source/subregister pair"); + } + auto InnerSubReg = subRegIndex(*IndexOperand, Target); + if (!InnerSubReg) + return std::unexpected(InnerSubReg.error()); + auto DestinationSubReg = composeSubReg(DestinationOperand->subReg(), *InnerSubReg, Target); + if (!DestinationSubReg) + return std::unexpected(DestinationSubReg.error()); + + RegisterValue LaneDestination{ + *Destination, *DestinationSubReg, {}, DestinationOperand->targetFlags()}; + if (isImplicitlyUndef(Function, *SourceOperand)) { + auto Undef = + buildImplicitDef(Function, Target, *Block, &Instruction, LaneDestination, &Instruction); + if (!Undef) + return std::unexpected(Undef.error()); + continue; + } + RegisterValue SourceValue{*Source, SourceOperand->subReg(), SourceOperand->registerFlags(), + SourceOperand->targetFlags()}; + auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, LaneDestination, + SourceValue, &Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + } + return removeInstruction(Instruction); +} + +[[nodiscard]] Expected<void> expandInsertSubreg(MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target, + const TargetSSAInfo &TargetInfo) { + if (Instruction.operandCount() != 4) { + return makeUnexpected(ErrorCode::VerificationError, + "INSERT_SUBREG requires destination, base, inserted value, and index"); + } + MachineOperand *DestinationOperand = Instruction.operandAt(0); + MachineOperand *BaseOperand = Instruction.operandAt(1); + MachineOperand *InsertedOperand = Instruction.operandAt(2); + MachineOperand *IndexOperand = Instruction.operandAt(3); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + const Register *Base = BaseOperand == nullptr ? nullptr : BaseOperand->getIf<Register>(); + const Register *Inserted = + InsertedOperand == nullptr ? nullptr : InsertedOperand->getIf<Register>(); + if (Destination == nullptr || Base == nullptr || Inserted == nullptr || + Destination->isNoRegister() || DestinationOperand == nullptr || + !DestinationOperand->isDef() || BaseOperand == nullptr || !BaseOperand->isUse() || + InsertedOperand == nullptr || !InsertedOperand->isUse() || IndexOperand == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "INSERT_SUBREG contains malformed register operands"); + } + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "INSERT_SUBREG is not linked to a block"); + + RegisterValue DestinationValue{*Destination, DestinationOperand->subReg(), + DestinationOperand->registerFlags(), + DestinationOperand->targetFlags()}; + if (isImplicitlyUndef(Function, *BaseOperand)) { + auto Undef = + buildImplicitDef(Function, Target, *Block, &Instruction, DestinationValue, &Instruction); + if (!Undef) + return std::unexpected(Undef.error()); + } else if (*Destination != *Base || DestinationOperand->subReg() != BaseOperand->subReg()) { + RegisterValue BaseValue{*Base, BaseOperand->subReg(), BaseOperand->registerFlags(), + BaseOperand->targetFlags()}; + auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, DestinationValue, + BaseValue, &Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + } + + auto InnerSubReg = subRegIndex(*IndexOperand, Target); + if (!InnerSubReg) + return std::unexpected(InnerSubReg.error()); + auto DestinationSubReg = composeSubReg(DestinationOperand->subReg(), *InnerSubReg, Target); + if (!DestinationSubReg) + return std::unexpected(DestinationSubReg.error()); + RegisterValue LaneDestination{ + *Destination, *DestinationSubReg, {}, DestinationOperand->targetFlags()}; + if (isImplicitlyUndef(Function, *InsertedOperand)) { + auto Undef = + buildImplicitDef(Function, Target, *Block, &Instruction, LaneDestination, &Instruction); + if (!Undef) + return std::unexpected(Undef.error()); + } else { + RegisterValue InsertedValue{*Inserted, InsertedOperand->subReg(), + InsertedOperand->registerFlags(), InsertedOperand->targetFlags()}; + auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, LaneDestination, + InsertedValue, &Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + } + return removeInstruction(Instruction); +} + +[[nodiscard]] Expected<void> swapRegisterUses(MachineOperand &Left, MachineOperand &Right) { + const std::optional<Register> LeftReg = Left.registerValue(); + const std::optional<Register> RightReg = Right.registerValue(); + if (!LeftReg || !RightReg || !Left.isUse() || Left.isDef() || !Right.isUse() || Right.isDef()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "commutation requires two pure register uses"); + } + const SubRegIndex LeftSubReg = Left.subReg(); + const SubRegIndex RightSubReg = Right.subReg(); + const RegisterOperandFlags LeftFlags = Left.registerFlags(); + const RegisterOperandFlags RightFlags = Right.registerFlags(); + const std::uint32_t LeftTargetFlags = Left.targetFlags(); + const std::uint32_t RightTargetFlags = Right.targetFlags(); + + auto SetLeftReg = Left.setRegister(*RightReg); + if (!SetLeftReg) + return std::unexpected(SetLeftReg.error()); + auto SetRightReg = Right.setRegister(*LeftReg); + if (!SetRightReg) + return std::unexpected(SetRightReg.error()); + auto SetLeftSubReg = Left.setSubReg(RightSubReg); + if (!SetLeftSubReg) + return std::unexpected(SetLeftSubReg.error()); + auto SetRightSubReg = Right.setSubReg(LeftSubReg); + if (!SetRightSubReg) + return std::unexpected(SetRightSubReg.error()); + auto SetLeftFlags = Left.setRegisterFlags(RightFlags); + if (!SetLeftFlags) + return std::unexpected(SetLeftFlags.error()); + auto SetRightFlags = Right.setRegisterFlags(LeftFlags); + if (!SetRightFlags) + return std::unexpected(SetRightFlags.error()); + Left.setTargetFlags(RightTargetFlags); + Right.setTargetFlags(LeftTargetFlags); + return {}; +} + +[[nodiscard]] Expected<bool> tryCommute(MachineInstr &Instruction, std::size_t TiedUseIndex, + Register Destination, const TargetDescription &Target, + MachineFunction &Function) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + if (Descriptor == nullptr || !Descriptor->Flags.has(InstructionFlag::Commutable)) + return false; + MachineOperand *TiedUse = Instruction.operandAt(TiedUseIndex); + if (TiedUse == nullptr) + return makeUnexpected(ErrorCode::InternalError, "tied use disappeared during commutation"); + + for (std::size_t Index = 0; Index < Instruction.operandCount(); ++Index) { + if (Index == TiedUseIndex) + continue; + MachineOperand *Candidate = Instruction.operandAt(Index); + if (Candidate == nullptr || Candidate->isImplicit() || !Candidate->isUse() || + Candidate->isDef() || Candidate->tiedOperandIndex() || + Candidate->registerValue() != Destination || isImplicitlyUndef(Function, *Candidate)) { + continue; + } + auto Swapped = swapRegisterUses(*TiedUse, *Candidate); + if (!Swapped) + return std::unexpected(Swapped.error()); + auto Validation = Target.validateInstruction(Instruction, Function.registerInfo()); + if (Validation) + return true; + auto Restored = swapRegisterUses(*TiedUse, *Candidate); + if (!Restored) + return std::unexpected(Restored.error()); + } + return false; +} + +[[nodiscard]] Expected<void> rewriteUndefTie(MachineOperand &Use, const MachineOperand &Def) { + const std::optional<Register> Destination = Def.registerValue(); + if (!Destination) + return makeUnexpected(ErrorCode::VerificationError, "tied definition is not a register"); + auto SetRegister = Use.setRegister(*Destination); + if (!SetRegister) + return std::unexpected(SetRegister.error()); + auto SetSubReg = Use.setSubReg(Def.subReg()); + if (!SetSubReg) + return std::unexpected(SetSubReg.error()); + RegisterOperandFlags Flags = Use.registerFlags(); + Flags.set(RegisterOperandFlag::Undef); + Flags.clear(RegisterOperandFlag::Kill); + return Use.setRegisterFlags(Flags); +} + +[[nodiscard]] Expected<void> verifyNoStageTenPseudos(const MachineFunction &Function, + const TargetDescription &Target) { + for (const MachineInstr *Instruction : Function.allInstructions()) { + if (Instruction->parent() == nullptr) + continue; + if (Instruction->opcode() == opcode(GenericOpcode::G_PHI) || + Instruction->opcode() == opcode(GenericOpcode::PHI) || + Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE) || + Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) { + return makeUnexpected(ErrorCode::VerificationError, + "SSA exit left a Stage 10 pseudo instruction in MachineIR"); + } + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "SSA exit produced an instruction with no descriptor"); + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + const MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isUse()) + continue; + const std::optional<std::size_t> Tie = Operand->tiedOperandIndex(); + if (!Tie) + continue; + const MachineOperand *Def = Instruction->operandAt(Tie.value()); + if (Def == nullptr || Def->registerValue() != Operand->registerValue()) { + return makeUnexpected(ErrorCode::VerificationError, + "two-address rewrite left an unequal tied register"); + } + } + } + return {}; +} + +} // namespace + +const MachinePassContract &PHIEliminationPass::contract() const noexcept { + static const MachinePassContract Contract{ + .Name = "PHIElimination", + .Requires = {MachineFunctionProperty::IsSSA, MachineFunctionProperty::Selected, + MachineFunctionProperty::RegBankSelected}, + .Sets = {MachineFunctionProperty::NoPHIs}, + .Clears = {MachineFunctionProperty::IsSSA}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::SSAEliminated, + }; + return Contract; +} + +Expected<MachinePassResult> PHIEliminationPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + if (Info == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "PHI elimination has no target SSA behavior interface"); + } + auto Required = requireProperties(Function, contract()); + if (!Required) + return std::unexpected(Required.error()); + + auto Trial = cloneMachineFunction( + Function, Target, + MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); + if (!Trial) { + return std::unexpected( + prefixedError(Trial.error(), "PHI-elimination transaction setup failed: ")); + } + MachineAnalysisManager TrialAnalyses; + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses); + if (!TrialResult) + return std::unexpected(TrialResult.error()); + + auto Result = runImplementation(Function, Target, Analyses); + if (!Result) { + return std::unexpected(prefixedError( + Result.error(), "PHI elimination diverged after a successful transaction preflight: ")); + } + return Result; +} + +Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &) { + MachinePassResult Result; + std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> SplitEdges; + const std::vector<MachineBasicBlock *> Blocks(Function.allBlocks().begin(), + Function.allBlocks().end()); + + for (MachineBasicBlock *Block : Blocks) { + auto Plans = collectPhiPlans(*Block, Function, Target); + if (!Plans) + return std::unexpected(Plans.error()); + if (Plans->empty()) + continue; + + for (PhiPlan &Plan : *Plans) { + auto Fresh = cloneRegisterConstraints(Function, Plan.Destination.Reg); + if (!Fresh) + return std::unexpected(Fresh.error()); + Plan.FreshIncoming = *Fresh; + } + + for (PhiPlan &Plan : *Plans) { + for (const PhiIncoming &Incoming : Plan.IncomingValues) { + auto EdgeBlock = placePhiCopiesOnEdge(Function, Target, *Info, *Incoming.Predecessor, + *Block, SplitEdges, Result); + if (!EdgeBlock) + return std::unexpected(EdgeBlock.error()); + if (*EdgeBlock != Incoming.Predecessor) { + const std::optional<PhysicalRegister> Physical = Incoming.Value.Reg.physicalRegister(); + if (Physical) { + auto LiveIn = ensurePhysicalLiveIn(**EdgeBlock, *Physical, Target); + if (!LiveIn) + return std::unexpected(LiveIn.error()); + } + } + MachineInstr *Terminator = firstTerminator(**EdgeBlock, Target); + RegisterValue Fresh{Plan.FreshIncoming, Plan.Destination.SubReg, Plan.Destination.Flags, + Plan.Destination.TargetFlags}; + Expected<MachineInstr *> Transfer = + Incoming.IsUndef ? buildImplicitDef(Function, Target, **EdgeBlock, Terminator, Fresh, + Plan.Instruction) + : buildCopy(Function, Target, *Info, **EdgeBlock, Terminator, Fresh, + Incoming.Value, Plan.Instruction); + if (!Transfer) + return std::unexpected(Transfer.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + } + } + + MachineInstr *InsertionPoint = firstCodeAfterPhiRegion(*Block, Target); + for (PhiPlan &Plan : *Plans) { + RegisterValue Fresh{ + Plan.FreshIncoming, Plan.Destination.SubReg, {}, Plan.Destination.TargetFlags}; + auto Copy = buildCopy(Function, Target, *Info, *Block, InsertionPoint, Plan.Destination, + Fresh, Plan.Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + } + + for (PhiPlan &Plan : *Plans) { + auto Removed = Block->removeInstruction(*Plan.Instruction); + if (!Removed) + return std::unexpected(Removed.error()); + } + Result.Changes.add(MachinePassChange::Registers); + } + + if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) { + auto Cleared = clearStaleLivenessFlags(Function); + if (!Cleared) + return std::unexpected(Cleared.error()); + if (*Cleared) + Result.Changes.add(MachinePassChange::Operands); + } + Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); + return Result; +} + +const MachinePassContract &TwoAddressRewritePass::contract() const noexcept { + static const MachinePassContract Contract{ + .Name = "TwoAddressRewrite", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs}, + .Sets = {MachineFunctionProperty::TiedOpsRewritten}, + .Clears = {MachineFunctionProperty::IsSSA}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::TiedOpsRewritten, + }; + return Contract; +} + +Expected<MachinePassResult> TwoAddressRewritePass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + if (Info == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "two-address rewrite has no target SSA behavior interface"); + } + auto Required = requireProperties(Function, contract()); + if (!Required) + return std::unexpected(Required.error()); + + auto Trial = cloneMachineFunction( + Function, Target, + MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); + if (!Trial) { + return std::unexpected(prefixedError(Trial.error(), "two-address transaction setup failed: ")); + } + MachineAnalysisManager TrialAnalyses; + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses); + if (!TrialResult) + return std::unexpected(TrialResult.error()); + + auto Result = runImplementation(Function, Target, Analyses); + if (!Result) { + return std::unexpected(prefixedError( + Result.error(), "two-address rewrite diverged after a successful transaction preflight: ")); + } + return Result; +} + +Expected<MachinePassResult> +TwoAddressRewritePass::runImplementation(MachineFunction &Function, const TargetDescription &Target, + MachineAnalysisManager &) { + MachinePassResult Result; + const std::vector<MachineInstr *> Instructions(Function.allInstructions().begin(), + Function.allInstructions().end()); + for (MachineInstr *Instruction : Instructions) { + if (Instruction->parent() == nullptr) + continue; + if (Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE)) { + auto Expanded = expandRegSequence(*Instruction, Function, Target, *Info); + if (!Expanded) + return std::unexpected(Expanded.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + continue; + } + if (Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) { + auto Expanded = expandInsertSubreg(*Instruction, Function, Target, *Info); + if (!Expanded) + return std::unexpected(Expanded.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + continue; + } + + std::size_t RewriteAttempts = 0; + bool Restart = true; + while (Restart && Instruction->parent() != nullptr) { + Restart = false; + if (++RewriteAttempts > Instruction->operandCount() * 2U + 8U) { + return makeUnexpected(ErrorCode::InternalError, + "two-address target conversion did not make progress"); + } + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "two-address rewrite encountered an unknown opcode"); + } + + for (std::size_t UseIndex = 0; UseIndex < Instruction->operandCount(); ++UseIndex) { + MachineOperand *Use = Instruction->operandAt(UseIndex); + if (Use == nullptr || !Use->isUse()) + continue; + const std::optional<std::size_t> TiedDefIndex = Use->tiedOperandIndex(); + if (!TiedDefIndex) + continue; + const std::size_t DefIndex = TiedDefIndex.value(); + MachineOperand *Def = Instruction->operandAt(DefIndex); + if (Def == nullptr || !Def->isDef()) { + return makeUnexpected(ErrorCode::VerificationError, + "tied use does not reference a definition"); + } + const std::optional<Register> DefReg = Def->registerValue(); + const std::optional<Register> UseReg = Use->registerValue(); + if (!DefReg || !UseReg || DefReg->isNoRegister()) { + return makeUnexpected(ErrorCode::Unsupported, + "two-address rewrite requires register ties"); + } + if (*DefReg == *UseReg) + continue; + + if (isImplicitlyUndef(Function, *Use)) { + auto Rewritten = rewriteUndefTie(*Use, *Def); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Operands); + continue; + } + + auto Commuted = tryCommute(*Instruction, UseIndex, *DefReg, Target, Function); + if (!Commuted) + return std::unexpected(Commuted.error()); + if (*Commuted) { + Result.Changed = true; + Result.Changes.add(MachinePassChange::Operands); + continue; + } + + auto Converted = + Info->tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target); + if (!Converted) + return std::unexpected(Converted.error()); + if (*Converted) { + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + Result.Changes.add(MachinePassChange::Operands); + Result.Changes.add(MachinePassChange::Registers); + Restart = true; + break; + } + + MachineBasicBlock *Block = Instruction->parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "two-address instruction disappeared before COPY insertion"); + RegisterValue Destination{*DefReg, Def->subReg(), Def->registerFlags(), Def->targetFlags()}; + RegisterValue Source{*UseReg, Use->subReg(), Use->registerFlags(), Use->targetFlags()}; + auto Copy = buildCopy(Function, Target, *Info, *Block, Instruction, Destination, Source, + Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + auto SetRegister = Use->setRegister(*DefReg); + if (!SetRegister) + return std::unexpected(SetRegister.error()); + auto SetSubReg = Use->setSubReg(Def->subReg()); + if (!SetSubReg) + return std::unexpected(SetSubReg.error()); + RegisterOperandFlags Flags = Use->registerFlags(); + Flags.clear(RegisterOperandFlag::Kill); + auto SetFlags = Use->setRegisterFlags(Flags); + if (!SetFlags) + return std::unexpected(SetFlags.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + Result.Changes.add(MachinePassChange::Operands); + } + } + } + + auto FinalState = verifyNoStageTenPseudos(Function, Target); + if (!FinalState) + return std::unexpected(FinalState.error()); + if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) { + auto Cleared = clearStaleLivenessFlags(Function); + if (!Cleared) + return std::unexpected(Cleared.error()); + if (*Cleared) + Result.Changes.add(MachinePassChange::Operands); + } + Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); + return Result; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp index f6f5640..8f4809a 100644 --- a/backend/lib/CodeGen/MachineVerifier.cpp +++ b/backend/lib/CodeGen/MachineVerifier.cpp @@ -2,6 +2,7 @@ #include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/CodeGen/GenericOpcodes.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFrameInfo.h" #include "rcc/CodeGen/MachineFunction.h" @@ -87,6 +88,9 @@ public: auto CFGResult = verifyCFG(); if (!CFGResult) return CFGResult; + auto PHIResult = verifyPHIs(); + if (!PHIResult) + return PHIResult; auto RegisterResult = verifyRegisterInfo(); if (!RegisterResult) return RegisterResult; @@ -428,9 +432,8 @@ private: } [[nodiscard]] Expected<void> verifyFrameLifetimes() const { - auto VerifyPoints = - [this](std::span<const MachineFrameSaveRestorePoint> Points, - std::string_view Kind) -> Expected<void> { + auto VerifyPoints = [this](std::span<const MachineFrameSaveRestorePoint> Points, + std::string_view Kind) -> Expected<void> { for (const MachineFrameSaveRestorePoint &Point : Points) { if (!LinkedBlockIDs.contains(Point.Block)) { return fail(std::string("frame ") + std::string(Kind) + @@ -591,6 +594,8 @@ private: } HasPhi |= Descriptor->Flags.has(InstructionFlag::Phi); + HasStageTenPseudo |= Instruction.opcode() == opcode(GenericOpcode::REG_SEQUENCE) || + Instruction.opcode() == opcode(GenericOpcode::INSERT_SUBREG); HasGenericInstruction |= Descriptor->Flags.has(InstructionFlag::Generic); HasExecutablePseudo |= Descriptor->Flags.has(InstructionFlag::Pseudo) && !Descriptor->Flags.has(InstructionFlag::Meta) && @@ -708,6 +713,75 @@ private: return {}; } + [[nodiscard]] Expected<void> verifyPHIs() { + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + bool SawNonMetaInstruction = false; + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = + Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return fail("PHI verification encountered an unregistered instruction"); + + if (!Descriptor->Flags.has(InstructionFlag::Phi)) { + SawNonMetaInstruction |= !Descriptor->Flags.has(InstructionFlag::Meta); + continue; + } + if (SawNonMetaInstruction) + return fail("PHI instruction appears after a non-meta instruction"); + + const std::span<const MachineOperand> Operands = Instruction->operands(); + if (Operands.size() < 3 || (Operands.size() - 1U) % 2U != 0) { + return fail("PHI must contain a destination and at least one incoming pair"); + } + const Register *Destination = Operands.front().getIf<Register>(); + if (Destination == nullptr || !Destination->isVirtual() || !Operands.front().isDef() || + Operands.front().isUse() || Operands.front().isImplicit()) { + return fail("PHI destination must be an explicit virtual-register definition"); + } + + std::unordered_set<const MachineBasicBlock *> IncomingBlocks; + for (std::size_t Index = 1; Index < Operands.size(); Index += 2U) { + const MachineOperand &ValueOperand = Operands[Index]; + const MachineOperand &BlockOperand = Operands[Index + 1U]; + const Register *Value = ValueOperand.getIf<Register>(); + const BasicBlockOperand *Incoming = BlockOperand.getIf<BasicBlockOperand>(); + if (Value == nullptr || !ValueOperand.isUse() || ValueOperand.isDef() || + ValueOperand.isImplicit() || Incoming == nullptr || Incoming->Block == nullptr || + BlockOperand.isImplicit()) { + return fail("PHI incoming operands must be explicit register/block pairs"); + } + if (std::ranges::find(Block->predecessors(), Incoming->Block) == + Block->predecessors().end()) { + return fail("PHI incoming block is not a CFG predecessor"); + } + if (!IncomingBlocks.insert(Incoming->Block).second) + return fail("PHI contains duplicate incoming blocks"); + + if (!Value->isNoRegister() && Destination->isVirtual() && Value->isVirtual() && + Operands.front().subReg().value() == 0 && ValueOperand.subReg().value() == 0) { + auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(*Destination); + auto ValueInfo = Function.registerInfo().virtualRegisterInfo(*Value); + if (!DestinationInfo || !ValueInfo) + return fail("PHI references an unknown virtual register"); + if (DestinationInfo->get().Type && ValueInfo->get().Type && + DestinationInfo->get().Type != ValueInfo->get().Type) { + return fail("PHI destination and incoming value types do not match"); + } + } + auto Compatibility = Target.validateTieCompatibility(Operands.front(), ValueOperand, + Function.registerInfo()); + if (!Compatibility) + return failWith("PHI register compatibility", Compatibility.error()); + } + if (IncomingBlocks.size() != Block->predecessors().size()) + return fail("PHI incoming blocks do not exactly cover CFG predecessors"); + } + } + return {}; + } + [[nodiscard]] Expected<void> verifyRegisterInfo() { const MachineRegisterInfo &RegInfo = Function.registerInfo(); std::unordered_set<PhysicalRegister> FunctionLiveIns; @@ -767,6 +841,9 @@ private: if (Has(MachineFunctionProperty::TiedOpsRewritten) && !Has(MachineFunctionProperty::Selected)) { return fail("TiedOpsRewritten requires Selected"); } + if (Has(MachineFunctionProperty::TiedOpsRewritten) && !Has(MachineFunctionProperty::NoPHIs)) { + return fail("TiedOpsRewritten requires NoPHIs"); + } if (Has(MachineFunctionProperty::FrameFinalized) && (!Has(MachineFunctionProperty::NoVRegs) || !Has(MachineFunctionProperty::NoFrameIndices))) { return fail("FrameFinalized requires NoVRegs and NoFrameIndices"); @@ -797,6 +874,9 @@ private: if (Has(MachineFunctionProperty::TiedOpsRewritten) && HasUnrewrittenTie) { return fail("TiedOpsRewritten function has unequal tied registers"); } + if (Has(MachineFunctionProperty::TiedOpsRewritten) && HasStageTenPseudo) { + return fail("TiedOpsRewritten function contains a Stage 10 pseudo"); + } const bool NeedsTypes = Options.Mode == MachineVerifierMode::PreLegalizer || Has(MachineFunctionProperty::Legalized) || @@ -837,6 +917,7 @@ private: bool HasExecutablePseudo = false; bool HasFrameIndex = false; bool HasUnrewrittenTie = false; + bool HasStageTenPseudo = false; bool HasLiveVirtualRegister = false; bool MissingVirtualType = false; bool MissingVirtualBank = false; diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp index e2bbe8a..e8c7d79 100644 --- a/backend/lib/CodeGen/TargetDescription.cpp +++ b/backend/lib/CodeGen/TargetDescription.cpp @@ -58,7 +58,13 @@ Expected<TargetDescription> TargetDescription::create(InstructionSet Instruction for (const InstructionDescriptor &Instruction : Instructions.descriptors()) { for (const OperandDescriptor &Operand : Instruction.Operands) { - if ((Operand.AllowedTargetFlags & ~MIRText->serializableOperandFlagMask()) != 0) { + if (Operand.AllowAnyTargetFlags && Operand.AllowedTargetFlags != 0) { + return makeUnexpected( + ErrorCode::InvalidArgument, + "instruction operand cannot combine unrestricted and explicit target flags"); + } + if (!Operand.AllowAnyTargetFlags && + (Operand.AllowedTargetFlags & ~MIRText->serializableOperandFlagMask()) != 0) { return makeUnexpected( ErrorCode::InvalidArgument, "instruction operand allows a target flag outside the MIR text schema"); diff --git a/backend/lib/Target/RISCV/RISCVCodeGen.cpp b/backend/lib/Target/RISCV/RISCVCodeGen.cpp index 631ac33..642982a 100644 --- a/backend/lib/Target/RISCV/RISCVCodeGen.cpp +++ b/backend/lib/Target/RISCV/RISCVCodeGen.cpp @@ -4,6 +4,7 @@ #include "rcc/CodeGen/GenericOpcodes.h" #include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" @@ -13,6 +14,7 @@ #include "rcc/CodeGen/TargetDescription.h" #include "rcc/Target/RISCV/RISCVTarget.h" +#include <algorithm> #include <array> #include <bit> #include <cstdint> @@ -3219,6 +3221,198 @@ private: } }; +class RISCVSSAInfo final : public TargetSSAInfo { +public: + [[nodiscard]] Expected<bool> isFallthroughEdge(const MachineBasicBlock &From, + const MachineBasicBlock &To, + const MachineFunction &, + const TargetDescription &Target) const override { + 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)) + continue; + CanFallThrough = isConditionalBranch(Instruction->opcode()); + } + return CanFallThrough; + } + + [[nodiscard]] Expected<bool> rewriteBranchTarget(MachineBasicBlock &Block, + MachineBasicBlock &OldTarget, + MachineBasicBlock &NewTarget, + MachineFunction &Function, + const TargetDescription &Target) const override { + if (&Block.function() != &Function || &OldTarget.function() != &Function || + &NewTarget.function() != &Function) { + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V branch rewrite references another machine function"); + } + + bool Changed = false; + 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 rewrite encountered an unknown opcode"); + } + if (!Descriptor->Flags.has(InstructionFlag::Branch) || + Descriptor->Flags.has(InstructionFlag::IndirectBranch)) { + continue; + } + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + MachineOperand *Operand = Instruction->operandAt(Index); + const BasicBlockOperand *TargetOperand = + Operand == nullptr ? nullptr : Operand->getIf<BasicBlockOperand>(); + if (TargetOperand == nullptr || TargetOperand->Block != &OldTarget) + continue; + auto Rewritten = Operand->setBasicBlock(NewTarget); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + Changed = true; + } + } + return Changed; + } + + [[nodiscard]] Expected<void> + insertUnconditionalBranch(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 machine function"); + } + auto Zero = physicalRegister(PhysicalRegisterID::X0); + if (!Zero) + return std::unexpected(Zero.error()); + MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Branch = Builder.buildInstr(targetOpcode(InstructionOpcode::JAL)); + if (!Branch) + return std::unexpected(Branch.error()); + auto Link = Branch->addDef(Register::fromPhysical(*Zero)); + if (!Link) + return std::unexpected(Link.error()); + auto Destination = Branch->addBasicBlock(TargetBlock); + if (!Destination) + return std::unexpected(Destination.error()); + auto Built = Branch->build(); + if (!Built) + return std::unexpected(Built.error()); + return {}; + } + + [[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"); + } + 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 {}; + } + +private: + struct CopyShape final { + RegisterBankID Bank; + std::optional<std::uint32_t> Width; + }; + + [[nodiscard]] static bool isConditionalBranch(Opcode Value) noexcept { + return Value == targetOpcode(InstructionOpcode::BEQ) || + Value == targetOpcode(InstructionOpcode::BNE) || + Value == targetOpcode(InstructionOpcode::BLT) || + Value == targetOpcode(InstructionOpcode::BGE) || + Value == targetOpcode(InstructionOpcode::BLTU) || + Value == targetOpcode(InstructionOpcode::BGEU); + } + + [[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.value()); + if (Class == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V COPY references an unknown register class"); + } + return CopyShape{Bank.value(), 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 TargetLegalizerInfo &legalizerInfo() noexcept { @@ -3236,4 +3430,9 @@ const TargetInstructionSelector &instructionSelector() noexcept { return Value; } +const TargetSSAInfo &ssaInfo() noexcept { + static const RISCVSSAInfo Value; + return Value; +} + } // namespace rcc::riscv diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt index 19beb2f..c8ea9b8 100644 --- a/backend/unittests/CodeGen/CMakeLists.txt +++ b/backend/unittests/CodeGen/CMakeLists.txt @@ -21,6 +21,7 @@ set( MachineOperandTest.cpp MachinePassTest.cpp MachinePipelinePassesTest.cpp + MachineSSAExitTest.cpp MachineVerifierTest.cpp MachineVerifierTargetTest.cpp MachineValueTypesTest.cpp @@ -273,6 +274,14 @@ target_link_libraries( add_test(NAME RCCBackend.CodeGen.MachineAnalyses COMMAND RCCBackendCodeGenMachineAnalysesTests) +add_executable(RCCBackendCodeGenMachineSSAExitTests MachineSSAExitTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenMachineSSAExitTests) +target_link_libraries( + RCCBackendCodeGenMachineSSAExitTests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget +) +add_test(NAME RCCBackend.CodeGen.MachineSSAExit COMMAND RCCBackendCodeGenMachineSSAExitTests) + add_executable(RCCBackendCodeGenTargetConstantTests TargetConstantTest.cpp) rcc_backend_configure_target(RCCBackendCodeGenTargetConstantTests) target_link_libraries(RCCBackendCodeGenTargetConstantTests PRIVATE RCCBackend::CodeGen) @@ -350,6 +359,7 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTargetTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp" @@ -379,6 +389,7 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTargetTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp" diff --git a/backend/unittests/CodeGen/MachineAnalysesTest.cpp b/backend/unittests/CodeGen/MachineAnalysesTest.cpp index 23c5e19..1c9f255 100644 --- a/backend/unittests/CodeGen/MachineAnalysesTest.cpp +++ b/backend/unittests/CodeGen/MachineAnalysesTest.cpp @@ -458,6 +458,108 @@ void testCFGUpdaterPHIs(TestContext &Context, const rcc::TargetDescription &Targ "CFG block deletion must detach a disconnected block cleanly"); } +void testCFGUpdaterFailureAtomicity(TestContext &Context, const rcc::TargetDescription &Target) { + auto SplitFunction = + rcc::MachineFunction::create("cfg_split_atomic", rcc::MachineFunctionStableID::fromValue(5)); + if (!SplitFunction) { + Context.expect(false, "CFG split atomicity function creation must succeed"); + return; + } + auto Source = appendBlock(**SplitFunction); + auto Merge = appendBlock(**SplitFunction); + if (!Source || !Merge) + return; + auto SplitUpdater = (*SplitFunction)->cfgUpdater(); + if (!SplitUpdater.addSuccessor(**Source, **Merge, rcc::BranchProbability::one())) + return; + + auto I64 = rcc::LLT::makeInteger(64); + auto Destination = I64 ? (*SplitFunction)->registerInfo().createVirtualRegister(*I64) + : rcc::Expected<rcc::Register>{std::unexpected(I64.error())}; + auto Value = I64 ? (*SplitFunction)->registerInfo().createVirtualRegister(*I64) + : rcc::Expected<rcc::Register>{std::unexpected(I64.error())}; + if (!Destination || !Value) + return; + + rcc::MachineIRBuilder Builder(**SplitFunction, Target); + if (!Builder.setInsertPoint(**Source)) + return; + auto Branch = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_BR)); + auto BranchInstruction = + Branch && Branch->addBasicBlock(**Merge) + ? Branch->build() + : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected( + rcc::ErrorCode::InternalError, "failed to build CFG split branch")}; + if (!BranchInstruction || !Builder.setInsertPoint(**Merge)) + return; + auto Phi = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_PHI)); + auto PhiInstruction = + Phi && Phi->addDef(*Destination) && Phi->addUse(*Value) && Phi->addBasicBlock(**Source) + ? Phi->build() + : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected( + rcc::ErrorCode::InternalError, "failed to build CFG split PHI")}; + if (!PhiInstruction || !(*PhiInstruction)->eraseOperand(2)) + return; + + const std::size_t LinkedBlocksBefore = (*SplitFunction)->blockCount(); + const std::size_t AllocatedBlocksBefore = (*SplitFunction)->allBlocks().size(); + auto FailedSplit = SplitUpdater.splitBlock(**Source, **BranchInstruction); + Context.expect( + !FailedSplit && (*SplitFunction)->blockCount() == LinkedBlocksBefore && + (*SplitFunction)->allBlocks().size() == AllocatedBlocksBefore && + (*BranchInstruction)->parent() == *Source && (*Source)->successors().size() == 1 && + (*Source)->successors().front().Block == *Merge && (*Merge)->predecessors().size() == 1 && + (*Merge)->predecessors().front() == *Source, + "failed block split must not mutate layout, instructions, or CFG edges"); + + auto FailedDelete = SplitUpdater.deleteBlock(**Source); + Context.expect(!FailedDelete && (*Source)->isLinked() && + (*SplitFunction)->blockCount() == LinkedBlocksBefore && + (*Source)->successors().size() == 1 && (*Merge)->predecessors().size() == 1, + "failed block deletion must not partially disconnect CFG edges"); + + auto TransferFunction = rcc::MachineFunction::create("cfg_transfer_atomic", + rcc::MachineFunctionStableID::fromValue(6)); + if (!TransferFunction) + return; + auto From = appendBlock(**TransferFunction); + auto To = appendBlock(**TransferFunction); + auto Successor = appendBlock(**TransferFunction); + if (!From || !To || !Successor) + return; + auto TransferUpdater = (*TransferFunction)->cfgUpdater(); + if (!TransferUpdater.addSuccessor(**From, **Successor, rcc::BranchProbability::one()) || + !TransferUpdater.addSuccessor(**To, **Successor, rcc::BranchProbability::one())) { + return; + } + auto TransferDestination = I64 ? (*TransferFunction)->registerInfo().createVirtualRegister(*I64) + : rcc::Expected<rcc::Register>{std::unexpected(I64.error())}; + auto TransferValue = I64 ? (*TransferFunction)->registerInfo().createVirtualRegister(*I64) + : rcc::Expected<rcc::Register>{std::unexpected(I64.error())}; + if (!TransferDestination || !TransferValue) + return; + rcc::MachineIRBuilder TransferBuilder(**TransferFunction, Target); + if (!TransferBuilder.setInsertPoint(**Successor)) + return; + auto TransferPhi = TransferBuilder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_PHI)); + auto TransferPhiInstruction = + TransferPhi && TransferPhi->addDef(*TransferDestination) && + TransferPhi->addUse(*TransferValue) && TransferPhi->addBasicBlock(**From) + ? TransferPhi->build() + : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected( + rcc::ErrorCode::InternalError, "failed to build CFG transfer PHI")}; + if (!TransferPhiInstruction) + return; + + auto FailedTransfer = TransferUpdater.transferSuccessors(**From, **To); + Context.expect( + !FailedTransfer && (*From)->successors().size() == 1 && (*To)->successors().size() == 1 && + (*Successor)->predecessors().size() == 2 && + (*TransferPhiInstruction)->operandCount() == 3 && + (*TransferPhiInstruction)->operandAt(2)->getIf<rcc::BasicBlockOperand>()->Block == *From, + "failed successor transfer must preserve both CFG edges and PHI operands"); +} + } // namespace int main() { @@ -472,6 +574,7 @@ int main() { testAliasAnalysis(Context); testMemoryDependence(Context, *Target); testCFGUpdaterPHIs(Context, *Target); + testCFGUpdaterFailureAtomicity(Context, *Target); testAtomicStandardRegistration(Context); return Context.result(); } diff --git a/backend/unittests/CodeGen/MachineSSAExitTest.cpp b/backend/unittests/CodeGen/MachineSSAExitTest.cpp new file mode 100644 index 0000000..7c65345 --- /dev/null +++ b/backend/unittests/CodeGen/MachineSSAExitTest.cpp @@ -0,0 +1,1113 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineSSAExit.h" + +#include "Target/TestTarget.h" +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <algorithm> +#include <array> +#include <cstddef> +#include <cstdint> +#include <iostream> +#include <memory> +#include <optional> +#include <span> +#include <string> +#include <string_view> +#include <utility> +#include <vector> + +namespace { + +constexpr std::uint32_t DefOpcode = 1024; +constexpr std::uint32_t UseOpcode = 1025; +constexpr std::uint32_t ConditionalBranchOpcode = 1026; +constexpr std::uint32_t JumpOpcode = 1027; +constexpr std::uint32_t ReturnOpcode = 1028; +constexpr std::uint32_t MetaOpcode = 1029; +constexpr std::uint32_t TiedOpcode = 1030; +constexpr std::uint32_t CommutableTiedOpcode = 1031; +constexpr std::uint32_t ConvertibleTiedOpcode = 1032; +constexpr std::uint32_t ThreeAddressOpcode = 1033; + +class TestContext final { +public: + void expect(bool Condition, std::string_view Message) { + if (Condition) + return; + std::cerr << Message << '\n'; + ++Failures; + } + + [[nodiscard]] int result() const noexcept { + return Failures == 0 ? 0 : 1; + } + +private: + int Failures = 0; +}; + +[[nodiscard]] rcc::Opcode testOpcode(std::uint32_t Value) { + return rcc::Opcode::fromValue(Value); +} + +[[nodiscard]] rcc::OperandDescriptor registerOperand(rcc::RegisterOperandRole Role, + bool AllowSubReg = true) { + rcc::OperandDescriptor Result; + Result.Kinds = {rcc::MachineOperand::Kind::Register}; + Result.RegisterRole = Role; + Result.AllowSubReg = AllowSubReg; + Result.AllowAnyTargetFlags = true; + return Result; +} + +[[nodiscard]] rcc::OperandDescriptor blockOperand() { + rcc::OperandDescriptor Result; + Result.Kinds = {rcc::MachineOperand::Kind::BasicBlock}; + return Result; +} + +[[nodiscard]] rcc::InstructionDescriptor instruction(std::uint32_t Value, std::string Name) { + rcc::InstructionDescriptor Result; + Result.InstructionOpcode = testOpcode(Value); + Result.Name = std::move(Name); + Result.Flags = {rcc::InstructionFlag::ProducesCode}; + return Result; +} + +[[nodiscard]] rcc::Expected<rcc::TargetDescription> createTarget() { + std::vector<rcc::InstructionDescriptor> Descriptors; + std::vector<rcc::ImmediatePredicate> Predicates; + auto Generic = rcc::appendGenericInstructionInfo(Descriptors, Predicates); + if (!Generic) + return std::unexpected(Generic.error()); + + auto Def = instruction(DefOpcode, "TEST_DEF"); + Def.Operands = {registerOperand(rcc::RegisterOperandRole::Def)}; + Def.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Def)); + + auto Use = instruction(UseOpcode, "TEST_USE"); + Use.Operands = {registerOperand(rcc::RegisterOperandRole::Use)}; + Descriptors.push_back(std::move(Use)); + + auto Conditional = instruction(ConditionalBranchOpcode, "TEST_BRCOND"); + Conditional.Operands = {registerOperand(rcc::RegisterOperandRole::Use, false), blockOperand()}; + Conditional.Flags.set(rcc::InstructionFlag::Branch); + Conditional.Flags.set(rcc::InstructionFlag::Terminator); + Descriptors.push_back(std::move(Conditional)); + + auto Jump = instruction(JumpOpcode, "TEST_JUMP"); + Jump.Operands = {blockOperand()}; + Jump.Flags.set(rcc::InstructionFlag::Branch); + Jump.Flags.set(rcc::InstructionFlag::Terminator); + Jump.Flags.set(rcc::InstructionFlag::Barrier); + Descriptors.push_back(std::move(Jump)); + + auto Return = instruction(ReturnOpcode, "TEST_RETURN"); + Return.Flags.set(rcc::InstructionFlag::Return); + Return.Flags.set(rcc::InstructionFlag::Terminator); + Return.Flags.set(rcc::InstructionFlag::Barrier); + Descriptors.push_back(std::move(Return)); + + auto Meta = instruction(MetaOpcode, "TEST_META"); + Meta.Flags = {rcc::InstructionFlag::Pseudo, rcc::InstructionFlag::Meta}; + Descriptors.push_back(std::move(Meta)); + + auto Tied = instruction(TiedOpcode, "TEST_TIED"); + auto TiedDef = registerOperand(rcc::RegisterOperandRole::Def); + auto TiedUse = registerOperand(rcc::RegisterOperandRole::Use); + TiedDef.DefaultTiedOperand = 1; + TiedUse.DefaultTiedOperand = 0; + Tied.Operands = {TiedDef, TiedUse}; + Tied.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Tied)); + + auto Commutable = instruction(CommutableTiedOpcode, "TEST_COMMUTABLE_TIED"); + Commutable.Operands = {TiedDef, TiedUse, registerOperand(rcc::RegisterOperandRole::Use)}; + Commutable.NumExplicitDefs = 1; + Commutable.Flags.set(rcc::InstructionFlag::Commutable); + Descriptors.push_back(std::move(Commutable)); + + auto Convertible = instruction(ConvertibleTiedOpcode, "TEST_CONVERTIBLE_TIED"); + Convertible.Operands = {TiedDef, TiedUse}; + Convertible.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Convertible)); + + auto ThreeAddress = instruction(ThreeAddressOpcode, "TEST_THREE_ADDRESS"); + ThreeAddress.Operands = {registerOperand(rcc::RegisterOperandRole::Def), + registerOperand(rcc::RegisterOperandRole::Use)}; + ThreeAddress.NumExplicitDefs = 1; + Descriptors.push_back(std::move(ThreeAddress)); + + auto Instructions = rcc::InstructionSet::create(std::move(Descriptors), std::move(Predicates)); + if (!Instructions) + return std::unexpected(Instructions.error()); + return rcc::test::createTestTargetDescription(std::move(*Instructions)); +} + +class TestSSAInfo final : public rcc::TargetSSAInfo { +public: + explicit TestSSAInfo(bool RejectCopies = false) : RejectCopies(RejectCopies) {} + + [[nodiscard]] rcc::Expected<bool> + isFallthroughEdge(const rcc::MachineBasicBlock &From, const rcc::MachineBasicBlock &To, + const rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) const override { + if (&From.function() != &Function || &To.function() != &Function) { + return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument, + "fallthrough query references another function"); + } + if (From.next() != &To || + std::ranges::none_of(From.successors(), [&To](const rcc::MachineSuccessor &Successor) { + return Successor.Block == &To; + })) { + return false; + } + + bool CanFallThrough = true; + for (const rcc::MachineInstr *Instruction = From.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const rcc::InstructionDescriptor *Descriptor = + Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return rcc::makeUnexpected(rcc::ErrorCode::VerificationError, + "fallthrough query encountered an unknown opcode"); + } + if (Descriptor->Flags.has(rcc::InstructionFlag::Terminator)) + CanFallThrough = Instruction->opcode() == testOpcode(ConditionalBranchOpcode); + } + return CanFallThrough; + } + + [[nodiscard]] rcc::Expected<bool> + rewriteBranchTarget(rcc::MachineBasicBlock &Block, rcc::MachineBasicBlock &OldTarget, + rcc::MachineBasicBlock &NewTarget, rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) const override { + if (&Block.function() != &Function || &OldTarget.function() != &Function || + &NewTarget.function() != &Function) { + return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument, + "branch rewrite references another function"); + } + bool Changed = false; + for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const rcc::InstructionDescriptor *Descriptor = + Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return rcc::makeUnexpected(rcc::ErrorCode::VerificationError, "unknown branch opcode"); + if (!Descriptor->Flags.has(rcc::InstructionFlag::Branch)) + continue; + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + rcc::MachineOperand *Operand = Instruction->operandAt(Index); + const auto *BlockOperand = + Operand == nullptr ? nullptr : Operand->getIf<rcc::BasicBlockOperand>(); + if (BlockOperand == nullptr || BlockOperand->Block != &OldTarget) + continue; + auto Rewritten = Operand->setBasicBlock(NewTarget); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + Changed = true; + } + } + return Changed; + } + + [[nodiscard]] rcc::Expected<void> + insertUnconditionalBranch(rcc::MachineBasicBlock &Block, rcc::MachineBasicBlock &TargetBlock, + rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) const override { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(testOpcode(JumpOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Destination = Pending->addBasicBlock(TargetBlock); + if (!Destination) + return std::unexpected(Destination.error()); + auto Built = Pending->build(); + if (!Built) + return std::unexpected(Built.error()); + return {}; + } + + [[nodiscard]] rcc::Expected<void> + validateCopy(rcc::Register Destination, rcc::SubRegIndex DestinationSubReg, rcc::Register Source, + rcc::SubRegIndex SourceSubReg, const rcc::MachineFunction &Function, + const rcc::TargetDescription &Target) const override { + if (RejectCopies) { + return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, + "test target intentionally rejects COPY"); + } + if (Destination.isNoRegister() || Source.isNoRegister()) { + return rcc::makeUnexpected(rcc::ErrorCode::VerificationError, + "COPY requires nonzero registers"); + } + if ((Destination.isPhysical() && DestinationSubReg.value() != 0) || + (Source.isPhysical() && SourceSubReg.value() != 0)) { + return rcc::makeUnexpected(rcc::ErrorCode::VerificationError, + "physical COPY operands cannot carry subregisters"); + } + auto Def = rcc::MachineOperand::registerOperand(Destination, {rcc::RegisterOperandFlag::Define}, + DestinationSubReg); + auto Use = + rcc::MachineOperand::registerOperand(Source, {rcc::RegisterOperandFlag::Use}, SourceSubReg); + if (!Def || !Use) + return rcc::makeUnexpected(rcc::ErrorCode::InternalError, "failed to model COPY operands"); + return Target.validateTieCompatibility(*Def, *Use, Function.registerInfo()); + } + + [[nodiscard]] rcc::Expected<bool> + tryConvertToThreeAddress(rcc::MachineInstr &Instruction, std::size_t DefIndex, + std::size_t UseIndex, rcc::MachineFunction &, + const rcc::TargetDescription &) const override { + if (Instruction.opcode() != testOpcode(ConvertibleTiedOpcode)) + return false; + if (DefIndex != 0 || UseIndex != 1) + return rcc::makeUnexpected(rcc::ErrorCode::VerificationError, + "unexpected convertible tie indices"); + auto Untied = Instruction.untieOperand(DefIndex); + if (!Untied) + return std::unexpected(Untied.error()); + auto Opcode = Instruction.setOpcode(testOpcode(ThreeAddressOpcode)); + if (!Opcode) + return std::unexpected(Opcode.error()); + return true; + } + +private: + bool RejectCopies = false; +}; + +struct FunctionFixture final { + std::unique_ptr<rcc::MachineFunction> Function; + std::vector<rcc::MachineBasicBlock *> Blocks; +}; + +[[nodiscard]] FunctionFixture createFunction(TestContext &Context, std::string Name, + std::uint64_t ID, std::size_t BlockCount) { + auto Function = + rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID)); + Context.expect(Function.has_value(), "SSA-exit function creation must succeed"); + if (!Function) + return {}; + + FunctionFixture Result{std::move(*Function), {}}; + for (std::size_t Index = 0; Index < BlockCount; ++Index) { + auto Block = Result.Function->createBasicBlock(); + Context.expect(Block && Result.Function->appendBlock(**Block).has_value(), + "SSA-exit block creation must succeed"); + if (!Block) + return {}; + Result.Blocks.push_back(*Block); + } + return Result; +} + +[[nodiscard]] rcc::Expected<rcc::Register> +createVReg(rcc::MachineFunction &Function, rcc::LLT Type, rcc::RegisterBankID Bank, + rcc::RegisterClassID Class, std::uint8_t TargetFlags = 0, + std::optional<rcc::PhysicalRegister> Hint = std::nullopt) { + auto Reg = Function.registerInfo().createVirtualRegister(Type); + if (!Reg) + return std::unexpected(Reg.error()); + auto BankResult = Function.registerInfo().setRegisterBank(*Reg, Bank); + if (!BankResult) + return std::unexpected(BankResult.error()); + auto ClassResult = Function.registerInfo().setRegisterClass(*Reg, Class); + if (!ClassResult) + return std::unexpected(ClassResult.error()); + if (TargetFlags != 0) { + auto FlagsResult = Function.registerInfo().setTargetRegisterFlags(*Reg, TargetFlags); + if (!FlagsResult) + return std::unexpected(FlagsResult.error()); + } + if (Hint) { + auto HintResult = Function.registerInfo().addAllocationHint(*Reg, *Hint); + if (!HintResult) + return std::unexpected(HintResult.error()); + } + return *Reg; +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildRegisterInstruction(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Opcode Opcode, + std::span<const rcc::Register> Defs, std::span<const rcc::Register> Uses, + rcc::RegisterOperandFlags DefFlags = {}, + rcc::RegisterOperandFlags UseFlags = {}) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(Opcode); + if (!Pending) + return std::unexpected(Pending.error()); + for (rcc::Register Reg : Defs) { + auto Added = Pending->addDef(Reg, DefFlags); + if (!Added) + return std::unexpected(Added.error()); + } + for (rcc::Register Reg : Uses) { + auto Added = Pending->addUse(Reg, UseFlags); + if (!Added) + return std::unexpected(Added.error()); + } + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> buildJump(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, + rcc::MachineBasicBlock &Destination) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(testOpcode(JumpOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + auto TargetOperand = Pending->addBasicBlock(Destination); + if (!TargetOperand) + return std::unexpected(TargetOperand.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Destination, + std::span<const std::pair<rcc::Register, rcc::MachineBasicBlock *>> Incoming, + rcc::RegisterOperandFlags DestinationFlags = {}, std::uint32_t DestinationTargetFlags = 0, + rcc::RegisterOperandFlags IncomingFlags = {}, std::uint32_t IncomingTargetFlags = 0) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Destination, DestinationFlags, {}, DestinationTargetFlags); + if (!Def) + return std::unexpected(Def.error()); + for (const auto &[Value, Predecessor] : Incoming) { + auto Use = Pending->addUse(Value, IncomingFlags, {}, IncomingTargetFlags); + if (!Use) + return std::unexpected(Use.error()); + auto IncomingBlock = Pending->addBasicBlock(*Predecessor); + if (!IncomingBlock) + return std::unexpected(IncomingBlock.error()); + } + return Pending->build(); +} + +void setSelectedSSAProperties(rcc::MachineFunction &Function) { + for (rcc::MachineFunctionProperty Property : + {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness, + rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected, + rcc::MachineFunctionProperty::Selected}) { + Function.properties().set(Property); + } +} + +[[nodiscard]] rcc::Expected<void> runPHIElimination(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + const rcc::TargetSSAInfo &Info) { + rcc::MachinePassManager Pipeline; + auto Added = Pipeline.addPass(std::make_unique<rcc::PHIEliminationPass>(Info)); + if (!Added) + return std::unexpected(Added.error()); + rcc::MachineAnalysisManager Analyses; + return Pipeline.run(Function, Target, Analyses); +} + +[[nodiscard]] std::vector<rcc::MachineInstr *> linkedInstructions(rcc::MachineBasicBlock &Block) { + std::vector<rcc::MachineInstr *> Result; + for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Result.push_back(Instruction); + } + return Result; +} + +[[nodiscard]] std::vector<rcc::MachineInstr *> +instructionsWithOpcode(rcc::MachineFunction &Function, rcc::Opcode Opcode) { + std::vector<rcc::MachineInstr *> Result; + for (rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (Instruction->opcode() == Opcode) + Result.push_back(Instruction); + } + } + return Result; +} + +[[nodiscard]] bool hasLiveIn(const rcc::MachineBasicBlock &Block, rcc::PhysicalRegister Reg) { + return std::ranges::any_of(Block.liveIns(), [Reg](const rcc::MachineBasicBlockLiveIn &LiveIn) { + return LiveIn.PhysReg == Reg; + }); +} + +void testParallelPHIsAndPlacement(TestContext &Context, const rcc::TargetDescription &Target, + const TestSSAInfo &Info) { + auto Fixture = createFunction(Context, "parallel_phis", 1, 3); + if (!Fixture.Function || Fixture.Blocks.size() != 3) + return; + auto I64 = rcc::LLT::makeInteger(64); + if (!I64) + return; + auto &Function = *Fixture.Function; + rcc::MachineBasicBlock &Preheader = *Fixture.Blocks[0]; + rcc::MachineBasicBlock &Header = *Fixture.Blocks[1]; + rcc::MachineBasicBlock &Backedge = *Fixture.Blocks[2]; + const rcc::PhysicalRegister Hint = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G1); + + auto InitA = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + auto InitB = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + auto DestinationA = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64, 0x1, Hint); + auto DestinationB = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + Context.expect(InitA && InitB && DestinationA && DestinationB, + "parallel PHI registers must be created"); + if (!InitA || !InitB || !DestinationA || !DestinationB) + return; + + auto CFG = Function.cfgUpdater(); + Context.expect( + CFG.addSuccessor(Preheader, Header, rcc::BranchProbability::one()).has_value() && + CFG.addSuccessor(Header, Backedge, rcc::BranchProbability::one()).has_value() && + CFG.addSuccessor(Backedge, Header, rcc::BranchProbability::one()).has_value(), + "parallel PHI loop CFG must be connected"); + + const std::array InitADef{*InitA}; + const std::array InitBDef{*InitB}; + Context.expect(buildRegisterInstruction(Function, Target, Preheader, testOpcode(DefOpcode), + InitADef, {}, {rcc::RegisterOperandFlag::Dead}) && + buildRegisterInstruction(Function, Target, Preheader, testOpcode(DefOpcode), + InitBDef, {}) && + buildJump(Function, Target, Preheader, Header), + "parallel PHI preheader must be populated"); + + const std::array IncomingA{ + std::pair<rcc::Register, rcc::MachineBasicBlock *>{*InitA, &Preheader}, + std::pair<rcc::Register, rcc::MachineBasicBlock *>{*DestinationB, &Backedge}}; + const std::array IncomingB{ + std::pair<rcc::Register, rcc::MachineBasicBlock *>{*InitB, &Preheader}, + std::pair<rcc::Register, rcc::MachineBasicBlock *>{*DestinationA, &Backedge}}; + Context.expect(buildPhi(Function, Target, Header, *DestinationA, IncomingA, {}, 0x4, {}, 0x8) && + buildPhi(Function, Target, Header, *DestinationB, IncomingB), + "parallel PHIs must be built"); + + rcc::MachineIRBuilder HeaderBuilder(Function, Target); + if (!HeaderBuilder.setInsertPoint(Header)) + return; + auto Meta = HeaderBuilder.buildInstr(testOpcode(MetaOpcode)); + const std::array HeaderUse{*DestinationA}; + Context.expect(Meta && Meta->build() && + buildRegisterInstruction(Function, Target, Header, testOpcode(UseOpcode), {}, + HeaderUse) && + buildJump(Function, Target, Header, Backedge), + "parallel PHI header must contain meta, code, and terminator instructions"); + + const std::array KilledUse{*DestinationA}; + Context.expect(buildRegisterInstruction(Function, Target, Backedge, testOpcode(UseOpcode), {}, + KilledUse, {}, {rcc::RegisterOperandFlag::Kill}) && + buildJump(Function, Target, Backedge, Header), + "parallel PHI backedge must be populated"); + setSelectedSSAProperties(Function); + + auto Run = runPHIElimination(Function, Target, Info); + Context.expect(Run.has_value(), "parallel PHI elimination must succeed"); + if (!Run) + return; + Context.expect(!Function.properties().has(rcc::MachineFunctionProperty::IsSSA) && + Function.properties().has(rcc::MachineFunctionProperty::NoPHIs) && + Function.properties().has(rcc::MachineFunctionProperty::TracksLiveness), + "PHI elimination must publish its exact property transition"); + Context.expect(instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::PHI)).empty(), + "PHI elimination must remove every PHI"); + + const auto HeaderInstructions = linkedInstructions(Header); + Context.expect(HeaderInstructions.size() == 5 && + HeaderInstructions[0]->opcode() == testOpcode(MetaOpcode) && + HeaderInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) && + HeaderInstructions[2]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) && + HeaderInstructions[3]->opcode() == testOpcode(UseOpcode) && + HeaderInstructions[4]->opcode() == testOpcode(JumpOpcode), + "destination COPYs must follow the full leading PHI/meta region"); + if (HeaderInstructions.size() < 3) + return; + + const rcc::Register *FreshA = HeaderInstructions[1]->operandAt(1)->getIf<rcc::Register>(); + const rcc::Register *FreshB = HeaderInstructions[2]->operandAt(1)->getIf<rcc::Register>(); + Context.expect(FreshA != nullptr && FreshB != nullptr && *FreshA != *FreshB && + *FreshA != *DestinationA && *FreshB != *DestinationB, + "each PHI must receive an independent fresh incoming vreg"); + if (FreshA == nullptr || FreshB == nullptr) + return; + + const auto BackedgeInstructions = linkedInstructions(Backedge); + Context.expect(BackedgeInstructions.size() == 4 && + BackedgeInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) && + BackedgeInstructions[2]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) && + BackedgeInstructions[3]->opcode() == testOpcode(JumpOpcode), + "incoming COPYs must be placed together before the first terminator"); + if (BackedgeInstructions.size() >= 3) { + const auto FirstDef = BackedgeInstructions[1]->operandAt(0)->registerValue(); + const auto FirstUse = BackedgeInstructions[1]->operandAt(1)->registerValue(); + const auto SecondDef = BackedgeInstructions[2]->operandAt(0)->registerValue(); + const auto SecondUse = BackedgeInstructions[2]->operandAt(1)->registerValue(); + Context.expect(FirstDef == *FreshA && FirstUse == *DestinationB && SecondDef == *FreshB && + SecondUse == *DestinationA, + "backedge COPYs must read old PHI destinations into distinct temporaries"); + } + + auto FreshInfo = Function.registerInfo().virtualRegisterInfo(*FreshA); + Context.expect(FreshInfo.has_value(), "fresh PHI vreg must remain registered"); + if (!FreshInfo) + return; + Context.expect(FreshInfo->get().Type == I64, "fresh PHI vreg must clone its LLT"); + Context.expect(FreshInfo->get().Bank == rcc::test::TestRegisterBank::GPR, + "fresh PHI vreg must clone its register bank"); + Context.expect(FreshInfo->get().RegClass == rcc::test::TestRegisterClass::GPR64, + "fresh PHI vreg must clone its register class"); + Context.expect(FreshInfo->get().TargetFlags == 0x1, + "fresh PHI vreg must clone registered target flags"); + Context.expect(FreshInfo->get().AllocationHints.size() == 1, + "fresh PHI vreg must clone the allocation-hint count"); + Context.expect(!FreshInfo->get().AllocationHints.empty() && + FreshInfo->get().AllocationHints.front() == Hint, + "fresh PHI vreg must clone the allocation-hint register"); + Context.expect(HeaderInstructions[1]->operandAt(0)->targetFlags() == 0x4 && + HeaderInstructions[1]->operandAt(1)->targetFlags() == 0x4, + "successor COPY must preserve registered destination target flags"); + + const rcc::MachineInstr *InitDefinition = Preheader.firstInstruction(); + Context.expect( + InitDefinition != nullptr && + !InitDefinition->operandAt(0)->registerFlags().has(rcc::RegisterOperandFlag::Dead) && + !BackedgeInstructions[0]->operandAt(0)->registerFlags().has( + rcc::RegisterOperandFlag::Kill), + "liveness-preserving PHI elimination must conservatively clear kill/dead flags"); + Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(), + "parallel PHI result must pass MachineVerifier"); +} + +void testCriticalEdgeAndPhysicalLiveIn(TestContext &Context, const rcc::TargetDescription &Target, + const TestSSAInfo &Info) { + auto Fixture = createFunction(Context, "critical_edge", 2, 4); + if (!Fixture.Function || Fixture.Blocks.size() != 4) + return; + auto I64 = rcc::LLT::makeInteger(64); + if (!I64) + return; + auto &Function = *Fixture.Function; + rcc::MachineBasicBlock &From = *Fixture.Blocks[0]; + rcc::MachineBasicBlock &Side = *Fixture.Blocks[1]; + rcc::MachineBasicBlock &Other = *Fixture.Blocks[2]; + rcc::MachineBasicBlock &Merge = *Fixture.Blocks[3]; + auto Condition = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + auto OtherValue = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + auto Destination = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + if (!Condition || !OtherValue || !Destination) + return; + + auto Half = rcc::BranchProbability::fromFraction(1, 2); + auto CFG = Function.cfgUpdater(); + Context.expect(Half && CFG.addSuccessor(From, Side, *Half) && + CFG.addSuccessor(From, Merge, *Half) && + CFG.addSuccessor(Other, Merge, rcc::BranchProbability::one()), + "critical-edge CFG must be connected"); + + const std::array ConditionDef{*Condition}; + Context.expect( + buildRegisterInstruction(Function, Target, From, testOpcode(DefOpcode), ConditionDef, {}) + .has_value(), + "critical-edge condition must be defined"); + rcc::MachineIRBuilder FromBuilder(Function, Target); + if (!FromBuilder.setInsertPoint(From)) + return; + auto Branch = FromBuilder.buildInstr(testOpcode(ConditionalBranchOpcode)); + Context.expect(Branch && Branch->addUse(*Condition) && Branch->addBasicBlock(Merge) && + Branch->build(), + "critical-edge conditional branch must be built"); + const std::array OtherDef{*OtherValue}; + Context.expect( + buildRegisterInstruction(Function, Target, Other, testOpcode(DefOpcode), OtherDef, {}) + .has_value(), + "unrelated fallthrough predecessor must define its incoming value"); + + const rcc::PhysicalRegister G0 = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G0); + const rcc::PhysicalRegister G1 = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G1); + Context.expect(Merge.addLiveIn(G1, rcc::LaneMask::fromRaw(0xF)).has_value(), + "merge block live-in setup must succeed"); + const std::array Incoming{ + std::pair<rcc::Register, rcc::MachineBasicBlock *>{rcc::Register::fromPhysical(G0), &From}, + std::pair<rcc::Register, rcc::MachineBasicBlock *>{*OtherValue, &Other}}; + Context.expect(buildPhi(Function, Target, Merge, *Destination, Incoming).has_value(), + "critical-edge PHI must be built"); + setSelectedSSAProperties(Function); + + auto Run = runPHIElimination(Function, Target, Info); + Context.expect(Run.has_value(), "critical-edge PHI elimination must succeed"); + if (!Run) + return; + + rcc::MachineBasicBlock *Edge = Merge.previous(); + Context.expect( + Edge != nullptr && Edge != &Other && Edge->previous() == &Other && + From.successors().size() == 2 && + std::ranges::any_of(From.successors(), + [Edge](const rcc::MachineSuccessor &S) { return S.Block == Edge; }) && + Edge->predecessors().size() == 1 && Edge->predecessors()[0] == &From && + Edge->successors().size() == 1 && Edge->successors()[0].Block == &Merge, + "critical edge must become a reciprocal From-to-edge-to-Merge CFG path"); + if (Edge == nullptr || Edge == &Other) + return; + + const rcc::MachineOperand *BranchTarget = From.lastInstruction()->operandAt(1); + const auto *BranchBlock = + BranchTarget == nullptr ? nullptr : BranchTarget->getIf<rcc::BasicBlockOperand>(); + Context.expect(BranchBlock != nullptr && BranchBlock->Block == Edge, + "explicit critical-edge branch must target the split block"); + const auto OtherInstructions = linkedInstructions(Other); + const auto EdgeInstructions = linkedInstructions(*Edge); + Context.expect(OtherInstructions.size() == 3 && + OtherInstructions.back()->opcode() == testOpcode(JumpOpcode) && + EdgeInstructions.size() == 2 && + EdgeInstructions[0]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) && + EdgeInstructions[1]->opcode() == testOpcode(JumpOpcode), + "edge split must preserve unrelated fallthrough and terminator placement"); + Context.expect(hasLiveIn(*Edge, G0) && hasLiveIn(*Edge, G1), + "split edge must inherit successor live-ins and its physical PHI source"); + Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(), + "critical-edge result must pass MachineVerifier"); +} + +void testUndefAndFailureAtomicity(TestContext &Context, const rcc::TargetDescription &Target, + const TestSSAInfo &Info) { + auto BuildFixture = [&](std::uint64_t ID) { + auto Fixture = createFunction(Context, "undef_phi", ID, 2); + if (!Fixture.Function || Fixture.Blocks.size() != 2) + return Fixture; + auto I64 = rcc::LLT::makeInteger(64); + if (!I64) + return Fixture; + auto Source = createVReg(*Fixture.Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + auto Destination = createVReg(*Fixture.Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + if (!Source || !Destination) + return Fixture; + auto CFG = Fixture.Function->cfgUpdater(); + if (!CFG.addSuccessor(*Fixture.Blocks[0], *Fixture.Blocks[1], rcc::BranchProbability::one()) || + !buildJump(*Fixture.Function, Target, *Fixture.Blocks[0], *Fixture.Blocks[1])) { + return Fixture; + } + const std::array Incoming{ + std::pair<rcc::Register, rcc::MachineBasicBlock *>{*Source, Fixture.Blocks[0]}}; + if (!buildPhi(*Fixture.Function, Target, *Fixture.Blocks[1], *Destination, Incoming, {}, 0, + {rcc::RegisterOperandFlag::Undef})) { + return Fixture; + } + setSelectedSSAProperties(*Fixture.Function); + return Fixture; + }; + + auto Undef = BuildFixture(3); + if (!Undef.Function) + return; + auto Run = runPHIElimination(*Undef.Function, Target, Info); + Context.expect(Run.has_value(), "undef PHI elimination must succeed"); + if (Run) { + const auto PredecessorInstructions = linkedInstructions(*Undef.Blocks[0]); + Context.expect(PredecessorInstructions.size() == 2 && + PredecessorInstructions[0]->opcode() == + rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF) && + PredecessorInstructions[1]->opcode() == testOpcode(JumpOpcode), + "undef PHI incoming values must become edge IMPLICIT_DEF instructions"); + } + + auto Atomic = BuildFixture(4); + if (!Atomic.Function) + return; + const std::size_t BlocksBefore = Atomic.Function->blockCount(); + const std::size_t InstructionsBefore = + instructionsWithOpcode(*Atomic.Function, rcc::opcode(rcc::GenericOpcode::PHI)).size(); + const std::size_t RegistersBefore = Atomic.Function->registerInfo().virtualRegisters().size(); + const std::uint64_t PropertiesBefore = Atomic.Function->properties().rawValue(); + TestSSAInfo RejectingInfo(true); + rcc::MachineAnalysisManager Analyses; + rcc::PHIEliminationPass FailingPass(RejectingInfo); + auto Failed = FailingPass.run(*Atomic.Function, Target, Analyses); + Context.expect(!Failed && Failed.error().code() == rcc::ErrorCode::Unsupported, + "COPY rejection must produce a structured PHI-elimination failure"); + Context.expect( + Atomic.Function->blockCount() == BlocksBefore && + instructionsWithOpcode(*Atomic.Function, rcc::opcode(rcc::GenericOpcode::PHI)).size() == + InstructionsBefore && + Atomic.Function->registerInfo().virtualRegisters().size() == RegistersBefore && + Atomic.Function->properties().rawValue() == PropertiesBefore, + "failed PHI transaction preflight must leave the original function unchanged"); + + rcc::PHIEliminationPass MissingBehavior; + auto Missing = MissingBehavior.run(*Atomic.Function, Target, Analyses); + Context.expect(!Missing && Missing.error().code() == rcc::ErrorCode::InvalidArgument, + "PHI elimination without target behavior must fail explicitly"); +} + +void testTwoAddressAndSubregisterPseudos(TestContext &Context, const rcc::TargetDescription &Target, + const TestSSAInfo &Info) { + auto Fixture = createFunction(Context, "two_address", 5, 1); + if (!Fixture.Function || Fixture.Blocks.empty()) + return; + auto I64 = rcc::LLT::makeInteger(64); + auto I32 = rcc::LLT::makeInteger(32); + if (!I64 || !I32) + return; + auto &Function = *Fixture.Function; + rcc::MachineBasicBlock &Block = *Fixture.Blocks[0]; + auto GPR64 = [&](std::uint8_t Flags = 0) { + return createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64, Flags); + }; + auto GPR32 = [&]() { + return createVReg(Function, *I32, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR32); + }; + + auto Satisfied = GPR64(); + auto UndefSource = GPR64(); + auto UndefDestination = GPR64(); + auto CommuteSource = GPR64(); + auto CommuteDestination = GPR64(); + auto ConvertSource = GPR64(); + auto ConvertDestination = GPR64(); + auto FallbackSource = GPR64(); + auto FallbackDestination = GPR64(); + auto SequenceDestination = GPR64(); + auto SequenceLow = GPR32(); + auto SequenceHigh = GPR32(); + auto InsertDestination = GPR64(); + auto InsertBase = GPR64(); + auto Inserted = GPR32(); + const bool Complete = Satisfied && UndefSource && UndefDestination && CommuteSource && + CommuteDestination && ConvertSource && ConvertDestination && + FallbackSource && FallbackDestination && SequenceDestination && + SequenceLow && SequenceHigh && InsertDestination && InsertBase && Inserted; + Context.expect(Complete, "two-address test registers must be created"); + if (!Complete) + return; + + for (rcc::Register Source : {*CommuteSource, *ConvertSource, *FallbackSource, *SequenceLow, + *SequenceHigh, *InsertBase, *Inserted}) { + const std::array Def{Source}; + Context.expect(buildRegisterInstruction(Function, Target, Block, testOpcode(DefOpcode), Def, {}, + {rcc::RegisterOperandFlag::Dead}) + .has_value(), + "two-address source definition must be built"); + } + const std::array UndefDef{*UndefSource}; + Context.expect(buildRegisterInstruction(Function, Target, Block, + rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF), UndefDef, + {}) + .has_value(), + "two-address undef source must be defined by IMPLICIT_DEF"); + + auto BuildTied = [&](rcc::Opcode Opcode, rcc::Register Def, rcc::Register Use, + std::optional<rcc::Register> Other = std::nullopt) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return rcc::Expected<rcc::MachineInstr *>{std::unexpected(Point.error())}; + auto Pending = Builder.buildInstr(Opcode); + if (!Pending) + return rcc::Expected<rcc::MachineInstr *>{std::unexpected(Pending.error())}; + auto AddedDef = Pending->addDef(Def); + if (!AddedDef) + return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedDef.error())}; + auto AddedUse = Pending->addUse(Use, {rcc::RegisterOperandFlag::Kill}); + if (!AddedUse) + return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedUse.error())}; + if (Other) { + auto AddedOther = Pending->addUse(*Other); + if (!AddedOther) + return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedOther.error())}; + } + return Pending->build(); + }; + + auto AlreadyTied = BuildTied(testOpcode(TiedOpcode), *Satisfied, *Satisfied); + auto UndefTied = BuildTied(testOpcode(TiedOpcode), *UndefDestination, *UndefSource); + auto Commutable = BuildTied(testOpcode(CommutableTiedOpcode), *CommuteDestination, *CommuteSource, + *CommuteDestination); + auto Convertible = + BuildTied(testOpcode(ConvertibleTiedOpcode), *ConvertDestination, *ConvertSource); + auto Fallback = BuildTied(testOpcode(TiedOpcode), *FallbackDestination, *FallbackSource); + Context.expect(AlreadyTied && UndefTied && Commutable && Convertible && Fallback, + "two-address instruction fixtures must be built"); + if (!AlreadyTied || !UndefTied || !Commutable || !Convertible || !Fallback) + return; + + rcc::MachineIRBuilder Builder(Function, Target); + if (!Builder.setInsertPoint(Block)) + return; + auto Sequence = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE)); + Context.expect( + Sequence && Sequence->addDef(*SequenceDestination) && Sequence->addUse(*SequenceLow) && + Sequence->addImmediate(rcc::test::TestSubReg::Low32.value()) && + Sequence->addUse(*SequenceHigh) && + Sequence->addImmediate(rcc::test::TestSubReg::High32.value()) && Sequence->build(), + "REG_SEQUENCE fixture must be built"); + auto Insert = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::INSERT_SUBREG)); + Context.expect(Insert && Insert->addDef(*InsertDestination) && Insert->addUse(*InsertBase) && + Insert->addUse(*Inserted) && + Insert->addImmediate(rcc::test::TestSubReg::Low32.value()) && Insert->build(), + "INSERT_SUBREG fixture must be built"); + auto Return = Builder.buildInstr(testOpcode(ReturnOpcode)); + Context.expect(Return && Return->build(), "two-address return must be built"); + + setSelectedSSAProperties(Function); + Function.properties().set(rcc::MachineFunctionProperty::NoPHIs); + rcc::MachinePassManager Pipeline; + Context.expect(Pipeline.addPass(std::make_unique<rcc::TwoAddressRewritePass>(Info)).has_value(), + "two-address pass must be registered"); + rcc::MachineAnalysisManager Analyses; + auto Run = Pipeline.run(Function, Target, Analyses); + Context.expect(Run.has_value(), "two-address rewrite must succeed"); + if (!Run) + return; + + Context.expect(Function.properties().has(rcc::MachineFunctionProperty::TiedOpsRewritten) && + !Function.properties().has(rcc::MachineFunctionProperty::IsSSA), + "two-address rewrite must publish TiedOpsRewritten and clear IsSSA"); + Context.expect( + instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE)).empty() && + instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::INSERT_SUBREG)).empty(), + "TwoAddressRewrite must consume all Stage 10 subregister pseudos"); + + Context.expect((*AlreadyTied)->operandAt(1)->registerValue() == *Satisfied, + "an already-satisfied tie must remain unchanged"); + Context.expect( + (*UndefTied)->operandAt(1)->registerValue() == *UndefDestination && + (*UndefTied)->operandAt(1)->registerFlags().has(rcc::RegisterOperandFlag::Undef), + "undef tied uses must be rewritten without a COPY"); + Context.expect((*Commutable)->operandAt(1)->registerValue() == *CommuteDestination && + (*Commutable)->operandAt(2)->registerValue() == *CommuteSource, + "commutation must satisfy a tie before COPY fallback"); + Context.expect((*Convertible)->opcode() == testOpcode(ThreeAddressOpcode) && + !(*Convertible)->operandAt(0)->tiedOperandIndex() && + !(*Convertible)->operandAt(1)->tiedOperandIndex(), + "target three-address conversion must run before COPY fallback"); + Context.expect((*Fallback)->previous() != nullptr && + (*Fallback)->previous()->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) && + (*Fallback)->previous()->operandAt(0)->registerValue() == + *FallbackDestination && + (*Fallback)->previous()->operandAt(1)->registerValue() == *FallbackSource && + (*Fallback)->operandAt(1)->registerValue() == *FallbackDestination, + "unsatisfied ties must receive a COPY immediately before the instruction"); + + const auto Copies = instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::COPY)); + const auto ImplicitDefs = + instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF)); + Context.expect(Copies.size() >= 5 && ImplicitDefs.size() >= 2, + "subregister pseudo expansion must materialize base and lane definitions"); + Context.expect( + std::ranges::any_of(Copies, + [InsertDestination](const rcc::MachineInstr *Copy) { + return Copy->operandAt(0)->registerValue() == *InsertDestination && + Copy->operandAt(0)->subReg() == rcc::test::TestSubReg::Low32; + }), + "INSERT_SUBREG must copy its inserted value into the requested destination lane"); + Context.expect( + std::ranges::all_of(Function.allInstructions(), + [](const rcc::MachineInstr *MI) { + if (MI->parent() == nullptr) + return true; + return std::ranges::none_of( + MI->operands(), [](const rcc::MachineOperand &Op) { + return Op.registerFlags().has(rcc::RegisterOperandFlag::Kill) || + Op.registerFlags().has(rcc::RegisterOperandFlag::Dead); + }); + }), + "two-address rewrite must conservatively clear stale kill/dead flags"); + Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(), + "two-address and subregister expansion result must verify"); + + auto AtomicFixture = createFunction(Context, "two_address_atomic", 10, 1); + if (!AtomicFixture.Function || AtomicFixture.Blocks.empty()) + return; + auto AtomicSource = createVReg(*AtomicFixture.Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + auto AtomicDestination = + createVReg(*AtomicFixture.Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + if (!AtomicSource || !AtomicDestination) + return; + const std::array AtomicSourceDef{*AtomicSource}; + Context.expect(buildRegisterInstruction(*AtomicFixture.Function, Target, *AtomicFixture.Blocks[0], + testOpcode(DefOpcode), AtomicSourceDef, {}) + .has_value(), + "two-address atomicity source definition must build"); + rcc::MachineIRBuilder AtomicBuilder(*AtomicFixture.Function, Target); + if (!AtomicBuilder.setInsertPoint(*AtomicFixture.Blocks[0])) + return; + auto AtomicPending = AtomicBuilder.buildInstr(testOpcode(TiedOpcode)); + auto AtomicInstruction = + AtomicPending && AtomicPending->addDef(*AtomicDestination) && + AtomicPending->addUse(*AtomicSource, {rcc::RegisterOperandFlag::Kill}) + ? AtomicPending->build() + : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected( + rcc::ErrorCode::InternalError, "failed to build atomicity fixture")}; + Context.expect(AtomicInstruction.has_value(), + "two-address atomicity tied instruction must build"); + if (!AtomicInstruction) + return; + setSelectedSSAProperties(*AtomicFixture.Function); + AtomicFixture.Function->properties().set(rcc::MachineFunctionProperty::NoPHIs); + const std::size_t AtomicInstructionsBefore = AtomicFixture.Function->allInstructions().size(); + const std::size_t AtomicRegistersBefore = + AtomicFixture.Function->registerInfo().virtualRegisters().size(); + const std::uint64_t AtomicPropertiesBefore = AtomicFixture.Function->properties().rawValue(); + + TestSSAInfo RejectingInfo(true); + rcc::MachineAnalysisManager AtomicAnalyses; + rcc::TwoAddressRewritePass FailingPass(RejectingInfo); + auto Failed = FailingPass.run(*AtomicFixture.Function, Target, AtomicAnalyses); + Context.expect(!Failed && Failed.error().code() == rcc::ErrorCode::Unsupported, + "COPY rejection must produce a structured two-address failure"); + Context.expect( + AtomicFixture.Function->allInstructions().size() == AtomicInstructionsBefore && + AtomicFixture.Function->registerInfo().virtualRegisters().size() == + AtomicRegistersBefore && + AtomicFixture.Function->properties().rawValue() == AtomicPropertiesBefore && + (*AtomicInstruction)->operandAt(0)->registerValue() == *AtomicDestination && + (*AtomicInstruction)->operandAt(1)->registerValue() == *AtomicSource && + (*AtomicInstruction)->operandAt(1)->registerFlags().has(rcc::RegisterOperandFlag::Kill), + "failed two-address transaction preflight must leave the original function unchanged"); + + rcc::TwoAddressRewritePass MissingBehavior; + auto Missing = MissingBehavior.run(*AtomicFixture.Function, Target, AtomicAnalyses); + Context.expect(!Missing && Missing.error().code() == rcc::ErrorCode::InvalidArgument, + "two-address rewrite without target behavior must fail explicitly"); +} + +void testVerifierAndPseudoFailures(TestContext &Context, const rcc::TargetDescription &Target) { + auto BuildBadPhi = [&](std::uint64_t ID, rcc::LLT DestinationType, + rcc::RegisterBankID DestinationBank, rcc::RegisterClassID DestinationClass, + rcc::LLT SourceType, rcc::RegisterBankID SourceBank, + rcc::RegisterClassID SourceClass, rcc::SubRegIndex SourceSubReg = {}) { + auto Fixture = createFunction(Context, "bad_phi", ID, 2); + if (!Fixture.Function || Fixture.Blocks.size() != 2) + return Fixture; + auto Destination = + createVReg(*Fixture.Function, DestinationType, DestinationBank, DestinationClass); + auto Source = createVReg(*Fixture.Function, SourceType, SourceBank, SourceClass); + if (!Destination || !Source) + return Fixture; + auto CFG = Fixture.Function->cfgUpdater(); + if (!CFG.addSuccessor(*Fixture.Blocks[0], *Fixture.Blocks[1], rcc::BranchProbability::one())) { + return Fixture; + } + const std::array SourceDef{*Source}; + if (!buildRegisterInstruction(*Fixture.Function, Target, *Fixture.Blocks[0], + testOpcode(DefOpcode), SourceDef, {})) { + return Fixture; + } + rcc::MachineIRBuilder Builder(*Fixture.Function, Target); + if (!Builder.setInsertPoint(*Fixture.Blocks[1])) + return Fixture; + auto Phi = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI)); + if (!Phi || !Phi->addDef(*Destination) || !Phi->addUse(*Source, {}, SourceSubReg) || + !Phi->addBasicBlock(*Fixture.Blocks[0]) || !Phi->build()) { + return Fixture; + } + return Fixture; + }; + + auto I64 = rcc::LLT::makeInteger(64); + auto I32 = rcc::LLT::makeInteger(32); + if (!I64 || !I32) + return; + auto BadType = + BuildBadPhi(6, *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64, + *I32, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR32); + Context.expect(BadType.Function && !rcc::MachineVerifier::verify(*BadType.Function, Target), + "MachineVerifier must reject incompatible PHI LLTs"); + + auto BadClass = + BuildBadPhi(7, *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64, + *I64, rcc::test::TestRegisterBank::FPR, rcc::test::TestRegisterClass::FPR64); + Context.expect(BadClass.Function && !rcc::MachineVerifier::verify(*BadClass.Function, Target), + "MachineVerifier must reject nonoverlapping PHI register classes"); + + auto BadSubReg = + BuildBadPhi(8, *I32, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR32Low, + *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64, + rcc::test::TestSubReg::High32); + Context.expect(BadSubReg.Function && !rcc::MachineVerifier::verify(*BadSubReg.Function, Target), + "MachineVerifier must reject incompatible PHI subregister projections"); + + auto Residual = createFunction(Context, "residual_stage10_pseudo", 9, 1); + if (!Residual.Function || Residual.Blocks.empty()) + return; + auto Destination = createVReg(*Residual.Function, *I64, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR64); + auto Source = createVReg(*Residual.Function, *I32, rcc::test::TestRegisterBank::GPR, + rcc::test::TestRegisterClass::GPR32); + if (!Destination || !Source) + return; + rcc::MachineIRBuilder Builder(*Residual.Function, Target); + if (!Builder.setInsertPoint(*Residual.Blocks[0])) + return; + auto Sequence = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE)); + Context.expect(Sequence && Sequence->addDef(*Destination) && Sequence->addUse(*Source) && + Sequence->addImmediate(rcc::test::TestSubReg::Low32.value()) && + Sequence->build(), + "residual Stage 10 pseudo fixture must be built"); + for (rcc::MachineFunctionProperty Property : + {rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected, + rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::NoPHIs, + rcc::MachineFunctionProperty::TiedOpsRewritten}) { + Residual.Function->properties().set(Property); + } + Context.expect(!rcc::MachineVerifier::verify(*Residual.Function, Target), + "TiedOpsRewritten must reject residual REG_SEQUENCE/INSERT_SUBREG pseudos"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "SSA-exit TestTarget must be created"); + if (!Target) + return Context.result(); + TestSSAInfo Info; + testParallelPHIsAndPlacement(Context, *Target, Info); + testCriticalEdgeAndPhysicalLiveIn(Context, *Target, Info); + testUndefAndFailureAtomicity(Context, *Target, Info); + testTwoAddressAndSubregisterPseudos(Context, *Target, Info); + testVerifierAndPseudoFailures(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/MachineVerifierTest.cpp b/backend/unittests/CodeGen/MachineVerifierTest.cpp index ca265a7..528ff3b 100644 --- a/backend/unittests/CodeGen/MachineVerifierTest.cpp +++ b/backend/unittests/CodeGen/MachineVerifierTest.cpp @@ -102,7 +102,15 @@ private: auto Phi = instructionDescriptor(PhiOpcode, "TEST_PHI"); Phi.Operands.push_back(registerDescriptor(rcc::RegisterOperandRole::Def)); + auto PhiValue = registerDescriptor(rcc::RegisterOperandRole::Use); + PhiValue.VariadicGroup = true; + Phi.Operands.push_back(PhiValue); + rcc::OperandDescriptor PhiBlock; + PhiBlock.Kinds = {rcc::MachineOperand::Kind::BasicBlock}; + PhiBlock.VariadicGroup = true; + Phi.Operands.push_back(PhiBlock); Phi.NumExplicitDefs = 1; + Phi.Variadic = true; Phi.Flags.set(rcc::InstructionFlag::Pseudo); Phi.Flags.set(rcc::InstructionFlag::Phi); Phi.Owner = rcc::PseudoOwner::PhiElimination; @@ -302,6 +310,103 @@ void testReachableStructuralFailures(TestContext &Context) { } } +enum class PhiTestShape : std::uint8_t { + Valid, + MissingPredecessor, + DuplicatePredecessor, + NonPredecessor, + AfterInstruction, +}; + +[[nodiscard]] std::unique_ptr<rcc::MachineFunction> +createPhiTestFunction(TestContext &Context, const rcc::TargetDescription &Target, std::string Name, + std::uint64_t ID, PhiTestShape Shape) { + auto Function = createFunction(Context, std::move(Name), ID); + if (!Function) + return nullptr; + rcc::MachineBasicBlock *Left = createBlock(Context, *Function); + rcc::MachineBasicBlock *Right = createBlock(Context, *Function); + rcc::MachineBasicBlock *Merge = createBlock(Context, *Function); + rcc::MachineBasicBlock *Other = createBlock(Context, *Function); + if (Left == nullptr || Right == nullptr || Merge == nullptr || Other == nullptr) + return nullptr; + + auto CFG = Function->cfgUpdater(); + if (!CFG.addSuccessor(*Left, *Merge, rcc::BranchProbability::one()) || + !CFG.addSuccessor(*Right, *Merge, rcc::BranchProbability::one())) { + Context.expect(false, "PHI verifier test CFG must be constructed"); + return nullptr; + } + + auto Type = rcc::LLT::makeInteger(64); + auto Destination = Type ? Function->registerInfo().createVirtualRegister(*Type) + : rcc::Expected<rcc::Register>{std::unexpected(Type.error())}; + auto LeftValue = Type ? Function->registerInfo().createVirtualRegister(*Type) + : rcc::Expected<rcc::Register>{std::unexpected(Type.error())}; + auto RightValue = Type ? Function->registerInfo().createVirtualRegister(*Type) + : rcc::Expected<rcc::Register>{std::unexpected(Type.error())}; + if (!Destination || !LeftValue || !RightValue) { + Context.expect(false, "PHI verifier test registers must be created"); + return nullptr; + } + + rcc::MachineIRBuilder Builder(*Function, Target); + if (!Builder.setInsertPoint(*Merge)) { + Context.expect(false, "PHI verifier insertion point must be valid"); + return nullptr; + } + if (Shape == PhiTestShape::AfterInstruction && + buildNoOperand(Context, Builder, NopOpcode) == nullptr) + return nullptr; + + auto Phi = Builder.buildInstr(rcc::Opcode::fromValue(PhiOpcode)); + if (!Phi || !Phi->addDef(*Destination) || !Phi->addUse(*LeftValue) || + !Phi->addBasicBlock(*Left)) { + Context.expect(false, "PHI verifier instruction prefix must build"); + return nullptr; + } + if (Shape == PhiTestShape::DuplicatePredecessor) { + if (!Phi->addUse(*RightValue) || !Phi->addBasicBlock(*Left)) + return nullptr; + } else if (Shape == PhiTestShape::NonPredecessor) { + if (!Phi->addUse(*RightValue) || !Phi->addBasicBlock(*Other)) + return nullptr; + } else if (Shape != PhiTestShape::MissingPredecessor) { + if (!Phi->addUse(*RightValue) || !Phi->addBasicBlock(*Right)) + return nullptr; + } + if (!Phi->build()) { + Context.expect(false, "PHI verifier test instruction must publish"); + return nullptr; + } + return Function; +} + +void testPHIStructure(TestContext &Context) { + auto Target = createTarget(); + if (!Target) + return; + auto Valid = createPhiTestFunction(Context, *Target, "valid_phi", 60, PhiTestShape::Valid); + auto Missing = + createPhiTestFunction(Context, *Target, "missing_phi", 61, PhiTestShape::MissingPredecessor); + auto Duplicate = createPhiTestFunction(Context, *Target, "duplicate_phi", 62, + PhiTestShape::DuplicatePredecessor); + auto NonPredecessor = + createPhiTestFunction(Context, *Target, "foreign_phi", 63, PhiTestShape::NonPredecessor); + auto AfterInstruction = + createPhiTestFunction(Context, *Target, "late_phi", 64, PhiTestShape::AfterInstruction); + Context.expect(Valid && rcc::MachineVerifier::verify(*Valid, *Target), + "PHI with one incoming value per predecessor must verify"); + Context.expect(Missing && !rcc::MachineVerifier::verify(*Missing, *Target), + "PHI missing a predecessor must fail verification"); + Context.expect(Duplicate && !rcc::MachineVerifier::verify(*Duplicate, *Target), + "PHI with duplicate incoming blocks must fail verification"); + Context.expect(NonPredecessor && !rcc::MachineVerifier::verify(*NonPredecessor, *Target), + "PHI naming a non-predecessor must fail verification"); + Context.expect(AfterInstruction && !rcc::MachineVerifier::verify(*AfterInstruction, *Target), + "PHI after a code instruction must fail verification"); +} + void testPropertyFailures(TestContext &Context) { auto Target = createTarget(); if (!Target) @@ -428,7 +533,8 @@ void testSelectedStateAndPseudoDeadline(TestContext &Context) { "tied-state instruction must build"); for (const rcc::MachineFunctionProperty Property : {rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected, - rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::TiedOpsRewritten}) { + rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::NoPHIs, + rcc::MachineFunctionProperty::TiedOpsRewritten}) { Tied->properties().set(Property); } Context.expect(!rcc::MachineVerifier::verify(*Tied, *Target), @@ -470,6 +576,20 @@ void testSelectedStateAndPseudoDeadline(TestContext &Context) { Context.expect(!rcc::MachineVerifier::verify(*Dependency, *Target), "FrameFinalized must require NoVRegs and NoFrameIndices"); } + + auto SSAExitDependency = createFunction(Context, "ssa_exit_property_dependency", 65); + if (SSAExitDependency) { + for (const rcc::MachineFunctionProperty Property : + {rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected, + rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::TiedOpsRewritten}) { + SSAExitDependency->properties().set(Property); + } + Context.expect(!rcc::MachineVerifier::verify(*SSAExitDependency, *Target), + "TiedOpsRewritten must require NoPHIs"); + SSAExitDependency->properties().set(rcc::MachineFunctionProperty::NoPHIs); + Context.expect(rcc::MachineVerifier::verify(*SSAExitDependency, *Target).has_value(), + "TiedOpsRewritten dependency must be satisfied by NoPHIs"); + } } void testFrameStateFailures(TestContext &Context) { @@ -523,8 +643,7 @@ void testTableReferenceFailures(TestContext &Context) { rcc::MachineConstantPoolEntryDesc ConstantDescription; auto Integer = rcc::IntegerImmediate::fromUnsigned(32, 0x01010101U); - ConstantDescription.Value = - std::move(*rcc::GenericConstantData::integer(std::move(*Integer))); + ConstantDescription.Value = std::move(*rcc::GenericConstantData::integer(std::move(*Integer))); ConstantDescription.Size = 4; ConstantDescription.Align = *rcc::Alignment::create(4); auto ConstantIndex = ConstantFunction->constantPool().addEntry(std::move(ConstantDescription)); @@ -609,6 +728,7 @@ int main() { TestContext Context; testValidFunctionAndModes(Context); testReachableStructuralFailures(Context); + testPHIStructure(Context); testPropertyFailures(Context); testSelectedStateAndPseudoDeadline(Context); testFrameStateFailures(Context); diff --git a/backend/unittests/Target/CMakeLists.txt b/backend/unittests/Target/CMakeLists.txt index 98c4426..0bffb47 100644 --- a/backend/unittests/Target/CMakeLists.txt +++ b/backend/unittests/Target/CMakeLists.txt @@ -33,11 +33,17 @@ rcc_backend_configure_target(RCCBackendRISCVCodeGenTests) target_link_libraries(RCCBackendRISCVCodeGenTests PRIVATE RCCBackend::RISCV RCCBackend::CodeGen) add_test(NAME RCCBackendRISCVCodeGenTests COMMAND RCCBackendRISCVCodeGenTests) +add_executable(RCCBackendRISCVSSAExitTests RISCVSSAExitTest.cpp) +rcc_backend_configure_target(RCCBackendRISCVSSAExitTests) +target_link_libraries(RCCBackendRISCVSSAExitTests PRIVATE RCCBackend::RISCV RCCBackend::CodeGen) +add_test(NAME RCCBackendRISCVSSAExitTests COMMAND RCCBackendRISCVSSAExitTests) + rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/DescriptionGeneratorTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLoweringTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTargetTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGenTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVSSAExitTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.h" ) @@ -46,5 +52,6 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLoweringTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTargetTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGenTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVSSAExitTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.cpp" ) diff --git a/backend/unittests/Target/RISCVSSAExitTest.cpp b/backend/unittests/Target/RISCVSSAExitTest.cpp new file mode 100644 index 0000000..1440855 --- /dev/null +++ b/backend/unittests/Target/RISCVSSAExitTest.cpp @@ -0,0 +1,346 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/MachineSSAExit.h" +#include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/Target/RISCV/RISCVCodeGen.h" +#include "rcc/Target/RISCV/RISCVTarget.h" + +#include <algorithm> +#include <array> +#include <cstddef> +#include <cstdint> +#include <iostream> +#include <memory> +#include <optional> +#include <string> +#include <string_view> +#include <utility> +#include <vector> + +namespace { + +class TestContext final { +public: + void expect(bool Condition, std::string_view Message) { + if (Condition) + return; + std::cerr << Message << '\n'; + ++Failures; + } + + [[nodiscard]] int result() const noexcept { + return Failures == 0 ? 0 : 1; + } + +private: + int Failures = 0; +}; + +[[nodiscard]] rcc::Opcode targetOpcode(rcc::riscv::InstructionOpcode Opcode) { + return rcc::Opcode::fromValue(static_cast<std::uint32_t>(Opcode)); +} + +[[nodiscard]] rcc::RegisterBankID bank(rcc::riscv::RegisterBank Bank) { + return rcc::RegisterBankID::fromValue(static_cast<std::uint32_t>(Bank)); +} + +[[nodiscard]] rcc::RegisterClassID regClass(rcc::riscv::RegisterClass Class) { + return rcc::RegisterClassID::fromValue(static_cast<std::uint32_t>(Class)); +} + +[[nodiscard]] rcc::Expected<rcc::Register> createVReg(rcc::MachineFunction &Function, rcc::LLT Type, + rcc::riscv::RegisterBank Bank, + rcc::riscv::RegisterClass Class) { + auto Reg = Function.registerInfo().createVirtualRegister(Type); + if (!Reg) + return std::unexpected(Reg.error()); + auto BankResult = Function.registerInfo().setRegisterBank(*Reg, bank(Bank)); + if (!BankResult) + return std::unexpected(BankResult.error()); + auto ClassResult = Function.registerInfo().setRegisterClass(*Reg, regClass(Class)); + if (!ClassResult) + return std::unexpected(ClassResult.error()); + return *Reg; +} + +[[nodiscard]] rcc::Expected<rcc::MachineBasicBlock *> appendBlock(rcc::MachineFunction &Function) { + auto Block = Function.createBasicBlock(); + if (!Block) + return std::unexpected(Block.error()); + auto Appended = Function.appendBlock(**Block); + if (!Appended) + return std::unexpected(Appended.error()); + return *Block; +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildAddImmediate(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Destination, rcc::Register Source, + std::int64_t Immediate) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(targetOpcode(rcc::riscv::InstructionOpcode::ADDI)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Destination); + if (!Def) + return std::unexpected(Def.error()); + auto Use = Pending->addUse(Source); + if (!Use) + return std::unexpected(Use.error()); + auto Value = Pending->addImmediate(Immediate); + if (!Value) + return std::unexpected(Value.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildBranchEqual(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Left, rcc::Register Right, + rcc::MachineBasicBlock &Destination) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(targetOpcode(rcc::riscv::InstructionOpcode::BEQ)); + if (!Pending) + return std::unexpected(Pending.error()); + auto LeftUse = Pending->addUse(Left); + if (!LeftUse) + return std::unexpected(LeftUse.error()); + auto RightUse = Pending->addUse(Right); + if (!RightUse) + return std::unexpected(RightUse.error()); + auto TargetOperand = Pending->addBasicBlock(Destination); + if (!TargetOperand) + return std::unexpected(TargetOperand.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Destination, + const std::array<std::pair<rcc::Register, rcc::MachineBasicBlock *>, 2> &Incoming) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Destination); + if (!Def) + return std::unexpected(Def.error()); + for (const auto &[Value, Predecessor] : Incoming) { + auto Use = Pending->addUse(Value); + if (!Use) + return std::unexpected(Use.error()); + auto IncomingBlock = Pending->addBasicBlock(*Predecessor); + if (!IncomingBlock) + return std::unexpected(IncomingBlock.error()); + } + return Pending->build(); +} + +[[nodiscard]] const rcc::BasicBlockOperand *blockOperand(const rcc::MachineInstr &Instruction, + std::size_t Index) { + const rcc::MachineOperand *Operand = Instruction.operandAt(Index); + return Operand == nullptr ? nullptr : Operand->getIf<rcc::BasicBlockOperand>(); +} + +[[nodiscard]] std::vector<rcc::MachineInstr *> linkedInstructions(rcc::MachineBasicBlock &Block) { + std::vector<rcc::MachineInstr *> Result; + for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Result.push_back(Instruction); + } + return Result; +} + +void setSelectedSSAProperties(rcc::MachineFunction &Function) { + for (rcc::MachineFunctionProperty Property : + {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness, + rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected, + rcc::MachineFunctionProperty::Selected}) { + Function.properties().set(Property); + } +} + +void testBehaviorAndCopyLegality(TestContext &Context, const rcc::TargetDescription &Target) { + auto Function = rcc::MachineFunction::create("riscv_ssa_behavior", + rcc::MachineFunctionStableID::fromValue(1)); + if (!Function) + return; + auto First = appendBlock(**Function); + auto Second = appendBlock(**Function); + auto Third = appendBlock(**Function); + if (!First || !Second || !Third) + return; + auto CFG = (*Function)->cfgUpdater(); + if (!CFG.addSuccessor(**First, **Second, rcc::BranchProbability::one())) + return; + + auto Fallthrough = rcc::riscv::ssaInfo().isFallthroughEdge(**First, **Second, **Function, Target); + Context.expect(Fallthrough && *Fallthrough, + "RV64GC SSA behavior must recognize an empty layout fallthrough edge"); + auto Inserted = + rcc::riscv::ssaInfo().insertUnconditionalBranch(**First, **Second, **Function, Target); + Context.expect(Inserted.has_value(), "RV64GC SSA behavior must insert an unconditional branch"); + if (!Inserted) + return; + rcc::MachineInstr *Jump = (*First)->lastInstruction(); + const auto X0 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X0); + Context.expect(Jump != nullptr && + Jump->opcode() == targetOpcode(rcc::riscv::InstructionOpcode::JAL) && + Jump->operandAt(0)->registerValue() == rcc::Register::fromPhysical(*X0) && + blockOperand(*Jump, 1) != nullptr && blockOperand(*Jump, 1)->Block == *Second, + "RV64GC unconditional branches must use JAL with x0 as the link destination"); + auto NoFallthrough = + rcc::riscv::ssaInfo().isFallthroughEdge(**First, **Second, **Function, Target); + Context.expect(NoFallthrough && !*NoFallthrough, "JAL must terminate RV64GC layout fallthrough"); + auto Rewritten = + rcc::riscv::ssaInfo().rewriteBranchTarget(**First, **Second, **Third, **Function, Target); + Context.expect(Rewritten && *Rewritten && blockOperand(*Jump, 1)->Block == *Third, + "RV64GC branch target rewriting must update direct JAL operands"); + + auto I64 = rcc::LLT::makeInteger(64); + auto F64 = rcc::LLT::makeFloat(rcc::FloatSemantics::IEEEDouble); + auto F32 = rcc::LLT::makeFloat(rcc::FloatSemantics::IEEESingle); + if (!I64 || !F64 || !F32) + return; + auto GPR = + createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR); + auto OtherGPR = + createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR); + auto FPR64 = + createVReg(**Function, *F64, rcc::riscv::RegisterBank::FPR, rcc::riscv::RegisterClass::FPR64); + auto FPR32 = + createVReg(**Function, *F32, rcc::riscv::RegisterBank::FPR, rcc::riscv::RegisterClass::FPR32); + auto Unclassified = (*Function)->registerInfo().createVirtualRegister(*I64); + if (!GPR || !OtherGPR || !FPR64 || !FPR32 || !Unclassified) + return; + + Context.expect( + rcc::riscv::ssaInfo().validateCopy(*GPR, {}, *OtherGPR, {}, **Function, Target).has_value(), + "RV64GC must allow a compatible GPR COPY"); + Context.expect( + rcc::riscv::ssaInfo().validateCopy(*GPR, {}, *FPR64, {}, **Function, Target).has_value(), + "RV64GC must allow supported 64-bit GPR/FPR bit moves"); + Context.expect(!rcc::riscv::ssaInfo().validateCopy(*FPR64, {}, *FPR32, {}, **Function, Target), + "RV64GC must reject incompatible same-bank COPY widths"); + Context.expect(!rcc::riscv::ssaInfo().validateCopy(*GPR, rcc::SubRegIndex::fromValue(1), + *OtherGPR, {}, **Function, Target), + "RV64GC must reject unmodeled subregister COPYs"); + Context.expect( + !rcc::riscv::ssaInfo().validateCopy(*GPR, {}, *Unclassified, {}, **Function, Target), + "RV64GC must reject COPYs involving an unconstrained virtual register"); +} + +void testRV64GCCriticalEdge(TestContext &Context, const rcc::TargetDescription &Target) { + auto Function = rcc::MachineFunction::create("riscv_ssa_critical_edge", + rcc::MachineFunctionStableID::fromValue(2)); + if (!Function) + return; + auto From = appendBlock(**Function); + auto Side = appendBlock(**Function); + auto Other = appendBlock(**Function); + auto Merge = appendBlock(**Function); + if (!From || !Side || !Other || !Merge) + return; + auto I64 = rcc::LLT::makeInteger(64); + auto X0 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X0); + if (!I64 || !X0) + return; + auto FromValue = + createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR); + auto OtherValue = + createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR); + auto Destination = + createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR); + if (!FromValue || !OtherValue || !Destination) + return; + + auto Half = rcc::BranchProbability::fromFraction(1, 2); + auto CFG = (*Function)->cfgUpdater(); + Context.expect(Half && CFG.addSuccessor(**From, **Side, *Half) && + CFG.addSuccessor(**From, **Merge, *Half) && + CFG.addSuccessor(**Other, **Merge, rcc::BranchProbability::one()), + "RV64GC critical-edge CFG must be connected"); + const rcc::Register Zero = rcc::Register::fromPhysical(*X0); + Context.expect(buildAddImmediate(**Function, Target, **From, *FromValue, Zero, 1) && + buildBranchEqual(**Function, Target, **From, Zero, Zero, **Merge) && + buildAddImmediate(**Function, Target, **Other, *OtherValue, Zero, 2), + "RV64GC critical-edge instructions must be built"); + const std::array Incoming{ + std::pair<rcc::Register, rcc::MachineBasicBlock *>{*FromValue, *From}, + std::pair<rcc::Register, rcc::MachineBasicBlock *>{*OtherValue, *Other}}; + Context.expect(buildPhi(**Function, Target, **Merge, *Destination, Incoming).has_value(), + "RV64GC critical-edge PHI must be built"); + setSelectedSSAProperties(**Function); + + rcc::MachinePassManager Pipeline; + Context.expect(Pipeline.addPass(std::make_unique<rcc::PHIEliminationPass>(rcc::riscv::ssaInfo())) + .has_value(), + "RV64GC PHI-elimination pass must be registered"); + rcc::MachineAnalysisManager Analyses; + auto Run = Pipeline.run(**Function, Target, Analyses); + Context.expect(Run.has_value(), "RV64GC critical-edge PHI elimination must succeed"); + if (!Run) + return; + + rcc::MachineBasicBlock *Edge = (*Merge)->previous(); + Context.expect(Edge != nullptr && Edge != *Other && Edge->previous() == *Other, + "RV64GC critical edge must receive a dedicated layout block"); + if (Edge == nullptr || Edge == *Other) + return; + rcc::MachineInstr *Conditional = (*From)->lastInstruction(); + Context.expect(Conditional != nullptr && + Conditional->opcode() == targetOpcode(rcc::riscv::InstructionOpcode::BEQ) && + blockOperand(*Conditional, 2) != nullptr && + blockOperand(*Conditional, 2)->Block == Edge, + "RV64GC BEQ must be redirected to the critical-edge block"); + + const auto OtherInstructions = linkedInstructions(**Other); + const auto EdgeInstructions = linkedInstructions(*Edge); + Context.expect(OtherInstructions.size() == 3 && + OtherInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) && + OtherInstructions[2]->opcode() == + targetOpcode(rcc::riscv::InstructionOpcode::JAL) && + blockOperand(*OtherInstructions[2], 1)->Block == *Merge, + "RV64GC must materialize an unrelated fallthrough before edge-block insertion"); + Context.expect(EdgeInstructions.size() == 2 && + EdgeInstructions[0]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) && + EdgeInstructions[1]->opcode() == + targetOpcode(rcc::riscv::InstructionOpcode::JAL) && + EdgeInstructions[1]->operandAt(0)->registerValue() == Zero && + blockOperand(*EdgeInstructions[1], 1)->Block == *Merge, + "RV64GC edge block must transfer the PHI value and jump to the merge"); + Context.expect((*Function)->properties().has(rcc::MachineFunctionProperty::NoPHIs) && + !(*Function)->properties().has(rcc::MachineFunctionProperty::IsSSA), + "RV64GC PHI elimination must publish SSA-exit properties"); + Context.expect(rcc::MachineVerifier::verify(**Function, Target).has_value(), + "RV64GC SSA-exit result must pass MachineVerifier"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = rcc::riscv::createTargetDescription(); + Context.expect(Target.has_value(), "RV64GC target must be created for SSA-exit tests"); + if (!Target) + return Context.result(); + testBehaviorAndCopyLegality(Context, *Target); + testRV64GCCriticalEdge(Context, *Target); + return Context.result(); +} |