diff options
19 files changed, 2712 insertions, 478 deletions
diff --git a/backend/include/rcc/ADT/APInt.h b/backend/include/rcc/ADT/APInt.h index 22ecf62..8b869be 100644 --- a/backend/include/rcc/ADT/APInt.h +++ b/backend/include/rcc/ADT/APInt.h @@ -43,7 +43,14 @@ public: [[nodiscard]] bool isNegative() const noexcept; [[nodiscard]] std::size_t activeBitWidth() const noexcept; [[nodiscard]] std::size_t countrZero() const noexcept; + [[nodiscard]] std::size_t countlOne() const noexcept; + [[nodiscard]] bool isAllOnes() const noexcept; + [[nodiscard]] bool testBit(std::size_t Bit) const noexcept; [[nodiscard]] std::uint64_t word(std::size_t Index) const noexcept; + [[nodiscard]] Expected<APInt> bitwiseAnd(const APInt &Other) const; + [[nodiscard]] Expected<APInt> bitwiseOr(const APInt &Other) const; + [[nodiscard]] Expected<APInt> bitwiseXor(const APInt &Other) const; + [[nodiscard]] Expected<APInt> bitwiseNot() const; [[nodiscard]] Expected<APInt> trunc(std::uint32_t NewBitWidth) const; [[nodiscard]] Expected<APInt> zext(std::uint32_t NewBitWidth) const; [[nodiscard]] Expected<APInt> sext(std::uint32_t NewBitWidth) const; diff --git a/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h b/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h new file mode 100644 index 0000000..aa02fe3 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h @@ -0,0 +1,53 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_GISELVALUETRACKING_H +#define RCC_CODEGEN_GLOBALISEL_GISELVALUETRACKING_H + +#include "rcc/ADT/APInt.h" +#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/Support/Error.h" + +#include <cstdint> + +namespace rcc { + +class MachineFunction; +class MachineRegisterInfo; +class TargetDescription; + +class GISelValueTracking final : public GISelChangeObserver { +public: + GISelValueTracking(MachineFunction &Function, const TargetDescription &Target, + unsigned MaxDepth = 6) noexcept; + + [[nodiscard]] const MachineFunction &getMachineFunction() const noexcept { + return Function; + } + + [[nodiscard]] Expected<APInt> getKnownZeroes(Register Reg) const; + [[nodiscard]] Expected<std::uint32_t> computeNumSignBits(Register Reg, unsigned Depth = 0) const; + + void erasingInstr(MachineInstr &) override {} + void createdInstr(MachineInstr &) override {} + void changingInstr(MachineInstr &) override {} + void changedInstr(MachineInstr &) override {} + +private: + struct KnownBits final { + APInt Zero; + APInt One; + }; + + [[nodiscard]] Expected<KnownBits> makeUnknown(std::uint32_t BitWidth) const; + [[nodiscard]] Expected<KnownBits> getKnownBits(Register Reg, unsigned Depth = 0) const; + + MachineFunction &Function; + MachineRegisterInfo &MRI; + const TargetDescription &Target; + unsigned MaxDepth; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_GISELVALUETRACKING_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h index c3f8d0b..7e2961d 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h @@ -4,8 +4,9 @@ #define RCC_CODEGEN_GLOBALISEL_LEGALIZATIONARTIFACTCOMBINER_H #include "rcc/CodeGen/GenericOpcodes.h" -#include "rcc/CodeGen/GlobalISel/GenericMachineInstrs.h" #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h" +#include "rcc/CodeGen/GlobalISel/GenericMachineInstrs.h" #include "rcc/CodeGen/GlobalISel/LegalizerInfo.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineIRBuilder.h" @@ -30,6 +31,7 @@ class LegalizationArtifactCombiner final { MachineIRBuilder &Builder; MachineRegisterInfo &MRI; const LegalizerInfo &LI; + GISelValueTracking *VT; [[nodiscard]] static bool isArtifactCast(Opcode InstructionOpcode) noexcept { switch (static_cast<GenericOpcode>(InstructionOpcode.value())) { @@ -45,13 +47,13 @@ class LegalizationArtifactCombiner final { public: LegalizationArtifactCombiner(MachineIRBuilder &Builder, MachineRegisterInfo &MRI, - const LegalizerInfo &Info) - : Builder(Builder), MRI(MRI), LI(Info) {} + const LegalizerInfo &Info, + GISelValueTracking *ValueTracking = nullptr) + : Builder(Builder), MRI(MRI), LI(Info), VT(ValueTracking) {} - [[nodiscard]] Expected<bool> - tryCombineInstruction(MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - GISelObserverWrapper &Observer) { + [[nodiscard]] Expected<bool> tryCombineInstruction(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + GISelObserverWrapper &Observer) { if (!DeadInstructions.empty()) { auto Deleted = deleteMarkedDeadInsts(DeadInstructions, Observer); if (!Deleted) @@ -77,9 +79,23 @@ public: break; case GenericOpcode::G_MERGE_VALUES: case GenericOpcode::G_BUILD_VECTOR: - case GenericOpcode::G_CONCAT_VECTORS: + case GenericOpcode::G_CONCAT_VECTORS: { + const auto Destination = Instruction.operandAt(0)->registerValue(); + if (Destination) { + for (MachineOperand &Use : MRI.useOperands(*Destination)) { + MachineInstr *User = Use.parent(); + if (User == nullptr) + continue; + if (User->opcode() == opcode(GenericOpcode::G_UNMERGE_VALUES) || + User->opcode() == opcode(GenericOpcode::G_TRUNC)) { + UpdatedDefs.push_back(*Destination); + break; + } + } + } Changed = tryCombineMergeLike(Instruction, DeadInstructions, UpdatedDefs, Observer); break; + } case GenericOpcode::G_EXTRACT: Changed = tryCombineExtract(Instruction, DeadInstructions, UpdatedDefs); break; @@ -114,14 +130,12 @@ public: case GenericOpcode::G_ASSERT_SEXT: case GenericOpcode::G_ASSERT_ZEXT: case GenericOpcode::G_ASSERT_ALIGN: - if (const auto Copy = Use->operandAt(0)->registerValue(); - Copy && Copy->isVirtual()) + if (const auto Copy = Use->operandAt(0)->registerValue(); Copy && Copy->isVirtual()) UpdatedDefs.push_back(*Copy); break; default: if (Use->opcode() == opcode(GenericOpcode::COPY)) { - if (const auto Copy = Use->operandAt(0)->registerValue(); - Copy && Copy->isVirtual()) + if (const auto Copy = Use->operandAt(0)->registerValue(); Copy && Copy->isVirtual()) UpdatedDefs.push_back(*Copy); } break; @@ -134,128 +148,107 @@ public: private: class ArtifactValueFinder final { public: - explicit ArtifactValueFinder(LegalizationArtifactCombiner &Combiner) - : Combiner(Combiner) {} + explicit ArtifactValueFinder(LegalizationArtifactCombiner &Combiner) : Combiner(Combiner) {} - [[nodiscard]] Expected<Register> findValueFromDef(Register DefReg, - std::uint64_t StartBit, + [[nodiscard]] Expected<Register> findValueFromDef(Register DefReg, std::uint64_t StartBit, std::uint64_t Size, LowLevelType DestinationType); + [[nodiscard]] Expected<bool> tryCombineUnmergeDefs(GUnmerge &Instruction, + GISelChangeObserver &Observer, + std::vector<Register> &UpdatedDefs); + [[nodiscard]] Expected<GUnmerge *> findUnmergeThatDefinesReg(Register Reg, std::uint64_t Size, + std::size_t &DefOperandIndex); [[nodiscard]] Expected<bool> - tryCombineUnmergeDefs(GUnmerge &Instruction, - GISelChangeObserver &Observer, - std::vector<Register> &UpdatedDefs); - [[nodiscard]] Expected<GUnmerge *> - findUnmergeThatDefinesReg(Register Reg, std::uint64_t Size, - std::size_t &DefOperandIndex); - [[nodiscard]] Expected<bool> - isSequenceFromUnmerge(GMergeLikeInstr &Instruction, - std::size_t MergeStartIndex, GUnmerge *Unmerge, - std::size_t UnmergeStartIndex, - std::size_t ElementCount, std::uint64_t ElementSize, - bool AllowUndef); - [[nodiscard]] Expected<bool> - tryCombineMergeLike(GMergeLikeInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs, - GISelChangeObserver &Observer); + isSequenceFromUnmerge(GMergeLikeInstr &Instruction, std::size_t MergeStartIndex, + GUnmerge *Unmerge, std::size_t UnmergeStartIndex, + std::size_t ElementCount, std::uint64_t ElementSize, bool AllowUndef); + [[nodiscard]] Expected<bool> tryCombineMergeLike(GMergeLikeInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelChangeObserver &Observer); private: + [[nodiscard]] Expected<Register> findValueFromDefImpl(Register DefReg, std::uint64_t StartBit, + std::uint64_t Size, + LowLevelType DestinationType); + [[nodiscard]] Expected<Register> findValueFromConcat(GConcatVectors &Instruction, + std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType); [[nodiscard]] Expected<Register> - findValueFromDefImpl(Register DefReg, std::uint64_t StartBit, - std::uint64_t Size, LowLevelType DestinationType); - [[nodiscard]] Expected<Register> - findValueFromConcat(GConcatVectors &Instruction, - std::uint64_t StartBit, std::uint64_t Size, - LowLevelType DestinationType); - [[nodiscard]] Expected<Register> - findValueFromBuildVector(GBuildVector &Instruction, - std::uint64_t StartBit, std::uint64_t Size); - [[nodiscard]] Expected<Register> - findValueFromInsert(MachineInstr &Instruction, std::uint64_t StartBit, - std::uint64_t Size, LowLevelType DestinationType); - [[nodiscard]] Expected<Register> - findValueFromExtension(MachineInstr &Instruction, - std::uint64_t StartBit, std::uint64_t Size, - LowLevelType DestinationType); - [[nodiscard]] Expected<Register> - findValueFromTrunc(MachineInstr &Instruction, std::uint64_t StartBit, - std::uint64_t Size, LowLevelType DestinationType); + findValueFromBuildVector(GBuildVector &Instruction, std::uint64_t StartBit, std::uint64_t Size); + [[nodiscard]] Expected<Register> findValueFromInsert(MachineInstr &Instruction, + std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType); + [[nodiscard]] Expected<Register> findValueFromExtension(MachineInstr &Instruction, + std::uint64_t StartBit, + std::uint64_t Size, + LowLevelType DestinationType); + [[nodiscard]] Expected<Register> findValueFromTrunc(MachineInstr &Instruction, + std::uint64_t StartBit, std::uint64_t Size, + LowLevelType DestinationType); LegalizationArtifactCombiner &Combiner; Register CurrentBest; std::unordered_set<Register> Visited; }; + [[nodiscard]] Expected<bool> tryCombineAnyExt(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> tryCombineZExt(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> tryCombineSExt(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> tryCombineTrunc(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); [[nodiscard]] Expected<bool> - tryCombineAnyExt(MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs, - GISelObserverWrapper &Observer); - [[nodiscard]] Expected<bool> - tryCombineZExt(MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs, - GISelObserverWrapper &Observer); - [[nodiscard]] Expected<bool> - tryCombineSExt(MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs, - GISelObserverWrapper &Observer); - [[nodiscard]] Expected<bool> - tryCombineTrunc(MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs, - GISelObserverWrapper &Observer); - [[nodiscard]] Expected<bool> - tryCombineUnmergeValues(MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs, - GISelObserverWrapper &Observer); - [[nodiscard]] Expected<bool> - tryCombineExtract(MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs); - [[nodiscard]] Expected<bool> - tryCombineMergeLike(MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs, - GISelObserverWrapper &Observer); - [[nodiscard]] Expected<bool> tryFoldImplicitDef( - MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer); + tryCombineUnmergeValues(MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> tryCombineExtract(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs); + [[nodiscard]] Expected<bool> tryCombineMergeLike(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); + [[nodiscard]] Expected<bool> tryFoldImplicitDef(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs, + GISelObserverWrapper &Observer); [[nodiscard]] Expected<MachineInstr *> buildUnary(GenericOpcode InstructionOpcode, - Register Destination, - Register Source); - [[nodiscard]] Expected<MachineInstr *> - buildMergeLike(Register Destination, const std::vector<Register> &Sources); + Register Destination, Register Source); + [[nodiscard]] Expected<MachineInstr *> buildMergeLike(Register Destination, + const std::vector<Register> &Sources); [[nodiscard]] Expected<void> buildConstant(Register Destination, APInt Value); [[nodiscard]] Expected<Register> buildConstant(LowLevelType Type, APInt Value); [[nodiscard]] Expected<bool> isConstantUnsupported(LowLevelType Type) const; - [[nodiscard]] static std::optional<std::int64_t> - immediateOperand(const MachineInstr &Instruction, std::size_t Index); - [[nodiscard]] static std::size_t getDefIndex(const MachineInstr &Instruction, - Register SearchDef); + [[nodiscard]] static std::optional<std::int64_t> immediateOperand(const MachineInstr &Instruction, + std::size_t Index); + [[nodiscard]] static std::size_t getDefIndex(const MachineInstr &Instruction, Register SearchDef); [[nodiscard]] Expected<std::pair<MachineInstr *, Register>> definitionIgnoringCopies(Register Reg) const; - [[nodiscard]] Expected<std::vector<Register>> - buildOrFindUnmerge(LowLevelType DestinationType, Register Source); - [[nodiscard]] Expected<LowLevelType> divideType(LowLevelType Type, - std::size_t Parts) const; - [[nodiscard]] Expected<bool> - tryFoldUnmergeCast(MachineInstr &Instruction, MachineInstr &Cast, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs); + [[nodiscard]] Expected<std::vector<Register>> buildOrFindUnmerge(LowLevelType DestinationType, + Register Source); + [[nodiscard]] Expected<LowLevelType> divideType(LowLevelType Type, std::size_t Parts) const; + [[nodiscard]] Expected<bool> tryFoldUnmergeCast(MachineInstr &Instruction, MachineInstr &Cast, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs); [[nodiscard]] static bool canFoldMergeOpcode(Opcode MergeOpcode, std::optional<Opcode> ConvertOpcode, LowLevelType OperandType, LowLevelType DestinationType); - [[nodiscard]] Expected<void> - replaceRegOrBuildCopy(Register Destination, Register Source, - std::vector<Register> &UpdatedDefs, - GISelChangeObserver &Observer) { + [[nodiscard]] Expected<void> replaceRegOrBuildCopy(Register Destination, Register Source, + std::vector<Register> &UpdatedDefs, + GISelChangeObserver &Observer) { auto DestinationType = MRI.getType(Destination); if (!DestinationType) return std::unexpected(DestinationType.error()); @@ -288,8 +281,7 @@ private: [[nodiscard]] Register lookThroughCopyInstrs(Register Reg) const { while (MachineInstr *Definition = MRI.getVRegDef(Reg)) { - if (Definition->opcode() != opcode(GenericOpcode::COPY) || - Definition->operandCount() < 2) + if (Definition->opcode() != opcode(GenericOpcode::COPY) || Definition->operandCount() < 2) break; const auto Source = Definition->operandAt(1)->registerValue(); if (!Source || !Source->isVirtual()) @@ -299,8 +291,8 @@ private: return Reg; } - [[nodiscard]] static std::optional<Register> - registerOperand(const MachineInstr &Instruction, std::size_t Index) { + [[nodiscard]] static std::optional<Register> registerOperand(const MachineInstr &Instruction, + std::size_t Index) { const MachineOperand *Operand = Instruction.operandAt(Index); return Operand == nullptr ? std::nullopt : Operand->registerValue(); } @@ -311,8 +303,7 @@ private: } void markDefDead(MachineInstr &Instruction, MachineInstr &Definition, - std::vector<MachineInstr *> &DeadInstructions, - std::size_t DefIndex = 0) { + std::vector<MachineInstr *> &DeadInstructions, std::size_t DefIndex = 0) { MachineInstr *Previous = &Instruction; while (Previous != &Definition) { const auto Source = artifactSourceRegister(*Previous); @@ -347,15 +338,13 @@ private: } void markInstAndDefDead(MachineInstr &Instruction, MachineInstr &Definition, - std::vector<MachineInstr *> &DeadInstructions, - std::size_t DefIndex = 0) { + std::vector<MachineInstr *> &DeadInstructions, std::size_t DefIndex = 0) { DeadInstructions.push_back(&Instruction); markDefDead(Instruction, Definition, DeadInstructions, DefIndex); } - [[nodiscard]] Expected<void> - deleteMarkedDeadInsts(std::vector<MachineInstr *> &DeadInstructions, - GISelObserverWrapper &) { + [[nodiscard]] Expected<void> deleteMarkedDeadInsts(std::vector<MachineInstr *> &DeadInstructions, + GISelObserverWrapper &) { for (MachineInstr *Dead : DeadInstructions) { if (Dead == nullptr || Dead->parent() == nullptr) continue; @@ -395,12 +384,10 @@ private: [[nodiscard]] Expected<bool> isInstLegal(LegalizationQuery Query) const { return LI.isLegal(Query); } - }; inline Expected<MachineInstr *> -LegalizationArtifactCombiner::buildUnary(GenericOpcode InstructionOpcode, - Register Destination, +LegalizationArtifactCombiner::buildUnary(GenericOpcode InstructionOpcode, Register Destination, Register Source) { auto Pending = Builder.buildInstr(opcode(InstructionOpcode)); if (!Pending) @@ -412,8 +399,9 @@ LegalizationArtifactCombiner::buildUnary(GenericOpcode InstructionOpcode, return Pending->build(); } -inline Expected<MachineInstr *> LegalizationArtifactCombiner::buildMergeLike( - Register Destination, const std::vector<Register> &Sources) { +inline Expected<MachineInstr *> +LegalizationArtifactCombiner::buildMergeLike(Register Destination, + const std::vector<Register> &Sources) { if (Sources.empty()) return makeUnexpected(ErrorCode::InvalidArgument, "merge-like instruction requires source registers"); @@ -426,8 +414,8 @@ inline Expected<MachineInstr *> LegalizationArtifactCombiner::buildMergeLike( GenericOpcode InstructionOpcode = GenericOpcode::G_MERGE_VALUES; if (DestinationType->isVector()) - InstructionOpcode = SourceType->isVector() ? GenericOpcode::G_CONCAT_VECTORS - : GenericOpcode::G_BUILD_VECTOR; + InstructionOpcode = + SourceType->isVector() ? GenericOpcode::G_CONCAT_VECTORS : GenericOpcode::G_BUILD_VECTOR; auto Pending = Builder.buildInstr(opcode(InstructionOpcode)); if (!Pending) return std::unexpected(Pending.error()); @@ -440,16 +428,16 @@ inline Expected<MachineInstr *> LegalizationArtifactCombiner::buildMergeLike( return Pending->build(); } -inline Expected<void> -LegalizationArtifactCombiner::buildConstant(Register Destination, APInt Value) { +inline Expected<void> LegalizationArtifactCombiner::buildConstant(Register Destination, + APInt Value) { auto Built = Builder.buildConstant(Destination, std::move(Value)); if (!Built) return std::unexpected(Built.error()); return {}; } -inline Expected<Register> -LegalizationArtifactCombiner::buildConstant(LowLevelType Type, APInt Value) { +inline Expected<Register> LegalizationArtifactCombiner::buildConstant(LowLevelType Type, + APInt Value) { auto Destination = MRI.createVirtualRegister(Type); if (!Destination) return std::unexpected(Destination.error()); @@ -459,25 +447,22 @@ LegalizationArtifactCombiner::buildConstant(LowLevelType Type, APInt Value) { return *Destination; } -inline Expected<bool> -LegalizationArtifactCombiner::isConstantUnsupported(LowLevelType Type) const { +inline Expected<bool> LegalizationArtifactCombiner::isConstantUnsupported(LowLevelType Type) const { if (!Type.isVector()) - return isInstUnsupported( - LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {Type})); + return isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {Type})); const auto ElementType = Type.scalarElementType(); if (!ElementType) return true; - auto ConstantUnsupported = isInstUnsupported( - LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*ElementType})); + auto ConstantUnsupported = + isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*ElementType})); if (!ConstantUnsupported || *ConstantUnsupported) return ConstantUnsupported; - return isInstUnsupported(LegalizationQuery( - opcode(GenericOpcode::G_BUILD_VECTOR), {Type, *ElementType})); + return isInstUnsupported( + LegalizationQuery(opcode(GenericOpcode::G_BUILD_VECTOR), {Type, *ElementType})); } inline std::optional<std::int64_t> -LegalizationArtifactCombiner::immediateOperand(const MachineInstr &Instruction, - std::size_t Index) { +LegalizationArtifactCombiner::immediateOperand(const MachineInstr &Instruction, std::size_t Index) { const MachineOperand *Operand = Instruction.operandAt(Index); if (Operand == nullptr) return std::nullopt; @@ -486,9 +471,8 @@ LegalizationArtifactCombiner::immediateOperand(const MachineInstr &Instruction, return std::nullopt; } -inline std::size_t -LegalizationArtifactCombiner::getDefIndex(const MachineInstr &Instruction, - Register SearchDef) { +inline std::size_t LegalizationArtifactCombiner::getDefIndex(const MachineInstr &Instruction, + Register SearchDef) { std::size_t Index = 0; for (const MachineOperand &Operand : Instruction.operands()) { if (!Operand.isDef()) @@ -517,9 +501,8 @@ LegalizationArtifactCombiner::definitionIgnoringCopies(Register Reg) const { return std::pair<MachineInstr *, Register>{nullptr, Reg}; } -inline Expected<LowLevelType> -LegalizationArtifactCombiner::divideType(LowLevelType Type, - std::size_t Parts) const { +inline Expected<LowLevelType> LegalizationArtifactCombiner::divideType(LowLevelType Type, + std::size_t Parts) const { if (Parts == 0 || Type.minimumBitWidth() % Parts != 0) return makeUnexpected(ErrorCode::InvalidArgument, "LowLevelType cannot be divided into equal parts"); @@ -530,20 +513,16 @@ LegalizationArtifactCombiner::divideType(LowLevelType Type, "vector element count cannot be divided into equal parts"); const auto ElementType = Type.scalarElementType(); if (!ElementType) - return makeUnexpected(ErrorCode::InvalidArgument, - "vector has no scalar element type"); - const std::uint32_t Elements = - Type.minimumElementCount() / static_cast<std::uint32_t>(Parts); + return makeUnexpected(ErrorCode::InvalidArgument, "vector has no scalar element type"); + const std::uint32_t Elements = Type.minimumElementCount() / static_cast<std::uint32_t>(Parts); if (Elements == 1) return *ElementType; - return Type.isScalableVector() - ? LowLevelType::makeScalableVector(Elements, *ElementType) - : LowLevelType::makeFixedVector(Elements, *ElementType); + return Type.isScalableVector() ? LowLevelType::makeScalableVector(Elements, *ElementType) + : LowLevelType::makeFixedVector(Elements, *ElementType); } inline Expected<std::vector<Register>> -LegalizationArtifactCombiner::buildOrFindUnmerge(LowLevelType DestinationType, - Register Source) { +LegalizationArtifactCombiner::buildOrFindUnmerge(LowLevelType DestinationType, Register Source) { auto SourceType = MRI.getType(Source); if (!SourceType) return std::unexpected(SourceType.error()); @@ -551,8 +530,8 @@ LegalizationArtifactCombiner::buildOrFindUnmerge(LowLevelType DestinationType, SourceType->minimumBitWidth() % DestinationType.minimumBitWidth() != 0) return makeUnexpected(ErrorCode::InvalidArgument, "unmerge destination does not tile the source type"); - const std::size_t Count = static_cast<std::size_t>( - SourceType->minimumBitWidth() / DestinationType.minimumBitWidth()); + const std::size_t Count = + static_cast<std::size_t>(SourceType->minimumBitWidth() / DestinationType.minimumBitWidth()); for (MachineOperand &Use : MRI.useOperands(Source)) { MachineInstr *Candidate = Use.parent(); @@ -592,17 +571,17 @@ LegalizationArtifactCombiner::buildOrFindUnmerge(LowLevelType DestinationType, return Destinations; } -inline bool LegalizationArtifactCombiner::canFoldMergeOpcode( - Opcode MergeOpcode, std::optional<Opcode> ConvertOpcode, - LowLevelType OperandType, LowLevelType DestinationType) { +inline bool LegalizationArtifactCombiner::canFoldMergeOpcode(Opcode MergeOpcode, + std::optional<Opcode> ConvertOpcode, + LowLevelType OperandType, + LowLevelType DestinationType) { const auto Generic = static_cast<GenericOpcode>(MergeOpcode.value()); - if (Generic == GenericOpcode::G_BUILD_VECTOR || - Generic == GenericOpcode::G_MERGE_VALUES) { + if (Generic == GenericOpcode::G_BUILD_VECTOR || Generic == GenericOpcode::G_MERGE_VALUES) { if (!ConvertOpcode) return true; const auto ElementType = OperandType.scalarElementType(); - return !DestinationType.isVector() && OperandType.isVector() && - ElementType && DestinationType == *ElementType; + return !DestinationType.isVector() && OperandType.isVector() && ElementType && + DestinationType == *ElementType; } if (Generic != GenericOpcode::G_CONCAT_VECTORS) return false; @@ -619,14 +598,12 @@ inline bool LegalizationArtifactCombiner::canFoldMergeOpcode( } inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt( - MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, + MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { const auto Destination = registerOperand(Instruction, 0); const auto OriginalSource = registerOperand(Instruction, 1); if (!Destination || !OriginalSource) - return makeUnexpected(ErrorCode::VerificationError, - "G_ANYEXT has invalid register operands"); + return makeUnexpected(ErrorCode::VerificationError, "G_ANYEXT has invalid register operands"); const Register Source = lookThroughCopyInstrs(*OriginalSource); MachineInstr *SourceDefinition = MRI.getVRegDef(Source); if (SourceDefinition == nullptr) @@ -645,8 +622,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt( if (!TruncSourceType) return std::unexpected(TruncSourceType.error()); if (*DestinationType == *TruncSourceType) { - auto Replaced = replaceRegOrBuildCopy(*Destination, *TruncSource, - UpdatedDefs, Observer); + auto Replaced = replaceRegOrBuildCopy(*Destination, *TruncSource, UpdatedDefs, Observer); if (!Replaced) return std::unexpected(Replaced.error()); } else { @@ -665,9 +641,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt( const auto ExtensionSource = registerOperand(*SourceDefinition, 1); if (!ExtensionSource) return false; - auto Built = buildUnary( - static_cast<GenericOpcode>(SourceDefinition->opcode().value()), - *Destination, *ExtensionSource); + auto Built = buildUnary(static_cast<GenericOpcode>(SourceDefinition->opcode().value()), + *Destination, *ExtensionSource); if (!Built) return std::unexpected(Built.error()); UpdatedDefs.push_back(*Destination); @@ -679,12 +654,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt( auto DestinationType = MRI.getType(*Destination); if (!DestinationType) return std::unexpected(DestinationType.error()); - auto Legal = isInstLegal(LegalizationQuery( - opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); + auto Legal = + isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); if (!Legal) return std::unexpected(Legal.error()); - const auto *Immediate = - SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); + const auto *Immediate = SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); if (*Legal && Immediate != nullptr) { auto Extended = Immediate->Value.sext(DestinationType->scalarBitWidth()); if (!Extended) @@ -697,19 +671,16 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineAnyExt( return true; } } - return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, - Observer); + return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, Observer); } inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt( - MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, + MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { const auto Destination = registerOperand(Instruction, 0); const auto OriginalSource = registerOperand(Instruction, 1); if (!Destination || !OriginalSource) - return makeUnexpected(ErrorCode::VerificationError, - "G_ZEXT has invalid register operands"); + return makeUnexpected(ErrorCode::VerificationError, "G_ZEXT has invalid register operands"); const Register Source = lookThroughCopyInstrs(*OriginalSource); MachineInstr *SourceDefinition = MRI.getVRegDef(Source); if (SourceDefinition == nullptr) @@ -728,8 +699,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt( auto SourceType = MRI.getType(Source); if (!SourceType) return std::unexpected(SourceType.error()); - auto AndUnsupported = isInstUnsupported( - LegalizationQuery(opcode(GenericOpcode::G_AND), {*DestinationType})); + auto AndUnsupported = + isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_AND), {*DestinationType})); if (!AndUnsupported) return std::unexpected(AndUnsupported.error()); auto ConstantUnsupported = isConstantUnsupported(*DestinationType); @@ -753,16 +724,32 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt( return std::unexpected(Built.error()); WideSource = *Wide; } - auto Mask = APInt::getLowBitsSet(DestinationType->scalarBitWidth(), - SourceType->scalarBitWidth()); + auto Mask = + APInt::getLowBitsSet(DestinationType->scalarBitWidth(), SourceType->scalarBitWidth()); if (!Mask) return std::unexpected(Mask.error()); - auto MaskRegister = buildConstant(*DestinationType, std::move(*Mask)); - if (!MaskRegister) - return std::unexpected(MaskRegister.error()); - auto Built = Builder.buildAnd(*Destination, WideSource, *MaskRegister); - if (!Built) - return std::unexpected(Built.error()); + bool ElideAnd = false; + if (VT != nullptr) { + auto KnownZeroes = VT->getKnownZeroes(WideSource); + if (!KnownZeroes) + return std::unexpected(KnownZeroes.error()); + auto CoveredBits = KnownZeroes->bitwiseOr(*Mask); + if (!CoveredBits) + return std::unexpected(CoveredBits.error()); + ElideAnd = CoveredBits->isAllOnes(); + } + if (ElideAnd) { + auto Replaced = replaceRegOrBuildCopy(*Destination, WideSource, UpdatedDefs, Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + } else { + auto MaskRegister = buildConstant(*DestinationType, std::move(*Mask)); + if (!MaskRegister) + return std::unexpected(MaskRegister.error()); + auto Built = Builder.buildAnd(*Destination, WideSource, *MaskRegister); + if (!Built) + return std::unexpected(Built.error()); + } UpdatedDefs.push_back(*Destination); markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); return true; @@ -786,12 +773,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt( auto DestinationType = MRI.getType(*Destination); if (!DestinationType) return std::unexpected(DestinationType.error()); - auto Legal = isInstLegal(LegalizationQuery( - opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); + auto Legal = + isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); if (!Legal) return std::unexpected(Legal.error()); - const auto *Immediate = - SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); + const auto *Immediate = SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); if (*Legal && Immediate != nullptr) { auto Extended = Immediate->Value.zext(DestinationType->scalarBitWidth()); if (!Extended) @@ -804,19 +790,16 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineZExt( return true; } } - return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, - Observer); + return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, Observer); } inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt( - MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, + MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { const auto Destination = registerOperand(Instruction, 0); const auto OriginalSource = registerOperand(Instruction, 1); if (!Destination || !OriginalSource) - return makeUnexpected(ErrorCode::VerificationError, - "G_SEXT has invalid register operands"); + return makeUnexpected(ErrorCode::VerificationError, "G_SEXT has invalid register operands"); const Register Source = lookThroughCopyInstrs(*OriginalSource); MachineInstr *SourceDefinition = MRI.getVRegDef(Source); if (SourceDefinition == nullptr) @@ -834,8 +817,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt( auto SourceType = MRI.getType(Source); if (!SourceType) return std::unexpected(SourceType.error()); - auto Unsupported = isInstUnsupported(LegalizationQuery( - opcode(GenericOpcode::G_SEXT_INREG), {*DestinationType})); + auto Unsupported = isInstUnsupported( + LegalizationQuery(opcode(GenericOpcode::G_SEXT_INREG), {*DestinationType})); if (!Unsupported) return std::unexpected(Unsupported.error()); if (*Unsupported) @@ -853,10 +836,22 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt( return std::unexpected(Built.error()); WideSource = *Wide; } - auto Built = Builder.buildSExtInReg(*Destination, WideSource, - SourceType->scalarBitWidth()); - if (!Built) - return std::unexpected(Built.error()); + bool ElideSExtInReg = false; + if (VT != nullptr) { + auto SignBits = VT->computeNumSignBits(WideSource); + if (!SignBits) + return std::unexpected(SignBits.error()); + ElideSExtInReg = *SignBits > DestinationType->scalarBitWidth() - SourceType->scalarBitWidth(); + } + if (ElideSExtInReg) { + auto Replaced = replaceRegOrBuildCopy(*Destination, WideSource, UpdatedDefs, Observer); + if (!Replaced) + return std::unexpected(Replaced.error()); + } else { + auto Built = Builder.buildSExtInReg(*Destination, WideSource, SourceType->scalarBitWidth()); + if (!Built) + return std::unexpected(Built.error()); + } UpdatedDefs.push_back(*Destination); markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); return true; @@ -867,9 +862,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt( const auto ExtensionSource = registerOperand(*SourceDefinition, 1); if (!ExtensionSource) return false; - auto Built = buildUnary( - static_cast<GenericOpcode>(SourceDefinition->opcode().value()), - *Destination, *ExtensionSource); + auto Built = buildUnary(static_cast<GenericOpcode>(SourceDefinition->opcode().value()), + *Destination, *ExtensionSource); if (!Built) return std::unexpected(Built.error()); UpdatedDefs.push_back(*Destination); @@ -881,12 +875,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt( auto DestinationType = MRI.getType(*Destination); if (!DestinationType) return std::unexpected(DestinationType.error()); - auto Legal = isInstLegal(LegalizationQuery( - opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); + auto Legal = + isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); if (!Legal) return std::unexpected(Legal.error()); - const auto *Immediate = - SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); + const auto *Immediate = SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); if (*Legal && Immediate != nullptr) { auto Extended = Immediate->Value.sext(DestinationType->scalarBitWidth()); if (!Extended) @@ -899,13 +892,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineSExt( return true; } } - return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, - Observer); + return tryFoldImplicitDef(Instruction, DeadInstructions, UpdatedDefs, Observer); } inline Expected<bool> LegalizationArtifactCombiner::tryFoldImplicitDef( - MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, + MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, std::vector<Register> &UpdatedDefs, GISelObserverWrapper &) { const auto Destination = registerOperand(Instruction, 0); const auto Source = registerOperand(Instruction, 1); @@ -920,8 +911,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryFoldImplicitDef( if (auto Point = Builder.setInsertPointBefore(Instruction); !Point) return std::unexpected(Point.error()); if (Instruction.opcode() == opcode(GenericOpcode::G_ANYEXT)) { - auto Legal = isInstLegal(LegalizationQuery( - opcode(GenericOpcode::G_IMPLICIT_DEF), {*DestinationType})); + auto Legal = + isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_IMPLICIT_DEF), {*DestinationType})); if (!Legal) return std::unexpected(Legal.error()); if (!*Legal) @@ -945,14 +936,12 @@ inline Expected<bool> LegalizationArtifactCombiner::tryFoldImplicitDef( } inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc( - MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, + MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { const auto Destination = registerOperand(Instruction, 0); const auto OriginalSource = registerOperand(Instruction, 1); if (!Destination || !OriginalSource) - return makeUnexpected(ErrorCode::VerificationError, - "G_TRUNC has invalid register operands"); + return makeUnexpected(ErrorCode::VerificationError, "G_TRUNC has invalid register operands"); const Register Source = lookThroughCopyInstrs(*OriginalSource); MachineInstr *SourceDefinition = MRI.getVRegDef(Source); if (SourceDefinition == nullptr) @@ -964,12 +953,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc( return std::unexpected(Point.error()); if (hasOpcode(SourceDefinition, GenericOpcode::G_CONSTANT)) { - auto Legal = isInstLegal(LegalizationQuery( - opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); + auto Legal = + isInstLegal(LegalizationQuery(opcode(GenericOpcode::G_CONSTANT), {*DestinationType})); if (!Legal) return std::unexpected(Legal.error()); - const auto *Immediate = - SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); + const auto *Immediate = SourceDefinition->operandAt(1)->getIf<IntegerImmediateOperand>(); if (*Legal && Immediate != nullptr) { auto Truncated = Immediate->Value.trunc(DestinationType->scalarBitWidth()); if (!Truncated) @@ -991,15 +979,13 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc( auto FirstSourceType = MRI.getType(FirstSource); if (!FirstSourceType) return std::unexpected(FirstSourceType.error()); - if (!DestinationType->isCategoryNeutralScalar() || - !FirstSourceType->isCategoryNeutralScalar()) + if (!DestinationType->isCategoryNeutralScalar() || !FirstSourceType->isCategoryNeutralScalar()) return false; const std::uint64_t DestinationSize = DestinationType->minimumBitWidth(); const std::uint64_t SourceSize = FirstSourceType->minimumBitWidth(); if (DestinationSize < SourceSize) { - auto Unsupported = isInstUnsupported(LegalizationQuery( - opcode(GenericOpcode::G_TRUNC), - {*DestinationType, *FirstSourceType})); + auto Unsupported = isInstUnsupported( + LegalizationQuery(opcode(GenericOpcode::G_TRUNC), {*DestinationType, *FirstSourceType})); if (!Unsupported) return std::unexpected(Unsupported.error()); if (*Unsupported) @@ -1009,18 +995,15 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc( return std::unexpected(Built.error()); UpdatedDefs.push_back(*Destination); } else if (DestinationSize == SourceSize) { - auto Replaced = replaceRegOrBuildCopy(*Destination, FirstSource, - UpdatedDefs, Observer); + auto Replaced = replaceRegOrBuildCopy(*Destination, FirstSource, UpdatedDefs, Observer); if (!Replaced) return std::unexpected(Replaced.error()); } else if (DestinationSize % SourceSize == 0) { - const std::size_t SourceCount = - static_cast<std::size_t>(DestinationSize / SourceSize); + const std::size_t SourceCount = static_cast<std::size_t>(DestinationSize / SourceSize); if (SourceCount >= Merge.getNumSources()) return false; - auto Unsupported = isInstUnsupported(LegalizationQuery( - opcode(GenericOpcode::G_MERGE_VALUES), - {*DestinationType, *FirstSourceType})); + auto Unsupported = isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_MERGE_VALUES), + {*DestinationType, *FirstSourceType})); if (!Unsupported) return std::unexpected(Unsupported.error()); if (*Unsupported) @@ -1053,8 +1036,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc( } ArtifactValueFinder Finder(*this); - auto Found = Finder.findValueFromDef(*Destination, 0, - DestinationType->minimumBitWidth(), + auto Found = Finder.findValueFromDef(*Destination, 0, DestinationType->minimumBitWidth(), *DestinationType); if (!Found) return std::unexpected(Found.error()); @@ -1063,8 +1045,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc( if (!FoundType) return std::unexpected(FoundType.error()); if (*FoundType == *DestinationType) { - auto Replaced = replaceRegOrBuildCopy(*Destination, *Found, UpdatedDefs, - Observer); + auto Replaced = replaceRegOrBuildCopy(*Destination, *Found, UpdatedDefs, Observer); if (!Replaced) return std::unexpected(Replaced.error()); markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions); @@ -1074,10 +1055,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineTrunc( return false; } -inline Expected<bool> -LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike( - GMergeLikeInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, +inline Expected<bool> LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike( + GMergeLikeInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, std::vector<Register> &UpdatedDefs, GISelChangeObserver &Observer) { if (Instruction.getNumSources() == 0) return false; @@ -1087,8 +1066,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike( return std::unexpected(ElementType.error()); const std::uint64_t ElementSize = ElementType->minimumBitWidth(); std::size_t FirstUnmergeIndex = 0; - auto UnmergeResult = - findUnmergeThatDefinesReg(FirstElement, ElementSize, FirstUnmergeIndex); + auto UnmergeResult = findUnmergeThatDefinesReg(FirstElement, ElementSize, FirstUnmergeIndex); if (!UnmergeResult) return std::unexpected(UnmergeResult.error()); GUnmerge *Unmerge = *UnmergeResult; @@ -1106,15 +1084,14 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike( const std::size_t SourceCount = Instruction.getNumSources(); if (*DestinationType == *UnmergeSourceType && FirstUnmergeIndex == 0) { - auto Sequence = isSequenceFromUnmerge( - Instruction, 0, Unmerge, 0, SourceCount, ElementSize, - DestinationType->isVector()); + auto Sequence = isSequenceFromUnmerge(Instruction, 0, Unmerge, 0, SourceCount, ElementSize, + DestinationType->isVector()); if (!Sequence) return std::unexpected(Sequence.error()); if (!*Sequence) return false; - auto Replaced = Combiner.replaceRegOrBuildCopy( - Destination, UnmergeSource, UpdatedDefs, Observer); + auto Replaced = + Combiner.replaceRegOrBuildCopy(Destination, UnmergeSource, UpdatedDefs, Observer); if (!Replaced) return std::unexpected(Replaced.error()); DeadInstructions.push_back(&Instruction); @@ -1124,29 +1101,23 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike( const bool MatchingDomains = (!DestinationType->isVector() && !UnmergeSourceType->isVector()) || (DestinationType->isVector() && UnmergeSourceType->isVector() && - DestinationType->scalarElementType() == - UnmergeSourceType->scalarElementType()); + DestinationType->scalarElementType() == UnmergeSourceType->scalarElementType()); if (MatchingDomains && FirstUnmergeIndex % SourceCount == 0 && - UnmergeSourceType->minimumBitWidth() % - DestinationType->minimumBitWidth() == - 0) { - auto Sequence = isSequenceFromUnmerge( - Instruction, 0, Unmerge, FirstUnmergeIndex, SourceCount, ElementSize, - false); + UnmergeSourceType->minimumBitWidth() % DestinationType->minimumBitWidth() == 0) { + auto Sequence = isSequenceFromUnmerge(Instruction, 0, Unmerge, FirstUnmergeIndex, SourceCount, + ElementSize, false); if (!Sequence) return std::unexpected(Sequence.error()); if (*Sequence) { - auto NewUnmerge = Combiner.buildOrFindUnmerge(*DestinationType, - UnmergeSource); + auto NewUnmerge = Combiner.buildOrFindUnmerge(*DestinationType, UnmergeSource); if (!NewUnmerge) return std::unexpected(NewUnmerge.error()); const std::size_t DestinationIndex = static_cast<std::size_t>( - (FirstUnmergeIndex * ElementSize) / - DestinationType->minimumBitWidth()); + (FirstUnmergeIndex * ElementSize) / DestinationType->minimumBitWidth()); if (DestinationIndex >= NewUnmerge->size()) return false; - auto Replaced = Combiner.replaceRegOrBuildCopy( - Destination, (*NewUnmerge)[DestinationIndex], UpdatedDefs, Observer); + auto Replaced = Combiner.replaceRegOrBuildCopy(Destination, (*NewUnmerge)[DestinationIndex], + UpdatedDefs, Observer); if (!Replaced) return std::unexpected(Replaced.error()); DeadInstructions.push_back(&Instruction); @@ -1155,27 +1126,22 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike( } if (DestinationType->isVector() == UnmergeSourceType->isVector() && - DestinationType->minimumBitWidth() % - UnmergeSourceType->minimumBitWidth() == - 0) { + DestinationType->minimumBitWidth() % UnmergeSourceType->minimumBitWidth() == 0) { const std::size_t UnmergeElementCount = Unmerge->getNumDefs(); if (UnmergeElementCount == 0 || SourceCount % UnmergeElementCount != 0) return false; std::vector<Register> MergeSources; - for (std::size_t Start = 0; Start < SourceCount; - Start += UnmergeElementCount) { + for (std::size_t Start = 0; Start < SourceCount; Start += UnmergeElementCount) { std::size_t SourceDefIndex = 0; - auto SourceUnmerge = findUnmergeThatDefinesReg( - Instruction.getSourceReg(Start), ElementSize, SourceDefIndex); + auto SourceUnmerge = + findUnmergeThatDefinesReg(Instruction.getSourceReg(Start), ElementSize, SourceDefIndex); if (!SourceUnmerge) return std::unexpected(SourceUnmerge.error()); - if (*SourceUnmerge == nullptr || - (*SourceUnmerge)->getNumDefs() != UnmergeElementCount || + if (*SourceUnmerge == nullptr || (*SourceUnmerge)->getNumDefs() != UnmergeElementCount || SourceDefIndex != 0) return false; - auto Sequence = isSequenceFromUnmerge( - Instruction, Start, *SourceUnmerge, 0, UnmergeElementCount, - ElementSize, false); + auto Sequence = isSequenceFromUnmerge(Instruction, Start, *SourceUnmerge, 0, + UnmergeElementCount, ElementSize, false); if (!Sequence) return std::unexpected(Sequence.error()); if (!*Sequence) @@ -1193,23 +1159,20 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineMergeLike( } inline Expected<bool> LegalizationArtifactCombiner::tryCombineMergeLike( - MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, + MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { if (!GMergeLikeInstr::classof(&Instruction)) return false; ArtifactValueFinder Finder(*this); - return Finder.tryCombineMergeLike( - castGenericMachineInstr<GMergeLikeInstr>(Instruction), DeadInstructions, - UpdatedDefs, Observer); + return Finder.tryCombineMergeLike(castGenericMachineInstr<GMergeLikeInstr>(Instruction), + DeadInstructions, UpdatedDefs, Observer); } -inline Expected<bool> LegalizationArtifactCombiner::tryFoldUnmergeCast( - MachineInstr &Instruction, MachineInstr &Cast, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs) { - if (!isArtifactCast(Cast.opcode()) || - Cast.opcode() != opcode(GenericOpcode::G_TRUNC)) +inline Expected<bool> +LegalizationArtifactCombiner::tryFoldUnmergeCast(MachineInstr &Instruction, MachineInstr &Cast, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs) { + if (!isArtifactCast(Cast.opcode()) || Cast.opcode() != opcode(GenericOpcode::G_TRUNC)) return false; const auto CastSource = registerOperand(Cast, 1); if (!CastSource) @@ -1227,20 +1190,16 @@ inline Expected<bool> LegalizationArtifactCombiner::tryFoldUnmergeCast( if (!DestinationType) return std::unexpected(DestinationType.error()); if (DestinationType->isVector() || !CastSourceType->isCategoryNeutralScalar() || - CastSourceType->minimumBitWidth() % - DestinationType->minimumBitWidth() != - 0) + CastSourceType->minimumBitWidth() % DestinationType->minimumBitWidth() != 0) return false; - auto Unsupported = isInstUnsupported(LegalizationQuery( - opcode(GenericOpcode::G_UNMERGE_VALUES), - {*DestinationType, *CastSourceType})); + auto Unsupported = isInstUnsupported(LegalizationQuery(opcode(GenericOpcode::G_UNMERGE_VALUES), + {*DestinationType, *CastSourceType})); if (!Unsupported) return std::unexpected(Unsupported.error()); if (*Unsupported) return false; - const std::size_t NewDefCount = static_cast<std::size_t>( - CastSourceType->minimumBitWidth() / - DestinationType->minimumBitWidth()); + const std::size_t NewDefCount = static_cast<std::size_t>(CastSourceType->minimumBitWidth() / + DestinationType->minimumBitWidth()); std::vector<Register> Destinations; Destinations.reserve(NewDefCount); for (std::size_t Index = 0; Index < NewDefCount; ++Index) { @@ -1262,15 +1221,13 @@ inline Expected<bool> LegalizationArtifactCombiner::tryFoldUnmergeCast( if (!Built) return std::unexpected(Built.error()); UpdatedDefs.insert(UpdatedDefs.end(), Destinations.begin(), - Destinations.begin() + - static_cast<std::ptrdiff_t>(OriginalDefCount)); + Destinations.begin() + static_cast<std::ptrdiff_t>(OriginalDefCount)); markInstAndDefDead(Instruction, Cast, DeadInstructions); return true; } inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( - MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, + MachineInstr &Instruction, std::vector<MachineInstr *> &DeadInstructions, std::vector<Register> &UpdatedDefs, GISelObserverWrapper &Observer) { if (!GUnmerge::classof(&Instruction)) return false; @@ -1284,8 +1241,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( MachineInstr *SourceDefinition = Definition->first; if (SourceDefinition == nullptr) return false; - const std::size_t SourceDefIndex = getDefIndex(*SourceDefinition, - Definition->second); + const std::size_t SourceDefIndex = getDefIndex(*SourceDefinition, Definition->second); auto OperandType = MRI.getType(Source); if (!OperandType) return std::unexpected(OperandType.error()); @@ -1296,13 +1252,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( return std::unexpected(Point.error()); ArtifactValueFinder Finder(*this); - auto AllCombined = Finder.tryCombineUnmergeDefs(Unmerge, Observer, - UpdatedDefs); + auto AllCombined = Finder.tryCombineUnmergeDefs(Unmerge, Observer, UpdatedDefs); if (!AllCombined) return std::unexpected(AllCombined.error()); if (*AllCombined) { - markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions, - SourceDefIndex); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions, SourceDefIndex); return true; } @@ -1319,14 +1273,12 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( if (BaseIndex + Unmerge.getNumDefs() > NewUnmerge->size()) return false; for (std::size_t Index = 0; Index < Unmerge.getNumDefs(); ++Index) { - auto Replaced = replaceRegOrBuildCopy( - Unmerge.getReg(Index), (*NewUnmerge)[BaseIndex + Index], UpdatedDefs, - Observer); + auto Replaced = replaceRegOrBuildCopy(Unmerge.getReg(Index), (*NewUnmerge)[BaseIndex + Index], + UpdatedDefs, Observer); if (!Replaced) return std::unexpected(Replaced.error()); } - markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions, - SourceDefIndex); + markInstAndDefDead(Instruction, *SourceDefinition, DeadInstructions, SourceDefIndex); return true; } @@ -1343,10 +1295,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( Merge = CastDefinition->first; } if (Merge == nullptr || - !canFoldMergeOpcode(Merge->opcode(), ConvertOpcode, *OperandType, - *DestinationType)) - return tryFoldUnmergeCast(Instruction, *SourceDefinition, - DeadInstructions, UpdatedDefs); + !canFoldMergeOpcode(Merge->opcode(), ConvertOpcode, *OperandType, *DestinationType)) + return tryFoldUnmergeCast(Instruction, *SourceDefinition, DeadInstructions, UpdatedDefs); const std::size_t MergeSourceCount = Merge->operandCount() - 1; const std::size_t DefCount = Unmerge.getNumDefs(); @@ -1354,13 +1304,11 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( if (DefCount % MergeSourceCount != 0) return false; const std::size_t NewDefCount = DefCount / MergeSourceCount; - for (std::size_t SourceIndex = 0; SourceIndex < MergeSourceCount; - ++SourceIndex) { + for (std::size_t SourceIndex = 0; SourceIndex < MergeSourceCount; ++SourceIndex) { std::vector<Register> Destinations; Destinations.reserve(NewDefCount); for (std::size_t Index = 0; Index < NewDefCount; ++Index) - Destinations.push_back( - Unmerge.getReg(SourceIndex * NewDefCount + Index)); + Destinations.push_back(Unmerge.getReg(SourceIndex * NewDefCount + Index)); Register SplitSource = *registerOperand(*Merge, SourceIndex + 1); if (ConvertOpcode) { auto ConvertedType = divideType(*OperandType, MergeSourceCount); @@ -1369,9 +1317,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( auto Converted = MRI.createVirtualRegister(*ConvertedType); if (!Converted) return std::unexpected(Converted.error()); - auto Built = buildUnary( - static_cast<GenericOpcode>(ConvertOpcode->value()), *Converted, - SplitSource); + auto Built = + buildUnary(static_cast<GenericOpcode>(ConvertOpcode->value()), *Converted, SplitSource); if (!Built) return std::unexpected(Built.error()); SplitSource = *Converted; @@ -1379,8 +1326,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( auto Built = Builder.buildUnmergeValues(Destinations, SplitSource); if (!Built) return std::unexpected(Built.error()); - UpdatedDefs.insert(UpdatedDefs.end(), Destinations.begin(), - Destinations.end()); + UpdatedDefs.insert(UpdatedDefs.end(), Destinations.begin(), Destinations.end()); } } else if (MergeSourceCount > DefCount) { if (ConvertOpcode || MergeSourceCount % DefCount != 0) @@ -1390,8 +1336,7 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( std::vector<Register> Sources; Sources.reserve(SourcesPerDef); for (std::size_t Index = 0; Index < SourcesPerDef; ++Index) { - const auto SourceReg = registerOperand( - *Merge, 1 + DefIndex * SourcesPerDef + Index); + const auto SourceReg = registerOperand(*Merge, 1 + DefIndex * SourcesPerDef + Index); if (!SourceReg) return false; Sources.push_back(*SourceReg); @@ -1422,16 +1367,15 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( return false; if (ConvertOpcode) { if (!MRI.useEmpty(Unmerge.getReg(Index))) { - auto Built = buildUnary( - static_cast<GenericOpcode>(ConvertOpcode->value()), - Unmerge.getReg(Index), *MergeSource); + auto Built = buildUnary(static_cast<GenericOpcode>(ConvertOpcode->value()), + Unmerge.getReg(Index), *MergeSource); if (!Built) return std::unexpected(Built.error()); UpdatedDefs.push_back(Unmerge.getReg(Index)); } } else { - auto Replaced = replaceRegOrBuildCopy( - Unmerge.getReg(Index), *MergeSource, UpdatedDefs, Observer); + auto Replaced = + replaceRegOrBuildCopy(Unmerge.getReg(Index), *MergeSource, UpdatedDefs, Observer); if (!Replaced) return std::unexpected(Replaced.error()); } @@ -1441,10 +1385,10 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineUnmergeValues( return true; } -inline Expected<bool> LegalizationArtifactCombiner::tryCombineExtract( - MachineInstr &Instruction, - std::vector<MachineInstr *> &DeadInstructions, - std::vector<Register> &UpdatedDefs) { +inline Expected<bool> +LegalizationArtifactCombiner::tryCombineExtract(MachineInstr &Instruction, + std::vector<MachineInstr *> &DeadInstructions, + std::vector<Register> &UpdatedDefs) { const auto Destination = registerOperand(Instruction, 0); const auto OriginalSource = registerOperand(Instruction, 1); const auto OffsetValue = immediateOperand(Instruction, 2); @@ -1475,21 +1419,18 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineExtract( const std::size_t SourceCount = Merge->operandCount() - 1; if (SourceCount == 0) return false; - const std::uint64_t MergeSourceSize = - SourceType->minimumBitWidth() / SourceCount; + const std::uint64_t MergeSourceSize = SourceType->minimumBitWidth() / SourceCount; const std::uint64_t Offset = static_cast<std::uint64_t>(*OffsetValue); - const std::size_t FirstSource = - static_cast<std::size_t>(Offset / MergeSourceSize); - const std::size_t LastSource = static_cast<std::size_t>( - (Offset + DestinationType->minimumBitWidth() - 1) / MergeSourceSize); + const std::size_t FirstSource = static_cast<std::size_t>(Offset / MergeSourceSize); + const std::size_t LastSource = + static_cast<std::size_t>((Offset + DestinationType->minimumBitWidth() - 1) / MergeSourceSize); if (FirstSource != LastSource || FirstSource >= SourceCount) return false; const auto MergeSource = registerOperand(*Merge, FirstSource + 1); if (!MergeSource) return false; - auto Built = Builder.buildExtract( - *Destination, *MergeSource, - Offset - FirstSource * MergeSourceSize); + auto Built = + Builder.buildExtract(*Destination, *MergeSource, Offset - FirstSource * MergeSourceSize); if (!Built) return std::unexpected(Built.error()); UpdatedDefs.push_back(*Destination); @@ -1497,10 +1438,8 @@ inline Expected<bool> LegalizationArtifactCombiner::tryCombineExtract( return true; } -inline Expected<Register> -LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDef( - Register DefReg, std::uint64_t StartBit, std::uint64_t Size, - LowLevelType DestinationType) { +inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDef( + Register DefReg, std::uint64_t StartBit, std::uint64_t Size, LowLevelType DestinationType) { CurrentBest = {}; Visited.clear(); auto Found = findValueFromDefImpl(DefReg, StartBit, Size, DestinationType); @@ -1509,8 +1448,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDef( return *Found == DefReg ? Register{} : *Found; } -inline Expected<Register> -LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromConcat( +inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromConcat( GConcatVectors &Instruction, std::uint64_t StartBit, std::uint64_t Size, LowLevelType DestinationType) { if (Instruction.getNumSources() == 0) @@ -1524,8 +1462,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromConcat( return CurrentBest; const std::size_t SourceIndex = static_cast<std::size_t>(StartBit / SourceSize); const std::uint64_t SourceOffset = StartBit % SourceSize; - if (SourceIndex >= Instruction.getNumSources() || - SourceOffset + Size > SourceSize) + if (SourceIndex >= Instruction.getNumSources() || SourceOffset + Size > SourceSize) return CurrentBest; const Register Source = Instruction.getSourceReg(SourceIndex); if (SourceOffset == 0 && Size == SourceSize) @@ -1543,8 +1480,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromBuildVector( if (!FirstType) return std::unexpected(FirstType.error()); const std::uint64_t SourceSize = FirstType->minimumBitWidth(); - if (SourceSize == 0 || StartBit % SourceSize != 0 || Size < SourceSize || - Size % SourceSize != 0) + if (SourceSize == 0 || StartBit % SourceSize != 0 || Size < SourceSize || Size % SourceSize != 0) return CurrentBest; const std::size_t FirstIndex = static_cast<std::size_t>(StartBit / SourceSize); const std::size_t SourceCount = static_cast<std::size_t>(Size / SourceSize); @@ -1558,8 +1494,8 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromBuildVector( auto VectorType = LowLevelType::makeFixedVector(SourceCount, *FirstType); if (!VectorType) return std::unexpected(VectorType.error()); - auto Legal = Combiner.isInstLegal(LegalizationQuery( - opcode(GenericOpcode::G_BUILD_VECTOR), {*VectorType, *FirstType})); + auto Legal = Combiner.isInstLegal( + LegalizationQuery(opcode(GenericOpcode::G_BUILD_VECTOR), {*VectorType, *FirstType})); if (!Legal) return std::unexpected(Legal.error()); if (!*Legal) @@ -1567,8 +1503,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromBuildVector( std::vector<Register> Sources; Sources.reserve(SourceCount); - for (std::size_t Index = FirstIndex; Index < FirstIndex + SourceCount; - ++Index) + for (std::size_t Index = FirstIndex; Index < FirstIndex + SourceCount; ++Index) Sources.push_back(Instruction.getSourceReg(Index)); auto Destination = Combiner.MRI.createVirtualRegister(*VectorType); if (!Destination) @@ -1579,8 +1514,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromBuildVector( return *Destination; } -inline Expected<Register> -LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromInsert( +inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromInsert( MachineInstr &Instruction, std::uint64_t StartBit, std::uint64_t Size, LowLevelType DestinationType) { const auto Container = registerOperand(Instruction, 1); @@ -1605,8 +1539,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromInsert( return Register{}; } -inline Expected<Register> -LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromExtension( +inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromExtension( MachineInstr &Instruction, std::uint64_t StartBit, std::uint64_t Size, LowLevelType DestinationType) { const auto Source = registerOperand(Instruction, 1); @@ -1615,16 +1548,14 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromExtension( auto SourceType = Combiner.MRI.getType(*Source); if (!SourceType) return std::unexpected(SourceType.error()); - if (!SourceType->isCategoryNeutralScalar() || - StartBit + Size > SourceType->minimumBitWidth()) + if (!SourceType->isCategoryNeutralScalar() || StartBit + Size > SourceType->minimumBitWidth()) return CurrentBest; if (StartBit == 0 && SourceType->minimumBitWidth() == Size) CurrentBest = *Source; return findValueFromDefImpl(*Source, StartBit, Size, DestinationType); } -inline Expected<Register> -LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromTrunc( +inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromTrunc( MachineInstr &Instruction, std::uint64_t StartBit, std::uint64_t Size, LowLevelType DestinationType) { const auto Source = registerOperand(Instruction, 1); @@ -1638,10 +1569,8 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromTrunc( return findValueFromDefImpl(*Source, StartBit, Size, DestinationType); } -inline Expected<Register> -LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl( - Register DefReg, std::uint64_t StartBit, std::uint64_t Size, - LowLevelType DestinationType) { +inline Expected<Register> LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl( + Register DefReg, std::uint64_t StartBit, std::uint64_t Size, LowLevelType DestinationType) { if (!DefReg.isVirtual() || !Visited.insert(DefReg).second) return CurrentBest; auto Definition = Combiner.definitionIgnoringCopies(DefReg); @@ -1654,21 +1583,18 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl( switch (static_cast<GenericOpcode>(Instruction->opcode().value())) { case GenericOpcode::G_CONCAT_VECTORS: - return findValueFromConcat( - castGenericMachineInstr<GConcatVectors>(*Instruction), StartBit, Size, - DestinationType); + return findValueFromConcat(castGenericMachineInstr<GConcatVectors>(*Instruction), StartBit, + Size, DestinationType); case GenericOpcode::G_UNMERGE_VALUES: { auto DefType = Combiner.MRI.getType(DefReg); if (!DefType) return std::unexpected(DefType.error()); const std::size_t DefIndex = getDefIndex(*Instruction, DefReg); - const auto Source = registerOperand(*Instruction, - Instruction->operandCount() - 1); + const auto Source = registerOperand(*Instruction, Instruction->operandCount() - 1); if (!Source) return CurrentBest; - auto Found = findValueFromDefImpl( - *Source, StartBit + DefIndex * DefType->minimumBitWidth(), Size, - DestinationType); + auto Found = findValueFromDefImpl(*Source, StartBit + DefIndex * DefType->minimumBitWidth(), + Size, DestinationType); if (!Found) return std::unexpected(Found.error()); if (!Found->isNoRegister()) @@ -1678,8 +1604,8 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl( return CurrentBest; } case GenericOpcode::G_BUILD_VECTOR: - return findValueFromBuildVector( - castGenericMachineInstr<GBuildVector>(*Instruction), StartBit, Size); + return findValueFromBuildVector(castGenericMachineInstr<GBuildVector>(*Instruction), StartBit, + Size); case GenericOpcode::G_INSERT: return findValueFromInsert(*Instruction, StartBit, Size, DestinationType); case GenericOpcode::G_TRUNC: @@ -1687,8 +1613,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl( case GenericOpcode::G_SEXT: case GenericOpcode::G_ZEXT: case GenericOpcode::G_ANYEXT: - return findValueFromExtension(*Instruction, StartBit, Size, - DestinationType); + return findValueFromExtension(*Instruction, StartBit, Size, DestinationType); case GenericOpcode::G_IMPLICIT_DEF: { auto Type = Combiner.MRI.getType(DefReg); if (!Type) @@ -1708,10 +1633,8 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findValueFromDefImpl( } } -inline Expected<bool> -LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs( - GUnmerge &Instruction, GISelChangeObserver &Observer, - std::vector<Register> &UpdatedDefs) { +inline Expected<bool> LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs( + GUnmerge &Instruction, GISelChangeObserver &Observer, std::vector<Register> &UpdatedDefs) { if (Instruction.getNumDefs() == 0) return false; auto DestinationType = Combiner.MRI.getType(Instruction.getReg(0)); @@ -1722,8 +1645,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs( const Register Def = Instruction.getReg(Index); if (Combiner.MRI.useEmpty(Def)) continue; - auto Found = findValueFromDef(Def, 0, DestinationType->minimumBitWidth(), - *DestinationType); + auto Found = findValueFromDef(Def, 0, DestinationType->minimumBitWidth(), *DestinationType); if (!Found) return std::unexpected(Found.error()); if (Found->isNoRegister()) { @@ -1737,8 +1659,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::tryCombineUnmergeDefs( AllDead = false; continue; } - auto Replaced = Combiner.replaceRegOrBuildCopy(Def, *Found, UpdatedDefs, - Observer); + auto Replaced = Combiner.replaceRegOrBuildCopy(Def, *Found, UpdatedDefs, Observer); if (!Replaced) return std::unexpected(Replaced.error()); Observer.changingInstr(Instruction); @@ -1772,16 +1693,14 @@ LegalizationArtifactCombiner::ArtifactValueFinder::findUnmergeThatDefinesReg( return &castGenericMachineInstr<GUnmerge>(*Definition->first); } -inline Expected<bool> -LegalizationArtifactCombiner::ArtifactValueFinder::isSequenceFromUnmerge( - GMergeLikeInstr &Instruction, std::size_t MergeStartIndex, - GUnmerge *Unmerge, std::size_t UnmergeStartIndex, - std::size_t ElementCount, std::uint64_t ElementSize, bool AllowUndef) { +inline Expected<bool> LegalizationArtifactCombiner::ArtifactValueFinder::isSequenceFromUnmerge( + GMergeLikeInstr &Instruction, std::size_t MergeStartIndex, GUnmerge *Unmerge, + std::size_t UnmergeStartIndex, std::size_t ElementCount, std::uint64_t ElementSize, + bool AllowUndef) { for (std::size_t Index = 0; Index < ElementCount; ++Index) { const Register Source = Instruction.getSourceReg(MergeStartIndex + Index); std::size_t SourceDefIndex = 0; - auto SourceUnmerge = - findUnmergeThatDefinesReg(Source, ElementSize, SourceDefIndex); + auto SourceUnmerge = findUnmergeThatDefinesReg(Source, ElementSize, SourceDefIndex); if (!SourceUnmerge) return std::unexpected(SourceUnmerge.error()); if (*SourceUnmerge == Unmerge) { @@ -1790,8 +1709,7 @@ LegalizationArtifactCombiner::ArtifactValueFinder::isSequenceFromUnmerge( continue; } MachineInstr *Definition = Combiner.MRI.getVRegDef(Source); - if (!AllowUndef || - !hasOpcode(Definition, GenericOpcode::G_IMPLICIT_DEF)) + if (!AllowUndef || !hasOpcode(Definition, GenericOpcode::G_IMPLICIT_DEF)) return false; } return true; diff --git a/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h b/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h index 9a34898..19b3345 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h +++ b/backend/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h @@ -8,6 +8,8 @@ #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/Support/Error.h" +#include <vector> + namespace rcc { class MachineFunction; @@ -36,7 +38,36 @@ public: std::size_t OperandIndex = 0, GenericOpcode TruncOpcode = GenericOpcode::G_TRUNC); + [[nodiscard]] Expected<void> narrowScalar(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + private: + [[nodiscard]] Expected<void> widenScalarMergeValues(MachineInstr &Instruction, + std::size_t TypeIndex, LowLevelType WideType); + [[nodiscard]] Expected<void> + widenScalarUnmergeValues(MachineInstr &Instruction, std::size_t TypeIndex, LowLevelType WideType); + [[nodiscard]] Expected<void> insertParts(Register Destination, LowLevelType ResultType, + LowLevelType PartType, + const std::vector<Register> &PartRegisters, + LowLevelType LeftoverType = {}, + const std::vector<Register> &LeftoverRegisters = {}); + [[nodiscard]] Expected<void> extractGCDType(std::vector<Register> &Parts, LowLevelType GCDType, + Register Source); + [[nodiscard]] Expected<LowLevelType> extractGCDType(std::vector<Register> &Parts, + LowLevelType DestinationType, + LowLevelType NarrowType, Register Source); + [[nodiscard]] Expected<LowLevelType> + buildLCMMergePieces(LowLevelType DestinationType, LowLevelType NarrowType, LowLevelType GCDType, + std::vector<Register> &Registers, + GenericOpcode PadStrategy = GenericOpcode::G_ANYEXT); + [[nodiscard]] Expected<void> + buildWidenedRemergeToDst(Register Destination, LowLevelType LCMType, + const std::vector<Register> &RemergeRegisters); + [[nodiscard]] Expected<void> narrowScalarAddSub(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + [[nodiscard]] Expected<void> narrowScalarExt(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType); + MachineFunction &Function; MachineRegisterInfo &MRI; const LegalizerInfo &Info; diff --git a/backend/include/rcc/CodeGen/GlobalISel/Utils.h b/backend/include/rcc/CodeGen/GlobalISel/Utils.h new file mode 100644 index 0000000..5af2fb4 --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/Utils.h @@ -0,0 +1,54 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_UTILS_H +#define RCC_CODEGEN_GLOBALISEL_UTILS_H + +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/Support/Error.h" + +#include <cstddef> +#include <span> +#include <vector> + +namespace rcc { + +class MachineIRBuilder; +class MachineInstr; +class MachineRegisterInfo; +class TargetDescription; + +/// Check whether an instruction only defines dead virtual registers and has no +/// observable side effects. +[[nodiscard]] bool isTriviallyDead(const MachineInstr &Instruction, + const MachineRegisterInfo &MRI, + const TargetDescription &Target) noexcept; + +[[nodiscard]] Expected<void> eraseInstrs(std::span<MachineInstr *const> Instructions, + MachineRegisterInfo &MRI, + const TargetDescription &Target); + +[[nodiscard]] Expected<void> eraseInstr(MachineInstr &Instruction, + MachineRegisterInfo &MRI, + const TargetDescription &Target); + +[[nodiscard]] Expected<void> extractParts(Register Reg, LowLevelType Type, + int PartCount, + std::vector<Register> &Parts, + MachineIRBuilder &MIRBuilder, + MachineRegisterInfo &MRI); + +[[nodiscard]] Expected<bool> +extractParts(Register Reg, LowLevelType RegisterType, LowLevelType MainType, + LowLevelType &LeftoverType, std::vector<Register> &Parts, + std::vector<Register> &LeftoverParts, + MachineIRBuilder &MIRBuilder, MachineRegisterInfo &MRI); + +[[nodiscard]] Expected<LowLevelType> getLCMType(LowLevelType OriginalType, + LowLevelType TargetType); +[[nodiscard]] Expected<LowLevelType> getGCDType(LowLevelType OriginalType, + LowLevelType TargetType); + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_UTILS_H diff --git a/backend/include/rcc/CodeGen/MachineIRBuilder.h b/backend/include/rcc/CodeGen/MachineIRBuilder.h index 01cd648..70a313a 100644 --- a/backend/include/rcc/CodeGen/MachineIRBuilder.h +++ b/backend/include/rcc/CodeGen/MachineIRBuilder.h @@ -11,6 +11,7 @@ #include <cstddef> #include <cstdint> +#include <initializer_list> #include <memory> #include <optional> #include <string> @@ -178,17 +179,20 @@ 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 *> 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, Register Source) const; [[nodiscard]] Expected<MachineInstr *> buildSExtOrTrunc(Register Destination, - Register Source) const; + Register Source) const; [[nodiscard]] Expected<MachineInstr *> buildConstant(Register Destination, APInt Value) const; [[nodiscard]] Expected<MachineInstr *> buildConstant(Register Destination, std::int64_t Value) const; @@ -196,23 +200,40 @@ public: std::uint32_t Width) const; [[nodiscard]] Expected<MachineInstr *> buildAnd(Register Destination, Register Left, Register Right) const; - [[nodiscard]] Expected<MachineInstr *> buildMergeValues( - Register Destination, const std::vector<Register> &Sources) const; - [[nodiscard]] Expected<MachineInstr *> buildUnmergeValues( - const std::vector<Register> &Destinations, Register Source) const; + [[nodiscard]] Expected<MachineInstr *> buildOr(Register Destination, Register Left, + Register Right) const; + [[nodiscard]] Expected<MachineInstr *> buildAdd(Register Destination, Register Left, + Register Right) const; + [[nodiscard]] Expected<MachineInstr *> buildSub(Register Destination, Register Left, + Register Right) const; + [[nodiscard]] Expected<MachineInstr *> buildShl(Register 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, + Register Left, Register Right) const; + [[nodiscard]] Expected<MachineInstr *> + buildMergeLikeInstr(Register Destination, const std::vector<Register> &Sources) const; + [[nodiscard]] Expected<MachineInstr *> + buildMergeValues(Register 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; private: - [[nodiscard]] Expected<MachineInstr *> buildUnary(Opcode InstructionOpcode, - Register Destination, + [[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; + [[nodiscard]] Expected<MachineInstr *> buildBinary(Opcode InstructionOpcode, Register Destination, + Register Left, Register Right) const; + [[nodiscard]] Expected<MachineInstr *> + buildExtOrTrunc(Opcode ExtensionOpcode, Register 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; diff --git a/backend/include/rcc/CodeGen/MachineRegisterInfo.h b/backend/include/rcc/CodeGen/MachineRegisterInfo.h index 456115f..d0353b3 100644 --- a/backend/include/rcc/CodeGen/MachineRegisterInfo.h +++ b/backend/include/rcc/CodeGen/MachineRegisterInfo.h @@ -109,6 +109,7 @@ public: [[nodiscard]] Expected<Register> createVirtualRegister(); [[nodiscard]] Expected<Register> createVirtualRegister(LowLevelType Type); + [[nodiscard]] Expected<Register> cloneVirtualRegister(Register Reg); [[nodiscard]] Expected<void> eraseVirtualRegister(Register Reg); [[nodiscard]] bool isKnownVirtualRegister(Register Reg) const noexcept; diff --git a/backend/include/rcc/CodeGen/TargetDescription.h b/backend/include/rcc/CodeGen/TargetDescription.h index 7e41a58..56d328e 100644 --- a/backend/include/rcc/CodeGen/TargetDescription.h +++ b/backend/include/rcc/CodeGen/TargetDescription.h @@ -8,6 +8,7 @@ #include "rcc/CodeGen/TargetRegisterInfo.h" #include "rcc/Support/Error.h" +#include <cstdint> #include <optional> #include <span> #include <utility> @@ -23,6 +24,18 @@ class MachineMemOperand; class MachineRegisterInfo; struct VirtualRegisterInfo; +enum class BooleanContent : std::uint8_t { + Undefined, + ZeroOrOne, + ZeroOrNegativeOne, +}; + +struct TargetBooleanContentInfo final { + BooleanContent ScalarInteger = BooleanContent::Undefined; + BooleanContent ScalarFloatingPoint = BooleanContent::Undefined; + BooleanContent Vector = BooleanContent::Undefined; +}; + class TargetDescription final { public: TargetDescription(const TargetDescription &) = delete; @@ -31,9 +44,9 @@ public: TargetDescription &operator=(TargetDescription &&) noexcept = default; ~TargetDescription() = default; - [[nodiscard]] static Expected<TargetDescription> create(InstructionSet Instructions, - TargetRegisterInfo Registers, - TargetMIRTextInfoDesc MIRText = {}); + [[nodiscard]] static Expected<TargetDescription> + create(InstructionSet Instructions, TargetRegisterInfo Registers, + TargetMIRTextInfoDesc MIRText = {}, TargetBooleanContentInfo BooleanInfo = {}); [[nodiscard]] const InstructionSet &instructions() const noexcept { return Instructions; @@ -47,6 +60,13 @@ public: return MIRText; } + [[nodiscard]] BooleanContent getBooleanContents(bool IsVector, + bool IsFloatingPoint) const noexcept { + if (IsVector) + return BooleanInfo.Vector; + return IsFloatingPoint ? BooleanInfo.ScalarFloatingPoint : BooleanInfo.ScalarInteger; + } + [[nodiscard]] const InstructionDescriptor * instructionDescriptor(Opcode InstructionOpcode) const noexcept { return Instructions.descriptor(InstructionOpcode); @@ -87,9 +107,9 @@ public: private: TargetDescription(InstructionSet Instructions, TargetRegisterInfo Registers, - TargetMIRTextInfo MIRText) + TargetMIRTextInfo MIRText, TargetBooleanContentInfo BooleanInfo) : Instructions(std::move(Instructions)), Registers(std::move(Registers)), - MIRText(std::move(MIRText)) {} + MIRText(std::move(MIRText)), BooleanInfo(BooleanInfo) {} [[nodiscard]] Expected<void> validateTargetOperand(const OperandDescriptor *Descriptor, const MachineOperand &Operand, @@ -101,6 +121,7 @@ private: InstructionSet Instructions; TargetRegisterInfo Registers; TargetMIRTextInfo MIRText; + TargetBooleanContentInfo BooleanInfo; }; } // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt index b7064e3..3b01e9b 100644 --- a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt +++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt @@ -3,16 +3,19 @@ set( RCCBackendGlobalISelSources GISelChangeObserver.cpp + GISelValueTracking.cpp InstructionSelect.cpp Legalizer.cpp LegalizerHelper.cpp LegalizerInfo.cpp RegBankSelect.cpp + Utils.cpp ) set( RCCBackendGlobalISelHeaders "${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" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GenericMachineInstrs.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/InstructionSelect.h" @@ -22,25 +25,30 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerHelper.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/LegalizerInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/RegBankSelect.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/Utils.h" ) target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources}) rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/Utils.cpp" ${RCCBackendGlobalISelHeaders} ) rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/Legalizer.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerHelper.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/LegalizerInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegBankSelect.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/Utils.cpp" ) diff --git a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp new file mode 100644 index 0000000..fe694ab --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp @@ -0,0 +1,514 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <optional> +#include <vector> + +namespace rcc { +namespace { + +[[nodiscard]] std::optional<Register> registerOperand(const MachineInstr &Instruction, + std::size_t Index) noexcept { + const MachineOperand *Operand = Instruction.operandAt(Index); + return Operand == nullptr ? std::nullopt : Operand->registerValue(); +} + +[[nodiscard]] Expected<APInt> zero(std::uint32_t BitWidth) { + return APInt::fromUnsigned(BitWidth, 0); +} + +[[nodiscard]] Expected<APInt> resizeMask(const APInt &Value, std::uint32_t BitWidth) { + if (Value.bitWidth() == BitWidth) + return Value; + if (Value.bitWidth() == 0) + return zero(BitWidth); + if (Value.bitWidth() < BitWidth) + return Value.zext(BitWidth); + return Value.trunc(BitWidth); +} + +[[nodiscard]] Expected<APInt> highBitsMask(std::uint32_t BitWidth, std::uint32_t LowBitCount) { + auto LowBits = APInt::getLowBitsSet(BitWidth, LowBitCount); + if (!LowBits) + return std::unexpected(LowBits.error()); + return LowBits->bitwiseNot(); +} + +[[nodiscard]] Expected<APInt> mergeMasks(const APInt &Left, const APInt &Right) { + return Left.bitwiseOr(Right); +} + +[[nodiscard]] Expected<APInt> intersectMasks(const APInt &Left, const APInt &Right) { + return Left.bitwiseAnd(Right); +} + +[[nodiscard]] Expected<APInt> constantAtWidth(const APInt &Value, std::uint32_t BitWidth) { + return resizeMask(Value, BitWidth); +} + +[[nodiscard]] std::optional<std::uint32_t> +constantShiftAmount(Register Reg, const MachineRegisterInfo &MRI, std::uint32_t BitWidth) { + const MachineInstr *Definition = MRI.getVRegDef(Reg); + if (Definition == nullptr || Definition->opcode() != opcode(GenericOpcode::G_CONSTANT)) + return std::nullopt; + const MachineOperand *ValueOperand = Definition->operandAt(1); + const auto *Immediate = + ValueOperand == nullptr ? nullptr : ValueOperand->getIf<IntegerImmediateOperand>(); + if (Immediate == nullptr || Immediate->Value.activeBitWidth() > 32) + return std::nullopt; + const std::uint64_t Amount = Immediate->Value.word(0); + if (Amount >= BitWidth) + return std::nullopt; + return static_cast<std::uint32_t>(Amount); +} + +[[nodiscard]] Expected<APInt> shiftMaskLeft(const APInt &Value, std::uint32_t Amount) { + std::vector<std::uint64_t> Words(Value.words().size(), 0); + for (std::uint32_t Bit = 0; Bit + Amount < Value.bitWidth(); ++Bit) { + if (Value.testBit(Bit)) { + const std::uint32_t DestinationBit = Bit + Amount; + Words[DestinationBit / 64U] |= std::uint64_t{1} << (DestinationBit % 64U); + } + } + return APInt::create(Value.bitWidth(), Words); +} + +[[nodiscard]] Expected<APInt> shiftMaskRight(const APInt &Value, std::uint32_t Amount) { + std::vector<std::uint64_t> Words(Value.words().size(), 0); + for (std::uint32_t Bit = Amount; Bit < Value.bitWidth(); ++Bit) { + if (Value.testBit(Bit)) { + const std::uint32_t DestinationBit = Bit - Amount; + Words[DestinationBit / 64U] |= std::uint64_t{1} << (DestinationBit % 64U); + } + } + return APInt::create(Value.bitWidth(), Words); +} + +[[nodiscard]] std::uint32_t constantNumSignBits(const APInt &Value) noexcept { + if (Value.bitWidth() == 0) + return 1; + if (Value.isNegative()) + return static_cast<std::uint32_t>(Value.countlOne()); + auto Inverted = Value.bitwiseNot(); + return Inverted ? static_cast<std::uint32_t>(Inverted->countlOne()) : 1U; +} + +} // namespace + +GISelValueTracking::GISelValueTracking(MachineFunction &Function, const TargetDescription &Target, + unsigned MaxDepth) noexcept + : Function(Function), MRI(Function.registerInfo()), Target(Target), MaxDepth(MaxDepth) {} + +Expected<GISelValueTracking::KnownBits> +GISelValueTracking::makeUnknown(std::uint32_t BitWidth) const { + auto Zero = zero(BitWidth); + if (!Zero) + return std::unexpected(Zero.error()); + auto One = zero(BitWidth); + if (!One) + return std::unexpected(One.error()); + return KnownBits{.Zero = std::move(*Zero), .One = std::move(*One)}; +} + +Expected<GISelValueTracking::KnownBits> GISelValueTracking::getKnownBits(Register Reg, + unsigned Depth) const { + auto Type = MRI.getType(Reg); + if (!Type) + return std::unexpected(Type.error()); + const std::uint32_t BitWidth = Type->scalarBitWidth(); + auto Unknown = makeUnknown(BitWidth); + if (!Unknown) + return std::unexpected(Unknown.error()); + if (Depth >= MaxDepth) + return Unknown; + + const MachineInstr *Definition = MRI.getVRegDef(Reg); + if (Definition == nullptr) + return Unknown; + + const auto Opcode = static_cast<GenericOpcode>(Definition->opcode().value()); + if (Opcode == GenericOpcode::G_CONSTANT) { + const MachineOperand *ValueOperand = Definition->operandAt(1); + const auto *Immediate = + ValueOperand == nullptr ? nullptr : ValueOperand->getIf<IntegerImmediateOperand>(); + if (Immediate == nullptr) + return Unknown; + auto Value = constantAtWidth(Immediate->Value, BitWidth); + if (!Value) + return std::unexpected(Value.error()); + auto KnownZero = Value->bitwiseNot(); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*Value)}; + } + + if (Opcode == GenericOpcode::COPY) { + const auto Source = registerOperand(*Definition, 1); + if (!Source || !Source->isVirtual()) + return Unknown; + auto SourceBits = getKnownBits(*Source, Depth); + if (!SourceBits) + return std::unexpected(SourceBits.error()); + auto KnownZero = resizeMask(SourceBits->Zero, BitWidth); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = resizeMask(SourceBits->One, BitWidth); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + + if (Opcode == GenericOpcode::G_ICMP || Opcode == GenericOpcode::G_FCMP) { + if (!Type->isVector() && BitWidth > 1 && + Target.getBooleanContents(false, Opcode == GenericOpcode::G_FCMP) == + BooleanContent::ZeroOrOne) { + auto KnownZero = highBitsMask(BitWidth, 1); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + Unknown->Zero = std::move(*KnownZero); + } + return Unknown; + } + + switch (Opcode) { + case GenericOpcode::G_UADDO: + case GenericOpcode::G_UADDE: + case GenericOpcode::G_USUBO: + case GenericOpcode::G_USUBE: + case GenericOpcode::G_SADDO: + case GenericOpcode::G_SADDE: + case GenericOpcode::G_SSUBO: + case GenericOpcode::G_SSUBE: + case GenericOpcode::G_UMULO: + case GenericOpcode::G_SMULO: { + const auto BooleanResult = registerOperand(*Definition, 1); + if (BooleanResult && *BooleanResult == Reg && !Type->isVector() && BitWidth > 1 && + Target.getBooleanContents(false, false) == BooleanContent::ZeroOrOne) { + auto KnownZero = highBitsMask(BitWidth, 1); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + Unknown->Zero = std::move(*KnownZero); + } + return Unknown; + } + default: + break; + } + + const auto Source = registerOperand(*Definition, 1); + if (!Source) + return Unknown; + + if (Opcode == GenericOpcode::G_TRUNC || Opcode == GenericOpcode::G_ANYEXT || + Opcode == GenericOpcode::G_ZEXT || Opcode == GenericOpcode::G_SEXT || + Opcode == GenericOpcode::G_ASSERT_ZEXT || Opcode == GenericOpcode::G_ASSERT_SEXT || + Opcode == GenericOpcode::G_SEXT_INREG) { + auto SourceBits = getKnownBits(*Source, Depth + 1U); + if (!SourceBits) + return std::unexpected(SourceBits.error()); + auto SourceType = MRI.getType(*Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + const std::uint32_t SourceWidth = SourceType->scalarBitWidth(); + auto KnownZero = resizeMask(SourceBits->Zero, BitWidth); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = resizeMask(SourceBits->One, BitWidth); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + + if (Opcode == GenericOpcode::G_ZEXT && SourceWidth < BitWidth) { + auto HighZero = highBitsMask(BitWidth, SourceWidth); + if (!HighZero) + return std::unexpected(HighZero.error()); + KnownZero = mergeMasks(*KnownZero, *HighZero); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + } + + std::uint32_t ExtendedFrom = SourceWidth; + if (Opcode == GenericOpcode::G_ASSERT_ZEXT || Opcode == GenericOpcode::G_ASSERT_SEXT || + Opcode == GenericOpcode::G_SEXT_INREG) { + const MachineOperand *WidthOperand = Definition->operandAt(2); + const auto *Width = WidthOperand == nullptr ? nullptr : WidthOperand->getIf<std::int64_t>(); + if (Width == nullptr || *Width <= 0 || static_cast<std::uint64_t>(*Width) > BitWidth) + return Unknown; + ExtendedFrom = static_cast<std::uint32_t>(*Width); + } + + if (Opcode == GenericOpcode::G_ASSERT_ZEXT) { + auto HighZero = highBitsMask(BitWidth, ExtendedFrom); + if (!HighZero) + return std::unexpected(HighZero.error()); + KnownZero = mergeMasks(*KnownZero, *HighZero); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + } + + if ((Opcode == GenericOpcode::G_SEXT || Opcode == GenericOpcode::G_ASSERT_SEXT || + Opcode == GenericOpcode::G_SEXT_INREG) && + ExtendedFrom < BitWidth) { + auto HighBits = highBitsMask(BitWidth, ExtendedFrom); + if (!HighBits) + return std::unexpected(HighBits.error()); + if (KnownZero->testBit(ExtendedFrom - 1U)) { + KnownZero = mergeMasks(*KnownZero, *HighBits); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + } else if (KnownOne->testBit(ExtendedFrom - 1U)) { + KnownOne = mergeMasks(*KnownOne, *HighBits); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + } + } + + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + + if (Opcode == GenericOpcode::G_AND || Opcode == GenericOpcode::G_OR || + Opcode == GenericOpcode::G_XOR) { + const auto Right = registerOperand(*Definition, 2); + if (!Right) + return Unknown; + auto LeftBits = getKnownBits(*Source, Depth + 1U); + if (!LeftBits) + return std::unexpected(LeftBits.error()); + auto RightBits = getKnownBits(*Right, Depth + 1U); + if (!RightBits) + return std::unexpected(RightBits.error()); + + if (Opcode == GenericOpcode::G_AND) { + auto KnownZero = mergeMasks(LeftBits->Zero, RightBits->Zero); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = intersectMasks(LeftBits->One, RightBits->One); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + if (Opcode == GenericOpcode::G_OR) { + auto KnownZero = intersectMasks(LeftBits->Zero, RightBits->Zero); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = mergeMasks(LeftBits->One, RightBits->One); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + + auto BothZero = intersectMasks(LeftBits->Zero, RightBits->Zero); + if (!BothZero) + return std::unexpected(BothZero.error()); + auto BothOne = intersectMasks(LeftBits->One, RightBits->One); + if (!BothOne) + return std::unexpected(BothOne.error()); + auto KnownZero = mergeMasks(*BothZero, *BothOne); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto LeftZeroRightOne = intersectMasks(LeftBits->Zero, RightBits->One); + if (!LeftZeroRightOne) + return std::unexpected(LeftZeroRightOne.error()); + auto LeftOneRightZero = intersectMasks(LeftBits->One, RightBits->Zero); + if (!LeftOneRightZero) + return std::unexpected(LeftOneRightZero.error()); + auto KnownOne = mergeMasks(*LeftZeroRightOne, *LeftOneRightZero); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + + if (Opcode == GenericOpcode::G_SHL || Opcode == GenericOpcode::G_LSHR || + Opcode == GenericOpcode::G_ASHR) { + const auto AmountReg = registerOperand(*Definition, 2); + if (!AmountReg) + return Unknown; + const auto Amount = constantShiftAmount(*AmountReg, MRI, BitWidth); + if (!Amount) + return Unknown; + auto SourceBits = getKnownBits(*Source, Depth + 1U); + if (!SourceBits) + return std::unexpected(SourceBits.error()); + + if (Opcode == GenericOpcode::G_SHL) { + auto KnownZero = shiftMaskLeft(SourceBits->Zero, *Amount); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto LowZero = APInt::getLowBitsSet(BitWidth, *Amount); + if (!LowZero) + return std::unexpected(LowZero.error()); + KnownZero = mergeMasks(*KnownZero, *LowZero); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = shiftMaskLeft(SourceBits->One, *Amount); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + + auto KnownZero = shiftMaskRight(SourceBits->Zero, *Amount); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = shiftMaskRight(SourceBits->One, *Amount); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + auto HighBits = highBitsMask(BitWidth, BitWidth - *Amount); + if (!HighBits) + return std::unexpected(HighBits.error()); + if (Opcode == GenericOpcode::G_LSHR || SourceBits->Zero.testBit(BitWidth - 1U)) { + KnownZero = mergeMasks(*KnownZero, *HighBits); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + } else if (SourceBits->One.testBit(BitWidth - 1U)) { + KnownOne = mergeMasks(*KnownOne, *HighBits); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + } + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + + return Unknown; +} + +Expected<APInt> GISelValueTracking::getKnownZeroes(Register Reg) const { + auto Known = getKnownBits(Reg); + if (!Known) + return std::unexpected(Known.error()); + return std::move(Known->Zero); +} + +Expected<std::uint32_t> GISelValueTracking::computeNumSignBits(Register Reg, unsigned Depth) const { + auto Type = MRI.getType(Reg); + if (!Type) + return std::unexpected(Type.error()); + const std::uint32_t BitWidth = Type->scalarBitWidth(); + if (Depth >= MaxDepth) + return 1U; + + const MachineInstr *Definition = MRI.getVRegDef(Reg); + if (Definition == nullptr) + return 1U; + const auto Opcode = static_cast<GenericOpcode>(Definition->opcode().value()); + + if (Opcode == GenericOpcode::G_CONSTANT) { + const MachineOperand *ValueOperand = Definition->operandAt(1); + const auto *Immediate = + ValueOperand == nullptr ? nullptr : ValueOperand->getIf<IntegerImmediateOperand>(); + if (Immediate == nullptr) + return 1U; + auto Value = constantAtWidth(Immediate->Value, BitWidth); + if (!Value) + return std::unexpected(Value.error()); + return constantNumSignBits(*Value); + } + + const auto Source = registerOperand(*Definition, 1); + if (Opcode == GenericOpcode::COPY && Source && Source->isVirtual()) + return computeNumSignBits(*Source, Depth); + + if (Opcode == GenericOpcode::G_SEXT && Source) { + auto SourceType = MRI.getType(*Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U); + if (!SourceSignBits) + return std::unexpected(SourceSignBits.error()); + return std::min(BitWidth, *SourceSignBits + BitWidth - SourceType->scalarBitWidth()); + } + + if ((Opcode == GenericOpcode::G_ASSERT_SEXT || Opcode == GenericOpcode::G_SEXT_INREG) && Source) { + const MachineOperand *WidthOperand = Definition->operandAt(2); + const auto *Width = WidthOperand == nullptr ? nullptr : WidthOperand->getIf<std::int64_t>(); + if (Width != nullptr && *Width > 0 && static_cast<std::uint64_t>(*Width) <= BitWidth) { + auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U); + if (!SourceSignBits) + return std::unexpected(SourceSignBits.error()); + return std::max(*SourceSignBits, BitWidth - static_cast<std::uint32_t>(*Width) + 1U); + } + } + + if ((Opcode == GenericOpcode::G_AND || Opcode == GenericOpcode::G_OR || + Opcode == GenericOpcode::G_XOR) && + Source) { + const auto Right = registerOperand(*Definition, 2); + if (Right) { + auto LeftSignBits = computeNumSignBits(*Source, Depth + 1U); + if (!LeftSignBits) + return std::unexpected(LeftSignBits.error()); + if (*LeftSignBits != 1) { + auto RightSignBits = computeNumSignBits(*Right, Depth + 1U); + if (!RightSignBits) + return std::unexpected(RightSignBits.error()); + if (*RightSignBits != 1) + return std::min(*LeftSignBits, *RightSignBits); + } + } + } + + if (Opcode == GenericOpcode::G_TRUNC && Source) { + auto SourceType = MRI.getType(*Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + const std::uint32_t SourceWidth = SourceType->scalarBitWidth(); + auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U); + if (!SourceSignBits) + return std::unexpected(SourceSignBits.error()); + if (SourceWidth > BitWidth && *SourceSignBits > SourceWidth - BitWidth) + return *SourceSignBits - (SourceWidth - BitWidth); + } + + if (Opcode == GenericOpcode::G_ICMP || Opcode == GenericOpcode::G_FCMP) { + if (BitWidth > 1) { + const BooleanContent Contents = + Target.getBooleanContents(Type->isVector(), Opcode == GenericOpcode::G_FCMP); + if (Contents == BooleanContent::ZeroOrNegativeOne) + return BitWidth; + if (Contents == BooleanContent::ZeroOrOne) + return BitWidth - 1U; + } + } + + switch (Opcode) { + case GenericOpcode::G_UADDO: + case GenericOpcode::G_UADDE: + case GenericOpcode::G_USUBO: + case GenericOpcode::G_USUBE: + case GenericOpcode::G_SADDO: + case GenericOpcode::G_SADDE: + case GenericOpcode::G_SSUBO: + case GenericOpcode::G_SSUBE: + case GenericOpcode::G_UMULO: + case GenericOpcode::G_SMULO: { + const auto BooleanResult = registerOperand(*Definition, 1); + if (BooleanResult && *BooleanResult == Reg && + Target.getBooleanContents(Type->isVector(), false) == BooleanContent::ZeroOrNegativeOne) + return BitWidth; + break; + } + default: + break; + } + + auto Known = getKnownBits(Reg, Depth); + if (!Known) + return std::unexpected(Known.error()); + std::uint32_t KnownSignBits = 1; + if (Known->Zero.testBit(BitWidth - 1U)) + KnownSignBits = static_cast<std::uint32_t>(Known->Zero.countlOne()); + else if (Known->One.testBit(BitWidth - 1U)) + KnownSignBits = static_cast<std::uint32_t>(Known->One.countlOne()); + return std::max(1U, KnownSignBits); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp index d971b42..c749039 100644 --- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp +++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp @@ -4,9 +4,11 @@ #include "rcc/CodeGen/GenericOpcodes.h" #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/GlobalISel/GISelValueTracking.h" #include "rcc/CodeGen/GlobalISel/GISelWorkList.h" #include "rcc/CodeGen/GlobalISel/LegalizationArtifactCombiner.h" #include "rcc/CodeGen/GlobalISel/LegalizerHelper.h" +#include "rcc/CodeGen/GlobalISel/Utils.h" #include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" @@ -295,7 +297,9 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi MachineFunctionDelegateInstaller ObserverInstaller(Function, Observer); MachineIRBuilder Builder(Function, Target); LegalizerHelper Helper(Function, *Info, Observer, Builder); - LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info); + GISelValueTracking ValueTracking(Function, Target); + LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info, + &ValueTracking); do { while (!InstructionWorklist.empty()) { @@ -303,6 +307,15 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi if (Instruction == nullptr || Instruction->parent() == nullptr) continue; + if (isTriviallyDead(*Instruction, Function.registerInfo(), Target)) { + auto Removed = eraseInstr(*Instruction, Function.registerInfo(), Target); + if (!Removed) + return std::unexpected(Removed.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + continue; + } + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); if (Descriptor == nullptr) return std::unexpected( @@ -381,19 +394,23 @@ Expected<MachinePassResult> Legalizer::runImplementation(MachineFunction &Functi MachineInstr *Instruction = ArtifactWorklist.popBack(); if (Instruction == nullptr || Instruction->parent() == nullptr) continue; + if (isTriviallyDead(*Instruction, Function.registerInfo(), Target)) { + auto Removed = eraseInstr(*Instruction, Function.registerInfo(), Target); + if (!Removed) + return std::unexpected(Removed.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + continue; + } std::vector<MachineInstr *> DeadInstructions; auto Combined = ArtifactCombiner.tryCombineInstruction(*Instruction, DeadInstructions, Observer); if (!Combined) return std::unexpected(Combined.error()); if (*Combined) { - for (MachineInstr *Dead : DeadInstructions) { - if (Dead == nullptr || Dead->parent() == nullptr) - continue; - auto Removed = Dead->parent()->removeInstruction(*Dead); - if (!Removed) - return std::unexpected(Removed.error()); - } + auto Removed = eraseInstrs(DeadInstructions, Function.registerInfo(), Target); + if (!Removed) + return std::unexpected(Removed.error()); Result.Changed = true; Result.Changes.add(MachinePassChange::Instructions); continue; diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp index 1e52214..0ea3783 100644 --- a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp +++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp @@ -3,6 +3,7 @@ #include "rcc/CodeGen/GlobalISel/LegalizerHelper.h" #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" +#include "rcc/CodeGen/GlobalISel/Utils.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" @@ -14,7 +15,9 @@ #include <bit> #include <cstddef> #include <cstdint> +#include <numeric> #include <optional> +#include <span> #include <utility> namespace rcc { @@ -113,6 +116,539 @@ LegalizerHelper::LegalizerHelper(MachineFunction &Function, const LegalizerInfo : MIRBuilder(MIRBuilder), Observer(Observer), Function(Function), MRI(Function.registerInfo()), Info(Info) {} +Expected<void> LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction, + std::size_t TypeIndex, + LowLevelType WideType) { + if (TypeIndex != 1) + return makeUnexpected(ErrorCode::Unsupported, + "G_MERGE_VALUES widening requires type index one"); + if (Instruction.operandCount() < 3) + return makeUnexpected(ErrorCode::VerificationError, + "G_MERGE_VALUES requires a destination and sources"); + + const Register *Destination = Instruction.operandAt(0)->getIf<Register>(); + const Register *FirstSource = Instruction.operandAt(1)->getIf<Register>(); + if (Destination == nullptr || FirstSource == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "G_MERGE_VALUES requires register operands"); + auto DestinationType = MRI.getType(*Destination); + auto SourceType = MRI.getType(*FirstSource); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (!SourceType) + return std::unexpected(SourceType.error()); + if (DestinationType->isVector()) + return makeUnexpected(ErrorCode::Unsupported, + "vector G_MERGE_VALUES widening is not supported"); + + const std::uint64_t DestinationSize = DestinationType->minimumBitWidth(); + const std::uint64_t SourceSize = SourceType->minimumBitWidth(); + const std::uint64_t WideSize = WideType.minimumBitWidth(); + const std::uint64_t MergeCount = (DestinationSize + WideSize - 1U) / WideSize; + const std::size_t SourceCount = Instruction.operandCount() - 1U; + const std::uint64_t PartSize = DestinationSize / SourceCount; + + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + + if (WideSize >= DestinationSize) { + auto Result = MRI.createVirtualRegister(WideType); + 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) { + const Register *Source = Instruction.operandAt(Index)->getIf<Register>(); + if (Source == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "G_MERGE_VALUES requires register sources"); + auto ActualSourceType = MRI.getType(*Source); + if (!ActualSourceType) + return std::unexpected(ActualSourceType.error()); + if (*ActualSourceType != *SourceType || ActualSourceType->minimumBitWidth() != PartSize) + 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); + if (!ExtendedInput) + return std::unexpected(ExtendedInput.error()); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); + 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) { + auto NewResult = MRI.createVirtualRegister(WideType); + if (!NewResult) + return std::unexpected(NewResult.error()); + NextResult = *NewResult; + } + if (auto Built = MIRBuilder.buildOr(NextResult, ResultRegister, *ShiftedInput); !Built) + return std::unexpected(Built.error()); + ResultRegister = NextResult; + } + + if (WideSize > DestinationSize) { + if (auto Built = MIRBuilder.buildTrunc(*Destination, ResultRegister); !Built) + return std::unexpected(Built.error()); + } else if (DestinationType->isPointer()) { + if (auto Built = MIRBuilder.buildIntToPtr(*Destination, ResultRegister); !Built) + return std::unexpected(Built.error()); + } + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "G_MERGE_VALUES became detached during widening"); + return Block->removeInstruction(Instruction); + } + + auto GCDType = LowLevelType::makeCategoryNeutralScalar(std::gcd(SourceSize, WideSize)); + auto WideDestinationType = LowLevelType::makeCategoryNeutralScalar(MergeCount * WideSize); + if (!GCDType) + return std::unexpected(GCDType.error()); + if (!WideDestinationType) + return std::unexpected(WideDestinationType.error()); + + std::vector<Register> UnmergedRegisters; + for (std::size_t Index = 1; Index != Instruction.operandCount(); ++Index) { + const Register *Source = Instruction.operandAt(Index)->getIf<Register>(); + if (Source == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "G_MERGE_VALUES requires register sources"); + if (GCDType->minimumBitWidth() == SourceSize) { + UnmergedRegisters.push_back(*Source); + continue; + } + auto Extracted = extractGCDType(UnmergedRegisters, *GCDType, *Source); + if (!Extracted) + return std::unexpected(Extracted.error()); + } + + const std::uint64_t RequiredPartCount = MergeCount * WideSize; + if (UnmergedRegisters.size() != RequiredPartCount) { + auto UndefRegister = MRI.createVirtualRegister(*GCDType); + 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); + } + + const std::size_t PartsPerGCD = static_cast<std::size_t>(WideSize / GCDType->minimumBitWidth()); + std::vector<Register> NewMergeRegisters; + NewMergeRegisters.reserve(static_cast<std::size_t>(MergeCount)); + for (std::size_t Index = 0; Index != MergeCount; ++Index) { + 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); + if (!MergeRegister) + return std::unexpected(MergeRegister.error()); + if (auto Built = MIRBuilder.buildMergeLikeInstr(*MergeRegister, Parts); !Built) + return std::unexpected(Built.error()); + NewMergeRegisters.push_back(*MergeRegister); + } + + if (DestinationSize == WideDestinationType->minimumBitWidth()) { + if (auto Built = MIRBuilder.buildMergeLikeInstr(*Destination, NewMergeRegisters); !Built) + return std::unexpected(Built.error()); + } else { + auto FinalMerge = MRI.createVirtualRegister(*WideDestinationType); + 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()); + } + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "G_MERGE_VALUES became detached during widening"); + return Block->removeInstruction(Instruction); +} + +Expected<void> LegalizerHelper::widenScalarUnmergeValues(MachineInstr &Instruction, + std::size_t TypeIndex, + LowLevelType WideType) { + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::Unsupported, + "G_UNMERGE_VALUES widening requires type index zero"); + if (Instruction.operandCount() < 2) + return makeUnexpected(ErrorCode::VerificationError, + "G_UNMERGE_VALUES requires destinations and a source"); + + const std::size_t DestinationCount = Instruction.operandCount() - 1U; + const Register *Source = Instruction.operandAt(DestinationCount)->getIf<Register>(); + const Register *FirstDestination = Instruction.operandAt(0)->getIf<Register>(); + if (Source == nullptr || FirstDestination == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "G_UNMERGE_VALUES requires register operands"); + auto SourceType = MRI.getType(*Source); + auto DestinationType = MRI.getType(*FirstDestination); + if (!SourceType) + return std::unexpected(SourceType.error()); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (SourceType->isVector() || !DestinationType->isCategoryNeutralScalar()) + return makeUnexpected(ErrorCode::Unsupported, + "G_UNMERGE_VALUES widening requires scalar types"); + + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + + Register SourceRegister = *Source; + if (WideType.minimumBitWidth() >= SourceType->minimumBitWidth()) { + if (SourceType->isPointer()) { + auto IntegerSourceType = + LowLevelType::makeCategoryNeutralScalar(SourceType->minimumBitWidth()); + if (!IntegerSourceType) + return std::unexpected(IntegerSourceType.error()); + auto IntegerSource = MRI.createVirtualRegister(*IntegerSourceType); + if (!IntegerSource) + return std::unexpected(IntegerSource.error()); + if (auto Built = MIRBuilder.buildPtrToInt(*IntegerSource, SourceRegister); !Built) + return std::unexpected(Built.error()); + *SourceType = *IntegerSourceType; + SourceRegister = *IntegerSource; + } + + if (WideType.minimumBitWidth() > SourceType->minimumBitWidth()) { + auto WideSource = MRI.createVirtualRegister(WideType); + if (!WideSource) + return std::unexpected(WideSource.error()); + if (auto Built = MIRBuilder.buildAnyExt(*WideSource, SourceRegister); !Built) + return std::unexpected(Built.error()); + *SourceType = WideType; + SourceRegister = *WideSource; + } + + const std::uint64_t DestinationSize = DestinationType->minimumBitWidth(); + if (auto Built = MIRBuilder.buildTrunc(*FirstDestination, SourceRegister); !Built) + return std::unexpected(Built.error()); + for (std::size_t Index = 1; Index != DestinationCount; ++Index) { + const Register *Destination = Instruction.operandAt(Index)->getIf<Register>(); + 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()); + if (auto Built = MIRBuilder.buildLShr(*ShiftedSource, SourceRegister, *ShiftAmount); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildTrunc(*Destination, *ShiftedSource); !Built) + return std::unexpected(Built.error()); + } + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "G_UNMERGE_VALUES became detached during widening"); + return Block->removeInstruction(Instruction); + } + + auto LCMType = getLCMType(*SourceType, WideType); + if (!LCMType) + return std::unexpected(LCMType.error()); + Register WideSource = SourceRegister; + if (LCMType->minimumBitWidth() != SourceType->minimumBitWidth()) { + if (SourceType->isPointer()) + return makeUnexpected(ErrorCode::Unsupported, + "widening a pointer G_UNMERGE_VALUES source is not implemented"); + auto ExtendedSource = MRI.createVirtualRegister(*LCMType); + if (!ExtendedSource) + return std::unexpected(ExtendedSource.error()); + if (auto Built = MIRBuilder.buildAnyExt(*ExtendedSource, WideSource); !Built) + return std::unexpected(Built.error()); + WideSource = *ExtendedSource; + } + + const std::size_t UnmergeCount = + static_cast<std::size_t>(LCMType->minimumBitWidth() / WideType.minimumBitWidth()); + std::vector<Register> UnmergeRegisters; + UnmergeRegisters.reserve(UnmergeCount); + for (std::size_t Index = 0; Index != UnmergeCount; ++Index) { + auto Part = MRI.createVirtualRegister(WideType); + if (!Part) + return std::unexpected(Part.error()); + UnmergeRegisters.push_back(*Part); + } + if (auto Built = MIRBuilder.buildUnmergeValues(UnmergeRegisters, WideSource); !Built) + return std::unexpected(Built.error()); + + auto GCDType = getGCDType(WideType, *DestinationType); + if (!GCDType) + return std::unexpected(GCDType.error()); + const std::size_t PartsPerRemerge = + static_cast<std::size_t>(DestinationType->minimumBitWidth() / GCDType->minimumBitWidth()); + + if (PartsPerRemerge == 1) { + const std::size_t PartsPerUnmerge = + static_cast<std::size_t>(WideType.minimumBitWidth() / DestinationType->minimumBitWidth()); + for (std::size_t Index = 0; Index != UnmergeRegisters.size(); ++Index) { + std::vector<Register> Destinations; + Destinations.reserve(PartsPerUnmerge); + for (std::size_t PartIndex = 0; PartIndex != PartsPerUnmerge; ++PartIndex) { + const std::size_t DestinationIndex = Index * PartsPerUnmerge + PartIndex; + if (DestinationIndex < DestinationCount) { + const Register *Destination = Instruction.operandAt(DestinationIndex)->getIf<Register>(); + if (Destination == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "G_UNMERGE_VALUES requires register destinations"); + Destinations.push_back(*Destination); + } else { + auto DeadDestination = MRI.createVirtualRegister(*DestinationType); + if (!DeadDestination) + return std::unexpected(DeadDestination.error()); + Destinations.push_back(*DeadDestination); + } + } + if (auto Built = MIRBuilder.buildUnmergeValues(Destinations, UnmergeRegisters[Index]); !Built) + return std::unexpected(Built.error()); + } + } else { + std::vector<Register> Parts; + for (Register UnmergeRegister : UnmergeRegisters) { + auto Extracted = extractGCDType(Parts, *GCDType, UnmergeRegister); + if (!Extracted) + return std::unexpected(Extracted.error()); + } + for (std::size_t Index = 0; Index != DestinationCount; ++Index) { + const Register *Destination = Instruction.operandAt(Index)->getIf<Register>(); + if (Destination == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "G_UNMERGE_VALUES requires register destinations"); + std::vector<Register> RemergeParts( + Parts.begin() + static_cast<std::ptrdiff_t>(Index * PartsPerRemerge), + Parts.begin() + static_cast<std::ptrdiff_t>((Index + 1U) * PartsPerRemerge)); + if (auto Built = MIRBuilder.buildMergeLikeInstr(*Destination, RemergeParts); !Built) + return std::unexpected(Built.error()); + } + } + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "G_UNMERGE_VALUES became detached during widening"); + return Block->removeInstruction(Instruction); +} + +Expected<void> LegalizerHelper::insertParts(Register Destination, LowLevelType ResultType, + LowLevelType PartType, + const std::vector<Register> &PartRegisters, + LowLevelType LeftoverType, + const std::vector<Register> &LeftoverRegisters) { + if (!LeftoverType.isValid()) { + if (!LeftoverRegisters.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, + "leftover registers require a leftover type"); + return MIRBuilder.buildMergeLikeInstr(Destination, PartRegisters).transform([](MachineInstr *) { + }); + } + + if (ResultType.isVector()) { + if (LeftoverRegisters.size() != 1) + return makeUnexpected(ErrorCode::InvalidArgument, + "mixed subvector merge requires one leftover register"); + std::vector<Register> AllRegisters = PartRegisters; + AllRegisters.insert(AllRegisters.end(), LeftoverRegisters.begin(), LeftoverRegisters.end()); + return MIRBuilder.buildMergeLikeInstr(Destination, AllRegisters).transform([](MachineInstr *) { + }); + } + + std::vector<Register> GCDRegisters; + auto FirstGCD = getGCDType(ResultType, LeftoverType); + if (!FirstGCD) + return std::unexpected(FirstGCD.error()); + auto GCDType = getGCDType(*FirstGCD, PartType); + if (!GCDType) + return std::unexpected(GCDType.error()); + for (Register Part : PartRegisters) { + auto Extracted = extractGCDType(GCDRegisters, *GCDType, Part); + if (!Extracted) + return std::unexpected(Extracted.error()); + } + for (Register Part : LeftoverRegisters) { + auto Extracted = extractGCDType(GCDRegisters, *GCDType, Part); + if (!Extracted) + return std::unexpected(Extracted.error()); + } + auto LCMType = buildLCMMergePieces(ResultType, LeftoverType, *GCDType, GCDRegisters); + if (!LCMType) + return std::unexpected(LCMType.error()); + return buildWidenedRemergeToDst(Destination, *LCMType, GCDRegisters); +} + +Expected<void> LegalizerHelper::extractGCDType(std::vector<Register> &Parts, LowLevelType GCDType, + Register Source) { + auto SourceType = MRI.getType(Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + if (*SourceType == GCDType) { + Parts.push_back(Source); + return {}; + } + const std::uint64_t SourceSize = SourceType->minimumBitWidth(); + const std::uint64_t GCDSize = GCDType.minimumBitWidth(); + if (GCDSize == 0 || SourceSize % GCDSize != 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "GCD type does not evenly divide the source type"); + return extractParts(Source, GCDType, static_cast<int>(SourceSize / GCDSize), Parts, MIRBuilder, + MRI); +} + +Expected<LowLevelType> LegalizerHelper::extractGCDType(std::vector<Register> &Parts, + LowLevelType DestinationType, + LowLevelType NarrowType, Register Source) { + auto SourceType = MRI.getType(Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + auto FirstGCD = getGCDType(*SourceType, NarrowType); + if (!FirstGCD) + return std::unexpected(FirstGCD.error()); + auto GCDType = getGCDType(*FirstGCD, DestinationType); + if (!GCDType) + return std::unexpected(GCDType.error()); + auto Extracted = extractGCDType(Parts, *GCDType, Source); + if (!Extracted) + return std::unexpected(Extracted.error()); + return *GCDType; +} + +Expected<LowLevelType> LegalizerHelper::buildLCMMergePieces(LowLevelType DestinationType, + LowLevelType NarrowType, + LowLevelType GCDType, + std::vector<Register> &Registers, + GenericOpcode PadStrategy) { + auto LCMType = getLCMType(DestinationType, NarrowType); + if (!LCMType) + return std::unexpected(LCMType.error()); + const int PartCount = static_cast<int>(LCMType->minimumBitWidth() / NarrowType.minimumBitWidth()); + const int SubPartCount = + static_cast<int>(NarrowType.minimumBitWidth() / GCDType.minimumBitWidth()); + const int OriginalSourceCount = static_cast<int>(Registers.size()); + + 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()); + } + + std::vector<Register> Remerge(static_cast<std::size_t>(PartCount)); + std::vector<Register> SubMerge(static_cast<std::size_t>(SubPartCount)); + Register AllPadRegister; + for (int PartIndex = 0; PartIndex != PartCount; ++PartIndex) { + bool AllMergePartsArePadding = true; + for (int SubPartIndex = 0; SubPartIndex != SubPartCount; ++SubPartIndex) { + const int Index = PartIndex * SubPartCount + SubPartIndex; + if (Index >= OriginalSourceCount) { + SubMerge[static_cast<std::size_t>(SubPartIndex)] = PadRegister; + continue; + } + SubMerge[static_cast<std::size_t>(SubPartIndex)] = Registers[static_cast<std::size_t>(Index)]; + AllMergePartsArePadding = false; + } + + 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 (!AllPadRegister.isNoRegister()) { + Remerge[static_cast<std::size_t>(PartIndex)] = AllPadRegister; + continue; + } + 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); + if (!Built) + return std::unexpected(Built.error()); + Remerge[static_cast<std::size_t>(PartIndex)] = *RemergeRegister; + } + if (AllMergePartsArePadding && AllPadRegister.isNoRegister()) + AllPadRegister = Remerge[static_cast<std::size_t>(PartIndex)]; + } + Registers = std::move(Remerge); + return *LCMType; +} + +Expected<void> +LegalizerHelper::buildWidenedRemergeToDst(Register Destination, LowLevelType LCMType, + const std::vector<Register> &RemergeRegisters) { + auto DestinationType = MRI.getType(Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (*DestinationType == LCMType) + return MIRBuilder.buildMergeLikeInstr(Destination, RemergeRegisters) + .transform([](MachineInstr *) {}); + + auto Remerge = MRI.createVirtualRegister(LCMType); + if (!Remerge) + return std::unexpected(Remerge.error()); + auto BuiltMerge = MIRBuilder.buildMergeLikeInstr(*Remerge, RemergeRegisters); + if (!BuiltMerge) + return std::unexpected(BuiltMerge.error()); + if (!DestinationType->isVector() && !LCMType.isVector()) + return MIRBuilder.buildTrunc(Destination, *Remerge).transform([](MachineInstr *) {}); + + if (LCMType.isVector()) { + const std::size_t DefinitionCount = + static_cast<std::size_t>(LCMType.minimumBitWidth() / DestinationType->minimumBitWidth()); + std::vector<Register> Definitions; + Definitions.reserve(DefinitionCount); + Definitions.push_back(Destination); + for (std::size_t Index = 1; Index != DefinitionCount; ++Index) { + auto Definition = MRI.createVirtualRegister(*DestinationType); + if (!Definition) + return std::unexpected(Definition.error()); + Definitions.push_back(*Definition); + } + return MIRBuilder.buildUnmergeValues(Definitions, *Remerge).transform([](MachineInstr *) {}); + } + return makeUnexpected(ErrorCode::Unsupported, + "widened remerge has an unsupported type combination"); +} + Expected<void> LegalizerHelper::widenScalarSrc(MachineInstr &Instruction, LowLevelType WideType, std::size_t OperandIndex, GenericOpcode ExtensionOpcode) { @@ -192,6 +728,10 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size Observer.changingInstr(Instruction); switch (static_cast<GenericOpcode>(Instruction.opcode().value())) { + case GenericOpcode::G_MERGE_VALUES: + return widenScalarMergeValues(Instruction, TypeIndex, WideType); + case GenericOpcode::G_UNMERGE_VALUES: + return widenScalarUnmergeValues(Instruction, TypeIndex, WideType); case GenericOpcode::G_ATOMICRMW_XCHG: case GenericOpcode::G_ATOMICRMW_ADD: case GenericOpcode::G_ATOMICRMW_SUB: @@ -408,6 +948,232 @@ Expected<void> LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size return {}; } +Expected<void> LegalizerHelper::narrowScalarAddSub(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType) { + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::Unsupported, "add/sub narrowing requires type index zero"); + + const MachineOperand *DestinationOperand = Instruction.operandAt(0); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + if (Destination == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "add/sub narrowing requires a register destination"); + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (DestinationType->isVector()) + return makeUnexpected(ErrorCode::Unsupported, "vector add/sub narrowing is not implemented"); + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + + GenericOpcode FirstOpcode; + GenericOpcode MiddleOpcode; + GenericOpcode FinalOpcode; + switch (static_cast<GenericOpcode>(Instruction.opcode().value())) { + case GenericOpcode::G_SADDO: + case GenericOpcode::G_SADDE: + case GenericOpcode::G_UADDO: + case GenericOpcode::G_UADDE: + case GenericOpcode::G_ADD: + FirstOpcode = GenericOpcode::G_UADDO; + MiddleOpcode = GenericOpcode::G_UADDE; + FinalOpcode = Instruction.opcode() == opcode(GenericOpcode::G_SADDO) || + Instruction.opcode() == opcode(GenericOpcode::G_SADDE) + ? GenericOpcode::G_SADDE + : GenericOpcode::G_UADDE; + break; + case GenericOpcode::G_SSUBO: + case GenericOpcode::G_SSUBE: + case GenericOpcode::G_USUBO: + case GenericOpcode::G_USUBE: + case GenericOpcode::G_SUB: + FirstOpcode = GenericOpcode::G_USUBO; + MiddleOpcode = GenericOpcode::G_USUBE; + FinalOpcode = Instruction.opcode() == opcode(GenericOpcode::G_SSUBO) || + Instruction.opcode() == opcode(GenericOpcode::G_SSUBE) + ? GenericOpcode::G_SSUBE + : GenericOpcode::G_USUBE; + break; + default: + return makeUnexpected(ErrorCode::InternalError, + "unexpected add/sub opcode during scalar narrowing"); + } + + const InstructionDescriptor *Descriptor = + MIRBuilder.target().instructionDescriptor(Instruction.opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "add/sub narrowing has no instruction descriptor"); + const std::size_t DefinitionCount = Descriptor->NumExplicitDefs; + const MachineOperand *FirstSourceOperand = Instruction.operandAt(DefinitionCount); + const MachineOperand *SecondSourceOperand = Instruction.operandAt(DefinitionCount + 1); + const Register *FirstSource = + FirstSourceOperand == nullptr ? nullptr : FirstSourceOperand->getIf<Register>(); + const Register *SecondSource = + SecondSourceOperand == nullptr ? nullptr : SecondSourceOperand->getIf<Register>(); + if (FirstSource == nullptr || SecondSource == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "add/sub narrowing requires two register sources"); + + Register CarryDestination; + Register CarryIn; + if (DefinitionCount == 2) { + const MachineOperand *CarryOperand = Instruction.operandAt(1); + const Register *Carry = CarryOperand == nullptr ? nullptr : CarryOperand->getIf<Register>(); + if (Carry == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "add/sub narrowing has an invalid carry destination"); + CarryDestination = *Carry; + } + if (Instruction.operandCount() == DefinitionCount + 3) { + const MachineOperand *CarryOperand = Instruction.operandAt(DefinitionCount + 2); + const Register *Carry = CarryOperand == nullptr ? nullptr : CarryOperand->getIf<Register>(); + if (Carry == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "add/sub narrowing has an invalid carry input"); + CarryIn = *Carry; + } + + LowLevelType LeftoverType; + LowLevelType DummyType; + std::vector<Register> FirstParts; + std::vector<Register> SecondParts; + std::vector<Register> FirstLeftovers; + std::vector<Register> SecondLeftovers; + std::vector<Register> DestinationParts; + auto FirstExtracted = extractParts(*FirstSource, *DestinationType, NarrowType, LeftoverType, + FirstParts, FirstLeftovers, MIRBuilder, MRI); + if (!FirstExtracted) + return std::unexpected(FirstExtracted.error()); + auto SecondExtracted = extractParts(*SecondSource, *DestinationType, NarrowType, DummyType, + SecondParts, SecondLeftovers, MIRBuilder, MRI); + if (!SecondExtracted) + return std::unexpected(SecondExtracted.error()); + + const std::size_t NarrowPartCount = FirstParts.size(); + FirstParts.insert(FirstParts.end(), FirstLeftovers.begin(), FirstLeftovers.end()); + SecondParts.insert(SecondParts.end(), SecondLeftovers.begin(), SecondLeftovers.end()); + if (FirstParts.size() != SecondParts.size()) + return makeUnexpected(ErrorCode::InternalError, + "add/sub source splits have different part counts"); + DestinationParts.reserve(FirstParts.size()); + + auto BooleanType = LowLevelType::makeCategoryNeutralScalar(1); + if (!BooleanType) + return std::unexpected(BooleanType.error()); + for (std::size_t Index = 0; Index != FirstParts.size(); ++Index) { + auto PartType = MRI.getType(FirstParts[Index]); + if (!PartType) + return std::unexpected(PartType.error()); + auto PartDestination = MRI.createVirtualRegister(*PartType); + if (!PartDestination) + return std::unexpected(PartDestination.error()); + + Register CarryOut; + if (Index + 1 == FirstParts.size() && !CarryDestination.isNoRegister()) { + CarryOut = CarryDestination; + } else { + auto NewCarry = MRI.createVirtualRegister(*BooleanType); + if (!NewCarry) + return std::unexpected(NewCarry.error()); + CarryOut = *NewCarry; + } + + Expected<MachineInstr *> Built; + if (CarryIn.isNoRegister()) { + Built = MIRBuilder.buildInstr(opcode(FirstOpcode), {*PartDestination, CarryOut}, + {FirstParts[Index], SecondParts[Index]}); + } else if (Index + 1 == FirstParts.size()) { + Built = MIRBuilder.buildInstr(opcode(FinalOpcode), {*PartDestination, CarryOut}, + {FirstParts[Index], SecondParts[Index], CarryIn}); + } else { + Built = MIRBuilder.buildInstr(opcode(MiddleOpcode), {*PartDestination, CarryOut}, + {FirstParts[Index], SecondParts[Index], CarryIn}); + } + if (!Built) + return std::unexpected(Built.error()); + DestinationParts.push_back(*PartDestination); + CarryIn = CarryOut; + } + + std::vector<Register> MainDestinations(DestinationParts.begin(), + DestinationParts.begin() + + static_cast<std::ptrdiff_t>(NarrowPartCount)); + std::vector<Register> LeftoverDestinations(DestinationParts.begin() + + static_cast<std::ptrdiff_t>(NarrowPartCount), + DestinationParts.end()); + auto Inserted = insertParts(*Destination, *DestinationType, NarrowType, MainDestinations, + LeftoverType, LeftoverDestinations); + if (!Inserted) + return std::unexpected(Inserted.error()); + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "add/sub instruction became detached during narrowing"); + return Block->removeInstruction(Instruction); +} + +Expected<void> LegalizerHelper::narrowScalarExt(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType) { + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::Unsupported, "extension narrowing requires type index zero"); + + const auto Destination = Instruction.operandAt(0)->registerValue(); + const auto Source = Instruction.operandAt(1)->registerValue(); + if (!Destination || !Source) + return makeUnexpected(ErrorCode::VerificationError, + "extension narrowing requires register operands"); + + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (DestinationType->isVector()) + return makeUnexpected(ErrorCode::Unsupported, "vector extension narrowing is not implemented"); + + std::vector<Register> Parts; + auto GCDType = extractGCDType(Parts, *DestinationType, NarrowType, *Source); + if (!GCDType) + return std::unexpected(GCDType.error()); + auto LCMType = buildLCMMergePieces(*DestinationType, NarrowType, *GCDType, Parts, + static_cast<GenericOpcode>(Instruction.opcode().value())); + if (!LCMType) + return std::unexpected(LCMType.error()); + auto Remerged = buildWidenedRemergeToDst(*Destination, *LCMType, Parts); + if (!Remerged) + return std::unexpected(Remerged.error()); + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "extension instruction became detached during narrowing"); + return Block->removeInstruction(Instruction); +} + +Expected<void> LegalizerHelper::narrowScalar(MachineInstr &Instruction, std::size_t TypeIndex, + LowLevelType NarrowType) { + switch (static_cast<GenericOpcode>(Instruction.opcode().value())) { + case GenericOpcode::G_ADD: + case GenericOpcode::G_SUB: + case GenericOpcode::G_SADDO: + case GenericOpcode::G_SSUBO: + case GenericOpcode::G_SADDE: + case GenericOpcode::G_SSUBE: + case GenericOpcode::G_UADDO: + case GenericOpcode::G_USUBO: + case GenericOpcode::G_UADDE: + case GenericOpcode::G_USUBE: + return narrowScalarAddSub(Instruction, TypeIndex, NarrowType); + case GenericOpcode::G_SEXT: + case GenericOpcode::G_ZEXT: + case GenericOpcode::G_ANYEXT: + return narrowScalarExt(Instruction, TypeIndex, NarrowType); + default: + return makeUnexpected(ErrorCode::Unsupported, + "scalar narrowing is not implemented for this opcode"); + } +} + Expected<void> LegalizerHelper::lowerVAArg(MachineInstr &Instruction) { if (Instruction.opcode() != opcode(GenericOpcode::G_VAARG) || Instruction.operandCount() != 3 || !Instruction.memOperands().empty()) { @@ -550,6 +1316,166 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, switch (static_cast<GenericOpcode>(Instruction.opcode().value())) { case GenericOpcode::G_VAARG: return lowerVAArg(Instruction); + case GenericOpcode::G_UADDO: { + const Register Result = *Instruction.operandAt(0)->getIf<Register>(); + const Register CarryOut = *Instruction.operandAt(1)->getIf<Register>(); + const Register Left = *Instruction.operandAt(2)->getIf<Register>(); + const Register Right = *Instruction.operandAt(3)->getIf<Register>(); + auto NewResult = MRI.cloneVirtualRegister(Result); + if (!NewResult) + return std::unexpected(NewResult.error()); + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = MIRBuilder.buildAdd(*NewResult, Left, Right); !Built) + return std::unexpected(Built.error()); + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::UnsignedLessThan, CarryOut, *NewResult, Right); + !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildCopy(Result, *NewResult); !Built) + return std::unexpected(Built.error()); + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "G_UADDO became detached during lowering"); + return Block->removeInstruction(Instruction); + } + case GenericOpcode::G_UADDE: { + const Register Result = *Instruction.operandAt(0)->getIf<Register>(); + const Register CarryOut = *Instruction.operandAt(1)->getIf<Register>(); + const Register Left = *Instruction.operandAt(2)->getIf<Register>(); + const Register Right = *Instruction.operandAt(3)->getIf<Register>(); + const Register CarryIn = *Instruction.operandAt(4)->getIf<Register>(); + auto ResultType = MRI.getType(Result); + auto ConditionType = MRI.getType(CarryOut); + if (!ResultType) + return std::unexpected(ResultType.error()); + if (!ConditionType) + return std::unexpected(ConditionType.error()); + auto NewResult = MRI.cloneVirtualRegister(Result); + 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) + return std::unexpected(NewResult.error()); + if (!TemporaryResult) + return std::unexpected(TemporaryResult.error()); + if (!Carry) + 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) + return std::unexpected(SecondCarry.error()); + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = MIRBuilder.buildAdd(*TemporaryResult, Left, Right); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::UnsignedLessThan, *Carry, + *TemporaryResult, Left); + !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildZExt(*ExtendedCarryIn, CarryIn); !Built) + 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()); + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::Equal, *ResultIsZero, *NewResult, *Zero); + !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildAnd(*SecondCarry, *ResultIsZero, CarryIn); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildOr(CarryOut, *Carry, *SecondCarry); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildCopy(Result, *NewResult); !Built) + return std::unexpected(Built.error()); + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "G_UADDE became detached during lowering"); + return Block->removeInstruction(Instruction); + } + case GenericOpcode::G_USUBO: { + const Register Result = *Instruction.operandAt(0)->getIf<Register>(); + const Register BorrowOut = *Instruction.operandAt(1)->getIf<Register>(); + const Register Left = *Instruction.operandAt(2)->getIf<Register>(); + const Register Right = *Instruction.operandAt(3)->getIf<Register>(); + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = MIRBuilder.buildSub(Result, Left, Right); !Built) + return std::unexpected(Built.error()); + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::UnsignedLessThan, BorrowOut, Left, Right); + !Built) + return std::unexpected(Built.error()); + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "G_USUBO became detached during lowering"); + return Block->removeInstruction(Instruction); + } + case GenericOpcode::G_USUBE: { + const Register Result = *Instruction.operandAt(0)->getIf<Register>(); + const Register BorrowOut = *Instruction.operandAt(1)->getIf<Register>(); + const Register Left = *Instruction.operandAt(2)->getIf<Register>(); + const Register Right = *Instruction.operandAt(3)->getIf<Register>(); + const Register BorrowIn = *Instruction.operandAt(4)->getIf<Register>(); + auto ResultType = MRI.getType(Result); + auto ConditionType = MRI.getType(BorrowOut); + if (!ResultType) + return std::unexpected(ResultType.error()); + if (!ConditionType) + return std::unexpected(ConditionType.error()); + 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) + return std::unexpected(TemporaryResult.error()); + if (!Borrow) + 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) + return std::unexpected(SecondBorrow.error()); + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = MIRBuilder.buildSub(*TemporaryResult, Left, Right); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::UnsignedGreaterThan, *Borrow, + *TemporaryResult, Left); + !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildZExt(*ExtendedBorrowIn, BorrowIn); !Built) + 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()); + if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::Equal, *TemporaryResultIsZero, + *TemporaryResult, *Zero); + !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildAnd(*SecondBorrow, *TemporaryResultIsZero, BorrowIn); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildOr(BorrowOut, *Borrow, *SecondBorrow); !Built) + return std::unexpected(Built.error()); + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "G_USUBE became detached during lowering"); + return Block->removeInstruction(Instruction); + } default: { const InstructionDescriptor *Descriptor = MIRBuilder.target().instructionDescriptor(Instruction.opcode()); @@ -564,9 +1490,14 @@ Expected<void> LegalizerHelper::lower(MachineInstr &Instruction, Expected<void> LegalizerHelper::legalize(MachineInstr &Instruction, const LegalizationDecision &Decision) { + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + switch (Decision.Action) { case LegalizationAction::WidenScalar: return widenScalar(Instruction, Decision.TypeIndex, Decision.NewType); + case LegalizationAction::NarrowScalar: + return narrowScalar(Instruction, Decision.TypeIndex, Decision.NewType); case LegalizationAction::Custom: return Info.legalizeCustom(*this, Instruction, Decision); case LegalizationAction::Lower: @@ -575,7 +1506,6 @@ Expected<void> LegalizerHelper::legalize(MachineInstr &Instruction, return {}; case LegalizationAction::Unsupported: case LegalizationAction::Libcall: - case LegalizationAction::NarrowScalar: case LegalizationAction::MoreElements: case LegalizationAction::FewerElements: case LegalizationAction::Bitcast: diff --git a/backend/lib/CodeGen/GlobalISel/Utils.cpp b/backend/lib/CodeGen/GlobalISel/Utils.cpp new file mode 100644 index 0000000..6640694 --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/Utils.cpp @@ -0,0 +1,406 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/Utils.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <cstdint> +#include <numeric> +#include <utility> + +namespace rcc { +namespace { + +[[nodiscard]] bool hasProtectedAttachment(const MachineInstr &Instruction) noexcept { + return Instruction.flags().has(MachineInstrFlag::FrameSetup) || + Instruction.flags().has(MachineInstrFlag::FrameDestroy) || + Instruction.debugInstrNumber() != 0 || Instruction.preInstrSymbol().has_value() || + Instruction.postInstrSymbol().has_value() || Instruction.heapAllocMarker().has_value() || + Instruction.pcSections().has_value() || Instruction.mmra().has_value() || + Instruction.cfiType().has_value() || Instruction.deactivationSymbol().has_value(); +} + +[[nodiscard]] bool wouldBeTriviallyDead(const MachineInstr &Instruction, + const InstructionDescriptor &Descriptor) noexcept { + switch (static_cast<GenericOpcode>(Instruction.opcode().value())) { + case GenericOpcode::LOCAL_ESCAPE: + case GenericOpcode::FAKE_USE: + case GenericOpcode::LIFETIME_START: + case GenericOpcode::LIFETIME_END: + return false; + default: + break; + } + + const InstructionFlags Flags = Descriptor.Flags; + if (Flags.has(InstructionFlag::Phi)) + return true; + if (Flags.has(InstructionFlag::Terminator) || Flags.has(InstructionFlag::Branch) || + Flags.has(InstructionFlag::Call) || Flags.has(InstructionFlag::Return) || + Flags.has(InstructionFlag::Barrier) || Flags.has(InstructionFlag::MayLoad) || + Flags.has(InstructionFlag::MayStore) || Flags.has(InstructionFlag::HasSideEffects) || + Flags.has(InstructionFlag::UnmodeledSideEffects) || + Flags.has(InstructionFlag::MayRaiseFPException) || hasProtectedAttachment(Instruction)) + return false; + return true; +} + +[[nodiscard]] Expected<void> saveUsesAndErase(MachineInstr &Instruction, MachineRegisterInfo &MRI, + std::vector<MachineInstr *> &DeadChain) { + for (const MachineOperand &Operand : Instruction.operands()) { + if (!Operand.isRegister() || !Operand.isUse()) + continue; + const std::optional<Register> Reg = Operand.registerValue(); + if (!Reg || !Reg->isVirtual()) + continue; + MachineInstr *Definition = MRI.getVRegDef(*Reg); + if (Definition != nullptr && Definition != &Instruction) + DeadChain.push_back(Definition); + } + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return {}; + return Block->removeInstruction(Instruction); +} + +[[nodiscard]] Expected<LowLevelType> makeVectorType(std::uint64_t ElementCount, bool IsScalable, + LowLevelType ElementType) { + if (!IsScalable && ElementCount == 1) + return ElementType; + return IsScalable ? LowLevelType::makeScalableVector(ElementCount, ElementType) + : LowLevelType::makeFixedVector(ElementCount, ElementType); +} + +[[nodiscard]] Expected<void> extractVectorParts(Register Reg, std::size_t ElementCount, + std::vector<Register> &Parts, + MachineIRBuilder &MIRBuilder, + MachineRegisterInfo &MRI) { + auto RegisterType = MRI.getType(Reg); + if (!RegisterType) + return std::unexpected(RegisterType.error()); + if (!RegisterType->isVector() || RegisterType->isScalableVector() || ElementCount == 0) { + return makeUnexpected( + ErrorCode::InvalidArgument, + "vector part extraction requires a fixed vector and a nonzero element count"); + } + + const LowLevelType ElementType = *RegisterType->scalarElementType(); + auto NarrowType = makeVectorType(ElementCount, false, ElementType); + if (!NarrowType) + return std::unexpected(NarrowType.error()); + const std::size_t RegisterElementCount = RegisterType->minimumElementCount(); + const std::size_t LeftoverElementCount = RegisterElementCount % ElementCount; + const std::size_t NarrowPartCount = RegisterElementCount / ElementCount; + + if (LeftoverElementCount == 0) + return extractParts(Reg, *NarrowType, static_cast<int>(NarrowPartCount), Parts, MIRBuilder, + MRI); + + std::vector<Register> Elements; + auto Extracted = extractParts(Reg, ElementType, static_cast<int>(RegisterElementCount), Elements, + MIRBuilder, MRI); + if (!Extracted) + return std::unexpected(Extracted.error()); + + std::size_t Offset = 0; + for (std::size_t Index = 0; Index != NarrowPartCount; ++Index, Offset += ElementCount) { + std::vector<Register> Piece(Elements.begin() + static_cast<std::ptrdiff_t>(Offset), + Elements.begin() + + static_cast<std::ptrdiff_t>(Offset + ElementCount)); + auto Part = MRI.createVirtualRegister(*NarrowType); + if (!Part) + return std::unexpected(Part.error()); + auto Built = MIRBuilder.buildMergeLikeInstr(*Part, Piece); + if (!Built) + return std::unexpected(Built.error()); + Parts.push_back(*Part); + } + + if (LeftoverElementCount == 1) { + Parts.push_back(Elements[Offset]); + return {}; + } + + auto LeftoverType = LowLevelType::makeFixedVector(LeftoverElementCount, ElementType); + if (!LeftoverType) + return std::unexpected(LeftoverType.error()); + std::vector<Register> LeftoverElements(Elements.begin() + static_cast<std::ptrdiff_t>(Offset), + Elements.end()); + auto Leftover = MRI.createVirtualRegister(*LeftoverType); + if (!Leftover) + return std::unexpected(Leftover.error()); + auto Built = MIRBuilder.buildMergeLikeInstr(*Leftover, LeftoverElements); + if (!Built) + return std::unexpected(Built.error()); + Parts.push_back(*Leftover); + return {}; +} + +} // namespace + +bool isTriviallyDead(const MachineInstr &Instruction, const MachineRegisterInfo &MRI, + const TargetDescription &Target) noexcept { + for (const MachineOperand &Operand : Instruction.operands()) { + if (!Operand.isRegister() || !Operand.isDef()) + continue; + const std::optional<Register> Reg = Operand.registerValue(); + if (!Reg || Reg->isPhysical() || !MRI.useEmpty(*Reg, false)) + return false; + } + + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + return Descriptor != nullptr && wouldBeTriviallyDead(Instruction, *Descriptor); +} + +Expected<void> eraseInstrs(std::span<MachineInstr *const> Instructions, MachineRegisterInfo &MRI, + const TargetDescription &Target) { + std::vector<MachineInstr *> DeadChain; + for (MachineInstr *Instruction : Instructions) { + if (Instruction == nullptr || Instruction->parent() == nullptr) + continue; + auto Removed = saveUsesAndErase(*Instruction, MRI, DeadChain); + if (!Removed) + return std::unexpected(Removed.error()); + } + + while (!DeadChain.empty()) { + MachineInstr *Instruction = DeadChain.back(); + DeadChain.pop_back(); + if (Instruction == nullptr || Instruction->parent() == nullptr || + !isTriviallyDead(*Instruction, MRI, Target)) + continue; + auto Removed = saveUsesAndErase(*Instruction, MRI, DeadChain); + if (!Removed) + return std::unexpected(Removed.error()); + } + return {}; +} + +Expected<void> eraseInstr(MachineInstr &Instruction, MachineRegisterInfo &MRI, + const TargetDescription &Target) { + MachineInstr *Instructions[] = {&Instruction}; + return eraseInstrs(Instructions, MRI, Target); +} + +Expected<void> extractParts(Register Reg, LowLevelType Type, int PartCount, + std::vector<Register> &Parts, MachineIRBuilder &MIRBuilder, + MachineRegisterInfo &MRI) { + std::vector<Register> NewParts; + if (PartCount < 0) + return makeUnexpected(ErrorCode::InvalidArgument, "part count cannot be negative"); + NewParts.reserve(static_cast<std::size_t>(PartCount)); + for (int Index = 0; Index != PartCount; ++Index) { + auto Part = MRI.createVirtualRegister(Type); + if (!Part) + return std::unexpected(Part.error()); + NewParts.push_back(*Part); + } + auto Built = MIRBuilder.buildUnmergeValues(NewParts, Reg); + if (!Built) + return std::unexpected(Built.error()); + Parts.insert(Parts.end(), NewParts.begin(), NewParts.end()); + return {}; +} + +Expected<bool> extractParts(Register Reg, LowLevelType RegisterType, LowLevelType MainType, + LowLevelType &LeftoverType, std::vector<Register> &Parts, + std::vector<Register> &LeftoverParts, MachineIRBuilder &MIRBuilder, + MachineRegisterInfo &MRI) { + if (LeftoverType.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "part extraction leftover type must be an output"); + } + + const std::uint64_t RegisterSize = RegisterType.minimumBitWidth(); + const std::uint64_t MainSize = MainType.minimumBitWidth(); + if (MainSize == 0 || MainSize > RegisterSize) { + return makeUnexpected(ErrorCode::InvalidArgument, + "part extraction requires a smaller nonzero main type"); + } + const std::size_t PartCount = RegisterSize / MainSize; + const std::uint64_t LeftoverSize = RegisterSize - PartCount * MainSize; + + if (LeftoverSize == 0) { + auto Extracted = + extractParts(Reg, MainType, static_cast<int>(PartCount), Parts, MIRBuilder, MRI); + if (!Extracted) + return std::unexpected(Extracted.error()); + return true; + } + + if (RegisterType.isVector() && MainType.isVector() && !RegisterType.isScalableVector() && + !MainType.isScalableVector()) { + const std::size_t RegisterElementCount = RegisterType.minimumElementCount(); + const std::size_t MainElementCount = MainType.minimumElementCount(); + const std::size_t LeftoverElementCount = RegisterElementCount % MainElementCount; + if (LeftoverElementCount > 1 && MainElementCount % LeftoverElementCount == 0 && + RegisterElementCount % LeftoverElementCount == 0 && + RegisterType.scalarBitWidth() == MainType.scalarBitWidth()) { + auto Candidate = + LowLevelType::makeFixedVector(LeftoverElementCount, *RegisterType.scalarElementType()); + if (!Candidate) + return std::unexpected(Candidate.error()); + LeftoverType = *Candidate; + + std::vector<Register> Unmerged; + auto Extracted = extractParts(Reg, LeftoverType, + static_cast<int>(RegisterElementCount / LeftoverElementCount), + Unmerged, MIRBuilder, MRI); + if (!Extracted) + return std::unexpected(Extracted.error()); + + const std::size_t LeftoversPerMain = MainElementCount / LeftoverElementCount; + const std::size_t LeftoverValueCount = + (RegisterElementCount % MainElementCount) / LeftoverElementCount; + std::vector<Register> MergeValues; + for (std::size_t Index = 0; Index != Unmerged.size() - LeftoverValueCount; ++Index) { + MergeValues.push_back(Unmerged[Index]); + if (MergeValues.size() != LeftoversPerMain) + continue; + auto Part = MRI.createVirtualRegister(MainType); + if (!Part) + return std::unexpected(Part.error()); + auto Built = MIRBuilder.buildMergeLikeInstr(*Part, MergeValues); + if (!Built) + return std::unexpected(Built.error()); + Parts.push_back(*Part); + MergeValues.clear(); + } + LeftoverParts.insert(LeftoverParts.end(), + Unmerged.end() - static_cast<std::ptrdiff_t>(LeftoverValueCount), + Unmerged.end()); + return true; + } + } + + if (MainType.isVector()) { + std::vector<Register> RegisterPieces; + auto Extracted = + extractVectorParts(Reg, MainType.minimumElementCount(), RegisterPieces, MIRBuilder, MRI); + if (!Extracted) + return std::unexpected(Extracted.error()); + Parts.insert(Parts.end(), RegisterPieces.begin(), std::prev(RegisterPieces.end())); + LeftoverParts.push_back(RegisterPieces.back()); + auto Type = MRI.getType(LeftoverParts.front()); + if (!Type) + return std::unexpected(Type.error()); + LeftoverType = *Type; + return true; + } + + auto ScalarLeftover = LowLevelType::makeCategoryNeutralScalar(LeftoverSize); + if (!ScalarLeftover) + return std::unexpected(ScalarLeftover.error()); + LeftoverType = *ScalarLeftover; + for (std::size_t Index = 0; Index != PartCount; ++Index) { + auto Part = MRI.createVirtualRegister(MainType); + if (!Part) + return std::unexpected(Part.error()); + auto Built = MIRBuilder.buildExtract(*Part, Reg, MainSize * Index); + if (!Built) + return std::unexpected(Built.error()); + Parts.push_back(*Part); + } + for (std::uint64_t Offset = MainSize * PartCount; Offset < RegisterSize; Offset += LeftoverSize) { + auto Part = MRI.createVirtualRegister(LeftoverType); + if (!Part) + return std::unexpected(Part.error()); + auto Built = MIRBuilder.buildExtract(*Part, Reg, Offset); + if (!Built) + return std::unexpected(Built.error()); + LeftoverParts.push_back(*Part); + } + return true; +} + +Expected<LowLevelType> getLCMType(LowLevelType OriginalType, LowLevelType TargetType) { + if (OriginalType.minimumBitWidth() == TargetType.minimumBitWidth()) + return OriginalType; + if ((OriginalType.isScalableVector() && TargetType.isVector() && + !TargetType.isScalableVector()) || + (TargetType.isScalableVector() && OriginalType.isVector() && + !OriginalType.isScalableVector())) { + return makeUnexpected(ErrorCode::Unsupported, + "LCM type is undefined between fixed and scalable vectors"); + } + + if (OriginalType.isVector() && TargetType.isVector()) { + const LowLevelType OriginalElement = *OriginalType.scalarElementType(); + const LowLevelType TargetElement = *TargetType.scalarElementType(); + if (OriginalElement.minimumBitWidth() == TargetElement.minimumBitWidth()) { + const std::uint64_t ElementCount = + std::lcm(static_cast<std::uint64_t>(OriginalType.minimumElementCount()), + static_cast<std::uint64_t>(TargetType.minimumElementCount())); + return makeVectorType(ElementCount, OriginalType.isScalableVector(), OriginalElement); + } + const std::uint64_t Width = + std::lcm(OriginalType.minimumBitWidth(), TargetType.minimumBitWidth()); + return makeVectorType(Width / OriginalElement.minimumBitWidth(), + OriginalType.isScalableVector(), OriginalElement); + } + + if (OriginalType.isVector() || TargetType.isVector()) { + const LowLevelType VectorType = OriginalType.isVector() ? OriginalType : TargetType; + const LowLevelType ScalarType = OriginalType.isVector() ? TargetType : OriginalType; + const LowLevelType VectorElement = *VectorType.scalarElementType(); + const LowLevelType OriginalElement = + OriginalType.isVector() ? *OriginalType.scalarElementType() : OriginalType; + if (VectorElement.minimumBitWidth() == ScalarType.minimumBitWidth()) + return makeVectorType(VectorType.minimumElementCount(), VectorType.isScalableVector(), + OriginalElement); + const std::uint64_t Width = + std::lcm(VectorType.minimumBitWidth(), ScalarType.minimumBitWidth()); + return makeVectorType(Width / OriginalElement.minimumBitWidth(), VectorType.isScalableVector(), + OriginalElement); + } + + const std::uint64_t Width = + std::lcm(OriginalType.minimumBitWidth(), TargetType.minimumBitWidth()); + if (Width == OriginalType.minimumBitWidth()) + return OriginalType; + if (Width == TargetType.minimumBitWidth()) + return TargetType; + return LowLevelType::makeCategoryNeutralScalar(Width); +} + +Expected<LowLevelType> getGCDType(LowLevelType OriginalType, LowLevelType TargetType) { + if (OriginalType.minimumBitWidth() == TargetType.minimumBitWidth()) + return OriginalType; + if ((OriginalType.isScalableVector() && TargetType.isVector() && + !TargetType.isScalableVector()) || + (TargetType.isScalableVector() && OriginalType.isVector() && + !OriginalType.isScalableVector())) { + return makeUnexpected(ErrorCode::Unsupported, + "GCD type is undefined between fixed and scalable vectors"); + } + + if (OriginalType.isVector() && TargetType.isVector()) { + const LowLevelType OriginalElement = *OriginalType.scalarElementType(); + const std::uint64_t Width = + std::gcd(OriginalType.minimumBitWidth(), TargetType.minimumBitWidth()); + if (Width == OriginalElement.minimumBitWidth()) + return makeVectorType(1, OriginalType.isScalableVector(), OriginalElement); + if (Width < OriginalElement.minimumBitWidth()) + return LowLevelType::makeCategoryNeutralScalar(Width); + return makeVectorType(Width / OriginalElement.minimumBitWidth(), + OriginalType.isScalableVector(), OriginalElement); + } + + if (OriginalType.isVector() && OriginalType.scalarBitWidth() == TargetType.minimumBitWidth()) + return *OriginalType.scalarElementType(); + if (TargetType.isVector() && TargetType.scalarBitWidth() == OriginalType.minimumBitWidth()) + return OriginalType; + + const std::uint64_t OriginalScalarWidth = OriginalType.scalarBitWidth(); + const std::uint64_t TargetScalarWidth = TargetType.scalarBitWidth(); + return LowLevelType::makeCategoryNeutralScalar(std::gcd(OriginalScalarWidth, TargetScalarWidth)); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineIRBuilder.cpp b/backend/lib/CodeGen/MachineIRBuilder.cpp index 9195d1a..d5be3af 100644 --- a/backend/lib/CodeGen/MachineIRBuilder.cpp +++ b/backend/lib/CodeGen/MachineIRBuilder.cpp @@ -708,6 +708,23 @@ Expected<MachineInstrBuilder> MachineIRBuilder::buildInstr(Opcode InstructionOpc return MachineInstrBuilder(*Function, *Target, *Descriptor, *InsertBlock, InsertBefore); } +Expected<MachineInstr *> +MachineIRBuilder::buildInstr(Opcode InstructionOpcode, std::initializer_list<Register> Destinations, + std::initializer_list<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) + return std::unexpected(Added.error()); + } + for (Register Source : Sources) { + if (auto Added = Pending->addUse(Source); !Added) + return std::unexpected(Added.error()); + } + return Pending->build(); +} + Expected<LowLevelType> MachineIRBuilder::registerType(Register Reg) const { if (!Reg.isVirtual()) return makeUnexpected(ErrorCode::InvalidArgument, @@ -722,8 +739,7 @@ Expected<LowLevelType> MachineIRBuilder::registerType(Register Reg) const { } Expected<MachineInstr *> MachineIRBuilder::buildUnary(Opcode InstructionOpcode, - Register Destination, - Register Source) const { + Register Destination, Register Source) const { auto Pending = buildInstr(InstructionOpcode); if (!Pending) return std::unexpected(Pending.error()); @@ -749,13 +765,11 @@ Expected<MachineInstr *> MachineIRBuilder::buildBinary(Opcode InstructionOpcode, return Pending->build(); } -Expected<MachineInstr *> MachineIRBuilder::buildTrunc(Register Destination, - Register Source) const { +Expected<MachineInstr *> MachineIRBuilder::buildTrunc(Register 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(Register Destination, Register Source) const { return buildUnary(opcode(GenericOpcode::COPY), Destination, Source); } @@ -773,16 +787,18 @@ Expected<MachineInstr *> MachineIRBuilder::buildAnyExt(Register Destination, return buildUnary(opcode(GenericOpcode::G_ANYEXT), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildZExt(Register Destination, - Register Source) const { +Expected<MachineInstr *> MachineIRBuilder::buildZExt(Register 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(Register Destination, Register Source) const { return buildUnary(opcode(GenericOpcode::G_SEXT), Destination, Source); } +Expected<MachineInstr *> MachineIRBuilder::buildUndef(Register Destination) const { + return buildImplicitDef(Destination); +} + Expected<MachineInstr *> MachineIRBuilder::buildExtOrTrunc(Opcode ExtensionOpcode, Register Destination, Register Source) const { @@ -807,12 +823,11 @@ Expected<MachineInstr *> MachineIRBuilder::buildAnyExtOrTrunc(Register Destinati } Expected<MachineInstr *> MachineIRBuilder::buildSExtOrTrunc(Register Destination, - Register Source) const { + Register Source) const { return buildExtOrTrunc(opcode(GenericOpcode::G_SEXT), Destination, Source); } -Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination, - APInt Value) const { +Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination, APInt Value) const { auto Pending = buildInstr(opcode(GenericOpcode::G_CONSTANT)); if (!Pending) return std::unexpected(Pending.error()); @@ -834,8 +849,7 @@ Expected<MachineInstr *> MachineIRBuilder::buildConstant(Register Destination, return buildConstant(Destination, std::move(*Immediate)); } -Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(Register Destination, - Register Source, +Expected<MachineInstr *> MachineIRBuilder::buildSExtInReg(Register Destination, Register Source, std::uint32_t Width) const { auto Pending = buildInstr(opcode(GenericOpcode::G_SEXT_INREG)); if (!Pending) @@ -854,8 +868,94 @@ Expected<MachineInstr *> MachineIRBuilder::buildAnd(Register Destination, Regist return buildBinary(opcode(GenericOpcode::G_AND), Destination, Left, Right); } -Expected<MachineInstr *> MachineIRBuilder::buildMergeValues( - Register Destination, const std::vector<Register> &Sources) const { +Expected<MachineInstr *> MachineIRBuilder::buildOr(Register Destination, Register Left, + Register Right) const { + return buildBinary(opcode(GenericOpcode::G_OR), Destination, Left, Right); +} + +Expected<MachineInstr *> MachineIRBuilder::buildAdd(Register 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 { + return buildBinary(opcode(GenericOpcode::G_SUB), Destination, Left, Right); +} + +Expected<MachineInstr *> MachineIRBuilder::buildShl(Register 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 { + return buildBinary(opcode(GenericOpcode::G_LSHR), Destination, Left, Right); +} + +Expected<MachineInstr *> MachineIRBuilder::buildAShr(Register Destination, Register Left, + Register Right) const { + return buildBinary(opcode(GenericOpcode::G_ASHR), Destination, Left, Right); +} + +Expected<MachineInstr *> MachineIRBuilder::buildPtrToInt(Register Destination, + Register Source) const { + return buildUnary(opcode(GenericOpcode::G_PTRTOINT), Destination, Source); +} + +Expected<MachineInstr *> MachineIRBuilder::buildIntToPtr(Register 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 { + auto Pending = buildInstr(opcode(GenericOpcode::G_ICMP)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Added = Pending->addDef(Destination); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addIntegerPredicate(Predicate); !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(); +} + +Expected<MachineInstr *> +MachineIRBuilder::buildMergeLikeInstr(Register Destination, + const std::vector<Register> &Sources) const { + auto DestinationType = registerType(Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (!DestinationType->isVector()) + return buildMergeValues(Destination, Sources); + if (Sources.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, + "merge-like instruction requires source registers"); + auto SourceType = registerType(Sources.front()); + if (!SourceType) + 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(); +} + +Expected<MachineInstr *> +MachineIRBuilder::buildMergeValues(Register Destination, + const std::vector<Register> &Sources) const { auto Pending = buildInstr(opcode(GenericOpcode::G_MERGE_VALUES)); if (!Pending) return std::unexpected(Pending.error()); @@ -868,8 +968,9 @@ Expected<MachineInstr *> MachineIRBuilder::buildMergeValues( return Pending->build(); } -Expected<MachineInstr *> MachineIRBuilder::buildUnmergeValues( - const std::vector<Register> &Destinations, Register Source) const { +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()); @@ -882,8 +983,7 @@ Expected<MachineInstr *> MachineIRBuilder::buildUnmergeValues( return Pending->build(); } -Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination, - Register Source, +Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register 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, @@ -900,4 +1000,24 @@ Expected<MachineInstr *> MachineIRBuilder::buildExtract(Register Destination, return Pending->build(); } +Expected<MachineInstr *> MachineIRBuilder::buildInsert(Register 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, + "generic insert offset does not fit a machine immediate"); + auto Pending = buildInstr(opcode(GenericOpcode::G_INSERT)); + 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()); + if (auto Added = Pending->addUse(Inserted); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addImmediate(static_cast<std::int64_t>(Offset)); !Added) + return std::unexpected(Added.error()); + return Pending->build(); +} + } // namespace rcc diff --git a/backend/lib/CodeGen/MachineRegisterInfo.cpp b/backend/lib/CodeGen/MachineRegisterInfo.cpp index 4627f9e..cc1cbdb 100644 --- a/backend/lib/CodeGen/MachineRegisterInfo.cpp +++ b/backend/lib/CodeGen/MachineRegisterInfo.cpp @@ -81,6 +81,20 @@ Expected<Register> MachineRegisterInfo::createVirtualRegister(LowLevelType Type) return *Reg; } +Expected<Register> MachineRegisterInfo::cloneVirtualRegister(Register Reg) { + auto Source = virtualRegisterInfo(Reg); + if (!Source) + return std::unexpected(Source.error()); + auto Clone = createVirtualRegister(); + if (!Clone) + return std::unexpected(Clone.error()); + VirtualRegisters.back() = Source->get(); + VirtualRegisters.back().Name.reset(); + VirtualRegisters.back().AllocationHints.clear(); + VirtualRegisters.back().IsTombstone = false; + return *Clone; +} + Expected<void> MachineRegisterInfo::eraseVirtualRegister(Register Reg) { auto Info = virtualRegisterInfo(Reg); if (!Info) @@ -313,8 +327,7 @@ const MachineOperand *MachineRegisterInfo::getUniqueVRegDef(Register Reg) const MachineInstr *MachineRegisterInfo::getVRegDef(Register Reg) noexcept { const MachineOperand *Definition = getUniqueVRegDef(Reg); - return Definition == nullptr ? nullptr - : const_cast<MachineInstr *>(Definition->parent()); + return Definition == nullptr ? nullptr : const_cast<MachineInstr *>(Definition->parent()); } const MachineInstr *MachineRegisterInfo::getVRegDef(Register Reg) const noexcept { @@ -327,8 +340,7 @@ Expected<LowLevelType> MachineRegisterInfo::getType(Register Reg) const { if (!Info) return std::unexpected(Info.error()); if (!Info->get().Type) - return makeUnexpected(ErrorCode::InvalidArgument, - "virtual register has no LowLevelType"); + return makeUnexpected(ErrorCode::InvalidArgument, "virtual register has no LowLevelType"); return *Info->get().Type; } diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp index b9569be..2a64a02 100644 --- a/backend/lib/CodeGen/TargetDescription.cpp +++ b/backend/lib/CodeGen/TargetDescription.cpp @@ -51,7 +51,8 @@ namespace { Expected<TargetDescription> TargetDescription::create(InstructionSet Instructions, TargetRegisterInfo Registers, - TargetMIRTextInfoDesc MIRTextDescription) { + TargetMIRTextInfoDesc MIRTextDescription, + TargetBooleanContentInfo BooleanInfo) { auto MIRText = TargetMIRTextInfo::create(std::move(MIRTextDescription), Registers); if (!MIRText) return std::unexpected(MIRText.error()); @@ -122,7 +123,8 @@ Expected<TargetDescription> TargetDescription::create(InstructionSet Instruction } } - return TargetDescription(std::move(Instructions), std::move(Registers), std::move(*MIRText)); + return TargetDescription(std::move(Instructions), std::move(Registers), std::move(*MIRText), + BooleanInfo); } Expected<void> TargetDescription::validateVirtualRegister(Register Reg, diff --git a/backend/lib/Support/APInt.cpp b/backend/lib/Support/APInt.cpp index d54a4c2..74cbc56 100644 --- a/backend/lib/Support/APInt.cpp +++ b/backend/lib/Support/APInt.cpp @@ -138,16 +138,13 @@ Expected<APInt> APInt::fromSigned(std::uint32_t BitWidth, std::int64_t Value) { return create(BitWidth, Words); } -Expected<APInt> APInt::getLowBitsSet(std::uint32_t BitWidth, - std::uint32_t SetBitCount) { +Expected<APInt> APInt::getLowBitsSet(std::uint32_t BitWidth, std::uint32_t SetBitCount) { if (BitWidth == 0 || BitWidth > MaxBitWidth || SetBitCount > BitWidth) - return makeUnexpected(ErrorCode::InvalidArgument, - "APInt low-bit mask has an invalid width"); + return makeUnexpected(ErrorCode::InvalidArgument, "APInt low-bit mask has an invalid width"); std::vector<std::uint64_t> Words(wordCount(BitWidth), 0); const std::size_t FullWords = SetBitCount / 64U; - std::ranges::fill_n( - Words.begin(), - static_cast<std::vector<std::uint64_t>::difference_type>(FullWords), + std::ranges::fill_n(Words.begin(), + static_cast<std::vector<std::uint64_t>::difference_type>(FullWords), std::numeric_limits<std::uint64_t>::max()); const std::uint32_t RemainingBits = SetBitCount % 64U; if (RemainingBits != 0) @@ -256,20 +253,74 @@ std::size_t APInt::countrZero() const noexcept { return Result; } +std::size_t APInt::countlOne() const noexcept { + std::size_t Result = 0; + for (std::size_t Bit = BitWidth; Bit != 0 && testBit(Bit - 1U); --Bit) + ++Result; + return Result; +} + +bool APInt::isAllOnes() const noexcept { + return BitWidth != 0 && countlOne() == BitWidth; +} + +bool APInt::testBit(std::size_t Bit) const noexcept { + return Bit < BitWidth && (Words[Bit / 64U] & (std::uint64_t{1} << (Bit % 64U))) != 0; +} + std::uint64_t APInt::word(std::size_t Index) const noexcept { return Index < Words.size() ? Words[Index] : 0; } +Expected<APInt> APInt::bitwiseAnd(const APInt &Other) const { + if (BitWidth == 0 || BitWidth != Other.BitWidth) + return makeUnexpected(ErrorCode::InvalidArgument, + "APInt bitwise operands must have the same nonzero width"); + std::vector<std::uint64_t> ResultWords(Words.size(), 0); + for (std::size_t Index = 0; Index != Words.size(); ++Index) + ResultWords[Index] = Words[Index] & Other.Words[Index]; + return create(BitWidth, ResultWords); +} + +Expected<APInt> APInt::bitwiseOr(const APInt &Other) const { + if (BitWidth == 0 || BitWidth != Other.BitWidth) + return makeUnexpected(ErrorCode::InvalidArgument, + "APInt bitwise operands must have the same nonzero width"); + std::vector<std::uint64_t> ResultWords(Words.size(), 0); + for (std::size_t Index = 0; Index != Words.size(); ++Index) + ResultWords[Index] = Words[Index] | Other.Words[Index]; + return create(BitWidth, ResultWords); +} + +Expected<APInt> APInt::bitwiseXor(const APInt &Other) const { + if (BitWidth == 0 || BitWidth != Other.BitWidth) + return makeUnexpected(ErrorCode::InvalidArgument, + "APInt bitwise operands must have the same nonzero width"); + std::vector<std::uint64_t> ResultWords(Words.size(), 0); + for (std::size_t Index = 0; Index != Words.size(); ++Index) + ResultWords[Index] = Words[Index] ^ Other.Words[Index]; + return create(BitWidth, ResultWords); +} + +Expected<APInt> APInt::bitwiseNot() const { + if (BitWidth == 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "APInt bitwise complement requires a nonzero width"); + std::vector<std::uint64_t> ResultWords(Words.size(), 0); + for (std::size_t Index = 0; Index != Words.size(); ++Index) + ResultWords[Index] = ~Words[Index]; + ResultWords.back() &= highWordMask(BitWidth); + return create(BitWidth, ResultWords); +} + Expected<APInt> APInt::trunc(std::uint32_t NewBitWidth) const { if (NewBitWidth == 0 || NewBitWidth >= BitWidth) return makeUnexpected(ErrorCode::InvalidArgument, "APInt truncation requires a smaller nonzero width"); std::vector<std::uint64_t> ResultWords(wordCount(NewBitWidth), 0); - std::ranges::copy_n( - Words.begin(), - static_cast<std::vector<std::uint64_t>::difference_type>( - ResultWords.size()), - ResultWords.begin()); + std::ranges::copy_n(Words.begin(), + static_cast<std::vector<std::uint64_t>::difference_type>(ResultWords.size()), + ResultWords.begin()); ResultWords.back() &= highWordMask(NewBitWidth); return create(NewBitWidth, ResultWords); } @@ -287,9 +338,9 @@ Expected<APInt> APInt::sext(std::uint32_t NewBitWidth) const { if (NewBitWidth <= BitWidth || NewBitWidth > MaxBitWidth) return makeUnexpected(ErrorCode::InvalidArgument, "APInt sign extension requires a larger supported width"); - std::vector<std::uint64_t> ResultWords( - wordCount(NewBitWidth), - isNegative() ? std::numeric_limits<std::uint64_t>::max() : std::uint64_t{0}); + std::vector<std::uint64_t> ResultWords(wordCount(NewBitWidth), + isNegative() ? std::numeric_limits<std::uint64_t>::max() + : std::uint64_t{0}); std::ranges::copy(Words, ResultWords.begin()); if (isNegative() && BitWidth % 64U != 0) ResultWords[wordCount(BitWidth) - 1U] |= ~highWordMask(BitWidth); diff --git a/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp b/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp index 4d81404..f1d2fac 100644 --- a/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp +++ b/backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp @@ -4,6 +4,7 @@ #include "RISCVImmediateMaterialization.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" #include "rcc/CodeGen/GlobalISel/LegalizerHelper.h" #include "rcc/CodeGen/LowLevelType.h" #include "rcc/CodeGen/MachineBasicBlock.h" @@ -1093,6 +1094,69 @@ Expected<void> RISCVLegalizerInfo::legalizeCustom(LegalizerHelper &Helper, MachineFunction &Function = Helper.MIRBuilder.function(); const TargetDescription &Target = Helper.MIRBuilder.target(); + if (Instruction.opcode() == opcode(GenericOpcode::G_ADD) || + Instruction.opcode() == opcode(GenericOpcode::G_SUB)) { + auto XLenType = LowLevelType::makeCategoryNeutralScalar(64); + if (!XLenType) + return std::unexpected(XLenType.error()); + + Helper.Observer.changingInstr(Instruction); + if (auto Widened = Helper.widenScalarSrc(Instruction, *XLenType, 1, GenericOpcode::G_ANYEXT); + !Widened) + return std::unexpected(Widened.error()); + if (auto Widened = Helper.widenScalarSrc(Instruction, *XLenType, 2, GenericOpcode::G_ANYEXT); + !Widened) + return std::unexpected(Widened.error()); + + auto ALUDestination = Function.registerInfo().createVirtualRegister(*XLenType); + if (!ALUDestination) + return std::unexpected(ALUDestination.error()); + auto SignExtendedDestination = Function.registerInfo().createVirtualRegister(*XLenType); + if (!SignExtendedDestination) + return std::unexpected(SignExtendedDestination.error()); + + MachineOperand *DestinationOperand = Instruction.operandAt(0); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + if (Destination == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V word arithmetic requires a register destination"); + const Register OriginalDestination = *Destination; + if (auto Point = Helper.MIRBuilder.setInsertPointAfter(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = + Helper.MIRBuilder.buildSExtInReg(*SignExtendedDestination, *ALUDestination, 32); + !Built) + return std::unexpected(Built.error()); + if (auto Built = Helper.MIRBuilder.buildTrunc(OriginalDestination, *SignExtendedDestination); + !Built) + return std::unexpected(Built.error()); + if (auto Changed = DestinationOperand->setRegister(*ALUDestination); !Changed) + return std::unexpected(Changed.error()); + Helper.Observer.changedInstr(Instruction); + return {}; + } + if (Instruction.opcode() == opcode(GenericOpcode::G_SEXT_INREG)) { + const MachineOperand *DestinationOperand = Instruction.operandAt(0); + const MachineOperand *SizeOperand = Instruction.operandAt(2); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + const std::int64_t *Size = + SizeOperand == nullptr ? nullptr : SizeOperand->getIf<std::int64_t>(); + if (Destination == nullptr || Size == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V G_SEXT_INREG has invalid operands"); + auto DestinationType = Function.registerInfo().getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + if (DestinationType->minimumBitWidth() == 64 && *Size == 32) + return {}; + return Helper.lower(Instruction, LegalizationDecision{ + .Action = LegalizationAction::Lower, + .TypeIndex = 0, + .NewType = {}, + }); + } if (Instruction.opcode() == opcode(GenericOpcode::G_ICMP)) return lowerIntegerCompare(Instruction, Function, Target); if (Instruction.opcode() == opcode(GenericOpcode::G_ATOMIC_CMPXCHG)) diff --git a/backend/lib/Target/RISCV/RISCVTarget.cpp b/backend/lib/Target/RISCV/RISCVTarget.cpp index 8bdea20..1735386 100644 --- a/backend/lib/Target/RISCV/RISCVTarget.cpp +++ b/backend/lib/Target/RISCV/RISCVTarget.cpp @@ -241,8 +241,12 @@ Expected<TargetDescription> createTargetDescription() { TargetMIRTextInfoDesc MIRText; appendGeneratedMIRTextInfo(MIRText); configureFunctionInfoMIRSchema(MIRText); + TargetBooleanContentInfo BooleanInfo{ + .ScalarInteger = BooleanContent::ZeroOrOne, + .ScalarFloatingPoint = BooleanContent::ZeroOrOne, + }; return TargetDescription::create(std::move(*Instructions), std::move(*Registers), - std::move(MIRText)); + std::move(MIRText), BooleanInfo); } std::shared_ptr<const RegisterMask> createCallPreservedMask(CallingConvention Convention) { |