From 8be4d04455f70892a94d1e0798e266c948b4750a Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Fri, 14 Aug 2026 04:33:41 +0800 Subject: [CodeGen] Match LLVM Legalizer ownership --- backend/lib/CodeGen/GlobalISel/CMakeLists.txt | 14 + .../lib/CodeGen/GlobalISel/GISelChangeObserver.cpp | 61 +++ backend/lib/CodeGen/GlobalISel/Legalizer.cpp | 375 ++++++++----- backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp | 590 +++++++++++++++++++++ backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp | 477 +++++++++++++++++ 5 files changed, 1387 insertions(+), 130 deletions(-) create mode 100644 backend/lib/CodeGen/GlobalISel/GISelChangeObserver.cpp create mode 100644 backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp create mode 100644 backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp (limited to 'backend/lib/CodeGen/GlobalISel') diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt index 8a37497..b7064e3 100644 --- a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt +++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt @@ -2,16 +2,24 @@ set( RCCBackendGlobalISelSources + GISelChangeObserver.cpp InstructionSelect.cpp Legalizer.cpp + LegalizerHelper.cpp + LegalizerInfo.cpp RegBankSelect.cpp ) set( RCCBackendGlobalISelHeaders + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelWorkList.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/InstructionSelect.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/InstructionSelector.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/Legalizer.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/RegBankSelect.h" ) @@ -19,14 +27,20 @@ set( target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources}) rcc_backend_register_format_files( + "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp" ${RCCBackendGlobalISelHeaders} ) rcc_backend_register_tidy_files( + "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp" ) diff --git a/backend/lib/CodeGen/GlobalISel/GISelChangeObserver.cpp b/backend/lib/CodeGen/GlobalISel/GISelChangeObserver.cpp new file mode 100644 index 0000000..4ce1473 --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/GISelChangeObserver.cpp @@ -0,0 +1,61 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" + +#include + +namespace rcc { + +void GISelObserverWrapper::addObserver(GISelChangeObserver &Observer) { + Observers.push_back(&Observer); +} + +void GISelObserverWrapper::removeObserver(GISelChangeObserver &Observer) { + const auto Position = std::ranges::find(Observers, &Observer); + if (Position != Observers.end()) + Observers.erase(Position); +} + +void GISelObserverWrapper::clearObservers() noexcept { + Observers.clear(); +} + +void GISelObserverWrapper::erasingInstr(MachineInstr &Instruction) { + for (GISelChangeObserver *Observer : Observers) + Observer->erasingInstr(Instruction); +} + +void GISelObserverWrapper::createdInstr(MachineInstr &Instruction) { + for (GISelChangeObserver *Observer : Observers) + Observer->createdInstr(Instruction); +} + +void GISelObserverWrapper::changingInstr(MachineInstr &Instruction) { + for (GISelChangeObserver *Observer : Observers) + Observer->changingInstr(Instruction); +} + +void GISelObserverWrapper::changedInstr(MachineInstr &Instruction) { + for (GISelChangeObserver *Observer : Observers) + Observer->changedInstr(Instruction); +} + +void GISelObserverWrapper::handleInsertion(MachineInstr &Instruction) { + createdInstr(Instruction); +} + +void GISelObserverWrapper::handleRemoval(MachineInstr &Instruction) { + erasingInstr(Instruction); +} + +MachineFunctionDelegateInstaller::MachineFunctionDelegateInstaller( + MachineFunction &Function, MachineFunction::Delegate &Delegate) + : Function(&Function), Delegate(&Delegate) { + Function.setDelegate(Delegate); +} + +MachineFunctionDelegateInstaller::~MachineFunctionDelegateInstaller() { + Function->resetDelegate(*Delegate); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp index 83efb6a..d971b42 100644 --- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp +++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp @@ -2,6 +2,11 @@ #include "rcc/CodeGen/GlobalISel/Legalizer.h" +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/GlobalISel/GISelWorkList.h" +#include "rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h" +#include "rcc/CodeGen/GlobalISel/LegalizerHelper.h" #include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" @@ -10,8 +15,10 @@ #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" -#include +#include +#include #include +#include #include #include #include @@ -34,60 +41,122 @@ namespace { return Contract; } -struct OpcodeState final { - MachineInstrStableID Instruction; - Opcode OpcodeValue; - std::uint64_t OperandFingerprint = 0; +[[nodiscard]] std::vector layoutInstructions(MachineFunction &Function) { + std::vector Result; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) + Result.push_back(Instruction); + return Result; +} - friend bool operator==(const OpcodeState &Left, const OpcodeState &Right) noexcept = default; -}; +[[nodiscard]] bool isArtifact(const MachineInstr &Instruction) noexcept { + switch (static_cast(Instruction.opcode().value())) { + default: + return false; + case GenericOpcode::G_TRUNC: + case GenericOpcode::G_ZEXT: + case GenericOpcode::G_ANYEXT: + case GenericOpcode::G_SEXT: + case GenericOpcode::G_MERGE_VALUES: + case GenericOpcode::G_UNMERGE_VALUES: + case GenericOpcode::G_CONCAT_VECTORS: + case GenericOpcode::G_BUILD_VECTOR: + case GenericOpcode::G_EXTRACT: + case GenericOpcode::G_INSERT: + return true; + } +} + +using InstList = GISelWorkList<256>; +using ArtifactList = GISelWorkList<128>; + +class LegalizerWorkListManager final : public GISelChangeObserver { +public: + LegalizerWorkListManager(InstList &Instructions, ArtifactList &Artifacts) + : Instructions(Instructions), Artifacts(Artifacts) {} -struct OpcodeStateHash final { - [[nodiscard]] std::size_t operator()(const OpcodeState &State) const noexcept { - return std::hash{}(State.Instruction.value()) ^ - (std::hash{}(State.OpcodeValue.value()) << 1U) ^ - (std::hash{}(State.OperandFingerprint) << 2U); + void erasingInstr(MachineInstr &Instruction) override { + Instructions.remove(&Instruction); + Artifacts.remove(&Instruction); } -}; -void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept { - State ^= Value + 0x9e3779b97f4a7c15ULL + (State << 6U) + (State >> 2U); -} + void createdInstr(MachineInstr &Instruction) override { + createdOrChangedInstr(Instruction); + } + + void changingInstr(MachineInstr &) override {} -[[nodiscard]] std::uint64_t operandFingerprint(const MachineInstr &Instruction) noexcept { - std::uint64_t Result = 0xcbf29ce484222325ULL; - combineFingerprint(Result, Instruction.flags().rawValue()); - combineFingerprint(Result, Instruction.operandCount()); - for (const MachineOperand &Operand : Instruction.operands()) { - combineFingerprint(Result, static_cast(Operand.kind())); - combineFingerprint(Result, Operand.targetFlags()); - combineFingerprint(Result, Operand.registerFlags().rawValue()); - combineFingerprint(Result, Operand.subReg().value()); - if (const Register *Reg = Operand.getIf()) - combineFingerprint(Result, Reg->opaqueValue()); - else if (const std::int64_t *Immediate = Operand.getIf()) - combineFingerprint(Result, static_cast(*Immediate)); - else if (const auto *Integer = Operand.getIf()) - combineFingerprint(Result, Integer->Value.bitWidth()); - else if (const auto *Floating = Operand.getIf()) - combineFingerprint(Result, static_cast(Floating->Bits.semantics())); - else if (const auto *Block = Operand.getIf()) - combineFingerprint(Result, Block->Block == nullptr ? 0 : Block->Block->stableID().value()); + void changedInstr(MachineInstr &Instruction) override { + createdOrChangedInstr(Instruction); } - return Result; -} -[[nodiscard]] OpcodeState stateOf(const MachineInstr &Instruction) noexcept { - return {Instruction.stableID(), Instruction.opcode(), operandFingerprint(Instruction)}; -} +private: + void createdOrChangedInstr(MachineInstr &Instruction) { + if (!isGenericOpcode(Instruction.opcode())) + return; + if (isArtifact(Instruction)) + Artifacts.insert(&Instruction); + else + Instructions.insert(&Instruction); + } -[[nodiscard]] std::vector layoutInstructions(MachineFunction &Function) { - std::vector Result; + InstList &Instructions; + ArtifactList &Artifacts; +}; + +[[nodiscard]] std::vector reversePostOrderBlocks(MachineFunction &Function) { + struct TraversalFrame final { + MachineBasicBlock *Block = nullptr; + std::vector Successors; + std::size_t NextSuccessor = 0; + }; + + const auto makeFrame = [](MachineBasicBlock &Block) { + TraversalFrame Frame; + Frame.Block = &Block; + for (const MachineSuccessor &Successor : Block.successors()) { + if (Successor.Block != nullptr) + Frame.Successors.push_back(Successor.Block); + } + std::ranges::sort(Frame.Successors, {}, [](const MachineBasicBlock *Successor) { + return Successor->stableID().value(); + }); + return Frame; + }; + + std::vector Roots; for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) - for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; - Instruction = Instruction->next()) - Result.push_back(Instruction); - return Result; + Roots.push_back(Block); + std::ranges::sort(Roots, {}, + [](const MachineBasicBlock *Block) { return Block->stableID().value(); }); + if (MachineBasicBlock *Entry = Function.firstBlock(); Entry != nullptr) { + const auto Position = std::ranges::find(Roots, Entry); + if (Position != Roots.end()) + std::rotate(Roots.begin(), Position, std::next(Position)); + } + + std::vector PostOrder; + std::unordered_set Visited; + std::vector Stack; + for (MachineBasicBlock *Root : Roots) { + if (!Visited.insert(Root).second) + continue; + Stack.push_back(makeFrame(*Root)); + while (!Stack.empty()) { + TraversalFrame &Frame = Stack.back(); + if (Frame.NextSuccessor < Frame.Successors.size()) { + MachineBasicBlock *Successor = Frame.Successors[Frame.NextSuccessor++]; + if (Visited.insert(Successor).second) + Stack.push_back(makeFrame(*Successor)); + continue; + } + PostOrder.push_back(Frame.Block); + Stack.pop_back(); + } + } + std::ranges::reverse(PostOrder); + return PostOrder; } [[nodiscard]] Expected requireProperties(const MachineFunction &Function, @@ -202,91 +271,136 @@ Expected Legalizer::run(MachineFunction &Function, Expected Legalizer::runImplementation(MachineFunction &Function, const TargetDescription &Target, MachineActionReplay &Actions) { - MachinePassResult Result; - std::unordered_set SeenStates; - - std::vector Worklist = layoutInstructions(Function); - std::unordered_set PendingInstructions; - for (const MachineInstr *Instruction : Worklist) - PendingInstructions.insert(Instruction->stableID()); - for (std::size_t Index = 0; Index < Worklist.size(); ++Index) { - MachineInstr *Instruction = Worklist[Index]; - if (Instruction != nullptr) - PendingInstructions.erase(Instruction->stableID()); - if (Instruction == nullptr || Instruction->parent() == nullptr) - continue; + InstList InstructionWorklist; + ArtifactList ArtifactWorklist; + std::vector RetryList; - const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); - if (Descriptor == nullptr) - return std::unexpected( - passFailure("legalizer encountered an unknown instruction descriptor")); - if (!Descriptor->Flags.has(InstructionFlag::Generic)) - continue; + for (MachineBasicBlock *Block : reversePostOrderBlocks(Function)) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (!isGenericOpcode(Instruction->opcode())) + continue; + if (isArtifact(*Instruction)) + ArtifactWorklist.deferredInsert(Instruction); + else + InstructionWorklist.deferredInsert(Instruction); + } + } + ArtifactWorklist.finalize(); + InstructionWorklist.finalize(); - auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo()); - if (!Validation) - return std::unexpected(withErrorContext(Validation.error(), "legalizer input is invalid: ")); + LegalizerWorkListManager WorkListObserver(InstructionWorklist, ArtifactWorklist); + GISelObserverWrapper Observer(WorkListObserver); + MachineFunctionDelegateInstaller ObserverInstaller(Function, Observer); + MachineIRBuilder Builder(Function, Target); + LegalizerHelper Helper(Function, *Info, Observer, Builder); + LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info); - auto Action = Info->classify(*Instruction, Function, Target); - if (!Action) - return std::unexpected(Action.error()); - if (*Action == LegalizationAction::Legal) - continue; - if (*Action == LegalizationAction::Unsupported) { - return std::unexpected( - passFailure("target legalizer rejected generic instruction '" + Descriptor->Name + "'", - ErrorCode::Unsupported)); - } + do { + while (!InstructionWorklist.empty()) { + MachineInstr *Instruction = InstructionWorklist.popBack(); + if (Instruction == nullptr || Instruction->parent() == nullptr) + continue; - const OpcodeState Before = stateOf(*Instruction); - if (!SeenStates.insert(Before).second) - return std::unexpected( - passFailure("target legalizer entered a repeated state for '" + Descriptor->Name + "'", - ErrorCode::InternalError)); + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return std::unexpected( + passFailure("legalizer encountered an unknown instruction descriptor")); + if (!Descriptor->Flags.has(InstructionFlag::Generic)) + continue; - auto LoweringValidation = Info->validateLowering(*Instruction, Function, Target, *Action); - if (!LoweringValidation) - return std::unexpected( - withErrorContext(LoweringValidation.error(), "legalizer lowering precondition failed: ")); - std::string Rule = "legalize."; - Rule.append(legalizationActionName(*Action)); - Rule.push_back('.'); - Rule.append(Descriptor->Name); - auto Accepted = Actions.request(Rule, Function, Instruction->stableID()); - if (!Accepted) - return std::unexpected(Accepted.error()); - if (!*Accepted) { - return std::unexpected( - passFailure("required legalizer action was rejected for '" + Descriptor->Name + "'", - ErrorCode::VerificationError)); + auto Validation = Target.validateInstruction(*Instruction, Function.registerInfo()); + if (!Validation) { + return std::unexpected( + withErrorContext(Validation.error(), "legalizer input is invalid: ")); + } + + auto Decision = Info->getDecision(*Instruction, Function, Target); + if (!Decision) + return std::unexpected(Decision.error()); + if (Decision->Action == LegalizationAction::Legal) + continue; + if (Decision->Action == LegalizationAction::Unsupported) { + if (isArtifact(*Instruction)) { + RetryList.push_back(Instruction); + continue; + } + return std::unexpected( + passFailure("target legalizer rejected generic instruction '" + Descriptor->Name + "'", + ErrorCode::Unsupported)); + } + + auto LoweringValidation = Info->validateLowering(*Instruction, Function, Target, *Decision); + if (!LoweringValidation) { + return std::unexpected(withErrorContext(LoweringValidation.error(), + "legalizer lowering precondition failed: ")); + } + std::string Rule = "legalize."; + Rule.append(legalizationActionName(Decision->Action)); + Rule.push_back('.'); + Rule.append(Descriptor->Name); + auto Accepted = Actions.request(Rule, Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return std::unexpected( + passFailure("required legalizer action was rejected for '" + Descriptor->Name + "'", + ErrorCode::VerificationError)); + } + Expected Lowered = Helper.legalize(*Instruction, *Decision); + if (!Lowered) { + if (Lowered.error().code() == ErrorCode::Unsupported && Instruction->parent() != nullptr && + isArtifact(*Instruction)) { + RetryList.push_back(Instruction); + continue; + } + return std::unexpected(Lowered.error()); + } + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); } - auto Lowered = Info->lower(*Instruction, Function, Target, *Action); - if (!Lowered) - return std::unexpected(Lowered.error()); - const bool InstructionWasErased = Instruction->parent() == nullptr; - if (!InstructionWasErased) { - const OpcodeState After = stateOf(*Instruction); - if (After == Before) - return std::unexpected(passFailure("target legalizer made no observable progress for '" + - Descriptor->Name + "'", - ErrorCode::InternalError)); + + if (!RetryList.empty()) { + if (!ArtifactWorklist.empty()) { + for (MachineInstr *Instruction : RetryList) + ArtifactWorklist.insert(Instruction); + RetryList.clear(); + } else { + MachineInstr *Instruction = RetryList.front(); + const InstructionDescriptor *Descriptor = + Instruction == nullptr ? nullptr : Target.instructionDescriptor(Instruction->opcode()); + return std::unexpected(passFailure( + "target legalizer rejected generic artifact '" + + std::string(Descriptor == nullptr ? "" : Descriptor->Name) + "'", + ErrorCode::Unsupported)); + } } - Result.Changed = true; - Result.Changes.add(MachinePassChange::Instructions); - - const std::vector Current = layoutInstructions(Function); - for (MachineInstr *Candidate : Current) { - const InstructionDescriptor *CandidateDescriptor = - Target.instructionDescriptor(Candidate->opcode()); - if (CandidateDescriptor == nullptr) - return std::unexpected(passFailure("legalizer produced an unknown instruction descriptor")); - if (CandidateDescriptor->Flags.has(InstructionFlag::Generic) && - PendingInstructions.insert(Candidate->stableID()).second) { - Worklist.push_back(Candidate); + + while (!ArtifactWorklist.empty()) { + MachineInstr *Instruction = ArtifactWorklist.popBack(); + if (Instruction == nullptr || Instruction->parent() == nullptr) + continue; + std::vector DeadInstructions; + auto Combined = + ArtifactCombiner.tryCombineInstruction(*Instruction, DeadInstructions, Observer); + if (!Combined) + return std::unexpected(Combined.error()); + if (*Combined) { + for (MachineInstr *Dead : DeadInstructions) { + if (Dead == nullptr || Dead->parent() == nullptr) + continue; + auto Removed = Dead->parent()->removeInstruction(*Dead); + if (!Removed) + return std::unexpected(Removed.error()); + } + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + continue; } + InstructionWorklist.insert(Instruction); } - } + } while (!InstructionWorklist.empty()); for (MachineInstr *Instruction : layoutInstructions(Function)) { const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); @@ -294,15 +408,16 @@ Expected Legalizer::runImplementation(MachineFunction &Functi return std::unexpected(passFailure("legalizer produced an unknown instruction descriptor")); if (!Descriptor->Flags.has(InstructionFlag::Generic)) continue; - auto Action = Info->classify(*Instruction, Function, Target); - if (!Action) - return std::unexpected(Action.error()); - if (*Action != LegalizationAction::Legal) - return std::unexpected( - passFailure("legalizer reached a fixed point with an illegal generic instruction '" + - Descriptor->Name + "'", - *Action == LegalizationAction::Unsupported ? ErrorCode::Unsupported - : ErrorCode::InternalError)); + auto Decision = Info->getDecision(*Instruction, Function, Target); + if (!Decision) + return std::unexpected(Decision.error()); + if (Decision->Action != LegalizationAction::Legal && + Decision->Action != LegalizationAction::Custom) + return std::unexpected(passFailure( + "legalizer reached a fixed point with an illegal generic instruction '" + + Descriptor->Name + "'", + Decision->Action == LegalizationAction::Unsupported ? ErrorCode::Unsupported + : ErrorCode::InternalError)); auto FinalValidation = Target.validateInstruction(*Instruction, Function.registerInfo()); if (!FinalValidation) return std::unexpected( diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp new file mode 100644 index 0000000..1e52214 --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp @@ -0,0 +1,590 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/LegalizerHelper.h" + +#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/MachineBasicBlock.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 +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +struct ScalarLayout final { + std::uint64_t StoreSize = 0; + std::uint64_t AllocationSize = 0; + std::uint64_t ABIAlignment = 0; +}; + +[[nodiscard]] Expected signedImmediate(const MachineOperand &Operand) { + if (const std::int64_t *Value = Operand.getIf()) + return *Value; + const auto *Integer = Operand.getIf(); + if (Integer == nullptr || Integer->Value.bitWidth() == 0 || Integer->Value.bitWidth() > 64) { + return makeUnexpected(ErrorCode::VerificationError, + "legalizer requires an immediate no wider than 64 bits"); + } + std::uint64_t Raw = Integer->Value.words().empty() ? 0 : Integer->Value.words().front(); + const std::uint32_t Width = Integer->Value.bitWidth(); + if (Width < 64 && (Raw & (std::uint64_t{1} << (Width - 1U))) != 0) + Raw |= ~std::uint64_t{0} << Width; + return std::bit_cast(Raw); +} + +[[nodiscard]] std::optional scalarLayout(LowLevelType Type) noexcept { + if (!Type.isScalarValue() || Type.scalarBitWidth() == 0) + return std::nullopt; + const std::uint64_t StoreSize = (Type.scalarBitWidth() + 7U) / 8U; + const std::uint64_t AllocationSize = std::bit_ceil(StoreSize); + return ScalarLayout{StoreSize, AllocationSize, std::min(AllocationSize, 8)}; +} + +[[nodiscard]] Expected createMemoryAccess(MachineFunction &Function, + MemoryAccessFlag Access, + LowLevelType Type, + const ScalarLayout &Layout) { + auto Size = MemorySize::fixed(Layout.StoreSize); + auto Align = Alignment::create(Layout.ABIAlignment); + if (!Size || !Align) + return makeUnexpected(ErrorCode::InternalError, + "legalizer cannot represent scalar memory layout"); + MachineMemOperandDesc Description; + Description.Accesses = {Access}; + Description.Size = *Size; + Description.MemoryType = Type; + Description.Align = *Align; + return Function.createMemOperand(std::move(Description)); +} + +[[nodiscard]] Expected buildConstantBefore(MachineIRBuilder &Builder, + MachineInstr &Anchor, LowLevelType Type, + std::uint64_t Value) { + auto Result = Builder.function().registerInfo().createVirtualRegister(Type); + if (!Result) + return std::unexpected(Result.error()); + auto Immediate = APInt::fromUnsigned(Type.scalarBitWidth(), Value); + if (!Immediate) + return std::unexpected(Immediate.error()); + if (auto Point = Builder.setInsertPointBefore(Anchor); !Point) + return std::unexpected(Point.error()); + auto Built = Builder.buildConstant(*Result, std::move(*Immediate)); + if (!Built) + return std::unexpected(Built.error()); + return *Result; +} + +[[nodiscard]] Expected buildBinaryBefore(MachineIRBuilder &Builder, MachineInstr &Anchor, + GenericOpcode Generic, LowLevelType Type, + Register Left, Register Right) { + auto Result = Builder.function().registerInfo().createVirtualRegister(Type); + if (!Result) + return std::unexpected(Result.error()); + if (auto Point = Builder.setInsertPointBefore(Anchor); !Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(opcode(Generic)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Added = Pending->addDef(*Result); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(Left); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(Right); !Added) + return std::unexpected(Added.error()); + auto Built = Pending->build(); + if (!Built) + return std::unexpected(Built.error()); + return *Result; +} + +} // namespace + +LegalizerHelper::LegalizerHelper(MachineFunction &Function, const LegalizerInfo &Info, + GISelChangeObserver &Observer, MachineIRBuilder &MIRBuilder) + : MIRBuilder(MIRBuilder), Observer(Observer), Function(Function), MRI(Function.registerInfo()), + Info(Info) {} + +Expected LegalizerHelper::widenScalarSrc(MachineInstr &Instruction, LowLevelType WideType, + std::size_t OperandIndex, + GenericOpcode ExtensionOpcode) { + MachineOperand *Operand = Instruction.operandAt(OperandIndex); + const Register *Source = Operand == nullptr ? nullptr : Operand->getIf(); + if (Source == nullptr || !Source->isVirtual() || !Operand->isUse()) + return makeUnexpected(ErrorCode::VerificationError, + "scalar widening source is not a virtual-register use"); + + auto WideSource = MRI.createVirtualRegister(WideType); + if (!WideSource) + return std::unexpected(WideSource.error()); + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + auto Extension = MIRBuilder.buildInstr(opcode(ExtensionOpcode)); + if (!Extension) + return std::unexpected(Extension.error()); + if (auto Added = Extension->addDef(*WideSource); !Added) + return std::unexpected(Added.error()); + if (auto Added = Extension->addUse(*Source); !Added) + return std::unexpected(Added.error()); + if (auto Built = Extension->build(); !Built) + return std::unexpected(Built.error()); + return Operand->setRegister(*WideSource); +} + +Expected LegalizerHelper::widenScalarDst(MachineInstr &Instruction, LowLevelType WideType, + std::size_t OperandIndex, + GenericOpcode TruncOpcode) { + MachineOperand *Operand = Instruction.operandAt(OperandIndex); + const Register *Destination = Operand == nullptr ? nullptr : Operand->getIf(); + if (Destination == nullptr || !Destination->isVirtual() || !Operand->isDef()) + return makeUnexpected(ErrorCode::VerificationError, + "scalar widening destination is not a virtual-register definition"); + + auto WideDestination = MRI.createVirtualRegister(WideType); + if (!WideDestination) + return std::unexpected(WideDestination.error()); + if (auto Point = MIRBuilder.setInsertPointAfter(Instruction); !Point) + return std::unexpected(Point.error()); + auto Truncation = MIRBuilder.buildInstr(opcode(TruncOpcode)); + if (!Truncation) + return std::unexpected(Truncation.error()); + if (auto Added = Truncation->addDef(*Destination); !Added) + return std::unexpected(Added.error()); + if (auto Added = Truncation->addUse(*WideDestination); !Added) + return std::unexpected(Added.error()); + if (auto Built = Truncation->build(); !Built) + return std::unexpected(Built.error()); + return Operand->setRegister(*WideDestination); +} + +Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType WideType) { + auto Query = LegalizerInfo::buildQuery(Instruction, Function, MIRBuilder.target()); + if (!Query) + return std::unexpected(Query.error()); + if (!WideType.isCategoryNeutralScalar() || TypeIndex >= Query->Types.size() || + !Query->Types[TypeIndex].isCategoryNeutralScalar() || + WideType.scalarBitWidth() <= Query->Types[TypeIndex].scalarBitWidth()) { + return makeUnexpected(ErrorCode::VerificationError, + "scalar widening has an invalid type index or target type"); + } + + const auto widenSource = [&](std::size_t OperandIndex, GenericOpcode ExtensionOpcode) { + return widenScalarSrc(Instruction, WideType, OperandIndex, ExtensionOpcode); + }; + const auto widenDestination = [&](std::size_t OperandIndex = 0, + GenericOpcode TruncOpcode = GenericOpcode::G_TRUNC) { + return widenScalarDst(Instruction, WideType, OperandIndex, TruncOpcode); + }; + const auto apply = [](Expected Result) -> Expected { + if (!Result) + return std::unexpected(Result.error()); + return {}; + }; + + Observer.changingInstr(Instruction); + switch (static_cast(Instruction.opcode().value())) { + case GenericOpcode::G_ATOMICRMW_XCHG: + case GenericOpcode::G_ATOMICRMW_ADD: + case GenericOpcode::G_ATOMICRMW_SUB: + case GenericOpcode::G_ATOMICRMW_AND: + case GenericOpcode::G_ATOMICRMW_OR: + case GenericOpcode::G_ATOMICRMW_XOR: + case GenericOpcode::G_ATOMICRMW_MIN: + case GenericOpcode::G_ATOMICRMW_MAX: + case GenericOpcode::G_ATOMICRMW_UMIN: + case GenericOpcode::G_ATOMICRMW_UMAX: + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "atomic RMW value widening has an invalid type index"); + if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + + case GenericOpcode::G_ATOMIC_CMPXCHG: + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "compare-exchange widening has an invalid type index"); + if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + + case GenericOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS: + if (TypeIndex == 0) { + if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenSource(4, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + } + if (TypeIndex != 1) + return makeUnexpected(ErrorCode::VerificationError, + "compare-exchange success widening has an invalid type index"); + if (auto Result = apply(widenDestination(1)); !Result) + return Result; + break; + + case GenericOpcode::G_ADD: + case GenericOpcode::G_SUB: + case GenericOpcode::G_MUL: + case GenericOpcode::G_AND: + case GenericOpcode::G_OR: + case GenericOpcode::G_XOR: + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "binary operation widening has an invalid type index"); + if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + + case GenericOpcode::G_SDIV: + case GenericOpcode::G_SREM: + case GenericOpcode::G_SMIN: + case GenericOpcode::G_SMAX: + case GenericOpcode::G_ABDS: + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "signed operation widening has an invalid type index"); + if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result) + return Result; + if (auto Result = apply(widenSource(2, GenericOpcode::G_SEXT)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + + case GenericOpcode::G_UDIV: + case GenericOpcode::G_UREM: + case GenericOpcode::G_UMIN: + case GenericOpcode::G_UMAX: + case GenericOpcode::G_ABDU: + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "unsigned operation widening has an invalid type index"); + if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result) + return Result; + if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + + case GenericOpcode::G_SHL: + case GenericOpcode::G_LSHR: + case GenericOpcode::G_ASHR: + if (TypeIndex == 0) { + GenericOpcode ExtensionOpcode = GenericOpcode::G_ANYEXT; + if (Instruction.opcode() == opcode(GenericOpcode::G_LSHR)) + ExtensionOpcode = GenericOpcode::G_ZEXT; + else if (Instruction.opcode() == opcode(GenericOpcode::G_ASHR)) + ExtensionOpcode = GenericOpcode::G_SEXT; + if (auto Result = apply(widenSource(1, ExtensionOpcode)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + } + if (TypeIndex != 1) + return makeUnexpected(ErrorCode::VerificationError, + "shift widening has an invalid type index"); + if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result) + return Result; + break; + + case GenericOpcode::G_ROTL: + case GenericOpcode::G_ROTR: + if (TypeIndex != 1) + return makeUnexpected(ErrorCode::Unsupported, "rotate value widening is not defined"); + if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result) + return Result; + break; + + case GenericOpcode::G_FREEZE: + case GenericOpcode::G_CONSTANT_FOLD_BARRIER: + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "unary operation widening has an invalid type index"); + if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + + case GenericOpcode::G_ABS: + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "absolute-value widening has an invalid type index"); + if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + + case GenericOpcode::G_SELECT: + if (TypeIndex == 0) { + if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result) + return Result; + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + } + if (TypeIndex != 1) + return makeUnexpected(ErrorCode::VerificationError, + "select widening has an invalid type index"); + if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result) + return Result; + break; + + case GenericOpcode::G_FPEXT: + if (TypeIndex != 1) + return makeUnexpected(ErrorCode::Unsupported, + "floating-point extension destination widening is not defined"); + if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result) + return Result; + break; + + case GenericOpcode::G_FPTOSI: + case GenericOpcode::G_FPTOUI: + case GenericOpcode::G_INTRINSIC_LRINT: + case GenericOpcode::G_INTRINSIC_LLRINT: + case GenericOpcode::G_IS_FPCLASS: + if (TypeIndex == 0) { + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + } + if (TypeIndex != 1) + return makeUnexpected(ErrorCode::VerificationError, + "floating-to-integer widening has an invalid type index"); + if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result) + return Result; + break; + + case GenericOpcode::G_SITOFP: + case GenericOpcode::G_UITOFP: + if (TypeIndex == 0) { + if (auto Result = apply(widenDestination(0, GenericOpcode::G_FPTRUNC)); !Result) + return Result; + break; + } + if (TypeIndex != 1) + return makeUnexpected(ErrorCode::VerificationError, + "integer-to-floating widening has an invalid type index"); + if (auto Result = apply(widenSource(1, Instruction.opcode() == opcode(GenericOpcode::G_SITOFP) + ? GenericOpcode::G_SEXT + : GenericOpcode::G_ZEXT)); + !Result) + return Result; + break; + + default: + return makeUnexpected(ErrorCode::Unsupported, + "scalar widening is not implemented for this opcode"); + } + + Observer.changedInstr(Instruction); + return {}; +} + +Expected LegalizerHelper::lowerVAArg(MachineInstr &Instruction) { + if (Instruction.opcode() != opcode(GenericOpcode::G_VAARG) || Instruction.operandCount() != 3 || + !Instruction.memOperands().empty()) { + return makeUnexpected(ErrorCode::VerificationError, "G_VAARG has invalid operands"); + } + + MachineOperand *DestinationOperand = Instruction.operandAt(0); + MachineOperand *ListOperand = Instruction.operandAt(1); + MachineOperand *AlignmentOperand = Instruction.operandAt(2); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf(); + const Register *ListPointer = ListOperand == nullptr ? nullptr : ListOperand->getIf(); + if (Destination == nullptr || ListPointer == nullptr || !Destination->isVirtual() || + !ListPointer->isVirtual() || !DestinationOperand->isDef() || !ListOperand->isUse() || + AlignmentOperand == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "G_VAARG requires virtual-register operands"); + } + + auto DestinationInfo = MRI.virtualRegisterInfo(*Destination); + auto PointerInfo = MRI.virtualRegisterInfo(*ListPointer); + auto RequestedAlignment = signedImmediate(*AlignmentOperand); + if (!DestinationInfo || !PointerInfo || !DestinationInfo->get().Type || + !PointerInfo->get().Type || !RequestedAlignment || *RequestedAlignment <= 0 || + !std::has_single_bit(static_cast(*RequestedAlignment))) { + return makeUnexpected(ErrorCode::VerificationError, + "G_VAARG has invalid type or alignment information"); + } + + const LowLevelType DestinationType = *DestinationInfo->get().Type; + const LowLevelType PointerType = *PointerInfo->get().Type; + const auto DestinationLayout = scalarLayout(DestinationType); + const auto PointerLayout = scalarLayout(PointerType); + if (!DestinationLayout || !PointerLayout || !PointerType.isPointer()) { + return makeUnexpected(ErrorCode::Unsupported, + "G_VAARG requires scalar result and pointer list types"); + } + + auto ListLoadMemory = + createMemoryAccess(Function, MemoryAccessFlag::Load, PointerType, *PointerLayout); + auto ListStoreMemory = + createMemoryAccess(Function, MemoryAccessFlag::Store, PointerType, *PointerLayout); + if (!ListLoadMemory) + return std::unexpected(ListLoadMemory.error()); + if (!ListStoreMemory) + return std::unexpected(ListStoreMemory.error()); + + auto CurrentList = MRI.createVirtualRegister(PointerType); + if (!CurrentList) + return std::unexpected(CurrentList.error()); + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + auto ListLoad = MIRBuilder.buildInstr(opcode(GenericOpcode::G_LOAD)); + if (!ListLoad) + return std::unexpected(ListLoad.error()); + if (auto Added = ListLoad->addDef(*CurrentList); !Added) + return std::unexpected(Added.error()); + if (auto Added = ListLoad->addUse(*ListPointer); !Added) + return std::unexpected(Added.error()); + if (auto Added = ListLoad->addMemOperand(**ListLoadMemory); !Added) + return std::unexpected(Added.error()); + if (auto Built = ListLoad->build(); !Built) + return std::unexpected(Built.error()); + + Register ValueAddress = *CurrentList; + const std::uint64_t AlignmentValue = static_cast(*RequestedAlignment); + auto PointerScalarType = LowLevelType::makeCategoryNeutralScalar(PointerType.scalarBitWidth()); + if (!PointerScalarType) + return std::unexpected(PointerScalarType.error()); + if (AlignmentValue > 1) { + auto AlignmentOffset = + buildConstantBefore(MIRBuilder, Instruction, *PointerScalarType, AlignmentValue - 1U); + if (!AlignmentOffset) + return std::unexpected(AlignmentOffset.error()); + auto BiasedAddress = buildBinaryBefore(MIRBuilder, Instruction, GenericOpcode::G_PTR_ADD, + PointerType, ValueAddress, *AlignmentOffset); + if (!BiasedAddress) + return std::unexpected(BiasedAddress.error()); + auto AlignmentMask = + buildConstantBefore(MIRBuilder, Instruction, *PointerScalarType, ~(AlignmentValue - 1U)); + if (!AlignmentMask) + return std::unexpected(AlignmentMask.error()); + auto AlignedAddress = buildBinaryBefore(MIRBuilder, Instruction, GenericOpcode::G_PTRMASK, + PointerType, *BiasedAddress, *AlignmentMask); + if (!AlignedAddress) + return std::unexpected(AlignedAddress.error()); + ValueAddress = *AlignedAddress; + } + + auto Increment = buildConstantBefore(MIRBuilder, Instruction, *PointerScalarType, + DestinationLayout->AllocationSize); + if (!Increment) + return std::unexpected(Increment.error()); + auto NextList = buildBinaryBefore(MIRBuilder, Instruction, GenericOpcode::G_PTR_ADD, PointerType, + ValueAddress, *Increment); + if (!NextList) + return std::unexpected(NextList.error()); + + auto ListStore = MIRBuilder.buildInstr(opcode(GenericOpcode::G_STORE)); + if (!ListStore) + return std::unexpected(ListStore.error()); + if (auto Added = ListStore->addUse(*NextList); !Added) + return std::unexpected(Added.error()); + if (auto Added = ListStore->addUse(*ListPointer); !Added) + return std::unexpected(Added.error()); + if (auto Added = ListStore->addMemOperand(**ListStoreMemory); !Added) + return std::unexpected(Added.error()); + if (auto Built = ListStore->build(); !Built) + return std::unexpected(Built.error()); + + if (!MRI.useEmpty(*Destination)) { + auto ValueLoadMemory = + createMemoryAccess(Function, MemoryAccessFlag::Load, DestinationType, *DestinationLayout); + if (!ValueLoadMemory) + return std::unexpected(ValueLoadMemory.error()); + auto ValueLoad = MIRBuilder.buildInstr(opcode(GenericOpcode::G_LOAD)); + if (!ValueLoad) + return std::unexpected(ValueLoad.error()); + if (auto Added = ValueLoad->addDef(*Destination); !Added) + return std::unexpected(Added.error()); + if (auto Added = ValueLoad->addUse(ValueAddress); !Added) + return std::unexpected(Added.error()); + if (auto Added = ValueLoad->addMemOperand(**ValueLoadMemory); !Added) + return std::unexpected(Added.error()); + if (auto Built = ValueLoad->build(); !Built) + return std::unexpected(Built.error()); + } + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::VerificationError, "G_VAARG is detached during legalization"); + return Block->removeInstruction(Instruction); +} + +Expected LegalizerHelper::lower(MachineInstr &Instruction, + const LegalizationDecision &Decision) { + if (Decision.Action != LegalizationAction::Lower) + return makeUnexpected(ErrorCode::InvalidArgument, + "lower received a non-lower legalization action"); + switch (static_cast(Instruction.opcode().value())) { + case GenericOpcode::G_VAARG: + return lowerVAArg(Instruction); + default: { + const InstructionDescriptor *Descriptor = + MIRBuilder.target().instructionDescriptor(Instruction.opcode()); + const std::string_view Name = + Descriptor == nullptr ? std::string_view{""} : Descriptor->Name; + return makeUnexpected(ErrorCode::Unsupported, + "generic lowering is not implemented for opcode '" + std::string(Name) + + "'"); + } + } +} + +Expected LegalizerHelper::legalize(MachineInstr &Instruction, + const LegalizationDecision &Decision) { + switch (Decision.Action) { + case LegalizationAction::WidenScalar: + return widenScalar(Instruction, Decision.TypeIndex, Decision.NewType); + case LegalizationAction::Custom: + return Info.legalizeCustom(*this, Instruction, Decision); + case LegalizationAction::Lower: + return lower(Instruction, Decision); + case LegalizationAction::Legal: + return {}; + case LegalizationAction::Unsupported: + case LegalizationAction::Libcall: + case LegalizationAction::NarrowScalar: + case LegalizationAction::MoreElements: + case LegalizationAction::FewerElements: + case LegalizationAction::Bitcast: + case LegalizationAction::ChangeElementType: + case LegalizationAction::ChangeAddressSpace: + return makeUnexpected(ErrorCode::Unsupported, + "legalizer helper does not implement the requested action"); + } + return makeUnexpected(ErrorCode::InternalError, "unknown legalization action"); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp new file mode 100644 index 0000000..7d9e6ff --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp @@ -0,0 +1,477 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/LegalizerInfo.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.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 + +namespace rcc { +namespace { + +[[nodiscard]] LegalityPredicate typeInSet(std::size_t TypeIndex, std::vector Types) { + return [TypeIndex, Types = std::move(Types)](const LegalizationQuery &Query) { + return TypeIndex < Query.Types.size() && + std::ranges::find(Types, Query.Types[TypeIndex]) != Types.end(); + }; +} + +[[nodiscard]] LegalityPredicate +typePairInSet(std::vector> Types) { + return [Types = std::move(Types)](const LegalizationQuery &Query) { + return Query.Types.size() >= 2 && + std::ranges::find(Types, std::pair{Query.Types[0], Query.Types[1]}) != Types.end(); + }; +} + +[[nodiscard]] LegalityPredicate +typeTripleInSet(std::vector> Types) { + return [Types = std::move(Types)](const LegalizationQuery &Query) { + return Query.Types.size() >= 3 && + std::ranges::find(Types, std::tuple{Query.Types[0], Query.Types[1], Query.Types[2]}) != + Types.end(); + }; +} + +[[nodiscard]] LowLevelType scalarType(std::uint32_t BitWidth) { + auto Type = LowLevelType::makeCategoryNeutralScalar(BitWidth); + return Type ? *Type : LowLevelType{}; +} + +[[nodiscard]] std::uint32_t nextPowerOfTwo(std::uint32_t Width, std::uint32_t MinimumBitWidth) { + return std::max(std::bit_ceil(Width), MinimumBitWidth); +} + +[[nodiscard]] bool memoryRuleMatches(const LegalizationQuery &Query, + const LegalizeMemoryRule &Rule) { + if (Query.Types.size() < 2 || Query.MemoryOperands.size() != 1 || + Query.Types[0] != Rule.ValueType || Query.Types[1] != Rule.AddressType) + return false; + const LegalizationMemoryDesc &Memory = Query.MemoryOperands.front(); + if (Memory.AlignmentInBits < Rule.MinimumAlignmentInBits) + return false; + if (Memory.Type) + return Memory.Type->minimumBitWidth() == Rule.MemoryType.minimumBitWidth(); + return Memory.Size.isKnown() && !Memory.Size.isScalable() && + Memory.Size.minimumBytes() * 8U == Rule.MemoryType.scalarBitWidth(); +} + +} // namespace + +LegalizeRule::LegalizeRule(LegalityPredicate Predicate, LegalizationAction Action, + LegalizeMutation Mutation) + : Predicate(std::move(Predicate)), Action(Action), Mutation(std::move(Mutation)) {} + +bool LegalizeRule::matches(const LegalizationQuery &Query) const { + return Predicate(Query); +} + +LegalizationDecision LegalizeRule::apply(const LegalizationQuery &Query) const { + if (!Mutation) + return {.Action = Action, .TypeIndex = 0, .NewType = {}}; + auto [TypeIndex, NewType] = Mutation(Query); + return {.Action = Action, .TypeIndex = TypeIndex, .NewType = NewType}; +} + +LegalizeRuleSet &LegalizeRuleSet::actionIf(LegalizationAction Action, LegalityPredicate Predicate, + LegalizeMutation Mutation) { + Rules.emplace_back(std::move(Predicate), Action, std::move(Mutation)); + return *this; +} + +LegalizeRuleSet &LegalizeRuleSet::actionFor(LegalizationAction Action, + std::initializer_list Types) { + return actionIf(Action, typeInSet(0, std::vector(Types))); +} + +LegalizeRuleSet & +LegalizeRuleSet::actionFor(LegalizationAction Action, + std::initializer_list> Types) { + return actionIf(Action, typePairInSet(std::vector>(Types))); +} + +LegalizeRuleSet &LegalizeRuleSet::actionFor( + LegalizationAction Action, + std::initializer_list> Types) { + return actionIf( + Action, + typeTripleInSet(std::vector>(Types))); +} + +LegalizeRuleSet &LegalizeRuleSet::legalIf(LegalityPredicate Predicate) { + return actionIf(LegalizationAction::Legal, std::move(Predicate)); +} + +LegalizeRuleSet &LegalizeRuleSet::customIf(LegalityPredicate Predicate) { + return actionIf(LegalizationAction::Custom, std::move(Predicate)); +} + +LegalizeRuleSet &LegalizeRuleSet::lowerIf(LegalityPredicate Predicate) { + return actionIf(LegalizationAction::Lower, std::move(Predicate)); +} + +LegalizeRuleSet &LegalizeRuleSet::libcallIf(LegalityPredicate Predicate) { + return actionIf(LegalizationAction::Libcall, std::move(Predicate)); +} + +LegalizeRuleSet &LegalizeRuleSet::unsupportedIf(LegalityPredicate Predicate) { + return actionIf(LegalizationAction::Unsupported, std::move(Predicate)); +} + +LegalizeRuleSet &LegalizeRuleSet::widenScalarIf(LegalityPredicate Predicate, + LegalizeMutation Mutation) { + return actionIf(LegalizationAction::WidenScalar, std::move(Predicate), std::move(Mutation)); +} + +LegalizeRuleSet &LegalizeRuleSet::narrowScalarIf(LegalityPredicate Predicate, + LegalizeMutation Mutation) { + return actionIf(LegalizationAction::NarrowScalar, std::move(Predicate), std::move(Mutation)); +} + +LegalizeRuleSet &LegalizeRuleSet::moreElementsIf(LegalityPredicate Predicate, + LegalizeMutation Mutation) { + return actionIf(LegalizationAction::MoreElements, std::move(Predicate), std::move(Mutation)); +} + +LegalizeRuleSet &LegalizeRuleSet::fewerElementsIf(LegalityPredicate Predicate, + LegalizeMutation Mutation) { + return actionIf(LegalizationAction::FewerElements, std::move(Predicate), std::move(Mutation)); +} + +LegalizeRuleSet &LegalizeRuleSet::bitcastIf(LegalityPredicate Predicate, + LegalizeMutation Mutation) { + return actionIf(LegalizationAction::Bitcast, std::move(Predicate), std::move(Mutation)); +} + +LegalizeRuleSet &LegalizeRuleSet::legalFor(std::initializer_list Types) { + return actionFor(LegalizationAction::Legal, Types); +} + +LegalizeRuleSet &LegalizeRuleSet::legalFor(bool Enabled, + std::initializer_list Types) { + return Enabled ? legalFor(Types) : *this; +} + +LegalizeRuleSet & +LegalizeRuleSet::legalFor(std::initializer_list> Types) { + return actionFor(LegalizationAction::Legal, Types); +} + +LegalizeRuleSet & +LegalizeRuleSet::legalFor(bool Enabled, + std::initializer_list> Types) { + return Enabled ? legalFor(Types) : *this; +} + +LegalizeRuleSet &LegalizeRuleSet::legalFor( + std::initializer_list> Types) { + return actionFor(LegalizationAction::Legal, Types); +} + +LegalizeRuleSet &LegalizeRuleSet::customFor(std::initializer_list Types) { + return actionFor(LegalizationAction::Custom, Types); +} + +LegalizeRuleSet &LegalizeRuleSet::customFor(bool Enabled, + std::initializer_list Types) { + return Enabled ? customFor(Types) : *this; +} + +LegalizeRuleSet & +LegalizeRuleSet::customFor(std::initializer_list> Types) { + return actionFor(LegalizationAction::Custom, Types); +} + +LegalizeRuleSet & +LegalizeRuleSet::customFor(bool Enabled, + std::initializer_list> Types) { + return Enabled ? customFor(Types) : *this; +} + +LegalizeRuleSet &LegalizeRuleSet::lowerFor(std::initializer_list Types) { + return actionFor(LegalizationAction::Lower, Types); +} + +LegalizeRuleSet & +LegalizeRuleSet::lowerFor(std::initializer_list> Types) { + return actionFor(LegalizationAction::Lower, Types); +} + +LegalizeRuleSet &LegalizeRuleSet::libcallFor(std::initializer_list Types) { + return actionFor(LegalizationAction::Libcall, Types); +} + +LegalizeRuleSet &LegalizeRuleSet::libcallFor(bool Enabled, + std::initializer_list Types) { + return Enabled ? libcallFor(Types) : *this; +} + +LegalizeRuleSet & +LegalizeRuleSet::libcallFor(std::initializer_list> Types) { + return actionFor(LegalizationAction::Libcall, Types); +} + +LegalizeRuleSet & +LegalizeRuleSet::libcallFor(bool Enabled, + std::initializer_list> Types) { + return Enabled ? libcallFor(Types) : *this; +} + +LegalizeRuleSet & +LegalizeRuleSet::legalForTypesWithMemDesc(std::initializer_list MemoryRules) { + const std::vector MemoryRuleList(MemoryRules); + return legalIf([MemoryRuleList](const LegalizationQuery &Query) { + return std::ranges::any_of(MemoryRuleList, [&Query](const LegalizeMemoryRule &Rule) { + return memoryRuleMatches(Query, Rule); + }); + }); +} + +LegalizeRuleSet &LegalizeRuleSet::widenScalarToNextPow2(std::size_t TypeIndex, + std::uint32_t MinimumBitWidth) { + return widenScalarIf( + [TypeIndex, MinimumBitWidth](const LegalizationQuery &Query) { + if (TypeIndex >= Query.Types.size() || !Query.Types[TypeIndex].isCategoryNeutralScalar()) + return false; + const std::uint32_t Width = Query.Types[TypeIndex].scalarBitWidth(); + return nextPowerOfTwo(Width, MinimumBitWidth) > Width; + }, + [TypeIndex, MinimumBitWidth](const LegalizationQuery &Query) { + return std::pair{TypeIndex, scalarType(nextPowerOfTwo( + Query.Types[TypeIndex].scalarBitWidth(), MinimumBitWidth))}; + }); +} + +LegalizeRuleSet &LegalizeRuleSet::minScalar(std::size_t TypeIndex, LowLevelType MinimumType) { + return widenScalarIf( + [TypeIndex, MinimumType](const LegalizationQuery &Query) { + return TypeIndex < Query.Types.size() && Query.Types[TypeIndex].isCategoryNeutralScalar() && + Query.Types[TypeIndex].scalarBitWidth() < MinimumType.scalarBitWidth(); + }, + [TypeIndex, MinimumType](const LegalizationQuery &) { + return std::pair{TypeIndex, MinimumType}; + }); +} + +LegalizeRuleSet &LegalizeRuleSet::minScalar(bool Enabled, std::size_t TypeIndex, + LowLevelType MinimumType) { + return Enabled ? minScalar(TypeIndex, MinimumType) : *this; +} + +LegalizeRuleSet &LegalizeRuleSet::maxScalar(std::size_t TypeIndex, LowLevelType MaximumType) { + return narrowScalarIf( + [TypeIndex, MaximumType](const LegalizationQuery &Query) { + return TypeIndex < Query.Types.size() && Query.Types[TypeIndex].isCategoryNeutralScalar() && + Query.Types[TypeIndex].scalarBitWidth() > MaximumType.scalarBitWidth(); + }, + [TypeIndex, MaximumType](const LegalizationQuery &) { + return std::pair{TypeIndex, MaximumType}; + }); +} + +LegalizeRuleSet &LegalizeRuleSet::maxScalar(bool Enabled, std::size_t TypeIndex, + LowLevelType MaximumType) { + return Enabled ? maxScalar(TypeIndex, MaximumType) : *this; +} + +LegalizeRuleSet &LegalizeRuleSet::clampScalar(std::size_t TypeIndex, LowLevelType MinimumType, + LowLevelType MaximumType) { + return minScalar(TypeIndex, MinimumType).maxScalar(TypeIndex, MaximumType); +} + +LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex, + std::size_t ReferenceTypeIndex) { + const auto changeToReference = [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) { + return std::pair{TypeIndex, scalarType(Query.Types[ReferenceTypeIndex].scalarBitWidth())}; + }; + widenScalarIf( + [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) { + return TypeIndex < Query.Types.size() && ReferenceTypeIndex < Query.Types.size() && + Query.Types[TypeIndex].isCategoryNeutralScalar() && + Query.Types[ReferenceTypeIndex].isCategoryNeutralScalar() && + Query.Types[TypeIndex].scalarBitWidth() < + Query.Types[ReferenceTypeIndex].scalarBitWidth(); + }, + changeToReference); + return narrowScalarIf( + [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) { + return TypeIndex < Query.Types.size() && ReferenceTypeIndex < Query.Types.size() && + Query.Types[TypeIndex].isCategoryNeutralScalar() && + Query.Types[ReferenceTypeIndex].isCategoryNeutralScalar() && + Query.Types[TypeIndex].scalarBitWidth() > + Query.Types[ReferenceTypeIndex].scalarBitWidth(); + }, + changeToReference); +} + +LegalizeRuleSet &LegalizeRuleSet::lowerIfMemSizeNotByteSizePow2(std::size_t MemoryIndex) { + return lowerIf([MemoryIndex](const LegalizationQuery &Query) { + if (MemoryIndex >= Query.MemoryOperands.size()) + return false; + const MemorySize Size = Query.MemoryOperands[MemoryIndex].Size; + return !Size.isKnown() || Size.isScalable() || !std::has_single_bit(Size.minimumBytes()); + }); +} + +LegalizeRuleSet &LegalizeRuleSet::alwaysLegal() { + return legalIf([](const LegalizationQuery &) { return true; }); +} + +LegalizeRuleSet &LegalizeRuleSet::lower() { + return lowerIf([](const LegalizationQuery &) { return true; }); +} + +LegalizeRuleSet &LegalizeRuleSet::libcall() { + return libcallIf([](const LegalizationQuery &) { return true; }); +} + +std::optional LegalizeRuleSet::apply(const LegalizationQuery &Query) const { + for (const LegalizeRule &Rule : Rules) { + if (Rule.matches(Query)) + return Rule.apply(Query); + } + return std::nullopt; +} + +LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(Opcode InstructionOpcode) { + return RuleSets[InstructionOpcode]; +} + +LegalizeRuleSet & +LegalizerInfo::getActionDefinitionsBuilder(std::initializer_list InstructionOpcodes) { + const Opcode Representative = *InstructionOpcodes.begin(); + for (const Opcode InstructionOpcode : InstructionOpcodes) { + if (InstructionOpcode != Representative) + RuleAliases.emplace(InstructionOpcode, Representative); + } + return getActionDefinitionsBuilder(Representative); +} + +Expected LegalizerInfo::buildQuery(const MachineInstr &Instruction, + const MachineFunction &Function, + const TargetDescription &Target) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "legalization query requires a registered instruction opcode"); + + std::size_t ExplicitCount = 0; + while (ExplicitCount < Instruction.operandCount() && + !Instruction.operandAt(ExplicitCount)->isImplicit()) { + ++ExplicitCount; + } + auto OperandDescriptors = resolveExplicitOperandDescriptors(*Descriptor, ExplicitCount); + if (!OperandDescriptors) + return std::unexpected(OperandDescriptors.error()); + + std::size_t TypeCount = 0; + for (const OperandDescriptor *Operand : *OperandDescriptors) { + if (Operand->TypeConstraint && Operand->TypeConstraint->EqualityGroup) { + TypeCount = std::max(TypeCount, + static_cast(*Operand->TypeConstraint->EqualityGroup) + 1U); + } + } + + std::vector> OptionalTypes(TypeCount); + std::vector> TypeOperands(TypeCount); + for (std::size_t Index = 0; Index < ExplicitCount; ++Index) { + const OperandDescriptor &OperandDescriptor = *(*OperandDescriptors)[Index]; + if (!OperandDescriptor.TypeConstraint || !OperandDescriptor.TypeConstraint->EqualityGroup) { + continue; + } + const std::size_t TypeIndex = *OperandDescriptor.TypeConstraint->EqualityGroup; + const Register *Reg = Instruction.operandAt(Index)->getIf(); + if (Reg == nullptr || !Reg->isVirtual()) + return makeUnexpected(ErrorCode::VerificationError, + "legalization type operand must name a virtual register"); + auto Info = Function.registerInfo().virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + if (!Info->get().Type) + return makeUnexpected(ErrorCode::VerificationError, + "legalization type operand has no LowLevelType"); + if (OptionalTypes[TypeIndex] && *OptionalTypes[TypeIndex] != *Info->get().Type) + return makeUnexpected(ErrorCode::VerificationError, + "legalization type operands disagree within one type index"); + OptionalTypes[TypeIndex] = *Info->get().Type; + TypeOperands[TypeIndex].push_back(Index); + } + + std::vector Types; + Types.reserve(TypeCount); + for (const std::optional &Type : OptionalTypes) { + if (!Type) + return makeUnexpected(ErrorCode::VerificationError, + "legalization query contains a sparse type index"); + Types.push_back(*Type); + } + + std::vector MemoryOperands; + MemoryOperands.reserve(Instruction.memOperands().size()); + for (const MachineMemOperand *Memory : Instruction.memOperands()) { + const MachineMemOperandDesc &Description = Memory->description(); + MemoryOperands.push_back({Description.MemoryType, Description.Size, + Description.Align.bytes() * 8U, Description.AddressSpace, + Description.AtomicKind, Description.SuccessOrdering, + Description.FailureOrdering, Description.SyncScope}); + } + + LegalizationQuery Query(Instruction.opcode(), std::move(Types), std::move(MemoryOperands)); + Query.TypeOperands = std::move(TypeOperands); + return Query; +} + +Expected LegalizerInfo::getDecision(const MachineInstr &Instruction, + const MachineFunction &Function, + const TargetDescription &Target) const { + auto Query = buildQuery(Instruction, Function, Target); + if (!Query) + return std::unexpected(Query.error()); + return getDecision(*Query); +} + +Expected LegalizerInfo::getDecision(const LegalizationQuery &Query) const { + if (!isGenericOpcode(Query.InstructionOpcode)) + return LegalizationDecision{.Action = LegalizationAction::Legal, .TypeIndex = 0, .NewType = {}}; + + Opcode RuleOpcode = Query.InstructionOpcode; + if (const auto Alias = RuleAliases.find(RuleOpcode); Alias != RuleAliases.end()) + RuleOpcode = Alias->second; + const auto RuleSet = RuleSets.find(RuleOpcode); + if (RuleSet == RuleSets.end()) + return LegalizationDecision{ + .Action = LegalizationAction::Unsupported, .TypeIndex = 0, .NewType = {}}; + const std::optional Decision = RuleSet->second.apply(Query); + return Decision.value_or(LegalizationDecision{ + .Action = LegalizationAction::Unsupported, .TypeIndex = 0, .NewType = {}}); +} + +Expected LegalizerInfo::isLegal(const LegalizationQuery &Query) const { + auto Decision = getDecision(Query); + if (!Decision) + return std::unexpected(Decision.error()); + return Decision->Action == LegalizationAction::Legal; +} + +Expected LegalizerInfo::isUnsupported(const LegalizationQuery &Query) const { + auto Decision = getDecision(Query); + if (!Decision) + return std::unexpected(Decision.error()); + return Decision->Action == LegalizationAction::Unsupported; +} + +} // namespace rcc -- cgit v1.2.3