[RISCV] Macro Fusion for RISC-V

[kamleshbhalui]

Summary

Inspired from these two docs
https://arxiv.org/pdf/1607.02318.pdf
https://riscv.org/wp-content/uploads/2016/07/Tue1130celio-fusion-finalV2.pdf

this patch contains known pairs that can be fused from above two docs.

[lenary]

Wow, this is really cool! I'm amazed it took so little (target-specific) code.

It would be good to understand the trade-offs of doing this rescheduling when the core doesn't necessarily support fusion. With the current instructions, I don't see many scheduling problems coming from blindly fusing all the time, but maybe this should be a subtarget feature that can be switched on and off in case it creates scheduling issues.

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

125

Is this the default kind of machine scheduler? Does it necessarily make sense to schedule by liveness when RISC-V has so many registers?

[evandro]

As @lenary said, this must be enabled only for those sub targets that actually fuse these instrs. Also, when using the macro fusion pass, you should also enable the post RA pass. Otherwise, it's less effective.

[evandro]

llvm/lib/Target/RISCV/RISCVMacroFusion.cpp

22

Please, expand this comment.

27

Please, expand the acronym.

46

Please, add a comment.

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

125

Yes and yes. By scheduling by liveness, the result is usually more friendly to both in and out of order µarchitectures.

[kamleshbhalui]

@lenary and @evandro Thanks for reviewing.
Addressed reviewer's concerns and added few fusable pairs.

[evandro]

Please, prefix the title with [RISCV].

llvm/lib/Target/RISCV/RISCV.td

71

Different implementations may implement just some of the possible pairs. So this feature should perhaps be broken down into each category.

72

"Fuse select instruction pairs"

119

Does Rocket fuse all these pairs?

llvm/lib/Target/RISCV/RISCVMacroFusion.cpp

102

This is not correct as it increases compile time even when SecondMI is not a candidate for a fuseable pair. MacroFusion::scheduleAdjacentImpl() will call this function to query if SecondMI before traversing its predecessors. So you should go into the functions below and they should handle the case for FirstMI being nullptr for this test.

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

131

Please, insert a blank line here.

[jrtc27]

Indexed load and store fusion should not be exclusive to LD and SD. It applies to any (F)Lx/(F)Sx. The literature just talks about LD/ST (note that this is not SD) in the sense of an arbitrary load/store instruction. Similarly for the various other fusion pairs involving memory accesses.

llvm/lib/Target/RISCV/RISCV.td

71

This is a multi-word feature, so should be hyphenated as macro-fusion in my opinion (although I would prefer macro-op-fusion over that...).

llvm/lib/Target/RISCV/RISCVMacroFusion.cpp

37

This is clearly not a jump.

61

This is not the right name. This is for load immediate idioms.

79

We don't want to be fusing arbitrary loads/stores together, only those we know to be to adjacent memory locations with the same width (and in that order). Moreover it can only be done in decode if it's trivial to determine these conditions hold, ie they use the same opcode and base register, differing only in the immediate by the memory access width.

[• ahmd.otm]

Is Chipyard already supporting these micro-op-fusion? and how can i use this code to make a riscv file (test.riscv) from a c file?

[SForeKeeper]

Hi, I'd like to know if you are still interested in this work? There is a microarchitecture called XiangShan that actually supports instruction fusion.

We are working on support of this processor in LLVM, including macro fusion, and we hope to make our patches upstream. The fusion pairs are listed here (translations needed) and I suppose it's a good opportunity to introduce instruction fusion in the RISCV ecosystem of LLVM.

llvm/lib/Target/RISCV/CMakeLists.txt

add_llvm_target(RISCVCodeGen
   RISCVISelDAGToDAG.cpp
   RISCVISelLowering.cpp
   RISCVLegalizerInfo.cpp
   RISCVMCInstLower.cpp
   RISCVMergeBaseOffset.cpp
   RISCVRegisterBankInfo.cpp
   RISCVRegisterInfo.cpp
   RISCVSubtarget.cpp
+  RISCVMacroFusion.cpp
   RISCVTargetMachine.cpp
   RISCVTargetObjectFile.cpp
   RISCVTargetTransformInfo.cpp
   )
 
 add_subdirectory(AsmParser)
 add_subdirectory(Disassembler)
 add_subdirectory(MCTargetDesc)
 add_subdirectory(TargetInfo)
 add_subdirectory(Utils)

llvm/lib/Target/RISCV/RISCV.td

def IsRV64 : Predicate<"Subtarget->is64Bit()">,
                        "RV64I Base Instruction Set">;
 def IsRV32 : Predicate<"!Subtarget->is64Bit()">,
                        AssemblerPredicate<"!Feature64Bit",
                        "RV32I Base Instruction Set">;
 
 def RV64           : HwMode<"+64bit">;
 def RV32           : HwMode<"-64bit">;
 
+def FeatureMacroFusion
+    : SubtargetFeature<"macrofusion", "HasMacroFusion", "true",
+                "Various pair of instructions can be fused">;
+
 def FeatureRV32E
     : SubtargetFeature<"e", "IsRV32E", "true",
                        "Implements RV32E (provides 16 rather than 32 GPRs)">;
 def IsRV32E : Predicate<"Subtarget->isRV32E()">,
                         AssemblerPredicate<"FeatureRV32E">;
 
 def FeatureRelax
     : SubtargetFeature<"relax", "EnableLinkerRelax", "true",

 def : ProcessorModel<"generic-rv32", NoSchedModel, [FeatureRVCHints]>;
 
 def : ProcessorModel<"generic-rv64", NoSchedModel, [Feature64Bit,
                      FeatureRVCHints]>;
 
 def : ProcessorModel<"rocket-rv32", Rocket32Model, [FeatureRVCHints]>;
 
 def : ProcessorModel<"rocket-rv64", Rocket64Model, [Feature64Bit,
-                     FeatureRVCHints]>;
+                     FeatureRVCHints, FeatureMacroFusion]>;
 
 
 //===----------------------------------------------------------------------===//
 // Define the RISC-V target.
 //===----------------------------------------------------------------------===//
 
 def RISCVInstrInfo : InstrInfo {
   let guessInstructionProperties = 0;

llvm/lib/Target/RISCV/RISCVMacroFusion.h

+//===- RISCVMacroFusion.h - RISCV Macro Fusion ------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file This file contains the RISCV definition of the DAG scheduling mutation
+/// to pair instructions back to back.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_RISCV_RISCVMACROFUSION_H
+#define LLVM_LIB_TARGET_RISCV_RISCVMACROFUSION_H
+
+#include "llvm/CodeGen/MachineScheduler.h"
+
+namespace llvm {
+
+/// Note that you have to add:
+///   DAG.addMutation(createRISCVMacroFusionDAGMutation());
+/// to RISCVPassConfig::createMachineScheduler() to have an effect.
+std::unique_ptr<ScheduleDAGMutation> createRISCVMacroFusionDAGMutation();
+
+} // llvm
+
+#endif

llvm/lib/Target/RISCV/RISCVMacroFusion.cpp

+//===- RISCVMacroFusion.cpp - RISCV Macro Fusion ----------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file This file contains the RISCV implementation of the DAG scheduling
+///  mutation to pair instructions back to back.
+//
+//===----------------------------------------------------------------------===//
+
+#include "RISCVMacroFusion.h"
+#include "RISCVSubtarget.h"
+#include "llvm/CodeGen/MacroFusion.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
+
+namespace llvm {
+
+// Fuse Indexed Load
+static bool isIndexedLoad(const MachineInstr *FirstMI,
+                              const MachineInstr &SecondMI) {
+  return FirstMI->getOpcode() == RISCV::ADD &&
+          SecondMI.getOpcode() == RISCV::LD;
+}
+
+// Fuse Global Load and Far Jumps
+static bool isGLoadOrFJump(const MachineInstr *FirstMI,
+                              const MachineInstr &SecondMI) {
+  if (FirstMI->getOpcode() == RISCV::AUIPC) {
+      switch (SecondMI.getOpcode()) {
+        // Global Load
+        case RISCV::LW:
+          return true;
+        // Far Jumps
+        case RISCV::LD:
+          return true;
+      }
+  }
+  return false;
+}
+
+// Fuse Load Effective Address or Clear Upper Words Idioms
+static bool isLEAPair(const MachineInstr *FirstMI,
+                           const MachineInstr &SecondMI) {
+  if (FirstMI->getOpcode() == RISCV::SLLI) {
+      switch (SecondMI.getOpcode()) {
+        // Load Effective Address
+        case  RISCV::ADD:
+          return true;
+        // Clear Upper Word
+        case RISCV::SRLI:
+          return true;
+      }
+  }
+  return false;
+}
+
+// Fuse Load Immediate Idioms
+static bool isClearUpWord(const MachineInstr *FirstMI,
+                              const MachineInstr &SecondMI) {
+  if (FirstMI->getOpcode() == RISCV::LUI) {
+      switch (SecondMI.getOpcode()) {
+        // LUI based immediate Add
+        case  RISCV::ADDI:
+          return true;
+        // LUI based Loads
+        case RISCV::LD:
+          return true;
+      }
+  }
+  return false;
+}
+
+// Load Pair Idioms
+static bool isLoadPair(const MachineInstr *FirstMI,
+                                  const MachineInstr &SecondMI) {
+  return FirstMI->getOpcode() == RISCV::LD &&
+          SecondMI.getOpcode() == RISCV::LD;
+}
+
+// Store Pair Idioms
+static bool isStorePair(const MachineInstr *FirstMI,
+                            const MachineInstr &SecondMI) {
+  return FirstMI->getOpcode() == RISCV::SD &&
+            SecondMI.getOpcode() == RISCV::SD;
+}
+
+/// Check if the instr pair, FirstMI and SecondMI, should be fused
+/// together. Given SecondMI, when FirstMI is unspecified, then check if
+/// SecondMI may be part of a fused pair at all.
+static bool shouldScheduleAdjacent(const TargetInstrInfo &TII,
+                                   const TargetSubtargetInfo &TSI,
+                                   const MachineInstr *FirstMI,
+                                   const MachineInstr &SecondMI) {
+  const RISCVSubtarget &ST = static_cast<const RISCVSubtarget&>(TSI);
+  if (!ST.hasMacroFusion())
+    return false;
+
+  // We're only checking whether Second can be fused at all.
+  if (FirstMI == nullptr)
+    return true;
+
+  if (isLEAPair(FirstMI, SecondMI) ||
+          isClearUpWord(FirstMI, SecondMI) ||
+          isIndexedLoad(FirstMI, SecondMI))
+    return true;
+
+  if (isStorePair(FirstMI, SecondMI) || isLoadPair(FirstMI, SecondMI))
+    return true;
+
+  if (isGLoadOrFJump(FirstMI, SecondMI))
+    return true;
+  return false;
+}
+
+std::unique_ptr<ScheduleDAGMutation> createRISCVMacroFusionDAGMutation () {
+  return createMacroFusionDAGMutation(shouldScheduleAdjacent);
+}
+
+} // end namespace llvm

llvm/lib/Target/RISCV/RISCVSubtarget.h

const SelectionDAGTargetInfo *getSelectionDAGInfo() const override {
     return &TSInfo;
   }
   bool enableMachineScheduler() const override { return true; }
   bool hasStdExtM() const { return HasStdExtM; }
   bool hasStdExtA() const { return HasStdExtA; }
   bool hasStdExtF() const { return HasStdExtF; }
   bool hasStdExtD() const { return HasStdExtD; }
   bool hasStdExtC() const { return HasStdExtC; }
+  bool hasMacroFusion() const { return HasMacroFusion; }
   bool is64Bit() const { return HasRV64; }
   bool isRV32E() const { return IsRV32E; }
   bool enableLinkerRelax() const { return EnableLinkerRelax; }
   bool enableRVCHintInstrs() const { return EnableRVCHintInstrs; }
   MVT getXLenVT() const { return XLenVT; }
   unsigned getXLen() const { return XLen; }
   RISCVABI::ABI getTargetABI() const { return TargetABI; }
   bool isRegisterReservedByUser(Register i) const {
     assert(i < RISCV::NUM_TARGET_REGS && "Register out of range");
     return UserReservedRegister[i];
   }
 
 protected:
   // GlobalISel related APIs.
   std::unique_ptr<CallLowering> CallLoweringInfo;
   std::unique_ptr<InstructionSelector> InstSelector;
   std::unique_ptr<LegalizerInfo> Legalizer;
   std::unique_ptr<RegisterBankInfo> RegBankInfo;
 
+  /// True if the processor supports macrofusion.
+  bool HasMacroFusion = false;
+
 public:
   const CallLowering *getCallLowering() const override;
   InstructionSelector *getInstructionSelector() const override;
   const LegalizerInfo *getLegalizerInfo() const override;
   const RegisterBankInfo *getRegBankInfo() const override;
 };
 } // End llvm namespace
 
 #endif

llvm/lib/Target/RISCV/RISCVTargetMachine.cpp

 //===-- RISCVTargetMachine.cpp - Define TargetMachine for RISCV -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Implements the info about RISCV target spec.
 //
 //===----------------------------------------------------------------------===//
 
 #include "RISCVTargetMachine.h"
 #include "RISCV.h"
+#include "RISCVMacroFusion.h"
 #include "RISCVTargetObjectFile.h"
 #include "RISCVTargetTransformInfo.h"
 #include "TargetInfo/RISCVTargetInfo.h"
 #include "Utils/RISCVBaseInfo.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/GlobalISel/IRTranslator.h"
 #include "llvm/CodeGen/GlobalISel/InstructionSelect.h"

 class RISCVPassConfig : public TargetPassConfig {
 public:
   RISCVPassConfig(RISCVTargetMachine &TM, PassManagerBase &PM)
       : TargetPassConfig(TM, PM) {}
 
   RISCVTargetMachine &getRISCVTargetMachine() const {
     return getTM<RISCVTargetMachine>();
   }
-
+  ScheduleDAGInstrs *
+  createMachineScheduler(MachineSchedContext *C) const override {
+    ScheduleDAGMILive *DAG = createGenericSchedLive(C);
+    const RISCVSubtarget &ST = C->MF->getSubtarget<RISCVSubtarget>();
+    if (ST.hasMacroFusion())
+      DAG->addMutation(createRISCVMacroFusionDAGMutation());
+    return DAG;
+  }
+  ScheduleDAGInstrs *
+  createPostMachineScheduler(MachineSchedContext *C) const override {
+    const RISCVSubtarget &ST = C->MF->getSubtarget<RISCVSubtarget>();
+    if (ST.hasMacroFusion()) {
+      ScheduleDAGMI *DAG = createGenericSchedPostRA(C);
+      DAG->addMutation(createRISCVMacroFusionDAGMutation());
+      return DAG;
+    }
+    return nullptr;
+  }
   void addIRPasses() override;
   bool addInstSelector() override;
   bool addIRTranslator() override;
   bool addLegalizeMachineIR() override;
   bool addRegBankSelect() override;
   bool addGlobalInstructionSelect() override;
   void addPreEmitPass() override;
   void addPreEmitPass2() override;