[CodeGen] Split machine liveness components

1 files changed, 1031 insertions, 0 deletions

diff --git a/backend/lib/CodeGen/LiveVariables.cpp b/backend/lib/CodeGen/LiveVariables.cpp
new file mode 100644
index 0000000..7323e0d
--- /dev/null
+++ b/backend/lib/CodeGen/LiveVariables.cpp
@@ -0,0 +1,1031 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/LiveVariables.h"
+
+#include "rcc/CodeGen/LiveInterval.h"
+#include "rcc/CodeGen/LiveIntervals.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/RegisterMask.h"
+#include "rcc/CodeGen/SlotIndexes.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+
+#include <algorithm>
+#include <array>
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <string>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+namespace {
+[[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept {
+  return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue());
+}
+
+template <typename KeyT>
+void addLanes(std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, LaneMask Lanes) {
+  if (Lanes.empty())
+    return;
+  const auto Position = Values.find(Key);
+  if (Position == Values.end()) {
+    Values.emplace(Key, Lanes);
+    return;
+  }
+  Position->second = Position->second | Lanes;
+}
+
+template <typename KeyT>
+void removeLanes(std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, LaneMask Lanes) {
+  const auto Position = Values.find(Key);
+  if (Position == Values.end() || Lanes.empty())
+    return;
+  Position->second = subtractLanes(Position->second, Lanes);
+  if (Position->second.empty())
+    Values.erase(Position);
+}
+
+template <typename KeyT>
+[[nodiscard]] LaneMask lanesFor(const std::unordered_map<KeyT, LaneMask> &Values,
+                                KeyT Key) noexcept {
+  const auto Position = Values.find(Key);
+  return Position == Values.end() ? LaneMask{} : Position->second;
+}
+
+template <typename KeyT>
+[[nodiscard]] bool containsLanes(const std::unordered_map<KeyT, LaneMask> &Values, KeyT Key,
+                                 LaneMask Lanes) noexcept {
+  const LaneMask Present = lanesFor(Values, Key);
+  return !Present.empty() && Present.contains(Lanes);
+}
+
+template <typename KeyT>
+[[nodiscard]] bool intersectsLanes(const std::unordered_map<KeyT, LaneMask> &Values, KeyT Key,
+                                   LaneMask Lanes) noexcept {
+  return lanesFor(Values, Key).intersects(Lanes);
+}
+
+template <typename KeyT>
+void uniteLanes(std::unordered_map<KeyT, LaneMask> &Values,
+                const std::unordered_map<KeyT, LaneMask> &Other) {
+  for (const auto &[Key, Lanes] : Other)
+    addLanes(Values, Key, Lanes);
+}
+
+template <typename KeyT>
+void subtractLaneSets(std::unordered_map<KeyT, LaneMask> &Values,
+                      const std::unordered_map<KeyT, LaneMask> &Other) {
+  for (const auto &[Key, Lanes] : Other)
+    removeLanes(Values, Key, Lanes);
+}
+
+[[nodiscard]] Expected<void> addOperandUse(RegisterLaneSet &VirtualUses, LiveRegUnits &PhysicalUses,
+                                           const MachineOperand &Operand,
+                                           const MachineFunction &Function,
+                                           const TargetDescription &Target) {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || Reg->isNoRegister() || Operand.isDebugUse() ||
+      Operand.registerFlags().has(RegisterOperandFlag::Undef)) {
+    return {};
+  }
+  if (Reg->isVirtual()) {
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    VirtualUses.add(*Reg, *Lanes);
+    return {};
+  }
+  if (isReservedPhysicalRegister(*Reg, Function, Target))
+    return {};
+  auto Units = physicalOperandUnits(Operand, Target);
+  if (!Units)
+    return std::unexpected(Units.error());
+  for (const PhysicalUnitAccess &Unit : *Units)
+    PhysicalUses.add(Unit.Unit, Unit.Lanes);
+  return {};
+}
+
+[[nodiscard]] Expected<void> addOperandDef(RegisterLaneSet &VirtualDefs, LiveRegUnits &PhysicalDefs,
+                                           const MachineOperand &Operand,
+                                           const MachineFunction &Function,
+                                           const TargetDescription &Target) {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || Reg->isNoRegister())
+    return {};
+  if (Reg->isVirtual()) {
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    VirtualDefs.add(*Reg, *Lanes);
+    return {};
+  }
+  auto Units = physicalOperandUnits(Operand, Target);
+  if (!Units)
+    return std::unexpected(Units.error());
+  for (const PhysicalUnitAccess &Unit : *Units)
+    PhysicalDefs.add(Unit.Unit, Unit.Lanes);
+  return {};
+}
+
+struct LivenessEdgeKey final {
+  const MachineBasicBlock *Predecessor = nullptr;
+  const MachineBasicBlock *Successor = nullptr;
+
+  friend bool operator==(const LivenessEdgeKey &, const LivenessEdgeKey &) = default;
+};
+
+struct LivenessEdgeKeyHash final {
+  [[nodiscard]] std::size_t operator()(const LivenessEdgeKey &Key) const noexcept {
+    const std::size_t Left = std::hash<const MachineBasicBlock *>{}(Key.Predecessor);
+    const std::size_t Right = std::hash<const MachineBasicBlock *>{}(Key.Successor);
+    return Left ^ (Right + 0x9e3779b9U + (Left << 6U) + (Left >> 2U));
+  }
+};
+
+struct EdgeLivenessUses final {
+  RegisterLaneSet Virtual;
+  LiveRegUnits Physical;
+};
+
+[[nodiscard]] Expected<LiveVariablesAnalysis::Result>
+computeLiveVariables(const MachineFunction &Function, const TargetDescription &Target) {
+  LiveVariablesAnalysis::Result Result;
+  std::vector<const MachineBasicBlock *> Blocks;
+  std::unordered_map<LivenessEdgeKey, EdgeLivenessUses, LivenessEdgeKeyHash> EdgeUses;
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    Blocks.push_back(Block);
+    (void)Result.getOrCreateBlock(*Block);
+  }
+
+  for (const MachineBasicBlock *Block : Blocks) {
+    MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block);
+    if (Block == Function.firstBlock()) {
+      for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) {
+        const PhysicalRegisterDesc *Description =
+            Target.registers().physicalRegister(LiveIn.PhysReg);
+        if (Description == nullptr) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "function live-in references an unknown physical register");
+        }
+        addPhysicalRegister(Liveness.PhysicalUses, *Description);
+        if (LiveIn.InitialVirtualRegister) {
+          auto Lanes = virtualRegisterLanes(*LiveIn.InitialVirtualRegister, Function, Target);
+          if (!Lanes)
+            return std::unexpected(Lanes.error());
+          Liveness.VirtualDefs.add(*LiveIn.InitialVirtualRegister, *Lanes);
+        }
+      }
+    }
+    for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+      if (Descriptor == nullptr) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "liveness encountered an unknown instruction descriptor");
+      }
+      const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi);
+      if (IsPhi) {
+        if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness encountered a malformed PHI instruction");
+        }
+        std::unordered_set<const MachineBasicBlock *> IncomingBlocks;
+        for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) {
+          const MachineOperand *Incoming = Instruction->operandAt(Index);
+          const MachineOperand *PredecessorOperand = Instruction->operandAt(Index + 1U);
+          const auto *Predecessor = PredecessorOperand == nullptr
+                                        ? nullptr
+                                        : PredecessorOperand->getIf<BasicBlockOperand>();
+          if (Incoming == nullptr || Predecessor == nullptr || Predecessor->Block == nullptr) {
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "liveness encountered a malformed PHI incoming pair");
+          }
+          const MachineBasicBlock *IncomingBlock = Predecessor->Block;
+          const bool HasPredecessor = std::ranges::find(Block->predecessors(), IncomingBlock) !=
+                                      Block->predecessors().end();
+          const bool HasSuccessor = std::ranges::any_of(
+              IncomingBlock->successors(),
+              [Block](const MachineSuccessor &Successor) { return Successor.Block == Block; });
+          if (&IncomingBlock->function() != &Function || !IncomingBlock->isLinked() ||
+              !HasPredecessor || !HasSuccessor || !IncomingBlocks.insert(IncomingBlock).second) {
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "liveness encountered a PHI incoming without a unique CFG edge");
+          }
+          EdgeLivenessUses &Uses = EdgeUses[{IncomingBlock, Block}];
+          auto Added = addOperandUse(Uses.Virtual, Uses.Physical, *Incoming, Function, Target);
+          if (!Added)
+            return std::unexpected(Added.error());
+        }
+      }
+
+      RegisterLaneSet InstructionVirtualUses;
+      RegisterLaneSet InstructionVirtualDefs;
+      LiveRegUnits InstructionPhysicalUses;
+      LiveRegUnits InstructionPhysicalDefs;
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        const MachineOperand &Operand = *Instruction->operandAt(Index);
+        if (Operand.isRegister()) {
+          if (Operand.isUse() && (!IsPhi || Index == 0)) {
+            auto Use = addOperandUse(InstructionVirtualUses, InstructionPhysicalUses, Operand,
+                                     Function, Target);
+            if (!Use)
+              return std::unexpected(Use.error());
+          }
+          if (Operand.isDef()) {
+            auto Def = addOperandDef(InstructionVirtualDefs, InstructionPhysicalDefs, Operand,
+                                     Function, Target);
+            if (!Def)
+              return std::unexpected(Def.error());
+          }
+          continue;
+        }
+        if (const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>();
+            MaskOperand != nullptr) {
+          if (!MaskOperand->Mask)
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "liveness encountered a null register mask");
+          auto Added = addRegisterMaskDefs(InstructionPhysicalDefs, *MaskOperand->Mask, Target);
+          if (!Added)
+            return std::unexpected(Added.error());
+          continue;
+        }
+        if (const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>();
+            MaskOperand != nullptr) {
+          if (!MaskOperand->Mask)
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "liveness encountered a null live-out register mask");
+          auto Added = addRegisterMaskUses(InstructionPhysicalUses, *MaskOperand->Mask, Target);
+          if (!Added)
+            return std::unexpected(Added.error());
+        }
+      }
+
+      RegisterLaneSet NewVirtualUses = InstructionVirtualUses;
+      NewVirtualUses.subtract(Liveness.VirtualDefs);
+      Liveness.VirtualUses.unite(NewVirtualUses);
+      Liveness.VirtualDefs.unite(InstructionVirtualDefs);
+
+      LiveRegUnits NewPhysicalUses = InstructionPhysicalUses;
+      NewPhysicalUses.subtract(Liveness.PhysicalDefs);
+      Liveness.PhysicalUses.unite(NewPhysicalUses);
+      Liveness.PhysicalDefs.unite(InstructionPhysicalDefs);
+    }
+  }
+
+  bool Changed = true;
+  while (Changed) {
+    Changed = false;
+    for (const MachineBasicBlock *Block : Blocks | std::views::reverse) {
+      MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block);
+      RegisterLaneSet VirtualOut;
+      LiveRegUnits PhysicalOut;
+      for (const MachineSuccessor &Successor : Block->successors()) {
+        if (Successor.Block == nullptr || Result.block(*Successor.Block) == nullptr) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness encountered an invalid CFG successor");
+        }
+        const MachineBlockLiveness &SuccessorLiveness = *Result.block(*Successor.Block);
+        VirtualOut.unite(SuccessorLiveness.VirtualLiveIn);
+        PhysicalOut.unite(SuccessorLiveness.PhysicalLiveIn);
+        const auto Edge = EdgeUses.find({Block, Successor.Block});
+        if (Edge != EdgeUses.end()) {
+          VirtualOut.unite(Edge->second.Virtual);
+          PhysicalOut.unite(Edge->second.Physical);
+        }
+      }
+
+      RegisterLaneSet VirtualIn = VirtualOut;
+      VirtualIn.subtract(Liveness.VirtualDefs);
+      VirtualIn.unite(Liveness.VirtualUses);
+      LiveRegUnits PhysicalIn = PhysicalOut;
+      PhysicalIn.subtract(Liveness.PhysicalDefs);
+      PhysicalIn.unite(Liveness.PhysicalUses);
+
+      if (VirtualOut != Liveness.VirtualLiveOut || VirtualIn != Liveness.VirtualLiveIn ||
+          PhysicalOut != Liveness.PhysicalLiveOut || PhysicalIn != Liveness.PhysicalLiveIn) {
+        Liveness.VirtualLiveOut = std::move(VirtualOut);
+        Liveness.VirtualLiveIn = std::move(VirtualIn);
+        Liveness.PhysicalLiveOut = std::move(PhysicalOut);
+        Liveness.PhysicalLiveIn = std::move(PhysicalIn);
+        Changed = true;
+      }
+    }
+  }
+  return Result;
+}
+[[nodiscard]] Expected<std::vector<MachineBasicBlockLiveIn>>
+canonicalPhysicalLiveIns(const LiveRegUnits &Units, const TargetDescription &Target) {
+  struct Candidate final {
+    const PhysicalRegisterDesc *Description = nullptr;
+    LaneMask RegisterLanes;
+    LiveRegUnits Coverage;
+    std::size_t ExtraLanes = 0;
+    bool Selected = false;
+  };
+
+  std::vector<Candidate> Candidates;
+  for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) {
+    const LaneMask FullLanes = physicalRegisterLanes(Description);
+    std::uint64_t SelectableLanes = 0;
+    LaneMask RelevantLanes;
+    for (const RegisterUnitLane &Unit : Description.Units) {
+      RelevantLanes = RelevantLanes | denormalizeUnitLanes(Units.lanes(Unit.Unit), Unit.Lanes);
+    }
+    std::uint64_t PendingLanes = RelevantLanes.rawValue();
+    while (PendingLanes != 0) {
+      const std::uint64_t Lane = std::uint64_t{1} << std::countr_zero(PendingLanes);
+      const LiveRegUnits Coverage = physicalRegisterCoverage(Description, LaneMask::fromRaw(Lane));
+      if (isSubset(Coverage, Units))
+        SelectableLanes |= Lane;
+      PendingLanes &= PendingLanes - 1U;
+    }
+    if (SelectableLanes == 0)
+      continue;
+    Candidate Value;
+    Value.Description = &Description;
+    Value.RegisterLanes = LaneMask::fromRaw(SelectableLanes);
+    Value.Coverage = physicalRegisterCoverage(Description, Value.RegisterLanes);
+    Value.ExtraLanes = static_cast<std::size_t>(std::popcount(FullLanes.rawValue()) -
+                                                std::popcount(SelectableLanes));
+    Candidates.push_back(std::move(Value));
+  }
+
+  LiveRegUnits Covered;
+  std::vector<MachineBasicBlockLiveIn> Result;
+  while (Covered != Units) {
+    Candidate *Best = nullptr;
+    std::size_t BestNewLanes = 0;
+    std::size_t BestCoverage = 0;
+    for (Candidate &Value : Candidates) {
+      if (Value.Selected)
+        continue;
+      LiveRegUnits NewCoverage = Value.Coverage;
+      NewCoverage.subtract(Covered);
+      const std::size_t NewLanes = laneCount(NewCoverage);
+      if (NewLanes == 0)
+        continue;
+      const std::size_t Coverage = laneCount(Value.Coverage);
+      if (Best == nullptr || NewLanes > BestNewLanes ||
+          (NewLanes == BestNewLanes && Value.ExtraLanes < Best->ExtraLanes) ||
+          (NewLanes == BestNewLanes && Value.ExtraLanes == Best->ExtraLanes &&
+           Coverage > BestCoverage) ||
+          (NewLanes == BestNewLanes && Value.ExtraLanes == Best->ExtraLanes &&
+           Coverage == BestCoverage &&
+           Value.Description->Reg.number() < Best->Description->Reg.number())) {
+        Best = &Value;
+        BestNewLanes = NewLanes;
+        BestCoverage = Coverage;
+      }
+    }
+    if (Best == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "physical live-in units cannot be represented by target registers");
+    }
+    Best->Selected = true;
+    Covered.unite(Best->Coverage);
+    const LaneMask FullLanes = physicalRegisterLanes(*Best->Description);
+    const LaneMask Lanes = Best->RegisterLanes == FullLanes ? LaneMask::all() : Best->RegisterLanes;
+    Result.push_back({Best->Description->Reg, Lanes});
+  }
+  std::ranges::sort(Result,
+                    [](const MachineBasicBlockLiveIn &Left, const MachineBasicBlockLiveIn &Right) {
+                      return Left.PhysReg.number() < Right.PhysReg.number();
+                    });
+  return Result;
+}
+
+[[nodiscard]] Expected<LiveRegUnits> liveInUnits(std::span<const MachineBasicBlockLiveIn> LiveIns,
+                                                 const TargetDescription &Target) {
+  LiveRegUnits Result;
+  for (const MachineBasicBlockLiveIn &LiveIn : LiveIns) {
+    const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(LiveIn.PhysReg);
+    if (Description == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "block live-in references an unknown physical register");
+    }
+    Result.unite(physicalRegisterCoverage(*Description, LiveIn.Lanes));
+  }
+  return Result;
+}
+
+struct OperandFlagPlan final {
+  MachineInstrStableID Instruction;
+  std::size_t OperandIndex = 0;
+  RegisterOperandFlags Original;
+  RegisterOperandFlags Rebuilt;
+  bool KillIsValid = false;
+  bool DeadIsValid = false;
+};
+
+struct BlockLivenessPlan final {
+  MachineBlockStableID Block;
+  std::vector<MachineBasicBlockLiveIn> OriginalLiveIns;
+  std::vector<MachineBasicBlockLiveIn> RebuiltLiveIns;
+};
+
+struct LivenessRebuildPlan final {
+  std::vector<BlockLivenessPlan> Blocks;
+  std::vector<OperandFlagPlan> Operands;
+};
+
+[[nodiscard]] Expected<bool>
+liveSetIntersects(const MachineOperand &Operand, const RegisterLaneSet &Virtual,
+                  const LiveRegUnits &Physical, const MachineFunction &Function,
+                  const TargetDescription &Target, bool TreatReservedAsLive) {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || Reg->isNoRegister())
+    return false;
+  if (Reg->isVirtual()) {
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    return Virtual.intersects(*Reg, *Lanes);
+  }
+  if (TreatReservedAsLive && isReservedPhysicalRegister(*Reg, Function, Target))
+    return true;
+  auto Units = physicalOperandUnits(Operand, Target);
+  if (!Units)
+    return std::unexpected(Units.error());
+  return std::ranges::any_of(*Units, [&Physical](const PhysicalUnitAccess &Unit) {
+    return Physical.intersects(Unit.Unit, Unit.Lanes);
+  });
+}
+
+[[nodiscard]] Expected<void> removeOperandFromLiveSet(const MachineOperand &Operand,
+                                                      RegisterLaneSet &Virtual,
+                                                      LiveRegUnits &Physical,
+                                                      const MachineFunction &Function,
+                                                      const TargetDescription &Target) {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || Reg->isNoRegister())
+    return {};
+  if (Reg->isVirtual()) {
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    Virtual.remove(*Reg, *Lanes);
+    return {};
+  }
+  auto Units = physicalOperandUnits(Operand, Target);
+  if (!Units)
+    return std::unexpected(Units.error());
+  for (const PhysicalUnitAccess &Unit : *Units)
+    Physical.remove(Unit.Unit, Unit.Lanes);
+  return {};
+}
+
+[[nodiscard]] Expected<void> addOperandToLiveSet(const MachineOperand &Operand,
+                                                 RegisterLaneSet &Virtual, LiveRegUnits &Physical,
+                                                 const MachineFunction &Function,
+                                                 const TargetDescription &Target) {
+  return addOperandUse(Virtual, Physical, Operand, Function, Target);
+}
+
+[[nodiscard]] Expected<LiveRegUnits> requiredLocalPhysicalLiveIns(const MachineBasicBlock &Block,
+                                                                  const MachineFunction &Function,
+                                                                  const TargetDescription &Target) {
+  RegisterLaneSet Virtual;
+  LiveRegUnits Physical;
+  for (const MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr;
+       Instruction = Instruction->previous()) {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "liveness verification encountered an unknown instruction descriptor");
+    }
+    const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi);
+    for (const MachineOperand &Operand : Instruction->operands()) {
+      const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>();
+      if (MaskOperand == nullptr)
+        continue;
+      if (!MaskOperand->Mask) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "liveness verification encountered a null live-out register mask");
+      }
+      auto Added = addRegisterMaskUses(Physical, *MaskOperand->Mask, Target);
+      if (!Added)
+        return std::unexpected(Added.error());
+    }
+
+    for (const MachineOperand &Operand : Instruction->operands()) {
+      if (Operand.isRegister() && Operand.isDef()) {
+        auto Removed = removeOperandFromLiveSet(Operand, Virtual, Physical, Function, Target);
+        if (!Removed)
+          return std::unexpected(Removed.error());
+        continue;
+      }
+      const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>();
+      if (MaskOperand == nullptr)
+        continue;
+      if (!MaskOperand->Mask) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "liveness verification encountered a null register mask");
+      }
+      LiveRegUnits Clobbers;
+      auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target);
+      if (!Added)
+        return std::unexpected(Added.error());
+      Physical.subtract(Clobbers);
+    }
+
+    if (IsPhi)
+      continue;
+    for (const MachineOperand &Operand : Instruction->operands()) {
+      if (!Operand.isRegister() || !Operand.isUse())
+        continue;
+      auto Added = addOperandToLiveSet(Operand, Virtual, Physical, Function, Target);
+      if (!Added)
+        return std::unexpected(Added.error());
+    }
+  }
+  return Physical;
+}
+
+[[nodiscard]] Expected<LivenessRebuildPlan>
+buildLivenessRebuildPlan(const MachineFunction &Function, const TargetDescription &Target) {
+  auto Variables = computeLiveVariables(Function, Target);
+  if (!Variables)
+    return std::unexpected(Variables.error());
+
+  LivenessRebuildPlan Plan;
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    const MachineBlockLiveness *BlockVariables = Variables->block(*Block);
+    if (BlockVariables == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "liveness result omitted a machine block");
+    auto NewLiveIns = canonicalPhysicalLiveIns(BlockVariables->PhysicalLiveIn, Target);
+    if (!NewLiveIns)
+      return std::unexpected(NewLiveIns.error());
+    Plan.Blocks.push_back(
+        {Block->stableID(),
+         std::vector<MachineBasicBlockLiveIn>(Block->liveIns().begin(), Block->liveIns().end()),
+         std::move(*NewLiveIns)});
+
+    RegisterLaneSet Virtual = BlockVariables->VirtualLiveOut;
+    LiveRegUnits Physical = BlockVariables->PhysicalLiveOut;
+    for (const MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr;
+         Instruction = Instruction->previous()) {
+      const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+      if (Descriptor == nullptr) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "liveness rebuild encountered an unknown instruction descriptor");
+      }
+      const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi);
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>();
+        if (MaskOperand == nullptr)
+          continue;
+        if (!MaskOperand->Mask)
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness rebuild encountered a null live-out register mask");
+        auto Added = addRegisterMaskUses(Physical, *MaskOperand->Mask, Target);
+        if (!Added)
+          return std::unexpected(Added.error());
+      }
+
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        const MachineOperand *Operand = Instruction->operandAt(Index);
+        if (Operand == nullptr || !Operand->isRegister() || !Operand->isDef())
+          continue;
+        auto IsLive = liveSetIntersects(*Operand, Virtual, Physical, Function, Target, false);
+        if (!IsLive)
+          return std::unexpected(IsLive.error());
+        RegisterOperandFlags Flags = Operand->registerFlags();
+        Flags.clear(RegisterOperandFlag::Dead);
+        if (!*IsLive)
+          Flags.set(RegisterOperandFlag::Dead);
+        Plan.Operands.push_back(
+            {Instruction->stableID(), Index, Operand->registerFlags(), Flags, false, !*IsLive});
+      }
+
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        if (Operand.isRegister() && Operand.isDef()) {
+          auto Removed = removeOperandFromLiveSet(Operand, Virtual, Physical, Function, Target);
+          if (!Removed)
+            return std::unexpected(Removed.error());
+          continue;
+        }
+        const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>();
+        if (MaskOperand == nullptr)
+          continue;
+        if (!MaskOperand->Mask)
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness rebuild encountered a null register mask");
+        LiveRegUnits Clobbers;
+        auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target);
+        if (!Added)
+          return std::unexpected(Added.error());
+        Physical.subtract(Clobbers);
+      }
+
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        const MachineOperand *Operand = Instruction->operandAt(Index);
+        if (Operand == nullptr || !Operand->isRegister() || !Operand->isUse())
+          continue;
+        if (IsPhi) {
+          RegisterOperandFlags Flags = Operand->registerFlags();
+          Flags.clear(RegisterOperandFlag::Kill);
+          const auto Existing = std::ranges::find_if(
+              Plan.Operands, [Instruction, Index](const OperandFlagPlan &Entry) {
+                return Entry.Instruction == Instruction->stableID() && Entry.OperandIndex == Index;
+              });
+          if (Existing == Plan.Operands.end()) {
+            Plan.Operands.push_back(
+                {Instruction->stableID(), Index, Operand->registerFlags(), Flags, false, false});
+          } else {
+            Existing->Rebuilt.clear(RegisterOperandFlag::Kill);
+            Existing->KillIsValid = false;
+          }
+          continue;
+        }
+        const bool IsSemanticUse = !Operand->isDebugUse() &&
+                                   !Operand->registerFlags().has(RegisterOperandFlag::Undef) &&
+                                   !Operand->registerValue()->isNoRegister();
+        bool IsKill = false;
+        if (IsSemanticUse) {
+          auto IsLive = liveSetIntersects(*Operand, Virtual, Physical, Function, Target, true);
+          if (!IsLive)
+            return std::unexpected(IsLive.error());
+          IsKill = !*IsLive;
+        }
+        RegisterOperandFlags Flags = Operand->registerFlags();
+        Flags.clear(RegisterOperandFlag::Kill);
+        if (IsKill)
+          Flags.set(RegisterOperandFlag::Kill);
+
+        const auto Existing =
+            std::ranges::find_if(Plan.Operands, [Instruction, Index](const OperandFlagPlan &Entry) {
+              return Entry.Instruction == Instruction->stableID() && Entry.OperandIndex == Index;
+            });
+        if (Existing == Plan.Operands.end()) {
+          Plan.Operands.push_back(
+              {Instruction->stableID(), Index, Operand->registerFlags(), Flags, IsKill, false});
+        } else {
+          Existing->Rebuilt.clear(RegisterOperandFlag::Kill);
+          if (IsKill)
+            Existing->Rebuilt.set(RegisterOperandFlag::Kill);
+          Existing->KillIsValid = IsKill;
+        }
+        if (IsSemanticUse) {
+          auto Added = addOperandToLiveSet(*Operand, Virtual, Physical, Function, Target);
+          if (!Added)
+            return std::unexpected(Added.error());
+        }
+      }
+    }
+
+    if (Block == Function.firstBlock()) {
+      for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) {
+        const PhysicalRegisterDesc *Description =
+            Target.registers().physicalRegister(LiveIn.PhysReg);
+        if (Description == nullptr) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness rebuild encountered an unknown function live-in");
+        }
+        addPhysicalRegister(Physical, *Description);
+        if (LiveIn.InitialVirtualRegister) {
+          auto Lanes = virtualRegisterLanes(*LiveIn.InitialVirtualRegister, Function, Target);
+          if (!Lanes)
+            return std::unexpected(Lanes.error());
+          Virtual.remove(*LiveIn.InitialVirtualRegister, *Lanes);
+        }
+      }
+    }
+
+    if (Virtual != BlockVariables->VirtualLiveIn || Physical != BlockVariables->PhysicalLiveIn) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "reverse liveness reconstruction disagrees with block dataflow");
+    }
+  }
+  return Plan;
+}
+
+struct ResolvedBlockLivenessPlan final {
+  MachineBasicBlock *Block = nullptr;
+  const BlockLivenessPlan *Plan = nullptr;
+};
+
+struct ResolvedOperandFlagPlan final {
+  MachineOperand *Operand = nullptr;
+  const OperandFlagPlan *Plan = nullptr;
+};
+
+struct ResolvedLivenessRebuildPlan final {
+  std::vector<ResolvedBlockLivenessPlan> Blocks;
+  std::vector<ResolvedOperandFlagPlan> Operands;
+};
+
+[[nodiscard]] Expected<ResolvedLivenessRebuildPlan>
+resolveLivenessPlan(MachineFunction &Function, const LivenessRebuildPlan &Plan) {
+  ResolvedLivenessRebuildPlan Result;
+  Result.Blocks.reserve(Plan.Blocks.size());
+  for (const BlockLivenessPlan &BlockPlan : Plan.Blocks) {
+    const auto Position =
+        std::ranges::find_if(Function.allBlocks(), [&BlockPlan](const MachineBasicBlock *Block) {
+          return Block != nullptr && Block->stableID() == BlockPlan.Block;
+        });
+    if (Position == Function.allBlocks().end() || !(*Position)->isLinked()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "liveness rebuild plan references an unavailable machine block");
+    }
+    Result.Blocks.push_back({*Position, &BlockPlan});
+  }
+
+  Result.Operands.reserve(Plan.Operands.size());
+  for (const OperandFlagPlan &OperandPlan : Plan.Operands) {
+    const auto Position = std::ranges::find_if(
+        Function.allInstructions(), [&OperandPlan](const MachineInstr *Instruction) {
+          return Instruction != nullptr && Instruction->stableID() == OperandPlan.Instruction;
+        });
+    if (Position == Function.allInstructions().end() || !(*Position)->isLinked()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "liveness rebuild plan references an unavailable instruction");
+    }
+    MachineOperand *Operand = (*Position)->operandAt(OperandPlan.OperandIndex);
+    if (Operand == nullptr) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "liveness rebuild plan references an unavailable operand");
+    }
+    Result.Operands.push_back({Operand, &OperandPlan});
+  }
+  return Result;
+}
+
+[[nodiscard]] Expected<void> restoreLivenessPlan(const ResolvedLivenessRebuildPlan &Plan) {
+  for (const ResolvedBlockLivenessPlan &Resolved : Plan.Blocks) {
+    Resolved.Block->clearLiveIns();
+    for (const MachineBasicBlockLiveIn &LiveIn : Resolved.Plan->OriginalLiveIns) {
+      auto Restored = Resolved.Block->addLiveIn(LiveIn.PhysReg, LiveIn.Lanes);
+      if (!Restored)
+        return std::unexpected(Restored.error());
+    }
+  }
+  for (const ResolvedOperandFlagPlan &Resolved : Plan.Operands) {
+    auto Restored = Resolved.Operand->setRegisterFlags(Resolved.Plan->Original);
+    if (!Restored)
+      return std::unexpected(Restored.error());
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<bool> applyLivenessPlan(MachineFunction &Function,
+                                               const LivenessRebuildPlan &Plan) {
+  auto Resolved = resolveLivenessPlan(Function, Plan);
+  if (!Resolved)
+    return std::unexpected(Resolved.error());
+
+  bool Changed = false;
+  for (const ResolvedBlockLivenessPlan &BlockPlan : Resolved->Blocks) {
+    Changed |= BlockPlan.Plan->OriginalLiveIns != BlockPlan.Plan->RebuiltLiveIns;
+    BlockPlan.Block->clearLiveIns();
+    for (const MachineBasicBlockLiveIn &LiveIn : BlockPlan.Plan->RebuiltLiveIns) {
+      auto Added = BlockPlan.Block->addLiveIn(LiveIn.PhysReg, LiveIn.Lanes);
+      if (!Added) {
+        auto Restored = restoreLivenessPlan(*Resolved);
+        if (!Restored)
+          return makeUnexpected(ErrorCode::InternalError,
+                                "liveness rebuild failed and rollback also failed");
+        return std::unexpected(Added.error());
+      }
+    }
+  }
+  for (const ResolvedOperandFlagPlan &OperandPlan : Resolved->Operands) {
+    Changed |= OperandPlan.Plan->Original != OperandPlan.Plan->Rebuilt;
+    auto Updated = OperandPlan.Operand->setRegisterFlags(OperandPlan.Plan->Rebuilt);
+    if (!Updated) {
+      auto Restored = restoreLivenessPlan(*Resolved);
+      if (!Restored)
+        return makeUnexpected(ErrorCode::InternalError,
+                              "liveness rebuild failed and rollback also failed");
+      return std::unexpected(Updated.error());
+    }
+  }
+  return Changed;
+}
+} // namespace
+
+LaneMask RegisterLaneSet::lanes(Register Reg) const noexcept {
+  return lanesFor(Values, Reg);
+}
+
+bool RegisterLaneSet::contains(Register Reg, LaneMask Lanes) const noexcept {
+  return containsLanes(Values, Reg, Lanes);
+}
+
+bool RegisterLaneSet::intersects(Register Reg, LaneMask Lanes) const noexcept {
+  return intersectsLanes(Values, Reg, Lanes);
+}
+
+void RegisterLaneSet::add(Register Reg, LaneMask Lanes) {
+  if (!Reg.isNoRegister())
+    addLanes(Values, Reg, Lanes);
+}
+
+void RegisterLaneSet::remove(Register Reg, LaneMask Lanes) {
+  removeLanes(Values, Reg, Lanes);
+}
+
+void RegisterLaneSet::unite(const RegisterLaneSet &Other) {
+  uniteLanes(Values, Other.Values);
+}
+
+void RegisterLaneSet::subtract(const RegisterLaneSet &Other) {
+  subtractLaneSets(Values, Other.Values);
+}
+const MachineBlockLiveness *
+LiveVariablesAnalysis::Result::block(const MachineBasicBlock &Block) const noexcept {
+  const auto Position = Blocks.find(&Block);
+  return Position == Blocks.end() ? nullptr : &Position->second;
+}
+
+MachineBlockLiveness &
+LiveVariablesAnalysis::Result::getOrCreateBlock(const MachineBasicBlock &Block) {
+  return Blocks[&Block];
+}
+
+bool LiveVariablesAnalysis::Result::isLiveIn(const MachineBasicBlock &Block, Register Reg,
+                                             LaneMask Lanes) const noexcept {
+  const MachineBlockLiveness *Value = block(Block);
+  return Value != nullptr && Value->VirtualLiveIn.intersects(Reg, Lanes);
+}
+
+bool LiveVariablesAnalysis::Result::isLiveOut(const MachineBasicBlock &Block, Register Reg,
+                                              LaneMask Lanes) const noexcept {
+  const MachineBlockLiveness *Value = block(Block);
+  return Value != nullptr && Value->VirtualLiveOut.intersects(Reg, Lanes);
+}
+
+bool LiveVariablesAnalysis::Result::isUnitLiveIn(const MachineBasicBlock &Block,
+                                                 RegisterUnitID Unit,
+                                                 LaneMask Lanes) const noexcept {
+  const MachineBlockLiveness *Value = block(Block);
+  return Value != nullptr && Value->PhysicalLiveIn.intersects(Unit, Lanes);
+}
+
+bool LiveVariablesAnalysis::Result::isUnitLiveOut(const MachineBasicBlock &Block,
+                                                  RegisterUnitID Unit,
+                                                  LaneMask Lanes) const noexcept {
+  const MachineBlockLiveness *Value = block(Block);
+  return Value != nullptr && Value->PhysicalLiveOut.intersects(Unit, Lanes);
+}
+
+bool LiveVariablesAnalysis::Result::invalidate(const MachineFunction &,
+                                               const PreservedAnalyses &Preserved) const noexcept {
+  return !Preserved.preserves(MachineAnalysisManager::id<LiveVariablesAnalysis>());
+}
+
+Expected<LiveVariablesAnalysis::Result> LiveVariablesAnalysis::run(MachineFunction &Function,
+                                                                   const TargetDescription &Target,
+                                                                   MachineAnalysisManager &) {
+  return computeLiveVariables(Function, Target);
+}
+const MachinePassContract &RebuildMachineLivenessPass::contract() const noexcept {
+  static const MachinePassContract Contract = [] {
+    MachinePassContract Value{
+        .Name = "RebuildMachineLiveness",
+        .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
+                     MachineFunctionProperty::TiedOpsRewritten},
+        .Sets = {MachineFunctionProperty::TracksLiveness},
+        .Clears = {},
+        .RequiredAnalyses = {},
+        .VerificationStage = std::nullopt,
+    };
+    Value.DeclaredChanges = {MachinePassChange::Operands};
+    return Value;
+  }();
+  return Contract;
+}
+
+Expected<MachinePassResult> RebuildMachineLivenessPass::run(MachineFunction &Function,
+                                                            const TargetDescription &Target,
+                                                            MachineAnalysisManager &) {
+  const MachineFunctionProperties Missing = contract().Requires.missingFrom(Function.properties());
+  if (!Missing.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RebuildMachineLiveness requires properties: " + Missing.toString());
+  }
+  auto Applied = rebuildMachineLiveness(Function, Target);
+  if (!Applied)
+    return std::unexpected(Applied.error());
+
+  MachinePassResult Result;
+  Result.Changed = *Applied;
+  if (Result.Changed)
+    Result.Changes.add(MachinePassChange::Operands);
+  Result.Preserved = PreservedAnalyses::all();
+  return Result;
+}
+
+Expected<bool> rebuildMachineLiveness(MachineFunction &Function, const TargetDescription &Target) {
+  auto Plan = buildLivenessRebuildPlan(Function, Target);
+  if (!Plan)
+    return std::unexpected(Plan.error());
+  return applyLivenessPlan(Function, *Plan);
+}
+
+Expected<void> verifyTrackedMachineLiveness(const MachineFunction &Function,
+                                            const TargetDescription &Target) {
+  auto Plan = buildLivenessRebuildPlan(Function, Target);
+  if (!Plan)
+    return std::unexpected(Plan.error());
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    auto Actual = liveInUnits(Block->liveIns(), Target);
+    if (!Actual)
+      return std::unexpected(Actual.error());
+    auto Expected = requiredLocalPhysicalLiveIns(*Block, Function, Target);
+    if (!Expected)
+      return std::unexpected(Expected.error());
+    if (!isSubset(*Expected, *Actual)) {
+      const auto Missing = std::ranges::find_if(Expected->entries(), [&Actual](const auto &Entry) {
+        return !Actual->contains(Entry.first, Entry.second);
+      });
+      if (Missing != Expected->entries().end()) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "TracksLiveness block " + std::to_string(Block->stableID().value()) +
+                                  " is missing required physical register unit " +
+                                  std::to_string(Missing->first.value()));
+      }
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "TracksLiveness block is missing required physical live-ins");
+    }
+  }
+  for (const OperandFlagPlan &OperandPlan : Plan->Operands) {
+    if (OperandPlan.Original.has(RegisterOperandFlag::Kill) && !OperandPlan.KillIsValid) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "TracksLiveness operand has a stale kill flag");
+    }
+    if (OperandPlan.Original.has(RegisterOperandFlag::Dead) && !OperandPlan.DeadIsValid) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "TracksLiveness operand has a stale dead flag");
+    }
+  }
+  return {};
+}
+
+Expected<void> registerStage11MachineAnalyses(MachineAnalysisManager &Analyses) {
+  const std::array IDs{
+      MachineAnalysisManager::id<SlotIndexesAnalysis>(),
+      MachineAnalysisManager::id<LiveVariablesAnalysis>(),
+      MachineAnalysisManager::id<LiveIntervalsAnalysis>(),
+  };
+  const std::size_t Registered = static_cast<std::size_t>(
+      std::ranges::count_if(IDs, [&Analyses](AnalysisID ID) { return Analyses.isRegistered(ID); }));
+  if (Registered == IDs.size())
+    return {};
+  if (Registered != 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "standard liveness analyses are only partially registered");
+  }
+
+  auto Candidate = Analyses.forkEmpty();
+  if (!Candidate)
+    return std::unexpected(Candidate.error());
+  MachineAnalysisManager &Staging = **Candidate;
+  auto Slots = Staging.registerAnalysis<SlotIndexesAnalysis>({
+      .Name = "SlotIndexes",
+      .Dependencies = {},
+      .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::BlockLayout},
+      .ThreadSafety = PassThreadSafety::ThreadSafe,
+  });
+  if (!Slots)
+    return std::unexpected(Slots.error());
+  auto Variables = Staging.registerAnalysis<LiveVariablesAnalysis>({
+      .Name = "LiveVariables",
+      .Dependencies = {},
+      .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands,
+                        MachinePassChange::Registers, MachinePassChange::CFG,
+                        MachinePassChange::TargetState},
+      .ThreadSafety = PassThreadSafety::ThreadSafe,
+  });
+  if (!Variables)
+    return std::unexpected(Variables.error());
+  auto Intervals = Staging.registerAnalysis<LiveIntervalsAnalysis>({
+      .Name = "LiveIntervals",
+      .Dependencies = {MachineAnalysisManager::id<SlotIndexesAnalysis>(),
+                       MachineAnalysisManager::id<LiveVariablesAnalysis>()},
+      .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands,
+                        MachinePassChange::Registers, MachinePassChange::CFG,
+                        MachinePassChange::BlockLayout, MachinePassChange::TargetState},
+      .ThreadSafety = PassThreadSafety::ThreadSafe,
+  });
+  if (!Intervals)
+    return std::unexpected(Intervals.error());
+  Analyses.Registry = std::move(Staging.Registry);
+  return {};
+}
+
+} // namespace rcc