//===--------------------- Scheduler.h ------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
/// \file
///
/// A scheduler for Processor Resource Units and Processor Resource Groups.
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_MCA_HARDWAREUNITS_SCHEDULER_H
#define LLVM_MCA_HARDWAREUNITS_SCHEDULER_H
#include "llvm/ADT/SmallVector.h"
#include "llvm/MC/MCSchedule.h"
#include "llvm/MCA/HardwareUnits/HardwareUnit.h"
#include "llvm/MCA/HardwareUnits/LSUnit.h"
#include "llvm/MCA/HardwareUnits/ResourceManager.h"
#include "llvm/MCA/Support.h"
namespace llvm {
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.
///
class Scheduler : public HardwareUnit {
LSUnitBase &LSU;
// Instruction selection strategy for this Scheduler.
std::unique_ptr<SchedulerStrategy> Strategy;
// Hardware resources that are managed by this scheduler.
std::unique_ptr<ResourceManager> Resources;
// Instructions dispatched to the Scheduler are internally classified based on
// the instruction stage (see Instruction::InstrStage).
//
// An Instruction dispatched to the Scheduler is added to the WaitSet if not
// all its register operands are available, and at least one latency is
// unknown. By construction, the WaitSet only contains instructions that are
// in the IS_DISPATCHED stage.
//
// An Instruction transitions from the WaitSet to the PendingSet if the
// instruction is not ready yet, but the latency of every register read is
// known. Instructions in the PendingSet can only be in the IS_PENDING or
// IS_READY stage. Only IS_READY instructions that are waiting on memory
// dependencies can be added to the PendingSet.
//
// Instructions in the PendingSet are immediately dominated only by
// instructions that have already been issued to the underlying pipelines. In
// the presence of bottlenecks caused by data dependencies, the PendingSet can
// be inspected to identify problematic data dependencies between
// instructions.
//
// An instruction is moved to the ReadySet when all register operands become
// available, and all memory dependencies are met. Instructions that are
// moved from the PendingSet to the ReadySet must transition to the 'IS_READY'
// stage.
//
// On every cycle, the Scheduler checks if it can promote instructions from the
// PendingSet to the ReadySet.
//
// An Instruction is moved from the ReadySet to the `IssuedSet` when it starts
// exection. This event also causes an instruction state transition (i.e. from
// state IS_READY, to state IS_EXECUTING). An Instruction leaves the IssuedSet
// only when it reaches the write-back stage.
std::vector<InstRef> WaitSet;
std::vector<InstRef> PendingSet;
std::vector<InstRef> ReadySet;
std::vector<InstRef> IssuedSet;
// A mask of busy resource units. It defaults to the empty set (i.e. a zero
// mask), and it is cleared at the beginning of every cycle.
// It is updated every time the scheduler fails to issue an instruction from
// the ready set due to unavailable pipeline resources.
// Each bit of the mask represents an unavailable resource.
uint64_t BusyResourceUnits;
// Counts the number of instructions in the pending set that were dispatched
// during this cycle.
unsigned NumDispatchedToThePendingSet;
// True if the previous pipeline Stage was unable to dispatch a full group of
// opcodes because scheduler buffers (or LS queues) were unavailable.
bool HadTokenStall;
/// 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<SchedulerStrategy> S);
/// Issue an instruction without updating the ready queue.
void issueInstructionImpl(
InstRef &IR,
SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &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(SmallVectorImpl<InstRef> &Executed);
// Try to promote instructions from the PendingSet to the ReadySet.
// Add promoted instructions to the 'Ready' vector in input.
// Returns true if at least one instruction was promoted.
bool promoteToReadySet(SmallVectorImpl<InstRef> &Ready);
// Try to promote instructions from the WaitSet to the PendingSet.
// Add promoted instructions to the 'Pending' vector in input.
// Returns true if at least one instruction was promoted.
bool promoteToPendingSet(SmallVectorImpl<InstRef> &Pending);
public:
Scheduler(const MCSchedModel &Model, LSUnitBase &Lsu)
: Scheduler(Model, Lsu, nullptr) {}
Scheduler(const MCSchedModel &Model, LSUnitBase &Lsu,
std::unique_ptr<SchedulerStrategy> SelectStrategy)
: Scheduler(std::make_unique<ResourceManager>(Model), Lsu,
std::move(SelectStrategy)) {}
Scheduler(std::unique_ptr<ResourceManager> RM, LSUnitBase &Lsu,
std::unique_ptr<SchedulerStrategy> SelectStrategy)
: LSU(Lsu), Resources(std::move(RM)), BusyResourceUnits(0),
NumDispatchedToThePendingSet(0), HadTokenStall(false) {
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 during this cycle.
/// Return SC_AVAILABLE if both scheduler and LS resources are available.
///
/// This method is also responsible for setting field HadTokenStall if
/// IR cannot be dispatched to the Scheduler due to unavailable resources.
Status isAvailable(const InstRef &IR);
/// 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`.
///
/// If IR is a memory operation, then the Scheduler queries the LS unit to
/// obtain a LS token. An LS token is used internally to track memory
/// dependencies.
bool dispatch(InstRef &IR);
/// 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,
SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Used,
SmallVectorImpl<InstRef> &Pending,
SmallVectorImpl<InstRef> &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.
/// Vector Pending is popluated by instructions that have transitioned through
/// the pending stat during this cycle. The Pending and Ready sets may not be
/// disjoint. An instruction is allowed to transition from the WAIT state to
/// the READY state (going through the PENDING state) within a single cycle.
/// That means, instructions may appear in both the Pending and Ready set.
void cycleEvent(SmallVectorImpl<ResourceRef> &Freed,
SmallVectorImpl<InstRef> &Executed,
SmallVectorImpl<InstRef> &Pending,
SmallVectorImpl<InstRef> &Ready);
/// Convert a resource mask into a valid llvm processor resource identifier.
///
/// Only the most significant bit of the Mask is used by this method to
/// identify the processor resource.
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();
bool isReadySetEmpty() const { return ReadySet.empty(); }
bool isWaitSetEmpty() const { return WaitSet.empty(); }
/// This method is called by the ExecuteStage at the end of each cycle to
/// identify bottlenecks caused by data dependencies. Vector RegDeps is
/// populated by instructions that were not issued because of unsolved
/// register dependencies. Vector MemDeps is populated by instructions that
/// were not issued because of unsolved memory dependencies.
void analyzeDataDependencies(SmallVectorImpl<InstRef> &RegDeps,
SmallVectorImpl<InstRef> &MemDeps);
/// Returns a mask of busy resources, and populates vector Insts with
/// instructions that could not be issued to the underlying pipelines because
/// not all pipeline resources were available.
uint64_t analyzeResourcePressure(SmallVectorImpl<InstRef> &Insts);
// Returns true if the dispatch logic couldn't dispatch a full group due to
// unavailable scheduler and/or LS resources.
bool hadTokenStall() const { return HadTokenStall; }
#ifndef NDEBUG
// Update the ready queues.
void dump() const;
// This routine performs a basic correctness check. This routine should only
// be called when we know that 'IR' is not in the scheduler's instruction
// queues.
void instructionCheck(const InstRef &IR) const {
assert(!is_contained(WaitSet, IR) && "Already in the wait set!");
assert(!is_contained(ReadySet, IR) && "Already in the ready set!");
assert(!is_contained(IssuedSet, IR) && "Already executing!");
}
#endif // !NDEBUG
};
} // namespace mca
} // namespace llvm
#endif // LLVM_MCA_HARDWAREUNITS_SCHEDULER_H