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

adibiagio · adibiagio · commit f3374f04ad09 · 2018-08-21T18:20:16.000Z
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. Differential Revision: https://reviews.llvm.org/D51051 llvm-svn: 340314
diff --git a/llvm/tools/llvm-mca/Scheduler.cpp b/llvm/tools/llvm-mca/Scheduler.cpp
@@ -248,6 +248,10 @@ void ResourceManager::releaseResource(uint64_t 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';
@@ -259,7 +263,7 @@ void Scheduler::dump() const {
 
 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;
@@ -335,7 +339,7 @@ void Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
     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;
@@ -354,30 +358,13 @@ void Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
 
 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;
-      }
     }
   }
 
@@ -430,7 +417,7 @@ void Scheduler::cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
 
   for (InstRef &IR : WaitSet)
     IR.getInstruction()->cycleEvent();
-  
+
   promoteToReadySet(Ready);
 }
 
diff --git a/llvm/tools/llvm-mca/Scheduler.h b/llvm/tools/llvm-mca/Scheduler.h
@@ -339,6 +339,42 @@ class ResourceManager {
 #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.
 ///
@@ -363,9 +399,11 @@ class ResourceManager {
 /// 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;
 
@@ -389,8 +427,17 @@ class Scheduler : public HardwareUnit {
 
 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 {
@@ -450,13 +497,9 @@ class Scheduler : public HardwareUnit {
     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
