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
65ResourceState::ResourceState(const MCProcResourceDesc &Desc, unsigned Index,
66 uint64_t Mask)
67 : ProcResourceDescIndex(Index), ResourceMask(Mask),
68 BufferSize(Desc.BufferSize), IsAGroup(llvm::popcount(Value: ResourceMask) > 1) {
69 if (IsAGroup) {
70 ResourceSizeMask =
71 ResourceMask ^ 1ULL << getResourceStateIndex(Mask: 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(Value: ReadyMask) >= NumUnits;
83}
84
85ResourceStateEvent ResourceState::isBufferAvailable() const {
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
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>
105getStrategyFor(const ResourceState &RS) {
106 if (RS.isAResourceGroup() || RS.getNumUnits() > 1)
107 return std::make_unique<DefaultResourceStrategy>(args: RS.getReadyMask());
108 return std::unique_ptr<ResourceStrategy>(nullptr);
109}
110
111ResourceManager::ResourceManager(const MCSchedModel &SM)
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, Masks: ProcResID2Mask);
120
121 // initialize vector ResIndex2ProcResID.
122 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
123 unsigned Index = getResourceStateIndex(Mask: 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>(args: *SM.getProcResource(ProcResourceIdx: I), args&: I, args&: Mask);
132 Strategies[Index] = getStrategyFor(RS: *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(Mask: 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(Mask: 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
166unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
167 return ResIndex2ProcResID[getResourceStateIndex(Mask)];
168}
169
170unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
171 return Resources[getResourceStateIndex(Mask: 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(Mask: 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(x&: ResourceID, y: RS.getReadyMask());
187
188 uint64_t SubResourceID = Strategies[Index]->select(ReadyMask: RS.getReadyMask());
189 if (RS.isAResourceGroup())
190 return selectPipe(ResourceID: SubResourceID);
191 return std::make_pair(x&: ResourceID, y&: SubResourceID);
192}
193
194void ResourceManager::use(const ResourceRef &RR) {
195 // Mark the sub-resource referenced by RR as used.
196 unsigned RSID = getResourceStateIndex(Mask: RR.first);
197 ResourceState &RS = *Resources[RSID];
198 RS.markSubResourceAsUsed(ID: 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(ResourceMask: 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(Mask: Users & (-Users));
216 ResourceState &CurrentUser = *Resources[GroupIndex];
217 CurrentUser.markSubResourceAsUsed(ID: RR.first);
218 Strategies[GroupIndex]->used(ResourceMask: RR.first);
219 // Reset lowest set bit.
220 Users &= Users - 1;
221 }
222}
223
224void ResourceManager::release(const ResourceRef &RR) {
225 unsigned RSID = getResourceStateIndex(Mask: RR.first);
226 ResourceState &RS = *Resources[RSID];
227 bool WasFullyUsed = !RS.isReady();
228 RS.releaseSubResource(ID: 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(Mask: Users & (-Users));
238 ResourceState &CurrentUser = *Resources[GroupIndex];
239 CurrentUser.releaseSubResource(ID: RR.first);
240 Users &= Users - 1;
241 }
242}
243
244ResourceStateEvent
245ResourceManager::canBeDispatched(uint64_t ConsumedBuffers) const {
246 if (ConsumedBuffers & ReservedBuffers)
247 return ResourceStateEvent::RS_RESERVED;
248 if (ConsumedBuffers & (~AvailableBuffers))
249 return ResourceStateEvent::RS_BUFFER_UNAVAILABLE;
250 return ResourceStateEvent::RS_BUFFER_AVAILABLE;
251}
252
253void ResourceManager::reserveBuffers(uint64_t ConsumedBuffers) {
254 while (ConsumedBuffers) {
255 uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
256 ResourceState &RS = *Resources[getResourceStateIndex(Mask: 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
270void ResourceManager::releaseBuffers(uint64_t ConsumedBuffers) {
271 AvailableBuffers |= ConsumedBuffers;
272 while (ConsumedBuffers) {
273 uint64_t CurrentBuffer = ConsumedBuffers & (-ConsumedBuffers);
274 ResourceState &RS = *Resources[getResourceStateIndex(Mask: 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
282uint64_t ResourceManager::checkAvailability(const InstrDesc &Desc) const {
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(Mask: 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(Value: 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(Mask: 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(Value: ReadyMask);
324
325 auto [it, Inserted] = AvailableUnits.try_emplace(Key: ResourceMask);
326 if (Inserted) {
327 unsigned Index = getResourceStateIndex(Mask: ResourceMask);
328 unsigned NumUnits = llvm::popcount(Value: Resources[Index]->getReadyMask());
329 it->second = NumUnits;
330 }
331
332 if (!it->second) {
333 BusyResourceMask |= it->first;
334 continue;
335 }
336
337 it->second--;
338 if (!it->second)
339 ConsumedResourceMask |= it->first;
340 }
341 }
342
343 return BusyResourceMask;
344}
345
346void ResourceManager::issueInstructionImpl(
347 const InstrDesc &Desc, SmallVectorImpl<ResourceWithCycles> &Pipes) {
348
349 // Step 1.
350 // - Issue writes to non-group resources.
351 // - Issue writes to groups with only a single resource unit available.
352 // - Update reserved groups (if any)
353 // - Add any remaining resource usage requests to a Worklist.
354 SmallVector<std::pair<uint64_t, ResourceUsage>, 4> Worklist;
355
356 using ResourceWithUsage = std::pair<uint64_t, ResourceUsage>;
357
358 for (const ResourceWithUsage &R : Desc.Resources) {
359 const CycleSegment &CS = R.second.CS;
360 if (!CS.size()) {
361 releaseResource(ResourceID: R.first);
362 continue;
363 }
364
365 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
366 if (R.second.isReserved()) {
367 assert((llvm::popcount(R.first) > 1) && "Expected a group!");
368 // Mark this group as reserved.
369 assert(R.second.isReserved());
370 reserveResource(ResourceID: R.first);
371 BusyResources[ResourceRef(R.first, R.first)] += CS.size();
372 continue;
373 }
374
375 const ResourceState &RS = *Resources[getResourceStateIndex(Mask: R.first)];
376 if (RS.isAResourceGroup() && RS.getNumReadyUnits() > 1) {
377 Worklist.push_back(Elt: R);
378 continue;
379 }
380
381 ResourceRef Pipe = selectPipe(ResourceID: R.first);
382 use(RR: Pipe);
383 BusyResources[Pipe] += CS.size();
384 Pipes.emplace_back(Args: std::make_pair(x&: Pipe, y: ReleaseAtCycles(CS.size())));
385 }
386
387 // Step 2.
388 // Prioritize writes to groups with less available resources.
389 // NOTE: this algorithm has quadratic complexity in the worst case scenario.
390 // On average, this algorithm is expected to perform quite well and always
391 // converge in very few iterations. That is mainly because instructions rarely
392 // consume more than two or three resource groups.
393
394 while (!Worklist.empty()) {
395 sort(C&: Worklist, Comp: [&](const ResourceWithUsage &Lhs,
396 const ResourceWithUsage &Rhs) {
397 const ResourceState &LhsRS = *Resources[getResourceStateIndex(Mask: Lhs.first)];
398 const ResourceState &RhsRS = *Resources[getResourceStateIndex(Mask: Rhs.first)];
399 uint64_t LhsReadyUnits = LhsRS.getNumReadyUnits();
400 uint64_t RhsReadyUnits = RhsRS.getNumReadyUnits();
401 if (LhsReadyUnits == RhsReadyUnits)
402 return Lhs.first < Rhs.first;
403 return LhsReadyUnits < RhsReadyUnits;
404 });
405
406 SmallVector<ResourceWithUsage, 4> NewWorklist;
407
408 for (unsigned I = 0, E = Worklist.size(); I < E; ++I) {
409 const auto &Elt = Worklist[I];
410 const ResourceState &RS = *Resources[getResourceStateIndex(Mask: Elt.first)];
411
412 if (I == 0 || RS.getNumReadyUnits() == 1) {
413 ResourceRef Pipe = selectPipe(ResourceID: Elt.first);
414 use(RR: Pipe);
415 const CycleSegment &CS = Elt.second.CS;
416 BusyResources[Pipe] += CS.size();
417 Pipes.emplace_back(Args: std::make_pair(x&: Pipe, y: ReleaseAtCycles(CS.size())));
418 continue;
419 }
420
421 NewWorklist.push_back(Elt);
422 }
423
424 swap(LHS&: NewWorklist, RHS&: Worklist);
425 };
426}
427
428void ResourceManager::fastIssueInstruction(
429 const InstrDesc &Desc, SmallVectorImpl<ResourceWithCycles> &Pipes) {
430 for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
431 const CycleSegment &CS = R.second.CS;
432 if (!CS.size()) {
433 releaseResource(ResourceID: R.first);
434 continue;
435 }
436
437 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
438 if (!R.second.isReserved()) {
439 ResourceRef Pipe = selectPipe(ResourceID: R.first);
440 use(RR: Pipe);
441 BusyResources[Pipe] += CS.size();
442 Pipes.emplace_back(Args: std::pair<ResourceRef, ReleaseAtCycles>(
443 Pipe, ReleaseAtCycles(CS.size())));
444 } else {
445 assert((llvm::popcount(R.first) > 1) && "Expected a group!");
446 // Mark this group as reserved.
447 assert(R.second.isReserved());
448 reserveResource(ResourceID: R.first);
449 BusyResources[ResourceRef(R.first, R.first)] += CS.size();
450 }
451 }
452}
453
454void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
455 for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
456 if (BR.second)
457 BR.second--;
458 if (!BR.second) {
459 // Release this resource.
460 const ResourceRef &RR = BR.first;
461
462 if (llvm::popcount(Value: RR.first) == 1)
463 release(RR);
464 releaseResource(ResourceID: RR.first);
465 ResourcesFreed.push_back(Elt: RR);
466 }
467 }
468
469 for (const ResourceRef &RF : ResourcesFreed)
470 BusyResources.erase(Val: RF);
471}
472
473void ResourceManager::reserveResource(uint64_t ResourceID) {
474 const unsigned Index = getResourceStateIndex(Mask: ResourceID);
475 ResourceState &Resource = *Resources[Index];
476 assert(Resource.isAResourceGroup() && !Resource.isReserved() &&
477 "Unexpected resource state found!");
478 Resource.setReserved();
479 ReservedResourceGroups ^= 1ULL << Index;
480}
481
482void ResourceManager::releaseResource(uint64_t ResourceID) {
483 const unsigned Index = getResourceStateIndex(Mask: ResourceID);
484 ResourceState &Resource = *Resources[Index];
485 Resource.clearReserved();
486 if (Resource.isAResourceGroup())
487 ReservedResourceGroups ^= 1ULL << Index;
488 // Now it is safe to release dispatch/issue resources.
489 if (Resource.isADispatchHazard())
490 ReservedBuffers ^= 1ULL << Index;
491}
492
493} // namespace mca
494} // namespace llvm
495