1 //===--------------------- ResourceManager.cpp ------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
11 /// The classes here represent processor resource units and their management
12 /// strategy.  These classes are managed by the Scheduler.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/MCA/HardwareUnits/ResourceManager.h"
17 #include "llvm/MCA/Support.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/raw_ostream.h"
20 
21 namespace llvm {
22 namespace mca {
23 
24 #define DEBUG_TYPE "llvm-mca"
25 ResourceStrategy::~ResourceStrategy() = default;
26 
27 // Returns the index of the highest bit set. For resource masks, the position of
28 // the highest bit set can be used to construct a resource mask identifier.
29 static unsigned getResourceStateIndex(uint64_t Mask) {
30   return std::numeric_limits<uint64_t>::digits - countLeadingZeros(Mask);
31 }
32 
33 static uint64_t selectImpl(uint64_t CandidateMask,
34                            uint64_t &NextInSequenceMask) {
35   // The upper bit set in CandidateMask identifies our next candidate resource.
36   CandidateMask = 1ULL << (getResourceStateIndex(CandidateMask) - 1);
37   NextInSequenceMask &= (CandidateMask | (CandidateMask - 1));
38   return CandidateMask;
39 }
40 
41 uint64_t DefaultResourceStrategy::select(uint64_t ReadyMask) {
42   // This method assumes that ReadyMask cannot be zero.
43   uint64_t CandidateMask = ReadyMask & NextInSequenceMask;
44   if (CandidateMask)
45     return selectImpl(CandidateMask, NextInSequenceMask);
46 
47   NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
48   RemovedFromNextInSequence = 0;
49   CandidateMask = ReadyMask & NextInSequenceMask;
50   if (CandidateMask)
51     return selectImpl(CandidateMask, NextInSequenceMask);
52 
53   NextInSequenceMask = ResourceUnitMask;
54   CandidateMask = ReadyMask & NextInSequenceMask;
55   return selectImpl(CandidateMask, NextInSequenceMask);
56 }
57 
58 void DefaultResourceStrategy::used(uint64_t Mask) {
59   if (Mask > NextInSequenceMask) {
60     RemovedFromNextInSequence |= Mask;
61     return;
62   }
63 
64   NextInSequenceMask &= (~Mask);
65   if (NextInSequenceMask)
66     return;
67 
68   NextInSequenceMask = ResourceUnitMask ^ RemovedFromNextInSequence;
69   RemovedFromNextInSequence = 0;
70 }
71 
72 ResourceState::ResourceState(const MCProcResourceDesc &Desc, unsigned Index,
73                              uint64_t Mask)
74     : ProcResourceDescIndex(Index), ResourceMask(Mask),
75       BufferSize(Desc.BufferSize), IsAGroup(countPopulation(ResourceMask) > 1) {
76   if (IsAGroup) {
77     ResourceSizeMask =
78         ResourceMask ^ 1ULL << (getResourceStateIndex(ResourceMask) - 1);
79   } else {
80     ResourceSizeMask = (1ULL << Desc.NumUnits) - 1;
81   }
82   ReadyMask = ResourceSizeMask;
83   AvailableSlots = BufferSize == -1 ? 0U : static_cast<unsigned>(BufferSize);
84   Unavailable = false;
85 }
86 
87 bool ResourceState::isReady(unsigned NumUnits) const {
88   return (!isReserved() || isADispatchHazard()) &&
89          countPopulation(ReadyMask) >= NumUnits;
90 }
91 
92 ResourceStateEvent ResourceState::isBufferAvailable() const {
93   if (isADispatchHazard() && isReserved())
94     return RS_RESERVED;
95   if (!isBuffered() || AvailableSlots)
96     return RS_BUFFER_AVAILABLE;
97   return RS_BUFFER_UNAVAILABLE;
98 }
99 
100 #ifndef NDEBUG
101 void ResourceState::dump() const {
102   dbgs() << "MASK=" << format_hex(ResourceMask, 8)
103          << ", SZMASK=" << format_hex(ResourceSizeMask, 8)
104          << ", RDYMASK=" << format_hex(ReadyMask, 8)
105          << ", BufferSize=" << BufferSize
106          << ", AvailableSlots=" << AvailableSlots
107          << ", Reserved=" << Unavailable << '\n';
108 }
109 #endif
110 
111 static std::unique_ptr<ResourceStrategy>
112 getStrategyFor(const ResourceState &RS) {
113   if (RS.isAResourceGroup() || RS.getNumUnits() > 1)
114     return llvm::make_unique<DefaultResourceStrategy>(RS.getReadyMask());
115   return std::unique_ptr<ResourceStrategy>(nullptr);
116 }
117 
118 ResourceManager::ResourceManager(const MCSchedModel &SM)
119     : Resources(SM.getNumProcResourceKinds()),
120       Strategies(SM.getNumProcResourceKinds()),
121       Resource2Groups(SM.getNumProcResourceKinds(), 0) {
122   computeProcResourceMasks(SM, ProcResID2Mask);
123 
124   for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) {
125     uint64_t Mask = ProcResID2Mask[I];
126     unsigned Index = getResourceStateIndex(Mask);
127     Resources[Index] =
128         llvm::make_unique<ResourceState>(*SM.getProcResource(I), I, Mask);
129     Strategies[Index] = getStrategyFor(*Resources[Index]);
130   }
131 
132   for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) {
133     uint64_t Mask = ProcResID2Mask[I];
134     unsigned Index = getResourceStateIndex(Mask);
135     const ResourceState &RS = *Resources[Index];
136     if (!RS.isAResourceGroup())
137       continue;
138 
139     uint64_t GroupMaskIdx = 1ULL << (Index - 1);
140     Mask -= GroupMaskIdx;
141     while (Mask) {
142       // Extract lowest set isolated bit.
143       uint64_t Unit = Mask & (-Mask);
144       unsigned IndexUnit = getResourceStateIndex(Unit);
145       Resource2Groups[IndexUnit] |= GroupMaskIdx;
146       Mask ^= Unit;
147     }
148   }
149 }
150 
151 void ResourceManager::setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
152                                             uint64_t ResourceMask) {
153   unsigned Index = getResourceStateIndex(ResourceMask);
154   assert(Index < Resources.size() && "Invalid processor resource index!");
155   assert(S && "Unexpected null strategy in input!");
156   Strategies[Index] = std::move(S);
157 }
158 
159 unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
160   return Resources[getResourceStateIndex(Mask)]->getProcResourceID();
161 }
162 
163 unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
164   return Resources[getResourceStateIndex(ResourceID)]->getNumUnits();
165 }
166 
167 // Returns the actual resource consumed by this Use.
168 // First, is the primary resource ID.
169 // Second, is the specific sub-resource ID.
170 ResourceRef ResourceManager::selectPipe(uint64_t ResourceID) {
171   unsigned Index = getResourceStateIndex(ResourceID);
172   assert(Index < Resources.size() && "Invalid resource use!");
173   ResourceState &RS = *Resources[Index];
174   assert(RS.isReady() && "No available units to select!");
175 
176   // Special case where RS is not a group, and it only declares a single
177   // resource unit.
178   if (!RS.isAResourceGroup() && RS.getNumUnits() == 1)
179     return std::make_pair(ResourceID, RS.getReadyMask());
180 
181   uint64_t SubResourceID = Strategies[Index]->select(RS.getReadyMask());
182   if (RS.isAResourceGroup())
183     return selectPipe(SubResourceID);
184   return std::make_pair(ResourceID, SubResourceID);
185 }
186 
187 void ResourceManager::use(const ResourceRef &RR) {
188   // Mark the sub-resource referenced by RR as used.
189   unsigned RSID = getResourceStateIndex(RR.first);
190   ResourceState &RS = *Resources[RSID];
191   RS.markSubResourceAsUsed(RR.second);
192   // Remember to update the resource strategy for non-group resources with
193   // multiple units.
194   if (RS.getNumUnits() > 1)
195     Strategies[RSID]->used(RR.second);
196 
197   // If there are still available units in RR.first,
198   // then we are done.
199   if (RS.isReady())
200     return;
201 
202   // Notify groups that RR.first is no longer available.
203   uint64_t Users = Resource2Groups[RSID];
204   while (Users) {
205     // Extract lowest set isolated bit.
206     unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
207     ResourceState &CurrentUser = *Resources[GroupIndex];
208     CurrentUser.markSubResourceAsUsed(RR.first);
209     Strategies[GroupIndex]->used(RR.first);
210     // Reset lowest set bit.
211     Users &= Users - 1;
212   }
213 }
214 
215 void ResourceManager::release(const ResourceRef &RR) {
216   ResourceState &RS = *Resources[getResourceStateIndex(RR.first)];
217   bool WasFullyUsed = !RS.isReady();
218   RS.releaseSubResource(RR.second);
219   if (!WasFullyUsed)
220     return;
221 
222   for (std::unique_ptr<ResourceState> &Res : Resources) {
223     ResourceState &Current = *Res;
224     if (!Current.isAResourceGroup() || Current.getResourceMask() == RR.first)
225       continue;
226 
227     if (Current.containsResource(RR.first))
228       Current.releaseSubResource(RR.first);
229   }
230 }
231 
232 ResourceStateEvent
233 ResourceManager::canBeDispatched(ArrayRef<uint64_t> Buffers) const {
234   ResourceStateEvent Result = ResourceStateEvent::RS_BUFFER_AVAILABLE;
235   for (uint64_t Buffer : Buffers) {
236     ResourceState &RS = *Resources[getResourceStateIndex(Buffer)];
237     Result = RS.isBufferAvailable();
238     if (Result != ResourceStateEvent::RS_BUFFER_AVAILABLE)
239       break;
240   }
241   return Result;
242 }
243 
244 void ResourceManager::reserveBuffers(ArrayRef<uint64_t> Buffers) {
245   for (const uint64_t Buffer : Buffers) {
246     ResourceState &RS = *Resources[getResourceStateIndex(Buffer)];
247     assert(RS.isBufferAvailable() == ResourceStateEvent::RS_BUFFER_AVAILABLE);
248     RS.reserveBuffer();
249 
250     if (RS.isADispatchHazard()) {
251       assert(!RS.isReserved());
252       RS.setReserved();
253     }
254   }
255 }
256 
257 void ResourceManager::releaseBuffers(ArrayRef<uint64_t> Buffers) {
258   for (const uint64_t R : Buffers)
259     Resources[getResourceStateIndex(R)]->releaseBuffer();
260 }
261 
262 bool ResourceManager::canBeIssued(const InstrDesc &Desc) const {
263   return all_of(
264       Desc.Resources, [&](const std::pair<uint64_t, const ResourceUsage> &E) {
265         unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
266         unsigned Index = getResourceStateIndex(E.first);
267         return Resources[Index]->isReady(NumUnits);
268       });
269 }
270 
271 void ResourceManager::issueInstruction(
272     const InstrDesc &Desc,
273     SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
274   for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
275     const CycleSegment &CS = R.second.CS;
276     if (!CS.size()) {
277       releaseResource(R.first);
278       continue;
279     }
280 
281     assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
282     if (!R.second.isReserved()) {
283       ResourceRef Pipe = selectPipe(R.first);
284       use(Pipe);
285       BusyResources[Pipe] += CS.size();
286       // Replace the resource mask with a valid processor resource index.
287       const ResourceState &RS = *Resources[getResourceStateIndex(Pipe.first)];
288       Pipe.first = RS.getProcResourceID();
289       Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
290           Pipe, ResourceCycles(CS.size())));
291     } else {
292       assert((countPopulation(R.first) > 1) && "Expected a group!");
293       // Mark this group as reserved.
294       assert(R.second.isReserved());
295       reserveResource(R.first);
296       BusyResources[ResourceRef(R.first, R.first)] += CS.size();
297     }
298   }
299 }
300 
301 void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
302   for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
303     if (BR.second)
304       BR.second--;
305     if (!BR.second) {
306       // Release this resource.
307       const ResourceRef &RR = BR.first;
308 
309       if (countPopulation(RR.first) == 1)
310         release(RR);
311 
312       releaseResource(RR.first);
313       ResourcesFreed.push_back(RR);
314     }
315   }
316 
317   for (const ResourceRef &RF : ResourcesFreed)
318     BusyResources.erase(RF);
319 }
320 
321 void ResourceManager::reserveResource(uint64_t ResourceID) {
322   ResourceState &Resource = *Resources[getResourceStateIndex(ResourceID)];
323   assert(!Resource.isReserved());
324   Resource.setReserved();
325 }
326 
327 void ResourceManager::releaseResource(uint64_t ResourceID) {
328   ResourceState &Resource = *Resources[getResourceStateIndex(ResourceID)];
329   Resource.clearReserved();
330 }
331 
332 } // namespace mca
333 } // namespace llvm
334