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