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 277251662Sdim /// \brief True if an edge can be added from PredSU to SuccSU without creating 278251662Sdim /// a cycle. 279251662Sdim bool canAddEdge(SUnit *SuccSU, SUnit *PredSU); 280251662Sdim 281249423Sdim /// \brief Add a DAG edge to the given SU with the given predecessor 282249423Sdim /// dependence data. 283249423Sdim /// 284249423Sdim /// \returns true if the edge may be added without creating a cycle OR if an 285249423Sdim /// equivalent edge already existed (false indicates failure). 286249423Sdim bool addEdge(SUnit *SuccSU, const SDep &PredDep); 287249423Sdim 288243830Sdim MachineBasicBlock::iterator top() const { return CurrentTop; } 289243830Sdim MachineBasicBlock::iterator bottom() const { return CurrentBottom; } 290243830Sdim 291243830Sdim /// Implement the ScheduleDAGInstrs interface for handling the next scheduling 292243830Sdim /// region. This covers all instructions in a block, while schedule() may only 293243830Sdim /// cover a subset. 294243830Sdim void enterRegion(MachineBasicBlock *bb, 295243830Sdim MachineBasicBlock::iterator begin, 296243830Sdim MachineBasicBlock::iterator end, 297243830Sdim unsigned endcount); 298243830Sdim 299243830Sdim 300243830Sdim /// Implement ScheduleDAGInstrs interface for scheduling a sequence of 301243830Sdim /// reorderable instructions. 302243830Sdim virtual void schedule(); 303243830Sdim 304251662Sdim /// Change the position of an instruction within the basic block and update 305251662Sdim /// live ranges and region boundary iterators. 306251662Sdim void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos); 307251662Sdim 308243830Sdim /// Get current register pressure for the top scheduled instructions. 309243830Sdim const IntervalPressure &getTopPressure() const { return TopPressure; } 310243830Sdim const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; } 311243830Sdim 312243830Sdim /// Get current register pressure for the bottom scheduled instructions. 313243830Sdim const IntervalPressure &getBotPressure() const { return BotPressure; } 314243830Sdim const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; } 315243830Sdim 316243830Sdim /// Get register pressure for the entire scheduling region before scheduling. 317243830Sdim const IntervalPressure &getRegPressure() const { return RegPressure; } 318243830Sdim 319243830Sdim const std::vector<PressureElement> &getRegionCriticalPSets() const { 320243830Sdim return RegionCriticalPSets; 321243830Sdim } 322243830Sdim 323249423Sdim const SUnit *getNextClusterPred() const { return NextClusterPred; } 324249423Sdim 325249423Sdim const SUnit *getNextClusterSucc() const { return NextClusterSucc; } 326249423Sdim 327249423Sdim /// Compute a DFSResult after DAG building is complete, and before any 328249423Sdim /// queue comparisons. 329249423Sdim void computeDFSResult(); 330249423Sdim 331249423Sdim /// Return a non-null DFS result if the scheduling strategy initialized it. 332249423Sdim const SchedDFSResult *getDFSResult() const { return DFSResult; } 333249423Sdim 334249423Sdim BitVector &getScheduledTrees() { return ScheduledTrees; } 335249423Sdim 336249423Sdim void viewGraph(const Twine &Name, const Twine &Title) LLVM_OVERRIDE; 337249423Sdim void viewGraph() LLVM_OVERRIDE; 338249423Sdim 339243830Sdimprotected: 340243830Sdim // Top-Level entry points for the schedule() driver... 341243830Sdim 342243830Sdim /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking 343243830Sdim /// enabled. This sets up three trackers. RPTracker will cover the entire DAG 344243830Sdim /// region, TopTracker and BottomTracker will be initialized to the top and 345243830Sdim /// bottom of the DAG region without covereing any unscheduled instruction. 346243830Sdim void buildDAGWithRegPressure(); 347243830Sdim 348243830Sdim /// Apply each ScheduleDAGMutation step in order. This allows different 349243830Sdim /// instances of ScheduleDAGMI to perform custom DAG postprocessing. 350243830Sdim void postprocessDAG(); 351243830Sdim 352249423Sdim /// Release ExitSU predecessors and setup scheduler queues. 353249423Sdim void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots); 354243830Sdim 355243830Sdim /// Move an instruction and update register pressure. 356243830Sdim void scheduleMI(SUnit *SU, bool IsTopNode); 357243830Sdim 358243830Sdim /// Update scheduler DAG and queues after scheduling an instruction. 359243830Sdim void updateQueues(SUnit *SU, bool IsTopNode); 360243830Sdim 361243830Sdim /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues. 362243830Sdim void placeDebugValues(); 363243830Sdim 364243830Sdim /// \brief dump the scheduled Sequence. 365243830Sdim void dumpSchedule() const; 366243830Sdim 367243830Sdim // Lesser helpers... 368243830Sdim 369243830Sdim void initRegPressure(); 370243830Sdim 371249423Sdim void updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure); 372243830Sdim 373243830Sdim bool checkSchedLimit(); 374243830Sdim 375249423Sdim void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, 376249423Sdim SmallVectorImpl<SUnit*> &BotRoots); 377243830Sdim 378243830Sdim void releaseSucc(SUnit *SU, SDep *SuccEdge); 379243830Sdim void releaseSuccessors(SUnit *SU); 380243830Sdim void releasePred(SUnit *SU, SDep *PredEdge); 381243830Sdim void releasePredecessors(SUnit *SU); 382243830Sdim}; 383243830Sdim 384234285Sdim} // namespace llvm 385234285Sdim 386234285Sdim#endif 387