From d2cd152d658955a7fb64fb9a1329bc5bee4d8317 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Thu, 13 Aug 2026 02:43:59 +0800 Subject: [CodeGen] Split PHI elimination and two-address rewriting --- backend/include/rcc/CodeGen/MachineSSAExit.h | 49 - backend/include/rcc/CodeGen/PHIElimination.h | 31 + .../rcc/CodeGen/TwoAddressInstructionPass.h | 31 + backend/lib/CodeGen/CMakeLists.txt | 12 +- backend/lib/CodeGen/MachineSSAExit.cpp | 1129 ------------------- backend/lib/CodeGen/PHIElimination.cpp | 610 ++++++++++ backend/lib/CodeGen/TwoAddressInstructionPass.cpp | 661 +++++++++++ backend/lib/Target/RISCV/RISCVPipeline.cpp | 7 +- backend/unittests/CodeGen/CMakeLists.txt | 36 +- backend/unittests/CodeGen/MachineSSAExitTest.cpp | 1179 -------------------- backend/unittests/CodeGen/PHIEliminationTest.cpp | 479 ++++++++ backend/unittests/CodeGen/SSAExitTestSupport.h | 444 ++++++++ .../CodeGen/TwoAddressInstructionPassTest.cpp | 268 +++++ backend/unittests/Target/RISCVSSAExitTest.cpp | 2 +- 14 files changed, 2566 insertions(+), 2372 deletions(-) delete mode 100644 backend/include/rcc/CodeGen/MachineSSAExit.h create mode 100644 backend/include/rcc/CodeGen/PHIElimination.h create mode 100644 backend/include/rcc/CodeGen/TwoAddressInstructionPass.h delete mode 100644 backend/lib/CodeGen/MachineSSAExit.cpp create mode 100644 backend/lib/CodeGen/PHIElimination.cpp create mode 100644 backend/lib/CodeGen/TwoAddressInstructionPass.cpp delete mode 100644 backend/unittests/CodeGen/MachineSSAExitTest.cpp create mode 100644 backend/unittests/CodeGen/PHIEliminationTest.cpp create mode 100644 backend/unittests/CodeGen/SSAExitTestSupport.h create mode 100644 backend/unittests/CodeGen/TwoAddressInstructionPassTest.cpp (limited to 'backend') diff --git a/backend/include/rcc/CodeGen/MachineSSAExit.h b/backend/include/rcc/CodeGen/MachineSSAExit.h deleted file mode 100644 index 4b6966d..0000000 --- a/backend/include/rcc/CodeGen/MachineSSAExit.h +++ /dev/null @@ -1,49 +0,0 @@ -// 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/TargetInstrInfo.h" - -namespace rcc { - -class PHIEliminationPass final : public MachineFunctionPass { -public: - PHIEliminationPass() noexcept = default; - explicit PHIEliminationPass(const TargetInstrInfo &Info) noexcept : Info(&Info) {} - - [[nodiscard]] const MachinePassContract &contract() const noexcept override; - [[nodiscard]] Expected run(MachineFunction &Function, - const TargetDescription &Target, - MachineAnalysisManager &Analyses) override; - -private: - [[nodiscard]] Expected runImplementation(MachineFunction &Function, - const TargetDescription &Target, - MachineActionReplay &Actions); - - const TargetInstrInfo *Info = nullptr; -}; - -class TwoAddressRewritePass final : public MachineFunctionPass { -public: - TwoAddressRewritePass() noexcept = default; - explicit TwoAddressRewritePass(const TargetInstrInfo &Info) noexcept : Info(&Info) {} - - [[nodiscard]] const MachinePassContract &contract() const noexcept override; - [[nodiscard]] Expected run(MachineFunction &Function, - const TargetDescription &Target, - MachineAnalysisManager &Analyses) override; - -private: - [[nodiscard]] Expected runImplementation(MachineFunction &Function, - const TargetDescription &Target, - MachineActionReplay &Actions); - - const TargetInstrInfo *Info = nullptr; -}; - -} // namespace rcc - -#endif // RCC_CODEGEN_MACHINESSAEXIT_H diff --git a/backend/include/rcc/CodeGen/PHIElimination.h b/backend/include/rcc/CodeGen/PHIElimination.h new file mode 100644 index 0000000..3d69152 --- /dev/null +++ b/backend/include/rcc/CodeGen/PHIElimination.h @@ -0,0 +1,31 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_PHIELIMINATION_H +#define RCC_CODEGEN_PHIELIMINATION_H + +#include "rcc/CodeGen/MachinePass.h" + +namespace rcc { + +class TargetInstrInfo; + +class PHIEliminationPass final : public MachineFunctionPass { +public: + explicit PHIEliminationPass(const TargetInstrInfo &Info) noexcept : Info(Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineActionReplay &Actions); + + const TargetInstrInfo &Info; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_PHIELIMINATION_H diff --git a/backend/include/rcc/CodeGen/TwoAddressInstructionPass.h b/backend/include/rcc/CodeGen/TwoAddressInstructionPass.h new file mode 100644 index 0000000..696b46c --- /dev/null +++ b/backend/include/rcc/CodeGen/TwoAddressInstructionPass.h @@ -0,0 +1,31 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_TWOADDRESSINSTRUCTIONPASS_H +#define RCC_CODEGEN_TWOADDRESSINSTRUCTIONPASS_H + +#include "rcc/CodeGen/MachinePass.h" + +namespace rcc { + +class TargetInstrInfo; + +class TwoAddressInstructionPass final : public MachineFunctionPass { +public: + explicit TwoAddressInstructionPass(const TargetInstrInfo &Info) noexcept : Info(Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineActionReplay &Actions); + + const TargetInstrInfo &Info; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_TWOADDRESSINSTRUCTIONPASS_H diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 996f771..22bf032 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -66,7 +66,7 @@ set( RegAllocFast.cpp RegAllocPBQP.cpp VirtRegMap.cpp - MachineSSAExit.cpp + PHIElimination.cpp MachineVerifier.cpp MachineFunctionProperties.cpp MachineFunctionRecords.cpp @@ -80,6 +80,7 @@ set( TargetMIRTextInfo.cpp TargetRegisterInfo.cpp TargetSchedulingModel.cpp + TwoAddressInstructionPass.cpp ) set( RCCBackendCodeGenHeaders @@ -155,7 +156,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Spiller.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetRegisterAllocationInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/VirtRegMap.h" - "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineSSAExit.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PHIElimination.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" @@ -172,6 +173,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetMemoryFolding.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetRegisterInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetSchedulingModel.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TwoAddressInstructionPass.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetPseudoExpansion.h" ) @@ -271,7 +273,7 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBase.h" "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasic.h" "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocInternal.h" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/PHIElimination.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp" @@ -285,6 +287,7 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/TargetMIRTextInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetSchedulingModel.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/TwoAddressInstructionPass.cpp" ${RCCBackendCodeGenHeaders} ) rcc_backend_register_tidy_files( @@ -349,7 +352,7 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocFast.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocPBQP.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/VirtRegMap.cpp" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/PHIElimination.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp" @@ -363,4 +366,5 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/TargetMIRTextInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetSchedulingModel.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/TwoAddressInstructionPass.cpp" ) diff --git a/backend/lib/CodeGen/MachineSSAExit.cpp b/backend/lib/CodeGen/MachineSSAExit.cpp deleted file mode 100644 index ec10b3b..0000000 --- a/backend/lib/CodeGen/MachineSSAExit.cpp +++ /dev/null @@ -1,1129 +0,0 @@ -// 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/MachineLiveness.h" -#include "rcc/CodeGen/MachineOperand.h" -#include "rcc/CodeGen/MachineRegisterInfo.h" -#include "rcc/CodeGen/TargetDescription.h" - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -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{}(Key.From); - const std::size_t ToHash = std::hash{}(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 IncomingValues; -}; - -[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) { - Prefix.append(Source.message()); - return Error(Source.code(), std::move(Prefix)); -} - -[[nodiscard]] Expected 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 copyDebugLocation(MachineInstrBuilder &Builder, - const MachineInstr *Source) { - if (Source == nullptr || !Source->debugLocation()) - return {}; - return Builder.setDebugLocation(*Source->debugLocation()); -} - -[[nodiscard]] Expected 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 -buildCopy(MachineFunction &Function, const TargetDescription &Target, - const TargetInstrInfo &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 -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(); - 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 validatePhiValue(const MachineFunction &Function, - const TargetDescription &Target, - const MachineOperand &Destination, - const MachineOperand &Source) { - const Register *DestinationReg = Destination.getIf(); - const Register *SourceReg = Source.getIf(); - 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> collectPhiPlans(MachineBasicBlock &Block, - MachineFunction &Function, - const TargetDescription &Target) { - std::vector 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(); - 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 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(); - const BasicBlockOperand *IncomingBlock = - BlockOperand == nullptr ? nullptr : BlockOperand->getIf(); - 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 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 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 -placePhiCopiesOnEdge(MachineFunction &Function, const TargetDescription &Target, - const TargetInstrInfo &TargetInfo, MachineBasicBlock &From, - MachineBasicBlock &To, - std::unordered_map &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.insertBranch(*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.insertBranch(*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 repairTrackedLiveness(MachineFunction &Function, - const TargetDescription &Target, - MachinePassResult &Result) { - if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) { - return {}; - } - auto Rebuilt = rebuildMachineLiveness(Function, Target); - if (!Rebuilt) - return std::unexpected(Rebuilt.error()); - if (*Rebuilt) - Result.Changes.add(MachinePassChange::Operands); - return {}; -} - -[[nodiscard]] Expected subRegIndex(const MachineOperand &Operand, - const TargetDescription &Target) { - std::uint64_t Value = 0; - if (const auto *Immediate = Operand.getIf(); Immediate != nullptr) { - if (*Immediate <= 0) - return makeUnexpected(ErrorCode::VerificationError, - "subregister pseudo requires a positive subregister index"); - Value = static_cast(*Immediate); - } else if (const auto *WideImmediate = Operand.getIf(); - 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::max()) { - return makeUnexpected(ErrorCode::VerificationError, - "subregister pseudo index is outside the supported range"); - } - const SubRegIndex Result = SubRegIndex::fromValue(static_cast(Value)); - if (Target.registers().subRegIndex(Result) == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "subregister pseudo references an unknown target index"); - } - return Result; -} - -[[nodiscard]] Expected 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 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 expandRegSequence(MachineInstr &Instruction, MachineFunction &Function, - const TargetDescription &Target, - const TargetInstrInfo &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(); - 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(); - 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 expandInsertSubreg(MachineInstr &Instruction, - MachineFunction &Function, - const TargetDescription &Target, - const TargetInstrInfo &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(); - const Register *Base = BaseOperand == nullptr ? nullptr : BaseOperand->getIf(); - const Register *Inserted = - InsertedOperand == nullptr ? nullptr : InsertedOperand->getIf(); - 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 swapRegisterUses(MachineOperand &Left, MachineOperand &Right) { - const std::optional LeftReg = Left.registerValue(); - const std::optional 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 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 rewriteUndefTie(MachineOperand &Use, const MachineOperand &Def) { - const std::optional 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 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 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 = "phi-node-elimination", - .Requires = {MachineFunctionProperty::IsSSA, MachineFunctionProperty::Selected, - MachineFunctionProperty::RegBankSelected}, - .Sets = {MachineFunctionProperty::NoPHIs}, - .Clears = {MachineFunctionProperty::IsSSA}, - .RequiredAnalyses = {}, - .VerificationStage = PipelineStage::SSAEliminated, - }; - return Contract; -} - -Expected PHIEliminationPass::run(MachineFunction &Function, - const TargetDescription &Target, - MachineAnalysisManager &Analyses) { - if (Info == nullptr) { - return makeUnexpected(ErrorCode::InvalidArgument, - "PHI elimination has no target instruction information"); - } - 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: ")); - } - MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); - if (!TrialResult) - return std::unexpected(TrialResult.error()); - - Actions.beginReplay(); - auto Result = runImplementation(Function, Target, Actions); - if (!Result) { - return std::unexpected(prefixedError( - Result.error(), "PHI elimination diverged after a successful transaction preflight: ")); - } - auto Replayed = Actions.finishReplay(); - if (!Replayed) - return std::unexpected(Replayed.error()); - return Result; -} - -Expected PHIEliminationPass::runImplementation(MachineFunction &Function, - const TargetDescription &Target, - MachineActionReplay &Actions) { - MachinePassResult Result; - std::unordered_map SplitEdges; - const std::vector 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 Accepted = Actions.request("eliminate-phi", Function, Plan.Instruction->stableID()); - if (!Accepted) - return std::unexpected(Accepted.error()); - if (!*Accepted) { - return makeUnexpected(ErrorCode::VerificationError, - "required PHI elimination action was rejected"); - } - 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 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 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 Repaired = repairTrackedLiveness(Function, Target, Result); - if (!Repaired) - return std::unexpected( - prefixedError(Repaired.error(), "PHI-elimination liveness repair failed: ")); - } - Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); - return Result; -} - -const MachinePassContract &TwoAddressRewritePass::contract() const noexcept { - static const MachinePassContract Contract{ - .Name = "twoaddressinstruction", - .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs}, - .Sets = {MachineFunctionProperty::TiedOpsRewritten}, - .Clears = {MachineFunctionProperty::IsSSA}, - .RequiredAnalyses = {}, - .VerificationStage = PipelineStage::TiedOpsRewritten, - }; - return Contract; -} - -Expected TwoAddressRewritePass::run(MachineFunction &Function, - const TargetDescription &Target, - MachineAnalysisManager &Analyses) { - if (Info == nullptr) { - return makeUnexpected(ErrorCode::InvalidArgument, - "two-address rewrite has no target instruction information"); - } - 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: ")); - } - MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); - auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); - if (!TrialResult) - return std::unexpected(TrialResult.error()); - - Actions.beginReplay(); - auto Result = runImplementation(Function, Target, Actions); - if (!Result) { - return std::unexpected(prefixedError( - Result.error(), "two-address rewrite diverged after a successful transaction preflight: ")); - } - auto Replayed = Actions.finishReplay(); - if (!Replayed) - return std::unexpected(Replayed.error()); - return Result; -} - -Expected -TwoAddressRewritePass::runImplementation(MachineFunction &Function, const TargetDescription &Target, - MachineActionReplay &Actions) { - MachinePassResult Result; - const std::vector Instructions(Function.allInstructions().begin(), - Function.allInstructions().end()); - for (MachineInstr *Instruction : Instructions) { - if (Instruction->parent() == nullptr) - continue; - if (Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE)) { - auto Accepted = Actions.request("expand-reg-sequence", Function, Instruction->stableID()); - if (!Accepted) - return std::unexpected(Accepted.error()); - if (!*Accepted) - return makeUnexpected(ErrorCode::VerificationError, - "required REG_SEQUENCE expansion action was rejected"); - 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 Accepted = Actions.request("expand-insert-subreg", Function, Instruction->stableID()); - if (!Accepted) - return std::unexpected(Accepted.error()); - if (!*Accepted) - return makeUnexpected(ErrorCode::VerificationError, - "required INSERT_SUBREG expansion action was rejected"); - 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 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 DefReg = Def->registerValue(); - const std::optional 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 Accepted = Actions.request("rewrite-undef-tie", Function, Instruction->stableID()); - if (!Accepted) - return std::unexpected(Accepted.error()); - if (!*Accepted) - return makeUnexpected(ErrorCode::VerificationError, - "required undef tie rewrite action was rejected"); - auto Rewritten = rewriteUndefTie(*Use, *Def); - if (!Rewritten) - return std::unexpected(Rewritten.error()); - Result.Changed = true; - Result.Changes.add(MachinePassChange::Operands); - continue; - } - - auto AllowCommute = - Actions.request("commute-tied-operands", Function, Instruction->stableID()); - if (!AllowCommute) - return std::unexpected(AllowCommute.error()); - if (*AllowCommute) { - 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 AllowConversion = - Actions.request("convert-three-address", Function, Instruction->stableID()); - if (!AllowConversion) - return std::unexpected(AllowConversion.error()); - if (*AllowConversion) { - 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; - } - } - - auto AllowCopy = Actions.request("insert-tied-copy", Function, Instruction->stableID()); - if (!AllowCopy) - return std::unexpected(AllowCopy.error()); - if (!*AllowCopy) - return makeUnexpected(ErrorCode::VerificationError, - "required tied COPY insertion action was rejected"); - 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 Repaired = repairTrackedLiveness(Function, Target, Result); - if (!Repaired) - return std::unexpected( - prefixedError(Repaired.error(), "two-address liveness repair failed: ")); - } - Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); - return Result; -} - -} // namespace rcc diff --git a/backend/lib/CodeGen/PHIElimination.cpp b/backend/lib/CodeGen/PHIElimination.cpp new file mode 100644 index 0000000..5539708 --- /dev/null +++ b/backend/lib/CodeGen/PHIElimination.cpp @@ -0,0 +1,610 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/PHIElimination.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/MachineLiveness.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetInstrInfo.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +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{}(Key.From); + const std::size_t ToHash = std::hash{}(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 IncomingValues; +}; + +[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) { + Prefix.append(Source.message()); + return Error(Source.code(), std::move(Prefix)); +} + +[[nodiscard]] Expected 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 copyDebugLocation(MachineInstrBuilder &Builder, + const MachineInstr *Source) { + if (Source == nullptr || !Source->debugLocation()) + return {}; + return Builder.setDebugLocation(*Source->debugLocation()); +} + +[[nodiscard]] Expected 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 +buildCopy(MachineFunction &Function, const TargetDescription &Target, + const TargetInstrInfo &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 +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(); + 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 validatePhiValue(const MachineFunction &Function, + const TargetDescription &Target, + const MachineOperand &Destination, + const MachineOperand &Source) { + const Register *DestinationReg = Destination.getIf(); + const Register *SourceReg = Source.getIf(); + 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> collectPhiPlans(MachineBasicBlock &Block, + MachineFunction &Function, + const TargetDescription &Target) { + std::vector 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(); + 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 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(); + const BasicBlockOperand *IncomingBlock = + BlockOperand == nullptr ? nullptr : BlockOperand->getIf(); + 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 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 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 +placePhiCopiesOnEdge(MachineFunction &Function, const TargetDescription &Target, + const TargetInstrInfo &TargetInfo, MachineBasicBlock &From, + MachineBasicBlock &To, + std::unordered_map &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.insertBranch(*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.insertBranch(*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 repairTrackedLiveness(MachineFunction &Function, + const TargetDescription &Target, + MachinePassResult &Result) { + if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) { + return {}; + } + auto Rebuilt = rebuildMachineLiveness(Function, Target); + if (!Rebuilt) + return std::unexpected(Rebuilt.error()); + if (*Rebuilt) + Result.Changes.add(MachinePassChange::Operands); + return {}; +} + +} // namespace + +const MachinePassContract &PHIEliminationPass::contract() const noexcept { + static const MachinePassContract Contract{ + .Name = "phi-node-elimination", + .Requires = {MachineFunctionProperty::IsSSA, MachineFunctionProperty::Selected, + MachineFunctionProperty::RegBankSelected}, + .Sets = {MachineFunctionProperty::NoPHIs}, + .Clears = {MachineFunctionProperty::IsSSA}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::SSAEliminated, + }; + return Contract; +} + +Expected PHIEliminationPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + 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: ")); + } + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); + if (!TrialResult) + return std::unexpected(TrialResult.error()); + + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); + if (!Result) { + return std::unexpected(prefixedError( + Result.error(), "PHI elimination diverged after a successful transaction preflight: ")); + } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); + return Result; +} + +Expected PHIEliminationPass::runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineActionReplay &Actions) { + MachinePassResult Result; + std::unordered_map SplitEdges; + const std::vector 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 Accepted = Actions.request("eliminate-phi", Function, Plan.Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return makeUnexpected(ErrorCode::VerificationError, + "required PHI elimination action was rejected"); + } + 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 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 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 Repaired = repairTrackedLiveness(Function, Target, Result); + if (!Repaired) + return std::unexpected( + prefixedError(Repaired.error(), "PHI-elimination liveness repair failed: ")); + } + Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); + return Result; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/TwoAddressInstructionPass.cpp b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp new file mode 100644 index 0000000..1959b90 --- /dev/null +++ b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp @@ -0,0 +1,661 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/TwoAddressInstructionPass.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineFunctionCloner.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetInstrInfo.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +struct RegisterValue final { + Register Reg; + SubRegIndex SubReg; + RegisterOperandFlags Flags; + std::uint32_t TargetFlags = 0; +}; + +[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) { + Prefix.append(Source.message()); + return Error(Source.code(), std::move(Prefix)); +} + +[[nodiscard]] Expected 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]] RegisterOperandFlags generatedDefFlags(RegisterOperandFlags Original) noexcept { + RegisterOperandFlags Result; + if (Original.has(RegisterOperandFlag::Undef)) + Result.set(RegisterOperandFlag::Undef); + return Result; +} + +[[nodiscard]] Expected copyDebugLocation(MachineInstrBuilder &Builder, + const MachineInstr *Source) { + if (Source == nullptr || !Source->debugLocation()) + return {}; + return Builder.setDebugLocation(*Source->debugLocation()); +} + +[[nodiscard]] Expected +buildCopy(MachineFunction &Function, const TargetDescription &Target, + const TargetInstrInfo &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 +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(); + 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 repairTrackedLiveness(MachineFunction &Function, + const TargetDescription &Target, + MachinePassResult &Result) { + if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) { + return {}; + } + auto Rebuilt = rebuildMachineLiveness(Function, Target); + if (!Rebuilt) + return std::unexpected(Rebuilt.error()); + if (*Rebuilt) + Result.Changes.add(MachinePassChange::Operands); + return {}; +} + +[[nodiscard]] Expected subRegIndex(const MachineOperand &Operand, + const TargetDescription &Target) { + std::uint64_t Value = 0; + if (const auto *Immediate = Operand.getIf(); Immediate != nullptr) { + if (*Immediate <= 0) + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo requires a positive subregister index"); + Value = static_cast(*Immediate); + } else if (const auto *WideImmediate = Operand.getIf(); + 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::max()) { + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo index is outside the supported range"); + } + const SubRegIndex Result = SubRegIndex::fromValue(static_cast(Value)); + if (Target.registers().subRegIndex(Result) == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo references an unknown target index"); + } + return Result; +} + +[[nodiscard]] Expected 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 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 expandRegSequence(MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &Target, + const TargetInstrInfo &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(); + 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(); + 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 expandInsertSubreg(MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target, + const TargetInstrInfo &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(); + const Register *Base = BaseOperand == nullptr ? nullptr : BaseOperand->getIf(); + const Register *Inserted = + InsertedOperand == nullptr ? nullptr : InsertedOperand->getIf(); + 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 swapRegisterUses(MachineOperand &Left, MachineOperand &Right) { + const std::optional LeftReg = Left.registerValue(); + const std::optional 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 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 rewriteUndefTie(MachineOperand &Use, const MachineOperand &Def) { + const std::optional 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 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 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 &TwoAddressInstructionPass::contract() const noexcept { + static const MachinePassContract Contract{ + .Name = "twoaddressinstruction", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs}, + .Sets = {MachineFunctionProperty::TiedOpsRewritten}, + .Clears = {MachineFunctionProperty::IsSSA}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::TiedOpsRewritten, + }; + return Contract; +} + +Expected TwoAddressInstructionPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + 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: ")); + } + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); + if (!TrialResult) + return std::unexpected(TrialResult.error()); + + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); + if (!Result) { + return std::unexpected(prefixedError( + Result.error(), "two-address rewrite diverged after a successful transaction preflight: ")); + } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); + return Result; +} + +Expected TwoAddressInstructionPass::runImplementation( + MachineFunction &Function, const TargetDescription &Target, MachineActionReplay &Actions) { + MachinePassResult Result; + const std::vector Instructions(Function.allInstructions().begin(), + Function.allInstructions().end()); + for (MachineInstr *Instruction : Instructions) { + if (Instruction->parent() == nullptr) + continue; + if (Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE)) { + auto Accepted = Actions.request("expand-reg-sequence", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::VerificationError, + "required REG_SEQUENCE expansion action was rejected"); + 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 Accepted = Actions.request("expand-insert-subreg", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::VerificationError, + "required INSERT_SUBREG expansion action was rejected"); + 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 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 DefReg = Def->registerValue(); + const std::optional 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 Accepted = Actions.request("rewrite-undef-tie", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::VerificationError, + "required undef tie rewrite action was rejected"); + auto Rewritten = rewriteUndefTie(*Use, *Def); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Operands); + continue; + } + + auto AllowCommute = + Actions.request("commute-tied-operands", Function, Instruction->stableID()); + if (!AllowCommute) + return std::unexpected(AllowCommute.error()); + if (*AllowCommute) { + 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 AllowConversion = + Actions.request("convert-three-address", Function, Instruction->stableID()); + if (!AllowConversion) + return std::unexpected(AllowConversion.error()); + if (*AllowConversion) { + 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; + } + } + + auto AllowCopy = Actions.request("insert-tied-copy", Function, Instruction->stableID()); + if (!AllowCopy) + return std::unexpected(AllowCopy.error()); + if (!*AllowCopy) + return makeUnexpected(ErrorCode::VerificationError, + "required tied COPY insertion action was rejected"); + 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 Repaired = repairTrackedLiveness(Function, Target, Result); + if (!Repaired) + return std::unexpected( + prefixedError(Repaired.error(), "two-address liveness repair failed: ")); + } + Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); + return Result; +} + +} // namespace rcc diff --git a/backend/lib/Target/RISCV/RISCVPipeline.cpp b/backend/lib/Target/RISCV/RISCVPipeline.cpp index 5212838..c5601ef 100644 --- a/backend/lib/Target/RISCV/RISCVPipeline.cpp +++ b/backend/lib/Target/RISCV/RISCVPipeline.cpp @@ -11,9 +11,10 @@ #include "rcc/CodeGen/MachineCombiner.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineOptimizationPipeline.h" -#include "rcc/CodeGen/MachineSSAExit.h" +#include "rcc/CodeGen/PHIElimination.h" #include "rcc/CodeGen/RegAllocPBQP.h" #include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TwoAddressInstructionPass.h" #include #include @@ -52,7 +53,7 @@ template Added = addPass(Pipeline, instrInfo()); if (!Added) return std::unexpected(Added.error()); - return addPass(Pipeline, instrInfo()); + return addPass(Pipeline, instrInfo()); } [[nodiscard]] Expected addRegisterAllocationPipeline(MachinePassManager &Pipeline) { @@ -110,7 +111,7 @@ Expected addCanonicalPipeline(MachinePassManager &Pipeline, const MachineF } } if (!Function.properties().has(MachineFunctionProperty::TiedOpsRewritten)) { - auto Added = addPass(Pipeline, instrInfo()); + auto Added = addPass(Pipeline, instrInfo()); if (!Added) return std::unexpected(Added.error()); } diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt index 3ae0f3d..7e79344 100644 --- a/backend/unittests/CodeGen/CMakeLists.txt +++ b/backend/unittests/CodeGen/CMakeLists.txt @@ -25,7 +25,8 @@ set( MachineSchedulingTest.cpp PBQPTest.cpp RegisterAllocationTest.cpp - MachineSSAExitTest.cpp + PHIEliminationTest.cpp + TwoAddressInstructionPassTest.cpp MachineVerifierTest.cpp MachineVerifierTargetTest.cpp MachineValueTypesTest.cpp @@ -371,13 +372,30 @@ target_link_libraries( ) add_test(NAME RCCBackend.CodeGen.MachineScheduling COMMAND RCCBackendCodeGenMachineSchedulingTests) -add_executable(RCCBackendCodeGenMachineSSAExitTests MachineSSAExitTest.cpp) -rcc_backend_configure_target(RCCBackendCodeGenMachineSSAExitTests) +add_executable(RCCBackendCodeGenPHIEliminationTests PHIEliminationTest.cpp) +rcc_backend_configure_target(RCCBackendCodeGenPHIEliminationTests) target_link_libraries( - RCCBackendCodeGenMachineSSAExitTests + RCCBackendCodeGenPHIEliminationTests PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget ) -add_test(NAME RCCBackend.CodeGen.MachineSSAExit COMMAND RCCBackendCodeGenMachineSSAExitTests) +add_test( + NAME RCCBackend.CodeGen.PHIElimination + COMMAND RCCBackendCodeGenPHIEliminationTests +) + +add_executable( + RCCBackendCodeGenTwoAddressInstructionPassTests + TwoAddressInstructionPassTest.cpp +) +rcc_backend_configure_target(RCCBackendCodeGenTwoAddressInstructionPassTests) +target_link_libraries( + RCCBackendCodeGenTwoAddressInstructionPassTests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget +) +add_test( + NAME RCCBackend.CodeGen.TwoAddressInstructionPass + COMMAND RCCBackendCodeGenTwoAddressInstructionPassTests +) add_executable(RCCBackendCodeGenTargetConstantTests TargetConstantTest.cpp) rcc_backend_configure_target(RCCBackendCodeGenTargetConstantTests) @@ -460,7 +478,9 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulingTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/PHIEliminationTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SSAExitTestSupport.h" + "${CMAKE_CURRENT_SOURCE_DIR}/TwoAddressInstructionPassTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTargetTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp" @@ -501,7 +521,9 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulingTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/PHIEliminationTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SSAExitTestSupport.h" + "${CMAKE_CURRENT_SOURCE_DIR}/TwoAddressInstructionPassTest.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/MachineSSAExitTest.cpp b/backend/unittests/CodeGen/MachineSSAExitTest.cpp deleted file mode 100644 index a5cc1c7..0000000 --- a/backend/unittests/CodeGen/MachineSSAExitTest.cpp +++ /dev/null @@ -1,1179 +0,0 @@ -// 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/MachineLiveness.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 "rcc/CodeGen/TargetInstrInfo.h" - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -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 createTarget() { - std::vector Descriptors; - std::vector 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 TestInstrInfo final : public rcc::TargetInstrInfo { -public: - explicit TestInstrInfo(bool RejectCopies = false) : RejectCopies(RejectCopies) {} - - [[nodiscard]] rcc::Expected - analyzeBranch(rcc::MachineBasicBlock &, rcc::MachineFunction &, - const rcc::TargetDescription &) const override { - return rcc::MachineBranchAnalysis{}; - } - - [[nodiscard]] rcc::Expected - reverseBranchCondition(rcc::MachineInstr &, rcc::MachineBasicBlock &, rcc::MachineFunction &, - const rcc::TargetDescription &) const override { - return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test target has no branch reversal"); - } - - [[nodiscard]] rcc::Expected removeBranch(rcc::MachineInstr &, rcc::MachineFunction &, - const rcc::TargetDescription &) const override { - return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test target has no branch removal"); - } - - [[nodiscard]] rcc::Expected - 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 - 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(); - 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 - insertBranch(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 *Built; - } - - [[nodiscard]] rcc::Expected - 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 - 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; - } - - [[nodiscard]] rcc::Expected - instructionSize(const rcc::MachineInstr &, const rcc::MachineFunction &, - const rcc::TargetDescription &) const override { - return 4; - } - - [[nodiscard]] rcc::Expected - branchTarget(rcc::MachineInstr &, rcc::MachineFunction &, - const rcc::TargetDescription &) const override { - return static_cast(nullptr); - } - - [[nodiscard]] bool isBranchOffsetInRange(const rcc::MachineInstr &, - std::int64_t) const noexcept override { - return true; - } - - [[nodiscard]] rcc::Expected relaxBranch(rcc::MachineInstr &, std::int64_t, - rcc::MachineFunction &, - const rcc::TargetDescription &) const override { - return false; - } - -private: - bool RejectCopies = false; -}; - -struct FunctionFixture final { - std::unique_ptr Function; - std::vector 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 -createVReg(rcc::MachineFunction &Function, rcc::LLT Type, rcc::RegisterBankID Bank, - rcc::RegisterClassID Class, std::uint8_t TargetFlags = 0, - std::optional 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 -buildRegisterInstruction(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, - rcc::MachineBasicBlock &Block, rcc::Opcode Opcode, - std::span Defs, std::span 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 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 -buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, - rcc::MachineBasicBlock &Block, rcc::Register Destination, - std::span> 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(); -} - -[[nodiscard]] rcc::Expected setSelectedSSAProperties(rcc::MachineFunction &Function, - const rcc::TargetDescription &Target) { - auto Rebuilt = rcc::rebuildMachineLiveness(Function, Target); - if (!Rebuilt) - return std::unexpected(Rebuilt.error()); - for (rcc::MachineFunctionProperty Property : - {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness, - rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected, - rcc::MachineFunctionProperty::Selected}) { - Function.properties().set(Property); - } - return {}; -} - -[[nodiscard]] rcc::Expected runPHIElimination(rcc::MachineFunction &Function, - const rcc::TargetDescription &Target, - const rcc::TargetInstrInfo &Info) { - rcc::MachinePassManager Pipeline; - auto Added = Pipeline.addPass(std::make_unique(Info)); - if (!Added) - return std::unexpected(Added.error()); - rcc::MachineAnalysisManager Analyses; - return Pipeline.run(Function, Target, Analyses); -} - -[[nodiscard]] std::vector linkedInstructions(rcc::MachineBasicBlock &Block) { - std::vector Result; - for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; - Instruction = Instruction->next()) { - Result.push_back(Instruction); - } - return Result; -} - -[[nodiscard]] std::vector -instructionsWithOpcode(rcc::MachineFunction &Function, rcc::Opcode Opcode) { - std::vector 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 TestInstrInfo &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{*InitA, &Preheader}, - std::pair{*DestinationB, &Backedge}}; - const std::array IncomingB{ - std::pair{*InitB, &Preheader}, - std::pair{*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"); - auto InitialLiveness = setSelectedSSAProperties(Function, Target); - Context.expect(InitialLiveness.has_value(), "parallel PHI liveness rebuild must succeed"); - if (!InitialLiveness) - return; - - 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(); - const rcc::Register *FreshB = HeaderInstructions[2]->operandAt(1)->getIf(); - 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 TestInstrInfo &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::fromPhysical(G0), &From}, - std::pair{*OtherValue, &Other}}; - Context.expect(buildPhi(Function, Target, Merge, *Destination, Incoming).has_value(), - "critical-edge PHI must be built"); - const std::array G1Use{rcc::Register::fromPhysical(G1)}; - Context.expect(buildRegisterInstruction(Function, Target, Merge, testOpcode(UseOpcode), {}, G1Use) - .has_value(), - "merge block must consume its inherited physical live-in"); - auto InitialLiveness = setSelectedSSAProperties(Function, Target); - Context.expect(InitialLiveness.has_value(), "critical-edge PHI liveness rebuild must succeed"); - if (!InitialLiveness) - return; - - 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(); - 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 TestInstrInfo &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{*Source, Fixture.Blocks[0]}}; - if (!buildPhi(*Fixture.Function, Target, *Fixture.Blocks[1], *Destination, Incoming, {}, 0, - {rcc::RegisterOperandFlag::Undef})) { - return Fixture; - } - Context.expect(setSelectedSSAProperties(*Fixture.Function, Target).has_value(), - "undef PHI liveness rebuild must succeed"); - 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(); - TestInstrInfo 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 TestInstrInfo &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 Other = std::nullopt) { - rcc::MachineIRBuilder Builder(Function, Target); - auto Point = Builder.setInsertPoint(Block); - if (!Point) - return rcc::Expected{std::unexpected(Point.error())}; - auto Pending = Builder.buildInstr(Opcode); - if (!Pending) - return rcc::Expected{std::unexpected(Pending.error())}; - auto AddedDef = Pending->addDef(Def); - if (!AddedDef) - return rcc::Expected{std::unexpected(AddedDef.error())}; - auto AddedUse = Pending->addUse(Use, {rcc::RegisterOperandFlag::Kill}); - if (!AddedUse) - return rcc::Expected{std::unexpected(AddedUse.error())}; - if (Other) { - auto AddedOther = Pending->addUse(*Other); - if (!AddedOther) - return rcc::Expected{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"); - - auto InitialLiveness = setSelectedSSAProperties(Function, Target); - Context.expect(InitialLiveness.has_value(), "two-address liveness rebuild must succeed"); - if (!InitialLiveness) - return; - Function.properties().set(rcc::MachineFunctionProperty::NoPHIs); - rcc::MachinePassManager Pipeline; - Context.expect(Pipeline.addPass(std::make_unique(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"); - const bool HasKill = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) { - return MI->parent() != nullptr && - std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) { - return Operand.registerFlags().has(rcc::RegisterOperandFlag::Kill); - }); - }); - const bool HasDead = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) { - return MI->parent() != nullptr && - std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) { - return Operand.registerFlags().has(rcc::RegisterOperandFlag::Dead); - }); - }); - Context.expect(HasKill && HasDead, - "two-address rewrite must rebuild precise kill and 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::makeUnexpected( - rcc::ErrorCode::InternalError, "failed to build atomicity fixture")}; - Context.expect(AtomicInstruction.has_value(), - "two-address atomicity tied instruction must build"); - if (!AtomicInstruction) - return; - auto AtomicLiveness = setSelectedSSAProperties(*AtomicFixture.Function, Target); - Context.expect(AtomicLiveness.has_value(), "two-address atomicity liveness rebuild must succeed"); - if (!AtomicLiveness) - return; - 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(); - - TestInstrInfo 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(); - TestInstrInfo 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/PHIEliminationTest.cpp b/backend/unittests/CodeGen/PHIEliminationTest.cpp new file mode 100644 index 0000000..00668e4 --- /dev/null +++ b/backend/unittests/CodeGen/PHIEliminationTest.cpp @@ -0,0 +1,479 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/PHIElimination.h" + +#include "SSAExitTestSupport.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/MachineVerifier.h" + +#include +#include +#include + +namespace { + +using namespace rcc::test::ssa; + +[[nodiscard]] rcc::Expected 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 +buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Destination, + std::span> 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(); +} + +[[nodiscard]] rcc::Expected runPHIElimination(rcc::MachineFunction &Function, + const rcc::TargetDescription &Target, + const rcc::TargetInstrInfo &Info) { + rcc::MachinePassManager Pipeline; + auto Added = Pipeline.addPass(std::make_unique(Info)); + if (!Added) + return std::unexpected(Added.error()); + rcc::MachineAnalysisManager Analyses; + return Pipeline.run(Function, Target, Analyses); +} + +[[nodiscard]] std::vector linkedInstructions(rcc::MachineBasicBlock &Block) { + std::vector Result; + for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + 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 TestInstrInfo &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{*InitA, &Preheader}, + std::pair{*DestinationB, &Backedge}}; + const std::array IncomingB{ + std::pair{*InitB, &Preheader}, + std::pair{*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"); + auto InitialLiveness = setSelectedSSAProperties(Function, Target); + Context.expect(InitialLiveness.has_value(), "parallel PHI liveness rebuild must succeed"); + if (!InitialLiveness) + return; + + 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(); + const rcc::Register *FreshB = HeaderInstructions[2]->operandAt(1)->getIf(); + 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 TestInstrInfo &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::fromPhysical(G0), &From}, + std::pair{*OtherValue, &Other}}; + Context.expect(buildPhi(Function, Target, Merge, *Destination, Incoming).has_value(), + "critical-edge PHI must be built"); + const std::array G1Use{rcc::Register::fromPhysical(G1)}; + Context.expect(buildRegisterInstruction(Function, Target, Merge, testOpcode(UseOpcode), {}, G1Use) + .has_value(), + "merge block must consume its inherited physical live-in"); + auto InitialLiveness = setSelectedSSAProperties(Function, Target); + Context.expect(InitialLiveness.has_value(), "critical-edge PHI liveness rebuild must succeed"); + if (!InitialLiveness) + return; + + 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(); + 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 TestInstrInfo &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{*Source, Fixture.Blocks[0]}}; + if (!buildPhi(*Fixture.Function, Target, *Fixture.Blocks[1], *Destination, Incoming, {}, 0, + {rcc::RegisterOperandFlag::Undef})) { + return Fixture; + } + Context.expect(setSelectedSSAProperties(*Fixture.Function, Target).has_value(), + "undef PHI liveness rebuild must succeed"); + 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(); + TestInstrInfo 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"); +} + +void testMalformedPHIs(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"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "PHI-elimination TestTarget must be created"); + if (!Target) + return Context.result(); + TestInstrInfo Info; + testParallelPHIsAndPlacement(Context, *Target, Info); + testCriticalEdgeAndPhysicalLiveIn(Context, *Target, Info); + testUndefAndFailureAtomicity(Context, *Target, Info); + testMalformedPHIs(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/SSAExitTestSupport.h b/backend/unittests/CodeGen/SSAExitTestSupport.h new file mode 100644 index 0000000..a5eeff1 --- /dev/null +++ b/backend/unittests/CodeGen/SSAExitTestSupport.h @@ -0,0 +1,444 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +// This private test header has no stable include-root-relative guard name. +// NOLINTNEXTLINE(llvm-header-guard) +#ifndef RCC_BACKEND_SSA_EXIT_TEST_SUPPORT_H +#define RCC_BACKEND_SSA_EXIT_TEST_SUPPORT_H + +#include "Target/TestTarget.h" +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetInstrInfo.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc::test::ssa { + +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]] inline rcc::Opcode testOpcode(std::uint32_t Value) { + return rcc::Opcode::fromValue(Value); +} + +[[nodiscard]] inline 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]] inline rcc::OperandDescriptor blockOperand() { + rcc::OperandDescriptor Result; + Result.Kinds = {rcc::MachineOperand::Kind::BasicBlock}; + return Result; +} + +[[nodiscard]] inline 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]] inline rcc::Expected createTarget() { + std::vector Descriptors; + std::vector 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 TestInstrInfo final : public rcc::TargetInstrInfo { +public: + explicit TestInstrInfo(bool RejectCopies = false) : RejectCopies(RejectCopies) {} + + [[nodiscard]] rcc::Expected + analyzeBranch(rcc::MachineBasicBlock &, rcc::MachineFunction &, + const rcc::TargetDescription &) const override { + return rcc::MachineBranchAnalysis{}; + } + + [[nodiscard]] rcc::Expected + reverseBranchCondition(rcc::MachineInstr &, rcc::MachineBasicBlock &, rcc::MachineFunction &, + const rcc::TargetDescription &) const override { + return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test target has no branch reversal"); + } + + [[nodiscard]] rcc::Expected removeBranch(rcc::MachineInstr &, rcc::MachineFunction &, + const rcc::TargetDescription &) const override { + return rcc::makeUnexpected(rcc::ErrorCode::Unsupported, "test target has no branch removal"); + } + + [[nodiscard]] rcc::Expected + 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 + 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(); + 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 + insertBranch(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 *Built; + } + + [[nodiscard]] rcc::Expected + 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 + 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; + } + + [[nodiscard]] rcc::Expected + instructionSize(const rcc::MachineInstr &, const rcc::MachineFunction &, + const rcc::TargetDescription &) const override { + return 4; + } + + [[nodiscard]] rcc::Expected + branchTarget(rcc::MachineInstr &, rcc::MachineFunction &, + const rcc::TargetDescription &) const override { + return static_cast(nullptr); + } + + [[nodiscard]] bool isBranchOffsetInRange(const rcc::MachineInstr &, + std::int64_t) const noexcept override { + return true; + } + + [[nodiscard]] rcc::Expected relaxBranch(rcc::MachineInstr &, std::int64_t, + rcc::MachineFunction &, + const rcc::TargetDescription &) const override { + return false; + } + +private: + bool RejectCopies = false; +}; + +struct FunctionFixture final { + std::unique_ptr Function; + std::vector Blocks; +}; + +[[nodiscard]] inline 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]] inline rcc::Expected +createVReg(rcc::MachineFunction &Function, rcc::LLT Type, rcc::RegisterBankID Bank, + rcc::RegisterClassID Class, std::uint8_t TargetFlags = 0, + std::optional 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]] inline rcc::Expected +buildRegisterInstruction(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Opcode Opcode, + std::span Defs, std::span 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]] inline rcc::Expected +setSelectedSSAProperties(rcc::MachineFunction &Function, const rcc::TargetDescription &Target) { + auto Rebuilt = rcc::rebuildMachineLiveness(Function, Target); + if (!Rebuilt) + return std::unexpected(Rebuilt.error()); + for (rcc::MachineFunctionProperty Property : + {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness, + rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected, + rcc::MachineFunctionProperty::Selected}) { + Function.properties().set(Property); + } + return {}; +} + +[[nodiscard]] inline std::vector +instructionsWithOpcode(rcc::MachineFunction &Function, rcc::Opcode Opcode) { + std::vector 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; +} + +} // namespace rcc::test::ssa + +#endif // RCC_BACKEND_SSA_EXIT_TEST_SUPPORT_H diff --git a/backend/unittests/CodeGen/TwoAddressInstructionPassTest.cpp b/backend/unittests/CodeGen/TwoAddressInstructionPassTest.cpp new file mode 100644 index 0000000..6853a36 --- /dev/null +++ b/backend/unittests/CodeGen/TwoAddressInstructionPassTest.cpp @@ -0,0 +1,268 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/TwoAddressInstructionPass.h" + +#include "SSAExitTestSupport.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/MachineVerifier.h" + +#include +#include +#include + +namespace { + +using namespace rcc::test::ssa; + +void testTwoAddressAndSubregisterPseudos(TestContext &Context, const rcc::TargetDescription &Target, + const TestInstrInfo &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 Other = std::nullopt) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return rcc::Expected{std::unexpected(Point.error())}; + auto Pending = Builder.buildInstr(Opcode); + if (!Pending) + return rcc::Expected{std::unexpected(Pending.error())}; + auto AddedDef = Pending->addDef(Def); + if (!AddedDef) + return rcc::Expected{std::unexpected(AddedDef.error())}; + auto AddedUse = Pending->addUse(Use, {rcc::RegisterOperandFlag::Kill}); + if (!AddedUse) + return rcc::Expected{std::unexpected(AddedUse.error())}; + if (Other) { + auto AddedOther = Pending->addUse(*Other); + if (!AddedOther) + return rcc::Expected{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"); + + auto InitialLiveness = setSelectedSSAProperties(Function, Target); + Context.expect(InitialLiveness.has_value(), "two-address liveness rebuild must succeed"); + if (!InitialLiveness) + return; + Function.properties().set(rcc::MachineFunctionProperty::NoPHIs); + rcc::MachinePassManager Pipeline; + Context.expect( + Pipeline.addPass(std::make_unique(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(), + "TwoAddressInstructionPass 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"); + const bool HasKill = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) { + return MI->parent() != nullptr && + std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) { + return Operand.registerFlags().has(rcc::RegisterOperandFlag::Kill); + }); + }); + const bool HasDead = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) { + return MI->parent() != nullptr && + std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) { + return Operand.registerFlags().has(rcc::RegisterOperandFlag::Dead); + }); + }); + Context.expect(HasKill && HasDead, + "two-address rewrite must rebuild precise kill and 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::makeUnexpected( + rcc::ErrorCode::InternalError, "failed to build atomicity fixture")}; + Context.expect(AtomicInstruction.has_value(), + "two-address atomicity tied instruction must build"); + if (!AtomicInstruction) + return; + auto AtomicLiveness = setSelectedSSAProperties(*AtomicFixture.Function, Target); + Context.expect(AtomicLiveness.has_value(), "two-address atomicity liveness rebuild must succeed"); + if (!AtomicLiveness) + return; + 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(); + + TestInstrInfo RejectingInfo(true); + rcc::MachineAnalysisManager AtomicAnalyses; + rcc::TwoAddressInstructionPass 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"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "two-address TestTarget must be created"); + if (!Target) + return Context.result(); + TestInstrInfo Info; + testTwoAddressAndSubregisterPseudos(Context, *Target, Info); + return Context.result(); +} diff --git a/backend/unittests/Target/RISCVSSAExitTest.cpp b/backend/unittests/Target/RISCVSSAExitTest.cpp index eafb5a0..3f81d1d 100644 --- a/backend/unittests/Target/RISCVSSAExitTest.cpp +++ b/backend/unittests/Target/RISCVSSAExitTest.cpp @@ -11,8 +11,8 @@ #include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachinePass.h" -#include "rcc/CodeGen/MachineSSAExit.h" #include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/CodeGen/PHIElimination.h" #include "rcc/Target/RISCV/RISCVTarget.h" #include -- cgit v1.2.3