[llvm-mca] Introduce the ExecuteStage (was originally the Scheduler class).

[mattd]

Summary

This patch transforms the Scheduler class into the ExecuteStage. Most of the logic remains.

[courbet]

tools/llvm-mca/Backend.cpp

48

How do you intend to make this independent of the actual type of the Stages in the long term (when we have a vector<std::unique_ptr<Stage>> instead of Dispatch and Execute) ?
Would it make sense to use Stage::isReady() ?

[andreadb]

Hi Matt,

I am not convinced that it is a good idea to convert the Scheduler into a Stage.
I think the "execute stage" should just use/interact with the hardware schedulers to orchestrate the execution.
The statge would be also responsible for notifying events to listeners.

[andreadb]

What I am trying to say is that the stage should only be responsible for the process (i.e. orchestrating the execution).
The logic that lives in Scheduler::cycleEvent() is essentially where the "process" logic is implemented. That logic (plus the event notification logic) should be moved to the stage class. The rest of the logic should still be part of the Scheduler class. Basically, the stage is only where we control the execution. It helps decoupling the actual feature from the process (i.e. how we use the feature/interact with the hardware components).

[mattd]

This is an updated patch that maintains the logic of the Scheduler, but decoupling the hardware component from the execution component.
The ExecuteStage drives the Scheduler and provides the notification functionality.

• Scheduler::cycleEvent is now ExecuteStage::preExecute
• Scheduler::scheduleInstruction is now ExecuteStage::execute
• Scheduler::canBeDispatched now returns a HWStallEvent (or NoStall) instead of a bool. We might want to rename this routine to something more appropriate, it makes more sense to name the routine something that does not imply a boolean return value. I left the name the same for this patch.
• The Backend pointer (Owner) in ExecuteStage will eventually go away once we register the listeners to the stages.

[andreadb]

Hi Matt

thanks for the patch. Sorry for the late review; it took me a while to go through all of its parts (I was not expecting so many changes).
I have a few nits (see my comments below):

tools/llvm-mca/ExecuteStage.cpp

30

Something like a small paragraph with a brief overview of the sequence of steps performed by this method would really help. I know that it was missing in the original implementation. However, I think it really helps a lot if we add a small description here.

Some steps could be moved to a separate function. That might help with making the code more readable (if we choose good names for functions).

78

Please add a small comment here.

tools/llvm-mca/HWEventListener.h

106–107

See my other comment.

tools/llvm-mca/Scheduler.cpp

235–236

Could you change this method so that it returns a bool? I don't particularly like the fact that , as a consequence of this change, we now need a new value in the GenericEventType enum.
You can make the enum an in/out argument to this method. If canBeDispatched returns false, then the HWStallEvent::GenericEventType contains the reason why dispatch failed.

tools/llvm-mca/Scheduler.h

462

Emphasize that this method is meant to be called when a new cycle starts.
Also, add a small sentence to better describe the semantic of this method.

497–499

You can reuse the previous NDEBUG block. I think you should remove the #endif at line 497 instead of opening a new block.

[mattd]

tools/llvm-mca/Scheduler.cpp

235–236

Sounds good! Alternatively, we could make canBeDispatched return Optional<HWStallEvent::GenericEventType>, but I'm happy with an in/out in this case, simple enough.

[mattd]

Thanks for the review @andreadb! I updated this based on your suggestions.

[andreadb]

LGTM.

Thanks Matt!

tools/llvm-mca/Backend.h

 /// This file implements an OoO backend for the llvm-mca tool.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_MCA_BACKEND_H
 #define LLVM_TOOLS_LLVM_MCA_BACKEND_H
 
 #include "DispatchStage.h"
+#include "ExecuteStage.h"
 #include "FetchStage.h"
 #include "InstrBuilder.h"
-#include "Scheduler.h"
 
 namespace mca {
 
 class HWEventListener;
 class HWInstructionEvent;
 class HWStallEvent;
 
 /// An out of order backend for a specific subtarget.

 /// Internally, the Backend collects statistical information in the form of
 /// histograms. For example, it tracks how the dispatch group size changes
 /// over time.
 class Backend {
   /// This is the initial stage of the pipeline.
   /// TODO: Eventually this will become a list of unique Stage* that this
   /// backend pipeline executes.
   std::unique_ptr<FetchStage> Fetch;
-  std::unique_ptr<Scheduler> HWS;
   std::unique_ptr<DispatchStage> Dispatch;
+  std::unique_ptr<ExecuteStage> Execute;
   std::set<HWEventListener *> Listeners;
   unsigned Cycles;
 
   void runCycle(unsigned Cycle);
 
 public:
   Backend(const llvm::MCSubtargetInfo &Subtarget,
           const llvm::MCRegisterInfo &MRI,
           std::unique_ptr<FetchStage> InitialStage, unsigned DispatchWidth = 0,
           unsigned RegisterFileSize = 0, unsigned LoadQueueSize = 0,
           unsigned StoreQueueSize = 0, bool AssumeNoAlias = false)
       : Fetch(std::move(InitialStage)),
-        HWS(llvm::make_unique<Scheduler>(this, Subtarget.getSchedModel(),
+        Dispatch(llvm::make_unique<DispatchStage>(
+            this, Subtarget, MRI, RegisterFileSize, DispatchWidth)),
+        Execute(llvm::make_unique<ExecuteStage>(this, Subtarget.getSchedModel(),
                                                 LoadQueueSize, StoreQueueSize,
                                                 AssumeNoAlias)),
-        Dispatch(llvm::make_unique<DispatchStage>(
-            this, Subtarget, MRI, RegisterFileSize, DispatchWidth, HWS.get())),
         Cycles(0) {
-    HWS->setDispatchStage(Dispatch.get());
+    Execute->setDispatchStage(Dispatch.get());
   }
 
   void run();
   void addEventListener(HWEventListener *Listener);
   void notifyCycleBegin(unsigned Cycle);
   void notifyInstructionEvent(const HWInstructionEvent &Event);
   void notifyStallEvent(const HWStallEvent &Event);
   void notifyResourceAvailable(const ResourceRef &RR);
   void notifyReservedBuffers(llvm::ArrayRef<unsigned> Buffers);
   void notifyReleasedBuffers(llvm::ArrayRef<unsigned> Buffers);
   void notifyCycleEnd(unsigned Cycle);
 };
 } // namespace mca
 
 #endif

tools/llvm-mca/Backend.cpp

while (Fetch->isReady() || !Dispatch->isReady())
     runCycle(Cycles++);
 }
 
 void Backend::runCycle(unsigned Cycle) {
   notifyCycleBegin(Cycle);
 
   InstRef IR;
   Dispatch->preExecute(IR);
-  HWS->cycleEvent(); // TODO: This will eventually be stage-ified.
+  Execute->preExecute(IR);
 
   while (Fetch->execute(IR)) {
-    if (!Dispatch->execute(IR))
+    // Note that Execute::canBeDispatched must be attempted if
+    // Dispatch::canDispatch returns true.  Execute::canBeDispatched will
+    // notify of HW stalls.
+    if (!Dispatch->canDispatch(IR) || !Execute->canBeDispatched(IR))
       break;
+    Dispatch->execute(IR);
+    Execute->execute(IR);
     Fetch->postExecute(IR);
   }
 
   notifyCycleEnd(Cycle);
 }
 
 void Backend::notifyCycleBegin(unsigned Cycle) {
   LLVM_DEBUG(dbgs() << "[E] Cycle begin: " << Cycle << '\n');

tools/llvm-mca/CMakeLists.txt

set(LLVM_LINK_COMPONENTS
   )
 
 add_llvm_tool(llvm-mca
   Backend.cpp
   BackendPrinter.cpp
   CodeRegion.cpp
   DispatchStage.cpp
   DispatchStatistics.cpp
+  ExecuteStage.cpp
   FetchStage.cpp
   HWEventListener.cpp
   InstrBuilder.cpp
   Instruction.cpp
   InstructionInfoView.cpp
   InstructionTables.cpp
   LSUnit.cpp
   llvm-mca.cpp
   RegisterFile.cpp
   RegisterFileStatistics.cpp
   ResourcePressureView.cpp
   RetireControlUnit.cpp
   RetireControlUnitStatistics.cpp
-  Scheduler.cpp
   SchedulerStatistics.cpp
   Stage.cpp
   Support.cpp
   SummaryView.cpp
   TimelineView.cpp
   View.cpp
   )

tools/llvm-mca/DispatchStage.h

-//===----------------------- Dispatch.h -------------------------*- C++ -*-===//
+//===----------------------- DispatchStage.h --------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file

 #include "RetireControlUnit.h"
 #include "Stage.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/MC/MCSubtargetInfo.h"
 
 namespace mca {
 
 class WriteState;
-class Scheduler;
 class Backend;
 
 // Implements the hardware dispatch logic.
 //
 // This class is responsible for the dispatch stage, in which instructions are
-// dispatched in groups to the Scheduler.  An instruction can be dispatched if
-// functional units are available.
-// To be more specific, an instruction can be dispatched to the Scheduler if:
+// dispatched in groups to the ExecuteStage.  An instruction can be dispatched
+// if functional units are available.
+// To be more specific, an instruction can be dispatched to the ExecuteStage if:
 //  1) There are enough entries in the reorder buffer (implemented by class
 //     RetireControlUnit) to accommodate all opcodes.
 //  2) There are enough temporaries to rename output register operands.
 //  3) There are enough entries available in the used buffered resource(s).
 //
 // The number of micro opcodes that can be dispatched in one cycle is limited by
 // the value of field 'DispatchWidth'. A "dynamic dispatch stall" occurs when
 // processor resources are not available (i.e. at least one of the
 // aforementioned checks fails). Dispatch stall events are counted during the
 // entire execution of the code, and displayed by the performance report when
 // flag '-verbose' is specified.
 //
 // If the number of micro opcodes of an instruction is bigger than
 // DispatchWidth, then it can only be dispatched at the beginning of one cycle.
 // The DispatchStage will still have to wait for a number of cycles (depending
 // on the DispatchWidth and the number of micro opcodes) before it can serve
 // other instructions.
 class DispatchStage : public Stage {
   unsigned DispatchWidth;
   unsigned AvailableEntries;
   unsigned CarryOver;
-  Scheduler *SC;
   std::unique_ptr<RegisterFile> RAT;
   std::unique_ptr<RetireControlUnit> RCU;
   Backend *Owner;
   const llvm::MCSubtargetInfo &STI;
 
   bool checkRAT(const InstRef &IR);
   bool checkRCU(const InstRef &IR);
-  bool checkScheduler(const InstRef &IR);
   void dispatch(InstRef IR);
   bool isRCUEmpty() const { return RCU->isEmpty(); }
   void updateRAWDependencies(ReadState &RS, const llvm::MCSubtargetInfo &STI);
 
   void notifyInstructionDispatched(const InstRef &IR,
                                    llvm::ArrayRef<unsigned> UsedPhysRegs);
 
   bool isAvailable(unsigned NumEntries) const {
     return NumEntries <= AvailableEntries || AvailableEntries == DispatchWidth;
   }
 
-  bool canDispatch(const InstRef &IR) {
-    assert(isAvailable(IR.getInstruction()->getDesc().NumMicroOps));
-    return checkRCU(IR) && checkRAT(IR) && checkScheduler(IR);
-  }
-
   void collectWrites(llvm::SmallVectorImpl<WriteState *> &Vec,
                      unsigned RegID) const {
     return RAT->collectWrites(Vec, RegID);
   }
 
 public:
   DispatchStage(Backend *B, const llvm::MCSubtargetInfo &Subtarget,
                 const llvm::MCRegisterInfo &MRI, unsigned RegisterFileSize,
-                unsigned MaxDispatchWidth, Scheduler *Sched)
+                unsigned MaxDispatchWidth)
       : DispatchWidth(MaxDispatchWidth), AvailableEntries(MaxDispatchWidth),
-        CarryOver(0U), SC(Sched),
-        RAT(llvm::make_unique<RegisterFile>(Subtarget.getSchedModel(), MRI,
-                                            RegisterFileSize)),
+        CarryOver(0U), RAT(llvm::make_unique<RegisterFile>(
+                           Subtarget.getSchedModel(), MRI, RegisterFileSize)),
         RCU(llvm::make_unique<RetireControlUnit>(Subtarget.getSchedModel(),
                                                  this)),
         Owner(B), STI(Subtarget) {}
 
+  bool canDispatch(const InstRef &IR);
   virtual bool isReady() const override final { return isRCUEmpty(); }
   virtual void preExecute(const InstRef &IR) override final;
   virtual bool execute(InstRef &IR) override final;
   void notifyInstructionRetired(const InstRef &IR);
   void notifyDispatchStall(const InstRef &IR, unsigned EventType);
 
   void onInstructionExecuted(unsigned TokenID) {
     RCU->onInstructionExecuted(TokenID);

tools/llvm-mca/DispatchStage.cpp

-//===--------------------- Dispatch.cpp -------------------------*- C++ -*-===//
+//===--------------------- DispatchStage.cpp --------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// This file implements methods declared by the DispatchStage class.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "DispatchStage.h"
 #include "Backend.h"
 #include "HWEventListener.h"
-#include "Scheduler.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "llvm-mca"
 
 namespace mca {
 
bool DispatchStage::checkRCU(const InstRef &IR) {
   const unsigned NumMicroOps = IR.getInstruction()->getDesc().NumMicroOps;
   if (RCU->isAvailable(NumMicroOps))
     return true;
   Owner->notifyStallEvent(
       HWStallEvent(HWStallEvent::RetireControlUnitStall, IR));
   return false;
 }
 
-bool DispatchStage::checkScheduler(const InstRef &IR) {
-  return SC->canBeDispatched(IR);
-}
-
 void DispatchStage::updateRAWDependencies(ReadState &RS,
                                           const MCSubtargetInfo &STI) {
   SmallVector<WriteState *, 4> DependentWrites;
 
   collectWrites(DependentWrites, RS.getRegisterID());
   RS.setDependentWrites(DependentWrites.size());
   LLVM_DEBUG(dbgs() << "Found " << DependentWrites.size()
                     << " dependent writes\n");
for (std::unique_ptr<WriteState> &WS : IS.getDefs())
     RAT->addRegisterWrite(*WS, RegisterFiles, !Desc.isZeroLatency());
 
   // Reserve slots in the RCU, and notify the instruction that it has been
   // dispatched to the schedulers for execution.
   IS.dispatch(RCU->reserveSlot(IR, NumMicroOps));
 
   // Notify listeners of the "instruction dispatched" event.
   notifyInstructionDispatched(IR, RegisterFiles);
-
-  // Now move the instruction into the scheduler's queue.
-  // The scheduler is responsible for checking if this is a zero-latency
-  // instruction that doesn't consume pipeline/scheduler resources.
-  SC->scheduleInstruction(IR);
 }
 
 void DispatchStage::preExecute(const InstRef &IR) {
   RCU->cycleEvent();
   AvailableEntries = CarryOver >= DispatchWidth ? 0 : DispatchWidth - CarryOver;
   CarryOver = CarryOver >= DispatchWidth ? CarryOver - DispatchWidth : 0U;
 }
 
-bool DispatchStage::execute(InstRef &IR) {
+bool DispatchStage::canDispatch(const InstRef &IR) {
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
-  if (!isAvailable(Desc.NumMicroOps) || !canDispatch(IR))
+  if (!isAvailable(Desc.NumMicroOps) || !checkRCU(IR) || !checkRAT(IR))
     return false;
+  return true;
+}
+
+bool DispatchStage::execute(InstRef &IR) {
   dispatch(IR);
   return true;
 }
 
 #ifndef NDEBUG
 void DispatchStage::dump() const {
   RAT->dump();
   RCU->dump();
 }
 #endif
 } // namespace mca

tools/llvm-mca/ExecuteStage.h

-//===--------------------- Scheduler.h ------------------------*- C++ -*-===//
+//===------------------------- ExecuteStage.cpp -----------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// A scheduler for Processor Resource Units and Processor Resource Groups.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_MCA_SCHEDULER_H
 #define LLVM_TOOLS_LLVM_MCA_SCHEDULER_H
 
 #include "Instruction.h"
 #include "LSUnit.h"
+#include "Stage.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/MC/MCSubtargetInfo.h"
 #include <map>
 
 namespace mca {
 
 class Backend;
 class DispatchStage;

 
 // First: a MCProcResourceDesc index identifying a buffered resource.
 // Second: max number of buffer entries used in this resource.
 typedef std::pair<unsigned, unsigned> BufferUsageEntry;
 
 /// A resource manager for processor resource units and groups.
 ///
 /// This class owns all the ResourceState objects, and it is responsible for
-/// acting on requests from a Scheduler by updating the internal state of
+/// acting on requests from a ExecuteStage by updating the internal state of
 /// ResourceState objects.
 /// This class doesn't know about instruction itineraries and functional units.
 /// In future, it can be extended to support itineraries too through the same
 /// public interface.
 class ResourceManager {
   // The resource manager owns all the ResourceState.
   using UniqueResourceState = std::unique_ptr<ResourceState>;
   llvm::SmallDenseMap<uint64_t, UniqueResourceState> Resources;

 #ifndef NDEBUG
   void dump() const {
     for (const std::pair<uint64_t, UniqueResourceState> &Resource : Resources)
       Resource.second->dump();
   }
 #endif
 }; // namespace mca
 
-/// Class Scheduler is responsible for issuing instructions to pipeline
+/// Class ExecuteStage 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 nstruction dispatched to the Scheduler is initially placed into either
-/// the 'WaitQueue' or the 'ReadyQueue' depending on the availability of the
-/// input operands. Instructions in the WaitQueue are ordered by instruction
-/// index. An instruction is moved from the WaitQueue to the ReadyQueue when
-/// register operands become available, and all memory dependencies are met.
-/// Instructions that are moved from the WaitQueue to the ReadyQueue transition
-/// from state 'IS_AVAILABLE' to state 'IS_READY'.
+/// 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 ExecuteStage is initially placed into
+/// either the 'WaitQueue' or the 'ReadyQueue' depending on the availability
+/// of the input operands. Instructions in the WaitQueue are ordered by
+/// instruction index. An instruction is moved from the WaitQueue to the
+/// ReadyQueue when register operands become available, and all memory
+/// dependencies are met.  Instructions that are moved from the WaitQueue to
+/// the ReadyQueue transition from state 'IS_AVAILABLE' to state 'IS_READY'.
 ///
-/// At the beginning of each cycle, the Scheduler checks if there are
+/// At the beginning of each cycle, the ExecuteStage checks if there are
 /// instructions in the WaitQueue that can be moved to the ReadyQueue.  If the
 /// ReadyQueue is not empty, then older instructions from the queue are issued
 /// to the processor pipelines, and the underlying ResourceManager is updated
 /// accordingly.  The ReadyQueue is ordered by instruction index to guarantee
 /// that the first instructions in the set are also the oldest.
 ///
 /// An Instruction is moved from the ReadyQueue the `IssuedQueue` 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 IssuedQueue when it reaches the write-back stage.
-class Scheduler {
+class ExecuteStage : public Stage {
   const llvm::MCSchedModel &SM;
 
   // Hardware resources that are managed by this scheduler.
   std::unique_ptr<ResourceManager> Resources;
   std::unique_ptr<LSUnit> LSU;
 
   // The Backend gets notified when instructions are ready/issued/executed.
   Backend *const Owner;
class ExecuteStage : public Stage {
   void issueInstructionImpl(
       InstRef &IR,
       llvm::SmallVectorImpl<std::pair<ResourceRef, double>> &Pipes);
 
   void updatePendingQueue(llvm::SmallVectorImpl<InstRef> &Ready);
   void updateIssuedQueue(llvm::SmallVectorImpl<InstRef> &Executed);
 
 public:
-  Scheduler(Backend *B, const llvm::MCSchedModel &Model, unsigned LoadQueueSize,
-            unsigned StoreQueueSize, bool AssumeNoAlias)
-      : SM(Model), Resources(llvm::make_unique<ResourceManager>(SM)),
+  ExecuteStage(Backend *B, const llvm::MCSchedModel &Model,
+               unsigned LoadQueueSize, unsigned StoreQueueSize,
+               bool AssumeNoAlias)
+      : Stage(), SM(Model), Resources(llvm::make_unique<ResourceManager>(SM)),
         LSU(llvm::make_unique<LSUnit>(LoadQueueSize, StoreQueueSize,
                                       AssumeNoAlias)),
         Owner(B) {}
 
   void setDispatchStage(DispatchStage *DispStage) { DS = DispStage; }
 
   /// Check if the instruction in 'IR' can be dispatched.
   ///
-  /// The DispatchStage is responsible for querying the Scheduler before
+  /// The DispatchStage is responsible for querying the ExecuteStage before
   /// dispatching new instructions. Queries are performed through method
-  /// `Scheduler::canBeDispatched`. If scheduling resources are available,
+  /// `ExecuteStage::canBeDispatched`. If scheduling resources are available,
   /// and the instruction can be dispatched, then this method returns true.
   /// Otherwise, a generic HWStallEvent is notified to the listeners.
   bool canBeDispatched(const InstRef &IR) const;
   void scheduleInstruction(InstRef &IR);
 
   /// Issue an instruction.
   void issueInstruction(InstRef &IR);
 
   /// Reserve one entry in each buffered resource.
   void reserveBuffers(llvm::ArrayRef<uint64_t> Buffers) {
     Resources->reserveBuffers(Buffers);
   }
 
   /// Release buffer entries previously allocated by method reserveBuffers.
   void releaseBuffers(llvm::ArrayRef<uint64_t> Buffers) {
     Resources->releaseBuffers(Buffers);
   }
 
-  void cycleEvent();
+  virtual void preExecute(const InstRef &IR) override final;
+  virtual bool execute(InstRef &IR) override final;
 
 #ifndef NDEBUG
   void dump() const;
 #endif
 };
 } // Namespace mca
 
 #endif

tools/llvm-mca/ExecuteStage.cpp

-//===--------------------- Scheduler.cpp ------------------------*- C++ -*-===//
+//===------------------------- ExecuteStage.cpp -----------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // A scheduler for processor resource units and processor resource groups.
 //
 //===----------------------------------------------------------------------===//
 
-#include "Scheduler.h"
+#include "ExecuteStage.h"
 #include "Backend.h"
 #include "HWEventListener.h"
 #include "Support.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "llvm-mca"
 
 namespace mca {
 
 using namespace llvm;
 
 uint64_t ResourceState::selectNextInSequence() {
   assert(isReady());
   uint64_t Next = getNextInSequence();
   while (!isSubResourceReady(Next)) {
     updateNextInSequence();
     Next = getNextInSequence();
   }
   return Next;
 }
 
 #ifndef NDEBUG
 void ResourceState::dump() const {
std::pair<uint64_t, uint64_t> ResourceManager::selectPipe(uint64_t ResourceID) {
   return std::pair<uint64_t, uint64_t>(ResourceID, SubResourceID);
 }
 
 void ResourceState::removeFromNextInSequence(uint64_t ID) {
   assert(NextInSequenceMask);
   assert(countPopulation(ID) == 1);
   if (ID > getNextInSequence())
     RemovedFromNextInSequence |= ID;
   NextInSequenceMask = NextInSequenceMask & (~ID);
   if (!NextInSequenceMask) {
     NextInSequenceMask = ResourceSizeMask;
     assert(NextInSequenceMask != RemovedFromNextInSequence);
     NextInSequenceMask ^= RemovedFromNextInSequence;
     RemovedFromNextInSequence = 0;
   }
 }
 
if (!BR.second) {
       ResourcesFreed.push_back(RR);
     }
   }
 
   for (const ResourceRef &RF : ResourcesFreed)
     BusyResources.erase(RF);
 }
 
-void Scheduler::scheduleInstruction(InstRef &IR) {
+bool ExecuteStage::execute(InstRef &IR) {
   const unsigned Idx = IR.getSourceIndex();
   assert(WaitQueue.find(Idx) == WaitQueue.end());
   assert(ReadyQueue.find(Idx) == ReadyQueue.end());
   assert(IssuedQueue.find(Idx) == IssuedQueue.end());
 
   // Reserve a slot in each buffered resource. Also, mark units with
   // BufferSize=0 as reserved. Resources with a buffer size of zero will only
   // be released after MCIS is issued, and all the ResourceCycles for those
   // units have been consumed.
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
   reserveBuffers(Desc.Buffers);
   notifyReservedBuffers(Desc.Buffers);
 
   // If necessary, reserve queue entries in the load-store unit (LSU).
   bool Reserved = LSU->reserve(IR);
   if (!IR.getInstruction()->isReady() || (Reserved && !LSU->isReady(IR))) {
     LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding " << Idx
                       << " to the Wait Queue\n");
     WaitQueue[Idx] = IR.getInstruction();
-    return;
+    return false;
   }
   notifyInstructionReady(IR);
 
   // Don't add a zero-latency instruction to the Wait or Ready queue.
   // A zero-latency instruction doesn't consume any scheduler resources. That is
   // because it doesn't need to be executed, and it is often removed at register
   // renaming stage. For example, register-register moves are often optimized at
   // register renaming stage by simply updating register aliases. On some
   // targets, zero-idiom instructions (for example: a xor that clears the value
   // of a register) are treated speacially, and are often eliminated at register
   // renaming stage.
 
   // 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.
 
   if (!Desc.isZeroLatency() && !Resources->mustIssueImmediately(Desc)) {
     LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding " << IR
                       << " to the Ready Queue\n");
     ReadyQueue[IR.getSourceIndex()] = IR.getInstruction();
-    return;
+    return false;
   }
 
   LLVM_DEBUG(dbgs() << "[SCHEDULER] Instruction " << IR
                     << " issued immediately\n");
   // Release buffered resources and issue MCIS to the underlying pipelines.
   issueInstruction(IR);
+  return true;
 }
 
-void Scheduler::cycleEvent() {
+void ExecuteStage::preExecute(const InstRef &Unused) {
   SmallVector<ResourceRef, 8> ResourcesFreed;
   Resources->cycleEvent(ResourcesFreed);
 
   for (const ResourceRef &RR : ResourcesFreed)
     notifyResourceAvailable(RR);
 
   SmallVector<InstRef, 4> InstructionIDs;
   updateIssuedQueue(InstructionIDs);
while (IR.isValid()) {
     InstructionIDs.clear();
 
     // Select the next instruction to issue.
     IR = select();
   }
 }
 
 #ifndef NDEBUG
-void Scheduler::dump() const {
+void ExecuteStage::dump() const {
   dbgs() << "[SCHEDULER]: WaitQueue size is: " << WaitQueue.size() << '\n';
   dbgs() << "[SCHEDULER]: ReadyQueue size is: " << ReadyQueue.size() << '\n';
   dbgs() << "[SCHEDULER]: IssuedQueue size is: " << IssuedQueue.size() << '\n';
   Resources->dump();
 }
 #endif
 
-bool Scheduler::canBeDispatched(const InstRef &IR) const {
+bool ExecuteStage::canBeDispatched(const InstRef &IR) const {
   HWStallEvent::GenericEventType Type = HWStallEvent::Invalid;
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
 
   if (Desc.MayLoad && LSU->isLQFull())
     Type = HWStallEvent::LoadQueueFull;
   else if (Desc.MayStore && LSU->isSQFull())
     Type = HWStallEvent::StoreQueueFull;
   else {
     switch (Resources->canBeDispatched(Desc.Buffers)) {
     default:
       return true;
     case ResourceStateEvent::RS_BUFFER_UNAVAILABLE:
       Type = HWStallEvent::SchedulerQueueFull;
       break;
     case ResourceStateEvent::RS_RESERVED:
       Type = HWStallEvent::DispatchGroupStall;
     }
   }
 
   Owner->notifyStallEvent(HWStallEvent(Type, IR));
   return false;
 }
 
-void Scheduler::issueInstructionImpl(
+void ExecuteStage::issueInstructionImpl(
     InstRef &IR,
     SmallVectorImpl<std::pair<ResourceRef, double>> &UsedResources) {
   Instruction *IS = IR.getInstruction();
   const InstrDesc &D = IS->getDesc();
 
   // Issue the instruction and collect all the consumed resources
   // into a vector. That vector is then used to notify the listener.
   Resources->issueInstruction(D, UsedResources);
 
   // Notify the instruction that it started executing.
   // This updates the internal state of each write.
   IS->execute();
 
   if (IS->isExecuting())
     IssuedQueue[IR.getSourceIndex()] = IS;
 }
 
-void Scheduler::issueInstruction(InstRef &IR) {
+void ExecuteStage::issueInstruction(InstRef &IR) {
   // Release buffered resources.
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
   releaseBuffers(Desc.Buffers);
   notifyReleasedBuffers(Desc.Buffers);
 
   // Issue IS to the underlying pipelines and notify listeners.
   SmallVector<std::pair<ResourceRef, double>, 4> Pipes;
   issueInstructionImpl(IR, Pipes);
   notifyInstructionIssued(IR, Pipes);
   if (IR.getInstruction()->isExecuted())
     notifyInstructionExecuted(IR);
 }
 
-void Scheduler::promoteToReadyQueue(SmallVectorImpl<InstRef> &Ready) {
+void ExecuteStage::promoteToReadyQueue(SmallVectorImpl<InstRef> &Ready) {
   // Scan the set of waiting instructions and promote them to the
   // ready queue if operands are all ready.
   for (auto I = WaitQueue.begin(), E = WaitQueue.end(); I != E;) {
     const unsigned IID = I->first;
     Instruction *IS = I->second;
 
     // Check if this instruction is now ready. In case, force
     // a transition in state using method 'update()'.
for (auto I = WaitQueue.begin(), E = WaitQueue.end(); I != E;) {
     Ready.emplace_back(IID, IS);
     ReadyQueue[IID] = IS;
     auto ToRemove = I;
     ++I;
     WaitQueue.erase(ToRemove);
   }
 }
 
-InstRef Scheduler::select() {
+InstRef ExecuteStage::select() {
   // Give priority to older instructions in the ReadyQueue. Since the ready
   // queue is ordered by key, this will always prioritize older instructions.
   const auto It = std::find_if(ReadyQueue.begin(), ReadyQueue.end(),
                                [&](const QueueEntryTy &Entry) {
                                  const InstrDesc &D = Entry.second->getDesc();
                                  return Resources->canBeIssued(D);
                                });
 
   if (It == ReadyQueue.end())
     return {0, nullptr};
 
   // We found an instruction to issue.
   InstRef IR(It->first, It->second);
   ReadyQueue.erase(It);
   return IR;
 }
 
-void Scheduler::updatePendingQueue(SmallVectorImpl<InstRef> &Ready) {
+void ExecuteStage::updatePendingQueue(SmallVectorImpl<InstRef> &Ready) {
   // Notify to instructions in the pending queue that a new cycle just
   // started.
   for (QueueEntryTy Entry : WaitQueue)
     Entry.second->cycleEvent();
   promoteToReadyQueue(Ready);
 }
 
-void Scheduler::updateIssuedQueue(SmallVectorImpl<InstRef> &Executed) {
+void ExecuteStage::updateIssuedQueue(SmallVectorImpl<InstRef> &Executed) {
   for (auto I = IssuedQueue.begin(), E = IssuedQueue.end(); I != E;) {
     const QueueEntryTy Entry = *I;
     Instruction *IS = Entry.second;
     IS->cycleEvent();
     if (IS->isExecuted()) {
       Executed.push_back({Entry.first, Entry.second});
       auto ToRemove = I;
       ++I;
       IssuedQueue.erase(ToRemove);
     } else {
       LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction " << Entry.first
                         << " is still executing.\n");
       ++I;
     }
   }
 }
 
-void Scheduler::notifyInstructionIssued(
+void ExecuteStage::notifyInstructionIssued(
     const InstRef &IR, ArrayRef<std::pair<ResourceRef, double>> Used) {
   LLVM_DEBUG({
     dbgs() << "[E] Instruction Issued: " << IR << '\n';
     for (const std::pair<ResourceRef, unsigned> &Resource : Used) {
       dbgs() << "[E] Resource Used: [" << Resource.first.first << '.'
              << Resource.first.second << "]\n";
       dbgs() << "           cycles: " << Resource.second << '\n';
     }
   });
   Owner->notifyInstructionEvent(HWInstructionIssuedEvent(IR, Used));
 }
 
-void Scheduler::notifyInstructionExecuted(const InstRef &IR) {
+void ExecuteStage::notifyInstructionExecuted(const InstRef &IR) {
   LSU->onInstructionExecuted(IR);
   LLVM_DEBUG(dbgs() << "[E] Instruction Executed: " << IR << '\n');
   Owner->notifyInstructionEvent(
       HWInstructionEvent(HWInstructionEvent::Executed, IR));
   DS->onInstructionExecuted(IR.getInstruction()->getRCUTokenID());
 }
 
-void Scheduler::notifyInstructionReady(const InstRef &IR) {
+void ExecuteStage::notifyInstructionReady(const InstRef &IR) {
   LLVM_DEBUG(dbgs() << "[E] Instruction Ready: " << IR << '\n');
   Owner->notifyInstructionEvent(
       HWInstructionEvent(HWInstructionEvent::Ready, IR));
 }
 
-void Scheduler::notifyResourceAvailable(const ResourceRef &RR) {
+void ExecuteStage::notifyResourceAvailable(const ResourceRef &RR) {
   Owner->notifyResourceAvailable(RR);
 }
 
-void Scheduler::notifyReservedBuffers(ArrayRef<uint64_t> Buffers) {
+void ExecuteStage::notifyReservedBuffers(ArrayRef<uint64_t> Buffers) {
   if (Buffers.empty())
     return;
 
   SmallVector<unsigned, 4> BufferIDs(Buffers.begin(), Buffers.end());
   std::transform(
       Buffers.begin(), Buffers.end(), BufferIDs.begin(),
       [&](uint64_t Op) { return Resources->resolveResourceMask(Op); });
   Owner->notifyReservedBuffers(BufferIDs);
 }
 
-void Scheduler::notifyReleasedBuffers(ArrayRef<uint64_t> Buffers) {
+void ExecuteStage::notifyReleasedBuffers(ArrayRef<uint64_t> Buffers) {
   if (Buffers.empty())
     return;
 
   SmallVector<unsigned, 4> BufferIDs(Buffers.begin(), Buffers.end());
   std::transform(
       Buffers.begin(), Buffers.end(), BufferIDs.begin(),
       [&](uint64_t Op) { return Resources->resolveResourceMask(Op); });
   Owner->notifyReleasedBuffers(BufferIDs);
 }
 } // namespace mca

tools/llvm-mca/HWEventListener.h

 // they are not interested in.
 class HWInstructionEvent {
 public:
   // This is the list of event types that are shared by all targets, that
   // generic subtarget-agnostic classes (e.g. Backend, HWInstructionEvent, ...)
   // and generic Views can manipulate.
   // Subtargets are free to define additional event types, that are goin to be
   // handled by generic components as opaque values, but can still be
-  // emitted by subtarget-specific pipeline components (e.g. Scheduler,
+  // emitted by subtarget-specific pipeline components (e.g. ExecuteStage,
   // DispatchStage, ...) and interpreted by subtarget-specific EventListener
   // implementations.
   enum GenericEventType {
     Invalid = 0,
     // Events generated by the Retire Control Unit.
     Retired,
     // Events generated by the Scheduler.
     Ready,
enum GenericEventType {
     RegisterFileStall,
     RetireControlUnitStall,
     // Generic stall events generated by the Scheduler.
     DispatchGroupStall,
     SchedulerQueueFull,
     LoadQueueFull,
     StoreQueueFull,
     LastGenericEvent
   };
 
   HWStallEvent(unsigned type, const InstRef &Inst) : Type(type), IR(Inst) {}
 
   // The exact meaning of the stall event type depends on the subtarget.
   const unsigned Type;
 
   // The instruction this event was generated for.
   const InstRef &IR;
 };

tools/llvm-mca/README.txt

 input register operands become available.  Only at that point, does the
 instruction becomes eligible for execution and may be issued (potentially
 out-of-order) to a pipeline for execution.
 
 Instruction latencies can be computed by the tool with the help of the
 scheduling model; latency values are defined by the scheduling model through
 ProcWriteResources objects.
 
-Class Scheduler (see file Scheduler.h) knows how to emulate multiple processor
-schedulers.  A Scheduler is responsible for tracking data dependencies, and
-dynamically select which processor resources are consumed/used by instructions.
-
-Internally, the Scheduler class delegates the management of processor resource
-units and resource groups to the ResourceManager class.  ResourceManager is also
-responsible for selecting resource units that are effectively consumed by
-instructions.  For example, if an instruction consumes 1cy of a resource group,
-the ResourceManager object selects one of the available units from the group; by
-default, it uses a round-robin selector to guarantee that resource usage is
-uniformly distributed between all units of a group.
+Class ExecuteStage (see file ExecuteStage.h) knows how to emulate multiple
+processor schedulers.  The ExecuteStage is responsible for tracking data
+dependencies, and dynamically select which processor resources are
+consumed/used by instructions.
+
+Internally, the ExecuteStage class delegates the management of processor
+resource units and resource groups to the ResourceManager class.
+ResourceManager is also responsible for selecting resource units that are
+effectively consumed by instructions.  For example, if an instruction consumes
+1cy of a resource group, the ResourceManager object selects one of the
+available units from the group; by default, it uses a round-robin selector to
+guarantee that resource usage is uniformly distributed between all units of a
+group.
 
-Internally, class Scheduler implements three instruction queues:
+Internally, class ExecuteStage implements three instruction queues:
   - WaitQueue: a queue of instructions whose operands are not ready yet.
   - ReadyQueue: a queue of instructions ready to execute.
   - IssuedQueue: a queue of instructions executing.
 
 Depending on the operands availability, instructions that are dispatched to the
-Scheduler are either placed into the WaitQueue or into the ReadyQueue.
+ExecuteStage are either placed into the WaitQueue or into the ReadyQueue.
 
-Every cycle, class Scheduler checks if instructions can be moved from the
+Every cycle, class ExecuteStage checks if instructions can be moved from the
 WaitQueue to the ReadyQueue, and if instructions from the ReadyQueue can be
 issued to the underlying pipelines.  The algorithm prioritizes older
 instructions over younger instructions.
 
-Objects of class ResourceState (see Scheduler.h) describe processor resources.
-There is an instance of class ResourceState for each single processor resource
-specified by the scheduling model.  A ResourceState object for a processor
-resource with multiple units dynamically tracks the availability of every single
-unit.  For example, the ResourceState of a resource group tracks the
-availability of every resource in that group.  Internally, ResourceState
-implements a round-robin selector to dynamically pick the next unit to use from
-the group.
+Objects of class ResourceState (see ExecuteStage.h) describe processor
+resources.  There is an instance of class ResourceState for each single
+processor resource specified by the scheduling model.  A ResourceState object
+for a processor resource with multiple units dynamically tracks the
+availability of every single unit.  For example, the ResourceState of a
+resource group tracks the availability of every resource in that group.
+Internally, ResourceState implements a round-robin selector to dynamically pick
+the next unit to use from the group.
 
 Write-Back and Retire Stage
 ---------------------------
 
 Issued instructions are moved from the ReadyQueue to the IssuedQueue.  There,
 instructions wait until they reach the write-back stage.  At that point, they
 get removed from the queue and the retire control unit is notified.
 

 
 This model doesn't correctly describe processors where the dispatch/issue is a
 single stage. This is what happens for example in VLIW processors, where
 instructions are packaged and statically scheduled at compile time; it is up to
 the compiler to predict the latency of instructions and package issue groups
 accordingly. For such targets, there is no dynamic scheduling done by the
 hardware.
 
-Existing classes (DispatchStage, Scheduler, etc.) could be extended/adapted to
-support processors with a single dispatch/issue stage. The execution flow would
-require some changes in the way how existing components (i.e.,  DispatchStage,
-Scheduler, etc.) interact. This can be a future development.
+Existing classes (DispatchStage, ExecuteStage, etc.) could be extended/adapted
+to support processors with a single dispatch/issue stage. The execution flow
+would require some changes in the way how existing components (i.e.,
+DispatchStage, ExecuteStage, etc.) interact. This can be a future development.
 
 The following sections describes other known limitations.  The goal is not to
 provide an extensive list of limitations; we want to report what we believe are
 the most important limitations, and suggest possible methods to overcome them.
 
 Load/Store barrier instructions and serializing operations
 ----------------------------------------------------------
 Section "Load/Store Unit and Memory Consistency Model" already mentioned how

 instructions as serializing operations.
 
 Lack of support for instruction itineraries
 -------------------------------------------
 The current version of the tool doesn't know how to process instruction
 itineraries.  This is probably one of the most important limitations, since it
 affects a few out-of-order processors in LLVM.
 
-As mentioned in section 'Instruction Issue', class Scheduler delegates to an
+As mentioned in section 'Instruction Issue', class ExecuteStage delegates to an
 instance of class ResourceManager the handling of processor resources.
 ResourceManager is where most of the scheduling logic is implemented.
 
 Adding support for instruction itineraries requires that we teach
 ResourceManager how to handle functional units and instruction stages.  This
 development can be a future extension, and it would probably require a few
 changes to the ResourceManager interface.