[llvm-mca] Delay calculation of Cycles per Resources, separate the cycles and resource quantities.

[mattd]

Summary

This patch removes the storing of accumulated floating point data
within the llvm-mca library.

This patch splits-up the two quantities: cycles and number of resource units.
By splitting-up these two quantities, we delay the calculation of "cycles per resource unit"
until that value is read, reducing the chance of accumulating floating point error.

I considered using the APFloat, but after measuring performance, for a large (many iteration)
sample, I decided to go with this faster solution.

[andreadb]

Hi Matt,

tools/llvm-mca/include/HWEventListener.h

60–64 ↗

(On Diff #164768)

I find this comment very hard to read. Maybe it is just my English, however it doesn't what exactly do you mean by reducing floating point error.
The "floating point error" is a loss of precision.

I think you could simply write that class ResourceCycles defines fractions of cycles. Objects are essentially divisions, described by a pair of unsigned. The numerator is a number of cycles, while the denominator is a number of processor resource units.

You can then say that this class is currently used by the ResourcePressureView to compute average resource cycles per instruction/iteration.

98 ↗

(On Diff #164768)

Do we actually need this operator? If it is not used, then please remove it.
we can always add it in future if we think that we actually need it.

tools/llvm-mca/include/HardwareUnits/ResourceManager.h

19 ↗

(On Diff #164768)

This is not nice.
There shouldn't be any reference to HWEventListener from any hardware unit.
This is equivalent to a layering violation to me. Events and event listeners are a concept only known by stages and pipelines.

Either you move this into Instruction.h, or Support.h.

But definitely it should never be in HWEventListener.h

tools/llvm-mca/include/HardwareUnits/Scheduler.h

18 ↗

(On Diff #164768)

Same. This is not okay.

[andreadb]

I noticed that you forgot to add llvm-commits to the subscribers list.
Adding it now.

[mattd]

• Updated the ResourceCycles class description.
• Moved that class into Support.h.
• Removed an unused + operator.

[andreadb]

LGTM.

tools/llvm-mca/include/HWEventListener.h

64–65 ↗

(On Diff #164913)

You can probably add a using to give a name to type std::pair<ResourceRef, ResourceCycles>. I saw that it is used a few times (not just in this class). We should consider adding it if that makes code a bit more readable.

tools/llvm-mca/include/Support.h

29 ↗

(On Diff #164913)

per instruction/iteration.

llvm/trunk/tools/llvm-mca/Views/ResourcePressureView.h

class ResourcePressureView : public View {
   llvm::MCInstPrinter &MCIP;
   const SourceMgr &Source;
 
   // Map to quickly obtain the ResourceUsage column index from a processor
   // resource ID.
   llvm::DenseMap<unsigned, unsigned> Resource2VecIndex;
 
   // Table of resources used by instructions.
-  std::vector<double> ResourceUsage;
+  std::vector<ResourceCycles> ResourceUsage;
   unsigned NumResourceUnits;
 
   const llvm::MCInst &GetMCInstFromIndex(unsigned Index) const;
   void printResourcePressurePerIteration(llvm::raw_ostream &OS,
                                          unsigned Executions) const;
   void printResourcePressurePerInstruction(llvm::raw_ostream &OS,
                                            unsigned Executions) const;
   void initialize();

llvm/trunk/tools/llvm-mca/Views/ResourcePressureView.cpp

 }
 
 void ResourcePressureView::onEvent(const HWInstructionEvent &Event) {
   // We're only interested in Issue events.
   if (Event.Type != HWInstructionEvent::Issued)
     return;
   const auto &IssueEvent = static_cast<const HWInstructionIssuedEvent &>(Event);
   const unsigned SourceIdx = Event.IR.getSourceIndex() % Source.size();
-  for (const std::pair<ResourceRef, double> &Use : IssueEvent.UsedResources) {
+  for (const std::pair<ResourceRef, ResourceCycles> &Use :
+       IssueEvent.UsedResources) {
     const ResourceRef &RR = Use.first;
     assert(Resource2VecIndex.find(RR.first) != Resource2VecIndex.end());
     unsigned R2VIndex = Resource2VecIndex[RR.first];
     R2VIndex += countTrailingZeros(RR.second);
     ResourceUsage[R2VIndex + NumResourceUnits * SourceIdx] += Use.second;
     ResourceUsage[R2VIndex + NumResourceUnits * Source.size()] += Use.second;
   }
 }

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

 /// This file defines the main interface for hardware event listeners.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_MCA_HWEVENTLISTENER_H
 #define LLVM_TOOLS_LLVM_MCA_HWEVENTLISTENER_H
 
 #include "Instruction.h"
+#include "Support.h"
 #include "llvm/ADT/ArrayRef.h"
-#include <utility>
 
 namespace mca {
 
 // An HWInstructionEvent represents state changes of instructions that
 // listeners might be interested in. Listeners can choose to ignore any event
 // they are not interested in.
 class HWInstructionEvent {
 public:
public:
 
   // The instruction this event was generated for.
   const InstRef &IR;
 };
 
 class HWInstructionIssuedEvent : public HWInstructionEvent {
 public:
   using ResourceRef = std::pair<uint64_t, uint64_t>;
-  HWInstructionIssuedEvent(const InstRef &IR,
-                           llvm::ArrayRef<std::pair<ResourceRef, double>> UR)
+  HWInstructionIssuedEvent(
+      const InstRef &IR,
+      llvm::ArrayRef<std::pair<ResourceRef, ResourceCycles>> UR)
       : HWInstructionEvent(HWInstructionEvent::Issued, IR), UsedResources(UR) {}
 
-  llvm::ArrayRef<std::pair<ResourceRef, double>> UsedResources;
+  llvm::ArrayRef<std::pair<ResourceRef, ResourceCycles>> UsedResources;
 };
 
 class HWInstructionDispatchedEvent : public HWInstructionEvent {
 public:
   HWInstructionDispatchedEvent(const InstRef &IR, llvm::ArrayRef<unsigned> Regs,
                                unsigned UOps)
       : HWInstructionEvent(HWInstructionEvent::Dispatched, IR),
         UsedPhysRegs(Regs), MicroOpcodes(UOps) {}

llvm/trunk/tools/llvm-mca/include/HardwareUnits/ResourceManager.h

 /// strategy.  These classes are managed by the Scheduler.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_MCA_RESOURCE_MANAGER_H
 #define LLVM_TOOLS_LLVM_MCA_RESOURCE_MANAGER_H
 
 #include "Instruction.h"
+#include "Support.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/MC/MCSchedule.h"
 
 namespace mca {
 
 /// Used to notify the internal state of a processor resource.
public:
   // Returns true if all resources are in-order, and there is at least one
   // resource which is a dispatch hazard (BufferSize = 0).
   bool mustIssueImmediately(const InstrDesc &Desc) const;
 
   bool canBeIssued(const InstrDesc &Desc) const;
 
   void issueInstruction(
       const InstrDesc &Desc,
-      llvm::SmallVectorImpl<std::pair<ResourceRef, double>> &Pipes);
+      llvm::SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes);
 
   void cycleEvent(llvm::SmallVectorImpl<ResourceRef> &ResourcesFreed);
 
 #ifndef NDEBUG
   void dump() const {
     for (const std::unique_ptr<ResourceState> &Resource : Resources)
       Resource->dump();
   }
 #endif
 };
 } // namespace mca
 
 #endif // LLVM_TOOLS_LLVM_MCA_RESOURCE_MANAGER_H

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

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_MCA_SCHEDULER_H
 #define LLVM_TOOLS_LLVM_MCA_SCHEDULER_H
 
 #include "HardwareUnits/HardwareUnit.h"
 #include "HardwareUnits/LSUnit.h"
 #include "ResourceManager.h"
+#include "Support.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/MC/MCSchedule.h"
 
 namespace mca {
 
 class SchedulerStrategy {
 public:
   SchedulerStrategy() = default;
class Scheduler : public HardwareUnit {
   /// Verify the given selection strategy and set the Strategy member
   /// accordingly.  If no strategy is provided, the DefaultSchedulerStrategy is
   /// used.
   void initializeStrategy(std::unique_ptr<SchedulerStrategy> S);
 
   /// Issue an instruction without updating the ready queue.
   void issueInstructionImpl(
       InstRef &IR,
-      llvm::SmallVectorImpl<std::pair<ResourceRef, double>> &Pipes);
+      llvm::SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes);
 
   // Identify instructions that have finished executing, and remove them from
   // the IssuedSet. References to executed instructions are added to input
   // vector 'Executed'.
   void updateIssuedSet(llvm::SmallVectorImpl<InstRef> &Executed);
 
   // Try to promote instructions from WaitSet to ReadySet.
   // Add promoted instructions to the 'Ready' vector in input.
public:
 
   /// Returns true if IR is ready to be executed by the underlying pipelines.
   /// This method assumes that IR has been previously dispatched.
   bool isReady(const InstRef &IR) const;
 
   /// Issue an instruction and populates a vector of used pipeline resources,
   /// and a vector of instructions that transitioned to the ready state as a
   /// result of this event.
-  void
-  issueInstruction(InstRef &IR,
-                   llvm::SmallVectorImpl<std::pair<ResourceRef, double>> &Used,
-                   llvm::SmallVectorImpl<InstRef> &Ready);
+  void issueInstruction(
+      InstRef &IR,
+      llvm::SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Used,
 
   /// Returns true if IR has to be issued immediately, or if IR is a zero
   /// latency instruction.
   bool mustIssueImmediately(const InstRef &IR) const;
 
   /// This routine notifies the Scheduler that a new cycle just started.
   ///
   /// It notifies the underlying ResourceManager that a new cycle just started.

llvm/trunk/tools/llvm-mca/include/Stages/ExecuteStage.h

public:
   // This method notifies the scheduler that a new cycle started.
   // This method is also responsible for notifying listeners about instructions
   // state changes, and processor resources freed by the scheduler.
   // Instructions that transitioned to the 'Executed' state are automatically
   // moved to the next stage (i.e. RetireStage).
   llvm::Error cycleStart() override;
   llvm::Error execute(InstRef &IR) override;
 
-  void
-  notifyInstructionIssued(const InstRef &IR,
-                          llvm::ArrayRef<std::pair<ResourceRef, double>> Used);
+  void notifyInstructionIssued(
+      const InstRef &IR,
+      llvm::ArrayRef<std::pair<ResourceRef, ResourceCycles>> Used);
   void notifyInstructionExecuted(const InstRef &IR);
   void notifyInstructionReady(const InstRef &IR);
   void notifyResourceAvailable(const ResourceRef &RR);
 
   // Notify listeners that buffered resources have been consumed or freed.
   void notifyReservedOrReleasedBuffers(const InstRef &IR, bool Reserved);
 };
 
 } // namespace mca
 
 #endif // LLVM_TOOLS_LLVM_MCA_EXECUTE_STAGE_H

llvm/trunk/tools/llvm-mca/include/Stages/InstructionTables.h

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/MC/MCSchedule.h"
 
 namespace mca {
 
 class InstructionTables final : public Stage {
   const llvm::MCSchedModel &SM;
   InstrBuilder &IB;
-  llvm::SmallVector<std::pair<ResourceRef, double>, 4> UsedResources;
+  llvm::SmallVector<std::pair<ResourceRef, ResourceCycles>, 4> UsedResources;
 
 public:
   InstructionTables(const llvm::MCSchedModel &Model, InstrBuilder &Builder)
       : Stage(), SM(Model), IB(Builder) {}
 
   bool hasWorkToComplete() const override { return false; }
   llvm::Error execute(InstRef &IR) override;
 };
 } // namespace mca
 
 #endif

llvm/trunk/tools/llvm-mca/include/Support.h

 #define LLVM_TOOLS_LLVM_MCA_SUPPORT_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/MC/MCSchedule.h"
 
 namespace mca {
 
+/// This class represents the number of cycles per resource (fractions of
+/// cycles).  That quantity is managed here as a ratio, and accessed via the
+/// double cast-operator below.  The two quantities, number of cycles and
+/// number of resources, are kept separate.  This is used by the
+/// ResourcePressureView to calculate the average resource cycles
+/// per instruction/iteration.
+class ResourceCycles {
+  unsigned Numerator, Denominator;
+
+public:
+  ResourceCycles() : Numerator(0), Denominator(1) {}
+  ResourceCycles(unsigned Cycles, unsigned ResourceUnits = 1)
+      : Numerator(Cycles), Denominator(ResourceUnits) {}
+
+  operator double() const {
+    assert(Denominator && "Invalid denominator (must be non-zero).");
+    return (Denominator == 1) ? Numerator : (double)Numerator / Denominator;
+  }
+
+  // Add the components of RHS to this instance.  Instead of calculating
+  // the final value here, we keep track of the numerator and denominator
+  // separately, to reduce floating point error.
+  ResourceCycles &operator+=(const ResourceCycles &RHS) {
+    if (Denominator == RHS.Denominator)
+      Numerator += RHS.Numerator;
+    else {
+      // Create a common denominator for LHS and RHS by calculating the least
+      // common multiple from the GCD.
+      unsigned GCD =
+          llvm::GreatestCommonDivisor64(Denominator, RHS.Denominator);
+      unsigned LCM = (Denominator * RHS.Denominator) / GCD;
+      unsigned LHSNumerator = Numerator * (LCM / Denominator);
+      unsigned RHSNumerator = RHS.Numerator * (LCM / RHS.Denominator);
+      Numerator = LHSNumerator + RHSNumerator;
+      Denominator = LCM;
+    }
+    return *this;
+  }
+};
+
 /// Populates vector Masks with processor resource masks.
 ///
 /// The number of bits set in a mask depends on the processor resource type.
 /// Each processor resource mask has at least one bit set. For groups, the
 /// number of bits set in the mask is equal to the cardinality of the group plus
 /// one. Excluding the most significant bit, the remaining bits in the mask
 /// identify processor resources that are part of the group.
 ///

llvm/trunk/tools/llvm-mca/lib/HardwareUnits/ResourceManager.cpp

bool ResourceManager::mustIssueImmediately(const InstrDesc &Desc) const {
 
   return any_of(Desc.Buffers, [&](uint64_t BufferMask) {
     return Resources[getResourceStateIndex(BufferMask)]->isADispatchHazard();
   });
 }
 
 void ResourceManager::issueInstruction(
     const InstrDesc &Desc,
-    SmallVectorImpl<std::pair<ResourceRef, double>> &Pipes) {
+    SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes) {
   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 (!R.second.isReserved()) {
       ResourceRef Pipe = selectPipe(R.first);
       use(Pipe);
       BusyResources[Pipe] += CS.size();
       // Replace the resource mask with a valid processor resource index.
       const ResourceState &RS = *Resources[getResourceStateIndex(Pipe.first)];
       Pipe.first = RS.getProcResourceID();
-      Pipes.emplace_back(
-          std::pair<ResourceRef, double>(Pipe, static_cast<double>(CS.size())));
+      Pipes.emplace_back(std::pair<ResourceRef, ResourceCycles>(
+          Pipe, ResourceCycles(CS.size())));
     } else {
       assert((countPopulation(R.first) > 1) && "Expected a group!");
       // Mark this group as reserved.
       assert(R.second.isReserved());
       reserveResource(R.first);
       BusyResources[ResourceRef(R.first, R.first)] += CS.size();
     }
   }

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

case LSUnit::LSU_AVAILABLE:
     return Scheduler::SC_AVAILABLE;
   }
 
   llvm_unreachable("Don't know how to process this LSU state result!");
 }
 
 void Scheduler::issueInstructionImpl(
     InstRef &IR,
-    SmallVectorImpl<std::pair<ResourceRef, double>> &UsedResources) {
+    SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources) {
   Instruction *IS = IR.getInstruction();
   const InstrDesc &D = IS->getDesc();
 
   // Issue the instruction and collect all the consumed resources
   // into a vector. That vector is then used to notify the listener.
   Resources->issueInstruction(D, UsedResources);
 
   // Notify the instruction that it started executing.
   // This updates the internal state of each write.
   IS->execute();
 
   if (IS->isExecuting())
     IssuedSet.emplace_back(IR);
   else if (IS->isExecuted())
     LSU->onInstructionExecuted(IR);
 }
 
 // Release the buffered resources and issue the instruction.
 void Scheduler::issueInstruction(
-    InstRef &IR, SmallVectorImpl<std::pair<ResourceRef, double>> &UsedResources,
+    InstRef &IR,
+    SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &UsedResources,
     SmallVectorImpl<InstRef> &ReadyInstructions) {
   const Instruction &Inst = *IR.getInstruction();
   bool HasDependentUsers = Inst.hasDependentUsers();
 
   Resources->releaseBuffers(Inst.getDesc().Buffers);
   issueInstructionImpl(IR, UsedResources);
   // Instructions that have been issued during this cycle might have unblocked
   // other dependent instructions. Dependent instructions may be issued during

llvm/trunk/tools/llvm-mca/lib/Stages/ExecuteStage.cpp

if (Scheduler::Status S = HWS.isAvailable(IR)) {
     notifyEvent<HWStallEvent>(HWStallEvent(ET, IR));
     return false;
   }
 
   return true;
 }
 
 Error ExecuteStage::issueInstruction(InstRef &IR) {
-  SmallVector<std::pair<ResourceRef, double>, 4> Used;
+  SmallVector<std::pair<ResourceRef, ResourceCycles>, 4> Used;
   SmallVector<InstRef, 4> Ready;
   HWS.issueInstruction(IR, Used, Ready);
 
-  notifyReservedOrReleasedBuffers(IR, /* Reserved */false);
+  notifyReservedOrReleasedBuffers(IR, /* Reserved */ false);
   notifyInstructionIssued(IR, Used);
   if (IR.getInstruction()->isExecuted()) {
     notifyInstructionExecuted(IR);
     // FIXME: add a buffer of executed instructions.
     if (Error S = moveToTheNextStage(IR))
       return S;
   }
 
#ifndef NDEBUG
   // Ensure that the HWS has not stored this instruction in its queues.
   HWS.sanityCheck(IR);
 #endif
   // 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.
   HWS.dispatch(IR);
-  notifyReservedOrReleasedBuffers(IR, /* Reserved */true);
+  notifyReservedOrReleasedBuffers(IR, /* Reserved */ true);
   if (!HWS.isReady(IR))
     return ErrorSuccess();
 
   // If we did not return early, then the scheduler is ready for execution.
   notifyInstructionReady(IR);
 
   // If we cannot issue immediately, the HWS will add IR to its ready queue for
   // execution later, so we must return early here.

 void ExecuteStage::notifyResourceAvailable(const ResourceRef &RR) {
   LLVM_DEBUG(dbgs() << "[E] Resource Available: [" << RR.first << '.'
                     << RR.second << "]\n");
   for (HWEventListener *Listener : getListeners())
     Listener->onResourceAvailable(RR);
 }
 
 void ExecuteStage::notifyInstructionIssued(
-    const InstRef &IR, ArrayRef<std::pair<ResourceRef, double>> Used) {
+    const InstRef &IR, ArrayRef<std::pair<ResourceRef, ResourceCycles>> Used) {
   LLVM_DEBUG({
     dbgs() << "[E] Instruction Issued: #" << IR << '\n';
-    for (const std::pair<ResourceRef, unsigned> &Resource : Used) {
+    for (const std::pair<ResourceRef, ResourceCycles> &Resource : Used) {
       dbgs() << "[E] Resource Used: [" << Resource.first.first << '.'
              << Resource.first.second << "], ";
       dbgs() << "cycles: " << Resource.second << '\n';
     }
   });
   notifyEvent<HWInstructionEvent>(HWInstructionIssuedEvent(IR, Used));
 }
 

llvm/trunk/tools/llvm-mca/lib/Stages/InstructionTables.cpp

Error InstructionTables::execute(InstRef &IR) {
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
   UsedResources.clear();
 
   // Identify the resources consumed by this instruction.
   for (const std::pair<uint64_t, ResourceUsage> Resource : Desc.Resources) {
     // Skip zero-cycle resources (i.e., unused resources).
     if (!Resource.second.size())
       continue;
-    double Cycles = static_cast<double>(Resource.second.size());
+    unsigned Cycles = Resource.second.size();
     unsigned Index = std::distance(
         Masks.begin(), std::find(Masks.begin(), Masks.end(), Resource.first));
     const MCProcResourceDesc &ProcResource = *SM.getProcResource(Index);
     unsigned NumUnits = ProcResource.NumUnits;
     if (!ProcResource.SubUnitsIdxBegin) {
       // The number of cycles consumed by each unit.
-      Cycles /= NumUnits;
       for (unsigned I = 0, E = NumUnits; I < E; ++I) {
         ResourceRef ResourceUnit = std::make_pair(Index, 1U << I);
-        UsedResources.emplace_back(std::make_pair(ResourceUnit, Cycles));
+        UsedResources.emplace_back(
+            std::make_pair(ResourceUnit, ResourceCycles(Cycles, NumUnits)));
       }
       continue;
     }
 
     // This is a group. Obtain the set of resources contained in this
     // group. Some of these resources may implement multiple units.
     // Uniformly distribute Cycles across all of the units.
     for (unsigned I1 = 0; I1 < NumUnits; ++I1) {
       unsigned SubUnitIdx = ProcResource.SubUnitsIdxBegin[I1];
       const MCProcResourceDesc &SubUnit = *SM.getProcResource(SubUnitIdx);
       // Compute the number of cycles consumed by each resource unit.
-      double RUCycles = Cycles / (NumUnits * SubUnit.NumUnits);
       for (unsigned I2 = 0, E2 = SubUnit.NumUnits; I2 < E2; ++I2) {
         ResourceRef ResourceUnit = std::make_pair(SubUnitIdx, 1U << I2);
-        UsedResources.emplace_back(std::make_pair(ResourceUnit, RUCycles));
+        UsedResources.emplace_back(std::make_pair(
+            ResourceUnit, ResourceCycles(Cycles, NumUnits * SubUnit.NumUnits)));
       }
     }
   }
 
   // Send a fake instruction issued event to all the views.
   HWInstructionIssuedEvent Event(IR, UsedResources);
   notifyEvent<HWInstructionIssuedEvent>(Event);
   return ErrorSuccess();
 }
 
 } // namespace mca