contrib/llvm/include/llvm/MCA/HardwareUnits/Scheduler.h

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