[CodeGen] Split machine liveness components

1 files changed, 174 insertions, 0 deletions

diff --git a/backend/lib/CodeGen/LivePhysRegs.cpp b/backend/lib/CodeGen/LivePhysRegs.cpp
new file mode 100644
index 0000000..9bbc069
--- /dev/null
+++ b/backend/lib/CodeGen/LivePhysRegs.cpp
@@ -0,0 +1,174 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/LivePhysRegs.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/RegisterMask.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <ranges>
+#include <vector>
+
+namespace rcc {
+
+namespace {
+struct OperandFlagUpdate final {
+  MachineOperand *Operand = nullptr;
+  RegisterOperandFlags Flags;
+};
+
+[[nodiscard]] bool intersects(const LiveRegUnits &Live,
+                              const std::vector<PhysicalUnitAccess> &Units) noexcept {
+  return std::ranges::any_of(Units, [&Live](const PhysicalUnitAccess &Unit) {
+    return Live.intersects(Unit.Unit, Unit.Lanes);
+  });
+}
+
+void addUnits(LiveRegUnits &Live, const std::vector<PhysicalUnitAccess> &Units) {
+  for (const PhysicalUnitAccess &Unit : Units)
+    Live.add(Unit.Unit, Unit.Lanes);
+}
+
+void removeUnits(LiveRegUnits &Live, const std::vector<PhysicalUnitAccess> &Units) {
+  for (const PhysicalUnitAccess &Unit : Units)
+    Live.remove(Unit.Unit, Unit.Lanes);
+}
+
+[[nodiscard]] OperandFlagUpdate &getFlagUpdate(std::vector<OperandFlagUpdate> &Updates,
+                                               MachineOperand &Operand) {
+  const auto Position = std::ranges::find_if(
+      Updates, [&Operand](const OperandFlagUpdate &Update) { return Update.Operand == &Operand; });
+  if (Position != Updates.end())
+    return *Position;
+  Updates.push_back({&Operand, Operand.registerFlags()});
+  return Updates.back();
+}
+
+[[nodiscard]] Expected<std::vector<OperandFlagUpdate>>
+buildBlockLivenessRepairPlan(MachineBasicBlock &Block, const TargetDescription &Target,
+                             const MachineBlockLiveness &Boundary) {
+  LiveRegUnits Live = Boundary.PhysicalLiveOut;
+  std::vector<OperandFlagUpdate> Updates;
+  for (MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr;
+       Instruction = Instruction->previous()) {
+    for (const MachineOperand &Operand : Instruction->operands()) {
+      const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>();
+      if (Mask == nullptr)
+        continue;
+      if (!Mask->Mask) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "post-RA liveness repair encountered a null live-out mask");
+      }
+      for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) {
+        if (Mask->Mask->preserves(Register.Reg))
+          addPhysicalRegister(Live, Register);
+      }
+    }
+
+    for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+      MachineOperand *Operand = Instruction->operandAt(Index);
+      if (Operand == nullptr || !Operand->isRegister())
+        continue;
+      OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand);
+      Update.Flags.clear(RegisterOperandFlag::Dead);
+      if (!Operand->isDef())
+        continue;
+      const Register *Reg = Operand->getIf<Register>();
+      if (Reg == nullptr || Reg->isNoRegister())
+        continue;
+      auto Units = physicalOperandUnits(*Operand, Target);
+      if (!Units)
+        return std::unexpected(Units.error());
+      if (!intersects(Live, *Units))
+        Update.Flags.set(RegisterOperandFlag::Dead);
+    }
+
+    for (const MachineOperand &Operand : Instruction->operands()) {
+      if (Operand.isRegister() && Operand.isDef()) {
+        const Register *Reg = Operand.getIf<Register>();
+        if (Reg == nullptr || Reg->isNoRegister())
+          continue;
+        auto Units = physicalOperandUnits(Operand, Target);
+        if (!Units)
+          return std::unexpected(Units.error());
+        removeUnits(Live, *Units);
+        continue;
+      }
+      const auto *Mask = Operand.getIf<RegisterMaskOperand>();
+      if (Mask == nullptr)
+        continue;
+      if (!Mask->Mask) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "post-RA liveness repair encountered a null register mask");
+      }
+      LiveRegUnits Clobbers;
+      for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) {
+        if (Mask->Mask->clobbers(Register.Reg))
+          addPhysicalRegister(Clobbers, Register);
+      }
+      Live.subtract(Clobbers);
+    }
+
+    for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+      MachineOperand *Operand = Instruction->operandAt(Index);
+      if (Operand == nullptr || !Operand->isRegister())
+        continue;
+      OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand);
+      Update.Flags.clear(RegisterOperandFlag::Kill);
+      if (!Operand->isUse() || Operand->isDebugUse() ||
+          Operand->registerFlags().has(RegisterOperandFlag::Undef)) {
+        continue;
+      }
+      const Register *Reg = Operand->getIf<Register>();
+      if (Reg == nullptr || Reg->isNoRegister())
+        continue;
+      if (isReservedPhysicalRegister(*Reg, Block.function(), Target))
+        continue;
+      auto Units = physicalOperandUnits(*Operand, Target);
+      if (!Units)
+        return std::unexpected(Units.error());
+      if (!intersects(Live, *Units))
+        Update.Flags.set(RegisterOperandFlag::Kill);
+      addUnits(Live, *Units);
+    }
+  }
+  if (Live != Boundary.PhysicalLiveIn) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "post-RA local liveness repair changed the block boundary");
+  }
+  return Updates;
+}
+} // namespace
+
+Expected<bool> repairPostRAMachineBlockLiveness(std::span<MachineBasicBlock *const> Blocks,
+                                                const TargetDescription &Target,
+                                                const LiveVariablesAnalysis::Result &Liveness) {
+  std::vector<OperandFlagUpdate> Updates;
+  for (MachineBasicBlock *Block : Blocks) {
+    const MachineBlockLiveness *Boundary = Liveness.block(*Block);
+    if (Boundary == nullptr) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "post-RA scheduler lost a block liveness boundary");
+    }
+    auto BlockUpdates = buildBlockLivenessRepairPlan(*Block, Target, *Boundary);
+    if (!BlockUpdates)
+      return std::unexpected(BlockUpdates.error());
+    Updates.insert(Updates.end(), BlockUpdates->begin(), BlockUpdates->end());
+  }
+  bool Changed = false;
+  for (const OperandFlagUpdate &Update : Updates) {
+    Changed |= Update.Operand->registerFlags() != Update.Flags;
+    auto Applied = Update.Operand->setRegisterFlags(Update.Flags);
+    if (!Applied)
+      return std::unexpected(Applied.error());
+  }
+  return Changed;
+}
+
+} // namespace rcc