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 = AvailableUnits.find(Val: ResourceMask);
326 if (it == AvailableUnits.end()) {
327 unsigned Index = getResourceStateIndex(Mask: ResourceMask);
328 unsigned NumUnits = llvm::popcount(Value: Resources[Index]->getReadyMask());
329 it =
330 AvailableUnits.insert(KV: std::make_pair(x&: ResourceMask, y&: 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
347void ResourceManager::issueInstruction(
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(ResourceID: R.first);
354 continue;
355 }
356
357 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
358 if (!R.second.isReserved()) {
359 ResourceRef Pipe = selectPipe(ResourceID: R.first);
360 use(RR: Pipe);
361 BusyResources[Pipe] += CS.size();
362 Pipes.emplace_back(Args: 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(ResourceID: R.first);
369 BusyResources[ResourceRef(R.first, R.first)] += CS.size();
370 }
371 }
372}
373
374void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
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(Value: RR.first) == 1)
383 release(RR);
384 releaseResource(ResourceID: RR.first);
385 ResourcesFreed.push_back(Elt: RR);
386 }
387 }
388
389 for (const ResourceRef &RF : ResourcesFreed)
390 BusyResources.erase(Val: RF);
391}
392
393void ResourceManager::reserveResource(uint64_t ResourceID) {
394 const unsigned Index = getResourceStateIndex(Mask: 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
402void ResourceManager::releaseResource(uint64_t ResourceID) {
403 const unsigned Index = getResourceStateIndex(Mask: 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
415