LLVM 20.0.0git
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
20namespace llvm {
21namespace mca {
22
23#define DEBUG_TYPE "llvm-mca"
25
26static 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
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(llvm::popcount(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
80bool ResourceState::isReady(unsigned NumUnits) const {
81 return (!isReserved() || isADispatchHazard()) &&
82 (unsigned)llvm::popcount(ReadyMask) >= NumUnits;
83}
84
87 return RS_RESERVED;
88 if (!isBuffered() || AvailableSlots)
91}
92
93#ifndef NDEBUG
94void 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
104static 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), AvailableBuffers(~0ULL),
118 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
158void 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
167 return ResIndex2ProcResID[getResourceStateIndex(Mask)];
168}
169
170unsigned 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.
177ResourceRef 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
194void 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
224void 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
246 if (ConsumedBuffers & ReservedBuffers)
248 if (ConsumedBuffers & (~AvailableBuffers))
251}
252
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
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
283 uint64_t BusyResourceMask = 0;
284 uint64_t ConsumedResourceMask = 0;
285 DenseMap<uint64_t, unsigned> AvailableUnits;
286
287 for (const std::pair<uint64_t, ResourceUsage> &E : Desc.Resources) {
288 unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
289 const ResourceState &RS = *Resources[getResourceStateIndex(E.first)];
290 if (!RS.isReady(NumUnits)) {
291 BusyResourceMask |= E.first;
292 continue;
293 }
294
295 if (Desc.HasPartiallyOverlappingGroups && !RS.isAResourceGroup()) {
296 unsigned NumAvailableUnits = llvm::popcount(RS.getReadyMask());
297 NumAvailableUnits -= NumUnits;
298 AvailableUnits[E.first] = NumAvailableUnits;
299 if (!NumAvailableUnits)
300 ConsumedResourceMask |= E.first;
301 }
302 }
303
304 BusyResourceMask &= ProcResUnitMask;
305 if (BusyResourceMask)
306 return BusyResourceMask;
307
308 BusyResourceMask = Desc.UsedProcResGroups & ReservedResourceGroups;
309 if (!Desc.HasPartiallyOverlappingGroups || BusyResourceMask)
310 return BusyResourceMask;
311
312 // If this instruction has overlapping groups, make sure that we can
313 // select at least one unit per group.
314 for (const std::pair<uint64_t, ResourceUsage> &E : Desc.Resources) {
315 const ResourceState &RS = *Resources[getResourceStateIndex(E.first)];
316 if (!E.second.isReserved() && RS.isAResourceGroup()) {
317 uint64_t ReadyMask = RS.getReadyMask() & ~ConsumedResourceMask;
318 if (!ReadyMask) {
319 BusyResourceMask |= RS.getReadyMask();
320 continue;
321 }
322
323 uint64_t ResourceMask = llvm::bit_floor(ReadyMask);
324
325 auto it = AvailableUnits.find(ResourceMask);
326 if (it == AvailableUnits.end()) {
327 unsigned Index = getResourceStateIndex(ResourceMask);
328 unsigned NumUnits = llvm::popcount(Resources[Index]->getReadyMask());
329 it =
330 AvailableUnits.insert(std::make_pair(ResourceMask, NumUnits)).first;
331 }
332
333 if (!it->second) {
334 BusyResourceMask |= it->first;
335 continue;
336 }
337
338 it->second--;
339 if (!it->second)
340 ConsumedResourceMask |= it->first;
341 }
342 }
343
344 return BusyResourceMask;
345}
346
348 const InstrDesc &Desc,
349 SmallVectorImpl<std::pair<ResourceRef, ReleaseAtCycles>> &Pipes) {
350 for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
351 const CycleSegment &CS = R.second.CS;
352 if (!CS.size()) {
353 releaseResource(R.first);
354 continue;
355 }
356
357 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
358 if (!R.second.isReserved()) {
359 ResourceRef Pipe = selectPipe(R.first);
360 use(Pipe);
361 BusyResources[Pipe] += CS.size();
362 Pipes.emplace_back(std::pair<ResourceRef, ReleaseAtCycles>(
363 Pipe, ReleaseAtCycles(CS.size())));
364 } else {
365 assert((llvm::popcount(R.first) > 1) && "Expected a group!");
366 // Mark this group as reserved.
367 assert(R.second.isReserved());
368 reserveResource(R.first);
369 BusyResources[ResourceRef(R.first, R.first)] += CS.size();
370 }
371 }
372}
373
375 for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
376 if (BR.second)
377 BR.second--;
378 if (!BR.second) {
379 // Release this resource.
380 const ResourceRef &RR = BR.first;
381
382 if (llvm::popcount(RR.first) == 1)
383 release(RR);
384 releaseResource(RR.first);
385 ResourcesFreed.push_back(RR);
386 }
387 }
388
389 for (const ResourceRef &RF : ResourcesFreed)
390 BusyResources.erase(RF);
391}
392
394 const unsigned Index = getResourceStateIndex(ResourceID);
395 ResourceState &Resource = *Resources[Index];
396 assert(Resource.isAResourceGroup() && !Resource.isReserved() &&
397 "Unexpected resource state found!");
398 Resource.setReserved();
399 ReservedResourceGroups ^= 1ULL << Index;
400}
401
403 const unsigned Index = getResourceStateIndex(ResourceID);
404 ResourceState &Resource = *Resources[Index];
405 Resource.clearReserved();
406 if (Resource.isAResourceGroup())
407 ReservedResourceGroups ^= 1ULL << Index;
408 // Now it is safe to release dispatch/issue resources.
409 if (Resource.isADispatchHazard())
410 ReservedBuffers ^= 1ULL << Index;
411}
412
413} // namespace mca
414} // namespace llvm
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
iv Induction Variable Users
Definition: IVUsers.cpp:48
Move duplicate certain instructions close to their use
Definition: Localizer.cpp:33
#define I(x, y, z)
Definition: MD5.cpp:58
The classes here represent processor resource units and their management strategy.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
A sequence of cycles.
Definition: Instruction.h:389
unsigned size() const
Definition: Instruction.h:418
unsigned begin() const
Definition: Instruction.h:424
void used(uint64_t Mask) override
Called by the ResourceManager when a processor resource group, or a processor resource with multiple ...
uint64_t select(uint64_t ReadyMask) override
Selects a processor resource unit from a ReadyMask.
This class represents the number of cycles per resource (fractions of cycles).
Definition: Support.h:51
void reserveBuffers(uint64_t ConsumedBuffers)
void releaseBuffers(uint64_t ConsumedBuffers)
void issueInstruction(const InstrDesc &Desc, SmallVectorImpl< std::pair< ResourceRef, ReleaseAtCycles > > &Pipes)
void releaseResource(uint64_t ResourceID)
ResourceManager(const MCSchedModel &SM)
void reserveResource(uint64_t ResourceID)
unsigned resolveResourceMask(uint64_t Mask) const
void cycleEvent(SmallVectorImpl< ResourceRef > &ResourcesFreed)
ResourceStateEvent canBeDispatched(uint64_t ConsumedBuffers) const
uint64_t checkAvailability(const InstrDesc &Desc) const
A processor resource descriptor.
ResourceStateEvent isBufferAvailable() const
Checks if there is an available slot in the resource buffer.
ResourceState(const MCProcResourceDesc &Desc, unsigned Index, uint64_t Mask)
uint64_t getReadyMask() const
bool isADispatchHazard() const
Returns true if this is an in-order dispatch/issue resource.
bool isReady(unsigned NumUnits=1) const
Returs true if this resource is not reserved, and if there are at least NumUnits available units.
unsigned getNumUnits() const
Helper functions used by various pipeline components.
static std::unique_ptr< ResourceStrategy > getStrategyFor(const ResourceState &RS)
ResourceStateEvent
Used to notify the internal state of a processor resource.
@ RS_BUFFER_UNAVAILABLE
static uint64_t selectImpl(uint64_t CandidateMask, uint64_t &NextInSequenceMask)
std::pair< uint64_t, uint64_t > ResourceRef
A resource unit identifier.
void computeProcResourceMasks(const MCSchedModel &SM, MutableArrayRef< uint64_t > Masks)
Populates vector Masks with processor resource masks.
Definition: Support.cpp:40
unsigned getResourceStateIndex(uint64_t Mask)
Definition: Support.h:100
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
int popcount(T Value) noexcept
Count the number of set bits in a value.
Definition: bit.h:385
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FormattedNumber format_hex(uint64_t N, unsigned Width, bool Upper=false)
format_hex - Output N as a fixed width hexadecimal.
Definition: Format.h:187
T bit_floor(T Value)
Returns the largest integral power of two no greater than Value if Value is nonzero.
Definition: bit.h:327
Description of the encoding of one expression Op.
Define a kind of processor resource that will be modeled by the scheduler.
Definition: MCSchedule.h:31
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:253
unsigned getNumProcResourceKinds() const
Definition: MCSchedule.h:349
const MCProcResourceDesc * getProcResource(unsigned ProcResourceIdx) const
Definition: MCSchedule.h:353
An instruction descriptor.
Definition: Instruction.h:447