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
20namespace llvm {
21namespace mca {
22
23#define DEBUG_TYPE "llvm-mca"
24ResourceStrategy::~ResourceStrategy() = default;
25
26static 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
34uint64_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
51void 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
65ResourceState::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
80bool ResourceState::isReady(unsigned NumUnits) const {
81  return (!isReserved() || isADispatchHazard()) &&
82         (unsigned)llvm::popcount(ReadyMask) >= NumUnits;
83}
84
85ResourceStateEvent 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
94void 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
104static std::unique_ptr<ResourceStrategy>
105getStrategyFor(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
111ResourceManager::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
158void 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
166unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
167  return ResIndex2ProcResID[getResourceStateIndex(Mask)];
168}
169
170unsigned 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.
177ResourceRef 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
194void 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
224void 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
244ResourceStateEvent
245ResourceManager::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
253void 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
270void 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
282uint64_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
347void 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
374void 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
393void 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
402void 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