[llvm-mca] Introduce a sequential container of Stages

Summary:
Remove explicit stages and introduce a list of stages.

A pipeline should be composed of an arbitrary list of stages, and not any
 predefined list of stages in the Backend.  The Backend should not know of any
 particular stage, rather it should only be concerned that it has a list of
 stages, and that those stages will fulfill the contract of what it means to be
 a Stage (namely pre/post/execute a given instruction).

For now, we leave the original set of stages defined in the Backend ctor;
however, I imagine these will be moved out at a later time.

This patch makes an adjustment to the semantics of Stage::isReady.
Specifically, what the Backend really needs to know is if a Stage has
unfinished work.  With that said, it is more appropriately renamed
Stage::hasWorkToComplete().  This change will clean up the check in
Backend::run(), allowing us to query each stage to see if there is unfinished
work, regardless of what subclass a stage might be.  I feel that this change
simplifies the semantics too, but that's a subjective statement.

Given how RetireStage and ExecuteStage handle data in their preExecute(), I've
had to change the order of Retire and Execute in our stage list.  Retire must
complete any of its preExecute actions before ExecuteStage's preExecute can
take control.  This is mainly because both stages utilize the RCU.  In the
meantime, I want to see if I can adjust that or remove that coupling.

Reviewers: andreadb, RKSimon, courbet

Reviewed By: andreadb

Subscribers: tschuett, gbedwell, llvm-commits

Differential Revision: https://reviews.llvm.org/D46907

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

10 files changed, 86 insertions, 74 deletions

diff --git a/tools/llvm-mca/Backend.cpp b/tools/llvm-mca/Backend.cpp
index 3e7a3650e9d..c3e8d2f44c3 100644
--- a/tools/llvm-mca/Backend.cpp
+++ b/tools/llvm-mca/Backend.cpp
@@ -13,7 +13,6 @@
 //===----------------------------------------------------------------------===//
 
 #include "Backend.h"
-#include "FetchStage.h"
 #include "HWEventListener.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/Support/Debug.h"
@@ -29,8 +28,29 @@ void Backend::addEventListener(HWEventListener *Listener) {
     Listeners.insert(Listener);
 }
 
+bool Backend::hasWorkToProcess() {
+  const auto It = llvm::find_if(Stages, [](const std::unique_ptr<Stage> &S) {
+    return S->hasWorkToComplete();
+  });
+  return It != Stages.end();
+}
+
+// This routine returns early if any stage returns 'false' after execute() is
+// called on it.
+bool Backend::executeStages(InstRef &IR) {
+  for (const std::unique_ptr<Stage> &S : Stages)
+    if (!S->execute(IR))
+      return false;
+  return true;
+}
+
+void Backend::postExecuteStages(const InstRef &IR) {
+  for (const std::unique_ptr<Stage> &S : Stages)
+    S->postExecute(IR);
+}
+
 void Backend::run() {
-  while (Fetch->isReady() || !Dispatch->isReady())
+  while (hasWorkToProcess())
     runCycle(Cycles++);
 }
 
@@ -39,17 +59,13 @@ void Backend::runCycle(unsigned Cycle) {
 
   // Update the stages before we do any processing for this cycle.
   InstRef IR;
-  Retire->preExecute(IR);
-  Dispatch->preExecute(IR);
-  Execute->preExecute(IR);
-
-  // Fetch instructions and dispatch them to the hardware.
-  while (Fetch->execute(IR)) {
-    if (!Dispatch->execute(IR))
-      break;
-    Execute->execute(IR);
-    Fetch->postExecute(IR);
-  }
+  for (auto &S : Stages)
+    S->preExecute(IR);
+
+  // Continue executing this cycle until any stage claims it cannot make
+  // progress.
+  while (executeStages(IR))
+    postExecuteStages(IR);
 
   notifyCycleEnd(Cycle);
 }
diff --git a/tools/llvm-mca/Backend.h b/tools/llvm-mca/Backend.h
index 79e5bba7f8d..87969ae61c5 100644
--- a/tools/llvm-mca/Backend.h
+++ b/tools/llvm-mca/Backend.h
@@ -15,14 +15,9 @@
 #ifndef LLVM_TOOLS_LLVM_MCA_BACKEND_H
 #define LLVM_TOOLS_LLVM_MCA_BACKEND_H
 
-#include "DispatchStage.h"
-#include "ExecuteStage.h"
-#include "FetchStage.h"
-#include "InstrBuilder.h"
-#include "RegisterFile.h"
-#include "RetireControlUnit.h"
-#include "RetireStage.h"
 #include "Scheduler.h"
+#include "Stage.h"
+#include "llvm/ADT/SmallVector.h"
 
 namespace mca {
 
@@ -55,40 +50,22 @@ class HWStallEvent;
 /// histograms. For example, it tracks how the dispatch group size changes
 /// over time.
 class Backend {
-  // The following are the simulated hardware components of the backend.
-  RetireControlUnit RCU;
-  RegisterFile PRF;
-  Scheduler HWS;
-
-  /// TODO: Eventually this will become a list of unique Stage* that this
-  /// backend pipeline executes.
-  std::unique_ptr<FetchStage> Fetch;
-  std::unique_ptr<DispatchStage> Dispatch;
-  std::unique_ptr<ExecuteStage> Execute;
-  std::unique_ptr<RetireStage> Retire;
-
+  /// An ordered list of stages that define this backend's instruction pipeline.
+  llvm::SmallVector<std::unique_ptr<Stage>, 8> Stages;
   std::set<HWEventListener *> Listeners;
   unsigned Cycles;
 
+  bool executeStages(InstRef &IR);
+  void postExecuteStages(const InstRef &IR);
+  bool hasWorkToProcess();
   void runCycle(unsigned Cycle);
 
 public:
-  Backend(const llvm::MCSubtargetInfo &Subtarget,
-          const llvm::MCRegisterInfo &MRI,
-          std::unique_ptr<FetchStage> InitialStage, unsigned DispatchWidth = 0,
-          unsigned RegisterFileSize = 0, unsigned LoadQueueSize = 0,
-          unsigned StoreQueueSize = 0, bool AssumeNoAlias = false)
-      : RCU(Subtarget.getSchedModel()),
-        PRF(Subtarget.getSchedModel(), MRI, RegisterFileSize),
-        HWS(Subtarget.getSchedModel(), LoadQueueSize, StoreQueueSize,
-            AssumeNoAlias),
-        Fetch(std::move(InitialStage)),
-        Dispatch(llvm::make_unique<DispatchStage>(
-            this, Subtarget, MRI, RegisterFileSize, DispatchWidth, RCU, PRF,
-            HWS)),
-        Execute(llvm::make_unique<ExecuteStage>(this, RCU, HWS)),
-        Retire(llvm::make_unique<RetireStage>(this, RCU, PRF)), Cycles(0) {}
-
+  Backend(unsigned DispatchWidth = 0, unsigned RegisterFileSize = 0,
+          unsigned LoadQueueSize = 0, unsigned StoreQueueSize = 0,
+          bool AssumeNoAlias = false)
+      : Cycles(0) {}
+  void appendStage(std::unique_ptr<Stage> S) { Stages.push_back(std::move(S)); }
   void run();
   void addEventListener(HWEventListener *Listener);
   void notifyCycleBegin(unsigned Cycle);
diff --git a/tools/llvm-mca/DispatchStage.h b/tools/llvm-mca/DispatchStage.h
index 9317f88192e..60b33324ba0 100644
--- a/tools/llvm-mca/DispatchStage.h
+++ b/tools/llvm-mca/DispatchStage.h
@@ -64,7 +64,6 @@ class DispatchStage : public Stage {
   bool checkPRF(const InstRef &IR);
   bool checkScheduler(const InstRef &IR);
   void dispatch(InstRef IR);
-  bool isRCUEmpty() const { return RCU.isEmpty(); }
   void updateRAWDependencies(ReadState &RS, const llvm::MCSubtargetInfo &STI);
 
   void notifyInstructionDispatched(const InstRef &IR,
@@ -92,7 +91,10 @@ public:
       : DispatchWidth(MaxDispatchWidth), AvailableEntries(MaxDispatchWidth),
         CarryOver(0U), Owner(B), STI(Subtarget), RCU(R), PRF(F), SC(Sched) {}
 
-  virtual bool isReady() const override final { return isRCUEmpty(); }
+  // We can always try to dispatch, so returning false is okay in this case.
+  // The retire stage, which controls the RCU, might have items to complete but
+  // RetireStage::hasWorkToComplete will check for that case.
+  virtual bool hasWorkToComplete() const override final { return false; }
   virtual void preExecute(const InstRef &IR) override final;
   virtual bool execute(InstRef &IR) override final;
   void notifyDispatchStall(const InstRef &IR, unsigned EventType);
diff --git a/tools/llvm-mca/ExecuteStage.cpp b/tools/llvm-mca/ExecuteStage.cpp
index 1c222f0f1eb..6a0fefdadcc 100644
--- a/tools/llvm-mca/ExecuteStage.cpp
+++ b/tools/llvm-mca/ExecuteStage.cpp
@@ -110,9 +110,10 @@ bool ExecuteStage::execute(InstRef &IR) {
   HWS.reserveBuffers(Desc.Buffers);
   notifyReservedBuffers(Desc.Buffers);
 
-  // Obtain a slot in the LSU.
+  // Obtain a slot in the LSU.  If we cannot reserve resources, return true, so
+  // that succeeding stages can make progress.
   if (!HWS.reserveResources(IR))
-    return false;
+    return true;
 
   // If we did not return early, then the scheduler is ready for execution.
   notifyInstructionReady(IR);
diff --git a/tools/llvm-mca/ExecuteStage.h b/tools/llvm-mca/ExecuteStage.h
index c7399182316..a71aa45b3fd 100644
--- a/tools/llvm-mca/ExecuteStage.h
+++ b/tools/llvm-mca/ExecuteStage.h
@@ -45,6 +45,10 @@ public:
   ExecuteStage(const ExecuteStage &Other) = delete;
   ExecuteStage &operator=(const ExecuteStage &Other) = delete;
 
+  // The ExecuteStage will always complete all of its work per call to
+  // execute(), so it is never left in a 'to-be-processed' state.
+  virtual bool hasWorkToComplete() const override final { return false; }
+
   virtual void preExecute(const InstRef &IR) override final;
   virtual bool execute(InstRef &IR) override final;
 
diff --git a/tools/llvm-mca/FetchStage.cpp b/tools/llvm-mca/FetchStage.cpp
index d73585869e1..4ea1c6b0fe3 100644
--- a/tools/llvm-mca/FetchStage.cpp
+++ b/tools/llvm-mca/FetchStage.cpp
@@ -17,7 +17,7 @@
 
 namespace mca {
 
-bool FetchStage::isReady() const { return SM.hasNext(); }
+bool FetchStage::hasWorkToComplete() const { return SM.hasNext(); }
 
 bool FetchStage::execute(InstRef &IR) {
   if (!SM.hasNext())
diff --git a/tools/llvm-mca/FetchStage.h b/tools/llvm-mca/FetchStage.h
index b288d7aae99..4c70b7f2bc6 100644
--- a/tools/llvm-mca/FetchStage.h
+++ b/tools/llvm-mca/FetchStage.h
@@ -34,7 +34,7 @@ public:
   FetchStage(const FetchStage &Other) = delete;
   FetchStage &operator=(const FetchStage &Other) = delete;
 
-  bool isReady() const override final;
+  bool hasWorkToComplete() const override final;
   bool execute(InstRef &IR) override final;
   void postExecute(const InstRef &IR) override final;
 };
diff --git a/tools/llvm-mca/RetireStage.h b/tools/llvm-mca/RetireStage.h
index a40e4033b1f..3041f26fd6e 100644
--- a/tools/llvm-mca/RetireStage.h
+++ b/tools/llvm-mca/RetireStage.h
@@ -37,6 +37,7 @@ public:
   RetireStage(const RetireStage &Other) = delete;
   RetireStage &operator=(const RetireStage &Other) = delete;
 
+  virtual bool hasWorkToComplete() const override final { return !RCU.isEmpty(); }
   virtual void preExecute(const InstRef &IR) override final;
   virtual bool execute(InstRef &IR) override final { return true; }
   void notifyInstructionRetired(const InstRef &IR);
diff --git a/tools/llvm-mca/Stage.h b/tools/llvm-mca/Stage.h
index ffaf371921a..426c0227cb7 100644
--- a/tools/llvm-mca/Stage.h
+++ b/tools/llvm-mca/Stage.h
@@ -32,10 +32,11 @@ public:
   Stage();
   virtual ~Stage() = default;
 
-  /// Called prior to preExecute to ensure that the stage can operate.
-  /// TODO: Remove this logic once backend::run and backend::runCycle become
-  /// one routine.
-  virtual bool isReady() const { return true; }
+  /// Called prior to preExecute to ensure that the stage has items that it
+  /// is to process.  For example, a FetchStage might have more instructions
+  /// that need to be processed, or a RCU might have items that have yet to
+  /// retire.
+  virtual bool hasWorkToComplete() const = 0;
 
   /// Called as a setup phase to prepare for the main stage execution.
   virtual void preExecute(const InstRef &IR) {}
diff --git a/tools/llvm-mca/llvm-mca.cpp b/tools/llvm-mca/llvm-mca.cpp
index 372be3e0d6d..fb019f12580 100644
--- a/tools/llvm-mca/llvm-mca.cpp
+++ b/tools/llvm-mca/llvm-mca.cpp
@@ -23,13 +23,19 @@
 
 #include "BackendPrinter.h"
 #include "CodeRegion.h"
+#include "DispatchStage.h"
 #include "DispatchStatistics.h"
+#include "ExecuteStage.h"
 #include "FetchStage.h"
 #include "InstructionInfoView.h"
 #include "InstructionTables.h"
+#include "RegisterFile.h"
 #include "RegisterFileStatistics.h"
 #include "ResourcePressureView.h"
+#include "RetireControlUnit.h"
 #include "RetireControlUnitStatistics.h"
+#include "RetireStage.h"
+#include "Scheduler.h"
 #include "SchedulerStatistics.h"
 #include "SummaryView.h"
 #include "TimelineView.h"
@@ -65,15 +71,13 @@ static cl::opt<std::string> OutputFilename("o", cl::desc("Output filename"),
                                            cl::value_desc("filename"));
 
 static cl::opt<std::string>
-    ArchName("march",
-             cl::desc("Target arch to assemble for, "
-                      "see -version for available targets"),
+    ArchName("march", cl::desc("Target arch to assemble for, "
+                               "see -version for available targets"),
              cl::cat(ToolOptions));
 
 static cl::opt<std::string>
-    TripleName("mtriple",
-               cl::desc("Target triple to assemble for, "
-                        "see -version for available targets"),
+    TripleName("mtriple", cl::desc("Target triple to assemble for, "
+                                   "see -version for available targets"),
                cl::cat(ToolOptions));
 
 static cl::opt<std::string>
@@ -483,7 +487,7 @@ int main(int argc, char **argv) {
                      PrintInstructionTables ? 1 : Iterations);
 
     if (PrintInstructionTables) {
-      mca::InstructionTables IT(STI->getSchedModel(), IB, S);
+      mca::InstructionTables IT(SM, IB, S);
 
       if (PrintInstructionInfoView) {
         IT.addView(
@@ -496,14 +500,20 @@ int main(int argc, char **argv) {
       continue;
     }
 
-    // Ideally, I'd like to expose the pipeline building here,
-    // by registering all of the Stage instances.
-    // But for now, it's just this single puppy.
-    std::unique_ptr<mca::FetchStage> Fetch =
-        llvm::make_unique<mca::FetchStage>(IB, S);
-    mca::Backend B(*STI, *MRI, std::move(Fetch), Width, RegisterFileSize,
-                   LoadQueueSize, StoreQueueSize, AssumeNoAlias);
-    mca::BackendPrinter Printer(B);
+    // Create the hardware components required for the pipeline.
+    mca::RetireControlUnit RCU(SM);
+    mca::RegisterFile PRF(SM, *MRI, RegisterFileSize);
+    mca::Scheduler HWS(SM, LoadQueueSize, StoreQueueSize, AssumeNoAlias);
+
+    // Create the pipeline and add stages to it.
+    auto B = llvm::make_unique<mca::Backend>(
+        Width, RegisterFileSize, LoadQueueSize, StoreQueueSize, AssumeNoAlias);
+    B->appendStage(llvm::make_unique<mca::FetchStage>(IB, S));
+    B->appendStage(llvm::make_unique<mca::DispatchStage>(
+        B.get(), *STI, *MRI, RegisterFileSize, Width, RCU, PRF, HWS));
+    B->appendStage(llvm::make_unique<mca::RetireStage>(B.get(), RCU, PRF));
+    B->appendStage(llvm::make_unique<mca::ExecuteStage>(B.get(), RCU, HWS));
+    mca::BackendPrinter Printer(*B);
 
     if (PrintSummaryView)
       Printer.addView(llvm::make_unique<mca::SummaryView>(SM, S, Width));
@@ -533,7 +543,7 @@ int main(int argc, char **argv) {
           *STI, *IP, S, TimelineMaxIterations, TimelineMaxCycles));
     }
 
-    B.run();
+    B->run();
     Printer.printReport(TOF->os());
   }