diff options
Diffstat (limited to 'backend/include/rcc/CodeGen/GlobalISel')
6 files changed, 2264 insertions, 7 deletions
diff --git a/backend/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h b/backend/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h new file mode 100644 index 0000000..9538f20 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h @@ -0,0 +1,66 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_GISELCHANGEOBSERVER_H +#define RCC_CODEGEN_GLOBALISEL_GISELCHANGEOBSERVER_H + +#include "rcc/CodeGen/MachineFunction.h" + +#include <span> +#include <vector> + +namespace rcc { + +class MachineInstr; + +class GISelChangeObserver { +public: + virtual ~GISelChangeObserver() = default; + + virtual void erasingInstr(MachineInstr &Instruction) = 0; + virtual void createdInstr(MachineInstr &Instruction) = 0; + virtual void changingInstr(MachineInstr &Instruction) = 0; + virtual void changedInstr(MachineInstr &Instruction) = 0; +}; + +class GISelObserverWrapper final : public MachineFunction::Delegate, + public GISelChangeObserver { +public: + GISelObserverWrapper() = default; + explicit GISelObserverWrapper(GISelChangeObserver &Observer) { + Observers.push_back(&Observer); + } + explicit GISelObserverWrapper(std::span<GISelChangeObserver *const> InitialObservers) + : Observers(InitialObservers.begin(), InitialObservers.end()) {} + + void addObserver(GISelChangeObserver &Observer); + void removeObserver(GISelChangeObserver &Observer); + void clearObservers() noexcept; + + void erasingInstr(MachineInstr &Instruction) override; + void createdInstr(MachineInstr &Instruction) override; + void changingInstr(MachineInstr &Instruction) override; + void changedInstr(MachineInstr &Instruction) override; + + void handleInsertion(MachineInstr &Instruction) override; + void handleRemoval(MachineInstr &Instruction) override; + +private: + std::vector<GISelChangeObserver *> Observers; +}; + +class MachineFunctionDelegateInstaller final { +public: + MachineFunctionDelegateInstaller(MachineFunction &Function, + MachineFunction::Delegate &Delegate); + MachineFunctionDelegateInstaller(const MachineFunctionDelegateInstaller &) = delete; + MachineFunctionDelegateInstaller &operator=(const MachineFunctionDelegateInstaller &) = delete; + ~MachineFunctionDelegateInstaller(); + +private: + MachineFunction *Function; + MachineFunction::Delegate *Delegate; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_GISELCHANGEOBSERVER_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/GISelWorkList.h b/backend/include/rcc/CodeGen/GlobalISel/GISelWorkList.h new file mode 100644 index 0000000..faeafab --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/GISelWorkList.h @@ -0,0 +1,75 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_GISELWORKLIST_H +#define RCC_CODEGEN_GLOBALISEL_GISELWORKLIST_H + +#include <cstddef> +#include <unordered_map> +#include <vector> + +namespace rcc { + +class MachineInstr; + +template <std::size_t InlineCapacity> class GISelWorkList final { +public: + GISelWorkList() { + Worklist.reserve(InlineCapacity); + WorklistMap.reserve(InlineCapacity); + } + + [[nodiscard]] bool empty() const noexcept { + return WorklistMap.empty(); + } + + [[nodiscard]] std::size_t size() const noexcept { + return WorklistMap.size(); + } + + void deferredInsert(MachineInstr *Instruction) { + Worklist.push_back(Instruction); + } + + void finalize() { + WorklistMap.reserve(Worklist.size()); + for (std::size_t Index = 0; Index < Worklist.size(); ++Index) + WorklistMap.emplace(Worklist[Index], Index); + } + + void insert(MachineInstr *Instruction) { + const auto [Position, Inserted] = WorklistMap.emplace(Instruction, Worklist.size()); + if (Inserted) + Worklist.push_back(Instruction); + } + + void remove(const MachineInstr *Instruction) { + const auto Position = WorklistMap.find(Instruction); + if (Position == WorklistMap.end()) + return; + Worklist[Position->second] = nullptr; + WorklistMap.erase(Position); + } + + void clear() { + Worklist.clear(); + WorklistMap.clear(); + } + + [[nodiscard]] MachineInstr *popBack() { + MachineInstr *Instruction = nullptr; + do { + Instruction = Worklist.back(); + Worklist.pop_back(); + } while (Instruction == nullptr); + WorklistMap.erase(Instruction); + return Instruction; + } + +private: + std::vector<MachineInstr *> Worklist; + std::unordered_map<const MachineInstr *, std::size_t> WorklistMap; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_GISELWORKLIST_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h b/backend/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h new file mode 100644 index 0000000..d0a176d --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h @@ -0,0 +1,110 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_GENERICMACHINEINSTRS_H +#define RCC_CODEGEN_GLOBALISEL_GENERICMACHINEINSTRS_H + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/Register.h" + +#include <cassert> +#include <cstddef> + +namespace rcc { + +class GenericMachineInstr : public MachineInstr { +public: + GenericMachineInstr() = delete; + + [[nodiscard]] Register getReg(std::size_t Index) const { + const MachineOperand *Operand = operandAt(Index); + assert(Operand != nullptr && Operand->isRegister()); + return *Operand->registerValue(); + } + + [[nodiscard]] static bool classof(const MachineInstr *Instruction) noexcept { + return Instruction != nullptr && isGenericOpcode(Instruction->opcode()); + } +}; + +class GUnmerge : public GenericMachineInstr { +public: + [[nodiscard]] std::size_t getNumDefs() const noexcept { + return operandCount() - 1; + } + + [[nodiscard]] Register getSourceReg() const { + return getReg(getNumDefs()); + } + + [[nodiscard]] static bool classof(const MachineInstr *Instruction) noexcept { + return Instruction != nullptr && + Instruction->opcode() == rcc::opcode(GenericOpcode::G_UNMERGE_VALUES); + } +}; + +class GMergeLikeInstr : public GenericMachineInstr { +public: + [[nodiscard]] std::size_t getNumSources() const noexcept { + return operandCount() - 1; + } + + [[nodiscard]] Register getSourceReg(std::size_t Index) const { + return getReg(Index + 1); + } + + [[nodiscard]] static bool classof(const MachineInstr *Instruction) noexcept { + if (Instruction == nullptr) + return false; + switch (static_cast<GenericOpcode>(Instruction->opcode().value())) { + case GenericOpcode::G_MERGE_VALUES: + case GenericOpcode::G_CONCAT_VECTORS: + case GenericOpcode::G_BUILD_VECTOR: + return true; + default: + return false; + } + } +}; + +class GMerge : public GMergeLikeInstr { +public: + [[nodiscard]] static bool classof(const MachineInstr *Instruction) noexcept { + return Instruction != nullptr && + Instruction->opcode() == rcc::opcode(GenericOpcode::G_MERGE_VALUES); + } +}; + +class GConcatVectors : public GMergeLikeInstr { +public: + [[nodiscard]] static bool classof(const MachineInstr *Instruction) noexcept { + return Instruction != nullptr && + Instruction->opcode() == rcc::opcode(GenericOpcode::G_CONCAT_VECTORS); + } +}; + +class GBuildVector : public GMergeLikeInstr { +public: + [[nodiscard]] static bool classof(const MachineInstr *Instruction) noexcept { + return Instruction != nullptr && + Instruction->opcode() == rcc::opcode(GenericOpcode::G_BUILD_VECTOR); + } +}; + +template <typename InstructionT> +[[nodiscard]] InstructionT &castGenericMachineInstr(MachineInstr &Instruction) { + assert(InstructionT::classof(&Instruction)); + return static_cast<InstructionT &>(Instruction); +} + +template <typename InstructionT> +[[nodiscard]] const InstructionT & +castGenericMachineInstr(const MachineInstr &Instruction) { + assert(InstructionT::classof(&Instruction)); + return static_cast<const InstructionT &>(Instruction); +} + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_GENERICMACHINEINSTRS_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h new file mode 100644 index 0000000..c3f8d0b --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h @@ -0,0 +1,1802 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H +#define RCC_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/GenericMachineInstrs.h" +#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/GlobalISel/LegalizerInfo.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/Support/Error.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <optional> +#include <ranges> +#include <span> +#include <unordered_set> +#include <utility> +#include <vector> + +namespace rcc { + +class LegalizationArtifactCombiner final { + MachineIRBuilder &Builder; + MachineRegisterInfo &MRI; + const LegalizerInfo &LI; + + [[nodiscard]] static bool isArtifactCast(Opcode InstructionOpcode) noexcept { + switch (static_cast<GenericOpcode>(InstructionOpcode.value())) { + case GenericOpcode::G_TRUNC: + case GenericOpcode::G_SEXT: + case GenericOpcode::G_ZEXT: + case GenericOpcode::G_ANYEXT: + return true; + default: + return false; + } + } + +public: + LegalizationArtifactCombiner(MachineIRBuilder &Builder, MachineRegisterInfo &MRI, + const LegalizerInfo &Info) + : Builder(Builder), MRI(MRI), LI(Info) {} + + [[nodiscard]] Expected<bool> + tryCombineInstruction(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + GISelObserverWrapper &Observer) { + if (!DeadInstructions.empty()) { + auto Deleted = deleteMarkedDeadInsts(DeadInstructions, Observer); + if (!Deleted) + return std::unexpected(Deleted.error()); + } + + std::vector<Register> UpdatedDefs; + Expected<bool> Changed = false; + switch (static_cast<GenericOpcode>(Instruction.opcode().value())) { + default: + return false; + case GenericOpcode::G_ANYEXT: + Changed = tryCombineAnyExt(Instruction, DeadInstructions, UpdatedDefs, Observer); + break; + case GenericOpcode::G_ZEXT: + Changed = tryCombineZExt(Instruction, DeadInstructions, UpdatedDefs, Observer); + break; + case GenericOpcode::G_SEXT: + Changed = tryCombineSExt(Instruction, DeadInstructions, UpdatedDefs, Observer); + break; + case GenericOpcode::G_UNMERGE_VALUES: + Changed = tryCombineUnmergeValues(Instruction, DeadInstructions, UpdatedDefs, Observer); + break; + case GenericOpcode::G_MERGE_VALUES: + case GenericOpcode::G_BUILD_VECTOR: + case GenericOpcode::G_CONCAT_VECTORS: + Changed = tryCombineMergeLike(Instruction, DeadInstructions, UpdatedDefs, Observer); + break; + case GenericOpcode::G_EXTRACT: + Changed = tryCombineExtract(Instruction, DeadInstructions, UpdatedDefs); + break; + case GenericOpcode::G_TRUNC: + Changed = tryCombineTrunc(Instruction, DeadInstructions, UpdatedDefs, Observer); + if (Changed && !*Changed) + UpdatedDefs.push_back(*Instruction.operandAt(0)->registerValue()); + break; + } + if (!Changed) + return std::unexpected(Changed.error()); + + while (!UpdatedDefs.empty()) { + const Register NewDef = UpdatedDefs.back(); + UpdatedDefs.pop_back(); + std::vector<MachineInstr *> Uses; + for (MachineOperand &Use : MRI.useOperands(NewDef)) { + if (Use.parent() != nullptr) + Uses.push_back(Use.parent()); + } + for (MachineInstr *Use : Uses) { + switch (static_cast<GenericOpcode>(Use->opcode().value())) { + case GenericOpcode::G_ANYEXT: + case GenericOpcode::G_ZEXT: + case GenericOpcode::G_SEXT: + case GenericOpcode::G_UNMERGE_VALUES: + case GenericOpcode::G_EXTRACT: + case GenericOpcode::G_TRUNC: + case GenericOpcode::G_BUILD_VECTOR: + Observer.changedInstr(*Use); + break; + case GenericOpcode::G_ASSERT_SEXT: + case GenericOpcode::G_ASSERT_ZEXT: + case GenericOpcode::G_ASSERT_ALIGN: + if (const auto Copy = Use->operandAt(0)->registerValue(); + Copy && Copy->isVirtual()) + UpdatedDefs.push_back(*Copy); + break; + default: + if (Use->opcode() == opcode(GenericOpcode::COPY)) { + if (const auto Copy = Use->operandAt(0)->registerValue(); + Copy && Copy->isVirtual()) + UpdatedDefs.push_back(*Copy); + } + break; + } + } + } + return *Changed; + } + +private: + class ArtifactValueFinder final { + public: + explicit ArtifactValueFinder(LegalizationArtifactCombiner &Combiner) + : Combiner(Combiner) {} + + [[nodiscard]] Expected<Register> findValueFromDef(Register DefReg, + std::uint64_t StartBit, + std::uint64_t Size, + LowLevelType DestinationType); + [[nodiscard]] Expected<bool> + tryCombineUnmergeDefs(GUnmerge &Instruction, + GISelChangeObserver &Observer, + std::vector<Register> &UpdatedDefs); + [[nodiscard]] Expected<GUnmerge *> + findUnmergeThatDefinesReg(Register Reg, std::uint64_t Size, + std::size_t &DefOperandIndex); + [[nodiscard]] Expected<bool> + isSequenceFromUnmerge(GMergeLikeInstr &Instruction, + std::size_t MergeStartIndex, GUnmerge *Unmerge, + std::size_t UnmergeStartIndex, + std::size_t ElementCount, std::uint64_t ElementSize, + bool AllowUndef); + [[nodiscard]] Expected<bool> + tryCombineMergeLike(GMergeLikeInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelChangeObserver &Observer); + + private: + [[nodiscard]] Expected<Register> + findValueFromDefImpl(Register DefReg, std::uint64_t StartBit, + std::uint64_t Size, LowLevelType DestinationType); + [[nodiscard]] Expected<Register> + findValueFromConcat(GConcatVectors &Instruction, + std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType); + [[nodiscard]] Expected<Register> + findValueFromBuildVector(GBuildVector &Instruction, + std::uint64_t StartBit, std::uint64_t Size); + [[nodiscard]] Expected<Register> + findValueFromInsert(MachineInstr &Instruction, std::uint64_t StartBit, + std::uint64_t Size, LowLevelType DestinationType); + [[nodiscard]] Expected<Register> + findValueFromExtension(MachineInstr &Instruction, + std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType); + [[nodiscard]] Expected<Register> + findValueFromTrunc(MachineInstr &Instruction, std::uint64_t StartBit, + std::uint64_t Size, LowLevelType DestinationType); + + LegalizationArtifactCombiner &Combiner; + Register CurrentBest; + std::unordered_set<Register> Visited; + }; + + [[nodiscard]] Expected<bool> + tryCombineAnyExt(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> + tryCombineZExt(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> + tryCombineSExt(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> + tryCombineTrunc(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> + tryCombineUnmergeValues(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> + tryCombineExtract(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs); + [[nodiscard]] Expected<bool> + tryCombineMergeLike(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> tryFoldImplicitDef( + MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer); + + [[nodiscard]] Expected<MachineInstr *> buildUnary(GenericOpcode InstructionOpcode, + Register Destination, + Register Source); + [[nodiscard]] Expected<MachineInstr *> + buildMergeLike(Register Destination, const std::vector<Register> &Sources); + [[nodiscard]] Expected<void> buildConstant(Register Destination, APInt Value); + [[nodiscard]] Expected<Register> buildConstant(LowLevelType Type, APInt Value); + [[nodiscard]] Expected<bool> isConstantUnsupported(LowLevelType Type) const; + [[nodiscard]] static std::optional<std::int64_t> + immediateOperand(const MachineInstr &Instruction, std::size_t Index); + [[nodiscard]] static std::size_t getDefIndex(const MachineInstr &Instruction, + Register SearchDef); + [[nodiscard]] Expected<std::pair<MachineInstr *, Register>> + definitionIgnoringCopies(Register Reg) const; + [[nodiscard]] Expected<std::vector<Register>> + buildOrFindUnmerge(LowLevelType DestinationType, Register Source); + [[nodiscard]] Expected<LowLevelType> divideType(LowLevelType Type, + std::size_t Parts) const; + [[nodiscard]] Expected<bool> + tryFoldUnmergeCast(MachineInstr &Instruction, MachineInstr &Cast, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs); + [[nodiscard]] static bool canFoldMergeOpcode(Opcode MergeOpcode, + std::optional<Opcode> ConvertOpcode, + LowLevelType OperandType, + LowLevelType DestinationType); + + [[nodiscard]] Expected<void> + replaceRegOrBuildCopy(Register Destination, Register Source, + std::vector<Register> &UpdatedDefs, + GISelChangeObserver &Observer) { + auto DestinationType = MRI.getType(Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto SourceType = MRI.getType(Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + if (*DestinationType != *SourceType) { + auto Copy = Builder.buildCopy(Destination, Source); + if (!Copy) + return std::unexpected(Copy.error()); + UpdatedDefs.push_back(Destination); + return {}; + } + + std::vector<MachineInstr *> Uses; + for (MachineOperand &Use : MRI.useOperands(Destination)) { + if (Use.parent() == nullptr) + continue; + Uses.push_back(Use.parent()); + Observer.changingInstr(*Use.parent()); + } + auto Replaced = MRI.replaceRegWith(Destination, Source); + if (!Replaced) + return std::unexpected(Replaced.error()); + UpdatedDefs.push_back(Source); + for (MachineInstr *Use : Uses) + Observer.changedInstr(*Use); + return {}; + } + + [[nodiscard]] Register lookThroughCopyInstrs(Register Reg) const { + while (MachineInstr *Definition = MRI.getVRegDef(Reg)) { + if (Definition->opcode() != opcode(GenericOpcode::COPY) || + Definition->operandCount() < 2) + break; + const auto Source = Definition->operandAt(1)->registerValue(); + if (!Source || !Source->isVirtual()) + break; + Reg = *Source; + } + return Reg; + } + + [[nodiscard]] static std::optional<Register> + registerOperand(const MachineInstr &Instruction, std::size_t Index) { + const MachineOperand *Operand = Instruction.operandAt(Index); + return Operand == nullptr ? std::nullopt : Operand->registerValue(); + } + + [[nodiscard]] static bool hasOpcode(const MachineInstr *Instruction, + GenericOpcode ExpectedOpcode) noexcept { + return Instruction != nullptr && Instruction->opcode() == opcode(ExpectedOpcode); + } + + void markDefDead(MachineInstr &Instruction, MachineInstr &Definition, + std::vector<MachineInstr *> &DeadInstructions, + std::size_t DefIndex = 0) { + MachineInstr *Previous = &Instruction; + while (Previous != &Definition) { + const auto Source = artifactSourceRegister(*Previous); + if (!Source) + break; + MachineInstr *SourceDefinition = MRI.getVRegDef(*Source); + if (SourceDefinition == nullptr || !MRI.hasOneUse(*Source)) + break; + if (SourceDefinition != &Definition) + DeadInstructions.push_back(SourceDefinition); + Previous = SourceDefinition; + } + if (Previous != &Definition) + return; + + std::size_t CurrentDef = 0; + for (const MachineOperand &Operand : Definition.operands()) { + if (!Operand.isDef()) + continue; + const auto Reg = Operand.registerValue(); + if (!Reg) + return; + if (CurrentDef == DefIndex) { + if (!MRI.hasOneUse(*Reg)) + return; + } else if (!MRI.useEmpty(*Reg)) { + return; + } + ++CurrentDef; + } + DeadInstructions.push_back(&Definition); + } + + void markInstAndDefDead(MachineInstr &Instruction, MachineInstr &Definition, + std::vector<MachineInstr *> &DeadInstructions, + std::size_t DefIndex = 0) { + DeadInstructions.push_back(&Instruction); + markDefDead(Instruction, Definition, DeadInstructions, DefIndex); + } + + [[nodiscard]] Expected<void> + deleteMarkedDeadInsts(std::vector<MachineInstr *> &DeadInstructions, + GISelObserverWrapper &) { + for (MachineInstr *Dead : DeadInstructions) { + if (Dead == nullptr || Dead->parent() == nullptr) + continue; + auto Removed = Dead->parent()->removeInstruction(*Dead); + if (!Removed) + return std::unexpected(Removed.error()); + } + DeadInstructions.clear(); + return {}; + } + + [[nodiscard]] static std::optional<Register> + artifactSourceRegister(const MachineInstr &Instruction) { + switch (static_cast<GenericOpcode>(Instruction.opcode().value())) { + case GenericOpcode::G_TRUNC: + case GenericOpcode::G_ZEXT: + case GenericOpcode::G_ANYEXT: + case GenericOpcode::G_SEXT: + case GenericOpcode::G_EXTRACT: + case GenericOpcode::G_ASSERT_SEXT: + case GenericOpcode::G_ASSERT_ZEXT: + case GenericOpcode::G_ASSERT_ALIGN: + return registerOperand(Instruction, 1); + case GenericOpcode::G_UNMERGE_VALUES: + return registerOperand(Instruction, Instruction.operandCount() - 1); + default: + if (Instruction.opcode() == opcode(GenericOpcode::COPY)) + return registerOperand(Instruction, 1); + return std::nullopt; + } + } + + [[nodiscard]] Expected<bool> isInstUnsupported(LegalizationQuery Query) const { + return LI.isUnsupported(Query); + } + + [[nodiscard]] Expected<bool> isInstLegal(LegalizationQuery Query) const { + return LI.isLegal(Query); + } + +}; + +inline Expected<MachineInstr *> +LegalizationArtifactCombiner::buildUnary(GenericOpcode InstructionOpcode, + Register Destination, + Register Source) { + auto Pending = Builder.buildInstr(opcode(InstructionOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Added = Pending->addDef(Destination); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(Source); !Added) + return std::unexpected(Added.error()); + return Pending->build(); +} + +inline Expected<MachineInstr *> LegalizationArtifactCombiner::buildMergeLike( + Register Destination, const std::vector<Register> &Sources) { + if (Sources.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, + "merge-like instruction requires source registers"); + auto DestinationType = MRI.getType(Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto SourceType = MRI.getType(Sources.front()); + if (!SourceType) + return std::unexpected(SourceType.error()); + + GenericOpcode InstructionOpcode = GenericOpcode::G_MERGE_VALUES; + if (DestinationType->isVector()) + InstructionOpcode = SourceType->isVector() ? GenericOpcode::G_CONCAT_VECTORS + : GenericOpcode::G_BUILD_VECTOR; + auto Pending = Builder.buildInstr(opcode(InstructionOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Added = Pending->addDef(Destination); !Added) + return std::unexpected(Added.error()); + for (Register Source : Sources) { + if (auto Added = Pending->addUse(Source); !Added) + return std::unexpected(Added.error()); + } + return Pending->build(); +} + +inline Expected<void> +LegalizationArtifactCombiner::buildConstant(Register Destination, APInt Value) { + auto Built = Builder.buildConstant(Destination, std::move(Value)); + if (!Built) + return std::unexpected(Built.error()); + return {}; +} + +inline Expected<Register> +LegalizationArtifactCombiner::buildConstant(LowLevelType Type, APInt Value) { + auto Destination = MRI.createVirtualRegister(Type); + if (!Destination) + return std::unexpected(Destination.error()); + auto Built = buildConstant(*Destination, std::move(Value)); + if (!Built) + return std::unexpected(Built.error()); + return *Destination; +} + +inline Expected<bool> +LegalizationArtifactCombiner::isConstantUnsupported(LowLevelType Type) const { + if (!Type.isVector()) + return isInstUnsupported( + LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {Type})); + const auto ElementType = Type.scalarElementType(); + if (!ElementType) + return true; + auto ConstantUnsupported = isInstUnsupported( + LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*ElementType})); + if (!ConstantUnsupported || *ConstantUnsupported) + return ConstantUnsupported; + return isInstUnsupported(LegalizationQuery( + opcode(GenericOpcode::G_BUILD_VECTOR), {Type, *ElementType})); +} + +inline std::optional<std::int64_t> +LegalizationArtifactCombiner::immediateOperand(const MachineInstr &Instruction, + std::size_t Index) { + const MachineOperand *Operand = Instruction.operandAt(Index); + if (Operand == nullptr) + return std::nullopt; + if (const auto *Value = Operand->getIf<std::int64_t>()) + return *Value; + return std::nullopt; +} + +inline std::size_t +LegalizationArtifactCombiner::getDefIndex(const MachineInstr &Instruction, + Register SearchDef) { + std::size_t Index = 0; + for (const MachineOperand &Operand : Instruction.operands()) { + if (!Operand.isDef()) + continue; + if (Operand.registerValue() == SearchDef) + return Index; + ++Index; + } + return Index; +} + +inline Expected<std::pair<MachineInstr *, Register>> +LegalizationArtifactCombiner::definitionIgnoringCopies(Register Reg) const { + std::unordered_set<Register> Visited; + while (Reg.isVirtual() && Visited.insert(Reg).second) { + MachineInstr *Definition = MRI.getVRegDef(Reg); + if (Definition == nullptr) + return std::pair<MachineInstr *, Register>{nullptr, Reg}; + if (Definition->opcode() != opcode(GenericOpcode::COPY)) + return std::pair{Definition, Reg}; + const auto Source = registerOperand(*Definition, 1); + if (!Source) + return std::pair{Definition, Reg}; + Reg = *Source; + } + return std::pair<MachineInstr *, Register>{nullptr, Reg}; +} + +inline Expected<LowLevelType> +LegalizationArtifactCombiner::divideType(LowLevelType Type, + std::size_t Parts) const { + if (Parts == 0 || Type.minimumBitWidth() % Parts != 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "LowLevelType cannot be divided into equal parts"); + if (!Type.isVector()) + return LowLevelType::makeCategoryNeutralScalar(Type.scalarBitWidth() / Parts); + if (Type.minimumElementCount() % Parts != 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "vector element count cannot be divided into equal parts"); + const auto ElementType = Type.scalarElementType(); + if (!ElementType) + return makeUnexpected(ErrorCode::InvalidArgument, + "vector has no scalar element type"); + const std::uint32_t Elements = + Type.minimumElementCount() / static_cast<std::uint32_t>(Parts); + if (Elements == 1) + return *ElementType; + return Type.isScalableVector() + ? LowLevelType::makeScalableVector(Elements, *ElementType) + : LowLevelType::makeFixedVector(Elements, *ElementType); +} + +inline Expected<std::vector<Register>> +LegalizationArtifactCombiner::buildOrFindUnmerge(LowLevelType DestinationType, + Register Source) { + auto SourceType = MRI.getType(Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + if (DestinationType.minimumBitWidth() == 0 || + SourceType->minimumBitWidth() % DestinationType.minimumBitWidth() != 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "unmerge destination does not tile the source type"); + const std::size_t Count = static_cast<std::size_t>( + SourceType->minimumBitWidth() / DestinationType.minimumBitWidth()); + + for (MachineOperand &Use : MRI.useOperands(Source)) { + MachineInstr *Candidate = Use.parent(); + if (!GUnmerge::classof(Candidate) || Candidate->operandCount() != Count + 1) + continue; + std::vector<Register> Existing; + Existing.reserve(Count); + bool Matches = true; + for (std::size_t Index = 0; Index < Count; ++Index) { + const auto Reg = registerOperand(*Candidate, Index); + if (!Reg) { + Matches = false; + break; + } + auto Type = MRI.getType(*Reg); + if (!Type || *Type != DestinationType) { + Matches = false; + break; + } + Existing.push_back(*Reg); + } + if (Matches) + return Existing; + } + + std::vector<Register> Destinations; + Destinations.reserve(Count); + for (std::size_t Index = 0; Index < Count; ++Index) { + auto Destination = MRI.createVirtualRegister(DestinationType); + if (!Destination) + return std::unexpected(Destination.error()); + Destinations.push_back(*Destination); + } + auto Built = Builder.buildUnmergeValues(Destinations, Source); + if (!Built) + return std::unexpected(Built.error()); + return Destinations; +} + +inline bool LegalizationArtifactCombiner::canFoldMergeOpcode( + Opcode MergeOpcode, std::optional<Opcode> ConvertOpcode, + LowLevelType OperandType, LowLevelType DestinationType) { + const auto Generic = static_cast<GenericOpcode>(MergeOpcode.value()); + if (Generic == GenericOpcode::G_BUILD_VECTOR || + Generic == GenericOpcode::G_MERGE_VALUES) { + if (!ConvertOpcode) + return true; + const auto ElementType = OperandType.scalarElementType(); + return !DestinationType.isVector() && OperandType.isVector() && + ElementType && DestinationType == *ElementType; + } + if (Generic != GenericOpcode::G_CONCAT_VECTORS) + return false; + if (!ConvertOpcode) + return true; + if (!DestinationType.isVector()) + return false; + const auto ElementType = OperandType.scalarElementType(); + if (!ElementType) + return false; + if (*ConvertOpcode == opcode(GenericOpcode::G_TRUNC)) + return DestinationType.minimumBitWidth() <= ElementType->minimumBitWidth(); + return DestinationType.minimumBitWidth() >= ElementType->minimumBitWidth(); +} + +inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt( + MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { + const auto Destination = registerOperand(Instruction, 0); + const auto OriginalSource = registerOperand(Instruction, 1); + if (!Destination || !OriginalSource) + return makeUnexpected(ErrorCode::VerificationError, + "G_ANYEXT has invalid register operands"); + const Register Source = lookThroughCopyInstrs(*OriginalSource); + MachineInstr *SourceDefinition = MRI.getVRegDef(Source); + if (SourceDefinition == nullptr) + return false; + if (auto Point = Builder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + + if (hasOpcode(SourceDefinition, GenericOpcode::G_TRUNC)) { + const auto TruncSource = registerOperand(*SourceDefinition, 1); + if (!TruncSource) + return false; + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto TruncSourceType = MRI.getType(*TruncSource); + if (!TruncSourceType) + return std::unexpected(TruncSourceType.error()); + if (*DestinationType == *TruncSourceType) { + auto Replaced = replaceRegOrBuildCopy(*Destination, *TruncSource, + UpdatedDefs, Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + } else { + auto Built = Builder.buildAnyExtOrTrunc(*Destination, *TruncSource); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + } + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + + if (hasOpcode(SourceDefinition, GenericOpcode::G_ANYEXT) || + hasOpcode(SourceDefinition, GenericOpcode::G_SEXT) || + hasOpcode(SourceDefinition, GenericOpcode::G_ZEXT)) { + const auto ExtensionSource = registerOperand(*SourceDefinition, 1); + if (!ExtensionSource) + return false; + auto Built = buildUnary( + static_cast<GenericOpcode>(SourceDefinition->opcode().value()), + *Destination, *ExtensionSource); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + + if (hasOpcode(SourceDefinition, GenericOpcode::G_CONSTANT)) { + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto Legal = isInstLegal(LegalizationQuery( + opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); + if (!Legal) + return std::unexpected(Legal.error()); + const auto *Immediate = + SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); + if (*Legal && Immediate != nullptr) { + auto Extended = Immediate->Value.sext(DestinationType->scalarBitWidth()); + if (!Extended) + return std::unexpected(Extended.error()); + auto Built = buildConstant(*Destination, std::move(*Extended)); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + } + return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, + Observer); +} + +inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt( + MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { + const auto Destination = registerOperand(Instruction, 0); + const auto OriginalSource = registerOperand(Instruction, 1); + if (!Destination || !OriginalSource) + return makeUnexpected(ErrorCode::VerificationError, + "G_ZEXT has invalid register operands"); + const Register Source = lookThroughCopyInstrs(*OriginalSource); + MachineInstr *SourceDefinition = MRI.getVRegDef(Source); + if (SourceDefinition == nullptr) + return false; + if (auto Point = Builder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + + if (hasOpcode(SourceDefinition, GenericOpcode::G_TRUNC) || + hasOpcode(SourceDefinition, GenericOpcode::G_SEXT)) { + const auto NarrowSource = registerOperand(*SourceDefinition, 1); + if (!NarrowSource) + return false; + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto SourceType = MRI.getType(Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + auto AndUnsupported = isInstUnsupported( + LegalizationQuery(opcode(GenericOpcode::G_AND), {*DestinationType})); + if (!AndUnsupported) + return std::unexpected(AndUnsupported.error()); + auto ConstantUnsupported = isConstantUnsupported(*DestinationType); + if (!ConstantUnsupported) + return std::unexpected(ConstantUnsupported.error()); + if (*AndUnsupported || *ConstantUnsupported) + return false; + + Register WideSource = *NarrowSource; + auto WideSourceType = MRI.getType(WideSource); + if (!WideSourceType) + return std::unexpected(WideSourceType.error()); + if (*WideSourceType != *DestinationType) { + auto Wide = MRI.createVirtualRegister(*DestinationType); + if (!Wide) + return std::unexpected(Wide.error()); + auto Built = hasOpcode(SourceDefinition, GenericOpcode::G_SEXT) + ? Builder.buildSExtOrTrunc(*Wide, WideSource) + : Builder.buildAnyExtOrTrunc(*Wide, WideSource); + if (!Built) + return std::unexpected(Built.error()); + WideSource = *Wide; + } + auto Mask = APInt::getLowBitsSet(DestinationType->scalarBitWidth(), + SourceType->scalarBitWidth()); + if (!Mask) + return std::unexpected(Mask.error()); + auto MaskRegister = buildConstant(*DestinationType, std::move(*Mask)); + if (!MaskRegister) + return std::unexpected(MaskRegister.error()); + auto Built = Builder.buildAnd(*Destination, WideSource, *MaskRegister); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + + if (hasOpcode(SourceDefinition, GenericOpcode::G_ZEXT)) { + const auto ExtensionSource = registerOperand(*SourceDefinition, 1); + if (!ExtensionSource) + return false; + Observer.changingInstr(Instruction); + auto Updated = Instruction.operandAt(1)->setRegister(*ExtensionSource); + if (!Updated) + return std::unexpected(Updated.error()); + Observer.changedInstr(Instruction); + UpdatedDefs.push_back(*Destination); + markDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + + if (hasOpcode(SourceDefinition, GenericOpcode::G_CONSTANT)) { + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto Legal = isInstLegal(LegalizationQuery( + opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); + if (!Legal) + return std::unexpected(Legal.error()); + const auto *Immediate = + SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); + if (*Legal && Immediate != nullptr) { + auto Extended = Immediate->Value.zext(DestinationType->scalarBitWidth()); + if (!Extended) + return std::unexpected(Extended.error()); + auto Built = buildConstant(*Destination, std::move(*Extended)); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + } + return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, + Observer); +} + +inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt( + MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { + const auto Destination = registerOperand(Instruction, 0); + const auto OriginalSource = registerOperand(Instruction, 1); + if (!Destination || !OriginalSource) + return makeUnexpected(ErrorCode::VerificationError, + "G_SEXT has invalid register operands"); + const Register Source = lookThroughCopyInstrs(*OriginalSource); + MachineInstr *SourceDefinition = MRI.getVRegDef(Source); + if (SourceDefinition == nullptr) + return false; + if (auto Point = Builder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + + if (hasOpcode(SourceDefinition, GenericOpcode::G_TRUNC)) { + const auto TruncSource = registerOperand(*SourceDefinition, 1); + if (!TruncSource) + return false; + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto SourceType = MRI.getType(Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + auto Unsupported = isInstUnsupported(LegalizationQuery( + opcode(GenericOpcode::G_SEXT_INREG), {*DestinationType})); + if (!Unsupported) + return std::unexpected(Unsupported.error()); + if (*Unsupported) + return false; + Register WideSource = *TruncSource; + auto WideSourceType = MRI.getType(WideSource); + if (!WideSourceType) + return std::unexpected(WideSourceType.error()); + if (*WideSourceType != *DestinationType) { + auto Wide = MRI.createVirtualRegister(*DestinationType); + if (!Wide) + return std::unexpected(Wide.error()); + auto Built = Builder.buildAnyExtOrTrunc(*Wide, WideSource); + if (!Built) + return std::unexpected(Built.error()); + WideSource = *Wide; + } + auto Built = Builder.buildSExtInReg(*Destination, WideSource, + SourceType->scalarBitWidth()); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + + if (hasOpcode(SourceDefinition, GenericOpcode::G_ZEXT) || + hasOpcode(SourceDefinition, GenericOpcode::G_SEXT)) { + const auto ExtensionSource = registerOperand(*SourceDefinition, 1); + if (!ExtensionSource) + return false; + auto Built = buildUnary( + static_cast<GenericOpcode>(SourceDefinition->opcode().value()), + *Destination, *ExtensionSource); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + + if (hasOpcode(SourceDefinition, GenericOpcode::G_CONSTANT)) { + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto Legal = isInstLegal(LegalizationQuery( + opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); + if (!Legal) + return std::unexpected(Legal.error()); + const auto *Immediate = + SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); + if (*Legal && Immediate != nullptr) { + auto Extended = Immediate->Value.sext(DestinationType->scalarBitWidth()); + if (!Extended) + return std::unexpected(Extended.error()); + auto Built = buildConstant(*Destination, std::move(*Extended)); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + } + return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, + Observer); +} + +inline Expected<bool> LegalizationArtifactCombiner::tryFoldImplicitDef( + MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelObserverWrapper &) { + const auto Destination = registerOperand(Instruction, 0); + const auto Source = registerOperand(Instruction, 1); + if (!Destination || !Source) + return false; + MachineInstr *Definition = MRI.getVRegDef(lookThroughCopyInstrs(*Source)); + if (!hasOpcode(Definition, GenericOpcode::G_IMPLICIT_DEF)) + return false; + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (auto Point = Builder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (Instruction.opcode() == opcode(GenericOpcode::G_ANYEXT)) { + auto Legal = isInstLegal(LegalizationQuery( + opcode(GenericOpcode::G_IMPLICIT_DEF), {*DestinationType})); + if (!Legal) + return std::unexpected(Legal.error()); + if (!*Legal) + return false; + auto Built = Builder.buildImplicitDef(*Destination); + if (!Built) + return std::unexpected(Built.error()); + } else { + auto Unsupported = isConstantUnsupported(*DestinationType); + if (!Unsupported) + return std::unexpected(Unsupported.error()); + if (*Unsupported) + return false; + auto Built = Builder.buildConstant(*Destination, 0); + if (!Built) + return std::unexpected(Built.error()); + } + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *Definition, DeadInstructions); + return true; +} + +inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc( + MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { + const auto Destination = registerOperand(Instruction, 0); + const auto OriginalSource = registerOperand(Instruction, 1); + if (!Destination || !OriginalSource) + return makeUnexpected(ErrorCode::VerificationError, + "G_TRUNC has invalid register operands"); + const Register Source = lookThroughCopyInstrs(*OriginalSource); + MachineInstr *SourceDefinition = MRI.getVRegDef(Source); + if (SourceDefinition == nullptr) + return false; + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (auto Point = Builder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + + if (hasOpcode(SourceDefinition, GenericOpcode::G_CONSTANT)) { + auto Legal = isInstLegal(LegalizationQuery( + opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); + if (!Legal) + return std::unexpected(Legal.error()); + const auto *Immediate = + SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); + if (*Legal && Immediate != nullptr) { + auto Truncated = Immediate->Value.trunc(DestinationType->scalarBitWidth()); + if (!Truncated) + return std::unexpected(Truncated.error()); + auto Built = buildConstant(*Destination, std::move(*Truncated)); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + } + + if (GMerge::classof(SourceDefinition)) { + auto &Merge = castGenericMachineInstr<GMerge>(*SourceDefinition); + if (Merge.getNumSources() == 0) + return false; + const Register FirstSource = Merge.getSourceReg(0); + auto FirstSourceType = MRI.getType(FirstSource); + if (!FirstSourceType) + return std::unexpected(FirstSourceType.error()); + if (!DestinationType->isCategoryNeutralScalar() || + !FirstSourceType->isCategoryNeutralScalar()) + return false; + const std::uint64_t DestinationSize = DestinationType->minimumBitWidth(); + const std::uint64_t SourceSize = FirstSourceType->minimumBitWidth(); + if (DestinationSize < SourceSize) { + auto Unsupported = isInstUnsupported(LegalizationQuery( + opcode(GenericOpcode::G_TRUNC), + {*DestinationType, *FirstSourceType})); + if (!Unsupported) + return std::unexpected(Unsupported.error()); + if (*Unsupported) + return false; + auto Built = Builder.buildTrunc(*Destination, FirstSource); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + } else if (DestinationSize == SourceSize) { + auto Replaced = replaceRegOrBuildCopy(*Destination, FirstSource, + UpdatedDefs, Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + } else if (DestinationSize % SourceSize == 0) { + const std::size_t SourceCount = + static_cast<std::size_t>(DestinationSize / SourceSize); + if (SourceCount >= Merge.getNumSources()) + return false; + auto Unsupported = isInstUnsupported(LegalizationQuery( + opcode(GenericOpcode::G_MERGE_VALUES), + {*DestinationType, *FirstSourceType})); + if (!Unsupported) + return std::unexpected(Unsupported.error()); + if (*Unsupported) + return false; + std::vector<Register> Sources; + Sources.reserve(SourceCount); + for (std::size_t Index = 0; Index < SourceCount; ++Index) + Sources.push_back(Merge.getSourceReg(Index)); + auto Built = Builder.buildMergeValues(*Destination, Sources); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + } else { + return false; + } + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + + if (hasOpcode(SourceDefinition, GenericOpcode::G_TRUNC)) { + const auto TruncSource = registerOperand(*SourceDefinition, 1); + if (!TruncSource) + return false; + auto Built = Builder.buildTrunc(*Destination, *TruncSource); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + + ArtifactValueFinder Finder(*this); + auto Found = Finder.findValueFromDef(*Destination, 0, + DestinationType->minimumBitWidth(), + *DestinationType); + if (!Found) + return std::unexpected(Found.error()); + if (!Found->isNoRegister()) { + auto FoundType = MRI.getType(*Found); + if (!FoundType) + return std::unexpected(FoundType.error()); + if (*FoundType == *DestinationType) { + auto Replaced = replaceRegOrBuildCopy(*Destination, *Found, UpdatedDefs, + Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); + return true; + } + } + return false; +} + +inline Expected<bool> +LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike( + GMergeLikeInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelChangeObserver &Observer) { + if (Instruction.getNumSources() == 0) + return false; + const Register FirstElement = Instruction.getSourceReg(0); + auto ElementType = Combiner.MRI.getType(FirstElement); + if (!ElementType) + return std::unexpected(ElementType.error()); + const std::uint64_t ElementSize = ElementType->minimumBitWidth(); + std::size_t FirstUnmergeIndex = 0; + auto UnmergeResult = + findUnmergeThatDefinesReg(FirstElement, ElementSize, FirstUnmergeIndex); + if (!UnmergeResult) + return std::unexpected(UnmergeResult.error()); + GUnmerge *Unmerge = *UnmergeResult; + if (Unmerge == nullptr) + return false; + + const Register Destination = Instruction.getReg(0); + const Register UnmergeSource = Unmerge->getSourceReg(); + auto DestinationType = Combiner.MRI.getType(Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto UnmergeSourceType = Combiner.MRI.getType(UnmergeSource); + if (!UnmergeSourceType) + return std::unexpected(UnmergeSourceType.error()); + const std::size_t SourceCount = Instruction.getNumSources(); + + if (*DestinationType == *UnmergeSourceType && FirstUnmergeIndex == 0) { + auto Sequence = isSequenceFromUnmerge( + Instruction, 0, Unmerge, 0, SourceCount, ElementSize, + DestinationType->isVector()); + if (!Sequence) + return std::unexpected(Sequence.error()); + if (!*Sequence) + return false; + auto Replaced = Combiner.replaceRegOrBuildCopy( + Destination, UnmergeSource, UpdatedDefs, Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + DeadInstructions.push_back(&Instruction); + return true; + } + + const bool MatchingDomains = + (!DestinationType->isVector() && !UnmergeSourceType->isVector()) || + (DestinationType->isVector() && UnmergeSourceType->isVector() && + DestinationType->scalarElementType() == + UnmergeSourceType->scalarElementType()); + if (MatchingDomains && FirstUnmergeIndex % SourceCount == 0 && + UnmergeSourceType->minimumBitWidth() % + DestinationType->minimumBitWidth() == + 0) { + auto Sequence = isSequenceFromUnmerge( + Instruction, 0, Unmerge, FirstUnmergeIndex, SourceCount, ElementSize, + false); + if (!Sequence) + return std::unexpected(Sequence.error()); + if (*Sequence) { + auto NewUnmerge = Combiner.buildOrFindUnmerge(*DestinationType, + UnmergeSource); + if (!NewUnmerge) + return std::unexpected(NewUnmerge.error()); + const std::size_t DestinationIndex = static_cast<std::size_t>( + (FirstUnmergeIndex * ElementSize) / + DestinationType->minimumBitWidth()); + if (DestinationIndex >= NewUnmerge->size()) + return false; + auto Replaced = Combiner.replaceRegOrBuildCopy( + Destination, (*NewUnmerge)[DestinationIndex], UpdatedDefs, Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + DeadInstructions.push_back(&Instruction); + return true; + } + } + + if (DestinationType->isVector() == UnmergeSourceType->isVector() && + DestinationType->minimumBitWidth() % + UnmergeSourceType->minimumBitWidth() == + 0) { + const std::size_t UnmergeElementCount = Unmerge->getNumDefs(); + if (UnmergeElementCount == 0 || SourceCount % UnmergeElementCount != 0) + return false; + std::vector<Register> MergeSources; + for (std::size_t Start = 0; Start < SourceCount; + Start += UnmergeElementCount) { + std::size_t SourceDefIndex = 0; + auto SourceUnmerge = findUnmergeThatDefinesReg( + Instruction.getSourceReg(Start), ElementSize, SourceDefIndex); + if (!SourceUnmerge) + return std::unexpected(SourceUnmerge.error()); + if (*SourceUnmerge == nullptr || + (*SourceUnmerge)->getNumDefs() != UnmergeElementCount || + SourceDefIndex != 0) + return false; + auto Sequence = isSequenceFromUnmerge( + Instruction, Start, *SourceUnmerge, 0, UnmergeElementCount, + ElementSize, false); + if (!Sequence) + return std::unexpected(Sequence.error()); + if (!*Sequence) + return false; + MergeSources.push_back((*SourceUnmerge)->getSourceReg()); + } + auto Built = Combiner.buildMergeLike(Destination, MergeSources); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(Destination); + DeadInstructions.push_back(&Instruction); + return true; + } + return false; +} + +inline Expected<bool> LegalizationArtifactCombiner::tryCombineMergeLike( + MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { + if (!GMergeLikeInstr::classof(&Instruction)) + return false; + ArtifactValueFinder Finder(*this); + return Finder.tryCombineMergeLike( + castGenericMachineInstr<GMergeLikeInstr>(Instruction), DeadInstructions, + UpdatedDefs, Observer); +} + +inline Expected<bool> LegalizationArtifactCombiner::tryFoldUnmergeCast( + MachineInstr &Instruction, MachineInstr &Cast, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs) { + if (!isArtifactCast(Cast.opcode()) || + Cast.opcode() != opcode(GenericOpcode::G_TRUNC)) + return false; + const auto CastSource = registerOperand(Cast, 1); + if (!CastSource) + return false; + auto CastSourceType = MRI.getType(*CastSource); + if (!CastSourceType) + return std::unexpected(CastSourceType.error()); + const std::size_t OriginalDefCount = Instruction.operandCount() - 1; + if (OriginalDefCount == 0) + return false; + const auto FirstDestination = registerOperand(Instruction, 0); + if (!FirstDestination) + return false; + auto DestinationType = MRI.getType(*FirstDestination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (DestinationType->isVector() || !CastSourceType->isCategoryNeutralScalar() || + CastSourceType->minimumBitWidth() % + DestinationType->minimumBitWidth() != + 0) + return false; + auto Unsupported = isInstUnsupported(LegalizationQuery( + opcode(GenericOpcode::G_UNMERGE_VALUES), + {*DestinationType, *CastSourceType})); + if (!Unsupported) + return std::unexpected(Unsupported.error()); + if (*Unsupported) + return false; + const std::size_t NewDefCount = static_cast<std::size_t>( + CastSourceType->minimumBitWidth() / + DestinationType->minimumBitWidth()); + std::vector<Register> Destinations; + Destinations.reserve(NewDefCount); + for (std::size_t Index = 0; Index < NewDefCount; ++Index) { + if (Index < OriginalDefCount) { + const auto Destination = registerOperand(Instruction, Index); + if (!Destination) + return false; + Destinations.push_back(*Destination); + } else { + auto Destination = MRI.createVirtualRegister(*DestinationType); + if (!Destination) + return std::unexpected(Destination.error()); + Destinations.push_back(*Destination); + } + } + if (auto Point = Builder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + auto Built = Builder.buildUnmergeValues(Destinations, *CastSource); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.insert(UpdatedDefs.end(), Destinations.begin(), + Destinations.begin() + + static_cast<std::ptrdiff_t>(OriginalDefCount)); + markInstAndDefDead(Instruction, Cast, DeadInstructions); + return true; +} + +inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( + MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { + if (!GUnmerge::classof(&Instruction)) + return false; + auto &Unmerge = castGenericMachineInstr<GUnmerge>(Instruction); + if (Unmerge.getNumDefs() == 0) + return false; + const Register Source = Unmerge.getSourceReg(); + auto Definition = definitionIgnoringCopies(Source); + if (!Definition) + return std::unexpected(Definition.error()); + MachineInstr *SourceDefinition = Definition->first; + if (SourceDefinition == nullptr) + return false; + const std::size_t SourceDefIndex = getDefIndex(*SourceDefinition, + Definition->second); + auto OperandType = MRI.getType(Source); + if (!OperandType) + return std::unexpected(OperandType.error()); + auto DestinationType = MRI.getType(Unmerge.getReg(0)); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (auto Point = Builder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + + ArtifactValueFinder Finder(*this); + auto AllCombined = Finder.tryCombineUnmergeDefs(Unmerge, Observer, + UpdatedDefs); + if (!AllCombined) + return std::unexpected(AllCombined.error()); + if (*AllCombined) { + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions, + SourceDefIndex); + return true; + } + + if (GUnmerge::classof(SourceDefinition)) { + auto &SourceUnmerge = castGenericMachineInstr<GUnmerge>(*SourceDefinition); + const Register OriginalSource = SourceUnmerge.getSourceReg(); + auto OriginalSourceType = MRI.getType(OriginalSource); + if (!OriginalSourceType) + return std::unexpected(OriginalSourceType.error()); + auto NewUnmerge = buildOrFindUnmerge(*DestinationType, OriginalSource); + if (!NewUnmerge) + return std::unexpected(NewUnmerge.error()); + const std::size_t BaseIndex = SourceDefIndex * Unmerge.getNumDefs(); + if (BaseIndex + Unmerge.getNumDefs() > NewUnmerge->size()) + return false; + for (std::size_t Index = 0; Index < Unmerge.getNumDefs(); ++Index) { + auto Replaced = replaceRegOrBuildCopy( + Unmerge.getReg(Index), (*NewUnmerge)[BaseIndex + Index], UpdatedDefs, + Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + } + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions, + SourceDefIndex); + return true; + } + + MachineInstr *Merge = SourceDefinition; + std::optional<Opcode> ConvertOpcode; + if (isArtifactCast(SourceDefinition->opcode())) { + ConvertOpcode = SourceDefinition->opcode(); + const auto CastSource = registerOperand(*SourceDefinition, 1); + if (!CastSource) + return false; + auto CastDefinition = definitionIgnoringCopies(*CastSource); + if (!CastDefinition) + return std::unexpected(CastDefinition.error()); + Merge = CastDefinition->first; + } + if (Merge == nullptr || + !canFoldMergeOpcode(Merge->opcode(), ConvertOpcode, *OperandType, + *DestinationType)) + return tryFoldUnmergeCast(Instruction, *SourceDefinition, + DeadInstructions, UpdatedDefs); + + const std::size_t MergeSourceCount = Merge->operandCount() - 1; + const std::size_t DefCount = Unmerge.getNumDefs(); + if (MergeSourceCount < DefCount) { + if (DefCount % MergeSourceCount != 0) + return false; + const std::size_t NewDefCount = DefCount / MergeSourceCount; + for (std::size_t SourceIndex = 0; SourceIndex < MergeSourceCount; + ++SourceIndex) { + std::vector<Register> Destinations; + Destinations.reserve(NewDefCount); + for (std::size_t Index = 0; Index < NewDefCount; ++Index) + Destinations.push_back( + Unmerge.getReg(SourceIndex * NewDefCount + Index)); + Register SplitSource = *registerOperand(*Merge, SourceIndex + 1); + if (ConvertOpcode) { + auto ConvertedType = divideType(*OperandType, MergeSourceCount); + if (!ConvertedType) + return std::unexpected(ConvertedType.error()); + auto Converted = MRI.createVirtualRegister(*ConvertedType); + if (!Converted) + return std::unexpected(Converted.error()); + auto Built = buildUnary( + static_cast<GenericOpcode>(ConvertOpcode->value()), *Converted, + SplitSource); + if (!Built) + return std::unexpected(Built.error()); + SplitSource = *Converted; + } + auto Built = Builder.buildUnmergeValues(Destinations, SplitSource); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.insert(UpdatedDefs.end(), Destinations.begin(), + Destinations.end()); + } + } else if (MergeSourceCount > DefCount) { + if (ConvertOpcode || MergeSourceCount % DefCount != 0) + return false; + const std::size_t SourcesPerDef = MergeSourceCount / DefCount; + for (std::size_t DefIndex = 0; DefIndex < DefCount; ++DefIndex) { + std::vector<Register> Sources; + Sources.reserve(SourcesPerDef); + for (std::size_t Index = 0; Index < SourcesPerDef; ++Index) { + const auto SourceReg = registerOperand( + *Merge, 1 + DefIndex * SourcesPerDef + Index); + if (!SourceReg) + return false; + Sources.push_back(*SourceReg); + } + auto Built = buildMergeLike(Unmerge.getReg(DefIndex), Sources); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(Unmerge.getReg(DefIndex)); + } + } else { + const auto FirstMergeSource = registerOperand(*Merge, 1); + if (!FirstMergeSource) + return false; + auto MergeSourceType = MRI.getType(*FirstMergeSource); + if (!MergeSourceType) + return std::unexpected(MergeSourceType.error()); + if (!ConvertOpcode && *DestinationType != *MergeSourceType) { + if (DestinationType->isPointer()) + ConvertOpcode = opcode(GenericOpcode::G_INTTOPTR); + else if (MergeSourceType->isPointer()) + ConvertOpcode = opcode(GenericOpcode::G_PTRTOINT); + else + ConvertOpcode = opcode(GenericOpcode::G_BITCAST); + } + for (std::size_t Index = 0; Index < DefCount; ++Index) { + const auto MergeSource = registerOperand(*Merge, Index + 1); + if (!MergeSource) + return false; + if (ConvertOpcode) { + if (!MRI.useEmpty(Unmerge.getReg(Index))) { + auto Built = buildUnary( + static_cast<GenericOpcode>(ConvertOpcode->value()), + Unmerge.getReg(Index), *MergeSource); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(Unmerge.getReg(Index)); + } + } else { + auto Replaced = replaceRegOrBuildCopy( + Unmerge.getReg(Index), *MergeSource, UpdatedDefs, Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + } + } + } + markInstAndDefDead(Instruction, *Merge, DeadInstructions); + return true; +} + +inline Expected<bool> LegalizationArtifactCombiner::tryCombineExtract( + MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs) { + const auto Destination = registerOperand(Instruction, 0); + const auto OriginalSource = registerOperand(Instruction, 1); + const auto OffsetValue = immediateOperand(Instruction, 2); + if (!Destination || !OriginalSource || !OffsetValue || *OffsetValue < 0) + return false; + const Register Source = lookThroughCopyInstrs(*OriginalSource); + MachineInstr *Merge = MRI.getVRegDef(Source); + if (Merge == nullptr) + return false; + if (auto Point = Builder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (hasOpcode(Merge, GenericOpcode::G_IMPLICIT_DEF)) { + auto Built = Builder.buildImplicitDef(*Destination); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *Merge, DeadInstructions); + return true; + } + if (!GMergeLikeInstr::classof(Merge)) + return false; + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto SourceType = MRI.getType(Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + const std::size_t SourceCount = Merge->operandCount() - 1; + if (SourceCount == 0) + return false; + const std::uint64_t MergeSourceSize = + SourceType->minimumBitWidth() / SourceCount; + const std::uint64_t Offset = static_cast<std::uint64_t>(*OffsetValue); + const std::size_t FirstSource = + static_cast<std::size_t>(Offset / MergeSourceSize); + const std::size_t LastSource = static_cast<std::size_t>( + (Offset + DestinationType->minimumBitWidth() - 1) / MergeSourceSize); + if (FirstSource != LastSource || FirstSource >= SourceCount) + return false; + const auto MergeSource = registerOperand(*Merge, FirstSource + 1); + if (!MergeSource) + return false; + auto Built = Builder.buildExtract( + *Destination, *MergeSource, + Offset - FirstSource * MergeSourceSize); + if (!Built) + return std::unexpected(Built.error()); + UpdatedDefs.push_back(*Destination); + markInstAndDefDead(Instruction, *Merge, DeadInstructions); + return true; +} + +inline Expected<Register> +LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDef( + Register DefReg, std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType) { + CurrentBest = {}; + Visited.clear(); + auto Found = findValueFromDefImpl(DefReg, StartBit, Size, DestinationType); + if (!Found) + return std::unexpected(Found.error()); + return *Found == DefReg ? Register{} : *Found; +} + +inline Expected<Register> +LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromConcat( + GConcatVectors &Instruction, std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType) { + if (Instruction.getNumSources() == 0) + return CurrentBest; + const Register FirstSource = Instruction.getSourceReg(0); + auto FirstType = Combiner.MRI.getType(FirstSource); + if (!FirstType) + return std::unexpected(FirstType.error()); + const std::uint64_t SourceSize = FirstType->minimumBitWidth(); + if (SourceSize == 0) + return CurrentBest; + const std::size_t SourceIndex = static_cast<std::size_t>(StartBit / SourceSize); + const std::uint64_t SourceOffset = StartBit % SourceSize; + if (SourceIndex >= Instruction.getNumSources() || + SourceOffset + Size > SourceSize) + return CurrentBest; + const Register Source = Instruction.getSourceReg(SourceIndex); + if (SourceOffset == 0 && Size == SourceSize) + CurrentBest = Source; + return findValueFromDefImpl(Source, SourceOffset, Size, DestinationType); +} + +inline Expected<Register> +LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromBuildVector( + GBuildVector &Instruction, std::uint64_t StartBit, std::uint64_t Size) { + if (Instruction.getNumSources() == 0) + return CurrentBest; + const Register FirstSource = Instruction.getSourceReg(0); + auto FirstType = Combiner.MRI.getType(FirstSource); + if (!FirstType) + return std::unexpected(FirstType.error()); + const std::uint64_t SourceSize = FirstType->minimumBitWidth(); + if (SourceSize == 0 || StartBit % SourceSize != 0 || Size < SourceSize || + Size % SourceSize != 0) + return CurrentBest; + const std::size_t FirstIndex = static_cast<std::size_t>(StartBit / SourceSize); + const std::size_t SourceCount = static_cast<std::size_t>(Size / SourceSize); + if (FirstIndex + SourceCount > Instruction.getNumSources()) + return CurrentBest; + if (SourceCount == 1) + return Instruction.getSourceReg(FirstIndex); + if (FirstIndex == 0 && SourceCount == Instruction.getNumSources()) + return Instruction.getReg(0); + + auto VectorType = LowLevelType::makeFixedVector(SourceCount, *FirstType); + if (!VectorType) + return std::unexpected(VectorType.error()); + auto Legal = Combiner.isInstLegal(LegalizationQuery( + opcode(GenericOpcode::G_BUILD_VECTOR), {*VectorType, *FirstType})); + if (!Legal) + return std::unexpected(Legal.error()); + if (!*Legal) + return CurrentBest; + + std::vector<Register> Sources; + Sources.reserve(SourceCount); + for (std::size_t Index = FirstIndex; Index < FirstIndex + SourceCount; + ++Index) + Sources.push_back(Instruction.getSourceReg(Index)); + auto Destination = Combiner.MRI.createVirtualRegister(*VectorType); + if (!Destination) + return std::unexpected(Destination.error()); + auto Built = Combiner.buildMergeLike(*Destination, Sources); + if (!Built) + return std::unexpected(Built.error()); + return *Destination; +} + +inline Expected<Register> +LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromInsert( + MachineInstr &Instruction, std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType) { + const auto Container = registerOperand(Instruction, 1); + const auto Inserted = registerOperand(Instruction, 2); + const auto InsertOffset = immediateOperand(Instruction, 3); + if (!Container || !Inserted || !InsertOffset || *InsertOffset < 0) + return CurrentBest; + auto InsertedType = Combiner.MRI.getType(*Inserted); + if (!InsertedType) + return std::unexpected(InsertedType.error()); + const std::uint64_t Offset = static_cast<std::uint64_t>(*InsertOffset); + const std::uint64_t InsertedEnd = Offset + InsertedType->minimumBitWidth(); + const std::uint64_t End = StartBit + Size; + if (End <= Offset || InsertedEnd <= StartBit) + return findValueFromDefImpl(*Container, StartBit, Size, DestinationType); + if (Offset <= StartBit && End <= InsertedEnd) { + const std::uint64_t NewStart = StartBit - Offset; + if (NewStart == 0 && Size == InsertedType->minimumBitWidth()) + CurrentBest = *Inserted; + return findValueFromDefImpl(*Inserted, NewStart, Size, DestinationType); + } + return Register{}; +} + +inline Expected<Register> +LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromExtension( + MachineInstr &Instruction, std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType) { + const auto Source = registerOperand(Instruction, 1); + if (!Source) + return CurrentBest; + auto SourceType = Combiner.MRI.getType(*Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + if (!SourceType->isCategoryNeutralScalar() || + StartBit + Size > SourceType->minimumBitWidth()) + return CurrentBest; + if (StartBit == 0 && SourceType->minimumBitWidth() == Size) + CurrentBest = *Source; + return findValueFromDefImpl(*Source, StartBit, Size, DestinationType); +} + +inline Expected<Register> +LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromTrunc( + MachineInstr &Instruction, std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType) { + const auto Source = registerOperand(Instruction, 1); + if (!Source) + return CurrentBest; + auto SourceType = Combiner.MRI.getType(*Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + if (!SourceType->isCategoryNeutralScalar()) + return CurrentBest; + return findValueFromDefImpl(*Source, StartBit, Size, DestinationType); +} + +inline Expected<Register> +LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl( + Register DefReg, std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType) { + if (!DefReg.isVirtual() || !Visited.insert(DefReg).second) + return CurrentBest; + auto Definition = Combiner.definitionIgnoringCopies(DefReg); + if (!Definition) + return std::unexpected(Definition.error()); + MachineInstr *Instruction = Definition->first; + DefReg = Definition->second; + if (Instruction == nullptr) + return CurrentBest; + + switch (static_cast<GenericOpcode>(Instruction->opcode().value())) { + case GenericOpcode::G_CONCAT_VECTORS: + return findValueFromConcat( + castGenericMachineInstr<GConcatVectors>(*Instruction), StartBit, Size, + DestinationType); + case GenericOpcode::G_UNMERGE_VALUES: { + auto DefType = Combiner.MRI.getType(DefReg); + if (!DefType) + return std::unexpected(DefType.error()); + const std::size_t DefIndex = getDefIndex(*Instruction, DefReg); + const auto Source = registerOperand(*Instruction, + Instruction->operandCount() - 1); + if (!Source) + return CurrentBest; + auto Found = findValueFromDefImpl( + *Source, StartBit + DefIndex * DefType->minimumBitWidth(), Size, + DestinationType); + if (!Found) + return std::unexpected(Found.error()); + if (!Found->isNoRegister()) + return *Found; + if (StartBit == 0 && Size == DefType->minimumBitWidth()) + return DefReg; + return CurrentBest; + } + case GenericOpcode::G_BUILD_VECTOR: + return findValueFromBuildVector( + castGenericMachineInstr<GBuildVector>(*Instruction), StartBit, Size); + case GenericOpcode::G_INSERT: + return findValueFromInsert(*Instruction, StartBit, Size, DestinationType); + case GenericOpcode::G_TRUNC: + return findValueFromTrunc(*Instruction, StartBit, Size, DestinationType); + case GenericOpcode::G_SEXT: + case GenericOpcode::G_ZEXT: + case GenericOpcode::G_ANYEXT: + return findValueFromExtension(*Instruction, StartBit, Size, + DestinationType); + case GenericOpcode::G_IMPLICIT_DEF: { + auto Type = Combiner.MRI.getType(DefReg); + if (!Type) + return std::unexpected(Type.error()); + if (*Type == DestinationType) + return DefReg; + auto Undef = Combiner.MRI.createVirtualRegister(DestinationType); + if (!Undef) + return std::unexpected(Undef.error()); + auto Built = Combiner.Builder.buildImplicitDef(*Undef); + if (!Built) + return std::unexpected(Built.error()); + return *Undef; + } + default: + return CurrentBest; + } +} + +inline Expected<bool> +LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs( + GUnmerge &Instruction, GISelChangeObserver &Observer, + std::vector<Register> &UpdatedDefs) { + if (Instruction.getNumDefs() == 0) + return false; + auto DestinationType = Combiner.MRI.getType(Instruction.getReg(0)); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + bool AllDead = true; + for (std::size_t Index = 0; Index < Instruction.getNumDefs(); ++Index) { + const Register Def = Instruction.getReg(Index); + if (Combiner.MRI.useEmpty(Def)) + continue; + auto Found = findValueFromDef(Def, 0, DestinationType->minimumBitWidth(), + *DestinationType); + if (!Found) + return std::unexpected(Found.error()); + if (Found->isNoRegister()) { + AllDead = false; + continue; + } + auto FoundType = Combiner.MRI.getType(*Found); + if (!FoundType) + return std::unexpected(FoundType.error()); + if (*FoundType != *DestinationType) { + AllDead = false; + continue; + } + auto Replaced = Combiner.replaceRegOrBuildCopy(Def, *Found, UpdatedDefs, + Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + Observer.changingInstr(Instruction); + auto Restored = Instruction.operandAt(Index)->setRegister(Def); + if (!Restored) + return std::unexpected(Restored.error()); + Observer.changedInstr(Instruction); + } + return AllDead; +} + +inline Expected<GUnmerge *> +LegalizationArtifactCombiner::ArtifactValueFinder::findUnmergeThatDefinesReg( + Register Reg, std::uint64_t Size, std::size_t &DefOperandIndex) { + auto Type = Combiner.MRI.getType(Reg); + if (!Type) + return std::unexpected(Type.error()); + CurrentBest = {}; + Visited.clear(); + auto Found = findValueFromDefImpl(Reg, 0, Size, *Type); + if (!Found) + return std::unexpected(Found.error()); + if (Found->isNoRegister()) + return nullptr; + auto Definition = Combiner.definitionIgnoringCopies(*Found); + if (!Definition) + return std::unexpected(Definition.error()); + if (!GUnmerge::classof(Definition->first)) + return nullptr; + DefOperandIndex = getDefIndex(*Definition->first, Definition->second); + return &castGenericMachineInstr<GUnmerge>(*Definition->first); +} + +inline Expected<bool> +LegalizationArtifactCombiner::ArtifactValueFinder::isSequenceFromUnmerge( + GMergeLikeInstr &Instruction, std::size_t MergeStartIndex, + GUnmerge *Unmerge, std::size_t UnmergeStartIndex, + std::size_t ElementCount, std::uint64_t ElementSize, bool AllowUndef) { + for (std::size_t Index = 0; Index < ElementCount; ++Index) { + const Register Source = Instruction.getSourceReg(MergeStartIndex + Index); + std::size_t SourceDefIndex = 0; + auto SourceUnmerge = + findUnmergeThatDefinesReg(Source, ElementSize, SourceDefIndex); + if (!SourceUnmerge) + return std::unexpected(SourceUnmerge.error()); + if (*SourceUnmerge == Unmerge) { + if (SourceDefIndex != UnmergeStartIndex + Index) + return false; + continue; + } + MachineInstr *Definition = Combiner.MRI.getVRegDef(Source); + if (!AllowUndef || + !hasOpcode(Definition, GenericOpcode::G_IMPLICIT_DEF)) + return false; + } + return true; +} + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h new file mode 100644 index 0000000..9a34898 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h @@ -0,0 +1,47 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_LEGALIZERHELPER_H +#define RCC_CODEGEN_GLOBALISEL_LEGALIZERHELPER_H + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/LegalizerInfo.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/Support/Error.h" + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class GISelChangeObserver; + +class LegalizerHelper final { +public: + MachineIRBuilder &MIRBuilder; + GISelChangeObserver &Observer; + + LegalizerHelper(MachineFunction &Function, const LegalizerInfo &Info, + GISelChangeObserver &Observer, MachineIRBuilder &MIRBuilder); + + [[nodiscard]] Expected<void> legalize(MachineInstr &Instruction, + const LegalizationDecision &Decision); + [[nodiscard]] Expected<void> lower(MachineInstr &Instruction, + const LegalizationDecision &Decision); + [[nodiscard]] Expected<void> lowerVAArg(MachineInstr &Instruction); + [[nodiscard]] Expected<void> widenScalar(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType WideType); + [[nodiscard]] Expected<void> widenScalarSrc(MachineInstr &Instruction, LowLevelType WideType, + std::size_t OperandIndex, + GenericOpcode ExtensionOpcode); + [[nodiscard]] Expected<void> widenScalarDst(MachineInstr &Instruction, LowLevelType WideType, + std::size_t OperandIndex = 0, + GenericOpcode TruncOpcode = GenericOpcode::G_TRUNC); + +private: + MachineFunction &Function; + MachineRegisterInfo &MRI; + const LegalizerInfo &Info; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_LEGALIZERHELPER_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h index 218a4c6..d3515f3 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h @@ -3,15 +3,27 @@ #ifndef RCC_CODEGEN_GLOBALISEL_LEGALIZERINFO_H #define RCC_CODEGEN_GLOBALISEL_LEGALIZERINFO_H +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineIRTypes.h" #include "rcc/Support/Error.h" +#include <cstddef> #include <cstdint> +#include <functional> +#include <initializer_list> +#include <optional> +#include <tuple> +#include <unordered_map> +#include <utility> +#include <vector> namespace rcc { class MachineFunction; class MachineInstr; class TargetDescription; +class LegalizerHelper; enum class LegalizationAction : std::uint8_t { Legal, @@ -28,25 +40,170 @@ enum class LegalizationAction : std::uint8_t { ChangeAddressSpace, }; +struct LegalizationMemoryDesc final { + std::optional<LowLevelType> Type; + MemorySize Size; + std::uint64_t AlignmentInBits = 0; + std::uint32_t AddressSpace = 0; + AtomicOperation Operation = AtomicOperation::None; + AtomicOrdering SuccessOrdering = AtomicOrdering::NotAtomic; + AtomicOrdering FailureOrdering = AtomicOrdering::NotAtomic; + SyncScopeID SyncScope; +}; + +struct LegalizeMemoryRule final { + LowLevelType ValueType; + LowLevelType AddressType; + LowLevelType MemoryType; + std::uint64_t MinimumAlignmentInBits = 0; +}; + +struct LegalizationQuery final { + Opcode InstructionOpcode; + std::vector<LowLevelType> Types; + std::vector<std::vector<std::size_t>> TypeOperands; + std::vector<LegalizationMemoryDesc> MemoryOperands; + + LegalizationQuery(Opcode InstructionOpcode, std::vector<LowLevelType> Types, + std::vector<LegalizationMemoryDesc> MemoryOperands = {}) + : InstructionOpcode(InstructionOpcode), Types(std::move(Types)), + MemoryOperands(std::move(MemoryOperands)) {} +}; + +struct LegalizationDecision final { + LegalizationAction Action = LegalizationAction::Unsupported; + std::size_t TypeIndex = 0; + LowLevelType NewType; +}; + +using LegalityPredicate = std::function<bool(const LegalizationQuery &)>; +using LegalizeMutation = + std::function<std::pair<std::size_t, LowLevelType>(const LegalizationQuery &)>; + +class LegalizeRule final { +public: + LegalizeRule(LegalityPredicate Predicate, LegalizationAction Action, + LegalizeMutation Mutation = {}); + + [[nodiscard]] bool matches(const LegalizationQuery &Query) const; + [[nodiscard]] LegalizationDecision apply(const LegalizationQuery &Query) const; + +private: + LegalityPredicate Predicate; + LegalizationAction Action; + LegalizeMutation Mutation; +}; + +class LegalizeRuleSet final { +public: + LegalizeRuleSet &actionIf(LegalizationAction Action, LegalityPredicate Predicate, + LegalizeMutation Mutation = {}); + LegalizeRuleSet &actionFor(LegalizationAction Action, + std::initializer_list<LowLevelType> Types); + LegalizeRuleSet &actionFor( + LegalizationAction Action, + std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &actionFor( + LegalizationAction Action, + std::initializer_list<std::tuple<LowLevelType, LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &legalIf(LegalityPredicate Predicate); + LegalizeRuleSet &customIf(LegalityPredicate Predicate); + LegalizeRuleSet &lowerIf(LegalityPredicate Predicate); + LegalizeRuleSet &libcallIf(LegalityPredicate Predicate); + LegalizeRuleSet &unsupportedIf(LegalityPredicate Predicate); + LegalizeRuleSet &widenScalarIf(LegalityPredicate Predicate, LegalizeMutation Mutation); + LegalizeRuleSet &narrowScalarIf(LegalityPredicate Predicate, LegalizeMutation Mutation); + LegalizeRuleSet &moreElementsIf(LegalityPredicate Predicate, LegalizeMutation Mutation); + LegalizeRuleSet &fewerElementsIf(LegalityPredicate Predicate, LegalizeMutation Mutation); + LegalizeRuleSet &bitcastIf(LegalityPredicate Predicate, LegalizeMutation Mutation); + + LegalizeRuleSet &legalFor(std::initializer_list<LowLevelType> Types); + LegalizeRuleSet &legalFor(bool Enabled, std::initializer_list<LowLevelType> Types); + LegalizeRuleSet &legalFor( + std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &legalFor( + bool Enabled, std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &legalFor( + std::initializer_list<std::tuple<LowLevelType, LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &customFor(std::initializer_list<LowLevelType> Types); + LegalizeRuleSet &customFor(bool Enabled, std::initializer_list<LowLevelType> Types); + LegalizeRuleSet &customFor( + std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &customFor( + bool Enabled, std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &lowerFor(std::initializer_list<LowLevelType> Types); + LegalizeRuleSet &lowerFor( + std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &libcallFor(std::initializer_list<LowLevelType> Types); + LegalizeRuleSet &libcallFor(bool Enabled, std::initializer_list<LowLevelType> Types); + LegalizeRuleSet &libcallFor( + std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &libcallFor( + bool Enabled, std::initializer_list<std::pair<LowLevelType, LowLevelType>> Types); + LegalizeRuleSet &legalForTypesWithMemDesc( + std::initializer_list<LegalizeMemoryRule> Rules); + + LegalizeRuleSet &widenScalarToNextPow2(std::size_t TypeIndex, + std::uint32_t MinimumBitWidth = 0); + LegalizeRuleSet &minScalar(std::size_t TypeIndex, LowLevelType MinimumType); + LegalizeRuleSet &minScalar(bool Enabled, std::size_t TypeIndex, + LowLevelType MinimumType); + LegalizeRuleSet &maxScalar(std::size_t TypeIndex, LowLevelType MaximumType); + LegalizeRuleSet &maxScalar(bool Enabled, std::size_t TypeIndex, + LowLevelType MaximumType); + LegalizeRuleSet &clampScalar(std::size_t TypeIndex, LowLevelType MinimumType, + LowLevelType MaximumType); + LegalizeRuleSet &scalarSameSizeAs(std::size_t TypeIndex, std::size_t ReferenceTypeIndex); + LegalizeRuleSet &lowerIfMemSizeNotByteSizePow2(std::size_t MemoryIndex = 0); + LegalizeRuleSet &alwaysLegal(); + LegalizeRuleSet &lower(); + LegalizeRuleSet &libcall(); + + [[nodiscard]] std::optional<LegalizationDecision> + apply(const LegalizationQuery &Query) const; + +private: + std::vector<LegalizeRule> Rules; +}; + class LegalizerInfo { public: virtual ~LegalizerInfo() = default; - [[nodiscard]] virtual Expected<LegalizationAction> - classify(const MachineInstr &Instruction, const MachineFunction &Function, - const TargetDescription &Target) const = 0; + [[nodiscard]] static Expected<LegalizationQuery> + buildQuery(const MachineInstr &Instruction, const MachineFunction &Function, + const TargetDescription &Target); + + [[nodiscard]] Expected<LegalizationDecision> + getDecision(const MachineInstr &Instruction, const MachineFunction &Function, + const TargetDescription &Target) const; + + [[nodiscard]] Expected<LegalizationDecision> + getDecision(const LegalizationQuery &Query) const; - [[nodiscard]] virtual Expected<void> lower(MachineInstr &Instruction, MachineFunction &Function, - const TargetDescription &Target, - LegalizationAction Action) const = 0; + [[nodiscard]] Expected<bool> isLegal(const LegalizationQuery &Query) const; + [[nodiscard]] Expected<bool> isUnsupported(const LegalizationQuery &Query) const; + + [[nodiscard]] virtual Expected<void> + legalizeCustom(LegalizerHelper &Helper, MachineInstr &Instruction, + const LegalizationDecision &Decision) const = 0; // This hook performs read-only target checks before a lowering mutation is committed. [[nodiscard]] virtual Expected<void> validateLowering(const MachineInstr &, const MachineFunction &, const TargetDescription &, - LegalizationAction) const { + const LegalizationDecision &) const { return {}; } + +protected: + [[nodiscard]] LegalizeRuleSet &getActionDefinitionsBuilder(Opcode InstructionOpcode); + [[nodiscard]] LegalizeRuleSet & + getActionDefinitionsBuilder(std::initializer_list<Opcode> InstructionOpcodes); + +private: + std::unordered_map<Opcode, LegalizeRuleSet> RuleSets; + std::unordered_map<Opcode, Opcode> RuleAliases; }; } // namespace rcc |