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, 16)
103          << ", SZMASK=" << format_hex(ResourceSizeMask, 16)
104          << ", RDYMASK=" << format_hex(ReadyMask, 16)
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       ProcResID2Mask(SM.getNumProcResourceKinds()) {
123   computeProcResourceMasks(SM, ProcResID2Mask);
124 
125   for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) {
126     uint64_t Mask = ProcResID2Mask[I];
127     unsigned Index = getResourceStateIndex(Mask);
128     Resources[Index] =
129         llvm::make_unique<ResourceState>(*SM.getProcResource(I), I, Mask);
130     Strategies[Index] = getStrategyFor(*Resources[Index]);
131   }
132 
133   for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) {
134     uint64_t Mask = ProcResID2Mask[I];
135     unsigned Index = getResourceStateIndex(Mask);
136     const ResourceState &RS = *Resources[Index];
137     if (!RS.isAResourceGroup())
138       continue;
139 
140     uint64_t GroupMaskIdx = 1ULL << (Index - 1);
141     Mask -= GroupMaskIdx;
142     while (Mask) {
143       // Extract lowest set isolated bit.
144       uint64_t Unit = Mask & (-Mask);
145       unsigned IndexUnit = getResourceStateIndex(Unit);
146       Resource2Groups[IndexUnit] |= GroupMaskIdx;
147       Mask ^= Unit;
148     }
149   }
150 }
151 
152 void ResourceManager::setCustomStrategyImpl(std::unique_ptr<ResourceStrategy> S,
153                                             uint64_t ResourceMask) {
154   unsigned Index = getResourceStateIndex(ResourceMask);
155   assert(Index < Resources.size() && "Invalid processor resource index!");
156   assert(S && "Unexpected null strategy in input!");
157   Strategies[Index] = std::move(S);
158 }
159 
160 unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
161   return Resources[getResourceStateIndex(Mask)]->getProcResourceID();
162 }
163 
164 unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
165   return Resources[getResourceStateIndex(ResourceID)]->getNumUnits();
166 }
167 
168 // Returns the actual resource consumed by this Use.
169 // First, is the primary resource ID.
170 // Second, is the specific sub-resource ID.
171 ResourceRef ResourceManager::selectPipe(uint64_t ResourceID) {
172   unsigned Index = getResourceStateIndex(ResourceID);
173   assert(Index < Resources.size() && "Invalid resource use!");
174   ResourceState &RS = *Resources[Index];
175   assert(RS.isReady() && "No available units to select!");
176 
177   // Special case where RS is not a group, and it only declares a single
178   // resource unit.
179   if (!RS.isAResourceGroup() && RS.getNumUnits() == 1)
180     return std::make_pair(ResourceID, RS.getReadyMask());
181 
182   uint64_t SubResourceID = Strategies[Index]->select(RS.getReadyMask());
183   if (RS.isAResourceGroup())
184     return selectPipe(SubResourceID);
185   return std::make_pair(ResourceID, SubResourceID);
186 }
187 
188 void ResourceManager::use(const ResourceRef &RR) {
189   // Mark the sub-resource referenced by RR as used.
190   unsigned RSID = getResourceStateIndex(RR.first);
191   ResourceState &RS = *Resources[RSID];
192   RS.markSubResourceAsUsed(RR.second);
193   // Remember to update the resource strategy for non-group resources with
194   // multiple units.
195   if (RS.getNumUnits() > 1)
196     Strategies[RSID]->used(RR.second);
197 
198   // If there are still available units in RR.first,
199   // then we are done.
200   if (RS.isReady())
201     return;
202 
203   // Notify groups that RR.first is no longer available.
204   uint64_t Users = Resource2Groups[RSID];
205   while (Users) {
206     // Extract lowest set isolated bit.
207     unsigned GroupIndex = getResourceStateIndex(Users & (-Users));
208     ResourceState &CurrentUser = *Resources[GroupIndex];
209     CurrentUser.markSubResourceAsUsed(RR.first);
210     Strategies[GroupIndex]->used(RR.first);
211     // Reset lowest set bit.
212     Users &= Users - 1;
213   }
214 }
215 
216 void ResourceManager::release(const ResourceRef &RR) {
217   ResourceState &RS = *Resources[getResourceStateIndex(RR.first)];
218   bool WasFullyUsed = !RS.isReady();
219   RS.releaseSubResource(RR.second);
220   if (!WasFullyUsed)
221     return;
222 
223   for (std::unique_ptr<ResourceState> &Res : Resources) {
224     ResourceState &Current = *Res;
225     if (!Current.isAResourceGroup() || Current.getResourceMask() == RR.first)
226       continue;
227 
228     if (Current.containsResource(RR.first))
229       Current.releaseSubResource(RR.first);
230   }
231 }
232 
233 ResourceStateEvent
234 ResourceManager::canBeDispatched(ArrayRef<uint64_t> Buffers) const {
235   ResourceStateEvent Result = ResourceStateEvent::RS_BUFFER_AVAILABLE;
236   for (uint64_t Buffer : Buffers) {
237     ResourceState &RS = *Resources[getResourceStateIndex(Buffer)];
238     Result = RS.isBufferAvailable();
239     if (Result != ResourceStateEvent::RS_BUFFER_AVAILABLE)
240       break;
241   }
242   return Result;
243 }
244 
245 void ResourceManager::reserveBuffers(ArrayRef<uint64_t> Buffers) {
246   for (const uint64_t Buffer : Buffers) {
247     ResourceState &RS = *Resources[getResourceStateIndex(Buffer)];
248     assert(RS.isBufferAvailable() == ResourceStateEvent::RS_BUFFER_AVAILABLE);
249     RS.reserveBuffer();
250 
251     if (RS.isADispatchHazard()) {
252       assert(!RS.isReserved());
253       RS.setReserved();
254     }
255   }
256 }
257 
258 void ResourceManager::releaseBuffers(ArrayRef<uint64_t> Buffers) {
259   for (const uint64_t R : Buffers)
260     Resources[getResourceStateIndex(R)]->releaseBuffer();
261 }
262 
263 bool ResourceManager::canBeIssued(const InstrDesc &Desc) const {
264   return all_of(
265       Desc.Resources, [&](const std::pair<uint64_t, const ResourceUsage> &E) {
266         unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
267         unsigned Index = getResourceStateIndex(E.first);
268         return Resources[Index]->isReady(NumUnits);
269       });
270 }
271 
272 void ResourceManager::issueInstruction(
273     const InstrDesc &Desc,
274     SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
275   for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
276     const CycleSegment &CS = R.second.CS;
277     if (!CS.size()) {
278       releaseResource(R.first);
279       continue;
280     }
281 
282     assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
283     if (!R.second.isReserved()) {
284       ResourceRef Pipe = selectPipe(R.first);
285       use(Pipe);
286       BusyResources[Pipe] += CS.size();
287       Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
288           Pipe, ResourceCycles(CS.size())));
289     } else {
290       assert((countPopulation(R.first) > 1) && "Expected a group!");
291       // Mark this group as reserved.
292       assert(R.second.isReserved());
293       reserveResource(R.first);
294       BusyResources[ResourceRef(R.first, R.first)] += CS.size();
295     }
296   }
297 }
298 
299 void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
300   for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
301     if (BR.second)
302       BR.second--;
303     if (!BR.second) {
304       // Release this resource.
305       const ResourceRef &RR = BR.first;
306 
307       if (countPopulation(RR.first) == 1)
308         release(RR);
309 
310       releaseResource(RR.first);
311       ResourcesFreed.push_back(RR);
312     }
313   }
314 
315   for (const ResourceRef &RF : ResourcesFreed)
316     BusyResources.erase(RF);
317 }
318 
319 void ResourceManager::reserveResource(uint64_t ResourceID) {
320   ResourceState &Resource = *Resources[getResourceStateIndex(ResourceID)];
321   assert(!Resource.isReserved());
322   Resource.setReserved();
323 }
324 
325 void ResourceManager::releaseResource(uint64_t ResourceID) {
326   ResourceState &Resource = *Resources[getResourceStateIndex(ResourceID)];
327   Resource.clearReserved();
328 }
329 
330 } // namespace mca
331 } // namespace llvm
332