From f6fdfb8d484b4e52cdb24a94a31b0f00d41a5eb7 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sat, 15 Aug 2026 00:38:20 +0800 Subject: [GlobalISel] Match LLVM CSE builder result semantics --- backend/lib/CodeGen/GlobalISel/CMakeLists.txt | 8 + backend/lib/CodeGen/GlobalISel/CSEInfo.cpp | 467 +++++++++++++++++++++ backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp | 226 ++++++++++ backend/lib/CodeGen/GlobalISel/Legalizer.cpp | 28 +- backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp | 445 ++++++++++++++------ backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp | 18 +- 6 files changed, 1056 insertions(+), 136 deletions(-) create mode 100644 backend/lib/CodeGen/GlobalISel/CSEInfo.cpp create mode 100644 backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp (limited to 'backend/lib/CodeGen/GlobalISel') diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt index 3b01e9b..8fc50d2 100644 --- a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt +++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt @@ -2,6 +2,8 @@ set( RCCBackendGlobalISelSources + CSEInfo.cpp + CSEMIRBuilder.cpp GISelChangeObserver.cpp GISelValueTracking.cpp InstructionSelect.cpp @@ -14,6 +16,8 @@ set( set( RCCBackendGlobalISelHeaders + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/CSEInfo.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/CSEMIRBuilder.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelWorkList.h" @@ -31,6 +35,8 @@ set( target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources}) rcc_backend_register_format_files( + "${CMAKE_CURRENT_SOURCE_DIR}/CSEInfo.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/CSEMIRBuilder.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp" @@ -43,6 +49,8 @@ rcc_backend_register_format_files( ) rcc_backend_register_tidy_files( + "${CMAKE_CURRENT_SOURCE_DIR}/CSEInfo.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/CSEMIRBuilder.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionSelect.cpp" diff --git a/backend/lib/CodeGen/GlobalISel/CSEInfo.cpp b/backend/lib/CodeGen/GlobalISel/CSEInfo.cpp new file mode 100644 index 0000000..201dedd --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/CSEInfo.cpp @@ -0,0 +1,467 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/CSEInfo.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +enum class ProfileTag : std::uint64_t { + Definition, + Use, + RegisterNumber, + PhysicalRegister, + Type, + RegisterBank, + NoRegisterBank, + RegisterClass, + NoRegisterClass, + Immediate, + IntegerImmediate, + FloatingImmediate, + IntegerPredicate, + FloatingPredicate, + Flags, +}; + +void appendTypeProfile(std::vector &Profile, LowLevelType Type, + std::optional Bank, + std::optional RegClass) { + Profile.push_back(static_cast(ProfileTag::Type)); + Profile.push_back(Type.rawValue()); + if (Bank) { + Profile.push_back(static_cast(ProfileTag::RegisterBank)); + Profile.push_back(Bank->value()); + } else { + Profile.push_back(static_cast(ProfileTag::NoRegisterBank)); + } + if (RegClass) { + Profile.push_back(static_cast(ProfileTag::RegisterClass)); + Profile.push_back(RegClass->value()); + } else { + Profile.push_back(static_cast(ProfileTag::NoRegisterClass)); + } +} + +void appendAPIntProfile(std::vector &Profile, const APInt &Value) { + Profile.push_back(static_cast(ProfileTag::IntegerImmediate)); + Profile.push_back(Value.bitWidth()); + Profile.push_back(Value.words().size()); + Profile.insert(Profile.end(), Value.words().begin(), Value.words().end()); +} + +void appendAPFloatProfile(std::vector &Profile, const APFloat &Value) { + Profile.push_back(static_cast(ProfileTag::FloatingImmediate)); + Profile.push_back(static_cast(Value.semantics())); + Profile.push_back(Value.words().size()); + Profile.insert(Profile.end(), Value.words().begin(), Value.words().end()); +} + +void hashCombine(std::size_t &Seed, std::size_t Value) noexcept { + Seed ^= Value + 0x9e3779b97f4a7c15ULL + (Seed << 6U) + (Seed >> 2U); +} + +} // namespace + +bool CSEConfigFull::shouldCSEOpcode(Opcode InstructionOpcode) const noexcept { + switch (static_cast(InstructionOpcode.value())) { + default: + return false; + case GenericOpcode::G_ADD: + case GenericOpcode::G_AND: + case GenericOpcode::G_ASHR: + case GenericOpcode::G_LSHR: + case GenericOpcode::G_MUL: + case GenericOpcode::G_OR: + case GenericOpcode::G_SHL: + case GenericOpcode::G_SUB: + case GenericOpcode::G_XOR: + case GenericOpcode::G_UDIV: + case GenericOpcode::G_SDIV: + case GenericOpcode::G_UREM: + case GenericOpcode::G_SREM: + case GenericOpcode::G_CONSTANT: + case GenericOpcode::G_FCONSTANT: + case GenericOpcode::G_IMPLICIT_DEF: + case GenericOpcode::G_ZEXT: + case GenericOpcode::G_SEXT: + case GenericOpcode::G_ANYEXT: + case GenericOpcode::G_UNMERGE_VALUES: + case GenericOpcode::G_TRUNC: + case GenericOpcode::G_PTR_ADD: + case GenericOpcode::G_EXTRACT: + case GenericOpcode::G_SELECT: + case GenericOpcode::G_BUILD_VECTOR: + case GenericOpcode::G_BUILD_VECTOR_TRUNC: + case GenericOpcode::G_SEXT_INREG: + case GenericOpcode::G_FADD: + case GenericOpcode::G_FSUB: + case GenericOpcode::G_FMUL: + case GenericOpcode::G_FDIV: + case GenericOpcode::G_FABS: + case GenericOpcode::G_FMAXNUM: + case GenericOpcode::G_FMINNUM: + case GenericOpcode::G_FMAXNUM_IEEE: + case GenericOpcode::G_FMINNUM_IEEE: + return true; + } +} + +bool CSEConfigConstantOnly::shouldCSEOpcode(Opcode InstructionOpcode) const noexcept { + return InstructionOpcode == opcode(GenericOpcode::G_CONSTANT) || + InstructionOpcode == opcode(GenericOpcode::G_FCONSTANT) || + InstructionOpcode == opcode(GenericOpcode::G_IMPLICIT_DEF); +} + +std::unique_ptr getStandardCSEConfigForOpt(OptimizationLevel Level) { + if (Level == OptimizationLevel::O0) + return std::make_unique(); + return std::make_unique(); +} + +std::size_t GISelCSEInfo::CSEKeyHash::operator()(const CSEKey &Key) const noexcept { + std::size_t Result = std::hash{}(Key.Block); + hashCombine(Result, std::hash{}(Key.InstructionOpcode.value())); + for (std::uint64_t Value : Key.Profile) + hashCombine(Result, std::hash{}(Value)); + return Result; +} + +void GISelCSEInfo::setCSEConfig(std::unique_ptr NewConfig) noexcept { + Config = std::move(NewConfig); +} + +bool GISelCSEInfo::shouldCSE(Opcode InstructionOpcode) const noexcept { + return Config != nullptr && isGenericOpcode(InstructionOpcode) && + Config->shouldCSEOpcode(InstructionOpcode); +} + +Expected GISelCSEInfo::appendRegisterProfile(std::vector &Profile, + Register Reg, bool IsDefinition) const { + Profile.push_back( + static_cast(IsDefinition ? ProfileTag::Definition : ProfileTag::Use)); + if (!IsDefinition) { + Profile.push_back(static_cast(ProfileTag::RegisterNumber)); + Profile.push_back(Reg.opaqueValue()); + } + if (!Reg.isVirtual()) { + Profile.push_back(static_cast(ProfileTag::PhysicalRegister)); + Profile.push_back(Reg.opaqueValue()); + return {}; + } + if (Function == nullptr) + return makeUnexpected(ErrorCode::InternalError, "GlobalISel CSE has no machine function"); + auto Info = Function->registerInfo().virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + const std::optional &Type = Info->get().Type; + if (!Type.has_value()) { + return makeUnexpected(ErrorCode::VerificationError, + "GlobalISel CSE requires typed virtual registers"); + } + appendTypeProfile(Profile, Type.value(), Info->get().Bank, Info->get().RegClass); + return {}; +} + +Expected GISelCSEInfo::appendResultProfile(std::vector &Profile, + const MachineIRBuilderResult &Result) const { + if (Result.kind() == MachineIRBuilderResult::Kind::Register) + return appendRegisterProfile(Profile, Result.reg(), true); + Profile.push_back(static_cast(ProfileTag::Definition)); + appendTypeProfile(Profile, Result.type(), std::nullopt, std::nullopt); + return {}; +} + +Expected +GISelCSEInfo::profileInstruction(const MachineInstr &Instruction) const { + if (Instruction.parent() == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "cannot profile a detached instruction"); + if (!Instruction.memOperands().empty()) { + return makeUnexpected(ErrorCode::Unsupported, + "GlobalISel CSE does not profile memory operands"); + } + + CSEKey Key{ + .Block = Instruction.parent(), .InstructionOpcode = Instruction.opcode(), .Profile = {}}; + for (const MachineOperand &Operand : Instruction.operands()) { + switch (Operand.kind()) { + case MachineOperand::Kind::Register: { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || Operand.isImplicit()) { + return makeUnexpected(ErrorCode::Unsupported, + "GlobalISel CSE does not profile implicit register operands"); + } + auto Appended = appendRegisterProfile(Key.Profile, *Reg, Operand.isDef()); + if (!Appended) + return std::unexpected(Appended.error()); + break; + } + case MachineOperand::Kind::Immediate: { + const std::int64_t *Value = Operand.getIf(); + if (Value == nullptr) + return makeUnexpected(ErrorCode::InternalError, "invalid immediate operand storage"); + Key.Profile.push_back(static_cast(ProfileTag::Immediate)); + Key.Profile.push_back(std::bit_cast(*Value)); + break; + } + case MachineOperand::Kind::IntegerImmediate: { + const auto *Value = Operand.getIf(); + if (Value == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "invalid integer immediate operand storage"); + appendAPIntProfile(Key.Profile, Value->Value); + break; + } + case MachineOperand::Kind::FloatingImmediate: { + const auto *Value = Operand.getIf(); + if (Value == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "invalid floating immediate operand storage"); + appendAPFloatProfile(Key.Profile, Value->Bits); + break; + } + case MachineOperand::Kind::Predicate: { + const auto *Predicate = Operand.getIf(); + if (Predicate == nullptr) + return makeUnexpected(ErrorCode::InternalError, "invalid predicate operand storage"); + if (const IntegerPredicate *Integer = Predicate->integerPredicate()) { + Key.Profile.push_back(static_cast(ProfileTag::IntegerPredicate)); + Key.Profile.push_back(static_cast(*Integer)); + } else if (const FloatingPredicate *Floating = Predicate->floatingPredicate()) { + Key.Profile.push_back(static_cast(ProfileTag::FloatingPredicate)); + Key.Profile.push_back(static_cast(*Floating)); + } else { + return makeUnexpected(ErrorCode::InternalError, "empty predicate operand"); + } + break; + } + default: + return makeUnexpected(ErrorCode::Unsupported, + "GlobalISel CSE encountered an unsupported operand kind"); + } + } + Key.Profile.push_back(static_cast(ProfileTag::Flags)); + Key.Profile.push_back(Instruction.flags().rawValue()); + return Key; +} + +Expected GISelCSEInfo::profileBuilderInstruction( + Opcode InstructionOpcode, std::span Destinations, + std::span Sources, std::span Immediates, + MachineInstrFlags Flags, const MachineBasicBlock &Block) const { + CSEKey Key{.Block = &Block, .InstructionOpcode = InstructionOpcode, .Profile = {}}; + for (const MachineIRBuilderResult &Destination : Destinations) { + auto Appended = appendResultProfile(Key.Profile, Destination); + if (!Appended) + return std::unexpected(Appended.error()); + } + for (Register Source : Sources) { + auto Appended = appendRegisterProfile(Key.Profile, Source, false); + if (!Appended) + return std::unexpected(Appended.error()); + } + for (std::int64_t Immediate : Immediates) { + Key.Profile.push_back(static_cast(ProfileTag::Immediate)); + Key.Profile.push_back(std::bit_cast(Immediate)); + } + Key.Profile.push_back(static_cast(ProfileTag::Flags)); + Key.Profile.push_back(Flags.rawValue()); + return Key; +} + +Expected +GISelCSEInfo::profileConstant(const MachineIRBuilderResult &Destination, const APInt &Value, + const MachineBasicBlock &Block) const { + CSEKey Key{ + .Block = &Block, .InstructionOpcode = opcode(GenericOpcode::G_CONSTANT), .Profile = {}}; + auto Appended = appendResultProfile(Key.Profile, Destination); + if (!Appended) + return std::unexpected(Appended.error()); + appendAPIntProfile(Key.Profile, Value); + Key.Profile.push_back(static_cast(ProfileTag::Flags)); + Key.Profile.push_back(0); + return Key; +} + +Expected GISelCSEInfo::insertInstruction(MachineInstr &Instruction) { + TemporaryInstructions.remove(&Instruction); + auto Key = profileInstruction(Instruction); + if (!Key) + return std::unexpected(Key.error()); + auto [Position, Inserted] = CSEMap.emplace(*Key, &Instruction); + if (Inserted) + InstructionMapping.emplace(&Instruction, std::move(*Key)); + return {}; +} + +void GISelCSEInfo::recordNewInstruction(MachineInstr &Instruction) { + if (shouldCSE(Instruction.opcode())) + TemporaryInstructions.insert(&Instruction); +} + +Expected GISelCSEInfo::handleRecordedInstruction(MachineInstr &Instruction) { + TemporaryInstructions.remove(&Instruction); + handleRemoveInstruction(Instruction); + if (Instruction.parent() == nullptr || !shouldCSE(Instruction.opcode())) + return {}; + return insertInstruction(Instruction); +} + +Expected GISelCSEInfo::handleRecordedInstructions() { + if (HandlingRecordedInstructions) + return {}; + HandlingRecordedInstructions = true; + while (!TemporaryInstructions.empty()) { + MachineInstr *Instruction = TemporaryInstructions.popBack(); + if (Instruction == nullptr) + continue; + auto Handled = handleRecordedInstruction(*Instruction); + if (!Handled) { + HandlingRecordedInstructions = false; + return std::unexpected(Handled.error()); + } + } + HandlingRecordedInstructions = false; + return {}; +} + +void GISelCSEInfo::handleRemoveInstruction(MachineInstr &Instruction) noexcept { + const auto Mapping = InstructionMapping.find(&Instruction); + if (Mapping != InstructionMapping.end()) { + const auto Position = CSEMap.find(Mapping->second); + if (Position != CSEMap.end() && Position->second == &Instruction) + CSEMap.erase(Position); + InstructionMapping.erase(Mapping); + } + TemporaryInstructions.remove(&Instruction); +} + +Expected GISelCSEInfo::getMachineInstrIfExists( + Opcode InstructionOpcode, std::span Destinations, + std::span Sources, std::span Immediates, + MachineInstrFlags Flags, MachineBasicBlock &Block) { + auto Handled = handleRecordedInstructions(); + if (!Handled) + return std::unexpected(Handled.error()); + auto Key = + profileBuilderInstruction(InstructionOpcode, Destinations, Sources, Immediates, Flags, Block); + if (!Key) + return std::unexpected(Key.error()); + const auto Position = CSEMap.find(*Key); + if (Position == CSEMap.end()) + return nullptr; + countOpcodeHit(InstructionOpcode); + return Position->second; +} + +Expected +GISelCSEInfo::getConstantIfExists(const MachineIRBuilderResult &Destination, const APInt &Value, + MachineBasicBlock &Block) { + auto Handled = handleRecordedInstructions(); + if (!Handled) + return std::unexpected(Handled.error()); + auto Key = profileConstant(Destination, Value, Block); + if (!Key) + return std::unexpected(Key.error()); + const auto Position = CSEMap.find(*Key); + if (Position == CSEMap.end()) + return nullptr; + countOpcodeHit(opcode(GenericOpcode::G_CONSTANT)); + return Position->second; +} + +void GISelCSEInfo::countOpcodeHit(Opcode InstructionOpcode) noexcept { + ++OpcodeHitTable[InstructionOpcode.value()]; +} + +Expected GISelCSEInfo::analyze(MachineFunction &NewFunction) { + if (Config == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "GlobalISel CSE configuration is not set"); + CSEMap.clear(); + InstructionMapping.clear(); + TemporaryInstructions.clear(); + OpcodeHitTable.clear(); + HandlingRecordedInstructions = false; + Function = &NewFunction; + for (MachineBasicBlock *Block = NewFunction.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (!shouldCSE(Instruction->opcode())) + continue; + auto Inserted = insertInstruction(*Instruction); + if (!Inserted) + return std::unexpected(Inserted.error()); + } + } + return {}; +} + +Expected GISelCSEInfo::verify() { + auto Handled = handleRecordedInstructions(); + if (!Handled) + return std::unexpected(Handled.error()); + for (const auto &[Instruction, Key] : InstructionMapping) { + if (Instruction == nullptr || Instruction->parent() == nullptr) + return makeUnexpected(ErrorCode::InternalError, "GlobalISel CSE maps a detached instruction"); + auto CurrentKey = profileInstruction(*Instruction); + if (!CurrentKey) + return std::unexpected(CurrentKey.error()); + const auto Position = CSEMap.find(*CurrentKey); + if (*CurrentKey != Key || Position == CSEMap.end() || Position->second != Instruction) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE instruction mapping is inconsistent"); + } + } + for (const auto &[Key, Instruction] : CSEMap) { + const auto Mapping = InstructionMapping.find(Instruction); + if (Mapping == InstructionMapping.end() || Mapping->second != Key) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE table has no instruction mapping"); + } + } + return {}; +} + +void GISelCSEInfo::releaseMemory() noexcept { + CSEMap.clear(); + InstructionMapping.clear(); + TemporaryInstructions.clear(); + OpcodeHitTable.clear(); + Config.reset(); + Function = nullptr; + HandlingRecordedInstructions = false; +} + +void GISelCSEInfo::erasingInstr(MachineInstr &Instruction) { + handleRemoveInstruction(Instruction); +} + +void GISelCSEInfo::createdInstr(MachineInstr &Instruction) { + recordNewInstruction(Instruction); +} + +void GISelCSEInfo::changingInstr(MachineInstr &Instruction) { + erasingInstr(Instruction); + createdInstr(Instruction); +} + +void GISelCSEInfo::changedInstr(MachineInstr &Instruction) { + changingInstr(Instruction); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp b/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp new file mode 100644 index 0000000..e1fdaa6 --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp @@ -0,0 +1,226 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/CSEMIRBuilder.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/CSEInfo.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include +#include +#include +#include +#include +#include + +namespace rcc { + +bool CSEMIRBuilder::canPerformCSE(Opcode InstructionOpcode) const noexcept { + const GISelCSEInfo *Info = getCSEInfo(); + return Info != nullptr && Info->shouldCSE(InstructionOpcode); +} + +bool CSEMIRBuilder::dominatesInsertionPoint(const MachineInstr &Instruction) const noexcept { + const MachineBasicBlock *Block = insertionBlock(); + const MachineInstr *InsertBefore = insertionInstruction(); + if (Block == nullptr || Instruction.parent() != Block) + return false; + if (InsertBefore == nullptr) + return true; + for (const MachineInstr *Current = Block->firstInstruction(); Current != nullptr; + Current = Current->next()) { + if (Current == &Instruction) + return true; + if (Current == InsertBefore) + return false; + } + return false; +} + +Expected CSEMIRBuilder::makeInstructionDominate(MachineInstr &Instruction) const { + MachineBasicBlock *Block = insertionBlock(); + MachineInstr *InsertBefore = insertionInstruction(); + if (Block == nullptr || Instruction.parent() != Block) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE candidate is not in the insertion block"); + } + if (&Instruction == InsertBefore) { + return const_cast(this)->setInsertPointAfter(Instruction); + } + if (InsertBefore == nullptr || dominatesInsertionPoint(Instruction)) + return {}; + auto Removed = Block->removeInstruction(Instruction); + if (!Removed) + return std::unexpected(Removed.error()); + auto Inserted = Block->insertInstructionBefore(*InsertBefore, Instruction); + if (!Inserted) + return std::unexpected(Inserted.error()); + return {}; +} + +Expected +CSEMIRBuilder::generateCopyIfRequired(const MachineIRBuilderResult &Destination, + MachineInstr &Instruction) const { + if (Destination.kind() == MachineIRBuilderResult::Kind::Type) + return &Instruction; + const MachineOperand *Definition = Instruction.operandAt(0); + const Register *Source = Definition == nullptr ? nullptr : Definition->getIf(); + if (Source == nullptr || !Definition->isDef()) { + return makeUnexpected(ErrorCode::InternalError, + "GlobalISel CSE candidate has no register definition"); + } + if (Destination.reg() == *Source) + return &Instruction; + return MachineIRBuilder::buildCopy(Destination, *Source); +} + +Expected CSEMIRBuilder::memoize(MachineInstr &Instruction) const { + GISelCSEInfo *Info = getCSEInfo(); + if (Info == nullptr) + return &Instruction; + auto Inserted = Info->handleRecordedInstruction(Instruction); + if (!Inserted) + return std::unexpected(Inserted.error()); + return &Instruction; +} + +Expected +CSEMIRBuilder::buildInstr(Opcode InstructionOpcode, + std::span Destinations, + std::span Sources) const { + if (!canPerformCSE(InstructionOpcode)) + return MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + const bool CanGenerateCopies = + Destinations.size() == 1 || std::ranges::all_of(Destinations, [](const auto &Destination) { + return Destination.kind() == MachineIRBuilderResult::Kind::Type; + }); + if (!CanGenerateCopies) { + auto Built = MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources); + if (!Built) + return std::unexpected(Built.error()); + Info->handleRemoveInstruction(**Built); + return *Built; + } + + auto Existing = + Info->getMachineInstrIfExists(InstructionOpcode, Destinations, Sources, + std::span(), MachineInstrFlags(), *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + if (Destinations.size() == 1) + return generateCopyIfRequired(Destinations.front(), **Existing); + return *Existing; + } + + auto Built = MachineIRBuilder::buildInstr(InstructionOpcode, Destinations, Sources); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +Expected CSEMIRBuilder::buildConstant(MachineIRBuilderResult Destination, + APInt Value) const { + const Opcode ConstantOpcode = opcode(GenericOpcode::G_CONSTANT); + if (!canPerformCSE(ConstantOpcode)) + return MachineIRBuilder::buildConstant(Destination, std::move(Value)); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + auto Existing = Info->getConstantIfExists(Destination, Value, *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + return generateCopyIfRequired(Destination, **Existing); + } + + auto Built = MachineIRBuilder::buildConstant(Destination, std::move(Value)); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +Expected CSEMIRBuilder::buildSExtInReg(MachineIRBuilderResult Destination, + Register Source, std::uint32_t Width) const { + const Opcode InstructionOpcode = opcode(GenericOpcode::G_SEXT_INREG); + if (!canPerformCSE(InstructionOpcode)) + return MachineIRBuilder::buildSExtInReg(Destination, Source, Width); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + const std::array Destinations{Destination}; + const std::array Sources{Source}; + const std::array Immediates{static_cast(Width)}; + auto Existing = Info->getMachineInstrIfExists( + InstructionOpcode, std::span(Destinations), + std::span(Sources), std::span(Immediates), + MachineInstrFlags(), *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + return generateCopyIfRequired(Destination, **Existing); + } + + auto Built = MachineIRBuilder::buildSExtInReg(Destination, Source, Width); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +Expected CSEMIRBuilder::buildExtract(MachineIRBuilderResult Destination, + Register Source, std::uint64_t Offset) const { + if (Offset > static_cast(std::numeric_limits::max())) + return MachineIRBuilder::buildExtract(Destination, Source, Offset); + const Opcode InstructionOpcode = opcode(GenericOpcode::G_EXTRACT); + if (!canPerformCSE(InstructionOpcode)) + return MachineIRBuilder::buildExtract(Destination, Source, Offset); + MachineBasicBlock *Block = insertionBlock(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + + GISelCSEInfo *Info = getCSEInfo(); + const std::array Destinations{Destination}; + const std::array Sources{Source}; + const std::array Immediates{static_cast(Offset)}; + auto Existing = Info->getMachineInstrIfExists( + InstructionOpcode, std::span(Destinations), + std::span(Sources), std::span(Immediates), + MachineInstrFlags(), *Block); + if (!Existing) + return std::unexpected(Existing.error()); + if (*Existing != nullptr) { + auto Dominating = makeInstructionDominate(**Existing); + if (!Dominating) + return std::unexpected(Dominating.error()); + return generateCopyIfRequired(Destination, **Existing); + } + + auto Built = MachineIRBuilder::buildExtract(Destination, Source, Offset); + if (!Built) + return std::unexpected(Built.error()); + return memoize(**Built); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp index dfa4523..77c1b0c 100644 --- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp +++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp @@ -3,6 +3,8 @@ #include "rcc/CodeGen/GlobalISel/Legalizer.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/CSEInfo.h" +#include "rcc/CodeGen/GlobalISel/CSEMIRBuilder.h" #include "rcc/CodeGen/GlobalISel/GISelChangeObserver.h" #include "rcc/CodeGen/GlobalISel/GISelValueTracking.h" #include "rcc/CodeGen/GlobalISel/GISelWorkList.h" @@ -18,7 +20,9 @@ #include "rcc/CodeGen/TargetDescription.h" #include +#include #include +#include #include #include #include @@ -126,7 +130,7 @@ private: std::size_t NextSuccessor = 0; }; - const auto makeFrame = [](MachineBasicBlock &Block) { + const auto MakeFrame = [](MachineBasicBlock &Block) { TraversalFrame Frame; Frame.Block = &Block; for (const MachineSuccessor &Successor : Block.successors()) { @@ -156,13 +160,13 @@ private: for (MachineBasicBlock *Root : Roots) { if (!Visited.insert(Root).second) continue; - Stack.push_back(makeFrame(*Root)); + Stack.push_back(MakeFrame(*Root)); while (!Stack.empty()) { TraversalFrame &Frame = Stack.back(); if (Frame.NextSuccessor < Frame.Successors.size()) { MachineBasicBlock *Successor = Frame.Successors[Frame.NextSuccessor++]; if (Visited.insert(Successor).second) - Stack.push_back(makeFrame(*Successor)); + Stack.push_back(MakeFrame(*Successor)); continue; } PostOrder.push_back(Frame.Block); @@ -305,9 +309,17 @@ Expected Legalizer::runImplementation(MachineFunction &Functi InstructionWorklist.finalize(); LegalizerWorkListManager WorkListObserver(InstructionWorklist, ArtifactWorklist); - GISelObserverWrapper Observer(WorkListObserver); + GISelCSEInfo CSEInfo; + CSEInfo.setCSEConfig(getStandardCSEConfigForOpt(Optimization)); + auto CSEAnalysis = CSEInfo.analyze(Function); + if (!CSEAnalysis) + return std::unexpected( + withErrorContext(CSEAnalysis.error(), "GlobalISel CSE analysis failed: ")); + std::array AuxiliaryObservers{&WorkListObserver, &CSEInfo}; + GISelObserverWrapper Observer{std::span(AuxiliaryObservers)}; MachineFunctionDelegateInstaller ObserverInstaller(Function, Observer); - MachineIRBuilder Builder(Function, Target); + CSEMIRBuilder Builder(Function, Target); + Builder.setCSEInfo(&CSEInfo); LegalizerHelper Helper(Function, *Info, Observer, Builder); GISelValueTracking ValueTracking(Function, Target); LegalizationArtifactCombiner ArtifactCombiner(Builder, Function.registerInfo(), *Info, @@ -452,6 +464,12 @@ Expected Legalizer::runImplementation(MachineFunction &Functi } } while (!InstructionWorklist.empty()); + auto CSEValidation = CSEInfo.verify(); + if (!CSEValidation) { + return std::unexpected( + withErrorContext(CSEValidation.error(), "GlobalISel CSE verification failed: ")); + } + for (MachineInstr *Instruction : layoutInstructions(Function)) { const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); if (Descriptor == nullptr) diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp index def363a..a0b0981 100644 --- a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp +++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp @@ -69,21 +69,41 @@ struct ScalarLayout final { return Function.createMemOperand(std::move(Description)); } +[[nodiscard]] Expected resultRegister(MachineInstr &Instruction) { + const MachineOperand *Definition = Instruction.operandAt(0); + const Register *Result = Definition == nullptr ? nullptr : Definition->getIf(); + if (Result == nullptr || !Definition->isDef()) { + return makeUnexpected(ErrorCode::InternalError, + "machine IR builder returned an instruction without a register result"); + } + return *Result; +} + +[[nodiscard]] Expected buildConstantRegister(MachineIRBuilder &Builder, LowLevelType Type, + APInt Value) { + auto Built = Builder.buildConstant(Type, std::move(Value)); + if (!Built) + return std::unexpected(Built.error()); + return resultRegister(**Built); +} + +[[nodiscard]] Expected buildConstantRegister(MachineIRBuilder &Builder, LowLevelType Type, + std::int64_t Value) { + auto Immediate = APInt::fromSigned(Type.scalarBitWidth(), Value); + if (!Immediate) + return std::unexpected(Immediate.error()); + return buildConstantRegister(Builder, Type, std::move(*Immediate)); +} + [[nodiscard]] Expected buildConstantBefore(MachineIRBuilder &Builder, MachineInstr &Anchor, LowLevelType Type, std::uint64_t Value) { - auto Result = Builder.function().registerInfo().createVirtualRegister(Type); - if (!Result) - return std::unexpected(Result.error()); auto Immediate = APInt::fromUnsigned(Type.scalarBitWidth(), Value); if (!Immediate) return std::unexpected(Immediate.error()); if (auto Point = Builder.setInsertPointBefore(Anchor); !Point) return std::unexpected(Point.error()); - auto Built = Builder.buildConstant(*Result, std::move(*Immediate)); - if (!Built) - return std::unexpected(Built.error()); - return *Result; + return buildConstantRegister(Builder, Type, std::move(*Immediate)); } [[nodiscard]] Expected buildBinaryBefore(MachineIRBuilder &Builder, MachineInstr &Anchor, @@ -152,11 +172,12 @@ Expected LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction return std::unexpected(Point.error()); if (WideSize >= DestinationSize) { - auto Result = MRI.createVirtualRegister(WideType); + auto BuiltResult = MIRBuilder.buildZExt(WideType, *FirstSource); + if (!BuiltResult) + return std::unexpected(BuiltResult.error()); + auto Result = resultRegister(**BuiltResult); if (!Result) return std::unexpected(Result.error()); - if (auto Built = MIRBuilder.buildZExt(*Result, *FirstSource); !Built) - return std::unexpected(Built.error()); Register ResultRegister = *Result; for (std::size_t Index = 2; Index != Instruction.operandCount(); ++Index) { @@ -171,23 +192,22 @@ Expected LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction return makeUnexpected(ErrorCode::VerificationError, "G_MERGE_VALUES source types are inconsistent"); - auto ExtendedInput = MRI.createVirtualRegister(WideType); - auto ShiftAmount = MRI.createVirtualRegister(WideType); - auto ShiftedInput = MRI.createVirtualRegister(WideType); + auto BuiltExtendedInput = MIRBuilder.buildZExt(WideType, *Source); + if (!BuiltExtendedInput) + return std::unexpected(BuiltExtendedInput.error()); + auto ExtendedInput = resultRegister(**BuiltExtendedInput); if (!ExtendedInput) return std::unexpected(ExtendedInput.error()); + auto ShiftAmount = buildConstantRegister(MIRBuilder, WideType, + static_cast((Index - 1U) * PartSize)); if (!ShiftAmount) return std::unexpected(ShiftAmount.error()); + auto BuiltShiftedInput = MIRBuilder.buildShl(WideType, *ExtendedInput, *ShiftAmount); + if (!BuiltShiftedInput) + return std::unexpected(BuiltShiftedInput.error()); + auto ShiftedInput = resultRegister(**BuiltShiftedInput); if (!ShiftedInput) return std::unexpected(ShiftedInput.error()); - if (auto Built = MIRBuilder.buildZExt(*ExtendedInput, *Source); !Built) - return std::unexpected(Built.error()); - if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, - static_cast((Index - 1U) * PartSize)); - !Built) - return std::unexpected(Built.error()); - if (auto Built = MIRBuilder.buildShl(*ShiftedInput, *ExtendedInput, *ShiftAmount); !Built) - return std::unexpected(Built.error()); Register NextResult = *Destination; if (Index + 1U != Instruction.operandCount() || WideType != *DestinationType) { @@ -240,11 +260,12 @@ Expected LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction const std::uint64_t RequiredPartCount = MergeCount * WideSize; if (UnmergedRegisters.size() != RequiredPartCount) { - auto UndefRegister = MRI.createVirtualRegister(*GCDType); + auto BuiltUndef = MIRBuilder.buildUndef(*GCDType); + if (!BuiltUndef) + return std::unexpected(BuiltUndef.error()); + auto UndefRegister = resultRegister(**BuiltUndef); if (!UndefRegister) return std::unexpected(UndefRegister.error()); - if (auto Built = MIRBuilder.buildUndef(*UndefRegister); !Built) - return std::unexpected(Built.error()); while (UnmergedRegisters.size() != RequiredPartCount) UnmergedRegisters.push_back(*UndefRegister); } @@ -256,11 +277,12 @@ Expected LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction std::vector Parts( UnmergedRegisters.begin() + static_cast(Index * PartsPerGCD), UnmergedRegisters.begin() + static_cast((Index + 1U) * PartsPerGCD)); - auto MergeRegister = MRI.createVirtualRegister(WideType); + auto BuiltMerge = MIRBuilder.buildMergeLikeInstr(WideType, Parts); + if (!BuiltMerge) + return std::unexpected(BuiltMerge.error()); + auto MergeRegister = resultRegister(**BuiltMerge); if (!MergeRegister) return std::unexpected(MergeRegister.error()); - if (auto Built = MIRBuilder.buildMergeLikeInstr(*MergeRegister, Parts); !Built) - return std::unexpected(Built.error()); NewMergeRegisters.push_back(*MergeRegister); } @@ -268,11 +290,12 @@ Expected LegalizerHelper::widenScalarMergeValues(MachineInstr &Instruction if (auto Built = MIRBuilder.buildMergeLikeInstr(*Destination, NewMergeRegisters); !Built) return std::unexpected(Built.error()); } else { - auto FinalMerge = MRI.createVirtualRegister(*WideDestinationType); + auto BuiltFinalMerge = MIRBuilder.buildMergeLikeInstr(*WideDestinationType, NewMergeRegisters); + if (!BuiltFinalMerge) + return std::unexpected(BuiltFinalMerge.error()); + auto FinalMerge = resultRegister(**BuiltFinalMerge); if (!FinalMerge) return std::unexpected(FinalMerge.error()); - if (auto Built = MIRBuilder.buildMergeLikeInstr(*FinalMerge, NewMergeRegisters); !Built) - return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildTrunc(*Destination, *FinalMerge); !Built) return std::unexpected(Built.error()); } @@ -347,16 +370,13 @@ Expected LegalizerHelper::widenScalarUnmergeValues(MachineInstr &Instructi if (Destination == nullptr) return makeUnexpected(ErrorCode::VerificationError, "G_UNMERGE_VALUES requires register destinations"); - auto ShiftAmount = MRI.createVirtualRegister(*SourceType); auto ShiftedSource = MRI.createVirtualRegister(*SourceType); - if (!ShiftAmount) - return std::unexpected(ShiftAmount.error()); if (!ShiftedSource) return std::unexpected(ShiftedSource.error()); - if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, - static_cast(DestinationSize * Index)); - !Built) - return std::unexpected(Built.error()); + auto ShiftAmount = buildConstantRegister(MIRBuilder, *SourceType, + static_cast(DestinationSize * Index)); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); if (auto Built = MIRBuilder.buildLShr(*ShiftedSource, SourceRegister, *ShiftAmount); !Built) return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildTrunc(*Destination, *ShiftedSource); !Built) @@ -553,15 +573,20 @@ Expected LegalizerHelper::buildLCMMergePieces(LowLevelType Destina Register PadRegister; if (OriginalSourceCount < PartCount * SubPartCount) { - auto NewPad = MRI.createVirtualRegister(GCDType); - if (!NewPad) - return std::unexpected(NewPad.error()); - PadRegister = *NewPad; - Expected Built = PadStrategy == GenericOpcode::G_ZEXT - ? MIRBuilder.buildConstant(PadRegister, 0) - : MIRBuilder.buildUndef(PadRegister); - if (!Built) - return std::unexpected(Built.error()); + if (PadStrategy == GenericOpcode::G_ZEXT) { + auto Pad = buildConstantRegister(MIRBuilder, GCDType, 0); + if (!Pad) + return std::unexpected(Pad.error()); + PadRegister = *Pad; + } else { + auto Built = MIRBuilder.buildUndef(GCDType); + if (!Built) + return std::unexpected(Built.error()); + auto Pad = resultRegister(**Built); + if (!Pad) + return std::unexpected(Pad.error()); + PadRegister = *Pad; + } } std::vector Remerge(static_cast(PartCount)); @@ -580,15 +605,20 @@ Expected LegalizerHelper::buildLCMMergePieces(LowLevelType Destina } if (AllMergePartsArePadding && AllPadRegister.isNoRegister()) { - auto Pad = MRI.createVirtualRegister(NarrowType); - if (!Pad) - return std::unexpected(Pad.error()); - AllPadRegister = *Pad; - Expected Built = PadStrategy == GenericOpcode::G_ZEXT - ? MIRBuilder.buildConstant(AllPadRegister, 0) - : MIRBuilder.buildUndef(AllPadRegister); - if (!Built) - return std::unexpected(Built.error()); + if (PadStrategy == GenericOpcode::G_ZEXT) { + auto Pad = buildConstantRegister(MIRBuilder, NarrowType, 0); + if (!Pad) + return std::unexpected(Pad.error()); + AllPadRegister = *Pad; + } else { + auto Built = MIRBuilder.buildUndef(NarrowType); + if (!Built) + return std::unexpected(Built.error()); + auto Pad = resultRegister(**Built); + if (!Pad) + return std::unexpected(Pad.error()); + AllPadRegister = *Pad; + } } if (!AllPadRegister.isNoRegister()) { Remerge[static_cast(PartIndex)] = AllPadRegister; @@ -597,12 +627,12 @@ Expected LegalizerHelper::buildLCMMergePieces(LowLevelType Destina if (SubPartCount == 1) { Remerge[static_cast(PartIndex)] = SubMerge.front(); } else { - auto RemergeRegister = MRI.createVirtualRegister(NarrowType); - if (!RemergeRegister) - return std::unexpected(RemergeRegister.error()); - auto Built = MIRBuilder.buildMergeLikeInstr(*RemergeRegister, SubMerge); + auto Built = MIRBuilder.buildMergeLikeInstr(NarrowType, SubMerge); if (!Built) return std::unexpected(Built.error()); + auto RemergeRegister = resultRegister(**Built); + if (!RemergeRegister) + return std::unexpected(RemergeRegister.error()); Remerge[static_cast(PartIndex)] = *RemergeRegister; } if (AllMergePartsArePadding && AllPadRegister.isNoRegister()) @@ -701,6 +731,95 @@ Expected LegalizerHelper::widenScalarDst(MachineInstr &Instruction, LowLev return Operand->setRegister(*WideDestination); } +Expected LegalizerHelper::widenScalarAddSubOverflow(MachineInstr &Instruction, + std::size_t TypeIndex, + LowLevelType WideType) { + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "add/sub overflow widening requires type index zero"); + + const GenericOpcode Generic = static_cast(Instruction.opcode().value()); + GenericOpcode ArithmeticOpcode; + GenericOpcode ExtensionOpcode; + switch (Generic) { + case GenericOpcode::G_SADDO: + ArithmeticOpcode = GenericOpcode::G_ADD; + ExtensionOpcode = GenericOpcode::G_SEXT; + break; + case GenericOpcode::G_SSUBO: + ArithmeticOpcode = GenericOpcode::G_SUB; + ExtensionOpcode = GenericOpcode::G_SEXT; + break; + case GenericOpcode::G_UADDO: + ArithmeticOpcode = GenericOpcode::G_ADD; + ExtensionOpcode = GenericOpcode::G_ZEXT; + break; + case GenericOpcode::G_USUBO: + ArithmeticOpcode = GenericOpcode::G_SUB; + ExtensionOpcode = GenericOpcode::G_ZEXT; + break; + default: + return makeUnexpected(ErrorCode::InternalError, + "unexpected opcode during add/sub overflow widening"); + } + + const Register Destination = *Instruction.operandAt(0)->getIf(); + const Register Overflow = *Instruction.operandAt(1)->getIf(); + const Register Left = *Instruction.operandAt(2)->getIf(); + const Register Right = *Instruction.operandAt(3)->getIf(); + auto OriginalType = MRI.getType(Destination); + if (!OriginalType) + return std::unexpected(OriginalType.error()); + + auto WideLeft = MRI.createVirtualRegister(WideType); + auto WideRight = MRI.createVirtualRegister(WideType); + auto WideResult = MRI.createVirtualRegister(WideType); + auto TruncatedResult = MRI.createVirtualRegister(*OriginalType); + auto ExtendedResult = MRI.createVirtualRegister(WideType); + if (!WideLeft) + return std::unexpected(WideLeft.error()); + if (!WideRight) + return std::unexpected(WideRight.error()); + if (!WideResult) + return std::unexpected(WideResult.error()); + if (!TruncatedResult) + return std::unexpected(TruncatedResult.error()); + if (!ExtendedResult) + return std::unexpected(ExtendedResult.error()); + + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = MIRBuilder.buildInstr(opcode(ExtensionOpcode), {*WideLeft}, {Left}); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildInstr(opcode(ExtensionOpcode), {*WideRight}, {Right}); !Built) + return std::unexpected(Built.error()); + if (auto Built = + MIRBuilder.buildInstr(opcode(ArithmeticOpcode), {*WideResult}, {*WideLeft, *WideRight}); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildTrunc(*TruncatedResult, *WideResult); !Built) + return std::unexpected(Built.error()); + if (auto Built = + MIRBuilder.buildInstr(opcode(ExtensionOpcode), {*ExtendedResult}, {*TruncatedResult}); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::NotEqual, Overflow, *WideResult, *ExtendedResult); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildTrunc(Destination, *WideResult); !Built) + return std::unexpected(Built.error()); + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "add/sub overflow instruction became detached during widening"); + return Block->removeInstruction(Instruction); +} + Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size_t TypeIndex, LowLevelType WideType) { auto Query = LegalizerInfo::buildQuery(Instruction, Function, MIRBuilder.target()); @@ -713,14 +832,14 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size "scalar widening has an invalid type index or target type"); } - const auto widenSource = [&](std::size_t OperandIndex, GenericOpcode ExtensionOpcode) { + const auto WidenSource = [&](std::size_t OperandIndex, GenericOpcode ExtensionOpcode) { return widenScalarSrc(Instruction, WideType, OperandIndex, ExtensionOpcode); }; - const auto widenDestination = [&](std::size_t OperandIndex = 0, + const auto WidenDestination = [&](std::size_t OperandIndex = 0, GenericOpcode TruncOpcode = GenericOpcode::G_TRUNC) { return widenScalarDst(Instruction, WideType, OperandIndex, TruncOpcode); }; - const auto apply = [](Expected Result) -> Expected { + const auto Apply = [](Expected Result) -> Expected { if (!Result) return std::unexpected(Result.error()); return {}; @@ -745,9 +864,9 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "atomic RMW value widening has an invalid type index"); - if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -755,28 +874,28 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "compare-exchange widening has an invalid type index"); - if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(3, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; case GenericOpcode::G_ATOMIC_CMPXCHG_WITH_SUCCESS: if (TypeIndex == 0) { - if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(3, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenSource(4, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(4, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "compare-exchange success widening has an invalid type index"); - if (auto Result = apply(widenDestination(1)); !Result) + if (auto Result = Apply(WidenDestination(1)); !Result) return Result; break; @@ -804,11 +923,17 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size return std::unexpected(Extended.error()); if (auto Replaced = SourceOperand->setIntegerImmediate(std::move(*Extended)); !Replaced) return std::unexpected(Replaced.error()); - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } + case GenericOpcode::G_SADDO: + case GenericOpcode::G_SSUBO: + case GenericOpcode::G_UADDO: + case GenericOpcode::G_USUBO: + return widenScalarAddSubOverflow(Instruction, TypeIndex, WideType); + case GenericOpcode::G_ADD: case GenericOpcode::G_SUB: case GenericOpcode::G_MUL: @@ -818,11 +943,11 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "binary operation widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -834,11 +959,11 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "signed operation widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_SEXT)); !Result) return Result; - if (auto Result = apply(widenSource(2, GenericOpcode::G_SEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_SEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -850,11 +975,11 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "unsigned operation widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ZEXT)); !Result) return Result; - if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ZEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -867,16 +992,16 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size ExtensionOpcode = GenericOpcode::G_ZEXT; else if (Instruction.opcode() == opcode(GenericOpcode::G_ASHR)) ExtensionOpcode = GenericOpcode::G_SEXT; - if (auto Result = apply(widenSource(1, ExtensionOpcode)); !Result) + if (auto Result = Apply(WidenSource(1, ExtensionOpcode)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "shift widening has an invalid type index"); - if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ZEXT)); !Result) return Result; break; @@ -884,7 +1009,7 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size case GenericOpcode::G_ROTR: if (TypeIndex != 1) return makeUnexpected(ErrorCode::Unsupported, "rotate value widening is not defined"); - if (auto Result = apply(widenSource(2, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ZEXT)); !Result) return Result; break; @@ -893,9 +1018,9 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "unary operation widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; @@ -903,15 +1028,15 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, "absolute-value widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_SEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_SEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; case GenericOpcode::G_ICMP: if (TypeIndex == 0) { - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } @@ -952,27 +1077,27 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size IsSigned || Info.isSExtCheaperThanZExt(Query->Types[TypeIndex], WideType) ? GenericOpcode::G_SEXT : GenericOpcode::G_ZEXT; - if (auto Result = apply(widenSource(2, ExtensionOpcode)); !Result) + if (auto Result = Apply(WidenSource(2, ExtensionOpcode)); !Result) return Result; - if (auto Result = apply(widenSource(3, ExtensionOpcode)); !Result) + if (auto Result = Apply(WidenSource(3, ExtensionOpcode)); !Result) return Result; } break; case GenericOpcode::G_SELECT: if (TypeIndex == 0) { - if (auto Result = apply(widenSource(2, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(2, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenSource(3, GenericOpcode::G_ANYEXT)); !Result) + if (auto Result = Apply(WidenSource(3, GenericOpcode::G_ANYEXT)); !Result) return Result; - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "select widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_ZEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_ZEXT)); !Result) return Result; break; @@ -980,7 +1105,7 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size if (TypeIndex != 1) return makeUnexpected(ErrorCode::Unsupported, "floating-point extension destination widening is not defined"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_FPEXT)); !Result) return Result; break; @@ -990,28 +1115,28 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size case GenericOpcode::G_INTRINSIC_LLRINT: case GenericOpcode::G_IS_FPCLASS: if (TypeIndex == 0) { - if (auto Result = apply(widenDestination()); !Result) + if (auto Result = Apply(WidenDestination()); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "floating-to-integer widening has an invalid type index"); - if (auto Result = apply(widenSource(1, GenericOpcode::G_FPEXT)); !Result) + if (auto Result = Apply(WidenSource(1, GenericOpcode::G_FPEXT)); !Result) return Result; break; case GenericOpcode::G_SITOFP: case GenericOpcode::G_UITOFP: if (TypeIndex == 0) { - if (auto Result = apply(widenDestination(0, GenericOpcode::G_FPTRUNC)); !Result) + if (auto Result = Apply(WidenDestination(0, GenericOpcode::G_FPTRUNC)); !Result) return Result; break; } if (TypeIndex != 1) return makeUnexpected(ErrorCode::VerificationError, "integer-to-floating widening has an invalid type index"); - if (auto Result = apply(widenSource(1, Instruction.opcode() == opcode(GenericOpcode::G_SITOFP) + if (auto Result = Apply(WidenSource(1, Instruction.opcode() == opcode(GenericOpcode::G_SITOFP) ? GenericOpcode::G_SEXT : GenericOpcode::G_ZEXT)); !Result) @@ -1275,15 +1400,19 @@ Expected LegalizerHelper::lowerVAArg(MachineInstr &Instruction) { auto DestinationInfo = MRI.virtualRegisterInfo(*Destination); auto PointerInfo = MRI.virtualRegisterInfo(*ListPointer); auto RequestedAlignment = signedImmediate(*AlignmentOperand); - if (!DestinationInfo || !PointerInfo || !DestinationInfo->get().Type || - !PointerInfo->get().Type || !RequestedAlignment || *RequestedAlignment <= 0 || + if (!DestinationInfo || !PointerInfo) + return makeUnexpected(ErrorCode::VerificationError, "G_VAARG has invalid register information"); + const std::optional &DestinationTypeInfo = DestinationInfo->get().Type; + const std::optional &PointerTypeInfo = PointerInfo->get().Type; + if (!DestinationTypeInfo.has_value() || !PointerTypeInfo.has_value() || !RequestedAlignment || + *RequestedAlignment <= 0 || !std::has_single_bit(static_cast(*RequestedAlignment))) { return makeUnexpected(ErrorCode::VerificationError, "G_VAARG has invalid type or alignment information"); } - const LowLevelType DestinationType = *DestinationInfo->get().Type; - const LowLevelType PointerType = *PointerInfo->get().Type; + const LowLevelType DestinationType = DestinationTypeInfo.value(); + const LowLevelType PointerType = PointerTypeInfo.value(); const auto DestinationLayout = scalarLayout(DestinationType); const auto PointerLayout = scalarLayout(PointerType); if (!DestinationLayout || !PointerLayout || !PointerType.isPointer()) { @@ -1415,6 +1544,9 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, return lowerAbsDiffToMinMax(Instruction); return lowerAbsDiffToSelect(Instruction); } + case GenericOpcode::G_SADDO: + case GenericOpcode::G_SSUBO: + return lowerSignedAddSubOverflow(Instruction); case GenericOpcode::G_SEXT_INREG: { const Register Destination = *Instruction.operandAt(0)->getIf(); const Register Source = *Instruction.operandAt(1)->getIf(); @@ -1425,18 +1557,16 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, if (!Type) return std::unexpected(Type.error()); - auto ShiftAmount = MRI.createVirtualRegister(*Type); auto Temporary = MRI.createVirtualRegister(*Type); - if (!ShiftAmount) - return std::unexpected(ShiftAmount.error()); if (!Temporary) return std::unexpected(Temporary.error()); if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) return std::unexpected(Point.error()); const std::int64_t Shift = static_cast(Type->scalarBitWidth()) - *SizeInBits; - if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, Shift); !Built) - return std::unexpected(Built.error()); + auto ShiftAmount = buildConstantRegister(MIRBuilder, *Type, Shift); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); if (auto Built = MIRBuilder.buildShl(*Temporary, Source, *ShiftAmount); !Built) return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildAShr(Destination, *Temporary, *ShiftAmount); !Built) @@ -1490,7 +1620,6 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, auto TemporaryResult = MRI.createVirtualRegister(*ResultType); auto Carry = MRI.createVirtualRegister(*ConditionType); auto ExtendedCarryIn = MRI.createVirtualRegister(*ResultType); - auto Zero = MRI.createVirtualRegister(*ResultType); auto ResultIsZero = MRI.createVirtualRegister(*ConditionType); auto SecondCarry = MRI.createVirtualRegister(*ConditionType); if (!NewResult) @@ -1501,8 +1630,6 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, return std::unexpected(Carry.error()); if (!ExtendedCarryIn) return std::unexpected(ExtendedCarryIn.error()); - if (!Zero) - return std::unexpected(Zero.error()); if (!ResultIsZero) return std::unexpected(ResultIsZero.error()); if (!SecondCarry) @@ -1519,8 +1646,9 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildAdd(*NewResult, *TemporaryResult, *ExtendedCarryIn); !Built) return std::unexpected(Built.error()); - if (auto Built = MIRBuilder.buildConstant(*Zero, 0); !Built) - return std::unexpected(Built.error()); + auto Zero = buildConstantRegister(MIRBuilder, *ResultType, 0); + if (!Zero) + return std::unexpected(Zero.error()); if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::Equal, *ResultIsZero, *NewResult, *Zero); !Built) @@ -1569,7 +1697,6 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, auto TemporaryResult = MRI.createVirtualRegister(*ResultType); auto Borrow = MRI.createVirtualRegister(*ConditionType); auto ExtendedBorrowIn = MRI.createVirtualRegister(*ResultType); - auto Zero = MRI.createVirtualRegister(*ResultType); auto TemporaryResultIsZero = MRI.createVirtualRegister(*ConditionType); auto SecondBorrow = MRI.createVirtualRegister(*ConditionType); if (!TemporaryResult) @@ -1578,8 +1705,6 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, return std::unexpected(Borrow.error()); if (!ExtendedBorrowIn) return std::unexpected(ExtendedBorrowIn.error()); - if (!Zero) - return std::unexpected(Zero.error()); if (!TemporaryResultIsZero) return std::unexpected(TemporaryResultIsZero.error()); if (!SecondBorrow) @@ -1596,8 +1721,9 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildSub(Result, *TemporaryResult, *ExtendedBorrowIn); !Built) return std::unexpected(Built.error()); - if (auto Built = MIRBuilder.buildConstant(*Zero, 0); !Built) - return std::unexpected(Built.error()); + auto Zero = buildConstantRegister(MIRBuilder, *ResultType, 0); + if (!Zero) + return std::unexpected(Zero.error()); if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::Equal, *TemporaryResultIsZero, *TemporaryResult, *Zero); !Built) @@ -1630,11 +1756,8 @@ Expected LegalizerHelper::lowerAbsToAddXor(MachineInstr &Instruction) { if (!Type) return std::unexpected(Type.error()); - auto ShiftAmount = MRI.createVirtualRegister(*Type); auto Shift = MRI.createVirtualRegister(*Type); auto Add = MRI.createVirtualRegister(*Type); - if (!ShiftAmount) - return std::unexpected(ShiftAmount.error()); if (!Shift) return std::unexpected(Shift.error()); if (!Add) @@ -1642,8 +1765,10 @@ Expected LegalizerHelper::lowerAbsToAddXor(MachineInstr &Instruction) { if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) return std::unexpected(Point.error()); - if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, Type->scalarBitWidth() - 1U); !Built) - return std::unexpected(Built.error()); + auto ShiftAmount = buildConstantRegister(MIRBuilder, *Type, + static_cast(Type->scalarBitWidth() - 1U)); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); if (auto Built = MIRBuilder.buildAShr(*Shift, Source, *ShiftAmount); !Built) return std::unexpected(Built.error()); if (auto Built = MIRBuilder.buildAdd(*Add, Source, *Shift); !Built) @@ -1736,6 +1861,76 @@ Expected LegalizerHelper::lowerAbsDiffToMinMax(MachineInstr &Instruction) return Block->removeInstruction(Instruction); } +Expected LegalizerHelper::lowerSignedAddSubOverflow(MachineInstr &Instruction) { + const bool IsAdd = Instruction.opcode() == opcode(GenericOpcode::G_SADDO); + const Register Destination = *Instruction.operandAt(0)->getIf(); + const Register Overflow = *Instruction.operandAt(1)->getIf(); + const Register Left = *Instruction.operandAt(2)->getIf(); + const Register Right = *Instruction.operandAt(3)->getIf(); + auto Type = MRI.getType(Destination); + auto BooleanType = MRI.getType(Overflow); + if (!Type) + return std::unexpected(Type.error()); + if (!BooleanType) + return std::unexpected(BooleanType.error()); + + auto Result = MRI.cloneVirtualRegister(Destination); + auto FirstComparison = MRI.createVirtualRegister(*BooleanType); + auto SecondComparison = MRI.createVirtualRegister(*BooleanType); + if (!Result) + return std::unexpected(Result.error()); + if (!FirstComparison) + return std::unexpected(FirstComparison.error()); + if (!SecondComparison) + return std::unexpected(SecondComparison.error()); + + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = IsAdd ? MIRBuilder.buildAdd(*Result, Left, Right) + : MIRBuilder.buildSub(*Result, Left, Right); + !Built) { + return std::unexpected(Built.error()); + } + auto Zero = buildConstantRegister(MIRBuilder, *Type, 0); + if (!Zero) + return std::unexpected(Zero.error()); + if (IsAdd) { + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *FirstComparison, *Result, Left); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *SecondComparison, Right, *Zero); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildXor(Overflow, *SecondComparison, *FirstComparison); !Built) + return std::unexpected(Built.error()); + } else { + if (auto Built = + MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *FirstComparison, Left, Right); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildICmp(IntegerPredicate::SignedLessThan, *SecondComparison, + *Result, *Zero); + !Built) { + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildXor(Overflow, *FirstComparison, *SecondComparison); !Built) + return std::unexpected(Built.error()); + } + if (auto Built = MIRBuilder.buildCopy(Destination, *Result); !Built) + return std::unexpected(Built.error()); + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "signed add/sub overflow instruction became detached during lowering"); + return Block->removeInstruction(Instruction); +} + Expected LegalizerHelper::legalize(MachineInstr &Instruction, const LegalizationDecision &Decision) { if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp index c4cf946..ee7f856 100644 --- a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp +++ b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp @@ -295,7 +295,7 @@ LegalizeRuleSet &LegalizeRuleSet::clampScalar(std::size_t TypeIndex, LowLevelTyp LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex, std::size_t ReferenceTypeIndex) { - const auto changeToReference = [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) { + const auto ChangeToReference = [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) { return std::pair{TypeIndex, scalarType(Query.Types[ReferenceTypeIndex].scalarBitWidth())}; }; widenScalarIf( @@ -306,7 +306,7 @@ LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex, Query.Types[TypeIndex].scalarBitWidth() < Query.Types[ReferenceTypeIndex].scalarBitWidth(); }, - changeToReference); + ChangeToReference); return narrowScalarIf( [TypeIndex, ReferenceTypeIndex](const LegalizationQuery &Query) { return TypeIndex < Query.Types.size() && ReferenceTypeIndex < Query.Types.size() && @@ -315,7 +315,7 @@ LegalizeRuleSet &LegalizeRuleSet::scalarSameSizeAs(std::size_t TypeIndex, Query.Types[TypeIndex].scalarBitWidth() > Query.Types[ReferenceTypeIndex].scalarBitWidth(); }, - changeToReference); + ChangeToReference); } LegalizeRuleSet &LegalizeRuleSet::lowerIfMemSizeNotByteSizePow2(std::size_t MemoryIndex) { @@ -327,6 +327,10 @@ LegalizeRuleSet &LegalizeRuleSet::lowerIfMemSizeNotByteSizePow2(std::size_t Memo }); } +LegalizeRuleSet &LegalizeRuleSet::custom() { + return customIf([](const LegalizationQuery &) { return true; }); +} + LegalizeRuleSet &LegalizeRuleSet::alwaysLegal() { return legalIf([](const LegalizationQuery &) { return true; }); } @@ -401,13 +405,15 @@ Expected LegalizerInfo::buildQuery(const MachineInstr &Instru auto Info = Function.registerInfo().virtualRegisterInfo(*Reg); if (!Info) return std::unexpected(Info.error()); - if (!Info->get().Type) + const std::optional &RegisterType = Info->get().Type; + if (!RegisterType.has_value()) return makeUnexpected(ErrorCode::VerificationError, "legalization type operand has no LowLevelType"); - if (OptionalTypes[TypeIndex] && *OptionalTypes[TypeIndex] != *Info->get().Type) + std::optional &ExistingType = OptionalTypes[TypeIndex]; + if (ExistingType.has_value() && ExistingType.value() != RegisterType.value()) return makeUnexpected(ErrorCode::VerificationError, "legalization type operands disagree within one type index"); - OptionalTypes[TypeIndex] = *Info->get().Type; + ExistingType = RegisterType.value(); TypeOperands[TypeIndex].push_back(Index); } -- cgit v1.2.3