[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

21

Please, expand this comment.

26

Please, expand the acronym.

45

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 ↗

(On Diff #241740)

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

72 ↗

(On Diff #241740)

"Fuse select instruction pairs"

119 ↗

(On Diff #241740)

Does Rocket fuse all these pairs?

llvm/lib/Target/RISCV/RISCVMacroFusion.cpp

103

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 ↗

(On Diff #241740)

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

38

This is clearly not a jump.

62

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

80

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/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 Idiom
+static bool isLEAPair(const MachineInstr *FirstMI,
+                           const MachineInstr &SecondMI) {
+  if (FirstMI->getOpcode() == RISCV::SLLI) {
+      switch (SecondMI.getOpcode()) {
+        // LEA
+        case  RISCV::ADD:
+          return true;
+        // Indexed Load
+        case  RISCV::LD:
+          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()) {
+        case  RISCV::ADDI:
+          return true;
+        // LUI based Loads
+        case RISCV::LD:
+          return true;
+      }
+  }
+  return false;
+}
+
+
+/// 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);
+
+  // We're only checking whether Second can be fused at all.
+  if (FirstMI == nullptr)
+    return true;
+
+  if (isLEAPair(FirstMI, SecondMI))
+    return true;
+
+  if (isClearUpWord(FirstMI, SecondMI))
+    return true;
+
+  return false;
+}
+
+std::unique_ptr<ScheduleDAGMutation> createRISCVMacroFusionDAGMutation () {
+  return createMacroFusionDAGMutation(shouldScheduleAdjacent);
+}
+
+} // end namespace llvm

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);
+    DAG->addMutation(createRISCVMacroFusionDAGMutation());
+    return DAG;
+  }
   void addIRPasses() override;
   bool addInstSelector() override;
   bool addIRTranslator() override;
   bool addLegalizeMachineIR() override;
   bool addRegBankSelect() override;
   bool addGlobalInstructionSelect() override;
   void addPreEmitPass() override;
   void addPreEmitPass2() override;
   void addPreRegAlloc() override;
 };
 }

llvm/test/CodeGen/RISCV/add-before-shl.ll

; RV64I-NEXT:    ret
   %2 = shl i32 %1, 24
   %3 = ashr i32 %2, 24
   ret i32 %3
 }
 
 define signext i32 @add_large_const(i32 signext %a) nounwind {
 ; RV32I-LABEL: add_large_const:
 ; RV32I:       # %bb.0:
-; RV32I-NEXT:    slli a0, a0, 16
 ; RV32I-NEXT:    lui a1, 65520
+; RV32I-NEXT:    slli a0, a0, 16
 ; RV32I-NEXT:    add a0, a0, a1
 ; RV32I-NEXT:    srai a0, a0, 16
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: add_large_const:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    lui a1, 1
 ; RV64I-NEXT:    addiw a1, a1, -1
 ; RV64I-NEXT:    add a0, a0, a1
 ; RV64I-NEXT:    slli a0, a0, 48
 ; RV64I-NEXT:    srai a0, a0, 48
 ; RV64I-NEXT:    ret
   %1 = add i32 %a, 4095
   %2 = shl i32 %1, 16
   %3 = ashr i32 %2, 16
   ret i32 %3
 }
 
 define signext i32 @add_huge_const(i32 signext %a) nounwind {
 ; RV32I-LABEL: add_huge_const:
 ; RV32I:       # %bb.0:
-; RV32I-NEXT:    slli a0, a0, 16
 ; RV32I-NEXT:    lui a1, 524272
+; RV32I-NEXT:    slli a0, a0, 16
 ; RV32I-NEXT:    add a0, a0, a1
 ; RV32I-NEXT:    srai a0, a0, 16
 ; RV32I-NEXT:    ret
 ;
 ; RV64I-LABEL: add_huge_const:
 ; RV64I:       # %bb.0:
 ; RV64I-NEXT:    lui a1, 8
 ; RV64I-NEXT:    addiw a1, a1, -1