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

struct SISchedulerCandidate {
 
   bool isRepeat(SIScheduleCandReason R) { return RepeatReasonSet & (1 << R); }
   void setRepeat(SIScheduleCandReason R) { RepeatReasonSet |= (1 << R); }
 };
 
 class SIScheduleDAGMI;
 class SIScheduleBlockCreator;
 
+enum SIScheduleBlockLinkKind {
+  NoData,
+  Data
+};
+
 class SIScheduleBlock {
   SIScheduleDAGMI *DAG;
   SIScheduleBlockCreator *BC;
 
   std::vector<SUnit*> SUnits;
   std::map<unsigned, unsigned> NodeNum2Index;
   std::vector<SUnit*> TopReadySUs;
   std::vector<SUnit*> ScheduledSUnits;
class SIScheduleBlock {
   bool HighLatencyBlock = false;
 
   std::vector<unsigned> HasLowLatencyNonWaitedParent;
 
   // Unique ID, the index of the Block in the SIScheduleDAGMI Blocks table.
   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*, SIScheduleBlockLinkKind>> Succs;
   unsigned NumHighLatencySuccessors = 0;
 
 public:
   SIScheduleBlock(SIScheduleDAGMI *DAG, SIScheduleBlockCreator *BC,
                   unsigned ID):
     DAG(DAG), BC(BC), TopRPTracker(TopPressure), ID(ID) {}
 
   ~SIScheduleBlock() = default;
 
   unsigned getID() const { return ID; }
 
   /// Functions for Block construction.
   void addUnit(SUnit *SU);
 
   // When all SUs have been added.
   void finalizeUnits();
 
   // Add block pred, which has instruction predecessor of SU.
   void addPred(SIScheduleBlock *Pred);
-  void addSucc(SIScheduleBlock *Succ);
+  void addSucc(SIScheduleBlock *Succ, SIScheduleBlockLinkKind Kind);
 
   const std::vector<SIScheduleBlock*>& getPreds() const { return Preds; }
-  const std::vector<SIScheduleBlock*>& getSuccs() const { return Succs; }
+  ArrayRef<std::pair<SIScheduleBlock*, 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
 
   unsigned getNumHighLatencySuccessors() const {
     return NumHighLatencySuccessors;
   }
 

lib/Target/AMDGPU/SIMachineScheduler.cpp

void SIScheduleBlock::addPred(SIScheduleBlock *Pred) {
 
   // Check if not already predecessor.
   for (SIScheduleBlock* P : Preds) {
     if (PredID == P->getID())
       return;
   }
   Preds.push_back(Pred);
 
   assert(none_of(Succs,
-                 [=](SIScheduleBlock *S) { return PredID == S->getID(); }) &&
+                 [=](std::pair<SIScheduleBlock*,
+                     SIScheduleBlockLinkKind> S) {
+                   return PredID == S.first->getID();
+                    }) &&
          "Loop in the Block Graph!");
 }
 
-void SIScheduleBlock::addSucc(SIScheduleBlock *Succ) {
+void SIScheduleBlock::addSucc(SIScheduleBlock *Succ,
+                              SIScheduleBlockLinkKind Kind) {
   unsigned SuccID = Succ->getID();
 
   // Check if not already predecessor.
-  for (SIScheduleBlock* S : Succs) {
-    if (SuccID == S->getID())
+  for (std::pair<SIScheduleBlock*, 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::make_pair(Succ, Kind));
+
   assert(none_of(Preds,
                  [=](SIScheduleBlock *P) { return SuccID == P->getID(); }) &&
          "Loop in the Block Graph!");
 }
 
 #ifndef NDEBUG
 void SIScheduleBlock::printDebug(bool full) {
   dbgs() << "Block (" << ID << ")\n";
   if (!full)
     return;
 
   dbgs() << "\nContains High Latency Instruction: "
          << HighLatencyBlock << '\n';
   dbgs() << "\nDepends On:\n";
   for (SIScheduleBlock* P : Preds) {
     P->printDebug(false);
   }
 
   dbgs() << "\nSuccessors:\n";
-  for (SIScheduleBlock* S : Succs) {
-    S->printDebug(false);
+  for (std::pair<SIScheduleBlock*, SIScheduleBlockLinkKind> S : Succs) {
+    if (S.second == SIScheduleBlockLinkKind::Data)
+      dbgs() << "(Data Dep) ";
+    S.first->printDebug(false);
   }
 
   if (Scheduled) {
     dbgs() << "LiveInPressure " << LiveInPressure[DAG->getSGPRSetID()] << ' '
            << LiveInPressure[DAG->getVGPRSetID()] << '\n';
     dbgs() << "LiveOutPressure " << LiveOutPressure[DAG->getSGPRSetID()] << ' '
            << LiveOutPressure[DAG->getVGPRSetID()] << "\n\n";
     dbgs() << "LiveIns:\n";
void SIScheduleBlockCreator::createBlocksForVariant(SISchedulerBlockCreatorVariant BlockVariant) {
   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
     SUnit *SU = &DAG->SUnits[i];
     int SUID = Node2CurrentBlock[i];
      for (SDep& SuccDep : SU->Succs) {
        SUnit *Succ = SuccDep.getSUnit();
       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();
       if (PredDep.isWeak() || Pred->NodeNum >= DAGSize)
         continue;
       if (Node2CurrentBlock[Pred->NodeNum] != SUID)
         CurrentBlocks[SUID]->addPred(CurrentBlocks[Node2CurrentBlock[Pred->NodeNum]]);
     }
void SIScheduleBlockCreator::fillStats() {
 
   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
     int BlockIndice = BottomUpIndex2Block[i];
     SIScheduleBlock *Block = CurrentBlocks[BlockIndice];
     if (Block->getSuccs().empty())
       Block->Height = 0;
     else {
       unsigned Height = 0;
-      for (SIScheduleBlock *Succ : Block->getSuccs()) {
-        if (Height < Succ->Height + 1)
-          Height = Succ->Height + 1;
-      }
+      for (const auto &Succ : Block->getSuccs())
+        Height = std::min(Height, Succ.first->Height + 1);
       Block->Height = Height;
     }
   }
 }
 
 // SIScheduleBlockScheduler //
 
 SIScheduleBlockScheduler::SIScheduleBlockScheduler(SIScheduleDAGMI *DAG,
                                                    SISchedulerBlockSchedulerVariant Variant,
assert (Pos != LiveRegs.end() && // Reg must be live.
                LiveRegsConsumers[Reg] >= 1);
     --LiveRegsConsumers[Reg];
     if (LiveRegsConsumers[Reg] == 0)
       LiveRegs.erase(Pos);
   }
 }
 
 void SIScheduleBlockScheduler::releaseBlockSuccs(SIScheduleBlock *Parent) {
-  for (SIScheduleBlock* Block : Parent->getSuccs()) {
-    --BlockNumPredsLeft[Block->getID()];
-    if (BlockNumPredsLeft[Block->getID()] == 0) {
-      ReadyBlocks.push_back(Block);
-    }
-    // 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;
+  for (const auto &Block : Parent->getSuccs()) {
+    if (--BlockNumPredsLeft[Block.first->getID()] == 0)
+      ReadyBlocks.push_back(Block.first);
+
+    if (Parent->isHighLatencyBlock() &&
+        Block.second == SIScheduleBlockLinkKind::Data)
+      LastPosHighLatencyParentScheduled[Block.first->getID()] = NumBlockScheduled;
   }
 }
 
 void SIScheduleBlockScheduler::blockScheduled(SIScheduleBlock *Block) {
   decreaseLiveRegs(Block, Block->getInRegs());
   addLiveRegs(Block->getOutRegs());
   releaseBlockSuccs(Block);
   for (std::map<unsigned, unsigned>::iterator RegI =