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

(On Diff #148157)

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 ↗

(On Diff #150568)

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 ↗

(On Diff #150568)

Please add a small comment here.

tools/llvm-mca/HWEventListener.h

106–107 ↗

(On Diff #150568)

See my other comment.

tools/llvm-mca/Scheduler.cpp

235–236 ↗

(On Diff #150568)

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 ↗

(On Diff #150568)

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 ↗

(On Diff #150568)

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 ↗

(On Diff #150568)

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!

llvm/trunk/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 "RegisterFile.h"
 #include "RetireControlUnit.h"
 #include "RetireStage.h"
 #include "Scheduler.h"
 
 namespace mca {

 ///
 /// 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 {
   // The following are the simulated hardware components of the backend.
   RetireControlUnit RCU;
   RegisterFile PRF;
+  Scheduler HWS;
 
   /// 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::unique_ptr<RetireStage> Retire;
 
   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)
       : RCU(Subtarget.getSchedModel()),
         PRF(Subtarget.getSchedModel(), MRI, RegisterFileSize),
+        HWS(Subtarget.getSchedModel(), LoadQueueSize, StoreQueueSize,
+            AssumeNoAlias),
         Fetch(std::move(InitialStage)),
-        HWS(llvm::make_unique<Scheduler>(this, Subtarget.getSchedModel(), RCU,
-                                         LoadQueueSize, StoreQueueSize,
-                                         AssumeNoAlias)),
         Dispatch(llvm::make_unique<DispatchStage>(
             this, Subtarget, MRI, RegisterFileSize, DispatchWidth, RCU, PRF,
-            HWS.get())),
+            HWS)),
+        Execute(llvm::make_unique<ExecuteStage>(this, RCU, HWS)),
         Retire(llvm::make_unique<RetireStage>(this, RCU, PRF)), Cycles(0) {}
 
   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

llvm/trunk/tools/llvm-mca/Backend.cpp

 
 void Backend::runCycle(unsigned Cycle) {
   notifyCycleBegin(Cycle);
 
   // Update the stages before we do any processing for this cycle.
   InstRef IR;
   Retire->preExecute(IR);
   Dispatch->preExecute(IR);
-
-  // This will execute scheduled instructions.
-  HWS->cycleEvent(); // TODO: This will eventually be stage-ified.
+  Execute->preExecute(IR);
 
   // Fetch instructions and dispatch them to the hardware.
   while (Fetch->execute(IR)) {
     if (!Dispatch->execute(IR))
       break;
+    Execute->execute(IR);
     Fetch->postExecute(IR);
   }
 
   notifyCycleEnd(Cycle);
 }
 
 void Backend::notifyCycleBegin(unsigned Cycle) {
   LLVM_DEBUG(dbgs() << "[E] Cycle begin: " << Cycle << '\n');

llvm/trunk/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

llvm/trunk/tools/llvm-mca/DispatchStage.h

 // 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;
   Backend *Owner;
   const llvm::MCSubtargetInfo &STI;
   RetireControlUnit &RCU;
   RegisterFile &PRF;
+  Scheduler ≻
 
   bool checkRCU(const InstRef &IR);
   bool checkPRF(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 collectWrites(llvm::SmallVectorImpl<WriteState *> &Vec,
                      unsigned RegID) const {
     return PRF.collectWrites(Vec, RegID);
   }
 
 public:
   DispatchStage(Backend *B, const llvm::MCSubtargetInfo &Subtarget,
                 const llvm::MCRegisterInfo &MRI, unsigned RegisterFileSize,
                 unsigned MaxDispatchWidth, RetireControlUnit &R,
-                RegisterFile &F, Scheduler *Sched)
+                RegisterFile &F, Scheduler &Sched)
       : DispatchWidth(MaxDispatchWidth), AvailableEntries(MaxDispatchWidth),
-        CarryOver(0U), SC(Sched), Owner(B), STI(Subtarget), RCU(R), PRF(F) {}
+        CarryOver(0U), Owner(B), STI(Subtarget), RCU(R), PRF(F), SC(Sched) {}
 
   virtual bool isReady() const override final { return isRCUEmpty(); }
   virtual void preExecute(const InstRef &IR) override final;
   virtual bool execute(InstRef &IR) override final;
   void notifyDispatchStall(const InstRef &IR, unsigned EventType);
 
 #ifndef NDEBUG
   void dump() const;
 #endif
 };
 } // namespace mca
 
 #endif // LLVM_TOOLS_LLVM_MCA_DISPATCH_STAGE_H

llvm/trunk/tools/llvm-mca/DispatchStage.cpp

bool DispatchStage::checkRCU(const InstRef &IR) {
   if (RCU.isAvailable(NumMicroOps))
     return true;
   Owner->notifyStallEvent(
       HWStallEvent(HWStallEvent::RetireControlUnitStall, IR));
   return false;
 }
 
 bool DispatchStage::checkScheduler(const InstRef &IR) {
-  return SC->canBeDispatched(IR);
+  HWStallEvent::GenericEventType Event;
+  const bool Ready = SC.canBeDispatched(IR, Event);
+  if (!Ready)
+    Owner->notifyStallEvent(HWStallEvent(Event, IR));
+  return Ready;
 }
 
 void DispatchStage::updateRAWDependencies(ReadState &RS,
                                           const MCSubtargetInfo &STI) {
   SmallVector<WriteState *, 4> DependentWrites;
 
   collectWrites(DependentWrites, RS.getRegisterID());
   RS.setDependentWrites(DependentWrites.size());
for (std::unique_ptr<WriteState> &WS : IS.getDefs())
     PRF.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) {
   AvailableEntries = CarryOver >= DispatchWidth ? 0 : DispatchWidth - CarryOver;
   CarryOver = CarryOver >= DispatchWidth ? CarryOver - DispatchWidth : 0U;
 }
 
 bool DispatchStage::execute(InstRef &IR) {

llvm/trunk/tools/llvm-mca/ExecuteStage.h

+//===---------------------- ExecuteStage.h ----------------------*- 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 defines the execution stage of an instruction pipeline.
+///
+/// The ExecuteStage is responsible for managing the hardware scheduler
+/// and issuing notifications that an instruction has been executed.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_MCA_EXECUTE_STAGE_H
+#define LLVM_TOOLS_LLVM_MCA_EXECUTE_STAGE_H
+
+#include "Instruction.h"
+#include "RetireControlUnit.h"
+#include "Scheduler.h"
+#include "Stage.h"
+#include "llvm/ADT/ArrayRef.h"
+
+namespace mca {
+
+class Backend;
+
+class ExecuteStage : public Stage {
+  // Owner will go away when we move listeners/eventing to the stages.
+  Backend *Owner;
+  RetireControlUnit &RCU;
+  Scheduler &HWS;
+
+  // The following routines are used to maintain the HWS.
+  void reclaimSchedulerResources();
+  void updateSchedulerQueues();
+  void issueReadyInstructions();
+
+public:
+  ExecuteStage(Backend *B, RetireControlUnit &R, Scheduler &S)
+      : Stage(), Owner(B), RCU(R), HWS(S) {}
+  ExecuteStage(const ExecuteStage &Other) = delete;
+  ExecuteStage &operator=(const ExecuteStage &Other) = delete;
+
+  virtual void preExecute(const InstRef &IR) override final;
+  virtual bool execute(InstRef &IR) override final;
+
+  void
+  notifyInstructionIssued(const InstRef &IR,
+                          llvm::ArrayRef<std::pair<ResourceRef, double>> Used);
+  void notifyInstructionExecuted(const InstRef &IR);
+  void notifyInstructionReady(const InstRef &IR);
+  void notifyResourceAvailable(const ResourceRef &RR);
+
+  // Notify listeners that buffered resources were consumed.
+  void notifyReservedBuffers(llvm::ArrayRef<uint64_t> Buffers);
+
+  // Notify listeners that buffered resources were freed.
+  void notifyReleasedBuffers(llvm::ArrayRef<uint64_t> Buffers);
+};
+
+} // namespace mca
+
+#endif // LLVM_TOOLS_LLVM_MCA_EXECUTE_STAGE_H

llvm/trunk/tools/llvm-mca/ExecuteStage.cpp

+//===---------------------- 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
+///
+/// This file defines the execution stage of an instruction pipeline.
+///
+/// The ExecuteStage is responsible for managing the hardware scheduler
+/// and issuing notifications that an instruction has been executed.
+///
+//===----------------------------------------------------------------------===//
+
+#include "ExecuteStage.h"
+#include "Backend.h"
+#include "Scheduler.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Debug.h"
+
+#define DEBUG_TYPE "llvm-mca"
+
+namespace mca {
+
+using namespace llvm;
+
+// Reclaim the simulated resources used by the scheduler.
+void ExecuteStage::reclaimSchedulerResources() {
+  SmallVector<ResourceRef, 8> ResourcesFreed;
+  HWS.reclaimSimulatedResources(ResourcesFreed);
+  for (const ResourceRef &RR : ResourcesFreed)
+    notifyResourceAvailable(RR);
+}
+
+// Update the scheduler's instruction queues.
+void ExecuteStage::updateSchedulerQueues() {
+  SmallVector<InstRef, 4> InstructionIDs;
+  HWS.updateIssuedQueue(InstructionIDs);
+  for (const InstRef &IR : InstructionIDs)
+    notifyInstructionExecuted(IR);
+  InstructionIDs.clear();
+
+  HWS.updatePendingQueue(InstructionIDs);
+  for (const InstRef &IR : InstructionIDs)
+    notifyInstructionReady(IR);
+}
+
+// Issue instructions that are waiting in the scheduler's ready queue.
+void ExecuteStage::issueReadyInstructions() {
+  SmallVector<InstRef, 4> InstructionIDs;
+  InstRef IR = HWS.select();
+  while (IR.isValid()) {
+    SmallVector<std::pair<ResourceRef, double>, 4> Used;
+    HWS.issueInstruction(IR, Used);
+
+    // Reclaim instruction resources and perform notifications.
+    const InstrDesc &Desc = IR.getInstruction()->getDesc();
+    notifyReleasedBuffers(Desc.Buffers);
+    notifyInstructionIssued(IR, Used);
+    if (IR.getInstruction()->isExecuted())
+      notifyInstructionExecuted(IR);
+
+    // 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 ReadyQueue and tell to the caller that we need
+    // another round of 'issue()'.
+    HWS.promoteToReadyQueue(InstructionIDs);
+    for (const InstRef &I : InstructionIDs)
+      notifyInstructionReady(I);
+    InstructionIDs.clear();
+
+    // Select the next instruction to issue.
+    IR = HWS.select();
+  }
+}
+
+// The following routine is the maintenance routine of the ExecuteStage.
+// It is responsible for updating the hardware scheduler (HWS), including
+// reclaiming the HWS's simulated hardware resources, as well as updating the
+// HWS's queues.
+//
+// This routine also processes the instructions that are ready for issuance.
+// These instructions are managed by the HWS's ready queue and can be accessed
+// via the Scheduler::select() routine.
+//
+// Notifications are issued to this stage's listeners when instructions are
+// moved between the HWS's queues.  In particular, when an instruction becomes
+// ready or executed.
+void ExecuteStage::preExecute(const InstRef &Unused) {
+  reclaimSchedulerResources();
+  updateSchedulerQueues();
+  issueReadyInstructions();
+}
+
+// Schedule the instruction for execution on the hardware.
+bool ExecuteStage::execute(InstRef &IR) {
+#ifndef NDEBUG
+  // Ensure that the HWS has not stored this instruction in its queues.
+  HWS.sanityCheck(IR);
+#endif
+  // 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();
+  HWS.reserveBuffers(Desc.Buffers);
+  notifyReservedBuffers(Desc.Buffers);
+
+  // Obtain a slot in the LSU.
+  if (!HWS.reserveResources(IR))
+    return false;
+
+  // If we did not return early, then the scheduler is ready for execution.
+  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 specially, 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 we cannot issue immediately, the HWS will add IR to its ready queue for
+  // execution later, so we must return early here.
+  if (!HWS.issueImmediately(IR))
+    return true;
+
+  LLVM_DEBUG(dbgs() << "[SCHEDULER] Instruction " << IR
+                    << " issued immediately\n");
+
+  // Issue IR.  The resources for this issuance will be placed in 'Used.'
+  SmallVector<std::pair<ResourceRef, double>, 4> Used;
+  HWS.issueInstruction(IR, Used);
+
+  // Perform notifications.
+  notifyReleasedBuffers(Desc.Buffers);
+  notifyInstructionIssued(IR, Used);
+  if (IR.getInstruction()->isExecuted())
+    notifyInstructionExecuted(IR);
+
+  return true;
+}
+
+void ExecuteStage::notifyInstructionExecuted(const InstRef &IR) {
+  HWS.onInstructionExecuted(IR);
+  LLVM_DEBUG(dbgs() << "[E] Instruction Executed: " << IR << '\n');
+  Owner->notifyInstructionEvent(
+      HWInstructionEvent(HWInstructionEvent::Executed, IR));
+  RCU.onInstructionExecuted(IR.getInstruction()->getRCUTokenID());
+}
+
+void ExecuteStage::notifyInstructionReady(const InstRef &IR) {
+  LLVM_DEBUG(dbgs() << "[E] Instruction Ready: " << IR << '\n');
+  Owner->notifyInstructionEvent(
+      HWInstructionEvent(HWInstructionEvent::Ready, IR));
+}
+
+void ExecuteStage::notifyResourceAvailable(const ResourceRef &RR) {
+  Owner->notifyResourceAvailable(RR);
+}
+
+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 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 HWS.getResourceID(Op); });
+  Owner->notifyReservedBuffers(BufferIDs);
+}
+
+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 HWS.getResourceID(Op); });
+  Owner->notifyReleasedBuffers(BufferIDs);
+}
+
+} // namespace mca

llvm/trunk/tools/llvm-mca/Scheduler.h

 ///
 /// 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 "HWEventListener.h"
 #include "Instruction.h"
 #include "LSUnit.h"
 #include "RetireControlUnit.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/MC/MCSubtargetInfo.h"
 #include <map>
 
 namespace mca {
 
-class Backend;
-
 /// Used to notify the internal state of a processor resource.
 ///
 /// A processor resource is available if it is not reserved, and there are
 /// available slots in the buffer.  A processor resource is unavailable if it
 /// is either reserved, or the associated buffer is full. A processor resource
 /// with a buffer size of -1 is always available if it is not reserved.
 ///
 /// Values of type ResourceStateEvent are returned by method

 /// 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 {
   const llvm::MCSchedModel &SM;
-  RetireControlUnit &RCU;
 
   // 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;
-
   using QueueEntryTy = std::pair<unsigned, Instruction *>;
   std::map<unsigned, Instruction *> WaitQueue;
   std::map<unsigned, Instruction *> ReadyQueue;
   std::map<unsigned, Instruction *> IssuedQueue;
 
-  void
-  notifyInstructionIssued(const InstRef &IR,
-                          llvm::ArrayRef<std::pair<ResourceRef, double>> Used);
-  void notifyInstructionExecuted(const InstRef &IR);
-  void notifyInstructionReady(const InstRef &IR);
-  void notifyResourceAvailable(const ResourceRef &RR);
-
-  // Notify the Backend that buffered resources were consumed.
-  void notifyReservedBuffers(llvm::ArrayRef<uint64_t> Buffers);
-  // Notify the Backend that buffered resources were freed.
-  void notifyReleasedBuffers(llvm::ArrayRef<uint64_t> Buffers);
-
-  /// Select the next instruction to issue from the ReadyQueue.
-  /// This method gives priority to older instructions.
-  InstRef select();
-
-  /// Move instructions from the WaitQueue to the ReadyQueue if input operands
-  /// are all available.
-  void promoteToReadyQueue(llvm::SmallVectorImpl<InstRef> &Ready);
-
   /// Issue an instruction without updating the ready queue.
   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, RetireControlUnit &R,
-            unsigned LoadQueueSize, unsigned StoreQueueSize, bool AssumeNoAlias)
-      : SM(Model), RCU(R), Resources(llvm::make_unique<ResourceManager>(SM)),
+  Scheduler(const llvm::MCSchedModel &Model, unsigned LoadQueueSize,
+            unsigned StoreQueueSize, bool AssumeNoAlias)
+      : SM(Model), Resources(llvm::make_unique<ResourceManager>(SM)),
         LSU(llvm::make_unique<LSUnit>(LoadQueueSize, StoreQueueSize,
-                                      AssumeNoAlias)),
-        Owner(B) {}
+                                      AssumeNoAlias)) {}
 
   /// Check if the instruction in 'IR' can be dispatched.
   ///
   /// The DispatchStage is responsible for querying the Scheduler before
-  /// dispatching new instructions. Queries are performed through method
-  /// `Scheduler::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);
+  /// dispatching new instructions. This routine is used for performing such
+  /// a query.  If the instruction 'IR' can be dispatched, then true is
+  /// returned, otherwise false is returned with Event set to the stall type.
+  bool canBeDispatched(const InstRef &IR,
+                       HWStallEvent::GenericEventType &Event) const;
 
-  /// Issue an instruction.
-  void issueInstruction(InstRef &IR);
+  /// Returns true if there is availibility for IR in the LSU.
+  bool isReady(const InstRef &IR) const { return LSU->isReady(IR); }
+
+  /// Issue an instruction.  The Used container is populated with
+  /// the resource objects consumed on behalf of issuing this instruction.
+  void
+  issueInstruction(InstRef &IR,
+                   llvm::SmallVectorImpl<std::pair<ResourceRef, double>> &Used);
+
+  /// This routine will attempt to issue an instruction immediately (for
+  /// zero-latency instructions).
+  ///
+  /// Returns true if the instruction is issued immediately.  If this does not
+  /// occur, then the instruction will be added to the Scheduler's ReadyQueue.
+  bool issueImmediately(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();
+  /// Update the resources managed by the scheduler.
+  /// This routine is to be called at the start of a new cycle, and is
+  /// responsible for updating scheduler resources.  Resources are released
+  /// once they have been fully consumed.
+  void reclaimSimulatedResources(llvm::SmallVectorImpl<ResourceRef> &Freed);
+
+  /// Move instructions from the WaitQueue to the ReadyQueue if input operands
+  /// are all available.
+  void promoteToReadyQueue(llvm::SmallVectorImpl<InstRef> &Ready);
+
+  /// Update the ready queue.
+  void updatePendingQueue(llvm::SmallVectorImpl<InstRef> &Ready);
+
+  /// Update the issued queue.
+  void updateIssuedQueue(llvm::SmallVectorImpl<InstRef> &Executed);
+
+  /// Updates the Scheduler's resources to reflect that an instruction has just
+  /// been executed.
+  void onInstructionExecuted(const InstRef &IR);
+
+  /// Obtain the processor's resource identifier for the given
+  /// resource mask.
+  unsigned getResourceID(uint64_t Mask) {
+    return Resources->resolveResourceMask(Mask);
+  }
+
+  /// Reserve resources necessary to issue the instruction.
+  /// Returns true if the resources are ready and the (LSU) can
+  /// execute the given instruction immediately.
+  bool reserveResources(InstRef &IR);
+
+  /// Select the next instruction to issue from the ReadyQueue.
+  /// This method gives priority to older instructions.
+  InstRef select();
 
 #ifndef NDEBUG
+  // Update the ready queues.
   void dump() const;
-#endif
+
+  // This routine performs a sanity check.  This routine should only be called
+  // when we know that 'IR' is not in the scheduler's instruction queues.
+  void sanityCheck(const InstRef &IR) const {
+    const unsigned Idx = IR.getSourceIndex();
+    assert(WaitQueue.find(Idx) == WaitQueue.end());
+    assert(ReadyQueue.find(Idx) == ReadyQueue.end());
+    assert(IssuedQueue.find(Idx) == IssuedQueue.end());
+  }
+#endif // !NDEBUG
 };
-} // Namespace mca
+} // namespace mca
 
-#endif
+#endif // LLVM_TOOLS_LLVM_MCA_SCHEDULER_H

llvm/trunk/tools/llvm-mca/Scheduler.cpp

 // A scheduler for processor resource units and processor resource groups.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Scheduler.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)) {
if (!BR.second) {
       ResourcesFreed.push_back(RR);
     }
   }
 
   for (const ResourceRef &RF : ResourcesFreed)
     BusyResources.erase(RF);
 }
 
-void Scheduler::scheduleInstruction(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;
-  }
-  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;
-  }
-
-  LLVM_DEBUG(dbgs() << "[SCHEDULER] Instruction " << IR
-                    << " issued immediately\n");
-  // Release buffered resources and issue MCIS to the underlying pipelines.
-  issueInstruction(IR);
-}
-
-void Scheduler::cycleEvent() {
-  SmallVector<ResourceRef, 8> ResourcesFreed;
-  Resources->cycleEvent(ResourcesFreed);
-
-  for (const ResourceRef &RR : ResourcesFreed)
-    notifyResourceAvailable(RR);
-
-  SmallVector<InstRef, 4> InstructionIDs;
-  updateIssuedQueue(InstructionIDs);
-  for (const InstRef &IR : InstructionIDs)
-    notifyInstructionExecuted(IR);
-  InstructionIDs.clear();
-
-  updatePendingQueue(InstructionIDs);
-  for (const InstRef &IR : InstructionIDs)
-    notifyInstructionReady(IR);
-  InstructionIDs.clear();
-
-  InstRef IR = select();
-  while (IR.isValid()) {
-    issueInstruction(IR);
-
-    // 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 ReadyQueue and tell to the caller that we need
-    // another round of 'issue()'.
-    promoteToReadyQueue(InstructionIDs);
-    for (const InstRef &I : InstructionIDs)
-      notifyInstructionReady(I);
-    InstructionIDs.clear();
-
-    // Select the next instruction to issue.
-    IR = select();
-  }
-}
-
 #ifndef NDEBUG
 void Scheduler::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 {
-  HWStallEvent::GenericEventType Type = HWStallEvent::Invalid;
+bool Scheduler::canBeDispatched(const InstRef &IR,
+                                HWStallEvent::GenericEventType &Event) const {
+  Event = HWStallEvent::Invalid;
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
 
   if (Desc.MayLoad && LSU->isLQFull())
-    Type = HWStallEvent::LoadQueueFull;
+    Event = HWStallEvent::LoadQueueFull;
   else if (Desc.MayStore && LSU->isSQFull())
-    Type = HWStallEvent::StoreQueueFull;
+    Event = HWStallEvent::StoreQueueFull;
   else {
     switch (Resources->canBeDispatched(Desc.Buffers)) {
     default:
       return true;
     case ResourceStateEvent::RS_BUFFER_UNAVAILABLE:
-      Type = HWStallEvent::SchedulerQueueFull;
+      Event = HWStallEvent::SchedulerQueueFull;
       break;
     case ResourceStateEvent::RS_RESERVED:
-      Type = HWStallEvent::DispatchGroupStall;
+      Event = HWStallEvent::DispatchGroupStall;
     }
   }
 
-  Owner->notifyStallEvent(HWStallEvent(Type, IR));
   return false;
 }
 
 void Scheduler::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) {
-  // Release buffered resources.
+// Release the buffered resources and issue the instruction.
+void Scheduler::issueInstruction(
+    InstRef &IR,
+    SmallVectorImpl<std::pair<ResourceRef, double>> &UsedResources) {
   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);
+  issueInstructionImpl(IR, UsedResources);
 }
 
 void Scheduler::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;
for (auto I = IssuedQueue.begin(), E = IssuedQueue.end(); I != E;) {
     } else {
       LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction " << Entry.first
                         << " is still executing.\n");
       ++I;
     }
   }
 }
 
-void Scheduler::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 Scheduler::onInstructionExecuted(const InstRef &IR) {
   LSU->onInstructionExecuted(IR);
-  LLVM_DEBUG(dbgs() << "[E] Instruction Executed: " << IR << '\n');
-  Owner->notifyInstructionEvent(
-      HWInstructionEvent(HWInstructionEvent::Executed, IR));
-  RCU.onInstructionExecuted(IR.getInstruction()->getRCUTokenID());
 }
 
-void Scheduler::notifyInstructionReady(const InstRef &IR) {
-  LLVM_DEBUG(dbgs() << "[E] Instruction Ready: " << IR << '\n');
-  Owner->notifyInstructionEvent(
-      HWInstructionEvent(HWInstructionEvent::Ready, IR));
+void Scheduler::reclaimSimulatedResources(SmallVectorImpl<ResourceRef> &Freed) {
+  Resources->cycleEvent(Freed);
 }
 
-void Scheduler::notifyResourceAvailable(const ResourceRef &RR) {
-  Owner->notifyResourceAvailable(RR);
+bool Scheduler::reserveResources(InstRef &IR) {
+  // If necessary, reserve queue entries in the load-store unit (LSU).
+  const bool Reserved = LSU->reserve(IR);
+  if (!IR.getInstruction()->isReady() || (Reserved && !LSU->isReady(IR))) {
+    LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding " << IR << " to the Wait Queue\n");
+    WaitQueue[IR.getSourceIndex()] = IR.getInstruction();
+    return false;
   }
-
-void Scheduler::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);
+  return true;
 }
 
-void Scheduler::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);
+bool Scheduler::issueImmediately(InstRef &IR) {
+  const InstrDesc &Desc = IR.getInstruction()->getDesc();
+  if (!Desc.isZeroLatency() && !Resources->mustIssueImmediately(Desc)) {
+    LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding " << IR
+                      << " to the Ready Queue\n");
+    ReadyQueue[IR.getSourceIndex()] = IR.getInstruction();
+    return false;
   }
+  return true;
+}
+
 } // namespace mca