[llvm-mca] Introduce a pipeline Stage class and FetchStage.

Summary:
    This is just an idea, really two ideas.  I expect some push-back,
    but I realize that posting a diff is the most comprehensive way to express
    these concepts.

    This patch introduces a Stage class which represents the
    various stages of an instruction pipeline.  As a start, I have created a simple
    FetchStage that is based on existing logic for how MCA produces
    instructions, but now encapsulated in a Stage.  The idea should become more concrete
    once we introduce additional stages.  The idea being, that when a stage completes,
    the next stage in the pipeline will be executed.  Stages are chained together
    as a singly linked list to closely model a real pipeline. For now there is only one stage,
    so the stage-to-stage flow of instructions isn't immediately obvious.

    Eventually, Stage will also handle event notifications, but that functionality
    is not complete, and not destined for this patch.  Ideally, an interested party 
    can register for notifications from a particular stage.  Callbacks will be issued to
    these listeners at various points in the execution of the stage.  
    For now, eventing functionality remains similar to what it has been in mca::Backend. 
    We will be building-up the Stage class as we move on, such as adding debug output.

    This patch also removes the unique_ptr<Instruction> return value from
    InstrBuilder::createInstruction.  An Instruction pointer is still produced,
    but now it's up to the caller to decide how that item should be managed post-allocation
    (e.g., smart pointer).  This allows the Fetch stage to create instructions and
    manage the lifetime of those instructions as it wishes, and not have to be bound to any
    specific managed pointer type.  Other callers of createInstruction might have different 
    requirements, and thus can manage the pointer to fit their needs.  Another idea would be to push the
   ownership to the RCU. 

    Currently, the FetchStage will wrap the Instruction
    pointer in a shared_ptr.  This allows us to remove the Instruction container in
    Backend, which was probably going to disappear, or move, at some point anyways.
    Note that I did run these changes through valgrind, to make sure we are not leaking
    memory.  While the shared_ptr comes with some additional overhead it relieves us
    from having to manage a list of generated instructions, and/or make lookup calls
    to remove the instructions. 

    I realize that both the Stage class and the Instruction pointer management
    (mentioned directly above) are separate but related ideas, and probably should
    land as separate patches; I am happy to do that if either idea is decent.
    The main reason these two ideas are together is that
    Stage::execute() can mutate an InstRef. For the fetch stage, the InstRef is populated
    as the primary action of that stage (execute()).  I didn't want to change the Stage interface
    to support the idea of generating an instruction.  Ideally, instructions are to
    be pushed through the pipeline.  I didn't want to draw too much of a
    specialization just for the fetch stage.  Excuse the word-salad.

Reviewers: andreadb, courbet, RKSimon

Reviewed By: andreadb

Subscribers: llvm-commits, mgorny, javed.absar, tschuett, gbedwell

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

llvm-svn: 332390

10 files changed, 216 insertions, 39 deletions

diff --git a/llvm/tools/llvm-mca/Backend.cpp b/llvm/tools/llvm-mca/Backend.cpp
index 4e6ec482eef..9b88c0af6c1 100644
--- a/llvm/tools/llvm-mca/Backend.cpp
+++ b/llvm/tools/llvm-mca/Backend.cpp
@@ -13,6 +13,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "Backend.h"
+#include "FetchStage.h"
 #include "HWEventListener.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/Support/Debug.h"
@@ -28,20 +29,21 @@ void Backend::addEventListener(HWEventListener *Listener) {
     Listeners.insert(Listener);
 }
 
+void Backend::run() {
+  while (Fetch->isReady() || !DU->isRCUEmpty())
+    runCycle(Cycles++);
+}
+
 void Backend::runCycle(unsigned Cycle) {
   notifyCycleBegin(Cycle);
 
-  while (SM.hasNext()) {
-    SourceRef SR = SM.peekNext();
-    std::unique_ptr<Instruction> NewIS = IB.createInstruction(*SR.second);
-    const InstrDesc &Desc = NewIS->getDesc();
-    Instruction *IS = NewIS.get();
-    InstRef IR(SR.first, IS);
+  InstRef IR;
+  while (Fetch->execute(IR)) {
+    const InstrDesc &Desc = IR.getInstruction()->getDesc();
     if (!DU->isAvailable(Desc.NumMicroOps) || !DU->canDispatch(IR))
       break;
-    Instructions[SR.first] = std::move(NewIS);
     DU->dispatch(IR, STI);
-    SM.updateNext();
+    Fetch->postExecute(IR);
   }
 
   notifyCycleEnd(Cycle);
diff --git a/llvm/tools/llvm-mca/Backend.h b/llvm/tools/llvm-mca/Backend.h
index fee3ca2a948..5530aaf90bd 100644
--- a/llvm/tools/llvm-mca/Backend.h
+++ b/llvm/tools/llvm-mca/Backend.h
@@ -16,9 +16,9 @@
 #define LLVM_TOOLS_LLVM_MCA_BACKEND_H
 
 #include "Dispatch.h"
+#include "FetchStage.h"
 #include "InstrBuilder.h"
 #include "Scheduler.h"
-#include "SourceMgr.h"
 
 namespace mca {
 
@@ -29,61 +29,60 @@ class HWStallEvent;
 /// An out of order backend for a specific subtarget.
 ///
 /// It emulates an out-of-order execution of instructions. Instructions are
-/// fetched from a MCInst sequence managed by an object of class SourceMgr.
-/// Instructions are firstly dispatched to the schedulers and then executed.
+/// fetched from a MCInst sequence managed by an initial 'Fetch' stage.
+/// Instructions are firstly fetched, then dispatched to the schedulers, and
+/// then executed.
+///
 /// This class tracks the lifetime of an instruction from the moment where
 /// it gets dispatched to the schedulers, to the moment where it finishes
 /// executing and register writes are architecturally committed.
 /// In particular, it monitors changes in the state of every instruction
 /// in flight.
+///
 /// Instructions are executed in a loop of iterations. The number of iterations
-/// is defined by the SourceMgr object.
-/// The Backend entrypoint is method 'Run()' which execute cycles in a loop
+/// is defined by the SourceMgr object, which is managed by the initial stage
+/// of the instruction pipeline.
+///
+/// The Backend entry point is method 'run()' which executes cycles in a loop
 /// until there are new instructions to dispatch, and not every instruction
 /// has been retired.
+///
 /// Internally, the Backend collects statistical information in the form of
 /// histograms. For example, it tracks how the dispatch group size changes
 /// over time.
 class Backend {
   const llvm::MCSubtargetInfo &STI;
 
-  InstrBuilder &IB;
+  /// This is the initial stage of the pipeline.
+  /// TODO: Eventually this will become a list of unique Stage* that this
+  /// backend pipeline executes.
+  std::unique_ptr<FetchStage> Fetch;
+
   std::unique_ptr<Scheduler> HWS;
   std::unique_ptr<DispatchUnit> DU;
-  SourceMgr &SM;
-  unsigned Cycles;
-
-  llvm::DenseMap<unsigned, std::unique_ptr<Instruction>> Instructions;
   std::set<HWEventListener *> Listeners;
+  unsigned Cycles;
 
   void runCycle(unsigned Cycle);
 
 public:
   Backend(const llvm::MCSubtargetInfo &Subtarget,
-          const llvm::MCRegisterInfo &MRI, InstrBuilder &B, SourceMgr &Source,
-          unsigned DispatchWidth = 0, unsigned RegisterFileSize = 0,
-          unsigned LoadQueueSize = 0, unsigned StoreQueueSize = 0,
-          bool AssumeNoAlias = false)
-      : STI(Subtarget), IB(B),
+          const llvm::MCRegisterInfo &MRI,
+          std::unique_ptr<FetchStage> InitialStage, unsigned DispatchWidth = 0,
+          unsigned RegisterFileSize = 0, unsigned LoadQueueSize = 0,
+          unsigned StoreQueueSize = 0, bool AssumeNoAlias = false)
+      : STI(Subtarget), Fetch(std::move(InitialStage)),
         HWS(llvm::make_unique<Scheduler>(this, Subtarget.getSchedModel(),
                                          LoadQueueSize, StoreQueueSize,
                                          AssumeNoAlias)),
         DU(llvm::make_unique<DispatchUnit>(this, Subtarget.getSchedModel(), MRI,
                                            RegisterFileSize, DispatchWidth,
                                            HWS.get())),
-        SM(Source), Cycles(0) {
+        Cycles(0) {
     HWS->setDispatchUnit(DU.get());
   }
 
-  void run() {
-    while (SM.hasNext() || !DU->isRCUEmpty())
-      runCycle(Cycles++);
-  }
-
-  void eraseInstruction(const InstRef &IR) {
-    Instructions.erase(IR.getSourceIndex());
-  }
-
+  void run();
   void addEventListener(HWEventListener *Listener);
   void notifyCycleBegin(unsigned Cycle);
   void notifyInstructionEvent(const HWInstructionEvent &Event);
diff --git a/llvm/tools/llvm-mca/CMakeLists.txt b/llvm/tools/llvm-mca/CMakeLists.txt
index 38100257355..d35ec7676bf 100644
--- a/llvm/tools/llvm-mca/CMakeLists.txt
+++ b/llvm/tools/llvm-mca/CMakeLists.txt
@@ -15,6 +15,7 @@ add_llvm_tool(llvm-mca
   CodeRegion.cpp
   Dispatch.cpp
   DispatchStatistics.cpp
+  FetchStage.cpp
   HWEventListener.cpp
   InstrBuilder.cpp
   Instruction.cpp
@@ -28,6 +29,7 @@ add_llvm_tool(llvm-mca
   RetireControlUnitStatistics.cpp
   Scheduler.cpp
   SchedulerStatistics.cpp
+  Stage.cpp
   Support.cpp
   SummaryView.cpp
   TimelineView.cpp
diff --git a/llvm/tools/llvm-mca/Dispatch.cpp b/llvm/tools/llvm-mca/Dispatch.cpp
index 1a3fb7e9476..4153173e40c 100644
--- a/llvm/tools/llvm-mca/Dispatch.cpp
+++ b/llvm/tools/llvm-mca/Dispatch.cpp
@@ -146,9 +146,9 @@ void RegisterFile::addRegisterWrite(WriteState &WS,
     RegisterMappings[*I].first = &WS;
 }
 
-void RegisterFile::removeRegisterWrite(
-    const WriteState &WS, MutableArrayRef<unsigned> FreedPhysRegs,
-    bool ShouldFreePhysRegs) {
+void RegisterFile::removeRegisterWrite(const WriteState &WS,
+                                       MutableArrayRef<unsigned> FreedPhysRegs,
+                                       bool ShouldFreePhysRegs) {
   unsigned RegID = WS.getRegisterID();
   bool ShouldInvalidateSuperRegs = WS.fullyUpdatesSuperRegs();
 
@@ -273,7 +273,6 @@ void DispatchUnit::notifyInstructionRetired(const InstRef &IR) {
   for (const std::unique_ptr<WriteState> &WS : IR.getInstruction()->getDefs())
     RAT->removeRegisterWrite(*WS.get(), FreedRegs, !Desc.isZeroLatency());
   Owner->notifyInstructionEvent(HWInstructionRetiredEvent(IR, FreedRegs));
-  Owner->eraseInstruction(IR);
 }
 
 bool DispatchUnit::checkRAT(const InstRef &IR) {
diff --git a/llvm/tools/llvm-mca/FetchStage.cpp b/llvm/tools/llvm-mca/FetchStage.cpp
new file mode 100644
index 00000000000..b9e5e0d5ee4
--- /dev/null
+++ b/llvm/tools/llvm-mca/FetchStage.cpp
@@ -0,0 +1,38 @@
+//===---------------------- FetchStage.cpp ----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file defines the Fetch stage of an instruction pipeline.  Its sole
+/// purpose in life is to produce instructions for the rest of the pipeline.
+///
+//===----------------------------------------------------------------------===//
+
+#include "FetchStage.h"
+#include "Instruction.h"
+
+using namespace mca;
+
+bool FetchStage::isReady() { return SM.hasNext(); }
+
+bool FetchStage::execute(InstRef &IR) {
+  if (!SM.hasNext())
+    return false;
+  const SourceRef SR = SM.peekNext();
+  std::unique_ptr<Instruction> I = IB.createInstruction(*SR.second);
+  IR = InstRef(SR.first, I.get());
+  Instructions[IR.getSourceIndex()] = std::move(I);
+  return true;
+}
+
+void FetchStage::postExecute(const InstRef &IR) {
+  // Reclaim instructions that have been retired.
+  llvm::remove_if(Instructions,
+                  [](InstMapPr &Pr) { return Pr.getSecond()->isRetired(); });
+  SM.updateNext();
+}
diff --git a/llvm/tools/llvm-mca/FetchStage.h b/llvm/tools/llvm-mca/FetchStage.h
new file mode 100644
index 00000000000..823dc37b132
--- /dev/null
+++ b/llvm/tools/llvm-mca/FetchStage.h
@@ -0,0 +1,47 @@
+//===---------------------- FetchStage.h ------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file defines the Fetch stage of an instruction pipeline.  Its sole
+/// purpose in life is to produce instructions for the rest of the pipeline.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_MCA_FETCH_STAGE_H
+#define LLVM_TOOLS_LLVM_MCA_FETCH_STAGE_H
+
+#include "InstrBuilder.h"
+#include "Instruction.h"
+#include "SourceMgr.h"
+#include "Stage.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace mca {
+
+class FetchStage : public Stage {
+  using InstMap = llvm::DenseMap<unsigned, std::unique_ptr<Instruction>>;
+  using InstMapPr =
+      llvm::detail::DenseMapPair<unsigned, std::unique_ptr<Instruction>>;
+  InstMap Instructions;
+  InstrBuilder &IB;
+  SourceMgr &SM;
+
+public:
+  FetchStage(InstrBuilder &IB, SourceMgr &SM) : IB(IB), SM(SM) {}
+  FetchStage(const FetchStage &Other) = delete;
+  FetchStage &operator=(const FetchStage &Other) = delete;
+
+  bool isReady() override final;
+  bool execute(InstRef &IR) override final;
+  void postExecute(const InstRef &IR) override final;
+};
+
+} // namespace mca
+
+#endif // LLVM_TOOLS_LLVM_MCA_FETCH_STAGE_H
diff --git a/llvm/tools/llvm-mca/Instruction.h b/llvm/tools/llvm-mca/Instruction.h
index f68951c4118..81f12cc2efb 100644
--- a/llvm/tools/llvm-mca/Instruction.h
+++ b/llvm/tools/llvm-mca/Instruction.h
@@ -347,6 +347,7 @@ public:
   bool isReady() const { return Stage == IS_READY; }
   bool isExecuting() const { return Stage == IS_EXECUTING; }
   bool isExecuted() const { return Stage == IS_EXECUTED; }
+  bool isRetired() const { return Stage == IS_RETIRED; }
 
   void retire() {
     assert(isExecuted() && "Instruction is in an invalid state!");
diff --git a/llvm/tools/llvm-mca/Stage.cpp b/llvm/tools/llvm-mca/Stage.cpp
new file mode 100644
index 00000000000..5d6ae56b5df
--- /dev/null
+++ b/llvm/tools/llvm-mca/Stage.cpp
@@ -0,0 +1,28 @@
+//===---------------------- Stage.cpp ---------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file defines a stage.
+/// A chain of stages compose an instruction pipeline.
+///
+//===----------------------------------------------------------------------===//
+
+#include "Stage.h"
+#include "llvm/Support/ErrorHandling.h"
+
+namespace mca {
+
+// Pin the vtable here in the implementation file.
+Stage::Stage() {}
+
+void Stage::addListener(HWEventListener *Listener) {
+  llvm::llvm_unreachable_internal("Stage-based eventing is not implemented.");
+}
+
+} // namespace mca
diff --git a/llvm/tools/llvm-mca/Stage.h b/llvm/tools/llvm-mca/Stage.h
new file mode 100644
index 00000000000..829803d107d
--- /dev/null
+++ b/llvm/tools/llvm-mca/Stage.h
@@ -0,0 +1,55 @@
+//===---------------------- Stage.h -----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file defines a stage.
+/// A chain of stages compose an instruction pipeline.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_MCA_STAGE_H
+#define LLVM_TOOLS_LLVM_MCA_STAGE_H
+
+#include "HWEventListener.h"
+#include "Instruction.h"
+#include "SourceMgr.h"
+#include <memory>
+#include <string>
+
+namespace mca {
+
+class Stage {
+  std::set<HWEventListener *> Listeners;
+  Stage(const Stage &Other) = delete;
+  Stage &operator=(const Stage &Other) = delete;
+
+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() { return true; }
+
+  /// Called as a setup phase to prepare for the main stage execution.
+  virtual void preExecute(const InstRef &IR) {}
+
+  /// Called as a cleanup and finalization phase after main stage execution.
+  virtual void postExecute(const InstRef &IR) {}
+
+  /// The primary action that this stage performs.
+  virtual bool execute(InstRef &IR) = 0;
+
+  /// Add a listener to receive callbaks during the execution of this stage.
+  void addListener(HWEventListener *Listener);
+};
+
+} // namespace mca
+#endif // LLVM_TOOLS_LLVM_MCA_STAGE_H
diff --git a/llvm/tools/llvm-mca/llvm-mca.cpp b/llvm/tools/llvm-mca/llvm-mca.cpp
index 75ffca6d20d..51d6ad1d984 100644
--- a/llvm/tools/llvm-mca/llvm-mca.cpp
+++ b/llvm/tools/llvm-mca/llvm-mca.cpp
@@ -24,6 +24,7 @@
 #include "BackendPrinter.h"
 #include "CodeRegion.h"
 #include "DispatchStatistics.h"
+#include "FetchStage.h"
 #include "InstructionInfoView.h"
 #include "InstructionTables.h"
 #include "RegisterFileStatistics.h"
@@ -435,8 +436,13 @@ int main(int argc, char **argv) {
       continue;
     }
 
-    mca::Backend B(*STI, *MRI, IB, S, Width, RegisterFileSize, LoadQueueSize,
-                   StoreQueueSize, AssumeNoAlias);
+    // 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);
 
     Printer.addView(llvm::make_unique<mca::SummaryView>(S, Width));