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

   1 //===---------------------- ExecuteStage.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 /// \file
  10 ///
  11 /// This file defines the execution stage of an instruction pipeline.
  12 ///
  13 /// The ExecuteStage is responsible for managing the hardware scheduler
  14 /// and issuing notifications that an instruction has been executed.
  15 ///
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "ExecuteStage.h"
  19 #include "Scheduler.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/Support/Debug.h"
  22
  23 #define DEBUG_TYPE "llvm-mca"
  24
  25 namespace mca {
  26
  27 using namespace llvm;
  28
  29 // Reclaim the simulated resources used by the scheduler.
  30 void ExecuteStage::reclaimSchedulerResources() {
  31   SmallVector<ResourceRef, 8> ResourcesFreed;
  32   HWS.reclaimSimulatedResources(ResourcesFreed);
  33   for (const ResourceRef &RR : ResourcesFreed)
  34     notifyResourceAvailable(RR);
  35 }
  36
  37 // Update the scheduler's instruction queues.
  38 void ExecuteStage::updateSchedulerQueues() {
  39   SmallVector<InstRef, 4> InstructionIDs;
  40   HWS.updateIssuedQueue(InstructionIDs);
  41   for (const InstRef &IR : InstructionIDs)
  42     notifyInstructionExecuted(IR);
  43   InstructionIDs.clear();
  44
  45   HWS.updatePendingQueue(InstructionIDs);
  46   for (const InstRef &IR : InstructionIDs)
  47     notifyInstructionReady(IR);
  48 }
  49
  50 // Issue instructions that are waiting in the scheduler's ready queue.
  51 void ExecuteStage::issueReadyInstructions() {
  52   SmallVector<InstRef, 4> InstructionIDs;
  53   InstRef IR = HWS.select();
  54   while (IR.isValid()) {
  55     SmallVector<std::pair<ResourceRef, double>, 4> Used;
  56     HWS.issueInstruction(IR, Used);
  57
  58     // Reclaim instruction resources and perform notifications.
  59     const InstrDesc &Desc = IR.getInstruction()->getDesc();
  60     notifyReleasedBuffers(Desc.Buffers);
  61     notifyInstructionIssued(IR, Used);
  62     if (IR.getInstruction()->isExecuted())
  63       notifyInstructionExecuted(IR);
  64
  65     // Instructions that have been issued during this cycle might have unblocked
  66     // other dependent instructions. Dependent instructions may be issued during
  67     // this same cycle if operands have ReadAdvance entries.  Promote those
  68     // instructions to the ReadyQueue and tell to the caller that we need
  69     // another round of 'issue()'.
  70     HWS.promoteToReadyQueue(InstructionIDs);
  71     for (const InstRef &I : InstructionIDs)
  72       notifyInstructionReady(I);
  73     InstructionIDs.clear();
  74
  75     // Select the next instruction to issue.
  76     IR = HWS.select();
  77   }
  78 }
  79
  80 // The following routine is the maintenance routine of the ExecuteStage.
  81 // It is responsible for updating the hardware scheduler (HWS), including
  82 // reclaiming the HWS's simulated hardware resources, as well as updating the
  83 // HWS's queues.
  84 //
  85 // This routine also processes the instructions that are ready for issuance.
  86 // These instructions are managed by the HWS's ready queue and can be accessed
  87 // via the Scheduler::select() routine.
  88 //
  89 // Notifications are issued to this stage's listeners when instructions are
  90 // moved between the HWS's queues.  In particular, when an instruction becomes
  91 // ready or executed.
  92 void ExecuteStage::cycleStart() {
  93   reclaimSchedulerResources();
  94   updateSchedulerQueues();
  95   issueReadyInstructions();
  96 }
  97
  98 // Schedule the instruction for execution on the hardware.
  99 bool ExecuteStage::execute(InstRef &IR) {
 100 #ifndef NDEBUG
 101   // Ensure that the HWS has not stored this instruction in its queues.
 102   HWS.sanityCheck(IR);
 103 #endif
 104   // Reserve a slot in each buffered resource. Also, mark units with
 105   // BufferSize=0 as reserved. Resources with a buffer size of zero will only
 106   // be released after MCIS is issued, and all the ResourceCycles for those
 107   // units have been consumed.
 108   const InstrDesc &Desc = IR.getInstruction()->getDesc();
 109   HWS.reserveBuffers(Desc.Buffers);
 110   notifyReservedBuffers(Desc.Buffers);
 111
 112   // Obtain a slot in the LSU.  If we cannot reserve resources, return true, so
 113   // that succeeding stages can make progress.
 114   if (!HWS.reserveResources(IR))
 115     return true;
 116
 117   // If we did not return early, then the scheduler is ready for execution.
 118   notifyInstructionReady(IR);
 119
 120   // Don't add a zero-latency instruction to the Wait or Ready queue.
 121   // A zero-latency instruction doesn't consume any scheduler resources. That is
 122   // because it doesn't need to be executed, and it is often removed at register
 123   // renaming stage. For example, register-register moves are often optimized at
 124   // register renaming stage by simply updating register aliases. On some
 125   // targets, zero-idiom instructions (for example: a xor that clears the value
 126   // of a register) are treated specially, and are often eliminated at register
 127   // renaming stage.
 128   //
 129   // Instructions that use an in-order dispatch/issue processor resource must be
 130   // issued immediately to the pipeline(s). Any other in-order buffered
 131   // resources (i.e. BufferSize=1) is consumed.
 132   //
 133   // If we cannot issue immediately, the HWS will add IR to its ready queue for
 134   // execution later, so we must return early here.
 135   if (!HWS.issueImmediately(IR))
 136     return true;
 137
 138   LLVM_DEBUG(dbgs() << "[SCHEDULER] Instruction #" << IR
 139                     << " issued immediately\n");
 140
 141   // Issue IR.  The resources for this issuance will be placed in 'Used.'
 142   SmallVector<std::pair<ResourceRef, double>, 4> Used;
 143   HWS.issueInstruction(IR, Used);
 144
 145   // Perform notifications.
 146   notifyReleasedBuffers(Desc.Buffers);
 147   notifyInstructionIssued(IR, Used);
 148   if (IR.getInstruction()->isExecuted())
 149     notifyInstructionExecuted(IR);
 150
 151   return true;
 152 }
 153
 154 void ExecuteStage::notifyInstructionExecuted(const InstRef &IR) {
 155   HWS.onInstructionExecuted(IR);
 156   LLVM_DEBUG(dbgs() << "[E] Instruction Executed: #" << IR << '\n');
 157   notifyEvent<HWInstructionEvent>(
 158       HWInstructionEvent(HWInstructionEvent::Executed, IR));
 159   RCU.onInstructionExecuted(IR.getInstruction()->getRCUTokenID());
 160 }
 161
 162 void ExecuteStage::notifyInstructionReady(const InstRef &IR) {
 163   LLVM_DEBUG(dbgs() << "[E] Instruction Ready: #" << IR << '\n');
 164   notifyEvent<HWInstructionEvent>(
 165       HWInstructionEvent(HWInstructionEvent::Ready, IR));
 166 }
 167
 168 void ExecuteStage::notifyResourceAvailable(const ResourceRef &RR) {
 169   LLVM_DEBUG(dbgs() << "[E] Resource Available: [" << RR.first << '.'
 170                     << RR.second << "]\n");
 171   for (HWEventListener *Listener : getListeners())
 172     Listener->onResourceAvailable(RR);
 173 }
 174
 175 void ExecuteStage::notifyInstructionIssued(
 176     const InstRef &IR, ArrayRef<std::pair<ResourceRef, double>> Used) {
 177   LLVM_DEBUG({
 178     dbgs() << "[E] Instruction Issued: #" << IR << '\n';
 179     for (const std::pair<ResourceRef, unsigned> &Resource : Used) {
 180       dbgs() << "[E] Resource Used: [" << Resource.first.first << '.'
 181              << Resource.first.second << "], ";
 182       dbgs() << "cycles: " << Resource.second << '\n';
 183     }
 184   });
 185   notifyEvent<HWInstructionEvent>(HWInstructionIssuedEvent(IR, Used));
 186 }
 187
 188 void ExecuteStage::notifyReservedBuffers(ArrayRef<uint64_t> Buffers) {
 189   if (Buffers.empty())
 190     return;
 191
 192   SmallVector<unsigned, 4> BufferIDs(Buffers.begin(), Buffers.end());
 193   std::transform(Buffers.begin(), Buffers.end(), BufferIDs.begin(),
 194                  [&](uint64_t Op) { return HWS.getResourceID(Op); });
 195   for (HWEventListener *Listener : getListeners())
 196     Listener->onReservedBuffers(BufferIDs);
 197 }
 198
 199 void ExecuteStage::notifyReleasedBuffers(ArrayRef<uint64_t> Buffers) {
 200   if (Buffers.empty())
 201     return;
 202
 203   SmallVector<unsigned, 4> BufferIDs(Buffers.begin(), Buffers.end());
 204   std::transform(Buffers.begin(), Buffers.end(), BufferIDs.begin(),
 205                  [&](uint64_t Op) { return HWS.getResourceID(Op); });
 206   for (HWEventListener *Listener : getListeners())
 207     Listener->onReleasedBuffers(BufferIDs);
 208 }
 209
 210 } // namespace mca