[llvm-mca] Use a vector to store ResourceState objects in the ResourceManager.

We don't need to use a map to store ResourceState objects. The number of
processor resources is known statically from the scheduling model. We can
therefore use a vector, and reserve a slot for each processor resource that we
want to simulate.
Every time the ResourceManager queries the ResourceState vector, the index to
the vector of ResourceState objects can be easily computed from the processor
resource mask.

This drastically reduces the time complexity of method ResourceManager::use() and
method ResourceManager::release(). This patch gives an average speedup of 12%.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@338702 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 70 insertions, 81 deletions

diff --git a/tools/llvm-mca/Scheduler.cpp b/tools/llvm-mca/Scheduler.cpp
index b98fab87b3a..553cd00bb3a 100644
--- a/tools/llvm-mca/Scheduler.cpp
+++ b/tools/llvm-mca/Scheduler.cpp
@@ -42,30 +42,38 @@ void ResourceState::dump() const {
 }
 #endif
 
+unsigned getResourceStateIndex(uint64_t Mask) {
+  return std::numeric_limits<uint64_t>::digits - llvm::countLeadingZeros(Mask);
+}
+
+unsigned ResourceManager::resolveResourceMask(uint64_t Mask) const {
+  return Resources[getResourceStateIndex(Mask)]->getProcResourceID();
+}
+
+unsigned ResourceManager::getNumUnits(uint64_t ResourceID) const {
+  return Resources[getResourceStateIndex(ResourceID)]->getNumUnits();
+}
+
 void ResourceManager::initialize(const llvm::MCSchedModel &SM) {
   computeProcResourceMasks(SM, ProcResID2Mask);
-  for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I)
-    addResource(*SM.getProcResource(I), I, ProcResID2Mask[I]);
-}
+  Resources.resize(SM.getNumProcResourceKinds());
 
-// Adds a new resource state in Resources, as well as a new descriptor in
-// ResourceDescriptor. Map 'Resources' allows to quickly obtain ResourceState
-// objects from resource mask identifiers.
-void ResourceManager::addResource(const MCProcResourceDesc &Desc,
-                                  unsigned Index, uint64_t Mask) {
-  assert(Resources.find(Mask) == Resources.end() && "Resource already added!");
-  Resources[Mask] = llvm::make_unique<ResourceState>(Desc, Index, Mask);
+  for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) {
+    unsigned Mask = ProcResID2Mask[I];
+    Resources[getResourceStateIndex(Mask)] =
+        llvm::make_unique<ResourceState>(*SM.getProcResource(I), I, Mask);
+  }
 }
 
 // Returns the actual resource consumed by this Use.
 // First, is the primary resource ID.
 // Second, is the specific sub-resource ID.
 std::pair<uint64_t, uint64_t> ResourceManager::selectPipe(uint64_t ResourceID) {
-  ResourceState &RS = *Resources[ResourceID];
+  ResourceState &RS = *Resources[getResourceStateIndex(ResourceID)];
   uint64_t SubResourceID = RS.selectNextInSequence();
   if (RS.isAResourceGroup())
     return selectPipe(SubResourceID);
-  return std::pair<uint64_t, uint64_t>(ResourceID, SubResourceID);
+  return std::make_pair(ResourceID, SubResourceID);
 }
 
 void ResourceState::removeFromNextInSequence(uint64_t ID) {
@@ -82,9 +90,9 @@ void ResourceState::removeFromNextInSequence(uint64_t ID) {
   }
 }
 
-void ResourceManager::use(ResourceRef RR) {
+void ResourceManager::use(const ResourceRef &RR) {
   // Mark the sub-resource referenced by RR as used.
-  ResourceState &RS = *Resources[RR.first];
+  ResourceState &RS = *Resources[getResourceStateIndex(RR.first)];
   RS.markSubResourceAsUsed(RR.second);
   // If there are still available units in RR.first,
   // then we are done.
@@ -92,8 +100,8 @@ void ResourceManager::use(ResourceRef RR) {
     return;
 
   // Notify to other resources that RR.first is no longer available.
-  for (const std::pair<uint64_t, UniqueResourceState> &Res : Resources) {
-    ResourceState &Current = *Res.second.get();
+  for (UniqueResourceState &Res : Resources) {
+    ResourceState &Current = *Res;
     if (!Current.isAResourceGroup() || Current.getResourceMask() == RR.first)
       continue;
 
@@ -104,15 +112,15 @@ void ResourceManager::use(ResourceRef RR) {
   }
 }
 
-void ResourceManager::release(ResourceRef RR) {
-  ResourceState &RS = *Resources[RR.first];
+void ResourceManager::release(const ResourceRef &RR) {
+  ResourceState &RS = *Resources[getResourceStateIndex(RR.first)];
   bool WasFullyUsed = !RS.isReady();
   RS.releaseSubResource(RR.second);
   if (!WasFullyUsed)
     return;
 
-  for (const std::pair<uint64_t, UniqueResourceState> &Res : Resources) {
-    ResourceState &Current = *Res.second.get();
+  for (UniqueResourceState &Res : Resources) {
+    ResourceState &Current = *Res;
     if (!Current.isAResourceGroup() || Current.getResourceMask() == RR.first)
       continue;
 
@@ -125,7 +133,8 @@ ResourceStateEvent
 ResourceManager::canBeDispatched(ArrayRef<uint64_t> Buffers) const {
   ResourceStateEvent Result = ResourceStateEvent::RS_BUFFER_AVAILABLE;
   for (uint64_t Buffer : Buffers) {
-    Result = isBufferAvailable(Buffer);
+    ResourceState &RS = *Resources[getResourceStateIndex(Buffer)];
+    Result = RS.isBufferAvailable();
     if (Result != ResourceStateEvent::RS_BUFFER_AVAILABLE)
       break;
   }
@@ -133,19 +142,21 @@ ResourceManager::canBeDispatched(ArrayRef<uint64_t> Buffers) const {
 }
 
 void ResourceManager::reserveBuffers(ArrayRef<uint64_t> Buffers) {
-  for (const uint64_t R : Buffers) {
-    reserveBuffer(R);
-    ResourceState &Resource = *Resources[R];
-    if (Resource.isADispatchHazard()) {
-      assert(!Resource.isReserved());
-      Resource.setReserved();
+  for (const uint64_t Buffer : Buffers) {
+    ResourceState &RS = *Resources[getResourceStateIndex(Buffer)];
+    assert(RS.isBufferAvailable() == ResourceStateEvent::RS_BUFFER_AVAILABLE);
+    RS.reserveBuffer();
+
+    if (RS.isADispatchHazard()) {
+      assert(!RS.isReserved());
+      RS.setReserved();
     }
   }
 }
 
 void ResourceManager::releaseBuffers(ArrayRef<uint64_t> Buffers) {
   for (const uint64_t R : Buffers)
-    releaseBuffer(R);
+    Resources[getResourceStateIndex(R)]->releaseBuffer();
 }
 
 bool ResourceManager::canBeIssued(const InstrDesc &Desc) const {
@@ -153,7 +164,8 @@ bool ResourceManager::canBeIssued(const InstrDesc &Desc) const {
                      [&](const std::pair<uint64_t, const ResourceUsage> &E) {
                        unsigned NumUnits =
                            E.second.isReserved() ? 0U : E.second.NumUnits;
-                       return isReady(E.first, NumUnits);
+                       unsigned Index = getResourceStateIndex(E.first);
+                       return Resources[Index]->isReady(NumUnits);
                      });
 }
 
@@ -163,14 +175,15 @@ bool ResourceManager::mustIssueImmediately(const InstrDesc &Desc) {
   if (!canBeIssued(Desc))
     return false;
   bool AllInOrderResources = all_of(Desc.Buffers, [&](uint64_t BufferMask) {
-    const ResourceState &Resource = *Resources[BufferMask];
+    unsigned Index = getResourceStateIndex(BufferMask);
+    const ResourceState &Resource = *Resources[Index];
     return Resource.isInOrder() || Resource.isADispatchHazard();
   });
   if (!AllInOrderResources)
     return false;
 
   return any_of(Desc.Buffers, [&](uint64_t BufferMask) {
-    return Resources[BufferMask]->isADispatchHazard();
+    return Resources[getResourceStateIndex(BufferMask)]->isADispatchHazard();
   });
 }
 
@@ -190,7 +203,7 @@ void ResourceManager::issueInstruction(
       use(Pipe);
       BusyResources[Pipe] += CS.size();
       // Replace the resource mask with a valid processor resource index.
-      const ResourceState &RS = *Resources[Pipe.first];
+      const ResourceState &RS = *Resources[getResourceStateIndex(Pipe.first)];
       Pipe.first = RS.getProcResourceID();
       Pipes.emplace_back(
           std::pair<ResourceRef, double>(Pipe, static_cast<double>(CS.size())));
@@ -224,6 +237,17 @@ void ResourceManager::cycleEvent(SmallVectorImpl<ResourceRef> &ResourcesFreed) {
     BusyResources.erase(RF);
 }
 
+void ResourceManager::reserveResource(uint64_t ResourceID) {
+  ResourceState &Resource = *Resources[getResourceStateIndex(ResourceID)];
+  assert(!Resource.isReserved());
+  Resource.setReserved();
+}
+
+void ResourceManager::releaseResource(uint64_t ResourceID) {
+  ResourceState &Resource = *Resources[getResourceStateIndex(ResourceID)];
+  Resource.clearReserved();
+}
+
 #ifndef NDEBUG
 void Scheduler::dump() const {
   dbgs() << "[SCHEDULER]: WaitQueue size is: " << WaitQueue.size() << '\n';
@@ -384,7 +408,8 @@ bool Scheduler::reserveResources(InstRef &IR) {
   // If necessary, reserve queue entries in the load-store unit (LSU).
   const bool Reserved = LSU->reserve(IR);
   if (!IR.getInstruction()->isReady() || (Reserved && !LSU->isReady(IR))) {
-    LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the Wait Queue\n");
+    LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR
+                      << " to the Wait Queue\n");
     WaitQueue[IR.getSourceIndex()] = IR.getInstruction();
     return false;
   }
diff --git a/tools/llvm-mca/Scheduler.h b/tools/llvm-mca/Scheduler.h
index 428fbc01707..b0d2dbc53c6 100644
--- a/tools/llvm-mca/Scheduler.h
+++ b/tools/llvm-mca/Scheduler.h
@@ -274,7 +274,7 @@ typedef std::pair<unsigned, unsigned> BufferUsageEntry;
 class ResourceManager {
   // The resource manager owns all the ResourceState.
   using UniqueResourceState = std::unique_ptr<ResourceState>;
-  llvm::SmallDenseMap<uint64_t, UniqueResourceState> Resources;
+  std::vector<UniqueResourceState> Resources;
 
   // Keeps track of which resources are busy, and how many cycles are left
   // before those become usable again.
@@ -283,46 +283,16 @@ class ResourceManager {
   // A table to map processor resource IDs to processor resource masks.
   llvm::SmallVector<uint64_t, 8> ProcResID2Mask;
 
-  // Adds a new resource state in Resources, as well as a new descriptor in
-  // ResourceDescriptor.
-  void addResource(const llvm::MCProcResourceDesc &Desc, unsigned Index,
-                   uint64_t Mask);
-
   // Populate resource descriptors.
   void initialize(const llvm::MCSchedModel &SM);
 
   // Returns the actual resource unit that will be used.
   ResourceRef selectPipe(uint64_t ResourceID);
 
-  void use(ResourceRef RR);
-  void release(ResourceRef RR);
-
-  unsigned getNumUnits(uint64_t ResourceID) const {
-    assert(Resources.find(ResourceID) != Resources.end());
-    return Resources.find(ResourceID)->getSecond()->getNumUnits();
-  }
+  void use(const ResourceRef &RR);
+  void release(const ResourceRef &RR);
 
-  // Reserve a specific Resource kind.
-  void reserveBuffer(uint64_t ResourceID) {
-    assert(isBufferAvailable(ResourceID) ==
-           ResourceStateEvent::RS_BUFFER_AVAILABLE);
-    ResourceState &Resource = *Resources[ResourceID];
-    Resource.reserveBuffer();
-  }
-
-  void releaseBuffer(uint64_t ResourceID) {
-    Resources[ResourceID]->releaseBuffer();
-  }
-
-  ResourceStateEvent isBufferAvailable(uint64_t ResourceID) const {
-    const ResourceState &Resource = *Resources.find(ResourceID)->second;
-    return Resource.isBufferAvailable();
-  }
-
-  bool isReady(uint64_t ResourceID, unsigned NumUnits) const {
-    const ResourceState &Resource = *Resources.find(ResourceID)->second;
-    return Resource.isReady(NumUnits);
-  }
+  unsigned getNumUnits(uint64_t ResourceID) const;
 
 public:
   ResourceManager(const llvm::MCSchedModel &SM)
@@ -335,9 +305,7 @@ public:
   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();
-  }
+  unsigned resolveResourceMask(uint64_t Mask) const;
 
   // Consume a slot in every buffered resource from array 'Buffers'. Resource
   // units that are dispatch hazards (i.e. BufferSize=0) are marked as reserved.
@@ -346,16 +314,12 @@ public:
   // Release buffer entries previously allocated by method reserveBuffers.
   void releaseBuffers(llvm::ArrayRef<uint64_t> Buffers);
 
-  void reserveResource(uint64_t ResourceID) {
-    ResourceState &Resource = *Resources[ResourceID];
-    assert(!Resource.isReserved());
-    Resource.setReserved();
-  }
+  // Reserve a processor resource. A reserved resource is not available for
+  // instruction issue until it is released. 
+  void reserveResource(uint64_t ResourceID);
 
-  void releaseResource(uint64_t ResourceID) {
-    ResourceState &Resource = *Resources[ResourceID];
-    Resource.clearReserved();
-  }
+  // Release a previously reserved processor resource.
+  void releaseResource(uint64_t ResourceID);
 
   // Returns true if all resources are in-order, and there is at least one
   // resource which is a dispatch hazard (BufferSize = 0).
@@ -371,8 +335,8 @@ public:
 
 #ifndef NDEBUG
   void dump() const {
-    for (const std::pair<uint64_t, UniqueResourceState> &Resource : Resources)
-      Resource.second->dump();
+    for (const UniqueResourceState &Resource : Resources)
+      Resource->dump();
   }
 #endif
 }; // namespace mca