From 36c4344ddf1866005c62910166ca077bf2e8f62e Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Wed, 26 Aug 2026 17:38:21 +0800 Subject: [CodeGen] Implement RISC-V finalize-isel --- backend/include/rcc/CodeGen/FinalizeISel.h | 37 ++ .../include/rcc/CodeGen/InstructionDescriptor.h | 1 + backend/lib/CodeGen/CMakeLists.txt | 2 + backend/lib/CodeGen/FinalizeISel.cpp | 101 ++++ backend/lib/Target/RISCV/CMakeLists.txt | 3 + backend/lib/Target/RISCV/RISCV.h | 2 + backend/lib/Target/RISCV/RISCVFinalizeISel.cpp | 506 +++++++++++++++++++++ .../lib/Target/RISCV/RISCVInstrInfoPseudo.rccdesc | 6 +- backend/lib/Target/RISCV/RISCVPipeline.cpp | 11 +- .../utils/TableGen/Common/CodeGenInstruction.cpp | 3 +- 10 files changed, 667 insertions(+), 5 deletions(-) create mode 100644 backend/include/rcc/CodeGen/FinalizeISel.h create mode 100644 backend/lib/CodeGen/FinalizeISel.cpp create mode 100644 backend/lib/Target/RISCV/RISCVFinalizeISel.cpp (limited to 'backend') diff --git a/backend/include/rcc/CodeGen/FinalizeISel.h b/backend/include/rcc/CodeGen/FinalizeISel.h new file mode 100644 index 0000000..c3121ec --- /dev/null +++ b/backend/include/rcc/CodeGen/FinalizeISel.h @@ -0,0 +1,37 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_FINALIZEISEL_H +#define RCC_CODEGEN_FINALIZEISEL_H + +#include "rcc/CodeGen/MachinePassManager.h" + +namespace rcc { + +class MachineBasicBlock; +class MachineInstr; + +class TargetFinalizeISelInfo { +public: + virtual ~TargetFinalizeISelInfo() = default; + + [[nodiscard]] virtual Expected + emitInstrWithCustomInserter(MachineInstr &Instruction, MachineBasicBlock &Block, + MachineFunction &Function, const TargetDescription &Target) const = 0; +}; + +class FinalizeISelPass final : public MachineFunctionPass { +public: + explicit FinalizeISelPass(const TargetFinalizeISelInfo &Info) noexcept : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) override; + +private: + const TargetFinalizeISelInfo *Info; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_FINALIZEISEL_H diff --git a/backend/include/rcc/CodeGen/InstructionDescriptor.h b/backend/include/rcc/CodeGen/InstructionDescriptor.h index b172cd9..ca127d4 100644 --- a/backend/include/rcc/CodeGen/InstructionDescriptor.h +++ b/backend/include/rcc/CodeGen/InstructionDescriptor.h @@ -147,6 +147,7 @@ enum class InstructionFlag : std::uint8_t { FakeUse, Generic, TerminalEmission, + UsesCustomInserter, Count, }; diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 795fb40..a7a0586 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -8,6 +8,7 @@ set( GlobalObject.cpp GenericOpcodes.cpp FrameIndexElimination.cpp + FinalizeISel.cpp InstructionDescriptor.cpp LowLevelType.cpp MachineBasicBlockAttributes.cpp @@ -100,6 +101,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalObject.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericOpcodes.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/FrameIndexElimination.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/FinalizeISel.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InstructionDescriptor.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InlineAsm.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h" diff --git a/backend/lib/CodeGen/FinalizeISel.cpp b/backend/lib/CodeGen/FinalizeISel.cpp new file mode 100644 index 0000000..9b5c11f --- /dev/null +++ b/backend/lib/CodeGen/FinalizeISel.cpp @@ -0,0 +1,101 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/FinalizeISel.h" + +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFrameInfo.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include + +namespace rcc { +namespace { + +[[nodiscard]] const MachinePassContract &finalizeISelContract() { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = "finalize-isel", + .Requires = {}, + .Sets = {}, + .Clears = {}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::Selected, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::CFG, MachinePassChange::BlockLayout, + MachinePassChange::Frame}; + return Value; + }(); + return Contract; +} + +} // namespace + +const MachinePassContract &FinalizeISelPass::contract() const noexcept { + return finalizeISelContract(); +} + +Expected FinalizeISelPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &) { + MachinePassResult Result; + MachineBasicBlock *Block = Function.firstBlock(); + while (Block != nullptr) { + MachineInstr *Instruction = Block->firstInstruction(); + while (Instruction != nullptr) { + MachineInstr *Next = Instruction->next(); + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "finalize-isel encountered an unknown opcode"); + } + + if (Instruction->flags().has(MachineInstrFlag::FrameSetup) || + Instruction->flags().has(MachineInstrFlag::FrameDestroy)) { + MachineFrameState State = Function.frameInfo().state(); + if (!State.AdjustsStack) { + State.AdjustsStack = true; + auto Updated = Function.frameInfo().setState(std::move(State)); + if (!Updated) + return std::unexpected(Updated.error()); + Result.Changes.add(MachinePassChange::Frame); + } + } + + if (!Descriptor->Flags.has(InstructionFlag::UsesCustomInserter)) { + Instruction = Next; + continue; + } + + auto Expanded = Info->emitInstrWithCustomInserter(*Instruction, *Block, Function, Target); + if (!Expanded) + return std::unexpected(Expanded.error()); + if (*Expanded == nullptr || &(*Expanded)->function() != &Function) { + return makeUnexpected(ErrorCode::InternalError, + "custom inserter returned an invalid basic block"); + } + + Result.Changes.add(MachinePassChange::Instructions); + Result.Changes.add(MachinePassChange::Operands); + if (*Expanded != Block) { + Result.Changes.add(MachinePassChange::CFG); + Result.Changes.add(MachinePassChange::BlockLayout); + Block = *Expanded; + Instruction = Block->firstInstruction(); + } else { + Instruction = Next; + } + } + Block = Block->next(); + } + + Result.Changed = !Result.Changes.empty(); + Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); + return Result; +} + +} // namespace rcc diff --git a/backend/lib/Target/RISCV/CMakeLists.txt b/backend/lib/Target/RISCV/CMakeLists.txt index f34a9b0..0e93ea9 100644 --- a/backend/lib/Target/RISCV/CMakeLists.txt +++ b/backend/lib/Target/RISCV/CMakeLists.txt @@ -113,6 +113,7 @@ add_library( RISCVInstrInfo.cpp RISCVAssemblyPrinter.cpp RISCVFrameLowering.cpp + RISCVFinalizeISel.cpp RISCVFunctionInfo.cpp RISCVImmediateMaterialization.cpp RISCVInstPrinter.cpp @@ -200,6 +201,7 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVInstrInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVAssemblyPrinter.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFrameLowering.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFinalizeISel.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFunctionInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVImmediateMaterialization.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVImmediateMaterialization.h" @@ -245,6 +247,7 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVInstrInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVAssemblyPrinter.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFrameLowering.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFinalizeISel.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFunctionInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVImmediateMaterialization.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVInstPrinter.cpp" diff --git a/backend/lib/Target/RISCV/RISCV.h b/backend/lib/Target/RISCV/RISCV.h index 3153668..e7ab865 100644 --- a/backend/lib/Target/RISCV/RISCV.h +++ b/backend/lib/Target/RISCV/RISCV.h @@ -3,6 +3,7 @@ #ifndef RCC_LIB_TARGET_RISCV_RISCV_H #define RCC_LIB_TARGET_RISCV_RISCV_H +#include "rcc/CodeGen/FinalizeISel.h" #include "rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h" #include "rcc/CodeGen/MachineCombinerPattern.h" #include "rcc/CodeGen/MachineOptimizationPipeline.h" @@ -38,6 +39,7 @@ createSchedulingModel(const TargetSchedulingHooks &Hooks); [[nodiscard]] const GIMatchTableExecutor &giselCombinerExecutor() noexcept; [[nodiscard]] const TargetMemoryFoldingInfo &memoryFoldingInfo() noexcept; [[nodiscard]] const TargetPseudoExpansionInfo &pseudoExpansionInfo() noexcept; +[[nodiscard]] const TargetFinalizeISelInfo &finalizeISelInfo() noexcept; [[nodiscard]] std::unique_ptr createMoveMergePass(const RISCVSubtarget &Subtarget); [[nodiscard]] std::unique_ptr diff --git a/backend/lib/Target/RISCV/RISCVFinalizeISel.cpp b/backend/lib/Target/RISCV/RISCVFinalizeISel.cpp new file mode 100644 index 0000000..784490d --- /dev/null +++ b/backend/lib/Target/RISCV/RISCVFinalizeISel.cpp @@ -0,0 +1,506 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "RISCV.h" +#include "RISCVInstrInfo.h" +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/Target/RISCV/RISCVInstructions.h" + +#include +#include +#include +#include +#include + +namespace rcc::riscv { +namespace { + +struct SelectOperands final { + Register Destination; + Register Left; + Register Right; + std::int64_t Condition = 0; + Register TrueValue; + Register FalseValue; +}; + +struct SelectSequence final { + std::vector Selects; + std::vector DebugValues; + MachineInstr *LastSelect = nullptr; +}; + +[[nodiscard]] bool isSelectPseudo(Opcode Value) noexcept { + return Value == instructionOpcode(InstructionOpcode::Select_GPR_Using_CC_GPR) || + Value == instructionOpcode(InstructionOpcode::Select_FPR32_Using_CC_GPR) || + Value == instructionOpcode(InstructionOpcode::Select_FPR64_Using_CC_GPR); +} + +[[nodiscard]] Expected selectOperands(const MachineInstr &Instruction) { + if (!isSelectPseudo(Instruction.opcode()) || Instruction.operandCount() < 6U) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V custom select has an invalid opcode or operand count"); + } + + const auto RegisterAt = [&Instruction](std::size_t Index) -> std::optional { + const MachineOperand *Operand = Instruction.operandAt(Index); + if (Operand == nullptr) + return std::nullopt; + return Operand->registerValue(); + }; + const auto Destination = RegisterAt(0); + const auto Left = RegisterAt(1); + const auto Right = RegisterAt(2); + const MachineOperand *ConditionOperand = Instruction.operandAt(3); + const auto *Condition = + ConditionOperand == nullptr ? nullptr : ConditionOperand->getIf(); + const auto TrueValue = RegisterAt(4); + const auto FalseValue = RegisterAt(5); + if (!Destination || !Left || !Right || Condition == nullptr || !TrueValue || !FalseValue) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V custom select has malformed operands"); + } + if (*Condition < static_cast(BranchConditionCode::Equal) || + *Condition > static_cast(BranchConditionCode::UnsignedGreaterEqual)) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V custom select has an invalid condition code"); + } + return SelectOperands{*Destination, *Left, *Right, *Condition, *TrueValue, *FalseValue}; +} + +[[nodiscard]] bool containsRegister(const std::vector &Registers, + Register Value) noexcept { + for (const Register Candidate : Registers) + if (Candidate == Value) + return true; + return false; +} + +[[nodiscard]] bool instructionUsesAny(const MachineInstr &Instruction, + const std::vector &Registers) noexcept { + for (const MachineOperand &Operand : Instruction.operands()) { + const std::optional Reg = Operand.registerValue(); + if (Reg && Operand.isUse() && containsRegister(Registers, *Reg)) + return true; + } + return false; +} + +void collectAdjacentDebugValues(MachineInstr &Select, Register Destination, + std::vector &Result) { + for (MachineInstr *Instruction = Select.next(); + Instruction != nullptr && Instruction->isDebugInstr(); Instruction = Instruction->next()) { + const std::vector DestinationList{Destination}; + if (instructionUsesAny(*Instruction, DestinationList)) + Result.push_back(Instruction); + } +} + +[[nodiscard]] bool stopsSelectSequence(const MachineInstr &Instruction, + const InstructionDescriptor &Descriptor, + const std::vector &SelectDestinations) noexcept { + const InstructionFlags Flags = Descriptor.Flags; + if (Flags.has(InstructionFlag::UnmodeledSideEffects) || + Flags.has(InstructionFlag::HasSideEffects) || Flags.has(InstructionFlag::MayLoad) || + Flags.has(InstructionFlag::MayStore) || Flags.has(InstructionFlag::UsesCustomInserter) || + !Instruction.memOperands().empty() || Instruction.flags().has(MachineInstrFlag::FrameSetup) || + Instruction.flags().has(MachineInstrFlag::FrameDestroy) || + Instruction.opcode() == opcode(GenericOpcode::INLINEASM) || + Instruction.opcode() == opcode(GenericOpcode::INLINEASM_BR)) { + return true; + } + return instructionUsesAny(Instruction, SelectDestinations); +} + +[[nodiscard]] Expected collectSelectSequence(MachineInstr &First, + const TargetDescription &Target) { + auto FirstOperands = selectOperands(First); + if (!FirstOperands) + return std::unexpected(FirstOperands.error()); + + SelectSequence Result; + std::vector SelectDestinations{FirstOperands->Destination}; + for (MachineInstr *Instruction = &First; Instruction != nullptr; + Instruction = Instruction->next()) { + if (Instruction->isDebugInstr()) + continue; + if (isSelectPseudo(Instruction->opcode())) { + auto Operands = selectOperands(*Instruction); + if (!Operands) + return std::unexpected(Operands.error()); + if (Operands->Left != FirstOperands->Left || Operands->Right != FirstOperands->Right || + Operands->Condition != FirstOperands->Condition || + containsRegister(SelectDestinations, Operands->TrueValue) || + containsRegister(SelectDestinations, Operands->FalseValue)) { + break; + } + Result.Selects.push_back(Instruction); + Result.LastSelect = Instruction; + collectAdjacentDebugValues(*Instruction, Operands->Destination, Result.DebugValues); + if (!containsRegister(SelectDestinations, Operands->Destination)) + SelectDestinations.push_back(Operands->Destination); + continue; + } + + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V select expansion encountered an unknown opcode"); + } + if (stopsSelectSequence(*Instruction, *Descriptor, SelectDestinations)) + break; + } + if (Result.Selects.empty() || Result.LastSelect == nullptr) { + return makeUnexpected(ErrorCode::InternalError, + "RISC-V select sequence did not contain its anchor instruction"); + } + return Result; +} + +[[nodiscard]] Expected conditionalBranchOpcode(std::int64_t Condition) { + switch (static_cast(Condition)) { + case BranchConditionCode::Equal: + return instructionOpcode(InstructionOpcode::BEQ); + case BranchConditionCode::NotEqual: + return instructionOpcode(InstructionOpcode::BNE); + case BranchConditionCode::SignedLessThan: + return instructionOpcode(InstructionOpcode::BLT); + case BranchConditionCode::SignedGreaterEqual: + return instructionOpcode(InstructionOpcode::BGE); + case BranchConditionCode::UnsignedLessThan: + return instructionOpcode(InstructionOpcode::BLTU); + case BranchConditionCode::UnsignedGreaterEqual: + return instructionOpcode(InstructionOpcode::BGEU); + } + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V select has an invalid condition code"); +} + +[[nodiscard]] Expected +buildConditionalBranch(MachineFunction &Function, const TargetDescription &Target, + MachineBasicBlock &Block, MachineBasicBlock &Destination, + const SelectOperands &Operands, const MachineInstr &Source) { + auto BranchOpcode = conditionalBranchOpcode(Operands.Condition); + if (!BranchOpcode) + return std::unexpected(BranchOpcode.error()); + MachineIRBuilder Builder(Function, Target); + if (auto Point = Builder.setInsertPoint(Block); !Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(*BranchOpcode); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Added = Pending->addUse(Operands.Left); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(Operands.Right); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addBasicBlock(Destination); !Added) + return std::unexpected(Added.error()); + if (Source.debugLocation()) { + if (auto Location = Pending->setDebugLocation(*Source.debugLocation()); !Location) + return std::unexpected(Location.error()); + } + return Pending->build(); +} + +[[nodiscard]] Expected +buildPhi(MachineFunction &Function, const TargetDescription &Target, MachineBasicBlock &Tail, + MachineInstr *InsertBefore, const SelectOperands &Operands, MachineBasicBlock &Head, + MachineBasicBlock &IfFalse, const MachineInstr &Source) { + MachineIRBuilder Builder(Function, Target); + Expected Point = InsertBefore == nullptr ? Builder.setInsertPoint(Tail) + : Builder.setInsertPointBefore(*InsertBefore); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(opcode(GenericOpcode::PHI)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Added = Pending->addDef(Operands.Destination); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(Operands.TrueValue); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addBasicBlock(Head); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(Operands.FalseValue); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addBasicBlock(IfFalse); !Added) + return std::unexpected(Added.error()); + if (Source.debugLocation()) { + if (auto Location = Pending->setDebugLocation(*Source.debugLocation()); !Location) + return std::unexpected(Location.error()); + } + return Pending->build(); +} + +[[nodiscard]] Expected insertBlocksAfter(MachineFunction &Function, MachineBasicBlock &Head, + MachineBasicBlock &First, + MachineBasicBlock &Second) { + MachineBasicBlock *Following = Head.next(); + if (Following == nullptr) { + if (auto Inserted = Function.appendBlock(First); !Inserted) + return std::unexpected(Inserted.error()); + return Function.appendBlock(Second); + } + if (auto Inserted = Function.insertBlockBefore(*Following, First); !Inserted) + return std::unexpected(Inserted.error()); + return Function.insertBlockBefore(*Following, Second); +} + +[[nodiscard]] Expected moveInstructionToEnd(MachineInstr &Instruction, + MachineBasicBlock &Destination) { + MachineBasicBlock *Source = Instruction.parent(); + if (Source == nullptr) + return makeUnexpected(ErrorCode::InternalError, "moved instruction is detached"); + if (auto Removed = Source->removeInstruction(Instruction); !Removed) + return std::unexpected(Removed.error()); + return Destination.appendInstruction(Instruction); +} + +[[nodiscard]] Expected emitSelectSequence(MachineInstr &First, + MachineBasicBlock &Head, + MachineFunction &Function, + const TargetDescription &Target) { + auto Sequence = collectSelectSequence(First, Target); + if (!Sequence) + return std::unexpected(Sequence.error()); + auto FirstOperands = selectOperands(First); + if (!FirstOperands) + return std::unexpected(FirstOperands.error()); + + auto TailResult = Function.createBasicBlock(); + if (!TailResult) + return std::unexpected(TailResult.error()); + auto IfFalseResult = Function.createBasicBlock(); + if (!IfFalseResult) + return std::unexpected(IfFalseResult.error()); + MachineBasicBlock *Tail = *TailResult; + MachineBasicBlock *IfFalse = *IfFalseResult; + if (auto Inserted = insertBlocksAfter(Function, Head, *IfFalse, *Tail); !Inserted) + return std::unexpected(Inserted.error()); + const std::uint32_t CallFrameSize = Head.attributes().callFrameSize(); + IfFalse->attributes().setCallFrameSize(CallFrameSize); + Tail->attributes().setCallFrameSize(CallFrameSize); + + for (MachineInstr *DebugValue : Sequence->DebugValues) { + if (auto Moved = moveInstructionToEnd(*DebugValue, *Tail); !Moved) + return std::unexpected(Moved.error()); + } + for (MachineInstr *Instruction = Sequence->LastSelect->next(); Instruction != nullptr;) { + MachineInstr *Next = Instruction->next(); + if (auto Moved = moveInstructionToEnd(*Instruction, *Tail); !Moved) + return std::unexpected(Moved.error()); + Instruction = Next; + } + + MachineCFGUpdater CFG = Function.cfgUpdater(); + if (auto Transferred = CFG.transferSuccessors(Head, *Tail); !Transferred) + return std::unexpected(Transferred.error()); + auto Half = BranchProbability::fromFraction(1U, 2U); + if (!Half) + return std::unexpected(Half.error()); + if (auto Added = CFG.addSuccessor(Head, *IfFalse, *Half); !Added) + return std::unexpected(Added.error()); + if (auto Added = CFG.addSuccessor(Head, *Tail, *Half); !Added) + return std::unexpected(Added.error()); + if (auto Added = CFG.addSuccessor(*IfFalse, *Tail, BranchProbability::one()); !Added) + return std::unexpected(Added.error()); + + auto Branch = buildConditionalBranch(Function, Target, Head, *Tail, *FirstOperands, First); + if (!Branch) + return std::unexpected(Branch.error()); + + MachineInstr *PhiInsertBefore = Tail->firstInstruction(); + for (MachineInstr *Select : Sequence->Selects) { + auto Operands = selectOperands(*Select); + if (!Operands) + return std::unexpected(Operands.error()); + auto Phi = + buildPhi(Function, Target, *Tail, PhiInsertBefore, *Operands, Head, *IfFalse, *Select); + if (!Phi) + return std::unexpected(Phi.error()); + } + for (MachineInstr *Select : Sequence->Selects) { + MachineBasicBlock *Parent = Select->parent(); + if (Parent == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "RISC-V custom select became detached during expansion"); + if (auto Removed = Parent->removeInstruction(*Select); !Removed) + return std::unexpected(Removed.error()); + } + Function.properties().clear(MachineFunctionProperty::NoPHIs); + return Tail; +} + +[[nodiscard]] MachineInstr *nextNonDebug(MachineInstr &Instruction) noexcept { + MachineInstr *Next = Instruction.next(); + while (Next != nullptr && Next->isDebugInstr()) + Next = Next->next(); + return Next; +} + +[[nodiscard]] bool isCascadedFloatingSelect(MachineInstr &First, MachineInstr *Second) noexcept { + if (First.opcode() == instructionOpcode(InstructionOpcode::Select_GPR_Using_CC_GPR) || + Second == nullptr || Second->opcode() != First.opcode()) { + return false; + } + const MachineOperand *DestinationOperand = First.operandAt(0); + const MachineOperand *FalseOperand = Second->operandAt(5); + const auto Destination = + DestinationOperand == nullptr ? std::nullopt : DestinationOperand->registerValue(); + const auto FalseValue = FalseOperand == nullptr ? std::nullopt : FalseOperand->registerValue(); + return Destination && FalseValue && *Destination == *FalseValue && + FalseOperand->registerFlags().has(RegisterOperandFlag::Kill); +} + +[[nodiscard]] Expected +buildCascadedPhi(MachineFunction &Function, const TargetDescription &Target, + MachineBasicBlock &Sink, const SelectOperands &FirstOperands, + const SelectOperands &SecondOperands, MachineBasicBlock &Head, + MachineBasicBlock &FirstPath, MachineBasicBlock &SecondPath, + const MachineInstr &Source) { + MachineIRBuilder Builder(Function, Target); + Expected Point = Sink.firstInstruction() == nullptr + ? Builder.setInsertPoint(Sink) + : Builder.setInsertPointBefore(*Sink.firstInstruction()); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(opcode(GenericOpcode::PHI)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Added = Pending->addDef(SecondOperands.Destination); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(SecondOperands.TrueValue); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addBasicBlock(Head); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(FirstOperands.TrueValue); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addBasicBlock(FirstPath); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(FirstOperands.FalseValue); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addBasicBlock(SecondPath); !Added) + return std::unexpected(Added.error()); + if (Source.debugLocation()) { + if (auto Location = Pending->setDebugLocation(*Source.debugLocation()); !Location) + return std::unexpected(Location.error()); + } + return Pending->build(); +} + +[[nodiscard]] Expected +emitCascadedSelect(MachineInstr &First, MachineInstr &Second, MachineBasicBlock &Head, + MachineFunction &Function, const TargetDescription &Target) { + auto FirstOperands = selectOperands(First); + if (!FirstOperands) + return std::unexpected(FirstOperands.error()); + auto SecondOperands = selectOperands(Second); + if (!SecondOperands) + return std::unexpected(SecondOperands.error()); + + auto FirstPathResult = Function.createBasicBlock(); + if (!FirstPathResult) + return std::unexpected(FirstPathResult.error()); + auto SecondPathResult = Function.createBasicBlock(); + if (!SecondPathResult) + return std::unexpected(SecondPathResult.error()); + auto SinkResult = Function.createBasicBlock(); + if (!SinkResult) + return std::unexpected(SinkResult.error()); + MachineBasicBlock *FirstPath = *FirstPathResult; + MachineBasicBlock *SecondPath = *SecondPathResult; + MachineBasicBlock *Sink = *SinkResult; + MachineBasicBlock *Following = Head.next(); + const auto Insert = [&](MachineBasicBlock &Block) -> Expected { + return Following == nullptr ? Function.appendBlock(Block) + : Function.insertBlockBefore(*Following, Block); + }; + if (auto Inserted = Insert(*FirstPath); !Inserted) + return std::unexpected(Inserted.error()); + if (auto Inserted = Insert(*SecondPath); !Inserted) + return std::unexpected(Inserted.error()); + if (auto Inserted = Insert(*Sink); !Inserted) + return std::unexpected(Inserted.error()); + const std::uint32_t CallFrameSize = Head.attributes().callFrameSize(); + FirstPath->attributes().setCallFrameSize(CallFrameSize); + SecondPath->attributes().setCallFrameSize(CallFrameSize); + Sink->attributes().setCallFrameSize(CallFrameSize); + + for (MachineInstr *Instruction = First.next(); Instruction != nullptr;) { + MachineInstr *Next = Instruction->next(); + if (auto Moved = moveInstructionToEnd(*Instruction, *Sink); !Moved) + return std::unexpected(Moved.error()); + Instruction = Next; + } + + MachineCFGUpdater CFG = Function.cfgUpdater(); + if (auto Transferred = CFG.transferSuccessors(Head, *Sink); !Transferred) + return std::unexpected(Transferred.error()); + auto Half = BranchProbability::fromFraction(1U, 2U); + if (!Half) + return std::unexpected(Half.error()); + if (auto Added = CFG.addSuccessor(Head, *FirstPath, *Half); !Added) + return std::unexpected(Added.error()); + if (auto Added = CFG.addSuccessor(Head, *Sink, *Half); !Added) + return std::unexpected(Added.error()); + if (auto Added = CFG.addSuccessor(*FirstPath, *SecondPath, *Half); !Added) + return std::unexpected(Added.error()); + if (auto Added = CFG.addSuccessor(*FirstPath, *Sink, *Half); !Added) + return std::unexpected(Added.error()); + if (auto Added = CFG.addSuccessor(*SecondPath, *Sink, BranchProbability::one()); !Added) + return std::unexpected(Added.error()); + + auto FirstBranch = + buildConditionalBranch(Function, Target, *FirstPath, *Sink, *FirstOperands, First); + if (!FirstBranch) + return std::unexpected(FirstBranch.error()); + auto SecondBranch = buildConditionalBranch(Function, Target, Head, *Sink, *SecondOperands, First); + if (!SecondBranch) + return std::unexpected(SecondBranch.error()); + auto Phi = buildCascadedPhi(Function, Target, *Sink, *FirstOperands, *SecondOperands, Head, + *FirstPath, *SecondPath, First); + if (!Phi) + return std::unexpected(Phi.error()); + + if (auto Removed = Head.removeInstruction(First); !Removed) + return std::unexpected(Removed.error()); + MachineBasicBlock *SecondParent = Second.parent(); + if (SecondParent == nullptr) + return makeUnexpected(ErrorCode::InternalError, "cascaded select became detached"); + if (auto Removed = SecondParent->removeInstruction(Second); !Removed) + return std::unexpected(Removed.error()); + Function.properties().clear(MachineFunctionProperty::NoPHIs); + return Sink; +} + +class RISCVFinalizeISelInfo final : public TargetFinalizeISelInfo { +public: + [[nodiscard]] Expected + emitInstrWithCustomInserter(MachineInstr &Instruction, MachineBasicBlock &Block, + MachineFunction &Function, + const TargetDescription &Target) const override { + if (!isSelectPseudo(Instruction.opcode())) { + return makeUnexpected(ErrorCode::Unsupported, + "RISC-V has no custom inserter for the requested opcode"); + } + MachineInstr *Second = nextNonDebug(Instruction); + if (isCascadedFloatingSelect(Instruction, Second)) + return emitCascadedSelect(Instruction, *Second, Block, Function, Target); + return emitSelectSequence(Instruction, Block, Function, Target); + } +}; + +} // namespace + +const TargetFinalizeISelInfo &finalizeISelInfo() noexcept { + static const RISCVFinalizeISelInfo Info; + return Info; +} + +} // namespace rcc::riscv diff --git a/backend/lib/Target/RISCV/RISCVInstrInfoPseudo.rccdesc b/backend/lib/Target/RISCV/RISCVInstrInfoPseudo.rccdesc index 41cc051..a0767f9 100644 --- a/backend/lib/Target/RISCV/RISCVInstrInfoPseudo.rccdesc +++ b/backend/lib/Target/RISCV/RISCVInstrInfoPseudo.rccdesc @@ -186,7 +186,7 @@ instructions: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR } - { kinds: [register], role: use, register_class: GPR, register_bank: GPR } num_explicit_defs: 1 - flags: [pseudo, produces_code, allowed_pre_legalizer] + flags: [pseudo, produces_code, allowed_pre_legalizer, uses_custom_inserter] owner: instruction_select deadline: selected - @@ -201,7 +201,7 @@ instructions: - { kinds: [register], role: use, register_class: FPR32, register_bank: FPR } - { kinds: [register], role: use, register_class: FPR32, register_bank: FPR } num_explicit_defs: 1 - flags: [pseudo, produces_code, allowed_pre_legalizer] + flags: [pseudo, produces_code, allowed_pre_legalizer, uses_custom_inserter] owner: instruction_select deadline: selected - @@ -216,7 +216,7 @@ instructions: - { kinds: [register], role: use, register_class: FPR64, register_bank: FPR } - { kinds: [register], role: use, register_class: FPR64, register_bank: FPR } num_explicit_defs: 1 - flags: [pseudo, produces_code, allowed_pre_legalizer] + flags: [pseudo, produces_code, allowed_pre_legalizer, uses_custom_inserter] owner: instruction_select deadline: selected - diff --git a/backend/lib/Target/RISCV/RISCVPipeline.cpp b/backend/lib/Target/RISCV/RISCVPipeline.cpp index adcf22c..331d81f 100644 --- a/backend/lib/Target/RISCV/RISCVPipeline.cpp +++ b/backend/lib/Target/RISCV/RISCVPipeline.cpp @@ -7,6 +7,7 @@ #include "RISCV.h" #include "RISCVInstrInfo.h" #include "rcc/CodeGen/CFIInstrInserter.h" +#include "rcc/CodeGen/FinalizeISel.h" #include "rcc/CodeGen/GlobalISel/Combiner.h" #include "rcc/CodeGen/GlobalISel/InstructionSelect.h" #include "rcc/CodeGen/GlobalISel/Legalizer.h" @@ -57,7 +58,10 @@ template Added = addPass(Pipeline, Subtarget.getRegBankInfo()); if (!Added) return std::unexpected(Added.error()); - return addPass(Pipeline, Subtarget.getInstructionSelector()); + Added = addPass(Pipeline, Subtarget.getInstructionSelector()); + if (!Added) + return std::unexpected(Added.error()); + return addPass(Pipeline, finalizeISelInfo()); } [[nodiscard]] Expected addSSAExitPipeline(MachineFunctionPassManager &Pipeline, @@ -154,6 +158,11 @@ Expected addCanonicalPipeline(MachineFunctionPassManager &Pipeline, if (!Added) return std::unexpected(Added.error()); } + if (!Function.properties().has(MachineFunctionProperty::TiedOpsRewritten)) { + auto Added = addPass(Pipeline, finalizeISelInfo()); + if (!Added) + return std::unexpected(Added.error()); + } if (!Function.properties().has(MachineFunctionProperty::TiedOpsRewritten)) { auto Added = addSelectedSSAOptimizationPipeline( Pipeline, optimizationPipelineInfo(Subtarget, Options.DebugMachineScheduler, diff --git a/backend/utils/TableGen/Common/CodeGenInstruction.cpp b/backend/utils/TableGen/Common/CodeGenInstruction.cpp index 45b597c..a34f5ab 100644 --- a/backend/utils/TableGen/Common/CodeGenInstruction.cpp +++ b/backend/utils/TableGen/Common/CodeGenInstruction.cpp @@ -76,7 +76,7 @@ memoryRoleEnumerator(std::string_view Value) noexcept { [[nodiscard]] std::optional instructionFlagEnumerator(std::string_view Value) noexcept { - static constexpr std::array, 24> Flags = {{ + static constexpr std::array, 25> Flags = {{ {"terminator", "Terminator"}, {"branch", "Branch"}, {"indirect_branch", "IndirectBranch"}, @@ -101,6 +101,7 @@ instructionFlagEnumerator(std::string_view Value) noexcept { {"fake_use", "FakeUse"}, {"generic", "Generic"}, {"terminal_emission", "TerminalEmission"}, + {"uses_custom_inserter", "UsesCustomInserter"}, }}; const auto *const Position = std::ranges::find(Flags, Value, &decltype(Flags)::value_type::first); if (Position == Flags.end()) -- cgit v1.2.3