1 //===--------------------- Scheduler.cpp ------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // A scheduler for processor resource units and processor resource groups. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "Scheduler.h" 15 #include "Support.h" 16 #include "llvm/Support/Debug.h" 17 #include "llvm/Support/raw_ostream.h" 18 19 namespace mca { 20 21 using namespace llvm; 22 23 #define DEBUG_TYPE "llvm-mca" 24 25 uint64_t ResourceState::selectNextInSequence() { 26 assert(isReady()); 27 uint64_t Next = getNextInSequence(); 28 while (!isSubResourceReady(Next)) { 29 updateNextInSequence(); 30 Next = getNextInSequence(); 31 } 32 return Next; 33 } 34 35 #ifndef NDEBUG 36 void ResourceState::dump() const { 37 dbgs() << "MASK: " << ResourceMask << ", SIZE_MASK: " << ResourceSizeMask 38 << ", NEXT: " << NextInSequenceMask << ", RDYMASK: " << ReadyMask 39 << ", BufferSize=" << BufferSize 40 << ", AvailableSlots=" << AvailableSlots 41 << ", Reserved=" << Unavailable << '\n'; 42 } 43 #endif 44 45 void ResourceManager::initialize(const llvm::MCSchedModel &SM) { 46 computeProcResourceMasks(SM, ProcResID2Mask); 47 for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) 48 addResource(*SM.getProcResource(I), I, ProcResID2Mask[I]); 49 } 50 51 // Adds a new resource state in Resources, as well as a new descriptor in 52 // ResourceDescriptor. Map 'Resources' allows to quickly obtain ResourceState 53 // objects from resource mask identifiers. 54 void ResourceManager::addResource(const MCProcResourceDesc &Desc, 55 unsigned Index, uint64_t Mask) { 56 assert(Resources.find(Mask) == Resources.end() && "Resource already added!"); 57 Resources[Mask] = llvm::make_unique<ResourceState>(Desc, Index, Mask); 58 } 59 60 // Returns the actual resource consumed by this Use. 61 // First, is the primary resource ID. 62 // Second, is the specific sub-resource ID. 63 std::pair<uint64_t, uint64_t> ResourceManager::selectPipe(uint64_t ResourceID) { 64 ResourceState &RS = *Resources[ResourceID]; 65 uint64_t SubResourceID = RS.selectNextInSequence(); 66 if (RS.isAResourceGroup()) 67 return selectPipe(SubResourceID); 68 return std::pair<uint64_t, uint64_t>(ResourceID, SubResourceID); 69 } 70 71 void ResourceState::removeFromNextInSequence(uint64_t ID) { 72 assert(NextInSequenceMask); 73 assert(countPopulation(ID) == 1); 74 if (ID > getNextInSequence()) 75 RemovedFromNextInSequence |= ID; 76 NextInSequenceMask = NextInSequenceMask & (~ID); 77 if (!NextInSequenceMask) { 78 NextInSequenceMask = ResourceSizeMask; 79 assert(NextInSequenceMask != RemovedFromNextInSequence); 80 NextInSequenceMask ^= RemovedFromNextInSequence; 81 RemovedFromNextInSequence = 0; 82 } 83 } 84 85 void ResourceManager::use(ResourceRef RR) { 86 // Mark the sub-resource referenced by RR as used. 87 ResourceState &RS = *Resources[RR.first]; 88 RS.markSubResourceAsUsed(RR.second); 89 // If there are still available units in RR.first, 90 // then we are done. 91 if (RS.isReady()) 92 return; 93 94 // Notify to other resources that RR.first is no longer available. 95 for (const std::pair<uint64_t, UniqueResourceState> &Res : Resources) { 96 ResourceState &Current = *Res.second.get(); 97 if (!Current.isAResourceGroup() || Current.getResourceMask() == RR.first) 98 continue; 99 100 if (Current.containsResource(RR.first)) { 101 Current.markSubResourceAsUsed(RR.first); 102 Current.removeFromNextInSequence(RR.first); 103 } 104 } 105 } 106 107 void ResourceManager::release(ResourceRef RR) { 108 ResourceState &RS = *Resources[RR.first]; 109 bool WasFullyUsed = !RS.isReady(); 110 RS.releaseSubResource(RR.second); 111 if (!WasFullyUsed) 112 return; 113 114 for (const std::pair<uint64_t, UniqueResourceState> &Res : Resources) { 115 ResourceState &Current = *Res.second.get(); 116 if (!Current.isAResourceGroup() || Current.getResourceMask() == RR.first) 117 continue; 118 119 if (Current.containsResource(RR.first)) 120 Current.releaseSubResource(RR.first); 121 } 122 } 123 124 ResourceStateEvent 125 ResourceManager::canBeDispatched(ArrayRef<uint64_t> Buffers) const { 126 ResourceStateEvent Result = ResourceStateEvent::RS_BUFFER_AVAILABLE; 127 for (uint64_t Buffer : Buffers) { 128 Result = isBufferAvailable(Buffer); 129 if (Result != ResourceStateEvent::RS_BUFFER_AVAILABLE) 130 break; 131 } 132 return Result; 133 } 134 135 void ResourceManager::reserveBuffers(ArrayRef<uint64_t> Buffers) { 136 for (const uint64_t R : Buffers) { 137 reserveBuffer(R); 138 ResourceState &Resource = *Resources[R]; 139 if (Resource.isADispatchHazard()) { 140 assert(!Resource.isReserved()); 141 Resource.setReserved(); 142 } 143 } 144 } 145 146 void ResourceManager::releaseBuffers(ArrayRef<uint64_t> Buffers) { 147 for (const uint64_t R : Buffers) 148 releaseBuffer(R); 149 } 150 151 bool ResourceManager::canBeIssued(const InstrDesc &Desc) const { 152 return std::all_of(Desc.Resources.begin(), Desc.Resources.end(), 153 [&](const std::pair<uint64_t, const ResourceUsage> &E) { 154 unsigned NumUnits = 155 E.second.isReserved() ? 0U : E.second.NumUnits; 156 return isReady(E.first, NumUnits); 157 }); 158 } 159 160 // Returns true if all resources are in-order, and there is at least one 161 // resource which is a dispatch hazard (BufferSize = 0). 162 bool ResourceManager::mustIssueImmediately(const InstrDesc &Desc) { 163 if (!canBeIssued(Desc)) 164 return false; 165 bool AllInOrderResources = all_of(Desc.Buffers, [&](uint64_t BufferMask) { 166 const ResourceState &Resource = *Resources[BufferMask]; 167 return Resource.isInOrder() || Resource.isADispatchHazard(); 168 }); 169 if (!AllInOrderResources) 170 return false; 171 172 return any_of(Desc.Buffers, [&](uint64_t BufferMask) { 173 return Resources[BufferMask]->isADispatchHazard(); 174 }); 175 } 176 177 void ResourceManager::issueInstruction( 178 const InstrDesc &Desc, 179 SmallVectorImpl<std::pair<ResourceRef, double>> &Pipes) { 180 for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) { 181 const CycleSegment &CS = R.second.CS; 182 if (!CS.size()) { 183 releaseResource(R.first); 184 continue; 185 } 186 187 assert(CS.begin() == 0 && "Invalid {Start, End} cycles!"); 188 if (!R.second.isReserved()) { 189 ResourceRef Pipe = selectPipe(R.first); 190 use(Pipe); 191 BusyResources[Pipe] += CS.size(); 192 // Replace the resource mask with a valid processor resource index. 193 const ResourceState &RS = *Resources[Pipe.first]; 194 Pipe.first = RS.getProcResourceID(); 195 Pipes.emplace_back( 196 std::pair<ResourceRef, double>(Pipe, static_cast<double>(CS.size()))); 197 } else { 198 assert((countPopulation(R.first) > 1) && "Expected a group!"); 199 // Mark this group as reserved. 200 assert(R.second.isReserved()); 201 reserveResource(R.first); 202 BusyResources[ResourceRef(R.first, R.first)] += CS.size(); 203 } 204 } 205 } 206 207 void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) { 208 for (std::pair<ResourceRef, unsigned> &BR : BusyResources) { 209 if (BR.second) 210 BR.second--; 211 if (!BR.second) { 212 // Release this resource. 213 const ResourceRef &RR = BR.first; 214 215 if (countPopulation(RR.first) == 1) 216 release(RR); 217 218 releaseResource(RR.first); 219 ResourcesFreed.push_back(RR); 220 } 221 } 222 223 for (const ResourceRef &RF : ResourcesFreed) 224 BusyResources.erase(RF); 225 } 226 227 #ifndef NDEBUG 228 void Scheduler::dump() const { 229 dbgs() << "[SCHEDULER]: WaitQueue size is: " << WaitQueue.size() << '\n'; 230 dbgs() << "[SCHEDULER]: ReadyQueue size is: " << ReadyQueue.size() << '\n'; 231 dbgs() << "[SCHEDULER]: IssuedQueue size is: " << IssuedQueue.size() << '\n'; 232 Resources->dump(); 233 } 234 #endif 235 236 bool Scheduler::canBeDispatched(const InstRef &IR, 237 HWStallEvent::GenericEventType &Event) const { 238 Event = HWStallEvent::Invalid; 239 const InstrDesc &Desc = IR.getInstruction()->getDesc(); 240 241 if (Desc.MayLoad && LSU->isLQFull()) 242 Event = HWStallEvent::LoadQueueFull; 243 else if (Desc.MayStore && LSU->isSQFull()) 244 Event = HWStallEvent::StoreQueueFull; 245 else { 246 switch (Resources->canBeDispatched(Desc.Buffers)) { 247 default: 248 return true; 249 case ResourceStateEvent::RS_BUFFER_UNAVAILABLE: 250 Event = HWStallEvent::SchedulerQueueFull; 251 break; 252 case ResourceStateEvent::RS_RESERVED: 253 Event = HWStallEvent::DispatchGroupStall; 254 } 255 } 256 257 return false; 258 } 259 260 void Scheduler::issueInstructionImpl( 261 InstRef &IR, 262 SmallVectorImpl<std::pair<ResourceRef, double>> &UsedResources) { 263 Instruction *IS = IR.getInstruction(); 264 const InstrDesc &D = IS->getDesc(); 265 266 // Issue the instruction and collect all the consumed resources 267 // into a vector. That vector is then used to notify the listener. 268 Resources->issueInstruction(D, UsedResources); 269 270 // Notify the instruction that it started executing. 271 // This updates the internal state of each write. 272 IS->execute(); 273 274 if (IS->isExecuting()) 275 IssuedQueue[IR.getSourceIndex()] = IS; 276 } 277 278 // Release the buffered resources and issue the instruction. 279 void Scheduler::issueInstruction( 280 InstRef &IR, 281 SmallVectorImpl<std::pair<ResourceRef, double>> &UsedResources) { 282 const InstrDesc &Desc = IR.getInstruction()->getDesc(); 283 releaseBuffers(Desc.Buffers); 284 issueInstructionImpl(IR, UsedResources); 285 } 286 287 void Scheduler::promoteToReadyQueue(SmallVectorImpl<InstRef> &Ready) { 288 // Scan the set of waiting instructions and promote them to the 289 // ready queue if operands are all ready. 290 for (auto I = WaitQueue.begin(), E = WaitQueue.end(); I != E;) { 291 const unsigned IID = I->first; 292 Instruction *IS = I->second; 293 294 // Check if this instruction is now ready. In case, force 295 // a transition in state using method 'update()'. 296 if (!IS->isReady()) 297 IS->update(); 298 299 const InstrDesc &Desc = IS->getDesc(); 300 bool IsMemOp = Desc.MayLoad || Desc.MayStore; 301 if (!IS->isReady() || (IsMemOp && !LSU->isReady({IID, IS}))) { 302 ++I; 303 continue; 304 } 305 306 Ready.emplace_back(IID, IS); 307 ReadyQueue[IID] = IS; 308 auto ToRemove = I; 309 ++I; 310 WaitQueue.erase(ToRemove); 311 } 312 } 313 314 InstRef Scheduler::select() { 315 // Find the oldest ready-to-issue instruction in the ReadyQueue. 316 auto It = std::find_if(ReadyQueue.begin(), ReadyQueue.end(), 317 [&](const QueueEntryTy &Entry) { 318 const InstrDesc &D = Entry.second->getDesc(); 319 return Resources->canBeIssued(D); 320 }); 321 322 if (It == ReadyQueue.end()) 323 return {0, nullptr}; 324 325 // We want to prioritize older instructions over younger instructions to 326 // minimize the pressure on the reorder buffer. We also want to 327 // rank higher the instructions with more users to better expose ILP. 328 329 // Compute a rank value based on the age of an instruction (i.e. its source 330 // index) and its number of users. The lower the rank value, the better. 331 int Rank = It->first - It->second->getNumUsers(); 332 for (auto I = It, E = ReadyQueue.end(); I != E; ++I) { 333 int CurrentRank = I->first - I->second->getNumUsers(); 334 if (CurrentRank < Rank) { 335 const InstrDesc &D = I->second->getDesc(); 336 if (Resources->canBeIssued(D)) 337 It = I; 338 } 339 } 340 341 // We found an instruction to issue. 342 InstRef IR(It->first, It->second); 343 ReadyQueue.erase(It); 344 return IR; 345 } 346 347 void Scheduler::updatePendingQueue(SmallVectorImpl<InstRef> &Ready) { 348 // Notify to instructions in the pending queue that a new cycle just 349 // started. 350 for (QueueEntryTy Entry : WaitQueue) 351 Entry.second->cycleEvent(); 352 promoteToReadyQueue(Ready); 353 } 354 355 void Scheduler::updateIssuedQueue(SmallVectorImpl<InstRef> &Executed) { 356 for (auto I = IssuedQueue.begin(), E = IssuedQueue.end(); I != E;) { 357 const QueueEntryTy Entry = *I; 358 Instruction *IS = Entry.second; 359 IS->cycleEvent(); 360 if (IS->isExecuted()) { 361 Executed.push_back({Entry.first, Entry.second}); 362 auto ToRemove = I; 363 ++I; 364 IssuedQueue.erase(ToRemove); 365 } else { 366 LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << Entry.first 367 << " is still executing.\n"); 368 ++I; 369 } 370 } 371 } 372 373 void Scheduler::onInstructionExecuted(const InstRef &IR) { 374 LSU->onInstructionExecuted(IR); 375 } 376 377 void Scheduler::reclaimSimulatedResources(SmallVectorImpl<ResourceRef> &Freed) { 378 Resources->cycleEvent(Freed); 379 } 380 381 bool Scheduler::reserveResources(InstRef &IR) { 382 // If necessary, reserve queue entries in the load-store unit (LSU). 383 const bool Reserved = LSU->reserve(IR); 384 if (!IR.getInstruction()->isReady() || (Reserved && !LSU->isReady(IR))) { 385 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the Wait Queue\n"); 386 WaitQueue[IR.getSourceIndex()] = IR.getInstruction(); 387 return false; 388 } 389 return true; 390 } 391 392 bool Scheduler::issueImmediately(InstRef &IR) { 393 const InstrDesc &Desc = IR.getInstruction()->getDesc(); 394 if (!Desc.isZeroLatency() && !Resources->mustIssueImmediately(Desc)) { 395 LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR 396 << " to the Ready Queue\n"); 397 ReadyQueue[IR.getSourceIndex()] = IR.getInstruction(); 398 return false; 399 } 400 return true; 401 } 402 403 } // namespace mca 404