[RISCV] Add InstrInfo areMemAccessesTriviallyDisjoint hook

[luismarques]

Summary

Introduces the InstrInfo::areMemAccessesTriviallyDisjoint hook.
The test could check for instruction reorderings, but to avoid being brittle it just checks instruction dependencies.

[luismarques]

Added a test. Updated summary.

[lenary]

llvm/test/CodeGen/RISCV/disjoint.ll

27

This test seems really brittle.

Now that you've implemented the hook, the compiler can see that this load and store do not interact, so can now schedule the store after the load. However, what the hook actually means for these instructions is that the load and store don't interact, and so any more-specific schedule could undo this change by implementing a schedule that thinks if you do the store first, the code is faster.

I don't know how to write a test that's less brittle to this kind of issue. I suppose a lot of asm tests could be changed by a change in the schedule, but it seems like this one has a large chance of suddenly not testing anything.

Do you have any better ideas for how to test this, or do we not have enough testcases that hit the hook and are trivially disjoint?

[lenary]

I have decided I'm not too worried by the brittle test.

[luismarques]

Rebased the test on master.
Changed the test to instead check the instruction dependencies directly.
Updated summary.

[luismarques]

Changed the test. Please review again. Thank you!

[luismarques]

NFC. Appease clang-format, even though it was a copy-pasted declaration.

[luismarques]

Fix RUN lines and add REQUIRES: asserts.

[lenary]

llvm/test/CodeGen/RISCV/disjoint.ll

6

Please can you write a few sentences explaining how this tests that these two SW's are disjoint?

I presume it's to do with the fact that the scheduler does not deem the SW %1:gpr, %0:gpr, 8 to have to come after the first SW (it not being in the successors list).

Knowing how this tests the disjoint hook will help us understand how to update the test if the exact output ever changes.

[lenary]

LGTM. When you land it, do add a comment about how the disjoint.ll test works.

[luismarques]

Rebased on master. Add test comments.

[luismarques]

llvm/test/CodeGen/RISCV/disjoint.ll

27

You're right, this merited some context and explanation. Thanks!

llvm/lib/Target/RISCV/RISCVInstrInfo.h

 #include "RISCVRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 
 #define GET_INSTRINFO_HEADER
 #include "RISCVGenInstrInfo.inc"
 
 namespace llvm {
 
+class RISCVSubtarget;
+
 class RISCVInstrInfo : public RISCVGenInstrInfo {
 
 public:
-  RISCVInstrInfo();
+  explicit RISCVInstrInfo(RISCVSubtarget &STI);
 
   unsigned isLoadFromStackSlot(const MachineInstr &MI,
                                int &FrameIndex) const override;
   unsigned isStoreToStackSlot(const MachineInstr &MI,
                               int &FrameIndex) const override;
 
   void copyPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                    const DebugLoc &DL, unsigned DstReg, unsigned SrcReg,
public:
   reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;
 
   MachineBasicBlock *getBranchDestBlock(const MachineInstr &MI) const override;
 
   bool isBranchOffsetInRange(unsigned BranchOpc,
                              int64_t BrOffset) const override;
 
   bool isAsCheapAsAMove(const MachineInstr &MI) const override;
+
+  bool getMemOperandWithOffsetWidth(const MachineInstr &LdSt,
+                                    const MachineOperand *&BaseOp,
+                                    int64_t &Offset, unsigned &Width,
+                                    const TargetRegisterInfo *TRI) const;
+
+  bool areMemAccessesTriviallyDisjoint(const MachineInstr &MIa,
+                                       const MachineInstr &MIb) const override;
+
+protected:
+  const RISCVSubtarget &STI;
 };
 }
 #endif

llvm/lib/Target/RISCV/RISCVInstrInfo.cpp

 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/TargetRegistry.h"
 
 #define GET_INSTRINFO_CTOR_DTOR
 #include "RISCVGenInstrInfo.inc"
 
 using namespace llvm;
 
-RISCVInstrInfo::RISCVInstrInfo()
-    : RISCVGenInstrInfo(RISCV::ADJCALLSTACKDOWN, RISCV::ADJCALLSTACKUP) {}
+RISCVInstrInfo::RISCVInstrInfo(RISCVSubtarget &STI)
+    : RISCVGenInstrInfo(RISCV::ADJCALLSTACKDOWN, RISCV::ADJCALLSTACKUP),
+      STI(STI) {}
 
 unsigned RISCVInstrInfo::isLoadFromStackSlot(const MachineInstr &MI,
                                              int &FrameIndex) const {
   switch (MI.getOpcode()) {
   default:
     return 0;
   case RISCV::LB:
   case RISCV::LBU:
default:
       break;
     case RISCV::ADDI:
     case RISCV::ORI:
     case RISCV::XORI:
       return (MI.getOperand(1).isReg() && MI.getOperand(1).getReg() == RISCV::X0);
   }
   return MI.isAsCheapAsAMove();
 }
+
+// Return true if get the base operand, byte offset of an instruction and the
+// memory width. Width is the size of memory that is being loaded/stored.
+bool RISCVInstrInfo::getMemOperandWithOffsetWidth(
+    const MachineInstr &LdSt, const MachineOperand *&BaseReg, int64_t &Offset,
+    unsigned &Width, const TargetRegisterInfo *TRI) const {
+  assert(LdSt.mayLoadOrStore() && "Expected a memory operation.");
+
+  // Here we assume the standard RISC-V ISA, which uses a base+offset
+  // addressing mode. You'll need to relax these conditions to support custom
+  // load/stores instructions.
+  if (LdSt.getNumExplicitOperands() != 3)
+    return false;
+  if (!LdSt.getOperand(1).isReg() || !LdSt.getOperand(2).isImm())
+    return false;
+
+  if (!LdSt.hasOneMemOperand())
+    return false;
+
+  Width = (*LdSt.memoperands_begin())->getSize();
+  BaseReg = &LdSt.getOperand(1);
+  Offset = LdSt.getOperand(2).getImm();
+  return true;
+}
+
+bool RISCVInstrInfo::areMemAccessesTriviallyDisjoint(
+    const MachineInstr &MIa, const MachineInstr &MIb) const {
+  assert(MIa.mayLoadOrStore() && "MIa must be a load or store.");
+  assert(MIb.mayLoadOrStore() && "MIb must be a load or store.");
+
+  if (MIa.hasUnmodeledSideEffects() || MIb.hasUnmodeledSideEffects() ||
+      MIa.hasOrderedMemoryRef() || MIb.hasOrderedMemoryRef())
+    return false;
+
+  // Retrieve the base register, offset from the base register and width. Width
+  // is the size of memory that is being loaded/stored (e.g. 1, 2, 4).  If
+  // base registers are identical, and the offset of a lower memory access +
+  // the width doesn't overlap the offset of a higher memory access,
+  // then the memory accesses are different.
+  const TargetRegisterInfo *TRI = STI.getRegisterInfo();
+  const MachineOperand *BaseOpA = nullptr, *BaseOpB = nullptr;
+  int64_t OffsetA = 0, OffsetB = 0;
+  unsigned int WidthA = 0, WidthB = 0;
+  if (getMemOperandWithOffsetWidth(MIa, BaseOpA, OffsetA, WidthA, TRI) &&
+      getMemOperandWithOffsetWidth(MIb, BaseOpB, OffsetB, WidthB, TRI)) {
+    if (BaseOpA->isIdenticalTo(*BaseOpB)) {
+      int LowOffset = std::min(OffsetA, OffsetB);
+      int HighOffset = std::max(OffsetA, OffsetB);
+      int LowWidth = (LowOffset == OffsetA) ? WidthA : WidthB;
+      if (LowOffset + LowWidth <= HighOffset)
+        return true;
+    }
+  }
+  return false;
+}

llvm/lib/Target/RISCV/RISCVSubtarget.cpp

RISCVSubtarget &RISCVSubtarget::initializeSubtargetDependencies(
   RISCVFeatures::validate(TT, getFeatureBits());
   return *this;
 }
 
 RISCVSubtarget::RISCVSubtarget(const Triple &TT, StringRef CPU, StringRef FS,
                                StringRef ABIName, const TargetMachine &TM)
     : RISCVGenSubtargetInfo(TT, CPU, FS),
       FrameLowering(initializeSubtargetDependencies(TT, CPU, FS, ABIName)),
-      InstrInfo(), RegInfo(getHwMode()), TLInfo(TM, *this) {
+      InstrInfo(*this), RegInfo(getHwMode()), TLInfo(TM, *this) {
   CallLoweringInfo.reset(new RISCVCallLowering(*getTargetLowering()));
   Legalizer.reset(new RISCVLegalizerInfo(*this));
 
   auto *RBI = new RISCVRegisterBankInfo(*getRegisterInfo());
   RegBankInfo.reset(RBI);
   InstSelector.reset(createRISCVInstructionSelector(
       *static_cast<const RISCVTargetMachine *>(&TM), *this, *RBI));
 }

llvm/test/CodeGen/RISCV/disjoint.ll

+; REQUIRES: asserts
+; RUN: llc -mtriple=riscv32 -debug-only=machine-scheduler < %s \
+; RUN:   -o /dev/null 2>&1 | FileCheck %s
+; RUN: llc -mtriple=riscv64 -debug-only=machine-scheduler < %s \
+; RUN:   -o /dev/null 2>&1 | FileCheck %s
+
+define i32 @test_disjoint(i32* %P, i32 %v) {
+entry:
+; CHECK: ********** MI Scheduling **********
+; CHECK-LABEL: test_disjoint:%bb.0
+; CHECK:SU(2):   SW %1:gpr, %0:gpr, 12 :: (store 4 into %ir.arrayidx)
+; CHECK-NOT: Successors:
+; CHECK:SU(3):   SW %1:gpr, %0:gpr, 8 :: (store 4 into %ir.arrayidx1)
+; CHECK: Predecessors:
+; CHECK-NOT:    SU(2): Ord  Latency=0 Memory
+  %arrayidx = getelementptr inbounds i32, i32* %P, i32 3
+  store i32 %v, i32* %arrayidx
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i32 2
+  store i32 %v, i32* %arrayidx1
+  ret i32 %v
+}