[CodeGen] Implement RISC-V machine outlining

3 files changed, 120 insertions, 0 deletions

diff --git a/backend/include/rcc/CodeGen/MachineOutliner.h b/backend/include/rcc/CodeGen/MachineOutliner.h
new file mode 100644
index 0000000..a12ddaf
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineOutliner.h
@@ -0,0 +1,97 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEOUTLINER_H
+#define RCC_CODEGEN_MACHINEOUTLINER_H
+
+#include "rcc/CodeGen/MachinePassManager.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+#include <memory>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineFunction;
+class MachineInstr;
+class TargetDescription;
+
+enum class MachineOutlinerInstrType : std::uint8_t {
+  Legal,
+  LegalTerminator,
+  Illegal,
+  Invisible,
+};
+
+struct MachineOutlinerFunctionProperties final {
+  bool LinkOnceODR = false;
+  bool HasSection = false;
+  bool HasComdat = false;
+  bool HasSectionPrefix = false;
+};
+
+using MachineOutlinerFunctionPropertyMap =
+    std::unordered_map<std::string, MachineOutlinerFunctionProperties>;
+
+struct MachineOutlinerOptions final {
+  MachineOutlinerFunctionPropertyMap FunctionProperties;
+};
+
+struct MachineOutlinerCandidate final {
+  MachineFunction *Function = nullptr;
+  MachineBasicBlock *Block = nullptr;
+  std::vector<MachineInstr *> Instructions;
+  std::vector<PhysicalRegister> LiveIns;
+  std::vector<PhysicalRegister> DefinedRegisters;
+  std::uint32_t CallConstructionID = 0;
+  std::uint32_t CallOverhead = 0;
+  PhysicalRegister SaveRegister;
+
+  [[nodiscard]] MachineInstr &front() const noexcept;
+  [[nodiscard]] MachineInstr &back() const noexcept;
+  [[nodiscard]] bool containsRegister(PhysicalRegister Reg,
+                                      const TargetDescription &Target) const noexcept;
+  [[nodiscard]] bool isRegisterLiveAfter(PhysicalRegister Reg,
+                                         const TargetDescription &Target) const noexcept;
+  [[nodiscard]] bool isRegisterAvailable(PhysicalRegister Reg,
+                                         const TargetDescription &Target) const noexcept;
+};
+
+class TargetMachineOutlinerInfo {
+public:
+  virtual ~TargetMachineOutlinerInfo();
+
+  [[nodiscard]] virtual bool isFunctionSafeToOutlineFrom(
+      const MachineFunction &Function,
+      const MachineOutlinerFunctionProperties &Properties) const noexcept = 0;
+  [[nodiscard]] virtual MachineOutlinerInstrType
+  getOutliningType(const MachineInstr &Instruction,
+                   const MachineOutlinerFunctionProperties &Properties,
+                   const TargetDescription &Target) const noexcept = 0;
+  [[nodiscard]] virtual Expected<bool> analyzeCandidate(MachineOutlinerCandidate &Candidate,
+                                                        const TargetDescription &Target) const = 0;
+  [[nodiscard]] virtual Expected<std::uint32_t>
+  instructionSize(const MachineInstr &Instruction, const MachineFunction &Function,
+                  const TargetDescription &Target) const = 0;
+  [[nodiscard]] virtual std::uint32_t
+  frameOverhead(const MachineOutlinerCandidate &Candidate) const noexcept = 0;
+  [[nodiscard]] virtual Expected<void>
+  insertOutlinedCall(MachineOutlinerCandidate &Candidate, std::string OutlinedFunctionName,
+                     const TargetDescription &Target) const = 0;
+  [[nodiscard]] virtual Expected<void>
+  buildOutlinedFrame(MachineFunction &Function, MachineBasicBlock &Block,
+                     const MachineOutlinerCandidate &Candidate,
+                     const TargetDescription &Target) const = 0;
+};
+
+[[nodiscard]] std::unique_ptr<CompilationUnitPass>
+createMachineOutlinerPass(std::unique_ptr<TargetMachineOutlinerInfo> TargetInfo,
+                          MachineOutlinerOptions Options = {});
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEOUTLINER_H
diff --git a/backend/include/rcc/MIR/EmbeddedIR.h b/backend/include/rcc/MIR/EmbeddedIR.h
index 022f121..80e512a 100644
--- a/backend/include/rcc/MIR/EmbeddedIR.h
+++ b/backend/include/rcc/MIR/EmbeddedIR.h
@@ -58,6 +58,22 @@ public:
     return IsUnnamed;
   }
 
+  [[nodiscard]] bool hasLinkOnceODRLinkage() const noexcept {
+    return HasLinkOnceODRLinkage;
+  }
+
+  [[nodiscard]] bool hasSection() const noexcept {
+    return HasSection;
+  }
+
+  [[nodiscard]] bool hasComdat() const noexcept {
+    return HasComdat;
+  }
+
+  [[nodiscard]] bool hasSectionPrefix() const noexcept {
+    return HasSectionPrefix;
+  }
+
   [[nodiscard]] std::span<const EmbeddedIRReference> blocks() const noexcept {
     return Blocks;
   }
@@ -87,6 +103,10 @@ private:
   TextRange NameRange;
   bool IsDefinition = false;
   bool IsUnnamed = false;
+  bool HasLinkOnceODRLinkage = false;
+  bool HasSection = false;
+  bool HasComdat = false;
+  bool HasSectionPrefix = false;
   std::uint64_t NextUnnamedSlot = 0;
   std::vector<EmbeddedIRReference> Blocks;
   std::vector<EmbeddedIRReference> Allocas;
diff --git a/backend/include/rcc/Target/RISCV/RISCVPipeline.h b/backend/include/rcc/Target/RISCV/RISCVPipeline.h
index 50a6a68..3e8ea3d 100644
--- a/backend/include/rcc/Target/RISCV/RISCVPipeline.h
+++ b/backend/include/rcc/Target/RISCV/RISCVPipeline.h
@@ -17,6 +17,7 @@ namespace rcc {
 
 class MachineFunction;
 class TargetDescription;
+class TargetMachineOutlinerInfo;
 
 namespace riscv {
 
@@ -37,6 +38,8 @@ createCanonicalPipelinePass(std::string_view Name, const RISCVSubtarget &Subtarg
                             RISCVPipelineOptions Options = {});
 [[nodiscard]] Expected<std::vector<std::string>>
 canonicalPipelinePassNames(const MachineFunction &Function, const RISCVSubtarget &Subtarget);
+[[nodiscard]] Expected<std::unique_ptr<TargetMachineOutlinerInfo>>
+createMachineOutlinerInfo(bool FunctionSections, bool EnableRegisterSave);
 } // namespace riscv
 } // namespace rcc