[Scheduling] Fall back to the fast cluster algorithm if the DAG is too complex

[steven.zhang]

Summary

We have added a new load/store cluster algorithm in D85517. However, AArch64 see some compiling deg with the new algorithm as the IsReachable() is not cheap if the DAG is complex. O(M+N) See https://bugs.llvm.org/show_bug.cgi?id=47966

So, this patch added a heuristic to switch to old cluster algorithm if the DAG is too complex. For now, I used the heuristic value 5M for NumOfStores * NumOfSUnits. This is a rough threshold as I don't see compiling time impact with it. Welcome for more comments.

The case in https://bugs.llvm.org/show_bug.cgi?id=47966 is that, we have ~10000 LdSt and ~15000 SUnits in one region, which blow up the compiling time.

[resistor]

Did the concept of using the static DAG not work?

llvm/lib/CodeGen/MachineScheduler.cpp

1586

s/be/been/

1587

"they don't have dependencies on each other"

1708

This threshold happens to work for the testcase in question, but my gut tells me that the threshold should be substantially lower than this. It might make sense to generate some artificial test cases and measure how big of a cluster is needed to make compile time explode.

[steven.zhang]

Address comments.

Did the concept of using the static DAG not work?

If we want to close the gap with old algorithm, we have to have the O(1) query algorithm, which requires O(M^2) space and some time effort to construct the index. This is a known graph problem and I have no good idea. The scheduling DAG has property that seldom removing the edges but keeping adding edges. Do you have any good idea to improve the IsReachable() which will also benefit the compiling time of scheduler ?

Regarding to the threshold, I did a test with your case by removing the stores to reduce the DAG. This is the data.

LdSt Num: 794, DAG Size: 1191, 794 x 1191 = 945654 
new algorithm: 0.53s
old algorithm: 0.34s

They are completely the same when it is:

LdSt Num: 669, DAG Size: 1015, 669 x 1015 = 679035 
new algorithm: 0.39s
old algorithm: 0.41s

The time complexity for this algorithm is: O(M*(N+E)) if I understand correctly. M is the number of the load/store, and N is the number of the SUnits and E is the number of edges. For now, I choose the 1000000 as threshold as it seems not deg too much. Is it ok ?

llvm/lib/CodeGen/MachineScheduler.cpp

static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden,
   cl::desc("Enable register pressure scheduling."), cl::init(true));
 
 static cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden,
   cl::desc("Enable cyclic critical path analysis."), cl::init(true));
 
 static cl::opt<bool> EnableMemOpCluster("misched-cluster", cl::Hidden,
                                         cl::desc("Enable memop clustering."),
                                         cl::init(true));
+static cl::opt<bool>
+    ForceFastCluster("force-fast-cluster", cl::Hidden,
+                     cl::desc("Switch to fast cluster algorithm with the lost "
+                              "of some fusion opportunities"),
+                     cl::init(false));
+static cl::opt<unsigned>
+    FastClusterThreshold("fast-cluster-threshold", cl::Hidden,
+                         cl::desc("The threshold for fast cluster"),
+                         cl::init(5));
 
 // DAG subtrees must have at least this many nodes.
 static const unsigned MinSubtreeSize = 8;
 
 // Pin the vtables to this file.
 void MachineSchedStrategy::anchor() {}
 
 void ScheduleDAGMutation::anchor() {}

 public:
   BaseMemOpClusterMutation(const TargetInstrInfo *tii,
                            const TargetRegisterInfo *tri, bool IsLoad)
       : TII(tii), TRI(tri), IsLoad(IsLoad) {}
 
   void apply(ScheduleDAGInstrs *DAGInstrs) override;
 
 protected:
-  void clusterNeighboringMemOps(ArrayRef<MemOpInfo> MemOps,
+  void clusterNeighboringMemOps(ArrayRef<MemOpInfo> MemOps, bool FastCluster,
                                 ScheduleDAGInstrs *DAG);
   void collectMemOpRecords(std::vector<SUnit> &SUnits,
                            SmallVectorImpl<MemOpInfo> &MemOpRecords);
+  bool GroupMemOps(ArrayRef<MemOpInfo> MemOps, ScheduleDAGInstrs *DAG,
+                   DenseMap<unsigned, SmallVector<MemOpInfo, 32>> &Groups);
 };
 
 class StoreClusterMutation : public BaseMemOpClusterMutation {
 public:
   StoreClusterMutation(const TargetInstrInfo *tii,
                        const TargetRegisterInfo *tri)
       : BaseMemOpClusterMutation(tii, tri, false) {}
 };
return EnableMemOpCluster ? std::make_unique<StoreClusterMutation>(TII, TRI)
                             : nullptr;
 }
 
 } // end namespace llvm
 
 // Sorting all the loads/stores first, then for each load/store, checking the
 // following load/store one by one, until reach the first non-dependent one and
 // call target hook to see if they can cluster.
+// If FastCluster is enabled, we assume that, all the loads/stores have be
+// preprocessed and now, they didn't have dependency with each other.
 void BaseMemOpClusterMutation::clusterNeighboringMemOps(
-    ArrayRef<MemOpInfo> MemOpRecords, ScheduleDAGInstrs *DAG) {
+    ArrayRef<MemOpInfo> MemOpRecords, bool FastCluster,
+    ScheduleDAGInstrs *DAG) {
   // Keep track of the current cluster length and bytes for each SUnit.
   DenseMap<unsigned, std::pair<unsigned, unsigned>> SUnit2ClusterInfo;
 
   // At this point, `MemOpRecords` array must hold atleast two mem ops. Try to
   // cluster mem ops collected within `MemOpRecords` array.
   for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {
     // Decision to cluster mem ops is taken based on target dependent logic
     auto MemOpa = MemOpRecords[Idx];
 
     // Seek for the next load/store to do the cluster.
     unsigned NextIdx = Idx + 1;
     for (; NextIdx < End; ++NextIdx)
       // Skip if MemOpb has been clustered already or has dependency with
       // MemOpa.
       if (!SUnit2ClusterInfo.count(MemOpRecords[NextIdx].SU->NodeNum) &&
-          !DAG->IsReachable(MemOpRecords[NextIdx].SU, MemOpa.SU) &&
-          !DAG->IsReachable(MemOpa.SU, MemOpRecords[NextIdx].SU))
+          (FastCluster ||
+           (!DAG->IsReachable(MemOpRecords[NextIdx].SU, MemOpa.SU) &&
+            !DAG->IsReachable(MemOpa.SU, MemOpRecords[NextIdx].SU))))
         break;
     if (NextIdx == End)
       continue;
 
     auto MemOpb = MemOpRecords[NextIdx];
     unsigned ClusterLength = 2;
     unsigned CurrentClusterBytes = MemOpa.Width + MemOpb.Width;
     if (SUnit2ClusterInfo.count(MemOpa.SU->NodeNum)) {
for (auto &SU : SUnits) {
     }
 #ifndef NDEBUG
     for (auto *Op : BaseOps)
       assert(Op);
 #endif
   }
 }
 
+bool BaseMemOpClusterMutation::GroupMemOps(
+    ArrayRef<MemOpInfo> MemOps, ScheduleDAGInstrs *DAG,
+    DenseMap<unsigned, SmallVector<MemOpInfo, 32>> &Groups) {
+  bool FastCluster =
+      ForceFastCluster ||
+      MemOps.size() * DAG->SUnits.size() / 1000000 > FastClusterThreshold;
+  for (auto &MemOp : MemOps) {
+    unsigned ChainPredID = DAG->SUnits.size();
+    if (FastCluster) {
+      for (const SDep &Pred : MemOp.SU->Preds) {
+        // We only want to cluster the mem ops that have the same ctrl(non-data)
+        // pred so that they didn't have ctrl dependency for each other. But for
+        // store instrs, we can still cluster them if the pred is load instr.
+        if ((Pred.isCtrl() &&
+             (IsLoad ||
+              (Pred.getSUnit() && Pred.getSUnit()->getInstr()->mayStore()))) &&
+            !Pred.isArtificial()) {
+          ChainPredID = Pred.getSUnit()->NodeNum;
+          break;
+        }
+      }
+    } else
+      ChainPredID = 0;
+
+    Groups[ChainPredID].push_back(MemOp);
+  }
+  return FastCluster;
+}
+
 /// Callback from DAG postProcessing to create cluster edges for loads/stores.
 void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs *DAG) {
   // Collect all the clusterable loads/stores
   SmallVector<MemOpInfo, 32> MemOpRecords;
   collectMemOpRecords(DAG->SUnits, MemOpRecords);
 
   if (MemOpRecords.size() < 2)
     return;
 
+  // Put the loads/stores without dependency into the same group with some
+  // heuristic if the DAG is too complex to avoid compiling time blow up.
+  // Notice that, some fusion pair could be lost with this.
+  DenseMap<unsigned, SmallVector<MemOpInfo, 32>> Groups;
+  bool FastCluster = GroupMemOps(MemOpRecords, DAG, Groups);
+
+  for (auto &Group : Groups) {
     // Sorting the loads/stores, so that, we can stop the cluster as early as
     // possible.
-  llvm::sort(MemOpRecords);
+    llvm::sort(Group.second);
 
     // Trying to cluster all the neighboring loads/stores.
-  clusterNeighboringMemOps(MemOpRecords, DAG);
+    clusterNeighboringMemOps(Group.second, FastCluster, DAG);
+  }
 }
 
 //===----------------------------------------------------------------------===//
 // CopyConstrain - DAG post-processing to encourage copy elimination.
 //===----------------------------------------------------------------------===//
 
 namespace {
 

llvm/test/CodeGen/AArch64/aarch64-stp-cluster.ll

 ; REQUIRES: asserts
 ; RUN: llc < %s -mtriple=arm64-linux-gnu -mcpu=cortex-a57 -verify-misched -debug-only=machine-scheduler -aarch64-enable-stp-suppress=false -o - 2>&1 > /dev/null | FileCheck %s
+; RUN: llc < %s -mtriple=arm64-linux-gnu -mcpu=cortex-a57 -force-fast-cluster -verify-misched -debug-only=machine-scheduler -aarch64-enable-stp-suppress=false -o - 2>&1 > /dev/null | FileCheck %s --check-prefix=CHECK-FAST
 
 ; CHECK: ********** MI Scheduling **********
 ; CHECK-LABEL: stp_i64_scale:%bb.0
 ; CHECK:Cluster ld/st SU(3) - SU(4)
 ; CHECK:Cluster ld/st SU(2) - SU(5)
 ; CHECK:SU(4):   STRXui %1:gpr64, %0:gpr64common, 1
 ; CHECK:SU(3):   STRXui %1:gpr64, %0:gpr64common, 2
 ; CHECK:SU(2):   STRXui %1:gpr64, %0:gpr64common, 3

 ; CHECK:SU(3):   STRWui %2:gpr32, %0:gpr64common, 0 ::
 ; CHECK:SU(4):   %3:gpr32 = LDRWui %1:gpr64common, 0 ::
 ; CHECK:Predecessors:
 ; CHECK: SU(3): Ord  Latency=1 Memory
 ; CHECK:SU(6):   STRBBui %4:gpr32, %1:gpr64common, 4 ::
 ; CHECK:SU(7):   %5:gpr32 = LDRWui %1:gpr64common, 1 ::
 ; CHECK:Predecessors:
 ; CHECK:SU(6): Ord  Latency=1 Memory
+; CHECK-FAST: cluster_with_different_preds:%bb.0
+; CHECK-FAST-NOT: Cluster ld/st
+; CHECK-FAST:SU(3):   STRWui %2:gpr32, %0:gpr64common, 0 ::
+; CHECK-FAST:SU(4):   %3:gpr32 = LDRWui %1:gpr64common, 0 ::
 define i32 @cluster_with_different_preds(i32* %p, i32* %q) {
 entry:
   store i32 3, i32* %p, align 4
   %0 = load i32, i32* %q, align 4
   %add.ptr = getelementptr inbounds i32, i32* %q, i64 1
   %1 = bitcast i32* %add.ptr to i8*
   store i8 5, i8* %1, align 1
   %2 = load i32, i32* %add.ptr, align 4
   %add = add nsw i32 %2, %0
   ret i32 %add
 }