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 std::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       AvailableBuffers(~0ULL), 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
 158 void 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
 166 unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
 167   return ResIndex2ProcResID[getResourceStateIndex(Mask)];
 168 }
 169
 170 unsigned 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.
 177 ResourceRef 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
 194 void 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
 224 void 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
 244 ResourceStateEvent
 245 ResourceManager::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
 253 void 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
 270 void 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
 282 uint64_t ResourceManager::checkAvailability(const InstrDesc &Desc) const {
 283   uint64_t BusyResourceMask = 0;
 284   for (const std::pair<uint64_t, const ResourceUsage> &E : Desc.Resources) {
 285     unsigned NumUnits = E.second.isReserved() ? 0U : E.second.NumUnits;
 286     unsigned Index = getResourceStateIndex(E.first);
 287     if (!Resources[Index]->isReady(NumUnits))
 288       BusyResourceMask |= E.first;
 289   }
 290
 291   BusyResourceMask &= ProcResUnitMask;
 292   if (BusyResourceMask)
 293     return BusyResourceMask;
 294   return Desc.UsedProcResGroups & ReservedResourceGroups;
 295 }
 296
 297 void ResourceManager::issueInstruction(
 298     const InstrDesc &Desc,
 299     SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
 300   for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
 301     const CycleSegment &CS = R.second.CS;
 302     if (!CS.size()) {
 303       releaseResource(R.first);
 304       continue;
 305     }
 306
 307     assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
 308     if (!R.second.isReserved()) {
 309       ResourceRef Pipe = selectPipe(R.first);
 310       use(Pipe);
 311       BusyResources[Pipe] += CS.size();
 312       Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
 313           Pipe, ResourceCycles(CS.size())));
 314     } else {
 315       assert((countPopulation(R.first) > 1) && "Expected a group!");
 316       // Mark this group as reserved.
 317       assert(R.second.isReserved());
 318       reserveResource(R.first);
 319       BusyResources[ResourceRef(R.first, R.first)] += CS.size();
 320     }
 321   }
 322 }
 323
 324 void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
 325   for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {
 326     if (BR.second)
 327       BR.second--;
 328     if (!BR.second) {
 329       // Release this resource.
 330       const ResourceRef &RR = BR.first;
 331
 332       if (countPopulation(RR.first) == 1)
 333         release(RR);
 334       releaseResource(RR.first);
 335       ResourcesFreed.push_back(RR);
 336     }
 337   }
 338
 339   for (const ResourceRef &RF : ResourcesFreed)
 340     BusyResources.erase(RF);
 341 }
 342
 343 void ResourceManager::reserveResource(uint64_t ResourceID) {
 344   const unsigned Index = getResourceStateIndex(ResourceID);
 345   ResourceState &Resource = *Resources[Index];
 346   assert(Resource.isAResourceGroup() && !Resource.isReserved() &&
 347          "Unexpected resource state found!");
 348   Resource.setReserved();
 349   ReservedResourceGroups ^= 1ULL << Index;
 350 }
 351
 352 void ResourceManager::releaseResource(uint64_t ResourceID) {
 353   const unsigned Index = getResourceStateIndex(ResourceID);
 354   ResourceState &Resource = *Resources[Index];
 355   Resource.clearReserved();
 356   if (Resource.isAResourceGroup())
 357     ReservedResourceGroups ^= 1ULL << Index;
 358   // Now it is safe to release dispatch/issue resources.
 359   if (Resource.isADispatchHazard())
 360     ReservedBuffers ^= 1ULL << Index;
 361 }
 362
 363 } // namespace mca
 364 } // namespace llvm