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 llvm::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  computeProcResourceMasks(SM, ProcResID2Mask);
119 
120  // initialize vector ResIndex2ProcResID.
121  for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
122  unsigned Index = getResourceStateIndex(ProcResID2Mask[I]);
123  ResIndex2ProcResID[Index] = I;
124  }
125 
126  for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
127  uint64_t Mask = ProcResID2Mask[I];
128  unsigned Index = getResourceStateIndex(Mask);
129  Resources[Index] =
130  llvm::make_unique<ResourceState>(*SM.getProcResource(I), I, Mask);
131  Strategies[Index] = getStrategyFor(*Resources[Index]);
132  }
133 
134  for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
135  uint64_t Mask = ProcResID2Mask[I];
136  unsigned Index = getResourceStateIndex(Mask);
137  const ResourceState &RS = *Resources[Index];
138  if (!RS.isAResourceGroup()) {
139  ProcResUnitMask |= Mask;
140  continue;
141  }
142 
143  uint64_t GroupMaskIdx = 1ULL << Index;
144  Mask -= GroupMaskIdx;
145  while (Mask) {
146  // Extract lowest set isolated bit.
147  uint64_t Unit = Mask & (-Mask);
148  unsigned IndexUnit = getResourceStateIndex(Unit);
149  Resource2Groups[IndexUnit] |= GroupMaskIdx;
150  Mask ^= Unit;
151  }
152  }
153 
154  AvailableProcResUnits = ProcResUnitMask;
155 }
156 
157 void ResourceManager::setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
158  uint64_t ResourceMask) {
159  unsigned Index = getResourceStateIndex(ResourceMask);
160  assert(Index < Resources.size() && "Invalid processor resource index!");
161  assert(S && "Unexpected null strategy in input!");
162  Strategies[Index] = std::move(S);
163 }
164 
165 unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
166  return ResIndex2ProcResID[getResourceStateIndex(Mask)];
167 }
168 
169 unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
170  return Resources[getResourceStateIndex(ResourceID)]->getNumUnits();
171 }
172 
173 // Returns the actual resource consumed by this Use.
174 // First, is the primary resource ID.
175 // Second, is the specific sub-resource ID.
176 ResourceRef ResourceManager::selectPipe(uint64_t ResourceID) {
177  unsigned Index = getResourceStateIndex(ResourceID);
178  assert(Index < Resources.size() && "Invalid resource use!");
179  ResourceState &RS = *Resources[Index];
180  assert(RS.isReady() && "No available units to select!");
181 
182  // Special case where RS is not a group, and it only declares a single
183  // resource unit.
184  if (!RS.isAResourceGroup() && RS.getNumUnits() == 1)
185  return std::make_pair(ResourceID, RS.getReadyMask());
186 
187  uint64_t SubResourceID = Strategies[Index]->select(RS.getReadyMask());
188  if (RS.isAResourceGroup())
189  return selectPipe(SubResourceID);
190  return std::make_pair(ResourceID, SubResourceID);
191 }
192 
193 void ResourceManager::use(const ResourceRef &RR) {
194  // Mark the sub-resource referenced by RR as used.
195  unsigned RSID = getResourceStateIndex(RR.first);
196  ResourceState &RS = *Resources[RSID];
197  RS.markSubResourceAsUsed(RR.second);
198  // Remember to update the resource strategy for non-group resources with
199  // multiple units.
200  if (RS.getNumUnits() > 1)
201  Strategies[RSID]->used(RR.second);
202 
203  // If there are still available units in RR.first,
204  // then we are done.
205  if (RS.isReady())
206  return;
207 
208  AvailableProcResUnits ^= RR.first;
209 
210  // Notify groups that RR.first is no longer available.
211  uint64_t Users = Resource2Groups[RSID];
212  while (Users) {
213  // Extract lowest set isolated bit.
214  unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
215  ResourceState &CurrentUser = *Resources[GroupIndex];
216  CurrentUser.markSubResourceAsUsed(RR.first);
217  Strategies[GroupIndex]->used(RR.first);
218  // Reset lowest set bit.
219  Users &= Users - 1;
220  }
221 }
222 
223 void ResourceManager::release(const ResourceRef &RR) {
224  unsigned RSID = getResourceStateIndex(RR.first);
225  ResourceState &RS = *Resources[RSID];
226  bool WasFullyUsed = !RS.isReady();
227  RS.releaseSubResource(RR.second);
228  if (!WasFullyUsed)
229  return;
230 
231  AvailableProcResUnits ^= RR.first;
232 
233  // Notify groups that RR.first is now available again.
234  uint64_t Users = Resource2Groups[RSID];
235  while (Users) {
236  unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
237  ResourceState &CurrentUser = *Resources[GroupIndex];
238  CurrentUser.releaseSubResource(RR.first);
239  Users &= Users - 1;
240  }
241 }
242 
246  for (uint64_t Buffer : Buffers) {
247  ResourceState &RS = *Resources[getResourceStateIndex(Buffer)];
248  Result = RS.isBufferAvailable();
250  break;
251  }
252  return Result;
253 }
254 
256  for (const uint64_t Buffer : Buffers) {
257  ResourceState &RS = *Resources[getResourceStateIndex(Buffer)];
259  RS.reserveBuffer();
260 
261  if (RS.isADispatchHazard()) {
262  assert(!RS.isReserved());
263  RS.setReserved();
264  }
265  }
266 }
267 
269  for (const uint64_t R : Buffers)
270  Resources[getResourceStateIndex(R)]->releaseBuffer();
271 }
272 
273 uint64_t ResourceManager::checkAvailability(const InstrDesc &Desc) const {
274  uint64_t BusyResourceMask = 0;
275  for (const std::pair<uint64_t, const ResourceUsage> &E : Desc.Resources) {
276  unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
277  unsigned Index = getResourceStateIndex(E.first);
278  if (!Resources[Index]->isReady(NumUnits))
279  BusyResourceMask |= E.first;
280  }
281 
282  BusyResourceMask &= ProcResUnitMask;
283  if (BusyResourceMask)
284  return BusyResourceMask;
285  return Desc.UsedProcResGroups & ReservedResourceGroups;
286 }
287 
289  const InstrDesc &Desc,
290  SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
291  for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
292  const CycleSegment &CS = R.second.CS;
293  if (!CS.size()) {
294  releaseResource(R.first);
295  continue;
296  }
297 
298  assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
299  if (!R.second.isReserved()) {
300  ResourceRef Pipe = selectPipe(R.first);
301  use(Pipe);
302  BusyResources[Pipe] += CS.size();
303  Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
304  Pipe, ResourceCycles(CS.size())));
305  } else {
306  assert((countPopulation(R.first) > 1) && "Expected a group!");
307  // Mark this group as reserved.
308  assert(R.second.isReserved());
309  reserveResource(R.first);
310  BusyResources[ResourceRef(R.first, R.first)] += CS.size();
311  }
312  }
313 }
314 
316  for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
317  if (BR.second)
318  BR.second--;
319  if (!BR.second) {
320  // Release this resource.
321  const ResourceRef &RR = BR.first;
322 
323  if (countPopulation(RR.first) == 1)
324  release(RR);
325 
326  releaseResource(RR.first);
327  ResourcesFreed.push_back(RR);
328  }
329  }
330 
331  for (const ResourceRef &RF : ResourcesFreed)
332  BusyResources.erase(RF);
333 }
334 
335 void ResourceManager::reserveResource(uint64_t ResourceID) {
336  const unsigned Index = getResourceStateIndex(ResourceID);
337  ResourceState &Resource = *Resources[Index];
338  assert(Resource.isAResourceGroup() && !Resource.isReserved() &&
339  "Unexpected resource found!");
340  Resource.setReserved();
341  ReservedResourceGroups ^= 1ULL << Index;
342 }
343 
344 void ResourceManager::releaseResource(uint64_t ResourceID) {
345  const unsigned Index = getResourceStateIndex(ResourceID);
346  ResourceState &Resource = *Resources[Index];
347  Resource.clearReserved();
348  if (Resource.isAResourceGroup())
349  ReservedResourceGroups ^= 1ULL << Index;
350 }
351 
352 } // namespace mca
353 } // namespace llvm
A sequence of cycles.
Definition: Instruction.h:289
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:185
unsigned UsedProcResGroups
Definition: Instruction.h:359
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
void releaseBuffers(ArrayRef< uint64_t > Buffers)
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
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:657
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.
void reserveBuffer()
Reserve a slot in the buffer.
Helper functions used by various pipeline components.
SmallVector< std::pair< uint64_t, ResourceUsage >, 4 > Resources
Definition: Instruction.h:353
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
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:324
An instruction descriptor.
Definition: Instruction.h:347
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)
ResourceStateEvent canBeDispatched(ArrayRef< uint64_t > Buffers) const
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
void reserveBuffers(ArrayRef< uint64_t > Buffers)
ResourceState(const MCProcResourceDesc &Desc, unsigned Index, uint64_t Mask)
unsigned size() const
Definition: Instruction.h:318
unsigned getNumProcResourceKinds() const
Definition: MCSchedule.h:335