diff options
Diffstat (limited to 'backend/include/rcc/CodeGen/GlobalISel')
8 files changed, 195 insertions, 20 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/GISelChangeObserver.h b/backend/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h index 9538f20..cc0c5a0 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h +++ b/backend/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h @@ -22,8 +22,7 @@ public: virtual void changedInstr(MachineInstr &Instruction) = 0; }; -class GISelObserverWrapper final : public MachineFunction::Delegate, - public GISelChangeObserver { +class GISelObserverWrapper final : public MachineFunction::Delegate, public GISelChangeObserver { public: GISelObserverWrapper() = default; explicit GISelObserverWrapper(GISelChangeObserver &Observer) { @@ -50,8 +49,7 @@ private: class MachineFunctionDelegateInstaller final { public: - MachineFunctionDelegateInstaller(MachineFunction &Function, - MachineFunction::Delegate &Delegate); + MachineFunctionDelegateInstaller(MachineFunction &Function, MachineFunction::Delegate &Delegate); MachineFunctionDelegateInstaller(const MachineFunctionDelegateInstaller &) = delete; MachineFunctionDelegateInstaller &operator=(const MachineFunctionDelegateInstaller &) = delete; ~MachineFunctionDelegateInstaller(); diff --git a/backend/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h b/backend/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h index d0a176d..ea3532c 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h +++ b/backend/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h @@ -20,7 +20,9 @@ public: [[nodiscard]] Register getReg(std::size_t Index) const { const MachineOperand *Operand = operandAt(Index); assert(Operand != nullptr && Operand->isRegister()); - return *Operand->registerValue(); + const Register *Reg = Operand->getIf<Register>(); + assert(Reg != nullptr); + return *Reg; } [[nodiscard]] static bool classof(const MachineInstr *Instruction) noexcept { @@ -99,8 +101,7 @@ template <typename InstructionT> } template <typename InstructionT> -[[nodiscard]] const InstructionT & -castGenericMachineInstr(const MachineInstr &Instruction) { +[[nodiscard]] const InstructionT &castGenericMachineInstr(const MachineInstr &Instruction) { assert(InstructionT::classof(&Instruction)); return static_cast<const InstructionT &>(Instruction); } diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h index 7e2961d..c0c7be0 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h @@ -101,8 +101,11 @@ public: break; case GenericOpcode::G_TRUNC: Changed = tryCombineTrunc(Instruction, DeadInstructions, UpdatedDefs, Observer); - if (Changed && !*Changed) - UpdatedDefs.push_back(*Instruction.operandAt(0)->registerValue()); + if (Changed && !*Changed) { + const Register *Destination = Instruction.operandAt(0)->getIf<Register>(); + assert(Destination != nullptr); + UpdatedDefs.push_back(*Destination); + } break; } if (!Changed) @@ -377,11 +380,11 @@ private: } } - [[nodiscard]] Expected<bool> isInstUnsupported(LegalizationQuery Query) const { + [[nodiscard]] Expected<bool> isInstUnsupported(const LegalizationQuery &Query) const { return LI.isUnsupported(Query); } - [[nodiscard]] Expected<bool> isInstLegal(LegalizationQuery Query) const { + [[nodiscard]] Expected<bool> isInstLegal(const LegalizationQuery &Query) const { return LI.isLegal(Query); } }; @@ -438,12 +441,15 @@ inline Expected<void> LegalizationArtifactCombiner::buildConstant(Register Desti inline Expected<Register> LegalizationArtifactCombiner::buildConstant(LowLevelType Type, APInt Value) { - auto Destination = MRI.createVirtualRegister(Type); - if (!Destination) - return std::unexpected(Destination.error()); - auto Built = buildConstant(*Destination, std::move(Value)); + 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; } @@ -1309,7 +1315,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( Destinations.reserve(NewDefCount); for (std::size_t Index = 0; Index < NewDefCount; ++Index) Destinations.push_back(Unmerge.getReg(SourceIndex * NewDefCount + Index)); - Register SplitSource = *registerOperand(*Merge, SourceIndex + 1); + 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) diff --git a/backend/include/rcc/CodeGen/GlobalISel/Legalizer.h b/backend/include/rcc/CodeGen/GlobalISel/Legalizer.h index dfeda22..358ed1a 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/Legalizer.h +++ b/backend/include/rcc/CodeGen/GlobalISel/Legalizer.h @@ -3,6 +3,7 @@ #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" @@ -12,10 +13,12 @@ namespace rcc { class Legalizer final : public MachineFunctionPass { public: - explicit Legalizer(const LegalizerInfo *Info) : Info(Info) {} - explicit Legalizer(const LegalizerInfo &Info) : Info(&Info) {} - explicit Legalizer(std::unique_ptr<LegalizerInfo> Info) - : OwnedInfo(std::move(Info)), Info(OwnedInfo.get()) {} + Legalizer(const LegalizerInfo *Info, OptimizationLevel Optimization) + : Info(Info), Optimization(Optimization) {} + Legalizer(const LegalizerInfo &Info, OptimizationLevel Optimization) + : Info(&Info), Optimization(Optimization) {} + Legalizer(std::unique_ptr<LegalizerInfo> Info, OptimizationLevel Optimization) + : OwnedInfo(std::move(Info)), Info(OwnedInfo.get()), Optimization(Optimization) {} [[nodiscard]] const MachinePassContract &contract() const noexcept override; [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, @@ -29,6 +32,7 @@ private: std::unique_ptr<LegalizerInfo> OwnedInfo; const LegalizerInfo *Info = nullptr; + OptimizationLevel Optimization; }; } // namespace rcc diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h index 0fdc89f..ece0793 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h @@ -70,6 +70,10 @@ private: LowLevelType NarrowType); [[nodiscard]] Expected<void> narrowScalarExt(MachineInstr &Instruction, std::size_t TypeIndex, LowLevelType NarrowType); + [[nodiscard]] Expected<void> widenScalarAddSubOverflow(MachineInstr &Instruction, + std::size_t TypeIndex, + LowLevelType WideType); + [[nodiscard]] Expected<void> lowerSignedAddSubOverflow(MachineInstr &Instruction); MachineFunction &Function; MachineRegisterInfo &MRI; diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h index 5deefd4..3433e3a 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h @@ -137,6 +137,7 @@ public: 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 &minScalar(std::size_t TypeIndex, LowLevelType MinimumType); LegalizeRuleSet &minScalar(bool Enabled, std::size_t TypeIndex, LowLevelType MinimumType); |