[RISCV] Implement Zcmp move merging

9 files changed, 392 insertions, 0 deletions

diff --git a/backend/include/rcc/Target/RISCV/RISCVSubtarget.h b/backend/include/rcc/Target/RISCV/RISCVSubtarget.h
index 208f758..52e4b03 100644
--- a/backend/include/rcc/Target/RISCV/RISCVSubtarget.h
+++ b/backend/include/rcc/Target/RISCV/RISCVSubtarget.h
@@ -38,6 +38,7 @@ enum class RISCVExtension : std::uint8_t {
   Zifencei,
   Zacas,
   Zabha,
+  Zcmp,
   Count,
 };
 
diff --git a/backend/lib/Target/RISCV/CMakeLists.txt b/backend/lib/Target/RISCV/CMakeLists.txt
index dccced9..85c69d6 100644
--- a/backend/lib/Target/RISCV/CMakeLists.txt
+++ b/backend/lib/Target/RISCV/CMakeLists.txt
@@ -122,6 +122,7 @@ add_library(
   RISCVMCTargetLowering.cpp
   RISCVMachineCombiner.cpp
   RISCVMachineMemoryFolding.cpp
+  RISCVMoveMerger.cpp
   RISCVOptimizationPipeline.cpp
   RISCVPipeline.cpp
   RISCVPseudoExpansion.cpp
@@ -205,6 +206,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVMCTargetLowering.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVMachineCombiner.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVMachineMemoryFolding.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RISCVMoveMerger.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVOptimizationPipeline.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVPipeline.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVPseudoExpansion.cpp"
diff --git a/backend/lib/Target/RISCV/RISCV.h b/backend/lib/Target/RISCV/RISCV.h
index fea5010..d45d7e6 100644
--- a/backend/lib/Target/RISCV/RISCV.h
+++ b/backend/lib/Target/RISCV/RISCV.h
@@ -16,6 +16,7 @@
 namespace rcc {
 
 class InstructionSelector;
+class MachineFunctionPass;
 
 namespace riscv {
 
@@ -37,6 +38,8 @@ createSchedulingModel(const TargetSchedulingHooks &Hooks);
 [[nodiscard]] const GIMatchTableExecutor &giselCombinerExecutor() noexcept;
 [[nodiscard]] const TargetMemoryFoldingInfo &memoryFoldingInfo() noexcept;
 [[nodiscard]] const TargetPseudoExpansionInfo &pseudoExpansionInfo() noexcept;
+[[nodiscard]] std::unique_ptr<MachineFunctionPass>
+createMoveMergePass(const RISCVSubtarget &Subtarget);
 [[nodiscard]] MachineOptimizationPipelineTargetInfo
 optimizationPipelineInfo(const RISCVSubtarget &Subtarget, bool EmitSchedulerDebugOutput = false,
                          bool EmitFrameDebugOutput = false) noexcept;
diff --git a/backend/lib/Target/RISCV/RISCVInstrInfoC.rccdesc b/backend/lib/Target/RISCV/RISCVInstrInfoC.rccdesc
index fa1b75a..7f5c3c5 100644
--- a/backend/lib/Target/RISCV/RISCVInstrInfoC.rccdesc
+++ b/backend/lib/Target/RISCV/RISCVInstrInfoC.rccdesc
@@ -513,3 +513,33 @@ instructions:
     scheduling_class: STORE
     encoding_category: C
     assembly_format: RS2_OFFSET_SP
+  -
+    id: 1270
+    symbol: CM_MVA01S
+    name: CM_MVA01S
+    assembly_mnemonic: cm.mva01s
+    encoding: 44130
+    operands:
+      - { kinds: [register], role: use, register_class: SR07, register_bank: GPR, name: RS1 }
+      - { kinds: [register], role: use, register_class: SR07, register_bank: GPR, name: RS2 }
+    num_explicit_defs: 0
+    flags: [produces_code]
+    implicit_defs: [{ register: X10 }, { register: X11 }]
+    scheduling_class: COMPRESSED
+    encoding_category: C
+    assembly_format: RD_RS2
+  -
+    id: 1271
+    symbol: CM_MVSA01
+    name: CM_MVSA01
+    assembly_mnemonic: cm.mvsa01
+    encoding: 44066
+    operands:
+      - { kinds: [register], role: def, register_class: SR07, register_bank: GPR, name: RD }
+      - { kinds: [register], role: def, register_class: SR07, register_bank: GPR, name: RS2 }
+    num_explicit_defs: 2
+    flags: [produces_code]
+    implicit_uses: [{ register: X10 }, { register: X11 }]
+    scheduling_class: COMPRESSED
+    encoding_category: C
+    assembly_format: RD_RS2
diff --git a/backend/lib/Target/RISCV/RISCVMCCodeEmitter.cpp b/backend/lib/Target/RISCV/RISCVMCCodeEmitter.cpp
index 15a0c2d..339d817 100644
--- a/backend/lib/Target/RISCV/RISCVMCCodeEmitter.cpp
+++ b/backend/lib/Target/RISCV/RISCVMCCodeEmitter.cpp
@@ -88,6 +88,20 @@ namespace {
   return *Encoding - 8U;
 }
 
+[[nodiscard]] Expected<std::uint32_t> savedRegisterEncoding(const mc::MCInst &Instruction,
+                                                            std::size_t Index,
+                                                            const TargetDescription &Target) {
+  auto Encoding = registerEncoding(Instruction, Index, Target);
+  if (!Encoding)
+    return std::unexpected(Encoding.error());
+  if (*Encoding == 8 || *Encoding == 9)
+    return *Encoding - 8U;
+  if (*Encoding >= 18 && *Encoding <= 23)
+    return *Encoding - 16U;
+  return makeUnexpected(ErrorCode::InstructionEncodingFailed,
+                        "Zcmp move requires an s0-s7 register");
+}
+
 [[nodiscard]] bool fitsSigned(std::int64_t Value, unsigned Bits) noexcept {
   const std::int64_t Minimum = -(std::int64_t{1} << (Bits - 1U));
   const std::int64_t Maximum = (std::int64_t{1} << (Bits - 1U)) - 1;
@@ -649,6 +663,20 @@ namespace {
     return immediateOrFixup(Instruction, Index, Kind, PCRelative, Result);
   };
 
+  if (Opcode == InstructionOpcode::CM_MVA01S || Opcode == InstructionOpcode::CM_MVSA01) {
+    auto Count = requireOperandCount(Instruction, 2);
+    if (!Count)
+      return std::unexpected(Count.error());
+    auto First = savedRegisterEncoding(Instruction, 0, Target);
+    auto Second = savedRegisterEncoding(Instruction, 1, Target);
+    if (!First)
+      return std::unexpected(First.error());
+    if (!Second)
+      return std::unexpected(Second.error());
+    return static_cast<std::uint16_t>((Encoding & ~std::uint16_t{0x039c}) | *First << 7U |
+                                      *Second << 2U);
+  }
+
   if (Opcode == InstructionOpcode::C_ADDI4SPN) {
     auto Count = requireOperandCount(Instruction, 2);
     if (!Count)
diff --git a/backend/lib/Target/RISCV/RISCVMoveMerger.cpp b/backend/lib/Target/RISCV/RISCVMoveMerger.cpp
new file mode 100644
index 0000000..fa1b1ee
--- /dev/null
+++ b/backend/lib/Target/RISCV/RISCVMoveMerger.cpp
@@ -0,0 +1,310 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "RISCV.h"
+#include "RISCVInstrInfo.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachinePassManager.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/Target/RISCV/RISCVInstructions.h"
+#include "rcc/Target/RISCV/RISCVRegisters.h"
+
+#include <memory>
+#include <optional>
+#include <utility>
+
+namespace rcc::riscv {
+namespace {
+
+struct CopyOperands final {
+  MachineOperand *Destination = nullptr;
+  MachineOperand *Source = nullptr;
+  Register DestinationRegister;
+  Register SourceRegister;
+  PhysicalRegister DestinationPhysical;
+  PhysicalRegister SourcePhysical;
+};
+
+[[nodiscard]] std::optional<CopyOperands> copyOperands(MachineInstr &Instruction) {
+  auto Operands = instrInfo().getCopyOperands(Instruction);
+  if (!Operands || Operands->Destination == nullptr || Operands->Source == nullptr)
+    return std::nullopt;
+  auto Destination = Operands->Destination->registerValue();
+  auto Source = Operands->Source->registerValue();
+  if (!Destination || !Source)
+    return std::nullopt;
+  auto DestinationPhysical = Destination->physicalRegister();
+  auto SourcePhysical = Source->physicalRegister();
+  if (!DestinationPhysical || !SourcePhysical)
+    return std::nullopt;
+  return CopyOperands{
+      .Destination = Operands->Destination,
+      .Source = Operands->Source,
+      .DestinationRegister = *Destination,
+      .SourceRegister = *Source,
+      .DestinationPhysical = *DestinationPhysical,
+      .SourcePhysical = *SourcePhysical,
+  };
+}
+
+[[nodiscard]] bool isRegister(PhysicalRegister RegisterValue,
+                              PhysicalRegisterID Expected) noexcept {
+  return RegisterValue.number() == static_cast<std::uint32_t>(Expected);
+}
+
+[[nodiscard]] bool isArgumentRegister(PhysicalRegister RegisterValue) noexcept {
+  return isRegister(RegisterValue, PhysicalRegisterID::X10) ||
+         isRegister(RegisterValue, PhysicalRegisterID::X11);
+}
+
+[[nodiscard]] bool isSavedRegister(PhysicalRegister RegisterValue,
+                                   const TargetDescription &Target) noexcept {
+  const RegisterClassID Class =
+      RegisterClassID::fromValue(static_cast<std::uint32_t>(RegisterClass::SR07));
+  return Target.registers().registerClassContains(Class, RegisterValue);
+}
+
+[[nodiscard]] bool isMoveFromSavedToArgument(const CopyOperands &Copy,
+                                             const TargetDescription &Target) noexcept {
+  return isArgumentRegister(Copy.DestinationPhysical) &&
+         isSavedRegister(Copy.SourcePhysical, Target);
+}
+
+[[nodiscard]] bool isMoveFromArgumentToSaved(const CopyOperands &Copy,
+                                             const TargetDescription &Target) noexcept {
+  return isArgumentRegister(Copy.SourcePhysical) &&
+         isSavedRegister(Copy.DestinationPhysical, Target);
+}
+
+[[nodiscard]] bool operandOverlaps(const MachineOperand &Operand, PhysicalRegister RegisterValue,
+                                   const TargetDescription &Target) noexcept {
+  auto OperandRegister = Operand.registerValue();
+  if (!OperandRegister)
+    return false;
+  auto OperandPhysical = OperandRegister->physicalRegister();
+  return OperandPhysical && Target.registers().regsOverlap(*OperandPhysical, RegisterValue);
+}
+
+[[nodiscard]] bool instructionDefines(const MachineInstr &Instruction,
+                                      PhysicalRegister RegisterValue,
+                                      const TargetDescription &Target) noexcept {
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    if (Operand.isDef() && operandOverlaps(Operand, RegisterValue, Target))
+      return true;
+  }
+  return false;
+}
+
+[[nodiscard]] bool instructionUses(const MachineInstr &Instruction, PhysicalRegister RegisterValue,
+                                   const TargetDescription &Target) noexcept {
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    if (Operand.isUse() && !Operand.isDebugUse() && operandOverlaps(Operand, RegisterValue, Target))
+      return true;
+  }
+  return false;
+}
+
+[[nodiscard]] bool hasHazard(MachineInstr &First, MachineInstr &Second,
+                             const CopyOperands &SecondCopy,
+                             const TargetDescription &Target) noexcept {
+  for (MachineInstr *Instruction = First.next(); Instruction != &Second;
+       Instruction = Instruction->next()) {
+    if (Instruction == nullptr)
+      return true;
+    if (Instruction->isDebugInstr())
+      continue;
+    if (instructionDefines(*Instruction, SecondCopy.DestinationPhysical, Target) ||
+        instructionUses(*Instruction, SecondCopy.DestinationPhysical, Target) ||
+        instructionDefines(*Instruction, SecondCopy.SourcePhysical, Target)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+[[nodiscard]] bool isReadBetween(MachineInstr &First, MachineInstr &Second,
+                                 PhysicalRegister RegisterValue,
+                                 const TargetDescription &Target) noexcept {
+  for (MachineInstr *Instruction = First.next(); Instruction != &Second;
+       Instruction = Instruction->next()) {
+    if (Instruction == nullptr)
+      return true;
+    if (!Instruction->isDebugInstr() && instructionUses(*Instruction, RegisterValue, Target))
+      return true;
+  }
+  return false;
+}
+
+[[nodiscard]] MachineInstr *findMatchingCopy(MachineInstr &First, const CopyOperands &FirstCopy,
+                                             bool MoveFromSavedToArgument,
+                                             const TargetDescription &Target) noexcept {
+  for (MachineInstr *Instruction = First.next(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    if (Instruction->isDebugInstr())
+      continue;
+    auto SecondCopy = copyOperands(*Instruction);
+    if (!SecondCopy)
+      continue;
+    const bool Candidate = MoveFromSavedToArgument ? isMoveFromSavedToArgument(*SecondCopy, Target)
+                                                   : isMoveFromArgumentToSaved(*SecondCopy, Target);
+    if (!Candidate)
+      continue;
+    if (FirstCopy.DestinationPhysical == SecondCopy->DestinationPhysical)
+      return nullptr;
+    if (!MoveFromSavedToArgument && FirstCopy.SourcePhysical == SecondCopy->SourcePhysical)
+      return nullptr;
+    if (hasHazard(First, *Instruction, *SecondCopy, Target))
+      return nullptr;
+    return Instruction;
+  }
+  return nullptr;
+}
+
+[[nodiscard]] Expected<MachineInstr *> mergeCopies(MachineFunction &Function, MachineInstr &First,
+                                                   MachineInstr &Second,
+                                                   bool MoveFromSavedToArgument,
+                                                   const TargetDescription &Target) {
+  auto FirstCopy = copyOperands(First);
+  auto SecondCopy = copyOperands(Second);
+  if (!FirstCopy || !SecondCopy) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "RISC-V move merger lost a recognized copy instruction");
+  }
+
+  MachineOperand *FirstOperand =
+      MoveFromSavedToArgument ? FirstCopy->Source : FirstCopy->Destination;
+  MachineOperand *SecondOperand =
+      MoveFromSavedToArgument ? SecondCopy->Source : SecondCopy->Destination;
+  if (MoveFromSavedToArgument ? !isRegister(FirstCopy->DestinationPhysical, PhysicalRegisterID::X10)
+                              : !isRegister(FirstCopy->SourcePhysical, PhysicalRegisterID::X10)) {
+    std::swap(FirstOperand, SecondOperand);
+  }
+
+  RegisterOperandFlags FirstFlags = FirstOperand->registerFlags();
+  RegisterOperandFlags SecondFlags = SecondOperand->registerFlags();
+  if (MoveFromSavedToArgument && SecondFlags.has(RegisterOperandFlag::Kill) &&
+      isReadBetween(First, Second, *SecondOperand->registerValue()->physicalRegister(), Target)) {
+    SecondFlags.clear(RegisterOperandFlag::Kill);
+  }
+
+  MachineIRBuilder Builder(Function, Target);
+  auto InsertPoint = Builder.setInsertPointBefore(First);
+  if (!InsertPoint)
+    return std::unexpected(InsertPoint.error());
+  const InstructionOpcode Opcode =
+      MoveFromSavedToArgument ? InstructionOpcode::CM_MVA01S : InstructionOpcode::CM_MVSA01;
+  auto Pending = Builder.buildInstr(instructionOpcode(Opcode));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  Expected<void> Added = MoveFromSavedToArgument
+                             ? Pending->addUse(*FirstOperand->registerValue(), FirstFlags)
+                             : Pending->addDef(*FirstOperand->registerValue(), FirstFlags);
+  if (!Added)
+    return std::unexpected(Added.error());
+  Added = MoveFromSavedToArgument ? Pending->addUse(*SecondOperand->registerValue(), SecondFlags)
+                                  : Pending->addDef(*SecondOperand->registerValue(), SecondFlags);
+  if (!Added)
+    return std::unexpected(Added.error());
+  return Pending->build();
+}
+
+[[nodiscard]] Expected<bool> mergeBlock(MachineFunction &Function, MachineBasicBlock &Block,
+                                        const TargetDescription &Target) {
+  bool Changed = false;
+  for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;) {
+    MachineInstr *Next = Instruction->next();
+    if (Instruction->isDebugInstr()) {
+      Instruction = Next;
+      continue;
+    }
+    auto FirstCopy = copyOperands(*Instruction);
+    if (!FirstCopy) {
+      Instruction = Next;
+      continue;
+    }
+    const bool MoveFromSavedToArgument = isMoveFromSavedToArgument(*FirstCopy, Target);
+    const bool MoveFromArgumentToSaved = isMoveFromArgumentToSaved(*FirstCopy, Target);
+    if (!MoveFromSavedToArgument && !MoveFromArgumentToSaved) {
+      Instruction = Next;
+      continue;
+    }
+    MachineInstr *Paired =
+        findMatchingCopy(*Instruction, *FirstCopy, MoveFromSavedToArgument, Target);
+    if (Paired == nullptr) {
+      Instruction = Next;
+      continue;
+    }
+    MachineInstr *AfterPair = Paired->next();
+    auto Merged = mergeCopies(Function, *Instruction, *Paired, MoveFromSavedToArgument, Target);
+    if (!Merged)
+      return std::unexpected(Merged.error());
+    auto RemovedFirst = Block.removeInstruction(*Instruction);
+    if (!RemovedFirst)
+      return std::unexpected(RemovedFirst.error());
+    auto RemovedPaired = Block.removeInstruction(*Paired);
+    if (!RemovedPaired)
+      return std::unexpected(RemovedPaired.error());
+    Changed = true;
+    Instruction = Next == Paired ? AfterPair : Next;
+  }
+  return Changed;
+}
+
+class RISCVMoveMergePass final : public MachineFunctionPass {
+public:
+  explicit RISCVMoveMergePass(const RISCVSubtarget &Subtarget) noexcept : Subtarget(&Subtarget) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override {
+    static const MachinePassContract Contract = [] {
+      MachinePassContract Value{
+          .Name = "riscv-move-merge",
+          .Requires = {},
+          .Sets = {},
+          .Clears = {},
+          .RequiredAnalyses = {},
+          .VerificationStage = std::nullopt,
+      };
+      Value.ThreadSafety = PassThreadSafety::ThreadSafe;
+      Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands,
+                               MachinePassChange::Registers};
+      return Value;
+    }();
+    return Contract;
+  }
+
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineFunctionAnalysisManager &) override {
+    MachinePassResult Result;
+    Result.Preserved = PreservedAnalyses::all();
+    if (Subtarget == nullptr || !Subtarget->features().has(RISCVExtension::Zcmp))
+      return Result;
+    for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+         Block = Block->next()) {
+      auto BlockResult = mergeBlock(Function, *Block, Target);
+      if (!BlockResult)
+        return std::unexpected(BlockResult.error());
+      Result.Changed |= *BlockResult;
+    }
+    if (Result.Changed) {
+      Result.Changes = {MachinePassChange::Instructions, MachinePassChange::Operands,
+                        MachinePassChange::Registers};
+      Result.Preserved = PreservedAnalyses::none();
+    }
+    return Result;
+  }
+
+private:
+  const RISCVSubtarget *Subtarget = nullptr;
+};
+
+} // namespace
+
+std::unique_ptr<MachineFunctionPass> createMoveMergePass(const RISCVSubtarget &Subtarget) {
+  return std::make_unique<RISCVMoveMergePass>(Subtarget);
+}
+
+} // namespace rcc::riscv
diff --git a/backend/lib/Target/RISCV/RISCVPipeline.cpp b/backend/lib/Target/RISCV/RISCVPipeline.cpp
index e094591..5ad7da9 100644
--- a/backend/lib/Target/RISCV/RISCVPipeline.cpp
+++ b/backend/lib/Target/RISCV/RISCVPipeline.cpp
@@ -106,6 +106,9 @@ template <typename PassT, typename... ArgumentT>
                                              Options.UseTargetCopyInstructions});
   if (!Added)
     return std::unexpected(Added.error());
+  Added = Pipeline.addPass(createMoveMergePass(Subtarget));
+  if (!Added)
+    return std::unexpected(Added.error());
   return addPass<CFIInstrInserterPass>(Pipeline, Subtarget.frameLowering());
 }
 
@@ -166,6 +169,8 @@ Expected<void> addCanonicalPipeline(MachineFunctionPassManager &Pipeline,
     if (!Added)
       return std::unexpected(Added.error());
   }
+  if (Subtarget.features().has(RISCVExtension::Zcmp))
+    return Pipeline.addPass(createMoveMergePass(Subtarget));
   return {};
 }
 
diff --git a/backend/lib/Target/RISCV/RISCVRegisterInfo.rccdesc b/backend/lib/Target/RISCV/RISCVRegisterInfo.rccdesc
index 9e5a237..4806ec4 100644
--- a/backend/lib/Target/RISCV/RISCVRegisterInfo.rccdesc
+++ b/backend/lib/Target/RISCV/RISCVRegisterInfo.rccdesc
@@ -378,6 +378,18 @@ register_classes:
     lanes: 1
     registers: [X6, X8, X9, X10, X11, X12, X13, X14, X15, X16, X17, X18, X19, X20, X21, X22, X23, X24, X25, X26, X27, X28, X29, X30, X31]
     allocation_order: [X10, X11, X12, X13, X14, X15, X16, X17, X6, X28, X29, X30, X31, X8, X9, X18, X19, X20, X21, X22, X23, X24, X25, X26, X27]
+  -
+    id: 13
+    symbol: SR07
+    name: SR07
+    bank: GPR
+    superclasses: [GPR]
+    size_bits: 64
+    spill_size_bits: 64
+    spill_alignment_bits: 64
+    lanes: 1
+    registers: [X8, X9, X18, X19, X20, X21, X22, X23]
+    allocation_order: [X8, X9, X18, X19, X20, X21, X22, X23]
 
 register_masks:
   -
diff --git a/backend/lib/Target/RISCV/RISCVSubtarget.cpp b/backend/lib/Target/RISCV/RISCVSubtarget.cpp
index 314aeb7..c97d3cd 100644
--- a/backend/lib/Target/RISCV/RISCVSubtarget.cpp
+++ b/backend/lib/Target/RISCV/RISCVSubtarget.cpp
@@ -41,6 +41,7 @@ constexpr std::array ExtensionNames{
     ExtensionName{"zifencei", RISCVExtension::Zifencei},
     ExtensionName{"zacas", RISCVExtension::Zacas},
     ExtensionName{"zabha", RISCVExtension::Zabha},
+    ExtensionName{"zcmp", RISCVExtension::Zcmp},
 };
 
 constexpr std::array OptionNames{