llvm/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(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
  80 bool ResourceState::isReady(unsigned NumUnits) const {
  81   return (!isReserved() || isADispatchHazard()) &&
  82          (unsigned)llvm::popcount(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), 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
 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   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
 347 void 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
 374 void 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
 393 void 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
 402 void 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