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
15#include "llvm/MCA/HardwareUnits/ResourceManager.h"
16#include "llvm/MCA/Support.h"
17#include "llvm/Support/Debug.h"
18#include "llvm/Support/raw_ostream.h"
19
20namespace llvm {
21namespace mca {
22
23#define DEBUG_TYPE "llvm-mca"
24ResourceStrategy::~ResourceStrategy() = default;
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(Mask: CandidateMask);
30 NextInSequenceMask &= (CandidateMask | (CandidateMask - 1));
31 return CandidateMask;
32}
33
34uint64_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
51void DefaultResourceStrategy::used(uint64_t Mask) {
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
65static uint64_t computeResourceSizeMask(uint64_t Mask, bool IsAGroup,
66 unsigned NumUnits) {
67 if (IsAGroup)
68 return Mask ^ (1ULL << getResourceStateIndex(Mask));
69 return (1ULL << NumUnits) - 1;
70}
71
72ResourceState::ResourceState(const MCProcResourceDesc &Desc, unsigned Index,
73 uint64_t Mask, const MCSchedModel &SM)
74 : ProcResourceDescIndex(Index), ResourceMask(Mask),
75 IsAGroup(llvm::popcount(Value: ResourceMask) > 1),
76 ResourceSizeMask(computeResourceSizeMask(Mask, IsAGroup, NumUnits: Desc.NumUnits)),
77 BufferSize(SM.getResourceBufferSize(ProcResourceIdx: Index)) {
78 ReadyMask = ResourceSizeMask;
79 AvailableSlots = BufferSize == -1 ? 0U : static_cast<unsigned>(BufferSize);
80 Unavailable = false;
81}
82
83bool ResourceState::isReady(unsigned NumUnits) const {
84 return (!isReserved() || isADispatchHazard()) &&
85 (unsigned)llvm::popcount(Value: ReadyMask) >= NumUnits;
86}
87
88ResourceStateEvent ResourceState::isBufferAvailable() const {
89 if (isADispatchHazard() && isReserved())
90 return RS_RESERVED;
91 if (!isBuffered() || AvailableSlots)
92 return RS_BUFFER_AVAILABLE;
93 return RS_BUFFER_UNAVAILABLE;
94}
95
96#ifndef NDEBUG
97void ResourceState::dump() const {
98 dbgs() << "MASK=" << format_hex(ResourceMask, 16)
99 << ", SZMASK=" << format_hex(ResourceSizeMask, 16)
100 << ", RDYMASK=" << format_hex(ReadyMask, 16)
101 << ", BufferSize=" << BufferSize
102 << ", AvailableSlots=" << AvailableSlots
103 << ", Reserved=" << Unavailable << '\n';
104}
105#endif
106
107static std::unique_ptr<ResourceStrategy>
108getStrategyFor(const ResourceState &RS) {
109 if (RS.isAResourceGroup() || RS.getNumUnits() > 1)
110 return std::make_unique<DefaultResourceStrategy>(args: RS.getReadyMask());
111 return std::unique_ptr<ResourceStrategy>(nullptr);
112}
113
114ResourceManager::ResourceManager(const MCSchedModel &SM)
115 : Resources(SM.getNumProcResourceKinds() - 1),
116 Strategies(SM.getNumProcResourceKinds() - 1),
117 Resource2Groups(SM.getNumProcResourceKinds() - 1, 0),
118 ProcResID2Mask(SM.getNumProcResourceKinds(), 0),
119 ResIndex2ProcResID(SM.getNumProcResourceKinds() - 1, 0),
120 ProcResUnitMask(0), ReservedResourceGroups(0), AvailableBuffers(~0ULL),
121 ReservedBuffers(0) {
122 computeProcResourceMasks(SM, Masks: ProcResID2Mask);
123
124 // initialize vector ResIndex2ProcResID.
125 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
126 unsigned Index = getResourceStateIndex(Mask: ProcResID2Mask[I]);
127 ResIndex2ProcResID[Index] = I;
128 }
129
130 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
131 uint64_t Mask = ProcResID2Mask[I];
132 unsigned Index = getResourceStateIndex(Mask);
133 Resources[Index] =
134 std::make_unique<ResourceState>(args: *SM.getProcResource(ProcResourceIdx: I), args&: I, args&: Mask, args: SM);
135 Strategies[Index] = getStrategyFor(RS: *Resources[Index]);
136 }
137
138 // Print static resource information on debug mode
139 LLVM_DEBUG({
140 dbgs() << "\nProcessor resources:\n";
141 // Print InvalidUnit first to be consistent with scheduling model indexing
142 // schema
143 const MCProcResourceDesc &InvalidUnit = *SM.getProcResource(0);
144 dbgs() << "[ 0] - " << format_hex(ProcResID2Mask[0], 16) << " - "
145 << InvalidUnit.Name << "\n";
146 for (unsigned I = 0, E = Resources.size(); I < E; ++I) {
147 const ResourceState &RS = *Resources[I];
148 const unsigned ProcResID = RS.getProcResourceID();
149 const MCProcResourceDesc &Desc = *SM.getProcResource(ProcResID);
150 dbgs() << '[' << format_decimal(ProcResID, 2) << "] "
151 << " - " << format_hex(RS.getResourceMask(), 16) << " - "
152 << Desc.Name << " (BufferSize=" << RS.getBufferSize() << ")\n";
153 }
154 });
155
156 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
157 uint64_t Mask = ProcResID2Mask[I];
158 unsigned Index = getResourceStateIndex(Mask);
159 const ResourceState &RS = *Resources[Index];
160 if (!RS.isAResourceGroup()) {
161 ProcResUnitMask |= Mask;
162 continue;
163 }
164
165 uint64_t GroupMaskIdx = 1ULL << Index;
166 Mask -= GroupMaskIdx;
167 while (Mask) {
168 // Extract lowest set isolated bit.
169 uint64_t Unit = Mask & (-Mask);
170 unsigned IndexUnit = getResourceStateIndex(Mask: Unit);
171 Resource2Groups[IndexUnit] |= GroupMaskIdx;
172 Mask ^= Unit;
173 }
174 }
175
176 AvailableProcResUnits = ProcResUnitMask;
177}
178
179void ResourceManager::setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
180 uint64_t ResourceMask) {
181 unsigned Index = getResourceStateIndex(Mask: ResourceMask);
182 assert(Index < Resources.size() && "Invalid processor resource index!");
183 assert(S && "Unexpected null strategy in input!");
184 Strategies[Index] = std::move(S);
185}
186
187unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
188 return ResIndex2ProcResID[getResourceStateIndex(Mask)];
189}
190
191unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
192 return Resources[getResourceStateIndex(Mask: ResourceID)]->getNumUnits();
193}
194
195// Returns the actual resource consumed by this Use.
196// First, is the primary resource ID.
197// Second, is the specific sub-resource ID.
198ResourceRef ResourceManager::selectPipe(uint64_t ResourceID) {
199 unsigned Index = getResourceStateIndex(Mask: ResourceID);
200 assert(Index < Resources.size() && "Invalid resource use!");
201 ResourceState &RS = *Resources[Index];
202 assert(RS.isReady() && "No available units to select!");
203
204 // Special case where RS is not a group, and it only declares a single
205 // resource unit.
206 if (!RS.isAResourceGroup() && RS.getNumUnits() == 1)
207 return std::make_pair(x&: ResourceID, y: RS.getReadyMask());
208
209 uint64_t SubResourceID = Strategies[Index]->select(ReadyMask: RS.getReadyMask());
210 if (RS.isAResourceGroup())
211 return selectPipe(ResourceID: SubResourceID);
212 return std::make_pair(x&: ResourceID, y&: SubResourceID);
213}
214
215void ResourceManager::use(const ResourceRef &RR) {
216 // Mark the sub-resource referenced by RR as used.
217 unsigned RSID = getResourceStateIndex(Mask: RR.first);
218 ResourceState &RS = *Resources[RSID];
219 RS.markSubResourceAsUsed(ID: RR.second);
220 // Remember to update the resource strategy for non-group resources with
221 // multiple units.
222 if (RS.getNumUnits() > 1)
223 Strategies[RSID]->used(ResourceMask: RR.second);
224
225 // If there are still available units in RR.first,
226 // then we are done.
227 if (RS.isReady())
228 return;
229
230 AvailableProcResUnits ^= RR.first;
231
232 // Notify groups that RR.first is no longer available.
233 uint64_t Users = Resource2Groups[RSID];
234 while (Users) {
235 // Extract lowest set isolated bit.
236 unsigned GroupIndex = getResourceStateIndex(Mask: Users & (-Users));
237 ResourceState &CurrentUser = *Resources[GroupIndex];
238 CurrentUser.markSubResourceAsUsed(ID: RR.first);
239 Strategies[GroupIndex]->used(ResourceMask: RR.first);
240 // Reset lowest set bit.
241 Users &= Users - 1;
242 }
243}
244
245void ResourceManager::release(const ResourceRef &RR) {
246 unsigned RSID = getResourceStateIndex(Mask: RR.first);
247 ResourceState &RS = *Resources[RSID];
248 bool WasFullyUsed = !RS.isReady();
249 RS.releaseSubResource(ID: RR.second);
250 if (!WasFullyUsed)
251 return;
252
253 AvailableProcResUnits ^= RR.first;
254
255 // Notify groups that RR.first is now available again.
256 uint64_t Users = Resource2Groups[RSID];
257 while (Users) {
258 unsigned GroupIndex = getResourceStateIndex(Mask: Users & (-Users));
259 ResourceState &CurrentUser = *Resources[GroupIndex];
260 CurrentUser.releaseSubResource(ID: RR.first);
261 Users &= Users - 1;
262 }
263}
264
265ResourceStateEvent
266ResourceManager::canBeDispatched(uint64_t ConsumedBuffers) const {
267 if (ConsumedBuffers & ReservedBuffers)
268 return ResourceStateEvent::RS_RESERVED;
269 if (ConsumedBuffers & (~AvailableBuffers))
270 return ResourceStateEvent::RS_BUFFER_UNAVAILABLE;
271 return ResourceStateEvent::RS_BUFFER_AVAILABLE;
272}
273
274void ResourceManager::reserveBuffers(uint64_t ConsumedBuffers) {
275 while (ConsumedBuffers) {
276 uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
277 ResourceState &RS = *Resources[getResourceStateIndex(Mask: CurrentBuffer)];
278 ConsumedBuffers ^= CurrentBuffer;
279 assert(RS.isBufferAvailable() == ResourceStateEvent::RS_BUFFER_AVAILABLE);
280 if (!RS.reserveBuffer())
281 AvailableBuffers ^= CurrentBuffer;
282 if (RS.isADispatchHazard()) {
283 // Reserve this buffer now, and release it once pipeline resources
284 // consumed by the instruction become available again.
285 // We do this to simulate an in-order dispatch/issue of instructions.
286 ReservedBuffers ^= CurrentBuffer;
287 }
288 }
289}
290
291void ResourceManager::releaseBuffers(uint64_t ConsumedBuffers) {
292 AvailableBuffers |= ConsumedBuffers;
293 while (ConsumedBuffers) {
294 uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
295 ResourceState &RS = *Resources[getResourceStateIndex(Mask: CurrentBuffer)];
296 ConsumedBuffers ^= CurrentBuffer;
297 RS.releaseBuffer();
298 // Do not unreserve dispatch hazard resource buffers. Wait until all
299 // pipeline resources have been freed too.
300 }
301}
302
303uint64_t ResourceManager::checkAvailability(const InstrDesc &Desc) const {
304 uint64_t BusyResourceMask = 0;
305 uint64_t ConsumedResourceMask = 0;
306 DenseMap<uint64_t, unsigned> AvailableUnits;
307
308 for (const std::pair<uint64_t, ResourceUsage> &E : Desc.Resources) {
309 unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
310 const ResourceState &RS = *Resources[getResourceStateIndex(Mask: E.first)];
311 if (!RS.isReady(NumUnits)) {
312 BusyResourceMask |= E.first;
313 continue;
314 }
315
316 if (Desc.HasPartiallyOverlappingGroups && !RS.isAResourceGroup()) {
317 unsigned NumAvailableUnits = llvm::popcount(Value: RS.getReadyMask());
318 NumAvailableUnits -= NumUnits;
319 AvailableUnits[E.first] = NumAvailableUnits;
320 if (!NumAvailableUnits)
321 ConsumedResourceMask |= E.first;
322 }
323 }
324
325 BusyResourceMask &= ProcResUnitMask;
326 if (BusyResourceMask)
327 return BusyResourceMask;
328
329 BusyResourceMask = Desc.UsedProcResGroups & ReservedResourceGroups;
330 if (!Desc.HasPartiallyOverlappingGroups || BusyResourceMask)
331 return BusyResourceMask;
332
333 // If this instruction has overlapping groups, make sure that we can
334 // select at least one unit per group.
335 for (const std::pair<uint64_t, ResourceUsage> &E : Desc.Resources) {
336 const ResourceState &RS = *Resources[getResourceStateIndex(Mask: E.first)];
337 if (!E.second.isReserved() && RS.isAResourceGroup()) {
338 uint64_t ReadyMask = RS.getReadyMask() & ~ConsumedResourceMask;
339 if (!ReadyMask) {
340 BusyResourceMask |= RS.getReadyMask();
341 continue;
342 }
343
344 uint64_t ResourceMask = llvm::bit_floor(Value: ReadyMask);
345
346 auto [it, Inserted] = AvailableUnits.try_emplace(Key: ResourceMask);
347 if (Inserted) {
348 unsigned Index = getResourceStateIndex(Mask: ResourceMask);
349 unsigned NumUnits = llvm::popcount(Value: Resources[Index]->getReadyMask());
350 it->second = NumUnits;
351 }
352
353 if (!it->second) {
354 BusyResourceMask |= it->first;
355 continue;
356 }
357
358 it->second--;
359 if (!it->second)
360 ConsumedResourceMask |= it->first;
361 }
362 }
363
364 return BusyResourceMask;
365}
366
367void ResourceManager::issueInstructionImpl(
368 const InstrDesc &Desc, SmallVectorImpl<ResourceWithCycles> &Pipes) {
369
370 // Step 1.
371 // - Issue writes to non-group resources.
372 // - Issue writes to groups with only a single resource unit available.
373 // - Update reserved groups (if any)
374 // - Add any remaining resource usage requests to a Worklist.
375 SmallVector<std::pair<uint64_t, ResourceUsage>, 4> Worklist;
376
377 using ResourceWithUsage = std::pair<uint64_t, ResourceUsage>;
378
379 for (const ResourceWithUsage &R : Desc.Resources) {
380 const CycleSegment &CS = R.second.CS;
381 if (!CS.size()) {
382 releaseResource(ResourceID: R.first);
383 continue;
384 }
385
386 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
387 if (R.second.isReserved()) {
388 assert((llvm::popcount(R.first) > 1) && "Expected a group!");
389 // Mark this group as reserved.
390 assert(R.second.isReserved());
391 reserveResource(ResourceID: R.first);
392 BusyResources[ResourceRef(R.first, R.first)] += CS.size();
393 continue;
394 }
395
396 const ResourceState &RS = *Resources[getResourceStateIndex(Mask: R.first)];
397 if (RS.isAResourceGroup() && RS.getNumReadyUnits() > 1) {
398 Worklist.push_back(Elt: R);
399 continue;
400 }
401
402 ResourceRef Pipe = selectPipe(ResourceID: R.first);
403 use(RR: Pipe);
404 BusyResources[Pipe] += CS.size();
405 Pipes.emplace_back(Args: std::make_pair(x&: Pipe, y: ReleaseAtCycles(CS.size())));
406 }
407
408 // Step 2.
409 // Prioritize writes to groups with less available resources.
410 // NOTE: this algorithm has quadratic complexity in the worst case scenario.
411 // On average, this algorithm is expected to perform quite well and always
412 // converge in very few iterations. That is mainly because instructions rarely
413 // consume more than two or three resource groups.
414
415 while (!Worklist.empty()) {
416 sort(C&: Worklist, Comp: [&](const ResourceWithUsage &Lhs,
417 const ResourceWithUsage &Rhs) {
418 const ResourceState &LhsRS = *Resources[getResourceStateIndex(Mask: Lhs.first)];
419 const ResourceState &RhsRS = *Resources[getResourceStateIndex(Mask: Rhs.first)];
420 uint64_t LhsReadyUnits = LhsRS.getNumReadyUnits();
421 uint64_t RhsReadyUnits = RhsRS.getNumReadyUnits();
422 if (LhsReadyUnits == RhsReadyUnits)
423 return Lhs.first < Rhs.first;
424 return LhsReadyUnits < RhsReadyUnits;
425 });
426
427 SmallVector<ResourceWithUsage, 4> NewWorklist;
428
429 for (unsigned I = 0, E = Worklist.size(); I < E; ++I) {
430 const auto &Elt = Worklist[I];
431 const ResourceState &RS = *Resources[getResourceStateIndex(Mask: Elt.first)];
432
433 if (I == 0 || RS.getNumReadyUnits() == 1) {
434 ResourceRef Pipe = selectPipe(ResourceID: Elt.first);
435 use(RR: Pipe);
436 const CycleSegment &CS = Elt.second.CS;
437 BusyResources[Pipe] += CS.size();
438 Pipes.emplace_back(Args: std::make_pair(x&: Pipe, y: ReleaseAtCycles(CS.size())));
439 continue;
440 }
441
442 NewWorklist.push_back(Elt);
443 }
444
445 swap(LHS&: NewWorklist, RHS&: Worklist);
446 };
447}
448
449void ResourceManager::fastIssueInstruction(
450 const InstrDesc &Desc, SmallVectorImpl<ResourceWithCycles> &Pipes) {
451 for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
452 const CycleSegment &CS = R.second.CS;
453 if (!CS.size()) {
454 releaseResource(ResourceID: R.first);
455 continue;
456 }
457
458 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
459 if (!R.second.isReserved()) {
460 ResourceRef Pipe = selectPipe(ResourceID: R.first);
461 use(RR: Pipe);
462 BusyResources[Pipe] += CS.size();
463 Pipes.emplace_back(Args: std::pair<ResourceRef, ReleaseAtCycles>(
464 Pipe, ReleaseAtCycles(CS.size())));
465 } else {
466 assert((llvm::popcount(R.first) > 1) && "Expected a group!");
467 // Mark this group as reserved.
468 assert(R.second.isReserved());
469 reserveResource(ResourceID: R.first);
470 BusyResources[ResourceRef(R.first, R.first)] += CS.size();
471 }
472 }
473}
474
475void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
476 for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
477 if (BR.second)
478 BR.second--;
479 if (!BR.second) {
480 // Release this resource.
481 const ResourceRef &RR = BR.first;
482
483 if (llvm::popcount(Value: RR.first) == 1)
484 release(RR);
485 releaseResource(ResourceID: RR.first);
486 ResourcesFreed.push_back(Elt: RR);
487 }
488 }
489
490 for (const ResourceRef &RF : ResourcesFreed)
491 BusyResources.erase(Val: RF);
492}
493
494void ResourceManager::reserveResource(uint64_t ResourceID) {
495 const unsigned Index = getResourceStateIndex(Mask: ResourceID);
496 ResourceState &Resource = *Resources[Index];
497 assert(Resource.isAResourceGroup() && !Resource.isReserved() &&
498 "Unexpected resource state found!");
499 Resource.setReserved();
500 ReservedResourceGroups ^= 1ULL << Index;
501}
502
503void ResourceManager::releaseResource(uint64_t ResourceID) {
504 const unsigned Index = getResourceStateIndex(Mask: ResourceID);
505 ResourceState &Resource = *Resources[Index];
506 Resource.clearReserved();
507 if (Resource.isAResourceGroup())
508 ReservedResourceGroups ^= 1ULL << Index;
509 // Now it is safe to release dispatch/issue resources.
510 if (Resource.isADispatchHazard())
511 ReservedBuffers ^= 1ULL << Index;
512}
513
514} // namespace mca
515} // namespace llvm
516