diff options
Diffstat (limited to 'backend')
| -rw-r--r-- | backend/include/rcc/CodeGen/MachineFunctionCloner.h | 49 | ||||
| -rw-r--r-- | backend/lib/CodeGen/CMakeLists.txt | 4 | ||||
| -rw-r--r-- | backend/lib/CodeGen/MachineFunctionCloner.cpp | 373 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/CMakeLists.txt | 18 | ||||
| -rw-r--r-- | backend/unittests/CodeGen/MachineFunctionClonerTest.cpp | 441 |
5 files changed, 885 insertions, 0 deletions
diff --git a/backend/include/rcc/CodeGen/MachineFunctionCloner.h b/backend/include/rcc/CodeGen/MachineFunctionCloner.h new file mode 100644 index 0000000..3abdf78 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineFunctionCloner.h @@ -0,0 +1,49 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEFUNCTIONCLONER_H +#define RCC_CODEGEN_MACHINEFUNCTIONCLONER_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/CodeGen/StableID.h" +#include "rcc/Support/Error.h" + +#include <memory> +#include <optional> +#include <string> +#include <unordered_map> + +namespace rcc { + +class InstructionSet; +class MachineFunction; + +struct MachineFunctionCloneOptions final { + MachineFunctionStableID NewStableID; + std::optional<std::string> NewName; +}; + +struct MachineFunctionCloneResult final { + MachineFunctionCloneResult(); + MachineFunctionCloneResult(const MachineFunctionCloneResult &) = delete; + MachineFunctionCloneResult &operator=(const MachineFunctionCloneResult &) = delete; + MachineFunctionCloneResult(MachineFunctionCloneResult &&) noexcept; + MachineFunctionCloneResult &operator=(MachineFunctionCloneResult &&) noexcept; + ~MachineFunctionCloneResult(); + + std::unique_ptr<MachineFunction> ClonedFunction; + std::unordered_map<MachineBlockStableID, MachineBlockStableID> BlockStableIDs; + std::unordered_map<MachineInstrStableID, MachineInstrStableID> InstructionStableIDs; + std::unordered_map<Register, Register> VirtualRegisters; + std::unordered_map<FrameIndex, FrameIndex> FrameIndices; + std::unordered_map<ConstantPoolIndex, ConstantPoolIndex> ConstantPoolIndices; + std::unordered_map<JumpTableIndex, JumpTableIndex> JumpTableIndices; +}; + +[[nodiscard]] Expected<MachineFunctionCloneResult> +cloneMachineFunction(const MachineFunction &Source, const InstructionSet &Instructions, + MachineFunctionCloneOptions Options); + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEFUNCTIONCLONER_H diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 273ef9c..d19aaba 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -7,6 +7,7 @@ set( MachineBasicBlock.cpp MachineCFGUpdater.cpp MachineFunction.cpp + MachineFunctionCloner.cpp MachineIRTypes.cpp MachineIRBuilder.cpp MachineInstr.cpp @@ -25,6 +26,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlock.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCFGUpdater.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunction.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionCloner.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineIRTypes.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineIRBuilder.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineInstr.h" @@ -72,6 +74,7 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionCloner.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilder.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" @@ -90,6 +93,7 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionCloner.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilder.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" diff --git a/backend/lib/CodeGen/MachineFunctionCloner.cpp b/backend/lib/CodeGen/MachineFunctionCloner.cpp new file mode 100644 index 0000000..d452546 --- /dev/null +++ b/backend/lib/CodeGen/MachineFunctionCloner.cpp @@ -0,0 +1,373 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineFunctionCloner.h" + +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/MachineVerifier.h" + +#include <cstddef> +#include <cstdint> +#include <memory> +#include <optional> +#include <string> +#include <unordered_map> +#include <utility> + +namespace rcc { +namespace { + +struct CloneState final { + const MachineFunction &Source; + MachineFunction &Destination; + MachineFunctionCloneResult &Result; + std::unordered_map<const MachineBasicBlock *, MachineBasicBlock *> Blocks; + std::unordered_map<const MachineInstr *, MachineInstr *> Instructions; + std::unordered_map<const MachineMemOperand *, const MachineMemOperand *> MemOperands; +}; + +[[nodiscard]] Expected<MachineOperand> cloneOperand(const MachineOperand &SourceOperand, + CloneState &State) { + switch (SourceOperand.kind()) { + case MachineOperand::Kind::Register: { + const Register *SourceReg = SourceOperand.getIf<Register>(); + if (SourceReg == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "source register operand has inconsistent storage"); + } + Register DestinationReg = *SourceReg; + if (SourceReg->isVirtual()) { + const auto Position = State.Result.VirtualRegisters.find(*SourceReg); + if (Position == State.Result.VirtualRegisters.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "source operand references an unmapped virtual register"); + } + DestinationReg = Position->second; + } + + MachineOperand Result = SourceOperand.cloneDetached(); + auto SetResult = Result.setRegister(DestinationReg); + if (!SetResult) + return std::unexpected(SetResult.error()); + return Result; + } + case MachineOperand::Kind::BasicBlock: { + const auto *SourceBlock = SourceOperand.getIf<BasicBlockOperand>(); + if (SourceBlock == nullptr || SourceBlock->Block == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "source basic-block operand is invalid"); + } + const auto Position = State.Blocks.find(SourceBlock->Block); + if (Position == State.Blocks.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "source basic-block operand is not in live layout"); + } + return MachineOperand::basicBlock(*Position->second, SourceOperand.targetFlags()); + } + case MachineOperand::Kind::BlockAddress: { + const auto *Address = SourceOperand.getIf<BlockAddressOperand>(); + if (Address == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "source block-address operand is invalid"); + } + std::string FunctionName = Address->FunctionName; + if (FunctionName == State.Source.name()) + FunctionName = std::string(State.Destination.name()); + return MachineOperand::blockAddress(std::move(FunctionName), Address->BlockName, + Address->Offset, SourceOperand.targetFlags()); + } + case MachineOperand::Kind::FrameIndex: { + const auto *Frame = SourceOperand.getIf<FrameIndexOperand>(); + if (Frame == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "source frame-index operand is invalid"); + } + State.Result.FrameIndices.emplace(Frame->Index, Frame->Index); + return SourceOperand.cloneDetached(); + } + case MachineOperand::Kind::ConstantPoolIndex: { + const auto *Constant = SourceOperand.getIf<ConstantPoolOperand>(); + if (Constant == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "source constant-pool operand is invalid"); + } + State.Result.ConstantPoolIndices.emplace(Constant->Index, Constant->Index); + return SourceOperand.cloneDetached(); + } + case MachineOperand::Kind::JumpTableIndex: { + const auto *JumpTable = SourceOperand.getIf<JumpTableOperand>(); + if (JumpTable == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "source jump-table operand is invalid"); + } + State.Result.JumpTableIndices.emplace(JumpTable->Index, JumpTable->Index); + return SourceOperand.cloneDetached(); + } + case MachineOperand::Kind::Immediate: + case MachineOperand::Kind::FloatingImmediate: + case MachineOperand::Kind::GlobalSymbol: + case MachineOperand::Kind::ExternalSymbol: + case MachineOperand::Kind::RegisterMask: + case MachineOperand::Kind::Metadata: + case MachineOperand::Kind::TargetIndex: + case MachineOperand::Kind::MCSymbol: + return SourceOperand.cloneDetached(); + case MachineOperand::Kind::Count: + return makeUnexpected(ErrorCode::VerificationError, "source operand has an invalid kind"); + } + return makeUnexpected(ErrorCode::InternalError, "source operand kind is not handled"); +} + +void recordMemoryIndexMappings(const MachineMemOperandDesc &Description, + MachineFunctionCloneResult &Result) { + if (const auto Frame = Description.Base.frameIndex()) + Result.FrameIndices.emplace(*Frame, *Frame); + if (const auto Constant = Description.Base.constantPoolIndex()) + Result.ConstantPoolIndices.emplace(*Constant, *Constant); + if (const auto JumpTable = Description.Base.jumpTableIndex()) + Result.JumpTableIndices.emplace(*JumpTable, *JumpTable); +} + +[[nodiscard]] Expected<const MachineMemOperand *> +cloneMemOperand(const MachineMemOperand &SourceOperand, CloneState &State) { + const auto Existing = State.MemOperands.find(&SourceOperand); + if (Existing != State.MemOperands.end()) + return Existing->second; + + MachineMemOperandDesc Description = SourceOperand.description(); + recordMemoryIndexMappings(Description, State.Result); + auto DestinationOperand = State.Destination.createMemOperand(std::move(Description)); + if (!DestinationOperand) + return std::unexpected(DestinationOperand.error()); + State.MemOperands.emplace(&SourceOperand, *DestinationOperand); + return *DestinationOperand; +} + +[[nodiscard]] Expected<void> cloneVirtualRegisters(CloneState &State) { + const auto SourceRegisters = State.Source.registerInfo().virtualRegisters(); + for (std::size_t Index = 0; Index < SourceRegisters.size(); ++Index) { + const VirtualRegisterInfo &SourceInfo = SourceRegisters[Index]; + if (SourceInfo.IsTombstone) + continue; + + auto SourceReg = Register::makeVirtual(Index); + if (!SourceReg) + return std::unexpected(SourceReg.error()); + Expected<Register> DestinationReg = + SourceInfo.Type ? State.Destination.registerInfo().createVirtualRegister(*SourceInfo.Type) + : State.Destination.registerInfo().createVirtualRegister(); + if (!DestinationReg) + return std::unexpected(DestinationReg.error()); + + if (SourceInfo.Bank) { + auto SetResult = + State.Destination.registerInfo().setRegisterBank(*DestinationReg, *SourceInfo.Bank); + if (!SetResult) + return std::unexpected(SetResult.error()); + } + if (SourceInfo.RegClass) { + auto SetResult = + State.Destination.registerInfo().setRegisterClass(*DestinationReg, *SourceInfo.RegClass); + if (!SetResult) + return std::unexpected(SetResult.error()); + } + for (const PhysicalRegister Hint : SourceInfo.AllocationHints) { + auto AddResult = State.Destination.registerInfo().addAllocationHint(*DestinationReg, Hint); + if (!AddResult) + return std::unexpected(AddResult.error()); + } + State.Result.VirtualRegisters.emplace(*SourceReg, *DestinationReg); + } + return {}; +} + +[[nodiscard]] Expected<void> cloneRegisterConfiguration(CloneState &State) { + for (const PhysicalRegisterLiveIn &LiveIn : State.Source.registerInfo().liveIns()) { + std::optional<Register> Initial; + if (LiveIn.InitialVirtualRegister) { + const auto Position = State.Result.VirtualRegisters.find(*LiveIn.InitialVirtualRegister); + if (Position == State.Result.VirtualRegisters.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "source live-in references an unmapped virtual register"); + } + Initial = Position->second; + } + auto AddResult = State.Destination.registerInfo().addLiveIn(LiveIn.PhysReg, Initial); + if (!AddResult) + return std::unexpected(AddResult.error()); + } + for (const PhysicalRegister Reg : State.Source.registerInfo().reservedRegisters()) { + auto ReserveResult = State.Destination.registerInfo().reservePhysicalRegister(Reg); + if (!ReserveResult) + return std::unexpected(ReserveResult.error()); + } + return {}; +} + +[[nodiscard]] Expected<void> cloneBlocks(CloneState &State) { + for (const MachineBasicBlock *SourceBlock = State.Source.firstBlock(); SourceBlock != nullptr; + SourceBlock = SourceBlock->next()) { + auto DestinationBlock = State.Destination.createBasicBlock(); + if (!DestinationBlock) + return std::unexpected(DestinationBlock.error()); + auto AppendResult = State.Destination.appendBlock(**DestinationBlock); + if (!AppendResult) + return std::unexpected(AppendResult.error()); + State.Blocks.emplace(SourceBlock, *DestinationBlock); + State.Result.BlockStableIDs.emplace(SourceBlock->stableID(), (*DestinationBlock)->stableID()); + + for (const MachineBasicBlockLiveIn &LiveIn : SourceBlock->liveIns()) { + auto AddResult = (*DestinationBlock)->addLiveIn(LiveIn.PhysReg, LiveIn.Lanes); + if (!AddResult) + return std::unexpected(AddResult.error()); + } + } + return {}; +} + +[[nodiscard]] Expected<void> cloneInstructions(CloneState &State) { + for (const MachineBasicBlock *SourceBlock = State.Source.firstBlock(); SourceBlock != nullptr; + SourceBlock = SourceBlock->next()) { + const auto DestinationBlockPosition = State.Blocks.find(SourceBlock); + if (DestinationBlockPosition == State.Blocks.end()) { + return makeUnexpected(ErrorCode::InternalError, + "source block was not mapped before instruction cloning"); + } + MachineBasicBlock *DestinationBlock = DestinationBlockPosition->second; + for (const MachineInstr *SourceInstruction = SourceBlock->firstInstruction(); + SourceInstruction != nullptr; SourceInstruction = SourceInstruction->next()) { + auto DestinationInstruction = + State.Destination.createInstruction(SourceInstruction->opcode()); + if (!DestinationInstruction) + return std::unexpected(DestinationInstruction.error()); + MachineInstr *NewInstruction = *DestinationInstruction; + State.Instructions.emplace(SourceInstruction, NewInstruction); + State.Result.InstructionStableIDs.emplace(SourceInstruction->stableID(), + NewInstruction->stableID()); + NewInstruction->reserveOperands(SourceInstruction->operandCount()); + + for (const MachineOperand &SourceOperand : SourceInstruction->operands()) { + auto DestinationOperand = cloneOperand(SourceOperand, State); + if (!DestinationOperand) + return std::unexpected(DestinationOperand.error()); + auto AddResult = NewInstruction->addOperand(std::move(*DestinationOperand)); + if (!AddResult) + return std::unexpected(AddResult.error()); + } + + const auto SourceOperands = SourceInstruction->operands(); + for (std::size_t Index = 0; Index < SourceOperands.size(); ++Index) { + const auto Tied = SourceOperands[Index].tiedOperandIndex(); + if (!Tied || Index > *Tied) + continue; + const std::size_t DefIndex = SourceOperands[Index].isDef() ? Index : *Tied; + const std::size_t UseIndex = SourceOperands[Index].isDef() ? *Tied : Index; + auto TieResult = NewInstruction->tieOperands(DefIndex, UseIndex); + if (!TieResult) + return std::unexpected(TieResult.error()); + } + + for (const MachineMemOperand *SourceMemOperand : SourceInstruction->memOperands()) { + auto DestinationMemOperand = cloneMemOperand(*SourceMemOperand, State); + if (!DestinationMemOperand) + return std::unexpected(DestinationMemOperand.error()); + auto AddResult = NewInstruction->addMemOperand(**DestinationMemOperand); + if (!AddResult) + return std::unexpected(AddResult.error()); + } + + NewInstruction->setFlags(SourceInstruction->flags()); + if (SourceInstruction->sourceLocation()) { + NewInstruction->setSourceLocation(*SourceInstruction->sourceLocation()); + } + if (SourceInstruction->origin()) + NewInstruction->setOrigin(*SourceInstruction->origin()); + + auto AppendResult = DestinationBlock->appendInstruction(*NewInstruction); + if (!AppendResult) + return std::unexpected(AppendResult.error()); + } + } + return {}; +} + +[[nodiscard]] Expected<void> cloneCFG(CloneState &State) { + MachineCFGUpdater Updater = State.Destination.cfgUpdater(); + for (const MachineBasicBlock *SourceBlock = State.Source.firstBlock(); SourceBlock != nullptr; + SourceBlock = SourceBlock->next()) { + const auto DestinationBlockPosition = State.Blocks.find(SourceBlock); + if (DestinationBlockPosition == State.Blocks.end()) { + return makeUnexpected(ErrorCode::InternalError, + "source block was not mapped before CFG cloning"); + } + MachineBasicBlock *DestinationBlock = DestinationBlockPosition->second; + for (const MachineSuccessor &Successor : SourceBlock->successors()) { + const auto Target = State.Blocks.find(Successor.Block); + if (Target == State.Blocks.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "source CFG references a detached block"); + } + auto AddResult = + Updater.addSuccessor(*DestinationBlock, *Target->second, Successor.Probability); + if (!AddResult) + return std::unexpected(AddResult.error()); + } + } + return {}; +} + +} // namespace + +MachineFunctionCloneResult::MachineFunctionCloneResult() = default; +MachineFunctionCloneResult::MachineFunctionCloneResult(MachineFunctionCloneResult &&) noexcept = + default; +MachineFunctionCloneResult & +MachineFunctionCloneResult::operator=(MachineFunctionCloneResult &&) noexcept = default; +MachineFunctionCloneResult::~MachineFunctionCloneResult() = default; + +Expected<MachineFunctionCloneResult> cloneMachineFunction(const MachineFunction &Source, + const InstructionSet &Instructions, + MachineFunctionCloneOptions Options) { + auto SourceVerification = MachineVerifier::verify(Source, Instructions); + if (!SourceVerification) + return std::unexpected(SourceVerification.error()); + if (!Options.NewStableID.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, "clone function StableID must be valid"); + } + + std::string Name = Options.NewName ? std::move(*Options.NewName) : std::string(Source.name()); + auto Destination = MachineFunction::create(std::move(Name), Options.NewStableID); + if (!Destination) + return std::unexpected(Destination.error()); + + MachineFunctionCloneResult Result; + Result.ClonedFunction = std::move(*Destination); + CloneState State{Source, *Result.ClonedFunction, Result, {}, {}, {}}; + + auto VRegResult = cloneVirtualRegisters(State); + if (!VRegResult) + return std::unexpected(VRegResult.error()); + auto RegisterResult = cloneRegisterConfiguration(State); + if (!RegisterResult) + return std::unexpected(RegisterResult.error()); + auto BlockResult = cloneBlocks(State); + if (!BlockResult) + return std::unexpected(BlockResult.error()); + auto InstructionResult = cloneInstructions(State); + if (!InstructionResult) + return std::unexpected(InstructionResult.error()); + auto CFGResult = cloneCFG(State); + if (!CFGResult) + return std::unexpected(CFGResult.error()); + + Result.ClonedFunction->properties() = Source.properties(); + auto DestinationVerification = MachineVerifier::verify(*Result.ClonedFunction, Instructions); + if (!DestinationVerification) + return std::unexpected(DestinationVerification.error()); + return Result; +} + +} // namespace rcc diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt index 6f17fc0..650cfa9 100644 --- a/backend/unittests/CodeGen/CMakeLists.txt +++ b/backend/unittests/CodeGen/CMakeLists.txt @@ -4,6 +4,7 @@ set( RCCBackendCodeGenTestSources CoreTypesTest.cpp InstructionDescriptorTest.cpp + MachineFunctionClonerTest.cpp MachineIRBuilderTest.cpp MachineIRCoreTest.cpp MachineVerifierTest.cpp @@ -31,6 +32,21 @@ add_test( COMMAND RCCBackendCodeGenInstructionDescriptorTests ) +add_executable( + RCCBackendCodeGenMachineFunctionClonerTests + MachineFunctionClonerTest.cpp +) +rcc_backend_configure_target(RCCBackendCodeGenMachineFunctionClonerTests) +target_link_libraries( + RCCBackendCodeGenMachineFunctionClonerTests + PRIVATE RCCBackend::CodeGen +) + +add_test( + NAME RCCBackend.CodeGen.MachineFunctionCloner + COMMAND RCCBackendCodeGenMachineFunctionClonerTests +) + add_executable(RCCBackendCodeGenMachineIRBuilderTests MachineIRBuilderTest.cpp) rcc_backend_configure_target(RCCBackendCodeGenMachineIRBuilderTests) target_link_libraries( @@ -76,6 +92,7 @@ add_test( rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptorTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionClonerTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilderTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp" @@ -84,6 +101,7 @@ rcc_backend_register_format_files( rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptorTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionClonerTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilderTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp" diff --git a/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp b/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp new file mode 100644 index 0000000..90e847b --- /dev/null +++ b/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp @@ -0,0 +1,441 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineFunctionCloner.h" + +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineFunctionProperties.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/MachineVerifier.h" + +#include <algorithm> +#include <cstdint> +#include <iostream> +#include <memory> +#include <optional> +#include <string> +#include <string_view> +#include <utility> +#include <vector> + +namespace { + +constexpr std::uint32_t NopOpcode = 1; +constexpr std::uint32_t DefOpcode = 2; +constexpr std::uint32_t BranchOpcode = 3; +constexpr std::uint32_t CopyOpcode = 4; +constexpr std::uint32_t FrameOpcode = 5; +constexpr std::uint32_t BlockAddressOpcode = 6; +constexpr std::uint32_t LoadOpcode = 7; + +class TestContext final { +public: + void expect(bool Condition, std::string_view Message) { + if (Condition) + return; + std::cerr << Message << '\n'; + ++FailureCount; + } + + [[nodiscard]] int result() const noexcept { + return FailureCount == 0 ? 0 : 1; + } + +private: + int FailureCount = 0; +}; + +[[nodiscard]] rcc::OperandDescriptor registerDescriptor(rcc::RegisterOperandRole Role) { + rcc::OperandDescriptor Descriptor; + Descriptor.Kinds = {rcc::MachineOperand::Kind::Register}; + Descriptor.RegisterRole = Role; + return Descriptor; +} + +[[nodiscard]] rcc::InstructionDescriptor instructionDescriptor(std::uint32_t OpcodeValue, + std::string Name) { + rcc::InstructionDescriptor Descriptor; + Descriptor.InstructionOpcode = rcc::Opcode::fromValue(OpcodeValue); + Descriptor.Name = std::move(Name); + Descriptor.Flags = {rcc::InstructionFlag::ProducesCode}; + return Descriptor; +} + +[[nodiscard]] rcc::Expected<rcc::InstructionSet> createInstructionSet() { + auto Nop = instructionDescriptor(NopOpcode, "TEST_NOP"); + + auto Def = instructionDescriptor(DefOpcode, "TEST_DEF"); + Def.Operands.push_back(registerDescriptor(rcc::RegisterOperandRole::Def)); + Def.NumExplicitDefs = 1; + + auto Branch = instructionDescriptor(BranchOpcode, "TEST_BRANCH"); + rcc::OperandDescriptor Block; + Block.Kinds = {rcc::MachineOperand::Kind::BasicBlock}; + Branch.Operands.push_back(Block); + Branch.Flags.set(rcc::InstructionFlag::Branch); + Branch.Flags.set(rcc::InstructionFlag::Terminator); + + auto Copy = instructionDescriptor(CopyOpcode, "TEST_COPY"); + auto CopyDef = registerDescriptor(rcc::RegisterOperandRole::Def); + auto CopyUse = registerDescriptor(rcc::RegisterOperandRole::Use); + CopyDef.DefaultTiedOperand = 1; + CopyUse.DefaultTiedOperand = 0; + Copy.Operands.push_back(CopyDef); + Copy.Operands.push_back(CopyUse); + Copy.NumExplicitDefs = 1; + + auto Frame = instructionDescriptor(FrameOpcode, "TEST_FRAME"); + rcc::OperandDescriptor FrameIndex; + FrameIndex.Kinds = {rcc::MachineOperand::Kind::FrameIndex}; + Frame.Operands.push_back(FrameIndex); + + auto BlockAddress = instructionDescriptor(BlockAddressOpcode, "TEST_BLOCK_ADDRESS"); + rcc::OperandDescriptor Address; + Address.Kinds = {rcc::MachineOperand::Kind::BlockAddress}; + BlockAddress.Operands.push_back(Address); + + auto Load = instructionDescriptor(LoadOpcode, "TEST_LOAD"); + Load.Flags.set(rcc::InstructionFlag::MayLoad); + Load.RequiresMemoryOperands = true; + + std::vector<rcc::InstructionDescriptor> Descriptors; + Descriptors.push_back(std::move(Nop)); + Descriptors.push_back(std::move(Def)); + Descriptors.push_back(std::move(Branch)); + Descriptors.push_back(std::move(Copy)); + Descriptors.push_back(std::move(Frame)); + Descriptors.push_back(std::move(BlockAddress)); + Descriptors.push_back(std::move(Load)); + return rcc::InstructionSet::create(std::move(Descriptors)); +} + +[[nodiscard]] std::unique_ptr<rcc::MachineFunction> +createFunction(TestContext &Context, std::string Name, std::uint64_t ID) { + auto Function = + rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID)); + Context.expect(Function.has_value(), "machine function creation must succeed"); + if (!Function) + return nullptr; + return std::move(*Function); +} + +[[nodiscard]] rcc::MachineBasicBlock *createBlock(TestContext &Context, + rcc::MachineFunction &Function) { + auto Block = Function.createBasicBlock(); + Context.expect(Block.has_value(), "machine basic block creation must succeed"); + if (!Block) + return nullptr; + Context.expect(Function.appendBlock(**Block).has_value(), + "machine basic block linking must succeed"); + return *Block; +} + +[[nodiscard]] rcc::MachineMemOperandDesc loadDescription() { + rcc::MachineMemOperandDesc Description; + Description.Accesses = {rcc::MemoryAccessFlag::Load, rcc::MemoryAccessFlag::Dereferenceable}; + Description.Size = *rcc::MemorySize::fixed(8); + Description.Align = *rcc::Alignment::create(8); + Description.Base = rcc::MemoryBase::frameIndex(rcc::FrameIndex::fromValue(4)); + Description.Offset = -8; + return Description; +} + +[[nodiscard]] rcc::MachineInstr *findInstruction(rcc::MachineBasicBlock &Block, + std::uint32_t OpcodeValue) { + for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (Instruction->opcode() == rcc::Opcode::fromValue(OpcodeValue)) + return Instruction; + } + return nullptr; +} + +struct SourceFixture final { + rcc::MachineBasicBlock *Entry = nullptr; + rcc::MachineBasicBlock *Exit = nullptr; + rcc::Register Value; + rcc::Register CopyValue; + const rcc::MachineMemOperand *LoadMMO = nullptr; +}; + +[[nodiscard]] bool populateSource(TestContext &Context, rcc::MachineFunction &Function, + const rcc::InstructionSet &InstructionSet, + SourceFixture &Fixture) { + auto HistoricalBlock = Function.createBasicBlock(); + auto HistoricalInstruction = Function.createInstruction(rcc::Opcode::fromValue(NopOpcode)); + Context.expect(HistoricalBlock && HistoricalInstruction, "source arena history must be created"); + + auto Type = rcc::LLT::makeInteger(64); + auto Tombstone = Function.registerInfo().createVirtualRegister(*Type); + Context.expect(Tombstone && Function.registerInfo().eraseVirtualRegister(*Tombstone).has_value(), + "source vreg history must contain a tombstone"); + + Fixture.Entry = createBlock(Context, Function); + Fixture.Exit = createBlock(Context, Function); + if (Fixture.Entry == nullptr || Fixture.Exit == nullptr) + return false; + + auto Value = Function.registerInfo().createVirtualRegister(*Type); + auto CopyValue = Function.registerInfo().createVirtualRegister(*Type); + Context.expect(Value && CopyValue, "source live vregs must be created"); + if (!Value || !CopyValue) + return false; + Fixture.Value = *Value; + Fixture.CopyValue = *CopyValue; + + const auto Bank = rcc::RegisterBankID::fromValue(1); + const auto RegClass = rcc::RegisterClassID::fromValue(2); + for (const rcc::Register Reg : {Fixture.Value, Fixture.CopyValue}) { + Context.expect(Function.registerInfo().setRegisterBank(Reg, Bank).has_value() && + Function.registerInfo().setRegisterClass(Reg, RegClass).has_value(), + "source vreg constraints must be recorded"); + } + + const auto LiveIn = *rcc::PhysicalRegister::create(1); + const auto Reserved = *rcc::PhysicalRegister::create(2); + const auto Hint = *rcc::PhysicalRegister::create(5); + Context.expect(Function.registerInfo().addAllocationHint(Fixture.Value, Hint).has_value() && + Function.registerInfo().addLiveIn(LiveIn, Fixture.Value).has_value() && + Function.registerInfo().reservePhysicalRegister(Reserved).has_value() && + Fixture.Entry->addLiveIn(LiveIn).has_value(), + "source register configuration must be recorded"); + + rcc::MachineIRBuilder Builder(Function, InstructionSet); + Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(), + "source entry insertion point must be valid"); + auto Def = Builder.buildInstr(rcc::Opcode::fromValue(DefOpcode)); + Context.expect(Def && Def->addDef(Fixture.Value).has_value(), + "source definition must be assembled"); + if (!Def) + return false; + Context.expect(Def->setFlags({rcc::MachineInstrFlag::NoMerge}).has_value() && + Def->setSourceLocation({"source.mir", 9, 4, 2}).has_value() && + Def->setOrigin(rcc::OriginID::fromValue(77)).has_value() && Def->build(), + "source definition metadata must build"); + + auto Branch = Builder.buildInstr(rcc::Opcode::fromValue(BranchOpcode)); + Context.expect(Branch && Branch->addBasicBlock(*Fixture.Exit).has_value() && Branch->build(), + "source branch must build"); + Context.expect(Function.cfgUpdater() + .addSuccessor(*Fixture.Entry, *Fixture.Exit, rcc::BranchProbability::one()) + .has_value(), + "source CFG edge must build"); + + Context.expect(Builder.setInsertPoint(*Fixture.Exit).has_value(), + "source exit insertion point must be valid"); + auto Copy = Builder.buildInstr(rcc::Opcode::fromValue(CopyOpcode)); + Context.expect(Copy && Copy->addDef(Fixture.CopyValue).has_value() && + Copy->addUse(Fixture.Value).has_value() && Copy->build(), + "source tied copy must build"); + + auto Frame = Builder.buildInstr(rcc::Opcode::fromValue(FrameOpcode)); + Context.expect(Frame && Frame->addFrameIndex(rcc::FrameIndex::fromValue(4), -8).has_value() && + Frame->build(), + "source frame-index instruction must build"); + + auto Address = Builder.buildInstr(rcc::Opcode::fromValue(BlockAddressOpcode)); + Context.expect( + Address && Address->addBlockAddress(std::string(Function.name()), "exit", 3).has_value() && + Address->build(), + "source self block-address instruction must build"); + + auto MMO = Function.createMemOperand(loadDescription()); + Context.expect(MMO.has_value(), "source MMO must be created"); + if (!MMO) + return false; + Fixture.LoadMMO = *MMO; + auto Load = Builder.buildInstr(rcc::Opcode::fromValue(LoadOpcode)); + Context.expect(Load && Load->addMemOperand(**MMO).has_value() && Load->build(), + "source load with MMO must build"); + + Function.properties().set(rcc::MachineFunctionProperty::IsSSA); + Function.properties().set(rcc::MachineFunctionProperty::TracksLiveness); + Function.properties().set(rcc::MachineFunctionProperty::NoPHIs); + return true; +} + +void testDeepClone(TestContext &Context) { + auto InstructionSet = createInstructionSet(); + auto Source = createFunction(Context, "source_function", 1); + SourceFixture Fixture; + if (!InstructionSet || !Source || !populateSource(Context, *Source, *InstructionSet, Fixture)) { + return; + } + Context.expect(rcc::MachineVerifier::verify(*Source, *InstructionSet).has_value(), + "source function must verify before cloning"); + + auto Clone = rcc::cloneMachineFunction( + *Source, *InstructionSet, + rcc::MachineFunctionCloneOptions{rcc::MachineFunctionStableID::fromValue(99), + std::string("cloned_function")}); + Context.expect(Clone.has_value(), "valid source function must deep-clone"); + if (!Clone) + return; + rcc::MachineFunction &Destination = *Clone->ClonedFunction; + + Context.expect(Destination.name() == "cloned_function" && + Destination.stableID() == rcc::MachineFunctionStableID::fromValue(99), + "clone must use its explicit function identity"); + Context.expect(Destination.properties() == Source->properties() && + rcc::MachineVerifier::verify(Destination, *InstructionSet).has_value() && + rcc::MachineVerifier::verify(*Source, *InstructionSet).has_value(), + "source and destination must independently preserve valid properties"); + Context.expect(Source->allBlocks().size() == 3 && Destination.allBlocks().size() == 2 && + Source->allInstructions().size() == 7 && + Destination.allInstructions().size() == 6, + "clone must omit detached arena history"); + Context.expect(Clone->BlockStableIDs.size() == 2 && Clone->InstructionStableIDs.size() == 6 && + Clone->VirtualRegisters.size() == 2, + "clone must publish complete live identity mappings"); + + rcc::MachineBasicBlock *DestinationEntry = Destination.firstBlock(); + rcc::MachineBasicBlock *DestinationExit = + DestinationEntry == nullptr ? nullptr : DestinationEntry->next(); + Context.expect(DestinationEntry != nullptr && DestinationExit != nullptr && + DestinationExit->next() == nullptr && DestinationEntry != Fixture.Entry && + DestinationExit != Fixture.Exit, + "clone blocks must be distinct and preserve layout"); + if (DestinationEntry == nullptr || DestinationExit == nullptr) + return; + + const auto EntryID = Clone->BlockStableIDs.find(Fixture.Entry->stableID()); + const auto ExitID = Clone->BlockStableIDs.find(Fixture.Exit->stableID()); + Context.expect(EntryID != Clone->BlockStableIDs.end() && ExitID != Clone->BlockStableIDs.end() && + EntryID->second == DestinationEntry->stableID() && + ExitID->second == DestinationExit->stableID(), + "block StableID mapping must identify cloned layout objects"); + Context.expect(DestinationEntry->successors().size() == 1 && + DestinationEntry->successors()[0].Block == DestinationExit && + DestinationExit->predecessors().size() == 1 && + DestinationExit->predecessors()[0] == DestinationEntry, + "clone must rebuild reciprocal CFG edges"); + Context.expect(std::ranges::equal(DestinationEntry->liveIns(), Fixture.Entry->liveIns()), + "clone must preserve block live-ins"); + + const auto ValuePosition = Clone->VirtualRegisters.find(Fixture.Value); + const auto CopyValuePosition = Clone->VirtualRegisters.find(Fixture.CopyValue); + Context.expect(ValuePosition != Clone->VirtualRegisters.end() && + CopyValuePosition != Clone->VirtualRegisters.end(), + "clone must map every live source vreg"); + if (ValuePosition == Clone->VirtualRegisters.end() || + CopyValuePosition == Clone->VirtualRegisters.end()) { + return; + } + const rcc::Register NewValue = ValuePosition->second; + const rcc::Register NewCopyValue = CopyValuePosition->second; + Context.expect(NewValue.virtualIndex() == 0 && NewCopyValue.virtualIndex() == 1, + "clone must deterministically compact source vreg tombstones"); + + auto SourceInfo = Source->registerInfo().virtualRegisterInfo(Fixture.Value); + auto DestinationInfo = Destination.registerInfo().virtualRegisterInfo(NewValue); + Context.expect(SourceInfo && DestinationInfo && + SourceInfo->get().Type == DestinationInfo->get().Type && + SourceInfo->get().Bank == DestinationInfo->get().Bank && + SourceInfo->get().RegClass == DestinationInfo->get().RegClass && + SourceInfo->get().AllocationHints == DestinationInfo->get().AllocationHints, + "clone must preserve vreg type and allocation constraints"); + Context.expect(Destination.registerInfo().liveIns().size() == 1 && + Destination.registerInfo().liveIns()[0].InitialVirtualRegister == NewValue && + std::ranges::equal(Destination.registerInfo().reservedRegisters(), + Source->registerInfo().reservedRegisters()), + "clone must remap function live-ins and preserve reserved registers"); + + rcc::MachineInstr *DestinationDef = findInstruction(*DestinationEntry, DefOpcode); + rcc::MachineInstr *DestinationBranch = findInstruction(*DestinationEntry, BranchOpcode); + rcc::MachineInstr *DestinationCopy = findInstruction(*DestinationExit, CopyOpcode); + rcc::MachineInstr *DestinationFrame = findInstruction(*DestinationExit, FrameOpcode); + rcc::MachineInstr *DestinationAddress = findInstruction(*DestinationExit, BlockAddressOpcode); + rcc::MachineInstr *DestinationLoad = findInstruction(*DestinationExit, LoadOpcode); + Context.expect(DestinationDef && DestinationBranch && DestinationCopy && DestinationFrame && + DestinationAddress && DestinationLoad, + "clone must preserve every live instruction"); + if (!DestinationDef || !DestinationBranch || !DestinationCopy || !DestinationFrame || + !DestinationAddress || !DestinationLoad) { + return; + } + + Context.expect(DestinationDef->operandAt(0)->registerValue() == NewValue && + DestinationDef->flags().has(rcc::MachineInstrFlag::NoMerge) && + DestinationDef->sourceLocation() == + rcc::SourceLocation{"source.mir", 9, 4, 2} && + DestinationDef->origin() == rcc::OriginID::fromValue(77), + "clone must remap register operands and preserve instruction metadata"); + Context.expect(DestinationBranch->operandAt(0)->getIf<rcc::BasicBlockOperand>()->Block == + DestinationExit, + "clone must remap basic-block operands"); + Context.expect(DestinationCopy->operandAt(0)->registerValue() == NewCopyValue && + DestinationCopy->operandAt(1)->registerValue() == NewValue && + DestinationCopy->operandAt(0)->tiedOperandIndex() == 1 && + DestinationCopy->operandAt(1)->tiedOperandIndex() == 0, + "clone must remap tied registers and rebuild ties"); + Context.expect(DestinationFrame->operandAt(0)->getIf<rcc::FrameIndexOperand>()->Index == + rcc::FrameIndex::fromValue(4) && + Clone->FrameIndices.contains(rcc::FrameIndex::fromValue(4)), + "clone must preserve and map frame indices"); + Context.expect( + DestinationAddress->operandAt(0)->getIf<rcc::BlockAddressOperand>()->FunctionName == + "cloned_function", + "clone must rewrite self block-address function names"); + + Context.expect(DestinationLoad->memOperands().size() == 1 && + DestinationLoad->memOperands()[0] != Fixture.LoadMMO && + *DestinationLoad->memOperands()[0] == *Fixture.LoadMMO && + Destination.ownsMemOperand(*DestinationLoad->memOperands()[0]) && + !Source->ownsMemOperand(*DestinationLoad->memOperands()[0]), + "clone must deep-copy MMO ownership while preserving semantics"); + + rcc::MachineInstr *SourceDef = findInstruction(*Fixture.Entry, DefOpcode); + const auto InstructionID = SourceDef == nullptr + ? Clone->InstructionStableIDs.end() + : Clone->InstructionStableIDs.find(SourceDef->stableID()); + Context.expect(SourceDef != nullptr && InstructionID != Clone->InstructionStableIDs.end() && + InstructionID->second == DestinationDef->stableID(), + "instruction StableID mapping must identify cloned instructions"); +} + +void testCloneFailures(TestContext &Context) { + auto InstructionSet = createInstructionSet(); + auto Source = createFunction(Context, "failure_source", 2); + if (!InstructionSet || !Source) + return; + + Context.expect( + !rcc::cloneMachineFunction(*Source, *InstructionSet, + rcc::MachineFunctionCloneOptions{ + rcc::MachineFunctionStableID::fromValue(0), std::nullopt}), + "clone must reject an invalid destination StableID"); + Context.expect( + !rcc::cloneMachineFunction(*Source, *InstructionSet, + rcc::MachineFunctionCloneOptions{ + rcc::MachineFunctionStableID::fromValue(3), std::string()}), + "clone must reject an explicitly empty destination name"); + + auto Invalid = createFunction(Context, "invalid_source", 4); + rcc::MachineBasicBlock *Block = Invalid ? createBlock(Context, *Invalid) : nullptr; + if (Invalid && Block != nullptr) { + auto Unknown = Invalid->createInstruction(rcc::Opcode::fromValue(999)); + Context.expect(Unknown && Block->appendInstruction(**Unknown).has_value(), + "invalid clone source must contain an unknown opcode"); + Context.expect( + !rcc::cloneMachineFunction(*Invalid, *InstructionSet, + rcc::MachineFunctionCloneOptions{ + rcc::MachineFunctionStableID::fromValue(5), std::nullopt}), + "clone must verify and reject an invalid source function"); + } +} + +} // namespace + +int main() { + TestContext Context; + testDeepClone(Context); + testCloneFailures(Context); + return Context.result(); +} |