MachineScheduler.h revision 249423
1234285Sdim//==- MachineScheduler.h - MachineInstr Scheduling Pass ----------*- C++ -*-==// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This file provides a MachineSchedRegistry for registering alternative machine 11234285Sdim// schedulers. A Target may provide an alternative scheduler implementation by 12234285Sdim// implementing the following boilerplate: 13234285Sdim// 14234285Sdim// static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) { 15234285Sdim// return new CustomMachineScheduler(C); 16234285Sdim// } 17234285Sdim// static MachineSchedRegistry 18234285Sdim// SchedCustomRegistry("custom", "Run my target's custom scheduler", 19234285Sdim// createCustomMachineSched); 20234285Sdim// 21234285Sdim// Inside <Target>PassConfig: 22239462Sdim// enablePass(&MachineSchedulerID); 23234285Sdim// MachineSchedRegistry::setDefault(createCustomMachineSched); 24234285Sdim// 25234285Sdim//===----------------------------------------------------------------------===// 26234285Sdim 27249423Sdim#ifndef LLVM_CODEGEN_MACHINESCHEDULER_H 28249423Sdim#define LLVM_CODEGEN_MACHINESCHEDULER_H 29234285Sdim 30234285Sdim#include "llvm/CodeGen/MachinePassRegistry.h" 31243830Sdim#include "llvm/CodeGen/RegisterPressure.h" 32243830Sdim#include "llvm/CodeGen/ScheduleDAGInstrs.h" 33243830Sdim#include "llvm/Target/TargetInstrInfo.h" 34234285Sdim 35234285Sdimnamespace llvm { 36234285Sdim 37243830Sdimextern cl::opt<bool> ForceTopDown; 38243830Sdimextern cl::opt<bool> ForceBottomUp; 39243830Sdim 40234285Sdimclass AliasAnalysis; 41234285Sdimclass LiveIntervals; 42234285Sdimclass MachineDominatorTree; 43234285Sdimclass MachineLoopInfo; 44239462Sdimclass RegisterClassInfo; 45234285Sdimclass ScheduleDAGInstrs; 46249423Sdimclass SchedDFSResult; 47234285Sdim 48234285Sdim/// MachineSchedContext provides enough context from the MachineScheduler pass 49234285Sdim/// for the target to instantiate a scheduler. 50234285Sdimstruct MachineSchedContext { 51234285Sdim MachineFunction *MF; 52234285Sdim const MachineLoopInfo *MLI; 53234285Sdim const MachineDominatorTree *MDT; 54234285Sdim const TargetPassConfig *PassConfig; 55234285Sdim AliasAnalysis *AA; 56234285Sdim LiveIntervals *LIS; 57234285Sdim 58239462Sdim RegisterClassInfo *RegClassInfo; 59239462Sdim 60239462Sdim MachineSchedContext(); 61239462Sdim virtual ~MachineSchedContext(); 62234285Sdim}; 63234285Sdim 64234285Sdim/// MachineSchedRegistry provides a selection of available machine instruction 65234285Sdim/// schedulers. 66234285Sdimclass MachineSchedRegistry : public MachinePassRegistryNode { 67234285Sdimpublic: 68234285Sdim typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineSchedContext *); 69234285Sdim 70234285Sdim // RegisterPassParser requires a (misnamed) FunctionPassCtor type. 71234285Sdim typedef ScheduleDAGCtor FunctionPassCtor; 72234285Sdim 73234285Sdim static MachinePassRegistry Registry; 74234285Sdim 75234285Sdim MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C) 76234285Sdim : MachinePassRegistryNode(N, D, (MachinePassCtor)C) { 77234285Sdim Registry.Add(this); 78234285Sdim } 79234285Sdim ~MachineSchedRegistry() { Registry.Remove(this); } 80234285Sdim 81234285Sdim // Accessors. 82234285Sdim // 83234285Sdim MachineSchedRegistry *getNext() const { 84234285Sdim return (MachineSchedRegistry *)MachinePassRegistryNode::getNext(); 85234285Sdim } 86234285Sdim static MachineSchedRegistry *getList() { 87234285Sdim return (MachineSchedRegistry *)Registry.getList(); 88234285Sdim } 89234285Sdim static ScheduleDAGCtor getDefault() { 90234285Sdim return (ScheduleDAGCtor)Registry.getDefault(); 91234285Sdim } 92234285Sdim static void setDefault(ScheduleDAGCtor C) { 93234285Sdim Registry.setDefault((MachinePassCtor)C); 94234285Sdim } 95239462Sdim static void setDefault(StringRef Name) { 96239462Sdim Registry.setDefault(Name); 97239462Sdim } 98234285Sdim static void setListener(MachinePassRegistryListener *L) { 99234285Sdim Registry.setListener(L); 100234285Sdim } 101234285Sdim}; 102234285Sdim 103243830Sdimclass ScheduleDAGMI; 104243830Sdim 105243830Sdim/// MachineSchedStrategy - Interface to the scheduling algorithm used by 106243830Sdim/// ScheduleDAGMI. 107243830Sdimclass MachineSchedStrategy { 108243830Sdimpublic: 109243830Sdim virtual ~MachineSchedStrategy() {} 110243830Sdim 111243830Sdim /// Initialize the strategy after building the DAG for a new region. 112243830Sdim virtual void initialize(ScheduleDAGMI *DAG) = 0; 113243830Sdim 114243830Sdim /// Notify this strategy that all roots have been released (including those 115243830Sdim /// that depend on EntrySU or ExitSU). 116243830Sdim virtual void registerRoots() {} 117243830Sdim 118243830Sdim /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to 119243830Sdim /// schedule the node at the top of the unscheduled region. Otherwise it will 120243830Sdim /// be scheduled at the bottom. 121243830Sdim virtual SUnit *pickNode(bool &IsTopNode) = 0; 122243830Sdim 123249423Sdim /// \brief Scheduler callback to notify that a new subtree is scheduled. 124249423Sdim virtual void scheduleTree(unsigned SubtreeID) {} 125249423Sdim 126243830Sdim /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an 127243830Sdim /// instruction and updated scheduled/remaining flags in the DAG nodes. 128243830Sdim virtual void schedNode(SUnit *SU, bool IsTopNode) = 0; 129243830Sdim 130243830Sdim /// When all predecessor dependencies have been resolved, free this node for 131243830Sdim /// top-down scheduling. 132243830Sdim virtual void releaseTopNode(SUnit *SU) = 0; 133243830Sdim /// When all successor dependencies have been resolved, free this node for 134243830Sdim /// bottom-up scheduling. 135243830Sdim virtual void releaseBottomNode(SUnit *SU) = 0; 136243830Sdim}; 137243830Sdim 138243830Sdim/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience 139243830Sdim/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified 140243830Sdim/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in. 141243830Sdim/// 142243830Sdim/// This is a convenience class that may be used by implementations of 143243830Sdim/// MachineSchedStrategy. 144243830Sdimclass ReadyQueue { 145243830Sdim unsigned ID; 146243830Sdim std::string Name; 147243830Sdim std::vector<SUnit*> Queue; 148243830Sdim 149243830Sdimpublic: 150243830Sdim ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {} 151243830Sdim 152243830Sdim unsigned getID() const { return ID; } 153243830Sdim 154243830Sdim StringRef getName() const { return Name; } 155243830Sdim 156243830Sdim // SU is in this queue if it's NodeQueueID is a superset of this ID. 157243830Sdim bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); } 158243830Sdim 159243830Sdim bool empty() const { return Queue.empty(); } 160243830Sdim 161243830Sdim void clear() { Queue.clear(); } 162243830Sdim 163243830Sdim unsigned size() const { return Queue.size(); } 164243830Sdim 165243830Sdim typedef std::vector<SUnit*>::iterator iterator; 166243830Sdim 167243830Sdim iterator begin() { return Queue.begin(); } 168243830Sdim 169243830Sdim iterator end() { return Queue.end(); } 170243830Sdim 171249423Sdim ArrayRef<SUnit*> elements() { return Queue; } 172249423Sdim 173243830Sdim iterator find(SUnit *SU) { 174243830Sdim return std::find(Queue.begin(), Queue.end(), SU); 175243830Sdim } 176243830Sdim 177243830Sdim void push(SUnit *SU) { 178243830Sdim Queue.push_back(SU); 179243830Sdim SU->NodeQueueId |= ID; 180243830Sdim } 181243830Sdim 182243830Sdim iterator remove(iterator I) { 183243830Sdim (*I)->NodeQueueId &= ~ID; 184243830Sdim *I = Queue.back(); 185243830Sdim unsigned idx = I - Queue.begin(); 186243830Sdim Queue.pop_back(); 187243830Sdim return Queue.begin() + idx; 188243830Sdim } 189243830Sdim 190249423Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 191243830Sdim void dump(); 192243830Sdim#endif 193243830Sdim}; 194243830Sdim 195243830Sdim/// Mutate the DAG as a postpass after normal DAG building. 196243830Sdimclass ScheduleDAGMutation { 197243830Sdimpublic: 198243830Sdim virtual ~ScheduleDAGMutation() {} 199243830Sdim 200243830Sdim virtual void apply(ScheduleDAGMI *DAG) = 0; 201243830Sdim}; 202243830Sdim 203243830Sdim/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules 204243830Sdim/// machine instructions while updating LiveIntervals and tracking regpressure. 205243830Sdimclass ScheduleDAGMI : public ScheduleDAGInstrs { 206243830Sdimprotected: 207243830Sdim AliasAnalysis *AA; 208243830Sdim RegisterClassInfo *RegClassInfo; 209243830Sdim MachineSchedStrategy *SchedImpl; 210243830Sdim 211249423Sdim /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees 212249423Sdim /// will be empty. 213249423Sdim SchedDFSResult *DFSResult; 214249423Sdim BitVector ScheduledTrees; 215249423Sdim 216249423Sdim /// Topo - A topological ordering for SUnits which permits fast IsReachable 217249423Sdim /// and similar queries. 218249423Sdim ScheduleDAGTopologicalSort Topo; 219249423Sdim 220243830Sdim /// Ordered list of DAG postprocessing steps. 221243830Sdim std::vector<ScheduleDAGMutation*> Mutations; 222243830Sdim 223243830Sdim MachineBasicBlock::iterator LiveRegionEnd; 224243830Sdim 225243830Sdim /// Register pressure in this region computed by buildSchedGraph. 226243830Sdim IntervalPressure RegPressure; 227243830Sdim RegPressureTracker RPTracker; 228243830Sdim 229243830Sdim /// List of pressure sets that exceed the target's pressure limit before 230243830Sdim /// scheduling, listed in increasing set ID order. Each pressure set is paired 231243830Sdim /// with its max pressure in the currently scheduled regions. 232243830Sdim std::vector<PressureElement> RegionCriticalPSets; 233243830Sdim 234243830Sdim /// The top of the unscheduled zone. 235243830Sdim MachineBasicBlock::iterator CurrentTop; 236243830Sdim IntervalPressure TopPressure; 237243830Sdim RegPressureTracker TopRPTracker; 238243830Sdim 239243830Sdim /// The bottom of the unscheduled zone. 240243830Sdim MachineBasicBlock::iterator CurrentBottom; 241243830Sdim IntervalPressure BotPressure; 242243830Sdim RegPressureTracker BotRPTracker; 243243830Sdim 244249423Sdim /// Record the next node in a scheduled cluster. 245249423Sdim const SUnit *NextClusterPred; 246249423Sdim const SUnit *NextClusterSucc; 247249423Sdim 248243830Sdim#ifndef NDEBUG 249243830Sdim /// The number of instructions scheduled so far. Used to cut off the 250243830Sdim /// scheduler at the point determined by misched-cutoff. 251243830Sdim unsigned NumInstrsScheduled; 252243830Sdim#endif 253243830Sdim 254243830Sdimpublic: 255243830Sdim ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S): 256243830Sdim ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS), 257249423Sdim AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S), DFSResult(0), 258249423Sdim Topo(SUnits, &ExitSU), RPTracker(RegPressure), CurrentTop(), 259249423Sdim TopRPTracker(TopPressure), CurrentBottom(), BotRPTracker(BotPressure), 260249423Sdim NextClusterPred(NULL), NextClusterSucc(NULL) { 261243830Sdim#ifndef NDEBUG 262243830Sdim NumInstrsScheduled = 0; 263243830Sdim#endif 264243830Sdim } 265243830Sdim 266249423Sdim virtual ~ScheduleDAGMI(); 267243830Sdim 268243830Sdim /// Add a postprocessing step to the DAG builder. 269243830Sdim /// Mutations are applied in the order that they are added after normal DAG 270243830Sdim /// building and before MachineSchedStrategy initialization. 271249423Sdim /// 272249423Sdim /// ScheduleDAGMI takes ownership of the Mutation object. 273243830Sdim void addMutation(ScheduleDAGMutation *Mutation) { 274243830Sdim Mutations.push_back(Mutation); 275243830Sdim } 276243830Sdim 277249423Sdim /// \brief Add a DAG edge to the given SU with the given predecessor 278249423Sdim /// dependence data. 279249423Sdim /// 280249423Sdim /// \returns true if the edge may be added without creating a cycle OR if an 281249423Sdim /// equivalent edge already existed (false indicates failure). 282249423Sdim bool addEdge(SUnit *SuccSU, const SDep &PredDep); 283249423Sdim 284243830Sdim MachineBasicBlock::iterator top() const { return CurrentTop; } 285243830Sdim MachineBasicBlock::iterator bottom() const { return CurrentBottom; } 286243830Sdim 287243830Sdim /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 288243830Sdim /// region. This covers all instructions in a block, while schedule() may only 289243830Sdim /// cover a subset. 290243830Sdim void enterRegion(MachineBasicBlock *bb, 291243830Sdim MachineBasicBlock::iterator begin, 292243830Sdim MachineBasicBlock::iterator end, 293243830Sdim unsigned endcount); 294243830Sdim 295243830Sdim 296243830Sdim /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 297243830Sdim /// reorderable instructions. 298243830Sdim virtual void schedule(); 299243830Sdim 300243830Sdim /// Get current register pressure for the top scheduled instructions. 301243830Sdim const IntervalPressure &getTopPressure() const { return TopPressure; } 302243830Sdim const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } 303243830Sdim 304243830Sdim /// Get current register pressure for the bottom scheduled instructions. 305243830Sdim const IntervalPressure &getBotPressure() const { return BotPressure; } 306243830Sdim const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } 307243830Sdim 308243830Sdim /// Get register pressure for the entire scheduling region before scheduling. 309243830Sdim const IntervalPressure &getRegPressure() const { return RegPressure; } 310243830Sdim 311243830Sdim const std::vector<PressureElement> &getRegionCriticalPSets() const { 312243830Sdim return RegionCriticalPSets; 313243830Sdim } 314243830Sdim 315249423Sdim const SUnit *getNextClusterPred() const { return NextClusterPred; } 316249423Sdim 317249423Sdim const SUnit *getNextClusterSucc() const { return NextClusterSucc; } 318249423Sdim 319249423Sdim /// Compute a DFSResult after DAG building is complete, and before any 320249423Sdim /// queue comparisons. 321249423Sdim void computeDFSResult(); 322249423Sdim 323249423Sdim /// Return a non-null DFS result if the scheduling strategy initialized it. 324249423Sdim const SchedDFSResult *getDFSResult() const { return DFSResult; } 325249423Sdim 326249423Sdim BitVector &getScheduledTrees() { return ScheduledTrees; } 327249423Sdim 328249423Sdim void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE; 329249423Sdim void viewGraph() LLVM_OVERRIDE; 330249423Sdim 331243830Sdimprotected: 332243830Sdim // Top-Level entry points for the schedule() driver... 333243830Sdim 334243830Sdim /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking 335243830Sdim /// enabled. This sets up three trackers. RPTracker will cover the entire DAG 336243830Sdim /// region, TopTracker and BottomTracker will be initialized to the top and 337243830Sdim /// bottom of the DAG region without covereing any unscheduled instruction. 338243830Sdim void buildDAGWithRegPressure(); 339243830Sdim 340243830Sdim /// Apply each ScheduleDAGMutation step in order. This allows different 341243830Sdim /// instances of ScheduleDAGMI to perform custom DAG postprocessing. 342243830Sdim void postprocessDAG(); 343243830Sdim 344249423Sdim /// Release ExitSU predecessors and setup scheduler queues. 345249423Sdim void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots); 346243830Sdim 347243830Sdim /// Move an instruction and update register pressure. 348243830Sdim void scheduleMI(SUnit *SU, bool IsTopNode); 349243830Sdim 350243830Sdim /// Update scheduler DAG and queues after scheduling an instruction. 351243830Sdim void updateQueues(SUnit *SU, bool IsTopNode); 352243830Sdim 353243830Sdim /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. 354243830Sdim void placeDebugValues(); 355243830Sdim 356243830Sdim /// \brief dump the scheduled Sequence. 357243830Sdim void dumpSchedule() const; 358243830Sdim 359243830Sdim // Lesser helpers... 360243830Sdim 361243830Sdim void initRegPressure(); 362243830Sdim 363249423Sdim void updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure); 364243830Sdim 365243830Sdim void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); 366243830Sdim bool checkSchedLimit(); 367243830Sdim 368249423Sdim void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, 369249423Sdim SmallVectorImpl<SUnit*> &BotRoots); 370243830Sdim 371243830Sdim void releaseSucc(SUnit *SU, SDep *SuccEdge); 372243830Sdim void releaseSuccessors(SUnit *SU); 373243830Sdim void releasePred(SUnit *SU, SDep *PredEdge); 374243830Sdim void releasePredecessors(SUnit *SU); 375243830Sdim}; 376243830Sdim 377234285Sdim} // namespace llvm 378234285Sdim 379234285Sdim#endif 380