[CodeGen] Add machine metadata graphs

Model ordered function-local metadata tuples with explicit embedded-IR and MachineFunction reference scopes. Preserve slot zero, distinct nodes, forward references, and cyclic graphs while verifying function-local closure and cloning the graph deterministically.

4 files changed, 125 insertions, 0 deletions

diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 3625473..ec95c3c 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -19,6 +19,7 @@ set(
   MachineInstr.cpp
   MachineJumpTableInfo.cpp
   MachineMemOperand.cpp
+  MachineMetadata.cpp
   MachineOperand.cpp
   MachineRegisterInfo.cpp
   MachineVerifier.cpp
@@ -50,6 +51,7 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineInstr.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineJumpTableInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMetadata.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOperand.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineVerifier.h"
@@ -110,6 +112,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
@@ -141,6 +144,7 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
diff --git a/backend/lib/CodeGen/MachineFunctionCloner.cpp b/backend/lib/CodeGen/MachineFunctionCloner.cpp
index 2f99341..e12e33e 100644
--- a/backend/lib/CodeGen/MachineFunctionCloner.cpp
+++ b/backend/lib/CodeGen/MachineFunctionCloner.cpp
@@ -626,6 +626,10 @@ Expected<MachineFunctionCloneResult> cloneMachineFunction(const MachineFunction
   if (!Records)
     return std::unexpected(Records.error());
   Result.ClonedFunction->records() = std::move(*Records);
+  auto Metadata = Source.metadata().clone();
+  if (!Metadata)
+    return std::unexpected(Metadata.error());
+  Result.ClonedFunction->metadata() = std::move(*Metadata);
   Result.ClonedFunction->properties() = Source.properties();
   Result.ClonedFunction->attributes() = Source.attributes();
   auto DestinationVerification = MachineVerifier::verify(*Result.ClonedFunction, Target);
diff --git a/backend/lib/CodeGen/MachineMetadata.cpp b/backend/lib/CodeGen/MachineMetadata.cpp
new file mode 100644
index 0000000..24a04e9
--- /dev/null
+++ b/backend/lib/CodeGen/MachineMetadata.cpp
@@ -0,0 +1,114 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineMetadata.h"
+
+#include <cstddef>
+#include <string>
+#include <unordered_set>
+#include <utility>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] Expected<void> verifyNodeElements(const MachineMetadataNode &Node) {
+  for (const MachineMetadataElement &Element : Node.Elements) {
+    if (!Element.isValid()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "machine metadata tuple contains an invalid element");
+    }
+    const MachineMetadataReference *Reference = Element.reference();
+    if (Reference != nullptr && !Reference->isValid()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "machine metadata tuple contains an invalid reference");
+    }
+  }
+  return {};
+}
+
+} // namespace
+
+Expected<MachineMetadataElement>
+MachineMetadataElement::reference(MachineMetadataReference Reference) {
+  if (!Reference.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine metadata element reference must be valid");
+  }
+  return MachineMetadataElement(Reference);
+}
+
+MachineMetadataElement MachineMetadataElement::string(std::string Value) {
+  return MachineMetadataElement(std::move(Value));
+}
+
+Expected<void> MachineMetadataInfo::addNode(MachineMetadataNode Node) {
+  auto Verification = verifyNodeElements(Node);
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  if (SlotToIndex.contains(Node.Slot)) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine metadata slot is already defined");
+  }
+
+  const std::size_t Index = Nodes.size();
+  SlotToIndex.emplace(Node.Slot, Index);
+  Nodes.push_back(std::move(Node));
+  return {};
+}
+
+const MachineMetadataNode *MachineMetadataInfo::node(std::uint32_t Slot) const noexcept {
+  const auto Position = SlotToIndex.find(Slot);
+  if (Position == SlotToIndex.end())
+    return nullptr;
+  return &Nodes[Position->second];
+}
+
+Expected<void> MachineMetadataInfo::verify() const {
+  if (SlotToIndex.size() != Nodes.size()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "machine metadata slot index has an inconsistent size");
+  }
+
+  std::unordered_set<std::uint32_t> Slots;
+  for (std::size_t Index = 0; Index < Nodes.size(); ++Index) {
+    const MachineMetadataNode &Node = Nodes[Index];
+    if (!Slots.insert(Node.Slot).second) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "machine metadata contains duplicate slot definitions");
+    }
+    const auto Position = SlotToIndex.find(Node.Slot);
+    if (Position == SlotToIndex.end() || Position->second != Index) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "machine metadata slot index is inconsistent");
+    }
+    auto ElementVerification = verifyNodeElements(Node);
+    if (!ElementVerification)
+      return ElementVerification;
+  }
+
+  for (const MachineMetadataNode &Node : Nodes) {
+    for (const MachineMetadataElement &Element : Node.Elements) {
+      const MachineMetadataReference *Reference = Element.reference();
+      if (Reference != nullptr && Reference->scope() == MachineMetadataScope::MachineFunction &&
+          !Slots.contains(Reference->slot())) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "machine metadata tuple references an undefined function slot");
+      }
+    }
+  }
+  return {};
+}
+
+Expected<MachineMetadataInfo> MachineMetadataInfo::clone() const {
+  auto Verification = verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+
+  MachineMetadataInfo Result;
+  for (const MachineMetadataNode &Node : Nodes) {
+    auto AddResult = Result.addNode(Node);
+    if (!AddResult)
+      return std::unexpected(AddResult.error());
+  }
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp
index 2fbbd38..2a29343 100644
--- a/backend/lib/CodeGen/MachineVerifier.cpp
+++ b/backend/lib/CodeGen/MachineVerifier.cpp
@@ -37,6 +37,9 @@ public:
     auto AttributeResult = Function.attributes().verify();
     if (!AttributeResult)
       return failWith("function attributes", AttributeResult.error());
+    auto MetadataResult = Function.metadata().verify();
+    if (!MetadataResult)
+      return failWith("machine metadata", MetadataResult.error());
     if (Function.targetState().hasValue()) {
       auto TargetStateResult = Function.targetState().verify();
       if (!TargetStateResult)