Scheduler.h revision 360784
1220559Sadrian//===--------------------- Scheduler.h ------------------------*- C++ -*-===// 2220559Sadrian// 3220559Sadrian// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4220559Sadrian// See https://llvm.org/LICENSE.txt for license information. 5220559Sadrian// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6220559Sadrian// 7220559Sadrian//===----------------------------------------------------------------------===// 8220559Sadrian/// \file 9220559Sadrian/// 10220559Sadrian/// A scheduler for Processor Resource Units and Processor Resource Groups. 11220559Sadrian/// 12220559Sadrian//===----------------------------------------------------------------------===// 13220559Sadrian 14220559Sadrian#ifndef LLVM_MCA_SCHEDULER_H 15220559Sadrian#define LLVM_MCA_SCHEDULER_H 16220559Sadrian 17220559Sadrian#include "llvm/ADT/SmallVector.h" 18220559Sadrian#include "llvm/MC/MCSchedule.h" 19220559Sadrian#include "llvm/MCA/HardwareUnits/HardwareUnit.h" 20220559Sadrian#include "llvm/MCA/HardwareUnits/LSUnit.h" 21220559Sadrian#include "llvm/MCA/HardwareUnits/ResourceManager.h" 22220559Sadrian#include "llvm/MCA/Support.h" 23220559Sadrian 24220559Sadriannamespace llvm { 25220559Sadriannamespace mca { 26220559Sadrian 27220559Sadrianclass SchedulerStrategy { 28220559Sadrianpublic: 29220559Sadrian SchedulerStrategy() = default; 30220559Sadrian virtual ~SchedulerStrategy(); 31220559Sadrian 32220559Sadrian /// Returns true if Lhs should take priority over Rhs. 33220559Sadrian /// 34220559Sadrian /// This method is used by class Scheduler to select the "best" ready 35220559Sadrian /// instruction to issue to the underlying pipelines. 36220559Sadrian virtual bool compare(const InstRef &Lhs, const InstRef &Rhs) const = 0; 37220559Sadrian}; 38220559Sadrian 39220559Sadrian/// Default instruction selection strategy used by class Scheduler. 40220559Sadrianclass DefaultSchedulerStrategy : public SchedulerStrategy { 41220559Sadrian /// This method ranks instructions based on their age, and the number of known 42220559Sadrian /// users. The lower the rank value, the better. 43220559Sadrian int computeRank(const InstRef &Lhs) const { 44220559Sadrian return Lhs.getSourceIndex() - Lhs.getInstruction()->getNumUsers(); 45220559Sadrian } 46221500Sadrian 47220559Sadrianpublic: 48220559Sadrian DefaultSchedulerStrategy() = default; 49220559Sadrian virtual ~DefaultSchedulerStrategy(); 50220559Sadrian 51221500Sadrian bool compare(const InstRef &Lhs, const InstRef &Rhs) const override { 52220559Sadrian int LhsRank = computeRank(Lhs); 53221500Sadrian int RhsRank = computeRank(Rhs); 54220559Sadrian 55220559Sadrian /// Prioritize older instructions over younger instructions to minimize the 56221500Sadrian /// pressure on the reorder buffer. 57221500Sadrian if (LhsRank == RhsRank) 58221500Sadrian return Lhs.getSourceIndex() < Rhs.getSourceIndex(); 59221500Sadrian return LhsRank < RhsRank; 60221500Sadrian } 61221500Sadrian}; 62220559Sadrian 63220559Sadrian/// Class Scheduler is responsible for issuing instructions to pipeline 64220559Sadrian/// resources. 65220559Sadrian/// 66220559Sadrian/// Internally, it delegates to a ResourceManager the management of processor 67221500Sadrian/// resources. This class is also responsible for tracking the progress of 68221500Sadrian/// instructions from the dispatch stage, until the write-back stage. 69221500Sadrian/// 70220559Sadrianclass Scheduler : public HardwareUnit { 71221500Sadrian LSUnitBase &LSU; 72221500Sadrian 73221500Sadrian // Instruction selection strategy for this Scheduler. 74221500Sadrian std::unique_ptr<SchedulerStrategy> Strategy; 75220559Sadrian 76220559Sadrian // Hardware resources that are managed by this scheduler. 77221500Sadrian std::unique_ptr<ResourceManager> Resources; 78220559Sadrian 79220559Sadrian // Instructions dispatched to the Scheduler are internally classified based on 80220559Sadrian // the instruction stage (see Instruction::InstrStage). 81220559Sadrian // 82220559Sadrian // An Instruction dispatched to the Scheduler is added to the WaitSet if not 83220559Sadrian // all its register operands are available, and at least one latency is 84220559Sadrian // unknown. By construction, the WaitSet only contains instructions that are 85221500Sadrian // in the IS_DISPATCHED stage. 86220559Sadrian // 87220559Sadrian // An Instruction transitions from the WaitSet to the PendingSet if the 88221500Sadrian // instruction is not ready yet, but the latency of every register read is 89220559Sadrian // known. Instructions in the PendingSet can only be in the IS_PENDING or 90220559Sadrian // IS_READY stage. Only IS_READY instructions that are waiting on memory 91220559Sadrian // dependencies can be added to the PendingSet. 92220559Sadrian // 93220559Sadrian // Instructions in the PendingSet are immediately dominated only by 94220559Sadrian // instructions that have already been issued to the underlying pipelines. In 95221500Sadrian // the presence of bottlenecks caused by data dependencies, the PendingSet can 96220559Sadrian // be inspected to identify problematic data dependencies between 97220559Sadrian // instructions. 98221500Sadrian // 99220559Sadrian // An instruction is moved to the ReadySet when all register operands become 100221500Sadrian // available, and all memory dependencies are met. Instructions that are 101220559Sadrian // moved from the PendingSet to the ReadySet must transition to the 'IS_READY' 102221500Sadrian // stage. 103220559Sadrian // 104221500Sadrian // On every cycle, the Scheduler checks if it can promote instructions from the 105220559Sadrian // PendingSet to the ReadySet. 106221500Sadrian // 107220559Sadrian // An Instruction is moved from the ReadySet to the `IssuedSet` when it starts 108220559Sadrian // exection. This event also causes an instruction state transition (i.e. from 109220559Sadrian // state IS_READY, to state IS_EXECUTING). An Instruction leaves the IssuedSet 110220559Sadrian // only when it reaches the write-back stage. 111220559Sadrian std::vector<InstRef> WaitSet; 112221500Sadrian std::vector<InstRef> PendingSet; 113220559Sadrian std::vector<InstRef> ReadySet; 114220559Sadrian std::vector<InstRef> IssuedSet; 115220559Sadrian 116220559Sadrian // A mask of busy resource units. It defaults to the empty set (i.e. a zero 117220559Sadrian // mask), and it is cleared at the beginning of every cycle. 118220559Sadrian // It is updated every time the scheduler fails to issue an instruction from 119220559Sadrian // the ready set due to unavailable pipeline resources. 120220559Sadrian // Each bit of the mask represents an unavailable resource. 121220559Sadrian uint64_t BusyResourceUnits; 122237820Sbrooks 123237820Sbrooks // Counts the number of instructions in the pending set that were dispatched 124220559Sadrian // during this cycle. 125237820Sbrooks unsigned NumDispatchedToThePendingSet; 126237820Sbrooks 127237820Sbrooks // True if the previous pipeline Stage was unable to dispatch a full group of 128237820Sbrooks // opcodes because scheduler buffers (or LS queues) were unavailable. 129220559Sadrian bool HadTokenStall; 130220559Sadrian 131220559Sadrian /// Verify the given selection strategy and set the Strategy member 132220559Sadrian /// accordingly. If no strategy is provided, the DefaultSchedulerStrategy is 133221500Sadrian /// used. 134221500Sadrian void initializeStrategy(std::unique_ptr<SchedulerStrategy> S); 135220559Sadrian 136221500Sadrian /// Issue an instruction without updating the ready queue. 137221500Sadrian void issueInstructionImpl( 138221500Sadrian InstRef &IR, 139221500Sadrian SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Pipes); 140221500Sadrian 141220559Sadrian // Identify instructions that have finished executing, and remove them from 142221500Sadrian // the IssuedSet. References to executed instructions are added to input 143221500Sadrian // vector 'Executed'. 144221500Sadrian void updateIssuedSet(SmallVectorImpl<InstRef> &Executed); 145221500Sadrian 146220559Sadrian // Try to promote instructions from the PendingSet to the ReadySet. 147221500Sadrian // Add promoted instructions to the 'Ready' vector in input. 148221500Sadrian // Returns true if at least one instruction was promoted. 149220559Sadrian bool promoteToReadySet(SmallVectorImpl<InstRef> &Ready); 150221500Sadrian 151221500Sadrian // Try to promote instructions from the WaitSet to the PendingSet. 152221500Sadrian // Add promoted instructions to the 'Pending' vector in input. 153221500Sadrian // Returns true if at least one instruction was promoted. 154220559Sadrian bool promoteToPendingSet(SmallVectorImpl<InstRef> &Pending); 155221500Sadrian 156237820Sbrookspublic: 157237820Sbrooks Scheduler(const MCSchedModel &Model, LSUnitBase &Lsu) 158221500Sadrian : Scheduler(Model, Lsu, nullptr) {} 159220559Sadrian 160221500Sadrian Scheduler(const MCSchedModel &Model, LSUnitBase &Lsu, 161221500Sadrian std::unique_ptr<SchedulerStrategy> SelectStrategy) 162221500Sadrian : Scheduler(std::make_unique<ResourceManager>(Model), Lsu, 163220559Sadrian std::move(SelectStrategy)) {} 164221500Sadrian 165221500Sadrian Scheduler(std::unique_ptr<ResourceManager> RM, LSUnitBase &Lsu, 166221500Sadrian std::unique_ptr<SchedulerStrategy> SelectStrategy) 167221500Sadrian : LSU(Lsu), Resources(std::move(RM)), BusyResourceUnits(0), 168220559Sadrian NumDispatchedToThePendingSet(0), HadTokenStall(false) { 169221500Sadrian initializeStrategy(std::move(SelectStrategy)); 170221500Sadrian } 171221500Sadrian 172221500Sadrian // Stalls generated by the scheduler. 173220559Sadrian enum Status { 174221500Sadrian SC_AVAILABLE, 175221500Sadrian SC_LOAD_QUEUE_FULL, 176220559Sadrian SC_STORE_QUEUE_FULL, 177221500Sadrian SC_BUFFERS_FULL, 178220559Sadrian SC_DISPATCH_GROUP_STALL, 179221500Sadrian }; 180221500Sadrian 181221500Sadrian /// Check if the instruction in 'IR' can be dispatched during this cycle. 182221500Sadrian /// Return SC_AVAILABLE if both scheduler and LS resources are available. 183221500Sadrian /// 184221500Sadrian /// This method is also responsible for setting field HadTokenStall if 185220559Sadrian /// IR cannot be dispatched to the Scheduler due to unavailable resources. 186221500Sadrian Status isAvailable(const InstRef &IR); 187221500Sadrian 188221500Sadrian /// Reserves buffer and LSUnit queue resources that are necessary to issue 189221500Sadrian /// this instruction. 190221500Sadrian /// 191221500Sadrian /// Returns true if instruction IR is ready to be issued to the underlying 192221500Sadrian /// pipelines. Note that this operation cannot fail; it assumes that a 193221500Sadrian /// previous call to method `isAvailable(IR)` returned `SC_AVAILABLE`. 194221500Sadrian /// 195220559Sadrian /// If IR is a memory operation, then the Scheduler queries the LS unit to 196221500Sadrian /// obtain a LS token. An LS token is used internally to track memory 197221500Sadrian /// dependencies. 198221500Sadrian bool dispatch(InstRef &IR); 199220559Sadrian 200221500Sadrian /// Issue an instruction and populates a vector of used pipeline resources, 201221500Sadrian /// and a vector of instructions that transitioned to the ready state as a 202221500Sadrian /// result of this event. 203221500Sadrian void issueInstruction( 204221500Sadrian InstRef &IR, 205221500Sadrian SmallVectorImpl<std::pair<ResourceRef, ResourceCycles>> &Used, 206221500Sadrian SmallVectorImpl<InstRef> &Pending, 207221500Sadrian SmallVectorImpl<InstRef> &Ready); 208220559Sadrian 209221500Sadrian /// Returns true if IR has to be issued immediately, or if IR is a zero 210221500Sadrian /// latency instruction. 211221500Sadrian bool mustIssueImmediately(const InstRef &IR) const; 212220559Sadrian 213221500Sadrian /// This routine notifies the Scheduler that a new cycle just started. 214221500Sadrian /// 215221500Sadrian /// It notifies the underlying ResourceManager that a new cycle just started. 216220559Sadrian /// Vector `Freed` is populated with resourceRef related to resources that 217221500Sadrian /// have changed in state, and that are now available to new instructions. 218221500Sadrian /// Instructions executed are added to vector Executed, while vector Ready is 219221500Sadrian /// populated with instructions that have become ready in this new cycle. 220221500Sadrian /// Vector Pending is popluated by instructions that have transitioned through 221221500Sadrian /// the pending stat during this cycle. The Pending and Ready sets may not be 222221500Sadrian /// disjoint. An instruction is allowed to transition from the WAIT state to 223221500Sadrian /// the READY state (going through the PENDING state) within a single cycle. 224221500Sadrian /// That means, instructions may appear in both the Pending and Ready set. 225221500Sadrian void cycleEvent(SmallVectorImpl<ResourceRef> &Freed, 226220559Sadrian SmallVectorImpl<InstRef> &Executed, 227221500Sadrian SmallVectorImpl<InstRef> &Pending, 228221500Sadrian SmallVectorImpl<InstRef> &Ready); 229221500Sadrian 230221500Sadrian /// Convert a resource mask into a valid llvm processor resource identifier. 231221500Sadrian /// 232221500Sadrian /// Only the most significant bit of the Mask is used by this method to 233221500Sadrian /// identify the processor resource. 234221500Sadrian unsigned getResourceID(uint64_t Mask) const { 235221500Sadrian return Resources->resolveResourceMask(Mask); 236221500Sadrian } 237221500Sadrian 238221500Sadrian /// Select the next instruction to issue from the ReadySet. Returns an invalid 239221500Sadrian /// instruction reference if there are no ready instructions, or if processor 240221500Sadrian /// resources are not available. 241221500Sadrian InstRef select(); 242221500Sadrian 243221500Sadrian bool isReadySetEmpty() const { return ReadySet.empty(); } 244221500Sadrian bool isWaitSetEmpty() const { return WaitSet.empty(); } 245220559Sadrian 246221500Sadrian /// This method is called by the ExecuteStage at the end of each cycle to 247221500Sadrian /// identify bottlenecks caused by data dependencies. Vector RegDeps is 248221500Sadrian /// populated by instructions that were not issued because of unsolved 249221500Sadrian /// register dependencies. Vector MemDeps is populated by instructions that 250221500Sadrian /// were not issued because of unsolved memory dependencies. 251221500Sadrian void analyzeDataDependencies(SmallVectorImpl<InstRef> &RegDeps, 252221500Sadrian SmallVectorImpl<InstRef> &MemDeps); 253221500Sadrian 254221500Sadrian /// Returns a mask of busy resources, and populates vector Insts with 255221500Sadrian /// instructions that could not be issued to the underlying pipelines because 256221500Sadrian /// not all pipeline resources were available. 257221500Sadrian uint64_t analyzeResourcePressure(SmallVectorImpl<InstRef> &Insts); 258221500Sadrian 259220559Sadrian // Returns true if the dispatch logic couldn't dispatch a full group due to 260221500Sadrian // unavailable scheduler and/or LS resources. 261221500Sadrian bool hadTokenStall() const { return HadTokenStall; } 262221500Sadrian 263220559Sadrian#ifndef NDEBUG 264221500Sadrian // Update the ready queues. 265221500Sadrian void dump() const; 266221500Sadrian 267221500Sadrian // This routine performs a sanity check. This routine should only be called 268221500Sadrian // when we know that 'IR' is not in the scheduler's instruction queues. 269221500Sadrian void sanityCheck(const InstRef &IR) const { 270221500Sadrian assert(find(WaitSet, IR) == WaitSet.end() && "Already in the wait set!"); 271220559Sadrian assert(find(ReadySet, IR) == ReadySet.end() && "Already in the ready set!"); 272221500Sadrian assert(find(IssuedSet, IR) == IssuedSet.end() && "Already executing!"); 273220559Sadrian } 274221500Sadrian#endif // !NDEBUG 275221500Sadrian}; 276221500Sadrian} // namespace mca 277220559Sadrian} // namespace llvm 278221500Sadrian 279221500Sadrian#endif // LLVM_MCA_SCHEDULER_H 280221500Sadrian