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 354