Index: tools/llvm-mca/Backend.h =================================================================== --- tools/llvm-mca/Backend.h +++ tools/llvm-mca/Backend.h @@ -18,7 +18,7 @@ #include "Dispatch.h" #include "InstrBuilder.h" #include "Scheduler.h" -#include "SourceMgr.h" +#include "Stage.h" namespace mca { @@ -29,59 +29,62 @@ /// An out of order backend for a specific subtarget. /// /// It emulates an out-of-order execution of instructions. Instructions are -/// fetched from a MCInst sequence managed by an object of class SourceMgr. -/// Instructions are firstly dispatched to the schedulers and then executed. +/// fetched from a MCInst sequence managed by an initial 'Fetch' stage: +/// 'InitialStage'. Instructions are firstly dispatched to the schedulers and +/// then executed. +/// /// This class tracks the lifetime of an instruction from the moment where /// it gets dispatched to the schedulers, to the moment where it finishes /// executing and register writes are architecturally committed. /// In particular, it monitors changes in the state of every instruction /// in flight. +/// /// Instructions are executed in a loop of iterations. The number of iterations -/// is defined by the SourceMgr object. -/// The Backend entrypoint is method 'Run()' which execute cycles in a loop +/// is defined by the SourceMgr object, which is managed by the initial stage +/// of the instruction pipeline. +/// +/// The Backend entrypoint is method 'run()' which executes cycles in a loop /// until there are new instructions to dispatch, and not every instruction /// has been retired. +/// /// Internally, the Backend collects statistical information in the form of /// histograms. For example, it tracks how the dispatch group size changes /// over time. class Backend { const llvm::MCSubtargetInfo &STI; - InstrBuilder &IB; + // This is most likely an instruction fetch stage, but that decision will be + // decided by the backend implementation. + std::unique_ptr InitialStage; + std::unique_ptr HWS; std::unique_ptr DU; - SourceMgr &SM; - unsigned Cycles; - - llvm::DenseMap> Instructions; std::set Listeners; + unsigned Cycles; void runCycle(unsigned Cycle); public: Backend(const llvm::MCSubtargetInfo &Subtarget, - const llvm::MCRegisterInfo &MRI, InstrBuilder &B, SourceMgr &Source, - unsigned DispatchWidth = 0, unsigned RegisterFileSize = 0, - unsigned LoadQueueSize = 0, unsigned StoreQueueSize = 0, - bool AssumeNoAlias = false) - : STI(Subtarget), IB(B), + const llvm::MCRegisterInfo &MRI, unsigned DispatchWidth = 0, + unsigned RegisterFileSize = 0, unsigned LoadQueueSize = 0, + unsigned StoreQueueSize = 0, bool AssumeNoAlias = false) + : STI(Subtarget), InitialStage(nullptr), HWS(llvm::make_unique(this, Subtarget.getSchedModel(), LoadQueueSize, StoreQueueSize, AssumeNoAlias)), DU(llvm::make_unique(this, Subtarget.getSchedModel(), MRI, RegisterFileSize, DispatchWidth, HWS.get())), - SM(Source), Cycles(0) { + Cycles(0) { HWS->setDispatchUnit(DU.get()); } - void run() { - while (SM.hasNext() || !DU->isRCUEmpty()) - runCycle(Cycles++); - } + void run(); - void eraseInstruction(const InstRef &IR) { - Instructions.erase(IR.getSourceIndex()); + void registerInitialStage(std::unique_ptr IS) { + assert(IS && "Expected a non-nullptr initial stage instance."); + InitialStage = std::move(IS); } void addEventListener(HWEventListener *Listener); Index: tools/llvm-mca/Backend.cpp =================================================================== --- tools/llvm-mca/Backend.cpp +++ tools/llvm-mca/Backend.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "Backend.h" +#include "FetchStage.h" #include "HWEventListener.h" #include "llvm/CodeGen/TargetSchedule.h" #include "llvm/Support/Debug.h" @@ -28,20 +29,22 @@ Listeners.insert(Listener); } +void Backend::run() { + while (InitialStage->isReady() || !DU->isRCUEmpty()) + runCycle(Cycles++); +} + void Backend::runCycle(unsigned Cycle) { notifyCycleBegin(Cycle); - while (SM.hasNext()) { - SourceRef SR = SM.peekNext(); - std::unique_ptr NewIS = IB.createInstruction(*SR.second); - const InstrDesc &Desc = NewIS->getDesc(); - Instruction *IS = NewIS.get(); - InstRef IR(SR.first, IS); + InstRef IR; + while (InitialStage->execute(IR)) { + assert(IR.isValid() && "Invalid InstRef produced by the initial stage."); + const InstrDesc &Desc = IR.getInstruction()->getDesc(); if (!DU->isAvailable(Desc.NumMicroOps) || !DU->canDispatch(IR)) break; - Instructions[SR.first] = std::move(NewIS); DU->dispatch(IR, STI); - SM.updateNext(); + InitialStage->postExecute(IR); } notifyCycleEnd(Cycle); Index: tools/llvm-mca/CMakeLists.txt =================================================================== --- tools/llvm-mca/CMakeLists.txt +++ tools/llvm-mca/CMakeLists.txt @@ -15,6 +15,7 @@ CodeRegion.cpp Dispatch.cpp DispatchStatistics.cpp + FetchStage.cpp HWEventListener.cpp InstrBuilder.cpp Instruction.cpp Index: tools/llvm-mca/Dispatch.cpp =================================================================== --- tools/llvm-mca/Dispatch.cpp +++ tools/llvm-mca/Dispatch.cpp @@ -264,7 +264,6 @@ for (const std::unique_ptr &WS : IR.getInstruction()->getDefs()) RAT->invalidateRegisterMapping(*WS.get(), FreedRegs); Owner->notifyInstructionEvent(HWInstructionRetiredEvent(IR, FreedRegs)); - Owner->eraseInstruction(IR); } bool DispatchUnit::checkRAT(const InstRef &IR) { Index: tools/llvm-mca/FetchStage.h =================================================================== --- /dev/null +++ tools/llvm-mca/FetchStage.h @@ -0,0 +1,43 @@ +//===---------------------- FetchStage.h ------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file defines the Fetch stage of an instruction pipeline. Its sole +/// purpose in life is to produce instructions for the rest of the pipeline. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TOOLS_LLVM_MCA_FETCH_STAGE_H +#define LLVM_TOOLS_LLVM_MCA_FETCH_STAGE_H + +#include "InstrBuilder.h" +#include "Instruction.h" +#include "SourceMgr.h" +#include "Stage.h" + +namespace mca { + +class FetchStage : public Stage { + InstrBuilder &IB; + SourceMgr &SM; + +public: + FetchStage(InstrBuilder &IB, SourceMgr &SM) + : Stage("Fetch Stage"), IB(IB), SM(SM) {} + FetchStage(const FetchStage &Other) = delete; + FetchStage &operator=(const FetchStage &Other) = delete; + + bool isReady() override final; + bool execute(InstRef &IR) override final; + void postExecute(const InstRef &IR) override final; +}; + +} // namespace mca + +#endif // LLVM_TOOLS_LLVM_MCA_FETCH_STAGE_H Index: tools/llvm-mca/FetchStage.cpp =================================================================== --- /dev/null +++ tools/llvm-mca/FetchStage.cpp @@ -0,0 +1,31 @@ +//===---------------------- FetchStage.h ------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file defines the Fetch stage of an instruction pipeline. Its sole +/// purpose in life is to produce instructions for the rest of the pipeline. +/// +//===----------------------------------------------------------------------===// + +#include "FetchStage.h" +#include "Instruction.h" + +using namespace mca; + +bool FetchStage::isReady() { return SM.hasNext(); } + +bool FetchStage::execute(InstRef &IR) { + if (!SM.hasNext()) + return false; + const SourceRef SR = SM.peekNext(); + IR.update(SR.first, IB.createInstruction(*SR.second)); + return true; +} + +void FetchStage::postExecute(const InstRef &IR) { SM.updateNext(); } Index: tools/llvm-mca/InstrBuilder.h =================================================================== --- tools/llvm-mca/InstrBuilder.h +++ tools/llvm-mca/InstrBuilder.h @@ -62,7 +62,7 @@ return ProcResourceMasks; } - std::unique_ptr createInstruction(const llvm::MCInst &MCI); + Instruction *createInstruction(const llvm::MCInst &MCI); }; } // namespace mca Index: tools/llvm-mca/InstrBuilder.cpp =================================================================== --- tools/llvm-mca/InstrBuilder.cpp +++ tools/llvm-mca/InstrBuilder.cpp @@ -427,10 +427,10 @@ return *Descriptors[MCI.getOpcode()]; } -std::unique_ptr +Instruction* InstrBuilder::createInstruction(const MCInst &MCI) { const InstrDesc &D = getOrCreateInstrDesc(MCI); - std::unique_ptr NewIS = llvm::make_unique(D); + Instruction *NewIS = new Instruction(D); // Initialize Reads first. for (const ReadDescriptor &RD : D.Reads) { Index: tools/llvm-mca/Instruction.h =================================================================== --- tools/llvm-mca/Instruction.h +++ tools/llvm-mca/Instruction.h @@ -36,15 +36,22 @@ /// An InstRef contains both a SourceMgr index and Instruction pair. The index /// is used as a unique identifier for the instruction. MCA will make use of /// this index as a key throughout MCA. -class InstRef : public std::pair { +class InstRef : public std::pair> { public: - InstRef() : std::pair(0, nullptr) {} + InstRef() : std::pair>(0, nullptr) {} + InstRef(unsigned Index, std::shared_ptr I) + : std::pair>(Index, I) {} InstRef(unsigned Index, Instruction *I) - : std::pair(Index, I) {} + : InstRef(Index, std::shared_ptr(I)) {} unsigned getSourceIndex() const { return first; } - Instruction *getInstruction() { return second; } - const Instruction *getInstruction() const { return second; } + std::shared_ptr getInstruction() { return second; } + const Instruction *getInstruction() const { return second.get(); } + + void update(unsigned Index, Instruction *Inst) { + first = Index; + second = std::shared_ptr(Inst); + } /// Returns true if this InstRef has been populated. bool isValid() const { return second != nullptr; } Index: tools/llvm-mca/InstructionTables.cpp =================================================================== --- tools/llvm-mca/InstructionTables.cpp +++ tools/llvm-mca/InstructionTables.cpp @@ -31,7 +31,7 @@ while (S.hasNext()) { UsedResources.clear(); SourceRef SR = S.peekNext(); - std::unique_ptr Inst = IB.createInstruction(*SR.second); + Instruction *Inst = IB.createInstruction(*SR.second); const InstrDesc &Desc = Inst->getDesc(); // Now identify the resources consumed by this instruction. for (const std::pair Resource : Desc.Resources) { @@ -39,9 +39,8 @@ if (!Resource.second.size()) continue; double Cycles = static_cast(Resource.second.size()); - unsigned Index = - std::distance(Masks.begin(), std::find(Masks.begin(), Masks.end(), - Resource.first)); + unsigned Index = std::distance( + Masks.begin(), std::find(Masks.begin(), Masks.end(), Resource.first)); const MCProcResourceDesc &ProcResource = *SM.getProcResource(Index); unsigned NumUnits = ProcResource.NumUnits; if (!ProcResource.SubUnitsIdxBegin) { @@ -70,7 +69,7 @@ } // Now send a fake instruction issued event to all the views. - InstRef IR(SR.first, Inst.get()); + InstRef IR(SR.first, Inst); HWInstructionIssuedEvent Event(IR, UsedResources); for (std::unique_ptr &Listener : Views) Listener->onInstructionEvent(Event); Index: tools/llvm-mca/Scheduler.h =================================================================== --- tools/llvm-mca/Scheduler.h +++ tools/llvm-mca/Scheduler.h @@ -413,10 +413,10 @@ // The dispatch unit gets notified when instructions are executed. DispatchUnit *DU; - using QueueEntryTy = std::pair; - std::map WaitQueue; - std::map ReadyQueue; - std::map IssuedQueue; + using QueueEntryTy = std::pair>; + std::map> WaitQueue; + std::map> ReadyQueue; + std::map> IssuedQueue; void notifyInstructionIssued(const InstRef &IR, Index: tools/llvm-mca/Scheduler.cpp =================================================================== --- tools/llvm-mca/Scheduler.cpp +++ tools/llvm-mca/Scheduler.cpp @@ -349,17 +349,14 @@ void Scheduler::issueInstructionImpl( InstRef &IR, SmallVectorImpl> &UsedResources) { - Instruction *IS = IR.getInstruction(); - const InstrDesc &D = IS->getDesc(); - // Issue the instruction and collect all the consumed resources // into a vector. That vector is then used to notify the listener. - Resources->issueInstruction(D, UsedResources); + std::shared_ptr IS = IR.getInstruction(); + Resources->issueInstruction(IS->getDesc(), UsedResources); // Notify the instruction that it started executing. // This updates the internal state of each write. IS->execute(); - if (IS->isExecuting()) IssuedQueue[IR.getSourceIndex()] = IS; } @@ -383,7 +380,7 @@ // ready queue if operands are all ready. for (auto I = WaitQueue.begin(), E = WaitQueue.end(); I != E;) { const unsigned IID = I->first; - Instruction *IS = I->second; + std::shared_ptr IS = I->second; // Check if this instruction is now ready. In case, force // a transition in state using method 'update()'. @@ -417,7 +414,7 @@ return {0, nullptr}; // We found an instruction to issue. - InstRef IR(It->first, It->second); + InstRef IR(It->first, std::shared_ptr(It->second)); ReadyQueue.erase(It); return IR; } @@ -433,7 +430,7 @@ void Scheduler::updateIssuedQueue(SmallVectorImpl &Executed) { for (auto I = IssuedQueue.begin(), E = IssuedQueue.end(); I != E;) { const QueueEntryTy Entry = *I; - Instruction *IS = Entry.second; + std::shared_ptr IS = Entry.second; IS->cycleEvent(); if (IS->isExecuted()) { Executed.push_back({Entry.first, Entry.second}); Index: tools/llvm-mca/Stage.h =================================================================== --- /dev/null +++ tools/llvm-mca/Stage.h @@ -0,0 +1,69 @@ +//===---------------------- Stage.h -----------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file defines a stage. +/// A chain of stages compose an instruction pipeline. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TOOLS_LLVM_MCA_STAGE_H +#define LLVM_TOOLS_LLVM_MCA_STAGE_H + +#include "HWEventListener.h" +#include "Instruction.h" +#include "SourceMgr.h" +#include "llvm/Support/ErrorHandling.h" +#include +#include + +namespace mca { + +class Stage { + std::string Name; + std::set Listeners; + std::unique_ptr NextStage; + +public: + Stage(std::string Name) : Name(Name), NextStage(nullptr) {} + virtual ~Stage() = default; + Stage(const Stage &Other) = delete; + Stage &operator=(const Stage &Other) = delete; + + /// Called prior to preExecute to ensure that the stage can operate. + /// TODO: Remove this logic once backend::run and backend::runCycle become + /// one routine. + virtual bool isReady() { return true; } + + /// Called as a setup phase to prepare for the main stage execution. + virtual void preExecute(const InstRef &IR) {} + + /// Called as a cleanup and finalization phase after main stage execution. + virtual void postExecute(const InstRef &IR) {} + + /// The primary action that this stage performs. + virtual bool execute(InstRef &IR) = 0; + + /// Append the next stage of the pipeline. + void registerNextStage(std::unique_ptr S) { + assert(S && "Invalid stage for registration."); + assert(!NextStage && "Already registered next stage."); + NextStage = std::move(S); + } + + /// Add a listener to receive callbaks during the execution of this stage. + void addListener(HWEventListener *Listener) { + assert(Listener && "Invalid listener instance."); + Listeners.insert(Listener); + llvm::llvm_unreachable_internal("Stage-based eventing is not implemented."); + } +}; + +} // namespace mca +#endif // LLVM_TOOLS_LLVM_MCA_STAGE_H Index: tools/llvm-mca/llvm-mca.cpp =================================================================== --- tools/llvm-mca/llvm-mca.cpp +++ tools/llvm-mca/llvm-mca.cpp @@ -24,6 +24,7 @@ #include "BackendPrinter.h" #include "CodeRegion.h" #include "DispatchStatistics.h" +#include "FetchStage.h" #include "InstructionInfoView.h" #include "InstructionTables.h" #include "RegisterFileStatistics.h" @@ -435,10 +436,17 @@ continue; } - mca::Backend B(*STI, *MRI, IB, S, Width, RegisterFileSize, LoadQueueSize, + mca::Backend B(*STI, *MRI, Width, RegisterFileSize, LoadQueueSize, StoreQueueSize, AssumeNoAlias); mca::BackendPrinter Printer(B); + // Ideally, I'd like to expose the pipeline building here, + // e.g., all of the stages are chained together explictly. + // But for now, it's just this single puppy. + std::unique_ptr Fetch = + llvm::make_unique(IB, S); + B.registerInitialStage(std::move(Fetch)); + Printer.addView(llvm::make_unique(S, Width)); if (PrintInstructionInfoView) Printer.addView(