[CodeGen] Complete register allocation infrastructure

1 files changed, 236 insertions, 0 deletions

diff --git a/backend/lib/CodeGen/RegAllocInternal.h b/backend/lib/CodeGen/RegAllocInternal.h
new file mode 100644
index 0000000..5d0f434
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocInternal.h
@@ -0,0 +1,236 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// The private header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
+#ifndef RCC_LIB_CODEGEN_REGALLOCINTERNAL_H
+#define RCC_LIB_CODEGEN_REGALLOCINTERNAL_H
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionCloner.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/RegAllocCommon.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+#include "rcc/CodeGen/VirtRegMap.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace rcc::regalloc_detail {
+
+struct AllocationRunResult final {
+  bool Changed = false;
+  bool ChangedInstructions = false;
+  bool ChangedFrame = false;
+};
+
+[[nodiscard]] inline Error withPrefix(const Error &Failure, std::string_view Prefix) {
+  std::string Message(Prefix);
+  Message.append(Failure.message());
+  return Error(Failure.code(), std::move(Message));
+}
+
+[[nodiscard]] inline Expected<Register> virtualRegisterAt(std::size_t Index) {
+  auto Reg = Register::makeVirtual(Index);
+  if (!Reg)
+    return std::unexpected(Reg.error());
+  return *Reg;
+}
+
+[[nodiscard]] inline Expected<RegisterClassID> registerClassFor(const MachineFunction &Function,
+                                                                Register VirtualReg) {
+  auto Info = Function.registerInfo().virtualRegisterInfo(VirtualReg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  const auto ClassID = Info->get().RegClass;
+  if (!ClassID) {
+    return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                          "virtual register has no register class after instruction selection");
+  }
+  return ClassID.value();
+}
+
+[[nodiscard]] inline bool isUnavailablePhysicalRegister(const MachineFunction &Function,
+                                                        const TargetRegisterInfo &Registers,
+                                                        PhysicalRegister Reg) noexcept {
+  const PhysicalRegisterDesc *Description = Registers.physicalRegister(Reg);
+  return Description == nullptr || Description->IsConstant || Description->IsArtificial ||
+         Description->IsReserved || Registers.isReservedRegister(Reg) ||
+         Function.registerInfo().isReserved(Reg);
+}
+
+[[nodiscard]] inline bool candidateSupportsSubRegisters(const MachineFunction &Function,
+                                                        const TargetRegisterInfo &Registers,
+                                                        Register VirtualReg,
+                                                        PhysicalRegister Candidate) noexcept {
+  for (const MachineOperand &Operand :
+       const_cast<MachineRegisterInfo &>(Function.registerInfo()).regOperands(VirtualReg)) {
+    if (Operand.subReg().value() != 0 && !Registers.subRegister(Candidate, Operand.subReg()))
+      return false;
+  }
+  return true;
+}
+
+[[nodiscard]] inline Expected<std::vector<PhysicalRegister>>
+allocationOrder(const MachineFunction &Function, const TargetDescription &Target,
+                Register VirtualReg) {
+  auto ClassID = registerClassFor(Function, VirtualReg);
+  if (!ClassID)
+    return std::unexpected(ClassID.error());
+  const RegisterClassDesc *Class = Target.registers().registerClass(*ClassID);
+  if (Class == nullptr || !Class->Allocatable || Class->AllocationOrder.empty()) {
+    return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                          "virtual register class has no allocatable physical registers");
+  }
+
+  auto Info = Function.registerInfo().virtualRegisterInfo(VirtualReg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  std::vector<PhysicalRegister> Result;
+  Result.reserve(Class->AllocationOrder.size());
+  for (const PhysicalRegister Hint : Info->get().AllocationHints) {
+    if (std::ranges::find(Class->AllocationOrder, Hint) != Class->AllocationOrder.end() &&
+        std::ranges::find(Result, Hint) == Result.end())
+      Result.push_back(Hint);
+  }
+  for (const PhysicalRegister Candidate : Class->AllocationOrder) {
+    if (std::ranges::find(Result, Candidate) == Result.end())
+      Result.push_back(Candidate);
+  }
+  std::erase_if(Result, [&](PhysicalRegister Candidate) {
+    return isUnavailablePhysicalRegister(Function, Target.registers(), Candidate) ||
+           !candidateSupportsSubRegisters(Function, Target.registers(), VirtualReg, Candidate);
+  });
+  return Result;
+}
+
+[[nodiscard]] inline MachineInstr *firstTerminator(MachineBasicBlock &Block,
+                                                   const TargetDescription &Target) noexcept {
+  for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator))
+      return Instruction;
+  }
+  return nullptr;
+}
+
+[[nodiscard]] inline bool hasTerminatorDefinition(const MachineFunction &Function,
+                                                  const TargetDescription &Target,
+                                                  Register VirtualReg) noexcept {
+  for (const MachineOperand &Operand :
+       const_cast<MachineRegisterInfo &>(Function.registerInfo()).defOperands(VirtualReg)) {
+    const MachineInstr *Instruction = Operand.parent();
+    const InstructionDescriptor *Descriptor =
+        Instruction == nullptr ? nullptr : Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator))
+      return true;
+  }
+  return false;
+}
+
+[[nodiscard]] inline std::uint64_t allocationFingerprint(const MachineFunction &Function) noexcept {
+  std::uint64_t Hash = 1469598103934665603ULL;
+  auto Mix = [&Hash](std::uint64_t Value) {
+    Hash ^= Value;
+    Hash *= 1099511628211ULL;
+  };
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    Mix(Block->stableID().value());
+    for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      Mix(Instruction->opcode().value());
+      Mix(Instruction->stableID().value());
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        Mix(static_cast<std::uint64_t>(Operand.kind()));
+        if (const Register *Reg = Operand.getIf<Register>())
+          Mix(Reg->opaqueValue());
+      }
+    }
+  }
+  return Hash;
+}
+
+[[nodiscard]] inline Expected<void> initializeMapping(MachineFunction &Function,
+                                                      VirtRegMap &Mapping) {
+  for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) {
+    auto Reg = virtualRegisterAt(Index);
+    if (!Reg)
+      return std::unexpected(Reg.error());
+    if (!Function.registerInfo().isKnownVirtualRegister(*Reg))
+      continue;
+    auto Added = Mapping.add(*Reg);
+    if (!Added)
+      return std::unexpected(Added.error());
+  }
+  return {};
+}
+
+[[nodiscard]] inline MachinePassResult passResult(const AllocationRunResult &Run) {
+  MachinePassResult Result;
+  Result.Changed = Run.Changed;
+  if (Run.Changed) {
+    Result.Changes.add(MachinePassChange::Registers);
+    Result.Changes.add(MachinePassChange::Operands);
+  }
+  if (Run.ChangedInstructions)
+    Result.Changes.add(MachinePassChange::Instructions);
+  if (Run.ChangedFrame)
+    Result.Changes.add(MachinePassChange::Frame);
+  Result.Preserved = PreservedAnalyses::none();
+  return Result;
+}
+
+[[nodiscard]] inline Expected<void>
+requireAllocationProperties(const MachineFunction &Function, const MachinePassContract &Contract) {
+  const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties());
+  if (!Missing.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          Contract.Name + " requires properties: " + Missing.toString());
+  }
+  return {};
+}
+
+[[nodiscard]] inline Expected<void> verifyAllocationTrial(MachineFunction &Function,
+                                                          const TargetDescription &Target,
+                                                          const MachinePassContract &Contract) {
+  auto Transition =
+      Function.properties().applyTransition(Contract.Requires, Contract.Sets, Contract.Clears);
+  if (!Transition)
+    return std::unexpected(Transition.error());
+  return MachineVerifier::verify(Function, Target,
+                                 MachineVerifierOptions{.Mode = MachineVerifierMode::Generic,
+                                                        .Stage = Contract.VerificationStage,
+                                                        .VerifyProperties = true});
+}
+
+[[nodiscard]] inline Expected<MachineFunctionCloneResult>
+cloneForAllocation(const MachineFunction &Function, const TargetDescription &Target) {
+  return cloneMachineFunction(
+      Function, Target,
+      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+}
+
+[[nodiscard]] bool
+intervalsOverlapOnPhysicalRegisters(const LiveInterval &Left, PhysicalRegister LeftReg,
+                                    const LiveInterval &Right, PhysicalRegister RightReg,
+                                    const TargetRegisterInfo &Registers) noexcept;
+
+} // namespace rcc::regalloc_detail
+
+#endif // RCC_LIB_CODEGEN_REGALLOCINTERNAL_H