xref: /freebsd/contrib/llvm-project/llvm/lib/MCA/HardwareUnits/ResourceManager.cpp (revision 5956d97f4b3204318ceb6aa9c77bd0bc6ea87a41) 
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(countPopulation(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          countPopulation(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   for (const std::pair<uint64_t, ResourceUsage> &E : Desc.Resources) {
285     unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
286     unsigned Index = getResourceStateIndex(E.first);
287     if (!Resources[Index]->isReady(NumUnits))
288       BusyResourceMask |= E.first;
289   }
290 
291   uint64_t ImplicitUses = Desc.ImplicitlyUsedProcResUnits;
292   while (ImplicitUses) {
293     uint64_t Use = ImplicitUses & -ImplicitUses;
294     ImplicitUses ^= Use;
295     unsigned Index = getResourceStateIndex(Use);
296     if (!Resources[Index]->isReady(/* NumUnits */ 1))
297       BusyResourceMask |= Index;
298   }
299 
300   BusyResourceMask &= ProcResUnitMask;
301   if (BusyResourceMask)
302     return BusyResourceMask;
303   return Desc.UsedProcResGroups & ReservedResourceGroups;
304 }
305 
306 void ResourceManager::issueInstruction(
307     const InstrDesc &Desc,
308     SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
309   for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
310     const CycleSegment &CS = R.second.CS;
311     if (!CS.size()) {
312       releaseResource(R.first);
313       continue;
314     }
315 
316     assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
317     if (!R.second.isReserved()) {
318       ResourceRef Pipe = selectPipe(R.first);
319       use(Pipe);
320       BusyResources[Pipe] += CS.size();
321       Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
322           Pipe, ResourceCycles(CS.size())));
323     } else {
324       assert((countPopulation(R.first) > 1) && "Expected a group!");
325       // Mark this group as reserved.
326       assert(R.second.isReserved());
327       reserveResource(R.first);
328       BusyResources[ResourceRef(R.first, R.first)] += CS.size();
329     }
330   }
331 }
332 
333 void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
334   for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
335     if (BR.second)
336       BR.second--;
337     if (!BR.second) {
338       // Release this resource.
339       const ResourceRef &RR = BR.first;
340 
341       if (countPopulation(RR.first) == 1)
342         release(RR);
343       releaseResource(RR.first);
344       ResourcesFreed.push_back(RR);
345     }
346   }
347 
348   for (const ResourceRef &RF : ResourcesFreed)
349     BusyResources.erase(RF);
350 }
351 
352 void ResourceManager::reserveResource(uint64_t ResourceID) {
353   const unsigned Index = getResourceStateIndex(ResourceID);
354   ResourceState &Resource = *Resources[Index];
355   assert(Resource.isAResourceGroup() && !Resource.isReserved() &&
356          "Unexpected resource state found!");
357   Resource.setReserved();
358   ReservedResourceGroups ^= 1ULL << Index;
359 }
360 
361 void ResourceManager::releaseResource(uint64_t ResourceID) {
362   const unsigned Index = getResourceStateIndex(ResourceID);
363   ResourceState &Resource = *Resources[Index];
364   Resource.clearReserved();
365   if (Resource.isAResourceGroup())
366     ReservedResourceGroups ^= 1ULL << Index;
367   // Now it is safe to release dispatch/issue resources.
368   if (Resource.isADispatchHazard())
369     ReservedBuffers ^= 1ULL << Index;
370 }
371 
372 } // namespace mca
373 } // namespace llvm
374