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