[llvm-mca] Add the ability to customize the instruction selection strategy in the Scheduler.

[andreadb]

Summary

The constructor of Scheduler now accepts a SchedulerStrategy object, which is used internally by method Scheduler::select() to drive the instruction selection process.

The goal of this patch is to enable the definition of custom selection strategies while reusing the same algorithms implemented by class Scheduler.
The motivation is that, on some targets, the default strategy may not well approximate the selection logic in the hardware schedulers.

This patch also adds the ability to pass a ResourceManager object to the constructor of Scheduler. This gives a bit more flexibility to the design, and potentially it allows to expose processor resources to SchedulerStrategy objects.

Please let me know if okay to commit.

-Andrea

[mattd]

LGTM, we chatted about the index calculation offline. I am okay with that instruction age calculation.

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

 #ifndef NDEBUG
   void dump() const {
     for (const UniqueResourceState &Resource : Resources)
       Resource->dump();
   }
 #endif
 }; // namespace mca
 
+class SchedulerStrategy {
+public:
+  SchedulerStrategy() = default;
+  virtual ~SchedulerStrategy();
+
+  /// Returns true if Lhs should take priority over Rhs.
+  ///
+  /// This method is used by class Scheduler to select the "best" ready
+  /// instruction to issue to the underlying pipelines.
+  virtual bool compare(const InstRef &Lhs, const InstRef &Rhs) const = 0;
+};
+
+/// Default instruction selection strategy used by class Scheduler.
+class DefaultSchedulerStrategy : public SchedulerStrategy {
+  /// This method ranks instructions based on their age, and the number of known
+  /// users. The lower the rank value, the better.
+  int computeRank(const InstRef &Lhs) const {
+    return Lhs.getSourceIndex() - Lhs.getInstruction()->getNumUsers();
+  }
+
+public:
+  DefaultSchedulerStrategy() = default;
+  virtual ~DefaultSchedulerStrategy();
+
+  bool compare(const InstRef &Lhs, const InstRef &Rhs) const override {
+    int LhsRank = computeRank(Lhs);
+    int RhsRank = computeRank(Rhs);
+
+    /// Prioritize older instructions over younger instructions to minimize the
+    /// pressure on the reorder buffer.
+    if (LhsRank == RhsRank)
+      return Lhs.getSourceIndex() < Rhs.getSourceIndex();
+    return LhsRank < RhsRank;
+  }
+};
+
 /// 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_AVAILABLE' 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 {
-  const llvm::MCSchedModel &SM;
   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;
 
   std::vector<InstRef> WaitSet;
   std::vector<InstRef> ReadySet;
   std::vector<InstRef> IssuedSet;
 
   /// Issue an instruction without updating the ready queue.
   void issueInstructionImpl(
       InstRef &IR,
       llvm::SmallVectorImpl<std::pair<ResourceRef, double>> &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(llvm::SmallVectorImpl<InstRef> &Executed);
 
   // Try to promote instructions from WaitSet to ReadySet.
   // Add promoted instructions to the 'Ready' vector in input.
   void promoteToReadySet(llvm::SmallVectorImpl<InstRef> &Ready);
 
 public:
   Scheduler(const llvm::MCSchedModel &Model, LSUnit *Lsu)
-      : SM(Model), LSU(Lsu), Resources(llvm::make_unique<ResourceManager>(SM)) {
-  }
+      : LSU(Lsu),
+        Strategy(llvm::make_unique<DefaultSchedulerStrategy>()),
+        Resources(llvm::make_unique<ResourceManager>(Model)) {}
+  Scheduler(const llvm::MCSchedModel &Model, LSUnit *Lsu,
+            std::unique_ptr<SchedulerStrategy> SelectStrategy)
+      : LSU(Lsu), Strategy(std::move(SelectStrategy)),
+        Resources(llvm::make_unique<ResourceManager>(Model)) {}
+  Scheduler(std::unique_ptr<ResourceManager> RM, LSUnit *Lsu,
+            std::unique_ptr<SchedulerStrategy> SelectStrategy)
+      : LSU(Lsu), Strategy(std::move(SelectStrategy)),
+        Resources(std::move(RM)) {}
 
   // Stalls generated by the scheduler.
   enum Status {
     SC_AVAILABLE,
     SC_LOAD_QUEUE_FULL,
     SC_STORE_QUEUE_FULL,
     SC_BUFFERS_FULL,
     SC_DISPATCH_GROUP_STALL,
void cycleEvent(llvm::SmallVectorImpl<ResourceRef> &Freed,
                   llvm::SmallVectorImpl<InstRef> &Ready,
                   llvm::SmallVectorImpl<InstRef> &Executed);
 
   /// Convert a resource mask into a valid llvm processor resource identifier.
   unsigned getResourceID(uint64_t Mask) const {
     return Resources->resolveResourceMask(Mask);
   }
 
-  /// Select the next instruction to issue from the ReadySet.
-  ///
-  /// The default implementation of this method ranks instructions based on
-  /// their age, and the number of known users. It prioritizes older
-  /// instructions over younger instructions to minimize the pressure on the
-  /// reorder buffer. It also gives a little priority boost to instructions
-  /// with multiple users to better expose ILP.
+  /// Select the next instruction to issue from the ReadySet. Returns an invalid
+  /// instruction reference if there are no ready instructions, or if processor
+  /// resources are not available.
   InstRef select();
 
 #ifndef NDEBUG
   // Update the ready queues.
   void dump() const;
 
   // 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.

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

void ResourceManager::reserveResource(uint64_t ResourceID) {
   Resource.setReserved();
 }
 
 void ResourceManager::releaseResource(uint64_t ResourceID) {
   ResourceState &Resource = *Resources[getResourceStateIndex(ResourceID)];
   Resource.clearReserved();
 }
 
+// Anchor the vtable of SchedulerStrategy and DefaultSchedulerStrategy.
+SchedulerStrategy::~SchedulerStrategy() = default;
+DefaultSchedulerStrategy::~DefaultSchedulerStrategy() = default;
+
 #ifndef NDEBUG
 void Scheduler::dump() const {
   dbgs() << "[SCHEDULER]: WaitSet size is: " << WaitSet.size() << '\n';
   dbgs() << "[SCHEDULER]: ReadySet size is: " << ReadySet.size() << '\n';
   dbgs() << "[SCHEDULER]: IssuedSet size is: " << IssuedSet.size() << '\n';
   Resources->dump();
 }
 #endif
 
 Scheduler::Status Scheduler::isAvailable(const InstRef &IR) const {
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
-   
   switch (Resources->canBeDispatched(Desc.Buffers)) {
   case ResourceStateEvent::RS_BUFFER_UNAVAILABLE:
     return Scheduler::SC_BUFFERS_FULL;
   case ResourceStateEvent::RS_RESERVED:
     return Scheduler::SC_DISPATCH_GROUP_STALL;
   case ResourceStateEvent::RS_BUFFER_AVAILABLE:
     break;
   }
if (!IR.isValid())
       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();
 
-    // Check f there are still unsolved data dependencies. 
+    // Check if there are still unsolved data dependencies.
     if (!isReady(IR)) {
       ++I;
       continue;
     }
 
     Ready.emplace_back(IR);
     ReadySet.emplace_back(IR);
 
     IR.invalidate();
     ++RemovedElements;
     std::iter_swap(I, E - RemovedElements);
   }
 
   WaitSet.resize(WaitSet.size() - RemovedElements);
 }
 
 InstRef Scheduler::select() {
   unsigned QueueIndex = ReadySet.size();
-  int Rank = std::numeric_limits<int>::max();
-
   for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
     const InstRef &IR = ReadySet[I];
-    const unsigned IID = IR.getSourceIndex();
-    const Instruction &IS = *IR.getInstruction();
-
-    // Compute a rank value based on the age of an instruction (i.e. its source
-    // index) and its number of users. The lower the rank value, the better.
-    int CurrentRank = IID - IS.getNumUsers();
-
-    // We want to prioritize older instructions over younger instructions to
-    // minimize the pressure on the reorder buffer.  We also want to
-    // rank higher the instructions with more users to better expose ILP.
-    if (CurrentRank == Rank)
-      if (IID > ReadySet[QueueIndex].getSourceIndex())
-        continue;
-
-    if (CurrentRank <= Rank) {
-      const InstrDesc &D = IS.getDesc();
-      if (Resources->canBeIssued(D)) {
-        Rank = CurrentRank;
+    if (QueueIndex == ReadySet.size() ||
+        Strategy->compare(IR, ReadySet[QueueIndex])) {
+      const InstrDesc &D = IR.getInstruction()->getDesc();
+      if (Resources->canBeIssued(D))
         QueueIndex = I;
-      }
-    }
-  }
 
   if (QueueIndex == ReadySet.size())
     return InstRef();
 
   // We found an instruction to issue.
   InstRef IR = ReadySet[QueueIndex];
   std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);
   ReadySet.pop_back();
void Scheduler::cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
   // Propagate the cycle event to the 'Issued' and 'Wait' sets.
   for (InstRef &IR : IssuedSet)
     IR.getInstruction()->cycleEvent();
 
   updateIssuedSet(Executed);
 
   for (InstRef &IR : WaitSet)
     IR.getInstruction()->cycleEvent();
-  
   promoteToReadySet(Ready);
 }
 
 bool Scheduler::mustIssueImmediately(const InstRef &IR) const {
   // 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.
   const InstrDesc &Desc = IR.getInstruction()->getDesc();