diff options
Diffstat (limited to 'backend/include/rcc/CodeGen/GlobalISel')
16 files changed, 2971 insertions, 0 deletions
diff --git a/backend/include/rcc/CodeGen/GlobalISel/CSEInfo.h b/backend/include/rcc/CodeGen/GlobalISel/CSEInfo.h new file mode 100644 index 0000000..27bc2a3 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/CSEInfo.h @@ -0,0 +1,114 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_CSEINFO_H +#define RCC_CODEGEN_GLOBALISEL_CSEINFO_H + +#include "rcc/ADT/APInt.h" +#include "rcc/CodeGen/CSEConfigBase.h" +#include "rcc/CodeGen/CommandFlags.h" +#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/GlobalISel/GISelWorkList.h" +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/Support/Error.h" + +#include <cstddef> +#include <cstdint> +#include <memory> +#include <span> +#include <unordered_map> +#include <vector> + +namespace rcc { + +class MachineBasicBlock; +class MachineFunction; +class MachineInstr; +class MachineIRBuilderResult; + +class CSEConfigFull final : public CSEConfigBase { +public: + [[nodiscard]] bool shouldCSEOpcode(Opcode InstructionOpcode) const noexcept override; +}; + +class CSEConfigConstantOnly final : public CSEConfigBase { +public: + [[nodiscard]] bool shouldCSEOpcode(Opcode InstructionOpcode) const noexcept override; +}; + +[[nodiscard]] std::unique_ptr<CSEConfigBase> getStandardCSEConfigForOpt(OptimizationLevel Level); + +class GISelCSEInfo final : public GISelChangeObserver { +public: + GISelCSEInfo() = default; + GISelCSEInfo(const GISelCSEInfo &) = delete; + GISelCSEInfo &operator=(const GISelCSEInfo &) = delete; + ~GISelCSEInfo() override = default; + + void setCSEConfig(std::unique_ptr<CSEConfigBase> Config) noexcept; + [[nodiscard]] bool shouldCSE(Opcode InstructionOpcode) const noexcept; + [[nodiscard]] Expected<void> analyze(MachineFunction &Function); + [[nodiscard]] Expected<void> verify(); + void releaseMemory() noexcept; + + void erasingInstr(MachineInstr &Instruction) override; + void createdInstr(MachineInstr &Instruction) override; + void changingInstr(MachineInstr &Instruction) override; + void changedInstr(MachineInstr &Instruction) override; + +private: + struct CSEKey final { + const MachineBasicBlock *Block = nullptr; + Opcode InstructionOpcode; + std::vector<std::uint64_t> Profile; + + friend bool operator==(const CSEKey &, const CSEKey &) = default; + }; + + struct CSEKeyHash final { + [[nodiscard]] std::size_t operator()(const CSEKey &Key) const noexcept; + }; + + [[nodiscard]] Expected<void> appendRegisterProfile(std::vector<std::uint64_t> &Profile, + Register Reg, bool IsDefinition) const; + [[nodiscard]] Expected<void> appendResultProfile(std::vector<std::uint64_t> &Profile, + const MachineIRBuilderResult &Result) const; + [[nodiscard]] Expected<CSEKey> profileInstruction(const MachineInstr &Instruction) const; + [[nodiscard]] Expected<CSEKey> profileBuilderInstruction( + Opcode InstructionOpcode, std::span<const MachineIRBuilderResult> Destinations, + std::span<const Register> Sources, std::span<const std::int64_t> Immediates, + MachineInstrFlags Flags, const MachineBasicBlock &Block) const; + [[nodiscard]] Expected<CSEKey> profileConstant(const MachineIRBuilderResult &Destination, + const APInt &Value, + const MachineBasicBlock &Block) const; + + void recordNewInstruction(MachineInstr &Instruction); + [[nodiscard]] Expected<void> handleRecordedInstruction(MachineInstr &Instruction); + [[nodiscard]] Expected<void> handleRecordedInstructions(); + void handleRemoveInstruction(MachineInstr &Instruction) noexcept; + [[nodiscard]] Expected<void> insertInstruction(MachineInstr &Instruction); + + [[nodiscard]] Expected<MachineInstr *> getMachineInstrIfExists( + Opcode InstructionOpcode, std::span<const MachineIRBuilderResult> Destinations, + std::span<const Register> Sources, std::span<const std::int64_t> Immediates, + MachineInstrFlags Flags, MachineBasicBlock &Block); + [[nodiscard]] Expected<MachineInstr *> + getConstantIfExists(const MachineIRBuilderResult &Destination, const APInt &Value, + MachineBasicBlock &Block); + void countOpcodeHit(Opcode InstructionOpcode) noexcept; + + MachineFunction *Function = nullptr; + std::unique_ptr<CSEConfigBase> Config; + std::unordered_map<CSEKey, MachineInstr *, CSEKeyHash> CSEMap; + std::unordered_map<const MachineInstr *, CSEKey> InstructionMapping; + GISelWorkList<8> TemporaryInstructions; + std::unordered_map<std::uint32_t, std::size_t> OpcodeHitTable; + bool HandlingRecordedInstructions = false; + + friend class CSEMIRBuilder; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_CSEINFO_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/CSEMIRBuilder.h b/backend/include/rcc/CodeGen/GlobalISel/CSEMIRBuilder.h new file mode 100644 index 0000000..1adf474 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/CSEMIRBuilder.h @@ -0,0 +1,43 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_CSEMIRBUILDER_H +#define RCC_CODEGEN_GLOBALISEL_CSEMIRBUILDER_H + +#include "rcc/CodeGen/MachineIRBuilder.h" + +#include <cstdint> +#include <span> + +namespace rcc { + +class CSEMIRBuilder final : public MachineIRBuilder { +public: + using MachineIRBuilder::buildConstant; + using MachineIRBuilder::buildInstr; + using MachineIRBuilder::MachineIRBuilder; + + [[nodiscard]] Expected<MachineInstr *> + buildInstr(Opcode InstructionOpcode, std::span<const MachineIRBuilderResult> Destinations, + std::span<const Register> Sources) const override; + [[nodiscard]] Expected<MachineInstr *> buildConstant(MachineIRBuilderResult Destination, + APInt Value) const override; + [[nodiscard]] Expected<MachineInstr *> buildSExtInReg(MachineIRBuilderResult Destination, + Register Source, + std::uint32_t Width) const override; + [[nodiscard]] Expected<MachineInstr *> buildExtract(MachineIRBuilderResult Destination, + Register Source, + std::uint64_t Offset) const override; + +private: + [[nodiscard]] bool canPerformCSE(Opcode InstructionOpcode) const noexcept; + [[nodiscard]] bool dominatesInsertionPoint(const MachineInstr &Instruction) const noexcept; + [[nodiscard]] Expected<void> makeInstructionDominate(MachineInstr &Instruction) const; + [[nodiscard]] Expected<MachineInstr *> + generateCopyIfRequired(const MachineIRBuilderResult &Destination, + MachineInstr &Instruction) const; + [[nodiscard]] Expected<MachineInstr *> memoize(MachineInstr &Instruction) const; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_CSEMIRBUILDER_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/Combiner.h b/backend/include/rcc/CodeGen/GlobalISel/Combiner.h new file mode 100644 index 0000000..9ef7ed7 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/Combiner.h @@ -0,0 +1,50 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_COMBINER_H +#define RCC_CODEGEN_GLOBALISEL_COMBINER_H + +#include "rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h" +#include "rcc/CodeGen/MachinePassManager.h" + +#include <cstddef> +#include <string> +#include <utility> + +namespace rcc { + +class GlobalISelCombinerPass final : public MachineFunctionPass { +public: + GlobalISelCombinerPass(const GIMatchTable &Table, const GIMatchTableExecutor &Executor, + std::string PassName, std::size_t MaximumRewrites = 4096, + std::size_t MaximumIterations = 8) noexcept + : Table(&Table), Executor(&Executor), PassName(std::move(PassName)), + MaximumRewrites(MaximumRewrites), MaximumIterations(MaximumIterations) { + Contract.Name = this->PassName; + Contract.Requires = {MachineFunctionProperty::IsSSA}; + Contract.VerificationStage = PipelineStage::MachineIRInput; + Contract.ThreadSafety = PassThreadSafety::ThreadSafe; + Contract.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers}; + } + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected<MachinePassResult> + runImplementation(MachineFunction &Function, const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) const; + + const GIMatchTable *Table; + const GIMatchTableExecutor *Executor; + std::string PassName; + std::size_t MaximumRewrites; + std::size_t MaximumIterations; + MachinePassContract Contract; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_COMBINER_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h new file mode 100644 index 0000000..f191db2 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h @@ -0,0 +1,149 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTOR_H +#define RCC_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTOR_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/Support/Error.h" + +#include <cstdint> +#include <optional> +#include <span> +#include <string_view> +#include <vector> + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class TargetDescription; + +enum class GIMatchTypeKind : std::uint8_t { + Any, + Scalar, + Pointer, +}; + +enum class GIMatchImmediateTransform : std::uint8_t { + Identity, + Negate, + PlusOne, +}; + +enum class GIMatchTableOpcode : std::uint8_t { + CheckOpcode, + CheckOperandType, + CheckInstructionFlag, + ClearInstructionFlags, + CheckOperandBank, + CheckOperandClass, + CheckIntegerPredicate, + CheckFloatingPredicate, + CheckMemorySize, + CheckTargetPredicate, + CheckOperandImmediateRanges, + CheckOperandDefConstantRanges, + CheckOperandDefOpcode, + CheckOperandDefIntegerPredicate, + CheckOperandDefOperandConstantRanges, + CaptureDefOperand, + CreateTemporary, + CreateTemporaryType, + MutateOpcode, + BuildInstruction, + RenderOperand, + RenderComplexOperand, + RenderCapturedOperand, + RenderCapturedTypeBits, + RenderPhysicalRegister, + RenderTemporary, + RenderCapturedImmediate, + RenderImmediate, + ReplaceRootWithCapturedOperand, + EraseOperandDefinition, + Complete, +}; + +struct GIMatchTableInstruction final { + GIMatchTableOpcode Opcode = GIMatchTableOpcode::Complete; + std::uint16_t OperandIndex = 0; + std::uint32_t Value = 0; + std::uint32_t Auxiliary = 0; + std::int64_t Immediate = 0; + std::string_view Symbol; +}; + +struct GIMatchComplexInstruction final { + Opcode ResultOpcode; + LowLevelType ResultType; + std::vector<MachineOperand> Operands; +}; + +struct GIMatchComplexOperand final { + std::optional<MachineOperand> Operand; + std::optional<GIMatchComplexInstruction> Instruction; +}; + +struct GIMatchTableConstantRange final { + std::int64_t Minimum = 0; + std::int64_t Maximum = 0; +}; + +struct GIMatchTableRule final { + std::string_view Name; + std::uint32_t Priority = 0; + std::uint32_t FirstInstruction = 0; + std::uint32_t InstructionCount = 0; +}; + +enum class GIMatchTableKind : std::uint8_t { + Selection, + Combiner, +}; + +struct GIMatchTable final { + std::span<const GIMatchTableInstruction> Instructions; + std::span<const GIMatchTableRule> Rules; + std::span<const GIMatchTableConstantRange> ConstantRanges; + GIMatchTableKind Kind = GIMatchTableKind::Selection; +}; + +class GIMatchTableExecutor { +public: + virtual ~GIMatchTableExecutor() = default; + + [[nodiscard]] Expected<bool> match(const GIMatchTable &Table, const MachineInstr &Instruction, + const MachineFunction &Function, + const TargetDescription &Target) const; + + // A false result means that no table rule matched. The executor completes all + // predicates before applying the selected rule to MachineIR. + [[nodiscard]] Expected<bool> select(const GIMatchTable &Table, MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) const; + + // Match and apply one generated GlobalISel combiner rule. + [[nodiscard]] Expected<bool> combine(const GIMatchTable &Table, MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) const; + +protected: + [[nodiscard]] virtual Expected<bool> + matchesTargetPredicate(std::string_view Name, const MachineInstr &Instruction, + const MachineFunction &Function, const TargetDescription &Target) const; + + [[nodiscard]] virtual Expected<std::optional<GIMatchComplexOperand>> + renderComplexOperand(std::string_view Name, const MachineInstr &Instruction, + const MachineFunction &Function, const TargetDescription &Target, + std::uint32_t OperandIndex) const; + + [[nodiscard]] virtual Expected<void> + finalizeGeneratedInstruction(MachineInstr &Output, MachineFunction &Function, + const TargetDescription &Target, MachineInstrFlags InputFlags, + bool InputMayRaiseFPException) const; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTOR_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h b/backend/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h new file mode 100644 index 0000000..cc0c5a0 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h @@ -0,0 +1,64 @@ +// 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/GISelValueTracking.h b/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h new file mode 100644 index 0000000..e51f8c1 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h @@ -0,0 +1,53 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_GISELVALUETRACKING_H +#define RCC_CODEGEN_GLOBALISEL_GISELVALUETRACKING_H + +#include "rcc/ADT/APInt.h" +#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/Support/Error.h" + +#include <cstdint> + +namespace rcc { + +class MachineFunction; +class MachineRegisterInfo; +class TargetDescription; + +class GISelValueTracking final : public GISelChangeObserver { +public: + GISelValueTracking(const MachineFunction &Function, const TargetDescription &Target, + unsigned MaxDepth = 6) noexcept; + + [[nodiscard]] const MachineFunction &getMachineFunction() const noexcept { + return Function; + } + + [[nodiscard]] Expected<APInt> getKnownZeroes(Register Reg) const; + [[nodiscard]] Expected<std::uint32_t> computeNumSignBits(Register Reg, unsigned Depth = 0) const; + + void erasingInstr(MachineInstr &) override {} + void createdInstr(MachineInstr &) override {} + void changingInstr(MachineInstr &) override {} + void changedInstr(MachineInstr &) override {} + +private: + struct KnownBits final { + APInt Zero; + APInt One; + }; + + [[nodiscard]] Expected<KnownBits> makeUnknown(std::uint32_t BitWidth) const; + [[nodiscard]] Expected<KnownBits> getKnownBits(Register Reg, unsigned Depth = 0) const; + + const MachineFunction &Function; + const MachineRegisterInfo &MRI; + const TargetDescription &Target; + unsigned MaxDepth; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_GISELVALUETRACKING_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..ea3532c --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h @@ -0,0 +1,111 @@ +// 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()); + const Register *Reg = Operand->getIf<Register>(); + assert(Reg != nullptr); + return *Reg; + } + + [[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/InstructionSelect.h b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelect.h new file mode 100644 index 0000000..33b1659 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelect.h @@ -0,0 +1,31 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_H +#define RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_H + +#include "rcc/CodeGen/GlobalISel/InstructionSelector.h" +#include "rcc/CodeGen/MachinePassManager.h" + +namespace rcc { + +class InstructionSelect final : public MachineFunctionPass { +public: + explicit InstructionSelect(const InstructionSelector *Info) : Info(Info) {} + explicit InstructionSelect(const InstructionSelector &Info) : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected<MachinePassResult> + runImplementation(MachineFunction &Function, const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses); + + const InstructionSelector *Info; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h new file mode 100644 index 0000000..8e5b56d --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h @@ -0,0 +1,45 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H +#define RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H + +#include "rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h" +#include "rcc/Support/Error.h" + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class TargetDescription; + +class InstructionSelector : public GIMatchTableExecutor { +public: + ~InstructionSelector() override = default; + + [[nodiscard]] virtual Expected<void> select(MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &Target) const = 0; + + [[nodiscard]] virtual Expected<void> + constrainSelectedInstruction(MachineInstr &, MachineFunction &, const TargetDescription &) const { + return {}; + } + + [[nodiscard]] Expected<void> propagateSelectionFlags(MachineInstr &Output, + MachineInstrFlags InputFlags, + bool InputMayRaiseFPException, + const TargetDescription &Target) const; + + [[nodiscard]] Expected<void> propagateSelectionFlags(MachineInstr &Output, + const MachineInstr &Input, + const TargetDescription &Target) const; + +protected: + [[nodiscard]] Expected<void> + finalizeGeneratedInstruction(MachineInstr &Output, MachineFunction &Function, + const TargetDescription &Target, MachineInstrFlags InputFlags, + bool InputMayRaiseFPException) const override; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_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..12225cf --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h @@ -0,0 +1,1730 @@ +// 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/GISelChangeObserver.h" +#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h" +#include "rcc/CodeGen/GlobalISel/GenericMachineInstrs.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; + GISelValueTracking *VT; + + [[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, + GISelValueTracking *ValueTracking = nullptr) + : Builder(Builder), MRI(MRI), LI(Info), VT(ValueTracking) {} + + [[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: { + const auto Destination = Instruction.operandAt(0)->registerValue(); + if (Destination) { + for (MachineOperand &Use : MRI.useOperands(*Destination)) { + MachineInstr *User = Use.parent(); + if (User == nullptr) + continue; + if (User->opcode() == opcode(GenericOpcode::G_UNMERGE_VALUES) || + User->opcode() == opcode(GenericOpcode::G_TRUNC)) { + UpdatedDefs.push_back(*Destination); + break; + } + } + } + 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) { + const Register *Destination = Instruction.operandAt(0)->getIf<Register>(); + assert(Destination != nullptr); + UpdatedDefs.push_back(*Destination); + } + 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->eraseFromParent(); + 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(const LegalizationQuery &Query) const { + return LI.isUnsupported(Query); + } + + [[nodiscard]] Expected<bool> isInstLegal(const 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 Built = Builder.buildConstant(Type, std::move(Value)); + if (!Built) + return std::unexpected(Built.error()); + const MachineOperand *Definition = (*Built)->operandAt(0); + const Register *Destination = Definition == nullptr ? nullptr : Definition->getIf<Register>(); + if (Destination == nullptr || !Definition->isDef()) { + return makeUnexpected(ErrorCode::InternalError, + "constant builder returned an instruction without a register definition"); + } + 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()); + bool ElideAnd = false; + if (VT != nullptr) { + auto KnownZeroes = VT->getKnownZeroes(WideSource); + if (!KnownZeroes) + return std::unexpected(KnownZeroes.error()); + auto CoveredBits = KnownZeroes->bitwiseOr(*Mask); + if (!CoveredBits) + return std::unexpected(CoveredBits.error()); + ElideAnd = CoveredBits->isAllOnes(); + } + if (ElideAnd) { + auto Replaced = replaceRegOrBuildCopy(*Destination, WideSource, UpdatedDefs, Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + } else { + 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; + } + bool ElideSExtInReg = false; + if (VT != nullptr) { + auto SignBits = VT->computeNumSignBits(WideSource); + if (!SignBits) + return std::unexpected(SignBits.error()); + ElideSExtInReg = *SignBits > DestinationType->scalarBitWidth() - SourceType->scalarBitWidth(); + } + if (ElideSExtInReg) { + auto Replaced = replaceRegOrBuildCopy(*Destination, WideSource, UpdatedDefs, Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + } else { + 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)); + const auto SplitSourceOperand = registerOperand(*Merge, SourceIndex + 1); + if (!SplitSourceOperand) + return makeUnexpected(ErrorCode::VerificationError, + "merge source is not a register operand"); + Register SplitSource = SplitSourceOperand.value(); + 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/Legalizer.h b/backend/include/rcc/CodeGen/GlobalISel/Legalizer.h new file mode 100644 index 0000000..8f2f3f7 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/Legalizer.h @@ -0,0 +1,50 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_LEGALIZER_H +#define RCC_CODEGEN_GLOBALISEL_LEGALIZER_H + +#include "rcc/CodeGen/CommandFlags.h" +#include "rcc/CodeGen/GlobalISel/LegalizerInfo.h" +#include "rcc/CodeGen/MachinePassManager.h" +#include "rcc/CodeGen/TargetCallLowering.h" + +#include <memory> + +namespace rcc { + +class Legalizer final : public MachineFunctionPass { +public: + Legalizer(const LegalizerInfo *Info, OptimizationLevel Optimization, + LibcallLoweringInfo Libcalls = {}, + GlobalISelAbortMode AbortMode = GlobalISelAbortMode::Enable) + : Info(Info), Optimization(Optimization), Libcalls(Libcalls), AbortMode(AbortMode) {} + Legalizer(const LegalizerInfo &Info, OptimizationLevel Optimization, + LibcallLoweringInfo Libcalls = {}, + GlobalISelAbortMode AbortMode = GlobalISelAbortMode::Enable) + : Info(&Info), Optimization(Optimization), Libcalls(Libcalls), AbortMode(AbortMode) {} + Legalizer(std::unique_ptr<LegalizerInfo> Info, OptimizationLevel Optimization, + LibcallLoweringInfo Libcalls = {}, + GlobalISelAbortMode AbortMode = GlobalISelAbortMode::Enable) + : OwnedInfo(std::move(Info)), Info(OwnedInfo.get()), Optimization(Optimization), + Libcalls(Libcalls), AbortMode(AbortMode) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected<MachinePassResult> + runImplementation(MachineFunction &Function, const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses); + + std::unique_ptr<LegalizerInfo> OwnedInfo; + const LegalizerInfo *Info = nullptr; + OptimizationLevel Optimization; + LibcallLoweringInfo Libcalls; + GlobalISelAbortMode AbortMode; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_LEGALIZER_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..fa4e5e2 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h @@ -0,0 +1,158 @@ +// 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" + +#include <vector> + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class GISelChangeObserver; +struct LibcallLoweringInfo; + +class LegalizerHelper final { +public: + MachineIRBuilder &MIRBuilder; + GISelChangeObserver &Observer; + + LegalizerHelper(MachineFunction &Function, const LegalizerInfo &Info, + GISelChangeObserver &Observer, MachineIRBuilder &MIRBuilder, + const LibcallLoweringInfo *Libcalls = nullptr); + + [[nodiscard]] Expected<void> legalize(MachineInstr &Instruction, + const LegalizationDecision &Decision); + [[nodiscard]] Expected<void> lower(MachineInstr &Instruction, + const LegalizationDecision &Decision); + [[nodiscard]] Expected<void> lowerAbsToAddXor(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerAbsDiffToSelect(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerAbsDiffToMinMax(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerMinMax(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerThreewayCompare(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerDivRem(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerHighMultiply(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerBitCount(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerBswap(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerFunnelShift(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerRotate(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerDynStackAlloc(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerStackSave(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerStackRestore(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerMemcpyInline(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerVAArg(MachineInstr &Instruction); + [[nodiscard]] Expected<void> libcall(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> narrowScalarSrc(MachineInstr &Instruction, LowLevelType NarrowType, + std::size_t OperandIndex); + [[nodiscard]] Expected<void> narrowScalarDst(MachineInstr &Instruction, LowLevelType NarrowType, + std::size_t OperandIndex, + GenericOpcode ExtensionOpcode); + [[nodiscard]] Expected<void> widenScalarDst(MachineInstr &Instruction, LowLevelType WideType, + std::size_t OperandIndex = 0, + GenericOpcode TruncOpcode = GenericOpcode::G_TRUNC); + + [[nodiscard]] Expected<void> narrowScalar(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + +private: + [[nodiscard]] Expected<void> widenScalarMergeValues(MachineInstr &Instruction, + std::size_t TypeIndex, LowLevelType WideType); + [[nodiscard]] Expected<void> + widenScalarUnmergeValues(MachineInstr &Instruction, std::size_t TypeIndex, LowLevelType WideType); + [[nodiscard]] Expected<void> insertParts(Register Destination, LowLevelType ResultType, + LowLevelType PartType, + const std::vector<Register> &PartRegisters, + LowLevelType LeftoverType = {}, + const std::vector<Register> &LeftoverRegisters = {}); + [[nodiscard]] Expected<void> extractGCDType(std::vector<Register> &Parts, LowLevelType GCDType, + Register Source); + [[nodiscard]] Expected<LowLevelType> extractGCDType(std::vector<Register> &Parts, + LowLevelType DestinationType, + LowLevelType NarrowType, Register Source); + [[nodiscard]] Expected<LowLevelType> + buildLCMMergePieces(LowLevelType DestinationType, LowLevelType NarrowType, LowLevelType GCDType, + std::vector<Register> &Registers, + GenericOpcode PadStrategy = GenericOpcode::G_ANYEXT); + [[nodiscard]] Expected<void> + buildWidenedRemergeToDst(Register Destination, LowLevelType LCMType, + const std::vector<Register> &RemergeRegisters); + [[nodiscard]] Expected<void> multiplyRegisters(std::vector<Register> &Destinations, + const std::vector<Register> &FirstSources, + const std::vector<Register> &SecondSources, + LowLevelType NarrowType); + [[nodiscard]] Expected<void> narrowScalarAddSub(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + [[nodiscard]] Expected<void> narrowScalarMul(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + [[nodiscard]] Expected<void> + narrowScalarLoadStore(MachineInstr &Instruction, std::size_t TypeIndex, LowLevelType NarrowType); + [[nodiscard]] Expected<void> reduceLoadStoreWidth(MachineInstr &Instruction, + std::size_t TypeIndex, LowLevelType NarrowType); + [[nodiscard]] Expected<void> lowerLoad(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerStore(MachineInstr &Instruction); + [[nodiscard]] Expected<void> narrowScalarBasic(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + [[nodiscard]] Expected<void> narrowScalarExt(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + [[nodiscard]] Expected<void> narrowScalarSelect(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + [[nodiscard]] Expected<void> narrowScalarShift(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + [[nodiscard]] Expected<void> narrowScalarShiftByConstant(MachineInstr &Instruction, + const APInt &Amount, + LowLevelType HalfType, + LowLevelType AmountType); + [[nodiscard]] Expected<void> narrowScalarShiftMultiway(MachineInstr &Instruction, + LowLevelType TargetType); + [[nodiscard]] Expected<void> narrowScalarShiftByConstantMultiway(MachineInstr &Instruction, + const APInt &Amount, + LowLevelType TargetType, + LowLevelType AmountType); + [[nodiscard]] Expected<void> fewerElements(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + + struct ShiftParameters final { + Register WordShift; + Register BitShift; + Register InverseBitShift; + Register Zero; + Register SignBit; + }; + + [[nodiscard]] Expected<Register> + buildConstantShiftPart(GenericOpcode Generic, std::size_t PartIndex, std::size_t PartCount, + const std::vector<Register> &SourceParts, + const ShiftParameters &Parameters, LowLevelType TargetType); + [[nodiscard]] Expected<Register> + buildVariableShiftPart(GenericOpcode Generic, Register MainOperand, Register ShiftAmount, + LowLevelType TargetType, Register CarryOperand = {}); + [[nodiscard]] Expected<void> widenScalarAddSubOverflow(MachineInstr &Instruction, + std::size_t TypeIndex, + LowLevelType WideType); + [[nodiscard]] Expected<void> widenScalarMulo(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType WideType); + [[nodiscard]] Expected<void> lowerSignedAddSubOverflow(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerSaturatingAddSubToMinMax(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerSaturatingAddSubToOverflow(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerSaturatingShiftLeft(MachineInstr &Instruction); + [[nodiscard]] Expected<void> lowerMulo(MachineInstr &Instruction); + + MachineFunction &Function; + MachineRegisterInfo &MRI; + const LegalizerInfo &Info; + const LibcallLoweringInfo *Libcalls = nullptr; +}; + +} // 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 new file mode 100644 index 0000000..78e6a32 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h @@ -0,0 +1,213 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_LEGALIZERINFO_H +#define RCC_CODEGEN_GLOBALISEL_LEGALIZERINFO_H + +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/MachineMemOperand.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 GenericOpcode : std::uint32_t; + +enum class LegalizationAction : std::uint8_t { + Legal, + Unsupported, + Custom, + Lower, + Libcall, + WidenScalar, + NarrowScalar, + MoreElements, + FewerElements, + Bitcast, + ChangeElementType, + 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 &custom(); + LegalizeRuleSet &widenScalarToNextPow2(std::size_t TypeIndex, std::uint32_t MinimumBitWidth = 0); + LegalizeRuleSet &scalarize(std::size_t TypeIndex); + 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]] 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]] 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; + + // Target intrinsic lowering runs before the ordinary legality action. + [[nodiscard]] virtual Expected<bool> legalizeIntrinsic(LegalizerHelper &, MachineInstr &) const { + return true; + } + + [[nodiscard]] virtual GenericOpcode getExtOpcodeForWideningConstant(LowLevelType SmallType) const; + + [[nodiscard]] virtual bool isSExtCheaperThanZExt(LowLevelType, LowLevelType) const { + return false; + } + + // This hook performs read-only target checks before a lowering mutation is committed. + [[nodiscard]] virtual Expected<void> validateLowering(const MachineInstr &, + const MachineFunction &, + const TargetDescription &, + 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 + +#endif // RCC_CODEGEN_GLOBALISEL_LEGALIZERINFO_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/RegBankSelect.h b/backend/include/rcc/CodeGen/GlobalISel/RegBankSelect.h new file mode 100644 index 0000000..a7fc6bf --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/RegBankSelect.h @@ -0,0 +1,27 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_REGBANKSELECT_H +#define RCC_CODEGEN_GLOBALISEL_REGBANKSELECT_H + +#include "rcc/CodeGen/MachinePassManager.h" +#include "rcc/CodeGen/RegisterBankInfo.h" + +namespace rcc { + +class RegBankSelect final : public MachineFunctionPass { +public: + explicit RegBankSelect(const RegisterBankInfo *Info) : Info(Info) {} + explicit RegBankSelect(const RegisterBankInfo &Info) : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) override; + +private: + const RegisterBankInfo *Info; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_REGBANKSELECT_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/Utils.h b/backend/include/rcc/CodeGen/GlobalISel/Utils.h new file mode 100644 index 0000000..f252454 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/Utils.h @@ -0,0 +1,58 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_UTILS_H +#define RCC_CODEGEN_GLOBALISEL_UTILS_H + +#include "rcc/ADT/APInt.h" +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/Support/Error.h" + +#include <cstddef> +#include <optional> +#include <span> +#include <vector> + +namespace rcc { + +class MachineIRBuilder; +class MachineInstr; +class MachineRegisterInfo; +class TargetDescription; + +struct ValueAndVReg final { + APInt Value; + Register VReg; +}; + +[[nodiscard]] std::optional<ValueAndVReg> +getIConstantVRegValWithLookThrough(Register VReg, const MachineRegisterInfo &MRI, + bool LookThroughInstrs = true); + +/// Check whether an instruction only defines dead virtual registers and has no +/// observable side effects. +[[nodiscard]] bool isTriviallyDead(const MachineInstr &Instruction, const MachineRegisterInfo &MRI, + const TargetDescription &Target) noexcept; + +[[nodiscard]] Expected<void> eraseInstrs(std::span<MachineInstr *const> Instructions, + MachineRegisterInfo &MRI, const TargetDescription &Target); + +[[nodiscard]] Expected<void> eraseInstr(MachineInstr &Instruction, MachineRegisterInfo &MRI, + const TargetDescription &Target); + +[[nodiscard]] Expected<void> extractParts(Register Reg, LowLevelType Type, int PartCount, + std::vector<Register> &Parts, + MachineIRBuilder &MIRBuilder, MachineRegisterInfo &MRI); + +[[nodiscard]] Expected<bool> extractParts(Register Reg, LowLevelType RegisterType, + LowLevelType MainType, LowLevelType &LeftoverType, + std::vector<Register> &Parts, + std::vector<Register> &LeftoverParts, + MachineIRBuilder &MIRBuilder, MachineRegisterInfo &MRI); + +[[nodiscard]] Expected<LowLevelType> getLCMType(LowLevelType OriginalType, LowLevelType TargetType); +[[nodiscard]] Expected<LowLevelType> getGCDType(LowLevelType OriginalType, LowLevelType TargetType); + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_UTILS_H |