LLVM  10.0.0svn
ResourceManager.h
Go to the documentation of this file.
1 //===--------------------- ResourceManager.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 /// The classes here represent processor resource units and their management
11 /// strategy. These classes are managed by the Scheduler.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_MCA_RESOURCE_MANAGER_H
16 #define LLVM_MCA_RESOURCE_MANAGER_H
17 
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/MC/MCSchedule.h"
22 #include "llvm/MCA/Instruction.h"
23 #include "llvm/MCA/Support.h"
24 
25 namespace llvm {
26 namespace mca {
27 
28 /// Used to notify the internal state of a processor resource.
29 ///
30 /// A processor resource is available if it is not reserved, and there are
31 /// available slots in the buffer. A processor resource is unavailable if it
32 /// is either reserved, or the associated buffer is full. A processor resource
33 /// with a buffer size of -1 is always available if it is not reserved.
34 ///
35 /// Values of type ResourceStateEvent are returned by method
36 /// ResourceManager::canBeDispatched()
37 ///
38 /// The naming convention for resource state events is:
39 /// * Event names start with prefix RS_
40 /// * Prefix RS_ is followed by a string describing the actual resource state.
45 };
46 
47 /// Resource allocation strategy used by hardware scheduler resources.
49  ResourceStrategy(const ResourceStrategy &) = delete;
50  ResourceStrategy &operator=(const ResourceStrategy &) = delete;
51 
52 public:
54  virtual ~ResourceStrategy();
55 
56  /// Selects a processor resource unit from a ReadyMask.
57  virtual uint64_t select(uint64_t ReadyMask) = 0;
58 
59  /// Called by the ResourceManager when a processor resource group, or a
60  /// processor resource with multiple units has become unavailable.
61  ///
62  /// The default strategy uses this information to bias its selection logic.
63  virtual void used(uint64_t ResourceMask) {}
64 };
65 
66 /// Default resource allocation strategy used by processor resource groups and
67 /// processor resources with multiple units.
69  /// A Mask of resource unit identifiers.
70  ///
71  /// There is one bit set for every available resource unit.
72  /// It defaults to the value of field ResourceSizeMask in ResourceState.
73  const uint64_t ResourceUnitMask;
74 
75  /// A simple round-robin selector for processor resource units.
76  /// Each bit of this mask identifies a sub resource within a group.
77  ///
78  /// As an example, lets assume that this is a default policy for a
79  /// processor resource group composed by the following three units:
80  /// ResourceA -- 0b001
81  /// ResourceB -- 0b010
82  /// ResourceC -- 0b100
83  ///
84  /// Field NextInSequenceMask is used to select the next unit from the set of
85  /// resource units. It defaults to the value of field `ResourceUnitMasks` (in
86  /// this example, it defaults to mask '0b111').
87  ///
88  /// The round-robin selector would firstly select 'ResourceC', then
89  /// 'ResourceB', and eventually 'ResourceA'. When a resource R is used, the
90  /// corresponding bit in NextInSequenceMask is cleared. For example, if
91  /// 'ResourceC' is selected, then the new value of NextInSequenceMask becomes
92  /// 0xb011.
93  ///
94  /// When NextInSequenceMask becomes zero, it is automatically reset to the
95  /// default value (i.e. ResourceUnitMask).
96  uint64_t NextInSequenceMask;
97 
98  /// This field is used to track resource units that are used (i.e. selected)
99  /// by other groups other than the one associated with this strategy object.
100  ///
101  /// In LLVM processor resource groups are allowed to partially (or fully)
102  /// overlap. That means, a same unit may be visible to multiple groups.
103  /// This field keeps track of uses that have originated from outside of
104  /// this group. The idea is to bias the selection strategy, so that resources
105  /// that haven't been used by other groups get prioritized.
106  ///
107  /// The end goal is to (try to) keep the resource distribution as much uniform
108  /// as possible. By construction, this mask only tracks one-level of resource
109  /// usage. Therefore, this strategy is expected to be less accurate when same
110  /// units are used multiple times by other groups within a single round of
111  /// select.
112  ///
113  /// Note: an LRU selector would have a better accuracy at the cost of being
114  /// slightly more expensive (mostly in terms of runtime cost). Methods
115  /// 'select' and 'used', are always in the hot execution path of llvm-mca.
116  /// Therefore, a slow implementation of 'select' would have a negative impact
117  /// on the overall performance of the tool.
118  uint64_t RemovedFromNextInSequence;
119 
120 public:
121  DefaultResourceStrategy(uint64_t UnitMask)
122  : ResourceStrategy(), ResourceUnitMask(UnitMask),
123  NextInSequenceMask(UnitMask), RemovedFromNextInSequence(0) {}
124  virtual ~DefaultResourceStrategy() = default;
125 
126  uint64_t select(uint64_t ReadyMask) override;
127  void used(uint64_t Mask) override;
128 };
129 
130 /// A processor resource descriptor.
131 ///
132 /// There is an instance of this class for every processor resource defined by
133 /// the machine scheduling model.
134 /// Objects of class ResourceState dynamically track the usage of processor
135 /// resource units.
137  /// An index to the MCProcResourceDesc entry in the processor model.
138  const unsigned ProcResourceDescIndex;
139  /// A resource mask. This is generated by the tool with the help of
140  /// function `mca::computeProcResourceMasks' (see Support.h).
141  ///
142  /// Field ResourceMask only has one bit set if this resource state describes a
143  /// processor resource unit (i.e. this is not a group). That means, we can
144  /// quickly check if a resource is a group by simply counting the number of
145  /// bits that are set in the mask.
146  ///
147  /// The most significant bit of a mask (MSB) uniquely identifies a resource.
148  /// Remaining bits are used to describe the composition of a group (Group).
149  ///
150  /// Example (little endian):
151  /// Resource | Mask | MSB | Group
152  /// ---------+------------+------------+------------
153  /// A | 0b000001 | 0b000001 | 0b000000
154  /// | | |
155  /// B | 0b000010 | 0b000010 | 0b000000
156  /// | | |
157  /// C | 0b010000 | 0b010000 | 0b000000
158  /// | | |
159  /// D | 0b110010 | 0b100000 | 0b010010
160  ///
161  /// In this example, resources A, B and C are processor resource units.
162  /// Only resource D is a group resource, and it contains resources B and C.
163  /// That is because MSB(B) and MSB(C) are both contained within Group(D).
164  const uint64_t ResourceMask;
165 
166  /// A ProcResource can have multiple units.
167  ///
168  /// For processor resource groups this field is a mask of contained resource
169  /// units. It is obtained from ResourceMask by clearing the highest set bit.
170  /// The number of resource units in a group can be simply computed as the
171  /// population count of this field.
172  ///
173  /// For normal (i.e. non-group) resources, the number of bits set in this mask
174  /// is equivalent to the number of units declared by the processor model (see
175  /// field 'NumUnits' in 'ProcResourceUnits').
176  uint64_t ResourceSizeMask;
177 
178  /// A mask of ready units.
179  uint64_t ReadyMask;
180 
181  /// Buffered resources will have this field set to a positive number different
182  /// than zero. A buffered resource behaves like a reservation station
183  /// implementing its own buffer for out-of-order execution.
184  ///
185  /// A BufferSize of 1 is used by scheduler resources that force in-order
186  /// execution.
187  ///
188  /// A BufferSize of 0 is used to model in-order issue/dispatch resources.
189  /// Since in-order issue/dispatch resources don't implement buffers, dispatch
190  /// events coincide with issue events.
191  /// Also, no other instruction ca be dispatched/issue while this resource is
192  /// in use. Only when all the "resource cycles" are consumed (after the issue
193  /// event), a new instruction ca be dispatched.
194  const int BufferSize;
195 
196  /// Available slots in the buffer (zero, if this is not a buffered resource).
197  unsigned AvailableSlots;
198 
199  /// This field is set if this resource is currently reserved.
200  ///
201  /// Resources can be reserved for a number of cycles.
202  /// Instructions can still be dispatched to reserved resources. However,
203  /// istructions dispatched to a reserved resource cannot be issued to the
204  /// underlying units (i.e. pipelines) until the resource is released.
205  bool Unavailable;
206 
207  const bool IsAGroup;
208 
209  /// Checks for the availability of unit 'SubResMask' in the group.
210  bool isSubResourceReady(uint64_t SubResMask) const {
211  return ReadyMask & SubResMask;
212  }
213 
214 public:
215  ResourceState(const MCProcResourceDesc &Desc, unsigned Index, uint64_t Mask);
216 
217  unsigned getProcResourceID() const { return ProcResourceDescIndex; }
218  uint64_t getResourceMask() const { return ResourceMask; }
219  uint64_t getReadyMask() const { return ReadyMask; }
220  int getBufferSize() const { return BufferSize; }
221 
222  bool isBuffered() const { return BufferSize > 0; }
223  bool isInOrder() const { return BufferSize == 1; }
224 
225  /// Returns true if this is an in-order dispatch/issue resource.
226  bool isADispatchHazard() const { return BufferSize == 0; }
227  bool isReserved() const { return Unavailable; }
228 
229  void setReserved() { Unavailable = true; }
230  void clearReserved() { Unavailable = false; }
231 
232  /// Returs true if this resource is not reserved, and if there are at least
233  /// `NumUnits` available units.
234  bool isReady(unsigned NumUnits = 1) const;
235 
236  bool isAResourceGroup() const { return IsAGroup; }
237 
238  bool containsResource(uint64_t ID) const { return ResourceMask & ID; }
239 
240  void markSubResourceAsUsed(uint64_t ID) {
241  assert(isSubResourceReady(ID));
242  ReadyMask ^= ID;
243  }
244 
245  void releaseSubResource(uint64_t ID) {
246  assert(!isSubResourceReady(ID));
247  ReadyMask ^= ID;
248  }
249 
250  unsigned getNumUnits() const {
251  return isAResourceGroup() ? 1U : countPopulation(ResourceSizeMask);
252  }
253 
254  /// Checks if there is an available slot in the resource buffer.
255  ///
256  /// Returns RS_BUFFER_AVAILABLE if this is not a buffered resource, or if
257  /// there is a slot available.
258  ///
259  /// Returns RS_RESERVED if this buffered resource is a dispatch hazard, and it
260  /// is reserved.
261  ///
262  /// Returns RS_BUFFER_UNAVAILABLE if there are no available slots.
263  ResourceStateEvent isBufferAvailable() const;
264 
265  /// Reserve a buffer slot.
266  ///
267  /// Returns true if the buffer is not full.
268  /// It always returns true if BufferSize is set to zero.
269  bool reserveBuffer() {
270  if (BufferSize <= 0)
271  return true;
272 
273  --AvailableSlots;
274  assert(AvailableSlots <= static_cast<unsigned>(BufferSize));
275  return AvailableSlots;
276  }
277 
278  /// Releases a slot in the buffer.
279  void releaseBuffer() {
280  // Ignore dispatch hazards or invalid buffer sizes.
281  if (BufferSize <= 0)
282  return;
283 
284  ++AvailableSlots;
285  assert(AvailableSlots <= static_cast<unsigned>(BufferSize));
286  }
287 
288 #ifndef NDEBUG
289  void dump() const;
290 #endif
291 };
292 
293 /// A resource unit identifier.
294 ///
295 /// This is used to identify a specific processor resource unit using a pair
296 /// of indices where the 'first' index is a processor resource mask, and the
297 /// 'second' index is an index for a "sub-resource" (i.e. unit).
298 typedef std::pair<uint64_t, uint64_t> ResourceRef;
299 
300 // First: a MCProcResourceDesc index identifying a buffered resource.
301 // Second: max number of buffer entries used in this resource.
302 typedef std::pair<unsigned, unsigned> BufferUsageEntry;
303 
304 /// A resource manager for processor resource units and groups.
305 ///
306 /// This class owns all the ResourceState objects, and it is responsible for
307 /// acting on requests from a Scheduler by updating the internal state of
308 /// ResourceState objects.
309 /// This class doesn't know about instruction itineraries and functional units.
310 /// In future, it can be extended to support itineraries too through the same
311 /// public interface.
313  // Set of resources available on the subtarget.
314  //
315  // There is an instance of ResourceState for every resource declared by the
316  // target scheduling model.
317  //
318  // Elements of this vector are ordered by resource kind. In particular,
319  // resource units take precedence over resource groups.
320  //
321  // The index of a processor resource in this vector depends on the value of
322  // its mask (see the description of field ResourceState::ResourceMask). In
323  // particular, it is computed as the position of the most significant bit set
324  // (MSB) in the mask plus one (since we want to ignore the invalid resource
325  // descriptor at index zero).
326  //
327  // Example (little endian):
328  //
329  // Resource | Mask | MSB | Index
330  // ---------+---------+---------+-------
331  // A | 0b00001 | 0b00001 | 1
332  // | | |
333  // B | 0b00100 | 0b00100 | 3
334  // | | |
335  // C | 0b10010 | 0b10000 | 5
336  //
337  //
338  // The same index is also used to address elements within vector `Strategies`
339  // and vector `Resource2Groups`.
340  std::vector<std::unique_ptr<ResourceState>> Resources;
341  std::vector<std::unique_ptr<ResourceStrategy>> Strategies;
342 
343  // Used to quickly identify groups that own a particular resource unit.
344  std::vector<uint64_t> Resource2Groups;
345 
346  // A table that maps processor resource IDs to processor resource masks.
347  SmallVector<uint64_t, 8> ProcResID2Mask;
348 
349  // A table that maps resource indices to actual processor resource IDs in the
350  // scheduling model.
351  SmallVector<unsigned, 8> ResIndex2ProcResID;
352 
353  // Keeps track of which resources are busy, and how many cycles are left
354  // before those become usable again.
356 
357  // Set of processor resource units available on the target.
358  uint64_t ProcResUnitMask;
359 
360  // Set of processor resource units that are available during this cycle.
361  uint64_t AvailableProcResUnits;
362 
363  // Set of processor resources that are currently reserved.
364  uint64_t ReservedResourceGroups;
365 
366  // Set of unavailable scheduler buffer resources. This is used internally to
367  // speedup `canBeDispatched()` queries.
368  uint64_t AvailableBuffers;
369 
370  // Set of dispatch hazard buffer resources that are currently unavailable.
371  uint64_t ReservedBuffers;
372 
373  // Returns the actual resource unit that will be used.
374  ResourceRef selectPipe(uint64_t ResourceID);
375 
376  void use(const ResourceRef &RR);
377  void release(const ResourceRef &RR);
378 
379  unsigned getNumUnits(uint64_t ResourceID) const;
380 
381  // Overrides the selection strategy for the processor resource with the given
382  // mask.
383  void setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
384  uint64_t ResourceMask);
385 
386 public:
387  ResourceManager(const MCSchedModel &SM);
388  virtual ~ResourceManager() = default;
389 
390  // Overrides the selection strategy for the resource at index ResourceID in
391  // the MCProcResourceDesc table.
392  void setCustomStrategy(std::unique_ptr<ResourceStrategy> S,
393  unsigned ResourceID) {
394  assert(ResourceID < ProcResID2Mask.size() &&
395  "Invalid resource index in input!");
396  return setCustomStrategyImpl(std::move(S), ProcResID2Mask[ResourceID]);
397  }
398 
399  // Returns RS_BUFFER_AVAILABLE if buffered resources are not reserved, and if
400  // there are enough available slots in the buffers.
401  ResourceStateEvent canBeDispatched(uint64_t ConsumedBuffers) const;
402 
403  // Return the processor resource identifier associated to this Mask.
404  unsigned resolveResourceMask(uint64_t Mask) const;
405 
406  // Acquires a slot from every buffered resource in mask `ConsumedBuffers`.
407  // Units that are dispatch hazards (i.e. BufferSize=0) are marked as reserved.
408  void reserveBuffers(uint64_t ConsumedBuffers);
409 
410  // Releases a slot from every buffered resource in mask `ConsumedBuffers`.
411  // ConsumedBuffers is a bitmask of previously acquired buffers (using method
412  // `reserveBuffers`). Units that are dispatch hazards (i.e. BufferSize=0) are
413  // not automatically unreserved by this method.
414  void releaseBuffers(uint64_t ConsumedBuffers);
415 
416  // Reserve a processor resource. A reserved resource is not available for
417  // instruction issue until it is released.
418  void reserveResource(uint64_t ResourceID);
419 
420  // Release a previously reserved processor resource.
421  void releaseResource(uint64_t ResourceID);
422 
423  // Returns a zero mask if resources requested by Desc are all available during
424  // this cycle. It returns a non-zero mask value only if there are unavailable
425  // processor resources; each bit set in the mask represents a busy processor
426  // resource unit or a reserved processor resource group.
427  uint64_t checkAvailability(const InstrDesc &Desc) const;
428 
429  uint64_t getProcResUnitMask() const { return ProcResUnitMask; }
430  uint64_t getAvailableProcResUnits() const { return AvailableProcResUnits; }
431 
432  void issueInstruction(
433  const InstrDesc &Desc,
434  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes);
435 
436  void cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed);
437 
438 #ifndef NDEBUG
439  void dump() const {
440  for (const std::unique_ptr<ResourceState> &Resource : Resources)
441  Resource->dump();
442  }
443 #endif
444 };
445 } // namespace mca
446 } // namespace llvm
447 
448 #endif // LLVM_MCA_RESOURCE_MANAGER_H
A resource manager for processor resource units and groups.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void setCustomStrategy(std::unique_ptr< ResourceStrategy > S, unsigned ResourceID)
void markSubResourceAsUsed(uint64_t ID)
bool containsResource(uint64_t ID) const
virtual void used(uint64_t ResourceMask)
Called by the ResourceManager when a processor resource group, or a processor resource with multiple ...
uint64_t getResourceMask() const
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
virtual uint64_t select(uint64_t ReadyMask)=0
Selects a processor resource unit from a ReadyMask.
unsigned getNumUnits() const
uint64_t getReadyMask() const
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Move duplicate certain instructions close to their use
Definition: Localizer.cpp:27
void releaseBuffer()
Releases a slot in the buffer.
std::pair< uint64_t, uint64_t > ResourceRef
A resource unit identifier.
bool isADispatchHazard() const
Returns true if this is an in-order dispatch/issue resource.
Helper functions used by various pipeline components.
size_t size() const
Definition: SmallVector.h:52
ResourceStateEvent
Used to notify the internal state of a processor resource.
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:519
uint64_t getAvailableProcResUnits() const
Define a kind of processor resource that will be modeled by the scheduler.
Definition: MCSchedule.h:32
std::pair< unsigned, unsigned > BufferUsageEntry
An instruction descriptor.
Definition: Instruction.h:348
A processor resource descriptor.
bool reserveBuffer()
Reserve a buffer slot.
This file defines abstractions used by the Pipeline to model register reads, register writes and inst...
void releaseSubResource(uint64_t ID)
DefaultResourceStrategy(uint64_t UnitMask)
unsigned getProcResourceID() const
Default resource allocation strategy used by processor resource groups and processor resources with m...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
Resource allocation strategy used by hardware scheduler resources.
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:244
uint64_t getProcResUnitMask() const