From f6fdfb8d484b4e52cdb24a94a31b0f00d41a5eb7 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sat, 15 Aug 2026 00:38:20 +0800 Subject: [GlobalISel] Match LLVM CSE builder result semantics --- backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp | 226 +++++++++++++++++++++++ 1 file changed, 226 insertions(+) create mode 100644 backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp (limited to 'backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp') diff --git a/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp b/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp new file mode 100644 index 0000000..e1fdaa6 --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp @@ -0,0 +1,226 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/CSEMIRBuilder.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/CSEInfo.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include +#include +#include +#include +#include +#include + +namespace rcc { + +bool CSEMIRBuilder::canPerformCSE(Opcode InstructionOpcode) const noexcept { + const GISelCSEInfo *Info = getCSEInfo(); + return Info != nullptr && Info->shouldCSE(InstructionOpcode); +} + +bool CSEMIRBuilder::dominatesInsertionPoint(const MachineInstr &Instruction) const noexcept { + const MachineBasicBlock *Block = insertionBlock(); + const MachineInstr *InsertBefore = insertionInstruction(); + if (Block == nullptr || Instruction.parent() != Block) + return false; + if (InsertBefore == nullptr) + return true; + for (const MachineInstr *Current = Block->firstInstruction(); Current != nullptr; + Current = Current->next()) { + if (Current == &Instruction) + return true; + if (Current == InsertBefore) + return false; + } + return false; +} + +Expected CSEMIRBuilder::makeInstructionDominate(MachineInstr &Instruction) const { + MachineBasicBlock *Block = insertionBlock(); + MachineInstr *InsertBefore = insertionInstruction(); + if (Block == nullptr || Instruction.parent() != Block) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE candidate is not in the insertion block"); + } + if (&Instruction == InsertBefore) { + return const_cast(this)->setInsertPointAfter(Instruction); + } + if (InsertBefore == nullptr || dominatesInsertionPoint(Instruction)) + return {}; + auto Removed = Block->removeInstruction(Instruction); + if (!Removed) + return std::unexpected(Removed.error()); + auto Inserted = Block->insertInstructionBefore(*InsertBefore, Instruction); + if (!Inserted) + return std::unexpected(Inserted.error()); + return {}; +} + +Expected +CSEMIRBuilder::generateCopyIfRequired(const MachineIRBuilderResult &Destination, + MachineInstr &Instruction) const { + if (Destination.kind() == MachineIRBuilderResult::Kind::Type) + return &Instruction; + const MachineOperand *Definition = Instruction.operandAt(0); + const Register *Source = Definition == nullptr ? nullptr : Definition->getIf(); + if (Source == nullptr || !Definition->isDef()) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE candidate has no register definition"); + } + if (Destination.reg() == *Source) + return &Instruction; + return MachineIRBuilder::buildCopy(Destination, *Source); +} + +Expected CSEMIRBuilder::memoize(MachineInstr &Instruction) const { + GISelCSEInfo *Info = getCSEInfo(); + if (Info == nullptr) + return &Instruction; + auto Inserted = Info->handleRecordedInstruction(Instruction); + if (!Inserted) + return std::unexpected(Inserted.error()); + return &Instruction; +} + +Expected +CSEMIRBuilder::buildInstr(Opcode InstructionOpcode, + std::span Destinations, + std::span Sources) const { + if (!canPerformCSE(InstructionOpcode)) + return MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + const bool CanGenerateCopies = + Destinations.size() == 1 || std::ranges::all_of(Destinations, [](const auto &Destination) { + return Destination.kind() == MachineIRBuilderResult::Kind::Type; + }); + if (!CanGenerateCopies) { + auto Built = MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources); + if (!Built) + return std::unexpected(Built.error()); + Info->handleRemoveInstruction(**Built); + return *Built; + } + + auto Existing = + Info->getMachineInstrIfExists(InstructionOpcode, Destinations, Sources, + std::span(), MachineInstrFlags(), *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + if (Destinations.size() == 1) + return generateCopyIfRequired(Destinations.front(), **Existing); + return *Existing; + } + + auto Built = MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +Expected CSEMIRBuilder::buildConstant(MachineIRBuilderResult Destination, + APInt Value) const { + const Opcode ConstantOpcode = opcode(GenericOpcode::G_CONSTANT); + if (!canPerformCSE(ConstantOpcode)) + return MachineIRBuilder::buildConstant(Destination, std::move(Value)); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + auto Existing = Info->getConstantIfExists(Destination, Value, *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + return generateCopyIfRequired(Destination, **Existing); + } + + auto Built = MachineIRBuilder::buildConstant(Destination, std::move(Value)); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +Expected CSEMIRBuilder::buildSExtInReg(MachineIRBuilderResult Destination, + Register Source, std::uint32_t Width) const { + const Opcode InstructionOpcode = opcode(GenericOpcode::G_SEXT_INREG); + if (!canPerformCSE(InstructionOpcode)) + return MachineIRBuilder::buildSExtInReg(Destination, Source, Width); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + const std::array Destinations{Destination}; + const std::array Sources{Source}; + const std::array Immediates{static_cast(Width)}; + auto Existing = Info->getMachineInstrIfExists( + InstructionOpcode, std::span(Destinations), + std::span(Sources), std::span(Immediates), + MachineInstrFlags(), *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + return generateCopyIfRequired(Destination, **Existing); + } + + auto Built = MachineIRBuilder::buildSExtInReg(Destination, Source, Width); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +Expected CSEMIRBuilder::buildExtract(MachineIRBuilderResult Destination, + Register Source, std::uint64_t Offset) const { + if (Offset > static_cast(std::numeric_limits::max())) + return MachineIRBuilder::buildExtract(Destination, Source, Offset); + const Opcode InstructionOpcode = opcode(GenericOpcode::G_EXTRACT); + if (!canPerformCSE(InstructionOpcode)) + return MachineIRBuilder::buildExtract(Destination, Source, Offset); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + const std::array Destinations{Destination}; + const std::array Sources{Source}; + const std::array Immediates{static_cast(Offset)}; + auto Existing = Info->getMachineInstrIfExists( + InstructionOpcode, std::span(Destinations), + std::span(Sources), std::span(Immediates), + MachineInstrFlags(), *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + return generateCopyIfRequired(Destination, **Existing); + } + + auto Built = MachineIRBuilder::buildExtract(Destination, Source, Offset); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +} // namespace rcc -- cgit v1.2.3