contrib/llvm/lib/MCA/HardwareUnits/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 "llvm/MCA/HardwareUnits/Scheduler.h"
  15 #include "llvm/Support/Debug.h"
  16 #include "llvm/Support/raw_ostream.h"
  17
  18 namespace llvm {
  19 namespace mca {
  20
  21 #define DEBUG_TYPE "llvm-mca"
  22
  23 void Scheduler::initializeStrategy(std::unique_ptr<SchedulerStrategy> S) {
  24   // Ensure we have a valid (non-null) strategy object.
  25   Strategy = S ? std::move(S) : llvm::make_unique<DefaultSchedulerStrategy>();
  26 }
  27
  28 // Anchor the vtable of SchedulerStrategy and DefaultSchedulerStrategy.
  29 SchedulerStrategy::~SchedulerStrategy() = default;
  30 DefaultSchedulerStrategy::~DefaultSchedulerStrategy() = default;
  31
  32 #ifndef NDEBUG
  33 void Scheduler::dump() const {
  34   dbgs() << "[SCHEDULER]: WaitSet size is: " << WaitSet.size() << '\n';
  35   dbgs() << "[SCHEDULER]: ReadySet size is: " << ReadySet.size() << '\n';
  36   dbgs() << "[SCHEDULER]: IssuedSet size is: " << IssuedSet.size() << '\n';
  37   Resources->dump();
  38 }
  39 #endif
  40
  41 Scheduler::Status Scheduler::isAvailable(const InstRef &IR) const {
  42   const InstrDesc &Desc = IR.getInstruction()->getDesc();
  43
  44   switch (Resources->canBeDispatched(Desc.Buffers)) {
  45   case ResourceStateEvent::RS_BUFFER_UNAVAILABLE:
  46     return Scheduler::SC_BUFFERS_FULL;
  47   case ResourceStateEvent::RS_RESERVED:
  48     return Scheduler::SC_DISPATCH_GROUP_STALL;
  49   case ResourceStateEvent::RS_BUFFER_AVAILABLE:
  50     break;
  51   }
  52
  53   // Give lower priority to LSUnit stall events.
  54   switch (LSU.isAvailable(IR)) {
  55   case LSUnit::LSU_LQUEUE_FULL:
  56     return Scheduler::SC_LOAD_QUEUE_FULL;
  57   case LSUnit::LSU_SQUEUE_FULL:
  58     return Scheduler::SC_STORE_QUEUE_FULL;
  59   case LSUnit::LSU_AVAILABLE:
  60     return Scheduler::SC_AVAILABLE;
  61   }
  62
  63   llvm_unreachable("Don't know how to process this LSU state result!");
  64 }
  65
  66 void Scheduler::issueInstructionImpl(
  67     InstRef &IR,
  68     SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources) {
  69   Instruction *IS = IR.getInstruction();
  70   const InstrDesc &D = IS->getDesc();
  71
  72   // Issue the instruction and collect all the consumed resources
  73   // into a vector. That vector is then used to notify the listener.
  74   Resources->issueInstruction(D, UsedResources);
  75
  76   // Notify the instruction that it started executing.
  77   // This updates the internal state of each write.
  78   IS->execute();
  79
  80   if (IS->isExecuting())
  81     IssuedSet.emplace_back(IR);
  82   else if (IS->isExecuted())
  83     LSU.onInstructionExecuted(IR);
  84 }
  85
  86 // Release the buffered resources and issue the instruction.
  87 void Scheduler::issueInstruction(
  88     InstRef &IR,
  89     SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources,
  90     SmallVectorImpl<InstRef> &ReadyInstructions) {
  91   const Instruction &Inst = *IR.getInstruction();
  92   bool HasDependentUsers = Inst.hasDependentUsers();
  93
  94   Resources->releaseBuffers(Inst.getDesc().Buffers);
  95   issueInstructionImpl(IR, UsedResources);
  96   // Instructions that have been issued during this cycle might have unblocked
  97   // other dependent instructions. Dependent instructions may be issued during
  98   // this same cycle if operands have ReadAdvance entries.  Promote those
  99   // instructions to the ReadySet and notify the caller that those are ready.
 100   if (HasDependentUsers)
 101     promoteToReadySet(ReadyInstructions);
 102 }
 103
 104 void Scheduler::promoteToReadySet(SmallVectorImpl<InstRef> &Ready) {
 105   // Scan the set of waiting instructions and promote them to the
 106   // ready queue if operands are all ready.
 107   unsigned RemovedElements = 0;
 108   for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) {
 109     InstRef &IR = *I;
 110     if (!IR)
 111       break;
 112
 113     // Check if this instruction is now ready. In case, force
 114     // a transition in state using method 'update()'.
 115     Instruction &IS = *IR.getInstruction();
 116     if (!IS.isReady())
 117       IS.update();
 118
 119     // Check if there are still unsolved data dependencies.
 120     if (!isReady(IR)) {
 121       ++I;
 122       continue;
 123     }
 124
 125     Ready.emplace_back(IR);
 126     ReadySet.emplace_back(IR);
 127
 128     IR.invalidate();
 129     ++RemovedElements;
 130     std::iter_swap(I, E - RemovedElements);
 131   }
 132
 133   WaitSet.resize(WaitSet.size() - RemovedElements);
 134 }
 135
 136 InstRef Scheduler::select() {
 137   unsigned QueueIndex = ReadySet.size();
 138   for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) {
 139     const InstRef &IR = ReadySet[I];
 140     if (QueueIndex == ReadySet.size() ||
 141         Strategy->compare(IR, ReadySet[QueueIndex])) {
 142       const InstrDesc &D = IR.getInstruction()->getDesc();
 143       if (Resources->canBeIssued(D))
 144         QueueIndex = I;
 145     }
 146   }
 147
 148   if (QueueIndex == ReadySet.size())
 149     return InstRef();
 150
 151   // We found an instruction to issue.
 152   InstRef IR = ReadySet[QueueIndex];
 153   std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]);
 154   ReadySet.pop_back();
 155   return IR;
 156 }
 157
 158 void Scheduler::updateIssuedSet(SmallVectorImpl<InstRef> &Executed) {
 159   unsigned RemovedElements = 0;
 160   for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) {
 161     InstRef &IR = *I;
 162     if (!IR)
 163       break;
 164     Instruction &IS = *IR.getInstruction();
 165     if (!IS.isExecuted()) {
 166       LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR
 167                         << " is still executing.\n");
 168       ++I;
 169       continue;
 170     }
 171
 172     // Instruction IR has completed execution.
 173     LSU.onInstructionExecuted(IR);
 174     Executed.emplace_back(IR);
 175     ++RemovedElements;
 176     IR.invalidate();
 177     std::iter_swap(I, E - RemovedElements);
 178   }
 179
 180   IssuedSet.resize(IssuedSet.size() - RemovedElements);
 181 }
 182
 183 void Scheduler::cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
 184                            SmallVectorImpl<InstRef> &Executed,
 185                            SmallVectorImpl<InstRef> &Ready) {
 186   // Release consumed resources.
 187   Resources->cycleEvent(Freed);
 188
 189   // Propagate the cycle event to the 'Issued' and 'Wait' sets.
 190   for (InstRef &IR : IssuedSet)
 191     IR.getInstruction()->cycleEvent();
 192
 193   updateIssuedSet(Executed);
 194
 195   for (InstRef &IR : WaitSet)
 196     IR.getInstruction()->cycleEvent();
 197
 198   promoteToReadySet(Ready);
 199 }
 200
 201 bool Scheduler::mustIssueImmediately(const InstRef &IR) const {
 202   const InstrDesc &Desc = IR.getInstruction()->getDesc();
 203   if (Desc.isZeroLatency())
 204     return true;
 205   // Instructions that use an in-order dispatch/issue processor resource must be
 206   // issued immediately to the pipeline(s). Any other in-order buffered
 207   // resources (i.e. BufferSize=1) is consumed.
 208   return Desc.MustIssueImmediately;
 209 }
 210
 211 void Scheduler::dispatch(const InstRef &IR) {
 212   const InstrDesc &Desc = IR.getInstruction()->getDesc();
 213   Resources->reserveBuffers(Desc.Buffers);
 214
 215   // If necessary, reserve queue entries in the load-store unit (LSU).
 216   bool IsMemOp = Desc.MayLoad || Desc.MayStore;
 217   if (IsMemOp)
 218     LSU.dispatch(IR);
 219
 220   if (!isReady(IR)) {
 221     LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n");
 222     WaitSet.push_back(IR);
 223     return;
 224   }
 225
 226   // Don't add a zero-latency instruction to the Ready queue.
 227   // A zero-latency instruction doesn't consume any scheduler resources. That is
 228   // because it doesn't need to be executed, and it is often removed at register
 229   // renaming stage. For example, register-register moves are often optimized at
 230   // register renaming stage by simply updating register aliases. On some
 231   // targets, zero-idiom instructions (for example: a xor that clears the value
 232   // of a register) are treated specially, and are often eliminated at register
 233   // renaming stage.
 234   if (!mustIssueImmediately(IR)) {
 235     LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n");
 236     ReadySet.push_back(IR);
 237   }
 238 }
 239
 240 bool Scheduler::isReady(const InstRef &IR) const {
 241   const InstrDesc &Desc = IR.getInstruction()->getDesc();
 242   bool IsMemOp = Desc.MayLoad || Desc.MayStore;
 243   return IR.getInstruction()->isReady() && (!IsMemOp || LSU.isReady(IR));
 244 }
 245
 246 } // namespace mca
 247 } // namespace llvm