[CodeGen] Generate RISC-V macro fusion rules

11 files changed, 154 insertions, 8 deletions

diff --git a/backend/include/rcc/CodeGen/MIRParser/MIParser.h b/backend/include/rcc/CodeGen/MIRParser/MIParser.h
index cd40882..4df2ea4 100644
--- a/backend/include/rcc/CodeGen/MIRParser/MIParser.h
+++ b/backend/include/rcc/CodeGen/MIRParser/MIParser.h
@@ -3,9 +3,9 @@
 #ifndef RCC_CODEGEN_MIRPARSER_MIPARSER_H
 #define RCC_CODEGEN_MIRPARSER_MIPARSER_H
 
+#include "rcc/CodeGen/GlobalObject.h"
 #include "rcc/CodeGen/MachineIRTypes.h"
 #include "rcc/CodeGen/MachineMetadata.h"
-#include "rcc/CodeGen/GlobalObject.h"
 #include "rcc/CodeGen/Register.h"
 #include "rcc/Support/Error.h"
 #include "rcc/Support/TextDiagnostic.h"
diff --git a/backend/include/rcc/CodeGen/MachineOperand.h b/backend/include/rcc/CodeGen/MachineOperand.h
index d82e41a..fecb4e0 100644
--- a/backend/include/rcc/CodeGen/MachineOperand.h
+++ b/backend/include/rcc/CodeGen/MachineOperand.h
@@ -330,9 +330,10 @@ public:
                                                    std::uint32_t TargetFlags = 0);
   [[nodiscard]] static MachineOperand jumpTable(JumpTableIndex Index,
                                                 std::uint32_t TargetFlags = 0);
-  [[nodiscard]] static Expected<MachineOperand>
-  globalSymbol(std::string Name, std::int64_t Offset = 0, std::uint32_t TargetFlags = 0,
-               GlobalValueProperties Properties = {});
+  [[nodiscard]] static Expected<MachineOperand> globalSymbol(std::string Name,
+                                                             std::int64_t Offset = 0,
+                                                             std::uint32_t TargetFlags = 0,
+                                                             GlobalValueProperties Properties = {});
   [[nodiscard]] static Expected<MachineOperand>
   externalSymbol(std::string Name, std::int64_t Offset = 0, std::uint32_t TargetFlags = 0);
   [[nodiscard]] static Expected<MachineOperand> blockAddress(std::string FunctionName,
diff --git a/backend/include/rcc/CodeGen/MachineOptimizationPipeline.h b/backend/include/rcc/CodeGen/MachineOptimizationPipeline.h
index 911cb86..d4abf74 100644
--- a/backend/include/rcc/CodeGen/MachineOptimizationPipeline.h
+++ b/backend/include/rcc/CodeGen/MachineOptimizationPipeline.h
@@ -4,6 +4,7 @@
 #define RCC_CODEGEN_MACHINEOPTIMIZATIONPIPELINE_H
 
 #include "rcc/CodeGen/MachinePassManager.h"
+#include "rcc/CodeGen/MachineScheduler.h"
 
 namespace rcc {
 
@@ -21,6 +22,7 @@ struct MachineOptimizationPipelineTargetInfo final {
   const TargetFrameLowering &FrameLowering;
   const TargetPseudoExpansionInfo &PseudoExpansion;
   const TargetSchedulingModel &SchedulingModel;
+  MachineSchedulerOptions SchedulerOptions;
 };
 
 struct MachineOptimizationPipelineOptions final {
diff --git a/backend/include/rcc/CodeGen/MachineScheduler.h b/backend/include/rcc/CodeGen/MachineScheduler.h
index bfe9265..614ef86 100644
--- a/backend/include/rcc/CodeGen/MachineScheduler.h
+++ b/backend/include/rcc/CodeGen/MachineScheduler.h
@@ -14,6 +14,7 @@ class TargetSchedulingModel;
 struct MachineSchedulerOptions final {
   std::size_t MaximumRegionSize = 512;
   bool EnableBidirectionalScheduling = true;
+  bool EmitDebugOutput = false;
 };
 
 class MachineSchedulerPass final : public MachineFunctionPass {
diff --git a/backend/include/rcc/CodeGen/MacroFusion.h b/backend/include/rcc/CodeGen/MacroFusion.h
new file mode 100644
index 0000000..c3d811d
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MacroFusion.h
@@ -0,0 +1,77 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACROFUSION_H
+#define RCC_CODEGEN_MACROFUSION_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+#include <limits>
+#include <span>
+#include <string_view>
+
+namespace rcc {
+
+class MachineInstr;
+class ScheduleDAG;
+class TargetDescription;
+
+enum class MacroFusionInstruction : std::uint8_t {
+  First,
+  Second,
+};
+
+struct MacroFusionOpcodePair final {
+  Opcode First;
+  Opcode Second;
+};
+
+struct MacroFusionImmediatePredicate final {
+  MacroFusionInstruction Instruction = MacroFusionInstruction::First;
+  std::uint32_t OperandIndex = 0;
+  std::int64_t Minimum = 0;
+  std::int64_t Maximum = 0;
+};
+
+struct MacroFusionRegisterInequality final {
+  MacroFusionInstruction Instruction = MacroFusionInstruction::First;
+  std::uint32_t LeftOperand = 0;
+  std::uint32_t RightOperand = 0;
+};
+
+struct MacroFusionImmediateRelation final {
+  std::uint32_t FirstOperand = 0;
+  std::uint32_t SecondOperand = 0;
+};
+
+struct MacroFusionRule final {
+  static constexpr std::uint32_t NoOperand = std::numeric_limits<std::uint32_t>::max();
+
+  std::string_view Name;
+  std::string_view Feature;
+  std::span<const Opcode> FirstOpcodes;
+  std::span<const Opcode> SecondOpcodes;
+  std::span<const MacroFusionOpcodePair> OpcodePairs;
+  std::span<const MacroFusionImmediatePredicate> ImmediatePredicates;
+  std::span<const MacroFusionRegisterInequality> RegisterInequalities;
+  std::span<const MacroFusionImmediateRelation> ImmediateRelations;
+  std::uint32_t FirstDefinitionOperand = 0;
+  std::uint32_t SecondUseOperand = 1;
+  std::uint32_t SecondDefinitionOperand = 0;
+  std::uint32_t CommutableSecondUseOperand = NoOperand;
+  bool RequireSingleNonDebugUse = false;
+  bool RequireSecondDestinationTie = false;
+};
+
+[[nodiscard]] bool matchesMacroFusion(const MacroFusionRule &Rule, const MachineInstr *First,
+                                      const MachineInstr &Second) noexcept;
+
+[[nodiscard]] Expected<void> applyMacroFusion(ScheduleDAG &DAG,
+                                              std::span<const MacroFusionRule> Rules,
+                                              const TargetDescription &Target,
+                                              bool EmitDebugOutput);
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACROFUSION_H
diff --git a/backend/include/rcc/CodeGen/ScheduleDAG.h b/backend/include/rcc/CodeGen/ScheduleDAG.h
index 644d98a..7634202 100644
--- a/backend/include/rcc/CodeGen/ScheduleDAG.h
+++ b/backend/include/rcc/CodeGen/ScheduleDAG.h
@@ -9,6 +9,7 @@
 
 #include <cstddef>
 #include <cstdint>
+#include <optional>
 #include <span>
 #include <vector>
 
@@ -32,6 +33,7 @@ enum class ScheduleDependencyKind : std::uint8_t {
   Memory,
   Barrier,
   Artificial,
+  Cluster,
   RegisterUnit,
   RegisterMask,
 };
@@ -57,6 +59,8 @@ struct ScheduleUnit final {
   std::uint64_t Depth = 0;
   std::uint64_t Height = 0;
   MachineInstrStableID StableID;
+  std::optional<std::size_t> ClusterPredecessor;
+  std::optional<std::size_t> ClusterSuccessor;
 };
 
 class ScheduleDAG final {
@@ -64,7 +68,7 @@ public:
   [[nodiscard]] static Expected<ScheduleDAG>
   build(MachineBasicBlock &Block, std::span<MachineInstr *const> Instructions,
         const MachineFunction &Function, const TargetDescription &Target,
-        const TargetSchedulingModel &Model, ScheduleDAGMode Mode);
+        const TargetSchedulingModel &Model, ScheduleDAGMode Mode, bool EmitDebugOutput = false);
 
   [[nodiscard]] MachineBasicBlock &block() const noexcept {
     return *Block;
@@ -84,6 +88,7 @@ public:
 
   [[nodiscard]] Expected<void> addArtificialDependency(std::size_t Source, std::size_t Destination,
                                                        std::uint32_t Latency);
+  [[nodiscard]] Expected<bool> fuseInstructionPair(std::size_t First, std::size_t Second);
 
 private:
   explicit ScheduleDAG(MachineBasicBlock &Block) : Block(&Block) {}
@@ -97,9 +102,11 @@ private:
                                                          ScheduleDAGMode Mode);
   [[nodiscard]] Expected<void> buildMemoryDependencies(const TargetDescription &Target);
   [[nodiscard]] Expected<void> buildOrderDependencies(const TargetDescription &Target);
+  [[nodiscard]] bool hasPath(std::size_t Source, std::size_t Destination) const;
+  [[nodiscard]] bool hasDirectDependency(std::size_t Source, std::size_t Destination) const;
   void addDependency(std::size_t Source, std::size_t Destination, ScheduleDependencyKind Kind,
                      std::uint32_t Latency);
-  void computeCriticalPaths();
+  [[nodiscard]] Expected<void> computeCriticalPaths();
 
   MachineBasicBlock *Block;
   std::vector<ScheduleUnit> Units;
diff --git a/backend/include/rcc/CodeGen/TargetSchedulingModel.h b/backend/include/rcc/CodeGen/TargetSchedulingModel.h
index 4d7b3ce..5eb7116 100644
--- a/backend/include/rcc/CodeGen/TargetSchedulingModel.h
+++ b/backend/include/rcc/CodeGen/TargetSchedulingModel.h
@@ -107,7 +107,8 @@ public:
   [[nodiscard]] virtual Expected<void> mutateScheduleDAG(ScheduleDAG &DAG,
                                                          const MachineFunction &Function,
                                                          const TargetDescription &Target,
-                                                         ScheduleDAGMode Mode) const;
+                                                         ScheduleDAGMode Mode,
+                                                         bool EmitDebugOutput) const;
   [[nodiscard]] virtual std::int64_t
   candidatePreference(const ScheduleUnit &Unit, ScheduleDirection Direction,
                       const MachineBasicBlock &Block, std::uint64_t BlockFrequency) const noexcept;
diff --git a/backend/include/rcc/MIR/EmbeddedIR.h b/backend/include/rcc/MIR/EmbeddedIR.h
index 1c17938..022f121 100644
--- a/backend/include/rcc/MIR/EmbeddedIR.h
+++ b/backend/include/rcc/MIR/EmbeddedIR.h
@@ -170,7 +170,7 @@ private:
   std::optional<TextRange> DataLayoutRange;
   std::vector<EmbeddedIRFunction> Functions;
   std::vector<EmbeddedIRReference> GlobalObjects;
-  std::unordered_map<std::string, GlobalValueProperties, StringHash, std::equal_to<> >
+  std::unordered_map<std::string, GlobalValueProperties, StringHash, std::equal_to<>>
       GlobalProperties;
   std::vector<EmbeddedIRMetadataDefinition> MetadataDefinitions;
   std::vector<EmbeddedIRTypeDefinition> TypeDefinitions;
diff --git a/backend/include/rcc/TableGen/Record.h b/backend/include/rcc/TableGen/Record.h
index 9f3477f..9ebfb7f 100644
--- a/backend/include/rcc/TableGen/Record.h
+++ b/backend/include/rcc/TableGen/Record.h
@@ -143,6 +143,52 @@ struct SourceSchedulingClass final {
   TextRange Range;
 };
 
+struct SourceMacroFusionOpcodePair final {
+  std::string FirstOpcodeSymbol;
+  std::string SecondOpcodeSymbol;
+  TextRange Range;
+};
+
+struct SourceMacroFusionImmediatePredicate final {
+  std::string Instruction;
+  std::uint32_t OperandIndex = 0;
+  std::int64_t Minimum = 0;
+  std::int64_t Maximum = 0;
+  TextRange Range;
+};
+
+struct SourceMacroFusionRegisterInequality final {
+  std::string Instruction;
+  std::uint32_t LeftOperand = 0;
+  std::uint32_t RightOperand = 0;
+  TextRange Range;
+};
+
+struct SourceMacroFusionImmediateRelation final {
+  std::string Kind;
+  std::uint32_t FirstOperand = 0;
+  std::uint32_t SecondOperand = 0;
+  TextRange Range;
+};
+
+struct SourceMacroFusionRule final {
+  std::string Symbol;
+  std::string Feature;
+  std::vector<std::string> FirstOpcodeSymbols;
+  std::vector<std::string> SecondOpcodeSymbols;
+  std::vector<SourceMacroFusionOpcodePair> OpcodePairs;
+  std::vector<SourceMacroFusionImmediatePredicate> ImmediatePredicates;
+  std::vector<SourceMacroFusionRegisterInequality> RegisterInequalities;
+  std::vector<SourceMacroFusionImmediateRelation> ImmediateRelations;
+  std::uint32_t FirstDefinitionOperand = 0;
+  std::uint32_t SecondUseOperand = 0;
+  std::uint32_t SecondDefinitionOperand = 0;
+  std::optional<std::uint32_t> CommutableSecondUseOperand;
+  bool RequireSingleNonDebugUse = false;
+  bool RequireSecondDestinationTie = false;
+  TextRange Range;
+};
+
 struct SourceEncodingCategory final {
   std::uint32_t ID = 0;
   std::string Symbol;
@@ -394,6 +440,7 @@ struct DescriptionAST final {
   std::vector<SourceInstruction> Instructions;
   std::vector<SourceSelectionRule> SelectionRules;
   std::vector<SourceCombinerRule> CombinerRules;
+  std::vector<SourceMacroFusionRule> MacroFusionRules;
 };
 
 [[nodiscard]] std::string lowerASCII(std::string_view Value);
diff --git a/backend/include/rcc/Target/RISCV/RISCVPipeline.h b/backend/include/rcc/Target/RISCV/RISCVPipeline.h
index 262f7c1..21a4461 100644
--- a/backend/include/rcc/Target/RISCV/RISCVPipeline.h
+++ b/backend/include/rcc/Target/RISCV/RISCVPipeline.h
@@ -24,6 +24,7 @@ struct RISCVPipelineOptions final {
   OptimizationLevel Optimization = OptimizationLevel::O2;
   bool UseTargetCopyInstructions = false;
   GlobalISelAbortMode GlobalISelAbort = GlobalISelAbortMode::Enable;
+  bool DebugMachineScheduler = false;
 };
 
 [[nodiscard]] Expected<void> addCanonicalPipeline(MachineFunctionPassManager &Pipeline,
diff --git a/backend/include/rcc/Target/RISCV/RISCVSubtarget.h b/backend/include/rcc/Target/RISCV/RISCVSubtarget.h
index a77a045..c8a4298 100644
--- a/backend/include/rcc/Target/RISCV/RISCVSubtarget.h
+++ b/backend/include/rcc/Target/RISCV/RISCVSubtarget.h
@@ -10,12 +10,15 @@
 #include <memory>
 #include <span>
 #include <string>
+#include <string_view>
 
 namespace rcc {
 
 class InstructionSelector;
 class LegalizerInfo;
 class TargetCallLowering;
+class TargetSchedulingHooks;
+class TargetSchedulingModel;
 
 namespace riscv {
 
@@ -45,6 +48,7 @@ enum class RISCVSubtargetOption : std::uint8_t {
   FusionAddImmediateLoad,
   FusionAUIPCAddImmediate,
   FusionAUIPCLoad,
+  FusionBitfieldExtract,
   FusionLoadDoubleAdd,
   FusionLogicImmediateRegister,
   FusionLogicRegisterImmediate,
@@ -53,6 +57,7 @@ enum class RISCVSubtargetOption : std::uint8_t {
   FusionLUILoad,
   FusionMultiplyAdd,
   FusionShiftBitExtract,
+  FusionShiftedAddLoad,
   FusionShiftedZeroExtendWord,
   FusionZeroExtendHalf,
   FusionZeroExtendWord,
@@ -74,6 +79,7 @@ public:
 
   [[nodiscard]] bool has(RISCVExtension Extension) const noexcept;
   [[nodiscard]] bool has(RISCVSubtargetOption Option) const noexcept;
+  [[nodiscard]] bool hasFeature(std::string_view Feature) const noexcept;
 
   friend bool operator==(const RISCVSubtargetFeatures &Left,
                          const RISCVSubtargetFeatures &Right) = default;
@@ -114,6 +120,7 @@ public:
   [[nodiscard]] InstructionSelector *getInstructionSelector() const;
   [[nodiscard]] const LegalizerInfo *getLegalizerInfo() const;
   [[nodiscard]] const RISCVRegisterBankInfo *getRegBankInfo() const;
+  [[nodiscard]] const TargetSchedulingModel &schedulingModel() const noexcept;
 
 private:
   RISCVSubtargetFeatures Features;
@@ -123,6 +130,8 @@ private:
   mutable std::unique_ptr<InstructionSelector> InstSelector;
   mutable std::unique_ptr<LegalizerInfo> Legalizer;
   mutable std::unique_ptr<RISCVRegisterBankInfo> RegBankInfo;
+  std::unique_ptr<TargetSchedulingHooks> SchedulingHooks;
+  std::unique_ptr<TargetSchedulingModel> SchedulingModel;
 };
 
 } // namespace riscv