lib/MCA/HardwareUnits/ResourceManager.cpp

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