AMDGPU/SI: Detect dependency types between blocks

[axeldavy]

Summary

Detecting the type of dependencies between blocks
enables better handling of high latencies, as
order dependencies can be differentiated from
data dependencies (in the former you don't need
to insert a wait, whereas you need in the latter).

[arsenm]

lib/Target/AMDGPU/SIMachineScheduler.cpp

541–544

Factor into predicate function and assert on that condition

562–563

std::make_pair

586

Debug printing not guarded by DEBUG. Looks like this problem existed already, so this whole block should be under DEBUG

lib/Target/AMDGPU/SIMachineScheduler.h

101

Don't need enum keyword

124

Return ArrayRef

[axeldavy]

lib/Target/AMDGPU/SIMachineScheduler.cpp

586

It is in a function printDebug, protected by #ifndef NDEBUG

[axeldavy]

rebased.

[vpykhtin]

lib/Target/AMDGPU/SIMachineScheduler.cpp

586

Please provide full context diff next time (-U9999999), it helps to avoid such misunderstandings.

Better to use const reference to &S here.

1365

const auto &Succ

1367

In genereal please don't duplicate expressions. Compilers are good in CSE, but my eyes aren't :-)

This can be rewritten as Height = std::min(Height, Succ.first->Height + 1)

1650

const auto &Block

1653

if (--BlockNumPredsLeft[Block.first->getID()] == 0)

[axeldavy]

Updated according to comments

[vpykhtin]

LGTM.

lib/Target/AMDGPU/SIMachineScheduler.h

 class SIScheduleDAGMI;
 class SIScheduleBlockCreator;
 
+enum SIScheduleBlockLinkKind {
+  NoData,
+  Data
+};
+
 class SIScheduleBlock {
   SIScheduleDAGMI *DAG;
   SIScheduleBlockCreator *BC;

   unsigned ID;
 
   std::vector<SIScheduleBlock*> Preds;  // All blocks predecessors.
-  std::vector<SIScheduleBlock*> Succs;  // All blocks successors.
+  // All blocks successors, and the kind of link
+  std::vector<std::pair<SIScheduleBlock*, enum SIScheduleBlockLinkKind>> Succs;
   unsigned NumHighLatencySuccessors = 0;
 
 public:

 
   // Add block pred, which has instruction predecessor of SU.
   void addPred(SIScheduleBlock *Pred);
-  void addSucc(SIScheduleBlock *Succ);
+  void addSucc(SIScheduleBlock *Succ, enum SIScheduleBlockLinkKind Kind);
 
   const std::vector<SIScheduleBlock*>& getPreds() const { return Preds; }
-  const std::vector<SIScheduleBlock*>& getSuccs() const { return Succs; }
+  const std::vector<std::pair<SIScheduleBlock*, enum SIScheduleBlockLinkKind>>&
+    getSuccs() const { return Succs; }
 
   unsigned Height;  // Maximum topdown path length to block without outputs
   unsigned Depth;   // Maximum bottomup path length to block without inputs

lib/Target/AMDGPU/SIMachineScheduler.cpp

   }
   Preds.push_back(Pred);
 
-  assert(none_of(Succs,
-                 [=](SIScheduleBlock *S) { return PredID == S->getID(); }) &&
-         "Loop in the Block Graph!");
+  for (std::pair<SIScheduleBlock*, enum SIScheduleBlockLinkKind> S : Succs) {
+    if (PredID == S.first->getID())
+       assert(!"Loop in the Block Graph!\n");
+  }
 }
 
-void SIScheduleBlock::addSucc(SIScheduleBlock *Succ) {
+void SIScheduleBlock::addSucc(SIScheduleBlock *Succ,
+                              enum SIScheduleBlockLinkKind Kind) {
   unsigned SuccID = Succ->getID();
 
   // Check if not already predecessor.
-  for (SIScheduleBlock* S : Succs) {
-    if (SuccID == S->getID())
+  for (std::pair<SIScheduleBlock*, enum SIScheduleBlockLinkKind> &S : Succs) {
+    if (SuccID == S.first->getID()) {
+      if (S.second == SIScheduleBlockLinkKind::NoData &&
+          Kind == SIScheduleBlockLinkKind::Data)
+        S.second = Kind;
       return;
+    }
   }
   if (Succ->isHighLatencyBlock())
     ++NumHighLatencySuccessors;
-  Succs.push_back(Succ);
+  Succs.push_back(std::pair<SIScheduleBlock*,
+                  enum SIScheduleBlockLinkKind> (Succ, Kind));
+
   assert(none_of(Preds,
                  [=](SIScheduleBlock *P) { return SuccID == P->getID(); }) &&
          "Loop in the Block Graph!");

   }
 
   dbgs() << "\nSuccessors:\n";
-  for (SIScheduleBlock* S : Succs) {
-    S->printDebug(false);
+  for (std::pair<SIScheduleBlock*, enum SIScheduleBlockLinkKind> S : Succs) {
+    if (S.second == SIScheduleBlockLinkKind::Data)
+      dbgs() << "(Data Dep) ";
+    S.first->printDebug(false);
   }
 
   if (Scheduled) {

       if (SuccDep.isWeak() || Succ->NodeNum >= DAGSize)
         continue;
       if (Node2CurrentBlock[Succ->NodeNum] != SUID)
-        CurrentBlocks[SUID]->addSucc(CurrentBlocks[Node2CurrentBlock[Succ->NodeNum]]);
+        CurrentBlocks[SUID]->addSucc(CurrentBlocks[Node2CurrentBlock[Succ->NodeNum]],
+                                     SuccDep.isCtrl() ? NoData : Data);
     }
     for (SDep& PredDep : SU->Preds) {
       SUnit *Pred = PredDep.getSUnit();

       Block->Height = 0;
     else {
       unsigned Height = 0;
-      for (SIScheduleBlock *Succ : Block->getSuccs()) {
-        if (Height < Succ->Height + 1)
-          Height = Succ->Height + 1;
+      for (std::pair<SIScheduleBlock*, enum SIScheduleBlockLinkKind> Succ :
+             Block->getSuccs()) {
+        if (Height < Succ.first->Height + 1)
+          Height = Succ.first->Height + 1;
       }
       Block->Height = Height;
     }

 }
 
 void SIScheduleBlockScheduler::releaseBlockSuccs(SIScheduleBlock *Parent) {
-  for (SIScheduleBlock* Block : Parent->getSuccs()) {
-    --BlockNumPredsLeft[Block->getID()];
-    if (BlockNumPredsLeft[Block->getID()] == 0) {
-      ReadyBlocks.push_back(Block);
+  for (std::pair<SIScheduleBlock*, enum SIScheduleBlockLinkKind> Block :
+         Parent->getSuccs()) {
+    --BlockNumPredsLeft[Block.first->getID()];
+    if (BlockNumPredsLeft[Block.first->getID()] == 0) {
+      ReadyBlocks.push_back(Block.first);
     }
-    // TODO: Improve check. When the dependency between the high latency
-    // instructions and the instructions of the other blocks are WAR or WAW
-    // there will be no wait triggered. We would like these cases to not
-    // update LastPosHighLatencyParentScheduled.
-    if (Parent->isHighLatencyBlock())
-      LastPosHighLatencyParentScheduled[Block->getID()] = NumBlockScheduled;
+
+    if (Parent->isHighLatencyBlock() &&
+        Block.second == SIScheduleBlockLinkKind::Data)
+      LastPosHighLatencyParentScheduled[Block.first->getID()] = NumBlockScheduled;
   }
 }
 

         BlockInfo.ProducedRegisters.insert(RegIdentifier);
       }
 
-      for (SIScheduleBlock *Child : Block->getSuccs()) {
-        --BlockNumPredsLeftCurrent[Child->getID()];
-        if (BlockNumPredsLeftCurrent[Child->getID()] == 0) {
-          SchedulableBlockNextDepth.push_back(Child);
+      for (std::pair<SIScheduleBlock*, enum SIScheduleBlockLinkKind> Child :
+             Block->getSuccs()) {
+        --BlockNumPredsLeftCurrent[Child.first->getID()];
+        if (BlockNumPredsLeftCurrent[Child.first->getID()] == 0) {
+          SchedulableBlockNextDepth.push_back(Child.first);
         }
       }