xref: /freebsd/contrib/llvm-project/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp (revision 5f757f3ff9144b609b3c433dfd370cc6bdc191ad) 
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 
20 namespace llvm {
21 namespace mca {
22 
23 #define DEBUG_TYPE "llvm-mca"
24 ResourceStrategy::~ResourceStrategy() = default;
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 
51 void 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 
65 ResourceState::ResourceState(const MCProcResourceDesc &Desc, unsigned Index,
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 
80 bool ResourceState::isReady(unsigned NumUnits) const {
81   return (!isReserved() || isADispatchHazard()) &&
82          (unsigned)llvm::popcount(ReadyMask) >= NumUnits;
83 }
84 
85 ResourceStateEvent 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
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>
105 getStrategyFor(const ResourceState &RS) {
106   if (RS.isAResourceGroup() || RS.getNumUnits() > 1)
107     return std::make_unique<DefaultResourceStrategy>(RS.getReadyMask());
108   return std::unique_ptr<ResourceStrategy>(nullptr);
109 }
110 
111 ResourceManager::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, 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 
158 void 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 
166 unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
167   return ResIndex2ProcResID[getResourceStateIndex(Mask)];
168 }
169 
170 unsigned 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.
177 ResourceRef 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 
194 void 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 
224 void 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 
244 ResourceStateEvent
245 ResourceManager::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 
253 void ResourceManager::reserveBuffers(uint64_t ConsumedBuffers) {
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 
270 void ResourceManager::releaseBuffers(uint64_t ConsumedBuffers) {
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 
282 uint64_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(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 
347 void 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(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 
374 void 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(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 
393 void ResourceManager::reserveResource(uint64_t ResourceID) {
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 
402 void ResourceManager::releaseResource(uint64_t ResourceID) {
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
415