[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.

5 files changed, 385 insertions, 5 deletions

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;