[CodeGen] Implement machine SSA exit

7 files changed, 95 insertions, 4 deletions

diff --git a/backend/include/rcc/CodeGen/InstructionDescriptor.h b/backend/include/rcc/CodeGen/InstructionDescriptor.h
index 7cf598d..ca2c5cf 100644
--- a/backend/include/rcc/CodeGen/InstructionDescriptor.h
+++ b/backend/include/rcc/CodeGen/InstructionDescriptor.h
@@ -226,6 +226,7 @@ struct OperandDescriptor final {
   bool Optional = false;
   bool VariadicGroup = false;
   bool AllowSubReg = false;
+  bool AllowAnyTargetFlags = false;
   std::optional<NamedOperandID> Name;
   std::optional<TargetOperandTypeID> TargetOperandType;
   std::uint32_t AllowedTargetFlags = 0;
diff --git a/backend/include/rcc/CodeGen/MachineCFGUpdater.h b/backend/include/rcc/CodeGen/MachineCFGUpdater.h
index 4359538..70fb9aa 100644
--- a/backend/include/rcc/CodeGen/MachineCFGUpdater.h
+++ b/backend/include/rcc/CodeGen/MachineCFGUpdater.h
@@ -10,6 +10,7 @@ namespace rcc {
 
 class MachineBasicBlock;
 class MachineFunction;
+class MachineInstr;
 
 class MachineCFGUpdater final {
 public:
@@ -22,11 +23,16 @@ public:
   [[nodiscard]] Expected<void> replaceSuccessor(MachineBasicBlock &From,
                                                 MachineBasicBlock &OldTarget,
                                                 MachineBasicBlock &NewTarget);
+  [[nodiscard]] Expected<void> splitEdge(MachineBasicBlock &From, MachineBasicBlock &To,
+                                         MachineBasicBlock &EdgeBlock);
   [[nodiscard]] Expected<void> updateBranchProbability(MachineBasicBlock &From,
                                                        MachineBasicBlock &To,
                                                        BranchProbability Probability);
   [[nodiscard]] Expected<void> transferSuccessors(MachineBasicBlock &From, MachineBasicBlock &To);
   [[nodiscard]] Expected<void> disconnectBlock(MachineBasicBlock &Block);
+  [[nodiscard]] Expected<MachineBasicBlock *> splitBlock(MachineBasicBlock &Block,
+                                                         MachineInstr &SplitBefore);
+  [[nodiscard]] Expected<void> deleteBlock(MachineBasicBlock &Block);
 
 private:
   [[nodiscard]] Expected<void> verifyOwnership(const MachineBasicBlock &Block) const;
diff --git a/backend/include/rcc/CodeGen/MachineOperand.h b/backend/include/rcc/CodeGen/MachineOperand.h
index b8a6dcc..31ad7e4 100644
--- a/backend/include/rcc/CodeGen/MachineOperand.h
+++ b/backend/include/rcc/CodeGen/MachineOperand.h
@@ -449,6 +449,7 @@ public:
   [[nodiscard]] Expected<void> setRegister(Register Reg);
   [[nodiscard]] Expected<void> setRegisterFlags(RegisterOperandFlags Flags);
   [[nodiscard]] Expected<void> setSubReg(SubRegIndex SubReg);
+  [[nodiscard]] Expected<void> setBasicBlock(MachineBasicBlock &Block);
 
   [[nodiscard]] std::optional<std::size_t> tiedOperandIndex() const noexcept {
     return TiedOperandIndex;
diff --git a/backend/include/rcc/CodeGen/MachineSSAExit.h b/backend/include/rcc/CodeGen/MachineSSAExit.h
new file mode 100644
index 0000000..d98c0b9
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineSSAExit.h
@@ -0,0 +1,49 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINESSAEXIT_H
+#define RCC_CODEGEN_MACHINESSAEXIT_H
+
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/TargetCodeGen.h"
+
+namespace rcc {
+
+class PHIEliminationPass final : public MachineFunctionPass {
+public:
+  PHIEliminationPass() noexcept = default;
+  explicit PHIEliminationPass(const TargetSSAInfo &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,
+                                                              MachineAnalysisManager &Analyses);
+
+  const TargetSSAInfo *Info = nullptr;
+};
+
+class TwoAddressRewritePass final : public MachineFunctionPass {
+public:
+  TwoAddressRewritePass() noexcept = default;
+  explicit TwoAddressRewritePass(const TargetSSAInfo &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,
+                                                              MachineAnalysisManager &Analyses);
+
+  const TargetSSAInfo *Info = nullptr;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINESSAEXIT_H
diff --git a/backend/include/rcc/CodeGen/TargetCodeGen.h b/backend/include/rcc/CodeGen/TargetCodeGen.h
index b1be1f6..f2aac5d 100644
--- a/backend/include/rcc/CodeGen/TargetCodeGen.h
+++ b/backend/include/rcc/CodeGen/TargetCodeGen.h
@@ -7,12 +7,14 @@
 #include "rcc/CodeGen/Register.h"
 #include "rcc/Support/Error.h"
 
+#include <cstddef>
 #include <cstdint>
 #include <optional>
 
 namespace rcc {
 
 class MachineFunction;
+class MachineBasicBlock;
 class MachineInstr;
 class MachineRegisterInfo;
 class TargetDescription;
@@ -89,6 +91,38 @@ public:
   }
 };
 
+class TargetSSAInfo {
+public:
+  virtual ~TargetSSAInfo() = default;
+
+  [[nodiscard]] virtual Expected<bool> isFallthroughEdge(const MachineBasicBlock &From,
+                                                         const MachineBasicBlock &To,
+                                                         const MachineFunction &Function,
+                                                         const TargetDescription &Target) const = 0;
+
+  [[nodiscard]] virtual Expected<bool>
+  rewriteBranchTarget(MachineBasicBlock &Block, MachineBasicBlock &OldTarget,
+                      MachineBasicBlock &NewTarget, MachineFunction &Function,
+                      const TargetDescription &Target) const = 0;
+
+  [[nodiscard]] virtual Expected<void>
+  insertUnconditionalBranch(MachineBasicBlock &Block, MachineBasicBlock &Target,
+                            MachineFunction &Function,
+                            const TargetDescription &TargetDescription) const = 0;
+
+  [[nodiscard]] virtual Expected<void> validateCopy(Register Destination,
+                                                    SubRegIndex DestinationSubReg, Register Source,
+                                                    SubRegIndex SourceSubReg,
+                                                    const MachineFunction &Function,
+                                                    const TargetDescription &Target) const = 0;
+
+  [[nodiscard]] virtual Expected<bool> tryConvertToThreeAddress(MachineInstr &, std::size_t,
+                                                                std::size_t, MachineFunction &,
+                                                                const TargetDescription &) const {
+    return false;
+  }
+};
+
 } // namespace rcc
 
 #endif // RCC_CODEGEN_TARGETCODEGEN_H
diff --git a/backend/include/rcc/CodeGen/TargetDescription.h b/backend/include/rcc/CodeGen/TargetDescription.h
index c2a4133..7e41a58 100644
--- a/backend/include/rcc/CodeGen/TargetDescription.h
+++ b/backend/include/rcc/CodeGen/TargetDescription.h
@@ -72,6 +72,9 @@ public:
                       std::span<const MachineMemOperand *const> MemOperands) const;
   [[nodiscard]] Expected<void> validateInstruction(const MachineInstr &Instruction,
                                                    const MachineRegisterInfo &RegInfo) const;
+  [[nodiscard]] Expected<void> validateTieCompatibility(const MachineOperand &Def,
+                                                        const MachineOperand &Use,
+                                                        const MachineRegisterInfo &RegInfo) const;
   [[nodiscard]] Expected<void> validateCFIInfo(const MachineCFIInfo &Info) const;
   [[nodiscard]] Expected<void> validateFrameInfo(const MachineFrameInfo &Info) const;
   [[nodiscard]] Expected<void> validateRegisterInfo(const MachineRegisterInfo &RegInfo) const;
@@ -95,10 +98,6 @@ private:
                                                        const VirtualRegisterInfo &Info) const;
   [[nodiscard]] std::optional<RegisterClassID>
   effectiveRegisterClass(const MachineOperand &Operand, const MachineRegisterInfo &RegInfo) const;
-  [[nodiscard]] Expected<void> validateTieCompatibility(const MachineOperand &Def,
-                                                        const MachineOperand &Use,
-                                                        const MachineRegisterInfo &RegInfo) const;
-
   InstructionSet Instructions;
   TargetRegisterInfo Registers;
   TargetMIRTextInfo MIRText;
diff --git a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
index b06f20d..4db60f7 100644
--- a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
+++ b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
@@ -10,6 +10,7 @@ namespace rcc::riscv {
 [[nodiscard]] const TargetLegalizerInfo &legalizerInfo() noexcept;
 [[nodiscard]] const TargetRegisterBankInfo &registerBankInfo() noexcept;
 [[nodiscard]] const TargetInstructionSelector &instructionSelector() noexcept;
+[[nodiscard]] const TargetSSAInfo &ssaInfo() noexcept;
 
 } // namespace rcc::riscv