LLVM  10.0.0svn
ResourceManager.cpp
Go to the documentation of this file.
1 //===--------------------- ResourceManager.cpp ------------------*- 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 
16 #include "llvm/MCA/Support.h"
17 #include "llvm/Support/Debug.h"
19 
20 namespace llvm {
21 namespace mca {
22 
23 #define DEBUG_TYPE "llvm-mca"
25 
26 static uint64_t selectImpl(uint64_t CandidateMask,
27  uint64_t &NextInSequenceMask) {
28  // The upper bit set in CandidateMask identifies our next candidate resource.
29  CandidateMask = 1ULL << getResourceStateIndex(CandidateMask);
30  NextInSequenceMask &= (CandidateMask | (CandidateMask - 1));
31  return CandidateMask;
32 }
33 
34 uint64_t DefaultResourceStrategy::select(uint64_t ReadyMask) {
35  // This method assumes that ReadyMask cannot be zero.
36  uint64_t CandidateMask = ReadyMask & NextInSequenceMask;
37  if (CandidateMask)
38  return selectImpl(CandidateMask, NextInSequenceMask);
39 
40  NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
41  RemovedFromNextInSequence = 0;
42  CandidateMask = ReadyMask & NextInSequenceMask;
43  if (CandidateMask)
44  return selectImpl(CandidateMask, NextInSequenceMask);
45 
46  NextInSequenceMask = ResourceUnitMask;
47  CandidateMask = ReadyMask & NextInSequenceMask;
48  return selectImpl(CandidateMask, NextInSequenceMask);
49 }
50 
52  if (Mask > NextInSequenceMask) {
53  RemovedFromNextInSequence |= Mask;
54  return;
55  }
56 
57  NextInSequenceMask &= (~Mask);
58  if (NextInSequenceMask)
59  return;
60 
61  NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
62  RemovedFromNextInSequence = 0;
63 }
64 
66  uint64_t Mask)
67  : ProcResourceDescIndex(Index), ResourceMask(Mask),
68  BufferSize(Desc.BufferSize), IsAGroup(countPopulation(ResourceMask) > 1) {
69  if (IsAGroup) {
70  ResourceSizeMask =
71  ResourceMask ^ 1ULL << getResourceStateIndex(ResourceMask);
72  } else {
73  ResourceSizeMask = (1ULL << Desc.NumUnits) - 1;
74  }
75  ReadyMask = ResourceSizeMask;
76  AvailableSlots = BufferSize == -1 ? 0U : static_cast<unsigned>(BufferSize);
77  Unavailable = false;
78 }
79 
80 bool ResourceState::isReady(unsigned NumUnits) const {
81  return (!isReserved() || isADispatchHazard()) &&
82  countPopulation(ReadyMask) >= NumUnits;
83 }
84 
86  if (isADispatchHazard() && isReserved())
87  return RS_RESERVED;
88  if (!isBuffered() || AvailableSlots)
89  return RS_BUFFER_AVAILABLE;
90  return RS_BUFFER_UNAVAILABLE;
91 }
92 
93 #ifndef NDEBUG
94 void ResourceState::dump() const {
95  dbgs() << "MASK=" << format_hex(ResourceMask, 16)
96  << ", SZMASK=" << format_hex(ResourceSizeMask, 16)
97  << ", RDYMASK=" << format_hex(ReadyMask, 16)
98  << ", BufferSize=" << BufferSize
99  << ", AvailableSlots=" << AvailableSlots
100  << ", Reserved=" << Unavailable << '\n';
101 }
102 #endif
103 
104 static std::unique_ptr<ResourceStrategy>
106  if (RS.isAResourceGroup() || RS.getNumUnits() > 1)
107  return std::make_unique<DefaultResourceStrategy>(RS.getReadyMask());
108  return std::unique_ptr<ResourceStrategy>(nullptr);
109 }
110 
112  : Resources(SM.getNumProcResourceKinds() - 1),
113  Strategies(SM.getNumProcResourceKinds() - 1),
114  Resource2Groups(SM.getNumProcResourceKinds() - 1, 0),
115  ProcResID2Mask(SM.getNumProcResourceKinds(), 0),
116  ResIndex2ProcResID(SM.getNumProcResourceKinds() - 1, 0),
117  ProcResUnitMask(0), ReservedResourceGroups(0),
118  AvailableBuffers(~0ULL), ReservedBuffers(0) {
119  computeProcResourceMasks(SM, ProcResID2Mask);
120 
121  // initialize vector ResIndex2ProcResID.
122  for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
123  unsigned Index = getResourceStateIndex(ProcResID2Mask[I]);
124  ResIndex2ProcResID[Index] = I;
125  }
126 
127  for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
128  uint64_t Mask = ProcResID2Mask[I];
129  unsigned Index = getResourceStateIndex(Mask);
130  Resources[Index] =
131  std::make_unique<ResourceState>(*SM.getProcResource(I), I, Mask);
132  Strategies[Index] = getStrategyFor(*Resources[Index]);
133  }
134 
135  for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
136  uint64_t Mask = ProcResID2Mask[I];
137  unsigned Index = getResourceStateIndex(Mask);
138  const ResourceState &RS = *Resources[Index];
139  if (!RS.isAResourceGroup()) {
140  ProcResUnitMask |= Mask;
141  continue;
142  }
143 
144  uint64_t GroupMaskIdx = 1ULL << Index;
145  Mask -= GroupMaskIdx;
146  while (Mask) {
147  // Extract lowest set isolated bit.
148  uint64_t Unit = Mask & (-Mask);
149  unsigned IndexUnit = getResourceStateIndex(Unit);
150  Resource2Groups[IndexUnit] |= GroupMaskIdx;
151  Mask ^= Unit;
152  }
153  }
154 
155  AvailableProcResUnits = ProcResUnitMask;
156 }
157 
158 void ResourceManager::setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
159  uint64_t ResourceMask) {
160  unsigned Index = getResourceStateIndex(ResourceMask);
161  assert(Index < Resources.size() && "Invalid processor resource index!");
162  assert(S && "Unexpected null strategy in input!");
163  Strategies[Index] = std::move(S);
164 }
165 
166 unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
167  return ResIndex2ProcResID[getResourceStateIndex(Mask)];
168 }
169 
170 unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
171  return Resources[getResourceStateIndex(ResourceID)]->getNumUnits();
172 }
173 
174 // Returns the actual resource consumed by this Use.
175 // First, is the primary resource ID.
176 // Second, is the specific sub-resource ID.
177 ResourceRef ResourceManager::selectPipe(uint64_t ResourceID) {
178  unsigned Index = getResourceStateIndex(ResourceID);
179  assert(Index < Resources.size() && "Invalid resource use!");
180  ResourceState &RS = *Resources[Index];
181  assert(RS.isReady() && "No available units to select!");
182 
183  // Special case where RS is not a group, and it only declares a single
184  // resource unit.
185  if (!RS.isAResourceGroup() && RS.getNumUnits() == 1)
186  return std::make_pair(ResourceID, RS.getReadyMask());
187 
188  uint64_t SubResourceID = Strategies[Index]->select(RS.getReadyMask());
189  if (RS.isAResourceGroup())
190  return selectPipe(SubResourceID);
191  return std::make_pair(ResourceID, SubResourceID);
192 }
193 
194 void ResourceManager::use(const ResourceRef &RR) {
195  // Mark the sub-resource referenced by RR as used.
196  unsigned RSID = getResourceStateIndex(RR.first);
197  ResourceState &RS = *Resources[RSID];
198  RS.markSubResourceAsUsed(RR.second);
199  // Remember to update the resource strategy for non-group resources with
200  // multiple units.
201  if (RS.getNumUnits() > 1)
202  Strategies[RSID]->used(RR.second);
203 
204  // If there are still available units in RR.first,
205  // then we are done.
206  if (RS.isReady())
207  return;
208 
209  AvailableProcResUnits ^= RR.first;
210 
211  // Notify groups that RR.first is no longer available.
212  uint64_t Users = Resource2Groups[RSID];
213  while (Users) {
214  // Extract lowest set isolated bit.
215  unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
216  ResourceState &CurrentUser = *Resources[GroupIndex];
217  CurrentUser.markSubResourceAsUsed(RR.first);
218  Strategies[GroupIndex]->used(RR.first);
219  // Reset lowest set bit.
220  Users &= Users - 1;
221  }
222 }
223 
224 void ResourceManager::release(const ResourceRef &RR) {
225  unsigned RSID = getResourceStateIndex(RR.first);
226  ResourceState &RS = *Resources[RSID];
227  bool WasFullyUsed = !RS.isReady();
228  RS.releaseSubResource(RR.second);
229  if (!WasFullyUsed)
230  return;
231 
232  AvailableProcResUnits ^= RR.first;
233 
234  // Notify groups that RR.first is now available again.
235  uint64_t Users = Resource2Groups[RSID];
236  while (Users) {
237  unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
238  ResourceState &CurrentUser = *Resources[GroupIndex];
239  CurrentUser.releaseSubResource(RR.first);
240  Users &= Users - 1;
241  }
242 }
243 
245 ResourceManager::canBeDispatched(uint64_t ConsumedBuffers) const {
246  if (ConsumedBuffers & ReservedBuffers)
248  if (ConsumedBuffers & (~AvailableBuffers))
251 }
252 
253 void ResourceManager::reserveBuffers(uint64_t ConsumedBuffers) {
254  while (ConsumedBuffers) {
255  uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
256  ResourceState &RS = *Resources[getResourceStateIndex(CurrentBuffer)];
257  ConsumedBuffers ^= CurrentBuffer;
258  assert(RS.isBufferAvailable() == ResourceStateEvent::RS_BUFFER_AVAILABLE);
259  if (!RS.reserveBuffer())
260  AvailableBuffers ^= CurrentBuffer;
261  if (RS.isADispatchHazard()) {
262  // Reserve this buffer now, and release it once pipeline resources
263  // consumed by the instruction become available again.
264  // We do this to simulate an in-order dispatch/issue of instructions.
265  ReservedBuffers ^= CurrentBuffer;
266  }
267  }
268 }
269 
270 void ResourceManager::releaseBuffers(uint64_t ConsumedBuffers) {
271  AvailableBuffers |= ConsumedBuffers;
272  while (ConsumedBuffers) {
273  uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
274  ResourceState &RS = *Resources[getResourceStateIndex(CurrentBuffer)];
275  ConsumedBuffers ^= CurrentBuffer;
276  RS.releaseBuffer();
277  // Do not unreserve dispatch hazard resource buffers. Wait until all
278  // pipeline resources have been freed too.
279  }
280 }
281 
282 uint64_t ResourceManager::checkAvailability(const InstrDesc &Desc) const {
283  uint64_t BusyResourceMask = 0;
284  for (const std::pair<uint64_t, const ResourceUsage> &E : Desc.Resources) {
285  unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
286  unsigned Index = getResourceStateIndex(E.first);
287  if (!Resources[Index]->isReady(NumUnits))
288  BusyResourceMask |= E.first;
289  }
290 
291  BusyResourceMask &= ProcResUnitMask;
292  if (BusyResourceMask)
293  return BusyResourceMask;
294  return Desc.UsedProcResGroups & ReservedResourceGroups;
295 }
296 
298  const InstrDesc &Desc,
299  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
300  for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
301  const CycleSegment &CS = R.second.CS;
302  if (!CS.size()) {
303  releaseResource(R.first);
304  continue;
305  }
306 
307  assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
308  if (!R.second.isReserved()) {
309  ResourceRef Pipe = selectPipe(R.first);
310  use(Pipe);
311  BusyResources[Pipe] += CS.size();
312  Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
313  Pipe, ResourceCycles(CS.size())));
314  } else {
315  assert((countPopulation(R.first) > 1) && "Expected a group!");
316  // Mark this group as reserved.
317  assert(R.second.isReserved());
318  reserveResource(R.first);
319  BusyResources[ResourceRef(R.first, R.first)] += CS.size();
320  }
321  }
322 }
323 
325  for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
326  if (BR.second)
327  BR.second--;
328  if (!BR.second) {
329  // Release this resource.
330  const ResourceRef &RR = BR.first;
331 
332  if (countPopulation(RR.first) == 1)
333  release(RR);
334  releaseResource(RR.first);
335  ResourcesFreed.push_back(RR);
336  }
337  }
338 
339  for (const ResourceRef &RF : ResourcesFreed)
340  BusyResources.erase(RF);
341 }
342 
343 void ResourceManager::reserveResource(uint64_t ResourceID) {
344  const unsigned Index = getResourceStateIndex(ResourceID);
345  ResourceState &Resource = *Resources[Index];
346  assert(Resource.isAResourceGroup() && !Resource.isReserved() &&
347  "Unexpected resource state found!");
348  Resource.setReserved();
349  ReservedResourceGroups ^= 1ULL << Index;
350 }
351 
352 void ResourceManager::releaseResource(uint64_t ResourceID) {
353  const unsigned Index = getResourceStateIndex(ResourceID);
354  ResourceState &Resource = *Resources[Index];
355  Resource.clearReserved();
356  if (Resource.isAResourceGroup())
357  ReservedResourceGroups ^= 1ULL << Index;
358  // Now it is safe to release dispatch/issue resources.
359  if (Resource.isADispatchHazard())
360  ReservedBuffers ^= 1ULL << Index;
361 }
362 
363 } // namespace mca
364 } // namespace llvm
A sequence of cycles.
Definition: Instruction.h:290
ResourceManager(const MCSchedModel &SM)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
FormattedNumber format_hex(uint64_t N, unsigned Width, bool Upper=false)
format_hex - Output N as a fixed width hexadecimal.
Definition: Format.h:186
static uint64_t selectImpl(uint64_t CandidateMask, uint64_t &NextInSequenceMask)
void markSubResourceAsUsed(uint64_t ID)
const MCProcResourceDesc * getProcResource(unsigned ProcResourceIdx) const
Definition: MCSchedule.h:339
iv Induction Variable Users
Definition: IVUsers.cpp:51
static std::unique_ptr< ResourceStrategy > getStrategyFor(const ResourceState &RS)
void reserveResource(uint64_t ResourceID)
void issueInstruction(const InstrDesc &Desc, SmallVectorImpl< std::pair< ResourceRef, ResourceCycles >> &Pipes)
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
unsigned getNumUnits() const
bool isReady(unsigned NumUnits=1) const
Returs true if this resource is not reserved, and if there are at least NumUnits available units...
void computeProcResourceMasks(const MCSchedModel &SM, MutableArrayRef< uint64_t > Masks)
Populates vector Masks with processor resource masks.
Definition: Support.cpp:39
ResourceStateEvent isBufferAvailable() const
Checks if there is an available slot in the resource buffer.
void releaseResource(uint64_t ResourceID)
uint64_t getReadyMask() const
uint64_t UsedProcResGroups
Definition: Instruction.h:363
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:665
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
uint64_t checkAvailability(const InstrDesc &Desc) const
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.
SmallVector< std::pair< uint64_t, ResourceUsage >, 4 > Resources
Definition: Instruction.h:354
ResourceStateEvent
Used to notify the internal state of a processor resource.
void reserveBuffers(uint64_t ConsumedBuffers)
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:556
void used(uint64_t Mask) override
Called by the ResourceManager when a processor resource group, or a processor resource with multiple ...
Define a kind of processor resource that will be modeled by the scheduler.
Definition: MCSchedule.h:32
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
The classes here represent processor resource units and their management strategy.
This class represents the number of cycles per resource (fractions of cycles).
Definition: Support.h:50
unsigned begin() const
Definition: Instruction.h:325
An instruction descriptor.
Definition: Instruction.h:348
void releaseBuffers(uint64_t ConsumedBuffers)
uint64_t select(uint64_t ReadyMask) override
Selects a processor resource unit from a ReadyMask.
A processor resource descriptor.
unsigned getResourceStateIndex(uint64_t Mask)
Definition: Support.h:99
void cycleEvent(SmallVectorImpl< ResourceRef > &ResourcesFreed)
#define I(x, y, z)
Definition: MD5.cpp:58
void releaseSubResource(uint64_t ID)
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
unsigned resolveResourceMask(uint64_t Mask) const
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:244
ResourceStateEvent canBeDispatched(uint64_t ConsumedBuffers) const
ResourceState(const MCProcResourceDesc &Desc, unsigned Index, uint64_t Mask)
unsigned size() const
Definition: Instruction.h:319
unsigned getNumProcResourceKinds() const
Definition: MCSchedule.h:335