[MCA][Scheduler] Use latency information to further classify busy instructions.

[andreadb]

Summary

This patch introduces a new instruction stage named 'IS_WAITING'.
An instruction transitions from the IS_DISPATCHED to the IS_WAITING stage if the latency of all input register operands are known.

This patch also adds a new set of instructions named 'PendingSet' to class Scheduler. The idea is that the PendingSet will only contain instructions that have reached the IS_WAITING stage.
By construction, an instruction in the PendingSet is only dependent on instructions that have already reached the execution stage. The plan is to use this knowledge to identify bottlenecks caused by data dependencies (see PR37494).

[mattd]

LGTM. I had a few suggestions but nothing looks wrong to me.

lib/MCA/HardwareUnits/Scheduler.cpp

99

Suggestion: if (HasDependentUsers && promoteToPendingSet()) ...

143

Suggestion: s/RemovedElements/PromotedElements/

[RKSimon]

include/llvm/MCA/HardwareUnits/Scheduler.h

98

If possible it'd be useful to comment these sets and explain their relationship to the Instruction::InstrStage enum values

[courbet]

lib/MCA/Instruction.cpp

161

the capture is no longer needed.

[andreadb]

include/llvm/MCA/HardwareUnits/Scheduler.h

98

Sure. I will add a comment.

lib/MCA/Instruction.cpp

161

Nice catch. I will fix it. Thanks

[andreadb]

Addressed review comments.

For consistency, I renamed instruction stage IS_WAITING to IS_PENDING.

[RKSimon]

LGTM with a couple of minors

include/llvm/MCA/Instruction.h

458

IS_PENDING

lib/MCA/Instruction.cpp

163

As discussed offline please consistently embed/separate all the lambdas and the all_of calls.

include/llvm/MCA/HardwareUnits/Scheduler.h

class Scheduler : public HardwareUnit {
 
   // Instruction selection strategy for this Scheduler.
   std::unique_ptr<SchedulerStrategy> Strategy;
 
   // Hardware resources that are managed by this scheduler.
   std::unique_ptr<ResourceManager> Resources;
 
   std::vector<InstRef> WaitSet;
+  std::vector<InstRef> PendingSet;
   std::vector<InstRef> ReadySet;
   std::vector<InstRef> IssuedSet;
 
   // A mask of busy resource units. It defaults to the empty set (i.e. a zero
   // mask), and it is cleared at the beginning of every cycle.
   // It is updated every time the scheduler fails to issue an instruction from
   // the ready set due to unavailable pipeline resources.
   // Each bit of the mask represents an unavailable resource.
   uint64_t BusyResourceUnits;
 
   /// Verify the given selection strategy and set the Strategy member
   /// accordingly.  If no strategy is provided, the DefaultSchedulerStrategy is
   /// used.
   void initializeStrategy(std::unique_ptr<SchedulerStrategy> S);
 
   /// Issue an instruction without updating the ready queue.
   void issueInstructionImpl(
       InstRef &IR,
       SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes);
 
   // Identify instructions that have finished executing, and remove them from
   // the IssuedSet. References to executed instructions are added to input
   // vector 'Executed'.
   void updateIssuedSet(SmallVectorImpl<InstRef> &Executed);
 
-  // Try to promote instructions from WaitSet to ReadySet.
+  // Try to promote instructions from PendingSet to ReadySet.
   // Add promoted instructions to the 'Ready' vector in input.
-  void promoteToReadySet(SmallVectorImpl<InstRef> &Ready);
+  bool promoteToReadySet(SmallVectorImpl<InstRef> &Ready);
+
+  // Try to promote instructions from WaitSet to PendingSet.
+  // Returns true if at least one instruction was promoted.
+  bool promoteToPendingSet();
 
 public:
   Scheduler(const MCSchedModel &Model, LSUnit &Lsu)
       : Scheduler(Model, Lsu, nullptr) {}
 
   Scheduler(const MCSchedModel &Model, LSUnit &Lsu,
             std::unique_ptr<SchedulerStrategy> SelectStrategy)
       : Scheduler(make_unique<ResourceManager>(Model), Lsu,

include/llvm/MCA/Instruction.h

unsigned getNumUsers() const {
     if (PartialWrite)
       ++NumUsers;
     return NumUsers;
   }
 
   bool clearsSuperRegisters() const { return ClearsSuperRegs; }
   bool isWriteZero() const { return WritesZero; }
   bool isEliminated() const { return IsEliminated; }
+
+  bool isReady() const {
+    if (getDependentWrite())
+      return false;
+    unsigned CyclesLeft = getDependentWriteCyclesLeft();
+    return !CyclesLeft || CyclesLeft < getLatency();
+  }
+
   bool isExecuted() const {
     return CyclesLeft != UNKNOWN_CYCLES && CyclesLeft <= 0;
   }
 
   const WriteState *getDependentWrite() const { return DependentWrite; }
   void setDependentWrite(WriteState *Other) { DependentWrite = Other; }
   void writeStartEvent(unsigned Cycles) {
     DependentWriteCyclesLeft = Cycles;
ReadState(const ReadDescriptor &Desc, unsigned RegID)
         CyclesLeft(UNKNOWN_CYCLES), TotalCycles(0), IsReady(true),
         IsZero(false), IndependentFromDef(false) {}
 
   const ReadDescriptor &getDescriptor() const { return *RD; }
   unsigned getSchedClass() const { return RD->SchedClassID; }
   unsigned getRegisterID() const { return RegisterID; }
   unsigned getRegisterFileID() const { return PRFID; }
 
+  bool isWaiting() const { return !IndependentFromDef && CyclesLeft > 0; }
   bool isReady() const { return IsReady; }
   bool isImplicitRead() const { return RD->isImplicitRead(); }
 
   bool isIndependentFromDef() const { return IndependentFromDef; }
   void setIndependentFromDef() { IndependentFromDef = true; }
 
   void cycleEvent();
   void writeStartEvent(unsigned Cycles);

 /// An instruction propagated through the simulated instruction pipeline.
 ///
 /// This class is used to monitor changes to the internal state of instructions
 /// that are sent to the various components of the simulated hardware pipeline.
 class Instruction : public InstructionBase {
   enum InstrStage {
     IS_INVALID,    // Instruction in an invalid state.
     IS_DISPATCHED, // Instruction dispatched but operands are not ready.
+    IS_WAITING,    // Instruction is not ready, but operand latency is known.
     IS_READY,      // Instruction dispatched and operands ready.
     IS_EXECUTING,  // Instruction issued.
     IS_EXECUTED,   // Instruction executed. Values are written back.
     IS_RETIRED     // Instruction retired.
   };
 
   // The current instruction stage.
   enum InstrStage Stage;
public:
   // instruction. The RCUToken is used to track the completion of every
   // register write performed by this instruction.
   void dispatch(unsigned RCUTokenID);
 
   // Instruction issued. Transition to the IS_EXECUTING state, and update
   // all the definitions.
   void execute();
 
-  // Force a transition from the IS_DISPATCHED state to the IS_READY state if
-  // input operands are all ready. State transitions normally occur at the
-  // beginning of a new cycle (see method cycleEvent()). However, the scheduler
-  // may decide to promote instructions from the wait queue to the ready queue
-  // as the result of another issue event.  This method is called every time the
-  // instruction might have changed in state.
+  // Force a transition from the IS_DISPATCHED state to the IS_READY or
+  // IS_WAITING state. State transitions normally occur either at the beginning
+  // of a new cycle (see method cycleEvent()), or as a result of another issue
+  // event. This method is called every time the instruction might have changed
+  // in state. It internally delegates to method updateDispatched() and
+  // updateWaiting().
   void update();
+  bool updateDispatched();
+  bool updateWaiting();
 
   bool isDispatched() const { return Stage == IS_DISPATCHED; }
+  bool isWaiting() const { return Stage == IS_WAITING; }
   bool isReady() const { return Stage == IS_READY; }
   bool isExecuting() const { return Stage == IS_EXECUTING; }
   bool isExecuted() const { return Stage == IS_EXECUTED; }
   bool isRetired() const { return Stage == IS_RETIRED; }
 
   bool isEliminated() const {
     return isReady() && getDefs().size() &&
            all_of(getDefs(),

lib/MCA/HardwareUnits/Scheduler.cpp

void Scheduler::issueInstruction(
   bool HasDependentUsers = Inst.hasDependentUsers();
 
   Resources->releaseBuffers(Inst.getDesc().Buffers);
   issueInstructionImpl(IR, UsedResources);
   // Instructions that have been issued during this cycle might have unblocked
   // other dependent instructions. Dependent instructions may be issued during
   // this same cycle if operands have ReadAdvance entries.  Promote those
   // instructions to the ReadySet and notify the caller that those are ready.
   if (HasDependentUsers)
+    if (promoteToPendingSet())
       promoteToReadySet(ReadyInstructions);
 }
 
-void Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
+bool Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
   // Scan the set of waiting instructions and promote them to the
-  // ready queue if operands are all ready.
+  // ready set if operands are all ready.
   unsigned RemovedElements = 0;
-  for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
+  for (auto I = PendingSet.begin(), E = PendingSet.end(); I != E;) {
     InstRef &IR = *I;
     if (!IR)
       break;
 
     // Check if this instruction is now ready. In case, force
     // a transition in state using method 'update()'.
     Instruction &IS = *IR.getInstruction();
     if (!IS.isReady())
-      IS.update();
+      IS.updateWaiting();
 
     // Check if there are still unsolved data dependencies.
     if (!isReady(IR)) {
       ++I;
       continue;
     }
 
+    LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
+                      << " promoted to the READY set.\n");
+
     Ready.emplace_back(IR);
     ReadySet.emplace_back(IR);
 
     IR.invalidate();
     ++RemovedElements;
     std::iter_swap(I, E - RemovedElements);
   }
 
+  PendingSet.resize(PendingSet.size() - RemovedElements);
+  return RemovedElements;
+}
+
+bool Scheduler::promoteToPendingSet() {
+  // Scan the set of waiting instructions and promote them to the
+  // pending set if operands are all ready.
+  unsigned RemovedElements = 0;
+  for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
+    InstRef &IR = *I;
+    if (!IR)
+      break;
+
+    // Check if this instruction is now ready. In case, force
+    // a transition in state using method 'update()'.
+    Instruction &IS = *IR.getInstruction();
+    if (IS.isDispatched() && !IS.updateDispatched()) {
+      ++I;
+      continue;
+    }
+    LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
+                      << " promoted to the PENDING set.\n");
+
+    PendingSet.emplace_back(IR);
+
+    IR.invalidate();
+    ++RemovedElements;
+    std::iter_swap(I, E - RemovedElements);
+  }
+
   WaitSet.resize(WaitSet.size() - RemovedElements);
+  return RemovedElements;
 }
 
 InstRef Scheduler::select() {
   unsigned QueueIndex = ReadySet.size();
   for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
     const InstRef &IR = ReadySet[I];
     if (QueueIndex == ReadySet.size() ||
         Strategy->compare(IR, ReadySet[QueueIndex])) {
void Scheduler::cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
   Resources->cycleEvent(Freed);
 
   // Propagate the cycle event to the 'Issued' and 'Wait' sets.
   for (InstRef &IR : IssuedSet)
     IR.getInstruction()->cycleEvent();
 
   updateIssuedSet(Executed);
 
+  for (InstRef &IR : PendingSet)
+    IR.getInstruction()->cycleEvent();
+
   for (InstRef &IR : WaitSet)
     IR.getInstruction()->cycleEvent();
 
+  promoteToPendingSet();
   promoteToReadySet(Ready);
 
   BusyResourceUnits = 0;
 }
 
 bool Scheduler::mustIssueImmediately(const InstRef &IR) const {
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
   if (Desc.isZeroLatency())
     return true;
   // Instructions that use an in-order dispatch/issue processor resource must be
   // issued immediately to the pipeline(s). Any other in-order buffered
   // resources (i.e. BufferSize=1) is consumed.
   return Desc.MustIssueImmediately;
 }
 
 void Scheduler::dispatch(const InstRef &IR) {
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
   Resources->reserveBuffers(Desc.Buffers);
 
   // If necessary, reserve queue entries in the load-store unit (LSU).
   bool IsMemOp = Desc.MayLoad || Desc.MayStore;
   if (IsMemOp)
     LSU.dispatch(IR);
 
+  if (IR.getInstruction()->isWaiting()) {
+    LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR
+                      << " to the PendingSet\n");
+    PendingSet.push_back(IR);
+    return;
+  }
+
   if (!isReady(IR)) {
     LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
     WaitSet.push_back(IR);
     return;
   }
 
   // Don't add a zero-latency instruction to the Ready queue.
   // A zero-latency instruction doesn't consume any scheduler resources. That is

lib/MCA/Instruction.cpp

 }
 
 void Instruction::forceExecuted() {
   assert(Stage == IS_READY && "Invalid internal state!");
   CyclesLeft = 0;
   Stage = IS_EXECUTED;
 }
 
-void Instruction::update() {
-  assert(isDispatched() && "Unexpected instruction stage found!");
+bool Instruction::updateWaiting() {
+  assert(isWaiting() && "Unexpected instruction stage found!");
 
   if (!all_of(getUses(), [](const ReadState &Use) { return Use.isReady(); }))
-    return;
+    return false;
 
   // A partial register write cannot complete before a dependent write.
-  auto IsDefReady = [&](const WriteState &Def) {
-    if (!Def.getDependentWrite()) {
-      unsigned CyclesLeft = Def.getDependentWriteCyclesLeft();
-      return !CyclesLeft || CyclesLeft < getLatency();
-    }
+  auto IsDefReady = [&](const WriteState &Def) { return Def.isReady(); };
+
+  if (!all_of(getDefs(), IsDefReady))
+    return false;
+
+  Stage = IS_READY;
+  return true;
+
+bool Instruction::updateDispatched() {
+  assert(isDispatched() && "Unexpected instruction stage found!");
+
+  if (!all_of(getUses(), [](const ReadState &Use) {
+        return Use.isWaiting() || Use.isReady();
+      }))
     return false;
+
+  // A partial register write cannot complete before a dependent write.
+  auto IsDefWaitingOrReady = [&](const WriteState &Def) {
+    return !Def.getDependentWrite();
   };
 
-  if (all_of(getDefs(), IsDefReady))
-    Stage = IS_READY;
+  if (!all_of(getDefs(), IsDefWaitingOrReady))
+    return false;
+
+  Stage = IS_WAITING;
+  return true;
+}
+
+void Instruction::update() {
+  if (isDispatched())
+    updateDispatched();
+  if (isWaiting())
+    updateWaiting();
 }
 
 void Instruction::cycleEvent() {
   if (isReady())
     return;
 
-  if (isDispatched()) {
+  if (isDispatched() || isWaiting()) {
     for (ReadState &Use : getUses())
       Use.cycleEvent();
 
     for (WriteState &Def : getDefs())
       Def.cycleEvent();
 
     update();
     return;