Index: tools/llvm-mca/CMakeLists.txt =================================================================== --- tools/llvm-mca/CMakeLists.txt +++ tools/llvm-mca/CMakeLists.txt @@ -1,3 +1,5 @@ +include_directories(include) + set(LLVM_LINK_COMPONENTS AllTargetsAsmPrinters AllTargetsAsmParsers @@ -10,33 +12,20 @@ ) add_llvm_tool(llvm-mca - CodeRegion.cpp - Context.cpp - DispatchStage.cpp - DispatchStatistics.cpp - ExecuteStage.cpp - FetchStage.cpp - HWEventListener.cpp - HardwareUnit.cpp - InstrBuilder.cpp - Instruction.cpp - InstructionInfoView.cpp - InstructionTables.cpp - LSUnit.cpp llvm-mca.cpp - Pipeline.cpp + CodeRegion.cpp PipelinePrinter.cpp - RegisterFile.cpp - RegisterFileStatistics.cpp - ResourcePressureView.cpp - RetireControlUnit.cpp - RetireControlUnitStatistics.cpp - RetireStage.cpp - Scheduler.cpp - SchedulerStatistics.cpp - Stage.cpp - Support.cpp - SummaryView.cpp - TimelineView.cpp - View.cpp + Stats/DispatchStatistics.cpp + Stats/RegisterFileStatistics.cpp + Stats/RetireControlUnitStatistics.cpp + Stats/SchedulerStatistics.cpp + Views/InstructionInfoView.cpp + Views/ResourcePressureView.cpp + Views/SummaryView.cpp + Views/TimelineView.cpp + Views/View.cpp ) + +set(LLVM_MCA_SOURCE_DIR ${CURRENT_SOURCE_DIR}) +add_subdirectory(lib) +target_link_libraries(llvm-mca PRIVATE LLVMMCA) Index: tools/llvm-mca/PipelinePrinter.h =================================================================== --- tools/llvm-mca/PipelinePrinter.h +++ tools/llvm-mca/PipelinePrinter.h @@ -17,8 +17,8 @@ #ifndef LLVM_TOOLS_LLVM_MCA_PIPELINEPRINTER_H #define LLVM_TOOLS_LLVM_MCA_PIPELINEPRINTER_H -#include "Pipeline.h" -#include "View.h" +#include "Views/View.h" +#include "include/Pipeline.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/raw_ostream.h" Index: tools/llvm-mca/PipelinePrinter.cpp =================================================================== --- tools/llvm-mca/PipelinePrinter.cpp +++ tools/llvm-mca/PipelinePrinter.cpp @@ -13,7 +13,7 @@ //===----------------------------------------------------------------------===// #include "PipelinePrinter.h" -#include "View.h" +#include "Views/View.h" namespace mca { Index: tools/llvm-mca/Stats/DispatchStatistics.h =================================================================== --- tools/llvm-mca/Stats/DispatchStatistics.h +++ tools/llvm-mca/Stats/DispatchStatistics.h @@ -34,7 +34,7 @@ #ifndef LLVM_TOOLS_LLVM_MCA_DISPATCHVIEW_H #define LLVM_TOOLS_LLVM_MCA_DISPATCHVIEW_H -#include "View.h" +#include "Views/View.h" #include "llvm/ADT/SmallVector.h" #include "llvm/MC/MCSubtargetInfo.h" #include Index: tools/llvm-mca/Stats/DispatchStatistics.cpp =================================================================== --- tools/llvm-mca/Stats/DispatchStatistics.cpp +++ tools/llvm-mca/Stats/DispatchStatistics.cpp @@ -13,7 +13,7 @@ /// //===----------------------------------------------------------------------===// -#include "DispatchStatistics.h" +#include "Stats/DispatchStatistics.h" #include "llvm/Support/Format.h" using namespace llvm; Index: tools/llvm-mca/Stats/RegisterFileStatistics.h =================================================================== --- tools/llvm-mca/Stats/RegisterFileStatistics.h +++ tools/llvm-mca/Stats/RegisterFileStatistics.h @@ -32,7 +32,7 @@ #ifndef LLVM_TOOLS_LLVM_MCA_REGISTERFILESTATISTICS_H #define LLVM_TOOLS_LLVM_MCA_REGISTERFILESTATISTICS_H -#include "View.h" +#include "Views/View.h" #include "llvm/ADT/SmallVector.h" #include "llvm/MC/MCSubtargetInfo.h" Index: tools/llvm-mca/Stats/RegisterFileStatistics.cpp =================================================================== --- tools/llvm-mca/Stats/RegisterFileStatistics.cpp +++ tools/llvm-mca/Stats/RegisterFileStatistics.cpp @@ -12,7 +12,7 @@ /// //===----------------------------------------------------------------------===// -#include "RegisterFileStatistics.h" +#include "Stats/RegisterFileStatistics.h" #include "llvm/Support/Format.h" using namespace llvm; Index: tools/llvm-mca/Stats/RetireControlUnitStatistics.h =================================================================== --- tools/llvm-mca/Stats/RetireControlUnitStatistics.h +++ tools/llvm-mca/Stats/RetireControlUnitStatistics.h @@ -26,7 +26,7 @@ #ifndef LLVM_TOOLS_LLVM_MCA_RETIRECONTROLUNITSTATISTICS_H #define LLVM_TOOLS_LLVM_MCA_RETIRECONTROLUNITSTATISTICS_H -#include "View.h" +#include "Views/View.h" #include "llvm/MC/MCSubtargetInfo.h" #include Index: tools/llvm-mca/Stats/RetireControlUnitStatistics.cpp =================================================================== --- tools/llvm-mca/Stats/RetireControlUnitStatistics.cpp +++ tools/llvm-mca/Stats/RetireControlUnitStatistics.cpp @@ -12,7 +12,7 @@ /// //===----------------------------------------------------------------------===// -#include "RetireControlUnitStatistics.h" +#include "Stats/RetireControlUnitStatistics.h" #include "llvm/Support/Format.h" using namespace llvm; Index: tools/llvm-mca/Stats/SchedulerStatistics.h =================================================================== --- tools/llvm-mca/Stats/SchedulerStatistics.h +++ tools/llvm-mca/Stats/SchedulerStatistics.h @@ -31,7 +31,7 @@ #ifndef LLVM_TOOLS_LLVM_MCA_SCHEDULERSTATISTICS_H #define LLVM_TOOLS_LLVM_MCA_SCHEDULERSTATISTICS_H -#include "View.h" +#include "Views/View.h" #include "llvm/ADT/SmallVector.h" #include "llvm/MC/MCSubtargetInfo.h" #include Index: tools/llvm-mca/Stats/SchedulerStatistics.cpp =================================================================== --- tools/llvm-mca/Stats/SchedulerStatistics.cpp +++ tools/llvm-mca/Stats/SchedulerStatistics.cpp @@ -12,7 +12,7 @@ /// //===----------------------------------------------------------------------===// -#include "SchedulerStatistics.h" +#include "Stats/SchedulerStatistics.h" #include "llvm/Support/Format.h" using namespace llvm; Index: tools/llvm-mca/Views/InstructionInfoView.h =================================================================== --- tools/llvm-mca/Views/InstructionInfoView.h +++ tools/llvm-mca/Views/InstructionInfoView.h @@ -35,8 +35,8 @@ #ifndef LLVM_TOOLS_LLVM_MCA_INSTRUCTIONINFOVIEW_H #define LLVM_TOOLS_LLVM_MCA_INSTRUCTIONINFOVIEW_H -#include "SourceMgr.h" -#include "View.h" +#include "Views/View.h" +#include "include/SourceMgr.h" #include "llvm/MC/MCInstPrinter.h" #include "llvm/MC/MCInstrInfo.h" #include "llvm/MC/MCSubtargetInfo.h" Index: tools/llvm-mca/Views/InstructionInfoView.cpp =================================================================== --- tools/llvm-mca/Views/InstructionInfoView.cpp +++ tools/llvm-mca/Views/InstructionInfoView.cpp @@ -12,7 +12,7 @@ /// //===----------------------------------------------------------------------===// -#include "InstructionInfoView.h" +#include "Views/InstructionInfoView.h" namespace mca { Index: tools/llvm-mca/Views/ResourcePressureView.h =================================================================== --- tools/llvm-mca/Views/ResourcePressureView.h +++ tools/llvm-mca/Views/ResourcePressureView.h @@ -58,8 +58,8 @@ #ifndef LLVM_TOOLS_LLVM_MCA_RESOURCEPRESSUREVIEW_H #define LLVM_TOOLS_LLVM_MCA_RESOURCEPRESSUREVIEW_H -#include "SourceMgr.h" -#include "View.h" +#include "Views/View.h" +#include "include/SourceMgr.h" #include "llvm/ADT/DenseMap.h" #include "llvm/MC/MCInstPrinter.h" #include "llvm/MC/MCSubtargetInfo.h" Index: tools/llvm-mca/Views/ResourcePressureView.cpp =================================================================== --- tools/llvm-mca/Views/ResourcePressureView.cpp +++ tools/llvm-mca/Views/ResourcePressureView.cpp @@ -12,7 +12,7 @@ /// //===----------------------------------------------------------------------===// -#include "ResourcePressureView.h" +#include "Views/ResourcePressureView.h" #include "llvm/Support/FormattedStream.h" #include "llvm/Support/raw_ostream.h" Index: tools/llvm-mca/Views/SummaryView.h =================================================================== --- tools/llvm-mca/Views/SummaryView.h +++ tools/llvm-mca/Views/SummaryView.h @@ -29,8 +29,8 @@ #ifndef LLVM_TOOLS_LLVM_MCA_SUMMARYVIEW_H #define LLVM_TOOLS_LLVM_MCA_SUMMARYVIEW_H -#include "SourceMgr.h" -#include "View.h" +#include "Views/View.h" +#include "include/SourceMgr.h" #include "llvm/ADT/DenseMap.h" #include "llvm/MC/MCSchedule.h" #include "llvm/Support/raw_ostream.h" Index: tools/llvm-mca/Views/SummaryView.cpp =================================================================== --- tools/llvm-mca/Views/SummaryView.cpp +++ tools/llvm-mca/Views/SummaryView.cpp @@ -13,8 +13,8 @@ /// //===----------------------------------------------------------------------===// -#include "SummaryView.h" -#include "Support.h" +#include "Views/SummaryView.h" +#include "include/Support.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Format.h" Index: tools/llvm-mca/Views/TimelineView.h =================================================================== --- tools/llvm-mca/Views/TimelineView.h +++ tools/llvm-mca/Views/TimelineView.h @@ -100,8 +100,8 @@ #ifndef LLVM_TOOLS_LLVM_MCA_TIMELINEVIEW_H #define LLVM_TOOLS_LLVM_MCA_TIMELINEVIEW_H -#include "SourceMgr.h" -#include "View.h" +#include "Views/View.h" +#include "include/SourceMgr.h" #include "llvm/MC/MCInstPrinter.h" #include "llvm/MC/MCSubtargetInfo.h" #include "llvm/Support/FormattedStream.h" Index: tools/llvm-mca/Views/TimelineView.cpp =================================================================== --- tools/llvm-mca/Views/TimelineView.cpp +++ tools/llvm-mca/Views/TimelineView.cpp @@ -12,7 +12,7 @@ /// //===----------------------------------------------------------------------===// -#include "TimelineView.h" +#include "Views/TimelineView.h" using namespace llvm; Index: tools/llvm-mca/Views/View.h =================================================================== --- tools/llvm-mca/Views/View.h +++ tools/llvm-mca/Views/View.h @@ -16,7 +16,7 @@ #ifndef LLVM_TOOLS_LLVM_MCA_VIEW_H #define LLVM_TOOLS_LLVM_MCA_VIEW_H -#include "HWEventListener.h" +#include "include/HWEventListener.h" #include "llvm/Support/raw_ostream.h" namespace mca { Index: tools/llvm-mca/Views/View.cpp =================================================================== --- tools/llvm-mca/Views/View.cpp +++ tools/llvm-mca/Views/View.cpp @@ -12,7 +12,7 @@ /// //===----------------------------------------------------------------------===// -#include "View.h" +#include "Views/View.h" namespace mca { Index: tools/llvm-mca/include/Context.h =================================================================== --- tools/llvm-mca/include/Context.h +++ tools/llvm-mca/include/Context.h @@ -17,7 +17,7 @@ #ifndef LLVM_TOOLS_LLVM_MCA_CONTEXT_H #define LLVM_TOOLS_LLVM_MCA_CONTEXT_H -#include "HardwareUnit.h" +#include "HardwareUnits/HardwareUnit.h" #include "InstrBuilder.h" #include "Pipeline.h" #include "SourceMgr.h" Index: tools/llvm-mca/include/HardwareUnits/RegisterFile.h =================================================================== --- tools/llvm-mca/include/HardwareUnits/RegisterFile.h +++ tools/llvm-mca/include/HardwareUnits/RegisterFile.h @@ -17,7 +17,7 @@ #ifndef LLVM_TOOLS_LLVM_MCA_REGISTER_FILE_H #define LLVM_TOOLS_LLVM_MCA_REGISTER_FILE_H -#include "HardwareUnit.h" +#include "HardwareUnits/HardwareUnit.h" #include "llvm/ADT/SmallVector.h" #include "llvm/MC/MCRegisterInfo.h" #include "llvm/MC/MCSchedule.h" Index: tools/llvm-mca/include/HardwareUnits/ResourceManager.h =================================================================== --- tools/llvm-mca/include/HardwareUnits/ResourceManager.h +++ tools/llvm-mca/include/HardwareUnits/ResourceManager.h @@ -1,4 +1,4 @@ -//===--------------------- Scheduler.h ------------------------*- C++ -*-===// +//===--------------------- ResourceManager.h --------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -8,21 +8,19 @@ //===----------------------------------------------------------------------===// /// \file /// -/// A scheduler for Processor Resource Units and Processor Resource Groups. +/// The classes here represent processor resource units and their management +/// strategy. These classes are managed by the Scheduler. /// //===----------------------------------------------------------------------===// -#ifndef LLVM_TOOLS_LLVM_MCA_SCHEDULER_H -#define LLVM_TOOLS_LLVM_MCA_SCHEDULER_H +#ifndef LLVM_TOOLS_LLVM_MCA_RESOURCE_MANAGER_H +#define LLVM_TOOLS_LLVM_MCA_RESOURCE_MANAGER_H -#include "HardwareUnit.h" #include "Instruction.h" -#include "LSUnit.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/MC/MCSubtargetInfo.h" -#include +#include "llvm/MC/MCSchedule.h" namespace mca { @@ -356,192 +354,7 @@ Resource->dump(); } #endif -}; // namespace mca - -class SchedulerStrategy { -public: - SchedulerStrategy() = default; - virtual ~SchedulerStrategy(); - - /// Returns true if Lhs should take priority over Rhs. - /// - /// This method is used by class Scheduler to select the "best" ready - /// instruction to issue to the underlying pipelines. - virtual bool compare(const InstRef &Lhs, const InstRef &Rhs) const = 0; -}; - -/// Default instruction selection strategy used by class Scheduler. -class DefaultSchedulerStrategy : public SchedulerStrategy { - /// This method ranks instructions based on their age, and the number of known - /// users. The lower the rank value, the better. - int computeRank(const InstRef &Lhs) const { - return Lhs.getSourceIndex() - Lhs.getInstruction()->getNumUsers(); - } - -public: - DefaultSchedulerStrategy() = default; - virtual ~DefaultSchedulerStrategy(); - - bool compare(const InstRef &Lhs, const InstRef &Rhs) const override { - int LhsRank = computeRank(Lhs); - int RhsRank = computeRank(Rhs); - - /// Prioritize older instructions over younger instructions to minimize the - /// pressure on the reorder buffer. - if (LhsRank == RhsRank) - return Lhs.getSourceIndex() < Rhs.getSourceIndex(); - return LhsRank < RhsRank; - } -}; - -/// Class Scheduler is responsible for issuing instructions to pipeline -/// resources. -/// -/// Internally, it delegates to a ResourceManager the management of processor -/// resources. This class is also responsible for tracking the progress of -/// instructions from the dispatch stage, until the write-back stage. -/// -/// An instruction dispatched to the Scheduler is initially placed into either -/// the 'WaitSet' or the 'ReadySet' depending on the availability of the input -/// operands. -/// -/// An instruction is moved from the WaitSet to the ReadySet when register -/// operands become available, and all memory dependencies are met. -/// Instructions that are moved from the WaitSet to the ReadySet transition -/// in state from 'IS_AVAILABLE' to 'IS_READY'. -/// -/// On every cycle, the Scheduler checks if it can promote instructions from the -/// WaitSet to the ReadySet. -/// -/// An Instruction is moved from the ReadySet the `IssuedSet` when it is issued -/// to a (one or more) pipeline(s). This event also causes an instruction state -/// transition (i.e. from state IS_READY, to state IS_EXECUTING). An Instruction -/// leaves the IssuedSet when it reaches the write-back stage. -class Scheduler : public HardwareUnit { - LSUnit *LSU; - - // Instruction selection strategy for this Scheduler. - std::unique_ptr Strategy; - - // Hardware resources that are managed by this scheduler. - std::unique_ptr Resources; - - std::vector WaitSet; - std::vector ReadySet; - std::vector IssuedSet; - - /// Verify the given selection strategy and set the Strategy member - /// accordingly. If no strategy is provided, the DefaultSchedulerStrategy is - /// used. - void initializeStrategy(std::unique_ptr S); - - /// Issue an instruction without updating the ready queue. - void issueInstructionImpl( - InstRef &IR, - llvm::SmallVectorImpl> &Pipes); - - // Identify instructions that have finished executing, and remove them from - // the IssuedSet. References to executed instructions are added to input - // vector 'Executed'. - void updateIssuedSet(llvm::SmallVectorImpl &Executed); - - // Try to promote instructions from WaitSet to ReadySet. - // Add promoted instructions to the 'Ready' vector in input. - void promoteToReadySet(llvm::SmallVectorImpl &Ready); - -public: - Scheduler(const llvm::MCSchedModel &Model, LSUnit *Lsu) - : LSU(Lsu), Resources(llvm::make_unique(Model)) { - initializeStrategy(nullptr); - } - Scheduler(const llvm::MCSchedModel &Model, LSUnit *Lsu, - std::unique_ptr SelectStrategy) - : LSU(Lsu), Resources(llvm::make_unique(Model)) { - initializeStrategy(std::move(SelectStrategy)); - } - Scheduler(std::unique_ptr RM, LSUnit *Lsu, - std::unique_ptr SelectStrategy) - : LSU(Lsu), Resources(std::move(RM)) { - initializeStrategy(std::move(SelectStrategy)); - } - - // Stalls generated by the scheduler. - enum Status { - SC_AVAILABLE, - SC_LOAD_QUEUE_FULL, - SC_STORE_QUEUE_FULL, - SC_BUFFERS_FULL, - SC_DISPATCH_GROUP_STALL, - }; - - /// Check if the instruction in 'IR' can be dispatched and returns an answer - /// in the form of a Status value. - /// - /// The DispatchStage is responsible for querying the Scheduler before - /// dispatching new instructions. This routine is used for performing such - /// a query. If the instruction 'IR' can be dispatched, then true is - /// returned, otherwise false is returned with Event set to the stall type. - /// Internally, it also checks if the load/store unit is available. - Status isAvailable(const InstRef &IR) const; - - /// Reserves buffer and LSUnit queue resources that are necessary to issue - /// this instruction. - /// - /// Returns true if instruction IR is ready to be issued to the underlying - /// pipelines. Note that this operation cannot fail; it assumes that a - /// previous call to method `isAvailable(IR)` returned `SC_AVAILABLE`. - void dispatch(const InstRef &IR); - - /// Returns true if IR is ready to be executed by the underlying pipelines. - /// This method assumes that IR has been previously dispatched. - bool isReady(const InstRef &IR) const; - - /// Issue an instruction and populates a vector of used pipeline resources, - /// and a vector of instructions that transitioned to the ready state as a - /// result of this event. - void - issueInstruction(InstRef &IR, - llvm::SmallVectorImpl> &Used, - llvm::SmallVectorImpl &Ready); - - /// Returns true if IR has to be issued immediately, or if IR is a zero - /// latency instruction. - bool mustIssueImmediately(const InstRef &IR) const; - - /// This routine notifies the Scheduler that a new cycle just started. - /// - /// It notifies the underlying ResourceManager that a new cycle just started. - /// Vector `Freed` is populated with resourceRef related to resources that - /// have changed in state, and that are now available to new instructions. - /// Instructions executed are added to vector Executed, while vector Ready is - /// populated with instructions that have become ready in this new cycle. - void cycleEvent(llvm::SmallVectorImpl &Freed, - llvm::SmallVectorImpl &Ready, - llvm::SmallVectorImpl &Executed); - - /// Convert a resource mask into a valid llvm processor resource identifier. - unsigned getResourceID(uint64_t Mask) const { - return Resources->resolveResourceMask(Mask); - } - - /// Select the next instruction to issue from the ReadySet. Returns an invalid - /// instruction reference if there are no ready instructions, or if processor - /// resources are not available. - InstRef select(); - -#ifndef NDEBUG - // Update the ready queues. - void dump() const; - - // This routine performs a sanity check. This routine should only be called - // when we know that 'IR' is not in the scheduler's instruction queues. - void sanityCheck(const InstRef &IR) const { - assert(llvm::find(WaitSet, IR) == WaitSet.end()); - assert(llvm::find(ReadySet, IR) == ReadySet.end()); - assert(llvm::find(IssuedSet, IR) == IssuedSet.end()); - } -#endif // !NDEBUG }; } // namespace mca -#endif // LLVM_TOOLS_LLVM_MCA_SCHEDULER_H +#endif // LLVM_TOOLS_LLVM_MCA_RESOURCE_MANAGER_H Index: tools/llvm-mca/include/HardwareUnits/Scheduler.h =================================================================== --- /dev/null +++ tools/llvm-mca/include/HardwareUnits/Scheduler.h @@ -0,0 +1,212 @@ +//===--------------------- Scheduler.h ------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// A scheduler for Processor Resource Units and Processor Resource Groups. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TOOLS_LLVM_MCA_SCHEDULER_H +#define LLVM_TOOLS_LLVM_MCA_SCHEDULER_H + +#include "HardwareUnit.h" +#include "HardwareUnits/ResourceManager.h" +#include "HardwareUnits/LSUnit.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/MC/MCSchedule.h" + +namespace mca { + +class SchedulerStrategy { +public: + SchedulerStrategy() = default; + virtual ~SchedulerStrategy(); + + /// Returns true if Lhs should take priority over Rhs. + /// + /// This method is used by class Scheduler to select the "best" ready + /// instruction to issue to the underlying pipelines. + virtual bool compare(const InstRef &Lhs, const InstRef &Rhs) const = 0; +}; + +/// Default instruction selection strategy used by class Scheduler. +class DefaultSchedulerStrategy : public SchedulerStrategy { + /// This method ranks instructions based on their age, and the number of known + /// users. The lower the rank value, the better. + int computeRank(const InstRef &Lhs) const { + return Lhs.getSourceIndex() - Lhs.getInstruction()->getNumUsers(); + } + +public: + DefaultSchedulerStrategy() = default; + virtual ~DefaultSchedulerStrategy(); + + bool compare(const InstRef &Lhs, const InstRef &Rhs) const override { + int LhsRank = computeRank(Lhs); + int RhsRank = computeRank(Rhs); + + /// Prioritize older instructions over younger instructions to minimize the + /// pressure on the reorder buffer. + if (LhsRank == RhsRank) + return Lhs.getSourceIndex() < Rhs.getSourceIndex(); + return LhsRank < RhsRank; + } +}; + +/// Class Scheduler is responsible for issuing instructions to pipeline +/// resources. +/// +/// Internally, it delegates to a ResourceManager the management of processor +/// resources. This class is also responsible for tracking the progress of +/// instructions from the dispatch stage, until the write-back stage. +/// +/// An instruction dispatched to the Scheduler is initially placed into either +/// the 'WaitSet' or the 'ReadySet' depending on the availability of the input +/// operands. +/// +/// An instruction is moved from the WaitSet to the ReadySet when register +/// operands become available, and all memory dependencies are met. +/// Instructions that are moved from the WaitSet to the ReadySet transition +/// in state from 'IS_AVAILABLE' to 'IS_READY'. +/// +/// On every cycle, the Scheduler checks if it can promote instructions from the +/// WaitSet to the ReadySet. +/// +/// An Instruction is moved from the ReadySet the `IssuedSet` when it is issued +/// to a (one or more) pipeline(s). This event also causes an instruction state +/// transition (i.e. from state IS_READY, to state IS_EXECUTING). An Instruction +/// leaves the IssuedSet when it reaches the write-back stage. +class Scheduler : public HardwareUnit { + LSUnit *LSU; + + // Instruction selection strategy for this Scheduler. + std::unique_ptr Strategy; + + // Hardware resources that are managed by this scheduler. + std::unique_ptr Resources; + + std::vector WaitSet; + std::vector ReadySet; + std::vector IssuedSet; + + /// Verify the given selection strategy and set the Strategy member + /// accordingly. If no strategy is provided, the DefaultSchedulerStrategy is + /// used. + void initializeStrategy(std::unique_ptr S); + + /// Issue an instruction without updating the ready queue. + void issueInstructionImpl( + InstRef &IR, + llvm::SmallVectorImpl> &Pipes); + + // Identify instructions that have finished executing, and remove them from + // the IssuedSet. References to executed instructions are added to input + // vector 'Executed'. + void updateIssuedSet(llvm::SmallVectorImpl &Executed); + + // Try to promote instructions from WaitSet to ReadySet. + // Add promoted instructions to the 'Ready' vector in input. + void promoteToReadySet(llvm::SmallVectorImpl &Ready); + +public: + Scheduler(const llvm::MCSchedModel &Model, LSUnit *Lsu) + : LSU(Lsu), Resources(llvm::make_unique(Model)) { + initializeStrategy(nullptr); + } + Scheduler(const llvm::MCSchedModel &Model, LSUnit *Lsu, + std::unique_ptr SelectStrategy) + : LSU(Lsu), Resources(llvm::make_unique(Model)) { + initializeStrategy(std::move(SelectStrategy)); + } + Scheduler(std::unique_ptr RM, LSUnit *Lsu, + std::unique_ptr SelectStrategy) + : LSU(Lsu), Resources(std::move(RM)) { + initializeStrategy(std::move(SelectStrategy)); + } + + // Stalls generated by the scheduler. + enum Status { + SC_AVAILABLE, + SC_LOAD_QUEUE_FULL, + SC_STORE_QUEUE_FULL, + SC_BUFFERS_FULL, + SC_DISPATCH_GROUP_STALL, + }; + + /// Check if the instruction in 'IR' can be dispatched and returns an answer + /// in the form of a Status value. + /// + /// The DispatchStage is responsible for querying the Scheduler before + /// dispatching new instructions. This routine is used for performing such + /// a query. If the instruction 'IR' can be dispatched, then true is + /// returned, otherwise false is returned with Event set to the stall type. + /// Internally, it also checks if the load/store unit is available. + Status isAvailable(const InstRef &IR) const; + + /// Reserves buffer and LSUnit queue resources that are necessary to issue + /// this instruction. + /// + /// Returns true if instruction IR is ready to be issued to the underlying + /// pipelines. Note that this operation cannot fail; it assumes that a + /// previous call to method `isAvailable(IR)` returned `SC_AVAILABLE`. + void dispatch(const InstRef &IR); + + /// Returns true if IR is ready to be executed by the underlying pipelines. + /// This method assumes that IR has been previously dispatched. + bool isReady(const InstRef &IR) const; + + /// Issue an instruction and populates a vector of used pipeline resources, + /// and a vector of instructions that transitioned to the ready state as a + /// result of this event. + void + issueInstruction(InstRef &IR, + llvm::SmallVectorImpl> &Used, + llvm::SmallVectorImpl &Ready); + + /// Returns true if IR has to be issued immediately, or if IR is a zero + /// latency instruction. + bool mustIssueImmediately(const InstRef &IR) const; + + /// This routine notifies the Scheduler that a new cycle just started. + /// + /// It notifies the underlying ResourceManager that a new cycle just started. + /// Vector `Freed` is populated with resourceRef related to resources that + /// have changed in state, and that are now available to new instructions. + /// Instructions executed are added to vector Executed, while vector Ready is + /// populated with instructions that have become ready in this new cycle. + void cycleEvent(llvm::SmallVectorImpl &Freed, + llvm::SmallVectorImpl &Ready, + llvm::SmallVectorImpl &Executed); + + /// Convert a resource mask into a valid llvm processor resource identifier. + unsigned getResourceID(uint64_t Mask) const { + return Resources->resolveResourceMask(Mask); + } + + /// Select the next instruction to issue from the ReadySet. Returns an invalid + /// instruction reference if there are no ready instructions, or if processor + /// resources are not available. + InstRef select(); + +#ifndef NDEBUG + // Update the ready queues. + void dump() const; + + // This routine performs a sanity check. This routine should only be called + // when we know that 'IR' is not in the scheduler's instruction queues. + void sanityCheck(const InstRef &IR) const { + assert(llvm::find(WaitSet, IR) == WaitSet.end()); + assert(llvm::find(ReadySet, IR) == ReadySet.end()); + assert(llvm::find(IssuedSet, IR) == IssuedSet.end()); + } +#endif // !NDEBUG +}; +} // namespace mca + +#endif // LLVM_TOOLS_LLVM_MCA_SCHEDULER_H Index: tools/llvm-mca/include/Pipeline.h =================================================================== --- tools/llvm-mca/include/Pipeline.h +++ tools/llvm-mca/include/Pipeline.h @@ -16,8 +16,8 @@ #ifndef LLVM_TOOLS_LLVM_MCA_PIPELINE_H #define LLVM_TOOLS_LLVM_MCA_PIPELINE_H -#include "Scheduler.h" -#include "Stage.h" +#include "HardwareUnits/Scheduler.h" +#include "Stages/Stage.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Error.h" Index: tools/llvm-mca/include/Stages/DispatchStage.h =================================================================== --- tools/llvm-mca/include/Stages/DispatchStage.h +++ tools/llvm-mca/include/Stages/DispatchStage.h @@ -20,10 +20,10 @@ #define LLVM_TOOLS_LLVM_MCA_DISPATCH_STAGE_H #include "HWEventListener.h" +#include "HardwareUnits/RegisterFile.h" +#include "HardwareUnits/RetireControlUnit.h" #include "Instruction.h" -#include "RegisterFile.h" -#include "RetireControlUnit.h" -#include "Stage.h" +#include "Stages/Stage.h" #include "llvm/MC/MCRegisterInfo.h" #include "llvm/MC/MCSubtargetInfo.h" Index: tools/llvm-mca/include/Stages/ExecuteStage.h =================================================================== --- tools/llvm-mca/include/Stages/ExecuteStage.h +++ tools/llvm-mca/include/Stages/ExecuteStage.h @@ -18,9 +18,9 @@ #ifndef LLVM_TOOLS_LLVM_MCA_EXECUTE_STAGE_H #define LLVM_TOOLS_LLVM_MCA_EXECUTE_STAGE_H +#include "HardwareUnits/Scheduler.h" #include "Instruction.h" -#include "Scheduler.h" -#include "Stage.h" +#include "Stages/Stage.h" #include "llvm/ADT/ArrayRef.h" namespace mca { Index: tools/llvm-mca/include/Stages/FetchStage.h =================================================================== --- tools/llvm-mca/include/Stages/FetchStage.h +++ tools/llvm-mca/include/Stages/FetchStage.h @@ -18,7 +18,7 @@ #include "InstrBuilder.h" #include "SourceMgr.h" -#include "Stage.h" +#include "Stages/Stage.h" #include namespace mca { Index: tools/llvm-mca/include/Stages/InstructionTables.h =================================================================== --- tools/llvm-mca/include/Stages/InstructionTables.h +++ tools/llvm-mca/include/Stages/InstructionTables.h @@ -17,10 +17,9 @@ #ifndef LLVM_TOOLS_LLVM_MCA_INSTRUCTIONTABLES_H #define LLVM_TOOLS_LLVM_MCA_INSTRUCTIONTABLES_H +#include "HardwareUnits/Scheduler.h" #include "InstrBuilder.h" -#include "Scheduler.h" -#include "Stage.h" -#include "View.h" +#include "Stages/Stage.h" #include "llvm/ADT/SmallVector.h" #include "llvm/MC/MCSchedule.h" Index: tools/llvm-mca/include/Stages/RetireStage.h =================================================================== --- tools/llvm-mca/include/Stages/RetireStage.h +++ tools/llvm-mca/include/Stages/RetireStage.h @@ -17,9 +17,9 @@ #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" +#include "HardwareUnits/RegisterFile.h" +#include "HardwareUnits/RetireControlUnit.h" +#include "Stages/Stage.h" namespace mca { Index: tools/llvm-mca/lib/CMakeLists.txt =================================================================== --- /dev/null +++ tools/llvm-mca/lib/CMakeLists.txt @@ -0,0 +1,33 @@ +include_directories(${LLVM_MCA_SOURCE_DIR}/include) + +add_library(LLVMMCA + STATIC + Context.cpp + HWEventListener.cpp + HardwareUnits/HardwareUnit.cpp + HardwareUnits/LSUnit.cpp + HardwareUnits/RegisterFile.cpp + HardwareUnits/ResourceManager.cpp + HardwareUnits/RetireControlUnit.cpp + HardwareUnits/Scheduler.cpp + InstrBuilder.cpp + Instruction.cpp + Pipeline.cpp + Stages/DispatchStage.cpp + Stages/ExecuteStage.cpp + Stages/FetchStage.cpp + Stages/InstructionTables.cpp + Stages/RetireStage.cpp + Stages/Stage.cpp + Support.cpp + ) + +llvm_update_compile_flags(LLVMMCA) +llvm_map_components_to_libnames(libs + CodeGen + MC + Support + ) + +target_link_libraries(LLVMMCA ${libs}) +set_target_properties(LLVMMCA PROPERTIES FOLDER "Libraries") Index: tools/llvm-mca/lib/Context.cpp =================================================================== --- tools/llvm-mca/lib/Context.cpp +++ tools/llvm-mca/lib/Context.cpp @@ -16,13 +16,13 @@ //===----------------------------------------------------------------------===// #include "Context.h" -#include "DispatchStage.h" -#include "ExecuteStage.h" -#include "FetchStage.h" -#include "RegisterFile.h" -#include "RetireControlUnit.h" -#include "RetireStage.h" -#include "Scheduler.h" +#include "HardwareUnits/RegisterFile.h" +#include "HardwareUnits/RetireControlUnit.h" +#include "HardwareUnits/Scheduler.h" +#include "Stages/DispatchStage.h" +#include "Stages/ExecuteStage.h" +#include "Stages/FetchStage.h" +#include "Stages/RetireStage.h" namespace mca { Index: tools/llvm-mca/lib/HardwareUnits/HardwareUnit.cpp =================================================================== --- tools/llvm-mca/lib/HardwareUnits/HardwareUnit.cpp +++ tools/llvm-mca/lib/HardwareUnits/HardwareUnit.cpp @@ -13,7 +13,7 @@ /// //===----------------------------------------------------------------------===// -#include "HardwareUnit.h" +#include "HardwareUnits/HardwareUnit.h" namespace mca { Index: tools/llvm-mca/lib/HardwareUnits/LSUnit.cpp =================================================================== --- tools/llvm-mca/lib/HardwareUnits/LSUnit.cpp +++ tools/llvm-mca/lib/HardwareUnits/LSUnit.cpp @@ -12,7 +12,7 @@ /// //===----------------------------------------------------------------------===// -#include "LSUnit.h" +#include "HardwareUnits/LSUnit.h" #include "Instruction.h" #include "llvm/Support/Debug.h" Index: tools/llvm-mca/lib/HardwareUnits/RegisterFile.cpp =================================================================== --- tools/llvm-mca/lib/HardwareUnits/RegisterFile.cpp +++ tools/llvm-mca/lib/HardwareUnits/RegisterFile.cpp @@ -14,7 +14,7 @@ /// //===----------------------------------------------------------------------===// -#include "RegisterFile.h" +#include "HardwareUnits/RegisterFile.h" #include "Instruction.h" #include "llvm/Support/Debug.h" Index: tools/llvm-mca/lib/HardwareUnits/ResourceManager.cpp =================================================================== --- tools/llvm-mca/lib/HardwareUnits/ResourceManager.cpp +++ tools/llvm-mca/lib/HardwareUnits/ResourceManager.cpp @@ -1,4 +1,4 @@ -//===--------------------- Scheduler.cpp ------------------------*- C++ -*-===// +//===--------------------- ResourceManager.cpp ------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -6,12 +6,14 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// A scheduler for processor resource units and processor resource groups. -// +/// \file +/// +/// The classes here represent processor resource units and their management +/// strategy. These classes are managed by the Scheduler. +/// //===----------------------------------------------------------------------===// -#include "Scheduler.h" +#include "HardwareUnits/ResourceManager.h" #include "Support.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -21,14 +23,8 @@ using namespace llvm; #define DEBUG_TYPE "llvm-mca" - ResourceStrategy::~ResourceStrategy() = default; -void Scheduler::initializeStrategy(std::unique_ptr S) { - // Ensure we have a valid (non-null) strategy object. - Strategy = S ? std::move(S) : llvm::make_unique(); -} - void DefaultResourceStrategy::skipMask(uint64_t Mask) { NextInSequenceMask &= (~Mask); if (!NextInSequenceMask) { @@ -55,8 +51,8 @@ skipMask(Mask); } -ResourceState::ResourceState(const llvm::MCProcResourceDesc &Desc, - unsigned Index, uint64_t Mask) +ResourceState::ResourceState(const MCProcResourceDesc &Desc, unsigned Index, + uint64_t Mask) : ProcResourceDescIndex(Index), ResourceMask(Mask), BufferSize(Desc.BufferSize) { if (llvm::countPopulation(ResourceMask) > 1) @@ -101,7 +97,7 @@ return std::unique_ptr(nullptr); } -ResourceManager::ResourceManager(const llvm::MCSchedModel &SM) +ResourceManager::ResourceManager(const MCSchedModel &SM) : ProcResID2Mask(SM.getNumProcResourceKinds()) { computeProcResourceMasks(SM, ProcResID2Mask); Resources.resize(SM.getNumProcResourceKinds()); @@ -310,219 +306,4 @@ Resource.clearReserved(); } -// Anchor the vtable of SchedulerStrategy and DefaultSchedulerStrategy. -SchedulerStrategy::~SchedulerStrategy() = default; -DefaultSchedulerStrategy::~DefaultSchedulerStrategy() = default; - -#ifndef NDEBUG -void Scheduler::dump() const { - dbgs() << "[SCHEDULER]: WaitSet size is: " << WaitSet.size() << '\n'; - dbgs() << "[SCHEDULER]: ReadySet size is: " << ReadySet.size() << '\n'; - dbgs() << "[SCHEDULER]: IssuedSet size is: " << IssuedSet.size() << '\n'; - Resources->dump(); -} -#endif - -Scheduler::Status Scheduler::isAvailable(const InstRef &IR) const { - const InstrDesc &Desc = IR.getInstruction()->getDesc(); - - switch (Resources->canBeDispatched(Desc.Buffers)) { - case ResourceStateEvent::RS_BUFFER_UNAVAILABLE: - return Scheduler::SC_BUFFERS_FULL; - case ResourceStateEvent::RS_RESERVED: - return Scheduler::SC_DISPATCH_GROUP_STALL; - case ResourceStateEvent::RS_BUFFER_AVAILABLE: - break; - } - - // Give lower priority to LSUnit stall events. - switch (LSU->isAvailable(IR)) { - case LSUnit::LSU_LQUEUE_FULL: - return Scheduler::SC_LOAD_QUEUE_FULL; - case LSUnit::LSU_SQUEUE_FULL: - return Scheduler::SC_STORE_QUEUE_FULL; - case LSUnit::LSU_AVAILABLE: - return Scheduler::SC_AVAILABLE; - } - - llvm_unreachable("Don't know how to process this LSU state result!"); -} - -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); - - // Notify the instruction that it started executing. - // This updates the internal state of each write. - IS->execute(); - - if (IS->isExecuting()) - IssuedSet.emplace_back(IR); - else if (IS->isExecuted()) - LSU->onInstructionExecuted(IR); -} - -// Release the buffered resources and issue the instruction. -void Scheduler::issueInstruction( - InstRef &IR, SmallVectorImpl> &UsedResources, - SmallVectorImpl &ReadyInstructions) { - const Instruction &Inst = *IR.getInstruction(); - bool HasDependentUsers = Inst.hasDependentUsers(); - - Resources->releaseBuffers(Inst.getDesc().Buffers); - issueInstructionImpl(IR, UsedResources); - // Instructions that have been issued during this cycle might have unblocked - // other dependent instructions. Dependent instructions may be issued during - // this same cycle if operands have ReadAdvance entries. Promote those - // instructions to the ReadySet and notify the caller that those are ready. - if (HasDependentUsers) - promoteToReadySet(ReadyInstructions); -} - -void Scheduler::promoteToReadySet(SmallVectorImpl &Ready) { - // Scan the set of waiting instructions and promote them to the - // ready queue if operands are all ready. - unsigned RemovedElements = 0; - for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) { - InstRef &IR = *I; - if (!IR.isValid()) - break; - - // Check if this instruction is now ready. In case, force - // a transition in state using method 'update()'. - Instruction &IS = *IR.getInstruction(); - if (!IS.isReady()) - IS.update(); - - // Check if there are still unsolved data dependencies. - if (!isReady(IR)) { - ++I; - continue; - } - - Ready.emplace_back(IR); - ReadySet.emplace_back(IR); - - IR.invalidate(); - ++RemovedElements; - std::iter_swap(I, E - RemovedElements); - } - - WaitSet.resize(WaitSet.size() - RemovedElements); -} - -InstRef Scheduler::select() { - unsigned QueueIndex = ReadySet.size(); - for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) { - const InstRef &IR = ReadySet[I]; - if (QueueIndex == ReadySet.size() || - Strategy->compare(IR, ReadySet[QueueIndex])) { - const InstrDesc &D = IR.getInstruction()->getDesc(); - if (Resources->canBeIssued(D)) - QueueIndex = I; - } - } - - if (QueueIndex == ReadySet.size()) - return InstRef(); - - // We found an instruction to issue. - InstRef IR = ReadySet[QueueIndex]; - std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]); - ReadySet.pop_back(); - return IR; -} - -void Scheduler::updateIssuedSet(SmallVectorImpl &Executed) { - unsigned RemovedElements = 0; - for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) { - InstRef &IR = *I; - if (!IR.isValid()) - break; - Instruction &IS = *IR.getInstruction(); - if (!IS.isExecuted()) { - LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR - << " is still executing.\n"); - ++I; - continue; - } - - // Instruction IR has completed execution. - LSU->onInstructionExecuted(IR); - Executed.emplace_back(IR); - ++RemovedElements; - IR.invalidate(); - std::iter_swap(I, E - RemovedElements); - } - - IssuedSet.resize(IssuedSet.size() - RemovedElements); -} - -void Scheduler::cycleEvent(SmallVectorImpl &Freed, - SmallVectorImpl &Executed, - SmallVectorImpl &Ready) { - // Release consumed resources. - Resources->cycleEvent(Freed); - - // Propagate the cycle event to the 'Issued' and 'Wait' sets. - for (InstRef &IR : IssuedSet) - IR.getInstruction()->cycleEvent(); - - updateIssuedSet(Executed); - - for (InstRef &IR : WaitSet) - IR.getInstruction()->cycleEvent(); - - promoteToReadySet(Ready); -} - -bool Scheduler::mustIssueImmediately(const InstRef &IR) const { - // Instructions that use an in-order dispatch/issue processor resource must be - // issued immediately to the pipeline(s). Any other in-order buffered - // resources (i.e. BufferSize=1) is consumed. - const InstrDesc &Desc = IR.getInstruction()->getDesc(); - return Desc.isZeroLatency() || Resources->mustIssueImmediately(Desc); -} - -void Scheduler::dispatch(const InstRef &IR) { - const InstrDesc &Desc = IR.getInstruction()->getDesc(); - Resources->reserveBuffers(Desc.Buffers); - - // If necessary, reserve queue entries in the load-store unit (LSU). - bool IsMemOp = Desc.MayLoad || Desc.MayStore; - if (IsMemOp) - LSU->dispatch(IR); - - if (!isReady(IR)) { - LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n"); - WaitSet.push_back(IR); - return; - } - - // Don't add a zero-latency instruction to the Ready queue. - // A zero-latency instruction doesn't consume any scheduler resources. That is - // because it doesn't need to be executed, and it is often removed at register - // renaming stage. For example, register-register moves are often optimized at - // register renaming stage by simply updating register aliases. On some - // targets, zero-idiom instructions (for example: a xor that clears the value - // of a register) are treated specially, and are often eliminated at register - // renaming stage. - if (!mustIssueImmediately(IR)) { - LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n"); - ReadySet.push_back(IR); - } -} - -bool Scheduler::isReady(const InstRef &IR) const { - const InstrDesc &Desc = IR.getInstruction()->getDesc(); - bool IsMemOp = Desc.MayLoad || Desc.MayStore; - return IR.getInstruction()->isReady() && (!IsMemOp || LSU->isReady(IR)); -} - } // namespace mca Index: tools/llvm-mca/lib/HardwareUnits/RetireControlUnit.cpp =================================================================== --- tools/llvm-mca/lib/HardwareUnits/RetireControlUnit.cpp +++ tools/llvm-mca/lib/HardwareUnits/RetireControlUnit.cpp @@ -12,7 +12,7 @@ /// //===----------------------------------------------------------------------===// -#include "RetireControlUnit.h" +#include "HardwareUnits/RetireControlUnit.h" #include "llvm/Support/Debug.h" using namespace llvm; Index: tools/llvm-mca/lib/HardwareUnits/Scheduler.cpp =================================================================== --- /dev/null +++ tools/llvm-mca/lib/HardwareUnits/Scheduler.cpp @@ -0,0 +1,244 @@ +//===--------------------- Scheduler.cpp ------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// A scheduler for processor resource units and processor resource groups. +// +//===----------------------------------------------------------------------===// + +#include "HardwareUnits/Scheduler.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +namespace mca { + +using namespace llvm; + +#define DEBUG_TYPE "llvm-mca" + +void Scheduler::initializeStrategy(std::unique_ptr S) { + // Ensure we have a valid (non-null) strategy object. + Strategy = S ? std::move(S) : llvm::make_unique(); +} + +// Anchor the vtable of SchedulerStrategy and DefaultSchedulerStrategy. +SchedulerStrategy::~SchedulerStrategy() = default; +DefaultSchedulerStrategy::~DefaultSchedulerStrategy() = default; + +#ifndef NDEBUG +void Scheduler::dump() const { + dbgs() << "[SCHEDULER]: WaitSet size is: " << WaitSet.size() << '\n'; + dbgs() << "[SCHEDULER]: ReadySet size is: " << ReadySet.size() << '\n'; + dbgs() << "[SCHEDULER]: IssuedSet size is: " << IssuedSet.size() << '\n'; + Resources->dump(); +} +#endif + +Scheduler::Status Scheduler::isAvailable(const InstRef &IR) const { + const InstrDesc &Desc = IR.getInstruction()->getDesc(); + + switch (Resources->canBeDispatched(Desc.Buffers)) { + case ResourceStateEvent::RS_BUFFER_UNAVAILABLE: + return Scheduler::SC_BUFFERS_FULL; + case ResourceStateEvent::RS_RESERVED: + return Scheduler::SC_DISPATCH_GROUP_STALL; + case ResourceStateEvent::RS_BUFFER_AVAILABLE: + break; + } + + // Give lower priority to LSUnit stall events. + switch (LSU->isAvailable(IR)) { + case LSUnit::LSU_LQUEUE_FULL: + return Scheduler::SC_LOAD_QUEUE_FULL; + case LSUnit::LSU_SQUEUE_FULL: + return Scheduler::SC_STORE_QUEUE_FULL; + case LSUnit::LSU_AVAILABLE: + return Scheduler::SC_AVAILABLE; + } + + llvm_unreachable("Don't know how to process this LSU state result!"); +} + +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); + + // Notify the instruction that it started executing. + // This updates the internal state of each write. + IS->execute(); + + if (IS->isExecuting()) + IssuedSet.emplace_back(IR); + else if (IS->isExecuted()) + LSU->onInstructionExecuted(IR); +} + +// Release the buffered resources and issue the instruction. +void Scheduler::issueInstruction( + InstRef &IR, SmallVectorImpl> &UsedResources, + SmallVectorImpl &ReadyInstructions) { + const Instruction &Inst = *IR.getInstruction(); + bool HasDependentUsers = Inst.hasDependentUsers(); + + Resources->releaseBuffers(Inst.getDesc().Buffers); + issueInstructionImpl(IR, UsedResources); + // Instructions that have been issued during this cycle might have unblocked + // other dependent instructions. Dependent instructions may be issued during + // this same cycle if operands have ReadAdvance entries. Promote those + // instructions to the ReadySet and notify the caller that those are ready. + if (HasDependentUsers) + promoteToReadySet(ReadyInstructions); +} + +void Scheduler::promoteToReadySet(SmallVectorImpl &Ready) { + // Scan the set of waiting instructions and promote them to the + // ready queue if operands are all ready. + unsigned RemovedElements = 0; + for (auto I = WaitSet.begin(), E = WaitSet.end(); I != E;) { + InstRef &IR = *I; + if (!IR.isValid()) + break; + + // Check if this instruction is now ready. In case, force + // a transition in state using method 'update()'. + Instruction &IS = *IR.getInstruction(); + if (!IS.isReady()) + IS.update(); + + // Check if there are still unsolved data dependencies. + if (!isReady(IR)) { + ++I; + continue; + } + + Ready.emplace_back(IR); + ReadySet.emplace_back(IR); + + IR.invalidate(); + ++RemovedElements; + std::iter_swap(I, E - RemovedElements); + } + + WaitSet.resize(WaitSet.size() - RemovedElements); +} + +InstRef Scheduler::select() { + unsigned QueueIndex = ReadySet.size(); + for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) { + const InstRef &IR = ReadySet[I]; + if (QueueIndex == ReadySet.size() || + Strategy->compare(IR, ReadySet[QueueIndex])) { + const InstrDesc &D = IR.getInstruction()->getDesc(); + if (Resources->canBeIssued(D)) + QueueIndex = I; + } + } + + if (QueueIndex == ReadySet.size()) + return InstRef(); + + // We found an instruction to issue. + InstRef IR = ReadySet[QueueIndex]; + std::swap(ReadySet[QueueIndex], ReadySet[ReadySet.size() - 1]); + ReadySet.pop_back(); + return IR; +} + +void Scheduler::updateIssuedSet(SmallVectorImpl &Executed) { + unsigned RemovedElements = 0; + for (auto I = IssuedSet.begin(), E = IssuedSet.end(); I != E;) { + InstRef &IR = *I; + if (!IR.isValid()) + break; + Instruction &IS = *IR.getInstruction(); + if (!IS.isExecuted()) { + LLVM_DEBUG(dbgs() << "[SCHEDULER]: Instruction #" << IR + << " is still executing.\n"); + ++I; + continue; + } + + // Instruction IR has completed execution. + LSU->onInstructionExecuted(IR); + Executed.emplace_back(IR); + ++RemovedElements; + IR.invalidate(); + std::iter_swap(I, E - RemovedElements); + } + + IssuedSet.resize(IssuedSet.size() - RemovedElements); +} + +void Scheduler::cycleEvent(SmallVectorImpl &Freed, + SmallVectorImpl &Executed, + SmallVectorImpl &Ready) { + // Release consumed resources. + Resources->cycleEvent(Freed); + + // Propagate the cycle event to the 'Issued' and 'Wait' sets. + for (InstRef &IR : IssuedSet) + IR.getInstruction()->cycleEvent(); + + updateIssuedSet(Executed); + + for (InstRef &IR : WaitSet) + IR.getInstruction()->cycleEvent(); + + promoteToReadySet(Ready); +} + +bool Scheduler::mustIssueImmediately(const InstRef &IR) const { + // Instructions that use an in-order dispatch/issue processor resource must be + // issued immediately to the pipeline(s). Any other in-order buffered + // resources (i.e. BufferSize=1) is consumed. + const InstrDesc &Desc = IR.getInstruction()->getDesc(); + return Desc.isZeroLatency() || Resources->mustIssueImmediately(Desc); +} + +void Scheduler::dispatch(const InstRef &IR) { + const InstrDesc &Desc = IR.getInstruction()->getDesc(); + Resources->reserveBuffers(Desc.Buffers); + + // If necessary, reserve queue entries in the load-store unit (LSU). + bool IsMemOp = Desc.MayLoad || Desc.MayStore; + if (IsMemOp) + LSU->dispatch(IR); + + if (!isReady(IR)) { + LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the WaitSet\n"); + WaitSet.push_back(IR); + return; + } + + // Don't add a zero-latency instruction to the Ready queue. + // A zero-latency instruction doesn't consume any scheduler resources. That is + // because it doesn't need to be executed, and it is often removed at register + // renaming stage. For example, register-register moves are often optimized at + // register renaming stage by simply updating register aliases. On some + // targets, zero-idiom instructions (for example: a xor that clears the value + // of a register) are treated specially, and are often eliminated at register + // renaming stage. + if (!mustIssueImmediately(IR)) { + LLVM_DEBUG(dbgs() << "[SCHEDULER] Adding #" << IR << " to the ReadySet\n"); + ReadySet.push_back(IR); + } +} + +bool Scheduler::isReady(const InstRef &IR) const { + const InstrDesc &Desc = IR.getInstruction()->getDesc(); + bool IsMemOp = Desc.MayLoad || Desc.MayStore; + return IR.getInstruction()->isReady() && (!IsMemOp || LSU->isReady(IR)); +} + +} // namespace mca Index: tools/llvm-mca/lib/LLVMBuild.txt =================================================================== --- /dev/null +++ tools/llvm-mca/lib/LLVMBuild.txt @@ -0,0 +1,22 @@ +;===- ./tools/llvm-mca/lib/LLVMBuild.txt -----------------------*- Conf -*--===; +; +; The LLVM Compiler Infrastructure +; +; This file is distributed under the University of Illinois Open Source +; License. See LICENSE.TXT for details. +; +;===------------------------------------------------------------------------===; +; +; This is an LLVMBuild description file for the components in this subdirectory. +; +; For more information on the LLVMBuild system, please see: +; +; http://llvm.org/docs/LLVMBuild.html +; +;===------------------------------------------------------------------------===; + +[component_0] +type = Library +name = MCA +parent = Libraries +required_libraries = CodeGen MC Support Index: tools/llvm-mca/lib/Stages/DispatchStage.cpp =================================================================== --- tools/llvm-mca/lib/Stages/DispatchStage.cpp +++ tools/llvm-mca/lib/Stages/DispatchStage.cpp @@ -16,9 +16,9 @@ /// //===----------------------------------------------------------------------===// -#include "DispatchStage.h" +#include "Stages/DispatchStage.h" #include "HWEventListener.h" -#include "Scheduler.h" +#include "HardwareUnits/Scheduler.h" #include "llvm/Support/Debug.h" using namespace llvm; Index: tools/llvm-mca/lib/Stages/ExecuteStage.cpp =================================================================== --- tools/llvm-mca/lib/Stages/ExecuteStage.cpp +++ tools/llvm-mca/lib/Stages/ExecuteStage.cpp @@ -15,7 +15,7 @@ /// //===----------------------------------------------------------------------===// -#include "ExecuteStage.h" +#include "Stages/ExecuteStage.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Debug.h" Index: tools/llvm-mca/lib/Stages/FetchStage.cpp =================================================================== --- tools/llvm-mca/lib/Stages/FetchStage.cpp +++ tools/llvm-mca/lib/Stages/FetchStage.cpp @@ -13,7 +13,7 @@ /// //===----------------------------------------------------------------------===// -#include "FetchStage.h" +#include "Stages/FetchStage.h" namespace mca { Index: tools/llvm-mca/lib/Stages/InstructionTables.cpp =================================================================== --- tools/llvm-mca/lib/Stages/InstructionTables.cpp +++ tools/llvm-mca/lib/Stages/InstructionTables.cpp @@ -15,7 +15,7 @@ /// //===----------------------------------------------------------------------===// -#include "InstructionTables.h" +#include "Stages/InstructionTables.h" namespace mca { Index: tools/llvm-mca/lib/Stages/RetireStage.cpp =================================================================== --- tools/llvm-mca/lib/Stages/RetireStage.cpp +++ tools/llvm-mca/lib/Stages/RetireStage.cpp @@ -14,7 +14,7 @@ /// //===----------------------------------------------------------------------===// -#include "RetireStage.h" +#include "Stages/RetireStage.h" #include "HWEventListener.h" #include "llvm/Support/Debug.h" Index: tools/llvm-mca/lib/Stages/Stage.cpp =================================================================== --- tools/llvm-mca/lib/Stages/Stage.cpp +++ tools/llvm-mca/lib/Stages/Stage.cpp @@ -13,7 +13,7 @@ /// //===----------------------------------------------------------------------===// -#include "Stage.h" +#include "Stages/Stage.h" namespace mca { Index: tools/llvm-mca/llvm-mca.cpp =================================================================== --- tools/llvm-mca/llvm-mca.cpp +++ tools/llvm-mca/llvm-mca.cpp @@ -22,19 +22,19 @@ //===----------------------------------------------------------------------===// #include "CodeRegion.h" -#include "Context.h" -#include "DispatchStatistics.h" -#include "FetchStage.h" -#include "InstructionInfoView.h" -#include "InstructionTables.h" -#include "Pipeline.h" #include "PipelinePrinter.h" -#include "RegisterFileStatistics.h" -#include "ResourcePressureView.h" -#include "RetireControlUnitStatistics.h" -#include "SchedulerStatistics.h" -#include "SummaryView.h" -#include "TimelineView.h" +#include "Stats/DispatchStatistics.h" +#include "Stats/RegisterFileStatistics.h" +#include "Stats/RetireControlUnitStatistics.h" +#include "Stats/SchedulerStatistics.h" +#include "Views/InstructionInfoView.h" +#include "Views/ResourcePressureView.h" +#include "Views/SummaryView.h" +#include "Views/TimelineView.h" +#include "include/Context.h" +#include "include/Pipeline.h" +#include "include/Stages/FetchStage.h" +#include "include/Stages/InstructionTables.h" #include "llvm/MC/MCAsmInfo.h" #include "llvm/MC/MCContext.h" #include "llvm/MC/MCObjectFileInfo.h"