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.
computeRank(const InstRef & Lhs)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 
compare(const InstRef & Lhs,const InstRef & Rhs)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:
Scheduler(const MCSchedModel & Model,LSUnit & Lsu)120   Scheduler(const MCSchedModel &Model, LSUnit &Lsu)
121       : Scheduler(Model, Lsu, nullptr) {}
122 
Scheduler(const MCSchedModel & Model,LSUnit & Lsu,std::unique_ptr<SchedulerStrategy> SelectStrategy)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 
Scheduler(std::unique_ptr<ResourceManager> RM,LSUnit & Lsu,std::unique_ptr<SchedulerStrategy> SelectStrategy)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.
getResourceID(uint64_t Mask)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.
sanityCheck(const InstRef & IR)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
215