diff options
23 files changed, 1568 insertions, 393 deletions
diff --git a/backend/include/rcc/CodeGen/CSEConfigBase.h b/backend/include/rcc/CodeGen/CSEConfigBase.h new file mode 100644 index 0000000..68aa26e --- /dev/null +++ b/backend/include/rcc/CodeGen/CSEConfigBase.h @@ -0,0 +1,21 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_CSECONFIGBASE_H +#define RCC_CODEGEN_CSECONFIGBASE_H + +#include "rcc/CodeGen/MachineIRTypes.h" + +namespace rcc { + +class CSEConfigBase { +public: + virtual ~CSEConfigBase() = default; + + [[nodiscard]] virtual bool shouldCSEOpcode(Opcode) const noexcept { + return false; + } +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_CSECONFIGBASE_H 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); diff --git a/backend/include/rcc/CodeGen/MachineIRBuilder.h b/backend/include/rcc/CodeGen/MachineIRBuilder.h index e830837..f87adfe 100644 --- a/backend/include/rcc/CodeGen/MachineIRBuilder.h +++ b/backend/include/rcc/CodeGen/MachineIRBuilder.h @@ -14,6 +14,7 @@ #include <initializer_list> #include <memory> #include <optional> +#include <span> #include <string> #include <utility> #include <vector> @@ -24,7 +25,9 @@ class MachineBasicBlock; class MachineFunction; class MachineInstr; class MachineMemOperand; +class MachineRegisterInfo; class RegisterMask; +class GISelCSEInfo; class MachineInstrBuilder final { public: @@ -143,7 +146,32 @@ private: friend class MachineIRBuilder; }; -class MachineIRBuilder final { +class MachineIRBuilderResult final { +public: + enum class Kind : std::uint8_t { + Register, + Type, + }; + + MachineIRBuilderResult(Register Reg) noexcept : Reg(Reg), ResultKind(Kind::Register) {} + MachineIRBuilderResult(LowLevelType Type) noexcept : Type(Type), ResultKind(Kind::Type) {} + + [[nodiscard]] Kind kind() const noexcept { + return ResultKind; + } + + [[nodiscard]] Register reg() const noexcept; + [[nodiscard]] LowLevelType type() const noexcept; + [[nodiscard]] Expected<LowLevelType> type(const MachineRegisterInfo &MRI) const; + [[nodiscard]] Expected<void> addDef(MachineRegisterInfo &MRI, MachineInstrBuilder &Builder) const; + +private: + Register Reg; + LowLevelType Type; + Kind ResultKind; +}; + +class MachineIRBuilder { public: MachineIRBuilder(MachineFunction &Function, const TargetDescription &Target) noexcept : Function(&Function), Target(&Target) {} @@ -151,12 +179,13 @@ public: MachineIRBuilder &operator=(const MachineIRBuilder &) = delete; MachineIRBuilder(MachineIRBuilder &&) = delete; MachineIRBuilder &operator=(MachineIRBuilder &&) = delete; + virtual ~MachineIRBuilder() = default; [[nodiscard]] MachineFunction &function() noexcept { return *Function; } - [[nodiscard]] const MachineFunction &function() const noexcept { + [[nodiscard]] MachineFunction &function() const noexcept { return *Function; } @@ -168,6 +197,22 @@ public: return InsertBlock; } + [[nodiscard]] MachineInstr *insertionInstruction() const noexcept { + return InsertBefore; + } + + [[nodiscard]] GISelCSEInfo *getCSEInfo() noexcept { + return CSEInfo; + } + + [[nodiscard]] GISelCSEInfo *getCSEInfo() const noexcept { + return CSEInfo; + } + + void setCSEInfo(GISelCSEInfo *Info) noexcept { + CSEInfo = Info; + } + [[nodiscard]] Expected<void> verifyInsertPoint() const; [[nodiscard]] Expected<void> setInsertPoint(MachineBasicBlock &Block); @@ -179,63 +224,79 @@ public: } [[nodiscard]] Expected<MachineInstrBuilder> buildInstr(Opcode InstructionOpcode) const; - [[nodiscard]] Expected<MachineInstr *> buildInstr(Opcode InstructionOpcode, - std::initializer_list<Register> Destinations, - std::initializer_list<Register> Sources) const; - [[nodiscard]] Expected<MachineInstr *> buildTrunc(Register Destination, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildCopy(Register Destination, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildImplicitDef(Register Destination) const; - [[nodiscard]] Expected<MachineInstr *> buildAnyExt(Register Destination, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildZExt(Register Destination, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildSExt(Register Destination, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildUndef(Register Destination) const; - [[nodiscard]] Expected<MachineInstr *> buildAnyExtOrTrunc(Register Destination, + [[nodiscard]] Expected<MachineInstr *> + buildInstr(Opcode InstructionOpcode, std::initializer_list<MachineIRBuilderResult> Destinations, + std::initializer_list<Register> Sources) const; + [[nodiscard]] virtual Expected<MachineInstr *> + buildInstr(Opcode InstructionOpcode, std::span<const MachineIRBuilderResult> Destinations, + std::span<const Register> Sources) const; + [[nodiscard]] Expected<MachineInstr *> buildTrunc(MachineIRBuilderResult Destination, + Register Source) const; + [[nodiscard]] Expected<MachineInstr *> buildCopy(MachineIRBuilderResult Destination, + Register Source) const; + [[nodiscard]] Expected<MachineInstr *> buildImplicitDef(MachineIRBuilderResult Destination) const; + [[nodiscard]] Expected<MachineInstr *> buildAnyExt(MachineIRBuilderResult Destination, + Register Source) const; + [[nodiscard]] Expected<MachineInstr *> buildZExt(MachineIRBuilderResult Destination, + Register Source) const; + [[nodiscard]] Expected<MachineInstr *> buildSExt(MachineIRBuilderResult Destination, + Register Source) const; + [[nodiscard]] Expected<MachineInstr *> buildUndef(MachineIRBuilderResult Destination) const; + [[nodiscard]] Expected<MachineInstr *> buildAnyExtOrTrunc(MachineIRBuilderResult Destination, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildSExtOrTrunc(Register Destination, + [[nodiscard]] Expected<MachineInstr *> buildSExtOrTrunc(MachineIRBuilderResult Destination, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildConstant(Register Destination, APInt Value) const; - [[nodiscard]] Expected<MachineInstr *> buildConstant(Register Destination, + [[nodiscard]] virtual Expected<MachineInstr *> buildConstant(MachineIRBuilderResult Destination, + APInt Value) const; + [[nodiscard]] Expected<MachineInstr *> buildConstant(MachineIRBuilderResult Destination, std::int64_t Value) const; - [[nodiscard]] Expected<MachineInstr *> buildSExtInReg(Register Destination, Register Source, - std::uint32_t Width) const; - [[nodiscard]] Expected<MachineInstr *> buildAnd(Register Destination, Register Left, + [[nodiscard]] virtual Expected<MachineInstr *> + buildSExtInReg(MachineIRBuilderResult Destination, Register Source, std::uint32_t Width) const; + [[nodiscard]] Expected<MachineInstr *> buildAnd(MachineIRBuilderResult Destination, Register Left, Register Right) const; - [[nodiscard]] Expected<MachineInstr *> buildOr(Register Destination, Register Left, + [[nodiscard]] Expected<MachineInstr *> buildOr(MachineIRBuilderResult Destination, Register Left, Register Right) const; - [[nodiscard]] Expected<MachineInstr *> buildXor(Register Destination, Register Left, + [[nodiscard]] Expected<MachineInstr *> buildXor(MachineIRBuilderResult Destination, Register Left, Register Right) const; - [[nodiscard]] Expected<MachineInstr *> buildAdd(Register Destination, Register Left, + [[nodiscard]] Expected<MachineInstr *> buildAdd(MachineIRBuilderResult Destination, Register Left, Register Right) const; - [[nodiscard]] Expected<MachineInstr *> buildSub(Register Destination, Register Left, + [[nodiscard]] Expected<MachineInstr *> buildSub(MachineIRBuilderResult Destination, Register Left, Register Right) const; - [[nodiscard]] Expected<MachineInstr *> buildShl(Register Destination, Register Left, + [[nodiscard]] Expected<MachineInstr *> buildShl(MachineIRBuilderResult Destination, Register Left, Register Right) const; - [[nodiscard]] Expected<MachineInstr *> buildLShr(Register Destination, Register Left, - Register Right) const; - [[nodiscard]] Expected<MachineInstr *> buildAShr(Register Destination, Register Left, - Register Right) const; - [[nodiscard]] Expected<MachineInstr *> buildPtrToInt(Register Destination, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildIntToPtr(Register Destination, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildICmp(IntegerPredicate Predicate, Register Destination, + [[nodiscard]] Expected<MachineInstr *> buildLShr(MachineIRBuilderResult Destination, + Register Left, Register Right) const; + [[nodiscard]] Expected<MachineInstr *> buildAShr(MachineIRBuilderResult Destination, + Register Left, Register Right) const; + [[nodiscard]] Expected<MachineInstr *> buildPtrToInt(MachineIRBuilderResult Destination, + Register Source) const; + [[nodiscard]] Expected<MachineInstr *> buildIntToPtr(MachineIRBuilderResult Destination, + Register Source) const; + [[nodiscard]] Expected<MachineInstr *> buildICmp(IntegerPredicate Predicate, + MachineIRBuilderResult Destination, Register Left, Register Right) const; [[nodiscard]] Expected<MachineInstr *> - buildMergeLikeInstr(Register Destination, const std::vector<Register> &Sources) const; + buildMergeLikeInstr(MachineIRBuilderResult Destination, + const std::vector<Register> &Sources) const; [[nodiscard]] Expected<MachineInstr *> - buildMergeValues(Register Destination, const std::vector<Register> &Sources) const; + buildMergeValues(MachineIRBuilderResult Destination, const std::vector<Register> &Sources) const; [[nodiscard]] Expected<MachineInstr *> buildUnmergeValues(const std::vector<Register> &Destinations, Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildExtract(Register Destination, Register Source, - std::uint64_t Offset) const; - [[nodiscard]] Expected<MachineInstr *> buildInsert(Register Destination, Register Source, - Register Inserted, std::uint64_t Offset) const; + [[nodiscard]] virtual Expected<MachineInstr *> + buildExtract(MachineIRBuilderResult Destination, Register Source, std::uint64_t Offset) const; + [[nodiscard]] Expected<MachineInstr *> buildInsert(MachineIRBuilderResult Destination, + Register Source, Register Inserted, + std::uint64_t Offset) const; private: - [[nodiscard]] Expected<MachineInstr *> buildUnary(Opcode InstructionOpcode, Register Destination, - Register Source) const; - [[nodiscard]] Expected<MachineInstr *> buildBinary(Opcode InstructionOpcode, Register Destination, - Register Left, Register Right) const; [[nodiscard]] Expected<MachineInstr *> - buildExtOrTrunc(Opcode ExtensionOpcode, Register Destination, Register Source) const; + buildUnary(Opcode InstructionOpcode, MachineIRBuilderResult Destination, Register Source) const; + [[nodiscard]] Expected<MachineInstr *> buildBinary(Opcode InstructionOpcode, + MachineIRBuilderResult Destination, + Register Left, Register Right) const; + [[nodiscard]] Expected<MachineInstr *> buildExtOrTrunc(Opcode ExtensionOpcode, + MachineIRBuilderResult Destination, + Register Source) const; [[nodiscard]] Expected<LowLevelType> registerType(Register Reg) const; [[nodiscard]] Expected<void> validateBlock(const MachineBasicBlock &Block) const; [[nodiscard]] Expected<void> validateInstruction(const MachineInstr &Instruction) const; @@ -244,6 +305,7 @@ private: const TargetDescription *Target; MachineBasicBlock *InsertBlock = nullptr; MachineInstr *InsertBefore = nullptr; + GISelCSEInfo *CSEInfo = nullptr; }; } // namespace rcc diff --git a/backend/include/rcc/Target/RISCV/RISCVPipeline.h b/backend/include/rcc/Target/RISCV/RISCVPipeline.h index 267c497..07f3ece 100644 --- a/backend/include/rcc/Target/RISCV/RISCVPipeline.h +++ b/backend/include/rcc/Target/RISCV/RISCVPipeline.h @@ -3,6 +3,7 @@ #ifndef RCC_TARGET_RISCV_RISCVPIPELINE_H #define RCC_TARGET_RISCV_RISCVPIPELINE_H +#include "rcc/CodeGen/CommandFlags.h" #include "rcc/CodeGen/MachinePassManager.h" #include "rcc/Support/Error.h" #include "rcc/Target/RISCV/RISCVSubtarget.h" @@ -20,6 +21,7 @@ class TargetDescription; namespace riscv { struct RISCVPipelineOptions final { + OptimizationLevel Optimization = OptimizationLevel::O2; bool UseTargetCopyInstructions = false; }; diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index ff02a20..862caca 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -90,6 +90,7 @@ set( RCCBackendCodeGenHeaders "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CompilationUnit.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CommandFlags.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CSEConfigBase.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalObject.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericOpcodes.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/FrameIndexElimination.h" diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt index 3b01e9b..8fc50d2 100644 --- a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt +++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt @@ -2,6 +2,8 @@ set( RCCBackendGlobalISelSources + CSEInfo.cpp + CSEMIRBuilder.cpp GISelChangeObserver.cpp GISelValueTracking.cpp InstructionSelect.cpp @@ -14,6 +16,8 @@ set( set( RCCBackendGlobalISelHeaders + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/CSEInfo.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/CSEMIRBuilder.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelWorkList.h" @@ -31,6 +35,8 @@ set( target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources}) rcc_backend_register_format_files( + "${CMAKE_CURRENT_SOURCE_DIR}/CSEInfo.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/CSEMIRBuilder.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp" @@ -43,6 +49,8 @@ rcc_backend_register_format_files( ) rcc_backend_register_tidy_files( + "${CMAKE_CURRENT_SOURCE_DIR}/CSEInfo.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/CSEMIRBuilder.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp" diff --git a/backend/lib/CodeGen/GlobalISel/CSEInfo.cpp b/backend/lib/CodeGen/GlobalISel/CSEInfo.cpp new file mode 100644 index 0000000..201dedd --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/CSEInfo.cpp @@ -0,0 +1,467 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/CSEInfo.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include <bit> +#include <cstddef> +#include <cstdint> +#include <functional> +#include <memory> +#include <utility> + +namespace rcc { +namespace { + +enum class ProfileTag : std::uint64_t { + Definition, + Use, + RegisterNumber, + PhysicalRegister, + Type, + RegisterBank, + NoRegisterBank, + RegisterClass, + NoRegisterClass, + Immediate, + IntegerImmediate, + FloatingImmediate, + IntegerPredicate, + FloatingPredicate, + Flags, +}; + +void appendTypeProfile(std::vector<std::uint64_t> &Profile, LowLevelType Type, + std::optional<RegisterBankID> Bank, + std::optional<RegisterClassID> RegClass) { + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Type)); + Profile.push_back(Type.rawValue()); + if (Bank) { + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::RegisterBank)); + Profile.push_back(Bank->value()); + } else { + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::NoRegisterBank)); + } + if (RegClass) { + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::RegisterClass)); + Profile.push_back(RegClass->value()); + } else { + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::NoRegisterClass)); + } +} + +void appendAPIntProfile(std::vector<std::uint64_t> &Profile, const APInt &Value) { + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::IntegerImmediate)); + Profile.push_back(Value.bitWidth()); + Profile.push_back(Value.words().size()); + Profile.insert(Profile.end(), Value.words().begin(), Value.words().end()); +} + +void appendAPFloatProfile(std::vector<std::uint64_t> &Profile, const APFloat &Value) { + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::FloatingImmediate)); + Profile.push_back(static_cast<std::uint64_t>(Value.semantics())); + Profile.push_back(Value.words().size()); + Profile.insert(Profile.end(), Value.words().begin(), Value.words().end()); +} + +void hashCombine(std::size_t &Seed, std::size_t Value) noexcept { + Seed ^= Value + 0x9e3779b97f4a7c15ULL + (Seed << 6U) + (Seed >> 2U); +} + +} // namespace + +bool CSEConfigFull::shouldCSEOpcode(Opcode InstructionOpcode) const noexcept { + switch (static_cast<GenericOpcode>(InstructionOpcode.value())) { + default: + return false; + case GenericOpcode::G_ADD: + case GenericOpcode::G_AND: + case GenericOpcode::G_ASHR: + case GenericOpcode::G_LSHR: + case GenericOpcode::G_MUL: + case GenericOpcode::G_OR: + case GenericOpcode::G_SHL: + case GenericOpcode::G_SUB: + case GenericOpcode::G_XOR: + case GenericOpcode::G_UDIV: + case GenericOpcode::G_SDIV: + case GenericOpcode::G_UREM: + case GenericOpcode::G_SREM: + case GenericOpcode::G_CONSTANT: + case GenericOpcode::G_FCONSTANT: + case GenericOpcode::G_IMPLICIT_DEF: + case GenericOpcode::G_ZEXT: + case GenericOpcode::G_SEXT: + case GenericOpcode::G_ANYEXT: + case GenericOpcode::G_UNMERGE_VALUES: + case GenericOpcode::G_TRUNC: + case GenericOpcode::G_PTR_ADD: + case GenericOpcode::G_EXTRACT: + case GenericOpcode::G_SELECT: + case GenericOpcode::G_BUILD_VECTOR: + case GenericOpcode::G_BUILD_VECTOR_TRUNC: + case GenericOpcode::G_SEXT_INREG: + case GenericOpcode::G_FADD: + case GenericOpcode::G_FSUB: + case GenericOpcode::G_FMUL: + case GenericOpcode::G_FDIV: + case GenericOpcode::G_FABS: + case GenericOpcode::G_FMAXNUM: + case GenericOpcode::G_FMINNUM: + case GenericOpcode::G_FMAXNUM_IEEE: + case GenericOpcode::G_FMINNUM_IEEE: + return true; + } +} + +bool CSEConfigConstantOnly::shouldCSEOpcode(Opcode InstructionOpcode) const noexcept { + return InstructionOpcode == opcode(GenericOpcode::G_CONSTANT) || + InstructionOpcode == opcode(GenericOpcode::G_FCONSTANT) || + InstructionOpcode == opcode(GenericOpcode::G_IMPLICIT_DEF); +} + +std::unique_ptr<CSEConfigBase> getStandardCSEConfigForOpt(OptimizationLevel Level) { + if (Level == OptimizationLevel::O0) + return std::make_unique<CSEConfigConstantOnly>(); + return std::make_unique<CSEConfigFull>(); +} + +std::size_t GISelCSEInfo::CSEKeyHash::operator()(const CSEKey &Key) const noexcept { + std::size_t Result = std::hash<const MachineBasicBlock *>{}(Key.Block); + hashCombine(Result, std::hash<std::uint32_t>{}(Key.InstructionOpcode.value())); + for (std::uint64_t Value : Key.Profile) + hashCombine(Result, std::hash<std::uint64_t>{}(Value)); + return Result; +} + +void GISelCSEInfo::setCSEConfig(std::unique_ptr<CSEConfigBase> NewConfig) noexcept { + Config = std::move(NewConfig); +} + +bool GISelCSEInfo::shouldCSE(Opcode InstructionOpcode) const noexcept { + return Config != nullptr && isGenericOpcode(InstructionOpcode) && + Config->shouldCSEOpcode(InstructionOpcode); +} + +Expected<void> GISelCSEInfo::appendRegisterProfile(std::vector<std::uint64_t> &Profile, + Register Reg, bool IsDefinition) const { + Profile.push_back( + static_cast<std::uint64_t>(IsDefinition ? ProfileTag::Definition : ProfileTag::Use)); + if (!IsDefinition) { + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::RegisterNumber)); + Profile.push_back(Reg.opaqueValue()); + } + if (!Reg.isVirtual()) { + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::PhysicalRegister)); + Profile.push_back(Reg.opaqueValue()); + return {}; + } + if (Function == nullptr) + return makeUnexpected(ErrorCode::InternalError, "GlobalISel CSE has no machine function"); + auto Info = Function->registerInfo().virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + const std::optional<LowLevelType> &Type = Info->get().Type; + if (!Type.has_value()) { + return makeUnexpected(ErrorCode::VerificationError, + "GlobalISel CSE requires typed virtual registers"); + } + appendTypeProfile(Profile, Type.value(), Info->get().Bank, Info->get().RegClass); + return {}; +} + +Expected<void> GISelCSEInfo::appendResultProfile(std::vector<std::uint64_t> &Profile, + const MachineIRBuilderResult &Result) const { + if (Result.kind() == MachineIRBuilderResult::Kind::Register) + return appendRegisterProfile(Profile, Result.reg(), true); + Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Definition)); + appendTypeProfile(Profile, Result.type(), std::nullopt, std::nullopt); + return {}; +} + +Expected<GISelCSEInfo::CSEKey> +GISelCSEInfo::profileInstruction(const MachineInstr &Instruction) const { + if (Instruction.parent() == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "cannot profile a detached instruction"); + if (!Instruction.memOperands().empty()) { + return makeUnexpected(ErrorCode::Unsupported, + "GlobalISel CSE does not profile memory operands"); + } + + CSEKey Key{ + .Block = Instruction.parent(), .InstructionOpcode = Instruction.opcode(), .Profile = {}}; + for (const MachineOperand &Operand : Instruction.operands()) { + switch (Operand.kind()) { + case MachineOperand::Kind::Register: { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || Operand.isImplicit()) { + return makeUnexpected(ErrorCode::Unsupported, + "GlobalISel CSE does not profile implicit register operands"); + } + auto Appended = appendRegisterProfile(Key.Profile, *Reg, Operand.isDef()); + if (!Appended) + return std::unexpected(Appended.error()); + break; + } + case MachineOperand::Kind::Immediate: { + const std::int64_t *Value = Operand.getIf<std::int64_t>(); + if (Value == nullptr) + return makeUnexpected(ErrorCode::InternalError, "invalid immediate operand storage"); + Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Immediate)); + Key.Profile.push_back(std::bit_cast<std::uint64_t>(*Value)); + break; + } + case MachineOperand::Kind::IntegerImmediate: { + const auto *Value = Operand.getIf<IntegerImmediateOperand>(); + if (Value == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "invalid integer immediate operand storage"); + appendAPIntProfile(Key.Profile, Value->Value); + break; + } + case MachineOperand::Kind::FloatingImmediate: { + const auto *Value = Operand.getIf<FloatingImmediateOperand>(); + if (Value == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "invalid floating immediate operand storage"); + appendAPFloatProfile(Key.Profile, Value->Bits); + break; + } + case MachineOperand::Kind::Predicate: { + const auto *Predicate = Operand.getIf<PredicateOperand>(); + if (Predicate == nullptr) + return makeUnexpected(ErrorCode::InternalError, "invalid predicate operand storage"); + if (const IntegerPredicate *Integer = Predicate->integerPredicate()) { + Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::IntegerPredicate)); + Key.Profile.push_back(static_cast<std::uint64_t>(*Integer)); + } else if (const FloatingPredicate *Floating = Predicate->floatingPredicate()) { + Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::FloatingPredicate)); + Key.Profile.push_back(static_cast<std::uint64_t>(*Floating)); + } else { + return makeUnexpected(ErrorCode::InternalError, "empty predicate operand"); + } + break; + } + default: + return makeUnexpected(ErrorCode::Unsupported, + "GlobalISel CSE encountered an unsupported operand kind"); + } + } + Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Flags)); + Key.Profile.push_back(Instruction.flags().rawValue()); + return Key; +} + +Expected<GISelCSEInfo::CSEKey> GISelCSEInfo::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 { + CSEKey Key{.Block = &Block, .InstructionOpcode = InstructionOpcode, .Profile = {}}; + for (const MachineIRBuilderResult &Destination : Destinations) { + auto Appended = appendResultProfile(Key.Profile, Destination); + if (!Appended) + return std::unexpected(Appended.error()); + } + for (Register Source : Sources) { + auto Appended = appendRegisterProfile(Key.Profile, Source, false); + if (!Appended) + return std::unexpected(Appended.error()); + } + for (std::int64_t Immediate : Immediates) { + Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Immediate)); + Key.Profile.push_back(std::bit_cast<std::uint64_t>(Immediate)); + } + Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Flags)); + Key.Profile.push_back(Flags.rawValue()); + return Key; +} + +Expected<GISelCSEInfo::CSEKey> +GISelCSEInfo::profileConstant(const MachineIRBuilderResult &Destination, const APInt &Value, + const MachineBasicBlock &Block) const { + CSEKey Key{ + .Block = &Block, .InstructionOpcode = opcode(GenericOpcode::G_CONSTANT), .Profile = {}}; + auto Appended = appendResultProfile(Key.Profile, Destination); + if (!Appended) + return std::unexpected(Appended.error()); + appendAPIntProfile(Key.Profile, Value); + Key.Profile.push_back(static_cast<std::uint64_t>(ProfileTag::Flags)); + Key.Profile.push_back(0); + return Key; +} + +Expected<void> GISelCSEInfo::insertInstruction(MachineInstr &Instruction) { + TemporaryInstructions.remove(&Instruction); + auto Key = profileInstruction(Instruction); + if (!Key) + return std::unexpected(Key.error()); + auto [Position, Inserted] = CSEMap.emplace(*Key, &Instruction); + if (Inserted) + InstructionMapping.emplace(&Instruction, std::move(*Key)); + return {}; +} + +void GISelCSEInfo::recordNewInstruction(MachineInstr &Instruction) { + if (shouldCSE(Instruction.opcode())) + TemporaryInstructions.insert(&Instruction); +} + +Expected<void> GISelCSEInfo::handleRecordedInstruction(MachineInstr &Instruction) { + TemporaryInstructions.remove(&Instruction); + handleRemoveInstruction(Instruction); + if (Instruction.parent() == nullptr || !shouldCSE(Instruction.opcode())) + return {}; + return insertInstruction(Instruction); +} + +Expected<void> GISelCSEInfo::handleRecordedInstructions() { + if (HandlingRecordedInstructions) + return {}; + HandlingRecordedInstructions = true; + while (!TemporaryInstructions.empty()) { + MachineInstr *Instruction = TemporaryInstructions.popBack(); + if (Instruction == nullptr) + continue; + auto Handled = handleRecordedInstruction(*Instruction); + if (!Handled) { + HandlingRecordedInstructions = false; + return std::unexpected(Handled.error()); + } + } + HandlingRecordedInstructions = false; + return {}; +} + +void GISelCSEInfo::handleRemoveInstruction(MachineInstr &Instruction) noexcept { + const auto Mapping = InstructionMapping.find(&Instruction); + if (Mapping != InstructionMapping.end()) { + const auto Position = CSEMap.find(Mapping->second); + if (Position != CSEMap.end() && Position->second == &Instruction) + CSEMap.erase(Position); + InstructionMapping.erase(Mapping); + } + TemporaryInstructions.remove(&Instruction); +} + +Expected<MachineInstr *> GISelCSEInfo::getMachineInstrIfExists( + Opcode InstructionOpcode, std::span<const MachineIRBuilderResult> Destinations, + std::span<const Register> Sources, std::span<const std::int64_t> Immediates, + MachineInstrFlags Flags, MachineBasicBlock &Block) { + auto Handled = handleRecordedInstructions(); + if (!Handled) + return std::unexpected(Handled.error()); + auto Key = + profileBuilderInstruction(InstructionOpcode, Destinations, Sources, Immediates, Flags, Block); + if (!Key) + return std::unexpected(Key.error()); + const auto Position = CSEMap.find(*Key); + if (Position == CSEMap.end()) + return nullptr; + countOpcodeHit(InstructionOpcode); + return Position->second; +} + +Expected<MachineInstr *> +GISelCSEInfo::getConstantIfExists(const MachineIRBuilderResult &Destination, const APInt &Value, + MachineBasicBlock &Block) { + auto Handled = handleRecordedInstructions(); + if (!Handled) + return std::unexpected(Handled.error()); + auto Key = profileConstant(Destination, Value, Block); + if (!Key) + return std::unexpected(Key.error()); + const auto Position = CSEMap.find(*Key); + if (Position == CSEMap.end()) + return nullptr; + countOpcodeHit(opcode(GenericOpcode::G_CONSTANT)); + return Position->second; +} + +void GISelCSEInfo::countOpcodeHit(Opcode InstructionOpcode) noexcept { + ++OpcodeHitTable[InstructionOpcode.value()]; +} + +Expected<void> GISelCSEInfo::analyze(MachineFunction &NewFunction) { + if (Config == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "GlobalISel CSE configuration is not set"); + CSEMap.clear(); + InstructionMapping.clear(); + TemporaryInstructions.clear(); + OpcodeHitTable.clear(); + HandlingRecordedInstructions = false; + Function = &NewFunction; + for (MachineBasicBlock *Block = NewFunction.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (!shouldCSE(Instruction->opcode())) + continue; + auto Inserted = insertInstruction(*Instruction); + if (!Inserted) + return std::unexpected(Inserted.error()); + } + } + return {}; +} + +Expected<void> GISelCSEInfo::verify() { + auto Handled = handleRecordedInstructions(); + if (!Handled) + return std::unexpected(Handled.error()); + for (const auto &[Instruction, Key] : InstructionMapping) { + if (Instruction == nullptr || Instruction->parent() == nullptr) + return makeUnexpected(ErrorCode::InternalError, "GlobalISel CSE maps a detached instruction"); + auto CurrentKey = profileInstruction(*Instruction); + if (!CurrentKey) + return std::unexpected(CurrentKey.error()); + const auto Position = CSEMap.find(*CurrentKey); + if (*CurrentKey != Key || Position == CSEMap.end() || Position->second != Instruction) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE instruction mapping is inconsistent"); + } + } + for (const auto &[Key, Instruction] : CSEMap) { + const auto Mapping = InstructionMapping.find(Instruction); + if (Mapping == InstructionMapping.end() || Mapping->second != Key) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE table has no instruction mapping"); + } + } + return {}; +} + +void GISelCSEInfo::releaseMemory() noexcept { + CSEMap.clear(); + InstructionMapping.clear(); + TemporaryInstructions.clear(); + OpcodeHitTable.clear(); + Config.reset(); + Function = nullptr; + HandlingRecordedInstructions = false; +} + +void GISelCSEInfo::erasingInstr(MachineInstr &Instruction) { + handleRemoveInstruction(Instruction); +} + +void GISelCSEInfo::createdInstr(MachineInstr &Instruction) { + recordNewInstruction(Instruction); +} + +void GISelCSEInfo::changingInstr(MachineInstr &Instruction) { + erasingInstr(Instruction); + createdInstr(Instruction); +} + +void GISelCSEInfo::changedInstr(MachineInstr &Instruction) { + changingInstr(Instruction); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp b/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp new file mode 100644 index 0000000..e1fdaa6 --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp @@ -0,0 +1,226 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/CSEMIRBuilder.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/CSEInfo.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include <algorithm> +#include <array> +#include <cstdint> +#include <limits> +#include <span> +#include <utility> + +namespace rcc { + +bool CSEMIRBuilder::canPerformCSE(Opcode InstructionOpcode) const noexcept { + const GISelCSEInfo *Info = getCSEInfo(); + return Info != nullptr && Info->shouldCSE(InstructionOpcode); +} + +bool CSEMIRBuilder::dominatesInsertionPoint(const MachineInstr &Instruction) const noexcept { + const MachineBasicBlock *Block = insertionBlock(); + const MachineInstr *InsertBefore = insertionInstruction(); + if (Block == nullptr || Instruction.parent() != Block) + return false; + if (InsertBefore == nullptr) + return true; + for (const MachineInstr *Current = Block->firstInstruction(); Current != nullptr; + Current = Current->next()) { + if (Current == &Instruction) + return true; + if (Current == InsertBefore) + return false; + } + return false; +} + +Expected<void> CSEMIRBuilder::makeInstructionDominate(MachineInstr &Instruction) const { + MachineBasicBlock *Block = insertionBlock(); + MachineInstr *InsertBefore = insertionInstruction(); + if (Block == nullptr || Instruction.parent() != Block) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE candidate is not in the insertion block"); + } + if (&Instruction == InsertBefore) { + return const_cast<CSEMIRBuilder *>(this)->setInsertPointAfter(Instruction); + } + if (InsertBefore == nullptr || dominatesInsertionPoint(Instruction)) + return {}; + auto Removed = Block->removeInstruction(Instruction); + if (!Removed) + return std::unexpected(Removed.error()); + auto Inserted = Block->insertInstructionBefore(*InsertBefore, Instruction); + if (!Inserted) + return std::unexpected(Inserted.error()); + return {}; +} + +Expected<MachineInstr *> +CSEMIRBuilder::generateCopyIfRequired(const MachineIRBuilderResult &Destination, + MachineInstr &Instruction) const { + if (Destination.kind() == MachineIRBuilderResult::Kind::Type) + return &Instruction; + const MachineOperand *Definition = Instruction.operandAt(0); + const Register *Source = Definition == nullptr ? nullptr : Definition->getIf<Register>(); + if (Source == nullptr || !Definition->isDef()) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE candidate has no register definition"); + } + if (Destination.reg() == *Source) + return &Instruction; + return MachineIRBuilder::buildCopy(Destination, *Source); +} + +Expected<MachineInstr *> CSEMIRBuilder::memoize(MachineInstr &Instruction) const { + GISelCSEInfo *Info = getCSEInfo(); + if (Info == nullptr) + return &Instruction; + auto Inserted = Info->handleRecordedInstruction(Instruction); + if (!Inserted) + return std::unexpected(Inserted.error()); + return &Instruction; +} + +Expected<MachineInstr *> +CSEMIRBuilder::buildInstr(Opcode InstructionOpcode, + std::span<const MachineIRBuilderResult> Destinations, + std::span<const Register> Sources) const { + if (!canPerformCSE(InstructionOpcode)) + return MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + const bool CanGenerateCopies = + Destinations.size() == 1 || std::ranges::all_of(Destinations, [](const auto &Destination) { + return Destination.kind() == MachineIRBuilderResult::Kind::Type; + }); + if (!CanGenerateCopies) { + auto Built = MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources); + if (!Built) + return std::unexpected(Built.error()); + Info->handleRemoveInstruction(**Built); + return *Built; + } + + auto Existing = + Info->getMachineInstrIfExists(InstructionOpcode, Destinations, Sources, + std::span<const std::int64_t>(), MachineInstrFlags(), *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + if (Destinations.size() == 1) + return generateCopyIfRequired(Destinations.front(), **Existing); + return *Existing; + } + + auto Built = MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +Expected<MachineInstr *> CSEMIRBuilder::buildConstant(MachineIRBuilderResult Destination, + APInt Value) const { + const Opcode ConstantOpcode = opcode(GenericOpcode::G_CONSTANT); + if (!canPerformCSE(ConstantOpcode)) + return MachineIRBuilder::buildConstant(Destination, std::move(Value)); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + auto Existing = Info->getConstantIfExists(Destination, Value, *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + return generateCopyIfRequired(Destination, **Existing); + } + + auto Built = MachineIRBuilder::buildConstant(Destination, std::move(Value)); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +Expected<MachineInstr *> CSEMIRBuilder::buildSExtInReg(MachineIRBuilderResult Destination, + Register Source, std::uint32_t Width) const { + const Opcode InstructionOpcode = opcode(GenericOpcode::G_SEXT_INREG); + if (!canPerformCSE(InstructionOpcode)) + return MachineIRBuilder::buildSExtInReg(Destination, Source, Width); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + const std::array Destinations{Destination}; + const std::array Sources{Source}; + const std::array Immediates{static_cast<std::int64_t>(Width)}; + auto Existing = Info->getMachineInstrIfExists( + InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations), + std::span<const Register>(Sources), std::span<const std::int64_t>(Immediates), + MachineInstrFlags(), *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + return generateCopyIfRequired(Destination, **Existing); + } + + auto Built = MachineIRBuilder::buildSExtInReg(Destination, Source, Width); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +Expected<MachineInstr *> CSEMIRBuilder::buildExtract(MachineIRBuilderResult Destination, + Register Source, std::uint64_t Offset) const { + if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) + return MachineIRBuilder::buildExtract(Destination, Source, Offset); + const Opcode InstructionOpcode = opcode(GenericOpcode::G_EXTRACT); + if (!canPerformCSE(InstructionOpcode)) + return MachineIRBuilder::buildExtract(Destination, Source, Offset); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + const std::array Destinations{Destination}; + const std::array Sources{Source}; + const std::array Immediates{static_cast<std::int64_t>(Offset)}; + auto Existing = Info->getMachineInstrIfExists( + InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations), + std::span<const Register>(Sources), std::span<const std::int64_t>(Immediates), + MachineInstrFlags(), *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + return generateCopyIfRequired(Destination, **Existing); + } + + auto Built = MachineIRBuilder::buildExtract(Destination, Source, Offset); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp index dfa4523..77c1b0c 100644 --- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp +++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp @@ -3,6 +3,8 @@ #include "rcc/CodeGen/GlobalISel/Legalizer.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/CSEInfo.h" +#include "rcc/CodeGen/GlobalISel/CSEMIRBuilder.h" #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" #include "rcc/CodeGen/GlobalISel/GISelValueTracking.h" #include "rcc/CodeGen/GlobalISel/GISelWorkList.h" @@ -18,7 +20,9 @@ #include "rcc/CodeGen/TargetDescription.h" #include <algorithm> +#include <array> #include <cstddef> +#include <memory> #include <optional> #include <ranges> #include <string> @@ -126,7 +130,7 @@ private: std::size_t NextSuccessor = 0; }; - const auto makeFrame = [](MachineBasicBlock &Block) { + const auto MakeFrame = [](MachineBasicBlock &Block) { TraversalFrame Frame; Frame.Block = &Block; for (const MachineSuccessor &Successor : Block.successors()) { @@ -156,13 +160,13 @@ private: for (MachineBasicBlock *Root : Roots) { if (!Visited.insert(Root).second) continue; - Stack.push_back(makeFrame(*Root)); + Stack.push_back(MakeFrame(*Root)); while (!Stack.empty()) { TraversalFrame &Frame = Stack.back(); if (Frame.NextSuccessor < Frame.Successors.size()) { MachineBasicBlock *Successor = Frame.Successors[Frame.NextSuccessor++]; if (Visited.insert(Successor).second) - Stack.push_back(makeFrame(*Successor)); + Stack.push_back(MakeFrame(*Successor)); continue; } PostOrder.push_back(Frame.Block); @@ -305,9 +309,17 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi InstructionWorklist.finalize(); LegalizerWorkListManager WorkListObserver(InstructionWorklist, ArtifactWorklist); - GISelObserverWrapper Observer(WorkListObserver); + GISelCSEInfo CSEInfo; + CSEInfo.setCSEConfig(getStandardCSEConfigForOpt(Optimization)); + auto CSEAnalysis = CSEInfo.analyze(Function); + if (!CSEAnalysis) + return std::unexpected( + withErrorContext(CSEAnalysis.error(), "GlobalISel CSE analysis failed: ")); + std::array<GISelChangeObserver *, 2> AuxiliaryObservers{&WorkListObserver, &CSEInfo}; + GISelObserverWrapper Observer{std::span<GISelChangeObserver *const>(AuxiliaryObservers)}; MachineFunctionDelegateInstaller ObserverInstaller(Function, Observer); - MachineIRBuilder Builder(Function, Target); + CSEMIRBuilder Builder(Function, Target); + Builder.setCSEInfo(&CSEInfo); LegalizerHelper Helper(Function, *Info, Observer, Builder); GISelValueTracking ValueTracking(Function, Target); LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info, @@ -452,6 +464,12 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi } } while (!InstructionWorklist.empty()); + auto CSEValidation = CSEInfo.verify(); + if (!CSEValidation) { + return std::unexpected( + withErrorContext(CSEValidation.error(), "GlobalISel CSE verification failed: ")); + } + for (MachineInstr *Instruction : layoutInstructions(Function)) { const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); if (Descriptor == nullptr) diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp index def363a..a0b0981 100644 --- a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp +++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp @@ -69,21 +69,41 @@ struct ScalarLayout final { return Function.createMemOperand(std::move(Description)); } +[[nodiscard]] Expected<Register> resultRegister(MachineInstr &Instruction) { + const MachineOperand *Definition = Instruction.operandAt(0); + const Register *Result = Definition == nullptr ? nullptr : Definition->getIf<Register>(); + if (Result == nullptr || !Definition->isDef()) { + return makeUnexpected(ErrorCode::InternalError, + "machine IR builder returned an instruction without a register result"); + } + return *Result; +} + +[[nodiscard]] Expected<Register> buildConstantRegister(MachineIRBuilder &Builder, LowLevelType Type, + APInt Value) { + auto Built = Builder.buildConstant(Type, std::move(Value)); + if (!Built) + return std::unexpected(Built.error()); + return resultRegister(**Built); +} + +[[nodiscard]] Expected<Register> buildConstantRegister(MachineIRBuilder &Builder, LowLevelType Type, + std::int64_t Value) { + auto Immediate = APInt::fromSigned(Type.scalarBitWidth(), Value); + if (!Immediate) + return std::unexpected(Immediate.error()); + return buildConstantRegister(Builder, Type, std::move(*Immediate)); +} + [[nodiscard]] Expected<Register> buildConstantBefore(MachineIRBuilder &Builder, MachineInstr &Anchor, LowLevelType Type, std::uint64_t Value) { - auto Result = Builder.function().registerInfo().createVirtualRegister(Type); - if (!Result) - return std::unexpected(Result.error()); auto Immediate = APInt::fromUnsigned(Type.scalarBitWidth(), Value); if (!Immediate) return std::unexpected(Immediate.error()); if (auto Point = Builder.setInsertPointBefore(Anchor); !Point) return std::unexpected(Point.error()); - auto Built = Builder.buildConstant(*Result, std::move(*Immediate)); - if (!Built) - return std::unexpected(Built.error()); - return *Result; + return buildConstantRegister(Builder, Type, std::move(*Immediate)); } [[nodiscard]] Expected<Register> buildBinaryBefore(MachineIRBuilder &Builder, MachineInstr &Anchor, @@ -152,11 +172,12 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction return std::unexpected(Point.error()); if (WideSize >= DestinationSize) { - auto Result = MRI.createVirtualRegister(WideType); + auto BuiltResult = MIRBuilder.buildZExt(WideType, *FirstSource); + if (!BuiltResult) + return std::unexpected(BuiltResult.error()); + auto Result = resultRegister(**BuiltResult); if (!Result) return std::unexpected(Result.error()); - if (auto Built = MIRBuilder.buildZExt(*Result, *FirstSource); !Built) - return std::unexpected(Built.error()); Register ResultRegister = *Result; for (std::size_t Index = 2; Index != Instruction.operandCount(); ++Index) { @@ -171,23 +192,22 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction return makeUnexpected(ErrorCode::VerificationError, "G_MERGE_VALUES source types are inconsistent"); - auto ExtendedInput = MRI.createVirtualRegister(WideType); - auto ShiftAmount = MRI.createVirtualRegister(WideType); - auto ShiftedInput = MRI.createVirtualRegister(WideType); + auto BuiltExtendedInput = MIRBuilder.buildZExt(WideType, *Source); + if (!BuiltExtendedInput) + return std::unexpected(BuiltExtendedInput.error()); + auto ExtendedInput = resultRegister(**BuiltExtendedInput); if (!ExtendedInput) return std::unexpected(ExtendedInput.error()); + auto ShiftAmount = buildConstantRegister(MIRBuilder, WideType, + static_cast<std::int64_t>((Index - 1U) * PartSize)); if (!ShiftAmount) return std::unexpected(ShiftAmount.error()); + auto BuiltShiftedInput = MIRBuilder.buildShl(WideType, *ExtendedInput, *ShiftAmount); + if (!BuiltShiftedInput) + return std::unexpected(BuiltShiftedInput.error()); + auto ShiftedInput = resultRegister(**BuiltShiftedInput); if (!ShiftedInput) return std::unexpected(ShiftedInput.error()); - if (auto Built = MIRBuilder.buildZExt(*ExtendedInput, *Source); !Built) - return std::unexpected(Built.error()); - if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, - static_cast<std::int64_t>((Index - 1U) * PartSize)); - !Built) - return std::unexpected(Built.error()); - if (auto Built = MIRBuilder.buildShl(*ShiftedInput, *ExtendedInput, *ShiftAmount); !Built) - return std::unexpected(Built.error()); Register NextResult = *Destination; if (Index + 1U != Instruction.operandCount() || WideType != *DestinationType) { @@ -240,11 +260,12 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction const std::uint64_t RequiredPartCount = MergeCount * WideSize; if (UnmergedRegisters.size() != RequiredPartCount) { - auto UndefRegister = MRI.createVirtualRegister(*GCDType); + auto BuiltUndef = MIRBuilder.buildUndef(*GCDType); + if (!BuiltUndef) + return std::unexpected(BuiltUndef.error()); + auto UndefRegister = resultRegister(**BuiltUndef); if (!UndefRegister) return std::unexpected(UndefRegister.error()); - if (auto Built = MIRBuilder.buildUndef(*UndefRegister); !Built) - return std::unexpected(Built.error()); while (UnmergedRegisters.size() != RequiredPartCount) UnmergedRegisters.push_back(*UndefRegister); } @@ -256,11 +277,12 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction std::vector<Register> Parts( UnmergedRegisters.begin() + static_cast<std::ptrdiff_t>(Index * PartsPerGCD), UnmergedRegisters.begin() + static_cast<std::ptrdiff_t>((Index + 1U) * PartsPerGCD)); - auto MergeRegister = MRI.createVirtualRegister(WideType); + auto BuiltMerge = MIRBuilder.buildMergeLikeInstr(WideType, Parts); + if (!BuiltMerge) + return std::unexpected(BuiltMerge.error()); + auto MergeRegister = resultRegister(**BuiltMerge); if (!MergeRegister) return std::unexpected(MergeRegister.error()); - if (auto Built = MIRBuilder.buildMergeLikeInstr(*MergeRegister, Parts); !Built) - return std::unexpected(Built.error()); NewMergeRegisters.push_back(*MergeRegister); } @@ -268,11 +290,12 @@ Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction if (auto Built = MIRBuilder.buildMergeLikeInstr(*Destination, NewMergeRegisters); !Built) return std::unexpected(Built.error()); } else { - auto FinalMerge = MRI.createVirtualRegister(*WideDestinationType); + auto BuiltFinalMerge = MIRBuilder.buildMergeLikeInstr(*WideDestinationType, NewMergeRegisters); + if (!BuiltFinalMerge) + return std::unexpected(BuiltFinalMerge.error()); + auto FinalMerge = resultRegister(**BuiltFinalMerge); if (!FinalMerge) return std::unexpected(FinalMerge.error()); - if (auto Built = MIRBuilder.buildMergeLikeInstr(*FinalMerge, NewMergeRegisters); !Built) - return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildTrunc(*Destination, *FinalMerge); !Built) return std::unexpected(Built.error()); } @@ -347,16 +370,13 @@ Expected<void> LegalizerHelper::widenScalarUnmergeValues(MachineInstr &Instructi if (Destination == nullptr) return makeUnexpected(ErrorCode::VerificationError, "G_UNMERGE_VALUES requires register destinations"); - auto ShiftAmount = MRI.createVirtualRegister(*SourceType); auto ShiftedSource = MRI.createVirtualRegister(*SourceType); - if (!ShiftAmount) - return std::unexpected(ShiftAmount.error()); if (!ShiftedSource) return std::unexpected(ShiftedSource.error()); - if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, - static_cast<std::int64_t>(DestinationSize * Index)); - !Built) - return std::unexpected(Built.error()); + auto ShiftAmount = buildConstantRegister(MIRBuilder, *SourceType, + static_cast<std::int64_t>(DestinationSize * Index)); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); if (auto Built = MIRBuilder.buildLShr(*ShiftedSource, SourceRegister, *ShiftAmount); !Built) return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildTrunc(*Destination, *ShiftedSource); !Built) @@ -553,15 +573,20 @@ Expected<LowLevelType> LegalizerHelper::buildLCMMergePieces(LowLevelType Destina Register PadRegister; if (OriginalSourceCount < PartCount * SubPartCount) { - auto NewPad = MRI.createVirtualRegister(GCDType); - if (!NewPad) - return std::unexpected(NewPad.error()); - PadRegister = *NewPad; - Expected<MachineInstr *> Built = PadStrategy == GenericOpcode::G_ZEXT - ? MIRBuilder.buildConstant(PadRegister, 0) - : MIRBuilder.buildUndef(PadRegister); - if (!Built) - return std::unexpected(Built.error()); + if (PadStrategy == GenericOpcode::G_ZEXT) { + auto Pad = buildConstantRegister(MIRBuilder, GCDType, 0); + if (!Pad) + return std::unexpected(Pad.error()); + PadRegister = *Pad; + } else { + auto Built = MIRBuilder.buildUndef(GCDType); + if (!Built) + return std::unexpected(Built.error()); + auto Pad = resultRegister(**Built); + if (!Pad) + return std::unexpected(Pad.error()); + PadRegister = *Pad; + } } std::vector<Register> Remerge(static_cast<std::size_t>(PartCount)); @@ -580,15 +605,20 @@ Expected<LowLevelType> LegalizerHelper::buildLCMMergePieces(LowLevelType Destina } if (AllMergePartsArePadding && AllPadRegister.isNoRegister()) { - auto Pad = MRI.createVirtualRegister(NarrowType); - if (!Pad) - return std::unexpected(Pad.error()); - AllPadRegister = *Pad; - Expected<MachineInstr *> Built = PadStrategy == GenericOpcode::G_ZEXT - ? MIRBuilder.buildConstant(AllPadRegister, 0) - : MIRBuilder.buildUndef(AllPadRegister); - if (!Built) - return std::unexpected(Built.error()); + if (PadStrategy == GenericOpcode::G_ZEXT) { + auto Pad = buildConstantRegister(MIRBuilder, NarrowType, 0); + if (!Pad) + return std::unexpected(Pad.error()); + AllPadRegister = *Pad; + } else { + auto Built = MIRBuilder.buildUndef(NarrowType); + if (!Built) + return std::unexpected(Built.error()); + auto Pad = resultRegister(**Built); + if (!Pad) + return std::unexpected(Pad.error()); + AllPadRegister = *Pad; + } } if (!AllPadRegister.isNoRegister()) { Remerge[static_cast<std::size_t>(PartIndex)] = AllPadRegister; @@ -597,12 +627,12 @@ Expected<LowLevelType> LegalizerHelper::buildLCMMergePieces(LowLevelType Destina if (SubPartCount == 1) { Remerge[static_cast<std::size_t>(PartIndex)] = SubMerge.front(); } else { - auto RemergeRegister = MRI.createVirtualRegister(NarrowType); - if (!RemergeRegister) - return std::unexpected(RemergeRegister.error()); - auto Built = MIRBuilder.buildMergeLikeInstr(*RemergeRegister, SubMerge); + auto Built = MIRBuilder.buildMergeLikeInstr(NarrowType, SubMerge); if (!Built) return std::unexpected(Built.error()); + auto RemergeRegister = resultRegister(**Built); + if (!RemergeRegister) + return std::unexpected(RemergeRegister.error()); Remerge[static_cast<std::size_t>(PartIndex)] = *RemergeRegister; } if (AllMergePartsArePadding && AllPadRegister.isNoRegister()) @@ -701,6 +731,95 @@ Expected<void> LegalizerHelper::widenScalarDst(MachineInstr &Instruction, LowLev return Operand->setRegister(*WideDestination); } +Expected<void> LegalizerHelper::widenScalarAddSubOverflow(MachineInstr &Instruction, + std::size_t TypeIndex, + LowLevelType WideType) { + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "add/sub overflow widening requires type index zero"); + + const GenericOpcode Generic = static_cast<GenericOpcode>(Instruction.opcode().value()); + GenericOpcode ArithmeticOpcode; + GenericOpcode ExtensionOpcode; + switch (Generic) { + case GenericOpcode::G_SADDO: + ArithmeticOpcode = GenericOpcode::G_ADD; + ExtensionOpcode = GenericOpcode::G_SEXT; + break; + case GenericOpcode::G_SSUBO: + ArithmeticOpcode = GenericOpcode::G_SUB; + ExtensionOpcode = GenericOpcode::G_SEXT; + break; + case GenericOpcode::G_UADDO: + ArithmeticOpcode = GenericOpcode::G_ADD; + ExtensionOpcode = GenericOpcode::G_ZEXT; + break; + case GenericOpcode::G_USUBO: + ArithmeticOpcode = GenericOpcode::G_SUB; + ExtensionOpcode = GenericOpcode::G_ZEXT; + break; + default: + return makeUnexpected(ErrorCode::InternalError, + "unexpected opcode during add/sub overflow widening"); + } + + const Register Destination = *Instruction.operandAt(0)->getIf<Register>(); + const Register Overflow = *Instruction.operandAt(1)->getIf<Register>(); + const Register Left = *Instruction.operandAt(2)->getIf<Register>(); + const Register Right = *Instruction.operandAt(3)->getIf<Register>(); + auto OriginalType = MRI.getType(Destination); + if (!OriginalType) + return std::unexpected(OriginalType.error()); + + auto WideLeft = MRI.createVirtualRegister(WideType); + auto WideRight = MRI.createVirtualRegister(WideType); + auto WideResult = MRI.createVirtualRegister(WideType); + auto TruncatedResult = MRI.createVirtualRegister(*OriginalType); + auto ExtendedResult = MRI.createVirtualRegister(WideType); + if (!WideLeft) + return std::unexpected(WideLeft.error()); + if (!WideRight) + return std::unexpected(WideRight.error()); + if (!WideResult) + return std::unexpected(WideResult.error()); + if (!TruncatedResult) + return std::unexpected(TruncatedResult.error()); + if (!ExtendedResult) + return std::unexpected(ExtendedResult.error()); + + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = MIRBuilder.buildInstr(opcode(ExtensionOpcode), {*WideLeft}, {Left}); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildInstr(opcode(ExtensionOpcode), {*WideRight}, {Right}); !Built) + return std::unexpected(Built.error()); + if (auto Built = + MIRBuilder.buildInstr(opcode(ArithmeticOpcode), {*WideResult}, {*WideLeft, *WideRight}); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildTrunc(*TruncatedResult, *WideResult); !Built) + return std::unexpected(Built.error()); + if (auto Built = + MIRBuilder.buildInstr(opcode(ExtensionOpcode), {*ExtendedResult}, {*TruncatedResult}); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::NotEqual, Overflow, *WideResult, *ExtendedResult); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildTrunc(Destination, *WideResult); !Built) + return std::unexpected(Built.error()); + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "add/sub overflow instruction became detached during widening"); + return Block->removeInstruction(Instruction); +} + Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size_t TypeIndex, LowLevelType WideType) { auto Query = LegalizerInfo::buildQuery(Instruction, Function, MIRBuilder.target()); @@ -713,14 +832,14 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size "scalar widening has an invalid type index or target type"); } - const auto widenSource = [&](std::size_t OperandIndex, GenericOpcode ExtensionOpcode) { + const auto WidenSource = [&](std::size_t OperandIndex, GenericOpcode ExtensionOpcode) { return widenScalarSrc(Instruction, WideType, OperandIndex, ExtensionOpcode); }; - const auto widenDestination = [&](std::size_t OperandIndex = 0, + const auto WidenDestination = [&](std::size_t OperandIndex = 0, GenericOpcode TruncOpcode = GenericOpcode::G_TRUNC) { return widenScalarDst(Instruction, WideType, OperandIndex, TruncOpcode); }; - const auto apply = [](Expected<void> Result) -> Expected<void> { + const auto Apply = [](Expected<void> Result) -> Expected<void> { if (!Result) return std::unexpected(Result.error()); return {}; @@ -745,9 +864,9 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "atomic RMW value widening has an invalid type index"); - if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -755,28 +874,28 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "compare-exchange widening has an invalid type index"); - if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(3, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; case GenericOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS: if (TypeIndex == 0) { - if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(3, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenSource(4, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(4, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "compare-exchange success widening has an invalid type index"); - if (auto Result = apply(widenDestination(1)); !Result) + if (auto Result = Apply(WidenDestination(1)); !Result) return Result; break; @@ -804,11 +923,17 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size return std::unexpected(Extended.error()); if (auto Replaced = SourceOperand->setIntegerImmediate(std::move(*Extended)); !Replaced) return std::unexpected(Replaced.error()); - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } + case GenericOpcode::G_SADDO: + case GenericOpcode::G_SSUBO: + case GenericOpcode::G_UADDO: + case GenericOpcode::G_USUBO: + return widenScalarAddSubOverflow(Instruction, TypeIndex, WideType); + case GenericOpcode::G_ADD: case GenericOpcode::G_SUB: case GenericOpcode::G_MUL: @@ -818,11 +943,11 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "binary operation widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -834,11 +959,11 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "signed operation widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_SEXT)); !Result) return Result; - if (auto Result = apply(widenSource(2, GenericOpcode::G_SEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_SEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -850,11 +975,11 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "unsigned operation widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ZEXT)); !Result) return Result; - if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ZEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -867,16 +992,16 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size ExtensionOpcode = GenericOpcode::G_ZEXT; else if (Instruction.opcode() == opcode(GenericOpcode::G_ASHR)) ExtensionOpcode = GenericOpcode::G_SEXT; - if (auto Result = apply(widenSource(1, ExtensionOpcode)); !Result) + if (auto Result = Apply(WidenSource(1, ExtensionOpcode)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "shift widening has an invalid type index"); - if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ZEXT)); !Result) return Result; break; @@ -884,7 +1009,7 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size case GenericOpcode::G_ROTR: if (TypeIndex != 1) return makeUnexpected(ErrorCode::Unsupported, "rotate value widening is not defined"); - if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ZEXT)); !Result) return Result; break; @@ -893,9 +1018,9 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "unary operation widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -903,15 +1028,15 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "absolute-value widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_SEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; case GenericOpcode::G_ICMP: if (TypeIndex == 0) { - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } @@ -952,27 +1077,27 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size IsSigned || Info.isSExtCheaperThanZExt(Query->Types[TypeIndex], WideType) ? GenericOpcode::G_SEXT : GenericOpcode::G_ZEXT; - if (auto Result = apply(widenSource(2, ExtensionOpcode)); !Result) + if (auto Result = Apply(WidenSource(2, ExtensionOpcode)); !Result) return Result; - if (auto Result = apply(widenSource(3, ExtensionOpcode)); !Result) + if (auto Result = Apply(WidenSource(3, ExtensionOpcode)); !Result) return Result; } break; case GenericOpcode::G_SELECT: if (TypeIndex == 0) { - if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(3, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "select widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ZEXT)); !Result) return Result; break; @@ -980,7 +1105,7 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 1) return makeUnexpected(ErrorCode::Unsupported, "floating-point extension destination widening is not defined"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_FPEXT)); !Result) return Result; break; @@ -990,28 +1115,28 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size case GenericOpcode::G_INTRINSIC_LLRINT: case GenericOpcode::G_IS_FPCLASS: if (TypeIndex == 0) { - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "floating-to-integer widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_FPEXT)); !Result) return Result; break; case GenericOpcode::G_SITOFP: case GenericOpcode::G_UITOFP: if (TypeIndex == 0) { - if (auto Result = apply(widenDestination(0, GenericOpcode::G_FPTRUNC)); !Result) + if (auto Result = Apply(WidenDestination(0, GenericOpcode::G_FPTRUNC)); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "integer-to-floating widening has an invalid type index"); - if (auto Result = apply(widenSource(1, Instruction.opcode() == opcode(GenericOpcode::G_SITOFP) + if (auto Result = Apply(WidenSource(1, Instruction.opcode() == opcode(GenericOpcode::G_SITOFP) ? GenericOpcode::G_SEXT : GenericOpcode::G_ZEXT)); !Result) @@ -1275,15 +1400,19 @@ Expected<void> LegalizerHelper::lowerVAArg(MachineInstr &Instruction) { auto DestinationInfo = MRI.virtualRegisterInfo(*Destination); auto PointerInfo = MRI.virtualRegisterInfo(*ListPointer); auto RequestedAlignment = signedImmediate(*AlignmentOperand); - if (!DestinationInfo || !PointerInfo || !DestinationInfo->get().Type || - !PointerInfo->get().Type || !RequestedAlignment || *RequestedAlignment <= 0 || + if (!DestinationInfo || !PointerInfo) + return makeUnexpected(ErrorCode::VerificationError, "G_VAARG has invalid register information"); + const std::optional<LowLevelType> &DestinationTypeInfo = DestinationInfo->get().Type; + const std::optional<LowLevelType> &PointerTypeInfo = PointerInfo->get().Type; + if (!DestinationTypeInfo.has_value() || !PointerTypeInfo.has_value() || !RequestedAlignment || + *RequestedAlignment <= 0 || !std::has_single_bit(static_cast<std::uint64_t>(*RequestedAlignment))) { return makeUnexpected(ErrorCode::VerificationError, "G_VAARG has invalid type or alignment information"); } - const LowLevelType DestinationType = *DestinationInfo->get().Type; - const LowLevelType PointerType = *PointerInfo->get().Type; + const LowLevelType DestinationType = DestinationTypeInfo.value(); + const LowLevelType PointerType = PointerTypeInfo.value(); const auto DestinationLayout = scalarLayout(DestinationType); const auto PointerLayout = scalarLayout(PointerType); if (!DestinationLayout || !PointerLayout || !PointerType.isPointer()) { @@ -1415,6 +1544,9 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, return lowerAbsDiffToMinMax(Instruction); return lowerAbsDiffToSelect(Instruction); } + case GenericOpcode::G_SADDO: + case GenericOpcode::G_SSUBO: + return lowerSignedAddSubOverflow(Instruction); case GenericOpcode::G_SEXT_INREG: { const Register Destination = *Instruction.operandAt(0)->getIf<Register>(); const Register Source = *Instruction.operandAt(1)->getIf<Register>(); @@ -1425,18 +1557,16 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, if (!Type) return std::unexpected(Type.error()); - auto ShiftAmount = MRI.createVirtualRegister(*Type); auto Temporary = MRI.createVirtualRegister(*Type); - if (!ShiftAmount) - return std::unexpected(ShiftAmount.error()); if (!Temporary) return std::unexpected(Temporary.error()); if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) return std::unexpected(Point.error()); const std::int64_t Shift = static_cast<std::int64_t>(Type->scalarBitWidth()) - *SizeInBits; - if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, Shift); !Built) - return std::unexpected(Built.error()); + auto ShiftAmount = buildConstantRegister(MIRBuilder, *Type, Shift); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); if (auto Built = MIRBuilder.buildShl(*Temporary, Source, *ShiftAmount); !Built) return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildAShr(Destination, *Temporary, *ShiftAmount); !Built) @@ -1490,7 +1620,6 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, auto TemporaryResult = MRI.createVirtualRegister(*ResultType); auto Carry = MRI.createVirtualRegister(*ConditionType); auto ExtendedCarryIn = MRI.createVirtualRegister(*ResultType); - auto Zero = MRI.createVirtualRegister(*ResultType); auto ResultIsZero = MRI.createVirtualRegister(*ConditionType); auto SecondCarry = MRI.createVirtualRegister(*ConditionType); if (!NewResult) @@ -1501,8 +1630,6 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, return std::unexpected(Carry.error()); if (!ExtendedCarryIn) return std::unexpected(ExtendedCarryIn.error()); - if (!Zero) - return std::unexpected(Zero.error()); if (!ResultIsZero) return std::unexpected(ResultIsZero.error()); if (!SecondCarry) @@ -1519,8 +1646,9 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildAdd(*NewResult, *TemporaryResult, *ExtendedCarryIn); !Built) return std::unexpected(Built.error()); - if (auto Built = MIRBuilder.buildConstant(*Zero, 0); !Built) - return std::unexpected(Built.error()); + auto Zero = buildConstantRegister(MIRBuilder, *ResultType, 0); + if (!Zero) + return std::unexpected(Zero.error()); if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::Equal, *ResultIsZero, *NewResult, *Zero); !Built) @@ -1569,7 +1697,6 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, auto TemporaryResult = MRI.createVirtualRegister(*ResultType); auto Borrow = MRI.createVirtualRegister(*ConditionType); auto ExtendedBorrowIn = MRI.createVirtualRegister(*ResultType); - auto Zero = MRI.createVirtualRegister(*ResultType); auto TemporaryResultIsZero = MRI.createVirtualRegister(*ConditionType); auto SecondBorrow = MRI.createVirtualRegister(*ConditionType); if (!TemporaryResult) @@ -1578,8 +1705,6 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, return std::unexpected(Borrow.error()); if (!ExtendedBorrowIn) return std::unexpected(ExtendedBorrowIn.error()); - if (!Zero) - return std::unexpected(Zero.error()); if (!TemporaryResultIsZero) return std::unexpected(TemporaryResultIsZero.error()); if (!SecondBorrow) @@ -1596,8 +1721,9 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildSub(Result, *TemporaryResult, *ExtendedBorrowIn); !Built) return std::unexpected(Built.error()); - if (auto Built = MIRBuilder.buildConstant(*Zero, 0); !Built) - return std::unexpected(Built.error()); + auto Zero = buildConstantRegister(MIRBuilder, *ResultType, 0); + if (!Zero) + return std::unexpected(Zero.error()); if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::Equal, *TemporaryResultIsZero, *TemporaryResult, *Zero); !Built) @@ -1630,11 +1756,8 @@ Expected<void> LegalizerHelper::lowerAbsToAddXor(MachineInstr &Instruction) { if (!Type) return std::unexpected(Type.error()); - auto ShiftAmount = MRI.createVirtualRegister(*Type); auto Shift = MRI.createVirtualRegister(*Type); auto Add = MRI.createVirtualRegister(*Type); - if (!ShiftAmount) - return std::unexpected(ShiftAmount.error()); if (!Shift) return std::unexpected(Shift.error()); if (!Add) @@ -1642,8 +1765,10 @@ Expected<void> LegalizerHelper::lowerAbsToAddXor(MachineInstr &Instruction) { if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) return std::unexpected(Point.error()); - if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, Type->scalarBitWidth() - 1U); !Built) - return std::unexpected(Built.error()); + auto ShiftAmount = buildConstantRegister(MIRBuilder, *Type, + static_cast<std::int64_t>(Type->scalarBitWidth() - 1U)); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); if (auto Built = MIRBuilder.buildAShr(*Shift, Source, *ShiftAmount); !Built) return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildAdd(*Add, Source, *Shift); !Built) @@ -1736,6 +1861,76 @@ Expected<void> LegalizerHelper::lowerAbsDiffToMinMax(MachineInstr &Instruction) return Block->removeInstruction(Instruction); } +Expected<void> LegalizerHelper::lowerSignedAddSubOverflow(MachineInstr &Instruction) { + const bool IsAdd = Instruction.opcode() == opcode(GenericOpcode::G_SADDO); + const Register Destination = *Instruction.operandAt(0)->getIf<Register>(); + const Register Overflow = *Instruction.operandAt(1)->getIf<Register>(); + const Register Left = *Instruction.operandAt(2)->getIf<Register>(); + const Register Right = *Instruction.operandAt(3)->getIf<Register>(); + auto Type = MRI.getType(Destination); + auto BooleanType = MRI.getType(Overflow); + if (!Type) + return std::unexpected(Type.error()); + if (!BooleanType) + return std::unexpected(BooleanType.error()); + + auto Result = MRI.cloneVirtualRegister(Destination); + auto FirstComparison = MRI.createVirtualRegister(*BooleanType); + auto SecondComparison = MRI.createVirtualRegister(*BooleanType); + if (!Result) + return std::unexpected(Result.error()); + if (!FirstComparison) + return std::unexpected(FirstComparison.error()); + if (!SecondComparison) + return std::unexpected(SecondComparison.error()); + + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = IsAdd ? MIRBuilder.buildAdd(*Result, Left, Right) + : MIRBuilder.buildSub(*Result, Left, Right); + !Built) { + return std::unexpected(Built.error()); + } + auto Zero = buildConstantRegister(MIRBuilder, *Type, 0); + if (!Zero) + return std::unexpected(Zero.error()); + if (IsAdd) { + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *FirstComparison, *Result, Left); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *SecondComparison, Right, *Zero); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildXor(Overflow, *SecondComparison, *FirstComparison); !Built) + return std::unexpected(Built.error()); + } else { + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *FirstComparison, Left, Right); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *SecondComparison, + *Result, *Zero); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildXor(Overflow, *FirstComparison, *SecondComparison); !Built) + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildCopy(Destination, *Result); !Built) + return std::unexpected(Built.error()); + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "signed add/sub overflow instruction became detached during lowering"); + return Block->removeInstruction(Instruction); +} + Expected<void> LegalizerHelper::legalize(MachineInstr &Instruction, const LegalizationDecision &Decision) { if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp index c4cf946..ee7f856 100644 --- a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp +++ b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp @@ -295,7 +295,7 @@ LegalizeRuleSet &LegalizeRuleSet::clampScalar(std::size_t TypeIndex, LowLevelTyp LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex, std::size_t ReferenceTypeIndex) { - const auto changeToReference = [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) { + const auto ChangeToReference = [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) { return std::pair{TypeIndex, scalarType(Query.Types[ReferenceTypeIndex].scalarBitWidth())}; }; widenScalarIf( @@ -306,7 +306,7 @@ LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex, Query.Types[TypeIndex].scalarBitWidth() < Query.Types[ReferenceTypeIndex].scalarBitWidth(); }, - changeToReference); + ChangeToReference); return narrowScalarIf( [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) { return TypeIndex < Query.Types.size() && ReferenceTypeIndex < Query.Types.size() && @@ -315,7 +315,7 @@ LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex, Query.Types[TypeIndex].scalarBitWidth() > Query.Types[ReferenceTypeIndex].scalarBitWidth(); }, - changeToReference); + ChangeToReference); } LegalizeRuleSet &LegalizeRuleSet::lowerIfMemSizeNotByteSizePow2(std::size_t MemoryIndex) { @@ -327,6 +327,10 @@ LegalizeRuleSet &LegalizeRuleSet::lowerIfMemSizeNotByteSizePow2(std::size_t Memo }); } +LegalizeRuleSet &LegalizeRuleSet::custom() { + return customIf([](const LegalizationQuery &) { return true; }); +} + LegalizeRuleSet &LegalizeRuleSet::alwaysLegal() { return legalIf([](const LegalizationQuery &) { return true; }); } @@ -401,13 +405,15 @@ Expected<LegalizationQuery> LegalizerInfo::buildQuery(const MachineInstr &Instru auto Info = Function.registerInfo().virtualRegisterInfo(*Reg); if (!Info) return std::unexpected(Info.error()); - if (!Info->get().Type) + const std::optional<LowLevelType> &RegisterType = Info->get().Type; + if (!RegisterType.has_value()) return makeUnexpected(ErrorCode::VerificationError, "legalization type operand has no LowLevelType"); - if (OptionalTypes[TypeIndex] && *OptionalTypes[TypeIndex] != *Info->get().Type) + std::optional<LowLevelType> &ExistingType = OptionalTypes[TypeIndex]; + if (ExistingType.has_value() && ExistingType.value() != RegisterType.value()) return makeUnexpected(ErrorCode::VerificationError, "legalization type operands disagree within one type index"); - OptionalTypes[TypeIndex] = *Info->get().Type; + ExistingType = RegisterType.value(); TypeOperands[TypeIndex].push_back(Index); } diff --git a/backend/lib/CodeGen/MachineIRBuilder.cpp b/backend/lib/CodeGen/MachineIRBuilder.cpp index e3ac0bf..36f697b 100644 --- a/backend/lib/CodeGen/MachineIRBuilder.cpp +++ b/backend/lib/CodeGen/MachineIRBuilder.cpp @@ -11,6 +11,8 @@ #include "rcc/CodeGen/MachineRegisterInfo.h" #include <algorithm> +#include <array> +#include <cassert> #include <cstddef> #include <cstdint> #include <memory> @@ -21,6 +23,34 @@ namespace rcc { +Register MachineIRBuilderResult::reg() const noexcept { + assert(ResultKind == Kind::Register && "machine IR builder result is not a register"); + return Reg; +} + +LowLevelType MachineIRBuilderResult::type() const noexcept { + assert(ResultKind == Kind::Type && "machine IR builder result is not a type"); + return Type; +} + +Expected<LowLevelType> MachineIRBuilderResult::type(const MachineRegisterInfo &MRI) const { + if (ResultKind == Kind::Type) + return Type; + return MRI.getType(Reg); +} + +Expected<void> MachineIRBuilderResult::addDef(MachineRegisterInfo &MRI, + MachineInstrBuilder &Builder) const { + Register Definition = Reg; + if (ResultKind == Kind::Type) { + auto Created = MRI.createVirtualRegister(Type); + if (!Created) + return std::unexpected(Created.error()); + Definition = *Created; + } + return Builder.addDef(Definition); +} + MachineInstrBuilder::MachineInstrBuilder(MachineFunction &Function, const TargetDescription &Target, const InstructionDescriptor &Descriptor, MachineBasicBlock &InsertBlock, @@ -709,13 +739,24 @@ Expected<MachineInstrBuilder> MachineIRBuilder::buildInstr(Opcode InstructionOpc } Expected<MachineInstr *> -MachineIRBuilder::buildInstr(Opcode InstructionOpcode, std::initializer_list<Register> Destinations, +MachineIRBuilder::buildInstr(Opcode InstructionOpcode, + std::initializer_list<MachineIRBuilderResult> Destinations, std::initializer_list<Register> Sources) const { + return buildInstr( + InstructionOpcode, + std::span<const MachineIRBuilderResult>(Destinations.begin(), Destinations.size()), + std::span<const Register>(Sources.begin(), Sources.size())); +} + +Expected<MachineInstr *> +MachineIRBuilder::buildInstr(Opcode InstructionOpcode, + std::span<const MachineIRBuilderResult> Destinations, + std::span<const Register> Sources) const { auto Pending = buildInstr(InstructionOpcode); if (!Pending) return std::unexpected(Pending.error()); - for (Register Destination : Destinations) { - if (auto Added = Pending->addDef(Destination); !Added) + for (const MachineIRBuilderResult &Destination : Destinations) { + if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added) return std::unexpected(Added.error()); } for (Register Source : Sources) { @@ -732,77 +773,72 @@ Expected<LowLevelType> MachineIRBuilder::registerType(Register Reg) const { auto Info = Function->registerInfo().virtualRegisterInfo(Reg); if (!Info) return std::unexpected(Info.error()); - if (!Info->get().Type) + const std::optional<LowLevelType> &Type = Info->get().Type; + if (!Type.has_value()) return makeUnexpected(ErrorCode::InvalidArgument, "generic builder operand has no LowLevelType"); - return *Info->get().Type; + return Type.value(); } Expected<MachineInstr *> MachineIRBuilder::buildUnary(Opcode InstructionOpcode, - Register Destination, Register Source) const { - auto Pending = buildInstr(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(); + MachineIRBuilderResult Destination, + Register Source) const { + const std::array Destinations{Destination}; + const std::array Sources{Source}; + return buildInstr(InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations), + std::span<const Register>(Sources)); } Expected<MachineInstr *> MachineIRBuilder::buildBinary(Opcode InstructionOpcode, - Register Destination, Register Left, - Register Right) const { - auto Pending = buildInstr(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(Left); !Added) - return std::unexpected(Added.error()); - if (auto Added = Pending->addUse(Right); !Added) - return std::unexpected(Added.error()); - return Pending->build(); + MachineIRBuilderResult Destination, + Register Left, Register Right) const { + const std::array Destinations{Destination}; + const std::array Sources{Left, Right}; + return buildInstr(InstructionOpcode, std::span<const MachineIRBuilderResult>(Destinations), + std::span<const Register>(Sources)); } -Expected<MachineInstr *> MachineIRBuilder::buildTrunc(Register Destination, Register Source) const { +Expected<MachineInstr *> MachineIRBuilder::buildTrunc(MachineIRBuilderResult Destination, + Register Source) const { return buildUnary(opcode(GenericOpcode::G_TRUNC), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildCopy(Register Destination, Register Source) const { +Expected<MachineInstr *> MachineIRBuilder::buildCopy(MachineIRBuilderResult Destination, + Register Source) const { return buildUnary(opcode(GenericOpcode::COPY), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildImplicitDef(Register Destination) const { - auto Pending = buildInstr(opcode(GenericOpcode::G_IMPLICIT_DEF)); - if (!Pending) - return std::unexpected(Pending.error()); - if (auto Added = Pending->addDef(Destination); !Added) - return std::unexpected(Added.error()); - return Pending->build(); +Expected<MachineInstr *> +MachineIRBuilder::buildImplicitDef(MachineIRBuilderResult Destination) const { + const std::array Destinations{Destination}; + return buildInstr(opcode(GenericOpcode::G_IMPLICIT_DEF), + std::span<const MachineIRBuilderResult>(Destinations), + std::span<const Register>()); } -Expected<MachineInstr *> MachineIRBuilder::buildAnyExt(Register Destination, +Expected<MachineInstr *> MachineIRBuilder::buildAnyExt(MachineIRBuilderResult Destination, Register Source) const { return buildUnary(opcode(GenericOpcode::G_ANYEXT), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildZExt(Register Destination, Register Source) const { +Expected<MachineInstr *> MachineIRBuilder::buildZExt(MachineIRBuilderResult Destination, + Register Source) const { return buildUnary(opcode(GenericOpcode::G_ZEXT), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildSExt(Register Destination, Register Source) const { +Expected<MachineInstr *> MachineIRBuilder::buildSExt(MachineIRBuilderResult Destination, + Register Source) const { return buildUnary(opcode(GenericOpcode::G_SEXT), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildUndef(Register Destination) const { +Expected<MachineInstr *> MachineIRBuilder::buildUndef(MachineIRBuilderResult Destination) const { return buildImplicitDef(Destination); } Expected<MachineInstr *> MachineIRBuilder::buildExtOrTrunc(Opcode ExtensionOpcode, - Register Destination, + MachineIRBuilderResult Destination, Register Source) const { - auto DestinationType = registerType(Destination); + auto DestinationType = Destination.type(Function->registerInfo()); if (!DestinationType) return std::unexpected(DestinationType.error()); auto SourceType = registerType(Source); @@ -817,30 +853,31 @@ Expected<MachineInstr *> MachineIRBuilder::buildExtOrTrunc(Opcode ExtensionOpcod return buildUnary(opcode(GenericOpcode::COPY), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildAnyExtOrTrunc(Register Destination, +Expected<MachineInstr *> MachineIRBuilder::buildAnyExtOrTrunc(MachineIRBuilderResult Destination, Register Source) const { return buildExtOrTrunc(opcode(GenericOpcode::G_ANYEXT), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildSExtOrTrunc(Register Destination, +Expected<MachineInstr *> MachineIRBuilder::buildSExtOrTrunc(MachineIRBuilderResult Destination, Register Source) const { return buildExtOrTrunc(opcode(GenericOpcode::G_SEXT), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination, APInt Value) const { +Expected<MachineInstr *> MachineIRBuilder::buildConstant(MachineIRBuilderResult Destination, + APInt Value) const { auto Pending = buildInstr(opcode(GenericOpcode::G_CONSTANT)); if (!Pending) return std::unexpected(Pending.error()); - if (auto Added = Pending->addDef(Destination); !Added) + if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added) return std::unexpected(Added.error()); if (auto Added = Pending->addIntegerImmediate(std::move(Value)); !Added) return std::unexpected(Added.error()); return Pending->build(); } -Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination, +Expected<MachineInstr *> MachineIRBuilder::buildConstant(MachineIRBuilderResult Destination, std::int64_t Value) const { - auto Type = registerType(Destination); + auto Type = Destination.type(Function->registerInfo()); if (!Type) return std::unexpected(Type.error()); auto Immediate = APInt::fromSigned(Type->scalarBitWidth(), Value); @@ -849,12 +886,13 @@ Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination, return buildConstant(Destination, std::move(*Immediate)); } -Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(Register Destination, Register Source, +Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(MachineIRBuilderResult Destination, + Register Source, std::uint32_t Width) const { auto Pending = buildInstr(opcode(GenericOpcode::G_SEXT_INREG)); if (!Pending) return std::unexpected(Pending.error()); - if (auto Added = Pending->addDef(Destination); !Added) + if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added) return std::unexpected(Added.error()); if (auto Added = Pending->addUse(Source); !Added) return std::unexpected(Added.error()); @@ -863,63 +901,63 @@ Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(Register Destination, return Pending->build(); } -Expected<MachineInstr *> MachineIRBuilder::buildAnd(Register Destination, Register Left, - Register Right) const { +Expected<MachineInstr *> MachineIRBuilder::buildAnd(MachineIRBuilderResult Destination, + Register Left, Register Right) const { return buildBinary(opcode(GenericOpcode::G_AND), Destination, Left, Right); } -Expected<MachineInstr *> MachineIRBuilder::buildOr(Register Destination, Register Left, - Register Right) const { +Expected<MachineInstr *> MachineIRBuilder::buildOr(MachineIRBuilderResult Destination, + Register Left, Register Right) const { return buildBinary(opcode(GenericOpcode::G_OR), Destination, Left, Right); } -Expected<MachineInstr *> MachineIRBuilder::buildXor(Register Destination, Register Left, - Register Right) const { +Expected<MachineInstr *> MachineIRBuilder::buildXor(MachineIRBuilderResult Destination, + Register Left, Register Right) const { return buildBinary(opcode(GenericOpcode::G_XOR), Destination, Left, Right); } -Expected<MachineInstr *> MachineIRBuilder::buildAdd(Register Destination, Register Left, - Register Right) const { +Expected<MachineInstr *> MachineIRBuilder::buildAdd(MachineIRBuilderResult Destination, + Register Left, Register Right) const { return buildBinary(opcode(GenericOpcode::G_ADD), Destination, Left, Right); } -Expected<MachineInstr *> MachineIRBuilder::buildSub(Register Destination, Register Left, - Register Right) const { +Expected<MachineInstr *> MachineIRBuilder::buildSub(MachineIRBuilderResult Destination, + Register Left, Register Right) const { return buildBinary(opcode(GenericOpcode::G_SUB), Destination, Left, Right); } -Expected<MachineInstr *> MachineIRBuilder::buildShl(Register Destination, Register Left, - Register Right) const { +Expected<MachineInstr *> MachineIRBuilder::buildShl(MachineIRBuilderResult Destination, + Register Left, Register Right) const { return buildBinary(opcode(GenericOpcode::G_SHL), Destination, Left, Right); } -Expected<MachineInstr *> MachineIRBuilder::buildLShr(Register Destination, Register Left, - Register Right) const { +Expected<MachineInstr *> MachineIRBuilder::buildLShr(MachineIRBuilderResult Destination, + Register Left, Register Right) const { return buildBinary(opcode(GenericOpcode::G_LSHR), Destination, Left, Right); } -Expected<MachineInstr *> MachineIRBuilder::buildAShr(Register Destination, Register Left, - Register Right) const { +Expected<MachineInstr *> MachineIRBuilder::buildAShr(MachineIRBuilderResult Destination, + Register Left, Register Right) const { return buildBinary(opcode(GenericOpcode::G_ASHR), Destination, Left, Right); } -Expected<MachineInstr *> MachineIRBuilder::buildPtrToInt(Register Destination, +Expected<MachineInstr *> MachineIRBuilder::buildPtrToInt(MachineIRBuilderResult Destination, Register Source) const { return buildUnary(opcode(GenericOpcode::G_PTRTOINT), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildIntToPtr(Register Destination, +Expected<MachineInstr *> MachineIRBuilder::buildIntToPtr(MachineIRBuilderResult Destination, Register Source) const { return buildUnary(opcode(GenericOpcode::G_INTTOPTR), Destination, Source); } Expected<MachineInstr *> MachineIRBuilder::buildICmp(IntegerPredicate Predicate, - Register Destination, Register Left, - Register Right) const { + MachineIRBuilderResult Destination, + Register Left, Register Right) const { auto Pending = buildInstr(opcode(GenericOpcode::G_ICMP)); if (!Pending) return std::unexpected(Pending.error()); - if (auto Added = Pending->addDef(Destination); !Added) + if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added) return std::unexpected(Added.error()); if (auto Added = Pending->addIntegerPredicate(Predicate); !Added) return std::unexpected(Added.error()); @@ -931,9 +969,9 @@ Expected<MachineInstr *> MachineIRBuilder::buildICmp(IntegerPredicate Predicate, } Expected<MachineInstr *> -MachineIRBuilder::buildMergeLikeInstr(Register Destination, +MachineIRBuilder::buildMergeLikeInstr(MachineIRBuilderResult Destination, const std::vector<Register> &Sources) const { - auto DestinationType = registerType(Destination); + auto DestinationType = Destination.type(Function->registerInfo()); if (!DestinationType) return std::unexpected(DestinationType.error()); if (!DestinationType->isVector()) @@ -946,49 +984,33 @@ MachineIRBuilder::buildMergeLikeInstr(Register Destination, return std::unexpected(SourceType.error()); const GenericOpcode MergeOpcode = SourceType->isVector() ? GenericOpcode::G_CONCAT_VECTORS : GenericOpcode::G_BUILD_VECTOR; - auto Pending = buildInstr(opcode(MergeOpcode)); - 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(); + const std::array Destinations{Destination}; + return buildInstr(opcode(MergeOpcode), std::span<const MachineIRBuilderResult>(Destinations), + Sources); } Expected<MachineInstr *> -MachineIRBuilder::buildMergeValues(Register Destination, +MachineIRBuilder::buildMergeValues(MachineIRBuilderResult Destination, const std::vector<Register> &Sources) const { - auto Pending = buildInstr(opcode(GenericOpcode::G_MERGE_VALUES)); - 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(); + const std::array Destinations{Destination}; + return buildInstr(opcode(GenericOpcode::G_MERGE_VALUES), + std::span<const MachineIRBuilderResult>(Destinations), Sources); } Expected<MachineInstr *> MachineIRBuilder::buildUnmergeValues(const std::vector<Register> &Destinations, Register Source) const { - auto Pending = buildInstr(opcode(GenericOpcode::G_UNMERGE_VALUES)); - if (!Pending) - return std::unexpected(Pending.error()); - for (Register Destination : Destinations) { - 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(); + std::vector<MachineIRBuilderResult> Results; + Results.reserve(Destinations.size()); + for (Register Destination : Destinations) + Results.emplace_back(Destination); + const std::array Sources{Source}; + return buildInstr(opcode(GenericOpcode::G_UNMERGE_VALUES), Results, + std::span<const Register>(Sources)); } -Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination, Register Source, +Expected<MachineInstr *> MachineIRBuilder::buildExtract(MachineIRBuilderResult Destination, + Register Source, std::uint64_t Offset) const { if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) return makeUnexpected(ErrorCode::InvalidArgument, @@ -996,7 +1018,7 @@ Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination, Re auto Pending = buildInstr(opcode(GenericOpcode::G_EXTRACT)); if (!Pending) return std::unexpected(Pending.error()); - if (auto Added = Pending->addDef(Destination); !Added) + if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added) return std::unexpected(Added.error()); if (auto Added = Pending->addUse(Source); !Added) return std::unexpected(Added.error()); @@ -1005,8 +1027,8 @@ Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination, Re return Pending->build(); } -Expected<MachineInstr *> MachineIRBuilder::buildInsert(Register Destination, Register Source, - Register Inserted, +Expected<MachineInstr *> MachineIRBuilder::buildInsert(MachineIRBuilderResult Destination, + Register Source, Register Inserted, std::uint64_t Offset) const { if (Offset > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) return makeUnexpected(ErrorCode::InvalidArgument, @@ -1014,7 +1036,7 @@ Expected<MachineInstr *> MachineIRBuilder::buildInsert(Register Destination, Reg auto Pending = buildInstr(opcode(GenericOpcode::G_INSERT)); if (!Pending) return std::unexpected(Pending.error()); - if (auto Added = Pending->addDef(Destination); !Added) + if (auto Added = Destination.addDef(Function->registerInfo(), *Pending); !Added) return std::unexpected(Added.error()); if (auto Added = Pending->addUse(Source); !Added) return std::unexpected(Added.error()); diff --git a/backend/lib/Target/RISCV/RISCVPipeline.cpp b/backend/lib/Target/RISCV/RISCVPipeline.cpp index 9ce9f92..62b77f0 100644 --- a/backend/lib/Target/RISCV/RISCVPipeline.cpp +++ b/backend/lib/Target/RISCV/RISCVPipeline.cpp @@ -33,12 +33,13 @@ template <typename PassT, typename... ArgumentT> } [[nodiscard]] Expected<void> addInitialPipeline(MachineFunctionPassManager &Pipeline, - const RISCVSubtarget &Subtarget) { + const RISCVSubtarget &Subtarget, + RISCVPipelineOptions Options) { auto Added = addPass<MachineCombinerPass>(Pipeline, machineCombinerInfo(), MachineCombinerStage::PreLegalizer); if (!Added) return std::unexpected(Added.error()); - Added = addPass<Legalizer>(Pipeline, Subtarget.getLegalizerInfo()); + Added = addPass<Legalizer>(Pipeline, Subtarget.getLegalizerInfo(), Options.Optimization); if (!Added) return std::unexpected(Added.error()); Added = addPass<RegBankSelect>(Pipeline, Subtarget.getRegBankInfo()); @@ -67,7 +68,7 @@ template <typename PassT, typename... ArgumentT> [[nodiscard]] Expected<void> addCompleteRegistry(MachineFunctionPassManager &Pipeline, const RISCVSubtarget &Subtarget, RISCVPipelineOptions Options) { - auto Added = addInitialPipeline(Pipeline, Subtarget); + auto Added = addInitialPipeline(Pipeline, Subtarget, Options); if (!Added) return std::unexpected(Added.error()); Added = addSSAExitPipeline(Pipeline); @@ -92,7 +93,7 @@ Expected<void> addCanonicalPipeline(MachineFunctionPassManager &Pipeline, MachineCombinerStage::PreLegalizer); if (!Added) return std::unexpected(Added.error()); - Added = addPass<Legalizer>(Pipeline, Subtarget.getLegalizerInfo()); + Added = addPass<Legalizer>(Pipeline, Subtarget.getLegalizerInfo(), Options.Optimization); if (!Added) return std::unexpected(Added.error()); } diff --git a/backend/lib/Tooling/PipelineDriver.cpp b/backend/lib/Tooling/PipelineDriver.cpp index 542e2b5..7f252a6 100644 --- a/backend/lib/Tooling/PipelineDriver.cpp +++ b/backend/lib/Tooling/PipelineDriver.cpp @@ -100,9 +100,10 @@ createPasses(const MachineFunction &Function, const BackendInvocation &Invocatio const riscv::RISCVSubtarget &Subtarget, MachinePassManagerOptions Options) { MachineFunctionPassManager Pipeline(Options); if (Invocation.PassPipeline.size() == 1 && Invocation.PassPipeline.front() == "default") { - auto Added = - riscv::addCanonicalPipeline(Pipeline, Function, Subtarget, - riscv::RISCVPipelineOptions{.UseTargetCopyInstructions = true}); + auto Added = riscv::addCanonicalPipeline( + Pipeline, Function, Subtarget, + riscv::RISCVPipelineOptions{.Optimization = Invocation.Optimization, + .UseTargetCopyInstructions = true}); if (!Added) return std::unexpected(Added.error()); } else { @@ -117,7 +118,8 @@ createPasses(const MachineFunction &Function, const BackendInvocation &Invocatio for (const std::string &Name : Invocation.PassPipeline) { auto Pass = riscv::createCanonicalPipelinePass( Name, Subtarget, - riscv::RISCVPipelineOptions{.UseTargetCopyInstructions = UseTargetCopyInstructions}); + riscv::RISCVPipelineOptions{.Optimization = Invocation.Optimization, + .UseTargetCopyInstructions = UseTargetCopyInstructions}); if (!Pass) return std::unexpected(Pass.error()); auto Added = Pipeline.addPass(std::move(*Pass)); diff --git a/backend/unittests/CodeGen/GlobalISel/InstructionSelectTest.cpp b/backend/unittests/CodeGen/GlobalISel/InstructionSelectTest.cpp index 6d9fa3c..9f3f0b5 100644 --- a/backend/unittests/CodeGen/GlobalISel/InstructionSelectTest.cpp +++ b/backend/unittests/CodeGen/GlobalISel/InstructionSelectTest.cpp @@ -121,9 +121,11 @@ void testPipeline(TestContext &Context) { rcc::MachineFunctionProperty::TracksLiveness}; const rcc::riscv::RISCVSubtarget Subtarget(rcc::riscv::RISCVSubtargetFeatures::rv64gc()); rcc::MachineFunctionPassManager Pipeline; - Context.expect( - Pipeline.addPass(std::make_unique<rcc::Legalizer>(Subtarget.getLegalizerInfo())).has_value(), - "legalizer must be accepted by the pass manager"); + Context.expect(Pipeline + .addPass(std::make_unique<rcc::Legalizer>(Subtarget.getLegalizerInfo(), + rcc::OptimizationLevel::O2)) + .has_value(), + "legalizer must be accepted by the pass manager"); Context.expect(Pipeline.addPass(std::make_unique<rcc::RegBankSelect>(Subtarget.getRegBankInfo())) .has_value(), "register-bank selector must be accepted by the pass manager"); @@ -327,7 +329,8 @@ void testExtendedRV64GCPipeline(TestContext &Context) { rcc::MachineFunctionProperty::TracksLiveness}; const rcc::riscv::RISCVSubtarget Subtarget(rcc::riscv::RISCVSubtargetFeatures::rv64gc()); rcc::MachineFunctionPassManager Pipeline; - if (!Pipeline.addPass(std::make_unique<rcc::Legalizer>(Subtarget.getLegalizerInfo())) || + if (!Pipeline.addPass(std::make_unique<rcc::Legalizer>(Subtarget.getLegalizerInfo(), + rcc::OptimizationLevel::O2)) || !Pipeline.addPass(std::make_unique<rcc::RegBankSelect>(Subtarget.getRegBankInfo())) || !Pipeline.addPass( std::make_unique<rcc::InstructionSelect>(Subtarget.getInstructionSelector()))) { diff --git a/backend/unittests/CodeGen/GlobalISel/LegalizerTest.cpp b/backend/unittests/CodeGen/GlobalISel/LegalizerTest.cpp index b191a3f..eaf3741 100644 --- a/backend/unittests/CodeGen/GlobalISel/LegalizerTest.cpp +++ b/backend/unittests/CodeGen/GlobalISel/LegalizerTest.cpp @@ -3,6 +3,9 @@ #include "rcc/CodeGen/GlobalISel/Legalizer.h" #include "GISelMITest.h" +#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/GlobalISel/LegalizerHelper.h" +#include "rcc/Target/RISCV/RISCVRegisters.h" #include "rcc/Target/RISCV/RISCVSubtarget.h" #include "rcc/Target/RISCV/RISCVTarget.h" @@ -14,53 +17,38 @@ namespace { using rcc::test::buildAdd; using rcc::test::createFixture; -using rcc::test::createFloatRegister; using rcc::test::createRegister; using rcc::test::TestContext; -class TogglingLegalizer final : public rcc::LegalizerInfo { -public: - [[nodiscard]] rcc::Expected<rcc::LegalizationAction> - classify(const rcc::MachineInstr &, const rcc::MachineFunction &, - const rcc::TargetDescription &) const override { - return rcc::LegalizationAction::Lower; - } - - [[nodiscard]] rcc::Expected<void> lower(rcc::MachineInstr &Instruction, rcc::MachineFunction &, - const rcc::TargetDescription &, - rcc::LegalizationAction) const override { - const auto Generic = static_cast<rcc::GenericOpcode>(Instruction.opcode().value()); - return Instruction.setOpcode(rcc::opcode(Generic == rcc::GenericOpcode::G_ADD - ? rcc::GenericOpcode::G_SUB - : rcc::GenericOpcode::G_ADD)); - } -}; - class BackwardInvalidatingLegalizer final : public rcc::LegalizerInfo { public: - [[nodiscard]] rcc::Expected<rcc::LegalizationAction> - classify(const rcc::MachineInstr &Instruction, const rcc::MachineFunction &, - const rcc::TargetDescription &) const override { - return Instruction.opcode() == rcc::opcode(rcc::GenericOpcode::G_SUB) - ? rcc::LegalizationAction::Custom - : rcc::LegalizationAction::Legal; + BackwardInvalidatingLegalizer() { + getActionDefinitionsBuilder(rcc::opcode(rcc::GenericOpcode::G_ADD)).alwaysLegal(); + getActionDefinitionsBuilder(rcc::opcode(rcc::GenericOpcode::G_SUB)).custom(); } - [[nodiscard]] rcc::Expected<void> lower(rcc::MachineInstr &Instruction, - rcc::MachineFunction &Function, - const rcc::TargetDescription &, - rcc::LegalizationAction) const override { + [[nodiscard]] rcc::Expected<void> + legalizeCustom(rcc::LegalizerHelper &Helper, rcc::MachineInstr &Instruction, + const rcc::LegalizationDecision &) const override { + rcc::MachineFunction &Function = Helper.MIRBuilder.function(); for (rcc::MachineInstr *Candidate : Function.allInstructions()) { if (Candidate != &Instruction && Candidate->opcode() == rcc::opcode(rcc::GenericOpcode::G_ADD)) { + Helper.Observer.changingInstr(*Candidate); auto Invalidated = Candidate->setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB)); if (!Invalidated) return std::unexpected(Invalidated.error()); + Helper.Observer.changedInstr(*Candidate); break; } } - return Instruction.setOpcode( + Helper.Observer.changingInstr(Instruction); + auto Changed = Instruction.setOpcode( rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADD))); + if (!Changed) + return std::unexpected(Changed.error()); + Helper.Observer.changedInstr(Instruction); + return {}; } }; @@ -72,7 +60,7 @@ void testNullAndMissingContracts(TestContext &Context) { if (!Target || !Fixture.Function) return; - rcc::Legalizer NullPass(nullptr); + rcc::Legalizer NullPass(nullptr, rcc::OptimizationLevel::O2); rcc::MachineFunctionAnalysisManager Analyses; auto NullResult = NullPass.run(*Fixture.Function, *Target, Analyses); Context.expect(!NullResult && NullResult.error().code() == rcc::ErrorCode::InvalidArgument, @@ -81,7 +69,7 @@ void testNullAndMissingContracts(TestContext &Context) { "a rejected pass must not publish function properties"); const rcc::riscv::RISCVSubtarget Subtarget(rcc::riscv::RISCVSubtargetFeatures::rv64gc()); - rcc::Legalizer ValidPass(Subtarget.getLegalizerInfo()); + rcc::Legalizer ValidPass(Subtarget.getLegalizerInfo(), rcc::OptimizationLevel::O2); auto MissingResult = ValidPass.run(*Fixture.Function, *Target, Analyses); Context.expect(!MissingResult && MissingResult.error().code() == rcc::ErrorCode::VerificationError, @@ -97,14 +85,13 @@ void testUnsupportedRollback(TestContext &Context) { "unsupported pipeline fixture must be complete"); if (!Unsupported.Function || Unsupported.Entry == nullptr) return; - const rcc::Register UnsupportedReg = createFloatRegister(Context, *Unsupported.Function); - const rcc::Register UnsupportedSource = createFloatRegister(Context, *Unsupported.Function); + const rcc::Register UnsupportedReg = createRegister(Context, *Unsupported.Function, 64); rcc::MachineIRBuilder UnsupportedBuilder(*Unsupported.Function, *Target); Context.expect(UnsupportedBuilder.setInsertPoint(*Unsupported.Entry).has_value(), "unsupported pipeline insertion point must be valid"); - if (UnsupportedReg.isNoRegister() || UnsupportedSource.isNoRegister()) + if (UnsupportedReg.isNoRegister()) return; - auto Pending = UnsupportedBuilder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_FEXP)); + auto Pending = UnsupportedBuilder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_GET_FPENV)); Context.expect(Pending.has_value(), "unsupported generic instruction must be constructible"); if (!Pending) return; @@ -112,21 +99,22 @@ void testUnsupportedRollback(TestContext &Context) { Context.expect(Built.has_value(), "unsupported generic definition must be accepted"); if (!Built) return; - Context.expect(Pending->addUse(UnsupportedSource).has_value() && Pending->build().has_value(), - "unsupported floating operation must be constructible"); + Context.expect(Pending->build().has_value(), + "unsupported floating-point environment operation must be constructible"); Unsupported.Function->properties() = {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness}; const rcc::riscv::RISCVSubtarget Subtarget(rcc::riscv::RISCVSubtargetFeatures::rv64gc()); rcc::MachineFunctionPassManager OnlyLegalizer; - Context.expect( - OnlyLegalizer.addPass(std::make_unique<rcc::Legalizer>(Subtarget.getLegalizerInfo())) - .has_value(), - "standalone legalizer must be accepted"); + Context.expect(OnlyLegalizer + .addPass(std::make_unique<rcc::Legalizer>(Subtarget.getLegalizerInfo(), + rcc::OptimizationLevel::O2)) + .has_value(), + "standalone legalizer must be accepted"); rcc::MachineFunctionAnalysisManager UnsupportedAnalyses; auto Failure = OnlyLegalizer.run(*Unsupported.Function, *Target, UnsupportedAnalyses); Context.expect(!Failure && Failure.error().code() == rcc::ErrorCode::Unsupported, "unsupported generic instructions must produce a target diagnostic"); - Context.expect(!Failure && Failure.error().message().find("G_FEXP") != std::string::npos, + Context.expect(!Failure && Failure.error().message().find("G_GET_FPENV") != std::string::npos, "unsupported legalization diagnostics must name the rejected opcode"); Context.expect( Unsupported.Function->properties().has(rcc::MachineFunctionProperty::IsSSA) && @@ -134,36 +122,6 @@ void testUnsupportedRollback(TestContext &Context) { "failed legalizer execution must not publish Legalized"); } -void testLegalizerCycleDiagnostic(TestContext &Context) { - auto Target = rcc::riscv::createTargetDescription(); - auto Fixture = createFixture(Context, "pipeline_legalizer_cycle", 6); - Context.expect(Target.has_value() && Fixture.Function != nullptr && Fixture.Entry != nullptr, - "legalizer cycle fixture must be complete"); - if (!Target || !Fixture.Function || Fixture.Entry == nullptr) - return; - const rcc::Register Left = createRegister(Context, *Fixture.Function, 64); - const rcc::Register Right = createRegister(Context, *Fixture.Function, 64); - const rcc::Register Result = createRegister(Context, *Fixture.Function, 64); - rcc::MachineIRBuilder Builder(*Fixture.Function, *Target); - if (Left.isNoRegister() || Right.isNoRegister() || Result.isNoRegister() || - !Builder.setInsertPoint(*Fixture.Entry) || !buildAdd(Context, Builder, Result, Left, Right)) - return; - Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA, - rcc::MachineFunctionProperty::TracksLiveness}; - TogglingLegalizer Legalizer; - rcc::Legalizer StablePass(Legalizer); - rcc::MachineFunctionAnalysisManager Analyses; - auto ResultRun = StablePass.run(*Fixture.Function, *Target, Analyses); - Context.expect(!ResultRun && ResultRun.error().code() == rcc::ErrorCode::InternalError, - "repeated legalization states must report InternalError"); - Context.expect(Fixture.Entry->firstInstruction() != nullptr && - Fixture.Entry->firstInstruction()->opcode() == - rcc::opcode(rcc::GenericOpcode::G_ADD), - "failed legalization preflight must preserve the original instruction"); - Context.expect(!Fixture.Function->properties().has(rcc::MachineFunctionProperty::Legalized), - "a failed legalization cycle must not publish Legalized"); -} - void testLegalizerRevisitsInvalidatedInstructions(TestContext &Context) { auto Target = rcc::riscv::createTargetDescription(); auto Fixture = createFixture(Context, "pipeline_legalizer_revisit", 7); @@ -183,11 +141,20 @@ void testLegalizerRevisitsInvalidatedInstructions(TestContext &Context) { rcc::MachineInstr *Second = First == nullptr ? nullptr : First->next(); if (Second == nullptr || !Second->setOpcode(rcc::opcode(rcc::GenericOpcode::G_SUB))) return; + auto X10 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X10); + auto X11 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X11); + auto FirstCopy = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::COPY)); + auto SecondCopy = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::COPY)); + if (!X10 || !X11 || !FirstCopy || !FirstCopy->addDef(rcc::Register::fromPhysical(*X10)) || + !FirstCopy->addUse(FirstResult) || !FirstCopy->build() || !SecondCopy || + !SecondCopy->addDef(rcc::Register::fromPhysical(*X11)) || !SecondCopy->addUse(SecondResult) || + !SecondCopy->build()) + return; Fixture.Function->properties() = {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness}; BackwardInvalidatingLegalizer Legalizer; - rcc::Legalizer Pass(Legalizer); + rcc::Legalizer Pass(Legalizer, rcc::OptimizationLevel::O2); rcc::MachineFunctionAnalysisManager Analyses; auto Run = Pass.run(*Fixture.Function, *Target, Analyses); const rcc::Opcode LegalOpcode = @@ -202,7 +169,6 @@ int main() { TestContext Context; testNullAndMissingContracts(Context); testUnsupportedRollback(Context); - testLegalizerCycleDiagnostic(Context); testLegalizerRevisitsInvalidatedInstructions(Context); return Context.result(); } |