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

[mattd]

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.

[mattd]

Store each stage in the pipeline as a unique_ptr. There should only be a single owner of a stage. The initial stage is owned by the backend, and all subsequent stages are owned by their predecessor stage.

[andreadb]

Hi Matt,

Thanks for the patch! See my comments below.

-Andrea

tools/llvm-mca/Backend.cpp

42

Remove this assert. By construction, you cannot have a null pointer from the SourceMgr.

tools/llvm-mca/Backend.h

58

I would just call it FetchStage for now.

86

I would remove this for now.
It is clear that this is never going to be null.

tools/llvm-mca/FetchStage.cpp

1

It should be FetchStage.cpp.

tools/llvm-mca/InstrBuilder.cpp

430–433

It should return a unique_ptr.

tools/llvm-mca/InstrBuilder.h

65

I don't like the changes to InstrBuilder.h and InstrBuilder.cpp.

I don't think that there is a good reason why createInstruction should return a normal pointer instead of a unique_ptr.

tools/llvm-mca/Instruction.h

39

I've been thinking about the instruction ownership problem.

My opinion is that there is no real advantage in passing the ownership of an instruction from stage to stage.
It complicates the logic for very little (if no) gain. It forces the instruction to be manipulated as a shared_ptr in the Scheduler.

I'd like to keep the code simple. I prefer a simpler (and more intuitive) approach where instructions are created and destroyed in the same place.

Any particular reason why the FetchStage cannot be the owner of all Instructions? At the end of each cycle, it looks for instructions that have reached the retired stage, and remove them. That approach would be much cleaner, and - more importantly - it would not require using shared_ptr everywhere.

tools/llvm-mca/Stage.h

28

Create a Stage.cpp, and pin the vtable there.
Move the definition of registerNextStage and addListener to Stage.cpp.

29

Please remove this field.

31

A stage should not "own" the next stage. I think the Backend (i.e. our pipeline) should be the owner of all the stages. Please remove this unique_ptr.

36–37

Make these two to private.

[mattd]

Thanks a ton for your comments. I'll simplify per our offline discussion, and what was grazed upon in your comments above. Thanks.

tools/llvm-mca/InstrBuilder.h

65

My reason was to allow the caller decide how to manage the pointer. The benefit was that we can treat the pointer as a shared, or unique, else where. But given comments below, I'm convinced we can leave it as is.

tools/llvm-mca/Instruction.h

39

Those are all valid points. My goal was to remove the Instructions list and any callbacks, such as eraseInstruction, to that list. I was trying to remove the need for any Stage to have to callback-out to another stage or backend. However, after discussing off-line, I am convinced to keep this Stage introduction simple. While Instruction ownership did influence this patch, and I built Stage around that idea, I am convinced that we can just move the ownership to the FetchStage, at least for now.

tools/llvm-mca/Stage.h

31

The idea was that once a stage finishes with an instruction, it would then push that instruction to the next stage in the pipeline, very reactive. However, for now, we can just manage the stages as a list in Backend.

[mattd]

• Cleaned up the code per items mentioned in the comments.
• I added a single stage to Backend.h, in the future this will be a list of stages that represent the instruction pipeline. This patch is about introducing the Stage and FetchStage idea.
• As suggested, the Instruction list is now owned by the Fetch stage, since that stage produces the instructions.
  • I wonder if it would be cleaner to have an InstructionManager class, that manages the list of Instructions?
    • When the Backend instantiates the stages of the pipeline, it would also pass a reference to the InstructionManager instance to the stages.
• The callback to Backend::eraseInstruction is still there, however, that routine now invokes the Fetch stage to remove the specified Instruction instance. I don't like that indirection, but that would be a different patch. Specifically, once we add eventing to the Stages, then that functionality would be completely removed from the Backend.
  • If we take the InstructionManager idea, then that would eliminate the eraseInstruction definition from Backend and any Stage.

[andreadb]

Thanks Matt,

the patch looks much better now. I like how you designed the Stage interface.
See my comments below.

In D46741#1098416, @mattd wrote:

• The callback to Backend::eraseInstruction is still there, however, that routine now invokes the Fetch stage to remove the specified Instruction instance. I don't like that indirection, but that would be a different patch. Specifically, once we add eventing to the Stages, then that functionality would be completely removed from the Backend.
  • If we take the InstructionManager idea, then that would eliminate the eraseInstruction definition from Backend and any Stage.

There is no reason why you shouldn't be able to get rid of it now.
In FetchStage::postExecute(), you should be able to iterate over the set of instructions, and remove instructions that have reached the retire stage.

tools/llvm-mca/Backend.h

85–89

I think that you can get rid of this, if you modify the FetchStage::postExecute() method.

tools/llvm-mca/Stage.cpp

27 ↗

(On Diff #146671)

You can simply call llvm::llvm_unreachable("...").

[mattd]

• Removed eraseInstruction. Since we place ownership of all instructions in FetchStage, we can scan the list at the end of each Fetch cycle (postExecute) and clean up retired instructions at that time (thanks Andrea for that suggestion).
• Added isRetired predicate to Instruction.h

[andreadb]

LGTM. Thanks!

tools/llvm-mca/Backend.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_MCA_BACKEND_H
 #define LLVM_TOOLS_LLVM_MCA_BACKEND_H
 
 #include "Dispatch.h"
 #include "InstrBuilder.h"
 #include "Scheduler.h"
-#include "SourceMgr.h"
+#include "Stage.h"
 
 namespace mca {
 
 class HWEventListener;
 class HWInstructionEvent;
 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:
+/// 'InitialStage'. Instructions are firstly 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 entrypoint 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 most likely an instruction fetch stage, but that decision will be
+  // decided by the backend implementation.
+  std::unique_ptr<Stage> InitialStage;
+
   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, unsigned DispatchWidth = 0,
+          unsigned RegisterFileSize = 0, unsigned LoadQueueSize = 0,
+          unsigned StoreQueueSize = 0, bool AssumeNoAlias = false)
+      : STI(Subtarget), InitialStage(nullptr),
         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 run();
 
-  void eraseInstruction(const InstRef &IR) {
-    Instructions.erase(IR.getSourceIndex());
+  void registerInitialStage(std::unique_ptr<Stage> IS) {
+    assert(IS && "Expected a non-nullptr initial stage instance.");
+    InitialStage = std::move(IS);
   }
 
   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 "FetchStage.h"
 #include "HWEventListener.h"
 #include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/Support/Debug.h"
 
 namespace mca {
 
 #define DEBUG_TYPE "llvm-mca"
 
 using namespace llvm;
 
 void Backend::addEventListener(HWEventListener *Listener) {
   if (Listener)
     Listeners.insert(Listener);
 }
 
+void Backend::run() {
+  while (InitialStage->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 (InitialStage->execute(IR)) {
+    assert(IR.isValid() && "Invalid InstRef produced by the initial stage.");
+    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();
+    InitialStage->postExecute(IR);
   }
 
   notifyCycleEnd(Cycle);
 }
 
 void Backend::notifyCycleBegin(unsigned Cycle) {
   DEBUG(dbgs() << "[E] Cycle begin: " << Cycle << '\n');
   for (HWEventListener *Listener : Listeners)

tools/llvm-mca/CMakeLists.txt

set(LLVM_LINK_COMPONENTS
   )
 
 add_llvm_tool(llvm-mca
   Backend.cpp
   BackendPrinter.cpp
   CodeRegion.cpp
   Dispatch.cpp
   DispatchStatistics.cpp
+  FetchStage.cpp
   HWEventListener.cpp
   InstrBuilder.cpp
   Instruction.cpp
   InstructionInfoView.cpp
   InstructionTables.cpp
   LSUnit.cpp
   llvm-mca.cpp
   RegisterFileStatistics.cpp

tools/llvm-mca/Dispatch.cpp

 }
 
 void DispatchUnit::notifyInstructionRetired(const InstRef &IR) {
   DEBUG(dbgs() << "[E] Instruction Retired: " << IR << '\n');
   SmallVector<unsigned, 4> FreedRegs(RAT->getNumRegisterFiles());
   for (const std::unique_ptr<WriteState> &WS : IR.getInstruction()->getDefs())
     RAT->invalidateRegisterMapping(*WS.get(), FreedRegs);
   Owner->notifyInstructionEvent(HWInstructionRetiredEvent(IR, FreedRegs));
-  Owner->eraseInstruction(IR);
 }
 
 bool DispatchUnit::checkRAT(const InstRef &IR) {
   SmallVector<unsigned, 4> RegDefs;
   for (const std::unique_ptr<WriteState> &RegDef :
        IR.getInstruction()->getDefs())
     RegDefs.emplace_back(RegDef->getRegisterID());
 

tools/llvm-mca/FetchStage.h

+//===---------------------- 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"
+
+namespace mca {
+
+class FetchStage : public Stage {
+  InstrBuilder &IB;
+  SourceMgr &SM;
+
+public:
+  FetchStage(InstrBuilder &IB, SourceMgr &SM)
+      : Stage("Fetch Stage"), 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

tools/llvm-mca/FetchStage.cpp

+//===---------------------- 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.
+///
+//===----------------------------------------------------------------------===//
+
+#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();
+  IR.update(SR.first, IB.createInstruction(*SR.second));
+  return true;
+}
+
+void FetchStage::postExecute(const InstRef &IR) { SM.updateNext(); }

tools/llvm-mca/InstrBuilder.h

public:
   // Returns an array of processor resource masks.
   // Masks are computed by function mca::computeProcResourceMasks. see
   // Support.h for a description of how masks are computed and how masks can be
   // used to solve set membership problems.
   llvm::ArrayRef<uint64_t> getProcResourceMasks() const {
     return ProcResourceMasks;
   }
 
-  std::unique_ptr<Instruction> createInstruction(const llvm::MCInst &MCI);
+  Instruction *createInstruction(const llvm::MCInst &MCI);
 };
 } // namespace mca
 
 #endif

tools/llvm-mca/InstrBuilder.cpp

 }
 
 const InstrDesc &InstrBuilder::getOrCreateInstrDesc(const MCInst &MCI) {
   if (Descriptors.find_as(MCI.getOpcode()) == Descriptors.end())
     return createInstrDescImpl(MCI);
   return *Descriptors[MCI.getOpcode()];
 }
 
-std::unique_ptr<Instruction>
+Instruction*
 InstrBuilder::createInstruction(const MCInst &MCI) {
   const InstrDesc &D = getOrCreateInstrDesc(MCI);
-  std::unique_ptr<Instruction> NewIS = llvm::make_unique<Instruction>(D);
+  Instruction *NewIS = new Instruction(D);
 
   // Initialize Reads first.
   for (const ReadDescriptor &RD : D.Reads) {
     int RegID = -1;
     if (RD.OpIndex != -1) {
       // explicit read.
       const MCOperand &Op = MCI.getOperand(RD.OpIndex);
       // Skip non-register operands.

tools/llvm-mca/Instruction.h

 
 constexpr int UNKNOWN_CYCLES = -512;
 
 class Instruction;
 
 /// An InstRef contains both a SourceMgr index and Instruction pair.  The index
 /// is used as a unique identifier for the instruction.  MCA will make use of
 /// this index as a key throughout MCA.
-class InstRef : public std::pair<unsigned, Instruction *> {
+class InstRef : public std::pair<unsigned, std::shared_ptr<Instruction>> {
 public:
-  InstRef() : std::pair<unsigned, Instruction *>(0, nullptr) {}
+  InstRef() : std::pair<unsigned, std::shared_ptr<Instruction>>(0, nullptr) {}
+  InstRef(unsigned Index, std::shared_ptr<Instruction> I)
+      : std::pair<unsigned, std::shared_ptr<Instruction>>(Index, I) {}
   InstRef(unsigned Index, Instruction *I)
-      : std::pair<unsigned, Instruction *>(Index, I) {}
+      : InstRef(Index, std::shared_ptr<Instruction>(I)) {}
 
   unsigned getSourceIndex() const { return first; }
-  Instruction *getInstruction() { return second; }
-  const Instruction *getInstruction() const { return second; }
+  std::shared_ptr<Instruction> getInstruction() { return second; }
+  const Instruction *getInstruction() const { return second.get(); }
+
+  void update(unsigned Index, Instruction *Inst) {
+    first = Index;
+    second = std::shared_ptr<Instruction>(Inst);
+  }
 
   /// Returns true if  this InstRef has been populated.
   bool isValid() const { return second != nullptr; }
 
 #ifndef NDEBUG
   void print(llvm::raw_ostream &OS) const { OS << getSourceIndex(); }
 #endif
 };

tools/llvm-mca/InstructionTables.cpp

 void InstructionTables::run() {
   ArrayRef<uint64_t> Masks = IB.getProcResourceMasks();
   SmallVector<std::pair<ResourceRef, double>, 4> UsedResources;
 
   // Create an instruction descriptor for every instruction in the sequence.
   while (S.hasNext()) {
     UsedResources.clear();
     SourceRef SR = S.peekNext();
-    std::unique_ptr<Instruction> Inst = IB.createInstruction(*SR.second);
+    Instruction *Inst = IB.createInstruction(*SR.second);
     const InstrDesc &Desc = Inst->getDesc();
     // Now 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 Index =
-          std::distance(Masks.begin(), std::find(Masks.begin(), Masks.end(),
-                                                 Resource.first));
+      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));
for (const std::pair<uint64_t, ResourceUsage> Resource : Desc.Resources) {
         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));
         }
       }
     }
 
     // Now send a fake instruction issued event to all the views.
-    InstRef IR(SR.first, Inst.get());
+    InstRef IR(SR.first, Inst);
     HWInstructionIssuedEvent Event(IR, UsedResources);
     for (std::unique_ptr<View> &Listener : Views)
       Listener->onInstructionEvent(Event);
     S.updateNext();
   }
 }
 
 void InstructionTables::printReport(llvm::raw_ostream &OS) const {
   for (const std::unique_ptr<View> &V : Views)
     V->printView(OS);
 }
 
 } // namespace mca

tools/llvm-mca/Scheduler.h

class Scheduler {
   std::unique_ptr<LSUnit> LSU;
 
   // The Backend gets notified when instructions are ready/issued/executed.
   Backend *const Owner;
 
   // The dispatch unit gets notified when instructions are executed.
   DispatchUnit *DU;
 
-  using QueueEntryTy = std::pair<unsigned, Instruction *>;
-  std::map<unsigned, Instruction *> WaitQueue;
-  std::map<unsigned, Instruction *> ReadyQueue;
-  std::map<unsigned, Instruction *> IssuedQueue;
+  using QueueEntryTy = std::pair<unsigned, std::shared_ptr<Instruction>>;
+  std::map<unsigned, std::shared_ptr<Instruction>> WaitQueue;
+  std::map<unsigned, std::shared_ptr<Instruction>> ReadyQueue;
+  std::map<unsigned, std::shared_ptr<Instruction>> IssuedQueue;
 
   void
   notifyInstructionIssued(const InstRef &IR,
                           llvm::ArrayRef<std::pair<ResourceRef, double>> Used);
   void notifyInstructionExecuted(const InstRef &IR);
   void notifyInstructionReady(const InstRef &IR);
   void notifyResourceAvailable(const ResourceRef &RR);
 

tools/llvm-mca/Scheduler.cpp

bool Scheduler::canBeDispatched(const InstRef &IR) const {
 
   Owner->notifyStallEvent(HWStallEvent(Type, IR));
   return false;
 }
 
 void Scheduler::issueInstructionImpl(
     InstRef &IR,
     SmallVectorImpl<std::pair<ResourceRef, double>> &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);
+  std::shared_ptr<Instruction> IS = IR.getInstruction();
+  Resources->issueInstruction(IS->getDesc(), UsedResources);
 
   // Notify the instruction that it started executing.
   // This updates the internal state of each write.
   IS->execute();
-
   if (IS->isExecuting())
     IssuedQueue[IR.getSourceIndex()] = IS;
 }
 
 void Scheduler::issueInstruction(InstRef &IR) {
   // Release buffered resources.
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
   releaseBuffers(Desc.Buffers);
   notifyReleasedBuffers(Desc.Buffers);
 
   // Issue IS to the underlying pipelines and notify listeners.
   SmallVector<std::pair<ResourceRef, double>, 4> Pipes;
   issueInstructionImpl(IR, Pipes);
   notifyInstructionIssued(IR, Pipes);
   if (IR.getInstruction()->isExecuted())
     notifyInstructionExecuted(IR);
 }
 
 void Scheduler::promoteToReadyQueue(SmallVectorImpl<InstRef> &Ready) {
   // Scan the set of waiting instructions and promote them to the
   // ready queue if operands are all ready.
   for (auto I = WaitQueue.begin(), E = WaitQueue.end(); I != E;) {
     const unsigned IID = I->first;
-    Instruction *IS = I->second;
+    std::shared_ptr<Instruction> IS = I->second;
 
     // Check if this instruction is now ready. In case, force
     // a transition in state using method 'update()'.
     IS->update();
 
     const InstrDesc &Desc = IS->getDesc();
     bool IsMemOp = Desc.MayLoad || Desc.MayStore;
     if (!IS->isReady() || (IsMemOp && !LSU->isReady({IID, IS}))) {
const auto It = std::find_if(ReadyQueue.begin(), ReadyQueue.end(),
                                  const InstrDesc &D = Entry.second->getDesc();
                                  return Resources->canBeIssued(D);
                                });
 
   if (It == ReadyQueue.end())
     return {0, nullptr};
 
   // We found an instruction to issue.
-  InstRef IR(It->first, It->second);
+  InstRef IR(It->first, std::shared_ptr<Instruction>(It->second));
   ReadyQueue.erase(It);
   return IR;
 }
 
 void Scheduler::updatePendingQueue(SmallVectorImpl<InstRef> &Ready) {
   // Notify to instructions in the pending queue that a new cycle just
   // started.
   for (QueueEntryTy Entry : WaitQueue)
     Entry.second->cycleEvent();
   promoteToReadyQueue(Ready);
 }
 
 void Scheduler::updateIssuedQueue(SmallVectorImpl<InstRef> &Executed) {
   for (auto I = IssuedQueue.begin(), E = IssuedQueue.end(); I != E;) {
     const QueueEntryTy Entry = *I;
-    Instruction *IS = Entry.second;
+    std::shared_ptr<Instruction> IS = Entry.second;
     IS->cycleEvent();
     if (IS->isExecuted()) {
       Executed.push_back({Entry.first, Entry.second});
       auto ToRemove = I;
       ++I;
       IssuedQueue.erase(ToRemove);
     } else {
       DEBUG(dbgs() << "[SCHEDULER]: Instruction " << Entry.first

tools/llvm-mca/Stage.h

+//===---------------------- 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 "llvm/Support/ErrorHandling.h"
+#include <memory>
+#include <string>
+
+namespace mca {
+
+class Stage {
+  std::string Name;
+  std::set<HWEventListener *> Listeners;
+  std::unique_ptr<Stage> NextStage;
+
+public:
+  Stage(std::string Name) : Name(Name), NextStage(nullptr) {}
+  virtual ~Stage() = default;
+  Stage(const Stage &Other) = delete;
+  Stage &operator=(const Stage &Other) = delete;
+
+  /// 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;
+
+  /// Append the next stage of the pipeline.
+  void registerNextStage(std::unique_ptr<Stage> S) {
+    assert(S && "Invalid stage for registration.");
+    assert(!NextStage && "Already registered next stage.");
+    NextStage = std::move(S);
+  }
+
+  /// Add a listener to receive callbaks during the execution of this stage.
+  void addListener(HWEventListener *Listener) {
+    assert(Listener && "Invalid listener instance.");
+    Listeners.insert(Listener);
+    llvm::llvm_unreachable_internal("Stage-based eventing is not implemented.");
+  }
+};
+
+} // namespace mca
+#endif // LLVM_TOOLS_LLVM_MCA_STAGE_H

tools/llvm-mca/llvm-mca.cpp

 // The cpu defaults to the 'native' host cpu.
 // The output defaults to standard output.
 //
 //===----------------------------------------------------------------------===//
 
 #include "BackendPrinter.h"
 #include "CodeRegion.h"
 #include "DispatchStatistics.h"
+#include "FetchStage.h"
 #include "InstructionInfoView.h"
 #include "InstructionTables.h"
 #include "RegisterFileStatistics.h"
 #include "ResourcePressureView.h"
 #include "RetireControlUnitStatistics.h"
 #include "SchedulerStatistics.h"
 #include "SummaryView.h"
 #include "TimelineView.h"
if (PrintInstructionTables) {
       }
 
       IT.addView(llvm::make_unique<mca::ResourcePressureView>(*STI, *IP, S));
       IT.run();
       IT.printReport(TOF->os());
       continue;
     }
 
-    mca::Backend B(*STI, *MRI, IB, S, Width, RegisterFileSize, LoadQueueSize,
+    mca::Backend B(*STI, *MRI, Width, RegisterFileSize, LoadQueueSize,
                    StoreQueueSize, AssumeNoAlias);
     mca::BackendPrinter Printer(B);
 
+    // Ideally, I'd like to expose the pipeline building here,
+    // e.g., all of the stages are chained together explictly.
+    // But for now, it's just this single puppy.
+    std::unique_ptr<mca::Stage> Fetch =
+        llvm::make_unique<mca::FetchStage>(IB, S);
+    B.registerInitialStage(std::move(Fetch));
+
     Printer.addView(llvm::make_unique<mca::SummaryView>(S, Width));
     if (PrintInstructionInfoView)
       Printer.addView(
           llvm::make_unique<mca::InstructionInfoView>(*STI, *MCII, S, *IP));
 
     if (PrintDispatchStats)
       Printer.addView(llvm::make_unique<mca::DispatchStatistics>());