Index: tools/llvm-mca/Backend.h =================================================================== --- tools/llvm-mca/Backend.h +++ tools/llvm-mca/Backend.h @@ -18,6 +18,9 @@ #include "DispatchStage.h" #include "FetchStage.h" #include "InstrBuilder.h" +#include "RegisterFile.h" +#include "RetireControlUnit.h" +#include "RetireStage.h" #include "Scheduler.h" namespace mca { @@ -51,12 +54,17 @@ /// histograms. For example, it tracks how the dispatch group size changes /// over time. class Backend { - /// This is the initial stage of the pipeline. + // The following are the simulated hardware components of the backend. + RetireControlUnit RCU; + RegisterFile PRF; + /// TODO: Eventually this will become a list of unique Stage* that this /// backend pipeline executes. std::unique_ptr Fetch; std::unique_ptr HWS; std::unique_ptr Dispatch; + std::unique_ptr Retire; + std::set Listeners; unsigned Cycles; @@ -68,15 +76,16 @@ std::unique_ptr InitialStage, unsigned DispatchWidth = 0, unsigned RegisterFileSize = 0, unsigned LoadQueueSize = 0, unsigned StoreQueueSize = 0, bool AssumeNoAlias = false) - : Fetch(std::move(InitialStage)), - HWS(llvm::make_unique(this, Subtarget.getSchedModel(), + : RCU(Subtarget.getSchedModel()), + PRF(Subtarget.getSchedModel(), MRI, RegisterFileSize), + Fetch(std::move(InitialStage)), + HWS(llvm::make_unique(this, Subtarget.getSchedModel(), RCU, LoadQueueSize, StoreQueueSize, AssumeNoAlias)), Dispatch(llvm::make_unique( - this, Subtarget, MRI, RegisterFileSize, DispatchWidth, HWS.get())), - Cycles(0) { - HWS->setDispatchStage(Dispatch.get()); - } + this, Subtarget, MRI, RegisterFileSize, DispatchWidth, RCU, PRF, + HWS.get())), + Retire(llvm::make_unique(this, RCU, PRF)), Cycles(0) {} void run(); void addEventListener(HWEventListener *Listener); Index: tools/llvm-mca/Backend.cpp =================================================================== --- tools/llvm-mca/Backend.cpp +++ tools/llvm-mca/Backend.cpp @@ -37,10 +37,15 @@ void Backend::runCycle(unsigned Cycle) { notifyCycleBegin(Cycle); + // Update the stages before we do any processing for this cycle. InstRef IR; + Retire->preExecute(IR); Dispatch->preExecute(IR); + + // This will execute scheduled instructions. HWS->cycleEvent(); // TODO: This will eventually be stage-ified. + // Fetch instructions and dispatch them to the hardware. while (Fetch->execute(IR)) { if (!Dispatch->execute(IR)) break; Index: tools/llvm-mca/CMakeLists.txt =================================================================== --- tools/llvm-mca/CMakeLists.txt +++ tools/llvm-mca/CMakeLists.txt @@ -28,6 +28,7 @@ ResourcePressureView.cpp RetireControlUnit.cpp RetireControlUnitStatistics.cpp + RetireStage.cpp Scheduler.cpp SchedulerStatistics.cpp Stage.cpp Index: tools/llvm-mca/DispatchStage.h =================================================================== --- tools/llvm-mca/DispatchStage.h +++ tools/llvm-mca/DispatchStage.h @@ -57,16 +57,16 @@ unsigned AvailableEntries; unsigned CarryOver; Scheduler *SC; - std::unique_ptr RAT; - std::unique_ptr RCU; Backend *Owner; const llvm::MCSubtargetInfo &STI; + RetireControlUnit &RCU; + RegisterFile &PRF; - bool checkRAT(const InstRef &IR); bool checkRCU(const InstRef &IR); + bool checkPRF(const InstRef &IR); bool checkScheduler(const InstRef &IR); void dispatch(InstRef IR); - bool isRCUEmpty() const { return RCU->isEmpty(); } + bool isRCUEmpty() const { return RCU.isEmpty(); } void updateRAWDependencies(ReadState &RS, const llvm::MCSubtargetInfo &STI); void notifyInstructionDispatched(const InstRef &IR, @@ -78,36 +78,27 @@ bool canDispatch(const InstRef &IR) { assert(isAvailable(IR.getInstruction()->getDesc().NumMicroOps)); - return checkRCU(IR) && checkRAT(IR) && checkScheduler(IR); + return checkRCU(IR) && checkPRF(IR) && checkScheduler(IR); } void collectWrites(llvm::SmallVectorImpl &Vec, unsigned RegID) const { - return RAT->collectWrites(Vec, RegID); + return PRF.collectWrites(Vec, RegID); } public: DispatchStage(Backend *B, const llvm::MCSubtargetInfo &Subtarget, const llvm::MCRegisterInfo &MRI, unsigned RegisterFileSize, - unsigned MaxDispatchWidth, Scheduler *Sched) + unsigned MaxDispatchWidth, RetireControlUnit &R, + RegisterFile &F, Scheduler *Sched) : DispatchWidth(MaxDispatchWidth), AvailableEntries(MaxDispatchWidth), - CarryOver(0U), SC(Sched), - RAT(llvm::make_unique(Subtarget.getSchedModel(), MRI, - RegisterFileSize)), - RCU(llvm::make_unique(Subtarget.getSchedModel(), - this)), - Owner(B), STI(Subtarget) {} + CarryOver(0U), SC(Sched), Owner(B), STI(Subtarget), RCU(R), PRF(F) {} virtual bool isReady() const override final { return isRCUEmpty(); } virtual void preExecute(const InstRef &IR) override final; virtual bool execute(InstRef &IR) override final; - void notifyInstructionRetired(const InstRef &IR); void notifyDispatchStall(const InstRef &IR, unsigned EventType); - void onInstructionExecuted(unsigned TokenID) { - RCU->onInstructionExecuted(TokenID); - } - #ifndef NDEBUG void dump() const; #endif Index: tools/llvm-mca/DispatchStage.cpp =================================================================== --- tools/llvm-mca/DispatchStage.cpp +++ tools/llvm-mca/DispatchStage.cpp @@ -30,23 +30,13 @@ Owner->notifyInstructionEvent(HWInstructionDispatchedEvent(IR, UsedRegs)); } -void DispatchStage::notifyInstructionRetired(const InstRef &IR) { - LLVM_DEBUG(dbgs() << "[E] Instruction Retired: " << IR << '\n'); - SmallVector FreedRegs(RAT->getNumRegisterFiles()); - const InstrDesc &Desc = IR.getInstruction()->getDesc(); - - for (const std::unique_ptr &WS : IR.getInstruction()->getDefs()) - RAT->removeRegisterWrite(*WS.get(), FreedRegs, !Desc.isZeroLatency()); - Owner->notifyInstructionEvent(HWInstructionRetiredEvent(IR, FreedRegs)); -} - -bool DispatchStage::checkRAT(const InstRef &IR) { +bool DispatchStage::checkPRF(const InstRef &IR) { SmallVector RegDefs; for (const std::unique_ptr &RegDef : IR.getInstruction()->getDefs()) RegDefs.emplace_back(RegDef->getRegisterID()); - unsigned RegisterMask = RAT->isAvailable(RegDefs); + const unsigned RegisterMask = PRF.isAvailable(RegDefs); // A mask with all zeroes means: register files are available. if (RegisterMask) { Owner->notifyStallEvent(HWStallEvent(HWStallEvent::RegisterFileStall, IR)); @@ -58,7 +48,7 @@ bool DispatchStage::checkRCU(const InstRef &IR) { const unsigned NumMicroOps = IR.getInstruction()->getDesc().NumMicroOps; - if (RCU->isAvailable(NumMicroOps)) + if (RCU.isAvailable(NumMicroOps)) return true; Owner->notifyStallEvent( HWStallEvent(HWStallEvent::RetireControlUnitStall, IR)); @@ -125,13 +115,13 @@ // By default, a dependency-breaking zero-latency instruction is expected to // be optimized at register renaming stage. That means, no physical register // is allocated to the instruction. - SmallVector RegisterFiles(RAT->getNumRegisterFiles()); + SmallVector RegisterFiles(PRF.getNumRegisterFiles()); for (std::unique_ptr &WS : IS.getDefs()) - RAT->addRegisterWrite(*WS, RegisterFiles, !Desc.isZeroLatency()); + PRF.addRegisterWrite(*WS, RegisterFiles, !Desc.isZeroLatency()); // 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)); + IS.dispatch(RCU.reserveSlot(IR, NumMicroOps)); // Notify listeners of the "instruction dispatched" event. notifyInstructionDispatched(IR, RegisterFiles); @@ -143,7 +133,6 @@ } void DispatchStage::preExecute(const InstRef &IR) { - RCU->cycleEvent(); AvailableEntries = CarryOver >= DispatchWidth ? 0 : DispatchWidth - CarryOver; CarryOver = CarryOver >= DispatchWidth ? CarryOver - DispatchWidth : 0U; } @@ -158,8 +147,8 @@ #ifndef NDEBUG void DispatchStage::dump() const { - RAT->dump(); - RCU->dump(); + PRF.dump(); + RCU.dump(); } #endif } // namespace mca Index: tools/llvm-mca/RetireControlUnit.h =================================================================== --- tools/llvm-mca/RetireControlUnit.h +++ tools/llvm-mca/RetireControlUnit.h @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// /// \file /// -/// This file implements the logic for retiring instructions. +/// This file simulates the hardware responsible for retiring instructions. /// //===----------------------------------------------------------------------===// @@ -62,27 +62,32 @@ unsigned AvailableSlots; unsigned MaxRetirePerCycle; // 0 means no limit. std::vector Queue; - DispatchStage *Owner; public: - RetireControlUnit(const llvm::MCSchedModel &SM, DispatchStage *DU); + RetireControlUnit(const llvm::MCSchedModel &SM); bool isFull() const { return !AvailableSlots; } bool isEmpty() const { return AvailableSlots == Queue.size(); } bool isAvailable(unsigned Quantity = 1) const { - // Some instructions may declare a number of uOps which exceedes the size + // Some instructions may declare a number of uOps which exceeds the size // of the reorder buffer. To avoid problems, cap the amount of slots to // the size of the reorder buffer. Quantity = std::min(Quantity, static_cast(Queue.size())); return AvailableSlots >= Quantity; } + unsigned getMaxRetirePerCycle() const { return MaxRetirePerCycle; } + // Reserves a number of slots, and returns a new token. unsigned reserveSlot(const InstRef &IS, unsigned NumMicroOps); - /// Retires instructions in program order. - void cycleEvent(); + // Return the current token from the RCU's circular token queue. + const RUToken &peekCurrentToken() const; + + // Advance the pointer to the next token in the circular token queue. + void consumeCurrentToken(); + // Update the RCU token to represent the executed state. void onInstructionExecuted(unsigned TokenID); #ifndef NDEBUG Index: tools/llvm-mca/RetireControlUnit.cpp =================================================================== --- tools/llvm-mca/RetireControlUnit.cpp +++ tools/llvm-mca/RetireControlUnit.cpp @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// /// \file /// -/// This file implements methods declared by the RetireControlUnit interface. +/// This file simulates the hardware responsible for retiring instructions. /// //===----------------------------------------------------------------------===// @@ -22,10 +22,9 @@ namespace mca { -RetireControlUnit::RetireControlUnit(const llvm::MCSchedModel &SM, - DispatchStage *DS) +RetireControlUnit::RetireControlUnit(const llvm::MCSchedModel &SM) : NextAvailableSlotIdx(0), CurrentInstructionSlotIdx(0), - AvailableSlots(SM.MicroOpBufferSize), MaxRetirePerCycle(0), Owner(DS) { + AvailableSlots(SM.MicroOpBufferSize), MaxRetirePerCycle(0) { // Check if the scheduling model provides extra information about the machine // processor. If so, then use that information to set the reorder buffer size // and the maximum number of instructions retired per cycle. @@ -58,25 +57,19 @@ return TokenID; } -void RetireControlUnit::cycleEvent() { - if (isEmpty()) - return; +const RetireControlUnit::RUToken &RetireControlUnit::peekCurrentToken() const { + return Queue[CurrentInstructionSlotIdx]; +} - unsigned NumRetired = 0; - while (!isEmpty()) { - if (MaxRetirePerCycle != 0 && NumRetired == MaxRetirePerCycle) - break; - RUToken &Current = Queue[CurrentInstructionSlotIdx]; - assert(Current.NumSlots && "Reserved zero slots?"); - assert(Current.IR.isValid() && "Invalid RUToken in the RCU queue."); - if (!Current.Executed) - break; - Owner->notifyInstructionRetired(Current.IR); - CurrentInstructionSlotIdx += Current.NumSlots; - CurrentInstructionSlotIdx %= Queue.size(); - AvailableSlots += Current.NumSlots; - NumRetired++; - } +void RetireControlUnit::consumeCurrentToken() { + const RetireControlUnit::RUToken &Current = peekCurrentToken(); + assert(Current.NumSlots && "Reserved zero slots?"); + assert(Current.IR.isValid() && "Invalid RUToken in the RCU queue."); + + // Update the slot index to be the next item in the circular queue. + CurrentInstructionSlotIdx += Current.NumSlots; + CurrentInstructionSlotIdx %= Queue.size(); + AvailableSlots += Current.NumSlots; } void RetireControlUnit::onInstructionExecuted(unsigned TokenID) { Index: tools/llvm-mca/RetireStage.h =================================================================== --- /dev/null +++ tools/llvm-mca/RetireStage.h @@ -0,0 +1,48 @@ +//===---------------------- RetireStage.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 retire stage of an instruction pipeline. +/// The RetireStage represents the process logic that interacts with the +/// simulated RetireControlUnit hardware. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TOOLS_LLVM_MCA_RETIRE_STAGE_H +#define LLVM_TOOLS_LLVM_MCA_RETIRE_STAGE_H + +#include "RegisterFile.h" +#include "RetireControlUnit.h" +#include "Stage.h" + +namespace mca { + +class Backend; + +class RetireStage : public Stage { + // Owner will go away when we move listeners/eventing to the stages. + Backend *Owner; + RetireControlUnit &RCU; + RegisterFile &PRF; + +public: + RetireStage(Backend *B, RetireControlUnit &R, RegisterFile &F) + : Stage(), Owner(B), RCU(R), PRF(F) {} + RetireStage(const RetireStage &Other) = delete; + RetireStage &operator=(const RetireStage &Other) = delete; + + virtual void preExecute(const InstRef &IR) override final; + virtual bool execute(InstRef &IR) override final { return true; } + void notifyInstructionRetired(const InstRef &IR); + void onInstructionExecuted(unsigned TokenID); +}; + +} // namespace mca + +#endif // LLVM_TOOLS_LLVM_MCA_RETIRE_STAGE_H Index: tools/llvm-mca/RetireStage.cpp =================================================================== --- /dev/null +++ tools/llvm-mca/RetireStage.cpp @@ -0,0 +1,56 @@ +//===---------------------- RetireStage.cpp ---------------------*- 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 retire stage of an instruction pipeline. +/// The RetireStage represents the process logic that interacts with the +/// simulated RetireControlUnit hardware. +/// +//===----------------------------------------------------------------------===// + +#include "RetireStage.h" +#include "Backend.h" +#include "HWEventListener.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; + +#define DEBUG_TYPE "llvm-mca" + +namespace mca { + +void RetireStage::preExecute(const InstRef &IR) { + if (RCU.isEmpty()) + return; + + const unsigned MaxRetirePerCycle = RCU.getMaxRetirePerCycle(); + unsigned NumRetired = 0; + while (!RCU.isEmpty()) { + if (MaxRetirePerCycle != 0 && NumRetired == MaxRetirePerCycle) + break; + const RetireControlUnit::RUToken &Current = RCU.peekCurrentToken(); + if (!Current.Executed) + break; + RCU.consumeCurrentToken(); + notifyInstructionRetired(Current.IR); + NumRetired++; + } +} + +void RetireStage::notifyInstructionRetired(const InstRef &IR) { + LLVM_DEBUG(dbgs() << "[E] Instruction Retired: " << IR << '\n'); + SmallVector FreedRegs(PRF.getNumRegisterFiles()); + const InstrDesc &Desc = IR.getInstruction()->getDesc(); + + for (const std::unique_ptr &WS : IR.getInstruction()->getDefs()) + PRF.removeRegisterWrite(*WS.get(), FreedRegs, !Desc.isZeroLatency()); + Owner->notifyInstructionEvent(HWInstructionRetiredEvent(IR, FreedRegs)); +} + +} // namespace mca Index: tools/llvm-mca/Scheduler.h =================================================================== --- tools/llvm-mca/Scheduler.h +++ tools/llvm-mca/Scheduler.h @@ -17,6 +17,7 @@ #include "Instruction.h" #include "LSUnit.h" +#include "RetireControlUnit.h" #include "llvm/ADT/DenseMap.h" #include "llvm/MC/MCSubtargetInfo.h" #include @@ -24,7 +25,6 @@ namespace mca { class Backend; -class DispatchStage; /// Used to notify the internal state of a processor resource. /// @@ -402,6 +402,7 @@ /// An Instruction leaves the IssuedQueue when it reaches the write-back stage. class Scheduler { const llvm::MCSchedModel &SM; + RetireControlUnit &RCU; // Hardware resources that are managed by this scheduler. std::unique_ptr Resources; @@ -410,9 +411,6 @@ // The Backend gets notified when instructions are ready/issued/executed. Backend *const Owner; - // The dispatch unit gets notified when instructions are executed. - DispatchStage *DS; - using QueueEntryTy = std::pair; std::map WaitQueue; std::map ReadyQueue; @@ -447,15 +445,13 @@ void updateIssuedQueue(llvm::SmallVectorImpl &Executed); public: - Scheduler(Backend *B, const llvm::MCSchedModel &Model, unsigned LoadQueueSize, - unsigned StoreQueueSize, bool AssumeNoAlias) - : SM(Model), Resources(llvm::make_unique(SM)), + Scheduler(Backend *B, const llvm::MCSchedModel &Model, RetireControlUnit &R, + unsigned LoadQueueSize, unsigned StoreQueueSize, bool AssumeNoAlias) + : SM(Model), RCU(R), Resources(llvm::make_unique(SM)), LSU(llvm::make_unique(LoadQueueSize, StoreQueueSize, AssumeNoAlias)), Owner(B) {} - void setDispatchStage(DispatchStage *DispStage) { DS = DispStage; } - /// Check if the instruction in 'IR' can be dispatched. /// /// The DispatchStage is responsible for querying the Scheduler before Index: tools/llvm-mca/Scheduler.cpp =================================================================== --- tools/llvm-mca/Scheduler.cpp +++ tools/llvm-mca/Scheduler.cpp @@ -468,7 +468,7 @@ LLVM_DEBUG(dbgs() << "[E] Instruction Executed: " << IR << '\n'); Owner->notifyInstructionEvent( HWInstructionEvent(HWInstructionEvent::Executed, IR)); - DS->onInstructionExecuted(IR.getInstruction()->getRCUTokenID()); + RCU.onInstructionExecuted(IR.getInstruction()->getRCUTokenID()); } void Scheduler::notifyInstructionReady(const InstRef &IR) {