Index: tools/llvm-mca/Scheduler.h =================================================================== --- tools/llvm-mca/Scheduler.h +++ tools/llvm-mca/Scheduler.h @@ -339,6 +339,42 @@ #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. /// @@ -363,9 +399,11 @@ /// 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 { - const llvm::MCSchedModel &SM; LSUnit *LSU; + // Instruction selection strategy for this Scheduler. + std::unique_ptr Strategy; + // Hardware resources that are managed by this scheduler. std::unique_ptr Resources; @@ -389,8 +427,17 @@ public: Scheduler(const llvm::MCSchedModel &Model, LSUnit *Lsu) - : SM(Model), LSU(Lsu), Resources(llvm::make_unique(SM)) { - } + : LSU(Lsu), + Strategy(llvm::make_unique()), + Resources(llvm::make_unique(Model)) {} + Scheduler(const llvm::MCSchedModel &Model, LSUnit *Lsu, + std::unique_ptr SelectStrategy) + : LSU(Lsu), Strategy(std::move(SelectStrategy)), + Resources(llvm::make_unique(Model)) {} + Scheduler(std::unique_ptr RM, LSUnit *Lsu, + std::unique_ptr SelectStrategy) + : LSU(Lsu), Strategy(std::move(SelectStrategy)), + Resources(std::move(RM)) {} // Stalls generated by the scheduler. enum Status { @@ -450,13 +497,9 @@ return Resources->resolveResourceMask(Mask); } - /// Select the next instruction to issue from the ReadySet. - /// - /// The default implementation of this method ranks instructions based on - /// their age, and the number of known users. It prioritizes older - /// instructions over younger instructions to minimize the pressure on the - /// reorder buffer. It also gives a little priority boost to instructions - /// with multiple users to better expose ILP. + /// 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 Index: tools/llvm-mca/Scheduler.cpp =================================================================== --- tools/llvm-mca/Scheduler.cpp +++ tools/llvm-mca/Scheduler.cpp @@ -248,6 +248,10 @@ 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'; @@ -259,7 +263,7 @@ 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; @@ -335,7 +339,7 @@ if (!IS.isReady()) IS.update(); - // Check f there are still unsolved data dependencies. + // Check if there are still unsolved data dependencies. if (!isReady(IR)) { ++I; continue; @@ -354,30 +358,13 @@ InstRef Scheduler::select() { unsigned QueueIndex = ReadySet.size(); - int Rank = std::numeric_limits::max(); - for (unsigned I = 0, E = ReadySet.size(); I != E; ++I) { const InstRef &IR = ReadySet[I]; - const unsigned IID = IR.getSourceIndex(); - const Instruction &IS = *IR.getInstruction(); - - // Compute a rank value based on the age of an instruction (i.e. its source - // index) and its number of users. The lower the rank value, the better. - int CurrentRank = IID - IS.getNumUsers(); - - // We want to prioritize older instructions over younger instructions to - // minimize the pressure on the reorder buffer. We also want to - // rank higher the instructions with more users to better expose ILP. - if (CurrentRank == Rank) - if (IID > ReadySet[QueueIndex].getSourceIndex()) - continue; - - if (CurrentRank <= Rank) { - const InstrDesc &D = IS.getDesc(); - if (Resources->canBeIssued(D)) { - Rank = CurrentRank; + if (QueueIndex == ReadySet.size() || + Strategy->compare(IR, ReadySet[QueueIndex])) { + const InstrDesc &D = IR.getInstruction()->getDesc(); + if (Resources->canBeIssued(D)) QueueIndex = I; - } } } @@ -430,7 +417,7 @@ for (InstRef &IR : WaitSet) IR.getInstruction()->cycleEvent(); - + promoteToReadySet(Ready); }