[MCA] Introducing incremental SourceMgr and resumable pipeline

[myhsu]

Summary

The new resumable mca::Pipeline capability introduced in this patch allows users to save the current state of pipeline and resume from the very checkpoint.
It is better (but not require) to use with the new IncrementalSourceMgr, where users can add mca::Instruction incrementally rather than having a fixed number of instructions ahead-of-time.

Note that we're using unit tests to test these new features. Because integrating them into the llvm-mca tool will make too many churns.

This is patch 1/2 of MCA Daemon's upstreaming efforts.

[andreadb]

Hi Min,

Thanks for this patch. I have just started looking at it. I left a few comments inline.

Thanks!

llvm/include/llvm/MCA/Pipeline.h

54

Can you use an enum class here?

llvm/include/llvm/MCA/SourceMgr.h

26–59

This is not ideal, but I can't think of any other obvious way to avoid this refactoring.

Did you notice a perf regression after this change on normal llvm-mca runs with several iterations?

I wonder if you could make SourceMgr a template class, and have it specialised based on whether you want a "circular buffer" behaviour or not.

Ideally, class SourceMgr should only be visible to the so-called pipeline entry stage(s). In llvm-mca there are two default entry stages: EntryStage (for the out-of-order pipeline) and InOrderIssueStage (for the in-order pipeline). Any other module should not use SourceMgr; for those modules, the input assembly sequence can often be easily abstracted using an ArrayRef<MCInst>. This is for example what we do in some Views.

That being said, I am seeing uses of SourceMgr in the CustomBehaviour API. For example, AMDGPU uses a CustomBehaviour to get access to the immutable MCInst sequence and simply iterate over the MCInst. This might have been an oversight/poor design choice from our end, since we don't seem to really need any of the extra SourceMgr functionalities in CustomBehaviour. In fact, passing an ArrayRef<MCInst> would be enough (at least for the AMDGPU).
'
In retrospect, I wonder whether there was a reason for that choice.
@holland11 Would it cause problems if we changed the CustomBehaviour constructor so that it accepts an ArrayRef<MCInst> instead of a SourceMgr? Do you remember why we needed it?

32–34

Is there a reason why you want to add this method?

[andreadb]

llvm/include/llvm/MCA/Stages/Stage.h

21

Is there a reason why you use <system_error> for your new Error type?

[holland11]

Out of curiosity, what is one of the motivating use cases for this?

As far as reviewing goes, I haven't been actively involved in mca enough lately to consider my opinions or input of much value, but I appreciate being notified of these PRs so that I can learn from them :).

[myhsu]

Thank you for your comments. The SourceMgr performance regression is pretty interesting, I'll look deep into that.
Meanwhile, I just fixed some minor issues first.

llvm/include/llvm/MCA/SourceMgr.h

26–59

This is not ideal, but I can't think of any other obvious way to avoid this refactoring.

Did you notice a perf regression after this change on normal llvm-mca runs with several iterations?

Interesting...I haven't done such measurement and I didn't know vtable dispatching in this case would cause noticeable regression. I'll look into it.

I wonder if you could make SourceMgr a template class, and have it specialised based on whether you want a "circular buffer" behaviour or not.

Right, if vtable is the bottleneck here, another similar solution can be:

template <class SubClass> SourceMgr {
  bool hasNext() const {
    return static_cast<const SubClass *>(this)->hasNext();
  }
};

class MySourceMgr : public SourceMgr<MySourceMgr> {
  bool hasNext() const { /*not a virtual function*/ }
};

Then consumers of SourceMgr need to accept something with a template. Which is not a big problem if we only use it in few places (i.e. less fiddling with template arguments) so I'm with the idea you put below to limit as many SourceMgr usages as possible, for instance in CustomBehavior. That said, for EntryStage and InOrderIssueStage, we need to move lots of code from .cpp file to the header file since we're taking template version of SourceMgr, I'm wondering what's your thoughts about this?

Ideally, class SourceMgr should only be visible to the so-called pipeline entry stage(s). In llvm-mca there are two default entry stages: EntryStage (for the out-of-order pipeline) and InOrderIssueStage (for the in-order pipeline). Any other module should not use SourceMgr; for those modules, the input assembly sequence can often be easily abstracted using an ArrayRef<MCInst>. This is for example what we do in some Views.

Sounds reasonable to me.

That being said, I am seeing uses of SourceMgr in the CustomBehaviour API. For example, AMDGPU uses a CustomBehaviour to get access to the immutable MCInst sequence and simply iterate over the MCInst. This might have been an oversight/poor design choice from our end, since we don't seem to really need any of the extra SourceMgr functionalities in CustomBehaviour. In fact, passing an ArrayRef<MCInst> would be enough (at least for the AMDGPU).
'
In retrospect, I wonder whether there was a reason for that choice.
@holland11 Would it cause problems if we changed the CustomBehaviour constructor so that it accepts an ArrayRef<MCInst> instead of a SourceMgr? Do you remember why we needed it?

32–34

Originally we were using begin/end methods here, but with the current scheme (i.e. SourceMgr as an abstract class) it's easier to have such getInstructions rather than worry about types for the iterator (returning from begin/end) -- It's not impossible to use begin/end, it's just easier to returning an ArrayRef. Also, it works just fine with current usages. Do you think it's better to use begin/end instead?

llvm/include/llvm/MCA/Stages/Stage.h

21

I didn't know there is llvm::inconvertibleErrorCode() when I first wrote this code. I'll change to use inconvertibleErrorCode() instead.

[myhsu]

In D127083#3561083, @holland11 wrote:

Out of curiosity, what is one of the motivating use cases for this?

These changes are originated from a downstream project which tries use MCA in a larger scale but observed some difficulties on flexibility as well as increasing memory footprint when the input size is big. This patch (and the following one) upstream some of the improvements on those issues because we think making MCA more scalable and versatile is generally a good idea. There might be some community members with a similar need, too. Here is the full story: https://youtu.be/ZGEP7JEIKNo

As far as reviewing goes, I haven't been actively involved in mca enough lately to consider my opinions or input of much value, but I appreciate being notified of these PRs so that I can learn from them :).

[myhsu]

Did you notice a perf regression after this change on normal llvm-mca runs with several iterations?

Following up on the potential performance regression caused by abstracting away SourceMgr, here is my experiment:

• Baseline SHA: 8f7b14898fe32f9c41059517a5a3872ef089174b
• Host arch / OS: Core i7-8700K / Ubuntu 20.04
• MCA command: llvm-mca -mcpu=btver2 -mtriple=x86_64-unknown-linux /path/to/llvm-project/llvm/test/tools/llvm-mca/X86/BtVer2/resources-sse2.s -o /dev/null
• Perf command: perf stat --repeat=1000 -- <MCA command>

Here are the baseline numbers:

      48.43 msec task-clock                #    0.997 CPUs utilized            ( +-  0.08% )
          0      context-switches          #    0.008 K/sec                    ( +-  7.25% )
          0      cpu-migrations            #    0.000 K/sec                  
        767      page-faults               #    0.016 M/sec                    ( +-  0.01% )
220,767,126      cycles                    #    4.558 GHz                      ( +-  0.01% )
477,655,890      instructions              #    2.16  insn per cycle           ( +-  0.00% )
112,417,237      branches                  # 2321.072 M/sec                    ( +-  0.00% )
  1,266,955      branch-misses             #    1.13% of all branches          ( +-  0.02% )

  0.0485851 +- 0.0000370 seconds time elapsed  ( +-  0.08% )

Here are the numbers after this particular patch is applied:

      47.90 msec task-clock                #    0.997 CPUs utilized            ( +-  0.07% )
          0      context-switches          #    0.003 K/sec                    ( +-  7.75% )
          0      cpu-migrations            #    0.000 K/sec                  
        762      page-faults               #    0.016 M/sec                    ( +-  0.01% )
220,706,375      cycles                    #    4.608 GHz                      ( +-  0.01% )
479,569,839      instructions              #    2.17  insn per cycle           ( +-  0.00% )
112,961,518      branches                  # 2358.488 M/sec                    ( +-  0.00% )
  1,261,302      branch-misses             #    1.12% of all branches          ( +-  0.02% )

  0.0480387 +- 0.0000322 seconds time elapsed  ( +-  0.07% )

If we look into the number of instructions, a more stable metric, there is an increase on that, but it only accounts about 0.4%.

[andreadb]

In D127083#3561836, @myhsu wrote:

Did you notice a perf regression after this change on normal llvm-mca runs with several iterations?

Following up on the potential performance regression caused by abstracting away SourceMgr, here is my experiment:
<snip>

If we look into the number of instructions, a more stable metric, there is an increase on that, but it only accounts about 0.4%.

That's great thanks.

If that's the case, then I am less worried about using a base class with just pure virtual methods.

llvm/include/llvm/MCA/SourceMgr.h

32–34

In principle, I prefer using ArrayRef instead using begin/end iterators.

The only problem with ArrayRef (at least in this context) is that it assumes that the underlying data structure in SourceMgr can be seen as an array-like struct.

In your patch, the std::deque breaks that assumption. As the docs say, std::deque doesn't guarantee that elements are stored contiguously.

For that reason, having that method returning an ArrayRef is a bit limiting.
Ideally, what you really want is the ability to return an "iterator range".

I noticed that llvm provides a class iterator_range. Maybe using an llvm::iterator_range could be a compromise?

[myhsu]

llvm/include/llvm/MCA/SourceMgr.h

32–34

In your patch, the std::deque breaks that assumption. As the docs say, std::deque doesn't guarantee that elements are stored contiguously.

Correct, though IncrementalSourceMgr::getInstructions will eventually be marked as unimplemented / not applicable. Because when the users decide to recycle instructions, it's really hard to return a meaningful sequence of instructions. That said, we can still return the sequence of instructions stored in InstStorage anyway as a best-effort result.

Ideally, what you really want is the ability to return an "iterator range".

Agree, though this goes back to a previous concern where we need to abstract away the type of iterator (as iterator_range still takes the type of iterator as its template argument). I will do some explorations on this topic.

[andreadb]

Hi Min,

llvm/include/llvm/MCA/SourceMgr.h

32–34

Right. I see the problem.

If you can't find anything better, then your current approach (i.e. marking getInstructions as unimplemented) looks good to me.

I don't have any other requests.

Thanks!

[myhsu]

Thank you @andreadb !
It will be great if you can help me review the follow-up patch, D127084, which implement the instruction recycling feature.

[andreadb]

In D127083#3573746, @myhsu wrote:

Thank you @andreadb !
It will be great if you can help me review the follow-up patch, D127084, which implement the instruction recycling feature.

Sure,

I'll review that patch too.

-Andrea

[hubert.reinterpretcast]

llvm/unittests/tools/llvm-mca/MCATestBase.cpp

85

This is causing failures:
https://lab.llvm.org/buildbot/#/builders/57/builds/19267

/home/buildbots/docker-RHEL-buildbot/SetupBot/worker_env/ppc64le-clang-rhel-test/clang-ppc64le-rhel/llvm-project/llvm/unittests/tools/llvm-mca/MCATestBase.cpp:85:16: error: moving a local object in a return statement prevents copy elision [-Werror,-Wpessimizing-move]
        return std::move(NewE);
               ^
/home/buildbots/docker-RHEL-buildbot/SetupBot/worker_env/ppc64le-clang-rhel-test/clang-ppc64le-rhel/llvm-project/llvm/unittests/tools/llvm-mca/MCATestBase.cpp:85:16: note: remove std::move call here
        return std::move(NewE);
               ^~~~~~~~~~    ~
1 error generated.

[thakis]

llvm/unittests/tools/llvm-mca/CMakeLists.txt

26

Why is this file so complicated? All other CMakeLists.txt in llvm/unittests are very simple.

It kind of looks like this links in some, but not all, code in tools/llvm-mca/Views in to the test, instead of doing a library-level dependency. That seems
a) strange from a layering PoV
b) ODR-violation-prone in the future

Why is this designed the way it is, instead of more like all the other tests?

[thakis]

llvm/unittests/tools/llvm-mca/CMakeLists.txt

26

For example, the llvm/unittests/tools/llvm-exegesis/* does something somewhat similar (…I think?) with much less machinery, by having a test binary per target. Could that design work here?

[thakis]

llvm/unittests/tools/llvm-mca/X86/CMakeLists.txt

3

(But, similar to the llvm-exegesis tests, it's weird that this depends on internals of the X86 target. llvm-exegesis "at least" makes this choice at the tool level, but here it's only the test that does this. Is there a way to instead use the public API instead of depending on internal headers of lib/Target/X86?)

[myhsu]

llvm/unittests/tools/llvm-mca/CMakeLists.txt

26

This file is taking references from unittest/tools/llvm-exegesis/CMakeLists.txt (which is actually more complicated than this one) because llvm-mca has a similar need with llvm-exegesis.

The rationale behind this is that we want to build in-memory MCInst objects as the test input (which requires target specific header files) for a simpler test harness.
That said, I think moving files under tools/llvm-mca/Views into include/llvm/MCA/Views (and its lib/MCA counterpart) is a good future idea @andreadb what do you think?

llvm/unittests/tools/llvm-mca/MCATestBase.cpp

85

Sorry for that, will be fixed shortly...

[myhsu]

llvm/unittests/tools/llvm-mca/CMakeLists.txt

26

For example, the llvm/unittests/tools/llvm-exegesis/* does something somewhat similar (…I think?) with much less machinery, by having a test binary per target. Could that design work here?

I don't think so, there is only a single test binary, LLVMExegesisTests, same as us. We also assigned each target a folder (currently there is only X86).

[thakis]

llvm/unittests/tools/llvm-mca/CMakeLists.txt

26

Oh I see, I hadn't seen D106464. I agree that this is similar to what llvm-exegesis's tests now do, thanks.

(It'd still be nice to randomly pull in files from llvm-mca/Views.)

[myhsu]

llvm/unittests/tools/llvm-mca/MCATestBase.cpp

85

Fixed in rG1f62e245e68d

llvm/include/llvm/MCA/IncrementalSourceMgr.h

+//===---------------- IncrementalSourceMgr.h --------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// This file contains IncrementalSourceMgr, an implementation of SourceMgr
+/// that allows users to add new instructions incrementally / dynamically.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_MCA_INCREMENTALSOURCEMGR_H
+#define LLVM_MCA_INCREMENTALSOURCEMGR_H
+
+#include "llvm/MCA/SourceMgr.h"
+#include <deque>
+
+namespace llvm {
+namespace mca {
+
+/// An implementation of \a SourceMgr that allows users to add new instructions
+/// incrementally / dynamically.
+/// Note that this SourceMgr takes ownership of all \a mca::Instruction.
+class IncrementalSourceMgr : public SourceMgr {
+  /// Owner of all mca::Instruction instances. Note that we use std::deque here
+  /// to have a better throughput, in comparison to std::vector or
+  /// llvm::SmallVector, as they usually pay a higher re-allocation cost when
+  /// there is a large number of instructions.
+  std::deque<UniqueInst> InstStorage;
+
+  /// Current instruction index.
+  unsigned TotalCounter;
+
+  /// End-of-stream flag.
+  bool EOS;
+
+public:
+  IncrementalSourceMgr() : TotalCounter(0U), EOS(false) {}
+
+  void clear() {
+    InstStorage.clear();
+    TotalCounter = 0U;
+    EOS = false;
+  }
+
+  ArrayRef<UniqueInst> getInstructions() const override {
+    llvm_unreachable("Not applicable");
+  }
+
+  bool hasNext() const override { return TotalCounter < InstStorage.size(); }
+  bool isEnd() const override { return EOS; }
+
+  SourceRef peekNext() const override {
+    assert(hasNext());
+    return SourceRef(TotalCounter, *InstStorage[TotalCounter]);
+  }
+
+  /// Add a new instruction.
+  void addInst(UniqueInst &&Inst) { InstStorage.emplace_back(std::move(Inst)); }
+
+  void updateNext() override { ++TotalCounter; }
+
+  /// Mark the end of instruction stream.
+  void endOfStream() { EOS = true; }
+};
+
+} // end namespace mca
+} // end namespace llvm
+
+#endif // LLVM_MCA_INCREMENTALSOURCEMGR_H

llvm/include/llvm/MCA/Pipeline.h

 ///
 /// Internally, the Pipeline collects statistical information in the form of
 /// histograms. For example, it tracks how the dispatch group size changes
 /// over time.
 class Pipeline {
   Pipeline(const Pipeline &P) = delete;
   Pipeline &operator=(const Pipeline &P) = delete;
 
+  enum class State {
+    Created, // Pipeline was just created. The default state.
+    Started, // Pipeline has started running.
+    Paused   // Pipeline is paused.
+  };
+  State CurrentState;
+
   /// An ordered list of stages that define this instruction pipeline.
   SmallVector<std::unique_ptr<Stage>, 8> Stages;
   std::set<HWEventListener *> Listeners;
   unsigned Cycles;
 
   Error runCycle();
   bool hasWorkToProcess();
   void notifyCycleBegin();
   void notifyCycleEnd();
 
 public:
-  Pipeline() : Cycles(0) {}
+  Pipeline() : CurrentState(State::Created), Cycles(0) {}
   void appendStage(std::unique_ptr<Stage> S);
 
   /// Returns the total number of simulated cycles.
   Expected<unsigned> run();
 
   void addEventListener(HWEventListener *Listener);
+
+  /// Returns whether the pipeline is currently paused.
+  bool isPaused() const { return CurrentState == State::Paused; }
 };
 } // namespace mca
 } // namespace llvm
 
 #endif // LLVM_MCA_PIPELINE_H

llvm/include/llvm/MCA/SourceMgr.h

 //===--------------------- SourceMgr.h --------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
-/// This file implements class SourceMgr. Class SourceMgr abstracts the input
-/// code sequence (a sequence of MCInst), and assings unique identifiers to
-/// every instruction in the sequence.
+/// This file contains abstract class SourceMgr and the default implementation,
+/// CircularSourceMgr.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_MCA_SOURCEMGR_H
 #define LLVM_MCA_SOURCEMGR_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/MCA/Instruction.h"
 
 namespace llvm {
 namespace mca {
 
 // MSVC >= 19.15, < 19.20 need to see the definition of class Instruction to
 // prevent compiler error C2139 about intrinsic type trait '__is_assignable'.
 typedef std::pair<unsigned, const Instruction &> SourceRef;
 
-class SourceMgr {
+/// Abstracting the input code sequence (a sequence of MCInst) and assigning
+/// unique identifiers to every instruction in the sequence.
+struct SourceMgr {
   using UniqueInst = std::unique_ptr<Instruction>;
+
+  /// Provides a fixed range of \a UniqueInst to iterate.
+  virtual ArrayRef<UniqueInst> getInstructions() const = 0;
+
+  /// (Fixed) Number of \a UniqueInst. Returns the size of
+  /// \a getInstructions by default.
+  virtual size_t size() const { return getInstructions().size(); }
+
+  /// Whether there is any \a SourceRef to inspect / peek next.
+  /// Note that returning false from this doesn't mean the instruction
+  /// stream has ended.
+  virtual bool hasNext() const = 0;
+
+  /// Whether the instruction stream has eneded.
+  virtual bool isEnd() const = 0;
+
+  /// The next \a SourceRef.
+  virtual SourceRef peekNext() const = 0;
+
+  /// Advance to the next \a SourceRef.
+  virtual void updateNext() = 0;
+
+  virtual ~SourceMgr() {}
+};
+
+/// The default implementation of \a SourceMgr. It always takes a fixed number
+/// of instructions and provides an option to loop the given sequence for a
+/// certain iterations.
+class CircularSourceMgr : public SourceMgr {
   ArrayRef<UniqueInst> Sequence;
   unsigned Current;
   const unsigned Iterations;
   static const unsigned DefaultIterations = 100;
 
 public:
-  SourceMgr(ArrayRef<UniqueInst> S, unsigned Iter)
-      : Sequence(S), Current(0), Iterations(Iter ? Iter : DefaultIterations) {}
+  CircularSourceMgr(ArrayRef<UniqueInst> S, unsigned Iter)
+      : Sequence(S), Current(0U), Iterations(Iter ? Iter : DefaultIterations) {}
+
+  ArrayRef<UniqueInst> getInstructions() const override { return Sequence; }
 
   unsigned getNumIterations() const { return Iterations; }
-  unsigned size() const { return Sequence.size(); }
-  bool hasNext() const { return Current < (Iterations * Sequence.size()); }
-  void updateNext() { ++Current; }
+  bool hasNext() const override {
+    return Current < (Iterations * Sequence.size());
+  }
+  bool isEnd() const override { return !hasNext(); }
 
-  SourceRef peekNext() const {
+  SourceRef peekNext() const override {
     assert(hasNext() && "Already at end of sequence!");
     return SourceRef(Current, *Sequence[Current % Sequence.size()]);
   }
 
-  using const_iterator = ArrayRef<UniqueInst>::const_iterator;
-  const_iterator begin() const { return Sequence.begin(); }
-  const_iterator end() const { return Sequence.end(); }
+  void updateNext() override { ++Current; }
 };
 
 } // namespace mca
 } // namespace llvm
 
 #endif // LLVM_MCA_SOURCEMGR_H

llvm/include/llvm/MCA/Stages/EntryStage.h

 
 class EntryStage final : public Stage {
   InstRef CurrentInstruction;
   SmallVector<std::unique_ptr<Instruction>, 16> Instructions;
   SourceMgr &SM;
   unsigned NumRetired;
 
   // Updates the program counter, and sets 'CurrentInstruction'.
-  void getNextInstruction();
+  Error getNextInstruction();
 
   EntryStage(const EntryStage &Other) = delete;
   EntryStage &operator=(const EntryStage &Other) = delete;
 
 public:
   EntryStage(SourceMgr &SM) : SM(SM), NumRetired(0) {}
 
   bool isAvailable(const InstRef &IR) const override;
   bool hasWorkToComplete() const override;
   Error execute(InstRef &IR) override;
   Error cycleStart() override;
+  Error cycleResume() override;
   Error cycleEnd() override;
 };
 
 } // namespace mca
 } // namespace llvm
 
 #endif // LLVM_MCA_STAGES_ENTRYSTAGE_H

llvm/include/llvm/MCA/Stages/Stage.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_MCA_STAGES_STAGE_H
 #define LLVM_MCA_STAGES_STAGE_H
 
 #include "llvm/MCA/HWEventListener.h"
 #include "llvm/Support/Error.h"
 #include <set>
 
 namespace llvm {
 namespace mca {
 
 class InstRef;
 
 class Stage {
   Stage *NextInSequence;
   std::set<HWEventListener *> Listeners;
public:
 
   /// 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 Error cycleStart() { return ErrorSuccess(); }
 
+  /// Called after the pipeline is resumed from pausing state.
+  virtual Error cycleResume() { return ErrorSuccess(); }
+
   /// Called once at the end of each cycle.
   virtual Error cycleEnd() { return ErrorSuccess(); }
 
   /// The primary action that this stage performs on instruction IR.
   virtual Error execute(InstRef &IR) = 0;
 
   void setNextInSequence(Stage *NextStage) {
     assert(!NextInSequence && "This stage already has a NextInSequence!");
public:
 
   /// Notify listeners of a particular hardware event.
   template <typename EventT> void notifyEvent(const EventT &Event) const {
     for (HWEventListener *Listener : Listeners)
       Listener->onEvent(Event);
   }
 };
 
+/// This is actually not an error but a marker to indicate that
+/// the instruction stream is paused.
+struct InstStreamPause : public ErrorInfo<InstStreamPause> {
+  static char ID;
+
+  std::error_code convertToErrorCode() const override {
+    return llvm::inconvertibleErrorCode();
+  }
+  void log(raw_ostream &OS) const override { OS << "Stream is paused"; }
+};
 } // namespace mca
 } // namespace llvm
 #endif // LLVM_MCA_STAGES_STAGE_H

llvm/lib/MCA/Pipeline.cpp

return any_of(Stages, [](const std::unique_ptr<Stage> &S) {
     return S->hasWorkToComplete();
   });
 }
 
 Expected<unsigned> Pipeline::run() {
   assert(!Stages.empty() && "Unexpected empty pipeline found!");
 
   do {
+    if (!isPaused())
       notifyCycleBegin();
     if (Error Err = runCycle())
       return std::move(Err);
     notifyCycleEnd();
     ++Cycles;
   } while (hasWorkToProcess());
 
   return Cycles;
 }
 
 Error Pipeline::runCycle() {
   Error Err = ErrorSuccess();
   // 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;
+    if (isPaused())
+      Err = S->cycleResume();
+    else
       Err = S->cycleStart();
   }
 
+  CurrentState = State::Started;
+
   // Now fetch and execute new instructions.
   InstRef IR;
   Stage &FirstStage = *Stages[0];
   while (!Err && FirstStage.isAvailable(IR))
     Err = FirstStage.execute(IR);
 
+  if (Err.isA<InstStreamPause>()) {
+    CurrentState = State::Paused;
+    return Err;
+  }
+
   // Update stages in preparation for a new cycle.
   for (const std::unique_ptr<Stage> &S : Stages) {
     Err = S->cycleEnd();
     if (Err)
       break;
   }
 
   return Err;

llvm/lib/MCA/Stages/EntryStage.cpp

 
 #include "llvm/MCA/Stages/EntryStage.h"
 #include "llvm/MCA/Instruction.h"
 
 namespace llvm {
 namespace mca {
 
 bool EntryStage::hasWorkToComplete() const {
-  return static_cast<bool>(CurrentInstruction);
+  return static_cast<bool>(CurrentInstruction) || !SM.isEnd();
 }
 
 bool EntryStage::isAvailable(const InstRef & /* unused */) const {
   if (CurrentInstruction)
     return checkNextStage(CurrentInstruction);
   return false;
 }
 
-void EntryStage::getNextInstruction() {
+Error EntryStage::getNextInstruction() {
   assert(!CurrentInstruction && "There is already an instruction to process!");
-  if (!SM.hasNext())
-    return;
+  if (!SM.hasNext()) {
+    if (!SM.isEnd())
+      return llvm::make_error<InstStreamPause>();
+    else
+      return llvm::ErrorSuccess();
+  }
   SourceRef SR = SM.peekNext();
   std::unique_ptr<Instruction> Inst = std::make_unique<Instruction>(SR.second);
   CurrentInstruction = InstRef(SR.first, Inst.get());
   Instructions.emplace_back(std::move(Inst));
   SM.updateNext();
+  return llvm::ErrorSuccess();
 }
 
 llvm::Error EntryStage::execute(InstRef & /*unused */) {
   assert(CurrentInstruction && "There is no instruction to process!");
   if (llvm::Error Val = moveToTheNextStage(CurrentInstruction))
     return Val;
 
   // Move the program counter.
   CurrentInstruction.invalidate();
-  getNextInstruction();
-  return llvm::ErrorSuccess();
+  return getNextInstruction();
 }
 
 llvm::Error EntryStage::cycleStart() {
   if (!CurrentInstruction)
-    getNextInstruction();
+    return getNextInstruction();
   return llvm::ErrorSuccess();
 }
 
+llvm::Error EntryStage::cycleResume() {
+  assert(!CurrentInstruction);
+  return getNextInstruction();
+}
+
 llvm::Error EntryStage::cycleEnd() {
   // Find the first instruction which hasn't been retired.
   auto Range = make_range(&Instructions[NumRetired], Instructions.end());
   auto It = find_if(Range, [](const std::unique_ptr<Instruction> &I) {
     return !I->isRetired();
   });
 
   NumRetired = std::distance(Instructions.begin(), It);

llvm/lib/MCA/Stages/Stage.cpp

 
 // Pin the vtable here in the implementation file.
 Stage::~Stage() = default;
 
 void Stage::addListener(HWEventListener *Listener) {
   Listeners.insert(Listener);
 }
 
+char InstStreamPause::ID = 0;
 } // namespace mca
 } // namespace llvm

llvm/lib/Target/AMDGPU/MCA/AMDGPUCustomBehaviour.cpp

void AMDGPUCustomBehaviour::generateWaitCntInfo() {
   // functions. Therefore, we conservatively assume that these functions will
   // return true. This may cause a few instructions to be incorrectly tagged
   // with an extra CNT. However, these are instructions that do interact with at
   // least one CNT so giving them an extra CNT shouldn't cause issues in most
   // scenarios.
   AMDGPU::IsaVersion IV = AMDGPU::getIsaVersion(STI.getCPU());
   InstrWaitCntInfo.resize(SrcMgr.size());
 
-  int Index = 0;
-  for (auto I = SrcMgr.begin(), E = SrcMgr.end(); I != E; ++I, ++Index) {
-    const std::unique_ptr<Instruction> &Inst = *I;
+  for (const auto &EN : llvm::enumerate(SrcMgr.getInstructions())) {
+    const std::unique_ptr<Instruction> &Inst = EN.value();
+    unsigned Index = EN.index();
     unsigned Opcode = Inst->getOpcode();
     const MCInstrDesc &MCID = MCII.get(Opcode);
     if ((MCID.TSFlags & SIInstrFlags::DS) &&
         (MCID.TSFlags & SIInstrFlags::LGKM_CNT)) {
       InstrWaitCntInfo[Index].LgkmCnt = true;
       if (isAlwaysGDS(Opcode) || hasModifiersSet(Inst, AMDGPU::OpName::gds))
         InstrWaitCntInfo[Index].ExpCnt = true;
     } else if (MCID.TSFlags & SIInstrFlags::FLAT) {

llvm/tools/llvm-mca/llvm-mca.cpp

for (const MCInst &MCI : Insts) {
         return 1;
       }
 
       IPP->postProcessInstruction(Inst.get(), MCI);
 
       LoweredSequence.emplace_back(std::move(Inst.get()));
     }
 
-    mca::SourceMgr S(LoweredSequence, PrintInstructionTables ? 1 : Iterations);
+    mca::CircularSourceMgr S(LoweredSequence,
+                             PrintInstructionTables ? 1 : Iterations);
 
     if (PrintInstructionTables) {
       //  Create a pipeline, stages, and a printer.
       auto P = std::make_unique<mca::Pipeline>();
       P->appendStage(std::make_unique<mca::EntryStage>(S));
       P->appendStage(std::make_unique<mca::InstructionTables>(SM));
 
       mca::PipelinePrinter Printer(*P, *Region, RegionIdx, *STI, PO);

llvm/unittests/tools/CMakeLists.txt

 if(LLVM_TARGETS_TO_BUILD MATCHES "X86")
   add_subdirectory(
     llvm-cfi-verify
   )
 endif()
 
 add_subdirectory(
   llvm-exegesis
 )
 add_subdirectory(llvm-profgen)
+add_subdirectory(llvm-mca)

llvm/unittests/tools/llvm-mca/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  MC
+  MCA
+  Object
+  Support
+  )
+
+set(mca_root ${LLVM_MAIN_SRC_DIR}/tools/llvm-mca)
+
+set(mca_includes
+  ${CMAKE_CURRENT_SOURCE_DIR}
+  ${mca_root}
+  )
+
+# Right now we only need SummaryView.
+set(mca_views_sources
+  SummaryView.cpp
+  )
+list(TRANSFORM mca_views_sources PREPEND "${mca_root}/Views/")
+
+set(mca_sources
+  MCATestBase.cpp
+  ${mca_views_sources}
+  )
+
+function(add_llvm_mca_unittest_includes)
+  set(mca_includes ${mca_includes} ${ARGV} PARENT_SCOPE)
+endfunction()
+
+function(add_llvm_mca_unittest_sources)
+  set(sources ${ARGV})
+  list(TRANSFORM sources PREPEND "${CMAKE_CURRENT_LIST_DIR}/")
+  set(mca_sources ${mca_sources} ${sources} PARENT_SCOPE)
+endfunction()
+
+function(add_llvm_mca_unittest_link_components comps)
+  set(LLVM_LINK_COMPONENTS ${LLVM_LINK_COMPONENTS} ${ARGV} PARENT_SCOPE)
+endfunction()
+
+if(LLVM_TARGETS_TO_BUILD MATCHES "X86")
+  include(X86/CMakeLists.txt)
+endif()
+
+list(REMOVE_DUPLICATES LLVM_LINK_COMPONENTS)
+
+include_directories(${mca_includes})
+
+add_llvm_target_unittest(LLVMMCATests
+  ${mca_sources}
+  )
+
+set_property(TARGET LLVMMCATests PROPERTY FOLDER "Tests/UnitTests/ToolTests")

llvm/unittests/tools/llvm-mca/MCATestBase.h

+//===---- MCATestBase.h -----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Test fixture common to all MCA tests.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UNITTESTS_TOOLS_LLVMMCA_MCATESTBASE_H
+#define LLVM_UNITTESTS_TOOLS_LLVMMCA_MCATESTBASE_H
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/MC/MCTargetOptions.h"
+#include "llvm/MC/SubtargetFeature.h"
+#include "llvm/MC/TargetRegistry.h"
+#include "llvm/MCA/Context.h"
+
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace json {
+class Object;
+} // end namespace json
+
+namespace mca {
+class View;
+
+class MCATestBase : public ::testing::Test {
+protected:
+  // Note: Subclass ctors are expected to perform target-specific
+  // initializations.
+  MCATestBase(StringRef TripleStr, StringRef CPUName, StringRef MAttr = "")
+      : TheTriple(TripleStr), CPUName(CPUName), MAttr(MAttr) {}
+
+  /// Factory function to create a Target.
+  virtual const Target *getLLVMTarget() const;
+
+  /// Factory function to create a MCTargetOptions instance. Returns an
+  /// empty one by default.
+  virtual MCTargetOptions getMCTargetOptions() { return MCTargetOptions(); }
+
+  const Target *TheTarget;
+  const Triple TheTriple;
+  StringRef CPUName;
+  StringRef MAttr;
+
+  // MC components.
+  std::unique_ptr<MCSubtargetInfo> STI;
+  std::unique_ptr<MCRegisterInfo> MRI;
+  std::unique_ptr<MCAsmInfo> MAI;
+  std::unique_ptr<MCObjectFileInfo> MOFI;
+  std::unique_ptr<MCContext> Ctx;
+  std::unique_ptr<MCInstrInfo> MCII;
+  std::unique_ptr<MCInstrAnalysis> MCIA;
+  std::unique_ptr<MCInstPrinter> IP;
+
+  static mca::PipelineOptions getDefaultPipelineOptions();
+
+  void SetUp() override;
+
+  /// Utility function to run MCA with (nearly) the same configuration as the
+  /// `llvm-mca` tool to verify result correctness.
+  /// This function only displays on SummaryView by default.
+  virtual Error runBaselineMCA(json::Object &Result, ArrayRef<MCInst> Insts,
+                               ArrayRef<mca::View *> Views = None,
+                               const mca::PipelineOptions *PO = nullptr);
+};
+
+} // end namespace mca
+} // end namespace llvm
+#endif

llvm/unittests/tools/llvm-mca/MCATestBase.cpp

+#include "MCATestBase.h"
+#include "Views/SummaryView.h"
+#include "llvm/MCA/CustomBehaviour.h"
+#include "llvm/MCA/InstrBuilder.h"
+#include "llvm/MCA/Pipeline.h"
+#include "llvm/MCA/SourceMgr.h"
+#include "llvm/MCA/View.h"
+#include "llvm/Support/JSON.h"
+#include "llvm/Support/WithColor.h"
+#include <string>
+
+using namespace llvm;
+using namespace mca;
+
+const Target *MCATestBase::getLLVMTarget() const {
+  std::string Error;
+  return TargetRegistry::lookupTarget(TheTriple.getTriple(), Error);
+}
+
+mca::PipelineOptions MCATestBase::getDefaultPipelineOptions() {
+  mca::PipelineOptions PO(/*MicroOpQueue=*/0, /*DecoderThroughput=*/0,
+                          /*DispatchWidth=*/0,
+                          /*RegisterFileSize=*/0,
+                          /*LoadQueueSize=*/0, /*StoreQueueSize=*/0,
+                          /*AssumeNoAlias=*/true,
+                          /*EnableBottleneckAnalysis=*/false);
+  return PO;
+}
+
+void MCATestBase::SetUp() {
+  TheTarget = getLLVMTarget();
+  ASSERT_NE(TheTarget, nullptr);
+
+  StringRef TripleName = TheTriple.getTriple();
+
+  STI.reset(TheTarget->createMCSubtargetInfo(TripleName, CPUName, MAttr));
+  ASSERT_TRUE(STI);
+  ASSERT_TRUE(STI->isCPUStringValid(CPUName));
+
+  MRI.reset(TheTarget->createMCRegInfo(TripleName));
+  ASSERT_TRUE(MRI);
+
+  auto MCOptions = getMCTargetOptions();
+  MAI.reset(TheTarget->createMCAsmInfo(*MRI, TripleName, MCOptions));
+  ASSERT_TRUE(MAI);
+
+  Ctx = std::make_unique<MCContext>(TheTriple, MAI.get(), MRI.get(), STI.get());
+  MOFI.reset(TheTarget->createMCObjectFileInfo(*Ctx, /*PIC=*/false));
+  Ctx->setObjectFileInfo(MOFI.get());
+
+  MCII.reset(TheTarget->createMCInstrInfo());
+  ASSERT_TRUE(MCII);
+
+  MCIA.reset(TheTarget->createMCInstrAnalysis(MCII.get()));
+  ASSERT_TRUE(MCIA);
+
+  IP.reset(TheTarget->createMCInstPrinter(TheTriple, /*AssemblerDialect=*/0,
+                                          *MAI, *MCII, *MRI));
+  ASSERT_TRUE(IP);
+}
+
+Error MCATestBase::runBaselineMCA(json::Object &Result, ArrayRef<MCInst> Insts,
+                                  ArrayRef<mca::View *> Views,
+                                  const mca::PipelineOptions *PO) {
+  mca::Context MCA(*MRI, *STI);
+
+  mca::InstrBuilder IB(*STI, *MCII, *MRI, MCIA.get());
+
+  SmallVector<std::unique_ptr<mca::Instruction>> LoweredInsts;
+  for (const auto &MCI : Insts) {
+    Expected<std::unique_ptr<mca::Instruction>> Inst =
+        IB.createInstruction(MCI);
+    if (!Inst) {
+      if (auto NewE =
+              handleErrors(Inst.takeError(),
+                           [this](const mca::InstructionError<MCInst> &IE) {
+                             std::string InstructionStr;
+                             raw_string_ostream SS(InstructionStr);
+                             WithColor::error() << IE.Message << '\n';
+                             IP->printInst(&IE.Inst, 0, "", *STI, SS);
+                             WithColor::note()
+                                 << "instruction: " << InstructionStr << '\n';
+                           })) {
+        // Default case.
+        return std::move(NewE);
+      }
+    } else {
+      LoweredInsts.emplace_back(std::move(Inst.get()));
+    }
+  }
+
+  mca::CircularSourceMgr SM(LoweredInsts, /*Iterations=*/1);
+
+  // Empty CustomBehaviour.
+  auto CB = std::make_unique<mca::CustomBehaviour>(*STI, SM, *MCII);
+
+  mca::PipelineOptions ThePO = PO ? *PO : getDefaultPipelineOptions();
+  auto P = MCA.createDefaultPipeline(ThePO, SM, *CB);
+
+  SmallVector<std::unique_ptr<mca::View>, 1> DefaultViews;
+  if (Views.empty()) {
+    // By default, we only add SummaryView.
+    auto SV = std::make_unique<SummaryView>(STI->getSchedModel(), Insts,
+                                            ThePO.DispatchWidth);
+    P->addEventListener(SV.get());
+    DefaultViews.emplace_back(std::move(SV));
+  } else {
+    for (auto *V : Views)
+      P->addEventListener(V);
+  }
+
+  // Run the pipeline.
+  Expected<unsigned> Cycles = P->run();
+  if (!Cycles)
+    return Cycles.takeError();
+
+  for (const auto *V : Views)
+    Result[V->getNameAsString()] = V->toJSON();
+  for (const auto &V : DefaultViews)
+    Result[V->getNameAsString()] = V->toJSON();
+
+  return Error::success();
+}

llvm/unittests/tools/llvm-mca/X86/CMakeLists.txt

+add_llvm_mca_unittest_includes(
+  ${LLVM_MAIN_SRC_DIR}/lib/Target/X86
+  ${LLVM_BINARY_DIR}/lib/Target/X86
+  )
+
+add_llvm_mca_unittest_sources(
+  TestIncrementalMCA.cpp
+  X86TestBase.cpp
+  )
+
+add_llvm_mca_unittest_link_components(
+  X86
+  )

llvm/unittests/tools/llvm-mca/X86/TestIncrementalMCA.cpp

+#include "Views/SummaryView.h"
+#include "X86TestBase.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/MCA/CustomBehaviour.h"
+#include "llvm/MCA/IncrementalSourceMgr.h"
+#include "llvm/MCA/InstrBuilder.h"
+#include "llvm/MCA/Pipeline.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/JSON.h"
+#include "llvm/Support/raw_ostream.h"
+#include <unordered_map>
+
+using namespace llvm;
+using namespace mca;
+
+TEST_F(X86TestBase, TestResumablePipeline) {
+  mca::Context MCA(*MRI, *STI);
+
+  mca::IncrementalSourceMgr ISM;
+  // Empty CustomBehaviour.
+  auto CB = std::make_unique<mca::CustomBehaviour>(*STI, ISM, *MCII);
+
+  auto PO = getDefaultPipelineOptions();
+  auto P = MCA.createDefaultPipeline(PO, ISM, *CB);
+  ASSERT_TRUE(P);
+
+  SmallVector<MCInst> MCIs;
+  getSimpleInsts(MCIs, /*Repeats=*/100);
+
+  // Add views.
+  auto SV = std::make_unique<SummaryView>(STI->getSchedModel(), MCIs,
+                                          PO.DispatchWidth);
+  P->addEventListener(SV.get());
+
+  mca::InstrBuilder IB(*STI, *MCII, *MRI, MCIA.get());
+
+  // Tile size = 7
+  for (unsigned i = 0U, E = MCIs.size(); i < E;) {
+    for (unsigned TE = i + 7; i < TE && i < E; ++i) {
+      Expected<std::unique_ptr<mca::Instruction>> InstOrErr =
+          IB.createInstruction(MCIs[i]);
+      ASSERT_TRUE(bool(InstOrErr));
+      ISM.addInst(std::move(InstOrErr.get()));
+    }
+
+    // Run the pipeline.
+    Expected<unsigned> Cycles = P->run();
+    if (!Cycles) {
+      // Should be a stream pause error.
+      ASSERT_TRUE(Cycles.errorIsA<mca::InstStreamPause>());
+      llvm::consumeError(Cycles.takeError());
+    }
+  }
+
+  ISM.endOfStream();
+  // Has to terminate properly.
+  Expected<unsigned> Cycles = P->run();
+  ASSERT_TRUE(bool(Cycles));
+
+  json::Value Result = SV->toJSON();
+  auto *ResultObj = Result.getAsObject();
+  ASSERT_TRUE(ResultObj);
+
+  // Run the baseline.
+  json::Object BaselineResult;
+  auto E = runBaselineMCA(BaselineResult, MCIs);
+  ASSERT_FALSE(bool(E)) << "Failed to run baseline";
+  auto *BaselineObj = BaselineResult.getObject(SV->getNameAsString());
+  ASSERT_TRUE(BaselineObj) << "Does not contain SummaryView result";
+
+  // Compare the results.
+  constexpr const char *Fields[] = {"Instructions", "TotalCycles", "TotaluOps",
+                                    "BlockRThroughput"};
+  for (const auto *F : Fields) {
+    auto V = ResultObj->getInteger(F);
+    auto BV = BaselineObj->getInteger(F);
+    ASSERT_TRUE(V && BV);
+    ASSERT_EQ(*BV, *V) << "Value of '" << F << "' does not match";
+  }
+}

llvm/unittests/tools/llvm-mca/X86/X86TestBase.h

+//===---- X86TestBase.h -----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// Test fixture common to all X86 MCA tests.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UNITTESTS_TOOLS_LLVMMCA_X86_X86TESTBASE_H
+#define LLVM_UNITTESTS_TOOLS_LLVMMCA_X86_X86TESTBASE_H
+
+#include "MCATestBase.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace llvm {
+namespace mca {
+
+class X86TestBase : public MCATestBase {
+protected:
+  X86TestBase();
+
+  void getSimpleInsts(SmallVectorImpl<MCInst> &Insts, unsigned Repeats = 1);
+};
+
+} // end namespace mca
+} // end namespace llvm
+
+#endif

llvm/unittests/tools/llvm-mca/X86/X86TestBase.cpp

+#include "X86TestBase.h"
+#include "MCTargetDesc/X86MCTargetDesc.h"
+#include "llvm/MC/MCInstBuilder.h"
+#include "llvm/Support/TargetSelect.h"
+
+using namespace llvm;
+using namespace mca;
+
+X86TestBase::X86TestBase() : MCATestBase("x86_64-unknown-linux", "skylake") {
+  LLVMInitializeX86TargetInfo();
+  LLVMInitializeX86TargetMC();
+  LLVMInitializeX86Target();
+  LLVMInitializeX86AsmPrinter();
+}
+
+void X86TestBase::getSimpleInsts(SmallVectorImpl<MCInst> &Insts,
+                                 unsigned Repeats) {
+  for (unsigned i = 0U; i < Repeats; ++i) {
+    // vmulps  %xmm0, %xmm1, %xmm2
+    Insts.push_back(MCInstBuilder(X86::VMULPSrr)
+                        .addReg(X86::XMM2)
+                        .addReg(X86::XMM1)
+                        .addReg(X86::XMM0));
+    // vhaddps %xmm2, %xmm2, %xmm3
+    Insts.push_back(MCInstBuilder(X86::VHADDPSrr)
+                        .addReg(X86::XMM3)
+                        .addReg(X86::XMM2)
+                        .addReg(X86::XMM2));
+    // vhaddps %xmm3, %xmm3, %xmm4
+    Insts.push_back(MCInstBuilder(X86::VHADDPSrr)
+                        .addReg(X86::XMM4)
+                        .addReg(X86::XMM3)
+                        .addReg(X86::XMM3));
+  }
+}