[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 ↗

(On Diff #186285)

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

143 ↗

(On Diff #186285)

Suggestion: s/RemovedElements/PromotedElements/

[RKSimon]

include/llvm/MCA/HardwareUnits/Scheduler.h

98 ↗

(On Diff #186285)

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 ↗

(On Diff #186285)

the capture is no longer needed.

[andreadb]

include/llvm/MCA/HardwareUnits/Scheduler.h

98 ↗

(On Diff #186285)

Sure. I will add a comment.

lib/MCA/Instruction.cpp

161 ↗

(On Diff #186285)

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 ↗

(On Diff #186442)

IS_PENDING

lib/MCA/Instruction.cpp

163 ↗

(On Diff #186442)

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

llvm/trunk/include/llvm/MCA/HardwareUnits/Scheduler.h

 
 /// Class Scheduler is responsible for issuing instructions to pipeline
 /// resources.
 ///
 /// Internally, it delegates to a ResourceManager the management of processor
 /// resources. This class is also responsible for tracking the progress of
 /// instructions from the dispatch stage, until the write-back stage.
 ///
-/// An instruction dispatched to the Scheduler is initially placed into either
-/// the 'WaitSet' or the 'ReadySet' depending on the availability of the input
-/// operands.
-///
-/// An instruction is moved from the WaitSet to the ReadySet when register
-/// operands become available, and all memory dependencies are met.
-/// Instructions that are moved from the WaitSet to the ReadySet transition
-/// in state from 'IS_DISPATCHED' to 'IS_READY'.
-///
-/// On every cycle, the Scheduler checks if it can promote instructions from the
-/// WaitSet to the ReadySet.
-///
-/// An Instruction is moved from the ReadySet the `IssuedSet` when it is issued
-/// to a (one or more) pipeline(s). This event also causes an instruction state
-/// transition (i.e. from state IS_READY, to state IS_EXECUTING). An Instruction
-/// leaves the IssuedSet when it reaches the write-back stage.
 class Scheduler : public HardwareUnit {
   LSUnit &LSU;
 
   // Instruction selection strategy for this Scheduler.
   std::unique_ptr<SchedulerStrategy> Strategy;
 
   // Hardware resources that are managed by this scheduler.
   std::unique_ptr<ResourceManager> Resources;
 
+  // Instructions dispatched to the Scheduler are internally classified based on
+  // the instruction stage (see Instruction::InstrStage).
+  //
+  // An Instruction dispatched to the Scheduler is added to the WaitSet if not
+  // all its register operands are available, and at least one latency is unknown.
+  // By construction, the WaitSet only contains instructions that are in the
+  // IS_DISPATCHED stage.
+  //
+  // An Instruction transitions from the WaitSet to the PendingSet if the
+  // instruction is not ready yet, but the latency of every register read is known.
+  // Instructions in the PendingSet are expected to be in the IS_PENDING stage.
+  //
+  // Instructions in the PendingSet are immediately dominated only by
+  // instructions that have already been issued to the underlying pipelines.
+  // In the presence of bottlenecks caused by data dependencies, the PendingSet
+  // can be inspected to identify problematic data dependencies between
+  // instructions.
+  //
+  // An instruction is moved to the ReadySet when all register operands become
+  // available, and all memory dependencies are met.  Instructions that are
+  // moved from the PendingSet to the ReadySet transition in state from
+  // 'IS_PENDING' to 'IS_READY'.
+  //
+  // On every cycle, the Scheduler checks if it can promote instructions from the
+  // PendingSet to the ReadySet.
+  //
+  // An Instruction is moved from the ReadySet to the `IssuedSet` when it starts
+  // exection. This event also causes an instruction state transition (i.e. from
+  // state IS_READY, to state IS_EXECUTING). An Instruction leaves the IssuedSet
+  // only when it reaches the write-back stage.
   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.
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 the PendingSet to the ReadySet.
   // Add promoted instructions to the 'Ready' vector in input.
-  void promoteToReadySet(SmallVectorImpl<InstRef> &Ready);
+  // Returns true if at least one instruction was promoted.
+  bool promoteToReadySet(SmallVectorImpl<InstRef> &Ready);
+
+  // Try to promote instructions from the WaitSet to the 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,

llvm/trunk/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 isPending() 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_PENDING,    // 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_PENDING 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 updatePending();
 
   bool isDispatched() const { return Stage == IS_DISPATCHED; }
+  bool isPending() const { return Stage == IS_PENDING; }
   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(),

llvm/trunk/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 (HasDependentUsers && 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.
-  unsigned RemovedElements = 0;
-  for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
+  // ready set if operands are all ready.
+  unsigned PromotedElements = 0;
+  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.updatePending();
 
     // 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();
+    ++PromotedElements;
+    std::iter_swap(I, E - PromotedElements);
+  }
+
+  PendingSet.resize(PendingSet.size() - PromotedElements);
+  return PromotedElements;
+}
+
+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()->isPending()) {
+    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

llvm/trunk/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::updatePending() {
+  assert(isPending() && "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();
-    }
+  if (!all_of(getDefs(), [](const WriteState &Def) { return Def.isReady(); }))
     return false;
-  };
 
-  if (all_of(getDefs(), IsDefReady))
-    Stage = IS_READY;
+  return true;
+}
+
+bool Instruction::updateDispatched() {
+  assert(isDispatched() && "Unexpected instruction stage found!");
+
+  if (!all_of(getUses(), [](const ReadState &Use) {
+        return Use.isPending() || Use.isReady();
+      }))
+    return false;
+
+  // A partial register write cannot complete before a dependent write.
+  if (!all_of(getDefs(),
+              [](const WriteState &Def) { return !Def.getDependentWrite(); }))
+    return false;
+
+  Stage = IS_PENDING;
+  return true;
+}
+
+void Instruction::update() {
+  if (isDispatched())
+    updateDispatched();
+  if (isPending())
+    updatePending();
 }
 
 void Instruction::cycleEvent() {
   if (isReady())
     return;
 
-  if (isDispatched()) {
+  if (isDispatched() || isPending()) {
     for (ReadState &Use : getUses())
       Use.cycleEvent();
 
     for (WriteState &Def : getDefs())
       Def.cycleEvent();
 
     update();
     return;