From 183e2354e9fdd107be420cbb185c1d239434aa48 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Tue, 4 Aug 2026 05:34:15 +0800 Subject: [MIR] Add machine instruction parser and printer Parse MachineFunction bodies in two passes and serialize the same MachineIR model in complete or readable form. Extend instruction attachments and memory operands required by the fixed LLVM MIR grammar, and cover deterministic parse-print round trips. --- backend/include/rcc/CodeGen/MachineInstr.h | 59 + backend/include/rcc/CodeGen/MachineMemOperand.h | 23 + backend/include/rcc/MIR/MIParser.h | 95 + backend/include/rcc/MIR/MIPrinter.h | 35 + backend/lib/CodeGen/MachineFunctionCloner.cpp | 39 + backend/lib/CodeGen/MachineInstr.cpp | 69 + backend/lib/CodeGen/MachineMemOperand.cpp | 55 +- backend/lib/CodeGen/MachineVerifier.cpp | 38 + backend/lib/MIR/CMakeLists.txt | 8 + backend/lib/MIR/MILexer.cpp | 42 +- backend/lib/MIR/MIParser.cpp | 3043 ++++++++++++++++++++ backend/lib/MIR/MIPrinter.cpp | 1464 ++++++++++ .../CodeGen/MachineFunctionClonerTest.cpp | 34 +- backend/unittests/MIR/CMakeLists.txt | 13 + backend/unittests/MIR/MIParserTest.cpp | 396 +++ 15 files changed, 5394 insertions(+), 19 deletions(-) create mode 100644 backend/include/rcc/MIR/MIParser.h create mode 100644 backend/include/rcc/MIR/MIPrinter.h create mode 100644 backend/lib/MIR/MIParser.cpp create mode 100644 backend/lib/MIR/MIPrinter.cpp create mode 100644 backend/unittests/MIR/MIParserTest.cpp (limited to 'backend') diff --git a/backend/include/rcc/CodeGen/MachineInstr.h b/backend/include/rcc/CodeGen/MachineInstr.h index 69d7dd7..e7294b4 100644 --- a/backend/include/rcc/CodeGen/MachineInstr.h +++ b/backend/include/rcc/CodeGen/MachineInstr.h @@ -13,6 +13,8 @@ #include #include #include +#include +#include #include #include @@ -154,6 +156,56 @@ public: DebugInstrNumber = 0; } + [[nodiscard]] std::optional preInstrSymbol() const noexcept; + [[nodiscard]] Expected setPreInstrSymbol(std::string Symbol); + void clearPreInstrSymbol() noexcept { + PreInstrSymbol.reset(); + } + + [[nodiscard]] std::optional postInstrSymbol() const noexcept; + [[nodiscard]] Expected setPostInstrSymbol(std::string Symbol); + void clearPostInstrSymbol() noexcept { + PostInstrSymbol.reset(); + } + + [[nodiscard]] const std::optional &heapAllocMarker() const noexcept { + return HeapAllocMarker; + } + [[nodiscard]] Expected setHeapAllocMarker(MachineMetadataReference Marker); + void clearHeapAllocMarker() noexcept { + HeapAllocMarker.reset(); + } + + [[nodiscard]] const std::optional &pcSections() const noexcept { + return PCSections; + } + [[nodiscard]] Expected setPCSections(MachineMetadataReference Sections); + void clearPCSections() noexcept { + PCSections.reset(); + } + + [[nodiscard]] const std::optional &mmra() const noexcept { + return MMRA; + } + [[nodiscard]] Expected setMMRA(MachineMetadataReference Metadata); + void clearMMRA() noexcept { + MMRA.reset(); + } + + [[nodiscard]] std::optional cfiType() const noexcept { + return CFIType; + } + [[nodiscard]] Expected setCFIType(std::uint64_t Type); + void clearCFIType() noexcept { + CFIType.reset(); + } + + [[nodiscard]] std::optional deactivationSymbol() const noexcept; + [[nodiscard]] Expected setDeactivationSymbol(std::string Symbol); + void clearDeactivationSymbol() noexcept { + DeactivationSymbol.reset(); + } + private: MachineInstr(MachineFunction &OwnerFunction, Opcode InstructionOpcode, MachineInstrStableID StableID); @@ -177,6 +229,13 @@ private: std::optional DebugLocation; std::optional Origin; std::uint32_t DebugInstrNumber = 0; + std::optional PreInstrSymbol; + std::optional PostInstrSymbol; + std::optional HeapAllocMarker; + std::optional PCSections; + std::optional MMRA; + std::optional CFIType; + std::optional DeactivationSymbol; friend class MachineArena; friend class MachineBasicBlock; diff --git a/backend/include/rcc/CodeGen/MachineMemOperand.h b/backend/include/rcc/CodeGen/MachineMemOperand.h index b6cb07f..a9e19a6 100644 --- a/backend/include/rcc/CodeGen/MachineMemOperand.h +++ b/backend/include/rcc/CodeGen/MachineMemOperand.h @@ -5,6 +5,7 @@ #include "rcc/CodeGen/LowLevelType.h" #include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/MachineMetadata.h" #include #include @@ -138,6 +139,14 @@ public: JumpTable, GlobalSymbol, ExternalSymbol, + IRValue, + Stack, + GOT, + ConstantPoolPseudo, + JumpTablePseudo, + CallEntryGlobal, + CallEntryExternal, + Custom, }; MemoryBase() = default; @@ -147,6 +156,14 @@ public: [[nodiscard]] static MemoryBase jumpTable(JumpTableIndex Index); [[nodiscard]] static MemoryBase globalSymbol(std::string Name); [[nodiscard]] static MemoryBase externalSymbol(std::string Name); + [[nodiscard]] static MemoryBase irValue(std::string Name); + [[nodiscard]] static MemoryBase stack(); + [[nodiscard]] static MemoryBase got(); + [[nodiscard]] static MemoryBase constantPoolPseudo(); + [[nodiscard]] static MemoryBase jumpTablePseudo(); + [[nodiscard]] static MemoryBase callEntryGlobal(std::string Name); + [[nodiscard]] static MemoryBase callEntryExternal(std::string Name); + [[nodiscard]] static MemoryBase custom(std::string Name); [[nodiscard]] Kind kind() const noexcept { return BaseKind; @@ -177,11 +194,17 @@ struct MachineMemOperandDesc final { SyncScopeID SyncScope; MemorySize Size; Alignment Align; + std::optional BaseAlign; std::uint32_t AddressSpace = 0; MemoryBase Base; std::int64_t Offset = 0; std::optional OffsetRange; std::optional AliasSource; + std::optional TBAA; + std::optional AliasScope; + std::optional NoAlias; + std::optional NoAliasAddressSpace; + std::optional RangeMetadata; std::uint16_t TargetFlags = 0; friend bool operator==(const MachineMemOperandDesc &Left, diff --git a/backend/include/rcc/MIR/MIParser.h b/backend/include/rcc/MIR/MIParser.h new file mode 100644 index 0000000..978e928 --- /dev/null +++ b/backend/include/rcc/MIR/MIParser.h @@ -0,0 +1,95 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_MIR_MIPARSER_H +#define RCC_MIR_MIPARSER_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/MachineMetadata.h" +#include "rcc/Support/Error.h" +#include "rcc/Support/TextDiagnostic.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +class MachineFunction; +class TargetDescription; + +namespace mir { + +struct MIFrameObjectSlot final { + std::uint32_t TextID = 0; + FrameIndex Index; + std::optional Name; +}; + +struct MIConstantPoolSlot final { + std::uint32_t TextID = 0; + ConstantPoolIndex Index; +}; + +struct MIJumpTableSlot final { + std::uint32_t TextID = 0; + JumpTableIndex Index; +}; + +struct MIMetadataSlot final { + std::uint32_t TextID = 0; + MachineMetadataReference Reference; +}; + +struct MISyncScopeSlot final { + std::string Name; + SyncScopeID ID; +}; + +struct MIParserContext final { + std::vector StackObjects; + std::vector FixedStackObjects; + std::vector ConstantPoolItems; + std::vector JumpTables; + std::vector Metadata; + std::vector SyncScopes; + std::uint32_t DefaultPointerSizeInBits = 0; +}; + +struct MIParserOptions final { + std::size_t MaximumTokens = std::size_t{1} << 24U; + std::size_t MaximumTokenLength = std::size_t{1} << 24U; + std::size_t MaximumBlocks = std::size_t{1} << 20U; + std::size_t MaximumInstructions = std::size_t{1} << 24U; + std::size_t MaximumOperandsPerInstruction = std::size_t{1} << 20U; + std::size_t MaximumMemoryOperandsPerInstruction = std::size_t{1} << 20U; +}; + +class MIParser final { +public: + MIParser(MachineFunction &Function, const TargetDescription &Target, std::string SourceName, + std::string SourceText, MIParserContext Context = {}, MIParserOptions Options = {}); + MIParser(const MIParser &) = delete; + MIParser &operator=(const MIParser &) = delete; + MIParser(MIParser &&) noexcept; + MIParser &operator=(MIParser &&) noexcept; + ~MIParser(); + + [[nodiscard]] Expected parse(); + + [[nodiscard]] const TextSource &source() const noexcept; + [[nodiscard]] std::span diagnostics() const noexcept; + [[nodiscard]] bool failed() const noexcept; + +private: + class Impl; + std::unique_ptr Implementation; +}; + +} // namespace mir +} // namespace rcc + +#endif // RCC_MIR_MIPARSER_H diff --git a/backend/include/rcc/MIR/MIPrinter.h b/backend/include/rcc/MIR/MIPrinter.h new file mode 100644 index 0000000..663859e --- /dev/null +++ b/backend/include/rcc/MIR/MIPrinter.h @@ -0,0 +1,35 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_MIR_MIPRINTER_H +#define RCC_MIR_MIPRINTER_H + +#include "rcc/MIR/MIParser.h" +#include "rcc/Support/Error.h" + +#include + +namespace rcc { + +class MachineFunction; +class TargetDescription; + +namespace mir { + +enum class MIPrintMode : unsigned char { + Complete, + Readable, +}; + +struct MIPrinterOptions final { + MIPrintMode Mode = MIPrintMode::Complete; +}; + +[[nodiscard]] Expected printMachineFunctionBody(const MachineFunction &Function, + const TargetDescription &Target, + const MIParserContext &Context = {}, + MIPrinterOptions Options = {}); + +} // namespace mir +} // namespace rcc + +#endif // RCC_MIR_MIPRINTER_H diff --git a/backend/lib/CodeGen/MachineFunctionCloner.cpp b/backend/lib/CodeGen/MachineFunctionCloner.cpp index 7dcf5e2..9342c5a 100644 --- a/backend/lib/CodeGen/MachineFunctionCloner.cpp +++ b/backend/lib/CodeGen/MachineFunctionCloner.cpp @@ -414,6 +414,45 @@ cloneMemOperand(const MachineMemOperand &SourceOperand, CloneState &State) { if (!DebugNumberResult) return std::unexpected(DebugNumberResult.error()); } + if (SourceInstruction->preInstrSymbol()) { + auto SymbolResult = + NewInstruction->setPreInstrSymbol(std::string(*SourceInstruction->preInstrSymbol())); + if (!SymbolResult) + return std::unexpected(SymbolResult.error()); + } + if (SourceInstruction->postInstrSymbol()) { + auto SymbolResult = + NewInstruction->setPostInstrSymbol(std::string(*SourceInstruction->postInstrSymbol())); + if (!SymbolResult) + return std::unexpected(SymbolResult.error()); + } + if (SourceInstruction->heapAllocMarker()) { + auto MarkerResult = + NewInstruction->setHeapAllocMarker(*SourceInstruction->heapAllocMarker()); + if (!MarkerResult) + return std::unexpected(MarkerResult.error()); + } + if (SourceInstruction->pcSections()) { + auto SectionsResult = NewInstruction->setPCSections(*SourceInstruction->pcSections()); + if (!SectionsResult) + return std::unexpected(SectionsResult.error()); + } + if (SourceInstruction->mmra()) { + auto MMRAResult = NewInstruction->setMMRA(*SourceInstruction->mmra()); + if (!MMRAResult) + return std::unexpected(MMRAResult.error()); + } + if (SourceInstruction->cfiType()) { + auto TypeResult = NewInstruction->setCFIType(*SourceInstruction->cfiType()); + if (!TypeResult) + return std::unexpected(TypeResult.error()); + } + if (SourceInstruction->deactivationSymbol()) { + auto SymbolResult = NewInstruction->setDeactivationSymbol( + std::string(*SourceInstruction->deactivationSymbol())); + if (!SymbolResult) + return std::unexpected(SymbolResult.error()); + } auto AppendResult = DestinationBlock->appendInstruction(*NewInstruction); if (!AppendResult) diff --git a/backend/lib/CodeGen/MachineInstr.cpp b/backend/lib/CodeGen/MachineInstr.cpp index a8fe9b5..7597651 100644 --- a/backend/lib/CodeGen/MachineInstr.cpp +++ b/backend/lib/CodeGen/MachineInstr.cpp @@ -12,6 +12,8 @@ #include #include #include +#include +#include #include namespace rcc { @@ -157,6 +159,73 @@ Expected MachineInstr::setDebugLocation(MachineDebugLocation NewLocation) return {}; } +std::optional MachineInstr::preInstrSymbol() const noexcept { + if (!PreInstrSymbol) + return std::nullopt; + return *PreInstrSymbol; +} + +Expected MachineInstr::setPreInstrSymbol(std::string Symbol) { + if (Symbol.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "pre-instruction symbol cannot be empty"); + PreInstrSymbol = std::move(Symbol); + return {}; +} + +std::optional MachineInstr::postInstrSymbol() const noexcept { + if (!PostInstrSymbol) + return std::nullopt; + return *PostInstrSymbol; +} + +Expected MachineInstr::setPostInstrSymbol(std::string Symbol) { + if (Symbol.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "post-instruction symbol cannot be empty"); + PostInstrSymbol = std::move(Symbol); + return {}; +} + +Expected MachineInstr::setHeapAllocMarker(MachineMetadataReference Marker) { + if (!Marker.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "heap-allocation marker must be valid"); + HeapAllocMarker = Marker; + return {}; +} + +Expected MachineInstr::setPCSections(MachineMetadataReference Sections) { + if (!Sections.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "PC sections metadata must be valid"); + PCSections = Sections; + return {}; +} + +Expected MachineInstr::setMMRA(MachineMetadataReference Metadata) { + if (!Metadata.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "MMRA metadata must be valid"); + MMRA = Metadata; + return {}; +} + +Expected MachineInstr::setCFIType(std::uint64_t Type) { + if (Type == 0 || Type > std::numeric_limits::max()) + return makeUnexpected(ErrorCode::InvalidArgument, "CFI type must fit in nonzero uint32"); + CFIType = static_cast(Type); + return {}; +} + +std::optional MachineInstr::deactivationSymbol() const noexcept { + if (!DeactivationSymbol) + return std::nullopt; + return *DeactivationSymbol; +} + +Expected MachineInstr::setDeactivationSymbol(std::string Symbol) { + if (Symbol.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "deactivation symbol cannot be empty"); + DeactivationSymbol = std::move(Symbol); + return {}; +} + Expected MachineInstr::addMemOperand(const MachineMemOperand &MemOperand) { if (!OwnerFunction->ownsMemOperand(MemOperand)) { return makeUnexpected(ErrorCode::InvalidArgument, diff --git a/backend/lib/CodeGen/MachineMemOperand.cpp b/backend/lib/CodeGen/MachineMemOperand.cpp index 451dbdb..95e7237 100644 --- a/backend/lib/CodeGen/MachineMemOperand.cpp +++ b/backend/lib/CodeGen/MachineMemOperand.cpp @@ -2,6 +2,9 @@ #include "rcc/CodeGen/MachineMemOperand.h" +#include +#include +#include #include namespace rcc { @@ -160,6 +163,38 @@ MemoryBase MemoryBase::externalSymbol(std::string Name) { return MemoryBase(Kind::ExternalSymbol, std::move(Name)); } +MemoryBase MemoryBase::irValue(std::string Name) { + return MemoryBase(Kind::IRValue, std::move(Name)); +} + +MemoryBase MemoryBase::stack() { + return MemoryBase(Kind::Stack, std::monostate{}); +} + +MemoryBase MemoryBase::got() { + return MemoryBase(Kind::GOT, std::monostate{}); +} + +MemoryBase MemoryBase::constantPoolPseudo() { + return MemoryBase(Kind::ConstantPoolPseudo, std::monostate{}); +} + +MemoryBase MemoryBase::jumpTablePseudo() { + return MemoryBase(Kind::JumpTablePseudo, std::monostate{}); +} + +MemoryBase MemoryBase::callEntryGlobal(std::string Name) { + return MemoryBase(Kind::CallEntryGlobal, std::move(Name)); +} + +MemoryBase MemoryBase::callEntryExternal(std::string Name) { + return MemoryBase(Kind::CallEntryExternal, std::move(Name)); +} + +MemoryBase MemoryBase::custom(std::string Name) { + return MemoryBase(Kind::Custom, std::move(Name)); +} + std::optional MemoryBase::frameIndex() const noexcept { if (BaseKind != Kind::FrameIndex) return std::nullopt; @@ -179,8 +214,11 @@ std::optional MemoryBase::jumpTableIndex() const noexcept { } std::optional MemoryBase::symbolName() const noexcept { - if (BaseKind != Kind::GlobalSymbol && BaseKind != Kind::ExternalSymbol) + if (BaseKind != Kind::GlobalSymbol && BaseKind != Kind::ExternalSymbol && + BaseKind != Kind::IRValue && BaseKind != Kind::CallEntryGlobal && + BaseKind != Kind::CallEntryExternal && BaseKind != Kind::Custom) { return std::nullopt; + } return std::get(Value); } @@ -195,6 +233,10 @@ Expected MachineMemOperand::create(MachineMemOperandDesc Desc return makeUnexpected(ErrorCode::InvalidArgument, "machine memory operand address space must fit in 24 bits"); } + if (Description.BaseAlign && Description.BaseAlign->bytes() < Description.Align.bytes()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine memory operand base alignment cannot be smaller than alignment"); + } if (Description.Accesses.has(MemoryAccessFlag::Invariant) && (!IsLoad || IsStore)) { return makeUnexpected(ErrorCode::InvalidArgument, "invariant memory operands must be load-only"); @@ -208,6 +250,17 @@ Expected MachineMemOperand::create(MachineMemOperandDesc Desc if (SymbolName && SymbolName->empty()) { return makeUnexpected(ErrorCode::InvalidArgument, "memory base symbol name cannot be empty"); } + const std::array MetadataReferences{ + Description.TBAA, Description.AliasScope, + Description.NoAlias, Description.NoAliasAddressSpace, + Description.RangeMetadata, + }; + if (std::ranges::any_of(MetadataReferences, [](const auto &Reference) { + return Reference.has_value() && !Reference->isValid(); + })) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine memory operand contains an invalid metadata reference"); + } return MachineMemOperand(std::move(Description)); } diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp index fd027fe..3ebe683 100644 --- a/backend/lib/CodeGen/MachineVerifier.cpp +++ b/backend/lib/CodeGen/MachineVerifier.cpp @@ -12,11 +12,13 @@ #include "rcc/CodeGen/MachineRegisterInfo.h" #include +#include #include #include #include #include #include +#include #include #include #include @@ -306,6 +308,29 @@ private: if (!DebugLocationResult) return failWith("instruction debug location", DebugLocationResult.error()); } + const auto VerifyAttachment = [this](const std::optional &Reference, + std::string_view Name) -> Expected { + if (!Reference) + return {}; + auto Verification = verifyMachineMetadataReference(*Reference, Function.metadata()); + if (!Verification) + return failWith(Name, Verification.error()); + return {}; + }; + if (auto Verification = + VerifyAttachment(Instruction.heapAllocMarker(), "instruction heap-allocation marker"); + !Verification) { + return Verification; + } + if (auto Verification = + VerifyAttachment(Instruction.pcSections(), "instruction PC sections metadata"); + !Verification) { + return Verification; + } + if (auto Verification = VerifyAttachment(Instruction.mmra(), "instruction MMRA metadata"); + !Verification) { + return Verification; + } if (Instruction.origin() && Instruction.origin()->value() == 0) return fail("instruction has an invalid origin ID"); @@ -364,6 +389,19 @@ private: if (MemOperand == nullptr || !RegisteredMemOperands.contains(MemOperand)) { return fail("instruction references a foreign or null MMO"); } + const MachineMemOperandDesc &Description = MemOperand->description(); + const std::array MetadataReferences{ + Description.TBAA, Description.AliasScope, + Description.NoAlias, Description.NoAliasAddressSpace, + Description.RangeMetadata, + }; + for (const auto &Reference : MetadataReferences) { + if (!Reference) + continue; + auto Verification = verifyMachineMetadataReference(*Reference, Function.metadata()); + if (!Verification) + return failWith("machine memory operand metadata", Verification.error()); + } } return {}; } diff --git a/backend/lib/MIR/CMakeLists.txt b/backend/lib/MIR/CMakeLists.txt index ca213aa..7f66685 100644 --- a/backend/lib/MIR/CMakeLists.txt +++ b/backend/lib/MIR/CMakeLists.txt @@ -4,11 +4,15 @@ set( RCCBackendMIRSources EmbeddedIR.cpp MILexer.cpp + MIParser.cpp + MIPrinter.cpp ) set( RCCBackendMIRHeaders "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/EmbeddedIR.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/MILexer.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/MIParser.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/MIPrinter.h" ) add_library(RCCBackendMIR ${RCCBackendMIRSources}) @@ -42,9 +46,13 @@ install( rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIR.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MILexer.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MIParser.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MIPrinter.cpp" ${RCCBackendMIRHeaders} ) rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIR.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MILexer.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MIParser.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MIPrinter.cpp" ) diff --git a/backend/lib/MIR/MILexer.cpp b/backend/lib/MIR/MILexer.cpp index 816264e..f568cef 100644 --- a/backend/lib/MIR/MILexer.cpp +++ b/backend/lib/MIR/MILexer.cpp @@ -569,14 +569,25 @@ private: ++Offset; const std::string_view Number = slice(NumberBegin, Offset); - std::size_t NameBegin = Offset; - if (peek() == '.') { - ++Offset; - NameBegin = Offset; - while (!atEnd() && isIdentifierCharacter(peek())) - ++Offset; + if (peek() != '.') { + return stringToken(IsReference ? MITokenKind::MachineBasicBlock + : MITokenKind::MachineBasicBlockLabel, + Begin, Offset, {}, Number); } + ++Offset; + const std::size_t NameBegin = Offset; + if (peek() == '"') { + auto Quoted = scanQuotedString(Offset); + if (!Quoted) + return token(MITokenKind::Error, Begin, Offset); + Offset = Quoted->End; + return ownedStringToken(IsReference ? MITokenKind::MachineBasicBlock + : MITokenKind::MachineBasicBlockLabel, + Begin, Offset, std::move(Quoted->Value), Number); + } + while (!atEnd() && isIdentifierCharacter(peek())) + ++Offset; return stringToken(IsReference ? MITokenKind::MachineBasicBlock : MITokenKind::MachineBasicBlockLabel, Begin, Offset, slice(NameBegin, Offset), Number); @@ -597,13 +608,20 @@ private: if (!HasOptionalName) return token(Kind, Begin, Offset, Number); - std::size_t NameBegin = Offset; - if (peek() == '.') { - ++Offset; - NameBegin = Offset; - while (!atEnd() && isIdentifierCharacter(peek())) - ++Offset; + if (peek() != '.') + return stringToken(Kind, Begin, Offset, {}, Number); + + ++Offset; + const std::size_t NameBegin = Offset; + if (peek() == '"') { + auto Quoted = scanQuotedString(Offset); + if (!Quoted) + return token(MITokenKind::Error, Begin, Offset); + Offset = Quoted->End; + return ownedStringToken(Kind, Begin, Offset, std::move(Quoted->Value), Number); } + while (!atEnd() && isIdentifierCharacter(peek())) + ++Offset; return stringToken(Kind, Begin, Offset, slice(NameBegin, Offset), Number); } diff --git a/backend/lib/MIR/MIParser.cpp b/backend/lib/MIR/MIParser.cpp new file mode 100644 index 0000000..b632415 --- /dev/null +++ b/backend/lib/MIR/MIParser.cpp @@ -0,0 +1,3043 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/MIR/MIParser.h" + +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetMIRTextInfo.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" +#include "rcc/MIR/MILexer.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc::mir { +namespace { + +[[nodiscard]] bool parseUnsignedDecimal(std::string_view Spelling, std::uint64_t &Value) { + if (Spelling.empty() || Spelling.front() == '-') + return false; + const char *Begin = Spelling.data(); + const char *End = Begin + Spelling.size(); + const auto Result = std::from_chars(Begin, End, Value, 10); + return Result.ec == std::errc{} && Result.ptr == End; +} + +[[nodiscard]] bool parseSignedDecimal(std::string_view Spelling, std::int64_t &Value) { + if (Spelling.empty()) + return false; + const char *Begin = Spelling.data(); + const char *End = Begin + Spelling.size(); + const auto Result = std::from_chars(Begin, End, Value, 10); + return Result.ec == std::errc{} && Result.ptr == End; +} + +[[nodiscard]] bool parseHexadecimal(std::string_view Spelling, std::uint64_t &Value) { + if (Spelling.size() < 3 || Spelling[0] != '0' || (Spelling[1] != 'x' && Spelling[1] != 'X')) + return false; + const char *Begin = Spelling.data() + 2; + const char *End = Spelling.data() + Spelling.size(); + const auto Result = std::from_chars(Begin, End, Value, 16); + return Result.ec == std::errc{} && Result.ptr == End; +} + +[[nodiscard]] bool parseUnsignedDigits(std::string_view Spelling, std::uint64_t &Value) { + if (Spelling.empty()) + return false; + const char *Begin = Spelling.data(); + const char *End = Begin + Spelling.size(); + const auto Result = std::from_chars(Begin, End, Value, 10); + return Result.ec == std::errc{} && Result.ptr == End; +} + +[[nodiscard]] std::optional floatSemanticsForKeyword(std::string_view Keyword) { + if (Keyword == "half") + return FloatSemantics::IEEEHalf; + if (Keyword == "bfloat") + return FloatSemantics::BFloat; + if (Keyword == "float") + return FloatSemantics::IEEESingle; + if (Keyword == "double") + return FloatSemantics::IEEEDouble; + if (Keyword == "x86_fp80") + return FloatSemantics::X87DoubleExtended; + if (Keyword == "fp128") + return FloatSemantics::IEEEQuad; + if (Keyword == "ppc_fp128") + return FloatSemantics::PPCDoubleDouble; + return std::nullopt; +} + +[[nodiscard]] bool isFloatingSemanticsKeyword(const MIToken &Token) { + return Token.kind() == MITokenKind::Keyword && + floatSemanticsForKeyword(Token.stringValue()).has_value(); +} + +[[nodiscard]] bool isCFIOperationToken(const MIToken &Token) { + return Token.isKeyword("same_value") || Token.isKeyword("remember_state") || + Token.isKeyword("restore_state") || Token.isKeyword("offset") || + Token.isKeyword("llvm_def_aspace_cfa") || Token.isKeyword("def_cfa_register") || + Token.isKeyword("def_cfa_offset") || Token.isKeyword("def_cfa") || + Token.isKeyword("rel_offset") || Token.isKeyword("adjust_cfa_offset") || + Token.isKeyword("escape") || Token.isKeyword("restore") || Token.isKeyword("undefined") || + Token.isKeyword("register") || Token.isKeyword("window_save") || + Token.isKeyword("negate_ra_sign_state") || + Token.isKeyword("negate_ra_sign_state_with_pc") || Token.isKeyword("llvm_register_pair") || + Token.isKeyword("llvm_vector_registers") || Token.isKeyword("llvm_vector_offset") || + Token.isKeyword("llvm_vector_register_mask"); +} + +[[nodiscard]] std::optional hexDigit(char Character) noexcept { + if (Character >= '0' && Character <= '9') + return static_cast(Character - '0'); + if (Character >= 'a' && Character <= 'f') + return static_cast(Character - 'a') + 10U; + if (Character >= 'A' && Character <= 'F') + return static_cast(Character - 'A') + 10U; + return std::nullopt; +} + +[[nodiscard]] bool parseHexWords(std::string_view Digits, std::uint32_t BitWidth, + std::vector &Words) { + if (Digits.empty() || Digits.size() > (static_cast(BitWidth) + 3U) / 4U) + return false; + Words.assign((static_cast(BitWidth) + 63U) / 64U, 0); + std::size_t BitOffset = 0; + for (auto Iterator = Digits.rbegin(); Iterator != Digits.rend(); ++Iterator) { + const auto Digit = hexDigit(*Iterator); + if (!Digit) + return false; + const std::size_t WordIndex = BitOffset / 64U; + const unsigned Shift = static_cast(BitOffset % 64U); + Words[WordIndex] |= static_cast(*Digit) << Shift; + BitOffset += 4U; + } + if (BitWidth % 64U != 0) + Words.back() &= (std::uint64_t{1} << (BitWidth % 64U)) - 1U; + return true; +} + +[[nodiscard]] bool isZeroWords(std::span Words) noexcept { + return std::ranges::all_of(Words, [](std::uint64_t Word) { return Word == 0; }); +} + +[[nodiscard]] bool magnitudeFitsSignedNegative(std::span Words, + std::uint32_t BitWidth) noexcept { + const std::size_t SignWord = (BitWidth - 1U) / 64U; + const unsigned SignBit = (BitWidth - 1U) % 64U; + for (std::size_t Index = SignWord + 1U; Index < Words.size(); ++Index) { + if (Words[Index] != 0) + return false; + } + const std::uint64_t SignMask = std::uint64_t{1} << SignBit; + if ((Words[SignWord] & ~SignMask) != 0) + return false; + if ((Words[SignWord] & SignMask) == 0) + return true; + for (std::size_t Index = 0; Index < SignWord; ++Index) { + if (Words[Index] != 0) + return false; + } + return true; +} + +[[nodiscard]] Expected parseIntegerImmediateValue(std::uint32_t BitWidth, + std::string_view Spelling) { + if (BitWidth == 0 || BitWidth > IntegerImmediate::MaxBitWidth) + return makeUnexpected(ErrorCode::ParseError, "typed integer width is out of range"); + + const bool Negative = Spelling.starts_with('-'); + if (Negative) + Spelling.remove_prefix(1); + if (Spelling.empty()) + return makeUnexpected(ErrorCode::ParseError, "typed integer has no digits"); + + std::vector Words((static_cast(BitWidth) + 63U) / 64U, 0); + for (char Character : Spelling) { + if (Character < '0' || Character > '9') + return makeUnexpected(ErrorCode::ParseError, "typed integer contains a non-decimal digit"); + std::uint64_t Carry = static_cast(Character - '0'); + for (std::uint64_t &Word : Words) { + const unsigned __int128 Product = static_cast(Word) * 10U + Carry; + Word = static_cast(Product); + Carry = static_cast(Product >> 64U); + } + if (Carry != 0) + return makeUnexpected(ErrorCode::ParseError, "typed integer does not fit its bit width"); + if (BitWidth % 64U != 0 && (Words.back() >> (BitWidth % 64U)) != 0) { + return makeUnexpected(ErrorCode::ParseError, "typed integer does not fit its bit width"); + } + } + + if (Negative) { + if (isZeroWords(Words) || !magnitudeFitsSignedNegative(Words, BitWidth)) + return makeUnexpected(ErrorCode::ParseError, + "negative typed integer does not fit its bit width"); + for (std::uint64_t &Word : Words) + Word = ~Word; + std::uint64_t Carry = 1; + for (std::uint64_t &Word : Words) { + const std::uint64_t Previous = Word; + Word += Carry; + Carry = Carry != 0 && Word < Previous ? 1 : 0; + } + if (BitWidth % 64U != 0) + Words.back() &= (std::uint64_t{1} << (BitWidth % 64U)) - 1U; + } + return IntegerImmediate::create(BitWidth, Words); +} + +[[nodiscard]] std::uint16_t floatToHalfBits(float Value) noexcept { + const std::uint32_t Bits = std::bit_cast(Value); + const std::uint32_t Sign = (Bits >> 16U) & 0x8000U; + const std::uint32_t Exponent = (Bits >> 23U) & 0xFFU; + const std::uint32_t Fraction = Bits & 0x7FFFFFU; + if (Exponent == 0xFFU) { + const std::uint32_t Payload = Fraction == 0 ? 0 : std::max(1U, Fraction >> 13U); + return static_cast(Sign | 0x7C00U | Payload); + } + + const int HalfExponent = static_cast(Exponent) - 127 + 15; + if (HalfExponent >= 31) + return static_cast(Sign | 0x7C00U); + if (HalfExponent <= 0) { + if (HalfExponent < -10) + return static_cast(Sign); + const std::uint32_t Mantissa = Fraction | 0x800000U; + const unsigned Shift = static_cast(14 - HalfExponent); + std::uint32_t Rounded = Mantissa >> Shift; + const std::uint32_t Remainder = Mantissa & ((std::uint32_t{1} << Shift) - 1U); + const std::uint32_t Halfway = std::uint32_t{1} << (Shift - 1U); + if (Remainder > Halfway || (Remainder == Halfway && (Rounded & 1U) != 0)) + ++Rounded; + return static_cast(Sign | Rounded); + } + + std::uint32_t Rounded = Fraction >> 13U; + const std::uint32_t Remainder = Fraction & 0x1FFFU; + if (Remainder > 0x1000U || (Remainder == 0x1000U && (Rounded & 1U) != 0)) { + ++Rounded; + if (Rounded == 0x400U) + return static_cast(Sign | + (static_cast(HalfExponent + 1) << 10U)); + } + return static_cast(Sign | (static_cast(HalfExponent) << 10U) | + Rounded); +} + +[[nodiscard]] std::uint16_t floatToBFloatBits(float Value) noexcept { + std::uint32_t Bits = std::bit_cast(Value); + const std::uint32_t Bias = 0x7FFFU + ((Bits >> 16U) & 1U); + Bits += Bias; + return static_cast(Bits >> 16U); +} + +[[nodiscard]] std::optional debugExpressionOpcode(std::string_view Name) noexcept { + if (Name.starts_with("DW_OP_lit")) { + std::uint64_t Index = 0; + if (parseUnsignedDigits(Name.substr(9), Index) && Index <= 31) + return 0x30U + Index; + } + if (Name.starts_with("DW_OP_reg")) { + std::uint64_t Index = 0; + if (parseUnsignedDigits(Name.substr(9), Index) && Index <= 31) + return 0x50U + Index; + } + if (Name.starts_with("DW_OP_breg")) { + std::uint64_t Index = 0; + if (parseUnsignedDigits(Name.substr(10), Index) && Index <= 31) + return 0x70U + Index; + } + + constexpr auto NamedOpcodes = std::to_array>({ + {"DW_OP_addr", 0x03}, + {"DW_OP_deref", 0x06}, + {"DW_OP_const1u", 0x08}, + {"DW_OP_const1s", 0x09}, + {"DW_OP_const2u", 0x0A}, + {"DW_OP_const2s", 0x0B}, + {"DW_OP_const4u", 0x0C}, + {"DW_OP_const4s", 0x0D}, + {"DW_OP_const8u", 0x0E}, + {"DW_OP_const8s", 0x0F}, + {"DW_OP_constu", 0x10}, + {"DW_OP_consts", 0x11}, + {"DW_OP_dup", 0x12}, + {"DW_OP_drop", 0x13}, + {"DW_OP_over", 0x14}, + {"DW_OP_pick", 0x15}, + {"DW_OP_swap", 0x16}, + {"DW_OP_rot", 0x17}, + {"DW_OP_xderef", 0x18}, + {"DW_OP_abs", 0x19}, + {"DW_OP_and", 0x1A}, + {"DW_OP_div", 0x1B}, + {"DW_OP_minus", 0x1C}, + {"DW_OP_mod", 0x1D}, + {"DW_OP_mul", 0x1E}, + {"DW_OP_neg", 0x1F}, + {"DW_OP_not", 0x20}, + {"DW_OP_or", 0x21}, + {"DW_OP_plus", 0x22}, + {"DW_OP_plus_uconst", 0x23}, + {"DW_OP_shl", 0x24}, + {"DW_OP_shr", 0x25}, + {"DW_OP_shra", 0x26}, + {"DW_OP_xor", 0x27}, + {"DW_OP_bra", 0x28}, + {"DW_OP_eq", 0x29}, + {"DW_OP_ge", 0x2A}, + {"DW_OP_gt", 0x2B}, + {"DW_OP_le", 0x2C}, + {"DW_OP_lt", 0x2D}, + {"DW_OP_ne", 0x2E}, + {"DW_OP_skip", 0x2F}, + {"DW_OP_regx", 0x90}, + {"DW_OP_fbreg", 0x91}, + {"DW_OP_bregx", 0x92}, + {"DW_OP_piece", 0x93}, + {"DW_OP_deref_size", 0x94}, + {"DW_OP_xderef_size", 0x95}, + {"DW_OP_nop", 0x96}, + {"DW_OP_push_object_address", 0x97}, + {"DW_OP_call2", 0x98}, + {"DW_OP_call4", 0x99}, + {"DW_OP_call_ref", 0x9A}, + {"DW_OP_form_tls_address", 0x9B}, + {"DW_OP_call_frame_cfa", 0x9C}, + {"DW_OP_bit_piece", 0x9D}, + {"DW_OP_implicit_value", 0x9E}, + {"DW_OP_stack_value", 0x9F}, + {"DW_OP_implicit_pointer", 0xA0}, + {"DW_OP_addrx", 0xA1}, + {"DW_OP_constx", 0xA2}, + {"DW_OP_entry_value", 0xA3}, + {"DW_OP_const_type", 0xA4}, + {"DW_OP_regval_type", 0xA5}, + {"DW_OP_deref_type", 0xA6}, + {"DW_OP_xderef_type", 0xA7}, + {"DW_OP_convert", 0xA8}, + {"DW_OP_reinterpret", 0xA9}, + {"DW_OP_LLVM_fragment", 0x1000}, + {"DW_OP_LLVM_convert", 0x1001}, + {"DW_OP_LLVM_tag_offset", 0x1002}, + {"DW_OP_LLVM_entry_value", 0x1003}, + {"DW_OP_LLVM_implicit_pointer", 0x1004}, + {"DW_OP_LLVM_arg", 0x1005}, + }); + const auto *const Found = + std::ranges::find_if(NamedOpcodes, [Name](const auto &Entry) { return Entry.first == Name; }); + if (Found == NamedOpcodes.end()) + return std::nullopt; + return Found->second; +} + +[[nodiscard]] std::optional minimumTypeSizeInBits(LLT Type) noexcept { + if (!Type.isValid() || Type.isToken()) + return std::nullopt; + const std::uint64_t ScalarSize = Type.scalarBitWidth(); + if (!Type.isVector()) + return ScalarSize; + const std::uint64_t ElementCount = Type.minimumElementCount(); + if (ScalarSize != 0 && ElementCount > std::numeric_limits::max() / ScalarSize) + return std::nullopt; + return ScalarSize * ElementCount; +} + +[[nodiscard]] std::optional atomicOrdering(std::string_view Name) noexcept { + if (Name == "unordered") + return AtomicOrdering::Unordered; + if (Name == "monotonic") + return AtomicOrdering::Monotonic; + if (Name == "acquire") + return AtomicOrdering::Acquire; + if (Name == "release") + return AtomicOrdering::Release; + if (Name == "acq_rel") + return AtomicOrdering::AcquireRelease; + if (Name == "seq_cst") + return AtomicOrdering::SequentiallyConsistent; + return std::nullopt; +} + +[[nodiscard]] bool isInstructionFlag(const MIToken &Token) { + return Token.isKeyword("frame-setup") || Token.isKeyword("frame-destroy") || + Token.isKeyword("nnan") || Token.isKeyword("ninf") || Token.isKeyword("nsz") || + Token.isKeyword("arcp") || Token.isKeyword("contract") || Token.isKeyword("afn") || + Token.isKeyword("reassoc") || Token.isKeyword("nuw") || Token.isKeyword("nsw") || + Token.isKeyword("nusw") || Token.isKeyword("exact") || Token.isKeyword("nofpexcept") || + Token.isKeyword("unpredictable") || Token.isKeyword("noconvergent") || + Token.isKeyword("nneg") || Token.isKeyword("disjoint") || Token.isKeyword("samesign") || + Token.isKeyword("inbounds"); +} + +[[nodiscard]] std::optional instructionFlag(std::string_view Name) { + if (Name == "frame-setup") + return MachineInstrFlag::FrameSetup; + if (Name == "frame-destroy") + return MachineInstrFlag::FrameDestroy; + if (Name == "nnan") + return MachineInstrFlag::FastMathNoNaNs; + if (Name == "ninf") + return MachineInstrFlag::FastMathNoInfs; + if (Name == "nsz") + return MachineInstrFlag::FastMathNoSignedZeros; + if (Name == "arcp") + return MachineInstrFlag::FastMathAllowReciprocal; + if (Name == "contract") + return MachineInstrFlag::FastMathAllowContract; + if (Name == "afn") + return MachineInstrFlag::FastMathApproxFunc; + if (Name == "reassoc") + return MachineInstrFlag::FastMathAllowReassoc; + if (Name == "nuw") + return MachineInstrFlag::NoUnsignedWrap; + if (Name == "nsw") + return MachineInstrFlag::NoSignedWrap; + if (Name == "nusw") + return MachineInstrFlag::NoUSWrap; + if (Name == "exact") + return MachineInstrFlag::Exact; + if (Name == "nofpexcept") + return MachineInstrFlag::NoFPExcept; + if (Name == "unpredictable") + return MachineInstrFlag::Unpredictable; + if (Name == "noconvergent") + return MachineInstrFlag::NoConvergent; + if (Name == "nneg") + return MachineInstrFlag::NonNeg; + if (Name == "disjoint") + return MachineInstrFlag::Disjoint; + if (Name == "samesign") + return MachineInstrFlag::SameSign; + if (Name == "inbounds") + return MachineInstrFlag::InBounds; + return std::nullopt; +} + +[[nodiscard]] std::optional integerPredicate(std::string_view Name) { + if (Name == "eq") + return IntegerPredicate::Equal; + if (Name == "ne") + return IntegerPredicate::NotEqual; + if (Name == "sgt") + return IntegerPredicate::SignedGreaterThan; + if (Name == "sge") + return IntegerPredicate::SignedGreaterEqual; + if (Name == "slt") + return IntegerPredicate::SignedLessThan; + if (Name == "sle") + return IntegerPredicate::SignedLessEqual; + if (Name == "ugt") + return IntegerPredicate::UnsignedGreaterThan; + if (Name == "uge") + return IntegerPredicate::UnsignedGreaterEqual; + if (Name == "ult") + return IntegerPredicate::UnsignedLessThan; + if (Name == "ule") + return IntegerPredicate::UnsignedLessEqual; + return std::nullopt; +} + +[[nodiscard]] std::optional floatingPredicate(std::string_view Name) { + if (Name == "false") + return FloatingPredicate::AlwaysFalse; + if (Name == "oeq") + return FloatingPredicate::OrderedEqual; + if (Name == "ogt") + return FloatingPredicate::OrderedGreaterThan; + if (Name == "oge") + return FloatingPredicate::OrderedGreaterEqual; + if (Name == "olt") + return FloatingPredicate::OrderedLessThan; + if (Name == "ole") + return FloatingPredicate::OrderedLessEqual; + if (Name == "one") + return FloatingPredicate::OrderedNotEqual; + if (Name == "ord") + return FloatingPredicate::Ordered; + if (Name == "uno") + return FloatingPredicate::Unordered; + if (Name == "ueq") + return FloatingPredicate::UnorderedEqual; + if (Name == "ugt") + return FloatingPredicate::UnorderedGreaterThan; + if (Name == "uge") + return FloatingPredicate::UnorderedGreaterEqual; + if (Name == "ult") + return FloatingPredicate::UnorderedLessThan; + if (Name == "ule") + return FloatingPredicate::UnorderedLessEqual; + if (Name == "une") + return FloatingPredicate::UnorderedNotEqual; + if (Name == "true") + return FloatingPredicate::AlwaysTrue; + return std::nullopt; +} + +} // namespace + +class MIParser::Impl final { +public: + Impl(MachineFunction &Function, const TargetDescription &Target, std::string SourceName, + std::string SourceText, MIParserContext Context, MIParserOptions Options) + : Function(Function), Target(Target), + Lexer(std::move(SourceName), std::move(SourceText), + MILexerOptions{.MaximumTokenLength = Options.MaximumTokenLength, + .MaximumTokens = Options.MaximumTokens}), + Context(std::move(Context)), Options(Options) {} + + [[nodiscard]] Expected parse(); + + [[nodiscard]] const TextSource &source() const noexcept { + return Lexer.source(); + } + + [[nodiscard]] std::span diagnostics() const noexcept { + return Diagnostics; + } + + [[nodiscard]] bool failed() const noexcept { + return !Diagnostics.empty(); + } + +private: + struct ParsedOperand final { + MachineOperand Operand; + std::optional TiedDef; + TextRange Range; + }; + + [[nodiscard]] const MIToken &token() const noexcept { + return Tokens[Position]; + } + + [[nodiscard]] bool at(MITokenKind Kind) const noexcept { + return token().is(Kind); + } + + [[nodiscard]] bool nextIs(MITokenKind Kind) const noexcept { + return Position + 1U < Tokens.size() && Tokens[Position + 1U].is(Kind); + } + + [[nodiscard]] bool atKeyword(std::string_view Keyword) const noexcept { + return token().isKeyword(Keyword); + } + + void advance() noexcept { + if (!at(MITokenKind::EndOfFile)) + ++Position; + } + + [[nodiscard]] bool consume(MITokenKind Kind) noexcept { + if (!at(Kind)) + return false; + advance(); + return true; + } + + [[nodiscard]] bool expect(MITokenKind Kind, std::string_view Description); + [[nodiscard]] bool fail(const MIToken &At, std::string Message); + [[nodiscard]] bool fail(std::string Message) { + return fail(token(), std::move(Message)); + } + [[nodiscard]] Expected failureResult() const; + [[nodiscard]] bool importError(const MIToken &At, const Error &Failure); + [[nodiscard]] bool tokenize(); + + [[nodiscard]] bool parseUnsigned(const MIToken &Token, std::uint64_t &Value); + [[nodiscard]] bool parseUnsigned32(const MIToken &Token, std::uint32_t &Value); + [[nodiscard]] bool parseSigned64(const MIToken &Token, std::int64_t &Value); + [[nodiscard]] bool parseOptionalOffset(std::int64_t &Offset); + [[nodiscard]] bool parseAlignment(Alignment &Result); + [[nodiscard]] bool parseLowLevelType(LLT &Result); + [[nodiscard]] bool parseScalarLowLevelType(const MIToken &Token, LLT &Result); + + [[nodiscard]] bool parseFirstPass(); + [[nodiscard]] bool parseSecondPass(); + [[nodiscard]] bool parseBlockDefinition(bool Create, std::uint32_t &ID); + [[nodiscard]] bool parseBlockAttributes(MachineBasicBlock *Block); + [[nodiscard]] bool parseBlockLiveIns(MachineBasicBlock &Block); + [[nodiscard]] bool parseBlockSuccessors(MachineBasicBlock &Block); + [[nodiscard]] bool parseInstruction(MachineBasicBlock &Block, bool InBundle, + MachineInstr *PreviousInstruction, MachineInstr *&Result); + [[nodiscard]] bool inferSuccessors(); + + [[nodiscard]] bool parseRegister(Register &Result); + [[nodiscard]] bool parseRegisterOperand(bool IsDef, ParsedOperand &Result); + [[nodiscard]] bool parseTargetFlags(std::uint32_t &Flags); + [[nodiscard]] bool parseOperand(bool IsDef, ParsedOperand &Result); + [[nodiscard]] bool parseTypedIntegerOperand(ParsedOperand &Result); + [[nodiscard]] bool parseFloatingImmediateOperand(ParsedOperand &Result); + [[nodiscard]] bool parseMetadataReference(MachineMetadataReference &Result); + [[nodiscard]] bool parseMetadataOperand(ParsedOperand &Result); + [[nodiscard]] bool + parseInlineDILocation(std::vector &InlineChain, + std::optional &TerminalInlinedAt); + [[nodiscard]] bool parseCFIRegister(DwarfRegisterNumber &Result); + [[nodiscard]] bool parseCFISigned(std::int64_t &Result); + [[nodiscard]] bool parseCFIUnsigned(std::uint32_t &Result); + [[nodiscard]] bool parseCFIOperand(ParsedOperand &Result); + [[nodiscard]] bool parseMemoryBase(MemoryBase &Result, std::int64_t &Offset); + [[nodiscard]] bool parseMemoryOperand(const MachineMemOperand *&Result); + [[nodiscard]] bool parsePredicateOperand(ParsedOperand &Result, bool IsFloating); + [[nodiscard]] bool parseShuffleMaskOperand(ParsedOperand &Result); + [[nodiscard]] bool parseDebugInstrRefOperand(ParsedOperand &Result); + [[nodiscard]] bool parseLaneMaskOperand(ParsedOperand &Result); + [[nodiscard]] bool parseIntrinsicOperand(ParsedOperand &Result); + [[nodiscard]] bool parseTargetIndexOperand(ParsedOperand &Result); + [[nodiscard]] bool parseLiveOutMaskOperand(ParsedOperand &Result); + [[nodiscard]] bool parseCustomMaskOperand(ParsedOperand &Result); + [[nodiscard]] bool parseBlockAddressOperand(ParsedOperand &Result); + + [[nodiscard]] Register getOrCreateVirtualRegister(const MIToken &Token); + [[nodiscard]] MachineBasicBlock *blockFor(const MIToken &Token); + [[nodiscard]] std::optional frameIndexFor(const MIToken &Token, bool Fixed); + [[nodiscard]] std::optional constantPoolIndexFor(const MIToken &Token); + [[nodiscard]] std::optional jumpTableIndexFor(const MIToken &Token); + [[nodiscard]] std::string symbolName(const MIToken &Token) const; + + MachineFunction &Function; + const TargetDescription &Target; + MILexer Lexer; + MIParserContext Context; + MIParserOptions Options; + std::vector Tokens; + std::size_t Position = 0; + std::vector Diagnostics; + std::unordered_map Blocks; + std::unordered_map NumericVirtualRegisters; + std::unordered_map NamedVirtualRegisters; + std::unordered_set ExplicitSuccessorBlocks; + std::size_t ParsedInstructionCount = 0; + bool ParseAttempted = false; +}; + +bool MIParser::Impl::expect(MITokenKind Kind, std::string_view Description) { + if (consume(Kind)) + return false; + return fail("expected " + std::string(Description) + ", found " + + std::string(getMITokenKindName(token().kind()))); +} + +bool MIParser::Impl::fail(const MIToken &At, std::string Message) { + if (Diagnostics.empty()) { + Diagnostics.push_back(TextDiagnostic{ + .Severity = DiagnosticSeverity::Error, + .Category = "mir-parser", + .Message = std::move(Message), + .SourceName = std::string(Lexer.source().name()), + .Range = At.range(), + }); + } + return true; +} + +Expected MIParser::Impl::failureResult() const { + const std::string Message = + Diagnostics.empty() ? "machine instruction parsing failed" : Diagnostics.front().Message; + return makeUnexpected(ErrorCode::ParseError, Message); +} + +bool MIParser::Impl::importError(const MIToken &At, const Error &Failure) { + return fail(At, std::string(Failure.message())); +} + +bool MIParser::Impl::tokenize() { + while (true) { + MIToken Token = Lexer.next(); + const MITokenKind Kind = Token.kind(); + Tokens.push_back(std::move(Token)); + if (Kind == MITokenKind::Error) { + const auto LexerDiagnostics = Lexer.diagnostics(); + Diagnostics.assign(LexerDiagnostics.begin(), LexerDiagnostics.end()); + return true; + } + if (Kind == MITokenKind::EndOfFile) + return false; + } +} + +bool MIParser::Impl::parseUnsigned(const MIToken &Token, std::uint64_t &Value) { + if (Token.kind() == MITokenKind::HexLiteral) + return !parseHexadecimal(Token.spelling(), Value); + if (Token.hasIntegerValue()) + return !parseUnsignedDecimal(Token.integerValue(), Value); + return true; +} + +bool MIParser::Impl::parseUnsigned32(const MIToken &Token, std::uint32_t &Value) { + std::uint64_t Wide = 0; + if (parseUnsigned(Token, Wide) || Wide > std::numeric_limits::max()) + return true; + Value = static_cast(Wide); + return false; +} + +bool MIParser::Impl::parseSigned64(const MIToken &Token, std::int64_t &Value) { + if (Token.kind() != MITokenKind::IntegerLiteral) + return true; + if (parseSignedDecimal(Token.integerValue(), Value)) + return false; + std::uint64_t Unsigned = 0; + if (!parseUnsignedDecimal(Token.integerValue(), Unsigned)) + return true; + Value = std::bit_cast(Unsigned); + return false; +} + +bool MIParser::Impl::parseOptionalOffset(std::int64_t &Offset) { + Offset = 0; + if (!at(MITokenKind::Plus) && !at(MITokenKind::Minus)) + return false; + const bool Negative = at(MITokenKind::Minus); + advance(); + std::uint64_t Magnitude = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned(token(), Magnitude) || + Magnitude > (std::uint64_t{1} << 63U)) { + return fail("expected a 64-bit integer offset"); + } + if (Negative) { + if (Magnitude == (std::uint64_t{1} << 63U)) + Offset = std::numeric_limits::min(); + else + Offset = -static_cast(Magnitude); + } else { + if (Magnitude > static_cast(std::numeric_limits::max())) + return fail("positive offset exceeds signed 64-bit range"); + Offset = static_cast(Magnitude); + } + advance(); + return false; +} + +bool MIParser::Impl::parseAlignment(Alignment &Result) { + advance(); + std::uint64_t Bytes = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned(token(), Bytes)) + return fail("expected an unsigned alignment"); + auto Parsed = Alignment::create(Bytes); + if (!Parsed) + return importError(token(), Parsed.error()); + Result = *Parsed; + advance(); + return false; +} + +bool MIParser::Impl::parseScalarLowLevelType(const MIToken &TypeToken, LLT &Result) { + if (TypeToken.kind() != MITokenKind::Identifier) + return fail(TypeToken, "expected a scalar low-level type"); + std::string_view Spelling = TypeToken.stringValue(); + enum class ScalarKind : std::uint8_t { + Any, + Integer, + Float, + BFloat, + Pointer, + }; + ScalarKind Kind = ScalarKind::Any; + std::string_view Digits; + if (Spelling.starts_with("bf")) { + Kind = ScalarKind::BFloat; + Digits = Spelling.substr(2); + } else if (Spelling.starts_with('s')) { + Kind = ScalarKind::Any; + Digits = Spelling.substr(1); + } else if (Spelling.starts_with('i')) { + Kind = ScalarKind::Integer; + Digits = Spelling.substr(1); + } else if (Spelling.starts_with('f')) { + Kind = ScalarKind::Float; + Digits = Spelling.substr(1); + } else if (Spelling.starts_with('p')) { + Kind = ScalarKind::Pointer; + Digits = Spelling.substr(1); + } else { + return fail(TypeToken, "unknown scalar low-level type '" + std::string(Spelling) + "'"); + } + + std::uint64_t Value = 0; + if (!parseUnsignedDigits(Digits, Value)) + return fail(TypeToken, "low-level type suffix must be an unsigned decimal integer"); + + Expected Created = makeUnexpected(ErrorCode::ParseError, "invalid low-level type"); + switch (Kind) { + case ScalarKind::Any: + if (Value == 0) { + Result = LLT::token(); + return false; + } + Created = LLT::makeAnyScalar(Value); + break; + case ScalarKind::Integer: + Created = LLT::makeInteger(Value); + break; + case ScalarKind::Float: { + std::optional Semantics; + if (Value == 16) + Semantics = FloatSemantics::IEEEHalf; + else if (Value == 32) + Semantics = FloatSemantics::IEEESingle; + else if (Value == 64) + Semantics = FloatSemantics::IEEEDouble; + else if (Value == 128) + Semantics = FloatSemantics::IEEEQuad; + if (!Semantics) + return fail(TypeToken, "unsupported IEEE floating low-level type width"); + Created = LLT::makeFloat(*Semantics); + break; + } + case ScalarKind::BFloat: + if (Value != 16) + return fail(TypeToken, "bfloat low-level type must have width 16"); + Created = LLT::makeFloat(FloatSemantics::BFloat); + break; + case ScalarKind::Pointer: + if (Context.DefaultPointerSizeInBits == 0) + return fail(TypeToken, "pointer low-level type requires an explicit pointer size"); + Created = LLT::makePointer(Value, Context.DefaultPointerSizeInBits); + break; + } + if (!Created) + return importError(TypeToken, Created.error()); + Result = *Created; + return false; +} + +bool MIParser::Impl::parseLowLevelType(LLT &Result) { + const MIToken Begin = token(); + if (at(MITokenKind::Identifier)) { + if (parseScalarLowLevelType(token(), Result)) + return true; + advance(); + return false; + } + if (!consume(MITokenKind::Less)) + return fail(Begin, "expected a scalar, pointer, or vector low-level type"); + + bool Scalable = false; + if (at(MITokenKind::Identifier) && token().stringValue() == "vscale") { + Scalable = true; + advance(); + if (!at(MITokenKind::Identifier) || token().stringValue() != "x") + return fail("expected 'x' after 'vscale' in a scalable vector type"); + advance(); + } + + std::uint64_t ElementCount = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned(token(), ElementCount)) + return fail("expected an unsigned vector element count"); + advance(); + if (!at(MITokenKind::Identifier) || token().stringValue() != "x") + return fail("expected 'x' after the vector element count"); + advance(); + + LLT ElementType; + if (parseScalarLowLevelType(token(), ElementType)) + return true; + if (ElementType.isToken()) + return fail("token cannot be a vector element type"); + advance(); + if (expect(MITokenKind::Greater, "'>' after the vector low-level type")) + return true; + + Expected Created = Scalable ? LLT::makeScalableVector(ElementCount, ElementType) + : LLT::makeFixedVector(ElementCount, ElementType); + if (!Created) + return importError(Begin, Created.error()); + Result = *Created; + return false; +} + +bool MIParser::Impl::parseBlockAttributes(MachineBasicBlock *Block) { + std::unordered_set Seen; + while (!at(MITokenKind::RightParen)) { + const MIToken AttributeToken = token(); + if (atKeyword("machine-block-address-taken") || atKeyword("landing-pad") || + atKeyword("inlineasm-br-indirect-target") || atKeyword("ehfunclet-entry") || + atKeyword("ehscope-entry")) { + const std::string Name(AttributeToken.stringValue()); + if (!Seen.insert(Name).second) + return fail("duplicate basic block attribute '" + Name + "'"); + if (Block != nullptr) { + if (Name == "machine-block-address-taken") + Block->attributes().set(MachineBasicBlockAttribute::MachineBlockAddressTaken); + else if (Name == "landing-pad") + Block->attributes().set(MachineBasicBlockAttribute::LandingPad); + else if (Name == "inlineasm-br-indirect-target") + Block->attributes().set(MachineBasicBlockAttribute::InlineAsmBrIndirectTarget); + else if (Name == "ehfunclet-entry") + Block->attributes().set(MachineBasicBlockAttribute::EHFuncletEntry); + else + Block->attributes().set(MachineBasicBlockAttribute::EHScopeEntry); + } + advance(); + } else if (atKeyword("ir-block-address-taken")) { + if (!Seen.insert("ir-block-address-taken").second) + return fail("duplicate basic block attribute 'ir-block-address-taken'"); + advance(); + if (!at(MITokenKind::IRBlock) && !at(MITokenKind::NamedIRBlock)) + return fail("expected an IR block after 'ir-block-address-taken'"); + if (Block != nullptr) { + Block->attributes().set(MachineBasicBlockAttribute::IRBlockAddressTaken); + auto SetName = Block->attributes().setIRBlockName(symbolName(token())); + if (!SetName) + return importError(token(), SetName.error()); + } + advance(); + } else if (at(MITokenKind::IRBlock) || at(MITokenKind::NamedIRBlock)) { + if (!Seen.insert("ir-block").second) + return fail("duplicate IR block attribute"); + if (Block != nullptr) { + auto SetName = Block->attributes().setIRBlockName(symbolName(token())); + if (!SetName) + return importError(token(), SetName.error()); + } + advance(); + } else if (atKeyword("align")) { + if (!Seen.insert("align").second) + return fail("duplicate basic block alignment"); + Alignment Align; + if (parseAlignment(Align)) + return true; + if (Block != nullptr) + Block->attributes().setAlignment(Align); + } else if (atKeyword("bbsections")) { + if (!Seen.insert("bbsections").second) + return fail("duplicate basic block section"); + advance(); + MachineBasicBlockSectionID Section; + std::uint32_t Number = 0; + if (at(MITokenKind::IntegerLiteral) && !parseUnsigned32(token(), Number)) + Section = MachineBasicBlockSectionID::numbered(Number); + else if (at(MITokenKind::Identifier) && token().stringValue() == "Exception") + Section = MachineBasicBlockSectionID::exception(); + else if (at(MITokenKind::Identifier) && token().stringValue() == "Cold") + Section = MachineBasicBlockSectionID::cold(); + else + return fail("unknown basic block section ID"); + if (Block != nullptr) + Block->attributes().setSectionID(Section); + advance(); + } else if (atKeyword("bb_id")) { + if (!Seen.insert("bb_id").second) + return fail("duplicate basic block profile ID"); + advance(); + std::uint32_t BaseID = 0; + std::uint32_t CloneID = 0; + if (at(MITokenKind::FloatingPointLiteral)) { + const std::string_view Spelling = token().spelling(); + const std::size_t Dot = Spelling.find('.'); + std::uint64_t Base = 0; + std::uint64_t Clone = 0; + if (Dot == std::string_view::npos || !parseUnsignedDecimal(Spelling.substr(0, Dot), Base) || + !parseUnsignedDecimal(Spelling.substr(Dot + 1), Clone) || + Base > std::numeric_limits::max() || + Clone > std::numeric_limits::max()) { + return fail("invalid basic block profile ID"); + } + BaseID = static_cast(Base); + CloneID = static_cast(Clone); + advance(); + } else { + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned32(token(), BaseID)) + return fail("invalid basic block base ID"); + advance(); + if (consume(MITokenKind::Dot) || consume(MITokenKind::Comma)) { + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned32(token(), CloneID)) + return fail("invalid basic block clone ID"); + advance(); + } + } + if (Block != nullptr) + Block->attributes().setProfileID({BaseID, CloneID}); + } else if (atKeyword("call-frame-size")) { + if (!Seen.insert("call-frame-size").second) + return fail("duplicate basic block call frame size"); + advance(); + std::uint32_t Size = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned32(token(), Size)) + return fail("invalid basic block call frame size"); + if (Block != nullptr) + Block->attributes().setCallFrameSize(Size); + advance(); + } else { + return fail("unknown basic block attribute '" + std::string(token().spelling()) + "'"); + } + + if (!consume(MITokenKind::Comma)) + break; + } + return expect(MITokenKind::RightParen, "')'"); +} + +bool MIParser::Impl::parseBlockDefinition(bool Create, std::uint32_t &ID) { + const MIToken Label = token(); + if (!at(MITokenKind::MachineBasicBlockLabel) || parseUnsigned32(Label, ID)) + return fail("invalid machine basic block label"); + advance(); + + MachineBasicBlock *Block = nullptr; + if (Create) { + if (Blocks.size() >= Options.MaximumBlocks) + return fail(Label, "machine basic block count exceeds parser limit"); + if (Blocks.contains(ID)) + return fail(Label, "redefinition of machine basic block #" + std::to_string(ID)); + auto Created = Function.createBasicBlock(); + if (!Created) + return importError(Label, Created.error()); + Block = *Created; + auto Appended = Function.appendBlock(*Block); + if (!Appended) + return importError(Label, Appended.error()); + if (!Label.stringValue().empty()) { + auto SetName = Block->attributes().setName(std::string(Label.stringValue())); + if (!SetName) + return importError(Label, SetName.error()); + } + Blocks.emplace(ID, Block); + } else { + const auto Found = Blocks.find(ID); + if (Found == Blocks.end()) + return fail(Label, "use of undefined machine basic block #" + std::to_string(ID)); + Block = Found->second; + } + + if (consume(MITokenKind::LeftParen) && parseBlockAttributes(Create ? Block : nullptr)) + return true; + return expect(MITokenKind::Colon, "':' after the basic block definition"); +} + +bool MIParser::Impl::parseFirstPass() { + Position = 0; + bool AtLineStart = true; + std::size_t BraceDepth = 0; + while (!at(MITokenKind::EndOfFile)) { + if (consume(MITokenKind::Newline)) { + AtLineStart = true; + continue; + } + if (at(MITokenKind::MachineBasicBlockLabel)) { + if (!AtLineStart || token().range().Begin.Column != 1) + return fail("basic block definition must be at the start of a line"); + std::uint32_t ID = 0; + if (parseBlockDefinition(true, ID)) + return true; + AtLineStart = false; + continue; + } + if (at(MITokenKind::LeftBrace)) + ++BraceDepth; + else if (at(MITokenKind::RightBrace)) { + if (BraceDepth == 0) + return fail("extraneous closing instruction bundle brace"); + --BraceDepth; + } + AtLineStart = false; + advance(); + } + if (BraceDepth != 0) + return fail("unterminated instruction bundle"); + return false; +} + +Register MIParser::Impl::getOrCreateVirtualRegister(const MIToken &Token) { + if (Token.kind() == MITokenKind::VirtualRegister) { + std::uint32_t ID = 0; + if (parseUnsigned32(Token, ID)) + return {}; + if (const auto Found = NumericVirtualRegisters.find(ID); + Found != NumericVirtualRegisters.end()) { + return Found->second; + } + auto Created = Function.registerInfo().createVirtualRegister(); + if (!Created) { + static_cast(importError(Token, Created.error())); + return {}; + } + NumericVirtualRegisters.emplace(ID, *Created); + return *Created; + } + + const std::string Name(Token.stringValue()); + if (const auto Found = NamedVirtualRegisters.find(Name); Found != NamedVirtualRegisters.end()) + return Found->second; + auto Created = Function.registerInfo().createVirtualRegister(); + if (!Created) { + static_cast(importError(Token, Created.error())); + return {}; + } + NamedVirtualRegisters.emplace(Name, *Created); + return *Created; +} + +bool MIParser::Impl::parseRegister(Register &Result) { + const MIToken RegisterToken = token(); + if (consume(MITokenKind::Underscore)) { + Result = {}; + return false; + } + if (at(MITokenKind::NamedRegister)) { + if (RegisterToken.stringValue() == "noreg") { + Result = {}; + advance(); + return false; + } + const PhysicalRegisterDesc *Description = + Target.registers().physicalRegister(RegisterToken.stringValue()); + if (Description == nullptr) + return fail("unknown physical register '$" + std::string(RegisterToken.stringValue()) + "'"); + Result = Register::fromPhysical(Description->Reg); + advance(); + return false; + } + if (at(MITokenKind::VirtualRegister) || at(MITokenKind::NamedVirtualRegister)) { + Result = getOrCreateVirtualRegister(RegisterToken); + if (Result.isNoRegister()) + return true; + advance(); + return false; + } + return fail("expected a machine register"); +} + +bool MIParser::Impl::parseRegisterOperand(bool IsDef, ParsedOperand &Result) { + const MIToken Begin = token(); + RegisterOperandFlags Flags{IsDef ? RegisterOperandFlag::Define : RegisterOperandFlag::Use}; + std::unordered_set SeenFlags; + while (token().isRegisterFlag()) { + const std::string Name(token().stringValue()); + if (!SeenFlags.insert(Name).second) + return fail("duplicate '" + Name + "' register flag"); + if (Name == "implicit") + Flags.set(RegisterOperandFlag::Implicit); + else if (Name == "implicit-def") { + Flags.clear(RegisterOperandFlag::Use); + Flags.set(RegisterOperandFlag::Define); + Flags.set(RegisterOperandFlag::Implicit); + IsDef = true; + } else if (Name == "def") { + Flags.clear(RegisterOperandFlag::Use); + Flags.set(RegisterOperandFlag::Define); + IsDef = true; + } else if (Name == "dead") + Flags.set(RegisterOperandFlag::Dead); + else if (Name == "killed") + Flags.set(RegisterOperandFlag::Kill); + else if (Name == "undef") + Flags.set(RegisterOperandFlag::Undef); + else if (Name == "internal") + Flags.set(RegisterOperandFlag::InternalRead); + else if (Name == "early-clobber") + Flags.set(RegisterOperandFlag::EarlyClobber); + else if (Name == "debug-use") + Flags.set(RegisterOperandFlag::Debug); + else if (Name == "renamable") + Flags.set(RegisterOperandFlag::Renamable); + advance(); + } + + Register Reg; + if (parseRegister(Reg)) + return true; + + SubRegIndex SubReg; + if (consume(MITokenKind::Dot)) { + if (!Reg.isVirtual() || !at(MITokenKind::Identifier)) + return fail("subregister index requires a virtual register"); + const SubRegIndexDesc *Description = Target.registers().subRegIndex(token().stringValue()); + if (Description == nullptr) + return fail("unknown subregister index '" + std::string(token().stringValue()) + "'"); + SubReg = Description->ID; + advance(); + } + + if (consume(MITokenKind::Colon)) { + if (!Reg.isVirtual()) + return fail("register class or bank requires a virtual register"); + auto InfoResult = Function.registerInfo().virtualRegisterInfo(Reg); + if (!InfoResult) + return importError(Begin, InfoResult.error()); + VirtualRegisterInfo &Info = InfoResult->get(); + if (consume(MITokenKind::Underscore)) { + if (Info.RegClass || Info.Bank) + return fail("conflicting generic virtual register constraint"); + } else if (at(MITokenKind::Identifier)) { + if (const RegisterClassDesc *Class = + Target.registers().registerClass(token().stringValue())) { + if ((Info.RegClass && *Info.RegClass != Class->ID) || Info.Bank) + return fail("conflicting virtual register class"); + auto SetClass = Function.registerInfo().setRegisterClass(Reg, Class->ID); + if (!SetClass) + return importError(token(), SetClass.error()); + } else if (const RegisterBankDesc *Bank = + Target.registers().registerBank(token().stringValue())) { + if ((Info.Bank && *Info.Bank != Bank->ID) || Info.RegClass) + return fail("conflicting virtual register bank"); + auto SetBank = Function.registerInfo().setRegisterBank(Reg, Bank->ID); + if (!SetBank) + return importError(token(), SetBank.error()); + } else { + return fail("unknown register class or bank '" + std::string(token().stringValue()) + "'"); + } + advance(); + } else { + return fail("expected '_', register class, or register bank name"); + } + } + + std::optional TiedDef; + if (consume(MITokenKind::LeftParen)) { + if (atKeyword("tied-def")) { + if (IsDef) + return fail("'tied-def' is only valid on register uses"); + advance(); + std::uint64_t Index = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned(token(), Index) || + Index > std::numeric_limits::max()) { + return fail("invalid tied-def operand index"); + } + TiedDef = static_cast(Index); + advance(); + if (expect(MITokenKind::RightParen, "')' after tied-def")) + return true; + } else { + if (!Reg.isVirtual()) + return fail("low-level type is only valid on a virtual register"); + LLT Type; + if (parseLowLevelType(Type)) + return true; + if (expect(MITokenKind::RightParen, "')' after the low-level type")) + return true; + auto InfoResult = Function.registerInfo().virtualRegisterInfo(Reg); + if (!InfoResult) + return importError(Begin, InfoResult.error()); + VirtualRegisterInfo &Info = InfoResult->get(); + if (Info.Type && *Info.Type != Type) + return fail(Begin, "conflicting virtual register low-level type"); + auto SetType = Function.registerInfo().setType(Reg, Type); + if (!SetType) + return importError(Begin, SetType.error()); + } + } + + if (IsDef && Reg.isVirtual()) { + auto InfoResult = Function.registerInfo().virtualRegisterInfo(Reg); + if (!InfoResult) + return importError(Begin, InfoResult.error()); + const VirtualRegisterInfo &Info = InfoResult->get(); + if (!Info.RegClass && !Info.Type) + return fail(Begin, "generic virtual register definition requires a low-level type"); + } + + if (Flags.has(RegisterOperandFlag::Define) && Flags.has(RegisterOperandFlag::Kill)) + return fail(Begin, "defined register operand cannot be killed"); + if (!Flags.has(RegisterOperandFlag::Define) && Flags.has(RegisterOperandFlag::Dead)) + return fail(Begin, "register use cannot be dead"); + + auto Operand = MachineOperand::registerOperand(Reg, Flags, SubReg); + if (!Operand) + return importError(Begin, Operand.error()); + Result = + ParsedOperand{std::move(*Operand), TiedDef, {Begin.range().Begin, token().range().Begin}}; + return false; +} + +MachineBasicBlock *MIParser::Impl::blockFor(const MIToken &Token) { + std::uint32_t ID = 0; + if (parseUnsigned32(Token, ID)) { + static_cast(fail(Token, "invalid machine basic block reference")); + return nullptr; + } + const auto Found = Blocks.find(ID); + if (Found == Blocks.end()) { + static_cast(fail(Token, "use of undefined machine basic block #" + std::to_string(ID))); + return nullptr; + } + if (!Token.stringValue().empty()) { + const std::optional Name = Found->second->attributes().name(); + if (!Name || *Name != Token.stringValue()) { + static_cast(fail(Token, "machine basic block reference has a mismatched name")); + return nullptr; + } + } + return Found->second; +} + +std::optional MIParser::Impl::frameIndexFor(const MIToken &Token, bool Fixed) { + std::uint32_t ID = 0; + if (parseUnsigned32(Token, ID)) { + static_cast(fail(Token, "invalid stack object reference")); + return std::nullopt; + } + const auto &Slots = Fixed ? Context.FixedStackObjects : Context.StackObjects; + for (const MIFrameObjectSlot &Slot : Slots) { + if (Slot.TextID != ID) + continue; + if (!Token.stringValue().empty() && (!Slot.Name || *Slot.Name != Token.stringValue())) { + static_cast(fail(Token, "stack object reference has a mismatched name")); + return std::nullopt; + } + if (Function.frameInfo().object(Slot.Index) == nullptr) { + static_cast(fail(Token, "stack object slot maps to a missing frame object")); + return std::nullopt; + } + return Slot.Index; + } + static_cast(fail(Token, std::string("use of undefined ") + + (Fixed ? "fixed stack" : "stack") + " object #" + + std::to_string(ID))); + return std::nullopt; +} + +std::optional MIParser::Impl::constantPoolIndexFor(const MIToken &Token) { + std::uint32_t ID = 0; + if (parseUnsigned32(Token, ID)) { + static_cast(fail(Token, "invalid constant pool reference")); + return std::nullopt; + } + for (const MIConstantPoolSlot &Slot : Context.ConstantPoolItems) { + if (Slot.TextID == ID && Function.constantPool().entry(Slot.Index) != nullptr) + return Slot.Index; + } + static_cast(fail(Token, "use of undefined constant pool item #" + std::to_string(ID))); + return std::nullopt; +} + +std::optional MIParser::Impl::jumpTableIndexFor(const MIToken &Token) { + std::uint32_t ID = 0; + if (parseUnsigned32(Token, ID)) { + static_cast(fail(Token, "invalid jump table reference")); + return std::nullopt; + } + for (const MIJumpTableSlot &Slot : Context.JumpTables) { + if (Slot.TextID == ID && Function.jumpTableInfo().table(Slot.Index) != nullptr) + return Slot.Index; + } + static_cast(fail(Token, "use of undefined jump table #" + std::to_string(ID))); + return std::nullopt; +} + +std::string MIParser::Impl::symbolName(const MIToken &Token) const { + if (Token.hasStringValue()) + return std::string(Token.stringValue()); + return std::string(Token.integerValue()); +} + +bool MIParser::Impl::parseTargetFlags(std::uint32_t &Flags) { + Flags = 0; + if (!atKeyword("target-flags")) + return false; + advance(); + if (expect(MITokenKind::LeftParen, "'(' after target-flags")) + return true; + if (!at(MITokenKind::Identifier)) + return fail("expected a target flag name"); + + const std::string First(token().stringValue()); + if (const auto Direct = Target.mirText().directOperandFlag(First)) + Flags = *Direct; + else if (const auto Bit = Target.mirText().bitmaskOperandFlag(First)) + Flags = *Bit; + else + return fail("unknown target operand flag '" + First + "'"); + advance(); + + std::unordered_set Seen{First}; + while (consume(MITokenKind::Comma)) { + if (!at(MITokenKind::Identifier)) + return fail("expected a target bit flag name"); + const std::string Name(token().stringValue()); + const auto Bit = Target.mirText().bitmaskOperandFlag(Name); + if (!Bit) + return fail("unknown target bit operand flag '" + Name + "'"); + if (!Seen.insert(Name).second || (Flags & *Bit) == *Bit) + return fail("duplicate target operand flag '" + Name + "'"); + Flags |= *Bit; + advance(); + } + if (expect(MITokenKind::RightParen, "')' after target flags")) + return true; + const auto Valid = Target.mirText().validateOperandFlags(Flags); + return !Valid && importError(token(), Valid.error()); +} + +bool MIParser::Impl::parseTypedIntegerOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + const std::string_view TypeSpelling = Begin.stringValue(); + if (!TypeSpelling.starts_with('i')) + return fail(Begin, "typed integer operand must use an 'iN' type"); + std::uint64_t WideBitWidth = 0; + if (!parseUnsignedDigits(TypeSpelling.substr(1), WideBitWidth) || + WideBitWidth > IntegerImmediate::MaxBitWidth) { + return fail(Begin, "typed integer operand has an invalid bit width"); + } + const auto BitWidth = static_cast(WideBitWidth); + advance(); + + std::string_view ValueSpelling; + if (at(MITokenKind::IntegerLiteral)) { + ValueSpelling = token().integerValue(); + } else if (at(MITokenKind::Identifier) && token().stringValue() == "true") { + ValueSpelling = "1"; + } else if (at(MITokenKind::Identifier) && token().stringValue() == "false") { + ValueSpelling = "0"; + } else { + return fail("expected a decimal integer, true, or false after the typed integer type"); + } + + auto Value = parseIntegerImmediateValue(BitWidth, ValueSpelling); + if (!Value) + return importError(token(), Value.error()); + advance(); + Result = ParsedOperand{ + MachineOperand::integerImmediate(std::move(*Value)), + std::nullopt, + {Begin.range().Begin, token().range().Begin}, + }; + return false; +} + +bool MIParser::Impl::parseFloatingImmediateOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + const auto Semantics = floatSemanticsForKeyword(Begin.stringValue()); + if (!Semantics) + return fail(Begin, "unknown floating-point immediate type"); + const std::uint32_t BitWidth = getFloatSemanticsBitWidth(*Semantics).value_or(0); + advance(); + if (!at(MITokenKind::FloatingPointLiteral) && !at(MITokenKind::HexLiteral)) + return fail("expected a floating-point literal"); + + const MIToken Literal = token(); + const std::string_view Spelling = Literal.spelling(); + std::vector Words; + if (Spelling.starts_with("f0x") || Spelling.starts_with("f0X")) { + if (!parseHexWords(Spelling.substr(3), BitWidth, Words)) + return fail(Literal, "raw floating-point literal does not fit its semantics"); + } else if (Spelling.starts_with("0x") || Spelling.starts_with("0X")) { + std::string_view Digits = Spelling.substr(2); + char Prefix = '\0'; + if (!Digits.empty() && !hexDigit(Digits.front())) { + Prefix = Digits.front(); + Digits.remove_prefix(1); + } + char ExpectedPrefix = '\0'; + switch (*Semantics) { + case FloatSemantics::IEEEHalf: + ExpectedPrefix = 'H'; + break; + case FloatSemantics::BFloat: + ExpectedPrefix = 'R'; + break; + case FloatSemantics::X87DoubleExtended: + ExpectedPrefix = 'K'; + break; + case FloatSemantics::IEEEQuad: + ExpectedPrefix = 'L'; + break; + case FloatSemantics::PPCDoubleDouble: + case FloatSemantics::PPCDoubleDoubleLegacy: + ExpectedPrefix = 'M'; + break; + default: + break; + } + if (ExpectedPrefix != '\0') { + if (Prefix != ExpectedPrefix || !parseHexWords(Digits, BitWidth, Words)) + return fail(Literal, "floating-point hexadecimal prefix does not match its semantics"); + } else if (Prefix != '\0') { + return fail(Literal, "unexpected floating-point hexadecimal prefix"); + } else if (*Semantics == FloatSemantics::IEEESingle) { + std::uint64_t DoubleBits = 0; + if (!parseHexadecimal(Spelling, DoubleBits)) + return fail(Literal, "invalid IEEE single hexadecimal literal"); + const float Value = static_cast(std::bit_cast(DoubleBits)); + Words = {std::bit_cast(Value)}; + } else if (*Semantics == FloatSemantics::IEEEDouble) { + std::uint64_t DoubleBits = 0; + if (!parseHexadecimal(Spelling, DoubleBits)) + return fail(Literal, "invalid IEEE double hexadecimal literal"); + Words = {DoubleBits}; + } else { + return fail(Literal, "floating-point literal requires its semantics prefix"); + } + } else { + const char *First = Spelling.data(); + const char *Last = First + Spelling.size(); + if (*Semantics == FloatSemantics::IEEEDouble) { + double Value = 0; + const auto Parsed = std::from_chars(First, Last, Value, std::chars_format::general); + if (Parsed.ec != std::errc{} || Parsed.ptr != Last) + return fail(Literal, "invalid IEEE double decimal literal"); + Words = {std::bit_cast(Value)}; + } else if (*Semantics == FloatSemantics::IEEESingle || *Semantics == FloatSemantics::IEEEHalf || + *Semantics == FloatSemantics::BFloat) { + float Value = 0; + const auto Parsed = std::from_chars(First, Last, Value, std::chars_format::general); + if (Parsed.ec != std::errc{} || Parsed.ptr != Last) + return fail(Literal, "invalid floating-point decimal literal"); + if (*Semantics == FloatSemantics::IEEESingle) + Words = {std::bit_cast(Value)}; + else if (*Semantics == FloatSemantics::IEEEHalf) + Words = {floatToHalfBits(Value)}; + else + Words = {floatToBFloatBits(Value)}; + } else { + return fail(Literal, "this floating-point semantics requires an exact hexadecimal literal"); + } + } + + auto Bits = FloatingPointBits::create(*Semantics, Words); + if (!Bits) + return importError(Literal, Bits.error()); + advance(); + Result = ParsedOperand{ + MachineOperand::floatingImmediate(*Bits), + std::nullopt, + {Begin.range().Begin, token().range().Begin}, + }; + return false; +} + +bool MIParser::Impl::parseMetadataReference(MachineMetadataReference &Result) { + const MIToken Begin = token(); + if (expect(MITokenKind::Exclaim, "'!' before a metadata slot")) + return true; + std::uint32_t TextID = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned32(token(), TextID)) + return fail("expected a 32-bit metadata slot number"); + + for (const MIMetadataSlot &Slot : Context.Metadata) { + if (Slot.TextID != TextID) + continue; + if (!Slot.Reference.isValid()) + return fail(Begin, "metadata slot maps to an invalid reference"); + Result = Slot.Reference; + advance(); + return false; + } + if (Function.metadata().node(TextID) != nullptr) { + Result = MachineMetadataReference::machineFunction(TextID); + advance(); + return false; + } + return fail(Begin, "use of undefined metadata slot !" + std::to_string(TextID)); +} + +bool MIParser::Impl::parseMetadataOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + MachineMetadataValue Value; + if (at(MITokenKind::Exclaim)) { + MachineMetadataReference Reference; + if (parseMetadataReference(Reference)) + return true; + auto Created = MachineMetadataValue::reference(Reference); + if (!Created) + return importError(Begin, Created.error()); + Value = std::move(*Created); + } else if (at(MITokenKind::MetadataKeyword) && token().isMetadataKeyword("!DIExpression")) { + advance(); + if (expect(MITokenKind::LeftParen, "'(' after !DIExpression")) + return true; + std::vector Elements; + while (!at(MITokenKind::RightParen)) { + if (at(MITokenKind::Identifier)) { + const auto Opcode = debugExpressionOpcode(token().stringValue()); + if (!Opcode) + return fail("unknown debug expression opcode '" + std::string(token().stringValue()) + + "'"); + Elements.push_back(*Opcode); + advance(); + } else if (at(MITokenKind::IntegerLiteral)) { + std::int64_t Signed = 0; + if (parseSigned64(token(), Signed)) + return fail("debug expression element exceeds 64 bits"); + Elements.push_back(std::bit_cast(Signed)); + advance(); + } else { + return fail("expected a debug expression opcode or integer"); + } + if (!consume(MITokenKind::Comma)) + break; + } + if (expect(MITokenKind::RightParen, "')' after !DIExpression")) + return true; + Value = MachineMetadataValue::expression(MachineDIExpression(std::move(Elements))); + } else { + return fail("expected a metadata reference or !DIExpression"); + } + + auto Operand = MachineOperand::metadata(std::move(Value)); + if (!Operand) + return importError(Begin, Operand.error()); + Result = ParsedOperand{ + std::move(*Operand), + std::nullopt, + {Begin.range().Begin, token().range().Begin}, + }; + return false; +} + +bool MIParser::Impl::parseInlineDILocation( + std::vector &InlineChain, + std::optional &TerminalInlinedAt) { + if (!at(MITokenKind::MetadataKeyword) || !token().isMetadataKeyword("!DILocation")) { + return fail("expected an inline !DILocation"); + } + advance(); + if (expect(MITokenKind::LeftParen, "'(' after !DILocation")) + return true; + + MachineDILocationFrame Frame; + bool HasLine = false; + bool HasScope = false; + std::vector NestedChain; + std::optional NestedTerminal; + std::unordered_set SeenFields; + while (!at(MITokenKind::RightParen)) { + if (!at(MITokenKind::Identifier)) + return fail("expected a DILocation field name"); + const MIToken FieldToken = token(); + const std::string Field(token().stringValue()); + if (!SeenFields.insert(Field).second) + return fail("duplicate DILocation field '" + Field + "'"); + advance(); + if (expect(MITokenKind::Colon, "':' after a DILocation field name")) + return true; + + if (Field == "line") { + std::uint32_t Line = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned32(token(), Line)) + return fail("expected an unsigned 32-bit DILocation line"); + Frame.Line = Line; + HasLine = true; + advance(); + } else if (Field == "column") { + std::uint64_t Column = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned(token(), Column) || + Column > std::numeric_limits::max()) { + return fail("expected an unsigned 16-bit DILocation column"); + } + Frame.Column = static_cast(Column); + advance(); + } else if (Field == "scope") { + MachineMetadataReference Scope; + if (parseMetadataReference(Scope)) + return true; + if (Scope.scope() != MachineMetadataScope::EmbeddedIR) + return fail(FieldToken, "DILocation scope must reference embedded IR metadata"); + Frame.Scope = Scope; + HasScope = true; + } else if (Field == "inlinedAt") { + if (at(MITokenKind::MetadataKeyword) && token().isMetadataKeyword("!DILocation")) { + if (parseInlineDILocation(NestedChain, NestedTerminal)) + return true; + } else { + MachineMetadataReference Reference; + if (parseMetadataReference(Reference)) + return true; + if (Reference.scope() != MachineMetadataScope::EmbeddedIR) { + return fail(FieldToken, "DILocation inlinedAt must reference embedded IR metadata"); + } + NestedTerminal = Reference; + } + } else if (Field == "isImplicitCode") { + if (!at(MITokenKind::Identifier) || + (token().stringValue() != "true" && token().stringValue() != "false")) { + return fail("expected 'true' or 'false' for DILocation isImplicitCode"); + } + Frame.IsImplicitCode = token().stringValue() == "true"; + advance(); + } else if (Field == "atomGroup") { + std::uint64_t Group = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned(token(), Group) || + Group > MachineDILocation::MaxAtomGroup) { + return fail("DILocation atomGroup exceeds 61 bits"); + } + Frame.AtomGroup = Group; + advance(); + } else if (Field == "atomRank") { + std::uint64_t Rank = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned(token(), Rank) || Rank > 7) { + return fail("DILocation atomRank exceeds three bits"); + } + Frame.AtomRank = static_cast(Rank); + advance(); + } else { + return fail(FieldToken, "unknown DILocation field '" + Field + "'"); + } + + if (!consume(MITokenKind::Comma)) + break; + } + if (expect(MITokenKind::RightParen, "')' after !DILocation")) + return true; + if (!HasLine) + return fail("DILocation requires a line field"); + if (!HasScope) + return fail("DILocation requires a scope field"); + + InlineChain.push_back(Frame); + InlineChain.insert(InlineChain.end(), NestedChain.begin(), NestedChain.end()); + TerminalInlinedAt = NestedTerminal; + return false; +} + +bool MIParser::Impl::parseCFIRegister(DwarfRegisterNumber &Result) { + if (!at(MITokenKind::NamedRegister)) + return fail("expected a physical register in the CFI instruction"); + const MIToken RegisterToken = token(); + Register Reg; + if (parseRegister(Reg) || !Reg.isPhysical()) + return true; + const auto Physical = Reg.physicalRegister(); + if (!Physical) + return fail(RegisterToken, "CFI register is not a physical register"); + const auto Dwarf = Target.mirText().dwarfRegister(*Physical); + if (!Dwarf) + return fail(RegisterToken, "physical register has no canonical DWARF register number"); + Result = DwarfRegisterNumber::fromValue(*Dwarf); + return false; +} + +bool MIParser::Impl::parseCFISigned(std::int64_t &Result) { + if (!at(MITokenKind::IntegerLiteral) || parseSigned64(token(), Result)) + return fail("expected a signed 64-bit CFI integer"); + advance(); + return false; +} + +bool MIParser::Impl::parseCFIUnsigned(std::uint32_t &Result) { + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned32(token(), Result)) + return fail("expected an unsigned 32-bit CFI integer"); + advance(); + return false; +} + +bool MIParser::Impl::parseCFIOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + const std::string Operation(token().stringValue()); + advance(); + + const auto Comma = [this]() { return expect(MITokenKind::Comma, "',' in CFI instruction"); }; + DwarfRegisterNumber Register; + DwarfRegisterNumber OtherRegister; + std::int64_t Offset = 0; + std::optional Instruction; + if (Operation == "same_value") { + if (parseCFIRegister(Register)) + return true; + Instruction = MachineCFIInstruction::sameValue(Register); + } else if (Operation == "remember_state") { + Instruction = MachineCFIInstruction::rememberState(); + } else if (Operation == "restore_state") { + Instruction = MachineCFIInstruction::restoreState(); + } else if (Operation == "offset" || Operation == "rel_offset") { + if (parseCFIRegister(Register) || Comma() || parseCFISigned(Offset)) + return true; + Instruction = Operation == "offset" ? MachineCFIInstruction::offset(Register, Offset) + : MachineCFIInstruction::relativeOffset(Register, Offset); + } else if (Operation == "def_cfa_register") { + if (parseCFIRegister(Register)) + return true; + Instruction = MachineCFIInstruction::defCFARegister(Register); + } else if (Operation == "def_cfa_offset" || Operation == "adjust_cfa_offset") { + if (parseCFISigned(Offset)) + return true; + Instruction = Operation == "def_cfa_offset" ? MachineCFIInstruction::defCFAOffset(Offset) + : MachineCFIInstruction::adjustCFAOffset(Offset); + } else if (Operation == "def_cfa") { + if (parseCFIRegister(Register) || Comma() || parseCFISigned(Offset)) + return true; + Instruction = MachineCFIInstruction::defCFA(Register, Offset); + } else if (Operation == "llvm_def_aspace_cfa") { + std::uint32_t AddressSpace = 0; + if (parseCFIRegister(Register) || Comma() || parseCFISigned(Offset) || Comma() || + parseCFIUnsigned(AddressSpace)) { + return true; + } + Instruction = MachineCFIInstruction::llvmDefAddressSpaceCFA(Register, Offset, AddressSpace); + } else if (Operation == "restore" || Operation == "undefined") { + if (parseCFIRegister(Register)) + return true; + Instruction = Operation == "restore" ? MachineCFIInstruction::restore(Register) + : MachineCFIInstruction::undefined(Register); + } else if (Operation == "register") { + if (parseCFIRegister(Register) || Comma() || parseCFIRegister(OtherRegister)) + return true; + Instruction = MachineCFIInstruction::registerRule(Register, OtherRegister); + } else if (Operation == "window_save") { + Instruction = MachineCFIInstruction::windowSave(); + } else if (Operation == "negate_ra_sign_state") { + Instruction = MachineCFIInstruction::negateReturnAddressState(); + } else if (Operation == "negate_ra_sign_state_with_pc") { + Instruction = MachineCFIInstruction::negateReturnAddressStateWithPC(); + } else if (Operation == "llvm_register_pair") { + DwarfRegisterNumber First; + DwarfRegisterNumber Second; + std::uint32_t FirstSize = 0; + std::uint32_t SecondSize = 0; + if (parseCFIRegister(Register) || Comma() || parseCFIRegister(First) || Comma() || + parseCFIUnsigned(FirstSize) || Comma() || parseCFIRegister(Second) || Comma() || + parseCFIUnsigned(SecondSize)) { + return true; + } + Instruction = MachineCFIInstruction::llvmRegisterPair({.Register = Register, + .FirstRegister = First, + .FirstSizeInBits = FirstSize, + .SecondRegister = Second, + .SecondSizeInBits = SecondSize}); + } else if (Operation == "llvm_vector_registers") { + if (parseCFIRegister(Register) || Comma()) + return true; + std::vector Registers; + do { + DwarfRegisterNumber VectorRegister; + std::uint32_t Lane = 0; + std::uint32_t Size = 0; + if (parseCFIRegister(VectorRegister) || Comma() || parseCFIUnsigned(Lane) || Comma() || + parseCFIUnsigned(Size)) { + return true; + } + Registers.push_back({.Register = VectorRegister, .Lane = Lane, .SizeInBits = Size}); + if (!at(MITokenKind::Comma)) + break; + advance(); + if (!at(MITokenKind::NamedRegister)) + return fail("expected another vector CFI register tuple"); + } while (true); + auto Created = MachineCFIInstruction::llvmVectorRegisters( + {.Register = Register, .VectorRegisters = std::move(Registers)}); + if (!Created) + return importError(Begin, Created.error()); + Instruction = std::move(*Created); + } else if (Operation == "llvm_vector_offset") { + DwarfRegisterNumber MaskRegister; + std::uint32_t RegisterSize = 0; + std::uint32_t MaskSize = 0; + if (parseCFIRegister(Register) || Comma() || parseCFIUnsigned(RegisterSize) || Comma() || + parseCFIRegister(MaskRegister) || Comma() || parseCFIUnsigned(MaskSize) || Comma() || + parseCFISigned(Offset)) { + return true; + } + Instruction = MachineCFIInstruction::llvmVectorOffset({.Register = Register, + .RegisterSizeInBits = RegisterSize, + .MaskRegister = MaskRegister, + .MaskRegisterSizeInBits = MaskSize, + .Offset = Offset}); + } else if (Operation == "llvm_vector_register_mask") { + DwarfRegisterNumber SpillRegister; + DwarfRegisterNumber MaskRegister; + std::uint32_t SpillLaneSize = 0; + std::uint32_t MaskSize = 0; + if (parseCFIRegister(Register) || Comma() || parseCFIRegister(SpillRegister) || Comma() || + parseCFIUnsigned(SpillLaneSize) || Comma() || parseCFIRegister(MaskRegister) || Comma() || + parseCFIUnsigned(MaskSize)) { + return true; + } + Instruction = + MachineCFIInstruction::llvmVectorRegisterMask({.Register = Register, + .SpillRegister = SpillRegister, + .SpillRegisterLaneSizeInBits = SpillLaneSize, + .MaskRegister = MaskRegister, + .MaskRegisterSizeInBits = MaskSize}); + } else if (Operation == "escape") { + std::vector Bytes; + while (true) { + std::uint64_t Byte = 0; + if (!at(MITokenKind::HexLiteral) || parseUnsigned(token(), Byte) || + Byte > std::numeric_limits::max()) { + return fail("CFI escape element must be an 8-bit hexadecimal literal"); + } + Bytes.push_back(static_cast(Byte)); + advance(); + if (!at(MITokenKind::Comma) || !nextIs(MITokenKind::HexLiteral)) + break; + advance(); + } + auto Created = MachineCFIInstruction::escape(std::move(Bytes)); + if (!Created) + return importError(Begin, Created.error()); + Instruction = std::move(*Created); + } else { + return fail(Begin, "unsupported CFI operation '" + Operation + "'"); + } + + auto Index = Function.cfiInfo().addInstruction(std::move(*Instruction)); + if (!Index) + return importError(Begin, Index.error()); + Result = ParsedOperand{ + MachineOperand::cfiIndex(*Index), + std::nullopt, + {Begin.range().Begin, token().range().Begin}, + }; + return false; +} + +bool MIParser::Impl::parseMemoryBase(MemoryBase &Result, std::int64_t &Offset) { + const MIToken BaseToken = token(); + switch (BaseToken.kind()) { + case MITokenKind::StackObject: + case MITokenKind::FixedStackObject: { + const auto Index = frameIndexFor(BaseToken, BaseToken.kind() == MITokenKind::FixedStackObject); + if (!Index) + return true; + Result = MemoryBase::frameIndex(*Index); + advance(); + break; + } + case MITokenKind::ConstantPoolItem: { + const auto Index = constantPoolIndexFor(BaseToken); + if (!Index) + return true; + Result = MemoryBase::constantPool(*Index); + advance(); + break; + } + case MITokenKind::JumpTableIndex: { + const auto Index = jumpTableIndexFor(BaseToken); + if (!Index) + return true; + Result = MemoryBase::jumpTable(*Index); + advance(); + break; + } + case MITokenKind::GlobalValue: + case MITokenKind::NamedGlobalValue: + Result = MemoryBase::globalSymbol(symbolName(BaseToken)); + advance(); + break; + case MITokenKind::ExternalSymbol: + Result = MemoryBase::externalSymbol(symbolName(BaseToken)); + advance(); + break; + case MITokenKind::IRValue: + case MITokenKind::NamedIRValue: + case MITokenKind::QuotedIRValue: + Result = MemoryBase::irValue(symbolName(BaseToken)); + advance(); + break; + case MITokenKind::Keyword: + if (BaseToken.isKeyword("unknown-address")) { + Result = MemoryBase(); + advance(); + } else if (BaseToken.isKeyword("stack")) { + Result = MemoryBase::stack(); + advance(); + } else if (BaseToken.isKeyword("got")) { + Result = MemoryBase::got(); + advance(); + } else if (BaseToken.isKeyword("constant-pool")) { + Result = MemoryBase::constantPoolPseudo(); + advance(); + } else if (BaseToken.isKeyword("jump-table")) { + Result = MemoryBase::jumpTablePseudo(); + advance(); + } else if (BaseToken.isKeyword("call-entry")) { + advance(); + if (at(MITokenKind::GlobalValue) || at(MITokenKind::NamedGlobalValue)) { + Result = MemoryBase::callEntryGlobal(symbolName(token())); + } else if (at(MITokenKind::ExternalSymbol)) { + Result = MemoryBase::callEntryExternal(symbolName(token())); + } else { + return fail("call-entry memory base requires a global or external symbol"); + } + advance(); + } else if (BaseToken.isKeyword("custom")) { + advance(); + if (!at(MITokenKind::Identifier) && !at(MITokenKind::StringConstant)) + return fail("custom memory base requires a target spelling"); + Result = MemoryBase::custom(std::string(token().stringValue())); + advance(); + } else { + return fail(BaseToken, "unsupported machine memory base"); + } + break; + default: + return fail(BaseToken, "expected a machine memory base"); + } + return parseOptionalOffset(Offset); +} + +bool MIParser::Impl::parseMemoryOperand(const MachineMemOperand *&Result) { + const MIToken Begin = token(); + if (expect(MITokenKind::LeftParen, "'(' before a machine memory operand")) + return true; + + MachineMemOperandDesc Description; + std::unordered_set SeenFlags; + while (token().isMemoryOperandFlag()) { + const std::string Name(token().stringValue()); + if (!SeenFlags.insert(Name).second) + return fail("duplicate machine memory operand flag '" + Name + "'"); + if (atKeyword("volatile")) + Description.Accesses.set(MemoryAccessFlag::Volatile); + else if (atKeyword("non-temporal")) + Description.Accesses.set(MemoryAccessFlag::NonTemporal); + else if (atKeyword("dereferenceable")) + Description.Accesses.set(MemoryAccessFlag::Dereferenceable); + else if (atKeyword("invariant")) + Description.Accesses.set(MemoryAccessFlag::Invariant); + else { + const auto Flag = Target.mirText().machineMemOperandFlag(token().stringValue()); + if (!Flag) + return fail("unknown target machine memory operand flag '" + Name + "'"); + if ((Description.TargetFlags & *Flag) != 0) + return fail("overlapping target machine memory operand flag '" + Name + "'"); + Description.TargetFlags |= *Flag; + } + advance(); + } + + if (!at(MITokenKind::Identifier) || + (token().stringValue() != "load" && token().stringValue() != "store")) { + return fail("expected load or store in a machine memory operand"); + } + if (token().stringValue() == "load") + Description.Accesses.set(MemoryAccessFlag::Load); + else + Description.Accesses.set(MemoryAccessFlag::Store); + advance(); + if (at(MITokenKind::Identifier) && token().stringValue() == "store") { + if (Description.Accesses.has(MemoryAccessFlag::Store)) + return fail("duplicate store memory operation"); + Description.Accesses.set(MemoryAccessFlag::Store); + advance(); + } + + if (at(MITokenKind::Identifier) && token().stringValue() == "syncscope") { + advance(); + if (expect(MITokenKind::LeftParen, "'(' after syncscope")) + return true; + if (!at(MITokenKind::StringConstant)) + return fail("syncscope requires a quoted scope name"); + const std::string_view Name = token().stringValue(); + const auto Scope = std::ranges::find_if( + Context.SyncScopes, [Name](const MISyncScopeSlot &Slot) { return Slot.Name == Name; }); + if (Scope == Context.SyncScopes.end()) + return fail("unknown synchronization scope '" + std::string(Name) + "'"); + Description.SyncScope = Scope->ID; + advance(); + if (expect(MITokenKind::RightParen, "')' after syncscope")) + return true; + } + + std::size_t OrderingCount = 0; + while (at(MITokenKind::Identifier)) { + const auto Ordering = atomicOrdering(token().stringValue()); + if (!Ordering) + break; + if (OrderingCount == 0) + Description.SuccessOrdering = *Ordering; + else if (OrderingCount == 1) + Description.FailureOrdering = *Ordering; + else + return fail("machine memory operand has more than two atomic orderings"); + ++OrderingCount; + advance(); + } + const bool IsLoad = Description.Accesses.has(MemoryAccessFlag::Load); + const bool IsStore = Description.Accesses.has(MemoryAccessFlag::Store); + if (OrderingCount == 1) + Description.AtomicKind = IsLoad && IsStore + ? AtomicOperation::ReadModifyWrite + : (IsLoad ? AtomicOperation::Load : AtomicOperation::Store); + else if (OrderingCount == 2) + Description.AtomicKind = AtomicOperation::CompareExchange; + + std::uint64_t MinimumBytes = 0; + if (at(MITokenKind::IntegerLiteral)) { + if (parseUnsigned(token(), MinimumBytes) || MinimumBytes == 0) + return fail("machine memory operand size must be a nonzero byte count"); + auto Size = MemorySize::fixed(MinimumBytes); + if (!Size) + return importError(token(), Size.error()); + Description.Size = *Size; + advance(); + } else if (atKeyword("unknown-size")) { + advance(); + } else if (consume(MITokenKind::LeftParen)) { + LLT Type; + if (parseLowLevelType(Type)) + return true; + if (expect(MITokenKind::RightParen, "')' after the memory low-level type")) + return true; + const auto MinimumBits = minimumTypeSizeInBits(Type); + if (!MinimumBits || *MinimumBits == 0) + return fail(Begin, "memory low-level type has no representable size"); + MinimumBytes = (*MinimumBits + 7U) / 8U; + auto Size = Type.isScalableVector() ? MemorySize::scalable(MinimumBytes) + : MemorySize::fixed(MinimumBytes); + if (!Size) + return importError(Begin, Size.error()); + Description.Size = *Size; + } else { + return fail("expected a memory size, unknown-size, or memory low-level type"); + } + + if (MinimumBytes != 0) { + if (MinimumBytes > (std::uint64_t{1} << 63U)) + return fail(Begin, "machine memory operand size has no representable default alignment"); + auto DefaultAlignment = Alignment::create(std::bit_ceil(MinimumBytes)); + if (!DefaultAlignment) + return importError(Begin, DefaultAlignment.error()); + Description.Align = *DefaultAlignment; + } + + if (at(MITokenKind::Identifier)) { + const std::string_view ExpectedPreposition = + IsLoad && IsStore ? "on" : (IsLoad ? "from" : "into"); + if (token().stringValue() != ExpectedPreposition) { + return fail("expected '" + std::string(ExpectedPreposition) + + "' before the machine memory base"); + } + advance(); + if (parseMemoryBase(Description.Base, Description.Offset)) + return true; + } + + std::unordered_set SeenOptions; + while (consume(MITokenKind::Comma)) { + const std::string Name(token().spelling()); + if (!SeenOptions.insert(Name).second) + return fail("duplicate machine memory operand option '" + Name + "'"); + if (atKeyword("align")) { + if (parseAlignment(Description.Align)) + return true; + } else if (atKeyword("basealign")) { + Alignment BaseAlignment; + if (parseAlignment(BaseAlignment)) + return true; + Description.BaseAlign = BaseAlignment; + } else if (atKeyword("addrspace")) { + advance(); + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned32(token(), Description.AddressSpace) || + Description.AddressSpace > LLT::MaxAddressSpace) { + return fail("invalid machine memory operand address space"); + } + advance(); + } else if (at(MITokenKind::MetadataKeyword)) { + const std::string MetadataKind(token().stringValue()); + advance(); + MachineMetadataReference Reference; + if (parseMetadataReference(Reference)) + return true; + if (MetadataKind == "!tbaa") + Description.TBAA = Reference; + else if (MetadataKind == "!alias.scope") + Description.AliasScope = Reference; + else if (MetadataKind == "!noalias") + Description.NoAlias = Reference; + else if (MetadataKind == "!noalias.addrspace") + Description.NoAliasAddressSpace = Reference; + else if (MetadataKind == "!range") + Description.RangeMetadata = Reference; + else + return fail("unsupported machine memory operand metadata attachment"); + } else { + return fail("unknown machine memory operand option '" + Name + "'"); + } + } + if (expect(MITokenKind::RightParen, "')' after the machine memory operand")) + return true; + + auto Created = Function.createMemOperand(std::move(Description)); + if (!Created) + return importError(Begin, Created.error()); + Result = *Created; + return false; +} + +bool MIParser::Impl::parsePredicateOperand(ParsedOperand &Result, bool IsFloating) { + const MIToken Begin = token(); + advance(); + if (expect(MITokenKind::LeftParen, "'(' after predicate kind")) + return true; + if (!at(MITokenKind::Identifier)) + return fail("expected a predicate spelling"); + + Expected Operand = IsFloating ? [&]() -> Expected { + const auto Predicate = floatingPredicate(token().stringValue()); + if (!Predicate) { + return makeUnexpected(ErrorCode::ParseError, "invalid floating-point predicate"); + } + return MachineOperand::floatingPredicate(*Predicate); + }() + : [&]() -> Expected { + const auto Predicate = integerPredicate(token().stringValue()); + if (!Predicate) { + return makeUnexpected(ErrorCode::ParseError, "invalid integer predicate"); + } + return MachineOperand::integerPredicate(*Predicate); + }(); + if (!Operand) + return importError(token(), Operand.error()); + advance(); + if (expect(MITokenKind::RightParen, "')' after predicate")) + return true; + Result = ParsedOperand{ + std::move(*Operand), std::nullopt, {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseShuffleMaskOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + advance(); + if (expect(MITokenKind::LeftParen, "'(' after shufflemask")) + return true; + std::vector Elements; + while (!at(MITokenKind::RightParen)) { + if (atKeyword("undef")) { + Elements.push_back(ShuffleMaskOperand::Undef); + advance(); + } else { + std::int64_t Value = 0; + if (!at(MITokenKind::IntegerLiteral) || parseSigned64(token(), Value) || + Value < std::numeric_limits::min() || + Value > std::numeric_limits::max()) { + return fail("shuffle mask element must be a 32-bit integer or undef"); + } + Elements.push_back(static_cast(Value)); + advance(); + } + if (!consume(MITokenKind::Comma)) + break; + } + if (expect(MITokenKind::RightParen, "')' after shufflemask")) + return true; + auto Operand = MachineOperand::shuffleMask(std::move(Elements)); + if (!Operand) + return importError(Begin, Operand.error()); + Result = ParsedOperand{ + std::move(*Operand), std::nullopt, {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseDebugInstrRefOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + advance(); + if (expect(MITokenKind::LeftParen, "'(' after dbg-instr-ref")) + return true; + std::uint64_t Instruction = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned(token(), Instruction)) + return fail("invalid debug instruction number"); + advance(); + if (expect(MITokenKind::Comma, "',' in dbg-instr-ref")) + return true; + std::uint64_t OperandNumber = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned(token(), OperandNumber)) + return fail("invalid debug operand number"); + advance(); + if (expect(MITokenKind::RightParen, "')' after dbg-instr-ref")) + return true; + auto Operand = MachineOperand::debugInstrRef(Instruction, OperandNumber); + if (!Operand) + return importError(Begin, Operand.error()); + Result = ParsedOperand{ + std::move(*Operand), std::nullopt, {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseLaneMaskOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + advance(); + if (expect(MITokenKind::LeftParen, "'(' after lanemask")) + return true; + std::uint64_t Value = 0; + if (parseUnsigned(token(), Value)) + return fail("invalid 64-bit lane mask"); + advance(); + if (expect(MITokenKind::RightParen, "')' after lanemask")) + return true; + Result = ParsedOperand{MachineOperand::laneMask(LaneMask::fromRaw(Value)), + std::nullopt, + {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseIntrinsicOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + advance(); + if (expect(MITokenKind::LeftParen, "'(' after intrinsic")) + return true; + if (!at(MITokenKind::NamedGlobalValue)) + return fail("expected a named intrinsic"); + const auto ID = Target.mirText().intrinsic(token().stringValue()); + if (!ID) + return fail("unknown intrinsic '" + std::string(token().stringValue()) + "'"); + advance(); + if (expect(MITokenKind::RightParen, "')' after intrinsic")) + return true; + auto Operand = MachineOperand::intrinsic(*ID); + if (!Operand) + return importError(Begin, Operand.error()); + Result = ParsedOperand{ + std::move(*Operand), std::nullopt, {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseTargetIndexOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + advance(); + if (expect(MITokenKind::LeftParen, "'(' after target-index")) + return true; + if (!at(MITokenKind::Identifier)) + return fail("expected a target index name"); + const auto Index = Target.mirText().targetIndex(token().stringValue()); + if (!Index) + return fail("unknown target index '" + std::string(token().stringValue()) + "'"); + advance(); + if (expect(MITokenKind::RightParen, "')' after target index")) + return true; + std::int64_t Offset = 0; + if (parseOptionalOffset(Offset)) + return true; + Result = ParsedOperand{MachineOperand::targetIndex(*Index, Offset), + std::nullopt, + {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseCustomMaskOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + advance(); + if (expect(MITokenKind::LeftParen, "'(' after CustomRegMask")) + return true; + std::uint32_t MaximumRegister = 0; + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) + MaximumRegister = std::max(MaximumRegister, Register.Reg.number()); + std::vector Words(MaximumRegister / 64U + 1U, 0); + if (!at(MITokenKind::RightParen)) { + do { + Register Reg; + if (!at(MITokenKind::NamedRegister) || parseRegister(Reg) || !Reg.isPhysical()) + return fail("CustomRegMask requires physical registers"); + const auto Physical = Reg.physicalRegister(); + if (!Physical) + return fail("CustomRegMask requires physical registers"); + const std::uint32_t Number = Physical->number(); + Words[Number / 64U] |= std::uint64_t{1} << (Number % 64U); + } while (consume(MITokenKind::Comma)); + } + if (expect(MITokenKind::RightParen, "')' after CustomRegMask")) + return true; + auto Operand = + MachineOperand::registerMask(std::make_shared(std::move(Words))); + if (!Operand) + return importError(Begin, Operand.error()); + Result = ParsedOperand{ + std::move(*Operand), std::nullopt, {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseLiveOutMaskOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + advance(); + if (expect(MITokenKind::LeftParen, "'(' after liveout")) + return true; + std::uint32_t MaximumRegister = 0; + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) + MaximumRegister = std::max(MaximumRegister, Register.Reg.number()); + std::vector Words(MaximumRegister / 64U + 1U, 0); + do { + Register Reg; + if (!at(MITokenKind::NamedRegister) || parseRegister(Reg) || !Reg.isPhysical()) + return fail("liveout requires physical registers"); + const auto Physical = Reg.physicalRegister(); + if (!Physical) + return fail("liveout requires physical registers"); + const std::uint32_t Number = Physical->number(); + Words[Number / 64U] |= std::uint64_t{1} << (Number % 64U); + } while (consume(MITokenKind::Comma)); + if (expect(MITokenKind::RightParen, "')' after liveout")) + return true; + auto Operand = + MachineOperand::liveOutRegisterMask(std::make_shared(std::move(Words))); + if (!Operand) + return importError(Begin, Operand.error()); + Result = ParsedOperand{ + std::move(*Operand), std::nullopt, {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseBlockAddressOperand(ParsedOperand &Result) { + const MIToken Begin = token(); + advance(); + if (expect(MITokenKind::LeftParen, "'(' after blockaddress")) + return true; + if (!at(MITokenKind::GlobalValue) && !at(MITokenKind::NamedGlobalValue)) + return fail("blockaddress requires a function reference"); + const std::string FunctionName = symbolName(token()); + advance(); + if (expect(MITokenKind::Comma, "',' in blockaddress")) + return true; + if (!at(MITokenKind::IRBlock) && !at(MITokenKind::NamedIRBlock)) + return fail("blockaddress requires an IR block reference"); + const std::string BlockName = symbolName(token()); + advance(); + if (expect(MITokenKind::RightParen, "')' after blockaddress")) + return true; + std::int64_t Offset = 0; + if (parseOptionalOffset(Offset)) + return true; + auto Operand = MachineOperand::blockAddress(FunctionName, BlockName, Offset); + if (!Operand) + return importError(Begin, Operand.error()); + Result = ParsedOperand{ + std::move(*Operand), std::nullopt, {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseOperand(bool IsDef, ParsedOperand &Result) { + const MIToken Begin = token(); + if (token().isRegister() || token().isRegisterFlag()) + return parseRegisterOperand(IsDef, Result); + + std::uint32_t TargetFlags = 0; + if (parseTargetFlags(TargetFlags)) + return true; + const MIToken OperandToken = token(); + if (isFloatingSemanticsKeyword(OperandToken)) { + if (parseFloatingImmediateOperand(Result)) + return true; + Result.Operand.setTargetFlags(TargetFlags); + return false; + } + if (OperandToken.kind() == MITokenKind::Exclaim || + (OperandToken.kind() == MITokenKind::MetadataKeyword && + OperandToken.isMetadataKeyword("!DIExpression"))) { + if (parseMetadataOperand(Result)) + return true; + Result.Operand.setTargetFlags(TargetFlags); + return false; + } + if (isCFIOperationToken(OperandToken)) { + if (parseCFIOperand(Result)) + return true; + Result.Operand.setTargetFlags(TargetFlags); + return false; + } + MachineOperand Operand = MachineOperand::immediate(0); + bool HasOperand = true; + + switch (OperandToken.kind()) { + case MITokenKind::IntegerLiteral: { + std::int64_t Value = 0; + if (parseSigned64(OperandToken, Value)) + return fail("integer literal is too large for a machine immediate"); + Operand = MachineOperand::immediate(Value, TargetFlags); + advance(); + break; + } + case MITokenKind::MachineBasicBlock: { + MachineBasicBlock *Block = blockFor(OperandToken); + if (Block == nullptr) + return true; + Operand = MachineOperand::basicBlock(*Block, TargetFlags); + advance(); + break; + } + case MITokenKind::StackObject: + case MITokenKind::FixedStackObject: { + const bool Fixed = OperandToken.kind() == MITokenKind::FixedStackObject; + const auto Index = frameIndexFor(OperandToken, Fixed); + if (!Index) + return true; + advance(); + std::int64_t Offset = 0; + if (parseOptionalOffset(Offset)) + return true; + Operand = MachineOperand::frameIndex(*Index, Offset, TargetFlags); + break; + } + case MITokenKind::ConstantPoolItem: { + const auto Index = constantPoolIndexFor(OperandToken); + if (!Index) + return true; + advance(); + std::int64_t Offset = 0; + if (parseOptionalOffset(Offset)) + return true; + Operand = MachineOperand::constantPool(*Index, Offset, TargetFlags); + break; + } + case MITokenKind::JumpTableIndex: { + const auto Index = jumpTableIndexFor(OperandToken); + if (!Index) + return true; + Operand = MachineOperand::jumpTable(*Index, TargetFlags); + advance(); + break; + } + case MITokenKind::NamedGlobalValue: + case MITokenKind::GlobalValue: { + const std::string Name = symbolName(OperandToken); + advance(); + std::int64_t Offset = 0; + if (parseOptionalOffset(Offset)) + return true; + auto Created = MachineOperand::globalSymbol(Name, Offset, TargetFlags); + if (!Created) + return importError(OperandToken, Created.error()); + Operand = std::move(*Created); + break; + } + case MITokenKind::ExternalSymbol: { + const std::string Name = symbolName(OperandToken); + advance(); + std::int64_t Offset = 0; + if (parseOptionalOffset(Offset)) + return true; + auto Created = MachineOperand::externalSymbol(Name, Offset, TargetFlags); + if (!Created) + return importError(OperandToken, Created.error()); + Operand = std::move(*Created); + break; + } + case MITokenKind::MCSymbol: { + const std::string Name = symbolName(OperandToken); + advance(); + std::int64_t Offset = 0; + if (parseOptionalOffset(Offset)) + return true; + auto Created = MachineOperand::mcSymbol(Name, Offset, TargetFlags); + if (!Created) + return importError(OperandToken, Created.error()); + Operand = std::move(*Created); + break; + } + case MITokenKind::SubRegisterIndex: { + const SubRegIndexDesc *Description = Target.registers().subRegIndex(OperandToken.stringValue()); + if (Description == nullptr) + return fail("unknown subregister index '" + std::string(OperandToken.stringValue()) + "'"); + Operand = + MachineOperand::immediate(static_cast(Description->ID.value()), TargetFlags); + advance(); + break; + } + case MITokenKind::Identifier: { + if (const auto Mask = Target.mirText().registerMask(OperandToken.stringValue())) { + auto Created = MachineOperand::registerMask(Mask, TargetFlags); + if (!Created) + return importError(OperandToken, Created.error()); + Operand = std::move(*Created); + advance(); + } else if (OperandToken.stringValue() == "CustomRegMask") { + if (TargetFlags != 0) + return fail("custom register masks cannot have target flags"); + return parseCustomMaskOperand(Result); + } else if (OperandToken.stringValue().starts_with('i')) { + if (parseTypedIntegerOperand(Result)) + return true; + Result.Operand.setTargetFlags(TargetFlags); + return false; + } else { + return fail("unknown named machine operand '" + std::string(OperandToken.stringValue()) + + "'"); + } + break; + } + case MITokenKind::Keyword: + HasOperand = false; + break; + default: + return fail("expected a machine operand"); + } + + if (!HasOperand) { + bool Failed = false; + if (OperandToken.isKeyword("intpred")) + Failed = parsePredicateOperand(Result, false); + else if (OperandToken.isKeyword("floatpred")) + Failed = parsePredicateOperand(Result, true); + else if (OperandToken.isKeyword("shufflemask")) + Failed = parseShuffleMaskOperand(Result); + else if (OperandToken.isKeyword("dbg-instr-ref")) + Failed = parseDebugInstrRefOperand(Result); + else if (OperandToken.isKeyword("lanemask")) + Failed = parseLaneMaskOperand(Result); + else if (OperandToken.isKeyword("intrinsic")) + Failed = parseIntrinsicOperand(Result); + else if (OperandToken.isKeyword("target-index")) + Failed = parseTargetIndexOperand(Result); + else if (OperandToken.isKeyword("liveout")) + Failed = parseLiveOutMaskOperand(Result); + else if (OperandToken.isKeyword("blockaddress")) + Failed = parseBlockAddressOperand(Result); + else + return fail("unsupported machine operand spelling '" + std::string(OperandToken.spelling()) + + "'"); + if (!Failed) + Result.Operand.setTargetFlags(TargetFlags); + return Failed; + } + + Result = + ParsedOperand{std::move(Operand), std::nullopt, {Begin.range().Begin, token().range().Begin}}; + return false; +} + +bool MIParser::Impl::parseBlockLiveIns(MachineBasicBlock &Block) { + advance(); + if (expect(MITokenKind::Colon, "':' after liveins")) + return true; + if (token().isNewlineOrEnd()) + return false; + do { + if (!at(MITokenKind::NamedRegister)) + return fail("expected a physical register in liveins"); + Register Reg; + if (parseRegister(Reg) || !Reg.isPhysical()) + return true; + const auto Physical = Reg.physicalRegister(); + if (!Physical) + return fail("expected a physical register in liveins"); + LaneMask Lanes = LaneMask::all(); + if (consume(MITokenKind::Colon)) { + std::uint64_t Raw = 0; + if (parseUnsigned(token(), Raw)) + return fail("invalid live-in lane mask"); + Lanes = LaneMask::fromRaw(Raw); + advance(); + } + auto Added = Block.addLiveIn(*Physical, Lanes); + if (!Added) + return importError(token(), Added.error()); + } while (consume(MITokenKind::Comma)); + return false; +} + +bool MIParser::Impl::parseBlockSuccessors(MachineBasicBlock &Block) { + advance(); + if (expect(MITokenKind::Colon, "':' after successors")) + return true; + ExplicitSuccessorBlocks.insert(&Block); + if (token().isNewlineOrEnd()) + return false; + do { + if (!at(MITokenKind::MachineBasicBlock)) + return fail("expected a machine basic block successor"); + MachineBasicBlock *Successor = blockFor(token()); + if (Successor == nullptr) + return true; + advance(); + BranchProbability Probability = BranchProbability::zero(); + if (consume(MITokenKind::LeftParen)) { + std::uint32_t Weight = 0; + if (parseUnsigned32(token(), Weight)) + return fail("invalid successor probability weight"); + Probability = BranchProbability::fromRaw(Weight); + advance(); + if (expect(MITokenKind::RightParen, "')' after successor weight")) + return true; + } + auto Added = Function.cfgUpdater().addSuccessor(Block, *Successor, Probability); + if (!Added) + return importError(token(), Added.error()); + } while (consume(MITokenKind::Comma)); + return false; +} + +bool MIParser::Impl::parseInstruction(MachineBasicBlock &Block, bool InBundle, + MachineInstr *PreviousInstruction, MachineInstr *&Result) { + if (ParsedInstructionCount >= Options.MaximumInstructions) + return fail("machine instruction count exceeds parser limit"); + + std::vector Operands; + while (token().isRegister() || token().isRegisterFlag()) { + ParsedOperand Operand{MachineOperand::immediate(0), std::nullopt, {}}; + if (parseRegisterOperand(true, Operand)) + return true; + Operands.push_back(std::move(Operand)); + if (!consume(MITokenKind::Comma)) + break; + } + if (!Operands.empty() && expect(MITokenKind::Equal, "'=' after register definitions")) + return true; + + MachineInstrFlags Flags; + while (isInstructionFlag(token())) { + const auto Flag = instructionFlag(token().stringValue()); + if (!Flag) + return fail("unknown instruction flag"); + if (Flags.has(*Flag)) + return fail("duplicate instruction flag '" + std::string(token().stringValue()) + "'"); + Flags.set(*Flag); + advance(); + } + if (!at(MITokenKind::Identifier)) + return fail("expected a machine instruction name"); + const MIToken OpcodeToken = token(); + const InstructionDescriptor *Descriptor = + Target.instructions().descriptor(OpcodeToken.stringValue()); + if (Descriptor == nullptr) + return fail("unknown machine instruction '" + std::string(OpcodeToken.stringValue()) + "'"); + advance(); + + while (!token().isNewlineOrEnd() && !at(MITokenKind::DoubleColon) && + !at(MITokenKind::LeftBrace) && !atKeyword("debug-instr-number") && + !atKeyword("debug-location") && !atKeyword("pre-instr-symbol") && + !atKeyword("post-instr-symbol") && !atKeyword("heap-alloc-marker") && + !atKeyword("pcsections") && !atKeyword("mmra") && !atKeyword("cfi-type") && + !atKeyword("deactivation-symbol")) { + if (Operands.size() >= Options.MaximumOperandsPerInstruction) + return fail("instruction operand count exceeds parser limit"); + ParsedOperand Operand{MachineOperand::immediate(0), std::nullopt, {}}; + if (parseOperand(false, Operand)) + return true; + Operands.push_back(std::move(Operand)); + if (token().isNewlineOrEnd() || at(MITokenKind::DoubleColon) || at(MITokenKind::LeftBrace) || + atKeyword("debug-instr-number") || atKeyword("debug-location")) + break; + if (expect(MITokenKind::Comma, "',' before the next machine operand")) + return true; + } + + std::uint32_t DebugNumber = 0; + std::optional DebugLocation; + std::optional PreInstrSymbol; + std::optional PostInstrSymbol; + std::optional HeapAllocMarker; + std::optional PCSections; + std::optional MMRA; + std::optional CFIType; + std::optional DeactivationSymbol; + std::unordered_set SeenAttachments; + while (atKeyword("debug-instr-number") || atKeyword("debug-location") || + atKeyword("pre-instr-symbol") || atKeyword("post-instr-symbol") || + atKeyword("heap-alloc-marker") || atKeyword("pcsections") || atKeyword("mmra") || + atKeyword("cfi-type") || atKeyword("deactivation-symbol")) { + const std::string Name(token().stringValue()); + if (!SeenAttachments.insert(Name).second) + return fail("duplicate instruction attachment '" + Name + "'"); + advance(); + if (Name == "debug-instr-number") { + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned32(token(), DebugNumber) || + DebugNumber == 0) { + return fail("invalid debug instruction number"); + } + advance(); + } else if (Name == "debug-location") { + if (at(MITokenKind::MetadataKeyword) && token().isMetadataKeyword("!DILocation")) { + std::vector InlineChain; + std::optional TerminalInlinedAt; + if (parseInlineDILocation(InlineChain, TerminalInlinedAt)) + return true; + auto Location = MachineDILocation::create(std::move(InlineChain), TerminalInlinedAt); + if (!Location) + return importError(OpcodeToken, Location.error()); + DebugLocation = MachineDebugLocation::inlineLocation(std::move(*Location)); + } else { + MachineMetadataReference Reference; + if (parseMetadataReference(Reference)) + return true; + auto Created = MachineDebugLocation::reference(Reference); + if (!Created) + return importError(OpcodeToken, Created.error()); + DebugLocation = std::move(*Created); + } + } else if (Name == "pre-instr-symbol" || Name == "post-instr-symbol") { + if (!at(MITokenKind::MCSymbol)) + return fail("expected an MC symbol after '" + Name + "'"); + if (Name == "pre-instr-symbol") + PreInstrSymbol = symbolName(token()); + else + PostInstrSymbol = symbolName(token()); + advance(); + } else if (Name == "heap-alloc-marker" || Name == "pcsections" || Name == "mmra") { + MachineMetadataReference Reference; + if (parseMetadataReference(Reference)) + return true; + if (Name == "heap-alloc-marker") + HeapAllocMarker = Reference; + else if (Name == "pcsections") + PCSections = Reference; + else + MMRA = Reference; + } else if (Name == "cfi-type") { + std::uint32_t Type = 0; + if (!at(MITokenKind::IntegerLiteral) || parseUnsigned32(token(), Type) || Type == 0) + return fail("invalid nonzero CFI type"); + CFIType = Type; + advance(); + } else { + if (!at(MITokenKind::GlobalValue) && !at(MITokenKind::NamedGlobalValue)) + return fail("expected a global value after 'deactivation-symbol'"); + DeactivationSymbol = symbolName(token()); + advance(); + } + static_cast(consume(MITokenKind::Comma)); + } + std::vector MemOperands; + if (consume(MITokenKind::DoubleColon)) { + while (!token().isNewlineOrEnd() && !at(MITokenKind::LeftBrace)) { + if (MemOperands.size() >= Options.MaximumMemoryOperandsPerInstruction) + return fail("machine memory operand count exceeds parser limit"); + const MachineMemOperand *MemOperand = nullptr; + if (parseMemoryOperand(MemOperand)) + return true; + MemOperands.push_back(MemOperand); + if (token().isNewlineOrEnd() || at(MITokenKind::LeftBrace)) + break; + if (expect(MITokenKind::Comma, "',' before the next machine memory operand")) + return true; + } + } + + auto Created = Function.createInstruction(Descriptor->InstructionOpcode); + if (!Created) + return importError(OpcodeToken, Created.error()); + MachineInstr *Instruction = *Created; + Instruction->setFlags(Flags); + for (ParsedOperand &Parsed : Operands) { + auto Added = Instruction->addOperand(std::move(Parsed.Operand)); + if (!Added) + return importError(OpcodeToken, Added.error()); + } + for (std::size_t Index = 0; Index < Operands.size(); ++Index) { + if (!Operands[Index].TiedDef) + continue; + if (*Operands[Index].TiedDef >= Operands.size()) + return fail(OpcodeToken, "tied-def operand index is out of range"); + auto Tied = Instruction->tieOperands(*Operands[Index].TiedDef, Index); + if (!Tied) + return importError(OpcodeToken, Tied.error()); + } + for (const MachineMemOperand *MemOperand : MemOperands) { + auto Added = Instruction->addMemOperand(*MemOperand); + if (!Added) + return importError(OpcodeToken, Added.error()); + } + if (DebugNumber != 0) { + auto SetNumber = Instruction->setDebugInstrNumber(DebugNumber); + if (!SetNumber) + return importError(OpcodeToken, SetNumber.error()); + } + if (DebugLocation) { + auto SetLocation = Instruction->setDebugLocation(std::move(*DebugLocation)); + if (!SetLocation) + return importError(OpcodeToken, SetLocation.error()); + } + if (PreInstrSymbol) { + auto SetSymbol = Instruction->setPreInstrSymbol(std::move(*PreInstrSymbol)); + if (!SetSymbol) + return importError(OpcodeToken, SetSymbol.error()); + } + if (PostInstrSymbol) { + auto SetSymbol = Instruction->setPostInstrSymbol(std::move(*PostInstrSymbol)); + if (!SetSymbol) + return importError(OpcodeToken, SetSymbol.error()); + } + if (HeapAllocMarker) { + auto SetMarker = Instruction->setHeapAllocMarker(*HeapAllocMarker); + if (!SetMarker) + return importError(OpcodeToken, SetMarker.error()); + } + if (PCSections) { + auto SetSections = Instruction->setPCSections(*PCSections); + if (!SetSections) + return importError(OpcodeToken, SetSections.error()); + } + if (MMRA) { + auto SetMMRA = Instruction->setMMRA(*MMRA); + if (!SetMMRA) + return importError(OpcodeToken, SetMMRA.error()); + } + if (CFIType) { + auto SetType = Instruction->setCFIType(*CFIType); + if (!SetType) + return importError(OpcodeToken, SetType.error()); + } + if (DeactivationSymbol) { + auto SetSymbol = Instruction->setDeactivationSymbol(std::move(*DeactivationSymbol)); + if (!SetSymbol) + return importError(OpcodeToken, SetSymbol.error()); + } + if (InBundle) { + Flags.set(MachineInstrFlag::BundledWithPred); + Instruction->setFlags(Flags); + if (PreviousInstruction != nullptr) { + MachineInstrFlags PreviousFlags = PreviousInstruction->flags(); + PreviousFlags.set(MachineInstrFlag::BundledWithSucc); + PreviousInstruction->setFlags(PreviousFlags); + } + } + auto Appended = Block.appendInstruction(*Instruction); + if (!Appended) + return importError(OpcodeToken, Appended.error()); + + ++ParsedInstructionCount; + Result = Instruction; + return false; +} + +bool MIParser::Impl::parseSecondPass() { + Position = 0; + while (consume(MITokenKind::Newline)) { + } + while (!at(MITokenKind::EndOfFile)) { + if (!at(MITokenKind::MachineBasicBlockLabel)) + return fail("expected a machine basic block definition"); + std::uint32_t ID = 0; + if (parseBlockDefinition(false, ID)) + return true; + MachineBasicBlock *Block = Blocks.at(ID); + + while (consume(MITokenKind::Newline)) { + } + while (atKeyword("liveins") || atKeyword("successors")) { + if ((atKeyword("liveins") && parseBlockLiveIns(*Block)) || + (atKeyword("successors") && parseBlockSuccessors(*Block))) { + return true; + } + if (!token().isNewlineOrEnd()) + return fail("expected a line break after the block list"); + while (consume(MITokenKind::Newline)) { + } + } + + bool InBundle = false; + MachineInstr *PreviousInstruction = nullptr; + while (!at(MITokenKind::MachineBasicBlockLabel) && !at(MITokenKind::EndOfFile)) { + if (consume(MITokenKind::Newline)) + continue; + if (consume(MITokenKind::RightBrace)) { + if (!InBundle) + return fail("closing brace without an active instruction bundle"); + InBundle = false; + continue; + } + + MachineInstr *Instruction = nullptr; + if (parseInstruction(*Block, InBundle, PreviousInstruction, Instruction)) + return true; + PreviousInstruction = Instruction; + if (consume(MITokenKind::LeftBrace)) { + if (InBundle) + return fail("nested instruction bundles are not allowed"); + MachineInstrFlags BundleFlags = Instruction->flags(); + BundleFlags.set(MachineInstrFlag::BundledWithSucc); + Instruction->setFlags(BundleFlags); + InBundle = true; + } + if (!token().isNewlineOrEnd() && !at(MITokenKind::RightBrace)) + return fail("expected a line break after the machine instruction"); + } + if (InBundle) + return fail("unterminated instruction bundle"); + } + return false; +} + +bool MIParser::Impl::inferSuccessors() { + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + if (ExplicitSuccessorBlocks.contains(Block)) + continue; + + bool BlocksFallthrough = true; + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = + Target.instructions().descriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return fail("instruction has no target descriptor while inferring successors"); + if (Descriptor->Flags.has(InstructionFlag::Branch)) { + for (const MachineOperand &Operand : Instruction->operands()) { + if (const BasicBlockOperand *TargetBlock = Operand.getIf()) { + auto Added = Function.cfgUpdater().addSuccessor(*Block, *TargetBlock->Block); + if (!Added) + return importError(token(), Added.error()); + } + } + } + if (Descriptor->Flags.has(InstructionFlag::Barrier)) + BlocksFallthrough = false; + } + if (BlocksFallthrough && Block->next() != nullptr) { + auto Added = Function.cfgUpdater().addSuccessor(*Block, *Block->next()); + if (!Added) + return importError(token(), Added.error()); + } + } + return false; +} + +Expected MIParser::Impl::parse() { + if (ParseAttempted) + return makeUnexpected(ErrorCode::InvalidArgument, "MI parser can only be run once"); + ParseAttempted = true; + if (Function.blockCount() != 0 || !Function.allInstructions().empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "MI parser requires a staging machine function with an empty body"); + } + if (tokenize()) + return failureResult(); + if (parseFirstPass() || parseSecondPass() || inferSuccessors()) + return failureResult(); + + Function.renumberBlocks(); + auto Verified = MachineVerifier::verify( + Function, Target, + MachineVerifierOptions{ + .Mode = MachineVerifierMode::Generic, .Stage = std::nullopt, .VerifyProperties = false}); + if (!Verified) { + static_cast(fail(token(), "parsed machine function failed verification: " + + std::string(Verified.error().message()))); + return failureResult(); + } + return {}; +} + +MIParser::MIParser(MachineFunction &Function, const TargetDescription &Target, + std::string SourceName, std::string SourceText, MIParserContext Context, + MIParserOptions Options) + : Implementation(std::make_unique(Function, Target, std::move(SourceName), + std::move(SourceText), std::move(Context), Options)) {} + +MIParser::MIParser(MIParser &&) noexcept = default; + +MIParser &MIParser::operator=(MIParser &&) noexcept = default; + +MIParser::~MIParser() = default; + +Expected MIParser::parse() { + return Implementation->parse(); +} + +const TextSource &MIParser::source() const noexcept { + return Implementation->source(); +} + +std::span MIParser::diagnostics() const noexcept { + return Implementation->diagnostics(); +} + +bool MIParser::failed() const noexcept { + return Implementation->failed(); +} + +} // namespace rcc::mir diff --git a/backend/lib/MIR/MIPrinter.cpp b/backend/lib/MIR/MIPrinter.cpp new file mode 100644 index 0000000..e3f504b --- /dev/null +++ b/backend/lib/MIR/MIPrinter.cpp @@ -0,0 +1,1464 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/MIR/MIPrinter.h" + +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFIInfo.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetMIRTextInfo.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc::mir { +namespace { + +[[nodiscard]] bool isBareNameCharacter(char Character) noexcept { + return (Character >= 'a' && Character <= 'z') || (Character >= 'A' && Character <= 'Z') || + (Character >= '0' && Character <= '9') || Character == '_' || Character == '-' || + Character == '.' || Character == '$'; +} + +[[nodiscard]] std::string quoteName(std::string_view Name) { + if (!Name.empty() && std::ranges::all_of(Name, isBareNameCharacter)) + return std::string(Name); + + constexpr std::string_view Hex = "0123456789ABCDEF"; + std::string Result; + Result.reserve(Name.size() + 2U); + Result.push_back('"'); + for (const char RawCharacter : Name) { + const auto Character = static_cast(RawCharacter); + if (Character >= 0x20U && Character <= 0x7EU && Character != '"' && Character != '\\') { + Result.push_back(static_cast(Character)); + continue; + } + Result.push_back('\\'); + Result.push_back(Hex[Character >> 4U]); + Result.push_back(Hex[Character & 0xFU]); + } + Result.push_back('"'); + return Result; +} + +[[nodiscard]] std::string hexadecimalWords(std::span Words, + std::uint32_t BitWidth) { + constexpr std::string_view Hex = "0123456789ABCDEF"; + const std::size_t DigitCount = (static_cast(BitWidth) + 3U) / 4U; + std::string Result(DigitCount, '0'); + for (std::size_t Digit = 0; Digit < DigitCount; ++Digit) { + const std::size_t BitOffset = Digit * 4U; + const std::uint64_t Nibble = (Words[BitOffset / 64U] >> (BitOffset % 64U)) & 0xFU; + Result[DigitCount - Digit - 1U] = Hex[Nibble]; + } + return Result; +} + +[[nodiscard]] std::string unsignedDecimal(std::span InputWords) { + std::vector Words(InputWords.begin(), InputWords.end()); + while (!Words.empty() && Words.back() == 0) + Words.pop_back(); + if (Words.empty()) + return "0"; + + std::string Reversed; + while (!Words.empty()) { + std::uint64_t Remainder = 0; + for (std::size_t Index = Words.size(); Index != 0; --Index) { + const unsigned __int128 Dividend = + (static_cast(Remainder) << 64U) | Words[Index - 1U]; + Words[Index - 1U] = static_cast(Dividend / 10U); + Remainder = static_cast(Dividend % 10U); + } + Reversed.push_back(static_cast('0' + Remainder)); + while (!Words.empty() && Words.back() == 0) + Words.pop_back(); + } + std::ranges::reverse(Reversed); + return Reversed; +} + +[[nodiscard]] std::string_view floatKeyword(FloatSemantics Semantics) noexcept { + switch (Semantics) { + case FloatSemantics::IEEEHalf: + return "half"; + case FloatSemantics::BFloat: + return "bfloat"; + case FloatSemantics::IEEESingle: + return "float"; + case FloatSemantics::IEEEDouble: + return "double"; + case FloatSemantics::IEEEQuad: + return "fp128"; + case FloatSemantics::PPCDoubleDouble: + case FloatSemantics::PPCDoubleDoubleLegacy: + return "ppc_fp128"; + case FloatSemantics::X87DoubleExtended: + return "x86_fp80"; + default: + return {}; + } +} + +[[nodiscard]] std::string_view integerPredicateName(IntegerPredicate Predicate) noexcept { + switch (Predicate) { + case IntegerPredicate::Equal: + return "eq"; + case IntegerPredicate::NotEqual: + return "ne"; + case IntegerPredicate::SignedGreaterThan: + return "sgt"; + case IntegerPredicate::SignedGreaterEqual: + return "sge"; + case IntegerPredicate::SignedLessThan: + return "slt"; + case IntegerPredicate::SignedLessEqual: + return "sle"; + case IntegerPredicate::UnsignedGreaterThan: + return "ugt"; + case IntegerPredicate::UnsignedGreaterEqual: + return "uge"; + case IntegerPredicate::UnsignedLessThan: + return "ult"; + case IntegerPredicate::UnsignedLessEqual: + return "ule"; + case IntegerPredicate::Count: + return {}; + } + return {}; +} + +[[nodiscard]] std::string_view floatingPredicateName(FloatingPredicate Predicate) noexcept { + switch (Predicate) { + case FloatingPredicate::AlwaysFalse: + return "false"; + case FloatingPredicate::OrderedEqual: + return "oeq"; + case FloatingPredicate::OrderedGreaterThan: + return "ogt"; + case FloatingPredicate::OrderedGreaterEqual: + return "oge"; + case FloatingPredicate::OrderedLessThan: + return "olt"; + case FloatingPredicate::OrderedLessEqual: + return "ole"; + case FloatingPredicate::OrderedNotEqual: + return "one"; + case FloatingPredicate::Ordered: + return "ord"; + case FloatingPredicate::Unordered: + return "uno"; + case FloatingPredicate::UnorderedEqual: + return "ueq"; + case FloatingPredicate::UnorderedGreaterThan: + return "ugt"; + case FloatingPredicate::UnorderedGreaterEqual: + return "uge"; + case FloatingPredicate::UnorderedLessThan: + return "ult"; + case FloatingPredicate::UnorderedLessEqual: + return "ule"; + case FloatingPredicate::UnorderedNotEqual: + return "une"; + case FloatingPredicate::AlwaysTrue: + return "true"; + case FloatingPredicate::Count: + return {}; + } + return {}; +} + +[[nodiscard]] std::string_view atomicOrderingName(AtomicOrdering Ordering) noexcept { + switch (Ordering) { + case AtomicOrdering::Unordered: + return "unordered"; + case AtomicOrdering::Monotonic: + return "monotonic"; + case AtomicOrdering::Acquire: + return "acquire"; + case AtomicOrdering::Release: + return "release"; + case AtomicOrdering::AcquireRelease: + return "acq_rel"; + case AtomicOrdering::SequentiallyConsistent: + return "seq_cst"; + case AtomicOrdering::NotAtomic: + return {}; + } + return {}; +} + +class BodyPrinter final { +public: + BodyPrinter(const MachineFunction &Function, const TargetDescription &Target, + const MIParserContext &Context, MIPrinterOptions Options) + : Function(Function), Target(Target), Context(Context), Options(Options) {} + + [[nodiscard]] Expected run(); + +private: + [[nodiscard]] Expected initialize(); + [[nodiscard]] Expected printBlock(const MachineBasicBlock &Block); + [[nodiscard]] Expected printInstruction(const MachineInstr &Instruction); + [[nodiscard]] Expected printOperand(const MachineOperand &Operand, bool IsExplicitDef); + [[nodiscard]] Expected printRegisterOperand(const MachineOperand &Operand, + bool IsExplicitDef); + [[nodiscard]] Expected printTargetFlags(std::uint32_t Flags); + [[nodiscard]] Expected printMetadataReference(MachineMetadataReference Reference); + [[nodiscard]] Expected printDILocation(const MachineDILocation &Location, + std::size_t FrameIndex); + [[nodiscard]] Expected printCFIInstruction(CFIInstructionIndex Index); + [[nodiscard]] Expected printMemoryOperand(const MachineMemOperand &Operand); + [[nodiscard]] Expected printMemoryBase(const MemoryBase &Base, std::int64_t Offset); + + [[nodiscard]] Expected blockID(const MachineBasicBlock &Block) const; + [[nodiscard]] Expected frameID(FrameIndex Index) const; + [[nodiscard]] Expected constantPoolID(ConstantPoolIndex Index) const; + [[nodiscard]] Expected jumpTableID(JumpTableIndex Index) const; + [[nodiscard]] Expected metadataID(MachineMetadataReference Reference) const; + [[nodiscard]] Expected appendPhysicalRegister(PhysicalRegister Register); + void appendBlockReference(const MachineBasicBlock &Block); + void appendOffset(std::int64_t Offset); + + const MachineFunction &Function; + const TargetDescription &Target; + const MIParserContext &Context; + MIPrinterOptions Options; + std::string Output; + std::unordered_map BlockIDs; +}; + +Expected BodyPrinter::initialize() { + std::uint64_t NextID = 0; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + if (NextID > std::numeric_limits::max()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine function has too many blocks to print"); + } + BlockIDs.emplace(Block, static_cast(NextID)); + ++NextID; + } + return {}; +} + +Expected BodyPrinter::blockID(const MachineBasicBlock &Block) const { + const auto Found = BlockIDs.find(&Block); + if (Found == BlockIDs.end()) + return makeUnexpected(ErrorCode::VerificationError, + "machine operand references an unlinked basic block"); + return Found->second; +} + +Expected BodyPrinter::frameID(FrameIndex Index) const { + const auto InStack = std::ranges::find_if( + Context.StackObjects, [Index](const MIFrameObjectSlot &Slot) { return Slot.Index == Index; }); + if (InStack != Context.StackObjects.end()) + return InStack->TextID; + const auto InFixed = + std::ranges::find_if(Context.FixedStackObjects, + [Index](const MIFrameObjectSlot &Slot) { return Slot.Index == Index; }); + if (InFixed != Context.FixedStackObjects.end()) + return InFixed->TextID; + return makeUnexpected(ErrorCode::VerificationError, "frame index has no MIR text slot"); +} + +Expected BodyPrinter::constantPoolID(ConstantPoolIndex Index) const { + const auto Found = + std::ranges::find_if(Context.ConstantPoolItems, + [Index](const MIConstantPoolSlot &Slot) { return Slot.Index == Index; }); + if (Found == Context.ConstantPoolItems.end()) { + return makeUnexpected(ErrorCode::VerificationError, "constant-pool index has no MIR text slot"); + } + return Found->TextID; +} + +Expected BodyPrinter::jumpTableID(JumpTableIndex Index) const { + const auto Found = std::ranges::find_if( + Context.JumpTables, [Index](const MIJumpTableSlot &Slot) { return Slot.Index == Index; }); + if (Found == Context.JumpTables.end()) + return makeUnexpected(ErrorCode::VerificationError, "jump-table index has no MIR text slot"); + return Found->TextID; +} + +Expected BodyPrinter::metadataID(MachineMetadataReference Reference) const { + const auto Found = + std::ranges::find_if(Context.Metadata, [Reference](const MIMetadataSlot &Slot) { + return Slot.Reference == Reference; + }); + if (Found != Context.Metadata.end()) + return Found->TextID; + if (Reference.scope() == MachineMetadataScope::MachineFunction) + return Reference.slot(); + return makeUnexpected(ErrorCode::VerificationError, + "embedded metadata reference has no MIR text slot"); +} + +Expected BodyPrinter::appendPhysicalRegister(PhysicalRegister Register) { + const auto Name = Target.registers().physicalRegisterMIRName(Register); + if (!Name) + return makeUnexpected(ErrorCode::VerificationError, "physical register has no MIR name"); + Output.push_back('$'); + Output.append(*Name); + return {}; +} + +void BodyPrinter::appendBlockReference(const MachineBasicBlock &Block) { + Output.append("%bb."); + Output.append(std::to_string(BlockIDs.at(&Block))); + const auto &Name = Block.attributes().name(); + if (Name) { + Output.push_back('.'); + Output.append(quoteName(*Name)); + } +} + +void BodyPrinter::appendOffset(std::int64_t Offset) { + if (Offset == 0) + return; + if (Offset > 0) { + Output.append(" + "); + Output.append(std::to_string(Offset)); + return; + } + Output.append(" - "); + const std::uint64_t Magnitude = Offset == std::numeric_limits::min() + ? std::uint64_t{1} << 63U + : static_cast(-Offset); + Output.append(std::to_string(Magnitude)); +} + +Expected BodyPrinter::printTargetFlags(std::uint32_t Flags) { + if (Flags == 0) + return {}; + auto Names = Target.mirText().operandFlagNames(Flags); + if (!Names) + return std::unexpected(Names.error()); + Output.append("target-flags("); + for (std::size_t Index = 0; Index < Names->size(); ++Index) { + if (Index != 0) + Output.append(", "); + Output.append((*Names)[Index]); + } + Output.append(") "); + return {}; +} + +Expected BodyPrinter::printMetadataReference(MachineMetadataReference Reference) { + auto ID = metadataID(Reference); + if (!ID) + return std::unexpected(ID.error()); + Output.push_back('!'); + Output.append(std::to_string(*ID)); + return {}; +} + +Expected BodyPrinter::printDILocation(const MachineDILocation &Location, + std::size_t FrameIndex) { + const auto Frames = Location.inlineChain(); + if (FrameIndex >= Frames.size()) { + return makeUnexpected(ErrorCode::VerificationError, + "inline DILocation has an invalid frame index"); + } + const MachineDILocationFrame &Frame = Frames[FrameIndex]; + Output.append("!DILocation(line: "); + Output.append(std::to_string(Frame.Line)); + if (Options.Mode == MIPrintMode::Complete || Frame.Column != 0) { + Output.append(", column: "); + Output.append(std::to_string(Frame.Column)); + } + Output.append(", scope: "); + if (auto Printed = printMetadataReference(Frame.Scope); !Printed) + return Printed; + if (FrameIndex + 1U < Frames.size()) { + Output.append(", inlinedAt: "); + if (auto Printed = printDILocation(Location, FrameIndex + 1U); !Printed) + return Printed; + } else if (Location.terminalInlinedAt()) { + Output.append(", inlinedAt: "); + if (auto Printed = printMetadataReference(*Location.terminalInlinedAt()); !Printed) { + return Printed; + } + } + if (Options.Mode == MIPrintMode::Complete || Frame.IsImplicitCode) { + Output.append(", isImplicitCode: "); + Output.append(Frame.IsImplicitCode ? "true" : "false"); + } + if (Options.Mode == MIPrintMode::Complete || Frame.AtomGroup != 0) { + Output.append(", atomGroup: "); + Output.append(std::to_string(Frame.AtomGroup)); + } + if (Options.Mode == MIPrintMode::Complete || Frame.AtomRank != 0) { + Output.append(", atomRank: "); + Output.append(std::to_string(Frame.AtomRank)); + } + Output.push_back(')'); + return {}; +} + +Expected BodyPrinter::printRegisterOperand(const MachineOperand &Operand, + bool IsExplicitDef) { + const RegisterOperandFlags Flags = Operand.registerFlags(); + if (Flags.has(RegisterOperandFlag::Implicit) && Flags.has(RegisterOperandFlag::Define)) { + Output.append("implicit-def "); + } else { + if (!IsExplicitDef && Flags.has(RegisterOperandFlag::Define)) + Output.append("def "); + if (Flags.has(RegisterOperandFlag::Implicit)) + Output.append("implicit "); + } + if (Flags.has(RegisterOperandFlag::Dead)) + Output.append("dead "); + if (Flags.has(RegisterOperandFlag::Kill)) + Output.append("killed "); + if (Flags.has(RegisterOperandFlag::Undef)) + Output.append("undef "); + if (Flags.has(RegisterOperandFlag::InternalRead)) + Output.append("internal "); + if (Flags.has(RegisterOperandFlag::EarlyClobber)) + Output.append("early-clobber "); + if (Flags.has(RegisterOperandFlag::Debug)) + Output.append("debug-use "); + if (Flags.has(RegisterOperandFlag::Renamable)) + Output.append("renamable "); + + const auto RegisterValue = Operand.registerValue(); + if (!RegisterValue) { + return makeUnexpected(ErrorCode::VerificationError, "register operand has no register value"); + } + const Register Reg = *RegisterValue; + if (Reg.isNoRegister()) { + Output.append("$noreg"); + } else if (Reg.isPhysical()) { + const auto Physical = Reg.physicalRegister(); + if (!Physical) { + return makeUnexpected(ErrorCode::VerificationError, + "physical register has no physical-register value"); + } + auto Printed = appendPhysicalRegister(*Physical); + if (!Printed) + return Printed; + } else { + const auto VirtualIndex = Reg.virtualIndex(); + if (!VirtualIndex) + return makeUnexpected(ErrorCode::VerificationError, "virtual register has no numeric index"); + Output.push_back('%'); + Output.append(std::to_string(*VirtualIndex)); + if (Operand.subReg().value() != 0) { + const SubRegIndexDesc *SubReg = Target.registers().subRegIndex(Operand.subReg()); + if (SubReg == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "virtual register has an unknown subregister"); + Output.push_back('.'); + Output.append(SubReg->Name); + } + + auto Info = Function.registerInfo().virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + const VirtualRegisterInfo &RegisterInfo = Info->get(); + if (RegisterInfo.RegClass) { + const auto Name = Target.registers().registerClassMIRName(*RegisterInfo.RegClass); + if (!Name) + return makeUnexpected(ErrorCode::VerificationError, + "virtual register class has no MIR name"); + Output.push_back(':'); + Output.append(*Name); + } else if (RegisterInfo.Bank) { + const auto Name = Target.registers().registerBankMIRName(*RegisterInfo.Bank); + if (!Name) + return makeUnexpected(ErrorCode::VerificationError, + "virtual register bank has no MIR name"); + Output.push_back(':'); + Output.append(*Name); + } else if (RegisterInfo.Type) { + Output.append(":_"); + } + if (RegisterInfo.Type) { + Output.push_back('('); + Output.append(RegisterInfo.Type->toString()); + Output.push_back(')'); + } + } + + if (Operand.tiedOperandIndex() && Operand.isUse()) { + Output.append("(tied-def "); + Output.append(std::to_string(*Operand.tiedOperandIndex())); + Output.push_back(')'); + } + return {}; +} + +Expected BodyPrinter::printCFIInstruction(CFIInstructionIndex Index) { + const MachineCFIInstruction *Instruction = Function.cfiInfo().instruction(Index); + if (Instruction == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "CFI operand references an unknown instruction"); + const auto PrintRegister = [this](DwarfRegisterNumber Dwarf) -> Expected { + const auto Register = Target.mirText().physicalRegister(Dwarf.value()); + if (!Register) { + return makeUnexpected(ErrorCode::VerificationError, + "CFI instruction has no canonical physical register"); + } + return appendPhysicalRegister(*Register); + }; + const auto PrintRegisterOffset = + [this, &PrintRegister](std::string_view Name, + const MachineCFIRegisterOffsetRule &Rule) -> Expected { + Output.append(Name); + Output.push_back(' '); + if (auto Printed = PrintRegister(Rule.Register); !Printed) + return Printed; + Output.append(", "); + Output.append(std::to_string(Rule.Offset)); + return {}; + }; + + switch (Instruction->operation()) { + case MachineCFIOperation::SameValue: { + Output.append("same_value "); + return PrintRegister(Instruction->getIf()->Register); + } + case MachineCFIOperation::RememberState: + Output.append("remember_state"); + return {}; + case MachineCFIOperation::RestoreState: + Output.append("restore_state"); + return {}; + case MachineCFIOperation::Offset: + return PrintRegisterOffset("offset", *Instruction->getIf()); + case MachineCFIOperation::LLVMDefAddressSpaceCFA: { + const auto &Rule = *Instruction->getIf(); + Output.append("llvm_def_aspace_cfa "); + if (auto Printed = PrintRegister(Rule.Register); !Printed) + return Printed; + Output.append(", "); + Output.append(std::to_string(Rule.Offset)); + Output.append(", "); + Output.append(std::to_string(Rule.AddressSpace)); + return {}; + } + case MachineCFIOperation::DefCFARegister: + Output.append("def_cfa_register "); + return PrintRegister(Instruction->getIf()->Register); + case MachineCFIOperation::DefCFAOffset: + Output.append("def_cfa_offset "); + Output.append(std::to_string(Instruction->getIf()->Offset)); + return {}; + case MachineCFIOperation::DefCFA: + return PrintRegisterOffset("def_cfa", *Instruction->getIf()); + case MachineCFIOperation::RelativeOffset: + return PrintRegisterOffset("rel_offset", *Instruction->getIf()); + case MachineCFIOperation::AdjustCFAOffset: + Output.append("adjust_cfa_offset "); + Output.append(std::to_string(Instruction->getIf()->Offset)); + return {}; + case MachineCFIOperation::Escape: { + Output.append("escape "); + constexpr std::string_view Hex = "0123456789ABCDEF"; + const auto &Bytes = Instruction->getIf()->Bytes; + for (std::size_t ByteIndex = 0; ByteIndex < Bytes.size(); ++ByteIndex) { + if (ByteIndex != 0) + Output.append(", "); + Output.append("0x"); + Output.push_back(Hex[Bytes[ByteIndex] >> 4U]); + Output.push_back(Hex[Bytes[ByteIndex] & 0xFU]); + } + return {}; + } + case MachineCFIOperation::Restore: + Output.append("restore "); + return PrintRegister(Instruction->getIf()->Register); + case MachineCFIOperation::Undefined: + Output.append("undefined "); + return PrintRegister(Instruction->getIf()->Register); + case MachineCFIOperation::Register: { + const auto &Rule = *Instruction->getIf(); + Output.append("register "); + if (auto Printed = PrintRegister(Rule.Register); !Printed) + return Printed; + Output.append(", "); + return PrintRegister(Rule.SourceRegister); + } + case MachineCFIOperation::WindowSave: + Output.append("window_save"); + return {}; + case MachineCFIOperation::NegateReturnAddressState: + Output.append("negate_ra_sign_state"); + return {}; + case MachineCFIOperation::NegateReturnAddressStateWithPC: + Output.append("negate_ra_sign_state_with_pc"); + return {}; + case MachineCFIOperation::GNUArgsSize: + case MachineCFIOperation::Label: + case MachineCFIOperation::ValueOffset: + return makeUnexpected( + ErrorCode::Unsupported, + "CFI operation has no textual representation in the fixed LLVM MIR baseline"); + case MachineCFIOperation::LLVMRegisterPair: { + const auto &Rule = *Instruction->getIf(); + Output.append("llvm_register_pair "); + if (auto Printed = PrintRegister(Rule.Register); !Printed) + return Printed; + Output.append(", "); + if (auto Printed = PrintRegister(Rule.FirstRegister); !Printed) + return Printed; + Output.append(", "); + Output.append(std::to_string(Rule.FirstSizeInBits)); + Output.append(", "); + if (auto Printed = PrintRegister(Rule.SecondRegister); !Printed) + return Printed; + Output.append(", "); + Output.append(std::to_string(Rule.SecondSizeInBits)); + return {}; + } + case MachineCFIOperation::LLVMVectorRegisters: { + const auto &Rule = *Instruction->getIf(); + Output.append("llvm_vector_registers "); + if (auto Printed = PrintRegister(Rule.Register); !Printed) + return Printed; + for (const MachineCFIVectorRegisterLane &Lane : Rule.VectorRegisters) { + Output.append(", "); + if (auto Printed = PrintRegister(Lane.Register); !Printed) + return Printed; + Output.append(", "); + Output.append(std::to_string(Lane.Lane)); + Output.append(", "); + Output.append(std::to_string(Lane.SizeInBits)); + } + return {}; + } + case MachineCFIOperation::LLVMVectorOffset: { + const auto &Rule = *Instruction->getIf(); + Output.append("llvm_vector_offset "); + if (auto Printed = PrintRegister(Rule.Register); !Printed) + return Printed; + Output.append(", "); + Output.append(std::to_string(Rule.RegisterSizeInBits)); + Output.append(", "); + if (auto Printed = PrintRegister(Rule.MaskRegister); !Printed) + return Printed; + Output.append(", "); + Output.append(std::to_string(Rule.MaskRegisterSizeInBits)); + Output.append(", "); + Output.append(std::to_string(Rule.Offset)); + return {}; + } + case MachineCFIOperation::LLVMVectorRegisterMask: { + const auto &Rule = *Instruction->getIf(); + Output.append("llvm_vector_register_mask "); + if (auto Printed = PrintRegister(Rule.Register); !Printed) + return Printed; + Output.append(", "); + if (auto Printed = PrintRegister(Rule.SpillRegister); !Printed) + return Printed; + Output.append(", "); + Output.append(std::to_string(Rule.SpillRegisterLaneSizeInBits)); + Output.append(", "); + if (auto Printed = PrintRegister(Rule.MaskRegister); !Printed) + return Printed; + Output.append(", "); + Output.append(std::to_string(Rule.MaskRegisterSizeInBits)); + return {}; + } + case MachineCFIOperation::Count: + return makeUnexpected(ErrorCode::VerificationError, "CFI instruction has an invalid operation"); + } + return makeUnexpected(ErrorCode::InternalError, "CFI printer did not handle an operation"); +} + +Expected BodyPrinter::printOperand(const MachineOperand &Operand, bool IsExplicitDef) { + if (Operand.isRegister()) + return printRegisterOperand(Operand, IsExplicitDef); + if (auto Flags = printTargetFlags(Operand.targetFlags()); !Flags) + return Flags; + + switch (Operand.kind()) { + case MachineOperand::Kind::Register: + return makeUnexpected(ErrorCode::InternalError, + "register operand reached the non-register printer"); + case MachineOperand::Kind::Immediate: + Output.append(std::to_string(*Operand.getIf())); + return {}; + case MachineOperand::Kind::IntegerImmediate: { + const IntegerImmediate &Value = Operand.getIf()->Value; + Output.push_back('i'); + Output.append(std::to_string(Value.bitWidth())); + Output.push_back(' '); + Output.append(unsignedDecimal(Value.words())); + return {}; + } + case MachineOperand::Kind::FloatingImmediate: { + const FloatingPointBits &Bits = Operand.getIf()->Bits; + const std::string_view Keyword = floatKeyword(Bits.semantics()); + if (Keyword.empty()) { + return makeUnexpected(ErrorCode::Unsupported, + "floating-point semantics has no LLVM MIR spelling"); + } + Output.append(Keyword); + Output.append(" f0x"); + Output.append(hexadecimalWords(Bits.words(), Bits.bitWidth())); + return {}; + } + case MachineOperand::Kind::BasicBlock: { + const MachineBasicBlock *Block = Operand.getIf()->Block; + if (Block == nullptr || !BlockIDs.contains(Block)) { + return makeUnexpected(ErrorCode::VerificationError, + "basic-block operand references an unlinked block"); + } + appendBlockReference(*Block); + return {}; + } + case MachineOperand::Kind::FrameIndex: { + const auto &Frame = *Operand.getIf(); + auto ID = frameID(Frame.Index); + if (!ID) + return std::unexpected(ID.error()); + const auto Stack = std::ranges::find_if( + Context.StackObjects, + [Index = Frame.Index](const MIFrameObjectSlot &Slot) { return Slot.Index == Index; }); + if (Stack != Context.StackObjects.end()) { + Output.append("%stack."); + Output.append(std::to_string(*ID)); + if (Stack->Name) { + Output.push_back('.'); + Output.append(quoteName(*Stack->Name)); + } + } else { + Output.append("%fixed-stack."); + Output.append(std::to_string(*ID)); + } + appendOffset(Frame.Offset); + return {}; + } + case MachineOperand::Kind::ConstantPoolIndex: { + const auto &Constant = *Operand.getIf(); + auto ID = constantPoolID(Constant.Index); + if (!ID) + return std::unexpected(ID.error()); + Output.append("%const."); + Output.append(std::to_string(*ID)); + appendOffset(Constant.Offset); + return {}; + } + case MachineOperand::Kind::JumpTableIndex: { + auto ID = jumpTableID(Operand.getIf()->Index); + if (!ID) + return std::unexpected(ID.error()); + Output.append("%jump-table."); + Output.append(std::to_string(*ID)); + return {}; + } + case MachineOperand::Kind::GlobalSymbol: { + const auto &Global = *Operand.getIf(); + Output.push_back('@'); + Output.append(quoteName(Global.Name)); + appendOffset(Global.Offset); + return {}; + } + case MachineOperand::Kind::ExternalSymbol: { + const auto &External = *Operand.getIf(); + Output.push_back('&'); + Output.append(quoteName(External.Name)); + appendOffset(External.Offset); + return {}; + } + case MachineOperand::Kind::BlockAddress: { + const auto &Address = *Operand.getIf(); + Output.append("blockaddress(@"); + Output.append(quoteName(Address.FunctionName)); + Output.append(", %ir-block."); + Output.append(quoteName(Address.BlockName)); + Output.push_back(')'); + appendOffset(Address.Offset); + return {}; + } + case MachineOperand::Kind::RegisterMask: { + const RegisterMask &Mask = *Operand.getIf()->Mask; + if (const auto Name = Target.mirText().registerMaskName(Mask)) { + Output.append(*Name); + return {}; + } + Output.append("CustomRegMask("); + bool First = true; + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { + if (!Mask.preserves(Register.Reg)) + continue; + if (!First) + Output.append(", "); + First = false; + if (auto Printed = appendPhysicalRegister(Register.Reg); !Printed) + return Printed; + } + Output.push_back(')'); + return {}; + } + case MachineOperand::Kind::LiveOutRegisterMask: { + const RegisterMask &Mask = *Operand.getIf()->Mask; + Output.append("liveout("); + bool First = true; + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { + if (!Mask.preserves(Register.Reg)) + continue; + if (!First) + Output.append(", "); + First = false; + if (auto Printed = appendPhysicalRegister(Register.Reg); !Printed) + return Printed; + } + Output.push_back(')'); + return {}; + } + case MachineOperand::Kind::Metadata: { + const MachineMetadataValue &Value = Operand.getIf()->Value; + if (const auto *Reference = Value.reference()) + return printMetadataReference(*Reference); + const MachineDIExpression *Expression = Value.expression(); + if (Expression == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "metadata operand has no printable value"); + } + Output.append("!DIExpression("); + const auto Elements = Expression->elements(); + for (std::size_t Index = 0; Index < Elements.size(); ++Index) { + if (Index != 0) + Output.append(", "); + Output.append(std::to_string(Elements[Index])); + } + Output.push_back(')'); + return {}; + } + case MachineOperand::Kind::TargetIndex: { + const auto &TargetIndexValue = *Operand.getIf(); + const auto Name = Target.mirText().targetIndexName(TargetIndexValue.Index); + if (!Name) + return makeUnexpected(ErrorCode::VerificationError, "target index has no MIR name"); + Output.append("target-index("); + Output.append(*Name); + Output.push_back(')'); + appendOffset(TargetIndexValue.Offset); + return {}; + } + case MachineOperand::Kind::MCSymbol: { + const auto &Symbol = *Operand.getIf(); + Output.append("'); + appendOffset(Symbol.Offset); + return {}; + } + case MachineOperand::Kind::CFIIndex: + return printCFIInstruction(Operand.getIf()->Index); + case MachineOperand::Kind::Intrinsic: { + const auto Name = Target.mirText().intrinsicName(Operand.getIf()->ID); + if (!Name) + return makeUnexpected(ErrorCode::VerificationError, "intrinsic has no MIR name"); + Output.append("intrinsic(@"); + Output.append(*Name); + Output.push_back(')'); + return {}; + } + case MachineOperand::Kind::Predicate: { + const PredicateOperand &Predicate = *Operand.getIf(); + if (const auto *Integer = Predicate.integerPredicate()) { + Output.append("intpred("); + Output.append(integerPredicateName(*Integer)); + } else { + Output.append("floatpred("); + Output.append(floatingPredicateName(*Predicate.floatingPredicate())); + } + Output.push_back(')'); + return {}; + } + case MachineOperand::Kind::ShuffleMask: { + Output.append("shufflemask("); + const auto &Elements = Operand.getIf()->Elements; + for (std::size_t Index = 0; Index < Elements.size(); ++Index) { + if (Index != 0) + Output.append(", "); + if (Elements[Index] == ShuffleMaskOperand::Undef) + Output.append("undef"); + else + Output.append(std::to_string(Elements[Index])); + } + Output.push_back(')'); + return {}; + } + case MachineOperand::Kind::DebugInstrRef: { + const auto &Reference = *Operand.getIf(); + Output.append("dbg-instr-ref("); + Output.append(std::to_string(Reference.InstructionNumber)); + Output.append(", "); + Output.append(std::to_string(Reference.OperandNumber)); + Output.push_back(')'); + return {}; + } + case MachineOperand::Kind::LaneMask: + Output.append("lanemask(0x"); + Output.append( + hexadecimalWords(std::array{Operand.getIf()->Mask.rawValue()}, 64)); + Output.push_back(')'); + return {}; + case MachineOperand::Kind::Count: + return makeUnexpected(ErrorCode::VerificationError, "machine operand has an invalid kind"); + } + return makeUnexpected(ErrorCode::InternalError, "machine operand printer did not handle a kind"); +} + +Expected BodyPrinter::printMemoryBase(const MemoryBase &Base, std::int64_t Offset) { + switch (Base.kind()) { + case MemoryBase::Kind::Unknown: + Output.append("unknown-address"); + break; + case MemoryBase::Kind::FrameIndex: { + const auto Frame = Base.frameIndex(); + if (!Frame) { + return makeUnexpected(ErrorCode::VerificationError, + "frame-index memory base has no frame index"); + } + const FrameIndex Index = *Frame; + auto ID = frameID(Index); + if (!ID) + return std::unexpected(ID.error()); + const auto Stack = + std::ranges::find_if(Context.StackObjects, [Index](const MIFrameObjectSlot &Slot) { + return Slot.Index == Index; + }); + if (Stack != Context.StackObjects.end()) { + Output.append("%stack."); + Output.append(std::to_string(*ID)); + if (Stack->Name) { + Output.push_back('.'); + Output.append(quoteName(*Stack->Name)); + } + } else { + Output.append("%fixed-stack."); + Output.append(std::to_string(*ID)); + } + break; + } + case MemoryBase::Kind::ConstantPool: { + const auto Constant = Base.constantPoolIndex(); + if (!Constant) { + return makeUnexpected(ErrorCode::VerificationError, "constant-pool memory base has no index"); + } + auto ID = constantPoolID(*Constant); + if (!ID) + return std::unexpected(ID.error()); + Output.append("%const."); + Output.append(std::to_string(*ID)); + break; + } + case MemoryBase::Kind::JumpTable: { + const auto JumpTable = Base.jumpTableIndex(); + if (!JumpTable) { + return makeUnexpected(ErrorCode::VerificationError, "jump-table memory base has no index"); + } + auto ID = jumpTableID(*JumpTable); + if (!ID) + return std::unexpected(ID.error()); + Output.append("%jump-table."); + Output.append(std::to_string(*ID)); + break; + } + case MemoryBase::Kind::GlobalSymbol: { + const auto &Name = Base.symbolName(); + if (!Name) { + return makeUnexpected(ErrorCode::VerificationError, "global memory base has no symbol name"); + } + Output.push_back('@'); + Output.append(quoteName(*Name)); + break; + } + case MemoryBase::Kind::ExternalSymbol: { + const auto &Name = Base.symbolName(); + if (!Name) { + return makeUnexpected(ErrorCode::VerificationError, + "external memory base has no symbol name"); + } + Output.push_back('&'); + Output.append(quoteName(*Name)); + break; + } + case MemoryBase::Kind::IRValue: { + const auto &Name = Base.symbolName(); + if (!Name) { + return makeUnexpected(ErrorCode::VerificationError, "IR-value memory base has no value name"); + } + Output.append("%ir."); + Output.append(quoteName(*Name)); + break; + } + case MemoryBase::Kind::Stack: + Output.append("stack"); + break; + case MemoryBase::Kind::GOT: + Output.append("got"); + break; + case MemoryBase::Kind::ConstantPoolPseudo: + Output.append("constant-pool"); + break; + case MemoryBase::Kind::JumpTablePseudo: + Output.append("jump-table"); + break; + case MemoryBase::Kind::CallEntryGlobal: { + const auto &Name = Base.symbolName(); + if (!Name) { + return makeUnexpected(ErrorCode::VerificationError, + "global call-entry memory base has no symbol name"); + } + Output.append("call-entry @"); + Output.append(quoteName(*Name)); + break; + } + case MemoryBase::Kind::CallEntryExternal: { + const auto &Name = Base.symbolName(); + if (!Name) { + return makeUnexpected(ErrorCode::VerificationError, + "external call-entry memory base has no symbol name"); + } + Output.append("call-entry &"); + Output.append(quoteName(*Name)); + break; + } + case MemoryBase::Kind::Custom: { + const auto &Name = Base.symbolName(); + if (!Name) { + return makeUnexpected(ErrorCode::VerificationError, "custom memory base has no name"); + } + Output.append("custom "); + Output.append(quoteName(*Name)); + break; + } + } + appendOffset(Offset); + return {}; +} + +Expected BodyPrinter::printMemoryOperand(const MachineMemOperand &Operand) { + const MachineMemOperandDesc &Description = Operand.description(); + Output.push_back('('); + if (Description.Accesses.has(MemoryAccessFlag::Volatile)) + Output.append("volatile "); + if (Description.Accesses.has(MemoryAccessFlag::NonTemporal)) + Output.append("non-temporal "); + if (Description.Accesses.has(MemoryAccessFlag::Dereferenceable)) + Output.append("dereferenceable "); + if (Description.Accesses.has(MemoryAccessFlag::Invariant)) + Output.append("invariant "); + if (Description.TargetFlags != 0) { + auto Names = Target.mirText().machineMemOperandFlagNames(Description.TargetFlags); + if (!Names) + return std::unexpected(Names.error()); + for (std::string_view Name : *Names) { + Output.append(quoteName(Name)); + Output.push_back(' '); + } + } + + if (Operand.isLoad()) + Output.append("load"); + else + Output.append("store"); + if (Operand.isLoad() && Operand.isStore()) + Output.append(" store"); + + if (Description.SyncScope.value() != 0) { + const auto Scope = + std::ranges::find_if(Context.SyncScopes, [&Description](const MISyncScopeSlot &Slot) { + return Slot.ID == Description.SyncScope; + }); + if (Scope == Context.SyncScopes.end()) { + return makeUnexpected(ErrorCode::VerificationError, "synchronization scope has no MIR name"); + } + Output.append(" syncscope("); + Output.append(quoteName(Scope->Name)); + Output.push_back(')'); + } + if (Description.SuccessOrdering != AtomicOrdering::NotAtomic) { + Output.push_back(' '); + Output.append(atomicOrderingName(Description.SuccessOrdering)); + } + if (Description.FailureOrdering != AtomicOrdering::NotAtomic) { + Output.push_back(' '); + Output.append(atomicOrderingName(Description.FailureOrdering)); + } + + Output.push_back(' '); + switch (Description.Size.kind()) { + case MemorySize::Kind::Unknown: + Output.append("unknown-size"); + break; + case MemorySize::Kind::Fixed: + Output.append(std::to_string(Description.Size.minimumBytes())); + break; + case MemorySize::Kind::Scalable: + Output.append("()"); + break; + } + + const std::string_view Preposition = + Operand.isLoad() && Operand.isStore() ? " on " : (Operand.isLoad() ? " from " : " into "); + Output.append(Preposition); + if (auto Printed = printMemoryBase(Description.Base, Description.Offset); !Printed) { + return Printed; + } + + Output.append(", align "); + Output.append(std::to_string(Description.Align.bytes())); + if (Description.BaseAlign) { + Output.append(", basealign "); + Output.append(std::to_string(Description.BaseAlign->bytes())); + } + if (Description.AddressSpace != 0) { + Output.append(", addrspace "); + Output.append(std::to_string(Description.AddressSpace)); + } + + const auto PrintMetadata = + [this](std::string_view Name, + const std::optional &Reference) -> Expected { + if (!Reference) + return {}; + Output.append(", "); + Output.append(Name); + Output.push_back(' '); + return printMetadataReference(*Reference); + }; + if (auto Printed = PrintMetadata("!tbaa", Description.TBAA); !Printed) + return Printed; + if (auto Printed = PrintMetadata("!alias.scope", Description.AliasScope); !Printed) { + return Printed; + } + if (auto Printed = PrintMetadata("!noalias", Description.NoAlias); !Printed) + return Printed; + if (auto Printed = PrintMetadata("!noalias.addrspace", Description.NoAliasAddressSpace); + !Printed) { + return Printed; + } + if (auto Printed = PrintMetadata("!range", Description.RangeMetadata); !Printed) { + return Printed; + } + Output.push_back(')'); + return {}; +} + +Expected BodyPrinter::printInstruction(const MachineInstr &Instruction) { + const InstructionDescriptor *Descriptor = Target.instructions().descriptor(Instruction.opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "machine instruction has no target descriptor"); + } + if (Descriptor->NumExplicitDefs > Instruction.operandCount()) { + return makeUnexpected(ErrorCode::VerificationError, + "machine instruction has fewer operands than explicit definitions"); + } + + Output.append(" "); + for (std::size_t Index = 0; Index < Descriptor->NumExplicitDefs; ++Index) { + if (Index != 0) + Output.append(", "); + if (auto Printed = printOperand(*Instruction.operandAt(Index), true); !Printed) { + return Printed; + } + } + if (Descriptor->NumExplicitDefs != 0) + Output.append(" = "); + + const MachineInstrFlags Flags = Instruction.flags(); + constexpr std::array FlagSpellings{ + std::pair{MachineInstrFlag::FrameSetup, std::string_view{"frame-setup"}}, + std::pair{MachineInstrFlag::FrameDestroy, std::string_view{"frame-destroy"}}, + std::pair{MachineInstrFlag::FastMathNoNaNs, std::string_view{"nnan"}}, + std::pair{MachineInstrFlag::FastMathNoInfs, std::string_view{"ninf"}}, + std::pair{MachineInstrFlag::FastMathNoSignedZeros, std::string_view{"nsz"}}, + std::pair{MachineInstrFlag::FastMathAllowReciprocal, std::string_view{"arcp"}}, + std::pair{MachineInstrFlag::FastMathAllowContract, std::string_view{"contract"}}, + std::pair{MachineInstrFlag::FastMathApproxFunc, std::string_view{"afn"}}, + std::pair{MachineInstrFlag::FastMathAllowReassoc, std::string_view{"reassoc"}}, + std::pair{MachineInstrFlag::NoUnsignedWrap, std::string_view{"nuw"}}, + std::pair{MachineInstrFlag::NoSignedWrap, std::string_view{"nsw"}}, + std::pair{MachineInstrFlag::NoUSWrap, std::string_view{"nusw"}}, + std::pair{MachineInstrFlag::Exact, std::string_view{"exact"}}, + std::pair{MachineInstrFlag::NoFPExcept, std::string_view{"nofpexcept"}}, + std::pair{MachineInstrFlag::Unpredictable, std::string_view{"unpredictable"}}, + std::pair{MachineInstrFlag::NoConvergent, std::string_view{"noconvergent"}}, + std::pair{MachineInstrFlag::NonNeg, std::string_view{"nneg"}}, + std::pair{MachineInstrFlag::Disjoint, std::string_view{"disjoint"}}, + std::pair{MachineInstrFlag::SameSign, std::string_view{"samesign"}}, + std::pair{MachineInstrFlag::InBounds, std::string_view{"inbounds"}}, + }; + for (const auto &[Flag, Spelling] : FlagSpellings) { + if (Flags.has(Flag)) { + Output.append(Spelling); + Output.push_back(' '); + } + } + Output.append(Descriptor->Name); + + bool HasPrintedTail = false; + for (std::size_t Index = Descriptor->NumExplicitDefs; Index < Instruction.operandCount(); + ++Index) { + Output.append(HasPrintedTail ? ", " : " "); + HasPrintedTail = true; + if (auto Printed = printOperand(*Instruction.operandAt(Index), false); !Printed) { + return Printed; + } + } + + const auto BeginAttachment = [this, &HasPrintedTail](std::string_view Name) { + Output.append(HasPrintedTail ? ", " : " "); + HasPrintedTail = true; + Output.append(Name); + Output.push_back(' '); + }; + if (Instruction.preInstrSymbol()) { + BeginAttachment("pre-instr-symbol"); + Output.append("'); + } + if (Instruction.postInstrSymbol()) { + BeginAttachment("post-instr-symbol"); + Output.append("'); + } + if (Instruction.heapAllocMarker()) { + BeginAttachment("heap-alloc-marker"); + if (auto Printed = printMetadataReference(*Instruction.heapAllocMarker()); !Printed) { + return Printed; + } + } + if (Instruction.pcSections()) { + BeginAttachment("pcsections"); + if (auto Printed = printMetadataReference(*Instruction.pcSections()); !Printed) { + return Printed; + } + } + if (Instruction.mmra()) { + BeginAttachment("mmra"); + if (auto Printed = printMetadataReference(*Instruction.mmra()); !Printed) + return Printed; + } + if (Instruction.cfiType()) { + BeginAttachment("cfi-type"); + Output.append(std::to_string(*Instruction.cfiType())); + } + if (Instruction.deactivationSymbol()) { + BeginAttachment("deactivation-symbol"); + Output.push_back('@'); + Output.append(quoteName(*Instruction.deactivationSymbol())); + } + if (Instruction.debugInstrNumber() != 0) { + BeginAttachment("debug-instr-number"); + Output.append(std::to_string(Instruction.debugInstrNumber())); + } + if (Instruction.debugLocation()) { + BeginAttachment("debug-location"); + if (const MachineMetadataReference *Reference = Instruction.debugLocation()->reference()) { + if (auto Printed = printMetadataReference(*Reference); !Printed) + return Printed; + } else if (const MachineDILocation *Location = Instruction.debugLocation()->inlineLocation()) { + if (auto Printed = printDILocation(*Location, 0); !Printed) + return Printed; + } else { + return makeUnexpected(ErrorCode::VerificationError, + "machine debug location has no printable value"); + } + } + + if (!Instruction.memOperands().empty()) { + Output.append(" :: "); + for (std::size_t Index = 0; Index < Instruction.memOperands().size(); ++Index) { + if (Index != 0) + Output.append(", "); + if (auto Printed = printMemoryOperand(*Instruction.memOperands()[Index]); !Printed) { + return Printed; + } + } + } + return {}; +} + +Expected BodyPrinter::printBlock(const MachineBasicBlock &Block) { + auto ID = blockID(Block); + if (!ID) + return std::unexpected(ID.error()); + Output.append("bb."); + Output.append(std::to_string(*ID)); + const auto &Name = Block.attributes().name(); + if (Name) { + Output.push_back('.'); + Output.append(quoteName(*Name)); + } + + std::vector Attributes; + const auto AddFlag = [&Block, &Attributes](MachineBasicBlockAttribute Attribute, + std::string_view Spelling) { + if (Block.attributes().has(Attribute)) + Attributes.emplace_back(Spelling); + }; + AddFlag(MachineBasicBlockAttribute::MachineBlockAddressTaken, "machine-block-address-taken"); + if (Block.attributes().has(MachineBasicBlockAttribute::IRBlockAddressTaken)) { + std::string Attribute = "ir-block-address-taken"; + const auto &IRBlockName = Block.attributes().irBlockName(); + if (IRBlockName) { + Attribute.append(" %ir-block."); + Attribute.append(quoteName(*IRBlockName)); + } + Attributes.push_back(std::move(Attribute)); + } else { + const auto &IRBlockName = Block.attributes().irBlockName(); + if (IRBlockName) + Attributes.push_back("%ir-block." + quoteName(*IRBlockName)); + } + AddFlag(MachineBasicBlockAttribute::LandingPad, "landing-pad"); + AddFlag(MachineBasicBlockAttribute::InlineAsmBrIndirectTarget, "inlineasm-br-indirect-target"); + AddFlag(MachineBasicBlockAttribute::EHFuncletEntry, "ehfunclet-entry"); + AddFlag(MachineBasicBlockAttribute::EHScopeEntry, "ehscope-entry"); + if (Block.attributes().alignment().bytes() != 1) { + Attributes.push_back("align " + std::to_string(Block.attributes().alignment().bytes())); + } + const MachineBasicBlockSectionID Section = Block.attributes().sectionID(); + if (!Section.isDefault()) { + std::string Value; + if (Section.kind() == MachineBasicBlockSectionKind::Exception) + Value = "Exception"; + else if (Section.kind() == MachineBasicBlockSectionKind::Cold) + Value = "Cold"; + else + Value = std::to_string(Section.number()); + Attributes.push_back("bbsections " + Value); + } + const auto &ProfileID = Block.attributes().profileID(); + if (ProfileID) { + const MachineBasicBlockProfileID Profile = *ProfileID; + Attributes.push_back("bb_id " + std::to_string(Profile.BaseID) + "." + + std::to_string(Profile.CloneID)); + } + if (Block.attributes().callFrameSize() != 0) { + Attributes.push_back("call-frame-size " + std::to_string(Block.attributes().callFrameSize())); + } + if (!Attributes.empty()) { + Output.append(" ("); + for (std::size_t Index = 0; Index < Attributes.size(); ++Index) { + if (Index != 0) + Output.append(", "); + Output.append(Attributes[Index]); + } + Output.push_back(')'); + } + Output.append(":\n"); + + if (!Block.liveIns().empty()) { + Output.append(" liveins: "); + for (std::size_t Index = 0; Index < Block.liveIns().size(); ++Index) { + if (Index != 0) + Output.append(", "); + const MachineBasicBlockLiveIn &LiveIn = Block.liveIns()[Index]; + if (auto Printed = appendPhysicalRegister(LiveIn.PhysReg); !Printed) + return Printed; + if (LiveIn.Lanes != LaneMask::all()) { + Output.append(": 0x"); + Output.append(hexadecimalWords(std::array{LiveIn.Lanes.rawValue()}, 64)); + } + } + Output.push_back('\n'); + } + if (!Block.successors().empty()) { + Output.append(" successors: "); + for (std::size_t Index = 0; Index < Block.successors().size(); ++Index) { + if (Index != 0) + Output.append(", "); + const MachineSuccessor &Successor = Block.successors()[Index]; + if (Successor.Block == nullptr || !BlockIDs.contains(Successor.Block)) { + return makeUnexpected(ErrorCode::VerificationError, + "successor references an unlinked block"); + } + appendBlockReference(*Successor.Block); + Output.push_back('('); + Output.append(std::to_string(Successor.Probability.rawValue())); + Output.push_back(')'); + } + Output.push_back('\n'); + } + + bool InBundle = false; + for (const MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (auto Printed = printInstruction(*Instruction); !Printed) + return Printed; + const bool HasPredecessor = Instruction->flags().has(MachineInstrFlag::BundledWithPred); + const bool HasSuccessor = Instruction->flags().has(MachineInstrFlag::BundledWithSucc); + if (!InBundle && HasSuccessor && !HasPredecessor) { + Output.append(" {"); + InBundle = true; + } + Output.push_back('\n'); + if (InBundle && !HasSuccessor) { + Output.append(" }\n"); + InBundle = false; + } + } + if (InBundle) { + return makeUnexpected(ErrorCode::VerificationError, + "unterminated instruction bundle cannot be printed"); + } + return {}; +} + +Expected BodyPrinter::run() { + auto Verification = MachineVerifier::verify( + Function, Target, + MachineVerifierOptions{ + .Mode = MachineVerifierMode::Generic, .Stage = std::nullopt, .VerifyProperties = false}); + if (!Verification) + return std::unexpected(Verification.error()); + if (auto Initialized = initialize(); !Initialized) + return std::unexpected(Initialized.error()); + + bool First = true; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + if (!First) + Output.push_back('\n'); + First = false; + if (auto Printed = printBlock(*Block); !Printed) + return std::unexpected(Printed.error()); + } + return std::move(Output); +} + +} // namespace + +Expected printMachineFunctionBody(const MachineFunction &Function, + const TargetDescription &Target, + const MIParserContext &Context, + MIPrinterOptions Options) { + return BodyPrinter(Function, Target, Context, Options).run(); +} + +} // namespace rcc::mir diff --git a/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp b/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp index a019c8b..9c8a447 100644 --- a/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp +++ b/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp @@ -266,8 +266,14 @@ createFunction(TestContext &Context, std::string Name, std::uint64_t ID) { Description.Accesses = {rcc::MemoryAccessFlag::Load, rcc::MemoryAccessFlag::Dereferenceable}; Description.Size = *rcc::MemorySize::fixed(8); Description.Align = *rcc::Alignment::create(8); + Description.BaseAlign = *rcc::Alignment::create(16); Description.Base = std::move(Base); Description.Offset = -8; + Description.TBAA = rcc::MachineMetadataReference::embeddedIR(10); + Description.AliasScope = rcc::MachineMetadataReference::embeddedIR(11); + Description.NoAlias = rcc::MachineMetadataReference::embeddedIR(12); + Description.NoAliasAddressSpace = rcc::MachineMetadataReference::embeddedIR(13); + Description.RangeMetadata = rcc::MachineMetadataReference::embeddedIR(14); Description.TargetFlags = 0x3; return Description; } @@ -469,6 +475,16 @@ struct SourceFixture final { const rcc::StackObject *Object = Function.frameInfo().object(Fixture.StackSlot); if (Definition == nullptr || LoadInstruction == nullptr || Object == nullptr) return false; + Context.expect( + Definition->setPreInstrSymbol("before").has_value() && + Definition->setPostInstrSymbol("after").has_value() && + Definition->setHeapAllocMarker(rcc::MachineMetadataReference::embeddedIR(20)) + .has_value() && + Definition->setPCSections(rcc::MachineMetadataReference::embeddedIR(21)).has_value() && + Definition->setMMRA(rcc::MachineMetadataReference::embeddedIR(22)).has_value() && + Definition->setCFIType(23).has_value() && + Definition->setDeactivationSymbol("guard").has_value(), + "source instruction attachments must be recorded"); rcc::StackObjectDesc UpdatedStackSlot = *Object->description(); UpdatedStackSlot.Lifetime.push_back({Definition->stableID(), LoadInstruction->stableID()}); Context.expect(Function.frameInfo() @@ -621,12 +637,18 @@ void testDeepClone(TestContext &Context) { return; } - Context.expect(DestinationDef->operandAt(0)->registerValue() == NewValue && - DestinationDef->flags().has(rcc::MachineInstrFlag::NoMerge) && - DestinationDef->sourceLocation() == - rcc::SourceLocation{"source.mir", 9, 4, 2} && - DestinationDef->origin() == rcc::OriginID::fromValue(77), - "clone must remap register operands and preserve instruction metadata"); + Context.expect( + DestinationDef->operandAt(0)->registerValue() == NewValue && + DestinationDef->flags().has(rcc::MachineInstrFlag::NoMerge) && + DestinationDef->sourceLocation() == rcc::SourceLocation{"source.mir", 9, 4, 2} && + DestinationDef->origin() == rcc::OriginID::fromValue(77) && + DestinationDef->preInstrSymbol() == "before" && + DestinationDef->postInstrSymbol() == "after" && + DestinationDef->heapAllocMarker() == rcc::MachineMetadataReference::embeddedIR(20) && + DestinationDef->pcSections() == rcc::MachineMetadataReference::embeddedIR(21) && + DestinationDef->mmra() == rcc::MachineMetadataReference::embeddedIR(22) && + DestinationDef->cfiType() == 23 && DestinationDef->deactivationSymbol() == "guard", + "clone must remap register operands and preserve instruction metadata"); Context.expect(DestinationBranch->operandAt(0)->getIf()->Block == DestinationExit, "clone must remap basic-block operands"); diff --git a/backend/unittests/MIR/CMakeLists.txt b/backend/unittests/MIR/CMakeLists.txt index bff2c99..1eb0965 100644 --- a/backend/unittests/MIR/CMakeLists.txt +++ b/backend/unittests/MIR/CMakeLists.txt @@ -12,11 +12,24 @@ target_link_libraries(RCCBackendMILexerTests PRIVATE RCCBackend::MIR) add_test(NAME RCCBackend.MIR.MILexer COMMAND RCCBackendMILexerTests) +add_executable(RCCBackendMIParserTests MIParserTest.cpp) +rcc_backend_configure_target(RCCBackendMIParserTests) +target_link_libraries( + RCCBackendMIParserTests + PRIVATE + RCCBackend::MIR + RCCBackend::TestTarget +) + +add_test(NAME RCCBackend.MIR.MIParser COMMAND RCCBackendMIParserTests) + rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIRTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MILexerTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MIParserTest.cpp" ) rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIRTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MILexerTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/MIParserTest.cpp" ) diff --git a/backend/unittests/MIR/MIParserTest.cpp b/backend/unittests/MIR/MIParserTest.cpp new file mode 100644 index 0000000..d037bef --- /dev/null +++ b/backend/unittests/MIR/MIParserTest.cpp @@ -0,0 +1,396 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/MIR/MIParser.h" + +#include "Target/TestTarget.h" +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/MIR/MIPrinter.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace { + +constexpr std::uint32_t CopyOpcode = 1; +constexpr std::uint32_t AddImmediateOpcode = 2; +constexpr std::uint32_t BranchOpcode = 3; +constexpr std::uint32_t NopOpcode = 4; +constexpr std::uint32_t ConstantOpcode = 5; +constexpr std::uint32_t FloatingConstantOpcode = 6; +constexpr std::uint32_t MetadataOpcode = 7; +constexpr std::uint32_t LoadOpcode = 8; + +class TestContext final { +public: + void expect(bool Condition, std::string_view Message) { + if (Condition) + return; + std::cerr << Message << '\n'; + ++FailureCount; + } + + [[nodiscard]] int result() const noexcept { + return FailureCount == 0 ? 0 : 1; + } + +private: + int FailureCount = 0; +}; + +[[nodiscard]] rcc::OperandDescriptor +registerOperand(rcc::RegisterOperandRole Role, + rcc::RegisterClassID Class = rcc::test::TestRegisterClass::GPR64) { + rcc::OperandDescriptor Descriptor; + Descriptor.Kinds = {rcc::MachineOperand::Kind::Register}; + Descriptor.RegisterRole = Role; + Descriptor.RegClass = Class; + return Descriptor; +} + +[[nodiscard]] rcc::InstructionDescriptor descriptor(std::uint32_t OpcodeValue, std::string Name) { + rcc::InstructionDescriptor Descriptor; + Descriptor.InstructionOpcode = rcc::Opcode::fromValue(OpcodeValue); + Descriptor.Name = std::move(Name); + Descriptor.Flags = {rcc::InstructionFlag::ProducesCode}; + return Descriptor; +} + +[[nodiscard]] rcc::OperandDescriptor genericRegisterOperand(rcc::RegisterOperandRole Role) { + rcc::OperandDescriptor Descriptor; + Descriptor.Kinds = {rcc::MachineOperand::Kind::Register}; + Descriptor.RegisterRole = Role; + return Descriptor; +} + +[[nodiscard]] rcc::OperandDescriptor operand(rcc::MachineOperand::Kind Kind) { + rcc::OperandDescriptor Descriptor; + Descriptor.Kinds = {Kind}; + return Descriptor; +} + +[[nodiscard]] rcc::Expected createTarget() { + auto Copy = descriptor(CopyOpcode, "TEST_COPY"); + Copy.Operands = { + registerOperand(rcc::RegisterOperandRole::Def), + registerOperand(rcc::RegisterOperandRole::Use), + }; + Copy.NumExplicitDefs = 1; + + auto AddImmediate = descriptor(AddImmediateOpcode, "TEST_ADDI"); + AddImmediate.Operands = { + registerOperand(rcc::RegisterOperandRole::Def), + registerOperand(rcc::RegisterOperandRole::Use), + }; + rcc::OperandDescriptor Immediate; + Immediate.Kinds = {rcc::MachineOperand::Kind::Immediate}; + Immediate.AllowedTargetFlags = 0xFU; + AddImmediate.Operands.push_back(Immediate); + AddImmediate.NumExplicitDefs = 1; + + auto Branch = descriptor(BranchOpcode, "TEST_BRANCH"); + rcc::OperandDescriptor Block; + Block.Kinds = {rcc::MachineOperand::Kind::BasicBlock}; + Branch.Operands.push_back(Block); + Branch.Flags.set(rcc::InstructionFlag::Branch); + Branch.Flags.set(rcc::InstructionFlag::Terminator); + Branch.Flags.set(rcc::InstructionFlag::Barrier); + + auto Nop = descriptor(NopOpcode, "TEST_NOP"); + + auto Constant = descriptor(ConstantOpcode, "TEST_CONSTANT"); + Constant.Operands = { + genericRegisterOperand(rcc::RegisterOperandRole::Def), + operand(rcc::MachineOperand::Kind::IntegerImmediate), + }; + Constant.NumExplicitDefs = 1; + Constant.Flags.set(rcc::InstructionFlag::Generic); + Constant.Flags.set(rcc::InstructionFlag::AllowedPreLegalizer); + + auto FloatingConstant = descriptor(FloatingConstantOpcode, "TEST_FCONSTANT"); + FloatingConstant.Operands = { + genericRegisterOperand(rcc::RegisterOperandRole::Def), + operand(rcc::MachineOperand::Kind::FloatingImmediate), + }; + FloatingConstant.NumExplicitDefs = 1; + FloatingConstant.Flags.set(rcc::InstructionFlag::Generic); + FloatingConstant.Flags.set(rcc::InstructionFlag::AllowedPreLegalizer); + + auto Metadata = descriptor(MetadataOpcode, "TEST_METADATA"); + Metadata.Operands = { + operand(rcc::MachineOperand::Kind::Metadata), + operand(rcc::MachineOperand::Kind::Metadata), + operand(rcc::MachineOperand::Kind::CFIIndex), + }; + + auto Load = descriptor(LoadOpcode, "TEST_LOAD"); + Load.Operands = { + registerOperand(rcc::RegisterOperandRole::Def), + registerOperand(rcc::RegisterOperandRole::Use), + }; + Load.NumExplicitDefs = 1; + Load.Flags.set(rcc::InstructionFlag::MayLoad); + Load.RequiresMemoryOperands = true; + + std::vector Descriptors; + Descriptors.push_back(std::move(Copy)); + Descriptors.push_back(std::move(AddImmediate)); + Descriptors.push_back(std::move(Branch)); + Descriptors.push_back(std::move(Nop)); + Descriptors.push_back(std::move(Constant)); + Descriptors.push_back(std::move(FloatingConstant)); + Descriptors.push_back(std::move(Metadata)); + Descriptors.push_back(std::move(Load)); + auto Instructions = rcc::InstructionSet::create(std::move(Descriptors)); + if (!Instructions) + return std::unexpected(Instructions.error()); + return rcc::test::createTestTargetDescription(std::move(*Instructions)); +} + +[[nodiscard]] std::unique_ptr createFunction(TestContext &Context, + std::uint64_t ID) { + auto Function = + rcc::MachineFunction::create("parser", rcc::MachineFunctionStableID::fromValue(ID)); + Context.expect(Function.has_value(), "machine function creation must succeed"); + if (!Function) + return nullptr; + return std::move(*Function); +} + +void testTwoPassBodyParsing(TestContext &Context) { + auto Target = createTarget(); + auto Function = createFunction(Context, 1); + Context.expect(Target.has_value(), "parser target description must be valid"); + if (!Target) + std::cerr << "error: " << Target.error().message() << '\n'; + if (!Target || !Function) + return; + auto MetadataNode = + Function->metadata().addNode({.Slot = 100, .IsDistinct = false, .Elements = {}}); + Context.expect(MetadataNode.has_value(), "metadata fixture must be valid"); + if (!MetadataNode) + return; + + const std::string Body = R"( +bb.0."entry block" (align 16, bb_id 7.1, call-frame-size 32): + liveins: $g0 + successors: %bb.1."exit block"(2147483648) + %0:gpr64 = TEST_COPY $g0 + %1:gpr64 = frame-setup TEST_ADDI %0, target-flags(test-direct-one, test-bit-four) 4 + %2:_(s128) = TEST_CONSTANT i128 340282366920938463463374607431768211455 + %3:_(f64) = TEST_FCONSTANT double f0x400921FB54442D18 + TEST_METADATA !100, !DIExpression(DW_OP_LLVM_arg, 0), def_cfa $g0, 16, pre-instr-symbol , post-instr-symbol , heap-alloc-marker !0, pcsections !0, mmra !0, cfi-type 17, deactivation-symbol @guard, debug-instr-number 9, debug-location !DILocation(line: 42, column: 7, scope: !0, inlinedAt: !DILocation(line: 8, scope: !0, inlinedAt: !0), isImplicitCode: true, atomGroup: 3, atomRank: 2) + %4:gpr64 = TEST_LOAD %0 :: (load 8 from unknown-address, align 8, addrspace 0, !tbaa !0) + TEST_BRANCH %bb.1."exit block" + +bb.1."exit block" (landing-pad, bbsections Cold): + $g1 = TEST_COPY %1 + TEST_NOP { + TEST_NOP + } +)"; + + rcc::mir::MIParserContext ParserContext; + ParserContext.Metadata.push_back( + {.TextID = 0, .Reference = rcc::MachineMetadataReference::embeddedIR(0)}); + ParserContext.DefaultPointerSizeInBits = 64; + rcc::mir::MIParser Parser(*Function, *Target, "body.mir", Body, ParserContext); + const auto Parsed = Parser.parse(); + const bool ParseSucceeded = + Parsed.has_value() && !Parser.failed() && Parser.diagnostics().empty(); + Context.expect(ParseSucceeded, + "valid MIR body must pass both parsing passes and final verification"); + if (!ParseSucceeded) { + for (const auto &Diagnostic : Parser.diagnostics()) + std::cerr << Diagnostic.Category << ": " << Diagnostic.Message << '\n'; + if (!Parsed) + std::cerr << "error: " << Parsed.error().message() << '\n'; + } + if (!Parsed) + return; + + Context.expect(Function->blockCount() == 2 && Function->allInstructions().size() == 10, + "parser must publish every declared block and instruction"); + rcc::MachineBasicBlock *Entry = Function->firstBlock(); + rcc::MachineBasicBlock *Exit = Entry == nullptr ? nullptr : Entry->next(); + Context.expect(Entry != nullptr && Exit != nullptr && !Exit->next(), + "parsed block layout must retain source order"); + if (Entry == nullptr || Exit == nullptr) + return; + + Context.expect(Entry->attributes().name() == "entry block" && + Entry->attributes().alignment().bytes() == 16 && + Entry->attributes().profileID() == rcc::MachineBasicBlockProfileID{7, 1} && + Entry->attributes().callFrameSize() == 32, + "first-pass block attributes must be retained"); + Context.expect(Exit->attributes().has(rcc::MachineBasicBlockAttribute::LandingPad) && + Exit->attributes().sectionID() == rcc::MachineBasicBlockSectionID::cold(), + "named block flags and section IDs must be retained"); + Context.expect(Entry->liveIns().size() == 1 && Entry->successors().size() == 1 && + Entry->successors().front().Block == Exit && + Entry->successors().front().Probability.rawValue() == 2147483648U, + "live-ins and explicitly weighted successors must be published"); + + const auto Registers = Function->registerInfo().virtualRegisters(); + Context.expect(Registers.size() == 5 && + Registers[0].RegClass == rcc::test::TestRegisterClass::GPR64 && + Registers[1].RegClass == rcc::test::TestRegisterClass::GPR64 && + Registers[2].Type == *rcc::LLT::makeAnyScalar(128) && + Registers[3].Type == *rcc::LLT::makeFloat(rcc::FloatSemantics::IEEEDouble) && + Registers[4].RegClass == rcc::test::TestRegisterClass::GPR64, + "textual virtual registers must map deterministically to classed MachineIR vregs"); + + const rcc::MachineInstr *Add = Entry->firstInstruction()->next(); + Context.expect(Add->flags().has(rcc::MachineInstrFlag::FrameSetup) && + Add->operandAt(2)->targetFlags() == 0x5U, + "instruction and target operand flags must be preserved"); + + const rcc::MachineInstr *Constant = Add->next(); + const auto *Integer = Constant->operandAt(1)->getIf(); + const auto *Floating = Constant->next()->operandAt(1)->getIf(); + Context.expect(Integer != nullptr && Integer->Value.bitWidth() == 128 && + Integer->Value.words().size() == 2 && + Integer->Value.words()[0] == std::numeric_limits::max() && + Integer->Value.words()[1] == std::numeric_limits::max() && + Floating != nullptr && + Floating->Bits.semantics() == rcc::FloatSemantics::IEEEDouble && + Floating->Bits.words()[0] == 0x400921FB54442D18ULL, + "typed integer and exact floating-point operands must retain their bit patterns"); + + const rcc::MachineInstr *Metadata = Constant->next()->next(); + const auto *Reference = Metadata->operandAt(0)->getIf(); + const auto *Expression = Metadata->operandAt(1)->getIf(); + const auto *CFI = Metadata->operandAt(2)->getIf(); + Context.expect( + Reference != nullptr && Reference->Value.reference() != nullptr && + Reference->Value.reference()->scope() == rcc::MachineMetadataScope::MachineFunction && + Reference->Value.reference()->slot() == 100 && Expression != nullptr && + Expression->Value.expression() != nullptr && + Expression->Value.expression()->elements().size() == 2 && + Expression->Value.expression()->elements()[0] == 0x1005U && CFI != nullptr && + Function->cfiInfo().instruction(CFI->Index) != nullptr && + Function->cfiInfo().instruction(CFI->Index)->operation() == + rcc::MachineCFIOperation::DefCFA && + Metadata->preInstrSymbol() == "before" && Metadata->postInstrSymbol() == "after" && + Metadata->heapAllocMarker().has_value() && Metadata->pcSections().has_value() && + Metadata->mmra().has_value() && Metadata->cfiType() == 17 && + Metadata->deactivationSymbol() == "guard" && Metadata->debugInstrNumber() == 9 && + Metadata->debugLocation().has_value() && + Metadata->debugLocation()->inlineLocation() != nullptr && + Metadata->debugLocation()->inlineLocation()->inlineChain().size() == 2 && + Metadata->debugLocation()->inlineLocation()->inlineChain()[0].Line == 42 && + Metadata->debugLocation()->inlineLocation()->inlineChain()[0].Column == 7 && + Metadata->debugLocation()->inlineLocation()->inlineChain()[0].IsImplicitCode && + Metadata->debugLocation()->inlineLocation()->inlineChain()[0].AtomGroup == 3 && + Metadata->debugLocation()->inlineLocation()->inlineChain()[0].AtomRank == 2 && + Metadata->debugLocation()->inlineLocation()->terminalInlinedAt() == + rcc::MachineMetadataReference::embeddedIR(0), + "metadata, debug expressions, and CFI operands must retain structured semantics"); + + const rcc::MachineInstr *Load = Metadata->next(); + Context.expect(Load->memOperands().size() == 1 && Load->memOperands().front()->isLoad() && + Load->memOperands().front()->description().Size == + *rcc::MemorySize::fixed(8) && + Load->memOperands().front()->description().Align.bytes() == 8 && + Load->memOperands().front()->description().TBAA.has_value(), + "machine memory operands must retain access, size, alignment, and metadata"); + + const rcc::MachineInstr *BundleHeader = Exit->firstInstruction()->next(); + const rcc::MachineInstr *BundleMember = BundleHeader->next(); + Context.expect(BundleHeader->flags().has(rcc::MachineInstrFlag::BundledWithSucc) && + BundleMember->flags().has(rcc::MachineInstrFlag::BundledWithPred), + "instruction bundle braces must produce reciprocal layout flags"); + + auto Printed = rcc::mir::printMachineFunctionBody(*Function, *Target, ParserContext); + Context.expect(Printed.has_value(), "complete MIR body printing must accept the parsed function"); + if (!Printed) { + std::cerr << "error: " << Printed.error().message() << '\n'; + return; + } + + auto RoundTripFunction = createFunction(Context, 2); + if (!RoundTripFunction) + return; + auto RoundTripMetadata = + RoundTripFunction->metadata().addNode({.Slot = 100, .IsDistinct = false, .Elements = {}}); + Context.expect(RoundTripMetadata.has_value(), "round-trip metadata fixture must be valid"); + if (!RoundTripMetadata) + return; + rcc::mir::MIParser RoundTripParser(*RoundTripFunction, *Target, "round-trip.mir", *Printed, + ParserContext); + const auto RoundTrip = RoundTripParser.parse(); + Context.expect(RoundTrip.has_value() && !RoundTripParser.failed(), + "the complete body printer output must parse successfully"); + if (!RoundTrip) { + std::cerr << *Printed << '\n'; + for (const auto &Diagnostic : RoundTripParser.diagnostics()) + std::cerr << Diagnostic.Category << ": " << Diagnostic.Message << '\n'; + return; + } + auto PrintedAgain = + rcc::mir::printMachineFunctionBody(*RoundTripFunction, *Target, ParserContext); + Context.expect(PrintedAgain.has_value() && *PrintedAgain == *Printed, + "complete MIR body parse-print-parse must be deterministic"); +} + +void expectParseError(TestContext &Context, const rcc::TargetDescription &Target, std::string Body, + std::string_view Message) { + auto Function = createFunction(Context, 10); + if (!Function) + return; + rcc::mir::MIParser Parser(*Function, Target, "invalid.mir", std::move(Body)); + const auto Parsed = Parser.parse(); + const bool IsExpectedDiagnostic = + !Parsed && Parser.failed() && Parser.diagnostics().size() == 1 && + Parser.diagnostics().front().Category == "mir-parser" && + Parser.diagnostics().front().Message.find(Message) != std::string::npos; + Context.expect(IsExpectedDiagnostic, + "invalid MIR body must produce one stable parser diagnostic"); + if (!IsExpectedDiagnostic) { + for (const auto &Diagnostic : Parser.diagnostics()) + std::cerr << Diagnostic.Category << ": " << Diagnostic.Message << '\n'; + if (!Parsed) + std::cerr << "error: " << Parsed.error().message() << '\n'; + } +} + +void testDiagnostics(TestContext &Context) { + auto Target = createTarget(); + Context.expect(Target.has_value(), "diagnostic target description must be valid"); + if (!Target) + std::cerr << "error: " << Target.error().message() << '\n'; + if (!Target) + return; + + expectParseError(Context, *Target, "bb.0:\n TEST_BRANCH %bb.9\n", + "undefined machine basic block"); + expectParseError(Context, *Target, "bb.0:\n TEST_NOP\nbb.0:\n TEST_NOP\n", + "redefinition of machine basic block"); + expectParseError(Context, *Target, + "bb.0:\n %0:gpr64 = TEST_ADDI $g0, " + "target-flags(no-such-flag) 1\n", + "unknown target operand flag"); + expectParseError(Context, *Target, " bb.0:\n TEST_NOP\n", + "basic block definition must be at the start of a line"); +} + +} // namespace + +int main() { + TestContext Context; + testTwoPassBodyParsing(Context); + testDiagnostics(Context); + return Context.result(); +} -- cgit v1.2.3