From f99ef4322a7a2c09380fff61f88ab9440f05a92c Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Fri, 7 Aug 2026 22:06:28 +0800 Subject: [CodeGen] Complete machine pass and ABI lowering infrastructure --- backend/lib/CodeGen/CMakeLists.txt | 16 + backend/lib/CodeGen/GenericOpcodes.cpp | 1498 ++++++++++++++++++++++++++++ backend/lib/CodeGen/MachineAnalyses.cpp | 850 ++++++++++++++++ backend/lib/CodeGen/MachineIRBuilder.cpp | 13 + backend/lib/CodeGen/MachinePass.cpp | 1370 +++++++++++++++++++++++++ backend/lib/CodeGen/TargetCallLowering.cpp | 353 +++++++ 6 files changed, 4100 insertions(+) create mode 100644 backend/lib/CodeGen/GenericOpcodes.cpp create mode 100644 backend/lib/CodeGen/MachineAnalyses.cpp create mode 100644 backend/lib/CodeGen/MachinePass.cpp create mode 100644 backend/lib/CodeGen/TargetCallLowering.cpp (limited to 'backend/lib/CodeGen') diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 34e9ef6..5a12055 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -3,6 +3,7 @@ set( RCCBackendCodeGenSources CompilationUnit.cpp + GenericOpcodes.cpp GenericConstant.cpp InstructionDescriptor.cpp LowLevelType.cpp @@ -19,11 +20,13 @@ set( MachineFunctionCloner.cpp MachineIRTypes.cpp MachineIRBuilder.cpp + MachineAnalyses.cpp MachineInstr.cpp MachineJumpTableInfo.cpp MachineMemOperand.cpp MachineMetadata.cpp MachineOperand.cpp + MachinePass.cpp MachineRegisterInfo.cpp MachineVerifier.cpp MachineFunctionProperties.cpp @@ -31,6 +34,7 @@ set( Register.cpp RegisterMask.cpp TargetConstant.cpp + TargetCallLowering.cpp TargetDescription.cpp TargetFunctionState.cpp TargetMIRTextInfo.cpp @@ -39,6 +43,7 @@ set( set( RCCBackendCodeGenHeaders "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CompilationUnit.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericOpcodes.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericConstant.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InstructionDescriptor.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h" @@ -55,11 +60,13 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionCloner.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineIRTypes.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineIRBuilder.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineAnalyses.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineInstr.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineJumpTableInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMetadata.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOperand.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePass.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineVerifier.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h" @@ -68,6 +75,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/StableID.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetConstant.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetCallLowering.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetDescription.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetFunctionState.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetMIRTextInfo.h" @@ -104,6 +112,7 @@ install( rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/CompilationUnit.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/GenericOpcodes.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GenericConstant.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptor.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp" @@ -120,11 +129,13 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionCloner.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilder.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineAnalyses.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" @@ -132,6 +143,7 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetConstant.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/TargetCallLowering.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetDescription.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetFunctionState.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetMIRTextInfo.cpp" @@ -140,6 +152,7 @@ rcc_backend_register_format_files( ) rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/CompilationUnit.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/GenericOpcodes.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GenericConstant.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptor.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp" @@ -156,11 +169,13 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionCloner.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilder.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachineAnalyses.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" @@ -168,6 +183,7 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetConstant.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/TargetCallLowering.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetDescription.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetFunctionState.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetMIRTextInfo.cpp" diff --git a/backend/lib/CodeGen/GenericOpcodes.cpp b/backend/lib/CodeGen/GenericOpcodes.cpp new file mode 100644 index 0000000..0b0e0fe --- /dev/null +++ b/backend/lib/CodeGen/GenericOpcodes.cpp @@ -0,0 +1,1498 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GenericOpcodes.h" + +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +using GO = GenericOpcode; + +[[nodiscard]] Expected verifyGenericExplicitOperands(Opcode InstructionOpcode, + std::span Operands, + const MachineRegisterInfo &RegInfo); +[[nodiscard]] Expected verifyGenericInstructionSemantics(const MachineInstr &Instruction, + const MachineRegisterInfo &RegInfo); + +[[nodiscard]] LLTKindSet anyValueKinds() { + return {LLT::Kind::AnyScalar, LLT::Kind::Integer, LLT::Kind::Float, + LLT::Kind::Pointer, LLT::Kind::VectorAny, LLT::Kind::VectorInteger, + LLT::Kind::VectorFloat, LLT::Kind::VectorPointer}; +} + +[[nodiscard]] LLTKindSet integerKinds() { + return {LLT::Kind::AnyScalar, LLT::Kind::Integer, LLT::Kind::VectorAny, LLT::Kind::VectorInteger}; +} + +[[nodiscard]] LLTKindSet scalarIntegerKinds() { + return {LLT::Kind::AnyScalar, LLT::Kind::Integer}; +} + +[[nodiscard]] LLTKindSet scalarValueKinds() { + return {LLT::Kind::AnyScalar, LLT::Kind::Integer, LLT::Kind::Float, LLT::Kind::Pointer}; +} + +[[nodiscard]] LLTKindSet floatingKinds() { + return {LLT::Kind::AnyScalar, LLT::Kind::Float, LLT::Kind::VectorAny, LLT::Kind::VectorFloat}; +} + +[[nodiscard]] LLTKindSet scalarFloatingKinds() { + return {LLT::Kind::AnyScalar, LLT::Kind::Float}; +} + +[[nodiscard]] LLTKindSet pointerKinds() { + return {LLT::Kind::Pointer, LLT::Kind::VectorPointer}; +} + +[[nodiscard]] LLTKindSet scalarPointerKinds() { + return {LLT::Kind::Pointer}; +} + +[[nodiscard]] LLTKindSet vectorKinds() { + return {LLT::Kind::VectorAny, LLT::Kind::VectorInteger, LLT::Kind::VectorFloat, + LLT::Kind::VectorPointer}; +} + +[[nodiscard]] OperandKindSet allOperandKinds() { + return {MachineOperand::Kind::Register, + MachineOperand::Kind::Immediate, + MachineOperand::Kind::IntegerImmediate, + MachineOperand::Kind::FloatingImmediate, + MachineOperand::Kind::BasicBlock, + MachineOperand::Kind::FrameIndex, + MachineOperand::Kind::ConstantPoolIndex, + MachineOperand::Kind::JumpTableIndex, + MachineOperand::Kind::GlobalSymbol, + MachineOperand::Kind::ExternalSymbol, + MachineOperand::Kind::BlockAddress, + MachineOperand::Kind::RegisterMask, + MachineOperand::Kind::LiveOutRegisterMask, + MachineOperand::Kind::Metadata, + MachineOperand::Kind::TargetIndex, + MachineOperand::Kind::MCSymbol, + MachineOperand::Kind::CFIIndex, + MachineOperand::Kind::Intrinsic, + MachineOperand::Kind::Predicate, + MachineOperand::Kind::ShuffleMask, + MachineOperand::Kind::DebugInstrRef, + MachineOperand::Kind::LaneMask}; +} + +[[nodiscard]] OperandDescriptor typedRegister(RegisterOperandRole Role, LLTKindSet Kinds, + std::uint16_t Group) { + OperandDescriptor Result; + Result.Kinds = {MachineOperand::Kind::Register}; + Result.RegisterRole = Role; + Result.TypeConstraint = OperandTypeConstraint{std::move(Kinds), Group}; + return Result; +} + +[[nodiscard]] OperandDescriptor untypedRegister(RegisterOperandRole Role, bool AllowSubReg = true) { + OperandDescriptor Result; + Result.Kinds = {MachineOperand::Kind::Register}; + Result.RegisterRole = Role; + Result.AllowSubReg = AllowSubReg; + return Result; +} + +[[nodiscard]] OperandDescriptor operand(OperandKindSet Kinds) { + OperandDescriptor Result; + Result.Kinds = Kinds; + if (Kinds.contains(MachineOperand::Kind::Register)) { + Result.RegisterRole = RegisterOperandRole::Any; + Result.AllowSubReg = true; + } + return Result; +} + +[[nodiscard]] OperandDescriptor kind(MachineOperand::Kind Kind) { + return operand(OperandKindSet{Kind}); +} + +[[nodiscard]] OperandDescriptor immediate() { + return operand({MachineOperand::Kind::Immediate, MachineOperand::Kind::IntegerImmediate}); +} + +[[nodiscard]] OperandDescriptor symbol() { + return operand({MachineOperand::Kind::GlobalSymbol, MachineOperand::Kind::ExternalSymbol, + MachineOperand::Kind::MCSymbol}); +} + +[[nodiscard]] OperandDescriptor anyOperand() { + return operand(allOperandKinds()); +} + +[[nodiscard]] OperandDescriptor repeated(OperandDescriptor Descriptor) { + Descriptor.VariadicGroup = true; + return Descriptor; +} + +class DescriptorRegistry final { +public: + DescriptorRegistry() { + Descriptors.reserve(CorePseudoOpcodeCount + GenericOpcodeCount); + Configured.reserve(CorePseudoOpcodeCount + GenericOpcodeCount); +#define RCC_CORE_OPCODE(Name) add(GO::Name, #Name, false); +#define RCC_GENERIC_OPCODE(Name) add(GO::Name, #Name, true); +#include "rcc/CodeGen/GenericOpcode.def" +#undef RCC_GENERIC_OPCODE +#undef RCC_CORE_OPCODE + } + + void configure(std::initializer_list Opcodes, std::vector Operands, + std::size_t NumDefs, std::initializer_list Flags = {}, + bool Variadic = false, std::size_t MinimumRepetitions = 0, + bool RequiresMemoryOperands = false, PseudoOwner Owner = PseudoOwner::None, + PipelineStage Deadline = PipelineStage::Emission, + bool AllowExtraImplicitOperands = false) { + for (const GO OpcodeValue : Opcodes) { + const std::size_t Index = index(OpcodeValue); + if (Index >= Descriptors.size() || Configured[Index]) + std::terminate(); + Configured[Index] = true; + InstructionDescriptor &Descriptor = Descriptors[Index]; + Descriptor.Operands = Operands; + Descriptor.NumExplicitDefs = NumDefs; + Descriptor.Variadic = Variadic; + Descriptor.MinimumVariadicRepetitions = MinimumRepetitions; + Descriptor.Flags = {}; + Descriptor.Flags.set(isGenericOpcode(Descriptor.InstructionOpcode) ? InstructionFlag::Generic + : InstructionFlag::Pseudo); + Descriptor.Flags.set(InstructionFlag::AllowedPreLegalizer); + for (const InstructionFlag Flag : Flags) + Descriptor.Flags.set(Flag); + Descriptor.RequiresMemoryOperands = RequiresMemoryOperands; + Descriptor.Owner = Owner; + Descriptor.Deadline = Deadline; + Descriptor.AllowExtraImplicitOperands = AllowExtraImplicitOperands; + if (isGenericOpcode(Descriptor.InstructionOpcode)) { + Descriptor.VerifyExplicitOperands = &verifyGenericExplicitOperands; + Descriptor.VerifyInstructionSemantics = &verifyGenericInstructionSemantics; + } + } + } + + void addFlag(std::initializer_list Opcodes, InstructionFlag Flag) { + for (const GO OpcodeValue : Opcodes) { + const std::size_t Index = index(OpcodeValue); + if (Index >= Descriptors.size() || !Configured[Index]) + std::terminate(); + Descriptors[Index].Flags.set(Flag); + } + } + + void tie(GO OpcodeValue, std::size_t Left, std::size_t Right) { + InstructionDescriptor &Descriptor = Descriptors[index(OpcodeValue)]; + if (!Configured[index(OpcodeValue)] || Left >= Descriptor.Operands.size() || + Right >= Descriptor.Operands.size()) { + std::terminate(); + } + Descriptor.Operands[Left].DefaultTiedOperand = Right; + Descriptor.Operands[Right].DefaultTiedOperand = Left; + } + + [[nodiscard]] std::vector take() { + if (!std::ranges::all_of(Configured, [](bool Value) { return Value; })) + std::terminate(); + return std::move(Descriptors); + } + +private: + static std::size_t index(GO OpcodeValue) { + const std::size_t Value = static_cast(OpcodeValue); + if (Value < static_cast(GO::CORE_PSEUDO_END)) + return Value - static_cast(GO::PHI); + return CorePseudoOpcodeCount + Value - static_cast(GO::G_ASSERT_SEXT); + } + + void add(GO OpcodeValue, std::string_view Name, bool IsGeneric) { + InstructionDescriptor Descriptor; + Descriptor.InstructionOpcode = opcode(OpcodeValue); + Descriptor.Name = Name; + if (IsGeneric != isGenericOpcode(Descriptor.InstructionOpcode)) + std::terminate(); + Descriptors.push_back(std::move(Descriptor)); + Configured.push_back(false); + } + + std::vector Descriptors; + std::vector Configured; +}; + +[[nodiscard]] Expected semanticError(std::string_view Message) { + return makeUnexpected(ErrorCode::VerificationError, std::string(Message)); +} + +[[nodiscard]] std::optional plainImmediate(const MachineOperand &Operand) noexcept { + const auto *Value = Operand.getIf(); + if (Operand.kind() != MachineOperand::Kind::Immediate || Value == nullptr) + return std::nullopt; + return *Value; +} + +[[nodiscard]] std::uint64_t minimumBitWidth(LLT Type) noexcept { + const std::uint64_t Elements = Type.isVector() ? Type.minimumElementCount() : 1; + return Elements * Type.scalarBitWidth(); +} + +[[nodiscard]] std::uint64_t minimumStoreBytes(LLT Type) noexcept { + return (minimumBitWidth(Type) + 7) / 8; +} + +[[nodiscard]] LLT scalarElementType(LLT Type) noexcept { + if (const auto Element = Type.scalarElementType()) + return *Element; + return Type; +} + +[[nodiscard]] bool hasSameShape(LLT Left, LLT Right) noexcept { + if (Left.isVector() != Right.isVector()) + return false; + if (!Left.isVector()) + return true; + return Left.isScalableVector() == Right.isScalableVector() && + Left.minimumElementCount() == Right.minimumElementCount(); +} + +[[nodiscard]] bool isI1(LLT Type) noexcept { + return Type.isIntegerOrIntegerVector() && Type.scalarBitWidth() == 1; +} + +[[nodiscard]] Expected requireSameShape(LLT Left, LLT Right, std::string_view Message) { + if (!hasSameShape(Left, Right)) + return semanticError(Message); + return {}; +} + +[[nodiscard]] Expected requireI1WithShape(LLT Condition, LLT Value, + bool AllowScalarCondition) { + if (!isI1(Condition)) + return semanticError("generic condition or status result must use an i1 LLT"); + if (AllowScalarCondition && !Condition.isVector()) + return {}; + return requireSameShape(Condition, Value, + "generic condition or status vector shape does not match its value"); +} + +[[nodiscard]] Expected verifyGenericExplicitOperands(Opcode InstructionOpcode, + std::span Operands, + const MachineRegisterInfo &RegInfo) { + std::vector> Types(Operands.size()); + bool SawNonDefinition = false; + for (std::size_t Index = 0; Index < Operands.size(); ++Index) { + const MachineOperand &Operand = Operands[Index]; + if (!Operand.isRegister()) { + SawNonDefinition = true; + continue; + } + + if (Operand.isDef() == Operand.isUse()) + return semanticError("generic register operand must be either a pure definition or use"); + if (Operand.isDef()) { + if (SawNonDefinition) + return semanticError("generic register definitions must form the explicit operand prefix"); + } else { + SawNonDefinition = true; + if (Operand.registerFlags().has(RegisterOperandFlag::Undef)) + return semanticError("generic virtual-register uses cannot carry the undef flag"); + } + + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || !Reg->isVirtual()) + return semanticError("generic instruction register operands must be virtual registers"); + auto Info = RegInfo.virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + if (!Info->get().Type) + return semanticError("generic virtual register is missing its LLT"); + Types[Index] = *Info->get().Type; + } + + const auto TypeAt = [&Types](std::size_t Index) -> LLT { return *Types[Index]; }; + const GO Generic = static_cast(InstructionOpcode.value()); + + const auto VerifyWidthChange = [&](bool IsExtension) -> Expected { + const LLT Dst = TypeAt(0); + const LLT Src = TypeAt(1); + if (auto Shape = + requireSameShape(Dst, Src, "generic width conversion must preserve vector shape"); + !Shape) { + return Shape; + } + if ((IsExtension && Dst.scalarBitWidth() <= Src.scalarBitWidth()) || + (!IsExtension && Dst.scalarBitWidth() >= Src.scalarBitWidth())) { + return semanticError(IsExtension + ? "generic extension destination must be wider than its source" + : "generic truncation destination must be narrower than its source"); + } + return {}; + }; + + const auto VerifyImmediateBitWidth = [&](std::size_t ImmediateIndex, std::size_t TypeIndex, + bool StrictlySmaller) -> Expected { + const auto Value = plainImmediate(Operands[ImmediateIndex]); + if (!Value || *Value <= 0) + return semanticError("generic bit-width immediate must be a positive machine immediate"); + const std::uint64_t Width = TypeAt(TypeIndex).scalarBitWidth(); + if ((StrictlySmaller && static_cast(*Value) >= Width) || + (!StrictlySmaller && static_cast(*Value) > Width)) { + return semanticError("generic bit-width immediate exceeds its register element width"); + } + return {}; + }; + + switch (Generic) { + case GO::G_ASSERT_SEXT: + case GO::G_ASSERT_ZEXT: + case GO::G_SEXT_INREG: + return VerifyImmediateBitWidth(2, 1, true); + case GO::G_ASSERT_ALIGN: { + const auto AlignmentValue = plainImmediate(Operands[2]); + if (!AlignmentValue || *AlignmentValue <= 0 || + !std::has_single_bit(static_cast(*AlignmentValue))) { + return semanticError("G_ASSERT_ALIGN requires a positive power-of-two alignment"); + } + return {}; + } + case GO::G_CONSTANT: { + if (const auto *Payload = Operands[1].getIf(); + Payload != nullptr && Payload->Value.bitWidth() != TypeAt(0).scalarBitWidth()) { + return semanticError("G_CONSTANT integer width must match its destination LLT"); + } + return {}; + } + case GO::G_FCONSTANT: { + const auto *Payload = Operands[1].getIf(); + if (Payload == nullptr || Payload->Bits.semantics() != TypeAt(0).floatSemantics()) + return semanticError("G_FCONSTANT semantics must match its destination LLT"); + return {}; + } + case GO::G_BITCAST: { + const LLT Dst = TypeAt(0); + const LLT Src = TypeAt(1); + if (Dst.isPointerOrPointerVector() != Src.isPointerOrPointerVector()) + return semanticError("G_BITCAST cannot cross the pointer/non-pointer boundary"); + if (minimumBitWidth(Dst) != minimumBitWidth(Src) || + Dst.isScalableVector() != Src.isScalableVector()) { + return semanticError("G_BITCAST source and destination sizes must match"); + } + if (Dst == Src) + return semanticError("G_BITCAST must change the LLT"); + return {}; + } + case GO::G_INTTOPTR: + case GO::G_PTRTOINT: + return requireSameShape(TypeAt(0), TypeAt(1), + "pointer/integer conversion must preserve vector shape"); + case GO::G_ADDRSPACE_CAST: { + const LLT Dst = TypeAt(0); + const LLT Src = TypeAt(1); + if (auto Shape = requireSameShape(Dst, Src, "G_ADDRSPACE_CAST must preserve vector shape"); + !Shape) { + return Shape; + } + if (Dst.addressSpace() == Src.addressSpace()) + return semanticError("G_ADDRSPACE_CAST must change the address space"); + return {}; + } + case GO::G_ANYEXT: + case GO::G_SEXT: + case GO::G_ZEXT: + case GO::G_FPEXT: + return VerifyWidthChange(true); + case GO::G_TRUNC: + case GO::G_TRUNC_SSAT_S: + case GO::G_TRUNC_SSAT_U: + case GO::G_TRUNC_USAT_U: + case GO::G_FPTRUNC: + return VerifyWidthChange(false); + case GO::G_PTR_ADD: + case GO::G_PTRMASK: + return requireSameShape(TypeAt(1), TypeAt(2), + "pointer arithmetic operands must have matching scalar/vector shape"); + case GO::G_ICMP: + case GO::G_FCMP: + case GO::G_STRICT_FCMP: + case GO::G_STRICT_FCMPS: { + const PredicateOperand *Predicate = Operands[1].getIf(); + if (Predicate == nullptr || ((Generic == GO::G_ICMP) != Predicate->isInteger())) { + return semanticError("generic comparison predicate kind does not match its opcode"); + } + return requireI1WithShape(TypeAt(0), TypeAt(2), false); + } + case GO::G_SCMP: + case GO::G_UCMP: + if (TypeAt(0).scalarBitWidth() < 2) + return semanticError("G_SCMP/G_UCMP result elements must be at least two bits wide"); + return requireSameShape(TypeAt(0), TypeAt(1), + "G_SCMP/G_UCMP must preserve scalar/vector shape"); + case GO::G_SELECT: + return requireI1WithShape(TypeAt(1), TypeAt(0), true); + case GO::G_UADDO: + case GO::G_USUBO: + case GO::G_SADDO: + case GO::G_SSUBO: + case GO::G_UMULO: + case GO::G_SMULO: + case GO::G_UADDE: + case GO::G_USUBE: + case GO::G_SADDE: + case GO::G_SSUBE: + return requireI1WithShape(TypeAt(1), TypeAt(0), false); + case GO::G_CTTZ: + case GO::G_CTTZ_ZERO_POISON: + case GO::G_CTLZ: + case GO::G_CTLZ_ZERO_POISON: + case GO::G_CTLS: + case GO::G_CTPOP: + return requireSameShape(TypeAt(0), TypeAt(1), + "generic bit-count operation must preserve scalar/vector shape"); + case GO::G_BSWAP: + if ((TypeAt(0).scalarBitWidth() % 16) != 0) + return semanticError("G_BSWAP element width must be a multiple of 16 bits"); + return {}; + case GO::G_FPTOSI: + case GO::G_FPTOUI: + case GO::G_FPTOSI_SAT: + case GO::G_FPTOUI_SAT: + case GO::G_SITOFP: + case GO::G_UITOFP: + case GO::G_LROUND: + case GO::G_LLROUND: + return requireSameShape(TypeAt(0), TypeAt(1), + "generic numeric conversion must preserve scalar/vector shape"); + case GO::G_FCOPYSIGN: + return requireSameShape(TypeAt(0), TypeAt(2), + "G_FCOPYSIGN operands must have matching scalar/vector shape"); + case GO::G_IS_FPCLASS: { + if (auto Shape = requireI1WithShape(TypeAt(0), TypeAt(1), false); !Shape) + return Shape; + const auto Classes = plainImmediate(Operands[2]); + if (!Classes || *Classes < 0 || *Classes > 0x3ff) + return semanticError("G_IS_FPCLASS class mask must fit the supported ten-bit mask"); + return {}; + } + case GO::G_FPOWI: + case GO::G_FLDEXP: + case GO::G_STRICT_FLDEXP: + return requireSameShape(TypeAt(0), TypeAt(2), + "floating operation exponent must match the result vector shape"); + case GO::G_FFREXP: + return requireSameShape(TypeAt(0), TypeAt(1), + "G_FFREXP mantissa and exponent results must have matching shape"); + case GO::G_MERGE_VALUES: { + if (TypeAt(0).isVector() || TypeAt(1).isVector()) + return semanticError("G_MERGE_VALUES only merges scalar values"); + if (minimumBitWidth(TypeAt(0)) != minimumBitWidth(TypeAt(1)) * (Operands.size() - 1)) + return semanticError("G_MERGE_VALUES source widths do not fill the destination"); + return {}; + } + case GO::G_UNMERGE_VALUES: { + const std::size_t DestinationCount = Operands.size() - 1; + const LLT Dst = TypeAt(0); + const LLT Src = TypeAt(DestinationCount); + if (minimumBitWidth(Src) != minimumBitWidth(Dst) * DestinationCount) + return semanticError("G_UNMERGE_VALUES destination widths do not cover the source"); + if (Dst.isVector() && (!Src.isVector() || Dst.isScalableVector() != Src.isScalableVector() || + scalarElementType(Dst) != scalarElementType(Src))) { + return semanticError("vector G_UNMERGE_VALUES operands have incompatible element types"); + } + return {}; + } + case GO::G_EXTRACT: { + const auto Offset = plainImmediate(Operands[2]); + const std::uint64_t DstBits = minimumBitWidth(TypeAt(0)); + const std::uint64_t SrcBits = minimumBitWidth(TypeAt(1)); + if (!Offset || *Offset < 0 || DstBits >= SrcBits || + static_cast(*Offset) > SrcBits - DstBits) { + return semanticError("G_EXTRACT offset and result width must stay inside its source"); + } + return {}; + } + case GO::G_INSERT: { + const auto Offset = plainImmediate(Operands[3]); + const std::uint64_t DstBits = minimumBitWidth(TypeAt(0)); + const std::uint64_t InsertBits = minimumBitWidth(TypeAt(2)); + if (!Offset || *Offset < 0 || InsertBits >= DstBits || + static_cast(*Offset) > DstBits - InsertBits) { + return semanticError("G_INSERT offset and inserted width must stay inside its result"); + } + return {}; + } + case GO::G_BUILD_VECTOR: + case GO::G_BUILD_VECTOR_TRUNC: { + const LLT Dst = TypeAt(0); + const LLT Src = TypeAt(1); + if (!Dst.isVector() || Dst.isScalableVector() || Src.isVector()) + return semanticError("G_BUILD_VECTOR requires a fixed vector result and scalar sources"); + if (Dst.minimumElementCount() != Operands.size() - 1) + return semanticError("G_BUILD_VECTOR source count must equal the result lane count"); + const LLT Element = scalarElementType(Dst); + if (Generic == GO::G_BUILD_VECTOR && Element != Src) + return semanticError("G_BUILD_VECTOR source LLT must equal the result element LLT"); + if (Generic == GO::G_BUILD_VECTOR_TRUNC && Src.scalarBitWidth() <= Element.scalarBitWidth()) + return semanticError("G_BUILD_VECTOR_TRUNC sources must be wider than result elements"); + return {}; + } + case GO::G_CONCAT_VECTORS: { + const LLT Dst = TypeAt(0); + const LLT Src = TypeAt(1); + if (!Dst.isVector() || !Src.isVector() || Dst.isScalableVector() != Src.isScalableVector() || + scalarElementType(Dst) != scalarElementType(Src) || + Dst.minimumElementCount() != Src.minimumElementCount() * (Operands.size() - 1)) { + return semanticError("G_CONCAT_VECTORS operands do not exactly tile the result vector"); + } + return {}; + } + case GO::G_VSCALE: { + const auto *Scale = Operands[1].getIf(); + if (TypeAt(0).isVector() || Scale == nullptr || Scale->Value.isZero() || + Scale->Value.bitWidth() != TypeAt(0).scalarBitWidth()) { + return semanticError("G_VSCALE requires a nonzero typed constant matching a scalar result"); + } + return {}; + } + case GO::G_SHL: + case GO::G_LSHR: + case GO::G_ASHR: + case GO::G_ROTR: + case GO::G_ROTL: + case GO::G_USHLSAT: + case GO::G_SSHLSAT: + case GO::G_FSHL: + case GO::G_FSHR: + return requireSameShape(TypeAt(1), TypeAt(Operands.size() - 1), + "shift amount must match the shifted value's scalar/vector shape"); + case GO::G_INSERT_SUBVECTOR: + case GO::G_EXTRACT_SUBVECTOR: { + const bool IsInsert = Generic == GO::G_INSERT_SUBVECTOR; + const LLT Outer = TypeAt(IsInsert ? 0 : 1); + const LLT Inner = TypeAt(IsInsert ? 2 : 0); + const auto Index = plainImmediate(Operands[IsInsert ? 3 : 2]); + if (!Outer.isVector() || !Inner.isVector() || + scalarElementType(Outer) != scalarElementType(Inner) || !Index || *Index < 0) { + return semanticError("subvector operation has incompatible vector types or index"); + } + if ((!Outer.isScalableVector() && Inner.isScalableVector()) || + Inner.minimumElementCount() > Outer.minimumElementCount()) { + return semanticError("subvector operation cannot place a larger vector inside a smaller one"); + } + const std::uint64_t Start = static_cast(*Index); + const std::uint64_t InnerLength = Inner.minimumElementCount(); + const std::uint64_t OuterLength = Outer.minimumElementCount(); + const bool MixedScalability = Outer.isScalableVector() && !Inner.isScalableVector(); + if ((Start % InnerLength) != 0 || Start >= OuterLength || + (!MixedScalability && Start + InnerLength > OuterLength)) { + return semanticError("subvector index is misaligned or outside the containing vector"); + } + return {}; + } + case GO::G_SHUFFLE_VECTOR: { + const LLT Dst = TypeAt(0); + const LLT Src = TypeAt(1); + const auto *Mask = Operands[3].getIf(); + if (!Dst.isVector() || !Src.isVector() || Dst.isScalableVector() || Src.isScalableVector() || + scalarElementType(Dst) != scalarElementType(Src) || Mask == nullptr || + Mask->Elements.size() != Dst.minimumElementCount()) { + return semanticError("G_SHUFFLE_VECTOR types and mask length are inconsistent"); + } + const std::uint64_t SourceLanes = Src.minimumElementCount(); + for (const std::int32_t Element : Mask->Elements) { + if (Element < ShuffleMaskOperand::Undef || + (Element >= 0 && static_cast(Element) >= 2 * SourceLanes)) { + return semanticError("G_SHUFFLE_VECTOR mask contains an invalid lane index"); + } + } + return {}; + } + case GO::G_SPLAT_VECTOR: { + const LLT Dst = TypeAt(0); + const LLT Src = TypeAt(1); + if (!Dst.isScalableVector() || Src.isVector() || + scalarElementType(Dst).scalarBitWidth() > Src.scalarBitWidth()) { + return semanticError("G_SPLAT_VECTOR requires a scalable result with no wider elements"); + } + return {}; + } + case GO::G_STEP_VECTOR: { + const LLT Dst = TypeAt(0); + const auto *Step = Operands[1].getIf(); + if (!Dst.isScalableVector() || Step == nullptr || Step->Value.isZero() || + Step->Value.isNegative() || Step->Value.bitWidth() != Dst.scalarBitWidth()) { + return semanticError("G_STEP_VECTOR step must be a positive typed element-width constant"); + } + return {}; + } + case GO::G_INSERT_VECTOR_ELT: { + const LLT Vector = TypeAt(0); + if (scalarElementType(Vector) != TypeAt(2) || TypeAt(3).isVector()) + return semanticError("G_INSERT_VECTOR_ELT element or index LLT is incompatible"); + return {}; + } + case GO::G_EXTRACT_VECTOR_ELT: { + const LLT Vector = TypeAt(1); + if (scalarElementType(Vector) != TypeAt(0) || TypeAt(2).isVector()) + return semanticError("G_EXTRACT_VECTOR_ELT result or index LLT is incompatible"); + return {}; + } + case GO::G_VECTOR_COMPRESS: + return requireI1WithShape(TypeAt(2), TypeAt(0), false); + case GO::G_VECREDUCE_SEQ_FADD: + case GO::G_VECREDUCE_SEQ_FMUL: + if (TypeAt(0).isVector() || TypeAt(1).isVector() || !TypeAt(2).isVector() || + scalarElementType(TypeAt(2)) != TypeAt(0) || TypeAt(0) != TypeAt(1)) { + return semanticError("sequential vector reduction accumulator and element LLTs must match"); + } + return {}; + case GO::G_VECREDUCE_FADD: + case GO::G_VECREDUCE_FMUL: + case GO::G_VECREDUCE_FMAX: + case GO::G_VECREDUCE_FMIN: + case GO::G_VECREDUCE_FMAXIMUM: + case GO::G_VECREDUCE_FMINIMUM: + case GO::G_VECREDUCE_ADD: + case GO::G_VECREDUCE_MUL: + case GO::G_VECREDUCE_AND: + case GO::G_VECREDUCE_OR: + case GO::G_VECREDUCE_XOR: + case GO::G_VECREDUCE_SMAX: + case GO::G_VECREDUCE_SMIN: + case GO::G_VECREDUCE_UMAX: + case GO::G_VECREDUCE_UMIN: + if (TypeAt(0).isVector() || !TypeAt(1).isVector() || + scalarElementType(TypeAt(1)) != TypeAt(0)) { + return semanticError("vector reduction result must equal the source element LLT"); + } + return {}; + case GO::G_SBFX: + case GO::G_UBFX: + if (TypeAt(0).isVector() || TypeAt(2).isVector() || TypeAt(3).isVector()) + return semanticError("generic bit-field extraction only supports scalar operands"); + return {}; + case GO::G_BRCOND: + if (!isI1(TypeAt(0)) || TypeAt(0).isVector()) + return semanticError("G_BRCOND condition must be a scalar i1 virtual register"); + return {}; + case GO::G_BRJT: + if (TypeAt(0).isVector() || TypeAt(2).isVector()) + return semanticError("G_BRJT table pointer and index must be scalar values"); + return {}; + case GO::G_INTRINSIC: + case GO::G_INTRINSIC_W_SIDE_EFFECTS: + case GO::G_INTRINSIC_CONVERGENT: + case GO::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS: { + const auto FirstUse = std::ranges::find_if_not(Operands, [](const MachineOperand &Operand) { + return Operand.isRegister() && Operand.isDef(); + }); + if (FirstUse == Operands.end() || FirstUse->kind() != MachineOperand::Kind::Intrinsic) + return semanticError("generic intrinsic must place its intrinsic ID after all definitions"); + return {}; + } + case GO::G_INDEXED_LOAD: + case GO::G_INDEXED_SEXTLOAD: + case GO::G_INDEXED_ZEXTLOAD: + if (const auto Mode = plainImmediate(Operands[4]); !Mode || (*Mode != 0 && *Mode != 1)) + return semanticError("generic indexed-load address mode must be immediate 0 or 1"); + return {}; + case GO::G_INDEXED_STORE: + if (const auto Mode = plainImmediate(Operands[4]); !Mode || (*Mode != 0 && *Mode != 1)) + return semanticError("G_INDEXED_STORE address mode must be immediate 0 or 1"); + return {}; + case GO::G_ATOMIC_CMPXCHG_WITH_SUCCESS: + return requireI1WithShape(TypeAt(1), TypeAt(0), false); + case GO::G_FENCE: { + const auto Ordering = plainImmediate(Operands[0]); + const auto Scope = plainImmediate(Operands[1]); + if (!Ordering || *Ordering < 4 || *Ordering > 7 || !Scope || *Scope < 0 || + static_cast(*Scope) > std::numeric_limits::max()) { + return semanticError("G_FENCE requires acquire-or-stronger ordering and a uint32 scope"); + } + return {}; + } + case GO::G_PREFETCH: { + const auto ReadWrite = plainImmediate(Operands[1]); + const auto Locality = plainImmediate(Operands[2]); + const auto CacheType = plainImmediate(Operands[3]); + if (!ReadWrite || *ReadWrite < 0 || *ReadWrite > 1 || !Locality || *Locality < 0 || + *Locality > 3 || !CacheType || *CacheType < 0 || *CacheType > 1) { + return semanticError("G_PREFETCH control operands are outside their defined ranges"); + } + return {}; + } + case GO::G_VAARG: { + const auto Align = plainImmediate(Operands[2]); + if (!Align || *Align <= 0 || !std::has_single_bit(static_cast(*Align))) + return semanticError("G_VAARG alignment must be a positive power of two"); + return {}; + } + case GO::G_DYN_STACKALLOC: { + const auto Align = plainImmediate(Operands[2]); + if (!Align || *Align <= 0 || !std::has_single_bit(static_cast(*Align))) + return semanticError("G_DYN_STACKALLOC alignment must be a positive power of two"); + return {}; + } + case GO::G_MEMCPY: + case GO::G_MEMMOVE: + if (const auto Tail = plainImmediate(Operands[3]); !Tail || (*Tail != 0 && *Tail != 1)) + return semanticError("generic memory-transfer tail flag must be immediate 0 or 1"); + return {}; + case GO::G_MEMSET: + if (TypeAt(1).isVector() || TypeAt(1).scalarBitWidth() != 8) + return semanticError("G_MEMSET fill value must be a scalar i8 value"); + if (const auto Tail = plainImmediate(Operands[3]); !Tail || (*Tail != 0 && *Tail != 1)) + return semanticError("G_MEMSET tail flag must be immediate 0 or 1"); + return {}; + case GO::G_BZERO: + if (const auto Tail = plainImmediate(Operands[2]); !Tail || (*Tail != 0 && *Tail != 1)) + return semanticError("G_BZERO tail flag must be immediate 0 or 1"); + return {}; + case GO::G_UBSANTRAP: { + const auto Kind = plainImmediate(Operands[0]); + if (!Kind || *Kind < -128 || *Kind > 127) + return semanticError("G_UBSANTRAP kind must fit in a signed eight-bit immediate"); + return {}; + } + case GO::G_INTRINSIC_FPTRUNC_ROUND: { + const auto Rounding = plainImmediate(Operands[2]); + if (!Rounding || !((*Rounding >= 0 && *Rounding <= 4) || *Rounding == 7)) + return semanticError("floating truncation rounding mode is invalid"); + return VerifyWidthChange(false); + } + default: + return {}; + } +} + +[[nodiscard]] Expected verifyGenericInstructionSemantics(const MachineInstr &Instruction, + const MachineRegisterInfo &RegInfo) { + const auto Operands = Instruction.operands(); + const auto MemoryOperands = Instruction.memOperands(); + const GO Generic = static_cast(Instruction.opcode().value()); + + const auto TypeAt = [&](std::size_t Index) -> Expected { + if (Index >= Operands.size()) + return makeUnexpected(ErrorCode::InternalError, + "generic semantic verifier operand index is out of range"); + const Register *Reg = Operands[Index].getIf(); + if (Reg == nullptr || !Reg->isVirtual()) + return makeUnexpected(ErrorCode::InternalError, + "generic semantic verifier expected a virtual register"); + auto Info = RegInfo.virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + if (!Info->get().Type) + return makeUnexpected(ErrorCode::InternalError, + "generic semantic verifier found a register without an LLT"); + return *Info->get().Type; + }; + + const auto VerifyAddress = [&](std::size_t OperandIndex, + const MachineMemOperand &Memory) -> Expected { + auto Type = TypeAt(OperandIndex); + if (!Type) + return std::unexpected(Type.error()); + if (!Type->isPointer() || Type->addressSpace() != Memory.description().AddressSpace) + return semanticError("generic memory address LLT and MMO address space do not match"); + return {}; + }; + + enum class SizeRelation : std::uint8_t { + Equal, + NoLarger, + StrictlySmaller, + }; + const auto VerifySize = [&](LLT ValueType, const MachineMemOperand &Memory, + SizeRelation Relation) -> Expected { + const MemorySize Size = Memory.description().Size; + if (!Size.isKnown()) + return semanticError("typed generic memory access requires a known MMO size"); + if (Size.isScalable() != ValueType.isScalableVector()) + return semanticError("generic value and MMO scalability do not match"); + const std::uint64_t MemoryBytes = Size.minimumBytes(); + const std::uint64_t ValueBytes = minimumStoreBytes(ValueType); + const bool Valid = Relation == SizeRelation::Equal + ? MemoryBytes == ValueBytes + : (Relation == SizeRelation::NoLarger ? MemoryBytes <= ValueBytes + : MemoryBytes < ValueBytes); + if (!Valid) + return semanticError("generic memory access size is incompatible with its value LLT"); + return {}; + }; + + const auto VerifySingleAccess = [&](std::size_t AddressIndex, std::size_t ValueIndex, + bool MustLoad, bool MustStore, + SizeRelation Relation) -> Expected { + if (MemoryOperands.size() != 1) + return semanticError("generic scalar memory instruction requires exactly one MMO"); + const MachineMemOperand &Memory = *MemoryOperands.front(); + if (Memory.isLoad() != MustLoad || Memory.isStore() != MustStore) + return semanticError("generic instruction and MMO access directions do not match"); + if (auto Address = VerifyAddress(AddressIndex, Memory); !Address) + return Address; + auto ValueType = TypeAt(ValueIndex); + if (!ValueType) + return std::unexpected(ValueType.error()); + return VerifySize(*ValueType, Memory, Relation); + }; + + switch (Generic) { + case GO::G_LOAD: + return VerifySingleAccess(1, 0, true, false, SizeRelation::NoLarger); + case GO::G_SEXTLOAD: + case GO::G_ZEXTLOAD: + case GO::G_FPEXTLOAD: + return VerifySingleAccess(1, 0, true, false, SizeRelation::StrictlySmaller); + case GO::G_STORE: + return VerifySingleAccess(1, 0, false, true, SizeRelation::NoLarger); + case GO::G_FPTRUNCSTORE: + return VerifySingleAccess(1, 0, false, true, SizeRelation::StrictlySmaller); + case GO::G_INDEXED_LOAD: + return VerifySingleAccess(2, 0, true, false, SizeRelation::NoLarger); + case GO::G_INDEXED_SEXTLOAD: + case GO::G_INDEXED_ZEXTLOAD: + return VerifySingleAccess(2, 0, true, false, SizeRelation::StrictlySmaller); + case GO::G_INDEXED_STORE: + return VerifySingleAccess(2, 1, false, true, SizeRelation::NoLarger); + case GO::G_ATOMIC_CMPXCHG_WITH_SUCCESS: + if (MemoryOperands.size() != 1 || + MemoryOperands.front()->description().AtomicKind != AtomicOperation::CompareExchange) + return semanticError("G_ATOMIC_CMPXCHG_WITH_SUCCESS requires one compare-exchange MMO"); + return VerifySingleAccess(2, 0, true, true, SizeRelation::Equal); + case GO::G_ATOMIC_CMPXCHG: + if (MemoryOperands.size() != 1 || + MemoryOperands.front()->description().AtomicKind != AtomicOperation::CompareExchange) + return semanticError("G_ATOMIC_CMPXCHG requires one compare-exchange MMO"); + return VerifySingleAccess(1, 0, true, true, SizeRelation::Equal); + case GO::G_ATOMICRMW_XCHG: + case GO::G_ATOMICRMW_ADD: + case GO::G_ATOMICRMW_SUB: + case GO::G_ATOMICRMW_AND: + case GO::G_ATOMICRMW_NAND: + case GO::G_ATOMICRMW_OR: + case GO::G_ATOMICRMW_XOR: + case GO::G_ATOMICRMW_MAX: + case GO::G_ATOMICRMW_MIN: + case GO::G_ATOMICRMW_UMAX: + case GO::G_ATOMICRMW_UMIN: + case GO::G_ATOMICRMW_FADD: + case GO::G_ATOMICRMW_FSUB: + case GO::G_ATOMICRMW_FMAX: + case GO::G_ATOMICRMW_FMIN: + case GO::G_ATOMICRMW_FMAXIMUM: + case GO::G_ATOMICRMW_FMINIMUM: + case GO::G_ATOMICRMW_FMAXIMUMNUM: + case GO::G_ATOMICRMW_FMINIMUMNUM: + case GO::G_ATOMICRMW_UINC_WRAP: + case GO::G_ATOMICRMW_UDEC_WRAP: + case GO::G_ATOMICRMW_USUB_COND: + case GO::G_ATOMICRMW_USUB_SAT: + if (MemoryOperands.size() != 1 || + MemoryOperands.front()->description().AtomicKind != AtomicOperation::ReadModifyWrite) + return semanticError("generic atomic RMW requires one read-modify-write MMO"); + return VerifySingleAccess(1, 0, true, true, SizeRelation::Equal); + case GO::G_PREFETCH: { + if (MemoryOperands.size() != 1) + return semanticError("G_PREFETCH requires exactly one MMO"); + const auto ReadWrite = plainImmediate(Operands[1]); + if (!ReadWrite) + return semanticError("G_PREFETCH is missing its validated read/write selector"); + const MachineMemOperand &Memory = *MemoryOperands.front(); + if ((*ReadWrite == 0 && (!Memory.isLoad() || Memory.isStore())) || + (*ReadWrite == 1 && (Memory.isLoad() || !Memory.isStore()))) { + return semanticError("G_PREFETCH selector and MMO access direction do not match"); + } + return VerifyAddress(0, Memory); + } + case GO::G_VASTART: + if (MemoryOperands.size() != 1 || MemoryOperands.front()->isLoad() || + !MemoryOperands.front()->isStore()) { + return semanticError("G_VASTART requires exactly one store-only MMO"); + } + return VerifyAddress(0, *MemoryOperands.front()); + case GO::G_VAARG: { + if (MemoryOperands.size() != 2) + return semanticError("G_VAARG requires separate value-load and list-update MMOs"); + const MachineMemOperand *ValueLoad = nullptr; + const MachineMemOperand *ListStore = nullptr; + for (const MachineMemOperand *Memory : MemoryOperands) { + if (Memory->isLoad() == Memory->isStore()) { + return semanticError("G_VAARG MMOs must each describe exactly one access direction"); + } + if (Memory->isLoad()) + ValueLoad = Memory; + else + ListStore = Memory; + if (auto Address = VerifyAddress(1, *Memory); !Address) + return Address; + } + if (ValueLoad == nullptr || ListStore == nullptr) + return semanticError("G_VAARG MMOs must cover both the value load and list update"); + auto ResultType = TypeAt(0); + if (!ResultType) + return std::unexpected(ResultType.error()); + return VerifySize(*ResultType, *ValueLoad, SizeRelation::Equal); + } + case GO::G_MEMCPY: + case GO::G_MEMCPY_INLINE: + case GO::G_MEMMOVE: { + if (MemoryOperands.size() != 2 || MemoryOperands[0]->isLoad() || + !MemoryOperands[0]->isStore() || !MemoryOperands[1]->isLoad() || + MemoryOperands[1]->isStore()) { + return semanticError("generic memory transfer requires store and load MMOs in that order"); + } + if (MemoryOperands[0]->description().Size != MemoryOperands[1]->description().Size) + return semanticError("generic memory-transfer MMOs must have identical sizes"); + if (auto Destination = VerifyAddress(0, *MemoryOperands[0]); !Destination) + return Destination; + return VerifyAddress(1, *MemoryOperands[1]); + } + case GO::G_MEMSET: + case GO::G_BZERO: + if (MemoryOperands.size() != 1 || MemoryOperands.front()->isLoad() || + !MemoryOperands.front()->isStore()) { + return semanticError("generic memory fill requires exactly one store-only MMO"); + } + return VerifyAddress(0, *MemoryOperands.front()); + default: + return {}; + } +} + +void configureCoreOpcodes(DescriptorRegistry &Registry) { + const auto RegDef = untypedRegister(RegisterOperandRole::Def); + const auto RegUse = untypedRegister(RegisterOperandRole::Use); + const auto Any = anyOperand(); + const auto VariadicAny = repeated(Any); + const auto VariadicUse = repeated(RegUse); + + Registry.configure({GO::PHI}, + {RegDef, VariadicUse, repeated(kind(MachineOperand::Kind::BasicBlock))}, 1, + {InstructionFlag::Phi}, true, 1, false, PseudoOwner::PhiElimination, + PipelineStage::SSAEliminated); + Registry.configure({GO::INLINEASM}, {VariadicAny}, 0, + {InstructionFlag::ProducesCode, InstructionFlag::TerminalEmission, + InstructionFlag::UnmodeledSideEffects}, + true, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::INLINEASM_BR}, {VariadicAny}, 0, + {InstructionFlag::ProducesCode, InstructionFlag::TerminalEmission, + InstructionFlag::UnmodeledSideEffects, InstructionFlag::HasSideEffects}, + true, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::CFI_INSTRUCTION}, {kind(MachineOperand::Kind::CFIIndex)}, 0, + {InstructionFlag::Meta, InstructionFlag::NotDuplicable}); + Registry.configure({GO::EH_LABEL, GO::GC_LABEL, GO::ANNOTATION_LABEL}, + {kind(MachineOperand::Kind::MCSymbol)}, 0, + {InstructionFlag::Meta, InstructionFlag::NotDuplicable}); + Registry.configure({GO::KILL}, {VariadicUse}, 0, {InstructionFlag::Meta}, true); + Registry.configure({GO::EXTRACT_SUBREG}, {RegDef, RegUse, immediate()}, 1, {}, false, 0, false, + PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized); + Registry.configure({GO::INSERT_SUBREG}, {RegDef, RegUse, RegUse, immediate()}, 1, {}, false, 0, + false, PseudoOwner::TwoAddressRewrite, PipelineStage::TiedOpsRewritten); + Registry.tie(GO::INSERT_SUBREG, 0, 1); + Registry.configure({GO::IMPLICIT_DEF}, {RegDef}, 1, + {InstructionFlag::Meta, InstructionFlag::Rematerializable}); + Registry.configure({GO::INIT_UNDEF}, {RegDef}, 1, {}, false, 0, false, + PseudoOwner::RegisterAllocator, PipelineStage::RegisterAllocated); + Registry.configure({GO::SUBREG_TO_REG}, {RegDef, RegUse, immediate()}, 1, {}, false, 0, false, + PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized); + Registry.configure({GO::COPY_TO_REGCLASS}, {RegDef, RegUse, immediate()}, 1, {}, false, 0, false, + PseudoOwner::RegisterAllocator, PipelineStage::RegisterAllocated); + Registry.configure({GO::DBG_VALUE, GO::DBG_VALUE_LIST, GO::DBG_INSTR_REF, GO::DBG_PHI}, + {VariadicAny}, 0, {InstructionFlag::Meta}, true); + Registry.configure({GO::DBG_LABEL}, {kind(MachineOperand::Kind::Metadata)}, 0, + {InstructionFlag::Meta}); + Registry.configure({GO::REG_SEQUENCE}, {RegDef, repeated(RegUse), repeated(immediate())}, 1, {}, + true, 1, false, PseudoOwner::TwoAddressRewrite, + PipelineStage::TiedOpsRewritten); + Registry.configure({GO::COPY}, {RegDef, RegUse}, 1, {}, false, 0, false, + PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized); + Registry.configure({GO::COPY_LANEMASK}, {RegDef, RegUse, kind(MachineOperand::Kind::LaneMask)}, 1, + {}, false, 0, false, PseudoOwner::PostRAExpansion, + PipelineStage::PostRAFinalized); + Registry.configure({GO::BUNDLE}, {VariadicAny}, 0, {InstructionFlag::Meta}, true, 0, false, + PseudoOwner::None, PipelineStage::Emission, true); + Registry.configure({GO::LIFETIME_START, GO::LIFETIME_END}, {immediate()}, 0, + {InstructionFlag::Meta}); + Registry.configure({GO::PSEUDO_PROBE}, {immediate(), immediate(), immediate(), immediate()}, 0, + {InstructionFlag::Meta, InstructionFlag::HasSideEffects}); + Registry.configure({GO::ARITH_FENCE}, {RegDef, RegUse}, 1, {InstructionFlag::Meta}); + Registry.tie(GO::ARITH_FENCE, 0, 1); + Registry.configure({GO::STACKMAP}, {immediate(), immediate(), VariadicAny}, 0, + {InstructionFlag::Call, InstructionFlag::MayLoad, + InstructionFlag::HasSideEffects, InstructionFlag::ProducesCode, + InstructionFlag::TerminalEmission}, + true, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::FENTRY_CALL}, {}, 0, + {InstructionFlag::Call, InstructionFlag::MayLoad, InstructionFlag::MayStore, + InstructionFlag::HasSideEffects, InstructionFlag::ProducesCode, + InstructionFlag::TerminalEmission}, + false, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure( + {GO::PATCHPOINT}, + {RegDef, immediate(), immediate(), Any, immediate(), immediate(), VariadicAny}, 1, + {InstructionFlag::Call, InstructionFlag::MayLoad, InstructionFlag::HasSideEffects, + InstructionFlag::ProducesCode, InstructionFlag::TerminalEmission}, + true, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::LOAD_STACK_GUARD}, {RegDef}, 1, + {InstructionFlag::MayLoad, InstructionFlag::Rematerializable}, false, 0, false, + PseudoOwner::InstructionSelect, PipelineStage::Selected); + Registry.configure({GO::PREALLOCATED_SETUP}, {immediate()}, 0, {InstructionFlag::HasSideEffects}, + false, 0, false, PseudoOwner::InstructionSelect, PipelineStage::Selected); + Registry.configure({GO::PREALLOCATED_ARG}, {RegDef, immediate(), immediate()}, 1, + {InstructionFlag::HasSideEffects}, false, 0, false, + PseudoOwner::InstructionSelect, PipelineStage::Selected); + Registry.configure({GO::STATEPOINT}, {VariadicAny}, 0, + {InstructionFlag::Call, InstructionFlag::MayLoad, InstructionFlag::MayStore, + InstructionFlag::HasSideEffects, InstructionFlag::ProducesCode, + InstructionFlag::TerminalEmission}, + true, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::LOCAL_ESCAPE}, {symbol(), kind(MachineOperand::Kind::FrameIndex)}, 0, + {InstructionFlag::Meta}); + Registry.configure({GO::FAULTING_OP}, {RegDef, VariadicAny}, 1, + {InstructionFlag::MayLoad, InstructionFlag::MayStore, + InstructionFlag::HasSideEffects, InstructionFlag::Terminator, + InstructionFlag::Branch, InstructionFlag::ProducesCode, + InstructionFlag::TerminalEmission}, + true, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::PATCHABLE_OP}, {VariadicAny}, 0, + {InstructionFlag::MayLoad, InstructionFlag::MayStore, + InstructionFlag::HasSideEffects, InstructionFlag::ProducesCode, + InstructionFlag::TerminalEmission}, + true, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::PATCHABLE_FUNCTION_ENTER, GO::PATCHABLE_FUNCTION_EXIT}, {}, 0, + {InstructionFlag::HasSideEffects, InstructionFlag::ProducesCode, + InstructionFlag::TerminalEmission}, + false, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission); + Registry.configure({GO::PATCHABLE_RET, GO::PATCHABLE_TAIL_CALL}, {VariadicAny}, 0, + {InstructionFlag::HasSideEffects, InstructionFlag::ProducesCode, + InstructionFlag::TerminalEmission, InstructionFlag::Terminator, + InstructionFlag::Return}, + true, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::PATCHABLE_EVENT_CALL}, {RegUse, Any}, 0, + {InstructionFlag::Call, InstructionFlag::MayLoad, InstructionFlag::MayStore, + InstructionFlag::HasSideEffects, InstructionFlag::ProducesCode, + InstructionFlag::TerminalEmission}, + false, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::PATCHABLE_TYPED_EVENT_CALL}, {Any, RegUse, Any}, 0, + {InstructionFlag::Call, InstructionFlag::MayLoad, InstructionFlag::MayStore, + InstructionFlag::HasSideEffects, InstructionFlag::ProducesCode, + InstructionFlag::TerminalEmission}, + false, 0, false, PseudoOwner::AsmPrinter, PipelineStage::Emission, true); + Registry.configure({GO::ICALL_BRANCH_FUNNEL}, {VariadicAny}, 0, {InstructionFlag::HasSideEffects}, + true, 0, false, PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized, + true); + Registry.configure({GO::FAKE_USE}, {VariadicUse}, 0, + {InstructionFlag::Meta, InstructionFlag::FakeUse}, true); + Registry.configure({GO::MEMBARRIER}, {}, 0, + {InstructionFlag::Meta, InstructionFlag::HasSideEffects}); + Registry.configure({GO::JUMP_TABLE_DEBUG_INFO}, {kind(MachineOperand::Kind::JumpTableIndex)}, 0, + {InstructionFlag::Meta}); + Registry.configure({GO::RELOC_NONE}, {symbol()}, 0, + {InstructionFlag::Meta, InstructionFlag::HasSideEffects}); + Registry.configure({GO::CONVERGENCECTRL_ENTRY, GO::CONVERGENCECTRL_ANCHOR}, {RegDef}, 1, + {InstructionFlag::Meta, InstructionFlag::Convergent}); + Registry.configure({GO::CONVERGENCECTRL_LOOP}, {RegDef, RegUse}, 1, + {InstructionFlag::Meta, InstructionFlag::Convergent}); + Registry.configure({GO::CONVERGENCECTRL_GLUE}, {RegUse}, 0, + {InstructionFlag::Meta, InstructionFlag::Convergent}); +} + +void configureGenericOpcodes(DescriptorRegistry &Registry) { + const LLTKindSet AnyTypes = anyValueKinds(); + const LLTKindSet IntTypes = integerKinds(); + const LLTKindSet ScalarValues = scalarValueKinds(); + const LLTKindSet ScalarInts = scalarIntegerKinds(); + const LLTKindSet FloatTypes = floatingKinds(); + const LLTKindSet ScalarFloats = scalarFloatingKinds(); + const LLTKindSet PointerTypes = pointerKinds(); + const LLTKindSet ScalarPointers = scalarPointerKinds(); + const LLTKindSet VectorTypes = vectorKinds(); + + const auto AnyDef0 = typedRegister(RegisterOperandRole::Def, AnyTypes, 0); + const auto AnyUse0 = typedRegister(RegisterOperandRole::Use, AnyTypes, 0); + const auto AnyUse1 = typedRegister(RegisterOperandRole::Use, AnyTypes, 1); + const auto ScalarDef0 = typedRegister(RegisterOperandRole::Def, ScalarValues, 0); + const auto ScalarUse0 = typedRegister(RegisterOperandRole::Use, ScalarValues, 0); + const auto IntDef0 = typedRegister(RegisterOperandRole::Def, IntTypes, 0); + const auto IntDef1 = typedRegister(RegisterOperandRole::Def, IntTypes, 1); + const auto IntUse0 = typedRegister(RegisterOperandRole::Use, IntTypes, 0); + const auto IntUse1 = typedRegister(RegisterOperandRole::Use, IntTypes, 1); + const auto ScalarIntDef0 = typedRegister(RegisterOperandRole::Def, ScalarInts, 0); + const auto ScalarIntDef1 = typedRegister(RegisterOperandRole::Def, ScalarInts, 1); + const auto ScalarIntUse0 = typedRegister(RegisterOperandRole::Use, ScalarInts, 0); + const auto ScalarIntUse1 = typedRegister(RegisterOperandRole::Use, ScalarInts, 1); + const auto ScalarIntUse2 = typedRegister(RegisterOperandRole::Use, ScalarInts, 2); + const auto FloatDef0 = typedRegister(RegisterOperandRole::Def, FloatTypes, 0); + const auto FloatUse0 = typedRegister(RegisterOperandRole::Use, FloatTypes, 0); + const auto FloatUse1 = typedRegister(RegisterOperandRole::Use, FloatTypes, 1); + const auto ScalarFloatDef0 = typedRegister(RegisterOperandRole::Def, ScalarFloats, 0); + const auto ScalarFloatUse0 = typedRegister(RegisterOperandRole::Use, ScalarFloats, 0); + const auto PointerDef0 = typedRegister(RegisterOperandRole::Def, PointerTypes, 0); + const auto PointerUse0 = typedRegister(RegisterOperandRole::Use, PointerTypes, 0); + const auto PointerUse1 = typedRegister(RegisterOperandRole::Use, PointerTypes, 1); + const auto ScalarPointerDef0 = typedRegister(RegisterOperandRole::Def, ScalarPointers, 0); + const auto ScalarPointerDef1 = typedRegister(RegisterOperandRole::Def, ScalarPointers, 1); + const auto ScalarPointerUse0 = typedRegister(RegisterOperandRole::Use, ScalarPointers, 0); + const auto ScalarPointerUse1 = typedRegister(RegisterOperandRole::Use, ScalarPointers, 1); + const auto ScalarPointerUse2 = typedRegister(RegisterOperandRole::Use, ScalarPointers, 2); + + Registry.configure({GO::G_ASSERT_SEXT, GO::G_ASSERT_ZEXT}, {IntDef0, IntUse0, immediate()}, 1); + Registry.configure({GO::G_ASSERT_ALIGN}, {AnyDef0, AnyUse0, immediate()}, 1); + + Registry.configure( + {GO::G_ADD, GO::G_SUB, GO::G_MUL, GO::G_SDIV, GO::G_UDIV, GO::G_SREM, + GO::G_UREM, GO::G_AND, GO::G_OR, GO::G_XOR, GO::G_ABDS, GO::G_ABDU, + GO::G_UAVGFLOOR, GO::G_UAVGCEIL, GO::G_SAVGFLOOR, GO::G_SAVGCEIL, GO::G_UMULH, GO::G_SMULH, + GO::G_UADDSAT, GO::G_SADDSAT, GO::G_USUBSAT, GO::G_SSUBSAT, GO::G_SMIN, GO::G_SMAX, + GO::G_UMIN, GO::G_UMAX, GO::G_CLMUL}, + {IntDef0, IntUse0, IntUse0}, 1); + Registry.addFlag({GO::G_ADD, GO::G_MUL, GO::G_AND, GO::G_OR, GO::G_XOR, GO::G_ABDS, GO::G_ABDU, + GO::G_UMULH, GO::G_SMULH, GO::G_UADDSAT, GO::G_SADDSAT, GO::G_SMIN, GO::G_SMAX, + GO::G_UMIN, GO::G_UMAX, GO::G_CLMUL}, + InstructionFlag::Commutable); + + Registry.configure({GO::G_SDIVREM, GO::G_UDIVREM}, {IntDef0, IntDef0, IntUse0, IntUse0}, 2); + Registry.configure({GO::G_IMPLICIT_DEF}, {AnyDef0}, 1); + Registry.configure({GO::G_PHI}, + {AnyDef0, repeated(AnyUse0), repeated(kind(MachineOperand::Kind::BasicBlock))}, + 1, {InstructionFlag::Phi}, true, 1); + Registry.configure({GO::G_FRAME_INDEX}, + {ScalarPointerDef0, kind(MachineOperand::Kind::FrameIndex)}, 1); + Registry.configure({GO::G_GLOBAL_VALUE}, + {ScalarPointerDef0, kind(MachineOperand::Kind::GlobalSymbol)}, 1); + Registry.configure( + {GO::G_PTRAUTH_GLOBAL_VALUE}, + {ScalarPointerDef0, ScalarPointerUse1, immediate(), ScalarIntUse2, immediate()}, 1); + Registry.configure({GO::G_CONSTANT_POOL}, + {ScalarPointerDef0, kind(MachineOperand::Kind::ConstantPoolIndex)}, 1); + Registry.configure({GO::G_EXTRACT}, {AnyDef0, AnyUse1, immediate()}, 1); + Registry.configure({GO::G_UNMERGE_VALUES}, {AnyDef0, repeated(AnyDef0), AnyUse1}, 2, {}, true, 1); + Registry.configure({GO::G_INSERT}, {AnyDef0, AnyUse0, AnyUse1, immediate()}, 1); + Registry.configure({GO::G_MERGE_VALUES}, {AnyDef0, AnyUse1, repeated(AnyUse1)}, 1, {}, true, 1); + + const auto VectorDef0 = typedRegister(RegisterOperandRole::Def, VectorTypes, 0); + Registry.configure({GO::G_BUILD_VECTOR, GO::G_BUILD_VECTOR_TRUNC}, + {VectorDef0, AnyUse1, repeated(AnyUse1)}, 1, {}, true); + Registry.configure({GO::G_CONCAT_VECTORS}, + {VectorDef0, typedRegister(RegisterOperandRole::Use, VectorTypes, 1), + repeated(typedRegister(RegisterOperandRole::Use, VectorTypes, 1))}, + 1, {}, true, 1); + + Registry.configure({GO::G_PTRTOINT}, {IntDef0, PointerUse1}, 1); + Registry.configure({GO::G_INTTOPTR}, {PointerDef0, IntUse1}, 1); + Registry.configure({GO::G_BITCAST}, {AnyDef0, AnyUse1}, 1); + Registry.configure({GO::G_FREEZE, GO::G_CONSTANT_FOLD_BARRIER}, {AnyDef0, AnyUse0}, 1); + Registry.configure({GO::G_INTRINSIC_FPTRUNC_ROUND}, {FloatDef0, FloatUse1, immediate()}, 1); + Registry.configure({GO::G_INTRINSIC_TRUNC, GO::G_INTRINSIC_ROUND, GO::G_INTRINSIC_ROUNDEVEN}, + {FloatDef0, FloatUse0}, 1); + Registry.configure({GO::G_INTRINSIC_LRINT, GO::G_INTRINSIC_LLRINT}, {IntDef0, FloatUse1}, 1); + Registry.configure({GO::G_READCYCLECOUNTER, GO::G_READSTEADYCOUNTER}, + {typedRegister(RegisterOperandRole::Def, ScalarInts, 0)}, 1, + {InstructionFlag::HasSideEffects}); + + Registry.configure({GO::G_LOAD}, {AnyDef0, ScalarPointerUse1}, 1, {InstructionFlag::MayLoad}, + false, 0, true); + Registry.configure({GO::G_SEXTLOAD, GO::G_ZEXTLOAD}, {IntDef0, ScalarPointerUse1}, 1, + {InstructionFlag::MayLoad}, false, 0, true); + Registry.configure({GO::G_FPEXTLOAD}, {FloatDef0, ScalarPointerUse1}, 1, + {InstructionFlag::MayLoad}, false, 0, true); + Registry.configure({GO::G_INDEXED_LOAD}, + {AnyDef0, ScalarPointerDef1, ScalarPointerUse1, ScalarIntUse2, immediate()}, 2, + {InstructionFlag::MayLoad}, false, 0, true); + Registry.configure({GO::G_INDEXED_SEXTLOAD, GO::G_INDEXED_ZEXTLOAD}, + {IntDef0, ScalarPointerDef1, ScalarPointerUse1, ScalarIntUse2, immediate()}, 2, + {InstructionFlag::MayLoad}, false, 0, true); + Registry.configure({GO::G_STORE}, {AnyUse0, ScalarPointerUse1}, 0, {InstructionFlag::MayStore}, + false, 0, true); + Registry.configure({GO::G_FPTRUNCSTORE}, {FloatUse0, ScalarPointerUse1}, 0, + {InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_INDEXED_STORE}, + {ScalarPointerDef0, AnyUse1, ScalarPointerUse0, ScalarIntUse2, immediate()}, 1, + {InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_ATOMIC_CMPXCHG_WITH_SUCCESS}, + {ScalarDef0, ScalarIntDef1, ScalarPointerUse2, ScalarUse0, ScalarUse0}, 2, + {InstructionFlag::MayLoad, InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_ATOMIC_CMPXCHG}, + {ScalarDef0, ScalarPointerUse1, ScalarUse0, ScalarUse0}, 1, + {InstructionFlag::MayLoad, InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_ATOMICRMW_XCHG}, {ScalarDef0, ScalarPointerUse1, ScalarUse0}, 1, + {InstructionFlag::MayLoad, InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_ATOMICRMW_ADD, GO::G_ATOMICRMW_SUB, GO::G_ATOMICRMW_AND, + GO::G_ATOMICRMW_NAND, GO::G_ATOMICRMW_OR, GO::G_ATOMICRMW_XOR, + GO::G_ATOMICRMW_MAX, GO::G_ATOMICRMW_MIN, GO::G_ATOMICRMW_UMAX, + GO::G_ATOMICRMW_UMIN, GO::G_ATOMICRMW_UINC_WRAP, GO::G_ATOMICRMW_UDEC_WRAP, + GO::G_ATOMICRMW_USUB_COND, GO::G_ATOMICRMW_USUB_SAT}, + {ScalarIntDef0, ScalarPointerUse1, ScalarIntUse0}, 1, + {InstructionFlag::MayLoad, InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_ATOMICRMW_FADD, GO::G_ATOMICRMW_FSUB, GO::G_ATOMICRMW_FMAX, + GO::G_ATOMICRMW_FMIN, GO::G_ATOMICRMW_FMAXIMUM, GO::G_ATOMICRMW_FMINIMUM, + GO::G_ATOMICRMW_FMAXIMUMNUM, GO::G_ATOMICRMW_FMINIMUMNUM}, + {ScalarFloatDef0, ScalarPointerUse1, ScalarFloatUse0}, 1, + {InstructionFlag::MayLoad, InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_FENCE}, {immediate(), immediate()}, 0, + {InstructionFlag::HasSideEffects}); + Registry.configure( + {GO::G_PREFETCH}, {ScalarPointerUse0, immediate(), immediate(), immediate()}, 0, + {InstructionFlag::MayLoad, InstructionFlag::MayStore, InstructionFlag::HasSideEffects}, false, + 0, true); + Registry.configure({GO::G_BRCOND}, {ScalarIntUse0, kind(MachineOperand::Kind::BasicBlock)}, 0, + {InstructionFlag::Terminator, InstructionFlag::Branch}); + Registry.configure({GO::G_BRINDIRECT}, {ScalarPointerUse0}, 0, + {InstructionFlag::Terminator, InstructionFlag::Branch, + InstructionFlag::IndirectBranch, InstructionFlag::Barrier}); + Registry.configure({GO::G_INVOKE_REGION_START}, {}, 0, {InstructionFlag::Terminator}); + Registry.configure({GO::G_INTRINSIC, GO::G_INTRINSIC_W_SIDE_EFFECTS, GO::G_INTRINSIC_CONVERGENT, + GO::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS}, + {repeated(anyOperand())}, 0, {}, true, 1, false, PseudoOwner::None, + PipelineStage::Emission, true); + Registry.addFlag({GO::G_INTRINSIC_W_SIDE_EFFECTS, GO::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS}, + InstructionFlag::HasSideEffects); + Registry.addFlag({GO::G_INTRINSIC_W_SIDE_EFFECTS, GO::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS}, + InstructionFlag::MayLoad); + Registry.addFlag({GO::G_INTRINSIC_W_SIDE_EFFECTS, GO::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS}, + InstructionFlag::MayStore); + Registry.addFlag({GO::G_INTRINSIC_CONVERGENT, GO::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS}, + InstructionFlag::Convergent); + + Registry.configure({GO::G_ANYEXT, GO::G_SEXT, GO::G_ZEXT}, {IntDef0, IntUse1}, 1); + Registry.configure({GO::G_TRUNC, GO::G_TRUNC_SSAT_S, GO::G_TRUNC_SSAT_U, GO::G_TRUNC_USAT_U}, + {IntDef0, IntUse1}, 1); + Registry.configure( + {GO::G_CONSTANT}, + {typedRegister(RegisterOperandRole::Def, ScalarInts, 0), + operand({MachineOperand::Kind::Immediate, MachineOperand::Kind::IntegerImmediate})}, + 1); + Registry.configure({GO::G_FCONSTANT}, + {ScalarFloatDef0, kind(MachineOperand::Kind::FloatingImmediate)}, 1); + Registry.configure({GO::G_VASTART}, {ScalarPointerUse0}, 0, {InstructionFlag::MayStore}, false, 0, + true); + Registry.configure({GO::G_VAARG}, {AnyDef0, ScalarPointerUse1, immediate()}, 1, + {InstructionFlag::MayLoad, InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_SEXT_INREG}, {IntDef0, IntUse0, immediate()}, 1); + Registry.configure( + {GO::G_SHL, GO::G_LSHR, GO::G_ASHR, GO::G_ROTR, GO::G_ROTL, GO::G_USHLSAT, GO::G_SSHLSAT}, + {IntDef0, IntUse0, IntUse1}, 1); + Registry.configure({GO::G_FSHL, GO::G_FSHR}, {IntDef0, IntUse0, IntUse0, IntUse1}, 1); + Registry.configure({GO::G_ICMP}, + {IntDef0, kind(MachineOperand::Kind::Predicate), IntUse1, IntUse1}, 1); + Registry.configure({GO::G_FCMP}, + {IntDef0, kind(MachineOperand::Kind::Predicate), FloatUse1, FloatUse1}, 1); + Registry.configure({GO::G_SCMP, GO::G_UCMP}, {IntDef0, IntUse1, IntUse1}, 1); + Registry.configure({GO::G_SELECT}, {AnyDef0, IntUse1, AnyUse0, AnyUse0}, 1); + + Registry.configure({GO::G_UADDO, GO::G_USUBO, GO::G_SADDO, GO::G_SSUBO, GO::G_UMULO, GO::G_SMULO}, + {IntDef0, IntDef1, IntUse0, IntUse0}, 2); + Registry.configure({GO::G_UADDE, GO::G_USUBE, GO::G_SADDE, GO::G_SSUBE}, + {IntDef0, IntDef1, IntUse0, IntUse0, IntUse1}, 2); + Registry.addFlag({GO::G_UADDO, GO::G_SADDO, GO::G_UMULO, GO::G_SMULO}, + InstructionFlag::Commutable); + Registry.configure({GO::G_SMULFIX, GO::G_UMULFIX, GO::G_SMULFIXSAT, GO::G_UMULFIXSAT, + GO::G_SDIVFIX, GO::G_UDIVFIX, GO::G_SDIVFIXSAT, GO::G_UDIVFIXSAT}, + {IntDef0, IntUse0, IntUse0, immediate()}, 1); + Registry.addFlag({GO::G_SMULFIX, GO::G_UMULFIX, GO::G_SMULFIXSAT, GO::G_UMULFIXSAT}, + InstructionFlag::Commutable); + + Registry.configure({GO::G_FNEG, GO::G_FABS, GO::G_FCANONICALIZE, GO::G_FEXP, GO::G_FEXP2, + GO::G_FEXP10, GO::G_FLOG, GO::G_FLOG2, GO::G_FLOG10, GO::G_FCEIL, + GO::G_FCOS, GO::G_FSIN, GO::G_FTAN, GO::G_FACOS, GO::G_FASIN, + GO::G_FATAN, GO::G_FCOSH, GO::G_FSINH, GO::G_FTANH, GO::G_FSQRT, + GO::G_FFLOOR, GO::G_FRINT, GO::G_FNEARBYINT}, + {FloatDef0, FloatUse0}, 1); + Registry.configure({GO::G_FPEXT, GO::G_FPTRUNC}, {FloatDef0, FloatUse1}, 1); + Registry.configure({GO::G_FPTOSI, GO::G_FPTOUI, GO::G_FPTOSI_SAT, GO::G_FPTOUI_SAT}, + {IntDef0, FloatUse1}, 1); + Registry.configure({GO::G_SITOFP, GO::G_UITOFP}, {FloatDef0, IntUse1}, 1); + Registry.configure({GO::G_FCOPYSIGN}, {FloatDef0, FloatUse0, FloatUse1}, 1); + Registry.configure({GO::G_IS_FPCLASS}, {IntDef0, FloatUse1, immediate()}, 1); + Registry.configure({GO::G_FADD, GO::G_FSUB, GO::G_FMUL, GO::G_FDIV, GO::G_FREM, GO::G_FPOW, + GO::G_FATAN2, GO::G_FMINNUM, GO::G_FMAXNUM, GO::G_FMINNUM_IEEE, + GO::G_FMAXNUM_IEEE, GO::G_FMINIMUM, GO::G_FMAXIMUM, GO::G_FMINIMUMNUM, + GO::G_FMAXIMUMNUM}, + {FloatDef0, FloatUse0, FloatUse0}, 1); + Registry.addFlag({GO::G_FADD, GO::G_FMUL, GO::G_FMINNUM, GO::G_FMAXNUM, GO::G_FMINNUM_IEEE, + GO::G_FMAXNUM_IEEE, GO::G_FMINIMUM, GO::G_FMAXIMUM, GO::G_FMINIMUMNUM, + GO::G_FMAXIMUMNUM}, + InstructionFlag::Commutable); + Registry.configure({GO::G_FMA, GO::G_FMAD}, {FloatDef0, FloatUse0, FloatUse0, FloatUse0}, 1); + Registry.configure({GO::G_FMODF, GO::G_FSINCOS}, {FloatDef0, FloatDef0, FloatUse0}, 2); + Registry.configure({GO::G_FPOWI, GO::G_FLDEXP}, {FloatDef0, FloatUse0, IntUse1}, 1); + Registry.configure({GO::G_FFREXP}, {FloatDef0, IntDef1, FloatUse0}, 2); + + Registry.configure({GO::G_GET_FPENV, GO::G_GET_FPMODE}, {AnyDef0}, 1, + {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_SET_FPENV, GO::G_SET_FPMODE}, {AnyUse0}, 0, + {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_RESET_FPENV, GO::G_RESET_FPMODE}, {}, 0, + {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_GET_ROUNDING}, {IntDef0}, 1, {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_SET_ROUNDING}, {IntUse0}, 0, {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_PTR_ADD}, {PointerDef0, PointerUse0, IntUse1}, 1); + Registry.configure({GO::G_PTRMASK}, {PointerDef0, PointerUse0, IntUse1}, 1); + Registry.configure({GO::G_ABS}, {IntDef0, IntUse0}, 1); + Registry.configure({GO::G_LROUND, GO::G_LLROUND}, {IntDef0, FloatUse1}, 1); + Registry.configure( + {GO::G_BR}, {kind(MachineOperand::Kind::BasicBlock)}, 0, + {InstructionFlag::Terminator, InstructionFlag::Branch, InstructionFlag::Barrier}); + Registry.configure({GO::G_BRJT}, + {ScalarPointerUse0, kind(MachineOperand::Kind::JumpTableIndex), ScalarIntUse1}, + 0, + {InstructionFlag::Terminator, InstructionFlag::Branch, + InstructionFlag::IndirectBranch, InstructionFlag::Barrier}); + Registry.configure({GO::G_VSCALE}, {ScalarIntDef0, immediate()}, 1); + + Registry.configure({GO::G_INSERT_SUBVECTOR}, + {VectorDef0, typedRegister(RegisterOperandRole::Use, VectorTypes, 0), + typedRegister(RegisterOperandRole::Use, VectorTypes, 1), immediate()}, + 1); + Registry.configure( + {GO::G_EXTRACT_SUBVECTOR}, + {VectorDef0, typedRegister(RegisterOperandRole::Use, VectorTypes, 1), immediate()}, 1); + Registry.configure( + {GO::G_INSERT_VECTOR_ELT}, + {VectorDef0, typedRegister(RegisterOperandRole::Use, VectorTypes, 0), AnyUse1, ScalarIntUse2}, + 1); + Registry.configure( + {GO::G_EXTRACT_VECTOR_ELT}, + {AnyDef0, typedRegister(RegisterOperandRole::Use, VectorTypes, 1), ScalarIntUse2}, 1); + Registry.configure({GO::G_SHUFFLE_VECTOR}, + {VectorDef0, typedRegister(RegisterOperandRole::Use, VectorTypes, 1), + typedRegister(RegisterOperandRole::Use, VectorTypes, 1), + kind(MachineOperand::Kind::ShuffleMask)}, + 1); + Registry.configure({GO::G_SPLAT_VECTOR}, {VectorDef0, AnyUse1}, 1); + Registry.configure({GO::G_STEP_VECTOR}, {VectorDef0, immediate()}, 1); + Registry.configure({GO::G_VECTOR_COMPRESS}, + {VectorDef0, typedRegister(RegisterOperandRole::Use, VectorTypes, 0), + typedRegister(RegisterOperandRole::Use, VectorTypes, 1), + typedRegister(RegisterOperandRole::Use, VectorTypes, 0)}, + 1); + + Registry.configure({GO::G_CTTZ, GO::G_CTTZ_ZERO_POISON, GO::G_CTLZ, GO::G_CTLZ_ZERO_POISON, + GO::G_CTLS, GO::G_CTPOP, GO::G_BSWAP, GO::G_BITREVERSE}, + {IntDef0, IntUse0}, 1); + Registry.configure({GO::G_ADDRSPACE_CAST}, {PointerDef0, PointerUse1}, 1); + Registry.configure({GO::G_BLOCK_ADDR}, + {ScalarPointerDef0, kind(MachineOperand::Kind::BlockAddress)}, 1); + Registry.configure({GO::G_JUMP_TABLE}, + {ScalarPointerDef0, kind(MachineOperand::Kind::JumpTableIndex)}, 1); + Registry.configure({GO::G_DYN_STACKALLOC}, {ScalarPointerDef0, ScalarIntUse1, immediate()}, 1, + {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_STACKSAVE}, {ScalarPointerDef0}, 1, {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_STACKRESTORE}, {ScalarPointerUse0}, 0, + {InstructionFlag::HasSideEffects}); + + Registry.configure({GO::G_STRICT_FADD, GO::G_STRICT_FSUB, GO::G_STRICT_FMUL, GO::G_STRICT_FDIV, + GO::G_STRICT_FREM}, + {FloatDef0, FloatUse0, FloatUse0}, 1, {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_STRICT_FMA}, {FloatDef0, FloatUse0, FloatUse0, FloatUse0}, 1, + {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_STRICT_FSQRT}, {FloatDef0, FloatUse0}, 1, + {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_STRICT_FLDEXP}, {FloatDef0, FloatUse0, IntUse1}, 1, + {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_STRICT_FCMP, GO::G_STRICT_FCMPS}, + {IntDef0, kind(MachineOperand::Kind::Predicate), FloatUse1, FloatUse1}, 1, + {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_READ_REGISTER}, {AnyDef0, kind(MachineOperand::Kind::Metadata)}, 1, + {InstructionFlag::HasSideEffects, InstructionFlag::Convergent}); + Registry.configure({GO::G_WRITE_REGISTER}, {kind(MachineOperand::Kind::Metadata), AnyUse0}, 0, + {InstructionFlag::HasSideEffects, InstructionFlag::Convergent}); + Registry.configure({GO::G_MEMCPY, GO::G_MEMMOVE}, + {ScalarPointerUse0, ScalarPointerUse1, ScalarIntUse2, immediate()}, 0, + {InstructionFlag::MayLoad, InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_MEMCPY_INLINE}, {ScalarPointerUse0, ScalarPointerUse1, ScalarIntUse2}, + 0, {InstructionFlag::MayLoad, InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_MEMSET}, {ScalarPointerUse0, ScalarIntUse1, ScalarIntUse2, immediate()}, + 0, {InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_BZERO}, {ScalarPointerUse0, ScalarIntUse1, immediate()}, 0, + {InstructionFlag::MayStore}, false, 0, true); + Registry.configure({GO::G_TRAP}, {}, 0, + {InstructionFlag::HasSideEffects, InstructionFlag::MayStore}); + Registry.configure({GO::G_DEBUGTRAP}, {}, 0, {InstructionFlag::HasSideEffects}); + Registry.configure({GO::G_UBSANTRAP}, {immediate()}, 0, {InstructionFlag::HasSideEffects}); + + Registry.configure({GO::G_VECREDUCE_SEQ_FADD, GO::G_VECREDUCE_SEQ_FMUL}, + {ScalarFloatDef0, typedRegister(RegisterOperandRole::Use, ScalarFloats, 1), + typedRegister(RegisterOperandRole::Use, VectorTypes, 2)}, + 1); + Registry.configure({GO::G_VECREDUCE_FADD, GO::G_VECREDUCE_FMUL, GO::G_VECREDUCE_FMAX, + GO::G_VECREDUCE_FMIN, GO::G_VECREDUCE_FMAXIMUM, GO::G_VECREDUCE_FMINIMUM}, + {ScalarFloatDef0, typedRegister(RegisterOperandRole::Use, VectorTypes, 1)}, 1); + Registry.configure({GO::G_VECREDUCE_ADD, GO::G_VECREDUCE_MUL, GO::G_VECREDUCE_AND, + GO::G_VECREDUCE_OR, GO::G_VECREDUCE_XOR, GO::G_VECREDUCE_SMAX, + GO::G_VECREDUCE_SMIN, GO::G_VECREDUCE_UMAX, GO::G_VECREDUCE_UMIN}, + {ScalarIntDef0, typedRegister(RegisterOperandRole::Use, VectorTypes, 1)}, 1); + Registry.configure({GO::G_SBFX, GO::G_UBFX}, + {ScalarIntDef0, ScalarIntUse0, ScalarIntUse1, ScalarIntUse1}, 1); +} + +[[nodiscard]] std::vector buildDescriptors() { + DescriptorRegistry Registry; + configureCoreOpcodes(Registry); + configureGenericOpcodes(Registry); + return Registry.take(); +} + +[[nodiscard]] const std::vector &descriptors() { + static const std::vector Value = buildDescriptors(); + return Value; +} + +} // namespace + +std::string_view getGenericOpcodeName(GenericOpcode OpcodeValue) noexcept { + const Opcode Value = opcode(OpcodeValue); + const auto Position = + std::ranges::find_if(descriptors(), [Value](const InstructionDescriptor &Descriptor) { + return Descriptor.InstructionOpcode == Value; + }); + return Position == descriptors().end() ? std::string_view{} : std::string_view(Position->Name); +} + +std::span genericInstructionDescriptors() noexcept { + return descriptors(); +} + +std::span genericImmediatePredicates() noexcept { + static const std::vector Predicates; + return Predicates; +} + +Expected appendGenericInstructionInfo(std::vector &Descriptors, + std::vector &Predicates) { + const auto ExistingOpcode = [&Descriptors](Opcode Value) { + return std::ranges::any_of(Descriptors, [Value](const InstructionDescriptor &Descriptor) { + return Descriptor.InstructionOpcode == Value; + }); + }; + for (const InstructionDescriptor &Descriptor : descriptors()) { + if (ExistingOpcode(Descriptor.InstructionOpcode)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "target instruction set already contains a target-independent opcode"); + } + Descriptors.push_back(Descriptor); + } + for (const ImmediatePredicate &Predicate : genericImmediatePredicates()) + Predicates.push_back(Predicate); + return {}; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineAnalyses.cpp b/backend/lib/CodeGen/MachineAnalyses.cpp new file mode 100644 index 0000000..cbc46fd --- /dev/null +++ b/backend/lib/CodeGen/MachineAnalyses.cpp @@ -0,0 +1,850 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineAnalyses.h" + +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +[[nodiscard]] std::vector linkedBlocks(MachineFunction &Function) { + std::vector Result; + Result.reserve(Function.blockCount()); + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) + Result.push_back(Block); + return Result; +} + +[[nodiscard]] std::unordered_map +blockOrder(std::span Blocks) { + std::unordered_map Result; + for (std::size_t Index = 0; Index < Blocks.size(); ++Index) + Result.emplace(Blocks[Index], Index); + return Result; +} + +[[nodiscard]] bool containsBlock(std::span Blocks, + const MachineBasicBlock *Block) { + return std::ranges::find(Blocks, Block) != Blocks.end(); +} + +[[nodiscard]] std::uint64_t saturatingAdd(std::uint64_t Left, std::uint64_t Right) noexcept { + if (std::numeric_limits::max() - Left < Right) + return std::numeric_limits::max(); + return Left + Right; +} + +[[nodiscard]] std::uint64_t saturatingMultiply(std::uint64_t Value, + std::uint64_t Multiplier) noexcept { + if (Value != 0 && Multiplier > std::numeric_limits::max() / Value) + return std::numeric_limits::max(); + return Value * Multiplier; +} + +[[nodiscard]] std::uint64_t scaleByProbability(std::uint64_t Value, + BranchProbability Probability) noexcept { + constexpr std::uint64_t Denominator = std::numeric_limits::max(); + const std::uint64_t Numerator = Probability.rawValue(); + const std::uint64_t Quotient = Value / Denominator; + const std::uint64_t Remainder = Value % Denominator; + return saturatingAdd(saturatingMultiply(Quotient, Numerator), + (Remainder * Numerator) / Denominator); +} + +[[nodiscard]] bool isKnownDistinctObject(const MachineMemOperandDesc &Left, + const MachineMemOperandDesc &Right) noexcept { + const auto IsUniqueObject = [](MemoryBase::Kind Kind) { + return Kind == MemoryBase::Kind::FrameIndex || Kind == MemoryBase::Kind::ConstantPool || + Kind == MemoryBase::Kind::JumpTable; + }; + if (IsUniqueObject(Left.Base.kind()) && IsUniqueObject(Right.Base.kind()) && + Left.Base.kind() != Right.Base.kind()) { + return true; + } + if (Left.Base.kind() != Right.Base.kind()) + return false; + switch (Left.Base.kind()) { + case MemoryBase::Kind::FrameIndex: + return Left.Base.frameIndex() != Right.Base.frameIndex(); + case MemoryBase::Kind::ConstantPool: + return Left.Base.constantPoolIndex() != Right.Base.constantPoolIndex(); + case MemoryBase::Kind::JumpTable: + return Left.Base.jumpTableIndex() != Right.Base.jumpTableIndex(); + default: + return false; + } +} + +[[nodiscard]] bool hasOrderedMemory(const MachineInstr &Instruction) noexcept { + for (const MachineMemOperand *Memory : Instruction.memOperands()) { + if (Memory != nullptr && (Memory->isAtomic() || Memory->isVolatile())) + return true; + } + return false; +} + +} // namespace + +Expected MachineDominatorTreeAnalysis::Result::build(MachineFunction &Function) { + Blocks = linkedBlocks(Function); + BlockToIndex = blockOrder(Blocks); + Dominators.assign(Blocks.size(), std::vector(Blocks.size(), false)); + ImmediateDominators.assign(Blocks.size(), nullptr); + Reachable.assign(Blocks.size(), false); + UnreachableBlocks.clear(); + if (Blocks.empty()) + return {}; + + std::vector Worklist{Blocks.front()}; + Reachable[0] = true; + for (std::size_t Position = 0; Position < Worklist.size(); ++Position) { + MachineBasicBlock *Block = Worklist[Position]; + for (const MachineSuccessor &Successor : Block->successors()) { + const auto Found = BlockToIndex.find(Successor.Block); + if (Successor.Block == nullptr || Found == BlockToIndex.end()) { + return makeUnexpected(ErrorCode::VerificationError, + "dominator analysis encountered an out-of-function CFG edge"); + } + if (!Reachable[Found->second]) { + Reachable[Found->second] = true; + Worklist.push_back(Successor.Block); + } + } + } + + for (std::size_t BlockIndex = 0; BlockIndex < Blocks.size(); ++BlockIndex) { + if (!Reachable[BlockIndex]) { + UnreachableBlocks.push_back(Blocks[BlockIndex]); + Dominators[BlockIndex][BlockIndex] = true; + continue; + } + if (BlockIndex == 0) { + Dominators[BlockIndex][BlockIndex] = true; + continue; + } + for (std::size_t Candidate = 0; Candidate < Blocks.size(); ++Candidate) + Dominators[BlockIndex][Candidate] = Reachable[Candidate]; + } + + bool Changed = true; + while (Changed) { + Changed = false; + for (std::size_t BlockIndex = 1; BlockIndex < Blocks.size(); ++BlockIndex) { + if (!Reachable[BlockIndex]) + continue; + std::vector NewDominators(Blocks.size(), false); + bool HasReachablePredecessor = false; + for (MachineBasicBlock *Predecessor : Blocks[BlockIndex]->predecessors()) { + const auto Found = BlockToIndex.find(Predecessor); + if (Found == BlockToIndex.end() || !Reachable[Found->second]) + continue; + if (!HasReachablePredecessor) { + NewDominators = Dominators[Found->second]; + HasReachablePredecessor = true; + } else { + for (std::size_t Candidate = 0; Candidate < Blocks.size(); ++Candidate) + NewDominators[Candidate] = + NewDominators[Candidate] && Dominators[Found->second][Candidate]; + } + } + if (!HasReachablePredecessor) { + return makeUnexpected(ErrorCode::VerificationError, + "reachable non-entry block has no reachable predecessor"); + } + NewDominators[BlockIndex] = true; + if (NewDominators != Dominators[BlockIndex]) { + Dominators[BlockIndex] = std::move(NewDominators); + Changed = true; + } + } + } + + for (std::size_t BlockIndex = 1; BlockIndex < Blocks.size(); ++BlockIndex) { + if (!Reachable[BlockIndex]) + continue; + std::size_t Best = Blocks.size(); + std::size_t BestDepth = 0; + for (std::size_t Candidate = 0; Candidate < Blocks.size(); ++Candidate) { + if (Candidate == BlockIndex || !Dominators[BlockIndex][Candidate]) + continue; + const std::size_t Depth = + static_cast(std::ranges::count(Dominators[Candidate], true)); + if (Best == Blocks.size() || Depth > BestDepth) { + Best = Candidate; + BestDepth = Depth; + } + } + if (Best == Blocks.size()) + return makeUnexpected(ErrorCode::InternalError, "reachable block has no immediate dominator"); + ImmediateDominators[BlockIndex] = Blocks[Best]; + } + return {}; +} + +Expected +MachineDominatorTreeAnalysis::Result::updateAfterCFGChange(MachineFunction &Function) { + return build(Function); +} + +bool MachineDominatorTreeAnalysis::Result::isReachable( + const MachineBasicBlock &Block) const noexcept { + const auto Found = BlockToIndex.find(&Block); + return Found != BlockToIndex.end() && Reachable[Found->second]; +} + +bool MachineDominatorTreeAnalysis::Result::dominates( + const MachineBasicBlock &Dominator, const MachineBasicBlock &Block) const noexcept { + const auto DominatorPosition = BlockToIndex.find(&Dominator); + const auto BlockPosition = BlockToIndex.find(&Block); + if (DominatorPosition == BlockToIndex.end() || BlockPosition == BlockToIndex.end() || + !Reachable[BlockPosition->second]) { + return false; + } + return Dominators[BlockPosition->second][DominatorPosition->second]; +} + +bool MachineDominatorTreeAnalysis::Result::dominates( + const MachineInstr &Dominator, const MachineInstr &Instruction) const noexcept { + const MachineBasicBlock *DominatorBlock = Dominator.parent(); + const MachineBasicBlock *InstructionBlock = Instruction.parent(); + if (DominatorBlock == nullptr || InstructionBlock == nullptr) + return false; + if (DominatorBlock != InstructionBlock) + return dominates(*DominatorBlock, *InstructionBlock); + for (const MachineInstr *Current = DominatorBlock->firstInstruction(); Current != nullptr; + Current = Current->next()) { + if (Current == &Dominator) + return true; + if (Current == &Instruction) + return false; + } + return false; +} + +const MachineBasicBlock *MachineDominatorTreeAnalysis::Result::immediateDominator( + const MachineBasicBlock &Block) const noexcept { + const auto Found = BlockToIndex.find(&Block); + return Found == BlockToIndex.end() ? nullptr : ImmediateDominators[Found->second]; +} + +const MachineBasicBlock *MachineDominatorTreeAnalysis::Result::nearestCommonDominator( + const MachineBasicBlock &Left, const MachineBasicBlock &Right) const noexcept { + if (!isReachable(Left) || !isReachable(Right)) + return nullptr; + std::unordered_set LeftAncestors; + for (const MachineBasicBlock *Current = &Left; Current != nullptr; + Current = immediateDominator(*Current)) { + LeftAncestors.insert(Current); + } + for (const MachineBasicBlock *Current = &Right; Current != nullptr; + Current = immediateDominator(*Current)) { + if (LeftAncestors.contains(Current)) + return Current; + } + return nullptr; +} + +Expected +MachineDominatorTreeAnalysis::run(MachineFunction &Function, const TargetDescription &, + MachineAnalysisManager &) { + Result ResultValue; + auto Built = ResultValue.build(Function); + if (!Built) + return std::unexpected(Built.error()); + return ResultValue; +} + +const MachineLoop * +MachineLoopAnalysis::Result::loopFor(const MachineBasicBlock &Block) const noexcept { + const auto Found = InnermostLoop.find(&Block); + return Found == InnermostLoop.end() ? nullptr : &Loops[Found->second]; +} + +std::uint32_t +MachineLoopAnalysis::Result::loopDepth(const MachineBasicBlock &Block) const noexcept { + const MachineLoop *Loop = loopFor(Block); + return Loop == nullptr ? 0 : Loop->Depth; +} + +bool MachineLoopAnalysis::Result::isIrreducible(const MachineBasicBlock &Block) const noexcept { + return IrreducibleBlocks.contains(&Block); +} + +Expected MachineLoopAnalysis::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + auto Dominators = Analyses.getResult(Function, Target); + if (!Dominators) + return std::unexpected(Dominators.error()); + + Result ResultValue; + std::vector Blocks = linkedBlocks(Function); + const auto Order = blockOrder(Blocks); + std::unordered_map> LoopBlocks; + std::unordered_map> LoopLatches; + + for (MachineBasicBlock *Latch : Blocks) { + if (!(*Dominators)->isReachable(*Latch)) + continue; + for (const MachineSuccessor &Successor : Latch->successors()) { + MachineBasicBlock *Header = Successor.Block; + if (Header == nullptr || !(*Dominators)->dominates(*Header, *Latch)) + continue; + auto &Members = LoopBlocks[Header]; + Members.insert(Header); + Members.insert(Latch); + LoopLatches[Header].push_back(Latch); + std::vector Worklist; + if (Latch != Header) + Worklist.push_back(Latch); + for (std::size_t Position = 0; Position < Worklist.size(); ++Position) { + MachineBasicBlock *Current = Worklist[Position]; + for (MachineBasicBlock *Predecessor : Current->predecessors()) { + if (!(*Dominators)->isReachable(*Predecessor) || + !(*Dominators)->dominates(*Header, *Predecessor)) { + continue; + } + if (Members.insert(Predecessor).second && Predecessor != Header) + Worklist.push_back(Predecessor); + } + } + } + } + + std::vector Headers; + Headers.reserve(LoopBlocks.size()); + for (const auto &[Header, Members] : LoopBlocks) { + (void)Members; + Headers.push_back(Header); + } + std::ranges::sort(Headers, + [&Order](const MachineBasicBlock *Left, const MachineBasicBlock *Right) { + return Order.at(Left) < Order.at(Right); + }); + for (MachineBasicBlock *Header : Headers) { + MachineLoop Loop; + Loop.Header = Header; + Loop.Blocks.assign(LoopBlocks[Header].begin(), LoopBlocks[Header].end()); + Loop.Latches = LoopLatches[Header]; + std::ranges::sort(Loop.Blocks, + [&Order](const MachineBasicBlock *Left, const MachineBasicBlock *Right) { + return Order.at(Left) < Order.at(Right); + }); + std::ranges::sort(Loop.Latches, + [&Order](const MachineBasicBlock *Left, const MachineBasicBlock *Right) { + return Order.at(Left) < Order.at(Right); + }); + Loop.Latches.erase(std::ranges::unique(Loop.Latches).begin(), Loop.Latches.end()); + ResultValue.Loops.push_back(std::move(Loop)); + } + + for (std::size_t Index = 0; Index < ResultValue.Loops.size(); ++Index) { + const MachineLoop &Loop = ResultValue.Loops[Index]; + std::size_t Parent = static_cast(-1); + for (std::size_t Candidate = 0; Candidate < ResultValue.Loops.size(); ++Candidate) { + if (Candidate == Index || ResultValue.Loops[Candidate].Blocks.size() <= Loop.Blocks.size()) { + continue; + } + const bool Contains = std::ranges::all_of(Loop.Blocks, [&](MachineBasicBlock *Block) { + return containsBlock(ResultValue.Loops[Candidate].Blocks, Block); + }); + if (Contains && + (Parent == static_cast(-1) || + ResultValue.Loops[Candidate].Blocks.size() < ResultValue.Loops[Parent].Blocks.size())) { + Parent = Candidate; + } + } + ResultValue.Loops[Index].Parent = Parent; + } + for (std::size_t Index = 0; Index < ResultValue.Loops.size(); ++Index) { + const std::size_t Parent = ResultValue.Loops[Index].Parent; + if (Parent != static_cast(-1)) + ResultValue.Loops[Parent].Children.push_back(Index); + std::uint32_t Depth = 1; + for (std::size_t Ancestor = Parent; Ancestor != static_cast(-1); + Ancestor = ResultValue.Loops[Ancestor].Parent) { + ++Depth; + } + ResultValue.Loops[Index].Depth = Depth; + } + for (std::size_t Index = 0; Index < ResultValue.Loops.size(); ++Index) { + for (MachineBasicBlock *Block : ResultValue.Loops[Index].Blocks) { + const auto Existing = ResultValue.InnermostLoop.find(Block); + if (Existing == ResultValue.InnermostLoop.end() || + ResultValue.Loops[Existing->second].Depth < ResultValue.Loops[Index].Depth) { + ResultValue.InnermostLoop[Block] = Index; + } + } + } + + std::unordered_set Visited; + std::vector FinishOrder; + for (MachineBasicBlock *Root : Blocks) { + if (!(*Dominators)->isReachable(*Root) || Visited.contains(Root)) + continue; + std::vector> Stack{{Root, 0}}; + Visited.insert(Root); + while (!Stack.empty()) { + auto &[Current, NextSuccessor] = Stack.back(); + if (NextSuccessor < Current->successors().size()) { + MachineBasicBlock *Next = Current->successors()[NextSuccessor++].Block; + if (Next != nullptr && (*Dominators)->isReachable(*Next) && Visited.insert(Next).second) + Stack.emplace_back(Next, 0); + continue; + } + FinishOrder.push_back(Current); + Stack.pop_back(); + } + } + + Visited.clear(); + for (auto RootPosition = FinishOrder.rbegin(); RootPosition != FinishOrder.rend(); + ++RootPosition) { + MachineBasicBlock *Root = *RootPosition; + if (!Visited.insert(Root).second) + continue; + std::vector Component; + std::vector Worklist{Root}; + for (std::size_t Position = 0; Position < Worklist.size(); ++Position) { + MachineBasicBlock *Current = Worklist[Position]; + Component.push_back(Current); + for (MachineBasicBlock *Predecessor : Current->predecessors()) { + if ((*Dominators)->isReachable(*Predecessor) && Visited.insert(Predecessor).second) + Worklist.push_back(Predecessor); + } + } + bool Cyclic = Component.size() > 1; + if (!Cyclic) { + Cyclic = std::ranges::any_of( + Component.front()->successors(), + [Root](const MachineSuccessor &Successor) { return Successor.Block == Root; }); + } + if (!Cyclic) + continue; + + std::unordered_set ComponentSet(Component.begin(), Component.end()); + std::unordered_set EntrySet; + for (MachineBasicBlock *Block : Component) { + if (std::ranges::any_of(Block->predecessors(), [&](MachineBasicBlock *Predecessor) { + return !ComponentSet.contains(Predecessor); + })) { + EntrySet.insert(Block); + } + } + if (EntrySet.size() <= 1) + continue; + + std::ranges::sort(Component, + [&Order](const MachineBasicBlock *Left, const MachineBasicBlock *Right) { + return Order.at(Left) < Order.at(Right); + }); + IrreducibleMachineRegion Region; + Region.Blocks = std::move(Component); + Region.Entries.assign(EntrySet.begin(), EntrySet.end()); + std::ranges::sort(Region.Entries, + [&Order](const MachineBasicBlock *Left, const MachineBasicBlock *Right) { + return Order.at(Left) < Order.at(Right); + }); + for (MachineBasicBlock *Block : Region.Blocks) + ResultValue.IrreducibleBlocks.insert(Block); + ResultValue.IrreducibleRegions.push_back(std::move(Region)); + } + std::ranges::sort( + ResultValue.IrreducibleRegions, + [&Order](const IrreducibleMachineRegion &Left, const IrreducibleMachineRegion &Right) { + return Order.at(Left.Blocks.front()) < Order.at(Right.Blocks.front()); + }); + return ResultValue; +} + +BranchProbability +MachineBranchProbabilityAnalysis::Result::probability(const MachineBasicBlock &From, + const MachineBasicBlock &To) const noexcept { + const auto Found = Probabilities.find(&From); + if (Found == Probabilities.end()) + return BranchProbability::zero(); + for (const MachineSuccessor &Successor : Found->second) { + if (Successor.Block == &To) + return Successor.Probability; + } + return BranchProbability::zero(); +} + +std::span MachineBranchProbabilityAnalysis::Result::successors( + const MachineBasicBlock &Block) const noexcept { + const auto Found = Probabilities.find(&Block); + return Found == Probabilities.end() ? std::span{} + : std::span{Found->second}; +} + +Expected +MachineBranchProbabilityAnalysis::run(MachineFunction &Function, const TargetDescription &, + MachineAnalysisManager &) { + Result ResultValue; + const std::vector Blocks = linkedBlocks(Function); + const auto Order = blockOrder(Blocks); + for (MachineBasicBlock *Block : Blocks) { + std::vector Successors(Block->successors().begin(), + Block->successors().end()); + for (const MachineSuccessor &Successor : Successors) { + if (Successor.Block == nullptr || !Order.contains(Successor.Block)) { + return makeUnexpected(ErrorCode::VerificationError, + "branch-probability analysis encountered an invalid CFG edge"); + } + } + ResultValue.Probabilities.emplace(Block, std::move(Successors)); + } + return ResultValue; +} + +std::uint64_t +MachineBlockFrequencyAnalysis::Result::frequency(const MachineBasicBlock &Block) const noexcept { + const auto Found = Frequencies.find(&Block); + return Found == Frequencies.end() ? 0 : Found->second; +} + +Expected +MachineBlockFrequencyAnalysis::run(MachineFunction &Function, const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + auto Dominators = Analyses.getResult(Function, Target); + auto Loops = Analyses.getResult(Function, Target); + auto Probabilities = Analyses.getResult(Function, Target); + if (!Dominators) + return std::unexpected(Dominators.error()); + if (!Loops) + return std::unexpected(Loops.error()); + if (!Probabilities) + return std::unexpected(Probabilities.error()); + + Result ResultValue; + MachineBasicBlock *Entry = Function.firstBlock(); + if (Entry == nullptr) + return ResultValue; + + std::unordered_set Visited; + std::vector PostOrder; + std::vector> Stack{{Entry, 0}}; + Visited.insert(Entry); + while (!Stack.empty()) { + auto &[Current, NextSuccessor] = Stack.back(); + const auto Successors = (*Probabilities)->successors(*Current); + if (NextSuccessor < Successors.size()) { + MachineBasicBlock *Next = Successors[NextSuccessor++].Block; + if (Next != nullptr && (*Dominators)->isReachable(*Next) && Visited.insert(Next).second) + Stack.emplace_back(Next, 0); + continue; + } + PostOrder.push_back(Current); + Stack.pop_back(); + } + std::ranges::reverse(PostOrder); + std::unordered_map BaseFrequencies; + BaseFrequencies[Entry] = EntryFrequency; + for (MachineBasicBlock *Block : PostOrder) { + const std::uint64_t Frequency = BaseFrequencies[Block]; + + const auto Successors = (*Probabilities)->successors(*Block); + const bool UseUniformProbability = + !Successors.empty() && std::ranges::all_of(Successors, [](const MachineSuccessor &Edge) { + return Edge.Probability == BranchProbability::zero(); + }); + for (std::size_t SuccessorIndex = 0; SuccessorIndex < Successors.size(); ++SuccessorIndex) { + const MachineSuccessor &Successor = Successors[SuccessorIndex]; + if (Successor.Block == nullptr || (*Dominators)->dominates(*Successor.Block, *Block)) + continue; + std::uint64_t Contribution = 0; + if (UseUniformProbability) { + const std::uint64_t Count = Successors.size(); + Contribution = Frequency / Count; + if (SuccessorIndex < Frequency % Count) + ++Contribution; + } else { + Contribution = scaleByProbability(Frequency, Successor.Probability); + } + BaseFrequencies[Successor.Block] = + saturatingAdd(BaseFrequencies[Successor.Block], Contribution); + } + } + for (MachineBasicBlock *Block : linkedBlocks(Function)) { + if (!(*Dominators)->isReachable(*Block)) { + ResultValue.Frequencies[Block] = 0; + continue; + } + std::uint64_t Frequency = std::max(BaseFrequencies[Block], 1); + for (std::uint32_t Level = 0; Level < (*Loops)->loopDepth(*Block); ++Level) + Frequency = saturatingMultiply(Frequency, 8); + ResultValue.Frequencies[Block] = Frequency; + } + return ResultValue; +} + +MachineAliasResult +MachineAliasAnalysis::Result::alias(const MachineMemOperand &Left, + const MachineMemOperand &Right) const noexcept { + const MachineMemOperandDesc &LeftDesc = Left.description(); + const MachineMemOperandDesc &RightDesc = Right.description(); + if (isKnownDistinctObject(LeftDesc, RightDesc)) + return MachineAliasResult::NoAlias; + + const bool SameBase = + LeftDesc.Base == RightDesc.Base && LeftDesc.Base.kind() != MemoryBase::Kind::Unknown; + const bool SameAliasSource = LeftDesc.AliasSource && RightDesc.AliasSource && + LeftDesc.AliasSource == RightDesc.AliasSource; + if (!SameBase && !SameAliasSource) + return MachineAliasResult::MayAlias; + if (!LeftDesc.Size.isKnown() || !RightDesc.Size.isKnown() || LeftDesc.Size.isScalable() || + RightDesc.Size.isScalable()) { + return MachineAliasResult::MayAlias; + } + + const std::uint64_t LeftSize = LeftDesc.Size.minimumBytes(); + const std::uint64_t RightSize = RightDesc.Size.minimumBytes(); + if (LeftDesc.Offset == RightDesc.Offset) + return LeftSize == RightSize ? MachineAliasResult::MustAlias : MachineAliasResult::PartialAlias; + + const bool LeftFirst = LeftDesc.Offset < RightDesc.Offset; + const std::int64_t Lower = LeftFirst ? LeftDesc.Offset : RightDesc.Offset; + const std::int64_t Higher = LeftFirst ? RightDesc.Offset : LeftDesc.Offset; + const std::uint64_t LowerSize = LeftFirst ? LeftSize : RightSize; + const std::uint64_t Distance = + static_cast(Higher) - static_cast(Lower); + return Distance >= LowerSize ? MachineAliasResult::NoAlias : MachineAliasResult::PartialAlias; +} + +Expected +MachineAliasAnalysis::run(MachineFunction &, const TargetDescription &, MachineAnalysisManager &) { + return Result{}; +} + +std::span MachineMemoryDependenceAnalysis::Result::dependencies( + const MachineInstr &Instruction) const noexcept { + const auto Found = DestinationRanges.find(Instruction.stableID()); + if (Found == DestinationRanges.end()) + return {}; + return std::span(Dependencies) + .subspan(Found->second.Begin, Found->second.Size); +} + +const MachineMemoryDependenceRegion * +MachineMemoryDependenceAnalysis::Result::regionFor(const MachineBasicBlock &Block) const noexcept { + const auto Found = BlockToRegion.find(&Block); + return Found == BlockToRegion.end() ? nullptr : &Regions[Found->second]; +} + +std::span MachineMemoryDependenceAnalysis::Result::dependencies( + const MachineBasicBlock &Block) const noexcept { + const auto Found = BlockRanges.find(&Block); + if (Found == BlockRanges.end()) + return {}; + return std::span(Dependencies) + .subspan(Found->second.Begin, Found->second.Size); +} + +Expected +MachineMemoryDependenceAnalysis::run(MachineFunction &Function, const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + auto Alias = Analyses.getResult(Function, Target); + if (!Alias) + return std::unexpected(Alias.error()); + + struct MemoryNode final { + MachineInstr *Instruction = nullptr; + bool Reads = false; + bool Writes = false; + bool Ordered = false; + bool Barrier = false; + }; + + Result ResultValue; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + std::vector Nodes; + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "memory-dependence analysis encountered an unknown opcode"); + } + MemoryNode Node; + Node.Instruction = Instruction; + Node.Reads = Descriptor->Flags.has(InstructionFlag::MayLoad); + Node.Writes = Descriptor->Flags.has(InstructionFlag::MayStore); + Node.Ordered = hasOrderedMemory(*Instruction); + Node.Barrier = Descriptor->Flags.has(InstructionFlag::Call) || + Descriptor->Flags.has(InstructionFlag::UnmodeledSideEffects) || + (Descriptor->Flags.has(InstructionFlag::HasSideEffects) && + Instruction->memOperands().empty()); + for (const MachineMemOperand *Memory : Instruction->memOperands()) { + if (Memory == nullptr) + continue; + Node.Reads = Node.Reads || Memory->isLoad(); + Node.Writes = Node.Writes || Memory->isStore(); + } + if (Node.Reads || Node.Writes || Node.Ordered || Node.Barrier) + Nodes.push_back(Node); + } + + MachineMemoryDependenceRegion Region; + Region.Block = Block; + Region.Instructions.reserve(Nodes.size()); + for (const MemoryNode &Node : Nodes) + Region.Instructions.push_back(Node.Instruction->stableID()); + ResultValue.BlockToRegion.emplace(Block, ResultValue.Regions.size()); + ResultValue.Regions.push_back(std::move(Region)); + + const std::size_t RegionBegin = ResultValue.Dependencies.size(); + for (std::size_t Destination = 0; Destination < Nodes.size(); ++Destination) { + for (std::size_t Source = 0; Source < Destination; ++Source) { + const MemoryNode &From = Nodes[Source]; + const MemoryNode &To = Nodes[Destination]; + if (!From.Writes && !To.Writes && !From.Ordered && !To.Ordered && !From.Barrier && + !To.Barrier) { + continue; + } + + bool MayAlias = From.Barrier || To.Barrier || From.Ordered || To.Ordered || + From.Instruction->memOperands().empty() || + To.Instruction->memOperands().empty(); + if (!MayAlias) { + for (const MachineMemOperand *Left : From.Instruction->memOperands()) { + for (const MachineMemOperand *Right : To.Instruction->memOperands()) { + if (Left != nullptr && Right != nullptr && + (*Alias)->alias(*Left, *Right) != MachineAliasResult::NoAlias) { + MayAlias = true; + break; + } + } + if (MayAlias) + break; + } + } + if (!MayAlias) + continue; + + MachineMemoryDependencyKind Kind = MachineMemoryDependencyKind::Ordered; + if (From.Writes && To.Reads) + Kind = MachineMemoryDependencyKind::Flow; + else if (From.Reads && To.Writes) + Kind = MachineMemoryDependencyKind::Anti; + else if (From.Writes && To.Writes) + Kind = MachineMemoryDependencyKind::Output; + ResultValue.Dependencies.push_back( + {From.Instruction->stableID(), To.Instruction->stableID(), Kind}); + } + } + + const std::size_t RegionEnd = ResultValue.Dependencies.size(); + ResultValue.BlockRanges.emplace(Block, Result::Range{RegionBegin, RegionEnd - RegionBegin}); + for (std::size_t Begin = RegionBegin; Begin < RegionEnd;) { + std::size_t End = Begin + 1; + while (End < RegionEnd && ResultValue.Dependencies[End].Destination == + ResultValue.Dependencies[Begin].Destination) { + ++End; + } + ResultValue.DestinationRanges.emplace(ResultValue.Dependencies[Begin].Destination, + Result::Range{Begin, End - Begin}); + Begin = End; + } + } + return ResultValue; +} + +Expected registerStage8MachineAnalyses(MachineAnalysisManager &Analyses) { + const std::array IDs{ + MachineAnalysisManager::id(), + MachineAnalysisManager::id(), + MachineAnalysisManager::id(), + MachineAnalysisManager::id(), + MachineAnalysisManager::id(), + MachineAnalysisManager::id(), + }; + const std::size_t Registered = static_cast( + std::ranges::count_if(IDs, [&Analyses](AnalysisID ID) { return Analyses.isRegistered(ID); })); + if (Registered == IDs.size()) + return {}; + if (Registered != 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "standard machine analyses are only partially registered"); + } + + auto Candidate = Analyses.forkEmpty(); + if (!Candidate) + return std::unexpected(Candidate.error()); + MachineAnalysisManager &Staging = **Candidate; + + auto Dominators = Staging.registerAnalysis({ + .Name = "MachineDominatorTree", + .Dependencies = {}, + .InvalidatedBy = {MachinePassChange::CFG, MachinePassChange::BlockLayout}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!Dominators) + return std::unexpected(Dominators.error()); + auto Loops = Staging.registerAnalysis({ + .Name = "MachineLoopInfo", + .Dependencies = {MachineAnalysisManager::id()}, + .InvalidatedBy = {MachinePassChange::CFG, MachinePassChange::BlockLayout}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!Loops) + return std::unexpected(Loops.error()); + auto Probabilities = Staging.registerAnalysis({ + .Name = "MachineBranchProbability", + .Dependencies = {}, + .InvalidatedBy = {MachinePassChange::CFG}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!Probabilities) + return std::unexpected(Probabilities.error()); + auto Frequencies = Staging.registerAnalysis({ + .Name = "MachineBlockFrequency", + .Dependencies = {MachineAnalysisManager::id(), + MachineAnalysisManager::id(), + MachineAnalysisManager::id()}, + .InvalidatedBy = {MachinePassChange::CFG, MachinePassChange::BlockLayout}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!Frequencies) + return std::unexpected(Frequencies.error()); + auto Alias = Staging.registerAnalysis({ + .Name = "MachineAliasAnalysis", + .Dependencies = {}, + .InvalidatedBy = {MachinePassChange::Operands, MachinePassChange::Frame, + MachinePassChange::ConstantPool, MachinePassChange::JumpTable, + MachinePassChange::TargetState}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!Alias) + return std::unexpected(Alias.error()); + auto MemoryDependence = Staging.registerAnalysis({ + .Name = "MachineMemoryDependence", + .Dependencies = {MachineAnalysisManager::id()}, + .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::CFG, MachinePassChange::BlockLayout, + MachinePassChange::Frame, MachinePassChange::ConstantPool, + MachinePassChange::JumpTable, MachinePassChange::TargetState}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!MemoryDependence) + return std::unexpected(MemoryDependence.error()); + Analyses.Registry = std::move(Staging.Registry); + return {}; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineIRBuilder.cpp b/backend/lib/CodeGen/MachineIRBuilder.cpp index e1e8006..6887804 100644 --- a/backend/lib/CodeGen/MachineIRBuilder.cpp +++ b/backend/lib/CodeGen/MachineIRBuilder.cpp @@ -650,6 +650,19 @@ Expected MachineIRBuilder::validateInstruction(const MachineInstr &Instruc return {}; } +Expected MachineIRBuilder::verifyInsertPoint() const { + if (InsertBlock == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); + auto BlockValidation = validateBlock(*InsertBlock); + if (!BlockValidation) + return std::unexpected(BlockValidation.error()); + if (InsertBefore != nullptr && InsertBefore->parent() != InsertBlock) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine IR builder insertion cursor is no longer in its block"); + } + return {}; +} + Expected MachineIRBuilder::setInsertPoint(MachineBasicBlock &Block) { auto Validation = validateBlock(Block); if (!Validation) diff --git a/backend/lib/CodeGen/MachinePass.cpp b/backend/lib/CodeGen/MachinePass.cpp new file mode 100644 index 0000000..e6dccd0 --- /dev/null +++ b/backend/lib/CodeGen/MachinePass.cpp @@ -0,0 +1,1370 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachinePass.h" + +#include "rcc/CodeGen/CompilationUnit.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineFunctionCloner.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +thread_local MachinePassInstrumentation::BufferedEvents *MachinePassInstrumentation::ActiveBuffer = + nullptr; + +namespace { + +using Clock = std::chrono::steady_clock; + +[[nodiscard]] std::uint64_t elapsedNanoseconds(Clock::time_point Start) noexcept { + const auto Elapsed = std::chrono::duration_cast(Clock::now() - Start); + if (Elapsed.count() <= 0) + return 0; + return static_cast(Elapsed.count()); +} + +[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) { + Prefix.append(Source.message()); + return Error(Source.code(), std::move(Prefix)); +} + +[[nodiscard]] bool hasDuplicateAnalysisIDs(std::span IDs) { + std::unordered_set Unique; + for (const AnalysisID ID : IDs) { + if (ID == nullptr || !Unique.insert(ID).second) + return true; + } + return false; +} + +[[nodiscard]] Expected validateParameters(std::span Parameters) { + std::unordered_set Names; + for (const PassParameter &Parameter : Parameters) { + if (Parameter.Name.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "pass parameter name cannot be empty"); + if (!Names.insert(Parameter.Name).second) + return makeUnexpected(ErrorCode::InvalidArgument, "pass parameter names must be unique"); + if (Parameter.Required && Parameter.DefaultValue) { + return makeUnexpected(ErrorCode::InvalidArgument, + "a required pass parameter cannot have a default value"); + } + } + return {}; +} + +void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept { + State ^= Value + 0x9e3779b97f4a7c15ULL + (State << 6U) + (State >> 2U); +} + +[[nodiscard]] std::uint64_t machineFunctionFingerprint(const MachineFunction &Function) noexcept { + std::uint64_t Result = 0xcbf29ce484222325ULL; + combineFingerprint(Result, Function.stableID().value()); + combineFingerprint(Result, Function.properties().rawValue()); + combineFingerprint(Result, Function.blockCount()); + combineFingerprint(Result, Function.allInstructions().size()); + combineFingerprint(Result, Function.allMemOperands().size()); + + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + combineFingerprint(Result, Block->stableID().value()); + combineFingerprint(Result, Block->instructionCount()); + combineFingerprint(Result, Block->successors().size()); + for (const MachineSuccessor &Successor : Block->successors()) { + combineFingerprint(Result, + Successor.Block == nullptr ? 0 : Successor.Block->stableID().value()); + combineFingerprint(Result, Successor.Probability.rawValue()); + } + for (const MachineBasicBlockLiveIn &LiveIn : Block->liveIns()) { + combineFingerprint(Result, LiveIn.PhysReg.number()); + combineFingerprint(Result, LiveIn.Lanes.rawValue()); + } + + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + combineFingerprint(Result, Instruction->stableID().value()); + combineFingerprint(Result, Instruction->opcode().value()); + combineFingerprint(Result, Instruction->flags().rawValue()); + combineFingerprint(Result, Instruction->operandCount()); + combineFingerprint(Result, Instruction->memOperands().size()); + for (const MachineOperand &Operand : Instruction->operands()) { + combineFingerprint(Result, static_cast(Operand.kind())); + combineFingerprint(Result, Operand.targetFlags()); + combineFingerprint(Result, Operand.registerFlags().rawValue()); + combineFingerprint(Result, Operand.subReg().value()); + if (const Register *Reg = Operand.getIf()) + combineFingerprint(Result, Reg->opaqueValue()); + else if (const std::int64_t *Immediate = Operand.getIf()) + combineFingerprint(Result, static_cast(*Immediate)); + } + } + } + return Result; +} + +[[nodiscard]] Expected verifyCompilationUnit(const CompilationUnit &Unit, + const TargetDescription &Target) { + auto UnitVerification = Unit.verify(); + if (!UnitVerification) + return std::unexpected(UnitVerification.error()); + for (std::size_t Index = 0; Index < Unit.functionCount(); ++Index) { + const MachineFunction *Function = Unit.functionAt(Index); + if (Function == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "compilation unit function order contains a null entry"); + auto FunctionVerification = MachineVerifier::verify(*Function, Target); + if (!FunctionVerification) + return std::unexpected(FunctionVerification.error()); + } + return {}; +} + +} // namespace + +Expected +MachineAnalysisManager::registerAnalysisImpl(MachineAnalysisRegistration Registration, + ErasedRunner Runner, ErasedInvalidator Invalidator) { + if (Registration.ID == nullptr || Registration.Name.empty() || !Runner || !Invalidator) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine analysis registration is incomplete"); + } + if (hasDuplicateAnalysisIDs(Registration.Dependencies)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine analysis dependencies must be non-null and unique"); + } + if (std::ranges::find(Registration.Dependencies, Registration.ID) != + Registration.Dependencies.end()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine analysis cannot directly depend on itself"); + } + if (Registry.contains(Registration.ID)) + return makeUnexpected(ErrorCode::InvalidArgument, "machine analysis ID is already registered"); + if (std::ranges::any_of(Registry, [&Registration](const auto &Entry) { + return Entry.second.Info.Name == Registration.Name; + })) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine analysis name is already registered"); + } + Registry.emplace(Registration.ID, RegisteredAnalysis{std::move(Registration), std::move(Runner), + std::move(Invalidator)}); + return {}; +} + +bool MachineAnalysisManager::isRegistered(AnalysisID ID) const noexcept { + return ID != nullptr && Registry.contains(ID); +} + +bool MachineAnalysisManager::hasCached(const MachineFunction &Function, + AnalysisID ID) const noexcept { + const auto FunctionPosition = Cache.find(const_cast(&Function)); + if (FunctionPosition == Cache.end()) + return false; + const auto AnalysisPosition = FunctionPosition->second.find(ID); + return AnalysisPosition != FunctionPosition->second.end() && AnalysisPosition->second.Value; +} + +std::size_t +MachineAnalysisManager::cachedResultCount(const MachineFunction &Function) const noexcept { + const auto Position = Cache.find(const_cast(&Function)); + return Position == Cache.end() ? 0 : Position->second.size(); +} + +Expected +MachineAnalysisManager::materializeDependencies(const RegisteredAnalysis &Registration, + MachineFunction &Function, + const TargetDescription &Target) { + for (const AnalysisID Dependency : Registration.Info.Dependencies) { + if (!Registry.contains(Dependency)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine analysis depends on an unregistered analysis"); + } + auto Result = getResultImpl(Dependency, Function, Target); + if (!Result) + return std::unexpected(Result.error()); + } + return {}; +} + +Expected MachineAnalysisManager::getResultImpl(AnalysisID ID, MachineFunction &Function, + const TargetDescription &Target) { + if (ID == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "machine analysis ID cannot be null"); + + auto &FunctionCache = Cache[&Function]; + if (const auto Cached = FunctionCache.find(ID); + Cached != FunctionCache.end() && Cached->second.Value) { + const auto Registration = Registry.find(ID); + const std::string_view Name = Registration == Registry.end() + ? std::string_view{"unknown-machine-analysis"} + : std::string_view{Registration->second.Info.Name}; + if (Instrumentation != nullptr) + Instrumentation->afterAnalysis(Name, Function, true, 0); + return Cached->second.Value.get(); + } + + const auto RegistrationPosition = Registry.find(ID); + if (RegistrationPosition == Registry.end()) + return makeUnexpected(ErrorCode::InvalidArgument, "machine analysis ID is not registered"); + const RegisteredAnalysis &Registration = RegistrationPosition->second; + + auto &Stack = ActiveComputations[&Function]; + if (std::ranges::find(Stack, ID) != Stack.end()) { + Error Failure(ErrorCode::InvalidArgument, + "machine analysis dependency cycle reaches '" + Registration.Info.Name + "'"); + if (Instrumentation != nullptr) + Instrumentation->analysisFailure(Registration.Info.Name, Function, Failure, 0); + return std::unexpected(std::move(Failure)); + } + + if (Instrumentation != nullptr) + Instrumentation->beforeAnalysis(Registration.Info.Name, Function); + const Clock::time_point Start = Clock::now(); + Stack.push_back(ID); + auto Dependencies = materializeDependencies(Registration, Function, Target); + if (!Dependencies) { + Stack.pop_back(); + if (Stack.empty()) + ActiveComputations.erase(&Function); + Error Failure = prefixedError(Dependencies.error(), + "machine analysis '" + Registration.Info.Name + "' failed: "); + if (Instrumentation != nullptr) { + Instrumentation->analysisFailure(Registration.Info.Name, Function, Failure, + elapsedNanoseconds(Start)); + } + return std::unexpected(std::move(Failure)); + } + + auto Computed = Registration.Runner(Function, Target, *this); + Stack.pop_back(); + if (Stack.empty()) + ActiveComputations.erase(&Function); + const std::uint64_t Duration = elapsedNanoseconds(Start); + if (!Computed) { + Error Failure = prefixedError(Computed.error(), + "machine analysis '" + Registration.Info.Name + "' failed: "); + if (Instrumentation != nullptr) + Instrumentation->analysisFailure(Registration.Info.Name, Function, Failure, Duration); + return std::unexpected(std::move(Failure)); + } + if (!*Computed) { + Error Failure(ErrorCode::InternalError, + "machine analysis '" + Registration.Info.Name + "' returned a null result"); + if (Instrumentation != nullptr) + Instrumentation->analysisFailure(Registration.Info.Name, Function, Failure, Duration); + return std::unexpected(std::move(Failure)); + } + + void *Result = Computed->get(); + FunctionCache.emplace(ID, CacheEntry{std::move(*Computed), ID}); + if (Instrumentation != nullptr) + Instrumentation->afterAnalysis(Registration.Info.Name, Function, false, Duration); + return Result; +} + +void MachineAnalysisManager::invalidate(MachineFunction &Function, + const PreservedAnalyses &Preserved, + MachinePassChanges Changes) noexcept { + const auto FunctionPosition = Cache.find(&Function); + if (FunctionPosition == Cache.end() || Preserved.preservesAll() || Changes.empty()) + return; + + std::unordered_set Invalid; + for (auto &[ID, Entry] : FunctionPosition->second) { + if (Preserved.preserves(ID)) + continue; + const auto Registration = Registry.find(ID); + if (Registration == Registry.end() || + Registration->second.Info.InvalidatedBy.intersects(Changes)) { + const bool ShouldInvalidate = + Registration == Registry.end() || !Entry.Value || !Registration->second.Invalidator || + Registration->second.Invalidator(Entry.Value.get(), Function, Preserved); + if (ShouldInvalidate) + Invalid.insert(ID); + } + } + + bool Added = true; + while (Added) { + Added = false; + for (const auto &[ID, Entry] : FunctionPosition->second) { + (void)Entry; + if (Invalid.contains(ID) || Preserved.preserves(ID)) + continue; + const auto Registration = Registry.find(ID); + if (Registration != Registry.end() && + std::ranges::any_of( + Registration->second.Info.Dependencies, + [&Invalid](AnalysisID Dependency) { return Invalid.contains(Dependency); })) { + Added = Invalid.insert(ID).second || Added; + } + } + } + + for (const AnalysisID ID : Invalid) + FunctionPosition->second.erase(ID); + if (FunctionPosition->second.empty()) + Cache.erase(FunctionPosition); +} + +void MachineAnalysisManager::clear(MachineFunction &Function) noexcept { + Cache.erase(&Function); + ActiveComputations.erase(&Function); +} + +void MachineAnalysisManager::clearAll() noexcept { + Cache.clear(); + ActiveComputations.clear(); +} + +Expected> MachineAnalysisManager::forkEmpty() const { + if (!ActiveComputations.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "cannot fork a machine analysis manager during analysis computation"); + } + auto Result = std::make_unique(); + Result->Registry = Registry; + return Result; +} + +Expected MachineAnalysisManager::validateParallelRequirements( + std::span RequiredAnalyses) const { + std::vector Worklist(RequiredAnalyses.begin(), RequiredAnalyses.end()); + std::unordered_set Visited; + for (std::size_t Index = 0; Index < Worklist.size(); ++Index) { + const AnalysisID ID = Worklist[Index]; + if (ID == nullptr || !Visited.insert(ID).second) + continue; + const auto Position = Registry.find(ID); + if (Position == Registry.end()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "parallel machine pass requires an unregistered analysis"); + } + if (Position->second.Info.ThreadSafety != PassThreadSafety::ThreadSafe) { + return makeUnexpected(ErrorCode::InvalidArgument, + "parallel machine pipeline requires analysis '" + + Position->second.Info.Name + "' to be marked thread-safe"); + } + Worklist.insert(Worklist.end(), Position->second.Info.Dependencies.begin(), + Position->second.Info.Dependencies.end()); + } + return {}; +} + +Expected MachineAnalysisManager::requestAction(std::string_view Action, + const MachineFunction &Function, + std::uint64_t Cost) { + if (Action.empty() || Cost == 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "machine action requires a name and nonzero cost"); + if (Instrumentation == nullptr) + return true; + return Instrumentation->requestAction(Action, Function, Cost); +} + +Expected CompilationUnitAnalysisManager::registerAnalysisImpl( + CompilationUnitAnalysisRegistration Registration, ErasedRunner Runner, + ErasedInvalidator Invalidator) { + if (Registration.ID == nullptr || Registration.Name.empty() || !Runner || !Invalidator) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit analysis registration is incomplete"); + } + if (hasDuplicateAnalysisIDs(Registration.Dependencies)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit analysis dependencies must be non-null and unique"); + } + if (std::ranges::find(Registration.Dependencies, Registration.ID) != + Registration.Dependencies.end()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit analysis cannot directly depend on itself"); + } + if (Registry.contains(Registration.ID)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit analysis ID is already registered"); + } + if (std::ranges::any_of(Registry, [&Registration](const auto &Entry) { + return Entry.second.Info.Name == Registration.Name; + })) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit analysis name is already registered"); + } + Registry.emplace(Registration.ID, RegisteredAnalysis{std::move(Registration), std::move(Runner), + std::move(Invalidator)}); + return {}; +} + +bool CompilationUnitAnalysisManager::isRegistered(AnalysisID ID) const noexcept { + return ID != nullptr && Registry.contains(ID); +} + +bool CompilationUnitAnalysisManager::hasCached(const CompilationUnit &Unit, + AnalysisID ID) const noexcept { + const auto UnitPosition = Cache.find(const_cast(&Unit)); + if (UnitPosition == Cache.end()) + return false; + const auto AnalysisPosition = UnitPosition->second.find(ID); + return AnalysisPosition != UnitPosition->second.end() && AnalysisPosition->second.Value; +} + +Expected +CompilationUnitAnalysisManager::materializeDependencies(const RegisteredAnalysis &Registration, + CompilationUnit &Unit, + const TargetDescription &Target) { + for (const AnalysisID Dependency : Registration.Info.Dependencies) { + if (!Registry.contains(Dependency)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit analysis depends on an unregistered analysis"); + } + auto Result = getResultImpl(Dependency, Unit, Target); + if (!Result) + return std::unexpected(Result.error()); + } + return {}; +} + +Expected CompilationUnitAnalysisManager::getResultImpl(AnalysisID ID, CompilationUnit &Unit, + const TargetDescription &Target) { + if (ID == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit analysis ID cannot be null"); + auto &UnitCache = Cache[&Unit]; + if (const auto Cached = UnitCache.find(ID); Cached != UnitCache.end() && Cached->second.Value) { + const auto Registration = Registry.find(ID); + const std::string_view Name = Registration == Registry.end() + ? std::string_view{"unknown-compilation-unit-analysis"} + : std::string_view{Registration->second.Info.Name}; + if (Instrumentation != nullptr) + Instrumentation->afterUnitAnalysis(Name, Unit, true, 0); + return Cached->second.Value.get(); + } + + const auto RegistrationPosition = Registry.find(ID); + if (RegistrationPosition == Registry.end()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit analysis ID is not registered"); + } + const RegisteredAnalysis &Registration = RegistrationPosition->second; + auto &Stack = ActiveComputations[&Unit]; + if (std::ranges::find(Stack, ID) != Stack.end()) { + Error Failure(ErrorCode::InvalidArgument, + "compilation-unit analysis dependency cycle reaches '" + Registration.Info.Name + + "'"); + if (Instrumentation != nullptr) + Instrumentation->unitAnalysisFailure(Registration.Info.Name, Unit, Failure, 0); + return std::unexpected(std::move(Failure)); + } + + if (Instrumentation != nullptr) + Instrumentation->beforeUnitAnalysis(Registration.Info.Name, Unit); + const Clock::time_point Start = Clock::now(); + Stack.push_back(ID); + auto Dependencies = materializeDependencies(Registration, Unit, Target); + if (!Dependencies) { + Stack.pop_back(); + if (Stack.empty()) + ActiveComputations.erase(&Unit); + Error Failure = prefixedError(Dependencies.error(), "compilation-unit analysis '" + + Registration.Info.Name + "' failed: "); + if (Instrumentation != nullptr) { + Instrumentation->unitAnalysisFailure(Registration.Info.Name, Unit, Failure, + elapsedNanoseconds(Start)); + } + return std::unexpected(std::move(Failure)); + } + + auto Computed = Registration.Runner(Unit, Target, *this); + Stack.pop_back(); + if (Stack.empty()) + ActiveComputations.erase(&Unit); + const std::uint64_t Duration = elapsedNanoseconds(Start); + if (!Computed) { + Error Failure = prefixedError(Computed.error(), "compilation-unit analysis '" + + Registration.Info.Name + "' failed: "); + if (Instrumentation != nullptr) + Instrumentation->unitAnalysisFailure(Registration.Info.Name, Unit, Failure, Duration); + return std::unexpected(std::move(Failure)); + } + if (!*Computed) { + Error Failure(ErrorCode::InternalError, "compilation-unit analysis '" + Registration.Info.Name + + "' returned a null result"); + if (Instrumentation != nullptr) + Instrumentation->unitAnalysisFailure(Registration.Info.Name, Unit, Failure, Duration); + return std::unexpected(std::move(Failure)); + } + + void *Result = Computed->get(); + UnitCache.emplace(ID, CacheEntry{std::move(*Computed), ID}); + if (Instrumentation != nullptr) + Instrumentation->afterUnitAnalysis(Registration.Info.Name, Unit, false, Duration); + return Result; +} + +void CompilationUnitAnalysisManager::invalidate(CompilationUnit &Unit, + const PreservedAnalyses &Preserved, + MachinePassChanges Changes) noexcept { + const auto UnitPosition = Cache.find(&Unit); + if (UnitPosition == Cache.end() || Preserved.preservesAll() || Changes.empty()) + return; + + std::unordered_set Invalid; + for (auto &[ID, Entry] : UnitPosition->second) { + if (Preserved.preserves(ID)) + continue; + const auto Registration = Registry.find(ID); + if (Registration == Registry.end() || + Registration->second.Info.InvalidatedBy.intersects(Changes)) { + const bool ShouldInvalidate = + Registration == Registry.end() || !Entry.Value || !Registration->second.Invalidator || + Registration->second.Invalidator(Entry.Value.get(), Unit, Preserved); + if (ShouldInvalidate) + Invalid.insert(ID); + } + } + + bool Added = true; + while (Added) { + Added = false; + for (const auto &[ID, Entry] : UnitPosition->second) { + (void)Entry; + if (Invalid.contains(ID) || Preserved.preserves(ID)) + continue; + const auto Registration = Registry.find(ID); + if (Registration != Registry.end() && + std::ranges::any_of( + Registration->second.Info.Dependencies, + [&Invalid](AnalysisID Dependency) { return Invalid.contains(Dependency); })) { + Added = Invalid.insert(ID).second || Added; + } + } + } + for (const AnalysisID InvalidID : Invalid) + UnitPosition->second.erase(InvalidID); + if (UnitPosition->second.empty()) + Cache.erase(UnitPosition); +} + +void CompilationUnitAnalysisManager::clear(CompilationUnit &Unit) noexcept { + Cache.erase(&Unit); + ActiveComputations.erase(&Unit); +} + +void CompilationUnitAnalysisManager::clearAll() noexcept { + Cache.clear(); + ActiveComputations.clear(); +} + +void MachinePassInstrumentation::addBeforeCallback(BeforeCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + Before.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addAfterCallback(AfterCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + After.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addFailureCallback(FailureCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + Failure.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addBeforeAnalysisCallback(BeforeAnalysisCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + BeforeAnalysis.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addAfterAnalysisCallback(AfterAnalysisCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + AfterAnalysis.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addAnalysisFailureCallback(AnalysisFailureCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + AnalysisFailure.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addIRPrintCallback(IRPrintCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + IRPrint.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addChangeCallback(ChangeCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + Change.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::setActionFilter(ActionFilter NewFilter) { + std::scoped_lock Lock(Mutex); + Filter = std::move(NewFilter); +} + +void MachinePassInstrumentation::setPerFunctionFuel(std::optional Fuel) { + std::scoped_lock Lock(Mutex); + PerFunctionFuel = Fuel; + ConsumedFuel.clear(); +} + +void MachinePassInstrumentation::addBeforeUnitCallback(BeforeUnitCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + BeforeUnit.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addAfterUnitCallback(AfterUnitCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + AfterUnit.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addUnitFailureCallback(UnitFailureCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + UnitFailure.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addBeforeUnitAnalysisCallback( + BeforeUnitAnalysisCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + BeforeUnitAnalysis.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addAfterUnitAnalysisCallback(AfterUnitAnalysisCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + AfterUnitAnalysis.push_back(std::move(Callback)); +} + +void MachinePassInstrumentation::addUnitAnalysisFailureCallback( + UnitAnalysisFailureCallback Callback) { + if (!Callback) + return; + std::scoped_lock Lock(Mutex); + UnitAnalysisFailure.push_back(std::move(Callback)); +} + +InstrumentationStatistic &MachinePassInstrumentation::statistic(std::string_view Name, + bool IsAnalysis) const { + const std::string Key = std::string(IsAnalysis ? "analysis:" : "pass:") + std::string(Name); + auto [Position, Inserted] = Statistics.try_emplace(Key); + if (Inserted) { + Position->second.Name = std::string(Name); + Position->second.IsAnalysis = IsAnalysis; + } + return Position->second; +} + +bool MachinePassInstrumentation::bufferFunctionEvent( + const MachineFunction &Function, std::function Replay) const { + if (ActiveBuffer == nullptr) + return false; + + std::shared_ptr Snapshot; + auto Cloned = cloneMachineFunction( + Function, *ActiveBuffer->Target, + MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); + if (Cloned) { + Snapshot = std::shared_ptr(std::move(Cloned->ClonedFunction)); + } else { + Snapshot = + std::shared_ptr(&Function, [](const MachineFunction *) noexcept {}); + } + ActiveBuffer->Events.emplace_back( + [Snapshot = std::move(Snapshot), Replay = std::move(Replay)]() { Replay(*Snapshot); }); + return true; +} + +void MachinePassInstrumentation::beginBuffering(BufferedEvents &Buffer, + const TargetDescription &Target) const noexcept { + Buffer.Target = &Target; + Buffer.Events.clear(); + ActiveBuffer = &Buffer; +} + +void MachinePassInstrumentation::endBuffering() const noexcept { + ActiveBuffer = nullptr; +} + +void MachinePassInstrumentation::replayBufferedEvents(BufferedEvents &Buffer) const { + for (const std::function &Event : Buffer.Events) + Event(); + Buffer.Events.clear(); + Buffer.Target = nullptr; +} + +void MachinePassInstrumentation::before(std::string_view Name, + const MachineFunction &Function) const { + if (bufferFunctionEvent(Function, [this, Name = std::string(Name)](const MachineFunction &Input) { + before(Name, Input); + })) { + return; + } + std::vector Callbacks; + std::vector Printers; + { + std::scoped_lock Lock(Mutex); + Callbacks = Before; + Printers = IRPrint; + } + for (const BeforeCallback &Callback : Callbacks) + Callback(Name, Function); + for (const IRPrintCallback &Printer : Printers) + Printer(InstrumentationPhase::Before, Name, Function); +} + +void MachinePassInstrumentation::after(std::string_view Name, const MachineFunction &Function, + const MachinePassResult &Result, + std::uint64_t Nanoseconds) const { + if (bufferFunctionEvent(Function, [this, Name = std::string(Name), Result, + Nanoseconds](const MachineFunction &Input) { + after(Name, Input, Result, Nanoseconds); + })) { + return; + } + std::vector Callbacks; + std::vector Printers; + { + std::scoped_lock Lock(Mutex); + InstrumentationStatistic &Record = statistic(Name, false); + ++Record.Invocations; + Record.Changes += Result.Changed ? 1U : 0U; + Record.TotalNanoseconds += Nanoseconds; + Callbacks = After; + Printers = IRPrint; + } + for (const AfterCallback &Callback : Callbacks) + Callback(Name, Function, Result); + for (const IRPrintCallback &Printer : Printers) + Printer(InstrumentationPhase::After, Name, Function); +} + +void MachinePassInstrumentation::failure(std::string_view Name, const MachineFunction &Function, + const Error &ErrorValue, std::uint64_t Nanoseconds) const { + if (bufferFunctionEvent(Function, [this, Name = std::string(Name), ErrorValue, + Nanoseconds](const MachineFunction &Input) { + failure(Name, Input, ErrorValue, Nanoseconds); + })) { + return; + } + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + InstrumentationStatistic &Record = statistic(Name, false); + ++Record.Invocations; + ++Record.Failures; + Record.TotalNanoseconds += Nanoseconds; + Callbacks = Failure; + } + for (const FailureCallback &Callback : Callbacks) + Callback(Name, Function, ErrorValue); +} + +void MachinePassInstrumentation::beforeAnalysis(std::string_view Name, + const MachineFunction &Function) const { + if (bufferFunctionEvent(Function, [this, Name = std::string(Name)](const MachineFunction &Input) { + beforeAnalysis(Name, Input); + })) { + return; + } + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + Callbacks = BeforeAnalysis; + } + for (const BeforeAnalysisCallback &Callback : Callbacks) + Callback(Name, Function); +} + +void MachinePassInstrumentation::afterAnalysis(std::string_view Name, + const MachineFunction &Function, bool CacheHit, + std::uint64_t Nanoseconds) const { + if (bufferFunctionEvent(Function, [this, Name = std::string(Name), CacheHit, + Nanoseconds](const MachineFunction &Input) { + afterAnalysis(Name, Input, CacheHit, Nanoseconds); + })) { + return; + } + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + InstrumentationStatistic &Record = statistic(Name, true); + ++Record.Invocations; + Record.CacheHits += CacheHit ? 1U : 0U; + Record.TotalNanoseconds += Nanoseconds; + Callbacks = AfterAnalysis; + } + for (const AfterAnalysisCallback &Callback : Callbacks) + Callback(Name, Function, CacheHit, Nanoseconds); +} + +void MachinePassInstrumentation::analysisFailure(std::string_view Name, + const MachineFunction &Function, + const Error &ErrorValue, + std::uint64_t Nanoseconds) const { + if (bufferFunctionEvent(Function, [this, Name = std::string(Name), ErrorValue, + Nanoseconds](const MachineFunction &Input) { + analysisFailure(Name, Input, ErrorValue, Nanoseconds); + })) { + return; + } + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + InstrumentationStatistic &Record = statistic(Name, true); + ++Record.Invocations; + ++Record.Failures; + Record.TotalNanoseconds += Nanoseconds; + Callbacks = AnalysisFailure; + } + for (const AnalysisFailureCallback &Callback : Callbacks) + Callback(Name, Function, ErrorValue); +} + +void MachinePassInstrumentation::change(std::string_view Name, const MachineFunction &Function, + MachinePassChanges Changes, bool FingerprintChanged) const { + if (bufferFunctionEvent(Function, [this, Name = std::string(Name), Changes, + FingerprintChanged](const MachineFunction &Input) { + change(Name, Input, Changes, FingerprintChanged); + })) { + return; + } + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + Callbacks = Change; + } + for (const ChangeCallback &Callback : Callbacks) + Callback(Name, Function, Changes, FingerprintChanged); +} + +Expected MachinePassInstrumentation::requestAction(std::string_view Action, + const MachineFunction &Function, + std::uint64_t Cost) { + std::scoped_lock ActionLock(ActionMutex); + ActionFilter CurrentFilter; + { + std::scoped_lock Lock(Mutex); + CurrentFilter = Filter; + } + if (CurrentFilter && !CurrentFilter(Action, Function, Cost)) + return false; + + std::scoped_lock Lock(Mutex); + if (!PerFunctionFuel) + return true; + std::uint64_t &Consumed = ConsumedFuel[Function.stableID().value()]; + if (Consumed > *PerFunctionFuel || Cost > *PerFunctionFuel - Consumed) + return false; + Consumed += Cost; + return true; +} + +void MachinePassInstrumentation::beforeUnit(std::string_view Name, + const CompilationUnit &Unit) const { + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + Callbacks = BeforeUnit; + } + for (const BeforeUnitCallback &Callback : Callbacks) + Callback(Name, Unit); +} + +void MachinePassInstrumentation::afterUnit(std::string_view Name, const CompilationUnit &Unit, + const CompilationUnitPassResult &Result, + std::uint64_t Nanoseconds) const { + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + InstrumentationStatistic &Record = statistic("unit:" + std::string(Name), false); + ++Record.Invocations; + Record.Changes += Result.Changed ? 1U : 0U; + Record.TotalNanoseconds += Nanoseconds; + Callbacks = AfterUnit; + } + for (const AfterUnitCallback &Callback : Callbacks) + Callback(Name, Unit, Result); +} + +void MachinePassInstrumentation::unitFailure(std::string_view Name, const CompilationUnit &Unit, + const Error &ErrorValue, + std::uint64_t Nanoseconds) const { + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + InstrumentationStatistic &Record = statistic("unit:" + std::string(Name), false); + ++Record.Invocations; + ++Record.Failures; + Record.TotalNanoseconds += Nanoseconds; + Callbacks = UnitFailure; + } + for (const UnitFailureCallback &Callback : Callbacks) + Callback(Name, Unit, ErrorValue); +} + +void MachinePassInstrumentation::beforeUnitAnalysis(std::string_view Name, + const CompilationUnit &Unit) const { + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + Callbacks = BeforeUnitAnalysis; + } + for (const BeforeUnitAnalysisCallback &Callback : Callbacks) + Callback(Name, Unit); +} + +void MachinePassInstrumentation::afterUnitAnalysis(std::string_view Name, + const CompilationUnit &Unit, bool CacheHit, + std::uint64_t Nanoseconds) const { + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + InstrumentationStatistic &Record = statistic("unit:" + std::string(Name), true); + ++Record.Invocations; + Record.CacheHits += CacheHit ? 1U : 0U; + Record.TotalNanoseconds += Nanoseconds; + Callbacks = AfterUnitAnalysis; + } + for (const AfterUnitAnalysisCallback &Callback : Callbacks) + Callback(Name, Unit, CacheHit, Nanoseconds); +} + +void MachinePassInstrumentation::unitAnalysisFailure(std::string_view Name, + const CompilationUnit &Unit, + const Error &ErrorValue, + std::uint64_t Nanoseconds) const { + std::vector Callbacks; + { + std::scoped_lock Lock(Mutex); + InstrumentationStatistic &Record = statistic("unit:" + std::string(Name), true); + ++Record.Invocations; + ++Record.Failures; + Record.TotalNanoseconds += Nanoseconds; + Callbacks = UnitAnalysisFailure; + } + for (const UnitAnalysisFailureCallback &Callback : Callbacks) + Callback(Name, Unit, ErrorValue); +} + +std::vector MachinePassInstrumentation::statistics() const { + std::vector Result; + { + std::scoped_lock Lock(Mutex); + Result.reserve(Statistics.size()); + for (const auto &[Key, Record] : Statistics) { + (void)Key; + Result.push_back(Record); + } + } + std::ranges::sort( + Result, [](const InstrumentationStatistic &Left, const InstrumentationStatistic &Right) { + if (Left.IsAnalysis != Right.IsAnalysis) + return Left.IsAnalysis < Right.IsAnalysis; + return Left.Name < Right.Name; + }); + return Result; +} + +void MachinePassInstrumentation::clearStatistics() { + std::scoped_lock Lock(Mutex); + Statistics.clear(); + ConsumedFuel.clear(); +} + +Expected MachinePassManager::validateContract(const MachinePassContract &Contract) const { + if (Contract.Name.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "machine pass must have a non-empty name"); + if (Contract.Sets.intersects(Contract.Clears)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine pass cannot set and clear the same property"); + } + if (hasDuplicateAnalysisIDs(Contract.RequiredAnalyses)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine pass required analyses must be non-null and unique"); + } + return validateParameters(Contract.Parameters); +} + +Expected MachinePassManager::addPass(std::unique_ptr Pass) { + if (!Pass) + return makeUnexpected(ErrorCode::InvalidArgument, + "machine pass manager cannot add a null pass"); + auto Validation = validateContract(Pass->contract()); + if (!Validation) + return std::unexpected(Validation.error()); + Passes.push_back(std::move(Pass)); + return {}; +} + +Expected MachinePassManager::run(MachineFunction &Function, const TargetDescription &Target, + MachineAnalysisManager &Analyses, + MachinePassInstrumentation *Instrumentation) const { + Analyses.setInstrumentation(Instrumentation); + for (const std::unique_ptr &Pass : Passes) { + const MachinePassContract &Contract = Pass->contract(); + const std::string_view Name = Contract.Name; + + if (const MachineFunctionProperties Missing = + Contract.Requires.missingFrom(Function.properties()); + !Missing.empty()) { + Error Failure(ErrorCode::VerificationError, + "pass '" + std::string(Name) + "' requires properties: " + Missing.toString()); + if (Instrumentation != nullptr) + Instrumentation->failure(Name, Function, Failure); + Analyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + + if (Options.VerifyBefore) { + auto Verification = MachineVerifier::verify(Function, Target); + if (!Verification) { + Error Failure = prefixedError(Verification.error(), "pass '" + std::string(Name) + + "' received invalid MachineIR: "); + if (Instrumentation != nullptr) + Instrumentation->failure(Name, Function, Failure); + Analyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + } + + for (const AnalysisID Required : Contract.RequiredAnalyses) { + auto Result = Analyses.getResultImpl(Required, Function, Target); + if (!Result) { + Error Failure = + prefixedError(Result.error(), "pass '" + std::string(Name) + + "' could not materialize a required analysis: "); + if (Instrumentation != nullptr) + Instrumentation->failure(Name, Function, Failure); + Analyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + } + + const std::uint64_t FingerprintBefore = + Options.DetectUnreportedChanges ? machineFunctionFingerprint(Function) : 0; + if (Instrumentation != nullptr) + Instrumentation->before(Name, Function); + const Clock::time_point Start = Clock::now(); + auto PassResult = Pass->run(Function, Target, Analyses); + const std::uint64_t Duration = elapsedNanoseconds(Start); + if (!PassResult) { + Error Failure = + prefixedError(PassResult.error(), "pass '" + std::string(Name) + "' failed: "); + if (Instrumentation != nullptr) + Instrumentation->failure(Name, Function, Failure, Duration); + Analyses.clear(Function); + Analyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + + if (PassResult->Changed != !PassResult->Changes.empty()) { + Error Failure(ErrorCode::VerificationError, + "pass '" + std::string(Name) + + "' reported inconsistent changed state and modification categories"); + if (Instrumentation != nullptr) + Instrumentation->failure(Name, Function, Failure, Duration); + Analyses.clear(Function); + Analyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + if (!Contract.DeclaredChanges.contains(PassResult->Changes)) { + Error Failure(ErrorCode::VerificationError, + "pass '" + std::string(Name) + + "' reported a modification category absent from its registration"); + if (Instrumentation != nullptr) + Instrumentation->failure(Name, Function, Failure, Duration); + Analyses.clear(Function); + Analyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + + bool FingerprintChanged = PassResult->Changed; + if (Options.DetectUnreportedChanges) { + FingerprintChanged = FingerprintBefore != machineFunctionFingerprint(Function); + if (FingerprintChanged && !PassResult->Changed) { + Error Failure(ErrorCode::VerificationError, + "pass '" + std::string(Name) + + "' changed MachineIR without reporting a modification"); + if (Instrumentation != nullptr) + Instrumentation->failure(Name, Function, Failure, Duration); + Analyses.clear(Function); + Analyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + } + if (Instrumentation != nullptr) + Instrumentation->change(Name, Function, PassResult->Changes, FingerprintChanged); + + auto Transition = + Function.properties().applyTransition(Contract.Requires, Contract.Sets, Contract.Clears); + if (!Transition) { + Error Failure = + prefixedError(Transition.error(), "pass '" + std::string(Name) + + "' produced an invalid property transition: "); + if (Instrumentation != nullptr) + Instrumentation->failure(Name, Function, Failure, Duration); + Analyses.clear(Function); + Analyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + Analyses.invalidate(Function, PassResult->Preserved, PassResult->Changes); + + if (Options.VerifyEach) { + MachineVerifierOptions VerifyOptions; + VerifyOptions.Stage = Contract.VerificationStage; + auto Verification = MachineVerifier::verify(Function, Target, VerifyOptions); + if (!Verification) { + Error Failure = prefixedError(Verification.error(), + "pass '" + std::string(Name) + "' left invalid MachineIR: "); + if (Instrumentation != nullptr) + Instrumentation->failure(Name, Function, Failure, Duration); + Analyses.clear(Function); + Analyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + } + if (Instrumentation != nullptr) + Instrumentation->after(Name, Function, *PassResult, Duration); + } + Analyses.setInstrumentation(nullptr); + return {}; +} + +Expected MachinePassManager::runFunctions(CompilationUnit &Unit, + const TargetDescription &Target, + const MachineAnalysisManager &AnalysisPrototype, + std::size_t ThreadCount, + MachinePassInstrumentation *Instrumentation) const { + if (ThreadCount == 0) + return makeUnexpected(ErrorCode::InvalidArgument, "machine pass thread count must be nonzero"); + auto UnitVerification = verifyCompilationUnit(Unit, Target); + if (!UnitVerification) + return std::unexpected(UnitVerification.error()); + const std::size_t FunctionCount = Unit.functionCount(); + if (FunctionCount == 0) + return {}; + const std::size_t WorkerCount = std::min(ThreadCount, FunctionCount); + if (WorkerCount > 1) { + for (const std::unique_ptr &Pass : Passes) { + if (Pass->contract().ThreadSafety != PassThreadSafety::ThreadSafe) { + return makeUnexpected(ErrorCode::InvalidArgument, + "parallel machine pipeline contains a pass not marked thread-safe"); + } + auto AnalysisSafety = + AnalysisPrototype.validateParallelRequirements(Pass->contract().RequiredAnalyses); + if (!AnalysisSafety) + return std::unexpected(AnalysisSafety.error()); + } + } + std::vector> Managers; + Managers.reserve(FunctionCount); + for (std::size_t Index = 0; Index < FunctionCount; ++Index) { + auto Manager = AnalysisPrototype.forkEmpty(); + if (!Manager) + return std::unexpected(Manager.error()); + Managers.push_back(std::move(*Manager)); + } + + std::vector> Failures(FunctionCount); + std::vector EventBuffers(FunctionCount); + std::atomic NextFunction = 0; + const auto Worker = [&]() { + while (true) { + const std::size_t Index = NextFunction.fetch_add(1, std::memory_order_relaxed); + if (Index >= FunctionCount) + return; + MachineFunction *Function = Unit.functionAt(Index); + if (Function == nullptr) { + Failures[Index] = Error(ErrorCode::InternalError, + "compilation unit contains a null function during parallel run"); + continue; + } + if (Instrumentation != nullptr) + Instrumentation->beginBuffering(EventBuffers[Index], Target); + auto Result = run(*Function, Target, *Managers[Index], Instrumentation); + if (Instrumentation != nullptr) + Instrumentation->endBuffering(); + if (!Result) + Failures[Index] = Result.error(); + } + }; + + std::vector Workers; + Workers.reserve(WorkerCount); + for (std::size_t Index = 0; Index < WorkerCount; ++Index) + Workers.emplace_back(Worker); + for (std::thread &WorkerThread : Workers) + WorkerThread.join(); + + for (std::size_t Index = 0; Index < FunctionCount; ++Index) { + if (Instrumentation != nullptr) + Instrumentation->replayBufferedEvents(EventBuffers[Index]); + if (Failures[Index]) { + return std::unexpected( + prefixedError(*Failures[Index], + "function '" + std::string(Unit.functionAt(Index)->name()) + "' failed: ")); + } + } + return {}; +} + +Expected CompilationUnitPassManager::addPass(std::unique_ptr Pass) { + if (!Pass) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit pass manager cannot add a null pass"); + } + const CompilationUnitPassContract &Contract = Pass->contract(); + if (Contract.Name.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit pass must have a non-empty name"); + } + if (hasDuplicateAnalysisIDs(Contract.RequiredAnalyses)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "compilation-unit pass required analyses must be non-null and unique"); + } + auto Parameters = validateParameters(Contract.Parameters); + if (!Parameters) + return std::unexpected(Parameters.error()); + Passes.push_back(std::move(Pass)); + return {}; +} + +Expected CompilationUnitPassManager::run(CompilationUnit &Unit, + const TargetDescription &Target, + CompilationUnitAnalysisManager &UnitAnalyses, + MachineAnalysisManager &FunctionAnalyses, + MachinePassInstrumentation *Instrumentation) const { + UnitAnalyses.setInstrumentation(Instrumentation); + FunctionAnalyses.setInstrumentation(Instrumentation); + for (const std::unique_ptr &Pass : Passes) { + const CompilationUnitPassContract &Contract = Pass->contract(); + const std::string_view Name = Contract.Name; + + if (Options.VerifyBefore) { + auto Verification = verifyCompilationUnit(Unit, Target); + if (!Verification) { + Error Failure = + prefixedError(Verification.error(), "compilation-unit pass '" + std::string(Name) + + "' received invalid MachineIR: "); + if (Instrumentation != nullptr) + Instrumentation->unitFailure(Name, Unit, Failure); + UnitAnalyses.setInstrumentation(nullptr); + FunctionAnalyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + } + + for (const AnalysisID Required : Contract.RequiredAnalyses) { + auto Result = UnitAnalyses.getResultImpl(Required, Unit, Target); + if (!Result) { + Error Failure = + prefixedError(Result.error(), "compilation-unit pass '" + std::string(Name) + + "' could not materialize a required analysis: "); + if (Instrumentation != nullptr) + Instrumentation->unitFailure(Name, Unit, Failure); + UnitAnalyses.setInstrumentation(nullptr); + FunctionAnalyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + } + + if (Instrumentation != nullptr) + Instrumentation->beforeUnit(Name, Unit); + const Clock::time_point Start = Clock::now(); + auto Result = Pass->run(Unit, Target, UnitAnalyses, FunctionAnalyses); + const std::uint64_t Duration = elapsedNanoseconds(Start); + if (!Result) { + Error Failure = prefixedError(Result.error(), + "compilation-unit pass '" + std::string(Name) + "' failed: "); + if (Instrumentation != nullptr) + Instrumentation->unitFailure(Name, Unit, Failure, Duration); + UnitAnalyses.clearAll(); + FunctionAnalyses.clearAll(); + UnitAnalyses.setInstrumentation(nullptr); + FunctionAnalyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + if (Result->Changed != !Result->Changes.empty() || + !Contract.DeclaredChanges.contains(Result->Changes)) { + Error Failure(ErrorCode::VerificationError, + "compilation-unit pass '" + std::string(Name) + + "' reported inconsistent or undeclared modifications"); + if (Instrumentation != nullptr) + Instrumentation->unitFailure(Name, Unit, Failure, Duration); + UnitAnalyses.clearAll(); + FunctionAnalyses.clearAll(); + UnitAnalyses.setInstrumentation(nullptr); + FunctionAnalyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + + UnitAnalyses.invalidate(Unit, Result->PreservedUnitAnalyses, Result->Changes); + for (std::size_t Index = 0; Index < Unit.functionCount(); ++Index) { + MachineFunction *Function = Unit.functionAt(Index); + if (Function != nullptr) { + FunctionAnalyses.invalidate(*Function, Result->PreservedFunctionAnalyses, Result->Changes); + } + } + if (Options.VerifyEach) { + auto Verification = verifyCompilationUnit(Unit, Target); + if (!Verification) { + Error Failure = + prefixedError(Verification.error(), "compilation-unit pass '" + std::string(Name) + + "' left invalid MachineIR: "); + if (Instrumentation != nullptr) + Instrumentation->unitFailure(Name, Unit, Failure, Duration); + UnitAnalyses.clearAll(); + FunctionAnalyses.clearAll(); + UnitAnalyses.setInstrumentation(nullptr); + FunctionAnalyses.setInstrumentation(nullptr); + return std::unexpected(std::move(Failure)); + } + } + if (Instrumentation != nullptr) + Instrumentation->afterUnit(Name, Unit, *Result, Duration); + } + UnitAnalyses.setInstrumentation(nullptr); + FunctionAnalyses.setInstrumentation(nullptr); + return {}; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/TargetCallLowering.cpp b/backend/lib/CodeGen/TargetCallLowering.cpp new file mode 100644 index 0000000..d6a14b7 --- /dev/null +++ b/backend/lib/CodeGen/TargetCallLowering.cpp @@ -0,0 +1,353 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/TargetCallLowering.h" + +#include "rcc/CodeGen/MachineIRBuilder.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +[[nodiscard]] bool isKnownExtension(ABIExtensionKind Extension) noexcept { + return Extension < ABIExtensionKind::Count; +} + +[[nodiscard]] bool isKnownLocationKind(CCLocationKind Kind) noexcept { + return Kind <= CCLocationKind::Custom; +} + +[[nodiscard]] bool isKnownTailCallKind(TailCallKind Kind) noexcept { + return Kind <= TailCallKind::MustTail; +} + +[[nodiscard]] bool addOverflows(std::uint64_t Left, std::uint64_t Right) noexcept { + return Left > std::numeric_limits::max() - Right; +} + +[[nodiscard]] Expected verifyAssignment(const CCAssignment &Assignment, + bool AllowNoRegister) { + if (Assignment.OriginalValue.isNoRegister() && !AllowNoRegister) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering assignment requires a machine register value"); + } + if (!Assignment.ValueType.isValid() || !Assignment.LocationType.isValid() || + !Assignment.ValueType.isScalarValue() || !Assignment.LocationType.isScalarValue()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering assignments require scalar value and location LLTs"); + } + if (Assignment.FragmentCount == 0 || Assignment.FragmentIndex >= Assignment.FragmentCount) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering assignment has invalid fragment coordinates"); + } + if (Assignment.LocationSizeBytes == 0 || Assignment.StackSlotSizeBytes == 0 || + Assignment.LocationSizeBytes > Assignment.StackSlotSizeBytes || + !isKnownExtension(Assignment.Extension) || !isKnownLocationKind(Assignment.LocationKind)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering assignment has invalid size or extension metadata"); + } + + const bool HasRegister = Assignment.LocationRegister.has_value(); + const bool HasStack = Assignment.StackOffsetBytes.has_value(); + if (HasRegister && !Assignment.LocationRegister->isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering assignment names an invalid physical register"); + } + if (HasStack && *Assignment.StackOffsetBytes % Assignment.LocationAlignment.bytes() != 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "stack assignment offset violates its location alignment"); + } + switch (Assignment.LocationKind) { + case CCLocationKind::Register: + if (!HasRegister || HasStack) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register assignment must name exactly one physical register"); + } + break; + case CCLocationKind::Stack: + if (HasRegister || !HasStack) { + return makeUnexpected(ErrorCode::InvalidArgument, + "stack assignment must name exactly one stack offset"); + } + break; + case CCLocationKind::Indirect: + if (HasRegister == HasStack || !Assignment.CustomFlags.has(CCAssignmentFlag::Indirect)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "indirect assignment must have one transport location and its flag"); + } + break; + case CCLocationKind::Custom: + if (HasRegister && HasStack) { + return makeUnexpected(ErrorCode::InvalidArgument, + "custom assignment cannot use register and stack simultaneously"); + } + break; + } + return {}; +} + +[[nodiscard]] Expected verifyAssignments(std::span Assignments, + bool AllowNoRegister, + const StackArgumentArea &StackArea) { + std::unordered_set Registers; + std::vector> StackRanges; + StackRanges.reserve(Assignments.size()); + for (const CCAssignment &Assignment : Assignments) { + auto Verification = verifyAssignment(Assignment, AllowNoRegister); + if (!Verification) + return std::unexpected(Verification.error()); + if (Assignment.LocationRegister && !Registers.insert(*Assignment.LocationRegister).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering assignments reuse a physical location register"); + } + if (!Assignment.StackOffsetBytes) + continue; + if (addOverflows(*Assignment.StackOffsetBytes, Assignment.StackSlotSizeBytes)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering stack assignment range overflows uint64"); + } + const std::uint64_t End = *Assignment.StackOffsetBytes + Assignment.StackSlotSizeBytes; + if (End > StackArea.SizeBytes) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering stack assignment exceeds its argument area"); + } + StackRanges.emplace_back(*Assignment.StackOffsetBytes, End); + } + + std::ranges::sort(StackRanges); + for (std::size_t Index = 1; Index < StackRanges.size(); ++Index) { + if (StackRanges[Index].first < StackRanges[Index - 1].second) { + return makeUnexpected(ErrorCode::InvalidArgument, "call-lowering stack assignments overlap"); + } + } + return {}; +} + +[[nodiscard]] Expected verifyVarArgs(const VarArgLoweringState &State) { + if (!State.IsVariadic) { + if (State.FixedArgumentCount != 0 || State.FirstUnallocatedIntegerRegister != 0 || + State.OverflowAreaOffsetBytes != 0 || State.RegisterSaveAreaOffsetBytes != 0 || + State.RegisterSaveAreaSizeBytes != 0 || State.RegisterSavePaddingBytes != 0 || + !State.RegistersToSave.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "non-variadic plan contains variadic lowering state"); + } + return {}; + } + + if (State.RegisterSaveAreaSizeBytes == 0 && !State.RegistersToSave.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "variadic register saves require a nonempty save area"); + } + if (State.RegisterSaveAreaSizeBytes % 8 != 0 || State.RegisterSavePaddingBytes % 8 != 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "variadic register-save size and padding must be XLEN aligned"); + } + std::unordered_set SavedRegisters; + std::unordered_set SavedOffsets; + for (const VarArgRegisterSave Save : State.RegistersToSave) { + if (!Save.Reg.isValid() || !SavedRegisters.insert(Save.Reg).second || + Save.OffsetBytes % 8 != 0 || !SavedOffsets.insert(Save.OffsetBytes).second || + addOverflows(Save.OffsetBytes, std::uint64_t{8}) || + Save.OffsetBytes + 8 > State.RegisterSaveAreaSizeBytes) { + return makeUnexpected(ErrorCode::InvalidArgument, + "variadic register-save entry is invalid or outside its area"); + } + } + return {}; +} + +} // namespace + +ABIValueFlags::ABIValueFlags(std::initializer_list Flags) noexcept { + for (const ABIValueFlag Flag : Flags) + set(Flag); +} + +CCAssignmentFlags::CCAssignmentFlags(std::initializer_list Flags) noexcept { + for (const CCAssignmentFlag Flag : Flags) + set(Flag); +} + +Expected MachineCallTarget::globalSymbol(std::string Name, + std::uint32_t TargetFlags) { + if (Name.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "global call target name cannot be empty"); + return MachineCallTarget(MachineCallTargetKind::GlobalSymbol, std::move(Name), TargetFlags); +} + +Expected MachineCallTarget::externalSymbol(std::string Name, + std::uint32_t TargetFlags) { + if (Name.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "external call target name cannot be empty"); + return MachineCallTarget(MachineCallTargetKind::ExternalSymbol, std::move(Name), TargetFlags); +} + +Expected MachineCallTarget::indirect(Register Callee, + std::uint32_t TargetFlags) { + if (Callee.isNoRegister()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "indirect call target requires a machine register"); + } + return MachineCallTarget(MachineCallTargetKind::IndirectRegister, Callee, TargetFlags); +} + +std::string_view MachineCallTarget::symbolName() const noexcept { + const auto *Name = std::get_if(&Value); + return Name == nullptr ? std::string_view{} : std::string_view(*Name); +} + +Register MachineCallTarget::indirectRegister() const noexcept { + const auto *Reg = std::get_if(&Value); + return Reg == nullptr ? Register{} : *Reg; +} + +Expected CallLoweringPlan::create(CallLoweringPlanDesc Description) { + if (Description.Target.empty() || Description.Convention.value() == 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering plan requires target and calling-convention identities"); + } + if (Description.Kind > CallLoweringPlanKind::Return || + !isKnownTailCallKind(Description.TailDecision)) { + return makeUnexpected(ErrorCode::InvalidArgument, "call-lowering plan kind is invalid"); + } + if (Description.StackArguments.ShadowSpaceBytes > Description.StackArguments.SizeBytes || + Description.StackArguments.SizeBytes % Description.StackArguments.Align.bytes() != 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering stack argument area is malformed"); + } + if (Description.CallFrame.SizeBytes % Description.CallFrame.Align.bytes() != 0 || + Description.CallFrame.EmitSetup != Description.CallFrame.EmitDestroy) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering call-frame requirements are inconsistent"); + } + + auto ArgumentVerification = + verifyAssignments(Description.ArgumentAssignments, false, Description.StackArguments); + if (!ArgumentVerification) + return std::unexpected(ArgumentVerification.error()); + const bool AllowNoReturnRegister = Description.Kind == CallLoweringPlanKind::Call && + Description.TailDecision != TailCallKind::NotTail; + auto ReturnVerification = verifyAssignments(Description.ReturnAssignments, AllowNoReturnRegister, + StackArgumentArea{0, 0, Alignment{}}); + if (!ReturnVerification) + return std::unexpected(ReturnVerification.error()); + auto VarArgVerification = verifyVarArgs(Description.VarArgs); + if (!VarArgVerification) + return std::unexpected(VarArgVerification.error()); + + switch (Description.Kind) { + case CallLoweringPlanKind::FormalArguments: + if (!Description.ReturnAssignments.empty() || Description.Callee || Description.PreservedMask || + Description.CallSiteID != 0 || Description.TailDecision != TailCallKind::NotTail || + Description.CallFrame.EmitSetup || Description.CallFrame.ReusesIncomingArea || + !Description.ByValCopies.empty() || !Description.TailRejectionReason.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "formal-argument plan contains call or return state"); + } + break; + case CallLoweringPlanKind::Return: + if (!Description.ArgumentAssignments.empty() || Description.Callee || + Description.PreservedMask || Description.CallSiteID != 0 || + Description.TailDecision != TailCallKind::NotTail || Description.CallFrame.EmitSetup || + Description.CallFrame.ReusesIncomingArea || !Description.ByValCopies.empty() || + Description.VarArgs.IsVariadic || !Description.TailRejectionReason.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "return plan contains formal-argument or call state"); + } + break; + case CallLoweringPlanKind::Call: + if (!Description.Callee || !Description.Callee->isValid() || !Description.PreservedMask || + Description.CallSiteID == 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call plan requires a callee, call-site ID, and preserved mask"); + } + if (Description.TailDecision == TailCallKind::NotTail) { + if (!Description.CallFrame.EmitSetup || Description.CallFrame.ReusesIncomingArea) { + return makeUnexpected(ErrorCode::InvalidArgument, + "ordinary call plan requires a private call frame"); + } + } else if (Description.CallFrame.EmitSetup || !Description.CallFrame.ReusesIncomingArea || + !Description.TailRejectionReason.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "tail-call plan must reuse the caller's incoming argument area"); + } + if (Description.CallFrame.SizeBytes < Description.StackArguments.SizeBytes) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call frame does not contain the stack-argument area"); + } + break; + } + + std::unordered_set ByValAssignments; + std::vector> ByValRanges; + for (const ByValCopyAssignment &Copy : Description.ByValCopies) { + if (Copy.ArgumentAssignmentIndex >= Description.ArgumentAssignments.size() || + !ByValAssignments.insert(Copy.ArgumentAssignmentIndex).second || + Copy.Source.isNoRegister() || !Copy.PointerType.isPointer() || Copy.SizeBytes == 0 || + Copy.StackOffsetBytes % Copy.Align.bytes() != 0 || + Copy.StackOffsetBytes < Description.StackArguments.SizeBytes || + !Description.ArgumentAssignments[Copy.ArgumentAssignmentIndex].CustomFlags.has( + CCAssignmentFlag::ByVal) || + addOverflows(Copy.StackOffsetBytes, Copy.SizeBytes) || + Copy.StackOffsetBytes + Copy.SizeBytes > Description.CallFrame.SizeBytes) { + return makeUnexpected(ErrorCode::InvalidArgument, + "call-lowering byval copy is malformed or outside the call frame"); + } + ByValRanges.emplace_back(Copy.StackOffsetBytes, Copy.StackOffsetBytes + Copy.SizeBytes); + } + std::ranges::sort(ByValRanges); + for (std::size_t Index = 1; Index < ByValRanges.size(); ++Index) { + if (ByValRanges[Index].first < ByValRanges[Index - 1].second) { + return makeUnexpected(ErrorCode::InvalidArgument, "call-lowering byval copy ranges overlap"); + } + } + + return CallLoweringPlan(std::move(Description)); +} + +Expected +TargetCallLowering::lowerFormalArguments(MachineIRBuilder &Builder, + const FormalArgumentRequest &Request) const { + auto Plan = planFormalArguments(Request); + if (!Plan) + return std::unexpected(Plan.error()); + if (Plan->kind() != CallLoweringPlanKind::FormalArguments) { + return makeUnexpected(ErrorCode::InternalError, + "target returned the wrong call-lowering plan kind for formal arguments"); + } + return emitPlan(Builder, *Plan); +} + +Expected TargetCallLowering::lowerCall(MachineIRBuilder &Builder, + const CallLoweringRequest &Request) const { + auto Plan = planCall(Request); + if (!Plan) + return std::unexpected(Plan.error()); + if (Plan->kind() != CallLoweringPlanKind::Call) { + return makeUnexpected(ErrorCode::InternalError, + "target returned the wrong call-lowering plan kind for a call"); + } + return emitPlan(Builder, *Plan); +} + +Expected TargetCallLowering::lowerReturn(MachineIRBuilder &Builder, + const ReturnLoweringRequest &Request) const { + auto Plan = planReturn(Request); + if (!Plan) + return std::unexpected(Plan.error()); + if (Plan->kind() != CallLoweringPlanKind::Return) { + return makeUnexpected(ErrorCode::InternalError, + "target returned the wrong call-lowering plan kind for a return"); + } + return emitPlan(Builder, *Plan); +} + +} // namespace rcc -- cgit v1.2.3