[CodeGen] Add machine function records

Represent callee-saved registers, call-site information, called globals, and prefetch targets in the core MachineIR model. Verify target and instruction references and remap StableIDs during explicit function cloning.

8 files changed, 724 insertions, 0 deletions

diff --git a/backend/include/rcc/CodeGen/MachineFunction.h b/backend/include/rcc/CodeGen/MachineFunction.h
index 4ed660d..c067ee1 100644
--- a/backend/include/rcc/CodeGen/MachineFunction.h
+++ b/backend/include/rcc/CodeGen/MachineFunction.h
@@ -8,6 +8,7 @@
 #include "rcc/CodeGen/MachineFrameInfo.h"
 #include "rcc/CodeGen/MachineFunctionAttributes.h"
 #include "rcc/CodeGen/MachineFunctionProperties.h"
+#include "rcc/CodeGen/MachineFunctionRecords.h"
 #include "rcc/CodeGen/MachineJumpTableInfo.h"
 #include "rcc/CodeGen/MachineRegisterInfo.h"
 #include "rcc/CodeGen/StableID.h"
@@ -98,6 +99,14 @@ public:
     return Attributes;
   }
 
+  [[nodiscard]] MachineFunctionRecords &records() noexcept {
+    return Records;
+  }
+
+  [[nodiscard]] const MachineFunctionRecords &records() const noexcept {
+    return Records;
+  }
+
   [[nodiscard]] const TargetFunctionState &targetState() const noexcept {
     return TargetState;
   }
@@ -176,6 +185,7 @@ private:
   MachineJumpTableInfo JumpTables;
   MachineFunctionProperties Properties;
   MachineFunctionAttributes Attributes;
+  MachineFunctionRecords Records;
   TargetFunctionState TargetState;
   MachineCompilationStatus CompilationStatus;
   MachineBasicBlock *FirstBlock = nullptr;
diff --git a/backend/include/rcc/CodeGen/MachineFunctionRecords.h b/backend/include/rcc/CodeGen/MachineFunctionRecords.h
new file mode 100644
index 0000000..7050072
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineFunctionRecords.h
@@ -0,0 +1,114 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEFUNCTIONRECORDS_H
+#define RCC_CODEGEN_MACHINEFUNCTIONRECORDS_H
+
+#include "rcc/CodeGen/MachineBasicBlockAttributes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+#include <optional>
+#include <span>
+#include <string>
+#include <vector>
+
+namespace rcc {
+
+class MachineFunctionCloneContext;
+
+struct MachineCallSiteArgument final {
+  PhysicalRegister Reg;
+  std::uint16_t ArgumentNumber = 0;
+
+  friend constexpr bool operator==(MachineCallSiteArgument Left,
+                                   MachineCallSiteArgument Right) noexcept = default;
+};
+
+struct MachineCallSiteInfo final {
+  MachineInstrStableID CallInstruction;
+  std::vector<MachineCallSiteArgument> ForwardedArguments;
+  std::vector<std::uint64_t> CalleeTypeIDs;
+
+  friend bool operator==(const MachineCallSiteInfo &Left,
+                         const MachineCallSiteInfo &Right) = default;
+};
+
+struct MachineCalledGlobal final {
+  MachineInstrStableID CallInstruction;
+  std::string Callee;
+  std::uint32_t Flags = 0;
+
+  friend bool operator==(const MachineCalledGlobal &Left,
+                         const MachineCalledGlobal &Right) = default;
+};
+
+struct MachinePrefetchTarget final {
+  MachineBasicBlockProfileID Block;
+  std::uint32_t CallsiteIndex = 0;
+
+  friend constexpr bool operator==(MachinePrefetchTarget Left,
+                                   MachinePrefetchTarget Right) noexcept = default;
+};
+
+class MachineFunctionRecords final {
+public:
+  MachineFunctionRecords() = default;
+  MachineFunctionRecords(const MachineFunctionRecords &) = delete;
+  MachineFunctionRecords &operator=(const MachineFunctionRecords &) = delete;
+  MachineFunctionRecords(MachineFunctionRecords &&) noexcept = default;
+  MachineFunctionRecords &operator=(MachineFunctionRecords &&) noexcept = default;
+  ~MachineFunctionRecords() = default;
+
+  [[nodiscard]] bool hasCalleeSavedRegisters() const noexcept {
+    return CalleeSavedRegisters.has_value();
+  }
+
+  [[nodiscard]] std::span<const PhysicalRegister> calleeSavedRegisters() const noexcept {
+    if (!CalleeSavedRegisters)
+      return {};
+    return *CalleeSavedRegisters;
+  }
+
+  [[nodiscard]] Expected<void> setCalleeSavedRegisters(std::vector<PhysicalRegister> Registers);
+
+  void clearCalleeSavedRegisters() noexcept {
+    CalleeSavedRegisters.reset();
+  }
+
+  [[nodiscard]] std::span<const MachineCallSiteInfo> callSites() const noexcept {
+    return CallSites;
+  }
+
+  [[nodiscard]] Expected<void> addCallSite(MachineCallSiteInfo CallSite);
+
+  [[nodiscard]] std::span<const MachineCalledGlobal> calledGlobals() const noexcept {
+    return CalledGlobals;
+  }
+
+  [[nodiscard]] Expected<void> addCalledGlobal(MachineCalledGlobal CalledGlobal);
+
+  [[nodiscard]] std::span<const MachinePrefetchTarget> prefetchTargets() const noexcept {
+    return PrefetchTargets;
+  }
+
+  [[nodiscard]] Expected<void> addPrefetchTarget(MachinePrefetchTarget Target);
+
+  [[nodiscard]] Expected<void> verify() const;
+  [[nodiscard]] Expected<MachineFunctionRecords>
+  clone(const MachineFunctionCloneContext &CloneContext) const;
+
+  friend bool operator==(const MachineFunctionRecords &Left,
+                         const MachineFunctionRecords &Right) = default;
+
+private:
+  std::optional<std::vector<PhysicalRegister>> CalleeSavedRegisters;
+  std::vector<MachineCallSiteInfo> CallSites;
+  std::vector<MachineCalledGlobal> CalledGlobals;
+  std::vector<MachinePrefetchTarget> PrefetchTargets;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEFUNCTIONRECORDS_H
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 35e9a23..3625473 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -23,6 +23,7 @@ set(
   MachineRegisterInfo.cpp
   MachineVerifier.cpp
   MachineFunctionProperties.cpp
+  MachineFunctionRecords.cpp
   Register.cpp
   RegisterMask.cpp
   TargetConstant.cpp
@@ -53,6 +54,7 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineVerifier.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionRecords.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Register.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/StableID.h"
@@ -112,6 +114,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetConstant.cpp"
@@ -142,6 +145,7 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetConstant.cpp"
diff --git a/backend/lib/CodeGen/MachineFunctionCloner.cpp b/backend/lib/CodeGen/MachineFunctionCloner.cpp
index 971ef3c..aae74ff 100644
--- a/backend/lib/CodeGen/MachineFunctionCloner.cpp
+++ b/backend/lib/CodeGen/MachineFunctionCloner.cpp
@@ -616,6 +616,10 @@ Expected<MachineFunctionCloneResult> cloneMachineFunction(const MachineFunction
   if (!CompilationStatus)
     return std::unexpected(CompilationStatus.error());
   Result.ClonedFunction->compilationStatus() = std::move(*CompilationStatus);
+  auto Records = Source.records().clone(CloneContext);
+  if (!Records)
+    return std::unexpected(Records.error());
+  Result.ClonedFunction->records() = std::move(*Records);
   Result.ClonedFunction->properties() = Source.properties();
   Result.ClonedFunction->attributes() = Source.attributes();
   auto DestinationVerification = MachineVerifier::verify(*Result.ClonedFunction, Target);
diff --git a/backend/lib/CodeGen/MachineFunctionRecords.cpp b/backend/lib/CodeGen/MachineFunctionRecords.cpp
new file mode 100644
index 0000000..be0d936
--- /dev/null
+++ b/backend/lib/CodeGen/MachineFunctionRecords.cpp
@@ -0,0 +1,187 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineFunctionRecords.h"
+
+#include "rcc/CodeGen/MachineFunctionCloner.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <string>
+#include <unordered_set>
+#include <utility>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] Expected<void>
+verifyCalleeSavedRegisters(std::span<const PhysicalRegister> Registers) {
+  std::unordered_set<PhysicalRegister> Seen;
+  for (const PhysicalRegister Reg : Registers) {
+    if (!Reg.isValid()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "callee-saved register list contains noreg");
+    }
+    if (!Seen.insert(Reg).second) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "callee-saved register list contains a duplicate register");
+    }
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> verifyCallSite(const MachineCallSiteInfo &CallSite) {
+  if (!CallSite.CallInstruction.isValid()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "call-site record has an invalid instruction StableID");
+  }
+  for (const MachineCallSiteArgument &Argument : CallSite.ForwardedArguments) {
+    if (!Argument.Reg.isValid()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "call-site forwarded argument contains noreg");
+    }
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> verifyCalledGlobal(const MachineCalledGlobal &CalledGlobal) {
+  if (!CalledGlobal.CallInstruction.isValid()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "called-global record has an invalid instruction StableID");
+  }
+  if (CalledGlobal.Callee.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "called-global record has an empty callee name");
+  }
+  return {};
+}
+
+} // namespace
+
+Expected<void>
+MachineFunctionRecords::setCalleeSavedRegisters(std::vector<PhysicalRegister> Registers) {
+  auto Verification = verifyCalleeSavedRegisters(Registers);
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  CalleeSavedRegisters = std::move(Registers);
+  return {};
+}
+
+Expected<void> MachineFunctionRecords::addCallSite(MachineCallSiteInfo CallSite) {
+  auto Verification = verifyCallSite(CallSite);
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  if (std::ranges::any_of(CallSites, [&CallSite](const MachineCallSiteInfo &Existing) {
+        return Existing.CallInstruction == CallSite.CallInstruction;
+      })) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "call instruction already has a call-site record");
+  }
+  CallSites.push_back(std::move(CallSite));
+  return {};
+}
+
+Expected<void> MachineFunctionRecords::addCalledGlobal(MachineCalledGlobal CalledGlobal) {
+  auto Verification = verifyCalledGlobal(CalledGlobal);
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  if (std::ranges::any_of(CalledGlobals, [&CalledGlobal](const MachineCalledGlobal &Existing) {
+        return Existing.CallInstruction == CalledGlobal.CallInstruction;
+      })) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "call instruction already has a called-global record");
+  }
+  CalledGlobals.push_back(std::move(CalledGlobal));
+  return {};
+}
+
+Expected<void> MachineFunctionRecords::addPrefetchTarget(MachinePrefetchTarget Target) {
+  if (std::ranges::find(PrefetchTargets, Target) != PrefetchTargets.end()) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "prefetch target is already recorded");
+  }
+  PrefetchTargets.push_back(Target);
+  return {};
+}
+
+Expected<void> MachineFunctionRecords::verify() const {
+  if (CalleeSavedRegisters) {
+    auto CalleeSavedVerification = verifyCalleeSavedRegisters(*CalleeSavedRegisters);
+    if (!CalleeSavedVerification)
+      return CalleeSavedVerification;
+  }
+
+  std::unordered_set<MachineInstrStableID> CallInstructions;
+  for (const MachineCallSiteInfo &CallSite : CallSites) {
+    auto CallSiteVerification = verifyCallSite(CallSite);
+    if (!CallSiteVerification)
+      return CallSiteVerification;
+    if (!CallInstructions.insert(CallSite.CallInstruction).second) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "multiple call-site records reference one call instruction");
+    }
+  }
+
+  std::unordered_set<MachineInstrStableID> CalledGlobalInstructions;
+  for (const MachineCalledGlobal &CalledGlobal : CalledGlobals) {
+    auto CalledGlobalVerification = verifyCalledGlobal(CalledGlobal);
+    if (!CalledGlobalVerification)
+      return CalledGlobalVerification;
+    if (!CalledGlobalInstructions.insert(CalledGlobal.CallInstruction).second) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "multiple called-global records reference one call instruction");
+    }
+  }
+
+  for (std::size_t Index = 0; Index < PrefetchTargets.size(); ++Index) {
+    if (std::ranges::find(PrefetchTargets.begin() + static_cast<std::ptrdiff_t>(Index + 1),
+                          PrefetchTargets.end(), PrefetchTargets[Index]) != PrefetchTargets.end()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "prefetch target list contains a duplicate entry");
+    }
+  }
+  return {};
+}
+
+Expected<MachineFunctionRecords>
+MachineFunctionRecords::clone(const MachineFunctionCloneContext &CloneContext) const {
+  auto Verification = verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+
+  MachineFunctionRecords Result;
+  if (CalleeSavedRegisters) {
+    auto SetResult = Result.setCalleeSavedRegisters(*CalleeSavedRegisters);
+    if (!SetResult)
+      return std::unexpected(SetResult.error());
+  }
+
+  for (const MachineCallSiteInfo &Source : CallSites) {
+    auto Instruction = CloneContext.mapInstructionStableID(Source.CallInstruction);
+    if (!Instruction)
+      return std::unexpected(Instruction.error());
+    MachineCallSiteInfo Destination = Source;
+    Destination.CallInstruction = *Instruction;
+    auto AddResult = Result.addCallSite(std::move(Destination));
+    if (!AddResult)
+      return std::unexpected(AddResult.error());
+  }
+
+  for (const MachineCalledGlobal &Source : CalledGlobals) {
+    auto Instruction = CloneContext.mapInstructionStableID(Source.CallInstruction);
+    if (!Instruction)
+      return std::unexpected(Instruction.error());
+    MachineCalledGlobal Destination = Source;
+    Destination.CallInstruction = *Instruction;
+    auto AddResult = Result.addCalledGlobal(std::move(Destination));
+    if (!AddResult)
+      return std::unexpected(AddResult.error());
+  }
+
+  for (const MachinePrefetchTarget Source : PrefetchTargets) {
+    auto AddResult = Result.addPrefetchTarget(Source);
+    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 905d685..d1c6989 100644
--- a/backend/lib/CodeGen/MachineVerifier.cpp
+++ b/backend/lib/CodeGen/MachineVerifier.cpp
@@ -54,6 +54,9 @@ public:
     auto LayoutResult = verifyBlockLayout();
     if (!LayoutResult)
       return LayoutResult;
+    auto RecordResult = verifyFunctionRecords();
+    if (!RecordResult)
+      return RecordResult;
     auto CompilationStatusResult = verifyCompilationStatus();
     if (!CompilationStatusResult)
       return CompilationStatusResult;
@@ -177,6 +180,12 @@ private:
       if (Block->denseNumber() != LayoutIndex || Block->layoutIndex() != LayoutIndex) {
         return fail("block dense number or layout index is stale");
       }
+      if (const auto &ProfileID = Block->attributes().profileID()) {
+        const std::uint64_t Key = (static_cast<std::uint64_t>(ProfileID->BaseID) << 32U) |
+                                  static_cast<std::uint64_t>(ProfileID->CloneID);
+        if (!LinkedBlockProfileIDs.insert(Key).second)
+          return fail("multiple linked blocks have the same bb_id");
+      }
 
       auto InstructionResult = verifyInstructionLayout(*Block);
       if (!InstructionResult)
@@ -237,6 +246,7 @@ private:
       if (!LinkedInstructions.insert(Instruction).second)
         return fail("instruction layout contains a cycle or duplicate instruction");
       LinkedInstructionIDs.insert(Instruction->stableID());
+      LinkedInstructionsByID.emplace(Instruction->stableID(), Instruction);
       if (Instruction->parent() != &Block || Instruction->previous() != Previous) {
         return fail("instruction parent or previous link is inconsistent");
       }
@@ -333,6 +343,62 @@ private:
     return {};
   }
 
+  [[nodiscard]] Expected<void> verifyFunctionRecords() const {
+    const MachineFunctionRecords &Records = Function.records();
+    auto Verification = Records.verify();
+    if (!Verification)
+      return failWith("function records", Verification.error());
+
+    for (const PhysicalRegister Reg : Records.calleeSavedRegisters()) {
+      if (!Target.registers().isKnownPhysicalRegister(Reg))
+        return fail("callee-saved register list references an unknown physical register");
+    }
+
+    auto VerifyCall = [this](MachineInstrStableID ID,
+                             std::string_view Kind) -> Expected<const MachineInstr *> {
+      const auto Position = LinkedInstructionsByID.find(ID);
+      if (Position == LinkedInstructionsByID.end()) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "machine function '" + std::string(Function.name()) +
+                                  "': " + std::string(Kind) +
+                                  " references a detached or unknown instruction");
+      }
+      const InstructionDescriptor *Descriptor =
+          Target.instructionDescriptor(Position->second->opcode());
+      if (Descriptor == nullptr || !Descriptor->Flags.has(InstructionFlag::Call)) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "machine function '" + std::string(Function.name()) +
+                                  "': " + std::string(Kind) + " references a non-call instruction");
+      }
+      return Position->second;
+    };
+
+    for (const MachineCallSiteInfo &CallSite : Records.callSites()) {
+      auto Call = VerifyCall(CallSite.CallInstruction, "call-site record");
+      if (!Call)
+        return std::unexpected(Call.error());
+      for (const MachineCallSiteArgument &Argument : CallSite.ForwardedArguments) {
+        if (!Target.registers().isKnownPhysicalRegister(Argument.Reg)) {
+          return fail("call-site record references an unknown forwarded physical register");
+        }
+      }
+    }
+
+    for (const MachineCalledGlobal &CalledGlobal : Records.calledGlobals()) {
+      auto Call = VerifyCall(CalledGlobal.CallInstruction, "called-global record");
+      if (!Call)
+        return std::unexpected(Call.error());
+    }
+
+    for (const MachinePrefetchTarget &Prefetch : Records.prefetchTargets()) {
+      const std::uint64_t Key = (static_cast<std::uint64_t>(Prefetch.Block.BaseID) << 32U) |
+                                static_cast<std::uint64_t>(Prefetch.Block.CloneID);
+      if (!LinkedBlockProfileIDs.contains(Key))
+        return fail("prefetch target references an unknown bb_id");
+    }
+    return {};
+  }
+
   [[nodiscard]] Expected<void> verifyCompilationStatus() const {
     const MachineCompilationStatus &Status = Function.compilationStatus();
     auto Verification = Status.verify();
@@ -596,6 +662,8 @@ private:
   std::unordered_set<const MachineInstr *> RegisteredInstructions;
   std::unordered_set<const MachineInstr *> LinkedInstructions;
   std::unordered_set<MachineInstrStableID> LinkedInstructionIDs;
+  std::unordered_map<MachineInstrStableID, const MachineInstr *> LinkedInstructionsByID;
+  std::unordered_set<std::uint64_t> LinkedBlockProfileIDs;
   std::unordered_set<const MachineMemOperand *> RegisteredMemOperands;
   std::unordered_map<Register, std::size_t> VirtualDefCounts;
   bool HasPhi = false;
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index ff38ed7..92bed00 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -9,6 +9,7 @@ set(
   MachineConstantPoolTest.cpp
   MachineFrameInfoTest.cpp
   MachineFunctionClonerTest.cpp
+  MachineFunctionRecordsTest.cpp
   MachineIRAttributesTest.cpp
   MachineIRBuilderTest.cpp
   MachineIRCoreTest.cpp
@@ -99,6 +100,21 @@ add_test(
   COMMAND RCCBackendCodeGenMachineFunctionClonerTests
 )
 
+add_executable(
+  RCCBackendCodeGenMachineFunctionRecordsTests
+  MachineFunctionRecordsTest.cpp
+)
+rcc_backend_configure_target(RCCBackendCodeGenMachineFunctionRecordsTests)
+target_link_libraries(
+  RCCBackendCodeGenMachineFunctionRecordsTests
+  PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget
+)
+
+add_test(
+  NAME RCCBackend.CodeGen.MachineFunctionRecords
+  COMMAND RCCBackendCodeGenMachineFunctionRecordsTests
+)
+
 add_executable(RCCBackendCodeGenMachineIRBuilderTests MachineIRBuilderTest.cpp)
 rcc_backend_configure_target(RCCBackendCodeGenMachineIRBuilderTests)
 target_link_libraries(
@@ -218,6 +234,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineConstantPoolTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFrameInfoTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionClonerTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecordsTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRAttributesTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilderTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
@@ -237,6 +254,7 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineConstantPoolTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFrameInfoTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionClonerTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecordsTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRAttributesTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilderTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
diff --git a/backend/unittests/CodeGen/MachineFunctionRecordsTest.cpp b/backend/unittests/CodeGen/MachineFunctionRecordsTest.cpp
new file mode 100644
index 0000000..4f41b39
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineFunctionRecordsTest.cpp
@@ -0,0 +1,319 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineFunctionRecords.h"
+
+#include "Target/TestTarget.h"
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionCloner.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace {
+
+constexpr std::uint32_t NopOpcode = 1;
+constexpr std::uint32_t CallOpcode = 2;
+
+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::PhysicalRegister phys(std::uint32_t Number) {
+  auto Reg = rcc::PhysicalRegister::create(Number);
+  return Reg ? *Reg : rcc::PhysicalRegister{};
+}
+
+[[nodiscard]] rcc::Expected<rcc::TargetDescription> createTarget() {
+  rcc::InstructionDescriptor Nop;
+  Nop.InstructionOpcode = rcc::Opcode::fromValue(NopOpcode);
+  Nop.Name = "TEST_NOP";
+  Nop.Flags = {rcc::InstructionFlag::ProducesCode};
+
+  rcc::InstructionDescriptor Call;
+  Call.InstructionOpcode = rcc::Opcode::fromValue(CallOpcode);
+  Call.Name = "TEST_CALL";
+  Call.Flags = {rcc::InstructionFlag::Call, rcc::InstructionFlag::HasSideEffects,
+                rcc::InstructionFlag::ProducesCode};
+
+  std::vector<rcc::InstructionDescriptor> Descriptors;
+  Descriptors.push_back(std::move(Nop));
+  Descriptors.push_back(std::move(Call));
+  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<rcc::MachineFunction>
+createFunction(TestContext &Context, std::uint64_t StableID, std::string Name) {
+  auto Function = rcc::MachineFunction::create(std::move(Name),
+                                               rcc::MachineFunctionStableID::fromValue(StableID));
+  Context.expect(Function.has_value(), "machine function creation must succeed");
+  if (!Function)
+    return nullptr;
+  return std::move(*Function);
+}
+
+[[nodiscard]] rcc::MachineBasicBlock *appendBlock(TestContext &Context,
+                                                  rcc::MachineFunction &Function) {
+  auto Block = Function.createBasicBlock();
+  Context.expect(Block.has_value(), "machine basic block creation must succeed");
+  if (!Block)
+    return nullptr;
+  Context.expect(Function.appendBlock(**Block).has_value(), "machine block linking must succeed");
+  return *Block;
+}
+
+[[nodiscard]] rcc::MachineInstr *appendInstruction(TestContext &Context,
+                                                   rcc::MachineFunction &Function,
+                                                   rcc::MachineBasicBlock &Block,
+                                                   std::uint32_t OpcodeValue) {
+  auto Instruction = Function.createInstruction(rcc::Opcode::fromValue(OpcodeValue));
+  Context.expect(Instruction.has_value(), "machine instruction creation must succeed");
+  if (!Instruction)
+    return nullptr;
+  Context.expect(Block.appendInstruction(**Instruction).has_value(),
+                 "machine instruction linking must succeed");
+  return *Instruction;
+}
+
+void testValueValidation(TestContext &Context) {
+  rcc::MachineFunctionRecords Records;
+  Context.expect(!Records.hasCalleeSavedRegisters() && Records.calleeSavedRegisters().empty(),
+                 "an absent callee-saved list must remain distinguishable");
+  Context.expect(Records.setCalleeSavedRegisters({}).has_value() &&
+                     Records.hasCalleeSavedRegisters() && Records.calleeSavedRegisters().empty(),
+                 "an explicit empty callee-saved list must remain present");
+  Records.clearCalleeSavedRegisters();
+
+  const rcc::PhysicalRegister G0 = phys(rcc::test::TestRegister::G0);
+  Context.expect(!Records.setCalleeSavedRegisters({G0, G0}),
+                 "duplicate callee-saved registers must be rejected");
+  Context.expect(!Records.addCallSite({}),
+                 "a call-site record must require a valid instruction StableID");
+  Context.expect(!Records.addCalledGlobal({
+                     .CallInstruction = rcc::MachineInstrStableID::fromValue(1),
+                     .Callee = {},
+                     .Flags = 0,
+                 }),
+                 "a called-global record must require a nonempty callee");
+
+  const rcc::MachinePrefetchTarget Target{
+      .Block = {.BaseID = 7, .CloneID = 3},
+      .CallsiteIndex = 4,
+  };
+  Context.expect(Records.addPrefetchTarget(Target).has_value() &&
+                     !Records.addPrefetchTarget(Target),
+                 "duplicate structured prefetch targets must be rejected");
+}
+
+void testVerifierAndClone(TestContext &Context) {
+  auto Target = createTarget();
+  auto Function = createFunction(Context, 1, "records");
+  if (!Target || Function == nullptr)
+    return;
+
+  rcc::MachineBasicBlock *Block = appendBlock(Context, *Function);
+  if (Block == nullptr)
+    return;
+  Block->attributes().setProfileID({.BaseID = 19, .CloneID = 2});
+  rcc::MachineInstr *Call = appendInstruction(Context, *Function, *Block, CallOpcode);
+  if (Call == nullptr)
+    return;
+
+  const rcc::PhysicalRegister G0 = phys(rcc::test::TestRegister::G0);
+  const rcc::PhysicalRegister G1 = phys(rcc::test::TestRegister::G1);
+  Context.expect(Function->records().setCalleeSavedRegisters({G0, G1}).has_value(),
+                 "callee-saved registers must be stored");
+  Context.expect(Function->records()
+                     .addCallSite({
+                         .CallInstruction = Call->stableID(),
+                         .ForwardedArguments =
+                             {
+                                 {.Reg = G0, .ArgumentNumber = 0},
+                                 {.Reg = G1, .ArgumentNumber = 0},
+                             },
+                         .CalleeTypeIDs = {0x11, 0x22},
+                     })
+                     .has_value(),
+                 "structured call-site information must be stored");
+  Context.expect(Function->records()
+                     .addCalledGlobal({
+                         .CallInstruction = Call->stableID(),
+                         .Callee = "callee",
+                         .Flags = 5,
+                     })
+                     .has_value(),
+                 "structured called-global information must be stored");
+  Context.expect(Function->records()
+                     .addPrefetchTarget({
+                         .Block = {.BaseID = 19, .CloneID = 2},
+                         .CallsiteIndex = 8,
+                     })
+                     .has_value(),
+                 "structured prefetch target information must be stored");
+  Context.expect(rcc::MachineVerifier::verify(*Function, *Target).has_value(),
+                 "well-formed function records must pass unified verification");
+
+  auto Clone =
+      rcc::cloneMachineFunction(*Function, *Target,
+                                {
+                                    .NewStableID = rcc::MachineFunctionStableID::fromValue(2),
+                                    .NewName = std::string("records.clone"),
+                                });
+  Context.expect(Clone.has_value(), "machine function records must support deep cloning");
+  if (!Clone)
+    return;
+
+  const auto InstructionID = Clone->InstructionStableIDs.find(Call->stableID());
+  const rcc::MachineFunctionRecords &ClonedRecords = Clone->ClonedFunction->records();
+  Context.expect(InstructionID != Clone->InstructionStableIDs.end() &&
+                     ClonedRecords.hasCalleeSavedRegisters() &&
+                     ClonedRecords.calleeSavedRegisters().size() == 2 &&
+                     ClonedRecords.callSites().size() == 1 &&
+                     ClonedRecords.callSites()[0].CallInstruction == InstructionID->second &&
+                     ClonedRecords.callSites()[0].ForwardedArguments.size() == 2 &&
+                     ClonedRecords.callSites()[0].ForwardedArguments[1].ArgumentNumber == 0 &&
+                     ClonedRecords.callSites()[0].CalleeTypeIDs ==
+                         std::vector<std::uint64_t>({0x11, 0x22}) &&
+                     ClonedRecords.calledGlobals().size() == 1 &&
+                     ClonedRecords.calledGlobals()[0].CallInstruction == InstructionID->second &&
+                     ClonedRecords.calledGlobals()[0].Callee == "callee" &&
+                     ClonedRecords.calledGlobals()[0].Flags == 5 &&
+                     ClonedRecords.prefetchTargets().size() == 1 &&
+                     ClonedRecords.prefetchTargets()[0].Block ==
+                         rcc::MachineBasicBlockProfileID{.BaseID = 19, .CloneID = 2} &&
+                     ClonedRecords.prefetchTargets()[0].CallsiteIndex == 8,
+                 "deep clone must preserve records and remap instruction StableIDs");
+}
+
+void testCrossReferenceFailures(TestContext &Context) {
+  auto Target = createTarget();
+  if (!Target)
+    return;
+
+  {
+    auto Function = createFunction(Context, 10, "noncall");
+    if (Function == nullptr)
+      return;
+    rcc::MachineBasicBlock *Block = appendBlock(Context, *Function);
+    if (Block == nullptr)
+      return;
+    rcc::MachineInstr *Nop = appendInstruction(Context, *Function, *Block, NopOpcode);
+    if (Nop == nullptr)
+      return;
+    Context.expect(Function->records()
+                           .addCallSite({
+                               .CallInstruction = Nop->stableID(),
+                               .ForwardedArguments = {},
+                               .CalleeTypeIDs = {},
+                           })
+                           .has_value() &&
+                       !rcc::MachineVerifier::verify(*Function, *Target),
+                   "call-site records must reference instructions described as calls");
+  }
+
+  {
+    auto Function = createFunction(Context, 11, "detached");
+    if (Function == nullptr)
+      return;
+    rcc::MachineBasicBlock *Block = appendBlock(Context, *Function);
+    if (Block == nullptr)
+      return;
+    auto Detached = Function->createInstruction(rcc::Opcode::fromValue(CallOpcode));
+    Context.expect(Detached.has_value() &&
+                       Function->records()
+                           .addCalledGlobal({
+                               .CallInstruction = (*Detached)->stableID(),
+                               .Callee = "callee",
+                           })
+                           .has_value() &&
+                       !rcc::MachineVerifier::verify(*Function, *Target),
+                   "function records must not reference detached instructions");
+  }
+
+  {
+    auto Function = createFunction(Context, 12, "unknown-register");
+    if (Function == nullptr)
+      return;
+    rcc::MachineBasicBlock *Block = appendBlock(Context, *Function);
+    if (Block == nullptr)
+      return;
+    rcc::MachineInstr *Call = appendInstruction(Context, *Function, *Block, CallOpcode);
+    if (Call == nullptr)
+      return;
+    Context.expect(Function->records()
+                           .addCallSite({
+                               .CallInstruction = Call->stableID(),
+                               .ForwardedArguments = {{.Reg = phys(999), .ArgumentNumber = 0}},
+                               .CalleeTypeIDs = {},
+                           })
+                           .has_value() &&
+                       !rcc::MachineVerifier::verify(*Function, *Target),
+                   "call-site records must reject target-unknown physical registers");
+  }
+
+  {
+    auto Function = createFunction(Context, 13, "unknown-bbid");
+    if (Function == nullptr)
+      return;
+    rcc::MachineBasicBlock *Block = appendBlock(Context, *Function);
+    if (Block == nullptr)
+      return;
+    Context.expect(Function->records()
+                           .addPrefetchTarget({
+                               .Block = {.BaseID = 1, .CloneID = 0},
+                               .CallsiteIndex = 0,
+                           })
+                           .has_value() &&
+                       !rcc::MachineVerifier::verify(*Function, *Target),
+                   "prefetch targets must reference a live block bb_id");
+  }
+
+  {
+    auto Function = createFunction(Context, 14, "duplicate-bbid");
+    if (Function == nullptr)
+      return;
+    rcc::MachineBasicBlock *First = appendBlock(Context, *Function);
+    rcc::MachineBasicBlock *Second = appendBlock(Context, *Function);
+    if (First == nullptr || Second == nullptr)
+      return;
+    First->attributes().setProfileID({.BaseID = 3, .CloneID = 1});
+    Second->attributes().setProfileID({.BaseID = 3, .CloneID = 1});
+    Context.expect(!rcc::MachineVerifier::verify(*Function, *Target),
+                   "linked block bb_id values must be unique");
+  }
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testValueValidation(Context);
+  testVerifierAndClone(Context);
+  testCrossReferenceFailures(Context);
+  return Context.result();
+}