[CodeGen] Implement RV64GC frame lowering

8 files changed, 177 insertions, 0 deletions

diff --git a/backend/include/rcc/CodeGen/FrameIndexElimination.h b/backend/include/rcc/CodeGen/FrameIndexElimination.h
new file mode 100644
index 0000000..df67479
--- /dev/null
+++ b/backend/include/rcc/CodeGen/FrameIndexElimination.h
@@ -0,0 +1,22 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_FRAMEINDEXELIMINATION_H
+#define RCC_CODEGEN_FRAMEINDEXELIMINATION_H
+
+#include "rcc/Support/Error.h"
+
+namespace rcc {
+
+class MachineFunction;
+class RegisterScavenger;
+class TargetDescription;
+class TargetFrameLowering;
+
+[[nodiscard]] Expected<bool> eliminateFrameIndices(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   const TargetFrameLowering &FrameLowering,
+                                                   RegisterScavenger &Scavenger);
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_FRAMEINDEXELIMINATION_H
diff --git a/backend/include/rcc/CodeGen/MachineInstr.h b/backend/include/rcc/CodeGen/MachineInstr.h
index e7294b4..84d2f0e 100644
--- a/backend/include/rcc/CodeGen/MachineInstr.h
+++ b/backend/include/rcc/CodeGen/MachineInstr.h
@@ -98,6 +98,8 @@ public:
   [[nodiscard]] Expected<void> untieOperand(std::size_t Index);
 
   [[nodiscard]] Expected<void> addMemOperand(const MachineMemOperand &MemOperand);
+  [[nodiscard]] Expected<void> replaceMemOperand(std::size_t Index,
+                                                 const MachineMemOperand &MemOperand);
   [[nodiscard]] Expected<void> eraseMemOperand(std::size_t Index);
   [[nodiscard]] std::span<const MachineMemOperand *const> memOperands() const noexcept {
     return MemOperands;
diff --git a/backend/include/rcc/CodeGen/PrologueEpilogueInsertion.h b/backend/include/rcc/CodeGen/PrologueEpilogueInsertion.h
new file mode 100644
index 0000000..b94715a
--- /dev/null
+++ b/backend/include/rcc/CodeGen/PrologueEpilogueInsertion.h
@@ -0,0 +1,30 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_PROLOGUEEPILOGUEINSERTION_H
+#define RCC_CODEGEN_PROLOGUEEPILOGUEINSERTION_H
+
+#include "rcc/CodeGen/MachinePass.h"
+
+namespace rcc {
+
+class TargetFrameLowering;
+
+class PrologueEpilogueInsertionPass final : public MachineFunctionPass {
+public:
+  explicit PrologueEpilogueInsertionPass(const TargetFrameLowering &Info) noexcept : Info(&Info) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+
+private:
+  [[nodiscard]] Expected<MachinePassResult>
+  runImplementation(MachineFunction &Function, const TargetDescription &Target) const;
+
+  const TargetFrameLowering *Info;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_PROLOGUEEPILOGUEINSERTION_H
diff --git a/backend/include/rcc/CodeGen/RegisterScavenger.h b/backend/include/rcc/CodeGen/RegisterScavenger.h
new file mode 100644
index 0000000..6351b98
--- /dev/null
+++ b/backend/include/rcc/CodeGen/RegisterScavenger.h
@@ -0,0 +1,42 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_REGISTERSCAVENGER_H
+#define RCC_CODEGEN_REGISTERSCAVENGER_H
+
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <span>
+
+namespace rcc {
+
+class MachineFunction;
+class MachineInstr;
+class TargetDescription;
+
+struct ScavengedRegister final {
+  PhysicalRegister Reg;
+  bool RequiresSpill = false;
+};
+
+class RegisterScavenger final {
+public:
+  RegisterScavenger(const MachineFunction &Function, const TargetDescription &Target) noexcept
+      : Function(&Function), Target(&Target) {}
+
+  [[nodiscard]] Expected<ScavengedRegister>
+  scavenge(const MachineInstr &Instruction, std::span<const PhysicalRegister> Candidates) const;
+
+private:
+  [[nodiscard]] Expected<bool> isLiveBefore(const MachineInstr &Instruction,
+                                            PhysicalRegister Reg) const;
+  [[nodiscard]] bool instructionUses(const MachineInstr &Instruction,
+                                     PhysicalRegister Reg) const noexcept;
+
+  const MachineFunction *Function;
+  const TargetDescription *Target;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_REGISTERSCAVENGER_H
diff --git a/backend/include/rcc/CodeGen/TargetFrameLowering.h b/backend/include/rcc/CodeGen/TargetFrameLowering.h
new file mode 100644
index 0000000..1712616
--- /dev/null
+++ b/backend/include/rcc/CodeGen/TargetFrameLowering.h
@@ -0,0 +1,73 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_TARGETFRAMELOWERING_H
+#define RCC_CODEGEN_TARGETFRAMELOWERING_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineFunction;
+class MachineInstr;
+class RegisterScavenger;
+class TargetDescription;
+
+struct FrameIndexReference final {
+  PhysicalRegister BaseRegister;
+  std::int64_t Offset = 0;
+};
+
+class TargetFrameLowering {
+public:
+  virtual ~TargetFrameLowering() = default;
+
+  [[nodiscard]] virtual Expected<void> prepareFrame(MachineFunction &Function,
+                                                    const TargetDescription &Target) const = 0;
+  [[nodiscard]] virtual Expected<void>
+  insertCalleeSavedSpillsAndRestores(MachineFunction &Function,
+                                     const TargetDescription &Target) const = 0;
+  [[nodiscard]] virtual Expected<void>
+  processFunctionBeforeFrameFinalized(MachineFunction &, const TargetDescription &) const {
+    return {};
+  }
+  [[nodiscard]] virtual Expected<void> finalizeFrame(MachineFunction &Function,
+                                                     const TargetDescription &Target) const = 0;
+
+  [[nodiscard]] virtual bool isCallFramePseudo(const MachineInstr &Instruction) const noexcept = 0;
+  [[nodiscard]] virtual Expected<void>
+  eliminateCallFramePseudo(MachineInstr &Instruction, MachineFunction &Function,
+                           const TargetDescription &Target, RegisterScavenger &Scavenger) const = 0;
+
+  [[nodiscard]] virtual Expected<void> emitPrologue(MachineFunction &Function,
+                                                    const TargetDescription &Target,
+                                                    RegisterScavenger &Scavenger) const = 0;
+  [[nodiscard]] virtual bool
+  isEpilogueTerminator(const MachineInstr &Instruction,
+                       const TargetDescription &Target) const noexcept = 0;
+  [[nodiscard]] virtual Expected<void>
+  emitEpilogue(MachineBasicBlock &Block, MachineInstr &Terminator, MachineFunction &Function,
+               const TargetDescription &Target, RegisterScavenger &Scavenger) const = 0;
+  [[nodiscard]] virtual Expected<void>
+  processFunctionBeforeFrameIndexElimination(MachineFunction &, const TargetDescription &) const {
+    return {};
+  }
+
+  [[nodiscard]] virtual Expected<FrameIndexReference>
+  getFrameIndexReference(const MachineFunction &Function, const MachineInstr &Instruction,
+                         FrameIndex Index, std::int64_t OperandOffset) const = 0;
+  [[nodiscard]] virtual Expected<void> eliminateFrameIndex(MachineInstr &Instruction,
+                                                           std::size_t OperandIndex,
+                                                           MachineFunction &Function,
+                                                           const TargetDescription &Target,
+                                                           RegisterScavenger &Scavenger) const = 0;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_TARGETFRAMELOWERING_H
diff --git a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
index 6e25465..4448933 100644
--- a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
+++ b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
@@ -51,6 +51,11 @@ public:
                                                 RegisterClassID) const noexcept {
     return 1;
   }
+
+  [[nodiscard]] virtual bool isReservedForFunction(const MachineFunction &, PhysicalRegister,
+                                                   const TargetDescription &) const noexcept {
+    return false;
+  }
 };
 
 } // namespace rcc
diff --git a/backend/include/rcc/Support/Error.h b/backend/include/rcc/Support/Error.h
index 81568de..44ff967 100644
--- a/backend/include/rcc/Support/Error.h
+++ b/backend/include/rcc/Support/Error.h
@@ -19,6 +19,7 @@ enum class ErrorCode : std::uint8_t {
   RegisterAllocationFailed,
   IoError,
   InternalError,
+  FrameLayoutFailed,
 };
 
 [[nodiscard]] std::string_view getErrorCodeName(ErrorCode Code) noexcept;
diff --git a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
index 403bb2d..0cec77d 100644
--- a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
+++ b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
@@ -4,6 +4,7 @@
 #define RCC_TARGET_RISCV_RISCVCODEGEN_H
 
 #include "rcc/CodeGen/TargetCodeGen.h"
+#include "rcc/CodeGen/TargetFrameLowering.h"
 #include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
 
 namespace rcc::riscv {
@@ -13,6 +14,7 @@ namespace rcc::riscv {
 [[nodiscard]] const TargetInstructionSelector &instructionSelector() noexcept;
 [[nodiscard]] const TargetSSAInfo &ssaInfo() noexcept;
 [[nodiscard]] const TargetRegisterAllocationInfo &registerAllocationInfo() noexcept;
+[[nodiscard]] const TargetFrameLowering &frameLowering() noexcept;
 
 } // namespace rcc::riscv