[MCA] Allow mca::Instruction-s to be recycled and reused

[myhsu]

Summary

This patch introduces a new feature that allows InstrBuilder to reuse mca::Instruction recycled from IncrementalSourceMgr. This significantly reduces the memory footprint.
Note that we're only recycling instructions that have static InstrDesc and no variadic operands.

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

[andreadb]

Hi Min,

I left a few comments below.

Thanks for the patch!

-Andrea

llvm/include/llvm/MCA/IncrementalSourceMgr.h

81–108

Could you please move these definitions to a IncrementalSourceMgr.cpp ?

llvm/include/llvm/MCA/InstrBuilder.h

25

I really don't think that we should use system_error.

78

Would it be more readable if we defined that type with a using InstRecycleCallback = ...?

That way, you may not need to use decltype at line 101.

llvm/include/llvm/MCA/Instruction.h

576–577

Personally, I prefer that we don't touch that method. What about adding a
void clearOptimizableMove() ?

653–663

Please move this definition to Instruction.cpp

llvm/lib/MCA/InstrBuilder.cpp

542–544

I wonder if instead we should add a bitfield bool IsRecyclable : 1 to struct InstrDesc.

By default, it would be set to false.

That way, you don't need to change these signatures, and you can still retrieve that information automatically. It might make the rest of the logic a bit more readable/self documenting.

[myhsu]

Addressed feedbacks.

[myhsu]

llvm/lib/MCA/InstrBuilder.cpp

542–544

yeah that definitely sounds more elegant

[andreadb]

Hi Min,

Patch looks good modulo a minor nit (see my comment below).

Thanks!
-Andrea

llvm/include/llvm/MCA/IncrementalSourceMgr.h

43–56

I suggest to use a using for that type, and then use that new type definition in setOnInstFreedCallback (instead of using decltype).

Something like this:

using InstFreedCallbackTy = llvm::function_ref<void(Instruction *)>;

[myhsu]

Use type alias for instruction recycling callback function type.

[myhsu]

a gentle ping

[andreadb]

In D127084#3605593, @myhsu wrote:

a gentle ping

LGTM

Thanks!

llvm/include/llvm/MCA/IncrementalSourceMgr.h

 /// 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;
 
+  /// Instructions that are ready to be used. Each of them is a pointer of an
+  /// \a UniqueInst inside InstStorage.
+  std::deque<Instruction *> Staging;
+
   /// Current instruction index.
   unsigned TotalCounter;
 
   /// End-of-stream flag.
   bool EOS;
 
+  /// Called when an instruction is no longer needed.
+  using InstFreedCallback = llvm::function_ref<void(Instruction *)>;
+  InstFreedCallback InstFreedCB;
+
 public:
   IncrementalSourceMgr() : TotalCounter(0U), EOS(false) {}
 
-  void clear() {
-    InstStorage.clear();
-    TotalCounter = 0U;
-    EOS = false;
-  }
+  void clear();
+
+  /// Set a callback that is invoked when a mca::Instruction is
+  /// no longer needed. This is usually used for recycling the
+  /// instruction.
+  void setOnInstFreedCallback(InstFreedCallback CB) { InstFreedCB = CB; }
 
   ArrayRef<UniqueInst> getInstructions() const override {
     llvm_unreachable("Not applicable");
   }
 
-  bool hasNext() const override { return TotalCounter < InstStorage.size(); }
+  bool hasNext() const override { return !Staging.empty(); }
   bool isEnd() const override { return EOS; }
 
   SourceRef peekNext() const override {
     assert(hasNext());
-    return SourceRef(TotalCounter, *InstStorage[TotalCounter]);
+    return SourceRef(TotalCounter, *Staging.front());
   }
 
   /// Add a new instruction.
-  void addInst(UniqueInst &&Inst) { InstStorage.emplace_back(std::move(Inst)); }
+  void addInst(UniqueInst &&Inst) {
+    InstStorage.emplace_back(std::move(Inst));
+    Staging.push_back(InstStorage.back().get());
+  }
+
+  /// Add a recycled instruction.
+  void addRecycledInst(Instruction *Inst) { Staging.push_back(Inst); }
 
-  void updateNext() override { ++TotalCounter; }
+  void updateNext() override;
 
   /// Mark the end of instruction stream.
   void endOfStream() { EOS = true; }
+
+#ifndef NDEBUG
+  /// Print statistic about instruction recycling stats.
+  void printStatistic(raw_ostream &OS);
+#endif
 };
 
 } // end namespace mca
 } // end namespace llvm
 
 #endif // LLVM_MCA_INCREMENTALSOURCEMGR_H

llvm/include/llvm/MCA/InstrBuilder.h

 //===--------------------- InstrBuilder.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
 ///
 /// A builder class for instructions that are statically analyzed by llvm-mca.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_MCA_INSTRBUILDER_H
 #define LLVM_MCA_INSTRBUILDER_H
 
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/MC/MCInstrAnalysis.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/MC/MCSubtargetInfo.h"
 #include "llvm/MCA/Instruction.h"
 #include "llvm/MCA/Support.h"
 #include "llvm/Support/Error.h"
 
 namespace llvm {
 namespace mca {
 
+class RecycledInstErr : public ErrorInfo<RecycledInstErr> {
+  Instruction *RecycledInst;
+
+public:
+  static char ID;
+
+  explicit RecycledInstErr(Instruction *Inst) : RecycledInst(Inst) {}
+  // Always need to carry an Instruction
+  RecycledInstErr() = delete;
+
+  Instruction *getInst() const { return RecycledInst; }
+
+  void log(raw_ostream &OS) const override {
+    OS << "Instruction is recycled\n";
+  }
+
+  std::error_code convertToErrorCode() const override {
+    return llvm::inconvertibleErrorCode();
+  }
+};
+
 /// A builder class that knows how to construct Instruction objects.
 ///
 /// Every llvm-mca Instruction is described by an object of class InstrDesc.
 /// An InstrDesc describes which registers are read/written by the instruction,
 /// as well as the instruction latency and hardware resources consumed.
 ///
 /// This class is used by the tool to construct Instructions and instruction
 /// descriptors (i.e. InstrDesc objects).
 /// Information from the machine scheduling model is used to identify processor
 /// resources that are consumed by an instruction.
 class InstrBuilder {
   const MCSubtargetInfo &STI;
   const MCInstrInfo &MCII;
   const MCRegisterInfo &MRI;
   const MCInstrAnalysis *MCIA;
   SmallVector<uint64_t, 8> ProcResourceMasks;
 
   DenseMap<unsigned short, std::unique_ptr<const InstrDesc>> Descriptors;
   DenseMap<const MCInst *, std::unique_ptr<const InstrDesc>> VariantDescriptors;
 
   bool FirstCallInst;
   bool FirstReturnInst;
 
+  using InstRecycleCallback =
+      llvm::function_ref<Instruction *(const InstrDesc &)>;
+  InstRecycleCallback InstRecycleCB;
+
   Expected<const InstrDesc &> createInstrDescImpl(const MCInst &MCI);
   Expected<const InstrDesc &> getOrCreateInstrDesc(const MCInst &MCI);
 
   InstrBuilder(const InstrBuilder &) = delete;
   InstrBuilder &operator=(const InstrBuilder &) = delete;
 
   void populateWrites(InstrDesc &ID, const MCInst &MCI, unsigned SchedClassID);
   void populateReads(InstrDesc &ID, const MCInst &MCI, unsigned SchedClassID);
   Error verifyInstrDesc(const InstrDesc &ID, const MCInst &MCI) const;
 
 public:
   InstrBuilder(const MCSubtargetInfo &STI, const MCInstrInfo &MCII,
                const MCRegisterInfo &RI, const MCInstrAnalysis *IA);
 
   void clear() {
     Descriptors.clear();
     VariantDescriptors.clear();
     FirstCallInst = true;
     FirstReturnInst = true;
   }
 
+  /// Set a callback which is invoked to retrieve a recycled mca::Instruction
+  /// or null if there isn't any.
+  void setInstRecycleCallback(InstRecycleCallback CB) { InstRecycleCB = CB; }
+
   Expected<std::unique_ptr<Instruction>> createInstruction(const MCInst &MCI);
 };
 } // namespace mca
 } // namespace llvm
 
 #endif // LLVM_MCA_INSTRBUILDER_H

llvm/include/llvm/MCA/Instruction.h

struct InstrDesc {
   // This information is currently used by views to do fast queries on the
   // subtarget when computing the reciprocal throughput.
   unsigned SchedClassID;
 
   // True if all buffered resources are in-order, and there is at least one
   // buffer which is a dispatch hazard (BufferSize = 0).
   unsigned MustIssueImmediately : 1;
 
+  // True if the corresponding mca::Instruction can be recycled. Currently only
+  // instructions that are neither variadic nor have any variant can be
+  // recycled.
+  unsigned IsRecyclable : 1;
+
   // A zero latency instruction doesn't consume any scheduler resources.
   bool isZeroLatency() const { return !MaxLatency && Resources.empty(); }
 
   InstrDesc() = default;
   InstrDesc(const InstrDesc &Other) = delete;
   InstrDesc &operator=(const InstrDesc &Other) = delete;
 };
 
unsigned getNumUsers() const {
     unsigned NumUsers = 0;
     for (const WriteState &Def : Defs)
       NumUsers += Def.getNumUsers();
     return NumUsers;
   }
 
   // Returns true if this instruction is a candidate for move elimination.
   bool isOptimizableMove() const { return IsOptimizableMove; }
   void setOptimizableMove() { IsOptimizableMove = true; }
+  void clearOptimizableMove() { IsOptimizableMove = false; }
   bool isMemOp() const { return MayLoad || MayStore; }
 
   // Getters and setters for general instruction flags.
   void setMayLoad(bool newVal) { MayLoad = newVal; }
   void setMayStore(bool newVal) { MayStore = newVal; }
   void setHasSideEffects(bool newVal) { HasSideEffects = newVal; }
   void setBeginGroup(bool newVal) { BeginGroup = newVal; }
   void setEndGroup(bool newVal) { EndGroup = newVal; }

 
 public:
   Instruction(const InstrDesc &D, const unsigned Opcode)
       : InstructionBase(D, Opcode), Stage(IS_INVALID),
         CyclesLeft(UNKNOWN_CYCLES), RCUTokenID(0), LSUTokenID(0),
         UsedBuffers(D.UsedBuffers), CriticalRegDep(), CriticalMemDep(),
         CriticalResourceMask(0), IsEliminated(false) {}
 
+  void reset();
+
   unsigned getRCUTokenID() const { return RCUTokenID; }
   unsigned getLSUTokenID() const { return LSUTokenID; }
   void setLSUTokenID(unsigned LSUTok) { LSUTokenID = LSUTok; }
 
   uint64_t getUsedBuffers() const { return UsedBuffers; }
   void setUsedBuffers(uint64_t Mask) { UsedBuffers = Mask; }
   void clearUsedBuffers() { UsedBuffers = 0ULL; }
 
   int getCyclesLeft() const { return CyclesLeft; }
 
   // Transition to the dispatch stage, and assign a RCUToken to this
   // instruction. The RCUToken is used to track the completion of every
   // register write performed by this instruction.
   void dispatch(unsigned RCUTokenID);
 
   // Instruction issued. Transition to the IS_EXECUTING state, and update
   // all the register definitions.
   void execute(unsigned IID);
 
   // Force a transition from the IS_DISPATCHED state to the IS_READY or
   // IS_PENDING state. State transitions normally occur either at the beginning
   // of a new cycle (see method cycleEvent()), or as a result of another issue
   // event. This method is called every time the instruction might have changed
   // in state. It internally delegates to method updateDispatched() and
   // updateWaiting().
   void update();
   bool updateDispatched();
   bool updatePending();
 
+  bool isInvalid() const { return Stage == IS_INVALID; }
   bool isDispatched() const { return Stage == IS_DISPATCHED; }
   bool isPending() const { return Stage == IS_PENDING; }
   bool isReady() const { return Stage == IS_READY; }
   bool isExecuting() const { return Stage == IS_EXECUTING; }
   bool isExecuted() const { return Stage == IS_EXECUTED; }
   bool isRetired() const { return Stage == IS_RETIRED; }
   bool isEliminated() const { return IsEliminated; }
 

llvm/lib/MCA/CMakeLists.txt

 add_llvm_component_library(LLVMMCA
   CodeEmitter.cpp
   Context.cpp
   CustomBehaviour.cpp
   HWEventListener.cpp
   HardwareUnits/HardwareUnit.cpp
   HardwareUnits/LSUnit.cpp
   HardwareUnits/RegisterFile.cpp
   HardwareUnits/ResourceManager.cpp
   HardwareUnits/RetireControlUnit.cpp
   HardwareUnits/Scheduler.cpp
+  IncrementalSourceMgr.cpp
   InstrBuilder.cpp
   Instruction.cpp
   Pipeline.cpp
   Stages/DispatchStage.cpp
   Stages/EntryStage.cpp
   Stages/ExecuteStage.cpp
   Stages/InOrderIssueStage.cpp
   Stages/InstructionTables.cpp

llvm/lib/MCA/IncrementalSourceMgr.cpp

+//===-------------------- IncrementalSourceMgr.cpp ------------------------===//
+//
+// 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 defines some implementations for IncrementalSourceMgr.
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/MCA/IncrementalSourceMgr.h"
+#ifndef NDEBUG
+#include "llvm/Support/Format.h"
+#endif
+
+using namespace llvm;
+using namespace llvm::mca;
+
+void IncrementalSourceMgr::clear() {
+  Staging.clear();
+  InstStorage.clear();
+  TotalCounter = 0U;
+  EOS = false;
+}
+
+void IncrementalSourceMgr::updateNext() {
+  ++TotalCounter;
+  Instruction *I = Staging.front();
+  Staging.pop_front();
+  I->reset();
+
+  if (InstFreedCB)
+    InstFreedCB(I);
+}
+
+#ifndef NDEBUG
+void IncrementalSourceMgr::printStatistic(raw_ostream &OS) {
+  unsigned MaxInstStorageSize = InstStorage.size();
+  if (MaxInstStorageSize <= TotalCounter) {
+    auto Ratio = double(MaxInstStorageSize) / double(TotalCounter);
+    OS << "Cache ratio = " << MaxInstStorageSize << " / " << TotalCounter
+       << llvm::format(" (%.2f%%)", (1.0 - Ratio) * 100.0) << "\n";
+  } else {
+    OS << "Error: Number of created instructions "
+       << "are larger than the number of issued instructions\n";
+  }
+}
+#endif

llvm/lib/MCA/InstrBuilder.cpp

 //===--------------------- InstrBuilder.cpp ---------------------*- 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 the InstrBuilder interface.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/MCA/InstrBuilder.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
 
-#define DEBUG_TYPE "llvm-mca"
+#define DEBUG_TYPE "llvm-mca-instrbuilder"
 
 namespace llvm {
 namespace mca {
 
+char RecycledInstErr::ID = 0;
+
 InstrBuilder::InstrBuilder(const llvm::MCSubtargetInfo &sti,
                            const llvm::MCInstrInfo &mcii,
                            const llvm::MCRegisterInfo &mri,
                            const llvm::MCInstrAnalysis *mcia)
     : STI(sti), MCII(mcii), MRI(mri), MCIA(mcia), FirstCallInst(true),
       FirstReturnInst(true) {
   const MCSchedModel &SM = STI.getSchedModel();
   ProcResourceMasks.resize(SM.getNumProcResourceKinds());
Error InstrBuilder::verifyInstrDesc(const InstrDesc &ID,
   // FIXME: see PR44797. We should revisit these checks and possibly move them
   // in CodeGenSchedule.cpp.
   StringRef Message = "found an inconsistent instruction that decodes to zero "
                       "opcodes and that consumes scheduler resources.";
   return make_error<InstructionError<MCInst>>(std::string(Message), MCI);
 }
 
 Expected<const InstrDesc &>
 InstrBuilder::createInstrDescImpl(const MCInst &MCI) {
   assert(STI.getSchedModel().hasInstrSchedModel() &&
          "Itineraries are not yet supported!");
 
   // Obtain the instruction descriptor from the opcode.
   unsigned short Opcode = MCI.getOpcode();
   const MCInstrDesc &MCDesc = MCII.get(Opcode);
   const MCSchedModel &SM = STI.getSchedModel();
 
   // Then obtain the scheduling class information from the instruction.
   unsigned SchedClassID = MCDesc.getSchedClass();
InstrBuilder::createInstrDescImpl(const MCInst &MCI) {
   LLVM_DEBUG(dbgs() << "\t\tNumMicroOps=" << ID->NumMicroOps << '\n');
 
   // Validation check on the instruction descriptor.
   if (Error Err = verifyInstrDesc(*ID, MCI))
     return std::move(Err);
 
   // Now add the new descriptor.
   bool IsVariadic = MCDesc.isVariadic();
-  if (!IsVariadic && !IsVariant) {
+  if ((ID->IsRecyclable = !IsVariadic && !IsVariant)) {
     Descriptors[MCI.getOpcode()] = std::move(ID);
     return *Descriptors[MCI.getOpcode()];
   }
 
   VariantDescriptors[&MCI] = std::move(ID);
   return *VariantDescriptors[&MCI];
 }
 
 Expected<const InstrDesc &>
 InstrBuilder::getOrCreateInstrDesc(const MCInst &MCI) {
   if (Descriptors.find_as(MCI.getOpcode()) != Descriptors.end())
     return *Descriptors[MCI.getOpcode()];
 
   if (VariantDescriptors.find(&MCI) != VariantDescriptors.end())
     return *VariantDescriptors[&MCI];
 
   return createInstrDescImpl(MCI);
 }
 
+STATISTIC(NumVariantInst, "Number of MCInsts that doesn't have static Desc");
+
 Expected<std::unique_ptr<Instruction>>
 InstrBuilder::createInstruction(const MCInst &MCI) {
   Expected<const InstrDesc &> DescOrErr = getOrCreateInstrDesc(MCI);
   if (!DescOrErr)
     return DescOrErr.takeError();
   const InstrDesc &D = *DescOrErr;
-  std::unique_ptr<Instruction> NewIS =
-      std::make_unique<Instruction>(D, MCI.getOpcode());
+  Instruction *NewIS = nullptr;
+  std::unique_ptr<Instruction> CreatedIS;
+  bool IsInstRecycled = false;
+
+  if (!D.IsRecyclable)
+    ++NumVariantInst;
+
+  if (D.IsRecyclable && InstRecycleCB) {
+    if (auto *I = InstRecycleCB(D)) {
+      NewIS = I;
+      NewIS->reset();
+      IsInstRecycled = true;
+    }
+  }
+  if (!IsInstRecycled) {
+    CreatedIS = std::make_unique<Instruction>(D, MCI.getOpcode());
+    NewIS = CreatedIS.get();
+  }
 
   const MCInstrDesc &MCDesc = MCII.get(MCI.getOpcode());
   const MCSchedClassDesc &SCDesc =
       *STI.getSchedModel().getSchedClassDesc(D.SchedClassID);
 
   NewIS->setMayLoad(MCDesc.mayLoad());
   NewIS->setMayStore(MCDesc.mayStore());
   NewIS->setHasSideEffects(MCDesc.hasUnmodeledSideEffects());
if (MCIA) {
     IsDepBreaking =
         IsZeroIdiom || MCIA->isDependencyBreaking(MCI, Mask, ProcID);
     if (MCIA->isOptimizableRegisterMove(MCI, ProcID))
       NewIS->setOptimizableMove();
   }
 
   // Initialize Reads first.
   MCPhysReg RegID = 0;
+  size_t Idx = 0U;
   for (const ReadDescriptor &RD : D.Reads) {
     if (!RD.isImplicitRead()) {
       // explicit read.
       const MCOperand &Op = MCI.getOperand(RD.OpIndex);
       // Skip non-register operands.
       if (!Op.isReg())
         continue;
       RegID = Op.getReg();
     } else {
       // Implicit read.
       RegID = RD.RegisterID;
     }
 
     // Skip invalid register operands.
     if (!RegID)
       continue;
 
     // Okay, this is a register operand. Create a ReadState for it.
+    ReadState *RS = nullptr;
+    if (IsInstRecycled && Idx < NewIS->getUses().size()) {
+      NewIS->getUses()[Idx] = ReadState(RD, RegID);
+      RS = &NewIS->getUses()[Idx++];
+    } else {
       NewIS->getUses().emplace_back(RD, RegID);
-    ReadState &RS = NewIS->getUses().back();
+      RS = &NewIS->getUses().back();
+      ++Idx;
+    }
 
     if (IsDepBreaking) {
       // A mask of all zeroes means: explicit input operands are not
       // independent.
       if (Mask.isZero()) {
         if (!RD.isImplicitRead())
-          RS.setIndependentFromDef();
+          RS->setIndependentFromDef();
       } else {
         // Check if this register operand is independent according to `Mask`.
         // Note that Mask may not have enough bits to describe all explicit and
         // implicit input operands. If this register operand doesn't have a
         // corresponding bit in Mask, then conservatively assume that it is
         // dependent.
         if (Mask.getBitWidth() > RD.UseIndex) {
           // Okay. This map describe register use `RD.UseIndex`.
           if (Mask[RD.UseIndex])
-            RS.setIndependentFromDef();
+            RS->setIndependentFromDef();
         }
       }
     }
   }
+  if (IsInstRecycled && Idx < NewIS->getUses().size())
+    NewIS->getUses().pop_back_n(NewIS->getUses().size() - Idx);
 
   // Early exit if there are no writes.
-  if (D.Writes.empty())
-    return std::move(NewIS);
+  if (D.Writes.empty()) {
+    if (IsInstRecycled)
+      return llvm::make_error<RecycledInstErr>(NewIS);
+    else
+      return std::move(CreatedIS);
+  }
 
   // Track register writes that implicitly clear the upper portion of the
   // underlying super-registers using an APInt.
   APInt WriteMask(D.Writes.size(), 0);
 
   // Now query the MCInstrAnalysis object to obtain information about which
   // register writes implicitly clear the upper portion of a super-register.
   if (MCIA)
     MCIA->clearsSuperRegisters(MRI, MCI, WriteMask);
 
   // Initialize writes.
   unsigned WriteIndex = 0;
+  Idx = 0U;
   for (const WriteDescriptor &WD : D.Writes) {
     RegID = WD.isImplicitWrite() ? WD.RegisterID
                                  : MCI.getOperand(WD.OpIndex).getReg();
     // Check if this is a optional definition that references NoReg.
     if (WD.IsOptionalDef && !RegID) {
       ++WriteIndex;
       continue;
     }
 
     assert(RegID && "Expected a valid register ID!");
+    if (IsInstRecycled && Idx < NewIS->getDefs().size()) {
+      NewIS->getDefs()[Idx++] =
+          WriteState(WD, RegID,
+                     /* ClearsSuperRegs */ WriteMask[WriteIndex],
+                     /* WritesZero */ IsZeroIdiom);
+    } else {
       NewIS->getDefs().emplace_back(WD, RegID,
                                     /* ClearsSuperRegs */ WriteMask[WriteIndex],
                                     /* WritesZero */ IsZeroIdiom);
+      ++Idx;
+    }
     ++WriteIndex;
   }
+  if (IsInstRecycled && Idx < NewIS->getDefs().size())
+    NewIS->getDefs().pop_back_n(NewIS->getDefs().size() - Idx);
 
-  return std::move(NewIS);
+  if (IsInstRecycled)
+    return llvm::make_error<RecycledInstErr>(NewIS);
+  else
+    return std::move(CreatedIS);
 }
 } // namespace mca
 } // namespace llvm

llvm/lib/MCA/Instruction.cpp

for (const ReadState &RS : getUses()) {
     const CriticalDependency &ReadCRD = RS.getCriticalRegDep();
     if (ReadCRD.Cycles > MaxLatency)
       CriticalRegDep = ReadCRD;
   }
 
   return CriticalRegDep;
 }
 
+void Instruction::reset() {
+  // Note that this won't clear read/write descriptors
+  // or other non-trivial fields
+  Stage = IS_INVALID;
+  CyclesLeft = UNKNOWN_CYCLES;
+  clearOptimizableMove();
+  RCUTokenID = 0;
+  LSUTokenID = 0;
+  CriticalResourceMask = 0;
+  IsEliminated = false;
+}
+
 void Instruction::dispatch(unsigned RCUToken) {
   assert(Stage == IS_INVALID);
   Stage = IS_DISPATCHED;
   RCUTokenID = RCUToken;
 
   // Check if input operands are already available.
   if (updateDispatched())
     updatePending();

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

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";
   }
 }
+
+TEST_F(X86TestBase, TestInstructionRecycling) {
+  mca::Context MCA(*MRI, *STI);
+
+  std::unordered_map<const mca::InstrDesc *, SmallPtrSet<mca::Instruction *, 2>>
+      RecycledInsts;
+  auto GetRecycledInst = [&](const mca::InstrDesc &Desc) -> mca::Instruction * {
+    auto It = RecycledInsts.find(&Desc);
+    if (It != RecycledInsts.end()) {
+      auto &Insts = It->second;
+      if (Insts.size()) {
+        mca::Instruction *I = *Insts.begin();
+        Insts.erase(I);
+        return I;
+      }
+    }
+    return nullptr;
+  };
+  auto AddRecycledInst = [&](mca::Instruction *I) {
+    const mca::InstrDesc &D = I->getDesc();
+    RecycledInsts[&D].insert(I);
+  };
+
+  mca::IncrementalSourceMgr ISM;
+  ISM.setOnInstFreedCallback(AddRecycledInst);
+
+  // 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());
+  IB.setInstRecycleCallback(GetRecycledInst);
+
+  // 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]);
+
+      if (!InstOrErr) {
+        mca::Instruction *RecycledInst = nullptr;
+        // Check if the returned instruction is a recycled
+        // one.
+        auto RemainingE = handleErrors(InstOrErr.takeError(),
+                                       [&](const mca::RecycledInstErr &RC) {
+                                         RecycledInst = RC.getInst();
+                                       });
+        ASSERT_FALSE(bool(RemainingE));
+        ASSERT_TRUE(RecycledInst);
+        ISM.addRecycledInst(RecycledInst);
+      } else {
+        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";
+  }
+}