Home | History | Annotate | Line # | Download | only in HardwareUnits 
      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, 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
    365