1 files changed, 323 insertions, 0 deletions
diff --git a/backend/lib/CodeGen/MachineFunctionRecords.cpp b/backend/lib/CodeGen/MachineFunctionRecords.cpp
new file mode 100644
index 0000000..18ac596
--- /dev/null
+++ b/backend/lib/CodeGen/MachineFunctionRecords.cpp
@@ -0,0 +1,323 @@
+// 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_map>
+#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 {};
+}
+
+[[nodiscard]] constexpr std::uint64_t
+debugReferenceKey(MachineDebugValueReference Reference) noexcept {
+  return (static_cast<std::uint64_t>(Reference.InstructionNumber) << 32U) |
+         static_cast<std::uint64_t>(Reference.OperandNumber);
+}
+
+[[nodiscard]] Expected<void>
+verifyDebugValueSubstitution(const MachineDebugValueSubstitution &Substitution) {
+  if (Substitution.Source.InstructionNumber == 0 ||
+      Substitution.Destination.InstructionNumber == 0) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "debug value substitution has a zero instruction number");
+  }
+  if (Substitution.Source.InstructionNumber == Substitution.Destination.InstructionNumber) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "debug value substitution cannot replace a value within one instruction");
+  }
+  if (Substitution.Source.OperandNumber == MachineDebugMemoryOperandNumber) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "debug value substitution cannot originate from the memory operand");
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> verifyEntryValue(const MachineEntryValueInfo &EntryValue) {
+  if (!EntryValue.Reg.isValid()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "entry-value record requires a physical register");
+  }
+  return EntryValue.DebugInfo.verifyStructure();
+}
+
+} // 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::replaceInstructionReference(MachineInstrStableID OldInstruction,
+                                                    MachineInstrStableID NewInstruction) {
+  if (!OldInstruction.isValid() || !NewInstruction.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "instruction-record replacement requires two valid stable IDs");
+  }
+  if (OldInstruction == NewInstruction)
+    return {};
+  for (const MachineCallSiteInfo &CallSite : CallSites) {
+    if (CallSite.CallInstruction == NewInstruction) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "replacement instruction already owns a call-site record");
+    }
+  }
+  for (const MachineCalledGlobal &CalledGlobal : CalledGlobals) {
+    if (CalledGlobal.CallInstruction == NewInstruction) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "replacement instruction already owns a called-global record");
+    }
+  }
+  for (MachineCallSiteInfo &CallSite : CallSites) {
+    if (CallSite.CallInstruction == OldInstruction)
+      CallSite.CallInstruction = NewInstruction;
+  }
+  for (MachineCalledGlobal &CalledGlobal : CalledGlobals) {
+    if (CalledGlobal.CallInstruction == OldInstruction)
+      CalledGlobal.CallInstruction = NewInstruction;
+  }
+  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::addDebugValueSubstitution(MachineDebugValueSubstitution Substitution) {
+  auto Verification = verifyDebugValueSubstitution(Substitution);
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  if (std::ranges::any_of(DebugValueSubstitutions,
+                          [&Substitution](const MachineDebugValueSubstitution &Existing) {
+                            return Existing.Source == Substitution.Source;
+                          })) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "debug value source already has a substitution");
+  }
+  DebugValueSubstitutions.push_back(Substitution);
+  return {};
+}
+
+Expected<void> MachineFunctionRecords::addEntryValue(MachineEntryValueInfo EntryValue) {
+  auto Verification = verifyEntryValue(EntryValue);
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  EntryValues.push_back(std::move(EntryValue));
+  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");
+    }
+  }
+
+  std::unordered_map<std::uint64_t, std::uint64_t> DebugSubstitutionEdges;
+  for (const MachineDebugValueSubstitution &Substitution : DebugValueSubstitutions) {
+    auto SubstitutionVerification = verifyDebugValueSubstitution(Substitution);
+    if (!SubstitutionVerification)
+      return SubstitutionVerification;
+    const std::uint64_t Source = debugReferenceKey(Substitution.Source);
+    const std::uint64_t Destination = debugReferenceKey(Substitution.Destination);
+    if (!DebugSubstitutionEdges.emplace(Source, Destination).second) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "multiple debug substitutions have the same source");
+    }
+  }
+
+  std::unordered_set<std::uint64_t> CompletedDebugReferences;
+  for (const auto &Edge : DebugSubstitutionEdges) {
+    const std::uint64_t Start = Edge.first;
+    std::unordered_set<std::uint64_t> Path;
+    std::uint64_t Current = Start;
+    while (!CompletedDebugReferences.contains(Current)) {
+      const auto Position = DebugSubstitutionEdges.find(Current);
+      if (Position == DebugSubstitutionEdges.end())
+        break;
+      if (!Path.insert(Current).second) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "debug value substitutions contain a cycle");
+      }
+      Current = Position->second;
+    }
+    CompletedDebugReferences.insert(Path.begin(), Path.end());
+  }
+
+  for (const MachineEntryValueInfo &EntryValue : EntryValues) {
+    auto EntryValueVerification = verifyEntryValue(EntryValue);
+    if (!EntryValueVerification)
+      return EntryValueVerification;
+  }
+  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());
+  }
+  for (const MachineDebugValueSubstitution Source : DebugValueSubstitutions) {
+    auto AddResult = Result.addDebugValueSubstitution(Source);
+    if (!AddResult)
+      return std::unexpected(AddResult.error());
+  }
+  for (const MachineEntryValueInfo &Source : EntryValues) {
+    auto AddResult = Result.addEntryValue(Source);
+    if (!AddResult)
+      return std::unexpected(AddResult.error());
+  }
+  return Result;
+}
+
+} // namespace rcc