[llvm-mca] Introduce a sequential container of Stages

[mattd]

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.

[mattd]

tools/llvm-mca/Backend.cpp

80

This case should never occur, but since we expose this as a public api routine, I want to be super-confident that users are using the backend correctly, e.g., an initial stage is always available.

[mattd]

This patch isn't crucial now, but eventually we'll most likely want to collect all stages in a sequential container.

[andreadb]

tools/llvm-mca/Backend.cpp

80

I don't see the reason why we should expose this method. Unless I am missing something, this method is completely redundant.

If you really need it, then it should be made private. Also, the assert is not needed. Instead, you should early exit from Backend::run() if there are no stages to run.

As a side note: you can use method empty() to check if there is at least one stage in the pipeline.

tools/llvm-mca/Backend.h

23

Is this include really needed? You implicitly get it from Dispatch.h

62

Any reason why a default of 2 elements? In practice we are going to have at least 4 stages.

78

What if we initialize this stage outside of Backend.h ?
Ideally, the Backend should be empty to start. It shouldn't be populated by the constructor; instead, users should populate the pipeline by performing multiple calls to method appendStage(). I think that the InitialStage should be added by main in llvm-mca.cpp.

81

See my comment below. I don't think this method is needed.

[courbet]

tools/llvm-mca/Backend.h

78

+1. This will make it possible for subtargets to customize this more when we move to a per-subtarget factory.

[mattd]

tools/llvm-mca/Backend.cpp

80

It's not necessary. Eventually the backend will just loop through all of the stages calling pre/execute/post accordingly. The backend will just go through the list sequentially ignorant of what the stage actually does.

tools/llvm-mca/Backend.h

62

No reason than for now I'm just trying to work in the Fetch and Dispatch portions. The number should increase accordingly :)

78

Agreed!

[courbet]

tools/llvm-mca/Backend.h

23

I think it should be included:

https://llvm.org/docs/CodingStandards.html#minimal-list-of-includes

You must include all of the header files that you are using

[andreadb]

tools/llvm-mca/Backend.h

23

[...] you can include them either directly or indirectly through another header file

I guess, it is a matter of how you interpret it?
Given the low importance of this, I don't really mind if we keep the include.

[mattd]

[mattd]

This change lifts the component initialization (stages and simulated hardware bits) out of Backend and into llvm-mca. That code will eventually be exposed as initializeDefaultPipeline. This patch removes the ownership of the simulated hardware pieces (Scheduler, RegisterFile, etc) from the Backend. Now a user can create stages using the simulated hardware components without having to enforce that the Backend own those components. That happens to simplify pipeline construction; however, we'll eventually need to pass ownership of the hardware with the stages. But for now, the patch just decouples hardware, stages, and the backend.

[mattd]

tools/llvm-mca/llvm-mca.cpp

74 ↗

(On Diff #152399)

I know the formatting here is not related to the primary idea behind this patch, but I decided to run clang-format on the entire file. If you prefer, I can ignore the formatting of the options here, and submit that as a NFC later.

[andreadb]

LGTM.

Thanks for doing this!

tools/llvm-mca/llvm-mca.cpp

74 ↗

(On Diff #152399)

No problem. It looks good :-)

tools/llvm-mca/Backend.h

 ///
 /// This file implements an OoO backend for the llvm-mca tool.
 ///
 //===----------------------------------------------------------------------===//
 
 #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 {
 
 class HWEventListener;
 class HWInstructionEvent;
 class HWStallEvent;
 
 /// An out of order backend for a specific subtarget.

 /// 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);
+  void appendStage(std::unique_ptr<Stage> S) { Stages.push_back(std::move(S)); }
 
 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) {}
-
+          unsigned StoreQueueSize = 0, bool AssumeNoAlias = false);
   void run();
   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

tools/llvm-mca/Backend.cpp

 //===--------------------- Backend.cpp --------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// Implementation of class Backend which emulates an hardware OoO backend.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "Backend.h"
+#include "DispatchStage.h"
+#include "ExecuteStage.h"
 #include "FetchStage.h"
 #include "HWEventListener.h"
+#include "RetireStage.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/Support/Debug.h"
 
 namespace mca {
 
 #define DEBUG_TYPE "llvm-mca"
 
 using namespace llvm;
 
+Backend::Backend(const llvm::MCSubtargetInfo &Subtarget,
+                 const llvm::MCRegisterInfo &MRI,
+                 std::unique_ptr<FetchStage> InitialStage,
+                 unsigned DispatchWidth, unsigned RegisterFileSize,
+                 unsigned LoadQueueSize, unsigned StoreQueueSize,
+                 bool AssumeNoAlias)
+    : RCU(Subtarget.getSchedModel()),
+      PRF(Subtarget.getSchedModel(), MRI, RegisterFileSize),
+      HWS(Subtarget.getSchedModel(), LoadQueueSize, StoreQueueSize,
+          AssumeNoAlias) {
+  Cycles = 0;
+  appendStage(std::move(InitialStage));
+  appendStage(llvm::make_unique<DispatchStage>(
+      this, Subtarget, MRI, RegisterFileSize, DispatchWidth, RCU, PRF, HWS));
+  appendStage(llvm::make_unique<RetireStage>(this, RCU, PRF));
+  appendStage(llvm::make_unique<ExecuteStage>(this, RCU, HWS));
+}
+
 void Backend::addEventListener(HWEventListener *Listener) {
   if (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++);
 }
 
 void Backend::runCycle(unsigned Cycle) {
   notifyCycleBegin(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);
 }
 
 void Backend::notifyCycleBegin(unsigned Cycle) {
   LLVM_DEBUG(dbgs() << "[E] Cycle begin: " << Cycle << '\n');
   for (HWEventListener *Listener : Listeners)
     Listener->onCycleBegin();

tools/llvm-mca/DispatchStage.h

class DispatchStage : public Stage {
   RetireControlUnit &RCU;
   RegisterFile &PRF;
   Scheduler ≻
 
   bool checkRCU(const InstRef &IR);
   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,
                                    llvm::ArrayRef<unsigned> UsedPhysRegs);
 
   bool isAvailable(unsigned NumEntries) const {
     return NumEntries <= AvailableEntries || AvailableEntries == DispatchWidth;
   }

 public:
   DispatchStage(Backend *B, const llvm::MCSubtargetInfo &Subtarget,
                 const llvm::MCRegisterInfo &MRI, unsigned RegisterFileSize,
                 unsigned MaxDispatchWidth, RetireControlUnit &R,
                 RegisterFile &F, Scheduler &Sched)
       : 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);
 
 #ifndef NDEBUG
   void dump() const;
 #endif
 };
 } // namespace mca
 
 #endif // LLVM_TOOLS_LLVM_MCA_DISPATCH_STAGE_H

tools/llvm-mca/ExecuteStage.h

class ExecuteStage : public Stage {
   void issueReadyInstructions();
 
 public:
   ExecuteStage(Backend *B, RetireControlUnit &R, Scheduler &S)
       : Stage(), Owner(B), RCU(R), HWS(S) {}
   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;
 
   void
   notifyInstructionIssued(const InstRef &IR,
                           llvm::ArrayRef<std::pair<ResourceRef, double>> Used);
   void notifyInstructionExecuted(const InstRef &IR);
   void notifyInstructionReady(const InstRef &IR);

tools/llvm-mca/ExecuteStage.cpp

#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.
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
   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);
 
   // Don't add a zero-latency instruction to the Wait or Ready queue.
   // A zero-latency instruction doesn't consume any scheduler resources. That is
   // because it doesn't need to be executed, and it is often removed at register
   // renaming stage. For example, register-register moves are often optimized at

tools/llvm-mca/FetchStage.h

class FetchStage : public Stage {
   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() const override final;
+  bool hasWorkToComplete() const 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

tools/llvm-mca/FetchStage.cpp

 /// purpose in life is to produce instructions for the rest of the pipeline.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "FetchStage.h"
 
 namespace mca {
 
-bool FetchStage::isReady() const { return SM.hasNext(); }
+bool FetchStage::hasWorkToComplete() const { 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);

tools/llvm-mca/RetireStage.h

class RetireStage : public Stage {
   RegisterFile &PRF;
 
 public:
   RetireStage(Backend *B, RetireControlUnit &R, RegisterFile &F)
       : Stage(), Owner(B), RCU(R), PRF(F) {}
   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);
   void onInstructionExecuted(unsigned TokenID);
 };
 
 } // namespace mca
 
 #endif // LLVM_TOOLS_LLVM_MCA_RETIRE_STAGE_H

tools/llvm-mca/Stage.h

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() 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) {}
 
   /// 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