[AMDGPU/MemOpsCluster] Code clean-up around mem ops clustering logic

[hsmhsm]

Summary

Clean-up code around mem ops clustering logic. This patch cleans up code within
the function clusterNeighboringMemOps(). It is WIP, and this patch is a first cut.

[foad]

This causes lots of test failures:

Failing Tests (35):
  LLVM :: CodeGen/AMDGPU/GlobalISel/cvt_f32_ubyte.ll
  LLVM :: CodeGen/AMDGPU/GlobalISel/llvm.amdgcn.div.fmas.ll
  LLVM :: CodeGen/AMDGPU/GlobalISel/llvm.amdgcn.div.scale.ll
  LLVM :: CodeGen/AMDGPU/GlobalISel/llvm.amdgcn.ubfe.ll
  LLVM :: CodeGen/AMDGPU/amdgpu-codegenprepare-idiv.ll
  LLVM :: CodeGen/AMDGPU/amdhsa-trap-num-sgprs.ll
  LLVM :: CodeGen/AMDGPU/bitreverse.ll
  LLVM :: CodeGen/AMDGPU/call-argument-types.ll
  LLVM :: CodeGen/AMDGPU/cvt_f32_ubyte.ll
  LLVM :: CodeGen/AMDGPU/fshr.ll
  LLVM :: CodeGen/AMDGPU/idot2.ll
  LLVM :: CodeGen/AMDGPU/idot4s.ll
  LLVM :: CodeGen/AMDGPU/idot4u.ll
  LLVM :: CodeGen/AMDGPU/idot8s.ll
  LLVM :: CodeGen/AMDGPU/idot8u.ll
  LLVM :: CodeGen/AMDGPU/insert_vector_dynelt.ll
  LLVM :: CodeGen/AMDGPU/insert_vector_elt.v2i16.ll
  LLVM :: CodeGen/AMDGPU/llvm.amdgcn.raw.buffer.load.ll
  LLVM :: CodeGen/AMDGPU/llvm.maxnum.f16.ll
  LLVM :: CodeGen/AMDGPU/llvm.minnum.f16.ll
  LLVM :: CodeGen/AMDGPU/llvm.round.f64.ll
  LLVM :: CodeGen/AMDGPU/memory_clause.ll
  LLVM :: CodeGen/AMDGPU/merge-stores.ll
  LLVM :: CodeGen/AMDGPU/promote-constOffset-to-imm.ll
  LLVM :: CodeGen/AMDGPU/salu-to-valu.ll
  LLVM :: CodeGen/AMDGPU/sdiv.ll
  LLVM :: CodeGen/AMDGPU/sdiv64.ll
  LLVM :: CodeGen/AMDGPU/setcc-limit-load-shrink.ll
  LLVM :: CodeGen/AMDGPU/sgpr-control-flow.ll
  LLVM :: CodeGen/AMDGPU/smrd.ll
  LLVM :: CodeGen/AMDGPU/srem64.ll
  LLVM :: CodeGen/AMDGPU/trunc-combine.ll
  LLVM :: CodeGen/AMDGPU/udiv64.ll
  LLVM :: CodeGen/AMDGPU/urem64.ll
  LLVM :: CodeGen/AMDGPU/use-sgpr-multiple-times.ll


Testing Time: 358.21s
  Unsupported Tests  :   102
  Expected Passes    : 15421
  Expected Failures  :    49
  Unexpected Failures:    35

[foad]

(1) NumLoads argument can initially be set to 2 instead of 1, this avoids incrementing NumLoads while calling shouldClusterMemOps()

Alternatively you could move ++ClusterLength to just before the call to shouldClusterMemOps. But I really don't think this is very important.

(2) Re-arrange the code within clusterNeighboringMemOps(), so that the code is more convenient to understand

I agree that using continue is more readable.

(3) Improve the logic within shouldClusterMemOps() and remove all FIXMEs

You've changed it to accurately count bytes in a cluster, which is nice, but (a) it's a change in behvaiour so needs test updates and benchmarking, and (b) I don't particularly like the implementation. I think a cleaner way to do this would be to change all target getMemOperandsWithOffset functions to return a Width (in bytes) as well (some targets already have an internal getMemOperandsWithOffsetWidth function which does this) and change MachineScheduler to use this information to track the size of a cluster, and pass that information into shouldClusterMemOps.

[hsmhsm]

Since it is safe to do clean-up step-by-step, the previous somewhat larger
patch is reverted back, and in this modified patch, initial step is taken
towards the clean-up.

[hsmhsm]

Hi Jay,

I would not want to submit bigger patch since it is bit risky. So, let's take it step-by-step at time. This modified patch is the first cut.

[foad]

Looks OK to me. Please also update the "summary" section at the top of this review (unfortunately "arc diff" does not do this for you when you edit the git commit message, so you have to do it by hand).

llvm/lib/CodeGen/MachineScheduler.cpp

#ifndef NDEBUG
     for (auto *Op : BaseOps)
       assert(Op);
 #endif
   }
   if (MemOpRecords.size() < 2)
     return;
 
   llvm::sort(MemOpRecords);
-  unsigned ClusterLength = 1;
+
+  unsigned ClusterLength = 2;
   for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {
-    SUnit *SUa = MemOpRecords[Idx].SU;
-    SUnit *SUb = MemOpRecords[Idx+1].SU;
-    if (TII->shouldClusterMemOps(MemOpRecords[Idx].BaseOps,
-                                 MemOpRecords[Idx + 1].BaseOps,
-                                 ClusterLength + 1)) {
-      if (SUa->NodeNum > SUb->NodeNum)
-        std::swap(SUa, SUb);
-      if (DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) {
-        LLVM_DEBUG(dbgs() << "Cluster ld/st SU(" << SUa->NodeNum << ") - SU("
-                          << SUb->NodeNum << ")\n");
-        // Copy successor edges from SUa to SUb. Interleaving computation
-        // dependent on SUa can prevent load combining due to register reuse.
-        // Predecessor edges do not need to be copied from SUb to SUa since
-        // nearby loads should have effectively the same inputs.
-        for (const SDep &Succ : SUa->Succs) {
-          if (Succ.getSUnit() == SUb)
-            continue;
-          LLVM_DEBUG(dbgs()
-                     << "  Copy Succ SU(" << Succ.getSUnit()->NodeNum << ")\n");
-          DAG->addEdge(Succ.getSUnit(), SDep(SUb, SDep::Artificial));
-        }
-        ++ClusterLength;
-      } else
-        ClusterLength = 1;
-    } else
-      ClusterLength = 1;
+    // Decision to cluster mem ops is taken based on target dependent logic
+    auto MemOpa = MemOpRecords[Idx];
+    auto MemOpb = MemOpRecords[Idx + 1];
+    if (!TII->shouldClusterMemOps(MemOpa.BaseOps, MemOpb.BaseOps,
+                                  ClusterLength)) {
+      // Current mem ops pair could not be clustered, reset cluster length, and
+      // go to next pair
+      ClusterLength = 2;
+      continue;
+    }
+
+    SUnit *SUa = MemOpa.SU;
+    SUnit *SUb = MemOpb.SU;
+
+    // FIXME: Is this check really required?
+    if (!DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) {
+      ClusterLength = 2;
+      continue;
+    }
+
+
+      LLVM_DEBUG(dbgs() << "  Copy Succ SU(" << Succ.getSUnit()->NodeNum
+                        << ")\n");
+
   }
 }
 
 /// Callback from DAG postProcessing to create cluster edges for loads.
 void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs *DAG) {
   // Map DAG NodeNum to a set of dependent MemOps in store chain.
   DenseMap<unsigned, SmallVector<SUnit *, 4>> StoreChains;
   for (SUnit &SU : DAG->SUnits) {

llvm/lib/Target/AMDGPU/SIInstrInfo.h

enum BranchPredicate {
     SCC_FALSE = -1,
     VCCNZ = 2,
     VCCZ = -2,
     EXECNZ = -3,
     EXECZ = 3
   };
 
   using SetVectorType = SmallSetVector<MachineInstr *, 32>;
+  mutable unsigned NumClusteredBytes = 0;
 
   static unsigned getBranchOpcode(BranchPredicate Cond);
   static BranchPredicate getBranchPredicate(unsigned Opcode);
 
 public:
   unsigned buildExtractSubReg(MachineBasicBlock::iterator MI,
                               MachineRegisterInfo &MRI,
                               MachineOperand &SuperReg,
private:
   const TargetRegisterClass *
   getDestEquivalentVGPRClass(const MachineInstr &Inst) const;
 
   bool checkInstOffsetsDoNotOverlap(const MachineInstr &MIa,
                                     const MachineInstr &MIb) const;
 
   Register findUsedSGPR(const MachineInstr &MI, int OpIndices[3]) const;
 
+  void computeNumClusteredBytes(const MachineInstr &FirstLdSt,
+                                const MachineOperand *FirstDst,
+                                const MachineOperand *SecondDst,
+                                const unsigned NumLoads) const;
+
 protected:
   bool swapSourceModifiers(MachineInstr &MI,
                            MachineOperand &Src0, unsigned Src0OpName,
                            MachineOperand &Src1, unsigned Src1OpName) const;
 
   MachineInstr *commuteInstructionImpl(MachineInstr &MI, bool NewMI,
                                        unsigned OpIdx0,
                                        unsigned OpIdx1) const override;

llvm/lib/Target/AMDGPU/SIInstrInfo.cpp

static bool memOpsHaveSameBasePtr(const MachineInstr &MI1,
   Base2 = GetUnderlyingObject(Base2, DL);
 
   if (isa<UndefValue>(Base1) || isa<UndefValue>(Base2))
     return false;
 
   return Base1 == Base2;
 }
 
+void SIInstrInfo::computeNumClusteredBytes(const MachineInstr &FirstLdSt,
+                                           const MachineOperand *FirstDst,
+                                           const MachineOperand *SecondDst,
+                                           const unsigned NumLoads) const {
+  const MachineRegisterInfo &MRI =
+      FirstLdSt.getParent()->getParent()->getRegInfo();
+
+  const Register FirstDstReg = FirstDst->getReg();
+  const Register SecondDstReg = SecondDst->getReg();
+
+  const TargetRegisterClass *FirstDstRC =
+      Register::isVirtualRegister(FirstDstReg)
+          ? MRI.getRegClass(FirstDstReg)
+          : RI.getPhysRegClass(FirstDstReg);
+  const TargetRegisterClass *SecondDstRC =
+      Register::isVirtualRegister(SecondDstReg)
+          ? MRI.getRegClass(SecondDstReg)
+          : RI.getPhysRegClass(SecondDstReg);
+
+  const unsigned FirstNumDestBytes = RI.getRegSizeInBits(*FirstDstRC) / 8;
+  const unsigned SecondNumDestBytes = RI.getRegSizeInBits(*SecondDstRC) / 8;
+
+  NumClusteredBytes = (NumLoads == 2)
+                          ? (FirstNumDestBytes + SecondNumDestBytes)
+                          : (NumClusteredBytes + SecondNumDestBytes);
+}
+
 bool SIInstrInfo::shouldClusterMemOps(ArrayRef<const MachineOperand *> BaseOps1,
                                       ArrayRef<const MachineOperand *> BaseOps2,
                                       unsigned NumLoads) const {
   assert(!BaseOps1.empty() && !BaseOps2.empty());
   const MachineInstr &FirstLdSt = *BaseOps1.front()->getParent();
   const MachineInstr &SecondLdSt = *BaseOps2.front()->getParent();
 
   if (!memOpsHaveSameBasePtr(FirstLdSt, BaseOps1, SecondLdSt, BaseOps2))
bool SIInstrInfo::shouldClusterMemOps(ArrayRef<const MachineOperand *> BaseOps1,
   } else if (isDS(FirstLdSt) && isDS(SecondLdSt)) {
     FirstDst = getNamedOperand(FirstLdSt, AMDGPU::OpName::vdst);
     SecondDst = getNamedOperand(SecondLdSt, AMDGPU::OpName::vdst);
   }
 
   if (!FirstDst || !SecondDst)
     return false;
 
-  // Try to limit clustering based on the total number of bytes loaded
-  // rather than the number of instructions.  This is done to help reduce
-  // register pressure.  The method used is somewhat inexact, though,
-  // because it assumes that all loads in the cluster will load the
-  // same number of bytes as FirstLdSt.
-
-  // The unit of this value is bytes.
-  // FIXME: This needs finer tuning.
-  unsigned LoadClusterThreshold = 16;
-
-  const MachineRegisterInfo &MRI =
-      FirstLdSt.getParent()->getParent()->getRegInfo();
-
-  const Register Reg = FirstDst->getReg();
-
-  const TargetRegisterClass *DstRC = Register::isVirtualRegister(Reg)
-                                         ? MRI.getRegClass(Reg)
-                                         : RI.getPhysRegClass(Reg);
-
-  // FIXME: NumLoads should not be subtracted 1. This is to match behavior
-  // of clusterNeighboringMemOps which was previosly passing cluster length
-  // less 1. LoadClusterThreshold should be tuned instead.
-  return ((NumLoads - 1) * (RI.getRegSizeInBits(*DstRC) / 8)) <=
-         LoadClusterThreshold;
+  // Try to limit clustering based on the total number of clustred bytes loaded
+  // rather than the number of clustered instructions.
+  unsigned MaxNumClusteredBytes = 16;
+  computeNumClusteredBytes(FirstLdSt, FirstDst, SecondDst, NumLoads);
+  return (NumClusteredBytes <= MaxNumClusteredBytes);
 }
 
 // FIXME: This behaves strangely. If, for example, you have 32 load + stores,
 // the first 16 loads will be interleaved with the stores, and the next 16 will
 // be clustered as expected. It should really split into 2 16 store batches.
 //
 // Loads are clustered until this returns false, rather than trying to schedule
 // groups of stores. This also means we have to deal with saying different