X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FMachineScheduler.h;h=c5f66a86a5ea199cbd9843608e7480a9cd1cc335;hp=d110ea1964da9c035232f5d05c75eca0eebb4edd;hb=cfe761c9e6cf97dc804725df08247b9402085f84;hpb=38084db681d99a7b167328cf5420c20f88036d1b diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index d110ea1964d..c5f66a86a5e 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -7,8 +7,48 @@ // //===----------------------------------------------------------------------===// // -// This file provides a MachineSchedRegistry for registering alternative machine -// schedulers. A Target may provide an alternative scheduler implementation by +// This file provides an interface for customizing the standard MachineScheduler +// pass. Note that the entire pass may be replaced as follows: +// +// TargetMachine::createPassConfig(PassManagerBase &PM) { +// PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID); +// ...} +// +// The MachineScheduler pass is only responsible for choosing the regions to be +// scheduled. Targets can override the DAG builder and scheduler without +// replacing the pass as follows: +// +// ScheduleDAGInstrs *PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// return new CustomMachineScheduler(C); +// } +// +// The default scheduler, ScheduleDAGMILive, builds the DAG and drives list +// scheduling while updating the instruction stream, register pressure, and live +// intervals. Most targets don't need to override the DAG builder and list +// schedulier, but subtargets that require custom scheduling heuristics may +// plugin an alternate MachineSchedStrategy. The strategy is responsible for +// selecting the highest priority node from the list: +// +// ScheduleDAGInstrs *PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// return new ScheduleDAGMI(C, CustomStrategy(C)); +// } +// +// The DAG builder can also be customized in a sense by adding DAG mutations +// that will run after DAG building and before list scheduling. DAG mutations +// can adjust dependencies based on target-specific knowledge or add weak edges +// to aid heuristics: +// +// ScheduleDAGInstrs *PassConfig:: +// createMachineScheduler(MachineSchedContext *C) { +// ScheduleDAGMI *DAG = new ScheduleDAGMI(C, CustomStrategy(C)); +// DAG->addMutation(new CustomDependencies(DAG->TII, DAG->TRI)); +// return DAG; +// } +// +// A target that supports alternative schedulers can use the +// MachineSchedRegistry to allow command line selection. This can be done by // implementing the following boilerplate: // // static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) { @@ -18,9 +58,19 @@ // SchedCustomRegistry("custom", "Run my target's custom scheduler", // createCustomMachineSched); // -// Inside PassConfig: -// enablePass(&MachineSchedulerID); -// MachineSchedRegistry::setDefault(createCustomMachineSched); +// +// Finally, subtargets that don't need to implement custom heuristics but would +// like to configure the GenericScheduler's policy for a given scheduler region, +// including scheduling direction and register pressure tracking policy, can do +// this: +// +// void Subtarget:: +// overrideSchedPolicy(MachineSchedPolicy &Policy, +// MachineInstr *begin, +// MachineInstr *end, +// unsigned NumRegionInstrs) const { +// Policy. = true; +// } // //===----------------------------------------------------------------------===// @@ -31,6 +81,8 @@ #include "llvm/CodeGen/RegisterPressure.h" #include "llvm/CodeGen/ScheduleDAGInstrs.h" +#include + namespace llvm { extern cl::opt ForceTopDown; @@ -43,6 +95,7 @@ class MachineLoopInfo; class RegisterClassInfo; class ScheduleDAGInstrs; class SchedDFSResult; +class ScheduleHazardRecognizer; /// MachineSchedContext provides enough context from the MachineScheduler pass /// for the target to instantiate a scheduler. @@ -85,15 +138,6 @@ public: static MachineSchedRegistry *getList() { return (MachineSchedRegistry *)Registry.getList(); } - static ScheduleDAGCtor getDefault() { - return (ScheduleDAGCtor)Registry.getDefault(); - } - static void setDefault(ScheduleDAGCtor C) { - Registry.setDefault((MachinePassCtor)C); - } - static void setDefault(StringRef Name) { - Registry.setDefault(Name); - } static void setListener(MachinePassRegistryListener *L) { Registry.setListener(L); } @@ -101,12 +145,41 @@ public: class ScheduleDAGMI; +/// Define a generic scheduling policy for targets that don't provide their own +/// MachineSchedStrategy. This can be overriden for each scheduling region +/// before building the DAG. +struct MachineSchedPolicy { + // Allow the scheduler to disable register pressure tracking. + bool ShouldTrackPressure; + + // Allow the scheduler to force top-down or bottom-up scheduling. If neither + // is true, the scheduler runs in both directions and converges. + bool OnlyTopDown; + bool OnlyBottomUp; + + MachineSchedPolicy(): ShouldTrackPressure(false), OnlyTopDown(false), + OnlyBottomUp(false) {} +}; + /// MachineSchedStrategy - Interface to the scheduling algorithm used by /// ScheduleDAGMI. +/// +/// Initialization sequence: +/// initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots class MachineSchedStrategy { + virtual void anchor(); public: virtual ~MachineSchedStrategy() {} + /// Optionally override the per-region scheduling policy. + virtual void initPolicy(MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + unsigned NumRegionInstrs) {} + + /// Check if pressure tracking is needed before building the DAG and + /// initializing this strategy. Called after initPolicy. + virtual bool shouldTrackPressure() const { return true; } + /// Initialize the strategy after building the DAG for a new region. virtual void initialize(ScheduleDAGMI *DAG) = 0; @@ -134,111 +207,36 @@ public: virtual void releaseBottomNode(SUnit *SU) = 0; }; -/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience -/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified -/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. -/// -/// This is a convenience class that may be used by implementations of -/// MachineSchedStrategy. -class ReadyQueue { - unsigned ID; - std::string Name; - std::vector Queue; - -public: - ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} - - unsigned getID() const { return ID; } - - StringRef getName() const { return Name; } - - // SU is in this queue if it's NodeQueueID is a superset of this ID. - bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } - - bool empty() const { return Queue.empty(); } - - void clear() { Queue.clear(); } - - unsigned size() const { return Queue.size(); } - - typedef std::vector::iterator iterator; - - iterator begin() { return Queue.begin(); } - - iterator end() { return Queue.end(); } - - ArrayRef elements() { return Queue; } - - iterator find(SUnit *SU) { - return std::find(Queue.begin(), Queue.end(), SU); - } - - void push(SUnit *SU) { - Queue.push_back(SU); - SU->NodeQueueId |= ID; - } - - iterator remove(iterator I) { - (*I)->NodeQueueId &= ~ID; - *I = Queue.back(); - unsigned idx = I - Queue.begin(); - Queue.pop_back(); - return Queue.begin() + idx; - } - -#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - void dump(); -#endif -}; - /// Mutate the DAG as a postpass after normal DAG building. class ScheduleDAGMutation { + virtual void anchor(); public: virtual ~ScheduleDAGMutation() {} virtual void apply(ScheduleDAGMI *DAG) = 0; }; -/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules -/// machine instructions while updating LiveIntervals and tracking regpressure. +/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply +/// schedules machine instructions according to the given MachineSchedStrategy +/// without much extra book-keeping. This is the common functionality between +/// PreRA and PostRA MachineScheduler. class ScheduleDAGMI : public ScheduleDAGInstrs { protected: AliasAnalysis *AA; - RegisterClassInfo *RegClassInfo; - MachineSchedStrategy *SchedImpl; - - /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees - /// will be empty. - SchedDFSResult *DFSResult; - BitVector ScheduledTrees; + std::unique_ptr SchedImpl; /// Topo - A topological ordering for SUnits which permits fast IsReachable /// and similar queries. ScheduleDAGTopologicalSort Topo; /// Ordered list of DAG postprocessing steps. - std::vector Mutations; - - MachineBasicBlock::iterator LiveRegionEnd; - - /// Register pressure in this region computed by buildSchedGraph. - IntervalPressure RegPressure; - RegPressureTracker RPTracker; - - /// List of pressure sets that exceed the target's pressure limit before - /// scheduling, listed in increasing set ID order. Each pressure set is paired - /// with its max pressure in the currently scheduled regions. - std::vector RegionCriticalPSets; + std::vector> Mutations; /// The top of the unscheduled zone. MachineBasicBlock::iterator CurrentTop; - IntervalPressure TopPressure; - RegPressureTracker TopRPTracker; /// The bottom of the unscheduled zone. MachineBasicBlock::iterator CurrentBottom; - IntervalPressure BotPressure; - RegPressureTracker BotRPTracker; /// Record the next node in a scheduled cluster. const SUnit *NextClusterPred; @@ -249,28 +247,31 @@ protected: /// scheduler at the point determined by misched-cutoff. unsigned NumInstrsScheduled; #endif - public: - ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): - ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), - AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0), - Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(), - TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), - NextClusterPred(NULL), NextClusterSucc(NULL) { + ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr S, + bool IsPostRA) + : ScheduleDAGInstrs(*C->MF, C->MLI, IsPostRA, + /*RemoveKillFlags=*/IsPostRA, C->LIS), + AA(C->AA), SchedImpl(std::move(S)), Topo(SUnits, &ExitSU), CurrentTop(), + CurrentBottom(), NextClusterPred(nullptr), NextClusterSucc(nullptr) { #ifndef NDEBUG NumInstrsScheduled = 0; #endif } - virtual ~ScheduleDAGMI(); + // Provide a vtable anchor + ~ScheduleDAGMI() override; + + /// Return true if this DAG supports VReg liveness and RegPressure. + virtual bool hasVRegLiveness() const { return false; } /// Add a postprocessing step to the DAG builder. /// Mutations are applied in the order that they are added after normal DAG /// building and before MachineSchedStrategy initialization. /// /// ScheduleDAGMI takes ownership of the Mutation object. - void addMutation(ScheduleDAGMutation *Mutation) { - Mutations.push_back(Mutation); + void addMutation(std::unique_ptr Mutation) { + Mutations.push_back(std::move(Mutation)); } /// \brief True if an edge can be added from PredSU to SuccSU without creating @@ -293,17 +294,106 @@ public: void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, - unsigned endcount); - + unsigned regioninstrs) override; /// Implement ScheduleDAGInstrs interface for scheduling a sequence of /// reorderable instructions. - virtual void schedule(); + void schedule() override; /// Change the position of an instruction within the basic block and update /// live ranges and region boundary iterators. void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); + const SUnit *getNextClusterPred() const { return NextClusterPred; } + + const SUnit *getNextClusterSucc() const { return NextClusterSucc; } + + void viewGraph(const Twine &Name, const Twine &Title) override; + void viewGraph() override; + +protected: + // Top-Level entry points for the schedule() driver... + + /// Apply each ScheduleDAGMutation step in order. This allows different + /// instances of ScheduleDAGMI to perform custom DAG postprocessing. + void postprocessDAG(); + + /// Release ExitSU predecessors and setup scheduler queues. + void initQueues(ArrayRef TopRoots, ArrayRef BotRoots); + + /// Update scheduler DAG and queues after scheduling an instruction. + void updateQueues(SUnit *SU, bool IsTopNode); + + /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. + void placeDebugValues(); + + /// \brief dump the scheduled Sequence. + void dumpSchedule() const; + + // Lesser helpers... + bool checkSchedLimit(); + + void findRootsAndBiasEdges(SmallVectorImpl &TopRoots, + SmallVectorImpl &BotRoots); + + void releaseSucc(SUnit *SU, SDep *SuccEdge); + void releaseSuccessors(SUnit *SU); + void releasePred(SUnit *SU, SDep *PredEdge); + void releasePredecessors(SUnit *SU); +}; + +/// ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules +/// machine instructions while updating LiveIntervals and tracking regpressure. +class ScheduleDAGMILive : public ScheduleDAGMI { +protected: + RegisterClassInfo *RegClassInfo; + + /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees + /// will be empty. + SchedDFSResult *DFSResult; + BitVector ScheduledTrees; + + MachineBasicBlock::iterator LiveRegionEnd; + + // Map each SU to its summary of pressure changes. This array is updated for + // liveness during bottom-up scheduling. Top-down scheduling may proceed but + // has no affect on the pressure diffs. + PressureDiffs SUPressureDiffs; + + /// Register pressure in this region computed by initRegPressure. + bool ShouldTrackPressure; + IntervalPressure RegPressure; + RegPressureTracker RPTracker; + + /// List of pressure sets that exceed the target's pressure limit before + /// scheduling, listed in increasing set ID order. Each pressure set is paired + /// with its max pressure in the currently scheduled regions. + std::vector RegionCriticalPSets; + + /// The top of the unscheduled zone. + IntervalPressure TopPressure; + RegPressureTracker TopRPTracker; + + /// The bottom of the unscheduled zone. + IntervalPressure BotPressure; + RegPressureTracker BotRPTracker; + +public: + ScheduleDAGMILive(MachineSchedContext *C, + std::unique_ptr S) + : ScheduleDAGMI(C, std::move(S), /*IsPostRA=*/false), + RegClassInfo(C->RegClassInfo), DFSResult(nullptr), + ShouldTrackPressure(false), RPTracker(RegPressure), + TopRPTracker(TopPressure), BotRPTracker(BotPressure) {} + + virtual ~ScheduleDAGMILive(); + + /// Return true if this DAG supports VReg liveness and RegPressure. + bool hasVRegLiveness() const override { return true; } + + /// \brief Return true if register pressure tracking is enabled. + bool isTrackingPressure() const { return ShouldTrackPressure; } + /// Get current register pressure for the top scheduled instructions. const IntervalPressure &getTopPressure() const { return TopPressure; } const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } @@ -315,13 +405,13 @@ public: /// Get register pressure for the entire scheduling region before scheduling. const IntervalPressure &getRegPressure() const { return RegPressure; } - const std::vector &getRegionCriticalPSets() const { + const std::vector &getRegionCriticalPSets() const { return RegionCriticalPSets; } - const SUnit *getNextClusterPred() const { return NextClusterPred; } - - const SUnit *getNextClusterSucc() const { return NextClusterSucc; } + PressureDiff &getPressureDiff(const SUnit *SU) { + return SUPressureDiffs[SU->NodeNum]; + } /// Compute a DFSResult after DAG building is complete, and before any /// queue comparisons. @@ -332,8 +422,20 @@ public: BitVector &getScheduledTrees() { return ScheduledTrees; } - void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE; - void viewGraph() LLVM_OVERRIDE; + /// Implement the ScheduleDAGInstrs interface for handling the next scheduling + /// region. This covers all instructions in a block, while schedule() may only + /// cover a subset. + void enterRegion(MachineBasicBlock *bb, + MachineBasicBlock::iterator begin, + MachineBasicBlock::iterator end, + unsigned regioninstrs) override; + + /// Implement ScheduleDAGInstrs interface for scheduling a sequence of + /// reorderable instructions. + void schedule() override; + + /// Compute the cyclic critical path through the DAG. + unsigned computeCyclicCriticalPath(); protected: // Top-Level entry points for the schedule() driver... @@ -344,40 +446,506 @@ protected: /// bottom of the DAG region without covereing any unscheduled instruction. void buildDAGWithRegPressure(); - /// Apply each ScheduleDAGMutation step in order. This allows different - /// instances of ScheduleDAGMI to perform custom DAG postprocessing. - void postprocessDAG(); - - /// Release ExitSU predecessors and setup scheduler queues. - void initQueues(ArrayRef TopRoots, ArrayRef BotRoots); - /// Move an instruction and update register pressure. void scheduleMI(SUnit *SU, bool IsTopNode); - /// Update scheduler DAG and queues after scheduling an instruction. - void updateQueues(SUnit *SU, bool IsTopNode); + // Lesser helpers... - /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. - void placeDebugValues(); + void initRegPressure(); - /// \brief dump the scheduled Sequence. - void dumpSchedule() const; + void updatePressureDiffs(ArrayRef LiveUses); - // Lesser helpers... + void updateScheduledPressure(const SUnit *SU, + const std::vector &NewMaxPressure); +}; - void initRegPressure(); +//===----------------------------------------------------------------------===// +/// +/// Helpers for implementing custom MachineSchedStrategy classes. These take +/// care of the book-keeping associated with list scheduling heuristics. +/// +//===----------------------------------------------------------------------===// - void updateScheduledPressure(const std::vector &NewMaxPressure); +/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience +/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified +/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. +/// +/// This is a convenience class that may be used by implementations of +/// MachineSchedStrategy. +class ReadyQueue { + unsigned ID; + std::string Name; + std::vector Queue; - bool checkSchedLimit(); +public: + ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} - void findRootsAndBiasEdges(SmallVectorImpl &TopRoots, - SmallVectorImpl &BotRoots); + unsigned getID() const { return ID; } - void releaseSucc(SUnit *SU, SDep *SuccEdge); - void releaseSuccessors(SUnit *SU); - void releasePred(SUnit *SU, SDep *PredEdge); - void releasePredecessors(SUnit *SU); + StringRef getName() const { return Name; } + + // SU is in this queue if it's NodeQueueID is a superset of this ID. + bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } + + bool empty() const { return Queue.empty(); } + + void clear() { Queue.clear(); } + + unsigned size() const { return Queue.size(); } + + typedef std::vector::iterator iterator; + + iterator begin() { return Queue.begin(); } + + iterator end() { return Queue.end(); } + + ArrayRef elements() { return Queue; } + + iterator find(SUnit *SU) { + return std::find(Queue.begin(), Queue.end(), SU); + } + + void push(SUnit *SU) { + Queue.push_back(SU); + SU->NodeQueueId |= ID; + } + + iterator remove(iterator I) { + (*I)->NodeQueueId &= ~ID; + *I = Queue.back(); + unsigned idx = I - Queue.begin(); + Queue.pop_back(); + return Queue.begin() + idx; + } + + void dump(); +}; + +/// Summarize the unscheduled region. +struct SchedRemainder { + // Critical path through the DAG in expected latency. + unsigned CriticalPath; + unsigned CyclicCritPath; + + // Scaled count of micro-ops left to schedule. + unsigned RemIssueCount; + + bool IsAcyclicLatencyLimited; + + // Unscheduled resources + SmallVector RemainingCounts; + + void reset() { + CriticalPath = 0; + CyclicCritPath = 0; + RemIssueCount = 0; + IsAcyclicLatencyLimited = false; + RemainingCounts.clear(); + } + + SchedRemainder() { reset(); } + + void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel); +}; + +/// Each Scheduling boundary is associated with ready queues. It tracks the +/// current cycle in the direction of movement, and maintains the state +/// of "hazards" and other interlocks at the current cycle. +class SchedBoundary { +public: + /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) + enum { + TopQID = 1, + BotQID = 2, + LogMaxQID = 2 + }; + + ScheduleDAGMI *DAG; + const TargetSchedModel *SchedModel; + SchedRemainder *Rem; + + ReadyQueue Available; + ReadyQueue Pending; + + ScheduleHazardRecognizer *HazardRec; + +private: + /// True if the pending Q should be checked/updated before scheduling another + /// instruction. + bool CheckPending; + + // For heuristics, keep a list of the nodes that immediately depend on the + // most recently scheduled node. + SmallPtrSet NextSUs; + + /// Number of cycles it takes to issue the instructions scheduled in this + /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls. + /// See getStalls(). + unsigned CurrCycle; + + /// Micro-ops issued in the current cycle + unsigned CurrMOps; + + /// MinReadyCycle - Cycle of the soonest available instruction. + unsigned MinReadyCycle; + + // The expected latency of the critical path in this scheduled zone. + unsigned ExpectedLatency; + + // The latency of dependence chains leading into this zone. + // For each node scheduled bottom-up: DLat = max DLat, N.Depth. + // For each cycle scheduled: DLat -= 1. + unsigned DependentLatency; + + /// Count the scheduled (issued) micro-ops that can be retired by + /// time=CurrCycle assuming the first scheduled instr is retired at time=0. + unsigned RetiredMOps; + + // Count scheduled resources that have been executed. Resources are + // considered executed if they become ready in the time that it takes to + // saturate any resource including the one in question. Counts are scaled + // for direct comparison with other resources. Counts can be compared with + // MOps * getMicroOpFactor and Latency * getLatencyFactor. + SmallVector ExecutedResCounts; + + /// Cache the max count for a single resource. + unsigned MaxExecutedResCount; + + // Cache the critical resources ID in this scheduled zone. + unsigned ZoneCritResIdx; + + // Is the scheduled region resource limited vs. latency limited. + bool IsResourceLimited; + + // Record the highest cycle at which each resource has been reserved by a + // scheduled instruction. + SmallVector ReservedCycles; + +#ifndef NDEBUG + // Remember the greatest possible stall as an upper bound on the number of + // times we should retry the pending queue because of a hazard. + unsigned MaxObservedStall; +#endif + +public: + /// Pending queues extend the ready queues with the same ID and the + /// PendingFlag set. + SchedBoundary(unsigned ID, const Twine &Name): + DAG(nullptr), SchedModel(nullptr), Rem(nullptr), Available(ID, Name+".A"), + Pending(ID << LogMaxQID, Name+".P"), + HazardRec(nullptr) { + reset(); + } + + ~SchedBoundary(); + + void reset(); + + void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, + SchedRemainder *rem); + + bool isTop() const { + return Available.getID() == TopQID; + } + + /// Number of cycles to issue the instructions scheduled in this zone. + unsigned getCurrCycle() const { return CurrCycle; } + + /// Micro-ops issued in the current cycle + unsigned getCurrMOps() const { return CurrMOps; } + + /// Return true if the given SU is used by the most recently scheduled + /// instruction. + bool isNextSU(const SUnit *SU) const { return NextSUs.count(SU); } + + // The latency of dependence chains leading into this zone. + unsigned getDependentLatency() const { return DependentLatency; } + + /// Get the number of latency cycles "covered" by the scheduled + /// instructions. This is the larger of the critical path within the zone + /// and the number of cycles required to issue the instructions. + unsigned getScheduledLatency() const { + return std::max(ExpectedLatency, CurrCycle); + } + + unsigned getUnscheduledLatency(SUnit *SU) const { + return isTop() ? SU->getHeight() : SU->getDepth(); + } + + unsigned getResourceCount(unsigned ResIdx) const { + return ExecutedResCounts[ResIdx]; + } + + /// Get the scaled count of scheduled micro-ops and resources, including + /// executed resources. + unsigned getCriticalCount() const { + if (!ZoneCritResIdx) + return RetiredMOps * SchedModel->getMicroOpFactor(); + return getResourceCount(ZoneCritResIdx); + } + + /// Get a scaled count for the minimum execution time of the scheduled + /// micro-ops that are ready to execute by getExecutedCount. Notice the + /// feedback loop. + unsigned getExecutedCount() const { + return std::max(CurrCycle * SchedModel->getLatencyFactor(), + MaxExecutedResCount); + } + + unsigned getZoneCritResIdx() const { return ZoneCritResIdx; } + + // Is the scheduled region resource limited vs. latency limited. + bool isResourceLimited() const { return IsResourceLimited; } + + /// Get the difference between the given SUnit's ready time and the current + /// cycle. + unsigned getLatencyStallCycles(SUnit *SU); + + unsigned getNextResourceCycle(unsigned PIdx, unsigned Cycles); + + bool checkHazard(SUnit *SU); + + unsigned findMaxLatency(ArrayRef ReadySUs); + + unsigned getOtherResourceCount(unsigned &OtherCritIdx); + + void releaseNode(SUnit *SU, unsigned ReadyCycle); + + void releaseTopNode(SUnit *SU); + + void releaseBottomNode(SUnit *SU); + + void bumpCycle(unsigned NextCycle); + + void incExecutedResources(unsigned PIdx, unsigned Count); + + unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle); + + void bumpNode(SUnit *SU); + + void releasePending(); + + void removeReady(SUnit *SU); + + /// Call this before applying any other heuristics to the Available queue. + /// Updates the Available/Pending Q's if necessary and returns the single + /// available instruction, or NULL if there are multiple candidates. + SUnit *pickOnlyChoice(); + +#ifndef NDEBUG + void dumpScheduledState(); +#endif +}; + +/// Base class for GenericScheduler. This class maintains information about +/// scheduling candidates based on TargetSchedModel making it easy to implement +/// heuristics for either preRA or postRA scheduling. +class GenericSchedulerBase : public MachineSchedStrategy { +public: + /// Represent the type of SchedCandidate found within a single queue. + /// pickNodeBidirectional depends on these listed by decreasing priority. + enum CandReason { + NoCand, PhysRegCopy, RegExcess, RegCritical, Stall, Cluster, Weak, RegMax, + ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce, + TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder}; + +#ifndef NDEBUG + static const char *getReasonStr(GenericSchedulerBase::CandReason Reason); +#endif + + /// Policy for scheduling the next instruction in the candidate's zone. + struct CandPolicy { + bool ReduceLatency; + unsigned ReduceResIdx; + unsigned DemandResIdx; + + CandPolicy(): ReduceLatency(false), ReduceResIdx(0), DemandResIdx(0) {} + }; + + /// Status of an instruction's critical resource consumption. + struct SchedResourceDelta { + // Count critical resources in the scheduled region required by SU. + unsigned CritResources; + + // Count critical resources from another region consumed by SU. + unsigned DemandedResources; + + SchedResourceDelta(): CritResources(0), DemandedResources(0) {} + + bool operator==(const SchedResourceDelta &RHS) const { + return CritResources == RHS.CritResources + && DemandedResources == RHS.DemandedResources; + } + bool operator!=(const SchedResourceDelta &RHS) const { + return !operator==(RHS); + } + }; + + /// Store the state used by GenericScheduler heuristics, required for the + /// lifetime of one invocation of pickNode(). + struct SchedCandidate { + CandPolicy Policy; + + // The best SUnit candidate. + SUnit *SU; + + // The reason for this candidate. + CandReason Reason; + + // Set of reasons that apply to multiple candidates. + uint32_t RepeatReasonSet; + + // Register pressure values for the best candidate. + RegPressureDelta RPDelta; + + // Critical resource consumption of the best candidate. + SchedResourceDelta ResDelta; + + SchedCandidate(const CandPolicy &policy) + : Policy(policy), SU(nullptr), Reason(NoCand), RepeatReasonSet(0) {} + + bool isValid() const { return SU; } + + // Copy the status of another candidate without changing policy. + void setBest(SchedCandidate &Best) { + assert(Best.Reason != NoCand && "uninitialized Sched candidate"); + SU = Best.SU; + Reason = Best.Reason; + RPDelta = Best.RPDelta; + ResDelta = Best.ResDelta; + } + + bool isRepeat(CandReason R) { return RepeatReasonSet & (1 << R); } + void setRepeat(CandReason R) { RepeatReasonSet |= (1 << R); } + + void initResourceDelta(const ScheduleDAGMI *DAG, + const TargetSchedModel *SchedModel); + }; + +protected: + const MachineSchedContext *Context; + const TargetSchedModel *SchedModel; + const TargetRegisterInfo *TRI; + + SchedRemainder Rem; +protected: + GenericSchedulerBase(const MachineSchedContext *C): + Context(C), SchedModel(nullptr), TRI(nullptr) {} + + void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone, + SchedBoundary *OtherZone); + +#ifndef NDEBUG + void traceCandidate(const SchedCandidate &Cand); +#endif +}; + +/// GenericScheduler shrinks the unscheduled zone using heuristics to balance +/// the schedule. +class GenericScheduler : public GenericSchedulerBase { + ScheduleDAGMILive *DAG; + + // State of the top and bottom scheduled instruction boundaries. + SchedBoundary Top; + SchedBoundary Bot; + + MachineSchedPolicy RegionPolicy; +public: + GenericScheduler(const MachineSchedContext *C): + GenericSchedulerBase(C), DAG(nullptr), Top(SchedBoundary::TopQID, "TopQ"), + Bot(SchedBoundary::BotQID, "BotQ") {} + + void initPolicy(MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + unsigned NumRegionInstrs) override; + + bool shouldTrackPressure() const override { + return RegionPolicy.ShouldTrackPressure; + } + + void initialize(ScheduleDAGMI *dag) override; + + SUnit *pickNode(bool &IsTopNode) override; + + void schedNode(SUnit *SU, bool IsTopNode) override; + + void releaseTopNode(SUnit *SU) override { + Top.releaseTopNode(SU); + } + + void releaseBottomNode(SUnit *SU) override { + Bot.releaseBottomNode(SU); + } + + void registerRoots() override; + +protected: + void checkAcyclicLatency(); + + void tryCandidate(SchedCandidate &Cand, + SchedCandidate &TryCand, + SchedBoundary &Zone, + const RegPressureTracker &RPTracker, + RegPressureTracker &TempTracker); + + SUnit *pickNodeBidirectional(bool &IsTopNode); + + void pickNodeFromQueue(SchedBoundary &Zone, + const RegPressureTracker &RPTracker, + SchedCandidate &Candidate); + + void reschedulePhysRegCopies(SUnit *SU, bool isTop); +}; + +/// PostGenericScheduler - Interface to the scheduling algorithm used by +/// ScheduleDAGMI. +/// +/// Callbacks from ScheduleDAGMI: +/// initPolicy -> initialize(DAG) -> registerRoots -> pickNode ... +class PostGenericScheduler : public GenericSchedulerBase { + ScheduleDAGMI *DAG; + SchedBoundary Top; + SmallVector BotRoots; +public: + PostGenericScheduler(const MachineSchedContext *C): + GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {} + + virtual ~PostGenericScheduler() {} + + void initPolicy(MachineBasicBlock::iterator Begin, + MachineBasicBlock::iterator End, + unsigned NumRegionInstrs) override { + /* no configurable policy */ + }; + + /// PostRA scheduling does not track pressure. + bool shouldTrackPressure() const override { return false; } + + void initialize(ScheduleDAGMI *Dag) override; + + void registerRoots() override; + + SUnit *pickNode(bool &IsTopNode) override; + + void scheduleTree(unsigned SubtreeID) override { + llvm_unreachable("PostRA scheduler does not support subtree analysis."); + } + + void schedNode(SUnit *SU, bool IsTopNode) override; + + void releaseTopNode(SUnit *SU) override { + Top.releaseTopNode(SU); + } + + // Only called for roots. + void releaseBottomNode(SUnit *SU) override { + BotRoots.push_back(SU); + } + +protected: + void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand); + + void pickNodeFromQueue(SchedCandidate &Cand); }; } // namespace llvm