include/llvm/MCA/HardwareUnits/Scheduler.h

   1 //===--------------------- Scheduler.h ------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 /// \file
   9 ///
  10 /// A scheduler for Processor Resource Units and Processor Resource Groups.
  11 ///
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_MCA_SCHEDULER_H
  15 #define LLVM_MCA_SCHEDULER_H
  16
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/MC/MCSchedule.h"
  19 #include "llvm/MCA/HardwareUnits/HardwareUnit.h"
  20 #include "llvm/MCA/HardwareUnits/LSUnit.h"
  21 #include "llvm/MCA/HardwareUnits/ResourceManager.h"
  22 #include "llvm/MCA/Support.h"
  23
  24 namespace llvm {
  25 namespace mca {
  26
  27 class SchedulerStrategy {
  28 public:
  29   SchedulerStrategy() = default;
  30   virtual ~SchedulerStrategy();
  31
  32   /// Returns true if Lhs should take priority over Rhs.
  33   ///
  34   /// This method is used by class Scheduler to select the "best" ready
  35   /// instruction to issue to the underlying pipelines.
  36   virtual bool compare(const InstRef &Lhs, const InstRef &Rhs) const = 0;
  37 };
  38
  39 /// Default instruction selection strategy used by class Scheduler.
  40 class DefaultSchedulerStrategy : public SchedulerStrategy {
  41   /// This method ranks instructions based on their age, and the number of known
  42   /// users. The lower the rank value, the better.
  43   int computeRank(const InstRef &Lhs) const {
  44     return Lhs.getSourceIndex() - Lhs.getInstruction()->getNumUsers();
  45   }
  46
  47 public:
  48   DefaultSchedulerStrategy() = default;
  49   virtual ~DefaultSchedulerStrategy();
  50
  51   bool compare(const InstRef &Lhs, const InstRef &Rhs) const override {
  52     int LhsRank = computeRank(Lhs);
  53     int RhsRank = computeRank(Rhs);
  54
  55     /// Prioritize older instructions over younger instructions to minimize the
  56     /// pressure on the reorder buffer.
  57     if (LhsRank == RhsRank)
  58       return Lhs.getSourceIndex() < Rhs.getSourceIndex();
  59     return LhsRank < RhsRank;
  60   }
  61 };
  62
  63 /// Class Scheduler is responsible for issuing instructions to pipeline
  64 /// resources.
  65 ///
  66 /// Internally, it delegates to a ResourceManager the management of processor
  67 /// resources. This class is also responsible for tracking the progress of
  68 /// instructions from the dispatch stage, until the write-back stage.
  69 ///
  70 class Scheduler : public HardwareUnit {
  71   LSUnit &LSU;
  72
  73   // Instruction selection strategy for this Scheduler.
  74   std::unique_ptr<SchedulerStrategy> Strategy;
  75
  76   // Hardware resources that are managed by this scheduler.
  77   std::unique_ptr<ResourceManager> Resources;
  78
  79   // Instructions dispatched to the Scheduler are internally classified based on
  80   // the instruction stage (see Instruction::InstrStage).
  81   //
  82   // An Instruction dispatched to the Scheduler is added to the WaitSet if not
  83   // all its register operands are available, and at least one latency is
  84   // unknown.  By construction, the WaitSet only contains instructions that are
  85   // in the IS_DISPATCHED stage.
  86   //
  87   // An Instruction transitions from the WaitSet to the PendingSet if the
  88   // instruction is not ready yet, but the latency of every register read is
  89   // known.  Instructions in the PendingSet can only be in the IS_PENDING or
  90   // IS_READY stage.  Only IS_READY instructions that are waiting on memory
  91   // dependencies can be added to the PendingSet.
  92   //
  93   // Instructions in the PendingSet are immediately dominated only by
  94   // instructions that have already been issued to the underlying pipelines.  In
  95   // the presence of bottlenecks caused by data dependencies, the PendingSet can
  96   // be inspected to identify problematic data dependencies between
  97   // instructions.
  98   //
  99   // An instruction is moved to the ReadySet when all register operands become
 100   // available, and all memory dependencies are met.  Instructions that are
 101   // moved from the PendingSet to the ReadySet must transition to the 'IS_READY'
 102   // stage.
 103   //
 104   // On every cycle, the Scheduler checks if it can promote instructions from the
 105   // PendingSet to the ReadySet.
 106   //
 107   // An Instruction is moved from the ReadySet to the `IssuedSet` when it starts
 108   // exection. This event also causes an instruction state transition (i.e. from
 109   // state IS_READY, to state IS_EXECUTING). An Instruction leaves the IssuedSet
 110   // only when it reaches the write-back stage.
 111   std::vector<InstRef> WaitSet;
 112   std::vector<InstRef> PendingSet;
 113   std::vector<InstRef> ReadySet;
 114   std::vector<InstRef> IssuedSet;
 115
 116   // A mask of busy resource units. It defaults to the empty set (i.e. a zero
 117   // mask), and it is cleared at the beginning of every cycle.
 118   // It is updated every time the scheduler fails to issue an instruction from
 119   // the ready set due to unavailable pipeline resources.
 120   // Each bit of the mask represents an unavailable resource.
 121   uint64_t BusyResourceUnits;
 122
 123   /// Verify the given selection strategy and set the Strategy member
 124   /// accordingly.  If no strategy is provided, the DefaultSchedulerStrategy is
 125   /// used.
 126   void initializeStrategy(std::unique_ptr<SchedulerStrategy> S);
 127
 128   /// Issue an instruction without updating the ready queue.
 129   void issueInstructionImpl(
 130       InstRef &IR,
 131       SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes);
 132
 133   // Identify instructions that have finished executing, and remove them from
 134   // the IssuedSet. References to executed instructions are added to input
 135   // vector 'Executed'.
 136   void updateIssuedSet(SmallVectorImpl<InstRef> &Executed);
 137
 138   // Try to promote instructions from the PendingSet to the ReadySet.
 139   // Add promoted instructions to the 'Ready' vector in input.
 140   // Returns true if at least one instruction was promoted.
 141   bool promoteToReadySet(SmallVectorImpl<InstRef> &Ready);
 142
 143   // Try to promote instructions from the WaitSet to the PendingSet.
 144   // Returns true if at least one instruction was promoted.
 145   bool promoteToPendingSet();
 146
 147 public:
 148   Scheduler(const MCSchedModel &Model, LSUnit &Lsu)
 149       : Scheduler(Model, Lsu, nullptr) {}
 150
 151   Scheduler(const MCSchedModel &Model, LSUnit &Lsu,
 152             std::unique_ptr<SchedulerStrategy> SelectStrategy)
 153       : Scheduler(make_unique<ResourceManager>(Model), Lsu,
 154                   std::move(SelectStrategy)) {}
 155
 156   Scheduler(std::unique_ptr<ResourceManager> RM, LSUnit &Lsu,
 157             std::unique_ptr<SchedulerStrategy> SelectStrategy)
 158       : LSU(Lsu), Resources(std::move(RM)), BusyResourceUnits(0) {
 159     initializeStrategy(std::move(SelectStrategy));
 160   }
 161
 162   // Stalls generated by the scheduler.
 163   enum Status {
 164     SC_AVAILABLE,
 165     SC_LOAD_QUEUE_FULL,
 166     SC_STORE_QUEUE_FULL,
 167     SC_BUFFERS_FULL,
 168     SC_DISPATCH_GROUP_STALL,
 169   };
 170
 171   /// Check if the instruction in 'IR' can be dispatched and returns an answer
 172   /// in the form of a Status value.
 173   ///
 174   /// The DispatchStage is responsible for querying the Scheduler before
 175   /// dispatching new instructions. This routine is used for performing such
 176   /// a query.  If the instruction 'IR' can be dispatched, then true is
 177   /// returned, otherwise false is returned with Event set to the stall type.
 178   /// Internally, it also checks if the load/store unit is available.
 179   Status isAvailable(const InstRef &IR) const;
 180
 181   /// Reserves buffer and LSUnit queue resources that are necessary to issue
 182   /// this instruction.
 183   ///
 184   /// Returns true if instruction IR is ready to be issued to the underlying
 185   /// pipelines. Note that this operation cannot fail; it assumes that a
 186   /// previous call to method `isAvailable(IR)` returned `SC_AVAILABLE`.
 187   void dispatch(const InstRef &IR);
 188
 189   /// Returns true if IR is ready to be executed by the underlying pipelines.
 190   /// This method assumes that IR has been previously dispatched.
 191   bool isReady(const InstRef &IR) const;
 192
 193   /// Issue an instruction and populates a vector of used pipeline resources,
 194   /// and a vector of instructions that transitioned to the ready state as a
 195   /// result of this event.
 196   void issueInstruction(
 197       InstRef &IR,
 198       SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Used,
 199       SmallVectorImpl<InstRef> &Ready);
 200
 201   /// Returns true if IR has to be issued immediately, or if IR is a zero
 202   /// latency instruction.
 203   bool mustIssueImmediately(const InstRef &IR) const;
 204
 205   /// This routine notifies the Scheduler that a new cycle just started.
 206   ///
 207   /// It notifies the underlying ResourceManager that a new cycle just started.
 208   /// Vector `Freed` is populated with resourceRef related to resources that
 209   /// have changed in state, and that are now available to new instructions.
 210   /// Instructions executed are added to vector Executed, while vector Ready is
 211   /// populated with instructions that have become ready in this new cycle.
 212   void cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
 213                   SmallVectorImpl<InstRef> &Ready,
 214                   SmallVectorImpl<InstRef> &Executed);
 215
 216   /// Convert a resource mask into a valid llvm processor resource identifier.
 217   unsigned getResourceID(uint64_t Mask) const {
 218     return Resources->resolveResourceMask(Mask);
 219   }
 220
 221   /// Select the next instruction to issue from the ReadySet. Returns an invalid
 222   /// instruction reference if there are no ready instructions, or if processor
 223   /// resources are not available.
 224   InstRef select();
 225
 226   /// Returns a mask of busy resources. Each bit of the mask identifies a unique
 227   /// processor resource unit. In the absence of bottlenecks caused by resource
 228   /// pressure, the mask value returned by this method is always zero.
 229   uint64_t getBusyResourceUnits() const { return BusyResourceUnits; }
 230   bool arePipelinesFullyUsed() const {
 231     return !Resources->getAvailableProcResUnits();
 232   }
 233   bool isReadySetEmpty() const { return ReadySet.empty(); }
 234   bool isWaitSetEmpty() const { return WaitSet.empty(); }
 235
 236 #ifndef NDEBUG
 237   // Update the ready queues.
 238   void dump() const;
 239
 240   // This routine performs a sanity check.  This routine should only be called
 241   // when we know that 'IR' is not in the scheduler's instruction queues.
 242   void sanityCheck(const InstRef &IR) const {
 243     assert(find(WaitSet, IR) == WaitSet.end() && "Already in the wait set!");
 244     assert(find(ReadySet, IR) == ReadySet.end() && "Already in the ready set!");
 245     assert(find(IssuedSet, IR) == IssuedSet.end() && "Already executing!");
 246   }
 247 #endif // !NDEBUG
 248 };
 249 } // namespace mca
 250 } // namespace llvm
 251
 252 #endif // LLVM_MCA_SCHEDULER_H