diff options
Diffstat (limited to 'backend/lib')
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/CMakeLists.txt | 8 | ||||
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp | 514 | ||||
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/Legalizer.cpp | 33 | ||||
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp | 932 | ||||
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/Utils.cpp | 406 | ||||
| -rw-r--r-- | backend/lib/CodeGen/MachineIRBuilder.cpp | 162 | ||||
| -rw-r--r-- | backend/lib/CodeGen/MachineRegisterInfo.cpp | 20 | ||||
| -rw-r--r-- | backend/lib/CodeGen/TargetDescription.cpp | 6 | ||||
| -rw-r--r-- | backend/lib/Support/APInt.cpp | 81 | ||||
| -rw-r--r-- | backend/lib/Target/RISCV/GISel/RISCVLegalizerInfo.cpp | 64 | ||||
| -rw-r--r-- | backend/lib/Target/RISCV/RISCVTarget.cpp | 6 |
11 files changed, 2180 insertions, 52 deletions
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) { |