diff options
Diffstat (limited to 'backend/lib/CodeGen/GlobalISel/Utils.cpp')
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/Utils.cpp | 406 |
1 files changed, 406 insertions, 0 deletions
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 |