[CodeGen] Add MachineFrameInfo

Model stable frame indices, stack object kinds, tombstones, lifetimes, and frozen layouts. Validate owned frame references in the builder and verifier, and remap complete frame state during MachineFunction cloning.

13 files changed, 876 insertions, 20 deletions

diff --git a/backend/include/rcc/CodeGen/MachineFrameInfo.h b/backend/include/rcc/CodeGen/MachineFrameInfo.h
new file mode 100644
index 0000000..ad1de53
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineFrameInfo.h
@@ -0,0 +1,186 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEFRAMEINFO_H
+#define RCC_CODEGEN_MACHINEFRAMEINFO_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+#include <optional>
+#include <span>
+#include <utility>
+#include <variant>
+#include <vector>
+
+namespace rcc {
+
+enum class StackObjectKind : std::uint8_t {
+  Default,
+  FixedABI,
+  SpillSlot,
+  VariableSized,
+  DynamicAlloca,
+  CalleeSaved,
+  EmergencySpill,
+  Target,
+  Count,
+};
+
+class StackID final {
+public:
+  constexpr StackID() noexcept = default;
+
+  [[nodiscard]] static constexpr StackID defaultStack() noexcept {
+    return StackID(DefaultStackValue);
+  }
+
+  [[nodiscard]] static constexpr StackID safeStack() noexcept {
+    return StackID(SafeStackValue);
+  }
+
+  [[nodiscard]] static constexpr StackID shadowCallStack() noexcept {
+    return StackID(ShadowCallStackValue);
+  }
+
+  [[nodiscard]] static constexpr StackID scalableVectorStack() noexcept {
+    return StackID(ScalableVectorStackValue);
+  }
+
+  [[nodiscard]] static Expected<StackID> targetStack(std::uint32_t Value);
+
+  [[nodiscard]] constexpr std::uint32_t value() const noexcept {
+    return Value;
+  }
+
+  [[nodiscard]] constexpr bool isTargetStack() const noexcept {
+    return Value >= FirstTargetStackValue;
+  }
+
+  [[nodiscard]] constexpr bool isValid() const noexcept {
+    return Value <= ScalableVectorStackValue || isTargetStack();
+  }
+
+  friend constexpr bool operator==(StackID Left, StackID Right) noexcept = default;
+
+private:
+  static constexpr std::uint32_t DefaultStackValue = 0;
+  static constexpr std::uint32_t SafeStackValue = 1;
+  static constexpr std::uint32_t ShadowCallStackValue = 2;
+  static constexpr std::uint32_t ScalableVectorStackValue = 3;
+  static constexpr std::uint32_t FirstTargetStackValue = 256;
+
+  explicit constexpr StackID(std::uint32_t Value) noexcept : Value(Value) {}
+
+  std::uint32_t Value = DefaultStackValue;
+};
+
+struct StackObjectLifetimeRange final {
+  MachineInstrStableID Begin;
+  MachineInstrStableID End;
+
+  friend constexpr bool operator==(StackObjectLifetimeRange Left,
+                                   StackObjectLifetimeRange Right) noexcept = default;
+};
+
+struct StackObjectDesc final {
+  StackObjectKind Kind = StackObjectKind::Default;
+  std::optional<std::uint64_t> Size;
+  Alignment Align;
+  std::optional<std::int64_t> Offset;
+  StackID Stack;
+  bool IsDead = false;
+  bool IsAliased = false;
+  bool AddressTaken = false;
+  std::vector<StackObjectLifetimeRange> Lifetime;
+  std::uint64_t TargetFlags = 0;
+
+  friend bool operator==(const StackObjectDesc &Left, const StackObjectDesc &Right) = default;
+};
+
+class StackObject final {
+public:
+  [[nodiscard]] FrameIndex index() const noexcept {
+    return Index;
+  }
+
+  [[nodiscard]] bool isTombstone() const noexcept {
+    return std::holds_alternative<std::monostate>(Description);
+  }
+
+  [[nodiscard]] const StackObjectDesc *description() const noexcept {
+    return std::get_if<StackObjectDesc>(&Description);
+  }
+
+  [[nodiscard]] bool isSpill() const noexcept;
+  [[nodiscard]] bool isFixed() const noexcept;
+  [[nodiscard]] bool isVariableSized() const noexcept;
+
+private:
+  StackObject(FrameIndex Index, StackObjectDesc Description)
+      : Index(Index), Description(std::move(Description)) {}
+
+  FrameIndex Index;
+  std::variant<std::monostate, StackObjectDesc> Description;
+
+  friend class MachineFrameInfo;
+};
+
+class MachineFrameInfo final {
+public:
+  MachineFrameInfo() = default;
+  MachineFrameInfo(const MachineFrameInfo &) = delete;
+  MachineFrameInfo &operator=(const MachineFrameInfo &) = delete;
+  MachineFrameInfo(MachineFrameInfo &&) noexcept = default;
+  MachineFrameInfo &operator=(MachineFrameInfo &&) noexcept = default;
+  ~MachineFrameInfo() = default;
+
+  [[nodiscard]] Expected<FrameIndex> createObject(StackObjectDesc Description);
+  [[nodiscard]] Expected<void> updateObject(FrameIndex Index, StackObjectDesc Description);
+  [[nodiscard]] Expected<void> setObjectOffset(FrameIndex Index, std::int64_t Offset);
+  [[nodiscard]] Expected<void> markObjectDead(FrameIndex Index);
+  [[nodiscard]] Expected<void> eraseObject(FrameIndex Index);
+
+  [[nodiscard]] const StackObject *object(FrameIndex Index) const noexcept;
+  [[nodiscard]] std::span<const StackObject> objects() const noexcept {
+    return Objects;
+  }
+
+  [[nodiscard]] std::size_t liveObjectCount() const noexcept;
+
+  [[nodiscard]] bool isFrozen() const noexcept {
+    return Frozen;
+  }
+
+  [[nodiscard]] std::optional<std::uint64_t> staticStackSize() const noexcept {
+    return StaticStackSize;
+  }
+
+  [[nodiscard]] Alignment stackAlignment() const noexcept {
+    return StackAlign;
+  }
+
+  [[nodiscard]] std::uint64_t maxCallFrameSize() const noexcept {
+    return MaxCallFrameSize;
+  }
+
+  [[nodiscard]] Expected<void> setMaxCallFrameSize(std::uint64_t Size);
+  [[nodiscard]] Expected<void> freeze(std::uint64_t Size, Alignment Align);
+  [[nodiscard]] Expected<void> verify() const;
+
+private:
+  [[nodiscard]] static Expected<void> verifyDescription(const StackObjectDesc &Description);
+  [[nodiscard]] Expected<StackObject *> mutableObject(FrameIndex Index);
+
+  std::vector<StackObject> Objects;
+  bool Frozen = false;
+  std::optional<std::uint64_t> StaticStackSize;
+  Alignment StackAlign;
+  std::uint64_t MaxCallFrameSize = 0;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEFRAMEINFO_H
diff --git a/backend/include/rcc/CodeGen/MachineFunction.h b/backend/include/rcc/CodeGen/MachineFunction.h
index 487fb5b..3e3fecb 100644
--- a/backend/include/rcc/CodeGen/MachineFunction.h
+++ b/backend/include/rcc/CodeGen/MachineFunction.h
@@ -3,6 +3,7 @@
 #ifndef RCC_CODEGEN_MACHINEFUNCTION_H
 #define RCC_CODEGEN_MACHINEFUNCTION_H
 
+#include "rcc/CodeGen/MachineFrameInfo.h"
 #include "rcc/CodeGen/MachineFunctionProperties.h"
 #include "rcc/CodeGen/MachineRegisterInfo.h"
 #include "rcc/CodeGen/StableID.h"
@@ -52,6 +53,14 @@ public:
     return RegInfo;
   }
 
+  [[nodiscard]] MachineFrameInfo &frameInfo() noexcept {
+    return FrameInfo;
+  }
+
+  [[nodiscard]] const MachineFrameInfo &frameInfo() const noexcept {
+    return FrameInfo;
+  }
+
   [[nodiscard]] MachineFunctionProperties &properties() noexcept {
     return Properties;
   }
@@ -110,6 +119,7 @@ private:
   std::string Name;
   MachineFunctionStableID StableID;
   MachineRegisterInfo RegInfo;
+  MachineFrameInfo FrameInfo;
   MachineFunctionProperties Properties;
   MachineBasicBlock *FirstBlock = nullptr;
   MachineBasicBlock *LastBlock = nullptr;
diff --git a/backend/include/rcc/CodeGen/MachineIRBuilder.h b/backend/include/rcc/CodeGen/MachineIRBuilder.h
index 02e47ff..3bd8d67 100644
--- a/backend/include/rcc/CodeGen/MachineIRBuilder.h
+++ b/backend/include/rcc/CodeGen/MachineIRBuilder.h
@@ -96,6 +96,7 @@ private:
 
   [[nodiscard]] Expected<void> ensurePending() const;
   [[nodiscard]] Expected<void> validateInsertionPoint() const;
+  [[nodiscard]] Expected<void> validateFrameReference(FrameIndex Index) const;
   [[nodiscard]] Expected<void> validateOperandOwnership(const MachineOperand &Operand) const;
   [[nodiscard]] std::vector<MachineOperandTie> collectOperandTies() const;
   [[nodiscard]] Expected<void> appendRegister(Register Reg, RegisterOperandFlags Flags,
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index d19aaba..283727c 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -6,6 +6,7 @@ set(
   LowLevelType.cpp
   MachineBasicBlock.cpp
   MachineCFGUpdater.cpp
+  MachineFrameInfo.cpp
   MachineFunction.cpp
   MachineFunctionCloner.cpp
   MachineIRTypes.cpp
@@ -25,6 +26,7 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlock.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCFGUpdater.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFrameInfo.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunction.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionCloner.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineIRTypes.h"
@@ -73,6 +75,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFrameInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionCloner.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp"
@@ -92,6 +95,7 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFrameInfo.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunction.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionCloner.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRTypes.cpp"
diff --git a/backend/lib/CodeGen/MachineFrameInfo.cpp b/backend/lib/CodeGen/MachineFrameInfo.cpp
new file mode 100644
index 0000000..58eab00
--- /dev/null
+++ b/backend/lib/CodeGen/MachineFrameInfo.cpp
@@ -0,0 +1,234 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineFrameInfo.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <unordered_set>
+#include <utility>
+
+namespace rcc {
+
+Expected<StackID> StackID::targetStack(std::uint32_t Value) {
+  if (Value < FirstTargetStackValue) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "target stack ID must not overlap a built-in stack ID");
+  }
+  return StackID(Value);
+}
+
+bool StackObject::isSpill() const noexcept {
+  const StackObjectDesc *Desc = description();
+  if (Desc == nullptr)
+    return false;
+  return Desc->Kind == StackObjectKind::SpillSlot || Desc->Kind == StackObjectKind::CalleeSaved ||
+         Desc->Kind == StackObjectKind::EmergencySpill;
+}
+
+bool StackObject::isFixed() const noexcept {
+  const StackObjectDesc *Desc = description();
+  return Desc != nullptr && Desc->Kind == StackObjectKind::FixedABI;
+}
+
+bool StackObject::isVariableSized() const noexcept {
+  const StackObjectDesc *Desc = description();
+  return Desc != nullptr && (Desc->Kind == StackObjectKind::VariableSized ||
+                             Desc->Kind == StackObjectKind::DynamicAlloca);
+}
+
+Expected<void> MachineFrameInfo::verifyDescription(const StackObjectDesc &Description) {
+  if (Description.Kind >= StackObjectKind::Count)
+    return makeUnexpected(ErrorCode::InvalidArgument, "stack object kind is invalid");
+  if (!Description.Stack.isValid())
+    return makeUnexpected(ErrorCode::InvalidArgument, "stack object has an invalid stack ID");
+
+  const bool IsVariable = Description.Kind == StackObjectKind::VariableSized ||
+                          Description.Kind == StackObjectKind::DynamicAlloca;
+  if (IsVariable) {
+    if (Description.Size || Description.Offset) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "variable-sized stack objects cannot have a fixed size or offset");
+    }
+  } else if (!Description.Size || *Description.Size == 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "fixed-size stack objects require a nonzero size");
+  }
+
+  if (Description.Kind == StackObjectKind::FixedABI && !Description.Offset) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "fixed ABI stack objects require a fixed offset");
+  }
+  if (Description.Kind == StackObjectKind::Target && !Description.Stack.isTargetStack() &&
+      Description.TargetFlags == 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "target stack objects require a target stack ID or nonzero target flags");
+  }
+
+  std::unordered_set<MachineInstrStableID> LifetimeBoundaries;
+  for (const StackObjectLifetimeRange &Range : Description.Lifetime) {
+    if (!Range.Begin.isValid() || !Range.End.isValid() || Range.Begin == Range.End) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "stack object lifetime boundaries must be valid and distinct");
+    }
+    if (!LifetimeBoundaries.insert(Range.Begin).second ||
+        !LifetimeBoundaries.insert(Range.End).second) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "stack object lifetime boundaries must not be reused");
+    }
+  }
+  return {};
+}
+
+Expected<FrameIndex> MachineFrameInfo::createObject(StackObjectDesc Description) {
+  if (Frozen)
+    return makeUnexpected(ErrorCode::InvalidArgument, "frozen frame cannot create stack objects");
+  auto DescriptionResult = verifyDescription(Description);
+  if (!DescriptionResult)
+    return std::unexpected(DescriptionResult.error());
+  if (Objects.size() > std::numeric_limits<std::uint32_t>::max()) {
+    return makeUnexpected(ErrorCode::Unsupported, "stack object index space is exhausted");
+  }
+
+  const FrameIndex Index = FrameIndex::fromValue(static_cast<std::uint32_t>(Objects.size()));
+  Objects.push_back(StackObject(Index, std::move(Description)));
+  return Index;
+}
+
+Expected<StackObject *> MachineFrameInfo::mutableObject(FrameIndex Index) {
+  if (Frozen)
+    return makeUnexpected(ErrorCode::InvalidArgument, "frozen frame cannot modify stack objects");
+  if (Index.value() >= Objects.size())
+    return makeUnexpected(ErrorCode::InvalidArgument, "stack object index is out of range");
+  StackObject &Object = Objects[Index.value()];
+  if (Object.isTombstone())
+    return makeUnexpected(ErrorCode::InvalidArgument, "stack object index is a tombstone");
+  return &Object;
+}
+
+Expected<void> MachineFrameInfo::updateObject(FrameIndex Index, StackObjectDesc Description) {
+  auto DescriptionResult = verifyDescription(Description);
+  if (!DescriptionResult)
+    return std::unexpected(DescriptionResult.error());
+  auto Object = mutableObject(Index);
+  if (!Object)
+    return std::unexpected(Object.error());
+  (*Object)->Description.emplace<StackObjectDesc>(std::move(Description));
+  return {};
+}
+
+Expected<void> MachineFrameInfo::setObjectOffset(FrameIndex Index, std::int64_t Offset) {
+  auto Object = mutableObject(Index);
+  if (!Object)
+    return std::unexpected(Object.error());
+  StackObjectDesc *CurrentDescription = std::get_if<StackObjectDesc>(&(*Object)->Description);
+  if (CurrentDescription == nullptr) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "live stack object unexpectedly lacks a description");
+  }
+  StackObjectDesc Description = *CurrentDescription;
+  if ((*Object)->isVariableSized()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "variable-sized stack object cannot have a fixed offset");
+  }
+  Description.Offset = Offset;
+  (*Object)->Description.emplace<StackObjectDesc>(std::move(Description));
+  return {};
+}
+
+Expected<void> MachineFrameInfo::markObjectDead(FrameIndex Index) {
+  auto Object = mutableObject(Index);
+  if (!Object)
+    return std::unexpected(Object.error());
+  StackObjectDesc *Description = std::get_if<StackObjectDesc>(&(*Object)->Description);
+  if (Description == nullptr) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "live stack object unexpectedly lacks a description");
+  }
+  Description->IsDead = true;
+  return {};
+}
+
+Expected<void> MachineFrameInfo::eraseObject(FrameIndex Index) {
+  auto Object = mutableObject(Index);
+  if (!Object)
+    return std::unexpected(Object.error());
+  (*Object)->Description.emplace<std::monostate>();
+  return {};
+}
+
+const StackObject *MachineFrameInfo::object(FrameIndex Index) const noexcept {
+  if (Index.value() >= Objects.size() || Objects[Index.value()].isTombstone())
+    return nullptr;
+  return &Objects[Index.value()];
+}
+
+std::size_t MachineFrameInfo::liveObjectCount() const noexcept {
+  std::size_t Count = 0;
+  for (const StackObject &Object : Objects) {
+    if (!Object.isTombstone())
+      ++Count;
+  }
+  return Count;
+}
+
+Expected<void> MachineFrameInfo::setMaxCallFrameSize(std::uint64_t Size) {
+  if (Frozen)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "frozen frame cannot change its maximum call-frame size");
+  MaxCallFrameSize = Size;
+  return {};
+}
+
+Expected<void> MachineFrameInfo::freeze(std::uint64_t Size, Alignment Align) {
+  if (Frozen)
+    return makeUnexpected(ErrorCode::InvalidArgument, "frame layout is already frozen");
+  for (const StackObject &Object : Objects) {
+    if (Object.isTombstone() || Object.isVariableSized())
+      continue;
+    if (!Object.description()->Offset) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "fixed-size stack object is missing its final offset");
+    }
+  }
+  if (Size % Align.bytes() != 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "static stack size must be aligned to the stack alignment");
+  }
+
+  StaticStackSize = Size;
+  StackAlign = Align;
+  Frozen = true;
+  return {};
+}
+
+Expected<void> MachineFrameInfo::verify() const {
+  for (std::size_t Position = 0; Position < Objects.size(); ++Position) {
+    const StackObject &Object = Objects[Position];
+    if (Object.index() != FrameIndex::fromValue(static_cast<std::uint32_t>(Position))) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "stack object index does not match its stable table position");
+    }
+    if (Object.isTombstone())
+      continue;
+    auto DescriptionResult = verifyDescription(*Object.description());
+    if (!DescriptionResult)
+      return std::unexpected(DescriptionResult.error());
+    if (Frozen && !Object.isVariableSized() && !Object.description()->Offset) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "frozen fixed-size stack object has no final offset");
+    }
+  }
+
+  if (Frozen != StaticStackSize.has_value()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "frame frozen state and static stack size are inconsistent");
+  }
+  if (Frozen && *StaticStackSize % StackAlign.bytes() != 0) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "frozen static stack size violates stack alignment");
+  }
+  return {};
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineFunctionCloner.cpp b/backend/lib/CodeGen/MachineFunctionCloner.cpp
index d452546..46fed6c 100644
--- a/backend/lib/CodeGen/MachineFunctionCloner.cpp
+++ b/backend/lib/CodeGen/MachineFunctionCloner.cpp
@@ -5,6 +5,7 @@
 #include "rcc/CodeGen/InstructionDescriptor.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFrameInfo.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineInstr.h"
 #include "rcc/CodeGen/MachineMemOperand.h"
@@ -86,8 +87,12 @@ struct CloneState final {
     if (Frame == nullptr) {
       return makeUnexpected(ErrorCode::VerificationError, "source frame-index operand is invalid");
     }
-    State.Result.FrameIndices.emplace(Frame->Index, Frame->Index);
-    return SourceOperand.cloneDetached();
+    const auto Position = State.Result.FrameIndices.find(Frame->Index);
+    if (Position == State.Result.FrameIndices.end()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "source operand references an unmapped frame index");
+    }
+    return MachineOperand::frameIndex(Position->second, Frame->Offset, SourceOperand.targetFlags());
   }
   case MachineOperand::Kind::ConstantPoolIndex: {
     const auto *Constant = SourceOperand.getIf<ConstantPoolOperand>();
@@ -123,8 +128,6 @@ struct CloneState final {
 
 void recordMemoryIndexMappings(const MachineMemOperandDesc &Description,
                                MachineFunctionCloneResult &Result) {
-  if (const auto Frame = Description.Base.frameIndex())
-    Result.FrameIndices.emplace(*Frame, *Frame);
   if (const auto Constant = Description.Base.constantPoolIndex())
     Result.ConstantPoolIndices.emplace(*Constant, *Constant);
   if (const auto JumpTable = Description.Base.jumpTableIndex())
@@ -139,6 +142,14 @@ cloneMemOperand(const MachineMemOperand &SourceOperand, CloneState &State) {
 
   MachineMemOperandDesc Description = SourceOperand.description();
   recordMemoryIndexMappings(Description, State.Result);
+  if (const auto Frame = Description.Base.frameIndex()) {
+    const auto Position = State.Result.FrameIndices.find(*Frame);
+    if (Position == State.Result.FrameIndices.end()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "source MMO references an unmapped frame index");
+    }
+    Description.Base = MemoryBase::frameIndex(Position->second);
+  }
   auto DestinationOperand = State.Destination.createMemOperand(std::move(Description));
   if (!DestinationOperand)
     return std::unexpected(DestinationOperand.error());
@@ -207,6 +218,23 @@ cloneMemOperand(const MachineMemOperand &SourceOperand, CloneState &State) {
   return {};
 }
 
+[[nodiscard]] Expected<void> cloneFrameObjects(CloneState &State) {
+  for (const StackObject &SourceObject : State.Source.frameInfo().objects()) {
+    const StackObjectDesc *Description = SourceObject.description();
+    if (Description == nullptr)
+      continue;
+    auto DestinationIndex = State.Destination.frameInfo().createObject(*Description);
+    if (!DestinationIndex)
+      return std::unexpected(DestinationIndex.error());
+    State.Result.FrameIndices.emplace(SourceObject.index(), *DestinationIndex);
+  }
+  auto CallFrameResult = State.Destination.frameInfo().setMaxCallFrameSize(
+      State.Source.frameInfo().maxCallFrameSize());
+  if (!CallFrameResult)
+    return std::unexpected(CallFrameResult.error());
+  return {};
+}
+
 [[nodiscard]] Expected<void> cloneBlocks(CloneState &State) {
   for (const MachineBasicBlock *SourceBlock = State.Source.firstBlock(); SourceBlock != nullptr;
        SourceBlock = SourceBlock->next()) {
@@ -294,6 +322,49 @@ cloneMemOperand(const MachineMemOperand &SourceOperand, CloneState &State) {
   return {};
 }
 
+[[nodiscard]] Expected<void> finalizeFrameClone(CloneState &State) {
+  for (const StackObject &SourceObject : State.Source.frameInfo().objects()) {
+    const StackObjectDesc *SourceDescription = SourceObject.description();
+    if (SourceDescription == nullptr)
+      continue;
+    const auto FramePosition = State.Result.FrameIndices.find(SourceObject.index());
+    if (FramePosition == State.Result.FrameIndices.end()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "source stack object was not mapped before frame finalization");
+    }
+
+    StackObjectDesc DestinationDescription = *SourceDescription;
+    for (StackObjectLifetimeRange &Range : DestinationDescription.Lifetime) {
+      const auto Begin = State.Result.InstructionStableIDs.find(Range.Begin);
+      const auto End = State.Result.InstructionStableIDs.find(Range.End);
+      if (Begin == State.Result.InstructionStableIDs.end() ||
+          End == State.Result.InstructionStableIDs.end()) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "source stack lifetime references an unmapped instruction");
+      }
+      Range.Begin = Begin->second;
+      Range.End = End->second;
+    }
+    auto UpdateResult = State.Destination.frameInfo().updateObject(
+        FramePosition->second, std::move(DestinationDescription));
+    if (!UpdateResult)
+      return std::unexpected(UpdateResult.error());
+  }
+
+  if (State.Source.frameInfo().isFrozen()) {
+    const auto StackSize = State.Source.frameInfo().staticStackSize();
+    if (!StackSize) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "verified frozen source frame has no static stack size");
+    }
+    auto FreezeResult =
+        State.Destination.frameInfo().freeze(*StackSize, State.Source.frameInfo().stackAlignment());
+    if (!FreezeResult)
+      return std::unexpected(FreezeResult.error());
+  }
+  return {};
+}
+
 [[nodiscard]] Expected<void> cloneCFG(CloneState &State) {
   MachineCFGUpdater Updater = State.Destination.cfgUpdater();
   for (const MachineBasicBlock *SourceBlock = State.Source.firstBlock(); SourceBlock != nullptr;
@@ -353,12 +424,18 @@ Expected<MachineFunctionCloneResult> cloneMachineFunction(const MachineFunction
   auto RegisterResult = cloneRegisterConfiguration(State);
   if (!RegisterResult)
     return std::unexpected(RegisterResult.error());
+  auto FrameResult = cloneFrameObjects(State);
+  if (!FrameResult)
+    return std::unexpected(FrameResult.error());
   auto BlockResult = cloneBlocks(State);
   if (!BlockResult)
     return std::unexpected(BlockResult.error());
   auto InstructionResult = cloneInstructions(State);
   if (!InstructionResult)
     return std::unexpected(InstructionResult.error());
+  auto FrameFinalizationResult = finalizeFrameClone(State);
+  if (!FrameFinalizationResult)
+    return std::unexpected(FrameFinalizationResult.error());
   auto CFGResult = cloneCFG(State);
   if (!CFGResult)
     return std::unexpected(CFGResult.error());
diff --git a/backend/lib/CodeGen/MachineIRBuilder.cpp b/backend/lib/CodeGen/MachineIRBuilder.cpp
index 8f80ad6..185b7df 100644
--- a/backend/lib/CodeGen/MachineIRBuilder.cpp
+++ b/backend/lib/CodeGen/MachineIRBuilder.cpp
@@ -3,6 +3,7 @@
 #include "rcc/CodeGen/MachineIRBuilder.h"
 
 #include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFrameInfo.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineInstr.h"
 #include "rcc/CodeGen/MachineMemOperand.h"
@@ -332,6 +333,15 @@ Expected<void> MachineInstrBuilder::validateInsertionPoint() const {
   return {};
 }
 
+Expected<void> MachineInstrBuilder::validateFrameReference(FrameIndex Index) const {
+  const StackObject *Object = Function->frameInfo().object(Index);
+  if (Object == nullptr || Object->description()->IsDead) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "builder references an unknown or dead stack object");
+  }
+  return {};
+}
+
 Expected<void> MachineInstrBuilder::validateOperandOwnership(const MachineOperand &Operand) const {
   if (Operand.parent() != nullptr) {
     return makeUnexpected(ErrorCode::InvalidArgument,
@@ -349,6 +359,11 @@ Expected<void> MachineInstrBuilder::validateOperandOwnership(const MachineOperan
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "builder operand references an unknown virtual register");
   }
+  if (const auto *Frame = Operand.getIf<FrameIndexOperand>(); Frame != nullptr) {
+    auto FrameResult = validateFrameReference(Frame->Index);
+    if (!FrameResult)
+      return FrameResult;
+  }
   return {};
 }
 
@@ -389,6 +404,13 @@ Expected<MachineInstr *> MachineInstrBuilder::build() {
     if (!Ownership)
       return std::unexpected(Ownership.error());
   }
+  for (const MachineMemOperand *MemOperand : MemOperands) {
+    if (const auto Frame = MemOperand->description().Base.frameIndex()) {
+      auto FrameResult = validateFrameReference(*Frame);
+      if (!FrameResult)
+        return std::unexpected(FrameResult.error());
+    }
+  }
 
   auto ExplicitValidation = Instructions->validateExplicitOperands(
       Descriptor->InstructionOpcode, ExplicitOperands, Function->registerInfo());
diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp
index 450f8e3..6331366 100644
--- a/backend/lib/CodeGen/MachineVerifier.cpp
+++ b/backend/lib/CodeGen/MachineVerifier.cpp
@@ -3,6 +3,7 @@
 #include "rcc/CodeGen/MachineVerifier.h"
 
 #include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFrameInfo.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineFunctionProperties.h"
 #include "rcc/CodeGen/MachineInstr.h"
@@ -36,9 +37,15 @@ public:
     auto CatalogResult = catalogArenaObjects();
     if (!CatalogResult)
       return CatalogResult;
+    auto FrameResult = Function.frameInfo().verify();
+    if (!FrameResult)
+      return failWith("frame info", FrameResult.error());
     auto LayoutResult = verifyBlockLayout();
     if (!LayoutResult)
       return LayoutResult;
+    auto FrameLifetimeResult = verifyFrameLifetimes();
+    if (!FrameLifetimeResult)
+      return FrameLifetimeResult;
     auto CFGResult = verifyCFG();
     if (!CFGResult)
       return CFGResult;
@@ -209,6 +216,7 @@ private:
         return fail("block layout references an unregistered instruction");
       if (!LinkedInstructions.insert(Instruction).second)
         return fail("instruction layout contains a cycle or duplicate instruction");
+      LinkedInstructionIDs.insert(Instruction->stableID());
       if (Instruction->parent() != &Block || Instruction->previous() != Previous) {
         return fail("instruction parent or previous link is inconsistent");
       }
@@ -270,6 +278,29 @@ private:
     return {};
   }
 
+  [[nodiscard]] Expected<void> verifyFrameIndex(FrameIndex Index) const {
+    const StackObject *Object = Function.frameInfo().object(Index);
+    const StackObjectDesc *Description = Object == nullptr ? nullptr : Object->description();
+    if (Description == nullptr || Description->IsDead)
+      return fail("live instruction references an unknown or dead stack object");
+    return {};
+  }
+
+  [[nodiscard]] Expected<void> verifyFrameLifetimes() const {
+    for (const StackObject &Object : Function.frameInfo().objects()) {
+      const StackObjectDesc *Description = Object.description();
+      if (Description == nullptr)
+        continue;
+      for (const StackObjectLifetimeRange &Range : Description->Lifetime) {
+        if (!LinkedInstructionIDs.contains(Range.Begin) ||
+            !LinkedInstructionIDs.contains(Range.End)) {
+          return fail("stack object lifetime references a detached or unknown instruction");
+        }
+      }
+    }
+    return {};
+  }
+
   [[nodiscard]] Expected<void> verifyLiveInstruction(const MachineInstr &Instruction) {
     auto LocalResult = verifyInstructionLocalState(Instruction);
     if (!LocalResult)
@@ -297,8 +328,12 @@ private:
     const auto Operands = Instruction.operands();
     for (std::size_t Index = 0; Index < Operands.size(); ++Index) {
       const MachineOperand &Operand = Operands[Index];
-      if (Operand.kind() == MachineOperand::Kind::FrameIndex)
+      if (const auto *Frame = Operand.getIf<FrameIndexOperand>(); Frame != nullptr) {
         HasFrameIndex = true;
+        auto FrameResult = verifyFrameIndex(Frame->Index);
+        if (!FrameResult)
+          return FrameResult;
+      }
 
       if (const auto *Block = Operand.getIf<BasicBlockOperand>();
           Block != nullptr &&
@@ -328,6 +363,13 @@ private:
           HasUnrewrittenTie = true;
       }
     }
+    for (const MachineMemOperand *MemOperand : Instruction.memOperands()) {
+      if (const auto Frame = MemOperand->description().Base.frameIndex()) {
+        auto FrameResult = verifyFrameIndex(*Frame);
+        if (!FrameResult)
+          return FrameResult;
+      }
+    }
     return {};
   }
 
@@ -480,6 +522,7 @@ private:
   std::unordered_set<const MachineBasicBlock *> LinkedBlocks;
   std::unordered_set<const MachineInstr *> RegisteredInstructions;
   std::unordered_set<const MachineInstr *> LinkedInstructions;
+  std::unordered_set<MachineInstrStableID> LinkedInstructionIDs;
   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 650cfa9..18cda7c 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -4,6 +4,7 @@ set(
   RCCBackendCodeGenTestSources
   CoreTypesTest.cpp
   InstructionDescriptorTest.cpp
+  MachineFrameInfoTest.cpp
   MachineFunctionClonerTest.cpp
   MachineIRBuilderTest.cpp
   MachineIRCoreTest.cpp
@@ -32,6 +33,15 @@ add_test(
   COMMAND RCCBackendCodeGenInstructionDescriptorTests
 )
 
+add_executable(RCCBackendCodeGenMachineFrameInfoTests MachineFrameInfoTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenMachineFrameInfoTests)
+target_link_libraries(RCCBackendCodeGenMachineFrameInfoTests PRIVATE RCCBackend::CodeGen)
+
+add_test(
+  NAME RCCBackend.CodeGen.MachineFrameInfo
+  COMMAND RCCBackendCodeGenMachineFrameInfoTests
+)
+
 add_executable(
   RCCBackendCodeGenMachineFunctionClonerTests
   MachineFunctionClonerTest.cpp
@@ -92,6 +102,7 @@ add_test(
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptorTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFrameInfoTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionClonerTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilderTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
@@ -101,6 +112,7 @@ rcc_backend_register_format_files(
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptorTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineFrameInfoTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionClonerTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilderTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
diff --git a/backend/unittests/CodeGen/MachineFrameInfoTest.cpp b/backend/unittests/CodeGen/MachineFrameInfoTest.cpp
new file mode 100644
index 0000000..7368815
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineFrameInfoTest.cpp
@@ -0,0 +1,156 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineFrameInfo.h"
+
+#include <cstdint>
+#include <iostream>
+#include <string_view>
+
+namespace {
+
+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::StackObjectDesc fixedObject(std::uint64_t Size, std::uint64_t Align) {
+  rcc::StackObjectDesc Description;
+  Description.Size = Size;
+  Description.Align = *rcc::Alignment::create(Align);
+  return Description;
+}
+
+void testObjectLifecycle(TestContext &Context) {
+  rcc::MachineFrameInfo Frame;
+
+  auto LocalDescription = fixedObject(8, 8);
+  LocalDescription.IsAliased = true;
+  LocalDescription.AddressTaken = true;
+  LocalDescription.Lifetime.push_back(
+      {rcc::MachineInstrStableID::fromValue(3), rcc::MachineInstrStableID::fromValue(7)});
+  auto Local = Frame.createObject(LocalDescription);
+
+  auto FixedDescription = fixedObject(16, 16);
+  FixedDescription.Kind = rcc::StackObjectKind::FixedABI;
+  FixedDescription.Offset = -32;
+  auto Fixed = Frame.createObject(FixedDescription);
+
+  auto SpillDescription = fixedObject(8, 8);
+  SpillDescription.Kind = rcc::StackObjectKind::SpillSlot;
+  auto Spill = Frame.createObject(SpillDescription);
+
+  rcc::StackObjectDesc VariableDescription;
+  VariableDescription.Kind = rcc::StackObjectKind::VariableSized;
+  VariableDescription.Align = *rcc::Alignment::create(32);
+  auto Variable = Frame.createObject(VariableDescription);
+
+  Context.expect(Local && Fixed && Spill && Variable, "valid stack object kinds must be created");
+  if (!Local || !Fixed || !Spill || !Variable)
+    return;
+
+  Context.expect(Local->value() == 0 && Fixed->value() == 1 && Spill->value() == 2 &&
+                     Variable->value() == 3 && Frame.liveObjectCount() == 4,
+                 "frame indices must be monotonic table identities");
+  Context.expect(Frame.object(*Fixed)->isFixed() && Frame.object(*Spill)->isSpill() &&
+                     Frame.object(*Variable)->isVariableSized(),
+                 "stack object semantic categories must be derived exactly");
+
+  Context.expect(Frame.setObjectOffset(*Local, -8).has_value() &&
+                     Frame.setObjectOffset(*Spill, -16).has_value() &&
+                     Frame.markObjectDead(*Spill).has_value(),
+                 "live stack objects must support controlled pre-freeze updates");
+  Context.expect(Frame.object(*Spill)->description()->IsDead,
+                 "dead stack object state must remain explicit");
+
+  Context.expect(Frame.eraseObject(*Fixed).has_value() && Frame.object(*Fixed) == nullptr &&
+                     Frame.liveObjectCount() == 3,
+                 "erasing a stack object must leave an inaccessible tombstone");
+  auto Replacement = Frame.createObject(fixedObject(4, 4));
+  Context.expect(Replacement && Replacement->value() == 4,
+                 "erased frame indices must never be reused");
+  if (!Replacement)
+    return;
+  Context.expect(Frame.setObjectOffset(*Replacement, -24).has_value(),
+                 "replacement stack object must accept a final offset");
+
+  Context.expect(Frame.setMaxCallFrameSize(24).has_value() &&
+                     Frame.freeze(64, *rcc::Alignment::create(16)).has_value() &&
+                     Frame.isFrozen() && Frame.staticStackSize() == 64 &&
+                     Frame.stackAlignment().bytes() == 16 && Frame.maxCallFrameSize() == 24 &&
+                     Frame.verify().has_value(),
+                 "complete frame layout must freeze atomically");
+
+  Context.expect(!Frame.createObject(fixedObject(8, 8)) && !Frame.setObjectOffset(*Local, -40) &&
+                     !Frame.eraseObject(*Local) && !Frame.setMaxCallFrameSize(32) &&
+                     !Frame.freeze(64, *rcc::Alignment::create(16)),
+                 "frozen frames must reject every semantic mutation");
+}
+
+void testInvalidDescriptions(TestContext &Context) {
+  rcc::MachineFrameInfo Frame;
+
+  rcc::StackObjectDesc MissingSize;
+  Context.expect(!Frame.createObject(MissingSize),
+                 "fixed-size stack object must reject a missing size");
+
+  auto ZeroSize = fixedObject(0, 1);
+  Context.expect(!Frame.createObject(ZeroSize), "fixed-size stack object must reject zero size");
+
+  rcc::StackObjectDesc InvalidVariable;
+  InvalidVariable.Kind = rcc::StackObjectKind::DynamicAlloca;
+  InvalidVariable.Size = 8;
+  Context.expect(!Frame.createObject(InvalidVariable),
+                 "variable-sized stack object must reject a fixed size");
+
+  auto MissingFixedOffset = fixedObject(8, 8);
+  MissingFixedOffset.Kind = rcc::StackObjectKind::FixedABI;
+  Context.expect(!Frame.createObject(MissingFixedOffset),
+                 "fixed ABI stack object must require an offset");
+
+  auto InvalidTarget = fixedObject(8, 8);
+  InvalidTarget.Kind = rcc::StackObjectKind::Target;
+  Context.expect(!Frame.createObject(InvalidTarget),
+                 "target stack object must carry target identity");
+
+  auto InvalidLifetime = fixedObject(8, 8);
+  InvalidLifetime.Lifetime.push_back(
+      {rcc::MachineInstrStableID::fromValue(4), rcc::MachineInstrStableID::fromValue(4)});
+  Context.expect(!Frame.createObject(InvalidLifetime),
+                 "stack object lifetime must reject equal boundaries");
+
+  Context.expect(!rcc::StackID::targetStack(4), "target stack IDs must not overlap built-in IDs");
+  auto TargetStack = rcc::StackID::targetStack(256);
+  auto Target = fixedObject(8, 8);
+  Target.Kind = rcc::StackObjectKind::Target;
+  if (TargetStack)
+    Target.Stack = *TargetStack;
+  auto TargetIndex = Frame.createObject(Target);
+  Context.expect(TargetStack && TargetIndex,
+                 "target stack identity must admit target stack objects");
+
+  auto Unresolved = Frame.createObject(fixedObject(8, 8));
+  Context.expect(Unresolved && !Frame.freeze(16, *rcc::Alignment::create(8)) && !Frame.isFrozen() &&
+                     !Frame.staticStackSize() && Frame.verify().has_value(),
+                 "failed frame freeze must not mutate frame state");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testObjectLifecycle(Context);
+  testInvalidDescriptions(Context);
+  return Context.result();
+}
diff --git a/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp b/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp
index 90e847b..3b2fce9 100644
--- a/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp
+++ b/backend/unittests/CodeGen/MachineFunctionClonerTest.cpp
@@ -6,6 +6,7 @@
 #include "rcc/CodeGen/LowLevelType.h"
 #include "rcc/CodeGen/MachineBasicBlock.h"
 #include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFrameInfo.h"
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineFunctionProperties.h"
 #include "rcc/CodeGen/MachineIRBuilder.h"
@@ -137,12 +138,12 @@ createFunction(TestContext &Context, std::string Name, std::uint64_t ID) {
   return *Block;
 }
 
-[[nodiscard]] rcc::MachineMemOperandDesc loadDescription() {
+[[nodiscard]] rcc::MachineMemOperandDesc loadDescription(rcc::FrameIndex Index) {
   rcc::MachineMemOperandDesc Description;
   Description.Accesses = {rcc::MemoryAccessFlag::Load, rcc::MemoryAccessFlag::Dereferenceable};
   Description.Size = *rcc::MemorySize::fixed(8);
   Description.Align = *rcc::Alignment::create(8);
-  Description.Base = rcc::MemoryBase::frameIndex(rcc::FrameIndex::fromValue(4));
+  Description.Base = rcc::MemoryBase::frameIndex(Index);
   Description.Offset = -8;
   return Description;
 }
@@ -162,6 +163,7 @@ struct SourceFixture final {
   rcc::MachineBasicBlock *Exit = nullptr;
   rcc::Register Value;
   rcc::Register CopyValue;
+  rcc::FrameIndex StackSlot;
   const rcc::MachineMemOperand *LoadMMO = nullptr;
 };
 
@@ -177,6 +179,25 @@ struct SourceFixture final {
   Context.expect(Tombstone && Function.registerInfo().eraseVirtualRegister(*Tombstone).has_value(),
                  "source vreg history must contain a tombstone");
 
+  rcc::StackObjectDesc HistoricalFrame;
+  HistoricalFrame.Size = 4;
+  HistoricalFrame.Align = *rcc::Alignment::create(4);
+  auto HistoricalFrameIndex = Function.frameInfo().createObject(HistoricalFrame);
+  Context.expect(HistoricalFrameIndex &&
+                     Function.frameInfo().eraseObject(*HistoricalFrameIndex).has_value(),
+                 "source frame history must contain a tombstone");
+
+  rcc::StackObjectDesc StackSlot;
+  StackSlot.Kind = rcc::StackObjectKind::SpillSlot;
+  StackSlot.Size = 8;
+  StackSlot.Align = *rcc::Alignment::create(8);
+  StackSlot.Offset = -16;
+  auto StackSlotIndex = Function.frameInfo().createObject(StackSlot);
+  Context.expect(StackSlotIndex.has_value(), "source live stack object must be created");
+  if (!StackSlotIndex)
+    return false;
+  Fixture.StackSlot = *StackSlotIndex;
+
   Fixture.Entry = createBlock(Context, Function);
   Fixture.Exit = createBlock(Context, Function);
   if (Fixture.Entry == nullptr || Fixture.Exit == nullptr)
@@ -236,8 +257,7 @@ struct SourceFixture final {
                  "source tied copy must build");
 
   auto Frame = Builder.buildInstr(rcc::Opcode::fromValue(FrameOpcode));
-  Context.expect(Frame && Frame->addFrameIndex(rcc::FrameIndex::fromValue(4), -8).has_value() &&
-                     Frame->build(),
+  Context.expect(Frame && Frame->addFrameIndex(Fixture.StackSlot, -8).has_value() && Frame->build(),
                  "source frame-index instruction must build");
 
   auto Address = Builder.buildInstr(rcc::Opcode::fromValue(BlockAddressOpcode));
@@ -246,7 +266,7 @@ struct SourceFixture final {
           Address->build(),
       "source self block-address instruction must build");
 
-  auto MMO = Function.createMemOperand(loadDescription());
+  auto MMO = Function.createMemOperand(loadDescription(Fixture.StackSlot));
   Context.expect(MMO.has_value(), "source MMO must be created");
   if (!MMO)
     return false;
@@ -255,6 +275,20 @@ struct SourceFixture final {
   Context.expect(Load && Load->addMemOperand(**MMO).has_value() && Load->build(),
                  "source load with MMO must build");
 
+  rcc::MachineInstr *Definition = findInstruction(*Fixture.Entry, DefOpcode);
+  rcc::MachineInstr *LoadInstruction = findInstruction(*Fixture.Exit, LoadOpcode);
+  const rcc::StackObject *Object = Function.frameInfo().object(Fixture.StackSlot);
+  if (Definition == nullptr || LoadInstruction == nullptr || Object == nullptr)
+    return false;
+  rcc::StackObjectDesc UpdatedStackSlot = *Object->description();
+  UpdatedStackSlot.Lifetime.push_back({Definition->stableID(), LoadInstruction->stableID()});
+  Context.expect(Function.frameInfo()
+                         .updateObject(Fixture.StackSlot, std::move(UpdatedStackSlot))
+                         .has_value() &&
+                     Function.frameInfo().setMaxCallFrameSize(16).has_value() &&
+                     Function.frameInfo().freeze(32, *rcc::Alignment::create(16)).has_value(),
+                 "source frame metadata must be finalized");
+
   Function.properties().set(rcc::MachineFunctionProperty::IsSSA);
   Function.properties().set(rcc::MachineFunctionProperty::TracksLiveness);
   Function.properties().set(rcc::MachineFunctionProperty::NoPHIs);
@@ -289,7 +323,9 @@ void testDeepClone(TestContext &Context) {
                  "source and destination must independently preserve valid properties");
   Context.expect(Source->allBlocks().size() == 3 && Destination.allBlocks().size() == 2 &&
                      Source->allInstructions().size() == 7 &&
-                     Destination.allInstructions().size() == 6,
+                     Destination.allInstructions().size() == 6 &&
+                     Source->frameInfo().objects().size() == 2 &&
+                     Destination.frameInfo().objects().size() == 1,
                  "clone must omit detached arena history");
   Context.expect(Clone->BlockStableIDs.size() == 2 && Clone->InstructionStableIDs.size() == 6 &&
                      Clone->VirtualRegisters.size() == 2,
@@ -375,21 +411,39 @@ void testDeepClone(TestContext &Context) {
                      DestinationCopy->operandAt(0)->tiedOperandIndex() == 1 &&
                      DestinationCopy->operandAt(1)->tiedOperandIndex() == 0,
                  "clone must remap tied registers and rebuild ties");
-  Context.expect(DestinationFrame->operandAt(0)->getIf<rcc::FrameIndexOperand>()->Index ==
-                         rcc::FrameIndex::fromValue(4) &&
-                     Clone->FrameIndices.contains(rcc::FrameIndex::fromValue(4)),
-                 "clone must preserve and map frame indices");
+  const auto FramePosition = Clone->FrameIndices.find(Fixture.StackSlot);
+  Context.expect(FramePosition != Clone->FrameIndices.end() &&
+                     FramePosition->second == rcc::FrameIndex::fromValue(0) &&
+                     DestinationFrame->operandAt(0)->getIf<rcc::FrameIndexOperand>()->Index ==
+                         FramePosition->second,
+                 "clone must compact and remap frame indices");
   Context.expect(
       DestinationAddress->operandAt(0)->getIf<rcc::BlockAddressOperand>()->FunctionName ==
           "cloned_function",
       "clone must rewrite self block-address function names");
 
+  rcc::MachineMemOperandDesc ExpectedMMO = Fixture.LoadMMO->description();
+  if (FramePosition != Clone->FrameIndices.end())
+    ExpectedMMO.Base = rcc::MemoryBase::frameIndex(FramePosition->second);
   Context.expect(DestinationLoad->memOperands().size() == 1 &&
                      DestinationLoad->memOperands()[0] != Fixture.LoadMMO &&
-                     *DestinationLoad->memOperands()[0] == *Fixture.LoadMMO &&
+                     DestinationLoad->memOperands()[0]->description() == ExpectedMMO &&
                      Destination.ownsMemOperand(*DestinationLoad->memOperands()[0]) &&
                      !Source->ownsMemOperand(*DestinationLoad->memOperands()[0]),
-                 "clone must deep-copy MMO ownership while preserving semantics");
+                 "clone must deep-copy MMO ownership while remapping frame semantics");
+
+  const rcc::StackObject *DestinationStackSlot =
+      FramePosition == Clone->FrameIndices.end()
+          ? nullptr
+          : Destination.frameInfo().object(FramePosition->second);
+  Context.expect(
+      DestinationStackSlot != nullptr && Destination.frameInfo().isFrozen() &&
+          Destination.frameInfo().staticStackSize() == 32 &&
+          Destination.frameInfo().maxCallFrameSize() == 16 &&
+          DestinationStackSlot->description()->Lifetime.size() == 1 &&
+          DestinationStackSlot->description()->Lifetime[0].Begin == DestinationDef->stableID() &&
+          DestinationStackSlot->description()->Lifetime[0].End == DestinationLoad->stableID(),
+      "clone must preserve frozen frame layout and remap instruction lifetimes");
 
   rcc::MachineInstr *SourceDef = findInstruction(*Fixture.Entry, DefOpcode);
   const auto InstructionID = SourceDef == nullptr
diff --git a/backend/unittests/CodeGen/MachineIRBuilderTest.cpp b/backend/unittests/CodeGen/MachineIRBuilderTest.cpp
index bda30b6..ba5e3db 100644
--- a/backend/unittests/CodeGen/MachineIRBuilderTest.cpp
+++ b/backend/unittests/CodeGen/MachineIRBuilderTest.cpp
@@ -356,6 +356,16 @@ void testImplicitAndMemoryValidation(TestContext &Context) {
                      Function->allInstructions().size() == BeforeMissingMemory,
                  "missing required MMO must fail before instruction allocation");
 
+  rcc::StackObjectDesc StackSlot;
+  StackSlot.Size = 8;
+  StackSlot.Align = *rcc::Alignment::create(8);
+  auto FrameIndex = Function->frameInfo().createObject(StackSlot);
+  auto ForeignFrameIndex = OtherFunction->frameInfo().createObject(StackSlot);
+  Context.expect(FrameIndex && ForeignFrameIndex,
+                 "memory validation stack objects must be created");
+  if (!FrameIndex || !ForeignFrameIndex)
+    return;
+
   auto LoadMemory = Function->createMemOperand(memoryDescription(rcc::MemoryAccessFlag::Load));
   auto StoreMemory = Function->createMemOperand(memoryDescription(rcc::MemoryAccessFlag::Store));
   auto ForeignMemory =
diff --git a/backend/unittests/CodeGen/MachineVerifierTest.cpp b/backend/unittests/CodeGen/MachineVerifierTest.cpp
index b8b985e..82ae68b 100644
--- a/backend/unittests/CodeGen/MachineVerifierTest.cpp
+++ b/backend/unittests/CodeGen/MachineVerifierTest.cpp
@@ -346,12 +346,17 @@ void testPropertyFailures(TestContext &Context) {
   auto Frame = createFunction(Context, "frame_index", 9);
   rcc::MachineBasicBlock *FrameBlock = Frame ? createBlock(Context, *Frame) : nullptr;
   if (Frame && FrameBlock != nullptr) {
+    rcc::StackObjectDesc StackSlot;
+    StackSlot.Size = 8;
+    StackSlot.Align = *rcc::Alignment::create(8);
+    auto FrameIndex = Frame->frameInfo().createObject(StackSlot);
     rcc::MachineIRBuilder Builder(*Frame, *InstructionSet);
-    Context.expect(Builder.setInsertPoint(*FrameBlock).has_value(),
+    Context.expect(FrameIndex && Builder.setInsertPoint(*FrameBlock).has_value(),
                    "frame-index negative test setup must succeed");
+    if (!FrameIndex)
+      return;
     auto Pending = Builder.buildInstr(rcc::Opcode::fromValue(FrameOpcode));
-    Context.expect(Pending && Pending->addFrameIndex(rcc::FrameIndex::fromValue(0)).has_value() &&
-                       Pending->build(),
+    Context.expect(Pending && Pending->addFrameIndex(*FrameIndex).has_value() && Pending->build(),
                    "frame-index negative test instruction must build");
     Frame->properties().set(rcc::MachineFunctionProperty::NoFrameIndices);
     Context.expect(!rcc::MachineVerifier::verify(*Frame, *InstructionSet),
@@ -447,6 +452,47 @@ void testSelectedStateAndPseudoDeadline(TestContext &Context) {
   }
 }
 
+void testFrameStateFailures(TestContext &Context) {
+  auto InstructionSet = createInstructionSet();
+  auto Function = createFunction(Context, "frame_references", 14);
+  rcc::MachineBasicBlock *Block = Function ? createBlock(Context, *Function) : nullptr;
+  if (!InstructionSet || !Function || Block == nullptr)
+    return;
+
+  rcc::MachineIRBuilder Builder(*Function, *InstructionSet);
+  Context.expect(Builder.setInsertPoint(*Block).has_value(),
+                 "frame reference insertion point must be valid");
+  auto Unknown = Builder.buildInstr(rcc::Opcode::fromValue(FrameOpcode));
+  Context.expect(Unknown && Unknown->addFrameIndex(rcc::FrameIndex::fromValue(99)).has_value() &&
+                     !Unknown->build() && Function->allInstructions().empty(),
+                 "builder must reject an unknown frame index before instruction allocation");
+
+  rcc::StackObjectDesc StackSlot;
+  StackSlot.Size = 8;
+  StackSlot.Align = *rcc::Alignment::create(8);
+  auto FrameIndex = Function->frameInfo().createObject(StackSlot);
+  if (!FrameIndex)
+    return;
+  auto Live = Builder.buildInstr(rcc::Opcode::fromValue(FrameOpcode));
+  Context.expect(Live && Live->addFrameIndex(*FrameIndex).has_value() && Live->build(),
+                 "known live frame index must build");
+  Context.expect(Function->frameInfo().markObjectDead(*FrameIndex).has_value() &&
+                     !rcc::MachineVerifier::verify(*Function, *InstructionSet),
+                 "verifier must reject an instruction that references a dead stack object");
+
+  auto Lifetime = createFunction(Context, "frame_lifetime", 15);
+  if (!Lifetime)
+    return;
+  rcc::StackObjectDesc LifetimeSlot;
+  LifetimeSlot.Size = 8;
+  LifetimeSlot.Align = *rcc::Alignment::create(8);
+  LifetimeSlot.Lifetime.push_back(
+      {rcc::MachineInstrStableID::fromValue(1), rcc::MachineInstrStableID::fromValue(2)});
+  Context.expect(Lifetime->frameInfo().createObject(LifetimeSlot).has_value() &&
+                     !rcc::MachineVerifier::verify(*Lifetime, *InstructionSet),
+                 "verifier must reject stack lifetimes that reference unknown instructions");
+}
+
 } // namespace
 
 int main() {
@@ -455,5 +501,6 @@ int main() {
   testReachableStructuralFailures(Context);
   testPropertyFailures(Context);
   testSelectedStateAndPseudoDeadline(Context);
+  testFrameStateFailures(Context);
   return Context.result();
 }