contrib/llvm/tools/llvm-mca/Scheduler.cpp

   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