495 lines · 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-exception6//7//===----------------------------------------------------------------------===//8/// \file9///10/// The classes here represent processor resource units and their management11/// 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 NDEBUG94void ResourceState::dump() const {95 dbgs() << "MASK=" << format_hex(ResourceMask, 16)96 << ", SZMASK=" << format_hex(ResourceSizeMask, 16)97 << ", RDYMASK=" << format_hex(ReadyMask, 16)98 << ", BufferSize=" << BufferSize99 << ", AvailableSlots=" << AvailableSlots100 << ", Reserved=" << Unavailable << '\n';101}102#endif103 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 single184 // 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 with200 // 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 244ResourceStateEvent245ResourceManager::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 resources263 // 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 all278 // 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 can313 // 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, Inserted] = AvailableUnits.try_emplace(ResourceMask);326 if (Inserted) {327 unsigned Index = getResourceStateIndex(ResourceMask);328 unsigned NumUnits = llvm::popcount(Resources[Index]->getReadyMask());329 it->second = NumUnits;330 }331 332 if (!it->second) {333 BusyResourceMask |= it->first;334 continue;335 }336 337 it->second--;338 if (!it->second)339 ConsumedResourceMask |= it->first;340 }341 }342 343 return BusyResourceMask;344}345 346void ResourceManager::issueInstructionImpl(347 const InstrDesc &Desc, SmallVectorImpl<ResourceWithCycles> &Pipes) {348 349 // Step 1.350 // - Issue writes to non-group resources.351 // - Issue writes to groups with only a single resource unit available.352 // - Update reserved groups (if any)353 // - Add any remaining resource usage requests to a Worklist.354 SmallVector<std::pair<uint64_t, ResourceUsage>, 4> Worklist;355 356 using ResourceWithUsage = std::pair<uint64_t, ResourceUsage>;357 358 for (const ResourceWithUsage &R : Desc.Resources) {359 const CycleSegment &CS = R.second.CS;360 if (!CS.size()) {361 releaseResource(R.first);362 continue;363 }364 365 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");366 if (R.second.isReserved()) {367 assert((llvm::popcount(R.first) > 1) && "Expected a group!");368 // Mark this group as reserved.369 assert(R.second.isReserved());370 reserveResource(R.first);371 BusyResources[ResourceRef(R.first, R.first)] += CS.size();372 continue;373 }374 375 const ResourceState &RS = *Resources[getResourceStateIndex(R.first)];376 if (RS.isAResourceGroup() && RS.getNumReadyUnits() > 1) {377 Worklist.push_back(R);378 continue;379 }380 381 ResourceRef Pipe = selectPipe(R.first);382 use(Pipe);383 BusyResources[Pipe] += CS.size();384 Pipes.emplace_back(std::make_pair(Pipe, ReleaseAtCycles(CS.size())));385 }386 387 // Step 2.388 // Prioritize writes to groups with less available resources.389 // NOTE: this algorithm has quadratic complexity in the worst case scenario.390 // On average, this algorithm is expected to perform quite well and always391 // converge in very few iterations. That is mainly because instructions rarely392 // consume more than two or three resource groups.393 394 while (!Worklist.empty()) {395 sort(Worklist, [&](const ResourceWithUsage &Lhs,396 const ResourceWithUsage &Rhs) {397 const ResourceState &LhsRS = *Resources[getResourceStateIndex(Lhs.first)];398 const ResourceState &RhsRS = *Resources[getResourceStateIndex(Rhs.first)];399 uint64_t LhsReadyUnits = LhsRS.getNumReadyUnits();400 uint64_t RhsReadyUnits = RhsRS.getNumReadyUnits();401 if (LhsReadyUnits == RhsReadyUnits)402 return Lhs.first < Rhs.first;403 return LhsReadyUnits < RhsReadyUnits;404 });405 406 SmallVector<ResourceWithUsage, 4> NewWorklist;407 408 for (unsigned I = 0, E = Worklist.size(); I < E; ++I) {409 const auto &Elt = Worklist[I];410 const ResourceState &RS = *Resources[getResourceStateIndex(Elt.first)];411 412 if (I == 0 || RS.getNumReadyUnits() == 1) {413 ResourceRef Pipe = selectPipe(Elt.first);414 use(Pipe);415 const CycleSegment &CS = Elt.second.CS;416 BusyResources[Pipe] += CS.size();417 Pipes.emplace_back(std::make_pair(Pipe, ReleaseAtCycles(CS.size())));418 continue;419 }420 421 NewWorklist.push_back(Elt);422 }423 424 swap(NewWorklist, Worklist);425 };426}427 428void ResourceManager::fastIssueInstruction(429 const InstrDesc &Desc, SmallVectorImpl<ResourceWithCycles> &Pipes) {430 for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {431 const CycleSegment &CS = R.second.CS;432 if (!CS.size()) {433 releaseResource(R.first);434 continue;435 }436 437 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");438 if (!R.second.isReserved()) {439 ResourceRef Pipe = selectPipe(R.first);440 use(Pipe);441 BusyResources[Pipe] += CS.size();442 Pipes.emplace_back(std::pair<ResourceRef, ReleaseAtCycles>(443 Pipe, ReleaseAtCycles(CS.size())));444 } else {445 assert((llvm::popcount(R.first) > 1) && "Expected a group!");446 // Mark this group as reserved.447 assert(R.second.isReserved());448 reserveResource(R.first);449 BusyResources[ResourceRef(R.first, R.first)] += CS.size();450 }451 }452}453 454void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {455 for (std::pair<ResourceRef, unsigned> &BR : BusyResources) {456 if (BR.second)457 BR.second--;458 if (!BR.second) {459 // Release this resource.460 const ResourceRef &RR = BR.first;461 462 if (llvm::popcount(RR.first) == 1)463 release(RR);464 releaseResource(RR.first);465 ResourcesFreed.push_back(RR);466 }467 }468 469 for (const ResourceRef &RF : ResourcesFreed)470 BusyResources.erase(RF);471}472 473void ResourceManager::reserveResource(uint64_t ResourceID) {474 const unsigned Index = getResourceStateIndex(ResourceID);475 ResourceState &Resource = *Resources[Index];476 assert(Resource.isAResourceGroup() && !Resource.isReserved() &&477 "Unexpected resource state found!");478 Resource.setReserved();479 ReservedResourceGroups ^= 1ULL << Index;480}481 482void ResourceManager::releaseResource(uint64_t ResourceID) {483 const unsigned Index = getResourceStateIndex(ResourceID);484 ResourceState &Resource = *Resources[Index];485 Resource.clearReserved();486 if (Resource.isAResourceGroup())487 ReservedResourceGroups ^= 1ULL << Index;488 // Now it is safe to release dispatch/issue resources.489 if (Resource.isADispatchHazard())490 ReservedBuffers ^= 1ULL << Index;491}492 493} // namespace mca494} // namespace llvm495