1 //===--------------------- Scheduler.h ------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// A scheduler for Processor Resource Units and Processor Resource Groups.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_TOOLS_LLVM_MCA_SCHEDULER_H
16 #define LLVM_TOOLS_LLVM_MCA_SCHEDULER_H
18 #include "Instruction.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/MC/MCSubtargetInfo.h"
29 /// Used to notify the internal state of a processor resource.
31 /// A processor resource is available if it is not reserved, and there are
32 /// available slots in the buffer. A processor resource is unavailable if it
33 /// is either reserved, or the associated buffer is full. A processor resource
34 /// with a buffer size of -1 is always available if it is not reserved.
36 /// Values of type ResourceStateEvent are returned by method
37 /// ResourceState::isBufferAvailable(), which is used to query the internal
38 /// state of a resource.
40 /// The naming convention for resource state events is:
41 /// * Event names start with prefix RS_
42 /// * Prefix RS_ is followed by a string describing the actual resource state.
43 enum ResourceStateEvent {
45 RS_BUFFER_UNAVAILABLE,
49 /// A descriptor for processor resources.
51 /// Each object of class ResourceState is associated to a specific processor
52 /// resource. There is an instance of this class for every processor resource
53 /// defined by the scheduling model.
54 /// A ResourceState dynamically tracks the availability of units of a processor
55 /// resource. For example, the ResourceState of a ProcResGroup tracks the
56 /// availability of resource units which are part of the group.
58 /// Internally, ResourceState uses a round-robin selector to identify
59 /// which unit of the group shall be used next.
61 // Index to the MCProcResourceDesc in the processor Model.
62 unsigned ProcResourceDescIndex;
63 // A resource mask. This is generated by the tool with the help of
64 // function `mca::createProcResourceMasks' (see Support.h).
65 uint64_t ResourceMask;
67 // A ProcResource can specify a number of units. For the purpose of dynamic
68 // scheduling, a processor resource with more than one unit behaves like a
69 // group. This field has one bit set for every unit/resource that is part of
71 // For groups, this field defaults to 'ResourceMask'. For non-group
72 // resources, the number of bits set in this mask is equivalent to the
73 // number of units (i.e. field 'NumUnits' in 'ProcResourceUnits').
74 uint64_t ResourceSizeMask;
76 // A simple round-robin selector for processor resources.
77 // Each bit of the mask identifies a sub resource within this group.
79 // As an example, lets assume that this ResourceState describes a
80 // processor resource group composed of the following three units:
85 // Each unit is identified by a ResourceMask which always contains a
86 // single bit set. Field NextInSequenceMask is initially set to value
87 // 0xb111. That value is obtained by OR'ing the resource masks of
88 // processor resource that are part of the group.
90 // NextInSequenceMask -- 0b111
92 // Field NextInSequenceMask is used by the resource manager (i.e.
93 // an object of class ResourceManager) to select the "next available resource"
94 // from the set. The algorithm would prioritize resources with a bigger
95 // ResourceMask value.
97 // In this example, there are three resources in the set, and 'ResourceC'
98 // has the highest mask value. The round-robin selector would firstly select
99 // 'ResourceC', then 'ResourceB', and eventually 'ResourceA'.
101 // When a resource R is used, its corresponding bit is cleared from the set.
103 // Back to the example:
104 // If 'ResourceC' is selected, then the new value of NextInSequenceMask
107 // When NextInSequenceMask becomes zero, it is reset to its original value
108 // (in this example, that value would be 0b111).
109 uint64_t NextInSequenceMask;
111 // Some instructions can only be issued on very specific pipeline resources.
112 // For those instructions, we know exactly which resource would be consumed
113 // without having to dynamically select it using field 'NextInSequenceMask'.
115 // The resource mask bit associated to the (statically) selected
116 // processor resource is still cleared from the 'NextInSequenceMask'.
117 // If that bit was already zero in NextInSequenceMask, then we update
118 // mask 'RemovedFromNextInSequence'.
120 // When NextInSequenceMask is reset back to its initial value, the algorithm
121 // removes any bits which are set in RemoveFromNextInSequence.
122 uint64_t RemovedFromNextInSequence;
124 // A mask of ready units.
127 // Buffered resources will have this field set to a positive number bigger
128 // than 0. A buffered resource behaves like a separate reservation station
129 // implementing its own buffer for out-of-order execution.
130 // A buffer of 1 is for units that force in-order execution.
131 // A value of 0 is treated specially. In particular, a resource with
132 // A BufferSize = 0 is for an in-order issue/dispatch resource.
133 // That means, this resource is reserved starting from the dispatch event,
134 // until all the "resource cycles" are consumed after the issue event.
135 // While this resource is reserved, no other instruction may be dispatched.
138 // Available slots in the buffer (zero, if this is not a buffered resource).
139 unsigned AvailableSlots;
141 // True if this is resource is currently unavailable.
142 // An instruction may "reserve" a resource for a number of cycles.
143 // During those cycles, the reserved resource cannot be used for other
144 // instructions, even if the ReadyMask is set.
147 bool isSubResourceReady(uint64_t ID) const { return ReadyMask & ID; }
149 /// Returns the mask identifier of the next available resource in the set.
150 uint64_t getNextInSequence() const {
151 assert(NextInSequenceMask);
152 return llvm::PowerOf2Floor(NextInSequenceMask);
155 /// Returns the mask of the next available resource within the set,
156 /// and updates the resource selector.
157 void updateNextInSequence() {
158 NextInSequenceMask ^= getNextInSequence();
159 if (!NextInSequenceMask)
160 NextInSequenceMask = ResourceSizeMask;
163 uint64_t computeResourceSizeMaskForGroup(uint64_t ResourceMask) {
164 assert(llvm::countPopulation(ResourceMask) > 1);
165 return ResourceMask ^ llvm::PowerOf2Floor(ResourceMask);
169 ResourceState(const llvm::MCProcResourceDesc &Desc, unsigned Index,
171 : ProcResourceDescIndex(Index), ResourceMask(Mask) {
172 bool IsAGroup = llvm::countPopulation(ResourceMask) > 1;
173 ResourceSizeMask = IsAGroup ? computeResourceSizeMaskForGroup(ResourceMask)
174 : ((1ULL << Desc.NumUnits) - 1);
175 NextInSequenceMask = ResourceSizeMask;
176 RemovedFromNextInSequence = 0;
177 ReadyMask = ResourceSizeMask;
178 BufferSize = Desc.BufferSize;
179 AvailableSlots = BufferSize == -1 ? 0U : static_cast<unsigned>(BufferSize);
183 unsigned getProcResourceID() const { return ProcResourceDescIndex; }
184 uint64_t getResourceMask() const { return ResourceMask; }
185 int getBufferSize() const { return BufferSize; }
187 bool isBuffered() const { return BufferSize > 0; }
188 bool isInOrder() const { return BufferSize == 1; }
189 bool isADispatchHazard() const { return BufferSize == 0; }
190 bool isReserved() const { return Unavailable; }
192 void setReserved() { Unavailable = true; }
193 void clearReserved() { Unavailable = false; }
195 // A resource is ready if it is not reserved, and if there are enough
197 // If a resource is also a dispatch hazard, then we don't check if
198 // it is reserved because that check would always return true.
199 // A resource marked as "dispatch hazard" is always reserved at
200 // dispatch time. When this method is called, the assumption is that
201 // the user of this resource has been already dispatched.
202 bool isReady(unsigned NumUnits = 1) const {
203 return (!isReserved() || isADispatchHazard()) &&
204 llvm::countPopulation(ReadyMask) >= NumUnits;
206 bool isAResourceGroup() const {
207 return llvm::countPopulation(ResourceMask) > 1;
210 bool containsResource(uint64_t ID) const { return ResourceMask & ID; }
212 void markSubResourceAsUsed(uint64_t ID) {
213 assert(isSubResourceReady(ID));
217 void releaseSubResource(uint64_t ID) {
218 assert(!isSubResourceReady(ID));
222 unsigned getNumUnits() const {
223 return isAResourceGroup() ? 1U : llvm::countPopulation(ResourceSizeMask);
226 uint64_t selectNextInSequence();
227 void removeFromNextInSequence(uint64_t ID);
229 ResourceStateEvent isBufferAvailable() const {
230 if (isADispatchHazard() && isReserved())
232 if (!isBuffered() || AvailableSlots)
233 return RS_BUFFER_AVAILABLE;
234 return RS_BUFFER_UNAVAILABLE;
237 void reserveBuffer() {
242 void releaseBuffer() {
245 assert(AvailableSlots <= static_cast<unsigned>(BufferSize));
253 /// A resource unit identifier.
255 /// This is used to identify a specific processor resource unit using a pair
256 /// of indices where the 'first' index is a processor resource mask, and the
257 /// 'second' index is an index for a "sub-resource" (i.e. unit).
258 typedef std::pair<uint64_t, uint64_t> ResourceRef;
260 // First: a MCProcResourceDesc index identifying a buffered resource.
261 // Second: max number of buffer entries used in this resource.
262 typedef std::pair<unsigned, unsigned> BufferUsageEntry;
264 /// A resource manager for processor resource units and groups.
266 /// This class owns all the ResourceState objects, and it is responsible for
267 /// acting on requests from a Scheduler by updating the internal state of
268 /// ResourceState objects.
269 /// This class doesn't know about instruction itineraries and functional units.
270 /// In future, it can be extended to support itineraries too through the same
271 /// public interface.
272 class ResourceManager {
273 // The resource manager owns all the ResourceState.
274 using UniqueResourceState = std::unique_ptr<ResourceState>;
275 llvm::SmallDenseMap<uint64_t, UniqueResourceState> Resources;
277 // Keeps track of which resources are busy, and how many cycles are left
278 // before those become usable again.
279 llvm::SmallDenseMap<ResourceRef, unsigned> BusyResources;
281 // A table to map processor resource IDs to processor resource masks.
282 llvm::SmallVector<uint64_t, 8> ProcResID2Mask;
284 // Adds a new resource state in Resources, as well as a new descriptor in
285 // ResourceDescriptor.
286 void addResource(const llvm::MCProcResourceDesc &Desc, unsigned Index,
289 // Populate resource descriptors.
290 void initialize(const llvm::MCSchedModel &SM);
292 // Returns the actual resource unit that will be used.
293 ResourceRef selectPipe(uint64_t ResourceID);
295 void use(ResourceRef RR);
296 void release(ResourceRef RR);
298 unsigned getNumUnits(uint64_t ResourceID) const {
299 assert(Resources.find(ResourceID) != Resources.end());
300 return Resources.find(ResourceID)->getSecond()->getNumUnits();
303 // Reserve a specific Resource kind.
304 void reserveBuffer(uint64_t ResourceID) {
305 assert(isBufferAvailable(ResourceID) ==
306 ResourceStateEvent::RS_BUFFER_AVAILABLE);
307 ResourceState &Resource = *Resources[ResourceID];
308 Resource.reserveBuffer();
311 void releaseBuffer(uint64_t ResourceID) {
312 Resources[ResourceID]->releaseBuffer();
315 ResourceStateEvent isBufferAvailable(uint64_t ResourceID) const {
316 const ResourceState &Resource = *Resources.find(ResourceID)->second;
317 return Resource.isBufferAvailable();
320 bool isReady(uint64_t ResourceID, unsigned NumUnits) const {
321 const ResourceState &Resource = *Resources.find(ResourceID)->second;
322 return Resource.isReady(NumUnits);
326 ResourceManager(const llvm::MCSchedModel &SM)
327 : ProcResID2Mask(SM.getNumProcResourceKinds()) {
331 // Returns RS_BUFFER_AVAILABLE if buffered resources are not reserved, and if
332 // there are enough available slots in the buffers.
333 ResourceStateEvent canBeDispatched(llvm::ArrayRef<uint64_t> Buffers) const;
335 // Return the processor resource identifier associated to this Mask.
336 unsigned resolveResourceMask(uint64_t Mask) const {
337 return Resources.find(Mask)->second->getProcResourceID();
340 // Consume a slot in every buffered resource from array 'Buffers'. Resource
341 // units that are dispatch hazards (i.e. BufferSize=0) are marked as reserved.
342 void reserveBuffers(llvm::ArrayRef<uint64_t> Buffers);
344 // Release buffer entries previously allocated by method reserveBuffers.
345 void releaseBuffers(llvm::ArrayRef<uint64_t> Buffers);
347 void reserveResource(uint64_t ResourceID) {
348 ResourceState &Resource = *Resources[ResourceID];
349 assert(!Resource.isReserved());
350 Resource.setReserved();
353 void releaseResource(uint64_t ResourceID) {
354 ResourceState &Resource = *Resources[ResourceID];
355 Resource.clearReserved();
358 // Returns true if all resources are in-order, and there is at least one
359 // resource which is a dispatch hazard (BufferSize = 0).
360 bool mustIssueImmediately(const InstrDesc &Desc);
362 bool canBeIssued(const InstrDesc &Desc) const;
364 void issueInstruction(
365 const InstrDesc &Desc,
366 llvm::SmallVectorImpl<std::pair<ResourceRef, double>> &Pipes);
368 void cycleEvent(llvm::SmallVectorImpl<ResourceRef> &ResourcesFreed);
372 for (const std::pair<uint64_t, UniqueResourceState> &Resource : Resources)
373 Resource.second->dump();
378 /// Class Scheduler is responsible for issuing instructions to pipeline
379 /// resources. Internally, it delegates to a ResourceManager the management of
380 /// processor resources.
381 /// This class is also responsible for tracking the progress of instructions
382 /// from the dispatch stage, until the write-back stage.
384 /// An nstruction dispatched to the Scheduler is initially placed into either
385 /// the 'WaitQueue' or the 'ReadyQueue' depending on the availability of the
386 /// input operands. Instructions in the WaitQueue are ordered by instruction
387 /// index. An instruction is moved from the WaitQueue to the ReadyQueue when
388 /// register operands become available, and all memory dependencies are met.
389 /// Instructions that are moved from the WaitQueue to the ReadyQueue transition
390 /// from state 'IS_AVAILABLE' to state 'IS_READY'.
392 /// At the beginning of each cycle, the Scheduler checks if there are
393 /// instructions in the WaitQueue that can be moved to the ReadyQueue. If the
394 /// ReadyQueue is not empty, then older instructions from the queue are issued
395 /// to the processor pipelines, and the underlying ResourceManager is updated
396 /// accordingly. The ReadyQueue is ordered by instruction index to guarantee
397 /// that the first instructions in the set are also the oldest.
399 /// An Instruction is moved from the ReadyQueue the `IssuedQueue` when it is
400 /// issued to a (one or more) pipeline(s). This event also causes an instruction
401 /// state transition (i.e. from state IS_READY, to state IS_EXECUTING).
402 /// An Instruction leaves the IssuedQueue when it reaches the write-back stage.
404 const llvm::MCSchedModel &SM;
406 // Hardware resources that are managed by this scheduler.
407 std::unique_ptr<ResourceManager> Resources;
408 std::unique_ptr<LSUnit> LSU;
410 // The Backend gets notified when instructions are ready/issued/executed.
411 Backend *const Owner;
413 // The dispatch unit gets notified when instructions are executed.
416 using QueueEntryTy = std::pair<unsigned, Instruction *>;
417 std::map<unsigned, Instruction *> WaitQueue;
418 std::map<unsigned, Instruction *> ReadyQueue;
419 std::map<unsigned, Instruction *> IssuedQueue;
422 notifyInstructionIssued(const InstRef &IR,
423 llvm::ArrayRef<std::pair<ResourceRef, double>> Used);
424 void notifyInstructionExecuted(const InstRef &IR);
425 void notifyInstructionReady(const InstRef &IR);
426 void notifyResourceAvailable(const ResourceRef &RR);
428 // Notify the Backend that buffered resources were consumed.
429 void notifyReservedBuffers(llvm::ArrayRef<uint64_t> Buffers);
430 // Notify the Backend that buffered resources were freed.
431 void notifyReleasedBuffers(llvm::ArrayRef<uint64_t> Buffers);
433 /// Select the next instruction to issue from the ReadyQueue.
434 /// This method gives priority to older instructions.
437 /// Move instructions from the WaitQueue to the ReadyQueue if input operands
438 /// are all available.
439 void promoteToReadyQueue(llvm::SmallVectorImpl<InstRef> &Ready);
441 /// Issue an instruction without updating the ready queue.
442 void issueInstructionImpl(
444 llvm::SmallVectorImpl<std::pair<ResourceRef, double>> &Pipes);
446 void updatePendingQueue(llvm::SmallVectorImpl<InstRef> &Ready);
447 void updateIssuedQueue(llvm::SmallVectorImpl<InstRef> &Executed);
450 Scheduler(Backend *B, const llvm::MCSchedModel &Model, unsigned LoadQueueSize,
451 unsigned StoreQueueSize, bool AssumeNoAlias)
452 : SM(Model), Resources(llvm::make_unique<ResourceManager>(SM)),
453 LSU(llvm::make_unique<LSUnit>(LoadQueueSize, StoreQueueSize,
457 void setDispatchStage(DispatchStage *DispStage) { DS = DispStage; }
459 /// Check if the instruction in 'IR' can be dispatched.
461 /// The DispatchStage is responsible for querying the Scheduler before
462 /// dispatching new instructions. Queries are performed through method
463 /// `Scheduler::canBeDispatched`. If scheduling resources are available,
464 /// and the instruction can be dispatched, then this method returns true.
465 /// Otherwise, a generic HWStallEvent is notified to the listeners.
466 bool canBeDispatched(const InstRef &IR) const;
467 void scheduleInstruction(InstRef &IR);
469 /// Issue an instruction.
470 void issueInstruction(InstRef &IR);
472 /// Reserve one entry in each buffered resource.
473 void reserveBuffers(llvm::ArrayRef<uint64_t> Buffers) {
474 Resources->reserveBuffers(Buffers);
477 /// Release buffer entries previously allocated by method reserveBuffers.
478 void releaseBuffers(llvm::ArrayRef<uint64_t> Buffers) {
479 Resources->releaseBuffers(Buffers);