[llvm-mca] Refactor how execution is orchestrated by the Pipeline. NFCI

[andreadb]

Summary

This patch changes how instruction execution is orchestrated by the Pipeline.

In particular, this patch makes it more explicit how instructions transition through the various pipeline stages during execution.

The main goal is to simplify the stage API and simpify the Pipeline execution. At the same time, this patch fixes some issues which are currently latent, but that are likely to cause problems in future if people define custom pipelines.

The new design assumes that each pipeline stage knows the "next-in-sequence".
The Stage API has gained two new methods:

• isAvailable(IR)
• checkNextStage(IR)
• moveToTheNextStage(IR).

An instruction IR can be executed by a Stage if method Stage::isAvailable(IR) returns true.
Stage may accept a limited number of instructions per cycle. So, method isAvailable(IR) is responsible for checking if instruction IR can execute within the current cycle.

Instructions can move to next stages using method moveToTheNextStage(IR).
An instruction cannot be moved to the next stage if method checkNextStage(IR) (called on the current stage) returns false.

Instruction IR may be allowed to transition through multiple stages in a single cycle, provided that stages are available, and that checkNextStage(IR) always returns true.

Since now stages know about their "next-in-sequence", some methods in the Stage interface have become now redundant. For example, this patch gets rid of Stage::preExecute() and Stage::postExecute().

Method Pipeline::runCycle() is now much simpler, and it correctly visits stages in post-order at the beginning/end of a cycle. Before, this caused an issue with the sequence of stages in the default pipeline; that issue is now fixed.

Other changes:

1. DispatchStage no longer requires a reference to the Scheduler.
2. ExecuteStage no longer needs to directly interact with the RetireControlUnit. Instead, executed instructions are now directly moved to the next stage (i.e. the retire stage).
3. RetireStage gained an execute method. This allowed us to remove the dependency with the RCU in ExecuteStage.
4. FecthStage now updates the "program counter" during cycleBegin() (i.e. before we start executing new instructions).
5. We no longer need Stage::Status to be returned by method execute(). It has been dropped in favor of a more lightweight llvm::Error.

With this change, the Pipeline logic is simplified. We no longer generate extra calls to pre/postExecute() every instruction. We also avoid redundant execute(IR) calls on stages that are not reached by IR (that was an oddity of the previous design).

Overally, when testing a debug build of llvm-mca, I measured a ~11% performance gain w.r.t. the previous design. I also think that the Stage interface is probably easier to read now. That being said, code comments have to be improved (I plan to do it in a follow-up patch).

Please let me know if okay to commit.

-Andrea

[mattd]

I made a few comments, all just nits. This is a pretty substantial change in design, but better. LGTM. Thanks for this!

tools/llvm-mca/FetchStage.cpp

37

nit: Not sure if we want whitespace here. Lines 41 and 43 below do not use white space to separate the if block.

tools/llvm-mca/Stage.h

58

Would there ever be the case where a stage might want to overwrite its NextInSequence? If not, then perhaps we should add an assertion.

65

This is the fundamental difference from this design and the previous incarnation of Stage. I think this comment should be a bit more explicit in saying that a Stage is responsible for transferring the instruction it completes processing on to its immediate successor stage.

[andreadb]

Hi Matt,

Thanks for the review.

tools/llvm-mca/Context.cpp

43

I plan to change that variable name to "StagePipeline".
Just to be consistent with the other naming convention.

tools/llvm-mca/FetchStage.cpp

37

I will remove that whitespace.

tools/llvm-mca/Stage.h

58

In future, we may want to allow stages to be inserted at specific positions (i.e. not just appended at the end of the pipeline).
That being said, for now it makes sense to have an assert. I will do it.

65

I will elaborate this a bit more.

[andreadb]

Addressed review comments.

[mattd]

Thanks!
LGTM (again)

tools/llvm-mca/Context.cpp

Context::createDefaultPipeline(const PipelineOptions &Opts, InstrBuilder &IB,
 
   // Create the hardware units defining the backend.
   auto RCU = llvm::make_unique<RetireControlUnit>(SM);
   auto PRF = llvm::make_unique<RegisterFile>(SM, MRI, Opts.RegisterFileSize);
   auto HWS = llvm::make_unique<Scheduler>(
       SM, Opts.LoadQueueSize, Opts.StoreQueueSize, Opts.AssumeNoAlias);
 
   // Create the pipeline and its stages.
   auto P = llvm::make_unique<Pipeline>();
-  auto F = llvm::make_unique<FetchStage>(IB, SrcMgr);
-  auto D = llvm::make_unique<DispatchStage>(
-      STI, MRI, Opts.RegisterFileSize, Opts.DispatchWidth, *RCU, *PRF, *HWS);
-  auto R = llvm::make_unique<RetireStage>(*RCU, *PRF);
-  auto E = llvm::make_unique<ExecuteStage>(*RCU, *HWS);
+  auto Fetch = llvm::make_unique<FetchStage>(IB, SrcMgr);
+  auto Dispatch = llvm::make_unique<DispatchStage>(
+      STI, MRI, Opts.RegisterFileSize, Opts.DispatchWidth, *RCU, *PRF);
+  auto Execute = llvm::make_unique<ExecuteStage>(*HWS);
+  auto Retire = llvm::make_unique<RetireStage>(*RCU, *PRF);
 
   // Add the hardware to the context.
   addHardwareUnit(std::move(RCU));
   addHardwareUnit(std::move(PRF));
   addHardwareUnit(std::move(HWS));
 
   // Build the pipeline.
-  P->appendStage(std::move(F));
-  P->appendStage(std::move(D));
-  P->appendStage(std::move(R));
-  P->appendStage(std::move(E));
+  P->appendStage(std::move(Fetch));
+  P->appendStage(std::move(Dispatch));
+  P->appendStage(std::move(Execute));
+  P->appendStage(std::move(Retire));
   return P;
 }
 
 } // namespace mca

tools/llvm-mca/DispatchStage.h

 #include "RegisterFile.h"
 #include "RetireControlUnit.h"
 #include "Stage.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/MC/MCSubtargetInfo.h"
 
 namespace mca {
 
-class Scheduler;
-
 // Implements the hardware dispatch logic.
 //
 // This class is responsible for the dispatch stage, in which instructions are
 // dispatched in groups to the Scheduler.  An instruction can be dispatched if
 // the following conditions are met:
 //  1) There are enough entries in the reorder buffer (see class
 //     RetireControlUnit) to write the opcodes associated with the instruction.
 //  2) There are enough physical registers to rename output register operands.

 // is dispatched in multiple cycles.
 class DispatchStage final : public Stage {
   unsigned DispatchWidth;
   unsigned AvailableEntries;
   unsigned CarryOver;
   const llvm::MCSubtargetInfo &STI;
   RetireControlUnit &RCU;
   RegisterFile &PRF;
-  Scheduler ≻
 
   bool checkRCU(const InstRef &IR) const;
   bool checkPRF(const InstRef &IR) const;
-  bool checkScheduler(const InstRef &IR) const;
-  void dispatch(InstRef IR);
+  llvm::Error dispatch(InstRef IR);
   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;
-  }
-
-  bool canDispatch(const InstRef &IR) {
-    assert(isAvailable(IR.getInstruction()->getDesc().NumMicroOps));
-    return checkRCU(IR) && checkPRF(IR) && checkScheduler(IR);
-  }
+  bool canDispatch(const InstRef &IR) const;
 
   void collectWrites(llvm::SmallVectorImpl<WriteRef> &Vec,
                      unsigned RegID) const {
     return PRF.collectWrites(Vec, RegID);
   }
 
 public:
   DispatchStage(const llvm::MCSubtargetInfo &Subtarget,
                 const llvm::MCRegisterInfo &MRI, unsigned RegisterFileSize,
                 unsigned MaxDispatchWidth, RetireControlUnit &R,
-                RegisterFile &F, Scheduler &Sched)
+                RegisterFile &F)
       : DispatchWidth(MaxDispatchWidth), AvailableEntries(MaxDispatchWidth),
-        CarryOver(0U), STI(Subtarget), RCU(R), PRF(F), SC(Sched) {}
+        CarryOver(0U), STI(Subtarget), RCU(R), PRF(F) {}
+
+  bool isAvailable(const InstRef &IR) const override;
 
-  // 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.
+  // The dispatch logic internally doesn't buffer instructions. So there is
+  // never work to do at the beginning of every cycle.
   bool hasWorkToComplete() const override { return false; }
   llvm::Error cycleStart() override;
-  Status execute(InstRef &IR) override;
+  llvm::Error execute(InstRef &IR) override;
   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/DispatchStage.cpp

bool DispatchStage::checkRCU(const InstRef &IR) const {
   const unsigned NumMicroOps = IR.getInstruction()->getDesc().NumMicroOps;
   if (RCU.isAvailable(NumMicroOps))
     return true;
   notifyEvent<HWStallEvent>(
       HWStallEvent(HWStallEvent::RetireControlUnitStall, IR));
   return false;
 }
 
-bool DispatchStage::checkScheduler(const InstRef &IR) const {
-  HWStallEvent::GenericEventType Event;
-  const bool Ready = SC.canBeDispatched(IR, Event);
-  if (!Ready)
-    notifyEvent<HWStallEvent>(HWStallEvent(Event, IR));
-  return Ready;
+bool DispatchStage::canDispatch(const InstRef &IR) const {
+  return checkRCU(IR) && checkPRF(IR) && checkNextStage(IR);
 }
 
 void DispatchStage::updateRAWDependencies(ReadState &RS,
                                           const MCSubtargetInfo &STI) {
   SmallVector<WriteRef, 4> DependentWrites;
 
   collectWrites(DependentWrites, RS.getRegisterID());
   RS.setDependentWrites(DependentWrites.size());
   // We know that this read depends on all the writes in DependentWrites.
   // For each write, check if we have ReadAdvance information, and use it
   // to figure out in how many cycles this read becomes available.
   const ReadDescriptor &RD = RS.getDescriptor();
   const MCSchedModel &SM = STI.getSchedModel();
   const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID);
   for (WriteRef &WR : DependentWrites) {
     WriteState &WS = *WR.getWriteState();
     unsigned WriteResID = WS.getWriteResourceID();
     int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID);
     WS.addUser(&RS, ReadAdvance);
   }
 }
 
-void DispatchStage::dispatch(InstRef IR) {
+llvm::Error DispatchStage::dispatch(InstRef IR) {
   assert(!CarryOver && "Cannot dispatch another instruction!");
   Instruction &IS = *IR.getInstruction();
   const InstrDesc &Desc = IS.getDesc();
   const unsigned NumMicroOps = Desc.NumMicroOps;
   if (NumMicroOps > DispatchWidth) {
     assert(AvailableEntries == DispatchWidth);
     AvailableEntries = 0;
     CarryOver = NumMicroOps - DispatchWidth;
for (std::unique_ptr<WriteState> &WS : IS.getDefs()) {
     PRF.addRegisterWrite(WriteRef(IR.first, WS.get()), RegisterFiles,
                          ShouldAllocateRegisters);
   }
 
   // Reserve slots in the RCU, and notify the instruction that it has been
   // dispatched to the schedulers for execution.
   IS.dispatch(RCU.reserveSlot(IR, NumMicroOps));
 
-  // Notify listeners of the "instruction dispatched" event.
+  // Notify listeners of the "instruction dispatched" event,
+  // and move IR to the next stage.
   notifyInstructionDispatched(IR, RegisterFiles);
+  return std::move(moveToTheNextStage(IR));
 }
 
 llvm::Error DispatchStage::cycleStart() {
   AvailableEntries = CarryOver >= DispatchWidth ? 0 : DispatchWidth - CarryOver;
   CarryOver = CarryOver >= DispatchWidth ? CarryOver - DispatchWidth : 0U;
   return llvm::ErrorSuccess();
 }
 
-Stage::Status DispatchStage::execute(InstRef &IR) {
+bool DispatchStage::isAvailable(const InstRef &IR) const {
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
-  if (!isAvailable(Desc.NumMicroOps) || !canDispatch(IR))
-    return Stage::Stop;
-  dispatch(IR);
-  return Stage::Continue;
+  unsigned Required = std::min(Desc.NumMicroOps, DispatchWidth);
+  if (Required > AvailableEntries)
+    return false;
+  // The dispatch logic doesn't internally buffer instructions.  It only accepts
+  // instructions that can be successfully moved to the next stage during this
+  // same cycle.
+  return canDispatch(IR);
+}
+
+llvm::Error DispatchStage::execute(InstRef &IR) {
+  assert(canDispatch(IR) && "Cannot dispatch another instruction!");
+  return std::move(dispatch(IR));
 }
 
 #ifndef NDEBUG
 void DispatchStage::dump() const {
   PRF.dump();
   RCU.dump();
 }
 #endif
 } // namespace mca

tools/llvm-mca/ExecuteStage.h

 /// and issuing notifications that an instruction has been executed.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_MCA_EXECUTE_STAGE_H
 #define LLVM_TOOLS_LLVM_MCA_EXECUTE_STAGE_H
 
 #include "Instruction.h"
-#include "RetireControlUnit.h"
 #include "Scheduler.h"
 #include "Stage.h"
 #include "llvm/ADT/ArrayRef.h"
 
 namespace mca {
 
 class ExecuteStage final : public Stage {
-  // Owner will go away when we move listeners/eventing to the stages.
-  RetireControlUnit &RCU;
   Scheduler &HWS;
 
   // The following routines are used to maintain the HWS.
   void reclaimSchedulerResources();
   llvm::Error updateSchedulerQueues();
   llvm::Error issueReadyInstructions();
 
   ExecuteStage(const ExecuteStage &Other) = delete;
   ExecuteStage &operator=(const ExecuteStage &Other) = delete;
 
 public:
-  ExecuteStage(RetireControlUnit &R, Scheduler &S) : Stage(), RCU(R), HWS(S) {}
+  ExecuteStage(Scheduler &S) : Stage(), HWS(S) {}
 
   // This stage works under the assumption that the Pipeline will eventually
   // execute a retire stage. We don't need to check if pipelines and/or
   // schedulers have instructions to process, because those instructions are
   // also tracked by the retire control unit. That means,
   // RetireControlUnit::hasWorkToComplete() is responsible for checking if there
   // are still instructions in-flight in the out-of-order backend.
   bool hasWorkToComplete() const override { return false; }
-
+  bool isAvailable(const InstRef &IR) const override;
   llvm::Error cycleStart() override;
-  Status execute(InstRef &IR) override;
+  llvm::Error execute(InstRef &IR) override;
 
   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/ExecuteStage.cpp

 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "llvm-mca"
 
 namespace mca {
 
 using namespace llvm;
 
+bool ExecuteStage::isAvailable(const InstRef &IR) const {
+  HWStallEvent::GenericEventType Event;
+  if (HWS.canBeDispatched(IR, Event))
+    return true;
+  notifyEvent<HWStallEvent>(HWStallEvent(Event, IR));
+  return false;
+}
+
 // Reclaim the simulated resources used by the scheduler.
 void ExecuteStage::reclaimSchedulerResources() {
   SmallVector<ResourceRef, 8> ResourcesFreed;
   HWS.reclaimSimulatedResources(ResourcesFreed);
   for (const ResourceRef &RR : ResourcesFreed)
     notifyResourceAvailable(RR);
 }
 
 // Update the scheduler's instruction queues.
 Error ExecuteStage::updateSchedulerQueues() {
   SmallVector<InstRef, 4> InstructionIDs;
   HWS.updateIssuedSet(InstructionIDs);
-  for (const InstRef &IR : InstructionIDs)
+  for (InstRef &IR : InstructionIDs) {
     notifyInstructionExecuted(IR);
+    //FIXME: add a buffer of executed instructions.
+    if (Error S = moveToTheNextStage(IR))
+      return S;
+  }
   InstructionIDs.clear();
 
   HWS.updatePendingQueue(InstructionIDs);
   for (const InstRef &IR : InstructionIDs)
     notifyInstructionReady(IR);
   return ErrorSuccess();
 }
 
 // Issue instructions that are waiting in the scheduler's ready queue.
 Error ExecuteStage::issueReadyInstructions() {
   SmallVector<InstRef, 4> InstructionIDs;
   InstRef IR = HWS.select();
   while (IR.isValid()) {
     SmallVector<std::pair<ResourceRef, double>, 4> Used;
     HWS.issueInstruction(IR, Used);
 
     // Reclaim instruction resources and perform notifications.
     const InstrDesc &Desc = IR.getInstruction()->getDesc();
     notifyReleasedBuffers(Desc.Buffers);
     notifyInstructionIssued(IR, Used);
-    if (IR.getInstruction()->isExecuted())
+    if (IR.getInstruction()->isExecuted()) {
       notifyInstructionExecuted(IR);
+      //FIXME: add a buffer of executed instructions.
+      if (Error S = moveToTheNextStage(IR))
+        return S;
+    }
 
     // Instructions that have been issued during this cycle might have unblocked
     // other dependent instructions. Dependent instructions may be issued during
     // this same cycle if operands have ReadAdvance entries.  Promote those
     // instructions to the ReadySet and tell to the caller that we need
     // another round of 'issue()'.
     HWS.promoteToReadySet(InstructionIDs);
     for (const InstRef &I : InstructionIDs)

 Error ExecuteStage::cycleStart() {
   reclaimSchedulerResources();
   if (Error S = updateSchedulerQueues())
     return S;
   return issueReadyInstructions();
 }
 
 // Schedule the instruction for execution on the hardware.
-Stage::Status ExecuteStage::execute(InstRef &IR) {
+Error ExecuteStage::execute(InstRef &IR) {
+  assert(isAvailable(IR) && "Scheduler is not available!");
+
 #ifndef NDEBUG
   // Ensure that the HWS has not stored this instruction in its queues.
   HWS.sanityCheck(IR);
 #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.  If we cannot reserve resources, return true, so
   // that succeeding stages can make progress.
   if (!HWS.reserveResources(IR))
-    return Stage::Continue;
+    return ErrorSuccess();
 
   // 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
   // register renaming stage by simply updating register aliases. On some
   // targets, zero-idiom instructions (for example: a xor that clears the value
   // of a register) are treated specially, and are often eliminated at register
   // renaming stage.
   //
   // Instructions that use an in-order dispatch/issue processor resource must be
   // issued immediately to the pipeline(s). Any other in-order buffered
   // resources (i.e. BufferSize=1) is consumed.
   //
   // If we cannot issue immediately, the HWS will add IR to its ready queue for
   // execution later, so we must return early here.
   if (!HWS.issueImmediately(IR))
-    return Stage::Continue;
+    return ErrorSuccess();
 
   LLVM_DEBUG(dbgs() << "[SCHEDULER] Instruction #" << IR
                     << " issued immediately\n");
 
   // Issue IR.  The resources for this issuance will be placed in 'Used.'
   SmallVector<std::pair<ResourceRef, double>, 4> Used;
   HWS.issueInstruction(IR, Used);
 
   // Perform notifications.
   notifyReleasedBuffers(Desc.Buffers);
   notifyInstructionIssued(IR, Used);
-  if (IR.getInstruction()->isExecuted())
+  if (IR.getInstruction()->isExecuted()) {
     notifyInstructionExecuted(IR);
-
-  return Stage::Continue;
+    //FIXME: add a buffer of executed instructions.
+    return std::move(moveToTheNextStage(IR));
+  }
+  return ErrorSuccess();
 }
 
 void ExecuteStage::notifyInstructionExecuted(const InstRef &IR) {
   HWS.onInstructionExecuted(IR);
   LLVM_DEBUG(dbgs() << "[E] Instruction Executed: #" << IR << '\n');
   notifyEvent<HWInstructionEvent>(
       HWInstructionEvent(HWInstructionEvent::Executed, IR));
-  RCU.onInstructionExecuted(IR.getInstruction()->getRCUTokenID());
 }
 
 void ExecuteStage::notifyInstructionReady(const InstRef &IR) {
   LLVM_DEBUG(dbgs() << "[E] Instruction Ready: #" << IR << '\n');
   notifyEvent<HWInstructionEvent>(
       HWInstructionEvent(HWInstructionEvent::Ready, IR));
 }
 

tools/llvm-mca/FetchStage.h

 #include "InstrBuilder.h"
 #include "SourceMgr.h"
 #include "Stage.h"
 #include <map>
 
 namespace mca {
 
 class FetchStage final : public Stage {
+  std::unique_ptr<Instruction> CurrentInstruction;
   using InstMap = std::map<unsigned, std::unique_ptr<Instruction>>;
   InstMap Instructions;
   InstrBuilder &IB;
   SourceMgr &SM;
 
+  // Updates the program counter, and sets 'CurrentInstruction'.
+  llvm::Error getNextInstruction();
+
   FetchStage(const FetchStage &Other) = delete;
   FetchStage &operator=(const FetchStage &Other) = delete;
 
 public:
-  FetchStage(InstrBuilder &IB, SourceMgr &SM) : IB(IB), SM(SM) {}
+  FetchStage(InstrBuilder &IB, SourceMgr &SM)
+      : CurrentInstruction(), IB(IB), SM(SM) {}
 
+  bool isAvailable(const InstRef &IR) const override;
   bool hasWorkToComplete() const override;
-  Status execute(InstRef &IR) override;
-  void postExecute() override;
+  llvm::Error execute(InstRef &IR) override;
+  llvm::Error cycleStart() override;
   llvm::Error cycleEnd() override;
 };
 
 } // 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::hasWorkToComplete() const { return SM.hasNext(); }
+bool FetchStage::hasWorkToComplete() const {
+  return CurrentInstruction.get() || SM.hasNext();
+}
+
+bool FetchStage::isAvailable(const InstRef & /* unused */) const {
+  if (!CurrentInstruction)
+    return false;
+  assert(SM.hasNext() && "Unexpected internal state!");
+  const SourceRef SR = SM.peekNext();
+  InstRef IR(SR.first, CurrentInstruction.get());
+  return checkNextStage(IR);
+}
 
-Stage::Status FetchStage::execute(InstRef &IR) {
+llvm::Error FetchStage::getNextInstruction() {
+  assert(!CurrentInstruction && "There is already an instruction to process!");
   if (!SM.hasNext())
-    return Stage::Stop;
+    return llvm::ErrorSuccess();
+
   const SourceRef SR = SM.peekNext();
   llvm::Expected<std::unique_ptr<Instruction>> InstOrErr =
       IB.createInstruction(*SR.second);
   if (!InstOrErr)
     return InstOrErr.takeError();
-  std::unique_ptr<Instruction> I = std::move(*InstOrErr);
-  IR = InstRef(SR.first, I.get());
-  Instructions[IR.getSourceIndex()] = std::move(I);
-  return Stage::Continue;
+  CurrentInstruction = std::move(InstOrErr.get());
+  return llvm::ErrorSuccess();
 }
 
-void FetchStage::postExecute() { SM.updateNext(); }
+llvm::Error FetchStage::execute(InstRef & /*unused */) {
+  assert(CurrentInstruction && "There is no instruction to process!");
+  const SourceRef SR = SM.peekNext();
+  InstRef IR(SR.first, CurrentInstruction.get());
+  assert(checkNextStage(IR) && "Invalid fetch!");
+
+  Instructions[IR.getSourceIndex()] = std::move(CurrentInstruction);
+  if (llvm::Error Val = moveToTheNextStage(IR))
+    return Val;
+
+  SM.updateNext();
+
+  // Move the program counter.
+  return getNextInstruction();
+}
+
+llvm::Error FetchStage::cycleStart() {
+  if (!CurrentInstruction && SM.hasNext())
+    return getNextInstruction();
+  return llvm::ErrorSuccess();
+}
 
 llvm::Error FetchStage::cycleEnd() {
   // Find the first instruction which hasn't been retired.
   const InstMap::iterator It =
       llvm::find_if(Instructions, [](const InstMap::value_type &KeyValuePair) {
         return !KeyValuePair.second->isRetired();
       });
 
   // Erase instructions up to the first that hasn't been retired.
   if (It != Instructions.begin())
     Instructions.erase(Instructions.begin(), It);
 
   return llvm::ErrorSuccess();
 }
 
 } // namespace mca

tools/llvm-mca/InstructionTables.h

 #include "Scheduler.h"
 #include "Stage.h"
 #include "View.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/MC/MCSchedule.h"
 
 namespace mca {
 
-class InstructionTables : public Stage {
+class InstructionTables final : public Stage {
   const llvm::MCSchedModel &SM;
   InstrBuilder &IB;
   llvm::SmallVector<std::pair<ResourceRef, double>, 4> UsedResources;
 
 public:
   InstructionTables(const llvm::MCSchedModel &Model, InstrBuilder &Builder)
       : Stage(), SM(Model), IB(Builder) {}
 
-  bool hasWorkToComplete() const override final { return false; }
-  Status execute(InstRef &IR) override final;
+  bool hasWorkToComplete() const override { return false; }
+  llvm::Error execute(InstRef &IR) override;
 };
 } // namespace mca
 
 #endif

tools/llvm-mca/InstructionTables.cpp

 //===----------------------------------------------------------------------===//
 
 #include "InstructionTables.h"
 
 namespace mca {
 
 using namespace llvm;
 
-Stage::Status InstructionTables::execute(InstRef &IR) {
+Error InstructionTables::execute(InstRef &IR) {
   ArrayRef<uint64_t> Masks = IB.getProcResourceMasks();
   const InstrDesc &Desc = IR.getInstruction()->getDesc();
   UsedResources.clear();
 
   // 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())
for (unsigned I1 = 0; I1 < NumUnits; ++I1) {
         UsedResources.emplace_back(std::make_pair(ResourceUnit, RUCycles));
       }
     }
   }
 
   // Send a fake instruction issued event to all the views.
   HWInstructionIssuedEvent Event(IR, UsedResources);
   notifyEvent<HWInstructionIssuedEvent>(Event);
-  return Stage::Continue;
+  return ErrorSuccess();
 }
 
 } // namespace mca

tools/llvm-mca/Pipeline.h

class Pipeline {
   Pipeline(const Pipeline &P) = delete;
   Pipeline &operator=(const Pipeline &P) = delete;
 
   /// An ordered list of stages that define this instruction pipeline.
   llvm::SmallVector<std::unique_ptr<Stage>, 8> Stages;
   std::set<HWEventListener *> Listeners;
   unsigned Cycles;
 
-  void preExecuteStages();
-  Stage::Status executeStages(InstRef &IR);
-  void postExecuteStages();
   llvm::Error runCycle();
-
   bool hasWorkToProcess();
   void notifyCycleBegin();
   void notifyCycleEnd();
 
 public:
   Pipeline() : Cycles(0) {}
-  void appendStage(std::unique_ptr<Stage> S) { Stages.push_back(std::move(S)); }
+  void appendStage(std::unique_ptr<Stage> S);
   llvm::Error run();
   void addEventListener(HWEventListener *Listener);
 };
 } // namespace mca
 
 #endif // LLVM_TOOLS_LLVM_MCA_PIPELINE_H

tools/llvm-mca/Pipeline.cpp

 }
 
 bool Pipeline::hasWorkToProcess() {
   return llvm::any_of(Stages, [](const std::unique_ptr<Stage> &S) {
     return S->hasWorkToComplete();
   });
 }
 
-// This routine returns early if any stage returns 'false' after execute() is
-// called on it.
-Stage::Status Pipeline::executeStages(InstRef &IR) {
-  for (const std::unique_ptr<Stage> &S : Stages) {
-    Stage::Status StatusOrErr = S->execute(IR);
-    if (!StatusOrErr)
-      return StatusOrErr.takeError();
-    else if (StatusOrErr.get() == Stage::Stop)
-      return Stage::Stop;
-  }
-  return Stage::Continue;
-}
-
-void Pipeline::preExecuteStages() {
-  for (const std::unique_ptr<Stage> &S : Stages)
-    S->preExecute();
-}
-
-void Pipeline::postExecuteStages() {
-  for (const std::unique_ptr<Stage> &S : Stages)
-    S->postExecute();
-}
-
 llvm::Error Pipeline::run() {
   assert(!Stages.empty() && "Unexpected empty pipeline found!");
 
   while (hasWorkToProcess()) {
     notifyCycleBegin();
     if (llvm::Error Err = runCycle())
       return Err;
     notifyCycleEnd();
     ++Cycles;
   }
   return llvm::ErrorSuccess();
 }
 
 llvm::Error Pipeline::runCycle() {
-  // Update stages before we start processing new instructions.
   llvm::Error Err = llvm::ErrorSuccess();
-  for (auto I = Stages.begin(), E = Stages.end(); I != E && !Err; ++I) {
+  // Update stages before we start processing new instructions.
+  for (auto I = Stages.rbegin(), E = Stages.rend(); I != E && !Err; ++I) {
     const std::unique_ptr<Stage> &S = *I;
     Err = S->cycleStart();
   }
 
-  if (Err)
-    return Err;
-
   // Now fetch and execute new instructions.
   InstRef IR;
-  while (true) {
-    preExecuteStages();
-    Stage::Status Val = executeStages(IR);
-    if (!Val)
-      return Val.takeError();
-    if (Val.get() == Stage::Stop)
-      break;
-    postExecuteStages();
-  }
+  Stage &FirstStage = *Stages[0];
+  while (!Err && FirstStage.isAvailable(IR))
+    Err = FirstStage.execute(IR);
 
   // Update stages in preparation for a new cycle.
-  for (auto I = Stages.begin(), E = Stages.end(); I != E && !Err; ++I) {
+  for (auto I = Stages.rbegin(), E = Stages.rend(); I != E && !Err; ++I) {
     const std::unique_ptr<Stage> &S = *I;
     Err = S->cycleEnd();
   }
+
   return Err;
 }
 
+void Pipeline::appendStage(std::unique_ptr<Stage> S) {
+  assert(S && "Invalid null stage in input!");
+  if (!Stages.empty()) {
+    Stage *Last = Stages.back().get();
+    Last->setNextInSequence(S.get());
+  }
+
+  Stages.push_back(std::move(S));
+}
+
 void Pipeline::notifyCycleBegin() {
   LLVM_DEBUG(dbgs() << "[E] Cycle begin: " << Cycles << '\n');
   for (HWEventListener *Listener : Listeners)
     Listener->onCycleBegin();
 }
 
 void Pipeline::notifyCycleEnd() {
   LLVM_DEBUG(dbgs() << "[E] Cycle end: " << Cycles << "\n\n");
   for (HWEventListener *Listener : Listeners)
     Listener->onCycleEnd();
 }
 } // namespace mca.

tools/llvm-mca/RetireStage.h

class RetireStage final : public Stage {
   RetireStage &operator=(const RetireStage &Other) = delete;
 
 public:
   RetireStage(RetireControlUnit &R, RegisterFile &F)
       : Stage(), RCU(R), PRF(F) {}
 
   bool hasWorkToComplete() const override { return !RCU.isEmpty(); }
   llvm::Error cycleStart() override;
-  Status execute(InstRef &IR) override { return Stage::Continue; }
+  llvm::Error execute(InstRef &IR) override;
   void notifyInstructionRetired(const InstRef &IR);
-  void onInstructionExecuted(unsigned TokenID);
 };
 
 } // namespace mca
 
 #endif // LLVM_TOOLS_LLVM_MCA_RETIRE_STAGE_H

tools/llvm-mca/RetireStage.cpp

while (!RCU.isEmpty()) {
     RCU.consumeCurrentToken();
     notifyInstructionRetired(Current.IR);
     NumRetired++;
   }
 
   return llvm::ErrorSuccess();
 }
 
+llvm::Error RetireStage::execute(InstRef &IR) {
+  RCU.onInstructionExecuted(IR.getInstruction()->getRCUTokenID());
+  return llvm::ErrorSuccess();
+}
+
 void RetireStage::notifyInstructionRetired(const InstRef &IR) {
   LLVM_DEBUG(llvm::dbgs() << "[E] Instruction Retired: #" << IR << '\n');
   llvm::SmallVector<unsigned, 4> FreedRegs(PRF.getNumRegisterFiles());
   const Instruction &Inst = *IR.getInstruction();
   const InstrDesc &Desc = Inst.getDesc();
 
   bool ShouldFreeRegs = !(Desc.isZeroLatency() && Inst.isDependencyBreaking());
   for (const std::unique_ptr<WriteState> &WS : Inst.getDefs())
     PRF.removeRegisterWrite(*WS.get(), FreedRegs, ShouldFreeRegs);
   notifyEvent<HWInstructionEvent>(HWInstructionRetiredEvent(IR, FreedRegs));
 }
 
 } // namespace mca

tools/llvm-mca/Stage.h

 #include "llvm/Support/Error.h"
 #include <set>
 
 namespace mca {
 
 class InstRef;
 
 class Stage {
+  Stage *NextInSequence;
   std::set<HWEventListener *> Listeners;
 
   Stage(const Stage &Other) = delete;
   Stage &operator=(const Stage &Other) = delete;
 
-public:
-  /// A Stage's execute() returns Continue, Stop, or an error.  Returning
-  /// Continue means that the stage successfully completed its 'execute'
-  /// action, and that the instruction being processed can be moved to the next
-  /// pipeline stage during this cycle.  Continue allows the pipeline to
-  /// continue calling 'execute' on subsequent stages.  Returning Stop
-  /// signifies that the stage ran into an error, and tells the pipeline to stop
-  /// passing the instruction to subsequent stages during this cycle.  Any
-  /// failures that occur during 'execute' are represented by the error variant
-  /// that is provided by the Expected template.
-  enum State { Stop, Continue };
-  using Status = llvm::Expected<State>;
-
 protected:
   const std::set<HWEventListener *> &getListeners() const { return Listeners; }
 
 public:
-  Stage() {}
+  Stage() : NextInSequence(nullptr) {}
   virtual ~Stage();
 
-  /// 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.
+  /// Returns true if it can execute IR during this cycle.
+  virtual bool isAvailable(const InstRef &IR) const { return true; }
+
+  /// Returns true if some instructions are still executing this stage.
   virtual bool hasWorkToComplete() const = 0;
 
   /// Called once at the start of each cycle.  This can be used as a setup
   /// phase to prepare for the executions during the cycle.
   virtual llvm::Error cycleStart() { return llvm::ErrorSuccess(); }
 
   /// Called once at the end of each cycle.
   virtual llvm::Error cycleEnd() { return llvm::ErrorSuccess(); }
 
-  /// Called prior to executing the list of stages.
-  /// This can be called multiple times per cycle.
-  virtual void preExecute() {}
-
-  /// Called as a cleanup and finalization phase after each execution.
-  /// This will only be called if all stages return a success from their
-  /// execute callback.  This can be called multiple times per cycle.
-  virtual void postExecute() {}
-
-  /// The primary action that this stage performs.
-  /// Returning false prevents successor stages from having their 'execute'
-  /// routine called.  This can be called multiple times during a single cycle.
-  virtual Status execute(InstRef &IR) = 0;
+  /// The primary action that this stage performs on instruction IR.
+  virtual llvm::Error execute(InstRef &IR) = 0;
+
+  void setNextInSequence(Stage *NextStage) {
+    NextInSequence = NextStage;
+  }
+
+  bool checkNextStage(const InstRef &IR) const {
+    return NextInSequence && NextInSequence->isAvailable(IR);
+  }
+
+  /// Called when an instruction is ready to move the next stage of the
+  /// pipeline. 
+  llvm::Error moveToTheNextStage(InstRef &IR) {
+    assert(checkNextStage(IR) && "Next stage is not ready!");
+    return std::move(NextInSequence->execute(IR));
+  }
 
   /// Add a listener to receive callbacks during the execution of this stage.
   void addListener(HWEventListener *Listener);
 
   /// Notify listeners of a particular hardware event.
   template <typename EventT> void notifyEvent(const EventT &Event) const {
     for (HWEventListener *Listener : Listeners)
       Listener->onEvent(Event);
   }
 };
 
 } // namespace mca
 #endif // LLVM_TOOLS_LLVM_MCA_STAGE_H