[llvm-mca] Move the logic that computes the scheduler's queue usage to the BackendStatistics view.

[andreadb]

Summary

This patch introduces two new callbacks in the event listener interface to handle the "buffered resource reserved" event and the "buffered resource released" event. Every time a buffered resource is used, an event is generated.

Before this patch, the Scheduler (with the help of the ResourceManager) was responsible for tracking the scheduler's queue usage. However, that design forced the Scheduler to 'publish' resource pressure information through the Backend interface.

The goal of this patch is to breaks the dependency between the BackendStatistics view, and the Backend.
Now the Scheduler knows how to notify "buffer reserved/released" events.
The scheduler's queue usage analysis has been moved to the BackendStatistics.

No functional change intended.

Note: I didn't add other tests because scheduler-queue-usage.s in the X86/BtVer2 directory already checks that the tool reports the right scheduler usage information.

[andreadb]

Patch updated.

[RKSimon]

LGTM

llvm/trunk/tools/llvm-mca/Backend.h

public:
   }
   void eraseInstruction(unsigned Index) { Instructions.erase(Index); }
   unsigned getTotalRegisterMappingsCreated() const {
     return DU->getTotalRegisterMappingsCreated();
   }
   unsigned getMaxUsedRegisterMappings() const {
     return DU->getMaxUsedRegisterMappings();
   }
-  void getBuffersUsage(std::vector<BufferUsageEntry> &Usage) const {
-    return HWS->getBuffersUsage(Usage);
-  }
 
   void addEventListener(HWEventListener *Listener);
   void notifyCycleBegin(unsigned Cycle);
   void notifyInstructionEvent(const HWInstructionEvent &Event);
   void notifyStallEvent(const HWStallEvent &Event);
   void notifyResourceAvailable(const ResourceRef &RR);
+  void notifyReservedBuffers(llvm::ArrayRef<unsigned> Buffers);
+  void notifyReleasedBuffers(llvm::ArrayRef<unsigned> Buffers);
   void notifyCycleEnd(unsigned Cycle);
 };
 
 } // namespace mca
 
 #endif

llvm/trunk/tools/llvm-mca/Backend.cpp

 
 void Backend::notifyResourceAvailable(const ResourceRef &RR) {
   DEBUG(dbgs() << "[E] Resource Available: [" << RR.first << '.' << RR.second
                << "]\n");
   for (HWEventListener *Listener : Listeners)
     Listener->onResourceAvailable(RR);
 }
 
+void Backend::notifyReservedBuffers(ArrayRef<unsigned> Buffers) {
+  for (HWEventListener *Listener : Listeners)
+    Listener->onReservedBuffers(Buffers);
+}
+
+void Backend::notifyReleasedBuffers(ArrayRef<unsigned> Buffers) {
+  for (HWEventListener *Listener : Listeners)
+    Listener->onReleasedBuffers(Buffers);
+}
+
 void Backend::notifyCycleEnd(unsigned Cycle) {
   DEBUG(dbgs() << "[E] Cycle end: " << Cycle << "\n\n");
   for (HWEventListener *Listener : Listeners)
     Listener->onCycleEnd(Cycle);
 }
 } // namespace mca.

llvm/trunk/tools/llvm-mca/BackendStatistics.h

class BackendStatistics : public View {
   unsigned NumIssued;
   unsigned NumRetired;
   unsigned NumCycles;
 
   // Counts dispatch stall events caused by unavailability of resources.  There
   // is one counter for every generic stall kind (see class HWStallEvent).
   llvm::SmallVector<unsigned, 8> HWStalls;
 
+  // Tracks the usage of a scheduler's queue.
+  struct BufferUsage {
+    unsigned SlotsInUse;
+    unsigned MaxUsedSlots;
+  };
+
+  // There is a map entry for each buffered resource in the scheduling model.
+  // Every time a buffer is consumed/freed, this view updates the corresponding
+  // entry.
+  llvm::DenseMap<unsigned, BufferUsage> BufferedResources;
+
   void updateHistograms() {
     DispatchGroupSizePerCycle[NumDispatched]++;
     IssuedPerCycle[NumIssued]++;
     RetiredPerCycle[NumRetired]++;
     NumDispatched = 0;
     NumIssued = 0;
     NumRetired = 0;
   }
 
   void printRetireUnitStatistics(llvm::raw_ostream &OS) const;
   void printDispatchUnitStatistics(llvm::raw_ostream &OS) const;
   void printSchedulerStatistics(llvm::raw_ostream &OS) const;
 
   void printDispatchStalls(llvm::raw_ostream &OS) const;
   void printRATStatistics(llvm::raw_ostream &OS, unsigned Mappings,
                           unsigned MaxUsedMappings) const;
   void printRCUStatistics(llvm::raw_ostream &OS, const Histogram &Histogram,
                           unsigned Cycles) const;
   void printDispatchUnitUsage(llvm::raw_ostream &OS, const Histogram &Stats,
                               unsigned Cycles) const;
   void printIssuePerCycle(const Histogram &IssuePerCycle,
                           unsigned TotalCycles) const;
-  void printSchedulerUsage(llvm::raw_ostream &OS, const llvm::MCSchedModel &SM,
-                           const llvm::ArrayRef<BufferUsageEntry> &Usage) const;
+  void printSchedulerUsage(llvm::raw_ostream &OS,
+                           const llvm::MCSchedModel &SM) const;
 
 public:
   BackendStatistics(const Backend &backend, const llvm::MCSubtargetInfo &sti)
       : B(backend), STI(sti), NumDispatched(0), NumIssued(0), NumRetired(0),
         NumCycles(0), HWStalls(HWStallEvent::LastGenericEvent) {}
 
   void onInstructionEvent(const HWInstructionEvent &Event) override;
 
   void onCycleBegin(unsigned Cycle) override { NumCycles++; }
 
   void onCycleEnd(unsigned Cycle) override { updateHistograms(); }
 
   void onStallEvent(const HWStallEvent &Event) override {
     if (Event.Type < HWStallEvent::LastGenericEvent)
       HWStalls[Event.Type]++;
   }
 
+  // Increases the number of used scheduler queue slots of every buffered
+  // resource in the Buffers set.
+  void onReservedBuffers(llvm::ArrayRef<unsigned> Buffers);
+
+  // Decreases by one the number of used scheduler queue slots of every
+  // buffered resource in the Buffers set.
+  void onReleasedBuffers(llvm::ArrayRef<unsigned> Buffers);
+
   void printView(llvm::raw_ostream &OS) const override {
     printDispatchStalls(OS);
     printRATStatistics(OS, B.getTotalRegisterMappingsCreated(),
                        B.getMaxUsedRegisterMappings());
     printDispatchUnitStatistics(OS);
     printSchedulerStatistics(OS);
     printRetireUnitStatistics(OS);
 
-    std::vector<BufferUsageEntry> Usage;
-    B.getBuffersUsage(Usage);
-    printSchedulerUsage(OS, STI.getSchedModel(), Usage);
+    printSchedulerUsage(OS, STI.getSchedModel());
   }
 };
-
 } // namespace mca
 
 #endif

llvm/trunk/tools/llvm-mca/BackendStatistics.cpp

void BackendStatistics::onInstructionEvent(const HWInstructionEvent &Event) {
   case HWInstructionEvent::Dispatched:
     ++NumDispatched;
     break;
   default:
     break;
   }
 }
 
+void BackendStatistics::onReservedBuffers(ArrayRef<unsigned> Buffers) {
+  for (const unsigned Buffer : Buffers) {
+    if (BufferedResources.find(Buffer) != BufferedResources.end()) {
+      BufferUsage &BU = BufferedResources[Buffer];
+      BU.SlotsInUse++;
+      BU.MaxUsedSlots = std::max(BU.MaxUsedSlots, BU.SlotsInUse);
+      continue;
+    }
+
+    BufferedResources.insert(
+        std::pair<unsigned, BufferUsage>(Buffer, {1U, 1U}));
+  }
+}
+
+void BackendStatistics::onReleasedBuffers(ArrayRef<unsigned> Buffers) {
+  for (const unsigned Buffer : Buffers) {
+    assert(BufferedResources.find(Buffer) != BufferedResources.end() &&
+           "Buffered resource not in map?");
+    BufferUsage &BU = BufferedResources[Buffer];
+    BU.SlotsInUse--;
+  }
+}
+
 void BackendStatistics::printRetireUnitStatistics(llvm::raw_ostream &OS) const {
   std::string Buffer;
   raw_string_ostream TempStream(Buffer);
   TempStream << "\n\nRetire Control Unit - "
              << "number of cycles where we saw N instructions retired:\n";
   TempStream << "[# retired], [# cycles]\n";
 
   for (const std::pair<unsigned, unsigned> &Entry : RetiredPerCycle) {
TempStream << "\nSQ      - Store queue full:                          "
              << HWStalls[HWStallEvent::StoreQueueFull];
   TempStream << "\nGROUP   - Static restrictions on the dispatch group: "
              << HWStalls[HWStallEvent::DispatchGroupStall];
   TempStream << '\n';
   TempStream.flush();
   OS << Buffer;
 }
 
-void BackendStatistics::printSchedulerUsage(
-    raw_ostream &OS, const MCSchedModel &SM,
-    const ArrayRef<BufferUsageEntry> &Usage) const {
- 
+void BackendStatistics::printSchedulerUsage(raw_ostream &OS,
+                                            const MCSchedModel &SM) const {
   std::string Buffer;
   raw_string_ostream TempStream(Buffer);
   TempStream << "\n\nScheduler's queue usage:\n";
   // Early exit if no buffered resources were consumed.
-  if (Usage.empty()) {
+  if (BufferedResources.empty()) {
     TempStream << "No scheduler resources used.\n";
     TempStream.flush();
     OS << Buffer;
     return;
   }
 
   for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) {
     const MCProcResourceDesc &ProcResource = *SM.getProcResource(I);
-    if (!ProcResource.BufferSize)
+    if (ProcResource.BufferSize <= 0)
       continue;
 
-    for (const BufferUsageEntry &Entry : Usage)
-      if (I == Entry.first)
-        TempStream << ProcResource.Name << ",  " << Entry.second << '/'
-                   << ProcResource.BufferSize << '\n';
+    const BufferUsage &BU = BufferedResources.lookup(I);
+    TempStream << ProcResource.Name << ",  " << BU.MaxUsedSlots << '/'
   }
 
   TempStream.flush();
   OS << Buffer;
 }
-
 } // namespace mca

llvm/trunk/tools/llvm-mca/HWEventListener.h

public:
   virtual void onCycleEnd(unsigned Cycle) {}
 
   virtual void onInstructionEvent(const HWInstructionEvent &Event) {}
   virtual void onStallEvent(const HWStallEvent &Event) {}
 
   using ResourceRef = std::pair<uint64_t, uint64_t>;
   virtual void onResourceAvailable(const ResourceRef &RRef) {}
 
+  // Events generated by the Scheduler when buffered resources are
+  // consumed/freed.
+  virtual void onReservedBuffers(llvm::ArrayRef<unsigned> Buffers) {}
+  virtual void onReleasedBuffers(llvm::ArrayRef<unsigned> Buffers) {}
+
   virtual ~HWEventListener() {}
 
 private:
   virtual void anchor();
 };
 
 } // namespace mca
 
 #endif

llvm/trunk/tools/llvm-mca/Scheduler.h

class ResourceState {
   // That means, this resource is reserved starting from the dispatch event,
   // until all the "resource cycles" are consumed after the issue event.
   // While this resource is reserved, no other instruction may be dispatched.
   int BufferSize;
 
   // Available slots in the buffer (zero, if this is not a buffered resource).
   unsigned AvailableSlots;
 
-  // Maximum number of buffer slots seen used during one cycle.
-  // This helps tracking dynamic dispatch stalls caused by the lack of
-  // entries in the scheduler's queue.
-  unsigned MaxUsedSlots;
-
   // True if this is resource is currently unavailable.
   // An instruction may "reserve" a resource for a number of cycles.
   // During those cycles, the reserved resource cannot be used for other
   // instructions, even if the ReadyMask is set.
   bool Unavailable;
 
   bool isSubResourceReady(uint64_t ID) const { return ReadyMask & ID; }
 
ResourceState(const llvm::MCProcResourceDesc &Desc, unsigned Index,
     bool IsAGroup = llvm::countPopulation(ResourceMask) > 1;
     ResourceSizeMask = IsAGroup ? computeResourceSizeMaskForGroup(ResourceMask)
                                 : ((1ULL << Desc.NumUnits) - 1);
     NextInSequenceMask = ResourceSizeMask;
     RemovedFromNextInSequence = 0;
     ReadyMask = ResourceSizeMask;
     BufferSize = Desc.BufferSize;
     AvailableSlots = BufferSize == -1 ? 0U : static_cast<unsigned>(BufferSize);
-    MaxUsedSlots = 0;
     Unavailable = false;
   }
 
   unsigned getProcResourceID() const { return ProcResourceDescIndex; }
   uint64_t getResourceMask() const { return ResourceMask; }
   int getBufferSize() const { return BufferSize; }
-  unsigned getMaxUsedSlots() const { return MaxUsedSlots; }
 
   bool isBuffered() const { return BufferSize > 0; }
   bool isInOrder() const { return BufferSize == 1; }
   bool isADispatchHazard() const { return BufferSize == 0; }
   bool isReserved() const { return Unavailable; }
 
   void setReserved() { Unavailable = true; }
   void clearReserved() { Unavailable = false; }
ResourceStateEvent isBufferAvailable() const {
     if (!isBuffered() || AvailableSlots)
       return RS_BUFFER_AVAILABLE;
     return RS_BUFFER_UNAVAILABLE;
   }
 
   void reserveBuffer() {
     if (AvailableSlots)
       AvailableSlots--;
-    unsigned UsedSlots = static_cast<unsigned>(BufferSize) - AvailableSlots;
-    MaxUsedSlots = std::max(MaxUsedSlots, UsedSlots);
   }
 
   void releaseBuffer() {
     if (BufferSize > 0)
       AvailableSlots++;
     assert(AvailableSlots <= static_cast<unsigned>(BufferSize));
   }
 

 public:
   ResourceManager(const llvm::MCSchedModel &SM)
       : ProcResID2Mask(SM.getNumProcResourceKinds()) {
     initialize(SM);
   }
 
   // Returns RS_BUFFER_AVAILABLE if buffered resources are not reserved, and if
   // there are enough available slots in the buffers.
-  ResourceStateEvent
-  canBeDispatched(const llvm::ArrayRef<uint64_t> Buffers) const;
+  ResourceStateEvent canBeDispatched(llvm::ArrayRef<uint64_t> Buffers) const;
+
+  // Return the processor resource identifier associated to this Mask.
+  unsigned resolveResourceMask(uint64_t Mask) const {
+    return Resources.find(Mask)->second->getProcResourceID();
+  }
 
   // Consume a slot in every buffered resource from array 'Buffers'. Resource
   // units that are dispatch hazards (i.e. BufferSize=0) are marked as reserved.
   void reserveBuffers(const llvm::ArrayRef<uint64_t> Buffers);
 
   // Release buffer entries previously allocated by method reserveBuffers.
   void releaseBuffers(const llvm::ArrayRef<uint64_t> Buffers);
 
public:
   bool canBeIssued(const InstrDesc &Desc) const;
 
   void issueInstruction(
       unsigned Index, const InstrDesc &Desc,
       llvm::SmallVectorImpl<std::pair<ResourceRef, unsigned>> &Pipes);
 
   void cycleEvent(llvm::SmallVectorImpl<ResourceRef> &ResourcesFreed);
 
-  void getBuffersUsage(std::vector<BufferUsageEntry> &Usage) const {
-    for (const std::pair<uint64_t, UniqueResourceState> &Resource : Resources) {
-      const ResourceState &RS = *Resource.second;
-      if (RS.isBuffered())
-        Usage.emplace_back(std::pair<unsigned, unsigned>(RS.getProcResourceID(),
-                                                         RS.getMaxUsedSlots()));
-    }
-  }
-
 #ifndef NDEBUG
   void dump() const {
     for (const std::pair<uint64_t, UniqueResourceState> &Resource : Resources)
       Resource.second->dump();
   }
 #endif
 }; // namespace mca
 
class Scheduler {
 
   void notifyInstructionIssued(
       unsigned Index,
       const llvm::ArrayRef<std::pair<ResourceRef, unsigned>> &Used);
   void notifyInstructionExecuted(unsigned Index);
   void notifyInstructionReady(unsigned Index);
   void notifyResourceAvailable(const ResourceRef &RR);
 
+  // Notify the Backend that buffered resources were consumed.
+  void notifyReservedBuffers(llvm::ArrayRef<uint64_t> Buffers);
+  // Notify the Backend that buffered resources were freed.
+  void notifyReleasedBuffers(llvm::ArrayRef<uint64_t> Buffers);
+
   /// Issue instructions from the ready queue by giving priority to older
   /// instructions.
   void issue();
 
   /// Issue an instruction without updating the ready queue.
   void issueInstruction(Instruction &IS, unsigned InstrIndex);
   void updatePendingQueue();
   void updateIssuedQueue();
enum Event {
     HWS_ST_QUEUE_UNAVAILABLE
   };
 
   Event canBeDispatched(const InstrDesc &Desc) const;
   void scheduleInstruction(unsigned Idx, Instruction &MCIS);
 
   void cycleEvent(unsigned Cycle);
 
-  void getBuffersUsage(std::vector<BufferUsageEntry> &Usage) const {
-    Resources->getBuffersUsage(Usage);
-  }
-
 #ifndef NDEBUG
   void dump() const;
 #endif
 };
 } // Namespace mca
 
 #endif

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

return std::any_of(Desc.Buffers.begin(), Desc.Buffers.end(),
                      [&](const unsigned BufferMask) {
                        return Resources[BufferMask]->isADispatchHazard();
                      });
 }
 
 void ResourceManager::issueInstruction(
     unsigned Index, const InstrDesc &Desc,
     SmallVectorImpl<std::pair<ResourceRef, unsigned>> &Pipes) {
-  releaseBuffers(Desc.Buffers);
   for (const std::pair<uint64_t, ResourceUsage> &R : Desc.Resources) {
     const CycleSegment &CS = R.second.CS;
     if (!CS.size()) {
       releaseResource(R.first);
       continue;
     }
 
     assert(CS.begin() == 0 && "Invalid {Start, End} cycles!");
if (MCIS.isZeroLatency()) {
     notifyInstructionIssued(Idx, {});
     notifyInstructionExecuted(Idx);
     return;
   }
 
   // Consume entries in the reservation stations.
   const InstrDesc &Desc = MCIS.getDesc();
 
+  if (!Desc.Buffers.empty()) {
     // Reserve a slot in each buffered resource. Also, mark units with
-  // BufferSize=0 as reserved. Resources with a buffer size of zero will only be
-  // released after MCIS is issued, and all the ResourceCycles for those units
-  // have been consumed.
+    // BufferSize=0 as reserved. Resources with a buffer size of zero will only
+    // be released after MCIS is issued, and all the ResourceCycles for those
+    // units have been consumed.
     Resources->reserveBuffers(Desc.Buffers);
+    notifyReservedBuffers(Desc.Buffers);
+  }
 
   bool MayLoad = Desc.MayLoad;
   bool MayStore = Desc.MayStore;
   if (MayLoad || MayStore)
     LSU->reserve(Idx, MayLoad, MayStore, Desc.HasSideEffects);
 
   MCIS.dispatch();
   bool IsReady = MCIS.isReady();
case ResourceStateEvent::RS_BUFFER_UNAVAILABLE:
     break;
   case ResourceStateEvent::RS_RESERVED:
     Event = HWS_DISPATCH_GROUP_RESTRICTION;
   }
   return Event;
 }
 
 void Scheduler::issueInstruction(Instruction &IS, unsigned InstrIndex) {
+  const InstrDesc &D = IS.getDesc();
+
+  if (!D.Buffers.empty()) {
+    Resources->releaseBuffers(D.Buffers);
+    notifyReleasedBuffers(D.Buffers);
+  }
+
   // Issue the instruction and collect all the consumed resources
   // into a vector. That vector is then used to notify the listener.
   // Most instructions consume very few resurces (typically one or
   // two resources). We use a small vector here, and conservatively
   // initialize its capacity to 4. This should address the majority of
   // the cases.
   SmallVector<std::pair<ResourceRef, unsigned>, 4> UsedResources;
-
-  const InstrDesc &D = IS.getDesc();
   Resources->issueInstruction(InstrIndex, D, UsedResources);
   // Notify the instruction that it started executing.
   // This updates the internal state of each write.
   IS.execute();
 
   if (D.MaxLatency) {
     IssuedQueue[InstrIndex] = &IS;
     notifyInstructionIssued(InstrIndex, UsedResources);
if (Entry.second->isExecuted()) {
                    << " is still executing.\n");
       ++I;
     }
   }
 }
 
 void Scheduler::notifyInstructionIssued(
     unsigned Index, const ArrayRef<std::pair<ResourceRef, unsigned>> &Used) {
-  DEBUG(dbgs() << "[E] Instruction Issued: " << Index << '\n';
-        for (const std::pair<ResourceRef, unsigned> &Resource
-             : Used) {
-          dbgs() << "[E] Resource Used: [" << Resource.first.first << '.'
-                 << Resource.first.second << "]\n";
-          dbgs() << "           cycles: " << Resource.second << '\n';
-        });
+  DEBUG({
+    dbgs() << "[E] Instruction Issued: " << Index << '\n';
+    for (const std::pair<ResourceRef, unsigned> &Resource : Used) {
+    }
   Owner->notifyInstructionEvent(HWInstructionIssuedEvent(Index, Used));
 }
 
 void Scheduler::notifyInstructionExecuted(unsigned Index) {
   LSU->onInstructionExecuted(Index);
   DEBUG(dbgs() << "[E] Instruction Executed: " << Index << '\n');
   Owner->notifyInstructionEvent(
       HWInstructionEvent(HWInstructionEvent::Executed, Index));
 
   const Instruction &IS = Owner->getInstruction(Index);
   DU->onInstructionExecuted(IS.getRCUTokenID());
 }
 
 void Scheduler::notifyInstructionReady(unsigned Index) {
   DEBUG(dbgs() << "[E] Instruction Ready: " << Index << '\n');
   Owner->notifyInstructionEvent(
       HWInstructionEvent(HWInstructionEvent::Ready, Index));
 }
 
 void Scheduler::notifyResourceAvailable(const ResourceRef &RR) {
   Owner->notifyResourceAvailable(RR);
 }
+
+void Scheduler::notifyReservedBuffers(ArrayRef<uint64_t> Buffers) {
+  SmallVector<unsigned, 4> BufferIDs(Buffers.begin(), Buffers.end());
+  std::transform(
+      Buffers.begin(), Buffers.end(), BufferIDs.begin(),
+      [&](uint64_t Op) { return Resources->resolveResourceMask(Op); });
+  Owner->notifyReservedBuffers(BufferIDs);
+}
+
+void Scheduler::notifyReleasedBuffers(ArrayRef<uint64_t> Buffers) {
+  SmallVector<unsigned, 4> BufferIDs(Buffers.begin(), Buffers.end());
+  std::transform(
+      Buffers.begin(), Buffers.end(), BufferIDs.begin(),
+      [&](uint64_t Op) { return Resources->resolveResourceMask(Op); });
+  Owner->notifyReleasedBuffers(BufferIDs);
+}
 } // namespace mca