[AMDGPU] Update the mechanism used to check for cycles and add eges in power-sched mutation

[jrbyrnes]

Summary

Update the checking and adding of edges in power-sched dag mutation. Previously, the methods used the Preds and Succs of SUnits to determine whether or not adding an edge was feasible. An example issue of this is that the Preds and Succs vectors may not contain artificial edges added from previous DAG mutations. By using methods in the DAG to check for and add edges, we can be sure to not create cycles. Note: power-sched is now off by default in trunk, this patch is needed for cherry picking.

[kerbowa]

Can you add a test with the bug?

[jrbyrnes]

Include test which which minimally reproduces the SmallVector error reported.

[kerbowa]

llvm/test/CodeGen/AMDGPU/power-sched-no-cycle.mir

3

Remove debug-only lines and add enable-power-sched.

[jrbyrnes]

Address review comments.

Additionally, add some quick checks to potentially avoid calls to DAG->canAddEdge() / handle edge case where ExitSU is treated as predecessor in DAG->canAddEdge()

[kerbowa]

Didn't this land?

[jrbyrnes]

In D129667#4104416, @kerbowa wrote:

Didn't this land?

Thanks -- landed via https://github.com/llvm/llvm-project/commit/8a12f20ef7732ebad2a91417f577f1af0c470765

llvm/lib/Target/AMDGPU/AMDGPUSubtarget.cpp

bool isSALU(const SUnit *SU) const {
     return MI && TII->isSALU(*MI) && !MI->isTerminator();
   }
 
   bool isVALU(const SUnit *SU) const {
     const MachineInstr *MI = SU->getInstr();
     return MI && TII->isVALU(*MI);
   }
 
-  bool canAddEdge(const SUnit *Succ, const SUnit *Pred) const {
-    if (Pred->NodeNum < Succ->NodeNum)
-      return true;
-
-    SmallVector<const SUnit*, 64> Succs({Succ}), Preds({Pred});
-
-    for (unsigned I = 0; I < Succs.size(); ++I) {
-      for (const SDep &SI : Succs[I]->Succs) {
-        const SUnit *SU = SI.getSUnit();
-        if (SU != Succs[I] && !llvm::is_contained(Succs, SU))
-          Succs.push_back(SU);
-      }
-    }
-
-    SmallPtrSet<const SUnit*, 32> Visited;
-    while (!Preds.empty()) {
-      const SUnit *SU = Preds.pop_back_val();
-      if (llvm::is_contained(Succs, SU))
-        return false;
-      Visited.insert(SU);
-      for (const SDep &SI : SU->Preds)
-        if (SI.getSUnit() != SU && !Visited.count(SI.getSUnit()))
-          Preds.push_back(SI.getSUnit());
-    }
-
-    return true;
-  }
-
   // Link as many SALU instructions in chain as possible. Return the size
   // of the chain. Links up to MaxChain instructions.
   unsigned linkSALUChain(SUnit *From, SUnit *To, unsigned MaxChain,
                          SmallPtrSetImpl<SUnit *> &Visited) const {
     SmallVector<SUnit *, 8> Worklist({To});
     unsigned Linked = 0;
 
     while (!Worklist.empty() && MaxChain-- > 0) {
       SUnit *SU = Worklist.pop_back_val();
       if (!Visited.insert(SU).second)
         continue;
 
       LLVM_DEBUG(dbgs() << "Inserting edge from\n" ; DAG->dumpNode(*From);
                  dbgs() << "to\n"; DAG->dumpNode(*SU); dbgs() << '\n');
 
-      if (SU->addPred(SDep(From, SDep::Artificial), false))
+      if (SU != From && From != &DAG->ExitSU && DAG->canAddEdge(SU, From))
+        if (DAG->addEdge(SU, SDep(From, SDep::Artificial)))
           ++Linked;
 
       for (SDep &SI : From->Succs) {
         SUnit *SUv = SI.getSUnit();
-        if (SUv != From && isVALU(SUv) && canAddEdge(SUv, SU))
-          SUv->addPred(SDep(SU, SDep::Artificial), false);
+        if (SUv != From && SU != &DAG->ExitSU && isVALU(SUv) &&
+            DAG->canAddEdge(SUv, SU))
+          DAG->addEdge(SUv, SDep(SU, SDep::Artificial));
       }
 
       for (SDep &SI : SU->Succs) {
         SUnit *Succ = SI.getSUnit();
-        if (Succ != SU && isSALU(Succ) && canAddEdge(From, Succ))
+        if (Succ != SU && isSALU(Succ))
           Worklist.push_back(Succ);
       }
     }
 
     return Linked;
   }
 
   void apply(ScheduleDAGInstrs *DAGInstrs) override {
for (SUnit &SU : DAG->SUnits) {
                         << " instructions to cover latency.\n");
 
       // Find up to Lat independent scalar instructions as early as
       // possible such that they can be scheduled after this MFMA.
       for ( ; Lat && LastSALU != E; ++LastSALU) {
         if (Visited.count(&*LastSALU))
           continue;
 
-        if (!isSALU(&*LastSALU) || !canAddEdge(&*LastSALU, &SU))
+        if (&SU == &DAG->ExitSU || &SU == &*LastSALU || !isSALU(&*LastSALU) ||
+            !DAG->canAddEdge(&*LastSALU, &SU))
           continue;
 
         Lat -= linkSALUChain(&SU, &*LastSALU, Lat, Visited);
       }
     }
   }
 };
 } // namespace

llvm/test/CodeGen/AMDGPU/power-sched-no-cycle.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -march=amdgcn -mcpu=gfx90a -run-pass=postmisched %s -o - -amdgpu-enable-power-sched=true  2>&1 | FileCheck %s
+# This test represents a pattern which caused power-sched to introduce cycles into the Scheduling graph. By virtue of this test not crashing indicates it has completed succesfully.
+
+---
+name:            power_sched_cycle_condition
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $vgpr1, $sgpr2_sgpr3, $sgpr1, $vgpr72_vgpr73, $vgpr2_vgpr3, $sgpr22, $sgpr6_sgpr7, $sgpr10_sgpr11
+    ; CHECK-LABEL: name: power_sched_cycle_condition
+    ; CHECK: liveins: $vgpr1, $sgpr2_sgpr3, $sgpr1, $vgpr72_vgpr73, $vgpr2_vgpr3, $sgpr22, $sgpr6_sgpr7, $sgpr10_sgpr11
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: $sgpr1 = S_LOAD_DWORD_IMM $sgpr2_sgpr3, 56, 0 :: (dereferenceable invariant load (s64), addrspace 4)
+    ; CHECK-NEXT: $sgpr4 = S_LSHL_B32 killed $sgpr22, 1, implicit-def dead $scc
+    ; CHECK-NEXT: $sgpr22_sgpr23 = S_LOAD_DWORDX2_IMM killed $sgpr2_sgpr3, 36, 0 :: (dereferenceable invariant load (s64), addrspace 4)
+    ; CHECK-NEXT: $vgpr2 = nsw V_MUL_LO_U32_e64 killed $vgpr1, killed $sgpr1, implicit $exec
+    ; CHECK-NEXT: early-clobber $vgpr6_vgpr7_vgpr8_vgpr9_vgpr10_vgpr11_vgpr12_vgpr13_vgpr14_vgpr15_vgpr16_vgpr17_vgpr18_vgpr19_vgpr20_vgpr21 = V_MFMA_F32_32X32X8F16_vgprcd_e64 killed $vgpr2_vgpr3, $vgpr72_vgpr73, 0, 0, 0, 0, implicit $mode, implicit $exec
+    $sgpr1 = S_LOAD_DWORD_IMM $sgpr2_sgpr3, 56, 0 :: (dereferenceable invariant load (s64), addrspace 4)
+    $vgpr2 = nsw V_MUL_LO_U32_e64 $vgpr1, $sgpr1, implicit $exec
+    $vgpr6_vgpr7_vgpr8_vgpr9_vgpr10_vgpr11_vgpr12_vgpr13_vgpr14_vgpr15_vgpr16_vgpr17_vgpr18_vgpr19_vgpr20_vgpr21 =  V_MFMA_F32_32X32X8F16_vgprcd_e64 $vgpr2_vgpr3, $vgpr72_vgpr73, 0, 0, 0, 0, implicit $mode, implicit $exec
+    $sgpr4 = S_LSHL_B32 $sgpr22, 1, implicit-def dead $scc
+    $sgpr22_sgpr23 = S_LOAD_DWORDX2_IMM $sgpr2_sgpr3, 36, 0 :: (dereferenceable invariant load (s64), addrspace 4)
+...
+
+