[PPC] - Add LoadCluster/StoreCluster DAG mutations to the MachineScheduler

[inouehrs]

lib/Target/PowerPC/PPCInstrInfo.cpp

2016

Here, do you mean cache line size?
Some PPC processors use a shorter cache line size (e.g. L1$ of BG/Q or embedded PPC), so maybe better to avoid hardcoding a value.
(But, TTI->getCacheLineSize() always returns 64, since it is only used on BG/Q so far.)

2127

Ditto.

[nemanjai]

Please be a bit more careful to ensure that comments are complete sentences with the expected punctuation, etc. Also, if your editor doesn't automatically format your code, consider running the patch through clang-format-diff.

lib/Target/PowerPC/PPCInstrInfo.cpp

1937

What is the use of the string parameter?

1940

Naming convention.

1950

"...are instructions are..." -> "... instructions are..."

1953

Please fix the formatting in this comment. I believe we should send out an RFC on llvm-dev to provide a new property for intrinsics that specifies that they have side-effects but do not touch memory. We have such a flag for instructions, I think it makes sense to have it for intrinsics as well. If we do that, I believe this comment should include a FIXME to remove this function once such a property exists and is used correctly in the PPC back end in all instances where it should be used.

1957

Why can't SDNode::getGluedNode() be used for this purpose and eliminate the need for this function?

1959

Is the operand you're after not guaranteed to be the very last operand?
In any case, it seems more natural to loop over the operands in reverse order, terminating before the first - and return the Glue operand when one is found. If the loop terminates, assert and return SDValue().

1965

Why is this needed? It seems that the above loop has terminated either when it has gone over all the operands (caught by previous assert) or when it found an operand whose type is MVT::Glue (whose type you check in this assert again). I think the weird structure of this function makes the logic more difficult to reason about than it needs to be.

1966

Keep in mind that you'll be returning something that you probably don't want to return (i.e. what you would assert on) in a no-asserts build.

1992

Text for the assert.

2001

tlat -> that

2015

Why?

2016

I agree. If we mean cache line size, we should check the cache line size. If we don't have accurate information about the cache line size for the common processors in the TTI implementation, we should update the implementation.

2037

This assert is unnecessary. Already exists in getImm().

2099

I think you may have physical registers at this point for TOC based loads (i.e. X2/R2 may already be part of the instruction at this point). It would make sense to look into whether this is the case and if it is, we should handle physical registers. Other than that, I don't see any compelling need to handle physical registers here.

2102

I am probably missing something here so it's a good indication that a detailed comment is in order...
What I mean is that it appears at first glance that if we have a load-hit-store situation where the store is followed by a load from the exact memory location, we'd happily cluster them together here. Presumably there's something after this (or before?) that will prevent this, but I think it would be good to document that here.

2103

This line looks way too long.

2106

A comment as to why we're exiting here.

lib/Target/PowerPC/PPCInstrInfo.h

52

Please refrain from unrelated formatting changes.

183

"... a used..." -> "... used ..."

204

Sentence fragment in comment, please revise.

[sfertile]

lib/Target/PowerPC/PPCInstrInfo.cpp

1937

I was using the string argument for some debugging and left it in by accident. I'll clean it up.

2016

Yeah this is the cache-line size. I'll update it the TTI implementation like you guys suggest as part of this patch

lib/Target/PowerPC/PPCInstrInfo.h

enum {
   /// two dispatch pipes to be available to issue.
   PPC970_Cracked = 0x4,
 
   /// PPC970_Mask/Shift - This is a bitmask that selects the pipeline type that
   /// an instruction is issued to.
   PPC970_Shift = 3,
   PPC970_Mask = 0x07 << PPC970_Shift
 };
+
 enum PPC970_Unit {
   /// These are the various PPC970 execution unit pipelines.  Each instruction
   /// is one of these.
   PPC970_Pseudo = 0 << PPC970_Shift,   // Pseudo instruction
   PPC970_FXU    = 1 << PPC970_Shift,   // Fixed Point (aka Integer/ALU) Unit
   PPC970_LSU    = 2 << PPC970_Shift,   // Load Store Unit
   PPC970_FPU    = 3 << PPC970_Shift,   // Floating Point Unit
   PPC970_CRU    = 4 << PPC970_Shift,   // Control Register Unit
unsigned isStoreToStackSlot(const MachineInstr &MI,
                               int &FrameIndex) const override;
 
   bool findCommutedOpIndices(MachineInstr &MI, unsigned &SrcOpIdx1,
                              unsigned &SrcOpIdx2) const override;
 
   void insertNoop(MachineBasicBlock &MBB,
                   MachineBasicBlock::iterator MI) const override;
 
+  /// This is used by the pre-regalloc scheduler to determine if two loads are
+  /// loading from the same base address. It should only return true if the base
+  /// pointers are the same and the only differences between the two addresses
+  /// are the offset. It also returns the offsets by reference.
+  bool areLoadsFromSameBasePtr(SDNode *Load1, SDNode *Load2,
+                               int64_t &Offset1,
+                               int64_t &Offset2) const override;
+
+  /// shouldScheduleLoadsNear - This is a used by the pre-regalloc scheduler to
+  /// determine (in conjunction with areLoadsFromSameBasePtr) if two loads should
+  /// be scheduled togther. On some targets if two loads are loading from
+  /// addresses in the same cache line, it's better if they are scheduled
+  /// together. This function takes two integers that represent the load offsets
+  /// from the common base address. It returns true if it decides it's desirable
+  /// to schedule the two loads together. "NumLoads" is the number of loads that
+  /// have already been scheduled after Load1.
+  bool shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2,
+                               int64_t Offset1, int64_t Offset2,
+                               unsigned NumLoads) const override;
+
+
+  /// Get the base register and byte offset of an instruction that reads/writes
+  /// memory.
+  virtual bool getMemOpBaseRegImmOfs(MachineInstr &MemOp, unsigned &BaseReg,
+                                     int64_t &Offset,
+                                     const TargetRegisterInfo *TRI) const override;
+
+  /// Returns true if the two given memory operations should be scheduled
+  /// adjacent. Called from the LoadCluster/StoreCluster DAG mutation passes.
+  /// to TargetPassConfig::createMachineScheduler() to have an effect.
+  virtual bool shouldClusterMemOps(MachineInstr &FirstLdSt,
+                                   MachineInstr &SecondLdSt,
+                                   unsigned NumLoads) const override;
 
   // Branch analysis.
   bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                      MachineBasicBlock *&FBB,
                      SmallVectorImpl<MachineOperand> &Cond,
                      bool AllowModify) const override;
   unsigned removeBranch(MachineBasicBlock &MBB,
                         int *BytesRemoved = nullptr) const override;

lib/Target/PowerPC/PPCInstrInfo.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
+static cl::opt<unsigned> VectorLoadClusterCount("vec-load-clustering", cl::Hidden, cl::init(4));
+static cl::opt<unsigned> ScalarLoadClusterCount("scalar-load-clustering", cl::Hidden, cl::init(4));
+
 #define DEBUG_TYPE "ppc-instr-info"
 
 #define GET_INSTRMAP_INFO
 #define GET_INSTRINFO_CTOR_DTOR
 #include "PPCGenInstrInfo.inc"
 
 static cl::
 opt<bool> DisableCTRLoopAnal("disable-ppc-ctrloop-analysis", cl::Hidden,

 }
 
 const TargetRegisterClass *
 PPCInstrInfo::updatedRC(const TargetRegisterClass *RC) const {
   if (Subtarget.hasVSX() && RC == &PPC::VRRCRegClass)
     return &PPC::VSRCRegClass;
   return RC;
 }
+
+
+static MachineMemOperand* extractBasePointer(MachineSDNode *Load, const char* LoadName) {
+  MachineMemOperand **IMemOp = Load->memoperands_begin();
+  if(IMemOp) {
+    MachineMemOperand* ret = *IMemOp;
+    assert(++IMemOp == Load->memoperands_end() &&
+           "Expect a single memory operand in a load");
+    return ret;
+  }
+
+  return nullptr;
+}
+
+// Some machine instructions may have both mayLoad and mayStore flags set.
+// These are instructions are lowered from intrinsics that don't actually
+// touch memory, but can not have the IntrNoMem flags becuase it needs to be
+//  inserted into the chain due to their side-effects.
+static bool mayActuallyLoad(MCInstrDesc Desc) {
+  return Desc.mayLoad() && !Desc.mayStore();
+}
+
+static SDValue getChainOperand(SDNode *Node) {
+  unsigned OpIndex  = Node->getNumOperands();
+  while(OpIndex && Node->getOperand(OpIndex - 1).getValueType() == MVT::Glue) {
+    --OpIndex;
+  }
+
+  assert(OpIndex && "expected at least one Operand!");
+  SDValue ChainOp = Node->getOperand(--OpIndex);
+  assert(ChainOp.getValueType() == MVT::Other && "Expected Chain Operand!");
+  return ChainOp;
+}
+
+bool PPCInstrInfo::areLoadsFromSameBasePtr(SDNode *Load1, SDNode *Load2,
+                                    int64_t &Offset1, int64_t &Offset2) const {
+
+  // Only interested in MachineSDNodes
+  if(!Load1->isMachineOpcode() || !Load2->isMachineOpcode()) {
+    return false;
+  }
+
+  const MCInstrDesc &MCIDesc1 = get(Load1->getMachineOpcode());
+  const MCInstrDesc &MCIDesc2 = get(Load2->getMachineOpcode());
+  if(!mayActuallyLoad(MCIDesc1) || MCIDesc1.isPseudo() ||
+     !mayActuallyLoad(MCIDesc2) || MCIDesc2.isPseudo()) {
+    return false;
+  }
+
+  // only interested in Loads in the same chain.
+  if(getChainOperand(Load1) != getChainOperand(Load2)) {
+    return false;
+  }
+
+  // Get the memory operands
+  MachineSDNode *MachineLoad1 = dyn_cast<MachineSDNode>(Load1);
+  MachineSDNode *MachineLoad2 = dyn_cast<MachineSDNode>(Load2);
+  assert(MachineLoad1 && MachineLoad1);
+  MachineMemOperand *MemOp1 = extractBasePointer(MachineLoad1, "Load1");
+  MachineMemOperand *MemOp2 = extractBasePointer(MachineLoad2, "Load2");;
+
+  // Not every load will have its MMO properly set. For example the loads
+  // created from intrinsic calls might not have them set.
+  if(!MemOp1 || !MemOp2)
+     return false;
+
+  // Check tlat the memory ops use the same base value
+  if(MemOp1->getValue() == MemOp2->getValue()) {
+    Offset1 = MemOp1->getOffset();
+    Offset2 = MemOp2->getOffset();
+    return true;
+  }
+
+  // Loads are off different base values.
+  return false;
+}
+
+bool PPCInstrInfo::shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2,
+                             int64_t Offset1, int64_t Offset2,
+                             unsigned NumLoads) const  {
+  assert(Offset2 > Offset1 && "Offset2 must larger then Offset1!");
+  if(Offset2 - Offset1 > 128)
+     return false;
+
+  // Want to cluster vector loads with a different threshold from scalar loads
+  // due to having more vector registers. Since the incoming Loads are sorted
+  // based on offset
+  EVT VT = Load1->getValueType(0);
+  if (VT.isVector()) {
+    return NumLoads < VectorLoadClusterCount ;
+  }
+
+  return NumLoads < ScalarLoadClusterCount;
+}
+
+static bool tryExtractImm(MachineInstr *MI, int64_t &Offset) {
+  switch(MI->getOpcode())
+    {
+    default:
+      return false;
+    case PPC::LI8:
+    case PPC::LI:
+     assert(MI->getOperand(1).isImm());
+     Offset = MI->getOperand(1).getImm();
+     return true;
+    }
+}
+
+bool PPCInstrInfo::getMemOpBaseRegImmOfs(MachineInstr &MemOp, unsigned &BaseReg,
+                                         int64_t &Offset,
+                                         const TargetRegisterInfo *TRI) const {
+
+  const MCInstrDesc &InstrDesc = get(MemOp.getOpcode());
+
+  // mayLoad and mayStore means its a MachineInstr with side-effects rather then
+  // an actual memory operation.
+  if (InstrDesc.mayLoad() && InstrDesc.mayStore()) {
+    return false;
+  }
+
+  // expect at least 3 (explicit) operands.
+  if(MemOp.getNumExplicitOperands() < 3) {
+    return false;
+  }
+
+  MachineOperand &Mo1 = MemOp.getOperand(1);
+  MachineOperand &Mo2 = MemOp.getOperand(2);
+
+  // Check for 'BaseAddr + imm' and 'imm + BaseAddr'.
+  if(Mo1.isReg() && Mo2.isImm()) {
+     BaseReg = Mo1.getReg();
+     Offset = Mo2.getImm();
+     return true;
+  } else if (Mo2.isReg() && Mo1.isImm()) {
+     BaseReg = Mo2.getReg();
+     Offset = Mo1.getImm();
+     return true;
+  }
+
+  if (!(Mo1.isReg() && Mo2.isReg())) {
+    return false;
+  }
+
+  // check for 'r0 + BaseAddr'
+  if (Mo1.getReg() == PPC::ZERO8 || Mo1.getReg() == PPC::ZERO) {
+    BaseReg = Mo2.getReg();
+    Offset = 0;
+    return true;
+  }
+
+  BaseReg = Mo1.getReg();
+  MachineRegisterInfo &MRI = MemOp.getParent()->getParent()->getRegInfo();
+
+  // Try to extract an immediate from the register definition.
+  if(TargetRegisterInfo::isVirtualRegister(Mo2.getReg())) {
+    // May have more then one def
+    if(!MRI.hasOneDef(Mo2.getReg())) {
+     return false;
+    }
+
+    MachineInstr *MI = MRI.getVRegDef(Mo2.getReg());
+    return tryExtractImm(MI, Offset);
+  }
+
+  // TODO Do I need to handle physical registers at this point?
+  return false;
+}
+
+bool PPCInstrInfo::shouldClusterMemOps(MachineInstr &FirstLdSt, MachineInstr &SecondLdSt,
+                         unsigned NumLoads) const {
+
+  if (FirstLdSt.hasOrderedMemoryRef() || SecondLdSt.hasOrderedMemoryRef()) {
+    return false;
+  }
+
+  const TargetRegisterInfo *TRI = &getRegisterInfo();
+  unsigned FirstBaseReg, SecondBaseReg;
+  int64_t FirstOffset, SecondOffset;
+
+  if (!getMemOpBaseRegImmOfs(FirstLdSt, FirstBaseReg, FirstOffset, TRI) ||
+      !getMemOpBaseRegImmOfs(SecondLdSt, SecondBaseReg, SecondOffset, TRI)) {
+    return false;
+  }
+
+  // Only cluster loads from the same base address
+  if (FirstBaseReg != SecondBaseReg)
+     return false;
+
+  int64_t OffsetDiff =  FirstOffset > SecondOffset ?
+                        FirstOffset - SecondOffset :
+                        SecondOffset - FirstOffset;
+
+  if(OffsetDiff > 128) {
+    return false;
+  }
+
+  return true;
+}

lib/Target/PowerPC/PPCTargetMachine.cpp

 #include "PPCTargetTransformInfo.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
+#include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Target/TargetLoweringObjectFile.h"

 public:
   PPCPassConfig(PPCTargetMachine *TM, PassManagerBase &PM)
     : TargetPassConfig(TM, PM) {}
 
   PPCTargetMachine &getPPCTargetMachine() const {
     return getTM<PPCTargetMachine>();
   }
 
+  ScheduleDAGInstrs *
+  createMachineScheduler(MachineSchedContext *C) const override {
+    // TODO: Create the default for non-P8 Targets.
+    // ScheduleDAGInstrs *DAG =  TargetPassConfig::createMachineScheduler(C);
+    ScheduleDAGMILive *DAG = createGenericSchedLive(C);
+    DAG->addMutation(createLoadClusterDAGMutation(DAG->TII, DAG->TRI));
+    DAG->addMutation(createStoreClusterDAGMutation(DAG->TII, DAG->TRI));
+
+    return DAG;
+  }
+
   void addIRPasses() override;
   bool addPreISel() override;
   bool addILPOpts() override;
   bool addInstSelector() override;
   void addMachineSSAOptimization() override;
   void addPreRegAlloc() override;
   void addPreSched2() override;
   void addPreEmitPass() override;

test/CodeGen/PowerPC/fp128-bitcast-after-operation.ll

 ; PPC64-P8-DAG: li [[MASK_REG:[0-9]+]], 1
 ; PPC64-P8-DAG: sldi [[SHIFT_REG:[0-9]+]], [[MASK_REG]], 63
 ; PPC64-P8: and [[FLIP_BIT:[0-9]+]], [[HI]], [[SHIFT_REG]]
 ; PPC64-P8-DAG: xor 3, [[HI]], [[FLIP_BIT]]
 ; PPC64-P8-DAG: xor 4, [[LO]], [[FLIP_BIT]]
 ; PPC64-P8: blr
 
 ; PPC32-DAG: stfd 1, 24(1)
-; PPC32-DAG: stfd 2, 16(1)
+; PPC32: nop
 ; PPC32: nop
 ; PPC32-DAG: lwz [[HI0:[0-9]+]], 24(1)
-; PPC32-DAG: lwz [[LO0:[0-9]+]], 16(1)
 ; PPC32-DAG: lwz [[HI1:[0-9]+]], 28(1)
+; PPC32-DAG: stfd 2, 16(1)
+; PPC32-DAG: lwz [[LO0:[0-9]+]], 16(1)
 ; PPC32-DAG: lwz [[LO1:[0-9]+]], 20(1)
 ; PPC32: rlwinm [[FLIP_BIT:[0-9]+]], [[HI0]], 0, 0, 0
 ; PPC32-DAG: xor [[HI0]], [[HI0]], [[FLIP_BIT]]
 ; PPC32-DAG: xor [[LO0]], [[LO0]], [[FLIP_BIT]]
 ; PPC32: blr
   %0 = tail call ppc_fp128 @llvm.fabs.ppcf128(ppc_fp128 %x)
   %1 = bitcast ppc_fp128 %0 to i128
   ret i128 %1

test/CodeGen/PowerPC/jaggedstructs.ll

 ; CHECK: lwz {{[0-9]+}}, 171(1)
 ; CHECK: stb {{[0-9]+}}, 63(1)
 ; CHECK: stw {{[0-9]+}}, 59(1)
 ; CHECK: lhz {{[0-9]+}}, 182(1)
 ; CHECK: lwz {{[0-9]+}}, 178(1)
 ; CHECK: sth {{[0-9]+}}, 70(1)
 ; CHECK: stw {{[0-9]+}}, 66(1)
 ; CHECK: lbz {{[0-9]+}}, 191(1)
-; CHECK: lhz {{[0-9]+}}, 189(1)
 ; CHECK: lwz {{[0-9]+}}, 185(1)
-; CHECK: stb {{[0-9]+}}, 79(1)
+; CHECK: lhz {{[0-9]+}}, 189(1)
 ; CHECK: sth {{[0-9]+}}, 77(1)
+; CHECK: stb {{[0-9]+}}, 79(1)
 ; CHECK: stw {{[0-9]+}}, 73(1)
 ; CHECK: ld 6, 72(1)
 ; CHECK: ld 5, 64(1)
 ; CHECK: ld 4, 56(1)
 ; CHECK: ld 3, 48(1)
 
 declare void @check(%struct.S3* byval, %struct.S5* byval, %struct.S6* byval, %struct.S7* byval)

test/CodeGen/PowerPC/memcpy-vec.ll

entry:
   %0 = bitcast double* %x to i8*
   %1 = bitcast double* %y to i8*
   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %0, i8* %1, i64 32, i32 8, i1 false)
   ret void
 
 ; PWR7-LABEL: @foo1
 ; PWR7-NOT: bl memcpy
 ; PWR7-DAG: li [[OFFSET:[0-9]+]], 16
-; PWR7-DAG: lxvd2x [[TMP0:[0-9]+]], 4, [[OFFSET]]
+; PWR7-DAG: lxvd2x [[TMP0:[0-9]+]], 0, 4
+; PWR7-DAG: lxvd2x [[TMP1:[0-9]+]], 4, [[OFFSET]]
+; PWR7-DAG: stxvd2x [[TMP1]], 3, [[OFFSET]]
 ; PWR7-DAG: stxvd2x [[TMP0]], 0, 3
-; PWR7-DAG: lxvd2x [[TMP1:[0-9]+]], 0, 4
-; PWR7-DAG: stxvd2x [[TMP1]], 0, 3
 ; PWR7: blr
 
 ; PWR8-LABEL: @foo1
 ; PWR8: lxvw4x
 ; PWR8: stxvw4x
 ; PWR8: blr
 
 ; A2Q-LABEL: @foo1

test/CodeGen/PowerPC/ppc32-vacopy.ll

entry:
   call void @llvm.va_copy(i8* %3, i8* %2)
 
   ret void
 }
 ; CHECK: test_vacopy:
 ; CHECK: lwz [[REG1:[0-9]+]], {{.*}}
 ; CHECK: lwz [[REG2:[0-9]+]], {{.*}}
 ; CHECK: lwz [[REG3:[0-9]+]], {{.*}}
-; CHECK: stw [[REG1]], {{.*}}
-; CHECK: stw [[REG2]], {{.*}}
 ; CHECK: stw [[REG3]], {{.*}}
+; CHECK: stw [[REG2]], {{.*}}
+; CHECK: stw [[REG1]], {{.*}}

test/CodeGen/PowerPC/ppcf128-endian.ll

 define void @caller() {
 entry:
   %0 = load ppc_fp128, ppc_fp128* @g, align 16
   call void @test(ppc_fp128 %0)
   ret void
 }
 ; CHECK: @caller
 ; CHECK: ld [[REG:[0-9]+]], .LC
-; CHECK: lfd 2, 8([[REG]])
 ; CHECK: lfd 1, 0([[REG]])
+; CHECK: lfd 2, 8([[REG]])
 ; CHECK: bl test
 
 declare void @test(ppc_fp128)
 
 define void @caller_const() {
 entry:
   call void @test(ppc_fp128 0xM3FF00000000000000000000000000000)
   ret void